embed-btree 0.4.1

/*

# Designer notes

Target scenario:  To maintain slab tree for disk, lets say 1 billion nodes, this design is aim for high fan-out.

Since There're no parent pointer, no fence keys. So we maintain a cache to accelerate the look up for parent nodes.

Since we support combining cursor moving in Entry API (try to merge with previous or next adjacent
 node). But user can call `remove()` on moved cursor.

## Acceleration Search for finding the parent using PathBuffer

PathBuffer is embedded the the end of TreeInfo, will delay allocation until the first split of leaf,
which lead to the first InterNode allocation.

- Assume PathBuffer is for Node A, Node B is the right brother of node A. A's ptr is at ParentA[idx]
  - To find parent for Node B
    - If idx < last (Cap - 1), then A and B has common parent,
    - otherwise A and B have no common parent. Should continue iteration to upper PathBuffer. There will be common ancestor until idx < last

- Assume PathBuffer is for Node B, Node A is the left brother of node B, B's ptr is at ParentB[idx]
  - To find parent for Node A
    - If idx > 0, then A and B has common parent.
    - otherwise A and B have no common parent. Should continue iteration to upper PathBuffer. There will be common ancestor until idx > 0

## Rebalance

- When insert on a full LeafNode, we try to move items to left/right brother, to delay split operation.

- One entry removed, current node usage < 50% (the threshold can be adjust according to tree size)

  - we don't need to borrow data from brothers (to avoid trashing), and we have already done borrowing on insert.

  - try to merge data, with left + current < cap, or current + right < cap, or left + current + right == 2 * cap

  - No need to mere 3 -> 1, because before reaching 30% average usage, we already checked 3 -> 2.

- The threshold to check merge for InterNode can be lower (like 30%), to avoid trashing


## Future ideas

- dynamically incress InterNode size, or variable size

*/

#[allow(unused_imports)]
use crate::{print_log, trace_log};
use core::borrow::Borrow;
use core::fmt::{self, Debug};
use core::ops::{Bound, RangeBounds};
pub(crate) mod cursor;
pub use cursor::*;
pub(crate) mod entry;
use entry::EntryInner;
pub use entry::{Entry, OccupiedEntry, VacantEntry};

pub(crate) mod helper;
use helper::*;
pub(crate) mod node;
use node::*;
pub(crate) mod inter;
use inter::*;
pub(crate) mod leaf;
use leaf::*;
pub mod iter;

pub(crate) mod tree;
use iter::RangeBase;
pub use iter::{IntoIter, Iter, IterMut, Keys, Range, RangeMut, Values, ValuesMut};
use tree::BTreeInner;

#[cfg(test)]
pub(crate) mod tests;

pub trait Value: Sized + 'static {}

impl<T: Sized + 'static> Value for T {}

pub trait Key: Value + Clone + Ord + 'static {}

impl<T: Value + Clone + Ord + 'static> Key for T {}

/// B+Tree Map for single-threaded usage, optimized for numeric type.
pub struct BTree<K: Key, V: Value, S: Stats> {
    pub(crate) inner: BTreeInner<K, V>,
    // use unsafe to avoid borrow problems
    pub(crate) stats: S,
}

#[allow(private_bounds)]
pub trait Stats: StatsPriv {}

pub(crate) trait StatsPriv: Default + Send + Debug + 'static {
    type EntryInner<'a, K, V>: EntryInner<K, V>
    where
        K: Key + 'a,
        V: Value + 'a;

    type PathBufferRef<'a>: PathBuffer
    where
        Self: 'a;

    // owned for IntoIter and drop
    type PathBuffer: PathBuffer + 'static;

    type BufferStack: Default;

    // the stack part pass with mut reference, avoid moving
    fn get_cache<'a, K>(
        &'a mut self, stack: &'a mut Self::BufferStack, root: Option<InterNode<K>>,
    ) -> Self::PathBufferRef<'a>;

    fn take_cache<K>(self, root: Option<InterNode<K>>) -> Self::PathBuffer;

    fn search_entry<'a, K: Key, V: Value>(
        tree: &'a mut BTree<K, V, Self>, key: K,
    ) -> Entry<'a, K, V, Self>
    where
        Self: Stats;

    /// seek first or last entry
    fn seek_entry<'a, K: Key, V: Value, const FIRST: bool>(
        tree: &'a mut BTree<K, V, Self>,
    ) -> Option<OccupiedEntry<'a, K, V, Self>>
    where
        Self: Stats;

    #[cfg(test)]
    fn init_count(&mut self, leaf_count: usize, inter_count: u32);

    #[cfg(test)]
    fn assert_leaf_count(&self, _leaf_count: usize) {}

    #[cfg(test)]
    fn assert_inter_count(&self, _inter_count: usize) {}
}

