diff options
Diffstat (limited to 'src/weak_key_hash_map.rs')
| -rw-r--r-- | src/weak_key_hash_map.rs | 188 |
1 files changed, 145 insertions, 43 deletions
diff --git a/src/weak_key_hash_map.rs b/src/weak_key_hash_map.rs index 91bee2a..7dcb8c4 100644 --- a/src/weak_key_hash_map.rs +++ b/src/weak_key_hash_map.rs @@ -1,12 +1,5 @@ //! A hash map where the keys are held by weak pointers and compared by key value. -use std::borrow::Borrow; -use std::cmp::max; -use std::collections::hash_map::RandomState; -use std::hash::{BuildHasher, Hash, Hasher}; -use std::fmt::{self, Debug, Formatter}; -use std::mem; - use super::*; use super::size_policy::*; use super::traits::*; @@ -36,7 +29,7 @@ struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> { /// An iterator over the keys and values of the weak hash map. #[derive(Clone, Debug)] pub struct Iter<'a, K: 'a, V: 'a> { - base: ::std::slice::Iter<'a, Bucket<K, V>>, + base: slice::Iter<'a, Bucket<K, V>>, size: usize, } @@ -44,7 +37,7 @@ impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> { type Item = (K::Strong, &'a V); fn next(&mut self) -> Option<Self::Item> { - while let Some(bucket) = self.base.next() { + for bucket in &mut self.base { if let Some((ref weak_ptr, ref value, _)) = *bucket { self.size -= 1; if let Some(strong_ptr) = weak_ptr.view() { @@ -64,7 +57,7 @@ impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> { #[derive(Debug)] /// An iterator over the keys and mutable values of the weak hash map. pub struct IterMut<'a, K: 'a, V: 'a> { - base: ::std::slice::IterMut<'a, Bucket<K, V>>, + base: slice::IterMut<'a, Bucket<K, V>>, size: usize, } @@ -72,7 +65,7 @@ impl<'a, K: WeakElement, V> Iterator for IterMut<'a, K, V> { type Item = (K::Strong, &'a mut V); fn next(&mut self) -> Option<Self::Item> { - while let Some(bucket) = self.base.next() { + for bucket in &mut self.base { if let Some((ref weak_ptr, ref mut value, _)) = *bucket { self.size -= 1; if let Some(strong_ptr) = weak_ptr.view() { @@ -140,7 +133,7 @@ impl<'a, K: WeakElement, V> Iterator for ValuesMut<'a, K, V> { #[derive(Debug)] /// An iterator that consumes the values of a weak hash map, leaving it empty. pub struct Drain<'a, K: 'a, V: 'a> { - base: ::std::slice::IterMut<'a, Bucket<K, V>>, + base: slice::IterMut<'a, Bucket<K, V>>, size: usize, } @@ -148,7 +141,7 @@ impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> { type Item = (K::Strong, V); fn next(&mut self) -> Option<Self::Item> { - while let Some(bucket) = self.base.next() { + for bucket in &mut self.base { if let Some((weak_ptr, value, _)) = bucket.take() { self.size -= 1; if let Some(strong_ptr) = weak_ptr.view() { @@ -167,7 +160,7 @@ impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> { impl<'a, K, V> Drop for Drain<'a, K, V> { fn drop(&mut self) { - while let Some(option) = self.base.next() { + for option in &mut self.base { *option = None; } } @@ -175,7 +168,7 @@ impl<'a, K, V> Drop for Drain<'a, K, V> { /// An iterator that consumes the values of a weak hash map, leaving it empty. pub struct IntoIter<K, V> { - base: ::std::vec::IntoIter<Bucket<K, V>>, + base: vec::IntoIter<Bucket<K, V>>, size: usize, } @@ -183,12 +176,10 @@ impl<K: WeakElement, V> Iterator for IntoIter<K, V> { type Item = (K::Strong, V); fn next(&mut self) -> Option<Self::Item> { - while let Some(bucket) = self.base.next() { - if let Some((weak_ptr, value, _)) = bucket { - self.size -= 1; - if let Some(strong_ptr) = weak_ptr.view() { - return Some((strong_ptr, value)); - } + for (weak_ptr, value, _) in (&mut self.base).flatten() { + self.size -= 1; + if let Some(strong_ptr) = weak_ptr.view() { + return Some((strong_ptr, value)); } } @@ -203,11 +194,15 @@ impl<K: WeakElement, V> Iterator for IntoIter<K, V> { impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState> { /// Creates an empty `WeakKeyHashMap`. + /// + /// *O*(1) time pub fn new() -> Self { Self::with_capacity(DEFAULT_INITIAL_CAPACITY) } /// Creates an empty `WeakKeyHashMap` with the given capacity. + /// + /// *O*(*n*) time pub fn with_capacity(capacity: usize) -> Self { Self::with_capacity_and_hasher(capacity, Default::default()) } @@ -216,11 +211,15 @@ impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState> impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> { /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher. + /// + /// *O*(*n*) time pub fn with_hasher(hash_builder: S) -> Self { Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder) } /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher. + /// + /// *O*(*n*) time pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { WeakKeyHashMap { hash_builder, @@ -232,11 +231,15 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Returns a reference to the map's `BuildHasher`. + /// + /// *O*(1) time pub fn hasher(&self) -> &S { &self.hash_builder } /// Returns the number of elements the map can hold without reallocating. + /// + /// *O*(1) time pub fn capacity(&self) -> usize { self.inner.capacity() } @@ -259,17 +262,23 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Removes all mappings whose keys have expired. + /// + /// *O*(*n*) time pub fn remove_expired(&mut self) { self.retain(|_, _| true) } /// Reserves room for additional elements. + /// + /// *O*(*n*) time pub fn reserve(&mut self, additional_capacity: usize) { let new_capacity = additional_capacity + self.capacity(); self.resize(new_capacity); } /// Shrinks the capacity to the minimum allowed to hold the current number of elements. + /// + /// *O*(*n*) time pub fn shrink_to_fit(&mut self) { self.remove_expired(); let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize; @@ -277,6 +286,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Returns an over-approximation of the number of elements. + /// + /// *O*(1) time pub fn len(&self) -> usize { self.inner.len } @@ -285,6 +296,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> /// /// Note that this may return false even if all keys in the map have /// expired, if they haven't been collected yet. + /// + /// *O*(1) time pub fn is_empty(&self) -> bool { self.len() == 0 } @@ -292,6 +305,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> /// The proportion of buckets that are used. /// /// This is an over-approximation because of expired keys. + /// + /// *O*(1) time pub fn load_factor(&self) -> f32 { (self.len() as f32 + 1.0) / self.capacity() as f32 } @@ -311,6 +326,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Gets the requested entry. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> { self.maybe_adjust_size(); self.entry_no_grow(key) @@ -318,7 +335,7 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> { let mut inner = { - let hash_code = K::with_key(&key, |k| self.hash(k)); + let hash_code = self.hash(&key, K::hash); InnerEntry { pos: self.which_bucket(hash_code), map: &mut self.inner, @@ -347,6 +364,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Removes all associations from the map. + /// + /// *O*(*n*) time pub fn clear(&mut self) { self.drain(); } @@ -357,14 +376,14 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> { if self.capacity() == 0 { return None; } - let hash_code = self.hash(key); + let hash_code = self.hash(key, Q::hash); let mut pos = self.which_bucket(hash_code); for dist in 0 .. self.capacity() { if let Some((ref weak_key, _, bucket_hash_code)) = self.inner.buckets[pos] { if bucket_hash_code == hash_code { if let Some(bucket_key) = weak_key.view() { - if K::with_key(&bucket_key, |k| k.borrow() == key) { + if K::equals(&bucket_key, key) { return Some((pos, bucket_key, bucket_hash_code)); } } @@ -386,6 +405,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Returns a reference to the value corresponding to the key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get<Q>(&self, key: &Q) -> Option<&V> where Q: ?Sized + Hash + Eq, K::Key: Borrow<Q> @@ -395,6 +416,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Returns true if the map contains the specified key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn contains_key<Q>(&self, key: &Q) -> bool where Q: ?Sized + Hash + Eq, K::Key: Borrow<Q> @@ -403,6 +426,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Returns a strong reference to the key, if found. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong> where Q: ?Sized + Hash + Eq, K::Key: Borrow<Q> @@ -411,6 +436,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Returns a pair of a strong reference to the key, and a reference to the value, if present. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, &V)> where Q: ?Sized + Hash + Eq, K::Key: Borrow<Q> @@ -420,6 +447,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Returns a mutable reference to the value corresponding to the key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V> where Q: ?Sized + Hash + Eq, K::Key: Borrow<Q> @@ -430,6 +459,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> /// Returns a pair of a strong reference to the key, and a mutable reference to the value, /// if present. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get_both_mut<Q>(&mut self, key: &Q) -> Option<(K::Strong, &mut V)> where Q: ?Sized + Hash + Eq, K::Key: Borrow<Q> @@ -441,6 +472,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> /// Unconditionally inserts the value, returning the old value if already present. /// /// Unlike `std::collections::HashMap`, this replaced the key even if occupied. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> { match self.entry(key) { Entry::Occupied(mut occupied) => { @@ -454,6 +487,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Removes the entry with the given key, if it exists, and returns the value. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn remove<Q>(&mut self, key: &Q) -> Option<V> where Q: ?Sized + Hash + Eq, K::Key: Borrow<Q> @@ -471,6 +506,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> /// Removes all mappings not satisfying the given predicate. /// /// Also removes any expired mappings. + /// + /// *O*(*n*) time pub fn retain<F>(&mut self, mut f: F) where F: FnMut(K::Strong, &mut V) -> bool { @@ -490,18 +527,24 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } } - /// Is this map a submap of the other, using the given value comparison. + /// Is this map a submap of the other under the given value comparison `cmp`? /// - /// In particular, all the keys of `self` must be in `other` and the values must compare - /// `true` with `value_equal`. + /// In particular, for every key `k` of `self`, + /// + /// - `k` must also be a key of `other` and + /// - `cmp(self[k], other[k])` must hold. + /// + /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is + /// `self.capacity()` and *q* is the length of the probe sequences + /// in `other`) pub fn is_submap_with<F, S1, V1>(&self, other: &WeakKeyHashMap<K, V1, S1>, - mut value_equal: F) -> bool + mut cmp: F) -> bool where F: FnMut(&V, &V1) -> bool, S1: BuildHasher { for (key, value1) in self { if let Some(value2) = K::with_key(&key, |k| other.get(k)) { - if !value_equal(value1, value2) { + if !cmp(value1, value2) { return false; } } else { @@ -513,6 +556,10 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Is `self` a submap of `other`? + /// + /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is + /// `self.capacity()` and *q* is the length of the probe sequences + /// in `other`) pub fn is_submap<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool where V: PartialEq<V1>, S1: BuildHasher @@ -521,18 +568,21 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S> } /// Are the keys of `self` a subset of the keys of `other`? + /// + /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is + /// `self.capacity()` and *q* is the length of the probe sequences + /// in `other`) pub fn domain_is_subset<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool where S1: BuildHasher { self.is_submap_with(other, |_, _| true) } - fn hash<Q>(&self, key: &Q) -> HashCode - where Q: ?Sized + Hash, - K::Key: Borrow<Q> + fn hash<Q, H>(&self, key: Q, hash: H) -> HashCode + where H: FnOnce(Q, &mut S::Hasher) { - let mut hasher = self.hash_builder.build_hasher(); - key.hash(&mut hasher); + let hasher = &mut self.hash_builder.build_hasher(); + hash(key, hasher); HashCode(hasher.finish()) } } @@ -556,7 +606,7 @@ impl<K: WeakKey, V, S: BuildHasher + Default> Default for WeakKeyHashMap<K, V, S } } -impl<'a, K, V, S, Q> ::std::ops::Index<&'a Q> for WeakKeyHashMap<K, V, S> +impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap<K, V, S> where K: WeakKey, K::Key: Borrow<Q>, S: BuildHasher, @@ -569,7 +619,7 @@ impl<'a, K, V, S, Q> ::std::ops::Index<&'a Q> for WeakKeyHashMap<K, V, S> } } -impl<'a, K, V, S, Q> ::std::ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S> +impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S> where K: WeakKey, K::Key: Borrow<Q>, S: BuildHasher, @@ -580,7 +630,7 @@ impl<'a, K, V, S, Q> ::std::ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S> } } -impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S> +impl<K, V, S> iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S> where K: WeakKey, S: BuildHasher + Default { @@ -591,7 +641,7 @@ impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, } } -impl<K, V, S> ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S> +impl<K, V, S> iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S> where K: WeakKey, S: BuildHasher { @@ -602,7 +652,7 @@ impl<K, V, S> ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S> } } -impl<'a, K, V, S> ::std::iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S> +impl<'a, K, V, S> iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S> where K: 'a + WeakKey, K::Strong: Clone, V: 'a + Clone, @@ -628,7 +678,7 @@ impl<'a, K: WeakKey, V> InnerEntry<'a, K, V> { Some(bucket) => { if bucket.2 == self.hash_code { if let Some(key) = bucket.0.view() { - if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) { + if K::with_key(&self.key, |k| K::equals(&key, k)) { return BucketStatus::MatchesKey; } } @@ -647,6 +697,8 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> { /// Ensures a value is in the entry by inserting a default value /// if empty, and returns a mutable reference to the value in the /// entry. + /// + /// *O*(1) time pub fn or_insert(self, default: V) -> &'a mut V { self.or_insert_with(|| default) } @@ -654,6 +706,8 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> { /// Ensures a value is in the entry by inserting the result of the /// default function if empty, and returns a mutable reference to /// the value in the entry. + /// + /// *O*(1) time pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V { match self { Entry::Occupied(occupied) => occupied.into_mut(), @@ -662,6 +716,8 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> { } /// Returns a reference to this entry's key. + /// + /// *O*(1) time pub fn key(&self) -> &K::Strong { match *self { Entry::Occupied(ref occupied) => occupied.key(), @@ -672,11 +728,15 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> { impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> { /// Gets a reference to the key held by the entry. + /// + /// *O*(1) time pub fn key(&self) -> &K::Strong { &self.0.key } /// Takes ownership of the key and value from the map. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn remove_entry(self) -> (K::Strong, V) { let (_, value, _) = self.0.map.buckets[self.0.pos].take().unwrap(); self.0.map.remove_index(self.0.pos); @@ -684,21 +744,29 @@ impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> { } /// Gets a reference to the value in the entry. + /// + /// *O*(1) time pub fn get(&self) -> &V { &self.0.map.buckets[self.0.pos].as_ref().unwrap().1 } /// Gets a mutable reference to the value in the entry. + /// + /// *O*(1) time pub fn get_mut(&mut self) -> &mut V { &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1 } /// Turns the entry into a mutable reference to the value borrowed from the map. + /// + /// *O*(1) time pub fn into_mut(self) -> &'a mut V { &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1 } /// Replaces the value in the entry with the given value. + /// + /// *O*(1) time pub fn insert(&mut self, mut value: V) -> V { self.0.map.buckets[self.0.pos].as_mut().unwrap().0 = K::new(&self.0.key); mem::swap(self.get_mut(), &mut value); @@ -706,6 +774,8 @@ impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> { } /// Removes the entry, returning the value. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn remove(self) -> V { self.remove_entry().1 } @@ -714,17 +784,23 @@ impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> { impl<'a, K: WeakKey, V> VacantEntry<'a, K, V> { /// Gets a reference to the key that would be used when inserting a /// value through the `VacantEntry`. + /// + /// *O*(1) time pub fn key(&self) -> &K::Strong { &self.0.key } /// Returns ownership of the key. + /// + /// *O*(1) time pub fn into_key(self) -> K::Strong { self.0.key } /// Inserts the key and value into the map and return a mutable /// reference to the value. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn insert(self, value: V) -> &'a mut V { let old_bucket = mem::replace( &mut self.0.map.buckets[self.0.pos], @@ -934,6 +1010,9 @@ impl<K: WeakElement, V, S> IntoIterator for WeakKeyHashMap<K, V, S> { type Item = (K::Strong, V); type IntoIter = IntoIter<K, V>; + /// Creates an owning iterator from `self`. + /// + /// *O*(1) time (and *O*(*n*) time to dispose of the result) fn into_iter(self) -> Self::IntoIter { IntoIter { size: self.inner.len, @@ -946,6 +1025,9 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a WeakKeyHashMap<K, V, S> { type Item = (K::Strong, &'a V); type IntoIter = Iter<'a, K, V>; + /// Creates a borrowing iterator from `self`. + /// + /// *O*(1) time fn into_iter(self) -> Self::IntoIter { Iter { base: self.inner.buckets.iter(), @@ -958,6 +1040,9 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap<K, V, S> type Item = (K::Strong, &'a mut V); type IntoIter = IterMut<'a, K, V>; + /// Creates a borrowing iterator from `self`. + /// + /// *O*(1) time fn into_iter(self) -> Self::IntoIter { IterMut { base: self.inner.buckets.iter_mut(), @@ -968,31 +1053,43 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap<K, V, S> impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> { /// Gets an iterator over the keys and values. + /// + /// *O*(1) time pub fn iter(&self) -> Iter<K, V> { self.into_iter() } /// Gets an iterator over the keys. + /// + /// *O*(1) time pub fn keys(&self) -> Keys<K, V> { Keys(self.iter()) } /// Gets an iterator over the values. + /// + /// *O*(1) time pub fn values(&self) -> Values<K, V> { Values(self.iter()) } /// Gets an iterator over the keys and mutable values. + /// + /// *O*(1) time pub fn iter_mut(&mut self) -> IterMut<K, V> { self.into_iter() } /// Gets an iterator over the mutable values. + /// + /// *O*(1) time pub fn values_mut(&mut self) -> ValuesMut<K, V> { ValuesMut(self.iter_mut()) } /// Gets a draining iterator, which removes all the values but retains the storage. + /// + /// *O*(1) time (and *O*(*n*) time to dispose of the result) pub fn drain(&mut self) -> Drain<K, V> { let old_len = self.inner.len; self.inner.len = 0; @@ -1004,8 +1101,13 @@ impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> { } #[cfg(test)] -mod tests { - use std::rc::{Rc, Weak}; +mod test { + use crate::compat::{ + eprintln, + rc::{Rc, Weak}, + String, + Vec, + }; use super::{Entry, WeakKeyHashMap}; #[test] @@ -1014,7 +1116,7 @@ mod tests { assert_eq!( map.len(), 0 ); assert!( !map.contains_key("five") ); - let five: Rc<str> = Rc::from("five".to_string()); + let five: Rc<str> = Rc::from(String::from("five")); map.insert(five.clone(), 5); assert_eq!( map.len(), 1 ); |