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;
9pub(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 pub(super) fn reborrow(&self) -> LeafRange<marker::Immut<'_>, K, V> {
38 LeafRange {
39 front: self.front.as_ref().map(|f| f.reborrow()),
40 back: self.back.as_ref().map(|b| b.reborrow()),
41 }
42 }
43}
44
45impl<'a, K, V> LeafRange<marker::Immut<'a>, K, V> {
46 #[inline]
47 pub(super) fn next_checked(&mut self) -> Option<(&'a K, &'a V)> {
48 self.perform_next_checked(|kv| kv.into_kv())
49 }
50
51 #[inline]
52 pub(super) fn next_back_checked(&mut self) -> Option<(&'a K, &'a V)> {
53 self.perform_next_back_checked(|kv| kv.into_kv())
54 }
55}
56
57impl<'a, K, V> LeafRange<marker::ValMut<'a>, K, V> {
58 #[inline]
59 pub(super) fn next_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
60 self.perform_next_checked(|kv| unsafe { ptr::read(kv) }.into_kv_valmut())
61 }
62
63 #[inline]
64 pub(super) fn next_back_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
65 self.perform_next_back_checked(|kv| unsafe { ptr::read(kv) }.into_kv_valmut())
66 }
67}
68
69impl<BorrowType: marker::BorrowType, K, V> LeafRange<BorrowType, K, V> {
70 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 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>), Edge(Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>),
106}
107
108impl<'a, K: 'a, V: 'a> Clone for LazyLeafHandle<marker::Immut<'a>, K, V> {
109 fn clone(&self) -> Self {
110 match self {
111 LazyLeafHandle::Root(root) => LazyLeafHandle::Root(*root),
112 LazyLeafHandle::Edge(edge) => LazyLeafHandle::Edge(*edge),
113 }
114 }
115}
116
117impl<BorrowType, K, V> LazyLeafHandle<BorrowType, K, V> {
118 fn reborrow(&self) -> LazyLeafHandle<marker::Immut<'_>, K, V> {
119 match self {
120 LazyLeafHandle::Root(root) => LazyLeafHandle::Root(root.reborrow()),
121 LazyLeafHandle::Edge(edge) => LazyLeafHandle::Edge(edge.reborrow()),
122 }
123 }
124}
125
126pub(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 pub(super) fn reborrow(&self) -> LazyLeafRange<marker::Immut<'_>, K, V> {
151 LazyLeafRange {
152 front: self.front.as_ref().map(|f| f.reborrow()),
153 back: self.back.as_ref().map(|b| b.reborrow()),
154 }
155 }
156}
157
158impl<'a, K, V> LazyLeafRange<marker::Immut<'a>, K, V> {
159 #[inline]
160 pub(super) unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
161 unsafe { self.init_front().unwrap().next_unchecked() }
162 }
163
164 #[inline]
165 pub(super) unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
166 unsafe { self.init_back().unwrap().next_back_unchecked() }
167 }
168}
169
170impl<'a, K, V> LazyLeafRange<marker::ValMut<'a>, K, V> {
171 #[inline]
172 pub(super) unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
173 unsafe { self.init_front().unwrap().next_unchecked() }
174 }
175
176 #[inline]
177 pub(super) unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
178 unsafe { self.init_back().unwrap().next_back_unchecked() }
179 }
180}
181
182impl<K, V> LazyLeafRange<marker::Dying, K, V> {
183 fn take_front(
184 &mut self,
185 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge>> {
186 match self.front.take()? {
187 LazyLeafHandle::Root(root) => Some(root.first_leaf_edge()),
188 LazyLeafHandle::Edge(edge) => Some(edge),
189 }
190 }
191
192 #[inline]
193 pub(super) unsafe fn deallocating_next_unchecked<A: Allocator + Clone>(
194 &mut self,
195 alloc: A,
196 ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
197 debug_assert!(self.front.is_some());
198 let front = self.init_front().unwrap();
199 unsafe { front.deallocating_next_unchecked(alloc) }
200 }
201
202 #[inline]
203 pub(super) unsafe fn deallocating_next_back_unchecked<A: Allocator + Clone>(
204 &mut self,
205 alloc: A,
206 ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
207 debug_assert!(self.back.is_some());
208 let back = self.init_back().unwrap();
209 unsafe { back.deallocating_next_back_unchecked(alloc) }
210 }
211
212 #[inline]
213 pub(super) fn deallocating_end<A: Allocator + Clone>(&mut self, alloc: A) {
214 if let Some(front) = self.take_front() {
215 front.deallocating_end(alloc)
216 }
217 }
218}
219
220impl<BorrowType: marker::BorrowType, K, V> LazyLeafRange<BorrowType, K, V> {
221 fn init_front(
222 &mut self,
223 ) -> Option<&mut Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>> {
224 if let Some(LazyLeafHandle::Root(root)) = &self.front {
225 self.front = Some(LazyLeafHandle::Edge(unsafe { ptr::read(root) }.first_leaf_edge()));
226 }
227 match &mut self.front {
228 None => None,
229 Some(LazyLeafHandle::Edge(edge)) => Some(edge),
230 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 Some(LazyLeafHandle::Root(_)) => unsafe { hint::unreachable_unchecked() },
246 }
247 }
248}
249
250impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
251 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 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 unsafe { self.find_leaf_edges_spanning_range(range) }
324 }
325
326 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 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 pub(super) fn full_range(self) -> LazyLeafRange<marker::ValMut<'a>, K, V> {
355 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 pub(super) fn full_range(self) -> LazyLeafRange<marker::Dying, K, V> {
367 let self2 = unsafe { ptr::read(&self) };
370 full_range(self, self2)
371 }
372}
373
374impl<BorrowType: marker::BorrowType, K, V>
375 Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
376{
377 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 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 fn next_kv(
427 self,
428 ) -> Result<
429 Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>,
430 NodeRef<BorrowType, K, V, marker::Internal>,
431 > {
432 let mut edge = self;
433 loop {
434 edge = match edge.right_kv() {
435 Ok(internal_kv) => return Ok(internal_kv),
436 Err(last_edge) => match last_edge.into_node().ascend() {
437 Ok(parent_edge) => parent_edge,
438 Err(root) => return Err(root),
439 },
440 }
441 }
442 }
443}
444
445impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> {
446 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 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 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 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 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 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 kv.into_kv_valmut()
565 }
566
567 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 kv.into_kv_valmut()
579 }
580}
581
582impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> {
583 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 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 #[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 #[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 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 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 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 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 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 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}