-- DirectoryTreesImpl.mesa (last edited by: Keith on: January 14, 1981 3:23 PM)
-- Schmidt March 16, 1983 2:11 pm

DIRECTORY
Ascii,
Directory,
DirectoryContexts USING [ContextSpace],
DirectoryFiles,
DirectoryInternal,
DirectoryTrees,
Environment USING [wordsPerPage],
File USING [Capability, GetSize, nullCapability, PageCount, SetSize, Unknown],
Inline USING [LongCOPY, LowHalf],
LongString USING[EquivalentStrings],
Space USING [Create, ForceOut, GetHandle, Handle, LongPointer, Map, PageFromLongPointer, Unmap,
virtualMemory],
Volume USING [InsufficientSpace];

DirectoryTreesImpl: PROGRAM
IMPORTS Directory, DirectoryContexts, DirectoryFiles, File, Inline, LongString, Space, Volume
EXPORTS DirectoryTrees =
-- This module implements the operations on the directory B-Tree and the Directory Tree
BEGIN OPEN DirectoryInternal, DirectoryTrees;

debug: BOOLEAN ← FALSE; -- if TRUE check B-Trees for validity after touching
Invalid: SIGNAL [
btError: BTError, base: DirectoryInternal.DirectoryPageHandle,
page: DirectoryInternal.PagePointer, pE: DirectoryInternal.DirectoryEntryHandle] = CODE;
BTError: TYPE = {badEntry, badPage, cycle, noFile, orphan};

CompareResult: TYPE = {equal, less, greater};
copyWork:
LONG POINTER TO ARRAY [0..Environment.wordsPerPage) OF UNSPECIFIED; -- work area for Copy procedure
copySpace: Space.Handle;

GetNextCache: TYPE = RECORD [
dir: DirectoryPageHandle ← NIL,
lastName: StringBody ← [length: 0, maxlength: Directory.maxDirectoryNameLength, text:],
array: PACKED ARRAY [0.. Directory.maxDirectoryNameLength) OF CHARACTER ← ALL [’ ],
lastpP: PagePointer ← nilPagePointer,
lastpE: DirectoryEntryHandle ← NIL];

gncSize: CARDINAL = 5;
GNCache: TYPE = ARRAY [0.. gncSize) OF GetNextCache;
getNextCache: LONG POINTER TO GNCache;

GetGNCache: PROC [dir: LONG POINTER TO DirectoryDescriptor]
RETURNS [pCache: CARDINAL] =
-- return/load cache value
BEGIN
pFreeCache: [0.. gncSize] ← gncSize;
FOR pCache IN [0.. gncSize) DO
IF getNextCache[pCache].dir = dir.base THEN EXIT;
IF getNextCache[pCache].dir = NIL THEN pFreeCache ← pCache;
REPEAT FINISHED => IF pFreeCache # gncSize THEN {
getNextCache[pFreeCache].dir ← dir.base;
getNextCache[pFreeCache].lastName.length ← 0;
pCache ← pFreeCache};
ENDLOOP;
RETURN
END;

FlushGNCache: PROC [dir: LONG POINTER TO DirectoryDescriptor] =
-- clear entry in Get Next cache
BEGIN
FOR i: CARDINAL IN [0.. gncSize) DO
IF getNextCache[i].dir = dir.base THEN {getNextCache[i].dir ← NIL; EXIT}
ENDLOOP;
RETURN
END;

BTreeEmpty: PUBLIC PROC
[dir: LONG POINTER TO DirectoryDescriptor] RETURNS [BOOLEAN] =
-- B-Tree predicate
BEGIN RETURN [dir.base[dir.top].size = emptySize] END;

BTreeGetNext: PUBLIC PROC
[dir: LONG POINTER TO DirectoryDescriptor,
name, nextName, mask: LONG STRING]
RETURNS [cap: File.Capability] =
-- Stateless enumerator of B-Tree
BEGIN
pE: DirectoryEntryHandle;
pP: PagePointer;
pC: CARDINAL;
ok: BOOLEAN;
MaskFilename: PROCEDURE [file: LONG STRING, fileIndex: CARDINAL, maskIndex: CARDINAL]
RETURNS [outcome: BOOLEAN] =
BEGIN
-- local variables
i, j: CARDINAL;
IF (mask = NIL) OR (mask.length = 0) THEN RETURN [TRUE];
-- process each character in mask
FOR i IN [maskIndex..mask.length) DO
SELECT mask[i] FROM
’* => -- matches any string of zero or more characters
BEGIN
FOR j IN [fileIndex..file.length] DO
IF MaskFilename[file, j, i+1] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
END;
’# => -- matches any single character
IF fileIndex = file.length THEN RETURN[FALSE]
ELSE fileIndex ← fileIndex + 1;
’> =>
IF fileIndex = file.length OR
LowerCase[file[fileIndex]] # LowerCase[Ascii.BEL] THEN
RETURN[FALSE]
ELSE fileIndex ← fileIndex + 1;
ENDCASE =>
IF fileIndex = file.length OR
LowerCase[file[fileIndex]] # LowerCase[mask[i]] THEN
RETURN[FALSE]
ELSE fileIndex ← fileIndex + 1;
ENDLOOP;
-- filename passes mask if entire filename has been consumed
outcome ← fileIndex = file.length;
END;
IF dir.base[dir.top].size = emptySize THEN {nextName.length←0; RETURN[File.nullCapability]};
pC ← GetGNCache[dir];
IF name.length = 0 THEN {
pE ← FirstEntry[@dir.base[dir.top]]; pP ← dir.top;
WHILE pE.pointer # nilPagePointer DO
pP←pE.pointer; pE←FirstEntry[@dir.base[pP]] ENDLOOP}
ELSE IF LongString.EquivalentStrings[name, @getNextCache[pC].lastName] THEN
[pE, pP] ← GetNextEntry[dir, getNextCache[pC].lastpE, getNextCache[pC].lastpP]
ELSE {
[ent: pE, page: pP, ok: ok] ← Find[dir, name];
IF ~ok THEN {nextName.length←0; RETURN[File.nullCapability]};
[pE, pP] ← GetNextEntry[dir, pE, pP]};
IF pE = NIL THEN {FlushGNCache[dir]; nextName.length ← 0; RETURN [File.nullCapability]};
WHILE ~MaskFilename[@pE.name, 0, 0] DO
[pE, pP] ← GetNextEntry[dir, pE, pP];
IF pE = NIL THEN {FlushGNCache[dir]; nextName.length ← 0; RETURN [File.nullCapability]};
ENDLOOP;
cap ← pE.cap; MoveLongString[nextName, @pE.name];
MoveLongString[@getNextCache[pC].lastName, @pE.name];
getNextCache[pC].lastpE ← pE; getNextCache[pC].lastpP ← pP;
RETURN
END;

