-- File: RandomIndexTest.mesa
-- Contents: program to add and delete random numbers of CedarDB index entries
-- Last edited by
  -- Rick Cattell on September 20, 1982 2:38 pm

DIRECTORY
  DBStorage,
  DBTuplesConcrete,
  DBView,
  DBViewPrivate,
  IO,
  Process,
  Random,
  Rope,
  UserExec,
  UserExecExtras;
  
RandomIndexTest: PROGRAM IMPORTS
  DBStorage, DBView, DBViewPrivate, IO, Process, Random,
  Rope, UserExec, UserExecExtras  =

BEGIN ROPE: TYPE = Rope.ROPE;

in, out: IO.Handle;

keys: LIST OF ROPE_ NIL;
value: DBStorage.TupleHandle;
keyListLength: INT_ 0;
nIterations, maxInsertions: INT;
cycleCount: INT;
stopAtThisCycle: INT_ 0;
pleaseStop: BOOL_ FALSE;
paddingStringLength: INT_ 5;
paddingString: ROPE;
index: DBStorage.IndexHandle;
prefixArray: ARRAY [0..50) OF ROPE;
prefixCount: INT_ 10;
averageCommitFrequency: INT;

WhatNow: SIGNAL = CODE;

SystemTSTuple: TYPE = REF tupleSet DBTuplesConcrete.TupleObject;

TickTock: PROC =
  BEGIN
  cycleCount_ cycleCount+1;
  IF Random.Choose[0, averageCommitFrequency] = 0 THEN 
    BEGIN -- close and re-set-up database
    out.PutF["Closing & Re-opening..."];
    DBView.CloseDatabase[];
    []_ DBView.OpenDatabase[databaseName: dbName, version: OldOnly];
    value_ index_ DBViewPrivate.systemIndex;
    END;
  IF cycleCount=stopAtThisCycle THEN SIGNAL WhatNow;
  END;

GenRandomKey: PROC RETURNS [ROPE] =
  -- prefix random key with a randomly chosen rope, and follow with padding
  BEGIN
  prefix: ROPE _
    IF prefixCount#0 THEN prefixArray[Random.Choose[0, prefixCount-1]]
    ELSE NIL;
  RETURN[IO.PutFR[
    "%g%g%g",
    IO.rope[prefix],
    IO.int[Random.Next[]],
    IO.rope[paddingString] ]];
  END;

GenPlainRandomKey: PROC RETURNS [ROPE] =
  -- same as above but without prefix, or padding after 
  {RETURN[IO.PutFR[, IO.int[Random.Next[]] ]]};



PlayWithIndex: PROC =
  BEGIN  
  out.PutF["Testing index...\n"];
  THROUGH [1 .. nIterations] DO 
    AddSomeEntries[];
    DeleteSomeEntries[];
    ENDLOOP;
  CheckEntries[];
  END;

