auto merge of #5509 : thestinger/rust/oldmap, r=brson

The reasoning for doing it this way is that it's much easier to transition method-by-method to the `Map` API than trying to do the migration all at once.

I found an issue unrelated to my changes in one of the run-fail tests - if it uses `LinearMap`, it still fails but exits with 0. I xfailed it for now and opened [an issue](https://github.com/mozilla/rust/issues/5512), because it's not caused by these changes.

1 files changed, 28 insertions, 335 deletions

diff --git a/src/libstd/oldmap.rs b/src/libstd/oldmap.rs
index 02c610e4854..b40237cf584 100644
--- a/src/libstd/oldmap.rs
+++ b/src/libstd/oldmap.rs
@@ -8,13 +8,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! A map type - **deprecated**, use `core::hashmap` instead
+//! A deprecated compatibility layer on top of `core::hashmap`
 
-use core::container::{Container, Mutable, Map};
-use core::cmp::Eq;
+use core::prelude::*;
 use core::hash::Hash;
-use core::io::WriterUtil;
-use core::to_str::ToStr;
 use core::prelude::*;
 use core::to_bytes::IterBytes;
 use core::vec;
@@ -24,335 +21,68 @@ pub type Set<K> = HashMap<K, ()>;
 
 pub type HashMap<K, V> = chained::T<K, V>;
 
-pub mod util {
-    pub struct Rational {
-        // : int::positive(*.den);
-        num: int,
-        den: int,
-    }
-
-    pub fn rational_leq(x: Rational, y: Rational) -> bool {
-        // NB: Uses the fact that rationals have positive denominators WLOG:
-
-        x.num * y.den <= y.num * x.den
-    }
-}
-
-
-// FIXME (#2344): package this up and export it as a datatype usable for
-// external code that doesn't want to pay the cost of a box.
 pub mod chained {
-    use super::util;
-
-    use core::io;
     use core::ops;
-    use core::option;
     use core::prelude::*;
-    use core::uint;
-    use core::vec;
-
-    static initial_capacity: uint = 32u; // 2^5
-
-    struct Entry<K, V> {
-        hash: uint,
-        key: K,
-        value: V,
-        mut next: Option<@Entry<K, V>>
-    }
+    use core::hashmap::linear::LinearMap;
 
     struct HashMap_<K, V> {
-        mut count: uint,
-        mut chains: ~[Option<@Entry<K,V>>]
-    }
-
-    pub type T<K, V> = @HashMap_<K, V>;
-
-    enum SearchResult<K, V> {
-        NotFound,
-        FoundFirst(uint, @Entry<K,V>),
-        FoundAfter(@Entry<K,V>, @Entry<K,V>)
+        priv map: LinearMap<K, V>
     }
 
-    priv impl<K:Eq + IterBytes + Hash,V> HashMap_<K, V> {
-        fn search_rem(&self, k: &K, h: uint, idx: uint,
-                           e_root: @Entry<K,V>) -> SearchResult<K,V> {
-            let mut e0 = e_root;
-            let mut comp = 1u;   // for logging
-            loop {
-                match copy e0.next {
-                  None => {
-                    debug!("search_tbl: absent, comp %u, hash %u, idx %u",
-                           comp, h, idx);
-                    return NotFound;
-                  }
-                  Some(e1) => {
-                    comp += 1u;
-                    if e1.hash == h && e1.key == *k {
-                        debug!(
-                            "search_tbl: present, comp %u, hash %u, idx %u",
-                            comp, h, idx);
-                        return FoundAfter(e0, e1);
-                    } else {
-                        e0 = e1;
-                    }
-                  }
-                }
-            };
-        }
-
-        fn search_tbl(&self, k: &K, h: uint) -> SearchResult<K,V> {
-            let idx = h % vec::uniq_len(&const self.chains);
-            match copy self.chains[idx] {
-              None => {
-                debug!("search_tbl: none, comp %u, hash %u, idx %u",
-                       0u, h, idx);
-                return NotFound;
-              }
-              Some(e) => {
-                if e.hash == h && e.key == *k {
-                    debug!("search_tbl: present, comp %u, hash %u, \
-                           idx %u", 1u, h, idx);
-                    return FoundFirst(idx, e);
-                } else {
-                    return self.search_rem(k, h, idx, e);
-                }
-              }
-            }
-        }
-
-        fn rehash(@self) {
-            let n_old_chains = vec::uniq_len(&const self.chains);
-            let n_new_chains: uint = uint::next_power_of_two(n_old_chains+1u);
-            let mut new_chains = chains(n_new_chains);
-            for self.each_entry |entry| {
-                let idx = entry.hash % n_new_chains;
-                entry.next = new_chains[idx];
-                new_chains[idx] = Some(entry);
-            }
-            self.chains = new_chains;
-        }
-    }
+    pub type T<K, V> = @mut HashMap_<K, V>;
 
     pub impl<K:Eq + IterBytes + Hash,V> HashMap_<K, V> {
-        fn each_entry(&self, blk: &fn(@Entry<K,V>) -> bool) {
-            // n.b. we can't use vec::iter() here because self.chains
-            // is stored in a mutable location.
-            let mut i = 0u, n = vec::uniq_len(&const self.chains);
-            while i < n {
-                let mut chain = self.chains[i];
-                loop {
-                    chain = match chain {
-                      None => break,
-                      Some(entry) => {
-                        let next = entry.next;
-                        if !blk(entry) { return; }
-                        next
-                      }
-                    }
-                }
-                i += 1u;
-            }
-        }
-
-        fn clear(@self) {
-            self.count = 0u;
-            self.chains = chains(initial_capacity);
+        fn clear(&mut self) {
+            self.map.clear()
         }
     }
 
     impl<K:Eq + IterBytes + Hash,V> Container for HashMap_<K, V> {
-        fn len(&const self) -> uint { self.count }
-        fn is_empty(&const self) -> bool { self.count == 0 }
+        fn len(&const self) -> uint { self.map.len() }
+        fn is_empty(&const self) -> bool { self.map.is_empty() }
     }
 
     pub impl<K:Eq + IterBytes + Hash,V> HashMap_<K, V> {
-        fn contains_key(@self, k: &K) -> bool {
-            let hash = k.hash_keyed(0,0) as uint;
-            match self.search_tbl(k, hash) {
-              NotFound => false,
-              FoundFirst(*) | FoundAfter(*) => true
-            }
+        fn contains_key(&self, k: &K) -> bool {
+            self.map.contains_key(k)
         }
 
-        fn insert(@self, k: K, v: V) -> bool {
-            let hash = k.hash_keyed(0,0) as uint;
-            match self.search_tbl(&k, hash) {
-              NotFound => {
-                self.count += 1u;
-                let idx = hash % vec::uniq_len(&const self.chains);
-                let old_chain = self.chains[idx];
-                self.chains[idx] = Some(@Entry {
-                    hash: hash,
-                    key: k,
-                    value: v,
-                    next: old_chain});
-
-                // consider rehashing if more 3/4 full
-                let nchains = vec::uniq_len(&const self.chains);
-                let load = util::Rational {
-                    num: (self.count + 1u) as int,
-                    den: nchains as int,
-                };
-                if !util::rational_leq(load, util::Rational {num:3, den:4}) {
-                    self.rehash();
-                }
-
-                return true;
-              }
-              FoundFirst(idx, entry) => {
-                self.chains[idx] = Some(@Entry {
-                    hash: hash,
-                    key: k,
-                    value: v,
-                    next: entry.next});
-                return false;
-              }
-              FoundAfter(prev, entry) => {
-                prev.next = Some(@Entry {
-                    hash: hash,
-                    key: k,
-                    value: v,
-                    next: entry.next});
-                return false;
-              }
-            }
+        fn insert(&mut self, k: K, v: V) -> bool {
+            self.map.insert(k, v)
         }
 
-        fn remove(@self, k: &K) -> bool {
-            match self.search_tbl(k, k.hash_keyed(0,0) as uint) {
-              NotFound => false,
-              FoundFirst(idx, entry) => {
-                self.count -= 1u;
-                self.chains[idx] = entry.next;
-                true
-              }
-              FoundAfter(eprev, entry) => {
-                self.count -= 1u;
-                eprev.next = entry.next;
-                true
-              }
-            }
+        fn remove(&mut self, k: &K) -> bool {
+            self.map.remove(k)
         }
 
-        fn each(@self, blk: &fn(key: &K, value: &V) -> bool) {
-            for self.each_entry |entry| {
-                if !blk(&entry.key, &entry.value) { break; }
-            }
+        fn each(&self, blk: &fn(key: &K, value: &V) -> bool) {
+            do self.map.each |&(k, v)| { blk(k, v) }
         }
 
-        fn each_key(@self, blk: &fn(key: &K) -> bool) {
-            self.each(|k, _v| blk(k))
+        fn each_key(&self, blk: &fn(key: &K) -> bool) {
+            self.map.each_key(blk)
         }
 
-        fn each_value(@self, blk: &fn(value: &V) -> bool) {
-            self.each(|_k, v| blk(v))
+        fn each_value(&self, blk: &fn(value: &V) -> bool) {
+            self.map.each_value(blk)
         }
     }
 
     pub impl<K:Eq + IterBytes + Hash + Copy,V:Copy> HashMap_<K, V> {
         fn find(&self, k: &K) -> Option<V> {
-            match self.search_tbl(k, k.hash_keyed(0,0) as uint) {
-              NotFound => None,
-              FoundFirst(_, entry) => Some(entry.value),
-              FoundAfter(_, entry) => Some(entry.value)
-            }
+            self.map.find(k).map(|&x| copy *x)
         }
 
-        fn update_with_key(@self, key: K, newval: V, ff: &fn(K, V, V) -> V)
-                        -> bool {
-/*
-            match self.find(key) {
-                None            => return self.insert(key, val),
-                Some(copy orig) => return self.insert(key, ff(key, orig, val))
-            }
-*/
-
-            let hash = key.hash_keyed(0,0) as uint;
-            match self.search_tbl(&key, hash) {
-              NotFound => {
-                self.count += 1u;
-                let idx = hash % vec::uniq_len(&const self.chains);
-                let old_chain = self.chains[idx];
-                self.chains[idx] = Some(@Entry {
-                    hash: hash,
-                    key: key,
-                    value: newval,
-                    next: old_chain});
-
-                // consider rehashing if more 3/4 full
-                let nchains = vec::uniq_len(&const self.chains);
-                let load = util::Rational {
-                    num: (self.count + 1u) as int,
-                    den: nchains as int,
-                };
-                if !util::rational_leq(load, util::Rational {num:3, den:4}) {
-                    self.rehash();
-                }
-
-                return true;
-              }
-              FoundFirst(idx, entry) => {
-                self.chains[idx] = Some(@Entry {
-                    hash: hash,
-                    key: key,
-                    value: ff(key, entry.value, newval),
-                    next: entry.next});
-                return false;
-              }
-              FoundAfter(prev, entry) => {
-                prev.next = Some(@Entry {
-                    hash: hash,
-                    key: key,
-                    value: ff(key, entry.value, newval),
-                    next: entry.next});
-                return false;
-              }
+        fn update(&mut self, key: K, newval: V, ff: &fn(V, V) -> V) -> bool {
+            match self.find(&key) {
+                None => self.insert(key, newval),
+                Some(orig) => self.insert(key, ff(orig, newval))
             }
         }
 
-        fn update(@self, key: K, newval: V, ff: &fn(V, V) -> V) -> bool {
-            return self.update_with_key(key, newval, |_k, v, v1| ff(v,v1));
-        }
-
         fn get(&self, k: &K) -> V {
-            let opt_v = self.find(k);
-            if opt_v.is_none() {
-                fail!(fmt!("Key not found in table: %?", k));
-            }
-            option::unwrap(opt_v)
-        }
-    }
-
-    pub impl<K:Eq + IterBytes + Hash + Copy + ToStr,V:ToStr + Copy>
-            HashMap_<K, V> {
-        fn to_writer(&self, wr: @io::Writer) {
-            if self.count == 0u {
-                wr.write_str(~"{}");
-                return;
-            }
-
-            wr.write_str(~"{ ");
-            let mut first = true;
-            for self.each_entry |entry| {
-                if !first {
-                    wr.write_str(~", ");
-                }
-                first = false;
-                wr.write_str(entry.key.to_str());
-                wr.write_str(~": ");
-                wr.write_str((copy entry.value).to_str());
-            };
-            wr.write_str(~" }");
-        }
-    }
-
-    impl<K:Eq + IterBytes + Hash + Copy + ToStr,V:ToStr + Copy> ToStr
-            for HashMap_<K, V> {
-        fn to_str(&self) -> ~str {
-            unsafe {
-                // Meh -- this should be safe
-                do io::with_str_writer |wr| { self.to_writer(wr) }
-            }
+            copy *self.map.get(k)
         }
     }
 
@@ -363,14 +93,8 @@ pub mod chained {
         }
     }
 
-    fn chains<K,V>(nchains: uint) -> ~[Option<@Entry<K,V>>] {
-        vec::from_elem(nchains, None)
-    }
-
     pub fn mk<K:Eq + IterBytes + Hash,V:Copy>() -> T<K,V> {
-        let slf: T<K, V> = @HashMap_ {count: 0u,
-                                      chains: chains(initial_capacity)};
-        slf
+        @mut HashMap_{map: LinearMap::new()}
     }
 }
 
@@ -661,35 +385,4 @@ mod tests {
         fail_unless!(map.get(&~"b") == 2);
         fail_unless!(map.get(&~"c") == 3);
     }
-
-    #[test]
-    fn test_update_with_key() {
-        let map = HashMap::<~str, uint>();
-
-        // given a new key, initialize it with this new count, given
-        // given an existing key, add more to its count
-        fn addMoreToCount(_k: ~str, v0: uint, v1: uint) -> uint {
-            v0 + v1
-        }
-
-        fn addMoreToCount_simple(v0: uint, v1: uint) -> uint {
-            v0 + v1
-        }
-
-        // count the number of several types of animal,
-        // adding in groups as we go
-        map.update(~"cat",      1, addMoreToCount_simple);
-        map.update_with_key(~"mongoose", 1, addMoreToCount);
-        map.update(~"cat",      7, addMoreToCount_simple);
-        map.update_with_key(~"ferret",   3, addMoreToCount);
-        map.update_with_key(~"cat",      2, addMoreToCount);
-
-        // check the total counts
-        fail_unless!(map.find(&~"cat").get() == 10);
-        fail_unless!(map.find(&~"ferret").get() == 3);
-        fail_unless!(map.find(&~"mongoose").get() == 1);
-
-        // sadly, no mythical animals were counted!
-        fail_unless!(map.find(&~"unicorn").is_none());
-    }
 }