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

alloc/collections/btree/
navigate.rs
