

<<BackupBTreeTest.mesa>>

DIRECTORY
AlpineEnvironment,
AlpInstance,
AlpTransaction,
AlpDirectory,
BackupBTree,
Convert USING[RopeFromCard],
IO,
Process,
ViewerIO USING[CreateViewerStreams],
ViewRec,
Rope;

BackupBTreeTest: PROGRAM IMPORTS AlpTransaction, AlpDirectory, AlpInstance, BackupBTree, Convert, IO, Process, ViewerIO, ViewRec = 
BEGIN

NotImplemented: ERROR = CODE;
ROPE: TYPE = Rope.ROPE;

ActionProcedure: TYPE = PROCEDURE RETURNS[BOOLEAN];   
Action: TYPE = REF ActionBody;
ActionBody: TYPE = RECORD[name: Rope.ROPE, proc: ActionProcedure, count: LONG CARDINAL];
MaxNItemsInPhase: CARDINAL = 100;
MaxTotalWeightOfPhase: LONG CARDINAL = 20000;
Phase: TYPE = REF PhaseBody;
PhaseBody: TYPE = RECORD[nItems: CARDINAL, totalWeight: CARDINAL, items: SEQUENCE max: CARDINAL OF PhaseCase];
PhaseCase: TYPE = RECORD[act: Action, weight: CARDINAL];

<<control>>

Control: PROCEDURE =
BEGIN
InsertARandomItemAction: Action _ DefineAction["InsertARandomItem", InsertARandomItem];
ChangeARandomEntryAction: Action _ DefineAction["ChangeARandomEntry", ChangeARandomEntry];
DeleteARandomEntryAction: Action _ DefineAction["DeleteARandomEntry", DeleteARandomEntry];
DeleteARandomOldEntryAction: Action _ DefineAction["DeleteARandomOldEntry", DeleteARandomOldEntry];
DeleteARandomNonEntryAction: Action _ DefineAction["DeleteARandomNonEntry", DeleteARandomNonEntry];
CheckARandomOldEntryAction: Action _ DefineAction["CheckARandomOldEntry", CheckARandomOldEntry];
CheckARandomNonEntryAction: Action _ DefineAction["CheckARandomNonEntry", CheckARandomNonEntry];

growing: Phase _ DefinePhase[LIST[
[InsertARandomItemAction, 200],
[ChangeARandomEntryAction, 100],
[DeleteARandomEntryAction, 100],
[DeleteARandomOldEntryAction, 100],
[DeleteARandomNonEntryAction, 100],
[CheckARandomOldEntryAction, 100],
[CheckARandomNonEntryAction, 100]
]];
shrinking: Phase _ DefinePhase[LIST[
[InsertARandomItemAction, 200],
[ChangeARandomEntryAction, 100],
[DeleteARandomEntryAction, 400],
[DeleteARandomOldEntryAction, 400],
[DeleteARandomNonEntryAction, 100],
[CheckARandomOldEntryAction, 100],
[CheckARandomNonEntryAction, 100]
]];

currentPhase: Phase _ growing;
trans: AlpTransaction.Handle _ AlpTransaction.Create[AlpInstance.Create["sea-wolf.alpine", NIL, ALL[0]]];
btreeFile: AlpineEnvironment.UniversalFile _ AlpDirectory.Lookup["/sea-wolf.alpine/chauser.pa/backup.btree"].file;

BackupBTree.OpenForNormalOperation[trans, btreeFile, TRUE];


InitModel[];

FOR i: CARDINAL IN [0..20000] WHILE NOT tick.stop DO
PerformOneRandomAct[currentPhase];
IF i MOD 40 = 0 THEN [] _ BackupBTree.Commit[];
IF i MOD 1000 = 999 THEN Process.Pause[Process.SecondsToTicks[30]];
WHILE tick.pause DO Process.Pause[100] ENDLOOP;
ENDLOOP;

currentPhase _ shrinking;


WHILE NOT tick.stop DO
PerformOneRandomAct[currentPhase];
WHILE tick.pause DO Process.Pause[100] ENDLOOP;
IF tick.tick MOD 40 = 0 THEN BackupBTree.Commit[];
IF tick.tick MOD 1000 = 999 THEN Process.Pause[Process.SecondsToTicks[30]];
ENDLOOP;
[] _ AlpTransaction.Finish[trans, abort];


