diff options
Diffstat (limited to 'src/libstd')
| -rw-r--r-- | src/libstd/hashmap.rs | 1422 | ||||
| -rw-r--r-- | src/libstd/io/signal.rs | 21 | ||||
| -rw-r--r-- | src/libstd/lib.rs | 10 | ||||
| -rw-r--r-- | src/libstd/logging.rs | 2 | ||||
| -rw-r--r-- | src/libstd/rt/crate_map.rs | 43 | ||||
| -rw-r--r-- | src/libstd/to_str.rs | 85 | ||||
| -rw-r--r-- | src/libstd/trie.rs | 1047 | ||||
| -rw-r--r-- | src/libstd/vec.rs | 11 |
8 files changed, 47 insertions, 2594 deletions
diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs deleted file mode 100644 index f3783c27b54..00000000000 --- a/src/libstd/hashmap.rs +++ /dev/null @@ -1,1422 +0,0 @@ -// Copyright 2013 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! Unordered containers, implemented as hash-tables (`HashSet` and `HashMap` types) -//! -//! The tables use a keyed hash with new random keys generated for each container, so the ordering -//! of a set of keys in a hash table is randomized. -//! -//! # Example -//! -//! ```rust -//! use std::hashmap::HashMap; -//! -//! // type inference lets us omit an explicit type signature (which -//! // would be `HashMap<&str, &str>` in this example). -//! let mut book_reviews = HashMap::new(); -//! -//! // review some books. -//! book_reviews.insert("Adventures of Hucklebury Fin", "My favorite book."); -//! book_reviews.insert("Grimms' Fairy Tales", "Masterpiece."); -//! book_reviews.insert("Pride and Prejudice", "Very enjoyable."); -//! book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot."); -//! -//! // check for a specific one. -//! if !book_reviews.contains_key(& &"Les Misérables") { -//! println!("We've got {} reviews, but Les Misérables ain't one.", -//! book_reviews.len()); -//! } -//! -//! // oops, this review has a lot of spelling mistakes, let's delete it. -//! book_reviews.remove(& &"The Adventures of Sherlock Holmes"); -//! -//! // look up the values associated with some keys. -//! let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; -//! for book in to_find.iter() { -//! match book_reviews.find(book) { -//! Some(review) => println!("{}: {}", *book, *review), -//! None => println!("{} is unreviewed.", *book) -//! } -//! } -//! -//! // iterate over everything. -//! for (book, review) in book_reviews.iter() { -//! println!("{}: \"{}\"", *book, *review); -//! } -//! ``` - -use container::{Container, Mutable, Map, MutableMap, Set, MutableSet}; -use clone::Clone; -use cmp::{Eq, Equiv, max}; -use default::Default; -use fmt; -use hash_old::Hash; -use iter; -use iter::{Iterator, FromIterator, Extendable}; -use iter::{FilterMap, Chain, Repeat, Zip}; -use mem::replace; -use num; -use option::{None, Option, Some}; -use rand::Rng; -use rand; -use result::{Ok, Err}; -use vec::{ImmutableVector, MutableVector, OwnedVector, Items, MutItems}; -use vec_ng; -use vec_ng::Vec; - -static INITIAL_CAPACITY: uint = 32u; // 2^5 - -struct Bucket<K,V> { - hash: uint, - key: K, - value: V, -} - -/// A hash map implementation which uses linear probing along with the SipHash -/// hash function for internal state. This means that the order of all hash maps -/// is randomized by keying each hash map randomly on creation. -/// -/// It is required that the keys implement the `Eq` and `Hash` traits, although -/// this can frequently be achieved by just implementing the `Eq` and -/// `IterBytes` traits as `Hash` is automatically implemented for types that -/// implement `IterBytes`. -pub struct HashMap<K,V> { - priv k0: u64, - priv k1: u64, - priv resize_at: uint, - priv size: uint, - priv buckets: Vec<Option<Bucket<K, V>>> -} - -// We could rewrite FoundEntry to have type Option<&Bucket<K, V>> -// which would be nifty -enum SearchResult { - FoundEntry(uint), FoundHole(uint), TableFull -} - -#[inline] -fn resize_at(capacity: uint) -> uint { - (capacity * 3) / 4 -} - -impl<K:Hash + Eq,V> HashMap<K, V> { - #[inline] - fn to_bucket(&self, h: uint) -> uint { - // A good hash function with entropy spread over all of the - // bits is assumed. SipHash is more than good enough. - h % self.buckets.len() - } - - #[inline] - fn next_bucket(&self, idx: uint, len_buckets: uint) -> uint { - (idx + 1) % len_buckets - } - - #[inline] - fn bucket_sequence(&self, hash: uint, op: |uint| -> bool) -> bool { - let start_idx = self.to_bucket(hash); - let len_buckets = self.buckets.len(); - let mut idx = start_idx; - loop { - if !op(idx) { return false; } - idx = self.next_bucket(idx, len_buckets); - if idx == start_idx { - return true; - } - } - } - - #[inline] - fn bucket_for_key(&self, k: &K) -> SearchResult { - let hash = k.hash_keyed(self.k0, self.k1) as uint; - self.bucket_for_key_with_hash(hash, k) - } - - #[inline] - fn bucket_for_key_equiv<Q:Hash + Equiv<K>>(&self, k: &Q) - -> SearchResult { - let hash = k.hash_keyed(self.k0, self.k1) as uint; - self.bucket_for_key_with_hash_equiv(hash, k) - } - - #[inline] - fn bucket_for_key_with_hash(&self, - hash: uint, - k: &K) - -> SearchResult { - let mut ret = TableFull; - self.bucket_sequence(hash, |i| { - match self.buckets.as_slice()[i] { - Some(ref bkt) if bkt.hash == hash && *k == bkt.key => { - ret = FoundEntry(i); false - }, - None => { ret = FoundHole(i); false } - _ => true, - } - }); - ret - } - - #[inline] - fn bucket_for_key_with_hash_equiv<Q:Equiv<K>>(&self, - hash: uint, - k: &Q) - -> SearchResult { - let mut ret = TableFull; - self.bucket_sequence(hash, |i| { - match self.buckets.as_slice()[i] { - Some(ref bkt) if bkt.hash == hash && k.equiv(&bkt.key) => { - ret = FoundEntry(i); false - }, - None => { ret = FoundHole(i); false } - _ => true, - } - }); - ret - } - - /// Expand the capacity of the array to the next power of two - /// and re-insert each of the existing buckets. - #[inline] - fn expand(&mut self) { - let new_capacity = self.buckets.len() * 2; - self.resize(new_capacity); - } - - /// Expands the capacity of the array and re-insert each of the - /// existing buckets. - fn resize(&mut self, new_capacity: uint) { - self.resize_at = resize_at(new_capacity); - - let old_buckets = replace(&mut self.buckets, - Vec::from_fn(new_capacity, |_| None)); - - self.size = 0; - for bucket in old_buckets.move_iter() { - self.insert_opt_bucket(bucket); - } - } - - fn insert_opt_bucket(&mut self, bucket: Option<Bucket<K, V>>) { - match bucket { - Some(Bucket{hash: hash, key: key, value: value}) => { - self.insert_internal(hash, key, value); - } - None => {} - } - } - - #[inline] - fn value_for_bucket<'a>(&'a self, idx: uint) -> &'a V { - match self.buckets.as_slice()[idx] { - Some(ref bkt) => &bkt.value, - None => fail!("HashMap::find: internal logic error"), - } - } - - #[inline] - fn mut_value_for_bucket<'a>(&'a mut self, idx: uint) -> &'a mut V { - match self.buckets.as_mut_slice()[idx] { - Some(ref mut bkt) => &mut bkt.value, - None => unreachable!() - } - } - - /// Inserts the key value pair into the buckets. - /// Assumes that there will be a bucket. - /// True if there was no previous entry with that key - fn insert_internal(&mut self, hash: uint, k: K, v: V) -> Option<V> { - match self.bucket_for_key_with_hash(hash, &k) { - TableFull => { fail!("Internal logic error"); } - FoundHole(idx) => { - self.buckets.as_mut_slice()[idx] = Some(Bucket{hash: hash, key: k, value: v}); - self.size += 1; - None - } - FoundEntry(idx) => { - match self.buckets.as_mut_slice()[idx] { - None => { fail!("insert_internal: Internal logic error") } - Some(ref mut b) => { - b.hash = hash; - b.key = k; - Some(replace(&mut b.value, v)) - } - } - } - } - } - - fn pop_internal(&mut self, hash: uint, k: &K) -> Option<V> { - // Removing from an open-addressed hashtable - // is, well, painful. The problem is that - // the entry may lie on the probe path for other - // entries, so removing it would make you think that - // those probe paths are empty. - // - // To address this we basically have to keep walking, - // re-inserting entries we find until we reach an empty - // bucket. We know we will eventually reach one because - // we insert one ourselves at the beginning (the removed - // entry). - // - // I found this explanation elucidating: - // http://www.maths.lse.ac.uk/Courses/MA407/del-hash.pdf - let mut idx = match self.bucket_for_key_with_hash(hash, k) { - TableFull | FoundHole(_) => return None, - FoundEntry(idx) => idx - }; - - let len_buckets = self.buckets.len(); - let bucket = self.buckets.as_mut_slice()[idx].take(); - - let value = bucket.map(|bucket| bucket.value); - - /* re-inserting buckets may cause changes in size, so remember - what our new size is ahead of time before we start insertions */ - let size = self.size - 1; - idx = self.next_bucket(idx, len_buckets); - while self.buckets.as_slice()[idx].is_some() { - let bucket = self.buckets.as_mut_slice()[idx].take(); - self.insert_opt_bucket(bucket); - idx = self.next_bucket(idx, len_buckets); - } - self.size = size; - - value - } -} - -impl<K:Hash + Eq,V> Container for HashMap<K, V> { - /// Return the number of elements in the map - fn len(&self) -> uint { self.size } -} - -impl<K:Hash + Eq,V> Mutable for HashMap<K, V> { - /// Clear the map, removing all key-value pairs. - fn clear(&mut self) { - for bkt in self.buckets.as_mut_slice().mut_iter() { - *bkt = None; - } - self.size = 0; - } -} - -impl<K:Hash + Eq,V> Map<K, V> for HashMap<K, V> { - /// Return a reference to the value corresponding to the key - fn find<'a>(&'a self, k: &K) -> Option<&'a V> { - match self.bucket_for_key(k) { - FoundEntry(idx) => Some(self.value_for_bucket(idx)), - TableFull | FoundHole(_) => None, - } - } -} - -impl<K:Hash + Eq,V> MutableMap<K, V> for HashMap<K, V> { - /// Return a mutable reference to the value corresponding to the key - fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> { - let idx = match self.bucket_for_key(k) { - FoundEntry(idx) => idx, - TableFull | FoundHole(_) => return None - }; - Some(self.mut_value_for_bucket(idx)) - } - - /// Insert a key-value pair from the map. If the key already had a value - /// present in the map, that value is returned. Otherwise None is returned. - fn swap(&mut self, k: K, v: V) -> Option<V> { - // this could be faster. - - if self.size >= self.resize_at { - // n.b.: We could also do this after searching, so - // that we do not resize if this call to insert is - // simply going to update a key in place. My sense - // though is that it's worse to have to search through - // buckets to find the right spot twice than to just - // resize in this corner case. - self.expand(); - } - - let hash = k.hash_keyed(self.k0, self.k1) as uint; - self.insert_internal(hash, k, v) - } - - /// Removes a key from the map, returning the value at the key if the key - /// was previously in the map. - fn pop(&mut self, k: &K) -> Option<V> { - let hash = k.hash_keyed(self.k0, self.k1) as uint; - self.pop_internal(hash, k) - } -} - -impl<K: Hash + Eq, V> HashMap<K, V> { - /// Create an empty HashMap - pub fn new() -> HashMap<K, V> { - HashMap::with_capacity(INITIAL_CAPACITY) - } - - /// Create an empty HashMap with space for at least `capacity` - /// elements in the hash table. - pub fn with_capacity(capacity: uint) -> HashMap<K, V> { - let mut r = rand::task_rng(); - HashMap::with_capacity_and_keys(r.gen(), r.gen(), capacity) - } - - /// Create an empty HashMap with space for at least `capacity` - /// elements, using `k0` and `k1` as the keys. - /// - /// Warning: `k0` and `k1` are normally randomly generated, and - /// are designed to allow HashMaps to be resistant to attacks that - /// cause many collisions and very poor performance. Setting them - /// manually using this function can expose a DoS attack vector. - pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashMap<K, V> { - let cap = max(INITIAL_CAPACITY, capacity); - HashMap { - k0: k0, k1: k1, - resize_at: resize_at(cap), - size: 0, - buckets: Vec::from_fn(cap, |_| None) - } - } - - /// Reserve space for at least `n` elements in the hash table. - pub fn reserve(&mut self, n: uint) { - if n > self.buckets.len() { - let buckets = n * 4 / 3 + 1; - self.resize(num::next_power_of_two(buckets)); - } - } - - /// Modify and return the value corresponding to the key in the map, or - /// insert and return a new value if it doesn't exist. - /// - /// This method allows for all insertion behaviours of a hashmap, - /// see methods like `insert`, `find_or_insert` and - /// `insert_or_update_with` for less general and more friendly - /// variations of this. - /// - /// # Example - /// - /// ```rust - /// use std::hashmap::HashMap; - /// - /// // map some strings to vectors of strings - /// let mut map = HashMap::<~str, ~[~str]>::new(); - /// map.insert(~"a key", ~[~"value"]); - /// map.insert(~"z key", ~[~"value"]); - /// - /// let new = ~[~"a key", ~"b key", ~"z key"]; - /// for k in new.move_iter() { - /// map.mangle(k, ~"new value", - /// // if the key doesn't exist in the map yet, add it in - /// // the obvious way. - /// |_k, v| ~[v], - /// // if the key does exist either prepend or append this - /// // new value based on the first letter of the key. - /// |key, already, new| { - /// if key.starts_with("z") { - /// already.unshift(new); - /// } else { - /// already.push(new); - /// } - /// }); - /// } - /// - /// for (k, v) in map.iter() { - /// println!("{} -> {:?}", *k, *v); - /// } - /// ``` - pub fn mangle<'a, - A>( - &'a mut self, - k: K, - a: A, - not_found: |&K, A| -> V, - found: |&K, &mut V, A|) - -> &'a mut V { - if self.size >= self.resize_at { - // n.b.: We could also do this after searching, so - // that we do not resize if this call to insert is - // simply going to update a key in place. My sense - // though is that it's worse to have to search through - // buckets to find the right spot twice than to just - // resize in this corner case. - self.expand(); - } - - let hash = k.hash_keyed(self.k0, self.k1) as uint; - let idx = match self.bucket_for_key_with_hash(hash, &k) { - TableFull => fail!("Internal logic error"), - FoundEntry(idx) => { found(&k, self.mut_value_for_bucket(idx), a); idx } - FoundHole(idx) => { - let v = not_found(&k, a); - self.buckets.as_mut_slice()[idx] = Some(Bucket{hash: hash, key: k, value: v}); - self.size += 1; - idx - } - }; - - self.mut_value_for_bucket(idx) - } - - /// Return the value corresponding to the key in the map, or insert - /// and return the value if it doesn't exist. - pub fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a mut V { - self.mangle(k, v, |_k, a| a, |_k,_v,_a| ()) - } - - /// Return the value corresponding to the key in the map, or create, - /// insert, and return a new value if it doesn't exist. - pub fn find_or_insert_with<'a>(&'a mut self, k: K, f: |&K| -> V) - -> &'a mut V { - self.mangle(k, (), |k,_a| f(k), |_k,_v,_a| ()) - } - - /// Insert a key-value pair into the map if the key is not already present. - /// Otherwise, modify the existing value for the key. - /// Returns the new or modified value for the key. - pub fn insert_or_update_with<'a>( - &'a mut self, - k: K, - v: V, - f: |&K, &mut V|) - -> &'a mut V { - self.mangle(k, v, |_k,a| a, |k,v,_a| f(k,v)) - } - - /// Retrieves a value for the given key, failing if the key is not - /// present. - pub fn get<'a>(&'a self, k: &K) -> &'a V { - match self.find(k) { - Some(v) => v, - None => fail!("No entry found for key: {:?}", k), - } - } - - /// Retrieves a (mutable) value for the given key, failing if the key - /// is not present. - pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V { - match self.find_mut(k) { - Some(v) => v, - None => fail!("No entry found for key: {:?}", k), - } - } - - /// Return true if the map contains a value for the specified key, - /// using equivalence - pub fn contains_key_equiv<Q:Hash + Equiv<K>>(&self, key: &Q) -> bool { - match self.bucket_for_key_equiv(key) { - FoundEntry(_) => {true} - TableFull | FoundHole(_) => {false} - } - } - - /// Return the value corresponding to the key in the map, using - /// equivalence - pub fn find_equiv<'a, Q:Hash + Equiv<K>>(&'a self, k: &Q) - -> Option<&'a V> { - match self.bucket_for_key_equiv(k) { - FoundEntry(idx) => Some(self.value_for_bucket(idx)), - TableFull | FoundHole(_) => None, - } - } - - /// An iterator visiting all keys in arbitrary order. - /// Iterator element type is &'a K. - pub fn keys<'a>(&'a self) -> Keys<'a, K, V> { - self.iter().map(|(k, _v)| k) - } - - /// An iterator visiting all values in arbitrary order. - /// Iterator element type is &'a V. - pub fn values<'a>(&'a self) -> Values<'a, K, V> { - self.iter().map(|(_k, v)| v) - } - - /// An iterator visiting all key-value pairs in arbitrary order. - /// Iterator element type is (&'a K, &'a V). - pub fn iter<'a>(&'a self) -> Entries<'a, K, V> { - Entries { iter: self.buckets.as_slice().iter() } - } - - /// An iterator visiting all key-value pairs in arbitrary order, - /// with mutable references to the values. - /// Iterator element type is (&'a K, &'a mut V). - pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> { - MutEntries { iter: self.buckets.as_mut_slice().mut_iter() } - } - - /// Creates a consuming iterator, that is, one that moves each key-value - /// pair out of the map in arbitrary order. The map cannot be used after - /// calling this. - pub fn move_iter(self) -> MoveEntries<K, V> { - MoveEntries {iter: self.buckets.move_iter()} - } -} - -impl<K: Hash + Eq, V: Clone> HashMap<K, V> { - /// Like `find`, but returns a copy of the value. - pub fn find_copy(&self, k: &K) -> Option<V> { - self.find(k).map(|v| (*v).clone()) - } - - /// Like `get`, but returns a copy of the value. - pub fn get_copy(&self, k: &K) -> V { - (*self.get(k)).clone() - } -} - -impl<K:Hash + Eq,V:Eq> Eq for HashMap<K, V> { - fn eq(&self, other: &HashMap<K, V>) -> bool { - if self.len() != other.len() { return false; } - - self.iter().all(|(key, value)| { - match other.find(key) { - None => false, - Some(v) => value == v - } - }) - } - - fn ne(&self, other: &HashMap<K, V>) -> bool { !self.eq(other) } -} - -impl<K:Hash + Eq + Clone,V:Clone> Clone for HashMap<K,V> { - fn clone(&self) -> HashMap<K,V> { - let mut new_map = HashMap::with_capacity(self.len()); - for (key, value) in self.iter() { - new_map.insert((*key).clone(), (*value).clone()); - } - new_map - } -} - -impl<A: fmt::Show + Hash + Eq, B: fmt::Show> fmt::Show for HashMap<A, B> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - try!(write!(f.buf, r"\{")) - let mut first = true; - for (key, value) in self.iter() { - if first { - first = false; - } else { - try!(write!(f.buf, ", ")); - } - try!(write!(f.buf, "{}: {}", *key, *value)); - } - write!(f.buf, r"\}") - } -} - -/// HashMap iterator -#[deriving(Clone)] -pub struct Entries<'a, K, V> { - priv iter: Items<'a, Option<Bucket<K, V>>>, -} - -/// HashMap mutable values iterator -pub struct MutEntries<'a, K, V> { - priv iter: MutItems<'a, Option<Bucket<K, V>>>, -} - -/// HashMap move iterator -pub struct MoveEntries<K, V> { - priv iter: vec_ng::MoveItems<Option<Bucket<K, V>>>, -} - -/// HashMap keys iterator -pub type Keys<'a, K, V> = - iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>; - -/// HashMap values iterator -pub type Values<'a, K, V> = - iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>; - -/// HashSet iterator -#[deriving(Clone)] -pub struct SetItems<'a, K> { - priv iter: Items<'a, Option<Bucket<K, ()>>>, -} - -/// HashSet move iterator -pub struct SetMoveItems<K> { - priv iter: vec_ng::MoveItems<Option<Bucket<K, ()>>>, -} - -impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> { - #[inline] - fn next(&mut self) -> Option<(&'a K, &'a V)> { - for elt in self.iter { - match elt { - &Some(ref bucket) => return Some((&bucket.key, &bucket.value)), - &None => {}, - } - } - None - } -} - -impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> { - #[inline] - fn next(&mut self) -> Option<(&'a K, &'a mut V)> { - for elt in self.iter { - match elt { - &Some(ref mut bucket) => return Some((&bucket.key, &mut bucket.value)), - &None => {}, - } - } - None - } -} - -impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> { - #[inline] - fn next(&mut self) -> Option<(K, V)> { - for elt in self.iter { - match elt { - Some(Bucket {key, value, ..}) => return Some((key, value)), - None => {}, - } - } - None - } -} - -impl<'a, K> Iterator<&'a K> for SetItems<'a, K> { - #[inline] - fn next(&mut self) -> Option<&'a K> { - for elt in self.iter { - match elt { - &Some(ref bucket) => return Some(&bucket.key), - &None => {}, - } - } - None - } -} - -impl<K> Iterator<K> for SetMoveItems<K> { - #[inline] - fn next(&mut self) -> Option<K> { - for elt in self.iter { - match elt { - Some(bucket) => return Some(bucket.key), - None => {}, - } - } - None - } -} - -impl<K: Eq + Hash, V> FromIterator<(K, V)> for HashMap<K, V> { - fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> HashMap<K, V> { - let (lower, _) = iter.size_hint(); - let mut map = HashMap::with_capacity(lower); - map.extend(iter); - map - } -} - -impl<K: Eq + Hash, V> Extendable<(K, V)> for HashMap<K, V> { - fn extend<T: Iterator<(K, V)>>(&mut self, iter: &mut T) { - for (k, v) in *iter { - self.insert(k, v); - } - } -} - -impl<K: Eq + Hash, V> Default for HashMap<K, V> { - fn default() -> HashMap<K, V> { HashMap::new() } -} - -/// An implementation of a hash set using the underlying representation of a -/// HashMap where the value is (). As with the `HashMap` type, a `HashSet` -/// requires that the elements implement the `Eq` and `Hash` traits. -pub struct HashSet<T> { - priv map: HashMap<T, ()> -} - -impl<T:Hash + Eq> Eq for HashSet<T> { - fn eq(&self, other: &HashSet<T>) -> bool { self.map == other.map } - fn ne(&self, other: &HashSet<T>) -> bool { self.map != other.map } -} - -impl<T:Hash + Eq> Container for HashSet<T> { - /// Return the number of elements in the set - fn len(&self) -> uint { self.map.len() } -} - -impl<T:Hash + Eq> Mutable for HashSet<T> { - /// Clear the set, removing all values. - fn clear(&mut self) { self.map.clear() } -} - -impl<T:Hash + Eq> Set<T> for HashSet<T> { - /// Return true if the set contains a value - fn contains(&self, value: &T) -> bool { self.map.contains_key(value) } - - /// Return true if the set has no elements in common with `other`. - /// This is equivalent to checking for an empty intersection. - fn is_disjoint(&self, other: &HashSet<T>) -> bool { - self.iter().all(|v| !other.contains(v)) - } - - /// Return true if the set is a subset of another - fn is_subset(&self, other: &HashSet<T>) -> bool { - self.iter().all(|v| other.contains(v)) - } - - /// Return true if the set is a superset of another - fn is_superset(&self, other: &HashSet<T>) -> bool { - other.is_subset(self) - } -} - -impl<T:Hash + Eq> MutableSet<T> for HashSet<T> { - /// Add a value to the set. Return true if the value was not already - /// present in the set. - fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) } - - /// Remove a value from the set. Return true if the value was - /// present in the set. - fn remove(&mut self, value: &T) -> bool { self.map.remove(value) } -} - -impl<T:Hash + Eq> HashSet<T> { - /// Create an empty HashSet - pub fn new() -> HashSet<T> { - HashSet::with_capacity(INITIAL_CAPACITY) - } - - /// Create an empty HashSet with space for at least `n` elements in - /// the hash table. - pub fn with_capacity(capacity: uint) -> HashSet<T> { - HashSet { map: HashMap::with_capacity(capacity) } - } - - /// Create an empty HashSet with space for at least `capacity` - /// elements in the hash table, using `k0` and `k1` as the keys. - /// - /// Warning: `k0` and `k1` are normally randomly generated, and - /// are designed to allow HashSets to be resistant to attacks that - /// cause many collisions and very poor performance. Setting them - /// manually using this function can expose a DoS attack vector. - pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashSet<T> { - HashSet { map: HashMap::with_capacity_and_keys(k0, k1, capacity) } - } - - /// Reserve space for at least `n` elements in the hash table. - pub fn reserve(&mut self, n: uint) { - self.map.reserve(n) - } - - /// Returns true if the hash set contains a value equivalent to the - /// given query value. - pub fn contains_equiv<Q:Hash + Equiv<T>>(&self, value: &Q) -> bool { - self.map.contains_key_equiv(value) - } - - /// An iterator visiting all elements in arbitrary order. - /// Iterator element type is &'a T. - pub fn iter<'a>(&'a self) -> SetItems<'a, T> { - SetItems { iter: self.map.buckets.as_slice().iter() } - } - - /// Creates a consuming iterator, that is, one that moves each value out - /// of the set in arbitrary order. The set cannot be used after calling - /// this. - pub fn move_iter(self) -> SetMoveItems<T> { - SetMoveItems {iter: self.map.buckets.move_iter()} - } - - /// Visit the values representing the difference - pub fn difference<'a>(&'a self, other: &'a HashSet<T>) -> SetAlgebraItems<'a, T> { - Repeat::new(other) - .zip(self.iter()) - .filter_map(|(other, elt)| { - if !other.contains(elt) { Some(elt) } else { None } - }) - } - - /// Visit the values representing the symmetric difference - pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T>) - -> Chain<SetAlgebraItems<'a, T>, SetAlgebraItems<'a, T>> { - self.difference(other).chain(other.difference(self)) - } - - /// Visit the values representing the intersection - pub fn intersection<'a>(&'a self, other: &'a HashSet<T>) - -> SetAlgebraItems<'a, T> { - Repeat::new(other) - .zip(self.iter()) - .filter_map(|(other, elt)| { - if other.contains(elt) { Some(elt) } else { None } - }) - } - - /// Visit the values representing the union - pub fn union<'a>(&'a self, other: &'a HashSet<T>) - -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T>> { - self.iter().chain(other.difference(self)) - } - -} - -impl<T:Hash + Eq + Clone> Clone for HashSet<T> { - fn clone(&self) -> HashSet<T> { - HashSet { - map: self.map.clone() - } - } -} - -impl<A: fmt::Show + Hash + Eq> fmt::Show for HashSet<A> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - try!(write!(f.buf, r"\{")) - let mut first = true; - for x in self.iter() { - if first { - first = false; - } else { - try!(write!(f.buf, ", ")); - } - try!(write!(f.buf, "{}", *x)); - } - write!(f.buf, r"\}") - } -} - -impl<K: Eq + Hash> FromIterator<K> for HashSet<K> { - fn from_iterator<T: Iterator<K>>(iter: &mut T) -> HashSet<K> { - let (lower, _) = iter.size_hint(); - let mut set = HashSet::with_capacity(lower); - set.extend(iter); - set - } -} - -impl<K: Eq + Hash> Extendable<K> for HashSet<K> { - fn extend<T: Iterator<K>>(&mut self, iter: &mut T) { - for k in *iter { - self.insert(k); - } - } -} - -impl<K: Eq + Hash> Default for HashSet<K> { - fn default() -> HashSet<K> { HashSet::new() } -} - -// `Repeat` is used to feed the filter closure an explicit capture -// of a reference to the other set -/// Set operations iterator -pub type SetAlgebraItems<'a, T> = - FilterMap<'static,(&'a HashSet<T>, &'a T), &'a T, - Zip<Repeat<&'a HashSet<T>>,SetItems<'a,T>>>; - - -#[cfg(test)] -mod test_map { - use prelude::*; - use super::*; - use fmt; - - #[test] - fn test_create_capacity_zero() { - let mut m = HashMap::with_capacity(0); - assert!(m.insert(1, 1)); - } - - #[test] - fn test_insert() { - let mut m = HashMap::new(); - assert!(m.insert(1, 2)); - assert!(m.insert(2, 4)); - assert_eq!(*m.get(&1), 2); - assert_eq!(*m.get(&2), 4); - } - - #[test] - fn test_find_mut() { - let mut m = HashMap::new(); - assert!(m.insert(1, 12)); - assert!(m.insert(2, 8)); - assert!(m.insert(5, 14)); - let new = 100; - match m.find_mut(&5) { - None => fail!(), Some(x) => *x = new - } - assert_eq!(m.find(&5), Some(&new)); - } - - #[test] - fn test_insert_overwrite() { - let mut m = HashMap::new(); - assert!(m.insert(1, 2)); - assert_eq!(*m.get(&1), 2); - assert!(!m.insert(1, 3)); - assert_eq!(*m.get(&1), 3); - } - - #[test] - fn test_insert_conflicts() { - let mut m = HashMap::with_capacity(4); - assert!(m.insert(1, 2)); - assert!(m.insert(5, 3)); - assert!(m.insert(9, 4)); - assert_eq!(*m.get(&9), 4); - assert_eq!(*m.get(&5), 3); - assert_eq!(*m.get(&1), 2); - } - - #[test] - fn test_conflict_remove() { - let mut m = HashMap::with_capacity(4); - assert!(m.insert(1, 2)); - assert!(m.insert(5, 3)); - assert!(m.insert(9, 4)); - assert!(m.remove(&1)); - assert_eq!(*m.get(&9), 4); - assert_eq!(*m.get(&5), 3); - } - - #[test] - fn test_is_empty() { - let mut m = HashMap::with_capacity(4); - assert!(m.insert(1, 2)); - assert!(!m.is_empty()); - assert!(m.remove(&1)); - assert!(m.is_empty()); - } - - #[test] - fn test_pop() { - let mut m = HashMap::new(); - m.insert(1, 2); - assert_eq!(m.pop(&1), Some(2)); - assert_eq!(m.pop(&1), None); - } - - #[test] - fn test_swap() { - let mut m = HashMap::new(); - assert_eq!(m.swap(1, 2), None); - assert_eq!(m.swap(1, 3), Some(2)); - assert_eq!(m.swap(1, 4), Some(3)); - } - - #[test] - fn test_find_or_insert() { - let mut m: HashMap<int,int> = HashMap::new(); - assert_eq!(*m.find_or_insert(1, 2), 2); - assert_eq!(*m.find_or_insert(1, 3), 2); - } - - #[test] - fn test_find_or_insert_with() { - let mut m: HashMap<int,int> = HashMap::new(); - assert_eq!(*m.find_or_insert_with(1, |_| 2), 2); - assert_eq!(*m.find_or_insert_with(1, |_| 3), 2); - } - - #[test] - fn test_insert_or_update_with() { - let mut m: HashMap<int,int> = HashMap::new(); - assert_eq!(*m.insert_or_update_with(1, 2, |_,x| *x+=1), 2); - assert_eq!(*m.insert_or_update_with(1, 2, |_,x| *x+=1), 3); - } - - #[test] - fn test_move_iter() { - let hm = { - let mut hm = HashMap::new(); - - hm.insert('a', 1); - hm.insert('b', 2); - - hm - }; - - let v = hm.move_iter().collect::<~[(char, int)]>(); - assert!([('a', 1), ('b', 2)] == v || [('b', 2), ('a', 1)] == v); - } - - #[test] - fn test_iterate() { - let mut m = HashMap::with_capacity(4); - for i in range(0u, 32) { - assert!(m.insert(i, i*2)); - } - let mut observed = 0; - for (k, v) in m.iter() { - assert_eq!(*v, *k * 2); - observed |= (1 << *k); - } - assert_eq!(observed, 0xFFFF_FFFF); - } - - #[test] - fn test_keys() { - let vec = ~[(1, 'a'), (2, 'b'), (3, 'c')]; - let map = vec.move_iter().collect::<HashMap<int, char>>(); - let keys = map.keys().map(|&k| k).collect::<~[int]>(); - assert_eq!(keys.len(), 3); - assert!(keys.contains(&1)); - assert!(keys.contains(&2)); - assert!(keys.contains(&3)); - } - - #[test] - fn test_values() { - let vec = ~[(1, 'a'), (2, 'b'), (3, 'c')]; - let map = vec.move_iter().collect::<HashMap<int, char>>(); - let values = map.values().map(|&v| v).collect::<~[char]>(); - assert_eq!(values.len(), 3); - assert!(values.contains(&'a')); - assert!(values.contains(&'b')); - assert!(values.contains(&'c')); - } - - #[test] - fn test_find() { - let mut m = HashMap::new(); - assert!(m.find(&1).is_none()); - m.insert(1, 2); - match m.find(&1) { - None => fail!(), - Some(v) => assert!(*v == 2) - } - } - - #[test] - fn test_eq() { - let mut m1 = HashMap::new(); - m1.insert(1, 2); - m1.insert(2, 3); - m1.insert(3, 4); - - let mut m2 = HashMap::new(); - m2.insert(1, 2); - m2.insert(2, 3); - - assert!(m1 != m2); - - m2.insert(3, 4); - - assert_eq!(m1, m2); - } - - #[test] - fn test_expand() { - let mut m = HashMap::new(); - - assert_eq!(m.len(), 0); - assert!(m.is_empty()); - - let mut i = 0u; - let old_resize_at = m.resize_at; - while old_resize_at == m.resize_at { - m.insert(i, i); - i += 1; - } - - assert_eq!(m.len(), i); - assert!(!m.is_empty()); - } - - #[test] - fn test_find_equiv() { - let mut m = HashMap::new(); - - let (foo, bar, baz) = (1,2,3); - m.insert(~"foo", foo); - m.insert(~"bar", bar); - m.insert(~"baz", baz); - - - assert_eq!(m.find_equiv(&("foo")), Some(&foo)); - assert_eq!(m.find_equiv(&("bar")), Some(&bar)); - assert_eq!(m.find_equiv(&("baz")), Some(&baz)); - - assert_eq!(m.find_equiv(&("qux")), None); - } - - #[test] - fn test_from_iter() { - let xs = ~[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - - let map: HashMap<int, int> = xs.iter().map(|&x| x).collect(); - - for &(k, v) in xs.iter() { - assert_eq!(map.find(&k), Some(&v)); - } - } - - struct ShowableStruct { - value: int, - } - - impl fmt::Show for ShowableStruct { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - write!(f.buf, r"s{}", self.value) - } - } - - #[test] - fn test_show() { - let mut table: HashMap<int, ShowableStruct> = HashMap::new(); - let empty: HashMap<int, ShowableStruct> = HashMap::new(); - - table.insert(3, ShowableStruct { value: 4 }); - table.insert(1, ShowableStruct { value: 2 }); - - let table_str = format!("{}", table); - - assert!(table_str == ~"{1: s2, 3: s4}" || table_str == ~"{3: s4, 1: s2}"); - assert_eq!(format!("{}", empty), ~"{}"); - } -} - -#[cfg(test)] -mod test_set { - use super::*; - use prelude::*; - use container::Container; - use vec::ImmutableEqVector; - - #[test] - fn test_disjoint() { - let mut xs = HashSet::new(); - let mut ys = HashSet::new(); - assert!(xs.is_disjoint(&ys)); - assert!(ys.is_disjoint(&xs)); - assert!(xs.insert(5)); - assert!(ys.insert(11)); - assert!(xs.is_disjoint(&ys)); - assert!(ys.is_disjoint(&xs)); - assert!(xs.insert(7)); - assert!(xs.insert(19)); - assert!(xs.insert(4)); - assert!(ys.insert(2)); - assert!(ys.insert(-11)); - assert!(xs.is_disjoint(&ys)); - assert!(ys.is_disjoint(&xs)); - assert!(ys.insert(7)); - assert!(!xs.is_disjoint(&ys)); - assert!(!ys.is_disjoint(&xs)); - } - - #[test] - fn test_subset_and_superset() { - let mut a = HashSet::new(); - assert!(a.insert(0)); - assert!(a.insert(5)); - assert!(a.insert(11)); - assert!(a.insert(7)); - - let mut b = HashSet::new(); - assert!(b.insert(0)); - assert!(b.insert(7)); - assert!(b.insert(19)); - assert!(b.insert(250)); - assert!(b.insert(11)); - assert!(b.insert(200)); - - assert!(!a.is_subset(&b)); - assert!(!a.is_superset(&b)); - assert!(!b.is_subset(&a)); - assert!(!b.is_superset(&a)); - - assert!(b.insert(5)); - - assert!(a.is_subset(&b)); - assert!(!a.is_superset(&b)); - assert!(!b.is_subset(&a)); - assert!(b.is_superset(&a)); - } - - #[test] - fn test_iterate() { - let mut a = HashSet::new(); - for i in range(0u, 32) { - assert!(a.insert(i)); - } - let mut observed = 0; - for k in a.iter() { - observed |= (1 << *k); - } - assert_eq!(observed, 0xFFFF_FFFF); - } - - #[test] - fn test_intersection() { - let mut a = HashSet::new(); - let mut b = HashSet::new(); - - assert!(a.insert(11)); - assert!(a.insert(1)); - assert!(a.insert(3)); - assert!(a.insert(77)); - assert!(a.insert(103)); - assert!(a.insert(5)); - assert!(a.insert(-5)); - - assert!(b.insert(2)); - assert!(b.insert(11)); - assert!(b.insert(77)); - assert!(b.insert(-9)); - assert!(b.insert(-42)); - assert!(b.insert(5)); - assert!(b.insert(3)); - - let mut i = 0; - let expected = [3, 5, 11, 77]; - for x in a.intersection(&b) { - assert!(expected.contains(x)); - i += 1 - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_difference() { - let mut a = HashSet::new(); - let mut b = HashSet::new(); - - assert!(a.insert(1)); - assert!(a.insert(3)); - assert!(a.insert(5)); - assert!(a.insert(9)); - assert!(a.insert(11)); - - assert!(b.insert(3)); - assert!(b.insert(9)); - - let mut i = 0; - let expected = [1, 5, 11]; - for x in a.difference(&b) { - assert!(expected.contains(x)); - i += 1 - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_symmetric_difference() { - let mut a = HashSet::new(); - let mut b = HashSet::new(); - - assert!(a.insert(1)); - assert!(a.insert(3)); - assert!(a.insert(5)); - assert!(a.insert(9)); - assert!(a.insert(11)); - - assert!(b.insert(-2)); - assert!(b.insert(3)); - assert!(b.insert(9)); - assert!(b.insert(14)); - assert!(b.insert(22)); - - let mut i = 0; - let expected = [-2, 1, 5, 11, 14, 22]; - for x in a.symmetric_difference(&b) { - assert!(expected.contains(x)); - i += 1 - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_union() { - let mut a = HashSet::new(); - let mut b = HashSet::new(); - - assert!(a.insert(1)); - assert!(a.insert(3)); - assert!(a.insert(5)); - assert!(a.insert(9)); - assert!(a.insert(11)); - assert!(a.insert(16)); - assert!(a.insert(19)); - assert!(a.insert(24)); - - assert!(b.insert(-2)); - assert!(b.insert(1)); - assert!(b.insert(5)); - assert!(b.insert(9)); - assert!(b.insert(13)); - assert!(b.insert(19)); - - let mut i = 0; - let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]; - for x in a.union(&b) { - assert!(expected.contains(x)); - i += 1 - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_from_iter() { - let xs = ~[1, 2, 3, 4, 5, 6, 7, 8, 9]; - - let set: HashSet<int> = xs.iter().map(|&x| x).collect(); - - for x in xs.iter() { - assert!(set.contains(x)); - } - } - - #[test] - fn test_move_iter() { - let hs = { - let mut hs = HashSet::new(); - - hs.insert('a'); - hs.insert('b'); - - hs - }; - - let v = hs.move_iter().collect::<~[char]>(); - assert!(['a', 'b'] == v || ['b', 'a'] == v); - } - - #[test] - fn test_eq() { - let mut s1 = HashSet::new(); - s1.insert(1); - s1.insert(2); - s1.insert(3); - - let mut s2 = HashSet::new(); - s2.insert(1); - s2.insert(2); - - assert!(s1 != s2); - - s2.insert(3); - - assert_eq!(s1, s2); - } - - #[test] - fn test_show() { - let mut set: HashSet<int> = HashSet::new(); - let empty: HashSet<int> = HashSet::new(); - - set.insert(1); - set.insert(2); - - let set_str = format!("{}", set); - - assert!(set_str == ~"{1, 2}" || set_str == ~"{2, 1}"); - assert_eq!(format!("{}", empty), ~"{}"); - } -} diff --git a/src/libstd/io/signal.rs b/src/libstd/io/signal.rs index 46c106234db..19aff4f70fe 100644 --- a/src/libstd/io/signal.rs +++ b/src/libstd/io/signal.rs @@ -20,12 +20,14 @@ definitions for a number of signals. */ use clone::Clone; -use result::{Ok, Err}; use comm::{Port, Chan}; -use container::{Map, MutableMap}; -use hashmap; use io; +use iter::Iterator; +use mem::drop; +use option::{Some, None}; +use result::{Ok, Err}; use rt::rtio::{IoFactory, LocalIo, RtioSignal}; +use vec::{ImmutableVector, OwnedVector}; #[repr(int)] #[deriving(Eq, IterBytes)] @@ -78,7 +80,7 @@ pub enum Signum { /// ``` pub struct Listener { /// A map from signums to handles to keep the handles in memory - priv handles: hashmap::HashMap<Signum, ~RtioSignal>, + priv handles: ~[(Signum, ~RtioSignal)], /// chan is where all the handles send signums, which are received by /// the clients from port. priv chan: Chan<Signum>, @@ -97,7 +99,7 @@ impl Listener { Listener { chan: chan, port: port, - handles: hashmap::HashMap::new(), + handles: ~[], } } @@ -118,14 +120,14 @@ impl Listener { /// If this function fails to register a signal handler, then an error will /// be returned. pub fn register(&mut self, signum: Signum) -> io::IoResult<()> { - if self.handles.contains_key(&signum) { + if self.handles.iter().any(|&(sig, _)| sig == signum) { return Ok(()); // self is already listening to signum, so succeed } match LocalIo::maybe_raise(|io| { io.signal(signum, self.chan.clone()) }) { Ok(handle) => { - self.handles.insert(signum, handle); + self.handles.push((signum, handle)); Ok(()) } Err(e) => Err(e) @@ -137,7 +139,10 @@ impl Listener { /// notification about the signal. If the signal has already been received, /// it may still be returned by `recv`. pub fn unregister(&mut self, signum: Signum) { - self.handles.pop(&signum); + match self.handles.iter().position(|&(i, _)| i == signum) { + Some(i) => drop(self.handles.remove(i)), + None => {} + } } } diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs index 6996cba42b4..d855aebdf3f 100644 --- a/src/libstd/lib.rs +++ b/src/libstd/lib.rs @@ -11,7 +11,7 @@ //! # The Rust standard library //! //! The Rust standard library is a group of interrelated modules defining -//! the core language traits, operations on built-in data types, collections, +//! the core language traits, operations on built-in data types, //! platform abstractions, the task scheduler, runtime support for language //! features and other common functionality. //! @@ -68,9 +68,9 @@ // When testing libstd, bring in libuv as the I/O backend so tests can print // things and all of the std::io tests have an I/O interface to run on top // of -#[cfg(test)] extern crate rustuv = "rustuv"; -#[cfg(test)] extern crate native = "native"; -#[cfg(test)] extern crate green = "green"; +#[cfg(test)] extern crate rustuv; +#[cfg(test)] extern crate native; +#[cfg(test)] extern crate green; // Make extra accessible for benchmarking #[cfg(test)] extern crate extra = "extra"; @@ -156,9 +156,7 @@ pub mod any; pub mod option; pub mod result; -pub mod hashmap; pub mod cell; -pub mod trie; /* Tasks and communication */ diff --git a/src/libstd/logging.rs b/src/libstd/logging.rs index 9aa63f15def..39a62a80cfc 100644 --- a/src/libstd/logging.rs +++ b/src/libstd/logging.rs @@ -70,7 +70,7 @@ hello // turns on all logging for the 'hello' module info // turns on all info logging hello=debug // turns on debug logging for 'hello' hello=3 // turns on info logging for 'hello' -hello,std::hashmap // turns on hello, and std's hashmap logging +hello,std::option // turns on hello, and std's option logging error,hello=warn // turn on global error logging and also warn for hello ``` diff --git a/src/libstd/rt/crate_map.rs b/src/libstd/rt/crate_map.rs index 8567f0e0251..847375121c8 100644 --- a/src/libstd/rt/crate_map.rs +++ b/src/libstd/rt/crate_map.rs @@ -8,13 +8,13 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +use cmp::TotalOrd; use container::MutableSet; -use hashmap::HashSet; use iter::Iterator; use option::{Some, None, Option}; use ptr::RawPtr; -use vec::ImmutableVector; use rt::rtio::EventLoop; +use vec::{ImmutableVector, OwnedVector}; // Need to tell the linker on OS X to not barf on undefined symbols // and instead look them up at runtime, which we need to resolve @@ -89,28 +89,33 @@ fn version(crate_map: &CrateMap) -> i32 { fn do_iter_crate_map<'a>( crate_map: &'a CrateMap<'a>, f: |&ModEntry|, - visited: &mut HashSet<*CrateMap<'a>>) { - if visited.insert(crate_map as *CrateMap) { - match version(crate_map) { - 2 => { - let (entries, children) = (crate_map.entries, crate_map.children); - for entry in entries.iter() { - f(entry); - } - for child in children.iter() { - do_iter_crate_map(*child, |x| f(x), visited); - } - }, - _ => fail!("invalid crate map version") - } + visited: &mut ~[*CrateMap<'a>]) { + let raw = crate_map as *CrateMap<'a>; + if visited.bsearch(|a| (*a as uint).cmp(&(raw as uint))).is_some() { + return + } + match visited.iter().position(|i| *i as uint > raw as uint) { + Some(i) => visited.insert(i, raw), + None => visited.push(raw), + } + + match version(crate_map) { + 2 => { + let (entries, children) = (crate_map.entries, crate_map.children); + for entry in entries.iter() { + f(entry); + } + for child in children.iter() { + do_iter_crate_map(*child, |x| f(x), visited); + } + }, + _ => fail!("invalid crate map version") } } /// Iterates recursively over `crate_map` and all child crate maps pub fn iter_crate_map<'a>(crate_map: &'a CrateMap<'a>, f: |&ModEntry|) { - // FIXME: use random numbers as keys from the OS-level RNG when there is a nice - // way to do this - let mut v: HashSet<*CrateMap<'a>> = HashSet::with_capacity_and_keys(0, 0, 32); + let mut v = ~[]; do_iter_crate_map(crate_map, f, &mut v); } diff --git a/src/libstd/to_str.rs b/src/libstd/to_str.rs index 0e5627fa066..46a9e93f416 100644 --- a/src/libstd/to_str.rs +++ b/src/libstd/to_str.rs @@ -16,11 +16,7 @@ The `ToStr` trait for converting to strings use option::{Some, None}; use str::OwnedStr; -use hashmap::HashMap; -use hashmap::HashSet; -use hash_old::Hash; use iter::Iterator; -use cmp::Eq; use vec::ImmutableVector; /// A generic trait for converting a value to a string @@ -40,46 +36,6 @@ impl ToStr for () { fn to_str(&self) -> ~str { ~"()" } } -impl<A:ToStr+Hash+Eq, B:ToStr> ToStr for HashMap<A, B> { - #[inline] - fn to_str(&self) -> ~str { - let mut acc = ~"{"; - let mut first = true; - for (key, value) in self.iter() { - if first { - first = false; - } - else { - acc.push_str(", "); - } - acc.push_str(key.to_str()); - acc.push_str(": "); - acc.push_str(value.to_str()); - } - acc.push_char('}'); - acc - } -} - -impl<A:ToStr+Hash+Eq> ToStr for HashSet<A> { - #[inline] - fn to_str(&self) -> ~str { - let mut acc = ~"{"; - let mut first = true; - for element in self.iter() { - if first { - first = false; - } - else { - acc.push_str(", "); - } - acc.push_str(element.to_str()); - } - acc.push_char('}'); - acc - } -} - impl<'a,A:ToStr> ToStr for &'a [A] { #[inline] fn to_str(&self) -> ~str { @@ -120,9 +76,6 @@ impl<A:ToStr> ToStr for ~[A] { #[cfg(test)] mod tests { - use hashmap::HashMap; - use hashmap::HashSet; - use container::{MutableSet, MutableMap}; use super::*; #[test] @@ -146,42 +99,4 @@ mod tests { assert!((~[~[], ~[1], ~[1, 1]]).to_str() == ~"[[], [1], [1, 1]]"); } - - struct StructWithToStrWithoutEqOrHash { - value: int - } - - impl ToStr for StructWithToStrWithoutEqOrHash { - fn to_str(&self) -> ~str { - format!("s{}", self.value) - } - } - - #[test] - fn test_hashmap() { - let mut table: HashMap<int, StructWithToStrWithoutEqOrHash> = HashMap::new(); - let empty: HashMap<int, StructWithToStrWithoutEqOrHash> = HashMap::new(); - - table.insert(3, StructWithToStrWithoutEqOrHash { value: 4 }); - table.insert(1, StructWithToStrWithoutEqOrHash { value: 2 }); - - let table_str = table.to_str(); - - assert!(table_str == ~"{1: s2, 3: s4}" || table_str == ~"{3: s4, 1: s2}"); - assert_eq!(empty.to_str(), ~"{}"); - } - - #[test] - fn test_hashset() { - let mut set: HashSet<int> = HashSet::new(); - let empty_set: HashSet<int> = HashSet::new(); - - set.insert(1); - set.insert(2); - - let set_str = set.to_str(); - - assert!(set_str == ~"{1, 2}" || set_str == ~"{2, 1}"); - assert_eq!(empty_set.to_str(), ~"{}"); - } } diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs deleted file mode 100644 index d17d59f8665..00000000000 --- a/src/libstd/trie.rs +++ /dev/null @@ -1,1047 +0,0 @@ -// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! Ordered containers with integer keys, implemented as radix tries (`TrieSet` and `TrieMap` types) - -use option::{None, Option, Some}; -use container::{Container, Map, Mutable, MutableMap}; -use iter::{Extendable, FromIterator, Iterator}; -use mem; -use uint; -use mem::init; -use vec; -use ptr::RawPtr; -use vec::{ImmutableVector, Items, MutableVector, MutItems, OwnedVector}; - -// FIXME: #5244: need to manually update the TrieNode constructor -static SHIFT: uint = 4; -static SIZE: uint = 1 << SHIFT; -static MASK: uint = SIZE - 1; -static NUM_CHUNKS: uint = uint::BITS / SHIFT; - -enum Child<T> { - Internal(~TrieNode<T>), - External(uint, T), - Nothing -} - -#[allow(missing_doc)] -pub struct TrieMap<T> { - priv root: TrieNode<T>, - priv length: uint -} - -impl<T> Container for TrieMap<T> { - /// Return the number of elements in the map - #[inline] - fn len(&self) -> uint { self.length } -} - -impl<T> Mutable for TrieMap<T> { - /// Clear the map, removing all values. - #[inline] - fn clear(&mut self) { - self.root = TrieNode::new(); - self.length = 0; - } -} - -impl<T> Map<uint, T> for TrieMap<T> { - /// Return a reference to the value corresponding to the key - #[inline] - fn find<'a>(&'a self, key: &uint) -> Option<&'a T> { - let mut node: &'a TrieNode<T> = &self.root; - let mut idx = 0; - loop { - match node.children[chunk(*key, idx)] { - Internal(ref x) => node = &**x, - External(stored, ref value) => { - if stored == *key { - return Some(value) - } else { - return None - } - } - Nothing => return None - } - idx += 1; - } - } -} - -impl<T> MutableMap<uint, T> for TrieMap<T> { - /// Return a mutable reference to the value corresponding to the key - #[inline] - fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> { - find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1) - } - - /// Insert a key-value pair from the map. If the key already had a value - /// present in the map, that value is returned. Otherwise None is returned. - fn swap(&mut self, key: uint, value: T) -> Option<T> { - let ret = insert(&mut self.root.count, - &mut self.root.children[chunk(key, 0)], - key, value, 1); - if ret.is_none() { self.length += 1 } - ret - } - - /// Removes a key from the map, returning the value at the key if the key - /// was previously in the map. - fn pop(&mut self, key: &uint) -> Option<T> { - let ret = remove(&mut self.root.count, - &mut self.root.children[chunk(*key, 0)], - *key, 1); - if ret.is_some() { self.length -= 1 } - ret - } -} - -impl<T> TrieMap<T> { - /// Create an empty TrieMap - #[inline] - pub fn new() -> TrieMap<T> { - TrieMap{root: TrieNode::new(), length: 0} - } - - /// Visit all key-value pairs in reverse order - #[inline] - pub fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool { - self.root.each_reverse(f) - } - - /// Get an iterator over the key-value pairs in the map - pub fn iter<'a>(&'a self) -> Entries<'a, T> { - let mut iter = unsafe {Entries::new()}; - iter.stack[0] = self.root.children.iter(); - iter.length = 1; - iter.remaining_min = self.length; - iter.remaining_max = self.length; - - iter - } - - /// Get an iterator over the key-value pairs in the map, with the - /// ability to mutate the values. - pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, T> { - let mut iter = unsafe {MutEntries::new()}; - iter.stack[0] = self.root.children.mut_iter(); - iter.length = 1; - iter.remaining_min = self.length; - iter.remaining_max = self.length; - - iter - } -} - -// FIXME #5846 we want to be able to choose between &x and &mut x -// (with many different `x`) below, so we need to optionally pass mut -// as a tt, but the only thing we can do with a `tt` is pass them to -// other macros, so this takes the `& <mutability> <operand>` token -// sequence and forces their evalutation as an expression. (see also -// `item!` below.) -macro_rules! addr { ($e:expr) => { $e } } - -macro_rules! bound { - ($iterator_name:ident, - // the current treemap - self = $this:expr, - // the key to look for - key = $key:expr, - // are we looking at the upper bound? - is_upper = $upper:expr, - - // method names for slicing/iterating. - slice_from = $slice_from:ident, - iter = $iter:ident, - - // see the comment on `addr!`, this is just an optional mut, but - // there's no 0-or-1 repeats yet. - mutability = $($mut_:tt)*) => { - { - // # For `mut` - // We need an unsafe pointer here because we are borrowing - // mutable references to the internals of each of these - // mutable nodes, while still using the outer node. - // - // However, we're allowed to flaunt rustc like this because we - // never actually modify the "shape" of the nodes. The only - // place that mutation is can actually occur is of the actual - // values of the TrieMap (as the return value of the - // iterator), i.e. we can never cause a deallocation of any - // TrieNodes so the raw pointer is always valid. - // - // # For non-`mut` - // We like sharing code so much that even a little unsafe won't - // stop us. - let this = $this; - let mut node = addr!(& $($mut_)* this.root as * $($mut_)* TrieNode<T>); - - let key = $key; - - let mut it = unsafe {$iterator_name::new()}; - // everything else is zero'd, as we want. - it.remaining_max = this.length; - - // this addr is necessary for the `Internal` pattern. - addr!(loop { - let children = unsafe {addr!(& $($mut_)* (*node).children)}; - // it.length is the current depth in the iterator and the - // current depth through the `uint` key we've traversed. - let child_id = chunk(key, it.length); - let (slice_idx, ret) = match children[child_id] { - Internal(ref $($mut_)* n) => { - node = addr!(& $($mut_)* **n as * $($mut_)* TrieNode<T>); - (child_id + 1, false) - } - External(stored, _) => { - (if stored < key || ($upper && stored == key) { - child_id + 1 - } else { - child_id - }, true) - } - Nothing => { - (child_id + 1, true) - } - }; - // push to the stack. - it.stack[it.length] = children.$slice_from(slice_idx).$iter(); - it.length += 1; - if ret { return it } - }) - } - } -} - -impl<T> TrieMap<T> { - // If `upper` is true then returns upper_bound else returns lower_bound. - #[inline] - fn bound<'a>(&'a self, key: uint, upper: bool) -> Entries<'a, T> { - bound!(Entries, self = self, - key = key, is_upper = upper, - slice_from = slice_from, iter = iter, - mutability = ) - } - - /// Get an iterator pointing to the first key-value pair whose key is not less than `key`. - /// If all keys in the map are less than `key` an empty iterator is returned. - pub fn lower_bound<'a>(&'a self, key: uint) -> Entries<'a, T> { - self.bound(key, false) - } - - /// Get an iterator pointing to the first key-value pair whose key is greater than `key`. - /// If all keys in the map are not greater than `key` an empty iterator is returned. - pub fn upper_bound<'a>(&'a self, key: uint) -> Entries<'a, T> { - self.bound(key, true) - } - // If `upper` is true then returns upper_bound else returns lower_bound. - #[inline] - fn mut_bound<'a>(&'a mut self, key: uint, upper: bool) -> MutEntries<'a, T> { - bound!(MutEntries, self = self, - key = key, is_upper = upper, - slice_from = mut_slice_from, iter = mut_iter, - mutability = mut) - } - - /// Get an iterator pointing to the first key-value pair whose key is not less than `key`. - /// If all keys in the map are less than `key` an empty iterator is returned. - pub fn mut_lower_bound<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> { - self.mut_bound(key, false) - } - - /// Get an iterator pointing to the first key-value pair whose key is greater than `key`. - /// If all keys in the map are not greater than `key` an empty iterator is returned. - pub fn mut_upper_bound<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> { - self.mut_bound(key, true) - } -} - -impl<T> FromIterator<(uint, T)> for TrieMap<T> { - fn from_iterator<Iter: Iterator<(uint, T)>>(iter: &mut Iter) -> TrieMap<T> { - let mut map = TrieMap::new(); - map.extend(iter); - map - } -} - -impl<T> Extendable<(uint, T)> for TrieMap<T> { - fn extend<Iter: Iterator<(uint, T)>>(&mut self, iter: &mut Iter) { - for (k, v) in *iter { - self.insert(k, v); - } - } -} - -#[allow(missing_doc)] -pub struct TrieSet { - priv map: TrieMap<()> -} - -impl Container for TrieSet { - /// Return the number of elements in the set - #[inline] - fn len(&self) -> uint { self.map.len() } -} - -impl Mutable for TrieSet { - /// Clear the set, removing all values. - #[inline] - fn clear(&mut self) { self.map.clear() } -} - -impl TrieSet { - /// Create an empty TrieSet - #[inline] - pub fn new() -> TrieSet { - TrieSet{map: TrieMap::new()} - } - - /// Return true if the set contains a value - #[inline] - pub fn contains(&self, value: &uint) -> bool { - self.map.contains_key(value) - } - - /// Add a value to the set. Return true if the value was not already - /// present in the set. - #[inline] - pub fn insert(&mut self, value: uint) -> bool { - self.map.insert(value, ()) - } - - /// Remove a value from the set. Return true if the value was - /// present in the set. - #[inline] - pub fn remove(&mut self, value: &uint) -> bool { - self.map.remove(value) - } - - /// Visit all values in reverse order - #[inline] - pub fn each_reverse(&self, f: |&uint| -> bool) -> bool { - self.map.each_reverse(|k, _| f(k)) - } - - /// Get an iterator over the values in the set - #[inline] - pub fn iter<'a>(&'a self) -> SetItems<'a> { - SetItems{iter: self.map.iter()} - } - - /// Get an iterator pointing to the first value that is not less than `val`. - /// If all values in the set are less than `val` an empty iterator is returned. - pub fn lower_bound<'a>(&'a self, val: uint) -> SetItems<'a> { - SetItems{iter: self.map.lower_bound(val)} - } - - /// Get an iterator pointing to the first value that key is greater than `val`. - /// If all values in the set are not greater than `val` an empty iterator is returned. - pub fn upper_bound<'a>(&'a self, val: uint) -> SetItems<'a> { - SetItems{iter: self.map.upper_bound(val)} - } -} - -impl FromIterator<uint> for TrieSet { - fn from_iterator<Iter: Iterator<uint>>(iter: &mut Iter) -> TrieSet { - let mut set = TrieSet::new(); - set.extend(iter); - set - } -} - -impl Extendable<uint> for TrieSet { - fn extend<Iter: Iterator<uint>>(&mut self, iter: &mut Iter) { - for elem in *iter { - self.insert(elem); - } - } -} - -struct TrieNode<T> { - count: uint, - children: [Child<T>, ..SIZE] -} - -impl<T> TrieNode<T> { - #[inline] - fn new() -> TrieNode<T> { - // FIXME: #5244: [Nothing, ..SIZE] should be possible without implicit - // copyability - TrieNode{count: 0, - children: [Nothing, Nothing, Nothing, Nothing, - Nothing, Nothing, Nothing, Nothing, - Nothing, Nothing, Nothing, Nothing, - Nothing, Nothing, Nothing, Nothing]} - } -} - -impl<T> TrieNode<T> { - fn each_reverse<'a>(&'a self, f: |&uint, &'a T| -> bool) -> bool { - for elt in self.children.rev_iter() { - match *elt { - Internal(ref x) => if !x.each_reverse(|i,t| f(i,t)) { return false }, - External(k, ref v) => if !f(&k, v) { return false }, - Nothing => () - } - } - true - } -} - -// if this was done via a trait, the key could be generic -#[inline] -fn chunk(n: uint, idx: uint) -> uint { - let sh = uint::BITS - (SHIFT * (idx + 1)); - (n >> sh) & MASK -} - -fn find_mut<'r, T>(child: &'r mut Child<T>, key: uint, idx: uint) -> Option<&'r mut T> { - match *child { - External(stored, ref mut value) if stored == key => Some(value), - External(..) => None, - Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1), - Nothing => None - } -} - -fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T, - idx: uint) -> Option<T> { - // we branch twice to avoid having to do the `replace` when we - // don't need to; this is much faster, especially for keys that - // have long shared prefixes. - match *child { - Nothing => { - *count += 1; - *child = External(key, value); - return None; - } - Internal(ref mut x) => { - return insert(&mut x.count, &mut x.children[chunk(key, idx)], key, value, idx + 1); - } - External(stored_key, ref mut stored_value) if stored_key == key => { - // swap in the new value and return the old. - return Some(mem::replace(stored_value, value)); - } - _ => {} - } - - // conflict, an external node with differing keys: we have to - // split the node, so we need the old value by value; hence we - // have to move out of `child`. - match mem::replace(child, Nothing) { - External(stored_key, stored_value) => { - let mut new = ~TrieNode::new(); - insert(&mut new.count, - &mut new.children[chunk(stored_key, idx)], - stored_key, stored_value, idx + 1); - let ret = insert(&mut new.count, &mut new.children[chunk(key, idx)], - key, value, idx + 1); - *child = Internal(new); - return ret; - } - _ => unreachable!() - } -} - -fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint, - idx: uint) -> Option<T> { - let (ret, this) = match *child { - External(stored, _) if stored == key => { - match mem::replace(child, Nothing) { - External(_, value) => (Some(value), true), - _ => fail!() - } - } - External(..) => (None, false), - Internal(ref mut x) => { - let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)], - key, idx + 1); - (ret, x.count == 0) - } - Nothing => (None, false) - }; - - if this { - *child = Nothing; - *count -= 1; - } - return ret; -} - -/// Forward iterator over a map -pub struct Entries<'a, T> { - priv stack: [vec::Items<'a, Child<T>>, .. NUM_CHUNKS], - priv length: uint, - priv remaining_min: uint, - priv remaining_max: uint -} - -/// Forward iterator over the key-value pairs of a map, with the -/// values being mutable. -pub struct MutEntries<'a, T> { - priv stack: [vec::MutItems<'a, Child<T>>, .. NUM_CHUNKS], - priv length: uint, - priv remaining_min: uint, - priv remaining_max: uint -} - -// FIXME #5846: see `addr!` above. -macro_rules! item { ($i:item) => {$i}} - -macro_rules! iterator_impl { - ($name:ident, - iter = $iter:ident, - mutability = $($mut_:tt)*) => { - impl<'a, T> $name<'a, T> { - // Create new zero'd iterator. We have a thin gilding of safety by - // using init rather than uninit, so that the worst that can happen - // from failing to initialise correctly after calling these is a - // segfault. - #[cfg(target_word_size="32")] - unsafe fn new() -> $name<'a, T> { - $name { - remaining_min: 0, - remaining_max: 0, - length: 0, - // ick :( ... at least the compiler will tell us if we screwed up. - stack: [init(), init(), init(), init(), init(), init(), init(), init()] - } - } - - #[cfg(target_word_size="64")] - unsafe fn new() -> $name<'a, T> { - $name { - remaining_min: 0, - remaining_max: 0, - length: 0, - stack: [init(), init(), init(), init(), init(), init(), init(), init(), - init(), init(), init(), init(), init(), init(), init(), init()] - } - } - } - - item!(impl<'a, T> Iterator<(uint, &'a $($mut_)* T)> for $name<'a, T> { - // you might wonder why we're not even trying to act within the - // rules, and are just manipulating raw pointers like there's no - // such thing as invalid pointers and memory unsafety. The - // reason is performance, without doing this we can get the - // bench_iter_large microbenchmark down to about 30000 ns/iter - // (using .unsafe_ref to index self.stack directly, 38000 - // ns/iter with [] checked indexing), but this smashes that down - // to 13500 ns/iter. - // - // Fortunately, it's still safe... - // - // We have an invariant that every Internal node - // corresponds to one push to self.stack, and one pop, - // nested appropriately. self.stack has enough storage - // to store the maximum depth of Internal nodes in the - // trie (8 on 32-bit platforms, 16 on 64-bit). - fn next(&mut self) -> Option<(uint, &'a $($mut_)* T)> { - let start_ptr = self.stack.as_mut_ptr(); - - unsafe { - // write_ptr is the next place to write to the stack. - // invariant: start_ptr <= write_ptr < end of the - // vector. - let mut write_ptr = start_ptr.offset(self.length as int); - while write_ptr != start_ptr { - // indexing back one is safe, since write_ptr > - // start_ptr now. - match (*write_ptr.offset(-1)).next() { - // exhausted this iterator (i.e. finished this - // Internal node), so pop from the stack. - // - // don't bother clearing the memory, because the - // next time we use it we'll've written to it - // first. - None => write_ptr = write_ptr.offset(-1), - Some(child) => { - addr!(match *child { - Internal(ref $($mut_)* node) => { - // going down a level, so push - // to the stack (this is the - // write referenced above) - *write_ptr = node.children.$iter(); - write_ptr = write_ptr.offset(1); - } - External(key, ref $($mut_)* value) => { - self.remaining_max -= 1; - if self.remaining_min > 0 { - self.remaining_min -= 1; - } - // store the new length of the - // stack, based on our current - // position. - self.length = (write_ptr as uint - - start_ptr as uint) / - mem::size_of_val(&*write_ptr); - - return Some((key, value)); - } - Nothing => {} - }) - } - } - } - } - return None; - } - - #[inline] - fn size_hint(&self) -> (uint, Option<uint>) { - (self.remaining_min, Some(self.remaining_max)) - } - }) - } -} - -iterator_impl! { Entries, iter = iter, mutability = } -iterator_impl! { MutEntries, iter = mut_iter, mutability = mut } - -/// Forward iterator over a set -pub struct SetItems<'a> { - priv iter: Entries<'a, ()> -} - -impl<'a> Iterator<uint> for SetItems<'a> { - fn next(&mut self) -> Option<uint> { - self.iter.next().map(|(key, _)| key) - } - - fn size_hint(&self) -> (uint, Option<uint>) { - self.iter.size_hint() - } -} - -#[cfg(test)] -pub fn check_integrity<T>(trie: &TrieNode<T>) { - assert!(trie.count != 0); - - let mut sum = 0; - - for x in trie.children.iter() { - match *x { - Nothing => (), - Internal(ref y) => { - check_integrity(&**y); - sum += 1 - } - External(_, _) => { sum += 1 } - } - } - - assert_eq!(sum, trie.count); -} - -#[cfg(test)] -mod test_map { - use super::*; - use prelude::*; - use iter::range_step; - use uint; - - #[test] - fn test_find_mut() { - let mut m = TrieMap::new(); - assert!(m.insert(1, 12)); - assert!(m.insert(2, 8)); - assert!(m.insert(5, 14)); - let new = 100; - match m.find_mut(&5) { - None => fail!(), Some(x) => *x = new - } - assert_eq!(m.find(&5), Some(&new)); - } - - #[test] - fn test_find_mut_missing() { - let mut m = TrieMap::new(); - assert!(m.find_mut(&0).is_none()); - assert!(m.insert(1, 12)); - assert!(m.find_mut(&0).is_none()); - assert!(m.insert(2, 8)); - assert!(m.find_mut(&0).is_none()); - } - - #[test] - fn test_step() { - let mut trie = TrieMap::new(); - let n = 300u; - - for x in range_step(1u, n, 2) { - assert!(trie.insert(x, x + 1)); - assert!(trie.contains_key(&x)); - check_integrity(&trie.root); - } - - for x in range_step(0u, n, 2) { - assert!(!trie.contains_key(&x)); - assert!(trie.insert(x, x + 1)); - check_integrity(&trie.root); - } - - for x in range(0u, n) { - assert!(trie.contains_key(&x)); - assert!(!trie.insert(x, x + 1)); - check_integrity(&trie.root); - } - - for x in range_step(1u, n, 2) { - assert!(trie.remove(&x)); - assert!(!trie.contains_key(&x)); - check_integrity(&trie.root); - } - - for x in range_step(0u, n, 2) { - assert!(trie.contains_key(&x)); - assert!(!trie.insert(x, x + 1)); - check_integrity(&trie.root); - } - } - - #[test] - fn test_each_reverse() { - let mut m = TrieMap::new(); - - assert!(m.insert(3, 6)); - assert!(m.insert(0, 0)); - assert!(m.insert(4, 8)); - assert!(m.insert(2, 4)); - assert!(m.insert(1, 2)); - - let mut n = 4; - m.each_reverse(|k, v| { - assert_eq!(*k, n); - assert_eq!(*v, n * 2); - n -= 1; - true - }); - } - - #[test] - fn test_each_reverse_break() { - let mut m = TrieMap::new(); - - for x in range(uint::MAX - 10000, uint::MAX).rev() { - m.insert(x, x / 2); - } - - let mut n = uint::MAX - 1; - m.each_reverse(|k, v| { - if n == uint::MAX - 5000 { false } else { - assert!(n > uint::MAX - 5000); - - assert_eq!(*k, n); - assert_eq!(*v, n / 2); - n -= 1; - true - } - }); - } - - #[test] - fn test_swap() { - let mut m = TrieMap::new(); - assert_eq!(m.swap(1, 2), None); - assert_eq!(m.swap(1, 3), Some(2)); - assert_eq!(m.swap(1, 4), Some(3)); - } - - #[test] - fn test_pop() { - let mut m = TrieMap::new(); - m.insert(1, 2); - assert_eq!(m.pop(&1), Some(2)); - assert_eq!(m.pop(&1), None); - } - - #[test] - fn test_from_iter() { - let xs = ~[(1u, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - - let map: TrieMap<int> = xs.iter().map(|&x| x).collect(); - - for &(k, v) in xs.iter() { - assert_eq!(map.find(&k), Some(&v)); - } - } - - #[test] - fn test_iteration() { - let empty_map : TrieMap<uint> = TrieMap::new(); - assert_eq!(empty_map.iter().next(), None); - - let first = uint::MAX - 10000; - let last = uint::MAX; - - let mut map = TrieMap::new(); - for x in range(first, last).rev() { - map.insert(x, x / 2); - } - - let mut i = 0; - for (k, &v) in map.iter() { - assert_eq!(k, first + i); - assert_eq!(v, k / 2); - i += 1; - } - assert_eq!(i, last - first); - } - - #[test] - fn test_mut_iter() { - let mut empty_map : TrieMap<uint> = TrieMap::new(); - assert!(empty_map.mut_iter().next().is_none()); - - let first = uint::MAX - 10000; - let last = uint::MAX; - - let mut map = TrieMap::new(); - for x in range(first, last).rev() { - map.insert(x, x / 2); - } - - let mut i = 0; - for (k, v) in map.mut_iter() { - assert_eq!(k, first + i); - *v -= k / 2; - i += 1; - } - assert_eq!(i, last - first); - - assert!(map.iter().all(|(_, &v)| v == 0)); - } - - #[test] - fn test_bound() { - let empty_map : TrieMap<uint> = TrieMap::new(); - assert_eq!(empty_map.lower_bound(0).next(), None); - assert_eq!(empty_map.upper_bound(0).next(), None); - - let last = 999u; - let step = 3u; - let value = 42u; - - let mut map : TrieMap<uint> = TrieMap::new(); - for x in range_step(0u, last, step) { - assert!(x % step == 0); - map.insert(x, value); - } - - for i in range(0u, last - step) { - let mut lb = map.lower_bound(i); - let mut ub = map.upper_bound(i); - let next_key = i - i % step + step; - let next_pair = (next_key, &value); - if i % step == 0 { - assert_eq!(lb.next(), Some((i, &value))); - } else { - assert_eq!(lb.next(), Some(next_pair)); - } - assert_eq!(ub.next(), Some(next_pair)); - } - - let mut lb = map.lower_bound(last - step); - assert_eq!(lb.next(), Some((last - step, &value))); - let mut ub = map.upper_bound(last - step); - assert_eq!(ub.next(), None); - - for i in range(last - step + 1, last) { - let mut lb = map.lower_bound(i); - assert_eq!(lb.next(), None); - let mut ub = map.upper_bound(i); - assert_eq!(ub.next(), None); - } - } - - #[test] - fn test_mut_bound() { - let empty_map : TrieMap<uint> = TrieMap::new(); - assert_eq!(empty_map.lower_bound(0).next(), None); - assert_eq!(empty_map.upper_bound(0).next(), None); - - let mut m_lower = TrieMap::new(); - let mut m_upper = TrieMap::new(); - for i in range(0u, 100) { - m_lower.insert(2 * i, 4 * i); - m_upper.insert(2 * i, 4 * i); - } - - for i in range(0u, 199) { - let mut lb_it = m_lower.mut_lower_bound(i); - let (k, v) = lb_it.next().unwrap(); - let lb = i + i % 2; - assert_eq!(lb, k); - *v -= k; - } - - for i in range(0u, 198) { - let mut ub_it = m_upper.mut_upper_bound(i); - let (k, v) = ub_it.next().unwrap(); - let ub = i + 2 - i % 2; - assert_eq!(ub, k); - *v -= k; - } - - assert!(m_lower.mut_lower_bound(199).next().is_none()); - assert!(m_upper.mut_upper_bound(198).next().is_none()); - - assert!(m_lower.iter().all(|(_, &x)| x == 0)); - assert!(m_upper.iter().all(|(_, &x)| x == 0)); - } -} - -#[cfg(test)] -mod bench_map { - extern crate test; - use self::test::BenchHarness; - use super::*; - use prelude::*; - use rand::{weak_rng, Rng}; - - #[bench] - fn bench_iter_small(bh: &mut BenchHarness) { - let mut m = TrieMap::<uint>::new(); - let mut rng = weak_rng(); - for _ in range(0, 20) { - m.insert(rng.gen(), rng.gen()); - } - - bh.iter(|| for _ in m.iter() {}) - } - - #[bench] - fn bench_iter_large(bh: &mut BenchHarness) { - let mut m = TrieMap::<uint>::new(); - let mut rng = weak_rng(); - for _ in range(0, 1000) { - m.insert(rng.gen(), rng.gen()); - } - - bh.iter(|| for _ in m.iter() {}) - } - - #[bench] - fn bench_lower_bound(bh: &mut BenchHarness) { - let mut m = TrieMap::<uint>::new(); - let mut rng = weak_rng(); - for _ in range(0, 1000) { - m.insert(rng.gen(), rng.gen()); - } - - bh.iter(|| { - for _ in range(0, 10) { - m.lower_bound(rng.gen()); - } - }); - } - - #[bench] - fn bench_upper_bound(bh: &mut BenchHarness) { - let mut m = TrieMap::<uint>::new(); - let mut rng = weak_rng(); - for _ in range(0, 1000) { - m.insert(rng.gen(), rng.gen()); - } - - bh.iter(|| { - for _ in range(0, 10) { - m.upper_bound(rng.gen()); - } - }); - } - - #[bench] - fn bench_insert_large(bh: &mut BenchHarness) { - let mut m = TrieMap::<[uint, .. 10]>::new(); - let mut rng = weak_rng(); - - bh.iter(|| { - for _ in range(0, 1000) { - m.insert(rng.gen(), [1, .. 10]); - } - }) - } - #[bench] - fn bench_insert_large_low_bits(bh: &mut BenchHarness) { - let mut m = TrieMap::<[uint, .. 10]>::new(); - let mut rng = weak_rng(); - - bh.iter(|| { - for _ in range(0, 1000) { - // only have the last few bits set. - m.insert(rng.gen::<uint>() & 0xff_ff, [1, .. 10]); - } - }) - } - - #[bench] - fn bench_insert_small(bh: &mut BenchHarness) { - let mut m = TrieMap::<()>::new(); - let mut rng = weak_rng(); - - bh.iter(|| { - for _ in range(0, 1000) { - m.insert(rng.gen(), ()); - } - }) - } - #[bench] - fn bench_insert_small_low_bits(bh: &mut BenchHarness) { - let mut m = TrieMap::<()>::new(); - let mut rng = weak_rng(); - - bh.iter(|| { - for _ in range(0, 1000) { - // only have the last few bits set. - m.insert(rng.gen::<uint>() & 0xff_ff, ()); - } - }) - } -} - -#[cfg(test)] -mod test_set { - use super::*; - use prelude::*; - use uint; - - #[test] - fn test_sane_chunk() { - let x = 1; - let y = 1 << (uint::BITS - 1); - - let mut trie = TrieSet::new(); - - assert!(trie.insert(x)); - assert!(trie.insert(y)); - - assert_eq!(trie.len(), 2); - - let expected = [x, y]; - - for (i, x) in trie.iter().enumerate() { - assert_eq!(expected[i], x); - } - } - - #[test] - fn test_from_iter() { - let xs = ~[9u, 8, 7, 6, 5, 4, 3, 2, 1]; - - let set: TrieSet = xs.iter().map(|&x| x).collect(); - - for x in xs.iter() { - assert!(set.contains(x)); - } - } -} diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index 0adc6083f6b..b4764f577cb 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -3395,7 +3395,6 @@ mod tests { #[test] fn test_permutations() { - use hashmap; { let v: [int, ..0] = []; let mut it = v.permutations(); @@ -3418,13 +3417,13 @@ mod tests { assert_eq!(it.next(), None); } { - // check that we have N! unique permutations - let mut set = hashmap::HashSet::new(); + // check that we have N! permutations let v = ['A', 'B', 'C', 'D', 'E', 'F']; - for perm in v.permutations() { - set.insert(perm); + let mut amt = 0; + for _perm in v.permutations() { + amt += 1; } - assert_eq!(set.len(), 2 * 3 * 4 * 5 * 6); + assert_eq!(amt, 2 * 3 * 4 * 5 * 6); } } |