diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
commit | 9918693037dce8aa4bb6f08741b6812923486c18 (patch) | |
tree | 21d2b40bec7e6a7ea664acee056eb3d08e15a1cf /library/std/src/collections | |
parent | Releasing progress-linux version 1.75.0+dfsg1-5~progress7.99u1. (diff) | |
download | rustc-9918693037dce8aa4bb6f08741b6812923486c18.tar.xz rustc-9918693037dce8aa4bb6f08741b6812923486c18.zip |
Merging upstream version 1.76.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'library/std/src/collections')
-rw-r--r-- | library/std/src/collections/hash/map.rs | 157 | ||||
-rw-r--r-- | library/std/src/collections/hash/map/tests.rs | 2 | ||||
-rw-r--r-- | library/std/src/collections/hash/set.rs | 10 | ||||
-rw-r--r-- | library/std/src/collections/hash/set/tests.rs | 2 | ||||
-rw-r--r-- | library/std/src/collections/mod.rs | 5 |
5 files changed, 16 insertions, 160 deletions
diff --git a/library/std/src/collections/hash/map.rs b/library/std/src/collections/hash/map.rs index 4d109285d..39e94902c 100644 --- a/library/std/src/collections/hash/map.rs +++ b/library/std/src/collections/hash/map.rs @@ -6,16 +6,13 @@ use self::Entry::*; use hashbrown::hash_map as base; use crate::borrow::Borrow; -use crate::cell::Cell; use crate::collections::TryReserveError; use crate::collections::TryReserveErrorKind; use crate::error::Error; use crate::fmt::{self, Debug}; -#[allow(deprecated)] -use crate::hash::{BuildHasher, Hash, Hasher, SipHasher13}; +use crate::hash::{BuildHasher, Hash, RandomState}; use crate::iter::FusedIterator; use crate::ops::Index; -use crate::sys; /// A [hash map] implemented with quadratic probing and SIMD lookup. /// @@ -274,7 +271,7 @@ impl<K, V, S> HashMap<K, V, S> { /// /// ``` /// use std::collections::HashMap; - /// use std::collections::hash_map::RandomState; + /// use std::hash::RandomState; /// /// let s = RandomState::new(); /// let mut map = HashMap::with_hasher(s); @@ -306,7 +303,7 @@ impl<K, V, S> HashMap<K, V, S> { /// /// ``` /// use std::collections::HashMap; - /// use std::collections::hash_map::RandomState; + /// use std::hash::RandomState; /// /// let s = RandomState::new(); /// let mut map = HashMap::with_capacity_and_hasher(10, s); @@ -717,7 +714,7 @@ impl<K, V, S> HashMap<K, V, S> { /// /// ``` /// use std::collections::HashMap; - /// use std::collections::hash_map::RandomState; + /// use std::hash::RandomState; /// /// let hasher = RandomState::new(); /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher); @@ -3072,152 +3069,6 @@ where } } -/// `RandomState` is the default state for [`HashMap`] types. -/// -/// A particular instance `RandomState` will create the same instances of -/// [`Hasher`], but the hashers created by two different `RandomState` -/// instances are unlikely to produce the same result for the same values. -/// -/// # Examples -/// -/// ``` -/// use std::collections::HashMap; -/// use std::collections::hash_map::RandomState; -/// -/// let s = RandomState::new(); -/// let mut map = HashMap::with_hasher(s); -/// map.insert(1, 2); -/// ``` -#[derive(Clone)] -#[stable(feature = "hashmap_build_hasher", since = "1.7.0")] -pub struct RandomState { - k0: u64, - k1: u64, -} - -impl RandomState { - /// Constructs a new `RandomState` that is initialized with random keys. - /// - /// # Examples - /// - /// ``` - /// use std::collections::hash_map::RandomState; - /// - /// let s = RandomState::new(); - /// ``` - #[inline] - #[allow(deprecated)] - // rand - #[must_use] - #[stable(feature = "hashmap_build_hasher", since = "1.7.0")] - pub fn new() -> RandomState { - // Historically this function did not cache keys from the OS and instead - // simply always called `rand::thread_rng().gen()` twice. In #31356 it - // was discovered, however, that because we re-seed the thread-local RNG - // from the OS periodically that this can cause excessive slowdown when - // many hash maps are created on a thread. To solve this performance - // trap we cache the first set of randomly generated keys per-thread. - // - // Later in #36481 it was discovered that exposing a deterministic - // iteration order allows a form of DOS attack. To counter that we - // increment one of the seeds on every RandomState creation, giving - // every corresponding HashMap a different iteration order. - thread_local!(static KEYS: Cell<(u64, u64)> = { - Cell::new(sys::hashmap_random_keys()) - }); - - KEYS.with(|keys| { - let (k0, k1) = keys.get(); - keys.set((k0.wrapping_add(1), k1)); - RandomState { k0, k1 } - }) - } -} - -#[stable(feature = "hashmap_build_hasher", since = "1.7.0")] -impl BuildHasher for RandomState { - type Hasher = DefaultHasher; - #[inline] - #[allow(deprecated)] - fn build_hasher(&self) -> DefaultHasher { - DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1)) - } -} - -/// The default [`Hasher`] used by [`RandomState`]. -/// -/// The internal algorithm is not specified, and so it and its hashes should -/// not be relied upon over releases. -#[stable(feature = "hashmap_default_hasher", since = "1.13.0")] -#[allow(deprecated)] -#[derive(Clone, Debug)] -pub struct DefaultHasher(SipHasher13); - -impl DefaultHasher { - /// Creates a new `DefaultHasher`. - /// - /// This hasher is not guaranteed to be the same as all other - /// `DefaultHasher` instances, but is the same as all other `DefaultHasher` - /// instances created through `new` or `default`. - #[stable(feature = "hashmap_default_hasher", since = "1.13.0")] - #[inline] - #[allow(deprecated)] - #[rustc_const_unstable(feature = "const_hash", issue = "104061")] - #[must_use] - pub const fn new() -> DefaultHasher { - DefaultHasher(SipHasher13::new_with_keys(0, 0)) - } -} - -#[stable(feature = "hashmap_default_hasher", since = "1.13.0")] -impl Default for DefaultHasher { - /// Creates a new `DefaultHasher` using [`new`]. - /// See its documentation for more. - /// - /// [`new`]: DefaultHasher::new - #[inline] - fn default() -> DefaultHasher { - DefaultHasher::new() - } -} - -#[stable(feature = "hashmap_default_hasher", since = "1.13.0")] -impl Hasher for DefaultHasher { - // The underlying `SipHasher13` doesn't override the other - // `write_*` methods, so it's ok not to forward them here. - - #[inline] - fn write(&mut self, msg: &[u8]) { - self.0.write(msg) - } - - #[inline] - fn write_str(&mut self, s: &str) { - self.0.write_str(s); - } - - #[inline] - fn finish(&self) -> u64 { - self.0.finish() - } -} - -#[stable(feature = "hashmap_build_hasher", since = "1.7.0")] -impl Default for RandomState { - /// Constructs a new `RandomState`. - #[inline] - fn default() -> RandomState { - RandomState::new() - } -} - -#[stable(feature = "std_debug", since = "1.16.0")] -impl fmt::Debug for RandomState { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_struct("RandomState").finish_non_exhaustive() - } -} - #[inline] fn map_entry<'a, K: 'a, V: 'a>(raw: base::RustcEntry<'a, K, V>) -> Entry<'a, K, V> { match raw { diff --git a/library/std/src/collections/hash/map/tests.rs b/library/std/src/collections/hash/map/tests.rs index 91a3776e7..8585376ab 100644 --- a/library/std/src/collections/hash/map/tests.rs +++ b/library/std/src/collections/hash/map/tests.rs @@ -1,8 +1,8 @@ use super::Entry::{Occupied, Vacant}; use super::HashMap; -use super::RandomState; use crate::assert_matches::assert_matches; use crate::cell::RefCell; +use crate::hash::RandomState; use crate::test_helpers::test_rng; use rand::Rng; use realstd::collections::TryReserveErrorKind::*; diff --git a/library/std/src/collections/hash/set.rs b/library/std/src/collections/hash/set.rs index 6a87f6e5f..8bc596082 100644 --- a/library/std/src/collections/hash/set.rs +++ b/library/std/src/collections/hash/set.rs @@ -6,11 +6,11 @@ use hashbrown::hash_set as base; use crate::borrow::Borrow; use crate::collections::TryReserveError; use crate::fmt; -use crate::hash::{BuildHasher, Hash}; +use crate::hash::{BuildHasher, Hash, RandomState}; use crate::iter::{Chain, FusedIterator}; use crate::ops::{BitAnd, BitOr, BitXor, Sub}; -use super::map::{map_try_reserve_error, RandomState}; +use super::map::map_try_reserve_error; /// A [hash set] implemented as a `HashMap` where the value is `()`. /// @@ -361,7 +361,7 @@ impl<T, S> HashSet<T, S> { /// /// ``` /// use std::collections::HashSet; - /// use std::collections::hash_map::RandomState; + /// use std::hash::RandomState; /// /// let s = RandomState::new(); /// let mut set = HashSet::with_hasher(s); @@ -393,7 +393,7 @@ impl<T, S> HashSet<T, S> { /// /// ``` /// use std::collections::HashSet; - /// use std::collections::hash_map::RandomState; + /// use std::hash::RandomState; /// /// let s = RandomState::new(); /// let mut set = HashSet::with_capacity_and_hasher(10, s); @@ -411,7 +411,7 @@ impl<T, S> HashSet<T, S> { /// /// ``` /// use std::collections::HashSet; - /// use std::collections::hash_map::RandomState; + /// use std::hash::RandomState; /// /// let hasher = RandomState::new(); /// let set: HashSet<i32> = HashSet::with_hasher(hasher); diff --git a/library/std/src/collections/hash/set/tests.rs b/library/std/src/collections/hash/set/tests.rs index e0cd80b44..208f61e75 100644 --- a/library/std/src/collections/hash/set/tests.rs +++ b/library/std/src/collections/hash/set/tests.rs @@ -1,6 +1,6 @@ -use super::super::map::RandomState; use super::HashSet; +use crate::hash::RandomState; use crate::panic::{catch_unwind, AssertUnwindSafe}; use crate::sync::atomic::{AtomicU32, Ordering}; use crate::sync::Arc; diff --git a/library/std/src/collections/mod.rs b/library/std/src/collections/mod.rs index 42f738acb..1389d24a8 100644 --- a/library/std/src/collections/mod.rs +++ b/library/std/src/collections/mod.rs @@ -439,6 +439,11 @@ pub mod hash_map { //! A hash map implemented with quadratic probing and SIMD lookup. #[stable(feature = "rust1", since = "1.0.0")] pub use super::hash::map::*; + + #[stable(feature = "hashmap_build_hasher", since = "1.7.0")] + pub use crate::hash::random::DefaultHasher; + #[stable(feature = "hashmap_build_hasher", since = "1.7.0")] + pub use crate::hash::random::RandomState; } #[stable(feature = "rust1", since = "1.0.0")] |