hamst/
lib.rs

1//! HAMST - Hash Array Mapped Shareable Tries
2//!
3//! Each key is hashed and store related to the hash value.
4//!
5//! When cloning the data structure, the nodes are shared, so that the operation is
6//! is really cheap. When modifying the data structure, after an explicit thawing,
7//! the mutable structure share the unmodified node and only nodes requiring modification
8//! will be re-created from the node onwards to the leaf.
9
10#![allow(dead_code)]
11#[cfg(test)]
12extern crate quickcheck;
13#[cfg(test)]
14#[macro_use(quickcheck)]
15extern crate quickcheck_macros;
16
17mod bitmap;
18mod collision;
19mod hamt;
20mod hash;
21mod immutable;
22mod mutable;
23mod node;
24
25pub use hamt::*;
26
27#[cfg(test)]
28mod tests {
29    use super::*;
30
31    use quickcheck::{Arbitrary, Gen};
32
33    use std::cmp;
34    use std::collections::hash_map::DefaultHasher;
35    use std::collections::BTreeMap;
36    use std::hash::Hash;
37
38    #[derive(Debug, Clone)]
39    enum PlanOperation<K, V> {
40        Insert(K, V),
41        DeleteOneMatching(usize),
42        DeleteOne(usize),
43        Update(usize),
44        UpdateRemoval(usize),
45        Replace(usize, V),
46        ReplaceWith(usize),
47    }
48
49    #[derive(Debug, Clone)]
50    struct Plan<K, V>(Vec<PlanOperation<K, V>>);
51
52    const SIZE_LIMIT: usize = 5120;
53
54    impl<K: Arbitrary + Clone + Send, V: Arbitrary + Clone + Send> Arbitrary for Plan<K, V> {
55        fn arbitrary<G: Gen>(g: &mut G) -> Plan<K, V> {
56            let nb_ops = 1000 + cmp::min(SIZE_LIMIT, Arbitrary::arbitrary(g));
57            let mut v = Vec::new();
58            for _ in 0..nb_ops {
59                let op_nb: u32 = Arbitrary::arbitrary(g);
60                let op = match op_nb % 7u32 {
61                    0 => PlanOperation::Insert(Arbitrary::arbitrary(g), Arbitrary::arbitrary(g)),
62                    1 => PlanOperation::DeleteOne(Arbitrary::arbitrary(g)),
63                    2 => PlanOperation::DeleteOneMatching(Arbitrary::arbitrary(g)),
64                    3 => PlanOperation::Update(Arbitrary::arbitrary(g)),
65                    4 => PlanOperation::UpdateRemoval(Arbitrary::arbitrary(g)),
66                    5 => PlanOperation::Replace(Arbitrary::arbitrary(g), Arbitrary::arbitrary(g)),
67                    6 => PlanOperation::ReplaceWith(Arbitrary::arbitrary(g)),
68                    _ => panic!("test internal error: quickcheck tag code is invalid"),
69                };
70                v.push(op)
71            }
72            Plan(v)
73        }
74    }
75
76    #[test]
77    fn insert_lookup() {
78        let h: Hamt<String, u32, DefaultHasher> = Hamt::new();
79
80        let k1 = "ABC".to_string();
81        let v1 = 12u32;
82
83        let k2 = "DEF".to_string();
84        let v2 = 24u32;
85
86        let k3 = "XYZ".to_string();
87        let v3 = 42u32;
88
89        let h1 = h.mutate_freeze(|hm| hm.insert(k1.clone(), v1)).unwrap();
90        let h2 = h.mutate_freeze(|hm| hm.insert(k2.clone(), v2)).unwrap();
91
92        assert_eq!(h1.lookup(&k1), Some(&v1));
93        assert_eq!(h2.lookup(&k2), Some(&v2));
94        assert_eq!(h1.lookup(&k2), None);
95        assert_eq!(h2.lookup(&k1), None);
96
97        let h3 = h1.mutate_freeze(|hm| hm.insert(k3.clone(), v3)).unwrap();
98
99        assert_eq!(h1.lookup(&k3), None);
100        assert_eq!(h2.lookup(&k3), None);
101
102        assert_eq!(h3.lookup(&k1), Some(&v1));
103        assert_eq!(h3.lookup(&k2), None);
104        assert_eq!(h3.lookup(&k3), Some(&v3));
105
106        let (h4, oldk1) = h3.mutate_freeze_ret(|hm| hm.replace(&k1, v3)).unwrap();
107        assert_eq!(oldk1, v1);
108        assert_eq!(h4.lookup(&k1), Some(&v3));
109    }
110
111    #[test]
112    fn dup_insert() {
113        let mut h: Hamt<&String, u32, DefaultHasher> = Hamt::new();
114        let dkey = "A".to_string();
115        h = h.mutate_freeze(|hm| hm.insert(&dkey, 1)).unwrap();
116        assert_eq!(
117            h.mutate_freeze(|hm| hm.insert(&dkey, 2)).and(Ok(())),
118            Err(InsertError::EntryExists)
119        )
120    }
121
122    #[test]
123    fn empty_size() {
124        let h: Hamt<&String, u32, DefaultHasher> = Hamt::new();
125        assert_eq!(h.size(), 0)
126    }
127
128    #[test]
129    fn delete_key_not_exist() {
130        let mut h: Hamt<&String, u32, DefaultHasher> = Hamt::new();
131        let dkey = "A".to_string();
132        h = h.mutate_freeze(|hm| hm.insert(&dkey, 1)).unwrap();
133        assert_eq!(
134            h.mutate_freeze(|hm| hm.remove_match(&&dkey, &2))
135                .and(Ok(())),
136            Err(RemoveError::ValueNotMatching)
137        )
138    }
139
140    #[test]
141    fn delete_value_not_match() {
142        let mut h: Hamt<&String, u32, DefaultHasher> = Hamt::new();
143        let dkey = "A".to_string();
144        h = h.mutate_freeze(|hm| hm.insert(&dkey, 1)).unwrap();
145        assert_eq!(
146            h.mutate_freeze(|hm| hm.remove_match(&&dkey, &2))
147                .and(Ok(())),
148            Err(RemoveError::ValueNotMatching)
149        )
150    }
151
152    #[allow(clippy::trivially_copy_pass_by_ref)]
153    fn next_u32(x: &u32) -> Result<Option<u32>, ()> {
154        Ok(Some(*x + 1))
155    }
156
157    #[test]
158    fn delete() {
159        let mut h: Hamt<String, u32, DefaultHasher> = Hamt::new();
160
161        let keys = [
162            ("KEY1", 10000u32),
163            ("KEY2", 20000),
164            ("KEY3", 30000),
165            ("KEY4", 40000),
166            ("KEY5", 50000),
167            ("KEY6", 60000),
168            ("KEY7", 70000),
169            ("KEY8", 80000),
170            ("KEY9", 10000),
171            ("KEY10", 20000),
172            ("KEY11", 30000),
173            ("KEY12", 40000),
174            ("KEY13", 50000),
175            ("KEY14", 60000),
176            ("KEY15", 70000),
177            ("KEY16", 80000),
178        ];
179
180        let k1 = "ABC".to_string();
181        let v1 = 12u32;
182
183        let k2 = "DEF".to_string();
184        let v2 = 24u32;
185
186        let k3 = "XYZ".to_string();
187        let v3 = 42u32;
188
189        h = h
190            .mutate_freeze::<InsertError, _>(|hm| {
191                for (k, v) in keys.iter() {
192                    hm.insert((*k).to_owned(), *v)?;
193                }
194                Ok(())
195            })
196            .unwrap();
197
198        h = h
199            .mutate_freeze(|hm| {
200                hm.insert(k1.clone(), v1)?;
201                hm.insert(k2.clone(), v2)?;
202                hm.insert(k3.clone(), v3)
203            })
204            .unwrap();
205
206        let h2 = h
207            .mutate_freeze(|hm| hm.remove_match(&k1, &v1))
208            .expect("cannot remove from already inserted");
209
210        assert_eq!(h.size(), keys.len() + 3);
211        assert_eq!(h2.size(), keys.len() + 2);
212
213        assert_eq!(h.lookup(&k1), Some(&v1));
214        assert_eq!(h2.lookup(&k1), None);
215
216        h = h
217            .mutate_freeze(|hm| {
218                hm.remove_match(&k2, &v2)?;
219                hm.remove_match(&k3, &v3)
220            })
221            .unwrap();
222
223        assert_eq!(
224            h.mutate_freeze(|hm| hm.remove_match(&k3, &v3)).and(Ok(())),
225            Err(RemoveError::KeyNotFound),
226        );
227        assert_eq!(
228            h.mutate_freeze(|hm| hm.remove_match(&k1, &v2)).and(Ok(())),
229            Err(RemoveError::ValueNotMatching),
230        );
231        assert_eq!(
232            h2.mutate_freeze(|hm| hm.insert(k2, v3)).and(Ok(())),
233            Err(InsertError::EntryExists)
234        );
235
236        assert_eq!(
237            h2.mutate_freeze(|hm| hm.update(&"ZZZ".to_string(), next_u32))
238                .and(Ok(())),
239            Err(UpdateError::KeyNotFound)
240        );
241
242        assert_eq!(h.size(), keys.len() + 1);
243        assert_eq!(h2.size(), keys.len() + 2);
244    }
245
246    //use hash::HashedKey;
247    //use std::marker::PhantomData;
248
249    /* commented -- as this doesn't do what it says on the tin.
250    it doesn't test for h collision, but node splitting
251
252    #[test]
253    fn collision() {
254        let k0 = "keyx".to_string();
255        let h1 = HashedKey::compute(PhantomData::<DefaultHasher>, &k0);
256        let l = h1.level_index(0);
257        let mut found = None;
258        for i in 0..10000 {
259            let x = format!("key{}", i);
260            let h2 = HashedKey::compute(PhantomData::<DefaultHasher>, &x);
261            if h1 == h2 {
262            //if h2.level_index(0) == l {
263                found = Some(x.clone());
264                break;
265            }
266        }
267
268        match found {
269            None => assert!(false),
270            Some(x) => {
271                let mut h: Hamt<DefaultHasher, String, u32> = Hamt::new();
272                println!("k0: {}", k0);
273                h = h.insert(k0.clone(), 1u32).unwrap();
274                println!("x: {}", x);
275                h = h.insert(x.clone(), 2u32).unwrap();
276                assert_eq!(h.size(), 2);
277                assert_eq!(h.lookup(&k0), Some(&1u32));
278                assert_eq!(h.lookup(&x), Some(&2u32));
279
280                let h2 = h.remove_match(&x, &2u32).unwrap();
281                assert_eq!(h2.lookup(&k0), Some(&1u32));
282                assert_eq!(h2.size(), 1);
283
284                let h3 = h.remove_match(&k0, &1u32).unwrap();
285                assert_eq!(h3.lookup(&x), Some(&2u32));
286                assert_eq!(h3.size(), 1);
287            }
288        }
289    }
290    */
291
292    fn property_btreemap_eq<A: Eq + Ord + Hash, B: PartialEq>(
293        reference: &BTreeMap<A, B>,
294        h: &Hamt<A, B, DefaultHasher>,
295    ) -> bool {
296        // using the btreemap reference as starting point
297        for (k, v) in reference.iter() {
298            if h.lookup(&k) != Some(v) {
299                return false;
300            }
301        }
302        // then asking the hamt for any spurious values
303        for (k, v) in h.iter() {
304            if reference.get(&k) != Some(v) {
305                return false;
306            }
307        }
308        true
309    }
310
311    #[quickcheck]
312    fn insert_equivalent(xs: Vec<(String, u32)>) -> bool {
313        let mut reference = BTreeMap::new();
314        let mut h: HamtMut<String, u32, DefaultHasher> = HamtMut::new();
315        for (k, v) in xs.iter() {
316            if reference.get(k).is_some() {
317                continue;
318            }
319            reference.insert(k.clone(), *v);
320            h.insert(k.clone(), *v).expect("insert error");
321        }
322        property_btreemap_eq(&reference, &h.freeze())
323    }
324
325    #[derive(Clone, Debug, PartialEq, Eq)]
326    pub struct LargeVec<A>(Vec<A>);
327
328    const LARGE_MIN: usize = 1000;
329    const LARGE_DIFF: usize = 1000;
330
331    impl<A: Arbitrary + Clone + PartialEq + Send + 'static> Arbitrary for LargeVec<A> {
332        fn arbitrary<G: Gen>(g: &mut G) -> Self {
333            let nb = LARGE_MIN + (usize::arbitrary(g) % LARGE_DIFF);
334            let mut v = Vec::with_capacity(nb);
335            for _ in 0..nb {
336                v.push(Arbitrary::arbitrary(g))
337            }
338            LargeVec(v)
339        }
340    }
341
342    #[quickcheck]
343    fn large_insert_equivalent(xs: LargeVec<(String, u32)>) -> bool {
344        let xs = xs.0;
345        let mut reference = BTreeMap::new();
346        let mut h: HamtMut<String, u32, DefaultHasher> = HamtMut::new();
347        for (k, v) in xs.iter() {
348            if reference.get(k).is_some() {
349                continue;
350            }
351            reference.insert(k.clone(), *v);
352            h.insert(k.clone(), *v).expect("insert error");
353        }
354
355        property_btreemap_eq(&reference, &h.freeze())
356    }
357
358    fn get_key_nth<K: Clone, V>(b: &BTreeMap<K, V>, n: usize) -> Option<K> {
359        let keys_nb = b.len();
360        if keys_nb == 0 {
361            return None;
362        }
363        let mut keys = b.keys();
364        Some(keys.nth(n % keys_nb).unwrap().clone())
365    }
366
367    fn arbitrary_hamt_and_btree<K, V, F, G>(
368        xs: Plan<K, V>,
369        update_f: F,
370        replace_with_f: G,
371    ) -> (Hamt<K, V, DefaultHasher>, BTreeMap<K, V>)
372    where
373        K: Hash + Clone + Eq + Ord + Sync,
374        V: Clone + PartialEq + Sync,
375        F: Fn(&V) -> Result<Option<V>, ()> + Copy,
376        G: Fn(&V) -> V + Copy,
377    {
378        let mut reference = BTreeMap::new();
379        let mut h: HamtMut<K, V, DefaultHasher> = HamtMut::new();
380        //println!("plan {} operations", xs.0.len());
381        for op in xs.0.iter() {
382            match op {
383                PlanOperation::Insert(k, v) => {
384                    if reference.get(k).is_some() {
385                        continue;
386                    }
387                    reference.insert(k.clone(), v.clone());
388                    h.insert(k.clone(), v.clone()).expect("insert error")
389                }
390                PlanOperation::DeleteOne(r) => match get_key_nth(&reference, *r) {
391                    None => continue,
392                    Some(k) => {
393                        reference.remove(&k);
394                        h.remove(&k).expect("remove error");
395                    }
396                },
397                PlanOperation::DeleteOneMatching(r) => match get_key_nth(&reference, *r) {
398                    None => continue,
399                    Some(k) => {
400                        let v = reference.get(&k).unwrap().clone();
401                        reference.remove(&k);
402                        h.remove_match(&k, &v).expect("remove match error");
403                    }
404                },
405                PlanOperation::Replace(r, newv) => match get_key_nth(&reference, *r) {
406                    None => continue,
407                    Some(k) => {
408                        let v = reference.get_mut(&k).unwrap();
409                        *v = newv.clone();
410
411                        h.replace(&k, newv.clone()).expect("replace error");
412                    }
413                },
414                PlanOperation::ReplaceWith(r) => match get_key_nth(&reference, *r) {
415                    None => continue,
416                    Some(k) => {
417                        let v = reference.get_mut(&k).unwrap();
418                        *v = replace_with_f(v);
419
420                        h.replace_with(&k, replace_with_f)
421                            .expect("replace with error");
422                    }
423                },
424                PlanOperation::Update(r) => match get_key_nth(&reference, *r) {
425                    None => continue,
426                    Some(k) => {
427                        let v = reference.get_mut(&k).unwrap();
428                        match update_f(v).unwrap() {
429                            None => {
430                                reference.remove(&k);
431                            }
432                            Some(newv) => *v = newv,
433                        }
434
435                        h.update(&k, update_f).expect("update error");
436                    }
437                },
438                PlanOperation::UpdateRemoval(r) => match get_key_nth(&reference, *r) {
439                    None => continue,
440                    Some(k) => {
441                        reference.remove(&k);
442                        h.update::<_, ()>(&k, |_| Ok(None))
443                            .expect("update removal error");
444                    }
445                },
446            }
447        }
448        (h.freeze(), reference)
449    }
450
451    #[quickcheck]
452    fn plan_equivalent(xs: Plan<String, u32>) -> bool {
453        let (h, reference) = arbitrary_hamt_and_btree(xs, next_u32, |v| v.wrapping_mul(2));
454        property_btreemap_eq(&reference, &h)
455    }
456
457    #[quickcheck]
458    fn iter_equivalent(xs: Plan<String, u32>) -> bool {
459        use std::iter::FromIterator;
460        let (h, reference) = arbitrary_hamt_and_btree(xs, next_u32, |v| v.wrapping_mul(2));
461        let after_iter = BTreeMap::from_iter(h.iter().map(|(k, v)| (k.clone(), *v)));
462        reference == after_iter
463    }
464}
hamst/lib.rs

hamst/
lib.rs
