-- RefTabImpl.Mesa - implementation of REF table abstraction
-- last change: Bill Paxton - August 19, 1982 9:25 am
-- last change: Warren Teitelman - September 8, 1982 9:12 pm
-- last change: Paul Rovner - August 9, 1983 5:26 pm

DIRECTORY
Basics USING [LongNumber],
RefTab USING [EachPairAction, Key, Val]
;

RefTabImpl: CEDAR MONITOR LOCKS x USING x: Ref
EXPORTS RefTab
= BEGIN

Int: TYPE = LONG INTEGER;
Ref: TYPE = REF RefTabRep;
RefTabRep: PUBLIC TYPE =
MONITORED RECORD [mod,size: CARDINAL, data: REF Array];
NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node];
Node: TYPE = REF NodeRep;
Key: TYPE = RefTab.Key;
Val: TYPE = RefTab.Val;
EachPairAction: TYPE = RefTab.EachPairAction;

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

-- Private Operations

Hash: PROCEDURE [key: Key, mod: CARDINAL] RETURNS [CARDINAL] = INLINE BEGIN
RETURN [(LOOPHOLE[key, Basics.LongNumber].lowbits/4) MOD mod];
END;

-- public operations

Create: PUBLIC PROCEDURE [mod: CARDINAL ← 17]
RETURNS [Ref]
=
BEGIN
index: CARDINAL ← 0;
data: REF Array ← NIL;
IF mod < 1 THEN mod ← 1;
IF mod > 4095 THEN mod ← 4095;
data ← NEW[Array[mod]];
RETURN[NEW[RefTabRep ← [mod: mod, size: 0, data: data]]];
END;

GetSize: PUBLIC PROCEDURE [x: Ref] RETURNS [CARDINAL] =
{RETURN [x^.size]};

Fetch: PUBLIC ENTRY PROCEDURE [x: Ref, key: Key]
RETURNS [found: BOOLEAN, val: Val] = BEGIN
ENABLE UNWIND => NULL;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
WHILE node # NIL DO
IF key = node.key THEN RETURN [TRUE, node.val];
node ← node.next;
ENDLOOP;
RETURN [FALSE, NIL];
END;

EnterCode: TYPE = { insert, store, replace };

Replace: PUBLIC PROC [x: Ref, key: Key, val: Val] RETURNS [BOOLEAN] =
 { RETURN [Enter[x, key, val, replace]] };

Store: PUBLIC PROCEDURE [x: Ref, key: Key, val: Val] RETURNS [BOOLEAN] =
 { RETURN [Enter[x, key, val, store]] };

Insert: PUBLIC PROCEDURE [x: Ref, key: Key, val: Val] RETURNS [BOOLEAN] =
 { RETURN [Enter[x, key, val, insert]] };

Enter: ENTRY PROCEDURE [x: Ref, key: Key, val: Val, code: EnterCode]
RETURNS [BOOLEAN] = BEGIN
ENABLE UNWIND => NULL;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
head: Node ← node;
WHILE node # NIL DO
IF key = node.key THEN BEGIN
 SELECT code FROM
  store => node.val ← val;
  replace => { node.val ← val; RETURN [TRUE] };
  insert => NULL;
  ENDCASE => ERROR;
 RETURN [FALSE];
 END;
node ← node.next;
ENDLOOP;
IF code=replace THEN RETURN [FALSE];
x.data[hash] ← NEW[NodeRep ← [key: key, val: val, next: head]];
x.size ← x.size + 1;
RETURN [TRUE];
END;

Delete: PUBLIC ENTRY PROCEDURE [x: Ref, key: Key] RETURNS [BOOLEAN]
= BEGIN
ENABLE UNWIND => NULL;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
head: Node ← node;
lag: Node ← NIL;
WHILE node # NIL DO
IF key = node.key 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];
END;

Pairs: PUBLIC PROCEDURE [x: Ref, action: EachPairAction]
RETURNS [quit: BOOLEAN] = BEGIN
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;
END;

GetNext: ENTRY PROCEDURE [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.