1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use core
::cmp
::Ordering
;
13 use core
::hash
::{Hash, Hasher}
;
14 use core
::iter
::FromIterator
;
15 use core
::marker
::PhantomData
;
17 use core
::{fmt, intrinsics, mem, ptr}
;
20 use Bound
::{self, Included, Excluded, Unbounded}
;
22 use super::node
::{self, NodeRef, Handle, marker}
;
25 use super::node
::InsertResult
::*;
26 use super::node
::ForceResult
::*;
27 use super::search
::SearchResult
::*;
28 use self::UnderflowResult
::*;
31 /// A map based on a B-Tree.
33 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
34 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
35 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
36 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
37 /// is done is *very* inefficient for modern computer architectures. In particular, every element
38 /// is stored in its own individually heap-allocated node. This means that every single insertion
39 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
40 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
43 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
44 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
45 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
46 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
47 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
48 /// the node using binary search. As a compromise, one could also perform a linear search
49 /// that initially only checks every i<sup>th</sup> element for some choice of i.
51 /// Currently, our implementation simply performs naive linear search. This provides excellent
52 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
53 /// would like to further explore choosing the optimal search strategy based on the choice of B,
54 /// and possibly other factors. Using linear search, searching for a random element is expected
55 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
56 /// however, performance is excellent.
58 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
59 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
60 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
65 /// use std::collections::BTreeMap;
67 /// // type inference lets us omit an explicit type signature (which
68 /// // would be `BTreeMap<&str, &str>` in this example).
69 /// let mut movie_reviews = BTreeMap::new();
71 /// // review some books.
72 /// movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
73 /// movie_reviews.insert("Pulp Fiction", "Masterpiece.");
74 /// movie_reviews.insert("The Godfather", "Very enjoyable.");
75 /// movie_reviews.insert("The Blues Brothers", "Eye lyked it alot.");
77 /// // check for a specific one.
78 /// if !movie_reviews.contains_key("Les Misérables") {
79 /// println!("We've got {} reviews, but Les Misérables ain't one.",
80 /// movie_reviews.len());
83 /// // oops, this review has a lot of spelling mistakes, let's delete it.
84 /// movie_reviews.remove("The Blues Brothers");
86 /// // look up the values associated with some keys.
87 /// let to_find = ["Up!", "Office Space"];
88 /// for book in &to_find {
89 /// match movie_reviews.get(book) {
90 /// Some(review) => println!("{}: {}", book, review),
91 /// None => println!("{} is unreviewed.", book)
95 /// // iterate over everything.
96 /// for (movie, review) in &movie_reviews {
97 /// println!("{}: \"{}\"", movie, review);
101 /// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows
102 /// for more complex methods of getting, setting, updating and removing keys and
106 /// use std::collections::BTreeMap;
108 /// // type inference lets us omit an explicit type signature (which
109 /// // would be `BTreeMap<&str, u8>` in this example).
110 /// let mut player_stats = BTreeMap::new();
112 /// fn random_stat_buff() -> u8 {
113 /// // could actually return some random value here - let's just return
114 /// // some fixed value for now
118 /// // insert a key only if it doesn't already exist
119 /// player_stats.entry("health").or_insert(100);
121 /// // insert a key using a function that provides a new value only if it
122 /// // doesn't already exist
123 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
125 /// // update a key, guarding against the key possibly not being set
126 /// let stat = player_stats.entry("attack").or_insert(100);
127 /// *stat += random_stat_buff();
129 #[stable(feature = "rust1", since = "1.0.0")]
130 pub struct BTreeMap
<K
, V
> {
131 root
: node
::Root
<K
, V
>,
135 impl<K
, V
> Drop
for BTreeMap
<K
, V
> {
136 #[unsafe_destructor_blind_to_params]
139 for _
in ptr
::read(self).into_iter() { }
144 impl<K
: Clone
, V
: Clone
> Clone
for BTreeMap
<K
, V
> {
145 fn clone(&self) -> BTreeMap
<K
, V
> {
146 fn clone_subtree
<K
: Clone
, V
: Clone
>(
147 node
: node
::NodeRef
<marker
::Immut
, K
, V
, marker
::LeafOrInternal
>)
152 let mut out_tree
= BTreeMap
{
153 root
: node
::Root
::new_leaf(),
158 let mut out_node
= match out_tree
.root
.as_mut().force() {
160 Internal(_
) => unreachable
!()
163 let mut in_edge
= leaf
.first_edge();
164 while let Ok(kv
) = in_edge
.right_kv() {
165 let (k
, v
) = kv
.into_kv();
166 in_edge
= kv
.right_edge();
168 out_node
.push(k
.clone(), v
.clone());
169 out_tree
.length
+= 1;
175 Internal(internal
) => {
176 let mut out_tree
= clone_subtree(internal
.first_edge().descend());
179 let mut out_node
= out_tree
.root
.push_level();
180 let mut in_edge
= internal
.first_edge();
181 while let Ok(kv
) = in_edge
.right_kv() {
182 let (k
, v
) = kv
.into_kv();
183 in_edge
= kv
.right_edge();
185 let k
= (*k
).clone();
186 let v
= (*v
).clone();
187 let subtree
= clone_subtree(in_edge
.descend());
189 // We can't destructure subtree directly
190 // because BTreeMap implements Drop
191 let (subroot
, sublength
) = unsafe {
192 let root
= ptr
::read(&subtree
.root
);
193 let length
= subtree
.length
;
194 mem
::forget(subtree
);
198 out_node
.push(k
, v
, subroot
);
199 out_tree
.length
+= 1 + sublength
;
208 clone_subtree(self.root
.as_ref())
212 impl<K
, Q
: ?Sized
> super::Recover
<Q
> for BTreeMap
<K
, ()>
213 where K
: Borrow
<Q
> + Ord
,
218 fn get(&self, key
: &Q
) -> Option
<&K
> {
219 match search
::search_tree(self.root
.as_ref(), key
) {
220 Found(handle
) => Some(handle
.into_kv().0),
225 fn take(&mut self, key
: &Q
) -> Option
<K
> {
226 match search
::search_tree(self.root
.as_mut(), key
) {
230 length
: &mut self.length
,
231 _marker
: PhantomData
,
238 fn replace(&mut self, key
: K
) -> Option
<K
> {
239 match search
::search_tree
::<marker
::Mut
, K
, (), K
>(self.root
.as_mut(), &key
) {
240 Found(handle
) => Some(mem
::replace(handle
.into_kv_mut().0, key
)),
245 length
: &mut self.length
,
246 _marker
: PhantomData
,
254 /// An iterator over a BTreeMap's entries.
255 #[stable(feature = "rust1", since = "1.0.0")]
256 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
257 range
: Range
<'a
, K
, V
>,
261 /// A mutable iterator over a BTreeMap's entries.
262 #[stable(feature = "rust1", since = "1.0.0")]
263 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
264 range
: RangeMut
<'a
, K
, V
>,
268 /// An owning iterator over a BTreeMap's entries.
269 #[stable(feature = "rust1", since = "1.0.0")]
270 pub struct IntoIter
<K
, V
> {
271 front
: Handle
<NodeRef
<marker
::Owned
, K
, V
, marker
::Leaf
>, marker
::Edge
>,
272 back
: Handle
<NodeRef
<marker
::Owned
, K
, V
, marker
::Leaf
>, marker
::Edge
>,
276 /// An iterator over a BTreeMap's keys.
277 #[stable(feature = "rust1", since = "1.0.0")]
278 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
279 inner
: Iter
<'a
, K
, V
>,
282 /// An iterator over a BTreeMap's values.
283 #[stable(feature = "rust1", since = "1.0.0")]
284 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
285 inner
: Iter
<'a
, K
, V
>,
288 /// A mutable iterator over a BTreeMap's values.
289 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
290 pub struct ValuesMut
<'a
, K
: 'a
, V
: 'a
> {
291 inner
: IterMut
<'a
, K
, V
>,
294 /// An iterator over a sub-range of BTreeMap's entries.
295 pub struct Range
<'a
, K
: 'a
, V
: 'a
> {
296 front
: Handle
<NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
297 back
: Handle
<NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>
300 /// A mutable iterator over a sub-range of BTreeMap's entries.
301 pub struct RangeMut
<'a
, K
: 'a
, V
: 'a
> {
302 front
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
303 back
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
305 // Be invariant in `K` and `V`
306 _marker
: PhantomData
<&'a
mut (K
, V
)>,
309 /// A view into a single entry in a map, which may either be vacant or occupied.
310 #[stable(feature = "rust1", since = "1.0.0")]
311 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
313 #[stable(feature = "rust1", since = "1.0.0")]
315 #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
318 /// An occupied Entry
319 #[stable(feature = "rust1", since = "1.0.0")]
321 #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
326 #[stable(feature = "rust1", since = "1.0.0")]
327 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
329 handle
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
330 length
: &'a
mut usize,
332 // Be invariant in `K` and `V`
333 _marker
: PhantomData
<&'a
mut (K
, V
)>,
336 /// An occupied Entry.
337 #[stable(feature = "rust1", since = "1.0.0")]
338 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
339 handle
: Handle
<NodeRef
<
342 marker
::LeafOrInternal
345 length
: &'a
mut usize,
347 // Be invariant in `K` and `V`
348 _marker
: PhantomData
<&'a
mut (K
, V
)>,
351 impl<K
: Ord
, V
> BTreeMap
<K
, V
> {
352 /// Makes a new empty BTreeMap with a reasonable choice for B.
359 /// use std::collections::BTreeMap;
361 /// let mut map = BTreeMap::new();
363 /// // entries can now be inserted into the empty map
364 /// map.insert(1, "a");
366 #[stable(feature = "rust1", since = "1.0.0")]
367 pub fn new() -> BTreeMap
<K
, V
> {
369 root
: node
::Root
::new_leaf(),
374 /// Clears the map, removing all values.
381 /// use std::collections::BTreeMap;
383 /// let mut a = BTreeMap::new();
384 /// a.insert(1, "a");
386 /// assert!(a.is_empty());
388 #[stable(feature = "rust1", since = "1.0.0")]
389 pub fn clear(&mut self) {
390 // FIXME(gereeter) .clear() allocates
391 *self = BTreeMap
::new();
394 /// Returns a reference to the value corresponding to the key.
396 /// The key may be any borrowed form of the map's key type, but the ordering
397 /// on the borrowed form *must* match the ordering on the key type.
404 /// use std::collections::BTreeMap;
406 /// let mut map = BTreeMap::new();
407 /// map.insert(1, "a");
408 /// assert_eq!(map.get(&1), Some(&"a"));
409 /// assert_eq!(map.get(&2), None);
411 #[stable(feature = "rust1", since = "1.0.0")]
412 pub fn get
<Q
: ?Sized
>(&self, key
: &Q
) -> Option
<&V
> where K
: Borrow
<Q
>, Q
: Ord
{
413 match search
::search_tree(self.root
.as_ref(), key
) {
414 Found(handle
) => Some(handle
.into_kv().1),
419 /// Returns true if the map contains a value for the specified key.
421 /// The key may be any borrowed form of the map's key type, but the ordering
422 /// on the borrowed form *must* match the ordering on the key type.
429 /// use std::collections::BTreeMap;
431 /// let mut map = BTreeMap::new();
432 /// map.insert(1, "a");
433 /// assert_eq!(map.contains_key(&1), true);
434 /// assert_eq!(map.contains_key(&2), false);
436 #[stable(feature = "rust1", since = "1.0.0")]
437 pub fn contains_key
<Q
: ?Sized
>(&self, key
: &Q
) -> bool
where K
: Borrow
<Q
>, Q
: Ord
{
438 self.get(key
).is_some()
441 /// Returns a mutable reference to the value corresponding to the key.
443 /// The key may be any borrowed form of the map's key type, but the ordering
444 /// on the borrowed form *must* match the ordering on the key type.
451 /// use std::collections::BTreeMap;
453 /// let mut map = BTreeMap::new();
454 /// map.insert(1, "a");
455 /// if let Some(x) = map.get_mut(&1) {
458 /// assert_eq!(map[&1], "b");
460 // See `get` for implementation notes, this is basically a copy-paste with mut's added
461 #[stable(feature = "rust1", since = "1.0.0")]
462 pub fn get_mut
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<&mut V
> where K
: Borrow
<Q
>, Q
: Ord
{
463 match search
::search_tree(self.root
.as_mut(), key
) {
464 Found(handle
) => Some(handle
.into_kv_mut().1),
469 /// Inserts a key-value pair into the map.
471 /// If the map did not have this key present, `None` is returned.
473 /// If the map did have this key present, the value is updated, and the old
474 /// value is returned. The key is not updated, though; this matters for
475 /// types that can be `==` without being identical. See the [module-level
476 /// documentation] for more.
478 /// [module-level documentation]: index.html#insert-and-complex-keys
485 /// use std::collections::BTreeMap;
487 /// let mut map = BTreeMap::new();
488 /// assert_eq!(map.insert(37, "a"), None);
489 /// assert_eq!(map.is_empty(), false);
491 /// map.insert(37, "b");
492 /// assert_eq!(map.insert(37, "c"), Some("b"));
493 /// assert_eq!(map[&37], "c");
495 #[stable(feature = "rust1", since = "1.0.0")]
496 pub fn insert(&mut self, key
: K
, value
: V
) -> Option
<V
> {
497 match self.entry(key
) {
498 Occupied(mut entry
) => Some(entry
.insert(value
)),
506 /// Removes a key from the map, returning the value at the key if the key
507 /// was previously in the map.
509 /// The key may be any borrowed form of the map's key type, but the ordering
510 /// on the borrowed form *must* match the ordering on the key type.
517 /// use std::collections::BTreeMap;
519 /// let mut map = BTreeMap::new();
520 /// map.insert(1, "a");
521 /// assert_eq!(map.remove(&1), Some("a"));
522 /// assert_eq!(map.remove(&1), None);
524 #[stable(feature = "rust1", since = "1.0.0")]
525 pub fn remove
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<V
> where K
: Borrow
<Q
>, Q
: Ord
{
526 match search
::search_tree(self.root
.as_mut(), key
) {
530 length
: &mut self.length
,
531 _marker
: PhantomData
,
538 /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
539 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
540 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
541 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
548 /// #![feature(btree_range, collections_bound)]
550 /// use std::collections::BTreeMap;
551 /// use std::collections::Bound::{Included, Unbounded};
553 /// let mut map = BTreeMap::new();
554 /// map.insert(3, "a");
555 /// map.insert(5, "b");
556 /// map.insert(8, "c");
557 /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
558 /// println!("{}: {}", key, value);
560 /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
562 #[unstable(feature = "btree_range",
563 reason
= "matches collection reform specification, waiting for dust to settle",
565 pub fn range
<Min
: ?Sized
+ Ord
, Max
: ?Sized
+ Ord
>(&self,
569 where K
: Borrow
<Min
> + Borrow
<Max
>,
571 let front
= match min
{
572 Included(key
) => match search
::search_tree(self.root
.as_ref(), key
) {
573 Found(kv_handle
) => match kv_handle
.left_edge().force() {
574 Leaf(bottom
) => bottom
,
575 Internal(internal
) => last_leaf_edge(internal
.descend())
577 GoDown(bottom
) => bottom
579 Excluded(key
) => match search
::search_tree(self.root
.as_ref(), key
) {
580 Found(kv_handle
) => match kv_handle
.right_edge().force() {
581 Leaf(bottom
) => bottom
,
582 Internal(internal
) => first_leaf_edge(internal
.descend())
584 GoDown(bottom
) => bottom
586 Unbounded
=> first_leaf_edge(self.root
.as_ref())
589 let back
= match max
{
590 Included(key
) => match search
::search_tree(self.root
.as_ref(), key
) {
591 Found(kv_handle
) => match kv_handle
.right_edge().force() {
592 Leaf(bottom
) => bottom
,
593 Internal(internal
) => first_leaf_edge(internal
.descend())
595 GoDown(bottom
) => bottom
597 Excluded(key
) => match search
::search_tree(self.root
.as_ref(), key
) {
598 Found(kv_handle
) => match kv_handle
.left_edge().force() {
599 Leaf(bottom
) => bottom
,
600 Internal(internal
) => last_leaf_edge(internal
.descend())
602 GoDown(bottom
) => bottom
604 Unbounded
=> last_leaf_edge(self.root
.as_ref())
613 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
614 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
615 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
616 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
623 /// #![feature(btree_range, collections_bound)]
625 /// use std::collections::BTreeMap;
626 /// use std::collections::Bound::{Included, Excluded};
628 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
629 /// .map(|&s| (s, 0))
631 /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
634 /// for (name, balance) in &map {
635 /// println!("{} => {}", name, balance);
638 #[unstable(feature = "btree_range",
639 reason
= "matches collection reform specification, waiting for dust to settle",
641 pub fn range_mut
<Min
: ?Sized
+ Ord
, Max
: ?Sized
+ Ord
>(&mut self,
645 where K
: Borrow
<Min
> + Borrow
<Max
>,
647 let root1
= self.root
.as_mut();
648 let root2
= unsafe { ptr::read(&root1) }
;
650 let front
= match min
{
651 Included(key
) => match search
::search_tree(root1
, key
) {
652 Found(kv_handle
) => match kv_handle
.left_edge().force() {
653 Leaf(bottom
) => bottom
,
654 Internal(internal
) => last_leaf_edge(internal
.descend())
656 GoDown(bottom
) => bottom
658 Excluded(key
) => match search
::search_tree(root1
, key
) {
659 Found(kv_handle
) => match kv_handle
.right_edge().force() {
660 Leaf(bottom
) => bottom
,
661 Internal(internal
) => first_leaf_edge(internal
.descend())
663 GoDown(bottom
) => bottom
665 Unbounded
=> first_leaf_edge(root1
)
668 let back
= match max
{
669 Included(key
) => match search
::search_tree(root2
, key
) {
670 Found(kv_handle
) => match kv_handle
.right_edge().force() {
671 Leaf(bottom
) => bottom
,
672 Internal(internal
) => first_leaf_edge(internal
.descend())
674 GoDown(bottom
) => bottom
676 Excluded(key
) => match search
::search_tree(root2
, key
) {
677 Found(kv_handle
) => match kv_handle
.left_edge().force() {
678 Leaf(bottom
) => bottom
,
679 Internal(internal
) => last_leaf_edge(internal
.descend())
681 GoDown(bottom
) => bottom
683 Unbounded
=> last_leaf_edge(root2
)
693 /// Gets the given key's corresponding entry in the map for in-place manipulation.
700 /// use std::collections::BTreeMap;
702 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
704 /// // count the number of occurrences of letters in the vec
705 /// for x in vec!["a","b","a","c","a","b"] {
706 /// *count.entry(x).or_insert(0) += 1;
709 /// assert_eq!(count["a"], 3);
711 #[stable(feature = "rust1", since = "1.0.0")]
712 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
713 match search
::search_tree(self.root
.as_mut(), &key
) {
714 Found(handle
) => Occupied(OccupiedEntry
{
716 length
: &mut self.length
,
717 _marker
: PhantomData
,
719 GoDown(handle
) => Vacant(VacantEntry
{
722 length
: &mut self.length
,
723 _marker
: PhantomData
,
729 impl<'a
, K
: 'a
, V
: 'a
> IntoIterator
for &'a BTreeMap
<K
, V
> {
730 type Item
= (&'a K
, &'a V
);
731 type IntoIter
= Iter
<'a
, K
, V
>;
733 fn into_iter(self) -> Iter
<'a
, K
, V
> {
738 impl<'a
, K
: 'a
, V
: 'a
> Iterator
for Iter
<'a
, K
, V
> {
739 type Item
= (&'a K
, &'a V
);
741 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
742 if self.length
== 0 {
746 unsafe { Some(self.range.next_unchecked()) }
750 fn size_hint(&self) -> (usize, Option
<usize>) {
751 (self.length
, Some(self.length
))
755 impl<'a
, K
: 'a
, V
: 'a
> DoubleEndedIterator
for Iter
<'a
, K
, V
> {
756 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
757 if self.length
== 0 {
761 unsafe { Some(self.range.next_back_unchecked()) }
766 impl<'a
, K
: 'a
, V
: 'a
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
767 fn len(&self) -> usize { self.length }
770 impl<'a
, K
, V
> Clone
for Iter
<'a
, K
, V
> {
771 fn clone(&self) -> Iter
<'a
, K
, V
> {
773 range
: self.range
.clone(),
779 impl<'a
, K
: 'a
, V
: 'a
> IntoIterator
for &'a
mut BTreeMap
<K
, V
> {
780 type Item
= (&'a K
, &'a
mut V
);
781 type IntoIter
= IterMut
<'a
, K
, V
>;
783 fn into_iter(self) -> IterMut
<'a
, K
, V
> {
788 impl<'a
, K
: 'a
, V
: 'a
> Iterator
for IterMut
<'a
, K
, V
> {
789 type Item
= (&'a K
, &'a
mut V
);
791 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
792 if self.length
== 0 {
796 unsafe { Some(self.range.next_unchecked()) }
800 fn size_hint(&self) -> (usize, Option
<usize>) {
801 (self.length
, Some(self.length
))
805 impl<'a
, K
: 'a
, V
: 'a
> DoubleEndedIterator
for IterMut
<'a
, K
, V
> {
806 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
807 if self.length
== 0 {
811 unsafe { Some(self.range.next_back_unchecked()) }
816 impl<'a
, K
: 'a
, V
: 'a
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
817 fn len(&self) -> usize { self.length }
820 impl<K
, V
> IntoIterator
for BTreeMap
<K
, V
> {
822 type IntoIter
= IntoIter
<K
, V
>;
824 fn into_iter(self) -> IntoIter
<K
, V
> {
825 let root1
= unsafe { ptr::read(&self.root).into_ref() }
;
826 let root2
= unsafe { ptr::read(&self.root).into_ref() }
;
827 let len
= self.length
;
831 front
: first_leaf_edge(root1
),
832 back
: last_leaf_edge(root2
),
838 impl<K
, V
> Drop
for IntoIter
<K
, V
> {
840 for _
in &mut *self { }
842 let leaf_node
= ptr
::read(&self.front
).into_node();
843 if let Some(first_parent
) = leaf_node
.deallocate_and_ascend() {
844 let mut cur_node
= first_parent
.into_node();
845 while let Some(parent
) = cur_node
.deallocate_and_ascend() {
846 cur_node
= parent
.into_node()
853 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
856 fn next(&mut self) -> Option
<(K
, V
)> {
857 if self.length
== 0 {
863 let handle
= unsafe { ptr::read(&self.front) }
;
865 let mut cur_handle
= match handle
.right_kv() {
867 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
868 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
869 self.front
= kv
.right_edge();
872 Err(last_edge
) => unsafe {
873 unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend())
878 match cur_handle
.right_kv() {
880 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
881 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
882 self.front
= first_leaf_edge(kv
.right_edge().descend());
885 Err(last_edge
) => unsafe {
886 cur_handle
= unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend());
892 fn size_hint(&self) -> (usize, Option
<usize>) {
893 (self.length
, Some(self.length
))
897 impl<K
, V
> DoubleEndedIterator
for IntoIter
<K
, V
> {
898 fn next_back(&mut self) -> Option
<(K
, V
)> {
899 if self.length
== 0 {
905 let handle
= unsafe { ptr::read(&self.back) }
;
907 let mut cur_handle
= match handle
.left_kv() {
909 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
910 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
911 self.back
= kv
.left_edge();
914 Err(last_edge
) => unsafe {
915 unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend())
920 match cur_handle
.left_kv() {
922 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
923 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
924 self.back
= last_leaf_edge(kv
.left_edge().descend());
927 Err(last_edge
) => unsafe {
928 cur_handle
= unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend());
935 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
936 fn len(&self) -> usize { self.length }
939 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
942 fn next(&mut self) -> Option
<&'a K
> {
943 self.inner
.next().map(|(k
, _
)| k
)
946 fn size_hint(&self) -> (usize, Option
<usize>) {
947 self.inner
.size_hint()
951 impl<'a
, K
, V
> DoubleEndedIterator
for Keys
<'a
, K
, V
> {
952 fn next_back(&mut self) -> Option
<&'a K
> {
953 self.inner
.next_back().map(|(k
, _
)| k
)
957 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
958 fn len(&self) -> usize {
963 impl<'a
, K
, V
> Clone
for Keys
<'a
, K
, V
> {
964 fn clone(&self) -> Keys
<'a
, K
, V
> {
966 inner
: self.inner
.clone()
971 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
974 fn next(&mut self) -> Option
<&'a V
> {
975 self.inner
.next().map(|(_
, v
)| v
)
978 fn size_hint(&self) -> (usize, Option
<usize>) {
979 self.inner
.size_hint()
983 impl<'a
, K
, V
> DoubleEndedIterator
for Values
<'a
, K
, V
> {
984 fn next_back(&mut self) -> Option
<&'a V
> {
985 self.inner
.next_back().map(|(_
, v
)| v
)
989 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
990 fn len(&self) -> usize {
995 impl<'a
, K
, V
> Clone
for Values
<'a
, K
, V
> {
996 fn clone(&self) -> Values
<'a
, K
, V
> {
998 inner
: self.inner
.clone()
1003 impl<'a
, K
, V
> Iterator
for Range
<'a
, K
, V
> {
1004 type Item
= (&'a K
, &'a V
);
1006 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1007 if self.front
== self.back
{
1010 unsafe { Some(self.next_unchecked()) }
1015 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1016 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1017 type Item
= &'a
mut V
;
1019 fn next(&mut self) -> Option
<&'a
mut V
> {
1020 self.inner
.next().map(|(_
, v
)| v
)
1023 fn size_hint(&self) -> (usize, Option
<usize>) {
1024 self.inner
.size_hint()
1028 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1029 impl<'a
, K
, V
> DoubleEndedIterator
for ValuesMut
<'a
, K
, V
> {
1030 fn next_back(&mut self) -> Option
<&'a
mut V
> {
1031 self.inner
.next_back().map(|(_
, v
)| v
)
1035 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1036 impl<'a
, K
, V
> ExactSizeIterator
for ValuesMut
<'a
, K
, V
> {
1037 fn len(&self) -> usize {
1042 impl<'a
, K
, V
> Range
<'a
, K
, V
> {
1043 unsafe fn next_unchecked(&mut self) -> (&'a K
, &'a V
) {
1044 let handle
= self.front
;
1046 let mut cur_handle
= match handle
.right_kv() {
1048 let ret
= kv
.into_kv();
1049 self.front
= kv
.right_edge();
1053 let next_level
= last_edge
.into_node().ascend().ok();
1054 unwrap_unchecked(next_level
)
1059 match cur_handle
.right_kv() {
1061 let ret
= kv
.into_kv();
1062 self.front
= first_leaf_edge(kv
.right_edge().descend());
1066 let next_level
= last_edge
.into_node().ascend().ok();
1067 cur_handle
= unwrap_unchecked(next_level
);
1074 impl<'a
, K
, V
> DoubleEndedIterator
for Range
<'a
, K
, V
> {
1075 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
1076 if self.front
== self.back
{
1079 unsafe { Some(self.next_back_unchecked()) }
1084 impl<'a
, K
, V
> Range
<'a
, K
, V
> {
1085 unsafe fn next_back_unchecked(&mut self) -> (&'a K
, &'a V
) {
1086 let handle
= self.back
;
1088 let mut cur_handle
= match handle
.left_kv() {
1090 let ret
= kv
.into_kv();
1091 self.back
= kv
.left_edge();
1095 let next_level
= last_edge
.into_node().ascend().ok();
1096 unwrap_unchecked(next_level
)
1101 match cur_handle
.left_kv() {
1103 let ret
= kv
.into_kv();
1104 self.back
= last_leaf_edge(kv
.left_edge().descend());
1108 let next_level
= last_edge
.into_node().ascend().ok();
1109 cur_handle
= unwrap_unchecked(next_level
);
1116 impl<'a
, K
, V
> Clone
for Range
<'a
, K
, V
> {
1117 fn clone(&self) -> Range
<'a
, K
, V
> {
1125 impl<'a
, K
, V
> Iterator
for RangeMut
<'a
, K
, V
> {
1126 type Item
= (&'a K
, &'a
mut V
);
1128 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1129 if self.front
== self.back
{
1132 unsafe { Some (self.next_unchecked()) }
1137 impl<'a
, K
, V
> RangeMut
<'a
, K
, V
> {
1138 unsafe fn next_unchecked(&mut self) -> (&'a K
, &'a
mut V
) {
1139 let handle
= ptr
::read(&self.front
);
1141 let mut cur_handle
= match handle
.right_kv() {
1143 let (k
, v
) = ptr
::read(&kv
).into_kv_mut();
1144 self.front
= kv
.right_edge();
1148 let next_level
= last_edge
.into_node().ascend().ok();
1149 unwrap_unchecked(next_level
)
1154 match cur_handle
.right_kv() {
1156 let (k
, v
) = ptr
::read(&kv
).into_kv_mut();
1157 self.front
= first_leaf_edge(kv
.right_edge().descend());
1161 let next_level
= last_edge
.into_node().ascend().ok();
1162 cur_handle
= unwrap_unchecked(next_level
);
1169 impl<'a
, K
, V
> DoubleEndedIterator
for RangeMut
<'a
, K
, V
> {
1170 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1171 if self.front
== self.back
{
1174 unsafe { Some(self.next_back_unchecked()) }
1179 impl<'a
, K
, V
> RangeMut
<'a
, K
, V
> {
1180 unsafe fn next_back_unchecked(&mut self) -> (&'a K
, &'a
mut V
) {
1181 let handle
= ptr
::read(&self.back
);
1183 let mut cur_handle
= match handle
.left_kv() {
1185 let (k
, v
) = ptr
::read(&kv
).into_kv_mut();
1186 self.back
= kv
.left_edge();
1190 let next_level
= last_edge
.into_node().ascend().ok();
1191 unwrap_unchecked(next_level
)
1196 match cur_handle
.left_kv() {
1198 let (k
, v
) = ptr
::read(&kv
).into_kv_mut();
1199 self.back
= last_leaf_edge(kv
.left_edge().descend());
1203 let next_level
= last_edge
.into_node().ascend().ok();
1204 cur_handle
= unwrap_unchecked(next_level
);
1211 impl<K
: Ord
, V
> FromIterator
<(K
, V
)> for BTreeMap
<K
, V
> {
1212 fn from_iter
<T
: IntoIterator
<Item
=(K
, V
)>>(iter
: T
) -> BTreeMap
<K
, V
> {
1213 let mut map
= BTreeMap
::new();
1219 impl<K
: Ord
, V
> Extend
<(K
, V
)> for BTreeMap
<K
, V
> {
1221 fn extend
<T
: IntoIterator
<Item
=(K
, V
)>>(&mut self, iter
: T
) {
1222 for (k
, v
) in iter
{
1228 impl<'a
, K
: Ord
+ Copy
, V
: Copy
> Extend
<(&'a K
, &'a V
)> for BTreeMap
<K
, V
> {
1229 fn extend
<I
: IntoIterator
<Item
=(&'a K
, &'a V
)>>(&mut self, iter
: I
) {
1230 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
1234 impl<K
: Hash
, V
: Hash
> Hash
for BTreeMap
<K
, V
> {
1235 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
1242 impl<K
: Ord
, V
> Default
for BTreeMap
<K
, V
> {
1243 fn default() -> BTreeMap
<K
, V
> {
1248 impl<K
: PartialEq
, V
: PartialEq
> PartialEq
for BTreeMap
<K
, V
> {
1249 fn eq(&self, other
: &BTreeMap
<K
, V
>) -> bool
{
1250 self.len() == other
.len() &&
1251 self.iter().zip(other
).all(|(a
, b
)| a
== b
)
1255 impl<K
: Eq
, V
: Eq
> Eq
for BTreeMap
<K
, V
> {}
1257 impl<K
: PartialOrd
, V
: PartialOrd
> PartialOrd
for BTreeMap
<K
, V
> {
1259 fn partial_cmp(&self, other
: &BTreeMap
<K
, V
>) -> Option
<Ordering
> {
1260 self.iter().partial_cmp(other
.iter())
1264 impl<K
: Ord
, V
: Ord
> Ord
for BTreeMap
<K
, V
> {
1266 fn cmp(&self, other
: &BTreeMap
<K
, V
>) -> Ordering
{
1267 self.iter().cmp(other
.iter())
1271 impl<K
: Debug
, V
: Debug
> Debug
for BTreeMap
<K
, V
> {
1272 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1273 f
.debug_map().entries(self.iter()).finish()
1277 impl<'a
, K
: Ord
, Q
: ?Sized
, V
> Index
<&'a Q
> for BTreeMap
<K
, V
>
1278 where K
: Borrow
<Q
>, Q
: Ord
1283 fn index(&self, key
: &Q
) -> &V
{
1284 self.get(key
).expect("no entry found for key")
1288 fn first_leaf_edge
<BorrowType
, K
, V
>(
1289 mut node
: NodeRef
<BorrowType
,
1291 marker
::LeafOrInternal
>
1292 ) -> Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
> {
1294 match node
.force() {
1295 Leaf(leaf
) => return leaf
.first_edge(),
1296 Internal(internal
) => {
1297 node
= internal
.first_edge().descend();
1303 fn last_leaf_edge
<BorrowType
, K
, V
>(
1304 mut node
: NodeRef
<BorrowType
,
1306 marker
::LeafOrInternal
>
1307 ) -> Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
> {
1309 match node
.force() {
1310 Leaf(leaf
) => return leaf
.last_edge(),
1311 Internal(internal
) => {
1312 node
= internal
.last_edge().descend();
1319 unsafe fn unwrap_unchecked
<T
>(val
: Option
<T
>) -> T
{
1320 val
.unwrap_or_else(|| {
1321 if cfg
!(debug_assertions
) {
1322 panic
!("'unchecked' unwrap on None in BTreeMap");
1324 intrinsics
::unreachable();
1329 impl<K
, V
> BTreeMap
<K
, V
> {
1330 /// Gets an iterator over the entries of the map, sorted by key.
1337 /// use std::collections::BTreeMap;
1339 /// let mut map = BTreeMap::new();
1340 /// map.insert(3, "c");
1341 /// map.insert(2, "b");
1342 /// map.insert(1, "a");
1344 /// for (key, value) in map.iter() {
1345 /// println!("{}: {}", key, value);
1348 /// let (first_key, first_value) = map.iter().next().unwrap();
1349 /// assert_eq!((*first_key, *first_value), (1, "a"));
1351 #[stable(feature = "rust1", since = "1.0.0")]
1352 pub fn iter(&self) -> Iter
<K
, V
> {
1355 front
: first_leaf_edge(self.root
.as_ref()),
1356 back
: last_leaf_edge(self.root
.as_ref())
1362 /// Gets a mutable iterator over the entries of the map, sorted by key.
1369 /// use std::collections::BTreeMap;
1371 /// let mut map = BTreeMap::new();
1372 /// map.insert("a", 1);
1373 /// map.insert("b", 2);
1374 /// map.insert("c", 3);
1376 /// // add 10 to the value if the key isn't "a"
1377 /// for (key, value) in map.iter_mut() {
1378 /// if key != &"a" {
1383 #[stable(feature = "rust1", since = "1.0.0")]
1384 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
1385 let root1
= self.root
.as_mut();
1386 let root2
= unsafe { ptr::read(&root1) }
;
1389 front
: first_leaf_edge(root1
),
1390 back
: last_leaf_edge(root2
),
1391 _marker
: PhantomData
,
1397 /// Gets an iterator over the keys of the map, in sorted order.
1404 /// use std::collections::BTreeMap;
1406 /// let mut a = BTreeMap::new();
1407 /// a.insert(2, "b");
1408 /// a.insert(1, "a");
1410 /// let keys: Vec<_> = a.keys().cloned().collect();
1411 /// assert_eq!(keys, [1, 2]);
1413 #[stable(feature = "rust1", since = "1.0.0")]
1414 pub fn keys
<'a
>(&'a
self) -> Keys
<'a
, K
, V
> {
1415 Keys { inner: self.iter() }
1418 /// Gets an iterator over the values of the map, in order by key.
1425 /// use std::collections::BTreeMap;
1427 /// let mut a = BTreeMap::new();
1428 /// a.insert(1, "hello");
1429 /// a.insert(2, "goodbye");
1431 /// let values: Vec<&str> = a.values().cloned().collect();
1432 /// assert_eq!(values, ["hello", "goodbye"]);
1434 #[stable(feature = "rust1", since = "1.0.0")]
1435 pub fn values
<'a
>(&'a
self) -> Values
<'a
, K
, V
> {
1436 Values { inner: self.iter() }
1439 /// Gets a mutable iterator over the values of the map, in order by key.
1446 /// # #![feature(map_values_mut)]
1447 /// use std::collections::BTreeMap;
1449 /// let mut a = BTreeMap::new();
1450 /// a.insert(1, String::from("hello"));
1451 /// a.insert(2, String::from("goodbye"));
1453 /// for value in a.values_mut() {
1454 /// value.push_str("!");
1457 /// let values: Vec<String> = a.values().cloned().collect();
1458 /// assert_eq!(values, [String::from("hello!"),
1459 /// String::from("goodbye!")]);
1461 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1462 pub fn values_mut
<'a
>(&'a
mut self) -> ValuesMut
<'a
, K
, V
> {
1463 ValuesMut { inner: self.iter_mut() }
1466 /// Returns the number of elements in the map.
1473 /// use std::collections::BTreeMap;
1475 /// let mut a = BTreeMap::new();
1476 /// assert_eq!(a.len(), 0);
1477 /// a.insert(1, "a");
1478 /// assert_eq!(a.len(), 1);
1480 #[stable(feature = "rust1", since = "1.0.0")]
1481 pub fn len(&self) -> usize {
1485 /// Returns true if the map contains no elements.
1492 /// use std::collections::BTreeMap;
1494 /// let mut a = BTreeMap::new();
1495 /// assert!(a.is_empty());
1496 /// a.insert(1, "a");
1497 /// assert!(!a.is_empty());
1499 #[stable(feature = "rust1", since = "1.0.0")]
1500 pub fn is_empty(&self) -> bool
{
1505 impl<'a
, K
: Ord
, V
> Entry
<'a
, K
, V
> {
1506 /// Ensures a value is in the entry by inserting the default if empty, and returns
1507 /// a mutable reference to the value in the entry.
1508 #[stable(feature = "rust1", since = "1.0.0")]
1509 pub fn or_insert(self, default: V
) -> &'a
mut V
{
1511 Occupied(entry
) => entry
.into_mut(),
1512 Vacant(entry
) => entry
.insert(default),
1516 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1517 /// and returns a mutable reference to the value in the entry.
1518 #[stable(feature = "rust1", since = "1.0.0")]
1519 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
1521 Occupied(entry
) => entry
.into_mut(),
1522 Vacant(entry
) => entry
.insert(default()),
1527 impl<'a
, K
: Ord
, V
> VacantEntry
<'a
, K
, V
> {
1528 /// Gets a reference to the key that would be used when inserting a value
1529 /// through the VacantEntry.
1530 #[unstable(feature = "map_entry_keys", issue = "32281")]
1531 pub fn key(&self) -> &K
{
1535 /// Sets the value of the entry with the VacantEntry's key,
1536 /// and returns a mutable reference to it.
1537 #[stable(feature = "rust1", since = "1.0.0")]
1538 pub fn insert(self, value
: V
) -> &'a
mut V
{
1547 let mut cur_parent
= match self.handle
.insert(self.key
, value
) {
1548 (Fit(handle
), _
) => return handle
.into_kv_mut().1,
1549 (Split(left
, k
, v
, right
), ptr
) => {
1554 left
.ascend().map_err(|n
| n
.into_root_mut())
1560 Ok(parent
) => match parent
.insert(ins_k
, ins_v
, ins_edge
) {
1561 Fit(_
) => return unsafe { &mut *out_ptr }
,
1562 Split(left
, k
, v
, right
) => {
1566 cur_parent
= left
.ascend().map_err(|n
| n
.into_root_mut());
1570 root
.push_level().push(ins_k
, ins_v
, ins_edge
);
1571 return unsafe { &mut *out_ptr }
;
1578 impl<'a
, K
: Ord
, V
> OccupiedEntry
<'a
, K
, V
> {
1579 /// Gets a reference to the key in the entry.
1580 #[unstable(feature = "map_entry_keys", issue = "32281")]
1581 pub fn key(&self) -> &K
{
1582 self.handle
.reborrow().into_kv().0
1585 /// Gets a reference to the value in the entry.
1586 #[stable(feature = "rust1", since = "1.0.0")]
1587 pub fn get(&self) -> &V
{
1588 self.handle
.reborrow().into_kv().1
1591 /// Gets a mutable reference to the value in the entry.
1592 #[stable(feature = "rust1", since = "1.0.0")]
1593 pub fn get_mut(&mut self) -> &mut V
{
1594 self.handle
.kv_mut().1
1597 /// Converts the entry into a mutable reference to its value.
1598 #[stable(feature = "rust1", since = "1.0.0")]
1599 pub fn into_mut(self) -> &'a
mut V
{
1600 self.handle
.into_kv_mut().1
1603 /// Sets the value of the entry with the OccupiedEntry's key,
1604 /// and returns the entry's old value.
1605 #[stable(feature = "rust1", since = "1.0.0")]
1606 pub fn insert(&mut self, value
: V
) -> V
{
1607 mem
::replace(self.get_mut(), value
)
1610 /// Takes the value of the entry out of the map, and returns it.
1611 #[stable(feature = "rust1", since = "1.0.0")]
1612 pub fn remove(self) -> V
{
1616 fn remove_kv(self) -> (K
, V
) {
1619 let (small_leaf
, old_key
, old_val
) = match self.handle
.force() {
1621 let (hole
, old_key
, old_val
) = leaf
.remove();
1622 (hole
.into_node(), old_key
, old_val
)
1624 Internal(mut internal
) => {
1625 let key_loc
= internal
.kv_mut().0 as *mut K
;
1626 let val_loc
= internal
.kv_mut().1 as *mut V
;
1628 let to_remove
= first_leaf_edge(internal
.right_edge().descend()).right_kv().ok();
1629 let to_remove
= unsafe { unwrap_unchecked(to_remove) }
;
1631 let (hole
, key
, val
) = to_remove
.remove();
1633 let old_key
= unsafe {
1634 mem
::replace(&mut *key_loc
, key
)
1636 let old_val
= unsafe {
1637 mem
::replace(&mut *val_loc
, val
)
1640 (hole
.into_node(), old_key
, old_val
)
1645 let mut cur_node
= small_leaf
.forget_type();
1646 while cur_node
.len() < node
::CAPACITY
/ 2 {
1647 match handle_underfull_node(cur_node
) {
1649 EmptyParent(_
) => unreachable
!(),
1650 Merged(parent
) => if parent
.len() == 0 {
1651 // We must be at the root
1652 parent
.into_root_mut().pop_level();
1655 cur_node
= parent
.forget_type();
1665 enum UnderflowResult
<'a
, K
, V
> {
1667 EmptyParent(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>),
1668 Merged(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>),
1669 Stole(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>)
1672 fn handle_underfull_node
<'a
, K
, V
>(node
: NodeRef
<marker
::Mut
<'a
>,
1674 marker
::LeafOrInternal
>)
1675 -> UnderflowResult
<'a
, K
, V
> {
1676 let parent
= if let Ok(parent
) = node
.ascend() {
1682 let (is_left
, mut handle
) = match parent
.left_kv() {
1683 Ok(left
) => (true, left
),
1684 Err(parent
) => match parent
.right_kv() {
1685 Ok(right
) => (false, right
),
1687 return EmptyParent(parent
.into_node());
1692 if handle
.can_merge() {
1693 return Merged(handle
.merge().into_node());
1696 let (k
, v
, edge
) = if is_left
{
1697 handle
.reborrow_mut().left_edge().descend().pop()
1699 handle
.reborrow_mut().right_edge().descend().pop_front()
1702 let k
= mem
::replace(handle
.reborrow_mut().into_kv_mut().0, k
);
1703 let v
= mem
::replace(handle
.reborrow_mut().into_kv_mut().1, v
);
1705 // FIXME: reuse cur_node?
1707 match handle
.reborrow_mut().right_edge().descend().force() {
1708 Leaf(mut leaf
) => leaf
.push_front(k
, v
),
1709 Internal(mut internal
) => internal
.push_front(k
, v
, edge
.unwrap())
1712 match handle
.reborrow_mut().left_edge().descend().force() {
1713 Leaf(mut leaf
) => leaf
.push(k
, v
),
1714 Internal(mut internal
) => internal
.push(k
, v
, edge
.unwrap())
1719 return Stole(handle
.into_node());