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. bValueHashTablesImpl.Mesa Last tweaked by Mike Spreitzer on December 12, 1987 4:56:28 pm PST Κ2– "cedar" style˜code™K™B—K˜KšΟk œ,˜5K˜šΟnœœ˜"Kšœœ˜Kšœ˜K˜—K˜Kšœœ žœ'˜AK˜Kšž œœœ˜K˜Kšœ œœ˜'š œœœ œœ˜2K˜ Kšœœ˜'Kšœ œœ˜Kšœœ˜ Kšœ˜—K˜Kšœ œœ˜Kš œœœ œœ˜;Kšœœœ˜K˜šž œœœœ˜LKšœ$œ ˜:K˜—K˜šžœœœœ˜>šœœ˜K˜ K˜Kšœœ˜K˜—K˜—K˜š žœœœœœœ˜9Kšœœœ˜Kš œœœœœ ˜1Kšœ ˜Kšœ˜—K˜šžœœœœ˜SKšžœœœœ ˜JKšœœœ˜+Kšœ˜—K˜šžœœœ"œ˜RKš žœœœœœ ˜MKšœ˜K˜—K˜š žœœœœœœ˜PKšžœœœ"œ ˜ZKšœœœ˜+K˜—K˜š žœœœœžœ œ˜dKšœœœ˜Kšœ(˜(Kšœ œ˜K˜ šœ'œœ˜=šœœ6œ˜VKšœœ˜4Kšœ œœ˜6šœ˜Kšœœœœ˜FK˜K˜—Kšœ˜K˜—K˜ Kšœ˜—Kšœ#˜#šœ œ˜Kšœœ˜3Kšœ(œœ˜YK˜—K˜—K˜š žœœœžœ œ3˜jšžœœœ˜'Kšœœœ˜Kšœ&˜&K˜—šžœœœ˜'Kšœœœ˜K˜ Kšœ*˜*Kšœœœ˜#Kšœœœ˜@K˜—Kš œœœœœ ˜1Kšœ ˜ Kšœœœ˜Kšœ œ˜Kšœœ˜š˜Kšœ)˜)Kšœœœœ˜Kšœœœœ˜9Kšœ˜—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šœ˜—…—άp