1use core::marker::PhantomData;
35use core::mem::{self, MaybeUninit};
36use core::ptr::{self, NonNull};
37use core::slice::SliceIndex;
38
39use crate::alloc::{Allocator, Layout};
40use crate::boxed::Box;
41
42const B: usize = 6;
43pub(super) const CAPACITY: usize = 2 * B - 1;
44pub(super) const MIN_LEN_AFTER_SPLIT: usize = B - 1;
45const KV_IDX_CENTER: usize = B - 1;
46const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1;
47const EDGE_IDX_RIGHT_OF_CENTER: usize = B;
48
49struct LeafNode<K, V> {
51 parent: Option<NonNull<InternalNode<K, V>>>,
53
54 parent_idx: MaybeUninit<u16>,
58
59 len: u16,
61
62 keys: [MaybeUninit<K>; CAPACITY],
65 vals: [MaybeUninit<V>; CAPACITY],
66}
67
68impl<K, V> LeafNode<K, V> {
69 unsafe fn init(this: *mut Self) {
71 unsafe {
74 (&raw mut (*this).parent).write(None);
76 (&raw mut (*this).len).write(0);
77 }
78 }
79
80 fn new<A: Allocator + Clone>(alloc: A) -> Box<Self, A> {
82 unsafe {
83 let mut leaf = Box::new_uninit_in(alloc);
84 LeafNode::init(leaf.as_mut_ptr());
85 leaf.assume_init()
86 }
87 }
88}
89
90#[repr(C)]
96struct InternalNode<K, V> {
98 data: LeafNode<K, V>,
99
100 edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B],
104}
105
106impl<K, V> InternalNode<K, V> {
107 unsafe fn new<A: Allocator + Clone>(alloc: A) -> Box<Self, A> {
114 unsafe {
115 let mut node = Box::<Self, _>::new_uninit_in(alloc);
116 LeafNode::init(&raw mut (*node.as_mut_ptr()).data);
118 node.assume_init()
119 }
120 }
121}
122
123type BoxedNode<K, V> = NonNull<LeafNode<K, V>>;
130
131pub(super) struct NodeRef<BorrowType, K, V, Type> {
183 height: usize,
189 node: NonNull<LeafNode<K, V>>,
192 _marker: PhantomData<(BorrowType, Type)>,
193}
194
195pub(super) type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>;
199
200impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {}
201impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
202 fn clone(&self) -> Self {
203 *self
204 }
205}
206
207unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}
208
209unsafe impl<K: Sync, V: Sync, Type> Send for NodeRef<marker::Immut<'_>, K, V, Type> {}
210unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Mut<'_>, K, V, Type> {}
211unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::ValMut<'_>, K, V, Type> {}
212unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
213unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {}
214
215impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
216 pub(super) fn new_leaf<A: Allocator + Clone>(alloc: A) -> Self {
217 Self::from_new_leaf(LeafNode::new(alloc))
218 }
219
220 fn from_new_leaf<A: Allocator + Clone>(leaf: Box<LeafNode<K, V>, A>) -> Self {
221 NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _marker: PhantomData }
222 }
223}
224
225impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
226 fn new_internal<A: Allocator + Clone>(child: Root<K, V>, alloc: A) -> Self {
227 let mut new_node = unsafe { InternalNode::new(alloc) };
228 new_node.edges[0].write(child.node);
229 unsafe { NodeRef::from_new_internal(new_node, child.height + 1) }
230 }
231
232 unsafe fn from_new_internal<A: Allocator + Clone>(
235 internal: Box<InternalNode<K, V>, A>,
236 height: usize,
237 ) -> Self {
238 debug_assert!(height > 0);
239 let node = NonNull::from(Box::leak(internal)).cast();
240 let mut this = NodeRef { height, node, _marker: PhantomData };
241 this.borrow_mut().correct_all_childrens_parent_links();
242 this
243 }
244}
245
246impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
247 fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self {
249 debug_assert!(height > 0);
250 NodeRef { height, node: node.cast(), _marker: PhantomData }
251 }
252}
253
254impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
255 fn as_internal_ptr(this: &Self) -> *mut InternalNode<K, V> {
259 this.node.as_ptr() as *mut InternalNode<K, V>
261 }
262}
263
264impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
265 fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
267 let ptr = Self::as_internal_ptr(self);
268 unsafe { &mut *ptr }
269 }
270}
271
272impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
273 pub(super) fn len(&self) -> usize {
278 unsafe { usize::from((*Self::as_leaf_ptr(self)).len) }
281 }
282
283 pub(super) fn height(&self) -> usize {
289 self.height
290 }
291
292 pub(super) fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
294 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
295 }
296
297 fn as_leaf_ptr(this: &Self) -> *mut LeafNode<K, V> {
301 this.node.as_ptr()
305 }
306}
307
308impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
309 pub(super) fn ascend(
319 self,
320 ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
321 const {
322 assert!(BorrowType::TRAVERSAL_PERMIT);
323 }
324
325 let leaf_ptr: *const _ = Self::as_leaf_ptr(&self);
328 unsafe { (*leaf_ptr).parent }
329 .as_ref()
330 .map(|parent| Handle {
331 node: NodeRef::from_internal(*parent, self.height + 1),
332 idx: unsafe { usize::from((*leaf_ptr).parent_idx.assume_init()) },
333 _marker: PhantomData,
334 })
335 .ok_or(self)
336 }
337
338 pub(super) fn first_edge(self) -> Handle<Self, marker::Edge> {
339 unsafe { Handle::new_edge(self, 0) }
340 }
341
342 pub(super) fn last_edge(self) -> Handle<Self, marker::Edge> {
343 let len = self.len();
344 unsafe { Handle::new_edge(self, len) }
345 }
346
347 pub(super) fn first_kv(self) -> Handle<Self, marker::KV> {
349 let len = self.len();
350 assert!(len > 0);
351 unsafe { Handle::new_kv(self, 0) }
352 }
353
354 pub(super) fn last_kv(self) -> Handle<Self, marker::KV> {
356 let len = self.len();
357 assert!(len > 0);
358 unsafe { Handle::new_kv(self, len - 1) }
359 }
360}
361
362impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
363 fn eq(&self, other: &Self) -> bool {
365 let Self { node, height, _marker } = self;
366 if node.eq(&other.node) {
367 debug_assert_eq!(*height, other.height);
368 true
369 } else {
370 false
371 }
372 }
373}
374
375impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
376 fn into_leaf(self) -> &'a LeafNode<K, V> {
378 let ptr = Self::as_leaf_ptr(&self);
379 unsafe { &*ptr }
381 }
382
383 pub(super) fn keys(&self) -> &[K] {
385 let leaf = self.into_leaf();
386 unsafe { leaf.keys.get_unchecked(..usize::from(leaf.len)).assume_init_ref() }
387 }
388}
389
390impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> {
391 pub(super) unsafe fn deallocate_and_ascend<A: Allocator + Clone>(
395 self,
396 alloc: A,
397 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Internal>, marker::Edge>> {
398 let height = self.height;
399 let node = self.node;
400 let ret = self.ascend().ok();
401 unsafe {
402 alloc.deallocate(
403 node.cast(),
404 if height > 0 {
405 Layout::new::<InternalNode<K, V>>()
406 } else {
407 Layout::new::<LeafNode<K, V>>()
408 },
409 );
410 }
411 ret
412 }
413}
414
415impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
416 unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
427 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
428 }
429
430 fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
432 let ptr = Self::as_leaf_ptr(self);
433 unsafe { &mut *ptr }
435 }
436
437 fn into_leaf_mut(mut self) -> &'a mut LeafNode<K, V> {
439 let ptr = Self::as_leaf_ptr(&mut self);
440 unsafe { &mut *ptr }
442 }
443
444 pub(super) fn dormant(&self) -> NodeRef<marker::DormantMut, K, V, Type> {
447 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
448 }
449}
450
451impl<K, V, Type> NodeRef<marker::DormantMut, K, V, Type> {
452 pub(super) unsafe fn awaken<'a>(self) -> NodeRef<marker::Mut<'a>, K, V, Type> {
459 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
460 }
461}
462
463impl<K, V, Type> NodeRef<marker::Dying, K, V, Type> {
464 fn as_leaf_dying(&mut self) -> &mut LeafNode<K, V> {
466 let ptr = Self::as_leaf_ptr(self);
467 unsafe { &mut *ptr }
469 }
470}
471
472impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
473 unsafe fn key_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
478 where
479 I: SliceIndex<[MaybeUninit<K>], Output = Output>,
480 {
481 unsafe { self.as_leaf_mut().keys.as_mut_slice().get_unchecked_mut(index) }
485 }
486
487 unsafe fn val_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
492 where
493 I: SliceIndex<[MaybeUninit<V>], Output = Output>,
494 {
495 unsafe { self.as_leaf_mut().vals.as_mut_slice().get_unchecked_mut(index) }
499 }
500}
501
502impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
503 unsafe fn edge_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
508 where
509 I: SliceIndex<[MaybeUninit<BoxedNode<K, V>>], Output = Output>,
510 {
511 unsafe { self.as_internal_mut().edges.as_mut_slice().get_unchecked_mut(index) }
515 }
516}
517
518impl<'a, K, V, Type> NodeRef<marker::ValMut<'a>, K, V, Type> {
519 unsafe fn into_key_val_mut_at(mut self, idx: usize) -> (&'a K, &'a mut V) {
522 let leaf = Self::as_leaf_ptr(&mut self);
526 let keys = unsafe { &raw const (*leaf).keys };
527 let vals = unsafe { &raw mut (*leaf).vals };
528 let keys: *const [_] = keys;
530 let vals: *mut [_] = vals;
531 let key = unsafe { (&*keys.get_unchecked(idx)).assume_init_ref() };
532 let val = unsafe { (&mut *vals.get_unchecked_mut(idx)).assume_init_mut() };
533 (key, val)
534 }
535}
536
537impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
538 pub(super) fn len_mut(&mut self) -> &mut u16 {
540 &mut self.as_leaf_mut().len
541 }
542}
543
544impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
545 unsafe fn correct_childrens_parent_links<R: Iterator<Item = usize>>(&mut self, range: R) {
548 for i in range {
549 debug_assert!(i <= self.len());
550 unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link();
551 }
552 }
553
554 fn correct_all_childrens_parent_links(&mut self) {
555 let len = self.len();
556 unsafe { self.correct_childrens_parent_links(0..=len) };
557 }
558}
559
560impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
561 fn set_parent_link(&mut self, parent: NonNull<InternalNode<K, V>>, parent_idx: usize) {
564 let leaf = Self::as_leaf_ptr(self);
565 unsafe { (*leaf).parent = Some(parent) };
566 unsafe { (*leaf).parent_idx.write(parent_idx as u16) };
567 }
568}
569
570impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
571 fn clear_parent_link(&mut self) {
573 let mut root_node = self.borrow_mut();
574 let leaf = root_node.as_leaf_mut();
575 leaf.parent = None;
576 }
577}
578
579impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
580 pub(super) fn new<A: Allocator + Clone>(alloc: A) -> Self {
582 NodeRef::new_leaf(alloc).forget_type()
583 }
584
585 pub(super) fn push_internal_level<A: Allocator + Clone>(
589 &mut self,
590 alloc: A,
591 ) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
592 super::mem::take_mut(self, |old_root| NodeRef::new_internal(old_root, alloc).forget_type());
593
594 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
596 }
597
598 pub(super) fn pop_internal_level<A: Allocator + Clone>(&mut self, alloc: A) {
608 assert!(self.height > 0);
609
610 let top = self.node;
611
612 let internal_self = unsafe { self.borrow_mut().cast_to_internal_unchecked() };
614 let internal_node = unsafe { &mut *NodeRef::as_internal_ptr(&internal_self) };
616 self.node = unsafe { internal_node.edges[0].assume_init_read() };
618 self.height -= 1;
619 self.clear_parent_link();
620
621 unsafe {
622 alloc.deallocate(top.cast(), Layout::new::<InternalNode<K, V>>());
623 }
624 }
625}
626
627impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> {
628 pub(super) fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
632 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
633 }
634
635 pub(super) fn borrow_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, Type> {
637 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
638 }
639
640 pub(super) fn into_dying(self) -> NodeRef<marker::Dying, K, V, Type> {
643 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
644 }
645}
646
647impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
648 pub(super) unsafe fn push_with_handle<'b>(
655 &mut self,
656 key: K,
657 val: V,
658 ) -> Handle<NodeRef<marker::Mut<'b>, K, V, marker::Leaf>, marker::KV> {
659 let len = self.len_mut();
660 let idx = usize::from(*len);
661 assert!(idx < CAPACITY);
662 *len += 1;
663 unsafe {
664 self.key_area_mut(idx).write(key);
665 self.val_area_mut(idx).write(val);
666 Handle::new_kv(
667 NodeRef { height: self.height, node: self.node, _marker: PhantomData },
668 idx,
669 )
670 }
671 }
672
673 pub(super) fn push(&mut self, key: K, val: V) -> *mut V {
676 unsafe { self.push_with_handle(key, val).into_val_mut() }
678 }
679}
680
681impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
682 pub(super) fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
685 assert!(edge.height == self.height - 1);
686
687 let len = self.len_mut();
688 let idx = usize::from(*len);
689 assert!(idx < CAPACITY);
690 *len += 1;
691 unsafe {
692 self.key_area_mut(idx).write(key);
693 self.val_area_mut(idx).write(val);
694 self.edge_area_mut(idx + 1).write(edge.node);
695 Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
696 }
697 }
698}
699
700impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> {
701 pub(super) fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
703 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
704 }
705}
706
707impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
708 pub(super) fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
710 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
711 }
712}
713
714impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
715 pub(super) fn force(
717 self,
718 ) -> ForceResult<
719 NodeRef<BorrowType, K, V, marker::Leaf>,
720 NodeRef<BorrowType, K, V, marker::Internal>,
721 > {
722 if self.height == 0 {
723 ForceResult::Leaf(NodeRef {
724 height: self.height,
725 node: self.node,
726 _marker: PhantomData,
727 })
728 } else {
729 ForceResult::Internal(NodeRef {
730 height: self.height,
731 node: self.node,
732 _marker: PhantomData,
733 })
734 }
735 }
736}
737
738impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
739 pub(super) unsafe fn cast_to_leaf_unchecked(
741 self,
742 ) -> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
743 debug_assert!(self.height == 0);
744 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
745 }
746
747 unsafe fn cast_to_internal_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
749 debug_assert!(self.height > 0);
750 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
751 }
752}
753
754pub(super) struct Handle<Node, Type> {
763 node: Node,
764 idx: usize,
765 _marker: PhantomData<Type>,
766}
767
768impl<Node: Copy, Type> Copy for Handle<Node, Type> {}
769impl<Node: Copy, Type> Clone for Handle<Node, Type> {
772 fn clone(&self) -> Self {
773 *self
774 }
775}
776
777impl<Node, Type> Handle<Node, Type> {
778 pub(super) fn into_node(self) -> Node {
780 self.node
781 }
782
783 pub(super) fn idx(&self) -> usize {
785 self.idx
786 }
787}
788
789impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
790 pub(super) unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
793 debug_assert!(idx < node.len());
794
795 Handle { node, idx, _marker: PhantomData }
796 }
797
798 pub(super) fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
799 unsafe { Handle::new_edge(self.node, self.idx) }
800 }
801
802 pub(super) fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
803 unsafe { Handle::new_edge(self.node, self.idx + 1) }
804 }
805}
806
807impl<BorrowType, K, V, NodeType, HandleType> PartialEq
808 for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
809{
810 fn eq(&self, other: &Self) -> bool {
811 let Self { node, idx, _marker } = self;
812 node.eq(&other.node) && *idx == other.idx
813 }
814}
815
816impl<BorrowType, K, V, NodeType, HandleType>
817 Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
818{
819 pub(super) fn reborrow(
821 &self,
822 ) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
823 Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
825 }
826}
827
828impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
829 pub(super) unsafe fn reborrow_mut(
835 &mut self,
836 ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
837 Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData }
839 }
840
841 pub(super) fn dormant(
845 &self,
846 ) -> Handle<NodeRef<marker::DormantMut, K, V, NodeType>, HandleType> {
847 Handle { node: self.node.dormant(), idx: self.idx, _marker: PhantomData }
848 }
849}
850
851impl<K, V, NodeType, HandleType> Handle<NodeRef<marker::DormantMut, K, V, NodeType>, HandleType> {
852 pub(super) unsafe fn awaken<'a>(
859 self,
860 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
861 Handle { node: unsafe { self.node.awaken() }, idx: self.idx, _marker: PhantomData }
862 }
863}
864
865impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
866 pub(super) unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
869 debug_assert!(idx <= node.len());
870
871 Handle { node, idx, _marker: PhantomData }
872 }
873
874 pub(super) fn left_kv(
875 self,
876 ) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
877 if self.idx > 0 {
878 Ok(unsafe { Handle::new_kv(self.node, self.idx - 1) })
879 } else {
880 Err(self)
881 }
882 }
883
884 pub(super) fn right_kv(
885 self,
886 ) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
887 if self.idx < self.node.len() {
888 Ok(unsafe { Handle::new_kv(self.node, self.idx) })
889 } else {
890 Err(self)
891 }
892 }
893}
894
895pub(super) enum LeftOrRight<T> {
896 Left(T),
897 Right(T),
898}
899
900fn splitpoint(edge_idx: usize) -> (usize, LeftOrRight<usize>) {
906 debug_assert!(edge_idx <= CAPACITY);
907 match edge_idx {
909 0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, LeftOrRight::Left(edge_idx)),
910 EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, LeftOrRight::Left(edge_idx)),
911 EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, LeftOrRight::Right(0)),
912 _ => (KV_IDX_CENTER + 1, LeftOrRight::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))),
913 }
914}
915
916impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
917 unsafe fn insert_fit(
921 mut self,
922 key: K,
923 val: V,
924 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
925 debug_assert!(self.node.len() < CAPACITY);
926 let new_len = self.node.len() + 1;
927
928 unsafe {
929 slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
930 slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
931 *self.node.len_mut() = new_len as u16;
932
933 Handle::new_kv(self.node, self.idx)
934 }
935 }
936}
937
938impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
939 fn insert<A: Allocator + Clone>(
945 self,
946 key: K,
947 val: V,
948 alloc: A,
949 ) -> (
950 Option<SplitResult<'a, K, V, marker::Leaf>>,
951 Handle<NodeRef<marker::DormantMut, K, V, marker::Leaf>, marker::KV>,
952 ) {
953 if self.node.len() < CAPACITY {
954 let handle = unsafe { self.insert_fit(key, val) };
956 (None, handle.dormant())
957 } else {
958 let (middle_kv_idx, insertion) = splitpoint(self.idx);
959 let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
960 let mut result = middle.split(alloc);
961 let insertion_edge = match insertion {
962 LeftOrRight::Left(insert_idx) => unsafe {
963 Handle::new_edge(result.left.reborrow_mut(), insert_idx)
964 },
965 LeftOrRight::Right(insert_idx) => unsafe {
966 Handle::new_edge(result.right.borrow_mut(), insert_idx)
967 },
968 };
969 let handle = unsafe { insertion_edge.insert_fit(key, val).dormant() };
972 (Some(result), handle)
973 }
974 }
975}
976
977impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
978 fn correct_parent_link(self) {
981 let ptr = unsafe { NonNull::new_unchecked(NodeRef::as_internal_ptr(&self.node)) };
983 let idx = self.idx;
984 let mut child = self.descend();
985 child.set_parent_link(ptr, idx);
986 }
987}
988
989impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
990 fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
994 debug_assert!(self.node.len() < CAPACITY);
995 debug_assert!(edge.height == self.node.height - 1);
996 let new_len = self.node.len() + 1;
997
998 unsafe {
999 slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
1000 slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
1001 slice_insert(self.node.edge_area_mut(..new_len + 1), self.idx + 1, edge.node);
1002 *self.node.len_mut() = new_len as u16;
1003
1004 self.node.correct_childrens_parent_links(self.idx + 1..new_len + 1);
1005 }
1006 }
1007
1008 fn insert<A: Allocator + Clone>(
1012 mut self,
1013 key: K,
1014 val: V,
1015 edge: Root<K, V>,
1016 alloc: A,
1017 ) -> Option<SplitResult<'a, K, V, marker::Internal>> {
1018 assert!(edge.height == self.node.height - 1);
1019
1020 if self.node.len() < CAPACITY {
1021 self.insert_fit(key, val, edge);
1022 None
1023 } else {
1024 let (middle_kv_idx, insertion) = splitpoint(self.idx);
1025 let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
1026 let mut result = middle.split(alloc);
1027 let mut insertion_edge = match insertion {
1028 LeftOrRight::Left(insert_idx) => unsafe {
1029 Handle::new_edge(result.left.reborrow_mut(), insert_idx)
1030 },
1031 LeftOrRight::Right(insert_idx) => unsafe {
1032 Handle::new_edge(result.right.borrow_mut(), insert_idx)
1033 },
1034 };
1035 insertion_edge.insert_fit(key, val, edge);
1036 Some(result)
1037 }
1038 }
1039}
1040
1041impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
1042 pub(super) fn insert_recursing<A: Allocator + Clone>(
1050 self,
1051 key: K,
1052 value: V,
1053 alloc: A,
1054 split_root: impl FnOnce(SplitResult<'a, K, V, marker::LeafOrInternal>),
1055 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
1056 let (mut split, handle) = match self.insert(key, value, alloc.clone()) {
1057 (None, handle) => return unsafe { handle.awaken() },
1060 (Some(split), handle) => (split.forget_node_type(), handle),
1061 };
1062
1063 loop {
1064 split = match split.left.ascend() {
1065 Ok(parent) => {
1066 match parent.insert(split.kv.0, split.kv.1, split.right, alloc.clone()) {
1067 None => return unsafe { handle.awaken() },
1070 Some(split) => split.forget_node_type(),
1071 }
1072 }
1073 Err(root) => {
1074 split_root(SplitResult { left: root, ..split });
1075 return unsafe { handle.awaken() };
1078 }
1079 };
1080 }
1081 }
1082}
1083
1084impl<BorrowType: marker::BorrowType, K, V>
1085 Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>
1086{
1087 pub(super) fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
1094 const {
1095 assert!(BorrowType::TRAVERSAL_PERMIT);
1096 }
1097
1098 let parent_ptr = NodeRef::as_internal_ptr(&self.node);
1106 let node = unsafe { (*parent_ptr).edges.get_unchecked(self.idx).assume_init_read() };
1107 NodeRef { node, height: self.node.height - 1, _marker: PhantomData }
1108 }
1109}
1110
1111impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
1112 pub(super) fn into_kv(self) -> (&'a K, &'a V) {
1113 debug_assert!(self.idx < self.node.len());
1114 let leaf = self.node.into_leaf();
1115 let k = unsafe { leaf.keys.get_unchecked(self.idx).assume_init_ref() };
1116 let v = unsafe { leaf.vals.get_unchecked(self.idx).assume_init_ref() };
1117 (k, v)
1118 }
1119}
1120
1121impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1122 pub(super) fn key_mut(&mut self) -> &mut K {
1123 unsafe { self.node.key_area_mut(self.idx).assume_init_mut() }
1124 }
1125
1126 pub(super) fn into_val_mut(self) -> &'a mut V {
1127 debug_assert!(self.idx < self.node.len());
1128 let leaf = self.node.into_leaf_mut();
1129 unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }
1130 }
1131
1132 pub(super) fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
1133 debug_assert!(self.idx < self.node.len());
1134 let leaf = self.node.into_leaf_mut();
1135 let k = unsafe { leaf.keys.get_unchecked_mut(self.idx).assume_init_mut() };
1136 let v = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() };
1137 (k, v)
1138 }
1139}
1140
1141impl<'a, K, V, NodeType> Handle<NodeRef<marker::ValMut<'a>, K, V, NodeType>, marker::KV> {
1142 pub(super) fn into_kv_valmut(self) -> (&'a K, &'a mut V) {
1143 unsafe { self.node.into_key_val_mut_at(self.idx) }
1144 }
1145}
1146
1147impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1148 pub(super) fn kv_mut(&mut self) -> (&mut K, &mut V) {
1149 debug_assert!(self.idx < self.node.len());
1150 unsafe {
1153 let leaf = self.node.as_leaf_mut();
1154 let key = leaf.keys.get_unchecked_mut(self.idx).assume_init_mut();
1155 let val = leaf.vals.get_unchecked_mut(self.idx).assume_init_mut();
1156 (key, val)
1157 }
1158 }
1159
1160 pub(super) fn replace_kv(&mut self, k: K, v: V) -> (K, V) {
1162 let (key, val) = self.kv_mut();
1163 (mem::replace(key, k), mem::replace(val, v))
1164 }
1165}
1166
1167impl<K, V, NodeType> Handle<NodeRef<marker::Dying, K, V, NodeType>, marker::KV> {
1168 pub(super) unsafe fn into_key_val(mut self) -> (K, V) {
1172 debug_assert!(self.idx < self.node.len());
1173 let leaf = self.node.as_leaf_dying();
1174 unsafe {
1175 let key = leaf.keys.get_unchecked_mut(self.idx).assume_init_read();
1176 let val = leaf.vals.get_unchecked_mut(self.idx).assume_init_read();
1177 (key, val)
1178 }
1179 }
1180
1181 #[inline]
1185 pub(super) unsafe fn drop_key_val(mut self) {
1186 struct Dropper<'a, T>(&'a mut MaybeUninit<T>);
1188 impl<T> Drop for Dropper<'_, T> {
1189 #[inline]
1190 fn drop(&mut self) {
1191 unsafe {
1192 self.0.assume_init_drop();
1193 }
1194 }
1195 }
1196
1197 debug_assert!(self.idx < self.node.len());
1198 let leaf = self.node.as_leaf_dying();
1199 unsafe {
1200 let key = leaf.keys.get_unchecked_mut(self.idx);
1201 let val = leaf.vals.get_unchecked_mut(self.idx);
1202 let _guard = Dropper(val);
1203 key.assume_init_drop();
1204 }
1206 }
1207}
1208
1209impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1210 fn split_leaf_data(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V) {
1213 debug_assert!(self.idx < self.node.len());
1214 let old_len = self.node.len();
1215 let new_len = old_len - self.idx - 1;
1216 new_node.len = new_len as u16;
1217 unsafe {
1218 let k = self.node.key_area_mut(self.idx).assume_init_read();
1219 let v = self.node.val_area_mut(self.idx).assume_init_read();
1220
1221 move_to_slice(
1222 self.node.key_area_mut(self.idx + 1..old_len),
1223 &mut new_node.keys[..new_len],
1224 );
1225 move_to_slice(
1226 self.node.val_area_mut(self.idx + 1..old_len),
1227 &mut new_node.vals[..new_len],
1228 );
1229
1230 *self.node.len_mut() = self.idx as u16;
1231 (k, v)
1232 }
1233 }
1234}
1235
1236impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
1237 pub(super) fn split<A: Allocator + Clone>(
1245 mut self,
1246 alloc: A,
1247 ) -> SplitResult<'a, K, V, marker::Leaf> {
1248 let mut new_node = LeafNode::new(alloc);
1249
1250 let kv = self.split_leaf_data(&mut new_node);
1251
1252 let right = NodeRef::from_new_leaf(new_node);
1253 SplitResult { left: self.node, kv, right }
1254 }
1255
1256 pub(super) fn remove(
1259 mut self,
1260 ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
1261 let old_len = self.node.len();
1262 unsafe {
1263 let k = slice_remove(self.node.key_area_mut(..old_len), self.idx);
1264 let v = slice_remove(self.node.val_area_mut(..old_len), self.idx);
1265 *self.node.len_mut() = (old_len - 1) as u16;
1266 ((k, v), self.left_edge())
1267 }
1268 }
1269}
1270
1271impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1272 pub(super) fn split<A: Allocator + Clone>(
1280 mut self,
1281 alloc: A,
1282 ) -> SplitResult<'a, K, V, marker::Internal> {
1283 let old_len = self.node.len();
1284 unsafe {
1285 let mut new_node = InternalNode::new(alloc);
1286 let kv = self.split_leaf_data(&mut new_node.data);
1287 let new_len = usize::from(new_node.data.len);
1288 move_to_slice(
1289 self.node.edge_area_mut(self.idx + 1..old_len + 1),
1290 &mut new_node.edges[..new_len + 1],
1291 );
1292
1293 let height = self.node.height;
1294 let right = NodeRef::from_new_internal(new_node, height);
1295
1296 SplitResult { left: self.node, kv, right }
1297 }
1298 }
1299}
1300
1301pub(super) struct BalancingContext<'a, K, V> {
1304 parent: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV>,
1305 left_child: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1306 right_child: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1307}
1308
1309impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1310 pub(super) fn consider_for_balancing(self) -> BalancingContext<'a, K, V> {
1311 let self1 = unsafe { ptr::read(&self) };
1312 let self2 = unsafe { ptr::read(&self) };
1313 BalancingContext {
1314 parent: self,
1315 left_child: self1.left_edge().descend(),
1316 right_child: self2.right_edge().descend(),
1317 }
1318 }
1319}
1320
1321impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1322 pub(super) fn choose_parent_kv(self) -> Result<LeftOrRight<BalancingContext<'a, K, V>>, Self> {
1337 match unsafe { ptr::read(&self) }.ascend() {
1338 Ok(parent_edge) => match parent_edge.left_kv() {
1339 Ok(left_parent_kv) => Ok(LeftOrRight::Left(BalancingContext {
1340 parent: unsafe { ptr::read(&left_parent_kv) },
1341 left_child: left_parent_kv.left_edge().descend(),
1342 right_child: self,
1343 })),
1344 Err(parent_edge) => match parent_edge.right_kv() {
1345 Ok(right_parent_kv) => Ok(LeftOrRight::Right(BalancingContext {
1346 parent: unsafe { ptr::read(&right_parent_kv) },
1347 left_child: self,
1348 right_child: right_parent_kv.right_edge().descend(),
1349 })),
1350 Err(_) => unreachable!("empty internal node"),
1351 },
1352 },
1353 Err(root) => Err(root),
1354 }
1355 }
1356}
1357
1358impl<'a, K, V> BalancingContext<'a, K, V> {
1359 pub(super) fn left_child_len(&self) -> usize {
1360 self.left_child.len()
1361 }
1362
1363 pub(super) fn right_child_len(&self) -> usize {
1364 self.right_child.len()
1365 }
1366
1367 pub(super) fn into_left_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1368 self.left_child
1369 }
1370
1371 pub(super) fn into_right_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1372 self.right_child
1373 }
1374
1375 pub(super) fn can_merge(&self) -> bool {
1378 self.left_child.len() + 1 + self.right_child.len() <= CAPACITY
1379 }
1380}
1381
1382impl<'a, K: 'a, V: 'a> BalancingContext<'a, K, V> {
1383 fn do_merge<
1385 F: FnOnce(
1386 NodeRef<marker::Mut<'a>, K, V, marker::Internal>,
1387 NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1388 ) -> R,
1389 R,
1390 A: Allocator,
1391 >(
1392 self,
1393 result: F,
1394 alloc: A,
1395 ) -> R {
1396 let Handle { node: mut parent_node, idx: parent_idx, _marker } = self.parent;
1397 let old_parent_len = parent_node.len();
1398 let mut left_node = self.left_child;
1399 let old_left_len = left_node.len();
1400 let mut right_node = self.right_child;
1401 let right_len = right_node.len();
1402 let new_left_len = old_left_len + 1 + right_len;
1403
1404 assert!(new_left_len <= CAPACITY);
1405
1406 unsafe {
1407 *left_node.len_mut() = new_left_len as u16;
1408
1409 let parent_key = slice_remove(parent_node.key_area_mut(..old_parent_len), parent_idx);
1410 left_node.key_area_mut(old_left_len).write(parent_key);
1411 move_to_slice(
1412 right_node.key_area_mut(..right_len),
1413 left_node.key_area_mut(old_left_len + 1..new_left_len),
1414 );
1415
1416 let parent_val = slice_remove(parent_node.val_area_mut(..old_parent_len), parent_idx);
1417 left_node.val_area_mut(old_left_len).write(parent_val);
1418 move_to_slice(
1419 right_node.val_area_mut(..right_len),
1420 left_node.val_area_mut(old_left_len + 1..new_left_len),
1421 );
1422
1423 slice_remove(&mut parent_node.edge_area_mut(..old_parent_len + 1), parent_idx + 1);
1424 parent_node.correct_childrens_parent_links(parent_idx + 1..old_parent_len);
1425 *parent_node.len_mut() -= 1;
1426
1427 if parent_node.height > 1 {
1428 let mut left_node = left_node.reborrow_mut().cast_to_internal_unchecked();
1431 let mut right_node = right_node.cast_to_internal_unchecked();
1432 move_to_slice(
1433 right_node.edge_area_mut(..right_len + 1),
1434 left_node.edge_area_mut(old_left_len + 1..new_left_len + 1),
1435 );
1436
1437 left_node.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);
1438
1439 alloc.deallocate(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
1440 } else {
1441 alloc.deallocate(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
1442 }
1443 }
1444 result(parent_node, left_node)
1445 }
1446
1447 pub(super) fn merge_tracking_parent<A: Allocator + Clone>(
1452 self,
1453 alloc: A,
1454 ) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
1455 self.do_merge(|parent, _child| parent, alloc)
1456 }
1457
1458 pub(super) fn merge_tracking_child<A: Allocator + Clone>(
1463 self,
1464 alloc: A,
1465 ) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1466 self.do_merge(|_parent, child| child, alloc)
1467 }
1468
1469 pub(super) fn merge_tracking_child_edge<A: Allocator + Clone>(
1475 self,
1476 track_edge_idx: LeftOrRight<usize>,
1477 alloc: A,
1478 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1479 let old_left_len = self.left_child.len();
1480 let right_len = self.right_child.len();
1481 assert!(match track_edge_idx {
1482 LeftOrRight::Left(idx) => idx <= old_left_len,
1483 LeftOrRight::Right(idx) => idx <= right_len,
1484 });
1485 let child = self.merge_tracking_child(alloc);
1486 let new_idx = match track_edge_idx {
1487 LeftOrRight::Left(idx) => idx,
1488 LeftOrRight::Right(idx) => old_left_len + 1 + idx,
1489 };
1490 unsafe { Handle::new_edge(child, new_idx) }
1491 }
1492
1493 pub(super) fn steal_left(
1498 mut self,
1499 track_right_edge_idx: usize,
1500 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1501 self.bulk_steal_left(1);
1502 unsafe { Handle::new_edge(self.right_child, 1 + track_right_edge_idx) }
1503 }
1504
1505 pub(super) fn steal_right(
1510 mut self,
1511 track_left_edge_idx: usize,
1512 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1513 self.bulk_steal_right(1);
1514 unsafe { Handle::new_edge(self.left_child, track_left_edge_idx) }
1515 }
1516
1517 pub(super) fn bulk_steal_left(&mut self, count: usize) {
1519 assert!(count > 0);
1520 unsafe {
1521 let left_node = &mut self.left_child;
1522 let old_left_len = left_node.len();
1523 let right_node = &mut self.right_child;
1524 let old_right_len = right_node.len();
1525
1526 assert!(old_right_len + count <= CAPACITY);
1528 assert!(old_left_len >= count);
1529
1530 let new_left_len = old_left_len - count;
1531 let new_right_len = old_right_len + count;
1532 *left_node.len_mut() = new_left_len as u16;
1533 *right_node.len_mut() = new_right_len as u16;
1534
1535 {
1537 slice_shr(right_node.key_area_mut(..new_right_len), count);
1539 slice_shr(right_node.val_area_mut(..new_right_len), count);
1540
1541 move_to_slice(
1543 left_node.key_area_mut(new_left_len + 1..old_left_len),
1544 right_node.key_area_mut(..count - 1),
1545 );
1546 move_to_slice(
1547 left_node.val_area_mut(new_left_len + 1..old_left_len),
1548 right_node.val_area_mut(..count - 1),
1549 );
1550
1551 let k = left_node.key_area_mut(new_left_len).assume_init_read();
1553 let v = left_node.val_area_mut(new_left_len).assume_init_read();
1554 let (k, v) = self.parent.replace_kv(k, v);
1555
1556 right_node.key_area_mut(count - 1).write(k);
1558 right_node.val_area_mut(count - 1).write(v);
1559 }
1560
1561 match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
1562 (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1563 slice_shr(right.edge_area_mut(..new_right_len + 1), count);
1565
1566 move_to_slice(
1568 left.edge_area_mut(new_left_len + 1..old_left_len + 1),
1569 right.edge_area_mut(..count),
1570 );
1571
1572 right.correct_childrens_parent_links(0..new_right_len + 1);
1573 }
1574 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1575 _ => unreachable!(),
1576 }
1577 }
1578 }
1579
1580 pub(super) fn bulk_steal_right(&mut self, count: usize) {
1582 assert!(count > 0);
1583 unsafe {
1584 let left_node = &mut self.left_child;
1585 let old_left_len = left_node.len();
1586 let right_node = &mut self.right_child;
1587 let old_right_len = right_node.len();
1588
1589 assert!(old_left_len + count <= CAPACITY);
1591 assert!(old_right_len >= count);
1592
1593 let new_left_len = old_left_len + count;
1594 let new_right_len = old_right_len - count;
1595 *left_node.len_mut() = new_left_len as u16;
1596 *right_node.len_mut() = new_right_len as u16;
1597
1598 {
1600 let k = right_node.key_area_mut(count - 1).assume_init_read();
1602 let v = right_node.val_area_mut(count - 1).assume_init_read();
1603 let (k, v) = self.parent.replace_kv(k, v);
1604
1605 left_node.key_area_mut(old_left_len).write(k);
1607 left_node.val_area_mut(old_left_len).write(v);
1608
1609 move_to_slice(
1611 right_node.key_area_mut(..count - 1),
1612 left_node.key_area_mut(old_left_len + 1..new_left_len),
1613 );
1614 move_to_slice(
1615 right_node.val_area_mut(..count - 1),
1616 left_node.val_area_mut(old_left_len + 1..new_left_len),
1617 );
1618
1619 slice_shl(right_node.key_area_mut(..old_right_len), count);
1621 slice_shl(right_node.val_area_mut(..old_right_len), count);
1622 }
1623
1624 match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
1625 (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1626 move_to_slice(
1628 right.edge_area_mut(..count),
1629 left.edge_area_mut(old_left_len + 1..new_left_len + 1),
1630 );
1631
1632 slice_shl(right.edge_area_mut(..old_right_len + 1), count);
1634
1635 left.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);
1636 right.correct_childrens_parent_links(0..new_right_len + 1);
1637 }
1638 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1639 _ => unreachable!(),
1640 }
1641 }
1642 }
1643}
1644
1645impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1646 pub(super) fn forget_node_type(
1647 self,
1648 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1649 unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1650 }
1651}
1652
1653impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
1654 pub(super) fn forget_node_type(
1655 self,
1656 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1657 unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1658 }
1659}
1660
1661impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> {
1662 pub(super) fn forget_node_type(
1663 self,
1664 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
1665 unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
1666 }
1667}
1668
1669impl<BorrowType, K, V, Type> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, Type> {
1670 pub(super) fn force(
1672 self,
1673 ) -> ForceResult<
1674 Handle<NodeRef<BorrowType, K, V, marker::Leaf>, Type>,
1675 Handle<NodeRef<BorrowType, K, V, marker::Internal>, Type>,
1676 > {
1677 match self.node.force() {
1678 ForceResult::Leaf(node) => {
1679 ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData })
1680 }
1681 ForceResult::Internal(node) => {
1682 ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData })
1683 }
1684 }
1685 }
1686}
1687
1688impl<'a, K, V, Type> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, Type> {
1689 pub(super) unsafe fn cast_to_leaf_unchecked(
1691 self,
1692 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, Type> {
1693 let node = unsafe { self.node.cast_to_leaf_unchecked() };
1694 Handle { node, idx: self.idx, _marker: PhantomData }
1695 }
1696}
1697
1698impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1699 pub(super) fn move_suffix(
1702 &mut self,
1703 right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1704 ) {
1705 unsafe {
1706 let new_left_len = self.idx;
1707 let mut left_node = self.reborrow_mut().into_node();
1708 let old_left_len = left_node.len();
1709
1710 let new_right_len = old_left_len - new_left_len;
1711 let mut right_node = right.reborrow_mut();
1712
1713 assert!(right_node.len() == 0);
1714 assert!(left_node.height == right_node.height);
1715
1716 if new_right_len > 0 {
1717 *left_node.len_mut() = new_left_len as u16;
1718 *right_node.len_mut() = new_right_len as u16;
1719
1720 move_to_slice(
1721 left_node.key_area_mut(new_left_len..old_left_len),
1722 right_node.key_area_mut(..new_right_len),
1723 );
1724 move_to_slice(
1725 left_node.val_area_mut(new_left_len..old_left_len),
1726 right_node.val_area_mut(..new_right_len),
1727 );
1728 match (left_node.force(), right_node.force()) {
1729 (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1730 move_to_slice(
1731 left.edge_area_mut(new_left_len + 1..old_left_len + 1),
1732 right.edge_area_mut(1..new_right_len + 1),
1733 );
1734 right.correct_childrens_parent_links(1..new_right_len + 1);
1735 }
1736 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1737 _ => unreachable!(),
1738 }
1739 }
1740 }
1741 }
1742}
1743
1744pub(super) enum ForceResult<Leaf, Internal> {
1745 Leaf(Leaf),
1746 Internal(Internal),
1747}
1748
1749pub(super) struct SplitResult<'a, K, V, NodeType> {
1751 pub left: NodeRef<marker::Mut<'a>, K, V, NodeType>,
1753 pub kv: (K, V),
1755 pub right: NodeRef<marker::Owned, K, V, NodeType>,
1757}
1758
1759impl<'a, K, V> SplitResult<'a, K, V, marker::Leaf> {
1760 pub(super) fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> {
1761 SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() }
1762 }
1763}
1764
1765impl<'a, K, V> SplitResult<'a, K, V, marker::Internal> {
1766 pub(super) fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> {
1767 SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() }
1768 }
1769}
1770
1771pub(super) mod marker {
1772 use core::marker::PhantomData;
1773
1774 pub(crate) enum Leaf {}
1775 pub(crate) enum Internal {}
1776 pub(crate) enum LeafOrInternal {}
1777
1778 pub(crate) enum Owned {}
1779 pub(crate) enum Dying {}
1780 pub(crate) enum DormantMut {}
1781 pub(crate) struct Immut<'a>(PhantomData<&'a ()>);
1782 pub(crate) struct Mut<'a>(PhantomData<&'a mut ()>);
1783 pub(crate) struct ValMut<'a>(PhantomData<&'a mut ()>);
1784
1785 pub(crate) trait BorrowType {
1786 const TRAVERSAL_PERMIT: bool = true;
1790 }
1791 impl BorrowType for Owned {
1792 const TRAVERSAL_PERMIT: bool = false;
1797 }
1798 impl BorrowType for Dying {}
1799 impl<'a> BorrowType for Immut<'a> {}
1800 impl<'a> BorrowType for Mut<'a> {}
1801 impl<'a> BorrowType for ValMut<'a> {}
1802 impl BorrowType for DormantMut {}
1803
1804 pub(crate) enum KV {}
1805 pub(crate) enum Edge {}
1806}
1807
1808unsafe fn slice_insert<T>(slice: &mut [MaybeUninit<T>], idx: usize, val: T) {
1813 unsafe {
1814 let len = slice.len();
1815 debug_assert!(len > idx);
1816 let slice_ptr = slice.as_mut_ptr();
1817 if len > idx + 1 {
1818 ptr::copy(slice_ptr.add(idx), slice_ptr.add(idx + 1), len - idx - 1);
1819 }
1820 (*slice_ptr.add(idx)).write(val);
1821 }
1822}
1823
1824unsafe fn slice_remove<T>(slice: &mut [MaybeUninit<T>], idx: usize) -> T {
1830 unsafe {
1831 let len = slice.len();
1832 debug_assert!(idx < len);
1833 let slice_ptr = slice.as_mut_ptr();
1834 let ret = (*slice_ptr.add(idx)).assume_init_read();
1835 ptr::copy(slice_ptr.add(idx + 1), slice_ptr.add(idx), len - idx - 1);
1836 ret
1837 }
1838}
1839
1840unsafe fn slice_shl<T>(slice: &mut [MaybeUninit<T>], distance: usize) {
1845 unsafe {
1846 let slice_ptr = slice.as_mut_ptr();
1847 ptr::copy(slice_ptr.add(distance), slice_ptr, slice.len() - distance);
1848 }
1849}
1850
1851unsafe fn slice_shr<T>(slice: &mut [MaybeUninit<T>], distance: usize) {
1856 unsafe {
1857 let slice_ptr = slice.as_mut_ptr();
1858 ptr::copy(slice_ptr, slice_ptr.add(distance), slice.len() - distance);
1859 }
1860}
1861
1862fn move_to_slice<T>(src: &mut [MaybeUninit<T>], dst: &mut [MaybeUninit<T>]) {
1866 assert!(src.len() == dst.len());
1867 unsafe {
1868 ptr::copy_nonoverlapping(src.as_ptr(), dst.as_mut_ptr(), src.len());
1869 }
1870}
1871
1872#[cfg(test)]
1873mod tests;