diff options
Diffstat (limited to 'vendor/hashbrown/src/map.rs')
| -rw-r--r-- | vendor/hashbrown/src/map.rs | 396 |
1 files changed, 250 insertions, 146 deletions
diff --git a/vendor/hashbrown/src/map.rs b/vendor/hashbrown/src/map.rs index a5d3ccb97..5049aa2b5 100644 --- a/vendor/hashbrown/src/map.rs +++ b/vendor/hashbrown/src/map.rs @@ -1,5 +1,5 @@ use crate::raw::{Allocator, Bucket, Global, RawDrain, RawIntoIter, RawIter, RawTable}; -use crate::TryReserveError; +use crate::{Equivalent, TryReserveError}; use core::borrow::Borrow; use core::fmt::{self, Debug}; use core::hash::{BuildHasher, Hash}; @@ -10,7 +10,7 @@ use core::ops::Index; /// Default hasher for `HashMap`. #[cfg(feature = "ahash")] -pub type DefaultHashBuilder = ahash::RandomState; +pub type DefaultHashBuilder = core::hash::BuildHasherDefault<ahash::AHasher>; /// Dummy default hasher for `HashMap`. #[cfg(not(feature = "ahash"))] @@ -209,13 +209,12 @@ impl<K: Clone, V: Clone, S: Clone, A: Allocator + Clone> Clone for HashMap<K, V, /// Ensures that a single closure type across uses of this which, in turn prevents multiple /// instances of any functions like RawTable::reserve from being generated #[cfg_attr(feature = "inline-more", inline)] -pub(crate) fn make_hasher<K, Q, V, S>(hash_builder: &S) -> impl Fn(&(Q, V)) -> u64 + '_ +pub(crate) fn make_hasher<Q, V, S>(hash_builder: &S) -> impl Fn(&(Q, V)) -> u64 + '_ where - K: Borrow<Q>, Q: Hash, S: BuildHasher, { - move |val| make_hash::<K, Q, S>(hash_builder, &val.0) + move |val| make_hash::<Q, S>(hash_builder, &val.0) } /// Ensures that a single closure type across uses of this which, in turn prevents multiple @@ -223,10 +222,9 @@ where #[cfg_attr(feature = "inline-more", inline)] fn equivalent_key<Q, K, V>(k: &Q) -> impl Fn(&(K, V)) -> bool + '_ where - K: Borrow<Q>, - Q: ?Sized + Eq, + Q: ?Sized + Equivalent<K>, { - move |x| k.eq(x.0.borrow()) + move |x| k.equivalent(&x.0) } /// Ensures that a single closure type across uses of this which, in turn prevents multiple @@ -234,17 +232,15 @@ where #[cfg_attr(feature = "inline-more", inline)] fn equivalent<Q, K>(k: &Q) -> impl Fn(&K) -> bool + '_ where - K: Borrow<Q>, - Q: ?Sized + Eq, + Q: ?Sized + Equivalent<K>, { - move |x| k.eq(x.borrow()) + move |x| k.equivalent(x) } #[cfg(not(feature = "nightly"))] #[cfg_attr(feature = "inline-more", inline)] -pub(crate) fn make_hash<K, Q, S>(hash_builder: &S, val: &Q) -> u64 +pub(crate) fn make_hash<Q, S>(hash_builder: &S, val: &Q) -> u64 where - K: Borrow<Q>, Q: Hash + ?Sized, S: BuildHasher, { @@ -256,9 +252,8 @@ where #[cfg(feature = "nightly")] #[cfg_attr(feature = "inline-more", inline)] -pub(crate) fn make_hash<K, Q, S>(hash_builder: &S, val: &Q) -> u64 +pub(crate) fn make_hash<Q, S>(hash_builder: &S, val: &Q) -> u64 where - K: Borrow<Q>, Q: Hash + ?Sized, S: BuildHasher, { @@ -295,6 +290,18 @@ impl<K, V> HashMap<K, V, DefaultHashBuilder> { /// The hash map is initially created with a capacity of 0, so it will not allocate until it /// is first inserted into. /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashMap`], for example with + /// [`with_hasher`](HashMap::with_hasher) method. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// /// # Examples /// /// ``` @@ -313,6 +320,18 @@ impl<K, V> HashMap<K, V, DefaultHashBuilder> { /// The hash map will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash map will not allocate. /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashMap`], for example with + /// [`with_capacity_and_hasher`](HashMap::with_capacity_and_hasher) method. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// /// # Examples /// /// ``` @@ -333,6 +352,48 @@ impl<K, V, A: Allocator + Clone> HashMap<K, V, DefaultHashBuilder, A> { /// /// The hash map is initially created with a capacity of 0, so it will not allocate until it /// is first inserted into. + /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashMap`], for example with + /// [`with_hasher_in`](HashMap::with_hasher_in) method. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// + /// # Examples + /// + /// ``` + /// # #[cfg(feature = "bumpalo")] + /// # fn test() { + /// use hashbrown::{HashMap, BumpWrapper}; + /// use bumpalo::Bump; + /// + /// let bump = Bump::new(); + /// let mut map = HashMap::new_in(BumpWrapper(&bump)); + /// + /// // The created HashMap holds none elements + /// assert_eq!(map.len(), 0); + /// + /// // The created HashMap also doesn't allocate memory + /// assert_eq!(map.capacity(), 0); + /// + /// // Now we insert element inside created HashMap + /// map.insert("One", 1); + /// // We can see that the HashMap holds 1 element + /// assert_eq!(map.len(), 1); + /// // And it also allocates some capacity + /// assert!(map.capacity() > 1); + /// # } + /// # fn main() { + /// # #[cfg(feature = "bumpalo")] + /// # test() + /// # } + /// ``` #[cfg_attr(feature = "inline-more", inline)] pub fn new_in(alloc: A) -> Self { Self::with_hasher_in(DefaultHashBuilder::default(), alloc) @@ -342,6 +403,53 @@ impl<K, V, A: Allocator + Clone> HashMap<K, V, DefaultHashBuilder, A> { /// /// The hash map will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash map will not allocate. + /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashMap`], for example with + /// [`with_capacity_and_hasher_in`](HashMap::with_capacity_and_hasher_in) method. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// + /// # Examples + /// + /// ``` + /// # #[cfg(feature = "bumpalo")] + /// # fn test() { + /// use hashbrown::{HashMap, BumpWrapper}; + /// use bumpalo::Bump; + /// + /// let bump = Bump::new(); + /// let mut map = HashMap::with_capacity_in(5, BumpWrapper(&bump)); + /// + /// // The created HashMap holds none elements + /// assert_eq!(map.len(), 0); + /// // But it can hold at least 5 elements without reallocating + /// let empty_map_capacity = map.capacity(); + /// assert!(empty_map_capacity >= 5); + /// + /// // Now we insert some 5 elements inside created HashMap + /// map.insert("One", 1); + /// map.insert("Two", 2); + /// map.insert("Three", 3); + /// map.insert("Four", 4); + /// map.insert("Five", 5); + /// + /// // We can see that the HashMap holds 5 elements + /// assert_eq!(map.len(), 5); + /// // But its capacity isn't changed + /// assert_eq!(map.capacity(), empty_map_capacity) + /// # } + /// # fn main() { + /// # #[cfg(feature = "bumpalo")] + /// # test() + /// # } + /// ``` #[cfg_attr(feature = "inline-more", inline)] pub fn with_capacity_in(capacity: usize, alloc: A) -> Self { Self::with_capacity_and_hasher_in(capacity, DefaultHashBuilder::default(), alloc) @@ -355,14 +463,21 @@ impl<K, V, S> HashMap<K, V, S> { /// The hash map is initially created with a capacity of 0, so it will not /// allocate until it is first inserted into. /// - /// Warning: `hash_builder` is normally randomly generated, and - /// is designed to allow HashMaps to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashMap`]. /// /// The `hash_builder` passed should implement the [`BuildHasher`] trait for /// the HashMap to be useful, see its documentation for details. /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html + /// /// # Examples /// /// ``` @@ -376,8 +491,6 @@ impl<K, V, S> HashMap<K, V, S> { /// /// map.insert(1, 2); /// ``` - /// - /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html #[cfg_attr(feature = "inline-more", inline)] pub const fn with_hasher(hash_builder: S) -> Self { Self { @@ -392,14 +505,21 @@ impl<K, V, S> HashMap<K, V, S> { /// The hash map will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash map will not allocate. /// - /// Warning: `hash_builder` is normally randomly generated, and - /// is designed to allow HashMaps to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashMap`]. /// /// The `hash_builder` passed should implement the [`BuildHasher`] trait for /// the HashMap to be useful, see its documentation for details. /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html + /// /// # Examples /// /// ``` @@ -413,8 +533,6 @@ impl<K, V, S> HashMap<K, V, S> { /// /// map.insert(1, 2); /// ``` - /// - /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html #[cfg_attr(feature = "inline-more", inline)] pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { Self { @@ -434,12 +552,19 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// Creates an empty `HashMap` which will use the given hash builder to hash /// keys. It will be allocated with the given allocator. /// - /// The created map has the default initial capacity. + /// The hash map is initially created with a capacity of 0, so it will not allocate until it + /// is first inserted into. + /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashMap`]. /// - /// Warning: `hash_builder` is normally randomly generated, and - /// is designed to allow HashMaps to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html /// /// # Examples /// @@ -452,7 +577,7 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// map.insert(1, 2); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn with_hasher_in(hash_builder: S, alloc: A) -> Self { + pub const fn with_hasher_in(hash_builder: S, alloc: A) -> Self { Self { hash_builder, table: RawTable::new_in(alloc), @@ -465,10 +590,16 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// The hash map will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash map will not allocate. /// - /// Warning: `hash_builder` is normally randomly generated, and - /// is designed to allow HashMaps to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashMap`]. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html /// /// # Examples /// @@ -810,14 +941,11 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// /// let mut map: HashMap<i32, i32> = (0..8).map(|x|(x, x*10)).collect(); /// assert_eq!(map.len(), 8); - /// let capacity_before_retain = map.capacity(); /// /// map.retain(|&k, _| k % 2 == 0); /// /// // We can see, that the number of elements inside map is changed. /// assert_eq!(map.len(), 4); - /// // But map capacity is equal to old one. - /// assert_eq!(map.capacity(), capacity_before_retain); /// /// let mut vec: Vec<(i32, i32)> = map.iter().map(|(&k, &v)| (k, v)).collect(); /// vec.sort_unstable(); @@ -862,7 +990,7 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// use hashbrown::HashMap; /// /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect(); - /// let capacity_before_drain_filter = map.capacity(); + /// /// let drained: HashMap<i32, i32> = map.drain_filter(|k, _v| k % 2 == 0).collect(); /// /// let mut evens = drained.keys().cloned().collect::<Vec<_>>(); @@ -872,8 +1000,6 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// /// assert_eq!(evens, vec![0, 2, 4, 6]); /// assert_eq!(odds, vec![1, 3, 5, 7]); - /// // Map capacity is equal to old one. - /// assert_eq!(map.capacity(), capacity_before_drain_filter); /// /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect(); /// @@ -992,9 +1118,12 @@ where /// /// # Panics /// - /// Panics if the new allocation size overflows [`usize`]. + /// Panics if the new capacity exceeds [`isize::MAX`] bytes and [`abort`] the program + /// in case of allocation error. Use [`try_reserve`](HashMap::try_reserve) instead + /// if you want to handle memory allocation failure. /// - /// [`usize`]: https://doc.rust-lang.org/std/primitive.usize.html + /// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html + /// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html /// /// # Examples /// @@ -1012,7 +1141,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn reserve(&mut self, additional: usize) { self.table - .reserve(additional, make_hasher::<K, _, V, S>(&self.hash_builder)); + .reserve(additional, make_hasher::<_, V, S>(&self.hash_builder)); } /// Tries to reserve capacity for at least `additional` more elements to be inserted @@ -1062,7 +1191,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { self.table - .try_reserve(additional, make_hasher::<K, _, V, S>(&self.hash_builder)) + .try_reserve(additional, make_hasher::<_, V, S>(&self.hash_builder)) } /// Shrinks the capacity of the map as much as possible. It will drop @@ -1084,7 +1213,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn shrink_to_fit(&mut self) { self.table - .shrink_to(0, make_hasher::<K, _, V, S>(&self.hash_builder)); + .shrink_to(0, make_hasher::<_, V, S>(&self.hash_builder)); } /// Shrinks the capacity of the map with a lower limit. It will drop @@ -1113,7 +1242,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn shrink_to(&mut self, min_capacity: usize) { self.table - .shrink_to(min_capacity, make_hasher::<K, _, V, S>(&self.hash_builder)); + .shrink_to(min_capacity, make_hasher::<_, V, S>(&self.hash_builder)); } /// Gets the given key's corresponding entry in the map for in-place manipulation. @@ -1174,10 +1303,9 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn entry_ref<'a, 'b, Q: ?Sized>(&'a mut self, key: &'b Q) -> EntryRef<'a, 'b, K, Q, V, S, A> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { - let hash = make_hash::<K, Q, S>(&self.hash_builder, key); + let hash = make_hash::<Q, S>(&self.hash_builder, key); if let Some(elem) = self.table.find(hash, equivalent_key(key)) { EntryRef::Occupied(OccupiedEntryRef { hash, @@ -1216,8 +1344,7 @@ where #[inline] pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { // Avoid `Option::map` because it bloats LLVM IR. match self.get_inner(k) { @@ -1248,8 +1375,7 @@ where #[inline] pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { // Avoid `Option::map` because it bloats LLVM IR. match self.get_inner(k) { @@ -1261,13 +1387,12 @@ where #[inline] fn get_inner<Q: ?Sized>(&self, k: &Q) -> Option<&(K, V)> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { if self.table.is_empty() { None } else { - let hash = make_hash::<K, Q, S>(&self.hash_builder, k); + let hash = make_hash::<Q, S>(&self.hash_builder, k); self.table.get(hash, equivalent_key(k)) } } @@ -1298,8 +1423,7 @@ where #[inline] pub fn get_key_value_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<(&K, &mut V)> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { // Avoid `Option::map` because it bloats LLVM IR. match self.get_inner_mut(k) { @@ -1330,8 +1454,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { self.get_inner(k).is_some() } @@ -1362,8 +1485,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { // Avoid `Option::map` because it bloats LLVM IR. match self.get_inner_mut(k) { @@ -1375,13 +1497,12 @@ where #[inline] fn get_inner_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut (K, V)> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { if self.table.is_empty() { None } else { - let hash = make_hash::<K, Q, S>(&self.hash_builder, k); + let hash = make_hash::<Q, S>(&self.hash_builder, k); self.table.get_mut(hash, equivalent_key(k)) } } @@ -1431,8 +1552,7 @@ where /// ``` pub fn get_many_mut<Q: ?Sized, const N: usize>(&mut self, ks: [&Q; N]) -> Option<[&'_ mut V; N]> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { self.get_many_mut_inner(ks).map(|res| res.map(|(_, v)| v)) } @@ -1487,8 +1607,7 @@ where ks: [&Q; N], ) -> Option<[&'_ mut V; N]> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { self.get_many_unchecked_mut_inner(ks) .map(|res| res.map(|(_, v)| v)) @@ -1543,8 +1662,7 @@ where ks: [&Q; N], ) -> Option<[(&'_ K, &'_ mut V); N]> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { self.get_many_mut_inner(ks) .map(|res| res.map(|(k, v)| (&*k, v))) @@ -1599,8 +1717,7 @@ where ks: [&Q; N], ) -> Option<[(&'_ K, &'_ mut V); N]> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { self.get_many_unchecked_mut_inner(ks) .map(|res| res.map(|(k, v)| (&*k, v))) @@ -1611,12 +1728,11 @@ where ks: [&Q; N], ) -> Option<[&'_ mut (K, V); N]> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { let hashes = self.build_hashes_inner(ks); self.table - .get_many_mut(hashes, |i, (k, _)| ks[i].eq(k.borrow())) + .get_many_mut(hashes, |i, (k, _)| ks[i].equivalent(k)) } unsafe fn get_many_unchecked_mut_inner<Q: ?Sized, const N: usize>( @@ -1624,22 +1740,20 @@ where ks: [&Q; N], ) -> Option<[&'_ mut (K, V); N]> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { let hashes = self.build_hashes_inner(ks); self.table - .get_many_unchecked_mut(hashes, |i, (k, _)| ks[i].eq(k.borrow())) + .get_many_unchecked_mut(hashes, |i, (k, _)| ks[i].equivalent(k)) } fn build_hashes_inner<Q: ?Sized, const N: usize>(&self, ks: [&Q; N]) -> [u64; N] where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { let mut hashes = [0_u64; N]; for i in 0..N { - hashes[i] = make_hash::<K, Q, S>(&self.hash_builder, ks[i]); + hashes[i] = make_hash::<Q, S>(&self.hash_builder, ks[i]); } hashes } @@ -1677,7 +1791,7 @@ where Some(mem::replace(item, v)) } else { self.table - .insert(hash, (k, v), make_hasher::<K, _, V, S>(&self.hash_builder)); + .insert(hash, (k, v), make_hasher::<_, V, S>(&self.hash_builder)); None } } @@ -1736,7 +1850,7 @@ where let hash = make_insert_hash::<K, S>(&self.hash_builder, &k); let bucket = self .table - .insert(hash, (k, v), make_hasher::<K, _, V, S>(&self.hash_builder)); + .insert(hash, (k, v), make_hasher::<_, V, S>(&self.hash_builder)); let (k_ref, v_ref) = unsafe { bucket.as_mut() }; (k_ref, v_ref) } @@ -1801,19 +1915,17 @@ where /// assert!(map.is_empty() && map.capacity() == 0); /// /// map.insert(1, "a"); - /// let capacity_before_remove = map.capacity(); /// /// assert_eq!(map.remove(&1), Some("a")); /// assert_eq!(map.remove(&1), None); /// - /// // Now map holds none elements but capacity is equal to the old one - /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove); + /// // Now map holds none elements + /// assert!(map.is_empty()); /// ``` #[cfg_attr(feature = "inline-more", inline)] pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { // Avoid `Option::map` because it bloats LLVM IR. match self.remove_entry(k) { @@ -1842,21 +1954,19 @@ where /// assert!(map.is_empty() && map.capacity() == 0); /// /// map.insert(1, "a"); - /// let capacity_before_remove = map.capacity(); /// /// assert_eq!(map.remove_entry(&1), Some((1, "a"))); /// assert_eq!(map.remove(&1), None); /// - /// // Now map hold none elements but capacity is equal to the old one - /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove); + /// // Now map hold none elements + /// assert!(map.is_empty()); /// ``` #[cfg_attr(feature = "inline-more", inline)] pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)> where - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { - let hash = make_hash::<K, Q, S>(&self.hash_builder, k); + let hash = make_hash::<Q, S>(&self.hash_builder, k); self.table.remove_entry(hash, equivalent_key(k)) } } @@ -2018,14 +2128,14 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// /// # Note /// - /// Calling the function safe, but using raw hash table API's may require + /// Calling this function is safe, but using the raw hash table API may require /// unsafe functions or blocks. /// /// `RawTable` API gives the lowest level of control under the map that can be useful /// for extending the HashMap's API, but may lead to *[undefined behavior]*. /// /// [`HashMap`]: struct.HashMap.html - /// [`RawTable`]: raw/struct.RawTable.html + /// [`RawTable`]: crate::raw::RawTable /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html /// /// # Examples @@ -2140,8 +2250,8 @@ where impl<K, Q: ?Sized, V, S, A> Index<&Q> for HashMap<K, V, S, A> where - K: Eq + Hash + Borrow<Q>, - Q: Eq + Hash, + K: Eq + Hash, + Q: Hash + Equivalent<K>, S: BuildHasher, A: Allocator + Clone, { @@ -3103,10 +3213,9 @@ impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> { pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S, A> where S: BuildHasher, - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { - let hash = make_hash::<K, Q, S>(&self.map.hash_builder, k); + let hash = make_hash::<Q, S>(&self.map.hash_builder, k); self.from_key_hashed_nocheck(hash, k) } @@ -3136,8 +3245,7 @@ impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> { #[allow(clippy::wrong_self_convention)] pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S, A> where - K: Borrow<Q>, - Q: Eq, + Q: Equivalent<K>, { self.from_hash(hash, equivalent(k)) } @@ -3211,10 +3319,9 @@ impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilder<'a, K, V, S, A> { pub fn from_key<Q: ?Sized>(self, k: &Q) -> Option<(&'a K, &'a V)> where S: BuildHasher, - K: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<K>, { - let hash = make_hash::<K, Q, S>(&self.map.hash_builder, k); + let hash = make_hash::<Q, S>(&self.map.hash_builder, k); self.from_key_hashed_nocheck(hash, k) } @@ -3242,8 +3349,7 @@ impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilder<'a, K, V, S, A> { #[allow(clippy::wrong_self_convention)] pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)> where - K: Borrow<Q>, - Q: Eq, + Q: Equivalent<K>, { self.from_hash(hash, equivalent(k)) } @@ -3950,7 +4056,7 @@ impl<'a, K, V, S, A: Allocator + Clone> RawVacantEntryMut<'a, K, V, S, A> { let &mut (ref mut k, ref mut v) = self.table.insert_entry( hash, (key, value), - make_hasher::<K, _, V, S>(self.hash_builder), + make_hasher::<_, V, S>(self.hash_builder), ); (k, v) } @@ -4018,7 +4124,7 @@ impl<'a, K, V, S, A: Allocator + Clone> RawVacantEntryMut<'a, K, V, S, A> { let elem = self.table.insert( hash, (key, value), - make_hasher::<K, _, V, S>(self.hash_builder), + make_hasher::<_, V, S>(self.hash_builder), ); RawOccupiedEntryMut { elem, @@ -5183,7 +5289,6 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// assert!(map.is_empty() && map.capacity() == 0); /// /// map.entry("poneyland").or_insert(12); - /// let capacity_before_remove = map.capacity(); /// /// if let Entry::Occupied(o) = map.entry("poneyland") { /// // We delete the entry from the map. @@ -5191,8 +5296,8 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// } /// /// assert_eq!(map.contains_key("poneyland"), false); - /// // Now map hold none elements but capacity is equal to the old one - /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove); + /// // Now map hold none elements + /// assert!(map.is_empty()); /// ``` #[cfg_attr(feature = "inline-more", inline)] pub fn remove_entry(self) -> (K, V) { @@ -5319,15 +5424,14 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// assert!(map.is_empty() && map.capacity() == 0); /// /// map.entry("poneyland").or_insert(12); - /// let capacity_before_remove = map.capacity(); /// /// if let Entry::Occupied(o) = map.entry("poneyland") { /// assert_eq!(o.remove(), 12); /// } /// /// assert_eq!(map.contains_key("poneyland"), false); - /// // Now map hold none elements but capacity is equal to the old one - /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove); + /// // Now map hold none elements + /// assert!(map.is_empty()); /// ``` #[cfg_attr(feature = "inline-more", inline)] pub fn remove(self) -> V { @@ -5567,7 +5671,7 @@ impl<'a, K, V, S, A: Allocator + Clone> VacantEntry<'a, K, V, S, A> { let entry = table.insert_entry( self.hash, (self.key, value), - make_hasher::<K, _, V, S>(&self.table.hash_builder), + make_hasher::<_, V, S>(&self.table.hash_builder), ); &mut entry.1 } @@ -5581,7 +5685,7 @@ impl<'a, K, V, S, A: Allocator + Clone> VacantEntry<'a, K, V, S, A> { let elem = self.table.table.insert( self.hash, (self.key, value), - make_hasher::<K, _, V, S>(&self.table.hash_builder), + make_hasher::<_, V, S>(&self.table.hash_builder), ); OccupiedEntry { hash: self.hash, @@ -5682,10 +5786,7 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> EntryRef<'a, 'b, K, Q, V, /// Ensures a value is in the entry by inserting, if empty, the result of the default function. /// This method allows for generating key-derived values for insertion by providing the default - /// function a reference to the key that was moved during the `.entry_ref(key)` method call. - /// - /// The reference to the moved key is provided so that cloning or copying the key is - /// unnecessary, unlike with `.or_insert_with(|| ... )`. + /// function an access to the borrower form of the key. /// /// # Examples /// @@ -5914,7 +6015,6 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// assert!(map.is_empty() && map.capacity() == 0); /// /// map.entry_ref("poneyland").or_insert(12); - /// let capacity_before_remove = map.capacity(); /// /// if let EntryRef::Occupied(o) = map.entry_ref("poneyland") { /// // We delete the entry from the map. @@ -5923,7 +6023,7 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// /// assert_eq!(map.contains_key("poneyland"), false); /// // Now map hold none elements but capacity is equal to the old one - /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove); + /// assert!(map.is_empty()); /// ``` #[cfg_attr(feature = "inline-more", inline)] pub fn remove_entry(self) -> (K, V) { @@ -6048,7 +6148,6 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// assert!(map.is_empty() && map.capacity() == 0); /// /// map.entry_ref("poneyland").or_insert(12); - /// let capacity_before_remove = map.capacity(); /// /// if let EntryRef::Occupied(o) = map.entry_ref("poneyland") { /// assert_eq!(o.remove(), 12); @@ -6056,7 +6155,7 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// /// assert_eq!(map.contains_key("poneyland"), false); /// // Now map hold none elements but capacity is equal to the old one - /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove); + /// assert!(map.is_empty()); /// ``` #[cfg_attr(feature = "inline-more", inline)] pub fn remove(self) -> V { @@ -6068,7 +6167,7 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// /// # Panics /// - /// Will panic if this OccupiedEntry was created through [`EntryRef::insert`]. + /// Will panic if this OccupiedEntryRef was created through [`EntryRef::insert`]. /// /// # Examples /// @@ -6110,7 +6209,7 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// /// # Panics /// - /// Will panic if this OccupiedEntry was created through [`Entry::insert`]. + /// Will panic if this OccupiedEntryRef was created through [`EntryRef::insert`]. /// /// # Examples /// @@ -6138,7 +6237,7 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// fn reclaim_memory(map: &mut HashMap<Rc<str>, usize>, keys: &[Rc<str>]) { /// for key in keys { /// if let EntryRef::Occupied(entry) = map.entry_ref(key.as_ref()) { - /// /// Replaces the entry's key with our version of it in `keys`. + /// // Replaces the entry's key with our version of it in `keys`. /// entry.replace_key(); /// } /// } @@ -6305,7 +6404,7 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> VacantEntryRef<'a, 'b, K, let entry = table.insert_entry( self.hash, (self.key.into_owned(), value), - make_hasher::<K, _, V, S>(&self.table.hash_builder), + make_hasher::<_, V, S>(&self.table.hash_builder), ); &mut entry.1 } @@ -6319,7 +6418,7 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> VacantEntryRef<'a, 'b, K, let elem = self.table.table.insert( self.hash, (self.key.into_owned(), value), - make_hasher::<K, _, V, S>(&self.table.hash_builder), + make_hasher::<_, V, S>(&self.table.hash_builder), ); OccupiedEntryRef { hash: self.hash, @@ -6455,17 +6554,17 @@ where /// map.insert(1, 100); /// /// let arr = [(1, 1), (2, 2)]; - /// let some_iter = arr.iter().map(|&(k, v)| (k, v)); + /// let some_iter = arr.iter().map(|(k, v)| (k, v)); /// map.extend(some_iter); /// // Replace values with existing keys with new values returned from the iterator. /// // So that the map.get(&1) doesn't return Some(&100). /// assert_eq!(map.get(&1), Some(&1)); /// /// let some_vec: Vec<_> = vec![(3, 3), (4, 4)]; - /// map.extend(some_vec.iter().map(|&(k, v)| (k, v))); + /// map.extend(some_vec.iter().map(|(k, v)| (k, v))); /// /// let some_arr = [(5, 5), (6, 6)]; - /// map.extend(some_arr.iter().map(|&(k, v)| (k, v))); + /// map.extend(some_arr.iter().map(|(k, v)| (k, v))); /// /// // You can also extend from another HashMap /// let mut new_map = HashMap::new(); @@ -8070,27 +8169,32 @@ mod test_map { fn test_try_reserve() { use crate::TryReserveError::{AllocError, CapacityOverflow}; - const MAX_USIZE: usize = usize::MAX; + const MAX_ISIZE: usize = isize::MAX as usize; let mut empty_bytes: HashMap<u8, u8> = HashMap::new(); - if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) { + if let Err(CapacityOverflow) = empty_bytes.try_reserve(usize::MAX) { } else { panic!("usize::MAX should trigger an overflow!"); } - if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE / 16) { + if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_ISIZE) { + } else { + panic!("isize::MAX should trigger an overflow!"); + } + + if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_ISIZE / 5) { } else { // This may succeed if there is enough free memory. Attempt to // allocate a few more hashmaps to ensure the allocation will fail. let mut empty_bytes2: HashMap<u8, u8> = HashMap::new(); - let _ = empty_bytes2.try_reserve(MAX_USIZE / 16); + let _ = empty_bytes2.try_reserve(MAX_ISIZE / 5); let mut empty_bytes3: HashMap<u8, u8> = HashMap::new(); - let _ = empty_bytes3.try_reserve(MAX_USIZE / 16); + let _ = empty_bytes3.try_reserve(MAX_ISIZE / 5); let mut empty_bytes4: HashMap<u8, u8> = HashMap::new(); - if let Err(AllocError { .. }) = empty_bytes4.try_reserve(MAX_USIZE / 16) { + if let Err(AllocError { .. }) = empty_bytes4.try_reserve(MAX_ISIZE / 5) { } else { - panic!("usize::MAX / 8 should trigger an OOM!"); + panic!("isize::MAX / 5 should trigger an OOM!"); } } } @@ -8280,7 +8384,7 @@ mod test_map { let e = map.table.insert( hash_value, (i, 2 * i), - super::make_hasher::<usize, _, usize, _>(&hash_builder), + super::make_hasher::<_, usize, _>(&hash_builder), ); it.reflect_insert(&e); if let Some(p) = removed.iter().position(|e| e == &(i, 2 * i)) { |