<> <> <> <> <> <> <> <> <> <> DIRECTORY YggEnvironment, YggInternal, Basics, BasicTime, YggDID, YggFileLock, YggLock, YggLockControl, YggLockInternal, YggDummyProcess, Rope, YggTransactionMap; YggLockCoreImpl: CEDAR MONITOR <> IMPORTS Basics, BasicTime, YggFileLock, YggDID, YggDummyProcess, Rope, YggTransactionMap, YggLockInternal EXPORTS YggDID, YggInternal, YggLock, YggLockControl, YggLockInternal = BEGIN DID: PUBLIC TYPE ~ REF DIDRep; DIDRep: PUBLIC TYPE ~ Rope.ROPE; <> LockID: TYPE = YggLock.LockID; nullLockID: LockID = YggLock.nullLockID; LockMode: TYPE = YggLock.LockMode; ModeReleasableSet: TYPE = YggLock.ModeReleasableSet; Lock: TYPE = YggLockInternal.Lock; LockRep: TYPE = YggLockInternal.LockRep; Header: TYPE = YggLockInternal.Header; Request: TYPE = YggLockInternal.Request; GrantedRequest: TYPE = YggLockInternal.GrantedRequest; WaitingRequest: TYPE = YggLockInternal.WaitingRequest; LockTransHeader: TYPE = YggLockInternal.LockTransHeader; LockTransHeaderObject: PUBLIC TYPE = YggLockInternal.LockRep.request.transHeader; <> Failed: PUBLIC ERROR [why: YggEnvironment.LockFailure] = CODE; <> Error: PUBLIC ERROR [YggLock.ErrorType] = CODE; <> TransAborting: PUBLIC ERROR = CODE; <> Compat: PUBLIC ARRAY LockMode OF PACKED ARRAY LockMode OF BOOL _ [ <> none: [none: TRUE, read: TRUE, update: TRUE, write: TRUE, readIntendUpdate: TRUE, readIntendWrite: TRUE, intendRead: TRUE, intendUpdate: TRUE, intendWrite: TRUE], read: [none: TRUE, read: TRUE, update: TRUE, write: FALSE, readIntendUpdate: TRUE, readIntendWrite: FALSE, intendRead: TRUE, intendUpdate: TRUE, intendWrite: FALSE], update: [none: TRUE, read: TRUE, update: FALSE, write: FALSE, readIntendUpdate: FALSE, readIntendWrite: FALSE, intendRead: TRUE, intendUpdate: FALSE, intendWrite: FALSE], write: [none: TRUE, read: FALSE, update: FALSE, write: FALSE, readIntendUpdate: FALSE, readIntendWrite: FALSE, intendRead: FALSE, intendUpdate: FALSE, intendWrite: FALSE], readIntendUpdate: [none: TRUE, read: TRUE, update: FALSE, write: FALSE, readIntendUpdate: FALSE, readIntendWrite: FALSE, intendRead: TRUE, intendUpdate: TRUE, intendWrite: FALSE], readIntendWrite: [none: TRUE, read: FALSE, update: FALSE, write: FALSE, readIntendUpdate: FALSE, readIntendWrite: FALSE, intendRead: TRUE, intendUpdate: TRUE, intendWrite: FALSE], intendRead: [none: TRUE, read: TRUE, update: TRUE, write: FALSE, readIntendUpdate: TRUE, readIntendWrite: TRUE, intendRead: TRUE, intendUpdate: TRUE, intendWrite: TRUE], intendUpdate: [none: TRUE, read: TRUE, update: FALSE, write: FALSE, readIntendUpdate: TRUE, readIntendWrite: TRUE, intendRead: TRUE, intendUpdate: TRUE, intendWrite: TRUE], intendWrite: [none: TRUE, read: FALSE, update: FALSE, write: FALSE, readIntendUpdate: FALSE, readIntendWrite: FALSE, intendRead: TRUE, intendUpdate: TRUE, intendWrite: TRUE]]; Sup: PUBLIC ARRAY LockMode OF PACKED ARRAY LockMode OF LockMode _ [ <> none: [none: none, read: read, update: update, write: write, readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite, intendRead: intendRead, intendUpdate: intendUpdate, intendWrite: intendWrite], read: [none: read, read: read, update: update, write: write, readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite, intendRead: read, intendUpdate: readIntendUpdate, intendWrite: readIntendWrite], update: [none: update, read: update, update: update, write: write, readIntendUpdate: update, readIntendWrite: update, intendRead: update, intendUpdate: update, intendWrite: update], write: [none: write, read: write, update: write, write: write, readIntendUpdate: write, readIntendWrite: write, intendRead: write, intendUpdate: write, intendWrite: write], readIntendUpdate: [none: readIntendUpdate, read: readIntendUpdate, update: update, write: write, readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite, intendRead: readIntendUpdate, intendUpdate: readIntendUpdate, intendWrite: readIntendWrite], readIntendWrite: [none: readIntendWrite, read: readIntendWrite, update: update, write: write, readIntendUpdate: readIntendWrite, readIntendWrite: readIntendWrite, intendRead: readIntendWrite, intendUpdate: readIntendWrite, intendWrite: readIntendWrite], intendRead: [none: intendRead, read: read, update: update, write: write, readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite, intendRead: intendRead, intendUpdate: intendUpdate, intendWrite: intendWrite], intendUpdate: [ none: intendUpdate, read: readIntendUpdate, update: update, write: write, readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite, intendRead: intendUpdate, intendUpdate: intendUpdate, intendWrite: intendWrite], intendWrite: [ none: intendWrite, read: readIntendWrite, update: update, write: write, readIntendUpdate: readIntendWrite, readIntendWrite: readIntendWrite, intendRead: intendWrite, intendUpdate: intendWrite, intendWrite: intendWrite]]; lookupAndInsert: Header; <> nLocks, nRequests, nSetCalls, nSetCallsWaited: INT; <> MakeLockID: PUBLIC PROC [did: DID] RETURNS [lock: LockID] ~ { <> <> <> <> << else copy all the non "/" characters into the buffer from right to left. If there are still characters, then xor them in fetching the characters from the buffer from right to left, but xoring cycically from left to right.>> <> lockBuffer: ARRAY [0..24) OF CHAR _ ALL['\000]; noRootChar: INT; sizeOfString: INT; didAsRope: Rope.ROPE; noRootChar _ Rope.Length[YggDID.RootPath]; didAsRope _ did^; sizeOfString _ Rope.Length[didAsRope]; IF sizeOfString - noRootChar <= 24 THEN TRUSTED { nBytes: CARD; subFlatRope: Rope.Text; subFlatRope _ Rope.Flatten[base: didAsRope, start: noRootChar]; nBytes _ Basics.ByteBlt[ from: [blockPointer: LOOPHOLE[subFlatRope, POINTER]+UNITS[TEXT[0]], startIndex: 0, stopIndexPlusOne: sizeOfString - noRootChar], to: [blockPointer: @lockBuffer, startIndex: 0, stopIndexPlusOne: sizeOfString - noRootChar] ]; IF nBytes # sizeOfString THEN ERROR; } ELSE { charPos: INT _ sizeOfString; storePos: INT _ 23; WHILE charPos > noRootChar DO nowChar: CHAR; charPos _ charPos - 1; nowChar _ Rope.Fetch[didAsRope, charPos]; IF nowChar = '/ THEN LOOP; lockBuffer[storePos] _ nowChar; storePos _ storePos -1; IF storePos < 0 THEN EXIT; ENDLOOP; IF charPos > noRootChar THEN { storePos _ 0; WHILE charPos > noRootChar DO nowChar: CHAR; charPos _ charPos - 1; nowChar _ Rope.Fetch[didAsRope, charPos]; IF nowChar = '/ THEN LOOP; lockBuffer[storePos] _ LOOPHOLE[Basics.BITXOR[LOOPHOLE[lockBuffer[storePos]], LOOPHOLE[nowChar]]]; storePos _ storePos + 1; IF storePos >= 24 THEN storePos _ 0; ENDLOOP; }; }; }; Set: PUBLIC ENTRY PROC [ trans: YggInternal.TransHandle, lock: LockID, mode: LockMode, wait: BOOL] RETURNS [resultMode: LockMode] = { <> h: Header; <> wr: WaitingRequest _ NIL; <> thisTransGrantedRequest: GrantedRequest; <> useMode: LockMode; { -- EXITS CreateGrantedRequest, ConvertExistingRequest nSetCalls _ nSetCalls + 1; lookupAndInsert.lockID _ lock; IF (h _ LookupAndInsert[lookupAndInsert]) = lookupAndInsert THEN { <> lookupAndInsert _ NEW[LockRep.header _ [body: header []]]; lookupAndInsert.requestList _ lookupAndInsert; nLocks _ nLocks + 1; GOTO CreateGrantedRequest; }; <> <<(a) if the request is a conversion, the loop is traveled first with the requested mode, then again with the supremum of the current and requested modes.>> <<(b) if the request cannot be granted without waiting, the loop is traveled by the request as it attempts to acquire the lock. Only the first waiting request for a given LockID may acquire the lock, and usually this is the only request that wakes up when something interesting changes, but a request may travel the loop only to find that it is not first in line (and go right back to sleep) under some conditions.>> useMode _ mode; DO { -- EXITS Conflict, TryConversionMode { -- EXITS NoWaitingRequests, WaitingRequests <> <> <> thisTransGrantedRequest _ NIL; FOR r: Lock _ h.requestList, r.requestList DO WITH r SELECT FROM hh: Header=> GOTO NoWaitingRequests; rh: Request => WITH rh SELECT FROM grh: GrantedRequest => { IF grh.trans = trans THEN thisTransGrantedRequest _ grh ELSE IF NOT Compat[useMode][grh.mode] THEN GOTO CannotGrant; }; wrh: WaitingRequest => { IF wr # NIL AND wr # wrh THEN GOTO CannotGrant; <> GOTO WaitingRequests; <> }; th: LockTransHeader => ERROR; ENDCASE; ENDCASE; ENDLOOP; EXITS NoWaitingRequests => { IF thisTransGrantedRequest = NIL THEN GOTO CreateGrantedRequest; IF Sup[mode][thisTransGrantedRequest.mode] = useMode THEN GOTO ConvertExistingRequest; GOTO TryConversionMode; }; WaitingRequests => { IF thisTransGrantedRequest # NIL AND Sup[mode][thisTransGrantedRequest.mode] # useMode THEN GOTO TryConversionMode; <> IF wr # NIL THEN { UnregisterWaitingRequest[wr]; RemoveFromRequestList[r: wr, deleteHeaderIfNoRequests: FALSE]; nRequests _ nRequests - 1; }; IF thisTransGrantedRequest # NIL THEN GOTO ConvertExistingRequest; PromoteWaitingRequests[h, trans]; GOTO CreateGrantedRequest; }; };-- EXITS NoWaitingRequests, WaitingRequests EXITS CannotGrant => { <> IF NOT wait THEN RETURN WITH ERROR Failed [conflict]; IF wr = NIL THEN { <> wr _ RegisterWaitingRequest[trans, lock, mode]; EnterWaitingInRequestList[h, wr]; nRequests _ nRequests + 1; nSetCallsWaited _ nSetCallsWaited + 1; }; WAIT wr.somethingChanged; IF wr.giveUp THEN { UnregisterWaitingRequest[wr]; RemoveFromRequestList[wr]; SELECT wr.whyGivingUp FROM abort => RETURN WITH ERROR TransAborting; timeout => RETURN WITH ERROR Failed [timeout]; ENDCASE => ERROR; }; useMode _ mode; }; TryConversionMode => { <> useMode _ Sup[mode][thisTransGrantedRequest.mode]; }; };-- EXITS Conflict, TryConversionMode ENDLOOP; EXITS <> CreateGrantedRequest => { t: LockTransHeader = YggTransactionMap.GetLockHeader[trans]; r: GrantedRequest _ NEW[LockRep.request.granted _ [ requestList: h.requestList, body: request [ trans: trans, transList: t.transList, lockID: lock, mode: mode, rest: granted [count: 1]]]]; h.requestList _ r; t.transList _ r; t.nLocks _ t.nLocks + 1; nRequests _ nRequests + 1; RETURN [mode]; }; ConvertExistingRequest => { thisTransGrantedRequest.mode _ useMode; thisTransGrantedRequest.count _ thisTransGrantedRequest.count + 1; RETURN [useMode]; }; };-- EXITS CreateGrantedRequest, ConvertExistingRequest };--Set  Release: PUBLIC ENTRY PROC [trans: YggInternal.TransHandle, lock: LockID, releasable: ModeReleasableSet] RETURNS [LockMode] = { <> h: Header; IF (h _ Lookup[lock]) = NIL THEN RETURN WITH ERROR Error [unknown]; FOR r: Lock _ h.requestList, r.requestList DO WITH r SELECT FROM hh: Header => RETURN WITH ERROR Error [unknown]; rh: Request => WITH rh SELECT FROM grh: GrantedRequest => IF grh.trans = trans THEN { IF releasable[grh.mode] = no THEN RETURN WITH ERROR Error [lockUnreleasable]; IF (grh.count _ grh.count - 1) = 0 THEN { UnlinkFromTrans[trans, grh]; RemoveFromRequestList[grh]; DemoteWaitingRequests[h, trans]; RETURN [none]; } ELSE RETURN [grh.mode]; }; wrh: WaitingRequest => RETURN WITH ERROR Error [unknown]; th: LockTransHeader => ERROR; ENDCASE; ENDCASE; ENDLOOP; }; ReleaseFileLocks: PUBLIC ENTRY PROC [trans: YggInternal.TransHandle, prototype: LockID, releasable: ModeReleasableSet] = { <> transHeader: LockTransHeader = YggTransactionMap.GetLockHeader[trans]; rNext: Request; FOR rh: Request _ transHeader.transList, rNext DO rNext _ rh.transList; WITH rh SELECT FROM grh: GrantedRequest => IF releasable[grh.mode] = yes THEN { handleLockID: LockID _ YggLockInternal.LockIDFromRH[ grh ]; IF handleLockID.entity = prototype.entity AND handleLockID.subEntity = prototype.subEntity THEN { UnlinkFromTrans[trans, grh]; RemoveFromRequestList[grh]; }; }; wrh: WaitingRequest => ERROR; th: LockTransHeader => RETURN; ENDCASE; ENDLOOP; }; RemoveFromRequestList: INTERNAL PROC [ r: Request, deleteHeaderIfNoRequests: BOOL _ TRUE] = { <> <> rPred: Lock; notifyDone: BOOL _ FALSE; FOR rPred _ r.requestList, rPred.requestList UNTIL rPred.requestList = r DO WITH rPred SELECT FROM wrh: WaitingRequest => IF NOT notifyDone THEN { NOTIFY wrh.somethingChanged; notifyDone _ TRUE; }; ENDCASE; ENDLOOP; IF rPred = r.requestList AND deleteHeaderIfNoRequests THEN { rPred.requestList _ NIL; Delete[NARROW[rPred]]; nLocks _ nLocks - 1; } ELSE { rPred.requestList _ r.requestList; }; r.requestList _ NIL; nRequests _ nRequests - 1; }; Initialize: PUBLIC ENTRY PROC [lockZoneInitialSize: INT, hashArraySize: NAT] = { <> InitWaitingRequestList[]; InitializeHashTable[ numHashSlotsDesired: hashArraySize, hashHandle: NEW[LockRep.header _ [body: header []]]]; lookupAndInsert _ NEW[LockRep.header _ [body: header []]]; lookupAndInsert.requestList _ lookupAndInsert; nLocks _ 0; nRequests _ 0; nSetCalls _ 0; nSetCallsWaited _ 0; };  <> <> EnterWaitingInRequestList: INTERNAL PROC [ h: Header, wr: WaitingRequest] = { <> <> r: Lock; FOR r _ h, r.requestList UNTIL r.requestList = h DO ENDLOOP; r.requestList _ wr; wr.requestList _ h; }; PromoteWaitingRequests: INTERNAL PROC [ h: Header, trans: YggInternal.TransHandle] = { <> <> }; DemoteWaitingRequests: INTERNAL PROC [ h: Header, trans: YggInternal.TransHandle] = { <> <> };  <> ConsTransHeader: PUBLIC PROC [trans: YggInternal.TransHandle] RETURNS [lockHeader: LockTransHeader] = { <> lockHeader _ NEW[LockRep.request.transHeader _ [body: request [ trans: trans, transList: NIL, mode: none, rest: transHeader [nLocks: 0]]]]; lockHeader.transList _ lockHeader; RETURN [lockHeader]; }; UpgradeLocks: PUBLIC PROC [trans: YggInternal.TransHandle] = { <> <> <> ugh: LockTransHeader = YggTransactionMap.GetLockHeader[trans]; r: Request _ ugh; lockID: LockID; DO [r, lockID] _ GetNextInTransNeedingUpgrade[r]; IF r = NIL THEN RETURN; [] _ Set[trans, lockID, Upgrade[r.mode], TRUE]; ENDLOOP; }; GetNextInTransNeedingUpgrade: ENTRY PROC [r: Request] RETURNS [next: Request, nextLockID: LockID] = { <> FOR next _ r.transList, next.transList DO IF ISTYPE[next, LockTransHeader] THEN RETURN [NIL, nullLockID]; IF NeedsUpgrade[next.mode] THEN EXIT; ENDLOOP; <> FOR h: Lock _ next.requestList, h.requestList DO WITH h SELECT FROM hh: Header => RETURN [next, hh.lockID]; ENDCASE; ENDLOOP; }; <> Upgrade: ARRAY LockMode OF LockMode _ [ none: none, read: read, update: write, write: write, readIntendUpdate: readIntendWrite, readIntendWrite: readIntendWrite, intendRead: intendRead, intendUpdate: intendWrite, intendWrite: intendWrite]; NeedsUpgrade: ARRAY LockMode OF BOOL _ [ none: FALSE, read: FALSE, update: TRUE, write: FALSE, readIntendUpdate: TRUE, readIntendWrite: FALSE, intendRead: FALSE, intendUpdate: TRUE, intendWrite: FALSE]; <<>> <> Downgrade: ARRAY LockMode OF LockMode _ [ none: none, read: read, update: read, write: read, readIntendUpdate: read, readIntendWrite: read, intendRead: intendRead, intendUpdate: intendRead, intendWrite: intendRead]; ReleaseLocks: PUBLIC ENTRY PROC [trans: YggInternal.TransHandle] = { <> transHeader: LockTransHeader = YggTransactionMap.GetLockHeader[trans]; rNext: Request; FOR r: Request _ transHeader.transList, rNext DO rNext _ r.transList; r.transList _ NIL; r.trans _ NIL; WITH r SELECT FROM gr: GrantedRequest => RemoveFromRequestList[gr]; wr: WaitingRequest => ERROR; th: LockTransHeader => RETURN; ENDCASE; ENDLOOP; }; UnlinkFromTrans: INTERNAL PROC [ trans: YggInternal.TransHandle, gr: GrantedRequest] = { <> transHeader: LockTransHeader = YggTransactionMap.GetLockHeader[trans]; rPred: Request; FOR rPred _ transHeader, rPred.transList UNTIL rPred.transList = gr DO ENDLOOP; rPred.transList _ gr.transList; gr.transList _ NIL; gr.trans _ NIL; transHeader.nLocks _ transHeader.nLocks - 1; }; TransferLocks: PUBLIC ENTRY PROC [from, to: YggInternal.TransHandle] = { <> transHeader: LockTransHeader = YggTransactionMap.GetLockHeader[from]; FOR r: Request _ transHeader.transList, r.transList DO r.trans _ to; IF NOT (YggFileLock.IsWholeFileLock[r.lockID] AND (r.mode=write OR r.mode=update)) THEN r.mode _ Downgrade[r.mode]; IF r = transHeader THEN RETURN; ENDLOOP; };  <> waitingRequestList: WaitingRequest; <> <> <> InitWaitingRequestList: INTERNAL PROC [] = { waitingRequestList _ NEW[LockRep.request.waiting _ [body: request [ trans: NIL, transList: NIL, mode: none, rest: waiting [startTime: BasicTime.earliestGMT]]]]; }; RegisterWaitingRequest: INTERNAL PROC [ trans: YggInternal.TransHandle, lockID: LockID, mode: LockMode] RETURNS [wr: WaitingRequest] = { wr _ NEW[LockRep.request.waiting _ [ requestList: NIL, body: request [ trans: trans, transList: waitingRequestList.transList, lockID: lockID, mode: mode, rest: waiting [ startTime: BasicTime.Now[]]]]]; waitingRequestList.transList _ wr; TRUSTED {YggDummyProcess.DisableTimeout[@wr.somethingChanged];}; }; UnregisterWaitingRequest: INTERNAL PROC [wr: WaitingRequest] = { r: Request; FOR r _ waitingRequestList, r.transList UNTIL r.transList = wr DO ENDLOOP; r.transList _ wr.transList; wr.transList _ NIL; wr.trans _ NIL; }; AbortWaitingRequests: PUBLIC ENTRY PROC [trans: YggInternal.TransHandle] = { <> FOR r: Request _ waitingRequestList.transList, r.transList UNTIL r = NIL DO IF r.trans = trans THEN WITH r SELECT FROM wr: WaitingRequest => { wr.giveUp _ TRUE; wr.whyGivingUp _ abort; NOTIFY wr.somethingChanged; }; ENDCASE => ERROR; ENDLOOP; }; TimeoutWaitingRequest: PUBLIC ENTRY PROC [wr: WaitingRequest] = { <> wr.giveUp _ TRUE; wr.whyGivingUp _ timeout; NOTIFY wr.somethingChanged; }; EnumerateWaitingRequests: INTERNAL PROC [ proc: PROC [wr: WaitingRequest] RETURNS [stop: BOOL]] = { FOR r: Request _ waitingRequestList.transList, r.transList UNTIL r = NIL DO IF proc[NARROW[r]].stop THEN RETURN; ENDLOOP; };  GetInfo: PUBLIC ENTRY PROC [ generalInfoProc: YggLockInternal.GeneralInfoProc, lockEnumProc: YggLockInternal.LockEnumProc, waitingRequestEnumProc: YggLockInternal.WaitingRequestEnumProc, waitingRequestEnumProc2: YggLockInternal.WaitingRequestEnumProc] = { IF generalInfoProc # NIL THEN generalInfoProc[nLocks, nRequests, nSetCalls, nSetCallsWaited]; IF lockEnumProc # NIL THEN EnumerateWithProc[lockEnumProc]; IF waitingRequestEnumProc # NIL THEN EnumerateWaitingRequests[waitingRequestEnumProc]; IF waitingRequestEnumProc2 # NIL THEN EnumerateWaitingRequests[waitingRequestEnumProc2]; };  <> HashHandle: TYPE = Header; Key: TYPE = LockID; PrimeTable: ARRAY PrimeTableIndex OF NAT _ [37, 67, 131, 257, 513, 1031, 2003]; PrimeTableIndex: TYPE = [0 .. 6]; ClientHashInit: PROC [numHashSlotsDesired: NAT] RETURNS [numHashSlotsAllowed: NAT] = { FOR i: PrimeTableIndex IN PrimeTableIndex DO IF PrimeTable[i] >= numHashSlotsDesired THEN RETURN [PrimeTable[i]]; ENDLOOP; RETURN [PrimeTable[PrimeTableIndex.LAST]]; }; ClientHash: INTERNAL PROC [hashHandle: HashHandle] RETURNS [NAT--[0..numHashSlots)--] = INLINE { ID6: TYPE = RECORD [a, b, c, d, e, f, g: WORD32]; RETURN [Basics.BITXOR[ Basics.BITXOR[ LOOPHOLE[hashHandle.lockID, ID6].b, LOOPHOLE[hashHandle.lockID, ID6].d], Basics.BITXOR[ LOOPHOLE[hashHandle.lockID, ID6].f, LOOPHOLE[hashHandle.lockID, ID6].c]] MOD numHashSlots]; }; ClientEqualKeys: INTERNAL PROC [hashHandle1, hashHandle2: HashHandle] RETURNS [equal: BOOL] = INLINE { <> <> ID5: TYPE = RECORD [a, b, c, d, e, f, g: CARD32]; RETURN [ LOOPHOLE[hashHandle1.lockID, ID5].b = LOOPHOLE[hashHandle2.lockID, ID5].b AND LOOPHOLE[hashHandle1.lockID, ID5].d = LOOPHOLE[hashHandle2.lockID, ID5].d AND LOOPHOLE[hashHandle1.lockID, ID5].c = LOOPHOLE[hashHandle2.lockID, ID5].c AND LOOPHOLE[hashHandle1.lockID, ID5].e = LOOPHOLE[hashHandle2.lockID, ID5].e AND LOOPHOLE[hashHandle1.lockID, ID5].a = LOOPHOLE[hashHandle2.lockID, ID5].a AND LOOPHOLE[hashHandle1.lockID, ID5].f = LOOPHOLE[hashHandle2.lockID, ID5].f] }; ClientSetKey: INTERNAL PROC [hashHandle: HashHandle, key: Key] = INLINE { hashHandle.lockID _ key; }; <> LookupAndInsert: INTERNAL PROC [hashHandle: HashHandle] RETURNS [HashHandle] = INLINE { index: NAT _ ClientHash[hashHandle]; FOR newHashHandle: HashHandle _ hashSlots[index], newHashHandle.next UNTIL newHashHandle = NIL DO IF ClientEqualKeys[newHashHandle, hashHandle] THEN RETURN [newHashHandle]; ENDLOOP; hashHandle.next _ hashSlots[index]; hashSlots[index] _ hashHandle; RETURN [hashHandle]; }; <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<[hashHandle: HashHandle];>> <> <> <> <> <> <> <> 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.--LockCoreImpl CHANGE LOG Changed by MBrown on February 8, 1983 5:47 pm <> Changed by MBrown on February 9, 1983 4:16 pm <> <> <> <<>> <<>>