GetNextEntry: PROC [dir: LONG POINTER TO DirectoryDescriptor, pE: DirectoryEntryHandle, pP: PagePointer]
RETURNS [nextpE: DirectoryEntryHandle, nextpP: PagePointer] =
-- given a pointer to a directory entry, get the successor directory entry
BEGIN
IF pE.pointer = nilPagePointer THEN {
nextpE ← NextEntry[pE];
IF nextpE # FirstFreeEntry[@dir.base[pP]] THEN RETURN [nextpE, pP]
ELSE {
WHILE pP # dir.top DO
nextpP ← dir.base[pP].parent;
IF pP # dir.base[nextpP].lastPointer THEN EXIT;
pP ← nextpP;
REPEAT FINISHED => RETURN [NIL, nilPagePointer];
ENDLOOP;
FOR pE ← FirstEntry[@dir.base[nextpP]], NextEntry[pE]
UNTIL pE.pointer = pP DO ENDLOOP};
RETURN[pE, nextpP]}
ELSE {
nextpP ← Successor[dir, pP, pE].pg;
nextpE ← FirstEntry[@dir.base[nextpP]];
RETURN}
END;

BTreeFind: PUBLIC PROC [dir: LONG POINTER TO DirectoryDescriptor, name: LONG STRING]
RETURNS [ok: BOOLEAN, cap: File.Capability, isSD: BOOLEAN,
ent: DirectoryEntryHandle] =
-- Given a file name, return the capability and whether it is a subdirectory or not
BEGIN
nameWithBEL: LONG STRING ← LOOPHOLE[copyWork];
[ok: ok, cap: cap, ent: ent] ← Find[dir, name];
IF ok THEN RETURN [TRUE, cap, FALSE, ent];
nameWithBEL↑ ← StringBody[length: 0, maxlength: Directory.maxDirectoryNameLength+1, text: ];
MoveLongString[to: nameWithBEL, from: name];
nameWithBEL[nameWithBEL.length] ← Ascii.BEL;
nameWithBEL.length ← nameWithBEL.length+1;
[ok: ok, cap: cap, ent: ent] ← Find[dir, nameWithBEL];
IF ok THEN RETURN [TRUE, cap, TRUE, ent];
RETURN [FALSE, File.nullCapability, FALSE, ent];
END;

Find: PROC [dir: LONG POINTER TO DirectoryDescriptor, name: LONG STRING]
RETURNS [
ok: BOOLEAN, cap: File.Capability, page: PagePointer,
ent: DirectoryEntryHandle] =
-- Given a file name, return the capability and pointer to entry
BEGIN
dPage: DirectoryPageHandle;
intDD: DirectoryDescriptor;
pE: DirectoryEntryHandle;
loopSize: CARDINAL ← emptySize;
dPage ← @dir.base[dir.top];
IF dir.top = nilPagePointer THEN
RETURN[FALSE, File.nullCapability, nilPagePointer, NIL];
pE ← FirstEntry[dPage];
WHILE loopSize < dPage.size DO
SELECT StringCompare[name, @pE.name] FROM
= less =>
IF pE.pointer = nilPagePointer THEN
RETURN[FALSE, File.nullCapability, dir.top, NIL]
ELSE {
intDD ← [base: dir.base, top: pE.pointer, size: dir.size, space: dir.space];
[ok, cap, page, ent] ← Find[@intDD, name];
RETURN};
= equal => RETURN[TRUE, pE.cap, dir.top, pE];
ENDCASE;
loopSize ← loopSize + EntrySize[pE];
pE ← NextEntry[pE];
ENDLOOP;
IF dPage.lastPointer = nilPagePointer THEN
RETURN[FALSE, File.nullCapability, dir.top, NIL]
ELSE {
intDD ← [base: dir.base, top: dPage.lastPointer, size: dir.size, space: dir.space];
[ok, cap, page, ent] ← Find[@intDD, name];
RETURN};
END;

BTreeInsert: PUBLIC PROC [
dir: LONG POINTER TO DirectoryDescriptor, name: LONG STRING, cap: File.Capability]
RETURNS [ok, noRoom: BOOLEAN, ent: DirectoryInternal.DirectoryEntryHandle] =
-- insert a file name/capability pair into the B-Tree
BEGIN
found: BOOLEAN;
page: PagePointer;
[ok: found, page: page] ← Find[dir, name];
IF found THEN RETURN[FALSE, FALSE, NIL];
[ok, noRoom, ent] ← InsertInNode[dir, page, name, cap, nilPagePointer];
IF ok THEN FlushGNCache[dir];
IF debug THEN ValidateBTree[dir];
RETURN;
END;

