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: 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 [(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. ZHashTablesImpl.Mesa Last tweaked by Mike Spreitzer on May 15, 1987 10:07:25 am PDT Κ?– "cedar" style˜code™K™>—K˜KšΟk œ*˜3K˜šΟnœœ˜Kšœœ˜Kšœ˜$Kšœ ˜K˜—K˜Kšœœ*˜4K˜Kšž œœœ˜K˜Kšœ œœ˜'š œœœ œœ˜2K˜ Kšœœ˜'Kšœ œœ˜Kšœœ˜ Kšœ˜—K˜Kšœ œœ˜Kš œœœ œœ˜;Kšœœœ˜K˜šž œœœœ˜LKš œœœœœ$œ ˜iK˜—K˜šžœœœœ˜>šœœ˜K˜ K˜Kšœœ˜K˜—K˜—K˜š žœœœœœœ˜9Kšœœœ˜Kš œœœœœ ˜1Kšœ ˜Kšœ˜—K˜šžœœœœ˜IKšžœœœ&˜LKšœœœ˜+K˜—K˜šžœœœ"œ˜RKšžœœœœ˜OKšœ˜K˜—K˜š žœœœœœ˜HKšžœœœ6˜\Kšœœœ˜+K˜—K˜š žœœœœžœ œ˜dKšœœœ˜Kšœ(˜(Kšœ œ˜K˜ šœ'œœ˜=š œœœœ7œ˜oKšœœ˜4šœ œœ˜4Kšœœœœ˜FK˜K˜—Kšœ˜K˜—K˜ Kšœ˜—Kšœ#˜#šœ œ˜Kšœœ ˜4Kšœ(œœ˜YK˜—K˜—K˜š žœœœžœ œ%˜\šžœœœ˜'Kšœœœ˜Kšœ&˜&K˜—šžœœœ˜'Kšœœœ˜K˜ Kšœ*˜*Kšœœœ˜#Kšœœœ˜@K˜—šž œœ˜Kšœ œ˜Kšœœ˜š˜Kšœ)˜)Kšœœœœ˜Kšœœœœ˜;Kšœ˜—K˜—Kš œœœœœ ˜1Kšœ˜Kšœ ˜ Kšœ œ˜#Kšœ ˜ Kšœ˜—K˜š žœœœ$œœœ˜]Kšœœœ˜šœ˜ Kšœ˜šœ˜K˜Kšœœœœ˜(K˜——šœ ˜Kšœ˜Kšœ˜Kšœœœœ˜(Kšœ˜—Kšœœ˜K˜—K˜šžœœœœ˜CKšœœ˜Kšœœ˜Kšœœ˜ Kšœœ˜Kšœœ ˜šœ˜Kšœ˜šœ˜Kšœ˜Kšœœœ˜Kšœ˜Kšœ˜——Kš œœœœœ˜Fšœœ˜K˜K˜Kšœ˜Kšœœ˜K˜—šœ œ˜'Kšœ œ˜šœœœ˜2Kšœ5˜5K˜Kšœ˜Kšœ˜Kšœ˜—Kšœœœœ˜Kšœ˜—K˜—K˜šœœ˜Kšœ œœ˜/Kšœ œ˜—šœ œœœ˜7Kšœs˜s—Kšœ˜—…—0Ι