-- BTreeTestImpl.mesa DIRECTORY BTree, BTreeTestOps, BTreeVM, Environment, File, FileTypes, Inline, RandomCard, Real, System, Volume; BTreeTestImpl: PROGRAM IMPORTS BTree, BTreeVM, File, Inline, RandomCard, Real, System, Volume 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 [Environment.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 [Environment.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: [1..LAST[BTree.PageSize]]] = { 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]]; Inline.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; -- Main procedures callable from interpreter useFixedSeed: BOOLEAN _ TRUE; validateEveryUpdate: BOOLEAN _ FALSE; millisecondsPerPulse: REAL = 1000.0 / Real.Float[System.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 System.Pulses _ 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: System.Pulses _ System.GetClockPulses[]; [operation: operation, key: k] _ PerformRandomOperation[]; times[operation] _ [times[operation] + (System.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: LONG CARDINAL; cumReadWriteTime: System.Pulses; [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; FindMissingEntries: PROCEDURE = BEGIN FOR k: KeyIndex IN [0..entryTable.maxEntries) DO IF entryTable.exists[k] AND ~Lookup[k] THEN SIGNAL MissingEntry[k]; ENDLOOP; END; -- Type "conversion" operations, callable from debugger ConcreteKey: PROCEDURE [key: BTree.Key] RETURNS [Key] = { RETURN [NARROW[key]] }; ConcreteEntry: PROCEDURE [entry: BTree.Entry] RETURNS [Entry] = { RETURN [entry] }; -- Subsidiary procedures (some exported to BTreeTestOps so the BTreeTool can call them) file: File.Capability _ File.nullCapability; 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#File.nullCapability AND File.GetSize[file] 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 entSize: EntSize _ RandomCard.Choose[1, maxEntSize]; entry.copies _ entSize; FOR i: CARDINAL IN [0..entSize) DO entry.keys[i] _ keyVal; ENDLOOP; key^ _ keyVal; myTree.UpdateEntry[key: key, entry: entry]; 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; END. 8-- Last Edited by: Taft, March 26, 1983 10:42 am Κ 3– "Cedar" style˜IunitšΟc˜J™0šΟk ˜ Icodešœ˜L˜ Lšœ˜L˜ Lšœ˜Lšœ ˜ L˜L˜ L˜L˜Lšœ˜—šœž˜Lšžœ?˜FLšžœ ˜Lšœžœžœ˜šœ-˜-Lšœ˜Lšœ˜Lšœ˜Lšœ!˜!Lšœ(˜(—Kšœž˜Kšœžœžœ ˜Kšœžœžœ ˜*šœ ž œ˜Lšœ˜/Lšœžœ žœ ˜-—Kšœ žœžœ-˜Ešœ ž œ˜Lšœ˜Lš œžœžœžœžœ˜9—šΟnœž œ žœ˜TLšž˜Lšœžœ˜šžœžœžœ ž˜%L˜ L˜ Lšžœ ˜—Lšžœ˜—šŸœž œžœ˜TLšž˜Lšœžœ˜Lšœžœ˜šžœžœž˜L˜ L˜ Lšžœ ˜—Lšžœ˜—šŸ œž œžœ žœ˜PLšœžœžœ˜-—šŸœž œžœ˜JLšœžœžœ ˜—šŸœž œžœ˜GLšž˜Lšœ žœ˜(Lšœžœžœ˜\Lšžœ˜—K˜Kšœ˜Kšœ žœžœ˜K˜K˜ Kšœžœ˜GKšœ žœ ˜Kš,˜,Kšœžœžœ˜Kšœžœžœ˜%Kšœžœ=˜WšŸœž œžœžœžœ žœ žœžœ˜XLšž˜Lš œžœ žœžœžœžœ˜3Lšœžœ žœžœ˜4Lšœžœžœ˜%Lš œ žœžœžœžœ˜DLšžœžœžœ˜!šžœž˜Lšœ˜L˜ L˜.Lšœ:˜:L˜ILšœ'žœžœžœ˜gLšžœžœ žœžœ˜OLšœ˜Lšžœ˜—šžœžœ ž˜(Lšœ>žœ0˜qLšžœ˜—Lšžœ˜—šŸœž œžœžœžœžœžœžœ"žœ˜ˆLšž˜Lšœžœžœ˜,Lšœ ˜ Lšœ˜L˜Lšœ1žœ ˜?Lšœ<žœ+˜jLšœ9žœ ˜GLšžœ˜—Kšœžœžœ˜*šŸœž œ˜Lšž˜šžœ žœž˜0Lšžœžœ žœžœ˜CLšžœ˜—Lšžœ˜—Kš7˜7šŸ œž œžœ˜7Lšœžœžœ ˜—šŸ œž œžœ ˜?Lšœžœ ˜—KšW˜WKšœ,˜,šŸœžœžœž œ1žœžœvžœ/ž˜Lšž˜•StartOfExpansionŠ[volume: System.VolumeID _ [OPAQUE#[0, 0, 0, 0, 0]], initialSize: File.PageCount, type: File.Type _ [0], transaction:  _ OPAQUE#0]šžœ žœžœ$ž˜VLšœ2˜2—šžœž˜ Lšž˜Lšœh˜hLšœ žœ˜Lšžœ˜—Lšœ]˜]LšœΞ˜Ξšžœ ž˜Lšž˜Lšœ žœ˜&Lšœžœ ˜Lšœ žœ˜*L˜šžœ žœž˜0Lšœžœ˜Lšžœ˜—Lšžœ˜—L˜L˜Lšžœ˜—š Ÿœžœžœž œž˜(Lšž˜Lšžœžœ3˜SLšžœ˜—Kšœžœžœžœ˜)Kšœž œ˜(š Ÿœžœžœž œžœ)ž˜eLšž˜šžœ.ž˜8˜Lšžœ§˜­L˜L˜Lšžœ˜—šžœ˜ Lšžœ<˜BL˜4Lšžœžœžœ˜:šžœž˜Lšžœ’œ˜©šžœž˜#˜Lšž˜L˜Lšžœžœžœ˜:Lšžœ˜—˜Lšž˜L˜Lšžœžœžœ˜:Lšžœ˜—šžœ˜ Lšž˜L˜L˜ Lšžœ˜——Lšž˜—šžœžœ{˜†šžœž˜#˜Lšž˜L˜Lšžœ žœžœ#˜>Lšžœ˜—šžœ˜ Lšž˜Lšœ˜L˜ Lšžœ˜——Lšžœ˜—Lšžœ˜——Lšžœ˜—šŸ œžœžœž œžœ žœžœž˜MLšœžœ˜—šŸœž œžœ žœ˜?Lšž˜šŸ œž œ˜%Lšž˜Lšœžœ˜šžœž˜ šžœžœžœž˜'Lšžœžœžœ˜?Lšžœ˜——Lšžœ˜—L˜Lšœ,˜,Lšžœ˜—šŸœž œ˜&Lšž˜L˜4L˜šžœžœžœž˜"Lšœ˜Lšžœ˜—L˜Lšœ+˜+šžœž˜"Lšœžœ*˜L—Lšžœ˜—šŸœž œžœ žœ˜?Lšž˜L˜Lšœ#˜#šžœž˜ LšœEžœ˜M—Lšžœ˜—Kšžœ˜——…—θ*S