SplitNode: PROC [
dir: LONG POINTER TO DirectoryDescriptor, p: PagePointer, n: LONG STRING,
c: File.Capability, after: PagePointer]
RETURNS [ok, noRoom: BOOLEAN, ent: DirectoryInternal.DirectoryEntryHandle] =
-- split this node into two and insert the mid-entry into the parent node
BEGIN
dPage: DirectoryPageHandle;
newPage: PagePointer;
pNewPage: DirectoryPageHandle;
newPop: PagePointer;
pNewPop: DirectoryPageHandle;
pE, pMid: DirectoryEntryHandle;
midSize: CARDINAL;
middleName: STRING ← [40];
middleCap: File.Capability;
loopSize: CARDINAL ← emptySize;
dPage ← @dir.base[p];
newPage ← NewPage[dir];
IF newPage = nilPagePointer THEN RETURN[FALSE, TRUE, NIL];
pNewPage ← @dir.base[newPage];
IF dPage.parent = nilPagePointer THEN {
newPop ← NewPage[dir];
pNewPop ← @dir.base[newPop];
IF newPop = nilPagePointer THEN RETURN[FALSE, TRUE, NIL]};
-- fill the new page
pE ← FirstEntry[dPage];
WHILE loopSize < dPage.size/2 DO
loopSize ← loopSize + EntrySize[pE]; pE ← NextEntry[pE]; ENDLOOP;
pMid ← pE;
midSize ← loopSize;
MoveLongString[middleName, @pMid.name];
middleCap ← pMid.cap;
loopSize ← loopSize + EntrySize[pE];
pE ← NextEntry[pE];
-- move the rest of the page into the new page
Copy[from: pE, to: @pNewPage.entries, size: dPage.size - loopSize];
-- clean up the two pages
pNewPage.size ← dPage.size - loopSize + emptySize;
dPage.size ← midSize;
pNewPage.lastPointer ← dPage.lastPointer;
dPage.lastPointer ← pMid.pointer;
pNewPage.parent ← dPage.parent;
IF pNewPage.lastPointer # nilPagePointer THEN {
-- change parent pointers in children of new node
dir.base[pNewPage.lastPointer].parent ← newPage;
pE ← FirstEntry[pNewPage];
WHILE pE # FirstFreeEntry[pNewPage] DO
dir.base[pE.pointer].parent ← newPage;
pE ← NextEntry[pE]
ENDLOOP};
-- now the insert will work
IF StringCompare[n, middleName] = less THEN
[ent: ent] ← InsertInNode[dir, p, n, c, after]
ELSE [ent: ent] ← InsertInNode[dir, newPage, n, c, after];
IF dPage.parent = nilPagePointer THEN {
-- the tree has grown out the top
dir.top ← dir.base.top ← newPop;
dPage.parent ← pNewPage.parent ← newPop;
pE ← FirstEntry[pNewPop];
pE↑ ←
[cap:, pointer: p,
name: [length: 0, maxlength: middleName.length, text:]];
MoveLongString[@pE.name, middleName];
pE.cap ← middleCap;
pNewPop.lastPointer ← newPage;
pNewPop.size ← emptySize + overhead + SIZE[StringBody [middleName.length]];
RETURN[TRUE, FALSE, ent]};
[ok: ok, noRoom: noRoom] ← InsertInNode[
dir, dPage.parent, middleName, middleCap, newPage];
RETURN [ok, noRoom, ent]
END;

InsertInNode: PROC [
dir: LONG POINTER TO DirectoryDescriptor, p: PagePointer, n: LONG STRING,
c: File.Capability, after: PagePointer]
RETURNS [ok, noRoom: BOOLEAN, ent: DirectoryInternal.DirectoryEntryHandle] =
-- inserts the file name/cap pair into this node. The field "after" points to the node that follows this entry in the B-Tree
BEGIN
dPage: DirectoryPageHandle;
newEntrySize: CARDINAL;
pE, insertpE: DirectoryEntryHandle;
loopSize: CARDINAL;
dPage ← @dir.base[p];
newEntrySize ← overhead + SIZE[StringBody [n.length]];
IF dPage.size + newEntrySize > Environment.wordsPerPage THEN {
-- this node is full... split into two half-full nodes
[ok, noRoom, ent] ← SplitNode[dir, p, n, c, after];
RETURN};
IF dPage.size = emptySize THEN {
-- this is the first insert in this page
pE ← FirstEntry[dPage];
pE.name ← [length: 0, maxlength: n.length, text:];
MoveLongString[@pE.name, n];
pE.cap ← c;
pE.pointer ← nilPagePointer;
dPage.lastPointer ← after;
dPage.size ← dPage.size + newEntrySize;
RETURN[TRUE, FALSE, pE]};
-- change parent pointer in "after" node
IF after # nilPagePointer THEN dir.base[after].parent ← p;
-- move the other entries over and stick ours in
pE ← FirstEntry[dPage];
loopSize ← emptySize;
WHILE loopSize < dPage.size DO
IF StringCompare[n, @pE.name] = less THEN {
insertpE ← pE + newEntrySize;
Copy[from: pE, to: insertpE, size: dPage.size - loopSize];
pE↑ ←
[cap:, pointer: insertpE.pointer,
name: [length: 0, maxlength: n.length, text:]];
MoveLongString[@pE.name, n];
pE.cap ← c;
insertpE.pointer ← after;
dPage.size ← dPage.size + newEntrySize;
EXIT};
loopSize ← loopSize + EntrySize[pE];
pE ← NextEntry[pE];
REPEAT
FINISHED => {
pE↑ ←
[cap:, pointer: dPage.lastPointer,
name: [length: 0, maxlength: n.length, text:]];
MoveLongString[@pE.name, n];
pE.cap ← c;
dPage.lastPointer ← after;
dPage.size ← dPage.size + newEntrySize}
ENDLOOP;
RETURN[TRUE, FALSE, pE];
END;

