DIRECTORY Basics, BasicTime, BTreeSimple, Convert, FS, Random, Real, Rope; BTreeSimpleTestImpl: CEDAR PROGRAM IMPORTS Basics, BasicTime, BTreeSimple, Convert, FS, Random, Real = { ROPE: TYPE = Rope.ROPE; useFixedSeed: BOOL _ TRUE; markov: Random.RandomStream _ NIL; validateEveryUpdate: BOOL _ 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: PROC [iterations: LONG CARDINAL] RETURNS [msPerOp: ARRAY Operation OF REAL] = { counts: ARRAY Operation OF LONG CARDINAL _ ALL [0]; times: ARRAY Operation OF LONG CARDINAL _ ALL [0]; entriesEnumerated: LONG CARDINAL _ 0; markov _ Random.Create[0, 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; }; VMStats: PROC RETURNS [refs: LONG CARDINAL, hitPercent: REAL, reads, writes: LONG CARDINAL, msPerReadWrite, avgChainLength: REAL] = { 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]]; }; MissingEntry: SIGNAL [k: KeyIndex] = CODE; EnumerateFailedToTerminate: SIGNAL = CODE; FindMissingEntries: PROC = { FOR k: KeyIndex IN [0..entryTable.maxEntries) DO IF entryTable.exists[k] AND ~Lookup[k] THEN SIGNAL MissingEntry[k]; ENDLOOP; }; EnumerateBackward: PROC [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 _ 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 { 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; }; 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 BOOL]; entryTable: REF EntryTable; Create: PROC [cacheSize: BTreeSimple.CacheSize _ 20, initialize: BOOL _ TRUE, initialFileSize: INT _ 20, filePagesPerPage: BTreeSimple.FilePagesPerPage _ 1, maxEntries: KeyIndex _ 10000] RETURNS [tree: BTreeSimple.Tree] = { IF initialize AND file#FS.nullOpenFile AND file.GetInfo[].pages CONTINUE]; file _ FS.nullOpenFile; }; myTree _ NIL; }; keyOfInterest: CARDINAL _ LAST[CARDINAL]; EncounteredKeyOfInterest: SIGNAL = CODE; PerformRandomOperation: PUBLIC SAFE PROC 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 SIGNAL EncounteredKeyOfInterest; IF entryTable.exists[key] THEN { SELECT Random.ChooseInt[markov, 0, 3] FROM 0 => { operation _ lookup; IF ~Lookup[key] THEN ERROR; -- failed to find existing key }; 1 => { operation _ delete; IF ~Delete[key] THEN ERROR; -- failed to find existing key }; ENDCASE => { operation _ replace; Insert[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[key] THEN ERROR; -- found key that it shouldn't have }; ENDCASE => { operation _ insert; Insert[key]; }; }; }; }; GetEntryCount: PUBLIC SAFE PROC RETURNS [count: LONG CARDINAL] = CHECKED { RETURN [entryTable.count]; }; Lookup: PROC [keyVal: KeyIndex] RETURNS [found: BOOL] = { 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; }; Insert: PROC [keyVal: KeyIndex] = { key: BTreeSimple.Key = KeyFromIndex[keyVal]; valueLength: CARDINAL = Random.ChooseInt[markov, 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; }; }; Delete: PROC [keyVal: KeyIndex] RETURNS [found: BOOL] = { key: BTreeSimple.Key = KeyFromIndex[keyVal]; found _ BTreeSimple.DeleteKey[tree: myTree, key: key]; IF found THEN { entryTable.count _ entryTable.count-1; entryTable.exists[keyVal] _ FALSE; }; }; KeyFromIndex: PROC [keyIndex: KeyIndex] RETURNS [key: BTreeSimple.Key] = { RETURN[Convert.RopeFromCard[100000+keyIndex]]; }; MultThenDiv: PROC [m1: LONG CARDINAL, m2: CARDINAL, dv: CARDINAL] RETURNS [result: LONG CARDINAL] = { 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 { t.highlong _ LongMult[mm1.highbits, m2] + t.mid; IF t.high # 0 THEN { 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; }; }; RETURN[t.lowlong/LONG[dv]]; }; }. <BTreeSimpleTestImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Taft, January 13, 1984 11:15 am Russ Atkinson (RRA) March 11, 1985 10:04:23 pm PST Main procedures callable from interpreter Subsidiary procedures 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. otherwise, choose a random key and perform some operation 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. keys from 100000 to 165535, so ASCII collating sequence is same as numeric Yucky arithmetic lifted from SystemImpl (in Nucleus some day?). have to do triple divide t.high is 0, so let mesa do the work... Κ – "Cedar" style˜codešœ™Kšœ Οmœ1™Kšœžœ˜3Kšœ žœžœ˜K˜šΟnœžœžœžœžœ žœ žœžœ˜UKš œžœ žœžœžœžœ˜3Kš œžœ žœžœžœžœ˜2Kšœžœžœ˜%Kšœžœžœžœ˜:Kšžœžœžœ˜!šžœž˜Kšœ˜K˜ Kšœ4˜4Kšœ:˜:KšœJ˜JKšœ'žœžœ)žœ˜rKšžœžœ žœžœ˜ZKšœ˜Kšžœ˜—šžœžœ ž˜(Kšœ>žœ0˜qKšžœ˜—Kšœ˜K˜—š œžœžœžœžœžœžœžœ"žœ˜…Kšœ0žœžœ˜>Kšœ£˜£K˜Kšœ1žœ ˜?Kšœ<žœ+˜jKšœ9žœ ˜GKšœ˜K˜—Kšœžœžœ˜*Kšœžœžœ˜*K˜š œžœ˜šžœ žœž˜0Kšžœžœ žœžœ˜CKšžœ˜—Kšœ˜K˜—š  œžœžœžœžœ˜>š  œžœžœ>ž œ˜_Kšœ)˜)Kš œžœžœžœ žœ˜2Kšœ˜—Kšœ0˜0Kšœ@˜@Kš œžœ žœžœžœ˜Tšžœ ž œžœž˜;šžœžœ˜Kšœƒ˜ƒKš žœ žœžœžœžœ˜?Kšœ˜—Kšžœ˜—Kšœƒ˜ƒKšžœ žœžœžœ˜7Kšœ˜——šœ™Kšœ$˜$K˜Kšœ žœžœΟc˜Fšœ žœžœ˜Kšœ˜Kš œžœžœžœžœ˜6—Kšœ žœ ˜K˜š  œžœ5žœžœžœYžœ˜ίK•StartOfExpansionŠ[volume: System.VolumeID _ [OPAQUE#[0, 0, 0, 0, 0]], initialSize: File.PageCount, type: File.Type _ [0], transaction:  _ OPAQUE#0]šžœ žœžœ&žœ ˜_šžœžœ˜KšœI˜IKšœ žœ˜Kšœ˜—Kšœ˜Kšœ{˜{šžœ žœ˜Kšœ žœ˜*K˜šžœ žœž˜0Kšœžœ˜Kšžœ˜—Kšœ˜—K˜Kšœ˜K˜—š  œžœžœžœžœ˜%šžœžœ˜Kšœ žœ˜+K˜ Kšœ"žœ˜,Kšœ˜Kšœ˜—Kšœ žœ˜ Kšœ˜K˜—Kšœžœžœžœ˜)Kšœžœžœ˜(K˜š  œžœžœžœžœ)žœ˜bšžœ5ž˜?šœ˜Kšœ€™€K˜K˜Kšœ˜—šžœ˜ Kšœ9™9Kšœ;˜;Kšžœžœžœ˜:šžœžœ˜ Kšœ ™ šžœ ž˜*šœ˜K˜Kšžœžœžœ‘˜:Kšœ˜—šœ˜K˜Kšžœžœžœ‘˜:Kšœ˜—šžœ˜ K˜K˜ Kšœ˜——Kšœ˜—šžœ‘{˜‚šžœ ž˜*šœ˜K˜Kšžœ žœžœ‘#˜>Kšœ˜—šžœ˜ Kšœ˜K˜ Kšœ˜——Kšœ˜—Kšœ˜——Kšœ˜K˜—š  œžœžœžœžœ žœžœžœ˜JKšžœ˜Kšœ˜K˜—š œžœžœ žœ˜9K˜,K˜#K˜KšœD˜Dšžœžœž˜šžœžœžœž˜'Kšžœžœžœ‘˜:Kšžœ˜——Kšœ˜K˜—š œžœ˜#K˜,Kšœ žœ+˜@Kšœžœ'˜Ešžœžœžœž˜&Kšœ˜Kšžœ˜—Kšœ?˜?šžœžœ˜$Kšœžœ˜!Kšœ&˜&Kšœ˜—Kšœ˜K˜—š œžœžœ žœ˜9K˜,Kšœ6˜6šžœžœ˜Kšœ&˜&Kšœžœ˜"Kšœ˜—Kšœ˜K˜—š  œžœžœ˜JKšœJ™JKšžœ(˜.Kšœ˜——™?š  œžœžœžœžœžœžœ žœžœ˜eKšžœžœ˜6šœžœž œžœ˜šžœžœž˜Kšœžœ˜'Kšœžœžœžœ˜2Kšœžœ žœžœ˜4Kšžœ˜ ——K˜&šžœžœ˜K˜0šžœ ž˜Kšœžœžœ ˜2Kšœ™Kšžœžœžœ‘"˜OK˜FK˜#Kšžœ˜Kšœ˜—Kšœ˜—Kšœ'™'Kšžœ žœ˜Kšœ˜K˜—Kšœ˜——…—n,7