DIRECTORY
AlpFile,
AlpineEmergency USING [UncaughtThruMonitor, UnwindingMonitor],
AlpineEnvironment,
AlpineFile,
AlpineLog USING [nullRecordID, RecordID],
AlpTransaction,
AlpineTransaction,
BackupBTree USING [Error, Reason],
BackupLog USING [nullRecordID, RecordID],
BasicTime USING [GMT, nullGMT],
BTree,
BTreeAlpineVM USING [Handle, EndLongUpdate, Open, ReferencePage, ReleasePage, ReOpen, StartLongUpdate],
PrincOps USING [wordsPerPage],
PrincOpsUtils USING [LongCopy],
Rope USING [Flatten, Length, ROPE, Text, TextRep],
RuntimeError USING [UNCAUGHT],
ViewRec,
VM;
BackupBTreeImpl: CEDAR MONITOR
IMPORTS
AlpineEmergency, AlpFile, AlpTransaction, BackupBTree, BTree, BTreeAlpineVM, PrincOpsUtils, Rope, RuntimeError, ViewRec, VM
EXPORTS 
BackupBTree
SHARES
Rope
~ BEGIN

OPEN AE: AlpineEnvironment, BB: BackupBTree, RuntimeError;

Error: PUBLIC ERROR[why: BB.Reason] = CODE;

btree: RECORD [
tree: BTree.Tree,
storage: BTreeAlpineVM.Handle,
pathStk: BTree.PathStk
] _ [NIL, NIL, BTree.NewPathStk[]];
	
globals: RECORD [ 
openFile:  AlpFile.Handle,
universalFile: AE.UniversalFile,
trans: AlpTransaction.Handle
];

nullRecordID: BackupLog.RecordID  = BackupLog.nullRecordID;
UniversalFile: TYPE = AlpineEnvironment.UniversalFile;
RecordID: TYPE = BackupLog.RecordID;

OpenForNormalOperation: PUBLIC ENTRY PROC [trans: AlpTransaction.Handle, btreeFile: AE.UniversalFile, initialize: BOOL _ FALSE] ~ TRUSTED {
fileID: AE.FileID _ AE.nullFileID;
globals.universalFile _ btreeFile;
globals.trans _ trans;
[globals.openFile, fileID] _ AlpFile.Open[trans, btreeFile, readWrite];
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[file: globals.openFile, filePagesPerPage: pageSize, cacheSize: 8, base: 1]
ELSE BTreeAlpineVM.ReOpen[handle: btree.storage, file: globals.openFile, base: 1]; -- reuse backing VM
BTree.Open[
tree: btree.tree, storage: btree.storage, 
pageSize: pageSize*PrincOps.wordsPerPage,
maintainRecomputableState: FALSE,
initialize: initialize ! BTree.Error => GOTO damagedBTree]; -- badSeal or wrongPageSize
AlpFile.ReadPages[ handle: globals.openFile, pageRun: positionPageInfo.pageRun, pageBuffer: positionPageInfo.buffer, lock: [read, fail] ! AlpFile.LockFailed => {GOTO Failure} ];
IF initialize THEN {
positionPageInfo.ptr.logRecord _ AlpineLog.nullRecordID;
positionPageInfo.ptr.backupRecord _ BackupLog.nullRecordID;
positionPageInfo.ptr.lastFullyConsistentTime _ BasicTime.nullGMT;
positionPageInfo.ptr.lastFullyConsistentBackupRecord _ BackupLog.nullRecordID;
};
BTreeAlpineVM.StartLongUpdate[btree.storage];
EXITS 
Failure => RETURN WITH ERROR BB.Error[lockFailure];
damagedBTree => RETURN WITH ERROR BB.Error[damagedBTree];
};

BTreeEntry: TYPE ~ REF BTreeEntryObject;
BTreeEntryPtr: TYPE ~ LONG BASE POINTER TO BTreeEntryObject;
BTreeEntryObject: TYPE ~ MACHINE DEPENDENT RECORD [
size(0): CARDINAL, -- size in words of entire entry, including TextRep's at end
universalFile(1): AlpineEnvironment.UniversalFile,
base(10), lastIncrement(13), prevBase(16): BackupLog.RecordID _ nullRecordID,
name(19): TextRP -- FName w/o version,
];

