src/libcollections/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 module represents all the internal representation and logic for a B-Tree's node
  12 // with a safe interface, so that BTreeMap itself does not depend on any of these details.
  13
  14 pub use self::InsertionResult::*;
  15 pub use self::SearchResult::*;
  16 pub use self::ForceResult::*;
  17 pub use self::TraversalItem::*;
  18
  19 #[cfg(stage0)]
  20 use core::prelude::v1::*;
  21
  22 use core::cmp::Ordering::{Greater, Less, Equal};
  23 use core::intrinsics::arith_offset;
  24 use core::iter::Zip;
  25 use core::marker::PhantomData;
  26 use core::ops::{Deref, DerefMut, Index, IndexMut};
  27 use core::ptr::Unique;
  28 use core::{slice, mem, ptr, cmp, raw};
  29 use alloc::heap::{self, EMPTY};
  30
  31 use borrow::Borrow;
  32
  33 /// Represents the result of an Insertion: either the item fit, or the node had to split
  34 pub enum InsertionResult<K, V> {
  35     /// The inserted element fit
  36     Fit,
  37     /// The inserted element did not fit, so the node was split
  38     Split(K, V, Node<K, V>),
  39 }
  40
  41 /// Represents the result of a search for a key in a single node
  42 pub enum SearchResult<NodeRef> {
  43     /// The element was found at the given index
  44     Found(Handle<NodeRef, handle::KV, handle::LeafOrInternal>),
  45     /// The element wasn't found, but if it's anywhere, it must be beyond this edge
  46     GoDown(Handle<NodeRef, handle::Edge, handle::LeafOrInternal>),
  47 }
  48
  49 /// A B-Tree Node. We keep keys/edges/values separate to optimize searching for keys.
  50 #[unsafe_no_drop_flag]
  51 pub struct Node<K, V> {
  52     // To avoid the need for multiple allocations, we allocate a single buffer with enough space
  53     // for `capacity` keys, `capacity` values, and (in internal nodes) `capacity + 1` edges.
  54     // Despite this, we store three separate pointers to the three "chunks" of the buffer because
  55     // the performance drops significantly if the locations of the vals and edges need to be
  56     // recalculated upon access.
  57     //
  58     // These will never be null during normal usage of a `Node`. However, to avoid the need for a
  59     // drop flag, `Node::drop` zeroes `keys`, signaling that the `Node` has already been cleaned
  60     // up.
  61     keys: Unique<K>,
  62     vals: Unique<V>,
  63
  64     // In leaf nodes, this will be None, and no space will be allocated for edges.
  65     edges: Option<Unique<Node<K, V>>>,
  66
  67     // At any given time, there will be `_len` keys, `_len` values, and (in an internal node)
  68     // `_len + 1` edges. In a leaf node, there will never be any edges.
  69     //
  70     // Note: instead of accessing this field directly, please call the `len()` method, which should
  71     // be more stable in the face of representation changes.
  72     _len: usize,
  73
  74     // FIXME(gereeter) It shouldn't be necessary to store the capacity in every node, as it should
  75     // be constant throughout the tree. Once a solution to this is found, it might be possible to
  76     // also pass down the offsets into the buffer that vals and edges are stored at, removing the
  77     // need for those two pointers.
  78     //
  79     // Note: instead of accessing this field directly, please call the `capacity()` method, which
  80     // should be more stable in the face of representation changes.
  81     _capacity: usize,
  82 }
  83
  84 struct NodeSlice<'a, K: 'a, V: 'a> {
  85     keys: &'a [K],
  86     vals: &'a [V],
  87     pub edges: &'a [Node<K, V>],
  88     head_is_edge: bool,
  89     tail_is_edge: bool,
  90     has_edges: bool,
  91 }
  92
  93 struct MutNodeSlice<'a, K: 'a, V: 'a> {
  94     keys: &'a [K],
  95     vals: &'a mut [V],
  96     pub edges: &'a mut [Node<K, V>],
  97     head_is_edge: bool,
  98     tail_is_edge: bool,
  99     has_edges: bool,
 100 }
 101
 102 /// Rounds up to a multiple of a power of two. Returns the closest multiple
 103 /// of `target_alignment` that is higher or equal to `unrounded`.
 104 ///
 105 /// # Panics
 106 ///
 107 /// Fails if `target_alignment` is not a power of two.
 108 #[inline]
 109 fn round_up_to_next(unrounded: usize, target_alignment: usize) -> usize {
 110     assert!(target_alignment.is_power_of_two());
 111     (unrounded + target_alignment - 1) & !(target_alignment - 1)
 112 }
 113
 114 #[test]
 115 fn test_rounding() {
 116     assert_eq!(round_up_to_next(0, 4), 0);
 117     assert_eq!(round_up_to_next(1, 4), 4);
 118     assert_eq!(round_up_to_next(2, 4), 4);
 119     assert_eq!(round_up_to_next(3, 4), 4);
 120     assert_eq!(round_up_to_next(4, 4), 4);
 121     assert_eq!(round_up_to_next(5, 4), 8);
 122 }
 123
 124 // Returns a tuple of (val_offset, edge_offset),
 125 // from the start of a mallocated array.
 126 #[inline]
 127 fn calculate_offsets(keys_size: usize,
 128                      vals_size: usize, vals_align: usize,
 129                      edges_align: usize)
 130                      -> (usize, usize) {
 131     let vals_offset = round_up_to_next(keys_size, vals_align);
 132     let end_of_vals = vals_offset + vals_size;
 133
 134     let edges_offset = round_up_to_next(end_of_vals, edges_align);
 135
 136     (vals_offset, edges_offset)
 137 }
 138
 139 // Returns a tuple of (minimum required alignment, array_size),
 140 // from the start of a mallocated array.
 141 #[inline]
 142 fn calculate_allocation(keys_size: usize, keys_align: usize,
 143                         vals_size: usize, vals_align: usize,
 144                         edges_size: usize, edges_align: usize)
 145                         -> (usize, usize) {
 146     let (_, edges_offset) = calculate_offsets(keys_size,
 147                                               vals_size, vals_align,
 148                                                          edges_align);
 149     let end_of_edges = edges_offset + edges_size;
 150
 151     let min_align = cmp::max(keys_align, cmp::max(vals_align, edges_align));
 152
 153     (min_align, end_of_edges)
 154 }
 155
 156 #[test]
 157 fn test_offset_calculation() {
 158     assert_eq!(calculate_allocation(128, 8, 15, 1, 4, 4), (8, 148));
 159     assert_eq!(calculate_allocation(3, 1, 2, 1, 1, 1), (1, 6));
 160     assert_eq!(calculate_allocation(6, 2, 12, 4, 24, 8), (8, 48));
 161     assert_eq!(calculate_offsets(128, 15, 1, 4), (128, 144));
 162     assert_eq!(calculate_offsets(3, 2, 1, 1), (3, 5));
 163     assert_eq!(calculate_offsets(6, 12, 4, 8), (8, 24));
 164 }
 165
 166 fn calculate_allocation_generic<K, V>(capacity: usize, is_leaf: bool) -> (usize, usize) {
 167     let (keys_size, keys_align) = (capacity * mem::size_of::<K>(), mem::align_of::<K>());
 168     let (vals_size, vals_align) = (capacity * mem::size_of::<V>(), mem::align_of::<V>());
 169     let (edges_size, edges_align) = if is_leaf {
 170         (0, 1)
 171     } else {
 172         ((capacity + 1) * mem::size_of::<Node<K, V>>(), mem::align_of::<Node<K, V>>())
 173     };
 174
 175     calculate_allocation(
 176             keys_size, keys_align,
 177             vals_size, vals_align,
 178             edges_size, edges_align
 179     )
 180 }
 181
 182 fn calculate_offsets_generic<K, V>(capacity: usize, is_leaf: bool) -> (usize, usize) {
 183     let keys_size = capacity * mem::size_of::<K>();
 184     let vals_size = capacity * mem::size_of::<V>();
 185     let vals_align = mem::align_of::<V>();
 186     let edges_align = if is_leaf {
 187         1
 188     } else {
 189         mem::align_of::<Node<K, V>>()
 190     };
 191
 192     calculate_offsets(
 193             keys_size,
 194             vals_size, vals_align,
 195                        edges_align
 196     )
 197 }
 198
 199 /// An iterator over a slice that owns the elements of the slice but not the allocation.
 200 struct RawItems<T> {
 201     head: *const T,
 202     tail: *const T,
 203 }
 204
 205 impl<T> RawItems<T> {
 206     unsafe fn from_slice(slice: &[T]) -> RawItems<T> {
 207         RawItems::from_parts(slice.as_ptr(), slice.len())
 208     }
 209
 210     unsafe fn from_parts(ptr: *const T, len: usize) -> RawItems<T> {
 211         if mem::size_of::<T>() == 0 {
 212             RawItems {
 213                 head: ptr,
 214                 tail: arith_offset(ptr as *const i8, len as isize) as *const T,
 215             }
 216         } else {
 217             RawItems {
 218                 head: ptr,
 219                 tail: ptr.offset(len as isize),
 220             }
 221         }
 222     }
 223
 224     unsafe fn push(&mut self, val: T) {
 225         ptr::write(self.tail as *mut T, val);
 226
 227         if mem::size_of::<T>() == 0 {
 228             self.tail = arith_offset(self.tail as *const i8, 1) as *const T;
 229         } else {
 230             self.tail = self.tail.offset(1);
 231         }
 232     }
 233 }
 234
 235 impl<T> Iterator for RawItems<T> {
 236     type Item = T;
 237
 238     fn next(&mut self) -> Option<T> {
 239         if self.head == self.tail {
 240             None
 241         } else {
 242             unsafe {
 243                 let ret = Some(ptr::read(self.head));
 244
 245                 if mem::size_of::<T>() == 0 {
 246                     self.head = arith_offset(self.head as *const i8, 1) as *const T;
 247                 } else {
 248                     self.head = self.head.offset(1);
 249                 }
 250
 251                 ret
 252             }
 253         }
 254     }
 255 }
 256
 257 impl<T> DoubleEndedIterator for RawItems<T> {
 258     fn next_back(&mut self) -> Option<T> {
 259         if self.head == self.tail {
 260             None
 261         } else {
 262             unsafe {
 263                 if mem::size_of::<T>() == 0 {
 264                     self.tail = arith_offset(self.tail as *const i8, -1) as *const T;
 265                 } else {
 266                     self.tail = self.tail.offset(-1);
 267                 }
 268
 269                 Some(ptr::read(self.tail))
 270             }
 271         }
 272     }
 273 }
 274
 275 impl<T> Drop for RawItems<T> {
 276     fn drop(&mut self) {
 277         for _ in self.by_ref() {}
 278     }
 279 }
 280
 281 impl<K, V> Drop for Node<K, V> {
 282     fn drop(&mut self) {
 283         if self.keys.is_null() ||
 284             (unsafe { self.keys.get() as *const K as usize == mem::POST_DROP_USIZE })
 285         {
 286             // Since we have #[unsafe_no_drop_flag], we have to watch
 287             // out for the sentinel value being stored in self.keys. (Using
 288             // null is technically a violation of the `Unique`
 289             // requirements, though.)
 290             return;
 291         }
 292
 293         // Do the actual cleanup.
 294         unsafe {
 295             drop(RawItems::from_slice(self.keys()));
 296             drop(RawItems::from_slice(self.vals()));
 297             drop(RawItems::from_slice(self.edges()));
 298
 299             self.destroy();
 300         }
 301
 302         self.keys = unsafe { Unique::new(0 as *mut K) };
 303     }
 304 }
 305
 306 impl<K, V> Node<K, V> {
 307     /// Make a new internal node. The caller must initialize the result to fix the invariant that
 308     /// there are `len() + 1` edges.
 309     unsafe fn new_internal(capacity: usize) -> Node<K, V> {
 310         let (alignment, size) = calculate_allocation_generic::<K, V>(capacity, false);
 311
 312         let buffer = heap::allocate(size, alignment);
 313         if buffer.is_null() { ::alloc::oom(); }
 314
 315         let (vals_offset, edges_offset) = calculate_offsets_generic::<K, V>(capacity, false);
 316
 317         Node {
 318             keys: Unique::new(buffer as *mut K),
 319             vals: Unique::new(buffer.offset(vals_offset as isize) as *mut V),
 320             edges: Some(Unique::new(buffer.offset(edges_offset as isize) as *mut Node<K, V>)),
 321             _len: 0,
 322             _capacity: capacity,
 323         }
 324     }
 325
 326     /// Make a new leaf node
 327     fn new_leaf(capacity: usize) -> Node<K, V> {
 328         let (alignment, size) = calculate_allocation_generic::<K, V>(capacity, true);
 329
 330         let buffer = unsafe { heap::allocate(size, alignment) };
 331         if buffer.is_null() { ::alloc::oom(); }
 332
 333         let (vals_offset, _) = calculate_offsets_generic::<K, V>(capacity, true);
 334
 335         Node {
 336             keys: unsafe { Unique::new(buffer as *mut K) },
 337             vals: unsafe { Unique::new(buffer.offset(vals_offset as isize) as *mut V) },
 338             edges: None,
 339             _len: 0,
 340             _capacity: capacity,
 341         }
 342     }
 343
 344     unsafe fn destroy(&mut self) {
 345         let (alignment, size) =
 346                 calculate_allocation_generic::<K, V>(self.capacity(), self.is_leaf());
 347         heap::deallocate(*self.keys as *mut u8, size, alignment);
 348     }
 349
 350     #[inline]
 351     pub fn as_slices<'a>(&'a self) -> (&'a [K], &'a [V]) {
 352         unsafe {(
 353             slice::from_raw_parts(*self.keys, self.len()),
 354             slice::from_raw_parts(*self.vals, self.len()),
 355         )}
 356     }
 357
 358     #[inline]
 359     pub fn as_slices_mut<'a>(&'a mut self) -> (&'a mut [K], &'a mut [V]) {
 360         unsafe { mem::transmute(self.as_slices()) }
 361     }
 362
 363     #[inline]
 364     pub fn as_slices_internal<'b>(&'b self) -> NodeSlice<'b, K, V> {
 365         let is_leaf = self.is_leaf();
 366         let (keys, vals) = self.as_slices();
 367         let edges: &[_] = if self.is_leaf() {
 368             &[]
 369         } else {
 370             unsafe {
 371                 let data = match self.edges {
 372                     None => heap::EMPTY as *const Node<K,V>,
 373                     Some(ref p) => **p as *const Node<K,V>,
 374                 };
 375                 mem::transmute(raw::Slice {
 376                     data: data,
 377                     len: self.len() + 1
 378                 })
 379             }
 380         };
 381         NodeSlice {
 382             keys: keys,
 383             vals: vals,
 384             edges: edges,
 385             head_is_edge: true,
 386             tail_is_edge: true,
 387             has_edges: !is_leaf,
 388         }
 389     }
 390
 391     #[inline]
 392     pub fn as_slices_internal_mut<'b>(&'b mut self) -> MutNodeSlice<'b, K, V> {
 393         unsafe { mem::transmute(self.as_slices_internal()) }
 394     }
 395
 396     #[inline]
 397     pub fn keys<'a>(&'a self) -> &'a [K] {
 398         self.as_slices().0
 399     }
 400
 401     #[inline]
 402     pub fn keys_mut<'a>(&'a mut self) -> &'a mut [K] {
 403         self.as_slices_mut().0
 404     }
 405
 406     #[inline]
 407     pub fn vals<'a>(&'a self) -> &'a [V] {
 408         self.as_slices().1
 409     }
 410
 411     #[inline]
 412     pub fn vals_mut<'a>(&'a mut self) -> &'a mut [V] {
 413         self.as_slices_mut().1
 414     }
 415
 416     #[inline]
 417     pub fn edges<'a>(&'a self) -> &'a [Node<K, V>] {
 418         self.as_slices_internal().edges
 419     }
 420
 421     #[inline]
 422     pub fn edges_mut<'a>(&'a mut self) -> &'a mut [Node<K, V>] {
 423         self.as_slices_internal_mut().edges
 424     }
 425 }
 426
 427 // FIXME(gereeter) Write an efficient clone_from
 428 #[stable(feature = "rust1", since = "1.0.0")]
 429 impl<K: Clone, V: Clone> Clone for Node<K, V> {
 430     fn clone(&self) -> Node<K, V> {
 431         let mut ret = if self.is_leaf() {
 432             Node::new_leaf(self.capacity())
 433         } else {
 434             unsafe { Node::new_internal(self.capacity()) }
 435         };
 436
 437         unsafe {
 438             // For failure safety
 439             let mut keys = RawItems::from_parts(ret.keys().as_ptr(), 0);
 440             let mut vals = RawItems::from_parts(ret.vals().as_ptr(), 0);
 441             let mut edges = RawItems::from_parts(ret.edges().as_ptr(), 0);
 442
 443             for key in self.keys() {
 444                 keys.push(key.clone())
 445             }
 446             for val in self.vals() {
 447                 vals.push(val.clone())
 448             }
 449             for edge in self.edges() {
 450                 edges.push(edge.clone())
 451             }
 452
 453             mem::forget(keys);
 454             mem::forget(vals);
 455             mem::forget(edges);
 456
 457             ret._len = self.len();
 458         }
 459
 460         ret
 461     }
 462 }
 463
 464 /// A reference to something in the middle of a `Node`. There are two `Type`s of `Handle`s,
 465 /// namely `KV` handles, which point to key/value pairs, and `Edge` handles, which point to edges
 466 /// before or after key/value pairs. Methods are provided for removing pairs, inserting into edges,
 467 /// accessing the stored values, and moving around the `Node`.
 468 ///
 469 /// This handle is generic, and can take any sort of reference to a `Node`. The reason for this is
 470 /// two-fold. First of all, it reduces the amount of repetitive code, implementing functions that
 471 /// don't need mutability on both mutable and immutable references. Secondly and more importantly,
 472 /// this allows users of the `Handle` API to associate metadata with the reference. This is used in
 473 /// `BTreeMap` to give `Node`s temporary "IDs" that persist to when the `Node` is used in a
 474 /// `Handle`.
 475 ///
 476 /// # A note on safety
 477 ///
 478 /// Unfortunately, the extra power afforded by being generic also means that safety can technically
 479 /// be broken. For sensible implementations of `Deref` and `DerefMut`, these handles are perfectly
 480 /// safe. As long as repeatedly calling `.deref()` results in the same Node being returned each
 481 /// time, everything should work fine. However, if the `Deref` implementation swaps in multiple
 482 /// different nodes, then the indices that are assumed to be in bounds suddenly stop being so. For
 483 /// example:
 484 ///
 485 /// ```rust,ignore
 486 /// struct Nasty<'a> {
 487 ///     first: &'a Node<usize, usize>,
 488 ///     second: &'a Node<usize, usize>,
 489 ///     flag: &'a Cell<bool>,
 490 /// }
 491 ///
 492 /// impl<'a> Deref for Nasty<'a> {
 493 ///     type Target = Node<usize, usize>;
 494 ///
 495 ///     fn deref(&self) -> &Node<usize, usize> {
 496 ///         if self.flag.get() {
 497 ///             &*self.second
 498 ///         } else {
 499 ///             &*self.first
 500 ///         }
 501 ///     }
 502 /// }
 503 ///
 504 /// fn main() {
 505 ///     let flag = Cell::new(false);
 506 ///     let mut small_node = Node::make_leaf_root(3);
 507 ///     let mut large_node = Node::make_leaf_root(100);
 508 ///
 509 ///     for i in 0..100 {
 510 ///         // Insert to the end
 511 ///         large_node.edge_handle(i).insert_as_leaf(i, i);
 512 ///     }
 513 ///
 514 ///     let nasty = Nasty {
 515 ///         first: &large_node,
 516 ///         second: &small_node,
 517 ///         flag: &flag
 518 ///     }
 519 ///
 520 ///     // The handle points at index 75.
 521 ///     let handle = Node::search(nasty, 75);
 522 ///
 523 ///     // Now the handle still points at index 75, but on the small node, which has no index 75.
 524 ///     flag.set(true);
 525 ///
 526 ///     println!("Uninitialized memory: {:?}", handle.into_kv());
 527 /// }
 528 /// ```
 529 #[derive(Copy, Clone)]
 530 pub struct Handle<NodeRef, Type, NodeType> {
 531     node: NodeRef,
 532     index: usize,
 533     marker: PhantomData<(Type, NodeType)>,
 534 }
 535
 536 pub mod handle {
 537     // Handle types.
 538     pub enum KV {}
 539     pub enum Edge {}
 540
 541     // Handle node types.
 542     pub enum LeafOrInternal {}
 543     pub enum Leaf {}
 544     pub enum Internal {}
 545 }
 546
 547 impl<K: Ord, V> Node<K, V> {
 548     /// Searches for the given key in the node. If it finds an exact match,
 549     /// `Found` will be yielded with the matching index. If it doesn't find an exact match,
 550     /// `GoDown` will be yielded with the index of the subtree the key must lie in.
 551     pub fn search<Q: ?Sized, NodeRef: Deref<Target=Node<K, V>>>(node: NodeRef, key: &Q)
 552                   -> SearchResult<NodeRef> where K: Borrow<Q>, Q: Ord {
 553         // FIXME(Gankro): Tune when to search linear or binary based on B (and maybe K/V).
 554         // For the B configured as of this writing (B = 6), binary search was *significantly*
 555         // worse for usizes.
 556         match node.as_slices_internal().search_linear(key) {
 557             (index, true) => Found(Handle { node: node, index: index, marker: PhantomData }),
 558             (index, false) => GoDown(Handle { node: node, index: index, marker: PhantomData }),
 559         }
 560     }
 561 }
 562
 563 // Public interface
 564 impl <K, V> Node<K, V> {
 565     /// Make a leaf root from scratch
 566     pub fn make_leaf_root(b: usize) -> Node<K, V> {
 567         Node::new_leaf(capacity_from_b(b))
 568     }
 569
 570     /// Make an internal root and swap it with an old root
 571     pub fn make_internal_root(left_and_out: &mut Node<K,V>, b: usize, key: K, value: V,
 572             right: Node<K,V>) {
 573         let node = mem::replace(left_and_out, unsafe { Node::new_internal(capacity_from_b(b)) });
 574         left_and_out._len = 1;
 575         unsafe {
 576             ptr::write(left_and_out.keys_mut().get_unchecked_mut(0), key);
 577             ptr::write(left_and_out.vals_mut().get_unchecked_mut(0), value);
 578             ptr::write(left_and_out.edges_mut().get_unchecked_mut(0), node);
 579             ptr::write(left_and_out.edges_mut().get_unchecked_mut(1), right);
 580         }
 581     }
 582
 583     /// How many key-value pairs the node contains
 584     pub fn len(&self) -> usize {
 585         self._len
 586     }
 587
 588     /// Does the node not contain any key-value pairs
 589     pub fn is_empty(&self) -> bool { self.len() == 0 }
 590
 591     /// How many key-value pairs the node can fit
 592     pub fn capacity(&self) -> usize {
 593         self._capacity
 594     }
 595
 596     /// If the node has any children
 597     pub fn is_leaf(&self) -> bool {
 598         self.edges.is_none()
 599     }
 600
 601     /// if the node has too few elements
 602     pub fn is_underfull(&self) -> bool {
 603         self.len() < min_load_from_capacity(self.capacity())
 604     }
 605
 606     /// if the node cannot fit any more elements
 607     pub fn is_full(&self) -> bool {
 608         self.len() == self.capacity()
 609     }
 610 }
 611
 612 impl<K, V, NodeRef: Deref<Target=Node<K, V>>, Type, NodeType> Handle<NodeRef, Type, NodeType> {
 613     /// Returns a reference to the node that contains the pointed-to edge or key/value pair. This
 614     /// is very different from `edge` and `edge_mut` because those return children of the node
 615     /// returned by `node`.
 616     pub fn node(&self) -> &Node<K, V> {
 617         &*self.node
 618     }
 619 }
 620
 621 impl<K, V, NodeRef, Type, NodeType> Handle<NodeRef, Type, NodeType> where
 622     NodeRef: Deref<Target=Node<K, V>> + DerefMut,
 623 {
 624     /// Converts a handle into one that stores the same information using a raw pointer. This can
 625     /// be useful in conjunction with `from_raw` when the type system is insufficient for
 626     /// determining the lifetimes of the nodes.
 627     pub fn as_raw(&mut self) -> Handle<*mut Node<K, V>, Type, NodeType> {
 628         Handle {
 629             node: &mut *self.node as *mut _,
 630             index: self.index,
 631             marker: PhantomData,
 632         }
 633     }
 634 }
 635
 636 impl<K, V, Type, NodeType> Handle<*mut Node<K, V>, Type, NodeType> {
 637     /// Converts from a handle stored with a raw pointer, which isn't directly usable, to a handle
 638     /// stored with a reference. This is an unsafe inverse of `as_raw`, and together they allow
 639     /// unsafely extending the lifetime of the reference to the `Node`.
 640     pub unsafe fn from_raw<'a>(&'a self) -> Handle<&'a Node<K, V>, Type, NodeType> {
 641         Handle {
 642             node: &*self.node,
 643             index: self.index,
 644             marker: PhantomData,
 645         }
 646     }
 647
 648     /// Converts from a handle stored with a raw pointer, which isn't directly usable, to a handle
 649     /// stored with a mutable reference. This is an unsafe inverse of `as_raw`, and together they
 650     /// allow unsafely extending the lifetime of the reference to the `Node`.
 651     pub unsafe fn from_raw_mut<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, Type, NodeType> {
 652         Handle {
 653             node: &mut *self.node,
 654             index: self.index,
 655             marker: PhantomData,
 656         }
 657     }
 658 }
 659
 660 impl<'a, K: 'a, V: 'a> Handle<&'a Node<K, V>, handle::Edge, handle::Internal> {
 661     /// Turns the handle into a reference to the edge it points at. This is necessary because the
 662     /// returned pointer has a larger lifetime than what would be returned by `edge` or `edge_mut`,
 663     /// making it more suitable for moving down a chain of nodes.
 664     pub fn into_edge(self) -> &'a Node<K, V> {
 665         unsafe {
 666             self.node.edges().get_unchecked(self.index)
 667         }
 668     }
 669 }
 670
 671 impl<'a, K: 'a, V: 'a> Handle<&'a mut Node<K, V>, handle::Edge, handle::Internal> {
 672     /// Turns the handle into a mutable reference to the edge it points at. This is necessary
 673     /// because the returned pointer has a larger lifetime than what would be returned by
 674     /// `edge_mut`, making it more suitable for moving down a chain of nodes.
 675     pub fn into_edge_mut(self) -> &'a mut Node<K, V> {
 676         unsafe {
 677             self.node.edges_mut().get_unchecked_mut(self.index)
 678         }
 679     }
 680 }
 681
 682 impl<K, V, NodeRef: Deref<Target=Node<K, V>>> Handle<NodeRef, handle::Edge, handle::Internal> {
 683     // This doesn't exist because there are no uses for it,
 684     // but is fine to add, analogous to edge_mut.
 685     //
 686     // /// Returns a reference to the edge pointed-to by this handle. This should not be
 687     // /// confused with `node`, which references the parent node of what is returned here.
 688     // pub fn edge(&self) -> &Node<K, V>
 689 }
 690
 691 pub enum ForceResult<NodeRef, Type> {
 692     Leaf(Handle<NodeRef, Type, handle::Leaf>),
 693     Internal(Handle<NodeRef, Type, handle::Internal>)
 694 }
 695
 696 impl<K, V, NodeRef: Deref<Target=Node<K, V>>, Type> Handle<NodeRef, Type, handle::LeafOrInternal> {
 697     /// Figure out whether this handle is pointing to something in a leaf node or to something in
 698     /// an internal node, clarifying the type according to the result.
 699     pub fn force(self) -> ForceResult<NodeRef, Type> {
 700         if self.node.is_leaf() {
 701             Leaf(Handle {
 702                 node: self.node,
 703                 index: self.index,
 704                 marker: PhantomData,
 705             })
 706         } else {
 707             Internal(Handle {
 708                 node: self.node,
 709                 index: self.index,
 710                 marker: PhantomData,
 711             })
 712         }
 713     }
 714 }
 715 impl<K, V, NodeRef> Handle<NodeRef, handle::Edge, handle::Leaf> where
 716     NodeRef: Deref<Target=Node<K, V>> + DerefMut,
 717 {
 718     /// Tries to insert this key-value pair at the given index in this leaf node
 719     /// If the node is full, we have to split it.
 720     ///
 721     /// Returns a *mut V to the inserted value, because the caller may want this when
 722     /// they're done mutating the tree, but we don't want to borrow anything for now.
 723     pub fn insert_as_leaf(mut self, key: K, value: V) ->
 724             (InsertionResult<K, V>, *mut V) {
 725         if !self.node.is_full() {
 726             // The element can fit, just insert it
 727             (Fit, unsafe { self.node.insert_kv(self.index, key, value) as *mut _ })
 728         } else {
 729             // The element can't fit, this node is full. Split it into two nodes.
 730             let (new_key, new_val, mut new_right) = self.node.split();
 731             let left_len = self.node.len();
 732
 733             let ptr = unsafe {
 734                 if self.index <= left_len {
 735                     self.node.insert_kv(self.index, key, value)
 736                 } else {
 737                     // We need to subtract 1 because in splitting we took out new_key and new_val.
 738                     // Just being in the right node means we are past left_len k/v pairs in the
 739                     // left node and 1 k/v pair in the parent node.
 740                     new_right.insert_kv(self.index - left_len - 1, key, value)
 741                 }
 742             } as *mut _;
 743
 744             (Split(new_key, new_val, new_right), ptr)
 745         }
 746     }
 747 }
 748
 749 impl<K, V, NodeRef> Handle<NodeRef, handle::Edge, handle::Internal> where
 750     NodeRef: Deref<Target=Node<K, V>> + DerefMut,
 751 {
 752     /// Returns a mutable reference to the edge pointed-to by this handle. This should not be
 753     /// confused with `node`, which references the parent node of what is returned here.
 754     pub fn edge_mut(&mut self) -> &mut Node<K, V> {
 755         unsafe {
 756             self.node.edges_mut().get_unchecked_mut(self.index)
 757         }
 758     }
 759
 760     /// Tries to insert this key-value pair at the given index in this internal node
 761     /// If the node is full, we have to split it.
 762     pub fn insert_as_internal(mut self, key: K, value: V, right: Node<K, V>)
 763             -> InsertionResult<K, V> {
 764         if !self.node.is_full() {
 765             // The element can fit, just insert it
 766             unsafe {
 767                 self.node.insert_kv(self.index, key, value);
 768                 self.node.insert_edge(self.index + 1, right); // +1 to insert to the right
 769             }
 770             Fit
 771         } else {
 772             // The element can't fit, this node is full. Split it into two nodes.
 773             let (new_key, new_val, mut new_right) = self.node.split();
 774             let left_len = self.node.len();
 775
 776             if self.index <= left_len {
 777                 unsafe {
 778                     self.node.insert_kv(self.index, key, value);
 779                     self.node.insert_edge(self.index + 1, right); // +1 to insert to the right
 780                 }
 781             } else {
 782                 unsafe {
 783                     // The -1 here is for the same reason as in insert_as_internal - because we
 784                     // split, there are actually left_len + 1 k/v pairs before the right node, with
 785                     // the extra 1 being put in the parent.
 786                     new_right.insert_kv(self.index - left_len - 1, key, value);
 787                     new_right.insert_edge(self.index - left_len, right);
 788                 }
 789             }
 790
 791             Split(new_key, new_val, new_right)
 792         }
 793     }
 794
 795     /// Handle an underflow in this node's child. We favour handling "to the left" because we know
 796     /// we're empty, but our neighbour can be full. Handling to the left means when we choose to
 797     /// steal, we pop off the end of our neighbour (always fast) and "unshift" ourselves
 798     /// (always slow, but at least faster since we know we're half-empty).
 799     /// Handling "to the right" reverses these roles. Of course, we merge whenever possible
 800     /// because we want dense nodes, and merging is about equal work regardless of direction.
 801     pub fn handle_underflow(mut self) {
 802         unsafe {
 803             if self.index > 0 {
 804                 self.handle_underflow_to_left();
 805             } else {
 806                 self.handle_underflow_to_right();
 807             }
 808         }
 809     }
 810
 811     /// Right is underflowed. Tries to steal from left,
 812     /// but merges left and right if left is low too.
 813     unsafe fn handle_underflow_to_left(&mut self) {
 814         let left_len = self.node.edges()[self.index - 1].len();
 815         if left_len > min_load_from_capacity(self.node.capacity()) {
 816             self.left_kv().steal_rightward();
 817         } else {
 818             self.left_kv().merge_children();
 819         }
 820     }
 821
 822     /// Left is underflowed. Tries to steal from the right,
 823     /// but merges left and right if right is low too.
 824     unsafe fn handle_underflow_to_right(&mut self) {
 825         let right_len = self.node.edges()[self.index + 1].len();
 826         if right_len > min_load_from_capacity(self.node.capacity()) {
 827             self.right_kv().steal_leftward();
 828         } else {
 829             self.right_kv().merge_children();
 830         }
 831     }
 832 }
 833
 834 impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::Edge, NodeType> where
 835     NodeRef: Deref<Target=Node<K, V>> + DerefMut,
 836 {
 837     /// Gets the handle pointing to the key/value pair just to the left of the pointed-to edge.
 838     /// This is unsafe because the handle might point to the first edge in the node, which has no
 839     /// pair to its left.
 840     unsafe fn left_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
 841         Handle {
 842             node: &mut *self.node,
 843             index: self.index - 1,
 844             marker: PhantomData,
 845         }
 846     }
 847
 848     /// Gets the handle pointing to the key/value pair just to the right of the pointed-to edge.
 849     /// This is unsafe because the handle might point to the last edge in the node, which has no
 850     /// pair to its right.
 851     unsafe fn right_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
 852         Handle {
 853             node: &mut *self.node,
 854             index: self.index,
 855             marker: PhantomData,
 856         }
 857     }
 858 }
 859
 860 impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a Node<K, V>, handle::KV, NodeType> {
 861     /// Turns the handle into references to the key and value it points at. This is necessary
 862     /// because the returned pointers have larger lifetimes than what would be returned by `key`
 863     /// or `val`.
 864     pub fn into_kv(self) -> (&'a K, &'a V) {
 865         let (keys, vals) = self.node.as_slices();
 866         unsafe {
 867             (
 868                 keys.get_unchecked(self.index),
 869                 vals.get_unchecked(self.index)
 870             )
 871         }
 872     }
 873 }
 874
 875 impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
 876     /// Turns the handle into mutable references to the key and value it points at. This is
 877     /// necessary because the returned pointers have larger lifetimes than what would be returned
 878     /// by `key_mut` or `val_mut`.
 879     pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
 880         let (keys, vals) = self.node.as_slices_mut();
 881         unsafe {
 882             (
 883                 keys.get_unchecked_mut(self.index),
 884                 vals.get_unchecked_mut(self.index)
 885             )
 886         }
 887     }
 888
 889     /// Convert this handle into one pointing at the edge immediately to the left of the key/value
 890     /// pair pointed-to by this handle. This is useful because it returns a reference with larger
 891     /// lifetime than `left_edge`.
 892     pub fn into_left_edge(self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
 893         Handle {
 894             node: &mut *self.node,
 895             index: self.index,
 896             marker: PhantomData,
 897         }
 898     }
 899 }
 900
 901 impl<'a, K: 'a, V: 'a, NodeRef: Deref<Target=Node<K, V>> + 'a, NodeType> Handle<NodeRef, handle::KV,
 902                                                                          NodeType> {
 903     // These are fine to include, but are currently unneeded.
 904     //
 905     // /// Returns a reference to the key pointed-to by this handle. This doesn't return a
 906     // /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
 907     // /// handle.
 908     // pub fn key(&'a self) -> &'a K {
 909     //     unsafe { self.node.keys().get_unchecked(self.index) }
 910     // }
 911     //
 912     // /// Returns a reference to the value pointed-to by this handle. This doesn't return a
 913     // /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
 914     // /// handle.
 915     // pub fn val(&'a self) -> &'a V {
 916     //     unsafe { self.node.vals().get_unchecked(self.index) }
 917     // }
 918 }
 919
 920 impl<'a, K: 'a, V: 'a, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType> where
 921     NodeRef: 'a + Deref<Target=Node<K, V>> + DerefMut,
 922 {
 923     /// Returns a mutable reference to the key pointed-to by this handle. This doesn't return a
 924     /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
 925     /// handle.
 926     pub fn key_mut(&'a mut self) -> &'a mut K {
 927         unsafe { self.node.keys_mut().get_unchecked_mut(self.index) }
 928     }
 929
 930     /// Returns a mutable reference to the value pointed-to by this handle. This doesn't return a
 931     /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
 932     /// handle.
 933     pub fn val_mut(&'a mut self) -> &'a mut V {
 934         unsafe { self.node.vals_mut().get_unchecked_mut(self.index) }
 935     }
 936 }
 937
 938 impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType> where
 939     NodeRef: Deref<Target=Node<K, V>> + DerefMut,
 940 {
 941     /// Gets the handle pointing to the edge immediately to the left of the key/value pair pointed
 942     /// to by this handle.
 943     pub fn left_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
 944         Handle {
 945             node: &mut *self.node,
 946             index: self.index,
 947             marker: PhantomData,
 948         }
 949     }
 950
 951     /// Gets the handle pointing to the edge immediately to the right of the key/value pair pointed
 952     /// to by this handle.
 953     pub fn right_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
 954         Handle {
 955             node: &mut *self.node,
 956             index: self.index + 1,
 957             marker: PhantomData,
 958         }
 959     }
 960 }
 961
 962 impl<K, V, NodeRef> Handle<NodeRef, handle::KV, handle::Leaf> where
 963     NodeRef: Deref<Target=Node<K, V>> + DerefMut,
 964 {
 965     /// Removes the key/value pair at the handle's location.
 966     ///
 967     /// # Panics (in debug build)
 968     ///
 969     /// Panics if the node containing the pair is not a leaf node.
 970     pub fn remove_as_leaf(mut self) -> (K, V) {
 971         unsafe { self.node.remove_kv(self.index) }
 972     }
 973 }
 974
 975 impl<K, V, NodeRef> Handle<NodeRef, handle::KV, handle::Internal> where
 976     NodeRef: Deref<Target=Node<K, V>> + DerefMut
 977 {
 978     /// Steal! Stealing is roughly analogous to a binary tree rotation.
 979     /// In this case, we're "rotating" right.
 980     unsafe fn steal_rightward(&mut self) {
 981         // Take the biggest stuff off left
 982         let (mut key, mut val, edge) = {
 983             let mut left_handle = self.left_edge();
 984             let left = left_handle.edge_mut();
 985             let (key, val) = left.pop_kv();
 986             let edge = if left.is_leaf() {
 987                 None
 988             } else {
 989                 Some(left.pop_edge())
 990             };
 991
 992             (key, val, edge)
 993         };
 994
 995         // Swap the parent's separating key-value pair with left's
 996         mem::swap(&mut key, self.key_mut());
 997         mem::swap(&mut val, self.val_mut());
 998
 999         // Put them at the start of right
1000         let mut right_handle = self.right_edge();
1001         let right = right_handle.edge_mut();
1002         right.insert_kv(0, key, val);
1003         match edge {
1004             Some(edge) => right.insert_edge(0, edge),
1005             None => {}
1006         }
1007     }
1008
1009     /// Steal! Stealing is roughly analogous to a binary tree rotation.
1010     /// In this case, we're "rotating" left.
1011     unsafe fn steal_leftward(&mut self) {
1012         // Take the smallest stuff off right
1013         let (mut key, mut val, edge) = {
1014             let mut right_handle = self.right_edge();
1015             let right = right_handle.edge_mut();
1016             let (key, val) = right.remove_kv(0);
1017             let edge = if right.is_leaf() {
1018                 None
1019             } else {
1020                 Some(right.remove_edge(0))
1021             };
1022
1023             (key, val, edge)
1024         };
1025
1026         // Swap the parent's separating key-value pair with right's
1027         mem::swap(&mut key, self.key_mut());
1028         mem::swap(&mut val, self.val_mut());
1029
1030         // Put them at the end of left
1031         let mut left_handle = self.left_edge();
1032         let left = left_handle.edge_mut();
1033         left.push_kv(key, val);
1034         match edge {
1035             Some(edge) => left.push_edge(edge),
1036             None => {}
1037         }
1038     }
1039
1040     /// Merge! Smooshes left and right into one node, along with the key-value
1041     /// pair that separated them in their parent.
1042     unsafe fn merge_children(mut self) {
1043         // Permanently remove right's index, and the key-value pair that separates
1044         // left and right
1045         let (key, val) = self.node.remove_kv(self.index);
1046         let right = self.node.remove_edge(self.index + 1);
1047
1048         // Give left right's stuff.
1049         self.left_edge().edge_mut()
1050             .absorb(key, val, right);
1051     }
1052 }
1053
1054 impl<K, V> Node<K, V> {
1055     /// Returns the mutable handle pointing to the key/value pair at a given index.
1056     ///
1057     /// # Panics (in debug build)
1058     ///
1059     /// Panics if the given index is out of bounds.
1060     pub fn kv_handle(&mut self, index: usize) -> Handle<&mut Node<K, V>, handle::KV,
1061                                                        handle::LeafOrInternal> {
1062         // Necessary for correctness, but in a private module
1063         debug_assert!(index < self.len(), "kv_handle index out of bounds");
1064         Handle {
1065             node: self,
1066             index: index,
1067             marker: PhantomData,
1068         }
1069     }
1070
1071     pub fn iter<'a>(&'a self) -> Traversal<'a, K, V> {
1072         self.as_slices_internal().iter()
1073     }
1074
1075     pub fn iter_mut<'a>(&'a mut self) -> MutTraversal<'a, K, V> {
1076         self.as_slices_internal_mut().iter_mut()
1077     }
1078
1079     pub fn into_iter(self) -> MoveTraversal<K, V> {
1080         unsafe {
1081             let ret = MoveTraversal {
1082                 inner: MoveTraversalImpl {
1083                     keys: RawItems::from_slice(self.keys()),
1084                     vals: RawItems::from_slice(self.vals()),
1085                     edges: RawItems::from_slice(self.edges()),
1086
1087                     ptr: Unique::new(*self.keys as *mut u8),
1088                     capacity: self.capacity(),
1089                     is_leaf: self.is_leaf()
1090                 },
1091                 head_is_edge: true,
1092                 tail_is_edge: true,
1093                 has_edges: !self.is_leaf(),
1094             };
1095             mem::forget(self);
1096             ret
1097         }
1098     }
1099
1100     /// When a node has no keys or values and only a single edge, extract that edge.
1101     pub fn hoist_lone_child(&mut self) {
1102         // Necessary for correctness, but in a private module
1103         debug_assert!(self.is_empty());
1104         debug_assert!(!self.is_leaf());
1105
1106         unsafe {
1107             let ret = ptr::read(self.edges().get_unchecked(0));
1108             self.destroy();
1109             ptr::write(self, ret);
1110         }
1111     }
1112 }
1113
1114 // Vector functions (all unchecked)
1115 impl<K, V> Node<K, V> {
1116     // This must be followed by push_edge on an internal node.
1117     #[inline]
1118     unsafe fn push_kv(&mut self, key: K, val: V) {
1119         let len = self.len();
1120
1121         ptr::write(self.keys_mut().get_unchecked_mut(len), key);
1122         ptr::write(self.vals_mut().get_unchecked_mut(len), val);
1123
1124         self._len += 1;
1125     }
1126
1127     // This can only be called immediately after a call to push_kv.
1128     #[inline]
1129     unsafe fn push_edge(&mut self, edge: Node<K, V>) {
1130         let len = self.len();
1131
1132         ptr::write(self.edges_mut().get_unchecked_mut(len), edge);
1133     }
1134
1135     // This must be followed by insert_edge on an internal node.
1136     #[inline]
1137     unsafe fn insert_kv(&mut self, index: usize, key: K, val: V) -> &mut V {
1138         ptr::copy(
1139             self.keys().as_ptr().offset(index as isize),
1140             self.keys_mut().as_mut_ptr().offset(index as isize + 1),
1141             self.len() - index
1142         );
1143         ptr::copy(
1144             self.vals().as_ptr().offset(index as isize),
1145             self.vals_mut().as_mut_ptr().offset(index as isize + 1),
1146             self.len() - index
1147         );
1148
1149         ptr::write(self.keys_mut().get_unchecked_mut(index), key);
1150         ptr::write(self.vals_mut().get_unchecked_mut(index), val);
1151
1152         self._len += 1;
1153
1154         self.vals_mut().get_unchecked_mut(index)
1155     }
1156
1157     // This can only be called immediately after a call to insert_kv.
1158     #[inline]
1159     unsafe fn insert_edge(&mut self, index: usize, edge: Node<K, V>) {
1160         ptr::copy(
1161             self.edges().as_ptr().offset(index as isize),
1162             self.edges_mut().as_mut_ptr().offset(index as isize + 1),
1163             self.len() - index
1164         );
1165         ptr::write(self.edges_mut().get_unchecked_mut(index), edge);
1166     }
1167
1168     // This must be followed by pop_edge on an internal node.
1169     #[inline]
1170     unsafe fn pop_kv(&mut self) -> (K, V) {
1171         let key = ptr::read(self.keys().get_unchecked(self.len() - 1));
1172         let val = ptr::read(self.vals().get_unchecked(self.len() - 1));
1173
1174         self._len -= 1;
1175
1176         (key, val)
1177     }
1178
1179     // This can only be called immediately after a call to pop_kv.
1180     #[inline]
1181     unsafe fn pop_edge(&mut self) -> Node<K, V> {
1182         let edge = ptr::read(self.edges().get_unchecked(self.len() + 1));
1183
1184         edge
1185     }
1186
1187     // This must be followed by remove_edge on an internal node.
1188     #[inline]
1189     unsafe fn remove_kv(&mut self, index: usize) -> (K, V) {
1190         let key = ptr::read(self.keys().get_unchecked(index));
1191         let val = ptr::read(self.vals().get_unchecked(index));
1192
1193         ptr::copy(
1194             self.keys().as_ptr().offset(index as isize + 1),
1195             self.keys_mut().as_mut_ptr().offset(index as isize),
1196             self.len() - index - 1
1197         );
1198         ptr::copy(
1199             self.vals().as_ptr().offset(index as isize + 1),
1200             self.vals_mut().as_mut_ptr().offset(index as isize),
1201             self.len() - index - 1
1202         );
1203
1204         self._len -= 1;
1205
1206         (key, val)
1207     }
1208
1209     // This can only be called immediately after a call to remove_kv.
1210     #[inline]
1211     unsafe fn remove_edge(&mut self, index: usize) -> Node<K, V> {
1212         let edge = ptr::read(self.edges().get_unchecked(index));
1213
1214         ptr::copy(
1215             self.edges().as_ptr().offset(index as isize + 1),
1216             self.edges_mut().as_mut_ptr().offset(index as isize),
1217             // index can be == len+1, so do the +1 first to avoid underflow.
1218             (self.len() + 1) - index
1219         );
1220
1221         edge
1222     }
1223 }
1224
1225 // Private implementation details
1226 impl<K, V> Node<K, V> {
1227     /// Node is full, so split it into two nodes, and yield the middle-most key-value pair
1228     /// because we have one too many, and our parent now has one too few
1229     fn split(&mut self) -> (K, V, Node<K, V>) {
1230         // Necessary for correctness, but in a private function
1231         debug_assert!(!self.is_empty());
1232
1233         let mut right = if self.is_leaf() {
1234             Node::new_leaf(self.capacity())
1235         } else {
1236             unsafe { Node::new_internal(self.capacity()) }
1237         };
1238
1239         unsafe {
1240             right._len = self.len() / 2;
1241             let right_offset = self.len() - right.len();
1242             ptr::copy_nonoverlapping(
1243                 self.keys().as_ptr().offset(right_offset as isize),
1244                 right.keys_mut().as_mut_ptr(),
1245                 right.len()
1246             );
1247             ptr::copy_nonoverlapping(
1248                 self.vals().as_ptr().offset(right_offset as isize),
1249                 right.vals_mut().as_mut_ptr(),
1250                 right.len()
1251             );
1252             if !self.is_leaf() {
1253                 ptr::copy_nonoverlapping(
1254                     self.edges().as_ptr().offset(right_offset as isize),
1255                     right.edges_mut().as_mut_ptr(),
1256                     right.len() + 1
1257                 );
1258             }
1259
1260             let key = ptr::read(self.keys().get_unchecked(right_offset - 1));
1261             let val = ptr::read(self.vals().get_unchecked(right_offset - 1));
1262
1263             self._len = right_offset - 1;
1264
1265             (key, val, right)
1266         }
1267     }
1268
1269     /// Take all the values from right, separated by the given key and value
1270     fn absorb(&mut self, key: K, val: V, mut right: Node<K, V>) {
1271         // Necessary for correctness, but in a private function
1272         // Just as a sanity check, make sure we can fit this guy in
1273         debug_assert!(self.len() + right.len() <= self.capacity());
1274         debug_assert!(self.is_leaf() == right.is_leaf());
1275
1276         unsafe {
1277             let old_len = self.len();
1278             self._len += right.len() + 1;
1279
1280             ptr::write(self.keys_mut().get_unchecked_mut(old_len), key);
1281             ptr::write(self.vals_mut().get_unchecked_mut(old_len), val);
1282
1283             ptr::copy_nonoverlapping(
1284                 right.keys().as_ptr(),
1285                 self.keys_mut().as_mut_ptr().offset(old_len as isize + 1),
1286                 right.len()
1287             );
1288             ptr::copy_nonoverlapping(
1289                 right.vals().as_ptr(),
1290                 self.vals_mut().as_mut_ptr().offset(old_len as isize + 1),
1291                 right.len()
1292             );
1293             if !self.is_leaf() {
1294                 ptr::copy_nonoverlapping(
1295                     right.edges().as_ptr(),
1296                     self.edges_mut().as_mut_ptr().offset(old_len as isize + 1),
1297                     right.len() + 1
1298                 );
1299             }
1300
1301             right.destroy();
1302             mem::forget(right);
1303         }
1304     }
1305 }
1306
1307 /// Get the capacity of a node from the order of the parent B-Tree
1308 fn capacity_from_b(b: usize) -> usize {
1309     2 * b - 1
1310 }
1311
1312 /// Get the minimum load of a node from its capacity
1313 fn min_load_from_capacity(cap: usize) -> usize {
1314     // B - 1
1315     cap / 2
1316 }
1317
1318 /// A trait for pairs of `Iterator`s, one over edges and the other over key/value pairs. This is
1319 /// necessary, as the `MoveTraversalImpl` needs to have a destructor that deallocates the `Node`,
1320 /// and a pair of `Iterator`s would require two independent destructors.
1321 trait TraversalImpl {
1322     type Item;
1323     type Edge;
1324
1325     fn next_kv(&mut self) -> Option<Self::Item>;
1326     fn next_kv_back(&mut self) -> Option<Self::Item>;
1327
1328     fn next_edge(&mut self) -> Option<Self::Edge>;
1329     fn next_edge_back(&mut self) -> Option<Self::Edge>;
1330 }
1331
1332 /// A `TraversalImpl` that actually is backed by two iterators. This works in the non-moving case,
1333 /// as no deallocation needs to be done.
1334 #[derive(Clone)]
1335 struct ElemsAndEdges<Elems, Edges>(Elems, Edges);
1336
1337 impl<K, V, E, Elems: DoubleEndedIterator, Edges: DoubleEndedIterator>
1338         TraversalImpl for ElemsAndEdges<Elems, Edges>
1339     where Elems : Iterator<Item=(K, V)>, Edges : Iterator<Item=E>
1340 {
1341     type Item = (K, V);
1342     type Edge = E;
1343
1344     fn next_kv(&mut self) -> Option<(K, V)> { self.0.next() }
1345     fn next_kv_back(&mut self) -> Option<(K, V)> { self.0.next_back() }
1346
1347     fn next_edge(&mut self) -> Option<E> { self.1.next() }
1348     fn next_edge_back(&mut self) -> Option<E> { self.1.next_back() }
1349 }
1350
1351 /// A `TraversalImpl` taking a `Node` by value.
1352 struct MoveTraversalImpl<K, V> {
1353     keys: RawItems<K>,
1354     vals: RawItems<V>,
1355     edges: RawItems<Node<K, V>>,
1356
1357     // For deallocation when we are done iterating.
1358     ptr: Unique<u8>,
1359     capacity: usize,
1360     is_leaf: bool
1361 }
1362
1363 unsafe impl<K: Sync, V: Sync> Sync for MoveTraversalImpl<K, V> {}
1364 unsafe impl<K: Send, V: Send> Send for MoveTraversalImpl<K, V> {}
1365
1366 impl<K, V> TraversalImpl for MoveTraversalImpl<K, V> {
1367     type Item = (K, V);
1368     type Edge = Node<K, V>;
1369
1370     fn next_kv(&mut self) -> Option<(K, V)> {
1371         match (self.keys.next(), self.vals.next()) {
1372             (Some(k), Some(v)) => Some((k, v)),
1373             _ => None
1374         }
1375     }
1376
1377     fn next_kv_back(&mut self) -> Option<(K, V)> {
1378         match (self.keys.next_back(), self.vals.next_back()) {
1379             (Some(k), Some(v)) => Some((k, v)),
1380             _ => None
1381         }
1382     }
1383
1384     fn next_edge(&mut self) -> Option<Node<K, V>> {
1385         // Necessary for correctness, but in a private module
1386         debug_assert!(!self.is_leaf);
1387         self.edges.next()
1388     }
1389
1390     fn next_edge_back(&mut self) -> Option<Node<K, V>> {
1391         // Necessary for correctness, but in a private module
1392         debug_assert!(!self.is_leaf);
1393         self.edges.next_back()
1394     }
1395 }
1396
1397 impl<K, V> Drop for MoveTraversalImpl<K, V> {
1398     fn drop(&mut self) {
1399         // We need to cleanup the stored values manually, as the RawItems destructor would run
1400         // after our deallocation.
1401         for _ in self.keys.by_ref() {}
1402         for _ in self.vals.by_ref() {}
1403         for _ in self.edges.by_ref() {}
1404
1405         let (alignment, size) =
1406                 calculate_allocation_generic::<K, V>(self.capacity, self.is_leaf);
1407         unsafe { heap::deallocate(*self.ptr, size, alignment) };
1408     }
1409 }
1410
1411 /// An abstraction over all the different kinds of traversals a node supports
1412 #[derive(Clone)]
1413 struct AbsTraversal<Impl> {
1414     inner: Impl,
1415     head_is_edge: bool,
1416     tail_is_edge: bool,
1417     has_edges: bool,
1418 }
1419
1420 /// A single atomic step in a traversal.
1421 pub enum TraversalItem<K, V, E> {
1422     /// An element is visited. This isn't written as `Elem(K, V)` just because `opt.map(Elem)`
1423     /// requires the function to take a single argument. (Enum constructors are functions.)
1424     Elem((K, V)),
1425     /// An edge is followed.
1426     Edge(E),
1427 }
1428
1429 /// A traversal over a node's entries and edges
1430 pub type Traversal<'a, K, V> = AbsTraversal<ElemsAndEdges<Zip<slice::Iter<'a, K>,
1431                                                               slice::Iter<'a, V>>,
1432                                                           slice::Iter<'a, Node<K, V>>>>;
1433
1434 /// A mutable traversal over a node's entries and edges
1435 pub type MutTraversal<'a, K, V> = AbsTraversal<ElemsAndEdges<Zip<slice::Iter<'a, K>,
1436                                                                  slice::IterMut<'a, V>>,
1437                                                              slice::IterMut<'a, Node<K, V>>>>;
1438
1439 /// An owning traversal over a node's entries and edges
1440 pub type MoveTraversal<K, V> = AbsTraversal<MoveTraversalImpl<K, V>>;
1441
1442
1443 impl<K, V, E, Impl> Iterator for AbsTraversal<Impl>
1444         where Impl: TraversalImpl<Item=(K, V), Edge=E> {
1445     type Item = TraversalItem<K, V, E>;
1446
1447     fn next(&mut self) -> Option<TraversalItem<K, V, E>> {
1448         self.next_edge_item().map(Edge).or_else(||
1449             self.next_kv_item().map(Elem)
1450         )
1451     }
1452 }
1453
1454 impl<K, V, E, Impl> DoubleEndedIterator for AbsTraversal<Impl>
1455         where Impl: TraversalImpl<Item=(K, V), Edge=E> {
1456     fn next_back(&mut self) -> Option<TraversalItem<K, V, E>> {
1457         self.next_edge_item_back().map(Edge).or_else(||
1458             self.next_kv_item_back().map(Elem)
1459         )
1460     }
1461 }
1462
1463 impl<K, V, E, Impl> AbsTraversal<Impl>
1464         where Impl: TraversalImpl<Item=(K, V), Edge=E> {
1465     /// Advances the iterator and returns the item if it's an edge. Returns None
1466     /// and does nothing if the first item is not an edge.
1467     pub fn next_edge_item(&mut self) -> Option<E> {
1468         // NB. `&& self.has_edges` might be redundant in this condition.
1469         let edge = if self.head_is_edge && self.has_edges {
1470             self.inner.next_edge()
1471         } else {
1472             None
1473         };
1474         self.head_is_edge = false;
1475         edge
1476     }
1477
1478     /// Advances the iterator and returns the item if it's an edge. Returns None
1479     /// and does nothing if the last item is not an edge.
1480     pub fn next_edge_item_back(&mut self) -> Option<E> {
1481         let edge = if self.tail_is_edge && self.has_edges {
1482             self.inner.next_edge_back()
1483         } else {
1484             None
1485         };
1486         self.tail_is_edge = false;
1487         edge
1488     }
1489
1490     /// Advances the iterator and returns the item if it's a key-value pair. Returns None
1491     /// and does nothing if the first item is not a key-value pair.
1492     pub fn next_kv_item(&mut self) -> Option<(K, V)> {
1493         if !self.head_is_edge {
1494             self.head_is_edge = true;
1495             self.inner.next_kv()
1496         } else {
1497             None
1498         }
1499     }
1500
1501     /// Advances the iterator and returns the item if it's a key-value pair. Returns None
1502     /// and does nothing if the last item is not a key-value pair.
1503     pub fn next_kv_item_back(&mut self) -> Option<(K, V)> {
1504         if !self.tail_is_edge {
1505             self.tail_is_edge = true;
1506             self.inner.next_kv_back()
1507         } else {
1508             None
1509         }
1510     }
1511 }
1512
1513 macro_rules! node_slice_impl {
1514     ($NodeSlice:ident, $Traversal:ident,
1515      $as_slices_internal:ident, $index:ident, $iter:ident) => {
1516         impl<'a, K: Ord + 'a, V: 'a> $NodeSlice<'a, K, V> {
1517             /// Performs linear search in a slice. Returns a tuple of (index, is_exact_match).
1518             fn search_linear<Q: ?Sized>(&self, key: &Q) -> (usize, bool)
1519                     where K: Borrow<Q>, Q: Ord {
1520                 for (i, k) in self.keys.iter().enumerate() {
1521                     match key.cmp(k.borrow()) {
1522                         Greater => {},
1523                         Equal => return (i, true),
1524                         Less => return (i, false),
1525                     }
1526                 }
1527                 (self.keys.len(), false)
1528             }
1529
1530             /// Returns a sub-slice with elements starting with `min_key`.
1531             pub fn slice_from<Q: ?Sized + Ord>(self, min_key: &Q) -> $NodeSlice<'a, K, V> where
1532                 K: Borrow<Q>,
1533             {
1534                 //  _______________
1535                 // |_1_|_3_|_5_|_7_|
1536                 // |   |   |   |   |
1537                 // 0 0 1 1 2 2 3 3 4  index
1538                 // |   |   |   |   |
1539                 // \___|___|___|___/  slice_from(&0); pos = 0
1540                 //     \___|___|___/  slice_from(&2); pos = 1
1541                 //     |___|___|___/  slice_from(&3); pos = 1; result.head_is_edge = false
1542                 //         \___|___/  slice_from(&4); pos = 2
1543                 //             \___/  slice_from(&6); pos = 3
1544                 //                \|/ slice_from(&999); pos = 4
1545                 let (pos, pos_is_kv) = self.search_linear(min_key);
1546                 $NodeSlice {
1547                     has_edges: self.has_edges,
1548                     edges: if !self.has_edges {
1549                         self.edges
1550                     } else {
1551                         self.edges.$index(pos ..)
1552                     },
1553                     keys: &self.keys[pos ..],
1554                     vals: self.vals.$index(pos ..),
1555                     head_is_edge: !pos_is_kv,
1556                     tail_is_edge: self.tail_is_edge,
1557                 }
1558             }
1559
1560             /// Returns a sub-slice with elements up to and including `max_key`.
1561             pub fn slice_to<Q: ?Sized + Ord>(self, max_key: &Q) -> $NodeSlice<'a, K, V> where
1562                 K: Borrow<Q>,
1563             {
1564                 //  _______________
1565                 // |_1_|_3_|_5_|_7_|
1566                 // |   |   |   |   |
1567                 // 0 0 1 1 2 2 3 3 4  index
1568                 // |   |   |   |   |
1569                 //\|/  |   |   |   |  slice_to(&0); pos = 0
1570                 // \___/   |   |   |  slice_to(&2); pos = 1
1571                 // \___|___|   |   |  slice_to(&3); pos = 1; result.tail_is_edge = false
1572                 // \___|___/   |   |  slice_to(&4); pos = 2
1573                 // \___|___|___/   |  slice_to(&6); pos = 3
1574                 // \___|___|___|___/  slice_to(&999); pos = 4
1575                 let (pos, pos_is_kv) = self.search_linear(max_key);
1576                 let pos = pos + if pos_is_kv { 1 } else { 0 };
1577                 $NodeSlice {
1578                     has_edges: self.has_edges,
1579                     edges: if !self.has_edges {
1580                         self.edges
1581                     } else {
1582                         self.edges.$index(.. (pos + 1))
1583                     },
1584                     keys: &self.keys[..pos],
1585                     vals: self.vals.$index(.. pos),
1586                     head_is_edge: self.head_is_edge,
1587                     tail_is_edge: !pos_is_kv,
1588                 }
1589             }
1590         }
1591
1592         impl<'a, K: 'a, V: 'a> $NodeSlice<'a, K, V> {
1593             /// Returns an iterator over key/value pairs and edges in a slice.
1594             #[inline]
1595             pub fn $iter(self) -> $Traversal<'a, K, V> {
1596                 let mut edges = self.edges.$iter();
1597                 // Skip edges at both ends, if excluded.
1598                 if !self.head_is_edge { edges.next(); }
1599                 if !self.tail_is_edge { edges.next_back(); }
1600                 // The key iterator is always immutable.
1601                 $Traversal {
1602                     inner: ElemsAndEdges(
1603                         self.keys.iter().zip(self.vals.$iter()),
1604                         edges
1605                     ),
1606                     head_is_edge: self.head_is_edge,
1607                     tail_is_edge: self.tail_is_edge,
1608                     has_edges: self.has_edges,
1609                 }
1610             }
1611         }
1612     }
1613 }
1614
1615 node_slice_impl!(NodeSlice, Traversal, as_slices_internal, index, iter);
1616 node_slice_impl!(MutNodeSlice, MutTraversal, as_slices_internal_mut, index_mut, iter_mut);