-- DirectoryScavengerImplB.mesa (last edited by Fay on December 17, 1980 3:56 PM)
DIRECTORY
Directory USING [maxDirectoryNameLength],
DirectoryExtras USING [ScavengerContext, ScavengerError, ScavengerErrorType],
DirectoryInternal USING [DirectoryDescriptor, DirectoryEntryHandle, DirectoryPageHandle, emptySize, maxDirSize, overhead, nilPagePointer, PagePointer],
DirectoryScavenger USING [BTreeError],
Environment USING [wordsPerPage],
File USING [Capability, read, Unknown],
Inline USING [BITAND, BITOR, BITSHIFT],
Space USING [Create, Delete, GetWindow, Handle, LongPointer, Map, Unmap, virtualMemory, WindowOrigin],
Volume USING [Unknown];
DirectoryScavengerImplB: PROGRAM
IMPORTS DirectoryExtras, File, Inline, Space, Volume
EXPORTS DirectoryScavenger
SHARES File =
BEGIN
-- Global Constant
pilotLogSpaceSize: CARDINAL = 1;
-- Public Signal
BTreeInvalid: PUBLIC SIGNAL [error: DirectoryScavenger.BTreeError, page: DirectoryInternal.PagePointer, entry: DirectoryInternal.DirectoryEntryHandle] = CODE;
-- Exported procedures
-- ClosePilotLogFile: Delete the pilotLogFile space.
ClosePilotLogFile: PUBLIC PROC [pilotLogSpace: Space.Handle] =
BEGIN
Space.Delete[pilotLogSpace];
END; -- ClosePilotLogFile
-- DoNesting: Output two spaces per directory nesting level.
DoNesting: PUBLIC PROC [context: DirectoryExtras.ScavengerContext, nestingCount: CARDINAL] =
BEGIN
THROUGH [0..nestingCount) DO context.LogProc[" "]; ENDLOOP;
END; -- DoNesting
-- EquivalentLongStrings: Returns TRUE if s1 and s2 contain the same characters except for case shifts. [Copied from StringsImplA.mesa, substituting "LONG STRING" for "STRING".]
EquivalentLongStrings: PUBLIC PROC [s1, s2: LONG STRING] RETURNS [BOOLEAN] =
BEGIN OPEN Inline;
i: CARDINAL;
casebit: WORD = 40B;
IF s1 = NIL AND s2 = NIL THEN RETURN[TRUE];
IF s1 = NIL OR s2 = NIL OR s1.length # s2.length THEN RETURN[FALSE];
FOR i IN [0..s1.length) DO
IF BITOR[s1[i], casebit] # BITOR[s2[i], casebit] THEN RETURN[FALSE];
ENDLOOP;
RETURN[TRUE]
END; -- EquivalentLongStrings
-- GetWords: Get the next count words from the Pilot scavenger log.
GetWords: PUBLIC PROC [toPointer, bufferPointer: LONG POINTER TO UNSPECIFIED, currentWord, count: CARDINAL, pilotLogSpace: Space.Handle] RETURNS [nextWord: CARDINAL] =
BEGIN
pilotLogWindow: Space.WindowOrigin;
THROUGH [0..count) DO
IF currentWord >= (Environment.wordsPerPage * pilotLogSpaceSize) THEN
{pilotLogWindow ← Space.GetWindow[pilotLogSpace];
pilotLogWindow.base ← pilotLogWindow.base + pilotLogSpaceSize;
currentWord ← 0;
Space.Unmap[pilotLogSpace];
Space.Map[pilotLogSpace, pilotLogWindow];
};
toPointer↑ ← (bufferPointer + currentWord)↑;
toPointer ← toPointer + 1;
currentWord ← currentWord + 1;
ENDLOOP;
nextWord ← currentWord;
END; -- GetWords
-- OpenPilotLogFile: Map the Pilot scavenger log into a space and return a pointer to the header information.
OpenPilotLogFile: PUBLIC PROC [context: DirectoryExtras.ScavengerContext] RETURNS [bufferPointer: LONG POINTER TO UNSPECIFIED, pilotLogSpace: Space.Handle] =
BEGIN
pilotLogSpace ← Space.Create[pilotLogSpaceSize, Space.virtualMemory];
Space.Map[pilotLogSpace, [[context.pilotLogFile.fID, File.read], 0] !
File.Unknown, Volume.Unknown => ERROR DirectoryExtras.ScavengerError[pilotLogFileUnknown] ];
bufferPointer ← Space.LongPointer[pilotLogSpace];
END; -- OpenPilotLogFile
-- ValidateBTree: Perform some tests on this B-Tree. [This was developed from the PROCEDURE ValidateBTree in DirectoryTrees.mesa (last edited by Keith on October 8, 1980 11:01 PM), with several more tests added.]
ValidateBTree: PUBLIC PROC [dir: POINTER TO DirectoryInternal.DirectoryDescriptor] =
BEGIN
pPage: DirectoryInternal.PagePointer;
iPage: CARDINAL;
pageTouched: ARRAY [0.. DirectoryInternal.maxDirSize) OF BOOLEAN ← ALL[FALSE];
PointerToIndex: PROC [p: DirectoryInternal.PagePointer] RETURNS [index: CARDINAL] =
--change a page pointer to an index in [0.. 256), doing some checking as we go
BEGIN
index ← Inline.BITAND[p, 377B]; -- pointer must be multiple of page size
IF index # 0 THEN ERROR BTreeInvalid[error: BadPointer, page: p, entry: NIL];
index ← Inline.BITSHIFT[p, -8];
RETURN[index];
END;
ValidatePage: PROC [p, parent: DirectoryInternal.PagePointer] =
--check this page for validity
BEGIN
pE: DirectoryInternal.DirectoryEntryHandle;
pP: DirectoryInternal.DirectoryPageHandle;
iP: CARDINAL;
size: CARDINAL;
leafPage: BOOLEAN;
iP ← PointerToIndex[p];
IF iP > dir.size - 1 THEN SIGNAL BTreeInvalid[error: SizeError, page: p, entry: NIL];
pP ← @dir.base[p];
IF pageTouched[iP] THEN
{SIGNAL BTreeInvalid[error: Cycle, page: p, entry: NIL]; RETURN};
pageTouched[iP] ← TRUE;
IF pP.free THEN
{SIGNAL BTreeInvalid[error: BadPointer, page: parent, entry: NIL]; RETURN};
IF pP.size < DirectoryInternal.emptySize OR pP.size > Environment.wordsPerPage THEN {SIGNAL BTreeInvalid[error: SizeError, page: p, entry: NIL]; RETURN};
IF pP.size = DirectoryInternal.emptySize AND (pP.parent # DirectoryInternal.nilPagePointer) THEN
{SIGNAL BTreeInvalid[error: SizeError, page: p, entry: NIL]; RETURN};
IF pP.parent # parent THEN
{SIGNAL BTreeInvalid[error: BadPointer, page: p, entry: NIL]; RETURN};
leafPage ← pP.lastPointer = DirectoryInternal.nilPagePointer;
size ← DirectoryInternal.emptySize;
pE ← LOOPHOLE[@pP.entries]; -- pE ← FirstEntry[pP];
WHILE size < pP.size DO
IF (pE.name.length > pE.name.maxlength) OR (pE.name.length > (Directory.maxDirectoryNameLength+1)) OR (pE.name.length = 0) THEN
{SIGNAL BTreeInvalid[error: SizeError, page: p, entry: pE]; RETURN}; -- "+1" allows trailing Ascii.BEL on subdirectory names
IF pE.pointer # DirectoryInternal.nilPagePointer THEN {
IF leafPage THEN SIGNAL BTreeInvalid[error: LeafError, page: p, entry: pE];
ValidatePage[p: pE.pointer, parent: p]}
ELSE IF ~ leafPage THEN SIGNAL BTreeInvalid[error: LeafError, page: p, entry: pE];
size ← size + DirectoryInternal.overhead + SIZE[StringBody[pE.name.length]]; --size ← size + EntrySize[pE];
pE ← pE + DirectoryInternal.overhead + SIZE[StringBody[pE.name.length]]; -- pE ← NextEntry[pE];
ENDLOOP;
IF ~ leafPage THEN ValidatePage[p: pP.lastPointer, parent: p];
RETURN
END; -- ValidatePage
ValidatePage[p: dir.top, parent: DirectoryInternal.nilPagePointer];
pPage ← FIRST[DirectoryInternal.PagePointer];
iPage ← 0;
THROUGH [0..dir.size) DO -- test for orphan pages
IF ~dir.base[pPage].free AND ~pageTouched[iPage] THEN
SIGNAL BTreeInvalid[error: Orphan, page: pPage, entry: NIL];
pPage ← pPage + Environment.wordsPerPage;
iPage ← iPage + 1;
ENDLOOP;
RETURN
END; -- ValidateBTree
END.
LOG
Time: December 17, 1980 3:56 PMBy: FayAction: Created file.
Time: DateTimeBy: NameAction: Short Description.