auto merge of #12428 : alexcrichton/rust/move-hashmap, r=brson

These two containers are indeed collections, so there 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.

8 files changed, 47 insertions, 2594 deletions

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