diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/comp/metadata/creader.rs | 14 | ||||
| -rw-r--r-- | src/comp/middle/ast_map.rs | 80 | ||||
| -rw-r--r-- | src/comp/middle/tstate/auxiliary.rs | 6 | ||||
| -rw-r--r-- | src/comp/middle/tstate/collect_locals.rs | 2 | ||||
| -rw-r--r-- | src/comp/middle/tstate/pre_post_conditions.rs | 2 | ||||
| -rw-r--r-- | src/libstd/json.rs | 2 | ||||
| -rw-r--r-- | src/libstd/map.rs | 133 | ||||
| -rw-r--r-- | src/libstd/smallintmap.rs | 64 | ||||
| -rw-r--r-- | src/test/stdtest/map.rs | 10 |
9 files changed, 129 insertions, 184 deletions
diff --git a/src/comp/metadata/creader.rs b/src/comp/metadata/creader.rs index 167e6bbcbab..08df19b54e9 100644 --- a/src/comp/metadata/creader.rs +++ b/src/comp/metadata/creader.rs @@ -20,10 +20,9 @@ export list_file_metadata; // Traverses an AST, reading all the information about use'd crates and native // libraries necessary for later resolving, typechecking, linking, etc. fn read_crates(sess: session::session, crate: ast::crate) { - let e = - @{sess: sess, - crate_cache: @std::map::new_str_hash::<int>(), - mutable next_crate_num: 1}; + let e = @{sess: sess, + crate_cache: std::map::new_str_hash::<int>(), + mutable next_crate_num: 1}; let v = visit::mk_simple_visitor(@{visit_view_item: bind visit_view_item(e, _), @@ -32,10 +31,9 @@ fn read_crates(sess: session::session, crate: ast::crate) { visit::visit_crate(crate, (), v); } -type env = - @{sess: session::session, - crate_cache: @hashmap<str, int>, - mutable next_crate_num: ast::crate_num}; +type env = @{sess: session::session, + crate_cache: hashmap<str, int>, + mutable next_crate_num: ast::crate_num}; fn visit_view_item(e: env, i: @ast::view_item) { alt i.node { diff --git a/src/comp/middle/ast_map.rs b/src/comp/middle/ast_map.rs index b5e53ab305a..c9382589d73 100644 --- a/src/comp/middle/ast_map.rs +++ b/src/comp/middle/ast_map.rs @@ -1,5 +1,5 @@ import option; -import std::smallintmap; +import std::map; import syntax::ast::*; import syntax::ast_util; import syntax::{visit, codemap}; @@ -18,14 +18,11 @@ tag ast_node { node_res_ctor(@item); } -type map = std::map::hashmap<node_id, ast_node>; +type map = std::map::map<node_id, ast_node>; type ctx = @{map: map, mutable local_id: uint}; fn map_crate(c: crate) -> map { - // FIXME: This is using an adapter to convert the smallintmap - // interface to the hashmap interface. It would be better to just - // convert everything to use the smallintmap. - let cx = @{map: new_smallintmap_int_adapter::<ast_node>(), + let cx = @{map: std::map::new_int_hash(), mutable local_id: 0u}; let v_map = visit::mk_simple_visitor @@ -98,77 +95,6 @@ fn map_expr(cx: ctx, ex: @expr) { } } -fn new_smallintmap_int_adapter<V: copy>() -> std::map::hashmap<int, V> { - let key_idx = fn (&&key: int) -> uint { key as uint }; - let idx_key = fn (idx: uint) -> int { idx as int }; - ret new_smallintmap_adapter(key_idx, idx_key); -} - -// This creates an object with the hashmap interface backed -// by the smallintmap type, because I don't want to go through -// the entire codebase adapting all the callsites to the different -// interface. -// FIXME: hashmap and smallintmap should support the same interface. -fn new_smallintmap_adapter<K: copy, V: copy>(key_idx: fn(K) -> uint, - idx_key: fn(uint) -> K) - -> std::map::hashmap<K, V> { - - obj adapter<K: copy, V: copy>(map: smallintmap::smallintmap<V>, - key_idx: fn(K) -> uint, - idx_key: fn(uint) -> K) { - - fn size() -> uint { fail } - - fn insert(key: K, value: V) -> bool { - let exists = smallintmap::contains_key(map, key_idx(key)); - smallintmap::insert(map, key_idx(key), value); - ret !exists; - } - - fn contains_key(key: K) -> bool { - ret smallintmap::contains_key(map, key_idx(key)); - } - - fn get(key: K) -> V { ret smallintmap::get(map, key_idx(key)); } - - fn find(key: K) -> option::t<V> { - ret smallintmap::find(map, key_idx(key)); - } - - fn remove(_key: K) -> option::t<V> { fail } - - fn rehash() { fail } - - fn items(it: block(K, V)) { - let idx = 0u; - for item in map.v { - alt item { - option::some(elt) { - it(idx_key(idx), elt); - } - option::none. { } - } - idx += 1u; - } - } - fn keys(it: block(K)) { - let idx = 0u; - for item in map.v { - if item != option::none { it(idx_key(idx)); } - idx += 1u; - } - } - fn values(it: block(V)) { - for item in map.v { - alt item { option::some(elt) { it(elt); } _ {} } - } - } - } - - let map = smallintmap::mk::<V>(); - ret adapter(map, key_idx, idx_key); -} - fn node_span(node: ast_node) -> codemap::span { alt node { node_item(item) { item.span } diff --git a/src/comp/middle/tstate/auxiliary.rs b/src/comp/middle/tstate/auxiliary.rs index 0b021bbeac4..de723dc16cc 100644 --- a/src/comp/middle/tstate/auxiliary.rs +++ b/src/comp/middle/tstate/auxiliary.rs @@ -218,7 +218,7 @@ type sp_constr = spanned<tsconstr>; type norm_constraint = {bit_num: uint, c: sp_constr}; -type constr_map = @std::map::hashmap<def_id, constraint>; +type constr_map = std::map::hashmap<def_id, constraint>; /* Contains stuff that has to be computed up front */ /* For easy access, the fn_info stores two special constraints for each @@ -278,7 +278,7 @@ type node_ann_table = @mutable [mutable ts_ann]; /* mapping from function name to fn_info map */ -type fn_info_map = @std::map::hashmap<node_id, fn_info>; +type fn_info_map = std::map::hashmap<node_id, fn_info>; type fn_ctxt = {enclosing: fn_info, id: node_id, name: ident, ccx: crate_ctxt}; @@ -483,7 +483,7 @@ fn num_constraints(m: fn_info) -> uint { ret m.num_constraints; } fn new_crate_ctxt(cx: ty::ctxt) -> crate_ctxt { let na: [mutable ts_ann] = [mutable]; - ret {tcx: cx, node_anns: @mutable na, fm: @new_int_hash::<fn_info>()}; + ret {tcx: cx, node_anns: @mutable na, fm: new_int_hash::<fn_info>()}; } /* Use e's type to determine whether it returns. diff --git a/src/comp/middle/tstate/collect_locals.rs b/src/comp/middle/tstate/collect_locals.rs index 60c79468589..939197716b4 100644 --- a/src/comp/middle/tstate/collect_locals.rs +++ b/src/comp/middle/tstate/collect_locals.rs @@ -102,7 +102,7 @@ fn mk_fn_info(ccx: crate_ctxt, f_sp: span, id: node_id) { let name = visit::name_of_fn(fk); - let res_map = @new_def_hash::<constraint>(); + let res_map = new_def_hash::<constraint>(); let next: uint = 0u; let cx: ctxt = find_locals(ccx.tcx, fk, f_decl, f_body, f_sp, id); diff --git a/src/comp/middle/tstate/pre_post_conditions.rs b/src/comp/middle/tstate/pre_post_conditions.rs index e4d00120aac..244f696549e 100644 --- a/src/comp/middle/tstate/pre_post_conditions.rs +++ b/src/comp/middle/tstate/pre_post_conditions.rs @@ -44,7 +44,7 @@ fn find_pre_post_item(ccx: crate_ctxt, i: item) { { // just bogus enclosing: - {constrs: @new_def_hash::<constraint>(), + {constrs: new_def_hash::<constraint>(), num_constraints: 0u, cf: return_val, i_return: ninit(0, ""), diff --git a/src/libstd/json.rs b/src/libstd/json.rs index 64ce2794bb4..3e134c743ed 100644 --- a/src/libstd/json.rs +++ b/src/libstd/json.rs @@ -33,7 +33,7 @@ tag json { /* Variant: list */ list(@[json]); /* Variant: dict */ - dict(map::hashmap<str,json>); + dict(map::map<str,json>); /* Variant: null */ null; } diff --git a/src/libstd/map.rs b/src/libstd/map.rs index 727d32ef65a..0ea2f35d719 100644 --- a/src/libstd/map.rs +++ b/src/libstd/map.rs @@ -1,7 +1,7 @@ /* Module: map -A hashmap +A map type */ /* Section: Types */ @@ -25,14 +25,17 @@ type eqfn<K> = fn(K, K) -> bool; /* Type: hashset -A convenience type to treat a hashmap as a set +A convenience type to treat a map as a set */ -type hashset<K> = hashmap<K, ()>; +type set<K> = map<K, ()>; + +// Temporary alias to make migration easier +type hashmap<K, V> = map<K, V>; /* -Obj: hashmap +IFace: map */ -type hashmap<K, V> = obj { +iface map<K: copy, V: copy> { /* Method: size @@ -72,20 +75,14 @@ type hashmap<K, V> = obj { Get the value for the specified key. If the key does not exist in the map then returns none. */ - fn find(K) -> core::option::t<V>; + fn find(K) -> option::t<V>; /* Method: remove Remove and return a value from the map. If the key does not exist in the map then returns none. */ - fn remove(K) -> core::option::t<V>; - /* - Method: rehash - - Force map growth and rehashing - */ - fn rehash(); + fn remove(K) -> option::t<V>; /* Method: items @@ -98,46 +95,44 @@ type hashmap<K, V> = obj { Iterate over all the keys in the map */ fn keys(block(K)); - /* Iterate over all the values in the map */ fn values(block(V)); -}; - -/* Section: Operations */ +} +// FIXME: package this up and export it as a datatype usable for +// external code that doesn't want to pay the cost of a box and vtable +// lookups. mod chained { - type entry<K: copy, V: copy> = { + type entry<K, V> = { hash: uint, key: K, mutable value: V, mutable next: chain<K, V> }; - tag chain<K: copy, V: copy> { + tag chain<K, V> { present(@entry<K, V>); absent; } - type t<K: copy, V: copy> = { + type t<K, V> = { mutable size: uint, mutable chains: [mutable chain<K,V>], hasher: hashfn<K>, eqer: eqfn<K> }; - tag search_result<K: copy, V: copy> { + tag search_result<K, V> { not_found; found_first(uint, @entry<K,V>); found_after(@entry<K,V>, @entry<K,V>); } - fn search_rem<K: copy, V: copy>(tbl: t<K,V>, - k: K, - h: uint, - idx: uint, - e_root: @entry<K,V>) -> search_result<K,V> { + fn search_rem<K: copy, V: copy>( + tbl: t<K,V>, k: K, h: uint, idx: uint, + e_root: @entry<K,V>) -> search_result<K,V> { let e0 = e_root; let comp = 1u; // for logging while true { @@ -295,62 +290,40 @@ mod chained { } } - obj o<K: copy, V: copy>(tbl: @t<K,V>, - lf: util::rational) { - fn size() -> uint { - ret tbl.size; - } + impl <K: copy, V: copy> of map<K, V> for t<K, V> { + fn size() -> uint { self.size } fn insert(k: K, v: V) -> bool { - let nchains = vec::len(tbl.chains); - let load = {num:tbl.size + 1u as int, den:nchains as int}; - if !util::rational_leq(load, lf) { - rehash(*tbl); - } - ret insert(*tbl, k, v); + let nchains = vec::len(self.chains); + let load = {num: self.size + 1u as int, den: nchains as int}; + // Structural consts would be nice. This is a const 3/4 + // load factor that we compare against. + if !util::rational_leq(load, {num:3, den:4}) { rehash(self); } + ret insert(self, k, v); } - fn contains_key(k: K) -> bool { - ret core::option::is_some(get(*tbl, k)); - } + fn contains_key(k: K) -> bool { option::is_some(get(self, k)) } - fn get(k: K) -> V { - ret core::option::get(get(*tbl, k)); - } + fn get(k: K) -> V { option::get(get(self, k)) } - fn find(k: K) -> core::option::t<V> { - ret get(*tbl, k); - } + fn find(k: K) -> option::t<V> { get(self, k) } - fn remove(k: K) -> core::option::t<V> { - ret remove(*tbl, k); - } + fn remove(k: K) -> option::t<V> { remove(self, k) } - fn rehash() { - rehash(*tbl); - } + fn items(blk: block(K, V)) { items(self, blk); } - fn items(blk: block(K, V)) { - items(*tbl, blk); - } - - fn keys(blk: block(K)) { - items(*tbl) { |k, _v| blk(k) } - } + fn keys(blk: block(K)) { items(self) { |k, _v| blk(k) } } - fn values(blk: block(V)) { - items(*tbl) { |_k, v| blk(v) } - } + fn values(blk: block(V)) { items(self) { |_k, v| blk(v) } } } - fn mk<K: copy, V: copy>(hasher: hashfn<K>, eqer: eqfn<K>) - -> hashmap<K,V> { + fn mk<K: copy, V: copy>(hasher: hashfn<K>, eqer: eqfn<K>) -> map<K,V> { let initial_capacity: uint = 32u; // 2^5 - let t = @{mutable size: 0u, - mutable chains: chains(initial_capacity), - hasher: hasher, - eqer: eqer}; - ret o(t, {num:3, den:4}); + let slf: t<K, V> = {mutable size: 0u, + mutable chains: chains(initial_capacity), + hasher: hasher, + eqer: eqer}; + slf as map::<K, V> } } @@ -365,8 +338,8 @@ hasher - The hash function for key type K eqer - The equality function for key type K */ fn mk_hashmap<K: copy, V: copy>(hasher: hashfn<K>, eqer: eqfn<K>) - -> hashmap<K, V> { - ret chained::mk(hasher, eqer); + -> map<K, V> { + chained::mk(hasher, eqer) } /* @@ -374,7 +347,7 @@ Function: new_str_hash Construct a hashmap for string keys */ -fn new_str_hash<V: copy>() -> hashmap<str, V> { +fn new_str_hash<V: copy>() -> map<str, V> { ret mk_hashmap(str::hash, str::eq); } @@ -383,7 +356,7 @@ Function: new_bytes_hash Construct a hashmap for byte string keys */ -fn new_bytes_hash<V: copy>() -> hashmap<[u8], V> { +fn new_bytes_hash<V: copy>() -> map<[u8], V> { ret mk_hashmap(vec::u8::hash, vec::u8::eq); } @@ -392,7 +365,7 @@ Function: new_int_hash Construct a hashmap for int keys */ -fn new_int_hash<V: copy>() -> hashmap<int, V> { +fn new_int_hash<V: copy>() -> map<int, V> { fn hash_int(&&x: int) -> uint { int::hash(x) } fn eq_int(&&a: int, &&b: int) -> bool { ret a == b; } ret mk_hashmap(hash_int, eq_int); @@ -403,7 +376,7 @@ Function: new_uint_hash Construct a hashmap for uint keys */ -fn new_uint_hash<V: copy>() -> hashmap<uint, V> { +fn new_uint_hash<V: copy>() -> map<uint, V> { fn hash_uint(&&x: uint) -> uint { uint::hash(x) } fn eq_uint(&&a: uint, &&b: uint) -> bool { ret a == b; } ret mk_hashmap(hash_uint, eq_uint); @@ -414,12 +387,4 @@ Function: set_add Convenience function for adding keys to a hashmap with nil type keys */ -fn set_add<K>(set: hashset<K>, key: K) -> bool { ret set.insert(key, ()); } - -// Local Variables: -// mode: rust; -// fill-column: 78; -// indent-tabs-mode: nil -// c-basic-offset: 4 -// buffer-file-coding-system: utf-8-unix -// End: +fn set_add<K>(set: set<K>, key: K) -> bool { ret set.insert(key, ()); } diff --git a/src/libstd/smallintmap.rs b/src/libstd/smallintmap.rs index d40adc84739..ca618baa554 100644 --- a/src/libstd/smallintmap.rs +++ b/src/libstd/smallintmap.rs @@ -80,3 +80,67 @@ fn max_key<T>(m: smallintmap<T>) -> uint { ret vec::len::<option::t<T>>(m.v); } +/* +Impl: map + +Implements the map::map interface for smallintmap +*/ +impl <V: copy> of map::map<uint, V> for smallintmap<V> { + fn size() -> uint { + let sz = 0u; + for item in self.v { + alt item { some(_) { sz += 1u; } _ {} } + } + sz + } + fn insert(&&key: uint, value: V) -> bool { + let exists = contains_key(self, key); + insert(self, key, value); + ret !exists; + } + fn remove(&&key: uint) -> option::t<V> { + if key >= vec::len(self.v) { ret none; } + let old = self.v[key]; + self.v[key] = none; + old + } + fn contains_key(&&key: uint) -> bool { + contains_key(self, key) + } + fn get(&&key: uint) -> V { get(self, key) } + fn find(&&key: uint) -> option::t<V> { find(self, key) } + fn rehash() { fail } + fn items(it: block(&&uint, V)) { + let idx = 0u; + for item in self.v { + alt item { + some(elt) { + it(idx, elt); + } + none. { } + } + idx += 1u; + } + } + fn keys(it: block(&&uint)) { + let idx = 0u; + for item in self.v { + if item != none { it(idx); } + idx += 1u; + } + } + fn values(it: block(V)) { + for item in self.v { + alt item { some(elt) { it(elt); } _ {} } + } + } +} + +/* +Funtion: as_map + +Cast the given smallintmap to a map::map +*/ +fn as_map<V>(s: smallintmap<V>) -> map::map<uint, V> { + s as map::map::<uint, V> +} diff --git a/src/test/stdtest/map.rs b/src/test/stdtest/map.rs index d0d5e93bf98..8762c9e6198 100644 --- a/src/test/stdtest/map.rs +++ b/src/test/stdtest/map.rs @@ -78,7 +78,7 @@ fn test_simple() { /** - * Force map growth and rehashing. + * Force map growth */ #[test] fn test_growth() { @@ -107,7 +107,6 @@ fn test_growth() { assert (hm_uu.insert(num_to_insert, 17u)); assert (hm_uu.get(num_to_insert) == 17u); #debug("-----"); - hm_uu.rehash(); i = 0u; while i < num_to_insert { #debug("get(%u) = %u", i, hm_uu.get(i)); @@ -142,7 +141,6 @@ fn test_growth() { assert (str::eq(hm_ss.get(uint::to_str(num_to_insert, 2u)), uint::to_str(17u, 2u))); #debug("-----"); - hm_ss.rehash(); i = 0u; while i < num_to_insert { #debug("get(\"%s\") = \"%s\"", @@ -200,9 +198,6 @@ fn test_removal() { i += 2u; } #debug("-----"); - #debug("rehashing"); - hm.rehash(); - #debug("-----"); i = 1u; while i < num_to_insert { #debug("get(%u) = %u", i, hm.get(i)); @@ -225,9 +220,6 @@ fn test_removal() { i += 1u; } #debug("-----"); - #debug("rehashing"); - hm.rehash(); - #debug("-----"); assert (hm.size() == num_to_insert); i = 0u; while i < num_to_insert { |