AddSomeEntries: PROC =
    BEGIN
    key: ROPE;
    nToInsert: INT_ Random.Choose[0, maxInsertions];	
    FOR j: INT IN [0..nToInsert) DO
      TickTock[];
      IF pleaseStop THEN RETURN;
      key_ GenRandomKey[];
      DBStorage.InsertIntoIndex[index, key, value];
      keyListLength_ keyListLength + 1;
      keys_ CONS[key, keys];
      IF j MOD 10 = 0 THEN out.PutChar['+];
      ENDLOOP;
    out.PutF["... Added %g index entries (now %g)\n", IO.int[nToInsert], IO.int[keyListLength]];
    END;
  
DeleteSomeEntries: PROC =
    BEGIN
    prevKey: LIST OF ROPE;
    mDeleted, estToDelete: INT;
    estToDelete_ Random.Choose[0, keyListLength];
    --  Delete approx estToDelete entries by deleting each one
    -- with probability of estToDelete/keyListLength:
    mDeleted_ 0;
    prevKey_ NIL;
    FOR keysT: LIST OF ROPE_ keys, keysT.rest UNTIL keysT=NIL DO
      IF Random.Choose[0, keyListLength]<estToDelete THEN
        BEGIN
        TickTock[];
        IF mDeleted MOD 10 = 0 THEN out.PutChar['-];
        mDeleted_ mDeleted+1;
        keyListLength_ keyListLength-1;
        DBStorage.DeleteFromIndex[index, keysT.first, value];
        IF prevKey=NIL THEN
          keys_ keys.rest -- first elt of list deleted
        ELSE
          prevKey.rest_ keysT.rest; -- remove it from keys array
        END
      ELSE
        prevKey_ keysT;
      ENDLOOP;
    out.PutF["... Deleted %g index entries (now %g)\n", IO.int[mDeleted], IO.int[keyListLength]];
    END;

CheckEntries: PROC =
  BEGIN
  count: INT_ 0;
  ish: DBStorage.IndexScanHandle;
  t: DBStorage.TupleHandle;
  out.PutF["Checking contents of index..."];
  FOR keysT: LIST OF ROPE_ keys, keysT.rest UNTIL keysT=NIL DO
    ish_ DBStorage.OpenScanIndex[index, [keysT.first, keysT.first, TRUE, TRUE]];
    IF (t_DBStorage.NextScanIndex[ish])= NIL THEN ERROR; -- lost an index entry!
    IF NOT DBView.Eq[t, value] THEN ERROR; -- wrong value associated with it
    DBStorage.CloseScanIndex[ish];
    ENDLOOP;
  -- Check to see there are the right number of entries in the index
  ish_ DBStorage.OpenScanIndex[index, ["", "\177", TRUE, TRUE]];
  UNTIL DBStorage.NextScanIndex[ish]=NIL DO
    count_ count+1 ENDLOOP;
  DBStorage.CloseScanIndex[ish];
  -- Check that right number of entries in B-tree
  IF count#keyListLength+2 THEN ERROR;  -- add 2 because using owner index, contains 2 system entries 
  END;

AskForInt: PROC [question: ROPE, default: INT_ -1] RETURNS [v: INT] =
  -- Ask user question, return int with default value if user hits CR.
  BEGIN
  IF default=-1 THEN
    out.PutF["%g? ", IO.rope[question]]
  ELSE
    out.PutF["%g [%g]? ", IO.rope[question], IO.int[default]];
  IF default#-1 AND in.PeekChar[]='\n THEN v_ default
  ELSE v_ in.GetInt[];
  []_ in.GetChar[]; -- skip over the CR
  RETURN[v]
  END;

Main: PROC =
  BEGIN ENABLE Process.Aborted => GOTO Abort;
  keys_ NIL;
  cycleCount_ 15;
  keyListLength_ 0;
  []_ Random.Init[];
  FOR i: INT IN [0..prefixCount) DO
    prefixArray[i]_ GenPlainRandomKey[] ENDLOOP;
  [in, out]_ IO.CreateTTYStreams["IndexTest"];
  in_ IO.CreateEditedStream[in, out];
  out.PutF["Random DBIndex Test Program: Creating database..."];
  []_ DBView.OpenDatabase[databaseName: dbName, version: NewOnly];
  index_ DBViewPrivate.systemIndex; -- use the system index already created by DBView
  value_ index; -- just use the index tuple itself as a value to store, it doesn't matter for now!
  UserExecExtras.DoIt[UserExec.GetExecHandle[], "_ DBIndexImpl.CheckFlag_ TRUE"];
  UserExecExtras.DoIt[UserExec.GetExecHandle[], "_ DBIndexImpl.deletionTurnedOn_ TRUE"];
  nIterations_ AskForInt["\nHow many iterations", 10];
  maxInsertions_ AskForInt["Max insertions per iteration", 300];
  stopAtThisCycle_ AskForInt["Stop at cycle", 99999];
  averageCommitFrequency_ AskForInt["Mean re-open frequency", 300];
  paddingStringLength_ AskForInt["Key padding", 5];
  paddingString_ NIL;
  FOR j: INT IN [0.. paddingStringLength) DO
    paddingString_ paddingString.Concat[" ..."] ENDLOOP;
  PlayWithIndex;
  out.PutF["Deleting index..."];
  DBStorage.DestroyIndex[index];
  out.PutF["Closing database..."];
  DBView.CloseDatabase[];
  out.PutF["Done.  Bye.\n"];
  EXITS Abort => {out.PutF["Aborting..."]; DBView.CloseDatabase[]; out.PutF["Done.  Bye.\n"]};
  END;

dbName: ROPE _ "[Local]IndexTest";

Start: PROC =
  {Process.Detach[FORK Main[]]};
  
Start[];

END.

To run:

run ExtraCedar
run CedarDB
compile RandomIndexTest
run RandomImpl
run RandomIndexTest