Key: TYPE ~ REF KeyObject;
KeyObject: TYPE ~ RECORD [
universalFile: UniversalFile
];

pageSize: NAT = 4;

SetFileInfo: PUBLIC ENTRY PROC [universalFile: UniversalFile, baseRecord, lastIncrementRecord: RecordID _ nullRecordID, name: Rope.ROPE] ~ TRUSTED {
key: Key _ NewKey[universalFile];
flatName: Rope.Text;
size: CARDINAL _ SIZE[BTreeEntryObject] + SIZE[TextRep[name.Length[]]];
Write: UNSAFE PROC[e: BTree.Entry] = UNCHECKED BEGIN
entry: BTreeEntryPtr = LOOPHOLE[e];
SELECT TRUE FROM
baseRecord = nullRecordID AND lastIncrementRecord # nullRecordID => {
entry.lastIncrement _ lastIncrementRecord;
};
baseRecord # nullRecordID AND lastIncrementRecord = nullRecordID => { 
entry.prevBase _ entry.base;
entry.base _ baseRecord;
};
baseRecord # nullRecordID AND lastIncrementRecord # nullRecordID => {
entry.prevBase _ entry.base;
entry.base _ baseRecord; 
entry.lastIncrement _ lastIncrementRecord
};
baseRecord = nullRecordID AND lastIncrementRecord = nullRecordID => {
entry.prevBase _ entry.base _ entry.lastIncrement _ nullRecordID
};
ENDCASE;
entry.universalFile _ universalFile;
entry.size _ SIZE[BTreeEntryObject];
IF name = NIL THEN name _ "";
flatName _ Rope.Flatten[name];
entry.name _ AppendText[LOOPHOLE[entry, BTreeEntryPtr], flatName];
END;

TRUSTED {
BTree.UpdateEntry[btree.tree, key, btree.pathStk, TRUE, size, Write
! BTree.Error => BB.Error[damagedBTree]]};
FreeKey[key];
};

GetFileInfo: PUBLIC ENTRY PROC [universalFile: UniversalFile, relation: BTree.Relation _ equal] RETURNS [found: BOOLEAN _ FALSE, baseRecord, lastIncrementRecord, prevBaseRecord: RecordID _ nullRecordID, name: Rope.ROPE] ~ TRUSTED {
key: Key _ NewKey[universalFile];
Read: UNSAFE PROC [e: BTree.Entry] = UNCHECKED BEGIN
entry: BTreeEntryPtr = LOOPHOLE[e, BTreeEntryPtr];
IF entry # NIL THEN {
found _ TRUE;
baseRecord _ entry.base;
lastIncrementRecord _ entry.lastIncrement;
prevBaseRecord _ entry.prevBase;
name _ GetText[entry, entry.name];
};
END;
TRUSTED {BTree.ReadEntry[btree.tree, key, relation, btree.pathStk, TRUE, Read
! BTree.Error => BB.Error[damagedBTree]]};
FreeKey[key];
};

PositionInfo: TYPE = RECORD [
logRecord: AlpineLog.RecordID,
backupRecord: BackupLog.RecordID,
lastFullyConsistentTime: BasicTime.GMT,
lastFullyConsistentBackupRecord: BackupLog.RecordID
];

PositionPageInfo: TYPE = RECORD [
interval: VM.Interval,
ptr: LONG POINTER TO PositionInfo,
buffer: AlpineFile.PageBuffer,
pageRun: AlpineFile.PageRun
];

positionPageInfo: PositionPageInfo;

SetPositionInfo: PUBLIC ENTRY PROC [logRecord: AlpineLog.RecordID, backupRecord: BackupLog.RecordID] ~ TRUSTED {
positionPageInfo.ptr.logRecord _ logRecord;
positionPageInfo.ptr.backupRecord _ backupRecord;
};
GetPositionInfo: PUBLIC ENTRY PROC [] RETURNS [logRecord: AlpineLog.RecordID, backupRecord: BackupLog.RecordID] ~ TRUSTED {
logRecord _ positionPageInfo.ptr.logRecord;
backupRecord _ positionPageInfo.ptr.backupRecord;
};

