From 15744210e7913c6607bf033f4ffd53d36de116e6 Mon Sep 17 00:00:00 2001 From: Marijn Haverbeke Date: Mon, 9 Jan 2012 16:24:53 +0100 Subject: Implement std::map as an iface/impl instead of an obj --- src/comp/metadata/creader.rs | 14 ++- src/comp/middle/ast_map.rs | 80 +--------------- src/comp/middle/tstate/auxiliary.rs | 6 +- src/comp/middle/tstate/collect_locals.rs | 2 +- src/comp/middle/tstate/pre_post_conditions.rs | 2 +- src/libstd/json.rs | 2 +- src/libstd/map.rs | 133 ++++++++++---------------- src/libstd/smallintmap.rs | 64 +++++++++++++ src/test/stdtest/map.rs | 10 +- 9 files changed, 129 insertions(+), 184 deletions(-) (limited to 'src') 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::(), - mutable next_crate_num: 1}; + let e = @{sess: sess, + crate_cache: std::map::new_str_hash::(), + 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, - mutable next_crate_num: ast::crate_num}; +type env = @{sess: session::session, + crate_cache: hashmap, + 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; +type map = std::map::map; 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::(), + 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() -> std::map::hashmap { - 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(key_idx: fn(K) -> uint, - idx_key: fn(uint) -> K) - -> std::map::hashmap { - - obj adapter(map: smallintmap::smallintmap, - 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 { - ret smallintmap::find(map, key_idx(key)); - } - - fn remove(_key: K) -> option::t { 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::(); - 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; type norm_constraint = {bit_num: uint, c: sp_constr}; -type constr_map = @std::map::hashmap; +type constr_map = std::map::hashmap; /* 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; +type fn_info_map = std::map::hashmap; 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::()}; + ret {tcx: cx, node_anns: @mutable na, fm: new_int_hash::()}; } /* 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::(); + let res_map = new_def_hash::(); 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::(), + {constrs: new_def_hash::(), 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); + dict(map::map); /* 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 = 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 = hashmap; +type set = map; + +// Temporary alias to make migration easier +type hashmap = map; /* -Obj: hashmap +IFace: map */ -type hashmap = obj { +iface map { /* Method: size @@ -72,20 +75,14 @@ type hashmap = 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; + fn find(K) -> option::t; /* 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; - /* - Method: rehash - - Force map growth and rehashing - */ - fn rehash(); + fn remove(K) -> option::t; /* Method: items @@ -98,46 +95,44 @@ type hashmap = 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 = { + type entry = { hash: uint, key: K, mutable value: V, mutable next: chain }; - tag chain { + tag chain { present(@entry); absent; } - type t = { + type t = { mutable size: uint, mutable chains: [mutable chain], hasher: hashfn, eqer: eqfn }; - tag search_result { + tag search_result { not_found; found_first(uint, @entry); found_after(@entry, @entry); } - fn search_rem(tbl: t, - k: K, - h: uint, - idx: uint, - e_root: @entry) -> search_result { + fn search_rem( + tbl: t, k: K, h: uint, idx: uint, + e_root: @entry) -> search_result { let e0 = e_root; let comp = 1u; // for logging while true { @@ -295,62 +290,40 @@ mod chained { } } - obj o(tbl: @t, - lf: util::rational) { - fn size() -> uint { - ret tbl.size; - } + impl of map for t { + 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 { - ret get(*tbl, k); - } + fn find(k: K) -> option::t { get(self, k) } - fn remove(k: K) -> core::option::t { - ret remove(*tbl, k); - } + fn remove(k: K) -> option::t { 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(hasher: hashfn, eqer: eqfn) - -> hashmap { + fn mk(hasher: hashfn, eqer: eqfn) -> map { 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 = {mutable size: 0u, + mutable chains: chains(initial_capacity), + hasher: hasher, + eqer: eqer}; + slf as map:: } } @@ -365,8 +338,8 @@ hasher - The hash function for key type K eqer - The equality function for key type K */ fn mk_hashmap(hasher: hashfn, eqer: eqfn) - -> hashmap { - ret chained::mk(hasher, eqer); + -> map { + chained::mk(hasher, eqer) } /* @@ -374,7 +347,7 @@ Function: new_str_hash Construct a hashmap for string keys */ -fn new_str_hash() -> hashmap { +fn new_str_hash() -> map { 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() -> hashmap<[u8], V> { +fn new_bytes_hash() -> 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() -> hashmap { +fn new_int_hash() -> map { 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() -> hashmap { +fn new_uint_hash() -> map { 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(set: hashset, 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(set: set, 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(m: smallintmap) -> uint { ret vec::len::>(m.v); } +/* +Impl: map + +Implements the map::map interface for smallintmap +*/ +impl of map::map for smallintmap { + 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 { + 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 { 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(s: smallintmap) -> map::map { + s as map::map:: +} 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 { -- cgit 1.4.1-3-g733a5