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