concread/internals/bptree/
mutiter.rs

1//! Mutable iterators over bptree.
2
3use std::borrow::Borrow;
4// use std::collections::VecDeque;
5use std::fmt::Debug;
6use std::ops::RangeBounds;
7
8use super::cursor::{CursorReadOps, CursorWrite};
9use super::iter::RangeIter;
10
11/// Mutable Iterator over references to Key Value pairs stored, bounded by a range.
12pub struct RangeMutIter<'n, K, V>
13where
14    K: Ord + Clone + Debug,
15    V: Clone,
16{
17    cursor: &'n mut CursorWrite<K, V>,
18    inner_range_iter: RangeIter<'n, K, V>,
19}
20
21impl<'n, K, V> RangeMutIter<'n, K, V>
22where
23    K: Clone + Ord + Debug,
24    V: Clone,
25{
26    pub(crate) fn new<R, T>(cursor: &'n mut CursorWrite<K, V>, range: R) -> Self
27    where
28        T: Ord + ?Sized,
29        K: Borrow<T>,
30        R: RangeBounds<T>,
31    {
32        // For now I'm doing this in the "stupidest way possible".
33        //
34        // The reason is we could do this with a more advanced iterator that determines
35        // clones as we go, but that's quite a bit more work. For now if we just use
36        // an existing iterator and get_mut_ref as we go, we get the same effect.
37        //
38        // This relies on the fact that we take &mut over cursor, so the keys can't
39        // change during this, so even if we iterator over the ro-snapshot, the keys
40        // still sync to the rw version.
41
42        let length = cursor.len();
43        let root = cursor.get_root();
44
45        let inner_range_iter = RangeIter::new(root, range, length);
46
47        RangeMutIter {
48            cursor,
49            inner_range_iter,
50        }
51    }
52}
53
54impl<'n, K: Clone + Ord + Debug, V: Clone> Iterator for RangeMutIter<'n, K, V> {
55    type Item = (&'n K, &'n mut V);
56
57    /// Yield the next key value reference, or `None` if exhausted.
58    fn next(&mut self) -> Option<Self::Item> {
59        if let Some((k, _)) = self.inner_range_iter.next() {
60            self.cursor.get_mut_ref(k).map(|v| {
61                // Rust's lifetime constraints aren't working here, and this is
62                // yielding 'n when we need '_ which is shorter. So we force strip
63                // and apply the lifetime to constrain it to this iterator.
64                let v = v as *mut V;
65                let v = unsafe { &mut *v as &mut V };
66                (k, v)
67            })
68        } else {
69            None
70        }
71    }
72
73    /// Provide a hint as to the number of items this iterator will yield.
74    fn size_hint(&self) -> (usize, Option<usize>) {
75        (0, Some(self.cursor.len()))
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use super::super::cursor::SuperBlock;
82    use super::super::node::{Leaf, Node, L_CAPACITY};
83    use super::RangeMutIter;
84    use std::ops::Bound;
85    use std::ops::Bound::*;
86
87    use crate::internals::lincowcell::LinCowCellCapable;
88
89    fn create_leaf_node_full(vbase: usize) -> *mut Node<usize, usize> {
90        assert!(vbase % 10 == 0);
91        let node = Node::new_leaf(0);
92        {
93            let nmut = leaf_ref!(node, usize, usize);
94            for idx in 0..L_CAPACITY {
95                let v = vbase + idx;
96                nmut.insert_or_update(v, v);
97            }
98        }
99        node as *mut _
100    }
101
102    #[test]
103    fn test_bptree2_iter_mutrangeiter_1() {
104        let node = create_leaf_node_full(10);
105
106        let sb = SuperBlock::new_test(1, node as *mut Node<usize, usize>);
107        let mut wcurs = sb.create_writer();
108
109        let bounds: (Bound<usize>, Bound<usize>) = (Unbounded, Unbounded);
110        let range_mut_iter = RangeMutIter::new(&mut wcurs, bounds);
111        for (k, v_mut) in range_mut_iter {
112            assert_eq!(*k, *v_mut);
113        }
114
115        let bounds: (Bound<usize>, Bound<usize>) = (Unbounded, Unbounded);
116        let range_mut_iter = RangeMutIter::new(&mut wcurs, bounds);
117        for (_k, v_mut) in range_mut_iter {
118            *v_mut += 1;
119        }
120
121        let bounds: (Bound<usize>, Bound<usize>) = (Unbounded, Unbounded);
122        let range_mut_iter = RangeMutIter::new(&mut wcurs, bounds);
123        for (k, v_mut) in range_mut_iter {
124            assert_eq!(*k + 1, *v_mut);
125        }
126    }
127}
concread/internals/bptree/mutiter.rs

concread/internals/bptree/
mutiter.rs
