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