SetFullyConsistent: PUBLIC ENTRY PROC [backupRecord: RecordID, time: BasicTime.GMT] ~ TRUSTED {
positionPageInfo.ptr.lastFullyConsistentTime _ time;
positionPageInfo.ptr.lastFullyConsistentBackupRecord _ backupRecord;
};

Commit: PUBLIC PROC [] ~ TRUSTED {
outcome: AlpineTransaction.Outcome;
AlpFile.WritePages[ handle: globals.openFile, pageRun: positionPageInfo.pageRun, pageBuffer: positionPageInfo.buffer, lock: [write, fail] ! AlpFile.LockFailed => {GOTO LockFailure} ];
BTreeAlpineVM.EndLongUpdate[btree.storage];
outcome _ AlpTransaction.Finish[handle: globals.trans, requestedOutcome: commit, continue: TRUE];
IF outcome # commit THEN GOTO TransactionFailure;
BTreeAlpineVM.StartLongUpdate[btree.storage];
EXITS
LockFailure => RETURN WITH ERROR BB.Error[lockFailure];
TransactionFailure => RETURN WITH ERROR BB.Error[transactionFailure];
};
DeleteFileInfo: PUBLIC ENTRY PROC [universalFile: UniversalFile] RETURNS [found: BOOLEAN] ~ TRUSTED {
key: Key _ NewKey[universalFile];
found  _ BTree.DeleteKey[btree.tree, key, btree.pathStk, TRUE
! BTree.Error => BB.Error[damagedBTree]];
FreeKey[key];
};

EntrySize: BTree.EntrySize  -- [entry: BTree.Entry] RETURNS [words: BTree.EntSize] -- = TRUSTED {
e: BTreeEntryPtr _ LOOPHOLE[entry, BTreeEntryPtr]; 
RETURN[e.size];
};

Compare: BTree.Compare -- [key: BTree.Key, entry: BTree.Entry] RETURNS [PrincOps.Comparison] -- = TRUSTED {
k: Key = NARROW[key];
e: BTreeEntryPtr = LOOPHOLE[entry, BTreeEntryPtr];
KeyIndex: TYPE = [0..9);
KeyArray: TYPE = ARRAY KeyIndex OF CARDINAL;
FOR i: CARDINAL DECREASING IN KeyIndex DO
SELECT TRUE FROM 
LOOPHOLE[k.universalFile, KeyArray][i] < LOOPHOLE[e.universalFile, KeyArray][i] => RETURN[less];
LOOPHOLE[k.universalFile, KeyArray][i] > LOOPHOLE[e.universalFile, KeyArray][i] => RETURN[greater];
ENDCASE => NULL;
ENDLOOP;
RETURN[equal];
};

TextRP: TYPE = BTreeEntryPtr RELATIVE POINTER TO TextRep;
TextRep: TYPE = Rope.TextRep;

GetText: PROC [eP: BTreeEntryPtr, textRP: TextRP]  RETURNS[text: Rope.Text] = TRUSTED {
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]
];
};

AppendText: PROC [eP: BTreeEntryPtr, text: Rope.Text]  RETURNS [textRP: TextRP] = TRUSTED {
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;
};

stockKey: Key _ NIL;

NewKey: INTERNAL PROC [universalFile: UniversalFile] RETURNS[key: Key] = {
ENABLE {
UNWIND => AlpineEmergency.UnwindingMonitor[];
UNCAUGHT => {AlpineEmergency.UncaughtThruMonitor[]; REJECT};
};
IF stockKey = NIL THEN stockKey _ NEW[KeyObject];
key _ stockKey; 
stockKey _ NIL;
key^ _ [universalFile];
};

FreeKey: PROC [key: Key] = INLINE {
IF key # NIL THEN stockKey _ key;
};

ShowTree: PROC [] = {
[] _ ViewRec.ViewRef[agg: btree.tree];
};

