library/alloc/src/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 {
  13 //         [Box<Node<K, V, height - 1>>; 2 * B]
  14 //     } else { () },
  15 //     parent: *const Node<K, V, height + 1>,
  16 //     parent_idx: u16,
  17 //     len: u16,
  18 // }
  19 // ```
  20 //
  21 // Since Rust doesn't actually have dependent types and polymorphic recursion,
  22 // we make do with lots of unsafety.
  23
  24 // A major goal of this module is to avoid complexity by treating the tree as a generic (if
  25 // weirdly shaped) container and avoiding dealing with most of the B-Tree invariants. As such,
  26 // this module doesn't care whether the entries are sorted, which nodes can be underfull, or
  27 // even what underfull means. However, we do rely on a few invariants:
  28 //
  29 // - Trees must have uniform depth/height. This means that every path down to a leaf from a
  30 //   given node has exactly the same length.
  31 // - A node of length `n` has `n` keys, `n` values, and (in an internal node) `n + 1` edges.
  32 //   This implies that even an empty internal node has at least one edge.
  33
  34 use core::cmp::Ordering;
  35 use core::marker::PhantomData;
  36 use core::mem::{self, MaybeUninit};
  37 use core::ptr::{self, NonNull, Unique};
  38 use core::slice;
  39
  40 use crate::alloc::{AllocRef, Global, Layout};
  41 use crate::boxed::Box;
  42
  43 const B: usize = 6;
  44 pub const MIN_LEN: usize = B - 1;
  45 pub const CAPACITY: usize = 2 * B - 1;
  46 const KV_IDX_CENTER: usize = B - 1;
  47 const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1;
  48 const EDGE_IDX_RIGHT_OF_CENTER: usize = B;
  49
  50 /// The underlying representation of leaf nodes.
  51 #[repr(C)]
  52 struct LeafNode<K, V> {
  53     /// We use `*const` as opposed to `*mut` so as to be covariant in `K` and `V`.
  54     /// This either points to an actual node or is null.
  55     parent: *const InternalNode<K, V>,
  56
  57     /// This node's index into the parent node's `edges` array.
  58     /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`.
  59     /// This is only guaranteed to be initialized when `parent` is non-null.
  60     parent_idx: MaybeUninit<u16>,
  61
  62     /// The number of keys and values this node stores.
  63     ///
  64     /// This next to `parent_idx` to encourage the compiler to join `len` and
  65     /// `parent_idx` into the same 32-bit word, reducing space overhead.
  66     len: u16,
  67
  68     /// The arrays storing the actual data of the node. Only the first `len` elements of each
  69     /// array are initialized and valid.
  70     keys: [MaybeUninit<K>; CAPACITY],
  71     vals: [MaybeUninit<V>; CAPACITY],
  72 }
  73
  74 impl<K, V> LeafNode<K, V> {
  75     /// Creates a new `LeafNode`. Unsafe because all nodes should really be hidden behind
  76     /// `BoxedNode`, preventing accidental dropping of uninitialized keys and values.
  77     unsafe fn new() -> Self {
  78         LeafNode {
  79             // As a general policy, we leave fields uninitialized if they can be, as this should
  80             // be both slightly faster and easier to track in Valgrind.
  81             keys: [MaybeUninit::UNINIT; CAPACITY],
  82             vals: [MaybeUninit::UNINIT; CAPACITY],
  83             parent: ptr::null(),
  84             parent_idx: MaybeUninit::uninit(),
  85             len: 0,
  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 casted 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 struct InternalNode<K, V> {
  97     data: LeafNode<K, V>,
  98
  99     /// The pointers to the children of this node. `len + 1` of these are considered
 100     /// initialized and valid. Although during the process of `into_iter` or `drop`,
 101     /// some pointers are dangling while others still need to be traversed.
 102     edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B],
 103 }
 104
 105 impl<K, V> InternalNode<K, V> {
 106     /// Creates a new `InternalNode`.
 107     ///
 108     /// This is unsafe for two reasons. First, it returns an `InternalNode` by value, risking
 109     /// dropping of uninitialized fields. Second, an invariant of internal nodes is that `len + 1`
 110     /// edges are initialized and valid, meaning that even when the node is empty (having a
 111     /// `len` of 0), there must be one initialized and valid edge. This function does not set up
 112     /// such an edge.
 113     unsafe fn new() -> Self {
 114         InternalNode { data: unsafe { LeafNode::new() }, edges: [MaybeUninit::UNINIT; 2 * B] }
 115     }
 116 }
 117
 118 /// A managed, non-null pointer to a node. This is either an owned pointer to
 119 /// `LeafNode<K, V>` or an owned pointer to `InternalNode<K, V>`.
 120 ///
 121 /// However, `BoxedNode` contains no information as to which of the two types
 122 /// of nodes it actually contains, and, partially due to this lack of information,
 123 /// has no destructor.
 124 struct BoxedNode<K, V> {
 125     ptr: Unique<LeafNode<K, V>>,
 126 }
 127
 128 impl<K, V> BoxedNode<K, V> {
 129     fn from_leaf(node: Box<LeafNode<K, V>>) -> Self {
 130         BoxedNode { ptr: Box::into_unique(node) }
 131     }
 132
 133     fn from_internal(node: Box<InternalNode<K, V>>) -> Self {
 134         BoxedNode { ptr: Box::into_unique(node).cast() }
 135     }
 136
 137     unsafe fn from_ptr(ptr: NonNull<LeafNode<K, V>>) -> Self {
 138         BoxedNode { ptr: unsafe { Unique::new_unchecked(ptr.as_ptr()) } }
 139     }
 140
 141     fn as_ptr(&self) -> NonNull<LeafNode<K, V>> {
 142         NonNull::from(self.ptr)
 143     }
 144 }
 145
 146 /// An owned tree.
 147 ///
 148 /// Note that this does not have a destructor, and must be cleaned up manually.
 149 pub struct Root<K, V> {
 150     node: BoxedNode<K, V>,
 151     /// The number of levels below the root node.
 152     height: usize,
 153 }
 154
 155 unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> {}
 156 unsafe impl<K: Send, V: Send> Send for Root<K, V> {}
 157
 158 impl<K, V> Root<K, V> {
 159     /// Returns the number of levels below the root.
 160     pub fn height(&self) -> usize {
 161         self.height
 162     }
 163
 164     /// Returns a new owned tree, with its own root node that is initially empty.
 165     pub fn new_leaf() -> Self {
 166         Root { node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), height: 0 }
 167     }
 168
 169     /// Borrows and returns an immutable reference to the node owned by the root.
 170     pub fn node_as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> {
 171         NodeRef {
 172             height: self.height,
 173             node: self.node.as_ptr(),
 174             root: ptr::null(),
 175             _marker: PhantomData,
 176         }
 177     }
 178
 179     /// Borrows and returns a mutable reference to the node owned by the root.
 180     pub fn node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> {
 181         NodeRef {
 182             height: self.height,
 183             node: self.node.as_ptr(),
 184             root: self as *mut _,
 185             _marker: PhantomData,
 186         }
 187     }
 188
 189     pub fn into_ref(self) -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
 190         NodeRef {
 191             height: self.height,
 192             node: self.node.as_ptr(),
 193             root: ptr::null(),
 194             _marker: PhantomData,
 195         }
 196     }
 197
 198     /// Adds a new internal node with a single edge, pointing to the previous root, and make that
 199     /// new node the root. This increases the height by 1 and is the opposite of
 200     /// `pop_internal_level`.
 201     pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
 202         let mut new_node = Box::new(unsafe { InternalNode::new() });
 203         new_node.edges[0].write(unsafe { BoxedNode::from_ptr(self.node.as_ptr()) });
 204
 205         self.node = BoxedNode::from_internal(new_node);
 206         self.height += 1;
 207
 208         let mut ret = NodeRef {
 209             height: self.height,
 210             node: self.node.as_ptr(),
 211             root: self as *mut _,
 212             _marker: PhantomData,
 213         };
 214
 215         unsafe {
 216             ret.reborrow_mut().first_edge().correct_parent_link();
 217         }
 218
 219         ret
 220     }
 221
 222     /// Removes the internal root node, using its first child as the new root.
 223     /// As it is intended only to be called when the root has only one child,
 224     /// no cleanup is done on any of the other children of the root.
 225     /// This decreases the height by 1 and is the opposite of `push_internal_level`.
 226     /// Panics if there is no internal level, i.e. if the root is a leaf.
 227     pub fn pop_internal_level(&mut self) {
 228         assert!(self.height > 0);
 229
 230         let top = self.node.ptr;
 231
 232         self.node = unsafe {
 233             BoxedNode::from_ptr(
 234                 self.node_as_mut().cast_unchecked::<marker::Internal>().first_edge().descend().node,
 235             )
 236         };
 237         self.height -= 1;
 238         unsafe {
 239             (*self.node_as_mut().as_leaf_mut()).parent = ptr::null();
 240         }
 241
 242         unsafe {
 243             Global.dealloc(NonNull::from(top).cast(), Layout::new::<InternalNode<K, V>>());
 244         }
 245     }
 246 }
 247
 248 // N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType`
 249 // is `Mut`. This is technically wrong, but cannot result in any unsafety due to
 250 // internal use of `NodeRef` because we stay completely generic over `K` and `V`.
 251 // However, whenever a public type wraps `NodeRef`, make sure that it has the
 252 // correct variance.
 253 /// A reference to a node.
 254 ///
 255 /// This type has a number of parameters that controls how it acts:
 256 /// - `BorrowType`: This can be `Immut<'a>` or `Mut<'a>` for some `'a` or `Owned`.
 257 ///    When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`,
 258 ///    when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`,
 259 ///    and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`.
 260 /// - `K` and `V`: These control what types of things are stored in the nodes.
 261 /// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is
 262 ///   `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
 263 ///   `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
 264 ///   `NodeRef` could be pointing to either type of node.
 265 pub struct NodeRef<BorrowType, K, V, Type> {
 266     /// The number of levels below the node.
 267     height: usize,
 268     node: NonNull<LeafNode<K, V>>,
 269     // `root` is null unless the borrow type is `Mut`
 270     root: *const Root<K, V>,
 271     _marker: PhantomData<(BorrowType, Type)>,
 272 }
 273
 274 impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {}
 275 impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
 276     fn clone(&self) -> Self {
 277         *self
 278     }
 279 }
 280
 281 unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}
 282
 283 unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {}
 284 unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {}
 285 unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
 286
 287 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
 288     fn as_internal(&self) -> &InternalNode<K, V> {
 289         unsafe { &*(self.node.as_ptr() as *mut InternalNode<K, V>) }
 290     }
 291 }
 292
 293 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
 294     fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
 295         unsafe { &mut *(self.node.as_ptr() as *mut InternalNode<K, V>) }
 296     }
 297 }
 298
 299 impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
 300     /// Finds the length of the node. This is the number of keys or values. In an
 301     /// internal node, the number of edges is `len() + 1`.
 302     /// For any node, the number of possible edge handles is also `len() + 1`.
 303     /// Note that, despite being safe, calling this function can have the side effect
 304     /// of invalidating mutable references that unsafe code has created.
 305     pub fn len(&self) -> usize {
 306         self.as_leaf().len as usize
 307     }
 308
 309     /// Returns the height of this node in the whole tree. Zero height denotes the
 310     /// leaf level.
 311     pub fn height(&self) -> usize {
 312         self.height
 313     }
 314
 315     /// Temporarily takes out another, immutable reference to the same node.
 316     fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
 317         NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
 318     }
 319
 320     /// Exposes the leaf "portion" of any leaf or internal node.
 321     /// If the node is a leaf, this function simply opens up its data.
 322     /// If the node is an internal node, so not a leaf, it does have all the data a leaf has
 323     /// (header, keys and values), and this function exposes that.
 324     fn as_leaf(&self) -> &LeafNode<K, V> {
 325         // The node must be valid for at least the LeafNode portion.
 326         // This is not a reference in the NodeRef type because we don't know if
 327         // it should be unique or shared.
 328         unsafe { self.node.as_ref() }
 329     }
 330
 331     /// Borrows a view into the keys stored in the node.
 332     pub fn keys(&self) -> &[K] {
 333         self.reborrow().into_key_slice()
 334     }
 335
 336     /// Borrows a view into the values stored in the node.
 337     fn vals(&self) -> &[V] {
 338         self.reborrow().into_val_slice()
 339     }
 340
 341     /// Finds the parent of the current node. Returns `Ok(handle)` if the current
 342     /// node actually has a parent, where `handle` points to the edge of the parent
 343     /// that points to the current node. Returns `Err(self)` if the current node has
 344     /// no parent, giving back the original `NodeRef`.
 345     ///
 346     /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
 347     /// both, upon success, do nothing.
 348     pub fn ascend(
 349         self,
 350     ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
 351         let parent_as_leaf = self.as_leaf().parent as *const LeafNode<K, V>;
 352         if let Some(non_zero) = NonNull::new(parent_as_leaf as *mut _) {
 353             Ok(Handle {
 354                 node: NodeRef {
 355                     height: self.height + 1,
 356                     node: non_zero,
 357                     root: self.root,
 358                     _marker: PhantomData,
 359                 },
 360                 idx: unsafe { usize::from(*self.as_leaf().parent_idx.as_ptr()) },
 361                 _marker: PhantomData,
 362             })
 363         } else {
 364             Err(self)
 365         }
 366     }
 367
 368     pub fn first_edge(self) -> Handle<Self, marker::Edge> {
 369         unsafe { Handle::new_edge(self, 0) }
 370     }
 371
 372     pub fn last_edge(self) -> Handle<Self, marker::Edge> {
 373         let len = self.len();
 374         unsafe { Handle::new_edge(self, len) }
 375     }
 376
 377     /// Note that `self` must be nonempty.
 378     pub fn first_kv(self) -> Handle<Self, marker::KV> {
 379         let len = self.len();
 380         assert!(len > 0);
 381         unsafe { Handle::new_kv(self, 0) }
 382     }
 383
 384     /// Note that `self` must be nonempty.
 385     pub fn last_kv(self) -> Handle<Self, marker::KV> {
 386         let len = self.len();
 387         assert!(len > 0);
 388         unsafe { Handle::new_kv(self, len - 1) }
 389     }
 390 }
 391
 392 impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
 393     /// Similar to `ascend`, gets a reference to a node's parent node, but also
 394     /// deallocate the current node in the process. This is unsafe because the
 395     /// current node will still be accessible despite being deallocated.
 396     pub unsafe fn deallocate_and_ascend(
 397         self,
 398     ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> {
 399         let height = self.height;
 400         let node = self.node;
 401         let ret = self.ascend().ok();
 402         unsafe {
 403             Global.dealloc(
 404                 node.cast(),
 405                 if height > 0 {
 406                     Layout::new::<InternalNode<K, V>>()
 407                 } else {
 408                     Layout::new::<LeafNode<K, V>>()
 409                 },
 410             );
 411         }
 412         ret
 413     }
 414 }
 415
 416 impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
 417     /// Unsafely asserts to the compiler some static information about whether this
 418     /// node is a `Leaf` or an `Internal`.
 419     unsafe fn cast_unchecked<NewType>(self) -> NodeRef<marker::Mut<'a>, K, V, NewType> {
 420         NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
 421     }
 422
 423     /// Temporarily takes out another, mutable reference to the same node. Beware, as
 424     /// this method is very dangerous, doubly so since it may not immediately appear
 425     /// dangerous.
 426     ///
 427     /// Because mutable pointers can roam anywhere around the tree and can even (through
 428     /// `into_root_mut`) mess with the root of the tree, the result of `reborrow_mut`
 429     /// can easily be used to make the original mutable pointer dangling, or, in the case
 430     /// of a reborrowed handle, out of bounds.
 431     // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` that restricts
 432     // the use of `ascend` and `into_root_mut` on reborrowed pointers, preventing this unsafety.
 433     unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> {
 434         NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
 435     }
 436
 437     /// Exposes the leaf "portion" of any leaf or internal node for writing.
 438     /// If the node is a leaf, this function simply opens up its data.
 439     /// If the node is an internal node, so not a leaf, it does have all the data a leaf has
 440     /// (header, keys and values), and this function exposes that.
 441     ///
 442     /// Returns a raw ptr to avoid asserting exclusive access to the entire node.
 443     fn as_leaf_mut(&mut self) -> *mut LeafNode<K, V> {
 444         self.node.as_ptr()
 445     }
 446
 447     fn keys_mut(&mut self) -> &mut [K] {
 448         // SAFETY: the caller will not be able to call further methods on self
 449         // until the key slice reference is dropped, as we have unique access
 450         // for the lifetime of the borrow.
 451         unsafe { self.reborrow_mut().into_key_slice_mut() }
 452     }
 453
 454     fn vals_mut(&mut self) -> &mut [V] {
 455         // SAFETY: the caller will not be able to call further methods on self
 456         // until the value slice reference is dropped, as we have unique access
 457         // for the lifetime of the borrow.
 458         unsafe { self.reborrow_mut().into_val_slice_mut() }
 459     }
 460 }
 461
 462 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
 463     fn into_key_slice(self) -> &'a [K] {
 464         unsafe { slice::from_raw_parts(MaybeUninit::first_ptr(&self.as_leaf().keys), self.len()) }
 465     }
 466
 467     fn into_val_slice(self) -> &'a [V] {
 468         unsafe { slice::from_raw_parts(MaybeUninit::first_ptr(&self.as_leaf().vals), self.len()) }
 469     }
 470 }
 471
 472 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
 473     /// Gets a mutable reference to the root itself. This is useful primarily when the
 474     /// height of the tree needs to be adjusted. Never call this on a reborrowed pointer.
 475     pub fn into_root_mut(self) -> &'a mut Root<K, V> {
 476         unsafe { &mut *(self.root as *mut Root<K, V>) }
 477     }
 478
 479     fn into_key_slice_mut(mut self) -> &'a mut [K] {
 480         // SAFETY: The keys of a node must always be initialized up to length.
 481         unsafe {
 482             slice::from_raw_parts_mut(
 483                 MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).keys),
 484                 self.len(),
 485             )
 486         }
 487     }
 488
 489     fn into_val_slice_mut(mut self) -> &'a mut [V] {
 490         // SAFETY: The values of a node must always be initialized up to length.
 491         unsafe {
 492             slice::from_raw_parts_mut(
 493                 MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).vals),
 494                 self.len(),
 495             )
 496         }
 497     }
 498
 499     fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) {
 500         // We cannot use the getters here, because calling the second one
 501         // invalidates the reference returned by the first.
 502         // More precisely, it is the call to `len` that is the culprit,
 503         // because that creates a shared reference to the header, which *can*
 504         // overlap with the keys (and even the values, for ZST keys).
 505         let len = self.len();
 506         let leaf = self.as_leaf_mut();
 507         // SAFETY: The keys and values of a node must always be initialized up to length.
 508         let keys = unsafe {
 509             slice::from_raw_parts_mut(MaybeUninit::first_ptr_mut(&mut (*leaf).keys), len)
 510         };
 511         let vals = unsafe {
 512             slice::from_raw_parts_mut(MaybeUninit::first_ptr_mut(&mut (*leaf).vals), len)
 513         };
 514         (keys, vals)
 515     }
 516 }
 517
 518 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
 519     /// Adds a key/value pair to the end of the node.
 520     pub fn push(&mut self, key: K, val: V) {
 521         assert!(self.len() < CAPACITY);
 522
 523         let idx = self.len();
 524
 525         unsafe {
 526             ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
 527             ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
 528
 529             (*self.as_leaf_mut()).len += 1;
 530         }
 531     }
 532
 533     /// Adds a key/value pair to the beginning of the node.
 534     pub fn push_front(&mut self, key: K, val: V) {
 535         assert!(self.len() < CAPACITY);
 536
 537         unsafe {
 538             slice_insert(self.keys_mut(), 0, key);
 539             slice_insert(self.vals_mut(), 0, val);
 540
 541             (*self.as_leaf_mut()).len += 1;
 542         }
 543     }
 544 }
 545
 546 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
 547     /// Adds a key/value pair and an edge to go to the right of that pair to
 548     /// the end of the node.
 549     pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
 550         assert!(edge.height == self.height - 1);
 551         assert!(self.len() < CAPACITY);
 552
 553         let idx = self.len();
 554
 555         unsafe {
 556             ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
 557             ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
 558             self.as_internal_mut().edges.get_unchecked_mut(idx + 1).write(edge.node);
 559
 560             (*self.as_leaf_mut()).len += 1;
 561
 562             Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
 563         }
 564     }
 565
 566     // Unsafe because 'first' and 'after_last' must be in range
 567     unsafe fn correct_childrens_parent_links(&mut self, first: usize, after_last: usize) {
 568         debug_assert!(first <= self.len());
 569         debug_assert!(after_last <= self.len() + 1);
 570         for i in first..after_last {
 571             unsafe { Handle::new_edge(self.reborrow_mut(), i) }.correct_parent_link();
 572         }
 573     }
 574
 575     fn correct_all_childrens_parent_links(&mut self) {
 576         let len = self.len();
 577         unsafe { self.correct_childrens_parent_links(0, len + 1) };
 578     }
 579
 580     /// Adds a key/value pair and an edge to go to the left of that pair to
 581     /// the beginning of the node.
 582     pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
 583         assert!(edge.height == self.height - 1);
 584         assert!(self.len() < CAPACITY);
 585
 586         unsafe {
 587             slice_insert(self.keys_mut(), 0, key);
 588             slice_insert(self.vals_mut(), 0, val);
 589             slice_insert(
 590                 slice::from_raw_parts_mut(
 591                     MaybeUninit::first_ptr_mut(&mut self.as_internal_mut().edges),
 592                     self.len() + 1,
 593                 ),
 594                 0,
 595                 edge.node,
 596             );
 597
 598             (*self.as_leaf_mut()).len += 1;
 599
 600             self.correct_all_childrens_parent_links();
 601         }
 602     }
 603 }
 604
 605 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
 606     /// Removes a key/value pair from the end of this node and returns the pair.
 607     /// If this is an internal node, also removes the edge that was to the right
 608     /// of that pair and returns the orphaned node that this edge owned with its
 609     /// parent erased.
 610     pub fn pop(&mut self) -> (K, V, Option<Root<K, V>>) {
 611         assert!(self.len() > 0);
 612
 613         let idx = self.len() - 1;
 614
 615         unsafe {
 616             let key = ptr::read(self.keys().get_unchecked(idx));
 617             let val = ptr::read(self.vals().get_unchecked(idx));
 618             let edge = match self.reborrow_mut().force() {
 619                 ForceResult::Leaf(_) => None,
 620                 ForceResult::Internal(internal) => {
 621                     let edge =
 622                         ptr::read(internal.as_internal().edges.get_unchecked(idx + 1).as_ptr());
 623                     let mut new_root = Root { node: edge, height: internal.height - 1 };
 624                     (*new_root.node_as_mut().as_leaf_mut()).parent = ptr::null();
 625                     Some(new_root)
 626                 }
 627             };
 628
 629             (*self.as_leaf_mut()).len -= 1;
 630             (key, val, edge)
 631         }
 632     }
 633
 634     /// Removes a key/value pair from the beginning of this node. If this is an internal node,
 635     /// also removes the edge that was to the left of that pair.
 636     pub fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) {
 637         assert!(self.len() > 0);
 638
 639         let old_len = self.len();
 640
 641         unsafe {
 642             let key = slice_remove(self.keys_mut(), 0);
 643             let val = slice_remove(self.vals_mut(), 0);
 644             let edge = match self.reborrow_mut().force() {
 645                 ForceResult::Leaf(_) => None,
 646                 ForceResult::Internal(mut internal) => {
 647                     let edge = slice_remove(
 648                         slice::from_raw_parts_mut(
 649                             MaybeUninit::first_ptr_mut(&mut internal.as_internal_mut().edges),
 650                             old_len + 1,
 651                         ),
 652                         0,
 653                     );
 654
 655                     let mut new_root = Root { node: edge, height: internal.height - 1 };
 656                     (*new_root.node_as_mut().as_leaf_mut()).parent = ptr::null();
 657
 658                     for i in 0..old_len {
 659                         Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link();
 660                     }
 661
 662                     Some(new_root)
 663                 }
 664             };
 665
 666             (*self.as_leaf_mut()).len -= 1;
 667
 668             (key, val, edge)
 669         }
 670     }
 671
 672     fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) {
 673         (self.keys_mut().as_mut_ptr(), self.vals_mut().as_mut_ptr())
 674     }
 675 }
 676
 677 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
 678     /// Checks whether a node is an `Internal` node or a `Leaf` node.
 679     pub fn force(
 680         self,
 681     ) -> ForceResult<
 682         NodeRef<BorrowType, K, V, marker::Leaf>,
 683         NodeRef<BorrowType, K, V, marker::Internal>,
 684     > {
 685         if self.height == 0 {
 686             ForceResult::Leaf(NodeRef {
 687                 height: self.height,
 688                 node: self.node,
 689                 root: self.root,
 690                 _marker: PhantomData,
 691             })
 692         } else {
 693             ForceResult::Internal(NodeRef {
 694                 height: self.height,
 695                 node: self.node,
 696                 root: self.root,
 697                 _marker: PhantomData,
 698             })
 699         }
 700     }
 701 }
 702
 703 /// A reference to a specific key/value pair or edge within a node. The `Node` parameter
 704 /// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key/value
 705 /// pair) or `Edge` (signifying a handle on an edge).
 706 ///
 707 /// Note that even `Leaf` nodes can have `Edge` handles. Instead of representing a pointer to
 708 /// a child node, these represent the spaces where child pointers would go between the key/value
 709 /// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one
 710 /// to the left of the node, one between the two pairs, and one at the right of the node.
 711 pub struct Handle<Node, Type> {
 712     node: Node,
 713     idx: usize,
 714     _marker: PhantomData<Type>,
 715 }
 716
 717 impl<Node: Copy, Type> Copy for Handle<Node, Type> {}
 718 // We don't need the full generality of `#[derive(Clone)]`, as the only time `Node` will be
 719 // `Clone`able is when it is an immutable reference and therefore `Copy`.
 720 impl<Node: Copy, Type> Clone for Handle<Node, Type> {
 721     fn clone(&self) -> Self {
 722         *self
 723     }
 724 }
 725
 726 impl<Node, Type> Handle<Node, Type> {
 727     /// Retrieves the node that contains the edge or key/value pair this handle points to.
 728     pub fn into_node(self) -> Node {
 729         self.node
 730     }
 731
 732     /// Returns the position of this handle in the node.
 733     pub fn idx(&self) -> usize {
 734         self.idx
 735     }
 736 }
 737
 738 impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
 739     /// Creates a new handle to a key/value pair in `node`.
 740     /// Unsafe because the caller must ensure that `idx < node.len()`.
 741     pub unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
 742         debug_assert!(idx < node.len());
 743
 744         Handle { node, idx, _marker: PhantomData }
 745     }
 746
 747     pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
 748         unsafe { Handle::new_edge(self.node, self.idx) }
 749     }
 750
 751     pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
 752         unsafe { Handle::new_edge(self.node, self.idx + 1) }
 753     }
 754 }
 755
 756 impl<BorrowType, K, V, NodeType, HandleType> PartialEq
 757     for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
 758 {
 759     fn eq(&self, other: &Self) -> bool {
 760         self.node.node == other.node.node && self.idx == other.idx
 761     }
 762 }
 763
 764 impl<BorrowType, K, V, NodeType, HandleType> PartialOrd
 765     for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
 766 {
 767     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 768         if self.node.node == other.node.node { Some(self.idx.cmp(&other.idx)) } else { None }
 769     }
 770 }
 771
 772 impl<BorrowType, K, V, NodeType, HandleType>
 773     Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
 774 {
 775     /// Temporarily takes out another, immutable handle on the same location.
 776     pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> {
 777         // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
 778         Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
 779     }
 780 }
 781
 782 impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
 783     /// Temporarily takes out another, mutable handle on the same location. Beware, as
 784     /// this method is very dangerous, doubly so since it may not immediately appear
 785     /// dangerous.
 786     ///
 787     /// Because mutable pointers can roam anywhere around the tree and can even (through
 788     /// `into_root_mut`) mess with the root of the tree, the result of `reborrow_mut`
 789     /// can easily be used to make the original mutable pointer dangling, or, in the case
 790     /// of a reborrowed handle, out of bounds.
 791     // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` that restricts
 792     // the use of `ascend` and `into_root_mut` on reborrowed pointers, preventing this unsafety.
 793     pub unsafe fn reborrow_mut(
 794         &mut self,
 795     ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> {
 796         // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
 797         Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData }
 798     }
 799 }
 800
 801 impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
 802     /// Creates a new handle to an edge in `node`.
 803     /// Unsafe because the caller must ensure that `idx <= node.len()`.
 804     pub unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
 805         debug_assert!(idx <= node.len());
 806
 807         Handle { node, idx, _marker: PhantomData }
 808     }
 809
 810     pub fn left_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
 811         if self.idx > 0 {
 812             Ok(unsafe { Handle::new_kv(self.node, self.idx - 1) })
 813         } else {
 814             Err(self)
 815         }
 816     }
 817
 818     pub fn right_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
 819         if self.idx < self.node.len() {
 820             Ok(unsafe { Handle::new_kv(self.node, self.idx) })
 821         } else {
 822             Err(self)
 823         }
 824     }
 825 }
 826
 827 enum InsertionPlace {
 828     Left(usize),
 829     Right(usize),
 830 }
 831
 832 /// Given an edge index where we want to insert into a node filled to capacity,
 833 /// computes a sensible KV index of a split point and where to perform the insertion.
 834 /// The goal of the split point is for its key and value to end up in a parent node;
 835 /// the keys, values and edges to the left of the split point become the left child;
 836 /// the keys, values and edges to the right of the split point become the right child.
 837 fn splitpoint(edge_idx: usize) -> (usize, InsertionPlace) {
 838     debug_assert!(edge_idx <= CAPACITY);
 839     // Rust issue #74834 tries to explain these symmetric rules.
 840     match edge_idx {
 841         0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, InsertionPlace::Left(edge_idx)),
 842         EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Left(edge_idx)),
 843         EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Right(0)),
 844         _ => (KV_IDX_CENTER + 1, InsertionPlace::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))),
 845     }
 846 }
 847
 848 impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::Edge> {
 849     /// Helps implementations of `insert_fit` for a particular `NodeType`,
 850     /// by taking care of leaf data.
 851     /// Inserts a new key/value pair between the key/value pairs to the right and left of
 852     /// this edge. This method assumes that there is enough space in the node for the new
 853     /// pair to fit.
 854     fn leafy_insert_fit(&mut self, key: K, val: V) {
 855         // Necessary for correctness, but in a private module
 856         debug_assert!(self.node.len() < CAPACITY);
 857
 858         unsafe {
 859             slice_insert(self.node.keys_mut(), self.idx, key);
 860             slice_insert(self.node.vals_mut(), self.idx, val);
 861
 862             (*self.node.as_leaf_mut()).len += 1;
 863         }
 864     }
 865 }
 866
 867 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
 868     /// Inserts a new key/value pair between the key/value pairs to the right and left of
 869     /// this edge. This method assumes that there is enough space in the node for the new
 870     /// pair to fit.
 871     ///
 872     /// The returned pointer points to the inserted value.
 873     fn insert_fit(&mut self, key: K, val: V) -> *mut V {
 874         self.leafy_insert_fit(key, val);
 875         unsafe { self.node.vals_mut().get_unchecked_mut(self.idx) }
 876     }
 877 }
 878
 879 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
 880     /// Inserts a new key/value pair between the key/value pairs to the right and left of
 881     /// this edge. This method splits the node if there isn't enough room.
 882     ///
 883     /// The returned pointer points to the inserted value.
 884     fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
 885         if self.node.len() < CAPACITY {
 886             let ptr = self.insert_fit(key, val);
 887             let kv = unsafe { Handle::new_kv(self.node, self.idx) };
 888             (InsertResult::Fit(kv), ptr)
 889         } else {
 890             let (middle_kv_idx, insertion) = splitpoint(self.idx);
 891             let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
 892             let (mut left, k, v, mut right) = middle.split();
 893             let ptr = match insertion {
 894                 InsertionPlace::Left(insert_idx) => unsafe {
 895                     Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val)
 896                 },
 897                 InsertionPlace::Right(insert_idx) => unsafe {
 898                     Handle::new_edge(
 899                         right.node_as_mut().cast_unchecked::<marker::Leaf>(),
 900                         insert_idx,
 901                     )
 902                     .insert_fit(key, val)
 903                 },
 904             };
 905             (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), ptr)
 906         }
 907     }
 908 }
 909
 910 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
 911     /// Fixes the parent pointer and index in the child node below this edge. This is useful
 912     /// when the ordering of edges has been changed, such as in the various `insert` methods.
 913     fn correct_parent_link(mut self) {
 914         let idx = self.idx as u16;
 915         let ptr = self.node.as_internal_mut() as *mut _;
 916         let mut child = self.descend();
 917         unsafe {
 918             (*child.as_leaf_mut()).parent = ptr;
 919             (*child.as_leaf_mut()).parent_idx.write(idx);
 920         }
 921     }
 922
 923     /// Inserts a new key/value pair and an edge that will go to the right of that new pair
 924     /// between this edge and the key/value pair to the right of this edge. This method assumes
 925     /// that there is enough space in the node for the new pair to fit.
 926     fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
 927         // Necessary for correctness, but in an internal module
 928         debug_assert!(self.node.len() < CAPACITY);
 929         debug_assert!(edge.height == self.node.height - 1);
 930
 931         unsafe {
 932             self.leafy_insert_fit(key, val);
 933
 934             slice_insert(
 935                 slice::from_raw_parts_mut(
 936                     MaybeUninit::first_ptr_mut(&mut self.node.as_internal_mut().edges),
 937                     self.node.len(),
 938                 ),
 939                 self.idx + 1,
 940                 edge.node,
 941             );
 942
 943             for i in (self.idx + 1)..(self.node.len() + 1) {
 944                 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
 945             }
 946         }
 947     }
 948
 949     /// Inserts a new key/value pair and an edge that will go to the right of that new pair
 950     /// between this edge and the key/value pair to the right of this edge. This method splits
 951     /// the node if there isn't enough room.
 952     fn insert(
 953         mut self,
 954         key: K,
 955         val: V,
 956         edge: Root<K, V>,
 957     ) -> InsertResult<'a, K, V, marker::Internal> {
 958         assert!(edge.height == self.node.height - 1);
 959
 960         if self.node.len() < CAPACITY {
 961             self.insert_fit(key, val, edge);
 962             let kv = unsafe { Handle::new_kv(self.node, self.idx) };
 963             InsertResult::Fit(kv)
 964         } else {
 965             let (middle_kv_idx, insertion) = splitpoint(self.idx);
 966             let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
 967             let (mut left, k, v, mut right) = middle.split();
 968             match insertion {
 969                 InsertionPlace::Left(insert_idx) => unsafe {
 970                     Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val, edge);
 971                 },
 972                 InsertionPlace::Right(insert_idx) => unsafe {
 973                     Handle::new_edge(
 974                         right.node_as_mut().cast_unchecked::<marker::Internal>(),
 975                         insert_idx,
 976                     )
 977                     .insert_fit(key, val, edge);
 978                 },
 979             }
 980             InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right })
 981         }
 982     }
 983 }
 984
 985 impl<'a, K: 'a, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
 986     /// Inserts a new key/value pair between the key/value pairs to the right and left of
 987     /// this edge. This method splits the node if there isn't enough room, and tries to
 988     /// insert the split off portion into the parent node recursively, until the root is reached.
 989     ///
 990     /// If the returned result is a `Fit`, its handle's node can be this edge's node or an ancestor.
 991     /// If the returned result is a `Split`, the `left` field will be the root node.
 992     /// The returned pointer points to the inserted value.
 993     pub fn insert_recursing(
 994         self,
 995         key: K,
 996         value: V,
 997     ) -> (InsertResult<'a, K, V, marker::LeafOrInternal>, *mut V) {
 998         let (mut split, val_ptr) = match self.insert(key, value) {
 999             (InsertResult::Fit(handle), ptr) => {
1000                 return (InsertResult::Fit(handle.forget_node_type()), ptr);
1001             }
1002             (InsertResult::Split(split), val_ptr) => (split, val_ptr),
1003         };
1004
1005         loop {
1006             split = match split.left.ascend() {
1007                 Ok(parent) => match parent.insert(split.k, split.v, split.right) {
1008                     InsertResult::Fit(handle) => {
1009                         return (InsertResult::Fit(handle.forget_node_type()), val_ptr);
1010                     }
1011                     InsertResult::Split(split) => split,
1012                 },
1013                 Err(root) => {
1014                     return (InsertResult::Split(SplitResult { left: root, ..split }), val_ptr);
1015                 }
1016             };
1017         }
1018     }
1019 }
1020
1021 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
1022     /// Finds the node pointed to by this edge.
1023     ///
1024     /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
1025     /// both, upon success, do nothing.
1026     pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
1027         NodeRef {
1028             height: self.node.height - 1,
1029             node: unsafe {
1030                 (&*self.node.as_internal().edges.get_unchecked(self.idx).as_ptr()).as_ptr()
1031             },
1032             root: self.node.root,
1033             _marker: PhantomData,
1034         }
1035     }
1036 }
1037
1038 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
1039     pub fn into_kv(self) -> (&'a K, &'a V) {
1040         let keys = self.node.into_key_slice();
1041         let vals = self.node.into_val_slice();
1042         unsafe { (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx)) }
1043     }
1044 }
1045
1046 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1047     pub fn into_key_mut(self) -> &'a mut K {
1048         let keys = self.node.into_key_slice_mut();
1049         unsafe { keys.get_unchecked_mut(self.idx) }
1050     }
1051
1052     pub fn into_val_mut(self) -> &'a mut V {
1053         let vals = self.node.into_val_slice_mut();
1054         unsafe { vals.get_unchecked_mut(self.idx) }
1055     }
1056
1057     pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
1058         unsafe {
1059             let (keys, vals) = self.node.into_slices_mut();
1060             (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
1061         }
1062     }
1063 }
1064
1065 impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1066     pub fn kv_mut(&mut self) -> (&mut K, &mut V) {
1067         unsafe {
1068             let (keys, vals) = self.node.reborrow_mut().into_slices_mut();
1069             (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
1070         }
1071     }
1072 }
1073
1074 impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
1075     /// Helps implementations of `split` for a particular `NodeType`,
1076     /// by taking care of leaf data.
1077     fn leafy_split(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V, usize) {
1078         unsafe {
1079             let k = ptr::read(self.node.keys().get_unchecked(self.idx));
1080             let v = ptr::read(self.node.vals().get_unchecked(self.idx));
1081
1082             let new_len = self.node.len() - self.idx - 1;
1083
1084             ptr::copy_nonoverlapping(
1085                 self.node.keys().as_ptr().add(self.idx + 1),
1086                 new_node.keys.as_mut_ptr() as *mut K,
1087                 new_len,
1088             );
1089             ptr::copy_nonoverlapping(
1090                 self.node.vals().as_ptr().add(self.idx + 1),
1091                 new_node.vals.as_mut_ptr() as *mut V,
1092                 new_len,
1093             );
1094
1095             (*self.node.as_leaf_mut()).len = self.idx as u16;
1096             new_node.len = new_len as u16;
1097             (k, v, new_len)
1098         }
1099     }
1100 }
1101
1102 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
1103     /// Splits the underlying node into three parts:
1104     ///
1105     /// - The node is truncated to only contain the key/value pairs to the right of
1106     ///   this handle.
1107     /// - The key and value pointed to by this handle and extracted.
1108     /// - All the key/value pairs to the right of this handle are put into a newly
1109     ///   allocated node.
1110     pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) {
1111         unsafe {
1112             let mut new_node = Box::new(LeafNode::new());
1113
1114             let (k, v, _) = self.leafy_split(&mut new_node);
1115
1116             (self.node, k, v, Root { node: BoxedNode::from_leaf(new_node), height: 0 })
1117         }
1118     }
1119
1120     /// Removes the key/value pair pointed to by this handle and returns it, along with the edge
1121     /// that the key/value pair collapsed into.
1122     pub fn remove(
1123         mut self,
1124     ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
1125         unsafe {
1126             let k = slice_remove(self.node.keys_mut(), self.idx);
1127             let v = slice_remove(self.node.vals_mut(), self.idx);
1128             (*self.node.as_leaf_mut()).len -= 1;
1129             ((k, v), self.left_edge())
1130         }
1131     }
1132 }
1133
1134 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
1135     /// Splits the underlying node into three parts:
1136     ///
1137     /// - The node is truncated to only contain the edges and key/value pairs to the
1138     ///   right of this handle.
1139     /// - The key and value pointed to by this handle and extracted.
1140     /// - All the edges and key/value pairs to the right of this handle are put into
1141     ///   a newly allocated node.
1142     pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) {
1143         unsafe {
1144             let mut new_node = Box::new(InternalNode::new());
1145
1146             let (k, v, new_len) = self.leafy_split(&mut new_node.data);
1147             let height = self.node.height;
1148
1149             ptr::copy_nonoverlapping(
1150                 self.node.as_internal().edges.as_ptr().add(self.idx + 1),
1151                 new_node.edges.as_mut_ptr(),
1152                 new_len + 1,
1153             );
1154
1155             let mut new_root = Root { node: BoxedNode::from_internal(new_node), height };
1156
1157             for i in 0..(new_len + 1) {
1158                 Handle::new_edge(new_root.node_as_mut().cast_unchecked(), i).correct_parent_link();
1159             }
1160
1161             (self.node, k, v, new_root)
1162         }
1163     }
1164
1165     /// Returns `true` if it is valid to call `.merge()`, i.e., whether there is enough room in
1166     /// a node to hold the combination of the nodes to the left and right of this handle along
1167     /// with the key/value pair at this handle.
1168     pub fn can_merge(&self) -> bool {
1169         (self.reborrow().left_edge().descend().len()
1170             + self.reborrow().right_edge().descend().len()
1171             + 1)
1172             <= CAPACITY
1173     }
1174
1175     /// Combines the node immediately to the left of this handle, the key/value pair pointed
1176     /// to by this handle, and the node immediately to the right of this handle into one new
1177     /// child of the underlying node, returning an edge referencing that new child.
1178     ///
1179     /// Panics unless this edge `.can_merge()`.
1180     pub fn merge(
1181         mut self,
1182     ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
1183         let self1 = unsafe { ptr::read(&self) };
1184         let self2 = unsafe { ptr::read(&self) };
1185         let mut left_node = self1.left_edge().descend();
1186         let left_len = left_node.len();
1187         let right_node = self2.right_edge().descend();
1188         let right_len = right_node.len();
1189
1190         assert!(left_len + right_len < CAPACITY);
1191
1192         unsafe {
1193             ptr::write(
1194                 left_node.keys_mut().get_unchecked_mut(left_len),
1195                 slice_remove(self.node.keys_mut(), self.idx),
1196             );
1197             ptr::copy_nonoverlapping(
1198                 right_node.keys().as_ptr(),
1199                 left_node.keys_mut().as_mut_ptr().add(left_len + 1),
1200                 right_len,
1201             );
1202             ptr::write(
1203                 left_node.vals_mut().get_unchecked_mut(left_len),
1204                 slice_remove(self.node.vals_mut(), self.idx),
1205             );
1206             ptr::copy_nonoverlapping(
1207                 right_node.vals().as_ptr(),
1208                 left_node.vals_mut().as_mut_ptr().add(left_len + 1),
1209                 right_len,
1210             );
1211
1212             slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1);
1213             for i in self.idx + 1..self.node.len() {
1214                 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
1215             }
1216             (*self.node.as_leaf_mut()).len -= 1;
1217
1218             (*left_node.as_leaf_mut()).len += right_len as u16 + 1;
1219
1220             if self.node.height > 1 {
1221                 // SAFETY: the height of the nodes being merged is one below the height
1222                 // of the node of this edge, thus above zero, so they are internal.
1223                 let mut left_node = left_node.cast_unchecked();
1224                 let right_node = right_node.cast_unchecked();
1225                 ptr::copy_nonoverlapping(
1226                     right_node.reborrow().as_internal().edges.as_ptr(),
1227                     left_node.reborrow_mut().as_internal_mut().edges.as_mut_ptr().add(left_len + 1),
1228                     right_len + 1,
1229                 );
1230
1231                 for i in left_len + 1..left_len + right_len + 2 {
1232                     Handle::new_edge(left_node.reborrow_mut(), i).correct_parent_link();
1233                 }
1234
1235                 Global.dealloc(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
1236             } else {
1237                 Global.dealloc(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
1238             }
1239
1240             Handle::new_edge(self.node, self.idx)
1241         }
1242     }
1243
1244     /// This removes a key/value pair from the left child and places it in the key/value storage
1245     /// pointed to by this handle while pushing the old key/value pair of this handle into the right
1246     /// child.
1247     pub fn steal_left(&mut self) {
1248         unsafe {
1249             let (k, v, edge) = self.reborrow_mut().left_edge().descend().pop();
1250
1251             let k = mem::replace(self.kv_mut().0, k);
1252             let v = mem::replace(self.kv_mut().1, v);
1253
1254             match self.reborrow_mut().right_edge().descend().force() {
1255                 ForceResult::Leaf(mut leaf) => leaf.push_front(k, v),
1256                 ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap()),
1257             }
1258         }
1259     }
1260
1261     /// This removes a key/value pair from the right child and places it in the key/value storage
1262     /// pointed to by this handle while pushing the old key/value pair of this handle into the left
1263     /// child.
1264     pub fn steal_right(&mut self) {
1265         unsafe {
1266             let (k, v, edge) = self.reborrow_mut().right_edge().descend().pop_front();
1267
1268             let k = mem::replace(self.kv_mut().0, k);
1269             let v = mem::replace(self.kv_mut().1, v);
1270
1271             match self.reborrow_mut().left_edge().descend().force() {
1272                 ForceResult::Leaf(mut leaf) => leaf.push(k, v),
1273                 ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap()),
1274             }
1275         }
1276     }
1277
1278     /// This does stealing similar to `steal_left` but steals multiple elements at once.
1279     pub fn bulk_steal_left(&mut self, count: usize) {
1280         unsafe {
1281             let mut left_node = ptr::read(self).left_edge().descend();
1282             let left_len = left_node.len();
1283             let mut right_node = ptr::read(self).right_edge().descend();
1284             let right_len = right_node.len();
1285
1286             // Make sure that we may steal safely.
1287             assert!(right_len + count <= CAPACITY);
1288             assert!(left_len >= count);
1289
1290             let new_left_len = left_len - count;
1291
1292             // Move data.
1293             {
1294                 let left_kv = left_node.reborrow_mut().into_kv_pointers_mut();
1295                 let right_kv = right_node.reborrow_mut().into_kv_pointers_mut();
1296                 let parent_kv = {
1297                     let kv = self.kv_mut();
1298                     (kv.0 as *mut K, kv.1 as *mut V)
1299                 };
1300
1301                 // Make room for stolen elements in the right child.
1302                 ptr::copy(right_kv.0, right_kv.0.add(count), right_len);
1303                 ptr::copy(right_kv.1, right_kv.1.add(count), right_len);
1304
1305                 // Move elements from the left child to the right one.
1306                 move_kv(left_kv, new_left_len + 1, right_kv, 0, count - 1);
1307
1308                 // Move parent's key/value pair to the right child.
1309                 move_kv(parent_kv, 0, right_kv, count - 1, 1);
1310
1311                 // Move the left-most stolen pair to the parent.
1312                 move_kv(left_kv, new_left_len, parent_kv, 0, 1);
1313             }
1314
1315             (*left_node.reborrow_mut().as_leaf_mut()).len -= count as u16;
1316             (*right_node.reborrow_mut().as_leaf_mut()).len += count as u16;
1317
1318             match (left_node.force(), right_node.force()) {
1319                 (ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
1320                     // Make room for stolen edges.
1321                     let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr();
1322                     ptr::copy(right_edges, right_edges.add(count), right_len + 1);
1323                     right.correct_childrens_parent_links(count, count + right_len + 1);
1324
1325                     move_edges(left, new_left_len + 1, right, 0, count);
1326                 }
1327                 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1328                 _ => {
1329                     unreachable!();
1330                 }
1331             }
1332         }
1333     }
1334
1335     /// The symmetric clone of `bulk_steal_left`.
1336     pub fn bulk_steal_right(&mut self, count: usize) {
1337         unsafe {
1338             let mut left_node = ptr::read(self).left_edge().descend();
1339             let left_len = left_node.len();
1340             let mut right_node = ptr::read(self).right_edge().descend();
1341             let right_len = right_node.len();
1342
1343             // Make sure that we may steal safely.
1344             assert!(left_len + count <= CAPACITY);
1345             assert!(right_len >= count);
1346
1347             let new_right_len = right_len - count;
1348
1349             // Move data.
1350             {
1351                 let left_kv = left_node.reborrow_mut().into_kv_pointers_mut();
1352                 let right_kv = right_node.reborrow_mut().into_kv_pointers_mut();
1353                 let parent_kv = {
1354                     let kv = self.kv_mut();
1355                     (kv.0 as *mut K, kv.1 as *mut V)
1356                 };
1357
1358                 // Move parent's key/value pair to the left child.
1359                 move_kv(parent_kv, 0, left_kv, left_len, 1);
1360
1361                 // Move elements from the right child to the left one.
1362                 move_kv(right_kv, 0, left_kv, left_len + 1, count - 1);
1363
1364                 // Move the right-most stolen pair to the parent.
1365                 move_kv(right_kv, count - 1, parent_kv, 0, 1);
1366
1367                 // Fix right indexing
1368                 ptr::copy(right_kv.0.add(count), right_kv.0, new_right_len);
1369                 ptr::copy(right_kv.1.add(count), right_kv.1, new_right_len);
1370             }
1371
1372             (*left_node.reborrow_mut().as_leaf_mut()).len += count as u16;
1373             (*right_node.reborrow_mut().as_leaf_mut()).len -= count as u16;
1374
1375             match (left_node.force(), right_node.force()) {
1376                 (ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
1377                     move_edges(right.reborrow_mut(), 0, left, left_len + 1, count);
1378
1379                     // Fix right indexing.
1380                     let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr();
1381                     ptr::copy(right_edges.add(count), right_edges, new_right_len + 1);
1382                     right.correct_childrens_parent_links(0, new_right_len + 1);
1383                 }
1384                 (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1385                 _ => {
1386                     unreachable!();
1387                 }
1388             }
1389         }
1390     }
1391 }
1392
1393 unsafe fn move_kv<K, V>(
1394     source: (*mut K, *mut V),
1395     source_offset: usize,
1396     dest: (*mut K, *mut V),
1397     dest_offset: usize,
1398     count: usize,
1399 ) {
1400     unsafe {
1401         ptr::copy_nonoverlapping(source.0.add(source_offset), dest.0.add(dest_offset), count);
1402         ptr::copy_nonoverlapping(source.1.add(source_offset), dest.1.add(dest_offset), count);
1403     }
1404 }
1405
1406 // Source and destination must have the same height.
1407 unsafe fn move_edges<K, V>(
1408     mut source: NodeRef<marker::Mut<'_>, K, V, marker::Internal>,
1409     source_offset: usize,
1410     mut dest: NodeRef<marker::Mut<'_>, K, V, marker::Internal>,
1411     dest_offset: usize,
1412     count: usize,
1413 ) {
1414     let source_ptr = source.as_internal_mut().edges.as_mut_ptr();
1415     let dest_ptr = dest.as_internal_mut().edges.as_mut_ptr();
1416     unsafe {
1417         ptr::copy_nonoverlapping(source_ptr.add(source_offset), dest_ptr.add(dest_offset), count);
1418         dest.correct_childrens_parent_links(dest_offset, dest_offset + count);
1419     }
1420 }
1421
1422 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> {
1423     /// Removes any static information asserting that this node is a `Leaf` node.
1424     pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
1425         NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
1426     }
1427 }
1428
1429 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
1430     /// Removes any static information asserting that this node is an `Internal` node.
1431     pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
1432         NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
1433     }
1434 }
1435
1436 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1437     pub fn forget_node_type(
1438         self,
1439     ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1440         unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1441     }
1442 }
1443
1444 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
1445     pub fn forget_node_type(
1446         self,
1447     ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::Edge> {
1448         unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
1449     }
1450 }
1451
1452 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> {
1453     pub fn forget_node_type(
1454         self,
1455     ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
1456         unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
1457     }
1458 }
1459
1460 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV> {
1461     pub fn forget_node_type(
1462         self,
1463     ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
1464         unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
1465     }
1466 }
1467
1468 impl<BorrowType, K, V, HandleType>
1469     Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType>
1470 {
1471     /// Checks whether the underlying node is an `Internal` node or a `Leaf` node.
1472     pub fn force(
1473         self,
1474     ) -> ForceResult<
1475         Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>,
1476         Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>,
1477     > {
1478         match self.node.force() {
1479             ForceResult::Leaf(node) => {
1480                 ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData })
1481             }
1482             ForceResult::Internal(node) => {
1483                 ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData })
1484             }
1485         }
1486     }
1487 }
1488
1489 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> {
1490     /// Move the suffix after `self` from one node to another one. `right` must be empty.
1491     /// The first edge of `right` remains unchanged.
1492     pub fn move_suffix(
1493         &mut self,
1494         right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1495     ) {
1496         unsafe {
1497             let left_new_len = self.idx;
1498             let mut left_node = self.reborrow_mut().into_node();
1499
1500             let right_new_len = left_node.len() - left_new_len;
1501             let mut right_node = right.reborrow_mut();
1502
1503             assert!(right_node.len() == 0);
1504             assert!(left_node.height == right_node.height);
1505
1506             if right_new_len > 0 {
1507                 let left_kv = left_node.reborrow_mut().into_kv_pointers_mut();
1508                 let right_kv = right_node.reborrow_mut().into_kv_pointers_mut();
1509
1510                 move_kv(left_kv, left_new_len, right_kv, 0, right_new_len);
1511
1512                 (*left_node.reborrow_mut().as_leaf_mut()).len = left_new_len as u16;
1513                 (*right_node.reborrow_mut().as_leaf_mut()).len = right_new_len as u16;
1514
1515                 match (left_node.force(), right_node.force()) {
1516                     (ForceResult::Internal(left), ForceResult::Internal(right)) => {
1517                         move_edges(left, left_new_len + 1, right, 1, right_new_len);
1518                     }
1519                     (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {}
1520                     _ => {
1521                         unreachable!();
1522                     }
1523                 }
1524             }
1525         }
1526     }
1527 }
1528
1529 pub enum ForceResult<Leaf, Internal> {
1530     Leaf(Leaf),
1531     Internal(Internal),
1532 }
1533
1534 /// Result of insertion, when a node needed to expand beyond its capacity.
1535 /// Does not distinguish between `Leaf` and `Internal` because `Root` doesn't.
1536 pub struct SplitResult<'a, K, V> {
1537     // Altered node in existing tree with elements and edges that belong to the left of `k`.
1538     pub left: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>,
1539     // Some key and value split off, to be inserted elsewhere.
1540     pub k: K,
1541     pub v: V,
1542     // Owned, unattached, new node with elements and edges that belong to the right of `k`.
1543     pub right: Root<K, V>,
1544 }
1545
1546 pub enum InsertResult<'a, K, V, Type> {
1547     Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>),
1548     Split(SplitResult<'a, K, V>),
1549 }
1550
1551 pub mod marker {
1552     use core::marker::PhantomData;
1553
1554     pub enum Leaf {}
1555     pub enum Internal {}
1556     pub enum LeafOrInternal {}
1557
1558     pub enum Owned {}
1559     pub struct Immut<'a>(PhantomData<&'a ()>);
1560     pub struct Mut<'a>(PhantomData<&'a mut ()>);
1561
1562     pub enum KV {}
1563     pub enum Edge {}
1564 }
1565
1566 unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) {
1567     unsafe {
1568         ptr::copy(slice.as_ptr().add(idx), slice.as_mut_ptr().add(idx + 1), slice.len() - idx);
1569         ptr::write(slice.get_unchecked_mut(idx), val);
1570     }
1571 }
1572
1573 unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T {
1574     unsafe {
1575         let ret = ptr::read(slice.get_unchecked(idx));
1576         ptr::copy(slice.as_ptr().add(idx + 1), slice.as_mut_ptr().add(idx), slice.len() - idx - 1);
1577         ret
1578     }
1579 }
1580
1581 #[cfg(test)]
1582 mod tests;