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;
16 use core::{fmt, intrinsics, mem, ptr};
19 use Bound::{self, Included, Excluded, Unbounded};
21 use super::node::{self, NodeRef, Handle, marker};
24 use super::node::InsertResult::*;
25 use super::node::ForceResult::*;
26 use super::search::SearchResult::*;
27 use self::UnderflowResult::*;
30 /// A map based on a B-Tree.
32 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
33 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
34 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
35 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
36 /// is done is *very* inefficient for modern computer architectures. In particular, every element
37 /// is stored in its own individually heap-allocated node. This means that every single insertion
38 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
39 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
42 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
43 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
44 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
45 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
46 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
47 /// the node using binary search. As a compromise, one could also perform a linear search
48 /// that initially only checks every i<sup>th</sup> element for some choice of i.
50 /// Currently, our implementation simply performs naive linear search. This provides excellent
51 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
52 /// would like to further explore choosing the optimal search strategy based on the choice of B,
53 /// and possibly other factors. Using linear search, searching for a random element is expected
54 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
55 /// however, performance is excellent.
57 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
58 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
59 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
60 #[stable(feature = "rust1", since = "1.0.0")]
61 pub struct BTreeMap<K, V> {
62 root: node::Root<K, V>,
66 impl<K, V> Drop for BTreeMap<K, V> {
67 #[unsafe_destructor_blind_to_params]
70 for _ in ptr::read(self).into_iter() { }
75 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
76 fn clone(&self) -> BTreeMap<K, V> {
77 fn clone_subtree<K: Clone, V: Clone>(
78 node: node::NodeRef<marker::Immut, K, V, marker::LeafOrInternal>)
83 let mut out_tree = BTreeMap {
84 root: node::Root::new_leaf(),
89 let mut out_node = match out_tree.root.as_mut().force() {
91 Internal(_) => unreachable!()
94 let mut in_edge = leaf.first_edge();
95 while let Ok(kv) = in_edge.right_kv() {
96 let (k, v) = kv.into_kv();
97 in_edge = kv.right_edge();
99 out_node.push(k.clone(), v.clone());
100 out_tree.length += 1;
106 Internal(internal) => {
107 let mut out_tree = clone_subtree(internal.first_edge().descend());
110 let mut out_node = out_tree.root.push_level();
111 let mut in_edge = internal.first_edge();
112 while let Ok(kv) = in_edge.right_kv() {
113 let (k, v) = kv.into_kv();
114 in_edge = kv.right_edge();
116 let k = (*k).clone();
117 let v = (*v).clone();
118 let subtree = clone_subtree(in_edge.descend());
120 // We can't destructure subtree directly
121 // because BTreeMap implements Drop
122 let (subroot, sublength) = unsafe {
123 let root = ptr::read(&subtree.root);
124 let length = subtree.length;
125 mem::forget(subtree);
129 out_node.push(k, v, subroot);
130 out_tree.length += 1 + sublength;
139 clone_subtree(self.root.as_ref())
143 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
144 where K: Borrow<Q> + Ord,
149 fn get(&self, key: &Q) -> Option<&K> {
150 match search::search_tree(self.root.as_ref(), key) {
151 Found(handle) => Some(handle.into_kv().0),
156 fn take(&mut self, key: &Q) -> Option<K> {
157 match search::search_tree(self.root.as_mut(), key) {
161 length: &mut self.length
168 fn replace(&mut self, key: K) -> Option<K> {
169 match search::search_tree::<marker::Mut, K, (), K>(self.root.as_mut(), &key) {
170 Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
175 length: &mut self.length
183 /// An iterator over a BTreeMap's entries.
184 #[stable(feature = "rust1", since = "1.0.0")]
185 pub struct Iter<'a, K: 'a, V: 'a> {
186 range: Range<'a, K, V>,
190 /// A mutable iterator over a BTreeMap's entries.
191 #[stable(feature = "rust1", since = "1.0.0")]
192 pub struct IterMut<'a, K: 'a, V: 'a> {
193 range: RangeMut<'a, K, V>,
197 /// An owning iterator over a BTreeMap's entries.
198 #[stable(feature = "rust1", since = "1.0.0")]
199 pub struct IntoIter<K, V> {
200 front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
201 back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
205 /// An iterator over a BTreeMap's keys.
206 #[stable(feature = "rust1", since = "1.0.0")]
207 pub struct Keys<'a, K: 'a, V: 'a> {
208 inner: Iter<'a, K, V>,
211 /// An iterator over a BTreeMap's values.
212 #[stable(feature = "rust1", since = "1.0.0")]
213 pub struct Values<'a, K: 'a, V: 'a> {
214 inner: Iter<'a, K, V>,
217 /// An iterator over a sub-range of BTreeMap's entries.
218 pub struct Range<'a, K: 'a, V: 'a> {
219 front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
220 back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>
223 /// A mutable iterator over a sub-range of BTreeMap's entries.
224 pub struct RangeMut<'a, K: 'a, V: 'a> {
225 front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
226 back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>
229 /// A view into a single entry in a map, which may either be vacant or occupied.
230 #[stable(feature = "rust1", since = "1.0.0")]
231 pub enum Entry<'a, K: 'a, V: 'a> {
233 #[stable(feature = "rust1", since = "1.0.0")]
235 #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] VacantEntry<'a, K, V>
238 /// An occupied Entry
239 #[stable(feature = "rust1", since = "1.0.0")]
241 #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] OccupiedEntry<'a, K, V>
246 #[stable(feature = "rust1", since = "1.0.0")]
247 pub struct VacantEntry<'a, K: 'a, V: 'a> {
249 handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
250 length: &'a mut usize
253 /// An occupied Entry.
254 #[stable(feature = "rust1", since = "1.0.0")]
255 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
256 handle: Handle<NodeRef<
259 marker::LeafOrInternal
262 length: &'a mut usize
265 impl<K: Ord, V> BTreeMap<K, V> {
266 /// Makes a new empty BTreeMap with a reasonable choice for B.
267 #[stable(feature = "rust1", since = "1.0.0")]
268 pub fn new() -> BTreeMap<K, V> {
270 root: node::Root::new_leaf(),
275 /// Clears the map, removing all values.
280 /// use std::collections::BTreeMap;
282 /// let mut a = BTreeMap::new();
283 /// a.insert(1, "a");
285 /// assert!(a.is_empty());
287 #[stable(feature = "rust1", since = "1.0.0")]
288 pub fn clear(&mut self) {
289 // FIXME(gereeter) .clear() allocates
290 *self = BTreeMap::new();
293 /// Returns a reference to the value corresponding to the key.
295 /// The key may be any borrowed form of the map's key type, but the ordering
296 /// on the borrowed form *must* match the ordering on the key type.
301 /// use std::collections::BTreeMap;
303 /// let mut map = BTreeMap::new();
304 /// map.insert(1, "a");
305 /// assert_eq!(map.get(&1), Some(&"a"));
306 /// assert_eq!(map.get(&2), None);
308 #[stable(feature = "rust1", since = "1.0.0")]
309 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
310 match search::search_tree(self.root.as_ref(), key) {
311 Found(handle) => Some(handle.into_kv().1),
316 /// Returns true if the map contains a value for the specified key.
318 /// The key may be any borrowed form of the map's key type, but the ordering
319 /// on the borrowed form *must* match the ordering on the key type.
324 /// use std::collections::BTreeMap;
326 /// let mut map = BTreeMap::new();
327 /// map.insert(1, "a");
328 /// assert_eq!(map.contains_key(&1), true);
329 /// assert_eq!(map.contains_key(&2), false);
331 #[stable(feature = "rust1", since = "1.0.0")]
332 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
333 self.get(key).is_some()
336 /// Returns a mutable reference to the value corresponding to the key.
338 /// The key may be any borrowed form of the map's key type, but the ordering
339 /// on the borrowed form *must* match the ordering on the key type.
344 /// use std::collections::BTreeMap;
346 /// let mut map = BTreeMap::new();
347 /// map.insert(1, "a");
348 /// if let Some(x) = map.get_mut(&1) {
351 /// assert_eq!(map[&1], "b");
353 // See `get` for implementation notes, this is basically a copy-paste with mut's added
354 #[stable(feature = "rust1", since = "1.0.0")]
355 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
356 match search::search_tree(self.root.as_mut(), key) {
357 Found(handle) => Some(handle.into_kv_mut().1),
362 /// Inserts a key-value pair into the map.
364 /// If the map did not have this key present, `None` is returned.
366 /// If the map did have this key present, the key is not updated, the
367 /// value is updated and the old value is returned.
368 /// See the [module-level documentation] for more.
370 /// [module-level documentation]: index.html#insert-and-complex-keys
375 /// use std::collections::BTreeMap;
377 /// let mut map = BTreeMap::new();
378 /// assert_eq!(map.insert(37, "a"), None);
379 /// assert_eq!(map.is_empty(), false);
381 /// map.insert(37, "b");
382 /// assert_eq!(map.insert(37, "c"), Some("b"));
383 /// assert_eq!(map[&37], "c");
385 #[stable(feature = "rust1", since = "1.0.0")]
386 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
387 match self.entry(key) {
388 Occupied(mut entry) => Some(entry.insert(value)),
396 /// Removes a key from the map, returning the value at the key if the key
397 /// was previously in the map.
399 /// The key may be any borrowed form of the map's key type, but the ordering
400 /// on the borrowed form *must* match the ordering on the key type.
405 /// use std::collections::BTreeMap;
407 /// let mut map = BTreeMap::new();
408 /// map.insert(1, "a");
409 /// assert_eq!(map.remove(&1), Some("a"));
410 /// assert_eq!(map.remove(&1), None);
412 #[stable(feature = "rust1", since = "1.0.0")]
413 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
414 match search::search_tree(self.root.as_mut(), key) {
418 length: &mut self.length
425 /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
426 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
427 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
428 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
433 /// #![feature(btree_range, collections_bound)]
435 /// use std::collections::BTreeMap;
436 /// use std::collections::Bound::{Included, Unbounded};
438 /// let mut map = BTreeMap::new();
439 /// map.insert(3, "a");
440 /// map.insert(5, "b");
441 /// map.insert(8, "c");
442 /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
443 /// println!("{}: {}", key, value);
445 /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
447 #[unstable(feature = "btree_range",
448 reason = "matches collection reform specification, waiting for dust to settle",
450 pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
454 where K: Borrow<Min> + Borrow<Max>,
456 let front = match min {
457 Included(key) => match search::search_tree(self.root.as_ref(), key) {
458 Found(kv_handle) => match kv_handle.left_edge().force() {
459 Leaf(bottom) => bottom,
460 Internal(internal) => last_leaf_edge(internal.descend())
462 GoDown(bottom) => bottom
464 Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
465 Found(kv_handle) => match kv_handle.right_edge().force() {
466 Leaf(bottom) => bottom,
467 Internal(internal) => first_leaf_edge(internal.descend())
469 GoDown(bottom) => bottom
471 Unbounded => first_leaf_edge(self.root.as_ref())
474 let back = match max {
475 Included(key) => match search::search_tree(self.root.as_ref(), key) {
476 Found(kv_handle) => match kv_handle.right_edge().force() {
477 Leaf(bottom) => bottom,
478 Internal(internal) => first_leaf_edge(internal.descend())
480 GoDown(bottom) => bottom
482 Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
483 Found(kv_handle) => match kv_handle.left_edge().force() {
484 Leaf(bottom) => bottom,
485 Internal(internal) => last_leaf_edge(internal.descend())
487 GoDown(bottom) => bottom
489 Unbounded => last_leaf_edge(self.root.as_ref())
498 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
499 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
500 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
501 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
506 /// #![feature(btree_range, collections_bound)]
508 /// use std::collections::BTreeMap;
509 /// use std::collections::Bound::{Included, Excluded};
511 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
512 /// .map(|&s| (s, 0))
514 /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
517 /// for (name, balance) in &map {
518 /// println!("{} => {}", name, balance);
521 #[unstable(feature = "btree_range",
522 reason = "matches collection reform specification, waiting for dust to settle",
524 pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
528 where K: Borrow<Min> + Borrow<Max>,
530 let root1 = self.root.as_mut();
531 let root2 = unsafe { ptr::read(&root1) };
533 let front = match min {
534 Included(key) => match search::search_tree(root1, key) {
535 Found(kv_handle) => match kv_handle.left_edge().force() {
536 Leaf(bottom) => bottom,
537 Internal(internal) => last_leaf_edge(internal.descend())
539 GoDown(bottom) => bottom
541 Excluded(key) => match search::search_tree(root1, key) {
542 Found(kv_handle) => match kv_handle.right_edge().force() {
543 Leaf(bottom) => bottom,
544 Internal(internal) => first_leaf_edge(internal.descend())
546 GoDown(bottom) => bottom
548 Unbounded => first_leaf_edge(root1)
551 let back = match max {
552 Included(key) => match search::search_tree(root2, key) {
553 Found(kv_handle) => match kv_handle.right_edge().force() {
554 Leaf(bottom) => bottom,
555 Internal(internal) => first_leaf_edge(internal.descend())
557 GoDown(bottom) => bottom
559 Excluded(key) => match search::search_tree(root2, key) {
560 Found(kv_handle) => match kv_handle.left_edge().force() {
561 Leaf(bottom) => bottom,
562 Internal(internal) => last_leaf_edge(internal.descend())
564 GoDown(bottom) => bottom
566 Unbounded => last_leaf_edge(root2)
575 /// Gets the given key's corresponding entry in the map for in-place manipulation.
580 /// use std::collections::BTreeMap;
582 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
584 /// // count the number of occurrences of letters in the vec
585 /// for x in vec!["a","b","a","c","a","b"] {
586 /// *count.entry(x).or_insert(0) += 1;
589 /// assert_eq!(count["a"], 3);
591 #[stable(feature = "rust1", since = "1.0.0")]
592 pub fn entry(&mut self, key: K) -> Entry<K, V> {
593 match search::search_tree(self.root.as_mut(), &key) {
594 Found(handle) => Occupied(OccupiedEntry {
596 length: &mut self.length
598 GoDown(handle) => Vacant(VacantEntry {
601 length: &mut self.length
607 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
608 type Item = (&'a K, &'a V);
609 type IntoIter = Iter<'a, K, V>;
611 fn into_iter(self) -> Iter<'a, K, V> {
616 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
617 type Item = (&'a K, &'a V);
619 fn next(&mut self) -> Option<(&'a K, &'a V)> {
620 if self.length == 0 {
624 unsafe { Some(self.range.next_unchecked()) }
628 fn size_hint(&self) -> (usize, Option<usize>) {
629 (self.length, Some(self.length))
633 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
634 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
635 if self.length == 0 {
639 unsafe { Some(self.range.next_back_unchecked()) }
644 impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
645 fn len(&self) -> usize { self.length }
648 impl<'a, K, V> Clone for Iter<'a, K, V> {
649 fn clone(&self) -> Iter<'a, K, V> {
651 range: self.range.clone(),
657 impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
658 type Item = (&'a K, &'a mut V);
659 type IntoIter = IterMut<'a, K, V>;
661 fn into_iter(self) -> IterMut<'a, K, V> {
666 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
667 type Item = (&'a K, &'a mut V);
669 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
670 if self.length == 0 {
674 unsafe { Some(self.range.next_unchecked()) }
678 fn size_hint(&self) -> (usize, Option<usize>) {
679 (self.length, Some(self.length))
683 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
684 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
685 if self.length == 0 {
689 unsafe { Some(self.range.next_back_unchecked()) }
694 impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
695 fn len(&self) -> usize { self.length }
698 impl<K, V> IntoIterator for BTreeMap<K, V> {
700 type IntoIter = IntoIter<K, V>;
702 fn into_iter(self) -> IntoIter<K, V> {
703 let root1 = unsafe { ptr::read(&self.root).into_ref() };
704 let root2 = unsafe { ptr::read(&self.root).into_ref() };
705 let len = self.length;
709 front: first_leaf_edge(root1),
710 back: last_leaf_edge(root2),
716 impl<K, V> Drop for IntoIter<K, V> {
718 for _ in &mut *self { }
720 let leaf_node = ptr::read(&self.front).into_node();
721 if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
722 let mut cur_node = first_parent.into_node();
723 while let Some(parent) = cur_node.deallocate_and_ascend() {
724 cur_node = parent.into_node()
731 impl<K, V> Iterator for IntoIter<K, V> {
734 fn next(&mut self) -> Option<(K, V)> {
735 if self.length == 0 {
741 let handle = unsafe { ptr::read(&self.front) };
743 let mut cur_handle = match handle.right_kv() {
745 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
746 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
747 self.front = kv.right_edge();
750 Err(last_edge) => unsafe {
751 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
756 match cur_handle.right_kv() {
758 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
759 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
760 self.front = first_leaf_edge(kv.right_edge().descend());
763 Err(last_edge) => unsafe {
764 cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
770 fn size_hint(&self) -> (usize, Option<usize>) {
771 (self.length, Some(self.length))
775 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
776 fn next_back(&mut self) -> Option<(K, V)> {
777 if self.length == 0 {
783 let handle = unsafe { ptr::read(&self.back) };
785 let mut cur_handle = match handle.left_kv() {
787 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
788 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
789 self.back = kv.left_edge();
792 Err(last_edge) => unsafe {
793 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
798 match cur_handle.left_kv() {
800 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
801 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
802 self.back = last_leaf_edge(kv.left_edge().descend());
805 Err(last_edge) => unsafe {
806 cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
813 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
814 fn len(&self) -> usize { self.length }
817 impl<'a, K, V> Iterator for Keys<'a, K, V> {
820 fn next(&mut self) -> Option<&'a K> {
821 self.inner.next().map(|(k, _)| k)
824 fn size_hint(&self) -> (usize, Option<usize>) {
825 self.inner.size_hint()
829 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
830 fn next_back(&mut self) -> Option<&'a K> {
831 self.inner.next_back().map(|(k, _)| k)
835 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
836 fn len(&self) -> usize {
841 impl<'a, K, V> Clone for Keys<'a, K, V> {
842 fn clone(&self) -> Keys<'a, K, V> {
844 inner: self.inner.clone()
849 impl<'a, K, V> Iterator for Values<'a, K, V> {
852 fn next(&mut self) -> Option<&'a V> {
853 self.inner.next().map(|(_, v)| v)
856 fn size_hint(&self) -> (usize, Option<usize>) {
857 self.inner.size_hint()
861 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
862 fn next_back(&mut self) -> Option<&'a V> {
863 self.inner.next_back().map(|(_, v)| v)
867 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
868 fn len(&self) -> usize {
873 impl<'a, K, V> Clone for Values<'a, K, V> {
874 fn clone(&self) -> Values<'a, K, V> {
876 inner: self.inner.clone()
881 impl<'a, K, V> Iterator for Range<'a, K, V> {
882 type Item = (&'a K, &'a V);
884 fn next(&mut self) -> Option<(&'a K, &'a V)> {
885 if self.front == self.back {
888 unsafe { Some(self.next_unchecked()) }
893 impl<'a, K, V> Range<'a, K, V> {
894 unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
895 let handle = self.front;
897 let mut cur_handle = match handle.right_kv() {
899 let ret = kv.into_kv();
900 self.front = kv.right_edge();
904 let next_level = last_edge.into_node().ascend().ok();
905 unwrap_unchecked(next_level)
910 match cur_handle.right_kv() {
912 let ret = kv.into_kv();
913 self.front = first_leaf_edge(kv.right_edge().descend());
917 let next_level = last_edge.into_node().ascend().ok();
918 cur_handle = unwrap_unchecked(next_level);
925 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
926 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
927 if self.front == self.back {
930 unsafe { Some(self.next_back_unchecked()) }
935 impl<'a, K, V> Range<'a, K, V> {
936 unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
937 let handle = self.back;
939 let mut cur_handle = match handle.left_kv() {
941 let ret = kv.into_kv();
942 self.back = kv.left_edge();
946 let next_level = last_edge.into_node().ascend().ok();
947 unwrap_unchecked(next_level)
952 match cur_handle.left_kv() {
954 let ret = kv.into_kv();
955 self.back = last_leaf_edge(kv.left_edge().descend());
959 let next_level = last_edge.into_node().ascend().ok();
960 cur_handle = unwrap_unchecked(next_level);
967 impl<'a, K, V> Clone for Range<'a, K, V> {
968 fn clone(&self) -> Range<'a, K, V> {
976 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
977 type Item = (&'a K, &'a mut V);
979 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
980 if self.front == self.back {
983 unsafe { Some (self.next_unchecked()) }
988 impl<'a, K, V> RangeMut<'a, K, V> {
989 unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
990 let handle = ptr::read(&self.front);
992 let mut cur_handle = match handle.right_kv() {
994 let (k, v) = ptr::read(&kv).into_kv_mut();
995 self.front = kv.right_edge();
999 let next_level = last_edge.into_node().ascend().ok();
1000 unwrap_unchecked(next_level)
1005 match cur_handle.right_kv() {
1007 let (k, v) = ptr::read(&kv).into_kv_mut();
1008 self.front = first_leaf_edge(kv.right_edge().descend());
1012 let next_level = last_edge.into_node().ascend().ok();
1013 cur_handle = unwrap_unchecked(next_level);
1020 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1021 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1022 if self.front == self.back {
1025 unsafe { Some(self.next_back_unchecked()) }
1030 impl<'a, K, V> RangeMut<'a, K, V> {
1031 unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
1032 let handle = ptr::read(&self.back);
1034 let mut cur_handle = match handle.left_kv() {
1036 let (k, v) = ptr::read(&kv).into_kv_mut();
1037 self.back = kv.left_edge();
1041 let next_level = last_edge.into_node().ascend().ok();
1042 unwrap_unchecked(next_level)
1047 match cur_handle.left_kv() {
1049 let (k, v) = ptr::read(&kv).into_kv_mut();
1050 self.back = last_leaf_edge(kv.left_edge().descend());
1054 let next_level = last_edge.into_node().ascend().ok();
1055 cur_handle = unwrap_unchecked(next_level);
1062 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1063 fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
1064 let mut map = BTreeMap::new();
1070 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1072 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1073 for (k, v) in iter {
1079 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1080 fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
1081 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1085 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1086 fn hash<H: Hasher>(&self, state: &mut H) {
1093 impl<K: Ord, V> Default for BTreeMap<K, V> {
1094 fn default() -> BTreeMap<K, V> {
1099 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
1100 fn eq(&self, other: &BTreeMap<K, V>) -> bool {
1101 self.len() == other.len() &&
1102 self.iter().zip(other).all(|(a, b)| a == b)
1106 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
1108 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
1110 fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
1111 self.iter().partial_cmp(other.iter())
1115 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
1117 fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
1118 self.iter().cmp(other.iter())
1122 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
1123 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1124 f.debug_map().entries(self.iter()).finish()
1128 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
1129 where K: Borrow<Q>, Q: Ord
1134 fn index(&self, key: &Q) -> &V {
1135 self.get(key).expect("no entry found for key")
1139 fn first_leaf_edge<BorrowType, K, V>(
1140 mut node: NodeRef<BorrowType,
1142 marker::LeafOrInternal>
1143 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1145 match node.force() {
1146 Leaf(leaf) => return leaf.first_edge(),
1147 Internal(internal) => {
1148 node = internal.first_edge().descend();
1154 fn last_leaf_edge<BorrowType, K, V>(
1155 mut node: NodeRef<BorrowType,
1157 marker::LeafOrInternal>
1158 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1160 match node.force() {
1161 Leaf(leaf) => return leaf.last_edge(),
1162 Internal(internal) => {
1163 node = internal.last_edge().descend();
1170 unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
1171 val.unwrap_or_else(|| {
1172 if cfg!(debug_assertions) {
1173 panic!("'unchecked' unwrap on None in BTreeMap");
1175 intrinsics::unreachable();
1180 impl<K, V> BTreeMap<K, V> {
1181 /// Gets an iterator over the entries of the map.
1186 /// use std::collections::BTreeMap;
1188 /// let mut map = BTreeMap::new();
1189 /// map.insert(1, "a");
1190 /// map.insert(2, "b");
1191 /// map.insert(3, "c");
1193 /// for (key, value) in map.iter() {
1194 /// println!("{}: {}", key, value);
1197 /// let (first_key, first_value) = map.iter().next().unwrap();
1198 /// assert_eq!((*first_key, *first_value), (1, "a"));
1200 #[stable(feature = "rust1", since = "1.0.0")]
1201 pub fn iter(&self) -> Iter<K, V> {
1204 front: first_leaf_edge(self.root.as_ref()),
1205 back: last_leaf_edge(self.root.as_ref())
1211 /// Gets a mutable iterator over the entries of the map.
1216 /// use std::collections::BTreeMap;
1218 /// let mut map = BTreeMap::new();
1219 /// map.insert("a", 1);
1220 /// map.insert("b", 2);
1221 /// map.insert("c", 3);
1223 /// // add 10 to the value if the key isn't "a"
1224 /// for (key, value) in map.iter_mut() {
1225 /// if key != &"a" {
1230 #[stable(feature = "rust1", since = "1.0.0")]
1231 pub fn iter_mut(&mut self) -> IterMut<K, V> {
1232 let root1 = self.root.as_mut();
1233 let root2 = unsafe { ptr::read(&root1) };
1236 front: first_leaf_edge(root1),
1237 back: last_leaf_edge(root2),
1243 /// Gets an iterator over the keys of the map.
1248 /// use std::collections::BTreeMap;
1250 /// let mut a = BTreeMap::new();
1251 /// a.insert(1, "a");
1252 /// a.insert(2, "b");
1254 /// let keys: Vec<_> = a.keys().cloned().collect();
1255 /// assert_eq!(keys, [1, 2]);
1257 #[stable(feature = "rust1", since = "1.0.0")]
1258 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1259 Keys { inner: self.iter() }
1262 /// Gets an iterator over the values of the map.
1267 /// use std::collections::BTreeMap;
1269 /// let mut a = BTreeMap::new();
1270 /// a.insert(1, "a");
1271 /// a.insert(2, "b");
1273 /// let values: Vec<&str> = a.values().cloned().collect();
1274 /// assert_eq!(values, ["a", "b"]);
1276 #[stable(feature = "rust1", since = "1.0.0")]
1277 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1278 Values { inner: self.iter() }
1281 /// Returns the number of elements in the map.
1286 /// use std::collections::BTreeMap;
1288 /// let mut a = BTreeMap::new();
1289 /// assert_eq!(a.len(), 0);
1290 /// a.insert(1, "a");
1291 /// assert_eq!(a.len(), 1);
1293 #[stable(feature = "rust1", since = "1.0.0")]
1294 pub fn len(&self) -> usize {
1298 /// Returns true if the map contains no elements.
1303 /// use std::collections::BTreeMap;
1305 /// let mut a = BTreeMap::new();
1306 /// assert!(a.is_empty());
1307 /// a.insert(1, "a");
1308 /// assert!(!a.is_empty());
1310 #[stable(feature = "rust1", since = "1.0.0")]
1311 pub fn is_empty(&self) -> bool {
1316 impl<'a, K: Ord, V> Entry<'a, K, V> {
1317 /// Ensures a value is in the entry by inserting the default if empty, and returns
1318 /// a mutable reference to the value in the entry.
1319 #[stable(feature = "rust1", since = "1.0.0")]
1320 pub fn or_insert(self, default: V) -> &'a mut V {
1322 Occupied(entry) => entry.into_mut(),
1323 Vacant(entry) => entry.insert(default),
1327 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1328 /// and returns a mutable reference to the value in the entry.
1329 #[stable(feature = "rust1", since = "1.0.0")]
1330 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1332 Occupied(entry) => entry.into_mut(),
1333 Vacant(entry) => entry.insert(default()),
1338 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1339 /// Sets the value of the entry with the VacantEntry's key,
1340 /// and returns a mutable reference to it.
1341 #[stable(feature = "rust1", since = "1.0.0")]
1342 pub fn insert(self, value: V) -> &'a mut V {
1351 let mut cur_parent = match self.handle.insert(self.key, value) {
1352 (Fit(handle), _) => return handle.into_kv_mut().1,
1353 (Split(left, k, v, right), ptr) => {
1358 left.ascend().map_err(|n| n.into_root_mut())
1364 Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
1365 Fit(_) => return unsafe { &mut *out_ptr },
1366 Split(left, k, v, right) => {
1370 cur_parent = left.ascend().map_err(|n| n.into_root_mut());
1374 root.push_level().push(ins_k, ins_v, ins_edge);
1375 return unsafe { &mut *out_ptr };
1382 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1383 /// Gets a reference to the value in the entry.
1384 #[stable(feature = "rust1", since = "1.0.0")]
1385 pub fn get(&self) -> &V {
1386 self.handle.reborrow().into_kv().1
1389 /// Gets a mutable reference to the value in the entry.
1390 #[stable(feature = "rust1", since = "1.0.0")]
1391 pub fn get_mut(&mut self) -> &mut V {
1392 self.handle.kv_mut().1
1395 /// Converts the entry into a mutable reference to its value.
1396 #[stable(feature = "rust1", since = "1.0.0")]
1397 pub fn into_mut(self) -> &'a mut V {
1398 self.handle.into_kv_mut().1
1401 /// Sets the value of the entry with the OccupiedEntry's key,
1402 /// and returns the entry's old value.
1403 #[stable(feature = "rust1", since = "1.0.0")]
1404 pub fn insert(&mut self, value: V) -> V {
1405 mem::replace(self.get_mut(), value)
1408 /// Takes the value of the entry out of the map, and returns it.
1409 #[stable(feature = "rust1", since = "1.0.0")]
1410 pub fn remove(self) -> V {
1414 fn remove_kv(self) -> (K, V) {
1417 let (small_leaf, old_key, old_val) = match self.handle.force() {
1419 let (hole, old_key, old_val) = leaf.remove();
1420 (hole.into_node(), old_key, old_val)
1422 Internal(mut internal) => {
1423 let key_loc = internal.kv_mut().0 as *mut K;
1424 let val_loc = internal.kv_mut().1 as *mut V;
1426 let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
1427 let to_remove = unsafe { unwrap_unchecked(to_remove) };
1429 let (hole, key, val) = to_remove.remove();
1431 let old_key = unsafe {
1432 mem::replace(&mut *key_loc, key)
1434 let old_val = unsafe {
1435 mem::replace(&mut *val_loc, val)
1438 (hole.into_node(), old_key, old_val)
1443 let mut cur_node = small_leaf.forget_type();
1444 while cur_node.len() < node::CAPACITY / 2 {
1445 match handle_underfull_node(cur_node) {
1447 EmptyParent(_) => unreachable!(),
1448 Merged(parent) => if parent.len() == 0 {
1449 // We must be at the root
1450 parent.into_root_mut().pop_level();
1453 cur_node = parent.forget_type();
1463 enum UnderflowResult<'a, K, V> {
1465 EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1466 Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1467 Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
1470 fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
1472 marker::LeafOrInternal>)
1473 -> UnderflowResult<'a, K, V> {
1474 let parent = if let Ok(parent) = node.ascend() {
1480 let (is_left, mut handle) = match parent.left_kv() {
1481 Ok(left) => (true, left),
1482 Err(parent) => match parent.right_kv() {
1483 Ok(right) => (false, right),
1485 return EmptyParent(parent.into_node());
1490 if handle.can_merge() {
1491 return Merged(handle.merge().into_node());
1494 let (k, v, edge) = if is_left {
1495 handle.reborrow_mut().left_edge().descend().pop()
1497 handle.reborrow_mut().right_edge().descend().pop_front()
1500 let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
1501 let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
1503 // FIXME: reuse cur_node?
1505 match handle.reborrow_mut().right_edge().descend().force() {
1506 Leaf(mut leaf) => leaf.push_front(k, v),
1507 Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
1510 match handle.reborrow_mut().left_edge().descend().force() {
1511 Leaf(mut leaf) => leaf.push(k, v),
1512 Internal(mut internal) => internal.push(k, v, edge.unwrap())
1517 return Stole(handle.into_node());