IntToIntTabImpl.mesa
Copyright Ó 1987, 1988, 1990, 1991 by Xerox Corporation. All rights reserved.
Adapted from similar package by Christian Jacobi, May 13, 1987 10:43:20 am PDT
Christian Jacobi, July 19, 1990 12:43 pm PDT
DIRECTORY
IntToIntTab;
IntToIntTabImpl: CEDAR MONITOR LOCKS table USING table: Table
EXPORTS IntToIntTab =
BEGIN
OPEN IntToIntTab;
Impl: TYPE ~ REF IntToIntTabImplRep;
IntToIntTabImplRep: PUBLIC TYPE = RECORD [
size, sizeLimit, inhibitCount: INT,
data: REF Seq
];
SeqIndex: TYPE = NAT;
Seq: TYPE = RECORD [nodes: SEQUENCE max: SeqIndex OF Node];
Node: TYPE = REF NodeRep;
NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node];
minMod: SeqIndex = 2;
Create: PUBLIC PROC [mod: SeqIndex ¬ 17] RETURNS [Table] = {
seqLen: SeqIndex ~ MAX[mod, minMod];
impl: Impl ~ NEW [IntToIntTabImplRep ¬ [
size: 0, sizeLimit: seqLen, inhibitCount: 0,
data: NEW [Seq[seqLen]]
]];
RETURN [NEW [IntToIntTabRep ¬ [impl: impl]]];
};
GetSize: PUBLIC ENTRY PROC [table: Table] RETURNS [INT] = {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
RETURN [impl.size];
};
Nicefy: PROC [key: INT32] RETURNS [CARD32] = INLINE {
--for 32 bit machine CARD32 is good operand for MOD operation
RETURN [ LOOPHOLE[key] ]
};
ComputeIndex: PROC [impl: Impl, key: Key] RETURNS [index: SeqIndex] = INLINE {
index ¬ Nicefy[key] MOD impl.data.max;
};
Fetch: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [found: BOOL, val: Val] = {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
hash: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[hash];
WHILE node # NIL DO
IF key=node.key THEN RETURN [TRUE, node.val];
node ¬ node.next;
ENDLOOP;
RETURN [FALSE, -1];
};
Replace: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
hash: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[hash];
WHILE node # NIL DO
IF key=node.key THEN {node.val ¬ val; RETURN [TRUE]};
node ¬ node.next;
ENDLOOP;
RETURN [FALSE];
};
Store: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
hash: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[hash];
WHILE node # NIL DO
IF key=node.key THEN {node.val ¬ val; RETURN [FALSE]};
node ¬ node.next;
ENDLOOP;
impl.data[hash] ¬ NEW[NodeRep ¬ [key: key, val: val, next: impl.data[hash]]];
IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl];
RETURN [TRUE];
};
Insert: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
hash: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[hash];
WHILE node # NIL DO
IF key=node.key THEN RETURN [FALSE];
node ¬ node.next;
ENDLOOP;
impl.data[hash] ¬ NEW[NodeRep ¬ [key: key, val: val, next: impl.data[hash]]];
IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl];
RETURN [TRUE];
};
Delete: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
hash: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[hash];
lag: Node ¬ NIL;
WHILE node # NIL DO
IF key=node.key THEN {
IF lag = NIL THEN impl.data[hash] ¬ node.next ELSE lag.next ¬ node.next;
impl.size ¬ impl.size - 1;
RETURN [TRUE];
};
lag ¬ node;
node ¬ node.next;
ENDLOOP;
RETURN [FALSE];
};
Erase: PUBLIC ENTRY PROC [table: Table] = {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
FOR i: SeqIndex IN [0..impl.data.max) DO impl.data[i] ¬ NIL ENDLOOP;
impl.size ¬ 0;
};
Pairs: PUBLIC PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL] = {
Inhibit: ENTRY PROC [table: Table] ~ {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
impl.inhibitCount ¬ impl.inhibitCount + 1;
};
Release: ENTRY PROC [table: Table] ~ {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
impl.inhibitCount ¬ impl.inhibitCount - 1;
IF impl.inhibitCount#0 THEN RETURN;
WHILE impl.size > impl.sizeLimit DO ReHash[impl] ENDLOOP;
};
Enumerate: PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL ¬ FALSE] ~ {
node: Node ¬ NIL;
index: CARDINAL ¬ 0;
DO
[node, index] ¬ GetNext[table, node, index];
IF node = NIL THEN EXIT;
IF action[node.key, node.val] THEN RETURN [TRUE];
ENDLOOP;
};
Inhibit[table];
quit ¬ Enumerate[table, action ! UNWIND => Release[table]];
Release[table];
};
GetNext: ENTRY PROC [table: Table, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = {
ENABLE UNWIND => NULL;
impl: Impl ~ table.impl;
IF node = NIL
THEN index ¬ impl.data.max
ELSE {
node ¬ node.next;
IF node # NIL THEN RETURN [node, index];
};
WHILE index > 0 DO
index ¬ index - 1;
node ¬ impl.data[index];
IF node # NIL THEN RETURN [node, index];
ENDLOOP;
RETURN [NIL, 0];
};
Update: PUBLIC ENTRY PROC [table: Table, key: Key, action: UpdateAction] = {
ENABLE UNWIND => NULL; --necessary: calls client procedure
IF action # NIL THEN {
impl: Impl ~ table.impl;
index: SeqIndex ¬ ComputeIndex[impl, key];
head: Node ¬ impl.data[index];
node: Node ¬ head;
lag: Node ¬ NIL;
op: UpdateOperation ¬ none;
val: Val;
WHILE node # NIL DO
next: Node ¬ node.next;
IF key=node.key THEN {
[op, val] ¬ action[TRUE, node.val];
SELECT op FROM
delete => IF lag = NIL THEN impl.data[index] ¬ next ELSE lag.next ¬ next;
store => node.val ¬ val;
ENDCASE;
RETURN;
};
lag ¬ node;
node ¬ next;
ENDLOOP;
[op, val] ¬ action[FALSE, -1];
SELECT op FROM
store => {
impl.data[index] ¬ NEW[NodeRep ¬ [key: key, val: val, next: head]];
IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN
ReHash[impl];
};
ENDCASE;
};
};
Copy: PUBLIC ENTRY PROC [table: Table] RETURNS [Table] = {
ENABLE UNWIND => NULL;
impl: Impl = table.impl;
oldData: REF Seq = impl.data;
max: CARDINAL = oldData.max;
newImpl: Impl = NEW[IntToIntTabImplRep ¬ impl­];
newData: REF Seq = NEW[Seq[max]]; -- note, all buckets initially NIL
newImpl.data ¬ newData;
FOR i: NAT IN [0..max) DO
oldChain: Node ¬ oldData[i];
IF oldChain # NIL THEN {
newTail: Node ¬ NIL;
WHILE oldChain # NIL DO
new: Node ¬ NEW[NodeRep ¬ [key: oldChain.key, val: oldChain.val, next: NIL]];
IF newTail = NIL THEN newData[i] ¬ new ELSE newTail.next ¬ new;
newTail ¬ new;
oldChain ¬ oldChain.next;
ENDLOOP;
};
ENDLOOP;
RETURN [NEW[IntToIntTabRep ¬ [impl: newImpl]]];
};
ReHash: INTERNAL PROC [impl: Impl] = {
oldData: REF Seq = impl.data;
newData: REF Seq;
seek: CARDINAL = impl.data.max * 2;
newPTI: CARDINAL ¬ 0;
newMod: CARDINAL ¬ highPrime;
IF seek >= highPrime
THEN newPTI ¬ primeTableSize-1
ELSE DO
newMod ¬ primeTable[newPTI];
IF newMod >= seek THEN EXIT;
newPTI ¬ newPTI+1;
ENDLOOP;
IF newMod = impl.data.max THEN {impl.sizeLimit ¬ LAST[INT]; RETURN};
impl.sizeLimit ¬ newMod;
impl.data ¬ newData ¬ NEW[Seq[newMod]];
FOR i: SeqIndex IN [0 .. oldData.max) DO
next: Node ¬ NIL;
FOR cur: Node ¬ oldData[i], next WHILE cur # NIL DO
hash: SeqIndex ¬ ComputeIndex[impl, cur.key];
next ¬ cur.next;
cur.next ¬ newData[hash];
newData[hash] ¬ cur;
ENDLOOP;
IF next # NIL THEN ERROR;
ENDLOOP;
};
primeTableSize: NAT = 14;
highPrime: CARDINAL[0..LAST[SeqIndex]] = 32749;
primeTable: ARRAY [0 .. primeTableSize) OF CARDINAL = [
00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, highPrime];
END.