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 is an attempt at an implementation following the ideal
  12 //
  13 // ```
  14 // struct BTreeMap<K, V> {
  15 //     height: usize,
  16 //     root: Option<Box<Node<K, V, height>>>
  17 // }
  18 //
  19 // struct Node<K, V, height: usize> {
  20 //     keys: [K; 2 * B - 1],
  21 //     vals: [V; 2 * B - 1],
  22 //     edges: if height > 0 {
  23 //         [Box<Node<K, V, height - 1>>; 2 * B]
  24 //     } else { () },
  25 //     parent: *const Node<K, V, height + 1>,
  26 //     parent_idx: u16,
  27 //     len: u16,
  28 // }
  29 // ```
  30 //
  31 // Since Rust doesn't acutally have dependent types and polymorphic recursion,
  32 // we make do with lots of unsafety.
  33
  34 use alloc::heap;
  35 use core::marker::PhantomData;
  36 use core::mem;
  37 use core::nonzero::NonZero;
  38 use core::ptr::{self, Unique};
  39 use core::slice;
  40
  41 use boxed::Box;
  42
  43 const B: usize = 6;
  44 pub const CAPACITY: usize = 2 * B - 1;
  45
  46 struct LeafNode<K, V> {
  47     keys: [K; CAPACITY],
  48     vals: [V; CAPACITY],
  49     parent: *const InternalNode<K, V>,
  50     parent_idx: u16,
  51     len: u16,
  52 }
  53
  54 impl<K, V> LeafNode<K, V> {
  55     unsafe fn new() -> Self {
  56         LeafNode {
  57             keys: mem::uninitialized(),
  58             vals: mem::uninitialized(),
  59             parent: ptr::null(),
  60             parent_idx: mem::uninitialized(),
  61             len: 0
  62         }
  63     }
  64 }
  65
  66 // We use repr(C) so that a pointer to an internal node can be
  67 // directly used as a pointer to a leaf node
  68 #[repr(C)]
  69 struct InternalNode<K, V> {
  70     data: LeafNode<K, V>,
  71     edges: [BoxedNode<K, V>; 2 * B],
  72 }
  73
  74 impl<K, V> InternalNode<K, V> {
  75     unsafe fn new() -> Self {
  76         InternalNode {
  77             data: LeafNode::new(),
  78             edges: mem::uninitialized()
  79         }
  80     }
  81 }
  82
  83 struct BoxedNode<K, V> {
  84     ptr: Unique<LeafNode<K, V>> // we don't know if this points to a leaf node or an internal node
  85 }
  86
  87 impl<K, V> BoxedNode<K, V> {
  88     fn from_leaf(node: Box<LeafNode<K, V>>) -> Self {
  89         unsafe {
  90             BoxedNode { ptr: Unique::new(Box::into_raw(node)) }
  91         }
  92     }
  93
  94     fn from_internal(node: Box<InternalNode<K, V>>) -> Self {
  95         unsafe {
  96             BoxedNode { ptr: Unique::new(Box::into_raw(node) as *mut LeafNode<K, V>) }
  97         }
  98     }
  99
 100     unsafe fn from_ptr(ptr: NonZero<*const LeafNode<K, V>>) -> Self {
 101         BoxedNode { ptr: Unique::new(*ptr as *mut LeafNode<K, V>) }
 102     }
 103
 104     fn as_ptr(&self) -> NonZero<*const LeafNode<K, V>> {
 105         unsafe {
 106             NonZero::new(*self.ptr as *const LeafNode<K, V>)
 107         }
 108     }
 109 }
 110
 111 /// An owned tree. Note that despite being owned, this does not have a destructor,
 112 /// and must be cleaned up manually.
 113 pub struct Root<K, V> {
 114     node: BoxedNode<K, V>,
 115     height: usize
 116 }
 117
 118 unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> { }
 119 unsafe impl<K: Send, V: Send> Send for Root<K, V> { }
 120
 121 impl<K, V> Root<K, V> {
 122     pub fn new_leaf() -> Self {
 123         Root {
 124             node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })),
 125             height: 0
 126         }
 127     }
 128
 129     pub fn as_ref(&self)
 130             -> NodeRef<marker::Immut, K, V, marker::LeafOrInternal> {
 131         NodeRef {
 132             height: self.height,
 133             node: self.node.as_ptr(),
 134             root: self as *const _ as *mut _,
 135             _marker: PhantomData,
 136         }
 137     }
 138
 139     pub fn as_mut(&mut self)
 140             -> NodeRef<marker::Mut, K, V, marker::LeafOrInternal> {
 141         NodeRef {
 142             height: self.height,
 143             node: self.node.as_ptr(),
 144             root: self as *mut _,
 145             _marker: PhantomData,
 146         }
 147     }
 148
 149     pub fn into_ref(self)
 150             -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
 151         NodeRef {
 152             height: self.height,
 153             node: self.node.as_ptr(),
 154             root: ptr::null_mut(), // FIXME: Is there anything better to do here?
 155             _marker: PhantomData,
 156         }
 157     }
 158
 159     /// Add a new internal node with a single edge, pointing to the previous root, and make that
 160     /// new node the root. This increases the height by 1 and is the opposite of `pop_level`.
 161     pub fn push_level(&mut self)
 162             -> NodeRef<marker::Mut, K, V, marker::Internal> {
 163         let mut new_node = Box::new(unsafe { InternalNode::new() });
 164         new_node.edges[0] = unsafe { BoxedNode::from_ptr(self.node.as_ptr()) };
 165
 166         self.node = BoxedNode::from_internal(new_node);
 167         self.height += 1;
 168
 169         let mut ret = NodeRef {
 170             height: self.height,
 171             node: self.node.as_ptr(),
 172             root: self as *mut _,
 173             _marker: PhantomData
 174         };
 175
 176         unsafe {
 177             ret.reborrow_mut().first_edge().correct_parent_link();
 178         }
 179
 180         ret
 181     }
 182
 183     /// Remove the root node, using its first child as the new root. This cannot be called when
 184     /// the tree consists only of a leaf node. As it is intended only to be called when the root
 185     /// has only one edge, no cleanup is done on any of the other children are elements of the root.
 186     /// This decreases the height by 1 and is the opposite of `push_level`.
 187     pub fn pop_level(&mut self) {
 188         debug_assert!(self.height > 0);
 189
 190         let top = *self.node.ptr as *mut u8;
 191
 192         self.node = unsafe {
 193             BoxedNode::from_ptr(self.as_mut()
 194                                     .cast_unchecked::<marker::Internal>()
 195                                     .first_edge()
 196                                     .descend()
 197                                     .node)
 198         };
 199         self.height -= 1;
 200         self.as_mut().as_leaf_mut().parent = ptr::null();
 201
 202         unsafe {
 203             heap::deallocate(
 204                 top,
 205                 mem::size_of::<InternalNode<K, V>>(),
 206                 mem::align_of::<InternalNode<K, V>>()
 207             );
 208         }
 209     }
 210 }
 211
 212 // N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType`
 213 // is `Mut`. This is technically wrong, but cannot result in any unsafety due to
 214 // internal use of `NodeRef` because we stay completely generic over `K` and `V`.
 215 // However, whenever a public type wraps `NodeRef`, make sure that it has the
 216 // correct variance.
 217 /// A reference to a node.
 218 ///
 219 /// This type has a number of paramaters that controls how it acts:
 220 /// - `BorrowType`: This can be `Immut<'a>` or `Mut<'a>` for some `'a` or `Owned`.
 221 ///    When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`,
 222 ///    when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`,
 223 ///    and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`.
 224 /// - `K` and `V`: These control what types of things are stored in the nodes.
 225 /// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is
 226 ///   `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
 227 ///   `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
 228 ///   `NodeRef` could be pointing to either type of node.
 229 pub struct NodeRef<BorrowType, K, V, Type> {
 230     height: usize,
 231     node: NonZero<*const LeafNode<K, V>>,
 232     root: *const Root<K, V>,
 233     _marker: PhantomData<(BorrowType, Type)>
 234 }
 235
 236 impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> { }
 237 impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
 238     fn clone(&self) -> Self {
 239         *self
 240     }
 241 }
 242
 243 unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync
 244     for NodeRef<BorrowType, K, V, Type> { }
 245
 246 unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send
 247    for NodeRef<marker::Immut<'a>, K, V, Type> { }
 248 unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send
 249    for NodeRef<marker::Mut<'a>, K, V, Type> { }
 250 unsafe impl<K: Send, V: Send, Type> Send
 251    for NodeRef<marker::Owned, K, V, Type> { }
 252
 253 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
 254     fn as_internal(&self) -> &InternalNode<K, V> {
 255         unsafe {
 256             &*(*self.node as *const InternalNode<K, V>)
 257         }
 258     }
 259 }
 260
 261 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
 262     fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
 263         unsafe {
 264             &mut *(*self.node as *mut InternalNode<K, V>)
 265         }
 266     }
 267 }
 268
 269
 270 impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
 271     pub fn len(&self) -> usize {
 272         self.as_leaf().len as usize
 273     }
 274
 275     pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
 276         NodeRef {
 277             height: self.height,
 278             node: self.node,
 279             root: self.root,
 280             _marker: PhantomData
 281         }
 282     }
 283
 284     fn reborrow<'a>(&'a self) -> NodeRef<marker::Immut<'a>, K, V, Type> {
 285         NodeRef {
 286             height: self.height,
 287             node: self.node,
 288             root: self.root,
 289             _marker: PhantomData
 290         }
 291     }
 292
 293     fn as_leaf(&self) -> &LeafNode<K, V> {
 294         unsafe {
 295             &**self.node
 296         }
 297     }
 298
 299     pub fn keys(&self) -> &[K] {
 300         self.reborrow().into_slices().0
 301     }
 302
 303     pub fn vals(&self) -> &[V] {
 304         self.reborrow().into_slices().1
 305     }
 306
 307     pub fn ascend(self) -> Result<
 308         Handle<
 309             NodeRef<
 310                 BorrowType,
 311                 K, V,
 312                 marker::Internal
 313             >,
 314             marker::Edge
 315         >,
 316         Self
 317     > {
 318         if self.as_leaf().parent.is_null() {
 319             Err(self)
 320         } else {
 321             Ok(Handle {
 322                 node: NodeRef {
 323                     height: self.height + 1,
 324                     node: unsafe {
 325                         NonZero::new(self.as_leaf().parent as *mut LeafNode<K, V>)
 326                     },
 327                     root: self.root,
 328                     _marker: PhantomData
 329                 },
 330                 idx: self.as_leaf().parent_idx as usize,
 331                 _marker: PhantomData
 332             })
 333         }
 334     }
 335
 336     pub fn first_edge(self) -> Handle<Self, marker::Edge> {
 337         Handle::new_edge(self, 0)
 338     }
 339
 340     pub fn last_edge(self) -> Handle<Self, marker::Edge> {
 341         let len = self.len();
 342         Handle::new_edge(self, len)
 343     }
 344 }
 345
 346 impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
 347     pub unsafe fn deallocate_and_ascend(self) -> Option<
 348         Handle<
 349             NodeRef<
 350                 marker::Owned,
 351                 K, V,
 352                 marker::Internal
 353             >,
 354             marker::Edge
 355         >
 356     > {
 357         let ptr = self.as_leaf() as *const LeafNode<K, V> as *const u8 as *mut u8;
 358         let ret = self.ascend().ok();
 359         heap::deallocate(ptr, mem::size_of::<LeafNode<K, V>>(), mem::align_of::<LeafNode<K, V>>());
 360         ret
 361     }
 362 }
 363
 364 impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
 365     pub unsafe fn deallocate_and_ascend(self) -> Option<
 366         Handle<
 367             NodeRef<
 368                 marker::Owned,
 369                 K, V,
 370                 marker::Internal
 371             >,
 372             marker::Edge
 373         >
 374     > {
 375         let ptr = self.as_internal() as *const InternalNode<K, V> as *const u8 as *mut u8;
 376         let ret = self.ascend().ok();
 377         heap::deallocate(
 378             ptr,
 379             mem::size_of::<InternalNode<K, V>>(),
 380             mem::align_of::<InternalNode<K, V>>()
 381         );
 382         ret
 383     }
 384 }
 385
 386 impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
 387     unsafe fn cast_unchecked<NewType>(&mut self)
 388             -> NodeRef<marker::Mut, K, V, NewType> {
 389
 390         NodeRef {
 391             height: self.height,
 392             node: self.node,
 393             root: self.root,
 394             _marker: PhantomData
 395         }
 396     }
 397
 398     unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut, K, V, Type> {
 399         NodeRef {
 400             height: self.height,
 401             node: self.node,
 402             root: self.root,
 403             _marker: PhantomData
 404         }
 405     }
 406
 407     fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
 408         unsafe {
 409             &mut *(*self.node as *mut LeafNode<K, V>)
 410         }
 411     }
 412
 413     pub fn keys_mut(&mut self) -> &mut [K] {
 414         unsafe { self.reborrow_mut().into_slices_mut().0 }
 415     }
 416
 417     pub fn vals_mut(&mut self) -> &mut [V] {
 418         unsafe { self.reborrow_mut().into_slices_mut().1 }
 419     }
 420 }
 421
 422 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
 423     pub fn into_slices(self) -> (&'a [K], &'a [V]) {
 424         unsafe {
 425             (
 426                 slice::from_raw_parts(
 427                     self.as_leaf().keys.as_ptr(),
 428                     self.len()
 429                 ),
 430                 slice::from_raw_parts(
 431                     self.as_leaf().vals.as_ptr(),
 432                     self.len()
 433                 )
 434             )
 435         }
 436     }
 437 }
 438
 439 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
 440     pub fn into_root_mut(self) -> &'a mut Root<K, V> {
 441         unsafe {
 442             &mut *(self.root as *mut Root<K, V>)
 443         }
 444     }
 445
 446     pub fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) {
 447         unsafe {
 448             (
 449                 slice::from_raw_parts_mut(
 450                     &mut self.as_leaf_mut().keys as *mut [K] as *mut K,
 451                     self.len()
 452                 ),
 453                 slice::from_raw_parts_mut(
 454                     &mut self.as_leaf_mut().vals as *mut [V] as *mut V,
 455                     self.len()
 456                 )
 457             )
 458         }
 459     }
 460 }
 461
 462 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
 463     pub fn push(&mut self, key: K, val: V) {
 464         // Necessary for correctness, but this is an internal module
 465         debug_assert!(self.len() < CAPACITY);
 466
 467         let idx = self.len();
 468
 469         unsafe {
 470             ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
 471             ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
 472         }
 473
 474         self.as_leaf_mut().len += 1;
 475     }
 476
 477     pub fn push_front(&mut self, key: K, val: V) {
 478         // Necessary for correctness, but this is an internal module
 479         debug_assert!(self.len() < CAPACITY);
 480
 481         unsafe {
 482             slice_insert(self.keys_mut(), 0, key);
 483             slice_insert(self.vals_mut(), 0, val);
 484         }
 485
 486         self.as_leaf_mut().len += 1;
 487     }
 488 }
 489
 490 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
 491     pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
 492         // Necessary for correctness, but this is an internal module
 493         debug_assert!(edge.height == self.height - 1);
 494         debug_assert!(self.len() < CAPACITY);
 495
 496         let idx = self.len();
 497
 498         unsafe {
 499             ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
 500             ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
 501             ptr::write(self.as_internal_mut().edges.get_unchecked_mut(idx + 1), edge.node);
 502
 503             self.as_leaf_mut().len += 1;
 504
 505             Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
 506         }
 507     }
 508
 509     pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
 510         // Necessary for correctness, but this is an internal module
 511         debug_assert!(edge.height == self.height - 1);
 512         debug_assert!(self.len() < CAPACITY);
 513
 514         unsafe {
 515             slice_insert(self.keys_mut(), 0, key);
 516             slice_insert(self.vals_mut(), 0, val);
 517             slice_insert(
 518                 slice::from_raw_parts_mut(
 519                     self.as_internal_mut().edges.as_mut_ptr(),
 520                     self.len()+1
 521                 ),
 522                 0,
 523                 edge.node
 524             );
 525
 526             self.as_leaf_mut().len += 1;
 527
 528             for i in 0..self.len()+1 {
 529                 Handle::new_edge(self.reborrow_mut(), i).correct_parent_link();
 530             }
 531         }
 532
 533     }
 534 }
 535
 536 impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
 537     pub fn pop(&mut self) -> (K, V, Option<Root<K, V>>) {
 538         // Necessary for correctness, but this is an internal module
 539         debug_assert!(self.len() > 0);
 540
 541         let idx = self.len() - 1;
 542
 543         unsafe {
 544             let key = ptr::read(self.keys().get_unchecked(idx));
 545             let val = ptr::read(self.vals().get_unchecked(idx));
 546             let edge = match self.reborrow_mut().force() {
 547                 ForceResult::Leaf(_) => None,
 548                 ForceResult::Internal(internal) => {
 549                     let edge = ptr::read(internal.as_internal().edges.get_unchecked(idx + 1));
 550                     let mut new_root = Root { node: edge, height: internal.height - 1 };
 551                     new_root.as_mut().as_leaf_mut().parent = ptr::null();
 552                     Some(new_root)
 553                 }
 554             };
 555
 556             self.as_leaf_mut().len -= 1;
 557             (key, val, edge)
 558         }
 559     }
 560
 561     pub fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) {
 562         // Necessary for correctness, but this is an internal module
 563         debug_assert!(self.len() > 0);
 564
 565         let old_len = self.len();
 566
 567         unsafe {
 568             let key = slice_remove(self.keys_mut(), 0);
 569             let val = slice_remove(self.vals_mut(), 0);
 570             let edge = match self.reborrow_mut().force() {
 571                 ForceResult::Leaf(_) => None,
 572                 ForceResult::Internal(mut internal) => {
 573                     let edge = slice_remove(
 574                         slice::from_raw_parts_mut(
 575                             internal.as_internal_mut().edges.as_mut_ptr(),
 576                             old_len+1
 577                         ),
 578                         0
 579                     );
 580
 581                     let mut new_root = Root { node: edge, height: internal.height - 1 };
 582                     new_root.as_mut().as_leaf_mut().parent = ptr::null();
 583
 584                     for i in 0..old_len {
 585                         Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link();
 586                     }
 587
 588                     Some(new_root)
 589                 }
 590             };
 591
 592             self.as_leaf_mut().len -= 1;
 593
 594             (key, val, edge)
 595         }
 596     }
 597 }
 598
 599 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
 600     pub fn force(self) -> ForceResult<
 601         NodeRef<BorrowType, K, V, marker::Leaf>,
 602         NodeRef<BorrowType, K, V, marker::Internal>
 603     > {
 604         if self.height == 0 {
 605             ForceResult::Leaf(NodeRef {
 606                 height: self.height,
 607                 node: self.node,
 608                 root: self.root,
 609                 _marker: PhantomData
 610             })
 611         } else {
 612             ForceResult::Internal(NodeRef {
 613                 height: self.height,
 614                 node: self.node,
 615                 root: self.root,
 616                 _marker: PhantomData
 617             })
 618         }
 619     }
 620 }
 621
 622 pub struct Handle<Node, Type> {
 623     node: Node,
 624     idx: usize,
 625     _marker: PhantomData<Type>
 626 }
 627
 628 impl<Node: Copy, Type> Copy for Handle<Node, Type> { }
 629 impl<Node: Copy, Type> Clone for Handle<Node, Type> {
 630     fn clone(&self) -> Self {
 631         *self
 632     }
 633 }
 634
 635 impl<Node, Type> Handle<Node, Type> {
 636     pub fn into_node(self) -> Node {
 637         self.node
 638     }
 639 }
 640
 641 impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
 642     pub fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
 643         // Necessary for correctness, but in a private module
 644         debug_assert!(idx < node.len());
 645
 646         Handle {
 647             node: node,
 648             idx: idx,
 649             _marker: PhantomData
 650         }
 651     }
 652
 653     pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
 654         Handle::new_edge(self.node, self.idx)
 655     }
 656
 657     pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
 658         Handle::new_edge(self.node, self.idx + 1)
 659     }
 660 }
 661
 662 impl<BorrowType, K, V, NodeType, HandleType> PartialEq
 663         for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
 664
 665     fn eq(&self, other: &Self) -> bool {
 666         self.node.node == other.node.node && self.idx == other.idx
 667     }
 668 }
 669
 670 impl<BorrowType, K, V, NodeType, HandleType>
 671         Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
 672
 673     pub fn reborrow(&self)
 674             -> Handle<NodeRef<marker::Immut, K, V, NodeType>, HandleType> {
 675
 676         // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
 677         Handle {
 678             node: self.node.reborrow(),
 679             idx: self.idx,
 680             _marker: PhantomData
 681         }
 682     }
 683 }
 684
 685 impl<'a, K, V, NodeType, HandleType>
 686         Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
 687
 688     pub unsafe fn reborrow_mut(&mut self)
 689             -> Handle<NodeRef<marker::Mut, K, V, NodeType>, HandleType> {
 690
 691         // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
 692         Handle {
 693             node: self.node.reborrow_mut(),
 694             idx: self.idx,
 695             _marker: PhantomData
 696         }
 697     }
 698 }
 699
 700 impl<BorrowType, K, V, NodeType>
 701         Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
 702
 703     pub fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
 704         // Necessary for correctness, but in a private module
 705         debug_assert!(idx <= node.len());
 706
 707         Handle {
 708             node: node,
 709             idx: idx,
 710             _marker: PhantomData
 711         }
 712     }
 713
 714     pub fn left_kv(self)
 715             -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
 716
 717         if self.idx > 0 {
 718             Ok(Handle::new_kv(self.node, self.idx - 1))
 719         } else {
 720             Err(self)
 721         }
 722     }
 723
 724     pub fn right_kv(self)
 725             -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
 726
 727         if self.idx < self.node.len() {
 728             Ok(Handle::new_kv(self.node, self.idx))
 729         } else {
 730             Err(self)
 731         }
 732     }
 733 }
 734
 735 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
 736     fn insert_fit(&mut self, key: K, val: V) -> *mut V {
 737         // Necessary for correctness, but in a private module
 738         debug_assert!(self.node.len() < CAPACITY);
 739
 740         unsafe {
 741             slice_insert(self.node.keys_mut(), self.idx, key);
 742             slice_insert(self.node.vals_mut(), self.idx, val);
 743
 744             self.node.as_leaf_mut().len += 1;
 745
 746             self.node.vals_mut().get_unchecked_mut(self.idx)
 747         }
 748     }
 749
 750     pub fn insert(mut self, key: K, val: V)
 751             -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
 752
 753         if self.node.len() < CAPACITY {
 754             let ptr = self.insert_fit(key, val);
 755             (InsertResult::Fit(Handle::new_kv(self.node, self.idx)), ptr)
 756         } else {
 757             let middle = Handle::new_kv(self.node, B);
 758             let (mut left, k, v, mut right) = middle.split();
 759             let ptr = if self.idx <= B {
 760                 unsafe {
 761                     Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val)
 762                 }
 763             } else {
 764                 unsafe {
 765                     Handle::new_edge(
 766                         right.as_mut().cast_unchecked::<marker::Leaf>(),
 767                         self.idx - (B + 1)
 768                     ).insert_fit(key, val)
 769                 }
 770             };
 771             (InsertResult::Split(left, k, v, right), ptr)
 772         }
 773     }
 774 }
 775
 776 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
 777     fn correct_parent_link(mut self) {
 778         let idx = self.idx as u16;
 779         let ptr = self.node.as_internal_mut() as *mut _;
 780         let mut child = self.descend();
 781         child.as_leaf_mut().parent = ptr;
 782         child.as_leaf_mut().parent_idx = idx;
 783     }
 784
 785     unsafe fn cast_unchecked<NewType>(&mut self)
 786             -> Handle<NodeRef<marker::Mut, K, V, NewType>, marker::Edge> {
 787
 788         Handle::new_edge(self.node.cast_unchecked(), self.idx)
 789     }
 790
 791     fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
 792         // Necessary for correctness, but in an internal module
 793         debug_assert!(self.node.len() < CAPACITY);
 794         debug_assert!(edge.height == self.node.height - 1);
 795
 796         unsafe {
 797             self.cast_unchecked::<marker::Leaf>().insert_fit(key, val);
 798
 799             slice_insert(
 800                 slice::from_raw_parts_mut(
 801                     self.node.as_internal_mut().edges.as_mut_ptr(),
 802                     self.node.len()
 803                 ),
 804                 self.idx + 1,
 805                 edge.node
 806             );
 807
 808             for i in (self.idx+1)..(self.node.len()+1) {
 809                 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
 810             }
 811         }
 812     }
 813
 814     pub fn insert(mut self, key: K, val: V, edge: Root<K, V>)
 815             -> InsertResult<'a, K, V, marker::Internal> {
 816
 817         // Necessary for correctness, but this is an internal module
 818         debug_assert!(edge.height == self.node.height - 1);
 819
 820         if self.node.len() < CAPACITY {
 821             self.insert_fit(key, val, edge);
 822             InsertResult::Fit(Handle::new_kv(self.node, self.idx))
 823         } else {
 824             let middle = Handle::new_kv(self.node, B);
 825             let (mut left, k, v, mut right) = middle.split();
 826             if self.idx <= B {
 827                 unsafe {
 828                     Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val, edge);
 829                 }
 830             } else {
 831                 unsafe {
 832                     Handle::new_edge(
 833                         right.as_mut().cast_unchecked::<marker::Internal>(),
 834                         self.idx - (B + 1)
 835                     ).insert_fit(key, val, edge);
 836                 }
 837             }
 838             InsertResult::Split(left, k, v, right)
 839         }
 840     }
 841 }
 842
 843 impl<BorrowType, K, V>
 844         Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
 845
 846     pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
 847         NodeRef {
 848             height: self.node.height - 1,
 849             node: unsafe { self.node.as_internal().edges.get_unchecked(self.idx).as_ptr() },
 850             root: self.node.root,
 851             _marker: PhantomData
 852         }
 853     }
 854 }
 855
 856 impl<'a, K: 'a, V: 'a, NodeType>
 857         Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
 858
 859     pub fn into_kv(self) -> (&'a K, &'a V) {
 860         let (keys, vals) = self.node.into_slices();
 861         unsafe {
 862             (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx))
 863         }
 864     }
 865 }
 866
 867 impl<'a, K: 'a, V: 'a, NodeType>
 868         Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
 869
 870     pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
 871         let (mut keys, mut vals) = self.node.into_slices_mut();
 872         unsafe {
 873             (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
 874         }
 875     }
 876 }
 877
 878 impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
 879     pub fn kv_mut(&mut self) -> (&mut K, &mut V) {
 880         unsafe {
 881             let (mut keys, mut vals) = self.node.reborrow_mut().into_slices_mut();
 882             (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
 883         }
 884     }
 885 }
 886
 887 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
 888     pub fn split(mut self)
 889             -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) {
 890         unsafe {
 891             let mut new_node = Box::new(LeafNode::new());
 892
 893             let k = ptr::read(self.node.keys().get_unchecked(self.idx));
 894             let v = ptr::read(self.node.vals().get_unchecked(self.idx));
 895
 896             let new_len = self.node.len() - self.idx - 1;
 897
 898             ptr::copy_nonoverlapping(
 899                 self.node.keys().as_ptr().offset(self.idx as isize + 1),
 900                 new_node.keys.as_mut_ptr(),
 901                 new_len
 902             );
 903             ptr::copy_nonoverlapping(
 904                 self.node.vals().as_ptr().offset(self.idx as isize + 1),
 905                 new_node.vals.as_mut_ptr(),
 906                 new_len
 907             );
 908
 909             self.node.as_leaf_mut().len = self.idx as u16;
 910             new_node.len = new_len as u16;
 911
 912             (
 913                 self.node,
 914                 k, v,
 915                 Root {
 916                     node: BoxedNode::from_leaf(new_node),
 917                     height: 0
 918                 }
 919             )
 920         }
 921     }
 922
 923     pub fn remove(mut self)
 924             -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, K, V) {
 925         unsafe {
 926             let k = slice_remove(self.node.keys_mut(), self.idx);
 927             let v = slice_remove(self.node.vals_mut(), self.idx);
 928             self.node.as_leaf_mut().len -= 1;
 929             (self.left_edge(), k, v)
 930         }
 931     }
 932 }
 933
 934 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
 935     pub fn split(mut self)
 936             -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) {
 937         unsafe {
 938             let mut new_node = Box::new(InternalNode::new());
 939
 940             let k = ptr::read(self.node.keys().get_unchecked(self.idx));
 941             let v = ptr::read(self.node.vals().get_unchecked(self.idx));
 942
 943             let height = self.node.height;
 944             let new_len = self.node.len() - self.idx - 1;
 945
 946             ptr::copy_nonoverlapping(
 947                 self.node.keys().as_ptr().offset(self.idx as isize + 1),
 948                 new_node.data.keys.as_mut_ptr(),
 949                 new_len
 950             );
 951             ptr::copy_nonoverlapping(
 952                 self.node.vals().as_ptr().offset(self.idx as isize + 1),
 953                 new_node.data.vals.as_mut_ptr(),
 954                 new_len
 955             );
 956             ptr::copy_nonoverlapping(
 957                 self.node.as_internal().edges.as_ptr().offset(self.idx as isize + 1),
 958                 new_node.edges.as_mut_ptr(),
 959                 new_len + 1
 960             );
 961
 962             self.node.as_leaf_mut().len = self.idx as u16;
 963             new_node.data.len = new_len as u16;
 964
 965             let mut new_root = Root {
 966                 node: BoxedNode::from_internal(new_node),
 967                 height: height
 968             };
 969
 970             for i in 0..(new_len+1) {
 971                 Handle::new_edge(new_root.as_mut().cast_unchecked(), i).correct_parent_link();
 972             }
 973
 974             (
 975                 self.node,
 976                 k, v,
 977                 new_root
 978             )
 979         }
 980     }
 981
 982     pub fn can_merge(&self) -> bool {
 983         (
 984             self.reborrow()
 985                 .left_edge()
 986                 .descend()
 987                 .len()
 988           + self.reborrow()
 989                 .right_edge()
 990                 .descend()
 991                 .len()
 992           + 1
 993         ) <= CAPACITY
 994     }
 995
 996     pub fn merge(mut self)
 997             -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
 998         let self1 = unsafe { ptr::read(&self) };
 999         let self2 = unsafe { ptr::read(&self) };
