<> <> DIRECTORY BTree, BTreeTestOps, BTreeVM, File, PrincOps, PrincOpsUtils, ProcessorFace, RandomCard, Real; BTreeTestImpl: PROGRAM IMPORTS BTree, BTreeVM, File, RandomCard, PrincOpsUtils, ProcessorFace, Real 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 [BTree.Comparison] = BEGIN e: CARDINAL = entry.keys[0]; RETURN [SELECT NARROW[key, Key]^ FROM less, =e => equal, ENDCASE => greater]; END; CompareEntries: PROCEDURE [entry1, entry2: Entry] RETURNS [BTree.Comparison] = BEGIN e1: CARDINAL = entry1.keys[0]; e2: CARDINAL = entry2.keys[0]; RETURN [SELECT e1 FROM less, =e2 => equal, ENDCASE => greater]; END; EntrySize: PROCEDURE [entry: Entry] RETURNS [words: BTree.EntSize] = { 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]]; PrincOpsUtils.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; <<>> <<>> <
> useFixedSeed: BOOLEAN _ TRUE; validateEveryUpdate: BOOLEAN _ FALSE; millisecondsPerPulse: REAL = 1000.0 / Real.Float[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 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: LONG CARDINAL _ PrincOpsUtils.GetClockPulses[]; [operation: operation, key: k] _ PerformRandomOperation[]; times[operation] _ times[operation] + (PrincOpsUtils.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, 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]]; 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] = BEGIN EntryProc: PROCEDURE [entry: Entry] = BEGIN found _ entry#NIL; IF found THEN foundKey _ entry.keys[0]; END; found: BOOLEAN; 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 BEGIN key^ _ foundKey; myTree.ReadEntry[key: key, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk]; IF ~found OR foundKey#k THEN SIGNAL MissingEntry[k]; END; ENDLOOP; key^ _ foundKey; myTree.ReadEntry[key: key, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk]; IF found THEN SIGNAL EnumerateFailedToTerminate; END; <<>> <<>> <> ConcreteKey: PROCEDURE [key: BTree.Key] RETURNS [Key] = { RETURN [NARROW[key]] }; ConcreteEntry: PROCEDURE [entry: BTree.Entry] RETURNS [Entry] = { RETURN [entry] }; <<>> <<>> <> file: File.Handle _ NIL; 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#NIL AND file.Info[].size 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 ProduceEntry: PROCEDURE [bEntry: BTree.Entry] = { PrincOpsUtils.LongCOPY[to: bEntry, from: entry, nwords: words] }; copies: CARDINAL = RandomCard.Choose[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 }; 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; <<>> <> PulsesToMicroseconds: PUBLIC SAFE PROC [p: LONG CARDINAL] RETURNS [LONG CARDINAL] = TRUSTED BEGIN -- (p*msPerHp)/(100units/hundred) RETURN[MultThenDiv[p, ProcessorFace.microsecondsPerHundredPulses, 100]] END; MicrosecondsToPulses: PUBLIC SAFE PROC [m: LONG CARDINAL] RETURNS [LONG CARDINAL] = TRUSTED BEGIN -- (microseconds*100units/hundred)/microsecondsPerHundredPulses RETURN[MultThenDiv[m, 100, ProcessorFace.microsecondsPerHundredPulses]] END; MultThenDiv: PROC [m1: LONG CARDINAL, m2: CARDINAL, dv: CARDINAL] RETURNS [result: LONG CARDINAL] = BEGIN OPEN PrincOpsUtils, mm1: LOOPHOLE[m1, num PrincOps.LongNumber]; 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, num PrincOps.LongNumber]; <> 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.