#[cfg(all(test, feature = "trace_log"))]
#[repr(u32)]
enum TestFlag {
    LeafSplit = 1,
    InterSplit = 1 << 1,
    LeafMoveLeft = 1 << 2,
    LeafMoveRight = 1 << 3,
    LeafMergeLeft = 1 << 4,
    LeafMergeRight = 1 << 5,
    InterMoveLeft = 1 << 6,
    InterMoveLeftFirst = 1 << 7,
    InterMoveRight = 1 << 8,
    InterMoveRightLast = 1 << 9,
    InterMergeLeft = 1 << 10,
    InterMergeRight = 1 << 11,
    UpdateSepKey = 1 << 12,
    RemoveOnlyChild = 1 << 13,
    RemoveChildFirst = 1 << 14,
    RemoveChildMid = 1 << 15,
    RemoveChildLast = 1 << 16,
}

unsafe impl<K: Key + Send, V: Value + Send, S: Stats> Send for BTree<K, V, S> {}
unsafe impl<K: Key + Send, V: Value + Send, S: Stats> Sync for BTree<K, V, S> {}

#[cfg(feature = "std")]
impl<K: Key, V: Value, S: Stats> std::panic::RefUnwindSafe for BTree<K, V, S> {}

impl<K: Key, V: Value, S: Stats> BTree<K, V, S> {
    /// Create a new empty BTreeMap
    pub fn new() -> Self {
        Self {
            inner: BTreeInner {
                root: None,
                len: 0,
                _phan: Default::default(),
                #[cfg(all(test, feature = "trace_log"))]
                triggers: 0,
            },
            stats: S::default(),
        }
    }

