alloc/collections/btree/
node.rs

1// This is an attempt at an implementation following the ideal
2//
3// ```
4// struct BTreeMap<K, V> {
5//     height: usize,
6//     root: Option<Box<Node<K, V, height>>>
7// }
8//
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)>,
14//     len: u16,
15// }
16// ```
17//
18// Since Rust doesn't actually have dependent types and polymorphic recursion,
19// we make do with lots of unsafety.
20
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:
25//
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.
33
34use core::marker::PhantomData;
35use core::mem::{self, MaybeUninit};
36use core::ptr::{self, NonNull};
37use core::slice::SliceIndex;
38
39use crate::alloc::{Allocator, Layout};
40use crate::boxed::Box;
41
42const B: usize = 6;
43pub(super) const CAPACITY: usize = 2 * B - 1;
44pub(super) const MIN_LEN_AFTER_SPLIT: usize = B - 1;
45const KV_IDX_CENTER: usize = B - 1;
46const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1;
47const EDGE_IDX_RIGHT_OF_CENTER: usize = B;
48
49/// The underlying representation of leaf nodes and part of the representation of internal nodes.
50struct LeafNode<K, V> {
51    /// We want to be covariant in `K` and `V`.
52    parent: Option<NonNull<InternalNode<K, V>>>,
53
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>,
58
59    /// The number of keys and values this node stores.
60    len: u16,
61
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],
66}
67
68impl<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.
73        unsafe {
74            // parent_idx, keys, and vals are all MaybeUninit
75            (&raw mut (*this).parent).write(None);
76            (&raw mut (*this).len).write(0);
77        }
78    }
79
80    /// Creates a new boxed `LeafNode`.
81    fn new<A: Allocator + Clone>(alloc: A) -> Box<Self, A> {
82        unsafe {
83            let mut leaf = Box::new_uninit_in(alloc);
84            LeafNode::init(leaf.as_mut_ptr());
85            leaf.assume_init()
86        }
87    }
88}
89
90/// 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)`.
95#[repr(C)]
96// gdb_providers.py uses this type name for introspection.
97struct InternalNode<K, V> {
98    data: LeafNode<K, V>,
99
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],
104}
105
106impl<K, V> InternalNode<K, V> {
107    /// Creates a new boxed `InternalNode`.
108    ///
109    /// # Safety
110    /// An invariant of internal nodes is that they have at least one
111    /// initialized and valid edge. This function does not set up
112    /// such an edge.
113    unsafe fn new<A: Allocator + Clone>(alloc: A) -> Box<Self, A> {
114        unsafe {
115            let mut node = Box::<Self, _>::new_uninit_in(alloc);
116            // We only need to initialize the data; the edges are MaybeUninit.
117            LeafNode::init(&raw mut (*node.as_mut_ptr()).data);
118            node.assume_init()
119        }
120    }
121}
122
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>`.
125///
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.
129type BoxedNode<K, V> = NonNull<LeafNode<K, V>>;
130
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
135// correct variance.
136///
137/// A reference to a node.
138///
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`.
160///
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 powerful
171///   `NodeRef` in order to reach a method like `into_kv`.
172///
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.
182pub(super) 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`.
188    height: usize,
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)>,
193}
194
195/// The root node of an owned tree.
196///
197/// Note that this does not have a destructor, and must be cleaned up manually.
198pub(super) type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>;
199
200impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {}
201impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
202    fn clone(&self) -> Self {
203        *self
204    }
205}
206
207unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}
208
209unsafe impl<K: Sync, V: Sync, Type> Send for NodeRef<marker::Immut<'_>, K, V, Type> {}
210unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Mut<'_>, K, V, Type> {}
211unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::ValMut<'_>, K, V, Type> {}
212unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
213unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {}
214
215impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
216    pub(super) fn new_leaf<A: Allocator + Clone>(alloc: A) -> Self {
217        Self::from_new_leaf(LeafNode::new(alloc))
218    }
219
220    fn from_new_leaf<A: Allocator + Clone>(leaf: Box<LeafNode<K, V>, A>) -> Self {
221        NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _marker: PhantomData }
222    }
223}
224
225impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
226    fn new_internal<A: Allocator + Clone>(child: Root<K, V>, alloc: A) -> Self {
227        let mut new_node = unsafe { InternalNode::new(alloc) };
228        new_node.edges[0].write(child.node);
229        unsafe { NodeRef::from_new_internal(new_node, child.height + 1) }
230    }
231
232    /// # Safety
233    /// `height` must not be zero.
234    unsafe fn from_new_internal<A: Allocator + Clone>(
235        internal: Box<InternalNode<K, V>, A>,
236        height: usize,
237    ) -> Self {
238        debug_assert!(height > 0);
239        let node = NonNull::from(Box::leak(internal)).cast();
240        let mut this = NodeRef { height, node, _marker: PhantomData };
241        this.borrow_mut().correct_all_childrens_parent_links();
242        this
243    }
244}
245
246impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
247    /// Unpack a node reference that was packed as `NodeRef::parent`.
248    fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self {
249        debug_assert!(height > 0);
250        NodeRef { height, node: node.cast(), _marker: PhantomData }
251    }
252}
253
254impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
255    /// Exposes the data of an internal node.
256    ///
257    /// Returns a raw ptr to avoid invalidating other references to this node.
258    fn as_internal_ptr(this: &Self) -> *mut InternalNode<K, V> {
259        // SAFETY: the static node type is `Internal`.
260        this.node.as_ptr() as *mut InternalNode<K, V>
261    }
262}
263
264impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
265    /// Borrows exclusive access to the data of an internal node.
266    fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
267        let ptr = Self::as_internal_ptr(self);
268        unsafe { &mut *ptr }
269    }
270}
271
272impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
273    /// Finds the length of the node. This is the number of keys or values.
274    /// The number of edges is `len() + 1`.
275    /// Note that, despite being safe, calling this function can have the side effect
276    /// of invalidating mutable references that unsafe code has created.
277    pub(super) fn len(&self) -> usize {
278        // Crucially, we only access the `len` field here. If BorrowType is marker::ValMut,
279        // there might be outstanding mutable references to values that we must not invalidate.
280        unsafe { usize::from((*Self::as_leaf_ptr(self)).len) }
281    }
282
283    /// Returns the number of levels that the node and leaves are apart. Zero
284    /// height means the node is a leaf itself. If you picture trees with the
285    /// root on top, the number says at which elevation the node appears.
286    /// If you picture trees with leaves on top, the number says how high
287    /// the tree extends above the node.
288    pub(super) fn height(&self) -> usize {
289        self.height
290    }
291
292    /// Temporarily takes out another, immutable reference to the same node.
293    pub(super) fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
294        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
295    }
296
297    /// Exposes the leaf portion of any leaf or internal node.
298    ///
299    /// Returns a raw ptr to avoid invalidating other references to this node.
300    fn as_leaf_ptr(this: &Self) -> *mut LeafNode<K, V> {
301        // The node must be valid for at least the LeafNode portion.
302        // This is not a reference in the NodeRef type because we don't know if
303        // it should be unique or shared.
304        this.node.as_ptr()
305    }
306}
307
308impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
309    /// Finds the parent of the current node. Returns `Ok(handle)` if the current
310    /// node actually has a parent, where `handle` points to the edge of the parent
311    /// that points to the current node. Returns `Err(self)` if the current node has
312    /// no parent, giving back the original `NodeRef`.
313    ///
314    /// The method name assumes you picture trees with the root node on top.
315    ///
316    /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
317    /// both, upon success, do nothing.
318    pub(super) fn ascend(
319        self,
320    ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
321        const {
322            assert!(BorrowType::TRAVERSAL_PERMIT);
323        }
324
325        // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut,
326        // there might be outstanding mutable references to values that we must not invalidate.
327        let leaf_ptr: *const _ = Self::as_leaf_ptr(&self);
328        unsafe { (*leaf_ptr).parent }
329            .as_ref()
330            .map(|parent| Handle {
331                node: NodeRef::from_internal(*parent, self.height + 1),
332                idx: unsafe { usize::from((*leaf_ptr).parent_idx.assume_init()) },
333                _marker: PhantomData,
334            })
335            .ok_or(self)
336    }
337
338    pub(super) fn first_edge(self) -> Handle<Self, marker::Edge> {
339        unsafe { Handle::new_edge(self, 0) }
340    }
341
342    pub(super) fn last_edge(self) -> Handle<Self, marker::Edge> {
343        let len = self.len();
344        unsafe { Handle::new_edge(self, len) }
345    }
346
347    /// Note that `self` must be nonempty.
348    pub(super) fn first_kv(self) -> Handle<Self, marker::KV> {
349        let len = self.len();
350        assert!(len > 0);
351        unsafe { Handle::new_kv(self, 0) }
352    }
353
354    /// Note that `self` must be nonempty.
355    pub(super) fn last_kv(self) -> Handle<Self, marker::KV> {
356        let len = self.len();
357        assert!(len > 0);
358        unsafe { Handle::new_kv(self, len - 1) }
359    }
360}
361
362impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
363    /// Could be a public implementation of PartialEq, but only used in this module.
364    fn eq(&self, other: &Self) -> bool {
365        let Self { node, height, _marker } = self;
366        if node.eq(&other.node) {
367            debug_assert_eq!(*height, other.height);
368            true
369        } else {
370            false
371        }
372    }
373}
374
375impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
376    /// Exposes the leaf portion of any leaf or internal node in an immutable tree.
377    fn into_leaf(self) -> &'a LeafNode<K, V> {
378        let ptr = Self::as_leaf_ptr(&self);
379        // SAFETY: there can be no mutable references into this tree borrowed as `Immut`.
380        unsafe { &*ptr }
381    }
382
383    /// Borrows a view into the keys stored in the node.
384    pub(super) fn keys(&self) -> &[K] {
385        let leaf = self.into_leaf();
386        unsafe { leaf.keys.get_unchecked(..usize::from(leaf.len)).assume_init_ref() }
387    }
388}
389
390impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> {
391    /// Similar to `ascend`, gets a reference to a node's parent node, but also
392    /// deallocates the current node in the process. This is unsafe because the
393    /// current node will still be accessible despite being deallocated.
394    pub(super) unsafe fn deallocate_and_ascend<A: Allocator + Clone>(
395        self,
396        alloc: A,
397    ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Internal>, marker::Edge>> {
398        let height = self.height;
399        let node = self.node;
400        let ret = self.ascend().ok();
401        unsafe {
402            alloc.deallocate(
403                node.cast(),
404                if height > 0 {
405                    Layout::new::<InternalNode<K, V>>()
406                } else {
407                    Layout::new::<LeafNode<K, V>>()
408                },
409            );
410        }
411        ret
412    }
413}
414
415impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
416    /// Temporarily takes out another mutable reference to the same node. Beware, as
417    /// this method is very dangerous, doubly so since it might not immediately appear
418    /// dangerous.
419    ///
420    /// Because mutable pointers can roam anywhere around the tree, the returned
421    /// pointer can easily be used to make the original pointer dangling, out of
422    /// bounds, or invalid under stacked borrow rules.
423    // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef`
424    // that restricts the use of navigation methods on reborrowed pointers,
425    // preventing this unsafety.
426    unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
427        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
428    }
429
430    /// Borrows exclusive access to the leaf portion of a leaf or internal node.
431    fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
432        let ptr = Self::as_leaf_ptr(self);
433        // SAFETY: we have exclusive access to the entire node.
434        unsafe { &mut *ptr }
435    }
436
437    /// Offers exclusive access to the leaf portion of a leaf or internal node.
438    fn into_leaf_mut(mut self) -> &'a mut LeafNode<K, V> {
439        let ptr = Self::as_leaf_ptr(&mut self);
440        // SAFETY: we have exclusive access to the entire node.
441        unsafe { &mut *ptr }
442    }
443
444    /// Returns a dormant copy of this node with its lifetime erased which can
445    /// be reawakened later.
446    pub(super) fn dormant(&self) -> NodeRef<marker::DormantMut, K, V, Type> {
447        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
448    }
449}
450
451impl<K, V, Type> NodeRef<marker::DormantMut, K, V, Type> {
452    /// Revert to the unique borrow initially captured.
453    ///
454    /// # Safety
455    ///
456    /// The reborrow must have ended, i.e., the reference returned by `new` and
457    /// all pointers and references derived from it, must not be used anymore.
458    pub(super) unsafe fn awaken<'a>(self) -> NodeRef<marker::Mut<'a>, K, V, Type> {
459        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
460    }
461}
462
463impl<K, V, Type> NodeRef<marker::Dying, K, V, Type> {
464    /// Borrows exclusive access to the leaf portion of a dying leaf or internal node.
465    fn as_leaf_dying(&mut self) -> &mut LeafNode<K, V> {
466        let ptr = Self::as_leaf_ptr(self);
467        // SAFETY: we have exclusive access to the entire node.
468        unsafe { &mut *ptr }
469    }
470}
471
472impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
473    /// Borrows exclusive access to an element of the key storage area.
474    ///
475    /// # Safety
476    /// `index` is in bounds of 0..CAPACITY
477    unsafe fn key_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
478    where
479        I: SliceIndex<[MaybeUninit<K>], Output = Output>,
480    {
481        // SAFETY: the caller will not be able to call further methods on self
482        // until the key slice reference is dropped, as we have unique access
483        // for the lifetime of the borrow.
484        unsafe { self.as_leaf_mut().keys.as_mut_slice().get_unchecked_mut(index) }
485    }
486
487    /// Borrows exclusive access to an element or slice of the node's value storage area.
488    ///
489    /// # Safety
490    /// `index` is in bounds of 0..CAPACITY
491    unsafe fn val_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
492    where
493        I: SliceIndex<[MaybeUninit<V>], Output = Output>,
494    {
495        // SAFETY: the caller will not be able to call further methods on self
496        // until the value slice reference is dropped, as we have unique access
497        // for the lifetime of the borrow.
498        unsafe { self.as_leaf_mut().vals.as_mut_slice().get_unchecked_mut(index) }
499    }
500}
501
502impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
503    /// Borrows exclusive access to an element or slice of the node's storage area for edge contents.
504    ///
505    /// # Safety
506    /// `index` is in bounds of 0..CAPACITY + 1
507    unsafe fn edge_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Output
508    where
509        I: SliceIndex<[MaybeUninit<BoxedNode<K, V>>], Output = Output>,
510    {
511        // SAFETY: the caller will not be able to call further methods on self
512        // until the edge slice reference is dropped, as we have unique access
513        // for the lifetime of the borrow.
514        unsafe { self.as_internal_mut().edges.as_mut_slice().get_unchecked_mut(index) }
515    }
516}
517
518impl<'a, K, V, Type> NodeRef<marker::ValMut<'a>, K, V, Type> {
519    /// # Safety
520    /// - The node has more than `idx` initialized elements.
521    unsafe fn into_key_val_mut_at(mut self, idx: usize) -> (&'a K, &'a mut V) {
522        // We only create a reference to the one element we are interested in,
523        // to avoid aliasing with outstanding references to other elements,
524        // in particular, those returned to the caller in earlier iterations.
525        let leaf = Self::as_leaf_ptr(&mut self);
526        let keys = unsafe { &raw const (*leaf).keys };
527        let vals = unsafe { &raw mut (*leaf).vals };
528        // We must coerce to unsized array pointers because of Rust issue #74679.
529        let keys: *const [_] = keys;
530        let vals: *mut [_] = vals;
531        let key = unsafe { (&*keys.get_unchecked(idx)).assume_init_ref() };
532        let val = unsafe { (&mut *vals.get_unchecked_mut(idx)).assume_init_mut() };
533        (key, val)
534    }
535}
536
537impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
538    /// Borrows exclusive access to the length of the node.
539    pub(super) fn len_mut(&mut self) -> &mut u16 {
540        &mut self.as_leaf_mut().len
541    }
542}
543
544impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
545    /// # Safety
546    /// Every item returned by `range` is a valid edge index for the node.
547    unsafe fn correct_childrens_parent_links<R: Iterator<Item = usize>>(&mut self, range: R) {
548        for i in range {
549            debug_assert!(i <= self.len());
550            unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link();
551        }
552    }
553
554    fn correct_all_childrens_parent_links(&mut self) {
555        let len = self.len();
556        unsafe { self.correct_childrens_parent_links(0..=len) };
557    }
558}
559
560impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
561    /// Sets the node's link to its parent edge,
562    /// without invalidating other references to the node.
563    fn set_parent_link(&mut self, parent: NonNull<InternalNode<K, V>>, parent_idx: usize) {
564        let leaf = Self::as_leaf_ptr(self);
565        unsafe { (*leaf).parent = Some(parent) };
566        unsafe { (*leaf).parent_idx.write(parent_idx as u16) };
567    }
568}
569
570impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
571    /// Clears the root's link to its parent edge.
572    fn clear_parent_link(&mut self) {
573        let mut root_node = self.borrow_mut();
574        let leaf = root_node.as_leaf_mut();
575        leaf.parent = None;
576    }
577}
578
579impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
580    /// Returns a new owned tree, with its own root node that is initially empty.
581    pub(super) fn new<A: Allocator + Clone>(alloc: A) -> Self {
582        NodeRef::new_leaf(alloc).forget_type()
583    }
584
585    /// Adds a new internal node with a single edge pointing to the previous root node,
586    /// make that new node the root node, and return it. This increases the height by 1
587    /// and is the opposite of `pop_internal_level`.
588    pub(super) fn push_internal_level<A: Allocator + Clone>(
589        &mut self,
590        alloc: A,
591    ) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
592        super::mem::take_mut(self, |old_root| NodeRef::new_internal(old_root, alloc).forget_type());
593
594        // `self.borrow_mut()`, except that we just forgot we're internal now:
595        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
596    }
597
598    /// Removes the internal root node, using its first child as the new root node.
599    /// As it is intended only to be called when the root node has only one child,
600    /// no cleanup is done on any of the keys, values and other children.
601    /// This decreases the height by 1 and is the opposite of `push_internal_level`.
602    ///
603    /// Does not invalidate any handles or references pointing into the subtree
604    /// rooted at the first child of `self`.
605    ///
606    /// Panics if there is no internal level, i.e., if the root node is a leaf.
607    pub(super) fn pop_internal_level<A: Allocator + Clone>(&mut self, alloc: A) {
608        assert!(self.height > 0);
609
610        let top = self.node;
611
612        // SAFETY: we asserted to be internal.
613        let internal_self = unsafe { self.borrow_mut().cast_to_internal_unchecked() };
614        // SAFETY: we borrowed `self` exclusively and its borrow type is exclusive.
615        let internal_node = unsafe { &mut *NodeRef::as_internal_ptr(&internal_self) };
616        // SAFETY: the first edge is always initialized.
617        self.node = unsafe { internal_node.edges[0].assume_init_read() };
618        self.height -= 1;
619        self.clear_parent_link();
620
621        unsafe {
622            alloc.deallocate(top.cast(), Layout::new::<InternalNode<K, V>>());
623        }
624    }
625}
626
627impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> {
628    /// Mutably borrows the owned root node. Unlike `reborrow_mut`, this is safe
629    /// because the return value cannot be used to destroy the root, and there
630    /// cannot be other references to the tree.
631    pub(super) fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
632        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
633    }
634
635    /// Slightly mutably borrows the owned root node.
636    pub(super) fn borrow_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, Type> {
637        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
638    }
639
640    /// Irreversibly transitions to a reference that permits traversal and offers
641    /// destructive methods and little else.
642    pub(super) fn into_dying(self) -> NodeRef<marker::Dying, K, V, Type> {
643        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
644    }
645}
646
647impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
648    /// Adds a key-value pair to the end of the node, and returns
649    /// a handle to the inserted value.
650    ///
651    /// # Safety
652    ///
653    /// The returned handle has an unbound lifetime.
654    pub(super) unsafe fn push_with_handle<'b>(
655        &mut self,
656        key: K,
657        val: V,
658    ) -> Handle<NodeRef<marker::Mut<'b>, K, V, marker::Leaf>, marker::KV> {
659        let len = self.len_mut();
660        let idx = usize::from(*len);
661        assert!(idx < CAPACITY);
662        *len += 1;
663        unsafe {
664            self.key_area_mut(idx).write(key);
665            self.val_area_mut(idx).write(val);
666            Handle::new_kv(
667                NodeRef { height: self.height, node: self.node, _marker: PhantomData },
668                idx,
669            )
670        }
671    }
672
673    /// Adds a key-value pair to the end of the node, and returns
674    /// the mutable reference of the inserted value.
675    pub(super) fn push(&mut self, key: K, val: V) -> *mut V {
676        // SAFETY: The unbound handle is no longer accessible.
677        unsafe { self.push_with_handle(key, val).into_val_mut() }
678    }
679}
680
681impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
682    /// Adds a key-value pair, and an edge to go to the right of that pair,
683    /// to the end of the node.
684    pub(super) fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
685        assert!(edge.height == self.height - 1);
686
687        let len = self.len_mut();
688        let idx = usize::from(*len);
689        assert!(idx < CAPACITY);
690        *len += 1;
691        unsafe {
692            self.key_area_mut(idx).write(key);
693            self.val_area_mut(idx).write(val);
694            self.edge_area_mut(idx + 1).write(edge.node);
695            Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
696        }
697    }
698}
699
700impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> {
701    /// Removes any static information asserting that this node is a `Leaf` node.
702    pub(super) fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
703        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
704    }
705}
706
707impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
708    /// Removes any static information asserting that this node is an `Internal` node.
709    pub(super) fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
710        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
711    }
712}
713
714impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
715    /// Checks whether a node is an `Internal` node or a `Leaf` node.
716    pub(super) fn force(
717        self,
718    ) -> ForceResult<
719        NodeRef<BorrowType, K, V, marker::Leaf>,
720        NodeRef<BorrowType, K, V, marker::Internal>,
721    > {
722        if self.height == 0 {
723            ForceResult::Leaf(NodeRef {
724                height: self.height,
725                node: self.node,
726                _marker: PhantomData,
727            })
728        } else {
729            ForceResult::Internal(NodeRef {
730                height: self.height,
731                node: self.node,
732                _marker: PhantomData,
733            })
734        }
735    }
736}
737
738impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
739    /// Unsafely asserts to the compiler the static information that this node is a `Leaf`.
740    pub(super) unsafe fn cast_to_leaf_unchecked(
741        self,
742    ) -> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
743        debug_assert!(self.height == 0);
744        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
745    }
746
747    /// Unsafely asserts to the compiler the static information that this node is an `Internal`.
748    unsafe fn cast_to_internal_unchecked(self) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
749        debug_assert!(self.height > 0);
750        NodeRef { height: self.height, node: self.node, _marker: PhantomData }
751    }
752}
753
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).
757///
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.
762pub(super) struct Handle<Node, Type> {
763    node: Node,
764    idx: usize,
765    _marker: PhantomData<Type>,
766}
767
768impl<Node: Copy, Type> Copy for Handle<Node, Type> {}
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`.
771impl<Node: Copy, Type> Clone for Handle<Node, Type> {
772    fn clone(&self) -> Self {
773        *self
774    }
775}
776
777impl<Node, Type> Handle<Node, Type> {
778    /// Retrieves the node that contains the edge or key-value pair this handle points to.
779    pub(super) fn into_node(self) -> Node {
780        self.node
781    }
782
783    /// Returns the position of this handle in the node.
784    pub(super) fn idx(&self) -> usize {
785        self.idx
786    }
787}
788
789impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
790    /// Creates a new handle to a key-value pair in `node`.
791    /// Unsafe because the caller must ensure that `idx < node.len()`.
792    pub(super) unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
793        debug_assert!(idx < node.len());
794
795        Handle { node, idx, _marker: PhantomData }
796    }
797
798    pub(super) fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
799        unsafe { Handle::new_edge(self.node, self.idx) }
800    }
801
802    pub(super) fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
803        unsafe { Handle::new_edge(self.node, self.idx + 1) }
804    }
805}
806
807impl<BorrowType, K, V, NodeType, HandleType> PartialEq
808    for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
809{
810    fn eq(&self, other: &Self) -> bool {
811        let Self { node, idx, _marker } = self;
812        node.eq(&other.node) && *idx == other.idx
813    }
814}
815
816impl<BorrowType, K, V, NodeType, HandleType>
817    Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
818{
819    /// Temporarily takes out another immutable handle on the same location.
820    pub(super) fn reborrow(
821        &self,
822    ) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
823        // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
824        Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
825    }
826}
827
828impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
829    /// Temporarily takes out another mutable handle on the same location. Beware, as
830    /// this method is very dangerous, doubly so since it might not immediately appear
831    /// dangerous.
832    ///
833    /// For details, see `NodeRef::reborrow_mut`.
834    pub(super) unsafe fn reborrow_mut(
835        &mut self,
836    ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
837        // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
838        Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData }
839    }
840
841    /// Returns a dormant copy of this handle which can be reawakened later.
842    ///
843    /// See `DormantMutRef` for more details.
844    pub(super) fn dormant(
845        &self,
846    ) -> Handle<NodeRef<marker::DormantMut, K, V, NodeType>, HandleType> {
847        Handle { node: self.node.dormant(), idx: self.idx, _marker: PhantomData }
848    }
849}
850
851impl<K, V, NodeType, HandleType> Handle<NodeRef<marker::DormantMut, K, V, NodeType>, HandleType> {
852    /// Revert to the unique borrow initially captured.
853    ///
854    /// # Safety
855    ///
856    /// The reborrow must have ended, i.e., the reference returned by `new` and
857    /// all pointers and references derived from it, must not be used anymore.
858    pub(super) unsafe fn awaken<'a>(
859        self,
860    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
861        Handle { node: unsafe { self.node.awaken() }, idx: self.idx, _marker: PhantomData }
862    }
863}
864
865impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
866    /// Creates a new handle to an edge in `node`.
867    /// Unsafe because the caller must ensure that `idx <= node.len()`.
868    pub(super) unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
869        debug_assert!(idx <= node.len());
870
871        Handle { node, idx, _marker: PhantomData }
872    }
873
874    pub(super) fn left_kv(
875        self,
876    ) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
877        if self.idx > 0 {
878            Ok(unsafe { Handle::new_kv(self.node, self.idx - 1) })
879        } else {
880            Err(self)
881        }
882    }
883
884    pub(super) fn right_kv(
885        self,
886    ) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
887        if self.idx < self.node.len() {
888            Ok(unsafe { Handle::new_kv(self.node, self.idx) })
889        } else {
890            Err(self)
891        }
892    }
893}
894
895pub(super) enum LeftOrRight<T> {
896    Left(T),
897    Right(T),
898}
899
900/// Given an edge index where we want to insert into a node filled to capacity,
901/// computes a sensible KV index of a split point and where to perform the insertion.
902/// The goal of the split point is for its key and value to end up in a parent node;
903/// the keys, values and edges to the left of the split point become the left child;
904/// the keys, values and edges to the right of the split point become the right child.
905fn splitpoint(edge_idx: usize) -> (usize, LeftOrRight<usize>) {
906    debug_assert!(edge_idx <= CAPACITY);
907    // Rust issue #74834 tries to explain these symmetric rules.
908    match edge_idx {
909        0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, LeftOrRight::Left(edge_idx)),
910        EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, LeftOrRight::Left(edge_idx)),
911        EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, LeftOrRight::Right(0)),
912        _ => (KV_IDX_CENTER + 1, LeftOrRight::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))),
913    }
914}
915
916impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
917    /// Inserts a new key-value pair between the key-value pairs to the right and left of
918    /// this edge. This method assumes that there is enough space in the node for the new
919    /// pair to fit.
920    unsafe fn insert_fit(
921        mut self,
922        key: K,
923        val: V,
924    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
925        debug_assert!(self.node.len() < CAPACITY);
926        let new_len = self.node.len() + 1;
927
928        unsafe {
929            slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
930            slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
931            *self.node.len_mut() = new_len as u16;
932
933            Handle::new_kv(self.node, self.idx)
934        }
935    }
936}
937
938impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
939    /// Inserts a new key-value pair between the key-value pairs to the right and left of
940    /// this edge. This method splits the node if there isn't enough room.
941    ///
942    /// Returns a dormant handle to the inserted node which can be reawakened
943    /// once splitting is complete.
944    fn insert<A: Allocator + Clone>(
945        self,
946        key: K,
947        val: V,
948        alloc: A,
949    ) -> (
950        Option<SplitResult<'a, K, V, marker::Leaf>>,
951        Handle<NodeRef<marker::DormantMut, K, V, marker::Leaf>, marker::KV>,
952    ) {
953        if self.node.len() < CAPACITY {
954            // SAFETY: There is enough space in the node for insertion.
955            let handle = unsafe { self.insert_fit(key, val) };
956            (None, handle.dormant())
957        } else {
958            let (middle_kv_idx, insertion) = splitpoint(self.idx);
959            let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
960            let mut result = middle.split(alloc);
961            let insertion_edge = match insertion {
962                LeftOrRight::Left(insert_idx) => unsafe {
963                    Handle::new_edge(result.left.reborrow_mut(), insert_idx)
964                },
965                LeftOrRight::Right(insert_idx) => unsafe {
966                    Handle::new_edge(result.right.borrow_mut(), insert_idx)
967                },
968            };
969            // SAFETY: We just split the node, so there is enough space for
970            // insertion.
971            let handle = unsafe { insertion_edge.insert_fit(key, val).dormant() };
972            (Some(result), handle)
973        }
974    }
975}
976
977impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
978    /// Fixes the parent pointer and index in the child node that this edge
979    /// links to. This is useful when the ordering of edges has been changed,
980    fn correct_parent_link(self) {
981        // Create backpointer without invalidating other references to the node.
982        let ptr = unsafe { NonNull::new_unchecked(NodeRef::as_internal_ptr(&self.node)) };
983        let idx = self.idx;
984        let mut child = self.descend();
985        child.set_parent_link(ptr, idx);
986    }
987}
988
989impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
990    /// Inserts a new key-value pair and an edge that will go to the right of that new pair
991    /// between this edge and the key-value pair to the right of this edge. This method assumes
992    /// that there is enough space in the node for the new pair to fit.
993    fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
994        debug_assert!(self.node.len() < CAPACITY);
995        debug_assert!(edge.height == self.node.height - 1);
996        let new_len = self.node.len() + 1;
997
998        unsafe {
999            slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
1000            slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
1001            slice_insert(self.node.edge_area_mut(..new_len + 1), self.idx + 1, edge.node);
1002            *self.node.len_mut() = new_len as u16;
1003
1004            self.node.correct_childrens_parent_links(self.idx + 1..new_len + 1);
1005        }
1006    }
1007
1008    /// Inserts a new key-value pair and an edge that will go to the right of that new pair
1009    /// between this edge and the key-value pair to the right of this edge. This method splits
1010    /// the node if there isn't enough room.
1011    fn insert<A: Allocator + Clone>(
1012        mut self,
1013        key: K,
1014        val: V,
1015        edge: Root<K, V>,
1016        alloc: A,
1017    ) -> Option<SplitResult<'a, K, V, marker::Internal>> {
1018        assert!(edge.height == self.node.height - 1);
1019
1020        if self.node.len() < CAPACITY {
1021            self.insert_fit(key, val, edge);
1022            None
1023        } else {
1024            let (middle_kv_idx, insertion) = splitpoint(self.idx);
1025            let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
1026            let mut result = middle.split(alloc);
1027            let mut insertion_edge = match insertion {
1028                LeftOrRight::Left(insert_idx) => unsafe {
1029                    Handle::new_edge(result.left.reborrow_mut(), insert_idx)
1030                },
1031                LeftOrRight::Right(insert_idx) => unsafe {
1032                    Handle::new_edge(result.right.borrow_mut(), insert_idx)
1033                },
1034            };
1035            insertion_edge.insert_fit(key, val, edge);
1036            Some(result)
1037        }
1038    }
1039}
1040
1041impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
1042    /// Inserts a new key-value pair between the key-value pairs to the right and left of
1043    /// this edge. This method splits the node if there isn't enough room, and tries to
1044    /// insert the split off portion into the parent node recursively, until the root is reached.
1045    ///
1046    /// If the returned result is some `SplitResult`, the `left` field will be the root node.
1047    /// The returned pointer points to the inserted value, which in the case of `SplitResult`
1048    /// is in the `left` or `right` tree.
1049    pub(super) fn insert_recursing<A: Allocator + Clone>(
1050        self,
1051        key: K,
1052        value: V,
1053        alloc: A,
1054        split_root: impl FnOnce(SplitResult<'a, K, V, marker::LeafOrInternal>),
1055    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
1056        let (mut split, handle) = match self.insert(key, value, alloc.clone()) {
1057            // SAFETY: we have finished splitting and can now re-awaken the
1058            // handle to the inserted element.
1059            (None, handle) => return unsafe { handle.awaken() },
1060            (Some(split), handle) => (split.forget_node_type(), handle),
1061        };
1062
1063        loop {
1064            split = match split.left.ascend() {
1065                Ok(parent) => {
1066                    match parent.insert(split.kv.0, split.kv.1, split.right, alloc.clone()) {
1067                        // SAFETY: we have finished splitting and can now re-awaken the
1068                        // handle to the inserted element.
1069                        None => return unsafe { handle.awaken() },
1070                        Some(split) => split.forget_node_type(),
1071                    }
1072                }
1073                Err(root) => {
1074                    split_root(SplitResult { left: root, ..split });
1075                    // SAFETY: we have finished splitting and can now re-awaken the
1076                    // handle to the inserted element.
1077                    return unsafe { handle.awaken() };
1078                }
1079            };
1080        }
1081    }
1082}
1083
1084impl<BorrowType: marker::BorrowType, K, V>
1085    Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>
1086{
1087    /// Finds the node pointed to by this edge.
1088    ///
1089    /// The method name assumes you picture trees with the root node on top.
1090    ///
1091    /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
1092    /// both, upon success, do nothing.
1093    pub(super) fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
1094        const {
1095            assert!(BorrowType::TRAVERSAL_PERMIT);
1096        }
1097
1098        // We need to use raw pointers to nodes because, if BorrowType is
1099        // marker::ValMut, there might be outstanding mutable references to
1100        // values that we must not invalidate. There's no worry accessing the
1101        // height field because that value is copied. Beware that, once the
1102        // node pointer is dereferenced, we access the edges array with a
1103        // reference (Rust issue #73987) and invalidate any other references
1104        // to or inside the array, should any be around.
1105        let parent_ptr = NodeRef::as_internal_ptr(&self.node);
1106        let node = unsafe { (*parent_ptr).edges.get_unchecked(self.idx).assume_init_read() };
1107        NodeRef { node, height: self.node.height - 1, _marker: PhantomData }
1108    }
1109}
1110
1111impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
1112    pub(super) fn into_kv(self) -> (&'a K, &'a V) {
1113        debug_assert!(self.idx < self.node.len());
1114        let leaf = self.node.into_leaf();
1115        let k = unsafe { leaf.keys.get_unchecked(self.idx).assume_init_ref() };
1116        let v = unsafe { leaf.vals.get_unchecked(self.idx).assume_init_ref() };
1117        (k, v)
1118    }
1119}
1120
1121impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1122    pub(super) fn key_mut(&mut self) -> &mut K {
1123        unsafe { self.node.key_area_mut(self.idx).assume_init_mut() }
1124    }
1125
1126    pub(super) fn into_val_mut(self) -> &'a mut V {
1127        debug_assert!(self.idx < self.node.len());
1128        let leaf = self.node.into_leaf_mut();
1129        unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }
1130    }
1131
1132    pub(super) fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
1133        debug_assert!(self.idx < self.node.len());
1134        let leaf = self.node.into_leaf_mut();
1135        let k = unsafe { leaf.keys.get_unchecked_mut(self.idx).assume_init_mut() };
1136        let v = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() };
1137        (k, v)
1138    }
1139}
1140
1141impl<'a, K, V, NodeType> Handle<NodeRef<marker::ValMut<'a>, K, V, NodeType>, marker::KV> {
1142    pub(super) fn into_kv_valmut(self) -> (&'a K, &'a mut V) {
1143        unsafe { self.node.into_key_val_mut_at(self.idx) }
1144    }
1145}
1146
1147impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1148    pub(super) fn kv_mut(&mut self) -> (&mut K, &mut V) {
1149        debug_assert!(self.idx < self.node.len());
1150        // We cannot call separate key and value methods, because calling the second one
1151        // invalidates the reference returned by the first.
1152        unsafe {
1153            let leaf = self.node.as_leaf_mut();
1154            let key = leaf.keys.get_unchecked_mut(self.idx).assume_init_mut();
1155            let val = leaf.vals.get_unchecked_mut(self.idx).assume_init_mut();
1156            (key, val)
1157        }
1158    }
1159
1160    /// Replaces the key and value that the KV handle refers to.
1161    pub(super) fn replace_kv(&mut self, k: K, v: V) -> (K, V) {
1162        let (key, val) = self.kv_mut();
1163        (mem::replace(key, k), mem::replace(val, v))
1164    }
1165}
1166
1167impl<K, V, NodeType> Handle<NodeRef<marker::Dying, K, V, NodeType>, marker::KV> {
1168    /// Extracts the key and value that the KV handle refers to.
1169    /// # Safety
1170    /// The node that the handle refers to must not yet have been deallocated.
1171    pub(super) unsafe fn into_key_val(mut self) -> (K, V) {
1172        debug_assert!(self.idx < self.node.len());
1173        let leaf = self.node.as_leaf_dying();
1174        unsafe {
1175            let key = leaf.keys.get_unchecked_mut(self.idx).assume_init_read();
1176            let val = leaf.vals.get_unchecked_mut(self.idx).assume_init_read();
1177            (key, val)
1178        }
1179    }
1180
1181    /// Drops the key and value that the KV handle refers to.
1182    /// # Safety
1183    /// The node that the handle refers to must not yet have been deallocated.
1184    #[inline]
1185    pub(super) unsafe fn drop_key_val(mut self) {
1186        // Run the destructor of the value even if the destructor of the key panics.
1187        struct Dropper<'a, T>(&'a mut MaybeUninit<T>);
1188        impl<T> Drop for Dropper<'_, T> {
1189            #[inline]
1190            fn drop(&mut self) {
1191                unsafe {
1192                    self.0.assume_init_drop();
1193                }
1194            }
1195        }
1196
1197        debug_assert!(self.idx < self.node.len());
1198        let leaf = self.node.as_leaf_dying();
1199        unsafe {
1200            let key = leaf.keys.get_unchecked_mut(self.idx);
1201            let val = leaf.vals.get_unchecked_mut(self.idx);
1202            let _guard = Dropper(val);
1203            key.assume_init_drop();
1204            // dropping the guard will drop the value
1205        }
1206    }
1207}
1208
1209impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1210    /// Helps implementations of `split` for a particular `NodeType`,
1211    /// by taking care of leaf data.
1212    fn split_leaf_data(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V) {
1213        debug_assert!(self.idx < self.node.len());
1214        let old_len = self.node.len();
1215        let new_len = old_len - self.idx - 1;
1216        new_node.len = new_len as u16;
1217        unsafe {
1218            let k = self.node.key_area_mut(self.idx).assume_init_read();
1219            let v = self.node.val_area_mut(self.idx).assume_init_read();
1220
1221            move_to_slice(
1222                self.node.key_area_mut(self.idx + 1..old_len),
1223                &mut new_node.keys[..new_len],
1224            );
1225            move_to_slice(
1226                self.node.val_area_mut(self.idx + 1..old_len),
1227                &mut new_node.vals[..new_len],
1228            );
1229
1230            *self.node.len_mut() = self.idx as u16;
1231            (k, v)
1232        }
1233    }
1234}
1235
1236impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
1237    /// Splits the underlying node into three parts:
1238    ///
1239    /// - The node is truncated to only contain the key-value pairs to the left of
1240    ///   this handle.
1241    /// - The key and value pointed to by this handle are extracted.
1242    /// - All the key-value pairs to the right of this handle are put into a newly
1243    ///   allocated node.
1244    pub(super) fn split<A: Allocator + Clone>(
1245        mut self,
1246        alloc: A,
1247    ) -> SplitResult<'a, K, V, marker::Leaf> {
1248        let mut new_node = LeafNode::new(alloc);
1249
1250        let kv = self.split_leaf_data(&mut new_node);
1251
1252        let right = NodeRef::from_new_leaf(new_node);
1253        SplitResult { left: self.node, kv, right }
1254    }
1255
1256    /// Removes the key-value pair pointed to by this handle and returns it, along with the edge
1257    /// that the key-value pair collapsed into.
1258    pub(super) fn remove(
1259        mut self,
1260    ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
1261        let old_len = self.node.len();
1262        unsafe {
1263            let k = slice_remove(self.node.key_area_mut(..old_len), self.idx);
1264            let v = slice_remove(self.node.val_area_mut(..old_len), self.idx);
1265            *self.node.len_mut() = (old_len - 1) as u16;
1266            ((k, v), self.left_edge())
1267        }
1268    }
1269}
1270
1271impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1272    /// Splits the underlying node into three parts:
1273    ///
1274    /// - The node is truncated to only contain the edges and key-value pairs to the
1275    ///   left of this handle.
1276    /// - The key and value pointed to by this handle are extracted.
1277    /// - All the edges and key-value pairs to the right of this handle are put into
1278    ///   a newly allocated node.
1279    pub(super) fn split<A: Allocator + Clone>(
1280        mut self,
1281        alloc: A,
1282    ) -> SplitResult<'a, K, V, marker::Internal> {
1283        let old_len = self.node.len();
1284        unsafe {
1285            let mut new_node = InternalNode::new(alloc);
1286            let kv = self.split_leaf_data(&mut new_node.data);
1287            let new_len = usize::from(new_node.data.len);
1288            move_to_slice(
1289                self.node.edge_area_mut(self.idx + 1..old_len + 1),
1290                &mut new_node.edges[..new_len + 1],
1291            );
1292
1293            let height = self.node.height;
1294            let right = NodeRef::from_new_internal(new_node, height);
1295
1296            SplitResult { left: self.node, kv, right }
1297        }
1298    }
1299}
1300
1301/// Represents a session for evaluating and performing a balancing operation
1302/// around an internal key-value pair.
1303pub(super) struct BalancingContext<'a, K, V> {
1304    parent: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV>,
1305    left_child: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1306    right_child: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1307}
1308
1309impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1310    pub(super) fn consider_for_balancing(self) -> BalancingContext<'a, K, V> {
1311        let self1 = unsafe { ptr::read(&self) };
1312        let self2 = unsafe { ptr::read(&self) };
1313        BalancingContext {
1314            parent: self,
1315            left_child: self1.left_edge().descend(),
1316            right_child: self2.right_edge().descend(),
1317        }
1318    }
1319}
1320
1321impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1322    /// Chooses a balancing context involving the node as a child, thus between
1323    /// the KV immediately to the left or to the right in the parent node.
1324    /// Returns an `Err` if there is no parent.
1325    /// Panics if the parent is empty.
1326    ///
1327    /// Prefers the left side, to be optimal if the given node is somehow
1328    /// underfull, meaning here only that it has fewer elements than its left
1329    /// sibling and than its right sibling, if they exist. In that case,
1330    /// merging with the left sibling is faster, since we only need to move
1331    /// the node's N elements, instead of shifting them to the right and moving
1332    /// more than N elements in front. Stealing from the left sibling is also
1333    /// typically faster, since we only need to shift the node's N elements to
1334    /// the right, instead of shifting at least N of the sibling's elements to
1335    /// the left.
1336    pub(super) fn choose_parent_kv(self) -> Result<LeftOrRight<BalancingContext<'a, K, V>>, Self> {
1337        match unsafe { ptr::read(&self) }.ascend() {
1338            Ok(parent_edge) => match parent_edge.left_kv() {
1339                Ok(left_parent_kv) => Ok(LeftOrRight::Left(BalancingContext {
1340                    parent: unsafe { ptr::read(&left_parent_kv) },
1341                    left_child: left_parent_kv.left_edge().descend(),
1342                    right_child: self,
1343                })),
1344                Err(parent_edge) => match parent_edge.right_kv() {
1345                    Ok(right_parent_kv) => Ok(LeftOrRight::Right(BalancingContext {
1346                        parent: unsafe { ptr::read(&right_parent_kv) },
1347                        left_child: self,
1348                        right_child: right_parent_kv.right_edge().descend(),
1349                    })),
1350                    Err(_) => unreachable!("empty internal node"),
1351                },
1352            },
1353            Err(root) => Err(root),
1354        }
1355    }
1356}
1357
1358impl<'a, K, V> BalancingContext<'a, K, V> {
1359    pub(super) fn left_child_len(&self) -> usize {
1360        self.left_child.len()
1361    }
1362
1363    pub(super) fn right_child_len(&self) -> usize {
1364        self.right_child.len()
1365    }
1366
1367    pub(super) fn into_left_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1368        self.left_child
1369    }
1370
1371    pub(super) fn into_right_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1372        self.right_child
1373    }
1374
1375    /// Returns whether merging is possible, i.e., whether there is enough room
1376    /// in a node to combine the central KV with both adjacent child nodes.
1377    pub(super) fn can_merge(&self) -> bool {
1378        self.left_child.len() + 1 + self.right_child.len() <= CAPACITY
1379    }
1380}
1381
1382impl<'a, K: 'a, V: 'a> BalancingContext<'a, K, V> {
1383    /// Performs a merge and lets a closure decide what to return.
1384    fn do_merge<
1385        F: FnOnce(
1386            NodeRef<marker::Mut<'a>, K, V, marker::Internal>,
1387            NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1388        ) -> R,
1389        R,
1390        A: Allocator,
1391    >(
1392        self,
1393        result: F,
1394        alloc: A,
1395    ) -> R {
1396        let Handle { node: mut parent_node, idx: parent_idx, _marker } = self.parent;
1397        let old_parent_len = parent_node.len();
1398        let mut left_node = self.left_child;
1399        let old_left_len = left_node.len();
1400        let mut right_node = self.right_child;
1401        let right_len = right_node.len();
1402        let new_left_len = old_left_len + 1 + right_len;
1403
1404        assert!(new_left_len <= CAPACITY);
1405
1406        unsafe {
1407            *left_node.len_mut() = new_left_len as u16;
1408
1409            let parent_key = slice_remove(parent_node.key_area_mut(..old_parent_len), parent_idx);
1410            left_node.key_area_mut(old_left_len).write(parent_key);
1411            move_to_slice(
1412                right_node.key_area_mut(..right_len),
1413                left_node.key_area_mut(old_left_len + 1..new_left_len),
1414            );
1415
1416            let parent_val = slice_remove(parent_node.val_area_mut(..old_parent_len), parent_idx);
1417            left_node.val_area_mut(old_left_len).write(parent_val);
1418            move_to_slice(
1419                right_node.val_area_mut(..right_len),
1420                left_node.val_area_mut(old_left_len + 1..new_left_len),
1421            );
1422
1423            slice_remove(&mut parent_node.edge_area_mut(..old_parent_len + 1), parent_idx + 1);
1424            parent_node.correct_childrens_parent_links(parent_idx + 1..old_parent_len);
1425            *parent_node.len_mut() -= 1;
1426
1427            if parent_node.height > 1 {
1428                // SAFETY: the height of the nodes being merged is one below the height
1429                // of the node of this edge, thus above zero, so they are internal.
1430                let mut left_node = left_node.reborrow_mut().cast_to_internal_unchecked();
1431                let mut right_node = right_node.cast_to_internal_unchecked();
1432                move_to_slice(
1433                    right_node.edge_area_mut(..right_len + 1),
1434                    left_node.edge_area_mut(old_left_len + 1..new_left_len + 1),
1435                );
1436
1437                left_node.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);
1438
1439                alloc.deallocate(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
1440            } else {
1441                alloc.deallocate(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
1442            }
1443        }
1444        result(parent_node, left_node)
1445    }
1446
1447    /// Merges the parent's key-value pair and both adjacent child nodes into
1448    /// the left child node and returns the shrunk parent node.
1449    ///
1450    /// Panics unless we `.can_merge()`.
1451    pub(super) fn merge_tracking_parent<A: Allocator + Clone>(
1452        self,
1453        alloc: A,
1454    ) -> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
1455        self.do_merge(|parent, _child| parent, alloc)
1456    }
1457
1458    /// Merges the parent's key-value pair and both adjacent child nodes into
1459    /// the left child node and returns that child node.
1460    ///
1461    /// Panics unless we `.can_merge()`.
1462    pub(super) fn merge_tracking_child<A: Allocator + Clone>(
1463        self,
1464        alloc: A,
1465    ) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
1466        self.do_merge(|_parent, child| child, alloc)
1467    }
1468
1469    /// Merges the parent's key-value pair and both adjacent child nodes into
1470    /// the left child node and returns the edge handle in that child node
1471    /// where the tracked child edge ended up,
1472    ///
1473    /// Panics unless we `.can_merge()`.
1474    pub(super) fn merge_tracking_child_edge<A: Allocator + Clone>(
1475        self,
1476        track_edge_idx: LeftOrRight<usize>,
1477        alloc: A,
1478    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1479        let old_left_len = self.left_child.len();
1480        let right_len = self.right_child.len();
1481        assert!(match track_edge_idx {
1482            LeftOrRight::Left(idx) => idx <= old_left_len,
1483            LeftOrRight::Right(idx) => idx <= right_len,
1484        });
1485        let child = self.merge_tracking_child(alloc);
1486        let new_idx = match track_edge_idx {
1487            LeftOrRight::Left(idx) => idx,
1488            LeftOrRight::Right(idx) => old_left_len + 1 + idx,
1489        };
1490        unsafe { Handle::new_edge(child, new_idx) }
1491    }
1492
1493    /// Removes a key-value pair from the left child and places it in the key-value storage
1494    /// of the parent, while pushing the old parent key-value pair into the right child.
1495    /// Returns a handle to the edge in the right child corresponding to where the original
1496    /// edge specified by `track_right_edge_idx` ended up.
1497    pub(super) fn steal_left(
1498        mut self,
1499        track_right_edge_idx: usize,
1500    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1501        self.bulk_steal_left(1);
1502        unsafe { Handle::new_edge(self.right_child, 1 + track_right_edge_idx) }
1503    }
1504
1505    /// Removes a key-value pair from the right child and places it in the key-value storage
1506    /// of the parent, while pushing the old parent key-value pair onto the left child.
1507    /// Returns a handle to the edge in the left child specified by `track_left_edge_idx`,
1508    /// which didn't move.
1509    pub(super) fn steal_right(
1510        mut self,
1511        track_left_edge_idx: usize,
1512    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1513        self.bulk_steal_right(1);
1514        unsafe { Handle::new_edge(self.left_child, track_left_edge_idx) }
1515    }
1516
1517    /// This does stealing similar to `steal_left` but steals multiple elements at once.
1518    pub(super) fn bulk_steal_left(&mut self, count: usize) {
1519        assert!(count > 0);
1520        unsafe {
1521            let left_node = &mut self.left_child;
1522            let old_left_len = left_node.len();
1523            let right_node = &mut self.right_child;
1524            let old_right_len = right_node.len();
1525
1526            // Make sure that we may steal safely.
1527            assert!(old_right_len + count <= CAPACITY);
1528            assert!(old_left_len >= count);
1529
1530            let new_left_len = old_left_len - count;
1531            let new_right_len = old_right_len + count;
1532            *left_node.len_mut() = new_left_len as u16;
1533            *right_node.len_mut() = new_right_len as u16;
1534
1535            // Move leaf data.
1536            {
1537                // Make room for stolen elements in the right child.
1538                slice_shr(right_node.key_area_mut(..new_right_len), count);
1539                slice_shr(right_node.val_area_mut(..new_right_len), count);
1540
1541                // Move elements from the left child to the right one.
1542                move_to_slice(
1543                    left_node.key_area_mut(new_left_len + 1..old_left_len),
1544                    right_node.key_area_mut(..count - 1),
1545                );
1546                move_to_slice(
1547                    left_node.val_area_mut(new_left_len + 1..old_left_len),
1548                    right_node.val_area_mut(..count - 1),
1549                );
1550
1551                // Move the leftmost stolen pair to the parent.
1552                let k = left_node.key_area_mut(new_left_len).assume_init_read();
1553                let v = left_node.val_area_mut(new_left_len).assume_init_read();
1554                let (k, v) = self.parent.replace_kv(k, v);
1555
1556                // Move parent's key-value pair to the right child.
1557                right_node.key_area_mut(count - 1).write(k);
1558                right_node.val_area_mut(count - 1).write(v);
1559            }
1560
1561            match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
1562                (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1563                    // Make room for stolen edges.
1564                    slice_shr(right.edge_area_mut(..new_right_len + 1), count);
1565
1566                    // Steal edges.
1567                    move_to_slice(
1568                        left.edge_area_mut(new_left_len + 1..old_left_len + 1),
1569                        right.edge_area_mut(..count),
1570                    );
1571
1572                    right.correct_childrens_parent_links(0..new_right_len + 1);
1573                }
1574                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1575                _ => unreachable!(),
1576            }
1577        }
1578    }
1579
1580    /// The symmetric clone of `bulk_steal_left`.
1581    pub(super) fn bulk_steal_right(&mut self, count: usize) {
1582        assert!(count > 0);
1583        unsafe {
1584            let left_node = &mut self.left_child;
1585            let old_left_len = left_node.len();
1586            let right_node = &mut self.right_child;
1587            let old_right_len = right_node.len();
1588
1589            // Make sure that we may steal safely.
1590            assert!(old_left_len + count <= CAPACITY);
1591            assert!(old_right_len >= count);
1592
1593            let new_left_len = old_left_len + count;
1594            let new_right_len = old_right_len - count;
1595            *left_node.len_mut() = new_left_len as u16;
1596            *right_node.len_mut() = new_right_len as u16;
1597
1598            // Move leaf data.
1599            {
1600                // Move the rightmost stolen pair to the parent.
1601                let k = right_node.key_area_mut(count - 1).assume_init_read();
1602                let v = right_node.val_area_mut(count - 1).assume_init_read();
1603                let (k, v) = self.parent.replace_kv(k, v);
1604
1605                // Move parent's key-value pair to the left child.
1606                left_node.key_area_mut(old_left_len).write(k);
1607                left_node.val_area_mut(old_left_len).write(v);
1608
1609                // Move elements from the right child to the left one.
1610                move_to_slice(
1611                    right_node.key_area_mut(..count - 1),
1612                    left_node.key_area_mut(old_left_len + 1..new_left_len),
1613                );
1614                move_to_slice(
1615                    right_node.val_area_mut(..count - 1),
1616                    left_node.val_area_mut(old_left_len + 1..new_left_len),
1617                );
1618
1619                // Fill gap where stolen elements used to be.
1620                slice_shl(right_node.key_area_mut(..old_right_len), count);
1621                slice_shl(right_node.val_area_mut(..old_right_len), count);
1622            }
1623
1624            match (left_node.reborrow_mut().force(), right_node.reborrow_mut().force()) {
1625                (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1626                    // Steal edges.
1627                    move_to_slice(
1628                        right.edge_area_mut(..count),
1629                        left.edge_area_mut(old_left_len + 1..new_left_len + 1),
1630                    );
1631
1632                    // Fill gap where stolen edges used to be.
1633                    slice_shl(right.edge_area_mut(..old_right_len + 1), count);
1634
1635                    left.correct_childrens_parent_links(old_left_len + 1..new_left_len + 1);
1636                    right.correct_childrens_parent_links(0..new_right_len + 1);
1637                }
1638                (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1639                _ => unreachable!(),
1640            }
1641        }
1642    }
1643}
1644
1645impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1646    pub(super) fn forget_node_type(
1647        self,
1648    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1649        unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1650    }
1651}
1652
1653impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
1654    pub(super) fn forget_node_type(
1655        self,
1656    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1657        unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1658    }
1659}
1660
1661impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> {
1662    pub(super) fn forget_node_type(
1663        self,
1664    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
1665        unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
1666    }
1667}
1668
1669impl<BorrowType, K, V, Type> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, Type> {
1670    /// Checks whether the underlying node is an `Internal` node or a `Leaf` node.
1671    pub(super) fn force(
1672        self,
1673    ) -> ForceResult<
1674        Handle<NodeRef<BorrowType, K, V, marker::Leaf>, Type>,
1675        Handle<NodeRef<BorrowType, K, V, marker::Internal>, Type>,
1676    > {
1677        match self.node.force() {
1678            ForceResult::Leaf(node) => {
1679                ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData })
1680            }
1681            ForceResult::Internal(node) => {
1682                ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData })
1683            }
1684        }
1685    }
1686}
1687
1688impl<'a, K, V, Type> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, Type> {
1689    /// Unsafely asserts to the compiler the static information that the handle's node is a `Leaf`.
1690    pub(super) unsafe fn cast_to_leaf_unchecked(
1691        self,
1692    ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, Type> {
1693        let node = unsafe { self.node.cast_to_leaf_unchecked() };
1694        Handle { node, idx: self.idx, _marker: PhantomData }
1695    }
1696}
1697
1698impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1699    /// Move the suffix after `self` from one node to another one. `right` must be empty.
1700    /// The first edge of `right` remains unchanged.
1701    pub(super) fn move_suffix(
1702        &mut self,
1703        right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1704    ) {
1705        unsafe {
1706            let new_left_len = self.idx;
1707            let mut left_node = self.reborrow_mut().into_node();
1708            let old_left_len = left_node.len();
1709
1710            let new_right_len = old_left_len - new_left_len;
1711            let mut right_node = right.reborrow_mut();
1712
1713            assert!(right_node.len() == 0);
1714            assert!(left_node.height == right_node.height);
1715
1716            if new_right_len > 0 {
1717                *left_node.len_mut() = new_left_len as u16;
1718                *right_node.len_mut() = new_right_len as u16;
1719
1720                move_to_slice(
1721                    left_node.key_area_mut(new_left_len..old_left_len),
1722                    right_node.key_area_mut(..new_right_len),
1723                );
1724                move_to_slice(
1725                    left_node.val_area_mut(new_left_len..old_left_len),
1726                    right_node.val_area_mut(..new_right_len),
1727                );
1728                match (left_node.force(), right_node.force()) {
1729                    (ForceResult::Internal(mut left), ForceResult::Internal(mut right)) => {
1730                        move_to_slice(
1731                            left.edge_area_mut(new_left_len + 1..old_left_len + 1),
1732                            right.edge_area_mut(1..new_right_len + 1),
1733                        );
1734                        right.correct_childrens_parent_links(1..new_right_len + 1);
1735                    }
1736                    (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1737                    _ => unreachable!(),
1738                }
1739            }
1740        }
1741    }
1742}
1743
1744pub(super) enum ForceResult<Leaf, Internal> {
1745    Leaf(Leaf),
1746    Internal(Internal),
1747}
1748
1749/// Result of insertion, when a node needed to expand beyond its capacity.
1750pub(super) struct SplitResult<'a, K, V, NodeType> {
1751    // Altered node in existing tree with elements and edges that belong to the left of `kv`.
1752    pub left: NodeRef<marker::Mut<'a>, K, V, NodeType>,
1753    // Some key and value that existed before and were split off, to be inserted elsewhere.
1754    pub kv: (K, V),
1755    // Owned, unattached, new node with elements and edges that belong to the right of `kv`.
1756    pub right: NodeRef<marker::Owned, K, V, NodeType>,
1757}
1758
1759impl<'a, K, V> SplitResult<'a, K, V, marker::Leaf> {
1760    pub(super) fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> {
1761        SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() }
1762    }
1763}
1764
1765impl<'a, K, V> SplitResult<'a, K, V, marker::Internal> {
1766    pub(super) fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> {
1767        SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() }
1768    }
1769}
1770
1771pub(super) mod marker {
1772    use core::marker::PhantomData;
1773
1774    pub(crate) enum Leaf {}
1775    pub(crate) enum Internal {}
1776    pub(crate) enum LeafOrInternal {}
1777
1778    pub(crate) enum Owned {}
1779    pub(crate) enum Dying {}
1780    pub(crate) enum DormantMut {}
1781    pub(crate) struct Immut<'a>(PhantomData<&'a ()>);
1782    pub(crate) struct Mut<'a>(PhantomData<&'a mut ()>);
1783    pub(crate) struct ValMut<'a>(PhantomData<&'a mut ()>);
1784
1785    pub(crate) trait BorrowType {
1786        /// If node references of this borrow type allow traversing to other
1787        /// nodes in the tree, this constant is set to `true`. It can be used
1788        /// for a compile-time assertion.
1789        const TRAVERSAL_PERMIT: bool = true;
1790    }
1791    impl BorrowType for Owned {
1792        /// Reject traversal, because it isn't needed. Instead traversal
1793        /// happens using the result of `borrow_mut`.
1794        /// By disabling traversal, and only creating new references to roots,
1795        /// we know that every reference of the `Owned` type is to a root node.
1796        const TRAVERSAL_PERMIT: bool = false;
1797    }
1798    impl BorrowType for Dying {}
1799    impl<'a> BorrowType for Immut<'a> {}
1800    impl<'a> BorrowType for Mut<'a> {}
1801    impl<'a> BorrowType for ValMut<'a> {}
1802    impl BorrowType for DormantMut {}
1803
1804    pub(crate) enum KV {}
1805    pub(crate) enum Edge {}
1806}
1807
1808/// Inserts a value into a slice of initialized elements followed by one uninitialized element.
1809///
1810/// # Safety
1811/// The slice has more than `idx` elements.
1812unsafe fn slice_insert<T>(slice: &mut [MaybeUninit<T>], idx: usize, val: T) {
1813    unsafe {
1814        let len = slice.len();
1815        debug_assert!(len > idx);
1816        let slice_ptr = slice.as_mut_ptr();
1817        if len > idx + 1 {
1818            ptr::copy(slice_ptr.add(idx), slice_ptr.add(idx + 1), len - idx - 1);
1819        }
1820        (*slice_ptr.add(idx)).write(val);
1821    }
1822}
1823
1824/// Removes and returns a value from a slice of all initialized elements, leaving behind one
1825/// trailing uninitialized element.
1826///
1827/// # Safety
1828/// The slice has more than `idx` elements.
1829unsafe fn slice_remove<T>(slice: &mut [MaybeUninit<T>], idx: usize) -> T {
1830    unsafe {
1831        let len = slice.len();
1832        debug_assert!(idx < len);
1833        let slice_ptr = slice.as_mut_ptr();
1834        let ret = (*slice_ptr.add(idx)).assume_init_read();
1835        ptr::copy(slice_ptr.add(idx + 1), slice_ptr.add(idx), len - idx - 1);
1836        ret
1837    }
1838}
1839
1840/// Shifts the elements in a slice `distance` positions to the left.
1841///
1842/// # Safety
1843/// The slice has at least `distance` elements.
1844unsafe fn slice_shl<T>(slice: &mut [MaybeUninit<T>], distance: usize) {
1845    unsafe {
1846        let slice_ptr = slice.as_mut_ptr();
1847        ptr::copy(slice_ptr.add(distance), slice_ptr, slice.len() - distance);
1848    }
1849}
1850
1851/// Shifts the elements in a slice `distance` positions to the right.
1852///
1853/// # Safety
1854/// The slice has at least `distance` elements.
1855unsafe fn slice_shr<T>(slice: &mut [MaybeUninit<T>], distance: usize) {
1856    unsafe {
1857        let slice_ptr = slice.as_mut_ptr();
1858        ptr::copy(slice_ptr, slice_ptr.add(distance), slice.len() - distance);
1859    }
1860}
1861
1862/// Moves all values from a slice of initialized elements to a slice
1863/// of uninitialized elements, leaving behind `src` as all uninitialized.
1864/// Works like `dst.copy_from_slice(src)` but does not require `T` to be `Copy`.
1865fn move_to_slice<T>(src: &mut [MaybeUninit<T>], dst: &mut [MaybeUninit<T>]) {
1866    assert!(src.len() == dst.len());
1867    unsafe {
1868        ptr::copy_nonoverlapping(src.as_ptr(), dst.as_mut_ptr(), src.len());
1869    }
1870}
1871
1872#[cfg(test)]
1873mod tests;