-- BTreeTestImpl.mesa
<<-- Last Edited by: Taft, March 26, 1983 10:42 am>>
DIRECTORY
    BTree,
    BTreeTestOps,
    BTreeVM,
    Environment,
    File,
    FileTypes,
    Inline,
    RandomCard,
    Real,
    System,
    Volume;
BTreeTestImpl: PROGRAM
    IMPORTS BTree, BTreeVM, File, Inline, RandomCard, Real, System, Volume
    EXPORTS BTreeTestOps
    = BEGIN OPEN BTreeTestOps;
myRepPrim: BTree.RepresentationPrimitives = [
    compare: Compare,
    compareEntries: CompareEntries,
    entrySize: EntrySize,
    entryFromRecord: EntryFromRecord,
    newRecordFromEntry: NewRecordFromEntry];
Key: TYPE = REF CARDINAL;
Record: TYPE = REF EntryObject;
Entry: TYPE = LONG POINTER TO EntryObject;
EntryObject: TYPE = RECORD [
    copies: EntSize, -- number of copies of the key
    keys: SEQUENCE COMPUTED EntSize OF KeyIndex];
EntSize: TYPE = [0..LAST[BTree.PageSize]-BTree.reservedWordsPerPage];
EntryTable: TYPE = RECORD [
    count: KeyIndex,
    exists: PACKED SEQUENCE maxEntries: KeyIndex OF BOOLEAN];
Compare: PROCEDURE [key: BTree.Key, entry: Entry] RETURNS [Environment.Comparison] =
    BEGIN
    e: CARDINAL = entry.keys[0];
    RETURN [SELECT NARROW[key, Key]^ FROM
        <e => less,
        =e => equal,
        ENDCASE => greater];
    END;
CompareEntries: PROCEDURE [entry1, entry2: Entry] RETURNS [Environment.Comparison] =
    BEGIN
    e1: CARDINAL = entry1.keys[0];
    e2: CARDINAL = entry2.keys[0];
    RETURN [SELECT e1 FROM
        <e2 => less,
        =e2 => equal,
        ENDCASE => greater];
    END;
EntrySize: PROCEDURE [entry: Entry] RETURNS [words: [1..LAST[BTree.PageSize]]] =
    { RETURN [SIZE[EntryObject[entry.copies]]] };
EntryFromRecord: PROCEDURE [record: BTree.Record] RETURNS [entry: Entry] =
    { RETURN [LOOPHOLE[record]] };
NewRecordFromEntry: PROCEDURE [entry: Entry] RETURNS [record: Record] =
    BEGIN
    record _ NEW[EntryObject[entry.copies]];
    Inline.LongCOPY[to: LOOPHOLE[record], from: entry, nwords: SIZE[EntryObject[entry.copies]]];
    END;
myTree: BTree.Tree;
myStorage: BTreeVM.Handle;
key: Key = NEW[CARDINAL];
record: Record;
entry: Entry;
maxEntSize: EntSize _ FIRST[BTree.PageSize]/8; -- 1/8 minimum-size page
entryTable: REF EntryTable;
-- Main procedures callable from interpreter
useFixedSeed: BOOLEAN _ TRUE;
validateEveryUpdate: BOOLEAN _ FALSE;
millisecondsPerPulse: REAL = 1000.0 / Real.Float[System.MicrosecondsToPulses[1000000]];
Time: PROCEDURE [iterations: LONG CARDINAL] RETURNS [msPerOp: ARRAY Operation OF REAL] =
    BEGIN
    counts: ARRAY Operation OF LONG CARDINAL _ ALL [0];
    times: ARRAY Operation OF System.Pulses _ ALL [[0]];
    entriesEnumerated: LONG CARDINAL _ 0;
    seedUsed: INTEGER _ RandomCard.Init[IF useFixedSeed THEN 0 ELSE -1];
    IF myTree=NIL THEN [] _ Create[];
    WHILE iterations#0 DO
        operation: Operation;
        k: KeyIndex;
        then: System.Pulses _ System.GetClockPulses[];
        [operation: operation, key: k] _ PerformRandomOperation[];
        times[operation] _ [times[operation] + (System.GetClockPulses[] - then)];
        counts[operation] _ counts[operation]+(IF operation=validate THEN myTree.GetState[].entryCount ELSE 1);
        IF validateEveryUpdate AND operation IN UpdateOperation THEN myTree.Validate[];
        iterations _ iterations-1;
        ENDLOOP;
    FOR operation: Operation IN Operation DO
        msPerOp[operation] _ (Real.Float[times[operation]]/Real.Float[MAX[counts[operation], 1]]) * millisecondsPerPulse;
        ENDLOOP;
    END;
