--* From SMWATT%WATSON.vnet.ibm.com@yktvmv.watson.ibm.com Wed Jun 15 15:00:17 1994 --* Received: from yktvmv-ob.watson.ibm.com by asharp.watson.ibm.com (AIX 3.2/UCB 5.64/930311) --* id AA18429; Wed, 15 Jun 1994 15:00:17 -0400 --* Received: from watson.vnet.ibm.com by yktvmv.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 1079; Wed, 15 Jun 94 15:00:18 EDT --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Wed, 15 Jun 94 15:00:18 -0400 --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id 2599; Wed, 15 Jun 1994 15:00:17 EDT --* Received: from spadserv.watson.ibm.com by yktvmv.watson.ibm.com --* (IBM VM SMTP V2R3) with TCP; Wed, 15 Jun 94 15:00:16 EDT --* Received: by spadserv.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA27833; Wed, 15 Jun 1994 15:03:16 -0400 --* Date: Wed, 15 Jun 1994 15:03:16 -0400 --* From: smwatt@spadserv.watson.ibm.com (Stephen Watt) --* X-External-Networks: yes --* Message-Id: <9406151903.AA27833@spadserv.watson.ibm.com> --* To: asbugs@watson.ibm.com --* Subject: [4] of_inlin complains about a foam tag != FOAM_Values [table.as][v35.++] --@ Fixed by: PAB Sat Aug 6 11:30:44 EDT 1994 --@ Tested by: embed.as --@ Summary: embed tags #if BugHeaders LastSeenBy: PI LastUpdate: 02/Aug/94 BugKeywords: genfoam Priority: 4 Comments: Follows... Comments: SeenBy: Updates: #endif #assert modified #if modified #if 0 ------------------- REPORT This function is generating bad foam. Function: --------- generator(t: %): Generator Cross(Key, Value) == generate { for b in buckv t repeat for e in b repeat yield (e.key, e.value)@Cross(Key, Value); } Bad foam is: (look for BADFOAM) ------------ (Def (Const 32 generStepper) (Prog 0 9 NOp 0 17 0 0 0 (DDecl Params) (DDecl Locals (Decl Word "" -1 4) (Decl Clos "" -1 4) (Decl Clos "" -1 4) (Decl Clos "" -1 4) (Decl Clos "" -1 4) (Decl Clos "" -1 4) (Decl Clos "" -1 4) (Decl Clos "" -1 4) (Decl Clos "" -1 4)) (DFluid) (DEnv 4 4 15 16 4 4 4) (Seq (Select (Lex 2 2) 0 8) (Label 0) (Set (Lex 2 1) (Bool 0)) (Def (Values (Loc 1) (Loc 2) (Loc 3) (Loc 4)) (MFmt 9 (CCall NOp (CCall Clos (Lex 3 17 generator) (OCall Word (Const 41 buckv) (Env 3) (Lex 2 0 t)))))) (Def (Lex 2 5) (Loc 1)) (Def (Lex 2 6) (Loc 2)) (Def (Lex 2 7) (Loc 3)) (Goto 3) (Label 2) (Def (Values (Loc 5) (Loc 6) (Loc 7) (Loc 8)) (MFmt 9 (CCall NOp (CCall Clos (Lex 3 24 generator) (Lex 2 4 b))))) (Def (Lex 2 9) (Loc 5)) (Def (Lex 2 10) (Loc 6)) (Def (Lex 2 11) (Loc 7)) (Goto 6) (Label 5) (Set (Lex 2 2) (SInt 1)) (Set (Loc 0) ***** BADFOAM ***** (Values (RElt 10 (Lex 2 8 e) 0) (RElt 10 (Lex 2 8 e) 1))) (Goto 1) (Label 8) (Label 6) (CCall NOp (Lex 2 10)) (If (Cast Bool (CCall Word (Lex 2 9))) 7) (Set (Lex 2 8 e) (CCall Rec (Lex 2 11))) (Goto 5) (Label 7) (Label 3) (CCall NOp (Lex 2 6)) (If (Cast Bool (CCall Word (Lex 2 5))) 4) (Set (Lex 2 4 b) (CCall Word (Lex 2 7))) (Goto 2) (Label 4) (Set (Lex 2 1) (Bool 1)) (Label 1) (Set (Lex 2 3) (Loc 0)) (Return (Values))))) #endif #include "aslib" Hash ==> SingleInteger; +++ `HashTable(Key, Val)' provides a parameterized hash-table data type. HashTable(Key: BasicType, Value: BasicType): BasicType with { table: () -> %; ++ `table()' creates a new table using the equality test `=' ++ and the hash function `hash' from the `Key' type. eqtable: () -> %; ++ `eqtable()' creates a new table using instance equality. table: ((Key, Key) -> Boolean, Key->Hash) -> %; ++ `table(=, hash)' creates a new hash table using the ++ equality test `=' and the hash function `hash'. copy: % -> %; ++ `copy t' creates a copy of the table `t'. #: % -> SingleInteger; ++ `#t' returns the number of elements in `t'. search: (%, Key, Value) -> (Boolean, Value); ++ `(b,v) := search(t,k,d)' searches table `t' for the value ++ associated with key `k'. If there is such a value, `vk', ++ then `b' is set to `true' and `v' is set to `vk'. ++ Otherwise `b' is `false' and `v' is set to `d'. apply: (%, Key) -> Value; ++ `t.k' searches the table `t' for the value associated with ++ the key `k'. It is an error if there is no value for `k'. set!: (%, Key, Value) -> Value; ++ `t.k := val' associates `val' with `k' in `t'. drop!: (%, Key) -> Value; ++ `drop!(t, k)' removes the entry for `k' in `t'. dispose!: % -> (); ++ `dispose! t' indicates a table will no longer be used. generator: % -> Generator Cross(Key, Value); ++ `generator t' is a generator which produces all the ++ `(key, value)' pairs from `t'. } == add { -- Parameters to tune table performance. InitBuckC ==> primes.3; MaxLoad ==> 5.0; MinLoad ==> 0.5; -- primes.i is the largest prime <= 2^i. local primes: Array SingleInteger == [ 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: SingleInteger): SingleInteger == { p := 1; for i in 0.. repeat { if n <= p then return i; p := p + p; } never } -- Representation Entry ==> Record(key: Key, value: Value, hash: Hash); Rep ==> Record(isEq?: Boolean, equal: (Key, Key) -> Boolean, hash: (Key) -> Hash, count: SingleInteger, buckv: Array List Entry); -- Local representation operaitons import from Rep; local new(isEq?: Boolean, e: (Key,Key)->Boolean, h: Key->Hash): % == per [isEq?, e, h, 0, new(InitBuckC, nil)]; local isEq? (t: %): Boolean == rep(t).isEq?; local hash (t: %): (Key) -> Hash == rep(t).hash; local equal (t: %): (Key,Key) -> Boolean == rep(t).equal; local buckv (t: %): Array List Entry == rep(t).buckv; local buckc (t: %): SingleInteger == #rep(t).buckv; local inc!(t: %): () == { import from SingleFloat; rep(t).count := rep(t).count + 1; if #t::SingleFloat/buckc(t)::SingleFloat > MaxLoad then enlarge! t; } local dec!(t: %): () == { import from SingleFloat; rep(t).count := rep(t).count - 1; if #t::SingleFloat/buckc(t)::SingleFloat < MinLoad then shrink! t; } local peq(k1: Key, k2: Key): Boolean == { import from Pointer; k1 pretend Pointer = k2 pretend Pointer } local phash(k1: Key): Hash == { k1 pretend Pointer pretend Hash } -- Find the chain for k, moving the link to the front on success. local findChain(t: %, k: Key): SingleInteger == { h := hash(t)(k); n := h mod buckc(t) + 1; b := buckv(t).n; p := nil; -- Previous link or nil. while b repeat { e := first b; if h = e.hash then { if isEq? t or equal(t)(e.key, k) then { -- Move to front if p then { p.rest := b.rest; b.rest := buckv(t).n; buckv(t).n := b; } return n; } } p := b; b := rest b; } return 0; } -- Resize the table, larger or smaller. local enlarge!(t: %): % == resize!(t, lg buckc(t) + 1); local shrink! (t: %): % == resize!(t, lg buckc(t) - 1); local resize!(t: %, sizeix: SingleInteger): % == { sizeix < 1 or sizeix > #primes => t; nbuckc := primes sizeix; nbuckv := new(nbuckc, nil); for b0 in buckv t repeat { b := b0; while b repeat { hd := b; b := b.rest; n := (hd.first.hash mod nbuckc) + 1; hd.rest := nbuckv.n; nbuckv.n := b0; } } dispose! rep(t).buckv; rep(t).buckv := nbuckv; t; } -- Exported operations sample: % == table(); (t1: %) = (t2: %): Boolean == { import from Pointer; t1 pretend Pointer = t2 pretend Pointer } (out: OutPort) << (t: %): OutPort == { out << "table("; any? := false; for b in buckv(t) repeat for e in b repeat { if any? then out << ", " else any? := true; out << e.key << " = " << e.value; } out << ")" } #(t: %): SingleInteger == rep(t).count; eqtable(): % == new(true, peq, phash); table(): % == new(false, =$Key, hash$Key); table(eq:(Key,Key)->Boolean, hash:Key->Hash): % == new(false,eq,hash); copy(t: %): % == per [isEq? t, equal t, hash t, #t, [[[e.key, e.value, e.hash] for e in b] for b in buckv t]]; search(t: %, k: Key, def: Value): (Boolean, Value) == { n := findChain(t, k); if n = 0 then (false, def) else (true, buckv(t).n.first.value) } apply(t: %, k: Key) : Value == { n := findChain(t, k); n = 0 => error0 "Element missing from table."; buckv(t).n.first.value; } set!(t: %, k: Key, v: Value) : Value == { n := findChain(t, k); n > 0 => buckv(t).n.first.value := v; h := hash(t)(k); n := (h mod buckc(t)) + 1; buckv(t).n := cons([k,v,h], buckv(t).n); inc! t; v; } drop!(t: %, k: Key): Value == { n := findChain(t, k); n = 0 => error0 "Element missing from table."; e := buckv(t).n.first; v := e.value; buckv(t).n := disposeHead! buckv(t).n; -- Dispose of the link. dispose! e; -- Dispose of the record. dec! t; v; } dispose!(t: %): () == { for b in buckv(t) repeat dispose! b; dispose! buckv(t); dispose! rep(t); } generator(t: %): Generator Cross(Key, Value) == generate { for b in buckv t repeat for e in b repeat yield (e.key, e.value)@Cross(Key, Value); } } #else -- original begin #include "aslib" Hash ==> SingleInteger; +++ `HashTable(Key, Val)' provides a parameterized hash-table data type. HashTable(Key: BasicType, Value: BasicType): BasicType with { table: () -> %; ++ `table()' creates a new table using the equality test `=' ++ and the hash function `hash' from the `Key' type. eqtable: () -> %; ++ `eqtable()' creates a new table using instance equality. table: ((Key, Key) -> Boolean, Key->Hash) -> %; ++ `table(=, hash)' creates a new hash table using the ++ equality test `=' and the hash function `hash'. copy: % -> %; ++ `copy t' creates a copy of the table `t'. #: % -> SingleInteger; ++ `#t' returns the number of elements in `t'. search: (%, Key, Value) -> (Boolean, Value); ++ `(b,v) := search(t,k,d)' searches table `t' for the value ++ associated with key `k'. If there is such a value, `vk', ++ then `b' is set to `true' and `v' is set to `vk'. ++ Otherwise `b' is `false' and `v' is set to `d'. apply: (%, Key) -> Value; ++ `t.k' searches the table `t' for the value associated with ++ the key `k'. It is an error if there is no value for `k'. set!: (%, Key, Value) -> Value; ++ `t.k := val' associates `val' with `k' in `t'. drop!: (%, Key) -> Value; ++ `drop!(t, k)' removes the entry for `k' in `t'. dispose!: % -> (); ++ `dispose! t' indicates a table will no longer be used. generator: % -> Generator Cross(Key, Value); ++ `generator t' is a generator which produces all the ++ `(key, value)' pairs from `t'. } == add { -- Parameters to tune table performance. InitBuckC ==> primes.3; MaxLoad ==> 5.0; MinLoad ==> 0.5; -- primes.i is the largest prime <= 2^i. local primes: Array SingleInteger == [ 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: SingleInteger): SingleInteger == { p := 1; for i in 0.. repeat { if n <= p then return i; p := p + p; } never } -- Representation Entry ==> Record(key: Key, value: Value, hash: Hash); Rep ==> Record(isEq?: Boolean, equal: (Key, Key) -> Boolean, hash: (Key) -> Hash, count: SingleInteger, buckv: Array List Entry); -- Local representation operaitons import from Rep; local new(isEq?: Boolean, e: (Key,Key)->Boolean, h: Key->Hash): % == per [isEq?, e, h, 0, new(InitBuckC, nil)]; local isEq? (t: %): Boolean == rep(t).isEq?; local hash (t: %): (Key) -> Hash == rep(t).hash; local equal (t: %): (Key,Key) -> Boolean == rep(t).equal; local buckv (t: %): Array List Entry == rep(t).buckv; local buckc (t: %): SingleInteger == #rep(t).buckv; local inc!(t: %): () == { import from SingleFloat; rep(t).count := rep(t).count + 1; if #t::SingleFloat/buckc(t)::SingleFloat > MaxLoad then enlarge! t; } local dec!(t: %): () == { import from SingleFloat; rep(t).count := rep(t).count - 1; if #t::SingleFloat/buckc(t)::SingleFloat < MinLoad then shrink! t; } local peq(k1: Key, k2: Key): Boolean == { import from Pointer; k1 pretend Pointer = k2 pretend Pointer } local phash(k1: Key): Hash == { k1 pretend Pointer pretend Hash } -- Find the chain for k, moving the link to the front on success. local findChain(t: %, k: Key): SingleInteger == { h := hash(t)(k); n := h mod buckc(t) + 1; b := buckv(t).n; p := nil; -- Previous link or nil. while b repeat { e := first b; if h = e.hash then { if isEq? t or equal(t)(e.key, k) then { -- Move to front if p then { p.rest := b.rest; b.rest := buckv(t).n; buckv(t).n := b; } return n; } } p := b; b := rest b; } return 0; } -- Resize the table, larger or smaller. local enlarge!(t: %): % == resize!(t, lg buckc(t) + 1); local shrink! (t: %): % == resize!(t, lg buckc(t) - 1); local resize!(t: %, sizeix: SingleInteger): % == { sizeix < 1 or sizeix > #primes => t; nbuckc := primes sizeix; nbuckv := new(nbuckc, nil); for b0 in buckv t repeat { b := b0; while b repeat { hd := b; b := b.rest; n := (hd.first.hash mod nbuckc) + 1; hd.rest := nbuckv.n; nbuckv.n := b0; } } dispose! rep(t).buckv; rep(t).buckv := nbuckv; t; } -- Exported operations sample: % == table(); (t1: %) = (t2: %): Boolean == { import from Pointer; t1 pretend Pointer = t2 pretend Pointer } (out: OutPort) << (t: %): OutPort == { out << "table("; any? := false; for b in buckv(t) repeat for e in b repeat { if any? then out << ", " else any? := true; out << e.key << " = " << e.value; } out << ")" } #(t: %): SingleInteger == rep(t).count; eqtable(): % == new(true, peq, phash); table(): % == new(false, =$Key, hash$Key); table(eq:(Key,Key)->Boolean, hash:Key->Hash): % == new(false,eq,hash); copy(t: %): % == per [isEq? t, equal t, hash t, #t, [[[e.key, e.value, e.hash] for e in b] for b in buckv t]]; search(t: %, k: Key, def: Value): (Boolean, Value) == { n := findChain(t, k); if n = 0 then (false, def) else (true, buckv(t).n.first.value) } apply(t: %, k: Key) : Value == { n := findChain(t, k); n = 0 => error0 "Element missing from table."; buckv(t).n.first.value; } set!(t: %, k: Key, v: Value) : Value == { n := findChain(t, k); n > 0 => buckv(t).n.first.value := v; h := hash(t)(k); n := (h mod buckc(t)) + 1; buckv(t).n := cons([k,v,h], buckv(t).n); inc! t; v; } drop!(t: %, k: Key): Value == { n := findChain(t, k); n = 0 => error0 "Element missing from table."; e := buckv(t).n.first; v := e.value; buckv(t).n := disposeHead! buckv(t).n; -- Dispose of the link. dispose! e; -- Dispose of the record. dec! t; v; } dispose!(t: %): () == { for b in buckv(t) repeat dispose! b; dispose! buckv(t); dispose! rep(t); } generator(t: %): Generator Cross(Key, Value) == generate { for b in buckv t repeat for e in b repeat yield (e.key, e.value)@Cross(Key, Value); } } #endif -- original end