concread/internals/hashmap/
iter.rs

1//! Iterators for the map.
2
3// Iterators for the bptree
4use super::node::{Branch, Leaf, Meta, Node};
5use std::collections::VecDeque;
6use std::fmt::Debug;
7use std::hash::Hash;
8use std::marker::PhantomData;
9
10pub(crate) struct LeafIter<'a, K, V>
11where
12    K: Hash + Eq + Clone + Debug,
13    V: Clone,
14{
15    length: Option<usize>,
16    // idx: usize,
17    stack: VecDeque<(*mut Node<K, V>, usize)>,
18    phantom_k: PhantomData<&'a K>,
19    phantom_v: PhantomData<&'a V>,
20}
21
22impl<K: Clone + Hash + Eq + Debug, V: Clone> LeafIter<'_, K, V> {
23    pub(crate) fn new(root: *mut Node<K, V>, size_hint: bool) -> Self {
24        let length = if size_hint {
25            Some(unsafe { (*root).leaf_count() })
26        } else {
27            None
28        };
29
30        // We probably need to position the VecDeque here.
31        let mut stack = VecDeque::new();
32
33        let mut work_node = root;
34        loop {
35            stack.push_back((work_node, 0));
36            if self_meta!(work_node).is_leaf() {
37                break;
38            } else {
39                work_node = branch_ref!(work_node, K, V).get_idx_unchecked(0);
40            }
41        }
42
43        LeafIter {
44            length,
45            // idx: 0,
46            stack,
47            phantom_k: PhantomData,
48            phantom_v: PhantomData,
49        }
50    }
51
52    #[cfg(test)]
53    pub(crate) fn new_base() -> Self {
54        LeafIter {
55            length: None,
56            // idx: 0,
57            stack: VecDeque::new(),
58            phantom_k: PhantomData,
59            phantom_v: PhantomData,
60        }
61    }
62
63    pub(crate) fn stack_position(&mut self, idx: usize) {
64        // Get the current branch, it must the the back.
65        if let Some((bref, bpidx)) = self.stack.back() {
66            let wbranch = branch_ref!(*bref, K, V);
67            if let Some(node) = wbranch.get_idx_checked(idx) {
68                // Insert as much as possible now. First insert
69                // our current idx, then all the 0, idxs.
70                let mut work_node = node;
71                let mut work_idx = idx;
72                loop {
73                    self.stack.push_back((work_node, work_idx));
74                    if self_meta!(work_node).is_leaf() {
75                        break;
76                    } else {
77                        work_idx = 0;
78                        work_node = branch_ref!(work_node, K, V).get_idx_unchecked(work_idx);
79                    }
80                }
81            } else {
82                // Unwind further.
83                let bpidx = *bpidx + 1;
84                let _ = self.stack.pop_back();
85                self.stack_position(bpidx)
86            }
87        }
88        // Must have been none, so we are exhausted. This means
89        // the stack is empty, so return.
90    }
91
92    /*
93    fn peek(&mut self) -> Option<&Leaf<K, V>> {
94        // I have no idea how peekable works, yolo.
95        self.stack.back().map(|t| t.0.as_leaf())
96    }
97    */
98}
99
100impl<'a, K: Clone + Hash + Eq + Debug, V: Clone> Iterator for LeafIter<'a, K, V> {
101    type Item = &'a Leaf<K, V>;
102
103    fn next(&mut self) -> Option<Self::Item> {
104        // base case is the vecdeque is empty
105        let (leafref, parent_idx) = self.stack.pop_back()?;
106
107        // Setup the veqdeque for the next iteration.
108        self.stack_position(parent_idx + 1);
109
110        // Return the leaf as we found at the start, regardless of the
111        // stack operations.
112        Some(leaf_ref!(leafref, K, V))
113    }
114
115    fn size_hint(&self) -> (usize, Option<usize>) {
116        match self.length {
117            Some(l) => (l, Some(l)),
118            // We aren't (shouldn't) be estimating
119            None => (0, None),
120        }
121    }
122}
123
124/// Iterator over references to Key Value pairs stored in the map.
125pub struct Iter<'a, K, V>
126where
127    K: Hash + Eq + Clone + Debug,
128    V: Clone,
129{
130    length: usize,
131    slot_idx: usize,
132    bk_idx: usize,
133    curleaf: Option<&'a Leaf<K, V>>,
134    leafiter: LeafIter<'a, K, V>,
135}
136
137impl<K: Clone + Hash + Eq + Debug, V: Clone> Iter<'_, K, V> {
138    pub(crate) fn new(root: *mut Node<K, V>, length: usize) -> Self {
139        let mut liter = LeafIter::new(root, false);
140        let leaf = liter.next();
141        // We probably need to position the VecDeque here.
142        Iter {
143            length,
144            slot_idx: 0,
145            bk_idx: 0,
146            curleaf: leaf,
147            leafiter: liter,
148        }
149    }
150}
151
152impl<'a, K: Clone + Hash + Eq + Debug, V: Clone> Iterator for Iter<'a, K, V> {
153    type Item = (&'a K, &'a V);
154
155    /// Yield the next key value reference, or `None` if exhausted.
156    fn next(&mut self) -> Option<Self::Item> {
157        if let Some(leaf) = self.curleaf {
158            if let Some(r) = leaf.get_kv_idx_checked(self.slot_idx, self.bk_idx) {
159                self.bk_idx += 1;
160                Some(r)
161            } else {
162                // Are we partway in a bucket?
163                if self.bk_idx > 0 {
164                    // It's probably ended, next slot.
165                    self.slot_idx += 1;
166                    self.bk_idx = 0;
167                    self.next()
168                } else {
169                    // We've exhasuted the slots sink bk_idx == 0 was empty.
170                    self.curleaf = self.leafiter.next();
171                    self.slot_idx = 0;
172                    self.bk_idx = 0;
173                    self.next()
174                }
175            }
176        } else {
177            None
178        }
179    }
180
181    /// Provide a hint as to the number of items this iterator will yield.
182    fn size_hint(&self) -> (usize, Option<usize>) {
183        (self.length, Some(self.length))
184    }
185}
186
187/// Iterator over references to Keys stored in the map.
188pub struct KeyIter<'a, K, V>
189where
190    K: Hash + Eq + Clone + Debug,
191    V: Clone,
192{
193    iter: Iter<'a, K, V>,
194}
195
196impl<'a, K: Clone + Hash + Eq + Debug, V: Clone> KeyIter<'a, K, V> {
197    pub(crate) fn new(root: *mut Node<K, V>, length: usize) -> Self {
198        KeyIter {
199            iter: Iter::new(root, length),
200        }
201    }
202}
203
204impl<'a, K: Clone + Hash + Eq + Debug, V: Clone> Iterator for KeyIter<'a, K, V> {
205    type Item = &'a K;
206
207    /// Yield the next key value reference, or `None` if exhausted.
208    fn next(&mut self) -> Option<Self::Item> {
209        self.iter.next().map(|(k, _)| k)
210    }
211
212    fn size_hint(&self) -> (usize, Option<usize>) {
213        self.iter.size_hint()
214    }
215}
216
217/// Iterator over references to Values stored in the map.
218pub struct ValueIter<'a, K, V>
219where
220    K: Hash + Eq + Clone + Debug,
221    V: Clone,
222{
223    iter: Iter<'a, K, V>,
224}
225
226impl<K: Clone + Hash + Eq + Debug, V: Clone> ValueIter<'_, K, V> {
227    pub(crate) fn new(root: *mut Node<K, V>, length: usize) -> Self {
228        ValueIter {
229            iter: Iter::new(root, length),
230        }
231    }
232}
233
234impl<'a, K: Clone + Hash + Eq + Debug, V: Clone> Iterator for ValueIter<'a, K, V> {
235    type Item = &'a V;
236
237    /// Yield the next key value reference, or `None` if exhausted.
238    fn next(&mut self) -> Option<Self::Item> {
239        self.iter.next().map(|(_, v)| v)
240    }
241
242    fn size_hint(&self) -> (usize, Option<usize>) {
243        self.iter.size_hint()
244    }
245}
246
247#[cfg(test)]
248mod tests {
249    use super::super::cursor::SuperBlock;
250    use super::super::node::{Branch, Leaf, Node, H_CAPACITY};
251    use super::{Iter, LeafIter};
252
253    fn create_leaf_node_full(vbase: usize) -> *mut Node<usize, usize> {
254        assert!(vbase.is_multiple_of(10));
255        let node = Node::new_leaf(0);
256        {
257            let nmut = leaf_ref!(node, usize, usize);
258            for idx in 0..H_CAPACITY {
259                let v = vbase + idx;
260                nmut.insert_or_update(v as u64, v, v);
261            }
262        }
263        node as *mut _
264    }
265
266    #[test]
267    fn test_hashmap2_iter_leafiter_1() {
268        let test_iter: LeafIter<usize, usize> = LeafIter::new_base();
269        assert!(test_iter.count() == 0);
270    }
271
272    #[test]
273    fn test_hashmap2_iter_leafiter_2() {
274        let lnode = create_leaf_node_full(10);
275        let mut test_iter = LeafIter::new(lnode, true);
276
277        assert!(test_iter.size_hint() == (1, Some(1)));
278
279        let lref = test_iter.next().unwrap();
280        assert!(lref.min() == 10);
281        assert!(test_iter.next().is_none());
282        // This drops everything.
283        let _sb: SuperBlock<usize, usize> = SuperBlock::new_test(1, lnode as *mut _);
284    }
285
286    #[test]
287    fn test_hashmap2_iter_leafiter_3() {
288        let lnode = create_leaf_node_full(10);
289        let rnode = create_leaf_node_full(20);
290        let root = Node::new_branch(0, lnode, rnode);
291        let mut test_iter: LeafIter<usize, usize> = LeafIter::new(root as *mut _, true);
292
293        assert!(test_iter.size_hint() == (2, Some(2)));
294        let lref = test_iter.next().unwrap();
295        let rref = test_iter.next().unwrap();
296        assert!(lref.min() == 10);
297        assert!(rref.min() == 20);
298        assert!(test_iter.next().is_none());
299        // This drops everything.
300        let _sb: SuperBlock<usize, usize> = SuperBlock::new_test(1, root as *mut _);
301    }
302
303    #[test]
304    fn test_hashmap2_iter_leafiter_4() {
305        let l1node = create_leaf_node_full(10);
306        let r1node = create_leaf_node_full(20);
307        let l2node = create_leaf_node_full(30);
308        let r2node = create_leaf_node_full(40);
309        let b1node = Node::new_branch(0, l1node, r1node);
310        let b2node = Node::new_branch(0, l2node, r2node);
311        let root: *mut Branch<usize, usize> =
312            Node::new_branch(0, b1node as *mut _, b2node as *mut _);
313        let mut test_iter: LeafIter<usize, usize> = LeafIter::new(root as *mut _, true);
314
315        assert!(test_iter.size_hint() == (4, Some(4)));
316        let l1ref = test_iter.next().unwrap();
317        let r1ref = test_iter.next().unwrap();
318        let l2ref = test_iter.next().unwrap();
319        let r2ref = test_iter.next().unwrap();
320        assert!(l1ref.min() == 10);
321        assert!(r1ref.min() == 20);
322        assert!(l2ref.min() == 30);
323        assert!(r2ref.min() == 40);
324        assert!(test_iter.next().is_none());
325        // This drops everything.
326        let _sb: SuperBlock<usize, usize> = SuperBlock::new_test(1, root as *mut _);
327    }
328
329    #[test]
330    fn test_hashmap2_iter_leafiter_5() {
331        let lnode = create_leaf_node_full(10);
332        let mut test_iter = LeafIter::new(lnode, true);
333
334        assert!(test_iter.size_hint() == (1, Some(1)));
335
336        let lref = test_iter.next().unwrap();
337        assert!(lref.min() == 10);
338        assert!(test_iter.next().is_none());
339        // This drops everything.
340        let _sb: SuperBlock<usize, usize> = SuperBlock::new_test(1, lnode as *mut _);
341    }
342
343    #[test]
344    fn test_hashmap2_iter_iter_1() {
345        // Make a tree
346        let lnode = create_leaf_node_full(10);
347        let rnode = create_leaf_node_full(20);
348        let root = Node::new_branch(0, lnode, rnode);
349        let test_iter: Iter<usize, usize> = Iter::new(root as *mut _, H_CAPACITY * 2);
350
351        assert!(test_iter.size_hint() == (H_CAPACITY * 2, Some(H_CAPACITY * 2)));
352        assert!(test_iter.count() == H_CAPACITY * 2);
353        // Iterate!
354        // This drops everything.
355        let _sb: SuperBlock<usize, usize> = SuperBlock::new_test(1, root as *mut _);
356    }
357
358    #[test]
359    fn test_hashmap2_iter_iter_2() {
360        let l1node = create_leaf_node_full(10);
361        let r1node = create_leaf_node_full(20);
362        let l2node = create_leaf_node_full(30);
363        let r2node = create_leaf_node_full(40);
364        let b1node = Node::new_branch(0, l1node, r1node);
365        let b2node = Node::new_branch(0, l2node, r2node);
366        let root: *mut Branch<usize, usize> =
367            Node::new_branch(0, b1node as *mut _, b2node as *mut _);
368        let test_iter: Iter<usize, usize> = Iter::new(root as *mut _, H_CAPACITY * 4);
369
370        // println!("{:?}", test_iter.size_hint());
371
372        assert!(test_iter.size_hint() == (H_CAPACITY * 4, Some(H_CAPACITY * 4)));
373        assert!(test_iter.count() == H_CAPACITY * 4);
374        // This drops everything.
375        let _sb: SuperBlock<usize, usize> = SuperBlock::new_test(1, root as *mut _);
376    }
377}
concread/internals/hashmap/iter.rs

concread/internals/hashmap/
iter.rs