BTreeDelete: PUBLIC PROC
[dir: LONG POINTER TO DirectoryInternal.DirectoryDescriptor, name: LONG STRING, doSD: BOOLEAN]
RETURNS [ok: BOOLEAN, cap: File.Capability, isSD: BOOLEAN] =
-- remove an entry from the B-Tree and return the capability
BEGIN
pEntry: DirectoryEntryHandle;
page: PagePointer;
isSD ← FALSE;
[ok: ok, cap: cap, page: page, ent: pEntry] ← Find[dir, name];
IF ~ok THEN RETURN;
isSD ← pEntry.name.text[pEntry.name.length-1] = Ascii.BEL;
IF isSD AND ~doSD THEN RETURN;
Delete[dir, page, pEntry];
FlushGNCache[dir];
IF debug THEN ValidateBTree[dir];
RETURN
END;

Successor: PROC [
dir: LONG POINTER TO DirectoryDescriptor, p: PagePointer,
pE: DirectoryEntryHandle] RETURNS [pg, after: PagePointer] =
-- Finds the successor to a given entry. Also returns the after pointer given entry
BEGIN
IntSucc: PROC [p1: PagePointer] RETURNS [p0: PagePointer] =
BEGIN
nextP: PagePointer;
ipE: DirectoryEntryHandle;
ipE ← FirstEntry[@dir.base[p1]];
nextP ← ipE.pointer;
IF nextP = nilPagePointer THEN RETURN[p1]
ELSE {p0 ← IntSucc[nextP]; RETURN};
END;
testpE: DirectoryEntryHandle;
testpE ← FirstFreeEntry[@dir.base[p]];
pE ← NextEntry[pE];
after ← IF testpE = pE THEN dir.base[p].lastPointer ELSE pE.pointer;
pg ← IntSucc[after];
RETURN;
END;

Delete: PROC [
dir: LONG POINTER TO DirectoryDescriptor, p: PagePointer,
i: DirectoryEntryHandle] =
-- delete node p entry i
BEGIN OPEN dir.base[p];
succPage, after: PagePointer;
pE: DirectoryEntryHandle;
IF i.pointer = nilPagePointer THEN Compress[dir, p, i]
ELSE {
[succPage, after] ← Successor[dir, p, i];
pE ← FirstEntry[@dir.base[succPage]]; -- pointer to successor entry
IF (parent = nilPagePointer) AND (size = emptySize + EntrySize[i]) THEN {
-- this is the parent with one entry... do differently
Copy[
from: @pE.name, to: @i.name, size: SIZE[StringBody [pE.name.length]]];
i.cap ← pE.cap;
size ← emptySize + EntrySize[pE]}
ELSE {
Squeeze[dir, p, i]; -- replace entry with successor entry
[] ← InsertInNode[dir, p, @pE.name, pE.cap, after]};
Delete[dir, succPage, pE] -- Delete the successor entry
};
RETURN
END;

