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.
61 #[stable(feature = "rust1", since = "1.0.0")]
62 pub struct BTreeMap<K, V> {
63 root: node::Root<K, V>,
67 impl<K, V> Drop for BTreeMap<K, V> {
68 #[unsafe_destructor_blind_to_params]
71 for _ in ptr::read(self).into_iter() { }
76 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
77 fn clone(&self) -> BTreeMap<K, V> {
78 fn clone_subtree<K: Clone, V: Clone>(
79 node: node::NodeRef<marker::Immut, K, V, marker::LeafOrInternal>)
84 let mut out_tree = BTreeMap {
85 root: node::Root::new_leaf(),
90 let mut out_node = match out_tree.root.as_mut().force() {
92 Internal(_) => unreachable!()
95 let mut in_edge = leaf.first_edge();
96 while let Ok(kv) = in_edge.right_kv() {
97 let (k, v) = kv.into_kv();
98 in_edge = kv.right_edge();
100 out_node.push(k.clone(), v.clone());
101 out_tree.length += 1;
107 Internal(internal) => {
108 let mut out_tree = clone_subtree(internal.first_edge().descend());
111 let mut out_node = out_tree.root.push_level();
112 let mut in_edge = internal.first_edge();
113 while let Ok(kv) = in_edge.right_kv() {
114 let (k, v) = kv.into_kv();
115 in_edge = kv.right_edge();
117 let k = (*k).clone();
118 let v = (*v).clone();
119 let subtree = clone_subtree(in_edge.descend());
121 // We can't destructure subtree directly
122 // because BTreeMap implements Drop
123 let (subroot, sublength) = unsafe {
124 let root = ptr::read(&subtree.root);
125 let length = subtree.length;
126 mem::forget(subtree);
130 out_node.push(k, v, subroot);
131 out_tree.length += 1 + sublength;
140 clone_subtree(self.root.as_ref())
144 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
145 where K: Borrow<Q> + Ord,
150 fn get(&self, key: &Q) -> Option<&K> {
151 match search::search_tree(self.root.as_ref(), key) {
152 Found(handle) => Some(handle.into_kv().0),
157 fn take(&mut self, key: &Q) -> Option<K> {
158 match search::search_tree(self.root.as_mut(), key) {
162 length: &mut self.length,
163 _marker: PhantomData,
170 fn replace(&mut self, key: K) -> Option<K> {
171 match search::search_tree::<marker::Mut, K, (), K>(self.root.as_mut(), &key) {
172 Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
177 length: &mut self.length,
178 _marker: PhantomData,
186 /// An iterator over a BTreeMap's entries.
187 #[stable(feature = "rust1", since = "1.0.0")]
188 pub struct Iter<'a, K: 'a, V: 'a> {
189 range: Range<'a, K, V>,
193 /// A mutable iterator over a BTreeMap's entries.
194 #[stable(feature = "rust1", since = "1.0.0")]
195 pub struct IterMut<'a, K: 'a, V: 'a> {
196 range: RangeMut<'a, K, V>,
200 /// An owning iterator over a BTreeMap's entries.
201 #[stable(feature = "rust1", since = "1.0.0")]
202 pub struct IntoIter<K, V> {
203 front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
204 back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
208 /// An iterator over a BTreeMap's keys.
209 #[stable(feature = "rust1", since = "1.0.0")]
210 pub struct Keys<'a, K: 'a, V: 'a> {
211 inner: Iter<'a, K, V>,
214 /// An iterator over a BTreeMap's values.
215 #[stable(feature = "rust1", since = "1.0.0")]
216 pub struct Values<'a, K: 'a, V: 'a> {
217 inner: Iter<'a, K, V>,
220 /// An iterator over a sub-range of BTreeMap's entries.
221 pub struct Range<'a, K: 'a, V: 'a> {
222 front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
223 back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>
226 /// A mutable iterator over a sub-range of BTreeMap's entries.
227 pub struct RangeMut<'a, K: 'a, V: 'a> {
228 front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
229 back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
231 // Be invariant in `K` and `V`
232 _marker: PhantomData<&'a mut (K, V)>,
235 /// A view into a single entry in a map, which may either be vacant or occupied.
236 #[stable(feature = "rust1", since = "1.0.0")]
237 pub enum Entry<'a, K: 'a, V: 'a> {
239 #[stable(feature = "rust1", since = "1.0.0")]
241 #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] VacantEntry<'a, K, V>
244 /// An occupied Entry
245 #[stable(feature = "rust1", since = "1.0.0")]
247 #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] OccupiedEntry<'a, K, V>
252 #[stable(feature = "rust1", since = "1.0.0")]
253 pub struct VacantEntry<'a, K: 'a, V: 'a> {
255 handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
256 length: &'a mut usize,
258 // Be invariant in `K` and `V`
259 _marker: PhantomData<&'a mut (K, V)>,
262 /// An occupied Entry.
263 #[stable(feature = "rust1", since = "1.0.0")]
264 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
265 handle: Handle<NodeRef<
268 marker::LeafOrInternal
271 length: &'a mut usize,
273 // Be invariant in `K` and `V`
274 _marker: PhantomData<&'a mut (K, V)>,
277 impl<K: Ord, V> BTreeMap<K, V> {
278 /// Makes a new empty BTreeMap with a reasonable choice for B.
279 #[stable(feature = "rust1", since = "1.0.0")]
280 pub fn new() -> BTreeMap<K, V> {
282 root: node::Root::new_leaf(),
287 /// Clears the map, removing all values.
292 /// use std::collections::BTreeMap;
294 /// let mut a = BTreeMap::new();
295 /// a.insert(1, "a");
297 /// assert!(a.is_empty());
299 #[stable(feature = "rust1", since = "1.0.0")]
300 pub fn clear(&mut self) {
301 // FIXME(gereeter) .clear() allocates
302 *self = BTreeMap::new();
305 /// Returns a reference to the value corresponding to the key.
307 /// The key may be any borrowed form of the map's key type, but the ordering
308 /// on the borrowed form *must* match the ordering on the key type.
313 /// use std::collections::BTreeMap;
315 /// let mut map = BTreeMap::new();
316 /// map.insert(1, "a");
317 /// assert_eq!(map.get(&1), Some(&"a"));
318 /// assert_eq!(map.get(&2), None);
320 #[stable(feature = "rust1", since = "1.0.0")]
321 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
322 match search::search_tree(self.root.as_ref(), key) {
323 Found(handle) => Some(handle.into_kv().1),
328 /// Returns true if the map contains a value for the specified key.
330 /// The key may be any borrowed form of the map's key type, but the ordering
331 /// on the borrowed form *must* match the ordering on the key type.
336 /// use std::collections::BTreeMap;
338 /// let mut map = BTreeMap::new();
339 /// map.insert(1, "a");
340 /// assert_eq!(map.contains_key(&1), true);
341 /// assert_eq!(map.contains_key(&2), false);
343 #[stable(feature = "rust1", since = "1.0.0")]
344 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
345 self.get(key).is_some()
348 /// Returns a mutable reference to the value corresponding to the key.
350 /// The key may be any borrowed form of the map's key type, but the ordering
351 /// on the borrowed form *must* match the ordering on the key type.
356 /// use std::collections::BTreeMap;
358 /// let mut map = BTreeMap::new();
359 /// map.insert(1, "a");
360 /// if let Some(x) = map.get_mut(&1) {
363 /// assert_eq!(map[&1], "b");
365 // See `get` for implementation notes, this is basically a copy-paste with mut's added
366 #[stable(feature = "rust1", since = "1.0.0")]
367 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
368 match search::search_tree(self.root.as_mut(), key) {
369 Found(handle) => Some(handle.into_kv_mut().1),
374 /// Inserts a key-value pair into the map.
376 /// If the map did not have this key present, `None` is returned.
378 /// If the map did have this key present, the key is not updated, the
379 /// value is updated and the old value is returned.
380 /// See the [module-level documentation] for more.
382 /// [module-level documentation]: index.html#insert-and-complex-keys
387 /// use std::collections::BTreeMap;
389 /// let mut map = BTreeMap::new();
390 /// assert_eq!(map.insert(37, "a"), None);
391 /// assert_eq!(map.is_empty(), false);
393 /// map.insert(37, "b");
394 /// assert_eq!(map.insert(37, "c"), Some("b"));
395 /// assert_eq!(map[&37], "c");
397 #[stable(feature = "rust1", since = "1.0.0")]
398 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
399 match self.entry(key) {
400 Occupied(mut entry) => Some(entry.insert(value)),
408 /// Removes a key from the map, returning the value at the key if the key
409 /// was previously in the map.
411 /// The key may be any borrowed form of the map's key type, but the ordering
412 /// on the borrowed form *must* match the ordering on the key type.
417 /// use std::collections::BTreeMap;
419 /// let mut map = BTreeMap::new();
420 /// map.insert(1, "a");
421 /// assert_eq!(map.remove(&1), Some("a"));
422 /// assert_eq!(map.remove(&1), None);
424 #[stable(feature = "rust1", since = "1.0.0")]
425 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
426 match search::search_tree(self.root.as_mut(), key) {
430 length: &mut self.length,
431 _marker: PhantomData,
438 /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
439 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
440 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
441 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
446 /// #![feature(btree_range, collections_bound)]
448 /// use std::collections::BTreeMap;
449 /// use std::collections::Bound::{Included, Unbounded};
451 /// let mut map = BTreeMap::new();
452 /// map.insert(3, "a");
453 /// map.insert(5, "b");
454 /// map.insert(8, "c");
455 /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
456 /// println!("{}: {}", key, value);
458 /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
460 #[unstable(feature = "btree_range",
461 reason = "matches collection reform specification, waiting for dust to settle",
463 pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
467 where K: Borrow<Min> + Borrow<Max>,
469 let front = match min {
470 Included(key) => match search::search_tree(self.root.as_ref(), key) {
471 Found(kv_handle) => match kv_handle.left_edge().force() {
472 Leaf(bottom) => bottom,
473 Internal(internal) => last_leaf_edge(internal.descend())
475 GoDown(bottom) => bottom
477 Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
478 Found(kv_handle) => match kv_handle.right_edge().force() {
479 Leaf(bottom) => bottom,
480 Internal(internal) => first_leaf_edge(internal.descend())
482 GoDown(bottom) => bottom
484 Unbounded => first_leaf_edge(self.root.as_ref())
487 let back = match max {
488 Included(key) => match search::search_tree(self.root.as_ref(), key) {
489 Found(kv_handle) => match kv_handle.right_edge().force() {
490 Leaf(bottom) => bottom,
491 Internal(internal) => first_leaf_edge(internal.descend())
493 GoDown(bottom) => bottom
495 Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
496 Found(kv_handle) => match kv_handle.left_edge().force() {
497 Leaf(bottom) => bottom,
498 Internal(internal) => last_leaf_edge(internal.descend())
500 GoDown(bottom) => bottom
502 Unbounded => last_leaf_edge(self.root.as_ref())
511 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
512 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
513 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
514 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
519 /// #![feature(btree_range, collections_bound)]
521 /// use std::collections::BTreeMap;
522 /// use std::collections::Bound::{Included, Excluded};
524 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
525 /// .map(|&s| (s, 0))
527 /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
530 /// for (name, balance) in &map {
531 /// println!("{} => {}", name, balance);
534 #[unstable(feature = "btree_range",
535 reason = "matches collection reform specification, waiting for dust to settle",
537 pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
541 where K: Borrow<Min> + Borrow<Max>,
543 let root1 = self.root.as_mut();
544 let root2 = unsafe { ptr::read(&root1) };
546 let front = match min {
547 Included(key) => match search::search_tree(root1, key) {
548 Found(kv_handle) => match kv_handle.left_edge().force() {
549 Leaf(bottom) => bottom,
550 Internal(internal) => last_leaf_edge(internal.descend())
552 GoDown(bottom) => bottom
554 Excluded(key) => match search::search_tree(root1, key) {
555 Found(kv_handle) => match kv_handle.right_edge().force() {
556 Leaf(bottom) => bottom,
557 Internal(internal) => first_leaf_edge(internal.descend())
559 GoDown(bottom) => bottom
561 Unbounded => first_leaf_edge(root1)
564 let back = match max {
565 Included(key) => match search::search_tree(root2, key) {
566 Found(kv_handle) => match kv_handle.right_edge().force() {
567 Leaf(bottom) => bottom,
568 Internal(internal) => first_leaf_edge(internal.descend())
570 GoDown(bottom) => bottom
572 Excluded(key) => match search::search_tree(root2, key) {
573 Found(kv_handle) => match kv_handle.left_edge().force() {
574 Leaf(bottom) => bottom,
575 Internal(internal) => last_leaf_edge(internal.descend())
577 GoDown(bottom) => bottom
579 Unbounded => last_leaf_edge(root2)
589 /// Gets the given key's corresponding entry in the map for in-place manipulation.
594 /// use std::collections::BTreeMap;
596 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
598 /// // count the number of occurrences of letters in the vec
599 /// for x in vec!["a","b","a","c","a","b"] {
600 /// *count.entry(x).or_insert(0) += 1;
603 /// assert_eq!(count["a"], 3);
605 #[stable(feature = "rust1", since = "1.0.0")]
606 pub fn entry(&mut self, key: K) -> Entry<K, V> {
607 match search::search_tree(self.root.as_mut(), &key) {
608 Found(handle) => Occupied(OccupiedEntry {
610 length: &mut self.length,
611 _marker: PhantomData,
613 GoDown(handle) => Vacant(VacantEntry {
616 length: &mut self.length,
617 _marker: PhantomData,
623 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
624 type Item = (&'a K, &'a V);
625 type IntoIter = Iter<'a, K, V>;
627 fn into_iter(self) -> Iter<'a, K, V> {
632 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
633 type Item = (&'a K, &'a V);
635 fn next(&mut self) -> Option<(&'a K, &'a V)> {
636 if self.length == 0 {
640 unsafe { Some(self.range.next_unchecked()) }
644 fn size_hint(&self) -> (usize, Option<usize>) {
645 (self.length, Some(self.length))
649 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
650 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
651 if self.length == 0 {
655 unsafe { Some(self.range.next_back_unchecked()) }
660 impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
661 fn len(&self) -> usize { self.length }
664 impl<'a, K, V> Clone for Iter<'a, K, V> {
665 fn clone(&self) -> Iter<'a, K, V> {
667 range: self.range.clone(),
673 impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
674 type Item = (&'a K, &'a mut V);
675 type IntoIter = IterMut<'a, K, V>;
677 fn into_iter(self) -> IterMut<'a, K, V> {
682 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
683 type Item = (&'a K, &'a mut V);
685 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
686 if self.length == 0 {
690 unsafe { Some(self.range.next_unchecked()) }
694 fn size_hint(&self) -> (usize, Option<usize>) {
695 (self.length, Some(self.length))
699 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
700 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
701 if self.length == 0 {
705 unsafe { Some(self.range.next_back_unchecked()) }
710 impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
711 fn len(&self) -> usize { self.length }
714 impl<K, V> IntoIterator for BTreeMap<K, V> {
716 type IntoIter = IntoIter<K, V>;
718 fn into_iter(self) -> IntoIter<K, V> {
719 let root1 = unsafe { ptr::read(&self.root).into_ref() };
720 let root2 = unsafe { ptr::read(&self.root).into_ref() };
721 let len = self.length;
725 front: first_leaf_edge(root1),
726 back: last_leaf_edge(root2),
732 impl<K, V> Drop for IntoIter<K, V> {
734 for _ in &mut *self { }
736 let leaf_node = ptr::read(&self.front).into_node();
737 if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
738 let mut cur_node = first_parent.into_node();
739 while let Some(parent) = cur_node.deallocate_and_ascend() {
740 cur_node = parent.into_node()
747 impl<K, V> Iterator for IntoIter<K, V> {
750 fn next(&mut self) -> Option<(K, V)> {
751 if self.length == 0 {
757 let handle = unsafe { ptr::read(&self.front) };
759 let mut cur_handle = match handle.right_kv() {
761 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
762 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
763 self.front = kv.right_edge();
766 Err(last_edge) => unsafe {
767 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
772 match cur_handle.right_kv() {
774 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
775 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
776 self.front = first_leaf_edge(kv.right_edge().descend());
779 Err(last_edge) => unsafe {
780 cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
786 fn size_hint(&self) -> (usize, Option<usize>) {
787 (self.length, Some(self.length))
791 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
792 fn next_back(&mut self) -> Option<(K, V)> {
793 if self.length == 0 {
799 let handle = unsafe { ptr::read(&self.back) };
801 let mut cur_handle = match handle.left_kv() {
803 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
804 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
805 self.back = kv.left_edge();
808 Err(last_edge) => unsafe {
809 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
814 match cur_handle.left_kv() {
816 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
817 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
818 self.back = last_leaf_edge(kv.left_edge().descend());
821 Err(last_edge) => unsafe {
822 cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
829 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
830 fn len(&self) -> usize { self.length }
833 impl<'a, K, V> Iterator for Keys<'a, K, V> {
836 fn next(&mut self) -> Option<&'a K> {
837 self.inner.next().map(|(k, _)| k)
840 fn size_hint(&self) -> (usize, Option<usize>) {
841 self.inner.size_hint()
845 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
846 fn next_back(&mut self) -> Option<&'a K> {
847 self.inner.next_back().map(|(k, _)| k)
851 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
852 fn len(&self) -> usize {
857 impl<'a, K, V> Clone for Keys<'a, K, V> {
858 fn clone(&self) -> Keys<'a, K, V> {
860 inner: self.inner.clone()
865 impl<'a, K, V> Iterator for Values<'a, K, V> {
868 fn next(&mut self) -> Option<&'a V> {
869 self.inner.next().map(|(_, v)| v)
872 fn size_hint(&self) -> (usize, Option<usize>) {
873 self.inner.size_hint()
877 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
878 fn next_back(&mut self) -> Option<&'a V> {
879 self.inner.next_back().map(|(_, v)| v)
883 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
884 fn len(&self) -> usize {
889 impl<'a, K, V> Clone for Values<'a, K, V> {
890 fn clone(&self) -> Values<'a, K, V> {
892 inner: self.inner.clone()
897 impl<'a, K, V> Iterator for Range<'a, K, V> {
898 type Item = (&'a K, &'a V);
900 fn next(&mut self) -> Option<(&'a K, &'a V)> {
901 if self.front == self.back {
904 unsafe { Some(self.next_unchecked()) }
909 impl<'a, K, V> Range<'a, K, V> {
910 unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
911 let handle = self.front;
913 let mut cur_handle = match handle.right_kv() {
915 let ret = kv.into_kv();
916 self.front = kv.right_edge();
920 let next_level = last_edge.into_node().ascend().ok();
921 unwrap_unchecked(next_level)
926 match cur_handle.right_kv() {
928 let ret = kv.into_kv();
929 self.front = first_leaf_edge(kv.right_edge().descend());
933 let next_level = last_edge.into_node().ascend().ok();
934 cur_handle = unwrap_unchecked(next_level);
941 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
942 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
943 if self.front == self.back {
946 unsafe { Some(self.next_back_unchecked()) }
951 impl<'a, K, V> Range<'a, K, V> {
952 unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
953 let handle = self.back;
955 let mut cur_handle = match handle.left_kv() {
957 let ret = kv.into_kv();
958 self.back = kv.left_edge();
962 let next_level = last_edge.into_node().ascend().ok();
963 unwrap_unchecked(next_level)
968 match cur_handle.left_kv() {
970 let ret = kv.into_kv();
971 self.back = last_leaf_edge(kv.left_edge().descend());
975 let next_level = last_edge.into_node().ascend().ok();
976 cur_handle = unwrap_unchecked(next_level);
983 impl<'a, K, V> Clone for Range<'a, K, V> {
984 fn clone(&self) -> Range<'a, K, V> {
992 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
993 type Item = (&'a K, &'a mut V);
995 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
996 if self.front == self.back {
999 unsafe { Some (self.next_unchecked()) }
1004 impl<'a, K, V> RangeMut<'a, K, V> {
1005 unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
1006 let handle = ptr::read(&self.front);
1008 let mut cur_handle = match handle.right_kv() {
1010 let (k, v) = ptr::read(&kv).into_kv_mut();
1011 self.front = kv.right_edge();
1015 let next_level = last_edge.into_node().ascend().ok();
1016 unwrap_unchecked(next_level)
1021 match cur_handle.right_kv() {
1023 let (k, v) = ptr::read(&kv).into_kv_mut();
1024 self.front = first_leaf_edge(kv.right_edge().descend());
1028 let next_level = last_edge.into_node().ascend().ok();
1029 cur_handle = unwrap_unchecked(next_level);
1036 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1037 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1038 if self.front == self.back {
1041 unsafe { Some(self.next_back_unchecked()) }
1046 impl<'a, K, V> RangeMut<'a, K, V> {
1047 unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
1048 let handle = ptr::read(&self.back);
1050 let mut cur_handle = match handle.left_kv() {
1052 let (k, v) = ptr::read(&kv).into_kv_mut();
1053 self.back = kv.left_edge();
1057 let next_level = last_edge.into_node().ascend().ok();
1058 unwrap_unchecked(next_level)
1063 match cur_handle.left_kv() {
1065 let (k, v) = ptr::read(&kv).into_kv_mut();
1066 self.back = last_leaf_edge(kv.left_edge().descend());
1070 let next_level = last_edge.into_node().ascend().ok();
1071 cur_handle = unwrap_unchecked(next_level);
1078 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1079 fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
1080 let mut map = BTreeMap::new();
1086 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1088 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1089 for (k, v) in iter {
1095 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1096 fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
1097 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1101 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1102 fn hash<H: Hasher>(&self, state: &mut H) {
1109 impl<K: Ord, V> Default for BTreeMap<K, V> {
1110 fn default() -> BTreeMap<K, V> {
1115 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
1116 fn eq(&self, other: &BTreeMap<K, V>) -> bool {
1117 self.len() == other.len() &&
1118 self.iter().zip(other).all(|(a, b)| a == b)
1122 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
1124 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
1126 fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
1127 self.iter().partial_cmp(other.iter())
1131 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
1133 fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
1134 self.iter().cmp(other.iter())
1138 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
1139 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1140 f.debug_map().entries(self.iter()).finish()
1144 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
1145 where K: Borrow<Q>, Q: Ord
1150 fn index(&self, key: &Q) -> &V {
1151 self.get(key).expect("no entry found for key")
1155 fn first_leaf_edge<BorrowType, K, V>(
1156 mut node: NodeRef<BorrowType,
1158 marker::LeafOrInternal>
1159 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1161 match node.force() {
1162 Leaf(leaf) => return leaf.first_edge(),
1163 Internal(internal) => {
1164 node = internal.first_edge().descend();
1170 fn last_leaf_edge<BorrowType, K, V>(
1171 mut node: NodeRef<BorrowType,
1173 marker::LeafOrInternal>
1174 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1176 match node.force() {
1177 Leaf(leaf) => return leaf.last_edge(),
1178 Internal(internal) => {
1179 node = internal.last_edge().descend();
1186 unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
1187 val.unwrap_or_else(|| {
1188 if cfg!(debug_assertions) {
1189 panic!("'unchecked' unwrap on None in BTreeMap");
1191 intrinsics::unreachable();
1196 impl<K, V> BTreeMap<K, V> {
1197 /// Gets an iterator over the entries of the map, sorted by key.
1202 /// use std::collections::BTreeMap;
1204 /// let mut map = BTreeMap::new();
1205 /// map.insert(3, "c");
1206 /// map.insert(2, "b");
1207 /// map.insert(1, "a");
1209 /// for (key, value) in map.iter() {
1210 /// println!("{}: {}", key, value);
1213 /// let (first_key, first_value) = map.iter().next().unwrap();
1214 /// assert_eq!((*first_key, *first_value), (1, "a"));
1216 #[stable(feature = "rust1", since = "1.0.0")]
1217 pub fn iter(&self) -> Iter<K, V> {
1220 front: first_leaf_edge(self.root.as_ref()),
1221 back: last_leaf_edge(self.root.as_ref())
1227 /// Gets a mutable iterator over the entries of the map, sorted by key.
1232 /// use std::collections::BTreeMap;
1234 /// let mut map = BTreeMap::new();
1235 /// map.insert("a", 1);
1236 /// map.insert("b", 2);
1237 /// map.insert("c", 3);
1239 /// // add 10 to the value if the key isn't "a"
1240 /// for (key, value) in map.iter_mut() {
1241 /// if key != &"a" {
1246 #[stable(feature = "rust1", since = "1.0.0")]
1247 pub fn iter_mut(&mut self) -> IterMut<K, V> {
1248 let root1 = self.root.as_mut();
1249 let root2 = unsafe { ptr::read(&root1) };
1252 front: first_leaf_edge(root1),
1253 back: last_leaf_edge(root2),
1254 _marker: PhantomData,
1260 /// Gets an iterator over the keys of the map, in sorted order.
1265 /// use std::collections::BTreeMap;
1267 /// let mut a = BTreeMap::new();
1268 /// a.insert(2, "b");
1269 /// a.insert(1, "a");
1271 /// let keys: Vec<_> = a.keys().cloned().collect();
1272 /// assert_eq!(keys, [1, 2]);
1274 #[stable(feature = "rust1", since = "1.0.0")]
1275 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1276 Keys { inner: self.iter() }
1279 /// Gets an iterator over the values of the map, in order by key.
1284 /// use std::collections::BTreeMap;
1286 /// let mut a = BTreeMap::new();
1287 /// a.insert(1, "hello");
1288 /// a.insert(2, "goodbye");
1290 /// let values: Vec<&str> = a.values().cloned().collect();
1291 /// assert_eq!(values, ["hello", "goodbye"]);
1293 #[stable(feature = "rust1", since = "1.0.0")]
1294 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1295 Values { inner: self.iter() }
1298 /// Returns the number of elements in the map.
1303 /// use std::collections::BTreeMap;
1305 /// let mut a = BTreeMap::new();
1306 /// assert_eq!(a.len(), 0);
1307 /// a.insert(1, "a");
1308 /// assert_eq!(a.len(), 1);
1310 #[stable(feature = "rust1", since = "1.0.0")]
1311 pub fn len(&self) -> usize {
1315 /// Returns true if the map contains no elements.
1320 /// use std::collections::BTreeMap;
1322 /// let mut a = BTreeMap::new();
1323 /// assert!(a.is_empty());
1324 /// a.insert(1, "a");
1325 /// assert!(!a.is_empty());
1327 #[stable(feature = "rust1", since = "1.0.0")]
1328 pub fn is_empty(&self) -> bool {
1333 impl<'a, K: Ord, V> Entry<'a, K, V> {
1334 /// Ensures a value is in the entry by inserting the default if empty, and returns
1335 /// a mutable reference to the value in the entry.
1336 #[stable(feature = "rust1", since = "1.0.0")]
1337 pub fn or_insert(self, default: V) -> &'a mut V {
1339 Occupied(entry) => entry.into_mut(),
1340 Vacant(entry) => entry.insert(default),
1344 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1345 /// and returns a mutable reference to the value in the entry.
1346 #[stable(feature = "rust1", since = "1.0.0")]
1347 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1349 Occupied(entry) => entry.into_mut(),
1350 Vacant(entry) => entry.insert(default()),
1355 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1356 /// Sets the value of the entry with the VacantEntry's key,
1357 /// and returns a mutable reference to it.
1358 #[stable(feature = "rust1", since = "1.0.0")]
1359 pub fn insert(self, value: V) -> &'a mut V {
1368 let mut cur_parent = match self.handle.insert(self.key, value) {
1369 (Fit(handle), _) => return handle.into_kv_mut().1,
1370 (Split(left, k, v, right), ptr) => {
1375 left.ascend().map_err(|n| n.into_root_mut())
1381 Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
1382 Fit(_) => return unsafe { &mut *out_ptr },
1383 Split(left, k, v, right) => {
1387 cur_parent = left.ascend().map_err(|n| n.into_root_mut());
1391 root.push_level().push(ins_k, ins_v, ins_edge);
1392 return unsafe { &mut *out_ptr };
1399 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1400 /// Gets a reference to the value in the entry.
1401 #[stable(feature = "rust1", since = "1.0.0")]
1402 pub fn get(&self) -> &V {
1403 self.handle.reborrow().into_kv().1
1406 /// Gets a mutable reference to the value in the entry.
1407 #[stable(feature = "rust1", since = "1.0.0")]
1408 pub fn get_mut(&mut self) -> &mut V {
1409 self.handle.kv_mut().1
1412 /// Converts the entry into a mutable reference to its value.
1413 #[stable(feature = "rust1", since = "1.0.0")]
1414 pub fn into_mut(self) -> &'a mut V {
1415 self.handle.into_kv_mut().1
1418 /// Sets the value of the entry with the OccupiedEntry's key,
1419 /// and returns the entry's old value.
1420 #[stable(feature = "rust1", since = "1.0.0")]
1421 pub fn insert(&mut self, value: V) -> V {
1422 mem::replace(self.get_mut(), value)
1425 /// Takes the value of the entry out of the map, and returns it.
1426 #[stable(feature = "rust1", since = "1.0.0")]
1427 pub fn remove(self) -> V {
1431 fn remove_kv(self) -> (K, V) {
1434 let (small_leaf, old_key, old_val) = match self.handle.force() {
1436 let (hole, old_key, old_val) = leaf.remove();
1437 (hole.into_node(), old_key, old_val)
1439 Internal(mut internal) => {
1440 let key_loc = internal.kv_mut().0 as *mut K;
1441 let val_loc = internal.kv_mut().1 as *mut V;
1443 let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
1444 let to_remove = unsafe { unwrap_unchecked(to_remove) };
1446 let (hole, key, val) = to_remove.remove();
1448 let old_key = unsafe {
1449 mem::replace(&mut *key_loc, key)
1451 let old_val = unsafe {
1452 mem::replace(&mut *val_loc, val)
1455 (hole.into_node(), old_key, old_val)
1460 let mut cur_node = small_leaf.forget_type();
1461 while cur_node.len() < node::CAPACITY / 2 {
1462 match handle_underfull_node(cur_node) {
1464 EmptyParent(_) => unreachable!(),
1465 Merged(parent) => if parent.len() == 0 {
1466 // We must be at the root
1467 parent.into_root_mut().pop_level();
1470 cur_node = parent.forget_type();
1480 enum UnderflowResult<'a, K, V> {
1482 EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1483 Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1484 Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
1487 fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
1489 marker::LeafOrInternal>)
1490 -> UnderflowResult<'a, K, V> {
1491 let parent = if let Ok(parent) = node.ascend() {
1497 let (is_left, mut handle) = match parent.left_kv() {
1498 Ok(left) => (true, left),
1499 Err(parent) => match parent.right_kv() {
1500 Ok(right) => (false, right),
1502 return EmptyParent(parent.into_node());
1507 if handle.can_merge() {
1508 return Merged(handle.merge().into_node());
1511 let (k, v, edge) = if is_left {
1512 handle.reborrow_mut().left_edge().descend().pop()
1514 handle.reborrow_mut().right_edge().descend().pop_front()
1517 let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
1518 let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
1520 // FIXME: reuse cur_node?
1522 match handle.reborrow_mut().right_edge().descend().force() {
1523 Leaf(mut leaf) => leaf.push_front(k, v),
1524 Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
1527 match handle.reborrow_mut().left_edge().descend().force() {
1528 Leaf(mut leaf) => leaf.push(k, v),
1529 Internal(mut internal) => internal.push(k, v, edge.unwrap())
1534 return Stole(handle.into_node());