alloy_primitives/map/
fixed.rs

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

alloy_primitives/map/
fixed.rs
