embed_btree/bptree/
mod.rs

1/*
2
3# Designer notes
4
5Target scenario:  To maintain slab tree for disk, lets say 1 billion nodes, this design is aim for high fan-out.
6
7Since There're no parent pointer, no fence keys. So we maintain a cache to accelerate the look up for parent nodes.
8
9Since we support combining cursor moving in Entry API (try to merge with previous or next adjacent
10 node). But user can call `remove()` on moved cursor.
11
12## Acceleration Search for finding the parent using PathBuffer
13
14PathBuffer is embedded the the end of TreeInfo, will delay allocation until the first split of leaf,
15which lead to the first InterNode allocation.
16
17- Assume PathBuffer is for Node A, Node B is the right brother of node A. A's ptr is at ParentA[idx]
18  - To find parent for Node B
19    - If idx < last (Cap - 1), then A and B has common parent,
20    - otherwise A and B have no common parent. Should continue iteration to upper PathBuffer. There will be common ancestor until idx < last
21
22- Assume PathBuffer is for Node B, Node A is the left brother of node B, B's ptr is at ParentB[idx]
23  - To find parent for Node A
24    - If idx > 0, then A and B has common parent.
25    - otherwise A and B have no common parent. Should continue iteration to upper PathBuffer. There will be common ancestor until idx > 0
26
27## Rebalance
28
29- When insert on a full LeafNode, we try to move items to left/right brother, to delay split operation.
30
31- One entry removed, current node usage < 50% (the threshold can be adjust according to tree size)
32
33  - we don't need to borrow data from brothers (to avoid trashing), and we have already done borrowing on insert.
34
35  - try to merge data, with left + current < cap, or current + right < cap, or left + current + right == 2 * cap
36
37  - No need to mere 3 -> 1, because before reaching 30% average usage, we already checked 3 -> 2.
38
39- The threshold to check merge for InterNode can be lower (like 30%), to avoid trashing
40
41
42## Future ideas
43
44- dynamically incress InterNode size, or variable size
45
46*/
47
48#[allow(unused_imports)]
49use crate::{print_log, trace_log};
50use core::borrow::Borrow;
51use core::fmt::{self, Debug};
52use core::ops::{Bound, RangeBounds};
53pub(crate) mod cursor;
54pub use cursor::*;
55pub(crate) mod entry;
56use entry::EntryInner;
57pub use entry::{Entry, OccupiedEntry, VacantEntry};
58
59pub(crate) mod helper;
60use helper::*;
61pub(crate) mod node;
62use node::*;
63pub(crate) mod inter;
64use inter::*;
65pub(crate) mod leaf;
66use leaf::*;
67pub mod iter;
68
69pub(crate) mod tree;
70use iter::RangeBase;
71pub use iter::{IntoIter, Iter, IterMut, Keys, Range, RangeMut, Values, ValuesMut};
72use tree::BTreeInner;
73
74#[cfg(test)]
75pub(crate) mod tests;
76
77pub trait Value: Sized + 'static {}
78
79impl<T: Sized + 'static> Value for T {}
80
81pub trait Key: Value + Clone + Ord + 'static {}
82
83impl<T: Value + Clone + Ord + 'static> Key for T {}
84
85/// B+Tree Map for single-threaded usage, optimized for numeric type.
86pub struct BTree<K: Key, V: Value, S: Stats> {
87    pub(crate) inner: BTreeInner<K, V>,
88    // use unsafe to avoid borrow problems
89    pub(crate) stats: S,
90}
91
92#[allow(private_bounds)]
93pub trait Stats: StatsPriv {}
94
95pub(crate) trait StatsPriv: Default + Send + Debug + 'static {
96    type EntryInner<'a, K, V>: EntryInner<K, V>
97    where
98        K: Key + 'a,
99        V: Value + 'a;
100
101    type PathBufferRef<'a>: PathBuffer
102    where
103        Self: 'a;
104
105    // owned for IntoIter and drop
106    type PathBuffer: PathBuffer + 'static;
107
108    type BufferStack: Default;
109
110    // the stack part pass with mut reference, avoid moving
111    fn get_cache<'a, K>(
112        &'a mut self, stack: &'a mut Self::BufferStack, root: Option<InterNode<K>>,
113    ) -> Self::PathBufferRef<'a>;
114
115    fn take_cache<K>(self, root: Option<InterNode<K>>) -> Self::PathBuffer;
116
117    fn search_entry<'a, K: Key, V: Value>(
118        tree: &'a mut BTree<K, V, Self>, key: K,
119    ) -> Entry<'a, K, V, Self>
120    where
121        Self: Stats;
122
123    /// seek first or last entry
124    fn seek_entry<'a, K: Key, V: Value, const FIRST: bool>(
125        tree: &'a mut BTree<K, V, Self>,
126    ) -> Option<OccupiedEntry<'a, K, V, Self>>
127    where
128        Self: Stats;
129
130    #[cfg(test)]
131    fn init_count(&mut self, leaf_count: usize, inter_count: u32);
132
133    #[cfg(test)]
134    fn assert_leaf_count(&self, _leaf_count: usize) {}
135
136    #[cfg(test)]
137    fn assert_inter_count(&self, _inter_count: usize) {}
138}
139
140#[cfg(all(test, feature = "trace_log"))]
141#[repr(u32)]
142enum TestFlag {
143    LeafSplit = 1,
144    InterSplit = 1 << 1,
145    LeafMoveLeft = 1 << 2,
146    LeafMoveRight = 1 << 3,
147    LeafMergeLeft = 1 << 4,
148    LeafMergeRight = 1 << 5,
149    InterMoveLeft = 1 << 6,
150    InterMoveLeftFirst = 1 << 7,
151    InterMoveRight = 1 << 8,
152    InterMoveRightLast = 1 << 9,
153    InterMergeLeft = 1 << 10,
154    InterMergeRight = 1 << 11,
155    UpdateSepKey = 1 << 12,
156    RemoveOnlyChild = 1 << 13,
157    RemoveChildFirst = 1 << 14,
158    RemoveChildMid = 1 << 15,
159    RemoveChildLast = 1 << 16,
160}
161
162unsafe impl<K: Key + Send, V: Value + Send, S: Stats> Send for BTree<K, V, S> {}
163unsafe impl<K: Key + Send, V: Value + Send, S: Stats> Sync for BTree<K, V, S> {}
164
165#[cfg(feature = "std")]
166impl<K: Key, V: Value, S: Stats> std::panic::RefUnwindSafe for BTree<K, V, S> {}
167
168impl<K: Key, V: Value, S: Stats> BTree<K, V, S> {
169    /// Create a new empty BTreeMap
170    pub fn new() -> Self {
171        Self {
172            inner: BTreeInner {
173                root: None,
174                len: 0,
175                _phan: Default::default(),
176                #[cfg(all(test, feature = "trace_log"))]
177                triggers: 0,
178            },
179            stats: S::default(),
180        }
181    }
182
183    /// Returns the number of elements in the map
184    #[inline(always)]
185    pub fn len(&self) -> usize {
186        self.inner.len
187    }
188
189    /// Returns true if the map is empty
190    #[inline(always)]
191    pub fn is_empty(&self) -> bool {
192        self.inner.len == 0
193    }
194
195    /// return (cap_of_inter_node, cap_of_leaf_node)
196    #[inline]
197    pub const fn cap() -> (u8, u8) {
198        let inter_cap = InterNode::<K>::cap();
199        let leaf_cap = LeafNode::<K, V>::cap();
200        (inter_cap, leaf_cap)
201    }
202
203    /// When root is leaf, returns 1, otherwise return the number of layers of inter node
204    #[inline(always)]
205    pub fn height(&self) -> u8 {
206        if let Some(root) = self.inner.get_root() {
207            return root.height() + 1;
208        }
209        1
210    }
211
212    #[inline(always)]
213    fn find<Q>(&self, key: &Q) -> Option<(LeafNode<K, V>, u8)>
214    where
215        K: Borrow<Q>,
216        Q: Ord + ?Sized,
217    {
218        let leaf = self.inner.search_leaf_with(|inter| inter.find_leaf::<V, Q>(key))?;
219        let (idx, is_equal) = leaf.search(key);
220        trace_log!("find leaf {leaf:?} {idx} exist {is_equal}");
221        if is_equal { Some((leaf, idx)) } else { None }
222    }
223
224    /// Returns true if the map contains the key
225    #[inline(always)]
226    pub fn contains_key<Q>(&self, key: &Q) -> bool
227    where
228        K: Borrow<Q>,
229        Q: Ord + ?Sized,
230    {
231        self.find::<Q>(key).is_some()
232    }
233
234    /// Returns a reference to the value corresponding to the key
235    pub fn get<Q>(&self, key: &Q) -> Option<&V>
236    where
237        K: Borrow<Q>,
238        Q: Ord + ?Sized,
239    {
240        if let Some((leaf, idx)) = self.find::<Q>(key) {
241            let value = unsafe { leaf.value_ptr(idx) };
242            debug_assert!(!value.is_null());
243            Some(unsafe { (*value).assume_init_ref() })
244        } else {
245            None
246        }
247    }
248
249    /// Returns a mutable reference to the value corresponding to the key
250    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
251    where
252        K: Borrow<Q>,
253        Q: Ord + ?Sized,
254    {
255        if let Some((mut leaf, idx)) = self.find::<Q>(key) {
256            let value = unsafe { leaf.value_ptr_mut(idx) };
257            debug_assert!(!value.is_null());
258            Some(unsafe { (*value).assume_init_mut() })
259        } else {
260            None
261        }
262    }
263
264    /// Insert a key-value pair into the map
265    /// Returns the old value if the key already existed
266    #[inline]
267    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
268        let mut is_seq = true;
269        let mut stack = S::BufferStack::default();
270        let (o_leaf, mut cache) =
271            self.inner.search_leaf_with_cache(&mut stack, &mut self.stats, |inter, _cache| {
272                inter.find_leaf_with_cache_smart::<K, V, _>(_cache, &key, &mut is_seq)
273            });
274        if let Some(mut leaf) = o_leaf {
275            let (idx, is_equal) = leaf.search_smart(&key, is_seq);
276            if !is_equal {
277                self.inner.len += 1;
278                // Get the leaf node where we should insert
279                let count = leaf.key_count();
280                // Check if leaf has space
281                if count < LeafNode::<K, V>::cap() {
282                    leaf.insert_no_split_with_idx(idx, key, value);
283                } else {
284                    // Leaf is full, need to split
285                    self.inner.insert_with_split(&mut cache, key, value, leaf, idx);
286                }
287                None
288            } else {
289                Some(leaf.replace(idx, value))
290            }
291        } else {
292            self.inner.init_empty(key, value);
293            None
294        }
295    }
296
297    /// Remove a key from the map, returning the value if it existed
298    ///
299    /// #Example
300    ///
301    /// ```
302    /// use embed_btree::BTreeMap;
303    /// let mut map = BTreeMap::new();
304    /// map.insert(1, "a");
305    /// assert_eq!(map.remove(&1), Some("a"));
306    /// assert_eq!(map.remove(&1), None);
307    /// ```
308    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
309    where
310        K: Borrow<Q>,
311        Q: Ord + ?Sized,
312    {
313        let mut stack = S::BufferStack::default();
314        let (o_leaf, mut cache) =
315            self.inner.search_leaf_with_cache(&mut stack, &mut self.stats, |inter, _cache| {
316                inter.find_leaf_with_cache::<V, Q, _>(_cache, key)
317            });
318        let mut leaf = o_leaf?;
319        let (idx, is_equal) = leaf.search(key);
320        if is_equal {
321            trace_log!("{leaf:?} remove {idx}");
322            let val = leaf.remove_value_no_borrow(idx);
323            self.inner.len -= 1;
324            // Check for underflow and handle merge
325            let new_count = leaf.key_count();
326            let min_count = LeafNode::<K, V>::cap() >> 1;
327            if new_count < min_count && self.inner.root_is_inter() {
328                // The cache should already contain the path from the entry lookup
329                self.inner.handle_leaf_underflow(&mut cache, leaf, true);
330            }
331            Some(val)
332        } else {
333            None
334        }
335    }
336
337    /// Remove a key from the map, returning the (key, value) if it existed
338    ///
339    /// #Example
340    ///
341    /// ```
342    /// use embed_btree::BTreeMap;
343    /// let mut map = BTreeMap::new();
344    /// map.insert(1, "a");
345    /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
346    /// assert_eq!(map.remove_entry(&1), None);
347    /// ```
348    pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
349    where
350        K: Borrow<Q>,
351        Q: Ord + ?Sized,
352    {
353        let mut stack = S::BufferStack::default();
354        let (o_leaf, mut cache) =
355            self.inner.search_leaf_with_cache(&mut stack, &mut self.stats, |inter, _cache| {
356                inter.find_leaf_with_cache::<V, Q, _>(_cache, key)
357            });
358        let mut leaf = o_leaf?;
359        let (idx, is_equal) = leaf.search(key);
360        if is_equal {
361            trace_log!("{leaf:?} remove {idx}");
362            let (_key, val) = leaf.remove_pair_no_borrow(idx);
363            self.inner.len -= 1;
364            // Check for underflow and handle merge
365            let new_count = leaf.key_count();
366            let min_count = LeafNode::<K, V>::cap() >> 1;
367            if new_count < min_count && self.inner.root_is_inter() {
368                // The cache should already contain the path from the entry lookup
369                self.inner.handle_leaf_underflow(&mut cache, leaf, true);
370            }
371            Some((_key, val))
372        } else {
373            None
374        }
375    }
376
377    /// Returns an entry to the key in the map
378    #[inline]
379    pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V, S> {
380        <S as StatsPriv>::search_entry::<K, V>(self, key)
381    }
382
383    /// Returns an entry to the first key in the map
384    /// Returns `None` if the map is empty
385    #[inline]
386    pub fn first_entry<'a>(&'a mut self) -> Option<OccupiedEntry<'a, K, V, S>> {
387        <S as StatsPriv>::seek_entry::<K, V, true>(self)
388    }
389
390    /// Returns an entry to the last key in the map
391    /// Returns `None` if the map is empty
392    #[inline]
393    pub fn last_entry<'a>(&'a mut self) -> Option<OccupiedEntry<'a, K, V, S>> {
394        <S as StatsPriv>::seek_entry::<K, V, false>(self)
395    }
396
397    /// Removes and returns the first key-value pair in the map
398    /// Returns `None` if the map is empty
399    #[inline]
400    pub fn pop_first(&mut self) -> Option<(K, V)> {
401        self.first_entry().map(|entry| entry.remove_entry())
402    }
403
404    /// Removes and returns the last key-value pair in the map
405    /// Returns `None` if the map is empty
406    #[inline]
407    pub fn pop_last(&mut self) -> Option<(K, V)> {
408        self.last_entry().map(|entry| entry.remove_entry())
409    }
410
411    /// Perform removal in batch mode and return the last item removed
412    ///
413    /// NOTE: this function speed up by skipping the underflow of LeafNode until the last operation.
414    pub fn remove_range<R>(&mut self, range: R) -> Option<(K, V)>
415    where
416        R: RangeBounds<K>,
417    {
418        self.remove_range_with::<R, _>(range, |_, _| {})
419    }
420
421    /// Perform removal in batch mode and return the last item removed
422    ///
423    /// On each removal, callback function `cb` is invoke with (ref of key, ref of value)
424    ///
425    /// NOTE: this function speed up by skipping the underflow of LeafNode until the last operation.
426    #[inline]
427    pub fn remove_range_with<R, F>(&mut self, range: R, mut cb: F) -> Option<(K, V)>
428    where
429        R: RangeBounds<K>,
430        F: FnMut(&K, &V),
431    {
432        macro_rules! end_contains {
433            ($key: expr) => {{
434                match range.end_bound() {
435                    Bound::Excluded(k) => $key < k,
436                    Bound::Included(k) => $key <= k,
437                    Bound::Unbounded => true,
438                }
439            }};
440        }
441        // Note: do not use find_leaf_with_bound, it's a different behavior
442        let mut ent = match range.start_bound() {
443            Bound::Excluded(k) => match self.entry(k.clone()).move_forward() {
444                Ok(ent) => {
445                    if end_contains!(ent.key()) {
446                        ent
447                    } else {
448                        return None;
449                    }
450                }
451                Err(_) => return None,
452            },
453            Bound::Included(k) => match self.entry(k.clone()) {
454                Entry::Occupied(ent) => ent,
455                Entry::Vacant(ent) => match ent.move_forward() {
456                    Ok(ent) => {
457                        if end_contains!(ent.key()) {
458                            ent
459                        } else {
460                            return None;
461                        }
462                    }
463                    Err(_) => return None,
464                },
465            },
466            Bound::Unbounded => self.first_entry()?,
467        };
468        loop {
469            if let Some((_next_k, _next_v)) = ent.peek_forward()
470                && end_contains!(_next_k)
471            {
472                let next_key = _next_k.clone();
473                let (_k, _v) = ent._remove_entry(false);
474                cb(&_k, &_v);
475                if let Entry::Occupied(_ent) = self.entry(next_key) {
476                    ent = _ent;
477                    continue;
478                } else {
479                    unreachable!();
480                }
481            }
482            let (_k, _v) = ent._remove_entry(true);
483            cb(&_k, &_v);
484            return Some((_k, _v));
485        }
486    }
487
488    /// Dump the entire tree structure for debugging
489    #[cfg(test)]
490    pub fn dump(&self)
491    where
492        K: Debug,
493        V: Debug,
494    {
495        print_log!("=== BTreeMap Dump ===");
496        print_log!("Length: {}", self.inner.len);
497        if let Some(root) = self.inner.get_root() {
498            self.dump_node(&root, 0);
499        } else {
500            print_log!("(empty)");
501        }
502        print_log!("=====================");
503    }
504
505    #[cfg(test)]
506    fn dump_node(&self, node: &Node<K, V>, depth: usize)
507    where
508        K: Debug,
509        V: Debug,
510    {
511        match node {
512            Node::Leaf(leaf) => {
513                std::print!("{:indent$}", "", indent = depth * 2);
514                print_log!("{}", leaf);
515            }
516            Node::Inter(inter) => {
517                std::print!("{:indent$}", "", indent = depth * 2);
518                print_log!("{}", inter);
519                // Dump children
520                let count = inter.key_count() as u8;
521                for i in 0..=count {
522                    unsafe {
523                        let child_ptr = *inter.child_ptr(i);
524                        if !child_ptr.is_null() {
525                            let child_node = if (*child_ptr).is_leaf() {
526                                Node::Leaf(LeafNode::<K, V>::from_header(child_ptr))
527                            } else {
528                                Node::Inter(InterNode::<K>::from_header(child_ptr))
529                            };
530                            self.dump_node(&child_node, depth + 1);
531                        }
532                    }
533                }
534            }
535        }
536    }
537
538    /// Validate the entire tree structure
539    /// Uses the same traversal logic as Drop to avoid recursion
540    pub fn validate(&self)
541    where
542        K: Debug,
543        V: Debug,
544    {
545        self.inner.validate::<S>()
546    }
547
548    /// Returns the first key-value pair in the map
549    /// Returns `None` if the map is empty
550    #[inline]
551    pub fn first_key_value(&self) -> Option<(&K, &V)> {
552        let leaf = self.inner.search_leaf_with(InterNode::<K>::find_first_leaf::<V>)?;
553        debug_assert!(leaf.key_count() > 0);
554        unsafe {
555            let key = (*leaf.key_ptr(0)).assume_init_ref();
556            let value = (*leaf.value_ptr(0)).assume_init_ref();
557            Some((key, value))
558        }
559    }
560
561    /// Returns the last key-value pair in the map
562    /// Returns `None` if the map is empty
563    #[inline]
564    pub fn last_key_value(&self) -> Option<(&K, &V)> {
565        let leaf = self.inner.search_leaf_with(InterNode::<K>::find_last_leaf::<V>)?;
566        let count = leaf.key_count();
567        debug_assert!(count > 0);
568        unsafe {
569            let last_idx = count - 1;
570            let key = (*leaf.key_ptr(last_idx)).assume_init_ref();
571            let value = (*leaf.value_ptr(last_idx)).assume_init_ref();
572            Some((key, value))
573        }
574    }
575
576    /// Returns an iterator over the map's entries
577    #[inline]
578    pub fn iter(&self) -> Iter<'_, K, V> {
579        Iter::new(self.find_first_and_last_leaf(), self.inner.len)
580    }
581
582    /// Returns a mutable iterator over the map's entries
583    #[inline]
584    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
585        IterMut::new(self.find_first_and_last_leaf(), self.inner.len)
586    }
587
588    /// Return a consuming iterator in reversed order
589    #[inline]
590    pub fn into_iter_rev(self) -> IntoIter<K, V, S> {
591        IntoIter::new(self, false)
592    }
593
594    /// Returns an iterator over the map's keys
595    #[inline]
596    pub fn keys(&self) -> Keys<'_, K, V> {
597        Keys::new(self.iter())
598    }
599
600    /// Returns an iterator over the map's values
601    #[inline]
602    pub fn values(&self) -> Values<'_, K, V> {
603        Values::new(self.iter())
604    }
605
606    /// Returns a mutable iterator over the map's values
607    #[inline]
608    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
609        ValuesMut::new(self.iter_mut())
610    }
611
612    #[inline]
613    fn find_first_and_last_leaf(&self) -> Option<(LeafNode<K, V>, LeafNode<K, V>)> {
614        let root = self.inner.root?;
615        if !Node::<K, V>::root_is_leaf(root) {
616            let inter = InterNode::<K>::from(root);
617            Some((inter.clone().find_first_leaf::<V>(), inter.find_last_leaf::<V>()))
618        } else {
619            let leaf = LeafNode::<K, V>::from_root_ptr(root);
620            Some((leaf.clone(), leaf))
621        }
622    }
623
624    /// Internal helper to find range bounds
625    /// Returns (front_leaf, front_idx, back_leaf, back_idx) where both leaves are Some or both are None
626    #[inline]
627    fn find_range_bounds<R>(&self, range: R) -> Option<RangeBase<'_, K, V>>
628    where
629        R: RangeBounds<K>,
630    {
631        let root = self.inner.get_root()?;
632        let (front_leaf, front_idx) = root.find_leaf_with_bound(range.start_bound(), true);
633        let (back_leaf, back_idx) = root.find_leaf_with_bound(range.end_bound(), false);
634        Some(RangeBase::new(front_leaf, front_idx, back_leaf, back_idx))
635    }
636
637    /// Returns an iterator over a sub-range of entries in the map
638    #[inline]
639    pub fn range<R>(&self, range: R) -> Range<'_, K, V>
640    where
641        R: RangeBounds<K>,
642    {
643        Range::new(self.find_range_bounds(range))
644    }
645
646    /// Returns a mutable iterator over a sub-range of entries in the map
647    #[inline]
648    pub fn range_mut<R>(&mut self, range: R) -> RangeMut<'_, K, V>
649    where
650        R: RangeBounds<K>,
651    {
652        RangeMut::new(self.find_range_bounds(range))
653    }
654
655    /// Returns a cursor positioned at the first entry of the map.
656    /// Returns `None` if the map is empty.
657    #[inline]
658    pub fn first_cursor(&self) -> Cursor<'_, K, V> {
659        if let Some(leaf) = self.inner.search_leaf_with(InterNode::<K>::find_first_leaf::<V>)
660            && leaf.key_count() > 0
661        {
662            return Cursor {
663                leaf: Some(leaf),
664                is_exist: true,
665                idx: 0,
666                _marker: Default::default(),
667            };
668        }
669        Cursor { leaf: None, is_exist: true, idx: 0, _marker: Default::default() }
670    }
671
672    /// Returns a cursor positioned at the last entry of the map.
673    /// Returns `None` if the map is empty.
674    #[inline]
675    pub fn last_cursor(&self) -> Cursor<'_, K, V> {
676        if let Some(leaf) = self.inner.search_leaf_with(InterNode::<K>::find_last_leaf::<V>) {
677            let count = leaf.key_count();
678            if count > 0 {
679                return Cursor {
680                    leaf: Some(leaf),
681                    idx: count - 1,
682                    is_exist: true,
683                    _marker: Default::default(),
684                };
685            }
686        }
687        Cursor { leaf: None, idx: 0, is_exist: false, _marker: Default::default() }
688    }
689
690    /// Returns a cursor positioned at the given key.
691    ///
692    /// NOTE: There's slight different for existing/non-existing key, refer to the doc of [Cursor]
693    #[inline]
694    pub fn cursor<Q>(&self, key: &Q) -> Cursor<'_, K, V>
695    where
696        K: Borrow<Q>,
697        Q: Ord + ?Sized,
698    {
699        if let Some(leaf) = self.inner.search_leaf_with(|inter| inter.find_leaf::<V, Q>(key)) {
700            let (idx, is_exist) = leaf.search(key);
701            Cursor { leaf: Some(leaf), idx, is_exist, _marker: Default::default() }
702        } else {
703            Cursor { leaf: None, idx: 0, is_exist: false, _marker: Default::default() }
704        }
705    }
706
707    #[cfg(test)]
708    fn assert_leaf_count(&self, leaf_count: usize) {
709        if self.inner.root.is_some() {
710            self.stats.assert_leaf_count(leaf_count)
711        } else {
712            assert_eq!(leaf_count, 0);
713        }
714    }
715
716    #[cfg(test)]
717    fn assert_inter_count(&self, inter_count: usize) {
718        self.stats.assert_inter_count(inter_count)
719    }
720}
721
722impl<K: Key, V: Value, S: Stats> Default for BTree<K, V, S> {
723    fn default() -> Self {
724        Self::new()
725    }
726}
727
728impl<K: Key, V: Value, S: Stats> Drop for BTree<K, V, S> {
729    fn drop(&mut self) {
730        if let Some(root) = self.inner.root {
731            if Node::<K, V>::root_is_leaf(root) {
732                let leaf = LeafNode::<K, V>::from_root_ptr(root);
733                leaf.dealloc::<true>();
734            } else {
735                let inter = InterNode::<K>::from(root);
736                let mut stack = S::BufferStack::default();
737                let mut cache = self.stats.get_cache(&mut stack, Some(inter.clone()));
738                let mut cur = inter.find_first_leaf_with_cache::<V, _>(&mut cache);
739                cur.dealloc::<true>();
740                // To navigate to next leaf,
741                // return None when reach the end
742                while let Some((parent, idx)) =
743                    cache.move_path_right_and_pop_l1(|_cache, node| node.dealloc::<true>())
744                {
745                    cache.push_path(parent.clone(), idx);
746                    cur = parent.get_child_as_leaf::<V>(idx);
747                    cur.dealloc::<true>();
748                }
749            }
750        }
751    }
752}
753
754impl<K: Key, V: Value, S: Stats> IntoIterator for BTree<K, V, S> {
755    type Item = (K, V);
756    type IntoIter = IntoIter<K, V, S>;
757
758    #[inline]
759    fn into_iter(self) -> Self::IntoIter {
760        IntoIter::new(self, true)
761    }
762}
763
764impl<'a, K: Key, V: Value, S: Stats> IntoIterator for &'a BTree<K, V, S> {
765    type Item = (&'a K, &'a V);
766    type IntoIter = Iter<'a, K, V>;
767
768    #[inline]
769    fn into_iter(self) -> Self::IntoIter {
770        self.iter()
771    }
772}
773
774impl<'a, K: Key, V: Value, S: Stats> IntoIterator for &'a mut BTree<K, V, S> {
775    type Item = (&'a K, &'a mut V);
776    type IntoIter = IterMut<'a, K, V>;
777
778    #[inline]
779    fn into_iter(self) -> Self::IntoIter {
780        self.iter_mut()
781    }
782}
783
784impl<K: Key, V: Value + PartialEq, S: Stats> PartialEq for BTree<K, V, S> {
785    fn eq(&self, other: &Self) -> bool {
786        let mut this_iter = self.iter();
787        let mut other_iter = other.iter();
788        loop {
789            let this_item = this_iter.next();
790            let other_item = other_iter.next();
791            if this_item == other_item {
792                if this_item.is_some() {
793                    continue;
794                } else {
795                    return true;
796                }
797            } else {
798                return false;
799            }
800        }
801    }
802}
803
804impl<K: Key + Debug, V: Value + Debug, S: Stats> Debug for BTree<K, V, S> {
805    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
806        let _ = write!(f, "{{");
807        let mut iter = self.iter();
808        while let Some((k, v)) = iter.next() {
809            let _ = write!(f, "{k:?}:{v:?}");
810            if iter.len() > 0 {
811                let _ = write!(f, ",");
812            }
813        }
814        write!(f, "}}")
815    }
816}
embed_btree/bptree/mod.rs

embed_btree/bptree/
mod.rs
