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: 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;


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;


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[];
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]; 
};


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;




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;   



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;



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

END..


BBackupBTreeTest.mesa
control
model state
random actions
no need to delete it from model, and doing so would add it to the old list

model support code
testing support
random number stuff (February 13, 1978) (by jim morris and Jim Mitchell)
main code
RTE: tick: 12: NIL vs. "" for entries not present in the model.

ΚŸ˜J˜Jš
œ™J˜š
Οk	˜	J˜J˜J˜J˜
J˜Jšœœ˜Jšœ
˜J˜Jšœ	œ˜$J˜J˜J˜—šœœ
œBœ˜ˆ
J˜Jšœœœ
˜Jšœœœ
˜J˜Jš
Οnœœ	œ
œ
œ˜6Jšœœœ˜Jšœœœœ œ
œ˜XJšœœ˜!Jšœœ
œ	˜-Jšœœœ˜Jšœœœ	œœ	œœ
œ˜nJšœœœœ˜8J˜Jš
œ™J˜šžœ	œ˜Jš
˜J˜WJ˜ZJ˜ZJ˜cJ˜cJ˜`J˜`J˜šœœ
˜"J˜J˜ J˜ J˜#J˜#J˜"J˜!J˜—šœœ
˜$J˜J˜ J˜ J˜#J˜#J˜"J˜!J˜J˜—J˜Jšœ[œœ˜iJ˜rJ˜Jšœ5˜;J˜J˜˜J˜—šœœ
œœ
œ˜4J˜"Jšœœœ˜/Jšœœœ+˜CJšœœœ
˜/Jšœ
˜—J˜J˜J˜J˜šœ
œ˜J˜"Jšœœœ
˜/Jšœœœ˜2Jšœœœ+˜KJš
˜—Jš
œ)˜)——˜˜Jšœ
˜J˜Jš
œ™J˜Jšœœ˜Jšœ
œ˜J˜Jšœœ˜Jšœœ
œ˜&Jšœœœœ˜/Jšœœœœ˜*Jšœ
œœœ˜;Jš	œ	œœœ
œ
˜)J˜Jšœœ˜Jšœ
œœ˜/Jšœœœœ˜3J˜Jšœ
œ˜%Jšœœ	˜!J˜Jš
œ™J˜šžœ	œ
œ
œ˜/Jš
˜J˜Jšœœ
œ
œ˜)J˜"J˜J˜J˜J˜
Jšœ
œ˜
Jšœ
˜J˜—šžœ	œ
œ
œ˜0Jš
˜J˜Jšœœ
œ
œ˜!J˜J˜(J˜J˜J˜
Jšœ
œ˜
Jšœ
˜—J˜šžœ	œ
œ
œ˜0Jš
˜Jšœœ
˜Jšœœ
œ
œ˜!J˜J˜J˜J˜
Jšœ
œ˜
Jšœ
˜—J˜šžœ	œ
œ
œ˜3Jš
˜Jšœœ
˜Jšœœ
œ
œ˜$J˜Jš
œJ™JJ˜J˜
Jšœ
œ˜
Jšœ
˜—J˜šžœ	œ
œ
œ˜3Jš
˜Jšœœ˜'J˜J˜
Jšœ
œ˜
Jšœ
˜—J˜šžœ	œ
œ
œ˜2Jš
˜Jšœœ
˜Jšœœ
˜Jšœœ
œ
œ˜$J˜J˜Jšœœ
œ
˜Jšœ
œ˜
Jšœ
˜J˜—šžœ	œ
œ
œ˜2Jš
˜Jšœœ˜'Jšœ
œ
œ
œ
˜Jšœ
œ˜
Jšœ
˜—J˜
codešΠbnœœœœ˜0K˜K˜Kšœœ˜4K˜K˜—šΟbœœ˜K˜K˜Kšœ œ˜3K˜—J™šžœœ˜K˜K˜&Kšœ'œ˜IK˜K˜—Jš
œ™J˜šž	œ	œ˜Jš
˜J˜J˜Jšœ
˜J˜—šž
œ	œ˜&Jš
˜Jšœœ
˜šœœ
œ
˜!Jšœœ	œ˜*šœ
œ˜4Jš
˜Jšœœ
œ
˜!š	œœ

œ
œ
˜,J˜Jšœ
˜—J˜Jšœœ
˜Jšœ
˜—Jšœ
˜—J˜Jšœ
˜—J˜šžœ	œœ˜)Jš
˜šœœ
œ
˜!šœ˜Jš
˜J˜šœœ
œ
˜!J˜Jšœ
˜—J˜Jšœ
˜—Jšœœ
œ
˜&Jšœ
˜—Jšœ
˜—J˜šž
œ	œœ
œ˜5Jš
˜šœœ
œ
˜!Jšœœ
œ
˜*Jšœœ
œ
˜&Jšœ
˜—Jšœ
œ˜Jšœ
˜—J˜šžœ	œ
œ
œ˜2Jš
˜Jšœœ
œ
˜Jšœœ˜%Jšœ
˜J˜—šžœ	œ
œ
œ˜5Jš
˜Jšœœ
˜Jš
˜Jšœœ
˜
Jšœœœœ
˜:Jšœœ
œ˜)Jšœ
˜Jšœ
˜—J˜šžœ	œ
œ
œ˜+Jš
˜Jšœœ˜Jšœœœ
˜$Jšœ˜ Jšœ
˜J˜—šžœ	œœ
œ˜>Jš
˜Jšœœ˜Jšœœ˜
Jšœœ
œ
œ
˜Jš
œ#˜#Jšœ˜
šœ
˜J˜——šž
œ	œ˜#Jš
˜Jšœœ
˜šœ˜Jš
˜J˜J˜Jš
˜Jšœœ˜ —J˜Jšœ
˜J˜—šžœ	œ
œ
œ˜0Jš
˜Jšœœ
˜Jšœœ
œ
˜Jš
˜Jšœœ˜'Jšœœ
œ˜)Jšœ
˜Jšœ
˜J˜—šž
œ	œœ˜6Jš
˜šœ˜Jš
˜šœœœ˜!J˜J˜Jšœ˜—Jšœ=œœ
œ˜qJšœ
˜—Jšœ
˜J˜—J˜J˜Jš
œ™J˜Jšœœ
œ
˜Jš
œ	œœœ
œœœ˜MJšœœœ
˜!J˜šžœ	œ˜Jš
˜J˜7J˜J˜Jšœ
˜—J˜šžœ	œœœ
˜QJšœ
œ
œ!˜,J˜—š
žœ	œœ
œœ	˜@Jš
˜Jšœœ˜Jšœ
œ
œ˜Jšœœ˜J˜
Jšœœ
˜šœœ
œœœ
˜8J˜Jšœœ˜/J˜3Jšœ
˜—Jšœœ
œ
˜(Jšœ%œ
œ
˜2Jšœœ3˜>J˜šœœ
œœœ
˜8J˜J˜
Jšœ
˜—Jšœ˜Jšœ˜J˜—šžœ	œ˜.Jš
˜Jšœœœ˜-š
˜Jšœœ˜šœœ
œ˜'J˜6šœœ
˜Jš
˜šœ˜#Jš
˜J˜8J˜Jšœ
˜Jšœ
˜—Jšœ
˜Jšœ
˜——Jšœ
˜—Jšœ˜—˜J˜———Jš
œH™HJ˜Jšœœ˜Jšœ
œ˜Jšœ
œ
œ
œΟcC˜ŠJšœ
œ˜Jšœœ˜*J˜šž
œ	œœ˜(Jš
˜Jšœœ
˜Jšœœ
˜—˜Jšœœ
œœ
˜3J˜J˜
šœœœ˜"Jšœœ
œœœœ˜?J˜Jšœ
˜—J˜J˜ Jšœœœ
˜+Jšœ
˜Jšœ
˜—J˜šžœ	œ
œœ˜&Jš
˜Jšœœ7˜GJ˜"šœ˜˜Jš
˜J˜Jšœœœœ˜HJšœ
˜—˜Jš
˜J˜J˜"Jšœ
˜—Jšœœ‘&˜8—Jšœ
˜Jšœ
˜—J˜J˜Jš
œ	™	˜J˜J˜J˜J˜
—˜Jšœ˜J˜—Kš
Οr?™?K™—…—)š:{