ReHashTableImpl.mesa
Adapted from RefTabImpl.mesa by Bertrand Serlet, July 24, 1985 4:29:40 pm PDT
Last Edited by Bertrand Serlet, August 12, 1985 7:06:47 pm PDT
Last Edited by Widom, July 25, 1985 4:46:10 pm PDT
Spreitzer, November 6, 1985 12:24:25 pm PST
DIRECTORY
ReHashTable,
Rope,
RopeHash,
PrincOps USING [zXOR];
ReHashTableImpl: CEDAR MONITOR LOCKS table USING table: Table
IMPORTS Rope, RopeHash
EXPORTS ReHashTable = {
OPEN ReHashTable;
Default hash
Munch: HashProc = TRUSTED MACHINE CODE {
PrincOps.zXOR;
};
Public operations
Create: PUBLIC PROC [mod: SeqIndex ← 17, equal: EqualProc ← NIL, hash: HashProc ← NIL] RETURNS [Table] = {
mod ← MAX[mod, minMod];
RETURN [NEW [TableRec ← [
hash: hash,
equal: equal,
size: 0,
sizeLimit: mod,
inhibitCount: 0,
data: NEW [Seq[mod]]
]]];
};
minMod: SeqIndex = 2;
RopeEqual: PUBLIC PROC [k1, k2: Key] RETURNS [eq: BOOL] = {
r1: Rope.ROPE = NARROW[k1];
r2: Rope.ROPE = NARROW[k2];
eq ← r1.Equal[r2, TRUE];
};
RopeEqualModCase: PUBLIC PROC [k1, k2: Key] RETURNS [eq: BOOL] = {
r1: Rope.ROPE = NARROW[k1];
r2: Rope.ROPE = NARROW[k2];
eq ← r1.Equal[r2, FALSE];
};
HashRope: PUBLIC PROC [k: Key] RETURNS [hash: CARDINAL] = {
hash ← RopeHash.FromRope[NARROW[k], TRUE];
};
HashRopeModCase: PUBLIC PROC [k: Key] RETURNS [hash: CARDINAL] = {
hash ← RopeHash.FromRope[NARROW[k], FALSE];
};
GetSize: PUBLIC PROC [table: Table] RETURNS [INT] = {
RETURN [table.size];
};
ComputeIndex: PROC [table: Table, key: Key] RETURNS [index: SeqIndex] = INLINE {
hash: CARDINALIF table.hash=NIL THEN Munch[key] ELSE table.hash[key];
index ← hash MOD table.data.max;
};
Fetch: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [found: BOOL, value: Value] = {
ENABLE UNWIND => NULL;
hash: SeqIndex ← ComputeIndex[table, key];
node: Node ← table.data[hash];
WHILE node # NIL DO
IF key=node.key OR (table.equal#NIL AND table.equal[key, node.key])
THEN RETURN [TRUE, node.value];
node ← node.next;
ENDLOOP;
RETURN [FALSE, NIL];
};
Replace: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
hash: SeqIndex ← ComputeIndex[table, key];
node: Node ← table.data[hash];
WHILE node # NIL DO
IF key=node.key OR (table.equal#NIL AND table.equal[key, node.key])
THEN {node.value ← value; RETURN [TRUE]};
node ← node.next;
ENDLOOP;
RETURN [FALSE];
};
Store: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
hash: SeqIndex ← ComputeIndex[table, key];
node: Node ← table.data[hash];
WHILE node # NIL DO
IF key=node.key OR (table.equal#NIL AND table.equal[key, node.key])
THEN {node.value ← value; RETURN [FALSE]};
node ← node.next;
ENDLOOP;
table.data[hash] ← NEW[NodeRep ← [key: key, value: value, next: table.data[hash]]];
IF (table.size ← table.size + 1) > table.sizeLimit AND table.inhibitCount = 0 THEN ReHash[table];
RETURN [TRUE];
};
Insert: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
hash: SeqIndex ← ComputeIndex[table, key];
node: Node ← table.data[hash];
WHILE node # NIL DO
IF key=node.key OR (table.equal#NIL AND table.equal[key, node.key])
THEN RETURN [FALSE];
node ← node.next;
ENDLOOP;
table.data[hash] ← NEW[NodeRep ← [key: key, value: value, next: table.data[hash]]];
IF (table.size ← table.size + 1) > table.sizeLimit AND table.inhibitCount = 0 THEN ReHash[table];
RETURN [TRUE];
};
Delete: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [BOOL] = {
ENABLE UNWIND => NULL;
hash: SeqIndex ← ComputeIndex[table, key];
node: Node ← table.data[hash];
lag: Node ← NIL;
WHILE node # NIL DO
IF key=node.key OR (table.equal#NIL AND table.equal[key, node.key]) THEN {
IF lag = NIL THEN table.data[hash] ← node.next ELSE lag.next ← node.next;
table.size ← table.size - 1;
RETURN [TRUE];
};
lag ← node;
node ← node.next;
ENDLOOP;
RETURN [FALSE];
};
Pairs: PUBLIC PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL] = {
node: Node ← NIL;
DInhibit[table, +1];
{ENABLE UNWIND => DInhibit[table, -1];
index: CARDINAL ← table.data.max;
DO
[node, index] ← GetNext[table, node, index];
IF node = NIL THEN {quit ← FALSE; EXIT};
IF action[node.key, node.value] THEN {quit ← TRUE; EXIT};
ENDLOOP;
};
DInhibit[table, -1];
};
DInhibit: ENTRY PROC [table: Table, D: INT] = {
table.inhibitCount ← table.inhibitCount + D;
WHILE table.inhibitCount = 0 AND table.size > table.sizeLimit DO ReHash[table] ENDLOOP;
};
GetNext: ENTRY PROC [table: Table, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = {
ENABLE UNWIND => NULL;
IF node # NIL THEN {
node ← node.next;
IF node # NIL THEN RETURN [node, index];
};
WHILE index > 0 DO
index ← index - 1;
node ← table.data[index];
IF node # NIL THEN RETURN [node, index];
ENDLOOP;
RETURN [NIL, 0];
};
Erase: PUBLIC ENTRY PROC [table: Table] = {
FOR i: CARDINAL IN [0..table.data.max) DO table.data[i] ← NIL ENDLOOP;
table.size ← 0;
};
ReHash: INTERNAL PROC [table: Table] = {
oldData: REF Seq = table.data;
newData: REF Seq;
seek: CARDINAL = table.data.max * 2;
newPTI, newMod: CARDINAL ← 0;
IF primeTable[PrimeTableSize-1] > LAST[SeqIndex] THEN ERROR;
FOR newPTI ← 0, newPTI+1 WHILE newPTI+1 < PrimeTableSize AND primeTable[newPTI] < seek DO NULL ENDLOOP;
newMod ← primeTable[newPTI];
IF newMod = table.data.max THEN {table.sizeLimit ← LAST[INT]; RETURN};
table.sizeLimit ← newMod;
table.data ← newData ← NEW [Seq[newMod]];
FOR i: NAT IN [0 .. oldData.max) DO
next: Node ← NIL;
FOR cur: Node ← oldData[i], next WHILE cur # NIL DO
hash: SeqIndex ← ComputeIndex[table, cur.key];
next ← cur.next;
cur.next ← newData[hash];
newData[hash] ← cur;
ENDLOOP;
IF next # NIL THEN ERROR;
ENDLOOP;
table ← table;
};
PrimeTableSize: NAT = 14;
primeTable: ARRAY [0 .. PrimeTableSize) OF CARDINAL = [
00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, 32749];
}.