alloy_primitives/map/
fixed.rs

1use super::*;
2use crate::{Address, B256, FixedBytes, Selector, U256};
3use cfg_if::cfg_if;
4use core::{
5    fmt,
6    hash::{BuildHasher, Hasher},
7};
8
9/// [`HashMap`] optimized for hashing [fixed-size byte arrays](FixedBytes).
10pub type FbMap<const N: usize, V> = HashMap<FixedBytes<N>, V, FbBuildHasher<N>>;
11#[doc(hidden)]
12pub type FbHashMap<const N: usize, V> = FbMap<N, V>;
13/// [`HashSet`] optimized for hashing [fixed-size byte arrays](FixedBytes).
14pub type FbSet<const N: usize> = HashSet<FixedBytes<N>, FbBuildHasher<N>>;
15#[doc(hidden)]
16pub type FbHashSet<const N: usize> = FbSet<N>;
17
18cfg_if! {
19    if #[cfg(feature = "map-indexmap")] {
20        /// [`IndexMap`] optimized for hashing [fixed-size byte arrays](FixedBytes).
21        pub type FbIndexMap<const N: usize, V> =
22            indexmap::IndexMap<FixedBytes<N>, V, FbBuildHasher<N>>;
23        /// [`IndexSet`] optimized for hashing [fixed-size byte arrays](FixedBytes).
24        pub type FbIndexSet<const N: usize> =
25            indexmap::IndexSet<FixedBytes<N>, FbBuildHasher<N>>;
26    }
27}
28
29macro_rules! fb_alias_maps {
30    ($($ty:ident < $n:literal >),* $(,)?) => { paste::paste! {
31        $(
32            #[doc = concat!("[`HashMap`] optimized for hashing [`", stringify!($ty), "`].")]
33            pub type [<$ty Map>]<V> = HashMap<$ty, V, FbBuildHasher<$n>>;
34            #[doc(hidden)]
35            pub type [<$ty HashMap>]<V> = [<$ty Map>]<V>;
36            #[doc = concat!("[`HashSet`] optimized for hashing [`", stringify!($ty), "`].")]
37            pub type [<$ty Set>] = HashSet<$ty, FbBuildHasher<$n>>;
38            #[doc(hidden)]
39            pub type [<$ty HashSet>] = [<$ty Set>];
40
41            cfg_if! {
42                if #[cfg(feature = "map-indexmap")] {
43                    #[doc = concat!("[`IndexMap`] optimized for hashing [`", stringify!($ty), "`].")]
44                    pub type [<$ty IndexMap>]<V> = IndexMap<$ty, V, FbBuildHasher<$n>>;
45                    #[doc = concat!("[`IndexSet`] optimized for hashing [`", stringify!($ty), "`].")]
46                    pub type [<$ty IndexSet>] = IndexSet<$ty, FbBuildHasher<$n>>;
47                }
48            }
49        )*
50    } };
51}
52
53fb_alias_maps!(Selector<4>, Address<20>, B256<32>, U256<32>);
54
55type FbBuildHasherInner = super::FxBuildHasherInner;
56type FbHasherInner = rustc_hash::FxHasher;
57
58/// [`BuildHasher`] optimized for hashing [fixed-size byte arrays](FixedBytes).
59///
60/// **NOTE:** this hasher accepts only `N`-length byte arrays! It is invalid to hash anything else.
61#[derive(Clone, Default)]
62pub struct FbBuildHasher<const N: usize> {
63    inner: FbBuildHasherInner,
64    _marker: core::marker::PhantomData<[(); N]>,
65}
66
67impl<const N: usize> fmt::Debug for FbBuildHasher<N> {
68    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69        f.debug_struct("FbBuildHasher").finish_non_exhaustive()
70    }
71}
72
73impl<const N: usize> BuildHasher for FbBuildHasher<N> {
74    type Hasher = FbHasher<N>;
75
76    #[inline]
77    fn build_hasher(&self) -> Self::Hasher {
78        FbHasher { inner: self.inner.build_hasher(), _marker: core::marker::PhantomData }
79    }
80}
81
82/// [`Hasher`] optimized for hashing [fixed-size byte arrays](FixedBytes).
83///
84/// **NOTE:** this hasher accepts only `N`-length byte arrays! It is invalid to hash anything else.
85#[derive(Clone)]
86pub struct FbHasher<const N: usize> {
87    inner: FbHasherInner,
88    _marker: core::marker::PhantomData<[(); N]>,
89}
90
91impl<const N: usize> Default for FbHasher<N> {
92    #[inline]
93    fn default() -> Self {
94        Self {
95            inner: FbBuildHasherInner::default().build_hasher(),
96            _marker: core::marker::PhantomData,
97        }
98    }
99}
100
101impl<const N: usize> fmt::Debug for FbHasher<N> {
102    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
103        f.debug_struct("FbHasher").finish_non_exhaustive()
104    }
105}
106
107impl<const N: usize> Hasher for FbHasher<N> {
108    #[inline]
109    fn finish(&self) -> u64 {
110        self.inner.finish()
111    }
112
113    #[inline]
114    fn write(&mut self, bytes: &[u8]) {
115        // SAFETY: Precondition.
116        unsafe { core::hint::assert_unchecked(bytes.len() == N) };
117        // Threshold decided by some basic micro-benchmarks with fxhash.
118        if N > 32 {
119            self.inner.write(bytes);
120        } else {
121            write_bytes_unrolled(&mut self.inner, bytes);
122        }
123    }
124
125    // We can just skip hashing the length prefix entirely since we know it's always `<=N`.
126    // Not always `=N`, because arrays like `[T; M]` are hashed as `[u8; N=M*size_of::<T>()]` for a
127    // few primitive `T` types, like integers.
128
129    // `write_length_prefix` calls `write_usize` by default.
130    #[cfg(not(feature = "nightly"))]
131    #[inline]
132    fn write_usize(&mut self, i: usize) {
133        debug_assert!(i <= N, "{i} > {N}")
134    }
135
136    #[cfg(feature = "nightly")]
137    #[inline]
138    fn write_length_prefix(&mut self, len: usize) {
139        debug_assert!(len <= N, "{len} > {N}")
140    }
141}
142
143#[inline(always)]
144fn write_bytes_unrolled(hasher: &mut FbHasherInner, mut bytes: &[u8]) {
145    while let Some((chunk, rest)) = bytes.split_first_chunk() {
146        hasher.write_usize(usize::from_ne_bytes(*chunk));
147        bytes = rest;
148    }
149    if usize::BITS > 64 {
150        if let Some((chunk, rest)) = bytes.split_first_chunk() {
151            hasher.write_u64(u64::from_ne_bytes(*chunk));
152            bytes = rest;
153        }
154    }
155    if usize::BITS > 32 {
156        if let Some((chunk, rest)) = bytes.split_first_chunk() {
157            hasher.write_u32(u32::from_ne_bytes(*chunk));
158            bytes = rest;
159        }
160    }
161    if usize::BITS > 16 {
162        if let Some((chunk, rest)) = bytes.split_first_chunk() {
163            hasher.write_u16(u16::from_ne_bytes(*chunk));
164            bytes = rest;
165        }
166    }
167    if usize::BITS > 8 {
168        if let Some((chunk, rest)) = bytes.split_first_chunk() {
169            hasher.write_u8(u8::from_ne_bytes(*chunk));
170            bytes = rest;
171        }
172    }
173
174    debug_assert!(bytes.is_empty());
175}
176
177#[cfg(test)]
178mod tests {
179    use super::*;
180
181    fn hash_zero<const N: usize>() -> u64 {
182        FbBuildHasher::<N>::default().hash_one(&FixedBytes::<N>::ZERO)
183    }
184
185    #[test]
186    fn fb_hasher() {
187        // Just by running it once we test that it compiles and that debug assertions are correct.
188        ruint::const_for!(N in [ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
189                                16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
190                                32, 47, 48, 49, 63, 64, 127, 128, 256, 512, 1024, 2048, 4096] {
191            let _ = hash_zero::<N>();
192        });
193    }
194
195    #[test]
196    fn map() {
197        let mut map = AddressHashMap::<bool>::default();
198        map.insert(Address::ZERO, true);
199        assert_eq!(map.get(&Address::ZERO), Some(&true));
200        assert_eq!(map.get(&Address::with_last_byte(1)), None);
201
202        let map2 = map.clone();
203        assert_eq!(map.len(), map2.len());
204        assert_eq!(map.len(), 1);
205        assert_eq!(map2.get(&Address::ZERO), Some(&true));
206        assert_eq!(map2.get(&Address::with_last_byte(1)), None);
207    }
208
209    #[test]
210    fn u256_map() {
211        let mut map = U256Map::default();
212        map.insert(U256::ZERO, true);
213        assert_eq!(map.get(&U256::ZERO), Some(&true));
214        assert_eq!(map.get(&U256::ONE), None);
215
216        let map2 = map.clone();
217        assert_eq!(map.len(), map2.len());
218        assert_eq!(map.len(), 1);
219        assert_eq!(map2.get(&U256::ZERO), Some(&true));
220        assert_eq!(map2.get(&U256::ONE), None);
221    }
222}
alloy_primitives/map/fixed.rs

alloy_primitives/map/
fixed.rs
