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::*;
4use super::size_policy::*;
5use super::traits::*;
6use super::util::*;
7
8pub use super::WeakKeyHashMap;
9
10/// Represents an entry in the table which may be occupied or vacant.
11pub enum Entry<'a, K: 'a + WeakKey, V: 'a> {
12    Occupied(OccupiedEntry<'a, K, V>),
13    Vacant(VacantEntry<'a, K, V>),
14}
15
16/// An occupied entry, which can be removed or viewed.
17pub struct OccupiedEntry<'a, K: 'a + WeakKey, V: 'a>(InnerEntry<'a, K, V>);
18
19/// A vacant entry, which can be inserted in or viewed.
20pub struct VacantEntry<'a, K: 'a + WeakKey, V: 'a>(InnerEntry<'a, K, V>);
21
22struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> {
23    map:        &'a mut WeakKeyInnerMap<K, V>,
24    pos:        usize,
25    key:        K::Strong,
26    hash_code:  HashCode,
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> {
32    base: slice::Iter<'a, Bucket<K, V>>,
33    size: usize,
34}
35
36impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> {
37    type Item = (K::Strong, &'a V);
38
39    fn next(&mut self) -> Option<Self::Item> {
40        for bucket in &mut self.base {
41            if let Some((ref weak_ptr, ref value, _)) = *bucket {
42                self.size -= 1;
43                if let Some(strong_ptr) = weak_ptr.view() {
44                    return Some((strong_ptr, value));
45                }
46            }
47        }
48
49        None
50    }
51
52    fn size_hint(&self) -> (usize, Option<usize>) {
53        (0, Some(self.size))
54    }
55}
56
57#[derive(Debug)]
58/// An iterator over the keys and mutable values of the weak hash map.
59pub struct IterMut<'a, K: 'a, V: 'a> {
60    base: slice::IterMut<'a, Bucket<K, V>>,
61    size: usize,
62}
63
64impl<'a, K: WeakElement, V> Iterator for IterMut<'a, K, V> {
65    type Item = (K::Strong, &'a mut V);
66
67    fn next(&mut self) -> Option<Self::Item> {
68        for bucket in &mut self.base {
69            if let Some((ref weak_ptr, ref mut value, _)) = *bucket {
70                self.size -= 1;
71                if let Some(strong_ptr) = weak_ptr.view() {
72                    return Some((strong_ptr, value));
73                }
74            }
75        }
76
77        None
78    }
79
80    fn size_hint(&self) -> (usize, Option<usize>) {
81        (0, Some(self.size))
82    }
83}
84
85/// An iterator over the keys of the weak hash map.
86#[derive(Clone, Debug)]
87pub struct Keys<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
88
89impl<'a, K: WeakElement, V> Iterator for Keys<'a, K, V> {
90    type Item = K::Strong;
91
92    fn next(&mut self) -> Option<Self::Item> {
93        self.0.next().map(|(k, _)| k)
94    }
95
96    fn size_hint(&self) -> (usize, Option<usize>) {
97        self.0.size_hint()
98    }
99}
100
101/// An iterator over the values of the weak hash map.
102#[derive(Clone, Debug)]
103pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
104
105impl<'a, K: WeakElement, V> Iterator for Values<'a, K, V> {
106    type Item = &'a V;
107
108    fn next(&mut self) -> Option<Self::Item> {
109        self.0.next().map(|(_, v)| v)
110    }
111
112    fn size_hint(&self) -> (usize, Option<usize>) {
113        self.0.size_hint()
114    }
115}
116
117#[derive(Debug)]
118/// An iterator over the mutable values of the weak hash map.
119pub struct ValuesMut<'a, K: 'a, V: 'a>(IterMut<'a, K, V>);
120
121impl<'a, K: WeakElement, V> Iterator for ValuesMut<'a, K, V> {
122    type Item = &'a mut V;
123
124    fn next(&mut self) -> Option<Self::Item> {
125        self.0.next().map(|(_, v)| v)
126    }
127
128    fn size_hint(&self) -> (usize, Option<usize>) {
129        self.0.size_hint()
130    }
131}
132
133#[derive(Debug)]
134/// An iterator that consumes the values of a weak hash map, leaving it empty.
135pub struct Drain<'a, K: 'a, V: 'a> {
136    base: slice::IterMut<'a, Bucket<K, V>>,
137    size: usize,
138}
139
140impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> {
141    type Item = (K::Strong, V);
142
143    fn next(&mut self) -> Option<Self::Item> {
144        for bucket in &mut self.base {
145            if let Some((weak_ptr, value, _)) = bucket.take() {
146                self.size -= 1;
147                if let Some(strong_ptr) = weak_ptr.view() {
148                    return Some((strong_ptr, value));
149                }
150            }
151        }
152
153        None
154    }
155
156    fn size_hint(&self) -> (usize, Option<usize>) {
157        (0, Some(self.size))
158    }
159}
160
161impl<'a, K, V> Drop for Drain<'a, K, V> {
162    fn drop(&mut self) {
163        for option in &mut self.base {
164            *option = None;
165        }
166    }
167}
168
169/// An iterator that consumes the values of a weak hash map, leaving it empty.
170pub struct IntoIter<K, V> {
171    base: vec::IntoIter<Bucket<K, V>>,
172    size: usize,
173}
174
175impl<K: WeakElement, V> Iterator for IntoIter<K, V> {
176    type Item = (K::Strong, V);
177
178    fn next(&mut self) -> Option<Self::Item> {
179        for (weak_ptr, value, _) in (&mut self.base).flatten() {
180            self.size -= 1;
181            if let Some(strong_ptr) = weak_ptr.view() {
182                return Some((strong_ptr, value));
183            }
184        }
185
186        None
187    }
188
189    fn size_hint(&self) -> (usize, Option<usize>) {
190        (0, Some(self.size))
191    }
192}
193
194impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState>
195{
196    /// Creates an empty `WeakKeyHashMap`.
197    ///
198    /// *O*(1) time
199    pub fn new() -> Self {
200        Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
201    }
202
203    /// Creates an empty `WeakKeyHashMap` with the given capacity.
204    ///
205    /// *O*(*n*) time
206    pub fn with_capacity(capacity: usize) -> Self {
207        Self::with_capacity_and_hasher(capacity, Default::default())
208    }
209}
210
211impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
212{
213    /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
214    ///
215    /// *O*(*n*) time
216    pub fn with_hasher(hash_builder: S) -> Self {
217        Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
218    }
219
220    /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
221    ///
222    /// *O*(*n*) time
223    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
224        WeakKeyHashMap {
225            hash_builder,
226            inner: WeakKeyInnerMap {
227                buckets: new_boxed_option_slice(capacity),
228                len: 0,
229            }
230        }
231    }
232
233    /// Returns a reference to the map's `BuildHasher`.
234    ///
235    /// *O*(1) time
236    pub fn hasher(&self) -> &S {
237        &self.hash_builder
238    }
239
240    /// Returns the number of elements the map can hold without reallocating.
241    ///
242    /// *O*(1) time
243    pub fn capacity(&self) -> usize {
244        self.inner.capacity()
245    }
246
247    /// This has some preconditions.
248    fn resize(&mut self, capacity: usize) {
249        let old_buckets = mem::replace(&mut self.inner.buckets,
250                                       new_boxed_option_slice(capacity));
251
252        let iter = IntoIter {
253            base: old_buckets.into_vec().into_iter(),
254            size: self.inner.len,
255        };
256
257        self.inner.len = 0;
258
259        for (key, value) in iter {
260            self.entry_no_grow(key).or_insert(value);
261        }
262    }
263
264    /// Removes all mappings whose keys have expired.
265    ///
266    /// *O*(*n*) time
267    pub fn remove_expired(&mut self) {
268        self.retain(|_, _| true)
269    }
270
271    /// Reserves room for additional elements.
272    ///
273    /// *O*(*n*) time
274    pub fn reserve(&mut self, additional_capacity: usize) {
275        let new_capacity = additional_capacity + self.capacity();
276        self.resize(new_capacity);
277    }
278
279    /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
280    ///
281    /// *O*(*n*) time
282    pub fn shrink_to_fit(&mut self) {
283        self.remove_expired();
284        let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
285        self.resize(new_capacity);
286    }
287
288    /// Returns an over-approximation of the number of elements.
289    ///
290    /// *O*(1) time
291    pub fn len(&self) -> usize {
292        self.inner.len
293    }
294
295    /// Is the map empty?
296    ///
297    /// Note that this may return false even if all keys in the map have
298    /// expired, if they haven't been collected yet.
299    ///
300    /// *O*(1) time
301    pub fn is_empty(&self) -> bool {
302        self.len() == 0
303    }
304
305    /// The proportion of buckets that are used.
306    ///
307    /// This is an over-approximation because of expired keys.
308    ///
309    /// *O*(1) time
310    pub fn load_factor(&self) -> f32 {
311        (self.len() as f32 + 1.0) / self.capacity() as f32
312    }
313
314    fn maybe_adjust_size(&mut self) {
315        if self.load_factor() > COLLECT_LOAD_FACTOR {
316            self.remove_expired();
317
318            let load_factor = self.load_factor();
319            let capacity = self.capacity();
320            if load_factor > GROW_LOAD_FACTOR {
321                self.resize(max(1, capacity * 2));
322            } else if load_factor < SHRINK_LOAD_FACTOR && capacity > DEFAULT_INITIAL_CAPACITY {
323                self.resize(max(1, capacity / 2));
324            }
325        }
326    }
327
328    /// Gets the requested entry.
329    ///
330    /// expected *O*(1) time; worst-case *O*(*p*) time
331    pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> {
332        self.maybe_adjust_size();
333        self.entry_no_grow(key)
334    }
335
336    fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> {
337        let mut inner = {
338            let hash_code = self.hash(&key, K::hash);
339            InnerEntry {
340                pos:        self.which_bucket(hash_code),
341                map:        &mut self.inner,
342                hash_code,
343                key,
344            }
345        };
346
347        for dist in 0 .. inner.capacity() {
348            match inner.bucket_status() {
349                BucketStatus::Unoccupied =>
350                    return Entry::Vacant(VacantEntry(inner)),
351                BucketStatus::MatchesKey =>
352                    return Entry::Occupied(OccupiedEntry(inner)),
353                BucketStatus::ProbeDistance(bucket_distance) => {
354                    if bucket_distance < dist {
355                        return Entry::Vacant(VacantEntry(inner))
356                    } else {
357                        inner.pos = inner.next_bucket(inner.pos);
358                    }
359                }
360            }
361        }
362
363        panic!("WeakKeyHashTable::entry: out of space");
364    }
365
366    /// Removes all associations from the map.
367    ///
368    /// *O*(*n*) time
369    pub fn clear(&mut self) {
370        self.drain();
371    }
372
373    fn find_bucket<Q>(&self, key: &Q) -> Option<(usize, K::Strong, HashCode)>
374        where Q: ?Sized + Hash + Eq,
375              K::Key: Borrow<Q>
376    {
377        if self.capacity() == 0 { return None; }
378
379        let hash_code = self.hash(key, Q::hash);
380        let mut pos = self.which_bucket(hash_code);
381
382        for dist in 0 .. self.capacity() {
383            if let Some((ref weak_key, _, bucket_hash_code)) = self.inner.buckets[pos] {
384                if bucket_hash_code == hash_code {
385                    if let Some(bucket_key) = weak_key.view() {
386                        if K::equals(&bucket_key, key) {
387                            return Some((pos, bucket_key, bucket_hash_code));
388                        }
389                    }
390                }
391
392                let bucket_dist =
393                    self.probe_distance(pos, self.which_bucket(bucket_hash_code));
394                if bucket_dist < dist {
395                    return None;
396                }
397            } else {
398                return None;
399            }
400
401            pos = self.next_bucket(pos);
402        }
403
404        None
405    }
406
407    /// Returns a reference to the value corresponding to the key.
408    ///
409    /// expected *O*(1) time; worst-case *O*(*p*) time
410    pub fn get<Q>(&self, key: &Q) -> Option<&V>
411        where Q: ?Sized + Hash + Eq,
412              K::Key: Borrow<Q>
413    {
414        self.find_bucket(key).and_then(move |tup|
415            self.inner.buckets[tup.0].as_ref().map(|bucket| &bucket.1))
416    }
417
418    /// Returns true if the map contains the specified key.
419    ///
420    /// expected *O*(1) time; worst-case *O*(*p*) time
421    pub fn contains_key<Q>(&self, key: &Q) -> bool
422        where Q: ?Sized + Hash + Eq,
423              K::Key: Borrow<Q>
424    {
425        self.find_bucket(key).is_some()
426    }
427
428    /// Returns a strong reference to the key, if found.
429    ///
430    /// expected *O*(1) time; worst-case *O*(*p*) time
431    pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
432        where Q: ?Sized + Hash + Eq,
433              K::Key: Borrow<Q>
434    {
435        self.find_bucket(key).map(|tup| tup.1)
436    }
437
438    /// Returns a pair of a strong reference to the key, and a reference to the value, if present.
439    ///
440    /// expected *O*(1) time; worst-case *O*(*p*) time
441    pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, &V)>
442        where Q: ?Sized + Hash + Eq,
443              K::Key: Borrow<Q>
444    {
445        self.find_bucket(key).and_then(move |tup|
446            self.inner.buckets[tup.0].as_ref().map(|bucket| (tup.1, &bucket.1)))
447    }
448
449    /// Returns a mutable reference to the value corresponding to the key.
450    ///
451    /// expected *O*(1) time; worst-case *O*(*p*) time
452    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
453        where Q: ?Sized + Hash + Eq,
454              K::Key: Borrow<Q>
455    {
456        self.find_bucket(key).and_then(move |tup|
457            self.inner.buckets[tup.0].as_mut().map(|bucket| &mut bucket.1))
458    }
459
460    /// Returns a pair of a strong reference to the key, and a mutable reference to the value,
461    /// if present.
462    ///
463    /// expected *O*(1) time; worst-case *O*(*p*) time
464    pub fn get_both_mut<Q>(&mut self, key: &Q) -> Option<(K::Strong, &mut V)>
465        where Q: ?Sized + Hash + Eq,
466              K::Key: Borrow<Q>
467    {
468        self.find_bucket(key).and_then(move |tup|
469            self.inner.buckets[tup.0].as_mut().map(|bucket| (tup.1, &mut bucket.1)))
470    }
471
472    /// Unconditionally inserts the value, returning the old value if already present.
473    ///
474    /// Unlike `std::collections::HashMap`, this replaced the key even if occupied.
475    ///
476    /// expected *O*(1) time; worst-case *O*(*p*) time
477    pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> {
478        match self.entry(key) {
479            Entry::Occupied(mut occupied) => {
480                Some(occupied.insert(value))
481            },
482            Entry::Vacant(vacant) => {
483                vacant.insert(value);
484                None
485            }
486        }
487    }
488
489    /// Removes the entry with the given key, if it exists, and returns the value.
490    ///
491    /// expected *O*(1) time; worst-case *O*(*p*) time
492    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
493        where Q: ?Sized + Hash + Eq,
494              K::Key: Borrow<Q>
495    {
496        self.find_bucket(key).map(|(pos, strong_key, hash_code)| {
497            OccupiedEntry(InnerEntry {
498                map:        &mut self.inner,
499                pos,
500                key:        strong_key,
501                hash_code,
502            }).remove()
503        })
504    }
505
506    /// Removes all mappings not satisfying the given predicate.
507    ///
508    /// Also removes any expired mappings.
509    ///
510    /// *O*(*n*) time
511    pub fn retain<F>(&mut self, mut f: F)
512        where F: FnMut(K::Strong, &mut V) -> bool
513    {
514        for i in 0 .. self.capacity() {
515            let remove = match self.inner.buckets[i] {
516                None => false,
517                Some(ref mut bucket) =>
518                    match bucket.0.view() {
519                        None => true,
520                        Some(key) => !f(key, &mut bucket.1),
521                    }
522            };
523
524            if remove {
525                self.inner.remove_index(i);
526            }
527        }
528    }
529
530    /// Is this map a submap of the other under the given value comparison `cmp`?
531    ///
532    /// In particular, for every key `k` of `self`,
533    ///
534    ///  - `k` must also be a key of `other` and
535    ///  - `cmp(self[k], other[k])` must hold.
536    ///
537    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
538    /// `self.capacity()` and *q* is the length of the probe sequences
539    /// in `other`)
540    pub fn is_submap_with<F, S1, V1>(&self, other: &WeakKeyHashMap<K, V1, S1>,
541                                     mut cmp: F) -> bool
542        where F: FnMut(&V, &V1) -> bool,
543              S1: BuildHasher
544    {
545        for (key, value1) in self {
546            if let Some(value2) = K::with_key(&key, |k| other.get(k)) {
547                if !cmp(value1, value2) {
548                    return false;
549                }
550            } else {
551                return false;
552            }
553        }
554
555        true
556    }
557
558    /// Is `self` a submap of `other`?
559    ///
560    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
561    /// `self.capacity()` and *q* is the length of the probe sequences
562    /// in `other`)
563    pub fn is_submap<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
564        where V: PartialEq<V1>,
565              S1: BuildHasher
566    {
567        self.is_submap_with(other, PartialEq::eq)
568    }
569
570    /// Are the keys of `self` a subset of the keys of `other`?
571    ///
572    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
573    /// `self.capacity()` and *q* is the length of the probe sequences
574    /// in `other`)
575    pub fn domain_is_subset<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
576        where S1: BuildHasher
577    {
578        self.is_submap_with(other, |_, _| true)
579    }
580
581    fn hash<Q, H>(&self, key: Q, hash: H) -> HashCode
582        where H: FnOnce(Q, &mut S::Hasher)
583    {
584        let hasher = &mut self.hash_builder.build_hasher();
585        hash(key, hasher);
586        HashCode(hasher.finish())
587    }
588}
589
590impl<K, V, V1, S, S1> PartialEq<WeakKeyHashMap<K, V1, S1>> for WeakKeyHashMap<K, V, S>
591    where K: WeakKey,
592          V: PartialEq<V1>,
593          S: BuildHasher,
594          S1: BuildHasher
595{
596    fn eq(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool {
597        self.is_submap(other) && other.domain_is_subset(self)
598    }
599}
600
601impl<K: WeakKey, V: Eq, S: BuildHasher> Eq for WeakKeyHashMap<K, V, S> { }
602
603impl<K: WeakKey, V, S: BuildHasher + Default> Default for WeakKeyHashMap<K, V, S> {
604    fn default() -> Self {
605        WeakKeyHashMap::with_hasher(Default::default())
606    }
607}
608
609impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
610    where K: WeakKey,
611          K::Key: Borrow<Q>,
612          S: BuildHasher,
613          Q: ?Sized + Eq + Hash
614{
615    type Output = V;
616
617    fn index(&self, index: &'a Q) -> &Self::Output {
618        self.get(index).expect("Index::index: key not found")
619    }
620}
621
622impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
623    where K: WeakKey,
624          K::Key: Borrow<Q>,
625          S: BuildHasher,
626          Q: ?Sized + Eq + Hash
627{
628    fn index_mut(&mut self, index: &'a Q) -> &mut Self::Output {
629        self.get_mut(index).expect("IndexMut::index_mut: key not found")
630    }
631}
632
633impl<K, V, S> iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
634    where K: WeakKey,
635          S: BuildHasher + Default
636{
637    fn from_iter<T: IntoIterator<Item=(K::Strong, V)>>(iter: T) -> Self {
638        let mut result = WeakKeyHashMap::with_hasher(Default::default());
639        result.extend(iter);
640        result
641    }
642}
643
644impl<K, V, S> iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
645    where K: WeakKey,
646          S: BuildHasher
647{
648    fn extend<T: IntoIterator<Item=(K::Strong, V)>>(&mut self, iter: T) {
649        for (key, value) in iter {
650            self.insert(key, value);
651        }
652    }
653}
654
655impl<'a, K, V, S> iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
656    where K: 'a + WeakKey,
657          K::Strong: Clone,
658          V: 'a + Clone,
659          S: BuildHasher
660{
661    fn extend<T: IntoIterator<Item=(&'a K::Strong, &'a V)>>(&mut self, iter: T) {
662        for (key, value) in iter {
663            self.insert(key.clone(), value.clone());
664        }
665    }
666}
667
668enum BucketStatus {
669    Unoccupied,
670    MatchesKey,
671    ProbeDistance(usize),
672}
673
674impl<'a, K: WeakKey, V> InnerEntry<'a, K, V> {
675    // Gets the status of the current bucket.
676    fn bucket_status(&self) -> BucketStatus {
677        match &self.map.buckets[self.pos] {
678            Some(bucket) => {
679                if bucket.2 == self.hash_code {
680                    if let Some(key) = bucket.0.view() {
681                        if K::with_key(&self.key, |k| K::equals(&key, k)) {
682                            return BucketStatus::MatchesKey;
683                        }
684                    }
685                }
686
687                let dist = self.probe_distance(self.pos,
688                                               self.which_bucket(bucket.2));
689                BucketStatus::ProbeDistance(dist)
690            },
691            None => BucketStatus::Unoccupied,
692        }
693    }
694}
695
696impl<'a, K: WeakKey, V> Entry<'a, K, V> {
697    /// Ensures a value is in the entry by inserting a default value
698    /// if empty, and returns a mutable reference to the value in the
699    /// entry.
700    ///
701    /// *O*(1) time
702    pub fn or_insert(self, default: V) -> &'a mut V {
703        self.or_insert_with(|| default)
704    }
705
706    /// Ensures a value is in the entry by inserting the result of the
707    /// default function if empty, and returns a mutable reference to
708    /// the value in the entry.
709    ///
710    /// *O*(1) time
711    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
712        match self {
713            Entry::Occupied(occupied) => occupied.into_mut(),
714            Entry::Vacant(vacant) => vacant.insert(default()),
715        }
716    }
717
718    /// Returns a reference to this entry's key.
719    ///
720    /// *O*(1) time
721    pub fn key(&self) -> &K::Strong {
722        match *self {
723            Entry::Occupied(ref occupied) => occupied.key(),
724            Entry::Vacant(ref vacant) => vacant.key(),
725        }
726    }
727}
728
729impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
730    /// Gets a reference to the key held by the entry.
731    ///
732    /// *O*(1) time
733    pub fn key(&self) -> &K::Strong {
734        &self.0.key
735    }
736
737    /// Takes ownership of the key and value from the map.
738    ///
739    /// expected *O*(1) time; worst-case *O*(*p*) time
740    pub fn remove_entry(self) -> (K::Strong, V) {
741        let (_, value, _) = self.0.map.buckets[self.0.pos].take().unwrap();
742        self.0.map.remove_index(self.0.pos);
743        (self.0.key, value)
744    }
745
746    /// Gets a reference to the value in the entry.
747    ///
748    /// *O*(1) time
749    pub fn get(&self) -> &V {
750        &self.0.map.buckets[self.0.pos].as_ref().unwrap().1
751    }
752
753    /// Gets a mutable reference to the value in the entry.
754    ///
755    /// *O*(1) time
756    pub fn get_mut(&mut self) -> &mut V {
757        &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
758    }
759
760    /// Turns the entry into a mutable reference to the value borrowed from the map.
761    ///
762    /// *O*(1) time
763    pub fn into_mut(self) -> &'a mut V {
764        &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
765    }
766
767    /// Replaces the value in the entry with the given value.
768    ///
769    /// *O*(1) time
770    pub fn insert(&mut self, mut value: V) -> V {
771        self.0.map.buckets[self.0.pos].as_mut().unwrap().0 = K::new(&self.0.key);
772        mem::swap(self.get_mut(), &mut value);
773        value
774    }
775
776    /// Removes the entry, returning the value.
777    ///
778    /// expected *O*(1) time; worst-case *O*(*p*) time
779    pub fn remove(self) -> V {
780        self.remove_entry().1
781    }
782}
783
784impl<'a, K: WeakKey, V> VacantEntry<'a, K, V> {
785    /// Gets a reference to the key that would be used when inserting a
786    /// value through the `VacantEntry`.
787    ///
788    /// *O*(1) time
789    pub fn key(&self) -> &K::Strong {
790        &self.0.key
791    }
792
793    /// Returns ownership of the key.
794    ///
795    /// *O*(1) time
796    pub fn into_key(self) -> K::Strong {
797        self.0.key
798    }
799
800    /// Inserts the key and value into the map and return a mutable
801    /// reference to the value.
802    ///
803    /// expected *O*(1) time; worst-case *O*(*p*) time
804    pub fn insert(self, value: V) -> &'a mut V {
805        let old_bucket = mem::replace(
806            &mut self.0.map.buckets[self.0.pos],
807            Some((K::new(&self.0.key), value, self.0.hash_code)));
808
809        if let Some(full_bucket) = old_bucket {
810            let next_bucket = self.next_bucket(self.0.pos);
811            self.0.map.steal(next_bucket, full_bucket);
812        }
813
814        self.0.map.len += 1;
815
816        &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
817    }
818}
819
820impl<K: WeakKey, V> WeakKeyInnerMap<K, V> {
821    // Steals buckets starting at `pos`, replacing them with `bucket`.
822    fn steal(&mut self, mut pos: usize, mut bucket: FullBucket<K, V>) {
823        let mut my_dist = self.probe_distance(pos, self.which_bucket(bucket.2));
824
825        while let Some(hash_code) = self.buckets[pos].as_ref().and_then(
826            |bucket| if bucket.0.is_expired() {None} else {Some(bucket.2)}) {
827
828            let victim_dist = self.probe_distance(pos, self.which_bucket(hash_code));
829
830            if my_dist > victim_dist {
831                mem::swap(self.buckets[pos].as_mut().unwrap(), &mut bucket);
832                my_dist = victim_dist;
833            }
834
835            pos = self.next_bucket(pos);
836            my_dist += 1;
837        }
838
839        self.buckets[pos] = Some(bucket);
840    }
841
842    /// Removes the element at `dst`, shifting if necessary to preserve invariants.
843    fn remove_index(&mut self, mut dst: usize) {
844        let mut src = self.next_bucket(dst);
845
846        // We are going to remove the buckets in the range [dst, src)
847
848        loop {
849            let hash_code_option = self.buckets[src].as_ref().map(|tup| tup.2);
850
851            if let Some(hash_code) = hash_code_option {
852                let goal_pos = self.which_bucket(hash_code);
853                let dist = self.probe_distance(src, goal_pos);
854                if dist == 0 { break; }
855
856                if !self.buckets[src].as_ref().unwrap().0.is_expired() {
857                    if in_interval(dst, goal_pos, src) {
858                        self.erase_range(dst, goal_pos);
859                        self.buckets[goal_pos] = self.buckets[src].take();
860                        dst = self.next_bucket(goal_pos);
861                    } else {
862                        self.buckets[dst] = self.buckets[src].take();
863                        dst = self.next_bucket(dst);
864                    }
865                }
866            } else {
867                break;
868            }
869
870            src = self.next_bucket(src);
871        }
872
873        self.erase_range(dst, src);
874    }
875
876    /// Erases the (presumably expired, but not empty) elements in [start, limit).
877    fn erase_range(&mut self, mut start: usize, limit: usize)
878    {
879        while start != limit {
880            self.buckets[start] = None;
881            self.len -= 1;
882            start = self.next_bucket(start);
883        }
884    }
885}
886
887// Is value in [start, limit) modulo capacity?
888fn in_interval(start: usize, value: usize, limit: usize) -> bool
889{
890    if start <= limit {
891        start <= value && value < limit
892    } else {
893        start <= value || value < limit
894    }
895}
896
897// Helper trait for computing with indices modulo capacity.
898trait ModuloCapacity {
899    fn capacity(&self) -> usize;
900
901    fn probe_distance(&self, actual: usize, ideal: usize) -> usize {
902        if actual >= ideal {
903            actual - ideal
904        } else {
905            actual + self.capacity() - ideal
906        }
907    }
908
909    fn next_bucket(&self, pos: usize) -> usize {
910        assert_ne!( self.capacity(), 0 );
911        (pos + 1) % self.capacity()
912    }
913
914    fn which_bucket(&self, hash_code: HashCode) -> usize {
915        assert_ne!( self.capacity(), 0 );
916        (hash_code.0 as usize) % self.capacity()
917    }
918}
919
920impl<K, V> ModuloCapacity for WeakKeyInnerMap<K, V> {
921    fn capacity(&self) -> usize {
922        self.buckets.len()
923    }
924}
925
926impl<K, V, S> ModuloCapacity for WeakKeyHashMap<K, V, S> {
927    fn capacity(&self) -> usize {
928        self.inner.capacity()
929    }
930}
931
932impl<'a, K: WeakKey, V> ModuloCapacity for InnerEntry<'a, K, V> {
933    fn capacity(&self) -> usize {
934        self.map.capacity()
935    }
936}
937
938impl<'a, K: WeakKey, V> ModuloCapacity for OccupiedEntry<'a, K, V> {
939    fn capacity(&self) -> usize {
940        self.0.capacity()
941    }
942}
943
944impl<'a, K: WeakKey, V> ModuloCapacity for VacantEntry<'a, K, V> {
945    fn capacity(&self) -> usize {
946        self.0.capacity()
947    }
948}
949
950impl<K, V> Debug for WeakKeyInnerMap<K, V>
951    where K: WeakElement,
952          K::Strong: Debug,
953          V: Debug
954{
955    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
956        write!(f, "{{ ")?;
957        for (i, bucket) in self.buckets.iter().enumerate() {
958            if let Some((ref k, ref v, _)) = *bucket {
959                write!(f, "[{}] {:?} => {:?}, ", i, k.view(), *v)?;
960            }
961        }
962        write!(f, "}}")
963    }
964}
965
966impl<K: WeakElement, V: Debug, S> Debug for WeakKeyHashMap<K, V, S>
967    where K::Strong: Debug
968{
969    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
970        self.inner.fmt(f)
971    }
972}
973
974impl<'a, K: WeakKey, V: Debug> Debug for Entry<'a, K, V>
975    where K::Strong: Debug
976{
977    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
978        match *self {
979            Entry::Occupied(ref e)  => e.fmt(f),
980            Entry::Vacant(ref e)    => e.fmt(f),
981        }
982    }
983}
984
985impl<'a, K: WeakKey, V: Debug> Debug for OccupiedEntry<'a, K, V>
986    where K::Strong: Debug
987{
988    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
989        self.0.fmt(f)
990    }
991}
992
993impl<'a, K: WeakKey, V: Debug> Debug for VacantEntry<'a, K, V>
994    where K::Strong: Debug
995{
996    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
997        self.0.fmt(f)
998    }
999}
1000
1001impl<'a, K: WeakKey, V: Debug> Debug for InnerEntry<'a, K, V>
1002    where K::Strong: Debug
1003{
1004    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1005        write!(f, "InnerEntry {{ pos = {}, buckets = {:?} }}", self.pos, self.map)
1006    }
1007}
1008
1009impl<K: WeakElement, V, S> IntoIterator for WeakKeyHashMap<K, V, S> {
1010    type Item = (K::Strong, V);
1011    type IntoIter = IntoIter<K, V>;
1012
1013    /// Creates an owning iterator from `self`.
1014    ///
1015    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
1016    fn into_iter(self) -> Self::IntoIter {
1017        IntoIter {
1018            size: self.inner.len,
1019            base: self.inner.buckets.into_vec().into_iter(),
1020        }
1021    }
1022}
1023
1024impl<'a, K: WeakElement, V, S> IntoIterator for &'a WeakKeyHashMap<K, V, S> {
1025    type Item = (K::Strong, &'a V);
1026    type IntoIter = Iter<'a, K, V>;
1027
1028    /// Creates a borrowing iterator from `self`.
1029    ///
1030    /// *O*(1) time
1031    fn into_iter(self) -> Self::IntoIter {
1032        Iter {
1033            base: self.inner.buckets.iter(),
1034            size: self.inner.len,
1035        }
1036    }
1037}
1038
1039impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap<K, V, S> {
1040    type Item = (K::Strong, &'a mut V);
1041    type IntoIter = IterMut<'a, K, V>;
1042
1043    /// Creates a borrowing iterator from `self`.
1044    ///
1045    /// *O*(1) time
1046    fn into_iter(self) -> Self::IntoIter {
1047        IterMut {
1048            base: self.inner.buckets.iter_mut(),
1049            size: self.inner.len,
1050        }
1051    }
1052}
1053
1054impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> {
1055    /// Gets an iterator over the keys and values.
1056    ///
1057    /// *O*(1) time
1058    pub fn iter(&self) -> Iter<K, V> {
1059        self.into_iter()
1060    }
1061
1062    /// Gets an iterator over the keys.
1063    ///
1064    /// *O*(1) time
1065    pub fn keys(&self) -> Keys<K, V> {
1066        Keys(self.iter())
1067    }
1068
1069    /// Gets an iterator over the values.
1070    ///
1071    /// *O*(1) time
1072    pub fn values(&self) -> Values<K, V> {
1073        Values(self.iter())
1074    }
1075
1076    /// Gets an iterator over the keys and mutable values.
1077    ///
1078    /// *O*(1) time
1079    pub fn iter_mut(&mut self) -> IterMut<K, V> {
1080        self.into_iter()
1081    }
1082
1083    /// Gets an iterator over the mutable values.
1084    ///
1085    /// *O*(1) time
1086    pub fn values_mut(&mut self) -> ValuesMut<K, V> {
1087        ValuesMut(self.iter_mut())
1088    }
1089
1090    /// Gets a draining iterator, which removes all the values but retains the storage.
1091    ///
1092    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
1093    pub fn drain(&mut self) -> Drain<K, V> {
1094        let old_len = self.inner.len;
1095        self.inner.len = 0;
1096        Drain {
1097            base: self.inner.buckets.iter_mut(),
1098            size: old_len,
1099        }
1100    }
1101}
1102
1103#[cfg(test)]
1104mod test {
1105    use crate::compat::{
1106        eprintln,
1107        rc::{Rc, Weak},
1108        String,
1109        Vec,
1110    };
1111    use super::{Entry, WeakKeyHashMap};
1112
1113    #[test]
1114    fn simple() {
1115        let mut map: WeakKeyHashMap<Weak<str>, usize> = WeakKeyHashMap::new();
1116        assert_eq!( map.len(), 0 );
1117        assert!( !map.contains_key("five") );
1118
1119        let five: Rc<str> = Rc::from(String::from("five"));
1120        map.insert(five.clone(), 5);
1121
1122        assert_eq!( map.len(), 1 );
1123        assert!( map.contains_key("five") );
1124
1125        drop(five);
1126
1127        assert_eq!( map.len(), 1 );
1128        assert!( !map.contains_key("five") );
1129
1130        map.remove_expired();
1131
1132        assert_eq!( map.len(), 0 );
1133        assert!( !map.contains_key("five") );
1134    }
1135
1136    // From https://github.com/tov/weak-table-rs/issues/1#issuecomment-461858060
1137    #[test]
1138    fn insert_and_check() {
1139        let mut rcs: Vec<Rc<u32>> = Vec::new();
1140
1141        for i in 0 .. 50 {
1142            rcs.push(Rc::new(i));
1143        }
1144
1145        let mut weakmap: WeakKeyHashMap<Weak<u32>, f32> = WeakKeyHashMap::new();
1146
1147        for key in rcs.iter().cloned() {
1148            let f = *key as f32 + 0.1;
1149            weakmap.insert(key, f);
1150        }
1151
1152        let mut count = 0;
1153
1154        for key in &rcs {
1155            assert_eq!(weakmap.get(key), Some(&(**key as f32 + 0.1)));
1156
1157            match weakmap.entry(Rc::clone(key)) {
1158                Entry::Occupied(_) => count += 1,
1159                Entry::Vacant(_) => eprintln!("WeakKeyHashMap: missing: {}", *key),
1160            }
1161        }
1162
1163        assert_eq!( count, rcs.len() );
1164    }
1165}
weak_table/weak_key_hash_map.rs

weak_table/
weak_key_hash_map.rs
