src/libcollections/btree/map.rs

   1 // Copyright 2015 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 use core::cmp::Ordering;
  12 use core::fmt::Debug;
  13 use core::hash::{Hash, Hasher};
  14 use core::iter::FromIterator;
  15 use core::marker::PhantomData;
  16 use core::ops::Index;
  17 use core::{fmt, intrinsics, mem, ptr};
  18
  19 use borrow::Borrow;
  20 use Bound::{self, Included, Excluded, Unbounded};
  21
  22 use super::node::{self, NodeRef, Handle, marker};
  23 use super::search;
  24
  25 use super::node::InsertResult::*;
  26 use super::node::ForceResult::*;
  27 use super::search::SearchResult::*;
  28 use self::UnderflowResult::*;
  29 use self::Entry::*;
  30
  31 /// A map based on a B-Tree.
  32 ///
  33 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
  34 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
  35 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
  36 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
  37 /// is done is *very* inefficient for modern computer architectures. In particular, every element
  38 /// is stored in its own individually heap-allocated node. This means that every single insertion
  39 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
  40 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
  41 /// the BST strategy.
  42 ///
  43 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
  44 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
  45 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
  46 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
  47 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
  48 /// the node using binary search. As a compromise, one could also perform a linear search
  49 /// that initially only checks every i<sup>th</sup> element for some choice of i.
  50 ///
  51 /// Currently, our implementation simply performs naive linear search. This provides excellent
  52 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
  53 /// would like to further explore choosing the optimal search strategy based on the choice of B,
  54 /// and possibly other factors. Using linear search, searching for a random element is expected
  55 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
  56 /// however, performance is excellent.
  57 ///
  58 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
  59 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
  60 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
  61 #[stable(feature = "rust1", since = "1.0.0")]
  62 pub struct BTreeMap<K, V> {
  63     root: node::Root<K, V>,
  64     length: usize
  65 }
  66
  67 impl<K, V> Drop for BTreeMap<K, V> {
  68     #[unsafe_destructor_blind_to_params]
  69     fn drop(&mut self) {
  70         unsafe {
  71             for _ in ptr::read(self).into_iter() { }
  72         }
  73     }
  74 }
  75
  76 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
  77     fn clone(&self) -> BTreeMap<K, V> {
  78         fn clone_subtree<K: Clone, V: Clone>(
  79                 node: node::NodeRef<marker::Immut, K, V, marker::LeafOrInternal>)
  80                 -> BTreeMap<K, V> {
  81
  82             match node.force() {
  83                 Leaf(leaf) => {
  84                     let mut out_tree = BTreeMap {
  85                         root: node::Root::new_leaf(),
  86                         length: 0
  87                     };
  88
  89                     {
  90                         let mut out_node = match out_tree.root.as_mut().force() {
  91                             Leaf(leaf) => leaf,
  92                             Internal(_) => unreachable!()
  93                         };
  94
  95                         let mut in_edge = leaf.first_edge();
  96                         while let Ok(kv) = in_edge.right_kv() {
  97                             let (k, v) = kv.into_kv();
  98                             in_edge = kv.right_edge();
  99
 100                             out_node.push(k.clone(), v.clone());
 101                             out_tree.length += 1;
 102                         }
 103                     }
 104
 105                     out_tree
 106                 },
 107                 Internal(internal) => {
 108                     let mut out_tree = clone_subtree(internal.first_edge().descend());
 109
 110                     {
 111                         let mut out_node = out_tree.root.push_level();
 112                         let mut in_edge = internal.first_edge();
 113                         while let Ok(kv) = in_edge.right_kv() {
 114                             let (k, v) = kv.into_kv();
 115                             in_edge = kv.right_edge();
 116
 117                             let k = (*k).clone();
 118                             let v = (*v).clone();
 119                             let subtree = clone_subtree(in_edge.descend());
 120
 121                             // We can't destructure subtree directly
 122                             // because BTreeMap implements Drop
 123                             let (subroot, sublength) = unsafe {
 124                                 let root = ptr::read(&subtree.root);
 125                                 let length = subtree.length;
 126                                 mem::forget(subtree);
 127                                 (root, length)
 128                             };
 129
 130                             out_node.push(k, v, subroot);
 131                             out_tree.length += 1 + sublength;
 132                         }
 133                     }
 134
 135                     out_tree
 136                 }
 137             }
 138         }
 139
 140         clone_subtree(self.root.as_ref())
 141     }
 142 }
 143
 144 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
 145     where K: Borrow<Q> + Ord,
 146           Q: Ord
 147 {
 148     type Key = K;
 149
 150     fn get(&self, key: &Q) -> Option<&K> {
 151         match search::search_tree(self.root.as_ref(), key) {
 152             Found(handle) => Some(handle.into_kv().0),
 153             GoDown(_) => None
 154         }
 155     }
 156
 157     fn take(&mut self, key: &Q) -> Option<K> {
 158         match search::search_tree(self.root.as_mut(), key) {
 159             Found(handle) => {
 160                 Some(OccupiedEntry {
 161                     handle: handle,
 162                     length: &mut self.length,
 163                     _marker: PhantomData,
 164                 }.remove_kv().0)
 165             },
 166             GoDown(_) => None
 167         }
 168     }
 169
 170     fn replace(&mut self, key: K) -> Option<K> {
 171         match search::search_tree::<marker::Mut, K, (), K>(self.root.as_mut(), &key) {
 172             Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
 173             GoDown(handle) => {
 174                 VacantEntry {
 175                     key: key,
 176                     handle: handle,
 177                     length: &mut self.length,
 178                     _marker: PhantomData,
 179                 }.insert(());
 180                 None
 181             }
 182         }
 183     }
 184 }
 185
 186 /// An iterator over a BTreeMap's entries.
 187 #[stable(feature = "rust1", since = "1.0.0")]
 188 pub struct Iter<'a, K: 'a, V: 'a> {
 189     range: Range<'a, K, V>,
 190     length: usize
 191 }
 192
 193 /// A mutable iterator over a BTreeMap's entries.
 194 #[stable(feature = "rust1", since = "1.0.0")]
 195 pub struct IterMut<'a, K: 'a, V: 'a> {
 196     range: RangeMut<'a, K, V>,
 197     length: usize
 198 }
 199
 200 /// An owning iterator over a BTreeMap's entries.
 201 #[stable(feature = "rust1", since = "1.0.0")]
 202 pub struct IntoIter<K, V> {
 203     front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
 204     back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
 205     length: usize
 206 }
 207
 208 /// An iterator over a BTreeMap's keys.
 209 #[stable(feature = "rust1", since = "1.0.0")]
 210 pub struct Keys<'a, K: 'a, V: 'a> {
 211     inner: Iter<'a, K, V>,
 212 }
 213
 214 /// An iterator over a BTreeMap's values.
 215 #[stable(feature = "rust1", since = "1.0.0")]
 216 pub struct Values<'a, K: 'a, V: 'a> {
 217     inner: Iter<'a, K, V>,
 218 }
 219
 220 /// An iterator over a sub-range of BTreeMap's entries.
 221 pub struct Range<'a, K: 'a, V: 'a> {
 222     front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
 223     back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>
 224 }
 225
 226 /// A mutable iterator over a sub-range of BTreeMap's entries.
 227 pub struct RangeMut<'a, K: 'a, V: 'a> {
 228     front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 229     back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 230
 231     // Be invariant in `K` and `V`
 232     _marker: PhantomData<&'a mut (K, V)>,
 233 }
 234
 235 /// A view into a single entry in a map, which may either be vacant or occupied.
 236 #[stable(feature = "rust1", since = "1.0.0")]
 237 pub enum Entry<'a, K: 'a, V: 'a> {
 238     /// A vacant Entry
 239     #[stable(feature = "rust1", since = "1.0.0")]
 240     Vacant(
 241         #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] VacantEntry<'a, K, V>
 242     ),
 243
 244     /// An occupied Entry
 245     #[stable(feature = "rust1", since = "1.0.0")]
 246     Occupied(
 247         #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] OccupiedEntry<'a, K, V>
 248     ),
 249 }
 250
 251 /// A vacant Entry.
 252 #[stable(feature = "rust1", since = "1.0.0")]
 253 pub struct VacantEntry<'a, K: 'a, V: 'a> {
 254     key: K,
 255     handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 256     length: &'a mut usize,
 257
 258     // Be invariant in `K` and `V`
 259     _marker: PhantomData<&'a mut (K, V)>,
 260 }
 261
 262 /// An occupied Entry.
 263 #[stable(feature = "rust1", since = "1.0.0")]
 264 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
 265     handle: Handle<NodeRef<
 266         marker::Mut<'a>,
 267         K, V,
 268         marker::LeafOrInternal
 269     >, marker::KV>,
 270
 271     length: &'a mut usize,
 272
 273     // Be invariant in `K` and `V`
 274     _marker: PhantomData<&'a mut (K, V)>,
 275 }
 276
 277 impl<K: Ord, V> BTreeMap<K, V> {
 278     /// Makes a new empty BTreeMap with a reasonable choice for B.
 279     #[stable(feature = "rust1", since = "1.0.0")]
 280     pub fn new() -> BTreeMap<K, V> {
 281         BTreeMap {
 282             root: node::Root::new_leaf(),
 283             length: 0
 284         }
 285     }
 286
 287     /// Clears the map, removing all values.
 288     ///
 289     /// # Examples
 290     ///
 291     /// ```
 292     /// use std::collections::BTreeMap;
 293     ///
 294     /// let mut a = BTreeMap::new();
 295     /// a.insert(1, "a");
 296     /// a.clear();
 297     /// assert!(a.is_empty());
 298     /// ```
 299     #[stable(feature = "rust1", since = "1.0.0")]
 300     pub fn clear(&mut self) {
 301         // FIXME(gereeter) .clear() allocates
 302         *self = BTreeMap::new();
 303     }
 304
 305     /// Returns a reference to the value corresponding to the key.
 306     ///
 307     /// The key may be any borrowed form of the map's key type, but the ordering
 308     /// on the borrowed form *must* match the ordering on the key type.
 309     ///
 310     /// # Examples
 311     ///
 312     /// ```
 313     /// use std::collections::BTreeMap;
 314     ///
 315     /// let mut map = BTreeMap::new();
 316     /// map.insert(1, "a");
 317     /// assert_eq!(map.get(&1), Some(&"a"));
 318     /// assert_eq!(map.get(&2), None);
 319     /// ```
 320     #[stable(feature = "rust1", since = "1.0.0")]
 321     pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
 322         match search::search_tree(self.root.as_ref(), key) {
 323             Found(handle) => Some(handle.into_kv().1),
 324             GoDown(_) => None
 325         }
 326     }
 327
 328     /// Returns true if the map contains a value for the specified key.
 329     ///
 330     /// The key may be any borrowed form of the map's key type, but the ordering
 331     /// on the borrowed form *must* match the ordering on the key type.
 332     ///
 333     /// # Examples
 334     ///
 335     /// ```
 336     /// use std::collections::BTreeMap;
 337     ///
 338     /// let mut map = BTreeMap::new();
 339     /// map.insert(1, "a");
 340     /// assert_eq!(map.contains_key(&1), true);
 341     /// assert_eq!(map.contains_key(&2), false);
 342     /// ```
 343     #[stable(feature = "rust1", since = "1.0.0")]
 344     pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
 345         self.get(key).is_some()
 346     }
 347
 348     /// Returns a mutable reference to the value corresponding to the key.
 349     ///
 350     /// The key may be any borrowed form of the map's key type, but the ordering
 351     /// on the borrowed form *must* match the ordering on the key type.
 352     ///
 353     /// # Examples
 354     ///
 355     /// ```
 356     /// use std::collections::BTreeMap;
 357     ///
 358     /// let mut map = BTreeMap::new();
 359     /// map.insert(1, "a");
 360     /// if let Some(x) = map.get_mut(&1) {
 361     ///     *x = "b";
 362     /// }
 363     /// assert_eq!(map[&1], "b");
 364     /// ```
 365     // See `get` for implementation notes, this is basically a copy-paste with mut's added
 366     #[stable(feature = "rust1", since = "1.0.0")]
 367     pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
 368         match search::search_tree(self.root.as_mut(), key) {
 369             Found(handle) => Some(handle.into_kv_mut().1),
 370             GoDown(_) => None
 371         }
 372     }
 373
 374     /// Inserts a key-value pair into the map.
 375     ///
 376     /// If the map did not have this key present, `None` is returned.
 377     ///
 378     /// If the map did have this key present, the key is not updated, the
 379     /// value is updated and the old value is returned.
 380     /// See the [module-level documentation] for more.
 381     ///
 382     /// [module-level documentation]: index.html#insert-and-complex-keys
 383     ///
 384     /// # Examples
 385     ///
 386     /// ```
 387     /// use std::collections::BTreeMap;
 388     ///
 389     /// let mut map = BTreeMap::new();
 390     /// assert_eq!(map.insert(37, "a"), None);
 391     /// assert_eq!(map.is_empty(), false);
 392     ///
 393     /// map.insert(37, "b");
 394     /// assert_eq!(map.insert(37, "c"), Some("b"));
 395     /// assert_eq!(map[&37], "c");
 396     /// ```
 397     #[stable(feature = "rust1", since = "1.0.0")]
 398     pub fn insert(&mut self, key: K, value: V) -> Option<V> {
 399         match self.entry(key) {
 400             Occupied(mut entry) => Some(entry.insert(value)),
 401             Vacant(entry) => {
 402                 entry.insert(value);
 403                 None
 404             }
 405         }
 406     }
 407
 408     /// Removes a key from the map, returning the value at the key if the key
 409     /// was previously in the map.
 410     ///
 411     /// The key may be any borrowed form of the map's key type, but the ordering
 412     /// on the borrowed form *must* match the ordering on the key type.
 413     ///
 414     /// # Examples
 415     ///
 416     /// ```
 417     /// use std::collections::BTreeMap;
 418     ///
 419     /// let mut map = BTreeMap::new();
 420     /// map.insert(1, "a");
 421     /// assert_eq!(map.remove(&1), Some("a"));
 422     /// assert_eq!(map.remove(&1), None);
 423     /// ```
 424     #[stable(feature = "rust1", since = "1.0.0")]
 425     pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
 426         match search::search_tree(self.root.as_mut(), key) {
 427             Found(handle) => {
 428                 Some(OccupiedEntry {
 429                     handle: handle,
 430                     length: &mut self.length,
 431                     _marker: PhantomData,
 432                 }.remove())
 433             },
 434             GoDown(_) => None
 435         }
 436     }
 437
 438     /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
 439     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
 440     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
 441     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
 442     ///
 443     /// # Examples
 444     ///
 445     /// ```
 446     /// #![feature(btree_range, collections_bound)]
 447     ///
 448     /// use std::collections::BTreeMap;
 449     /// use std::collections::Bound::{Included, Unbounded};
 450     ///
 451     /// let mut map = BTreeMap::new();
 452     /// map.insert(3, "a");
 453     /// map.insert(5, "b");
 454     /// map.insert(8, "c");
 455     /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
 456     ///     println!("{}: {}", key, value);
 457     /// }
 458     /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
 459     /// ```
 460     #[unstable(feature = "btree_range",
 461                reason = "matches collection reform specification, waiting for dust to settle",
 462                issue = "27787")]
 463     pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
 464                                                        min: Bound<&Min>,
 465                                                        max: Bound<&Max>)
 466                                                        -> Range<K, V>
 467         where K: Borrow<Min> + Borrow<Max>,
 468     {
 469         let front = match min {
 470             Included(key) => match search::search_tree(self.root.as_ref(), key) {
 471                 Found(kv_handle) => match kv_handle.left_edge().force() {
 472                     Leaf(bottom) => bottom,
 473                     Internal(internal) => last_leaf_edge(internal.descend())
 474                 },
 475                 GoDown(bottom) => bottom
 476             },
 477             Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
 478                 Found(kv_handle) => match kv_handle.right_edge().force() {
 479                     Leaf(bottom) => bottom,
 480                     Internal(internal) => first_leaf_edge(internal.descend())
 481                 },
 482                 GoDown(bottom) => bottom
 483             },
 484             Unbounded => first_leaf_edge(self.root.as_ref())
 485         };
 486
 487         let back = match max {
 488             Included(key) => match search::search_tree(self.root.as_ref(), key) {
 489                 Found(kv_handle) => match kv_handle.right_edge().force() {
 490                     Leaf(bottom) => bottom,
 491                     Internal(internal) => first_leaf_edge(internal.descend())
 492                 },
 493                 GoDown(bottom) => bottom
 494             },
 495             Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
 496                 Found(kv_handle) => match kv_handle.left_edge().force() {
 497                     Leaf(bottom) => bottom,
 498                     Internal(internal) => last_leaf_edge(internal.descend())
 499                 },
 500                 GoDown(bottom) => bottom
 501             },
 502             Unbounded => last_leaf_edge(self.root.as_ref())
 503         };
 504
 505         Range {
 506             front: front,
 507             back: back
 508         }
 509     }
 510
 511     /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
 512     /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
 513     /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
 514     /// Thus range(Unbounded, Unbounded) will yield the whole collection.
 515     ///
 516     /// # Examples
 517     ///
 518     /// ```
 519     /// #![feature(btree_range, collections_bound)]
 520     ///
 521     /// use std::collections::BTreeMap;
 522     /// use std::collections::Bound::{Included, Excluded};
 523     ///
 524     /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
 525     ///                                                                       .map(|&s| (s, 0))
 526     ///                                                                       .collect();
 527     /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
 528     ///     *balance += 100;
 529     /// }
 530     /// for (name, balance) in &map {
 531     ///     println!("{} => {}", name, balance);
 532     /// }
 533     /// ```
 534     #[unstable(feature = "btree_range",
 535                reason = "matches collection reform specification, waiting for dust to settle",
 536                issue = "27787")]
 537     pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
 538                                                            min: Bound<&Min>,
 539                                                            max: Bound<&Max>)
 540                                                            -> RangeMut<K, V>
 541         where K: Borrow<Min> + Borrow<Max>,
 542     {
 543         let root1 = self.root.as_mut();
 544         let root2 = unsafe { ptr::read(&root1) };
 545
 546         let front = match min {
 547             Included(key) => match search::search_tree(root1, key) {
 548                 Found(kv_handle) => match kv_handle.left_edge().force() {
 549                     Leaf(bottom) => bottom,
 550                     Internal(internal) => last_leaf_edge(internal.descend())
 551                 },
 552                 GoDown(bottom) => bottom
 553             },
 554             Excluded(key) => match search::search_tree(root1, key) {
 555                 Found(kv_handle) => match kv_handle.right_edge().force() {
 556                     Leaf(bottom) => bottom,
 557                     Internal(internal) => first_leaf_edge(internal.descend())
 558                 },
 559                 GoDown(bottom) => bottom
 560             },
 561             Unbounded => first_leaf_edge(root1)
 562         };
 563
 564         let back = match max {
 565             Included(key) => match search::search_tree(root2, key) {
 566                 Found(kv_handle) => match kv_handle.right_edge().force() {
 567                     Leaf(bottom) => bottom,
 568                     Internal(internal) => first_leaf_edge(internal.descend())
 569                 },
 570                 GoDown(bottom) => bottom
 571             },
 572             Excluded(key) => match search::search_tree(root2, key) {
 573                 Found(kv_handle) => match kv_handle.left_edge().force() {
 574                     Leaf(bottom) => bottom,
 575                     Internal(internal) => last_leaf_edge(internal.descend())
 576                 },
 577                 GoDown(bottom) => bottom
 578             },
 579             Unbounded => last_leaf_edge(root2)
 580         };
 581
 582         RangeMut {
 583             front: front,
 584             back: back,
 585             _marker: PhantomData
 586         }
 587     }
 588
 589     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 590     ///
 591     /// # Examples
 592     ///
 593     /// ```
 594     /// use std::collections::BTreeMap;
 595     ///
 596     /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
 597     ///
 598     /// // count the number of occurrences of letters in the vec
 599     /// for x in vec!["a","b","a","c","a","b"] {
 600     ///     *count.entry(x).or_insert(0) += 1;
 601     /// }
 602     ///
 603     /// assert_eq!(count["a"], 3);
 604     /// ```
 605     #[stable(feature = "rust1", since = "1.0.0")]
 606     pub fn entry(&mut self, key: K) -> Entry<K, V> {
 607         match search::search_tree(self.root.as_mut(), &key) {
 608             Found(handle) => Occupied(OccupiedEntry {
 609                 handle: handle,
 610                 length: &mut self.length,
 611                 _marker: PhantomData,
 612             }),
 613             GoDown(handle) => Vacant(VacantEntry {
 614                 key: key,
 615                 handle: handle,
 616                 length: &mut self.length,
 617                 _marker: PhantomData,
 618             })
 619         }
 620     }
 621 }
 622
 623 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
 624     type Item = (&'a K, &'a V);
 625     type IntoIter = Iter<'a, K, V>;
 626
 627     fn into_iter(self) -> Iter<'a, K, V> {
 628         self.iter()
 629     }
 630 }
 631
 632 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
 633     type Item = (&'a K, &'a V);
 634
 635     fn next(&mut self) -> Option<(&'a K, &'a V)> {
 636         if self.length == 0 {
 637             None
 638         } else {
 639             self.length -= 1;
 640             unsafe { Some(self.range.next_unchecked()) }
 641         }
 642     }
 643
 644     fn size_hint(&self) -> (usize, Option<usize>) {
 645         (self.length, Some(self.length))
 646     }
 647 }
 648
 649 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
 650     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
 651         if self.length == 0 {
 652             None
 653         } else {
 654             self.length -= 1;
 655             unsafe { Some(self.range.next_back_unchecked()) }
 656         }
 657     }
 658 }
 659
 660 impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
 661     fn len(&self) -> usize { self.length }
 662 }
 663
 664 impl<'a, K, V> Clone for Iter<'a, K, V> {
 665     fn clone(&self) -> Iter<'a, K, V> {
 666         Iter {
 667             range: self.range.clone(),
 668             length: self.length
 669         }
 670     }
 671 }
 672
 673 impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
 674     type Item = (&'a K, &'a mut V);
 675     type IntoIter = IterMut<'a, K, V>;
 676
 677     fn into_iter(self) -> IterMut<'a, K, V> {
 678         self.iter_mut()
 679     }
 680 }
 681
 682 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
 683     type Item = (&'a K, &'a mut V);
 684
 685     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
 686         if self.length == 0 {
 687             None
 688         } else {
 689             self.length -= 1;
 690             unsafe { Some(self.range.next_unchecked()) }
 691         }
 692     }
 693
 694     fn size_hint(&self) -> (usize, Option<usize>) {
 695         (self.length, Some(self.length))
 696     }
 697 }
 698
 699 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
 700     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
 701         if self.length == 0 {
 702             None
 703         } else {
 704             self.length -= 1;
 705             unsafe { Some(self.range.next_back_unchecked()) }
 706         }
 707     }
 708 }
 709
 710 impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
 711     fn len(&self) -> usize { self.length }
 712 }
 713
 714 impl<K, V> IntoIterator for BTreeMap<K, V> {
 715     type Item = (K, V);
 716     type IntoIter = IntoIter<K, V>;
 717
 718     fn into_iter(self) -> IntoIter<K, V> {
 719         let root1 = unsafe { ptr::read(&self.root).into_ref() };
 720         let root2 = unsafe { ptr::read(&self.root).into_ref() };
 721         let len = self.length;
 722         mem::forget(self);
 723
 724         IntoIter {
 725             front: first_leaf_edge(root1),
 726             back: last_leaf_edge(root2),
 727             length: len
 728         }
 729     }
 730 }
 731
 732 impl<K, V> Drop for IntoIter<K, V> {
 733     fn drop(&mut self) {
 734         for _ in &mut *self { }
 735         unsafe {
 736             let leaf_node = ptr::read(&self.front).into_node();
 737             if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
 738                 let mut cur_node = first_parent.into_node();
 739                 while let Some(parent) = cur_node.deallocate_and_ascend() {
 740                     cur_node = parent.into_node()
 741                 }
 742             }
 743         }
 744     }
 745 }
 746
 747 impl<K, V> Iterator for IntoIter<K, V> {
 748     type Item = (K, V);
 749
 750     fn next(&mut self) -> Option<(K, V)> {
 751         if self.length == 0 {
 752             return None;
 753         } else {
 754             self.length -= 1;
 755         }
 756
 757         let handle = unsafe { ptr::read(&self.front) };
 758
 759         let mut cur_handle = match handle.right_kv() {
 760             Ok(kv) => {
 761                 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 762                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 763                 self.front = kv.right_edge();
 764                 return Some((k, v));
 765             },
 766             Err(last_edge) => unsafe {
 767                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
 768             }
 769         };
 770
 771         loop {
 772             match cur_handle.right_kv() {
 773                 Ok(kv) => {
 774                     let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 775                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 776                     self.front = first_leaf_edge(kv.right_edge().descend());
 777                     return Some((k, v));
 778                 },
 779                 Err(last_edge) => unsafe {
 780                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
 781                 }
 782             }
 783         }
 784     }
 785
 786     fn size_hint(&self) -> (usize, Option<usize>) {
 787         (self.length, Some(self.length))
 788     }
 789 }
 790
 791 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
 792     fn next_back(&mut self) -> Option<(K, V)> {
 793         if self.length == 0 {
 794             return None;
 795         } else {
 796             self.length -= 1;
 797         }
 798
 799         let handle = unsafe { ptr::read(&self.back) };
 800
 801         let mut cur_handle = match handle.left_kv() {
 802             Ok(kv) => {
 803                 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 804                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 805                 self.back = kv.left_edge();
 806                 return Some((k, v));
 807             },
 808             Err(last_edge) => unsafe {
 809                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
 810             }
 811         };
 812
 813         loop {
 814             match cur_handle.left_kv() {
 815                 Ok(kv) => {
 816                     let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 817                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 818                     self.back = last_leaf_edge(kv.left_edge().descend());
 819                     return Some((k, v));
 820                 },
 821                 Err(last_edge) => unsafe {
 822                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
 823                 }
 824             }
 825         }
 826     }
 827 }
 828
 829 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
 830     fn len(&self) -> usize { self.length }
 831 }
 832
 833 impl<'a, K, V> Iterator for Keys<'a, K, V> {
 834     type Item = &'a K;
 835
 836     fn next(&mut self) -> Option<&'a K> {
 837         self.inner.next().map(|(k, _)| k)
 838     }
 839
 840     fn size_hint(&self) -> (usize, Option<usize>) {
 841         self.inner.size_hint()
 842     }
 843 }
 844
 845 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
 846     fn next_back(&mut self) -> Option<&'a K> {
 847         self.inner.next_back().map(|(k, _)| k)
 848     }
 849 }
 850
 851 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
 852     fn len(&self) -> usize {
 853         self.inner.len()
 854     }
 855 }
 856
 857 impl<'a, K, V> Clone for Keys<'a, K, V> {
 858     fn clone(&self) -> Keys<'a, K, V> {
 859         Keys {
 860             inner: self.inner.clone()
 861         }
 862     }
 863 }
 864
 865 impl<'a, K, V> Iterator for Values<'a, K, V> {
 866     type Item = &'a V;
 867
 868     fn next(&mut self) -> Option<&'a V> {
 869         self.inner.next().map(|(_, v)| v)
 870     }
 871
 872     fn size_hint(&self) -> (usize, Option<usize>) {
 873         self.inner.size_hint()
 874     }
 875 }
 876
 877 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
 878     fn next_back(&mut self) -> Option<&'a V> {
 879         self.inner.next_back().map(|(_, v)| v)
 880     }
 881 }
 882
 883 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
 884     fn len(&self) -> usize {
 885         self.inner.len()
 886     }
 887 }
 888
 889 impl<'a, K, V> Clone for Values<'a, K, V> {
 890     fn clone(&self) -> Values<'a, K, V> {
 891         Values {
 892             inner: self.inner.clone()
 893         }
 894     }
 895 }
 896
 897 impl<'a, K, V> Iterator for Range<'a, K, V> {
 898     type Item = (&'a K, &'a V);
 899
 900     fn next(&mut self) -> Option<(&'a K, &'a V)> {
 901         if self.front == self.back {
 902             None
 903         } else {
 904             unsafe { Some(self.next_unchecked()) }
 905         }
 906     }
 907 }
 908
 909 impl<'a, K, V> Range<'a, K, V> {
 910     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
 911         let handle = self.front;
 912
 913         let mut cur_handle = match handle.right_kv() {
 914             Ok(kv) => {
 915                 let ret = kv.into_kv();
 916                 self.front = kv.right_edge();
 917                 return ret;
 918             },
 919             Err(last_edge) => {
 920                 let next_level = last_edge.into_node().ascend().ok();
 921                 unwrap_unchecked(next_level)
 922             }
 923         };
 924
 925         loop {
 926             match cur_handle.right_kv() {
 927                 Ok(kv) => {
 928                     let ret = kv.into_kv();
 929                     self.front = first_leaf_edge(kv.right_edge().descend());
 930                     return ret;
 931                 },
 932                 Err(last_edge) => {
 933                     let next_level = last_edge.into_node().ascend().ok();
 934                     cur_handle = unwrap_unchecked(next_level);
 935                 }
 936             }
 937         }
 938     }
 939 }
 940
 941 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
 942     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
 943         if self.front == self.back {
 944             None
 945         } else {
 946             unsafe { Some(self.next_back_unchecked()) }
 947         }
 948     }
 949 }
 950
 951 impl<'a, K, V> Range<'a, K, V> {
 952     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
 953         let handle = self.back;
 954
 955         let mut cur_handle = match handle.left_kv() {
 956             Ok(kv) => {
 957                 let ret = kv.into_kv();
 958                 self.back = kv.left_edge();
 959                 return ret;
 960             },
 961             Err(last_edge) => {
 962                 let next_level = last_edge.into_node().ascend().ok();
 963                 unwrap_unchecked(next_level)
 964             }
 965         };
 966
 967         loop {
 968             match cur_handle.left_kv() {
 969                 Ok(kv) => {
 970                     let ret = kv.into_kv();
 971                     self.back = last_leaf_edge(kv.left_edge().descend());
 972                     return ret;
 973                 },
 974                 Err(last_edge) => {
 975                     let next_level = last_edge.into_node().ascend().ok();
 976                     cur_handle = unwrap_unchecked(next_level);
 977                 }
 978             }
 979         }
 980     }
 981 }
 982
 983 impl<'a, K, V> Clone for Range<'a, K, V> {
 984     fn clone(&self) -> Range<'a, K, V> {
 985         Range {
 986             front: self.front,
 987             back: self.back
 988         }
 989     }
 990 }
 991
 992 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
 993     type Item = (&'a K, &'a mut V);
 994
 995     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
 996         if self.front == self.back {
 997             None
 998         } else {
 999             unsafe { Some (self.next_unchecked()) }
1000         }
1001     }
1002 }
1003
1004 impl<'a, K, V> RangeMut<'a, K, V> {
1005     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
1006         let handle = ptr::read(&self.front);
1007
1008         let mut cur_handle = match handle.right_kv() {
1009             Ok(kv) => {
1010                 let (k, v) = ptr::read(&kv).into_kv_mut();
1011                 self.front = kv.right_edge();
1012                 return (k, v);
1013             },
1014             Err(last_edge) => {
1015                 let next_level = last_edge.into_node().ascend().ok();
1016                 unwrap_unchecked(next_level)
1017             }
1018         };
1019
1020         loop {
1021             match cur_handle.right_kv() {
1022                 Ok(kv) => {
1023                     let (k, v) = ptr::read(&kv).into_kv_mut();
1024                     self.front = first_leaf_edge(kv.right_edge().descend());
1025                     return (k, v);
1026                 },
1027                 Err(last_edge) => {
1028                     let next_level = last_edge.into_node().ascend().ok();
1029                     cur_handle = unwrap_unchecked(next_level);
1030                 }
1031             }
1032         }
1033     }
1034 }
1035
1036 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1037     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1038         if self.front == self.back {
1039             None
1040         } else {
1041             unsafe { Some(self.next_back_unchecked()) }
1042         }
1043     }
1044 }
1045
1046 impl<'a, K, V> RangeMut<'a, K, V> {
1047     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
1048         let handle = ptr::read(&self.back);
1049
1050         let mut cur_handle = match handle.left_kv() {
1051             Ok(kv) => {
1052                 let (k, v) = ptr::read(&kv).into_kv_mut();
1053                 self.back = kv.left_edge();
1054                 return (k, v);
1055             },
1056             Err(last_edge) => {
1057                 let next_level = last_edge.into_node().ascend().ok();
1058                 unwrap_unchecked(next_level)
1059             }
1060         };
1061
1062         loop {
1063             match cur_handle.left_kv() {
1064                 Ok(kv) => {
1065                     let (k, v) = ptr::read(&kv).into_kv_mut();
1066                     self.back = last_leaf_edge(kv.left_edge().descend());
1067                     return (k, v);
1068                 },
1069                 Err(last_edge) => {
1070                     let next_level = last_edge.into_node().ascend().ok();
1071                     cur_handle = unwrap_unchecked(next_level);
1072                 }
1073             }
1074         }
1075     }
1076 }
1077
1078 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1079     fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
1080         let mut map = BTreeMap::new();
1081         map.extend(iter);
1082         map
1083     }
1084 }
1085
1086 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1087     #[inline]
1088     fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1089         for (k, v) in iter {
1090             self.insert(k, v);
1091         }
1092     }
1093 }
1094
1095 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1096     fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
1097         self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1098     }
1099 }
1100
1101 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1102     fn hash<H: Hasher>(&self, state: &mut H) {
1103         for elt in self {
1104             elt.hash(state);
1105         }
1106     }
1107 }
1108
1109 impl<K: Ord, V> Default for BTreeMap<K, V> {
1110     fn default() -> BTreeMap<K, V> {
1111         BTreeMap::new()
1112     }
1113 }
1114
1115 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
1116     fn eq(&self, other: &BTreeMap<K, V>) -> bool {
1117         self.len() == other.len() &&
1118             self.iter().zip(other).all(|(a, b)| a == b)
1119     }
1120 }
1121
1122 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
1123
1124 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
1125     #[inline]
1126     fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
1127         self.iter().partial_cmp(other.iter())
1128     }
1129 }
1130
1131 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
1132     #[inline]
1133     fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
1134         self.iter().cmp(other.iter())
1135     }
1136 }
1137
1138 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
1139     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1140         f.debug_map().entries(self.iter()).finish()
1141     }
1142 }
1143
1144 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
1145     where K: Borrow<Q>, Q: Ord
1146 {
1147     type Output = V;
1148
1149     #[inline]
1150     fn index(&self, key: &Q) -> &V {
1151         self.get(key).expect("no entry found for key")
1152     }
1153 }
1154
1155 fn first_leaf_edge<BorrowType, K, V>(
1156         mut node: NodeRef<BorrowType,
1157                           K, V,
1158                           marker::LeafOrInternal>
1159         ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1160     loop {
1161         match node.force() {
1162             Leaf(leaf) => return leaf.first_edge(),
1163             Internal(internal) => {
1164                 node = internal.first_edge().descend();
1165             }
1166         }
1167     }
1168 }
1169
1170 fn last_leaf_edge<BorrowType, K, V>(
1171         mut node: NodeRef<BorrowType,
1172                           K, V,
1173                           marker::LeafOrInternal>
1174         ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1175     loop {
1176         match node.force() {
1177             Leaf(leaf) => return leaf.last_edge(),
1178             Internal(internal) => {
1179                 node = internal.last_edge().descend();
1180             }
1181         }
1182     }
1183 }
1184
1185 #[inline(always)]
1186 unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
1187     val.unwrap_or_else(|| {
1188         if cfg!(debug_assertions) {
1189             panic!("'unchecked' unwrap on None in BTreeMap");
1190         } else {
1191             intrinsics::unreachable();
1192         }
1193     })
1194 }
1195
1196 impl<K, V> BTreeMap<K, V> {
1197     /// Gets an iterator over the entries of the map, sorted by key.
1198     ///
1199     /// # Examples
1200     ///
1201     /// ```
1202     /// use std::collections::BTreeMap;
1203     ///
1204     /// let mut map = BTreeMap::new();
1205     /// map.insert(3, "c");
1206     /// map.insert(2, "b");
1207     /// map.insert(1, "a");
1208     ///
1209     /// for (key, value) in map.iter() {
1210     ///     println!("{}: {}", key, value);
1211     /// }
1212     ///
1213     /// let (first_key, first_value) = map.iter().next().unwrap();
1214     /// assert_eq!((*first_key, *first_value), (1, "a"));
1215     /// ```
1216     #[stable(feature = "rust1", since = "1.0.0")]
1217     pub fn iter(&self) -> Iter<K, V> {
1218         Iter {
1219             range: Range {
1220                 front: first_leaf_edge(self.root.as_ref()),
1221                 back: last_leaf_edge(self.root.as_ref())
1222             },
1223             length: self.length
1224         }
1225     }
1226
1227     /// Gets a mutable iterator over the entries of the map, sorted by key.
1228     ///
1229     /// # Examples
1230     ///
1231     /// ```
1232     /// use std::collections::BTreeMap;
1233     ///
1234     /// let mut map = BTreeMap::new();
1235     /// map.insert("a", 1);
1236     /// map.insert("b", 2);
1237     /// map.insert("c", 3);
1238     ///
1239     /// // add 10 to the value if the key isn't "a"
1240     /// for (key, value) in map.iter_mut() {
1241     ///     if key != &"a" {
1242     ///         *value += 10;
1243     ///     }
1244     /// }
1245     /// ```
1246     #[stable(feature = "rust1", since = "1.0.0")]
1247     pub fn iter_mut(&mut self) -> IterMut<K, V> {
1248         let root1 = self.root.as_mut();
1249         let root2 = unsafe { ptr::read(&root1) };
1250         IterMut {
1251             range: RangeMut {
1252                 front: first_leaf_edge(root1),
1253                 back: last_leaf_edge(root2),
1254                 _marker: PhantomData,
1255             },
1256             length: self.length
1257         }
1258     }
1259
1260     /// Gets an iterator over the keys of the map, in sorted order.
1261     ///
1262     /// # Examples
1263     ///
1264     /// ```
1265     /// use std::collections::BTreeMap;
1266     ///
1267     /// let mut a = BTreeMap::new();
1268     /// a.insert(2, "b");
1269     /// a.insert(1, "a");
1270     ///
1271     /// let keys: Vec<_> = a.keys().cloned().collect();
1272     /// assert_eq!(keys, [1, 2]);
1273     /// ```
1274     #[stable(feature = "rust1", since = "1.0.0")]
1275     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1276         Keys { inner: self.iter() }
1277     }
1278
1279     /// Gets an iterator over the values of the map, in order by key.
1280     ///
1281     /// # Examples
1282     ///
1283     /// ```
1284     /// use std::collections::BTreeMap;
1285     ///
1286     /// let mut a = BTreeMap::new();
1287     /// a.insert(1, "hello");
1288     /// a.insert(2, "goodbye");
1289     ///
1290     /// let values: Vec<&str> = a.values().cloned().collect();
1291     /// assert_eq!(values, ["hello", "goodbye"]);
1292     /// ```
1293     #[stable(feature = "rust1", since = "1.0.0")]
1294     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1295         Values { inner: self.iter() }
1296     }
1297
1298     /// Returns the number of elements in the map.
1299     ///
1300     /// # Examples
1301     ///
1302     /// ```
1303     /// use std::collections::BTreeMap;
1304     ///
1305     /// let mut a = BTreeMap::new();
1306     /// assert_eq!(a.len(), 0);
1307     /// a.insert(1, "a");
1308     /// assert_eq!(a.len(), 1);
1309     /// ```
1310     #[stable(feature = "rust1", since = "1.0.0")]
1311     pub fn len(&self) -> usize {
1312         self.length
1313     }
1314
1315     /// Returns true if the map contains no elements.
1316     ///
1317     /// # Examples
1318     ///
1319     /// ```
1320     /// use std::collections::BTreeMap;
1321     ///
1322     /// let mut a = BTreeMap::new();
1323     /// assert!(a.is_empty());
1324     /// a.insert(1, "a");
1325     /// assert!(!a.is_empty());
1326     /// ```
1327     #[stable(feature = "rust1", since = "1.0.0")]
1328     pub fn is_empty(&self) -> bool {
1329         self.len() == 0
1330     }
1331 }
1332
1333 impl<'a, K: Ord, V> Entry<'a, K, V> {
1334     /// Ensures a value is in the entry by inserting the default if empty, and returns
1335     /// a mutable reference to the value in the entry.
1336     #[stable(feature = "rust1", since = "1.0.0")]
1337     pub fn or_insert(self, default: V) -> &'a mut V {
1338         match self {
1339             Occupied(entry) => entry.into_mut(),
1340             Vacant(entry) => entry.insert(default),
1341         }
1342     }
1343
1344     /// Ensures a value is in the entry by inserting the result of the default function if empty,
1345     /// and returns a mutable reference to the value in the entry.
1346     #[stable(feature = "rust1", since = "1.0.0")]
1347     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1348         match self {
1349             Occupied(entry) => entry.into_mut(),
1350             Vacant(entry) => entry.insert(default()),
1351         }
1352     }
1353 }
1354
1355 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1356     /// Sets the value of the entry with the VacantEntry's key,
1357     /// and returns a mutable reference to it.
1358     #[stable(feature = "rust1", since = "1.0.0")]
1359     pub fn insert(self, value: V) -> &'a mut V {
1360         *self.length += 1;
1361
1362         let out_ptr;
1363
1364         let mut ins_k;
1365         let mut ins_v;
1366         let mut ins_edge;
1367
1368         let mut cur_parent = match self.handle.insert(self.key, value) {
1369             (Fit(handle), _) => return handle.into_kv_mut().1,
1370             (Split(left, k, v, right), ptr) => {
1371                 ins_k = k;
1372                 ins_v = v;
1373                 ins_edge = right;
1374                 out_ptr = ptr;
1375                 left.ascend().map_err(|n| n.into_root_mut())
1376             }
1377         };
1378
1379         loop {
1380             match cur_parent {
1381                 Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
1382                     Fit(_) => return unsafe { &mut *out_ptr },
1383                     Split(left, k, v, right) => {
1384                         ins_k = k;
1385                         ins_v = v;
1386                         ins_edge = right;
1387                         cur_parent = left.ascend().map_err(|n| n.into_root_mut());
1388                     }
1389                 },
1390                 Err(root) => {
1391                     root.push_level().push(ins_k, ins_v, ins_edge);
1392                     return unsafe { &mut *out_ptr };
1393                 }
1394             }
1395         }
1396     }
1397 }
1398
1399 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1400     /// Gets a reference to the value in the entry.
1401     #[stable(feature = "rust1", since = "1.0.0")]
1402     pub fn get(&self) -> &V {
1403         self.handle.reborrow().into_kv().1
1404     }
1405
1406     /// Gets a mutable reference to the value in the entry.
1407     #[stable(feature = "rust1", since = "1.0.0")]
1408     pub fn get_mut(&mut self) -> &mut V {
1409         self.handle.kv_mut().1
1410     }
1411
1412     /// Converts the entry into a mutable reference to its value.
1413     #[stable(feature = "rust1", since = "1.0.0")]
1414     pub fn into_mut(self) -> &'a mut V {
1415         self.handle.into_kv_mut().1
1416     }
1417
1418     /// Sets the value of the entry with the OccupiedEntry's key,
1419     /// and returns the entry's old value.
1420     #[stable(feature = "rust1", since = "1.0.0")]
1421     pub fn insert(&mut self, value: V) -> V {
1422         mem::replace(self.get_mut(), value)
1423     }
1424
1425     /// Takes the value of the entry out of the map, and returns it.
1426     #[stable(feature = "rust1", since = "1.0.0")]
1427     pub fn remove(self) -> V {
1428         self.remove_kv().1
1429     }
1430
1431     fn remove_kv(self) -> (K, V) {
1432         *self.length -= 1;
1433
1434         let (small_leaf, old_key, old_val) = match self.handle.force() {
1435             Leaf(leaf) => {
1436                 let (hole, old_key, old_val) = leaf.remove();
1437                 (hole.into_node(), old_key, old_val)
1438             },
1439             Internal(mut internal) => {
1440                 let key_loc = internal.kv_mut().0 as *mut K;
1441                 let val_loc = internal.kv_mut().1 as *mut V;
1442
1443                 let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
1444                 let to_remove = unsafe { unwrap_unchecked(to_remove) };
1445
1446                 let (hole, key, val) = to_remove.remove();
1447
1448                 let old_key = unsafe {
1449                     mem::replace(&mut *key_loc, key)
1450                 };
1451                 let old_val = unsafe {
1452                     mem::replace(&mut *val_loc, val)
1453                 };
1454
1455                 (hole.into_node(), old_key, old_val)
1456             }
1457         };
1458
1459         // Handle underflow
1460         let mut cur_node = small_leaf.forget_type();
1461         while cur_node.len() < node::CAPACITY / 2 {
1462             match handle_underfull_node(cur_node) {
1463                 AtRoot => break,
1464                 EmptyParent(_) => unreachable!(),
1465                 Merged(parent) => if parent.len() == 0 {
1466                     // We must be at the root
1467                     parent.into_root_mut().pop_level();
1468                     break;
1469                 } else {
1470                     cur_node = parent.forget_type();
1471                 },
1472                 Stole(_) => break
1473             }
1474         }
1475
1476         (old_key, old_val)
1477     }
1478 }
1479
1480 enum UnderflowResult<'a, K, V> {
1481     AtRoot,
1482     EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1483     Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1484     Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
1485 }
1486
1487 fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
1488                                                  K, V,
1489                                                  marker::LeafOrInternal>)
1490                                                  -> UnderflowResult<'a, K, V> {
1491     let parent = if let Ok(parent) = node.ascend() {
1492         parent
1493     } else {
1494         return AtRoot;
1495     };
1496
1497     let (is_left, mut handle) = match parent.left_kv() {
1498         Ok(left) => (true, left),
1499         Err(parent) => match parent.right_kv() {
1500             Ok(right) => (false, right),
1501             Err(parent) => {
1502                 return EmptyParent(parent.into_node());
1503             }
1504         }
1505     };
1506
1507     if handle.can_merge() {
1508         return Merged(handle.merge().into_node());
1509     } else {
1510         unsafe {
1511             let (k, v, edge) = if is_left {
1512                 handle.reborrow_mut().left_edge().descend().pop()
1513             } else {
1514                 handle.reborrow_mut().right_edge().descend().pop_front()
1515             };
1516
1517             let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
1518             let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
1519
1520             // FIXME: reuse cur_node?
1521             if is_left {
1522                 match handle.reborrow_mut().right_edge().descend().force() {
1523                     Leaf(mut leaf) => leaf.push_front(k, v),
1524                     Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
1525                 }
1526             } else {
1527                 match handle.reborrow_mut().left_edge().descend().force() {
1528                     Leaf(mut leaf) => leaf.push(k, v),
1529                     Internal(mut internal) => internal.push(k, v, edge.unwrap())
1530                 }
1531             }
1532         }
1533
1534         return Stole(handle.into_node());
1535     }
1536 }