-- SymTabImpl.mesa - implementation of symbol table abstraction
-- Russ Atkinson, October 19, 1982 5:21 pm

DIRECTORY
Inline USING [LowHalf],
Rope USING [Equal, ROPE],
RopeInline USING [InlineFetch, InlineSize, Lower],
SafeStorage USING [NewZone],
SymTab USING [EachPairAction, Key, Val];

SymTabImpl: CEDAR MONITOR LOCKS x USING x: Ref
IMPORTS Inline, Rope, RopeInline, SafeStorage
EXPORTS SymTab
= BEGIN OPEN Rope, SymTab;

Ref: TYPE = REF SymTabRep;
SymTabRep: PUBLIC TYPE =
MONITORED RECORD [mod,size: CARDINAL, case: BOOL, data: REF Array];
NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node];
Node: TYPE = REF NodeRep;

Array: TYPE = RECORD[nodes: SEQUENCE max: CARDINAL OF Node];

pz: ZONE ← SafeStorage.NewZone[prefixed];

-- Private Operations

Hash: PROC [s: ROPE, mod: CARDINAL] RETURNS [CARDINAL] = TRUSTED {
size: INT ← RopeInline.InlineSize[s];
IF size = 0 THEN RETURN [0];
{c0: CARDINAL = RopeInline.Lower[RopeInline.InlineFetch[s, 0]] - 0C;
c1: CARDINAL = RopeInline.Lower[RopeInline.InlineFetch[s, size-1]] - 0C;
RETURN [(Inline.LowHalf[size] + c0 + c1) MOD mod]};
};

-- public operations

Create: PUBLIC PROC [mod: CARDINAL ← 17, case: BOOL ← TRUE] 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
index: CARDINAL ← 0;
data: REF Array ← NIL;
IF mod < 1 THEN mod ← 1;
IF mod > 4095 THEN mod ← 4095;
data ← pz.NEW[Array[mod]];
RETURN[pz.NEW[SymTabRep ← [mod: mod, size: 0, case: case, data: data]]];
};

GetSize: PUBLIC PROC [x: Ref] RETURNS [CARDINAL] =
-- returns number of key-value pairs in table
{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 is TRUE, val is value associated with given key
-- if found is FALSE, val is NIL
ENABLE UNWIND => NULL;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
case: BOOL ← x.case;
WHILE node # NIL DO
nkey: Key ← node.key;
IF Rope.Equal[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;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
head: Node ← node;
case: BOOL ← x.case;
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] ← pz.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;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
head: Node ← node;
case: BOOL ← x.case;
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] ← pz.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;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
head: Node ← node;
case: BOOL ← x.case;
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;
};

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.