Merge pull request #4594 from thestinger/map

more work on the map trait and TreeMap/LinearMap

16 files changed, 327 insertions, 295 deletions

diff --git a/src/libcargo/cargo.rc b/src/libcargo/cargo.rc
index eb89827e17a..193adc10997 100644
--- a/src/libcargo/cargo.rc
+++ b/src/libcargo/cargo.rc
@@ -52,7 +52,7 @@ use core::*;
 use core::dvec::DVec;
 use core::io::WriterUtil;
 use core::result::{Ok, Err};
-use core::send_map::linear::LinearMap;
+use core::hashmap::linear::LinearMap;
 use std::getopts::{optflag, optopt, opt_present};
 use std::map::HashMap;
 use std::{map, json, tempfile, term, sort, getopts};
@@ -465,19 +465,19 @@ fn parse_source(name: ~str, j: &json::Json) -> @Source {
 
     match *j {
         json::Object(j) => {
-            let mut url = match j.find(&~"url") {
+            let mut url = match j.find_copy(&~"url") {
                 Some(json::String(u)) => u,
                 _ => fail ~"needed 'url' field in source"
             };
-            let method = match j.find(&~"method") {
+            let method = match j.find_copy(&~"method") {
                 Some(json::String(u)) => u,
                 _ => assume_source_method(url)
             };
-            let key = match j.find(&~"key") {
+            let key = match j.find_copy(&~"key") {
                 Some(json::String(u)) => Some(u),
                 _ => None
             };
-            let keyfp = match j.find(&~"keyfp") {
+            let keyfp = match j.find_copy(&~"keyfp") {
                 Some(json::String(u)) => Some(u),
                 _ => None
             };
@@ -512,7 +512,7 @@ fn try_parse_sources(filename: &Path, sources: map::HashMap<~str, @Source>) {
 }
 
 fn load_one_source_package(src: @Source, p: &json::Object) {
-    let name = match p.find(&~"name") {
+    let name = match p.find_copy(&~"name") {
         Some(json::String(n)) => {
             if !valid_pkg_name(n) {
                 warn(~"malformed source json: "
@@ -529,7 +529,7 @@ fn load_one_source_package(src: @Source, p: &json::Object) {
         }
     };
 
-    let uuid = match p.find(&~"uuid") {
+    let uuid = match p.find_copy(&~"uuid") {
         Some(json::String(n)) => {
             if !is_uuid(n) {
                 warn(~"malformed source json: "
@@ -545,7 +545,7 @@ fn load_one_source_package(src: @Source, p: &json::Object) {
         }
     };
 
-    let url = match p.find(&~"url") {
+    let url = match p.find_copy(&~"url") {
         Some(json::String(n)) => n,
         _ => {
             warn(~"malformed source json: " + src.name + ~" (missing url)");
@@ -553,7 +553,7 @@ fn load_one_source_package(src: @Source, p: &json::Object) {
         }
     };
 
-    let method = match p.find(&~"method") {
+    let method = match p.find_copy(&~"method") {
         Some(json::String(n)) => n,
         _ => {
             warn(~"malformed source json: "
@@ -562,13 +562,13 @@ fn load_one_source_package(src: @Source, p: &json::Object) {
         }
     };
 
-    let reference = match p.find(&~"ref") {
+    let reference = match p.find_copy(&~"ref") {
         Some(json::String(n)) => Some(n),
         _ => None
     };
 
     let mut tags = ~[];
-    match p.find(&~"tags") {
+    match p.find_copy(&~"tags") {
         Some(json::List(js)) => {
           for js.each |j| {
                 match *j {
@@ -580,7 +580,7 @@ fn load_one_source_package(src: @Source, p: &json::Object) {
         _ => ()
     }
 
-    let description = match p.find(&~"description") {
+    let description = match p.find_copy(&~"description") {
         Some(json::String(n)) => n,
         _ => {
             warn(~"malformed source json: " + src.name
@@ -1619,7 +1619,7 @@ fn dump_cache(c: &Cargo) {
     need_dir(&c.root);
 
     let out = c.root.push("cache.json");
-    let _root = json::Object(~LinearMap());
+    let _root = json::Object(~LinearMap::new());
 
     if os::path_exists(&out) {
         copy_warn(&out, &c.root.push("cache.json.old"));
@@ -1640,10 +1640,10 @@ fn dump_sources(c: &Cargo) {
 
     match io::buffered_file_writer(&out) {
         result::Ok(writer) => {
-            let mut hash = ~LinearMap();
+            let mut hash = ~LinearMap::new();
 
             for c.sources.each |k, v| {
-                let mut chash = ~LinearMap();
+                let mut chash = ~LinearMap::new();
 
                 chash.insert(~"url", json::String(v.url));
                 chash.insert(~"method", json::String(v.method));
diff --git a/src/libcore/container.rs b/src/libcore/container.rs
index 062416838cc..272a2efc035 100644
--- a/src/libcore/container.rs
+++ b/src/libcore/container.rs
@@ -13,6 +13,8 @@
 #[forbid(deprecated_mode)];
 #[forbid(deprecated_pattern)];
 
+use option::Option;
+
 pub trait Container {
     /// Return the number of elements in the container
     pure fn len(&self) -> uint;
@@ -39,6 +41,9 @@ pub trait Map<K, V>: Mutable {
     /// Visit all values
     pure fn each_value(&self, f: fn(&V) -> bool);
 
+    /// Return the value corresponding to the key in the map
+    pure fn find(&self, key: &K) -> Option<&self/V>;
+
     /// Insert a key-value pair into the map. An existing value for a
     /// key is replaced by the new value. Return true if the key did
     /// not already exist in the map.
diff --git a/src/libcore/core.rc b/src/libcore/core.rc
index 24623f20c80..20057fa1038 100644
--- a/src/libcore/core.rc
+++ b/src/libcore/core.rc
@@ -138,7 +138,7 @@ pub mod dvec_iter;
 pub mod dlist;
 #[path="iter-trait.rs"] #[merge = "iter-trait/dlist.rs"]
 pub mod dlist_iter;
-pub mod send_map;
+pub mod hashmap;
 
 
 /* Tasks and communication */
diff --git a/src/libcore/gc.rs b/src/libcore/gc.rs
index b98c79f8d0e..d27681d4630 100644
--- a/src/libcore/gc.rs
+++ b/src/libcore/gc.rs
@@ -44,7 +44,7 @@ use io;
 use libc::{size_t, uintptr_t};
 use option::{None, Option, Some};
 use ptr;
-use send_map::linear::LinearSet;
+use hashmap::linear::LinearSet;
 use stackwalk;
 use sys;
 
diff --git a/src/libcore/send_map.rs b/src/libcore/hashmap.rs
index 788c4fdbd5e..40b80bddf84 100644
--- a/src/libcore/send_map.rs
+++ b/src/libcore/hashmap.rs
@@ -8,11 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-/*!
-
-Sendable hash maps.  Very much a work in progress.
-
-*/
+//! Sendable hash maps.
 
 // NB: transitionary, de-mode-ing.
 #[forbid(deprecated_mode)];
@@ -102,9 +98,7 @@ pub mod linear {
                             idx: uint,
                             len_buckets: uint) -> uint {
             let n = (idx + 1) % len_buckets;
-            unsafe{ // argh. log not considered pure.
-                debug!("next_bucket(%?, %?) = %?", idx, len_buckets, n);
-            }
+            debug!("next_bucket(%?, %?) = %?", idx, len_buckets, n);
             return n;
         }
 
@@ -259,11 +253,15 @@ pub mod linear {
     }
 
     impl <K: Hash IterBytes Eq, V> LinearMap<K, V>: Container {
+        /// Return the number of elements in the map
         pure fn len(&self) -> uint { self.size }
+
+        /// Return true if the map contains no elements
         pure fn is_empty(&self) -> bool { self.len() == 0 }
     }
 
     impl <K: Hash IterBytes Eq, V> LinearMap<K, V>: Mutable {
+        /// Clear the map, removing all key-value pairs.
         fn clear(&mut self) {
             for uint::range(0, self.buckets.len()) |idx| {
                 self.buckets[idx] = None;
@@ -273,6 +271,7 @@ pub mod linear {
     }
 
     impl <K: Hash IterBytes Eq, V> LinearMap<K, V>: Map<K, V> {
+        /// Return true if the map contains a value for the specified key
         pure fn contains_key(&self, k: &K) -> bool {
             match self.bucket_for_key(self.buckets, k) {
                 FoundEntry(_) => {true}
@@ -280,6 +279,7 @@ pub mod linear {
             }
         }
 
+        /// Visit all key-value pairs
         pure fn each(&self, blk: fn(k: &K, v: &V) -> bool) {
             for vec::each(self.buckets) |slot| {
                 let mut broke = false;
@@ -292,14 +292,40 @@ pub mod linear {
             }
         }
 
+        /// Visit all keys
         pure fn each_key(&self, blk: fn(k: &K) -> bool) {
             self.each(|k, _v| blk(k))
         }
 
+        /// Visit all values
         pure fn each_value(&self, blk: fn(v: &V) -> bool) {
             self.each(|_k, v| blk(v))
         }
 
+        /// Return the value corresponding to the key in the map
+        pure fn find(&self, k: &K) -> Option<&self/V> {
+            match self.bucket_for_key(self.buckets, k) {
+                FoundEntry(idx) => {
+                    match self.buckets[idx] {
+                        Some(ref bkt) => {
+                            // FIXME(#3148)---should be inferred
+                            let bkt: &self/Bucket<K,V> = bkt;
+                            Some(&bkt.value)
+                        }
+                        None => {
+                            fail ~"LinearMap::find: internal logic error"
+                        }
+                    }
+                }
+                TableFull | FoundHole(_) => {
+                    None
+                }
+            }
+        }
+
+        /// Insert a key-value pair into the map. An existing value for a
+        /// key is replaced by the new value. Return true if the key did
+        /// not already exist in the map.
         fn insert(&mut self, k: K, v: V) -> bool {
             if self.size >= self.resize_at {
                 // n.b.: We could also do this after searching, so
@@ -315,6 +341,8 @@ pub mod linear {
             self.insert_internal(hash, move k, move v)
         }
 
+        /// Remove a key-value pair from the map. Return true if the key
+        /// was present in the map, otherwise false.
         fn remove(&mut self, k: &K) -> bool {
             match self.pop(k) {
                 Some(_) => true,
@@ -324,6 +352,10 @@ pub mod linear {
     }
 
     impl<K:Hash IterBytes Eq,V> LinearMap<K,V> {
+        static fn new() -> LinearMap<K, V> {
+            linear_map_with_capacity(INITIAL_CAPACITY)
+        }
+
         fn pop(&mut self, k: &K) -> Option<V> {
             let hash = k.hash_keyed(self.k0, self.k1) as uint;
             self.pop_internal(hash, k)
@@ -369,36 +401,16 @@ pub mod linear {
             }
         }
 
-        pure fn find_ref(&self, k: &K) -> Option<&self/V> {
-            match self.bucket_for_key(self.buckets, k) {
-                FoundEntry(idx) => {
-                    match self.buckets[idx] {
-                        Some(ref bkt) => {
-                            // FIXME(#3148)---should be inferred
-                            let bkt: &self/Bucket<K,V> = bkt;
-                            Some(&bkt.value)
-                        }
-                        None => {
-                            fail ~"LinearMap::find: internal logic error"
-                        }
-                    }
-                }
-                TableFull | FoundHole(_) => {
-                    None
-                }
-            }
-        }
-
-        pure fn get_ref(&self, k: &K) -> &self/V {
-            match self.find_ref(k) {
+        pure fn get(&self, k: &K) -> &self/V {
+            match self.find(k) {
                 Some(v) => v,
                 None => fail fmt!("No entry found for key: %?", k),
             }
         }
     }
 
-    impl<K:Hash IterBytes Eq, V: Copy> LinearMap<K,V> {
-        pure fn find(&const self, k: &K) -> Option<V> {
+    impl<K:Hash IterBytes Eq, V: Copy> LinearMap<K, V> {
+        pure fn find_copy(&const self, k: &K) -> Option<V> {
             match self.bucket_for_key(self.buckets, k) {
                 FoundEntry(idx) => {
                     // FIXME (#3148): Once we rewrite found_entry, this
@@ -413,14 +425,6 @@ pub mod linear {
                 }
             }
         }
-
-        pure fn get(&const self, k: &K) -> V {
-            let value = self.find(k);
-            if value.is_none() {
-                fail fmt!("No entry found for key: %?", k);
-            }
-            option::unwrap(move value)
-        }
     }
 
     impl<K:Hash IterBytes Eq, V: Eq> LinearMap<K, V>: Eq {
@@ -428,7 +432,7 @@ pub mod linear {
             if self.len() != other.len() { return false; }
 
             for self.each |key, value| {
-                match other.find_ref(key) {
+                match other.find(key) {
                     None => return false,
                     Some(v) => if value != v { return false },
                 }
@@ -462,11 +466,15 @@ pub mod linear {
     }
 
     impl <T: Hash IterBytes Eq> LinearSet<T>: Container {
+        /// Return the number of elements in the set
         pure fn len(&self) -> uint { self.map.len() }
+
+        /// Return true if the set contains no elements
         pure fn is_empty(&self) -> bool { self.map.is_empty() }
     }
 
     impl <T: Hash IterBytes Eq> LinearSet<T>: Mutable {
+        /// Clear the set, removing all values.
         fn clear(&mut self) { self.map.clear() }
     }
 
@@ -494,26 +502,26 @@ pub mod linear {
 #[test]
 pub mod test {
     use option::{None, Some};
-    use send_map::linear::LinearMap;
-    use send_map::linear;
+    use hashmap::linear::LinearMap;
+    use hashmap::linear;
     use uint;
 
     #[test]
     pub fn inserts() {
-        let mut m = ~LinearMap();
+        let mut m = LinearMap::new();
         assert m.insert(1, 2);
         assert m.insert(2, 4);
-        assert m.get(&1) == 2;
-        assert m.get(&2) == 4;
+        assert *m.get(&1) == 2;
+        assert *m.get(&2) == 4;
     }
 
     #[test]
     pub fn overwrite() {
-        let mut m = ~LinearMap();
+        let mut m = LinearMap::new();
         assert m.insert(1, 2);
-        assert m.get(&1) == 2;
+        assert *m.get(&1) == 2;
         assert !m.insert(1, 3);
-        assert m.get(&1) == 3;
+        assert *m.get(&1) == 3;
     }
 
     #[test]
@@ -522,9 +530,9 @@ pub mod test {
         assert m.insert(1, 2);
         assert m.insert(5, 3);
         assert m.insert(9, 4);
-        assert m.get(&9) == 4;
-        assert m.get(&5) == 3;
-        assert m.get(&1) == 2;
+        assert *m.get(&9) == 4;
+        assert *m.get(&5) == 3;
+        assert *m.get(&1) == 2;
     }
 
     #[test]
@@ -534,8 +542,8 @@ pub mod test {
         assert m.insert(5, 3);
         assert m.insert(9, 4);
         assert m.remove(&1);
-        assert m.get(&9) == 4;
-        assert m.get(&5) == 3;
+        assert *m.get(&9) == 4;
+        assert *m.get(&5) == 3;
     }
 
     #[test]
@@ -549,7 +557,7 @@ pub mod test {
 
     #[test]
     pub fn pops() {
-        let mut m = ~LinearMap();
+        let mut m = LinearMap::new();
         m.insert(1, 2);
         assert m.pop(&1) == Some(2);
         assert m.pop(&1) == None;
@@ -557,7 +565,7 @@ pub mod test {
 
     #[test]
     pub fn swaps() {
-        let mut m = ~LinearMap();
+        let mut m = LinearMap::new();
         assert m.swap(1, 2) == None;
         assert m.swap(1, 3) == Some(2);
         assert m.swap(1, 4) == Some(3);
@@ -565,17 +573,17 @@ pub mod test {
 
     #[test]
     pub fn consumes() {
-        let mut m = ~LinearMap();
+        let mut m = LinearMap::new();
         assert m.insert(1, 2);
         assert m.insert(2, 3);
-        let mut m2 = ~LinearMap();
+        let mut m2 = LinearMap::new();
         do m.consume |k, v| {
             m2.insert(k, v);
         }
         assert m.len() == 0;
         assert m2.len() == 2;
-        assert m2.find(&1) == Some(2);
-        assert m2.find(&2) == Some(3);
+        assert m2.find_copy(&1) == Some(2);
+        assert m2.find_copy(&2) == Some(3);
     }
 
     #[test]
@@ -593,11 +601,11 @@ pub mod test {
     }
 
     #[test]
-    pub fn find_ref() {
-        let mut m = ~LinearMap();
-        assert m.find_ref(&1).is_none();
+    pub fn find() {
+        let mut m = LinearMap::new();
+        assert m.find(&1).is_none();
         m.insert(1, 2);
-        match m.find_ref(&1) {
+        match m.find(&1) {
             None => fail,
             Some(v) => assert *v == 2
         }
@@ -605,12 +613,12 @@ pub mod test {
 
     #[test]
     pub fn test_eq() {
-        let mut m1 = ~LinearMap();
+        let mut m1 = LinearMap::new();
         m1.insert(1, 2);
         m1.insert(2, 3);
         m1.insert(3, 4);
 
-        let mut m2 = ~LinearMap();
+        let mut m2 = LinearMap::new();
         m2.insert(1, 2);
         m2.insert(2, 3);
 
@@ -623,7 +631,7 @@ pub mod test {
 
     #[test]
     pub fn test_expand() {
-        let mut m = ~LinearMap();
+        let mut m = LinearMap::new();
 
         assert m.len() == 0;
         assert m.is_empty();
diff --git a/src/libcore/task/spawn.rs b/src/libcore/task/spawn.rs
index 2411bd896e7..4e9a0e43b36 100644
--- a/src/libcore/task/spawn.rs
+++ b/src/libcore/task/spawn.rs
@@ -81,7 +81,7 @@ use pipes;
 use prelude::*;
 use private;
 use ptr;
-use send_map;
+use hashmap::linear::LinearSet;
 use task::local_data_priv::{local_get, local_set};
 use task::rt::rust_task;
 use task::rt::rust_closure;
@@ -96,10 +96,10 @@ macro_rules! move_it (
     { $x:expr } => ( unsafe { let y = move *ptr::addr_of(&($x)); move y } )
 )
 
-type TaskSet = send_map::linear::LinearSet<*rust_task>;
+type TaskSet = LinearSet<*rust_task>;
 
 fn new_taskset() -> TaskSet {
-    send_map::linear::LinearSet::new()
+    LinearSet::new()
 }
 fn taskset_insert(tasks: &mut TaskSet, task: *rust_task) {
     let didnt_overwrite = tasks.insert(task);
diff --git a/src/librustc/middle/borrowck/gather_loans.rs b/src/librustc/middle/borrowck/gather_loans.rs
index 3561ef4db7d..aa7f3b71a50 100644
--- a/src/librustc/middle/borrowck/gather_loans.rs
+++ b/src/librustc/middle/borrowck/gather_loans.rs
@@ -30,7 +30,7 @@ use util::common::indenter;
 use util::ppaux::{expr_repr, region_to_str};
 
 use core::dvec;
-use core::send_map::linear::LinearSet;
+use core::hashmap::linear::LinearSet;
 use core::vec;
 use std::map::HashMap;
 use syntax::ast::{m_const, m_imm, m_mutbl};
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index df82c32f355..b0c98cfa2b1 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -57,7 +57,7 @@ use util::ppaux::ty_to_str;
 
 use core::dvec::DVec;
 use core::result::Ok;
-use core::send_map;
+use core::hashmap::linear::LinearSet;
 use core::uint::range;
 use core::uint;
 use core::vec::{len, push};
@@ -693,7 +693,7 @@ impl CoherenceChecker {
 
         let tcx = self.crate_context.tcx;
 
-        let mut provided_names = send_map::linear::LinearSet::new();
+        let mut provided_names = LinearSet::new();
         // Implemented methods
         for uint::range(0, all_methods.len()) |i| {
             provided_names.insert(all_methods[i].ident);
diff --git a/src/libstd/json.rs b/src/libstd/json.rs
index be7a9dcc6dc..ed3dbb48b2a 100644
--- a/src/libstd/json.rs
+++ b/src/libstd/json.rs
@@ -24,7 +24,7 @@ use core::float;
 use core::io::{WriterUtil, ReaderUtil};
 use core::io;
 use core::prelude::*;
-use core::send_map::linear;
+use core::hashmap::linear::LinearMap;
 use core::str;
 use core::to_str;
 use core::vec;
@@ -40,7 +40,7 @@ pub enum Json {
 }
 
 pub type List = ~[Json];
-pub type Object = linear::LinearMap<~str, Json>;
+pub type Object = LinearMap<~str, Json>;
 
 pub struct Error {
     line: uint,
@@ -673,7 +673,7 @@ priv impl Parser {
         self.bump();
         self.parse_whitespace();
 
-        let mut values = ~linear::LinearMap();
+        let mut values = ~LinearMap::new();
 
         if self.ch == '}' {
           self.bump();
@@ -913,7 +913,7 @@ pub impl Decoder: serialize::Decoder {
                 // FIXME(#3148) This hint should not be necessary.
                 let obj: &self/~Object = obj;
 
-                match obj.find_ref(&name.to_owned()) {
+                match obj.find(&name.to_owned()) {
                     None => fail fmt!("no such field: %s", name),
                     Some(json) => {
                         self.stack.push(json);
@@ -971,7 +971,7 @@ impl Json : Eq {
                         if d0.len() == d1.len() {
                             let mut equal = true;
                             for d0.each |k, v0| {
-                                match d1.find_ref(k) {
+                                match d1.find(k) {
                                     Some(v1) if v0 == v1 => { },
                                     _ => { equal = false; break }
                                 }
@@ -1177,9 +1177,9 @@ impl <A: ToJson> ~[A]: ToJson {
     fn to_json() -> Json { List(self.map(|elt| elt.to_json())) }
 }
 
-impl <A: ToJson Copy> linear::LinearMap<~str, A>: ToJson {
+impl <A: ToJson Copy> LinearMap<~str, A>: ToJson {
     fn to_json() -> Json {
-        let mut d = linear::LinearMap();
+        let mut d = LinearMap::new();
         for self.each() |key, value| {
             d.insert(copy *key, value.to_json());
         }
@@ -1190,7 +1190,7 @@ impl <A: ToJson Copy> linear::LinearMap<~str, A>: ToJson {
 /*
 impl <A: ToJson Copy> @std::map::HashMap<~str, A>: ToJson {
     fn to_json() -> Json {
-        let mut d = linear::LinearMap();
+        let mut d = LinearMap::new();
         for self.each_ref |key, value| {
             d.insert(copy *key, value.to_json());
         }
@@ -1225,10 +1225,10 @@ mod tests {
     use json::*;
 
     use core::result;
-    use core::send_map::linear;
+    use core::hashmap::linear::LinearMap;
 
     fn mk_object(items: &[(~str, Json)]) -> Json {
-        let mut d = ~linear::LinearMap();
+        let mut d = ~LinearMap::new();
 
         for items.each |item| {
             match *item {
diff --git a/src/libstd/map.rs b/src/libstd/map.rs
index 0b4c45da28e..4c05dd154ca 100644
--- a/src/libstd/map.rs
+++ b/src/libstd/map.rs
@@ -19,7 +19,6 @@ use core::ops;
 use core::to_str::ToStr;
 use core::mutable::Mut;
 use core::prelude::*;
-use core::send_map::linear::LinearMap;
 use core::to_bytes::IterBytes;
 use core::uint;
 use core::vec;
@@ -500,121 +499,6 @@ pub fn hash_from_vec<K: Eq IterBytes Hash Const Copy, V: Copy>(
     map
 }
 
-// FIXME #4431: Transitional
-impl<K: Eq IterBytes Hash Copy, V: Copy> @Mut<LinearMap<K, V>>:
-    Map<K, V> {
-    pure fn size() -> uint {
-        unsafe {
-            do self.borrow_const |p| {
-                p.len()
-            }
-        }
-    }
-
-    fn insert(key: K, value: V) -> bool {
-        do self.borrow_mut |p| {
-            p.insert(key, value)
-        }
-    }
-
-    pure fn contains_key(key: K) -> bool {
-        do self.borrow_const |p| {
-            p.contains_key(&key)
-        }
-    }
-
-    pure fn contains_key_ref(key: &K) -> bool {
-        do self.borrow_const |p| {
-            p.contains_key(key)
-        }
-    }
-
-    pure fn get(key: K) -> V {
-        do self.borrow_const |p| {
-            p.get(&key)
-        }
-    }
-
-    pure fn find(key: K) -> Option<V> {
-        unsafe {
-            do self.borrow_const |p| {
-                p.find(&key)
-            }
-        }
-    }
-
-    fn update_with_key(key: K, newval: V, ff: fn(K, V, V) -> V) -> bool {
-        match self.find(key) {
-            None            => return self.insert(key, newval),
-            Some(copy orig) => return self.insert(key, ff(key, orig, newval))
-        }
-    }
-
-    fn update(key: K, newval: V, ff: fn(V, V) -> V) -> bool {
-        return self.update_with_key(key, newval, |_k, v, v1| ff(v,v1));
-    }
-
-    fn remove(key: K) -> bool {
-        do self.borrow_mut |p| {
-            p.remove(&key)
-        }
-    }
-
-    fn clear() {
-        do self.borrow_mut |p| {
-            p.clear()
-        }
-    }
-
-    pure fn each(op: fn(key: K, value: V) -> bool) {
-        unsafe {
-            do self.borrow_imm |p| {
-                p.each(|k, v| op(*k, *v))
-            }
-        }
-    }
-
-    pure fn each_key(op: fn(key: K) -> bool) {
-        unsafe {
-            do self.borrow_imm |p| {
-                p.each_key(|k| op(*k))
-            }
-        }
-    }
-
-    pure fn each_value(op: fn(value: V) -> bool) {
-        unsafe {
-            do self.borrow_imm |p| {
-                p.each_value(|v| op(*v))
-            }
-        }
-    }
-
-    pure fn each_ref(op: fn(key: &K, value: &V) -> bool) {
-        unsafe {
-            do self.borrow_imm |p| {
-                p.each(op)
-            }
-        }
-    }
-
-    pure fn each_key_ref(op: fn(key: &K) -> bool) {
-        unsafe {
-            do self.borrow_imm |p| {
-                p.each_key(op)
-            }
-        }
-    }
-
-    pure fn each_value_ref(op: fn(value: &V) -> bool) {
-        unsafe {
-            do self.borrow_imm |p| {
-                p.each_value(op)
-            }
-        }
-    }
-}
-
 #[cfg(test)]
 mod tests {
     use map;
diff --git a/src/libstd/net_url.rs b/src/libstd/net_url.rs
index 5b377d9d932..0e352c78611 100644
--- a/src/libstd/net_url.rs
+++ b/src/libstd/net_url.rs
@@ -11,17 +11,13 @@
 //! Types/fns concerning URLs (see RFC 3986)
 #[forbid(deprecated_mode)];
 
-use map;
-use map::HashMap;
-
 use core::cmp::Eq;
 use core::dvec::DVec;
 use core::from_str::FromStr;
 use core::io::{Reader, ReaderUtil};
 use core::io;
 use core::prelude::*;
-use core::send_map::linear::LinearMap;
-use core::send_map;
+use core::hashmap::linear::LinearMap;
 use core::str;
 use core::to_bytes::IterBytes;
 use core::to_bytes;
@@ -244,11 +240,9 @@ pub fn encode_form_urlencoded(m: &LinearMap<~str, ~[~str]>) -> ~str {
  * Decode a string encoded with the 'application/x-www-form-urlencoded' media
  * type into a hashmap.
  */
-pub fn decode_form_urlencoded(
-    s: &[u8]
-) -> send_map::linear::LinearMap<~str, ~[~str]> {
+pub fn decode_form_urlencoded(s: &[u8]) -> LinearMap<~str, ~[~str]> {
     do io::with_bytes_reader(s) |rdr| {
-        let mut m = LinearMap();
+        let mut m = LinearMap::new();
         let mut key = ~"";
         let mut value = ~"";
         let mut parsing_key = true;
@@ -1061,18 +1055,18 @@ mod tests {
 
     #[test]
     fn test_encode_form_urlencoded() {
-        let mut m = LinearMap();
+        let mut m = LinearMap::new();
         assert encode_form_urlencoded(&m) == ~"";
 
         m.insert(~"", ~[]);
         m.insert(~"foo", ~[]);
         assert encode_form_urlencoded(&m) == ~"";
 
-        let mut m = LinearMap();
+        let mut m = LinearMap::new();
         m.insert(~"foo", ~[~"bar", ~"123"]);
         assert encode_form_urlencoded(&m) == ~"foo=bar&foo=123";
 
-        let mut m = LinearMap();
+        let mut m = LinearMap::new();
         m.insert(~"foo bar", ~[~"abc", ~"12 = 34"]);
         assert encode_form_urlencoded(&m) == ~"foo+bar=abc&foo+bar=12+%3D+34";
     }
diff --git a/src/libstd/treemap.rs b/src/libstd/treemap.rs
index 4b77e914ffb..95397254171 100644
--- a/src/libstd/treemap.rs
+++ b/src/libstd/treemap.rs
@@ -100,6 +100,26 @@ impl <K: Ord, V> TreeMap<K, V>: Map<K, V> {
     /// Visit all values in order
     pure fn each_value(&self, f: fn(&V) -> bool) { self.each(|_, v| f(v)) }
 
+    /// Return the value corresponding to the key in the map
+    pure fn find(&self, key: &K) -> Option<&self/V> {
+        let mut current: &self/Option<~TreeNode<K, V>> = &self.root;
+        loop {
+            match *current {
+              Some(ref r) => {
+                let r: &self/~TreeNode<K, V> = r; // FIXME: #3148
+                if *key < r.key {
+                    current = &r.left;
+                } else if r.key < *key {
+                    current = &r.right;
+                } else {
+                    return Some(&r.value);
+                }
+              }
+              None => return None
+            }
+        }
+    }
+
     /// Insert a key-value pair into the map. An existing value for a
     /// key is replaced by the new value. Return true if the key did
     /// not already exist in the map.
@@ -122,7 +142,6 @@ impl <K: Ord, V> TreeMap<K, V> {
     /// Create an empty TreeMap
     static pure fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
 
-
     /// Visit all key-value pairs in reverse order
     pure fn each_reverse(&self, f: fn(&K, &V) -> bool) {
         each_reverse(&self.root, f);
@@ -138,26 +157,6 @@ impl <K: Ord, V> TreeMap<K, V> {
         self.each_reverse(|_, v| f(v))
     }
 
-    /// Return the value corresponding to the key in the map
-    pure fn find(&self, key: &K) -> Option<&self/V> {
-        let mut current: &self/Option<~TreeNode<K, V>> = &self.root;
-        loop {
-            match *current {
-              Some(ref r) => {
-                let r: &self/~TreeNode<K, V> = r; // FIXME: #3148
-                if *key < r.key {
-                    current = &r.left;
-                } else if r.key < *key {
-                    current = &r.right;
-                } else {
-                    return Some(&r.value);
-                }
-              }
-              None => return None
-            }
-        }
-    }
-
     /// Get a lazy iterator over the key-value pairs in the map.
     /// Requires that it be frozen (immutable).
     pure fn iter(&self) -> TreeMapIterator/&self<K, V> {
@@ -209,10 +208,10 @@ impl <T: Eq Ord> TreeSet<T>: Eq {
 }
 
 impl <T: Ord> TreeSet<T>: Container {
-    /// Return the number of elements in the map
+    /// Return the number of elements in the set
     pure fn len(&self) -> uint { self.map.len() }
 
-    /// Return true if the map contains no elements
+    /// Return true if the set contains no elements
     pure fn is_empty(&self) -> bool { self.map.is_empty() }
 }
 
diff --git a/src/libstd/workcache.rs b/src/libstd/workcache.rs
index c0d762370c6..9572c07e715 100644
--- a/src/libstd/workcache.rs
+++ b/src/libstd/workcache.rs
@@ -22,7 +22,7 @@ use core::pipes::{recv, oneshot, PortOne, send_one};
 use core::prelude::*;
 use core::result;
 use core::run;
-use core::send_map::linear::LinearMap;
+use core::hashmap::linear::LinearMap;
 use core::task;
 use core::to_bytes;
 use core::mutable::Mut;
@@ -152,7 +152,7 @@ pub impl<S: Encoder> WorkMap: Encodable<S> {
 pub impl<D: Decoder> WorkMap: Decodable<D> {
     static fn decode(&self, d: &D) -> WorkMap {
         let v : ~[(WorkKey,~str)] = Decodable::decode(d);
-        let mut w = LinearMap();
+        let mut w = LinearMap::new();
         for v.each |&(k,v)| {
             w.insert(copy k, copy v);
         }
@@ -173,7 +173,7 @@ impl Database {
                declared_inputs: &WorkMap) ->
         Option<(WorkMap, WorkMap, ~str)> {
         let k = json_encode(&(fn_name, declared_inputs));
-        match self.db_cache.find(&k) {
+        match self.db_cache.find_copy(&k) {
             None => None,
             Some(v) => Some(json_decode(v))
         }
@@ -297,7 +297,7 @@ impl @Mut<Prep> : TPrep {
                 name: &str, val: &str) -> bool {
         do self.borrow_imm |p| {
             let k = kind.to_owned();
-            let f = (p.ctxt.freshness.get(&k))(name, val);
+            let f = (*p.ctxt.freshness.get(&k))(name, val);
             do p.ctxt.logger.borrow_imm |lg| {
                 if f {
                     lg.info(fmt!("%s %s:%s is fresh",
@@ -348,8 +348,8 @@ impl @Mut<Prep> : TPrep {
                     let blk = blk.unwrap();
                     let chan = ~mut Some(move chan);
                     do task::spawn |move blk, move chan| {
-                        let exe = Exec { discovered_inputs: LinearMap(),
-                                         discovered_outputs: LinearMap() };
+                        let exe = Exec{discovered_inputs: LinearMap::new(),
+                                       discovered_outputs: LinearMap::new()};
                         let chan = option::swap_unwrap(&mut *chan);
                         let v = blk(&exe);
                         send_one(move chan, (move exe, move v));
@@ -411,10 +411,10 @@ fn test() {
     use io::WriterUtil;
 
     let db = @Mut(Database { db_filename: Path("db.json"),
-                             db_cache: LinearMap(),
+                             db_cache: LinearMap::new(),
                              db_dirty: false });
     let lg = @Mut(Logger { a: () });
-    let cfg = @LinearMap();
+    let cfg = @LinearMap::new();
     let cx = @Context::new(db, lg, cfg);
     let w:Work<~str> = do cx.prep("test1") |prep| {
         let pth = Path("foo.c");
diff --git a/src/test/bench/core-map.rs b/src/test/bench/core-map.rs
index 83ca9fd06c9..d401b594c4c 100644
--- a/src/test/bench/core-map.rs
+++ b/src/test/bench/core-map.rs
@@ -8,16 +8,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-/*
-
-
-
-*/
-
 extern mod std;
 use std::map;
-use core::mutable::Mut;
-use core::send_map::linear::*;
+use std::treemap::TreeMap;
+use core::hashmap::linear::*;
 use core::io::WriterUtil;
 
 struct Results {
@@ -38,13 +32,10 @@ fn timed(result: &mut float,
     *result = (end - start);
 }
 
-fn int_benchmarks<M: map::Map<uint, uint>>(make_map: fn() -> M,
-                                           rng: @rand::Rng,
-                                           num_keys: uint,
-                                           results: &mut Results) {
+fn old_int_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
 
     {
-        let map = make_map();
+        let map = map::HashMap();
         do timed(&mut results.sequential_ints) {
             for uint::range(0, num_keys) |i| {
                 map.insert(i, i+1);
@@ -57,7 +48,7 @@ fn int_benchmarks<M: map::Map<uint, uint>>(make_map: fn() -> M,
     }
 
     {
-        let map = make_map();
+        let map = map::HashMap();
         do timed(&mut results.random_ints) {
             for uint::range(0, num_keys) |i| {
                 map.insert(rng.next() as uint, i);
@@ -66,7 +57,7 @@ fn int_benchmarks<M: map::Map<uint, uint>>(make_map: fn() -> M,
     }
 
     {
-        let map = make_map();
+        let map = map::HashMap();
         for uint::range(0, num_keys) |i| {
             map.insert(i, i);;
         }
@@ -79,12 +70,9 @@ fn int_benchmarks<M: map::Map<uint, uint>>(make_map: fn() -> M,
     }
 }
 
-fn str_benchmarks<M: map::Map<~str, uint>>(make_map: fn() -> M,
-                                           rng: @rand::Rng,
-                                           num_keys: uint,
-                                           results: &mut Results) {
+fn old_str_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
     {
-        let map = make_map();
+        let map = map::HashMap();
         do timed(&mut results.sequential_strings) {
             for uint::range(0, num_keys) |i| {
                 let s = uint::to_str(i, 10);
@@ -99,7 +87,7 @@ fn str_benchmarks<M: map::Map<~str, uint>>(make_map: fn() -> M,
     }
 
     {
-        let map = make_map();
+        let map = map::HashMap();
         do timed(&mut results.random_strings) {
             for uint::range(0, num_keys) |i| {
                 let s = uint::to_str(rng.next() as uint, 10);
@@ -109,7 +97,7 @@ fn str_benchmarks<M: map::Map<~str, uint>>(make_map: fn() -> M,
     }
 
     {
-        let map = make_map();
+        let map = map::HashMap();
         for uint::range(0, num_keys) |i| {
             map.insert(uint::to_str(i, 10), i);
         }
@@ -121,6 +109,158 @@ fn str_benchmarks<M: map::Map<~str, uint>>(make_map: fn() -> M,
     }
 }
 
+fn linear_int_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
+    {
+        let mut map = LinearMap::new();
+        do timed(&mut results.sequential_ints) {
+            for uint::range(0, num_keys) |i| {
+                map.insert(i, i+1);
+            }
+
+            for uint::range(0, num_keys) |i| {
+                assert map.find(&i).unwrap() == &(i+1);
+            }
+        }
+    }
+
+    {
+        let mut map = LinearMap::new();
+        do timed(&mut results.random_ints) {
+            for uint::range(0, num_keys) |i| {
+                map.insert(rng.next() as uint, i);
+            }
+        }
+    }
+
+    {
+        let mut map = LinearMap::new();
+        for uint::range(0, num_keys) |i| {
+            map.insert(i, i);;
+        }
+
+        do timed(&mut results.delete_ints) {
+            for uint::range(0, num_keys) |i| {
+                assert map.remove(&i);
+            }
+        }
+    }
+}
+
+fn linear_str_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
+    {
+        let mut map = LinearMap::new();
+        do timed(&mut results.sequential_strings) {
+            for uint::range(0, num_keys) |i| {
+                let s = uint::to_str(i, 10);
+                map.insert(s, i);
+            }
+
+            for uint::range(0, num_keys) |i| {
+                let s = uint::to_str(i, 10);
+                assert map.find(&s).unwrap() == &i;
+            }
+        }
+    }
+
+    {
+        let mut map = LinearMap::new();
+        do timed(&mut results.random_strings) {
+            for uint::range(0, num_keys) |i| {
+                let s = uint::to_str(rng.next() as uint, 10);
+                map.insert(s, i);
+            }
+        }
+    }
+
+    {
+        let mut map = LinearMap::new();
+        for uint::range(0, num_keys) |i| {
+            map.insert(uint::to_str(i, 10), i);
+        }
+        do timed(&mut results.delete_strings) {
+            for uint::range(0, num_keys) |i| {
+                assert map.remove(&uint::to_str(i, 10));
+            }
+        }
+    }
+}
+
+fn tree_int_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
+    {
+        let mut map = TreeMap::new();
+        do timed(&mut results.sequential_ints) {
+            for uint::range(0, num_keys) |i| {
+                map.insert(i, i+1);
+            }
+
+            for uint::range(0, num_keys) |i| {
+                assert map.find(&i).unwrap() == &(i+1);
+            }
+        }
+    }
+
+    {
+        let mut map = TreeMap::new();
+        do timed(&mut results.random_ints) {
+            for uint::range(0, num_keys) |i| {
+                map.insert(rng.next() as uint, i);
+            }
+        }
+    }
+
+    {
+        let mut map = TreeMap::new();
+        for uint::range(0, num_keys) |i| {
+            map.insert(i, i);;
+        }
+
+        do timed(&mut results.delete_ints) {
+            for uint::range(0, num_keys) |i| {
+                assert map.remove(&i);
+            }
+        }
+    }
+}
+
+fn tree_str_benchmarks(rng: @rand::Rng, num_keys: uint, results: &mut Results) {
+    {
+        let mut map = TreeMap::new();
+        do timed(&mut results.sequential_strings) {
+            for uint::range(0, num_keys) |i| {
+                let s = uint::to_str(i, 10);
+                map.insert(s, i);
+            }
+
+            for uint::range(0, num_keys) |i| {
+                let s = uint::to_str(i, 10);
+                assert map.find(&s).unwrap() == &i;
+            }
+        }
+    }
+
+    {
+        let mut map = TreeMap::new();
+        do timed(&mut results.random_strings) {
+            for uint::range(0, num_keys) |i| {
+                let s = uint::to_str(rng.next() as uint, 10);
+                map.insert(s, i);
+            }
+        }
+    }
+
+    {
+        let mut map = TreeMap::new();
+        for uint::range(0, num_keys) |i| {
+            map.insert(uint::to_str(i, 10), i);
+        }
+        do timed(&mut results.delete_strings) {
+            for uint::range(0, num_keys) |i| {
+                assert map.remove(&uint::to_str(i, 10));
+            }
+        }
+    }
+}
+
 fn write_header(header: &str) {
     io::stdout().write_str(header);
     io::stdout().write_str("\n");
@@ -167,22 +307,24 @@ fn main() {
     {
         let rng = rand::seeded_rng(&seed);
         let mut results = empty_results();
-        int_benchmarks::<map::HashMap<uint, uint>>(
-            map::HashMap, rng, num_keys, &mut results);
-        str_benchmarks::<map::HashMap<~str, uint>>(
-            map::HashMap, rng, num_keys, &mut results);
-        write_results("libstd::map::hashmap", &results);
+        old_int_benchmarks(rng, num_keys, &mut results);
+        old_str_benchmarks(rng, num_keys, &mut results);
+        write_results("std::map::HashMap", &results);
+    }
+
+    {
+        let rng = rand::seeded_rng(&seed);
+        let mut results = empty_results();
+        linear_int_benchmarks(rng, num_keys, &mut results);
+        linear_str_benchmarks(rng, num_keys, &mut results);
+        write_results("core::hashmap::linear::LinearMap", &results);
     }
 
     {
         let rng = rand::seeded_rng(&seed);
         let mut results = empty_results();
-        int_benchmarks::<@Mut<LinearMap<uint, uint>>>(
-            || @Mut(LinearMap()),
-            rng, num_keys, &mut results);
-        str_benchmarks::<@Mut<LinearMap<~str, uint>>>(
-            || @Mut(LinearMap()),
-            rng, num_keys, &mut results);
-        write_results("libstd::map::hashmap", &results);
+        tree_int_benchmarks(rng, num_keys, &mut results);
+        tree_str_benchmarks(rng, num_keys, &mut results);
+        write_results("std::treemap::TreeMap", &results);
     }
 }
diff --git a/src/test/run-pass/issue-2804.rs b/src/test/run-pass/issue-2804.rs
index a46a9b30d6d..c360a184d01 100644
--- a/src/test/run-pass/issue-2804.rs
+++ b/src/test/run-pass/issue-2804.rs
@@ -23,7 +23,7 @@ enum object
 
 fn lookup(table: ~json::Object, key: ~str, default: ~str) -> ~str
 {
-    match table.find(&key)
+    match table.find_copy(&key)
     {
         option::Some(std::json::String(copy s)) =>
         {
diff --git a/src/test/run-pass/issue-4016.rs b/src/test/run-pass/issue-4016.rs
index a0f93ddd5d1..253e0bd633b 100644
--- a/src/test/run-pass/issue-4016.rs
+++ b/src/test/run-pass/issue-4016.rs
@@ -11,7 +11,7 @@
 // xfail-test
 extern mod std;
 
-use send_map::linear;
+use hashmap::linear;
 use std::json;
 use std::serialization::{Deserializable, deserialize};