1 // Copyright 2014 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 // This implementation is largely based on the high-level description and analysis of B-Trees
12 // found in *Open Data Structures* (ODS). Although our implementation does not use any of
13 // the source found in ODS, if one wishes to review the high-level design of this structure, it
14 // can be freely downloaded at http://opendatastructures.org/. Its contents are as of this
15 // writing (August 2014) freely licensed under the following Creative Commons Attribution
16 // License: [CC BY 2.5 CA](http://creativecommons.org/licenses/by/2.5/ca/).
18 pub use self::Entry::*;
22 use core::borrow::BorrowFrom;
23 use core::cmp::Ordering;
24 use core::default::Default;
26 use core::hash::{Hash, Hasher};
28 use core::hash::Writer;
29 use core::iter::{Map, FromIterator};
30 use core::ops::{Index, IndexMut};
31 use core::{iter, fmt, mem};
33 use ring_buf::RingBuf;
35 use self::Continuation::{Continue, Finished};
37 use super::node::ForceResult::{Leaf, Internal};
38 use super::node::TraversalItem::{self, Elem, Edge};
39 use super::node::{Traversal, MutTraversal, MoveTraversal};
40 use super::node::{self, Node, Found, GoDown};
42 // FIXME(conventions): implement bounded iterators
44 /// A map based on a B-Tree.
46 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
47 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
48 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
49 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
50 /// is done is *very* inefficient for modern computer architectures. In particular, every element
51 /// is stored in its own individually heap-allocated node. This means that every single insertion
52 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
53 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
56 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
57 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
58 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
59 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
60 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
61 /// the node using binary search. As a compromise, one could also perform a linear search
62 /// that initially only checks every i<sup>th</sup> element for some choice of i.
64 /// Currently, our implementation simply performs naive linear search. This provides excellent
65 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
66 /// would like to further explore choosing the optimal search strategy based on the choice of B,
67 /// and possibly other factors. Using linear search, searching for a random element is expected
68 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
69 /// however, performance is excellent. `BTreeMap` is able to readily outperform `TreeMap` under
70 /// many workloads, and is competitive where it doesn't. BTreeMap also generally *scales* better
71 /// than TreeMap, making it more appropriate for large datasets.
73 /// However, `TreeMap` may still be more appropriate to use in many contexts. If elements are very
74 /// large or expensive to compare, `TreeMap` may be more appropriate. It won't allocate any
75 /// more space than is needed, and will perform the minimal number of comparisons necessary.
76 /// `TreeMap` also provides much better performance stability guarantees. Generally, very few
77 /// changes need to be made to update a BST, and two updates are expected to take about the same
78 /// amount of time on roughly equal sized BSTs. However a B-Tree's performance is much more
79 /// amortized. If a node is overfull, it must be split into two nodes. If a node is underfull, it
80 /// may be merged with another. Both of these operations are relatively expensive to perform, and
81 /// it's possible to force one to occur at every single level of the tree in a single insertion or
82 /// deletion. In fact, a malicious or otherwise unlucky sequence of insertions and deletions can
83 /// force this degenerate behaviour to occur on every operation. While the total amount of work
84 /// done on each operation isn't *catastrophic*, and *is* still bounded by O(B log<sub>B</sub>n),
85 /// it is certainly much slower when it does.
88 pub struct BTreeMap<K, V> {
95 /// An abstract base over-which all other BTree iterators are built.
103 /// An iterator over a BTreeMap's entries.
105 pub struct Iter<'a, K: 'a, V: 'a> {
106 inner: AbsIter<Traversal<'a, K, V>>
109 /// A mutable iterator over a BTreeMap's entries.
111 pub struct IterMut<'a, K: 'a, V: 'a> {
112 inner: AbsIter<MutTraversal<'a, K, V>>
115 /// An owning iterator over a BTreeMap's entries.
117 pub struct IntoIter<K, V> {
118 inner: AbsIter<MoveTraversal<K, V>>
121 /// An iterator over a BTreeMap's keys.
123 pub struct Keys<'a, K: 'a, V: 'a> {
124 inner: Map<(&'a K, &'a V), &'a K, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
127 /// An iterator over a BTreeMap's values.
129 pub struct Values<'a, K: 'a, V: 'a> {
130 inner: Map<(&'a K, &'a V), &'a V, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
133 /// A view into a single entry in a map, which may either be vacant or occupied.
134 #[unstable = "precise API still under development"]
135 pub enum Entry<'a, K:'a, V:'a> {
137 Vacant(VacantEntry<'a, K, V>),
138 /// An occupied Entry
139 Occupied(OccupiedEntry<'a, K, V>),
143 #[unstable = "precise API still under development"]
144 pub struct VacantEntry<'a, K:'a, V:'a> {
146 stack: stack::SearchStack<'a, K, V, node::handle::Edge, node::handle::Leaf>,
149 /// An occupied Entry.
150 #[unstable = "precise API still under development"]
151 pub struct OccupiedEntry<'a, K:'a, V:'a> {
152 stack: stack::SearchStack<'a, K, V, node::handle::KV, node::handle::LeafOrInternal>,
155 impl<K: Ord, V> BTreeMap<K, V> {
156 /// Makes a new empty BTreeMap with a reasonable choice for B.
158 pub fn new() -> BTreeMap<K, V> {
159 //FIXME(Gankro): Tune this as a function of size_of<K/V>?
163 /// Makes a new empty BTreeMap with the given B.
165 /// B cannot be less than 2.
166 pub fn with_b(b: uint) -> BTreeMap<K, V> {
167 assert!(b > 1, "B must be greater than 1");
171 root: Node::make_leaf_root(b),
176 /// Clears the map, removing all values.
181 /// use std::collections::BTreeMap;
183 /// let mut a = BTreeMap::new();
184 /// a.insert(1u, "a");
186 /// assert!(a.is_empty());
189 pub fn clear(&mut self) {
191 // avoid recursive destructors by manually traversing the tree
192 for _ in mem::replace(self, BTreeMap::with_b(b)).into_iter() {};
195 // Searching in a B-Tree is pretty straightforward.
197 // Start at the root. Try to find the key in the current node. If we find it, return it.
198 // If it's not in there, follow the edge *before* the smallest key larger than
199 // the search key. If no such key exists (they're *all* smaller), then just take the last
200 // edge in the node. If we're in a leaf and we don't find our key, then it's not
203 /// Returns a reference to the value corresponding to the key.
205 /// The key may be any borrowed form of the map's key type, but the ordering
206 /// on the borrowed form *must* match the ordering on the key type.
211 /// use std::collections::BTreeMap;
213 /// let mut map = BTreeMap::new();
214 /// map.insert(1u, "a");
215 /// assert_eq!(map.get(&1), Some(&"a"));
216 /// assert_eq!(map.get(&2), None);
219 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where Q: BorrowFrom<K> + Ord {
220 let mut cur_node = &self.root;
222 match Node::search(cur_node, key) {
223 Found(handle) => return Some(handle.into_kv().1),
224 GoDown(handle) => match handle.force() {
225 Leaf(_) => return None,
226 Internal(internal_handle) => {
227 cur_node = internal_handle.into_edge();
235 /// Returns true if the map contains a value for the specified key.
237 /// The key may be any borrowed form of the map's key type, but the ordering
238 /// on the borrowed form *must* match the ordering on the key type.
243 /// use std::collections::BTreeMap;
245 /// let mut map = BTreeMap::new();
246 /// map.insert(1u, "a");
247 /// assert_eq!(map.contains_key(&1), true);
248 /// assert_eq!(map.contains_key(&2), false);
251 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where Q: BorrowFrom<K> + Ord {
252 self.get(key).is_some()
255 /// Returns a mutable reference to the value corresponding to the key.
257 /// The key may be any borrowed form of the map's key type, but the ordering
258 /// on the borrowed form *must* match the ordering on the key type.
263 /// use std::collections::BTreeMap;
265 /// let mut map = BTreeMap::new();
266 /// map.insert(1u, "a");
267 /// match map.get_mut(&1) {
268 /// Some(x) => *x = "b",
271 /// assert_eq!(map[1], "b");
273 // See `get` for implementation notes, this is basically a copy-paste with mut's added
275 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where Q: BorrowFrom<K> + Ord {
276 // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
277 let mut temp_node = &mut self.root;
279 let cur_node = temp_node;
280 match Node::search(cur_node, key) {
281 Found(handle) => return Some(handle.into_kv_mut().1),
282 GoDown(handle) => match handle.force() {
283 Leaf(_) => return None,
284 Internal(internal_handle) => {
285 temp_node = internal_handle.into_edge_mut();
293 // Insertion in a B-Tree is a bit complicated.
295 // First we do the same kind of search described in `find`. But we need to maintain a stack of
296 // all the nodes/edges in our search path. If we find a match for the key we're trying to
297 // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,
298 // we attempt to insert our key-value pair at the same location we would want to follow another
301 // If the node has room, then this is done in the obvious way by shifting elements. However,
302 // if the node itself is full, we split node into two, and give its median key-value
303 // pair to its parent to insert the new node with. Of course, the parent may also be
304 // full, and insertion can propagate until we reach the root. If we reach the root, and
305 // it is *also* full, then we split the root and place the two nodes under a newly made root.
307 // Note that we subtly deviate from Open Data Structures in our implementation of split.
308 // ODS describes inserting into the node *regardless* of its capacity, and then
309 // splitting *afterwards* if it happens to be overfull. However, this is inefficient.
310 // Instead, we split beforehand, and then insert the key-value pair into the appropriate
311 // result node. This has two consequences:
313 // 1) While ODS produces a left node of size B-1, and a right node of size B,
314 // we may potentially reverse this. However, this shouldn't effect the analysis.
316 // 2) While ODS may potentially return the pair we *just* inserted after
317 // the split, we will never do this. Again, this shouldn't effect the analysis.
319 /// Inserts a key-value pair from the map. If the key already had a value
320 /// present in the map, that value is returned. Otherwise, `None` is returned.
325 /// use std::collections::BTreeMap;
327 /// let mut map = BTreeMap::new();
328 /// assert_eq!(map.insert(37u, "a"), None);
329 /// assert_eq!(map.is_empty(), false);
331 /// map.insert(37, "b");
332 /// assert_eq!(map.insert(37, "c"), Some("b"));
333 /// assert_eq!(map[37], "c");
336 pub fn insert(&mut self, mut key: K, mut value: V) -> Option<V> {
337 // This is a stack of rawptrs to nodes paired with indices, respectively
338 // representing the nodes and edges of our search path. We have to store rawptrs
339 // because as far as Rust is concerned, we can mutate aliased data with such a
340 // stack. It is of course correct, but what it doesn't know is that we will only
341 // be popping and using these ptrs one at a time in child-to-parent order. The alternative
342 // to doing this is to take the Nodes from their parents. This actually makes
343 // borrowck *really* happy and everything is pretty smooth. However, this creates
344 // *tons* of pointless writes, and requires us to always walk all the way back to
345 // the root after an insertion, even if we only needed to change a leaf. Therefore,
346 // we accept this potential unsafety and complexity in the name of performance.
348 // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap
349 // by the stack module. All it can do is immutably read nodes, and ask the search stack
350 // to proceed down some edge by index. This makes the search logic we'll be reusing in a
351 // few different methods much neater, and of course drastically improves safety.
352 let mut stack = stack::PartialSearchStack::new(self);
355 let result = stack.with(move |pusher, node| {
356 // Same basic logic as found in `find`, but with PartialSearchStack mediating the
357 // actual nodes for us
358 return match Node::search(node, &key) {
359 Found(mut handle) => {
360 // Perfect match, swap the values and return the old one
361 mem::swap(handle.val_mut(), &mut value);
362 Finished(Some(value))
365 // We need to keep searching, try to get the search stack
366 // to go down further
367 match handle.force() {
368 Leaf(leaf_handle) => {
369 // We've reached a leaf, perform the insertion here
370 pusher.seal(leaf_handle).insert(key, value);
373 Internal(internal_handle) => {
374 // We've found the subtree to insert this key/value pair in,
376 Continue((pusher.push(internal_handle), key, value))
383 Finished(ret) => { return ret; },
384 Continue((new_stack, renewed_key, renewed_val)) => {
393 // Deletion is the most complicated operation for a B-Tree.
395 // First we do the same kind of search described in
396 // `find`. But we need to maintain a stack of all the nodes/edges in our search path.
397 // If we don't find the key, then we just return `None` and do nothing. If we do find the
398 // key, we perform two operations: remove the item, and then possibly handle underflow.
400 // # removing the item
401 // If the node is a leaf, we just remove the item, and shift
402 // any items after it back to fill the hole.
404 // If the node is an internal node, we *swap* the item with the smallest item in
405 // in its right subtree (which must reside in a leaf), and then revert to the leaf
408 // # handling underflow
409 // After removing an item, there may be too few items in the node. We want nodes
410 // to be mostly full for efficiency, although we make an exception for the root, which
411 // may have as few as one item. If this is the case, we may first try to steal
412 // an item from our left or right neighbour.
414 // To steal from the left (right) neighbour,
415 // we take the largest (smallest) item and child from it. We then swap the taken item
416 // with the item in their mutual parent that separates them, and then insert the
417 // parent's item and the taken child into the first (last) index of the underflowed node.
419 // However, stealing has the possibility of underflowing our neighbour. If this is the
420 // case, we instead *merge* with our neighbour. This of course reduces the number of
421 // children in the parent. Therefore, we also steal the item that separates the now
422 // merged nodes, and insert it into the merged node.
424 // Merging may cause the parent to underflow. If this is the case, then we must repeat
425 // the underflow handling process on the parent. If merging merges the last two children
426 // of the root, then we replace the root with the merged node.
428 /// Removes a key from the map, returning the value at the key if the key
429 /// was previously in the map.
431 /// The key may be any borrowed form of the map's key type, but the ordering
432 /// on the borrowed form *must* match the ordering on the key type.
437 /// use std::collections::BTreeMap;
439 /// let mut map = BTreeMap::new();
440 /// map.insert(1u, "a");
441 /// assert_eq!(map.remove(&1), Some("a"));
442 /// assert_eq!(map.remove(&1), None);
445 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: BorrowFrom<K> + Ord {
446 // See `swap` for a more thorough description of the stuff going on in here
447 let mut stack = stack::PartialSearchStack::new(self);
449 let result = stack.with(move |pusher, node| {
450 return match Node::search(node, key) {
452 // Perfect match. Terminate the stack here, and remove the entry
453 Finished(Some(pusher.seal(handle).remove()))
456 // We need to keep searching, try to go down the next edge
457 match handle.force() {
458 // We're at a leaf; the key isn't in here
459 Leaf(_) => Finished(None),
460 Internal(internal_handle) => Continue(pusher.push(internal_handle))
466 Finished(ret) => return ret,
467 Continue(new_stack) => stack = new_stack
473 /// A helper enum useful for deciding whether to continue a loop since we can't
474 /// return from a closure
475 enum Continuation<A, B> {
480 /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
481 /// to nodes. By using this module much better safety guarantees can be made, and more search
482 /// boilerplate gets cut out.
484 use core::prelude::*;
487 use core::ops::{Deref, DerefMut};
489 use super::super::node::{self, Node, Fit, Split, Internal, Leaf};
490 use super::super::node::handle;
493 /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
494 /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
495 /// with the exact requested lifetime can be used. This is in contrast to normal references,
496 /// where `&'static` can be used in any function expecting any lifetime reference.
497 pub struct IdRef<'id, T: 'id> {
499 marker: marker::InvariantLifetime<'id>
502 impl<'id, T> Deref for IdRef<'id, T> {
505 fn deref(&self) -> &T {
510 impl<'id, T> DerefMut for IdRef<'id, T> {
511 fn deref_mut(&mut self) -> &mut T {
516 type StackItem<K, V> = node::Handle<*mut Node<K, V>, handle::Edge, handle::Internal>;
517 type Stack<K, V> = Vec<StackItem<K, V>>;
519 /// A `PartialSearchStack` handles the construction of a search stack.
520 pub struct PartialSearchStack<'a, K:'a, V:'a> {
521 map: &'a mut BTreeMap<K, V>,
523 next: *mut Node<K, V>,
526 /// A `SearchStack` represents a full path to an element or an edge of interest. It provides
527 /// methods depending on the type of what the path points to for removing an element, inserting
528 /// a new element, and manipulating to element at the top of the stack.
529 pub struct SearchStack<'a, K:'a, V:'a, Type, NodeType> {
530 map: &'a mut BTreeMap<K, V>,
532 top: node::Handle<*mut Node<K, V>, Type, NodeType>,
535 /// A `PartialSearchStack` that doesn't hold a a reference to the next node, and is just
536 /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with`
537 /// for more details.
538 pub struct Pusher<'id, 'a, K:'a, V:'a> {
539 map: &'a mut BTreeMap<K, V>,
541 marker: marker::InvariantLifetime<'id>
544 impl<'a, K, V> PartialSearchStack<'a, K, V> {
545 /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
546 /// root of the tree.
547 pub fn new(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {
548 let depth = map.depth;
551 next: &mut map.root as *mut _,
553 stack: Vec::with_capacity(depth),
557 /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure
558 /// to interact with, search, and finally push the `Node` onto the stack. The passed in
559 /// closure must be polymorphic on the `'id` lifetime parameter, as this statically
560 /// ensures that only `Handle`s from the correct `Node` can be pushed.
562 /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept
563 /// handles with the same `'id`. The closure could only get references with that lifetime
564 /// through its arguments or through some other `IdRef` that it has lying around. However,
565 /// no other `IdRef` could possibly work - because the `'id` is held in an invariant
566 /// parameter, it would need to have precisely the correct lifetime, which would mean that
567 /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a
568 /// specific lifetime instead of the one that `with` chooses to give it.
570 /// See also Haskell's `ST` monad, which uses a similar trick.
571 pub fn with<T, F: for<'id> FnOnce(Pusher<'id, 'a, K, V>,
572 IdRef<'id, Node<K, V>>) -> T>(self, closure: F) -> T {
573 let pusher = Pusher {
576 marker: marker::InvariantLifetime
579 inner: unsafe { &mut *self.next },
580 marker: marker::InvariantLifetime
583 closure(pusher, node)
587 impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> {
588 /// Pushes the requested child of the stack's current top on top of the stack. If the child
589 /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is
591 pub fn push(mut self, mut edge: node::Handle<IdRef<'id, Node<K, V>>,
594 -> PartialSearchStack<'a, K, V> {
595 self.stack.push(edge.as_raw());
599 next: edge.edge_mut() as *mut _,
603 /// Converts the PartialSearchStack into a SearchStack.
604 pub fn seal<Type, NodeType>
605 (self, mut handle: node::Handle<IdRef<'id, Node<K, V>>, Type, NodeType>)
606 -> SearchStack<'a, K, V, Type, NodeType> {
610 top: handle.as_raw(),
615 impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> {
616 /// Gets a reference to the value the stack points to.
617 pub fn peek(&self) -> &V {
618 unsafe { self.top.from_raw().into_kv().1 }
621 /// Gets a mutable reference to the value the stack points to.
622 pub fn peek_mut(&mut self) -> &mut V {
623 unsafe { self.top.from_raw_mut().into_kv_mut().1 }
626 /// Converts the stack into a mutable reference to the value it points to, with a lifetime
627 /// tied to the original tree.
628 pub fn into_top(mut self) -> &'a mut V {
630 mem::copy_mut_lifetime(
632 self.top.from_raw_mut().val_mut()
638 impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
639 /// Removes the key and value in the top element of the stack, then handles underflows as
640 /// described in BTree's pop function.
641 fn remove_leaf(mut self) -> V {
642 self.map.length -= 1;
644 // Remove the key-value pair from the leaf that this search stack points to.
645 // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
646 // to avoid ownership issues.
647 let (value, mut underflow) = unsafe {
648 let (_, value) = self.top.from_raw_mut().remove_as_leaf();
649 let underflow = self.top.from_raw().node().is_underfull();
654 match self.stack.pop() {
656 // We've reached the root, so no matter what, we're done. We manually
657 // access the root via the tree itself to avoid creating any dangling
659 if self.map.root.len() == 0 && !self.map.root.is_leaf() {
660 // We've emptied out the root, so make its only child the new root.
661 // If it's a leaf, we just let it become empty.
663 self.map.root.hoist_lone_child();
667 Some(mut handle) => {
669 // Underflow! Handle it!
671 handle.from_raw_mut().handle_underflow();
672 underflow = handle.from_raw().node().is_underfull();
684 impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> {
685 /// Removes the key and value in the top element of the stack, then handles underflows as
686 /// described in BTree's pop function.
687 pub fn remove(self) -> V {
688 // Ensure that the search stack goes to a leaf. This is necessary to perform deletion
689 // in a BTree. Note that this may put the tree in an inconsistent state (further
690 // described in into_leaf's comments), but this is immediately fixed by the
691 // removing the value we want to remove
692 self.into_leaf().remove_leaf()
695 /// Subroutine for removal. Takes a search stack for a key that might terminate at an
696 /// internal node, and mutates the tree and search stack to *make* it a search stack
697 /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
698 /// leaves the tree in an inconsistent state that must be repaired by the caller by
699 /// removing the entry in question. Specifically the key-value pair and its successor will
701 fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
703 let mut top_raw = self.top;
704 let mut top = top_raw.from_raw_mut();
706 let key_ptr = top.key_mut() as *mut _;
707 let val_ptr = top.val_mut() as *mut _;
709 // Try to go into the right subtree of the found key to find its successor
711 Leaf(mut leaf_handle) => {
712 // We're a proper leaf stack, nothing to do
716 top: leaf_handle.as_raw()
719 Internal(mut internal_handle) => {
720 let mut right_handle = internal_handle.right_edge();
722 //We're not a proper leaf stack, let's get to work.
723 self.stack.push(right_handle.as_raw());
725 let mut temp_node = right_handle.edge_mut();
727 // Walk into the smallest subtree of this node
728 let node = temp_node;
730 match node.kv_handle(0).force() {
731 Leaf(mut handle) => {
732 // This node is a leaf, do the swap and return
733 mem::swap(handle.key_mut(), &mut *key_ptr);
734 mem::swap(handle.val_mut(), &mut *val_ptr);
741 Internal(kv_handle) => {
742 // This node is internal, go deeper
743 let mut handle = kv_handle.into_left_edge();
744 self.stack.push(handle.as_raw());
745 temp_node = handle.into_edge_mut();
755 impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> {
756 /// Inserts the key and value into the top element in the stack, and if that node has to
757 /// split recursively inserts the split contents into the next element stack until
760 /// Assumes that the stack represents a search path from the root to a leaf.
762 /// An &mut V is returned to the inserted value, for callers that want a reference to this.
763 pub fn insert(mut self, key: K, val: V) -> &'a mut V {
765 self.map.length += 1;
767 // Insert the key and value into the leaf at the top of the stack
768 let (mut insertion, inserted_ptr) = self.top.from_raw_mut()
769 .insert_as_leaf(key, val);
774 // The last insertion went off without a hitch, no splits! We can stop
776 return &mut *inserted_ptr;
778 Split(key, val, right) => match self.stack.pop() {
779 // The last insertion triggered a split, so get the next element on the
780 // stack to recursively insert the split node into.
782 // The stack was empty; we've split the root, and need to make a
783 // a new one. This is done in-place because we can't move the
784 // root out of a reference to the tree.
785 Node::make_internal_root(&mut self.map.root, self.map.b,
789 return &mut *inserted_ptr;
791 Some(mut handle) => {
792 // The stack wasn't empty, do the insertion and recurse
793 insertion = handle.from_raw_mut()
794 .insert_as_internal(key, val, right);
806 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
807 fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
808 let mut map = BTreeMap::new();
815 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
817 fn extend<T: Iterator<Item=(K, V)>>(&mut self, mut iter: T) {
826 impl<S: Writer, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> {
827 fn hash(&self, state: &mut S) {
828 for elt in self.iter() {
835 impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> {
836 fn hash(&self, state: &mut S) {
837 for elt in self.iter() {
844 impl<K: Ord, V> Default for BTreeMap<K, V> {
846 fn default() -> BTreeMap<K, V> {
852 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
853 fn eq(&self, other: &BTreeMap<K, V>) -> bool {
854 self.len() == other.len() &&
855 self.iter().zip(other.iter()).all(|(a, b)| a == b)
860 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
863 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
865 fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
866 iter::order::partial_cmp(self.iter(), other.iter())
871 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
873 fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
874 iter::order::cmp(self.iter(), other.iter())
879 impl<K: Show, V: Show> Show for BTreeMap<K, V> {
880 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
881 try!(write!(f, "BTreeMap {{"));
883 for (i, (k, v)) in self.iter().enumerate() {
884 if i != 0 { try!(write!(f, ", ")); }
885 try!(write!(f, "{:?}: {:?}", *k, *v));
893 impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V>
894 where Q: BorrowFrom<K> + Ord
898 fn index(&self, key: &Q) -> &V {
899 self.get(key).expect("no entry found for key")
904 impl<K: Ord, Q: ?Sized, V> IndexMut<Q> for BTreeMap<K, V>
905 where Q: BorrowFrom<K> + Ord
909 fn index_mut(&mut self, key: &Q) -> &mut V {
910 self.get_mut(key).expect("no entry found for key")
914 /// Genericises over how to get the correct type of iterator from the correct type
915 /// of Node ownership.
917 fn traverse(node: N) -> Self;
920 impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> {
921 fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> {
926 impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> {
927 fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> {
932 impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> {
933 fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> {
938 /// Represents an operation to perform inside the following iterator methods.
939 /// This is necessary to use in `next` because we want to modify self.left inside
940 /// a match that borrows it. Similarly, in `next_back` for self.right. Instead, we use this
941 /// enum to note what we want to do, and do it after the match.
947 impl<K, V, E, T> Iterator for AbsIter<T> where
948 T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>,
952 // This function is pretty long, but only because there's a lot of cases to consider.
953 // Our iterator represents two search paths, left and right, to the smallest and largest
954 // elements we have yet to yield. lca represents the least common ancestor of these two paths,
955 // above-which we never walk, since everything outside it has already been consumed (or was
956 // never in the range to iterate).
958 // Note that the design of these iterators permits an *arbitrary* initial pair of min and max,
959 // making these arbitrary sub-range iterators. However the logic to construct these paths
960 // efficiently is fairly involved, so this is a FIXME. The sub-range iterators also wouldn't be
961 // able to accurately predict size, so those iterators can't implement ExactSizeIterator.
962 fn next(&mut self) -> Option<(K, V)> {
964 // We want the smallest element, so try to get the top of the left stack
965 let op = match self.left.back_mut() {
966 // The left stack is empty, so try to get the next element of the two paths
967 // LCAs (the left search path is currently a subpath of the right one)
968 None => match self.lca.next() {
969 // The lca has been exhausted, walk further down the right path
970 None => match self.right.pop_front() {
971 // The right path is exhausted, so we're done
973 // The right path had something, make that the new LCA
974 // and restart the whole process
980 // The lca yielded an edge, make that the new head of the left path
981 Some(Edge(next)) => Push(Traverse::traverse(next)),
982 // The lca yielded an entry, so yield that
983 Some(Elem(k, v)) => {
988 // The left stack wasn't empty, so continue along the node in its head
989 Some(iter) => match iter.next() {
990 // The head of the left path is empty, so Pop it off and restart the process
992 // The head of the left path yielded an edge, so make that the new head
994 Some(Edge(next)) => Push(Traverse::traverse(next)),
995 // The head of the left path yielded entry, so yield that
996 Some(Elem(k, v)) => {
1003 // Handle any operation on the left stack as necessary
1005 Push(item) => { self.left.push_back(item); },
1006 Pop => { self.left.pop_back(); },
1011 fn size_hint(&self) -> (uint, Option<uint>) {
1012 (self.size, Some(self.size))
1016 impl<K, V, E, T> DoubleEndedIterator for AbsIter<T> where
1017 T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>,
1019 // next_back is totally symmetric to next
1020 fn next_back(&mut self) -> Option<(K, V)> {
1022 let op = match self.right.back_mut() {
1023 None => match self.lca.next_back() {
1024 None => match self.left.pop_front() {
1025 None => return None,
1031 Some(Edge(next)) => Push(Traverse::traverse(next)),
1032 Some(Elem(k, v)) => {
1037 Some(iter) => match iter.next_back() {
1039 Some(Edge(next)) => Push(Traverse::traverse(next)),
1040 Some(Elem(k, v)) => {
1048 Push(item) => { self.right.push_back(item); },
1049 Pop => { self.right.pop_back(); }
1056 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1057 type Item = (&'a K, &'a V);
1059 fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1060 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1063 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
1064 fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() }
1067 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
1070 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1071 type Item = (&'a K, &'a mut V);
1073 fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1074 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1077 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1078 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() }
1081 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
1084 impl<K, V> Iterator for IntoIter<K, V> {
1087 fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1088 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1091 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1092 fn next_back(&mut self) -> Option<(K, V)> { self.inner.next_back() }
1095 impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
1098 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1101 fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1102 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1105 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1106 fn next_back(&mut self) -> Option<(&'a K)> { self.inner.next_back() }
1109 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
1113 impl<'a, K, V> Iterator for Values<'a, K, V> {
1116 fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1117 fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1120 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1121 fn next_back(&mut self) -> Option<(&'a V)> { self.inner.next_back() }
1124 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
1126 impl<'a, K: Ord, V> Entry<'a, K, V> {
1127 #[unstable = "matches collection reform v2 specification, waiting for dust to settle"]
1128 /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
1129 pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, K, V>> {
1131 Occupied(entry) => Ok(entry.into_mut()),
1132 Vacant(entry) => Err(entry),
1137 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1138 /// Sets the value of the entry with the VacantEntry's key,
1139 /// and returns a mutable reference to it.
1140 #[unstable = "matches collection reform v2 specification, waiting for dust to settle"]
1141 pub fn insert(self, value: V) -> &'a mut V {
1142 self.stack.insert(self.key, value)
1146 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1147 /// Gets a reference to the value in the entry.
1148 #[unstable = "matches collection reform v2 specification, waiting for dust to settle"]
1149 pub fn get(&self) -> &V {
1153 /// Gets a mutable reference to the value in the entry.
1154 #[unstable = "matches collection reform v2 specification, waiting for dust to settle"]
1155 pub fn get_mut(&mut self) -> &mut V {
1156 self.stack.peek_mut()
1159 /// Converts the entry into a mutable reference to its value.
1160 #[unstable = "matches collection reform v2 specification, waiting for dust to settle"]
1161 pub fn into_mut(self) -> &'a mut V {
1162 self.stack.into_top()
1165 /// Sets the value of the entry with the OccupiedEntry's key,
1166 /// and returns the entry's old value.
1167 #[unstable = "matches collection reform v2 specification, waiting for dust to settle"]
1168 pub fn insert(&mut self, mut value: V) -> V {
1169 mem::swap(self.stack.peek_mut(), &mut value);
1173 /// Takes the value of the entry out of the map, and returns it.
1174 #[unstable = "matches collection reform v2 specification, waiting for dust to settle"]
1175 pub fn remove(self) -> V {
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(1u, "a");
1190 /// map.insert(2u, "b");
1191 /// map.insert(3u, "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), (1u, "a"));
1201 pub fn iter(&self) -> Iter<K, V> {
1202 let len = self.len();
1205 lca: Traverse::traverse(&self.root),
1206 left: RingBuf::new(),
1207 right: RingBuf::new(),
1213 /// Gets a mutable iterator over the entries of the map.
1218 /// use std::collections::BTreeMap;
1220 /// let mut map = BTreeMap::new();
1221 /// map.insert("a", 1u);
1222 /// map.insert("b", 2u);
1223 /// map.insert("c", 3u);
1225 /// // add 10 to the value if the key isn't "a"
1226 /// for (key, value) in map.iter_mut() {
1227 /// if key != &"a" {
1233 pub fn iter_mut(&mut self) -> IterMut<K, V> {
1234 let len = self.len();
1237 lca: Traverse::traverse(&mut self.root),
1238 left: RingBuf::new(),
1239 right: RingBuf::new(),
1245 /// Gets an owning iterator over the entries of the map.
1250 /// use std::collections::BTreeMap;
1252 /// let mut map = BTreeMap::new();
1253 /// map.insert(1u, "a");
1254 /// map.insert(2u, "b");
1255 /// map.insert(3u, "c");
1257 /// for (key, value) in map.into_iter() {
1258 /// println!("{}: {}", key, value);
1262 pub fn into_iter(self) -> IntoIter<K, V> {
1263 let len = self.len();
1266 lca: Traverse::traverse(self.root),
1267 left: RingBuf::new(),
1268 right: RingBuf::new(),
1274 /// Gets an iterator over the keys of the map.
1279 /// use std::collections::BTreeMap;
1281 /// let mut a = BTreeMap::new();
1282 /// a.insert(1u, "a");
1283 /// a.insert(2u, "b");
1285 /// let keys: Vec<uint> = a.keys().cloned().collect();
1286 /// assert_eq!(keys, vec![1u,2,]);
1289 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1290 fn first<A, B>((a, _): (A, B)) -> A { a }
1291 let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer
1293 Keys { inner: self.iter().map(first) }
1296 /// Gets an iterator over the values of the map.
1301 /// use std::collections::BTreeMap;
1303 /// let mut a = BTreeMap::new();
1304 /// a.insert(1u, "a");
1305 /// a.insert(2u, "b");
1307 /// let values: Vec<&str> = a.values().cloned().collect();
1308 /// assert_eq!(values, vec!["a","b"]);
1311 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1312 fn second<A, B>((_, b): (A, B)) -> B { b }
1313 let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer
1315 Values { inner: self.iter().map(second) }
1318 /// Return the number of elements in the map.
1323 /// use std::collections::BTreeMap;
1325 /// let mut a = BTreeMap::new();
1326 /// assert_eq!(a.len(), 0);
1327 /// a.insert(1u, "a");
1328 /// assert_eq!(a.len(), 1);
1331 pub fn len(&self) -> uint { self.length }
1333 /// Return true if the map contains no elements.
1338 /// use std::collections::BTreeMap;
1340 /// let mut a = BTreeMap::new();
1341 /// assert!(a.is_empty());
1342 /// a.insert(1u, "a");
1343 /// assert!(!a.is_empty());
1346 pub fn is_empty(&self) -> bool { self.len() == 0 }
1349 impl<K: Ord, V> BTreeMap<K, V> {
1350 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1355 /// use std::collections::BTreeMap;
1356 /// use std::collections::btree_map::Entry;
1358 /// let mut count: BTreeMap<&str, uint> = BTreeMap::new();
1360 /// // count the number of occurrences of letters in the vec
1361 /// for x in vec!["a","b","a","c","a","b"].iter() {
1362 /// match count.entry(*x) {
1363 /// Entry::Vacant(view) => {
1366 /// Entry::Occupied(mut view) => {
1367 /// let v = view.get_mut();
1373 /// assert_eq!(count["a"], 3u);
1375 /// The key must have the same ordering before or after `.to_owned()` is called.
1376 #[unstable = "precise API still under development"]
1377 pub fn entry<'a>(&'a mut self, mut key: K) -> Entry<'a, K, V> {
1378 // same basic logic of `swap` and `pop`, blended together
1379 let mut stack = stack::PartialSearchStack::new(self);
1381 let result = stack.with(move |pusher, node| {
1382 return match Node::search(node, &key) {
1385 Finished(Occupied(OccupiedEntry {
1386 stack: pusher.seal(handle)
1390 match handle.force() {
1391 Leaf(leaf_handle) => {
1392 Finished(Vacant(VacantEntry {
1393 stack: pusher.seal(leaf_handle),
1397 Internal(internal_handle) => {
1399 pusher.push(internal_handle),
1408 Finished(finished) => return finished,
1409 Continue((new_stack, renewed_key)) => {
1426 use super::{BTreeMap, Occupied, Vacant};
1429 fn test_basic_large() {
1430 let mut map = BTreeMap::new();
1432 assert_eq!(map.len(), 0);
1434 for i in range(0, size) {
1435 assert_eq!(map.insert(i, 10*i), None);
1436 assert_eq!(map.len(), i + 1);
1439 for i in range(0, size) {
1440 assert_eq!(map.get(&i).unwrap(), &(i*10));
1443 for i in range(size, size*2) {
1444 assert_eq!(map.get(&i), None);
1447 for i in range(0, size) {
1448 assert_eq!(map.insert(i, 100*i), Some(10*i));
1449 assert_eq!(map.len(), size);
1452 for i in range(0, size) {
1453 assert_eq!(map.get(&i).unwrap(), &(i*100));
1456 for i in range(0, size/2) {
1457 assert_eq!(map.remove(&(i*2)), Some(i*200));
1458 assert_eq!(map.len(), size - i - 1);
1461 for i in range(0, size/2) {
1462 assert_eq!(map.get(&(2*i)), None);
1463 assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100));
1466 for i in range(0, size/2) {
1467 assert_eq!(map.remove(&(2*i)), None);
1468 assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
1469 assert_eq!(map.len(), size/2 - i - 1);
1474 fn test_basic_small() {
1475 let mut map = BTreeMap::new();
1476 assert_eq!(map.remove(&1), None);
1477 assert_eq!(map.get(&1), None);
1478 assert_eq!(map.insert(1u, 1u), None);
1479 assert_eq!(map.get(&1), Some(&1));
1480 assert_eq!(map.insert(1, 2), Some(1));
1481 assert_eq!(map.get(&1), Some(&2));
1482 assert_eq!(map.insert(2, 4), None);
1483 assert_eq!(map.get(&2), Some(&4));
1484 assert_eq!(map.remove(&1), Some(2));
1485 assert_eq!(map.remove(&2), Some(4));
1486 assert_eq!(map.remove(&1), None);
1494 let mut map: BTreeMap<uint, uint> = range(0, size).map(|i| (i, i)).collect();
1497 let mut iter = map.iter();
1498 for i in range(0, size) {
1499 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1500 assert_eq!(iter.next().unwrap(), (&i, &i));
1502 assert_eq!(iter.size_hint(), (0, Some(0)));
1503 assert_eq!(iter.next(), None);
1507 let mut iter = map.iter_mut();
1508 for i in range(0, size) {
1509 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1510 assert_eq!(iter.next().unwrap(), (&i, &mut (i + 0)));
1512 assert_eq!(iter.size_hint(), (0, Some(0)));
1513 assert_eq!(iter.next(), None);
1517 let mut iter = map.into_iter();
1518 for i in range(0, size) {
1519 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1520 assert_eq!(iter.next().unwrap(), (i, i));
1522 assert_eq!(iter.size_hint(), (0, Some(0)));
1523 assert_eq!(iter.next(), None);
1529 fn test_iter_rev() {
1533 let mut map: BTreeMap<uint, uint> = range(0, size).map(|i| (i, i)).collect();
1536 let mut iter = map.iter().rev();
1537 for i in range(0, size) {
1538 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1539 assert_eq!(iter.next().unwrap(), (&(size - i - 1), &(size - i - 1)));
1541 assert_eq!(iter.size_hint(), (0, Some(0)));
1542 assert_eq!(iter.next(), None);
1546 let mut iter = map.iter_mut().rev();
1547 for i in range(0, size) {
1548 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1549 assert_eq!(iter.next().unwrap(), (&(size - i - 1), &mut(size - i - 1)));
1551 assert_eq!(iter.size_hint(), (0, Some(0)));
1552 assert_eq!(iter.next(), None);
1556 let mut iter = map.into_iter().rev();
1557 for i in range(0, size) {
1558 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
1559 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
1561 assert_eq!(iter.size_hint(), (0, Some(0)));
1562 assert_eq!(iter.next(), None);
1569 let xs = [(1i, 10i), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1571 let mut map: BTreeMap<int, int> = xs.iter().map(|&x| x).collect();
1573 // Existing key (insert)
1574 match map.entry(1) {
1575 Vacant(_) => unreachable!(),
1576 Occupied(mut view) => {
1577 assert_eq!(view.get(), &10);
1578 assert_eq!(view.insert(100), 10);
1581 assert_eq!(map.get(&1).unwrap(), &100);
1582 assert_eq!(map.len(), 6);
1585 // Existing key (update)
1586 match map.entry(2) {
1587 Vacant(_) => unreachable!(),
1588 Occupied(mut view) => {
1589 let v = view.get_mut();
1593 assert_eq!(map.get(&2).unwrap(), &200);
1594 assert_eq!(map.len(), 6);
1596 // Existing key (take)
1597 match map.entry(3) {
1598 Vacant(_) => unreachable!(),
1600 assert_eq!(view.remove(), 30);
1603 assert_eq!(map.get(&3), None);
1604 assert_eq!(map.len(), 5);
1607 // Inexistent key (insert)
1608 match map.entry(10) {
1609 Occupied(_) => unreachable!(),
1611 assert_eq!(*view.insert(1000), 1000);
1614 assert_eq!(map.get(&10).unwrap(), &1000);
1615 assert_eq!(map.len(), 6);
1627 use std::rand::{weak_rng, Rng};
1628 use test::{Bencher, black_box};
1630 use super::BTreeMap;
1631 use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1634 pub fn insert_rand_100(b: &mut Bencher) {
1635 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1636 insert_rand_n(100, &mut m, b,
1637 |m, i| { m.insert(i, 1); },
1638 |m, i| { m.remove(&i); });
1642 pub fn insert_rand_10_000(b: &mut Bencher) {
1643 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1644 insert_rand_n(10_000, &mut m, b,
1645 |m, i| { m.insert(i, 1); },
1646 |m, i| { m.remove(&i); });
1651 pub fn insert_seq_100(b: &mut Bencher) {
1652 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1653 insert_seq_n(100, &mut m, b,
1654 |m, i| { m.insert(i, 1); },
1655 |m, i| { m.remove(&i); });
1659 pub fn insert_seq_10_000(b: &mut Bencher) {
1660 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1661 insert_seq_n(10_000, &mut m, b,
1662 |m, i| { m.insert(i, 1); },
1663 |m, i| { m.remove(&i); });
1668 pub fn find_rand_100(b: &mut Bencher) {
1669 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1670 find_rand_n(100, &mut m, b,
1671 |m, i| { m.insert(i, 1); },
1672 |m, i| { m.get(&i); });
1676 pub fn find_rand_10_000(b: &mut Bencher) {
1677 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1678 find_rand_n(10_000, &mut m, b,
1679 |m, i| { m.insert(i, 1); },
1680 |m, i| { m.get(&i); });
1685 pub fn find_seq_100(b: &mut Bencher) {
1686 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1687 find_seq_n(100, &mut m, b,
1688 |m, i| { m.insert(i, 1); },
1689 |m, i| { m.get(&i); });
1693 pub fn find_seq_10_000(b: &mut Bencher) {
1694 let mut m : BTreeMap<uint,uint> = BTreeMap::new();
1695 find_seq_n(10_000, &mut m, b,
1696 |m, i| { m.insert(i, 1); },
1697 |m, i| { m.get(&i); });
1700 fn bench_iter(b: &mut Bencher, size: uint) {
1701 let mut map = BTreeMap::<uint, uint>::new();
1702 let mut rng = weak_rng();
1704 for _ in range(0, size) {
1705 map.insert(rng.gen(), rng.gen());
1709 for entry in map.iter() {
1716 pub fn iter_20(b: &mut Bencher) {
1721 pub fn iter_1000(b: &mut Bencher) {
1722 bench_iter(b, 1000);
1726 pub fn iter_100000(b: &mut Bencher) {
1727 bench_iter(b, 100000);