--* From SMWATT%WATSON.vnet.ibm.com@yktvmh.watson.ibm.com Thu Jun 2 00:02:11 1994 --* Received: from yktvmh.watson.ibm.com by asharp.watson.ibm.com (AIX 3.2/UCB 5.64/930311) --* id AA19122; Thu, 2 Jun 1994 00:02:11 -0400 --* Received: from watson.vnet.ibm.com by yktvmh.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 5873; Thu, 02 Jun 94 00:02:16 EDT --* Received: from YKTVMH by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Thu, 02 Jun 94 00:02:14 -0400 --* Received: from YKTVMH by watson.vnet.ibm.com with "VAGENT.V1.0" --* id 3464; Thu, 2 Jun 1994 00:00:12 EDT --* Received: from spadserv.watson.ibm.com by yktvmh.watson.ibm.com --* (IBM VM SMTP V2R3) with TCP; Thu, 02 Jun 94 00:00:10 EDT --* Received: by spadserv.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA20985; Thu, 2 Jun 1994 00:02:39 -0400 --* Date: Thu, 2 Jun 1994 00:02:39 -0400 --* From: smwatt@spadserv.watson.ibm.com (Stephen Watt) --* X-External-Networks: yes --* Message-Id: <9406020402.AA20985@spadserv.watson.ibm.com> --* To: asbugs@watson.ibm.com --* Subject: [3] export not found -- asharp -L. -Fx foo.as table.aso ; foo [bug.as][rs3.2-stable] --@ Fixed by: PAB Tue Aug 2 15:48:58 EDT 1994 --@ Tested by: object0.as --@ Summary: implemented explode #if BugHeaders LastSeenBy: PAB LastUpdate: 02/Jun/94 BugKeywords: hashcode special op Records Priority: 3 Comments: Explode should be implemented as a special op, but isn't Comments: Fix is to add the special op SeenBy: PAB Updates: #endif #assert modified #if modified -------------------------------- table.as ------------------------------------- -- -- Hash tables -- ------------------------------------------------------------------------------- #include "aslib" Hash ==> SingleInteger; SInt ==> SingleInteger; TblInitBuckC ==> primes.3; TblMaxLoad ==> 5; -- -- Primes used for the number of buckets. -- import from SInt; local primes: Array SInt == [ 1, 2, 3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 1073741789, 2147483647, 4294967291 ]; local lg(n: SInt): SInt == { p := 1; i := 0; while p < n repeat { p := p + p; i := i + 1; } i } +++ Table(Key, Val) provides a parameterized hash-table data type. Table(Key: BasicType, Val: BasicType) : BasicType with { table: () -> %; ++ `table()' creates a new hash table. ++ The equality test is `=$Key', and the hash function ++ is `hash$Key', if Key exports one. table: (Key -> Hash, (Key,Key) -> Boolean) -> %; ++ `table(hash, equal)' creates a new hash table, ++ with a specified hash function and equality test, ++ such that if `equal(k1,k2)' then `hash k1 = hash k2'. copy: % -> %; ++ `copy t' creates a copy of the table `t'. #: % -> SInt; ++ `#t' returns the number of entries in `t'. search: (%, Key, Val) -> (Val, Boolean); ++ `(v,there?) := search(t,k,d)' ++ looks for the value associated with `k' in `t'. ++ The first return value, `v', is the value found, or `d' ++ if none was present. ++ The second return value is true when a value was found, ++ and false when `d' was returned. apply: (%, Key) -> Val; ++ `t.k' returns the value associated with `k' in `t'. ++ If no value is found, then an error occurs. set!: (%, Key, Val) -> Val; ++ `t.k := v' associates `v' with `k' in `t'. drop!: (%, Key) -> %; ++ `drop!(t, k)' removes the entry for `k' in `t'. generator: % -> Generator Record(keyx: Key, valx: Val); ++ `generator t' gives a generator which produces a key-value ++ pair for each entry in `t'. } == add { Slot ==> Record(key: Key, val: Val, hash: Hash); Rep ==> Record (hashfn: Key -> Hash, equal: (Key, Key) -> Boolean, count: SInt, buckv: Array List Slot); import from Slot; import from Rep; import from (Key, Key)->Boolean; import from Record(keyx: Key, valx: Val); hash (t: %): Key -> Hash == rep(t).hashfn; equal (t: %): (Key,Key)-> Boolean == rep(t).equal; buckv (t: %): Array List Slot == rep(t).buckv; buckc (t: %): SInt == # rep(t).buckv; # (t: %): SInt == rep(t).count; (m1: (Key, Key)-> Boolean) ~= (m2: (Key, Key)->Boolean): Boolean == { import from Pointer; (m1 pretend Pointer) ~= (m2 pretend Pointer) } if Key has with {hash: Key -> Hash} then { hashKey := hash } else { hashKey := (k: Key): Hash +-> 0 } table(): % == table(hashKey, =$Key); table(h: Key -> Hash, e:(Key,Key) -> Boolean): % == per [h, e, 0, new(TblInitBuckC, nil)]; (t1: %) = (t2: %): Boolean == { #t1 ~= #t2 => false; hash t1 ~= hash t2 => false; equal t1 ~= equal t2 => false; for k1v1 in t1 repeat { (k1, v1) := explode k1v1; (v2, there?) := search(t2, k1, v1); if not there? or v1 ~= v2 then return false; } return true; } apply(t: %, k: Key): Val == { (v, there?) := search(t, k, sample); if not there? then error "No value for key in the table"; v } sample: % == table(); apply(p: OutPort, t: %): OutPort == { #t = 1 => p "table()"; p "table("; rest := false; for kv in t repeat { (k,v) := explode kv; if rest then {p ", "; rest := true} p("(")(k)(",")(v)(")"); } p ")" } copy(t: %): % == per [ hash t, equal t, #t, [[[s.key, s.val, s.hash] for s in b] for b in rep(t).buckv] ]; lookie(t: %, x: SInt, b: List Slot, h: Hash, k: Key): List Slot == { empty? b => b; p := nil; e := equal t; while b repeat { b0 := first b; if b0.hash = h then { if e(k, b0.key) then { if p then { -- Move to front setRest!(p, rest b); setRest!(b, buckv(t).x); buckv(t).x := b; } return buckv(t).x; } } p := b; b := rest b; } return nil; } search(t: %, key: Key, def: Val): (Val, Boolean) == { h := hash(t)(key); x := h mod buckc(t) + 1; b := buckv(t).x; if b := lookie(t,x,b,h,key) then return (first(b).val, true); else return (def, false); } set!(t: %, key: Key, value: Val): Val == { h := hash(t)(key); x := h mod buckc(t) + 1; b := buckv(t).x; if b := lookie(t,x,b,h,key) then return (first(b).val := value); buckv(t).x := cons([key,value,h], buckv(t).x); rep(t).count := rep(t).count + 1; if #t > TblMaxLoad * buckc t then enlarge! t; value } drop!(t: %, key: Key): % == { h := (hash t)(key); x := h mod buckc(t) + 1; b := buckv(t).x; if b ~= nil and lookie(t, x, b, h, key) then { buckv(t).x := rest buckv(t).x; rep(t).count := rep(t).count - 1; } t } enlarge!(t: %) : % == { nbuckc := primes(lg(buckc t) + 1); nbuckv := new(nbuckc, nil); for buck in buckv t repeat { b := buck; while b repeat { hd := b; b := rest b; x := first(hd).hash mod nbuckc + 1; setRest!(hd, nbuckv.x); nbuckv.x := hd; } } rep(t).buckv := nbuckv; t } generator(t: %): Generator Record(keyx: Key, valx: Val) == generate for b in buckv t repeat for s in b repeat yield [s.key, s.val]; } --------------------------------- foo.as --------------------------------- import from SingleInteger; trivhash(n: SingleInteger): SingleInteger == n; t: Table(SingleInteger, SingleInteger) := table(trivhash, =); for i in 1..100 repeat t.(i^2 + 1) := i; print t #else -------------------------------- table.as ------------------------------------- -- -- Hash tables -- ------------------------------------------------------------------------------- #include "aslib" Hash ==> SingleInteger; SInt ==> SingleInteger; TblInitBuckC ==> primes.3; TblMaxLoad ==> 5; -- -- Primes used for the number of buckets. -- import from SInt; local primes: Array SInt == [ 1, 2, 3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 1073741789, 2147483647, 4294967291 ]; local lg(n: SInt): SInt == { p := 1; i := 0; while p < n repeat { p := p + p; i := i + 1; } i } +++ Table(Key, Val) provides a parameterized hash-table data type. Table(Key: BasicType, Val: BasicType) : BasicType with { table: () -> %; ++ `table()' creates a new hash table. ++ The equality test is `=$Key', and the hash function ++ is `hash$Key', if Key exports one. table: (Key -> Hash, (Key,Key) -> Boolean) -> %; ++ `table(hash, equal)' creates a new hash table, ++ with a specified hash function and equality test, ++ such that if `equal(k1,k2)' then `hash k1 = hash k2'. copy: % -> %; ++ `copy t' creates a copy of the table `t'. #: % -> SInt; ++ `#t' returns the number of entries in `t'. search: (%, Key, Val) -> (Val, Boolean); ++ `(v,there?) := search(t,k,d)' ++ looks for the value associated with `k' in `t'. ++ The first return value, `v', is the value found, or `d' ++ if none was present. ++ The second return value is true when a value was found, ++ and false when `d' was returned. apply: (%, Key) -> Val; ++ `t.k' returns the value associated with `k' in `t'. ++ If no value is found, then an error occurs. set!: (%, Key, Val) -> Val; ++ `t.k := v' associates `v' with `k' in `t'. drop!: (%, Key) -> %; ++ `drop!(t, k)' removes the entry for `k' in `t'. generator: % -> Generator Record(keyx: Key, valx: Val); ++ `generator t' gives a generator which produces a key-value ++ pair for each entry in `t'. } == add { Slot ==> Record(key: Key, val: Val, hash: Hash); Rep ==> Record (hashfn: Key -> Hash, equal: (Key, Key) -> Boolean, count: SInt, buckv: Array List Slot); import from Slot; import from Rep; import from (Key, Key)->Boolean; import from Record(keyx: Key, valx: Val); hash (t: %): Key -> Hash == rep(t).hashfn; equal (t: %): (Key,Key)-> Boolean == rep(t).equal; buckv (t: %): Array List Slot == rep(t).buckv; buckc (t: %): SInt == # rep(t).buckv; # (t: %): SInt == rep(t).count; (m1: (Key, Key)-> Boolean) ~= (m2: (Key, Key)->Boolean): Boolean == { import from Pointer; (m1 pretend Pointer) ~= (m2 pretend Pointer) } if Key has with {hash: Key -> Hash} then { hashKey := hash } else { hashKey := (k: Key): Hash +-> 0 } table(): % == table(hashKey, =$Key); table(h: Key -> Hash, e:(Key,Key) -> Boolean): % == per [h, e, 0, new(TblInitBuckC, nil)]; (t1: %) = (t2: %): Boolean == { #t1 ~= #t2 => false; hash t1 ~= hash t2 => false; equal t1 ~= equal t2 => false; for k1v1 in t1 repeat { (k1, v1) := explode k1v1; (v2, there?) := search(t2, k1, v1); if not there? or v1 ~= v2 then return false; } return true; } apply(t: %, k: Key): Val == { (v, there?) := search(t, k, sample); if not there? then error "No value for key in the table"; v } sample: % == table(); apply(p: OutPort, t: %): OutPort == { #t = 1 => p "table()"; p "table("; rest := false; for kv in t repeat { (k,v) := explode kv; if rest then {p ", "; rest := true} p("(")(k)(",")(v)(")"); } p ")" } copy(t: %): % == per [ hash t, equal t, #t, [[[s.key, s.val, s.hash] for s in b] for b in rep(t).buckv] ]; lookie(t: %, x: SInt, b: List Slot, h: Hash, k: Key): List Slot == { empty? b => b; p := nil; e := equal t; while b repeat { b0 := first b; if b0.hash = h then { if e(k, b0.key) then { if p then { -- Move to front setRest!(p, rest b); setRest!(b, buckv(t).x); buckv(t).x := b; } return buckv(t).x; } } p := b; b := rest b; } return nil; } search(t: %, key: Key, def: Val): (Val, Boolean) == { h := hash(t)(key); x := h mod buckc(t) + 1; b := buckv(t).x; if b := lookie(t,x,b,h,key) then return (first(b).val, true); else return (def, false); } set!(t: %, key: Key, value: Val): Val == { h := hash(t)(key); x := h mod buckc(t) + 1; b := buckv(t).x; if b := lookie(t,x,b,h,key) then return (first(b).val := value); buckv(t).x := cons([key,value,h], buckv(t).x); rep(t).count := rep(t).count + 1; if #t > TblMaxLoad * buckc t then enlarge! t; value } drop!(t: %, key: Key): % == { h := (hash t)(key); x := h mod buckc(t) + 1; b := buckv(t).x; if b ~= nil and lookie(t, x, b, h, key) then { buckv(t).x := rest buckv(t).x; rep(t).count := rep(t).count - 1; } t } enlarge!(t: %) : % == { nbuckc := primes(lg(buckc t) + 1); nbuckv := new(nbuckc, nil); for buck in buckv t repeat { b := buck; while b repeat { hd := b; b := rest b; x := first(hd).hash mod nbuckc + 1; setRest!(hd, nbuckv.x); nbuckv.x := hd; } } rep(t).buckv := nbuckv; t } generator(t: %): Generator Record(keyx: Key, valx: Val) == generate for b in buckv t repeat for s in b repeat yield [s.key, s.val]; } --------------------------------- foo.as --------------------------------- #include "aslib" #library TableLib "table.aso" import from TableLib; import from SingleInteger; trivhash(n: SingleInteger): SingleInteger == n; t: Table(SingleInteger, SingleInteger) := table(trivhash, =); for i in 1..100 repeat t.(i^2 + 1) := i; print t #endif