END;

<<model state>>

MaxNItems: CARDINAL = 1000;
MaxOldItems: CARDINAL = 100;

nItems: CARDINAL _ 0;
items: REF ItemArray _ NEW[ItemArray];
ItemArray: TYPE = ARRAY [0..MaxNItems) OF Item;
Item: TYPE = RECORD[k: ShortKey, v: ROPE];
ShortKey: TYPE = RECORD[ wordNum: [0..9), kval: CARDINAL ];
LongKey: TYPE = ARRAY [0..9) OF CARDINAL;

nOldItems: CARDINAL _ 0;
oldItems: REF OldItemArray _ NEW[OldItemArray];
OldItemArray: TYPE = ARRAY[0..MaxOldItems) OF Item;

ActionCodes: TYPE = {modify, delete};
interestingKey: CARDINAL _ 56920;

<<random actions>>

InsertARandomItem: PROCEDURE RETURNS[BOOLEAN] =
BEGIN
item: Item;
IF nItems = MaxNItems THEN RETURN[FALSE];
item.k _ PickARandomNonEntryKey[];
item.v _ PickARandomValue[];
InsertInModel[item];
NoteAction[item.k, modify];
Change[item];
RETURN[TRUE];
END;

ChangeARandomEntry: PROCEDURE RETURNS[BOOLEAN] =
BEGIN
item: Item;
IF nItems = 0 THEN RETURN[FALSE];
item.k _ PickARandomEntryKey[];
item.v _ PickARandomNewValueFor[item.k];
InsertInModel[item];
NoteAction[item.k, modify];
Change[item];
RETURN[TRUE];
END;

DeleteARandomEntry: PROCEDURE RETURNS[BOOLEAN] =
BEGIN
k: ShortKey;
IF nItems = 0 THEN RETURN[FALSE];
k _ PickARandomEntryKey[];
DeleteFromModel[k];
NoteAction[k, delete];
Delete[k];
RETURN[TRUE];
END;

DeleteARandomOldEntry: PROCEDURE RETURNS[BOOLEAN] =
BEGIN
k: ShortKey;
IF nOldItems = 0 THEN RETURN[FALSE];
k _ PickARandomOldKey[];
<<no need to delete it from model, and doing so would add it to the old list>>
NoteAction[k, delete];
Delete[k];
RETURN[TRUE];
END;

DeleteARandomNonEntry: PROCEDURE RETURNS[BOOLEAN] =
BEGIN
k: ShortKey _ PickARandomNonEntryKey[];
NoteAction[k, delete];
Delete[k];
RETURN[TRUE];
END;

CheckARandomOldEntry: PROCEDURE RETURNS[BOOLEAN] =
BEGIN
k: ShortKey;
v: ROPE;
IF nOldItems = 0 THEN RETURN[FALSE];
k _ PickARandomOldKey[];
v _ LookUpInModel[k];
IF LookUp[k] # v THEN ERROR;
RETURN[TRUE];
END;

CheckARandomNonEntry: PROCEDURE RETURNS[BOOLEAN] =
BEGIN
k: ShortKey _ PickARandomNonEntryKey[];
IF LookUp[k] # NIL THEN ERROR;
RETURN[TRUE];
END;

    LookUp: PROC [k: ShortKey] RETURNS [v: ROPE] ~ {
        longKey: LongKey _ ALL[0];
        longKey[k.wordNum] _ k.kval;
        v _ BackupBTree.GetFileInfo[LOOPHOLE[longKey]].name;
        };

    Delete: PROC [k: ShortKey] ~ {
        longKey: LongKey _ ALL[0];
        longKey[k.wordNum] _ k.kval;
        [] _ BackupBTree.DeleteFileInfo[LOOPHOLE[longKey]];
        };
<<>>
    Change: PROC [item: Item] ~ {
        longKey: LongKey _ ALL[0];
        longKey[item.k.wordNum] _ item.k.kval;
        BackupBTree.SetFileInfo[universalFile: LOOPHOLE[longKey], name: item.v]; 
        };

<<model support code>>

InitModel: PROCEDURE =
BEGIN
nItems _ 0;
nOldItems _ 0;
END;