positionPageInfo.interval _ VM.Allocate[count: 1];
positionPageInfo.ptr _ LOOPHOLE[VM.AddressForPageNumber[positionPageInfo.interval.page]];
TRUSTED { positionPageInfo.buffer _ DESCRIPTOR[VM.AddressForPageNumber[positionPageInfo.interval.page], 1*PrincOps.wordsPerPage] };
positionPageInfo.pageRun _ [0, 1]
END.
ΆBackupBTreeImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Carl Hauser, April 22, 1986 2:49:28 pm PST


There is just one btree maintained by this package -- it is here in the global frame.
OpenForRecovery: PUBLIC ENTRY PROC [] ~ {

Body
};

BTree Management

here follows the necessary TextRep
The following procedures store additional non-btree information in BTree page 0 of the file containing the BTree.



This loopholing trick only works because the components of a UniversalFileID are complete (not partial) word values.  Be careful.
Do the loop in decreasing order because, presumably, fileIDs are much less alike than VolumeIDs.
Body of BackupBTreeImpl
ΚS˜™Icodešœ
Οm
œ1™<K™*K™—š
Οk	˜	Jš
œ˜Jšœžœ)˜>Jš
œ˜J˜Jšœ
žœ˜)J˜Jš
œ˜Jšœžœ˜"Jšœ
žœ˜)Jšœ
žœžœ˜Jš
œ˜JšœžœT˜gJšœ	žœ˜Jšœžœ˜Jšœžœžœ˜2Jšœ
žœžœ˜J˜Jšžœ
˜—J™šœžœ
ž˜š
ž˜Jšœxž˜{—šžœ
˜J˜—š
ž˜J˜——Jšœž˜˜Jšžœ
žœžœ˜:—J˜Jš	œžœ
žœžœžœ
˜+J˜J™Ušœžœ˜J˜Jš
œ˜J˜Jšœžœžœ˜#J˜
—šœ	žœ˜Jš
œ˜Jšœžœ˜ Jš
œ˜J˜—J˜J˜;Jšœžœ#˜6Jšœ
žœ˜$J˜šΟnœžœ
žœ
žœ+žœžœžœžœ˜‹
Kšœžœ
žœ˜"Kš
œ"˜"K˜Kš
œG˜Gšžœžœ
žœ˜š
œ˜Jš
œ2˜2Jš
œE˜E——šžœžœ
˜J•StartOfExpansionœ
[file: 
AlpFile.Handle, filePagesPerPage: 
BTreeAlpineVM.FilePagesPerPage, cacheSize: 
BTreeAlpineVM.CacheSize, base: 
AlpineEnvironment.PageNumber _ 0]šžœn˜rJ–b[handle: 
BTreeAlpineVM.Handle, file: 
AlpFile.Handle, base: 
AlpineEnvironment.PageNumber _ 0]šžœOΟc˜f—š
œ˜J˜*J˜)Jšœžœ
˜!Jšœ(žœ ˜W—Kšœ‘
žœ˜±
˜Kš
œ8˜8Kš
œ;˜;Kš
œA˜AKš
œN˜NK˜—K˜-šžœ
˜Kš	œžœ
žœ
žœ
žœ˜3Jš	œžœ
žœ
žœ
žœ˜9—K˜—K˜šŸœžœ
žœ
žœ™)K™K™—K™K™K™Kšœžœžœ˜(Kšœžœžœ
žœ
žœ
žœ˜<š	œžœžœ
ž	œ
žœ˜3Kšœ	ž	œ
 <˜OKš
œ2˜2Kš
œM˜MKšœ ˜&Kš
œ"™"K˜—K˜Kšœžœžœ˜šœžœžœ˜Kš
œ˜K˜—K˜Kšœ
žœ˜K˜šŸœžœ
žœ
žœežœžœ˜”
Jš
œ!˜!J˜Jšœžœžœžœ˜Gš	Ÿœžœ
žœž	œ
ž˜4Jšœžœ˜#šžœ
žœ
ž˜šœžœ(˜EKš
œ*˜*K˜—šœžœ)˜FK˜Kš
œ˜K˜—šœžœ(˜EK˜Kš
œ˜Kš
œ)˜)Kš
œ˜—šœžœ(˜EKš
œ@˜@Kš
œ˜—Kšžœ
˜—Kš
œ$˜$Kšœ
žœ˜$Kšžœžœ
žœ˜K˜Kšœžœ"˜BJšžœ
˜J˜—šžœ˜	šœ2žœ
˜CJšœžœ˜*——J˜
K˜—K˜šŸœžœ
žœ
žœBžœ	žœžœWžœžœ˜η
Jš
œ!˜!š	Ÿœžœ
žœž	œ
ž˜4Jšœžœ˜2šžœ	žœ
žœ˜Kšœžœ
˜
Kš
œ˜Kš
œ*˜*Kš
œ ˜ K˜"K˜—Kšžœ
˜—šžœ<žœ˜MJšœžœ˜*—J˜
K˜K˜—K™qK™šœžœžœ˜Kš
œ˜Kš
œ!˜!Kšœ#žœ
˜'Kš
œ3˜3K˜K˜—šœžœžœ˜!Kšœ
žœ
˜Kšœžœ
žœ
žœ˜"Kš
œ˜Kš
œ˜K˜—K˜K˜#K˜š
Ÿœžœ
žœ
žœEžœ˜pKš
œ+˜+Kš
œ1˜1K˜—K™šŸœžœ
žœ
žœžœEžœ˜{Kš
œ+˜+Kš
œ1˜1K˜—K˜šŸœžœ
žœ
žœ*žœžœ˜_Kš
œ4˜4Kš
œD˜DK˜K˜—šŸœžœ
žœžœ˜"Kš
œ#˜#Kšœ£
žœ˜·
K˜+K–v[handle: 
AlpTransaction.Handle, requestedOutcome: 
AlpineTransaction.RequestedOutcome, continue: 
BOOLEAN _ FALSE]šœ[žœ˜aKšžœžœ
žœ˜1K˜-š
ž˜Kš	œžœ
žœ
žœ
žœ˜7Kš	œžœ
žœ
žœ
žœ˜E—K˜—K™šŸœžœ
žœ
žœ žœ	žœžœ˜eJš
œ!˜!šœ9ž˜=Jšœžœ˜)—Jš
œ
˜
Jš
œ˜—J˜šΟb	œ 9œžœ˜aJšœžœ˜3Jšžœ	˜Jš
œ˜—J˜š‘œ Hœžœ˜kJ™
Jšœ	žœ˜Jšœžœ˜2Jšœ
žœ
˜Jš	œ
žœžœ
žœ
žœ
˜,š	žœžœ
ž
œ
žœ
ž˜)J™`šžœ
žœ
žœ
˜Jšžœ!žœ"žœ˜`Jšžœ!žœ"žœ
˜cJšžœžœ
˜—Jšžœ
˜—Jšžœ˜Jš
œ˜—J˜Kš	œžœžœ
žœ
žœ	˜9Kšœ	žœ˜K˜šŸœžœ&žœžœ˜WJšœ	žœ
žœ
žœ˜/Jšœžœžœ˜/Jšœžœ˜$š
œ˜Jš
œ˜Jš
œ
˜
Jšœžœ˜Jš
œ˜—Jš
œ˜—J˜šŸ
œžœ'žœžœ˜[Jšœ	žœ
žœ
žœ	˜!Jšœžœžœ˜,Jšœ	žœ
˜J˜š
œ˜Jšœžœ˜Jš
œ
˜
Jš
œ˜Jš
œ˜—Jš
œ˜Jš
œ˜—J˜Kšœžœ
˜K˜šŸœžœ
žœ žœ˜Jšžœ˜Jšžœ'˜-Jšžœ,žœ˜<J˜—Jšžœžœ
žœžœ˜1Jš
œ˜Jšœžœ
˜Jš
œ˜Jš
œ˜—J˜šŸœžœžœ˜#Jšžœžœ
žœ˜!Jš
œ˜J˜—˜J˜&J˜J˜—™Jšœžœ˜2Jšœžœ
žœ7˜YJšžœž
œ
žœR˜ƒ
Jš
œ!˜!—Jšžœ
˜—…—%4