
<<BackupBTreeImpl.mesa>>
    <<Copyright © 1985 by Xerox Corporation.  All rights reserved.>>
    <<Carl Hauser, April 22, 1986 2:49:28 pm PST>>
    <<>>
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;

<<There is just one btree maintained by this package -- it is here in the global frame.>>
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];
        };

    <<OpenForRecovery: PUBLIC ENTRY PROC [] ~ {>>
        <<Body>>
        <<};>>
    <<>>
    <<BTree Management>>
    <<>>
    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,
        <<here follows the necessary TextRep>>
        ];

    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];
        };

    <<The following procedures store additional non-btree information in BTree page 0 of the file containing the BTree.>>
    <<>>
    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 {
<<This loopholing trick only works because the components of a UniversalFileID are complete (not partial) word values.  Be careful.>>
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
<<Do the loop in decreasing order because, presumably, fileIDs are much less alike than VolumeIDs.>>
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];
};

<<Body of BackupBTreeImpl>>
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.