src/liballoc/collections/btree/map.rs

   1 use core::borrow::Borrow;
   2 use core::cmp::Ordering;
   3 use core::fmt::Debug;
   4 use core::hash::{Hash, Hasher};
   5 use core::iter::{FromIterator, Peekable, FusedIterator};
   6 use core::marker::PhantomData;
   7 use core::ops::Bound::{Excluded, Included, Unbounded};
   8 use core::ops::{Index, RangeBounds};
   9 use core::{fmt, intrinsics, mem, ptr};
  10
  11 use super::node::{self, Handle, NodeRef, marker, InsertResult::*, ForceResult::*};
  12 use super::search::{self, SearchResult::*};
  13
  14 use UnderflowResult::*;
  15 use Entry::*;
  16
  17 /// A map based on a B-Tree.
  18 ///
  19 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
  20 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
  21 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
  22 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
  23 /// is done is *very* inefficient for modern computer architectures. In particular, every element
  24 /// is stored in its own individually heap-allocated node. This means that every single insertion
  25 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
  26 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
  27 /// the BST strategy.
  28 ///
  29 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
  30 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
  31 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
  32 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
  33 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
  34 /// the node using binary search. As a compromise, one could also perform a linear search
  35 /// that initially only checks every i<sup>th</sup> element for some choice of i.
  36 ///
  37 /// Currently, our implementation simply performs naive linear search. This provides excellent
  38 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
  39 /// would like to further explore choosing the optimal search strategy based on the choice of B,
  40 /// and possibly other factors. Using linear search, searching for a random element is expected
  41 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
  42 /// however, performance is excellent.
  43 ///
  44 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
  45 /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
  46 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
  47 ///
  48 /// [`Ord`]: ../../std/cmp/trait.Ord.html
  49 /// [`Cell`]: ../../std/cell/struct.Cell.html
  50 /// [`RefCell`]: ../../std/cell/struct.RefCell.html
  51 ///
  52 /// # Examples
  53 ///
  54 /// ```
  55 /// use std::collections::BTreeMap;
  56 ///
  57 /// // type inference lets us omit an explicit type signature (which
  58 /// // would be `BTreeMap<&str, &str>` in this example).
  59 /// let mut movie_reviews = BTreeMap::new();
  60 ///
  61 /// // review some movies.
  62 /// movie_reviews.insert("Office Space",       "Deals with real issues in the workplace.");
  63 /// movie_reviews.insert("Pulp Fiction",       "Masterpiece.");
  64 /// movie_reviews.insert("The Godfather",      "Very enjoyable.");
  65 /// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
  66 ///
  67 /// // check for a specific one.
  68 /// if !movie_reviews.contains_key("Les Misérables") {
  69 ///     println!("We've got {} reviews, but Les Misérables ain't one.",
  70 ///              movie_reviews.len());
  71 /// }
  72 ///
  73 /// // oops, this review has a lot of spelling mistakes, let's delete it.
  74 /// movie_reviews.remove("The Blues Brothers");
  75 ///
  76 /// // look up the values associated with some keys.
  77 /// let to_find = ["Up!", "Office Space"];
  78 /// for book in &to_find {
  79 ///     match movie_reviews.get(book) {
  80 ///        Some(review) => println!("{}: {}", book, review),
  81 ///        None => println!("{} is unreviewed.", book)
  82 ///     }
  83 /// }
  84 ///
  85 /// // Look up the value for a key (will panic if the key is not found).
  86 /// println!("Movie review: {}", movie_reviews["Office Space"]);
  87 ///
  88 /// // iterate over everything.
  89 /// for (movie, review) in &movie_reviews {
  90 ///     println!("{}: \"{}\"", movie, review);
  91 /// }
  92 /// ```
  93 ///
  94 /// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows
  95 /// for more complex methods of getting, setting, updating and removing keys and
  96 /// their values:
  97 ///
  98 /// ```
  99 /// use std::collections::BTreeMap;
 100 ///
 101 /// // type inference lets us omit an explicit type signature (which
 102 /// // would be `BTreeMap<&str, u8>` in this example).
 103 /// let mut player_stats = BTreeMap::new();
 104 ///
 105 /// fn random_stat_buff() -> u8 {
 106 ///     // could actually return some random value here - let's just return
 107 ///     // some fixed value for now
 108 ///     42
 109 /// }
 110 ///
 111 /// // insert a key only if it doesn't already exist
 112 /// player_stats.entry("health").or_insert(100);
 113 ///
 114 /// // insert a key using a function that provides a new value only if it
 115 /// // doesn't already exist
 116 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
 117 ///
 118 /// // update a key, guarding against the key possibly not being set
 119 /// let stat = player_stats.entry("attack").or_insert(100);
 120 /// *stat += random_stat_buff();
 121 /// ```
 122 #[stable(feature = "rust1", since = "1.0.0")]
 123 pub struct BTreeMap<K, V> {
 124     root: node::Root<K, V>,
 125     length: usize,
 126 }
 127
 128 #[stable(feature = "btree_drop", since = "1.7.0")]
 129 unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for BTreeMap<K, V> {
 130     fn drop(&mut self) {
 131         unsafe {
 132             drop(ptr::read(self).into_iter());
 133         }
 134     }
 135 }
 136
 137 #[stable(feature = "rust1", since = "1.0.0")]
 138 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
 139     fn clone(&self) -> BTreeMap<K, V> {
 140         fn clone_subtree<'a, K: Clone, V: Clone>(
 141             node: node::NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>
 142         ) -> BTreeMap<K, V>
 143         where K: 'a, V: 'a,
 144         {
 145             match node.force() {
 146                 Leaf(leaf) => {
 147                     let mut out_tree = BTreeMap {
 148                         root: node::Root::new_leaf(),
 149                         length: 0,
 150                     };
 151
 152                     {
 153                         let mut out_node = match out_tree.root.as_mut().force() {
 154                             Leaf(leaf) => leaf,
 155                             Internal(_) => unreachable!(),
 156                         };
 157
 158                         let mut in_edge = leaf.first_edge();
 159                         while let Ok(kv) = in_edge.right_kv() {
 160                             let (k, v) = kv.into_kv();
 161                             in_edge = kv.right_edge();
 162
 163                             out_node.push(k.clone(), v.clone());
 164                             out_tree.length += 1;
 165                         }
 166                     }
 167
 168                     out_tree
 169                 }
 170                 Internal(internal) => {
 171                     let mut out_tree = clone_subtree(internal.first_edge().descend());
 172
 173                     {
 174                         let mut out_node = out_tree.root.push_level();
 175                         let mut in_edge = internal.first_edge();
 176                         while let Ok(kv) = in_edge.right_kv() {
 177                             let (k, v) = kv.into_kv();
 178                             in_edge = kv.right_edge();
 179
 180                             let k = (*k).clone();
 181                             let v = (*v).clone();
 182                             let subtree = clone_subtree(in_edge.descend());
 183
 184                             // We can't destructure subtree directly
 185                             // because BTreeMap implements Drop
 186                             let (subroot, sublength) = unsafe {
 187                                 let root = ptr::read(&subtree.root);
 188                                 let length = subtree.length;
 189                                 mem::forget(subtree);
 190                                 (root, length)
 191                             };
 192
 193                             out_node.push(k, v, subroot);
 194                             out_tree.length += 1 + sublength;
 195                         }
 196                     }
 197
 198                     out_tree
 199                 }
 200             }
 201         }
 202
 203         if self.len() == 0 {
 204             // Ideally we'd call `BTreeMap::new` here, but that has the `K:
 205             // Ord` constraint, which this method lacks.
 206             BTreeMap {
 207                 root: node::Root::shared_empty_root(),
 208                 length: 0,
 209             }
 210         } else {
 211             clone_subtree(self.root.as_ref())
 212         }
 213     }
 214 }
 215
 216 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
 217     where K: Borrow<Q> + Ord,
 218           Q: Ord
 219 {
 220     type Key = K;
 221
 222     fn get(&self, key: &Q) -> Option<&K> {
 223         match search::search_tree(self.root.as_ref(), key) {
 224             Found(handle) => Some(handle.into_kv().0),
 225             GoDown(_) => None,
 226         }
 227     }
 228
 229     fn take(&mut self, key: &Q) -> Option<K> {
 230         match search::search_tree(self.root.as_mut(), key) {
 231             Found(handle) => {
 232                 Some(OccupiedEntry {
 233                          handle,
 234                          length: &mut self.length,
 235                          _marker: PhantomData,
 236                      }
 237                      .remove_kv()
 238                      .0)
 239             }
 240             GoDown(_) => None,
 241         }
 242     }
 243
 244     fn replace(&mut self, key: K) -> Option<K> {
 245         self.ensure_root_is_owned();
 246         match search::search_tree::<marker::Mut<'_>, K, (), K>(self.root.as_mut(), &key) {
 247             Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
 248             GoDown(handle) => {
 249                 VacantEntry {
 250                     key,
 251                     handle,
 252                     length: &mut self.length,
 253                     _marker: PhantomData,
 254                 }
 255                 .insert(());
 256                 None
 257             }
 258         }
 259     }
 260 }
 261
 262 /// An iterator over the entries of a `BTreeMap`.
 263 ///
 264 /// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its
 265 /// documentation for more.
 266 ///
 267 /// [`iter`]: struct.BTreeMap.html#method.iter
 268 /// [`BTreeMap`]: struct.BTreeMap.html
 269 #[stable(feature = "rust1", since = "1.0.0")]
 270 pub struct Iter<'a, K: 'a, V: 'a> {
 271     range: Range<'a, K, V>,
 272     length: usize,
 273 }
 274
 275 #[stable(feature = "collection_debug", since = "1.17.0")]
 276 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
 277     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 278         f.debug_list().entries(self.clone()).finish()
 279     }
 280 }
 281
 282 /// A mutable iterator over the entries of a `BTreeMap`.
 283 ///
 284 /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
 285 /// documentation for more.
 286 ///
 287 /// [`iter_mut`]: struct.BTreeMap.html#method.iter_mut
 288 /// [`BTreeMap`]: struct.BTreeMap.html
 289 #[stable(feature = "rust1", since = "1.0.0")]
 290 #[derive(Debug)]
 291 pub struct IterMut<'a, K: 'a, V: 'a> {
 292     range: RangeMut<'a, K, V>,
 293     length: usize,
 294 }
 295
 296 /// An owning iterator over the entries of a `BTreeMap`.
 297 ///
 298 /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`][`BTreeMap`]
 299 /// (provided by the `IntoIterator` trait). See its documentation for more.
 300 ///
 301 /// [`into_iter`]: struct.BTreeMap.html#method.into_iter
 302 /// [`BTreeMap`]: struct.BTreeMap.html
 303 #[stable(feature = "rust1", since = "1.0.0")]
 304 pub struct IntoIter<K, V> {
 305     front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
 306     back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
 307     length: usize,
 308 }
 309
 310 #[stable(feature = "collection_debug", since = "1.17.0")]
 311 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
 312     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 313         let range = Range {
 314             front: self.front.reborrow(),
 315             back: self.back.reborrow(),
 316         };
 317         f.debug_list().entries(range).finish()
 318     }
 319 }
 320
 321 /// An iterator over the keys of a `BTreeMap`.
 322 ///
 323 /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
 324 /// documentation for more.
 325 ///
 326 /// [`keys`]: struct.BTreeMap.html#method.keys
 327 /// [`BTreeMap`]: struct.BTreeMap.html
 328 #[stable(feature = "rust1", since = "1.0.0")]
 329 pub struct Keys<'a, K: 'a, V: 'a> {
 330     inner: Iter<'a, K, V>,
 331 }
 332
 333 #[stable(feature = "collection_debug", since = "1.17.0")]
 334 impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
 335     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 336         f.debug_list().entries(self.clone()).finish()
 337     }
 338 }
 339
 340 /// An iterator over the values of a `BTreeMap`.
 341 ///
 342 /// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its
 343 /// documentation for more.
 344 ///
 345 /// [`values`]: struct.BTreeMap.html#method.values
 346 /// [`BTreeMap`]: struct.BTreeMap.html
 347 #[stable(feature = "rust1", since = "1.0.0")]
 348 pub struct Values<'a, K: 'a, V: 'a> {
 349     inner: Iter<'a, K, V>,
 350 }
 351
 352 #[stable(feature = "collection_debug", since = "1.17.0")]
 353 impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
 354     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 355         f.debug_list().entries(self.clone()).finish()
 356     }
 357 }
 358
 359 /// A mutable iterator over the values of a `BTreeMap`.
 360 ///
 361 /// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its
 362 /// documentation for more.
 363 ///
 364 /// [`values_mut`]: struct.BTreeMap.html#method.values_mut
 365 /// [`BTreeMap`]: struct.BTreeMap.html
 366 #[stable(feature = "map_values_mut", since = "1.10.0")]
 367 #[derive(Debug)]
 368 pub struct ValuesMut<'a, K: 'a, V: 'a> {
 369     inner: IterMut<'a, K, V>,
 370 }
 371
 372 /// An iterator over a sub-range of entries in a `BTreeMap`.
 373 ///
 374 /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its
 375 /// documentation for more.
 376 ///
 377 /// [`range`]: struct.BTreeMap.html#method.range
 378 /// [`BTreeMap`]: struct.BTreeMap.html
 379 #[stable(feature = "btree_range", since = "1.17.0")]
 380 pub struct Range<'a, K: 'a, V: 'a> {
 381     front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
 382     back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
 383 }
 384
 385 #[stable(feature = "collection_debug", since = "1.17.0")]
 386 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Range<'_, K, V> {
 387     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 388         f.debug_list().entries(self.clone()).finish()
 389     }
 390 }
 391
 392 /// A mutable iterator over a sub-range of entries in a `BTreeMap`.
 393 ///
 394 /// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its
 395 /// documentation for more.
 396 ///
 397 /// [`range_mut`]: struct.BTreeMap.html#method.range_mut
 398 /// [`BTreeMap`]: struct.BTreeMap.html
 399 #[stable(feature = "btree_range", since = "1.17.0")]
 400 pub struct RangeMut<'a, K: 'a, V: 'a> {
 401     front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 402     back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 403
 404     // Be invariant in `K` and `V`
 405     _marker: PhantomData<&'a mut (K, V)>,
 406 }
 407
 408 #[stable(feature = "collection_debug", since = "1.17.0")]
 409 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> {
 410     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 411         let range = Range {
 412             front: self.front.reborrow(),
 413             back: self.back.reborrow(),
 414         };
 415         f.debug_list().entries(range).finish()
 416     }
 417 }
 418
 419 /// A view into a single entry in a map, which may either be vacant or occupied.
 420 ///
 421 /// This `enum` is constructed from the [`entry`] method on [`BTreeMap`].
 422 ///
 423 /// [`BTreeMap`]: struct.BTreeMap.html
 424 /// [`entry`]: struct.BTreeMap.html#method.entry
 425 #[stable(feature = "rust1", since = "1.0.0")]
 426 pub enum Entry<'a, K: 'a, V: 'a> {
 427     /// A vacant entry.
 428     #[stable(feature = "rust1", since = "1.0.0")]
 429     Vacant(#[stable(feature = "rust1", since = "1.0.0")]
 430            VacantEntry<'a, K, V>),
 431
 432     /// An occupied entry.
 433     #[stable(feature = "rust1", since = "1.0.0")]
 434     Occupied(#[stable(feature = "rust1", since = "1.0.0")]
 435              OccupiedEntry<'a, K, V>),
 436 }
 437
 438 #[stable(feature= "debug_btree_map", since = "1.12.0")]
 439 impl<K: Debug + Ord, V: Debug> Debug for Entry<'_, K, V> {
 440     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 441         match *self {
 442             Vacant(ref v) => f.debug_tuple("Entry")
 443                               .field(v)
 444                               .finish(),
 445             Occupied(ref o) => f.debug_tuple("Entry")
 446                                 .field(o)
 447                                 .finish(),
 448         }
 449     }
 450 }
 451
 452 /// A view into a vacant entry in a `BTreeMap`.
 453 /// It is part of the [`Entry`] enum.
 454 ///
 455 /// [`Entry`]: enum.Entry.html
 456 #[stable(feature = "rust1", since = "1.0.0")]
 457 pub struct VacantEntry<'a, K: 'a, V: 'a> {
 458     key: K,
 459     handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
 460     length: &'a mut usize,
 461
 462     // Be invariant in `K` and `V`
 463     _marker: PhantomData<&'a mut (K, V)>,
 464 }
 465
 466 #[stable(feature= "debug_btree_map", since = "1.12.0")]
 467 impl<K: Debug + Ord, V> Debug for VacantEntry<'_, K, V> {
 468     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 469         f.debug_tuple("VacantEntry")
 470          .field(self.key())
 471          .finish()
 472     }
 473 }
 474
 475 /// A view into an occupied entry in a `BTreeMap`.
 476 /// It is part of the [`Entry`] enum.
 477 ///
 478 /// [`Entry`]: enum.Entry.html
 479 #[stable(feature = "rust1", since = "1.0.0")]
 480 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
 481     handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>,
 482
 483     length: &'a mut usize,
 484
 485     // Be invariant in `K` and `V`
 486     _marker: PhantomData<&'a mut (K, V)>,
 487 }
 488
 489 #[stable(feature= "debug_btree_map", since = "1.12.0")]
 490 impl<K: Debug + Ord, V: Debug> Debug for OccupiedEntry<'_, K, V> {
 491     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 492         f.debug_struct("OccupiedEntry")
 493          .field("key", self.key())
 494          .field("value", self.get())
 495          .finish()
 496     }
 497 }
 498
 499 // An iterator for merging two sorted sequences into one
 500 struct MergeIter<K, V, I: Iterator<Item = (K, V)>> {
 501     left: Peekable<I>,
 502     right: Peekable<I>,
 503 }
 504
 505 impl<K: Ord, V> BTreeMap<K, V> {
 506     /// Makes a new empty BTreeMap with a reasonable choice for B.
 507     ///
 508     /// # Examples
 509     ///
 510     /// Basic usage:
 511     ///
 512     /// ```
 513     /// use std::collections::BTreeMap;
 514     ///
 515     /// let mut map = BTreeMap::new();
 516     ///
 517     /// // entries can now be inserted into the empty map
 518     /// map.insert(1, "a");
 519     /// ```
 520     #[stable(feature = "rust1", since = "1.0.0")]
 521     pub fn new() -> BTreeMap<K, V> {
 522         BTreeMap {
 523             root: node::Root::shared_empty_root(),
 524             length: 0,
 525         }
 526     }
 527
 528     /// Clears the map, removing all values.
 529     ///
 530     /// # Examples
 531     ///
 532     /// Basic usage:
 533     ///
 534     /// ```
 535     /// use std::collections::BTreeMap;
 536     ///
 537     /// let mut a = BTreeMap::new();
 538     /// a.insert(1, "a");
 539     /// a.clear();
 540     /// assert!(a.is_empty());
 541     /// ```
 542     #[stable(feature = "rust1", since = "1.0.0")]
 543     pub fn clear(&mut self) {
 544         *self = BTreeMap::new();
 545     }
 546
 547     /// Returns a reference to the value corresponding to the key.
 548     ///
 549     /// The key may be any borrowed form of the map's key type, but the ordering
 550     /// on the borrowed form *must* match the ordering on the key type.
 551     ///
 552     /// # Examples
 553     ///
 554     /// Basic usage:
 555     ///
 556     /// ```
 557     /// use std::collections::BTreeMap;
 558     ///
 559     /// let mut map = BTreeMap::new();
 560     /// map.insert(1, "a");
 561     /// assert_eq!(map.get(&1), Some(&"a"));
 562     /// assert_eq!(map.get(&2), None);
 563     /// ```
 564     #[stable(feature = "rust1", since = "1.0.0")]
 565     pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
 566         where K: Borrow<Q>,
 567               Q: Ord
 568     {
 569         match search::search_tree(self.root.as_ref(), key) {
 570             Found(handle) => Some(handle.into_kv().1),
 571             GoDown(_) => None,
 572         }
 573     }
 574
 575     /// Returns the key-value pair corresponding to the supplied key.
 576     ///
 577     /// The supplied key may be any borrowed form of the map's key type, but the ordering
 578     /// on the borrowed form *must* match the ordering on the key type.
 579     ///
 580     /// # Examples
 581     ///
 582     /// ```
 583     /// #![feature(map_get_key_value)]
 584     /// use std::collections::BTreeMap;
 585     ///
 586     /// let mut map = BTreeMap::new();
 587     /// map.insert(1, "a");
 588     /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
 589     /// assert_eq!(map.get_key_value(&2), None);
 590     /// ```
 591     #[unstable(feature = "map_get_key_value", issue = "49347")]
 592     pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
 593         where K: Borrow<Q>,
 594               Q: Ord
 595     {
 596         match search::search_tree(self.root.as_ref(), k) {
 597             Found(handle) => Some(handle.into_kv()),
 598             GoDown(_) => None,
 599         }
 600     }
 601
 602     /// Returns `true` if the map contains a value for the specified key.
 603     ///
 604     /// The key may be any borrowed form of the map's key type, but the ordering
 605     /// on the borrowed form *must* match the ordering on the key type.
 606     ///
 607     /// # Examples
 608     ///
 609     /// Basic usage:
 610     ///
 611     /// ```
 612     /// use std::collections::BTreeMap;
 613     ///
 614     /// let mut map = BTreeMap::new();
 615     /// map.insert(1, "a");
 616     /// assert_eq!(map.contains_key(&1), true);
 617     /// assert_eq!(map.contains_key(&2), false);
 618     /// ```
 619     #[stable(feature = "rust1", since = "1.0.0")]
 620     pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
 621         where K: Borrow<Q>,
 622               Q: Ord
 623     {
 624         self.get(key).is_some()
 625     }
 626
 627     /// Returns a mutable reference to the value corresponding to the key.
 628     ///
 629     /// The key may be any borrowed form of the map's key type, but the ordering
 630     /// on the borrowed form *must* match the ordering on the key type.
 631     ///
 632     /// # Examples
 633     ///
 634     /// Basic usage:
 635     ///
 636     /// ```
 637     /// use std::collections::BTreeMap;
 638     ///
 639     /// let mut map = BTreeMap::new();
 640     /// map.insert(1, "a");
 641     /// if let Some(x) = map.get_mut(&1) {
 642     ///     *x = "b";
 643     /// }
 644     /// assert_eq!(map[&1], "b");
 645     /// ```
 646     // See `get` for implementation notes, this is basically a copy-paste with mut's added
 647     #[stable(feature = "rust1", since = "1.0.0")]
 648     pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
 649         where K: Borrow<Q>,
 650               Q: Ord
 651     {
 652         match search::search_tree(self.root.as_mut(), key) {
 653             Found(handle) => Some(handle.into_kv_mut().1),
 654             GoDown(_) => None,
 655         }
 656     }
 657
 658     /// Inserts a key-value pair into the map.
 659     ///
 660     /// If the map did not have this key present, `None` is returned.
 661     ///
 662     /// If the map did have this key present, the value is updated, and the old
 663     /// value is returned. The key is not updated, though; this matters for
 664     /// types that can be `==` without being identical. See the [module-level
 665     /// documentation] for more.
 666     ///
 667     /// [module-level documentation]: index.html#insert-and-complex-keys
 668     ///
 669     /// # Examples
 670     ///
 671     /// Basic usage:
 672     ///
 673     /// ```
 674     /// use std::collections::BTreeMap;
 675     ///
 676     /// let mut map = BTreeMap::new();
 677     /// assert_eq!(map.insert(37, "a"), None);
 678     /// assert_eq!(map.is_empty(), false);
 679     ///
 680     /// map.insert(37, "b");
 681     /// assert_eq!(map.insert(37, "c"), Some("b"));
 682     /// assert_eq!(map[&37], "c");
 683     /// ```
 684     #[stable(feature = "rust1", since = "1.0.0")]
 685     pub fn insert(&mut self, key: K, value: V) -> Option<V> {
 686         match self.entry(key) {
 687             Occupied(mut entry) => Some(entry.insert(value)),
 688             Vacant(entry) => {
 689                 entry.insert(value);
 690                 None
 691             }
 692         }
 693     }
 694
 695     /// Removes a key from the map, returning the value at the key if the key
 696     /// was previously in the map.
 697     ///
 698     /// The key may be any borrowed form of the map's key type, but the ordering
 699     /// on the borrowed form *must* match the ordering on the key type.
 700     ///
 701     /// # Examples
 702     ///
 703     /// Basic usage:
 704     ///
 705     /// ```
 706     /// use std::collections::BTreeMap;
 707     ///
 708     /// let mut map = BTreeMap::new();
 709     /// map.insert(1, "a");
 710     /// assert_eq!(map.remove(&1), Some("a"));
 711     /// assert_eq!(map.remove(&1), None);
 712     /// ```
 713     #[stable(feature = "rust1", since = "1.0.0")]
 714     pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
 715         where K: Borrow<Q>,
 716               Q: Ord
 717     {
 718         match search::search_tree(self.root.as_mut(), key) {
 719             Found(handle) => {
 720                 Some(OccupiedEntry {
 721                          handle,
 722                          length: &mut self.length,
 723                          _marker: PhantomData,
 724                      }
 725                      .remove())
 726             }
 727             GoDown(_) => None,
 728         }
 729     }
 730
 731     /// Moves all elements from `other` into `Self`, leaving `other` empty.
 732     ///
 733     /// # Examples
 734     ///
 735     /// ```
 736     /// use std::collections::BTreeMap;
 737     ///
 738     /// let mut a = BTreeMap::new();
 739     /// a.insert(1, "a");
 740     /// a.insert(2, "b");
 741     /// a.insert(3, "c");
 742     ///
 743     /// let mut b = BTreeMap::new();
 744     /// b.insert(3, "d");
 745     /// b.insert(4, "e");
 746     /// b.insert(5, "f");
 747     ///
 748     /// a.append(&mut b);
 749     ///
 750     /// assert_eq!(a.len(), 5);
 751     /// assert_eq!(b.len(), 0);
 752     ///
 753     /// assert_eq!(a[&1], "a");
 754     /// assert_eq!(a[&2], "b");
 755     /// assert_eq!(a[&3], "d");
 756     /// assert_eq!(a[&4], "e");
 757     /// assert_eq!(a[&5], "f");
 758     /// ```
 759     #[stable(feature = "btree_append", since = "1.11.0")]
 760     pub fn append(&mut self, other: &mut Self) {
 761         // Do we have to append anything at all?
 762         if other.len() == 0 {
 763             return;
 764         }
 765
 766         // We can just swap `self` and `other` if `self` is empty.
 767         if self.len() == 0 {
 768             mem::swap(self, other);
 769             return;
 770         }
 771
 772         // First, we merge `self` and `other` into a sorted sequence in linear time.
 773         let self_iter = mem::replace(self, BTreeMap::new()).into_iter();
 774         let other_iter = mem::replace(other, BTreeMap::new()).into_iter();
 775         let iter = MergeIter {
 776             left: self_iter.peekable(),
 777             right: other_iter.peekable(),
 778         };
 779
 780         // Second, we build a tree from the sorted sequence in linear time.
 781         self.from_sorted_iter(iter);
 782         self.fix_right_edge();
 783     }
 784
 785     /// Constructs a double-ended iterator over a sub-range of elements in the map.
 786     /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
 787     /// yield elements from min (inclusive) to max (exclusive).
 788     /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
 789     /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
 790     /// range from 4 to 10.
 791     ///
 792     /// # Panics
 793     ///
 794     /// Panics if range `start > end`.
 795     /// Panics if range `start == end` and both bounds are `Excluded`.
 796     ///
 797     /// # Examples
 798     ///
 799     /// Basic usage:
 800     ///
 801     /// ```
 802     /// use std::collections::BTreeMap;
 803     /// use std::ops::Bound::Included;
 804     ///
 805     /// let mut map = BTreeMap::new();
 806     /// map.insert(3, "a");
 807     /// map.insert(5, "b");
 808     /// map.insert(8, "c");
 809     /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
 810     ///     println!("{}: {}", key, value);
 811     /// }
 812     /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
 813     /// ```
 814     #[stable(feature = "btree_range", since = "1.17.0")]
 815     pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
 816         where T: Ord, K: Borrow<T>, R: RangeBounds<T>
 817     {
 818         let root1 = self.root.as_ref();
 819         let root2 = self.root.as_ref();
 820         let (f, b) = range_search(root1, root2, range);
 821
 822         Range { front: f, back: b}
 823     }
 824
 825     /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
 826     /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
 827     /// yield elements from min (inclusive) to max (exclusive).
 828     /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
 829     /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
 830     /// range from 4 to 10.
 831     ///
 832     /// # Panics
 833     ///
 834     /// Panics if range `start > end`.
 835     /// Panics if range `start == end` and both bounds are `Excluded`.
 836     ///
 837     /// # Examples
 838     ///
 839     /// Basic usage:
 840     ///
 841     /// ```
 842     /// use std::collections::BTreeMap;
 843     ///
 844     /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"]
 845     ///     .iter()
 846     ///     .map(|&s| (s, 0))
 847     ///     .collect();
 848     /// for (_, balance) in map.range_mut("B".."Cheryl") {
 849     ///     *balance += 100;
 850     /// }
 851     /// for (name, balance) in &map {
 852     ///     println!("{} => {}", name, balance);
 853     /// }
 854     /// ```
 855     #[stable(feature = "btree_range", since = "1.17.0")]
 856     pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>
 857         where T: Ord, K: Borrow<T>, R: RangeBounds<T>
 858     {
 859         let root1 = self.root.as_mut();
 860         let root2 = unsafe { ptr::read(&root1) };
 861         let (f, b) = range_search(root1, root2, range);
 862
 863         RangeMut {
 864             front: f,
 865             back: b,
 866             _marker: PhantomData,
 867         }
 868     }
 869
 870     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 871     ///
 872     /// # Examples
 873     ///
 874     /// Basic usage:
 875     ///
 876     /// ```
 877     /// use std::collections::BTreeMap;
 878     ///
 879     /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
 880     ///
 881     /// // count the number of occurrences of letters in the vec
 882     /// for x in vec!["a","b","a","c","a","b"] {
 883     ///     *count.entry(x).or_insert(0) += 1;
 884     /// }
 885     ///
 886     /// assert_eq!(count["a"], 3);
 887     /// ```
 888     #[stable(feature = "rust1", since = "1.0.0")]
 889     pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
 890         // FIXME(@porglezomp) Avoid allocating if we don't insert
 891         self.ensure_root_is_owned();
 892         match search::search_tree(self.root.as_mut(), &key) {
 893             Found(handle) => {
 894                 Occupied(OccupiedEntry {
 895                     handle,
 896                     length: &mut self.length,
 897                     _marker: PhantomData,
 898                 })
 899             }
 900             GoDown(handle) => {
 901                 Vacant(VacantEntry {
 902                     key,
 903                     handle,
 904                     length: &mut self.length,
 905                     _marker: PhantomData,
 906                 })
 907             }
 908         }
 909     }
 910
 911     fn from_sorted_iter<I: Iterator<Item = (K, V)>>(&mut self, iter: I) {
 912         self.ensure_root_is_owned();
 913         let mut cur_node = last_leaf_edge(self.root.as_mut()).into_node();
 914         // Iterate through all key-value pairs, pushing them into nodes at the right level.
 915         for (key, value) in iter {
 916             // Try to push key-value pair into the current leaf node.
 917             if cur_node.len() < node::CAPACITY {
 918                 cur_node.push(key, value);
 919             } else {
 920                 // No space left, go up and push there.
 921                 let mut open_node;
 922                 let mut test_node = cur_node.forget_type();
 923                 loop {
 924                     match test_node.ascend() {
 925                         Ok(parent) => {
 926                             let parent = parent.into_node();
 927                             if parent.len() < node::CAPACITY {
 928                                 // Found a node with space left, push here.
 929                                 open_node = parent;
 930                                 break;
 931                             } else {
 932                                 // Go up again.
 933                                 test_node = parent.forget_type();
 934                             }
 935                         }
 936                         Err(node) => {
 937                             // We are at the top, create a new root node and push there.
 938                             open_node = node.into_root_mut().push_level();
 939                             break;
 940                         }
 941                     }
 942                 }
 943
 944                 // Push key-value pair and new right subtree.
 945                 let tree_height = open_node.height() - 1;
 946                 let mut right_tree = node::Root::new_leaf();
 947                 for _ in 0..tree_height {
 948                     right_tree.push_level();
 949                 }
 950                 open_node.push(key, value, right_tree);
 951
 952                 // Go down to the right-most leaf again.
 953                 cur_node = last_leaf_edge(open_node.forget_type()).into_node();
 954             }
 955
 956             self.length += 1;
 957         }
 958     }
 959
 960     fn fix_right_edge(&mut self) {
 961         // Handle underfull nodes, start from the top.
 962         let mut cur_node = self.root.as_mut();
 963         while let Internal(internal) = cur_node.force() {
 964             // Check if right-most child is underfull.
 965             let mut last_edge = internal.last_edge();
 966             let right_child_len = last_edge.reborrow().descend().len();
 967             if right_child_len < node::MIN_LEN {
 968                 // We need to steal.
 969                 let mut last_kv = match last_edge.left_kv() {
 970                     Ok(left) => left,
 971                     Err(_) => unreachable!(),
 972                 };
 973                 last_kv.bulk_steal_left(node::MIN_LEN - right_child_len);
 974                 last_edge = last_kv.right_edge();
 975             }
 976
 977             // Go further down.
 978             cur_node = last_edge.descend();
 979         }
 980     }
 981
 982     /// Splits the collection into two at the given key. Returns everything after the given key,
 983     /// including the key.
 984     ///
 985     /// # Examples
 986     ///
 987     /// Basic usage:
 988     ///
 989     /// ```
 990     /// use std::collections::BTreeMap;
 991     ///
 992     /// let mut a = BTreeMap::new();
 993     /// a.insert(1, "a");
 994     /// a.insert(2, "b");
 995     /// a.insert(3, "c");
 996     /// a.insert(17, "d");
 997     /// a.insert(41, "e");
 998     ///
 999     /// let b = a.split_off(&3);
