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 { Box<Node<K, V, height - 1>> } else { () }; 2 * B],
13 // parent: Option<(NonNull<Node<K, V, height + 1>>, u16)>,
18 // Since Rust doesn't actually have dependent types and polymorphic recursion,
19 // we make do with lots of unsafety.
21 // A major goal of this module is to avoid complexity by treating the tree as a generic (if
22 // weirdly shaped) container and avoiding dealing with most of the B-Tree invariants. As such,
23 // this module doesn't care whether the entries are sorted, which nodes can be underfull, or
24 // even what underfull means. However, we do rely on a few invariants:
26 // - Trees must have uniform depth/height. This means that every path down to a leaf from a
27 // given node has exactly the same length.
28 // - A node of length `n` has `n` keys, `n` values, and `n + 1` edges.
29 // This implies that even an empty node has at least one edge.
30 // For a leaf node, "having an edge" only means we can identify a position in the node,
31 // since leaf edges are empty and need no data representation. In an internal node,
32 // an edge both identifies a position and contains a pointer to a child node.
34 use core::marker::PhantomData;
35 use core::mem::{self, MaybeUninit};
36 use core::ptr::{self, NonNull};
37 use core::slice::SliceIndex;
39 use crate::alloc::{Allocator, Global, Layout};
40 use crate::boxed::Box;
43 pub const CAPACITY: usize = 2 * B - 1;
44 pub const MIN_LEN_AFTER_SPLIT: usize = B - 1;
45 const KV_IDX_CENTER: usize = B - 1;
46 const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1;
47 const EDGE_IDX_RIGHT_OF_CENTER: usize = B;
49 /// The underlying representation of leaf nodes and part of the representation of internal nodes.
50 struct LeafNode<K, V> {
51 /// We want to be covariant in `K` and `V`.
52 parent: Option<NonNull<InternalNode<K, V>>>,
54 /// This node's index into the parent node's `edges` array.
55 /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`.
56 /// This is only guaranteed to be initialized when `parent` is non-null.
57 parent_idx: MaybeUninit<u16>,
59 /// The number of keys and values this node stores.
62 /// The arrays storing the actual data of the node. Only the first `len` elements of each
63 /// array are initialized and valid.
64 keys: [MaybeUninit<K>; CAPACITY],
65 vals: [MaybeUninit<V>; CAPACITY],
68 impl<K, V> LeafNode<K, V> {
69 /// Initializes a new `LeafNode` in-place.
70 unsafe fn init(this: *mut Self) {
71 // As a general policy, we leave fields uninitialized if they can be, as this should
72 // be both slightly faster and easier to track in Valgrind.
74 // parent_idx, keys, and vals are all MaybeUninit
75 ptr::addr_of_mut!((*this).parent).write(None);
76 ptr::addr_of_mut!((*this).len).write(0);
80 /// Creates a new boxed `LeafNode`.
81 fn new() -> Box<Self> {
83 let mut leaf = Box::new_uninit();
84 LeafNode::init(leaf.as_mut_ptr());
90 /// The underlying representation of internal nodes. As with `LeafNode`s, these should be hidden
91 /// behind `BoxedNode`s to prevent dropping uninitialized keys and values. Any pointer to an
92 /// `InternalNode` can be directly cast to a pointer to the underlying `LeafNode` portion of the
93 /// node, allowing code to act on leaf and internal nodes generically without having to even check
94 /// which of the two a pointer is pointing at. This property is enabled by the use of `repr(C)`.
96 // gdb_providers.py uses this type name for introspection.
97 struct InternalNode<K, V> {
100 /// The pointers to the children of this node. `len + 1` of these are considered
101 /// initialized and valid, except that near the end, while the tree is held
102 /// through borrow type `Dying`, some of these pointers are dangling.
103 edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B],
106 impl<K, V> InternalNode<K, V> {
107 /// Creates a new boxed `InternalNode`.
110 /// An invariant of internal nodes is that they have at least one
111 /// initialized and valid edge. This function does not set up
113 unsafe fn new() -> Box<Self> {
115 let mut node = Box::<Self>::new_uninit();
116 // We only need to initialize the data; the edges are MaybeUninit.
117 LeafNode::init(ptr::addr_of_mut!((*node.as_mut_ptr()).data));
123 /// A managed, non-null pointer to a node. This is either an owned pointer to
124 /// `LeafNode<K, V>` or an owned pointer to `InternalNode<K, V>`.
126 /// However, `BoxedNode` contains no information as to which of the two types
127 /// of nodes it actually contains, and, partially due to this lack of information,
128 /// is not a separate type and has no destructor.
129 type BoxedNode<K, V> = NonNull<LeafNode<K, V>>;
131 // N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType`
132 // is `Mut`. This is technically wrong, but cannot result in any unsafety due to
133 // internal use of `NodeRef` because we stay completely generic over `K` and `V`.
134 // However, whenever a public type wraps `NodeRef`, make sure that it has the
137 /// A reference to a node.
139 /// This type has a number of parameters that controls how it acts:
140 /// - `BorrowType`: A dummy type that describes the kind of borrow and carries a lifetime.
141 /// - When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`.
142 /// - When this is `ValMut<'a>`, the `NodeRef` acts roughly like `&'a Node`
143 /// with respect to keys and tree structure, but also allows many
144 /// mutable references to values throughout the tree to coexist.
145 /// - When this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`,
146 /// although insert methods allow a mutable pointer to a value to coexist.
147 /// - When this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`,
148 /// but does not have a destructor, and must be cleaned up manually.
149 /// - When this is `Dying`, the `NodeRef` still acts roughly like `Box<Node>`,
150 /// but has methods to destroy the tree bit by bit, and ordinary methods,
151 /// while not marked as unsafe to call, can invoke UB if called incorrectly.
152 /// Since any `NodeRef` allows navigating through the tree, `BorrowType`
153 /// effectively applies to the entire tree, not just to the node itself.
154 /// - `K` and `V`: These are the types of keys and values stored in the nodes.
155 /// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is
156 /// `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
157 /// `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
158 /// `NodeRef` could be pointing to either type of node.
159 /// `Type` is named `NodeType` when used outside `NodeRef`.
161 /// Both `BorrowType` and `NodeType` restrict what methods we implement, to
162 /// exploit static type safety. There are limitations in the way we can apply
163 /// such restrictions:
164 /// - For each type parameter, we can only define a method either generically
165 /// or for one particular type. For example, we cannot define a method like
166 /// `into_kv` generically for all `BorrowType`, or once for all types that
167 /// carry a lifetime, because we want it to return `&'a` references.
168 /// Therefore, we define it only for the least powerful type `Immut<'a>`.
169 /// - We cannot get implicit coercion from say `Mut<'a>` to `Immut<'a>`.
170 /// Therefore, we have to explicitly call `reborrow` on a more powerfull
171 /// `NodeRef` in order to reach a method like `into_kv`.
173 /// All methods on `NodeRef` that return some kind of reference, either:
174 /// - Take `self` by value, and return the lifetime carried by `BorrowType`.
175 /// Sometimes, to invoke such a method, we need to call `reborrow_mut`.
176 /// - Take `self` by reference, and (implicitly) return that reference's
177 /// lifetime, instead of the lifetime carried by `BorrowType`. That way,
178 /// the borrow checker guarantees that the `NodeRef` remains borrowed as long
179 /// as the returned reference is used.
180 /// The methods supporting insert bend this rule by returning a raw pointer,
181 /// i.e., a reference without any lifetime.
182 pub struct NodeRef<BorrowType, K, V, Type> {
183 /// The number of levels that the node and the level of leaves are apart, a
184 /// constant of the node that cannot be entirely described by `Type`, and that
185 /// the node itself does not store. We only need to store the height of the root
186 /// node, and derive every other node's height from it.
187 /// Must be zero if `Type` is `Leaf` and non-zero if `Type` is `Internal`.
189 /// The pointer to the leaf or internal node. The definition of `InternalNode`
190 /// ensures that the pointer is valid either way.
191 node: NonNull<LeafNode<K, V>>,
192 _marker: PhantomData<(BorrowType, Type)>,
195 /// The root node of an owned tree.
197 /// Note that this does not have a destructor, and must be cleaned up manually.
198 pub type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>;
200 impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {}
201 impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
202 fn clone(&self) -> Self {
207 unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}
209 unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {}
210 unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {}
211 unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMut<'a>, K, V, Type> {}
212 unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
213 unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {}
215 impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
216 fn new_leaf() -> Self {
217 Self::from_new_leaf(LeafNode::new())
220 fn from_new_leaf(leaf: Box<LeafNode<K, V>>) -> Self {
221 NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _marker: PhantomData }
225 impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
226 fn new_internal(child: Root<K, V>) -> Self {
227 let mut new_node = unsafe { InternalNode::new() };
228 new_node.edges[0].write(child.node);
229 unsafe { NodeRef::from_new_internal(new_node, child.height + 1) }
233 /// `height` must not be zero.
234 unsafe fn from_new_internal(internal: Box<InternalNode<K, V>>, height: usize) -> Self {
235 debug_assert!(height > 0);
236 let node = NonNull::from(Box::leak(internal)).cast();
237 let mut this = NodeRef { height, node, _marker: PhantomData };
238 this.borrow_mut().correct_all_childrens_parent_links();
243 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
244 /// Unpack a node reference that was packed as `NodeRef::parent`.
245 fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self {
246 debug_assert!(height > 0);
247 NodeRef { height, node: node.cast(), _marker: PhantomData }
251 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
252 /// Exposes the data of an internal node.
254 /// Returns a raw ptr to avoid invalidating other references to this node.
255 fn as_internal_ptr(this: &Self) -> *mut InternalNode<K, V> {
256 // SAFETY: the static node type is `Internal`.
257 this.node.as_ptr() as *mut InternalNode<K, V>
261 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
262 /// Borrows exclusive access to the data of an internal node.
263 fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
264 let ptr = Self::as_internal_ptr(self);
269 impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
270 /// Finds the length of the node. This is the number of keys or values.
271 /// The number of edges is `len() + 1`.
272 /// Note that, despite being safe, calling this function can have the side effect
273 /// of invalidating mutable references that unsafe code has created.
274 pub fn len(&self) -> usize {
275 // Crucially, we only access the `len` field here. If BorrowType is marker::ValMut,
276 // there might be outstanding mutable references to values that we must not invalidate.
277 unsafe { usize::from((*Self::as_leaf_ptr(self)).len) }
280 /// Returns the number of levels that the node and leaves are apart. Zero
281 /// height means the node is a leaf itself. If you picture trees with the
282 /// root on top, the number says at which elevation the node appears.
283 /// If you picture trees with leaves on top, the number says how high
284 /// the tree extends above the node.
285 pub fn height(&self) -> usize {
289 /// Temporarily takes out another, immutable reference to the same node.
290 pub fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
291 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
294 /// Exposes the leaf portion of any leaf or internal node.
296 /// Returns a raw ptr to avoid invalidating other references to this node.
297 fn as_leaf_ptr(this: &Self) -> *mut LeafNode<K, V> {
298 // The node must be valid for at least the LeafNode portion.
299 // This is not a reference in the NodeRef type because we don't know if
300 // it should be unique or shared.
305 impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
306 /// Finds the parent of the current node. Returns `Ok(handle)` if the current
307 /// node actually has a parent, where `handle` points to the edge of the parent
308 /// that points to the current node. Returns `Err(self)` if the current node has
309 /// no parent, giving back the original `NodeRef`.
311 /// The method name assumes you picture trees with the root node on top.
313 /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
314 /// both, upon success, do nothing.
317 ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
318 assert!(BorrowType::PERMITS_TRAVERSAL);
319 // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut,
320 // there might be outstanding mutable references to values that we must not invalidate.
321 let leaf_ptr: *const _ = Self::as_leaf_ptr(&self);
322 unsafe { (*leaf_ptr).parent }
324 .map(|parent| Handle {
325 node: NodeRef::from_internal(*parent, self.height + 1),
326 idx: unsafe { usize::from((*leaf_ptr).parent_idx.assume_init()) },
327 _marker: PhantomData,
332 pub fn first_edge(self) -> Handle<Self, marker::Edge> {
333 unsafe { Handle::new_edge(self, 0) }
336 pub fn last_edge(self) -> Handle<Self, marker::Edge> {
337 let len = self.len();
338 unsafe { Handle::new_edge(self, len) }
341 /// Note that `self` must be nonempty.
342 pub fn first_kv(self) -> Handle<Self, marker::KV> {
343 let len = self.len();
345 unsafe { Handle::new_kv(self, 0) }
348 /// Note that `self` must be nonempty.
349 pub fn last_kv(self) -> Handle<Self, marker::KV> {
350 let len = self.len();
352 unsafe { Handle::new_kv(self, len - 1) }
356 impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
357 /// Could be a public implementation of PartialEq, but only used in this module.
358 fn eq(&self, other: &Self) -> bool {
359 let Self { node, height, _marker } = self;
360 if node.eq(&other.node) {
361 debug_assert_eq!(*height, other.height);
369 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
370 /// Exposes the leaf portion of any leaf or internal node in an immutable tree.
371 fn into_leaf(self) -> &'a LeafNode<K, V> {
372 let ptr = Self::as_leaf_ptr(&self);
373 // SAFETY: there can be no mutable references into this tree borrowed as `Immut`.
377 /// Borrows a view into the keys stored in the node.
378 pub fn keys(&self) -> &[K] {
379 let leaf = self.into_leaf();
381 MaybeUninit::slice_assume_init_ref(leaf.keys.get_unchecked(..usize::from(leaf.len)))
386 impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> {
387 /// Similar to `ascend`, gets a reference to a node's parent node, but also
388 /// deallocates the current node in the process. This is unsafe because the
389 /// current node will still be accessible despite being deallocated.
390 pub unsafe fn deallocate_and_ascend(
392 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Internal>, marker::Edge>> {
393 let height = self.height;
394 let node = self.node;
395 let ret = self.ascend().ok();
400 Layout::new::<InternalNode<K, V>>()
402 Layout::new::<LeafNode<K, V>>()
410 impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
411 /// Temporarily takes out another mutable reference to the same node. Beware, as
412 /// this method is very dangerous, doubly so since it may not immediately appear
415 /// Because mutable pointers can roam anywhere around the tree, the returned
416 /// pointer can easily be used to make the original pointer dangling, out of
417 /// bounds, or invalid under stacked borrow rules.
418 // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef`
419 // that restricts the use of navigation methods on reborrowed pointers,
420 // preventing this unsafety.
421 unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
422 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
425 /// Borrows exclusive access to the leaf portion of any leaf or internal node.
426 fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
427 let ptr = Self::as_leaf_ptr(self);
428 // SAFETY: we have exclusive access to the entire node.
432 /// Offers exclusive access to the leaf portion of any leaf or internal node.
433 fn into_leaf_mut(mut self) -> &'a mut LeafNode<K, V> {
434 let ptr = Self::as_leaf_ptr(&mut self);
435 // SAFETY: we have exclusive access to the entire node.
440 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
441 /// Borrows exclusive access to an element of the key storage area.
444 /// `index` is in bounds of 0..CAPACITY
445 unsafe fn key_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
447 I: SliceIndex<[MaybeUninit<K>], Output = Output>,
449 // SAFETY: the caller will not be able to call further methods on self
450 // until the key slice reference is dropped, as we have unique access
451 // for the lifetime of the borrow.
452 unsafe { self.as_leaf_mut().keys.as_mut_slice().get_unchecked_mut(index) }
455 /// Borrows exclusive access to an element or slice of the node's value storage area.
458 /// `index` is in bounds of 0..CAPACITY
459 unsafe fn val_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
461 I: SliceIndex<[MaybeUninit<V>], Output = Output>,
463 // SAFETY: the caller will not be able to call further methods on self
464 // until the value slice reference is dropped, as we have unique access
465 // for the lifetime of the borrow.
466 unsafe { self.as_leaf_mut().vals.as_mut_slice().get_unchecked_mut(index) }
470 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
471 /// Borrows exclusive access to an element or slice of the node's storage area for edge contents.
474 /// `index` is in bounds of 0..CAPACITY + 1
475 unsafe fn edge_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
477 I: SliceIndex<[MaybeUninit<BoxedNode<K, V>>], Output = Output>,
479 // SAFETY: the caller will not be able to call further methods on self
480 // until the edge slice reference is dropped, as we have unique access
481 // for the lifetime of the borrow.
482 unsafe { self.as_internal_mut().edges.as_mut_slice().get_unchecked_mut(index) }
486 impl<'a, K, V, Type> NodeRef<marker::ValMut<'a>, K, V, Type> {
488 /// - The node has more than `idx` initialized elements.
489 unsafe fn into_key_val_mut_at(mut self, idx: usize) -> (&'a K, &'a mut V) {
490 // We only create a reference to the one element we are interested in,
491 // to avoid aliasing with outstanding references to other elements,
492 // in particular, those returned to the caller in earlier iterations.
493 let leaf = Self::as_leaf_ptr(&mut self);
494 let keys = unsafe { ptr::addr_of!((*leaf).keys) };
495 let vals = unsafe { ptr::addr_of_mut!((*leaf).vals) };
496 // We must coerce to unsized array pointers because of Rust issue #74679.
497 let keys: *const [_] = keys;
498 let vals: *mut [_] = vals;
499 let key = unsafe { (&*keys.get_unchecked(idx)).assume_init_ref() };
500 let val = unsafe { (&mut *vals.get_unchecked_mut(idx)).assume_init_mut() };
505 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
506 /// Borrows exclusive access to the length of the node.
507 pub fn len_mut(&mut self) -> &mut u16 {
508 &mut self.as_leaf_mut().len
512 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
514 /// Every item returned by `range` is a valid edge index for the node.
515 unsafe fn correct_childrens_parent_links<R: Iterator<Item = usize>>(&mut self, range: R) {
517 debug_assert!(i <= self.len());
518 unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link();
522 fn correct_all_childrens_parent_links(&mut self) {
523 let len = self.len();
524 unsafe { self.correct_childrens_parent_links(0..=len) };
528 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
529 /// Sets the node's link to its parent edge,
530 /// without invalidating other references to the node.
531 fn set_parent_link(&mut self, parent: NonNull<InternalNode<K, V>>, parent_idx: usize) {
532 let leaf = Self::as_leaf_ptr(self);
533 unsafe { (*leaf).parent = Some(parent) };
534 unsafe { (*leaf).parent_idx.write(parent_idx as u16) };
538 impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
539 /// Clears the root's link to its parent edge.
540 fn clear_parent_link(&mut self) {
541 let mut root_node = self.borrow_mut();
542 let leaf = root_node.as_leaf_mut();
547 impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
548 /// Returns a new owned tree, with its own root node that is initially empty.
549 pub fn new() -> Self {
550 NodeRef::new_leaf().forget_type()
553 /// Adds a new internal node with a single edge pointing to the previous root node,
554 /// make that new node the root node, and return it. This increases the height by 1
555 /// and is the opposite of `pop_internal_level`.
556 pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
557 super::mem::take_mut(self, |old_root| NodeRef::new_internal(old_root).forget_type());
559 // `self.borrow_mut()`, except that we just forgot we're internal now:
560 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
563 /// Removes the internal root node, using its first child as the new root node.
564 /// As it is intended only to be called when the root node has only one child,
565 /// no cleanup is done on any of the keys, values and other children.
566 /// This decreases the height by 1 and is the opposite of `push_internal_level`.
568 /// Requires exclusive access to the `Root` object but not to the root node;
569 /// it will not invalidate other handles or references to the root node.
571 /// Panics if there is no internal level, i.e., if the root node is a leaf.
572 pub fn pop_internal_level(&mut self) {
573 assert!(self.height > 0);
577 // SAFETY: we asserted to be internal.
578 let internal_self = unsafe { self.borrow_mut().cast_to_internal_unchecked() };
579 // SAFETY: we borrowed `self` exclusively and its borrow type is exclusive.
580 let internal_node = unsafe { &mut *NodeRef::as_internal_ptr(&internal_self) };
581 // SAFETY: the first edge is always initialized.
582 self.node = unsafe { internal_node.edges[0].assume_init_read() };
584 self.clear_parent_link();
587 Global.deallocate(top.cast(), Layout::new::<InternalNode<K, V>>());
592 impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> {
593 /// Mutably borrows the owned root node. Unlike `reborrow_mut`, this is safe
594 /// because the return value cannot be used to destroy the root, and there
595 /// cannot be other references to the tree.
596 pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
597 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
600 /// Slightly mutably borrows the owned root node.
601 pub fn borrow_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, Type> {
602 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
605 /// Irreversibly transitions to a reference that permits traversal and offers
606 /// destructive methods and little else.
607 pub fn into_dying(self) -> NodeRef<marker::Dying, K, V, Type> {
608 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
612 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
613 /// Adds a key-value pair to the end of the node.
614 pub fn push(&mut self, key: K, val: V) {
615 let len = self.len_mut();
616 let idx = usize::from(*len);
617 assert!(idx < CAPACITY);
620 self.key_area_mut(idx).write(key);
621 self.val_area_mut(idx).write(val);
626 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
627 /// Adds a key-value pair, and an edge to go to the right of that pair,
628 /// to the end of the node.
629 pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
630 assert!(edge.height == self.height - 1);
632 let len = self.len_mut();
633 let idx = usize::from(*len);
634 assert!(idx < CAPACITY);
637 self.key_area_mut(idx).write(key);
638 self.val_area_mut(idx).write(val);
639 self.edge_area_mut(idx + 1).write(edge.node);
640 Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
645 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> {
646 /// Removes any static information asserting that this node is a `Leaf` node.
647 pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
648 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
652 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
653 /// Removes any static information asserting that this node is an `Internal` node.
654 pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
655 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
659 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
660 /// Checks whether a node is an `Internal` node or a `Leaf` node.
664 NodeRef<BorrowType, K, V, marker::Leaf>,
665 NodeRef<BorrowType, K, V, marker::Internal>,
667 if self.height == 0 {
668 ForceResult::Leaf(NodeRef {
671 _marker: PhantomData,
674 ForceResult::Internal(NodeRef {
677 _marker: PhantomData,
683 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
684 /// Unsafely asserts to the compiler the static information that this node is a `Leaf`.
685 unsafe fn cast_to_leaf_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
686 debug_assert!(self.height == 0);
687 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
690 /// Unsafely asserts to the compiler the static information that this node is an `Internal`.
691 unsafe fn cast_to_internal_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
692 debug_assert!(self.height > 0);
693 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
697 /// A reference to a specific key-value pair or edge within a node. The `Node` parameter
698 /// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key-value
699 /// pair) or `Edge` (signifying a handle on an edge).
701 /// Note that even `Leaf` nodes can have `Edge` handles. Instead of representing a pointer to
702 /// a child node, these represent the spaces where child pointers would go between the key-value
703 /// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one
704 /// to the left of the node, one between the two pairs, and one at the right of the node.
705 pub struct Handle<Node, Type> {
708 _marker: PhantomData<Type>,
711 impl<Node: Copy, Type> Copy for Handle<Node, Type> {}
712 // We don't need the full generality of `#[derive(Clone)]`, as the only time `Node` will be
713 // `Clone`able is when it is an immutable reference and therefore `Copy`.
714 impl<Node: Copy, Type> Clone for Handle<Node, Type> {
715 fn clone(&self) -> Self {
720 impl<Node, Type> Handle<Node, Type> {
721 /// Retrieves the node that contains the edge or key-value pair this handle points to.
722 pub fn into_node(self) -> Node {
726 /// Returns the position of this handle in the node.
727 pub fn idx(&self) -> usize {
732 impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
733 /// Creates a new handle to a key-value pair in `node`.
734 /// Unsafe because the caller must ensure that `idx < node.len()`.
735 pub unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
736 debug_assert!(idx < node.len());
738 Handle { node, idx, _marker: PhantomData }
741 pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
742 unsafe { Handle::new_edge(self.node, self.idx) }
745 pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
746 unsafe { Handle::new_edge(self.node, self.idx + 1) }
750 impl<BorrowType, K, V, NodeType, HandleType> PartialEq
751 for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
753 fn eq(&self, other: &Self) -> bool {
754 let Self { node, idx, _marker } = self;
755 node.eq(&other.node) && *idx == other.idx
759 impl<BorrowType, K, V, NodeType, HandleType>
760 Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
762 /// Temporarily takes out another immutable handle on the same location.
763 pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
764 // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
765 Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
769 impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
770 /// Temporarily takes out another mutable handle on the same location. Beware, as
771 /// this method is very dangerous, doubly so since it may not immediately appear
774 /// For details, see `NodeRef::reborrow_mut`.
775 pub unsafe fn reborrow_mut(
777 ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
778 // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
779 Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData }
783 impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
784 /// Creates a new handle to an edge in `node`.
785 /// Unsafe because the caller must ensure that `idx <= node.len()`.
786 pub unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
787 debug_assert!(idx <= node.len());
789 Handle { node, idx, _marker: PhantomData }
792 pub fn left_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
794 Ok(unsafe { Handle::new_kv(self.node, self.idx - 1) })
800 pub fn right_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
801 if self.idx < self.node.len() {
802 Ok(unsafe { Handle::new_kv(self.node, self.idx) })
809 pub enum LeftOrRight<T> {
814 /// Given an edge index where we want to insert into a node filled to capacity,
815 /// computes a sensible KV index of a split point and where to perform the insertion.
816 /// The goal of the split point is for its key and value to end up in a parent node;
817 /// the keys, values and edges to the left of the split point become the left child;
818 /// the keys, values and edges to the right of the split point become the right child.
819 fn splitpoint(edge_idx: usize) -> (usize, LeftOrRight<usize>) {
820 debug_assert!(edge_idx <= CAPACITY);
821 // Rust issue #74834 tries to explain these symmetric rules.
823 0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, LeftOrRight::Left(edge_idx)),
824 EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, LeftOrRight::Left(edge_idx)),
825 EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, LeftOrRight::Right(0)),
826 _ => (KV_IDX_CENTER + 1, LeftOrRight::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))),
830 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
831 /// Inserts a new key-value pair between the key-value pairs to the right and left of
832 /// this edge. This method assumes that there is enough space in the node for the new
835 /// The returned pointer points to the inserted value.
836 fn insert_fit(&mut self, key: K, val: V) -> *mut V {
837 debug_assert!(self.node.len() < CAPACITY);
838 let new_len = self.node.len() + 1;
841 slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
842 slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
843 *self.node.len_mut() = new_len as u16;
845 self.node.val_area_mut(self.idx).assume_init_mut()
850 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
851 /// Inserts a new key-value pair between the key-value pairs to the right and left of
852 /// this edge. This method splits the node if there isn't enough room.
854 /// The returned pointer points to the inserted value.
855 fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
856 if self.node.len() < CAPACITY {
857 let val_ptr = self.insert_fit(key, val);
858 let kv = unsafe { Handle::new_kv(self.node, self.idx) };
859 (InsertResult::Fit(kv), val_ptr)
861 let (middle_kv_idx, insertion) = splitpoint(self.idx);
862 let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
863 let mut result = middle.split();
864 let mut insertion_edge = match insertion {
865 LeftOrRight::Left(insert_idx) => unsafe {
866 Handle::new_edge(result.left.reborrow_mut(), insert_idx)
868 LeftOrRight::Right(insert_idx) => unsafe {
869 Handle::new_edge(result.right.borrow_mut(), insert_idx)
872 let val_ptr = insertion_edge.insert_fit(key, val);
873 (InsertResult::Split(result), val_ptr)
878 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
879 /// Fixes the parent pointer and index in the child node that this edge
880 /// links to. This is useful when the ordering of edges has been changed,
881 fn correct_parent_link(self) {
882 // Create backpointer without invalidating other references to the node.
883 let ptr = unsafe { NonNull::new_unchecked(NodeRef::as_internal_ptr(&self.node)) };
885 let mut child = self.descend();
886 child.set_parent_link(ptr, idx);
890 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
891 /// Inserts a new key-value pair and an edge that will go to the right of that new pair
892 /// between this edge and the key-value pair to the right of this edge. This method assumes
893 /// that there is enough space in the node for the new pair to fit.
894 fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
895 debug_assert!(self.node.len() < CAPACITY);
896 debug_assert!(edge.height == self.node.height - 1);
897 let new_len = self.node.len() + 1;
900 slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
901 slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
902 slice_insert(self.node.edge_area_mut(..new_len + 1), self.idx + 1, edge.node);
903 *self.node.len_mut() = new_len as u16;
905 self.node.correct_childrens_parent_links(self.idx + 1..new_len + 1);
909 /// Inserts a new key-value pair and an edge that will go to the right of that new pair
910 /// between this edge and the key-value pair to the right of this edge. This method splits
911 /// the node if there isn't enough room.
917 ) -> InsertResult<'a, K, V, marker::Internal> {
918 assert!(edge.height == self.node.height - 1);
920 if self.node.len() < CAPACITY {
921 self.insert_fit(key, val, edge);
922 let kv = unsafe { Handle::new_kv(self.node, self.idx) };
923 InsertResult::Fit(kv)
925 let (middle_kv_idx, insertion) = splitpoint(self.idx);
926 let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
927 let mut result = middle.split();
928 let mut insertion_edge = match insertion {
929 LeftOrRight::Left(insert_idx) => unsafe {
930 Handle::new_edge(result.left.reborrow_mut(), insert_idx)
932 LeftOrRight::Right(insert_idx) => unsafe {
933 Handle::new_edge(result.right.borrow_mut(), insert_idx)
936 insertion_edge.insert_fit(key, val, edge);
937 InsertResult::Split(result)
942 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
943 /// Inserts a new key-value pair between the key-value pairs to the right and left of
944 /// this edge. This method splits the node if there isn't enough room, and tries to
945 /// insert the split off portion into the parent node recursively, until the root is reached.
947 /// If the returned result is a `Fit`, its handle's node can be this edge's node or an ancestor.
948 /// If the returned result is a `Split`, the `left` field will be the root node.
949 /// The returned pointer points to the inserted value.
950 pub fn insert_recursing(
954 ) -> (InsertResult<'a, K, V, marker::LeafOrInternal>, *mut V) {
955 let (mut split, val_ptr) = match self.insert(key, value) {
956 (InsertResult::Fit(handle), ptr) => {
957 return (InsertResult::Fit(handle.forget_node_type()), ptr);
959 (InsertResult::Split(split), val_ptr) => (split.forget_node_type(), val_ptr),
963 split = match split.left.ascend() {
964 Ok(parent) => match parent.insert(split.kv.0, split.kv.1, split.right) {
965 InsertResult::Fit(handle) => {
966 return (InsertResult::Fit(handle.forget_node_type()), val_ptr);
968 InsertResult::Split(split) => split.forget_node_type(),
971 return (InsertResult::Split(SplitResult { left: root, ..split }), val_ptr);
978 impl<BorrowType: marker::BorrowType, K, V>
979 Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>
981 /// Finds the node pointed to by this edge.
983 /// The method name assumes you picture trees with the root node on top.
985 /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
986 /// both, upon success, do nothing.
987 pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
988 assert!(BorrowType::PERMITS_TRAVERSAL);
989 // We need to use raw pointers to nodes because, if BorrowType is
990 // marker::ValMut, there might be outstanding mutable references to
991 // values that we must not invalidate. There's no worry accessing the
992 // height field because that value is copied. Beware that, once the
993 // node pointer is dereferenced, we access the edges array with a
994 // reference (Rust issue #73987) and invalidate any other references
995 // to or inside the array, should any be around.
996 let parent_ptr = NodeRef::as_internal_ptr(&self.node);
997 let node = unsafe { (*parent_ptr).edges.get_unchecked(self.idx).assume_init_read() };
998 NodeRef { node, height: self.node.height - 1, _marker: PhantomData }
1002 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
1003 pub fn into_kv(self) -> (&'a K, &'a V) {
1004 debug_assert!(self.idx < self.node.len());
1005 let leaf = self.node.into_leaf();
1006 let k = unsafe { leaf.keys.get_unchecked(self.idx).assume_init_ref() };
1007 let v = unsafe { leaf.vals.get_unchecked(self.idx).assume_init_ref() };
1012 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1013 pub fn key_mut(&mut self) -> &mut K {
1014 unsafe { self.node.key_area_mut(self.idx).assume_init_mut() }
1017 pub fn into_val_mut(self) -> &'a mut V {
1018 debug_assert!(self.idx < self.node.len());
1019 let leaf = self.node.into_leaf_mut();
1020 unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }
1024 impl<'a, K, V, NodeType> Handle<NodeRef<marker::ValMut<'a>, K, V, NodeType>, marker::KV> {
1025 pub fn into_kv_valmut(self) -> (&'a K, &'a mut V) {
1026 unsafe { self.node.into_key_val_mut_at(self.idx) }
1030 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1031 pub fn kv_mut(&mut self) -> (&mut K, &mut V) {
1032 debug_assert!(self.idx < self.node.len());
1033 // We cannot call separate key and value methods, because calling the second one
1034 // invalidates the reference returned by the first.
1036 let leaf = self.node.as_leaf_mut();
1037 let key = leaf.keys.get_unchecked_mut(self.idx).assume_init_mut();
1038 let val = leaf.vals.get_unchecked_mut(self.idx).assume_init_mut();
1043 /// Replace the key and value that the KV handle refers to.
1044 pub fn replace_kv(&mut self, k: K, v: V) -> (K, V) {
1045 let (key, val) = self.kv_mut();
1046 (mem::replace(key, k), mem::replace(val, v))
1050 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1051 /// Helps implementations of `split` for a particular `NodeType`,
1052 /// by taking care of leaf data.
1053 fn split_leaf_data(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V) {
1054 debug_assert!(self.idx < self.node.len());
1055 let old_len = self.node.len();
1056 let new_len = old_len - self.idx - 1;
1057 new_node.len = new_len as u16;
1059 let k = self.node.key_area_mut(self.idx).assume_init_read();
1060 let v = self.node.val_area_mut(self.idx).assume_init_read();
1063 self.node.key_area_mut(self.idx + 1..old_len),
1064 &mut new_node.keys[..new_len],
1067 self.node.val_area_mut(self.idx + 1..old_len),
1068 &mut new_node.vals[..new_len],
1071 *self.node.len_mut() = self.idx as u16;
1077 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
1078 /// Splits the underlying node into three parts:
1080 /// - The node is truncated to only contain the key-value pairs to the left of
1082 /// - The key and value pointed to by this handle are extracted.
1083 /// - All the key-value pairs to the right of this handle are put into a newly
1085 pub fn split(mut self) -> SplitResult<'a, K, V, marker::Leaf> {
1086 let mut new_node = LeafNode::new();
1088 let kv = self.split_leaf_data(&mut new_node);
1090 let right = NodeRef::from_new_leaf(new_node);
1091 SplitResult { left: self.node, kv, right }
1094 /// Removes the key-value pair pointed to by this handle and returns it, along with the edge
1095 /// that the key-value pair collapsed into.
1098 ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
1099 let old_len = self.node.len();
1101 let k = slice_remove(self.node.key_area_mut(..old_len), self.idx);
1102 let v = slice_remove(self.node.val_area_mut(..old_len), self.idx);
1103 *self.node.len_mut() = (old_len - 1) as u16;
1104 ((k, v), self.left_edge())
1109 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1110 /// Splits the underlying node into three parts:
1112 /// - The node is truncated to only contain the edges and key-value pairs to the
1113 /// left of this handle.
1114 /// - The key and value pointed to by this handle are extracted.
1115 /// - All the edges and key-value pairs to the right of this handle are put into
1116 /// a newly allocated node.
1117 pub fn split(mut self) -> SplitResult<'a, K, V, marker::Internal> {
1118 let old_len = self.node.len();
1120 let mut new_node = InternalNode::new();
1121 let kv = self.split_leaf_data(&mut new_node.data);
1122 let new_len = usize::from(new_node.data.len);
1124 self.node.edge_area_mut(self.idx + 1..old_len + 1),
1125 &mut new_node.edges[..new_len + 1],
1128 let height = self.node.height;
1129 let right = NodeRef::from_new_internal(new_node, height);
1131 SplitResult { left: self.node, kv, right }
1136 /// Represents a session for evaluating and performing a balancing operation
1137 /// around an internal key-value pair.
1138 pub struct BalancingContext<'a, K, V> {
1139 parent: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV>,
1140 left_child: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1141 right_child: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1144 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1145 pub fn consider_for_balancing(self) -> BalancingContext<'a, K, V> {
1146 let self1 = unsafe { ptr::read(&self) };
1147 let self2 = unsafe { ptr::read(&self) };
1150 left_child: self1.left_edge().descend(),
1151 right_child: self2.right_edge().descend(),
1156 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1157 /// Chooses a balancing context involving the node as a child, thus between
1158 /// the KV immediately to the left or to the right in the parent node.
1159 /// Returns an `Err` if there is no parent.
1160 /// Panics if the parent is empty.
1162 /// Prefers the left side, to be optimal if the given node is somehow
1163 /// underfull, meaning here only that it has fewer elements than its left
1164 /// sibling and than its right sibling, if they exist. In that case,
1165 /// merging with the left sibling is faster, since we only need to move
1166 /// the node's N elements, instead of shifting them to the right and moving
1167 /// more than N elements in front. Stealing from the left sibling is also
1168 /// typically faster, since we only need to shift the node's N elements to
1169 /// the right, instead of shifting at least N of the sibling's elements to
1171 pub fn choose_parent_kv(self) -> Result<LeftOrRight<BalancingContext<'a, K, V>>, Self> {
1172 match unsafe { ptr::read(&self) }.ascend() {
1173 Ok(parent_edge) => match parent_edge.left_kv() {
1174 Ok(left_parent_kv) => Ok(LeftOrRight::Left(BalancingContext {
1175 parent: unsafe { ptr::read(&left_parent_kv) },
1176 left_child: left_parent_kv.left_edge().descend(),
1179 Err(parent_edge) => match parent_edge.right_kv() {
1180 Ok(right_parent_kv) => Ok(LeftOrRight::Right(BalancingContext {
1181 parent: unsafe { ptr::read(&right_parent_kv) },
1183 right_child: right_parent_kv.right_edge().descend(),
1185 Err(_) => unreachable!("empty internal node"),
1188 Err(root) => Err(root),
1193 impl<'a, K, V> BalancingContext<'a, K, V> {
1194 pub fn left_child_len(&self) -> usize {
1195 self.left_child.len()
1198 pub fn right_child_len(&self) -> usize {
1199 self.right_child.len()
1202 pub fn into_left_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1206 pub fn into_right_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1210 /// Returns whether merging is possible, i.e., whether there is enough room
1211 /// in a node to combine the central KV with both adjacent child nodes.
1212 pub fn can_merge(&self) -> bool {
1213 self.left_child.len() + 1 + self.right_child.len() <= CAPACITY
1217 impl<'a, K: 'a, V: 'a> BalancingContext<'a, K, V> {
1218 /// Performs a merge and lets a closure decide what to return.
1221 NodeRef<marker::Mut<'a>, K, V, marker::Internal>,
1222 NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1229 let Handle { node: mut parent_node, idx: parent_idx, _marker } = self.parent;
1230 let old_parent_len = parent_node.len();
1231 let mut left_node = self.left_child;
1232 let old_left_len = left_node.len();
1233 let mut right_node = self.right_child;
1234 let right_len = right_node.len();
1235 let new_left_len = old_left_len + 1 + right_len;
1237 assert!(new_left_len <= CAPACITY);
1240 *left_node.len_mut() = new_left_len as u16;
1242 let parent_key = slice_remove(parent_node.key_area_mut(..old_parent_len), parent_idx);
1243 left_node.key_area_mut(old_left_len).write(parent_key);
1245 right_node.key_area_mut(..right_len),
1246 left_node.key_area_mut(old_left_len + 1..new_left_len),
1249 let parent_val = slice_remove(parent_node.val_area_mut(..old_parent_len), parent_idx);
1250 left_node.val_area_mut(old_left_len).write(parent_val);
1252 right_node.val_area_mut(..right_len),
1253 left_node.val_area_mut(old_left_len + 1..new_left_len),
1256 slice_remove(&mut parent_node.edge_area_mut(..old_parent_len + 1), parent_idx + 1);
1257 parent_node.correct_childrens_parent_links(parent_idx + 1..old_parent_len);
1258 *parent_node.len_mut() -= 1;
1260 if parent_node.height > 1 {
1261 // SAFETY: the height of the nodes being merged is one below the height
1262 // of the node of this edge, thus above zero, so they are internal.
1263 let mut left_node = left_node.reborrow_mut().cast_to_internal_unchecked();
1264 let mut right_node = right_node.cast_to_internal_unchecked();
1266 right_node.edge_area_mut(..right_len + 1),
1267 left_node.edge_area_mut(old_left_len + 1..new_left_len + 1),
1270 left_node.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);
1272 Global.deallocate(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
1274 Global.deallocate(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
1277 result(parent_node, left_node)
1280 /// Merges the parent's key-value pair and both adjacent child nodes into
1281 /// the left child node and returns the shrunk parent node.
1283 /// Panics unless we `.can_merge()`.
1284 pub fn merge_tracking_parent(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
1285 self.do_merge(|parent, _child| parent)
1288 /// Merges the parent's key-value pair and both adjacent child nodes into
1289 /// the left child node and returns that child node.
1291 /// Panics unless we `.can_merge()`.
1292 pub fn merge_tracking_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1293 self.do_merge(|_parent, child| child)
1296 /// Merges the parent's key-value pair and both adjacent child nodes into
1297 /// the left child node and returns the edge handle in that child node
1298 /// where the tracked child edge ended up,
1300 /// Panics unless we `.can_merge()`.
1301 pub fn merge_tracking_child_edge(
1303 track_edge_idx: LeftOrRight<usize>,
1304 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1305 let old_left_len = self.left_child.len();
1306 let right_len = self.right_child.len();
1307 assert!(match track_edge_idx {
1308 LeftOrRight::Left(idx) => idx <= old_left_len,
1309 LeftOrRight::Right(idx) => idx <= right_len,
1311 let child = self.merge_tracking_child();
1312 let new_idx = match track_edge_idx {
1313 LeftOrRight::Left(idx) => idx,
1314 LeftOrRight::Right(idx) => old_left_len + 1 + idx,
1316 unsafe { Handle::new_edge(child, new_idx) }
1319 /// Removes a key-value pair from the left child and places it in the key-value storage
1320 /// of the parent, while pushing the old parent key-value pair into the right child.
1321 /// Returns a handle to the edge in the right child corresponding to where the original
1322 /// edge specified by `track_right_edge_idx` ended up.
1325 track_right_edge_idx: usize,
1326 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1327 self.bulk_steal_left(1);
1328 unsafe { Handle::new_edge(self.right_child, 1 + track_right_edge_idx) }
1331 /// Removes a key-value pair from the right child and places it in the key-value storage
1332 /// of the parent, while pushing the old parent key-value pair onto the left child.
1333 /// Returns a handle to the edge in the left child specified by `track_left_edge_idx`,
1334 /// which didn't move.
1337 track_left_edge_idx: usize,
1338 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1339 self.bulk_steal_right(1);
1340 unsafe { Handle::new_edge(self.left_child, track_left_edge_idx) }
1343 /// This does stealing similar to `steal_left` but steals multiple elements at once.
1344 pub fn bulk_steal_left(&mut self, count: usize) {
1347 let left_node = &mut self.left_child;
1348 let old_left_len = left_node.len();
1349 let right_node = &mut self.right_child;
1350 let old_right_len = right_node.len();
1352 // Make sure that we may steal safely.
1353 assert!(old_right_len + count <= CAPACITY);
1354 assert!(old_left_len >= count);
1356 let new_left_len = old_left_len - count;
1357 let new_right_len = old_right_len + count;
1358 *left_node.len_mut() = new_left_len as u16;
1359 *right_node.len_mut() = new_right_len as u16;
1363 // Make room for stolen elements in the right child.
1364 slice_shr(right_node.key_area_mut(..new_right_len), count);
1365 slice_shr(right_node.val_area_mut(..new_right_len), count);
1367 // Move elements from the left child to the right one.
1369 left_node.key_area_mut(new_left_len + 1..old_left_len),
1370 right_node.key_area_mut(..count - 1),
1373 left_node.val_area_mut(new_left_len + 1..old_left_len),
1374 right_node.val_area_mut(..count - 1),
1377 // Move the left-most stolen pair to the parent.
1378 let k = left_node.key_area_mut(new_left_len).assume_init_read();
1379 let v = left_node.val_area_mut(new_left_len).assume_init_read();
1380 let (k, v) = self.parent.replace_kv(k, v);
1382 // Move parent's key-value pair to the right child.
1383 right_node.key_area_mut(count - 1).write(k);
1384 right_node.val_area_mut(count - 1).write(v);
1387 match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
1388 (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1389 // Make room for stolen edges.
1390 slice_shr(right.edge_area_mut(..new_right_len + 1), count);
1394 left.edge_area_mut(new_left_len + 1..old_left_len + 1),
1395 right.edge_area_mut(..count),
1398 right.correct_childrens_parent_links(0..new_right_len + 1);
1400 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1401 _ => unreachable!(),
1406 /// The symmetric clone of `bulk_steal_left`.
1407 pub fn bulk_steal_right(&mut self, count: usize) {
1410 let left_node = &mut self.left_child;
1411 let old_left_len = left_node.len();
1412 let right_node = &mut self.right_child;
1413 let old_right_len = right_node.len();
1415 // Make sure that we may steal safely.
1416 assert!(old_left_len + count <= CAPACITY);
1417 assert!(old_right_len >= count);
1419 let new_left_len = old_left_len + count;
1420 let new_right_len = old_right_len - count;
1421 *left_node.len_mut() = new_left_len as u16;
1422 *right_node.len_mut() = new_right_len as u16;
1426 // Move the right-most stolen pair to the parent.
1427 let k = right_node.key_area_mut(count - 1).assume_init_read();
1428 let v = right_node.val_area_mut(count - 1).assume_init_read();
1429 let (k, v) = self.parent.replace_kv(k, v);
1431 // Move parent's key-value pair to the left child.
1432 left_node.key_area_mut(old_left_len).write(k);
1433 left_node.val_area_mut(old_left_len).write(v);
1435 // Move elements from the right child to the left one.
1437 right_node.key_area_mut(..count - 1),
1438 left_node.key_area_mut(old_left_len + 1..new_left_len),
1441 right_node.val_area_mut(..count - 1),
1442 left_node.val_area_mut(old_left_len + 1..new_left_len),
1445 // Fill gap where stolen elements used to be.
1446 slice_shl(right_node.key_area_mut(..old_right_len), count);
1447 slice_shl(right_node.val_area_mut(..old_right_len), count);
1450 match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
1451 (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1454 right.edge_area_mut(..count),
1455 left.edge_area_mut(old_left_len + 1..new_left_len + 1),
1458 // Fill gap where stolen edges used to be.
1459 slice_shl(right.edge_area_mut(..old_right_len + 1), count);
1461 left.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);
1462 right.correct_childrens_parent_links(0..new_right_len + 1);
1464 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1465 _ => unreachable!(),
1471 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1472 pub fn forget_node_type(
1474 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1475 unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1479 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
1480 pub fn forget_node_type(
1482 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1483 unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1487 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> {
1488 pub fn forget_node_type(
1490 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
1491 unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
1495 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV> {
1496 pub fn forget_node_type(
1498 ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
1499 unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
1503 impl<BorrowType, K, V, Type> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, Type> {
1504 /// Checks whether the underlying node is an `Internal` node or a `Leaf` node.
1508 Handle<NodeRef<BorrowType, K, V, marker::Leaf>, Type>,
1509 Handle<NodeRef<BorrowType, K, V, marker::Internal>, Type>,
1511 match self.node.force() {
1512 ForceResult::Leaf(node) => {
1513 ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData })
1515 ForceResult::Internal(node) => {
1516 ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData })
1522 impl<'a, K, V, Type> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, Type> {
1523 /// Unsafely asserts to the compiler the static information that the handle's node is a `Leaf`.
1524 pub unsafe fn cast_to_leaf_unchecked(
1526 ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, Type> {
1527 let node = unsafe { self.node.cast_to_leaf_unchecked() };
1528 Handle { node, idx: self.idx, _marker: PhantomData }
1532 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1533 /// Move the suffix after `self` from one node to another one. `right` must be empty.
1534 /// The first edge of `right` remains unchanged.
1537 right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1540 let new_left_len = self.idx;
1541 let mut left_node = self.reborrow_mut().into_node();
1542 let old_left_len = left_node.len();
1544 let new_right_len = old_left_len - new_left_len;
1545 let mut right_node = right.reborrow_mut();
1547 assert!(right_node.len() == 0);
1548 assert!(left_node.height == right_node.height);
1550 if new_right_len > 0 {
1551 *left_node.len_mut() = new_left_len as u16;
1552 *right_node.len_mut() = new_right_len as u16;
1555 left_node.key_area_mut(new_left_len..old_left_len),
1556 right_node.key_area_mut(..new_right_len),
1559 left_node.val_area_mut(new_left_len..old_left_len),
1560 right_node.val_area_mut(..new_right_len),
1562 match (left_node.force(), right_node.force()) {
1563 (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1565 left.edge_area_mut(new_left_len + 1..old_left_len + 1),
1566 right.edge_area_mut(1..new_right_len + 1),
1568 right.correct_childrens_parent_links(1..new_right_len + 1);
1570 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1571 _ => unreachable!(),
1578 pub enum ForceResult<Leaf, Internal> {
1583 /// Result of insertion, when a node needed to expand beyond its capacity.
1584 pub struct SplitResult<'a, K, V, NodeType> {
1585 // Altered node in existing tree with elements and edges that belong to the left of `kv`.
1586 pub left: NodeRef<marker::Mut<'a>, K, V, NodeType>,
1587 // Some key and value split off, to be inserted elsewhere.
1589 // Owned, unattached, new node with elements and edges that belong to the right of `kv`.
1590 pub right: NodeRef<marker::Owned, K, V, NodeType>,
1593 impl<'a, K, V> SplitResult<'a, K, V, marker::Leaf> {
1594 pub fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> {
1595 SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() }
1599 impl<'a, K, V> SplitResult<'a, K, V, marker::Internal> {
1600 pub fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> {
1601 SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() }
1605 pub enum InsertResult<'a, K, V, NodeType> {
1606 Fit(Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV>),
1607 Split(SplitResult<'a, K, V, NodeType>),
1611 use core::marker::PhantomData;
1614 pub enum Internal {}
1615 pub enum LeafOrInternal {}
1619 pub struct Immut<'a>(PhantomData<&'a ()>);
1620 pub struct Mut<'a>(PhantomData<&'a mut ()>);
1621 pub struct ValMut<'a>(PhantomData<&'a mut ()>);
1623 pub trait BorrowType {
1624 // Whether node references of this borrow type allow traversing
1625 // to other nodes in the tree.
1626 const PERMITS_TRAVERSAL: bool = true;
1628 impl BorrowType for Owned {
1629 // Traversal isn't needede, it happens using the result of `borrow_mut`.
1630 // By disabling traversal, and only creating new references to roots,
1631 // we know that every reference of the `Owned` type is to a root node.
1632 const PERMITS_TRAVERSAL: bool = false;
1634 impl BorrowType for Dying {}
1635 impl<'a> BorrowType for Immut<'a> {}
1636 impl<'a> BorrowType for Mut<'a> {}
1637 impl<'a> BorrowType for ValMut<'a> {}
1643 /// Inserts a value into a slice of initialized elements followed by one uninitialized element.
1646 /// The slice has more than `idx` elements.
1647 unsafe fn slice_insert<T>(slice: &mut [MaybeUninit<T>], idx: usize, val: T) {
1649 let len = slice.len();
1650 debug_assert!(len > idx);
1651 let slice_ptr = slice.as_mut_ptr();
1653 ptr::copy(slice_ptr.add(idx), slice_ptr.add(idx + 1), len - idx - 1);
1655 (*slice_ptr.add(idx)).write(val);
1659 /// Removes and returns a value from a slice of all initialized elements, leaving behind one
1660 /// trailing uninitialized element.
1663 /// The slice has more than `idx` elements.
1664 unsafe fn slice_remove<T>(slice: &mut [MaybeUninit<T>], idx: usize) -> T {
1666 let len = slice.len();
1667 debug_assert!(idx < len);
1668 let slice_ptr = slice.as_mut_ptr();
1669 let ret = (*slice_ptr.add(idx)).assume_init_read();
1670 ptr::copy(slice_ptr.add(idx + 1), slice_ptr.add(idx), len - idx - 1);
1675 /// Shifts the elements in a slice `distance` positions to the left.
1678 /// The slice has at least `distance` elements.
1679 unsafe fn slice_shl<T>(slice: &mut [MaybeUninit<T>], distance: usize) {
1681 let slice_ptr = slice.as_mut_ptr();
1682 ptr::copy(slice_ptr.add(distance), slice_ptr, slice.len() - distance);
1686 /// Shifts the elements in a slice `distance` positions to the right.
1689 /// The slice has at least `distance` elements.
1690 unsafe fn slice_shr<T>(slice: &mut [MaybeUninit<T>], distance: usize) {
1692 let slice_ptr = slice.as_mut_ptr();
1693 ptr::copy(slice_ptr, slice_ptr.add(distance), slice.len() - distance);
1697 /// Moves all values from a slice of initialized elements to a slice
1698 /// of uninitialized elements, leaving behind `src` as all uninitialized.
1699 /// Works like `dst.copy_from_slice(src)` but does not require `T` to be `Copy`.
1700 fn move_to_slice<T>(src: &mut [MaybeUninit<T>], dst: &mut [MaybeUninit<T>]) {
1701 assert!(src.len() == dst.len());
1703 ptr::copy_nonoverlapping(src.as_ptr(), dst.as_mut_ptr(), src.len());