1 // This is an attempt at an implementation following the ideal
4 // struct BTreeMap<K, V> {
6 // root: Option<Box<Node<K, V, height>>>
9 // struct Node<K, V, height: usize> {
10 // keys: [K; 2 * B - 1],
11 // vals: [V; 2 * B - 1],
12 // edges: if height > 0 {
13 // [Box<Node<K, V, height - 1>>; 2 * B]
15 // parent: Option<NonNull<Node<K, V, height + 1>>>,
21 // Since Rust doesn't actually have dependent types and polymorphic recursion,
22 // we make do with lots of unsafety.
24 // A major goal of this module is to avoid complexity by treating the tree as a generic (if
25 // weirdly shaped) container and avoiding dealing with most of the B-Tree invariants. As such,
26 // this module doesn't care whether the entries are sorted, which nodes can be underfull, or
27 // even what underfull means. However, we do rely on a few invariants:
29 // - Trees must have uniform depth/height. This means that every path down to a leaf from a
30 // given node has exactly the same length.
31 // - A node of length `n` has `n` keys, `n` values, and (in an internal node) `n + 1` edges.
32 // This implies that even an empty internal node has at least one edge.
34 use core::cmp::Ordering;
35 use core::marker::PhantomData;
36 use core::mem::{self, MaybeUninit};
37 use core::ptr::{self, NonNull, Unique};
40 use crate::alloc::{AllocRef, Global, Layout};
41 use crate::boxed::Box;
44 pub const MIN_LEN: usize = B - 1;
45 pub const CAPACITY: usize = 2 * B - 1;
46 const KV_IDX_CENTER: usize = B - 1;
47 const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1;
48 const EDGE_IDX_RIGHT_OF_CENTER: usize = B;
50 /// The underlying representation of leaf nodes.
52 struct LeafNode<K, V> {
53 /// We want to be covariant in `K` and `V`.
54 parent: Option<NonNull<InternalNode<K, V>>>,
56 /// This node's index into the parent node's `edges` array.
57 /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`.
58 /// This is only guaranteed to be initialized when `parent` is non-null.
59 parent_idx: MaybeUninit<u16>,
61 /// The number of keys and values this node stores.
63 /// This next to `parent_idx` to encourage the compiler to join `len` and
64 /// `parent_idx` into the same 32-bit word, reducing space overhead.
67 /// The arrays storing the actual data of the node. Only the first `len` elements of each
68 /// array are initialized and valid.
69 keys: [MaybeUninit<K>; CAPACITY],
70 vals: [MaybeUninit<V>; CAPACITY],
73 impl<K, V> LeafNode<K, V> {
74 /// Creates a new `LeafNode`. Unsafe because all nodes should really be hidden behind
75 /// `BoxedNode`, preventing accidental dropping of uninitialized keys and values.
76 unsafe fn new() -> Self {
78 // As a general policy, we leave fields uninitialized if they can be, as this should
79 // be both slightly faster and easier to track in Valgrind.
80 keys: MaybeUninit::uninit_array(),
81 vals: MaybeUninit::uninit_array(),
83 parent_idx: MaybeUninit::uninit(),
89 /// The underlying representation of internal nodes. As with `LeafNode`s, these should be hidden
90 /// behind `BoxedNode`s to prevent dropping uninitialized keys and values. Any pointer to an
91 /// `InternalNode` can be directly casted to a pointer to the underlying `LeafNode` portion of the
92 /// node, allowing code to act on leaf and internal nodes generically without having to even check
93 /// which of the two a pointer is pointing at. This property is enabled by the use of `repr(C)`.
95 struct InternalNode<K, V> {
98 /// The pointers to the children of this node. `len + 1` of these are considered
99 /// initialized and valid. Although during the process of `into_iter` or `drop`,
100 /// some pointers are dangling while others still need to be traversed.
101 edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B],
104 impl<K, V> InternalNode<K, V> {
105 /// Creates a new `InternalNode`.
107 /// This is unsafe for two reasons. First, it returns an `InternalNode` by value, risking
108 /// dropping of uninitialized fields. Second, an invariant of internal nodes is that `len + 1`
109 /// edges are initialized and valid, meaning that even when the node is empty (having a
110 /// `len` of 0), there must be one initialized and valid edge. This function does not set up
112 unsafe fn new() -> Self {
113 InternalNode { data: unsafe { LeafNode::new() }, edges: MaybeUninit::uninit_array() }
117 /// A managed, non-null pointer to a node. This is either an owned pointer to
118 /// `LeafNode<K, V>` or an owned pointer to `InternalNode<K, V>`.
120 /// However, `BoxedNode` contains no information as to which of the two types
121 /// of nodes it actually contains, and, partially due to this lack of information,
122 /// has no destructor.
123 struct BoxedNode<K, V> {
124 ptr: Unique<LeafNode<K, V>>,
127 impl<K, V> BoxedNode<K, V> {
128 fn from_leaf(node: Box<LeafNode<K, V>>) -> Self {
129 BoxedNode { ptr: Box::into_unique(node) }
132 fn from_internal(node: Box<InternalNode<K, V>>) -> Self {
133 BoxedNode { ptr: Box::into_unique(node).cast() }
136 unsafe fn from_ptr(ptr: NonNull<LeafNode<K, V>>) -> Self {
137 BoxedNode { ptr: unsafe { Unique::new_unchecked(ptr.as_ptr()) } }
140 fn as_ptr(&self) -> NonNull<LeafNode<K, V>> {
141 NonNull::from(self.ptr)
147 /// Note that this does not have a destructor, and must be cleaned up manually.
148 pub struct Root<K, V> {
149 node: BoxedNode<K, V>,
150 /// The number of levels below the root node.
154 unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> {}
155 unsafe impl<K: Send, V: Send> Send for Root<K, V> {}
157 impl<K, V> Root<K, V> {
158 /// Returns the number of levels below the root.
159 pub fn height(&self) -> usize {
163 /// Returns a new owned tree, with its own root node that is initially empty.
164 pub fn new_leaf() -> Self {
165 Root { node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), height: 0 }
168 /// Borrows and returns an immutable reference to the node owned by the root.
169 pub fn node_as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> {
170 NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }
173 /// Borrows and returns a mutable reference to the node owned by the root.
174 pub fn node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> {
175 NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }
178 pub fn node_as_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, marker::LeafOrInternal> {
179 NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }
182 pub fn into_ref(self) -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
183 NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData }
186 /// Adds a new internal node with a single edge, pointing to the previous root, and make that
187 /// new node the root. This increases the height by 1 and is the opposite of
188 /// `pop_internal_level`.
189 pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
190 let mut new_node = Box::new(unsafe { InternalNode::new() });
191 new_node.edges[0].write(unsafe { BoxedNode::from_ptr(self.node.as_ptr()) });
193 self.node = BoxedNode::from_internal(new_node);
197 NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData };
200 ret.reborrow_mut().first_edge().correct_parent_link();
206 /// Removes the internal root node, using its first child as the new root node.
207 /// As it is intended only to be called when the root node has only one child,
208 /// no cleanup is done on any of the other children.
209 /// This decreases the height by 1 and is the opposite of `push_internal_level`.
211 /// Requires exclusive access to the `Root` object but not to the root node;
212 /// it will not invalidate existing handles or references to the root node.
214 /// Panics if there is no internal level, i.e., if the root node is a leaf.
215 pub fn pop_internal_level(&mut self) {
216 assert!(self.height > 0);
218 let top = self.node.ptr;
222 self.node_as_mut().cast_unchecked::<marker::Internal>().first_edge().descend().node,
226 self.node_as_mut().as_leaf_mut().parent = None;
229 Global.dealloc(NonNull::from(top).cast(), Layout::new::<InternalNode<K, V>>());
234 // N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType`
235 // is `Mut`. This is technically wrong, but cannot result in any unsafety due to
236 // internal use of `NodeRef` because we stay completely generic over `K` and `V`.
237 // However, whenever a public type wraps `NodeRef`, make sure that it has the
239 /// A reference to a node.
241 /// This type has a number of parameters that controls how it acts:
242 /// - `BorrowType`: This can be `Immut<'a>`, `Mut<'a>` or `ValMut<'a>' for some `'a`
244 /// When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`,
245 /// when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`,
246 /// when this is `ValMut<'a>`, the `NodeRef` acts as immutable with respect
247 /// to keys and tree structure, but allows mutable references to values,
248 /// and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`.
249 /// - `K` and `V`: These control what types of things are stored in the nodes.
250 /// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is
251 /// `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
252 /// `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
253 /// `NodeRef` could be pointing to either type of node.
254 pub struct NodeRef<BorrowType, K, V, Type> {
255 /// The number of levels below the node.
257 node: NonNull<LeafNode<K, V>>,
258 _marker: PhantomData<(BorrowType, Type)>,
261 impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {}
262 impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
263 fn clone(&self) -> Self {
268 unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}
270 unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {}
271 unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {}
272 unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMut<'a>, K, V, Type> {}
273 unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
275 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
276 /// Exposes the data of an internal node for reading.
278 /// Returns a raw ptr to avoid invalidating other references to this node,
279 /// which is possible when BorrowType is marker::ValMut.
280 fn as_internal_ptr(&self) -> *const InternalNode<K, V> {
281 self.node.as_ptr() as *const InternalNode<K, V>
285 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
286 /// Exposes the data of an internal node for reading,
287 /// when we know we have exclusive access.
288 fn as_internal(&mut self) -> &InternalNode<K, V> {
289 unsafe { &*self.as_internal_ptr() }
293 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
294 /// Exposes the data of an internal node for writing.
296 /// We don't need to return a raw ptr because we have unique access to the entire node.
297 fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
298 unsafe { &mut *(self.node.as_ptr() as *mut InternalNode<K, V>) }
302 impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
303 /// Finds the length of the node. This is the number of keys or values. In an
304 /// internal node, the number of edges is `len() + 1`.
305 /// For any node, the number of possible edge handles is also `len() + 1`.
306 /// Note that, despite being safe, calling this function can have the side effect
307 /// of invalidating mutable references that unsafe code has created.
308 pub fn len(&self) -> usize {
309 // Crucially, we only access the `len` field here. If BorrowType is marker::ValMut,
310 // there might be outstanding mutable references to values that we must not invalidate.
311 unsafe { usize::from((*self.as_leaf_ptr()).len) }
314 /// Returns the height of this node in the whole tree. Zero height denotes the
316 pub fn height(&self) -> usize {
320 /// Temporarily takes out another, immutable reference to the same node.
321 fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
322 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
325 /// Exposes the leaf "portion" of any leaf or internal node.
326 /// If the node is a leaf, this function simply opens up its data.
327 /// If the node is an internal node, so not a leaf, it does have all the data a leaf has
328 /// (header, keys and values), and this function exposes that.
330 /// Returns a raw ptr to avoid invalidating other references to this node,
331 /// which is possible when BorrowType is marker::ValMut.
332 fn as_leaf_ptr(&self) -> *const LeafNode<K, V> {
333 // The node must be valid for at least the LeafNode portion.
334 // This is not a reference in the NodeRef type because we don't know if
335 // it should be unique or shared.
339 /// Borrows a reference to one of the keys stored in the node.
342 /// The node has more than `idx` initialized elements.
343 pub unsafe fn key_at(&self, idx: usize) -> &K {
344 unsafe { self.reborrow().into_key_at(idx) }
347 /// Borrows a reference to one of the values stored in the node.
350 /// The node has more than `idx` initialized elements.
351 unsafe fn val_at(&self, idx: usize) -> &V {
352 unsafe { self.reborrow().into_val_at(idx) }
355 /// Finds the parent of the current node. Returns `Ok(handle)` if the current
356 /// node actually has a parent, where `handle` points to the edge of the parent
357 /// that points to the current node. Returns `Err(self)` if the current node has
358 /// no parent, giving back the original `NodeRef`.
360 /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
361 /// both, upon success, do nothing.
364 ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
365 // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut,
366 // there might be outstanding mutable references to values that we must not invalidate.
367 let leaf_ptr = self.as_leaf_ptr();
368 unsafe { (*leaf_ptr).parent }
370 .map(|parent| Handle {
372 height: self.height + 1,
374 _marker: PhantomData,
376 idx: unsafe { usize::from((*leaf_ptr).parent_idx.assume_init()) },
377 _marker: PhantomData,
382 pub fn first_edge(self) -> Handle<Self, marker::Edge> {
383 unsafe { Handle::new_edge(self, 0) }
386 pub fn last_edge(self) -> Handle<Self, marker::Edge> {
387 let len = self.len();
388 unsafe { Handle::new_edge(self, len) }
391 /// Note that `self` must be nonempty.
392 pub fn first_kv(self) -> Handle<Self, marker::KV> {
393 let len = self.len();
395 unsafe { Handle::new_kv(self, 0) }
398 /// Note that `self` must be nonempty.
399 pub fn last_kv(self) -> Handle<Self, marker::KV> {
400 let len = self.len();
402 unsafe { Handle::new_kv(self, len - 1) }
406 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
407 /// Exposes the data of a leaf node for reading in an immutable tree.
408 fn into_leaf(self) -> &'a LeafNode<K, V> {
409 // SAFETY: we can access the entire node freely and do no need raw pointers,
410 // because there can be no mutable references to this Immut tree.
411 unsafe { &(*self.as_leaf_ptr()) }
415 impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
416 /// Similar to `ascend`, gets a reference to a node's parent node, but also
417 /// deallocate the current node in the process. This is unsafe because the
418 /// current node will still be accessible despite being deallocated.
419 pub unsafe fn deallocate_and_ascend(
421 ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> {
422 let height = self.height;
423 let node = self.node;
424 let ret = self.ascend().ok();
429 Layout::new::<InternalNode<K, V>>()
431 Layout::new::<LeafNode<K, V>>()
439 impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
440 /// Unsafely asserts to the compiler some static information about whether this
441 /// node is a `Leaf` or an `Internal`.
442 unsafe fn cast_unchecked<NewType>(self) -> NodeRef<marker::Mut<'a>, K, V, NewType> {
443 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
446 /// Temporarily takes out another, mutable reference to the same node. Beware, as
447 /// this method is very dangerous, doubly so since it may not immediately appear
450 /// Because mutable pointers can roam anywhere around the tree, the returned
451 /// pointer can easily be used to make the original pointer dangling, out of
452 /// bounds, or invalid under stacked borrow rules.
453 // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef`
454 // that restricts the use of navigation methods on reborrowed pointers,
455 // preventing this unsafety.
456 unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
457 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
460 /// Exposes the leaf "portion" of any leaf or internal node for writing.
461 /// If the node is a leaf, this function simply opens up its data.
462 /// If the node is an internal node, so not a leaf, it does have all the data a leaf has
463 /// (header, keys and values), and this function exposes that.
465 /// We don't need to return a raw ptr because we have unique access to the entire node.
466 fn as_leaf_mut(&mut self) -> &'a mut LeafNode<K, V> {
467 unsafe { &mut (*self.node.as_ptr()) }
470 /// Borrows a mutable reference to one of the keys stored in the node.
473 /// The node has more than `idx` initialized elements.
474 pub unsafe fn key_mut_at(&mut self, idx: usize) -> &mut K {
475 unsafe { self.reborrow_mut().into_key_mut_at(idx) }
478 /// Borrows a mutable reference to one of the values stored in the node.
481 /// The node has more than `idx` initialized elements.
482 pub unsafe fn val_mut_at(&mut self, idx: usize) -> &mut V {
483 unsafe { self.reborrow_mut().into_val_mut_at(idx) }
486 fn keys_mut(&mut self) -> &mut [K] {
487 // SAFETY: the caller will not be able to call further methods on self
488 // until the key slice reference is dropped, as we have unique access
489 // for the lifetime of the borrow.
490 unsafe { self.reborrow_mut().into_key_slice_mut() }
493 fn vals_mut(&mut self) -> &mut [V] {
494 // SAFETY: the caller will not be able to call further methods on self
495 // until the value slice reference is dropped, as we have unique access
496 // for the lifetime of the borrow.
497 unsafe { self.reborrow_mut().into_val_slice_mut() }
501 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
503 /// The node has more than `idx` initialized elements.
504 unsafe fn into_key_at(self, idx: usize) -> &'a K {
505 unsafe { self.into_leaf().keys.get_unchecked(idx).assume_init_ref() }
509 /// The node has more than `idx` initialized elements.
510 unsafe fn into_val_at(self, idx: usize) -> &'a V {
511 unsafe { self.into_leaf().vals.get_unchecked(idx).assume_init_ref() }
515 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
516 fn into_key_slice_mut(mut self) -> &'a mut [K] {
517 // SAFETY: The keys of a node must always be initialized up to length.
519 slice::from_raw_parts_mut(
520 MaybeUninit::slice_as_mut_ptr(&mut self.as_leaf_mut().keys),
526 fn into_val_slice_mut(mut self) -> &'a mut [V] {
527 // SAFETY: The values of a node must always be initialized up to length.
529 slice::from_raw_parts_mut(
530 MaybeUninit::slice_as_mut_ptr(&mut self.as_leaf_mut().vals),
537 /// The node has more than `idx` initialized elements.
538 unsafe fn into_key_mut_at(mut self, idx: usize) -> &'a mut K {
539 debug_assert!(idx < self.len());
541 let leaf = self.as_leaf_mut();
542 unsafe { leaf.keys.get_unchecked_mut(idx).assume_init_mut() }
546 /// The node has more than `idx` initialized elements.
547 unsafe fn into_val_mut_at(mut self, idx: usize) -> &'a mut V {
548 debug_assert!(idx < self.len());
550 let leaf = self.as_leaf_mut();
551 unsafe { leaf.vals.get_unchecked_mut(idx).assume_init_mut() }
555 impl<'a, K, V, Type> NodeRef<marker::ValMut<'a>, K, V, Type> {
557 /// The node has more than `idx` initialized elements.
558 unsafe fn into_key_val_mut_at(self, idx: usize) -> (&'a K, &'a mut V) {
559 // We only create a reference to the one element we are interested in,
560 // to avoid aliasing with outstanding references to other elements,
561 // in particular, those returned to the caller in earlier iterations.
562 let leaf = self.node.as_ptr();
563 // We must coerce to unsized array pointers because of Rust issue #74679.
564 let keys: *const [_] = unsafe { &raw const (*leaf).keys };
565 let vals: *mut [_] = unsafe { &raw mut (*leaf).vals };
566 // SAFETY: The keys and values of a node must always be initialized up to length.
567 let key = unsafe { (&*keys.get_unchecked(idx)).assume_init_ref() };
568 let val = unsafe { (&mut *vals.get_unchecked_mut(idx)).assume_init_mut() };
573 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
574 /// Adds a key/value pair to the end of the node.
575 pub fn push(&mut self, key: K, val: V) {
576 let len = &mut self.as_leaf_mut().len;
577 let idx = usize::from(*len);
578 assert!(idx < CAPACITY);
581 ptr::write(self.key_mut_at(idx), key);
582 ptr::write(self.val_mut_at(idx), val);
586 /// Adds a key/value pair to the beginning of the node.
587 pub fn push_front(&mut self, key: K, val: V) {
588 assert!(self.len() < CAPACITY);
591 slice_insert(self.keys_mut(), 0, key);
592 slice_insert(self.vals_mut(), 0, val);
594 self.as_leaf_mut().len += 1;
598 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
600 /// 'first' and 'after_last' must be in range.
601 unsafe fn correct_childrens_parent_links(&mut self, first: usize, after_last: usize) {
602 debug_assert!(first <= self.len());
603 debug_assert!(after_last <= self.len() + 1);
604 for i in first..after_last {
605 unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link();
609 fn correct_all_childrens_parent_links(&mut self) {
610 let len = self.len();
611 unsafe { self.correct_childrens_parent_links(0, len + 1) };
615 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
616 /// Adds a key/value pair and an edge to go to the right of that pair to
617 /// the end of the node.
618 pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
619 assert!(edge.height == self.height - 1);
621 let len = &mut self.as_leaf_mut().len;
622 let idx = usize::from(*len);
623 assert!(idx < CAPACITY);
626 ptr::write(self.key_mut_at(idx), key);
627 ptr::write(self.val_mut_at(idx), val);
628 self.as_internal_mut().edges.get_unchecked_mut(idx + 1).write(edge.node);
629 Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
633 /// Adds a key/value pair and an edge to go to the left of that pair to
634 /// the beginning of the node.
635 pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
636 assert!(edge.height == self.height - 1);
637 assert!(self.len() < CAPACITY);
640 slice_insert(self.keys_mut(), 0, key);
641 slice_insert(self.vals_mut(), 0, val);
643 slice::from_raw_parts_mut(
644 MaybeUninit::slice_as_mut_ptr(&mut self.as_internal_mut().edges),
652 self.as_leaf_mut().len += 1;
654 self.correct_all_childrens_parent_links();
658 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
659 /// Removes a key/value pair from the end of this node and returns the pair.
660 /// If this is an internal node, also removes the edge that was to the right
661 /// of that pair and returns the orphaned node that this edge owned with its
663 pub fn pop(&mut self) -> (K, V, Option<Root<K, V>>) {
664 assert!(self.len() > 0);
666 let idx = self.len() - 1;
669 let key = ptr::read(self.key_at(idx));
670 let val = ptr::read(self.val_at(idx));
671 let edge = match self.reborrow_mut().force() {
672 ForceResult::Leaf(_) => None,
673 ForceResult::Internal(mut internal) => {
675 ptr::read(internal.as_internal().edges.get_unchecked(idx + 1).as_ptr());
676 let mut new_root = Root { node: edge, height: internal.height - 1 };
677 new_root.node_as_mut().as_leaf_mut().parent = None;
682 self.as_leaf_mut().len -= 1;
687 /// Removes a key/value pair from the beginning of this node. If this is an internal node,
688 /// also removes the edge that was to the left of that pair.
689 pub fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) {
690 assert!(self.len() > 0);
692 let old_len = self.len();
695 let key = slice_remove(self.keys_mut(), 0);
696 let val = slice_remove(self.vals_mut(), 0);
697 let edge = match self.reborrow_mut().force() {
698 ForceResult::Leaf(_) => None,
699 ForceResult::Internal(mut internal) => {
700 let edge = slice_remove(
701 slice::from_raw_parts_mut(
702 MaybeUninit::slice_as_mut_ptr(&mut internal.as_internal_mut().edges),
708 let mut new_root = Root { node: edge, height: internal.height - 1 };
709 new_root.node_as_mut().as_leaf_mut().parent = None;
711 for i in 0..old_len {
712 Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link();
719 self.as_leaf_mut().len -= 1;
725 fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) {
726 (self.keys_mut().as_mut_ptr(), self.vals_mut().as_mut_ptr())
730 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
731 /// Checks whether a node is an `Internal` node or a `Leaf` node.
735 NodeRef<BorrowType, K, V, marker::Leaf>,
736 NodeRef<BorrowType, K, V, marker::Internal>,
738 if self.height == 0 {
739 ForceResult::Leaf(NodeRef {
742 _marker: PhantomData,
745 ForceResult::Internal(NodeRef {
748 _marker: PhantomData,
754 /// A reference to a specific key/value pair or edge within a node. The `Node` parameter
755 /// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key/value
756 /// pair) or `Edge` (signifying a handle on an edge).
758 /// Note that even `Leaf` nodes can have `Edge` handles. Instead of representing a pointer to
759 /// a child node, these represent the spaces where child pointers would go between the key/value
760 /// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one
761 /// to the left of the node, one between the two pairs, and one at the right of the node.
762 pub struct Handle<Node, Type> {
765 _marker: PhantomData<Type>,
768 impl<Node: Copy, Type> Copy for Handle<Node, Type> {}
769 // We don't need the full generality of `#[derive(Clone)]`, as the only time `Node` will be
770 // `Clone`able is when it is an immutable reference and therefore `Copy`.
771 impl<Node: Copy, Type> Clone for Handle<Node, Type> {
772 fn clone(&self) -> Self {
777 impl<Node, Type> Handle<Node, Type> {
778 /// Retrieves the node that contains the edge or key/value pair this handle points to.
779 pub fn into_node(self) -> Node {
783 /// Returns the position of this handle in the node.
784 pub fn idx(&self) -> usize {
789 impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
790 /// Creates a new handle to a key/value pair in `node`.
791 /// Unsafe because the caller must ensure that `idx < node.len()`.
792 pub unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
793 debug_assert!(idx < node.len());
795 Handle { node, idx, _marker: PhantomData }
798 pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
799 unsafe { Handle::new_edge(self.node, self.idx) }
802 pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
803 unsafe { Handle::new_edge(self.node, self.idx + 1) }
807 impl<BorrowType, K, V, NodeType, HandleType> PartialEq
808 for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
810 fn eq(&self, other: &Self) -> bool {
811 self.node.node == other.node.node && self.idx == other.idx
815 impl<BorrowType, K, V, NodeType, HandleType> PartialOrd
816 for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
818 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
819 if self.node.node == other.node.node { Some(self.idx.cmp(&other.idx)) } else { None }
823 impl<BorrowType, K, V, NodeType, HandleType>
824 Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
826 /// Temporarily takes out another, immutable handle on the same location.
827 pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
828 // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
829 Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
833 impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
834 /// Temporarily takes out another, mutable handle on the same location. Beware, as
835 /// this method is very dangerous, doubly so since it may not immediately appear
838 /// For details, see `NodeRef::reborrow_mut`.
839 pub unsafe fn reborrow_mut(
841 ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
842 // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
843 Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData }
847 impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
848 /// Creates a new handle to an edge in `node`.
849 /// Unsafe because the caller must ensure that `idx <= node.len()`.
850 pub unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
851 debug_assert!(idx <= node.len());
853 Handle { node, idx, _marker: PhantomData }
856 pub fn left_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
858 Ok(unsafe { Handle::new_kv(self.node, self.idx - 1) })
864 pub fn right_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
865 if self.idx < self.node.len() {
866 Ok(unsafe { Handle::new_kv(self.node, self.idx) })
873 enum InsertionPlace {
878 /// Given an edge index where we want to insert into a node filled to capacity,
879 /// computes a sensible KV index of a split point and where to perform the insertion.
880 /// The goal of the split point is for its key and value to end up in a parent node;
881 /// the keys, values and edges to the left of the split point become the left child;
882 /// the keys, values and edges to the right of the split point become the right child.
883 fn splitpoint(edge_idx: usize) -> (usize, InsertionPlace) {
884 debug_assert!(edge_idx <= CAPACITY);
885 // Rust issue #74834 tries to explain these symmetric rules.
887 0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, InsertionPlace::Left(edge_idx)),
888 EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Left(edge_idx)),
889 EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Right(0)),
890 _ => (KV_IDX_CENTER + 1, InsertionPlace::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))),
894 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::Edge> {
895 /// Helps implementations of `insert_fit` for a particular `NodeType`,
896 /// by taking care of leaf data.
897 /// Inserts a new key/value pair between the key/value pairs to the right and left of
898 /// this edge. This method assumes that there is enough space in the node for the new
900 fn leafy_insert_fit(&mut self, key: K, val: V) {
901 // Necessary for correctness, but in a private module
902 debug_assert!(self.node.len() < CAPACITY);
905 slice_insert(self.node.keys_mut(), self.idx, key);
906 slice_insert(self.node.vals_mut(), self.idx, val);
908 self.node.as_leaf_mut().len += 1;
913 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
914 /// Inserts a new key/value pair between the key/value pairs to the right and left of
915 /// this edge. This method assumes that there is enough space in the node for the new
918 /// The returned pointer points to the inserted value.
919 fn insert_fit(&mut self, key: K, val: V) -> *mut V {
920 self.leafy_insert_fit(key, val);
921 unsafe { self.node.val_mut_at(self.idx) }
925 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
926 /// Inserts a new key/value pair between the key/value pairs to the right and left of
927 /// this edge. This method splits the node if there isn't enough room.
929 /// The returned pointer points to the inserted value.
930 fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
931 if self.node.len() < CAPACITY {
932 let ptr = self.insert_fit(key, val);
933 let kv = unsafe { Handle::new_kv(self.node, self.idx) };
934 (InsertResult::Fit(kv), ptr)
936 let (middle_kv_idx, insertion) = splitpoint(self.idx);
937 let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
938 let (mut left, k, v, mut right) = middle.split();
939 let ptr = match insertion {
940 InsertionPlace::Left(insert_idx) => unsafe {
941 Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val)
943 InsertionPlace::Right(insert_idx) => unsafe {
945 right.node_as_mut().cast_unchecked::<marker::Leaf>(),
948 .insert_fit(key, val)
951 (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), ptr)
956 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
957 /// Fixes the parent pointer and index in the child node below this edge. This is useful
958 /// when the ordering of edges has been changed, such as in the various `insert` methods.
959 fn correct_parent_link(mut self) {
960 let idx = self.idx as u16;
961 let ptr = NonNull::new(self.node.as_internal_mut());
962 let mut child = self.descend();
963 child.as_leaf_mut().parent = ptr;
964 child.as_leaf_mut().parent_idx.write(idx);
968 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
969 /// Inserts a new key/value pair and an edge that will go to the right of that new pair
970 /// between this edge and the key/value pair to the right of this edge. This method assumes
971 /// that there is enough space in the node for the new pair to fit.
972 fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
973 // Necessary for correctness, but in an internal module
974 debug_assert!(self.node.len() < CAPACITY);
975 debug_assert!(edge.height == self.node.height - 1);
978 self.leafy_insert_fit(key, val);
981 slice::from_raw_parts_mut(
982 MaybeUninit::slice_as_mut_ptr(&mut self.node.as_internal_mut().edges),
989 for i in (self.idx + 1)..(self.node.len() + 1) {
990 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
995 /// Inserts a new key/value pair and an edge that will go to the right of that new pair
996 /// between this edge and the key/value pair to the right of this edge. This method splits
997 /// the node if there isn't enough room.
1003 ) -> InsertResult<'a, K, V, marker::Internal> {
1004 assert!(edge.height == self.node.height - 1);
1006 if self.node.len() < CAPACITY {
1007 self.insert_fit(key, val, edge);
1008 let kv = unsafe { Handle::new_kv(self.node, self.idx) };
1009 InsertResult::Fit(kv)
1011 let (middle_kv_idx, insertion) = splitpoint(self.idx);
1012 let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
1013 let (mut left, k, v, mut right) = middle.split();
1015 InsertionPlace::Left(insert_idx) => unsafe {
1016 Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val, edge);
1018 InsertionPlace::Right(insert_idx) => unsafe {
1020 right.node_as_mut().cast_unchecked::<marker::Internal>(),
1023 .insert_fit(key, val, edge);
1026 InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right })
1031 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
1032 /// Inserts a new key/value pair between the key/value pairs to the right and left of
1033 /// this edge. This method splits the node if there isn't enough room, and tries to
1034 /// insert the split off portion into the parent node recursively, until the root is reached.
1036 /// If the returned result is a `Fit`, its handle's node can be this edge's node or an ancestor.
1037 /// If the returned result is a `Split`, the `left` field will be the root node.
1038 /// The returned pointer points to the inserted value.
1039 pub fn insert_recursing(
1043 ) -> (InsertResult<'a, K, V, marker::LeafOrInternal>, *mut V) {
1044 let (mut split, val_ptr) = match self.insert(key, value) {
1045 (InsertResult::Fit(handle), ptr) => {
1046 return (InsertResult::Fit(handle.forget_node_type()), ptr);
1048 (InsertResult::Split(split), val_ptr) => (split, val_ptr),
1052 split = match split.left.ascend() {
1053 Ok(parent) => match parent.insert(split.k, split.v, split.right) {
1054 InsertResult::Fit(handle) => {
1055 return (InsertResult::Fit(handle.forget_node_type()), val_ptr);
1057 InsertResult::Split(split) => split,
1060 return (InsertResult::Split(SplitResult { left: root, ..split }), val_ptr);
1067 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
1068 /// Finds the node pointed to by this edge.
1070 /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
1071 /// both, upon success, do nothing.
1072 pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
1073 // We need to use raw pointers to nodes because, if BorrowType is
1074 // marker::ValMut, there might be outstanding mutable references to
1075 // values that we must not invalidate. There's no worry accessing the
1076 // height field because that value is copied. Beware that, once the
1077 // node pointer is dereferenced, we access the edges array with a
1078 // reference (Rust issue #73987) and invalidate any other references
1079 // to or inside the array, should any be around.
1080 let internal_node = self.node.as_internal_ptr();
1082 height: self.node.height - 1,
1083 node: unsafe { (&*(*internal_node).edges.get_unchecked(self.idx).as_ptr()).as_ptr() },
1084 _marker: PhantomData,
1089 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
1090 pub fn into_kv(self) -> (&'a K, &'a V) {
1091 (unsafe { self.node.into_key_at(self.idx) }, unsafe { self.node.into_val_at(self.idx) })
1095 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1096 pub fn into_key_mut(self) -> &'a mut K {
1097 unsafe { self.node.into_key_mut_at(self.idx) }
1100 pub fn into_val_mut(self) -> &'a mut V {
1101 unsafe { self.node.into_val_mut_at(self.idx) }
1105 impl<'a, K, V, NodeType> Handle<NodeRef<marker::ValMut<'a>, K, V, NodeType>, marker::KV> {
1106 pub fn into_kv_valmut(self) -> (&'a K, &'a mut V) {
1107 unsafe { self.node.into_key_val_mut_at(self.idx) }
1111 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1112 pub fn kv_mut(&mut self) -> (&mut K, &mut V) {
1113 // We cannot call into_key_mut_at and into_val_mut_at, because calling the second one
1114 // invalidates the reference returned by the first.
1115 let leaf = self.node.as_leaf_mut();
1116 let key = unsafe { leaf.keys.get_unchecked_mut(self.idx).assume_init_mut() };
1117 let val = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() };
1122 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1123 /// Helps implementations of `split` for a particular `NodeType`,
1124 /// by taking care of leaf data.
1125 fn leafy_split(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V, usize) {
1127 let k = ptr::read(self.node.key_at(self.idx));
1128 let v = ptr::read(self.node.val_at(self.idx));
1130 let new_len = self.node.len() - self.idx - 1;
1132 ptr::copy_nonoverlapping(
1133 self.node.key_at(self.idx + 1),
1134 new_node.keys.as_mut_ptr() as *mut K,
1137 ptr::copy_nonoverlapping(
1138 self.node.val_at(self.idx + 1),
1139 new_node.vals.as_mut_ptr() as *mut V,
1143 self.node.as_leaf_mut().len = self.idx as u16;
1144 new_node.len = new_len as u16;
1150 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
1151 /// Splits the underlying node into three parts:
1153 /// - The node is truncated to only contain the key/value pairs to the right of
1155 /// - The key and value pointed to by this handle and extracted.
1156 /// - All the key/value pairs to the right of this handle are put into a newly
1158 pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) {
1160 let mut new_node = Box::new(LeafNode::new());
1162 let (k, v, _) = self.leafy_split(&mut new_node);
1164 (self.node, k, v, Root { node: BoxedNode::from_leaf(new_node), height: 0 })
1168 /// Removes the key/value pair pointed to by this handle and returns it, along with the edge
1169 /// that the key/value pair collapsed into.
1172 ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
1174 let k = slice_remove(self.node.keys_mut(), self.idx);
1175 let v = slice_remove(self.node.vals_mut(), self.idx);
1176 self.node.as_leaf_mut().len -= 1;
1177 ((k, v), self.left_edge())
1182 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1183 /// Returns `true` if it is valid to call `.merge()`, i.e., whether there is enough room in
1184 /// a node to hold the combination of the nodes to the left and right of this handle along
1185 /// with the key/value pair at this handle.
1186 pub fn can_merge(&self) -> bool {
1187 (self.reborrow().left_edge().descend().len()
1188 + self.reborrow().right_edge().descend().len()
1194 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1195 /// Splits the underlying node into three parts:
1197 /// - The node is truncated to only contain the edges and key/value pairs to the
1198 /// right of this handle.
1199 /// - The key and value pointed to by this handle and extracted.
1200 /// - All the edges and key/value pairs to the right of this handle are put into
1201 /// a newly allocated node.
1202 pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) {
1204 let mut new_node = Box::new(InternalNode::new());
1206 let (k, v, new_len) = self.leafy_split(&mut new_node.data);
1207 let height = self.node.height;
1208 let old_node = &*self.node.as_internal_ptr();
1210 ptr::copy_nonoverlapping(
1211 old_node.edges.as_ptr().add(self.idx + 1),
1212 new_node.edges.as_mut_ptr(),
1216 let mut new_root = Root { node: BoxedNode::from_internal(new_node), height };
1218 for i in 0..(new_len + 1) {
1219 Handle::new_edge(new_root.node_as_mut().cast_unchecked(), i).correct_parent_link();
1222 (self.node, k, v, new_root)
1226 /// Combines the node immediately to the left of this handle, the key/value pair pointed
1227 /// to by this handle, and the node immediately to the right of this handle into one new
1228 /// child of the underlying node, returning an edge referencing that new child.
1230 /// Panics unless this edge `.can_merge()`.
1233 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
1234 let self1 = unsafe { ptr::read(&self) };
1235 let self2 = unsafe { ptr::read(&self) };
1236 let mut left_node = self1.left_edge().descend();
1237 let left_len = left_node.len();
1238 let right_node = self2.right_edge().descend();
1239 let right_len = right_node.len();
1241 assert!(left_len + right_len < CAPACITY);
1245 left_node.keys_mut().get_unchecked_mut(left_len),
1246 slice_remove(self.node.keys_mut(), self.idx),
1248 ptr::copy_nonoverlapping(
1249 right_node.key_at(0),
1250 left_node.keys_mut().as_mut_ptr().add(left_len + 1),
1254 left_node.vals_mut().get_unchecked_mut(left_len),
1255 slice_remove(self.node.vals_mut(), self.idx),
1257 ptr::copy_nonoverlapping(
1258 right_node.val_at(0),
1259 left_node.vals_mut().as_mut_ptr().add(left_len + 1),
1263 slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1);
1264 for i in self.idx + 1..self.node.len() {
1265 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
1267 self.node.as_leaf_mut().len -= 1;
1269 left_node.as_leaf_mut().len += right_len as u16 + 1;
1271 if self.node.height > 1 {
1272 // SAFETY: the height of the nodes being merged is one below the height
1273 // of the node of this edge, thus above zero, so they are internal.
1274 let mut left_node = left_node.cast_unchecked();
1275 let mut right_node = right_node.cast_unchecked();
1276 ptr::copy_nonoverlapping(
1277 right_node.as_internal().edges.as_ptr(),
1278 left_node.as_internal_mut().edges.as_mut_ptr().add(left_len + 1),
1282 for i in left_len + 1..left_len + right_len + 2 {
1283 Handle::new_edge(left_node.reborrow_mut(), i).correct_parent_link();
1286 Global.dealloc(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
1288 Global.dealloc(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
1291 Handle::new_edge(self.node, self.idx)
1295 /// This removes a key/value pair from the left child and places it in the key/value storage
1296 /// pointed to by this handle while pushing the old key/value pair of this handle into the right
1298 pub fn steal_left(&mut self) {
1300 let (k, v, edge) = self.reborrow_mut().left_edge().descend().pop();
1302 let k = mem::replace(self.kv_mut().0, k);
1303 let v = mem::replace(self.kv_mut().1, v);
1305 match self.reborrow_mut().right_edge().descend().force() {
1306 ForceResult::Leaf(mut leaf) => leaf.push_front(k, v),
1307 ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap()),
1312 /// This removes a key/value pair from the right child and places it in the key/value storage
1313 /// pointed to by this handle while pushing the old key/value pair of this handle into the left
1315 pub fn steal_right(&mut self) {
1317 let (k, v, edge) = self.reborrow_mut().right_edge().descend().pop_front();
1319 let k = mem::replace(self.kv_mut().0, k);
1320 let v = mem::replace(self.kv_mut().1, v);
1322 match self.reborrow_mut().left_edge().descend().force() {
1323 ForceResult::Leaf(mut leaf) => leaf.push(k, v),
1324 ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap()),
1329 /// This does stealing similar to `steal_left` but steals multiple elements at once.
1330 pub fn bulk_steal_left(&mut self, count: usize) {
1332 let mut left_node = ptr::read(self).left_edge().descend();
1333 let left_len = left_node.len();
1334 let mut right_node = ptr::read(self).right_edge().descend();
1335 let right_len = right_node.len();
1337 // Make sure that we may steal safely.
1338 assert!(right_len + count <= CAPACITY);
1339 assert!(left_len >= count);
1341 let new_left_len = left_len - count;
1345 let left_kv = left_node.reborrow_mut().into_kv_pointers_mut();
1346 let right_kv = right_node.reborrow_mut().into_kv_pointers_mut();
1348 let kv = self.kv_mut();
1349 (kv.0 as *mut K, kv.1 as *mut V)
1352 // Make room for stolen elements in the right child.
1353 ptr::copy(right_kv.0, right_kv.0.add(count), right_len);
1354 ptr::copy(right_kv.1, right_kv.1.add(count), right_len);
1356 // Move elements from the left child to the right one.
1357 move_kv(left_kv, new_left_len + 1, right_kv, 0, count - 1);
1359 // Move parent's key/value pair to the right child.
1360 move_kv(parent_kv, 0, right_kv, count - 1, 1);
1362 // Move the left-most stolen pair to the parent.
1363 move_kv(left_kv, new_left_len, parent_kv, 0, 1);
1366 left_node.as_leaf_mut().len -= count as u16;
1367 right_node.as_leaf_mut().len += count as u16;
1369 match (left_node.force(), right_node.force()) {
1370 (ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
1371 // Make room for stolen edges.
1372 let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr();
1373 ptr::copy(right_edges, right_edges.add(count), right_len + 1);
1374 right.correct_childrens_parent_links(count, count + right_len + 1);
1376 move_edges(left, new_left_len + 1, right, 0, count);
1378 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1386 /// The symmetric clone of `bulk_steal_left`.
1387 pub fn bulk_steal_right(&mut self, count: usize) {
1389 let mut left_node = ptr::read(self).left_edge().descend();
1390 let left_len = left_node.len();
1391 let mut right_node = ptr::read(self).right_edge().descend();
1392 let right_len = right_node.len();
1394 // Make sure that we may steal safely.
1395 assert!(left_len + count <= CAPACITY);
1396 assert!(right_len >= count);
1398 let new_right_len = right_len - count;
1402 let left_kv = left_node.reborrow_mut().into_kv_pointers_mut();
1403 let right_kv = right_node.reborrow_mut().into_kv_pointers_mut();
1405 let kv = self.kv_mut();
1406 (kv.0 as *mut K, kv.1 as *mut V)
1409 // Move parent's key/value pair to the left child.
1410 move_kv(parent_kv, 0, left_kv, left_len, 1);
1412 // Move elements from the right child to the left one.
1413 move_kv(right_kv, 0, left_kv, left_len + 1, count - 1);
1415 // Move the right-most stolen pair to the parent.
1416 move_kv(right_kv, count - 1, parent_kv, 0, 1);
1418 // Fix right indexing
1419 ptr::copy(right_kv.0.add(count), right_kv.0, new_right_len);
1420 ptr::copy(right_kv.1.add(count), right_kv.1, new_right_len);
1423 left_node.as_leaf_mut().len += count as u16;
1424 right_node.as_leaf_mut().len -= count as u16;
1426 match (left_node.force(), right_node.force()) {
1427 (ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
1428 move_edges(right.reborrow_mut(), 0, left, left_len + 1, count);
1430 // Fix right indexing.
1431 let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr();
1432 ptr::copy(right_edges.add(count), right_edges, new_right_len + 1);
1433 right.correct_childrens_parent_links(0, new_right_len + 1);
1435 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1444 unsafe fn move_kv<K, V>(
1445 source: (*mut K, *mut V),
1446 source_offset: usize,
1447 dest: (*mut K, *mut V),
1452 ptr::copy_nonoverlapping(source.0.add(source_offset), dest.0.add(dest_offset), count);
1453 ptr::copy_nonoverlapping(source.1.add(source_offset), dest.1.add(dest_offset), count);
1457 // Source and destination must have the same height.
1458 unsafe fn move_edges<K, V>(
1459 mut source: NodeRef<marker::Mut<'_>, K, V, marker::Internal>,
1460 source_offset: usize,
1461 mut dest: NodeRef<marker::Mut<'_>, K, V, marker::Internal>,
1465 let source_ptr = source.as_internal().edges.as_ptr();
1466 let dest_ptr = dest.as_internal_mut().edges.as_mut_ptr();
1468 ptr::copy_nonoverlapping(source_ptr.add(source_offset), dest_ptr.add(dest_offset), count);
1469 dest.correct_childrens_parent_links(dest_offset, dest_offset + count);
1473 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> {
1474 /// Removes any static information asserting that this node is a `Leaf` node.
1475 pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
1476 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
1480 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
1481 /// Removes any static information asserting that this node is an `Internal` node.
1482 pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
1483 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
1487 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1488 pub fn forget_node_type(
1490 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1491 unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1495 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
1496 pub fn forget_node_type(
1498 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1499 unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1503 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> {
1504 pub fn forget_node_type(
1506 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
1507 unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
1511 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV> {
1512 pub fn forget_node_type(
1514 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
1515 unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
1519 impl<BorrowType, K, V, HandleType>
1520 Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType>
1522 /// Checks whether the underlying node is an `Internal` node or a `Leaf` node.
1526 Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>,
1527 Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>,
1529 match self.node.force() {
1530 ForceResult::Leaf(node) => {
1531 ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData })
1533 ForceResult::Internal(node) => {
1534 ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData })
1540 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1541 /// Move the suffix after `self` from one node to another one. `right` must be empty.
1542 /// The first edge of `right` remains unchanged.
1545 right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1548 let left_new_len = self.idx;
1549 let mut left_node = self.reborrow_mut().into_node();
1551 let right_new_len = left_node.len() - left_new_len;
1552 let mut right_node = right.reborrow_mut();
1554 assert!(right_node.len() == 0);
1555 assert!(left_node.height == right_node.height);
1557 if right_new_len > 0 {
1558 let left_kv = left_node.reborrow_mut().into_kv_pointers_mut();
1559 let right_kv = right_node.reborrow_mut().into_kv_pointers_mut();
1561 move_kv(left_kv, left_new_len, right_kv, 0, right_new_len);
1563 left_node.as_leaf_mut().len = left_new_len as u16;
1564 right_node.as_leaf_mut().len = right_new_len as u16;
1566 match (left_node.force(), right_node.force()) {
1567 (ForceResult::Internal(left), ForceResult::Internal(right)) => {
1568 move_edges(left, left_new_len + 1, right, 1, right_new_len);
1570 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1580 pub enum ForceResult<Leaf, Internal> {
1585 /// Result of insertion, when a node needed to expand beyond its capacity.
1586 /// Does not distinguish between `Leaf` and `Internal` because `Root` doesn't.
1587 pub struct SplitResult<'a, K, V> {
1588 // Altered node in existing tree with elements and edges that belong to the left of `k`.
1589 pub left: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1590 // Some key and value split off, to be inserted elsewhere.
1593 // Owned, unattached, new node with elements and edges that belong to the right of `k`.
1594 pub right: Root<K, V>,
1597 pub enum InsertResult<'a, K, V, Type> {
1598 Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>),
1599 Split(SplitResult<'a, K, V>),
1603 use core::marker::PhantomData;
1606 pub enum Internal {}
1607 pub enum LeafOrInternal {}
1610 pub struct Immut<'a>(PhantomData<&'a ()>);
1611 pub struct Mut<'a>(PhantomData<&'a mut ()>);
1612 pub struct ValMut<'a>(PhantomData<&'a mut ()>);
1618 unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) {
1620 ptr::copy(slice.as_ptr().add(idx), slice.as_mut_ptr().add(idx + 1), slice.len() - idx);
1621 ptr::write(slice.get_unchecked_mut(idx), val);
1625 unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T {
1627 let ret = ptr::read(slice.get_unchecked(idx));
1628 ptr::copy(slice.as_ptr().add(idx + 1), slice.as_mut_ptr().add(idx), slice.len() - idx - 1);