alloc/collections/btree/
navigate.rs

Help
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}
alloc/collections/btree/navigate.rs

alloc/collections/btree/
navigate.rs