Compress: PROC [
dir: LONG POINTER TO DirectoryDescriptor, p: PagePointer,
pE: DirectoryEntryHandle] =
-- remove entry i from node p, with fill from a brother if necessary
BEGIN
dPage: DirectoryPageHandle;
killer: PagePointer; -- the node of the two brothers with the higher keys
pKiller: DirectoryPageHandle;
filler: PagePointer; -- the node of the two brothers with the lower keys
pFiller: DirectoryPageHandle;
pParent: DirectoryPageHandle;
pPopEntry, pLast, pNext, pChange: DirectoryEntryHandle;
nextSize, loopSize, totalSize, copySize: CARDINAL;
midName: STRING ← [40];
midCap: File.Capability;
dPage ← @dir.base[p];
-- compress out the old entry
Squeeze[dir, p, pE];
IF (dPage.size >= Environment.wordsPerPage/2) OR (dPage.parent = nilPagePointer) THEN
RETURN;
-- the node is too small! fill in from a brother
pParent ← @dir.base[dPage.parent];
-- choose which brother to use. If there is a choice, use the larger one
IF pParent.lastPointer = p THEN {
killer ← p; pPopEntry ← LastEntry[pParent]; filler ← pPopEntry.pointer}
ELSE {
pPopEntry ← FirstEntry[pParent];
IF pPopEntry.pointer = p THEN {
filler ← p;
pNext ← NextEntry[pPopEntry];
killer ←
IF pNext = FirstFreeEntry[pParent] THEN pParent.lastPointer
ELSE pNext.pointer}
ELSE {
pLast ← NextEntry[pPopEntry];
DO
IF pPopEntry.pointer = p THEN EXIT;
pLast ← pPopEntry;
pPopEntry ← NextEntry[pPopEntry];
ENDLOOP;
pNext ← NextEntry[pPopEntry];
killer ← IF pNext=FirstFreeEntry[pParent] THEN pParent.lastPointer
ELSE pNext.pointer;
IF dir.base[pLast.pointer].size < dir.base[killer].size THEN
filler ← p
ELSE {filler ← pLast.pointer; killer ← p; pPopEntry← pLast};
}};
pKiller ← @dir.base[killer];
pFiller ← @dir.base[filler];
nextSize ← EntrySize[pPopEntry];
totalSize ← pKiller.size + pFiller.size + nextSize - emptySize;
IF totalSize <= Environment.wordsPerPage THEN
-- the two brothers can be merged into one node
BEGIN OPEN fill: pFiller, kill: pKiller, pop: pParent;
pFillEnd: DirectoryEntryHandle;
pChange ← pFillEnd ← FirstFreeEntry[pFiller];
Copy[from: pPopEntry, to: pFillEnd, size: nextSize];
pFillEnd.pointer ← fill.lastPointer;
pFillEnd ← pFillEnd + nextSize;
Copy[from: FirstEntry[pKiller], to: pFillEnd, size: kill.size - emptySize];
fill.lastPointer ← kill.lastPointer;
fill.size ← totalSize;
OldPage[dir, killer];
IF fill.lastPointer # nilPagePointer THEN {
-- change parent pointers of new children
dir.base[fill.lastPointer].parent ← filler;
WHILE pChange # FirstFreeEntry[pFiller] DO
dir.base[pChange.pointer].parent ← filler;
pChange ← NextEntry[pChange];
ENDLOOP};
IF dir.top = fill.parent AND pop.size = nextSize + emptySize THEN {
-- this compress shrinks the tree
dir.top ← dir.base.top ← filler;
OldPage[dir, fill.parent];
fill.parent ← nilPagePointer;
RETURN}
ELSE {Compress[dir, fill.parent, pPopEntry]; RETURN}
END
ELSE
-- redistribute the entries so the two nodes have about the same size
BEGIN OPEN fill: pFiller, kill: pKiller, pop: pParent;
IF fill.size > kill.size THEN {
-- move entries into the "higher" page
pLast ← FirstEntry[pFiller];
pNext ← LastEntry[pFiller];
loopSize ← emptySize+EntrySize[pLast];
WHILE loopSize < totalSize/2 DO
pLast ← NextEntry[pLast];
loopSize ← loopSize + EntrySize[pLast];
IF pLast = pNext THEN RETURN; -- leave well enough alone!
ENDLOOP;
loopSize ← loopSize-EntrySize[pLast];
-- save the middle name, capability
MoveLongString[midName, @pLast.name];
midCap ← pLast.cap;
-- make room in the more empty node
copySize ← fill.size - loopSize - EntrySize[pLast] + nextSize;
pChange ← pNext ← FirstEntry[pKiller];
Copy[from: pNext, to: pNext + copySize, size: kill.size - emptySize];
-- move in the entries from the brother
Copy[from: NextEntry[pLast], to: pNext, size: copySize - nextSize];
pNext ← pNext + copySize - nextSize;
-- move parent entry
Copy[from: pPopEntry, to: pNext, size: nextSize];
pNext.pointer ← pFiller.lastPointer;
pFiller.lastPointer ← pLast.pointer;
fill.size ← loopSize;
kill.size ← kill.size + copySize;
IF pKiller.lastPointer # nilPagePointer THEN {
-- change parent pointers of moved children
pNext ← NextEntry[pNext];
WHILE pChange # pNext DO
dir.base[pChange.pointer].parent ← killer;
pChange ← NextEntry[pChange];
ENDLOOP}}
ELSE {
-- move entries into the "lower" page
-- copy the parent entry into the page
pChange ← pNext ← FirstFreeEntry[pFiller];
Copy[from: pPopEntry, to: pNext, size: nextSize];
pNext.pointer ← fill.lastPointer;
-- copy from the brother until the node is about 1/2 full
pLast ← FirstEntry[pKiller];
pNext ← pNext + nextSize;
copySize ← EntrySize[pLast];
loopSize ← fill.size + nextSize + copySize;
WHILE loopSize < totalSize/2 DO
pLast ← NextEntry[pLast];
copySize ← copySize + EntrySize[pLast];
loopSize ← fill.size + nextSize + copySize;
ENDLOOP;
copySize ← copySize -EntrySize[pLast];
Copy[from: FirstEntry[pKiller], to: pNext, size: copySize];
fill.lastPointer ← pLast.pointer;
-- save the new parent name, cap
MoveLongString[midName, @pLast.name];
midCap ← pLast.cap;
--move entries over in page we copied from
Copy[
from: NextEntry[pLast], to: FirstEntry[pKiller],
size: kill.size - copySize - emptySize - EntrySize[pLast]];
fill.size ← fill.size + nextSize + copySize;
kill.size ←
kill.size - copySize - overhead - SIZE[StringBody [midName.length]];
IF pFiller.lastPointer # nilPagePointer THEN {
-- change parent pointers of moved children
dir.base[pFiller.lastPointer].parent ← filler;
WHILE pChange # FirstFreeEntry[pFiller] DO
dir.base[pChange.pointer].parent ← filler;
pChange ← NextEntry[pChange];
ENDLOOP}};
IF (pop.parent = nilPagePointer) AND
(pop.size = emptySize + EntrySize[pPopEntry]) THEN {
-- this is the parent with one entry... do differently
pPopEntry.name ← [length: 0, maxlength: midName.length, text:];
Copy[
from: midName, to: @pPopEntry.name,
size: SIZE[StringBody [midName.length]]];
pPopEntry.cap ← midCap;
pop.size ← emptySize + EntrySize[pPopEntry]}
ELSE {
Squeeze[dir, fill.parent, pPopEntry];
-- replace entry with successor entry
[] ← InsertInNode[dir, fill.parent, midName, midCap, killer]};
END;
RETURN
END;

