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