SetByHash.Mesa
Last tweaked by Mike Spreitzer on February 27, 1988 12:36:04 pm PST
DIRECTORY AbSets, IntStuff, SetBasics;
SetByHash:
CEDAR
MONITOR
LOCKS ht USING ht: HashTable
IMPORTS AbSets, IntStuff, SetBasics
EXPORTS AbSets
=
BEGIN OPEN SetBasics, Sets:AbSets, Sets, IS:IntStuff;
HashTable: TYPE ~ REF HashTablePrivate;
HashTablePrivate:
PUBLIC
TYPE ~
MONITORED
RECORD [
space: Space,
size, sizeLimit, inhibitCount, frozenScans, freezeCount: INT ← 0,
seq: REF Seq
];
SeqIndex: TYPE = NAT;
Seq: TYPE = RECORD [nodes: SEQUENCE max: SeqIndex OF Node];
Node: TYPE ~ LOV;
Classes: TYPE ~ ARRAY Mutability OF SetClass;
classes: REF Classes ~ NEW [Classes];
frozenClass: SetClass ~ CreateClass[[
HasMember: HasMemByUpdate,
Scan: HashScan,
Size: HashSize,
Copy: HashCopy,
Insulate: HashInsulate,
ValueOf: HashValueOf,
Freeze: HashFreeze,
Thaw: HashThaw,
SpaceOf: HashSpaceOf,
mutability: constant,
data: $Frigid]];
ComputeIndex:
PROC [ht: HashTable, key: Value]
RETURNS [SeqIndex] =
INLINE {
RETURN [ht.space.SHash[key] MOD ht.seq.max];
};
CreateHashCopy:
PUBLIC
PROC [set: Set, space: Space ←
NIL
--NIL means to use the same space as the given set--]
RETURNS [HashSet] ~ {
copy: HashSet ~ CreateHashSet[IF space=NIL THEN set.SpaceOf[] ELSE space];
[] ← copy.AddSet[set];
RETURN [copy]};
CreateHashSetFromProc:
PUBLIC
PROC [
Produce:
PROC [
Consume:
PROC [Value]], space: Space ← refs]
RETURNS [HashSet] ~ {
set: HashSet ~ CreateHashSet[space];
Consume: PROC [val: Value] ~ {[] ← set.AddElt[val]; RETURN};
Produce[Consume];
RETURN [set]};
CreateHashSet:
PUBLIC
PROC [space: Space ← refs]
RETURNS [HashSet] ~ {
ht: HashTable ~
NEW [HashTablePrivate ← [
space: space,
sizeLimit: initSize,
seq: NEW [Seq[initSize]]
]];
RETURN AsVar[[classes[variable], AV[ht]]]};
IsHash:
PUBLIC
PROC [set: Set]
RETURNS [
BOOL]
~ {RETURN [set.class.HasMember = classes[variable].HasMember]};
HasMemByUpdate:
PROC [set: Set, elt: Value]
RETURNS [
BOOL] ~ {
ht: HashTable ~ NARROW[set.data.VA];
had: BOOL ← FALSE;
TestHas: PROC [has: BOOL] RETURNS [BOOL] ~ {RETURN [had ← has]};
HashUpdate[set, ht, elt, TestHas];
RETURN [had]};
HashScan:
PROC [set: Set,
Test: Tester, ro: RelOrder]
RETURNS [mv: MaybeValue ← noMaybe] = {
ht: HashTable ~ NARROW[set.data.VA];
Inhibit:
ENTRY
PROC [ht: HashTable] ~ {
ENABLE UNWIND => NULL;
IF set.class.data=$Frigid AND ht.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[AV[set.Refify]]];
ht.inhibitCount ← ht.inhibitCount + 1;
IF set.class=frozenClass THEN ht.frozenScans ← ht.frozenScans + 1;
};
Release:
ENTRY
PROC [ht: HashTable] ~ {
ENABLE UNWIND => NULL;
ht.inhibitCount ← ht.inhibitCount - 1;
IF set.class=frozenClass THEN ht.frozenScans ← ht.frozenScans - 1;
IF ht.inhibitCount#0 THEN RETURN;
WHILE ht.size > ht.sizeLimit DO ReHash[ht] ENDLOOP;
};
IF ro#no THEN RETURN DefaultScan[set, Test, ro];
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 {mv ← [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 IF node.rest#NIL THEN RETURN [node.rest, index];
{seq: REF Seq ~ ht.seq;
WHILE index > 0
DO
index ← index - 1;
node ← seq[index];
IF node#NIL THEN RETURN [node, index];
ENDLOOP;
RETURN [NIL, 0]}};
HashSize:
PROC [set: Set, limit:
EINT]
RETURNS [
EINT] = {
ht: HashTable ~ NARROW[set.data.VA];
EasySize:
ENTRY
PROC [ht: HashTable]
RETURNS [
EINT] ~ {
ENABLE UNWIND => NULL;
IF set.class.data=$Frigid AND ht.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[AV[set.Refify]]];
RETURN IS.IE[ht.size]};
RETURN EasySize[ht]};
LockedCopy:
ENTRY
PROC [set: Set, ht: HashTable]
RETURNS [new: HashTable] ~ {
ENABLE UNWIND => NULL;
IF set.class.data=$Frigid AND ht.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[AV[set.Refify]]];
{oldSeq: REF Seq ~ ht.seq;
newSeq: REF Seq ~ NEW [Seq[oldSeq.max]];
new ← NEW [HashTablePrivate ← ht^];
new.seq ← newSeq;
FOR i: SeqIndex
IN [0 .. oldSeq.max)
DO
start: Node ~ oldSeq[i];
IF start#
NIL
THEN {
tail: Node ← newSeq[i] ← LIST[start.first];
FOR from: Node ← start.rest, from.rest
WHILE from#
NIL
DO
this: Node ~ LIST[from.first];
tail ← tail.rest ← this;
ENDLOOP;
tail ← tail;
};
ENDLOOP;
new.inhibitCount ← new.freezeCount ← 0;
RETURN}};
HashCopy:
PROC [set: Set]
RETURNS [VarSet] ~ {
old: HashTable ~ NARROW[set.data.VA];
RETURN AsVar[[classes[variable], AV[LockedCopy[set, old]]]]};
HashInsulate:
PROC [set: Set]
RETURNS [UWSet] ~ {
old: HashTable ~ NARROW[set.data.VA];
RETURN AsUW[[classes[readonly], AV[old]]]};
HashValueOf:
PROC [set: Set]
RETURNS [ConstSet] ~ {
old: HashTable ~ NARROW[set.data.VA];
RETURN AsConst[[classes[constant], AV[LockedCopy[set, old]]]]};
HashFreeze:
PROC [set: Set]
RETURNS [ConstSet] ~ {
ht: HashTable ~ NARROW[set.data.VA];
LockedFreeze:
ENTRY
PROC [ht: HashTable] ~ {
ENABLE UNWIND => NULL;
ht.freezeCount ← ht.freezeCount + 1;
RETURN};
LockedFreeze[ht];
RETURN AsConst[[frozenClass, AV[ht]]]};
HashThaw:
PROC [set: Set] ~ {
ht: HashTable ~ NARROW[set.data.VA];
LockedThaw:
ENTRY
PROC [ht: HashTable] ~ {
ENABLE UNWIND => NULL;
IF ht.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[AV[set.Refify]]];
ht.freezeCount ← ht.freezeCount-1;
IF ht.freezeCount=0 AND ht.frozenScans>0 THEN RETURN WITH ERROR Error[unfrozen, LIST[AV[set.Refify]]];
RETURN};
LockedThaw[ht];
RETURN};
UpdateDecider: TYPE ~ PROC [BOOL] RETURNS [BOOL];
HashUpdate:
ENTRY
PROC [set: Set, ht: HashTable, val: Value,
Decide: UpdateDecider] ~ {
ENABLE UNWIND => NULL;
index: SeqIndex ~ ComputeIndex[ht, val];
prev: Node ← NIL;
IF set.class.data=$Frigid AND ht.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[AV[set.Refify]]];
FOR node: Node ← ht.seq[index], node.rest
WHILE node #
NIL
DO
IF ht.space.SEqual[val, node.first]
THEN {
have: BOOL ~ Decide[TRUE];
IF have THEN NULL
ELSE IF ht.freezeCount#0 THEN RETURN WITH ERROR Error[frozen, LIST[AV[set.Refify]]]
ELSE {
IF prev=NIL THEN ht.seq[index] ← node.rest ELSE prev.rest ← node.rest;
ht.size ← ht.size - 1;
};
RETURN;
};
prev ← node;
ENDLOOP;
{have: BOOL ~ Decide[FALSE];
IF have
THEN {
IF ht.freezeCount#0 THEN RETURN WITH ERROR Error[frozen, LIST[AV[set.Refify]]];
ht.seq[index] ← CONS[val, ht.seq[index]];
IF (ht.size ← ht.size + 1) > ht.sizeLimit AND ht.inhibitCount = 0 THEN ReHash[ht];
};
RETURN}};
AddSetByUpdate:
PROC [set, other: Set]
RETURNS [new: SomeAll ← []] ~ {
ht: HashTable ~ NARROW[set.data.VA];
AddElt:
PROC [elt: Value] ~ {
DecideToAdd:
PROC [has:
BOOL]
RETURNS [
BOOL] ~ {
IF has THEN new.all ← FALSE ELSE new.some ← TRUE;
RETURN [TRUE]};
HashUpdate[set, ht, elt, DecideToAdd];
RETURN};
IF set.MutabilityOf[]#variable THEN set.Complain[notVariable];
other.Enumerate[AddElt];
RETURN};
RemSetByUpdate:
PROC [set, other: Set]
RETURNS [had: SomeAll ← []] ~ {
ht: HashTable ~ NARROW[set.data.VA];
RemElt:
PROC [elt: Value] ~ {
DecideToRem:
PROC [has:
BOOL]
RETURNS [
BOOL] ~ {
IF has THEN had.some ← TRUE ELSE had.all ← FALSE;
RETURN [FALSE]};
HashUpdate[set, ht, elt, DecideToRem];
RETURN};
IF set.MutabilityOf[]#variable THEN set.Complain[notVariable];
IF other=set THEN RETURN Clear[set, ht];
other.Enumerate[RemElt];
RETURN};
Clear:
ENTRY
PROC [set: Set, ht: HashTable]
RETURNS [SomeAll] ~ {
ENABLE UNWIND => NULL;
seq: REF Seq ~ ht.seq;
IF ht.freezeCount#0 THEN RETURN WITH ERROR Error[frozen, LIST[AV[set.Refify]]];
IF ht.size=0 THEN RETURN [[some: FALSE, all: TRUE]];
ht.size ← 0;
FOR i: SeqIndex IN [0 .. seq.max) DO seq[i] ← NIL ENDLOOP;
RETURN [[some: TRUE, all: TRUE]]};
HashSpaceOf:
PROC [set: Set]
RETURNS [Space] ~ {
ht: HashTable ~ NARROW[set.data.VA];
RETURN [ht.space]};
ReHash:
INTERNAL
PROC [ht: HashTable] ~ {
oldSeq: REF Seq = ht.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 {ht.sizeLimit ← LAST[INT]; RETURN};
ht.sizeLimit ← newMod;
ht.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[ht, cur.first];
next ← cur.rest;
cur.rest ← newSeq[index];
newSeq[index] ← cur;
ENDLOOP;
IF next # NIL THEN ERROR;
ENDLOOP;
RETURN};
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];
Start:
PROC ~ {
FOR mut: Mutability
IN Mutability
DO
classes[mut] ← CreateClass[[
HasMember: HasMemByUpdate,
Scan: HashScan,
Size: HashSize,
Copy: HashCopy,
Insulate: IF mut=variable THEN HashInsulate ELSE NIL,
ValueOf: IF mut#constant THEN HashValueOf ELSE NIL,
Freeze: IF mut=variable THEN HashFreeze ELSE NIL,
Thaw: IF mut=variable THEN HashThaw ELSE NIL,
AddSet: AddSetByUpdate,
RemSet: RemSetByUpdate,
SpaceOf: HashSpaceOf,
mutability: mut]];
ENDLOOP;
RETURN};
Start[];
END.