weak_table/
weak_weak_hash_map.rs

1//! A hash map where the keys and values are both held by weak pointers, and keys are compared by
2//! value.
3
4use super::size_policy::*;
5use super::traits::*;
6use super::*;
7
8pub use super::WeakWeakHashMap;
9
10/// Represents an entry in the table which may be occupied or vacant.
11#[allow(clippy::exhaustive_enums)]
12pub enum Entry<'a, K: 'a + WeakKey, V: 'a + WeakElement> {
13    /// An occupied entry.
14    Occupied(OccupiedEntry<'a, K, V>),
15    /// A vacant entry.
16    Vacant(VacantEntry<'a, K, V>),
17}
18
19/// An occupied entry, which can be removed, modified, or viewed.
20pub struct OccupiedEntry<'a, K: 'a + WeakKey, V: 'a + WeakElement>(
21    inner::OccupiedEntry<'a, inner::WeakK<K>, inner::WeakV<V>>,
22);
23
24/// A vacant entry, which can be inserted in or viewed.
25pub struct VacantEntry<'a, K: 'a + WeakKey, V: 'a + WeakElement>(
26    inner::VacantEntry<'a, inner::WeakK<K>, inner::WeakV<V>>,
27);
28
29/// An iterator over the keys and values of the weak hash map.
30#[derive(Clone, Debug)]
31pub struct Iter<'a, K: 'a, V: 'a>(inner::Iter<'a, inner::WeakK<K>, inner::WeakV<V>>);
32
33impl<'a, K: WeakElement, V: WeakElement> Iterator for Iter<'a, K, V> {
34    type Item = (K::Strong, V::Strong);
35
36    fn next(&mut self) -> Option<Self::Item> {
37        self.0.next()
38    }
39
40    fn size_hint(&self) -> (usize, Option<usize>) {
41        self.0.size_hint()
42    }
43}
44
45/// An iterator over the keys of the weak hash map.
46#[derive(Clone, Debug)]
47pub struct Keys<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
48
49impl<'a, K: WeakElement, V: WeakElement> Iterator for Keys<'a, K, V> {
50    type Item = K::Strong;
51
52    fn next(&mut self) -> Option<Self::Item> {
53        self.0.next().map(|(k, _)| k)
54    }
55
56    fn size_hint(&self) -> (usize, Option<usize>) {
57        self.0.size_hint()
58    }
59}
60
61/// An iterator over the values of the weak hash map.
62#[derive(Clone, Debug)]
63pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
64
65impl<'a, K: WeakElement, V: WeakElement> Iterator for Values<'a, K, V> {
66    type Item = V::Strong;
67
68    fn next(&mut self) -> Option<Self::Item> {
69        self.0.next().map(|(_, v)| v)
70    }
71
72    fn size_hint(&self) -> (usize, Option<usize>) {
73        self.0.size_hint()
74    }
75}
76
77#[derive(Debug)]
78/// An iterator that consumes the values of a weak hash map, leaving it empty.
79///
80/// Once this iterator is dropped, all values are removed from the map,
81/// whether the iterator itself was drained or not.
82pub struct Drain<'a, K: 'a, V: 'a>(inner::Drain<'a, inner::WeakK<K>, inner::WeakV<V>>);
83
84impl<'a, K: WeakElement, V: WeakElement> Iterator for Drain<'a, K, V> {
85    type Item = (K::Strong, V::Strong);
86
87    fn next(&mut self) -> Option<Self::Item> {
88        self.0.next()
89    }
90
91    fn size_hint(&self) -> (usize, Option<usize>) {
92        self.0.size_hint()
93    }
94}
95
96/// An iterator that consumes a weak hash map, leaving it empty.
97pub struct IntoIter<K, V>(inner::IntoIter<inner::WeakK<K>, inner::WeakV<V>>);
98
99impl<K: WeakElement, V: WeakElement> Iterator for IntoIter<K, V> {
100    type Item = (K::Strong, V::Strong);
101
102    fn next(&mut self) -> Option<Self::Item> {
103        self.0.next()
104    }
105
106    fn size_hint(&self) -> (usize, Option<usize>) {
107        self.0.size_hint()
108    }
109}
110
111impl<K: WeakKey, V: WeakElement> WeakWeakHashMap<K, V, RandomState> {
112    /// Creates an empty `WeakWeakHashMap`.
113    ///
114    /// *O*(1) time
115    pub fn new() -> Self {
116        Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
117    }
118
119    /// Creates an empty `WeakWeakHashMap` with the given capacity.
120    ///
121    /// *O*(*n*) time
122    pub fn with_capacity(capacity: usize) -> Self {
123        Self::with_capacity_and_hasher(capacity, Default::default())
124    }
125}
126
127impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
128    /// Creates an empty `WeakWeakHashMap` with the given hasher.
129    ///
130    /// *O*(*n*) time
131    pub fn with_hasher(hash_builder: S) -> Self {
132        Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
133    }
134
135    /// Creates an empty `WeakWeakHashMap` with the given capacity and hasher.
136    ///
137    /// *O*(*n*) time
138    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
139        WeakWeakHashMap(inner::Table::new(capacity, hash_builder))
140    }
141
142    /// Returns a reference to the map's `BuildHasher`.
143    ///
144    /// *O*(1) time
145    pub fn hasher(&self) -> &S {
146        self.0.hasher()
147    }
148
149    /// Returns the number of elements the map can hold without reallocating.
150    ///
151    /// *O*(1) time
152    pub fn capacity(&self) -> usize {
153        self.0.capacity()
154    }
155
156    /// Removes all mappings whose keys have expired.
157    ///
158    /// *O*(*n*) time
159    pub fn remove_expired(&mut self) {
160        self.retain(|_, _| true);
161    }
162
163    /// Reserves room for additional elements.
164    ///
165    /// This method ensures that at least `additional_capacity` insertions
166    /// may be performed without reallocating.
167    ///
168    /// *O*(*n*) time
169    pub fn reserve(&mut self, additional_capacity: usize) {
170        self.0
171            .try_reserve(additional_capacity)
172            .expect("try_reserve failed");
173    }
174
175    /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
176    ///
177    /// *O*(*n*) time
178    pub fn shrink_to_fit(&mut self) {
179        self.0.shrink_to_fit();
180    }
181
182    /// Returns an over-approximation of the number of elements.
183    ///
184    /// (This is an over-approximation because it includes expired elements.)
185    ///
186    /// (This is an over-approximation because it includes expired elements.)
187    ///    /// *O*(1) time
188    pub fn len(&self) -> usize {
189        self.0.len()
190    }
191
192    /// Is the map empty?
193    ///
194    /// Note that this may return false even if all keys in the map have
195    /// expired, if they haven't been collected yet.
196    ///
197    /// *O*(1) time
198    pub fn is_empty(&self) -> bool {
199        self.len() == 0
200    }
201
202    /// The proportion of buckets that are used.
203    ///
204    /// This is an over-approximation because of expired keys.
205    ///
206    /// *O*(1) time
207    pub fn load_factor(&self) -> f32 {
208        (self.len() as f32 + 1.0) / self.capacity() as f32
209    }
210
211    /// Gets the requested entry.
212    ///
213    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
214    /// `self.capacity()` and *q* is the length of the probe sequences
215    /// in `other`)
216    pub fn entry(&mut self, key: K::Strong) -> Entry<'_, K, V> {
217        match self.0.entry(key) {
218            inner::Entry::Occupied(occupied) => Entry::Occupied(OccupiedEntry(occupied)),
219            inner::Entry::Vacant(vacant) => Entry::Vacant(VacantEntry(vacant)),
220        }
221    }
222
223    /// Removes all associations from the map.
224    ///
225    /// *O*(*n*) time
226    pub fn clear(&mut self) {
227        self.0.clear();
228    }
229
230    /// Returns a reference to the value corresponding to the key.
231    ///
232    /// Returns `None` if no matching key is found.
233    ///
234    /// expected *O*(1) time; worst-case *O*(*p*) time
235    pub fn get<Q>(&self, key: &Q) -> Option<V::Strong>
236    where
237        Q: ?Sized + Hash + Eq,
238        K::Key: Borrow<Q>,
239    {
240        Some(self.0.find(key)?.1)
241    }
242
243    /// Returns the strong reference to the key, if present.
244    ///
245    /// expected *O*(1) time; worst-case *O*(*p*) time
246    pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
247    where
248        Q: ?Sized + Hash + Eq,
249        K::Key: Borrow<Q>,
250    {
251        Some(self.0.find(key)?.0)
252    }
253
254    /// Returns strong references to both the key and the value, if present.
255    ///
256    /// expected *O*(1) time; worst-case *O*(*p*) time
257    pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, V::Strong)>
258    where
259        Q: ?Sized + Hash + Eq,
260        K::Key: Borrow<Q>,
261    {
262        self.0.find(key)
263    }
264
265    /// Returns true if the map contains the specified key.
266    ///
267    /// expected *O*(1) time; worst-case *O*(*p*) time
268    pub fn contains_key<Q>(&self, key: &Q) -> bool
269    where
270        Q: ?Sized + Hash + Eq,
271        K::Key: Borrow<Q>,
272    {
273        self.0.find(key).is_some()
274    }
275
276    /// Unconditionally inserts the value, returning the old value if already present.
277    ///
278    /// Unlike `std::collections::HashMap`, this replaces the key even if occupied.
279    ///
280    /// expected *O*(1) time; worst-case *O*(*p*) time
281    pub fn insert(&mut self, key: K::Strong, value: V::Strong) -> Option<V::Strong> {
282        match self.entry(key) {
283            Entry::Occupied(mut occupied) => Some(occupied.insert(value)),
284            Entry::Vacant(vacant) => {
285                vacant.insert(value);
286                None
287            }
288        }
289    }
290
291    /// Removes the entry with the given key, if it exists, and returns the value.
292    ///
293    /// expected *O*(1) time; worst-case *O*(*p*) time
294    pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong>
295    where
296        Q: ?Sized + Hash + Eq,
297        K::Key: Borrow<Q>,
298    {
299        self.0.find_entry(key).map(|occupied| occupied.remove().1)
300    }
301
302    /// Removes all mappings not satisfying the given predicate.
303    ///
304    /// Also removes any expired mappings.
305    ///
306    /// *O*(*n*) time
307    pub fn retain<F>(&mut self, mut f: F)
308    where
309        F: FnMut(K::Strong, V::Strong) -> bool,
310    {
311        // TODO: It would be better to use a retain method on Table, but I've
312        // run into lifetime issues there. See "TODO retain" in inner/table.rs
313        self.0.table.retain(|(k, v)| {
314            if let (Some(k), Some(v)) = (k.val.view(), v.val.view()) {
315                f(k, v)
316            } else {
317                false
318            }
319        });
320    }
321
322    /// Is this map a submap of the other, using the given value comparison.
323    ///
324    /// In particular, all the keys of `self` must be in `other` and the values must compare
325    /// `true` with `value_equal`.
326    ///
327    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
328    /// `self.capacity()` and *q* is the length of the probe sequences
329    /// in `other`)
330    pub fn is_submap_with<F, S1, V1>(
331        &self,
332        other: &WeakWeakHashMap<K, V1, S1>,
333        mut value_equal: F,
334    ) -> bool
335    where
336        V1: WeakElement,
337        F: FnMut(V::Strong, V1::Strong) -> bool,
338        S1: BuildHasher,
339    {
340        for (key, value1) in self {
341            if let Some(value2) = K::with_key(&key, |k| other.get(k)) {
342                if !value_equal(value1, value2) {
343                    return false;
344                }
345            } else {
346                return false;
347            }
348        }
349
350        true
351    }
352
353    /// Is `self` a submap of `other`?
354    ///
355    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
356    /// `self.capacity()` and *q* is the length of the probe sequences
357    /// in `other`)
358    pub fn is_submap<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool
359    where
360        V1: WeakElement,
361        V::Strong: PartialEq<V1::Strong>,
362        S1: BuildHasher,
363    {
364        self.is_submap_with(other, |v, v1| v == v1)
365    }
366
367    /// Are the keys of `self` a subset of the keys of `other`?
368    ///
369    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
370    /// `self.capacity()` and *q* is the length of the probe sequences
371    /// in `other`)
372    pub fn domain_is_subset<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool
373    where
374        V1: WeakElement,
375        S1: BuildHasher,
376    {
377        self.is_submap_with(other, |_, _| true)
378    }
379}
380
381impl<K, V, V1, S, S1> PartialEq<WeakWeakHashMap<K, V1, S1>> for WeakWeakHashMap<K, V, S>
382where
383    K: WeakKey,
384    V: WeakElement,
385    V1: WeakElement,
386    V::Strong: PartialEq<V1::Strong>,
387    S: BuildHasher,
388    S1: BuildHasher,
389{
390    fn eq(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool {
391        self.is_submap(other) && other.domain_is_subset(self)
392    }
393}
394
395impl<K: WeakKey, V: WeakElement, S: BuildHasher> Eq for WeakWeakHashMap<K, V, S> where V::Strong: Eq {}
396
397impl<K: WeakKey, V: WeakElement, S: BuildHasher + Default> Default for WeakWeakHashMap<K, V, S> {
398    fn default() -> Self {
399        WeakWeakHashMap::with_hasher(Default::default())
400    }
401}
402
403impl<K, V, S> iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
404where
405    K: WeakKey,
406    V: WeakElement,
407    S: BuildHasher + Default,
408{
409    fn from_iter<T: IntoIterator<Item = (K::Strong, V::Strong)>>(iter: T) -> Self {
410        let iter = iter.into_iter();
411        let min_size = iter.size_hint().0;
412        let mut result = WeakWeakHashMap::with_capacity_and_hasher(min_size, Default::default());
413        result.extend(iter);
414        result
415    }
416}
417
418impl<K, V, S> Extend<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
419where
420    K: WeakKey,
421    V: WeakElement,
422    S: BuildHasher,
423{
424    fn extend<T: IntoIterator<Item = (K::Strong, V::Strong)>>(&mut self, iter: T) {
425        let iter = iter.into_iter();
426        let min_size = iter.size_hint().0;
427        self.reserve(min_size);
428        for (key, value) in iter {
429            self.insert(key, value);
430        }
431    }
432}
433
434impl<'a, K: WeakKey, V: WeakElement> Entry<'a, K, V> {
435    /// Ensures a value is in the entry by inserting a default value
436    /// if empty, and returns a mutable reference to the value in the
437    /// entry.
438    ///
439    /// *O*(1) time
440    pub fn or_insert(self, default: V::Strong) -> V::Strong {
441        self.or_insert_with(|| default)
442    }
443
444    /// Ensures a value is in the entry by inserting the result of the
445    /// `default` function if empty, and returns a mutable reference to
446    /// the value in the entry.
447    ///
448    /// *O*(1) time
449    pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong {
450        match self {
451            Entry::Occupied(occupied) => occupied.get_strong(),
452            Entry::Vacant(vacant) => vacant.insert(default()),
453        }
454    }
455
456    /// Returns a reference to this entry's key.
457    ///
458    /// *O*(1) time
459    pub fn key(&self) -> &K::Strong {
460        match *self {
461            Entry::Occupied(ref occupied) => occupied.key(),
462            Entry::Vacant(ref vacant) => vacant.key(),
463        }
464    }
465}
466
467impl<'a, K: WeakKey, V: WeakElement> OccupiedEntry<'a, K, V> {
468    /// Gets a reference to the key held by the entry.
469    ///
470    /// *O*(1) time
471    pub fn key(&self) -> &K::Strong {
472        self.0.get().0
473    }
474
475    /// Takes ownership of the key and value, removing them from the map.
476    ///
477    /// expected *O*(1) time; worst-case *O*(*p*) time
478    pub fn remove_entry(self) -> (K::Strong, V::Strong) {
479        self.0.remove()
480    }
481
482    /// Gets a reference to the value in the entry.
483    ///
484    /// *O*(1) time
485    pub fn get(&self) -> &V::Strong {
486        self.0.get().1
487    }
488
489    /// Gets a clone of the reference to the value in the entry.
490    ///
491    /// *O*(1) time
492    pub fn get_strong(&self) -> V::Strong {
493        V::clone(self.get())
494    }
495
496    /// Replaces the value in the entry with the given value.
497    ///
498    /// Returns the previous value.
499    ///
500    /// *O*(1) time
501    pub fn insert(&mut self, value: V::Strong) -> V::Strong {
502        self.0.insert(value)
503    }
504
505    /// Removes the entry, returning the value.
506    ///
507    /// expected *O*(1) time; worst-case *O*(*p*) time
508    pub fn remove(self) -> V::Strong {
509        self.remove_entry().1
510    }
511}
512
513impl<'a, K: WeakKey, V: WeakElement> VacantEntry<'a, K, V> {
514    /// Gets a reference to the key that would be used when inserting a
515    /// value through the `VacantEntry`.
516    ///
517    /// *O*(1) time
518    pub fn key(&self) -> &K::Strong {
519        self.0.key()
520    }
521
522    /// Returns an owned reference to the key.
523    ///
524    /// *O*(1) time
525    pub fn into_key(self) -> K::Strong {
526        self.0.into_key()
527    }
528
529    /// Inserts the key and value into the map, returning the same value.
530    ///
531    /// *O*(1) time
532    pub fn insert(self, value: V::Strong) -> V::Strong {
533        V::clone(self.0.insert(value).get().1)
534    }
535}
536
537impl<K: WeakElement, V: WeakElement, S> Debug for WeakWeakHashMap<K, V, S>
538where
539    K::Strong: Debug,
540    V::Strong: Debug,
541{
542    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
543        f.debug_map().entries(self.iter()).finish()
544    }
545}
546
547impl<'a, K: WeakKey, V: WeakElement> Debug for Entry<'a, K, V>
548where
549    K::Strong: Debug,
550    V::Strong: Debug,
551{
552    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
553        match *self {
554            Entry::Occupied(ref e) => e.fmt(f),
555            Entry::Vacant(ref e) => e.fmt(f),
556        }
557    }
558}
559
560impl<'a, K: WeakKey, V: WeakElement> Debug for OccupiedEntry<'a, K, V>
561where
562    K::Strong: Debug,
563    V::Strong: Debug,
564{
565    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
566        self.0.fmt(f)
567    }
568}
569
570impl<'a, K: WeakKey, V: WeakElement> Debug for VacantEntry<'a, K, V>
571where
572    K::Strong: Debug,
573    V::Strong: Debug,
574{
575    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
576        self.0.fmt(f)
577    }
578}
579
580impl<K: WeakElement, V: WeakElement, S> IntoIterator for WeakWeakHashMap<K, V, S> {
581    type Item = (K::Strong, V::Strong);
582    type IntoIter = IntoIter<K, V>;
583
584    /// Creates an owning iterator from `self`.
585    ///
586    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
587    fn into_iter(self) -> Self::IntoIter {
588        IntoIter(self.0.into_iter())
589    }
590}
591
592impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a WeakWeakHashMap<K, V, S> {
593    type Item = (K::Strong, V::Strong);
594    type IntoIter = Iter<'a, K, V>;
595
596    /// Creates a borrowing iterator from `self`.
597    ///
598    /// *O*(1) time
599    fn into_iter(self) -> Self::IntoIter {
600        Iter(self.0.iter())
601    }
602}
603
604impl<K: WeakElement, V: WeakElement, S> WeakWeakHashMap<K, V, S> {
605    /// Gets an iterator over the keys and values.
606    ///
607    /// *O*(1) time
608    pub fn iter(&self) -> Iter<'_, K, V> {
609        self.into_iter()
610    }
611
612    /// Gets an iterator over the keys.
613    ///
614    /// *O*(1) time
615    pub fn keys(&self) -> Keys<'_, K, V> {
616        Keys(self.iter())
617    }
618
619    /// Gets an iterator over the values.
620    ///
621    /// *O*(1) time
622    pub fn values(&self) -> Values<'_, K, V> {
623        Values(self.iter())
624    }
625
626    /// Gets a draining iterator, which removes all the values but retains the storage.
627    ///
628    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
629    pub fn drain(&mut self) -> Drain<'_, K, V> {
630        Drain(self.0.drain())
631    }
632}
weak_table/weak_weak_hash_map.rs

weak_table/
weak_weak_hash_map.rs
