library/alloc/src/collections/btree/map.rs

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