#
alloc/collections/btree/
navigate.rs

    1use core::borrow::Borrow;
    2use core::ops::RangeBounds;
    3use core::{hint, ptr};
    4
    5use super::node::ForceResult::*;
    6use super::node::{Handle, NodeRef, marker};
    7use super::search::SearchBound;
    8use crate::alloc::Allocator;
    9// `front` and `back` are always both `None` or both `Some`.
    10pub(super) struct LeafRange<BorrowType, K, V> {
    11    front: Option<Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>>,
    12    back: Option<Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>>,
    13}
    14
    15impl<'a, K: 'a, V: 'a> Clone for LeafRange<marker::Immut<'a>, K, V> {
    16    fn clone(&self) -> Self {
    17        LeafRange { front: self.front.clone(), back: self.back.clone() }
    18    }
    19}
    20
    21impl<B, K, V> Default for LeafRange<B, K, V> {
    22    fn default() -> Self {
    23        LeafRange { front: None, back: None }
    24    }
    25}
    26
    27impl<BorrowType, K, V> LeafRange<BorrowType, K, V> {
    28    pub(super) fn none() -> Self {
    29        LeafRange { front: None, back: None }
    30    }
    31
    32    fn is_empty(&self) -> bool {
    33        self.front == self.back
    34    }
    35
    36    /// Temporarily takes out another, immutable equivalent of the same range.
    37    pub(super) fn reborrow(&self) -> LeafRange<marker::Immut<'_>, K, V> {
    38        LeafRange {
    39            front: self.front.as_ref().map(|f| f.reborrow()),
    40            back: self.back.as_ref().map(|b| b.reborrow()),
    41        }
    42    }
    43}
    44
    45impl<'a, K, V> LeafRange<marker::Immut<'a>, K, V> {
    46    #[inline]
    47    pub(super) fn next_checked(&mut self) -> Option<(&'a K, &'a V)> {
    48        self.perform_next_checked(|kv| kv.into_kv())
    49    }
    50
    51    #[inline]
    52    pub(super) fn next_back_checked(&mut self) -> Option<(&'a K, &'a V)> {
    53        self.perform_next_back_checked(|kv| kv.into_kv())
    54    }
    55}
    56
    57impl<'a, K, V> LeafRange<marker::ValMut<'a>, K, V> {
    58    #[inline]
    59    pub(super) fn next_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
    60        self.perform_next_checked(|kv| unsafe { ptr::read(kv) }.into_kv_valmut())
    61    }
    62
    63    #[inline]
    64    pub(super) fn next_back_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
    65        self.perform_next_back_checked(|kv| unsafe { ptr::read(kv) }.into_kv_valmut())
    66    }
    67}
    68
    69impl<BorrowType: marker::BorrowType, K, V> LeafRange<BorrowType, K, V> {
    70    /// If possible, extract some result from the following KV and move to the edge beyond it.
    71    fn perform_next_checked<F, R>(&mut self, f: F) -> Option<R>
    72    where
    73        F: Fn(&Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>) -> R,
    74    {
    75        if self.is_empty() {
    76            None
    77        } else {
    78            super::mem::replace(self.front.as_mut().unwrap(), |front| {
    79                let kv = front.next_kv().ok().unwrap();
    80                let result = f(&kv);
    81                (kv.next_leaf_edge(), Some(result))
    82            })
    83        }
    84    }
    85
    86    /// If possible, extract some result from the preceding KV and move to the edge beyond it.
    87    fn perform_next_back_checked<F, R>(&mut self, f: F) -> Option<R>
    88    where
    89        F: Fn(&Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>) -> R,
    90    {
    91        if self.is_empty() {
    92            None
    93        } else {
    94            super::mem::replace(self.back.as_mut().unwrap(), |back| {
    95                let kv = back.next_back_kv().ok().unwrap();
    96                let result = f(&kv);
    97                (kv.next_back_leaf_edge(), Some(result))
    98            })
    99        }
    100    }
    101}
    102
    103enum LazyLeafHandle<BorrowType, K, V> {
    104    Root(NodeRef<BorrowType, K, V, marker::LeafOrInternal>), // not yet descended
    105    Edge(Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>),
    106}
    107
    108impl<'a, K: 'a, V: 'a> Clone for LazyLeafHandle<marker::Immut<'a>, K, V> {
    109    fn clone(&self) -> Self {
    110        match self {
    111            LazyLeafHandle::Root(root) => LazyLeafHandle::Root(*root),
    112            LazyLeafHandle::Edge(edge) => LazyLeafHandle::Edge(*edge),
    113        }
    114    }
    115}
    116
    117impl<BorrowType, K, V> LazyLeafHandle<BorrowType, K, V> {
    118    fn reborrow(&self) -> LazyLeafHandle<marker::Immut<'_>, K, V> {
    119        match self {
    120            LazyLeafHandle::Root(root) => LazyLeafHandle::Root(root.reborrow()),
    121            LazyLeafHandle::Edge(edge) => LazyLeafHandle::Edge(edge.reborrow()),
    122        }
    123    }
    124}
    125
    126// `front` and `back` are always both `None` or both `Some`.
    127pub(super) struct LazyLeafRange<BorrowType, K, V> {
    128    front: Option<LazyLeafHandle<BorrowType, K, V>>,
    129    back: Option<LazyLeafHandle<BorrowType, K, V>>,
    130}
    131
    132impl<B, K, V> Default for LazyLeafRange<B, K, V> {
    133    fn default() -> Self {
    134        LazyLeafRange { front: None, back: None }
    135    }
    136}
    137
    138impl<'a, K: 'a, V: 'a> Clone for LazyLeafRange<marker::Immut<'a>, K, V> {
    139    fn clone(&self) -> Self {
    140        LazyLeafRange { front: self.front.clone(), back: self.back.clone() }
    141    }
    142}
    143
    144impl<BorrowType, K, V> LazyLeafRange<BorrowType, K, V> {
    145    pub(super) fn none() -> Self {
    146        LazyLeafRange { front: None, back: None }
    147    }
    148
    149    /// Temporarily takes out another, immutable equivalent of the same range.
    150    pub(super) fn reborrow(&self) -> LazyLeafRange<marker::Immut<'_>, K, V> {
    151        LazyLeafRange {
    152            front: self.front.as_ref().map(|f| f.reborrow()),
    153            back: self.back.as_ref().map(|b| b.reborrow()),
    154        }
    155    }
    156}
    157
    158impl<'a, K, V> LazyLeafRange<marker::Immut<'a>, K, V> {
    159    #[inline]
    160    pub(super) unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
    161        unsafe { self.init_front().unwrap().next_unchecked() }
    162    }
    163
    164    #[inline]
    165    pub(super) unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
    166        unsafe { self.init_back().unwrap().next_back_unchecked() }
    167    }
    168}
    169
    170impl<'a, K, V> LazyLeafRange<marker::ValMut<'a>, K, V> {
    171    #[inline]
    172    pub(super) unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
    173        unsafe { self.init_front().unwrap().next_unchecked() }
    174    }
    175
    176    #[inline]
    177    pub(super) unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
    178        unsafe { self.init_back().unwrap().next_back_unchecked() }
    179    }
    180}
    181
    182impl<K, V> LazyLeafRange<marker::Dying, K, V> {
    183    fn take_front(
    184        &mut self,
    185    ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge>> {
    186        match self.front.take()? {
    187            LazyLeafHandle::Root(root) => Some(root.first_leaf_edge()),
    188            LazyLeafHandle::Edge(edge) => Some(edge),
    189        }
    190    }
    191
    192    #[inline]
    193    pub(super) unsafe fn deallocating_next_unchecked<A: Allocator + Clone>(
    194        &mut self,
    195        alloc: A,
    196    ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
    197        debug_assert!(self.front.is_some());
    198        let front = self.init_front().unwrap();
    199        unsafe { front.deallocating_next_unchecked(alloc) }
    200    }
    201
    202    #[inline]
    203    pub(super) unsafe fn deallocating_next_back_unchecked<A: Allocator + Clone>(
    204        &mut self,
    205        alloc: A,
    206    ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
    207        debug_assert!(self.back.is_some());
    208        let back = self.init_back().unwrap();
    209        unsafe { back.deallocating_next_back_unchecked(alloc) }
    210    }
    211
    212    #[inline]
    213    pub(super) fn deallocating_end<A: Allocator + Clone>(&mut self, alloc: A) {
    214        if let Some(front) = self.take_front() {
    215            front.deallocating_end(alloc)
    216        }
    217    }
    218}
    219
    220impl<BorrowType: marker::BorrowType, K, V> LazyLeafRange<BorrowType, K, V> {
    221    fn init_front(
    222        &mut self,
    223    ) -> Option<&mut Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>> {
    224        if let Some(LazyLeafHandle::Root(root)) = &self.front {
    225            self.front = Some(LazyLeafHandle::Edge(unsafe { ptr::read(root) }.first_leaf_edge()));
    226        }
    227        match &mut self.front {
    228            None => None,
    229            Some(LazyLeafHandle::Edge(edge)) => Some(edge),
    230            // SAFETY: the code above would have replaced it.
    231            Some(LazyLeafHandle::Root(_)) => unsafe { hint::unreachable_unchecked() },
    232        }
    233    }
    234
    235    fn init_back(
    236        &mut self,
    237    ) -> Option<&mut Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>> {
    238        if let Some(LazyLeafHandle::Root(root)) = &self.back {
    239            self.back = Some(LazyLeafHandle::Edge(unsafe { ptr::read(root) }.last_leaf_edge()));
    240        }
    241        match &mut self.back {
    242            None => None,
    243            Some(LazyLeafHandle::Edge(edge)) => Some(edge),
    244            // SAFETY: the code above would have replaced it.
    245            Some(LazyLeafHandle::Root(_)) => unsafe { hint::unreachable_unchecked() },
    246        }
    247    }
    248}
    249
    250impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
    251    /// Finds the distinct leaf edges delimiting a specified range in a tree.
    252    ///
    253    /// If such distinct edges exist, returns them in ascending order, meaning
    254    /// that a non-zero number of calls to `next_unchecked` on the `front` of
    255    /// the result and/or calls to `next_back_unchecked` on the `back` of the
    256    /// result will eventually reach the same edge.
    257    ///
    258    /// If there are no such edges, i.e., if the tree contains no key within
    259    /// the range, returns an empty `front` and `back`.
    260    ///
    261    /// # Safety
    262    /// Unless `BorrowType` is `Immut`, do not use the handles to visit the same
    263    /// KV twice.
    264    unsafe fn find_leaf_edges_spanning_range<Q: ?Sized, R>(
    265        self,
    266        range: R,
    267    ) -> LeafRange<BorrowType, K, V>
    268    where
    269        Q: Ord,
    270        K: Borrow<Q>,
    271        R: RangeBounds<Q>,
    272    {
    273        match self.search_tree_for_bifurcation(&range) {
    274            Err(_) => LeafRange::none(),
    275            Ok((
    276                node,
    277                lower_edge_idx,
    278                upper_edge_idx,
    279                mut lower_child_bound,
    280                mut upper_child_bound,
    281            )) => {
    282                let mut lower_edge = unsafe { Handle::new_edge(ptr::read(&node), lower_edge_idx) };
    283                let mut upper_edge = unsafe { Handle::new_edge(node, upper_edge_idx) };
    284                loop {
    285                    match (lower_edge.force(), upper_edge.force()) {
    286                        (Leaf(f), Leaf(b)) => return LeafRange { front: Some(f), back: Some(b) },
    287                        (Internal(f), Internal(b)) => {
    288                            (lower_edge, lower_child_bound) =
    289                                f.descend().find_lower_bound_edge(lower_child_bound);
    290                            (upper_edge, upper_child_bound) =
    291                                b.descend().find_upper_bound_edge(upper_child_bound);
    292                        }
    293                        _ => unreachable!("BTreeMap has different depths"),
    294                    }
    295                }
    296            }
    297        }
    298    }
    299}
    300
    301fn full_range<BorrowType: marker::BorrowType, K, V>(
    302    root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
    303    root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
    304) -> LazyLeafRange<BorrowType, K, V> {
    305    LazyLeafRange {
    306        front: Some(LazyLeafHandle::Root(root1)),
    307        back: Some(LazyLeafHandle::Root(root2)),
    308    }
    309}
    310
    311impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
    312    /// Finds the pair of leaf edges delimiting a specific range in a tree.
    313    ///
    314    /// The result is meaningful only if the tree is ordered by key, like the tree
    315    /// in a `BTreeMap` is.
    316    pub(super) fn range_search<Q, R>(self, range: R) -> LeafRange<marker::Immut<'a>, K, V>
    317    where
    318        Q: ?Sized + Ord,
    319        K: Borrow<Q>,
    320        R: RangeBounds<Q>,
    321    {
    322        // SAFETY: our borrow type is immutable.
    323        unsafe { self.find_leaf_edges_spanning_range(range) }
    324    }
    325
    326    /// Finds the pair of leaf edges delimiting an entire tree.
    327    pub(super) fn full_range(self) -> LazyLeafRange<marker::Immut<'a>, K, V> {
    328        full_range(self, self)
    329    }
    330}
    331
    332impl<'a, K: 'a, V: 'a> NodeRef<marker::ValMut<'a>, K, V, marker::LeafOrInternal> {
    333    /// Splits a unique reference into a pair of leaf edges delimiting a specified range.
    334    /// The result are non-unique references allowing (some) mutation, which must be used
    335    /// carefully.
    336    ///
    337    /// The result is meaningful only if the tree is ordered by key, like the tree
    338    /// in a `BTreeMap` is.
    339    ///
    340    /// # Safety
    341    /// Do not use the duplicate handles to visit the same KV twice.
    342    pub(super) fn range_search<Q, R>(self, range: R) -> LeafRange<marker::ValMut<'a>, K, V>
    343    where
    344        Q: ?Sized + Ord,
    345        K: Borrow<Q>,
    346        R: RangeBounds<Q>,
    347    {
    348        unsafe { self.find_leaf_edges_spanning_range(range) }
    349    }
    350
    351    /// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree.
    352    /// The results are non-unique references allowing mutation (of values only), so must be used
    353    /// with care.
    354    pub(super) fn full_range(self) -> LazyLeafRange<marker::ValMut<'a>, K, V> {
    355        // We duplicate the root NodeRef here -- we will never visit the same KV
    356        // twice, and never end up with overlapping value references.
    357        let self2 = unsafe { ptr::read(&self) };
    358        full_range(self, self2)
    359    }
    360}
    361
    362impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> {
    363    /// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree.
    364    /// The results are non-unique references allowing massively destructive mutation, so must be
    365    /// used with the utmost care.
    366    pub(super) fn full_range(self) -> LazyLeafRange<marker::Dying, K, V> {
    367        // We duplicate the root NodeRef here -- we will never access it in a way
    368        // that overlaps references obtained from the root.
    369        let self2 = unsafe { ptr::read(&self) };
    370        full_range(self, self2)
    371    }
    372}
    373
    374impl<BorrowType: marker::BorrowType, K, V>
    375    Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
    376{
    377    /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
    378    /// on the right side, which is either in the same leaf node or in an ancestor node.
    379    /// If the leaf edge is the last one in the tree, returns [`Result::Err`] with the root node.
    380    pub(super) fn next_kv(
    381        self,
    382    ) -> Result<
    383        Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
    384        NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
    385    > {
    386        let mut edge = self.forget_node_type();
    387        loop {
    388            edge = match edge.right_kv() {
    389                Ok(kv) => return Ok(kv),
    390                Err(last_edge) => match last_edge.into_node().ascend() {
    391                    Ok(parent_edge) => parent_edge.forget_node_type(),
    392                    Err(root) => return Err(root),
    393                },
    394            }
    395        }
    396    }
    397
    398    /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
    399    /// on the left side, which is either in the same leaf node or in an ancestor node.
    400    /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node.
    401    pub(super) fn next_back_kv(
    402        self,
    403    ) -> Result<
    404        Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
    405        NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
    406    > {
    407        let mut edge = self.forget_node_type();
    408        loop {
    409            edge = match edge.left_kv() {
    410                Ok(kv) => return Ok(kv),
    411                Err(last_edge) => match last_edge.into_node().ascend() {
    412                    Ok(parent_edge) => parent_edge.forget_node_type(),
    413                    Err(root) => return Err(root),
    414                },
    415            }
    416        }
    417    }
    418}
    419
    420impl<BorrowType: marker::BorrowType, K, V>
    421    Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>
    422{
    423    /// Given an internal edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
    424    /// on the right side, which is either in the same internal node or in an ancestor node.
    425    /// If the internal edge is the last one in the tree, returns [`Result::Err`] with the root node.
    426    fn next_kv(
    427        self,
    428    ) -> Result<
    429        Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>,
    430        NodeRef<BorrowType, K, V, marker::Internal>,
    431    > {
    432        let mut edge = self;
    433        loop {
    434            edge = match edge.right_kv() {
    435                Ok(internal_kv) => return Ok(internal_kv),
    436                Err(last_edge) => match last_edge.into_node().ascend() {
    437                    Ok(parent_edge) => parent_edge,
    438                    Err(root) => return Err(root),
    439                },
    440            }
    441        }
    442    }
    443}
    444
    445impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> {
    446    /// Given a leaf edge handle into a dying tree, returns the next leaf edge
    447    /// on the right side, and the key-value pair in between, if they exist.
    448    ///
    449    /// If the given edge is the last one in a leaf, this method deallocates
    450    /// the leaf, as well as any ancestor nodes whose last edge was reached.
    451    /// This implies that if no more key-value pair follows, the entire tree
    452    /// will have been deallocated and there is nothing left to return.
    453    ///
    454    /// # Safety
    455    /// - The given edge must not have been previously returned by counterpart
    456    ///   `deallocating_next_back`.
    457    /// - The returned KV handle is only valid to access the key and value,
    458    ///   and only valid until the next call to a `deallocating_` method.
    459    unsafe fn deallocating_next<A: Allocator + Clone>(
    460        self,
    461        alloc: A,
    462    ) -> Option<(Self, Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>)>
    463    {
    464        let mut edge = self.forget_node_type();
    465        loop {
    466            edge = match edge.right_kv() {
    467                Ok(kv) => return Some((unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)),
    468                Err(last_edge) => {
    469                    match unsafe { last_edge.into_node().deallocate_and_ascend(alloc.clone()) } {
    470                        Some(parent_edge) => parent_edge.forget_node_type(),
    471                        None => return None,
    472                    }
    473                }
    474            }
    475        }
    476    }
    477
    478    /// Given a leaf edge handle into a dying tree, returns the next leaf edge
    479    /// on the left side, and the key-value pair in between, if they exist.
    480    ///
    481    /// If the given edge is the first one in a leaf, this method deallocates
    482    /// the leaf, as well as any ancestor nodes whose first edge was reached.
    483    /// This implies that if no more key-value pair follows, the entire tree
    484    /// will have been deallocated and there is nothing left to return.
    485    ///
    486    /// # Safety
    487    /// - The given edge must not have been previously returned by counterpart
    488    ///   `deallocating_next`.
    489    /// - The returned KV handle is only valid to access the key and value,
    490    ///   and only valid until the next call to a `deallocating_` method.
    491    unsafe fn deallocating_next_back<A: Allocator + Clone>(
    492        self,
    493        alloc: A,
    494    ) -> Option<(Self, Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>)>
    495    {
    496        let mut edge = self.forget_node_type();
    497        loop {
    498            edge = match edge.left_kv() {
    499                Ok(kv) => return Some((unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)),
    500                Err(last_edge) => {
    501                    match unsafe { last_edge.into_node().deallocate_and_ascend(alloc.clone()) } {
    502                        Some(parent_edge) => parent_edge.forget_node_type(),
    503                        None => return None,
    504                    }
    505                }
    506            }
    507        }
    508    }
    509
    510    /// Deallocates a pile of nodes from the leaf up to the root.
    511    /// This is the only way to deallocate the remainder of a tree after
    512    /// `deallocating_next` and `deallocating_next_back` have been nibbling at
    513    /// both sides of the tree, and have hit the same edge. As it is intended
    514    /// only to be called when all keys and values have been returned,
    515    /// no cleanup is done on any of the keys or values.
    516    fn deallocating_end<A: Allocator + Clone>(self, alloc: A) {
    517        let mut edge = self.forget_node_type();
    518        while let Some(parent_edge) =
    519            unsafe { edge.into_node().deallocate_and_ascend(alloc.clone()) }
    520        {
    521            edge = parent_edge.forget_node_type();
    522        }
    523    }
    524}
    525
    526impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge> {
    527    /// Moves the leaf edge handle to the next leaf edge and returns references to the
    528    /// key and value in between.
    529    ///
    530    /// # Safety
    531    /// There must be another KV in the direction travelled.
    532    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
    533        super::mem::replace(self, |leaf_edge| {
    534            let kv = leaf_edge.next_kv().ok().unwrap();
    535            (kv.next_leaf_edge(), kv.into_kv())
    536        })
    537    }
    538
    539    /// Moves the leaf edge handle to the previous leaf edge and returns references to the
    540    /// key and value in between.
    541    ///
    542    /// # Safety
    543    /// There must be another KV in the direction travelled.
    544    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
    545        super::mem::replace(self, |leaf_edge| {
    546            let kv = leaf_edge.next_back_kv().ok().unwrap();
    547            (kv.next_back_leaf_edge(), kv.into_kv())
    548        })
    549    }
    550}
    551
    552impl<'a, K, V> Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge> {
    553    /// Moves the leaf edge handle to the next leaf edge and returns references to the
    554    /// key and value in between.
    555    ///
    556    /// # Safety
    557    /// There must be another KV in the direction travelled.
    558    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
    559        let kv = super::mem::replace(self, |leaf_edge| {
    560            let kv = leaf_edge.next_kv().ok().unwrap();
    561            (unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)
    562        });
    563        // Doing this last is faster, according to benchmarks.
    564        kv.into_kv_valmut()
    565    }
    566
    567    /// Moves the leaf edge handle to the previous leaf and returns references to the
    568    /// key and value in between.
    569    ///
    570    /// # Safety
    571    /// There must be another KV in the direction travelled.
    572    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
    573        let kv = super::mem::replace(self, |leaf_edge| {
    574            let kv = leaf_edge.next_back_kv().ok().unwrap();
    575            (unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)
    576        });
    577        // Doing this last is faster, according to benchmarks.
    578        kv.into_kv_valmut()
    579    }
    580}
    581
    582impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> {
    583    /// Moves the leaf edge handle to the next leaf edge and returns the key and value
    584    /// in between, deallocating any node left behind while leaving the corresponding
    585    /// edge in its parent node dangling.
    586    ///
    587    /// # Safety
    588    /// - There must be another KV in the direction travelled.
    589    /// - That KV was not previously returned by counterpart
    590    ///   `deallocating_next_back_unchecked` on any copy of the handles
    591    ///   being used to traverse the tree.
    592    ///
    593    /// The only safe way to proceed with the updated handle is to compare it, drop it,
    594    /// or call this method or counterpart `deallocating_next_back_unchecked` again.
    595    unsafe fn deallocating_next_unchecked<A: Allocator + Clone>(
    596        &mut self,
    597        alloc: A,
    598    ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
    599        super::mem::replace(self, |leaf_edge| unsafe {
    600            leaf_edge.deallocating_next(alloc).unwrap()
    601        })
    602    }
    603
    604    /// Moves the leaf edge handle to the previous leaf edge and returns the key and value
    605    /// in between, deallocating any node left behind while leaving the corresponding
    606    /// edge in its parent node dangling.
    607    ///
    608    /// # Safety
    609    /// - There must be another KV in the direction travelled.
    610    /// - That leaf edge was not previously returned by counterpart
    611    ///   `deallocating_next_unchecked` on any copy of the handles
    612    ///   being used to traverse the tree.
    613    ///
    614    /// The only safe way to proceed with the updated handle is to compare it, drop it,
    615    /// or call this method or counterpart `deallocating_next_unchecked` again.
    616    unsafe fn deallocating_next_back_unchecked<A: Allocator + Clone>(
    617        &mut self,
    618        alloc: A,
    619    ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
    620        super::mem::replace(self, |leaf_edge| unsafe {
    621            leaf_edge.deallocating_next_back(alloc).unwrap()
    622        })
    623    }
    624}
    625
    626impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
    627    /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge
    628    /// you need first when navigating forward (or last when navigating backward).
    629    #[inline]
    630    pub(super) fn first_leaf_edge(
    631        self,
    632    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
    633        let mut node = self;
    634        loop {
    635            match node.force() {
    636                Leaf(leaf) => return leaf.first_edge(),
    637                Internal(internal) => node = internal.first_edge().descend(),
    638            }
    639        }
    640    }
    641
    642    /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge
    643    /// you need last when navigating forward (or first when navigating backward).
    644    #[inline]
    645    pub(super) fn last_leaf_edge(
    646        self,
    647    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
    648        let mut node = self;
    649        loop {
    650            match node.force() {
    651                Leaf(leaf) => return leaf.last_edge(),
    652                Internal(internal) => node = internal.last_edge().descend(),
    653            }
    654        }
    655    }
    656}
    657
    658pub(super) enum Position<BorrowType, K, V> {
    659    Leaf(NodeRef<BorrowType, K, V, marker::Leaf>),
    660    Internal(NodeRef<BorrowType, K, V, marker::Internal>),
    661    InternalKV,
    662}
    663
    664impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
    665    /// Visits leaf nodes and internal KVs in order of ascending keys, and also
    666    /// visits internal nodes as a whole in a depth first order, meaning that
    667    /// internal nodes precede their individual KVs and their child nodes.
    668    pub(super) fn visit_nodes_in_order<F>(self, mut visit: F)
    669    where
    670        F: FnMut(Position<marker::Immut<'a>, K, V>),
    671    {
    672        match self.force() {
    673            Leaf(leaf) => visit(Position::Leaf(leaf)),
    674            Internal(internal) => {
    675                visit(Position::Internal(internal));
    676                let mut edge = internal.first_edge();
    677                loop {
    678                    edge = match edge.descend().force() {
    679                        Leaf(leaf) => {
    680                            visit(Position::Leaf(leaf));
    681                            match edge.next_kv() {
    682                                Ok(kv) => {
    683                                    visit(Position::InternalKV);
    684                                    kv.right_edge()
    685                                }
    686                                Err(_) => return,
    687                            }
    688                        }
    689                        Internal(internal) => {
    690                            visit(Position::Internal(internal));
    691                            internal.first_edge()
    692                        }
    693                    }
    694                }
    695            }
    696        }
    697    }
    698
    699    /// Calculates the number of elements in a (sub)tree.
    700    pub(super) fn calc_length(self) -> usize {
    701        let mut result = 0;
    702        self.visit_nodes_in_order(|pos| match pos {
    703            Position::Leaf(node) => result += node.len(),
    704            Position::Internal(node) => result += node.len(),
    705            Position::InternalKV => (),
    706        });
    707        result
    708    }
    709}
    710
    711impl<BorrowType: marker::BorrowType, K, V>
    712    Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>
    713{
    714    /// Returns the leaf edge closest to a KV for forward navigation.
    715    pub(super) fn next_leaf_edge(
    716        self,
    717    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
    718        match self.force() {
    719            Leaf(leaf_kv) => leaf_kv.right_edge(),
    720            Internal(internal_kv) => {
    721                let next_internal_edge = internal_kv.right_edge();
    722                next_internal_edge.descend().first_leaf_edge()
    723            }
    724        }
    725    }
    726
    727    /// Returns the leaf edge closest to a KV for backward navigation.
    728    pub(super) fn next_back_leaf_edge(
    729        self,
    730    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
    731        match self.force() {
    732            Leaf(leaf_kv) => leaf_kv.left_edge(),
    733            Internal(internal_kv) => {
    734                let next_internal_edge = internal_kv.left_edge();
    735                next_internal_edge.descend().last_leaf_edge()
    736            }
    737        }
    738    }
    739}
    740
    741impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
    742    /// Returns the leaf edge corresponding to the first point at which the
    743    /// given bound is true.
    744    pub(super) fn lower_bound<Q: ?Sized>(
    745        self,
    746        mut bound: SearchBound<&Q>,
    747    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
    748    where
    749        Q: Ord,
    750        K: Borrow<Q>,
    751    {
    752        let mut node = self;
    753        loop {
    754            let (edge, new_bound) = node.find_lower_bound_edge(bound);
    755            match edge.force() {
    756                Leaf(edge) => return edge,
    757                Internal(edge) => {
    758                    node = edge.descend();
    759                    bound = new_bound;
    760                }
    761            }
    762        }
    763    }
    764
    765    /// Returns the leaf edge corresponding to the last point at which the
    766    /// given bound is true.
    767    pub(super) fn upper_bound<Q: ?Sized>(
    768        self,
    769        mut bound: SearchBound<&Q>,
    770    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
    771    where
    772        Q: Ord,
    773        K: Borrow<Q>,
    774    {
    775        let mut node = self;
    776        loop {
    777            let (edge, new_bound) = node.find_upper_bound_edge(bound);
    778            match edge.force() {
    779                Leaf(edge) => return edge,
    780                Internal(edge) => {
    781                    node = edge.descend();
    782                    bound = new_bound;
    783                }
    784            }
    785        }
    786    }
    787}