1000         let mut left_node = self1.left_edge().descend();
1001         let left_len = left_node.len();
1002         let mut right_node = self2.right_edge().descend();
1003         let right_len = right_node.len();
1004
1005         // necessary for correctness, but in a private module
1006         debug_assert!(left_len + right_len + 1 <= CAPACITY);
1007
1008         unsafe {
1009             ptr::write(left_node.keys_mut().get_unchecked_mut(left_len),
1010                        slice_remove(self.node.keys_mut(), self.idx));
1011             ptr::copy_nonoverlapping(
1012                 right_node.keys().as_ptr(),
1013                 left_node.keys_mut().as_mut_ptr().offset(left_len as isize + 1),
1014                 right_len
1015             );
1016             ptr::write(left_node.vals_mut().get_unchecked_mut(left_len),
1017                        slice_remove(self.node.vals_mut(), self.idx));
1018             ptr::copy_nonoverlapping(
1019                 right_node.vals().as_ptr(),
1020                 left_node.vals_mut().as_mut_ptr().offset(left_len as isize + 1),
1021                 right_len
1022             );
1023
1024             slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1);
1025             for i in self.idx+1..self.node.len() {
1026                 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
1027             }
1028             self.node.as_leaf_mut().len -= 1;
1029
1030             if self.node.height > 1 {
1031                 ptr::copy_nonoverlapping(
1032                     right_node.cast_unchecked().as_internal().edges.as_ptr(),
1033                     left_node.cast_unchecked()
1034                              .as_internal_mut()
1035                              .edges
1036                              .as_mut_ptr()
1037                              .offset(left_len as isize + 1),
1038                     right_len + 1
1039                 );
1040
1041                 for i in left_len+1..left_len+right_len+2 {
1042                     Handle::new_edge(
1043                         left_node.cast_unchecked().reborrow_mut(),
1044                         i
1045                     ).correct_parent_link();
1046                 }
1047
1048                 heap::deallocate(
1049                     *right_node.node as *mut u8,
1050                     mem::size_of::<InternalNode<K, V>>(),
1051                     mem::align_of::<InternalNode<K, V>>()
1052                 );
1053             } else {
1054                 heap::deallocate(
1055                     *right_node.node as *mut u8,
1056                     mem::size_of::<LeafNode<K, V>>(),
1057                     mem::align_of::<LeafNode<K, V>>()
1058                 );
1059             }
1060
1061             left_node.as_leaf_mut().len += right_len as u16 + 1;
1062
1063             Handle::new_edge(self.node, self.idx)
1064         }
1065     }
1066 }
1067
1068 impl<BorrowType, K, V, HandleType>
1069         Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> {
1070
1071     pub fn force(self) -> ForceResult<
1072         Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>,
1073         Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>
1074     > {
1075         match self.node.force() {
1076             ForceResult::Leaf(node) => ForceResult::Leaf(Handle {
1077                 node: node,
1078                 idx: self.idx,
1079                 _marker: PhantomData
1080             }),
1081             ForceResult::Internal(node) => ForceResult::Internal(Handle {
1082                 node: node,
1083                 idx: self.idx,
1084                 _marker: PhantomData
1085             })
1086         }
1087     }
1088 }
1089
1090 pub enum ForceResult<Leaf, Internal> {
1091     Leaf(Leaf),
1092     Internal(Internal)
1093 }
1094
1095 pub enum InsertResult<'a, K, V, Type> {
1096     Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>),
1097     Split(NodeRef<marker::Mut<'a>, K, V, Type>, K, V, Root<K, V>)
1098 }
1099
1100 pub mod marker {
1101     use core::marker::PhantomData;
1102
1103     pub enum Leaf { }
1104     pub enum Internal { }
1105     pub enum LeafOrInternal { }
1106
1107     pub enum Owned { }
1108     pub struct Immut<'a>(PhantomData<&'a ()>);
1109     pub struct Mut<'a>(PhantomData<&'a mut ()>);
1110
1111     pub enum KV { }
1112     pub enum Edge { }
1113 }
1114
1115 unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) {
1116     ptr::copy(
1117         slice.as_ptr().offset(idx as isize),
1118         slice.as_mut_ptr().offset(idx as isize + 1),
1119         slice.len() - idx
1120     );
1121     ptr::write(slice.get_unchecked_mut(idx), val);
1122 }
1123
1124 unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T {
1125     let ret = ptr::read(slice.get_unchecked(idx));
1126     ptr::copy(
1127         slice.as_ptr().offset(idx as isize + 1),
1128         slice.as_mut_ptr().offset(idx as isize),
1129         slice.len() - idx - 1
1130     );
1131     ret
1132 }