hashable_map/
set.rs

1use std::{
2    hash::{BuildHasher, Hash, Hasher, RandomState},
3    ops::{Deref, DerefMut},
4};
5
6macro_rules! make_hashable_set {
7    ($hash_set_impl:ident) => {
8        #[derive(Clone, Debug, Default)]
9        pub struct HashableSet<T, S = RandomState>($hash_set_impl<T, S>);
10
11        impl<T> HashableSet<T> {
12            pub fn new() -> Self {
13                Self($hash_set_impl::new())
14            }
15
16            pub fn with_capacity(capacity: usize) -> Self {
17                Self($hash_set_impl::with_capacity(capacity))
18            }
19        }
20
21        impl<T, S> HashableSet<T, S> {
22            pub fn with_hasher(hash_builder: S) -> Self {
23                Self($hash_set_impl::with_hasher(hash_builder))
24            }
25
26            pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
27                Self($hash_set_impl::with_capacity_and_hasher(
28                    capacity,
29                    hash_builder,
30                ))
31            }
32        }
33
34        impl<T, S> Deref for HashableSet<T, S> {
35            type Target = $hash_set_impl<T, S>;
36
37            fn deref(&self) -> &Self::Target {
38                &self.0
39            }
40        }
41
42        impl<T, S> DerefMut for HashableSet<T, S> {
43            fn deref_mut(&mut self) -> &mut Self::Target {
44                &mut self.0
45            }
46        }
47
48        impl<T, S> From<$hash_set_impl<T, S>> for HashableSet<T, S> {
49            fn from(value: $hash_set_impl<T, S>) -> Self {
50                Self(value)
51            }
52        }
53
54        impl<T, S> From<HashableSet<T, S>> for $hash_set_impl<T, S> {
55            fn from(value: HashableSet<T, S>) -> $hash_set_impl<T, S> {
56                value.0
57            }
58        }
59
60        impl<T, S, D> Hash for HashableSet<T, S>
61        where
62            T: Hash,
63            S: BuildHasher<Hasher = D>,
64            D: Hasher + Default,
65        {
66            fn hash<H: Hasher>(&self, state: &mut H) {
67                state.write_usize(self.len());
68
69                let hash = self
70                    .iter()
71                    .map(|t| {
72                        let mut hasher = D::default();
73                        t.hash(&mut hasher);
74                        hasher.finish()
75                    })
76                    .fold(0, u64::wrapping_add);
77
78                state.write_u64(hash);
79            }
80        }
81
82        impl<T, S> PartialEq for HashableSet<T, S>
83        where
84            T: Eq + Hash,
85            S: BuildHasher,
86        {
87            fn eq(&self, other: &Self) -> bool {
88                self.0 == other.0
89            }
90        }
91
92        impl<T, S> Eq for HashableSet<T, S>
93        where
94            T: Eq + Hash,
95            S: BuildHasher,
96        {
97        }
98
99        #[cfg(feature = "serde")]
100        impl<T, S> serde::Serialize for HashableSet<T, S>
101        where
102            $hash_set_impl<T, S>: serde::Serialize,
103        {
104            fn serialize<Ser>(&self, serializer: Ser) -> Result<Ser::Ok, Ser::Error>
105            where
106                Ser: serde::Serializer,
107            {
108                self.0.serialize(serializer)
109            }
110        }
111
112        #[cfg(feature = "serde")]
113        impl<'de, T, S> serde::Deserialize<'de> for HashableSet<T, S>
114        where
115            $hash_set_impl<T, S>: serde::Deserialize<'de>,
116        {
117            fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
118            where
119                D: serde::Deserializer<'de>,
120            {
121                Ok(Self($hash_set_impl::deserialize(deserializer)?))
122            }
123        }
124    };
125}
126
127use std::collections::HashSet;
128make_hashable_set!(HashSet);
129
130#[cfg(test)]
131pub(crate) mod tests {
132    use std::hash::BuildHasherDefault;
133
134    use super::*;
135
136    use crate::map::tests::*;
137
138    #[test]
139    fn insertion_order_random_state() {
140        insertion_order::<RandomState, _>()
141    }
142
143    #[test]
144    fn insertion_order_fx_build_hasher() {
145        insertion_order::<fxhash::FxBuildHasher, _>()
146    }
147
148    #[test]
149    fn insertion_order_fnv_build_hasher() {
150        insertion_order::<fnv::FnvBuildHasher, _>()
151    }
152
153    #[test]
154    fn insertion_order_ahash_build_hasher() {
155        insertion_order::<BuildHasherDefault<ahash::AHasher>, _>()
156    }
157
158    fn insertion_order<B: BuildHasher<Hasher = H> + Default, H: Hasher + Default>() {
159        let values = generate_random_values::<i32, 128>();
160        let values_shuffled = shuffle(&values);
161        let values_other = generate_random_values::<i32, 128>();
162
163        assert_ne!(values, values_shuffled);
164        assert_ne!(values, values_other);
165        assert_ne!(values_shuffled, values_other);
166
167        let mut a = HashableSet::<_, B>::default();
168        a.extend(values.iter().copied());
169        let mut b = HashableSet::<_, B>::default();
170        b.extend(values_shuffled.iter().copied());
171        let mut c = HashableSet::<_, B>::default();
172        c.extend(values_other.iter().copied());
173
174        assert_hash_eq(&a, &b);
175        assert_hash_ne(&a, &c);
176        assert_hash_ne(&b, &c)
177    }
178}
hashable_map/set.rs

hashable_map/
set.rs
