DIRECTORY
PrincOps USING [zXOR],
DragomanRefTab USING [EachPairAction, Key, Node, NodeRep, Ref, RefTabRep, Seq, SeqIndex, Val];
DragomanRefTabImpl:
CEDAR
MONITOR
LOCKS x
USING x: Ref
EXPORTS DragomanRefTab = { OPEN DragomanRefTab;
Private Operations
Munch:
PROC [key: Key]
RETURNS [
CARDINAL] =
TRUSTED
MACHINE
CODE {
PrincOps.zXOR;
};
public operations
Create:
PUBLIC
PROC [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 ← [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 ← Munch[key] MOD 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];
};
Replace:
PUBLIC
ENTRY PROC [x: Ref, key: Key, val: Val]
RETURNS [
BOOL] = {
ENABLE UNWIND => NULL;
hash: CARDINAL ← Munch[key] MOD x.mod;
node: Node ← x.data[hash];
head: Node ← node;
WHILE node #
NIL
DO
IF 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 ← Munch[key] MOD x.mod;
node: Node ← x.data[hash];
head: Node ← node;
WHILE node #
NIL
DO
IF 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 ← Munch[key] MOD x.mod;
node: Node ← x.data[hash];
head: Node ← node;
WHILE node #
NIL
DO
IF 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 ← Munch[key] MOD 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];
};
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];
};
}.