DIRECTORY Basics, BasicTime, BTreeSimple, Convert, FS, RandomCard, Real, Rope; BTreeSimpleTestImpl: CEDAR PROGRAM IMPORTS Basics, BasicTime, BTreeSimple, Convert, FS, RandomCard, Real = BEGIN ROPE: TYPE = Rope.ROPE; 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. BTreeSimpleTestImpl.mesa Last Edited by: Taft, January 13, 1984 11:15 am Main procedures callable from interpreter Subsidiary procedures Yucky arithmetic lifted from SystemImpl; to be put into the Nucleus some day. have to do triple divide t.high is 0, so let mesa do the work... ‌ت ج– "Cedar" styleکheadڑœ™Ibody™/code2ڑدk ک MکMک MڑœکMکMڑœکMکMڑœکMڑœک——ڑœ‌œ‌ک"Mڑ‌œ>کEMڑœ‌کMڑ‌œ‌œ‌œک—ڑœ)™)Mڑœ‌œ‌œکMڑœ‌œ‌œک%Mڑœ‌œ@کZMڑœ‌œ/ک>Mڑœ‌œک3Mڑœ ‌œ‌œکڑدnœ‌ œ‌œ‌œ‌œ‌œ‌œ‌œکXMڑ‌کMڑœ‌œ‌œ‌œ‌œ‌œک3Mڑœ‌œ‌œ‌œ‌œ‌œک2Mڑœ‌œ‌œک%Mڑ œ ‌œ‌œ‌œ‌œکDMڑ‌œ‌œ‌œک!ڑ‌œ‌کMڑœکMکMڑœ4ک4Mڑœ:ک:MڑœJکJMڑœ'‌œ‌œ)‌œکrMڑ‌œ‌œ‌œ‌œکZMڑœکMڑ‌œک—ڑ‌œ‌œ‌ک(Mڑœ>‌œ0کqMڑ‌œک—Mڑ‌œک—ڑ‍œ‌ œ‌œ‌œ‌œ‌œ‌œ‌œ"‌œکˆMڑ‌کMڑœ0‌œ‌œک>Mڑœ£ک£MکMڑœ1‌œک?Mڑœ<‌œ+کjMڑœ9‌œکGMڑ‌œک—Mڑœ‌œ‌œک*Mڑœ‌œ‌œک*ڑ‍œ‌ œکMڑ‌کڑ‌œ ‌œ‌ک0Mڑ‌œ‌œ‌œ‌œکCMڑ‌œک—Mڑ‌œک—ڑ ‍œ‌ œ‌œ‌œ‌کDMڑ‌کڑ‍ œ‌œ‌ œ>‌ کbMڑ‌کMڑœ)ک)Mڑ œ‌œ‌œ‌œ ‌œک2Mڑ‌œک—Mڑœ0ک0Mڑœ@ک@Mڑ œ‌œ‌œ‌œ‌œکTڑ‌œ ‌ œ‌œ‌ک;ڑ‌œ‌کMڑ‌کMڑœƒکƒMڑ ‌œ ‌œ‌œ‌œ‌œک?Mڑ‌œک—Mڑ‌œک—MڑœƒکƒMڑ‌œ ‌œ‌œ‌œک7Mڑ‌œک——ڑœ™Mڑœ$ک$MکMڑœ‌œ‌œدcکFڑœ‌œ‌œکMڑœکMڑ œ‌œ‌œ‌œ‌œک9—Mڑœ‌œکڑ‍œ‌ œ5‌œ‌œ‌œY‌œکهMڑ‌کM•StartOfExpansionٹ[volume: System.VolumeID _ [OPAQUE#[0, 0, 0, 0, 0]], initialSize: File.PageCount, type: File.Type _ [0], transaction: _ OPAQUE#0]ڑ‌œ‌œ‌œ&‌œک_ڑ‌œ‌کMڑ‌کMڑœIکIMڑœ ‌œکMڑ‌œک—MڑœکMڑœ{ک{ڑ‌œ‌کMڑ‌کMڑœ ‌œک*Mکڑ‌œ ‌œ‌ک0Mڑœ‌œکMڑ‌œک—Mڑ‌œک—MکMڑ‌œک—ڑ ‍œ‌œ‌œ‌ œ‌ک(Mڑ‌کڑ‌œ‌کMڑ‌کMڑœ‌œک+Mک Mڑœ"‌œک,MڑœکMڑ‌œک—Mڑœ ‌œک Mڑ‌œک—Mڑœ‌œ‌œ‌œک)Mڑœ‌œ‌œک(ڑ‍œ‌œ‌œ‌ œ‌œ)‌کeMڑ‌کڑ‌œ.‌ک8کMڑ‌œں§کMکMکMڑ‌œک—ڑ‌œک Mڑ‌œں<کBMک4Mڑ‌œ‌œ‌œک:ڑ‌œ‌کMڑ‌œں¢œک©ڑ‌œ‌ک#کMڑ‌کMکMڑ‌œ‌œ‌œںک:Mڑ‌œک—کMڑ‌کMکMڑ‌œ‌œ‌œںک:Mڑ‌œک—ڑ‌œک Mڑ‌کMکMکMڑ‌œک——Mڑ‌ک—ڑ‌œ‌œں{ک†ڑ‌œ‌ک#کMڑ‌کMکMڑ‌œ ‌œ‌œں#ک>Mڑ‌œک—ڑ‌œک Mڑ‌کMڑœکMکMڑ‌œک——Mڑ‌œک—Mڑ‌œک——Mڑ‌œک—ڑ‍ œ‌œ‌œ‌ œ‌œ ‌œ‌œ‌کMMڑœ‌œک—ڑ‍œ‌ œ‌œ ‌œک?Mڑ‌کMک,Mک#MکMڑœDکDڑ‌œ‌œ‌کڑ‌œ‌œ‌œ‌ک'Mڑ‌œ‌œ‌œںک:Mڑ‌œک——Mڑ‌œک—ڑ‍œ‌ œک&Mڑ‌کMک,Mڑœ ‌œ$ک9Mڑœ‌œ'کEڑ‌œ‌œ‌œ‌ک&MڑœکMڑ‌œک—Mڑœ?ک?ڑ‌œ‌ک"Mڑœ‌œ*کL—Mڑ‌œک—ڑ‍œ‌ œ‌œ ‌œک?Mڑ‌کMک,Mڑœ6ک6ڑ‌œ‌ک MڑœE‌œکM—Mڑ‌œک—ڑ‍œ‌ œ‌œ‌کTMڑœ‌œ*ںMک~——™Mڑ‍œ‌œ‌œ‌œ‌œ‌œکAMڑ‌œ ‌œ‌œک!Mڑ‌œ‌œ‌œک<ڑœ‌œ‌ œ‌œکڑ‌œ‌œ‌کMڑœ‌œک'Mڑœ‌œ‌œ‌œک2Mڑœ‌œ‌œ‌œک4Mڑ‌œک ——Mک&ڑ‌œ‌کMڑ‌کMک0ڑ‌œ‌کMڑ‌œ‌œ‌œ ک6Mڑœ™Mڑ‌œ‌œ‌œں"کOMکFMک#Mڑ‌œکMڑ‌œک—Mڑ‌œک—Mڑœ'™'Mڑ‌œ‌œکMڑ‌œک—Mڑ‌œک——…— ‏,è