src/liballoc/btree/node.rs

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