1000     ///
1001     /// assert_eq!(a.len(), 2);
1002     /// assert_eq!(b.len(), 3);
1003     ///
1004     /// assert_eq!(a[&1], "a");
1005     /// assert_eq!(a[&2], "b");
1006     ///
1007     /// assert_eq!(b[&3], "c");
1008     /// assert_eq!(b[&17], "d");
1009     /// assert_eq!(b[&41], "e");
1010     /// ```
1011     #[stable(feature = "btree_split_off", since = "1.11.0")]
1012     pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
1013         where K: Borrow<Q>
1014     {
1015         if self.is_empty() {
1016             return Self::new();
1017         }
1018
1019         let total_num = self.len();
1020
1021         let mut right = Self::new();
1022         right.root = node::Root::new_leaf();
1023         for _ in 0..(self.root.as_ref().height()) {
1024             right.root.push_level();
1025         }
1026
1027         {
1028             let mut left_node = self.root.as_mut();
1029             let mut right_node = right.root.as_mut();
1030
1031             loop {
1032                 let mut split_edge = match search::search_node(left_node, key) {
1033                     // key is going to the right tree
1034                     Found(handle) => handle.left_edge(),
1035                     GoDown(handle) => handle,
1036                 };
1037
1038                 split_edge.move_suffix(&mut right_node);
1039
1040                 match (split_edge.force(), right_node.force()) {
1041                     (Internal(edge), Internal(node)) => {
1042                         left_node = edge.descend();
1043                         right_node = node.first_edge().descend();
1044                     }
1045                     (Leaf(_), Leaf(_)) => {
1046                         break;
1047                     }
1048                     _ => {
1049                         unreachable!();
1050                     }
1051                 }
1052             }
1053         }
1054
1055         self.fix_right_border();
1056         right.fix_left_border();
1057
1058         if self.root.as_ref().height() < right.root.as_ref().height() {
1059             self.recalc_length();
1060             right.length = total_num - self.len();
1061         } else {
1062             right.recalc_length();
1063             self.length = total_num - right.len();
1064         }
1065
1066         right
1067     }
1068
1069     /// Calculates the number of elements if it is incorrect.
1070     fn recalc_length(&mut self) {
1071         fn dfs<'a, K, V>(
1072             node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>
1073         ) -> usize
1074         where K: 'a, V: 'a
1075         {
1076             let mut res = node.len();
1077
1078             if let Internal(node) = node.force() {
1079                 let mut edge = node.first_edge();
1080                 loop {
1081                     res += dfs(edge.reborrow().descend());
1082                     match edge.right_kv() {
1083                         Ok(right_kv) => {
1084                             edge = right_kv.right_edge();
1085                         }
1086                         Err(_) => {
1087                             break;
1088                         }
1089                     }
1090                 }
1091             }
1092
1093             res
1094         }
1095
1096         self.length = dfs(self.root.as_ref());
1097     }
1098
1099     /// Removes empty levels on the top.
1100     fn fix_top(&mut self) {
1101         loop {
1102             {
1103                 let node = self.root.as_ref();
1104                 if node.height() == 0 || node.len() > 0 {
1105                     break;
1106                 }
1107             }
1108             self.root.pop_level();
1109         }
1110     }
1111
1112     fn fix_right_border(&mut self) {
1113         self.fix_top();
1114
1115         {
1116             let mut cur_node = self.root.as_mut();
1117
1118             while let Internal(node) = cur_node.force() {
1119                 let mut last_kv = node.last_kv();
1120
1121                 if last_kv.can_merge() {
1122                     cur_node = last_kv.merge().descend();
1123                 } else {
1124                     let right_len = last_kv.reborrow().right_edge().descend().len();
1125                     // `MINLEN + 1` to avoid readjust if merge happens on the next level.
1126                     if right_len < node::MIN_LEN + 1 {
1127                         last_kv.bulk_steal_left(node::MIN_LEN + 1 - right_len);
1128                     }
1129                     cur_node = last_kv.right_edge().descend();
1130                 }
1131             }
1132         }
1133
1134         self.fix_top();
1135     }
1136
1137     /// The symmetric clone of `fix_right_border`.
1138     fn fix_left_border(&mut self) {
1139         self.fix_top();
1140
1141         {
1142             let mut cur_node = self.root.as_mut();
1143
1144             while let Internal(node) = cur_node.force() {
1145                 let mut first_kv = node.first_kv();
1146
1147                 if first_kv.can_merge() {
1148                     cur_node = first_kv.merge().descend();
1149                 } else {
1150                     let left_len = first_kv.reborrow().left_edge().descend().len();
1151                     if left_len < node::MIN_LEN + 1 {
1152                         first_kv.bulk_steal_right(node::MIN_LEN + 1 - left_len);
1153                     }
1154                     cur_node = first_kv.left_edge().descend();
1155                 }
1156             }
1157         }
1158
1159         self.fix_top();
1160     }
1161
1162     /// If the root node is the shared root node, allocate our own node.
1163     fn ensure_root_is_owned(&mut self) {
1164         if self.root.is_shared_root() {
1165             self.root = node::Root::new_leaf();
1166         }
1167     }
1168 }
1169
1170 #[stable(feature = "rust1", since = "1.0.0")]
1171 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
1172     type Item = (&'a K, &'a V);
1173     type IntoIter = Iter<'a, K, V>;
1174
1175     fn into_iter(self) -> Iter<'a, K, V> {
1176         self.iter()
1177     }
1178 }
1179
1180 #[stable(feature = "rust1", since = "1.0.0")]
1181 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
1182     type Item = (&'a K, &'a V);
1183
1184     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1185         if self.length == 0 {
1186             None
1187         } else {
1188             self.length -= 1;
1189             unsafe { Some(self.range.next_unchecked()) }
1190         }
1191     }
1192
1193     fn size_hint(&self) -> (usize, Option<usize>) {
1194         (self.length, Some(self.length))
1195     }
1196 }
1197
1198 #[stable(feature = "fused", since = "1.26.0")]
1199 impl<K, V> FusedIterator for Iter<'_, K, V> {}
1200
1201 #[stable(feature = "rust1", since = "1.0.0")]
1202 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
1203     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1204         if self.length == 0 {
1205             None
1206         } else {
1207             self.length -= 1;
1208             unsafe { Some(self.range.next_back_unchecked()) }
1209         }
1210     }
1211 }
1212
1213 #[stable(feature = "rust1", since = "1.0.0")]
1214 impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1215     fn len(&self) -> usize {
1216         self.length
1217     }
1218 }
1219
1220 #[stable(feature = "rust1", since = "1.0.0")]
1221 impl<K, V> Clone for Iter<'_, K, V> {
1222     fn clone(&self) -> Self {
1223         Iter {
1224             range: self.range.clone(),
1225             length: self.length,
1226         }
1227     }
1228 }
1229
1230 #[stable(feature = "rust1", since = "1.0.0")]
1231 impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
1232     type Item = (&'a K, &'a mut V);
1233     type IntoIter = IterMut<'a, K, V>;
1234
1235     fn into_iter(self) -> IterMut<'a, K, V> {
1236         self.iter_mut()
1237     }
1238 }
1239
1240 #[stable(feature = "rust1", since = "1.0.0")]
1241 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
1242     type Item = (&'a K, &'a mut V);
1243
1244     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1245         if self.length == 0 {
1246             None
1247         } else {
1248             self.length -= 1;
1249             unsafe { Some(self.range.next_unchecked()) }
1250         }
1251     }
1252
1253     fn size_hint(&self) -> (usize, Option<usize>) {
1254         (self.length, Some(self.length))
1255     }
1256 }
1257
1258 #[stable(feature = "rust1", since = "1.0.0")]
1259 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
1260     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1261         if self.length == 0 {
1262             None
1263         } else {
1264             self.length -= 1;
1265             unsafe { Some(self.range.next_back_unchecked()) }
1266         }
1267     }
1268 }
1269
1270 #[stable(feature = "rust1", since = "1.0.0")]
1271 impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
1272     fn len(&self) -> usize {
1273         self.length
1274     }
1275 }
1276
1277 #[stable(feature = "fused", since = "1.26.0")]
1278 impl<K, V> FusedIterator for IterMut<'_, K, V> {}
1279
1280 #[stable(feature = "rust1", since = "1.0.0")]
1281 impl<K, V> IntoIterator for BTreeMap<K, V> {
1282     type Item = (K, V);
1283     type IntoIter = IntoIter<K, V>;
1284
1285     fn into_iter(self) -> IntoIter<K, V> {
1286         let root1 = unsafe { ptr::read(&self.root).into_ref() };
1287         let root2 = unsafe { ptr::read(&self.root).into_ref() };
1288         let len = self.length;
1289         mem::forget(self);
1290
1291         IntoIter {
1292             front: first_leaf_edge(root1),
1293             back: last_leaf_edge(root2),
1294             length: len,
1295         }
1296     }
1297 }
1298
1299 #[stable(feature = "btree_drop", since = "1.7.0")]
1300 impl<K, V> Drop for IntoIter<K, V> {
1301     fn drop(&mut self) {
1302         self.for_each(drop);
1303         unsafe {
1304             let leaf_node = ptr::read(&self.front).into_node();
1305             if leaf_node.is_shared_root() {
1306                 return;
1307             }
1308
1309             if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
1310                 let mut cur_node = first_parent.into_node();
1311                 while let Some(parent) = cur_node.deallocate_and_ascend() {
1312                     cur_node = parent.into_node()
1313                 }
1314             }
1315         }
1316     }
1317 }
1318
1319 #[stable(feature = "rust1", since = "1.0.0")]
1320 impl<K, V> Iterator for IntoIter<K, V> {
1321     type Item = (K, V);
1322
1323     fn next(&mut self) -> Option<(K, V)> {
1324         if self.length == 0 {
1325             return None;
1326         } else {
1327             self.length -= 1;
1328         }
1329
1330         let handle = unsafe { ptr::read(&self.front) };
1331
1332         let mut cur_handle = match handle.right_kv() {
1333             Ok(kv) => {
1334                 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
1335                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
1336                 self.front = kv.right_edge();
1337                 return Some((k, v));
1338             }
1339             Err(last_edge) => unsafe {
1340                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
1341             },
1342         };
1343
1344         loop {
1345             match cur_handle.right_kv() {
1346                 Ok(kv) => {
1347                     let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
1348                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
1349                     self.front = first_leaf_edge(kv.right_edge().descend());
1350                     return Some((k, v));
1351                 }
1352                 Err(last_edge) => unsafe {
1353                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
1354                 },
1355             }
1356         }
1357     }
1358
1359     fn size_hint(&self) -> (usize, Option<usize>) {
1360         (self.length, Some(self.length))
1361     }
1362 }
1363
1364 #[stable(feature = "rust1", since = "1.0.0")]
1365 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1366     fn next_back(&mut self) -> Option<(K, V)> {
1367         if self.length == 0 {
1368             return None;
1369         } else {
1370             self.length -= 1;
1371         }
1372
1373         let handle = unsafe { ptr::read(&self.back) };
1374
1375         let mut cur_handle = match handle.left_kv() {
1376             Ok(kv) => {
1377                 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
1378                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
1379                 self.back = kv.left_edge();
1380                 return Some((k, v));
1381             }
1382             Err(last_edge) => unsafe {
1383                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
1384             },
1385         };
1386
1387         loop {
1388             match cur_handle.left_kv() {
1389                 Ok(kv) => {
1390                     let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
1391                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
1392                     self.back = last_leaf_edge(kv.left_edge().descend());
1393                     return Some((k, v));
1394                 }
1395                 Err(last_edge) => unsafe {
1396                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
1397                 },
1398             }
1399         }
1400     }
1401 }
1402
1403 #[stable(feature = "rust1", since = "1.0.0")]
1404 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1405     fn len(&self) -> usize {
1406         self.length
1407     }
1408 }
1409
1410 #[stable(feature = "fused", since = "1.26.0")]
1411 impl<K, V> FusedIterator for IntoIter<K, V> {}
1412
1413 #[stable(feature = "rust1", since = "1.0.0")]
1414 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1415     type Item = &'a K;
1416
1417     fn next(&mut self) -> Option<&'a K> {
1418         self.inner.next().map(|(k, _)| k)
1419     }
1420
1421     fn size_hint(&self) -> (usize, Option<usize>) {
1422         self.inner.size_hint()
1423     }
1424 }
1425
1426 #[stable(feature = "rust1", since = "1.0.0")]
1427 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1428     fn next_back(&mut self) -> Option<&'a K> {
1429         self.inner.next_back().map(|(k, _)| k)
1430     }
1431 }
1432
1433 #[stable(feature = "rust1", since = "1.0.0")]
1434 impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
1435     fn len(&self) -> usize {
1436         self.inner.len()
1437     }
1438 }
1439
1440 #[stable(feature = "fused", since = "1.26.0")]
1441 impl<K, V> FusedIterator for Keys<'_, K, V> {}
1442
1443 #[stable(feature = "rust1", since = "1.0.0")]
1444 impl<K, V> Clone for Keys<'_, K, V> {
1445     fn clone(&self) -> Self {
1446         Keys { inner: self.inner.clone() }
1447     }
1448 }
1449
1450 #[stable(feature = "rust1", since = "1.0.0")]
1451 impl<'a, K, V> Iterator for Values<'a, K, V> {
1452     type Item = &'a V;
1453
1454     fn next(&mut self) -> Option<&'a V> {
1455         self.inner.next().map(|(_, v)| v)
1456     }
1457
1458     fn size_hint(&self) -> (usize, Option<usize>) {
1459         self.inner.size_hint()
1460     }
1461 }
1462
1463 #[stable(feature = "rust1", since = "1.0.0")]
1464 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1465     fn next_back(&mut self) -> Option<&'a V> {
1466         self.inner.next_back().map(|(_, v)| v)
1467     }
1468 }
1469
1470 #[stable(feature = "rust1", since = "1.0.0")]
1471 impl<K, V> ExactSizeIterator for Values<'_, K, V> {
1472     fn len(&self) -> usize {
1473         self.inner.len()
1474     }
1475 }
1476
1477 #[stable(feature = "fused", since = "1.26.0")]
1478 impl<K, V> FusedIterator for Values<'_, K, V> {}
1479
1480 #[stable(feature = "rust1", since = "1.0.0")]
1481 impl<K, V> Clone for Values<'_, K, V> {
1482     fn clone(&self) -> Self {
1483         Values { inner: self.inner.clone() }
1484     }
1485 }
1486
1487 #[stable(feature = "btree_range", since = "1.17.0")]
1488 impl<'a, K, V> Iterator for Range<'a, K, V> {
1489     type Item = (&'a K, &'a V);
1490
1491     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1492         if self.front == self.back {
1493             None
1494         } else {
1495             unsafe { Some(self.next_unchecked()) }
1496         }
1497     }
1498 }
1499
1500 #[stable(feature = "map_values_mut", since = "1.10.0")]
1501 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1502     type Item = &'a mut V;
1503
1504     fn next(&mut self) -> Option<&'a mut V> {
1505         self.inner.next().map(|(_, v)| v)
1506     }
1507
1508     fn size_hint(&self) -> (usize, Option<usize>) {
1509         self.inner.size_hint()
1510     }
1511 }
1512
1513 #[stable(feature = "map_values_mut", since = "1.10.0")]
1514 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
1515     fn next_back(&mut self) -> Option<&'a mut V> {
1516         self.inner.next_back().map(|(_, v)| v)
1517     }
1518 }
1519
1520 #[stable(feature = "map_values_mut", since = "1.10.0")]
1521 impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
1522     fn len(&self) -> usize {
1523         self.inner.len()
1524     }
1525 }
1526
1527 #[stable(feature = "fused", since = "1.26.0")]
1528 impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
1529
1530 impl<'a, K, V> Range<'a, K, V> {
1531     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
1532         let handle = self.front;
1533
1534         let mut cur_handle = match handle.right_kv() {
1535             Ok(kv) => {
1536                 let ret = kv.into_kv();
1537                 self.front = kv.right_edge();
1538                 return ret;
1539             }
1540             Err(last_edge) => {
1541                 let next_level = last_edge.into_node().ascend().ok();
1542                 unwrap_unchecked(next_level)
1543             }
1544         };
1545
1546         loop {
1547             match cur_handle.right_kv() {
1548                 Ok(kv) => {
1549                     let ret = kv.into_kv();
1550                     self.front = first_leaf_edge(kv.right_edge().descend());
1551                     return ret;
1552                 }
1553                 Err(last_edge) => {
1554                     let next_level = last_edge.into_node().ascend().ok();
1555                     cur_handle = unwrap_unchecked(next_level);
1556                 }
1557             }
1558         }
1559     }
1560 }
1561
1562 #[stable(feature = "btree_range", since = "1.17.0")]
1563 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1564     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1565         if self.front == self.back {
1566             None
1567         } else {
1568             unsafe { Some(self.next_back_unchecked()) }
1569         }
1570     }
1571 }
1572
1573 impl<'a, K, V> Range<'a, K, V> {
1574     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
1575         let handle = self.back;
1576
1577         let mut cur_handle = match handle.left_kv() {
1578             Ok(kv) => {
1579                 let ret = kv.into_kv();
1580                 self.back = kv.left_edge();
1581                 return ret;
1582             }
1583             Err(last_edge) => {
1584                 let next_level = last_edge.into_node().ascend().ok();
1585                 unwrap_unchecked(next_level)
1586             }
1587         };
1588
1589         loop {
1590             match cur_handle.left_kv() {
1591                 Ok(kv) => {
1592                     let ret = kv.into_kv();
1593                     self.back = last_leaf_edge(kv.left_edge().descend());
1594                     return ret;
1595                 }
1596                 Err(last_edge) => {
1597                     let next_level = last_edge.into_node().ascend().ok();
1598                     cur_handle = unwrap_unchecked(next_level);
1599                 }
1600             }
1601         }
1602     }
1603 }
1604
1605 #[stable(feature = "fused", since = "1.26.0")]
1606 impl<K, V> FusedIterator for Range<'_, K, V> {}
1607
1608 #[stable(feature = "btree_range", since = "1.17.0")]
1609 impl<K, V> Clone for Range<'_, K, V> {
1610     fn clone(&self) -> Self {
1611         Range {
1612             front: self.front,
1613             back: self.back,
1614         }
1615     }
1616 }
1617
1618 #[stable(feature = "btree_range", since = "1.17.0")]
1619 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1620     type Item = (&'a K, &'a mut V);
1621
1622     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1623         if self.front == self.back {
1624             None
1625         } else {
1626             unsafe { Some(self.next_unchecked()) }
1627         }
1628     }
1629 }
1630
1631 impl<'a, K, V> RangeMut<'a, K, V> {
1632     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
1633         let handle = ptr::read(&self.front);
1634
1635         let mut cur_handle = match handle.right_kv() {
1636             Ok(kv) => {
1637                 self.front = ptr::read(&kv).right_edge();
1638                 // Doing the descend invalidates the references returned by `into_kv_mut`,
1639                 // so we have to do this last.
1640                 let (k, v) = kv.into_kv_mut();
1641                 return (k, v); // coerce k from `&mut K` to `&K`
1642             }
1643             Err(last_edge) => {
1644                 let next_level = last_edge.into_node().ascend().ok();
1645                 unwrap_unchecked(next_level)
1646             }
1647         };
1648
1649         loop {
1650             match cur_handle.right_kv() {
1651                 Ok(kv) => {
1652                     self.front = first_leaf_edge(ptr::read(&kv).right_edge().descend());
1653                     // Doing the descend invalidates the references returned by `into_kv_mut`,
1654                     // so we have to do this last.
1655                     let (k, v) = kv.into_kv_mut();
1656                     return (k, v); // coerce k from `&mut K` to `&K`
1657                 }
1658                 Err(last_edge) => {
1659                     let next_level = last_edge.into_node().ascend().ok();
1660                     cur_handle = unwrap_unchecked(next_level);
1661                 }
1662             }
1663         }
1664     }
1665 }
1666
1667 #[stable(feature = "btree_range", since = "1.17.0")]
1668 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1669     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1670         if self.front == self.back {
1671             None
1672         } else {
1673             unsafe { Some(self.next_back_unchecked()) }
1674         }
1675     }
1676 }
1677
1678 #[stable(feature = "fused", since = "1.26.0")]
1679 impl<K, V> FusedIterator for RangeMut<'_, K, V> {}
1680
1681 impl<'a, K, V> RangeMut<'a, K, V> {
1682     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
1683         let handle = ptr::read(&self.back);
1684
1685         let mut cur_handle = match handle.left_kv() {
1686             Ok(kv) => {
1687                 self.back = ptr::read(&kv).left_edge();
1688                 // Doing the descend invalidates the references returned by `into_kv_mut`,
1689                 // so we have to do this last.
1690                 let (k, v) = kv.into_kv_mut();
1691                 return (k, v); // coerce k from `&mut K` to `&K`
1692             }
1693             Err(last_edge) => {
1694                 let next_level = last_edge.into_node().ascend().ok();
1695                 unwrap_unchecked(next_level)
1696             }
1697         };
1698
1699         loop {
1700             match cur_handle.left_kv() {
1701                 Ok(kv) => {
1702                     self.back = last_leaf_edge(ptr::read(&kv).left_edge().descend());
1703                     // Doing the descend invalidates the references returned by `into_kv_mut`,
1704                     // so we have to do this last.
1705                     let (k, v) = kv.into_kv_mut();
1706                     return (k, v); // coerce k from `&mut K` to `&K`
1707                 }
1708                 Err(last_edge) => {
1709                     let next_level = last_edge.into_node().ascend().ok();
1710                     cur_handle = unwrap_unchecked(next_level);
1711                 }
1712             }
1713         }
1714     }
1715 }
1716
1717 #[stable(feature = "rust1", since = "1.0.0")]
1718 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1719     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
1720         let mut map = BTreeMap::new();
1721         map.extend(iter);
1722         map
1723     }
1724 }
1725
1726 #[stable(feature = "rust1", since = "1.0.0")]
1727 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1728     #[inline]
1729     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
1730         iter.into_iter().for_each(move |(k, v)| {
1731             self.insert(k, v);
1732         });
1733     }
1734 }
1735
1736 #[stable(feature = "extend_ref", since = "1.2.0")]
1737 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1738     fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
1739         self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1740     }
1741 }
1742
1743 #[stable(feature = "rust1", since = "1.0.0")]
1744 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1745     fn hash<H: Hasher>(&self, state: &mut H) {
1746         for elt in self {
1747             elt.hash(state);
1748         }
1749     }
1750 }
1751
1752 #[stable(feature = "rust1", since = "1.0.0")]
1753 impl<K: Ord, V> Default for BTreeMap<K, V> {
1754     /// Creates an empty `BTreeMap<K, V>`.
1755     fn default() -> BTreeMap<K, V> {
1756         BTreeMap::new()
1757     }
1758 }
1759
1760 #[stable(feature = "rust1", since = "1.0.0")]
1761 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
1762     fn eq(&self, other: &BTreeMap<K, V>) -> bool {
1763         self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
1764     }
1765 }
1766
1767 #[stable(feature = "rust1", since = "1.0.0")]
1768 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
1769
1770 #[stable(feature = "rust1", since = "1.0.0")]
1771 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
1772     #[inline]
1773     fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
1774         self.iter().partial_cmp(other.iter())
1775     }
1776 }
1777
1778 #[stable(feature = "rust1", since = "1.0.0")]
1779 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
1780     #[inline]
1781     fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
1782         self.iter().cmp(other.iter())
1783     }
1784 }
1785
1786 #[stable(feature = "rust1", since = "1.0.0")]
1787 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
1788     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1789         f.debug_map().entries(self.iter()).finish()
1790     }
1791 }
1792
1793 #[stable(feature = "rust1", since = "1.0.0")]
1794 impl<K: Ord, Q: ?Sized, V> Index<&Q> for BTreeMap<K, V>
1795     where K: Borrow<Q>,
1796           Q: Ord
1797 {
1798     type Output = V;
1799
1800     /// Returns a reference to the value corresponding to the supplied key.
1801     ///
1802     /// # Panics
1803     ///
1804     /// Panics if the key is not present in the `BTreeMap`.
1805     #[inline]
1806     fn index(&self, key: &Q) -> &V {
1807         self.get(key).expect("no entry found for key")
1808     }
1809 }
1810
1811 fn first_leaf_edge<BorrowType, K, V>
1812     (mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>)
1813      -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1814     loop {
1815         match node.force() {
1816             Leaf(leaf) => return leaf.first_edge(),
1817             Internal(internal) => {
1818                 node = internal.first_edge().descend();
1819             }
1820         }
1821     }
1822 }
1823
1824 fn last_leaf_edge<BorrowType, K, V>
1825     (mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>)
1826      -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1827     loop {
1828         match node.force() {
1829             Leaf(leaf) => return leaf.last_edge(),
1830             Internal(internal) => {
1831                 node = internal.last_edge().descend();
1832             }
1833         }
1834     }
1835 }
1836
1837 fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>(
1838     root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
1839     root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
1840     range: R
1841 )-> (Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
1842      Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>)
1843         where Q: Ord, K: Borrow<Q>
1844 {
1845     match (range.start_bound(), range.end_bound()) {
1846         (Excluded(s), Excluded(e)) if s==e =>
1847             panic!("range start and end are equal and excluded in BTreeMap"),
1848         (Included(s), Included(e)) |
1849         (Included(s), Excluded(e)) |
1850         (Excluded(s), Included(e)) |
1851         (Excluded(s), Excluded(e)) if s>e =>
1852             panic!("range start is greater than range end in BTreeMap"),
1853         _ => {},
1854     };
1855
1856     let mut min_node = root1;
1857     let mut max_node = root2;
1858     let mut min_found = false;
1859     let mut max_found = false;
1860     let mut diverged = false;
1861
1862     loop {
1863         let min_edge = match (min_found, range.start_bound()) {
1864             (false, Included(key)) => match search::search_linear(&min_node, key) {
1865                 (i, true) => { min_found = true; i },
1866                 (i, false) => i,
1867             },
1868             (false, Excluded(key)) => match search::search_linear(&min_node, key) {
1869                 (i, true) => { min_found = true; i+1 },
1870                 (i, false) => i,
1871             },
1872             (_, Unbounded) => 0,
1873             (true, Included(_)) => min_node.keys().len(),
1874             (true, Excluded(_)) => 0,
1875         };
1876
1877         let max_edge = match (max_found, range.end_bound()) {
1878             (false, Included(key)) => match search::search_linear(&max_node, key) {
1879                 (i, true) => { max_found = true; i+1 },
1880                 (i, false) => i,
1881             },
1882             (false, Excluded(key)) => match search::search_linear(&max_node, key) {
1883                 (i, true) => { max_found = true; i },
1884                 (i, false) => i,
1885             },
1886             (_, Unbounded) => max_node.keys().len(),
1887             (true, Included(_)) => 0,
1888             (true, Excluded(_)) => max_node.keys().len(),
1889         };
1890
1891         if !diverged {
1892             if max_edge < min_edge { panic!("Ord is ill-defined in BTreeMap range") }
1893             if min_edge != max_edge { diverged = true; }
1894         }
1895
1896         let front = Handle::new_edge(min_node, min_edge);
1897         let back = Handle::new_edge(max_node, max_edge);
1898         match (front.force(), back.force()) {
1899             (Leaf(f), Leaf(b)) => {
1900                 return (f, b);
1901             },
1902             (Internal(min_int), Internal(max_int)) => {
1903                 min_node = min_int.descend();
1904                 max_node = max_int.descend();
1905             },
1906             _ => unreachable!("BTreeMap has different depths"),
1907         };
1908     }
1909 }
1910
1911 #[inline(always)]
1912 unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
1913     val.unwrap_or_else(|| {
1914         if cfg!(debug_assertions) {
1915             panic!("'unchecked' unwrap on None in BTreeMap");
1916         } else {
1917             intrinsics::unreachable();
1918         }
1919     })
1920 }
1921
1922 impl<K, V> BTreeMap<K, V> {
1923     /// Gets an iterator over the entries of the map, sorted by key.
1924     ///
1925     /// # Examples
1926     ///
1927     /// Basic usage:
1928     ///
1929     /// ```
1930     /// use std::collections::BTreeMap;
1931     ///
1932     /// let mut map = BTreeMap::new();
1933     /// map.insert(3, "c");
1934     /// map.insert(2, "b");
1935     /// map.insert(1, "a");
1936     ///
1937     /// for (key, value) in map.iter() {
1938     ///     println!("{}: {}", key, value);
1939     /// }
1940     ///
1941     /// let (first_key, first_value) = map.iter().next().unwrap();
1942     /// assert_eq!((*first_key, *first_value), (1, "a"));
1943     /// ```
1944     #[stable(feature = "rust1", since = "1.0.0")]
1945     pub fn iter(&self) -> Iter<'_, K, V> {
1946         Iter {
1947             range: Range {
1948                 front: first_leaf_edge(self.root.as_ref()),
1949                 back: last_leaf_edge(self.root.as_ref()),
1950             },
1951             length: self.length,
1952         }
1953     }
1954
1955     /// Gets a mutable iterator over the entries of the map, sorted by key.
1956     ///
1957     /// # Examples
1958     ///
1959     /// Basic usage:
1960     ///
1961     /// ```
1962     /// use std::collections::BTreeMap;
1963     ///
1964     /// let mut map = BTreeMap::new();
1965     /// map.insert("a", 1);
1966     /// map.insert("b", 2);
1967     /// map.insert("c", 3);
1968     ///
1969     /// // add 10 to the value if the key isn't "a"
1970     /// for (key, value) in map.iter_mut() {
1971     ///     if key != &"a" {
1972     ///         *value += 10;
1973     ///     }
1974     /// }
1975     /// ```
1976     #[stable(feature = "rust1", since = "1.0.0")]
1977     pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
1978         let root1 = self.root.as_mut();
1979         let root2 = unsafe { ptr::read(&root1) };
1980         IterMut {
1981             range: RangeMut {
1982                 front: first_leaf_edge(root1),
1983                 back: last_leaf_edge(root2),
1984                 _marker: PhantomData,
1985             },
1986             length: self.length,
1987         }
1988     }
1989
1990     /// Gets an iterator over the keys of the map, in sorted order.
1991     ///
1992     /// # Examples
1993     ///
1994     /// Basic usage:
1995     ///
1996     /// ```
1997     /// use std::collections::BTreeMap;
1998     ///
1999     /// let mut a = BTreeMap::new();
2000     /// a.insert(2, "b");
2001     /// a.insert(1, "a");
2002     ///
2003     /// let keys: Vec<_> = a.keys().cloned().collect();
2004     /// assert_eq!(keys, [1, 2]);
2005     /// ```
2006     #[stable(feature = "rust1", since = "1.0.0")]
2007     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
2008         Keys { inner: self.iter() }
2009     }
2010
2011     /// Gets an iterator over the values of the map, in order by key.
2012     ///
2013     /// # Examples
2014     ///
2015     /// Basic usage:
2016     ///
2017     /// ```
2018     /// use std::collections::BTreeMap;
2019     ///
2020     /// let mut a = BTreeMap::new();
2021     /// a.insert(1, "hello");
2022     /// a.insert(2, "goodbye");
2023     ///
2024     /// let values: Vec<&str> = a.values().cloned().collect();
2025     /// assert_eq!(values, ["hello", "goodbye"]);
2026     /// ```
2027     #[stable(feature = "rust1", since = "1.0.0")]
2028     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
2029         Values { inner: self.iter() }
2030     }
2031
2032     /// Gets a mutable iterator over the values of the map, in order by key.
2033     ///
2034     /// # Examples
2035     ///
2036     /// Basic usage:
2037     ///
2038     /// ```
2039     /// use std::collections::BTreeMap;
2040     ///
2041     /// let mut a = BTreeMap::new();
2042     /// a.insert(1, String::from("hello"));
2043     /// a.insert(2, String::from("goodbye"));
2044     ///
2045     /// for value in a.values_mut() {
2046     ///     value.push_str("!");
2047     /// }
2048     ///
2049     /// let values: Vec<String> = a.values().cloned().collect();
2050     /// assert_eq!(values, [String::from("hello!"),
2051     ///                     String::from("goodbye!")]);
2052     /// ```
2053     #[stable(feature = "map_values_mut", since = "1.10.0")]
2054     pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
2055         ValuesMut { inner: self.iter_mut() }
2056     }
2057
2058     /// Returns the number of elements in the map.
2059     ///
2060     /// # Examples
2061     ///
2062     /// Basic usage:
2063     ///
2064     /// ```
2065     /// use std::collections::BTreeMap;
2066     ///
2067     /// let mut a = BTreeMap::new();
2068     /// assert_eq!(a.len(), 0);
2069     /// a.insert(1, "a");
2070     /// assert_eq!(a.len(), 1);
2071     /// ```
2072     #[stable(feature = "rust1", since = "1.0.0")]
2073     pub fn len(&self) -> usize {
2074         self.length
2075     }
2076
2077     /// Returns `true` if the map contains no elements.
2078     ///
2079     /// # Examples
2080     ///
2081     /// Basic usage:
2082     ///
2083     /// ```
2084     /// use std::collections::BTreeMap;
2085     ///
2086     /// let mut a = BTreeMap::new();
2087     /// assert!(a.is_empty());
2088     /// a.insert(1, "a");
2089     /// assert!(!a.is_empty());
2090     /// ```
2091     #[stable(feature = "rust1", since = "1.0.0")]
2092     pub fn is_empty(&self) -> bool {
2093         self.len() == 0
2094     }
2095 }
2096
2097 impl<'a, K: Ord, V> Entry<'a, K, V> {
2098     /// Ensures a value is in the entry by inserting the default if empty, and returns
2099     /// a mutable reference to the value in the entry.
2100     ///
2101     /// # Examples
2102     ///
2103     /// ```
2104     /// use std::collections::BTreeMap;
2105     ///
2106     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2107     /// map.entry("poneyland").or_insert(12);
2108     ///
2109     /// assert_eq!(map["poneyland"], 12);
2110     /// ```
2111     #[stable(feature = "rust1", since = "1.0.0")]
2112     pub fn or_insert(self, default: V) -> &'a mut V {
2113         match self {
2114             Occupied(entry) => entry.into_mut(),
2115             Vacant(entry) => entry.insert(default),
2116         }
2117     }
2118
2119     /// Ensures a value is in the entry by inserting the result of the default function if empty,
2120     /// and returns a mutable reference to the value in the entry.
2121     ///
2122     /// # Examples
2123     ///
2124     /// ```
2125     /// use std::collections::BTreeMap;
2126     ///
2127     /// let mut map: BTreeMap<&str, String> = BTreeMap::new();
2128     /// let s = "hoho".to_string();
2129     ///
2130     /// map.entry("poneyland").or_insert_with(|| s);
2131     ///
2132     /// assert_eq!(map["poneyland"], "hoho".to_string());
2133     /// ```
2134     #[stable(feature = "rust1", since = "1.0.0")]
2135     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
2136         match self {
2137             Occupied(entry) => entry.into_mut(),
2138             Vacant(entry) => entry.insert(default()),
2139         }
2140     }
2141
2142     /// Returns a reference to this entry's key.
2143     ///
2144     /// # Examples
2145     ///
2146     /// ```
2147     /// use std::collections::BTreeMap;
2148     ///
2149     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2150     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2151     /// ```
2152     #[stable(feature = "map_entry_keys", since = "1.10.0")]
2153     pub fn key(&self) -> &K {
2154         match *self {
2155             Occupied(ref entry) => entry.key(),
2156             Vacant(ref entry) => entry.key(),
2157         }
2158     }
2159
2160     /// Provides in-place mutable access to an occupied entry before any
2161     /// potential inserts into the map.
2162     ///
2163     /// # Examples
2164     ///
2165     /// ```
2166     /// use std::collections::BTreeMap;
2167     ///
2168     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2169     ///
2170     /// map.entry("poneyland")
2171     ///    .and_modify(|e| { *e += 1 })
2172     ///    .or_insert(42);
2173     /// assert_eq!(map["poneyland"], 42);
2174     ///
2175     /// map.entry("poneyland")
2176     ///    .and_modify(|e| { *e += 1 })
2177     ///    .or_insert(42);
2178     /// assert_eq!(map["poneyland"], 43);
2179     /// ```
2180     #[stable(feature = "entry_and_modify", since = "1.26.0")]
2181     pub fn and_modify<F>(self, f: F) -> Self
2182         where F: FnOnce(&mut V)
2183     {
2184         match self {
2185             Occupied(mut entry) => {
2186                 f(entry.get_mut());
2187                 Occupied(entry)
2188             },
2189             Vacant(entry) => Vacant(entry),
2190         }
2191     }
2192 }
2193
2194 impl<'a, K: Ord, V: Default> Entry<'a, K, V> {
2195     #[stable(feature = "entry_or_default", since = "1.28.0")]
2196     /// Ensures a value is in the entry by inserting the default value if empty,
2197     /// and returns a mutable reference to the value in the entry.
2198     ///
2199     /// # Examples
2200     ///
2201     /// ```
2202     /// # fn main() {
2203     /// use std::collections::BTreeMap;
2204     ///
2205     /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
2206     /// map.entry("poneyland").or_default();
2207     ///
2208     /// assert_eq!(map["poneyland"], None);
2209     /// # }
2210     /// ```
2211     pub fn or_default(self) -> &'a mut V {
2212         match self {
2213             Occupied(entry) => entry.into_mut(),
2214             Vacant(entry) => entry.insert(Default::default()),
2215         }
2216     }
2217
2218 }
2219
2220 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
2221     /// Gets a reference to the key that would be used when inserting a value
2222     /// through the VacantEntry.
2223     ///
2224     /// # Examples
2225     ///
2226     /// ```
2227     /// use std::collections::BTreeMap;
2228     ///
2229     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2230     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2231     /// ```
2232     #[stable(feature = "map_entry_keys", since = "1.10.0")]
2233     pub fn key(&self) -> &K {
2234         &self.key
2235     }
2236
2237     /// Take ownership of the key.
2238     ///
2239     /// # Examples
2240     ///
2241     /// ```
2242     /// use std::collections::BTreeMap;
2243     /// use std::collections::btree_map::Entry;
2244     ///
2245     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2246     ///
2247     /// if let Entry::Vacant(v) = map.entry("poneyland") {
2248     ///     v.into_key();
2249     /// }
2250     /// ```
2251     #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2252     pub fn into_key(self) -> K {
2253         self.key
2254     }
2255
2256     /// Sets the value of the entry with the `VacantEntry`'s key,
2257     /// and returns a mutable reference to it.
2258     ///
2259     /// # Examples
2260     ///
2261     /// ```
2262     /// use std::collections::BTreeMap;
2263     ///
2264     /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
2265     ///
2266     /// // count the number of occurrences of letters in the vec
2267     /// for x in vec!["a","b","a","c","a","b"] {
2268     ///     *count.entry(x).or_insert(0) += 1;
2269     /// }
2270     ///
2271     /// assert_eq!(count["a"], 3);
2272     /// ```
2273     #[stable(feature = "rust1", since = "1.0.0")]
2274     pub fn insert(self, value: V) -> &'a mut V {
2275         *self.length += 1;
2276
2277         let out_ptr;
2278
2279         let mut ins_k;
2280         let mut ins_v;
2281         let mut ins_edge;
2282
2283         let mut cur_parent = match self.handle.insert(self.key, value) {
2284             (Fit(handle), _) => return handle.into_kv_mut().1,
2285             (Split(left, k, v, right), ptr) => {
2286                 ins_k = k;
2287                 ins_v = v;
2288                 ins_edge = right;
2289                 out_ptr = ptr;
2290                 left.ascend().map_err(|n| n.into_root_mut())
2291             }
2292         };
2293
2294         loop {
2295             match cur_parent {
2296                 Ok(parent) => {
2297                     match parent.insert(ins_k, ins_v, ins_edge) {
2298                         Fit(_) => return unsafe { &mut *out_ptr },
2299                         Split(left, k, v, right) => {
2300                             ins_k = k;
2301                             ins_v = v;
2302                             ins_edge = right;
2303                             cur_parent = left.ascend().map_err(|n| n.into_root_mut());
2304                         }
2305                     }
2306                 }
2307                 Err(root) => {
2308                     root.push_level().push(ins_k, ins_v, ins_edge);
2309                     return unsafe { &mut *out_ptr };
2310                 }
2311             }
2312         }
2313     }
2314 }
2315
2316 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
2317     /// Gets a reference to the key in the entry.
2318     ///
2319     /// # Examples
2320     ///
2321     /// ```
2322     /// use std::collections::BTreeMap;
2323     ///
2324     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2325     /// map.entry("poneyland").or_insert(12);
2326     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2327     /// ```
2328     #[stable(feature = "map_entry_keys", since = "1.10.0")]
2329     pub fn key(&self) -> &K {
2330         self.handle.reborrow().into_kv().0
2331     }
2332
2333     /// Take ownership of the key and value from the map.
2334     ///
2335     /// # Examples
2336     ///
2337     /// ```
2338     /// use std::collections::BTreeMap;
2339     /// use std::collections::btree_map::Entry;
2340     ///
2341     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2342     /// map.entry("poneyland").or_insert(12);
2343     ///
2344     /// if let Entry::Occupied(o) = map.entry("poneyland") {
2345     ///     // We delete the entry from the map.
2346     ///     o.remove_entry();
2347     /// }
2348     ///
2349     /// // If now try to get the value, it will panic:
2350     /// // println!("{}", map["poneyland"]);
2351     /// ```
2352     #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2353     pub fn remove_entry(self) -> (K, V) {
2354         self.remove_kv()
2355     }
2356
2357     /// Gets a reference to the value in the entry.
2358     ///
2359     /// # Examples
2360     ///
2361     /// ```
2362     /// use std::collections::BTreeMap;
2363     /// use std::collections::btree_map::Entry;
2364     ///
2365     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2366     /// map.entry("poneyland").or_insert(12);
2367     ///
2368     /// if let Entry::Occupied(o) = map.entry("poneyland") {
2369     ///     assert_eq!(o.get(), &12);
2370     /// }
2371     /// ```
2372     #[stable(feature = "rust1", since = "1.0.0")]
2373     pub fn get(&self) -> &V {
2374         self.handle.reborrow().into_kv().1
2375     }
2376
2377     /// Gets a mutable reference to the value in the entry.
2378     ///
2379     /// If you need a reference to the `OccupiedEntry` that may outlive the
2380     /// destruction of the `Entry` value, see [`into_mut`].
2381     ///
2382     /// [`into_mut`]: #method.into_mut
2383     ///
2384     /// # Examples
2385     ///
2386     /// ```
2387     /// use std::collections::BTreeMap;
2388     /// use std::collections::btree_map::Entry;
2389     ///
2390     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2391     /// map.entry("poneyland").or_insert(12);
2392     ///
2393     /// assert_eq!(map["poneyland"], 12);
2394     /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2395     ///     *o.get_mut() += 10;
2396     ///     assert_eq!(*o.get(), 22);
2397     ///
2398     ///     // We can use the same Entry multiple times.
2399     ///     *o.get_mut() += 2;
2400     /// }
2401     /// assert_eq!(map["poneyland"], 24);
2402     /// ```
2403     #[stable(feature = "rust1", since = "1.0.0")]
2404     pub fn get_mut(&mut self) -> &mut V {
2405         self.handle.kv_mut().1
2406     }
2407
2408     /// Converts the entry into a mutable reference to its value.
2409     ///
2410     /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2411     ///
2412     /// [`get_mut`]: #method.get_mut
2413     ///
2414     /// # Examples
2415     ///
2416     /// ```
2417     /// use std::collections::BTreeMap;
2418     /// use std::collections::btree_map::Entry;
2419     ///
2420     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2421     /// map.entry("poneyland").or_insert(12);
2422     ///
2423     /// assert_eq!(map["poneyland"], 12);
2424     /// if let Entry::Occupied(o) = map.entry("poneyland") {
2425     ///     *o.into_mut() += 10;
2426     /// }
2427     /// assert_eq!(map["poneyland"], 22);
2428     /// ```
2429     #[stable(feature = "rust1", since = "1.0.0")]
2430     pub fn into_mut(self) -> &'a mut V {
2431         self.handle.into_kv_mut().1
2432     }
2433
2434     /// Sets the value of the entry with the `OccupiedEntry`'s key,
2435     /// and returns the entry's old value.
2436     ///
2437     /// # Examples
2438     ///
2439     /// ```
2440     /// use std::collections::BTreeMap;
2441     /// use std::collections::btree_map::Entry;
2442     ///
2443     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2444     /// map.entry("poneyland").or_insert(12);
2445     ///
2446     /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2447     ///     assert_eq!(o.insert(15), 12);
2448     /// }
2449     /// assert_eq!(map["poneyland"], 15);
2450     /// ```
2451     #[stable(feature = "rust1", since = "1.0.0")]
2452     pub fn insert(&mut self, value: V) -> V {
2453         mem::replace(self.get_mut(), value)
2454     }
2455
2456     /// Takes the value of the entry out of the map, and returns it.
2457     ///
2458     /// # Examples
2459     ///
2460     /// ```
2461     /// use std::collections::BTreeMap;
2462     /// use std::collections::btree_map::Entry;
2463     ///
2464     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2465     /// map.entry("poneyland").or_insert(12);
2466     ///
2467     /// if let Entry::Occupied(o) = map.entry("poneyland") {
2468     ///     assert_eq!(o.remove(), 12);
2469     /// }
2470     /// // If we try to get "poneyland"'s value, it'll panic:
2471     /// // println!("{}", map["poneyland"]);
2472     /// ```
2473     #[stable(feature = "rust1", since = "1.0.0")]
2474     pub fn remove(self) -> V {
2475         self.remove_kv().1
2476     }
2477
2478     fn remove_kv(self) -> (K, V) {
2479         *self.length -= 1;
2480
2481         let (small_leaf, old_key, old_val) = match self.handle.force() {
2482             Leaf(leaf) => {
2483                 let (hole, old_key, old_val) = leaf.remove();
2484                 (hole.into_node(), old_key, old_val)
2485             }
2486             Internal(mut internal) => {
2487                 let key_loc = internal.kv_mut().0 as *mut K;
2488                 let val_loc = internal.kv_mut().1 as *mut V;
2489
2490                 let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
2491                 let to_remove = unsafe { unwrap_unchecked(to_remove) };
2492
2493                 let (hole, key, val) = to_remove.remove();
2494
2495                 let old_key = unsafe { mem::replace(&mut *key_loc, key) };
2496                 let old_val = unsafe { mem::replace(&mut *val_loc, val) };
2497
2498                 (hole.into_node(), old_key, old_val)
2499             }
2500         };
2501
2502         // Handle underflow
2503         let mut cur_node = small_leaf.forget_type();
2504         while cur_node.len() < node::CAPACITY / 2 {
2505             match handle_underfull_node(cur_node) {
2506                 AtRoot => break,
2507                 EmptyParent(_) => unreachable!(),
2508                 Merged(parent) => {
2509                     if parent.len() == 0 {
2510                         // We must be at the root
2511                         parent.into_root_mut().pop_level();
2512                         break;
2513                     } else {
2514                         cur_node = parent.forget_type();
2515                     }
2516                 }
2517                 Stole(_) => break,
2518             }
2519         }
2520
2521         (old_key, old_val)
2522     }
2523 }
2524
2525 enum UnderflowResult<'a, K, V> {
2526     AtRoot,
2527     EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
2528     Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
2529     Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
2530 }
2531
2532 fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>)
2533                                    -> UnderflowResult<'a, K, V> {
2534     let parent = if let Ok(parent) = node.ascend() {
2535         parent
2536     } else {
2537         return AtRoot;
2538     };
2539
2540     let (is_left, mut handle) = match parent.left_kv() {
2541         Ok(left) => (true, left),
2542         Err(parent) => {
2543             match parent.right_kv() {
2544                 Ok(right) => (false, right),
2545                 Err(parent) => {
2546                     return EmptyParent(parent.into_node());
2547                 }
2548             }
2549         }
2550     };
2551
2552     if handle.can_merge() {
2553         Merged(handle.merge().into_node())
2554     } else {
2555         if is_left {
2556             handle.steal_left();
2557         } else {
2558             handle.steal_right();
2559         }
2560         Stole(handle.into_node())
2561     }
2562 }
2563
2564 impl<K: Ord, V, I: Iterator<Item = (K, V)>> Iterator for MergeIter<K, V, I> {
2565     type Item = (K, V);
2566
2567     fn next(&mut self) -> Option<(K, V)> {
2568         let res = match (self.left.peek(), self.right.peek()) {
2569             (Some(&(ref left_key, _)), Some(&(ref right_key, _))) => left_key.cmp(right_key),
2570             (Some(_), None) => Ordering::Less,
2571             (None, Some(_)) => Ordering::Greater,
2572             (None, None) => return None,
2573         };
2574
2575         // Check which elements comes first and only advance the corresponding iterator.
2576         // If two keys are equal, take the value from `right`.
2577         match res {
2578             Ordering::Less => self.left.next(),
2579             Ordering::Greater => self.right.next(),
2580             Ordering::Equal => {
2581                 self.left.next();
2582                 self.right.next()
2583             }
2584         }
2585     }
2586 }