<<>> <> <> <> <> <> <> <> <<>> DIRECTORY Basics, BasicTime, BTree, BTreeSimple, Commander, Convert, IO, Random, RealSupport, Rope, PFS; BTreeSimpleTest: CEDAR PROGRAM IMPORTS BasicTime, BTreeSimple, Commander, Convert, IO, Random, RealSupport, PFS = { ROPE: TYPE = Rope.ROPE; maxEntSize: CARD ¬ 256; -- 1/8 minimum-size page <> entryTable: REF EntryTable; EntryTable: TYPE = RECORD [ count: KeyIndex, exists: PACKED SEQUENCE maxEntries: KeyIndex OF BOOL ]; useFixedSeed: BOOL ¬ TRUE; markov: Random.RandomStream ¬ NIL; validateEveryUpdate: BOOL ¬ FALSE; millisecondsPerPulse: REAL = 1000.0 / RealSupport.IntToReal[BasicTime.MicrosecondsToPulses[1000000]]; OperationArray: TYPE = ARRAY Operation OF CARD ; Operation: TYPE = {lookup, validate, insert, delete, replace}; UpdateOperation: TYPE = Operation[insert..replace]; KeyIndex: TYPE = CARD; Error: PUBLIC ERROR [ec: ErrorCode, explanation: ROPE ¬ NIL]; ErrorCode: TYPE = ATOM; <<>> <> Create: PUBLIC PROC [readBacking, writeBacking: IO.STREAM, cacheSize: BTreeSimple.CacheSize ¬ 40, initialize: BOOL ¬ TRUE, pageSize: BTreeSimple.PageSize ¬ 2048, maxEntries: KeyIndex ¬ 10000] RETURNS [tree: BTreeSimple.Tree] = { IF readBacking = NIL OR writeBacking = NIL THEN ERROR Error[$NoBackingStream, "Backing stream is NIL"]; tree ¬ BTreeSimple.New[]; BTreeSimple.Open[tree: tree, readFile: readBacking, writeFile: writeBacking, pageSize: pageSize, cacheSize: cacheSize, initialize: initialize]; IF initialize THEN { entryTable ¬ NEW [EntryTable[maxEntries]]; entryTable.count ¬ 0; <> FOR i: KeyIndex IN [0..entryTable.maxEntries) DO entryTable.exists[i] ¬ FALSE; ENDLOOP; }; RETURN[tree]; }; <> Insert: PROC [myTree: BTreeSimple.Tree, keyVal: KeyIndex] = { <> key: BTreeSimple.Key = IndexToKey[keyVal]; <> valueLength: CARD = Random.ChooseInt[markov, 1, maxEntSize]; value: BTreeSimple.Value; <> value ¬ NEW[BTreeSimple.ValueObject[valueLength]]; <> FOR i: CARD 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; }; }; Lookup: PROC [myTree: BTreeSimple.Tree, keyVal: KeyIndex] RETURNS [found: BOOL] = { key: BTreeSimple.Key = IndexToKey[keyVal]; actualKey: BTreeSimple.InternalKey; value: BTreeSimple.Value; [actualKey, value] ¬ BTreeSimple.ReadRecord[tree: myTree, key: key]; IF (found ¬ actualKey#NIL) THEN FOR i: CARD IN [0..value.length) DO IF value[i]#keyVal THEN ERROR Error[$wrongContents, "Entry has wrong contents"]; -- entry has wrong contents ENDLOOP; RETURN [found]; }; Delete: PROC [myTree: BTreeSimple.Tree, keyVal: KeyIndex] RETURNS [found: BOOL] = { key: BTreeSimple.Key = IndexToKey[keyVal]; found ¬ BTreeSimple.DeleteKey[tree: myTree, key: key]; IF found THEN { entryTable.count ¬ entryTable.count-1; entryTable.exists[keyVal] ¬ FALSE; }; RETURN [found]; }; IndexToKey: PROC [keyIndex: KeyIndex] RETURNS [key: BTreeSimple.Key] = { <> RETURN[Convert.RopeFromCard[100000+keyIndex]]; }; keyOfInterest: CARD ¬ LAST[CARD]; RandomOperation: PUBLIC SAFE PROC [myTree: BTreeSimple.Tree] 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 ERROR Error[$EncounteredKeyOfInterest, "Interesting key encountered."]; IF entryTable.exists[key] THEN { <> SELECT Random.ChooseInt[markov, 0, 3] FROM 0 => { operation ¬ lookup; IF ~Lookup[myTree, key] THEN ERROR Error[$KeyNotFound, "key doesn't exist"]; -- failed to find existing key }; 1 => { operation ¬ delete; IF ~Delete[myTree, key] THEN ERROR Error[$KeyNotFound, "key doesn't exist"]; -- failed to find existing key }; ENDCASE => { operation ¬ replace; Insert[myTree, 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[myTree, key] THEN ERROR Error[$FoundKey, "found key that shouldn't be there"]; -- found key that it shouldn't have }; ENDCASE => { operation ¬ insert; Insert[myTree, key]; }; }; }; }; EnumerateBackward: PROC [myTree: BTreeSimple.Tree, 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 ¬ IndexToKey[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; }; GetEntryCount: PUBLIC SAFE PROC RETURNS [count: CARD] = CHECKED { RETURN [entryTable.count]; }; <<>> GetVMStats: PROC [myTree: BTreeSimple.Tree] RETURNS [refs, reads, writes: CARD, hitPercent: REAL, msPerReadWrite, avgChainLength: REAL] = { hits, misses, cumChainLength, cumReadWriteTime: CARD; [hits: hits, misses: misses, reads: reads, writes: writes, cumChainLength: cumChainLength, cumReadWriteTime: cumReadWriteTime] ¬ BTreeSimple.GetStatistics[myTree]; refs ¬ hits+misses; hitPercent ¬ RealSupport.IntToReal[hits]*100.0 / RealSupport.IntToReal[MAX[refs, 1]]; msPerReadWrite ¬ (RealSupport.IntToReal[cumReadWriteTime] / RealSupport.IntToReal[MAX[reads+writes, 1]]) * millisecondsPerPulse; avgChainLength ¬ RealSupport.IntToReal[cumChainLength] / RealSupport.IntToReal[MAX[refs, 1]]; }; MissingEntry: SIGNAL [k: KeyIndex] = CODE; EnumerateFailedToTerminate: SIGNAL = CODE; FindMissingEntries: PROC [myTree: BTreeSimple.Tree] = { FOR k: KeyIndex IN [0..entryTable.maxEntries) DO IF entryTable.exists[k] AND ~Lookup[myTree, k] THEN SIGNAL MissingEntry[k]; ENDLOOP; }; <> ElapsedTime: PROC [start, stop: BasicTime.Pulses] RETURNS [ROPE] ~ { microseconds, seconds: CARD; digit: CARD; any: BOOL ¬ FALSE; text: REF TEXT ¬ NEW[TEXT[8]]; microseconds ¬ BasicTime.PulsesToMicroseconds[stop - start]; seconds ¬ microseconds / 1000000; microseconds ¬ microseconds MOD 1000000; THROUGH [0..6) DO microseconds ¬ microseconds * 10; digit ¬ microseconds / 1000000; microseconds ¬ microseconds MOD 1000000; IF NOT any THEN { text ¬ Convert.AppendChar[to: text, from: '., quote: FALSE]; any ¬ TRUE; }; text ¬ Convert.AppendChar[to: text, from: digit + '0, quote: FALSE]; IF microseconds = 0 THEN EXIT; ENDLOOP; RETURN [IO.PutFR["%r%g\n", IO.card[seconds], IO.text[text]]]; }; <> RunTest: PROC [myTree: BTreeSimple.Tree, iterations: CARD] RETURNS [msPerOp: ARRAY Operation OF REAL] = { index: CARD; counts: ARRAY Operation OF CARD ¬ ALL [0]; times: ARRAY Operation OF CARD ¬ ALL [0]; IF iterations < 1 THEN ERROR; FOR index IN [1..iterations] DO operation: Operation; k: KeyIndex; then: BasicTime.Pulses ¬ BasicTime.GetClockPulses[]; [operation: operation, key: k] ¬ RandomOperation[myTree]; 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]; ENDLOOP; <> FOR operation: Operation IN Operation DO msPerOp[operation] ¬ (RealSupport.IntToReal[times[operation]]/RealSupport.IntToReal[MAX[counts[operation], 1]]) * millisecondsPerPulse; ENDLOOP; }; BTreeSimpleTest: Commander.CommandProc = { myTree: BTreeSimple.Tree; writeBacking, readBacking: IO.STREAM; msPerOp: ARRAY Operation OF REAL; refs, reads, writes: CARD; hitPercent, msPerReadWrite, avgChainLength: REAL; filename: ROPE ¬ NIL; iterations: CARD ¬ 0; okay: BOOLEAN ¬ TRUE; IO.PutRope[cmd.out, "Name of file to hold BTree: "]; filename ¬ IO.GetLineRope[cmd.in]; IF filename = NIL THEN { filename ¬ "BTreeTest.tree"; -- default filename }; IO.PutRope[cmd.out, "Number of iterations to perform: "]; iterations ¬ Convert.CardFromRope[IO.GetLineRope[cmd.in] ! Convert.Error => {IO.PutRope[cmd.out, "Error from BTreeSimpleTest: not a number\n"]; RETRY} ]; writeBacking ¬ PFS.StreamOpen[PFS.PathFromRope[filename], $write]; readBacking ¬ PFS.StreamOpen[PFS.PathFromRope[filename], $read]; myTree ¬ Create[readBacking, writeBacking, 500]; [msPerOp] ¬RunTest[myTree, iterations ! Error => {IO.PutF[cmd.out, "Error from BTreeSimpleTest: %g - %g\n", IO.atom[ec], IO.rope[explanation]]; CONTINUE}; ]; FOR operation: Operation IN Operation DO { opname: ROPE ¬ NIL; SELECT operation FROM lookup => opname ¬ "lookup"; validate => opname ¬ "validate"; insert => opname ¬ "insert"; delete => opname ¬ "delete"; replace => opname ¬ "replace"; ENDCASE; IO.PutF[cmd.out, " %g = %g msec\n", IO.rope[opname], IO.real[msPerOp[operation]]]; }; ENDLOOP; IO.PutRope[cmd.out, "\n Virtual memory statistics.\n\n"]; [refs, reads, writes, hitPercent, msPerReadWrite, avgChainLength] ¬ GetVMStats[myTree]; IO.PutF[cmd.out, " %g = %g \n", IO.rope["Hits and misses"], IO.card[refs]]; IO.PutF[cmd.out, " %g = %g \n", IO.rope["Reads"], IO.card[reads]]; IO.PutF[cmd.out, " %g = %g \n", IO.rope["Writes"], IO.card[writes]]; IO.PutF[cmd.out, " %g = %g \n", IO.rope["Percentage hit"], IO.real[hitPercent]]; IO.PutF[cmd.out, " %g = %g \n", IO.rope["Milliseconds per read/write"], IO.real[msPerReadWrite]]; IO.PutF[cmd.out, " %g = %g \n", IO.rope["Average chain length"], IO.real[avgChainLength]]; <> IO.Flush[writeBacking]; IO.Close[writeBacking]; IO.Close[readBacking]; }; Commander.Register[key: "BTreeSimpleTest", proc: BTreeSimpleTest, doc: "Test the BTreeSimple package." ]; }.