rune_alloc/btree/
navigate.rs

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

rune_alloc/btree/
navigate.rs
