RefTabImpl.Mesa - implementation of REF table abstraction
Copyright © 1985 by Xerox Corporation. All rights reserved.
Paxton - August 19, 1982 9:25 am
Teitelman - September 8, 1982 9:12 pm
Rovner - August 9, 1983 5:26 pm
Russ Atkinson (RRA) February 5, 1985 2:01:52 pm PST
DIRECTORY
PrincOps USING [zXOR],
RefTab USING [EachPairAction, Key, Node, NodeRep, Ref, RefTabRep, Seq, SeqIndex, Val];
RefTabImpl: CEDAR MONITOR LOCKS x USING x: Ref
EXPORTS RefTab = { OPEN RefTab;
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];
};
}.