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/libstd/json.rs | 2 +- src/libstd/map.rs | 133 +++++++++++++++++----------------------------- src/libstd/smallintmap.rs | 64 ++++++++++++++++++++++ 3 files changed, 114 insertions(+), 85 deletions(-) (limited to 'src/libstd') 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:: +} -- cgit 1.4.1-3-g733a5