weak_table/
weak_value_hash_map.rs

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

weak_table/
weak_value_hash_map.rs
