<> <> <> <> <> <> <> <> DIRECTORY YggDID USING[DID, EqualDIDs, RootPath], YggDIDMap, YggDIDMapPrivate USING[Document, DocumentRep], YggLock USING [LockID], YggDummyProcess USING[Detach], YggInternal USING[Document], SafeStorage USING[EnableFinalization, EstablishFinalization, FinalizationQueue, FQNext, IsFinalizationEnabled, NewFQ], Rope USING [Fetch, Length, ROPE]; YggDIDMapImpl: CEDAR MONITOR IMPORTS YggDID, YggDummyProcess, Rope, SafeStorage EXPORTS YggInternal, YggDIDMap, YggDID = BEGIN Document: TYPE = REF DocumentRep; DocumentRep: PUBLIC TYPE = YggDIDMapPrivate.DocumentRep; DID: PUBLIC TYPE ~ REF DIDRep; DIDRep: PUBLIC TYPE ~ Rope.ROPE; <> <> Register: PUBLIC ENTRY PROC [did: YggDID.DID] RETURNS [doc: YggInternal.Document] = { ENABLE UNWIND => NULL; IF (doc _ Lookup[did]) = NIL THEN Insert[(doc _ NEW[DocumentRep _ [did: did, componentFiles: NIL, interlock: FALSE, next: NIL]])]; SafeStorage.EnableFinalization[doc]; }; SetRecoveryData: PUBLIC PROC [doc: Document, ref: REF] ~ { doc.recoveryData _ ref; }; GetRecoveryData: PUBLIC PROC [doc: Document] RETURNS [ref: REF] ~ { ref _ doc.recoveryData; }; DocumentFromLockID: PUBLIC ENTRY PROC [lock: YggLock.LockID] RETURNS [Document _ NIL] ~ { <> ENABLE UNWIND => NULL; RETURN[Lookup[lock.did]]; }; finalizationQ: SafeStorage.FinalizationQueue; FinalizationProcess: PROCEDURE = BEGIN FinalizeEntry: ENTRY PROCEDURE [doc: Document] = BEGIN IF SafeStorage.IsFinalizationEnabled[doc] THEN RETURN; Delete[doc]; END; DO FinalizeEntry[NARROW[SafeStorage.FQNext[finalizationQ]]]; ENDLOOP; END; ZeroIllegal: --CALLING-- ERROR = CODE; secondLookupHashDocument: HashDocument _ NIL; -- wierdness to protect object from finalization. Initialize: PUBLIC ENTRY PROCEDURE[numHashSlotsDesired: NAT, fQLength: CARDINAL] = BEGIN -- errors defined in FileMap: none. IF fQLength = 0 THEN RETURN WITH ERROR ZeroIllegal; finalizationQ _ SafeStorage.NewFQ[fQLength]; -- do this before SafeStorage.EstablishFinalization[CODE[DocumentRep], 1, finalizationQ]; -- allocating any FileObjects. TRUSTED BEGIN YggDummyProcess.Detach[FORK FinalizationProcess[]]; END; secondLookupHashDocument _ NEW[DocumentRep _ [did: NIL, componentFiles: NIL, interlock: FALSE, next: NIL]]; InitializeHashTable[numHashSlotsDesired, secondLookupHashDocument]; END; <> GetNext: PUBLIC ENTRY PROCEDURE[doc: Document] RETURNS [nextDocument: Document] = BEGIN -- errors defined in FileMap: none. ENABLE UNWIND => NULL; RETURN[EnumerateNext[doc]]; END; <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<"hashDocument1" and "hashDocument2".>> <> <> <> <> <> <> <> <> <> <> <> <<[hashDocument: HashDocument];>> <> <> <> <> <> <> <> <> <> HashDocument: TYPE = Document; Key: TYPE = YggDID.DID; ClientHashInit: INTERNAL PROCEDURE[numHashSlotsDesired: NAT] RETURNS [numHashSlotsAllowed: NAT] = BEGIN divisor, quotient, remainder: CARDINAL; DO divisor _ 2; DO <<[quotient, remainder] _ Basics.DivMod[numHashSlotsDesired, divisor];>> quotient _ numHashSlotsDesired / divisor; remainder _ numHashSlotsDesired MOD divisor; IF remainder = 0 THEN EXIT; -- this number is not prime. IF quotient < divisor THEN RETURN[numHashSlotsDesired]; -- prime. divisor _ divisor + 1; ENDLOOP; numHashSlotsDesired _ numHashSlotsDesired + 1; ENDLOOP; END; ClientHash: INTERNAL PROCEDURE[hashDocument: HashDocument] RETURNS [index: NAT--[0..numHashSlots)--] = INLINE { didAsRope: Rope.ROPE; did: DID; did _ hashDocument.did; index _ 0; didAsRope _ did^; FOR charNo: INT IN [Rope.Length[YggDID.RootPath]..Rope.Length[didAsRope]) DO charAsOrd: INT; charAsOrd _ Rope.Fetch[didAsRope, charNo].ORD; index _ index + charAsOrd; ENDLOOP; index _ index MOD numHashSlots; }; ClientEqualKeys: INTERNAL PROCEDURE[hashDocument1, hashDocument2: HashDocument] RETURNS [equal: BOOLEAN] = INLINE { RETURN[YggDID.EqualDIDs[hashDocument1.did, hashDocument2.did]]; }; <> <> hashSlots: REF HashSlots _ NIL; HashSlots: TYPE = RECORD[SEQUENCE nSlots: NAT OF HashDocument]; numHashSlots: NAT _ 0; -- boy, will they be sorry if they don't init this package. lookupHashDocument: HashDocument _ NIL; -- for the "package's" use only. <> HashPkgCallerProgrammingError: ERROR = CODE; -- various fatal conditions. HashPkgDuplicateKey: ERROR = CODE; -- from Insert. InitializeHashTable: INTERNAL PROCEDURE[numHashSlotsDesired: NAT, hashDocument: HashDocument] = BEGIN -- errors: HashPkgCallerProgrammingError (numHashSlotsDesired = 0). numHashSlots _ ClientHashInit[numHashSlotsDesired]; IF numHashSlots = 0 THEN ERROR HashPkgCallerProgrammingError; lookupHashDocument _ hashDocument; hashSlots _ NEW[HashSlots[numHashSlots]]; FOR index: NAT IN [0..numHashSlots) DO hashSlots[index] _ NIL; ENDLOOP; END; Insert: INTERNAL PROCEDURE[hashDocument: HashDocument] = BEGIN -- errors: HashPkgDuplicateKey. index: NAT _ ClientHash[hashDocument]; FOR newHashDocument: HashDocument _ hashSlots[index], newHashDocument.next UNTIL newHashDocument = NIL DO IF ClientEqualKeys[newHashDocument, hashDocument] THEN ERROR HashPkgDuplicateKey; ENDLOOP; hashDocument.next _ hashSlots[index]; hashSlots[index] _ hashDocument; END; Lookup: INTERNAL PROCEDURE[key: Key] RETURNS [hashDocument: HashDocument] = BEGIN -- returns hashDocument = NIL if not found. lookupHashDocument.did _ key; FOR hashDocument _ hashSlots[ClientHash[lookupHashDocument]], hashDocument.next UNTIL hashDocument = NIL DO IF ClientEqualKeys[hashDocument, lookupHashDocument] THEN RETURN; ENDLOOP; RETURN[NIL]; END; Delete: INTERNAL PROCEDURE[hashDocument: HashDocument] = BEGIN -- errors: HashPkgCallerProgrammingError (not found). index: NAT _ ClientHash[hashDocument]; prevHashDocument: HashDocument _ NIL; FOR newHashDocument: HashDocument _ hashSlots[index], newHashDocument.next UNTIL newHashDocument = NIL DO IF ClientEqualKeys[newHashDocument, hashDocument] THEN EXIT; prevHashDocument _ newHashDocument; REPEAT FINISHED => ERROR HashPkgCallerProgrammingError; ENDLOOP; IF prevHashDocument = NIL THEN hashSlots[index] _ hashDocument.next ELSE prevHashDocument.next _ hashDocument.next; END; <> EnumerateNext: INTERNAL PROCEDURE[prevHashDocument: HashDocument] RETURNS [hashDocument: HashDocument] = BEGIN -- errors: none. index: NAT; IF prevHashDocument = NIL THEN index _ 0 ELSE BEGIN index _ ClientHash[prevHashDocument]; FOR hashDocument _ hashSlots[index], hashDocument.next UNTIL hashDocument = NIL DO IF ClientEqualKeys[hashDocument, prevHashDocument] THEN GOTO found; REPEAT found => BEGIN IF hashDocument.next # NIL THEN RETURN[hashDocument.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[hashDocument: HashDocument] RETURNS[stop: BOOLEAN]] = BEGIN -- errors: none. FOR index: NAT IN [0..numHashSlots) DO FOR hashDocument: HashDocument _ hashSlots[index], hashDocument.next UNTIL hashDocument = NIL DO IF proc[hashDocument] THEN RETURN; ENDLOOP; ENDLOOP; END; <> END. Edit Log Initial: Kolling: October 12, 1982 12:13 pm: an impl module for FileMap. <> <> <> <> <<>>