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