GeneralRefTabImpl.Mesa
Implementation for generalized REF table abstraction, with the possibility to give the hash function and the equality function.
Adapted from RefTabImpl.Mesa by Bertrand Serlet, June 3, 1985 6:08:45 pm PDT
Last Edited by Bertrand Serlet, June 15, 1985 2:44:10 pm PDT
DIRECTORY
GeneralRefTab,
PrincOps USING [zXOR];
GeneralRefTabImpl: CEDAR MONITOR LOCKS x USING x: Ref
EXPORTS GeneralRefTab = { OPEN GeneralRefTab;
Default hash and equality
Munch: PRIVATE HashProc = TRUSTED MACHINE CODE {
PrincOps.zXOR;
};
DefaultHashProc: PUBLIC HashProc = {RETURN[Munch[key]]};
DefaultEqualProc: PUBLIC EqualProc = {RETURN [key1=key2]}; -- The vanilla equality
Public operations
Create: PUBLIC PROC [hashProc: HashProc ← DefaultHashProc, equalProc: EqualProc ← DefaultEqualProc, mod: SeqIndex ← 17] RETURNS [Ref] = {
index: CARDINAL ← 0;
data: REF Seq ← NIL;
IF mod < 7 THEN mod ← 7;
data ← NEW[Seq[mod]];
RETURN[NEW[RefTabRep ← [hashProc: NEW[HashProc ← hashProc], equalProc: NEW[EqualProc ← equalProc], mod: mod, size: 0, data: data]]];
};
GetSize: PUBLIC PROC [x: Ref] RETURNS [INT] = {
RETURN [x.size];
};
Fetch: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = {
ENABLE UNWIND => NULL;
hash: CARDINAL ← x.hashProc[key] MOD x.mod;
node: Node ← x.data[hash];
WHILE node # NIL DO
IF x.equalProc[key, node.key] THEN RETURN [TRUE, node.val];
node ← node.next;
ENDLOOP;
RETURN [FALSE, NIL];
};
Replace: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
hash: CARDINAL ← x.hashProc[key] MOD x.mod;
node: Node ← x.data[hash];
head: Node ← node;
WHILE node # NIL DO
IF x.equalProc[key, node.key] THEN {node.val ← val; RETURN [TRUE]};
node ← node.next;
ENDLOOP;
RETURN [FALSE];
};
Store: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
hash: CARDINAL ← x.hashProc[key] MOD x.mod;
node: Node ← x.data[hash];
head: Node ← node;
WHILE node # NIL DO
IF x.equalProc[key, node.key] 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;
hash: CARDINAL ← x.hashProc[key] MOD x.mod;
node: Node ← x.data[hash];
head: Node ← node;
WHILE node # NIL DO
IF x.equalProc[key, node.key] 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;
hash: CARDINAL ← x.hashProc[key] MOD x.mod;
node: Node ← x.data[hash];
head: Node ← node;
lag: Node ← NIL;
WHILE node # NIL DO
IF x.equalProc[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];
};
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];
};
}.