BTreeSimpleTestImpl.mesa
Copyright © 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
DIRECTORY
Basics,
BasicTime,
BTreeSimple,
Convert,
FS,
Random,
Real,
Rope;
BTreeSimpleTestImpl:
CEDAR
PROGRAM
IMPORTS Basics, BasicTime, BTreeSimple, Convert, FS, Random, Real
= {
ROPE: TYPE = Rope.ROPE;
Main procedures callable from interpreter
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;
};
Subsidiary procedures
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<initialFileSize THEN Destroy[];
IF file=FS.nullOpenFile
THEN {
file ← FS.Create[name: "///Temp/BTreeTest.tree", pages: initialFileSize];
initialize ← TRUE;
};
tree ← BTreeSimple.New[];
BTreeSimple.Open[tree: tree, file: file, filePagesPerPage: filePagesPerPage, cacheSize: cacheSize, initialize: initialize];
IF initialize
THEN {
entryTable ← NEW [EntryTable[maxEntries]];
entryTable.count ← 0;
FOR i: KeyIndex
IN [0..entryTable.maxEntries)
DO
entryTable.exists[i] ← FALSE;
ENDLOOP;
};
myTree ← tree;
};
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;
};
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 => {
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;
};
ENDCASE => {
otherwise, choose a random key and perform some operation
key ← Random.ChooseInt[markov, 0, entryTable.maxEntries-1];
IF key=keyOfInterest THEN SIGNAL EncounteredKeyOfInterest;
IF entryTable.exists[key]
THEN {
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 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] = {
keys from 100000 to 165535, so ASCII collating sequence is same as numeric
RETURN[Convert.RopeFromCard[100000+keyIndex]];
};