hash_trie/
map.rs

1use crate::{traits::*, hash_trie::HashTrie, *};
2use alloc::fmt::Debug;
3
4/// `HashTrieMap` implements a hash map using a hash array mapped trie (HAMT).
5/// 
6/// # Example Usage
7/// 
8/// ```
9/// use fnv::FnvHasher;
10/// use hash_trie::{HashTrieMap, traits::HashLike};
11/// use std::string::String;
12/// 
13/// #[derive(Clone,Debug,Eq,Hash,PartialEq)]
14/// struct Str<'a> {
15///     s: &'a str
16/// }
17/// 
18/// impl <'a> Str<'a> {
19///     fn new(s: &'a str) -> Self {
20///         Self {s}
21///     }
22/// }
23/// 
24/// impl <'a> Default for Str<'a> {
25///     fn default() -> Self {
26///         Self {s: ""}
27///     }
28/// }
29/// impl <'a> From<Str<'a>> for String {
30///     fn from(s: Str<'a>) -> String {
31///         s.s.into()
32///     }
33/// }
34/// impl <'a> PartialEq<Str<'a>> for String {
35///     fn eq(&self, other: &Str<'a>) -> bool {
36///         *self == other.s
37///     }
38/// }
39/// impl <'a> HashLike<String> for Str<'a> {}
40/// impl <'a> HashLike<Str<'a>> for String {}
41/// unsafe impl <'a> Send for Str<'a> {}
42/// unsafe impl <'a> Sync for Str<'a> {}
43/// 
44/// let mut hash_map: HashTrieMap<u64, u32, String, String, FnvHasher> = HashTrieMap::new();
45/// let hello = "Hello,";
46/// let world = "world!,";
47/// 
48/// hash_map = hash_map.insert(Str::new(hello), world, false).unwrap().0;
49/// 
50/// // Inserting an already-inserted key returns references to the key and value in the map...
51/// assert!(hash_map.insert(Str::new(hello), "?", false).map(|_| ())
52///     .map_err(|key_value| *key_value.0 == hello && *key_value.1 == world).unwrap_err());
53/// // ... unless you enable replacement.
54/// assert!(hash_map.insert(Str::new(hello), "?", true).is_ok());
55/// 
56/// assert!(hash_map.find(&Str::new(hello)).map(|key_value| *key_value.0 == hello && *key_value.1 == world).unwrap());
57/// 
58/// match hash_map.remove(&Str::new(hello)) {
59///     Ok((mutated, key, value)) => {
60///         // Removing a key returns references to the key and
61///         // value in the set in addition to the mutated map.
62///         println!("Value stored in hash_map: ({}, {})", key, value);
63///         hash_map = mutated;
64///     },
65///     Err(_) => panic!(),
66/// }
67/// ```
68#[derive(Clone, Debug)]
69#[must_use]
70pub struct HashTrieMap <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
71    set: HashTrie<H, F, K, V, M>,
72}
73
74impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> HashTrieMap<H, F, K, V, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
75    /// Get a new, empty HashTrieMap.
76    pub fn new() -> Self {
77        Self {
78            set: HashTrie::<H, F, K, V, M>::new()
79        }
80    }
81
82    /// Get the total number of entries in the map.
83    pub fn size(&self) -> usize {
84        self.set.size()
85    }
86
87    /// Search the HashTrieMap for the given key and return references if found, or `HashTrieError::NotFound` if not found.
88    pub fn find<'a, L: Key + HashLike<K>>(&'a self, key: &L) -> Result<(&'a K, &'a V), HashTrieError> where K: PartialEq<L>, M: HasherBv<H, L> {
89        self.set.find(key)
90    }
91
92    /// Search the HashTrieMap for the spot to insert the key and return both a mutated map and, if applicable, references to the replaced values.
93    /// If found and replacement is disabled, references to the existing values are returned.
94    #[allow(clippy::type_complexity)]
95    pub fn insert<'a, L: Key + HashLike<K> + Into<K>, W: Into<V>>(&'a self, key: L, value: W, replace: bool) -> Result<(Self, *const K, *const V, Option<(&'a K, &'a V)>), (&'a K, &'a V)>
96    where
97        K: HashLike<L>,
98        K: PartialEq<L>,
99        M: HasherBv<H, L>
100    {
101        self.set.insert(key, value, replace).map(|(set, key, value, prev)| (Self {set}, key, value, prev))
102    }
103
104    /// Search the HashTrieMap for the given key to remove and return a mutated map, or `HashTrieError::NotFound` if not found.
105    pub fn remove<'a, L: Key + HashLike<K>>(&'a self, key: &L) -> Result<(Self, &'a K, &'a V), HashTrieError> where K: PartialEq<L>, M: HasherBv<H, L> {
106        self.set.remove(key).map(|(set, key, value)| (Self {set}, key, value))
107    }
108
109    /// Run an operation on each entry in the map.
110    pub fn visit<Op: Clone>(&self, op: Op) where Op: Fn(&K, &V) {
111        self.set.visit(|k,v| op(k, v));
112    }
113
114    /// Run a transform operation on each entry in the map. Returns the transformed map and a reduction of the secondary returns of the transform operations.
115    pub fn transform<ReduceT, ReduceOp, Op>
116        (&self, reduce_op: ReduceOp, op: Op) -> (Self, ReduceT)
117        where
118        Self: Sized,
119        ReduceT: Default,
120        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
121        Op: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone
122    {
123        let (set, reduced) = self.set.transform(reduce_op, |k, v| op(k, v));
124        (Self{set}, reduced)
125    }
126
127    /// Run a transmute operation on each entry in the map. Returns the transmuted map and a reduction of the secondary returns of the transmute operations.
128    pub unsafe fn transmute<S: Key + HashLike<K>, X: Value, ReduceT, ReduceOp, Op>
129        (&self, reduce_op: ReduceOp, op: Op) -> (HashTrieMap<H, F, S, X, M>, ReduceT)
130        where
131        Self: Sized,
132        ReduceT: Default,
133        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
134        Op: Fn(&K, &V) -> MapTransmuteResult<S, X, ReduceT> + Clone,
135        K: HashLike<S>,
136        K: PartialEq<S>,
137        M: HasherBv<H, S>,
138    {
139        let (set, reduced) = self.set.transmute(reduce_op, |k, v| op(k, v));
140        (HashTrieMap{set}, reduced)
141    }
142
143    /// Run a transform operation on each entry or pair of entries in the maps. Returns the transformed map and a reduction of the secondary returns of the transmute operations. Can reuse nodes from either map.
144    pub fn transform_with_transformed<ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
145        (&self, right: &Self, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (Self, ReduceT)
146        where
147        Self: Sized,
148        ReduceT: Default,
149        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
150        BothOp: Fn(&K, &V, &K, &V) -> MapJointTransformResult<V, ReduceT> + Clone,
151        LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
152        RightOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
153    {
154        let (set, reduced) = self.set.transform_with_transformed(&right.set, reduce_op, both_op, left_op, right_op);
155        (HashTrieMap{set}, reduced)
156    }
157
158    /// Run a transform/transmute operation on each entry or pair of entries in the maps. Returns the transmuted map and a reduction of the secondary returns of the transmute operations. Can reuse nodes from the transformed map. Like transform_with_transmuted but enforces identity transformations on keys.
159    pub fn transform_with_transfuted<W: Value, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
160        (&self, right: &HashTrieMap<H, F, K, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (Self, ReduceT)
161        where
162        Self: Sized,
163        ReduceT: Default,
164        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
165        BothOp: Fn(&K, &V, &K, &W) -> MapTransformResult<V, ReduceT> + Clone,
166        LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
167        RightOp: Fn(&K, &W) -> SetTransmuteResult<V, ReduceT> + Clone,
168    {
169        let (set, reduced) = unsafe {
170            self.set.transform_with_transmuted(&right.set, reduce_op, both_op, left_op, |k, w| match right_op(k, w) {
171                SetTransmuteResult::Transmuted(value, reduced) => MapTransmuteResult::Transmuted(k.clone(), value, reduced),
172                SetTransmuteResult::Removed(reduced) => MapTransmuteResult::Removed(reduced),
173            })
174        };
175        (HashTrieMap{set}, reduced)
176    }
177
178    /// Run a transform/transmute operation on each entry or pair of entries in the maps. Returns the transmuted map and a reduction of the secondary returns of the transmute operations. Can reuse nodes from the transformed map.
179    pub unsafe fn transform_with_transmuted<L: Key + HashLike<K>, W: Value, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
180        (&self, right: &HashTrieMap<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (Self, ReduceT)
181        where
182        Self: Sized,
183        ReduceT: Default,
184        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
185        BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<V, ReduceT> + Clone,
186        LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
187        RightOp: Fn(&L, &W) -> MapTransmuteResult<K, V, ReduceT> + Clone,
188        K: HashLike<L>,
189        K: PartialEq<L>,
190        L: HashLike<K>,
191        L: PartialEq<K>,
192        M: HasherBv<H, L>,
193    {
194        let (set, reduced) = self.set.transform_with_transmuted(&right.set, reduce_op, both_op, left_op, right_op);
195        (HashTrieMap{set}, reduced)
196    }
197
198    /// Run a transmute/transform operation on each entry or pair of entries in the maps. Returns the transmuted map and a reduction of the secondary returns of the transmute operations. Can reuse nodes from the transformed map. Like transmute_with_transformed but enforces identity transformations on keys.
199    pub fn transfute_with_transformed<W: Value, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
200        (&self, right: &HashTrieMap<H, F, K, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (HashTrieMap<H, F, K, W, M>, ReduceT)
201        where
202        Self: Sized,
203        ReduceT: Default,
204        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
205        BothOp: Fn(&K, &V, &K, &W) -> MapTransformResult<W, ReduceT> + Clone,
206        LeftOp: Fn(&K, &V) -> SetTransmuteResult<W, ReduceT> + Clone,
207        RightOp: Fn(&K, &W) -> MapTransformResult<W, ReduceT> + Clone,
208    {
209        let (set, reduced) = unsafe {
210            self.set.transmute_with_transformed(&right.set, reduce_op, both_op, |k, v| match left_op(k, v) {
211                SetTransmuteResult::Transmuted(value, reduced) => MapTransmuteResult::Transmuted(k.clone(), value, reduced),
212                SetTransmuteResult::Removed(reduced) => MapTransmuteResult::Removed(reduced),
213            }, right_op)
214        };
215        (HashTrieMap{set}, reduced)
216    }
217
218    /// Run a transmute/transform operation on each entry or pair of entries in the maps. Returns the transmuted map and a reduction of the secondary returns of the transmute operations. Can reuse nodes from the transformed map.
219    pub unsafe fn transmute_with_transformed<L: Key + HashLike<K>, W: Value, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
220        (&self, right: &HashTrieMap<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (HashTrieMap<H, F, L, W, M>, ReduceT)
221        where
222        Self: Sized,
223        ReduceT: Default,
224        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
225        BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<W, ReduceT> + Clone,
226        LeftOp: Fn(&K, &V) -> MapTransmuteResult<L, W, ReduceT> + Clone,
227        RightOp: Fn(&L, &W) -> MapTransformResult<W, ReduceT> + Clone,
228        K: HashLike<L>,
229        K: PartialEq<L>,
230        L: HashLike<K>,
231        L: PartialEq<K>,
232        M: HasherBv<H, L>,
233    {
234        let (set, reduced) = self.set.transmute_with_transformed(&right.set, reduce_op, both_op, left_op, right_op);
235        (HashTrieMap{set}, reduced)
236    }
237
238    /// Run a transmute operation on each entry or pair of entries in the maps. Returns the transmuted map and a reduction of the secondary returns of the transmute operations.
239    pub unsafe fn transmute_with_transmuted<L: Key + HashLike<K>, W: Value, S: Key + HashLike<K>, X: Value, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>
240        (&self, right: &HashTrieMap<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp) -> (HashTrieMap<H, F, S, X, M>, ReduceT)
241        where
242        Self: Sized,
243        ReduceT: Default,
244        ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
245        BothOp: Fn(&K, &V, &L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
246        LeftOp: Fn(&K, &V) -> MapTransmuteResult<S, X, ReduceT> + Clone,
247        RightOp: Fn(&L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
248        K: HashLike<L>,
249        K: PartialEq<L>,
250        K: HashLike<S>,
251        K: PartialEq<S>,
252        L: HashLike<K>,
253        L: PartialEq<K>,
254        L: HashLike<S>,
255        L: PartialEq<S>,
256        M: HasherBv<H, L>,
257        M: HasherBv<H, S>,
258    {
259        let (set, reduced) = self.set.transmute_with_transmuted(&right.set, reduce_op, both_op, left_op, right_op);
260        (HashTrieMap{set}, reduced)
261    }
262
263}
264
265impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> Default for HashTrieMap<H, F, K, V, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
266    fn default() -> Self {
267        Self::new()
268    }
269}
270
271impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> Eq for HashTrieMap<H, F, K, V, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {}
272
273impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> PartialEq for HashTrieMap<H, F, K, V, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
274    fn eq(&self, other: &Self) -> bool {
275        self.set == other.set
276    }
277}
278
279#[cfg(test)]
280mod tests {
281    use crate::*;
282    use rand::Rng;
283    
284    #[test]
285    fn map_transform() {
286        let mut map = DefaultHashTrieMap::<i32, i32>::new();
287        let mut squared = DefaultHashTrieMap::<i32, i32>::new();
288
289        for i in 1..101 {
290            map = map.insert(i, i, false).unwrap().0;
291            squared = squared.insert(i, i * i, false).unwrap().0;
292        }
293
294        let removed = map.transform(|_,_| (), |_,_| MapTransformResult::Removed(()));
295        let tsquared = map.transform(|_,_| (), |_,v| MapTransformResult::Transformed(v * v, ()));
296
297        assert_eq!(removed.0.size(), 0);
298
299        for i in 1..101 {
300            map.find(&i).unwrap();
301            assert_eq!(i * i, *squared.find(&i).unwrap().1);
302            assert_eq!(i * i, *tsquared.0.find(&i).unwrap().1);
303        }
304    }
305    
306    #[test]
307    fn map_transmute() {
308        let mut map = DefaultHashTrieMap::<i32, i32>::new();
309        let mut squared = DefaultHashTrieMap::<i32, i32>::new();
310
311        for i in 1..101 {
312            map = map.insert(i, i, false).unwrap().0;
313            squared = squared.insert(i, i * i, false).unwrap().0;
314        }
315
316        let removed: (DefaultHashTrieMap::<i32, i32>, ()) = unsafe { map.transmute(|_,_| (), |_,_| MapTransmuteResult::Removed(())) };
317        let tsquared = unsafe { map.transmute(|_,_| (), |k,v| MapTransmuteResult::Transmuted(*k, v * v, ())) };
318
319        assert_eq!(removed.0.size(), 0);
320
321        for i in 1..101 {
322            map.find(&i).unwrap();
323            assert_eq!(i * i, *squared.find(&i).unwrap().1);
324            assert_eq!(i * i, *tsquared.0.find(&i).unwrap().1);
325        }
326    }
327    
328    #[test]
329    fn map_joint_transformations() {
330        let mut mapa = DefaultHashTrieMap::<i32, i32>::new();
331        let mut mapb = DefaultHashTrieMap::<i32, i32>::new();
332
333        let mut rng = rand::thread_rng();
334        let a = (0..25000).map(|_| rng.gen_range(0..100000)).collect::<Vec<i32>>();
335        let b = (0..25000).map(|_| rng.gen_range(0..100000)).collect::<Vec<i32>>();
336        for i in a {
337            mapa = mapa.insert(i, i, true).unwrap().0;
338        }
339        for i in b {
340            mapb = mapb.insert(i, i, true).unwrap().0;
341        }
342
343        let ff = mapa.transform_with_transformed(&mapb, |l,r| -> i32 {l.wrapping_add(*r)},
344            |_,v,_,w| MapJointTransformResult::Removed(v.wrapping_mul(*w)), |_,v| MapTransformResult::Unchanged(*v), |_,v| MapTransformResult::Unchanged(*v));
345        let fm = unsafe { mapa.transform_with_transmuted(&mapb, |l,r| -> i32 {l.wrapping_add(*r)},
346            |_,v,_,w| MapTransformResult::Removed(v.wrapping_mul(*w)), |_,v| MapTransformResult::Unchanged(*v), |k,v| MapTransmuteResult::Transmuted(*k, *v, *v)) };
347        let mf = unsafe { mapa.transmute_with_transformed(&mapb, |l,r| -> i32 {l.wrapping_add(*r)},
348            |_,v,_,w| MapTransformResult::Removed(v.wrapping_mul(*w)), |k,v| MapTransmuteResult::Transmuted(*k, *v, *v), |_,v| MapTransformResult::Unchanged(*v)) };
349        let mm = unsafe { mapa.transmute_with_transmuted(&mapb, |l,r| -> i32 {l.wrapping_add(*r)},
350            |_,v,_,w| MapTransmuteResult::Removed(v.wrapping_mul(*w)), |k,v| MapTransmuteResult::Transmuted(*k, *v, *v), |k,v| MapTransmuteResult::Transmuted(*k, *v, *v)) };
351
352        assert_eq!(ff.1, fm.1);
353        assert_eq!(ff.1, mf.1);
354        assert_eq!(ff.1, mm.1);
355
356        let ffx = ff.0.transform(|l,r| -> i32 {l.wrapping_add(*r)}, |_,v| MapTransformResult::Removed(*v));
357        let fmx = fm.0.transform(|l,r| -> i32 {l.wrapping_add(*r)}, |_,v| MapTransformResult::Removed(*v));
358        let mfx = mf.0.transform(|l,r| -> i32 {l.wrapping_add(*r)}, |_,v| MapTransformResult::Removed(*v));
359        let mmx = mm.0.transform(|l,r| -> i32 {l.wrapping_add(*r)}, |_,v| MapTransformResult::Removed(*v));
360
361        assert_eq!(ffx.1, fmx.1);
362        assert_eq!(ffx.1, mfx.1);
363        assert_eq!(ffx.1, mmx.1);
364    }
365
366}
hash_trie/map.rs

hash_trie/
map.rs
