IntHashTableImpl.mesa
Copyright Ó 1992 by Xerox Corporation. All rights reserved.
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, May 7, 1986 4:29:35 pm PDT
Spreitzer, May 7, 1986 4:32:49 pm PDT
Russ Atkinson (RRA) January 16, 1987 6:31:36 pm PST
Ported by Bob Krivacic, December 4, 1989 10:37:18 am PST
Public operations
Create:
PUBLIC
PROC [mod: SeqIndex ¬ 17]
RETURNS [Table] = {
mod ¬ MAX[mod, minMod];
RETURN [
NEW [TableRec ¬ [
size: 0,
sizeLimit: mod,
inhibitCount: 0,
data: NEW [Seq[mod]]
]]];
};
minMod: SeqIndex = 2;
GetSize:
PUBLIC
PROC [table: Table]
RETURNS [
INT] = {
RETURN [table.size];
};
Nicefy:
PROC [key:
INT32]
RETURNS [
CARD16] =
TRUSTED INLINE {
RETURN[ Basics.LowHalf[LOOPHOLE[key]] + Basics.HighHalf[LOOPHOLE[key]] ];
};
ComputeIndex:
PROC [table: Table, key: Key]
RETURNS [index: SeqIndex] =
INLINE {
index ¬ Nicefy[key] 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 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 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 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 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
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];
}.