Squeeze: PROC [
dir: LONG POINTER TO DirectoryDescriptor, p: PagePointer,
pE: DirectoryEntryHandle] =
-- squeeze out the entry pointed to by pE
BEGIN
compress, copy: CARDINAL;
pNext: DirectoryEntryHandle;
compress ← EntrySize[pE];
pNext ← NextEntry[pE];
copy ← dir.base[p].size-Inline.LowHalf[
LOOPHOLE[pNext, LONG CARDINAL]
-LOOPHOLE[@dir.base[p], LONG CARDINAL]];
IF copy # 0 THEN {
pNext.pointer ← pE.pointer;
Copy[from: pNext, to: pE, size: copy]}
ELSE dir.base[p].lastPointer ← pE.pointer;
dir.base[p].size ← dir.base[p].size - compress;
RETURN
END;

Copy: PROC [from: LONG POINTER, to: LONG POINTER, size: CARDINAL] =
-- copy block of words. This routine will do overlapping moves correctly
BEGIN
cFrom, cTo: LONG CARDINAL;
cFrom ← LOOPHOLE[from];
cTo ← LOOPHOLE[to];
IF (cTo > cFrom) AND (cTo < cFrom + size) THEN {
Inline.LongCOPY[from: from, to: copyWork, nwords: size];
Inline.LongCOPY[from: copyWork, to: to, nwords: size]}
ELSE Inline.LongCOPY[from: from, to: to, nwords: size]
END;

FirstEntry: PROC [d: DirectoryPageHandle]
RETURNS [DirectoryEntryHandle] =
-- return pointer to first entry of this page
INLINE {RETURN[LOOPHOLE[@d.entries]]};

FirstFreeEntry: PROC [d: DirectoryPageHandle]
RETURNS [DirectoryEntryHandle] =
-- return pointer to first free entry of this page
INLINE {RETURN[LOOPHOLE[d + d.size]]};

LastEntry: PROC [d: DirectoryPageHandle]
RETURNS [p: DirectoryEntryHandle] =
-- return pointer to last filled entry of this page
BEGIN
l: CARDINAL ← emptySize;
p ← FirstEntry[d];
WHILE l < d.size DO
l ← l + overhead + SIZE[StringBody [p.name.length]];
IF l = d.size THEN EXIT;
p ← NextEntry[p];
ENDLOOP;
RETURN
END;

NextEntry: PROC [p: DirectoryEntryHandle]
RETURNS [DirectoryEntryHandle] =
-- return pointer to next entry in this page
INLINE {RETURN[p + overhead + SIZE[StringBody [p.name.length]]]};

EntrySize: PROC [p: DirectoryEntryHandle] RETURNS [CARDINAL] =
-- returns the size of an entry
INLINE {RETURN[overhead + SIZE[StringBody [p.name.length]]]};

NewPage: PROC [dir: LONG POINTER TO DirectoryDescriptor] RETURNS [p: PagePointer] =
BEGIN
p ← FIRST[PagePointer];
THROUGH [0.. dir.size) DO
IF dir.base[p].free THEN EXIT;
p ← p + Environment.wordsPerPage;
REPEAT FINISHED => {p ← ExpandBTree[dir]; IF p = nilPagePointer THEN RETURN};
ENDLOOP;
dir.base[p].size ← emptySize;
dir.base[p].free ← FALSE;
dir.base[p].lastPointer ← dir.base[p].parent ← nilPagePointer;
dir.base[p].filler ← 0;
Space.ForceOut[dir.space];
RETURN
END;

ExpandBTree: PROC [dir: LONG POINTER TO DirectoryDescriptor] RETURNS [p: PagePointer] =
-- Expand the directory
BEGIN
dirCap: File.Capability ← DirectoryFiles.directoryCache[DirectoryFiles.PDCFromDD[dir]].cap;
pPage: DirectoryInternal.DirectoryPageHandle;
IF dir.size = DirectoryInternal.maxDirSize THEN RETURN [nilPagePointer];
Space.Unmap[dir.space];
File.SetSize[dirCap, dir.size+DirectoryInternal.directoryIncrement+DirectoryInternal.leaderPageSize !
Volume.InsufficientSpace => GOTO NoRoom];
Space.Map[dir.space, [dirCap, DirectoryInternal.leaderPageSize]];
p ← FIRST[PagePointer]+Environment.wordsPerPage*dir.size;
pPage ← @dir.base[p];
THROUGH [0.. DirectoryInternal.directoryIncrement) DO
pPage.free ← TRUE;
pPage ← pPage+Environment.wordsPerPage
ENDLOOP;
dir.size ← dir.size+DirectoryInternal.directoryIncrement;
RETURN [p]
EXITS NoRoom => {Space.Map[dir.space]; RETURN [nilPagePointer];}
END;

OldPage: PROC [dir: LONG POINTER TO DirectoryDescriptor, p: PagePointer] =
BEGIN
dir.base[p].free ← TRUE;
Space.ForceOut[dir.space];
RETURN
END;

StringCompare: PROC [a, b: LONG STRING] RETURNS [relation: CompareResult] =
-- this is a bit convoluted, since we want to use the BEL on the end first
BEGIN
IF a[a.length-1] = Ascii.BEL AND b[b.length-1] # Ascii.BEL THEN RETURN [less] ELSE
IF a[a.length-1] # Ascii.BEL AND b[b.length-1] = Ascii.BEL THEN RETURN [greater];
FOR i: CARDINAL IN [0..a.length) DO
IF i >= b.length THEN {relation ← greater; EXIT};
IF LowerCase[a[i]] < LowerCase[b[i]] THEN {relation ←less; EXIT};
IF LowerCase[a[i]] > LowerCase[b[i]] THEN {relation ← greater; EXIT};
REPEAT
FINISHED => relation ← IF a.length = b.length THEN equal ELSE less;
ENDLOOP;
RETURN [relation];
END;

