> useFixedSeed: BOOL _ TRUE; markov: Random.RandomStream _ NIL; validateEveryUpdate: BOOL _ FALSE; millisecondsPerPulse: REAL = 1000.0 / Real.Float[BasicTime.MicrosecondsToPulses[1000000]]; Operation: TYPE = {lookup, validate, insert, delete, replace}; UpdateOperation: TYPE = Operation[insert..replace]; KeyIndex: TYPE = CARDINAL; 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 BTreeSimple.GetState[myTree].entryCount ELSE 1); IF validateEveryUpdate AND operation IN UpdateOperation THEN BTreeSimple.Validate[myTree]; 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] _ BTreeSimple.GetStatistics[myTree]; 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] = TRUSTED { EntryProc: UNSAFE PROC [key: BTreeSimple.EntryKey, value: BTreeSimple.EntryValue] = UNCHECKED { foundKey _ BTreeSimple.KeyFromEntry[key]; foundKeyIndex _ IF value#NIL THEN value[0] ELSE 0; }; foundKeyIndex: KeyIndex _ entryTable.maxEntries; foundKey: BTreeSimple.Key _ KeyFromIndex[entryTable.maxEntries]; pathStk: BTreeSimple.PathStk _ IF usePathStk THEN BTreeSimple.NewPathStk[] ELSE NIL; FOR k: KeyIndex DECREASING IN [0..entryTable.maxEntries) DO IF entryTable.exists[k] THEN { BTreeSimple.ReadEntry[tree: myTree, key: foundKey, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk]; IF foundKey=NIL OR foundKeyIndex#k THEN SIGNAL MissingEntry[k]; }; ENDLOOP; BTreeSimple.ReadEntry[tree: myTree, key: foundKey, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk]; IF foundKey#NIL THEN SIGNAL EnumerateFailedToTerminate; }; <> file: FS.OpenFile _ FS.nullOpenFile; myTree: BTreeSimple.Tree; maxEntSize: CARDINAL _ FS.WordsForPages[1]/8; -- 1/8 minimum-size page EntryTable: TYPE = RECORD [ count: KeyIndex, exists: PACKED SEQUENCE maxEntries: KeyIndex OF BOOL]; entryTable: REF EntryTable; Create: PROC [cacheSize: BTreeSimple.CacheSize _ 20, initialize: BOOL _ TRUE, initialFileSize: INT _ 20, filePagesPerPage: BTreeSimple.FilePagesPerPage _ 1, maxEntries: KeyIndex _ 10000] RETURNS [tree: BTreeSimple.Tree] = { IF initialize AND file#FS.nullOpenFile AND file.GetInfo[].pages CONTINUE]; file _ FS.nullOpenFile; }; myTree _ 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 => { <> BTreeSimple.Validate[myTree]; 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 { -- 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 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] = { key: BTreeSimple.Key = KeyFromIndex[keyVal]; actualKey: BTreeSimple.InternalKey; value: BTreeSimple.Value; [actualKey, value] _ BTreeSimple.ReadRecord[tree: myTree, key: key]; IF (found _ actualKey#NIL) THEN FOR i: CARDINAL IN [0..value.length) DO IF value[i]#keyVal THEN ERROR; -- entry has wrong contents ENDLOOP; }; Insert: PROC [keyVal: KeyIndex] = { key: BTreeSimple.Key = KeyFromIndex[keyVal]; valueLength: CARDINAL = Random.ChooseInt[markov, 1, maxEntSize]; value: BTreeSimple.Value = NEW[BTreeSimple.ValueObject[valueLength]]; FOR i: CARDINAL IN [0..valueLength) DO value[i] _ keyVal; ENDLOOP; BTreeSimple.UpdateRecord[tree: myTree, key: key, value: value]; IF ~entryTable.exists[keyVal] THEN { entryTable.exists[keyVal] _ TRUE; entryTable.count _ entryTable.count+1; }; }; Delete: PROC [keyVal: KeyIndex] RETURNS [found: BOOL] = { key: BTreeSimple.Key = KeyFromIndex[keyVal]; found _ BTreeSimple.DeleteKey[tree: myTree, key: key]; IF found THEN { entryTable.count _ entryTable.count-1; entryTable.exists[keyVal] _ FALSE; }; }; KeyFromIndex: PROC [keyIndex: KeyIndex] RETURNS [key: BTreeSimple.Key] = { <> RETURN[Convert.RopeFromCard[100000+keyIndex]]; }; <> 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]]; }; }.