diff options
Diffstat (limited to 'third_party/rust/ahash/src/lib.rs')
| -rw-r--r-- | third_party/rust/ahash/src/lib.rs | 243 |
1 files changed, 188 insertions, 55 deletions
diff --git a/third_party/rust/ahash/src/lib.rs b/third_party/rust/ahash/src/lib.rs index 9964a7c47b..69fb2ca237 100644 --- a/third_party/rust/ahash/src/lib.rs +++ b/third_party/rust/ahash/src/lib.rs @@ -1,86 +1,208 @@ -//! AHash is a hashing algorithm is intended to be a high performance, (hardware specific), keyed hash function. -//! This can be seen as a DOS resistant alternative to `FxHash`, or a fast equivalent to `SipHash`. -//! It provides a high speed hash algorithm, but where the result is not predictable without knowing a Key. -//! This allows it to be used in a `HashMap` without allowing for the possibility that an malicious user can +//! AHash is a high performance keyed hash function. +//! +//! It quickly provides a high quality hash where the result is not predictable without knowing the Key. +//! AHash works with `HashMap` to hash keys, but without allowing for the possibility that an malicious user can //! induce a collision. //! //! # How aHash works //! -//! aHash uses the hardware AES instruction on x86 processors to provide a keyed hash function. -//! aHash is not a cryptographically secure hash. -//! -//! # Example -//! ``` -//! use ahash::{AHasher, RandomState}; -//! use std::collections::HashMap; +//! When it is available aHash uses the hardware AES instructions to provide a keyed hash function. +//! When it is not, aHash falls back on a slightly slower alternative algorithm. //! -//! let mut map: HashMap<i32, i32, RandomState> = HashMap::default(); -//! map.insert(12, 34); -//! ``` -//! For convinence wrappers called `AHashMap` and `AHashSet` are also provided. -//! These to the same thing with slightly less typing. -//! ```ignore -//! use ahash::AHashMap; -//! -//! let mut map: AHashMap<i32, i32> = AHashMap::with_capacity(4); -//! map.insert(12, 34); -//! map.insert(56, 78); -//! ``` +//! Because aHash does not have a fixed standard for its output, it is able to improve over time. +//! But this also means that different computers or computers using different versions of ahash may observe different +//! hash values for the same input. +#![cfg_attr( + all( + feature = "std", + any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng") + ), + doc = r##" +# Basic Usage +AHash provides an implementation of the [Hasher] trait. +To construct a HashMap using aHash as its hasher do the following: +``` +use ahash::{AHasher, RandomState}; +use std::collections::HashMap; + +let mut map: HashMap<i32, i32, RandomState> = HashMap::default(); +map.insert(12, 34); +``` + +### Randomness + +The above requires a source of randomness to generate keys for the hashmap. By default this obtained from the OS. +It is also possible to have randomness supplied via the `compile-time-rng` flag, or manually. + +### If randomess is not available + +[AHasher::default()] can be used to hash using fixed keys. This works with +[BuildHasherDefault](std::hash::BuildHasherDefault). For example: + +``` +use std::hash::BuildHasherDefault; +use std::collections::HashMap; +use ahash::AHasher; + +let mut m: HashMap<_, _, BuildHasherDefault<AHasher>> = HashMap::default(); + # m.insert(12, 34); +``` +It is also possible to instantiate [RandomState] directly: + +``` +use ahash::HashMap; +use ahash::RandomState; + +let mut m = HashMap::with_hasher(RandomState::with_seed(42)); + # m.insert(1, 2); +``` +Or for uses besides a hashhmap: +``` +use std::hash::BuildHasher; +use ahash::RandomState; + +let hash_builder = RandomState::with_seed(42); +let hash = hash_builder.hash_one("Some Data"); +``` +There are several constructors for [RandomState] with different ways to supply seeds. + +# Convenience wrappers + +For convenience, both new-type wrappers and type aliases are provided. + +The new type wrappers are called called `AHashMap` and `AHashSet`. +``` +use ahash::AHashMap; + +let mut map: AHashMap<i32, i32> = AHashMap::new(); +map.insert(12, 34); +``` +This avoids the need to type "RandomState". (For convenience `From`, `Into`, and `Deref` are provided). + +# Aliases + +For even less typing and better interop with existing libraries (such as rayon) which require a `std::collection::HashMap` , +the type aliases [HashMap], [HashSet] are provided. + +``` +use ahash::{HashMap, HashMapExt}; + +let mut map: HashMap<i32, i32> = HashMap::new(); +map.insert(12, 34); +``` +Note the import of [HashMapExt]. This is needed for the constructor. + +"## +)] #![deny(clippy::correctness, clippy::complexity, clippy::perf)] #![allow(clippy::pedantic, clippy::cast_lossless, clippy::unreadable_literal)] #![cfg_attr(all(not(test), not(feature = "std")), no_std)] #![cfg_attr(feature = "specialize", feature(min_specialization))] -#![cfg_attr(feature = "stdsimd", feature(stdsimd))] +#![cfg_attr(feature = "nightly-arm-aes", feature(stdarch_arm_neon_intrinsics))] #[macro_use] mod convert; -#[cfg(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -))] -mod aes_hash; mod fallback_hash; + +cfg_if::cfg_if! { + if #[cfg(any( + all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), + all(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)), + all(feature = "nightly-arm-aes", target_arch = "arm", target_feature = "aes", not(miri)), + ))] { + mod aes_hash; + pub use crate::aes_hash::AHasher; + } else { + pub use crate::fallback_hash::AHasher; + } +} + +cfg_if::cfg_if! { + if #[cfg(feature = "std")] { + mod hash_map; + mod hash_set; + + pub use crate::hash_map::AHashMap; + pub use crate::hash_set::AHashSet; + + /// [Hasher]: std::hash::Hasher + /// [HashMap]: std::collections::HashMap + /// Type alias for [HashMap]<K, V, ahash::RandomState> + pub type HashMap<K, V> = std::collections::HashMap<K, V, crate::RandomState>; + + /// Type alias for [HashSet]<K, ahash::RandomState> + pub type HashSet<K> = std::collections::HashSet<K, crate::RandomState>; + } +} + #[cfg(test)] mod hash_quality_test; -#[cfg(feature = "std")] -mod hash_map; -#[cfg(feature = "std")] -mod hash_set; mod operations; -mod random_state; +pub mod random_state; mod specialize; -#[cfg(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -))] -pub use crate::aes_hash::AHasher; - -#[cfg(not(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -)))] -pub use crate::fallback_hash::AHasher; pub use crate::random_state::RandomState; -pub use crate::specialize::CallHasher; - -#[cfg(feature = "std")] -pub use crate::hash_map::AHashMap; -#[cfg(feature = "std")] -pub use crate::hash_set::AHashSet; use core::hash::BuildHasher; use core::hash::Hash; use core::hash::Hasher; +#[cfg(feature = "std")] +/// A convenience trait that can be used together with the type aliases defined to +/// get access to the `new()` and `with_capacity()` methods for the HashMap type alias. +pub trait HashMapExt { + /// Constructs a new HashMap + fn new() -> Self; + /// Constructs a new HashMap with a given initial capacity + fn with_capacity(capacity: usize) -> Self; +} + +#[cfg(feature = "std")] +/// A convenience trait that can be used together with the type aliases defined to +/// get access to the `new()` and `with_capacity()` methods for the HashSet type aliases. +pub trait HashSetExt { + /// Constructs a new HashSet + fn new() -> Self; + /// Constructs a new HashSet with a given initial capacity + fn with_capacity(capacity: usize) -> Self; +} + +#[cfg(feature = "std")] +impl<K, V, S> HashMapExt for std::collections::HashMap<K, V, S> +where + S: BuildHasher + Default, +{ + fn new() -> Self { + std::collections::HashMap::with_hasher(S::default()) + } + + fn with_capacity(capacity: usize) -> Self { + std::collections::HashMap::with_capacity_and_hasher(capacity, S::default()) + } +} + +#[cfg(feature = "std")] +impl<K, S> HashSetExt for std::collections::HashSet<K, S> +where + S: BuildHasher + Default, +{ + fn new() -> Self { + std::collections::HashSet::with_hasher(S::default()) + } + + fn with_capacity(capacity: usize) -> Self { + std::collections::HashSet::with_capacity_and_hasher(capacity, S::default()) + } +} + /// Provides a default [Hasher] with fixed keys. /// This is typically used in conjunction with [BuildHasherDefault] to create /// [AHasher]s in order to hash the keys of the map. /// /// Generally it is preferable to use [RandomState] instead, so that different -/// hashmaps will have different keys. However if fixed keys are desireable this +/// hashmaps will have different keys. However if fixed keys are desirable this /// may be used instead. /// /// # Example @@ -194,9 +316,21 @@ impl<B: BuildHasher> BuildHasherExt for B { #[cfg(test)] mod test { use crate::convert::Convert; + use crate::specialize::CallHasher; use crate::*; use std::collections::HashMap; - use std::hash::Hash; + + #[test] + fn test_ahash_alias_map_construction() { + let mut map = super::HashMap::with_capacity(1234); + map.insert(1, "test"); + } + + #[test] + fn test_ahash_alias_set_construction() { + let mut set = super::HashSet::with_capacity(1234); + set.insert(1); + } #[test] fn test_default_builder() { @@ -219,7 +353,6 @@ mod test { assert_eq!(bytes, 0x6464646464646464); } - #[test] fn test_non_zero() { let mut hasher1 = AHasher::new_with_keys(0, 0); @@ -241,7 +374,7 @@ mod test { #[test] fn test_non_zero_specialized() { - let hasher_build = RandomState::with_seeds(0,0,0,0); + let hasher_build = RandomState::with_seeds(0, 0, 0, 0); let h1 = str::get_hash("foo", &hasher_build); let h2 = str::get_hash("bar", &hasher_build); |