-- inline version of StringsImplB.LowerCase
LowerCase: PROCEDURE [c: CHARACTER] RETURNS [CHARACTER] = INLINE
BEGIN IF c IN [’A..’Z] THEN c ← c + (’a - ’A); RETURN[c] END;

ValidateBTree: PROC [dir: LONG POINTER TO DirectoryInternal.DirectoryDescriptor] =
-- Perform some tests on this B-Tree
BEGIN
pPage: DirectoryInternal.PagePointer;
ValidatePage: PROC [p: DirectoryInternal.PagePointer] =
-- check this page for validity
BEGIN
pE: DirectoryInternal.DirectoryEntryHandle;
pP: DirectoryInternal.DirectoryPageHandle ← @dir.base[p];
size: CARDINAL;
IF pP.filler # 0 THEN {SIGNAL Invalid[cycle, dir.base, p, NIL]; RETURN};
pP.filler ← 1;
IF pP.free THEN {SIGNAL Invalid[badPage, dir.base, p, NIL]; RETURN};
IF pP.size < emptySize OR pP.size > 256 THEN {SIGNAL Invalid[badPage, dir.base, p, NIL]; RETURN};
IF pP.size = emptySize AND (pP.parent # nilPagePointer) THEN
{SIGNAL Invalid[badPage, dir.base, p, NIL]; RETURN};
size ← emptySize;
pE ← FirstEntry[pP];
WHILE size < pP.size DO
IF pE.cap # File.nullCapability THEN
[] ← File.GetSize[pE.cap ! File.Unknown => {
SIGNAL Invalid[noFile, dir.base, p, pE]; CONTINUE}];
IF pE.pointer # nilPagePointer THEN {
IF pP.lastPointer = nilPagePointer THEN SIGNAL Invalid[badEntry, dir.base, p, pE];
ValidatePage[pE.pointer]}
ELSE IF pP.lastPointer # nilPagePointer THEN SIGNAL Invalid[badEntry, dir.base, p, pE];
size ← size+EntrySize[pE];
pE ← NextEntry[pE];
ENDLOOP;
IF pP.lastPointer # nilPagePointer THEN ValidatePage[dir.base[p].lastPointer];
RETURN
END;
ValidatePage[dir.top];
pPage ← FIRST[DirectoryInternal.PagePointer];
THROUGH [0.. dir.size) DO
IF ~ dir.base[pPage].free AND (dir.base[pPage].filler = 0) THEN SIGNAL Invalid[orphan, dir.base, pPage, NIL];
dir.base[pPage].filler ← 0;
pPage ← pPage + Environment.wordsPerPage;
ENDLOOP;
RETURN
END;

MoveLongString: PUBLIC PROC [to, from: LONG STRING] =
BEGIN
to.length ← MIN[from.length, to.maxlength];
Inline.LongCOPY[to: to+2, from: from+2, nwords: (to.length+1)/2];
RETURN
END;

DTDelete: PUBLIC PROC [pDT: PDT, pDTNode: PDTNode, name: LONG STRING] RETURNS [ok: BOOLEAN] =
-- Delete the named node from the directory tree
BEGIN
pNode, pLast: PDTNode;
pLast ← pDTNode;
FOR pNode ← pDT[pDTNode].son, pDT[pNode].bro UNTIL pNode = pDTNode DO
IF LongString.EquivalentStrings[name, @pDT[pNode].name] THEN EXIT;
pLast ← pNode;
REPEAT FINISHED => RETURN [FALSE];
ENDLOOP;
IF pLast = pDTNode THEN pDT[pLast].son ← pDT[pNode].bro
ELSE pDT[pLast].bro ← pDT[pNode].bro;
pDT[pNode].bro ← pDT.bro;
pDT.bro ← pNode;
RETURN [TRUE]
END;

DTFind: PUBLIC PROC [pDT: PDT, pDTNode: PDTNode, name: LONG STRING] RETURNS [PDTNode] =
-- Find the named node in the directory tree
BEGIN
pNode: PDTNode;
FOR pNode ← pDT[pDTNode].son, pDT[pNode].bro UNTIL pNode = pDTNode DO
IF LongString.EquivalentStrings[name, @pDT[pNode].name] THEN RETURN [pNode];
ENDLOOP;
RETURN [pDTnil];
END;

DTFirst: PUBLIC PROC [pDT: PDT] RETURNS [PDTNode] =
-- Return the first node of the directory tree
BEGIN
RETURN [pDT.son];
END;

DTInsert: PUBLIC PROC [pDT: PDT, pDTNode: PDTNode, name: LONG STRING, cap: File.Capability]
RETURNS [ok, noRoom: BOOLEAN] =
-- Insert a named node in the directory tree
BEGIN
pNode: PDTNode;
FOR pNode ← pDT[pDTNode].son, pDT[pNode].bro UNTIL pNode = pDTNode DO
IF LongString.EquivalentStrings[name, @pDT[pNode].name] THEN RETURN [FALSE, FALSE];
ENDLOOP;
pNode ← FreeDTNode[pDT];
IF pNode = pDTnil THEN RETURN [FALSE, TRUE];
pDT[pNode].son ← pNode;
pDT[pNode].bro ← pDT[pDTNode].son;
pDT[pNode].cap ← cap;
pDT[pNode].level ← pDT[pDTNode].level+1;
pDT[pDTNode].son ← pNode;
MoveLongString[to: @pDT[pNode].name, from: name];
RETURN [TRUE, FALSE];
END;