VMStats: PROCEDURE RETURNS [refs: LONG CARDINAL, hitPercent: REAL, reads, writes: LONG CARDINAL, msPerReadWrite, avgChainLength: 
REAL] =
    BEGIN
    hits, misses, cumChainLength: LONG CARDINAL;
    cumReadWriteTime: System.Pulses;
    [hits: hits, misses: misses, reads: reads, writes: writes, cumChainLength: cumChainLength, cumReadWriteTime: cumReadWriteTime] _ 
    BTreeVM.GetStats[myStorage];
    refs _ hits+misses;
    hitPercent _ Real.Float[hits]*100.0 / Real.Float[MAX[refs, 1]];
    msPerReadWrite _ (Real.Float[cumReadWriteTime] / Real.Float[MAX[reads+writes, 1]]) * millisecondsPerPulse;
    avgChainLength _ Real.Float[cumChainLength] / Real.Float[MAX[refs, 1]];
    END;
MissingEntry: SIGNAL [k: KeyIndex] = CODE;
FindMissingEntries: PROCEDURE =
    BEGIN
    FOR k: KeyIndex IN [0..entryTable.maxEntries) DO
        IF entryTable.exists[k] AND ~Lookup[k] THEN SIGNAL MissingEntry[k];
        ENDLOOP;
    END;
-- Type "conversion" operations, callable from debugger
ConcreteKey: PROCEDURE [key: BTree.Key] RETURNS [Key] =
    { RETURN [NARROW[key]] };
ConcreteEntry: PROCEDURE [entry: BTree.Entry] RETURNS [Entry] =
    { RETURN [entry] };
-- Subsidiary procedures (some exported to BTreeTestOps so the BTreeTool can call them)
file: File.Capability _ File.nullCapability;
Create: PUBLIC SAFE PROCEDURE [cacheSize: BTreeVM.CacheSize _ 20, initialize: BOOLEAN _ TRUE, initialFileSize: File.PageCount _ 20, 
filePagesPerPage: BTreeVM.FilePagesPerPage _ 1, maxEntries: KeyIndex _ 10000] RETURNS [tree: BTree.Tree, storage: BTreeVM.Handle] = 
TRUSTED
    BEGIN
    IF initialize AND file#File.nullCapability AND File.GetSize[file]<initialFileSize THEN
        { File.Delete[file]; file _ File.nullCapability };
    IF file=File.nullCapability THEN
        BEGIN
        file _ File.Create[volume: Volume.systemID, initialSize: initialFileSize, type: FileTypes.tUntypedFile];
        initialize _ TRUE;
        END;
    storage _ BTreeVM.Open[file: file, filePagesPerPage: filePagesPerPage, cacheSize: cacheSize];
    tree _ BTree.Open[repPrim: myRepPrim, storage: storage, storPrim: [BTreeVM.ReferencePage, BTreeVM.ReleasePage], pageSize: 
    filePagesPerPage*Environment.wordsPerPage, minEntrySize: 2, initialize: initialize];
    IF initialize THEN
        BEGIN
        record _ NEW[EntryObject[maxEntSize]];
        entry _ LOOPHOLE[record];
        entryTable _ NEW [EntryTable[maxEntries]];
        entryTable.count _ 0;
        FOR i: KeyIndex IN [0..entryTable.maxEntries) DO
            entryTable.exists[i] _ FALSE;
            ENDLOOP;
        END;
    myTree _ tree;
    myStorage _ storage;
    END;
