DIRECTORY YggEnvironment USING [], YggInternal USING [], Basics, YggConcreteTransID USING [TransID, Equal], YggTransactionMap USING [EnumProc], YggWorker USING [Handle, Object], YggWorkerControl USING []; YggWorkerMapImpl: CEDAR MONITOR IMPORTS Basics, YggConcreteTransID EXPORTS YggEnvironment, YggInternal, YggTransactionMap, YggWorkerControl = BEGIN Handle: TYPE = YggWorker.Handle; TransID: PUBLIC TYPE = YggConcreteTransID.TransID; TransObject: PUBLIC TYPE = YggWorker.Object; Initialize: PUBLIC ENTRY PROC [hashArraySize: NAT] = { InitializeHashTable [ numHashSlotsDesired: hashArraySize, hashHandle: NEW[YggWorker.Object _ [ timeOfLastStartWork: TRASH]]]; }; Register: PUBLIC ENTRY PROC [self: Handle] RETURNS [alreadyRegistered: BOOL] = { alreadyRegistered _ FALSE; Insert[self ! HashPkgDuplicateKey => { alreadyRegistered _ TRUE; CONTINUE }]; RETURN [alreadyRegistered]; }; GetHandle: PUBLIC ENTRY PROC [transID: TransID] RETURNS [handle: Handle] = { RETURN[Lookup[transID]]; }; Unregister: PUBLIC ENTRY PROC [self: Handle] = { Delete[self]; self.next _ NIL; }; LockedEnumerate: PUBLIC ENTRY PROC [proc: YggTransactionMap.EnumProc] = { EnumerateWithProc[proc]; }; UnlockedEnumerate: PUBLIC PROC [proc: YggTransactionMap.EnumProc] = { Next: ENTRY PROC [h: Handle] RETURNS [Handle] = INLINE { RETURN [EnumerateNext[h]]; }; h: Handle _ NIL; DO IF (h _ Next[h]) = NIL OR proc[h].stop THEN EXIT; ENDLOOP; }; HashHandle: TYPE = Handle; Key: TYPE = TransID; ClientHashInit: PROC [numHashSlotsDesired: NAT] RETURNS [numHashSlotsAllowed: NAT] = { hashMask _ numHashSlotsDesired - 1; IF Basics.BITAND[hashMask, numHashSlotsDesired] # 0 THEN ERROR HashPkgCallerProgrammingError; RETURN [numHashSlotsDesired] }; hashMask: WORD; ClientHash: INTERNAL PROC [hashHandle: HashHandle] RETURNS [NAT--[0..range)--] = INLINE { RETURN [Basics.BITAND[hashMask, LOOPHOLE[ LOOPHOLE[hashHandle.transID, YggConcreteTransID.TransID].randomBits, Basics.LongNumber.pair].lo]]; }; ClientEqualKeys: INTERNAL PROC [hashHandle1, hashHandle2: HashHandle] RETURNS [equal: BOOL] = INLINE { RETURN [YggConcreteTransID.Equal[hashHandle1.transID, hashHandle2.transID]]; }; ClientSetKey: INTERNAL PROC [hashHandle: HashHandle, key: Key] = INLINE { hashHandle.transID _ key; }; hashSlots: REF HashSlots _ NIL; HashSlots: TYPE = RECORD[SEQUENCE nSlots: NAT OF HashHandle]; numHashSlots: NAT _ 0; -- boy, will they be sorry if they don't init this package. lookupHashHandle: HashHandle _ NIL; -- for the "package's" use only. HashPkgCallerProgrammingError: ERROR = CODE; -- various fatal conditions. HashPkgDuplicateKey: ERROR = CODE; -- from Insert. InitializeHashTable: INTERNAL PROCEDURE[numHashSlotsDesired: NAT, hashHandle: HashHandle] = BEGIN -- errors: HashPkgCallerProgrammingError (numHashSlotsDesired = 0). numHashSlots _ ClientHashInit[numHashSlotsDesired]; IF numHashSlots = 0 THEN ERROR HashPkgCallerProgrammingError; lookupHashHandle _ hashHandle; hashSlots _ NEW[HashSlots[numHashSlots]]; FOR index: NAT IN [0..numHashSlots) DO hashSlots[index] _ NIL; ENDLOOP; END; Insert: INTERNAL PROCEDURE[hashHandle: HashHandle] = INLINE BEGIN -- errors: HashPkgDuplicateKey. index: NAT _ ClientHash[hashHandle]; FOR newHashHandle: HashHandle _ hashSlots[index], newHashHandle.next UNTIL newHashHandle = NIL DO IF ClientEqualKeys[newHashHandle, hashHandle] THEN ERROR HashPkgDuplicateKey; ENDLOOP; hashHandle.next _ hashSlots[index]; hashSlots[index] _ hashHandle; END; Lookup: INTERNAL PROCEDURE[key: Key] RETURNS [hashHandle: HashHandle] = INLINE BEGIN -- returns hashHandle = NIL if not found. ClientSetKey[lookupHashHandle, key]; FOR hashHandle _ hashSlots[ClientHash[lookupHashHandle]], hashHandle.next UNTIL hashHandle = NIL DO IF ClientEqualKeys[hashHandle, lookupHashHandle] THEN RETURN; ENDLOOP; RETURN[NIL]; END; Delete: INTERNAL PROCEDURE[hashHandle: HashHandle] = INLINE BEGIN -- errors: HashPkgCallerProgrammingError (not found). index: NAT _ ClientHash[hashHandle]; prevHashHandle: HashHandle _ NIL; FOR newHashHandle: HashHandle _ hashSlots[index], newHashHandle.next UNTIL newHashHandle = NIL DO IF ClientEqualKeys[newHashHandle, hashHandle] THEN EXIT; prevHashHandle _ newHashHandle; REPEAT FINISHED => ERROR HashPkgCallerProgrammingError; ENDLOOP; IF prevHashHandle = NIL THEN hashSlots[index] _ hashHandle.next ELSE prevHashHandle.next _ hashHandle.next; hashHandle.next _ NIL; END; EnumerateNext: INTERNAL PROCEDURE[prevHashHandle: HashHandle] RETURNS [hashHandle: HashHandle] = BEGIN -- errors: none. index: NAT; IF prevHashHandle = NIL THEN index _ 0 ELSE BEGIN index _ ClientHash[prevHashHandle]; FOR hashHandle _ hashSlots[index], hashHandle.next UNTIL hashHandle = NIL DO IF ClientEqualKeys[hashHandle, prevHashHandle] THEN GOTO found; REPEAT found => BEGIN IF hashHandle.next # NIL THEN RETURN[hashHandle.next]; index _ index + 1; END; ENDLOOP; END; UNTIL index >= numHashSlots DO IF hashSlots[index] # NIL THEN RETURN[hashSlots[index]]; index _ index + 1; ENDLOOP; RETURN[NIL]; END; EnumerateWithProc: INTERNAL PROCEDURE[proc: PROCEDURE[hashHandle: HashHandle] RETURNS[stop: BOOLEAN]] = BEGIN -- errors: none. FOR index: NAT IN [0..numHashSlots) DO FOR hashHandle: HashHandle _ hashSlots[index], hashHandle.next UNTIL hashHandle = NIL DO IF proc[hashHandle] THEN RETURN; ENDLOOP; ENDLOOP; END; END.--WorkerMapImpl CHANGE LOG Changed by MBrown on February 9, 1983 11:54 am YggWorkerMapImpl.mesa Copyright Ó 1985, 1988 by Xerox Corporation. All rights reserved. Exports YggTransactionMap global operations: Module initialization and Creating, finding, and deleting Handles Last edited by Taft on 1-Feb-82 10:14:46 MBrown on January 30, 1984 11:38:56 am PST Carl Hauser, February 24, 1987 4:57:29 pm PST Bob Hagmann May 2, 1988 2:30:59 pm PDT YggEnvironment.TransID. YggInternal.TransObject. Module initialization YggWorkerControl.Initialize Creating, finding, and deleting Handles If a worker object with TransID self.trans exists, return alreadyRegistered = TRUE. Otherwise insert self into the transactionmap and return alreadyRegistered = FALSE. Client-supplied parameters to hash package begin here: Client-supplied parameters to hash package end here. Hash table package. Explanation of client-supplied parameters: The procedure ClientHashInit is called during hash table initialization, to allow the hash function to precompute values based on the range and to make any small adjustments to the range that are necessary. HashHandle must: be a REF type. contain a field "next" of type HashHandle, under the exclusive control of the hash package. Key is an arbitrary type. SetKey sets the "key value" associated with a HashHandle. The key value must not change between the time the handle is Inserted into the table and the time it is deleted from the table. Hash must be a function of the key value of the parameter "hashHandle". EqualKeys must be the equality relation on the key values of the parameters "hashHandle1" and "hashHandle2". Interface description: InitializeHashTable: INTERNAL PROCEDURE[numHashSlotsDesired: NAT, hashTableZone: ZONE, hashHandle: HashHandle]; errors: HashPkgCallerProgrammingError (numHashSlotsDesired = 0). Insert: INTERNAL PROCEDURE[hashHandle: HashHandle]; errors: HashPkgDuplicateKey. Lookup: INTERNAL PROCEDURE[key: Key] RETURNS [hashHandle: HashHandle]; returns hashHandle = NIL if not found. Delete: INTERNAL PROCEDURE[hashHandle: HashHandle]; errors: HashPkgCallerProgrammingError (not found). EnumerateNext: INTERNAL PROCEDURE[prevHashHandle: HashHandle] RETURNS [hashHandle: HashHandle]; errors: none. prevHashHandle = NIL starts the enumeration, returned hashHandle = NIL is the end of the enumeration. This procedure guarantees that any hashHandle in existence throughout the entire enumeration will be seen. Other handles may or not not be seen. HashHandles may be seen more than once. EnumerateWithProc: INTERNAL PROCEDURE[proc: PROCEDURE[hashHandle: HashHandle] RETURNS[stop: BOOLEAN]]; errors: none. start of invariant hash package code: The INTERNAL procedures below expect to be called from a client procedure holding the module monitor lock, which protects the following data structures: errors: prevHashHandle = NIL starts the enumeration, returned hashHandle = NIL is the end of the enumeration. This procedure guarantees that any hashHandle in existence throughout the entire enumeration will be seen. Other handles may or not not be seen. HashHandles may be seen more than once. end of invariant hash package code. Change Unregister to NOT set continueWorker _ NIL. Hauser, March 8, 1985 11:17:11 am PST Nodified, added copyright. Ê «˜šœ™IcodešœB™B—JšœY™YJšœ™šœ™Jšœ™Jšœ*™*K™-K™&—˜šÏk ˜ Jšœœ˜Jšœœ˜J˜Jšœœ˜*Jšœœ˜#Jšœ œ˜!Jšœœ˜J˜——šœ ˜š˜J˜Jšœ˜—š˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜—Jšœ˜Jšœœ˜ J˜šœ œœ˜2Jšœ™—šœ œœ˜,Jšœ™J˜J˜—Jšœ™J˜š Ïn œœœœœ˜6Jšœ™˜J˜#šœœ˜$Jšœœ˜——J˜J˜J˜—Jšœ'™'J˜šžœœœœœœ˜PJšœS™SJšœS™SJšœœ˜Jšœ;œœ˜MJšœ˜J˜J˜—š ž œœœœœ˜LJšœ˜J˜J˜—šž œœœœ˜0J˜ Jšœœ˜J˜J˜—šžœœœœ'˜IJ˜J˜J˜—šžœœœ'˜Eš žœœœ œœ˜8Jšœ˜J˜—Jšœœ˜š˜Jš œœœœœ˜1Jšœ˜—J˜——J˜Jšœ6™6J˜Jšœœ ˜Jšœœ˜J˜šžœœœ˜/Jšœœ˜&J˜#šœœ$˜8Jšœ˜$—Jšœ˜J˜—Jšœ œ˜J˜šž œœœ˜2JšœÏcœœ˜&šœ œ ˜šœ˜ Jšœ<˜DJ˜——J˜J˜—šžœœœ'˜EJšœ œœ˜ JšœF˜LJ˜J˜—šžœœœ&œ˜IJ˜J˜J˜—Jšœ4™4J˜Jšœ™J˜Jšœ*™*J˜JšœZ™ZJšœU™UJšœ™Jšœ™Jšœ™JšœM™MJšœ ™ Jšœ™JšœM™MJšœN™NJšœ™JšœG™GJšœK™KJšœ ™ J˜J˜Jšœ™J˜JšœP™PJšœ™Jšœ@™@J˜Jšœ3™3Jšœ™J˜JšœF™FJšœ&™&J˜Jšœ3™3Jšœ2™2J˜JšœE™EJšœ™Jšœ ™ JšœQ™QJšœZ™ZJšœX™XJšœ™J˜JšœM™MJšœ™Jšœ ™ J˜J˜Jšœ%™%J˜Jšœ˜™˜J˜Jšœœ œ˜Jšœœœœ œœ ˜=J˜JšœœŸ;˜SJšœœŸ ˜DJ˜Jšœ™J˜JšœœœŸ˜IJšœœœŸ˜2J˜J˜šžœœ œœ˜[šœŸC˜JJ˜3Jšœœœ˜=J˜Jšœœ˜)šœœœ˜#Jšœœœ˜#—Jšœ˜J˜J˜——šžœœ œ˜;JšœŸ˜&Jšœœ˜$JšœA˜Dšœ˜Jš˜šœ+˜-Jšœœ˜—Jšœ˜—J˜$J˜Jšœ˜J˜J˜—š žœœ œœ˜NJšœŸ)˜0J˜$JšœF˜Išœ˜Jšœœ/œœ˜@Jšœ˜—Jšœœ˜Jšœ˜J˜J˜—šžœœ œ˜;JšœŸ5˜šœ˜Jšœœœœ˜#Jšœ˜—Jšœ˜—Jšœ˜J˜——Jšœ#™#˜JšœŸ˜J˜—Jšœ˜ J˜J˜.Jšœ2™2J˜™%K™—K™—…—@+‹