IntChainedHashTableImpl.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
Adapted from HashTableImpl.mesa by Mike Spreitzer, November 13, 1986 11:24:54 pm PST
Spreitzer, May 7, 1986 4:32:49 pm PDT
Public operations
Stuck: PUBLIC ERROR = CODE;
Create:
PUBLIC
PROC [invalidKey: Key, mod: SeqIndex ← 17]
RETURNS [Table] = {
pog: PrimeTableIndex = Pog[mod];
pmod: CARDINAL = primeTable[pog];
data: REF Seq = NEW [Seq[pmod]];
FOR i: CARDINAL IN [0..data.max) DO data[i] ← [key: invalidKey, value: NIL] ENDLOOP;
RETURN [
NEW [TableRec ← [
size: 0,
sizeLimit: pmod*2/3,
inhibitCount: 0,
chain: IF pog > 0 THEN primeTable[pog-1] ELSE 1,
invalidKey: invalidKey,
data: data
]]];
};
GetSize:
PUBLIC
PROC [table: Table]
RETURNS [
INT] = {
RETURN [table.size];
};
ComputeIndex:
PROC [table: Table, key: Key]
RETURNS [index: SeqIndex] =
INLINE {
index ← key MOD table.data.max;
};
Fetch:
PUBLIC
ENTRY
PROC [table: Table, key: Key]
RETURNS [found:
BOOL, value: Value] = {
ENABLE UNWIND => NULL;
data: REF Seq = table.data;
hash: SeqIndex ← ComputeIndex[table, key];
WHILE data[hash].key # table.invalidKey
DO
IF key=data[hash].key THEN RETURN [TRUE, data[hash].value];
hash ← IF hash < table.chain THEN (data.max - table.chain + hash) ELSE (hash - table.chain);
ENDLOOP;
RETURN [FALSE, NIL];
};
Replace:
PUBLIC
ENTRY
PROC [table: Table, key: Key, value: Value]
RETURNS [
BOOL] = {
ENABLE UNWIND => NULL;
data: REF Seq = table.data;
hash: SeqIndex ← ComputeIndex[table, key];
WHILE data[hash].key # table.invalidKey
DO
IF key=data[hash].key THEN {data[hash].value ← value; RETURN [TRUE]};
hash ← IF hash < table.chain THEN (data.max - table.chain + hash) ELSE (hash - table.chain);
ENDLOOP;
RETURN [FALSE];
};
Store:
PUBLIC
ENTRY
PROC [table: Table, key: Key, value: Value]
RETURNS [
BOOL] = {
ENABLE UNWIND => NULL;
IF table.size >= table.sizeLimit
THEN {
IF table.inhibitCount = 0 THEN ReHash[table]
ELSE IF table.size+1 = table.data.max THEN ERROR Stuck};
{data: REF Seq = table.data;
hash: SeqIndex ← ComputeIndex[table, key];
WHILE data[hash].key # table.invalidKey
DO
IF key=data[hash].key THEN {data[hash].value ← value; RETURN [FALSE]};
hash ← IF hash < table.chain THEN (data.max - table.chain + hash) ELSE (hash - table.chain);
ENDLOOP;
data[hash] ← [key: key, value: value];
table.size ← table.size + 1;
RETURN [TRUE];
}};
Insert:
PUBLIC
ENTRY
PROC [table: Table, key: Key, value: Value]
RETURNS [new:
BOOL] = {
ENABLE UNWIND => NULL;
IF table.size >= table.sizeLimit
THEN {
IF table.inhibitCount = 0 THEN ReHash[table]
ELSE IF table.size+1 = table.data.max THEN ERROR Stuck};
new ← BasicInsert[table, key, value];
table.size ← table.size + 1;
};
BasicInsert:
INTERNAL
PROC [table: Table, key: Key, value: Value]
RETURNS [
BOOL] = {
data: REF Seq = table.data;
hash: SeqIndex ← ComputeIndex[table, key];
WHILE data[hash].key # table.invalidKey
DO
IF key=data[hash].key THEN RETURN [FALSE];
hash ← IF hash < table.chain THEN (data.max - table.chain + hash) ELSE (hash - table.chain);
ENDLOOP;
data[hash] ← [key: key, value: value];
RETURN [TRUE];
};
Pairs:
PUBLIC
PROC [table: Table, action: EachPairAction]
RETURNS [quit:
BOOL] = {
DInhibit[table, +1];
{ENABLE UNWIND => DInhibit[table, -1];
data: REF Seq = table.data;
FOR index:
CARDINAL
IN [0 .. data.max)
DO
IF data[index].key # table.invalidKey AND action[data[index].key, data[index].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;
};
Erase:
PUBLIC
ENTRY
PROC [table: Table] = {
data: REF Seq = table.data;
FOR i: CARDINAL IN [0..data.max) DO data[i] ← [key: table.invalidKey, value: 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: PrimeTableIndex = Pog[seek];
newMod: CARDINAL ← 0;
IF primeTable[PrimeTableSize-1] > LAST[SeqIndex] THEN ERROR;
newMod ← primeTable[newPTI];
IF newMod = table.data.max THEN {table.sizeLimit ← LAST[NAT]; RETURN};
table.sizeLimit ← newMod*2/3;
table.chain ← primeTable[newPTI-1];
table.data ← newData ← NEW [Seq[newMod]];
FOR i: NAT IN [0 .. table.data.max) DO table.data[i] ← [key: table.invalidKey, value: NIL] ENDLOOP;
table ← table;
FOR i:
NAT
IN [0 .. oldData.max)
DO
IF oldData[i].key # table.invalidKey AND NOT BasicInsert[table, oldData[i].key, oldData[i].value] THEN ERROR;
ENDLOOP;
table ← table;
};
Pog:
PROC [n:
CARDINAL]
RETURNS [p: PrimeTableIndex] = {
PrimeTableSizeMinusOne: NAT = PrimeTableSize-1;
FOR p ← 0, p+1 WHILE p < PrimeTableSizeMinusOne AND primeTable[p] < n DO NULL ENDLOOP;
};
PrimeTableSize: NAT = 14;
PrimeTableIndex: TYPE = NAT[0 .. PrimeTableSize);
primeTable:
ARRAY PrimeTableIndex
OF
CARDINAL = [
00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, 32749];
}.