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

alloy_primitives/map/
fixed.rs
