YggDIDMapImpl.mesa
Copyright Ó 1985, 1988 by Xerox Corporation. All rights reserved.
Last edited by
MBrown on January 31, 1984 4:09:40 pm PST
Kolling on January 23, 1984 3:12:16 pm PST
Kupfer, February 21, 1985 10:38:18 am PST
Bob Hagmann May 13, 1988 8:42:54 am PDT
Carl Hauser, October 16, 1987 10:59:29 am PDT
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;
For Phase 0, the DIDRep is just a string that names a directory (without the trailing /).
Finds or creates a Document for the supplied volume and file.
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] ~ {
Picks apart the LockID and uses the values to find the Document. Similar to Register. FileLockImpl.MakeLockID is the reason for our trust. The hashing code only looks at the "id" part of fileID, so we let the DA part be NULL (yuck).
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;
doc = NIL starts a new enumeration, and GetNext returns nextDocument = NIL when the enumeration is exhausted. The only guaranteed property of the enumeration is that all documents in existence during the entire enumeration will be visited at least once. Some documents may be seen more than once.
GetNext: PUBLIC ENTRY PROCEDURE[doc: Document] RETURNS [nextDocument: Document] =
BEGIN -- errors defined in FileMap: none.
ENABLE UNWIND => NULL;
RETURN[EnumerateNext[doc]];
END;
Hash table management:
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.
HashDocument must:
be a REF type.
contain a field "next" of type HashDocument, under the exclusive control of the
hash package.
Key is an arbitrary type.
SetKey sets the "key value" associated with a HashDocument. The key value must
not change between the time the doc 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 "hashDocument".
EqualKeys must be the equality relation on the key values of the parameters
"hashDocument1" and "hashDocument2".
Interface description:
InitializeHashTable: INTERNAL PROCEDURE[numHashSlotsDesired: NAT, hashTableZone:
ZONE, hashDocument: HashDocument];
errors: HashPkgCallerProgrammingError (numHashSlotsDesired = 0).
Insert: INTERNAL PROCEDURE[hashDocument: HashDocument];
errors: HashPkgDuplicateKey.
Lookup: INTERNAL PROCEDURE[key: Key] RETURNS [hashDocument: HashDocument];
returns hashDocument = NIL if not found.
Delete: INTERNAL PROCEDURE[hashDocument: HashDocument];
errors: HashPkgCallerProgrammingError (not found).
EnumerateNext: INTERNAL PROCEDURE[prevHashDocument: HashDocument] RETURNS
[hashDocument: HashDocument];
errors: none.
prevHashDocument = NIL starts the enumeration, returned hashDocument = NIL is the end
of the enumeration. This procedure guarantees that any hashDocument in existence throughout
the entire enumeration will be seen. Other docs may or not not be seen. HashDocuments
may be seen more than once.
EnumerateWithProc: INTERNAL PROCEDURE[proc: PROCEDURE[hashDocument: HashDocument]
RETURNS[stop: BOOLEAN]];
errors: none.
client-supplied parameters to hash package begin here:
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]];
};
end of client-supplied parameters, 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:
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.
errors:
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;
prevHashDocument = NIL starts the enumeration, returned hashDocument = NIL is the end of the enumeration. This procedure guarantees that any hashDocument in existence throughout the entire enumeration will be seen. Other docs may or not not be seen. HashDocuments may be seen more than once.
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 of invariant hash package code.
END.
Edit Log
Initial: Kolling: October 12, 1982 12:13 pm: an impl module for FileMap.
Edited on February 21, 1985 10:38:15 am PST, by Kupfer
Add FileFromLockID.
Carl Hauser, October 16, 1987 10:59:04 am PDT
Added SetRecoveryData, GetRecoveryData