InsertInModel: PROCEDURE[item: Item] =
BEGIN
x: CARDINAL;
FOR I: CARDINAL IN [0..nItems] DO
IF items[I].k = item.k THEN {x _ I; EXIT};
IF  I = nItems OR items[I].k.kval > item.k.kval THEN
BEGIN
IF nItems = MaxNItems THEN ERROR;
FOR J: CARDINAL DECREASING IN [I..nItems) DO
items[J+1] _ items[J];
ENDLOOP;
nItems _ nItems+1;
x _ I; EXIT;
END;
ENDLOOP;
items[x] _ item;
END;

DeleteFromModel: PROCEDURE[k: ShortKey] =
BEGIN
FOR I: CARDINAL IN [0..nItems) DO
IF items[I].k = k THEN
BEGIN
RememberAsOld[items[I]];
FOR J: CARDINAL IN (I..nItems) DO
items[J-1] _ items[J];
ENDLOOP;
nItems _ nItems - 1;
END;
IF items[I].k.kval > k.kval THEN EXIT;
ENDLOOP;
END;

LookUpInModel: PROCEDURE[k: ShortKey] RETURNS[ROPE] =
BEGIN
FOR I: CARDINAL IN [0..nItems) DO
IF items[I].k = k THEN RETURN[items[I].v];
IF items[I].k.kval > k.kval THEN EXIT;
ENDLOOP;
RETURN[NIL];
END;

PickARandomEntryKey: PROCEDURE RETURNS[ShortKey] =
BEGIN
IF nItems = 0 THEN ERROR;
RETURN[items[Random[] MOD nItems].k];
END;

PickARandomNonEntryKey: PROCEDURE RETURNS[ShortKey] =
BEGIN
k: ShortKey;
DO
k _ [0,0];
WHILE k = [0,0] DO k _ [Random[] MOD 9, Random[]] ENDLOOP;
IF LookUpInModel[k] = NIL THEN RETURN[k];
ENDLOOP;
END;

PickARandomValue: PROCEDURE RETURNS[ROPE] =
BEGIN
v: CARDINAL _ 0;
WHILE v = 0 DO v _ Random[] ENDLOOP;
RETURN[Convert.RopeFromCard[v]];
END;

PickARandomNewValueFor: PROCEDURE[k: ShortKey] RETURNS[ROPE] =
BEGIN
old: ROPE _ LookUpInModel[k];
v: ROPE _ "";
IF old = NIL THEN ERROR;
v _ Convert.RopeFromCard[Random[]];
RETURN[v];
END;

RememberAsOld: PROCEDURE[i: Item] =
BEGIN
x: CARDINAL;
IF nOldItems # MaxOldItems THEN
BEGIN
x _ nOldItems;
nOldItems _ nOldItems+1;
END
ELSE x _ Random[] MOD nOldItems;
oldItems[x] _ i;
END;

PickARandomOldKey: PROCEDURE RETURNS[ShortKey] =
BEGIN
k: ShortKey;
IF nOldItems = 0 THEN ERROR;
DO
k _ oldItems[Random[] MOD nOldItems].k;
IF LookUpInModel[k] = NIL THEN RETURN[k];
ENDLOOP;
END;

NoteAction: PROCEDURE[k: ShortKey, act: ActionCodes] =
BEGIN
IF k.kval = interestingKey THEN
BEGIN
rAct: Rope.ROPE _ SELECT act FROM
modify => "modify",
delete => "delete",
ENDCASE => "other";
ttyOut.PutF["\n\tat tick = %g, performing %g on key = %g\n", IO.card[tick.tick], IO.rope[rAct], IO.card[k.kval]];
END;
END;


<<testing support>>

ttyOut: IO.STREAM;
TickRec: TYPE = RECORD [tick: LONG CARDINAL_0, stop, pause: BOOLEAN _ FALSE];
tick: REF TickRec _ NEW[TickRec];

InitTestSupport: PROCEDURE =
BEGIN
[ , ttyOut] _ ViewerIO.CreateViewerStreams["test.log"];
ttyOut.PutF["here we go\N"];
tick.tick _ 0;
END;

