DIRECTORY
Basics,
BasicTime,
BTree,
BTreeTestOps,
BTreeVM,
FS,
FSBackdoor,
PrincOps,
PrincOpsUtils,
Random,
Real,
Rope;
BTreeTestImpl: PROGRAM
IMPORTS Basics, BasicTime, BTree, BTreeVM, FS, FSBackdoor, Random, PrincOpsUtils, Real
EXPORTS BTreeTestOps
= { OPEN BTreeTestOps;
ROPE: TYPE = Rope.ROPE;
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 BOOL];
Compare: PROC [key: BTree.Key, entry: Entry] RETURNS [BTree.Comparison] = {
e: CARDINAL = entry.keys[0];
RETURN [SELECT NARROW[key, Key]^ FROM
<e => less,
=e => equal,
ENDCASE => greater];
};
CompareEntries: PROC [entry1, entry2: Entry] RETURNS [BTree.Comparison] = {
e1: CARDINAL = entry1.keys[0];
e2: CARDINAL = entry2.keys[0];
RETURN [SELECT e1 FROM
<e2 => less,
=e2 => equal,
ENDCASE => greater];
};
EntrySize: PROC [entry: Entry] RETURNS [words: BTree.EntSize] = {
RETURN [SIZE[EntryObject[entry.copies]]] };
EntryFromRecord: PROC [record: BTree.Record] RETURNS [entry: Entry] = {
RETURN [LOOPHOLE[record]] };
NewRecordFromEntry: PROC [entry: Entry] RETURNS [record: Record] = {
record _ NEW[EntryObject[entry.copies]];
PrincOpsUtils.LongCopy[to: LOOPHOLE[record], from: entry, nwords: SIZE[EntryObject[entry.copies]]];
};
myTree: BTree.Tree;
myStorage: BTreeVM.Handle;
key: Key = NEW[CARDINAL];
record: Record;
entry: Entry;
maxEntSize: EntSize _ FS.WordsForPages[1]/8; -- 1/8 minimum-size page
entryTable: REF EntryTable;
useFixedSeed: BOOL _ TRUE;
markov: Random.RandomStream;
validateEveryUpdate: BOOL _ FALSE;
millisecondsPerPulse: REAL = 1000.0 / Real.Float[BasicTime.MicrosecondsToPulses[1000000]];
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 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;
};
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] _ 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]];
};
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] = {
EntryProc: PROC [entry: Entry] = {
found _ entry#NIL;
IF found THEN foundKey _ entry.keys[0];
};
found: BOOL;
foundKey: KeyIndex _ entryTable.maxEntries;
pathStk: BTree.PathStk _ IF usePathStk THEN BTree.NewPathStk[] ELSE NIL;
FOR k: KeyIndex DECREASING IN [0..entryTable.maxEntries) DO
IF entryTable.exists[k] THEN {
key^ _ foundKey;
myTree.ReadEntry[key: key, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk];
IF ~found OR foundKey#k THEN SIGNAL MissingEntry[k];
};
ENDLOOP;
key^ _ foundKey;
myTree.ReadEntry[key: key, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk];
IF found THEN SIGNAL EnumerateFailedToTerminate;
};
ConcreteKey: PROC [key: BTree.Key] RETURNS [Key] = {
RETURN [NARROW[key]] };
ConcreteEntry: PROC [entry: BTree.Entry] RETURNS [Entry] = {
RETURN [entry] };
file: FS.OpenFile _ FS.nullOpenFile;
Create: PUBLIC SAFE PROC [cacheSize: BTreeVM.CacheSize _ 20, initialize: BOOL _ TRUE, initialFileSize: INT _ 20, filePagesPerPage: BTreeVM.FilePagesPerPage _ 1, maxEntries: KeyIndex _ 10000] RETURNS [tree: BTree.Tree, storage: BTreeVM.Handle] = TRUSTED {
IF initialize AND file#FS.nullOpenFile AND file.GetInfo[].pages<initialFileSize THEN Destroy[];
IF file=FS.nullOpenFile THEN {
file _ FS.Create[name: "///Temp/BTreeTest.tree", pages: initialFileSize];
initialize _ TRUE;
};
storage _ BTreeVM.Open[file: FSBackdoor.GetFileHandle[file], filePagesPerPage: filePagesPerPage, cacheSize: cacheSize];
tree _ BTree.New[repPrim: myRepPrim, storPrim: [BTreeVM.ReferencePage, BTreeVM.ReleasePage], minEntrySize: 2];
tree.Open[storage: storage, pageSize: FS.WordsForPages[filePagesPerPage], initialize: initialize];
IF initialize THEN {
record _ NEW[EntryObject[maxEntSize]];
entry _ LOOPHOLE[record];
entryTable _ NEW [EntryTable[maxEntries]];
entryTable.count _ 0;
FOR i: KeyIndex IN [0..entryTable.maxEntries) DO
entryTable.exists[i] _ FALSE;
ENDLOOP;
};
myTree _ tree;
myStorage _ storage;
};
Destroy: PUBLIC SAFE PROC = TRUSTED {
IF file#FS.nullOpenFile THEN {
fullFName: ROPE = file.GetName[].fullFName;
file.Close[];
FS.Delete[fullFName ! FS.Error => CONTINUE];
file _ FS.nullOpenFile;
};
myTree _ NIL;
myStorage _ 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 => {
myTree.Validate[];
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 {
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] = {
EntryProc: PROC [entry: Entry] = {
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;
};
key^ _ keyVal;
myTree.ReadEntry[key: key, Proc: EntryProc];
};
Insert: PROC [keyVal: KeyIndex] = {
ProduceEntry: PROC [bEntry: BTree.Entry] = {
PrincOpsUtils.LongCopy[to: bEntry, from: entry, nwords: words];
};
copies: CARDINAL = Random.ChooseInt[markov, 1, maxEntSize];
words: EntSize = SIZE[EntryObject[copies]];
entry.copies _ copies;
FOR i: CARDINAL IN [0..copies) DO
entry.keys[i] _ keyVal;
ENDLOOP;
key^ _ keyVal;
myTree.UpdateEntry[key: key, words: words, Proc: ProduceEntry];
IF ~entryTable.exists[keyVal] THEN {
entryTable.exists[keyVal] _ TRUE;
entryTable.count _ entryTable.count+1;
};
};
Delete: PROC [keyVal: KeyIndex] RETURNS [found: BOOL] = {
key^ _ keyVal;
found _ myTree.DeleteKey[key: key];
IF found THEN {
entryTable.count _ entryTable.count-1;
entryTable.exists[keyVal] _ FALSE;
};
};
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]];
};
}.
²BTreeTestImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Taft, December 10, 1983 2:52 pm
Russ Atkinson (RRA) March 11, 1985 10:41:00 pm PST
Representation primitives
Main procedures callable from interpreter
Type "conversion" operations, callable from debugger
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.
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.
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˜
headš
œ™Icodešœ
Οm
œ1™<L™L™2
code2š
Οk	˜	M˜M˜
Mš
œ˜M˜
Mš
œ˜Mšžœ
˜Mš
œ˜M˜	M˜M˜Mš
œ˜Mš
œ˜——šœž˜Mšžœ$žœ)˜VMšžœ
˜Mšœžœ˜Mšžœžœžœ
˜—™š
œ-˜-Mš
œ˜Mš
œ˜Mš
œ˜Mš
œ!˜!Mš
œ(˜(—Mšœžœžœ
žœ
˜Mšœžœžœ
˜Mš	œžœžœ
žœ
žœ
˜*šœ
žœžœ˜MšœΟc˜/Mšœžœ
žœ	žœ˜-—Mšœ	žœžœ-˜Ešœžœžœ˜Mš
œ˜Mš	œžœ
žœžœ
žœ˜6—šΟnœžœ žœ˜KMšœžœ˜šžœžœ
žœž˜%M˜M˜Mšžœ
˜—Mš
œ˜—š œžœžœ˜KMšœžœ˜Mšœžœ˜šžœžœž˜M˜M˜
Mšžœ
˜—Mš
œ˜—š 	œžœžœ˜AMšžœžœ˜+—š œžœžœ˜GMšžœžœ˜—š œžœžœ˜DMšœ	žœ˜(Mšœžœžœ˜cMš
œ˜—M˜Mš
œ˜Mšœžœ
žœ˜M˜M˜
MšœžœŸ˜EMšœžœ˜—š
œ)™)Mšœžœžœ
˜M˜Mšœžœžœ
˜"Mšœžœ@˜Zš œžœžœ
žœžœžœžœ
žœ˜UMšœžœžœ
žœ
žœžœ˜3Mšœžœžœ
žœ
žœžœ˜2Mšœžœ
žœ˜%Mšœžœžœžœ˜:Mšžœžœ
žœ˜!šžœž˜Mš
œ˜M˜Mš
œ4˜4Mš
œ:˜:Mš
œJ˜JMšœ'žœžœžœ˜gMšžœžœžœžœ˜OMš
œ˜Mšžœ
˜—šžœžœž˜(Mšœ>žœ0˜qMšžœ
˜—Mš
œ˜—š œžœ
žœžœ
žœžœžœ
žœ"žœ˜…
Mšœ0žœ
žœ
˜>Mš
œ
˜
M˜Mšœ1žœ˜?Mšœ<žœ+˜jMšœ9žœ˜GMš
œ˜—Mšœžœžœ
˜*Mšœžœžœ
˜*š œžœ˜šžœ
žœž˜0Mšžœžœžœ
žœ˜CMšžœ
˜—Mš
œ˜—š œžœžœžœ˜6š 	œžœ˜"Mšœžœ
˜Mšžœžœ˜'Mš
œ˜—Mšœžœ
˜Mš
œ+˜+Mš	œžœžœžœ
žœ
˜Hšžœ
ž
œ
žœž˜;šžœžœ˜Mš
œ˜Mš
œk˜kMšžœžœžœ
žœ˜4Mš
œ˜—Mšžœ
˜—Mš
œ˜Mš
œk˜kMšžœžœ
žœ˜0Mš
œ˜——š
œ4™4š œžœžœ
˜4Mšžœžœ	˜—š 
œžœžœ˜<Mšžœ˜——š
œ™Mšœžœžœ˜$š œžœ
žœ
žœ1žœžœžœUžœ/žœ˜ώ
M•StartOfExpansionŠ
[volume: 
System.VolumeID _ [OPAQUE#[0, 0, 0, 0, 0]], initialSize: 
File.PageCount, type: 
File.Type _ [0], transaction: 
 _ OPAQUE#0]š
žœžœžœžœ&žœ˜_šžœžœžœ˜Mšœžœ@˜IMšœ
žœ
˜Mš
œ˜—Mš
œw˜wMš
œn˜nMšœ&žœ:˜bšžœžœ˜Mšœ	žœ˜&Mšœžœ	˜Mšœ
žœ˜*M˜šžœ
žœž˜0Mšœžœ
˜Mšžœ
˜—Mš
œ˜—M˜M˜Mš
œ˜—š
 œžœ
žœ
žœžœ˜%šžœžœžœ˜Mšœžœ˜+M˜
Mšžœžœ
žœ˜,Mšœžœ˜Mš
œ˜—Mšœ	žœ
˜
Mšœžœ
˜Mš
œ˜—Mšœžœžœ
žœ˜)Mšœžœžœ
˜(š œžœ
žœ
žœ
žœ)žœ˜bšžœ5ž˜?š
œ˜Mš
œ€
™€
M˜M˜Mš
œ˜—šžœ˜Mš
œ9™9Mš
œ;˜;Mšžœžœ
žœ˜:šžœžœ˜ Mš
œ 
™ 
šžœ ž˜*š
œ˜M˜Mšžœžœ
žœŸ˜:Mš
œ˜—š
œ˜M˜Mšžœžœ
žœŸ˜:Mš
œ˜—šžœ˜M˜M˜Mš
œ˜——Mš
œ
˜
—šžœ˜Mš
œx™xšžœ ž˜*š
œ˜M˜Mšžœ
žœ
žœŸ#˜>Mš
œ˜—šžœ˜Mš
œ˜M˜Mš
œ˜——Mš
œ˜—Mš
œ˜——Mš
œ˜—š 
œžœ
žœ
žœ
žœ	žœ
žœžœ˜JMšžœ˜Mš
œ˜—š œžœžœ	žœ˜9š 	œžœ˜"Mšœžœ
˜šžœž˜
šžœžœ
žœž˜'Mšžœžœ
žœŸ˜?Mšžœ
˜——Mš
œ˜—M˜Mš
œ,˜,Mš
œ˜—š œžœ˜#š œžœ˜,Mš
œ?˜?Mš
œ˜—Mšœžœ+˜;Mšœžœ˜+Mš
œ˜šžœžœ
žœ
ž˜!Mš
œ˜Mšžœ
˜—M˜Mš
œ?˜?šžœžœ˜$Mšœžœ
˜!Mš
œ&˜&Mš
œ˜—Mš
œ˜—š œžœžœ	žœ˜9M˜Mš
œ#˜#šžœžœ˜Mš
œ&˜&Mšœžœ
˜"Mš
œ˜—Mš
œ˜——™>š œžœžœ
žœžœžœžœ
žœ
žœ˜eMšžœžœ˜6šœžœ
ž	œ
žœ˜šžœ
žœž˜Mšœžœ˜'Mšœžœ
žœžœ˜2Mšœžœžœ
žœ˜4Mšžœ˜	——M˜&šžœž˜Mš
œ
˜
M˜0šžœž˜Mšœžœžœ ˜2Mš
œ™MšžœžœžœŸ"˜OM˜FM˜#Mšžœ
˜Mš
œ˜—Mš
œ˜—Mš
œ'™'Mšžœžœ˜Mš
œ˜—Mš
œ˜——…—#P3Ά