<> <> <> <> DIRECTORY Basics, BasicTime, BTree, BTreeTestOps, BTreeVM, FS, FSBackdoor, PrincOps, PrincOpsUtils, Random, Real, Rope; BTreeTestImpl: PROGRAM IMPORTS Basics, BasicTime, BTree, BTreeVM, FS, FSBackdoor, Random, PrincOpsUtils, Real EXPORTS BTreeTestOps = { OPEN BTreeTestOps; ROPE: TYPE = Rope.ROPE; <> 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 BOOL]; Compare: PROC [key: BTree.Key, entry: Entry] RETURNS [BTree.Comparison] = { e: CARDINAL = entry.keys[0]; RETURN [SELECT NARROW[key, Key]^ FROM less, =e => equal, ENDCASE => greater]; }; CompareEntries: PROC [entry1, entry2: Entry] RETURNS [BTree.Comparison] = { e1: CARDINAL = entry1.keys[0]; e2: CARDINAL = entry2.keys[0]; RETURN [SELECT e1 FROM less, =e2 => equal, ENDCASE => greater]; }; EntrySize: PROC [entry: Entry] RETURNS [words: BTree.EntSize] = { RETURN [SIZE[EntryObject[entry.copies]]] }; EntryFromRecord: PROC [record: BTree.Record] RETURNS [entry: Entry] = { RETURN [LOOPHOLE[record]] }; NewRecordFromEntry: PROC [entry: Entry] RETURNS [record: Record] = { record _ NEW[EntryObject[entry.copies]]; PrincOpsUtils.LongCopy[to: LOOPHOLE[record], from: entry, nwords: SIZE[EntryObject[entry.copies]]]; }; myTree: BTree.Tree; myStorage: BTreeVM.Handle; key: Key = NEW[CARDINAL]; record: Record; entry: Entry; maxEntSize: EntSize _ FS.WordsForPages[1]/8; -- 1/8 minimum-size page entryTable: REF EntryTable; <
> useFixedSeed: BOOL _ TRUE; markov: Random.RandomStream; validateEveryUpdate: BOOL _ FALSE; millisecondsPerPulse: REAL = 1000.0 / Real.Float[BasicTime.MicrosecondsToPulses[1000000]]; Time: PROC [iterations: LONG CARDINAL] RETURNS [msPerOp: ARRAY Operation OF REAL] = { counts: ARRAY Operation OF LONG CARDINAL _ ALL [0]; times: ARRAY Operation OF LONG CARDINAL _ ALL [0]; entriesEnumerated: LONG CARDINAL _ 0; markov _ Random.Create[0, IF useFixedSeed THEN 0 ELSE -1]; IF myTree=NIL THEN [] _ Create[]; WHILE iterations#0 DO operation: Operation; k: KeyIndex; then: BasicTime.Pulses _ BasicTime.GetClockPulses[]; [operation: operation, key: k] _ PerformRandomOperation[]; times[operation] _ times[operation] + (BasicTime.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; }; VMStats: PROC RETURNS [refs: LONG CARDINAL, hitPercent: REAL, reads, writes: LONG CARDINAL, msPerReadWrite, avgChainLength: REAL] = { hits, misses, cumChainLength, cumReadWriteTime: LONG CARDINAL; [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]]; }; MissingEntry: SIGNAL [k: KeyIndex] = CODE; EnumerateFailedToTerminate: SIGNAL = CODE; FindMissingEntries: PROC = { FOR k: KeyIndex IN [0..entryTable.maxEntries) DO IF entryTable.exists[k] AND ~Lookup[k] THEN SIGNAL MissingEntry[k]; ENDLOOP; }; EnumerateBackward: PROC [usePathStk: BOOL _ FALSE] = { EntryProc: PROC [entry: Entry] = { found _ entry#NIL; IF found THEN foundKey _ entry.keys[0]; }; found: BOOL; foundKey: KeyIndex _ entryTable.maxEntries; pathStk: BTree.PathStk _ IF usePathStk THEN BTree.NewPathStk[] ELSE NIL; FOR k: KeyIndex DECREASING IN [0..entryTable.maxEntries) DO IF entryTable.exists[k] THEN { key^ _ foundKey; myTree.ReadEntry[key: key, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk]; IF ~found OR foundKey#k THEN SIGNAL MissingEntry[k]; }; ENDLOOP; key^ _ foundKey; myTree.ReadEntry[key: key, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk]; IF found THEN SIGNAL EnumerateFailedToTerminate; }; <> ConcreteKey: PROC [key: BTree.Key] RETURNS [Key] = { RETURN [NARROW[key]] }; ConcreteEntry: PROC [entry: BTree.Entry] RETURNS [Entry] = { RETURN [entry] }; <> file: FS.OpenFile _ FS.nullOpenFile; Create: PUBLIC SAFE PROC [cacheSize: BTreeVM.CacheSize _ 20, initialize: BOOL _ TRUE, initialFileSize: INT _ 20, filePagesPerPage: BTreeVM.FilePagesPerPage _ 1, maxEntries: KeyIndex _ 10000] RETURNS [tree: BTree.Tree, storage: BTreeVM.Handle] = TRUSTED { IF initialize AND file#FS.nullOpenFile AND file.GetInfo[].pages CONTINUE]; file _ FS.nullOpenFile; }; myTree _ NIL; myStorage _ NIL; }; keyOfInterest: CARDINAL _ LAST[CARDINAL]; EncounteredKeyOfInterest: SIGNAL = CODE; PerformRandomOperation: PUBLIC SAFE PROC RETURNS [operation: Operation, key: KeyIndex] = TRUSTED { SELECT Random.ChooseInt[markov, 0, 250+entryTable.count/2] FROM 0 => { <> myTree.Validate[]; operation _ validate; }; ENDCASE => { <> key _ Random.ChooseInt[markov, 0, entryTable.maxEntries-1]; IF key=keyOfInterest THEN SIGNAL EncounteredKeyOfInterest; IF entryTable.exists[key] THEN { <> SELECT Random.ChooseInt[markov, 0, 3] FROM 0 => { operation _ lookup; IF ~Lookup[key] THEN ERROR; -- failed to find existing key }; 1 => { operation _ delete; IF ~Delete[key] THEN ERROR; -- failed to find existing key }; ENDCASE => { operation _ replace; Insert[key]; }; } ELSE { <> SELECT Random.ChooseInt[markov, 0, 9] FROM 0 => { operation _ lookup; IF Lookup[key] THEN ERROR; -- found key that it shouldn't have }; ENDCASE => { operation _ insert; Insert[key]; }; }; }; }; GetEntryCount: PUBLIC SAFE PROC RETURNS [count: LONG CARDINAL] = CHECKED { RETURN [entryTable.count]; }; Lookup: PROC [keyVal: KeyIndex] RETURNS [found: BOOL] = { EntryProc: PROC [entry: Entry] = { 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; }; key^ _ keyVal; myTree.ReadEntry[key: key, Proc: EntryProc]; }; Insert: PROC [keyVal: KeyIndex] = { ProduceEntry: PROC [bEntry: BTree.Entry] = { PrincOpsUtils.LongCopy[to: bEntry, from: entry, nwords: words]; }; copies: CARDINAL = Random.ChooseInt[markov, 1, maxEntSize]; words: EntSize = SIZE[EntryObject[copies]]; entry.copies _ copies; FOR i: CARDINAL IN [0..copies) DO entry.keys[i] _ keyVal; ENDLOOP; key^ _ keyVal; myTree.UpdateEntry[key: key, words: words, Proc: ProduceEntry]; IF ~entryTable.exists[keyVal] THEN { entryTable.exists[keyVal] _ TRUE; entryTable.count _ entryTable.count+1; }; }; Delete: PROC [keyVal: KeyIndex] RETURNS [found: BOOL] = { key^ _ keyVal; found _ myTree.DeleteKey[key: key]; IF found THEN { entryTable.count _ entryTable.count-1; entryTable.exists[keyVal] _ FALSE; }; }; <> MultThenDiv: PROC [m1: LONG CARDINAL, m2: CARDINAL, dv: CARDINAL] RETURNS [result: LONG CARDINAL] = { OPEN Basics, mm1: LOOPHOLE[m1, Basics.LongNumber.num]; t: MACHINE DEPENDENT RECORD [ SELECT OVERLAID * FROM separate => [low, mid, high: CARDINAL], lower => [lowlong: LONG CARDINAL, junk: CARDINAL], higher => [junk: CARDINAL, highlong: LONG CARDINAL], ENDCASE]; t.lowlong _ LongMult[mm1.lowbits, m2]; IF mm1.highbits # 0 THEN { t.highlong _ LongMult[mm1.highbits, m2] + t.mid; IF t.high # 0 THEN { OPEN q: LOOPHOLE[result, Basics.LongNumber.num]; <> IF t.high >= dv THEN t.high _ t.high MOD dv; -- overflow; lowbits will be right [quotient: q.highbits, remainder: t.mid] _ LongDivMod[t.highlong, dv]; q.lowbits _ LongDiv[t.lowlong, dv]; RETURN; }; }; <> RETURN[t.lowlong/LONG[dv]]; }; }.