DefineAction: PROCEDURE[name: Rope.ROPE, proc: ActionProcedure] RETURNS[Action] =
{RETURN[NEW[ActionBody _ [name, proc, 0]]]};

DefinePhase: PROCEDURE[list: LIST OF PhaseCase] RETURNS[Phase] =
BEGIN
nItems: CARDINAL _ 0;
totalWeight: LONG CARDINAL _ 0;
totalWeightShort: CARDINAL _ 0;
phase: Phase;
i: CARDINAL;
FOR p: LIST OF PhaseCase _ list, p.rest UNTIL p = NIL DO
nItems _ nItems + 1;
totalWeight _ totalWeight+LONG[p.first.weight];
totalWeightShort _ totalWeightShort+p.first.weight;
ENDLOOP;
IF nItems > MaxNItemsInPhase THEN ERROR;
IF totalWeight > MaxTotalWeightOfPhase THEN ERROR;
phase _ NEW[PhaseBody[nItems] _ [nItems, totalWeightShort, ]];
i _ 0; 
FOR p: LIST OF PhaseCase _ list, p.rest UNTIL p = NIL DO
phase.items[i] _ p.first;
i _ i + 1;
ENDLOOP;
RETURN[phase];
END;  

PerformOneRandomAct: PROCEDURE[phase: Phase] =
BEGIN
k: CARDINAL _ Random[] MOD phase.totalWeight;
DO
runningWeight: CARDINAL _ 0; 
FOR I: CARDINAL IN [0..phase.nItems) DO
runningWeight _ runningWeight + phase.items[I].weight;
IF k <= runningWeight THEN 
BEGIN
IF (phase.items[I].act.proc)[] THEN
BEGIN
phase.items[I].act.count _ phase.items[I].act.count + 1;
tick.tick _ tick.tick+1;
RETURN;
END;
END;
ENDLOOP;
ENDLOOP;
END;   


<<random number stuff (February 13, 1978) (by jim morris and Jim Mitchell)>>

Degree: CARDINAL = 33;
MidPower: CARDINAL = 13;
randomTable: ARRAY [0..Degree) OF CARDINAL _ [56572B, 112312B,  4714B, 100763B, 62510B,  1572B, 12255B, 132113B, 166574B,  2440B, 
104704B, 105254B, 106030B,  7053B, 56322B, 41163B, 11105B, 136203B, 55327B, 125100B, 76206B, 167173B, 173672B, 33211B, 134253B, 
153317B, 25327B, 136567B, 171517B, 23161B, 44276B, 72324B, 143455B]; -- these initial values were obtained by   calling 
InitRandom[123].
randomIndex: CARDINAL _ 0;
randomTrailer: CARDINAL _ Degree-MidPower;

InitRandom: PROCEDURE [seed: CARDINAL] =
BEGIN
i: CARDINAL;
xseed: CARDINAL;

FOR i IN [0..Degree) DO randomTable[i] _ 0 ENDLOOP;
randomTable[0] _ 2*seed+1;
xseed _ seed;
FOR i IN [1..MIN[16, Degree-1]] DO
randomTable[i] _ IF LOOPHOLE[xseed, INTEGER] < 0 THEN 1 ELSE 0;
xseed _ 2*xseed;
ENDLOOP;
randomIndex _ 0;
randomTrailer _ Degree-MidPower;
THROUGH [1..2000] DO [] _ Random[] ENDLOOP;
RETURN;
END;

Random: PROCEDURE RETURNS [CARDINAL] =
BEGIN
Result: CARDINAL = randomTable[randomIndex]+randomTable[randomTrailer];
randomTable[randomIndex] _ Result;
SELECT randomIndex+1 FROM
< Degree =>
BEGIN
randomIndex _ randomIndex+1;
randomTrailer _ IF randomTrailer < Degree-1 THEN randomTrailer+1 ELSE 0;
END;
= Degree =>
BEGIN
randomIndex _ 0;
randomTrailer _ Degree - MidPower;
END;
ENDCASE => ERROR;    -- should never be greater than Degree
RETURN [Result];
END;


<<main code>>

InitTestSupport[];
InitRandom[123];
[] _ ViewRec.ViewRef[tick];
Control[];

END..

    <<RTE: tick: 12: NIL vs. "" for entries not present in the model.>>
    <<>>