BTreeTestImpl.mesa
Last Edited by: Taft, June 22, 1983 1:10 pm
DIRECTORY
BTree,
BTreeTestOps,
BTreeVM,
File,
PrincOps,
PrincOpsUtils,
ProcessorFace,
RandomCard,
Real;
BTreeTestImpl: PROGRAM
IMPORTS BTree, BTreeVM, File, RandomCard, PrincOpsUtils, ProcessorFace, Real
EXPORTS BTreeTestOps
= BEGIN OPEN BTreeTestOps;
Representation primitives
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 [BTree.Comparison] =
BEGIN
e: CARDINAL = entry.keys[0];
RETURN [SELECT NARROW[key, Key]^ FROM
<e => less,
=e => equal,
ENDCASE => greater];
END;
CompareEntries: PROCEDURE [entry1, entry2: Entry] RETURNS [BTree.Comparison] =
BEGIN
e1: CARDINAL = entry1.keys[0];
e2: CARDINAL = entry2.keys[0];
RETURN [SELECT e1 FROM
<e2 => less,
=e2 => equal,
ENDCASE => greater];
END;
EntrySize: PROCEDURE [entry: Entry] RETURNS [words: BTree.EntSize] =
{ 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]];
PrincOpsUtils.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[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 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: LONG CARDINAL ← PrincOpsUtils.GetClockPulses[];
[operation: operation, key: k] ← PerformRandomOperation[];
times[operation] ← times[operation] + (PrincOpsUtils.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, 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]];
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] =
BEGIN
EntryProc: PROCEDURE [entry: Entry] =
BEGIN
found ← entry#NIL;
IF found THEN foundKey ← entry.keys[0];
END;
found: BOOLEAN;
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
BEGIN
key^ ← foundKey;
myTree.ReadEntry[key: key, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk];
IF ~found OR foundKey#k THEN SIGNAL MissingEntry[k];
END;
ENDLOOP;
key^ ← foundKey;
myTree.ReadEntry[key: key, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk];
IF found THEN SIGNAL EnumerateFailedToTerminate;
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.Handle ← NIL;
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#NIL AND file.Info[].size<initialFileSize THEN
{ file.Delete[]; file ← NIL };
IF file=NIL THEN
BEGIN
file ← File.Create[volume: File.SystemVolume[], size: initialFileSize];
initialize ← TRUE;
END;
storage ← BTreeVM.Open[file: file, filePagesPerPage: filePagesPerPage, cacheSize: cacheSize];
tree ← BTree.Open[repPrim: myRepPrim, storage: storage, storPrim: [BTreeVM.ReferencePage, BTreeVM.ReleasePage], pageSize: filePagesPerPage*File.wordsPerPage, minEntrySize: 2, initialize: initialize];
IF initialize THEN
BEGIN
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;
END;
myTree ← tree;
myStorage ← storage;
END;
Destroy: PUBLIC SAFE PROCEDURE = TRUSTED
BEGIN
IF file#NIL THEN { file.Delete[]; file ← 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.
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
ProduceEntry: PROCEDURE [bEntry: BTree.Entry] =
{ PrincOpsUtils.LongCOPY[to: bEntry, from: entry, nwords: words] };
copies: CARDINAL = RandomCard.Choose[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 };
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;
Yucky arithmetic lifted from SystemImpl; to be put into the Nucleus some day.
PulsesToMicroseconds: PUBLIC SAFE PROC [p: LONG CARDINAL] RETURNS [LONG CARDINAL] = TRUSTED
BEGIN -- (p*msPerHp)/(100units/hundred)
RETURN[MultThenDiv[p, ProcessorFace.microsecondsPerHundredPulses, 100]]
END;
MicrosecondsToPulses: PUBLIC SAFE PROC [m: LONG CARDINAL] RETURNS [LONG CARDINAL] = TRUSTED
BEGIN -- (microseconds*100units/hundred)/microsecondsPerHundredPulses
RETURN[MultThenDiv[m, 100, ProcessorFace.microsecondsPerHundredPulses]]
END;
MultThenDiv: PROC [m1: LONG CARDINAL, m2: CARDINAL, dv: CARDINAL]
RETURNS [result: LONG CARDINAL] =
BEGIN OPEN PrincOpsUtils, mm1: LOOPHOLE[m1, num PrincOps.LongNumber];
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, num PrincOps.LongNumber];
have to do triple divide
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;
t.high is 0, so let mesa do the work...
RETURN[t.lowlong/LONG[dv]];
END;
END.