diff options
Diffstat (limited to 'vendor/hashbrown/src/set.rs')
| -rw-r--r-- | vendor/hashbrown/src/set.rs | 179 |
1 files changed, 139 insertions, 40 deletions
diff --git a/vendor/hashbrown/src/set.rs b/vendor/hashbrown/src/set.rs index 2a4dcea52..60c1b1cd1 100644 --- a/vendor/hashbrown/src/set.rs +++ b/vendor/hashbrown/src/set.rs @@ -1,6 +1,7 @@ -use crate::TryReserveError; +#[cfg(feature = "raw")] +use crate::raw::RawTable; +use crate::{Equivalent, TryReserveError}; use alloc::borrow::ToOwned; -use core::borrow::Borrow; use core::fmt; use core::hash::{BuildHasher, Hash}; use core::iter::{Chain, FromIterator, FusedIterator}; @@ -135,6 +136,18 @@ impl<T> HashSet<T, DefaultHashBuilder> { /// The hash set 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 `HashSet` 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 [`HashSet`], for example with + /// [`with_hasher`](HashSet::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 /// /// ``` @@ -153,6 +166,18 @@ impl<T> HashSet<T, DefaultHashBuilder> { /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` 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 [`HashSet`], for example with + /// [`with_capacity_and_hasher`](HashSet::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 /// /// ``` @@ -175,6 +200,18 @@ impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> { /// The hash set 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 `HashSet` 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 [`HashSet`], for example with + /// [`with_hasher_in`](HashSet::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 /// /// ``` @@ -193,6 +230,18 @@ impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> { /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` 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 [`HashSet`], for example with + /// [`with_capacity_and_hasher_in`](HashSet::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 /// /// ``` @@ -386,16 +435,23 @@ impl<T, S> HashSet<T, S, Global> { /// Creates a new empty hash set which will use the given hasher to hash /// keys. /// - /// The hash set is also created with the default initial capacity. + /// The hash set is initially created with a capacity of 0, so it will not + /// allocate until it is first inserted into. + /// + /// # HashDoS resistance /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s 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. + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` 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 [`HashSet`]. /// /// The `hash_builder` passed should implement the [`BuildHasher`] trait for - /// the HashMap to be useful, see its documentation for details. + /// the HashSet 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 /// @@ -407,8 +463,6 @@ impl<T, S> HashSet<T, S, Global> { /// let mut set = HashSet::with_hasher(s); /// set.insert(2); /// ``` - /// - /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html #[cfg_attr(feature = "inline-more", inline)] pub const fn with_hasher(hasher: S) -> Self { Self { @@ -422,13 +476,20 @@ impl<T, S> HashSet<T, S, Global> { /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s 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 `HashSet` 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 [`HashSet`]. /// /// The `hash_builder` passed should implement the [`BuildHasher`] trait for - /// the HashMap to be useful, see its documentation for details. + /// the HashSet 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 /// @@ -440,8 +501,6 @@ impl<T, S> HashSet<T, S, Global> { /// let mut set = HashSet::with_capacity_and_hasher(10, s); /// set.insert(1); /// ``` - /// - /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html #[cfg_attr(feature = "inline-more", inline)] pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self { Self { @@ -463,12 +522,23 @@ where /// Creates a new empty hash set which will use the given hasher to hash /// keys. /// - /// The hash set is also created with the default initial capacity. + /// The hash set is initially created with a capacity of 0, so it will not + /// allocate until it is first inserted into. /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s 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 `HashSet` 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 [`HashSet`]. + /// + /// The `hash_builder` passed should implement the [`BuildHasher`] trait for + /// the HashSet 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 /// @@ -481,7 +551,7 @@ where /// set.insert(2); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn with_hasher_in(hasher: S, alloc: A) -> Self { + pub const fn with_hasher_in(hasher: S, alloc: A) -> Self { Self { map: HashMap::with_hasher_in(hasher, alloc), } @@ -493,10 +563,20 @@ where /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s 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 `HashSet` 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 [`HashSet`]. + /// + /// The `hash_builder` passed should implement the [`BuildHasher`] trait for + /// the HashSet 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 /// @@ -547,7 +627,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`](HashSet::try_reserve) instead + /// if you want to handle memory allocation failure. + /// + /// [`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 /// @@ -773,8 +858,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, { self.map.contains_key(value) } @@ -800,8 +884,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, { // Avoid `Option::map` because it bloats LLVM IR. match self.map.get_key_value(value) { @@ -856,8 +939,7 @@ where #[inline] pub fn get_or_insert_owned<Q: ?Sized>(&mut self, value: &Q) -> &T where - T: Borrow<Q>, - Q: Hash + Eq + ToOwned<Owned = T>, + Q: Hash + Equivalent<T> + ToOwned<Owned = T>, { // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`. @@ -889,8 +971,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, F: FnOnce(&Q) -> T, { // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with @@ -1106,8 +1187,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, { self.map.remove(value).is_some() } @@ -1133,8 +1213,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, { // Avoid `Option::map` because it bloats LLVM IR. match self.map.remove_entry(value) { @@ -1142,6 +1221,26 @@ where None => None, } } + + /// Returns a mutable reference to the [`RawTable`] used underneath [`HashSet`]. + /// This function is only available if the `raw` feature of the crate is enabled. + /// + /// # Note + /// + /// 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 set that can be useful + /// for extending the HashSet's API, but may lead to *[undefined behavior]*. + /// + /// [`HashSet`]: struct.HashSet.html + /// [`RawTable`]: crate::raw::RawTable + /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html + #[cfg(feature = "raw")] + #[cfg_attr(feature = "inline-more", inline)] + pub fn raw_table(&mut self) -> &mut RawTable<(T, ()), A> { + self.map.raw_table() + } } impl<T, S, A> PartialEq for HashSet<T, S, A> |