    /// Returns the number of elements in the map
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.inner.len
    }

    /// Returns true if the map is empty
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.inner.len == 0
    }

    /// return (cap_of_inter_node, cap_of_leaf_node)
    #[inline]
    pub const fn cap() -> (u8, u8) {
        let inter_cap = InterNode::<K>::cap();
        let leaf_cap = LeafNode::<K, V>::cap();
        (inter_cap, leaf_cap)
    }

    /// When root is leaf, returns 1, otherwise return the number of layers of inter node
    #[inline(always)]
    pub fn height(&self) -> u8 {
        if let Some(root) = self.inner.get_root() {
            return root.height() + 1;
        }
        1
    }

    #[inline(always)]
    fn find<Q>(&self, key: &Q) -> Option<(LeafNode<K, V>, u8)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let leaf = self.inner.search_leaf_with(|inter| inter.find_leaf::<V, Q>(key))?;
        let (idx, is_equal) = leaf.search(key);
        trace_log!("find leaf {leaf:?} {idx} exist {is_equal}");
        if is_equal { Some((leaf, idx)) } else { None }
    }

    /// Returns true if the map contains the key
    #[inline(always)]
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.find::<Q>(key).is_some()
    }

    /// Returns a reference to the value corresponding to the key
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if let Some((leaf, idx)) = self.find::<Q>(key) {
            let value = unsafe { leaf.value_ptr(idx) };
            debug_assert!(!value.is_null());
            Some(unsafe { (*value).assume_init_ref() })
        } else {
            None
        }
    }

    /// Returns a mutable reference to the value corresponding to the key
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if let Some((mut leaf, idx)) = self.find::<Q>(key) {
            let value = unsafe { leaf.value_ptr_mut(idx) };
            debug_assert!(!value.is_null());
            Some(unsafe { (*value).assume_init_mut() })
        } else {
            None
        }
    }

    /// Insert a key-value pair into the map
    /// Returns the old value if the key already existed
    #[inline]
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        let mut is_seq = true;
        let mut stack = S::BufferStack::default();
        let (o_leaf, mut cache) =
            self.inner.search_leaf_with_cache(&mut stack, &mut self.stats, |inter, _cache| {
                inter.find_leaf_with_cache_smart::<K, V, _>(_cache, &key, &mut is_seq)
            });
        if let Some(mut leaf) = o_leaf {
            let (idx, is_equal) = leaf.search_smart(&key, is_seq);
            if !is_equal {
                self.inner.len += 1;
                // Get the leaf node where we should insert
                let count = leaf.key_count();
                // Check if leaf has space
                if count < LeafNode::<K, V>::cap() {
                    leaf.insert_no_split_with_idx(idx, key, value);
                } else {
                    // Leaf is full, need to split
                    self.inner.insert_with_split(&mut cache, key, value, leaf, idx);
                }
                None
            } else {
                Some(leaf.replace(idx, value))
            }
        } else {
            self.inner.init_empty(key, value);
            None
        }
    }

    /// Remove a key from the map, returning the value if it existed
    ///
    /// #Example
    ///
    /// ```
    /// use embed_btree::BTreeMap;
    /// let mut map = BTreeMap::new();
    /// map.insert(1, "a");
    /// assert_eq!(map.remove(&1), Some("a"));
    /// assert_eq!(map.remove(&1), None);
    /// ```
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut stack = S::BufferStack::default();
        let (o_leaf, mut cache) =
            self.inner.search_leaf_with_cache(&mut stack, &mut self.stats, |inter, _cache| {
                inter.find_leaf_with_cache::<V, Q, _>(_cache, key)
            });
        let mut leaf = o_leaf?;
        let (idx, is_equal) = leaf.search(key);
        if is_equal {
            trace_log!("{leaf:?} remove {idx}");
            let val = leaf.remove_value_no_borrow(idx);
            self.inner.len -= 1;
            // Check for underflow and handle merge
            let new_count = leaf.key_count();
            let min_count = LeafNode::<K, V>::cap() >> 1;
            if new_count < min_count && self.inner.root_is_inter() {
                // The cache should already contain the path from the entry lookup
                self.inner.handle_leaf_underflow(&mut cache, leaf, true);
            }
            Some(val)
        } else {
            None
        }
    }

    /// Remove a key from the map, returning the (key, value) if it existed
    ///
    /// #Example
    ///
    /// ```
    /// use embed_btree::BTreeMap;
    /// let mut map = BTreeMap::new();
    /// map.insert(1, "a");
    /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
    /// assert_eq!(map.remove_entry(&1), None);
    /// ```
    pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut stack = S::BufferStack::default();
        let (o_leaf, mut cache) =
            self.inner.search_leaf_with_cache(&mut stack, &mut self.stats, |inter, _cache| {
                inter.find_leaf_with_cache::<V, Q, _>(_cache, key)
            });
        let mut leaf = o_leaf?;
        let (idx, is_equal) = leaf.search(key);
        if is_equal {
            trace_log!("{leaf:?} remove {idx}");
            let (_key, val) = leaf.remove_pair_no_borrow(idx);
            self.inner.len -= 1;
            // Check for underflow and handle merge
            let new_count = leaf.key_count();
            let min_count = LeafNode::<K, V>::cap() >> 1;
            if new_count < min_count && self.inner.root_is_inter() {
                // The cache should already contain the path from the entry lookup
                self.inner.handle_leaf_underflow(&mut cache, leaf, true);
            }
            Some((_key, val))
        } else {
            None
        }
    }

    /// Returns an entry to the key in the map
    #[inline]
    pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V, S> {
        <S as StatsPriv>::search_entry::<K, V>(self, key)
    }

    /// Returns an entry to the first key in the map
    /// Returns `None` if the map is empty
    #[inline]
    pub fn first_entry<'a>(&'a mut self) -> Option<OccupiedEntry<'a, K, V, S>> {
        <S as StatsPriv>::seek_entry::<K, V, true>(self)
    }

    /// Returns an entry to the last key in the map
    /// Returns `None` if the map is empty
    #[inline]
    pub fn last_entry<'a>(&'a mut self) -> Option<OccupiedEntry<'a, K, V, S>> {
        <S as StatsPriv>::seek_entry::<K, V, false>(self)
    }

    /// Removes and returns the first key-value pair in the map
    /// Returns `None` if the map is empty
    #[inline]
    pub fn pop_first(&mut self) -> Option<(K, V)> {
        self.first_entry().map(|entry| entry.remove_entry())
    }

    /// Removes and returns the last key-value pair in the map
    /// Returns `None` if the map is empty
    #[inline]
    pub fn pop_last(&mut self) -> Option<(K, V)> {
        self.last_entry().map(|entry| entry.remove_entry())
    }

    /// Perform removal in batch mode and return the last item removed
    ///
    /// NOTE: this function speed up by skipping the underflow of LeafNode until the last operation.
    pub fn remove_range<R>(&mut self, range: R) -> Option<(K, V)>
    where
        R: RangeBounds<K>,
    {
        self.remove_range_with::<R, _>(range, |_, _| {})
    }

    /// Perform removal in batch mode and return the last item removed
    ///
    /// On each removal, callback function `cb` is invoke with (ref of key, ref of value)
    ///
    /// NOTE: this function speed up by skipping the underflow of LeafNode until the last operation.
    #[inline]
    pub fn remove_range_with<R, F>(&mut self, range: R, mut cb: F) -> Option<(K, V)>
    where
        R: RangeBounds<K>,
        F: FnMut(&K, &V),
    {
        macro_rules! end_contains {
            ($key: expr) => {{
                match range.end_bound() {
                    Bound::Excluded(k) => $key < k,
                    Bound::Included(k) => $key <= k,
                    Bound::Unbounded => true,
                }
            }};
        }
        // Note: do not use find_leaf_with_bound, it's a different behavior
        let mut ent = match range.start_bound() {
            Bound::Excluded(k) => match self.entry(k.clone()).move_forward() {
                Ok(ent) => {
                    if end_contains!(ent.key()) {
                        ent
                    } else {
                        return None;
                    }
                }
                Err(_) => return None,
            },
            Bound::Included(k) => match self.entry(k.clone()) {
                Entry::Occupied(ent) => ent,
                Entry::Vacant(ent) => match ent.move_forward() {
                    Ok(ent) => {
                        if end_contains!(ent.key()) {
                            ent
                        } else {
                            return None;
                        }
                    }
                    Err(_) => return None,
                },
            },
            Bound::Unbounded => self.first_entry()?,
        };
        loop {
            if let Some((_next_k, _next_v)) = ent.peek_forward()
                && end_contains!(_next_k)
            {
                let next_key = _next_k.clone();
                let (_k, _v) = ent._remove_entry(false);
                cb(&_k, &_v);
                if let Entry::Occupied(_ent) = self.entry(next_key) {
                    ent = _ent;
                    continue;
                } else {
                    unreachable!();
                }
            }
            let (_k, _v) = ent._remove_entry(true);
            cb(&_k, &_v);
            return Some((_k, _v));
        }
    }

    /// Dump the entire tree structure for debugging
    #[cfg(test)]
    pub fn dump(&self)
    where
        K: Debug,
        V: Debug,
    {
        print_log!("=== BTreeMap Dump ===");
        print_log!("Length: {}", self.inner.len);
        if let Some(root) = self.inner.get_root() {
            self.dump_node(&root, 0);
        } else {
            print_log!("(empty)");
        }
        print_log!("=====================");
    }

    #[cfg(test)]
    fn dump_node(&self, node: &Node<K, V>, depth: usize)
    where
        K: Debug,
        V: Debug,
    {
        match node {
            Node::Leaf(leaf) => {
                std::print!("{:indent$}", "", indent = depth * 2);
                print_log!("{}", leaf);
            }
            Node::Inter(inter) => {
                std::print!("{:indent$}", "", indent = depth * 2);
                print_log!("{}", inter);
                // Dump children
                let count = inter.key_count() as u8;
                for i in 0..=count {
                    unsafe {
                        let child_ptr = *inter.child_ptr(i);
                        if !child_ptr.is_null() {
                            let child_node = if (*child_ptr).is_leaf() {
                                Node::Leaf(LeafNode::<K, V>::from_header(child_ptr))
                            } else {
                                Node::Inter(InterNode::<K>::from_header(child_ptr))
                            };
                            self.dump_node(&child_node, depth + 1);
                        }
                    }
                }
            }
        }
    }

    /// Validate the entire tree structure
    /// Uses the same traversal logic as Drop to avoid recursion
    pub fn validate(&self)
    where
        K: Debug,
        V: Debug,
    {
        self.inner.validate::<S>()
    }

    /// Returns the first key-value pair in the map
    /// Returns `None` if the map is empty
    #[inline]
    pub fn first_key_value(&self) -> Option<(&K, &V)> {
        let leaf = self.inner.search_leaf_with(InterNode::<K>::find_first_leaf::<V>)?;
        debug_assert!(leaf.key_count() > 0);
        unsafe {
            let key = (*leaf.key_ptr(0)).assume_init_ref();
            let value = (*leaf.value_ptr(0)).assume_init_ref();
            Some((key, value))
        }
    }

    /// Returns the last key-value pair in the map
    /// Returns `None` if the map is empty
    #[inline]
    pub fn last_key_value(&self) -> Option<(&K, &V)> {
        let leaf = self.inner.search_leaf_with(InterNode::<K>::find_last_leaf::<V>)?;
        let count = leaf.key_count();
        debug_assert!(count > 0);
        unsafe {
            let last_idx = count - 1;
            let key = (*leaf.key_ptr(last_idx)).assume_init_ref();
            let value = (*leaf.value_ptr(last_idx)).assume_init_ref();
            Some((key, value))
        }
    }

    /// Returns an iterator over the map's entries
    #[inline]
    pub fn iter(&self) -> Iter<'_, K, V> {
        Iter::new(self.find_first_and_last_leaf(), self.inner.len)
    }

    /// Returns a mutable iterator over the map's entries
    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
        IterMut::new(self.find_first_and_last_leaf(), self.inner.len)
    }

    /// Return a consuming iterator in reversed order
    #[inline]
    pub fn into_iter_rev(self) -> IntoIter<K, V, S> {
        IntoIter::new(self, false)
    }

    /// Returns an iterator over the map's keys
    #[inline]
    pub fn keys(&self) -> Keys<'_, K, V> {
        Keys::new(self.iter())
    }

    /// Returns an iterator over the map's values
    #[inline]
    pub fn values(&self) -> Values<'_, K, V> {
        Values::new(self.iter())
    }

    /// Returns a mutable iterator over the map's values
    #[inline]
    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
        ValuesMut::new(self.iter_mut())
    }

    #[inline]
    fn find_first_and_last_leaf(&self) -> Option<(LeafNode<K, V>, LeafNode<K, V>)> {
        let root = self.inner.root?;
        if !Node::<K, V>::root_is_leaf(root) {
            let inter = InterNode::<K>::from(root);
            Some((inter.clone().find_first_leaf::<V>(), inter.find_last_leaf::<V>()))
        } else {
            let leaf = LeafNode::<K, V>::from_root_ptr(root);
            Some((leaf.clone(), leaf))
        }
    }

    /// Internal helper to find range bounds
    /// Returns (front_leaf, front_idx, back_leaf, back_idx) where both leaves are Some or both are None
    #[inline]
    fn find_range_bounds<R>(&self, range: R) -> Option<RangeBase<'_, K, V>>
    where
        R: RangeBounds<K>,
    {
        let root = self.inner.get_root()?;
        let (front_leaf, front_idx) = root.find_leaf_with_bound(range.start_bound(), true);
        let (back_leaf, back_idx) = root.find_leaf_with_bound(range.end_bound(), false);
        Some(RangeBase::new(front_leaf, front_idx, back_leaf, back_idx))
    }

    /// Returns an iterator over a sub-range of entries in the map
    #[inline]
    pub fn range<R>(&self, range: R) -> Range<'_, K, V>
    where
        R: RangeBounds<K>,
    {
        Range::new(self.find_range_bounds(range))
    }

    /// Returns a mutable iterator over a sub-range of entries in the map
    #[inline]
    pub fn range_mut<R>(&mut self, range: R) -> RangeMut<'_, K, V>
    where
        R: RangeBounds<K>,
    {
        RangeMut::new(self.find_range_bounds(range))
    }

    /// Returns a cursor positioned at the first entry of the map.
    /// Returns `None` if the map is empty.
    #[inline]
    pub fn first_cursor(&self) -> Cursor<'_, K, V> {
        if let Some(leaf) = self.inner.search_leaf_with(InterNode::<K>::find_first_leaf::<V>)
            && leaf.key_count() > 0
        {
            return Cursor {
                leaf: Some(leaf),
                is_exist: true,
                idx: 0,
                _marker: Default::default(),
            };
        }
        Cursor { leaf: None, is_exist: true, idx: 0, _marker: Default::default() }
    }

    /// Returns a cursor positioned at the last entry of the map.
    /// Returns `None` if the map is empty.
    #[inline]
    pub fn last_cursor(&self) -> Cursor<'_, K, V> {
        if let Some(leaf) = self.inner.search_leaf_with(InterNode::<K>::find_last_leaf::<V>) {
            let count = leaf.key_count();
            if count > 0 {
                return Cursor {
                    leaf: Some(leaf),
                    idx: count - 1,
                    is_exist: true,
                    _marker: Default::default(),
                };
            }
        }
        Cursor { leaf: None, idx: 0, is_exist: false, _marker: Default::default() }
    }

    /// Returns a cursor positioned at the given key.
    ///
    /// NOTE: There's slight different for existing/non-existing key, refer to the doc of [Cursor]
    #[inline]
    pub fn cursor<Q>(&self, key: &Q) -> Cursor<'_, K, V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if let Some(leaf) = self.inner.search_leaf_with(|inter| inter.find_leaf::<V, Q>(key)) {
            let (idx, is_exist) = leaf.search(key);
            Cursor { leaf: Some(leaf), idx, is_exist, _marker: Default::default() }
        } else {
            Cursor { leaf: None, idx: 0, is_exist: false, _marker: Default::default() }
        }
    }

    #[cfg(test)]
    fn assert_leaf_count(&self, leaf_count: usize) {
        if self.inner.root.is_some() {
            self.stats.assert_leaf_count(leaf_count)
        } else {
            assert_eq!(leaf_count, 0);
        }
    }

    #[cfg(test)]
    fn assert_inter_count(&self, inter_count: usize) {
        self.stats.assert_inter_count(inter_count)
    }
}

