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

alloc/collections/btree/
navigate.rs
