weak_table/
weak_key_hash_map.rs

1//! A hash map where the keys are held by weak pointers and compared by key value.
2
3use super::inner;
4use super::traits::*;
5use super::*;
6use crate::common::*;
7
8pub use super::WeakKeyHashMap;
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> {
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>(
21    inner::OccupiedEntry<'a, inner::WeakK<K>, inner::Owned<V>>,
22);
23
24/// A vacant entry, which can be inserted in or viewed.
25pub struct VacantEntry<'a, K: 'a + WeakKey, V: 'a>(
26    inner::VacantEntry<'a, inner::WeakK<K>, inner::Owned<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::Owned<V>>);
32
33impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> {
34    type Item = (K::Strong, &'a V);
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#[derive(Debug)]
46/// An iterator over the keys and mutable values of the weak hash map.
47pub struct IterMut<'a, K: 'a, V: 'a>(inner::IterMut<'a, inner::WeakK<K>, inner::Owned<V>>);
48
49impl<'a, K: WeakElement, V> Iterator for IterMut<'a, K, V> {
50    type Item = (K::Strong, &'a mut V);
51
52    fn next(&mut self) -> Option<Self::Item> {
53        self.0.next()
54    }
55
56    fn size_hint(&self) -> (usize, Option<usize>) {
57        self.0.size_hint()
58    }
59}
60
61/// An iterator over the keys of the weak hash map.
62#[derive(Clone, Debug)]
63pub struct Keys<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
64
65impl<'a, K: WeakElement, V> Iterator for Keys<'a, K, V> {
66    type Item = K::Strong;
67
68    fn next(&mut self) -> Option<Self::Item> {
69        self.0.next().map(|(k, _)| k)
70    }
71
72    fn size_hint(&self) -> (usize, Option<usize>) {
73        self.0.size_hint()
74    }
75}
76
77/// An iterator over the values of the weak hash map.
78#[derive(Clone, Debug)]
79pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
80
81impl<'a, K: WeakElement, V> Iterator for Values<'a, K, V> {
82    type Item = &'a V;
83
84    fn next(&mut self) -> Option<Self::Item> {
85        self.0.next().map(|(_, v)| v)
86    }
87
88    fn size_hint(&self) -> (usize, Option<usize>) {
89        self.0.size_hint()
90    }
91}
92
93#[derive(Debug)]
94/// An iterator over the mutable values of the weak hash map.
95pub struct ValuesMut<'a, K: 'a, V: 'a>(IterMut<'a, K, V>);
96
97impl<'a, K: WeakElement, V> Iterator for ValuesMut<'a, K, V> {
98    type Item = &'a mut V;
99
100    fn next(&mut self) -> Option<Self::Item> {
101        self.0.next().map(|(_, v)| v)
102    }
103
104    fn size_hint(&self) -> (usize, Option<usize>) {
105        self.0.size_hint()
106    }
107}
108
109#[derive(Debug)]
110/// An iterator that consumes the values of a weak hash map, leaving it empty.
111///
112/// Once this iterator is dropped, all values are removed from the map,
113/// whether the iterator itself was drained or not.
114pub struct Drain<'a, K: 'a, V: 'a>(inner::Drain<'a, inner::WeakK<K>, inner::Owned<V>>);
115
116impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> {
117    type Item = (K::Strong, V);
118
119    fn next(&mut self) -> Option<Self::Item> {
120        self.0.next()
121    }
122
123    fn size_hint(&self) -> (usize, Option<usize>) {
124        self.0.size_hint()
125    }
126}
127
128/// An iterator that consumes a weak hash map, leaving it empty.
129pub struct IntoIter<K, V>(inner::IntoIter<inner::WeakK<K>, inner::Owned<V>>);
130
131impl<K: WeakElement, V> Iterator for IntoIter<K, V> {
132    type Item = (K::Strong, V);
133
134    fn next(&mut self) -> Option<Self::Item> {
135        self.0.next()
136    }
137
138    fn size_hint(&self) -> (usize, Option<usize>) {
139        self.0.size_hint()
140    }
141}
142
143into_kv_types!(K::Strong, V where {K: WeakElement});
144
145universal_hashless_members! {
146    WeakKeyHashMap ("`WeakKeyHashMap`", a "map") inner::Table::new {K,V}
147}
148
149impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> {
150    universal_key_independent_members! {"mappings"}
151
152    /// Gets the requested entry.
153    ///
154    /// expected *O*(1) time; worst-case *O*(*p*) time
155    pub fn entry(&mut self, key: K::Strong) -> Entry<'_, K, V> {
156        match self.0.entry(key) {
157            inner::Entry::Occupied(occ) => Entry::Occupied(OccupiedEntry(occ)),
158            inner::Entry::Vacant(vac) => Entry::Vacant(VacantEntry(vac)),
159        }
160    }
161    /// Returns a reference to the value corresponding to the key.
162    ///
163    /// Returns `None` if no matching key is found.
164    ///
165    /// expected *O*(1) time; worst-case *O*(*p*) time
166    pub fn get<Q>(&self, key: &Q) -> Option<&V>
167    where
168        Q: ?Sized + Hash + Eq,
169        K::Key: Borrow<Q>,
170    {
171        Some(self.0.find(key)?.1)
172    }
173
174    /// Returns true if the map contains the specified key.
175    ///
176    /// expected *O*(1) time; worst-case *O*(*p*) time
177    pub fn contains_key<Q>(&self, key: &Q) -> bool
178    where
179        Q: ?Sized + Hash + Eq,
180        K::Key: Borrow<Q>,
181    {
182        self.0.find(key).is_some()
183    }
184
185    /// Returns a strong reference to the key, if found.
186    ///
187    /// expected *O*(1) time; worst-case *O*(*p*) time
188    pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
189    where
190        Q: ?Sized + Hash + Eq,
191        K::Key: Borrow<Q>,
192    {
193        Some(self.0.find(key)?.0)
194    }
195
196    /// Returns a pair of a strong reference to the key, and a reference to the value, if present.
197    ///
198    /// expected *O*(1) time; worst-case *O*(*p*) time
199    pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, &V)>
200    where
201        Q: ?Sized + Hash + Eq,
202        K::Key: Borrow<Q>,
203    {
204        self.0.find(key)
205    }
206
207    /// Returns a mutable reference to the value corresponding to the key.
208    ///
209    /// Returns `None` if no matching key is found.
210    ///
211    /// expected *O*(1) time; worst-case *O*(*p*) time
212    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
213    where
214        Q: ?Sized + Hash + Eq,
215        K::Key: Borrow<Q>,
216    {
217        Some(self.0.find_mut(key)?.1)
218    }
219
220    /// Returns a pair of a strong reference to the key, and a mutable reference to the value,
221    /// if present.
222    ///
223    /// expected *O*(1) time; worst-case *O*(*p*) time
224    pub fn get_both_mut<Q>(&mut self, key: &Q) -> Option<(K::Strong, &mut V)>
225    where
226        Q: ?Sized + Hash + Eq,
227        K::Key: Borrow<Q>,
228    {
229        self.0.find_mut(key)
230    }
231
232    /// Looks up mutable references to the values corresponding to several keys
233    /// at a time.
234    ///
235    /// (Because of borrowing rules, Rust doesn't allow you to call `get_mut()` again
236    /// while the result of a previous `get_mut()` is still live.  This method exists
237    /// to work around that limitation.)
238    ///
239    /// Only one mutable reference can exist to any given value at a time.
240    /// Therefore, all keys must refer to different values, or this
241    /// method will panic.
242    ///
243    /// expected *O*(1 `N^2`) time; worst-case *O*(*p* `N^2`) time,
244    /// where N is the length of the array.
245    ///
246    /// # Panics
247    ///
248    /// Panics if any keys refer to the same value.
249    pub fn get_disjoint_mut<Q, const N: usize>(&mut self, ks: [&Q; N]) -> [Option<&mut V>; N]
250    where
251        Q: Hash + Eq + ?Sized,
252        K::Key: Borrow<Q>,
253    {
254        self.0.get_disjoint_mut(ks).map(|e| e.map(|(_k, v)| v))
255    }
256
257    /// Looks up mutable references to the values corresponding to several keys
258    /// at a time.  Returns those references along with their keys as stored in
259    /// the table.
260    ///
261    /// (Because of borrowing rules, Rust doesn't allow you to call `get_mut()` again
262    /// while the result of a previous `get_mut()` is still live.  This method exists
263    /// to work around that limitation.)
264    ///
265    /// Only one mutable reference can exist to any given value at a time.
266    /// Therefore, all keys must refer to different values, or this
267    /// method will panic.
268    ///
269    /// expected *O*(1 `N^2`) time; worst-case *O*(*p* `N^2`) time,
270    /// where N is the length of the array.
271    ///
272    /// # Panics
273    ///
274    /// Panics if any keys refer to the same value.
275    pub fn get_both_disjoint_mut<Q, const N: usize>(
276        &mut self,
277        ks: [&Q; N],
278    ) -> [Option<(K::Strong, &mut V)>; N]
279    where
280        Q: Hash + Eq + ?Sized,
281        K::Key: Borrow<Q>,
282    {
283        self.0.get_disjoint_mut(ks)
284    }
285
286    /// Unconditionally inserts the value, returning the old value if already present.
287    ///
288    /// Unlike `std::collections::HashMap`, this replaces the key even the entry was occupied.
289    ///
290    /// expected *O*(1) time; worst-case *O*(*p*) time
291    pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> {
292        match self.entry(key) {
293            Entry::Occupied(mut occupied) => Some(occupied.insert(value)),
294            Entry::Vacant(vacant) => {
295                vacant.insert(value);
296                None
297            }
298        }
299    }
300
301    /// Removes the entry with the given key, if it exists, and returns the value.
302    ///
303    /// expected *O*(1) time; worst-case *O*(*p*) time
304    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
305    where
306        Q: ?Sized + Hash + Eq,
307        K::Key: Borrow<Q>,
308    {
309        Some(self.0.find_entry(key)?.remove().1)
310    }
311
312    /// Removes the entry with the given key, if it exists, and returns both the
313    /// key and value.
314    ///
315    /// expected *O*(1) time; worst-case *O*(*p*) time
316    pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K::Strong, V)>
317    where
318        Q: ?Sized + Hash + Eq,
319        K::Key: Borrow<Q>,
320    {
321        Some(self.0.find_entry(key)?.remove())
322    }
323
324    /// Removes all mappings not satisfying the given predicate.
325    ///
326    /// Also removes any expired mappings.
327    ///
328    /// *O*(*n*) time
329    pub fn retain<F>(&mut self, mut f: F)
330    where
331        F: FnMut(K::Strong, &mut V) -> bool,
332    {
333        // TODO: It would be better to use a retain method on Table, but I've
334        // run into lifetime issues there. See "TODO retain" in inner/table.rs
335        self.0.table.retain(|(k, v)| {
336            if let Some(k) = k.val.view() {
337                f(k, &mut v.val)
338            } else {
339                false
340            }
341        });
342    }
343
344    /// Is this map a submap of the other under the given value comparison `cmp`?
345    ///
346    /// In particular, for every key `k` of `self`,
347    ///
348    ///  - `k` must also be a key of `other` and
349    ///  - `cmp(self[k], other[k])` must hold.
350    ///
351    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
352    /// `self.capacity()` and *q* is the length of the probe sequences
353    /// in `other`)
354    pub fn is_submap_with<F, S1, V1>(&self, other: &WeakKeyHashMap<K, V1, S1>, mut cmp: F) -> bool
355    where
356        F: FnMut(&V, &V1) -> bool,
357        S1: BuildHasher,
358    {
359        for (key, value1) in self {
360            if let Some(value2) = K::with_key(&key, |k| other.get(k)) {
361                if !cmp(value1, value2) {
362                    return false;
363                }
364            } else {
365                return false;
366            }
367        }
368
369        true
370    }
371
372    /// Is `self` a submap of `other`?
373    ///
374    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
375    /// `self.capacity()` and *q* is the length of the probe sequences
376    /// in `other`)
377    pub fn is_submap<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
378    where
379        V: PartialEq<V1>,
380        S1: BuildHasher,
381    {
382        self.is_submap_with(other, PartialEq::eq)
383    }
384
385    /// Are the keys of `self` a subset of the keys of `other`?
386    ///
387    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
388    /// `self.capacity()` and *q* is the length of the probe sequences
389    /// in `other`)
390    pub fn domain_is_subset<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
391    where
392        S1: BuildHasher,
393    {
394        self.is_submap_with(other, |_, _| true)
395    }
396}
397
398impl<K, V, V1, S, S1> PartialEq<WeakKeyHashMap<K, V1, S1>> for WeakKeyHashMap<K, V, S>
399where
400    K: WeakKey,
401    V: PartialEq<V1>,
402    S: BuildHasher,
403    S1: BuildHasher,
404{
405    fn eq(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool {
406        self.is_submap(other) && other.domain_is_subset(self)
407    }
408}
409
410impl<K: WeakKey, V: Eq, S: BuildHasher> Eq for WeakKeyHashMap<K, V, S> {}
411
412impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
413where
414    K: WeakKey,
415    K::Key: Borrow<Q>,
416    S: BuildHasher,
417    Q: ?Sized + Eq + Hash,
418{
419    type Output = V;
420
421    fn index(&self, index: &'a Q) -> &Self::Output {
422        self.get(index).expect("Index::index: key not found")
423    }
424}
425
426impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
427where
428    K: WeakKey,
429    K::Key: Borrow<Q>,
430    S: BuildHasher,
431    Q: ?Sized + Eq + Hash,
432{
433    fn index_mut(&mut self, index: &'a Q) -> &mut Self::Output {
434        self.get_mut(index)
435            .expect("IndexMut::index_mut: key not found")
436    }
437}
438
439impl<K, V, S> iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
440where
441    K: WeakKey,
442    S: BuildHasher + Default,
443{
444    fn from_iter<T: IntoIterator<Item = (K::Strong, V)>>(iter: T) -> Self {
445        let iter = iter.into_iter();
446        let min_size = iter.size_hint().0;
447        let mut result = WeakKeyHashMap::with_capacity_and_hasher(min_size, Default::default());
448        result.extend(iter);
449        result
450    }
451}
452
453#[cfg(any(test, feature = "std", feature = "ahash"))]
454impl<K: WeakKey, V, const N: usize> From<[(K::Strong, V); N]>
455    for WeakKeyHashMap<K, V, RandomState>
456{
457    /// Converts an array of key-value pairs into a map.
458    ///
459    /// If any entries in the array have equal keys,
460    /// all but one of the corresponding values will be dropped.
461    fn from(value: [(K::Strong, V); N]) -> Self {
462        Self::from_iter(value)
463    }
464}
465
466impl<K, V, S> iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
467where
468    K: WeakKey,
469    S: BuildHasher,
470{
471    fn extend<T: IntoIterator<Item = (K::Strong, V)>>(&mut self, iter: T) {
472        let iter = iter.into_iter();
473        let min_size = iter.size_hint().0;
474        self.reserve(min_size);
475        for (key, value) in iter {
476            self.insert(key, value);
477        }
478    }
479}
480
481impl<'a, K, V, S> iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
482where
483    K: 'a + WeakKey,
484    K::Strong: Clone,
485    V: 'a + Clone,
486    S: BuildHasher,
487{
488    fn extend<T: IntoIterator<Item = (&'a K::Strong, &'a V)>>(&mut self, iter: T) {
489        let iter = iter.into_iter();
490        let min_size = iter.size_hint().0;
491        self.reserve(min_size);
492        for (key, value) in iter {
493            self.insert(key.clone(), value.clone());
494        }
495    }
496}
497
498impl<'a, K: WeakKey, V> Entry<'a, K, V> {
499    /// Ensures a value is in the entry by inserting a default value
500    /// if empty, and returns a mutable reference to the value in the
501    /// entry.
502    ///
503    /// *O*(1) time
504    pub fn or_insert(self, default: V) -> &'a mut V {
505        self.or_insert_with(|| default)
506    }
507
508    /// Ensures a value is in the entry by inserting the result of the
509    /// `default` function if empty, and returns a mutable reference to
510    /// the value in the entry.
511    ///
512    /// *O*(1) time
513    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
514        match self {
515            Entry::Occupied(occupied) => occupied.into_mut(),
516            Entry::Vacant(vacant) => vacant.insert(default()),
517        }
518    }
519
520    /// Ensures that a value is in the entry by inserting the result of calling the
521    /// `default` function on this entry's key if the function is empty, and
522    /// returns a mutable reference to the value in the entry.
523    pub fn or_insert_with_key<F>(self, default: F) -> &'a mut V
524    where
525        F: FnOnce(&K::Strong) -> V,
526    {
527        match self {
528            Entry::Occupied(occupied) => occupied.into_mut(),
529            Entry::Vacant(vacant) => {
530                let value = default(vacant.key());
531                vacant.insert(value)
532            }
533        }
534    }
535
536    /// Returns a reference to this entry's key.
537    ///
538    /// *O*(1) time
539    pub fn key(&self) -> &K::Strong {
540        match *self {
541            Entry::Occupied(ref occupied) => occupied.key(),
542            Entry::Vacant(ref vacant) => vacant.key(),
543        }
544    }
545
546    /// Inserts a value into this entry, and returns an [`OccupiedEntry`].
547    ///
548    /// *O*(1) time
549    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
550        match self {
551            Entry::Occupied(mut occupied) => {
552                occupied.insert(value);
553                occupied
554            }
555            Entry::Vacant(vacant) => vacant.insert_entry(value),
556        }
557    }
558
559    /// If this entry is occupied, uses `f` to modify its value in place.
560    ///
561    /// (Otherwise, if the entry is vacant, does nothing.)
562    ///
563    /// *O*(1) time
564    pub fn and_modify<F>(mut self, f: F) -> Self
565    where
566        F: FnOnce(&mut V),
567    {
568        if let Entry::Occupied(occupied) = &mut self {
569            f(occupied.get_mut());
570        }
571        self
572    }
573}
574
575impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
576    /// Gets a reference to the key held by the entry.
577    ///
578    /// *O*(1) time
579    pub fn key(&self) -> &K::Strong {
580        self.0.get().0
581    }
582
583    /// Takes ownership of the key and value, removing them from the map.
584    ///
585    /// expected *O*(1) time; worst-case *O*(*p*) time
586    pub fn remove_entry(self) -> (K::Strong, V) {
587        self.0.remove()
588    }
589
590    /// Gets a reference to the value in the entry.
591    ///
592    /// *O*(1) time
593    pub fn get(&self) -> &V {
594        self.0.get().1
595    }
596
597    /// Gets a mutable reference to the value in the entry.
598    ///
599    /// *O*(1) time
600    pub fn get_mut(&mut self) -> &mut V {
601        self.0.get_mut().1
602    }
603
604    /// Turns the entry into a mutable reference to the value borrowed from the map.
605    ///
606    /// *O*(1) time
607    pub fn into_mut(self) -> &'a mut V {
608        self.0.into_mut()
609    }
610
611    /// Replaces the value in the entry with the given value.
612    ///
613    /// Returns the previous value.
614    ///
615    /// *O*(1) time
616    pub fn insert(&mut self, mut value: V) -> V {
617        mem::swap(&mut value, self.get_mut());
618        value
619    }
620
621    /// Removes the entry, returning the value.
622    ///
623    /// expected *O*(1) time; worst-case *O*(*p*) time
624    pub fn remove(self) -> V {
625        self.remove_entry().1
626    }
627}
628
629impl<'a, K: WeakKey, V> VacantEntry<'a, K, V> {
630    /// Gets a reference to the key that would be used when inserting a
631    /// value through the `VacantEntry`.
632    ///
633    /// *O*(1) time
634    pub fn key(&self) -> &K::Strong {
635        self.0.key()
636    }
637
638    /// Returns an owned reference to the key.
639    ///
640    /// *O*(1) time
641    pub fn into_key(self) -> K::Strong {
642        self.0.into_key()
643    }
644
645    /// Inserts the key and value into the map and return a mutable
646    /// reference to the value.
647    ///
648    /// expected *O*(1) time; worst-case *O*(*p*) time
649    pub fn insert(self, value: V) -> &'a mut V {
650        let occupied = self.0.insert(value);
651        occupied.into_mut()
652    }
653
654    /// Inserts the key and value into the map, returning an `OccupiedEntry`.
655    ///
656    /// *O*(1) time
657    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
658        OccupiedEntry(self.0.insert(value))
659    }
660}
661
662impl<K: WeakElement, V: Debug, S> Debug for WeakKeyHashMap<K, V, S>
663where
664    K::Strong: Debug,
665{
666    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
667        f.debug_map().entries(self.iter()).finish()
668    }
669}
670
671debug_for_entry! {where {
672    K: WeakKey,
673    K::Strong: Debug,
674    V: Debug}
675}
676
677impl<K: WeakElement, V, S> IntoIterator for WeakKeyHashMap<K, V, S> {
678    type Item = (K::Strong, V);
679    type IntoIter = IntoIter<K, V>;
680
681    /// Creates an owning iterator from `self`.
682    ///
683    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
684    fn into_iter(self) -> Self::IntoIter {
685        IntoIter(self.0.into_iter())
686    }
687}
688
689impl<'a, K: WeakElement, V, S> IntoIterator for &'a WeakKeyHashMap<K, V, S> {
690    type Item = (K::Strong, &'a V);
691    type IntoIter = Iter<'a, K, V>;
692
693    /// Creates a borrowing iterator from `self`.
694    ///
695    /// *O*(1) time
696    fn into_iter(self) -> Self::IntoIter {
697        Iter(self.0.iter())
698    }
699}
700
701impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap<K, V, S> {
702    type Item = (K::Strong, &'a mut V);
703    type IntoIter = IterMut<'a, K, V>;
704
705    /// Creates a borrowing iterator from `self`.
706    ///
707    /// *O*(1) time
708    fn into_iter(self) -> Self::IntoIter {
709        IterMut(self.0.iter_mut())
710    }
711}
712
713impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> {
714    /// Gets an iterator over the keys and values.
715    ///
716    /// *O*(1) time
717    pub fn iter(&self) -> Iter<'_, K, V> {
718        self.into_iter()
719    }
720
721    /// Gets an iterator over the keys.
722    ///
723    /// *O*(1) time
724    pub fn keys(&self) -> Keys<'_, K, V> {
725        Keys(self.iter())
726    }
727
728    /// Gets an iterator over the values.
729    ///
730    /// *O*(1) time
731    pub fn values(&self) -> Values<'_, K, V> {
732        Values(self.iter())
733    }
734
735    /// Gets an iterator over the keys and mutable values.
736    ///
737    /// *O*(1) time
738    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
739        self.into_iter()
740    }
741
742    /// Gets an iterator over the mutable values.
743    ///
744    /// *O*(1) time
745    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
746        ValuesMut(self.iter_mut())
747    }
748
749    /// Gets a draining iterator, which removes all the values but retains the storage.
750    ///
751    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
752    pub fn drain(&mut self) -> Drain<'_, K, V> {
753        Drain(self.0.drain())
754    }
755
756    into_kv_methods! {}
757
758    /// Gets an iterator that removes and returns elements matching a given predicate.
759    ///
760    /// Expired elements are also removed.
761    ///
762    /// If this iterator is dropped before it is completed, then no further
763    /// elements are removed.
764    /// (This is in contrast to the behavior of [`drain`](Self::drain)).
765    ///
766    /// *O*(1) time
767    pub fn extract_if<'a, F>(&'a mut self, mut f: F) -> ExtractIf<'a, K, V, F>
768    where
769        F: FnMut(K::Strong, &mut V) -> bool + 'a,
770    {
771        ExtractIf {
772            inner: self.0.extract_if(move |e| {
773                if let Some(k) = e.0.val.view() {
774                    f(k, &mut e.1.val)
775                } else {
776                    true
777                }
778            }),
779            _phantom: PhantomData,
780        }
781    }
782}
783
784/// An iterator that removes members that match a given predicate.
785#[must_use = "iterators do nothing unless consumed; \
786    consider using `retain` instead"]
787pub struct ExtractIf<'a, K: WeakElement, V, F> {
788    /// The underlying iterator.
789    inner: inner::ExtractIf<'a, inner::WeakK<K>, inner::Owned<V>>,
790    /// A marker so that F does not appear unused.
791    _phantom: PhantomData<F>,
792}
793
794impl<'a, K: WeakElement, V, F> Iterator for ExtractIf<'a, K, V, F> {
795    type Item = (K::Strong, V);
796
797    fn next(&mut self) -> Option<Self::Item> {
798        self.inner.next()
799    }
800    fn size_hint(&self) -> (usize, Option<usize>) {
801        self.inner.size_hint()
802    }
803}
804
805#[cfg(test)]
806mod test {
807    #![allow(clippy::print_stderr)]
808    // TODO 050: remove.
809    #![cfg_attr(feature = "ahash", allow(deprecated))]
810
811    use super::{Entry, WeakKeyHashMap};
812    use crate::{
813        compat::{
814            eprintln, format,
815            rc::{Rc, Weak},
816            RandomState, String, ToString as _, Vec,
817        },
818        tests::util::VecDebugAsMap,
819        util,
820    };
821
822    crate::tests::common::empty_constructor_tests! {WeakKeyHashMap<Weak<u8>, u32>}
823
824    #[test]
825    fn simple() {
826        let mut map: WeakKeyHashMap<Weak<str>, usize> = WeakKeyHashMap::new();
827        assert_eq!(map.len(), 0);
828        assert!(!map.contains_key("five"));
829
830        let five: Rc<str> = Rc::from(String::from("five"));
831        map.insert(five.clone(), 5);
832
833        assert_eq!(map.len(), 1);
834        assert!(map.contains_key("five"));
835
836        drop(five);
837
838        assert_eq!(map.len(), 1);
839        assert!(!map.contains_key("five"));
840
841        map.remove_expired();
842
843        assert_eq!(map.len(), 0);
844        assert!(!map.contains_key("five"));
845    }
846
847    #[test]
848    fn simple_arc() {
849        use crate::compat::sync::{Arc, Weak};
850        let mut map: WeakKeyHashMap<Weak<str>, usize> = WeakKeyHashMap::new();
851        assert_eq!(map.len(), 0);
852        assert!(!map.contains_key("five"));
853
854        let five: Arc<str> = Arc::from(String::from("five"));
855        map.insert(five.clone(), 5);
856
857        assert_eq!(map.len(), 1);
858        assert!(map.contains_key("five"));
859
860        drop(five);
861
862        assert_eq!(map.len(), 1);
863        assert!(!map.contains_key("five"));
864
865        map.remove_expired();
866
867        assert_eq!(map.len(), 0);
868        assert!(!map.contains_key("five"));
869    }
870
871    #[test]
872    fn access_hasher() {
873        let bh = RandomState::new();
874
875        let map: WeakKeyHashMap<Weak<str>, usize> = WeakKeyHashMap::with_hasher(bh.clone());
876
877        assert_eq!(
878            util::hash_one(&bh, "hello world"),
879            util::hash_one(map.hasher(), "hello world")
880        );
881    }
882
883    #[test]
884    fn load_factor() {
885        let mut rcs: Vec<Rc<u32>> = (0..50).map(Rc::new).collect();
886        let weakmap: WeakKeyHashMap<Weak<u32>, u32> =
887            rcs.iter().map(|n| (n.clone(), *n.as_ref())).collect();
888        rcs.retain(|n| **n % 3 != 0);
889
890        let load = weakmap.load_factor();
891        assert!(load < 1.0);
892        assert!(load > 0.0);
893    }
894
895    #[test]
896    fn is_submap() {
897        let mut rcs: Vec<Rc<u32>> = (0..50).map(Rc::new).collect();
898        let weakmap: WeakKeyHashMap<Weak<u32>, u32> = rcs
899            .iter()
900            .take(25)
901            .map(|n| (n.clone(), *n.as_ref()))
902            .collect();
903        let mut weakmap2 = weakmap.clone();
904
905        assert!(weakmap.is_submap(&weakmap2));
906        assert!(weakmap2.is_submap(&weakmap));
907
908        weakmap2.extend(rcs.iter().skip(25).map(|n| (n, n.as_ref())));
909        assert!(weakmap.is_submap(&weakmap2));
910        assert!(!weakmap2.is_submap(&weakmap));
911
912        weakmap2[&0] = 12;
913        assert!(!weakmap.is_submap(&weakmap2));
914        assert!(!weakmap2.is_submap(&weakmap));
915
916        let _ = rcs.remove(0);
917        assert!(weakmap.is_submap(&weakmap2));
918    }
919
920    #[test]
921    fn entry_methods() {
922        let rcs: Vec<Rc<u32>> = (0..5).map(Rc::new).collect();
923        let mut weakmap: WeakKeyHashMap<Weak<u32>, u32> =
924            rcs.iter().map(|n| (n.clone(), *n.as_ref())).collect();
925
926        let seven = Rc::new(7);
927        let ptr = weakmap.entry(seven.clone()).or_insert(14);
928        assert_eq!(*ptr, 14);
929        *ptr = 21;
930
931        assert_eq!(weakmap.get(&7), Some(&21));
932
933        let twelve = Rc::new(12);
934        let e = weakmap.entry(twelve.clone());
935        if let Entry::Vacant(v) = e {
936            let t2 = v.into_key();
937            assert_eq!(*t2, 12);
938        } else {
939            panic!();
940        }
941        assert!(!weakmap.contains_key(&12));
942    }
943
944    #[test]
945    fn or_insert_with() {
946        let rcs: Vec<Rc<u32>> = (0..5).map(Rc::new).collect();
947        let mut weakmap: WeakKeyHashMap<Weak<u32>, u32> =
948            rcs.iter().map(|n| (n.clone(), **n)).collect();
949        let seven = Rc::new(7);
950        let eight = Rc::new(8);
951
952        // Absent key case:
953        let ptr: &mut u32 = weakmap.entry(seven.clone()).or_insert_with(|| 14);
954        assert_eq!(*ptr, 14);
955        let ptr: &mut u32 = weakmap.entry(eight.clone()).or_insert_with_key(|k| **k * 2);
956        assert_eq!(*ptr, 16);
957
958        // Present key case:
959        let one = Rc::new(1);
960        let ptr: &mut u32 = weakmap.entry(one.clone()).or_insert_with(|| 14);
961        assert_eq!(*ptr, 1);
962        let ptr: &mut u32 = weakmap.entry(one.clone()).or_insert_with_key(|k| **k * 2);
963        assert_eq!(*ptr, 1);
964    }
965
966    #[test]
967    fn entry_insert_entry() {
968        let rcs: Vec<Rc<u32>> = (0..5).map(Rc::new).collect();
969        let mut weakmap: WeakKeyHashMap<Weak<u32>, u32> =
970            rcs.iter().map(|n| (n.clone(), **n)).collect();
971
972        let one = Rc::new(1);
973        let ten = Rc::new(10);
974
975        let e1: super::OccupiedEntry<'_, Weak<u32>, u32> =
976            weakmap.entry(one.clone()).insert_entry(1001);
977        assert_eq!(e1.key(), &one);
978        assert_eq!(e1.get(), &1001);
979
980        let e2: super::OccupiedEntry<'_, Weak<u32>, u32> =
981            weakmap.entry(ten.clone()).insert_entry(1010);
982        assert_eq!(e2.key(), &ten);
983        assert_eq!(e2.get(), &1010);
984
985        assert_eq!(weakmap.get(&1), Some(&1001));
986        assert_eq!(weakmap.get(&10), Some(&1010));
987    }
988
989    #[test]
990    fn entry_and_modify() {
991        let rcs: Vec<Rc<u32>> = (0..5).map(Rc::new).collect();
992        let mut weakmap: WeakKeyHashMap<Weak<u32>, u32> =
993            rcs.iter().map(|n| (n.clone(), **n)).collect();
994
995        let one = Rc::new(1);
996        let ten = Rc::new(10);
997
998        let e = weakmap.entry(one.clone()).and_modify(|v| *v *= 2);
999        assert!(matches!(e, Entry::Occupied(e) if e.get() == &2));
1000
1001        let e = weakmap.entry(ten.clone()).and_modify(|v| *v *= 2);
1002        assert!(matches!(e, Entry::Vacant(_)));
1003    }
1004
1005    #[test]
1006    fn vacant_insert_entry() {
1007        let mut weakmap: WeakKeyHashMap<Weak<u32>, u32> = Default::default();
1008        let five = Rc::new(5);
1009
1010        let Entry::Vacant(e) = weakmap.entry(five.clone()) else {
1011            panic!("Not vacant");
1012        };
1013        let e: super::OccupiedEntry<'_, Weak<u32>, u32> = e.insert_entry(500);
1014        assert_eq!(e.get(), &500);
1015    }
1016
1017    #[test]
1018    fn from_array() {
1019        let a = [(Rc::new(5), 25), (Rc::new(7), 49), (Rc::new(9), 81)];
1020        let v = a.to_vec();
1021
1022        let map: WeakKeyHashMap<Weak<u32>, u32> = WeakKeyHashMap::from(a);
1023        assert_eq!(map.iter().count(), 3);
1024        let mut v2: Vec<_> = map.iter().map(|(k, v)| (k, *v)).collect();
1025        v2.sort();
1026        assert_eq!(v, v2);
1027    }
1028
1029    // From https://github.com/tov/weak-table-rs/issues/1#issuecomment-461858060
1030    #[test]
1031    fn insert_and_check() {
1032        let mut rcs: Vec<Rc<u32>> = Vec::new();
1033
1034        for i in 0..50 {
1035            rcs.push(Rc::new(i));
1036        }
1037
1038        let mut weakmap: WeakKeyHashMap<Weak<u32>, f32> = WeakKeyHashMap::new();
1039
1040        for key in rcs.iter().cloned() {
1041            let f = *key as f32 + 0.1;
1042            weakmap.insert(key, f);
1043        }
1044
1045        let mut count = 0;
1046
1047        for key in &rcs {
1048            assert_eq!(weakmap.get(key), Some(&(**key as f32 + 0.1)));
1049
1050            match weakmap.entry(Rc::clone(key)) {
1051                Entry::Occupied(_) => count += 1,
1052                Entry::Vacant(_) => eprintln!("WeakKeyHashMap: missing: {}", *key),
1053            }
1054        }
1055
1056        assert_eq!(count, rcs.len());
1057    }
1058
1059    #[test]
1060    fn extract_if() {
1061        let rcs: Vec<Rc<u32>> = (0..50).map(Rc::new).collect();
1062        let mut weakmap: WeakKeyHashMap<Weak<u32>, u32> =
1063            rcs.iter().map(|k| (k.clone(), *k.as_ref())).collect();
1064        let even_numbers: crate::compat::HashSet<u32> = (0..50).filter(|n| n % 2 == 0).collect();
1065
1066        let evens: Vec<_> = weakmap
1067            .extract_if(|k, v| {
1068                debug_assert!(k.as_ref() == v);
1069                *v *= 2;
1070                even_numbers.contains(k.as_ref())
1071            })
1072            .collect();
1073
1074        assert_eq!(weakmap.iter().count(), 25);
1075        assert_eq!(evens.len(), 25);
1076    }
1077
1078    #[test]
1079    fn failed_try_reserve() {
1080        let rcs: Vec<Rc<u32>> = (0..1000).map(Rc::new).collect();
1081        let mut map: WeakKeyHashMap<Weak<u32>, u32> =
1082            rcs.iter().map(|n| (n.clone(), **n)).collect();
1083
1084        // This one will cause an integer overflow in our code.
1085        let e = map.try_reserve(usize::MAX - 500);
1086        assert!(matches!(e, Err(crate::TryReserveError::CapacityOverflow)));
1087        assert_eq!(
1088            e.expect_err("Already checked").to_string(),
1089            "Allocation failed: arithmetic overflow in capacity calculation"
1090        );
1091
1092        // This one will cause an integer overflow in hashbrown.
1093        let e = map.try_reserve(usize::MAX / 4);
1094        assert!(matches!(e, Err(crate::TryReserveError::CapacityOverflow)));
1095    }
1096
1097    #[test]
1098    fn debug_map() {
1099        let rcs: Vec<Rc<u32>> = (0..20).map(Rc::new).collect();
1100        let map: WeakKeyHashMap<Weak<u32>, u32> =
1101            rcs.iter().map(|n| (n.clone(), **n * 7)).collect();
1102        let vec: VecDebugAsMap<_, _> = map.iter().collect();
1103        assert_eq!(format!("{map:?}"), format!("{vec:?}"));
1104    }
1105
1106    #[test]
1107    fn debug_entry() {
1108        let three = Rc::new(3);
1109        let mut map = WeakKeyHashMap::<Weak<u32>, u32>::new();
1110        map.insert(three.clone(), 9);
1111        let e1 = map.entry(three.clone());
1112        assert_eq!(format!("{e1:?}"), "OccupiedEntry { key: 3, val: 9 }");
1113
1114        let four = Rc::new(4);
1115        let e2 = map.entry(four.clone());
1116        assert_eq!(format!("{e2:?}"), "VacantEntry { key: 4 }");
1117    }
1118}
weak_table/weak_key_hash_map.rs

weak_table/
weak_key_hash_map.rs
