embed_btree/bptree/
iter.rs

1use super::{BTree, *};
2use crate::trace_log;
3use core::marker::PhantomData;
4use core::mem::needs_drop;
5
6pub(super) struct IterForward<K, V> {
7    /// Current leaf node for forward iteration
8    pub front_leaf: LeafNode<K, V>,
9    /// Current index within the leaf for forward iteration
10    pub idx: u8,
11}
12
13impl<K, V> IterForward<K, V> {
14    #[inline]
15    pub fn next(&mut self) -> Option<(&mut LeafNode<K, V>, u8)> {
16        if self.idx >= self.front_leaf.key_count() {
17            if let Some(next) = self.front_leaf.get_right_node() {
18                debug_assert!(next.key_count() > 0);
19                self.front_leaf = next;
20                self.idx = 0;
21            } else {
22                return None;
23            }
24        }
25        let current_idx = self.idx;
26        self.idx = current_idx + 1;
27        Some((&mut self.front_leaf, current_idx))
28    }
29
30    #[inline]
31    pub unsafe fn next_pair(&mut self) -> Option<(*mut K, *mut V)> {
32        let (leaf, idx) = self.next()?;
33        leaf.get_raw_pair(idx)
34    }
35}
36
37pub(super) struct IterBackward<K, V> {
38    /// Current leaf node for backward iteration
39    pub back_leaf: LeafNode<K, V>,
40    /// back_idx - 1 is the next index within the back leaf, initial to key_count
41    /// When back_idx == 0, should go to previous leaf
42    pub back_idx: u8,
43}
44
45impl<K, V> IterBackward<K, V> {
46    #[inline]
47    pub fn prev(&mut self) -> Option<(&mut LeafNode<K, V>, u8)> {
48        if self.back_idx == 0 {
49            if let Some(prev) = self.back_leaf.get_left_node() {
50                self.back_idx = prev.key_count();
51                self.back_leaf = prev;
52                debug_assert!(self.back_idx > 0);
53            } else {
54                return None;
55            }
56        }
57        self.back_idx -= 1;
58        Some((&mut self.back_leaf, self.back_idx))
59    }
60
61    #[inline]
62    pub unsafe fn prev_pair(&mut self) -> Option<(*mut K, *mut V)> {
63        let (leaf, idx) = self.prev()?;
64        leaf.get_raw_pair(idx)
65    }
66}
67
68/// Internal base iterator structure that handles the common logic
69/// for iterating over leaf nodes in both forward and backward directions.
70struct IterBase<K, V> {
71    /// Remaining elements to iterate, it serve as a guard in case forward and backward rendezvous
72    remaining: usize,
73    forward: IterForward<K, V>,
74    backward: IterBackward<K, V>,
75}
76
77impl<K, V> IterBase<K, V> {
78    /// Create a new IterBase
79    /// leaves: (front_leaf, back_leaf) - both Some or both None
80    /// remaining: total remaining elements
81    #[inline]
82    fn new(front_leaf: LeafNode<K, V>, back_leaf: LeafNode<K, V>, remaining: usize) -> Self {
83        Self {
84            forward: IterForward { front_leaf, idx: 0 },
85            backward: IterBackward { back_idx: back_leaf.key_count(), back_leaf },
86            remaining,
87        }
88    }
89
90    /// Advance the forward iterator and return the current leaf and index
91    /// Returns None if we've moved past the end
92    #[inline]
93    fn advance_forward(&mut self) -> Option<(&mut LeafNode<K, V>, u8)> {
94        if self.remaining == 0 {
95            return None;
96        }
97        self.remaining -= 1;
98        self.forward.next()
99    }
100
101    /// Advance the backward iterator and return the current leaf and index
102    /// Returns None if we've moved past the beginning
103    #[inline]
104    fn advance_backward(&mut self) -> Option<(&mut LeafNode<K, V>, u8)> {
105        if self.remaining == 0 {
106            return None;
107        }
108        self.remaining -= 1;
109        self.backward.prev()
110    }
111
112    /// Get remaining count
113    #[inline]
114    fn remaining(&self) -> usize {
115        self.remaining
116    }
117}
118
119/// An iterator over the entries of a BTreeMap
120pub struct Iter<'a, K: 'a, V: 'a> {
121    base: Option<IterBase<K, V>>,
122    _marker: PhantomData<&'a ()>,
123}
124
125impl<'a, K: 'a, V: 'a> Iter<'a, K, V> {
126    #[inline]
127    pub(super) fn new(leaves: Option<(LeafNode<K, V>, LeafNode<K, V>)>, remaining: usize) -> Self {
128        if let Some((front, back)) = leaves {
129            Self { base: Some(IterBase::new(front, back, remaining)), _marker: Default::default() }
130        } else {
131            Self { base: None, _marker: Default::default() }
132        }
133    }
134}
135
136impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
137    type Item = (&'a K, &'a V);
138
139    #[inline]
140    fn next(&mut self) -> Option<Self::Item> {
141        let base = self.base.as_mut()?;
142        let (leaf, idx) = base.advance_forward()?;
143        unsafe {
144            let key = (*leaf.key_ptr(idx)).assume_init_ref();
145            let value = (*leaf.value_ptr(idx)).assume_init_ref();
146            Some((key, value))
147        }
148    }
149
150    #[inline]
151    fn size_hint(&self) -> (usize, Option<usize>) {
152        let len = self.len();
153        (len, Some(len))
154    }
155}
156
157impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
158    #[inline]
159    fn len(&self) -> usize {
160        self.base.as_ref().map(|x| x.remaining()).unwrap_or(0)
161    }
162}
163
164impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
165    #[inline]
166    fn next_back(&mut self) -> Option<Self::Item> {
167        let base = self.base.as_mut()?;
168        let (leaf, idx) = base.advance_backward()?;
169        unsafe {
170            let key = (*leaf.key_ptr(idx)).assume_init_ref();
171            let value = (*leaf.value_ptr(idx)).assume_init_ref();
172            Some((key, value))
173        }
174    }
175}
176
177/// A mutable iterator over the entries of a BTreeMap
178pub struct IterMut<'a, K: 'a, V: 'a> {
179    base: Option<IterBase<K, V>>,
180    _marker: PhantomData<&'a mut ()>,
181}
182
183impl<'a, K: 'a, V: 'a> IterMut<'a, K, V> {
184    #[inline]
185    pub(super) fn new(leaves: Option<(LeafNode<K, V>, LeafNode<K, V>)>, remaining: usize) -> Self {
186        if let Some((front, back)) = leaves {
187            Self { base: Some(IterBase::new(front, back, remaining)), _marker: Default::default() }
188        } else {
189            Self { base: None, _marker: Default::default() }
190        }
191    }
192}
193
194impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
195    type Item = (&'a K, &'a mut V);
196
197    #[inline]
198    fn next(&mut self) -> Option<Self::Item> {
199        let base = self.base.as_mut()?;
200        let (leaf, idx) = base.advance_forward()?;
201        unsafe {
202            let key = (*leaf.key_ptr(idx)).assume_init_ref();
203            let value = (*leaf.value_ptr_mut(idx)).assume_init_mut();
204            Some((key, value))
205        }
206    }
207
208    #[inline]
209    fn size_hint(&self) -> (usize, Option<usize>) {
210        let len = self.len();
211        (len, Some(len))
212    }
213}
214
215impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
216    #[inline]
217    fn len(&self) -> usize {
218        self.base.as_ref().map(|x| x.remaining()).unwrap_or(0)
219    }
220}
221
222impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
223    #[inline]
224    fn next_back(&mut self) -> Option<Self::Item> {
225        let base = self.base.as_mut()?;
226        let (leaf, idx) = base.advance_backward()?;
227        unsafe {
228            let key = (*leaf.key_ptr(idx)).assume_init_ref();
229            let value = (*leaf.value_ptr_mut(idx)).assume_init_mut();
230            Some((key, value))
231        }
232    }
233}
234
235/// An iterator over the keys of a BTreeMap
236pub struct Keys<'a, K: 'a, V: 'a> {
237    inner: Iter<'a, K, V>,
238}
239
240impl<'a, K: 'a, V: 'a> Keys<'a, K, V> {
241    #[inline]
242    pub(super) fn new(inner: Iter<'a, K, V>) -> Self {
243        Self { inner }
244    }
245}
246
247impl<'a, K: 'a, V: 'a> Iterator for Keys<'a, K, V> {
248    type Item = &'a K;
249
250    #[inline]
251    fn next(&mut self) -> Option<Self::Item> {
252        self.inner.next().map(|(k, _)| k)
253    }
254
255    #[inline]
256    fn size_hint(&self) -> (usize, Option<usize>) {
257        self.inner.size_hint()
258    }
259}
260
261impl<'a, K: 'a, V: 'a> ExactSizeIterator for Keys<'a, K, V> {
262    #[inline]
263    fn len(&self) -> usize {
264        self.inner.len()
265    }
266}
267
268impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Keys<'a, K, V> {
269    #[inline]
270    fn next_back(&mut self) -> Option<Self::Item> {
271        self.inner.next_back().map(|(k, _)| k)
272    }
273}
274
275/// An iterator over the values of a BTreeMap
276pub struct Values<'a, K: 'a, V: 'a> {
277    inner: Iter<'a, K, V>,
278}
279
280impl<'a, K: 'a, V: 'a> Values<'a, K, V> {
281    #[inline]
282    pub(super) fn new(inner: Iter<'a, K, V>) -> Self {
283        Self { inner }
284    }
285}
286
287impl<'a, K: 'a, V: 'a> Iterator for Values<'a, K, V> {
288    type Item = &'a V;
289
290    #[inline]
291    fn next(&mut self) -> Option<Self::Item> {
292        self.inner.next().map(|(_, v)| v)
293    }
294
295    #[inline]
296    fn size_hint(&self) -> (usize, Option<usize>) {
297        self.inner.size_hint()
298    }
299}
300
301impl<'a, K: 'a, V: 'a> ExactSizeIterator for Values<'a, K, V> {
302    #[inline]
303    fn len(&self) -> usize {
304        self.inner.len()
305    }
306}
307
308impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Values<'a, K, V> {
309    #[inline]
310    fn next_back(&mut self) -> Option<Self::Item> {
311        self.inner.next_back().map(|(_, v)| v)
312    }
313}
314
315/// A mutable iterator over the values of a BTreeMap
316pub struct ValuesMut<'a, K: 'a, V: 'a> {
317    inner: IterMut<'a, K, V>,
318}
319
320impl<'a, K: 'a, V: 'a> ValuesMut<'a, K, V> {
321    #[inline]
322    pub(super) fn new(inner: IterMut<'a, K, V>) -> Self {
323        Self { inner }
324    }
325}
326
327impl<'a, K: 'a, V: 'a> Iterator for ValuesMut<'a, K, V> {
328    type Item = &'a mut V;
329
330    #[inline]
331    fn next(&mut self) -> Option<Self::Item> {
332        self.inner.next().map(|(_, v)| v)
333    }
334
335    #[inline]
336    fn size_hint(&self) -> (usize, Option<usize>) {
337        self.inner.size_hint()
338    }
339}
340
341impl<'a, K: 'a, V: 'a> ExactSizeIterator for ValuesMut<'a, K, V> {
342    #[inline]
343    fn len(&self) -> usize {
344        self.inner.len()
345    }
346}
347
348impl<'a, K: 'a, V: 'a> DoubleEndedIterator for ValuesMut<'a, K, V> {
349    #[inline]
350    fn next_back(&mut self) -> Option<Self::Item> {
351        self.inner.next_back().map(|(_, v)| v)
352    }
353}
354
355// Range and RangeMut implementations with DoubleEndedIterator support
356
357/// Internal base structure for range iteration
358/// Manages forward and backward iteration over a range of entries
359/// When the range is exhausted, the entire struct should be set to None
360pub(super) struct RangeBase<'a, K: 'a, V: 'a> {
361    front_leaf: LeafNode<K, V>,
362    back_leaf: LeafNode<K, V>,
363    front_idx: u8,
364    // back_idx -1 is the next pos, initial to be key_count
365    back_idx: u8,
366    _marker: PhantomData<&'a ()>,
367}
368
369impl<'a, K: 'a, V: 'a> RangeBase<'a, K, V> {
370    #[inline]
371    pub fn new(
372        front_leaf: LeafNode<K, V>, front_idx: u8, back_leaf: LeafNode<K, V>, back_idx: u8,
373    ) -> Self {
374        Self { front_leaf, front_idx, back_leaf, back_idx, _marker: PhantomData }
375    }
376
377    /// Advance forward and return the current leaf and index
378    /// Returns None when range is exhausted, caller should set RangeBase to None
379    #[inline]
380    fn advance_forward(&mut self) -> Option<(&mut LeafNode<K, V>, u8)> {
381        loop {
382            let idx = self.front_idx;
383            if self.front_leaf == self.back_leaf {
384                if idx < self.back_idx {
385                    self.front_idx = idx + 1;
386                    return Some((&mut self.front_leaf, idx));
387                } else {
388                    return None;
389                }
390            } else {
391                if idx < self.front_leaf.key_count() {
392                    self.front_idx = idx + 1;
393                    return Some((&mut self.front_leaf, idx));
394                } else {
395                    self.front_leaf = self.front_leaf.get_right_node().unwrap();
396                    self.front_idx = 0;
397                    // Because we always need to compare front_leaf and back_leaf after cursor
398                    // moves, cannot use IterForward & IterBackward here.
399                }
400            }
401        }
402    }
403
404    /// Advance backward and return the current leaf and index
405    /// Returns None when range is exhausted, caller should set RangeBase to None
406    #[inline]
407    fn advance_backward(&mut self) -> Option<(&mut LeafNode<K, V>, u8)> {
408        loop {
409            if self.back_leaf == self.front_leaf {
410                if self.back_idx == 0 {
411                    return None;
412                }
413                self.back_idx -= 1;
414                if self.back_idx >= self.front_idx {
415                    return Some((&mut self.back_leaf, self.back_idx));
416                } else {
417                    return None;
418                }
419            } else {
420                if self.back_idx == 0 {
421                    self.back_leaf = self.back_leaf.get_left_node().unwrap();
422                    self.back_idx = self.back_leaf.key_count();
423                    // Because we always need to compare front_leaf and back_leaf after cursor
424                    // moves, cannot use IterForward & IterBackward here.
425                } else {
426                    self.back_idx -= 1;
427                    return Some((&mut self.back_leaf, self.back_idx));
428                }
429            }
430        }
431    }
432}
433
434/// An iterator over a sub-range of entries in a BTreeMap
435/// RangeBase is wrapped in Option - when exhausted, it becomes None
436pub struct Range<'a, K: 'a, V: 'a> {
437    base: Option<RangeBase<'a, K, V>>,
438}
439
440impl<'a, K: 'a, V: 'a> Range<'a, K, V> {
441    #[inline]
442    pub(super) fn new(base: Option<RangeBase<'a, K, V>>) -> Self {
443        Self { base }
444    }
445}
446
447impl<'a, K: 'a, V: 'a> Iterator for Range<'a, K, V> {
448    type Item = (&'a K, &'a V);
449
450    #[inline]
451    fn next(&mut self) -> Option<Self::Item> {
452        let base = self.base.as_mut()?;
453        if let Some((leaf, idx)) = base.advance_forward() {
454            unsafe {
455                let key = (*leaf.key_ptr(idx)).assume_init_ref();
456                let value = (*leaf.value_ptr(idx)).assume_init_ref();
457                Some((key, value))
458            }
459        } else {
460            self.base = None;
461            None
462        }
463    }
464}
465
466impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Range<'a, K, V> {
467    #[inline]
468    fn next_back(&mut self) -> Option<Self::Item> {
469        let base = self.base.as_mut()?;
470        if let Some((leaf, idx)) = base.advance_backward() {
471            unsafe {
472                let key = (*leaf.key_ptr(idx)).assume_init_ref();
473                let value = (*leaf.value_ptr(idx)).assume_init_ref();
474                Some((key, value))
475            }
476        } else {
477            self.base = None;
478            None
479        }
480    }
481}
482
483/// A mutable iterator over a sub-range of entries in a BTreeMap
484/// RangeBase is wrapped in Option - when exhausted, it becomes None
485pub struct RangeMut<'a, K: 'a, V: 'a> {
486    base: Option<RangeBase<'a, K, V>>,
487}
488
489impl<'a, K: 'a, V: 'a> RangeMut<'a, K, V> {
490    #[inline]
491    pub(super) fn new(base: Option<RangeBase<'a, K, V>>) -> Self {
492        Self { base }
493    }
494}
495
496impl<'a, K: 'a, V: 'a> Iterator for RangeMut<'a, K, V> {
497    type Item = (&'a K, &'a mut V);
498
499    #[inline]
500    fn next(&mut self) -> Option<Self::Item> {
501        let base = self.base.as_mut()?;
502        if let Some((leaf, idx)) = base.advance_forward() {
503            unsafe {
504                let key = (*leaf.key_ptr(idx)).assume_init_ref();
505                let value = (*leaf.value_ptr_mut(idx)).assume_init_mut();
506                Some((key, value))
507            }
508        } else {
509            self.base = None;
510            None
511        }
512    }
513}
514
515impl<'a, K: 'a, V: 'a> DoubleEndedIterator for RangeMut<'a, K, V> {
516    #[inline]
517    fn next_back(&mut self) -> Option<Self::Item> {
518        let base = self.base.as_mut()?;
519        if let Some((leaf, idx)) = base.advance_backward() {
520            unsafe {
521                let key = (*leaf.key_ptr(idx)).assume_init_ref();
522                let value = (*leaf.value_ptr_mut(idx)).assume_init_mut();
523                Some((key, value))
524            }
525        } else {
526            self.base = None;
527            None
528        }
529    }
530}
531
532struct IntoIterBase<K: Key, V: Value, S: Stats> {
533    /// Path cache for deallocating internal nodes after iteration
534    cache: S::PathBuffer,
535    /// Current leaf being iterated
536    leaf: Option<LeafNode<K, V>>,
537    /// Current index within the leaf
538    idx: u8,
539    /// Remaining elements to iterate
540    remaining: usize,
541    is_forward: bool,
542}
543
544impl<K: Key, V: Value, S: Stats> IntoIterBase<K, V, S> {
545    #[inline]
546    fn new(tree: &mut BTree<K, V, S>, is_forward: bool) -> Self {
547        let mut stats = S::default();
548        let len = tree.inner.len;
549        core::mem::swap(&mut stats, &mut tree.stats);
550        let root = tree.inner.root.take();
551        if let Some(root_p) = root {
552            // Move TreeInfo out of BTreeMap, leave a fresh empty one as placeholder.
553            let (cache, leaf) = match Node::from_root_ptr(root_p) {
554                Node::Leaf(leaf) => (stats.take_cache::<K>(None), leaf),
555                Node::Inter(inter) => {
556                    let mut cache = stats.take_cache(Some(inter.clone()));
557                    let leaf = if is_forward {
558                        inter.find_first_leaf_with_cache::<V, _>(&mut cache)
559                    } else {
560                        inter.find_last_leaf_with_cache::<V, _>(&mut cache)
561                    };
562                    (cache, leaf)
563                }
564            };
565            Self {
566                cache,
567                idx: if is_forward { 0 } else { leaf.key_count() },
568                leaf: Some(leaf),
569                remaining: len,
570                is_forward,
571            }
572        } else {
573            Self {
574                cache: stats.take_cache::<K>(None),
575                leaf: None,
576                idx: 0,
577                remaining: 0,
578                is_forward,
579            }
580        }
581    }
582
583    #[inline(always)]
584    fn advance_forward(&mut self) -> LeafNode<K, V> {
585        let _leaf = self.leaf.take().unwrap();
586        _leaf.dealloc::<false>();
587        let (parent, idx) = self
588            .cache
589            .move_path_right_and_pop_l1::<K, _>(|_cache, node| {
590                node.dealloc::<true>();
591            })
592            .unwrap();
593        self.cache.push_path(parent.clone(), idx);
594        let new_leaf = parent.get_child_as_leaf(idx);
595        self.idx = 0;
596        new_leaf
597    }
598
599    #[inline(always)]
600    fn advance_backward(&mut self) -> LeafNode<K, V> {
601        let _leaf = self.leaf.take().unwrap();
602        _leaf.dealloc::<false>();
603        let (parent, idx) = self
604            .cache
605            .move_path_left_and_pop_l1::<K, _>(|_cache, node| node.dealloc::<true>())
606            .unwrap();
607        self.cache.push_path(parent.clone(), idx);
608        let new_leaf = parent.get_child_as_leaf(idx);
609        self.idx = new_leaf.key_count();
610        new_leaf
611    }
612
613    #[inline]
614    fn next(&mut self) -> Option<(K, V)> {
615        if self.remaining == 0 {
616            return None;
617        }
618        self.remaining -= 1;
619
620        // Check if we need to advance to next/prev leaf
621        if self.is_forward {
622            if let Some(ref leaf) = self.leaf {
623                if self.idx >= leaf.key_count() {
624                    let new_leaf = self.advance_forward();
625                    self.leaf = Some(new_leaf);
626                }
627            } else {
628                return None;
629            }
630            let idx = self.idx;
631            self.idx += 1;
632            if let Some(ref leaf) = self.leaf {
633                trace_log!("into_iter forward: {leaf:?}:{idx}");
634                unsafe {
635                    let key = (*leaf.key_ptr(idx)).assume_init_read();
636                    let value = (*leaf.value_ptr(idx)).assume_init_read();
637                    return Some((key, value));
638                }
639            }
640        } else {
641            if self.idx == 0 {
642                if let Some(ref leaf) = self.leaf {
643                    leaf.get_left_node()?;
644                }
645                let new_leaf = self.advance_backward();
646                self.leaf = Some(new_leaf);
647            }
648            if let Some(ref leaf) = self.leaf {
649                self.idx -= 1;
650                let idx = self.idx;
651                trace_log!("into_iter backward: {leaf:?}:{idx}");
652                unsafe {
653                    let key = (*leaf.key_ptr(idx)).assume_init_read();
654                    let value = (*leaf.value_ptr(idx)).assume_init_read();
655                    return Some((key, value));
656                }
657            }
658        }
659        None
660    }
661}
662
663impl<K: Key, V: Value, S: Stats> Drop for IntoIterBase<K, V, S> {
664    fn drop(&mut self) {
665        let is_forward = self.is_forward;
666        // NOTE: if the original tree has root, then self.leaf always exists after iteration done
667        if let Some(mut leaf) = self.leaf.take() {
668            if needs_drop::<K>() {
669                if is_forward {
670                    trace_log!("into_iter drop forward {leaf:?} [{}..]", self.idx);
671                    for idx in self.idx..leaf.key_count() {
672                        unsafe { (*leaf.key_ptr_mut(idx)).assume_init_drop() };
673                    }
674                } else {
675                    trace_log!("into_iter drop backward {leaf:?} [..{}]", self.idx);
676                    for idx in 0..self.idx {
677                        unsafe { (*leaf.key_ptr_mut(idx)).assume_init_drop() };
678                    }
679                }
680            }
681            if needs_drop::<V>() {
682                if is_forward {
683                    for idx in self.idx..leaf.key_count() {
684                        unsafe { (*leaf.value_ptr_mut(idx)).assume_init_drop() };
685                    }
686                } else {
687                    for idx in 0..self.idx {
688                        unsafe { (*leaf.value_ptr_mut(idx)).assume_init_drop() };
689                    }
690                }
691            }
692            leaf.dealloc::<false>();
693            // We should free the rest internal nodes even after leaf iteration done
694            if is_forward {
695                while let Some((parent, idx)) =
696                    self.cache.move_path_right_and_pop_l1::<K, _>(|_cache, _node| {
697                        _node.dealloc::<true>();
698                    })
699                {
700                    trace_log!("into_iter drop forward parent {parent:?}:{idx}");
701                    self.cache.push_path(parent.clone(), idx);
702                    let leaf = parent.get_child_as_leaf::<V>(idx);
703                    leaf.dealloc::<true>();
704                }
705            } else {
706                while let Some((parent, idx)) =
707                    self.cache.move_path_left_and_pop_l1::<K, _>(|_cache, _node| {
708                        _node.dealloc::<true>();
709                    })
710                {
711                    trace_log!("into_iter drop forward parent {parent:?}:{idx}");
712                    self.cache.push_path(parent.clone(), idx);
713                    let leaf = parent.get_child_as_leaf::<V>(idx);
714                    leaf.dealloc::<true>();
715                }
716            }
717        }
718    }
719}
720
721/// An owning iterator over the entries of a BTreeMap
722/// Uses PathBuffer to manage tree traversal and safe deallocation
723///
724/// NOTE: In order to keep the logic simple, we does not implement `DoubleEndedIterator` here
725pub struct IntoIter<K: Key, V: Value, S: Stats> {
726    /// If true, iterate in reverse order
727    base: Result<IntoIterBase<K, V, S>, (BTree<K, V, S>, bool)>,
728}
729
730impl<K: Key, V: Value, S: Stats> IntoIter<K, V, S> {
731    #[inline]
732    pub(super) fn new(tree: BTree<K, V, S>, is_forward: bool) -> Self {
733        Self { base: Err((tree, is_forward)) }
734    }
735
736    /// Return a iterator in reversed direction
737    ///
738    /// IntoIter only implement one way iteration (either forward or backward).
739    /// this will mock Iterator::rev for DoubleEndedIterator trait
740    ///
741    /// # Panic
742    ///
743    /// If iteration already started, cannot change the direction
744    #[inline]
745    pub fn rev(self) -> Self {
746        if let Err((tree, _is_forward)) = self.base {
747            Self { base: Err((tree, false)) }
748        } else {
749            panic!("cannot change direction after iteration start");
750        }
751    }
752}
753
754impl<K: Key, V: Value, S: Stats> Iterator for IntoIter<K, V, S> {
755    type Item = (K, V);
756
757    #[inline]
758    fn next(&mut self) -> Option<Self::Item> {
759        match &mut self.base {
760            Ok(base) => base.next(),
761            Err((tree, is_forward)) => {
762                self.base = Ok(IntoIterBase::new(tree, *is_forward));
763                if let Ok(base) = &mut self.base {
764                    base.next()
765                } else {
766                    unreachable!();
767                }
768            }
769        }
770    }
771
772    #[inline]
773    fn size_hint(&self) -> (usize, Option<usize>) {
774        let remaining = match &self.base {
775            Ok(base) => base.remaining,
776            Err((tree, _)) => tree.len(),
777        };
778        (remaining, Some(remaining))
779    }
780}
781
782impl<K: Key, V: Value, S: Stats> ExactSizeIterator for IntoIter<K, V, S> {
783    #[inline]
784    fn len(&self) -> usize {
785        match &self.base {
786            Ok(base) => base.remaining,
787            Err((tree, _)) => tree.len(),
788        }
789    }
790}
embed_btree/bptree/iter.rs

embed_btree/bptree/
iter.rs
