HashTableImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Adapted from HashTableImpl.mesa by Satterthwaite, March 21, 1986 4:27:51 pm PST
Last Edited by Satterthwaite, May 13, 1986 11:42:56 am PDT
HashTableImpl:
CEDAR
MONITOR
LOCKS table
USING table: Table
EXPORTS HashTable = {
Key: TYPE = HashTable.Key;
Value: TYPE = HashTable.Value;
Table: TYPE = HashTable.Table;
NodeList: TYPE = HashTable.NodeList;
SeqIndex: TYPE = HashTable.SeqIndex;
Public operations
Create:
PUBLIC
PROC[ops: HashTable.OpsRec, mod: SeqIndex�]
RETURNS[Table] = {
mod ← MAX[mod, minMod];
RETURN[
NEW [HashTable.TableRec ← [
ops: ops,
size: 0,
sizeLimit: mod,
inhibitCount: 0,
data: NEW [HashTable.Seq[mod]]
]]]
};
minMod: SeqIndex = 2;
GetSize:
PUBLIC
PROC[table: Table]
RETURNS[
INT] = {
RETURN[table.size]};
ComputeIndex:
PROC[table: Table, key: Key]
RETURNS[SeqIndex] =
INLINE {
RETURN[table.ops.HashFromKey[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];
FOR node: NodeList ← table.data[hash], node.rest
WHILE node #
NIL
DO
IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]]
THEN
RETURN[TRUE, node.first];
ENDLOOP;
RETURN [FALSE, NIL]};
Replace:
PUBLIC
ENTRY
PROC[table: Table, key: Key, value: Value]
RETURNS[
BOOL] = {
ENABLE UNWIND => NULL;
hash: SeqIndex = ComputeIndex[table, key];
FOR node: NodeList ← table.data[hash], node.rest
WHILE node #
NIL
DO
IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]]
THEN {
node.first ← value; RETURN[TRUE]};
ENDLOOP;
RETURN[FALSE]};
Store:
PUBLIC
ENTRY
PROC[table: Table, key: Key, value: Value]
RETURNS[
BOOL] = {
ENABLE UNWIND => NULL;
hash: SeqIndex = ComputeIndex[table, key];
FOR node: NodeList ← table.data[hash], node.rest
WHILE node #
NIL
DO
IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]]
THEN {
node.first ← value; RETURN [FALSE]};
ENDLOOP;
table.data[hash] ← CONS[first: value, rest: 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];
FOR node: NodeList ← table.data[hash], node.rest
WHILE node #
NIL
DO
IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]]
THEN
RETURN[FALSE];
ENDLOOP;
table.data[hash] ← CONS[first: value, rest: 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];
lag: NodeList ← NIL;
FOR node: NodeList ← table.data[hash], node.rest
WHILE node #
NIL
DO
IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]]
THEN {
IF lag = NIL THEN table.data[hash] ← node.rest ELSE lag.rest ← node.rest;
table.size ← table.size - 1;
RETURN[TRUE]};
lag ← node;
ENDLOOP;
RETURN[FALSE]};
ForEach:
PUBLIC
PROC[table: Table, action: HashTable.EachValueAction]
RETURNS[quit: BOOL] = {
DInhibit[table, +1];
{ENABLE UNWIND => DInhibit[table, -1];
head: NodeList ← NIL;
index: CARDINAL ← table.data.max;
DO
[head, index] ← GetNext[table, head, index];
IF head = NIL THEN {quit ← FALSE; EXIT};
IF action[head.first] 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, head: NodeList, index:
CARDINAL]
RETURNS[NodeList, CARDINAL] = {
ENABLE UNWIND => NULL;
IF head #
NIL
THEN {
head ← head.rest;
IF head # NIL THEN RETURN[head, index]};
WHILE index > 0
DO
index ← index - 1;
head ← table.data[index];
IF head # NIL THEN RETURN[head, index];
ENDLOOP;
RETURN[NIL, 0]};
Erase:
PUBLIC
ENTRY
PROC[table: Table] = {
FOR i: SeqIndex IN [0..table.data.max) DO table.data[i] ← NIL ENDLOOP;
table.size ← 0};
ReHash:
INTERNAL
PROC[table: Table] = {
oldData: REF HashTable.Seq = table.data;
newData: REF HashTable.Seq;
seek: CARDINAL = table.data.max * 2;
newPTI, newMod: CARDINAL ← 0;
IF primeTable[PrimeTableSize-1] > SeqIndex.LAST 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 ← INT.LAST; RETURN};
table.sizeLimit ← newMod;
table.data ← newData ← NEW [HashTable.Seq[newMod]];
FOR i:
NAT
IN [0 .. oldData.max)
DO
next: NodeList ← NIL;
FOR cur: NodeList ← oldData[i], next
WHILE cur #
NIL
DO
hash: SeqIndex = ComputeIndex[table, table.ops.GetKey[cur.first]];
next ← cur.rest;
cur.rest ← 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];
}.