impl<K: Key, V: Value, S: Stats> Default for BTree<K, V, S> {
    fn default() -> Self {
        Self::new()
    }
}

impl<K: Key, V: Value, S: Stats> Drop for BTree<K, V, S> {
    fn drop(&mut self) {
        if let Some(root) = self.inner.root {
            if Node::<K, V>::root_is_leaf(root) {
                let leaf = LeafNode::<K, V>::from_root_ptr(root);
                leaf.dealloc::<true>();
            } else {
                let inter = InterNode::<K>::from(root);
                let mut stack = S::BufferStack::default();
                let mut cache = self.stats.get_cache(&mut stack, Some(inter.clone()));
                let mut cur = inter.find_first_leaf_with_cache::<V, _>(&mut cache);
                cur.dealloc::<true>();
                // To navigate to next leaf,
                // return None when reach the end
                while let Some((parent, idx)) =
                    cache.move_path_right_and_pop_l1(|_cache, node| node.dealloc::<true>())
                {
                    cache.push_path(parent.clone(), idx);
                    cur = parent.get_child_as_leaf::<V>(idx);
                    cur.dealloc::<true>();
                }
            }
        }
    }
}

impl<K: Key, V: Value, S: Stats> IntoIterator for BTree<K, V, S> {
    type Item = (K, V);
    type IntoIter = IntoIter<K, V, S>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        IntoIter::new(self, true)
    }
}

impl<'a, K: Key, V: Value, S: Stats> IntoIterator for &'a BTree<K, V, S> {
    type Item = (&'a K, &'a V);
    type IntoIter = Iter<'a, K, V>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, K: Key, V: Value, S: Stats> IntoIterator for &'a mut BTree<K, V, S> {
    type Item = (&'a K, &'a mut V);
    type IntoIter = IterMut<'a, K, V>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<K: Key, V: Value + PartialEq, S: Stats> PartialEq for BTree<K, V, S> {
    fn eq(&self, other: &Self) -> bool {
        let mut this_iter = self.iter();
        let mut other_iter = other.iter();
        loop {
            let this_item = this_iter.next();
            let other_item = other_iter.next();
            if this_item == other_item {
                if this_item.is_some() {
                    continue;
                } else {
                    return true;
                }
            } else {
                return false;
            }
        }
    }
}

impl<K: Key + Debug, V: Value + Debug, S: Stats> Debug for BTree<K, V, S> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let _ = write!(f, "{{");
        let mut iter = self.iter();
        while let Some((k, v)) = iter.next() {
            let _ = write!(f, "{k:?}:{v:?}");
            if iter.len() > 0 {
                let _ = write!(f, ",");
            }
        }
        write!(f, "}}")
    }
}