> useFixedSeed: BOOLEAN _ TRUE; validateEveryUpdate: BOOLEAN _ 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: PROCEDURE [iterations: LONG CARDINAL] RETURNS [msPerOp: ARRAY Operation OF REAL] = BEGIN counts: ARRAY Operation OF LONG CARDINAL _ ALL [0]; times: ARRAY Operation OF LONG CARDINAL _ 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: 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; END; VMStats: PROCEDURE RETURNS [refs: LONG CARDINAL, hitPercent: REAL, reads, writes: LONG CARDINAL, msPerReadWrite, avgChainLength: REAL] = BEGIN 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]]; END; MissingEntry: SIGNAL [k: KeyIndex] = CODE; EnumerateFailedToTerminate: SIGNAL = 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; EnumerateBackward: PROCEDURE [usePathStk: BOOLEAN _ FALSE] = TRUSTED BEGIN EntryProc: UNSAFE PROCEDURE [key: BTreeSimple.EntryKey, value: BTreeSimple.EntryValue] = UNCHECKED BEGIN foundKey _ BTreeSimple.KeyFromEntry[key]; foundKeyIndex _ IF value#NIL THEN value[0] ELSE 0; END; 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 BEGIN BTreeSimple.ReadEntry[tree: myTree, key: foundKey, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk]; IF foundKey=NIL OR foundKeyIndex#k THEN SIGNAL MissingEntry[k]; END; ENDLOOP; BTreeSimple.ReadEntry[tree: myTree, key: foundKey, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk]; IF foundKey#NIL THEN SIGNAL EnumerateFailedToTerminate; END; <> 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 BOOLEAN]; entryTable: REF EntryTable; Create: PROCEDURE [cacheSize: BTreeSimple.CacheSize _ 20, initialize: BOOLEAN _ TRUE, initialFileSize: INT _ 20, filePagesPerPage: BTreeSimple.FilePagesPerPage _ 1, maxEntries: KeyIndex _ 10000] RETURNS [tree: BTreeSimple.Tree] = BEGIN IF initialize AND file#FS.nullOpenFile AND file.GetInfo[].pages CONTINUE]; file _ FS.nullOpenFile; END; myTree _ NIL; 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. BTreeSimple.Validate[myTree]; 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 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; END; Insert: PROCEDURE [keyVal: KeyIndex] = BEGIN key: BTreeSimple.Key = KeyFromIndex[keyVal]; valueLength: CARDINAL = RandomCard.Choose[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 }; END; Delete: PROCEDURE [keyVal: KeyIndex] RETURNS [found: BOOLEAN] = BEGIN key: BTreeSimple.Key = KeyFromIndex[keyVal]; found _ BTreeSimple.DeleteKey[tree: myTree, key: key]; IF found THEN { entryTable.count _ entryTable.count-1; entryTable.exists[keyVal] _ FALSE }; END; KeyFromIndex: PROCEDURE [keyIndex: KeyIndex] RETURNS [key: BTreeSimple.Key] = INLINE {RETURN[Convert.RopeFromCard[100000+keyIndex]]}; -- keys from 100000 to 165535, so ASCII collating sequence is same as numeric <> MultThenDiv: PROC [m1: LONG CARDINAL, m2: CARDINAL, dv: CARDINAL] RETURNS [result: LONG CARDINAL] = BEGIN 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 BEGIN t.highlong _ LongMult[mm1.highbits, m2] + t.mid; IF t.high # 0 THEN BEGIN 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; END; END; <> RETURN[t.lowlong/LONG[dv]]; END; END.