embed_collections/btree/
iter.rs

1use super::{BTreeMap, helper::*, leaf::*, node::*};
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: u32,
11}
12
13impl<K, V> IterForward<K, V> {
14    #[inline]
15    pub fn next(&mut self) -> Option<(&LeafNode<K, V>, u32)> {
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((&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: u32,
43}
44
45impl<K, V> IterBackward<K, V> {
46    #[inline]
47    pub fn prev(&mut self) -> Option<(&LeafNode<K, V>, u32)> {
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((&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<(&LeafNode<K, V>, u32)> {
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<(&LeafNode<K, V>, u32)> {
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(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(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: u32,
364    // back_idx -1 is the next pos, initial to be key_count
365    back_idx: u32,
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: u32, back_leaf: LeafNode<K, V>, back_idx: u32,
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<(&LeafNode<K, V>, u32)> {
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((&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((&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<(&LeafNode<K, V>, u32)> {
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((&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((&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(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(idx)).assume_init_mut();
523                Some((key, value))
524            }
525        } else {
526            self.base = None;
527            None
528        }
529    }
530}
531
532struct IntoIterBase<K: Ord + Clone + Sized, V: Sized> {
533    /// Path cache for deallocating internal nodes after iteration
534    _cache: Option<TreeInfo<K, V>>,
535    /// Current leaf being iterated
536    leaf: Option<LeafNode<K, V>>,
537    /// Current index within the leaf
538    idx: u32,
539    /// Remaining elements to iterate
540    remaining: usize,
541    is_forward: bool,
542}
543
544impl<K: Ord + Clone + Sized, V: Sized> IntoIterBase<K, V> {
545    #[inline]
546    fn new(tree: &mut BTreeMap<K, V>, is_forward: bool) -> Self {
547        if let Some(root_p) = tree.root.take() {
548            let mut cache = tree.take_cache();
549            // Move TreeInfo out of BTreeMap, leave a fresh empty one as placeholder.
550            let leaf = match Node::from_root_ptr(root_p) {
551                Node::Leaf(leaf) => leaf,
552                Node::Inter(inter) => {
553                    if is_forward {
554                        inter.find_first_leaf(cache.as_mut())
555                    } else {
556                        inter.find_last_leaf(cache.as_mut())
557                    }
558                }
559            };
560            Self {
561                _cache: cache,
562                idx: if is_forward { 0 } else { leaf.key_count() },
563                leaf: Some(leaf),
564                remaining: tree.len,
565                is_forward,
566            }
567        } else {
568            Self { _cache: None, leaf: None, idx: 0, remaining: 0, is_forward }
569        }
570    }
571
572    #[inline(always)]
573    fn get_cache(&mut self) -> Option<&mut TreeInfo<K, V>> {
574        self._cache.as_mut()
575    }
576
577    #[inline(always)]
578    fn advance_forward(&mut self) -> LeafNode<K, V> {
579        let _leaf = self.leaf.take().unwrap();
580        _leaf.dealloc::<false>();
581        let cache = self.get_cache().unwrap();
582        let (parent, idx) = cache
583            .move_right_and_pop_l1(|_info, _node| {
584                _node.dealloc::<true>();
585            })
586            .unwrap();
587        cache.push(parent.clone(), idx);
588        let new_leaf = parent.get_child_as_leaf(idx);
589        self.idx = 0;
590        new_leaf
591    }
592
593    #[inline(always)]
594    fn advance_backward(&mut self) -> LeafNode<K, V> {
595        let _leaf = self.leaf.take().unwrap();
596        _leaf.dealloc::<false>();
597        let cache = self.get_cache().unwrap();
598        let (parent, idx) =
599            cache.move_left_and_pop_l1(|_info, _node| _node.dealloc::<true>()).unwrap();
600        cache.push(parent.clone(), idx);
601        let new_leaf = parent.get_child_as_leaf(idx);
602        self.idx = new_leaf.key_count();
603        new_leaf
604    }
605
606    #[inline]
607    fn next(&mut self) -> Option<(K, V)> {
608        if self.remaining == 0 {
609            return None;
610        }
611        self.remaining -= 1;
612
613        // Check if we need to advance to next/prev leaf
614        if self.is_forward {
615            if let Some(ref leaf) = self.leaf {
616                if self.idx >= leaf.key_count() {
617                    let new_leaf = self.advance_forward();
618                    self.leaf = Some(new_leaf);
619                }
620            } else {
621                return None;
622            }
623            let idx = self.idx;
624            self.idx += 1;
625            if let Some(ref leaf) = self.leaf {
626                trace_log!("into_iter forward: {leaf:?}:{idx}");
627                unsafe {
628                    let key = (*leaf.key_ptr(idx)).assume_init_read();
629                    let value = (*leaf.value_ptr(idx)).assume_init_read();
630                    return Some((key, value));
631                }
632            }
633        } else {
634            if self.idx == 0 {
635                if let Some(ref leaf) = self.leaf {
636                    leaf.get_left_node()?;
637                }
638                let new_leaf = self.advance_backward();
639                self.leaf = Some(new_leaf);
640            }
641            if let Some(ref leaf) = self.leaf {
642                self.idx -= 1;
643                let idx = self.idx;
644                trace_log!("into_iter backward: {leaf:?}:{idx}");
645                unsafe {
646                    let key = (*leaf.key_ptr(idx)).assume_init_read();
647                    let value = (*leaf.value_ptr(idx)).assume_init_read();
648                    return Some((key, value));
649                }
650            }
651        }
652        None
653    }
654}
655
656impl<K: Ord + Clone + Sized, V: Sized> Drop for IntoIterBase<K, V> {
657    fn drop(&mut self) {
658        let is_forward = self.is_forward;
659        // NOTE: if the original tree has root, then self.leaf always exists after iteration done
660        if let Some(leaf) = self.leaf.take() {
661            if needs_drop::<K>() {
662                if is_forward {
663                    trace_log!("into_iter drop forward {leaf:?} [{}..]", self.idx);
664                    for idx in self.idx..leaf.key_count() {
665                        unsafe { (*leaf.key_ptr(idx)).assume_init_drop() };
666                    }
667                } else {
668                    trace_log!("into_iter drop backward {leaf:?} [..{}]", self.idx);
669                    for idx in 0..self.idx {
670                        unsafe { (*leaf.key_ptr(idx)).assume_init_drop() };
671                    }
672                }
673            }
674            if needs_drop::<V>() {
675                if is_forward {
676                    for idx in self.idx..leaf.key_count() {
677                        unsafe { (*leaf.value_ptr(idx)).assume_init_drop() };
678                    }
679                } else {
680                    for idx in 0..self.idx {
681                        unsafe { (*leaf.value_ptr(idx)).assume_init_drop() };
682                    }
683                }
684            }
685            leaf.dealloc::<false>();
686            if let Some(cache) = self.get_cache() {
687                // We should free the rest internal nodes even after leaf iteration done
688                if is_forward {
689                    while let Some((parent, idx)) = cache.move_right_and_pop_l1(|_info, _node| {
690                        _node.dealloc::<true>();
691                    }) {
692                        trace_log!("into_iter drop forward parent {parent:?}:{idx}");
693                        cache.push(parent.clone(), idx);
694                        let leaf = parent.get_child_as_leaf(idx);
695                        leaf.dealloc::<true>();
696                    }
697                } else {
698                    while let Some((parent, idx)) = cache.move_left_and_pop_l1(|_info, _node| {
699                        _node.dealloc::<true>();
700                    }) {
701                        trace_log!("into_iter drop forward parent {parent:?}:{idx}");
702                        cache.push(parent.clone(), idx);
703                        let leaf = parent.get_child_as_leaf(idx);
704                        leaf.dealloc::<true>();
705                    }
706                }
707            }
708        }
709    }
710}
711
712/// An owning iterator over the entries of a BTreeMap
713/// Uses PathCache to manage tree traversal and safe deallocation
714///
715/// NOTE: In order to keep the logic simple, we does not implement `DoubleEndedIterator` here
716pub struct IntoIter<K: Ord + Clone + Sized, V: Sized> {
717    /// If true, iterate in reverse order
718    base: Result<IntoIterBase<K, V>, (BTreeMap<K, V>, bool)>,
719}
720
721impl<K: Ord + Clone + Sized, V: Sized> IntoIter<K, V> {
722    #[inline]
723    pub(super) fn new(tree: BTreeMap<K, V>, is_forward: bool) -> Self {
724        Self { base: Err((tree, is_forward)) }
725    }
726
727    /// Return a iterator in reversed direction
728    ///
729    /// IntoIter only implement one way iteration (either forward or backward).
730    /// this will mock Iterator::rev for DoubleEndIterator trait
731    ///
732    /// # Panic
733    ///
734    /// If iteration already started, cannot change the direction
735    #[inline]
736    pub fn rev(self) -> Self {
737        if let Err((tree, _is_forward)) = self.base {
738            Self { base: Err((tree, false)) }
739        } else {
740            panic!("cannot change direction after iteration start");
741        }
742    }
743}
744
745impl<K: Ord + Clone + Sized, V: Sized> Iterator for IntoIter<K, V> {
746    type Item = (K, V);
747
748    #[inline]
749    fn next(&mut self) -> Option<Self::Item> {
750        match &mut self.base {
751            Ok(base) => base.next(),
752            Err((tree, is_forward)) => {
753                self.base = Ok(IntoIterBase::new(tree, *is_forward));
754                if let Ok(base) = &mut self.base {
755                    base.next()
756                } else {
757                    unreachable!();
758                }
759            }
760        }
761    }
762
763    #[inline]
764    fn size_hint(&self) -> (usize, Option<usize>) {
765        let remaining = match &self.base {
766            Ok(base) => base.remaining,
767            Err((tree, _)) => tree.len(),
768        };
769        (remaining, Some(remaining))
770    }
771}
772
773impl<K: Ord + Clone + Sized, V: Sized> ExactSizeIterator for IntoIter<K, V> {
774    #[inline]
775    fn len(&self) -> usize {
776        match &self.base {
777            Ok(base) => base.remaining,
778            Err((tree, _)) => tree.len(),
779        }
780    }
781}
embed_collections/btree/iter.rs

embed_collections/btree/
iter.rs
