hamt_sync/
map.rs

1use std::hash::Hash;
2
3use hamt::{Hamt, HamtIterator};
4use node::Node;
5
6/// Map data structure of HAMT.
7///
8/// Note that every method does not modify the original map but creates a new
9/// one if necessary.
10#[derive(Clone, Debug, Eq, Hash, PartialEq)]
11pub struct Map<K, V> {
12    size: usize,
13    hamt: Hamt<K, V>,
14}
15
16impl<K: Clone + Hash + PartialEq, V: Clone> Map<K, V> {
17    /// Creates a new map.
18    pub fn new() -> Self {
19        Map {
20            size: 0,
21            hamt: Hamt::new(0),
22        }
23    }
24
25    /// Inserts a key-value pair into a map.
26    pub fn insert(&self, k: K, v: V) -> Self {
27        let (h, b) = self.hamt.insert(k, v);
28
29        Map {
30            size: self.size + (b as usize),
31            hamt: h,
32        }
33    }
34
35    /// Deletes a key and its corresponding value from a map.
36    pub fn delete(&self, k: &K) -> Option<Self> {
37        self.hamt.delete(k).map(|h| Map {
38            size: self.size - 1,
39            hamt: h,
40        })
41    }
42
43    /// Finds a key and its corresponding value in a map.
44    pub fn find(&self, k: &K) -> Option<&V> {
45        self.hamt.find(k)
46    }
47
48    /// Removes the first element in a map and returns a new map containing the
49    /// rest of elements.
50    pub fn first_rest(&self) -> Option<(&K, &V, Self)> {
51        self.hamt.first_rest().map(|(k, v, h)| {
52            (
53                k,
54                v,
55                Map {
56                    size: self.size - 1,
57                    hamt: h,
58                },
59            )
60        })
61    }
62
63    /// Returns a size of a map.
64    pub fn size(&self) -> usize {
65        self.size
66    }
67}
68
69pub struct MapIterator<'a, K: 'a, V: 'a>(HamtIterator<'a, K, V>);
70
71impl<'a, K, V> Iterator for MapIterator<'a, K, V> {
72    type Item = (&'a K, &'a V);
73
74    fn next(&mut self) -> Option<Self::Item> {
75        self.0.next()
76    }
77}
78
79impl<'a, K, V> IntoIterator for &'a Map<K, V> {
80    type Item = (&'a K, &'a V);
81    type IntoIter = MapIterator<'a, K, V>;
82
83    fn into_iter(self) -> Self::IntoIter {
84        MapIterator(self.hamt.into_iter())
85    }
86}
87
88#[cfg(test)]
89mod test {
90    use std::thread::spawn;
91
92    use rand::{random, thread_rng, Rng};
93    use test::Bencher;
94
95    use super::Map;
96
97    const NUM_ITERATIONS: usize = 1 << 12;
98
99    #[test]
100    fn new() {
101        Map::new() as Map<usize, usize>;
102    }
103
104    #[test]
105    fn insert() {
106        let h = Map::new();
107
108        assert_eq!(h.size(), 0);
109        assert_eq!(h.insert(0, 0).size(), 1);
110        assert_eq!(h.insert(0, 0).insert(0, 0).size(), 1);
111        assert_eq!(h.insert(0, 0).insert(1, 0).size(), 2);
112    }
113
114    #[test]
115    fn insert_many_in_order() {
116        let mut h = Map::new();
117
118        for i in 0..NUM_ITERATIONS {
119            h = h.insert(i, i);
120            assert_eq!(h.size(), i + 1);
121        }
122    }
123
124    #[test]
125    fn insert_many_at_random() {
126        let mut h: Map<usize, usize> = Map::new();
127
128        for i in 0..NUM_ITERATIONS {
129            let k = random();
130            h = h.insert(k, k);
131            assert_eq!(h.size(), i + 1);
132        }
133    }
134
135    #[test]
136    fn delete() {
137        let h = Map::new();
138
139        assert_eq!(h.insert(0, 0).delete(&0), Some(h.clone()));
140        assert_eq!(h.insert(0, 0).delete(&1), None);
141        assert_eq!(h.insert(0, 0).insert(1, 0).delete(&0), Some(h.insert(1, 0)));
142        assert_eq!(h.insert(0, 0).insert(1, 0).delete(&1), Some(h.insert(0, 0)));
143        assert_eq!(h.insert(0, 0).insert(1, 0).delete(&2), None);
144    }
145
146    #[test]
147    fn insert_delete_many() {
148        let mut h: Map<i16, i16> = Map::new();
149
150        for _ in 0..NUM_ITERATIONS {
151            let k = random();
152            let s = h.size();
153            let found = h.find(&k).is_some();
154
155            if random() {
156                h = h.insert(k, k);
157
158                assert_eq!(h.size(), if found { s } else { s + 1 });
159                assert_eq!(h.find(&k), Some(&k));
160            } else {
161                h = h.delete(&k).unwrap_or(h);
162
163                assert_eq!(h.size(), if found { s - 1 } else { s });
164                assert_eq!(h.find(&k), None);
165            }
166        }
167    }
168
169    #[test]
170    fn find() {
171        let h = Map::new();
172
173        assert_eq!(h.insert(0, 0).find(&0), Some(&0));
174        assert_eq!(h.insert(0, 0).find(&1), None);
175        assert_eq!(h.insert(1, 0).find(&0), None);
176        assert_eq!(h.insert(1, 0).find(&1), Some(&0));
177        assert_eq!(h.insert(0, 0).insert(1, 0).find(&0), Some(&0));
178        assert_eq!(h.insert(0, 0).insert(1, 0).find(&1), Some(&0));
179        assert_eq!(h.insert(0, 0).insert(1, 0).find(&2), None);
180    }
181
182    #[test]
183    fn first_rest() {
184        let mut h: Map<i16, i16> = Map::new();
185
186        for _ in 0..NUM_ITERATIONS {
187            h = h.insert(random(), 0);
188        }
189
190        for _ in 0..h.size() {
191            let new: Map<i16, i16>;
192
193            {
194                let (f, _, r) = h.first_rest().unwrap();
195
196                assert_eq!(r.size(), h.size() - 1);
197                assert_eq!(r.find(f), None);
198
199                new = r;
200            }
201
202            h = new;
203        }
204
205        assert_eq!(h, Map::new());
206    }
207
208    #[test]
209    fn equality() {
210        for _ in 0..8 {
211            let mut hs: [Map<i16, i16>; 2] = [Map::new(), Map::new()];
212            let mut is: Vec<i16> = (0..NUM_ITERATIONS).map(|_| random()).collect();
213            let mut ds: Vec<i16> = (0..NUM_ITERATIONS).map(|_| random()).collect();
214
215            for h in hs.iter_mut() {
216                thread_rng().shuffle(&mut is);
217                thread_rng().shuffle(&mut ds);
218
219                for i in &is {
220                    *h = h.insert(*i, *i);
221                }
222
223                for d in &ds {
224                    *h = h.delete(d).unwrap_or(h.clone());
225                }
226            }
227
228            assert_eq!(hs[0], hs[1]);
229        }
230    }
231
232    #[test]
233    fn send_and_sync() {
234        let m: Map<usize, usize> = Map::new();
235        spawn(move || m);
236        let m: Map<String, String> = Map::new();
237        spawn(move || m);
238    }
239
240    fn keys() -> Vec<i16> {
241        (0..1000).collect()
242    }
243
244    #[bench]
245    fn bench_insert_1000(b: &mut Bencher) {
246        let ks = keys();
247
248        b.iter(|| {
249            let mut h = Map::new();
250
251            for k in &ks {
252                h = h.insert(k, k);
253            }
254        });
255    }
256
257    #[bench]
258    fn bench_find_1000(b: &mut Bencher) {
259        let ks = keys();
260        let mut h = Map::new();
261
262        for k in &ks {
263            h = h.insert(k, k);
264        }
265
266        b.iter(|| {
267            for k in &ks {
268                h.find(&k);
269            }
270        });
271    }
272}
hamt_sync/map.rs

hamt_sync/
map.rs
