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