weak_table/
weak_value_hash_map.rs

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

weak_table/
weak_value_hash_map.rs
