HashTablesImpl.Mesa
Last tweaked by Mike Spreitzer on May 15, 1987 10:07:25 am PDT
DIRECTORY HashTables, Collections, PairCollections;
HashTablesImpl: CEDAR MONITOR
LOCKS ht USING ht: HashTable
IMPORTS Collections, PairCollections
EXPORTS HashTables
=
BEGIN OPEN Collections, PairCollections, HashTables;
Destroyed: ERROR = CODE;
HashTable: TYPE ~ REF HashTablePrivate;
HashTablePrivate: PUBLIC TYPE ~ MONITORED RECORD [
space: Space,
size, sizeLimit, inhibitCount: INT ← 0,
destroyed: BOOLFALSE,
seq: REF Seq
];
SeqIndex: TYPE = NAT;
Seq: TYPE = RECORD [nodes: SEQUENCE max: SeqIndex OF Node];
Node: TYPE ~ LOP;
ComputeIndex: PROC [ht: HashTable, key: Value] RETURNS [SeqIndex] = INLINE {
RETURN [(IF ht.space.Hash=NIL THEN HashRefI[key] ELSE ht.space.Hash[ht.space.data, key]) MOD ht.seq.max];
};
Create: PUBLIC PROC [space: Space] RETURNS [ht: HashTable] ~ {
ht ← NEW [HashTablePrivate ← [
space: space,
sizeLimit: initSize,
seq: NEW [Seq[initSize]]
]];
};
Size: PUBLIC ENTRY PROC [ht: HashTable] RETURNS [INT] = {
ENABLE UNWIND => NULL;
IF ht.destroyed THEN RETURN WITH ERROR Destroyed;
RETURN [ht.size];
};
Map: PUBLIC PROC [ht: HashTable, arg: Value] RETURNS [mv: MaybeValue] ~ {
Decide: PROC [old: MaybeValue] RETURNS [new: MaybeValue] ~ {mv ← new ← old};
IF ht # Update[ht, arg, Decide] THEN ERROR;
};
Store: PUBLIC PROC [ht: HashTable, arg, res: Value] RETURNS [same: HashTable] ~ {
Decide: PROC [old: MaybeValue] RETURNS [new: MaybeValue] ~ {new ← [TRUE, res]};
same ← Update[ht, arg, Decide];
};
Delete: PUBLIC PROC [ht: HashTable, arg: Value] RETURNS [had: BOOL] ~ {
Decide: PROC [old: MaybeValue] RETURNS [new: MaybeValue] ~ {had ← old.found; new ← noMaybe};
IF ht # Update[ht, arg, Decide] THEN ERROR;
};
Update: PUBLIC ENTRY PROC [ht: HashTable, arg: Value, Decide: Decider] RETURNS [same: HashTable] ~ {
ENABLE UNWIND => NULL;
index: SeqIndex ~ ComputeIndex[ht, arg];
prev: Node ← NIL;
same ← ht;
FOR node: Node ← ht.seq[index], node.rest WHILE node # NIL DO
IF arg=node.first[left] OR (ht.space.Equal#NIL AND ht.space.Equal[ht.space.data, arg, node.first[left]]) THEN {
new: MaybeValue ~ Decide[[TRUE, node.first[right]]];
IF new.found THEN node.first[right] ← new.val ELSE {
IF prev=NIL THEN ht.seq[index] ← node.rest ELSE prev.rest ← node.rest;
ht.size ← ht.size - 1;
};
RETURN;
};
prev ← node;
ENDLOOP;
{new: MaybeValue ~ Decide[noMaybe];
IF new.found THEN {
ht.seq[index] ← CONS[[arg, new.val], ht.seq[index]];
IF (ht.size ← ht.size + 1) > ht.sizeLimit AND ht.inhibitCount = 0 THEN same ← ReHash[ht];
};
}};
Scan: PUBLIC PROC [ht: HashTable, Test: Tester] RETURNS [same: HashTable, mp: MaybePair] = {
Inhibit: ENTRY PROC [ht: HashTable] ~ {
ENABLE UNWIND => NULL;
ht.inhibitCount ← ht.inhibitCount + 1;
};
Release: ENTRY PROC [ht: HashTable] ~ {
ENABLE UNWIND => NULL;
same ← ht;
same.inhibitCount ← same.inhibitCount - 1;
IF same.inhibitCount#0 THEN RETURN;
WHILE same.size > same.sizeLimit DO same ← ReHash[same] ENDLOOP;
};
Enumerate: PROC ~ {
node: Node ← NIL;
index: CARDINAL ← 0;
DO
[node, index] ← GetNext[ht, node, index];
IF node = NIL THEN EXIT;
IF Test[node.first] THEN {mp ← [TRUE, node.first]; RETURN};
ENDLOOP;
};
IF ht.destroyed THEN RETURN WITH ERROR Destroyed;
mp ← noMaybePair;
Inhibit[ht];
Enumerate[! UNWIND => Release[ht]];
Release[ht];
};
GetNext: ENTRY PROC [ht: HashTable, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = {
ENABLE UNWIND => NULL;
IF node = NIL
THEN index ← ht.seq.max
ELSE {
node ← node.rest;
IF node # NIL THEN RETURN [node, index];
};
WHILE index > 0 DO
index ← index - 1;
node ← ht.seq[index];
IF node # NIL THEN RETURN [node, index];
ENDLOOP;
RETURN [NIL, 0];
};
ReHash: INTERNAL PROC [old: HashTable] RETURNS [new: HashTable] = {
oldSeq: REF Seq = old.seq;
newSeq: REF Seq;
seek: CARDINAL = oldSeq.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 = oldSeq.max THEN {old.sizeLimit ← LAST[INT]; RETURN [old]};
new ← NEW [HashTablePrivate ← [
space: old.space,
size: old.size,
sizeLimit: newMod,
seq: newSeq ← NEW [Seq[newMod]]
]];
FOR i: SeqIndex IN [0 .. oldSeq.max) DO
next: Node ← NIL;
FOR cur: Node ← oldSeq[i], next WHILE cur # NIL DO
index: SeqIndex ← ComputeIndex[new, cur.first[left]];
next ← cur.rest;
cur.rest ← newSeq[index];
newSeq[index] ← cur;
ENDLOOP;
IF next # NIL THEN ERROR;
ENDLOOP;
};
PrimeTableSize: NAT = 14;
highPrime: CARDINAL[0..LAST[SeqIndex]] = 32749;
initSize: NAT ~ 5;
primeTable: ARRAY [0 .. PrimeTableSize) OF CARDINAL = [
00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, highPrime];
END.