-- AlpineDirectoryBTreeImpl.mesa
-- Last Edited by: Maxwell, November 23, 1983 11:13 am
Last Edited by: Hauser, December 18, 1984 4:36:55 pm PST
DIRECTORY
AlpineDirectory,
AlpineDirectoryBTree,
AlpineEnvironment,
AlpFile USING [Create, Handle, Open, WriteProperties],
AlpInstance USING [AccessFailed],
AlpTransaction USING [GetNextVolumeGroup, Handle, ReadNextOwner, ReadOwnerProperties, WriteOwnerProperties],
Ascii USING [Upper],
BTree USING [Compare, DeleteKey, Entry, EntrySize, EnumerateEntries, Error, New, NewPathStk, Open, ReadEntry, Relation, Tree, UpdateEntry],
BTreeAlpineVM USING [Handle, Open, ReferencePage, ReleasePage, ReOpen],
Convert USING [RopeFromCard],
IO USING [Error, GetCard, RIS],
PrincOps USING [wordsPerPage],
PrincOpsUtils USING [LongCOPY],
Process USING [Detach],
Rope USING [Cat, Equal, Find, Fetch, Flatten, FromRefText, Length, Match, ROPE, RopeRep, Substr, Text],
SafeStorage USING [EnableFinalization, EstablishFinalization, FinalizationQueue, FQNext, NewFQ];
AlpineDirectoryBTreeImpl:
CEDAR
MONITOR
IMPORTS AlpFile, AlpInstance, AlpTransaction, AlpineDirectory, Ascii, BTree, BTreeAlpineVM, Convert, IO, PrincOpsUtils, Process, Rope, SafeStorage
EXPORTS AlpineDirectory, AlpineDirectoryBTree
SHARES Rope = BEGIN
OPEN AE: AlpineEnvironment, AD: AlpineDirectory, ADBTree: AlpineDirectoryBTree;
-- **********************************************************
-- general operations
-- **********************************************************
ReadEntry:
PUBLIC
PROC
[trans: AlpTransaction.Handle, name: Rope.ROPE, defaultVersion, desiredVersion: AD.Version]
RETURNS[entry: ADBTree.EntryHandle] = BEGIN
key: REF KeyObject;
relation: BTree.Relation ← equal;
Read:
UNSAFE
PROC [e: BTree.Entry] =
UNCHECKED
BEGIN
entryPtr: EntryPtr = LOOPHOLE[e];
IF entryPtr # NIL AND EntryNameMatches[entry.nameBody, entryPtr]
THEN
BEGIN
entry.found ← TRUE;
entry.keep ← entryPtr.keep;
entry.version ← entryPtr.version;
entry.nameBody ← GetText[entryPtr, entryPtr.nameBody]; -- to get capitalization
entry.directory ← Equal[entry.nameBody, directoryName];
entry.name ← FullPathName[entry];
WITH e: entryPtr^
SELECT
FROM
link => {entry.link ← GetText[entryPtr, e.link]; entry.file ← AE.nullUniversalFile};
file => {entry.link ← NIL; entry.file ← e.file};
ENDCASE => ERROR;
END;
END;
entry ← GetEntryHandle[trans, name, defaultVersion]; -- creates one if none exists
IF desiredVersion = AD.highest THEN entry.desiredVersion ← AD.highest;
IF desiredVersion = AD.lowest THEN entry.desiredVersion ← AD.lowest;
IF entry.desiredVersion = AD.highest THEN relation ← lessEqual;
IF entry.desiredVersion = AD.lowest THEN relation ← greaterEqual;
entry.found ← FALSE;
key ← NewKey[entry.desiredVersion, entry.nameBody];
TRUSTED {BTree.ReadEntry[entry.btree.tree, key, relation, entry.pathStk, entry.usePathStk, Read
! BTree.Error => AD.Error[damagedDirectory]]};
FreeKey[key];
END;
WriteEntry:
PUBLIC
PROC
[entry: ADBTree.EntryHandle] = BEGIN
size: CARDINAL;
key: REF KeyObject;
WriteLink:
UNSAFE
PROC[e: BTree.Entry] =
UNCHECKED
BEGIN
linkPtr: LONG POINTER TO EntryObject.link = LOOPHOLE[e];
IF linkPtr = NIL THEN RETURN;
linkPtr^ ← [SIZE[EntryObject.link], entry.keep, entry.version, , link[LOOPHOLE[NIL]]];
linkPtr.nameBody ← AppendText[linkPtr, entry.nameBody];
linkPtr.link ← AppendText[linkPtr, entry.link];
END;
WriteFile:
UNSAFE
PROC[e: BTree.Entry] =
UNCHECKED
BEGIN
filePtr: LONG POINTER TO EntryObject.file = LOOPHOLE[e];
IF filePtr = NIL THEN RETURN;
filePtr^ ← [SIZE[EntryObject.file], entry.keep, entry.version, , file[entry.file]];
filePtr.nameBody ← AppendText[filePtr, entry.nameBody];
END;
IF entry.directory THEN RETURN;
key ← NewKey[entry.version, entry.nameBody];
size ← SIZE[TextRep[entry.nameBody.length]];
IF entry.link #
NIL
THEN
TRUSTED {
size ← size + SIZE[EntryObject.link] + SIZE[TextRep[entry.link.length]];
BTree.UpdateEntry[entry.btree.tree, key, entry.pathStk, entry.usePathStk, size, WriteLink
! BTree.Error => AD.Error[damagedDirectory]]}
ELSE
TRUSTED {
size ← size + SIZE[EntryObject.file];
BTree.UpdateEntry[entry.btree.tree, key, entry.pathStk, entry.usePathStk, size, WriteFile
! BTree.Error => AD.Error[damagedDirectory]]};
FreeKey[key];
END;
DeleteEntry:
PUBLIC
PROC
[entry: ADBTree.EntryHandle] = BEGIN
found: BOOLEAN;
key: REF KeyObject;
IF entry.directory THEN RETURN;
key ← NewKey[entry.version, entry.nameBody];
found ← BTree.DeleteKey[entry.btree.tree, key, entry.pathStk, entry.usePathStk
! BTree.Error => AD.Error[damagedDirectory]];
FreeKey[key];
END;
NextEntry:
PUBLIC
PROC
[trans: AlpTransaction.Handle, pattern, start: Rope.ROPE, defaultVersion: AD.Version ← AD.all]
RETURNS [entry: ADBTree.EntryHandle] = BEGIN
subDirectories: BOOL ← FALSE;
Get an entry handle corresponding to start.
IF start =
NIL
THEN entry ← FirstOwner[trans, pattern, defaultVersion] -- <Owner>NIL
ELSE entry ← GetEntryHandle[trans, start, defaultVersion];
IF entry = NIL THEN RETURN[NIL]; -- FirstOwner returned NIL
See if we need to reparse the pattern.
IF ~Equal[entry.pattern, pattern]
THEN {
[entry.pVolume, entry.pOwner, entry.pNameBody, entry.pVersion] ←
ParseName[pattern, defaultVersion, TRUE];
entry.pattern ← pattern};
Are we just enumerating top level directories?
IF entry.pNameBody.Length[] = 0
THEN {
IF start # NIL THEN entry ← NextOwner[entry];
IF entry # NIL THEN entry.found ← TRUE;
RETURN[entry]};
Are we just enumerating subdirectories?
SELECT entry.pNameBody.text[entry.pNameBody.length-1]
FROM
'>, '/ => subDirectories ← TRUE;
ENDCASE => subDirectories ← FALSE;
Enumerate to get the next entry.
entry.found ← FALSE;
WHILE
TRUE
DO
IF subDirectories
THEN entry ← NextSubDirectory[entry]
ELSE entry ← NextEntryInThisDirectory[entry];
IF entry.found THEN EXIT;
entry ← NextOwner[entry];
IF entry = NIL THEN EXIT;
ENDLOOP;
END;
NextEntryInThisDirectory:
PROC
[entry: ADBTree.EntryHandle]
RETURNS[ADBTree.EntryHandle] = BEGIN
key: REF KeyObject;
Next:
UNSAFE
PROC[e: BTree.Entry]
RETURNS[continue:
BOOLEAN] =
UNCHECKED
BEGIN
entryPtr: EntryPtr = LOOPHOLE[e, EntryPtr];
IF entryPtr = NIL THEN RETURN[FALSE];
IF ~Rope.Match[entry.pNameBody,
LOOPHOLE[@entryPtr[entryPtr.nameBody]],
FALSE]
THEN RETURN[TRUE];
entry.found ← TRUE;
entry.keep ← entryPtr.keep;
entry.version ← entryPtr.version;
entry.desiredVersion ← entryPtr.version;
entry.nameBody ← GetText[entryPtr, entryPtr.nameBody];
entry.directory ← Equal[entry.nameBody, directoryName];
entry.name ← FullPathName[entry];
WITH e: entryPtr^
SELECT
FROM
link => {entry.link ← GetText[entryPtr, e.link]; entry.file ← AE.nullUniversalFile};
file => {entry.link ← NIL; entry.file ← e.file};
ENDCASE => ERROR;
RETURN[FALSE];
END;
Get then next name or the next entry.
IF entry.pVersion = AD.lowest
OR entry.pVersion = AD.highest
THEN key ← NewKey[AD.highest, entry.nameBody] -- get the next name
ELSE key ← NewKey[entry.version, entry.nameBody]; -- get the next entry
TRUSTED {[] ← BTree.EnumerateEntries[
entry.btree.tree, key, greater, entry.pathStk, entry.usePathStk, Next
! BTree.Error => AD.Error[damagedDirectory]]};
FreeKey[key];
IF ~entry.found THEN RETURN[entry]; -- terminate the enumeration
IF entry.pVersion = AD.highest
THEN
TRUSTED {
-- get the highest version of the new name
key ← NewKey[AD.highest, entry.nameBody];
[] ← BTree.EnumerateEntries[
entry.btree.tree, key, less, entry.pathStk, entry.usePathStk, Next
! BTree.Error => AD.Error[damagedDirectory]];
FreeKey[key]};
RETURN[entry];
END;
NextSubDirectory:
PROC
[entry: ADBTree.EntryHandle]
RETURNS[ADBTree.EntryHandle] = BEGIN
key: REF KeyObject;
Next:
UNSAFE
PROC[e: BTree.Entry]
RETURNS[continue:
BOOLEAN] =
UNCHECKED
BEGIN
directoryPart: Rope.ROPE;
lastBracket, temp: INT ← -1;
entryPtr: EntryPtr = LOOPHOLE[e, EntryPtr];
IF entryPtr = NIL THEN RETURN[FALSE];
WHILE
TRUE
DO
temp ← Rope.Find[LOOPHOLE[@entryPtr[entryPtr.nameBody]], ">", lastBracket+1];
IF temp # -1 THEN lastBracket ← temp ELSE EXIT;
ENDLOOP;
IF lastBracket = -1 THEN RETURN[TRUE]; -- no subdirectories
directoryPart ← Rope.Substr[LOOPHOLE[@entryPtr[entryPtr.nameBody]], 0, lastBracket+1];
IF Equal[entry.nameBody, directoryPart] THEN RETURN[TRUE]; -- already seen
IF ~Rope.Match[entry.pNameBody, directoryPart, FALSE] THEN RETURN[TRUE];
We found a new subdirectory.
entry.found ← TRUE;
entry.desiredVersion ← entry.version ← 0;
entry.nameBody ← Rope.FromRefText[LOOPHOLE[directoryPart]]; -- copy it out of the btree.
entry.name ← FullPathName[entry];
entry.file ← AE.nullUniversalFile;
entry.directory ← FALSE;
entry.link ← NIL;
entry.keep ← 0;
RETURN[FALSE];
END;
key ← NewKey[AD.highest, entry.nameBody];
TRUSTED {[] ← BTree.EnumerateEntries[
entry.btree.tree, key, greater, entry.pathStk, entry.usePathStk, Next
! BTree.Error => AD.Error[damagedDirectory]]};
FreeKey[key];
RETURN[entry];
END;
FirstOwner:
PROC
[trans: AlpTransaction.Handle, pattern: Rope.ROPE, defaultVersion: AD.Version ← AD.all]
RETURNS[entry: ADBTree.EntryHandle] = INLINE BEGIN
version: AD.Version;
volGroupID: AE.VolumeGroupID;
none: AE.OwnerPropertySet ← ALL[FALSE];
volume, owner, nameBody, actualOwner: Rope.Text;
[volume, owner, nameBody, version] ← ParseName[pattern, defaultVersion, TRUE];
volGroupID ← GetVolume[trans, volume];
IF Rope.Find[owner, "*"] < 0
THEN actualOwner ← owner
ELSE
WHILE
TRUE
DO
next: Rope.ROPE;
TRUSTED {next ← AlpTransaction.ReadNextOwner[trans, volGroupID, next, none].owner};
IF next = NIL THEN EXIT;
IF Rope.Match[owner, next, FALSE] THEN {actualOwner ← Rope.Flatten[next]; EXIT};
ENDLOOP;
IF actualOwner = NIL THEN RETURN[NIL];
Create a new entry handle for that owner.
entry ← NewEntryHandle[trans, volume, actualOwner, NIL];
entry.pattern ← pattern;
entry.pVolume ← volume;
entry.pOwner ← owner;
entry.pNameBody ← nameBody;
entry.pVersion ← version;
entry.volGroupID ← volGroupID;
END;
NextOwner:
PROC
[entry: ADBTree.EntryHandle]
RETURNS[next: ADBTree.EntryHandle] = BEGIN
nextOwner: Rope.ROPE;
none: AE.OwnerPropertySet ← ALL[FALSE];
IF Rope.Find[entry.pOwner, "*"] < 0 THEN RETURN[NIL];
WHILE
TRUE
DO
TRUSTED {nextOwner ← AlpTransaction.ReadNextOwner[entry.trans, entry.volGroupID, entry.owner, none].owner};
IF nextOwner = NIL THEN EXIT;
IF Rope.Match[entry.pOwner, nextOwner, FALSE] THEN EXIT;
ENDLOOP;
IF nextOwner #
NIL
THEN {
next ← NewEntryHandle[entry.trans, entry.pVolume, Rope.Flatten[nextOwner], NIL];
next.pattern ← entry.pattern;
next.pVolume ← entry.pVolume;
next.pOwner ← entry.pOwner;
next.pNameBody ← entry.pNameBody;
next.pVersion ← entry.pVersion};
FreeEntryHandle[entry];
END;
GetVolume:
PROC
[trans: AlpTransaction.Handle, volume: Rope.ROPE]
RETURNS[volGroupID: AE.VolumeGroupID] = TRUSTED BEGIN
For now, assume that there is only one volume group per server.
volGroupID ← AlpTransaction.GetNextVolumeGroup[trans];
IF AlpTransaction.GetNextVolumeGroup[trans, volGroupID] # AE.nullVolumeGroupID THEN ERROR;
END;
ParseName:
PROC
[name: Rope.ROPE, defaultVersion: AD.Version ← AD.highest, pattern: BOOLEAN ← FALSE]
RETURNS[volume, owner, nameBody: Rope.Text, version: AD.Version ← 1] = BEGIN
index: CARDINAL;
badName: AD.ErrorType;
text, versionName: Rope.Text;
NextPart:
PROC[text: Rope.Text, index:
CARDINAL, c1, c2:
CHAR, pattern:
BOOLEAN]
RETURNS[part: Rope.Text, newIndex: CARDINAL] = BEGIN
FOR i:
CARDINAL
IN [index..text.length)
DO
IF text.text[i] = c1
OR text.text[i] = c2
THEN {
IF i = index THEN RETURN[NIL, 0]; -- a nil string
RETURN[Rope.Flatten[name, index, i-index], i+1]};
IF ~IsLegal[text.text[i]] THEN AD.Error[badName];
IF ~pattern AND text.text[i] = '* THEN AD.Error[badName];
IF c1 # '! AND (text.text[i] = '/ OR text.text[i] = '>) THEN AD.Error[badName];
ENDLOOP;
IF text.length = index THEN RETURN[NIL, 0];
RETURN[Rope.Flatten[name, index, text.length - index], text.length];
END;
The name will usually be a Rope.Text since that is what RPC produces.
name ← Rope.Flatten[name];
text ← NARROW[name];
extract the volume name
badName ← IF pattern THEN illegalPattern ELSE illegalFileName;
IF text = NIL OR text.length = 0 THEN AD.Error[badName];
SELECT text.text[0] FROM '/, '[ => NULL; ENDCASE => AD.Error[badName];
[volume, index] ← NextPart[text, 1, '/, '], FALSE]; -- '* is always illegal in the volume name
IF volume = NIL THEN AD.Error[badName];
extract the owner
IF index >= text.length THEN AD.Error[badName];
IF text.text[index] = '< THEN index ← index + 1;
[owner, index] ← NextPart[text, index, '/, '>, pattern];
IF owner = NIL THEN AD.Error[badName];
extract and normalize the nameBody
[nameBody, index] ← NextPart[text, index, '!, '!, pattern];
IF nameBody = NIL THEN IF pattern THEN RETURN ELSE AD.Error[badName];
FOR i:
CARDINAL
IN [0..nameBody.length)
DO
IF nameBody.text[i] = '/ THEN nameBody.text[i] ← '>;
ENDLOOP;
extract the version
[versionName, index] ← NextPart[text, index, ' , ' , pattern];
IF versionName = NIL OR versionName.length = 0 THEN {version ← defaultVersion; RETURN};
IF versionName.length = 1
THEN
SELECT versionName.text[0]
FROM
'H, 'h => {version ← AD.highest; RETURN};
'L, 'l => {version ← AD.lowest; RETURN};
'* => {version ← AD.all; RETURN};
ENDCASE;
version ← IO.GetCard[IO.RIS[versionName] ! IO.Error => AD.Error[badName]];
END;
FullPathName:
PUBLIC
PROC
[entry: ADBTree.EntryHandle]
RETURNS[name: Rope.ROPE] = BEGIN
lastChar: CHAR ← 000C;
length: INT = entry.nameBody.Length[];
IF length # 0 THEN lastChar ← entry.nameBody.Fetch[length-1];
name ← Rope.Cat["[", entry.volume, "]<", entry.owner, ">", entry.nameBody];
IF length = 0 OR lastChar = '> OR lastChar = '/ THEN RETURN; -- a directory or sub-directory
name ← Rope.Cat[name, "!", Convert.RopeFromCard[entry.version]];
END;
IsLegal: PACKED ARRAY CHAR OF BOOL;
InitIsLegal:
PROCEDURE[] =
BEGIN
IsLegal ← ALL [FALSE];
FOR c: CHAR IN ['a .. 'z] DO IsLegal[c] ← TRUE ENDLOOP;
FOR c: CHAR IN ['A .. 'Z] DO IsLegal[c] ← TRUE ENDLOOP;
FOR c: CHAR IN ['0 .. '9] DO IsLegal[c] ← TRUE ENDLOOP;
IsLegal['+] ← TRUE; IsLegal['-] ← TRUE; IsLegal['.] ← TRUE; IsLegal['$] ← TRUE;
IsLegal['/] ← TRUE; IsLegal['>] ← TRUE;
IsLegal['*] ← TRUE; -- legal in patterns
END;
Equal:
PROC
[s1, s2: Rope.ROPE]
RETURNS[BOOL] = INLINE {
RETURN[Rope.Equal[s1, s2, FALSE]]}; -- case is never significant
-- **********************************************************
-- Managing the BTree cache.
-- **********************************************************
For each BTree, there can be at most one BTree handle open per transaction. This constraint is enforced by requiring all BTrees to be obtained through a centralized cache of EntryHandles. In addition to the BTree handle, each ADBTree.EntryHandle caches information that will speed up enumerations. There may be several EntryHandles with the same BTree handle.
cache: REF Cache ← NEW[Cache[cacheSize]];
cacheSize: CARDINAL ← 4;
Cache: TYPE = RECORD[s: SEQUENCE size: NAT OF ADBTree.EntryHandle];
rover: CARDINAL ← cacheSize - 1;
GetEntryHandle:
PROC
[trans: AlpTransaction.Handle, name: Rope.ROPE, defaultVersion: AD.Version]
RETURNS[entry: ADBTree.EntryHandle] = BEGIN
entry ← LookupEntryHandle[trans, name];
IF entry =
NIL
THEN {
desiredVersion: AD.Version;
volume, owner, nameBody: Rope.Text;
[volume, owner, nameBody, desiredVersion] ← ParseName[name, defaultVersion];
entry ← NewEntryHandle[trans, volume, owner, nameBody];
entry.directory ← Equal[nameBody, directoryName];
entry.name ← name;
entry.desiredVersion ← desiredVersion};
END;
LookupEntryHandle:
ENTRY
PROC
[trans: AlpTransaction.Handle, name: Rope.ROPE]
RETURNS[entry: ADBTree.EntryHandle] = BEGIN
FOR i:
CARDINAL
IN [0..cache.size)
DO
IF cache[i] = NIL THEN LOOP;
IF cache[i].trans.transID # trans.transID THEN LOOP;
IF ~Equal[cache[i].name, name] THEN LOOP;
IF InUse[cache[i]] THEN LOOP;
MakeInUse[cache[i]];
RETURN[cache[i]];
ENDLOOP;
END;
NewEntryHandle:
ENTRY
PROC
[trans: AlpTransaction.Handle, volume, owner, nameBody: Rope.Text]
RETURNS[entry: ADBTree.EntryHandle] = BEGIN
ENABLE UNWIND => NULL;
index: CARDINAL ← cache.size;
liveBTree: ADBTree.TreeRecord ← [NIL, NIL];
deadBTree: ADBTree.TreeRecord ← [NIL, NIL];
Look for an existing handle that isn't being used.
FOR i:
CARDINAL
IN [0..cache.size)
DO
IF cache[i] = NIL THEN LOOP;
IF cache[i].trans.transID # trans.transID THEN LOOP;
IF ~Equal[cache[i].volume, volume] THEN LOOP;
IF ~Equal[cache[i].owner, owner] THEN LOOP;
IF InUse[cache[i]]
THEN {
-- save btree for later use
IF liveBTree.tree = NIL THEN liveBTree ← cache[i].btree; LOOP};
IF ~Equal[cache[i].nameBody, nameBody] THEN LOOP;
MakeInUse[cache[i]];
RETURN[cache[i]];
ENDLOOP;
Find a place in the cache for a new entry handle.
FOR i:
CARDINAL
IN [0..2*cache.size)
DO
rover ← (rover + 1) MOD cache.size;
IF cache[rover] = NIL THEN {index ← rover; EXIT};
IF InUse[cache[rover]] THEN LOOP;
IF ~cache[rover].recentlyInUse THEN {index ← rover; EXIT};
cache[rover].recentlyInUse ← FALSE;
ENDLOOP;
IF index = cache.size
THEN {
-- extend the cache
temp: REF Cache ← NEW[Cache[cache.size+4]];
FOR i: NAT IN [0..cache.size) DO temp[i] ← cache[i]; ENDLOOP;
cache ← temp};
Flush out the old entry.
IF cache[index] #
NIL
THEN {
deadBTree ← cache[index].btree;
FOR i:
CARDINAL
IN [0..cache.size)
DO
IF i = index THEN LOOP;
IF cache[i] = NIL THEN LOOP;
IF cache[i].btree.tree # cache[index].btree.tree THEN LOOP;
IF ~InUse[cache[i]] THEN {cache[i].inUse ← NIL; cache[i] ← NIL; LOOP};
deadBTree ← [NIL, NIL]; -- still in use
EXIT; ENDLOOP};
Create an new entry.
entry ← cache[index] ← NEW[ADBTree.EntryRecord ← []];
SafeStorage.EnableFinalization[entry]; -- Finalization is incorrect. Disable until fixed.
entry.trans ← trans;
entry.owner ← owner;
entry.volume ← volume;
entry.nameBody ← nameBody;
entry.volGroupID ← GetVolume[trans, volume];
IF liveBTree.tree #
NIL
THEN entry.btree ← liveBTree -- obtained from another entry
ELSE entry.btree ← OpenBTree[trans, entry.volGroupID, owner, deadBTree !
ANY => { cache[index] ← NIL; REJECT } ];
entry.pathStk ← BTree.NewPathStk[];
entry.usePathStk ← TRUE;
MakeInUse[entry];
END;
FreeEntryHandle:
PUBLIC
ENTRY
PROC
[entry: ADBTree.EntryHandle] = BEGIN
IF entry = NIL THEN RETURN;
IF ~InUse[entry] THEN ERROR;
entry.link ← NIL;
entry.file ← AE.nullUniversalFile;
entry.recentlyInUse ← TRUE;
MakeFree[entry];
END;
InUse:
PROC
[entry: ADBTree.EntryHandle] RETURNS[BOOLEAN] = INLINE {RETURN[entry.inUse = NIL]};
MakeInUse:
PROC
[entry: ADBTree.EntryHandle] = INLINE {entry.inUse ← NIL};
MakeFree:
PROC
[entry: ADBTree.EntryHandle] = INLINE {entry.inUse ← entry};
FinalizationProcess:
PROC =
BEGIN
entry: ADBTree.EntryHandle;
DO entry ←
NARROW[SafeStorage.FQNext[finalizationQ]];
FreeEntryHandle[entry];
ENDLOOP;
END;
finalizationQ: SafeStorage.FinalizationQueue;
InitializeFinalization:
PROC =
BEGIN
finalizationQ ← SafeStorage.NewFQ[10];
SafeStorage.EstablishFinalization[CODE[ADBTree.EntryRecord], 1, finalizationQ];
TRUSTED {Process.Detach[FORK FinalizationProcess[]]};
END;
-- **********************************************************
-- Global BTree operations
-- **********************************************************
directoryName: Rope.Text = "$$$.btree";
directoryVersion: AD.Version = 1;
CreateDirectory:
PUBLIC
PROC
[trans: AlpTransaction.Handle, volume: Rope.ROPE, owner: AE.OwnerName] = BEGIN
[] ← OpenBTree[trans, GetVolume[trans, volume], owner, [NIL, NIL], TRUE];
END;
GetDirectory:
PUBLIC
PROC
[trans: AlpTransaction.Handle, volume: Rope.ROPE, owner: AE.OwnerName]
RETURNS[directory: AE.UniversalFile] = BEGIN
props: LIST OF AE.OwnerPropertyValuePair;
propertySet: AE.OwnerPropertySet ← ALL[FALSE];
Look for an existing directory file.
propertySet[rootFile] ← TRUE;
TRUSTED {props ← AlpTransaction.ReadOwnerProperties[trans, GetVolume[trans, volume], owner, propertySet]};
IF props #
NIL
THEN
TRUSTED {
WITH p: props.first
SELECT
FROM
rootFile => directory ← p.rootFile;
ENDCASE => ERROR};
END;
OpenBTree:
PROC
[trans: AlpTransaction.Handle, volGroupID: AE.VolumeGroupID, owner: Rope.ROPE, btree: ADBTree.TreeRecord, initialize: BOOL ← FALSE]
RETURNS[ADBTree.TreeRecord] = BEGIN
fileID: AE.FileID ← AE.nullFileID;
file: AE.UniversalFile ← AE.nullUniversalFile;
openFileID: AlpFile.Handle ← NIL;
file ← GetDirectory[trans, NIL, owner];
Create a new directory file.
IF file = AE.nullUniversalFile
THEN
TRUSTED {
fileRef: REF AE.UniversalFile ← NIL;
[openFileID, fileRef] ← AlpFile.Create[trans, volGroupID, owner, 20];
AlpFile.WriteProperties[openFileID, LIST[[stringName[directoryName]]]];
file ← fileRef^;
initialize ← TRUE};
The following try to open readWrite, followed by an open readOnly if the first failed is a kludge of the first order. Need a way to open with maximum permission allowed. Also, there may be bad effects of having the directory open readOnly and cached. Investigate this! -- Carl Hauser January 18, 1985
IF openFileID =
NIL
THEN
TRUSTED {
[openFileID, fileID] ← AlpFile.Open[trans, file, readWrite !
AlpInstance.AccessFailed => { [openFileID, fileID] ← AlpFile.Open[trans, file, readOnly];
CONTINUE }]
};
Write the file back into the owner data base.
IF file.fileID # fileID
THEN
TRUSTED {
IF fileID # AE.nullFileID THEN file.fileID ← fileID;
AlpTransaction.WriteOwnerProperties[trans, volGroupID, owner, FALSE, LIST[[rootFile[file]]]]};
Open the BTree.
IF btree.tree =
NIL
THEN {
btree.tree ← BTree.New[
repPrim: [compare: Compare, entrySize: EntrySize],
storPrim: [BTreeAlpineVM.ReferencePage, BTreeAlpineVM.ReleasePage]]};
IF btree.storage =
NIL
THEN btree.storage ← BTreeAlpineVM.Open[openFileID, pageSize, 8, 1]
ELSE BTreeAlpineVM.ReOpen[btree.storage, openFileID, 1]; -- reuse backing VM
BTree.Open[
tree: btree.tree, storage: btree.storage,
pageSize: pageSize*PrincOps.wordsPerPage,
initialize: initialize ! BTree.Error => GOTO damagedDirectory]; -- badSeal or wrongPageSize
IF initialize
THEN {
size: CARDINAL;
key: REF KeyObject;
WriteEntry:
UNSAFE
PROC[e: BTree.Entry] =
UNCHECKED
BEGIN
filePtr: LONG POINTER TO EntryObject.file = LOOPHOLE[e];
IF filePtr = NIL THEN RETURN;
filePtr^ ← [SIZE[EntryObject.file], 0, directoryVersion, , file[file]];
filePtr.nameBody ← AppendText[filePtr, directoryName];
END;
-- put the directory file in the directory
key ← NEW[KeyObject ← [directoryVersion, directoryName]];
size ← SIZE[TextRep[directoryName.Length[]]] + SIZE[EntryObject.file];
TRUSTED {BTree.UpdateEntry[btree.tree, key,
NIL,
FALSE, size, WriteEntry
! BTree.Error => GOTO damagedDirectory]};
FreeKey[key]};
initialize ← FALSE;
RETURN[btree];
EXITS damagedDirectory => ERROR AD.Error[damagedDirectory];
END;
-- **********************************************************
-- Key representation
-- **********************************************************
KeyObject:
TYPE =
RECORD[version: AD.Version, nameBody: Rope.Text];
stockKey: REF KeyObject ← NIL;
NewKey:
ENTRY
PROC
[version: AD.Version, nameBody: Rope.Text]
RETURNS[key: REF KeyObject] = BEGIN
IF nameBody = NIL THEN RETURN[NIL];
IF stockKey = NIL THEN stockKey ← NEW[KeyObject];
key ← stockKey;
stockKey ← NIL;
key^ ← [version, nameBody];
END;
FreeKey:
PROC
[key: REF KeyObject] = INLINE BEGIN
IF key # NIL THEN stockKey ← key;
END;
-- **********************************************************
-- Entry representation
-- **********************************************************
RecordObject: TYPE = EntryObject;
EntryObject:
TYPE =
MACHINE
DEPENDENT
RECORD [
-- corresponds to BTree.Entry
size(0): CARDINAL, -- size in words of entire entry, including TextRep's at end
keep(1): CARDINAL, -- cached value of the file's keep
version(2): CARDINAL, -- version part of FName
nameBody(3): TextRP, -- FName w/o version
rest(4):
SELECT type(4): *
FROM
link => [link(5): TextRP], -- includes optional version
file => [file(5): AE.UniversalFile],
ENDCASE
-- here follow the necessary TextRep's
];
EntryPtr: TYPE = LONG BASE POINTER TO EntryObject;
TextRP: TYPE = EntryPtr RELATIVE POINTER TO TextRep;
TextRep: TYPE = Rope.RopeRep.text;
pageSize: NAT = 5;
EntrySize: BTree.EntrySize
-- [entry: BTree.Entry]
-- RETURNS [words: BTree.EntSize] -- = TRUSTED BEGIN
RETURN[LOOPHOLE[entry, EntryPtr].size];
END;
Compare: BTree.Compare
-- [key: BTree.Key, entry: BTree.Entry]
-- RETURNS [PrincOps.Comparison] -- = TRUSTED BEGIN
keyRef: REF KeyObject = NARROW[key];
keyName: Rope.Text = keyRef.nameBody;
entryPtr: EntryPtr = LOOPHOLE[entry, EntryPtr];
entryName: LONG POINTER TO TextRep = @entryPtr[entryPtr.nameBody];
lenKey: CARDINAL = keyName.length;
lenEntry: CARDINAL = entryName.length;
FOR i:
CARDINAL
IN [ 0 ..
MIN[lenKey, lenEntry] )
DO
cKey: CHAR = Ascii.Upper[keyName[i]];
cEntry: CHAR = Ascii.Upper[entryName[i]];
SELECT cKey
FROM
< cEntry => RETURN [less];
> cEntry => RETURN [greater];
ENDCASE;
ENDLOOP;
SELECT lenKey
FROM
< lenEntry => RETURN [less];
> lenEntry => RETURN [greater];
ENDCASE =>
SELECT keyRef.version
FROM
< entryPtr.version => RETURN [less];
> entryPtr.version => RETURN [greater];
ENDCASE => RETURN [equal];
END;
EntryNameMatches:
PROC
[nameBody: Rope.Text, entryPtr: EntryPtr]
RETURNS[BOOLEAN] = TRUSTED BEGIN
entryName: LONG POINTER TO TextRep = @entryPtr[entryPtr.nameBody];
IF entryName.length # nameBody.length THEN RETURN[FALSE];
FOR i:
CARDINAL
IN [0 .. nameBody.length)
DO
IF Ascii.Upper[entryName[i]] # Ascii.Upper[nameBody[i]] THEN RETURN[FALSE];
ENDLOOP;
RETURN[TRUE];
END;
AppendText:
PROC
[eP: EntryPtr, text: Rope.Text]
RETURNS [textRP: TextRP] = TRUSTED BEGIN
textRep: LONG POINTER TO TextRep;
size: CARDINAL ← SIZE[TextRep[text.length]];
textRP ← LOOPHOLE[eP.size];
textRep ← @eP[textRP];
PrincOpsUtils.LongCOPY [
from: LOOPHOLE[text],
nwords: size,
to: textRep
];
eP.size ← eP.size+size;
END;
GetText:
PROC
[eP: EntryPtr, textRP: TextRP]
RETURNS[text: Rope.Text] = TRUSTED BEGIN
textRep: LONG POINTER TO TextRep ← @eP[textRP];
size: CARDINAL ← SIZE[TextRep[textRep.length]];
text ← NEW[TextRep[textRep.length]];
PrincOpsUtils.LongCOPY [
from: textRep,
nwords: size,
to: LOOPHOLE[text]
];
END;
InitIsLegal[];
InitializeFinalization[];
END . . .
chh December 18, 1984 Enumerate doesn't work right for patterns without version numbers. It may return the specified previous file which is, of course, incorrect. I have NOT fixed this problem.