DIRECTORY BasicTime USING[GMT], Camelot USING[segmentIdT], YggDIDPrivate USING[DIDRep], YggInternal USING[Document, FileHandle], YggEnvironment USING [DID, nullDID], YggRep USING[nullTimeStamp, TimeStamp], Rope USING [ROPE]; YggDIDMapPrivate: CEDAR DEFINITIONS = BEGIN Document: TYPE = YggInternal.Document; DocumentRep: TYPE = MONITORED RECORD[ did: YggEnvironment.DID, -- id of this document fromDID: YggEnvironment.DID _ YggEnvironment.nullDID, toDID: YggEnvironment.DID _ YggEnvironment.nullDID, linkType: Rope.ROPE _ NIL, name: Rope.ROPE, -- human-legible name. parsedDocList: LIST OF DocItem _ NIL, modifiedDIDMap: BOOL _ FALSE, destroyed: BOOL _ FALSE, okToRemoveFromDIDMapCache: BOOL _ FALSE, -- YggDIDMapImpl's flag for remove delayed due to finalization trouble timeStampForIndexMaint: YggRep.TimeStamp _ YggRep.nullTimeStamp, componentFiles: LIST OF YggInternal.FileHandle, interlock: BOOLEAN _ FALSE, next: Document, -- bucket hash chain for YggDIDMapImpl lruListNext: Document _ NIL, -- LRU lists for YggDIDMapImpl lruListPrev: Document _ NIL]; notCompressed: CARD = 0; EntryPtr: TYPE = LONG BASE POINTER TO Entry; DocPartPtr: TYPE = LONG BASE POINTER TO DocPart; TextRP: TYPE = DocPartPtr RELATIVE POINTER TO TextRep; TextRep: TYPE = MACHINE DEPENDENT RECORD [PACKED SEQUENCE length: CARDINAL OF CHAR]; PartType: TYPE = MACHINE DEPENDENT {root(0), contents(1), outlinks(2), attributes(3), index(4), directoryContents(5)}; DocPart: TYPE = MACHINE DEPENDENT RECORD [ docPartSize(0): CARD, -- size in words of part compression(2): CARD _ notCompressed, keepingModifications(4:0..0): BOOL, partType(4:1..4): PartType, extraFlags(4:5..15): CARD [0..0FFh] _ 0, slotNo(5): CARD _ 0, indexName(7): TextRP, versionIdentifierString(8): TextRP, fillOutTo32BitWord(9): CARD16, segments(10): CARD ]; SegmentRep: TYPE = MACHINE DEPENDENT RECORD [ firstPage(0): CARD, numberOfBytes(2): CARD, modificationDeltasOffset(4): CARD, lastUsedTime(6): BasicTime.GMT, backUpTime(8): BasicTime.GMT, backUpID(10): CARD, length(12): CARDINAL, fillOutTo32BitWord(13): CARD16, runs(14): SEQUENCE COMPUTED CARDINAL OF RunRep ]; RunRep: TYPE = MACHINE DEPENDENT RECORD [ sixteenBitsOfFill: CARDINAL _ 0, segmentId: Camelot.segmentIdT, segmentPage: CARD, -- offset in segment in pages pages: INT -- for non-leader, number of pages (0 for leader) ]; DocItem: TYPE = RECORD [ partType: PartType, indexName: ATOM _ NIL, slotNo: CARD _ 0, segments: LIST OF SegmentItem ]; SegmentItem: TYPE = RECORD [ firstPage: CARD, numberOfBytes: CARD, runs: LIST OF RunItem ]; RunItem: TYPE = RECORD [ segmentId: Camelot.segmentIdT, segmentPage: CARD, -- offset in segment in pages pages: INT -- for non-leader, number of pages (0 for leader) ]; OverheadPerEntry: CARD = 6; Word32OverheadPerEntry: CARD = OverheadPerEntry/WORDS[CARD32]; Entry: TYPE = MACHINE DEPENDENT RECORD [ size(0:0..15): CARD16, -- size in words of entire (physical) entry link(1:0..0): BOOL , -- does a link follow? extensionCount(1:1..15): [0..07fffh] , -- 0 for normal, 1 for normal with extentions, and 2 and up for extended entries did(2): YggDIDPrivate.DIDRep, -- the bits for a DID data(OverheadPerEntry): SEQUENCE COMPUTED [0..4096) OF CARD -- see above ]; END. ¬YggDIDMapPrivate.mesa Copyright Σ 1988 by Xerox Corporation. All rights reserved. Last edited by Bob Hagmann March 15, 1989 10:16:35 am PST Documents for links, the next three fields have non-trivial values Disk resident extensible hash entries Disk resident encoding of the variable fields for the DID map. Virtual memory resident versions the variable fields for the DID map. The info for a DID is usually stored in one B-tree entry. However, the entry can grow too large. Hence, it can be split up into parts. The records are indexed by both did and extensionCount. The extensionCount is a flag for normal or extended records. If it is 0, this is a normal record and all the info is stored starting at the data field, and continuing to end-of-record. For extended records, the CARD at data is the total size of all of the info for the did. The rest of the words from the first record are concatenated with the words from the rest of the records. The info is the link data and a list of DocPart's (see above.) The links are the from and to DIDs, followed by a string Each DocPart starts with it's size (docPartSize). The last DocPart completely uses all of the space in the data part of the entry. The segments field in the DocPart is the start of the segment list for the DocPart. The segment list completely consumes all of the space indicated by the docPartSize field. Each segment has a list of runs, written as a SEQUENCE. ΚK˜Jšœ™Jšœ<™<šœ™Icode™*J˜J˜—šΟk ˜ Kšœ œ˜Kšœœ ˜Kšœ œ ˜Kšœ œ˜(Kšœœ˜$Kšœœ˜'šœœœ˜K˜K˜——Kšœœ ˜#Kšœ˜K˜Kš˜K˜headšœ ™ Kšœ œ˜'K˜šœ œ œœ˜%šœœΟc˜0K™8—Kšœœ˜5Kšœœ˜3Kšœœœ˜Kšœ œž˜(Kšœœœ œ˜%Kšœœœ˜Kšœ œœ˜KšœœœžF˜pK˜@Kšœœœ˜/Kšœ œœ˜Kšœž'˜8Kšœœž˜K˜š œ œœ œœ˜*Kšœœž˜.Kšœœ˜%Kšœ#˜#Kšœ˜Kšœœ˜(Kšœ œ˜Kšœ˜Kšœ#˜#K˜Kšœ˜K˜—š œ œœ œœ˜-Kšœœ˜Kšœœ˜Kšœœ˜"Kšœœ˜Kšœœ˜Kšœœ˜Kšœ œ˜Kšœœ˜Kš œ œœœœ˜.Kšœ˜—š œœœ œœ˜)Kšœ œ˜ Kšœ˜Kšœ œž˜1Kšœœž1˜=K˜—K˜K™EK™šœ œœ˜Kšœ˜Kšœ œœ˜Kšœœ˜Kšœ œœ ˜K˜—šœ œœ˜Kšœ œ˜Kšœœ˜Kšœœœ˜Kšœ˜—šœ œœ˜Kšœ˜Kšœ œž˜1Kšœœž1˜=K˜—K˜K˜Kšœœ˜Kšœœœœ˜>K˜Kš œͺΟeœŸœŸœ{ŸœDœŸœ™ΑKšœ(Ÿ œG™xKšœŸœŸ œ ŸœFŸœŸœ*ŸœJŸ œ7œ™μK˜š œœœ œœ˜(Kšœœž+˜BKšœœž˜+Kšœ(žP˜xKšœž˜3Kšœ(ž ˜IKšœ˜—K˜—Kšœ˜˜J™——…— ¬£