From 2a14e084cfd8cf9a9149d0b7c6329b0dad0521d0 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Wed, 19 Feb 2014 19:29:58 -0800 Subject: Move std::{trie, hashmap} to libcollections These two containers are indeed collections, so their place is in libcollections, not in libstd. There will always be a hash map as part of the standard distribution of Rust, but by moving it out of the standard library it makes libstd that much more portable to more platforms and environments. This conveniently also removes the stuttering of 'std::hashmap::HashMap', although 'collections::HashMap' is only one character shorter. --- mk/crates.mk | 2 +- src/doc/rust.md | 2 +- src/doc/tutorial.md | 5 +- src/etc/combine-tests.py | 2 + src/libcollections/hashmap.rs | 1524 ++++++++++++++++++++ src/libcollections/lib.rs | 4 + src/libcollections/lru_cache.rs | 3 +- src/libcollections/trie.rs | 1094 ++++++++++++++ src/libextra/json.rs | 2 +- src/libextra/stats.rs | 2 +- src/libextra/url.rs | 4 +- src/libnative/io/timer_other.rs | 15 +- src/libnative/io/timer_timerfd.rs | 38 +- src/librustc/back/rpath.rs | 2 +- src/librustc/driver/driver.rs | 2 +- src/librustc/driver/session.rs | 2 +- src/librustc/lib/llvm.rs | 2 +- src/librustc/metadata/creader.rs | 2 +- src/librustc/metadata/cstore.rs | 2 +- src/librustc/metadata/encoder.rs | 2 +- src/librustc/metadata/filesearch.rs | 2 +- src/librustc/metadata/loader.rs | 2 +- src/librustc/metadata/tyencode.rs | 2 +- src/librustc/middle/borrowck/mod.rs | 2 +- src/librustc/middle/borrowck/move_data.rs | 2 +- src/librustc/middle/cfg/construct.rs | 2 +- src/librustc/middle/cfg/mod.rs | 2 +- src/librustc/middle/const_eval.rs | 2 +- src/librustc/middle/dataflow.rs | 2 +- src/librustc/middle/dead.rs | 2 +- src/librustc/middle/freevars.rs | 2 +- src/librustc/middle/lang_items.rs | 2 +- src/librustc/middle/lint.rs | 2 +- src/librustc/middle/liveness.rs | 2 +- src/librustc/middle/moves.rs | 2 +- src/librustc/middle/pat_util.rs | 2 +- src/librustc/middle/privacy.rs | 2 +- src/librustc/middle/reachable.rs | 2 +- src/librustc/middle/region.rs | 2 +- src/librustc/middle/resolve.rs | 2 +- src/librustc/middle/resolve_lifetime.rs | 2 +- src/librustc/middle/trans/_match.rs | 2 +- src/librustc/middle/trans/base.rs | 2 +- src/librustc/middle/trans/builder.rs | 2 +- src/librustc/middle/trans/common.rs | 2 +- src/librustc/middle/trans/context.rs | 2 +- src/librustc/middle/trans/debuginfo.rs | 4 +- src/librustc/middle/trans/expr.rs | 2 +- src/librustc/middle/ty.rs | 12 +- src/librustc/middle/typeck/check/_match.rs | 2 +- src/librustc/middle/typeck/check/method.rs | 2 +- src/librustc/middle/typeck/check/mod.rs | 2 +- src/librustc/middle/typeck/check/regionmanip.rs | 4 +- src/librustc/middle/typeck/check/vtable.rs | 2 +- src/librustc/middle/typeck/coherence.rs | 2 +- src/librustc/middle/typeck/infer/glb.rs | 2 +- src/librustc/middle/typeck/infer/lattice.rs | 2 +- src/librustc/middle/typeck/infer/lub.rs | 2 +- src/librustc/middle/typeck/infer/mod.rs | 2 +- .../middle/typeck/infer/region_inference/mod.rs | 2 +- src/librustc/middle/typeck/mod.rs | 2 +- src/librustc/middle/typeck/variance.rs | 2 +- src/librustdoc/core.rs | 2 +- src/librustdoc/html/render.rs | 2 +- src/librustdoc/passes.rs | 2 +- src/librustdoc/test.rs | 2 +- src/libserialize/serialize.rs | 121 -- src/libstd/hashmap.rs | 1422 ------------------ src/libstd/io/signal.rs | 21 +- src/libstd/lib.rs | 10 +- src/libstd/logging.rs | 2 +- src/libstd/rt/crate_map.rs | 43 +- src/libstd/to_str.rs | 85 -- src/libstd/trie.rs | 1047 -------------- src/libstd/vec.rs | 11 +- src/libsyntax/ast.rs | 6 +- src/libsyntax/ast_util.rs | 4 +- src/libsyntax/attr.rs | 2 +- src/libsyntax/ext/base.rs | 2 +- src/libsyntax/ext/deriving/show.rs | 2 +- src/libsyntax/ext/format.rs | 3 +- src/libsyntax/ext/tt/macro_parser.rs | 2 +- src/libsyntax/ext/tt/transcribe.rs | 2 +- src/libsyntax/parse/parser.rs | 2 +- src/libsyntax/util/interner.rs | 2 +- src/libterm/lib.rs | 2 + src/libterm/terminfo/mod.rs | 2 +- src/libterm/terminfo/parser/compiled.rs | 2 +- src/libuuid/lib.rs | 4 +- src/test/auxiliary/issue-2631-a.rs | 3 +- src/test/auxiliary/issue-5521.rs | 4 +- src/test/bench/core-map.rs | 4 +- src/test/bench/core-set.rs | 4 +- src/test/bench/shootout-k-nucleotide-pipes.rs | 3 +- .../compile-fail/borrowck-borrowed-uniq-rvalue.rs | 3 +- .../compile-fail/borrowck-insert-during-each.rs | 3 +- src/test/compile-fail/map-types.rs | 5 +- src/test/run-fail/unwind-misc-1.rs | 4 +- ...ach-external-iterators-hashmap-break-restart.rs | 4 +- .../run-pass/foreach-external-iterators-hashmap.rs | 4 +- src/test/run-pass/hashmap-memory.rs | 4 +- src/test/run-pass/issue-1696.rs | 4 +- src/test/run-pass/issue-2631-b.rs | 3 +- src/test/run-pass/issue-2804-2.rs | 4 +- src/test/run-pass/issue-2804.rs | 3 +- src/test/run-pass/issue-3026.rs | 4 +- src/test/run-pass/issue-3559.rs | 4 +- src/test/run-pass/issue-6128.rs | 4 +- src/test/run-pass/issue-7660.rs | 4 +- src/test/run-pass/regions-mock-tcx.rs | 3 +- src/test/run-pass/send_str_hashmap.rs | 4 +- 111 files changed, 2855 insertions(+), 2843 deletions(-) create mode 100644 src/libcollections/hashmap.rs create mode 100644 src/libcollections/trie.rs delete mode 100644 src/libstd/hashmap.rs delete mode 100644 src/libstd/trie.rs diff --git a/mk/crates.mk b/mk/crates.mk index af791c54edd..8e624cb313f 100644 --- a/mk/crates.mk +++ b/mk/crates.mk @@ -69,7 +69,7 @@ DEPS_flate := std native:miniz DEPS_arena := std collections DEPS_glob := std DEPS_serialize := std -DEPS_term := std +DEPS_term := std collections DEPS_semver := std DEPS_uuid := std serialize DEPS_sync := std diff --git a/src/doc/rust.md b/src/doc/rust.md index 9173156d91d..6d9cb8b5d7b 100644 --- a/src/doc/rust.md +++ b/src/doc/rust.md @@ -467,7 +467,7 @@ expression context, the final namespace qualifier is omitted. Two examples of paths with type arguments: ~~~~ -# use std::hashmap::HashMap; +# struct HashMap; # fn f() { # fn id(t: T) -> T { t } type T = HashMap; // Type arguments used in a type expression diff --git a/src/doc/tutorial.md b/src/doc/tutorial.md index 6454e22b896..304dc1fb5af 100644 --- a/src/doc/tutorial.md +++ b/src/doc/tutorial.md @@ -1977,8 +1977,8 @@ illegal to copy and pass by value. Generic `type`, `struct`, and `enum` declarations follow the same pattern: ~~~~ -use std::hashmap::HashMap; -type Set = HashMap; +extern crate collections; +type Set = collections::HashMap; struct Stack { elements: ~[T] @@ -1988,6 +1988,7 @@ enum Option { Some(T), None } +# fn main() {} ~~~~ These declarations can be instantiated to valid types like `Set`, diff --git a/src/etc/combine-tests.py b/src/etc/combine-tests.py index c972392a4a0..2590db56d0a 100755 --- a/src/etc/combine-tests.py +++ b/src/etc/combine-tests.py @@ -55,6 +55,8 @@ c.write( #[crate_id=\"run_pass_stage2#0.1\"]; #[feature(globs, macro_rules, struct_variant, managed_boxes)]; #[allow(warnings)]; +extern crate collections; +extern crate extra; """ ) for t in stage2_tests: diff --git a/src/libcollections/hashmap.rs b/src/libcollections/hashmap.rs new file mode 100644 index 00000000000..5cdd5bf3812 --- /dev/null +++ b/src/libcollections/hashmap.rs @@ -0,0 +1,1524 @@ +// 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 or the MIT license +// , 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 collections::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 std::cmp::max; +use std::fmt; +use std::hash_old::Hash; +use std::iter::{FilterMap, Chain, Repeat, Zip}; +use std::iter; +use std::mem::replace; +use std::num; +use std::rand::Rng; +use std::rand; +use std::vec::{Items, MutItems}; +use std::vec_ng::Vec; +use std::vec_ng; + +use serialize::{Encodable, Decodable, Encoder, Decoder}; + +static INITIAL_CAPACITY: uint = 32u; // 2^5 + +struct Bucket { + 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 { + priv k0: u64, + priv k1: u64, + priv resize_at: uint, + priv size: uint, + priv buckets: Vec>> +} + +// We could rewrite FoundEntry to have type Option<&Bucket> +// which would be nifty +enum SearchResult { + FoundEntry(uint), FoundHole(uint), TableFull +} + +#[inline] +fn resize_at(capacity: uint) -> uint { + (capacity * 3) / 4 +} + +impl HashMap { + #[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>(&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>(&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>) { + 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 { + 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 { + // 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 Container for HashMap { + /// Return the number of elements in the map + fn len(&self) -> uint { self.size } +} + +impl Mutable for HashMap { + /// 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 Map for HashMap { + /// 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 MutableMap for HashMap { + /// 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 { + // 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 { + let hash = k.hash_keyed(self.k0, self.k1) as uint; + self.pop_internal(hash, k) + } +} + +impl HashMap { + /// Create an empty HashMap + pub fn new() -> HashMap { + 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 { + 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 { + 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 collections::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>(&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>(&'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 { + MoveEntries {iter: self.buckets.move_iter()} + } +} + +impl HashMap { + /// Like `find`, but returns a copy of the value. + pub fn find_copy(&self, k: &K) -> Option { + 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 Eq for HashMap { + fn eq(&self, other: &HashMap) -> 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) -> bool { !self.eq(other) } +} + +impl Clone for HashMap { + fn clone(&self) -> HashMap { + 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 fmt::Show for HashMap { + 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"\}") + } +} + +impl ToStr for HashMap { + fn to_str(&self) -> ~str { format!("{}", *self) } +} + +/// HashMap iterator +#[deriving(Clone)] +pub struct Entries<'a, K, V> { + priv iter: Items<'a, Option>>, +} + +/// HashMap mutable values iterator +pub struct MutEntries<'a, K, V> { + priv iter: MutItems<'a, Option>>, +} + +/// HashMap move iterator +pub struct MoveEntries { + priv iter: vec_ng::MoveItems>>, +} + +/// 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>>, +} + +/// HashSet move iterator +pub struct SetMoveItems { + priv iter: vec_ng::MoveItems>>, +} + +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 Iterator<(K, V)> for MoveEntries { + #[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 Iterator for SetMoveItems { + #[inline] + fn next(&mut self) -> Option { + for elt in self.iter { + match elt { + Some(bucket) => return Some(bucket.key), + None => {}, + } + } + None + } +} + +impl FromIterator<(K, V)> for HashMap { + fn from_iterator>(iter: &mut T) -> HashMap { + let (lower, _) = iter.size_hint(); + let mut map = HashMap::with_capacity(lower); + map.extend(iter); + map + } +} + +impl Extendable<(K, V)> for HashMap { + fn extend>(&mut self, iter: &mut T) { + for (k, v) in *iter { + self.insert(k, v); + } + } +} + +impl Default for HashMap { + fn default() -> HashMap { 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 { + priv map: HashMap +} + +impl Eq for HashSet { + fn eq(&self, other: &HashSet) -> bool { self.map == other.map } + fn ne(&self, other: &HashSet) -> bool { self.map != other.map } +} + +impl Container for HashSet { + /// Return the number of elements in the set + fn len(&self) -> uint { self.map.len() } +} + +impl Mutable for HashSet { + /// Clear the set, removing all values. + fn clear(&mut self) { self.map.clear() } +} + +impl Set for HashSet { + /// 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) -> bool { + self.iter().all(|v| !other.contains(v)) + } + + /// Return true if the set is a subset of another + fn is_subset(&self, other: &HashSet) -> bool { + self.iter().all(|v| other.contains(v)) + } + + /// Return true if the set is a superset of another + fn is_superset(&self, other: &HashSet) -> bool { + other.is_subset(self) + } +} + +impl MutableSet for HashSet { + /// 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 HashSet { + /// Create an empty HashSet + pub fn new() -> HashSet { + 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 { + 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 { + 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>(&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 { + SetMoveItems {iter: self.map.buckets.move_iter()} + } + + /// Visit the values representing the difference + pub fn difference<'a>(&'a self, other: &'a HashSet) -> 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) + -> Chain, 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) + -> 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) + -> Chain, SetAlgebraItems<'a, T>> { + self.iter().chain(other.difference(self)) + } + +} + +impl Clone for HashSet { + fn clone(&self) -> HashSet { + HashSet { + map: self.map.clone() + } + } +} + +impl fmt::Show for HashSet { + 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 ToStr for HashSet { + fn to_str(&self) -> ~str { format!("{}", *self) } +} + +impl FromIterator for HashSet { + fn from_iterator>(iter: &mut T) -> HashSet { + let (lower, _) = iter.size_hint(); + let mut set = HashSet::with_capacity(lower); + set.extend(iter); + set + } +} + +impl Extendable for HashSet { + fn extend>(&mut self, iter: &mut T) { + for k in *iter { + self.insert(k); + } + } +} + +impl Default for HashSet { + fn default() -> HashSet { 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, &'a T), &'a T, + Zip>,SetItems<'a,T>>>; + +impl< + E: Encoder, + K: Encodable + Hash + IterBytes + Eq, + V: Encodable +> Encodable for HashMap { + fn encode(&self, e: &mut E) { + e.emit_map(self.len(), |e| { + let mut i = 0; + for (key, val) in self.iter() { + e.emit_map_elt_key(i, |e| key.encode(e)); + e.emit_map_elt_val(i, |e| val.encode(e)); + i += 1; + } + }) + } +} + +impl< + D: Decoder, + K: Decodable + Hash + IterBytes + Eq, + V: Decodable +> Decodable for HashMap { + fn decode(d: &mut D) -> HashMap { + d.read_map(|d, len| { + let mut map = HashMap::with_capacity(len); + for i in range(0u, len) { + let key = d.read_map_elt_key(i, |d| Decodable::decode(d)); + let val = d.read_map_elt_val(i, |d| Decodable::decode(d)); + map.insert(key, val); + } + map + }) + } +} + +impl< + S: Encoder, + T: Encodable + Hash + IterBytes + Eq +> Encodable for HashSet { + fn encode(&self, s: &mut S) { + s.emit_seq(self.len(), |s| { + let mut i = 0; + for e in self.iter() { + s.emit_seq_elt(i, |s| e.encode(s)); + i += 1; + } + }) + } +} + +impl< + D: Decoder, + T: Decodable + Hash + IterBytes + Eq +> Decodable for HashSet { + fn decode(d: &mut D) -> HashSet { + d.read_seq(|d, len| { + let mut set = HashSet::with_capacity(len); + for i in range(0u, len) { + set.insert(d.read_seq_elt(i, |d| Decodable::decode(d))); + } + set + }) + } +} + +#[cfg(test)] +mod test_map { + use super::{HashMap, HashSet}; + use std::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 = 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 = 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 = 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::>(); + 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::>(); + 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 = 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 = HashMap::new(); + let empty: HashMap = 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), ~"{}"); + } + + struct StructWithToStrWithoutEqOrHash { + value: int + } + + impl fmt::Show for StructWithToStrWithoutEqOrHash { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f.buf, "s{}", self.value) + } + } + + #[test] + fn test_hashset() { + let mut set: HashSet = HashSet::new(); + let empty_set: HashSet = 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(), ~"{}"); + } + + #[test] + fn test_hashmap() { + let mut table: HashMap = HashMap::new(); + let empty: HashMap = 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(), ~"{}"); + } +} + +#[cfg(test)] +mod test_set { + use super::HashSet; + + #[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 = 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 = HashSet::new(); + let empty: HashSet = 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/libcollections/lib.rs b/src/libcollections/lib.rs index e3413adfe91..dd42c2a0dd0 100644 --- a/src/libcollections/lib.rs +++ b/src/libcollections/lib.rs @@ -27,21 +27,25 @@ pub use btree::BTree; pub use deque::Deque; pub use dlist::DList; pub use enum_set::EnumSet; +pub use hashmap::{HashMap, HashSet}; pub use list::List; pub use lru_cache::LruCache; pub use priority_queue::PriorityQueue; pub use ringbuf::RingBuf; pub use smallintmap::SmallIntMap; pub use treemap::{TreeMap, TreeSet}; +pub use trie::{TrieMap, TrieSet}; pub mod bitv; pub mod btree; pub mod deque; pub mod dlist; pub mod enum_set; +pub mod hashmap; pub mod list; pub mod lru_cache; pub mod priority_queue; pub mod ringbuf; pub mod smallintmap; pub mod treemap; +pub mod trie; diff --git a/src/libcollections/lru_cache.rs b/src/libcollections/lru_cache.rs index de7b511fd41..d05d2f2d981 100644 --- a/src/libcollections/lru_cache.rs +++ b/src/libcollections/lru_cache.rs @@ -38,11 +38,12 @@ //! ``` use std::container::Container; -use std::hashmap::HashMap; use std::to_bytes::Cb; use std::ptr; use std::cast; +use HashMap; + struct KeyRef { k: *K } struct LruEntry { diff --git a/src/libcollections/trie.rs b/src/libcollections/trie.rs new file mode 100644 index 00000000000..022a64fbb7a --- /dev/null +++ b/src/libcollections/trie.rs @@ -0,0 +1,1094 @@ +// 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 or the MIT license +// , 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 std::mem; +use std::uint; +use std::mem::init; +use std::vec; +use std::vec::{Items, MutItems}; + +use serialize::{Encodable, Decodable, Encoder, Decoder}; + +// 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 { + Internal(~TrieNode), + External(uint, T), + Nothing +} + +#[allow(missing_doc)] +pub struct TrieMap { + priv root: TrieNode, + priv length: uint +} + +impl Container for TrieMap { + /// Return the number of elements in the map + #[inline] + fn len(&self) -> uint { self.length } +} + +impl Mutable for TrieMap { + /// Clear the map, removing all values. + #[inline] + fn clear(&mut self) { + self.root = TrieNode::new(); + self.length = 0; + } +} + +impl Map for TrieMap { + /// 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 = &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 MutableMap for TrieMap { + /// 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 { + 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 { + 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 TrieMap { + /// Create an empty TrieMap + #[inline] + pub fn new() -> TrieMap { + 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 `& ` 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); + + 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); + (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 TrieMap { + // 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 FromIterator<(uint, T)> for TrieMap { + fn from_iterator>(iter: &mut Iter) -> TrieMap { + let mut map = TrieMap::new(); + map.extend(iter); + map + } +} + +impl Extendable<(uint, T)> for TrieMap { + fn extend>(&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 for TrieSet { + fn from_iterator>(iter: &mut Iter) -> TrieSet { + let mut set = TrieSet::new(); + set.extend(iter); + set + } +} + +impl Extendable for TrieSet { + fn extend>(&mut self, iter: &mut Iter) { + for elem in *iter { + self.insert(elem); + } + } +} + +struct TrieNode { + count: uint, + children: [Child, ..SIZE] +} + +impl TrieNode { + #[inline] + fn new() -> TrieNode { + // 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 TrieNode { + 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, 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(count: &mut uint, child: &mut Child, key: uint, value: T, + idx: uint) -> Option { + // 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(count: &mut uint, child: &mut Child, key: uint, + idx: uint) -> Option { + 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>, .. 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>, .. 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) { + (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 for SetItems<'a> { + fn next(&mut self) -> Option { + self.iter.next().map(|(key, _)| key) + } + + fn size_hint(&self) -> (uint, Option) { + self.iter.size_hint() + } +} + +impl< + E: Encoder, + V: Encodable +> Encodable for TrieMap { + fn encode(&self, e: &mut E) { + e.emit_map(self.len(), |e| { + for (i, (key, val)) in self.iter().enumerate() { + e.emit_map_elt_key(i, |e| key.encode(e)); + e.emit_map_elt_val(i, |e| val.encode(e)); + } + }); + } +} + +impl< + D: Decoder, + V: Decodable +> Decodable for TrieMap { + fn decode(d: &mut D) -> TrieMap { + d.read_map(|d, len| { + let mut map = TrieMap::new(); + for i in range(0u, len) { + let key = d.read_map_elt_key(i, |d| Decodable::decode(d)); + let val = d.read_map_elt_val(i, |d| Decodable::decode(d)); + map.insert(key, val); + } + map + }) + } +} + +impl Encodable for TrieSet { + fn encode(&self, s: &mut S) { + s.emit_seq(self.len(), |s| { + for (i, e) in self.iter().enumerate() { + s.emit_seq_elt(i, |s| e.encode(s)); + } + }) + } +} + +impl Decodable for TrieSet { + fn decode(d: &mut D) -> TrieSet { + d.read_seq(|d, len| { + let mut set = TrieSet::new(); + for i in range(0u, len) { + set.insert(d.read_seq_elt(i, |d| Decodable::decode(d))); + } + set + }) + } +} + +#[cfg(test)] +mod test_map { + use super::{TrieMap, TrieNode, Internal, External}; + use std::iter::range_step; + use std::uint; + + fn check_integrity(trie: &TrieNode) { + 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); + } + + #[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 = 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 = 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 = 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 = 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 = 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 = 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 super::TrieMap; + use std::rand::{weak_rng, Rng}; + use self::test::BenchHarness; + + #[bench] + fn bench_iter_small(bh: &mut BenchHarness) { + let mut m = TrieMap::::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::::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::::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::::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::() & 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::() & 0xff_ff, ()); + } + }) + } +} + +#[cfg(test)] +mod test_set { + use super::TrieSet; + use std::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/libextra/json.rs b/src/libextra/json.rs index 370d1026c41..4cc210aaa6c 100644 --- a/src/libextra/json.rs +++ b/src/libextra/json.rs @@ -235,7 +235,7 @@ fn main() { use std::char; use std::f64; -use std::hashmap::HashMap; +use collections::HashMap; use std::io; use std::io::MemWriter; use std::num; diff --git a/src/libextra/stats.rs b/src/libextra/stats.rs index 6738275c4c1..d791e1a2988 100644 --- a/src/libextra/stats.rs +++ b/src/libextra/stats.rs @@ -12,10 +12,10 @@ use std::cmp; use std::hash_old::Hash; -use std::hashmap; use std::io; use std::mem; use std::num; +use collections::hashmap; // NB: this can probably be rewritten in terms of num::Num // to be less f64-specific. diff --git a/src/libextra/url.rs b/src/libextra/url.rs index 4580dd93098..6353e7e1159 100644 --- a/src/libextra/url.rs +++ b/src/libextra/url.rs @@ -14,7 +14,7 @@ use std::io::BufReader; use std::cmp::Eq; -use std::hashmap::HashMap; +use collections::HashMap; use std::to_bytes; use std::uint; @@ -957,7 +957,7 @@ mod tests { use super::*; - use std::hashmap::HashMap; + use collections::HashMap; #[test] fn test_url_parse() { diff --git a/src/libnative/io/timer_other.rs b/src/libnative/io/timer_other.rs index 3a060194a69..9f332adb27b 100644 --- a/src/libnative/io/timer_other.rs +++ b/src/libnative/io/timer_other.rs @@ -49,7 +49,6 @@ #[allow(non_camel_case_types)]; use std::comm::Data; -use std::hashmap::HashMap; use std::libc; use std::mem; use std::os; @@ -105,7 +104,7 @@ fn helper(input: libc::c_int, messages: Port) { // sorted list, and dead timers are those which have expired, but ownership // hasn't yet been transferred back to the timer itself. let mut active: ~[~Inner] = ~[]; - let mut dead = HashMap::new(); + let mut dead = ~[]; // inserts a timer into an array of timers (sorted by firing time) fn insert(t: ~Inner, active: &mut ~[~Inner]) { @@ -116,7 +115,7 @@ fn helper(input: libc::c_int, messages: Port) { } // signals the first requests in the queue, possible re-enqueueing it. - fn signal(active: &mut ~[~Inner], dead: &mut HashMap) { + fn signal(active: &mut ~[~Inner], dead: &mut ~[(uint, ~Inner)]) { let mut timer = match active.shift() { Some(timer) => timer, None => return }; @@ -127,7 +126,7 @@ fn helper(input: libc::c_int, messages: Port) { insert(timer, active); } else { drop(chan); - dead.insert(timer.id, timer); + dead.push((timer.id, timer)); } } @@ -172,8 +171,12 @@ fn helper(input: libc::c_int, messages: Port) { Data(NewTimer(timer)) => insert(timer, &mut active), Data(RemoveTimer(id, ack)) => { - match dead.pop(&id) { - Some(i) => { ack.send(i); continue } + match dead.iter().position(|&(i, _)| id == i) { + Some(i) => { + let (_, i) = dead.remove(i).unwrap(); + ack.send(i); + continue + } None => {} } let i = active.iter().position(|i| i.id == id); diff --git a/src/libnative/io/timer_timerfd.rs b/src/libnative/io/timer_timerfd.rs index b1ae5820888..baafe3f4850 100644 --- a/src/libnative/io/timer_timerfd.rs +++ b/src/libnative/io/timer_timerfd.rs @@ -35,7 +35,6 @@ use std::libc; use std::ptr; use std::os; use std::rt::rtio; -use std::hashmap::HashMap; use std::mem; use io::file::FileDesc; @@ -78,7 +77,7 @@ fn helper(input: libc::c_int, messages: Port) { add(efd, input); let events: [imp::epoll_event, ..16] = unsafe { mem::init() }; - let mut map: HashMap, bool)> = HashMap::new(); + let mut list: ~[(libc::c_int, Chan<()>, bool)] = ~[]; 'outer: loop { let n = match unsafe { imp::epoll_wait(efd, events.as_ptr(), @@ -107,13 +106,17 @@ fn helper(input: libc::c_int, messages: Port) { // FIXME: should this perform a send() this number of // times? let _ = FileDesc::new(fd, false).inner_read(bits).unwrap(); - let remove = { - match map.find(&fd).expect("fd unregistered") { - &(ref c, oneshot) => !c.try_send(()) || oneshot + let (remove, i) = { + match list.bsearch(|&(f, _, _)| f.cmp(&fd)) { + Some(i) => { + let (_, ref c, oneshot) = list[i]; + (!c.try_send(()) || oneshot, i) + } + None => fail!("fd not active: {}", fd), } }; if remove { - map.remove(&fd); + drop(list.remove(i)); del(efd, fd); } } @@ -128,8 +131,17 @@ fn helper(input: libc::c_int, messages: Port) { // If we haven't previously seen the file descriptor, then // we need to add it to the epoll set. - if map.insert(fd, (chan, one)) { - add(efd, fd); + match list.bsearch(|&(f, _, _)| f.cmp(&fd)) { + Some(i) => { + drop(mem::replace(&mut list[i], (fd, chan, one))); + } + None => { + match list.iter().position(|&(f, _, _)| f >= fd) { + Some(i) => list.insert(i, (fd, chan, one)), + None => list.push((fd, chan, one)), + } + add(efd, fd); + } } // Update the timerfd's time value now that we have control @@ -141,14 +153,18 @@ fn helper(input: libc::c_int, messages: Port) { } Data(RemoveTimer(fd, chan)) => { - if map.remove(&fd) { - del(efd, fd); + match list.bsearch(|&(f, _, _)| f.cmp(&fd)) { + Some(i) => { + drop(list.remove(i)); + del(efd, fd); + } + None => {} } chan.send(()); } Data(Shutdown) => { - assert!(map.len() == 0); + assert!(list.len() == 0); break 'outer; } diff --git a/src/librustc/back/rpath.rs b/src/librustc/back/rpath.rs index 43ecbccfd79..68deb0a9416 100644 --- a/src/librustc/back/rpath.rs +++ b/src/librustc/back/rpath.rs @@ -13,7 +13,7 @@ use driver::session; use metadata::cstore; use metadata::filesearch; -use std::hashmap::HashSet; +use collections::HashSet; use std::{os, vec}; use syntax::abi; diff --git a/src/librustc/driver/driver.rs b/src/librustc/driver/driver.rs index f2d82bfdf3c..1f7a75da345 100644 --- a/src/librustc/driver/driver.rs +++ b/src/librustc/driver/driver.rs @@ -31,12 +31,12 @@ use extra::json; use serialize::Encodable; use std::cell::{Cell, RefCell}; -use std::hashmap::{HashMap,HashSet}; use std::io; use std::io::fs; use std::io::MemReader; use std::os; use std::vec; +use collections::{HashMap, HashSet}; use getopts::{optopt, optmulti, optflag, optflagopt}; use getopts; use syntax::ast; diff --git a/src/librustc/driver/session.rs b/src/librustc/driver/session.rs index d43a68e4f87..e023190e5f4 100644 --- a/src/librustc/driver/session.rs +++ b/src/librustc/driver/session.rs @@ -26,7 +26,7 @@ use syntax::{abi, ast, codemap}; use syntax; use std::cell::{Cell, RefCell}; -use std::hashmap::{HashMap,HashSet}; +use collections::{HashMap,HashSet}; pub struct Config { os: abi::Os, diff --git a/src/librustc/lib/llvm.rs b/src/librustc/lib/llvm.rs index d565e378af4..3bee339e3cc 100644 --- a/src/librustc/lib/llvm.rs +++ b/src/librustc/lib/llvm.rs @@ -13,7 +13,7 @@ use std::c_str::ToCStr; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; use std::libc::{c_uint, c_ushort, c_void, free}; use std::str::raw::from_c_str; diff --git a/src/librustc/metadata/creader.rs b/src/librustc/metadata/creader.rs index d361ee56936..9f14b571d82 100644 --- a/src/librustc/metadata/creader.rs +++ b/src/librustc/metadata/creader.rs @@ -21,7 +21,7 @@ use metadata::loader; use metadata::loader::Os; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::ast; use syntax::abi; use syntax::attr; diff --git a/src/librustc/metadata/cstore.rs b/src/librustc/metadata/cstore.rs index 8c2c05b96cd..1a8b86b3510 100644 --- a/src/librustc/metadata/cstore.rs +++ b/src/librustc/metadata/cstore.rs @@ -17,7 +17,7 @@ use metadata::decoder; use metadata::loader; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::ast; use syntax::parse::token::IdentInterner; diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs index 210c1f2a875..a32cdbe98a1 100644 --- a/src/librustc/metadata/encoder.rs +++ b/src/librustc/metadata/encoder.rs @@ -27,9 +27,9 @@ use serialize::Encodable; use std::cast; use std::cell::{Cell, RefCell}; use std::hash_old::Hash; -use std::hashmap::{HashMap, HashSet}; use std::io::MemWriter; use std::str; +use collections::{HashMap, HashSet}; use syntax::abi::AbiSet; use syntax::ast::*; use syntax::ast; diff --git a/src/librustc/metadata/filesearch.rs b/src/librustc/metadata/filesearch.rs index 42231ce1b47..2ab3f8a147e 100644 --- a/src/librustc/metadata/filesearch.rs +++ b/src/librustc/metadata/filesearch.rs @@ -14,7 +14,7 @@ use std::cell::RefCell; use std::option; use std::os; use std::io::fs; -use std::hashmap::HashSet; +use collections::HashSet; pub enum FileMatch { FileMatches, FileDoesntMatch } diff --git a/src/librustc/metadata/loader.rs b/src/librustc/metadata/loader.rs index 3558166128b..e7d97f03913 100644 --- a/src/librustc/metadata/loader.rs +++ b/src/librustc/metadata/loader.rs @@ -26,13 +26,13 @@ use syntax::attr::AttrMetaMethods; use std::c_str::ToCStr; use std::cast; -use std::hashmap::{HashMap, HashSet}; use std::cmp; use std::io; use std::os::consts::{macos, freebsd, linux, android, win32}; use std::str; use std::vec; +use collections::{HashMap, HashSet}; use flate; use time; diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs index db0bcf7d029..c9b234743fa 100644 --- a/src/librustc/metadata/tyencode.rs +++ b/src/librustc/metadata/tyencode.rs @@ -14,7 +14,7 @@ #[allow(non_camel_case_types)]; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; use std::io; use std::io::MemWriter; use std::str; diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs index c7157ad1703..34008fb84df 100644 --- a/src/librustc/middle/borrowck/mod.rs +++ b/src/librustc/middle/borrowck/mod.rs @@ -21,7 +21,7 @@ use middle::dataflow::DataFlowOperator; use util::ppaux::{note_and_explain_region, Repr, UserString}; use std::cell::{Cell, RefCell}; -use std::hashmap::HashMap; +use collections::HashMap; use std::ops::{BitOr, BitAnd}; use std::result::{Result}; use syntax::ast; diff --git a/src/librustc/middle/borrowck/move_data.rs b/src/librustc/middle/borrowck/move_data.rs index 34efcacc44b..5034976c9f9 100644 --- a/src/librustc/middle/borrowck/move_data.rs +++ b/src/librustc/middle/borrowck/move_data.rs @@ -16,8 +16,8 @@ comments in the section "Moves and initialization" and in `doc.rs`. */ use std::cell::RefCell; -use std::hashmap::{HashMap, HashSet}; use std::uint; +use collections::{HashMap, HashSet}; use middle::borrowck::*; use middle::dataflow::DataFlowContext; use middle::dataflow::DataFlowOperator; diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs index 6ca779906e2..d4eb72ac577 100644 --- a/src/librustc/middle/cfg/construct.rs +++ b/src/librustc/middle/cfg/construct.rs @@ -12,7 +12,7 @@ use middle::cfg::*; use middle::graph; use middle::typeck; use middle::ty; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::ast; use syntax::ast_util; use syntax::opt_vec; diff --git a/src/librustc/middle/cfg/mod.rs b/src/librustc/middle/cfg/mod.rs index cc00ab921b4..b0ee26f6f23 100644 --- a/src/librustc/middle/cfg/mod.rs +++ b/src/librustc/middle/cfg/mod.rs @@ -18,7 +18,7 @@ Uses `Graph` as the underlying representation. use middle::graph; use middle::ty; use middle::typeck; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::ast; use syntax::opt_vec::OptVec; diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs index 9cf055cad9d..5322aac8c23 100644 --- a/src/librustc/middle/const_eval.rs +++ b/src/librustc/middle/const_eval.rs @@ -24,7 +24,7 @@ use syntax::visit; use syntax::{ast, ast_map, ast_util}; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; use std::rc::Rc; // diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs index 8a504f07b73..ba79d71bcb6 100644 --- a/src/librustc/middle/dataflow.rs +++ b/src/librustc/middle/dataflow.rs @@ -20,7 +20,7 @@ use std::io; use std::uint; use std::vec; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::ast; use syntax::ast_util; use syntax::ast_util::IdRange; diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs index 39b232eed33..9cc5a49600f 100644 --- a/src/librustc/middle/dead.rs +++ b/src/librustc/middle/dead.rs @@ -17,7 +17,7 @@ use middle::privacy; use middle::ty; use middle::typeck; -use std::hashmap::HashSet; +use collections::HashSet; use syntax::ast; use syntax::ast_map; use syntax::ast_util::{local_def, def_id_of_def, is_local}; diff --git a/src/librustc/middle/freevars.rs b/src/librustc/middle/freevars.rs index 4c488067ad3..9ff67377c59 100644 --- a/src/librustc/middle/freevars.rs +++ b/src/librustc/middle/freevars.rs @@ -16,7 +16,7 @@ use middle::resolve; use middle::ty; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::codemap::Span; use syntax::{ast, ast_util}; use syntax::visit; diff --git a/src/librustc/middle/lang_items.rs b/src/librustc/middle/lang_items.rs index 290e901d1a3..0194d4a2510 100644 --- a/src/librustc/middle/lang_items.rs +++ b/src/librustc/middle/lang_items.rs @@ -30,7 +30,7 @@ use syntax::parse::token::InternedString; use syntax::visit::Visitor; use syntax::visit; -use std::hashmap::HashMap; +use collections::HashMap; use std::iter::Enumerate; use std::vec; diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs index 911b6df10a6..36ed4913cdb 100644 --- a/src/librustc/middle/lint.rs +++ b/src/librustc/middle/lint.rs @@ -49,7 +49,7 @@ use std::to_str::ToStr; use util::ppaux::{ty_to_str}; use std::cmp; -use std::hashmap::HashMap; +use collections::HashMap; use std::i16; use std::i32; use std::i64; diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs index efe88b7847f..3b8eb682065 100644 --- a/src/librustc/middle/liveness.rs +++ b/src/librustc/middle/liveness.rs @@ -111,7 +111,7 @@ use middle::moves; use std::cast::transmute; use std::cell::{Cell, RefCell}; -use std::hashmap::HashMap; +use collections::HashMap; use std::io; use std::str; use std::to_str; diff --git a/src/librustc/middle/moves.rs b/src/librustc/middle/moves.rs index 32cb7ca57da..1705e3a5160 100644 --- a/src/librustc/middle/moves.rs +++ b/src/librustc/middle/moves.rs @@ -137,8 +137,8 @@ use util::common::indenter; use util::ppaux::UserString; use std::cell::RefCell; -use std::hashmap::{HashSet, HashMap}; use std::rc::Rc; +use collections::{HashSet, HashMap}; use syntax::ast::*; use syntax::ast_util; use syntax::visit; diff --git a/src/librustc/middle/pat_util.rs b/src/librustc/middle/pat_util.rs index 50096c012be..d352771ef50 100644 --- a/src/librustc/middle/pat_util.rs +++ b/src/librustc/middle/pat_util.rs @@ -11,7 +11,7 @@ use middle::resolve; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::ast::*; use syntax::ast_util::{path_to_ident, walk_pat}; use syntax::codemap::Span; diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs index 7578636b2b6..1899b52cca8 100644 --- a/src/librustc/middle/privacy.rs +++ b/src/librustc/middle/privacy.rs @@ -12,8 +12,8 @@ //! outside their scopes. This pass will also generate a set of exported items //! which are available for use externally when compiled as a library. -use std::hashmap::{HashSet, HashMap}; use std::mem::replace; +use collections::{HashSet, HashMap}; use metadata::csearch; use middle::resolve; diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs index 547d78219a5..26104331a10 100644 --- a/src/librustc/middle/reachable.rs +++ b/src/librustc/middle/reachable.rs @@ -20,7 +20,7 @@ use middle::typeck; use middle::privacy; use std::cell::RefCell; -use std::hashmap::HashSet; +use collections::HashSet; use syntax::ast; use syntax::ast_map; use syntax::ast_util::{def_id_of_def, is_local}; diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs index 9b1473cbd8e..c06ad66f606 100644 --- a/src/librustc/middle/region.rs +++ b/src/librustc/middle/region.rs @@ -26,7 +26,7 @@ use middle::ty::{FreeRegion}; use middle::ty; use std::cell::RefCell; -use std::hashmap::{HashMap, HashSet}; +use collections::{HashMap, HashSet}; use syntax::codemap::Span; use syntax::{ast, visit}; use syntax::visit::{Visitor, FnKind}; diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs index 066e4d2b313..72967ff8195 100644 --- a/src/librustc/middle/resolve.rs +++ b/src/librustc/middle/resolve.rs @@ -31,8 +31,8 @@ use syntax::visit::Visitor; use std::cell::{Cell, RefCell}; use std::uint; -use std::hashmap::{HashMap, HashSet}; use std::mem::replace; +use collections::{HashMap, HashSet}; // Definition mapping pub type DefMap = @RefCell>; diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs index b3a975a13e4..4e780f45111 100644 --- a/src/librustc/middle/resolve_lifetime.rs +++ b/src/librustc/middle/resolve_lifetime.rs @@ -19,7 +19,7 @@ use driver::session; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::ast; use syntax::codemap::Span; use syntax::opt_vec::OptVec; diff --git a/src/librustc/middle/trans/_match.rs b/src/librustc/middle/trans/_match.rs index 0aa8393e79d..5b2f9d87ca8 100644 --- a/src/librustc/middle/trans/_match.rs +++ b/src/librustc/middle/trans/_match.rs @@ -223,7 +223,7 @@ use util::common::indenter; use util::ppaux::{Repr, vec_map_to_str}; use std::cell::Cell; -use std::hashmap::HashMap; +use collections::HashMap; use std::vec; use syntax::ast; use syntax::ast::Ident; diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs index c7d09e31855..d920378f508 100644 --- a/src/librustc/middle/trans/base.rs +++ b/src/librustc/middle/trans/base.rs @@ -74,7 +74,7 @@ use util::sha2::Sha256; use arena::TypedArena; use std::c_str::ToCStr; use std::cell::{Cell, RefCell}; -use std::hashmap::HashMap; +use collections::HashMap; use std::libc::c_uint; use std::local_data; use syntax::abi::{X86, X86_64, Arm, Mips, Rust, RustIntrinsic, OsWin32}; diff --git a/src/librustc/middle/trans/builder.rs b/src/librustc/middle/trans/builder.rs index 9dd92fbc45c..4fa807ca608 100644 --- a/src/librustc/middle/trans/builder.rs +++ b/src/librustc/middle/trans/builder.rs @@ -17,8 +17,8 @@ use middle::trans::base; use middle::trans::common::*; use middle::trans::machine::llalign_of_pref; use middle::trans::type_::Type; -use std::hashmap::HashMap; use std::libc::{c_uint, c_ulonglong, c_char}; +use collections::HashMap; use syntax::codemap::Span; pub struct Builder<'a> { diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs index d9e929c2501..8ac885d183f 100644 --- a/src/librustc/middle/trans/common.rs +++ b/src/librustc/middle/trans/common.rs @@ -33,7 +33,7 @@ use util::ppaux::Repr; use arena::TypedArena; use std::c_str::ToCStr; use std::cell::{Cell, RefCell}; -use std::hashmap::HashMap; +use collections::HashMap; use std::libc::{c_uint, c_longlong, c_ulonglong, c_char}; use syntax::ast::Ident; use syntax::ast; diff --git a/src/librustc/middle/trans/context.rs b/src/librustc/middle/trans/context.rs index 2260ddea3c2..b90fc4f6bbf 100644 --- a/src/librustc/middle/trans/context.rs +++ b/src/librustc/middle/trans/context.rs @@ -29,9 +29,9 @@ use util::sha2::Sha256; use std::cell::{Cell, RefCell}; use std::c_str::ToCStr; -use std::hashmap::{HashMap, HashSet}; use std::local_data; use std::libc::c_uint; +use collections::{HashMap, HashSet}; use syntax::ast; use syntax::parse::token::InternedString; diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs index 6a9ee514f8f..564aab5d31d 100644 --- a/src/librustc/middle/trans/debuginfo.rs +++ b/src/librustc/middle/trans/debuginfo.rs @@ -142,8 +142,8 @@ use util::ppaux; use std::c_str::{CString, ToCStr}; use std::cell::{Cell, RefCell}; -use std::hashmap::HashMap; -use std::hashmap::HashSet; +use collections::HashMap; +use collections::HashSet; use std::libc::{c_uint, c_ulonglong, c_longlong}; use std::ptr; use std::sync::atomics; diff --git a/src/librustc/middle/trans/expr.rs b/src/librustc/middle/trans/expr.rs index 99852e446cc..e3724ab4d11 100644 --- a/src/librustc/middle/trans/expr.rs +++ b/src/librustc/middle/trans/expr.rs @@ -70,7 +70,7 @@ use middle::trans::machine::llsize_of; use middle::trans::type_::Type; -use std::hashmap::HashMap; +use collections::HashMap; use std::vec; use syntax::ast; use syntax::ast_map; diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs index 6f20de57fc7..c7aedec4b48 100644 --- a/src/librustc/middle/ty.rs +++ b/src/librustc/middle/ty.rs @@ -33,12 +33,12 @@ use util::common::{indenter}; use std::cast; use std::cell::{Cell, RefCell}; use std::cmp; -use std::hashmap::{HashMap, HashSet}; use std::ops; use std::rc::Rc; use std::to_bytes; use std::to_str::ToStr; use std::vec; +use collections::{HashMap, HashSet}; use syntax::ast::*; use syntax::ast_util::{is_local, lit_is_str}; use syntax::ast_util; @@ -460,7 +460,7 @@ pub struct param_ty { } /// Representation of regions: -#[deriving(Clone, Eq, IterBytes, Encodable, Decodable, ToStr)] +#[deriving(Clone, Eq, IterBytes, Encodable, Decodable, ToStr, Show)] pub enum Region { // Region bound in a type or fn declaration which will be // substituted 'early' -- that is, at the same time when type @@ -620,13 +620,13 @@ impl Region { } } -#[deriving(Clone, Eq, TotalOrd, TotalEq, IterBytes, Encodable, Decodable, ToStr)] +#[deriving(Clone, Eq, TotalOrd, TotalEq, IterBytes, Encodable, Decodable, ToStr, Show)] pub struct FreeRegion { scope_id: NodeId, bound_region: BoundRegion } -#[deriving(Clone, Eq, TotalEq, TotalOrd, IterBytes, Encodable, Decodable, ToStr)] +#[deriving(Clone, Eq, TotalEq, TotalOrd, IterBytes, Encodable, Decodable, ToStr, Show)] pub enum BoundRegion { /// An anonymous region parameter for a given fn (&T) BrAnon(uint), @@ -869,7 +869,7 @@ pub struct IntVid(uint); #[deriving(Clone, Eq, IterBytes)] pub struct FloatVid(uint); -#[deriving(Clone, Eq, Encodable, Decodable, IterBytes)] +#[deriving(Clone, Eq, Encodable, Decodable, IterBytes, Show)] pub struct RegionVid { id: uint } @@ -881,7 +881,7 @@ pub enum InferTy { FloatVar(FloatVid) } -#[deriving(Clone, Encodable, Decodable, IterBytes, ToStr)] +#[deriving(Clone, Encodable, Decodable, IterBytes, ToStr, Show)] pub enum InferRegion { ReVar(RegionVid), ReSkolemized(uint, BoundRegion) diff --git a/src/librustc/middle/typeck/check/_match.rs b/src/librustc/middle/typeck/check/_match.rs index 160b6f5ec4e..6620f8502ed 100644 --- a/src/librustc/middle/typeck/check/_match.rs +++ b/src/librustc/middle/typeck/check/_match.rs @@ -19,7 +19,7 @@ use middle::typeck::check::{structure_of, valid_range_bounds}; use middle::typeck::infer; use middle::typeck::require_same_types; -use std::hashmap::{HashMap, HashSet}; +use collections::{HashMap, HashSet}; use syntax::ast; use syntax::ast_util; use syntax::parse::token; diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs index fca89f3f91c..3837c0b55d1 100644 --- a/src/librustc/middle/typeck/check/method.rs +++ b/src/librustc/middle/typeck/check/method.rs @@ -98,7 +98,7 @@ use util::common::indenter; use util::ppaux::Repr; use std::cell::RefCell; -use std::hashmap::HashSet; +use collections::HashSet; use std::result; use std::vec; use syntax::ast::{DefId, SelfValue, SelfRegion}; diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs index 761a8b81a46..ac17d327166 100644 --- a/src/librustc/middle/typeck/check/mod.rs +++ b/src/librustc/middle/typeck/check/mod.rs @@ -114,7 +114,7 @@ use util::ppaux; use util::ppaux::{UserString, Repr}; use std::cell::{Cell, RefCell}; -use std::hashmap::HashMap; +use collections::HashMap; use std::mem::replace; use std::result; use std::vec; diff --git a/src/librustc/middle/typeck/check/regionmanip.rs b/src/librustc/middle/typeck/check/regionmanip.rs index 0b04db88234..9192bdfda29 100644 --- a/src/librustc/middle/typeck/check/regionmanip.rs +++ b/src/librustc/middle/typeck/check/regionmanip.rs @@ -13,7 +13,7 @@ use middle::ty; use middle::ty_fold; use middle::ty_fold::TypeFolder; -use std::hashmap::HashMap; +use collections::HashMap; use util::ppaux::Repr; use util::ppaux; @@ -39,7 +39,7 @@ pub fn replace_bound_regions_in_fn_sig( }); ty_fold::super_fold_sig(&mut f, fn_sig) }; - debug!("resulting map: {}", map.to_str()); + debug!("resulting map: {}", map); (map, fn_sig) } diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs index ba4300b58a1..588dbec8a83 100644 --- a/src/librustc/middle/typeck/check/vtable.rs +++ b/src/librustc/middle/typeck/check/vtable.rs @@ -27,7 +27,7 @@ use util::ppaux; use util::ppaux::Repr; use std::cell::RefCell; -use std::hashmap::HashSet; +use collections::HashSet; use std::result; use syntax::ast; use syntax::ast_util; diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs index a9dffeb670f..c22b3c81458 100644 --- a/src/librustc/middle/typeck/coherence.rs +++ b/src/librustc/middle/typeck/coherence.rs @@ -47,7 +47,7 @@ use syntax::parse::token; use syntax::visit; use std::cell::RefCell; -use std::hashmap::HashSet; +use collections::HashSet; use std::rc::Rc; use std::vec; diff --git a/src/librustc/middle/typeck/infer/glb.rs b/src/librustc/middle/typeck/infer/glb.rs index 4af6364642e..039ea995821 100644 --- a/src/librustc/middle/typeck/infer/glb.rs +++ b/src/librustc/middle/typeck/infer/glb.rs @@ -24,7 +24,7 @@ use middle::typeck::infer::fold_regions_in_sig; use syntax::ast::{Many, Once, MutImmutable, MutMutable}; use syntax::ast::{ExternFn, ImpureFn, UnsafeFn, NodeId}; use syntax::ast::{Onceness, Purity}; -use std::hashmap::HashMap; +use collections::HashMap; use util::common::{indenter}; use util::ppaux::mt_to_str; diff --git a/src/librustc/middle/typeck/infer/lattice.rs b/src/librustc/middle/typeck/infer/lattice.rs index fa40fa6a064..265ac7b0cf0 100644 --- a/src/librustc/middle/typeck/infer/lattice.rs +++ b/src/librustc/middle/typeck/infer/lattice.rs @@ -43,7 +43,7 @@ use middle::typeck::infer::lub::Lub; use middle::typeck::infer::unify::*; use middle::typeck::infer::sub::Sub; use middle::typeck::infer::to_str::InferStr; -use std::hashmap::HashMap; +use collections::HashMap; use util::common::indenter; pub trait LatticeValue { diff --git a/src/librustc/middle/typeck/infer/lub.rs b/src/librustc/middle/typeck/infer/lub.rs index dc6df333276..fd6950ee49e 100644 --- a/src/librustc/middle/typeck/infer/lub.rs +++ b/src/librustc/middle/typeck/infer/lub.rs @@ -21,7 +21,7 @@ use middle::typeck::infer::to_str::InferStr; use middle::typeck::infer::{cres, InferCtxt}; use middle::typeck::infer::fold_regions_in_sig; use middle::typeck::infer::{TypeTrace, Subtype}; -use std::hashmap::HashMap; +use collections::HashMap; use syntax::ast::{Many, Once, NodeId}; use syntax::ast::{ExternFn, ImpureFn, UnsafeFn}; use syntax::ast::{Onceness, Purity}; diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs index abff3b68395..dceef9e38d5 100644 --- a/src/librustc/middle/typeck/infer/mod.rs +++ b/src/librustc/middle/typeck/infer/mod.rs @@ -37,7 +37,7 @@ use middle::typeck::infer::to_str::InferStr; use middle::typeck::infer::unify::{ValsAndBindings, Root}; use middle::typeck::infer::error_reporting::ErrorReporting; use std::cell::{Cell, RefCell}; -use std::hashmap::HashMap; +use collections::HashMap; use std::result; use std::vec; use syntax::ast::{MutImmutable, MutMutable}; diff --git a/src/librustc/middle/typeck/infer/region_inference/mod.rs b/src/librustc/middle/typeck/infer/region_inference/mod.rs index bbd9d8e1c4d..98391436aa3 100644 --- a/src/librustc/middle/typeck/infer/region_inference/mod.rs +++ b/src/librustc/middle/typeck/infer/region_inference/mod.rs @@ -25,9 +25,9 @@ use util::common::indenter; use util::ppaux::{Repr}; use std::cell::{Cell, RefCell}; -use std::hashmap::{HashMap, HashSet}; use std::uint; use std::vec; +use collections::{HashMap, HashSet}; use syntax::ast; use syntax::opt_vec; use syntax::opt_vec::OptVec; diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs index 4f2c8966c50..d4e2660b4a0 100644 --- a/src/librustc/middle/typeck/mod.rs +++ b/src/librustc/middle/typeck/mod.rs @@ -70,7 +70,7 @@ use util::ppaux::Repr; use util::ppaux; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; use std::rc::Rc; use collections::List; use collections::list; diff --git a/src/librustc/middle/typeck/variance.rs b/src/librustc/middle/typeck/variance.rs index 57c7f6752a8..47c40514e6c 100644 --- a/src/librustc/middle/typeck/variance.rs +++ b/src/librustc/middle/typeck/variance.rs @@ -192,7 +192,7 @@ represents the "variance transform" as defined in the paper: */ -use std::hashmap::HashMap; +use collections::HashMap; use arena; use arena::Arena; use middle::ty; diff --git a/src/librustdoc/core.rs b/src/librustdoc/core.rs index 585b18a8821..f4062195978 100644 --- a/src/librustdoc/core.rs +++ b/src/librustdoc/core.rs @@ -21,7 +21,7 @@ use syntax; use std::cell::RefCell; use std::os; use std::local_data; -use std::hashmap::{HashSet}; +use collections::HashSet; use visit_ast::RustdocVisitor; use clean; diff --git a/src/librustdoc/html/render.rs b/src/librustdoc/html/render.rs index 0f017a04da3..ab4bf5403ad 100644 --- a/src/librustdoc/html/render.rs +++ b/src/librustdoc/html/render.rs @@ -34,12 +34,12 @@ //! both occur before the crate is rendered. use std::fmt; -use std::hashmap::{HashMap, HashSet}; use std::local_data; use std::io; use std::io::{fs, File, BufferedWriter}; use std::str; use std::vec; +use collections::{HashMap, HashSet}; use sync::Arc; use extra::json::ToJson; diff --git a/src/librustdoc/passes.rs b/src/librustdoc/passes.rs index 4fc47d64e57..b8cc271ca9c 100644 --- a/src/librustdoc/passes.rs +++ b/src/librustdoc/passes.rs @@ -9,7 +9,7 @@ // except according to those terms. use std::cmp; -use std::hashmap::HashSet; +use collections::HashSet; use std::local_data; use std::uint; use syntax::ast; diff --git a/src/librustdoc/test.rs b/src/librustdoc/test.rs index c0f8d2696ca..354b5cb0f14 100644 --- a/src/librustdoc/test.rs +++ b/src/librustdoc/test.rs @@ -9,7 +9,7 @@ // except according to those terms. use std::cell::RefCell; -use std::hashmap::HashSet; +use collections::HashSet; use std::local_data; use std::os; use std::run; diff --git a/src/libserialize/serialize.rs b/src/libserialize/serialize.rs index f350bb0761f..a94df9975a4 100644 --- a/src/libserialize/serialize.rs +++ b/src/libserialize/serialize.rs @@ -14,10 +14,7 @@ Core encoding and decoding interfaces. */ -use std::hash_old::Hash; -use std::hashmap::{HashMap, HashSet}; use std::rc::Rc; -use std::trie::{TrieMap, TrieSet}; use std::vec; use std::vec_ng::Vec; @@ -628,124 +625,6 @@ impl< } } -impl< - E: Encoder, - K: Encodable + Hash + IterBytes + Eq, - V: Encodable -> Encodable for HashMap { - fn encode(&self, e: &mut E) { - e.emit_map(self.len(), |e| { - let mut i = 0; - for (key, val) in self.iter() { - e.emit_map_elt_key(i, |e| key.encode(e)); - e.emit_map_elt_val(i, |e| val.encode(e)); - i += 1; - } - }) - } -} - -impl< - D: Decoder, - K: Decodable + Hash + IterBytes + Eq, - V: Decodable -> Decodable for HashMap { - fn decode(d: &mut D) -> HashMap { - d.read_map(|d, len| { - let mut map = HashMap::with_capacity(len); - for i in range(0u, len) { - let key = d.read_map_elt_key(i, |d| Decodable::decode(d)); - let val = d.read_map_elt_val(i, |d| Decodable::decode(d)); - map.insert(key, val); - } - map - }) - } -} - -impl< - S: Encoder, - T: Encodable + Hash + IterBytes + Eq -> Encodable for HashSet { - fn encode(&self, s: &mut S) { - s.emit_seq(self.len(), |s| { - let mut i = 0; - for e in self.iter() { - s.emit_seq_elt(i, |s| e.encode(s)); - i += 1; - } - }) - } -} - -impl< - D: Decoder, - T: Decodable + Hash + IterBytes + Eq -> Decodable for HashSet { - fn decode(d: &mut D) -> HashSet { - d.read_seq(|d, len| { - let mut set = HashSet::with_capacity(len); - for i in range(0u, len) { - set.insert(d.read_seq_elt(i, |d| Decodable::decode(d))); - } - set - }) - } -} - -impl< - E: Encoder, - V: Encodable -> Encodable for TrieMap { - fn encode(&self, e: &mut E) { - e.emit_map(self.len(), |e| { - for (i, (key, val)) in self.iter().enumerate() { - e.emit_map_elt_key(i, |e| key.encode(e)); - e.emit_map_elt_val(i, |e| val.encode(e)); - } - }); - } -} - -impl< - D: Decoder, - V: Decodable -> Decodable for TrieMap { - fn decode(d: &mut D) -> TrieMap { - d.read_map(|d, len| { - let mut map = TrieMap::new(); - for i in range(0u, len) { - let key = d.read_map_elt_key(i, |d| Decodable::decode(d)); - let val = d.read_map_elt_val(i, |d| Decodable::decode(d)); - map.insert(key, val); - } - map - }) - } -} - -impl Encodable for TrieSet { - fn encode(&self, s: &mut S) { - s.emit_seq(self.len(), |s| { - for (i, e) in self.iter().enumerate() { - s.emit_seq_elt(i, |s| e.encode(s)); - } - }) - } -} - -impl Decodable for TrieSet { - fn decode(d: &mut D) -> TrieSet { - d.read_seq(|d, len| { - let mut set = TrieSet::new(); - for i in range(0u, len) { - set.insert(d.read_seq_elt(i, |d| Decodable::decode(d))); - } - set - }) - } -} - // ___________________________________________________________________________ // Helper routines // 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 or the MIT license -// , 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 { - 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 { - priv k0: u64, - priv k1: u64, - priv resize_at: uint, - priv size: uint, - priv buckets: Vec>> -} - -// We could rewrite FoundEntry to have type Option<&Bucket> -// which would be nifty -enum SearchResult { - FoundEntry(uint), FoundHole(uint), TableFull -} - -#[inline] -fn resize_at(capacity: uint) -> uint { - (capacity * 3) / 4 -} - -impl HashMap { - #[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>(&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>(&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>) { - 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 { - 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 { - // 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 Container for HashMap { - /// Return the number of elements in the map - fn len(&self) -> uint { self.size } -} - -impl Mutable for HashMap { - /// 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 Map for HashMap { - /// 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 MutableMap for HashMap { - /// 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 { - // 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 { - let hash = k.hash_keyed(self.k0, self.k1) as uint; - self.pop_internal(hash, k) - } -} - -impl HashMap { - /// Create an empty HashMap - pub fn new() -> HashMap { - 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 { - 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 { - 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>(&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>(&'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 { - MoveEntries {iter: self.buckets.move_iter()} - } -} - -impl HashMap { - /// Like `find`, but returns a copy of the value. - pub fn find_copy(&self, k: &K) -> Option { - 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 Eq for HashMap { - fn eq(&self, other: &HashMap) -> 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) -> bool { !self.eq(other) } -} - -impl Clone for HashMap { - fn clone(&self) -> HashMap { - 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 fmt::Show for HashMap { - 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>>, -} - -/// HashMap mutable values iterator -pub struct MutEntries<'a, K, V> { - priv iter: MutItems<'a, Option>>, -} - -/// HashMap move iterator -pub struct MoveEntries { - priv iter: vec_ng::MoveItems>>, -} - -/// 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>>, -} - -/// HashSet move iterator -pub struct SetMoveItems { - priv iter: vec_ng::MoveItems>>, -} - -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 Iterator<(K, V)> for MoveEntries { - #[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 Iterator for SetMoveItems { - #[inline] - fn next(&mut self) -> Option { - for elt in self.iter { - match elt { - Some(bucket) => return Some(bucket.key), - None => {}, - } - } - None - } -} - -impl FromIterator<(K, V)> for HashMap { - fn from_iterator>(iter: &mut T) -> HashMap { - let (lower, _) = iter.size_hint(); - let mut map = HashMap::with_capacity(lower); - map.extend(iter); - map - } -} - -impl Extendable<(K, V)> for HashMap { - fn extend>(&mut self, iter: &mut T) { - for (k, v) in *iter { - self.insert(k, v); - } - } -} - -impl Default for HashMap { - fn default() -> HashMap { 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 { - priv map: HashMap -} - -impl Eq for HashSet { - fn eq(&self, other: &HashSet) -> bool { self.map == other.map } - fn ne(&self, other: &HashSet) -> bool { self.map != other.map } -} - -impl Container for HashSet { - /// Return the number of elements in the set - fn len(&self) -> uint { self.map.len() } -} - -impl Mutable for HashSet { - /// Clear the set, removing all values. - fn clear(&mut self) { self.map.clear() } -} - -impl Set for HashSet { - /// 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) -> bool { - self.iter().all(|v| !other.contains(v)) - } - - /// Return true if the set is a subset of another - fn is_subset(&self, other: &HashSet) -> bool { - self.iter().all(|v| other.contains(v)) - } - - /// Return true if the set is a superset of another - fn is_superset(&self, other: &HashSet) -> bool { - other.is_subset(self) - } -} - -impl MutableSet for HashSet { - /// 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 HashSet { - /// Create an empty HashSet - pub fn new() -> HashSet { - 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 { - 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 { - 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>(&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 { - SetMoveItems {iter: self.map.buckets.move_iter()} - } - - /// Visit the values representing the difference - pub fn difference<'a>(&'a self, other: &'a HashSet) -> 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) - -> Chain, 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) - -> 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) - -> Chain, SetAlgebraItems<'a, T>> { - self.iter().chain(other.difference(self)) - } - -} - -impl Clone for HashSet { - fn clone(&self) -> HashSet { - HashSet { - map: self.map.clone() - } - } -} - -impl fmt::Show for HashSet { - 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 FromIterator for HashSet { - fn from_iterator>(iter: &mut T) -> HashSet { - let (lower, _) = iter.size_hint(); - let mut set = HashSet::with_capacity(lower); - set.extend(iter); - set - } -} - -impl Extendable for HashSet { - fn extend>(&mut self, iter: &mut T) { - for k in *iter { - self.insert(k); - } - } -} - -impl Default for HashSet { - fn default() -> HashSet { 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, &'a T), &'a T, - Zip>,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 = 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 = 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 = 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::>(); - 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::>(); - 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 = 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 = HashMap::new(); - let empty: HashMap = 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 = 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 = HashSet::new(); - let empty: HashSet = 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, + priv handles: ~[(Signum, ~RtioSignal)], /// chan is where all the handles send signums, which are received by /// the clients from port. priv chan: Chan, @@ -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 ToStr for HashMap { - #[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 ToStr for HashSet { - #[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 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 = HashMap::new(); - let empty: HashMap = 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 = HashSet::new(); - let empty_set: HashSet = 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 or the MIT license -// , 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 { - Internal(~TrieNode), - External(uint, T), - Nothing -} - -#[allow(missing_doc)] -pub struct TrieMap { - priv root: TrieNode, - priv length: uint -} - -impl Container for TrieMap { - /// Return the number of elements in the map - #[inline] - fn len(&self) -> uint { self.length } -} - -impl Mutable for TrieMap { - /// Clear the map, removing all values. - #[inline] - fn clear(&mut self) { - self.root = TrieNode::new(); - self.length = 0; - } -} - -impl Map for TrieMap { - /// 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 = &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 MutableMap for TrieMap { - /// 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 { - 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 { - 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 TrieMap { - /// Create an empty TrieMap - #[inline] - pub fn new() -> TrieMap { - 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 `& ` 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); - - 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); - (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 TrieMap { - // 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 FromIterator<(uint, T)> for TrieMap { - fn from_iterator>(iter: &mut Iter) -> TrieMap { - let mut map = TrieMap::new(); - map.extend(iter); - map - } -} - -impl Extendable<(uint, T)> for TrieMap { - fn extend>(&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 for TrieSet { - fn from_iterator>(iter: &mut Iter) -> TrieSet { - let mut set = TrieSet::new(); - set.extend(iter); - set - } -} - -impl Extendable for TrieSet { - fn extend>(&mut self, iter: &mut Iter) { - for elem in *iter { - self.insert(elem); - } - } -} - -struct TrieNode { - count: uint, - children: [Child, ..SIZE] -} - -impl TrieNode { - #[inline] - fn new() -> TrieNode { - // 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 TrieNode { - 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, 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(count: &mut uint, child: &mut Child, key: uint, value: T, - idx: uint) -> Option { - // 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(count: &mut uint, child: &mut Child, key: uint, - idx: uint) -> Option { - 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>, .. 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>, .. 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) { - (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 for SetItems<'a> { - fn next(&mut self) -> Option { - self.iter.next().map(|(key, _)| key) - } - - fn size_hint(&self) -> (uint, Option) { - self.iter.size_hint() - } -} - -#[cfg(test)] -pub fn check_integrity(trie: &TrieNode) { - 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 = 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 = 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 = 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 = 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 = 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 = 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::::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::::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::::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::::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::() & 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::() & 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); } } diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs index 9ecc8e50935..db1243b18bc 100644 --- a/src/libsyntax/ast.rs +++ b/src/libsyntax/ast.rs @@ -18,7 +18,7 @@ use parse::token::{InternedString, special_idents, str_to_ident}; use parse::token; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; use std::option::Option; use std::rc::Rc; use std::to_str::ToStr; @@ -39,7 +39,7 @@ pub fn P(value: T) -> P { // table) and a SyntaxContext to track renaming and // macro expansion per Flatt et al., "Macros // That Work Together" -#[deriving(Clone, IterBytes, ToStr, TotalEq, TotalOrd)] +#[deriving(Clone, IterBytes, ToStr, TotalEq, TotalOrd, Show)] pub struct Ident { name: Name, ctxt: SyntaxContext } impl Ident { @@ -177,7 +177,7 @@ pub type CrateNum = u32; pub type NodeId = u32; -#[deriving(Clone, TotalEq, TotalOrd, Eq, Encodable, Decodable, IterBytes, ToStr)] +#[deriving(Clone, TotalEq, TotalOrd, Eq, Encodable, Decodable, IterBytes, ToStr, Show)] pub struct DefId { krate: CrateNum, node: NodeId, diff --git a/src/libsyntax/ast_util.rs b/src/libsyntax/ast_util.rs index 790f3927352..8ff66bc6629 100644 --- a/src/libsyntax/ast_util.rs +++ b/src/libsyntax/ast_util.rs @@ -20,7 +20,7 @@ use visit; use std::cell::{Cell, RefCell}; use std::cmp; -use std::hashmap::HashMap; +use collections::HashMap; use std::u32; use std::local_data; @@ -964,7 +964,7 @@ mod test { use ast::*; use super::*; use opt_vec; - use std::hashmap::HashMap; + use collections::HashMap; fn ident_to_segment(id : &Ident) -> PathSegment { PathSegment {identifier:id.clone(), diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs index 78e9d3bd46f..93edb552bbe 100644 --- a/src/libsyntax/attr.rs +++ b/src/libsyntax/attr.rs @@ -20,7 +20,7 @@ use parse::token::InternedString; use parse::token; use crateid::CrateId; -use std::hashmap::HashSet; +use collections::HashSet; pub trait AttrMetaMethods { // This could be changed to `fn check_name(&self, name: InternedString) -> diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs index e6fffe8b53f..0636d19163e 100644 --- a/src/libsyntax/ext/base.rs +++ b/src/libsyntax/ext/base.rs @@ -19,7 +19,7 @@ use parse::token; use parse::token::{InternedString, intern, str_to_ident}; use util::small_vector::SmallVector; -use std::hashmap::HashMap; +use collections::HashMap; // new-style macro! tt code: // diff --git a/src/libsyntax/ext/deriving/show.rs b/src/libsyntax/ext/deriving/show.rs index 56493000a92..5286720b9fc 100644 --- a/src/libsyntax/ext/deriving/show.rs +++ b/src/libsyntax/ext/deriving/show.rs @@ -18,7 +18,7 @@ use ext::deriving::generic::*; use parse::token; -use std::hashmap::HashMap; +use collections::HashMap; pub fn expand_deriving_show(cx: &mut ExtCtxt, span: Span, diff --git a/src/libsyntax/ext/format.rs b/src/libsyntax/ext/format.rs index 16a12661e9d..1b73d42c79a 100644 --- a/src/libsyntax/ext/format.rs +++ b/src/libsyntax/ext/format.rs @@ -18,8 +18,9 @@ use opt_vec; use parse::token::InternedString; use parse::token; use rsparse = parse; + use std::fmt::parse; -use std::hashmap::{HashMap, HashSet}; +use collections::{HashMap, HashSet}; use std::vec; #[deriving(Eq)] diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs index c2d005da74e..456533de5e9 100644 --- a/src/libsyntax/ext/tt/macro_parser.rs +++ b/src/libsyntax/ext/tt/macro_parser.rs @@ -21,7 +21,7 @@ use parse::parser::{LifetimeAndTypesWithoutColons, Parser}; use parse::token::{Token, EOF, Nonterminal}; use parse::token; -use std::hashmap::HashMap; +use collections::HashMap; use std::vec; /* This is an Earley-like parser, without support for in-grammar nonterminals, diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs index fb2aae9b8c1..a8c9fe37226 100644 --- a/src/libsyntax/ext/tt/transcribe.rs +++ b/src/libsyntax/ext/tt/transcribe.rs @@ -18,7 +18,7 @@ use parse::token; use parse::lexer::TokenAndSpan; use std::cell::{Cell, RefCell}; -use std::hashmap::HashMap; +use collections::HashMap; ///an unzipping of `TokenTree`s struct TtFrame { diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs index 30e77c8c1cb..fed2034cd26 100644 --- a/src/libsyntax/parse/parser.rs +++ b/src/libsyntax/parse/parser.rs @@ -79,7 +79,7 @@ use opt_vec; use opt_vec::OptVec; use std::cell::Cell; -use std::hashmap::HashSet; +use collections::HashSet; use std::kinds::marker; use std::mem::replace; use std::vec; diff --git a/src/libsyntax/util/interner.rs b/src/libsyntax/util/interner.rs index 1c801f7d970..44b366c9890 100644 --- a/src/libsyntax/util/interner.rs +++ b/src/libsyntax/util/interner.rs @@ -14,11 +14,11 @@ use ast::Name; +use collections::HashMap; use std::cast; use std::cell::RefCell; use std::cmp::Equiv; use std::hash_old::Hash; -use std::hashmap::HashMap; use std::rc::Rc; pub struct Interner { diff --git a/src/libterm/lib.rs b/src/libterm/lib.rs index 1efbd461da8..db9f5d3da5c 100644 --- a/src/libterm/lib.rs +++ b/src/libterm/lib.rs @@ -23,6 +23,8 @@ #[deny(non_camel_case_types)]; #[allow(missing_doc)]; +extern crate collections; + use std::os; use std::io; use terminfo::TermInfo; diff --git a/src/libterm/terminfo/mod.rs b/src/libterm/terminfo/mod.rs index 439297db84e..de8a1dcc363 100644 --- a/src/libterm/terminfo/mod.rs +++ b/src/libterm/terminfo/mod.rs @@ -10,7 +10,7 @@ #[allow(missing_doc)]; -use std::hashmap::HashMap; +use collections::HashMap; /// A parsed terminfo entry. pub struct TermInfo { diff --git a/src/libterm/terminfo/parser/compiled.rs b/src/libterm/terminfo/parser/compiled.rs index b2d06d3b7d8..e9d71d1c2f7 100644 --- a/src/libterm/terminfo/parser/compiled.rs +++ b/src/libterm/terminfo/parser/compiled.rs @@ -14,8 +14,8 @@ use std::{vec, str}; -use std::hashmap::HashMap; use std::io; +use collections::HashMap; use super::super::TermInfo; // These are the orders ncurses uses in its compiled format (as of 5.9). Not sure if portable. diff --git a/src/libuuid/lib.rs b/src/libuuid/lib.rs index 69780451935..e4053e3bc38 100644 --- a/src/libuuid/lib.rs +++ b/src/libuuid/lib.rs @@ -519,6 +519,8 @@ impl rand::Rand for Uuid { #[cfg(test)] mod test { + extern crate collections; + use super::{Uuid, VariantMicrosoft, VariantNCS, VariantRFC4122, Version1Mac, Version2Dce, Version3Md5, Version4Random, Version5Sha1}; @@ -800,7 +802,7 @@ mod test { #[test] fn test_iterbytes_impl_for_uuid() { - use std::hashmap::HashSet; + use self::collections::HashSet; let mut set = HashSet::new(); let id1 = Uuid::new_v4(); let id2 = Uuid::new_v4(); diff --git a/src/test/auxiliary/issue-2631-a.rs b/src/test/auxiliary/issue-2631-a.rs index 5c5a80e5d00..1a287b5e625 100644 --- a/src/test/auxiliary/issue-2631-a.rs +++ b/src/test/auxiliary/issue-2631-a.rs @@ -13,9 +13,10 @@ #[crate_type = "lib"]; extern crate extra; +extern crate collections; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; pub type header_map = HashMap<~str, @RefCell<~[@~str]>>; diff --git a/src/test/auxiliary/issue-5521.rs b/src/test/auxiliary/issue-5521.rs index 951e94e47c5..6f964d0824c 100644 --- a/src/test/auxiliary/issue-5521.rs +++ b/src/test/auxiliary/issue-5521.rs @@ -10,6 +10,8 @@ #[feature(managed_boxes)]; -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; pub type map = @HashMap; diff --git a/src/test/bench/core-map.rs b/src/test/bench/core-map.rs index ac77e62f2c0..1830a888345 100644 --- a/src/test/bench/core-map.rs +++ b/src/test/bench/core-map.rs @@ -11,11 +11,9 @@ extern crate collections; extern crate time; -use collections::TreeMap; -use std::hashmap::{HashMap, HashSet}; +use collections::{TrieMap, TreeMap, HashMap, HashSet}; use std::os; use std::rand::{Rng, IsaacRng, SeedableRng}; -use std::trie::TrieMap; use std::uint; use std::vec; diff --git a/src/test/bench/core-set.rs b/src/test/bench/core-set.rs index 25ced5f35da..d1c311d2a7d 100644 --- a/src/test/bench/core-set.rs +++ b/src/test/bench/core-set.rs @@ -15,7 +15,7 @@ extern crate time; use collections::bitv::BitvSet; use collections::TreeSet; -use std::hashmap::HashSet; +use collections::HashSet; use std::os; use std::rand; use std::uint; @@ -177,7 +177,7 @@ fn main() { let s: HashSet<~str> = HashSet::new(); s }); - write_results("std::hashmap::HashSet", &results); + write_results("collections::HashSet", &results); } { diff --git a/src/test/bench/shootout-k-nucleotide-pipes.rs b/src/test/bench/shootout-k-nucleotide-pipes.rs index 737e5c98214..7188e119a8d 100644 --- a/src/test/bench/shootout-k-nucleotide-pipes.rs +++ b/src/test/bench/shootout-k-nucleotide-pipes.rs @@ -14,10 +14,11 @@ // multi tasking k-nucleotide extern crate extra; +extern crate collections; use std::cmp::Ord; use std::comm; -use std::hashmap::HashMap; +use collections::HashMap; use std::mem::replace; use std::option; use std::os; diff --git a/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs b/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs index c004b3d0e54..20411723715 100644 --- a/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs +++ b/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs @@ -10,7 +10,8 @@ //buggy.rs -use std::hashmap::HashMap; +extern crate collections; +use collections::HashMap; fn main() { let mut buggy_map: HashMap = HashMap::new(); diff --git a/src/test/compile-fail/borrowck-insert-during-each.rs b/src/test/compile-fail/borrowck-insert-during-each.rs index 38ff840ada4..b4781171487 100644 --- a/src/test/compile-fail/borrowck-insert-during-each.rs +++ b/src/test/compile-fail/borrowck-insert-during-each.rs @@ -8,7 +8,8 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::hashmap::HashSet; +extern crate collections; +use collections::HashSet; struct Foo { n: HashSet, diff --git a/src/test/compile-fail/map-types.rs b/src/test/compile-fail/map-types.rs index a3b5a1264f7..bd10c6ad8c3 100644 --- a/src/test/compile-fail/map-types.rs +++ b/src/test/compile-fail/map-types.rs @@ -8,8 +8,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::container::Map; -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; // Test that trait types printed in error msgs include the type arguments. diff --git a/src/test/run-fail/unwind-misc-1.rs b/src/test/run-fail/unwind-misc-1.rs index 09e7d0bc28c..f9abb1566bb 100644 --- a/src/test/run-fail/unwind-misc-1.rs +++ b/src/test/run-fail/unwind-misc-1.rs @@ -13,9 +13,11 @@ #[feature(managed_boxes)]; +extern crate collections; + fn main() { let _count = @0u; - let mut map = std::hashmap::HashMap::new(); + let mut map = collections::HashMap::new(); let mut arr = ~[]; for _i in range(0u, 10u) { arr.push(@~"key stuff"); diff --git a/src/test/run-pass/foreach-external-iterators-hashmap-break-restart.rs b/src/test/run-pass/foreach-external-iterators-hashmap-break-restart.rs index 34ce8c47113..e2a06162bed 100644 --- a/src/test/run-pass/foreach-external-iterators-hashmap-break-restart.rs +++ b/src/test/run-pass/foreach-external-iterators-hashmap-break-restart.rs @@ -8,7 +8,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; // This is a fancy one: it uses an external iterator established // outside the loop, breaks, then _picks back up_ and continues diff --git a/src/test/run-pass/foreach-external-iterators-hashmap.rs b/src/test/run-pass/foreach-external-iterators-hashmap.rs index 365cde34dce..e6280b47b6e 100644 --- a/src/test/run-pass/foreach-external-iterators-hashmap.rs +++ b/src/test/run-pass/foreach-external-iterators-hashmap.rs @@ -8,7 +8,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; pub fn main() { let mut h = HashMap::new(); diff --git a/src/test/run-pass/hashmap-memory.rs b/src/test/run-pass/hashmap-memory.rs index 9c05dae46bd..3f3687fd333 100644 --- a/src/test/run-pass/hashmap-memory.rs +++ b/src/test/run-pass/hashmap-memory.rs @@ -12,6 +12,8 @@ #[feature(managed_boxes)]; +extern crate collections; + /** A somewhat reduced test case to expose some Valgrind issues. @@ -21,7 +23,7 @@ pub fn map(filename: ~str, emit: map_reduce::putter) { emit(filename, ~"1"); } mod map_reduce { - use std::hashmap::HashMap; + use collections::HashMap; use std::str; use std::task; diff --git a/src/test/run-pass/issue-1696.rs b/src/test/run-pass/issue-1696.rs index 207e402732a..2dbed23677f 100644 --- a/src/test/run-pass/issue-1696.rs +++ b/src/test/run-pass/issue-1696.rs @@ -10,7 +10,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; pub fn main() { let mut m = HashMap::new(); diff --git a/src/test/run-pass/issue-2631-b.rs b/src/test/run-pass/issue-2631-b.rs index 68f2fd95cde..592232ca21d 100644 --- a/src/test/run-pass/issue-2631-b.rs +++ b/src/test/run-pass/issue-2631-b.rs @@ -13,11 +13,12 @@ // ignore-fast // aux-build:issue-2631-a.rs +extern crate collections; extern crate req; use req::request; use std::cell::RefCell; -use std::hashmap::HashMap; +use collections::HashMap; pub fn main() { let v = ~[@~"hi"]; diff --git a/src/test/run-pass/issue-2804-2.rs b/src/test/run-pass/issue-2804-2.rs index 9357d19d380..5e6ea5f6d44 100644 --- a/src/test/run-pass/issue-2804-2.rs +++ b/src/test/run-pass/issue-2804-2.rs @@ -13,7 +13,9 @@ // Minimized version of issue-2804.rs. Both check that callee IDs don't // clobber the previous node ID in a macro expr -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; fn add_interfaces(managed_ip: ~str, device: HashMap<~str, int>) { error!("{}, {:?}", managed_ip, device.get(&~"interfaces")); diff --git a/src/test/run-pass/issue-2804.rs b/src/test/run-pass/issue-2804.rs index a9ac81be0ba..a1bed266817 100644 --- a/src/test/run-pass/issue-2804.rs +++ b/src/test/run-pass/issue-2804.rs @@ -10,10 +10,11 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +extern crate collections; extern crate extra; use extra::json; -use std::hashmap::HashMap; +use collections::HashMap; use std::option; enum object { diff --git a/src/test/run-pass/issue-3026.rs b/src/test/run-pass/issue-3026.rs index c32b24c3847..ee7f3aab47a 100644 --- a/src/test/run-pass/issue-3026.rs +++ b/src/test/run-pass/issue-3026.rs @@ -10,7 +10,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; pub fn main() { let mut buggy_map: HashMap = HashMap::new(); diff --git a/src/test/run-pass/issue-3559.rs b/src/test/run-pass/issue-3559.rs index 5cc098e591c..829df5060c3 100644 --- a/src/test/run-pass/issue-3559.rs +++ b/src/test/run-pass/issue-3559.rs @@ -8,7 +8,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; fn check_strs(actual: &str, expected: &str) -> bool { if actual != expected { diff --git a/src/test/run-pass/issue-6128.rs b/src/test/run-pass/issue-6128.rs index a01a04ebf82..3694421c691 100644 --- a/src/test/run-pass/issue-6128.rs +++ b/src/test/run-pass/issue-6128.rs @@ -8,7 +8,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; trait Graph { fn f(&self, Edge); diff --git a/src/test/run-pass/issue-7660.rs b/src/test/run-pass/issue-7660.rs index 7f1382cf890..eadcdb67f14 100644 --- a/src/test/run-pass/issue-7660.rs +++ b/src/test/run-pass/issue-7660.rs @@ -11,7 +11,9 @@ // Regresion test for issue 7660 // rvalue lifetime too short when equivalent `match` works -use std::hashmap::HashMap; +extern crate collections; + +use collections::HashMap; struct A(int, int); diff --git a/src/test/run-pass/regions-mock-tcx.rs b/src/test/run-pass/regions-mock-tcx.rs index 738a4899f27..6dafd81a018 100644 --- a/src/test/run-pass/regions-mock-tcx.rs +++ b/src/test/run-pass/regions-mock-tcx.rs @@ -17,9 +17,10 @@ // - Arenas extern crate arena; +extern crate collections; use arena::Arena; -use std::hashmap::HashMap; +use collections::HashMap; use std::cast; use std::libc; use std::mem; diff --git a/src/test/run-pass/send_str_hashmap.rs b/src/test/run-pass/send_str_hashmap.rs index 8599f9d3836..4fd7980e795 100644 --- a/src/test/run-pass/send_str_hashmap.rs +++ b/src/test/run-pass/send_str_hashmap.rs @@ -8,6 +8,8 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +extern crate collections; + use std::clone::{Clone, DeepClone}; use std::cmp::{TotalEq, Ord, TotalOrd, Equiv}; use std::cmp::Equal; @@ -15,7 +17,7 @@ use std::container::{Container, Map, MutableMap}; use std::default::Default; use std::str::{Str, SendStr, Owned, Slice}; use std::to_str::ToStr; -use std::hashmap::HashMap; +use collections::HashMap; use std::option::Some; pub fn main() { -- cgit 1.4.1-3-g733a5