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