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: &Handle, …>| f.reborrow()),
40 back: self.back.as_ref().map(|b: &Handle, …>| 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: &Handle, …, …, …>, …>| 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: &Handle, …, …, …>, …>| 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: &Handle, …, …, …>, …>| unsafe { ptr::read(src: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: &Handle, …, …, …>, …>| unsafe { ptr::read(src: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: &NodeRef, K, V, …>) => LazyLeafHandle::Root(*root),
112 LazyLeafHandle::Edge(edge: &Handle, …, …, …>, …>) => 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: &NodeRef) => LazyLeafHandle::Root(root.reborrow()),
121 LazyLeafHandle::Edge(edge: &Handle, …>) => 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: &LazyLeafHandle| f.reborrow()),
153 back: self.back.as_ref().map(|b: &LazyLeafHandle| 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: NodeRef = unsafe { ptr::read(&self) };
370 full_range(self, root2: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: Handle, …> = self;
433 loop {
434 edge = match edge.right_kv() {
435 Ok(internal_kv: Handle, …>) => return Ok(internal_kv),
436 Err(last_edge: Handle, …>) => match last_edge.into_node().ascend() {
437 Ok(parent_edge: Handle, …>) => parent_edge,
438 Err(root: NodeRef) => 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}
788