SymTabImpl.mesa - implementation of symbol table abstraction
Copyright © 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
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;
Public operations
Create: PUBLIC PROC [mod: SeqIndex, case: BOOL] RETURNS [Ref] = {
... 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
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] = {
... returns number of key-value pairs in table
ENABLE UNWIND => NULL;
RETURN [x.size];
};
Fetch: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = {
... looks up key in table, returns associated value (if any); if found = TRUE, val = value associated with given key; if found = FALSE, val = NIL
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 {
... 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
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] = {
... stores new key-value pair, overwriting previous value for given key; returns TRUE if new value, FALSE if previous value overwritten
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] = {
... inserts new key-value pair, except if previous value for given key; returns TRUE if inserted, FALSE if previous value for key
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] = {
... deletes key-value pair associated with given key; returns TRUE if deletion actually occurred, FALSE if no such key
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] = {
... 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
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;
};
Private Operations
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.