Destroy: PUBLIC SAFE PROCEDURE = TRUSTED
    BEGIN
    IF file#File.nullCapability THEN { File.Delete[file]; file _ File.nullCapability };
    END;
keyOfInterest: CARDINAL _ LAST[CARDINAL];
EncounteredKeyOfInterest: SIGNAL = CODE;
PerformRandomOperation: PUBLIC SAFE PROCEDURE RETURNS [operation: Operation, key: KeyIndex] = TRUSTED
    BEGIN
    SELECT RandomCard.Choose[0, 250+entryTable.count/2] FROM
        0 =>
            BEGIN -- occasionally validate the tree.  The frequency of this decreases in proportion to the size of the tree, since each 
            enumeration takes longer as the tree gets larger.
            myTree.Validate[];
            operation _ validate;
            END;
        ENDCASE =>
            BEGIN -- otherwise, choose a random key and perform some operation
            key _ RandomCard.Choose[0, entryTable.maxEntries-1];
            IF key=keyOfInterest THEN SIGNAL EncounteredKeyOfInterest;
            IF entryTable.exists[key] THEN
                BEGIN -- key exists.  25% of the time verify that looking it up succeeds, 25% of the time delete it, and 50% of the time replace it 
                with a new entry of a different size.
                SELECT RandomCard.Choose[0, 3] FROM
                    0 =>
                        BEGIN
                        operation _ lookup;
                        IF ~Lookup[key] THEN ERROR; -- failed to find existing key
                        END;
                    1 =>
                        BEGIN
                        operation _ delete;
                        IF ~Delete[key] THEN ERROR; -- failed to find existing key
                        END;
                    ENDCASE =>
                        BEGIN
                        operation _ replace;
                        Insert[key];
                        END;
                END
            ELSE BEGIN -- key does not exist.  10% of the time verify that looking it up fails, and 90% of the time insert an entry with this 
            key.
                SELECT RandomCard.Choose[0, 9] FROM
                    0 =>
                        BEGIN
                        operation _ lookup;
                        IF Lookup[key] THEN ERROR; -- found key that it shouldn't have
                        END;
                    ENDCASE =>
                        BEGIN
                        operation _ insert;
                        Insert[key];
                        END;
                END;
            END;
    END;
GetEntryCount: PUBLIC SAFE PROCEDURE RETURNS [count: LONG CARDINAL] = CHECKED
    { RETURN [entryTable.count] };
Lookup: PROCEDURE [keyVal: KeyIndex] RETURNS [found: BOOLEAN] =
    BEGIN
    EntryProc: PROCEDURE [entry: Entry] =
        BEGIN
        found _ entry#NIL;
        IF found THEN
            FOR i: CARDINAL IN [0..entry.copies) DO
                IF entry.keys[i]#keyVal THEN ERROR; -- entry has wrong contents
                ENDLOOP;
        END;
    key^ _ keyVal;
    myTree.ReadEntry[key: key, Proc: EntryProc];
    END;
Insert: PROCEDURE [keyVal: KeyIndex] =
    BEGIN
    entSize: EntSize _ RandomCard.Choose[1, maxEntSize];
    entry.copies _ entSize;
    FOR i: CARDINAL IN [0..entSize) DO
        entry.keys[i] _ keyVal;
        ENDLOOP;
    key^ _ keyVal;
    myTree.UpdateEntry[key: key, entry: entry];
    IF ~entryTable.exists[keyVal] THEN
        { entryTable.exists[keyVal] _ TRUE; entryTable.count _ entryTable.count+1 };
    END;
Delete: PROCEDURE [keyVal: KeyIndex] RETURNS [found: BOOLEAN] =
    BEGIN
    key^ _ keyVal;
    found _ myTree.DeleteKey[key: key];
    IF found THEN
        { entryTable.count _ entryTable.count-1; entryTable.exists[keyVal] _ FALSE };
    END;
END.