ValueHashTablesImpl.Mesa
Last tweaked by Mike Spreitzer on December 12, 1987 4:56:28 pm PST
DIRECTORY BiRels, SetBasics, AbSets, ValueHashTables;
ValueHashTablesImpl:
CEDAR
MONITOR
LOCKS ht USING ht: HashTable
EXPORTS ValueHashTables
=
BEGIN OPEN SetBasics, Sets:AbSets, Sets, BiRels, ValueHashTables;
Destroyed: ERROR = CODE;
HashTable: TYPE ~ REF HashTablePrivate;
HashTablePrivate:
PUBLIC
TYPE ~
MONITORED
RECORD [
space: Space,
size, sizeLimit, inhibitCount: INT ← 0,
destroyed: BOOL ← FALSE,
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 [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 ← noMaybe] ~ {
Decide: PROC [old: MaybeValue] RETURNS [MaybeValue] ~ {RETURN [mv ← old]};
IF ht # Update[ht, arg, Decide] THEN ERROR;
RETURN};
Store:
PUBLIC
PROC [ht: HashTable, arg, res: Value]
RETURNS [same: HashTable] ~ {
Decide: PROC [old: MaybeValue] RETURNS [MaybeValue] ~ {RETURN [[TRUE, res]]};
same ← Update[ht, arg, Decide];
};
Delete:
PUBLIC
PROC [ht: HashTable, arg: Value]
RETURNS [had:
BOOL ←
FALSE] ~ {
Decide: PROC [old: MaybeValue] RETURNS [MaybeValue] ~ {had ← old.found; RETURN [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[ht.space.data, arg, node.first[left]]
THEN {
new: MaybeValue ~ Decide[[TRUE, node.first[right]]];
IF new.found THEN TRUSTED {node.first[right] ← new.it}
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.it], 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 ← noMaybePair] = {
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;
};
IF ht.destroyed THEN RETURN WITH ERROR Destroyed;
Inhibit[ht];
{ENABLE UNWIND => Release[ht];
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]; EXIT};
ENDLOOP;
};
Release[ht];
RETURN};
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.