<<-- AlpineDirectoryBTreeImpl.mesa>> <<-- Last Edited by: Maxwell, November 23, 1983 11:13 am>> <> 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; <> IF start = NIL THEN entry _ FirstOwner[trans, pattern, defaultVersion] -- NIL ELSE entry _ GetEntryHandle[trans, start, defaultVersion]; IF entry = NIL THEN RETURN[NIL]; -- FirstOwner returned NIL <> IF ~Equal[entry.pattern, pattern] THEN { [entry.pVolume, entry.pOwner, entry.pNameBody, entry.pVersion] _ ParseName[pattern, defaultVersion, TRUE]; entry.pattern _ pattern}; <> IF entry.pNameBody.Length[] = 0 THEN { IF start # NIL THEN entry _ NextOwner[entry]; IF entry # NIL THEN entry.found _ TRUE; RETURN[entry]}; <> SELECT entry.pNameBody.text[entry.pNameBody.length-1] FROM '>, '/ => subDirectories _ TRUE; ENDCASE => subDirectories _ FALSE; <> 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; <> 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]; <> 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]; <> 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 <> 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; <> name _ Rope.Flatten[name]; text _ NARROW[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]; <> 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]; <> [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; <> [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.>> <<-- **********************************************************>> <> <<>> 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]; <> 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; <> 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}; <> IF cache[index] # NIL THEN { <> 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}; <> entry _ cache[index] _ NEW[ADBTree.EntryRecord _ []]; <> 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]; <> 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]; <> 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}; <> IF openFileID = NIL THEN TRUSTED { [openFileID, fileID] _ AlpFile.Open[trans, file, readWrite ! AlpInstance.AccessFailed => { [openFileID, fileID] _ AlpFile.Open[trans, file, readOnly]; CONTINUE }] }; <> IF file.fileID # fileID THEN TRUSTED { IF fileID # AE.nullFileID THEN file.fileID _ fileID; AlpTransaction.WriteOwnerProperties[trans, volGroupID, owner, FALSE, LIST[[rootFile[file]]]]}; <> 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 . . . <>