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 value is updated, and the old
379 /// value is returned. The key is not updated, though; this matters for
380 /// types that can be `==` without being identical. See the [module-level
381 /// documentation] for more.
383 /// [module-level documentation]: index.html#insert-and-complex-keys
388 /// use std::collections::BTreeMap;
390 /// let mut map = BTreeMap::new();
391 /// assert_eq!(map.insert(37, "a"), None);
392 /// assert_eq!(map.is_empty(), false);
394 /// map.insert(37, "b");
395 /// assert_eq!(map.insert(37, "c"), Some("b"));
396 /// assert_eq!(map[&37], "c");
398 #[stable(feature = "rust1", since = "1.0.0")]
399 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
400 match self.entry(key) {
401 Occupied(mut entry) => Some(entry.insert(value)),
409 /// Removes a key from the map, returning the value at the key if the key
410 /// was previously in the map.
412 /// The key may be any borrowed form of the map's key type, but the ordering
413 /// on the borrowed form *must* match the ordering on the key type.
418 /// use std::collections::BTreeMap;
420 /// let mut map = BTreeMap::new();
421 /// map.insert(1, "a");
422 /// assert_eq!(map.remove(&1), Some("a"));
423 /// assert_eq!(map.remove(&1), None);
425 #[stable(feature = "rust1", since = "1.0.0")]
426 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
427 match search::search_tree(self.root.as_mut(), key) {
431 length: &mut self.length,
432 _marker: PhantomData,
439 /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
440 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
441 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
442 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
447 /// #![feature(btree_range, collections_bound)]
449 /// use std::collections::BTreeMap;
450 /// use std::collections::Bound::{Included, Unbounded};
452 /// let mut map = BTreeMap::new();
453 /// map.insert(3, "a");
454 /// map.insert(5, "b");
455 /// map.insert(8, "c");
456 /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
457 /// println!("{}: {}", key, value);
459 /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
461 #[unstable(feature = "btree_range",
462 reason = "matches collection reform specification, waiting for dust to settle",
464 pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
468 where K: Borrow<Min> + Borrow<Max>,
470 let front = match min {
471 Included(key) => match search::search_tree(self.root.as_ref(), key) {
472 Found(kv_handle) => match kv_handle.left_edge().force() {
473 Leaf(bottom) => bottom,
474 Internal(internal) => last_leaf_edge(internal.descend())
476 GoDown(bottom) => bottom
478 Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
479 Found(kv_handle) => match kv_handle.right_edge().force() {
480 Leaf(bottom) => bottom,
481 Internal(internal) => first_leaf_edge(internal.descend())
483 GoDown(bottom) => bottom
485 Unbounded => first_leaf_edge(self.root.as_ref())
488 let back = match max {
489 Included(key) => match search::search_tree(self.root.as_ref(), key) {
490 Found(kv_handle) => match kv_handle.right_edge().force() {
491 Leaf(bottom) => bottom,
492 Internal(internal) => first_leaf_edge(internal.descend())
494 GoDown(bottom) => bottom
496 Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
497 Found(kv_handle) => match kv_handle.left_edge().force() {
498 Leaf(bottom) => bottom,
499 Internal(internal) => last_leaf_edge(internal.descend())
501 GoDown(bottom) => bottom
503 Unbounded => last_leaf_edge(self.root.as_ref())
512 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
513 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
514 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
515 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
520 /// #![feature(btree_range, collections_bound)]
522 /// use std::collections::BTreeMap;
523 /// use std::collections::Bound::{Included, Excluded};
525 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
526 /// .map(|&s| (s, 0))
528 /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
531 /// for (name, balance) in &map {
532 /// println!("{} => {}", name, balance);
535 #[unstable(feature = "btree_range",
536 reason = "matches collection reform specification, waiting for dust to settle",
538 pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
542 where K: Borrow<Min> + Borrow<Max>,
544 let root1 = self.root.as_mut();
545 let root2 = unsafe { ptr::read(&root1) };
547 let front = match min {
548 Included(key) => match search::search_tree(root1, key) {
549 Found(kv_handle) => match kv_handle.left_edge().force() {
550 Leaf(bottom) => bottom,
551 Internal(internal) => last_leaf_edge(internal.descend())
553 GoDown(bottom) => bottom
555 Excluded(key) => match search::search_tree(root1, key) {
556 Found(kv_handle) => match kv_handle.right_edge().force() {
557 Leaf(bottom) => bottom,
558 Internal(internal) => first_leaf_edge(internal.descend())
560 GoDown(bottom) => bottom
562 Unbounded => first_leaf_edge(root1)
565 let back = match max {
566 Included(key) => match search::search_tree(root2, key) {
567 Found(kv_handle) => match kv_handle.right_edge().force() {
568 Leaf(bottom) => bottom,
569 Internal(internal) => first_leaf_edge(internal.descend())
571 GoDown(bottom) => bottom
573 Excluded(key) => match search::search_tree(root2, key) {
574 Found(kv_handle) => match kv_handle.left_edge().force() {
575 Leaf(bottom) => bottom,
576 Internal(internal) => last_leaf_edge(internal.descend())
578 GoDown(bottom) => bottom
580 Unbounded => last_leaf_edge(root2)
590 /// Gets the given key's corresponding entry in the map for in-place manipulation.
595 /// use std::collections::BTreeMap;
597 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
599 /// // count the number of occurrences of letters in the vec
600 /// for x in vec!["a","b","a","c","a","b"] {
601 /// *count.entry(x).or_insert(0) += 1;
604 /// assert_eq!(count["a"], 3);
606 #[stable(feature = "rust1", since = "1.0.0")]
607 pub fn entry(&mut self, key: K) -> Entry<K, V> {
608 match search::search_tree(self.root.as_mut(), &key) {
609 Found(handle) => Occupied(OccupiedEntry {
611 length: &mut self.length,
612 _marker: PhantomData,
614 GoDown(handle) => Vacant(VacantEntry {
617 length: &mut self.length,
618 _marker: PhantomData,
624 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
625 type Item = (&'a K, &'a V);
626 type IntoIter = Iter<'a, K, V>;
628 fn into_iter(self) -> Iter<'a, K, V> {
633 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
634 type Item = (&'a K, &'a V);
636 fn next(&mut self) -> Option<(&'a K, &'a V)> {
637 if self.length == 0 {
641 unsafe { Some(self.range.next_unchecked()) }
645 fn size_hint(&self) -> (usize, Option<usize>) {
646 (self.length, Some(self.length))
650 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
651 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
652 if self.length == 0 {
656 unsafe { Some(self.range.next_back_unchecked()) }
661 impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
662 fn len(&self) -> usize { self.length }
665 impl<'a, K, V> Clone for Iter<'a, K, V> {
666 fn clone(&self) -> Iter<'a, K, V> {
668 range: self.range.clone(),
674 impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
675 type Item = (&'a K, &'a mut V);
676 type IntoIter = IterMut<'a, K, V>;
678 fn into_iter(self) -> IterMut<'a, K, V> {
683 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
684 type Item = (&'a K, &'a mut V);
686 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
687 if self.length == 0 {
691 unsafe { Some(self.range.next_unchecked()) }
695 fn size_hint(&self) -> (usize, Option<usize>) {
696 (self.length, Some(self.length))
700 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
701 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
702 if self.length == 0 {
706 unsafe { Some(self.range.next_back_unchecked()) }
711 impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
712 fn len(&self) -> usize { self.length }
715 impl<K, V> IntoIterator for BTreeMap<K, V> {
717 type IntoIter = IntoIter<K, V>;
719 fn into_iter(self) -> IntoIter<K, V> {
720 let root1 = unsafe { ptr::read(&self.root).into_ref() };
721 let root2 = unsafe { ptr::read(&self.root).into_ref() };
722 let len = self.length;
726 front: first_leaf_edge(root1),
727 back: last_leaf_edge(root2),
733 impl<K, V> Drop for IntoIter<K, V> {
735 for _ in &mut *self { }
737 let leaf_node = ptr::read(&self.front).into_node();
738 if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
739 let mut cur_node = first_parent.into_node();
740 while let Some(parent) = cur_node.deallocate_and_ascend() {
741 cur_node = parent.into_node()
748 impl<K, V> Iterator for IntoIter<K, V> {
751 fn next(&mut self) -> Option<(K, V)> {
752 if self.length == 0 {
758 let handle = unsafe { ptr::read(&self.front) };
760 let mut cur_handle = match handle.right_kv() {
762 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
763 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
764 self.front = kv.right_edge();
767 Err(last_edge) => unsafe {
768 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
773 match cur_handle.right_kv() {
775 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
776 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
777 self.front = first_leaf_edge(kv.right_edge().descend());
780 Err(last_edge) => unsafe {
781 cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
787 fn size_hint(&self) -> (usize, Option<usize>) {
788 (self.length, Some(self.length))
792 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
793 fn next_back(&mut self) -> Option<(K, V)> {
794 if self.length == 0 {
800 let handle = unsafe { ptr::read(&self.back) };
802 let mut cur_handle = match handle.left_kv() {
804 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
805 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
806 self.back = kv.left_edge();
809 Err(last_edge) => unsafe {
810 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
815 match cur_handle.left_kv() {
817 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
818 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
819 self.back = last_leaf_edge(kv.left_edge().descend());
822 Err(last_edge) => unsafe {
823 cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
830 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
831 fn len(&self) -> usize { self.length }
834 impl<'a, K, V> Iterator for Keys<'a, K, V> {
837 fn next(&mut self) -> Option<&'a K> {
838 self.inner.next().map(|(k, _)| k)
841 fn size_hint(&self) -> (usize, Option<usize>) {
842 self.inner.size_hint()
846 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
847 fn next_back(&mut self) -> Option<&'a K> {
848 self.inner.next_back().map(|(k, _)| k)
852 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
853 fn len(&self) -> usize {
858 impl<'a, K, V> Clone for Keys<'a, K, V> {
859 fn clone(&self) -> Keys<'a, K, V> {
861 inner: self.inner.clone()
866 impl<'a, K, V> Iterator for Values<'a, K, V> {
869 fn next(&mut self) -> Option<&'a V> {
870 self.inner.next().map(|(_, v)| v)
873 fn size_hint(&self) -> (usize, Option<usize>) {
874 self.inner.size_hint()
878 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
879 fn next_back(&mut self) -> Option<&'a V> {
880 self.inner.next_back().map(|(_, v)| v)
884 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
885 fn len(&self) -> usize {
890 impl<'a, K, V> Clone for Values<'a, K, V> {
891 fn clone(&self) -> Values<'a, K, V> {
893 inner: self.inner.clone()
898 impl<'a, K, V> Iterator for Range<'a, K, V> {
899 type Item = (&'a K, &'a V);
901 fn next(&mut self) -> Option<(&'a K, &'a V)> {
902 if self.front == self.back {
905 unsafe { Some(self.next_unchecked()) }
910 impl<'a, K, V> Range<'a, K, V> {
911 unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
912 let handle = self.front;
914 let mut cur_handle = match handle.right_kv() {
916 let ret = kv.into_kv();
917 self.front = kv.right_edge();
921 let next_level = last_edge.into_node().ascend().ok();
922 unwrap_unchecked(next_level)
927 match cur_handle.right_kv() {
929 let ret = kv.into_kv();
930 self.front = first_leaf_edge(kv.right_edge().descend());
934 let next_level = last_edge.into_node().ascend().ok();
935 cur_handle = unwrap_unchecked(next_level);
942 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
943 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
944 if self.front == self.back {
947 unsafe { Some(self.next_back_unchecked()) }
952 impl<'a, K, V> Range<'a, K, V> {
953 unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
954 let handle = self.back;
956 let mut cur_handle = match handle.left_kv() {
958 let ret = kv.into_kv();
959 self.back = kv.left_edge();
963 let next_level = last_edge.into_node().ascend().ok();
964 unwrap_unchecked(next_level)
969 match cur_handle.left_kv() {
971 let ret = kv.into_kv();
972 self.back = last_leaf_edge(kv.left_edge().descend());
976 let next_level = last_edge.into_node().ascend().ok();
977 cur_handle = unwrap_unchecked(next_level);
984 impl<'a, K, V> Clone for Range<'a, K, V> {
985 fn clone(&self) -> Range<'a, K, V> {
993 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
994 type Item = (&'a K, &'a mut V);
996 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
997 if self.front == self.back {
1000 unsafe { Some (self.next_unchecked()) }
1005 impl<'a, K, V> RangeMut<'a, K, V> {
1006 unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
1007 let handle = ptr::read(&self.front);
1009 let mut cur_handle = match handle.right_kv() {
1011 let (k, v) = ptr::read(&kv).into_kv_mut();
1012 self.front = kv.right_edge();
1016 let next_level = last_edge.into_node().ascend().ok();
1017 unwrap_unchecked(next_level)
1022 match cur_handle.right_kv() {
1024 let (k, v) = ptr::read(&kv).into_kv_mut();
1025 self.front = first_leaf_edge(kv.right_edge().descend());
1029 let next_level = last_edge.into_node().ascend().ok();
1030 cur_handle = unwrap_unchecked(next_level);
1037 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1038 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1039 if self.front == self.back {
1042 unsafe { Some(self.next_back_unchecked()) }
1047 impl<'a, K, V> RangeMut<'a, K, V> {
1048 unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
1049 let handle = ptr::read(&self.back);
1051 let mut cur_handle = match handle.left_kv() {
1053 let (k, v) = ptr::read(&kv).into_kv_mut();
1054 self.back = kv.left_edge();
1058 let next_level = last_edge.into_node().ascend().ok();
1059 unwrap_unchecked(next_level)
1064 match cur_handle.left_kv() {
1066 let (k, v) = ptr::read(&kv).into_kv_mut();
1067 self.back = last_leaf_edge(kv.left_edge().descend());
1071 let next_level = last_edge.into_node().ascend().ok();
1072 cur_handle = unwrap_unchecked(next_level);
1079 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1080 fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
1081 let mut map = BTreeMap::new();
1087 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1089 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1090 for (k, v) in iter {
1096 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1097 fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
1098 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1102 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1103 fn hash<H: Hasher>(&self, state: &mut H) {
1110 impl<K: Ord, V> Default for BTreeMap<K, V> {
1111 fn default() -> BTreeMap<K, V> {
1116 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
1117 fn eq(&self, other: &BTreeMap<K, V>) -> bool {
1118 self.len() == other.len() &&
1119 self.iter().zip(other).all(|(a, b)| a == b)
1123 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
1125 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
1127 fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
1128 self.iter().partial_cmp(other.iter())
1132 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
1134 fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
1135 self.iter().cmp(other.iter())
1139 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
1140 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1141 f.debug_map().entries(self.iter()).finish()
1145 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
1146 where K: Borrow<Q>, Q: Ord
1151 fn index(&self, key: &Q) -> &V {
1152 self.get(key).expect("no entry found for key")
1156 fn first_leaf_edge<BorrowType, K, V>(
1157 mut node: NodeRef<BorrowType,
1159 marker::LeafOrInternal>
1160 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1162 match node.force() {
1163 Leaf(leaf) => return leaf.first_edge(),
1164 Internal(internal) => {
1165 node = internal.first_edge().descend();
1171 fn last_leaf_edge<BorrowType, K, V>(
1172 mut node: NodeRef<BorrowType,
1174 marker::LeafOrInternal>
1175 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1177 match node.force() {
1178 Leaf(leaf) => return leaf.last_edge(),
1179 Internal(internal) => {
1180 node = internal.last_edge().descend();
1187 unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
1188 val.unwrap_or_else(|| {
1189 if cfg!(debug_assertions) {
1190 panic!("'unchecked' unwrap on None in BTreeMap");
1192 intrinsics::unreachable();
1197 impl<K, V> BTreeMap<K, V> {
1198 /// Gets an iterator over the entries of the map, sorted by key.
1203 /// use std::collections::BTreeMap;
1205 /// let mut map = BTreeMap::new();
1206 /// map.insert(3, "c");
1207 /// map.insert(2, "b");
1208 /// map.insert(1, "a");
1210 /// for (key, value) in map.iter() {
1211 /// println!("{}: {}", key, value);
1214 /// let (first_key, first_value) = map.iter().next().unwrap();
1215 /// assert_eq!((*first_key, *first_value), (1, "a"));
1217 #[stable(feature = "rust1", since = "1.0.0")]
1218 pub fn iter(&self) -> Iter<K, V> {
1221 front: first_leaf_edge(self.root.as_ref()),
1222 back: last_leaf_edge(self.root.as_ref())
1228 /// Gets a mutable iterator over the entries of the map, sorted by key.
1233 /// use std::collections::BTreeMap;
1235 /// let mut map = BTreeMap::new();
1236 /// map.insert("a", 1);
1237 /// map.insert("b", 2);
1238 /// map.insert("c", 3);
1240 /// // add 10 to the value if the key isn't "a"
1241 /// for (key, value) in map.iter_mut() {
1242 /// if key != &"a" {
1247 #[stable(feature = "rust1", since = "1.0.0")]
1248 pub fn iter_mut(&mut self) -> IterMut<K, V> {
1249 let root1 = self.root.as_mut();
1250 let root2 = unsafe { ptr::read(&root1) };
1253 front: first_leaf_edge(root1),
1254 back: last_leaf_edge(root2),
1255 _marker: PhantomData,
1261 /// Gets an iterator over the keys of the map, in sorted order.
1266 /// use std::collections::BTreeMap;
1268 /// let mut a = BTreeMap::new();
1269 /// a.insert(2, "b");
1270 /// a.insert(1, "a");
1272 /// let keys: Vec<_> = a.keys().cloned().collect();
1273 /// assert_eq!(keys, [1, 2]);
1275 #[stable(feature = "rust1", since = "1.0.0")]
1276 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1277 Keys { inner: self.iter() }
1280 /// Gets an iterator over the values of the map, in order by key.
1285 /// use std::collections::BTreeMap;
1287 /// let mut a = BTreeMap::new();
1288 /// a.insert(1, "hello");
1289 /// a.insert(2, "goodbye");
1291 /// let values: Vec<&str> = a.values().cloned().collect();
1292 /// assert_eq!(values, ["hello", "goodbye"]);
1294 #[stable(feature = "rust1", since = "1.0.0")]
1295 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1296 Values { inner: self.iter() }
1299 /// Returns the number of elements in the map.
1304 /// use std::collections::BTreeMap;
1306 /// let mut a = BTreeMap::new();
1307 /// assert_eq!(a.len(), 0);
1308 /// a.insert(1, "a");
1309 /// assert_eq!(a.len(), 1);
1311 #[stable(feature = "rust1", since = "1.0.0")]
1312 pub fn len(&self) -> usize {
1316 /// Returns true if the map contains no elements.
1321 /// use std::collections::BTreeMap;
1323 /// let mut a = BTreeMap::new();
1324 /// assert!(a.is_empty());
1325 /// a.insert(1, "a");
1326 /// assert!(!a.is_empty());
1328 #[stable(feature = "rust1", since = "1.0.0")]
1329 pub fn is_empty(&self) -> bool {
1334 impl<'a, K: Ord, V> Entry<'a, K, V> {
1335 /// Ensures a value is in the entry by inserting the default if empty, and returns
1336 /// a mutable reference to the value in the entry.
1337 #[stable(feature = "rust1", since = "1.0.0")]
1338 pub fn or_insert(self, default: V) -> &'a mut V {
1340 Occupied(entry) => entry.into_mut(),
1341 Vacant(entry) => entry.insert(default),
1345 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1346 /// and returns a mutable reference to the value in the entry.
1347 #[stable(feature = "rust1", since = "1.0.0")]
1348 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1350 Occupied(entry) => entry.into_mut(),
1351 Vacant(entry) => entry.insert(default()),
1356 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1357 /// Sets the value of the entry with the VacantEntry's key,
1358 /// and returns a mutable reference to it.
1359 #[stable(feature = "rust1", since = "1.0.0")]
1360 pub fn insert(self, value: V) -> &'a mut V {
1369 let mut cur_parent = match self.handle.insert(self.key, value) {
1370 (Fit(handle), _) => return handle.into_kv_mut().1,
1371 (Split(left, k, v, right), ptr) => {
1376 left.ascend().map_err(|n| n.into_root_mut())
1382 Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
1383 Fit(_) => return unsafe { &mut *out_ptr },
1384 Split(left, k, v, right) => {
1388 cur_parent = left.ascend().map_err(|n| n.into_root_mut());
1392 root.push_level().push(ins_k, ins_v, ins_edge);
1393 return unsafe { &mut *out_ptr };
1400 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1401 /// Gets a reference to the value in the entry.
1402 #[stable(feature = "rust1", since = "1.0.0")]
1403 pub fn get(&self) -> &V {
1404 self.handle.reborrow().into_kv().1
1407 /// Gets a mutable reference to the value in the entry.
1408 #[stable(feature = "rust1", since = "1.0.0")]
1409 pub fn get_mut(&mut self) -> &mut V {
1410 self.handle.kv_mut().1
1413 /// Converts the entry into a mutable reference to its value.
1414 #[stable(feature = "rust1", since = "1.0.0")]
1415 pub fn into_mut(self) -> &'a mut V {
1416 self.handle.into_kv_mut().1
1419 /// Sets the value of the entry with the OccupiedEntry's key,
1420 /// and returns the entry's old value.
1421 #[stable(feature = "rust1", since = "1.0.0")]
1422 pub fn insert(&mut self, value: V) -> V {
1423 mem::replace(self.get_mut(), value)
1426 /// Takes the value of the entry out of the map, and returns it.
1427 #[stable(feature = "rust1", since = "1.0.0")]
1428 pub fn remove(self) -> V {
1432 fn remove_kv(self) -> (K, V) {
1435 let (small_leaf, old_key, old_val) = match self.handle.force() {
1437 let (hole, old_key, old_val) = leaf.remove();
1438 (hole.into_node(), old_key, old_val)
1440 Internal(mut internal) => {
1441 let key_loc = internal.kv_mut().0 as *mut K;
1442 let val_loc = internal.kv_mut().1 as *mut V;
1444 let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
1445 let to_remove = unsafe { unwrap_unchecked(to_remove) };
1447 let (hole, key, val) = to_remove.remove();
1449 let old_key = unsafe {
1450 mem::replace(&mut *key_loc, key)
1452 let old_val = unsafe {
1453 mem::replace(&mut *val_loc, val)
1456 (hole.into_node(), old_key, old_val)
1461 let mut cur_node = small_leaf.forget_type();
1462 while cur_node.len() < node::CAPACITY / 2 {
1463 match handle_underfull_node(cur_node) {
1465 EmptyParent(_) => unreachable!(),
1466 Merged(parent) => if parent.len() == 0 {
1467 // We must be at the root
1468 parent.into_root_mut().pop_level();
1471 cur_node = parent.forget_type();
1481 enum UnderflowResult<'a, K, V> {
1483 EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1484 Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1485 Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
1488 fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
1490 marker::LeafOrInternal>)
1491 -> UnderflowResult<'a, K, V> {
1492 let parent = if let Ok(parent) = node.ascend() {
1498 let (is_left, mut handle) = match parent.left_kv() {
1499 Ok(left) => (true, left),
1500 Err(parent) => match parent.right_kv() {
1501 Ok(right) => (false, right),
1503 return EmptyParent(parent.into_node());
1508 if handle.can_merge() {
1509 return Merged(handle.merge().into_node());
1512 let (k, v, edge) = if is_left {
1513 handle.reborrow_mut().left_edge().descend().pop()
1515 handle.reborrow_mut().right_edge().descend().pop_front()
1518 let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
1519 let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
1521 // FIXME: reuse cur_node?
1523 match handle.reborrow_mut().right_edge().descend().force() {
1524 Leaf(mut leaf) => leaf.push_front(k, v),
1525 Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
1528 match handle.reborrow_mut().left_edge().descend().force() {
1529 Leaf(mut leaf) => leaf.push(k, v),
1530 Internal(mut internal) => internal.push(k, v, edge.unwrap())
1535 return Stole(handle.into_node());