1 // Copyright 2013-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 //! Ordered maps and sets, implemented as simple tries.
14 pub use self::Entry::*;
15 use self::TrieNode::*;
16 use alloc::boxed::Box;
17 use core::default::Default;
20 use core::mem::zeroed;
22 use core::ops::{Slice, SliceMut};
26 use std::hash::{Writer, Hash};
28 use slice::{Items, MutItems};
31 // FIXME(conventions): implement bounded iterators
32 // FIXME(conventions): implement into_iter
33 // FIXME(conventions): replace each_reverse by making iter DoubleEnded
35 // FIXME: #5244: need to manually update the InternalNode constructor
36 const SHIFT: uint = 4;
37 const SIZE: uint = 1 << SHIFT;
38 const MASK: uint = SIZE - 1;
39 // The number of chunks that the key is divided into. Also the maximum depth of the TrieMap.
40 const MAX_DEPTH: uint = uint::BITS / SHIFT;
42 /// A map implemented as a radix trie.
44 /// Keys are split into sequences of 4 bits, which are used to place elements in
45 /// 16-entry arrays which are nested to form a tree structure. Inserted elements are placed
46 /// as close to the top of the tree as possible. The most significant bits of the key are used to
47 /// assign the key to a node/bucket in the first layer. If there are no other elements keyed by
48 /// the same 4 bits in the first layer, a leaf node will be created in the first layer.
49 /// When keys coincide, the next 4 bits are used to assign the node to a bucket in the next layer,
50 /// with this process continuing until an empty spot is found or there are no more bits left in the
51 /// key. As a result, the maximum depth using 32-bit `uint` keys is 8. The worst collisions occur
52 /// for very small numbers. For example, 1 and 2 are identical in all but their least significant
53 /// 4 bits. If both numbers are used as keys, a chain of maximum length will be created to
54 /// differentiate them.
59 /// use std::collections::TrieMap;
61 /// let mut map = TrieMap::new();
62 /// map.insert(27, "Olaf");
63 /// map.insert(1, "Edgar");
64 /// map.insert(13, "Ruth");
65 /// map.insert(1, "Martin");
67 /// assert_eq!(map.len(), 3);
68 /// assert_eq!(map.get(&1), Some(&"Martin"));
70 /// if !map.contains_key(&90) {
71 /// println!("Nobody is keyed 90");
75 /// match map.get_mut(&1) {
76 /// Some(value) => *value = "Olga",
81 /// assert_eq!(map.len(), 2);
83 /// // Print the key value pairs, ordered by key.
84 /// for (key, value) in map.iter() {
85 /// // Prints `1: Olga` then `27: Olaf`
86 /// println!("{}: {}", key, value);
90 /// assert!(map.is_empty());
93 pub struct TrieMap<T> {
94 root: InternalNode<T>,
98 // An internal node holds SIZE child nodes, which may themselves contain more internal nodes.
100 // Throughout this implementation, "idx" is used to refer to a section of key that is used
101 // to access a node. The layer of the tree directly below the root corresponds to idx 0.
102 struct InternalNode<T> {
103 // The number of direct children which are external (i.e. that store a value).
105 children: [TrieNode<T>, ..SIZE]
108 // Each child of an InternalNode may be internal, in which case nesting continues,
109 // external (containing a value), or empty
112 Internal(Box<InternalNode<T>>),
117 impl<T: PartialEq> PartialEq for TrieMap<T> {
118 fn eq(&self, other: &TrieMap<T>) -> bool {
119 self.len() == other.len() &&
120 self.iter().zip(other.iter()).all(|(a, b)| a == b)
124 impl<T: Eq> Eq for TrieMap<T> {}
126 impl<T: PartialOrd> PartialOrd for TrieMap<T> {
128 fn partial_cmp(&self, other: &TrieMap<T>) -> Option<Ordering> {
129 iter::order::partial_cmp(self.iter(), other.iter())
133 impl<T: Ord> Ord for TrieMap<T> {
135 fn cmp(&self, other: &TrieMap<T>) -> Ordering {
136 iter::order::cmp(self.iter(), other.iter())
140 impl<T: Show> Show for TrieMap<T> {
141 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
142 try!(write!(f, "{{"));
144 for (i, (k, v)) in self.iter().enumerate() {
145 if i != 0 { try!(write!(f, ", ")); }
146 try!(write!(f, "{}: {}", k, *v));
153 impl<T> Default for TrieMap<T> {
155 fn default() -> TrieMap<T> { TrieMap::new() }
159 /// Creates an empty `TrieMap`.
164 /// use std::collections::TrieMap;
165 /// let mut map: TrieMap<&str> = TrieMap::new();
168 #[unstable = "matches collection reform specification, waiting for dust to settle"]
169 pub fn new() -> TrieMap<T> {
170 TrieMap{root: InternalNode::new(), length: 0}
173 /// Visits all key-value pairs in reverse order. Aborts traversal when `f` returns `false`.
174 /// Returns `true` if `f` returns `true` for all elements.
179 /// use std::collections::TrieMap;
180 /// let map: TrieMap<&str> = [(1, "a"), (2, "b"), (3, "c")].iter().map(|&x| x).collect();
182 /// let mut vec = Vec::new();
183 /// assert_eq!(true, map.each_reverse(|&key, &value| { vec.push((key, value)); true }));
184 /// assert_eq!(vec, vec![(3, "c"), (2, "b"), (1, "a")]);
186 /// // Stop when we reach 2
187 /// let mut vec = Vec::new();
188 /// assert_eq!(false, map.each_reverse(|&key, &value| { vec.push(value); key != 2 }));
189 /// assert_eq!(vec, vec!["c", "b"]);
192 pub fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
193 self.root.each_reverse(f)
196 /// Gets an iterator visiting all keys in ascending order by the keys.
197 /// The iterator's element type is `uint`.
198 #[unstable = "matches collection reform specification, waiting for dust to settle"]
199 pub fn keys<'r>(&'r self) -> Keys<'r, T> {
200 self.iter().map(|(k, _v)| k)
203 /// Gets an iterator visiting all values in ascending order by the keys.
204 /// The iterator's element type is `&'r T`.
205 #[unstable = "matches collection reform specification, waiting for dust to settle"]
206 pub fn values<'r>(&'r self) -> Values<'r, T> {
207 self.iter().map(|(_k, v)| v)
210 /// Gets an iterator over the key-value pairs in the map, ordered by keys.
215 /// use std::collections::TrieMap;
216 /// let map: TrieMap<&str> = [(3, "c"), (1, "a"), (2, "b")].iter().map(|&x| x).collect();
218 /// for (key, value) in map.iter() {
219 /// println!("{}: {}", key, value);
222 #[unstable = "matches collection reform specification, waiting for dust to settle"]
223 pub fn iter<'a>(&'a self) -> Entries<'a, T> {
224 let mut iter = unsafe {Entries::new()};
225 iter.stack[0] = self.root.children.iter();
227 iter.remaining_min = self.length;
228 iter.remaining_max = self.length;
233 /// Gets an iterator over the key-value pairs in the map, with the
234 /// ability to mutate the values.
239 /// use std::collections::TrieMap;
240 /// let mut map: TrieMap<int> = [(1, 2), (2, 4), (3, 6)].iter().map(|&x| x).collect();
242 /// for (key, value) in map.iter_mut() {
243 /// *value = -(key as int);
246 /// assert_eq!(map.get(&1), Some(&-1));
247 /// assert_eq!(map.get(&2), Some(&-2));
248 /// assert_eq!(map.get(&3), Some(&-3));
250 #[unstable = "matches collection reform specification, waiting for dust to settle"]
251 pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, T> {
252 let mut iter = unsafe {MutEntries::new()};
253 iter.stack[0] = self.root.children.iter_mut();
255 iter.remaining_min = self.length;
256 iter.remaining_max = self.length;
261 /// Return the number of elements in the map.
266 /// use std::collections::TrieMap;
268 /// let mut a = TrieMap::new();
269 /// assert_eq!(a.len(), 0);
270 /// a.insert(1, "a");
271 /// assert_eq!(a.len(), 1);
274 #[unstable = "matches collection reform specification, waiting for dust to settle"]
275 pub fn len(&self) -> uint { self.length }
277 /// Return true if the map contains no elements.
282 /// use std::collections::TrieMap;
284 /// let mut a = TrieMap::new();
285 /// assert!(a.is_empty());
286 /// a.insert(1, "a");
287 /// assert!(!a.is_empty());
290 #[unstable = "matches collection reform specification, waiting for dust to settle"]
291 pub fn is_empty(&self) -> bool { self.len() == 0 }
293 /// Clears the map, removing all values.
298 /// use std::collections::TrieMap;
300 /// let mut a = TrieMap::new();
301 /// a.insert(1, "a");
303 /// assert!(a.is_empty());
306 #[unstable = "matches collection reform specification, waiting for dust to settle"]
307 pub fn clear(&mut self) {
308 self.root = InternalNode::new();
312 /// Deprecated: renamed to `get`.
313 #[deprecated = "renamed to `get`"]
314 pub fn find(&self, key: &uint) -> Option<&T> {
318 /// Returns a reference to the value corresponding to the key.
323 /// use std::collections::TrieMap;
325 /// let mut map = TrieMap::new();
326 /// map.insert(1, "a");
327 /// assert_eq!(map.get(&1), Some(&"a"));
328 /// assert_eq!(map.get(&2), None);
331 #[unstable = "matches collection reform specification, waiting for dust to settle"]
332 pub fn get(&self, key: &uint) -> Option<&T> {
333 let mut node = &self.root;
336 match node.children[chunk(*key, idx)] {
337 Internal(ref x) => node = &**x,
338 External(stored, ref value) => {
345 Nothing => return None
351 /// Returns true if the map contains a value for the specified key.
356 /// use std::collections::TrieMap;
358 /// let mut map = TrieMap::new();
359 /// map.insert(1, "a");
360 /// assert_eq!(map.contains_key(&1), true);
361 /// assert_eq!(map.contains_key(&2), false);
364 #[unstable = "matches collection reform specification, waiting for dust to settle"]
365 pub fn contains_key(&self, key: &uint) -> bool {
366 self.get(key).is_some()
369 /// Deprecated: renamed to `get_mut`.
370 #[deprecated = "renamed to `get_mut`"]
371 pub fn find_mut(&mut self, key: &uint) -> Option<&mut T> {
375 /// Returns a mutable reference to the value corresponding to the key.
380 /// use std::collections::TrieMap;
382 /// let mut map = TrieMap::new();
383 /// map.insert(1, "a");
384 /// match map.get_mut(&1) {
385 /// Some(x) => *x = "b",
388 /// assert_eq!(map[1], "b");
391 #[unstable = "matches collection reform specification, waiting for dust to settle"]
392 pub fn get_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
393 find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
396 /// Deprecated: Renamed to `insert`.
397 #[deprecated = "Renamed to `insert`"]
398 pub fn swap(&mut self, key: uint, value: T) -> Option<T> {
399 self.insert(key, value)
402 /// Inserts a key-value pair from the map. If the key already had a value
403 /// present in the map, that value is returned. Otherwise, `None` is returned.
408 /// use std::collections::TrieMap;
410 /// let mut map = TrieMap::new();
411 /// assert_eq!(map.insert(37, "a"), None);
412 /// assert_eq!(map.is_empty(), false);
414 /// map.insert(37, "b");
415 /// assert_eq!(map.insert(37, "c"), Some("b"));
416 /// assert_eq!(map[37], "c");
418 #[unstable = "matches collection reform specification, waiting for dust to settle"]
419 pub fn insert(&mut self, key: uint, value: T) -> Option<T> {
420 let (_, old_val) = insert(&mut self.root.count,
421 &mut self.root.children[chunk(key, 0)],
423 if old_val.is_none() { self.length += 1 }
427 /// Deprecated: Renamed to `remove`.
428 #[deprecated = "Renamed to `remove`"]
429 pub fn pop(&mut self, key: &uint) -> Option<T> {
433 /// Removes a key from the map, returning the value at the key if the key
434 /// was previously in the map.
439 /// use std::collections::TrieMap;
441 /// let mut map = TrieMap::new();
442 /// map.insert(1, "a");
443 /// assert_eq!(map.remove(&1), Some("a"));
444 /// assert_eq!(map.remove(&1), None);
446 #[unstable = "matches collection reform specification, waiting for dust to settle"]
447 pub fn remove(&mut self, key: &uint) -> Option<T> {
448 let ret = remove(&mut self.root.count,
449 &mut self.root.children[chunk(*key, 0)],
451 if ret.is_some() { self.length -= 1 }
456 // FIXME #5846 we want to be able to choose between &x and &mut x
457 // (with many different `x`) below, so we need to optionally pass mut
458 // as a tt, but the only thing we can do with a `tt` is pass them to
459 // other macros, so this takes the `& <mutability> <operand>` token
460 // sequence and forces their evaluation as an expression. (see also
462 macro_rules! addr { ($e:expr) => { $e } }
465 ($iterator_name:ident,
466 // the current treemap
468 // the key to look for
470 // are we looking at the upper bound?
471 is_upper = $upper:expr,
473 // method names for slicing/iterating.
474 slice_from = $slice_from:ident,
477 // see the comment on `addr!`, this is just an optional mut, but
478 // there's no 0-or-1 repeats yet.
479 mutability = $($mut_:tt)*) => {
482 // We need an unsafe pointer here because we are borrowing
483 // mutable references to the internals of each of these
484 // mutable nodes, while still using the outer node.
486 // However, we're allowed to flaunt rustc like this because we
487 // never actually modify the "shape" of the nodes. The only
488 // place that mutation is can actually occur is of the actual
489 // values of the TrieMap (as the return value of the
490 // iterator), i.e. we can never cause a deallocation of any
491 // InternalNodes so the raw pointer is always valid.
494 // We like sharing code so much that even a little unsafe won't
497 let mut node = unsafe {
498 mem::transmute::<_, uint>(&this.root) as *mut InternalNode<T>
503 let mut it = unsafe {$iterator_name::new()};
504 // everything else is zero'd, as we want.
505 it.remaining_max = this.length;
507 // this addr is necessary for the `Internal` pattern.
509 let children = unsafe {addr!(& $($mut_)* (*node).children)};
510 // it.length is the current depth in the iterator and the
511 // current depth through the `uint` key we've traversed.
512 let child_id = chunk(key, it.length);
513 let (slice_idx, ret) = match children[child_id] {
514 Internal(ref $($mut_)* n) => {
516 mem::transmute::<_, uint>(&**n)
517 as *mut InternalNode<T>
519 (child_id + 1, false)
521 External(stored, _) => {
522 (if stored < key || ($upper && stored == key) {
532 // push to the stack.
533 it.stack[it.length] = children.$slice_from(&slice_idx).$iter();
542 // If `upper` is true then returns upper_bound else returns lower_bound.
544 fn bound<'a>(&'a self, key: uint, upper: bool) -> Entries<'a, T> {
545 bound!(Entries, self = self,
546 key = key, is_upper = upper,
547 slice_from = slice_from_or_fail, iter = iter,
551 /// Gets an iterator pointing to the first key-value pair whose key is not less than `key`.
552 /// If all keys in the map are less than `key` an empty iterator is returned.
557 /// use std::collections::TrieMap;
558 /// let map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).collect();
560 /// assert_eq!(map.lower_bound(4).next(), Some((4, &"b")));
561 /// assert_eq!(map.lower_bound(5).next(), Some((6, &"c")));
562 /// assert_eq!(map.lower_bound(10).next(), None);
564 pub fn lower_bound<'a>(&'a self, key: uint) -> Entries<'a, T> {
565 self.bound(key, false)
568 /// Gets an iterator pointing to the first key-value pair whose key is greater than `key`.
569 /// If all keys in the map are not greater than `key` an empty iterator is returned.
574 /// use std::collections::TrieMap;
575 /// let map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).collect();
577 /// assert_eq!(map.upper_bound(4).next(), Some((6, &"c")));
578 /// assert_eq!(map.upper_bound(5).next(), Some((6, &"c")));
579 /// assert_eq!(map.upper_bound(10).next(), None);
581 pub fn upper_bound<'a>(&'a self, key: uint) -> Entries<'a, T> {
582 self.bound(key, true)
584 // If `upper` is true then returns upper_bound else returns lower_bound.
586 fn bound_mut<'a>(&'a mut self, key: uint, upper: bool) -> MutEntries<'a, T> {
587 bound!(MutEntries, self = self,
588 key = key, is_upper = upper,
589 slice_from = slice_from_or_fail_mut, iter = iter_mut,
593 /// Gets an iterator pointing to the first key-value pair whose key is not less than `key`.
594 /// If all keys in the map are less than `key` an empty iterator is returned.
599 /// use std::collections::TrieMap;
600 /// let mut map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).collect();
602 /// assert_eq!(map.lower_bound_mut(4).next(), Some((4, &mut "b")));
603 /// assert_eq!(map.lower_bound_mut(5).next(), Some((6, &mut "c")));
604 /// assert_eq!(map.lower_bound_mut(10).next(), None);
606 /// for (key, value) in map.lower_bound_mut(4) {
607 /// *value = "changed";
610 /// assert_eq!(map.get(&2), Some(&"a"));
611 /// assert_eq!(map.get(&4), Some(&"changed"));
612 /// assert_eq!(map.get(&6), Some(&"changed"));
614 pub fn lower_bound_mut<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
615 self.bound_mut(key, false)
618 /// Gets an iterator pointing to the first key-value pair whose key is greater than `key`.
619 /// If all keys in the map are not greater than `key` an empty iterator is returned.
624 /// use std::collections::TrieMap;
625 /// let mut map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).collect();
627 /// assert_eq!(map.upper_bound_mut(4).next(), Some((6, &mut "c")));
628 /// assert_eq!(map.upper_bound_mut(5).next(), Some((6, &mut "c")));
629 /// assert_eq!(map.upper_bound_mut(10).next(), None);
631 /// for (key, value) in map.upper_bound_mut(4) {
632 /// *value = "changed";
635 /// assert_eq!(map.get(&2), Some(&"a"));
636 /// assert_eq!(map.get(&4), Some(&"b"));
637 /// assert_eq!(map.get(&6), Some(&"changed"));
639 pub fn upper_bound_mut<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
640 self.bound_mut(key, true)
644 impl<T> FromIterator<(uint, T)> for TrieMap<T> {
645 fn from_iter<Iter: Iterator<(uint, T)>>(iter: Iter) -> TrieMap<T> {
646 let mut map = TrieMap::new();
652 impl<T> Extend<(uint, T)> for TrieMap<T> {
653 fn extend<Iter: Iterator<(uint, T)>>(&mut self, mut iter: Iter) {
660 impl<S: Writer, T: Hash<S>> Hash<S> for TrieMap<T> {
661 fn hash(&self, state: &mut S) {
662 for elt in self.iter() {
668 impl<T> Index<uint, T> for TrieMap<T> {
670 fn index<'a>(&'a self, i: &uint) -> &'a T {
671 self.get(i).expect("key not present")
675 impl<T> IndexMut<uint, T> for TrieMap<T> {
677 fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut T {
678 self.get_mut(i).expect("key not present")
682 impl<T:Clone> Clone for InternalNode<T> {
684 fn clone(&self) -> InternalNode<T> {
685 let ch = &self.children;
688 children: [ch[0].clone(), ch[1].clone(), ch[2].clone(), ch[3].clone(),
689 ch[4].clone(), ch[5].clone(), ch[6].clone(), ch[7].clone(),
690 ch[8].clone(), ch[9].clone(), ch[10].clone(), ch[11].clone(),
691 ch[12].clone(), ch[13].clone(), ch[14].clone(), ch[15].clone()]}
695 impl<T> InternalNode<T> {
697 fn new() -> InternalNode<T> {
698 // FIXME: #5244: [Nothing, ..SIZE] should be possible without implicit
700 InternalNode{count: 0,
701 children: [Nothing, Nothing, Nothing, Nothing,
702 Nothing, Nothing, Nothing, Nothing,
703 Nothing, Nothing, Nothing, Nothing,
704 Nothing, Nothing, Nothing, Nothing]}
708 impl<T> InternalNode<T> {
709 fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool {
710 for elt in self.children.iter().rev() {
712 Internal(ref x) => if !x.each_reverse(|i,t| f(i,t)) { return false },
713 External(k, ref v) => if !f(&k, v) { return false },
721 // if this was done via a trait, the key could be generic
723 fn chunk(n: uint, idx: uint) -> uint {
724 let sh = uint::BITS - (SHIFT * (idx + 1));
728 fn find_mut<'r, T>(child: &'r mut TrieNode<T>, key: uint, idx: uint) -> Option<&'r mut T> {
730 External(stored, ref mut value) if stored == key => Some(value),
731 External(..) => None,
732 Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
737 /// Inserts a new node for the given key and value, at or below `start_node`.
739 /// The index (`idx`) is the index of the next node, such that the start node
740 /// was accessed via parent.children[chunk(key, idx - 1)].
742 /// The count is the external node counter for the start node's parent,
743 /// which will be incremented only if `start_node` is transformed into a *new* external node.
745 /// Returns a mutable reference to the inserted value and an optional previous value.
746 fn insert<'a, T>(count: &mut uint, start_node: &'a mut TrieNode<T>, key: uint, value: T, idx: uint)
747 -> (&'a mut T, Option<T>) {
748 // We branch twice to avoid having to do the `replace` when we
749 // don't need to; this is much faster, especially for keys that
750 // have long shared prefixes.
754 *start_node = External(key, value);
756 External(_, ref mut value_ref) => return (value_ref, None),
760 Internal(box ref mut x) => {
761 return insert(&mut x.count, &mut x.children[chunk(key, idx)], key, value, idx + 1);
763 External(stored_key, ref mut stored_value) if stored_key == key => {
764 // Swap in the new value and return the old.
765 let old_value = mem::replace(stored_value, value);
766 return (stored_value, Some(old_value));
771 // Conflict, an external node with differing keys.
772 // We replace the old node by an internal one, then re-insert the two values beneath it.
773 match mem::replace(start_node, Internal(box InternalNode::new())) {
774 External(stored_key, stored_value) => {
776 Internal(box ref mut new_node) => {
777 // Re-insert the old value.
778 insert(&mut new_node.count,
779 &mut new_node.children[chunk(stored_key, idx)],
780 stored_key, stored_value, idx + 1);
782 // Insert the new value, and return a reference to it directly.
783 insert(&mut new_node.count,
784 &mut new_node.children[chunk(key, idx)],
787 // Value that was just copied disappeared.
791 // Logic error in previous match.
796 fn remove<T>(count: &mut uint, child: &mut TrieNode<T>, key: uint,
797 idx: uint) -> Option<T> {
798 let (ret, this) = match *child {
799 External(stored, _) if stored == key => {
800 match mem::replace(child, Nothing) {
801 External(_, value) => (Some(value), true),
805 External(..) => (None, false),
806 Internal(box ref mut x) => {
807 let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
811 Nothing => (None, false)
821 /// A view into a single entry in a TrieMap, which may be vacant or occupied.
822 pub enum Entry<'a, T: 'a> {
823 /// An occupied entry.
824 Occupied(OccupiedEntry<'a, T>),
826 Vacant(VacantEntry<'a, T>)
829 /// A view into an occupied entry in a TrieMap.
830 pub struct OccupiedEntry<'a, T: 'a> {
831 search_stack: SearchStack<'a, T>
834 /// A view into a vacant entry in a TrieMap.
835 pub struct VacantEntry<'a, T: 'a> {
836 search_stack: SearchStack<'a, T>
839 /// A list of nodes encoding a path from the root of a TrieMap to a node.
842 /// * The last node is either `External` or `Nothing`.
843 /// * Pointers at indexes less than `length` can be safely dereferenced.
844 struct SearchStack<'a, T: 'a> {
845 map: &'a mut TrieMap<T>,
848 items: [*mut TrieNode<T>, ..MAX_DEPTH]
851 impl<'a, T> SearchStack<'a, T> {
852 /// Creates a new search-stack with empty entries.
853 fn new(map: &'a mut TrieMap<T>, key: uint) -> SearchStack<'a, T> {
858 items: [ptr::null_mut(), ..MAX_DEPTH]
862 fn push(&mut self, node: *mut TrieNode<T>) {
864 self.items[self.length - 1] = node;
867 fn peek(&self) -> *mut TrieNode<T> {
868 self.items[self.length - 1]
871 fn peek_ref(&self) -> &'a mut TrieNode<T> {
873 &mut *self.items[self.length - 1]
877 fn pop_ref(&mut self) -> &'a mut TrieNode<T> {
880 &mut *self.items[self.length]
884 fn is_empty(&self) -> bool {
888 fn get_ref(&self, idx: uint) -> &'a mut TrieNode<T> {
889 assert!(idx < self.length);
891 &mut *self.items[idx]
896 // Implementation of SearchStack creation logic.
897 // Once a SearchStack has been created the Entry methods are relatively straight-forward.
899 /// Gets the given key's corresponding entry in the map for in-place manipulation.
901 pub fn entry<'a>(&'a mut self, key: uint) -> Entry<'a, T> {
902 // Create an empty search stack.
903 let mut search_stack = SearchStack::new(self, key);
905 // Unconditionally add the corresponding node from the first layer.
906 let first_node = &mut search_stack.map.root.children[chunk(key, 0)] as *mut _;
907 search_stack.push(first_node);
909 // While no appropriate slot is found, keep descending down the Trie,
910 // adding nodes to the search stack.
911 let search_successful: bool;
913 match unsafe { next_child(search_stack.peek(), key, search_stack.length) } {
914 (Some(child), _) => search_stack.push(child),
916 search_successful = success;
922 if search_successful {
923 Occupied(OccupiedEntry { search_stack: search_stack })
925 Vacant(VacantEntry { search_stack: search_stack })
930 /// Get a mutable pointer to the next child of a node, given a key and an idx.
932 /// The idx is the index of the next child, such that `node` was accessed via
933 /// parent.children[chunk(key, idx - 1)].
935 /// Returns a tuple with an optional mutable pointer to the next child, and
936 /// a boolean flag to indicate whether the external key node was found.
938 /// This function is safe only if `node` points to a valid `TrieNode`.
940 unsafe fn next_child<'a, T>(node: *mut TrieNode<T>, key: uint, idx: uint)
941 -> (Option<*mut TrieNode<T>>, bool) {
943 // If the node is internal, tell the caller to descend further.
944 Internal(box ref mut node_internal) => {
945 (Some(&mut node_internal.children[chunk(key, idx)] as *mut _), false)
947 // If the node is external or empty, the search is complete.
948 // If the key doesn't match, node expansion will be done upon
949 // insertion. If it does match, we've found our node.
950 External(stored_key, _) if stored_key == key => (None, true),
951 External(..) | Nothing => (None, false)
955 // NB: All these methods assume a correctly constructed occupied entry (matching the given key).
956 impl<'a, T> OccupiedEntry<'a, T> {
957 /// Gets a reference to the value in the entry.
959 pub fn get(&self) -> &T {
960 match *self.search_stack.peek_ref() {
961 External(_, ref value) => value,
962 // Invalid SearchStack, non-external last node.
967 /// Gets a mutable reference to the value in the entry.
969 pub fn get_mut(&mut self) -> &mut T {
970 match *self.search_stack.peek_ref() {
971 External(_, ref mut value) => value,
972 // Invalid SearchStack, non-external last node.
977 /// Converts the OccupiedEntry into a mutable reference to the value in the entry,
978 /// with a lifetime bound to the map itself.
980 pub fn into_mut(self) -> &'a mut T {
981 match *self.search_stack.peek_ref() {
982 External(_, ref mut value) => value,
983 // Invalid SearchStack, non-external last node.
988 /// Sets the value of the entry, and returns the entry's old value.
990 pub fn set(&mut self, value: T) -> T {
991 match *self.search_stack.peek_ref() {
992 External(_, ref mut stored_value) => {
993 mem::replace(stored_value, value)
995 // Invalid SearchStack, non-external last node.
1000 /// Takes the value out of the entry, and returns it.
1002 pub fn take(self) -> T {
1003 // This function removes the external leaf-node, then unwinds the search-stack
1004 // deleting now-childless ancestors.
1005 let mut search_stack = self.search_stack;
1007 // Extract the value from the leaf-node of interest.
1008 let leaf_node = mem::replace(search_stack.pop_ref(), Nothing);
1010 let value = match leaf_node {
1011 External(_, value) => value,
1012 // Invalid SearchStack, non-external last node.
1016 // Iterate backwards through the search stack, deleting nodes if they are childless.
1017 // We compare each ancestor's parent count to 1 because each ancestor reached has just
1018 // had one of its children deleted.
1019 while !search_stack.is_empty() {
1020 let ancestor = search_stack.pop_ref();
1022 Internal(ref mut internal) => {
1023 // If stopping deletion, update the child count and break.
1024 if internal.count != 1 {
1025 internal.count -= 1;
1029 // Invalid SearchStack, non-internal ancestor node.
1032 *ancestor = Nothing;
1035 // Decrement the length of the entire TrieMap, for the removed node.
1036 search_stack.map.length -= 1;
1042 impl<'a, T> VacantEntry<'a, T> {
1043 /// Set the vacant entry to the given value.
1044 pub fn set(self, value: T) -> &'a mut T {
1045 let search_stack = self.search_stack;
1046 let old_length = search_stack.length;
1047 let key = search_stack.key;
1049 // Update the TrieMap's length for the new element.
1050 search_stack.map.length += 1;
1052 // If there's only 1 node in the search stack, insert a new node below it at idx 1.
1053 if old_length == 1 {
1054 // Note: Small hack to appease the borrow checker. Can't mutably borrow root.count
1055 let mut temp = search_stack.map.root.count;
1056 let (value_ref, _) = insert(&mut temp, search_stack.get_ref(0), key, value, 1);
1057 search_stack.map.root.count = temp;
1060 // Otherwise, find the predecessor of the last stack node, and insert as normal.
1062 match *search_stack.get_ref(old_length - 2) {
1063 Internal(box ref mut parent) => {
1064 let (value_ref, _) = insert(&mut parent.count,
1065 &mut parent.children[chunk(key, old_length - 1)],
1066 key, value, old_length);
1069 // Invalid SearchStack, non-internal ancestor node.
1076 /// A forward iterator over a map.
1077 pub struct Entries<'a, T:'a> {
1078 stack: [slice::Items<'a, TrieNode<T>>, .. MAX_DEPTH],
1080 remaining_min: uint,
1084 /// A forward iterator over the key-value pairs of a map, with the
1085 /// values being mutable.
1086 pub struct MutEntries<'a, T:'a> {
1087 stack: [slice::MutItems<'a, TrieNode<T>>, .. MAX_DEPTH],
1089 remaining_min: uint,
1093 /// A forward iterator over the keys of a map.
1094 pub type Keys<'a, T> =
1095 iter::Map<'static, (uint, &'a T), uint, Entries<'a, T>>;
1097 /// A forward iterator over the values of a map.
1098 pub type Values<'a, T> =
1099 iter::Map<'static, (uint, &'a T), &'a T, Entries<'a, T>>;
1101 // FIXME #5846: see `addr!` above.
1102 macro_rules! item { ($i:item) => {$i}}
1104 macro_rules! iterator_impl {
1107 mutability = $($mut_:tt)*) => {
1108 impl<'a, T> $name<'a, T> {
1109 // Create new zero'd iterator. We have a thin gilding of safety by
1110 // using init rather than uninit, so that the worst that can happen
1111 // from failing to initialise correctly after calling these is a
1113 #[cfg(target_word_size="32")]
1114 unsafe fn new() -> $name<'a, T> {
1119 // ick :( ... at least the compiler will tell us if we screwed up.
1120 stack: [zeroed(), zeroed(), zeroed(), zeroed(), zeroed(),
1121 zeroed(), zeroed(), zeroed()]
1125 #[cfg(target_word_size="64")]
1126 unsafe fn new() -> $name<'a, T> {
1131 stack: [zeroed(), zeroed(), zeroed(), zeroed(),
1132 zeroed(), zeroed(), zeroed(), zeroed(),
1133 zeroed(), zeroed(), zeroed(), zeroed(),
1134 zeroed(), zeroed(), zeroed(), zeroed()]
1139 item!(impl<'a, T> Iterator<(uint, &'a $($mut_)* T)> for $name<'a, T> {
1140 // you might wonder why we're not even trying to act within the
1141 // rules, and are just manipulating raw pointers like there's no
1142 // such thing as invalid pointers and memory unsafety. The
1143 // reason is performance, without doing this we can get the
1144 // (now replaced) bench_iter_large microbenchmark down to about
1145 // 30000 ns/iter (using .unsafe_get to index self.stack directly, 38000
1146 // ns/iter with [] checked indexing), but this smashes that down
1147 // to 13500 ns/iter.
1149 // Fortunately, it's still safe...
1151 // We have an invariant that every Internal node
1152 // corresponds to one push to self.stack, and one pop,
1153 // nested appropriately. self.stack has enough storage
1154 // to store the maximum depth of Internal nodes in the
1155 // trie (8 on 32-bit platforms, 16 on 64-bit).
1156 fn next(&mut self) -> Option<(uint, &'a $($mut_)* T)> {
1157 let start_ptr = self.stack.as_mut_ptr();
1160 // write_ptr is the next place to write to the stack.
1161 // invariant: start_ptr <= write_ptr < end of the
1163 let mut write_ptr = start_ptr.offset(self.length as int);
1164 while write_ptr != start_ptr {
1165 // indexing back one is safe, since write_ptr >
1167 match (*write_ptr.offset(-1)).next() {
1168 // exhausted this iterator (i.e. finished this
1169 // Internal node), so pop from the stack.
1171 // don't bother clearing the memory, because the
1172 // next time we use it we'll've written to it
1174 None => write_ptr = write_ptr.offset(-1),
1176 addr!(match *child {
1177 Internal(ref $($mut_)* node) => {
1178 // going down a level, so push
1179 // to the stack (this is the
1180 // write referenced above)
1181 *write_ptr = node.children.$iter();
1182 write_ptr = write_ptr.offset(1);
1184 External(key, ref $($mut_)* value) => {
1185 self.remaining_max -= 1;
1186 if self.remaining_min > 0 {
1187 self.remaining_min -= 1;
1189 // store the new length of the
1190 // stack, based on our current
1192 self.length = (write_ptr as uint
1193 - start_ptr as uint) /
1194 mem::size_of_val(&*write_ptr);
1196 return Some((key, value));
1208 fn size_hint(&self) -> (uint, Option<uint>) {
1209 (self.remaining_min, Some(self.remaining_max))
1215 iterator_impl! { Entries, iter = iter, mutability = }
1216 iterator_impl! { MutEntries, iter = iter_mut, mutability = mut }
1220 use std::prelude::*;
1221 use std::iter::range_step;
1225 use super::{TrieMap, InternalNode};
1226 use super::Entry::*;
1227 use super::TrieNode::*;
1229 fn check_integrity<T>(trie: &InternalNode<T>) {
1230 assert!(trie.count != 0);
1234 for x in trie.children.iter() {
1237 Internal(ref y) => {
1238 check_integrity(&**y);
1241 External(_, _) => { sum += 1 }
1245 assert_eq!(sum, trie.count);
1249 fn test_find_mut() {
1250 let mut m = TrieMap::new();
1251 assert!(m.insert(1u, 12i).is_none());
1252 assert!(m.insert(2u, 8i).is_none());
1253 assert!(m.insert(5u, 14i).is_none());
1255 match m.get_mut(&5) {
1256 None => panic!(), Some(x) => *x = new
1258 assert_eq!(m.get(&5), Some(&new));
1262 fn test_find_mut_missing() {
1263 let mut m = TrieMap::new();
1264 assert!(m.get_mut(&0).is_none());
1265 assert!(m.insert(1u, 12i).is_none());
1266 assert!(m.get_mut(&0).is_none());
1267 assert!(m.insert(2, 8).is_none());
1268 assert!(m.get_mut(&0).is_none());
1273 let mut trie = TrieMap::new();
1276 for x in range_step(1u, n, 2) {
1277 assert!(trie.insert(x, x + 1).is_none());
1278 assert!(trie.contains_key(&x));
1279 check_integrity(&trie.root);
1282 for x in range_step(0u, n, 2) {
1283 assert!(!trie.contains_key(&x));
1284 assert!(trie.insert(x, x + 1).is_none());
1285 check_integrity(&trie.root);
1288 for x in range(0u, n) {
1289 assert!(trie.contains_key(&x));
1290 assert!(!trie.insert(x, x + 1).is_none());
1291 check_integrity(&trie.root);
1294 for x in range_step(1u, n, 2) {
1295 assert!(trie.remove(&x).is_some());
1296 assert!(!trie.contains_key(&x));
1297 check_integrity(&trie.root);
1300 for x in range_step(0u, n, 2) {
1301 assert!(trie.contains_key(&x));
1302 assert!(!trie.insert(x, x + 1).is_none());
1303 check_integrity(&trie.root);
1308 fn test_each_reverse() {
1309 let mut m = TrieMap::new();
1311 assert!(m.insert(3, 6).is_none());
1312 assert!(m.insert(0, 0).is_none());
1313 assert!(m.insert(4, 8).is_none());
1314 assert!(m.insert(2, 4).is_none());
1315 assert!(m.insert(1, 2).is_none());
1318 m.each_reverse(|k, v| {
1320 assert_eq!(*v, n * 2);
1327 fn test_each_reverse_break() {
1328 let mut m = TrieMap::new();
1330 for x in range(uint::MAX - 10000, uint::MAX).rev() {
1334 let mut n = uint::MAX - 1;
1335 m.each_reverse(|k, v| {
1336 if n == uint::MAX - 5000 { false } else {
1337 assert!(n > uint::MAX - 5000);
1340 assert_eq!(*v, n / 2);
1349 let mut m = TrieMap::new();
1350 assert_eq!(m.insert(1u, 2i), None);
1351 assert_eq!(m.insert(1u, 3i), Some(2));
1352 assert_eq!(m.insert(1u, 4i), Some(3));
1357 let mut m = TrieMap::new();
1359 assert_eq!(m.remove(&1), Some(2));
1360 assert_eq!(m.remove(&1), None);
1364 fn test_from_iter() {
1365 let xs = vec![(1u, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1367 let map: TrieMap<int> = xs.iter().map(|&x| x).collect();
1369 for &(k, v) in xs.iter() {
1370 assert_eq!(map.get(&k), Some(&v));
1376 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1377 let map = vec.into_iter().collect::<TrieMap<char>>();
1378 let keys = map.keys().collect::<Vec<uint>>();
1379 assert_eq!(keys.len(), 3);
1380 assert!(keys.contains(&1));
1381 assert!(keys.contains(&2));
1382 assert!(keys.contains(&3));
1387 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1388 let map = vec.into_iter().collect::<TrieMap<char>>();
1389 let values = map.values().map(|&v| v).collect::<Vec<char>>();
1390 assert_eq!(values.len(), 3);
1391 assert!(values.contains(&'a'));
1392 assert!(values.contains(&'b'));
1393 assert!(values.contains(&'c'));
1397 fn test_iteration() {
1398 let empty_map : TrieMap<uint> = TrieMap::new();
1399 assert_eq!(empty_map.iter().next(), None);
1401 let first = uint::MAX - 10000;
1402 let last = uint::MAX;
1404 let mut map = TrieMap::new();
1405 for x in range(first, last).rev() {
1406 map.insert(x, x / 2);
1410 for (k, &v) in map.iter() {
1411 assert_eq!(k, first + i);
1412 assert_eq!(v, k / 2);
1415 assert_eq!(i, last - first);
1419 fn test_mut_iter() {
1420 let mut empty_map : TrieMap<uint> = TrieMap::new();
1421 assert!(empty_map.iter_mut().next().is_none());
1423 let first = uint::MAX - 10000;
1424 let last = uint::MAX;
1426 let mut map = TrieMap::new();
1427 for x in range(first, last).rev() {
1428 map.insert(x, x / 2);
1432 for (k, v) in map.iter_mut() {
1433 assert_eq!(k, first + i);
1437 assert_eq!(i, last - first);
1439 assert!(map.iter().all(|(_, &v)| v == 0));
1444 let empty_map : TrieMap<uint> = TrieMap::new();
1445 assert_eq!(empty_map.lower_bound(0).next(), None);
1446 assert_eq!(empty_map.upper_bound(0).next(), None);
1452 let mut map : TrieMap<uint> = TrieMap::new();
1453 for x in range_step(0u, last, step) {
1454 assert!(x % step == 0);
1455 map.insert(x, value);
1458 for i in range(0u, last - step) {
1459 let mut lb = map.lower_bound(i);
1460 let mut ub = map.upper_bound(i);
1461 let next_key = i - i % step + step;
1462 let next_pair = (next_key, &value);
1464 assert_eq!(lb.next(), Some((i, &value)));
1466 assert_eq!(lb.next(), Some(next_pair));
1468 assert_eq!(ub.next(), Some(next_pair));
1471 let mut lb = map.lower_bound(last - step);
1472 assert_eq!(lb.next(), Some((last - step, &value)));
1473 let mut ub = map.upper_bound(last - step);
1474 assert_eq!(ub.next(), None);
1476 for i in range(last - step + 1, last) {
1477 let mut lb = map.lower_bound(i);
1478 assert_eq!(lb.next(), None);
1479 let mut ub = map.upper_bound(i);
1480 assert_eq!(ub.next(), None);
1485 fn test_mut_bound() {
1486 let empty_map : TrieMap<uint> = TrieMap::new();
1487 assert_eq!(empty_map.lower_bound(0).next(), None);
1488 assert_eq!(empty_map.upper_bound(0).next(), None);
1490 let mut m_lower = TrieMap::new();
1491 let mut m_upper = TrieMap::new();
1492 for i in range(0u, 100) {
1493 m_lower.insert(2 * i, 4 * i);
1494 m_upper.insert(2 * i, 4 * i);
1497 for i in range(0u, 199) {
1498 let mut lb_it = m_lower.lower_bound_mut(i);
1499 let (k, v) = lb_it.next().unwrap();
1505 for i in range(0u, 198) {
1506 let mut ub_it = m_upper.upper_bound_mut(i);
1507 let (k, v) = ub_it.next().unwrap();
1508 let ub = i + 2 - i % 2;
1513 assert!(m_lower.lower_bound_mut(199).next().is_none());
1514 assert!(m_upper.upper_bound_mut(198).next().is_none());
1516 assert!(m_lower.iter().all(|(_, &x)| x == 0));
1517 assert!(m_upper.iter().all(|(_, &x)| x == 0));
1522 let mut a = TrieMap::new();
1528 assert!(a.clone() == a);
1533 let mut a = TrieMap::new();
1534 let mut b = TrieMap::new();
1537 assert!(a.insert(0, 5i).is_none());
1539 assert!(b.insert(0, 4i).is_none());
1541 assert!(a.insert(5, 19).is_none());
1543 assert!(!b.insert(0, 5).is_none());
1545 assert!(b.insert(5, 19).is_none());
1551 let mut a = TrieMap::new();
1552 let mut b = TrieMap::new();
1554 assert!(!(a < b) && !(b < a));
1555 assert!(b.insert(2u, 5i).is_none());
1557 assert!(a.insert(2, 7).is_none());
1558 assert!(!(a < b) && b < a);
1559 assert!(b.insert(1, 0).is_none());
1561 assert!(a.insert(0, 6).is_none());
1563 assert!(a.insert(6, 2).is_none());
1564 assert!(a < b && !(b < a));
1569 let mut a = TrieMap::new();
1570 let mut b = TrieMap::new();
1572 assert!(a <= b && a >= b);
1573 assert!(a.insert(1u, 1i).is_none());
1574 assert!(a > b && a >= b);
1575 assert!(b < a && b <= a);
1576 assert!(b.insert(2, 2).is_none());
1577 assert!(b > a && b >= a);
1578 assert!(a < b && a <= b);
1583 let mut x = TrieMap::new();
1584 let mut y = TrieMap::new();
1586 assert!(hash::hash(&x) == hash::hash(&y));
1595 assert!(hash::hash(&x) == hash::hash(&y));
1600 let mut map = TrieMap::new();
1601 let empty: TrieMap<uint> = TrieMap::new();
1606 let map_str = format!("{}", map);
1608 assert!(map_str == "{1: a, 2: b}".to_string());
1609 assert_eq!(format!("{}", empty), "{}".to_string());
1614 let mut map = TrieMap::new();
1620 assert_eq!(map[2], 1);
1625 fn test_index_nonexistent() {
1626 let mut map = TrieMap::new();
1635 // Number of items to insert into the map during entry tests.
1636 // The tests rely on it being even.
1637 const SQUARES_UPPER_LIM: uint = 128;
1639 /// Make a TrieMap storing i^2 for i in [0, 128)
1640 fn squares_map() -> TrieMap<uint> {
1641 let mut map = TrieMap::new();
1642 for i in range(0, SQUARES_UPPER_LIM) {
1643 map.insert(i, i * i);
1649 fn test_entry_get() {
1650 let mut map = squares_map();
1652 for i in range(0, SQUARES_UPPER_LIM) {
1653 match map.entry(i) {
1654 Occupied(slot) => assert_eq!(slot.get(), &(i * i)),
1655 Vacant(_) => panic!("Key not found.")
1658 check_integrity(&map.root);
1662 fn test_entry_get_mut() {
1663 let mut map = squares_map();
1665 // Change the entries to cubes.
1666 for i in range(0, SQUARES_UPPER_LIM) {
1667 match map.entry(i) {
1668 Occupied(mut e) => {
1669 *e.get_mut() = i * i * i;
1671 Vacant(_) => panic!("Key not found.")
1673 assert_eq!(map.get(&i).unwrap(), &(i * i * i));
1676 check_integrity(&map.root);
1680 fn test_entry_into_mut() {
1681 let mut map = TrieMap::new();
1684 let value_ref = match map.entry(3) {
1685 Occupied(e) => e.into_mut(),
1686 Vacant(_) => panic!("Entry not found.")
1689 assert_eq!(*value_ref, 6u);
1693 fn test_entry_take() {
1694 let mut map = squares_map();
1695 assert_eq!(map.len(), SQUARES_UPPER_LIM);
1697 // Remove every odd key, checking that the correct value is returned.
1698 for i in range_step(1, SQUARES_UPPER_LIM, 2) {
1699 match map.entry(i) {
1700 Occupied(e) => assert_eq!(e.take(), i * i),
1701 Vacant(_) => panic!("Key not found.")
1705 check_integrity(&map.root);
1707 // Check that the values for even keys remain unmodified.
1708 for i in range_step(0, SQUARES_UPPER_LIM, 2) {
1709 assert_eq!(map.get(&i).unwrap(), &(i * i));
1712 assert_eq!(map.len(), SQUARES_UPPER_LIM / 2);
1716 fn test_occupied_entry_set() {
1717 let mut map = squares_map();
1719 // Change all the entries to cubes.
1720 for i in range(0, SQUARES_UPPER_LIM) {
1721 match map.entry(i) {
1722 Occupied(mut e) => assert_eq!(e.set(i * i * i), i * i),
1723 Vacant(_) => panic!("Key not found.")
1725 assert_eq!(map.get(&i).unwrap(), &(i * i * i));
1727 check_integrity(&map.root);
1731 fn test_vacant_entry_set() {
1732 let mut map = TrieMap::new();
1734 for i in range(0, SQUARES_UPPER_LIM) {
1735 match map.entry(i) {
1738 let inserted_val = e.set(i * i);
1739 assert_eq!(*inserted_val, i * i);
1741 // Update it to i^3 using the returned mutable reference.
1742 *inserted_val = i * i * i;
1744 _ => panic!("Non-existent key found.")
1746 assert_eq!(map.get(&i).unwrap(), &(i * i * i));
1749 check_integrity(&map.root);
1750 assert_eq!(map.len(), SQUARES_UPPER_LIM);
1754 fn test_single_key() {
1755 let mut map = TrieMap::new();
1758 match map.entry(1) {
1759 Occupied(e) => { e.take(); },
1767 use std::prelude::*;
1768 use std::rand::{weak_rng, Rng};
1769 use test::{Bencher, black_box};
1771 use super::{TrieMap, Occupied, Vacant};
1773 const MAP_SIZE: uint = 1000;
1775 fn random_map(size: uint) -> TrieMap<uint> {
1776 let mut map = TrieMap::<uint>::new();
1777 let mut rng = weak_rng();
1779 for _ in range(0, size) {
1780 map.insert(rng.gen(), rng.gen());
1785 fn bench_iter(b: &mut Bencher, size: uint) {
1786 let map = random_map(size);
1788 for entry in map.iter() {
1795 pub fn iter_20(b: &mut Bencher) {
1800 pub fn iter_1000(b: &mut Bencher) {
1801 bench_iter(b, 1000);
1805 pub fn iter_100000(b: &mut Bencher) {
1806 bench_iter(b, 100000);
1810 fn bench_lower_bound(b: &mut Bencher) {
1811 let mut m = TrieMap::<uint>::new();
1812 let mut rng = weak_rng();
1813 for _ in range(0u, MAP_SIZE) {
1814 m.insert(rng.gen(), rng.gen());
1818 for _ in range(0u, 10) {
1819 m.lower_bound(rng.gen());
1825 fn bench_upper_bound(b: &mut Bencher) {
1826 let mut m = TrieMap::<uint>::new();
1827 let mut rng = weak_rng();
1828 for _ in range(0u, MAP_SIZE) {
1829 m.insert(rng.gen(), rng.gen());
1833 for _ in range(0u, 10) {
1834 m.upper_bound(rng.gen());
1840 fn bench_insert_large(b: &mut Bencher) {
1841 let mut m = TrieMap::<[uint, .. 10]>::new();
1842 let mut rng = weak_rng();
1845 for _ in range(0u, MAP_SIZE) {
1846 m.insert(rng.gen(), [1, .. 10]);
1852 fn bench_insert_large_entry(b: &mut Bencher) {
1853 let mut m = TrieMap::<[uint, .. 10]>::new();
1854 let mut rng = weak_rng();
1857 for _ in range(0u, MAP_SIZE) {
1858 match m.entry(rng.gen()) {
1859 Occupied(mut e) => { e.set([1, ..10]); },
1860 Vacant(e) => { e.set([1, ..10]); }
1867 fn bench_insert_large_low_bits(b: &mut Bencher) {
1868 let mut m = TrieMap::<[uint, .. 10]>::new();
1869 let mut rng = weak_rng();
1872 for _ in range(0u, MAP_SIZE) {
1873 // only have the last few bits set.
1874 m.insert(rng.gen::<uint>() & 0xff_ff, [1, .. 10]);
1880 fn bench_insert_small(b: &mut Bencher) {
1881 let mut m = TrieMap::<()>::new();
1882 let mut rng = weak_rng();
1885 for _ in range(0u, MAP_SIZE) {
1886 m.insert(rng.gen(), ());
1892 fn bench_insert_small_low_bits(b: &mut Bencher) {
1893 let mut m = TrieMap::<()>::new();
1894 let mut rng = weak_rng();
1897 for _ in range(0u, MAP_SIZE) {
1898 // only have the last few bits set.
1899 m.insert(rng.gen::<uint>() & 0xff_ff, ());
1905 fn bench_get(b: &mut Bencher) {
1906 let map = random_map(MAP_SIZE);
1907 let keys: Vec<uint> = map.keys().collect();
1909 for key in keys.iter() {
1910 black_box(map.get(key));
1916 fn bench_get_entry(b: &mut Bencher) {
1917 let mut map = random_map(MAP_SIZE);
1918 let keys: Vec<uint> = map.keys().collect();
1920 for key in keys.iter() {
1921 match map.entry(*key) {
1922 Occupied(e) => { black_box(e.get()); },
1930 fn bench_remove(b: &mut Bencher) {
1932 let mut map = random_map(MAP_SIZE);
1933 let keys: Vec<uint> = map.keys().collect();
1934 for key in keys.iter() {
1935 black_box(map.remove(key));
1941 fn bench_remove_entry(b: &mut Bencher) {
1943 let mut map = random_map(MAP_SIZE);
1944 let keys: Vec<uint> = map.keys().collect();
1945 for key in keys.iter() {
1946 match map.entry(*key) {
1947 Occupied(e) => { black_box(e.take()); },