-- BTreeTestTool.mesa -- Last Edited by: Taft, March 26, 1983 10:38 am DIRECTORY BTree USING [GetState, Tree, Validate], BTreeTestOps, BTreeVM, Buttons USING [Button, ButtonProc, Create, ReLabel], Containers USING [Container, Create], Convert USING [IntFromRope, ValueToRope], IO USING [PutFR], Labels USING [Create, Label, Set], Menus USING [AppendMenuEntry, CreateEntry, CreateMenu, Menu, MenuProc], MessageWindow USING [Append, Blink], Process USING [Detach, GetCurrent], RandomCard USING [Init], Real USING [Float], Rope USING [Concat, Length, ROPE, Substr], SafeStorage USING [NarrowFault], System USING [GetClockPulses, MicrosecondsToPulses, Pulses], VFonts USING [CharWidth, StringWidth], ViewerClasses USING [Viewer, ViewerClassRec], ViewerEvents USING [EventProc, RegisterEventProc], ViewerOps USING [AddProp, CreateViewer, FetchProp, SetMenu], ViewerTools USING [GetContents, MakeNewTextViewer, SetSelection]; BTreeTestTool: CEDAR PROGRAM IMPORTS BTree, BTreeTestOps, BTreeVM, Buttons, Containers, Convert, IO, Labels, Menus, MessageWindow, Process, RandomCard, Real, Rope, SafeStorage, System, VFonts, ViewerEvents, ViewerOps, ViewerTools = BEGIN entryHeight: CARDINAL = 15; -- how tall to make each line of items entryVSpace: CARDINAL = 8; -- vertical leading space between lines entryHSpace: CARDINAL = 8; -- horizontal space between items in a line Handle: TYPE = REF BTreeTestToolRec; BTreeTestToolRec: TYPE = RECORD [ -- the data for a particular tool instance outer: Containers.Container _ NIL, -- handle for the enclosing container height: CARDINAL _ 0, -- height measured from the top of the container idleMenu, activeMenu: Menus.Menu, parV: ParametersViewer, -- viewer containing user input parameters resV: ResultsViewer, -- viewer containing test results params: Params, -- parameters for setting up BTree results: Results, -- record of result values tree: BTree.Tree _ NIL, storage: BTreeVM.Handle _ NIL, initTree: BOOLEAN _ TRUE, process: PROCESS _ NIL, pleaseStop, pleaseDestroy: BOOLEAN _ FALSE]; MakeBTreeTestTool: PROCEDURE = BEGIN handle: Handle _ NEW[BTreeTestToolRec]; handle.idleMenu _ Menus.CreateMenu[]; Menus.AppendMenuEntry[ menu: handle.idleMenu, entry: Menus.CreateEntry[ name: "Start", proc: StartCommand, clientData: handle] ]; Menus.AppendMenuEntry[ menu: handle.idleMenu, entry: Menus.CreateEntry[ name: "InitTree", proc: InitTreeCommand, clientData: handle] ]; Menus.AppendMenuEntry[ menu: handle.idleMenu, entry: Menus.CreateEntry[ name: "ResetStats", proc: ResetStatsCommand, clientData: handle] ]; handle.activeMenu _ Menus.CreateMenu[]; Menus.AppendMenuEntry[ menu: handle.activeMenu, entry: Menus.CreateEntry[ name: "Stop", proc: StopCommand, clientData: handle] ]; handle.outer _ Containers.Create[[ name: "BTreeTest", iconic: FALSE, column: left, menu: handle.idleMenu, scrollable: TRUE ]]; MakeParametersViewer[handle]; MakeResultsViewer[handle]; ViewerOps.AddProp[viewer: handle.outer, prop: $handle, val: handle]; [] _ ViewerEvents.RegisterEventProc[proc: DestroyEvent, event: destroy, filter: handle.outer, before: TRUE]; END; DestroyEvent: ViewerEvents.EventProc --[viewer: ViewerClasses.Viewer, event: ViewerEvent, before: BOOL] RETURNS[abort: BOOL _ FALSE]-- = BEGIN handle: Handle = NARROW[ViewerOps.FetchProp[viewer: viewer, prop: $handle]]; handle.pleaseStop _ handle.pleaseDestroy _ TRUE; IF handle.process=NIL THEN TRUSTED { Process.Detach[FORK BTreeTestOps.Destroy[]] }; END; ParametersViewer: TYPE = RECORD [ pageSizeButton: Buttons.Button _ NIL, pageSize: ViewerClasses.Viewer _ NIL, cacheSizeButton: Buttons.Button _ NIL, cacheSize: ViewerClasses.Viewer _ NIL, maxTreeSizeButton: Buttons.Button _ NIL, maxTreeSize: ViewerClasses.Viewer _ NIL, longUpdate: Buttons.Button _ NIL, validateEveryUpdate: Buttons.Button _ NIL]; MakeParametersViewer: PROCEDURE [handle: Handle] = BEGIN OPEN par: handle.parV; MakePromptButton: PROCEDURE [name, initialValue: Rope.ROPE] RETURNS [button: Buttons.Button, viewer: ViewerClasses.Viewer] = BEGIN button _ Buttons.Create[ info: [ name: name, wx: xPos, wy: handle.height, -- default the width so that it will be computed for us -- wh: entryHeight, -- specify rather than defaulting so line is uniform parent: handle.outer, border: FALSE ], proc: Prompt]; viewer _ ViewerTools.MakeNewTextViewer[ [ parent: handle.outer, wx: button.wx + button.ww + entryHSpace, wy: handle.height+2, ww: 7*VFonts.CharWidth['0], wh: entryHeight, data: initialValue, -- initial contents scrollable: FALSE, border: FALSE]]; ViewerOps.AddProp[viewer: button, prop: $value, val: viewer]; xPos _ viewer.wx + viewer.ww + entryHSpace; END; MakeBoolButton: PROCEDURE [name: Rope.ROPE, initialValue: BOOLEAN] RETURNS [button: Buttons.Button] = BEGIN button _ Buttons.Create[ info: [ name: Rope.Concat[name, IF initialValue THEN ": Yes" ELSE ": No "], wx: xPos, wy: handle.height, -- default the width so that it will be computed for us -- wh: entryHeight, -- specify rather than defaulting so line is uniform parent: handle.outer, border: FALSE ], proc: BoolButton]; ViewerOps.AddProp[viewer: button, prop: $value, val: NEW [BOOLEAN _ initialValue]]; xPos _ button.wx + button.ww + entryHSpace; END; xPos: CARDINAL _ 0; handle.height _ handle.height + entryVSpace; -- space down from the top of the viewer [button: par.pageSizeButton, viewer: par.pageSize] _ MakePromptButton[name: "DiskPages/BTreePage:", initialValue: "1"]; [button: par.cacheSizeButton, viewer: par.cacheSize] _ MakePromptButton[name: "CacheSize:", initialValue: "20"]; [button: par.maxTreeSizeButton, viewer: par.maxTreeSize] _ MakePromptButton[name: "MaxTreeEntries:", initialValue: "10000"]; xPos _ 0; handle.height _ handle.height + entryHeight + entryVSpace; par.longUpdate _ MakeBoolButton[name: "LongUpdate", initialValue: FALSE]; par.validateEveryUpdate _ MakeBoolButton[name: "ValidateEveryUpdate", initialValue: FALSE]; handle.height _ handle.height + entryHeight + entryVSpace; -- interline spacing END; Prompt: Buttons.ButtonProc = BEGIN -- force the selection into the user input field viewer: ViewerClasses.Viewer _ NARROW[ViewerOps.FetchProp[viewer: NARROW[parent], prop: $value]]; ViewerTools.SetSelection[viewer]; -- force the selection END; BoolButton: Buttons.ButtonProc = BEGIN button: Buttons.Button = NARROW[parent]; value: REF BOOLEAN = NARROW[ViewerOps.FetchProp[viewer: button, prop: $value]]; name: Rope.ROPE = Rope.Substr[base: button.name, len: Rope.Length[button.name]-3]; value^ _ ~value^; Buttons.ReLabel[button: button, newName: Rope.Concat[name, IF value^ THEN "Yes" ELSE "No "]]; END; Params: TYPE = RECORD [ cacheSize: BTreeVM.CacheSize _ 20, filePagesPerPage: BTreeVM.FilePagesPerPage _ 1, maxEntries: BTreeTestOps.KeyIndex _ 10000, longUpdate, validateEveryUpdate: BOOLEAN _ FALSE]; ParamError: ERROR [message: Rope.ROPE] = CODE; ParseParams: PROCEDURE [handle: Handle] RETURNS [params: Params] = BEGIN OPEN pv: handle.parV; IntervalFromRope: PROCEDURE [r: Rope.ROPE, min, max: INT] RETURNS [result: INT] = BEGIN result _ Convert.IntFromRope[r ! SafeStorage.NarrowFault => GOTO notNumber]; IF result NOT IN [min..max] THEN ERROR ParamError[IO.PutFR["\"%g\" is out of bounds; must be in the range [%g..%g]", [rope[r]], [integer[min]], [integer[max]]]]; EXITS notNumber => ERROR ParamError[IO.PutFR["\"%g\" is not a number", [rope[r]]]]; END; params.cacheSize _ IntervalFromRope[r: ViewerTools.GetContents[pv.cacheSize], min: FIRST[BTreeVM.CacheSize], max: LAST[BTreeVM.CacheSize]]; params.filePagesPerPage _ IntervalFromRope[r: ViewerTools.GetContents[pv.pageSize], min: FIRST[BTreeVM.FilePagesPerPage], max: LAST[BTreeVM.FilePagesPerPage]]; params.maxEntries _ IntervalFromRope[r: ViewerTools.GetContents[pv.maxTreeSize], min: 100, max: LAST[BTreeTestOps.KeyIndex]]; params.longUpdate _ NARROW[ViewerOps.FetchProp[viewer: pv.longUpdate, prop: $value], REF BOOLEAN]^; params.validateEveryUpdate _ NARROW[ViewerOps.FetchProp[viewer: pv.validateEveryUpdate, prop: $value], REF BOOLEAN]^; END; ResultsViewer: TYPE = RECORD [ treePages, treeLevels, treeEntries: Labels.Label, operations: ARRAY Operation OF Labels.Label, totalOperations: Labels.Label, msPerOp: ARRAY Operation OF Labels.Label, cacheRefs, hitPercent, reads, writes, writesPerUpdate: Labels.Label, elapsed, percentRW, msPerReadWrite: Labels.Label]; Operation: TYPE = BTreeTestOps.Operation; MakeResultsViewer: PROCEDURE [handle: Handle] = BEGIN OPEN res: handle.resV; MakeLabel: PROCEDURE [value: Rope.ROPE, width: CARDINAL _ 0] RETURNS [label: Labels.Label] = BEGIN label _ Labels.Create[ [ name: value, wx: xPos, wy: handle.height, ww: IF width#0 THEN width ELSE VFonts.StringWidth[value], wh: entryHeight, parent: handle.outer, border: FALSE]]; xPos _ label.wx + label.ww + entryHSpace; END; charWidth: CARDINAL = VFonts.CharWidth['0]; itemWidth: CARDINAL = 12*charWidth; xPos: CARDINAL _ 0; handle.height _ handle.height + entryVSpace; [] _ MakeLabel["Tree size: Pages:"]; res.treePages _ MakeLabel["0", 6*charWidth]; [] _ MakeLabel["Levels:"]; res.treeLevels _ MakeLabel["0", 4*charWidth]; [] _ MakeLabel["Entries:"]; res.treeEntries _ MakeLabel["0", 8*charWidth]; handle.height _ handle.height + entryHeight + entryVSpace; xPos _ itemWidth + entryHSpace; [] _ MakeLabel["Lookup", itemWidth]; [] _ MakeLabel["Enumerate", itemWidth]; [] _ MakeLabel["Insert", itemWidth]; [] _ MakeLabel["Delete", itemWidth]; [] _ MakeLabel["Replace", itemWidth]; [] _ MakeLabel["Total", itemWidth]; xPos _ 0; handle.height _ handle.height + entryHeight + entryVSpace; [] _ MakeLabel["Operations", itemWidth]; FOR op: Operation IN Operation DO res.operations[op] _ MakeLabel["0", itemWidth]; ENDLOOP; res.totalOperations _ MakeLabel["0", itemWidth]; xPos _ 0; handle.height _ handle.height + entryHeight; [] _ MakeLabel["ms/op", itemWidth]; FOR op: Operation IN Operation DO res.msPerOp[op] _ MakeLabel["0", itemWidth]; ENDLOOP; handle.height _ handle.height + entryHeight + entryVSpace; xPos _ 0; [] _ MakeLabel["CacheRefs: "]; res.cacheRefs _ MakeLabel["0", 9*charWidth]; [] _ MakeLabel["Hit%: "]; res.hitPercent _ MakeLabel["0", 5*charWidth]; handle.height _ handle.height + entryHeight + entryVSpace; xPos _ 0; [] _ MakeLabel["Storage Reads: "]; res.reads _ MakeLabel["0", 9*charWidth]; [] _ MakeLabel["Writes: "]; res.writes _ MakeLabel["0", 9*charWidth]; [] _ MakeLabel["Writes/update: "]; res.writesPerUpdate _ MakeLabel["0", 7*charWidth]; handle.height _ handle.height + entryHeight + entryVSpace; xPos _ 0; [] _ MakeLabel["Total elapsed time (sec): "]; res.elapsed _ MakeLabel["0", 9*charWidth]; [] _ MakeLabel["% R+W time: "]; res.percentRW _ MakeLabel["0", 5*charWidth]; [] _ MakeLabel["ms/(R or W): "]; res.msPerReadWrite _ MakeLabel["0", 5*charWidth]; handle.height _ handle.height + entryHeight + entryVSpace; END; Results: TYPE = RECORD [ counts: ARRAY Operation OF LONG CARDINAL _ ALL [0], times: ARRAY Operation OF System.Pulses _ ALL [[0]], seedUsed: INTEGER _ RandomCard.Init[0], treePages, treeLevels: CARDINAL _ 0, treeEntries: LONG CARDINAL _ 0, hits, misses, reads, writes: LONG CARDINAL _ 0, cumReadWriteTime: System.Pulses _ [0]]; DisplayResults: PROCEDURE [handle: Handle] = BEGIN OPEN rv: handle.resV, res: handle.results; totalOperations: LONG CARDINAL _ 0; totalTime: System.Pulses _ [0]; millisecondsPerPulse: REAL = 1000.0 / Real.Float[System.MicrosecondsToPulses[1000000]]; Labels.Set[rv.treePages, Convert.ValueToRope[[unsigned[res.treePages]]]]; Labels.Set[rv.treeLevels, Convert.ValueToRope[[unsigned[res.treeLevels]]]]; Labels.Set[rv.treeEntries, Convert.ValueToRope[[unsigned[res.treeEntries]]]]; FOR op: Operation IN Operation DO Labels.Set[rv.operations[op], Convert.ValueToRope[[unsigned[res.counts[op]]]]]; totalOperations _ totalOperations+res.counts[op]; totalTime _ [totalTime+res.times[op]]; ENDLOOP; Labels.Set[rv.totalOperations, Convert.ValueToRope[[unsigned[totalOperations]]]]; FOR op: Operation IN Operation DO msPerOp: REAL = (Real.Float[res.times[op]] / Real.Float[MAX[res.counts[op], 1]]) * millisecondsPerPulse; Labels.Set[rv.msPerOp[op], Convert.ValueToRope[[real[real: msPerOp, precision: 3]]]]; ENDLOOP; Labels.Set[rv.cacheRefs, Convert.ValueToRope[[unsigned[res.hits+res.misses]]]]; Labels.Set[rv.hitPercent, Convert.ValueToRope[[real[real: Real.Float[res.hits]*100.0 / Real.Float[MAX[res.hits+res.misses, 1]], precision: 3]]]]; Labels.Set[rv.reads, Convert.ValueToRope[[unsigned[res.reads]]]]; Labels.Set[rv.writes, Convert.ValueToRope[[unsigned[res.writes]]]]; Labels.Set[rv.writesPerUpdate, Convert.ValueToRope[[real[real: Real.Float[res.writes] / Real.Float[MAX[res.counts[insert]+res.counts[delete]+res.counts[replace], 1]], precision: 3]]]]; Labels.Set[rv.elapsed, Convert.ValueToRope[[real[real: Real.Float[totalTime] * millisecondsPerPulse/1000.0, precision: 3]]]]; Labels.Set[rv.percentRW, Convert.ValueToRope[[real[real: Real.Float[res.cumReadWriteTime]*100.0 / Real.Float[MAX[totalTime, 1]], precision: 3]]]]; Labels.Set[rv.msPerReadWrite, Convert.ValueToRope[[real[real: (Real.Float[res.cumReadWriteTime] / Real.Float[MAX[res.reads+res.writes, 1]]) * millisecondsPerPulse, precision: 3]]]]; END; StartCommand: Menus.MenuProc = BEGIN handle: Handle = NARROW [clientData]; params: Params _ ParseParams[handle ! ParamError => { MessageWindow.Append[message: message, clearFirst: TRUE]; GOTO paramError }]; IF ~handle.initTree AND params#handle.params THEN BEGIN IF params.filePagesPerPage#handle.params.filePagesPerPage OR params.maxEntries#handle.params.maxEntries THEN BEGIN MessageWindow.Append[message: "Parameters changed; you must InitTree first", clearFirst: TRUE]; GOTO paramError; END; handle.tree _ NIL; handle.storage _ NIL; END; handle.params _ params; IF handle.tree=NIL THEN [tree: handle.tree, storage: handle.storage] _ BTreeTestOps.Create[cacheSize: params.cacheSize, initialize: handle.initTree, filePagesPerPage: params.filePagesPerPage, maxEntries: params.maxEntries]; handle.initTree _ FALSE; IF params.longUpdate THEN handle.storage.StartLongUpdate[]; handle.pleaseStop _ FALSE; handle.process _ FORK TestProc[handle]; ViewerOps.SetMenu[viewer: handle.outer, menu: handle.activeMenu]; EXITS paramError => MessageWindow.Blink[]; END; StopCommand: Menus.MenuProc = BEGIN handle: Handle = NARROW [clientData]; handle.pleaseStop _ TRUE; TRUSTED { JOIN handle.process }; handle.process _ NIL; ViewerOps.SetMenu[viewer: handle.outer, menu: handle.idleMenu]; END; InitTreeCommand: Menus.MenuProc = BEGIN handle: Handle = NARROW [clientData]; handle.tree _ NIL; handle.storage _ NIL; handle.initTree _ TRUE; handle.results _ []; DisplayResults[handle]; END; ResetStatsCommand: Menus.MenuProc = BEGIN handle: Handle = NARROW [clientData]; handle.tree _ NIL; handle.storage _ NIL; handle.results _ []; DisplayResults[handle]; END; TestProc: PROCEDURE [handle: Handle] = BEGIN OPEN res: handle.results; ENABLE UNWIND => IF ~handle.pleaseStop THEN BEGIN ViewerOps.SetMenu[viewer: handle.outer, menu: handle.idleMenu]; TRUSTED { Process.Detach[Process.GetCurrent[]] }; END; lastUpdateTime: System.Pulses _ System.GetClockPulses[]; updateInterval: LONG CARDINAL = 3*System.MicrosecondsToPulses[1000000]; UNTIL handle.pleaseStop DO operation: BTreeTestOps.Operation; k: BTreeTestOps.KeyIndex; then: System.Pulses _ System.GetClockPulses[]; now: System.Pulses; [operation: operation, key: k] _ BTreeTestOps.PerformRandomOperation[]; now _ System.GetClockPulses[]; res.times[operation] _ [res.times[operation] + (now - then)]; res.counts[operation] _ res.counts[operation]+(IF operation=validate THEN handle.tree.GetState[].entryCount ELSE 1); IF handle.params.validateEveryUpdate THEN BEGIN myCount: LONG CARDINAL = BTreeTestOps.GetEntryCount[]; then _ System.GetClockPulses[]; handle.tree.Validate[]; now _ System.GetClockPulses[]; res.times[validate] _ [res.times[validate] + (now - then)]; res.counts[validate] _ res.counts[validate] + myCount; IF handle.tree.GetState[].entryCount # myCount THEN ERROR; -- entry count disagrees. Call BTreeTestImpl.FindMissingEntries to find the missing ones. END; IF now-lastUpdateTime > updateInterval OR handle.pleaseStop THEN BEGIN [entryCount: res.treeEntries, greatestPage: res.treePages, depth: res.treeLevels] _ handle.tree.GetState[]; [hits: res.hits, misses: res.misses, reads: res.reads, writes: res.writes, cumReadWriteTime: res.cumReadWriteTime] _ handle.storage.GetStats[]; DisplayResults[handle]; lastUpdateTime _ now; END; ENDLOOP; IF handle.params.longUpdate THEN handle.storage.EndLongUpdate[]; IF handle.pleaseDestroy THEN BEGIN BTreeTestOps.Destroy[]; TRUSTED { Process.Detach[Process.GetCurrent[]] }; END; END; -- Initialization MakeBTreeTestTool[]; END. ΚΛ– "Cedar" style˜Iproc– "Cedar" stylešΟc˜Jš0˜0unitšΟk ˜ Jšœžœ˜'J˜ Jšœ˜Jšœžœ'˜4Jšœ žœ˜%Jšœžœ˜)Jšœžœ ˜Jšœžœ˜"Jšœžœ<˜GJšœžœ˜$Jšœžœ˜#Jšœ žœ˜Jšœžœ ˜Jšœžœžœ ˜*Jšœ žœ˜ Jšœžœ0˜