HashCollectionsPrivateImpl.Mesa
Last tweaked by Mike Spreitzer on September 21, 1987 11:41:06 am PDT
DIRECTORY Basics, HashCollectionsPrivate, Collections, PrincOps, Rope;
HashCollectionsPrivateImpl:
CEDAR
MONITOR
LOCKS
NARROW[coll.data, HashColl]
USING coll: Collection
IMPORTS Collections
EXPORTS HashCollectionsPrivate
=
BEGIN OPEN HashCollectionsPrivate, Collections;
classes:
PUBLIC
ARRAY Mutability
OF CollectionClass ~ [
variable: CreateClass[[
HasMember: HasMember,
Scan: Scan,
Size: Size,
Copy: Copy,
Insulate: Insulate,
Freeze: Freeze,
Thaw: Thaw,
AddColl: AddColl,
RemoveColl: RemoveColl,
SpaceOf: SpaceOf,
mayDuplicate: FALSE,
mutability: variable,
data: NIL]],
readonly: CreateClass[[
HasMember: HasMember,
Scan: Scan,
Size: Size,
Copy: Copy,
SpaceOf: SpaceOf,
mayDuplicate: FALSE,
mutability: readonly,
data: NIL]],
constant: CreateClass[[
HasMember: HasMember,
Scan: Scan,
Size: Size,
Copy: Copy,
SpaceOf: SpaceOf,
mayDuplicate: FALSE,
mutability: constant,
data: $Frigid]]
];
ComputeIndex:
PROC [hc: HashColl, elt: Value]
RETURNS [SeqIndex]
~ INLINE {RETURN [(IF hc.space.Hash=NIL THEN HashRefI[elt] ELSE hc.space.Hash[hc.space.data, elt]) MOD hc.elts.max];
};
Frigid:
PROC [class: CollectionClass]
RETURNS [
BOOL]
~ INLINE {RETURN [class.data = $Frigid]};
HasMember:
ENTRY
PROC [coll: Collection, elt: Value]
RETURNS [
BOOL] ~ {
ENABLE UNWIND => NULL;
hc: HashColl ~ NARROW[coll.data];
frigid: BOOL ~ Frigid[coll.class];
index: SeqIndex ~ ComputeIndex[hc, elt];
IF frigid AND hc.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[Refify[coll]]];
FOR node:
LOV ← hc.elts[index], node.rest
WHILE node #
NIL
DO
v: Value ~ node.first;
IF hc.space.SpaceEqual[v, elt] THEN RETURN [TRUE];
ENDLOOP;
RETURN [FALSE];
};
Scan:
PROC [coll: Collection,
Test: Tester, bkwd:
BOOL]
RETURNS [mv: MaybeValue ← noMaybe] ~ {
hc: HashColl ~ NARROW[coll.data];
frigid: BOOL ~ Frigid[coll.class];
Inhibit:
ENTRY
PROC [coll: Collection] ~ {
ENABLE UNWIND => NULL;
IF frigid AND hc.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[Refify[coll]]];
hc.inhibitCount ← hc.inhibitCount + 1;
};
Release:
ENTRY
PROC [coll: Collection] ~ {
ENABLE UNWIND => NULL;
hc.inhibitCount ← hc.inhibitCount - 1;
IF hc.inhibitCount#0 THEN RETURN;
WHILE hc.size > hc.sizeLimit DO ReHash[hc] ENDLOOP;
};
Enumerate:
PROC ~ {
node: LOV ← NIL;
index: CARDINAL ← 0;
DO
[node, index] ← GetNext[coll, node, index];
IF node = NIL THEN EXIT;
IF Test[node.first].pass THEN {mv ← [TRUE, node.first]; RETURN};
ENDLOOP;
};
IF bkwd THEN RETURN DefaultScan[coll, Test, bkwd];
Inhibit[coll];
Enumerate[! UNWIND => Release[coll]];
Release[coll];
RETURN};
GetNext:
ENTRY
PROC [coll: Collection, node:
LOV, index:
CARDINAL]
RETURNS [
LOV,
CARDINAL] = {
ENABLE UNWIND => NULL;
hc: HashColl ~ NARROW[coll.data];
IF node =
NIL
THEN index ← hc.elts.max
ELSE {
node ← node.rest;
IF node # NIL THEN RETURN [node, index];
};
WHILE index > 0
DO
index ← index - 1;
node ← hc.elts[index];
IF node # NIL THEN RETURN [node, index];
ENDLOOP;
RETURN [NIL, 0];
};
Size:
ENTRY
PROC [coll: Collection, limit:
LNAT ←
LNAT.
LAST]
RETURNS [
INT] = {
ENABLE UNWIND => NULL;
hc: HashColl ~ NARROW[coll.data];
frigid: BOOL ~ Frigid[coll.class];
IF frigid AND hc.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[Refify[coll]]];
RETURN [hc.size];
};
AddColl:
PROC [coll, other: Collection, where: Where]
RETURNS [someNew, allNew:
BOOL] ~ {
hc: HashColl ~ NARROW[coll.data];
frigid: BOOL ~ Frigid[coll.class];
EachEltAdd: PROC [elt: Value] ~ {Addit[coll, elt]};
Addit:
ENTRY
PROC [coll: Collection, elt: Value] ~ {
ENABLE UNWIND => NULL;
index: SeqIndex ~ ComputeIndex[hc, elt];
IF frigid AND hc.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[Refify[coll]]];
FOR node:
LOV ← hc.elts[index], node.rest
WHILE node #
NIL
DO
v: Value ~ node.first;
IF hc.space.SpaceEqual[v, elt] THEN {allNew ← FALSE; RETURN};
ENDLOOP;
hc.elts[index] ← CONS[elt, hc.elts[index]];
IF (hc.size ← hc.size + 1) > hc.sizeLimit AND hc.inhibitCount = 0 THEN ReHash[hc];
someNew ← TRUE;
};
someNew ← FALSE;
allNew ← TRUE;
IF hc.freezeCount#0 THEN coll.Complain[frozen];
other.Enumerate[EachEltAdd];
RETURN;
};
RemoveColl:
PROC [coll, other: Collection, style: RemoveStyle]
RETURNS [hadSome, hadAll:
BOOL] ~ {
hc: HashColl ~ NARROW[coll.data];
frigid: BOOL ~ Frigid[coll.class];
EachEltRem: PROC [elt: Value] ~ {Remit[coll, elt]};
Remit:
ENTRY
PROC [coll: Collection, elt: Value] ~ {
ENABLE UNWIND => NULL;
index: SeqIndex ~ ComputeIndex[hc, elt];
prev: LOV ← NIL;
IF frigid AND hc.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[Refify[coll]]];
FOR node:
LOV ← hc.elts[index], node.rest
WHILE node #
NIL
DO
v: Value ~ node.first;
IF hc.space.SpaceEqual[v, elt]
THEN {
hadSome ← TRUE;
IF prev=NIL THEN hc.elts[index] ← node.rest ELSE prev.rest ← node.rest;
hc.size ← hc.size-1;
RETURN};
prev ← node;
ENDLOOP;
hadAll ← FALSE;
};
hadSome ← FALSE;
hadAll ← TRUE;
IF hc.freezeCount#0 THEN coll.Complain[frozen];
other.Enumerate[EachEltRem];
RETURN;
};
Copy:
PROC [coll: Collection]
RETURNS [copy: VarColl] ~ {
copy ← CreateHashCopy[coll];
};
Insulate:
PROC [coll: Collection]
RETURNS [UWColl] ~ {
hc: HashColl ~ NARROW[coll.data];
RETURN [AsUW[[classes[readonly], coll.data]]];
};
Freeze:
ENTRY
PROC [coll: Collection]
RETURNS [const: ConstColl] ~ {
ENABLE UNWIND => NULL;
hc: HashColl ~ NARROW[coll.data];
IF coll.MutabilityOf # variable THEN RETURN WITH ERROR Error[notVariable, LIST[coll.Refify]];
hc.freezeCount ← hc.freezeCount + 1;
RETURN [AsConst[[classes[constant], coll.data]]];
};
Thaw:
ENTRY
PROC [coll: Collection] ~ {
ENABLE UNWIND => NULL;
hc: HashColl ~ NARROW[coll.data];
IF coll.MutabilityOf # variable THEN RETURN WITH ERROR Error[notVariable, LIST[coll.Refify]];
IF hc.freezeCount=0 THEN RETURN WITH ERROR Error["too many thaws", LIST[Refify[coll]]];
hc.freezeCount ← hc.freezeCount - 1;
};
SpaceOf:
ENTRY
PROC [coll: Collection]
RETURNS [Space] ~ {
ENABLE UNWIND => NULL;
hc: HashColl ~ NARROW[coll.data];
frigid: BOOL ~ Frigid[coll.class];
IF frigid AND hc.freezeCount=0 THEN RETURN WITH ERROR Error[unfrozen, LIST[Refify[coll]]];
RETURN [hc.space];
};
ReHash:
INTERNAL
PROC [hc: HashColl] = {
oldData: REF Seq = hc.elts;
newData: REF Seq;
seek: CARDINAL = hc.elts.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 = hc.elts.max THEN {hc.sizeLimit ← LAST[INT]; RETURN};
hc.sizeLimit ← newMod;
hc.elts ← newData ← NEW [Seq[newMod]];
FOR i: SeqIndex
IN [0 .. oldData.max)
DO
next: LOV ← NIL;
FOR cur:
LOV ← oldData[i], next
WHILE cur #
NIL
DO
index: SeqIndex ← ComputeIndex[hc, cur.first];
next ← cur.rest;
cur.rest ← newData[index];
newData[index] ← cur;
ENDLOOP;
IF next # NIL THEN ERROR;
ENDLOOP;
};
PrimeTableSize:
NAT = 14;
highPrime: CARDINAL[0..LAST[SeqIndex]] = 32749;
primeTable:
ARRAY [0 .. PrimeTableSize)
OF
CARDINAL = [
00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, highPrime];
END.