DIRECTORY SymTab USING [EachPairAction, Key, Node, NodeRep, Ref, Seq, SeqIndex, SymTabRep, TextKey, Val], Rope USING [Equal], RopeHash USING [FromRefText, FromRope]; SymTabImpl: CEDAR MONITOR LOCKS x USING x: Ref IMPORTS Rope, RopeHash EXPORTS SymTab SHARES Rope = BEGIN OPEN Rope, SymTab; Create: PUBLIC PROC [mod: SeqIndex, case: BOOL] RETURNS [Ref] = { SELECT mod FROM < 7 => mod _ 7; ENDCASE; RETURN[NEW[SymTabRep _ [mod: mod, size: 0, case: case, data: NEW[Seq[mod]]]]]; }; GetSize: PUBLIC ENTRY PROC [x: Ref] RETURNS [INT] = { ENABLE UNWIND => NULL; RETURN [x.size]; }; Fetch: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = { ENABLE UNWIND => NULL; case: BOOL _ x.case; node: Node _ x.data[RopeHash.FromRope[key, case] MOD x.mod]; WHILE node # NIL DO IF Rope.Equal[key, node.key, case] THEN RETURN [TRUE, node.val]; node _ node.next; ENDLOOP; RETURN [FALSE, NIL]; }; FetchText: PUBLIC ENTRY PROC [x: Ref, key: TextKey] RETURNS [found: BOOL, val: Val] = TRUSTED { ENABLE UNWIND => NULL; case: BOOL _ x.case; hash: CARDINAL _ (IF case THEN RopeHash.FromRefText[key] ELSE RopeHash.FromRope[LOOPHOLE[key, Key], case]) MOD x.mod; node: Node _ x.data[hash MOD x.mod]; WHILE node # NIL DO IF Rope.Equal[LOOPHOLE[key, Key], node.key, case] THEN RETURN [TRUE, node.val]; node _ node.next; ENDLOOP; RETURN [FALSE, NIL]; }; Store: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = { ENABLE UNWIND => NULL; case: BOOL _ x.case; hash: CARDINAL _ RopeHash.FromRope[key, case] MOD x.mod; node: Node _ x.data[hash]; head: Node _ node; WHILE node # NIL DO nkey: Key _ node.key; IF Rope.Equal[key, node.key, case] THEN {node.val _ val; RETURN [FALSE]}; node _ node.next; ENDLOOP; x.data[hash] _ NEW[NodeRep _ [key: key, val: val, next: head]]; x.size _ x.size + 1; RETURN [TRUE]; }; Insert: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = { ENABLE UNWIND => NULL; case: BOOL _ x.case; hash: CARDINAL _ RopeHash.FromRope[key, case] MOD x.mod; node: Node _ x.data[hash]; head: Node _ node; WHILE node # NIL DO nkey: Key _ node.key; IF Rope.Equal[key, node.key, case] THEN RETURN [FALSE]; node _ node.next; ENDLOOP; x.data[hash] _ NEW[NodeRep _ [key: key, val: val, next: head]]; x.size _ x.size + 1; RETURN [TRUE]; }; Delete: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [BOOL] = { ENABLE UNWIND => NULL; case: BOOL _ x.case; hash: CARDINAL _ RopeHash.FromRope[key, case] MOD x.mod; node: Node _ x.data[hash]; head: Node _ node; lag: Node _ NIL; WHILE node # NIL DO nkey: Key _ node.key; IF Rope.Equal[key, node.key, case] THEN { IF lag = NIL THEN x.data[hash] _ node.next ELSE lag.next _ node.next; x.size _ x.size - 1; RETURN [TRUE]}; lag _ node; node _ node.next; ENDLOOP; RETURN [FALSE]; }; Pairs: PUBLIC PROC [x: Ref, action: EachPairAction] RETURNS [quit: BOOL] = { node: Node _ NIL; index: CARDINAL _ 0; DO [node, index] _ GetNext[x, node, index]; IF node = NIL THEN RETURN [FALSE]; IF action[node.key, node.val] THEN RETURN [TRUE]; ENDLOOP; }; GetNext: ENTRY PROC [x: Ref, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = { ENABLE UNWIND => NULL; mod: CARDINAL _ x.mod; IF node # NIL THEN { node _ node.next; IF node # NIL THEN RETURN [node, index]; index _ index + 1} ELSE index _ 0; WHILE index < mod DO node _ x.data[index]; IF node = NIL THEN {index _ index + 1; LOOP}; RETURN [node, index]; ENDLOOP; RETURN [NIL, mod]; }; END. SymTabImpl.mesa - implementation of symbol table abstraction Copyright c 1985 by Xerox Corporation. All rights reserved. Russ Atkinson, March 25, 1985 3:13:35 pm PST Paul Rovner, August 9, 1983 5:25 pm Public operations ... creates new table with suggested hash size; if case is TRUE, keys are compared exactly; if case is FALSE, case is ignored in comparing keys ... returns number of key-value pairs in table ... looks up key in table, returns associated value (if any); if found = TRUE, val = value associated with given key; if found = FALSE, val = NIL ... looks up key in table, returns associated value (if any); if found = TRUE, val = value associated with given key; if found = FALSE, val = NIL; the key MUST NOT BE ALTERED during a call of this procedure ... stores new key-value pair, overwriting previous value for given key; returns TRUE if new value, FALSE if previous value overwritten ... inserts new key-value pair, except if previous value for given key; returns TRUE if inserted, FALSE if previous value for key ... deletes key-value pair associated with given key; returns TRUE if deletion actually occurred, FALSE if no such key ... enumerates pairs currently in symbol table in unspecified order; pairs inserted/deleted during enumeration may or may not be seen; applies action to each pair until action returns TRUE or no more pairs; returns TRUE if some action returns TRUE Private Operations Κ{˜codešœ<™žœ žœ™vKšžœžœžœ˜Kšœžœ ˜Kšœžœ žœ˜8K˜K˜Kšœ žœ˜šžœžœž˜K˜šžœ žœ˜)šžœž˜ Kšžœ˜Kšžœ˜—K˜Kšžœžœ˜—K˜ K˜Kšžœ˜—Kšžœžœ˜K˜K˜—š Ÿœžœžœ"žœžœ˜LKšœΈžœžœž™χKšœ žœ˜Kšœžœ˜šž˜K˜(Kš žœžœžœžœžœ˜"Kšžœžœžœžœ˜1Kšžœ˜—K˜K˜——šœ™K˜š Ÿœžœžœžœžœžœ˜VKšžœžœžœ˜Kšœžœ ˜šžœžœžœ˜K˜Kšžœžœžœžœ˜(K˜Kšžœ ˜—šžœ ž˜K˜Kšžœžœžœžœ˜-Kšžœ˜Kšžœ˜—Kšžœžœ˜K˜K˜—Kšžœ˜K˜K˜——…— LW