PDTNext: PUBLIC PROC [pDT: DirectoryInternal.PDT, pDTNode: DirectoryInternal.PDTNode]
RETURNS [pNext: DirectoryInternal.PDTNode] =
-- Returns the next node after pDTNode using a preorder traversal
BEGIN
IF pDT[pDTNode].son # pDTNode THEN RETURN[pDT[pDTNode].son];
pNext ← pDT[pDTNode].bro;
UNTIL pDT[pDTNode].level = pDT[pNext].level DO
pDTNode ← pNext; pNext ← pDT[pDTNode].bro; ENDLOOP;
END;

DTMoveNode: PUBLIC PROC
[pDT: DirectoryInternal.PDT, pDTNode1, pDTNode2: DirectoryInternal.PDTNode] =
-- Moves DTNode pDTNode1 to be an immediate child of pDTNode2
BEGIN
pN: DirectoryInternal.PDTNode;
delta: CARDINAL; -- level difference
IF NOT DTNotSon[pDT, pDTNode1, pDTNode2] THEN ERROR Directory.Error[invalidPathName];
FOR pN ← pDT[pDTNode1].bro, pDT[pN].bro UNTIL pDT[pN].level < pDT[pDTNode1].level
DO -- find parent node -- ENDLOOP;
IF pDT[pN].son = pDTNode1 THEN pDT[pN].son ← pDT[pDTNode1].bro
ELSE {
FOR pN ← pDT[pN].son, pDT[pN].bro UNTIL pDT[pN].bro = pDTNode1
DO -- find previous brother node -- ENDLOOP;
pDT[pN].bro ← pDT[pDTNode1].bro};
pDT[pDTNode1].bro ← pDT[pDTNode2].son;
pDT[pDTNode2].son ← pDTNode1;
-- Level Adjust
delta ← pDT[pDTNode2].level+1-pDT[pDTNode1].level;
pDT[pDTNode1].level ← pDT[pDTNode1].level+delta;
FOR pN ← PDTNext[pDT, pDTNode1], PDTNext[pDT, pN] UNTIL pDT[pN].level <= pDT[pDTNode1].level DO
pDT[pN].level ← pDT[pN].level+delta ENDLOOP;
RETURN
END;

DTNotSon: PROC [pDT: DirectoryInternal.PDT, pDTNode1, pDTNode2: DirectoryInternal.PDTNode]
RETURNS [BOOLEAN] =
-- TRUE if pDTNode1 is not parent of pDTNode2
BEGIN
pN: DirectoryInternal.PDTNode;
IF pDT[pDTNode1].level >= pDT[pDTNode2].level THEN RETURN [TRUE];
IF pDT[pDTNode1].level = 0 THEN RETURN [FALSE]; -- The Root Directory
FOR pN ← PDTNext[pDT, pDTNode1], PDTNext[pDT, pN] UNTIL pDT[pN].level <= pDT[pDTNode1].level DO
IF pN = pDTNode2 THEN RETURN [FALSE] ENDLOOP;
RETURN [TRUE];
END;

FreeDTNode: PROC [pDT: PDT] RETURNS [pDTNode: PDTNode] =
-- Get a Free Directory Tree node
BEGIN
IF pDT.bro = pDTnil THEN pDT.bro ← ExpandDT[pDT];
IF pDT.bro = pDTnil THEN ERROR Directory.Error[notImplemented];
pDTNode ← pDT.bro;
pDT.bro ← pDT[pDT.bro].bro;
RETURN
END;

ExpandDT: PROC [pDT: PDT] RETURNS [PDTNode] =
-- Expand the Directory Tree
BEGIN
pDTNode, pLoop: PDTNode;
dtCap: File.Capability ← pDT.cap;
dtHandle: Space.Handle ← Space.GetHandle[Space.PageFromLongPointer[pDT]];
treeSize: File.PageCount ← File.GetSize[dtCap];
BEGIN
IF treeSize = DirectoryInternal.maxDirSize THEN RETURN [pDTnil];
Space.Unmap[dtHandle];
File.SetSize[dtCap, treeSize+DirectoryInternal.directoryIncrement !
Volume.InsufficientSpace => GOTO NoRoom];
Space.Map[dtHandle, [dtCap, DirectoryInternal.leaderPageSize]];
pDTNode ← pLoop ← LOOPHOLE[Environment.wordsPerPage*Inline.LowHalf[treeSize]];
THROUGH
[0.. SIZE[DirectoryInternal.DTNode]/(Environment.wordsPerPage*DirectoryInternal.directoryIncrement))
DO pDT[pLoop] ← DirectoryInternal.DTNode[]; pLoop ← pLoop+SIZE[DirectoryInternal.DTNode];
ENDLOOP;
RETURN [pDTNode];
EXITS NoRoom => {Space.Map[dtHandle]; RETURN [pDTnil]};
END;
END;

copySpace ← Space.Create[size: 1, parent: Space.virtualMemory];
Space.Map[copySpace];
copyWork ← Space.LongPointer[copySpace];
getNextCache ← DirectoryContexts.ContextSpace.NEW[GNCache ← ALL[] ];

END.




LOG

Time: August 21, 1980 10:45 AM By: KeithAction: Created File

Time: October 8, 1980 11:03 PM By: KeithAction: Fixed DTDelete so free list is maintained correctly.

Time: January 14, 1981 3:36 PM By: Keith Action: Fixed AR 6861, added masking in BTreeGetNext, fixed BTreeFind to find subdirectories correctly, added DTMoveNode and associated procedures (2) and reduced global frame.