SQLite

#
# This Makefile is designed for use with main.mk in the root directory of

# this project. After including main.mk, the users makefile should contain:
#
#    LSMDIR=$(TOP)/ext/lsm1/

#    include $(LSMDIR)/Makefile
#
# The most useful targets are [lsmtest] and [lsm.so].
#

LSMOBJ    = \
  lsm_ckpt.o \
  lsm_file.o \
  lsm_log.o \
  lsm_main.o \
  lsm_mem.o \
  lsm_mutex.o \
  lsm_shared.o \
  lsm_sorted.o \
  lsm_str.o \
  lsm_tree.o \
  lsm_unix.o \
  lsm_win32.o \
  lsm_varint.o \
  lsm_vtab.o

LSMHDR   = \
  $(LSMDIR)/lsm.h \
  $(LSMDIR)/lsmInt.h

LSMTESTSRC = $(LSMDIR)/lsm-test/lsmtest1.c $(LSMDIR)/lsm-test/lsmtest2.c     \
             $(LSMDIR)/lsm-test/lsmtest3.c $(LSMDIR)/lsm-test/lsmtest4.c     \
             $(LSMDIR)/lsm-test/lsmtest5.c $(LSMDIR)/lsm-test/lsmtest6.c     \
             $(LSMDIR)/lsm-test/lsmtest7.c $(LSMDIR)/lsm-test/lsmtest8.c     \
             $(LSMDIR)/lsm-test/lsmtest9.c                                   \
             $(LSMDIR)/lsm-test/lsmtest_datasource.c \
             $(LSMDIR)/lsm-test/lsmtest_func.c $(LSMDIR)/lsm-test/lsmtest_io.c  \
             $(LSMDIR)/lsm-test/lsmtest_main.c $(LSMDIR)/lsm-test/lsmtest_mem.c \
             $(LSMDIR)/lsm-test/lsmtest_tdb.c $(LSMDIR)/lsm-test/lsmtest_tdb3.c \
             $(LSMDIR)/lsm-test/lsmtest_util.c


# all: lsm.so

lsm.so:	$(LSMOBJ)
	$(TCCX) $(CFLAGS) -shared -o lsm.so $(LSMOBJ)

%.o:	$(LSMDIR)/%.c $(LSMHDR)
	$(TCCX) -I$(LSMDIR) $(CFLAGS) -c $<
	
lsmtest$(EXE): $(LSMOBJ) $(LSMTESTSRC) $(LSMTESTHDR)
	# $(TCPPX) -c $(TOP)/lsm-test/lsmtest_tdb2.cc
	$(TCCX) -I$(LSMDIR) $(LSMTESTSRC) $(LSMOBJ) -o lsmtest$(EXE) $(THREADLIB) -lsqlite3 

Organization of test case files:

  lsmtest1.c: Data tests. Tests that perform many inserts and deletes on a 
              database file, then verify that the contents of the database can
              be queried.

  lsmtest2.c: Crash tests. Tests that attempt to verify that the database 
              recovers correctly following an application or system crash.

  lsmtest3.c: Rollback tests. Tests that focus on the explicit rollback of
              transactions and sub-transactions.

  lsmtest4.c: Multi-client tests.

  lsmtest5.c: Multi-client tests with a different thread for each client.

  lsmtest6.c: OOM injection tests.

  lsmtest7.c: API tests.

  lsmtest8.c: Writer crash tests. Tests in this file attempt to verify that
              the system recovers and other clients proceed unaffected if
              a process fails in the middle of a write transaction.

              The difference from lsmtest2.c is that this file tests
              live-recovery (recovery from a failure that occurs while other
              clients are still running) whereas lsmtest2.c tests recovery
              from a system or power failure.

  lsmtest9.c: More data tests. These focus on testing that calling
              lsm_work(nMerge=1) to compact the database does not corrupt it.
              In other words, that databases containing block-redirects
              can be read and written.

#ifndef __WRAPPER_INT_H_
#define __WRAPPER_INT_H_

#include "lsmtest_tdb.h"
#include "sqlite3.h"
#include "lsm.h"

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#ifdef __cplusplus
extern "C" {
#endif

#ifndef _LSM_INT_H
typedef unsigned int  u32;
typedef unsigned char u8;
typedef long long int i64;
typedef unsigned long long int u64;
#endif


#define ArraySize(x) ((int)(sizeof(x) / sizeof((x)[0])))

#define MIN(x,y) ((x)<(y) ? (x) : (y))
#define MAX(x,y) ((x)>(y) ? (x) : (y))

#define unused_parameter(x) (void)(x)

#define TESTDB_DEFAULT_PAGE_SIZE   4096
#define TESTDB_DEFAULT_CACHE_SIZE  2048

/*
** Ideally, these should be in wrapper.c. But they are here instead so that 
** they can be used by the C++ database wrappers in wrapper2.cc.
*/
typedef struct DatabaseMethods DatabaseMethods;
struct TestDb {
  DatabaseMethods const *pMethods;          /* Database methods */
  const char *zLibrary;                     /* Library name for tdb_open() */
};
struct DatabaseMethods {
  int (*xClose)(TestDb *);
  int (*xWrite)(TestDb *, void *, int , void *, int);
  int (*xDelete)(TestDb *, void *, int);
  int (*xDeleteRange)(TestDb *, void *, int, void *, int);
  int (*xFetch)(TestDb *, void *, int, void **, int *);
  int (*xScan)(TestDb *, void *, int, void *, int, void *, int,
    void (*)(void *, void *, int , void *, int)
  );
  int (*xBegin)(TestDb *, int);
  int (*xCommit)(TestDb *, int);
  int (*xRollback)(TestDb *, int);
};

/* 
** Functions in wrapper2.cc (a C++ source file). wrapper2.cc contains the
** wrapper for Kyoto Cabinet. Kyoto cabinet has a C API, but
** the primary interface is the C++ API.
*/
int test_kc_open(const char*, const char *zFilename, int bClear, TestDb **ppDb);
int test_kc_close(TestDb *);
int test_kc_write(TestDb *, void *, int , void *, int);
int test_kc_delete(TestDb *, void *, int);
int test_kc_delete_range(TestDb *, void *, int, void *, int);
int test_kc_fetch(TestDb *, void *, int, void **, int *);
int test_kc_scan(TestDb *, void *, int, void *, int, void *, int,
  void (*)(void *, void *, int , void *, int)
);

int test_mdb_open(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_mdb_close(TestDb *);
int test_mdb_write(TestDb *, void *, int , void *, int);
int test_mdb_delete(TestDb *, void *, int);
int test_mdb_fetch(TestDb *, void *, int, void **, int *);
int test_mdb_scan(TestDb *, void *, int, void *, int, void *, int,
  void (*)(void *, void *, int , void *, int)
);

/* 
** Functions in wrapper3.c. This file contains the tdb wrapper for lsm.
** The wrapper for lsm is a bit more involved than the others, as it 
** includes code for a couple of different lsm configurations, and for
** various types of fault injection and robustness testing.
*/
int test_lsm_open(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_lsm_lomem_open(const char*, const char*, int bClear, TestDb **ppDb);
int test_lsm_zip_open(const char*, const char*, int bClear, TestDb **ppDb);
int test_lsm_small_open(const char*, const char*, int bClear, TestDb **ppDb);
int test_lsm_mt2(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_lsm_mt3(const char*, const char *zFile, int bClear, TestDb **ppDb);

int tdb_lsm_configure(lsm_db *, const char *);

/* Functions in lsmtest_tdb4.c */
int test_bt_open(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_fbt_open(const char*, const char *zFile, int bClear, TestDb **ppDb);
int test_fbts_open(const char*, const char *zFile, int bClear, TestDb **ppDb);


/* Functions in testutil.c. */
int  testPrngInit(void);
u32  testPrngValue(u32 iVal);
void testPrngArray(u32 iVal, u32 *aOut, int nOut);
void testPrngString(u32 iVal, char *aOut, int nOut);

void testErrorInit(int argc, char **);
void testPrintError(const char *zFormat, ...);
void testPrintUsage(const char *zArgs);
void testPrintFUsage(const char *zFormat, ...);
void testTimeInit(void);
int  testTimeGet(void);

/* Functions in testmem.c. */
void testMallocInstall(lsm_env *pEnv);
void testMallocUninstall(lsm_env *pEnv);
void testMallocCheck(lsm_env *pEnv, int *, int *, FILE *);
void testMallocOom(lsm_env *pEnv, int, int, void(*)(void*), void *);
void testMallocOomEnable(lsm_env *pEnv, int);

/* lsmtest.c */
TestDb *testOpen(const char *zSystem, int, int *pRc);
void testReopen(TestDb **ppDb, int *pRc);
void testClose(TestDb **ppDb);

void testFetch(TestDb *, void *, int, void *, int, int *);
void testWrite(TestDb *, void *, int, void *, int, int *);
void testDelete(TestDb *, void *, int, int *);
void testDeleteRange(TestDb *, void *, int, void *, int, int *);
void testWriteStr(TestDb *, const char *, const char *zVal, int *pRc);
void testFetchStr(TestDb *, const char *, const char *, int *pRc);

void testBegin(TestDb *pDb, int iTrans, int *pRc);
void testCommit(TestDb *pDb, int iTrans, int *pRc);

void test_failed(void);

char *testMallocPrintf(const char *zFormat, ...);
char *testMallocVPrintf(const char *zFormat, va_list ap);
int testGlobMatch(const char *zPattern, const char *zStr);

void testScanCompare(TestDb *, TestDb *, int, void *, int, void *, int, int *);
void testFetchCompare(TestDb *, TestDb *, void *, int, int *);

void *testMalloc(int);
void *testMallocCopy(void *pCopy, int nByte);
void *testRealloc(void *, int);
void testFree(void *);

/* lsmtest_bt.c */
int do_bt(int nArg, char **azArg);

/* testio.c */
int testVfsConfigureDb(TestDb *pDb);

/* testfunc.c */
int do_show(int nArg, char **azArg);
int do_work(int nArg, char **azArg);

/* testio.c */
int do_io(int nArg, char **azArg);

/* lsmtest2.c */
void do_crash_test(const char *zPattern, int *pRc);
int do_rollback_test(int nArg, char **azArg);

/* test3.c */
void test_rollback(const char *zSystem, const char *zPattern, int *pRc);

/* test4.c */
void test_mc(const char *zSystem, const char *zPattern, int *pRc);

/* test5.c */
void test_mt(const char *zSystem, const char *zPattern, int *pRc);

/* lsmtest6.c */
void test_oom(const char *zPattern, int *pRc);
void testDeleteLsmdb(const char *zFile);

void testSaveDb(const char *zFile, const char *zAuxExt);
void testRestoreDb(const char *zFile, const char *zAuxExt);
void testCopyLsmdb(const char *zFrom, const char *zTo);

/* lsmtest7.c */
void test_api(const char *zPattern, int *pRc);

/* lsmtest8.c */
void do_writer_crash_test(const char *zPattern, int *pRc);

/*************************************************************************
** Interface to functionality in test_datasource.c.
*/
typedef struct Datasource Datasource;
typedef struct DatasourceDefn DatasourceDefn;

struct DatasourceDefn {
  int eType;                      /* A TEST_DATASOURCE_* value */
  int nMinKey;                    /* Minimum key size */
  int nMaxKey;                    /* Maximum key size */
  int nMinVal;                    /* Minimum value size */
  int nMaxVal;                    /* Maximum value size */
};

#define TEST_DATASOURCE_RANDOM    1
#define TEST_DATASOURCE_SEQUENCE  2

char *testDatasourceName(const DatasourceDefn *);
Datasource *testDatasourceNew(const DatasourceDefn *);
void testDatasourceFree(Datasource *);
void testDatasourceEntry(Datasource *, int, void **, int *, void **, int *);
/* End of test_datasource.c interface.
*************************************************************************/

void testWriteDatasource(TestDb *, Datasource *, int, int *);
void testWriteDatasourceRange(TestDb *, Datasource *, int, int, int *);
void testDeleteDatasource(TestDb *, Datasource *, int, int *);
void testDeleteDatasourceRange(TestDb *, Datasource *, int, int, int *);


/* test1.c */
void test_data_1(const char *, const char *, int *pRc);
void test_data_2(const char *, const char *, int *pRc);
void test_data_3(const char *, const char *, int *pRc);
void testDbContents(TestDb *, Datasource *, int, int, int, int, int, int *);
void testCaseProgress(int, int, int, int *);
int testCaseNDot(void);

void testCompareDb(Datasource *, int, int, TestDb *, TestDb *, int *);
int testControlDb(TestDb **ppDb);

typedef struct CksumDb CksumDb;
CksumDb *testCksumArrayNew(Datasource *, int, int, int);
char *testCksumArrayGet(CksumDb *, int);
void testCksumArrayFree(CksumDb *);
void testCaseStart(int *pRc, char *zFmt, ...);
void testCaseFinish(int rc);
void testCaseSkip(void);
int testCaseBegin(int *, const char *, const char *, ...);

#define TEST_CKSUM_BYTES 29
int testCksumDatabase(TestDb *pDb, char *zOut);
int testCountDatabase(TestDb *pDb);
void testCompareInt(int, int, int *);
void testCompareStr(const char *z1, const char *z2, int *pRc);

/* lsmtest9.c */
void test_data_4(const char *, const char *, int *pRc);


/*
** Similar to the Tcl_GetIndexFromObjStruct() Tcl library function.
*/
#define testArgSelect(w,x,y,z) testArgSelectX(w,x,sizeof(w[0]),y,z)
int testArgSelectX(void *, const char *, int, const char *, int *);

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif

#endif

#include "lsmtest.h"

#define DATA_SEQUENTIAL TEST_DATASOURCE_SEQUENCE
#define DATA_RANDOM     TEST_DATASOURCE_RANDOM

typedef struct Datatest1 Datatest1;
typedef struct Datatest2 Datatest2;

/*
** An instance of the following structure contains parameters used to
** customize the test function in this file. Test procedure:
**
**   1. Create a data-source based on the "datasource definition" vars.
**
**   2. Insert nRow key value pairs into the database.
**
**   3. Delete all keys from the database. Deletes are done in the same 
**      order as the inserts.
**
** During steps 2 and 3 above, after each Datatest1.nVerify inserts or
** deletes, the following:
**
**   a. Run Datasource.nTest key lookups and check the results are as expected.
**
**   b. If Datasource.bTestScan is true, run a handful (8) of range
**      queries (scanning forwards and backwards). Check that the results
**      are as expected.
**
**   c. Close and reopen the database. Then run (a) and (b) again.
*/
struct Datatest1 {
  /* Datasource definition */
  DatasourceDefn defn;

  /* Test procedure parameters */
  int nRow;                       /* Number of rows to insert then delete */
  int nVerify;                    /* How often to verify the db contents */
  int nTest;                      /* Number of keys to test (0==all) */
  int bTestScan;                  /* True to do scan tests */
};

/*
** An instance of the following data structure is used to describe the
** second type of test case in this file. The chief difference between 
** these tests and those described by Datatest1 is that these tests also
** experiment with range-delete operations. Tests proceed as follows:
**
**     1. Open the datasource described by Datatest2.defn. 
**
**     2. Open a connection on an empty database.
**
**     3. Do this Datatest2.nIter times:
**
**        a) Insert Datatest2.nWrite key-value pairs from the datasource.
**
**        b) Select two pseudo-random keys and use them as the start
**           and end points of a range-delete operation.
**
**        c) Verify that the contents of the database are as expected (see
**           below for details).
**
**        d) Close and then reopen the database handle.
**
**        e) Verify that the contents of the database are still as expected.
**
** The inserts and range deletes are run twice - once on the database being
** tested and once using a control system (sqlite3, kc etc. - something that 
** works). In order to verify that the contents of the db being tested are
** correct, the test runs a bunch of scans and lookups on both the test and
** control databases. If the results are the same, the test passes.
*/
struct Datatest2 {
  DatasourceDefn defn;
  int nRange;
  int nWrite;                     /* Number of writes per iteration */
  int nIter;                      /* Total number of iterations to run */
};

/*
** Generate a unique name for the test case pTest with database system
** zSystem.
*/
static char *getName(const char *zSystem, Datatest1 *pTest){
  char *zRet;
  char *zData;
  zData = testDatasourceName(&pTest->defn);
  zRet = testMallocPrintf("data.%s.%s.%d.%d", 
      zSystem, zData, pTest->nRow, pTest->nVerify
  );
  testFree(zData);
  return zRet;
}

int testControlDb(TestDb **ppDb){
#ifdef HAVE_KYOTOCABINET
  return tdb_open("kyotocabinet", "tmp.db", 1, ppDb);
#else
  return tdb_open("sqlite3", ":memory:", 1, ppDb);
#endif
}

void testDatasourceFetch(
  TestDb *pDb,                    /* Database handle */
  Datasource *pData,
  int iKey,
  int *pRc                        /* IN/OUT: Error code */
){
  void *pKey; int nKey;           /* Database key to query for */
  void *pVal; int nVal;           /* Expected result of query */

  testDatasourceEntry(pData, iKey, &pKey, &nKey, &pVal, &nVal);
  testFetch(pDb, pKey, nKey, pVal, nVal, pRc);
}

/*
** This function is called to test that the contents of database pDb
** are as expected. In this case, expected is defined as containing
** key-value pairs iFirst through iLast, inclusive, from data source 
** pData. In other words, a loop like the following could be used to
** construct a database with identical contents from scratch.
**
**   for(i=iFirst; i<=iLast; i++){
**     testDatasourceEntry(pData, i, &pKey, &nKey, &pVal, &nVal);
**     // insert (pKey, nKey) -> (pVal, nVal) into database
**   }
**
** The key domain consists of keys 0 to (nRow-1), inclusive, from
** data source pData. For both scan and lookup tests, keys are selected
** pseudo-randomly from within this set.
**
** This function runs nLookupTest lookup tests and nScanTest scan tests.
**
** A lookup test consists of selecting a key from the domain and querying
** pDb for it. The test fails if the presence of the key and, if present,
** the associated value do not match the expectations defined above.
**
** A scan test involves selecting a key from the domain and running
** the following queries:
**
**   1. Scan all keys equal to or greater than the key, in ascending order.
**   2. Scan all keys equal to or smaller than the key, in descending order.
**
** Additionally, if nLookupTest is greater than zero, the following are
** run once:
**
**   1. Scan all keys in the db, in ascending order.
**   2. Scan all keys in the db, in descending order.
**
** As you would assume, the test fails if the returned values do not match
** expectations.
*/
void testDbContents(
  TestDb *pDb,                    /* Database handle being tested */
  Datasource *pData,              /* pDb contains data from here */
  int nRow,                       /* Size of key domain */
  int iFirst,                     /* Index of first key from pData in pDb */
  int iLast,                      /* Index of last key from pData in pDb */
  int nLookupTest,                /* Number of lookup tests to run */
  int nScanTest,                  /* Number of scan tests to run */
  int *pRc                        /* IN/OUT: Error code */
){
  int j;
  int rc = *pRc;

  if( rc==0 && nScanTest ){
    TestDb *pDb2 = 0;

    /* Open a control db (i.e. one that we assume works) */
    rc = testControlDb(&pDb2);

    for(j=iFirst; rc==0 && j<=iLast; j++){
      void *pKey; int nKey;         /* Database key to insert */
      void *pVal; int nVal;         /* Database value to insert */
      testDatasourceEntry(pData, j, &pKey, &nKey, &pVal, &nVal);
      rc = tdb_write(pDb2, pKey, nKey, pVal, nVal);
    }

    if( rc==0 ){
      int iKey1;
      int iKey2;
      void *pKey1; int nKey1;       /* Start key */
      void *pKey2; int nKey2;       /* Final key */

      iKey1 = testPrngValue((iFirst<<8) + (iLast<<16)) % nRow;
      iKey2 = testPrngValue((iLast<<8) + (iFirst<<16)) % nRow;
      testDatasourceEntry(pData, iKey1, &pKey2, &nKey1, 0, 0);
      pKey1 = testMalloc(nKey1+1);
      memcpy(pKey1, pKey2, nKey1+1);
      testDatasourceEntry(pData, iKey2, &pKey2, &nKey2, 0, 0);

      testScanCompare(pDb2, pDb, 0, 0, 0,         0, 0,         &rc);
      testScanCompare(pDb2, pDb, 0, 0, 0,         pKey2, nKey2, &rc);
      testScanCompare(pDb2, pDb, 0, pKey1, nKey1, 0, 0,         &rc);
      testScanCompare(pDb2, pDb, 0, pKey1, nKey1, pKey2, nKey2, &rc);
      testScanCompare(pDb2, pDb, 1, 0, 0,         0, 0,         &rc);
      testScanCompare(pDb2, pDb, 1, 0, 0,         pKey2, nKey2, &rc);
      testScanCompare(pDb2, pDb, 1, pKey1, nKey1, 0, 0,         &rc);
      testScanCompare(pDb2, pDb, 1, pKey1, nKey1, pKey2, nKey2, &rc);
      testFree(pKey1);
    }
    tdb_close(pDb2);
  }

  /* Test some lookups. */
  for(j=0; rc==0 && j<nLookupTest; j++){
    int iKey;                     /* Datasource key to test */
    void *pKey; int nKey;         /* Database key to query for */
    void *pVal; int nVal;         /* Expected result of query */

    if( nLookupTest>=nRow ){
      iKey = j;
    }else{
      iKey = testPrngValue(j + (iFirst<<8) + (iLast<<16)) % nRow;
    }

    testDatasourceEntry(pData, iKey, &pKey, &nKey, &pVal, &nVal);
    if( iFirst>iKey || iKey>iLast ){
      pVal = 0;
      nVal = -1;
    }

    testFetch(pDb, pKey, nKey, pVal, nVal, &rc);
  }

  *pRc = rc;
}

/*
** This function should be called during long running test cases to output
** the progress dots (...) to stdout.
*/
void testCaseProgress(int i, int n, int nDot, int *piDot){
  int iDot = *piDot;
  while( iDot < ( ((nDot*2+1) * i) / (n*2) ) ){
    printf(".");
    fflush(stdout);
    iDot++;
  }
  *piDot = iDot;
}

int testCaseNDot(void){ return 20; }

#if 0
static void printScanCb(
    void *pCtx, void *pKey, int nKey, void *pVal, int nVal
){
  printf("%s\n", (char *)pKey);
  fflush(stdout);
}
#endif

static void doDataTest1(
  const char *zSystem,            /* Database system to test */
  Datatest1 *p,                   /* Structure containing test parameters */
  int *pRc                        /* OUT: Error code */
){
  int i;
  int iDot;
  int rc = LSM_OK;
  Datasource *pData;
  TestDb *pDb;

  /* Start the test case, open a database and allocate the datasource. */
  pDb = testOpen(zSystem, 1, &rc);
  pData = testDatasourceNew(&p->defn);

  i = 0;
  iDot = 0;
  while( rc==LSM_OK && i<p->nRow ){

    /* Insert some data */
    testWriteDatasourceRange(pDb, pData, i, p->nVerify, &rc);
    i += p->nVerify;

    /* Check that the db content is correct. */
    testDbContents(pDb, pData, p->nRow, 0, i-1, p->nTest, p->bTestScan, &rc);

    /* Close and reopen the database. */
    testReopen(&pDb, &rc);

    /* Check that the db content is still correct. */
    testDbContents(pDb, pData, p->nRow, 0, i-1, p->nTest, p->bTestScan, &rc);

    /* Update the progress dots... */
    testCaseProgress(i, p->nRow, testCaseNDot()/2, &iDot);
  }

  i = 0;
  iDot = 0;
  while( rc==LSM_OK && i<p->nRow ){

    /* Delete some entries */
    testDeleteDatasourceRange(pDb, pData, i, p->nVerify, &rc);
    i += p->nVerify;

    /* Check that the db content is correct. */
    testDbContents(pDb, pData, p->nRow, i, p->nRow-1,p->nTest,p->bTestScan,&rc);

    /* Close and reopen the database. */
    testReopen(&pDb, &rc);

    /* Check that the db content is still correct. */
    testDbContents(pDb, pData, p->nRow, i, p->nRow-1,p->nTest,p->bTestScan,&rc);

    /* Update the progress dots... */
    testCaseProgress(i, p->nRow, testCaseNDot()/2, &iDot);
  }

  /* Free the datasource, close the database and finish the test case. */
  testDatasourceFree(pData);
  tdb_close(pDb);
  testCaseFinish(rc);
  *pRc = rc;
}


void test_data_1(
  const char *zSystem,            /* Database system name */
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  Datatest1 aTest[] = {
    { {DATA_RANDOM,     500,600,   1000,2000},     1000,  100,  10,  0},
    { {DATA_RANDOM,     20,25,     100,200},       1000,  250, 1000, 1},
    { {DATA_RANDOM,     8,10,      100,200},       1000,  250, 1000, 1},
    { {DATA_RANDOM,     8,10,      10,20},         1000,  250, 1000, 1},
    { {DATA_RANDOM,     8,10,      1000,2000},     1000,  250, 1000, 1},
    { {DATA_RANDOM,     8,100,     10000,20000},    100,   25,  100, 1},
    { {DATA_RANDOM,     80,100,    10,20},         1000,  250, 1000, 1},
    { {DATA_RANDOM,     5000,6000, 10,20},          100,   25,  100, 1},
    { {DATA_SEQUENTIAL, 5,10,      10,20},         1000,  250, 1000, 1},
    { {DATA_SEQUENTIAL, 5,10,      100,200},       1000,  250, 1000, 1},
    { {DATA_SEQUENTIAL, 5,10,      1000,2000},     1000,  250, 1000, 1},
    { {DATA_SEQUENTIAL, 5,100,     10000,20000},    100,   25,  100, 1},
    { {DATA_RANDOM,     10,10,     100,100},     100000, 1000,  100, 0},
    { {DATA_SEQUENTIAL, 10,10,     100,100},     100000, 1000,  100, 0},
  };

  int i;

  for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){
    char *zName = getName(zSystem, &aTest[i]);
    if( testCaseBegin(pRc, zPattern, "%s", zName) ){
      doDataTest1(zSystem, &aTest[i], pRc);
    }
    testFree(zName);
  }
}

void testCompareDb(
  Datasource *pData,
  int nData,
  int iSeed,
  TestDb *pControl,
  TestDb *pDb,
  int *pRc
){
  int i;

  static int nCall = 0;
  nCall++;

  testScanCompare(pControl, pDb, 0, 0, 0,         0, 0,         pRc);
  testScanCompare(pControl, pDb, 1, 0, 0,         0, 0,         pRc);

  if( *pRc==0 ){
    int iKey1;
    int iKey2;
    void *pKey1; int nKey1;       /* Start key */
    void *pKey2; int nKey2;       /* Final key */

    iKey1 = testPrngValue(iSeed) % nData;
    iKey2 = testPrngValue(iSeed+1) % nData;
    testDatasourceEntry(pData, iKey1, &pKey2, &nKey1, 0, 0);
    pKey1 = testMalloc(nKey1+1);
    memcpy(pKey1, pKey2, nKey1+1);
    testDatasourceEntry(pData, iKey2, &pKey2, &nKey2, 0, 0);

    testScanCompare(pControl, pDb, 0, 0, 0,         pKey2, nKey2, pRc);
    testScanCompare(pControl, pDb, 0, pKey1, nKey1, 0, 0,         pRc);
    testScanCompare(pControl, pDb, 0, pKey1, nKey1, pKey2, nKey2, pRc);
    testScanCompare(pControl, pDb, 1, 0, 0,         pKey2, nKey2, pRc);
    testScanCompare(pControl, pDb, 1, pKey1, nKey1, 0, 0,         pRc);
    testScanCompare(pControl, pDb, 1, pKey1, nKey1, pKey2, nKey2, pRc);
    testFree(pKey1);
  }

  for(i=0; i<nData && *pRc==0; i++){
    void *pKey; int nKey;
    testDatasourceEntry(pData, i, &pKey, &nKey, 0, 0);
    testFetchCompare(pControl, pDb, pKey, nKey, pRc);
  }
}

static void doDataTest2(
  const char *zSystem,            /* Database system to test */
  Datatest2 *p,                   /* Structure containing test parameters */
  int *pRc                        /* OUT: Error code */
){
  TestDb *pDb;
  TestDb *pControl;
  Datasource *pData;
  int i;
  int rc = LSM_OK;
  int iDot = 0;

  /* Start the test case, open a database and allocate the datasource. */
  pDb = testOpen(zSystem, 1, &rc);
  pData = testDatasourceNew(&p->defn);
  rc = testControlDb(&pControl);

  if( tdb_lsm(pDb) ){
    int nBuf = 32 * 1024 * 1024;
    lsm_config(tdb_lsm(pDb), LSM_CONFIG_AUTOFLUSH, &nBuf);
  }

  for(i=0; rc==0 && i<p->nIter; i++){
    void *pKey1; int nKey1;
    void *pKey2; int nKey2;
    int ii;
    int nRange = MIN(p->nIter*p->nWrite, p->nRange);

    for(ii=0; rc==0 && ii<p->nWrite; ii++){
      int iKey = (i*p->nWrite + ii) % p->nRange;
      testWriteDatasource(pControl, pData, iKey, &rc);
      testWriteDatasource(pDb, pData, iKey, &rc);
    }

    testDatasourceEntry(pData, i+1000000, &pKey1, &nKey1, 0, 0);
    pKey1 = testMallocCopy(pKey1, nKey1);
    testDatasourceEntry(pData, i+2000000, &pKey2, &nKey2, 0, 0);

    testDeleteRange(pDb, pKey1, nKey1, pKey2, nKey2, &rc);
    testDeleteRange(pControl, pKey1, nKey1, pKey2, nKey2, &rc);
    testFree(pKey1);

    testCompareDb(pData, nRange, i, pControl, pDb, &rc);
    testReopen(&pDb, &rc);
    testCompareDb(pData, nRange, i, pControl, pDb, &rc);

    /* Update the progress dots... */
    testCaseProgress(i, p->nIter, testCaseNDot(), &iDot);
  }

  testClose(&pDb);
  testClose(&pControl);
  testDatasourceFree(pData);
  testCaseFinish(rc);
  *pRc = rc;
}

static char *getName2(const char *zSystem, Datatest2 *pTest){
  char *zRet;
  char *zData;
  zData = testDatasourceName(&pTest->defn);
  zRet = testMallocPrintf("data2.%s.%s.%d.%d.%d", 
      zSystem, zData, pTest->nRange, pTest->nWrite, pTest->nIter
  );
  testFree(zData);
  return zRet;
}

void test_data_2(
  const char *zSystem,            /* Database system name */
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  Datatest2 aTest[] = {
      /* defn,                                 nRange, nWrite, nIter */
    { {DATA_RANDOM,     20,25,     100,200},   10000,  10,     50   },
    { {DATA_RANDOM,     20,25,     100,200},   10000,  200,    50   },
    { {DATA_RANDOM,     20,25,     100,200},   100,    10,     1000 },
    { {DATA_RANDOM,     20,25,     100,200},   100,    200,    50   },
  };

  int i;

  for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){
    char *zName = getName2(zSystem, &aTest[i]);
    if( testCaseBegin(pRc, zPattern, "%s", zName) ){
      doDataTest2(zSystem, &aTest[i], pRc);
    }
    testFree(zName);
  }
}

/*************************************************************************
** Test case data3.*
*/

typedef struct Datatest3 Datatest3;
struct Datatest3 {
  int nRange;                     /* Keys are between 1 and this value, incl. */
  int nIter;                      /* Number of iterations */
  int nWrite;                     /* Number of writes per iteration */
  int nDelete;                    /* Number of deletes per iteration */

  int nValMin;                    /* Minimum value size for writes */
  int nValMax;                    /* Maximum value size for writes */
};

void testPutU32(u8 *aBuf, u32 iVal){
  aBuf[0] = (iVal >> 24) & 0xFF;
  aBuf[1] = (iVal >> 16) & 0xFF;
  aBuf[2] = (iVal >>  8) & 0xFF;
  aBuf[3] = (iVal >>  0) & 0xFF;
}

void dt3PutKey(u8 *aBuf, int iKey){
  assert( iKey<100000 && iKey>=0 );
  sprintf((char *)aBuf, "%.5d", iKey);
}

static void doDataTest3(
  const char *zSystem,            /* Database system to test */
  Datatest3 *p,                   /* Structure containing test parameters */
  int *pRc                        /* OUT: Error code */
){
  int iDot = 0;
  int rc = *pRc;
  TestDb *pDb;
  u8 *abPresent;                  /* Array of boolean */
  char *aVal;                     /* Buffer to hold values */
  int i;
  u32 iSeq = 10;                  /* prng counter */

  abPresent = (u8 *)testMalloc(p->nRange+1);
  aVal = (char *)testMalloc(p->nValMax+1);
  pDb = testOpen(zSystem, 1, &rc);

  for(i=0; i<p->nIter && rc==0; i++){
    int ii;

    testCaseProgress(i, p->nIter, testCaseNDot(), &iDot);

    /* Perform nWrite inserts */
    for(ii=0; ii<p->nWrite; ii++){
      u8 aKey[6];
      u32 iKey;
      int nVal;

      iKey = (testPrngValue(iSeq++) % p->nRange) + 1;
      nVal = (testPrngValue(iSeq++) % (p->nValMax - p->nValMin)) + p->nValMin;
      testPrngString(testPrngValue(iSeq++), aVal, nVal);
      dt3PutKey(aKey, iKey);

      testWrite(pDb, aKey, sizeof(aKey)-1, aVal, nVal, &rc);
      abPresent[iKey] = 1;
    }

    /* Perform nDelete deletes */
    for(ii=0; ii<p->nDelete; ii++){
      u8 aKey1[6];
      u8 aKey2[6];
      u32 iKey;

      iKey = (testPrngValue(iSeq++) % p->nRange) + 1;
      dt3PutKey(aKey1, iKey-1);
      dt3PutKey(aKey2, iKey+1);

      testDeleteRange(pDb, aKey1, sizeof(aKey1)-1, aKey2, sizeof(aKey2)-1, &rc);
      abPresent[iKey] = 0;
    }

    testReopen(&pDb, &rc);

    for(ii=1; rc==0 && ii<=p->nRange; ii++){
      int nDbVal;
      void *pDbVal;
      u8 aKey[6];
      int dbrc;

      dt3PutKey(aKey, ii);
      dbrc = tdb_fetch(pDb, aKey, sizeof(aKey)-1, &pDbVal, &nDbVal);
      testCompareInt(0, dbrc, &rc);

      if( abPresent[ii] ){
        testCompareInt(1, (nDbVal>0), &rc);
      }else{
        testCompareInt(1, (nDbVal<0), &rc);
      }
    }
  }

  testClose(&pDb);
  testCaseFinish(rc);
  *pRc = rc;
}

static char *getName3(const char *zSystem, Datatest3 *p){
  return testMallocPrintf("data3.%s.%d.%d.%d.%d.(%d..%d)",
      zSystem, p->nRange, p->nIter, p->nWrite, p->nDelete, 
      p->nValMin, p->nValMax
  );
}

void test_data_3(
  const char *zSystem,            /* Database system name */
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  Datatest3 aTest[] = {
    /* nRange, nIter, nWrite, nDelete, nValMin, nValMax */
    {  100,    1000,  5,      5,       50,      100 },
    {  100,    1000,  2,      2,        5,       10 },
  };

  int i;

  for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){
    char *zName = getName3(zSystem, &aTest[i]);
    if( testCaseBegin(pRc, zPattern, "%s", zName) ){
      doDataTest3(zSystem, &aTest[i], pRc);
    }
    testFree(zName);
  }
}

/*
** This file contains tests related to recovery following application 
** and system crashes (power failures) while writing to the database.
*/

#include "lsmtest.h"

/*
** Structure used by testCksumDatabase() to accumulate checksum values in.
*/
typedef struct Cksum Cksum;
struct Cksum {
  int nRow;
  int cksum1;
  int cksum2;
};

/*
** tdb_scan() callback used by testCksumDatabase()
*/
static void scanCksumDb(
  void *pCtx, 
  void *pKey, int nKey,
  void *pVal, int nVal
){
  Cksum *p = (Cksum *)pCtx;
  int i;

  p->nRow++;
  for(i=0; i<nKey; i++){
    p->cksum1 += ((u8 *)pKey)[i];
    p->cksum2 += p->cksum1;
  }
  for(i=0; i<nVal; i++){
    p->cksum1 += ((u8 *)pVal)[i];
    p->cksum2 += p->cksum1;
  }
}

/*
** tdb_scan() callback used by testCountDatabase()
*/
static void scanCountDb(
  void *pCtx, 
  void *pKey, int nKey,
  void *pVal, int nVal
){
  Cksum *p = (Cksum *)pCtx;
  p->nRow++;

  unused_parameter(pKey);
  unused_parameter(nKey);
  unused_parameter(pVal);
  unused_parameter(nVal);
}


/*
** Iterate through the entire contents of database pDb. Write a checksum
** string based on the db contents into buffer zOut before returning. A
** checksum string is at most 29 (TEST_CKSUM_BYTES) bytes in size:
**
**    * 32-bit integer (10 bytes)
**    * 1 space        (1 byte)
**    * 32-bit hex     (8 bytes)
**    * 1 space        (1 byte)
**    * 32-bit hex     (8 bytes)
**    * nul-terminator (1 byte)
**
** The number of entries in the database is returned.
*/
int testCksumDatabase(
  TestDb *pDb,                    /* Database handle */
  char *zOut                      /* Buffer to write checksum to */
){
  Cksum cksum;
  memset(&cksum, 0, sizeof(Cksum));
  tdb_scan(pDb, (void *)&cksum, 0, 0, 0, 0, 0, scanCksumDb);
  sprintf(zOut, "%d %x %x", 
      cksum.nRow, (u32)cksum.cksum1, (u32)cksum.cksum2
  );
  assert( strlen(zOut)<TEST_CKSUM_BYTES );
  return cksum.nRow;
}

int testCountDatabase(TestDb *pDb){
  Cksum cksum;
  memset(&cksum, 0, sizeof(Cksum));
  tdb_scan(pDb, (void *)&cksum, 0, 0, 0, 0, 0, scanCountDb);
  return cksum.nRow;
}

/*
** This function is a no-op if *pRc is not 0 when it is called.
**
** Otherwise, the two nul-terminated strings z1 and z1 are compared. If
** they are the same, the function returns without doing anything. Otherwise,
** an error message is printed, *pRc is set to 1 and the test_failed()
** function called.
*/
void testCompareStr(const char *z1, const char *z2, int *pRc){
  if( *pRc==0 ){
    if( strcmp(z1, z2) ){
      testPrintError("testCompareStr: \"%s\" != \"%s\"\n", z1, z2);
      *pRc = 1;
      test_failed();
    }
  }
}

/*
** This function is a no-op if *pRc is not 0 when it is called.
**
** Otherwise, the two integers i1 and i2 are compared. If they are equal,
** the function returns without doing anything. Otherwise, an error message 
** is printed, *pRc is set to 1 and the test_failed() function called.
*/
void testCompareInt(int i1, int i2, int *pRc){
  if( *pRc==0 && i1!=i2 ){
    testPrintError("testCompareInt: %d != %d\n", i1, i2);
    *pRc = 1;
    test_failed();
  }
}

void testCaseStart(int *pRc, char *zFmt, ...){
  va_list ap;
  va_start(ap, zFmt);
  vprintf(zFmt, ap);
  printf(" ...");
  va_end(ap);
  *pRc = 0;
  fflush(stdout);
}

/*
** This function is a no-op if *pRc is non-zero when it is called. Zero
** is returned in this case.
**
** Otherwise, the zFmt (a printf style format string) and following arguments 
** are used to create a test case name. If zPattern is NULL or a glob pattern
** that matches the test case name, 1 is returned and the test case started.
** Otherwise, zero is returned and the test case does not start.
*/
int testCaseBegin(int *pRc, const char *zPattern, const char *zFmt, ...){
  int res = 0;
  if( *pRc==0 ){
    char *zTest;
    va_list ap;

    va_start(ap, zFmt);
    zTest = testMallocVPrintf(zFmt, ap);
    va_end(ap);
    if( zPattern==0 || testGlobMatch(zPattern, zTest) ){
      printf("%-50s ...", zTest);
      res = 1;
    }
    testFree(zTest);
    fflush(stdout);
  }

  return res;
}

void testCaseFinish(int rc){
  if( rc==0 ){
    printf("Ok\n");
  }else{
    printf("FAILED\n");
  }
  fflush(stdout);
}

void testCaseSkip(){
  printf("Skipped\n");
}

void testSetupSavedLsmdb(
  const char *zCfg,
  const char *zFile,
  Datasource *pData,
  int nRow,
  int *pRc
){
  if( *pRc==0 ){
    int rc;
    TestDb *pDb;
    rc = tdb_lsm_open(zCfg, zFile, 1, &pDb);
    if( rc==0 ){
      testWriteDatasourceRange(pDb, pData, 0, nRow, &rc);
      testClose(&pDb);
      if( rc==0 ) testSaveDb(zFile, "log");
    }
    *pRc = rc;
  }
}

/*
** This function is a no-op if *pRc is non-zero when it is called.
**
** Open the LSM database identified by zFile and compute its checksum
** (a string, as returned by testCksumDatabase()). If the checksum is
** identical to zExpect1 or, if it is not NULL, zExpect2, the test passes.
** Otherwise, print an error message and set *pRc to 1.
*/
static void testCompareCksumLsmdb(
  const char *zFile,              /* Path to LSM database */
  int bCompress,                  /* True if db is compressed */
  const char *zExpect1,           /* Expected checksum 1 */
  const char *zExpect2,           /* Expected checksum 2 (or NULL) */
  int *pRc                        /* IN/OUT: Test case error code */
){
  if( *pRc==0 ){
    char zCksum[TEST_CKSUM_BYTES];
    TestDb *pDb;

    *pRc = tdb_lsm_open((bCompress?"compression=1 mmap=0":""), zFile, 0, &pDb);
    testCksumDatabase(pDb, zCksum);
    testClose(&pDb);

    if( *pRc==0 ){
      int r1 = 0;
      int r2 = -1;

      r1 = strcmp(zCksum, zExpect1);
      if( zExpect2 ) r2 = strcmp(zCksum, zExpect2);
      if( r1 && r2 ){
        if( zExpect2 ){
          testPrintError("testCompareCksumLsmdb: \"%s\" != (\"%s\" OR \"%s\")",
              zCksum, zExpect1, zExpect2
          );
        }else{
          testPrintError("testCompareCksumLsmdb: \"%s\" != \"%s\"",
              zCksum, zExpect1
          );
        }
        *pRc = 1;
        test_failed();
      }
    }
  }
}

static void testCompareCksumBtdb(
  const char *zFile,              /* Path to LSM database */
  const char *zExpect1,           /* Expected checksum 1 */
  const char *zExpect2,           /* Expected checksum 2 (or NULL) */
  int *pRc                        /* IN/OUT: Test case error code */
){
  if( *pRc==0 ){
    char zCksum[TEST_CKSUM_BYTES];
    TestDb *pDb;

    *pRc = tdb_open("bt", zFile, 0, &pDb);
    testCksumDatabase(pDb, zCksum);
    testClose(&pDb);

    if( *pRc==0 ){
      int r1 = 0;
      int r2 = -1;

      r1 = strcmp(zCksum, zExpect1);
      if( zExpect2 ) r2 = strcmp(zCksum, zExpect2);
      if( r1 && r2 ){
        if( zExpect2 ){
          testPrintError("testCompareCksumLsmdb: \"%s\" != (\"%s\" OR \"%s\")",
              zCksum, zExpect1, zExpect2
          );
        }else{
          testPrintError("testCompareCksumLsmdb: \"%s\" != \"%s\"",
              zCksum, zExpect1
          );
        }
        *pRc = 1;
        test_failed();
      }
    }
  }
}

/* Above this point are reusable test routines. Not clear that they
** should really be in this file.
*************************************************************************/

/*
** This test verifies that if a system crash occurs while doing merge work
** on the db, no data is lost.
*/
static void crash_test1(int bCompress, int *pRc){
  const char *DBNAME = "testdb.lsm";
  const DatasourceDefn defn = {TEST_DATASOURCE_RANDOM, 12, 16, 200, 200};

  const int nRow = 5000;          /* Database size */
  const int nIter = 200;          /* Number of test iterations */
  const int nWork = 20;           /* Maximum lsm_work() calls per iteration */
  const int nPage = 15;           /* Pages per lsm_work call */

  int i;
  int iDot = 0;
  Datasource *pData;
  CksumDb *pCksumDb;
  TestDb *pDb;
  char *zCfg;

  const char *azConfig[2] = {
    "page_size=1024 block_size=65536 autoflush=16384 safety=2 mmap=0", 
    "page_size=1024 block_size=65536 autoflush=16384 safety=2 "
    " compression=1 mmap=0"
  };
  assert( bCompress==0 || bCompress==1 );

  /* Allocate datasource. And calculate the expected checksums. */
  pData = testDatasourceNew(&defn);
  pCksumDb = testCksumArrayNew(pData, nRow, nRow, 1);

  /* Setup and save the initial database. */

  zCfg = testMallocPrintf("%s automerge=7", azConfig[bCompress]);
  testSetupSavedLsmdb(zCfg, DBNAME, pData, 5000, pRc);
  testFree(zCfg);

  for(i=0; i<nIter && *pRc==0; i++){
    int iWork;
    int testrc = 0;

    testCaseProgress(i, nIter, testCaseNDot(), &iDot);

    /* Restore and open the database. */
    testRestoreDb(DBNAME, "log");
    testrc = tdb_lsm_open(azConfig[bCompress], DBNAME, 0, &pDb);
    assert( testrc==0 );

    /* Call lsm_work() on the db */
    tdb_lsm_prepare_sync_crash(pDb, 1 + (i%(nWork*2)));
    for(iWork=0; testrc==0 && iWork<nWork; iWork++){
      int nWrite = 0;
      lsm_db *db = tdb_lsm(pDb);
      testrc = lsm_work(db, 0, nPage, &nWrite);
      assert( testrc!=0 || nWrite>0 );
      if( testrc==0 ) testrc = lsm_checkpoint(db, 0);
    }
    tdb_close(pDb);

    /* Check that the database content is still correct */
    testCompareCksumLsmdb(DBNAME, 
        bCompress, testCksumArrayGet(pCksumDb, nRow), 0, pRc);
  }

  testCksumArrayFree(pCksumDb);
  testDatasourceFree(pData);
}

/*
** This test verifies that if a system crash occurs while committing a
** transaction to the log file, no earlier transactions are lost or damaged.
*/
static void crash_test2(int bCompress, int *pRc){
  const char *DBNAME = "testdb.lsm";
  const DatasourceDefn defn = {TEST_DATASOURCE_RANDOM, 12, 16, 1000, 1000};

  const int nIter = 200;
  const int nInsert = 20;

  int i;
  int iDot = 0;
  Datasource *pData;
  CksumDb *pCksumDb;
  TestDb *pDb;

  /* Allocate datasource. And calculate the expected checksums. */
  pData = testDatasourceNew(&defn);
  pCksumDb = testCksumArrayNew(pData, 100, 100+nInsert, 1);

  /* Setup and save the initial database. */
  testSetupSavedLsmdb("", DBNAME, pData, 100, pRc);

  for(i=0; i<nIter && *pRc==0; i++){
    int iIns;
    int testrc = 0;

    testCaseProgress(i, nIter, testCaseNDot(), &iDot);

    /* Restore and open the database. */
    testRestoreDb(DBNAME, "log");
    testrc = tdb_lsm_open("safety=2", DBNAME, 0, &pDb);
    assert( testrc==0 );

    /* Insert nInsert records into the database. Crash midway through. */
    tdb_lsm_prepare_sync_crash(pDb, 1 + (i%(nInsert+2)));
    for(iIns=0; iIns<nInsert; iIns++){
      void *pKey; int nKey;
      void *pVal; int nVal;

      testDatasourceEntry(pData, 100+iIns, &pKey, &nKey, &pVal, &nVal);
      testrc = tdb_write(pDb, pKey, nKey, pVal, nVal);
      if( testrc ) break;
    }
    tdb_close(pDb);

    /* Check that no data was lost when the system crashed. */
    testCompareCksumLsmdb(DBNAME, bCompress,
      testCksumArrayGet(pCksumDb, 100 + iIns),
      testCksumArrayGet(pCksumDb, 100 + iIns + 1),
      pRc
    );
  }

  testDatasourceFree(pData);
  testCksumArrayFree(pCksumDb);
}


/*
** This test verifies that if a system crash occurs when checkpointing
** the database, data is not lost (assuming that any writes not synced
** to the db have been synced into the log file).
*/
static void crash_test3(int bCompress, int *pRc){
  const char *DBNAME = "testdb.lsm";
  const int nIter = 100;
  const DatasourceDefn defn = {TEST_DATASOURCE_RANDOM, 12, 16, 1000, 1000};

  int i;
  int iDot = 0;
  Datasource *pData;
  CksumDb *pCksumDb;
  TestDb *pDb;

  /* Allocate datasource. And calculate the expected checksums. */
  pData = testDatasourceNew(&defn);
  pCksumDb = testCksumArrayNew(pData, 110, 150, 10);

  /* Setup and save the initial database. */
  testSetupSavedLsmdb("", DBNAME, pData, 100, pRc);

  for(i=0; i<nIter && *pRc==0; i++){
    int iOpen;
    testCaseProgress(i, nIter, testCaseNDot(), &iDot);
    testRestoreDb(DBNAME, "log");

    for(iOpen=0; iOpen<5; iOpen++){
      /* Open the database. Insert 10 more records. */
      pDb = testOpen("lsm", 0, pRc);
      testWriteDatasourceRange(pDb, pData, 100+iOpen*10, 10, pRc);

      /* Schedule a crash simulation then close the db. */
      tdb_lsm_prepare_sync_crash(pDb, 1 + (i%2));
      tdb_close(pDb);

      /* Open the database and check that the crash did not cause any
      ** data loss.  */
      testCompareCksumLsmdb(DBNAME, bCompress,
        testCksumArrayGet(pCksumDb, 110 + iOpen*10), 0,
        pRc
      );
    }
  }

  testDatasourceFree(pData);
  testCksumArrayFree(pCksumDb);
}

void do_crash_test(const char *zPattern, int *pRc){
  struct Test {
    const char *zTest;
    void (*x)(int, int *);
    int bCompress;
  } aTest [] = {
    { "crash.lsm.1",     crash_test1, 0 },
    { "crash.lsm_zip.1", crash_test1, 1 },
    { "crash.lsm.2",     crash_test2, 0 },
    { "crash.lsm.3",     crash_test3, 0 },
  };
  int i;

  for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){
    struct Test *p = &aTest[i];
    if( testCaseBegin(pRc, zPattern, "%s", p->zTest) ){
      p->x(p->bCompress, pRc);
      testCaseFinish(*pRc);
    }
  }
}

/*
** This file contains tests related to the explicit rollback of database
** transactions and sub-transactions.
*/


/*
** Repeat 2000 times (until the db contains 100,000 entries):
**
**   1. Open a transaction and insert 500 rows, opening a nested 
**      sub-transaction each 100 rows.
**
**   2. Roll back to each sub-transaction savepoint. Check the database
**      checksum looks Ok.
**
**   3. Every second iteration, roll back the main transaction. Check the
**      db checksum is correct. Every other iteration, commit the main
**      transaction (increasing the size of the db by 100 rows).
*/


#include "lsmtest.h"

struct CksumDb {
  int nFirst;
  int nLast;
  int nStep;
  char **azCksum;
};

CksumDb *testCksumArrayNew(
  Datasource *pData, 
  int nFirst, 
  int nLast, 
  int nStep
){
  TestDb *pDb;
  CksumDb *pRet;
  int i;
  int nEntry;
  int rc = 0;

  assert( nLast>=nFirst && ((nLast-nFirst)%nStep)==0 );
 
  pRet = malloc(sizeof(CksumDb));
  memset(pRet, 0, sizeof(CksumDb));
  pRet->nFirst = nFirst;
  pRet->nLast = nLast;
  pRet->nStep = nStep;
  nEntry = 1 + ((nLast - nFirst) / nStep);

  /* Allocate space so that azCksum is an array of nEntry pointers to
  ** buffers each TEST_CKSUM_BYTES in size.  */
  pRet->azCksum = (char **)malloc(nEntry * (sizeof(char *) + TEST_CKSUM_BYTES));
  for(i=0; i<nEntry; i++){
    char *pStart = (char *)(&pRet->azCksum[nEntry]);
    pRet->azCksum[i] = &pStart[i * TEST_CKSUM_BYTES];
  }

  tdb_open("lsm", "tempdb.lsm", 1, &pDb);
  testWriteDatasourceRange(pDb, pData, 0, nFirst, &rc);
  for(i=0; i<nEntry; i++){
    testCksumDatabase(pDb, pRet->azCksum[i]);
    if( i==nEntry ) break;
    testWriteDatasourceRange(pDb, pData, nFirst+i*nStep, nStep, &rc);
  }

  tdb_close(pDb);

  return pRet;
}

char *testCksumArrayGet(CksumDb *p, int nRow){
  int i;
  assert( nRow>=p->nFirst );
  assert( nRow<=p->nLast );
  assert( ((nRow-p->nFirst) % p->nStep)==0 );

  i = (nRow - p->nFirst) / p->nStep;
  return p->azCksum[i];
}

void testCksumArrayFree(CksumDb *p){
  free(p->azCksum);
  memset(p, 0x55, sizeof(*p));
  free(p);
}

/* End of CksumDb code.
**************************************************************************/

/*
** Test utility function. Write key-value pair $i from datasource pData 
** into database pDb.
*/
void testWriteDatasource(TestDb *pDb, Datasource *pData, int i, int *pRc){
  void *pKey; int nKey;
  void *pVal; int nVal;
  testDatasourceEntry(pData, i, &pKey, &nKey, &pVal, &nVal);
  testWrite(pDb, pKey, nKey, pVal, nVal, pRc);
}

/*
** Test utility function. Delete datasource pData key $i from database pDb.
*/
void testDeleteDatasource(TestDb *pDb, Datasource *pData, int i, int *pRc){
  void *pKey; int nKey;
  testDatasourceEntry(pData, i, &pKey, &nKey, 0, 0);
  testDelete(pDb, pKey, nKey, pRc);
}

/*
** This function inserts nWrite key/value pairs into database pDb - the
** nWrite key value pairs starting at iFirst from data source pData.
*/
void testWriteDatasourceRange(
  TestDb *pDb,                    /* Database to write to */
  Datasource *pData,              /* Data source to read values from */
  int iFirst,                     /* Index of first key/value pair */
  int nWrite,                     /* Number of key/value pairs to write */
  int *pRc                        /* IN/OUT: Error code */
){
  int i;
  for(i=0; i<nWrite; i++){
    testWriteDatasource(pDb, pData, iFirst+i, pRc);
  }
}

void testDeleteDatasourceRange(
  TestDb *pDb,                    /* Database to write to */
  Datasource *pData,              /* Data source to read keys from */
  int iFirst,                     /* Index of first key */
  int nWrite,                     /* Number of keys to delete */
  int *pRc                        /* IN/OUT: Error code */
){
  int i;
  for(i=0; i<nWrite; i++){
    testDeleteDatasource(pDb, pData, iFirst+i, pRc);
  }
}

static char *getName(const char *zSystem){ 
  char *zRet; 
  zRet = testMallocPrintf("rollback.%s", zSystem);
  return zRet;
}

static int rollback_test_1(
  const char *zSystem,
  Datasource *pData
){
  const int nRepeat = 100;

  TestDb *pDb;
  int rc;
  int i;
  CksumDb *pCksum;
  char *zName;

  zName = getName(zSystem);
  testCaseStart(&rc, zName);
  testFree(zName);

  pCksum = testCksumArrayNew(pData, 0, nRepeat*100, 100);
  pDb = 0;
  rc = tdb_open(zSystem, 0, 1, &pDb);
  if( pDb && tdb_transaction_support(pDb)==0 ){
    testCaseSkip();
    goto skip_rollback_test;
  }

  for(i=0; i<nRepeat && rc==0; i++){
    char zCksum[TEST_CKSUM_BYTES];
    int nCurrent = (((i+1)/2) * 100);
    int nDbRow;
    int iTrans;

    /* Check that the database is the expected size. */
    nDbRow = testCountDatabase(pDb);
    testCompareInt(nCurrent, nDbRow, &rc);

    for(iTrans=2; iTrans<=6 && rc==0; iTrans++){
      tdb_begin(pDb, iTrans);
      testWriteDatasourceRange(pDb, pData, nCurrent, 100, &rc);
      nCurrent += 100;
    }

    testCksumDatabase(pDb, zCksum);
    testCompareStr(zCksum, testCksumArrayGet(pCksum, nCurrent), &rc);

    for(iTrans=6; iTrans>2 && rc==0; iTrans--){
      tdb_rollback(pDb, iTrans);
      nCurrent -= 100;
      testCksumDatabase(pDb, zCksum);
      testCompareStr(zCksum, testCksumArrayGet(pCksum, nCurrent), &rc);
    }

    if( i%2 ){
      tdb_rollback(pDb, 0);
      nCurrent -= 100;
      testCksumDatabase(pDb, zCksum);
      testCompareStr(zCksum, testCksumArrayGet(pCksum, nCurrent), &rc);
    }else{
      tdb_commit(pDb, 0);
    }
  }
  testCaseFinish(rc);

 skip_rollback_test:
  tdb_close(pDb);
  testCksumArrayFree(pCksum);
  return rc;
}

void test_rollback(
  const char *zSystem, 
  const char *zPattern, 
  int *pRc
){
  if( *pRc==0 ){
    int bRun = 1;

    if( zPattern ){
      char *zName = getName(zSystem);
      bRun = testGlobMatch(zPattern, zName);
      testFree(zName);
    }

    if( bRun ){
      DatasourceDefn defn = { TEST_DATASOURCE_RANDOM, 10, 15, 50, 100 };
      Datasource *pData = testDatasourceNew(&defn);
      *pRc = rollback_test_1(zSystem, pData);
      testDatasourceFree(pData);
    }
  }
}

/*
** This file contains test cases involving multiple database clients.
*/

#include "lsmtest.h"

/*
** The following code implements test cases "mc1.*".
**
** This test case uses one writer and $nReader readers. All connections
** are driven by a single thread. All connections are opened at the start
** of the test and remain open until the test is finished.
**
** The test consists of $nStep steps. Each step the following is performed:
**
**   1. The writer inserts $nWriteStep records into the db.
**
**   2. The writer checks that the contents of the db are as expected.
**
**   3. Each reader that currently has an open read transaction also checks
**      that the contents of the db are as expected (according to the snapshot
**      the read transaction is reading - see below).
**
** After step 1, reader 1 opens a read transaction. After step 2, reader
** 2 opens a read transaction, and so on. At step ($nReader+1), reader 1
** closes the current read transaction and opens a new one. And so on.
** The result is that at step N (for N > $nReader), there exists a reader
** with an open read transaction reading the snapshot committed following
** steps (N-$nReader-1) to N. 
*/
typedef struct Mctest Mctest;
struct Mctest {
  DatasourceDefn defn;            /* Datasource to use */
  int nStep;                      /* Total number of steps in test */
  int nWriteStep;                 /* Number of rows to insert each step */
  int nReader;                    /* Number of read connections */
};
static void do_mc_test(
  const char *zSystem,            /* Database system to test */
  Mctest *pTest,
  int *pRc                        /* IN/OUT: return code */
){
  const int nDomain = pTest->nStep * pTest->nWriteStep;
  Datasource *pData;              /* Source of data */
  TestDb *pDb;                    /* First database connection (writer) */
  int iReader;                    /* Used to iterate through aReader */
  int iStep;                      /* Current step in test */
  int iDot = 0;                   /* Current step in test */

  /* Array of reader connections */
  struct Reader {
    TestDb *pDb;                  /* Connection handle */
    int iLast;                    /* Current snapshot contains keys 0..iLast */
  } *aReader;

  /* Create a data source */
  pData = testDatasourceNew(&pTest->defn);

  /* Open the writer connection */
  pDb = testOpen(zSystem, 1, pRc);

  /* Allocate aReader */
  aReader = (struct Reader *)testMalloc(sizeof(aReader[0]) * pTest->nReader);
  for(iReader=0; iReader<pTest->nReader; iReader++){
    aReader[iReader].pDb = testOpen(zSystem, 0, pRc);
  }

  for(iStep=0; iStep<pTest->nStep; iStep++){
    int iLast;
    int iBegin;                   /* Start read trans using aReader[iBegin] */

    /* Insert nWriteStep more records into the database */
    int iFirst = iStep*pTest->nWriteStep;
    testWriteDatasourceRange(pDb, pData, iFirst, pTest->nWriteStep, pRc);

    /* Check that the db is Ok according to the writer */
    iLast = (iStep+1) * pTest->nWriteStep - 1;
    testDbContents(pDb, pData, nDomain, 0, iLast, iLast, 1, pRc);

    /* Have reader (iStep % nReader) open a read transaction here. */
    iBegin = (iStep % pTest->nReader);
    if( iBegin<iStep ) tdb_commit(aReader[iBegin].pDb, 0);
    tdb_begin(aReader[iBegin].pDb, 1);
    aReader[iBegin].iLast = iLast;

    /* Check that the db is Ok for each open reader */
    for(iReader=0; iReader<pTest->nReader && aReader[iReader].iLast; iReader++){
      iLast = aReader[iReader].iLast;
      testDbContents(
          aReader[iReader].pDb, pData, nDomain, 0, iLast, iLast, 1, pRc
      );
    }

    /* Report progress */
    testCaseProgress(iStep, pTest->nStep, testCaseNDot(), &iDot);
  }

  /* Close all readers */
  for(iReader=0; iReader<pTest->nReader; iReader++){
    testClose(&aReader[iReader].pDb);
  }
  testFree(aReader);

  /* Close the writer-connection and free the datasource */
  testClose(&pDb);
  testDatasourceFree(pData);
}


void test_mc(
  const char *zSystem,            /* Database system name */
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  int i;
  Mctest aTest[] = {
    { { TEST_DATASOURCE_RANDOM, 10,10, 100,100 }, 100, 10, 5 },
  };

  for(i=0; i<ArraySize(aTest); i++){
    if( testCaseBegin(pRc, zPattern, "mc1.%s.%d", zSystem, i) ){
      do_mc_test(zSystem, &aTest[i], pRc);
      testCaseFinish(*pRc);
    }
  }
}

/*
** This file is broken into three semi-autonomous parts:
**
**   1. The database functions.
**   2. The thread wrappers.
**   3. The implementation of the mt1.* tests.
*/

/*************************************************************************
** DATABASE CONTENTS:
**
**   The database contains up to N key/value pairs, where N is some large 
**   number (say 10,000,000). Keys are integer values between 0 and (N-1).
**   The value associated with each key is a pseudo-random blob of data.
**
**   Key/value pair keys are encoded as the two bytes "k." followed by a 
**   10-digit decimal number. i.e. key 45 -> "k.0000000045".
**
**   As well as the key/value pairs, the database also contains checksum 
**   entries. The checksums form a hierarchy - for every F key/value
**   entries there is one level 1 checksum. And for each F level 1 checksums
**   there is one level 2 checksum. And so on.
**
**   Checksum keys are encoded as the two byte "c." followed by the 
**   checksum level, followed by a 10 digit decimal number containing
**   the value of the first key that contributes to the checksum value.
**   For example, assuming F==10, the level 1 checksum that spans keys
**   10 to 19 is "c.1.0000000010".
**
**   Clients may perform one of two operations on the database: a read
**   or a write.
** 
** READ OPERATIONS:
**
**   A read operation scans a range of F key/value pairs. It computes
**   the expected checksum and then compares the computed value to the
**   actual value stored in the level 1 checksum entry. It then scans 
**   the group of F level 1 checksums, and compares the computed checksum 
**   to the associated level 2 checksum value, and so on until the 
**   highest level checksum value has been verified.
**
**   If a checksum ever fails to match the expected value, the test 
**   has failed.
**
** WRITE OPERATIONS:
**
**   A write operation involves writing (possibly clobbering) a single
**   key/value pair. The associated level 1 checksum is then recalculated
**   updated. Then the level 2 checksum, and so on until the highest
**   level checksum has been modified.
**
**   All updates occur inside a single transaction.
**
** INTERFACE:
**
**   The interface used by test cases to read and write the db consists
**   of type DbParameters and the following functions:
**
**       dbReadOperation()
**       dbWriteOperation()
*/

#include "lsmtest.h"

typedef struct DbParameters DbParameters;
struct DbParameters {
  int nFanout;                    /* Checksum fanout (F) */
  int nKey;                       /* Size of key space (N) */
};

#define DB_KEY_BYTES          (2+5+10+1)

/*
** Argument aBuf[] must point to a buffer at least DB_KEY_BYTES in size.
** This function populates the buffer with a nul-terminated key string 
** corresponding to key iKey.
*/
static void dbFormatKey(
  DbParameters *pParam,
  int iLevel,
  int iKey,                       /* Key value */
  char *aBuf                      /* Write key string here */
){
  if( iLevel==0 ){
    snprintf(aBuf, DB_KEY_BYTES, "k.%.10d", iKey);
  }else{
    int f = 1;
    int i;
    for(i=0; i<iLevel; i++) f = f * pParam->nFanout;
    snprintf(aBuf, DB_KEY_BYTES, "c.%d.%.10d", iLevel, f*(iKey/f));
  }
}

/*
** Argument aBuf[] must point to a buffer at least DB_KEY_BYTES in size.
** This function populates the buffer with the string representation of
** checksum value iVal.
*/
static void dbFormatCksumValue(u32 iVal, char *aBuf){
  snprintf(aBuf, DB_KEY_BYTES, "%.10u", iVal);
}

/*
** Return the highest level of checksum in the database described
** by *pParam.
*/
static int dbMaxLevel(DbParameters *pParam){
  int iMax;
  int n = 1;
  for(iMax=0; n<pParam->nKey; iMax++){
    n = n * pParam->nFanout;
  }
  return iMax;
}

static void dbCksum(
  void *pCtx,                     /* IN/OUT: Pointer to u32 containing cksum */
  void *pKey, int nKey,           /* Database key. Unused. */
  void *pVal, int nVal            /* Database value. Checksum this. */
){
  u8 *aVal = (u8 *)pVal;
  u32 *pCksum = (u32 *)pCtx;
  u32 cksum = *pCksum;
  int i;

  unused_parameter(pKey);
  unused_parameter(nKey);

  for(i=0; i<nVal; i++){
    cksum += (cksum<<3) + (int)aVal[i];
  }

  *pCksum = cksum;
}

/*
** Compute the value of the checksum stored on level iLevel that contains
** data from key iKey by scanning the pParam->nFanout entries at level 
** iLevel-1.
*/
static u32 dbComputeCksum(
  DbParameters *pParam,           /* Database parameters */
  TestDb *pDb,                    /* Database connection handle */
  int iLevel,                     /* Level of checksum to compute */
  int iKey,                       /* Compute checksum for this key */
  int *pRc                        /* IN/OUT: Error code */
){
  u32 cksum = 0;
  if( *pRc==0 ){
    int nFirst;
    int nLast;
    int iFirst = 0;
    int iLast = 0;
    int i;
    int f = 1;
    char zFirst[DB_KEY_BYTES];
    char zLast[DB_KEY_BYTES];

    assert( iLevel>=1 );
    for(i=0; i<iLevel; i++) f = f * pParam->nFanout;

    iFirst = f*(iKey/f);
    iLast = iFirst + f - 1;
    dbFormatKey(pParam, iLevel-1, iFirst, zFirst);
    dbFormatKey(pParam, iLevel-1, iLast, zLast);
    nFirst = strlen(zFirst);
    nLast = strlen(zLast);

    *pRc = tdb_scan(pDb, (u32*)&cksum, 0, zFirst, nFirst, zLast, nLast,dbCksum);
  }

  return cksum;
}

static void dbReadOperation(
  DbParameters *pParam,           /* Database parameters */
  TestDb *pDb,                    /* Database connection handle */
  void (*xDelay)(void *),
  void *pDelayCtx,
  int iKey,                       /* Key to read */
  int *pRc                        /* IN/OUT: Error code */
){
  const int iMax = dbMaxLevel(pParam);
  int i;

  if( tdb_transaction_support(pDb) ) testBegin(pDb, 1, pRc);
  for(i=1; *pRc==0 && i<=iMax; i++){
    char zCksum[DB_KEY_BYTES];
    char zKey[DB_KEY_BYTES];
    u32 iCksum = 0;

    iCksum = dbComputeCksum(pParam, pDb, i, iKey, pRc);
    if( iCksum ){
      if( xDelay && i==1 ) xDelay(pDelayCtx);
      dbFormatCksumValue(iCksum, zCksum);
      dbFormatKey(pParam, i, iKey, zKey);
      testFetchStr(pDb, zKey, zCksum, pRc);
    }
  }
  if( tdb_transaction_support(pDb) ) testCommit(pDb, 0, pRc);
}

static int dbWriteOperation(
  DbParameters *pParam,           /* Database parameters */
  TestDb *pDb,                    /* Database connection handle */
  int iKey,                       /* Key to write to */
  const char *zValue,             /* Nul-terminated value to write */
  int *pRc                        /* IN/OUT: Error code */
){
  const int iMax = dbMaxLevel(pParam);
  char zKey[DB_KEY_BYTES];
  int i;
  int rc;

  assert( iKey>=0 && iKey<pParam->nKey );
  dbFormatKey(pParam, 0, iKey, zKey);

  /* Open a write transaction. This may fail - SQLITE4_BUSY */
  if( *pRc==0 && tdb_transaction_support(pDb) ){
    rc = tdb_begin(pDb, 2);
    if( rc==5 ) return 0;
    *pRc = rc;
  }

  testWriteStr(pDb, zKey, zValue, pRc);
  for(i=1; i<=iMax; i++){
    char zCksum[DB_KEY_BYTES];
    u32 iCksum = 0;

    iCksum = dbComputeCksum(pParam, pDb, i, iKey, pRc);
    dbFormatCksumValue(iCksum, zCksum);
    dbFormatKey(pParam, i, iKey, zKey);
    testWriteStr(pDb, zKey, zCksum, pRc);
  }
  if( tdb_transaction_support(pDb) ) testCommit(pDb, 0, pRc);
  return 1;
}

/*************************************************************************
** The following block contains testXXX() functions that implement a
** wrapper around the systems native multi-thread support. There are no
** synchronization primitives - just functions to launch and join 
** threads. Wrapper functions are:
**
**    testThreadSupport()
**
**    testThreadInit()
**    testThreadShutdown()
**    testThreadLaunch()
**    testThreadWait()
**
**    testThreadSetHalt()
**    testThreadGetHalt()
**    testThreadSetResult()
**    testThreadGetResult()
**
**    testThreadEnterMutex()
**    testThreadLeaveMutex()
*/
typedef struct ThreadSet ThreadSet;
#ifdef LSM_MUTEX_PTHREADS

#include <pthread.h>
#include <unistd.h>

typedef struct Thread Thread;
struct Thread {
  int rc;
  char *zMsg;
  pthread_t id;
  void (*xMain)(ThreadSet *, int, void *);
  void *pCtx;
  ThreadSet *pThreadSet;
};

struct ThreadSet {
  int bHalt;                      /* Halt flag */
  int nThread;                    /* Number of threads */
  Thread *aThread;                /* Array of Thread structures */
  pthread_mutex_t mutex;          /* Mutex used for cheating */
};

/*
** Return true if this build supports threads, or false otherwise. If
** this function returns false, no other testThreadXXX() functions should
** be called.
*/
static int testThreadSupport(){ return 1; }

/*
** Allocate and return a thread-set handle with enough space allocated
** to handle up to nMax threads. Each call to this function should be
** matched by a call to testThreadShutdown() to delete the object.
*/
static ThreadSet *testThreadInit(int nMax){
  int nByte;                      /* Total space to allocate */
  ThreadSet *p;                   /* Return value */

  nByte = sizeof(ThreadSet) + sizeof(struct Thread) * nMax;
  p = (ThreadSet *)testMalloc(nByte);
  p->nThread = nMax;
  p->aThread = (Thread *)&p[1];
  pthread_mutex_init(&p->mutex, 0);

  return p;
}

/*
** Delete a thread-set object and release all resources held by it.
*/
static void testThreadShutdown(ThreadSet *p){
  int i;
  for(i=0; i<p->nThread; i++){
    testFree(p->aThread[i].zMsg);
  }
  pthread_mutex_destroy(&p->mutex);
  testFree(p);
}

static void *ttMain(void *pArg){
  Thread *pThread = (Thread *)pArg;
  int iThread;
  iThread = (pThread - pThread->pThreadSet->aThread);
  pThread->xMain(pThread->pThreadSet, iThread, pThread->pCtx);
  return 0;
}

/*
** Launch a new thread.
*/
static int testThreadLaunch(
  ThreadSet *p,
  int iThread,
  void (*xMain)(ThreadSet *, int, void *),
  void *pCtx
){
  int rc;
  Thread *pThread;

  assert( iThread>=0 && iThread<p->nThread );

  pThread = &p->aThread[iThread];
  assert( pThread->pThreadSet==0 );
  pThread->xMain = xMain;
  pThread->pCtx = pCtx;
  pThread->pThreadSet = p;
  rc = pthread_create(&pThread->id, 0, ttMain, (void *)pThread);

  return rc;
}

/*
** Set the thread-set "halt" flag.
*/
static void testThreadSetHalt(ThreadSet *pThreadSet){
  pThreadSet->bHalt = 1;
}

/*
** Return the current value of the thread-set "halt" flag.
*/
static int testThreadGetHalt(ThreadSet *pThreadSet){
  return pThreadSet->bHalt;
}

static void testThreadSleep(ThreadSet *pThreadSet, int nMs){
  int nRem = nMs;
  while( nRem>0 && testThreadGetHalt(pThreadSet)==0 ){
    usleep(50000);
    nRem -= 50;
  }
}

/*
** Wait for all threads launched to finish before returning. If nMs
** is greater than zero, set the "halt" flag to tell all threads
** to halt after waiting nMs milliseconds.
*/
static void testThreadWait(ThreadSet *pThreadSet, int nMs){
  int i;

  testThreadSleep(pThreadSet, nMs);
  testThreadSetHalt(pThreadSet);
  for(i=0; i<pThreadSet->nThread; i++){
    Thread *pThread = &pThreadSet->aThread[i];
    if( pThread->xMain ){
      pthread_join(pThread->id, 0);
    }
  }
}

/*
** Set the result for thread iThread. 
*/
static void testThreadSetResult(
  ThreadSet *pThreadSet,          /* Thread-set handle */
  int iThread,                    /* Set result for this thread */
  int rc,                         /* Result error code */
  char *zFmt,                     /* Result string format */
  ...                             /* Result string formatting args... */
){
  va_list ap;

  testFree(pThreadSet->aThread[iThread].zMsg);
  pThreadSet->aThread[iThread].rc = rc;
  pThreadSet->aThread[iThread].zMsg = 0;
  if( zFmt ){
    va_start(ap, zFmt);
    pThreadSet->aThread[iThread].zMsg = testMallocVPrintf(zFmt, ap);
    va_end(ap);
  }
}

/*
** Retrieve the result for thread iThread. 
*/
static int testThreadGetResult(
  ThreadSet *pThreadSet,          /* Thread-set handle */
  int iThread,                    /* Get result for this thread */
  const char **pzRes              /* OUT: Pointer to result string */
){
  if( pzRes ) *pzRes = pThreadSet->aThread[iThread].zMsg;
  return pThreadSet->aThread[iThread].rc;
}

/*
** Enter and leave the test case mutex.
*/
#if 0
static void testThreadEnterMutex(ThreadSet *p){
  pthread_mutex_lock(&p->mutex);
}
static void testThreadLeaveMutex(ThreadSet *p){
  pthread_mutex_unlock(&p->mutex);
}
#endif
#endif

#if !defined(LSM_MUTEX_PTHREADS)
static int testThreadSupport(){ return 0; }

#define testThreadInit(a) 0
#define testThreadShutdown(a)
#define testThreadLaunch(a,b,c,d) 0
#define testThreadWait(a,b)
#define testThreadSetHalt(a)
#define testThreadGetHalt(a) 0
#define testThreadGetResult(a,b,c) 0
#define testThreadSleep(a,b) 0

static void testThreadSetResult(ThreadSet *a, int b, int c, char *d, ...){
  unused_parameter(a);
  unused_parameter(b);
  unused_parameter(c);
  unused_parameter(d);
}
#endif
/* End of threads wrapper.
*************************************************************************/

/*************************************************************************
** Below this point is the third part of this file - the implementation
** of the mt1.* tests.
*/
typedef struct Mt1Test Mt1Test;
struct Mt1Test {
  DbParameters param;             /* Description of database to read/write */
  int nReadwrite;                 /* Number of read/write threads */
  int nFastReader;                /* Number of fast reader threads */
  int nSlowReader;                /* Number of slow reader threads */
  int nMs;                        /* How long to run for */
  const char *zSystem;            /* Database system to test */
};

typedef struct Mt1DelayCtx Mt1DelayCtx;
struct Mt1DelayCtx {
  ThreadSet *pSet;                /* Threadset to sleep within */
  int nMs;                        /* Sleep in ms */
};

static void xMt1Delay(void *pCtx){
  Mt1DelayCtx *p = (Mt1DelayCtx *)pCtx;
  testThreadSleep(p->pSet, p->nMs);
}

#define MT1_THREAD_RDWR 0
#define MT1_THREAD_SLOW 1
#define MT1_THREAD_FAST 2

static void xMt1Work(lsm_db *pDb, void *pCtx){
#if 0
  char *z = 0;
  lsm_info(pDb, LSM_INFO_DB_STRUCTURE, &z);
  printf("%s\n", z);
  fflush(stdout);
#endif
}

/*
** This is the main() proc for all threads in test case "mt1".
*/
static void mt1Main(ThreadSet *pThreadSet, int iThread, void *pCtx){
  Mt1Test *p = (Mt1Test *)pCtx;   /* Test parameters */
  Mt1DelayCtx delay;
  int nRead = 0;                  /* Number of calls to dbReadOperation() */
  int nWrite = 0;                 /* Number of completed database writes */
  int rc = 0;                     /* Error code */
  int iPrng;                      /* Prng argument variable */
  TestDb *pDb;                    /* Database handle */
  int eType;

  delay.pSet = pThreadSet;
  delay.nMs = 0;
  if( iThread<p->nReadwrite ){
    eType = MT1_THREAD_RDWR;
  }else if( iThread<(p->nReadwrite+p->nFastReader) ){
    eType = MT1_THREAD_FAST;
  }else{
    eType = MT1_THREAD_SLOW;
    delay.nMs = (p->nMs / 20);
  }

  /* Open a new database connection. Initialize the pseudo-random number
  ** argument based on the thread number.  */
  iPrng = testPrngValue(iThread);
  pDb = testOpen(p->zSystem, 0, &rc);

  if( rc==0 ){
    tdb_lsm_config_work_hook(pDb, xMt1Work, 0);
  }

  /* Loop until either an error occurs or some other thread sets the
  ** halt flag.  */
  while( rc==0 && testThreadGetHalt(pThreadSet)==0 ){
    int iKey;

    /* Perform a read operation on an arbitrarily selected key. */
    iKey = (testPrngValue(iPrng++) % p->param.nKey);
    dbReadOperation(&p->param, pDb, xMt1Delay, (void *)&delay, iKey, &rc);
    if( rc ) continue;
    nRead++;

    /* Attempt to write an arbitrary key value pair (and update the associated
    ** checksum entries). dbWriteOperation() returns 1 if the write is
    ** successful, or 0 if it failed with an LSM_BUSY error.  */
    if( eType==MT1_THREAD_RDWR ){
      char aValue[50];
      char aRnd[25];

      iKey = (testPrngValue(iPrng++) % p->param.nKey);
      testPrngString(iPrng, aRnd, sizeof(aRnd));
      iPrng += sizeof(aRnd);
      snprintf(aValue, sizeof(aValue), "%d.%s", iThread, aRnd);
      nWrite += dbWriteOperation(&p->param, pDb, iKey, aValue, &rc);
    }
  }
  testClose(&pDb);

  /* If an error has occured, set the thread error code and the threadset 
  ** halt flag to tell the other test threads to halt. Otherwise, set the
  ** thread error code to 0 and post a message with the number of read
  ** and write operations completed.  */
  if( rc ){
    testThreadSetResult(pThreadSet, iThread, rc, 0);
    testThreadSetHalt(pThreadSet);
  }else{
    testThreadSetResult(pThreadSet, iThread, 0, "r/w: %d/%d", nRead, nWrite);
  }
}

static void do_test_mt1(
  const char *zSystem,            /* Database system name */
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  Mt1Test aTest[] = {
    /* param, nReadwrite, nFastReader, nSlowReader, nMs, zSystem */
    { {10, 1000},     4, 0, 0,   10000,   0 },
    { {10, 1000},     4, 4, 2,   100000,  0 },
    { {10, 100000},   4, 0, 0,   10000,   0 },
    { {10, 100000},   4, 4, 2,   100000,  0 },
  };
  int i;

  for(i=0; *pRc==0 && i<ArraySize(aTest); i++){
    Mt1Test *p = &aTest[i];
    int bRun = testCaseBegin(pRc, zPattern, 
        "mt1.%s.db=%d,%d.ms=%d.rdwr=%d.fast=%d.slow=%d", 
        zSystem, p->param.nFanout, p->param.nKey, 
        p->nMs, p->nReadwrite, p->nFastReader, p->nSlowReader
    );
    if( bRun ){
      TestDb *pDb;
      ThreadSet *pSet;
      int iThread;
      int nThread;

      p->zSystem = zSystem;
      pDb = testOpen(zSystem, 1, pRc);

      nThread = p->nReadwrite + p->nFastReader + p->nSlowReader;
      pSet = testThreadInit(nThread);
      for(iThread=0; *pRc==0 && iThread<nThread; iThread++){
        testThreadLaunch(pSet, iThread, mt1Main, (void *)p);
      }

      testThreadWait(pSet, p->nMs);
      for(iThread=0; *pRc==0 && iThread<nThread; iThread++){
        *pRc = testThreadGetResult(pSet, iThread, 0);
      }
      testCaseFinish(*pRc);

      for(iThread=0; *pRc==0 && iThread<nThread; iThread++){
        const char *zMsg = 0;
        *pRc = testThreadGetResult(pSet, iThread, &zMsg);
        printf("  Info: thread %d (%d): %s\n", iThread, *pRc, zMsg);
      }

      testThreadShutdown(pSet);
      testClose(&pDb);
    }
  }
}

void test_mt(
  const char *zSystem,            /* Database system name */
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  if( testThreadSupport()==0 ) return;
  do_test_mt1(zSystem, zPattern, pRc);
}

#include "lsmtest.h"

typedef struct OomTest OomTest;
struct OomTest {
  lsm_env *pEnv;
  int iNext;                      /* Next value to pass to testMallocOom() */
  int nFail;                      /* Number of OOM events injected */
  int bEnable;
  int rc;                         /* Test case error code */
};

static void testOomStart(OomTest *p){
  memset(p, 0, sizeof(OomTest));
  p->iNext = 1;
  p->bEnable = 1;
  p->nFail = 1;
  p->pEnv = tdb_lsm_env();
}

static void xOomHook(OomTest *p){
  p->nFail++;
}

static int testOomContinue(OomTest *p){
  if( p->rc!=0 || (p->iNext>1 && p->nFail==0) ){
    return 0;
  }
  p->nFail = 0;
  testMallocOom(p->pEnv, p->iNext, 0, (void (*)(void*))xOomHook, (void *)p);
  return 1;
}

static void testOomEnable(OomTest *p, int bEnable){
  p->bEnable = bEnable;
  testMallocOomEnable(p->pEnv, bEnable);
}

static void testOomNext(OomTest *p){
  p->iNext++;
}

static int testOomHit(OomTest *p){
  return (p->nFail>0);
}

static int testOomFinish(OomTest *p){
  return p->rc;
}

static void testOomAssert(OomTest *p, int bVal){
  if( bVal==0 ){
    test_failed();
    p->rc = 1;
  }
}

/*
** Test that the error code matches the state of the OomTest object passed
** as the first argument. Specifically, check that rc is LSM_NOMEM if an 
** OOM error has already been injected, or LSM_OK if not.
*/
static void testOomAssertRc(OomTest *p, int rc){
  testOomAssert(p, rc==LSM_OK || rc==LSM_NOMEM);
  testOomAssert(p, testOomHit(p)==(rc==LSM_NOMEM) || p->bEnable==0 );
}

static void testOomOpen(
  OomTest *pOom,
  const char *zName,
  lsm_db **ppDb,
  int *pRc
){
  if( *pRc==LSM_OK ){
    int rc;
    rc = lsm_new(tdb_lsm_env(), ppDb);
    if( rc==LSM_OK ) rc = lsm_open(*ppDb, zName);
    testOomAssertRc(pOom, rc);
    *pRc = rc;
  }
}

static void testOomFetch(
  OomTest *pOom,
  lsm_db *pDb,
  void *pKey, int nKey,
  void *pVal, int nVal,
  int *pRc
){
  testOomAssertRc(pOom, *pRc);
  if( *pRc==LSM_OK ){
    lsm_cursor *pCsr;
    int rc;

    rc = lsm_csr_open(pDb, &pCsr);
    if( rc==LSM_OK ) rc = lsm_csr_seek(pCsr, pKey, nKey, 0);
    testOomAssertRc(pOom, rc);

    if( rc==LSM_OK ){
      const void *p; int n;
      testOomAssert(pOom, lsm_csr_valid(pCsr));

      rc = lsm_csr_key(pCsr, &p, &n);
      testOomAssertRc(pOom, rc);
      testOomAssert(pOom, rc!=LSM_OK || (n==nKey && memcmp(pKey, p, nKey)==0) );
    }

    if( rc==LSM_OK ){
      const void *p; int n;
      testOomAssert(pOom, lsm_csr_valid(pCsr));

      rc = lsm_csr_value(pCsr, &p, &n);
      testOomAssertRc(pOom, rc);
      testOomAssert(pOom, rc!=LSM_OK || (n==nVal && memcmp(pVal, p, nVal)==0) );
    }

    lsm_csr_close(pCsr);
    *pRc = rc;
  }
}

static void testOomWrite(
  OomTest *pOom,
  lsm_db *pDb,
  void *pKey, int nKey,
  void *pVal, int nVal,
  int *pRc
){
  testOomAssertRc(pOom, *pRc);
  if( *pRc==LSM_OK ){
    int rc;

    rc = lsm_insert(pDb, pKey, nKey, pVal, nVal);
    testOomAssertRc(pOom, rc);

    *pRc = rc;
  }
}


static void testOomFetchStr(
  OomTest *pOom,
  lsm_db *pDb,
  const char *zKey,
  const char *zVal,
  int *pRc
){
  int nKey = strlen(zKey);
  int nVal = strlen(zVal);
  testOomFetch(pOom, pDb, (void *)zKey, nKey, (void *)zVal, nVal, pRc);
}

static void testOomFetchData(
  OomTest *pOom,
  lsm_db *pDb,
  Datasource *pData,
  int iKey,
  int *pRc
){
  void *pKey; int nKey;
  void *pVal; int nVal;
  testDatasourceEntry(pData, iKey, &pKey, &nKey, &pVal, &nVal);
  testOomFetch(pOom, pDb, pKey, nKey, pVal, nVal, pRc);
}

static void testOomWriteStr(
  OomTest *pOom,
  lsm_db *pDb,
  const char *zKey,
  const char *zVal,
  int *pRc
){
  int nKey = strlen(zKey);
  int nVal = strlen(zVal);
  testOomWrite(pOom, pDb, (void *)zKey, nKey, (void *)zVal, nVal, pRc);
}

static void testOomWriteData(
  OomTest *pOom,
  lsm_db *pDb,
  Datasource *pData,
  int iKey,
  int *pRc
){
  void *pKey; int nKey;
  void *pVal; int nVal;
  testDatasourceEntry(pData, iKey, &pKey, &nKey, &pVal, &nVal);
  testOomWrite(pOom, pDb, pKey, nKey, pVal, nVal, pRc);
}

static void testOomScan(
  OomTest *pOom, 
  lsm_db *pDb, 
  int bReverse,
  const void *pKey, int nKey,
  int nScan,
  int *pRc
){
  if( *pRc==0 ){
    int rc;
    int iScan = 0;
    lsm_cursor *pCsr;
    int (*xAdvance)(lsm_cursor *);
    

    rc = lsm_csr_open(pDb, &pCsr);
    testOomAssertRc(pOom, rc);

    if( rc==LSM_OK ){
      if( bReverse ){
        rc = lsm_csr_seek(pCsr, pKey, nKey, LSM_SEEK_LE);
        xAdvance = lsm_csr_prev;
      }else{
        rc = lsm_csr_seek(pCsr, pKey, nKey, LSM_SEEK_GE);
        xAdvance = lsm_csr_next;
      }
    }
    testOomAssertRc(pOom, rc);

    while( rc==LSM_OK && lsm_csr_valid(pCsr) && iScan<nScan ){
      const void *p; int n;

      rc = lsm_csr_key(pCsr, &p, &n);
      testOomAssertRc(pOom, rc);
      if( rc==LSM_OK ){
        rc = lsm_csr_value(pCsr, &p, &n);
        testOomAssertRc(pOom, rc);
      }
      if( rc==LSM_OK ){
        rc = xAdvance(pCsr);
        testOomAssertRc(pOom, rc);
      }
      iScan++;
    }

    lsm_csr_close(pCsr);
    *pRc = rc;
  }
}

#define LSMTEST6_TESTDB "testdb.lsm" 

#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

void testDeleteLsmdb(const char *zFile){
  char *zLog = testMallocPrintf("%s-log", zFile);
  char *zShm = testMallocPrintf("%s-shm", zFile);
  unlink(zFile);
  unlink(zLog);
  unlink(zShm);
  testFree(zLog);
  testFree(zShm);
}

static void copy_file(const char *zFrom, const char *zTo){

  if( access(zFrom, F_OK) ){
    unlink(zTo);
  }else{
    int fd1;
    int fd2;
    off_t sz;
    off_t i;
    struct stat buf;
    u8 *aBuf;

    fd1 = open(zFrom, O_RDONLY, 0644);
    fd2 = open(zTo, O_RDWR | O_CREAT, 0644);

    fstat(fd1, &buf);
    sz = buf.st_size;
    ftruncate(fd2, sz);

    aBuf = testMalloc(4096);
    for(i=0; i<sz; i+=4096){
      int nByte = MIN(4096, sz - i);
      read(fd1, aBuf, nByte);
      write(fd2, aBuf, nByte);
    }
    testFree(aBuf);

    close(fd1);
    close(fd2);
  }
}

void testCopyLsmdb(const char *zFrom, const char *zTo){
  char *zLog1 = testMallocPrintf("%s-log", zFrom);
  char *zLog2 = testMallocPrintf("%s-log", zTo);
  char *zShm1 = testMallocPrintf("%s-shm", zFrom);
  char *zShm2 = testMallocPrintf("%s-shm", zTo);

  unlink(zShm2);
  unlink(zLog2);
  unlink(zTo);
  copy_file(zFrom, zTo);
  copy_file(zLog1, zLog2);
  copy_file(zShm1, zShm2);

  testFree(zLog1); testFree(zLog2); testFree(zShm1); testFree(zShm2);
}

/*
** File zFile is the path to a database. This function makes backups
** of the database file and its log as follows:
**
**     cp $(zFile)         $(zFile)-save
**     cp $(zFile)-$(zAux) $(zFile)-save-$(zAux)
**
** Function testRestoreDb() can be used to copy the files back in the
** other direction.
*/
void testSaveDb(const char *zFile, const char *zAux){
  char *zLog = testMallocPrintf("%s-%s", zFile, zAux);
  char *zFileSave = testMallocPrintf("%s-save", zFile);
  char *zLogSave = testMallocPrintf("%s-%s-save", zFile, zAux);

  unlink(zFileSave);
  unlink(zLogSave);
  copy_file(zFile, zFileSave);
  copy_file(zLog, zLogSave);

  testFree(zLog); testFree(zFileSave); testFree(zLogSave);
}

/*
** File zFile is the path to a database. This function restores
** a backup of the database made by a previous call to testSaveDb().
** Specifically, it does the equivalent of:
**
**     cp $(zFile)-save         $(zFile)
**     cp $(zFile)-save-$(zAux) $(zFile)-$(zAux)
*/
void testRestoreDb(const char *zFile, const char *zAux){
  char *zLog = testMallocPrintf("%s-%s", zFile, zAux);
  char *zFileSave = testMallocPrintf("%s-save", zFile);
  char *zLogSave = testMallocPrintf("%s-%s-save", zFile, zAux);

  copy_file(zFileSave, zFile);
  copy_file(zLogSave, zLog);

  testFree(zLog); testFree(zFileSave); testFree(zLogSave);
}


static int lsmWriteStr(lsm_db *pDb, const char *zKey, const char *zVal){
  int nKey = strlen(zKey);
  int nVal = strlen(zVal);
  return lsm_insert(pDb, (void *)zKey, nKey, (void *)zVal, nVal);
}

static void setup_delete_db(){
  testDeleteLsmdb(LSMTEST6_TESTDB);
}

/*
** Create a small database. With the following content:
**
**    "one"   -> "one"
**    "two"   -> "four"
**    "three" -> "nine"
**    "four"  -> "sixteen"
**    "five"  -> "twentyfive"
**    "six"   -> "thirtysix"
**    "seven" -> "fourtynine"
**    "eight" -> "sixtyfour"
*/
static void setup_populate_db(){
  const char *azStr[] = {
    "one",   "one",
    "two",   "four",
    "three", "nine",
    "four",  "sixteen",
    "five",  "twentyfive",
    "six",   "thirtysix",
    "seven", "fourtynine",
    "eight", "sixtyfour",
  };
  int rc;
  int ii;
  lsm_db *pDb;

  testDeleteLsmdb(LSMTEST6_TESTDB);

  rc = lsm_new(tdb_lsm_env(), &pDb);
  if( rc==LSM_OK ) rc = lsm_open(pDb, LSMTEST6_TESTDB);

  for(ii=0; rc==LSM_OK && ii<ArraySize(azStr); ii+=2){
    rc = lsmWriteStr(pDb, azStr[ii], azStr[ii+1]);
  }
  lsm_close(pDb);

  testSaveDb(LSMTEST6_TESTDB, "log");
  assert( rc==LSM_OK );
}

static Datasource *getDatasource(void){
  const DatasourceDefn defn = { TEST_DATASOURCE_RANDOM, 10, 15, 200, 250 };
  return testDatasourceNew(&defn);
}

/*
** Set up a database file with the following properties:
**
**   * Page size is 1024 bytes.
**   * Block size is 64 KB.
**   * Contains 5000 key-value pairs starting at 0 from the
**     datasource returned getDatasource().
*/
static void setup_populate_db2(){
  Datasource *pData;
  int ii;
  int rc;
  int nBlocksize = 64*1024;
  int nPagesize = 1024;
  int nWritebuffer = 4*1024;
  lsm_db *pDb;

  testDeleteLsmdb(LSMTEST6_TESTDB);
  rc = lsm_new(tdb_lsm_env(), &pDb);
  if( rc==LSM_OK ) rc = lsm_open(pDb, LSMTEST6_TESTDB);

  lsm_config(pDb, LSM_CONFIG_BLOCK_SIZE, &nBlocksize); 
  lsm_config(pDb, LSM_CONFIG_PAGE_SIZE, &nPagesize); 
  lsm_config(pDb, LSM_CONFIG_AUTOFLUSH, &nWritebuffer); 

  pData = getDatasource();
  for(ii=0; rc==LSM_OK && ii<5000; ii++){
    void *pKey; int nKey;
    void *pVal; int nVal;
    testDatasourceEntry(pData, ii, &pKey, &nKey, &pVal, &nVal);
    lsm_insert(pDb, pKey, nKey, pVal, nVal);
  }
  testDatasourceFree(pData);
  lsm_close(pDb);

  testSaveDb(LSMTEST6_TESTDB, "log");
  assert( rc==LSM_OK );
}

/*
** Test the results of OOM conditions in lsm_new().
*/
static void simple_oom_1(OomTest *pOom){
  int rc;
  lsm_db *pDb;

  rc = lsm_new(tdb_lsm_env(), &pDb);
  testOomAssertRc(pOom, rc);

  lsm_close(pDb);
}

/*
** Test the results of OOM conditions in lsm_open().
*/
static void simple_oom_2(OomTest *pOom){
  int rc;
  lsm_db *pDb;

  rc = lsm_new(tdb_lsm_env(), &pDb);
  if( rc==LSM_OK ){
    rc = lsm_open(pDb, "testdb.lsm");
  }
  testOomAssertRc(pOom, rc);

  lsm_close(pDb);
}

/*
** Test the results of OOM conditions in simple fetch operations.
*/
static void simple_oom_3(OomTest *pOom){
  int rc = LSM_OK;
  lsm_db *pDb;

  testOomOpen(pOom, LSMTEST6_TESTDB, &pDb, &rc);

  testOomFetchStr(pOom, pDb, "four",  "sixteen",    &rc);
  testOomFetchStr(pOom, pDb, "seven", "fourtynine", &rc);
  testOomFetchStr(pOom, pDb, "one",   "one",        &rc);
  testOomFetchStr(pOom, pDb, "eight", "sixtyfour",  &rc);

  lsm_close(pDb);
}

/*
** Test the results of OOM conditions in simple write operations.
*/
static void simple_oom_4(OomTest *pOom){
  int rc = LSM_OK;
  lsm_db *pDb;

  testDeleteLsmdb(LSMTEST6_TESTDB);
  testOomOpen(pOom, LSMTEST6_TESTDB, &pDb, &rc);

  testOomWriteStr(pOom, pDb, "123", "onetwothree", &rc);
  testOomWriteStr(pOom, pDb, "456", "fourfivesix", &rc);
  testOomWriteStr(pOom, pDb, "789", "seveneightnine", &rc);
  testOomWriteStr(pOom, pDb, "123", "teneleventwelve", &rc);
  testOomWriteStr(pOom, pDb, "456", "fourteenfifteensixteen", &rc);

  lsm_close(pDb);
}

static void simple_oom_5(OomTest *pOom){
  Datasource *pData = getDatasource();
  int rc = LSM_OK;
  lsm_db *pDb;

  testRestoreDb(LSMTEST6_TESTDB, "log");
  testOomOpen(pOom, LSMTEST6_TESTDB, &pDb, &rc);

  testOomFetchData(pOom, pDb, pData, 3333, &rc);
  testOomFetchData(pOom, pDb, pData, 0, &rc);
  testOomFetchData(pOom, pDb, pData, 4999, &rc);

  lsm_close(pDb);
  testDatasourceFree(pData);
}

static void simple_oom_6(OomTest *pOom){
  Datasource *pData = getDatasource();
  int rc = LSM_OK;
  lsm_db *pDb;

  testRestoreDb(LSMTEST6_TESTDB, "log");
  testOomOpen(pOom, LSMTEST6_TESTDB, &pDb, &rc);

  testOomWriteData(pOom, pDb, pData, 5000, &rc);
  testOomWriteData(pOom, pDb, pData, 5001, &rc);
  testOomWriteData(pOom, pDb, pData, 5002, &rc);
  testOomFetchData(pOom, pDb, pData, 5001, &rc);
  testOomFetchData(pOom, pDb, pData, 1234, &rc);

  lsm_close(pDb);
  testDatasourceFree(pData);
}

static void simple_oom_7(OomTest *pOom){
  Datasource *pData = getDatasource();
  int rc = LSM_OK;
  lsm_db *pDb;

  testRestoreDb(LSMTEST6_TESTDB, "log");
  testOomOpen(pOom, LSMTEST6_TESTDB, &pDb, &rc);
  testOomScan(pOom, pDb, 0, "abc", 3, 20, &rc);
  lsm_close(pDb);
  testDatasourceFree(pData);
}

static void simple_oom_8(OomTest *pOom){
  Datasource *pData = getDatasource();
  int rc = LSM_OK;
  lsm_db *pDb;
  testRestoreDb(LSMTEST6_TESTDB, "log");
  testOomOpen(pOom, LSMTEST6_TESTDB, &pDb, &rc);
  testOomScan(pOom, pDb, 1, "xyz", 3, 20, &rc);
  lsm_close(pDb);
  testDatasourceFree(pData);
}

/*
** This test case has two clients connected to a database. The first client
** hits an OOM while writing to the database. Check that the second 
** connection is still able to query the db following the OOM.
*/
static void simple_oom2_1(OomTest *pOom){
  const int nRecord = 100;        /* Number of records initially in db */
  const int nIns = 10;            /* Number of records inserted with OOM */

  Datasource *pData = getDatasource();
  int rc = LSM_OK;
  lsm_db *pDb1;
  lsm_db *pDb2;
  int i;

  testDeleteLsmdb(LSMTEST6_TESTDB);

  /* Open the two connections. Initialize the in-memory tree so that it
  ** contains 100 records. Do all this with OOM injection disabled. */
  testOomEnable(pOom, 0);
  testOomOpen(pOom, LSMTEST6_TESTDB, &pDb1, &rc);
  testOomOpen(pOom, LSMTEST6_TESTDB, &pDb2, &rc);
  for(i=0; i<nRecord; i++){
    testOomWriteData(pOom, pDb1, pData, i, &rc);
  }
  testOomEnable(pOom, 1);
  assert( rc==0 );

  /* Insert 10 more records using pDb1. Stop when an OOM is encountered. */
  for(i=nRecord; i<nRecord+nIns; i++){
    testOomWriteData(pOom, pDb1, pData, i, &rc);
    if( rc ) break;
  }
  testOomAssertRc(pOom, rc);

  /* Switch off OOM injection. Write a few rows using pDb2. Then check
  ** that the database may be successfully queried.  */
  testOomEnable(pOom, 0);
  rc = 0;
  for(; i<nRecord+nIns && rc==0; i++){
    testOomWriteData(pOom, pDb2, pData, i, &rc);
  }
  for(i=0; i<nRecord+nIns; i++) testOomFetchData(pOom, pDb2, pData, i, &rc);
  testOomEnable(pOom, 1);

  lsm_close(pDb1);
  lsm_close(pDb2);
  testDatasourceFree(pData);
}


static void do_test_oom1(const char *zPattern, int *pRc){
  struct SimpleOom {
    const char *zName;
    void (*xSetup)(void);
    void (*xFunc)(OomTest *);
  } aSimple[] = {
    { "oom1.lsm.1", setup_delete_db,    simple_oom_1 },
    { "oom1.lsm.2", setup_delete_db,    simple_oom_2 },
    { "oom1.lsm.3", setup_populate_db,  simple_oom_3 },
    { "oom1.lsm.4", setup_delete_db,    simple_oom_4 },
    { "oom1.lsm.5", setup_populate_db2, simple_oom_5 },
    { "oom1.lsm.6", setup_populate_db2, simple_oom_6 },
    { "oom1.lsm.7", setup_populate_db2, simple_oom_7 },
    { "oom1.lsm.8", setup_populate_db2, simple_oom_8 },

    { "oom2.lsm.1", setup_delete_db,    simple_oom2_1 },
  };
  int i;

  for(i=0; i<ArraySize(aSimple); i++){
    if( *pRc==0 && testCaseBegin(pRc, zPattern, "%s", aSimple[i].zName) ){
      OomTest t;

      if( aSimple[i].xSetup ){
        aSimple[i].xSetup();
      }

      for(testOomStart(&t); testOomContinue(&t); testOomNext(&t)){
        aSimple[i].xFunc(&t);
      }

      printf("(%d injections).", t.iNext-2);
      testCaseFinish( (*pRc = testOomFinish(&t)) );
      testMallocOom(tdb_lsm_env(), 0, 0, 0, 0);
    }
  }
}

void test_oom(
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  do_test_oom1(zPattern, pRc);
}

#include "lsmtest.h"


/*
** Test that the rules for when lsm_csr_next() and lsm_csr_prev() are
** enforced. Specifically:
**
**   * Both functions always return LSM_MISUSE if the cursor is at EOF
**     when they are called.
**
**   * lsm_csr_next() may only be used after lsm_csr_seek(LSM_SEEK_GE) or 
**     lsm_csr_first(). 
**
**   * lsm_csr_prev() may only be used after lsm_csr_seek(LSM_SEEK_LE) or 
**     lsm_csr_last().
*/
static void do_test_api1_lsm(lsm_db *pDb, int *pRc){
  int ret;
  lsm_cursor *pCsr;
  lsm_cursor *pCsr2;
  int nKey;
  const void *pKey;

  ret = lsm_csr_open(pDb, &pCsr);
  testCompareInt(LSM_OK, ret, pRc);

  ret = lsm_csr_next(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);
  ret = lsm_csr_prev(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);

  ret = lsm_csr_seek(pCsr, "jjj", 3, LSM_SEEK_GE);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_next(pCsr);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_prev(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);

  ret = lsm_csr_seek(pCsr, "jjj", 3, LSM_SEEK_LE);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_next(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);
  ret = lsm_csr_prev(pCsr);
  testCompareInt(LSM_OK, ret, pRc);

  ret = lsm_csr_seek(pCsr, "jjj", 3, LSM_SEEK_LEFAST);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_next(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);
  ret = lsm_csr_prev(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);

  ret = lsm_csr_key(pCsr, &pKey, &nKey);
  testCompareInt(LSM_OK, ret, pRc);

  ret = lsm_csr_open(pDb, &pCsr2);
  testCompareInt(LSM_OK, ret, pRc);

  ret = lsm_csr_seek(pCsr2, pKey, nKey, LSM_SEEK_EQ);
  testCompareInt(LSM_OK, ret, pRc);
  testCompareInt(1, lsm_csr_valid(pCsr2), pRc);
  ret = lsm_csr_next(pCsr2);
  testCompareInt(LSM_MISUSE, ret, pRc);
  ret = lsm_csr_prev(pCsr2);
  testCompareInt(LSM_MISUSE, ret, pRc);

  lsm_csr_close(pCsr2);

  ret = lsm_csr_first(pCsr);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_next(pCsr);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_prev(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);

  ret = lsm_csr_last(pCsr);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_prev(pCsr);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_next(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);

  ret = lsm_csr_first(pCsr);
  while( lsm_csr_valid(pCsr) ){
    ret = lsm_csr_next(pCsr);
    testCompareInt(LSM_OK, ret, pRc);
  }
  ret = lsm_csr_next(pCsr);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_prev(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);

  ret = lsm_csr_last(pCsr);
  while( lsm_csr_valid(pCsr) ){
    ret = lsm_csr_prev(pCsr);
    testCompareInt(LSM_OK, ret, pRc);
  }
  ret = lsm_csr_prev(pCsr);
  testCompareInt(LSM_OK, ret, pRc);
  ret = lsm_csr_next(pCsr);
  testCompareInt(LSM_MISUSE, ret, pRc);

  lsm_csr_close(pCsr);
}

static void do_test_api1(const char *zPattern, int *pRc){
  if( testCaseBegin(pRc, zPattern, "api1.lsm") ){
    const DatasourceDefn defn = { TEST_DATASOURCE_RANDOM, 10, 15, 200, 250 };
    Datasource *pData;
    TestDb *pDb;
    int rc = 0;

    pDb = testOpen("lsm_lomem", 1, &rc);
    pData = testDatasourceNew(&defn);
    testWriteDatasourceRange(pDb, pData, 0, 1000, pRc);

    do_test_api1_lsm(tdb_lsm(pDb), pRc);

    testDatasourceFree(pData);
    testClose(&pDb);

    testCaseFinish(*pRc);
  }
}

static lsm_db *newLsmConnection(
  const char *zDb, 
  int nPgsz, 
  int nBlksz,
  int *pRc
){
  lsm_db *db = 0;
  if( *pRc==0 ){
    int n1 = nPgsz;
    int n2 = nBlksz;
    *pRc = lsm_new(tdb_lsm_env(), &db);
    if( *pRc==0 ){
      if( n1 ) lsm_config(db, LSM_CONFIG_PAGE_SIZE, &n1);
      if( n2 ) lsm_config(db, LSM_CONFIG_BLOCK_SIZE, &n2);
      *pRc = lsm_open(db, "testdb.lsm");
    }
  }
  return db;
}

static void testPagesize(lsm_db *db, int nPgsz, int nBlksz, int *pRc){
  if( *pRc==0 ){
    int n1 = 0;
    int n2 = 0;

    lsm_config(db, LSM_CONFIG_PAGE_SIZE, &n1);
    lsm_config(db, LSM_CONFIG_BLOCK_SIZE, &n2);

    testCompareInt(n1, nPgsz, pRc);
    testCompareInt(n2, nBlksz, pRc);
  }
}

/*
** Test case "api2" tests that the default page and block sizes of a 
** database may only be modified before lsm_open() is called. And that
** after lsm_open() is called lsm_config() may be used to read the 
** actual page and block size of the db.
*/
static void do_test_api2(const char *zPattern, int *pRc){
  if( *pRc==0 && testCaseBegin(pRc, zPattern, "api2.lsm") ){
    lsm_db *db1 = 0;
    lsm_db *db2 = 0;

    testDeleteLsmdb("testdb.lsm");
    db1 = newLsmConnection("testdb.lsm", 0, 0, pRc);
    testPagesize(db1, 4096, 2*1024*1024, pRc);
    db2 = newLsmConnection("testdb.lsm", 1024, 64*1024, pRc);
    testPagesize(db2, 4096, 2*1024*1024, pRc);
    lsm_close(db1);
    lsm_close(db2);

    testDeleteLsmdb("testdb.lsm");
    db1 = newLsmConnection("testdb.lsm", 1024, 64*1024, pRc);
    testPagesize(db1, 1024, 64*1024, pRc);
    db2 = newLsmConnection("testdb.lsm", 0, 0, pRc);
    testPagesize(db2, 1024, 64*1024, pRc);
    lsm_close(db1);
    lsm_close(db2);

    testDeleteLsmdb("testdb.lsm");
    db1 = newLsmConnection("testdb.lsm", 8192, 1*1024*1024, pRc);
    testPagesize(db1, 8192, 1*1024*1024, pRc);
    db2 = newLsmConnection("testdb.lsm", 1024, 64*1024, pRc);
    testPagesize(db2, 8192, 1*1024*1024, pRc);
    lsm_close(db1);
    lsm_close(db2);

    testCaseFinish(*pRc);
  }
}

void test_api(
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  do_test_api1(zPattern, pRc);
  do_test_api2(zPattern, pRc);
}

/*
** This file contains test cases to verify that "live-recovery" following
** a mid-transaction failure of a writer process.
*/


/* 
** This test file includes lsmInt.h to get access to the definition of the
** ShmHeader structure. This is required to cause strategic damage to the
** shared memory header as part of recovery testing.
*/
#include "lsmInt.h"

#include "lsmtest.h"

typedef struct SetupStep SetupStep;
struct SetupStep {
  int bFlush;                     /* Flush to disk and checkpoint */
  int iInsStart;                  /* First key-value from ds to insert */
  int nIns;                       /* Number of rows to insert */
  int iDelStart;                  /* First key from ds to delete */
  int nDel;                       /* Number of rows to delete */
};

static void doSetupStep(
  TestDb *pDb, 
  Datasource *pData, 
  const SetupStep *pStep, 
  int *pRc
){
  testWriteDatasourceRange(pDb, pData, pStep->iInsStart, pStep->nIns, pRc);
  testDeleteDatasourceRange(pDb, pData, pStep->iDelStart, pStep->nDel, pRc);
  if( *pRc==0 ){
    int nSave = -1;
    int nBuf = 64;
    lsm_db *db = tdb_lsm(pDb);

    lsm_config(db, LSM_CONFIG_AUTOFLUSH, &nSave);
    lsm_config(db, LSM_CONFIG_AUTOFLUSH, &nBuf);
    lsm_begin(db, 1);
    lsm_commit(db, 0);
    lsm_config(db, LSM_CONFIG_AUTOFLUSH, &nSave);

    *pRc = lsm_work(db, 0, 0, 0);
    if( *pRc==0 ){
      *pRc = lsm_checkpoint(db, 0);
    }
  }
}

static void doSetupStepArray(
  TestDb *pDb, 
  Datasource *pData, 
  const SetupStep *aStep, 
  int nStep
){
  int i;
  for(i=0; i<nStep; i++){
    int rc = 0;
    doSetupStep(pDb, pData, &aStep[i], &rc);
    assert( rc==0 );
  }
}

static void setupDatabase1(TestDb *pDb, Datasource **ppData){
  const SetupStep aStep[] = {
    { 0,                                  1,     2000, 0, 0 },
    { 1,                                  0,     0, 0, 0 },
    { 0,                                  10001, 1000, 0, 0 },
  };
  const DatasourceDefn defn = {TEST_DATASOURCE_RANDOM, 12, 16, 100, 500};
  Datasource *pData;

  pData = testDatasourceNew(&defn);
  doSetupStepArray(pDb, pData, aStep, ArraySize(aStep));
  if( ppData ){
    *ppData = pData;
  }else{
    testDatasourceFree(pData);
  }
}

#include <stdio.h>
void testReadFile(const char *zFile, int iOff, void *pOut, int nByte, int *pRc){
  if( *pRc==0 ){
    FILE *fd;
    fd = fopen(zFile, "r");
    if( fd==0 ){
      *pRc = 1;
    }else{
      if( 0!=fseek(fd, iOff, SEEK_SET) ){
        *pRc = 1;
      }else{
        if( nByte!=fread(pOut, 1, nByte, fd) ){
          *pRc = 1;
        }
      }
      fclose(fd);
    }
  }
}

void testWriteFile(
  const char *zFile, 
  int iOff, 
  void *pOut, 
  int nByte, 
  int *pRc
){
  if( *pRc==0 ){
    FILE *fd;
    fd = fopen(zFile, "r+");
    if( fd==0 ){
      *pRc = 1;
    }else{
      if( 0!=fseek(fd, iOff, SEEK_SET) ){
        *pRc = 1;
      }else{
        if( nByte!=fwrite(pOut, 1, nByte, fd) ){
          *pRc = 1;
        }
      }
      fclose(fd);
    }
  }
}

static ShmHeader *getShmHeader(const char *zDb){
  int rc = 0;
  char *zShm = testMallocPrintf("%s-shm", zDb);
  ShmHeader *pHdr;

  pHdr = testMalloc(sizeof(ShmHeader));
  testReadFile(zShm, 0, (void *)pHdr, sizeof(ShmHeader), &rc);
  assert( rc==0 );

  return pHdr;
}

/*
** This function makes a copy of the three files associated with LSM 
** database zDb (i.e. if zDb is "test.db", it makes copies of "test.db",
** "test.db-log" and "test.db-shm").
**
** It then opens a new database connection to the copy with the xLock() call
** instrumented so that it appears that some other process already connected
** to the db (holding a shared lock on DMS2). This prevents recovery from
** running. Then:
**
**    1) Check that the checksum of the database is zCksum. 
**    2) Write a few keys to the database. Then delete the same keys. 
**    3) Check that the checksum is zCksum.
**    4) Flush the db to disk and run a checkpoint. 
**    5) Check once more that the checksum is still zCksum.
*/
static void doLiveRecovery(const char *zDb, const char *zCksum, int *pRc){
  const DatasourceDefn defn = {TEST_DATASOURCE_RANDOM, 20, 25, 100, 500};
  Datasource *pData;
  const char *zCopy = "testcopy.lsm";
  char zCksum2[TEST_CKSUM_BYTES];
  TestDb *pDb = 0;
  int rc;

  pData = testDatasourceNew(&defn);

  testCopyLsmdb(zDb, zCopy);
  rc = tdb_lsm_open("test_no_recovery=1", zCopy, 0, &pDb);
  if( rc==0 ){
    ShmHeader *pHdr;
    lsm_db *db;
    testCksumDatabase(pDb, zCksum2);
    testCompareStr(zCksum, zCksum2, &rc);

    testWriteDatasourceRange(pDb, pData, 1, 10, &rc);
    testDeleteDatasourceRange(pDb, pData, 1, 10, &rc);

    /* Test that the two tree-headers are now consistent. */
    pHdr = getShmHeader(zCopy);
    if( rc==0 && memcmp(&pHdr->hdr1, &pHdr->hdr2, sizeof(pHdr->hdr1)) ){
      rc = 1;
    }
    testFree(pHdr);

    if( rc==0 ){
      int nBuf = 64;
      db = tdb_lsm(pDb);
      lsm_config(db, LSM_CONFIG_AUTOFLUSH, &nBuf);
      lsm_begin(db, 1);
      lsm_commit(db, 0);
      rc = lsm_work(db, 0, 0, 0);
    }

    testCksumDatabase(pDb, zCksum2);
    testCompareStr(zCksum, zCksum2, &rc);
  }

  testDatasourceFree(pData);
  testClose(&pDb);
  testDeleteLsmdb(zCopy);
  *pRc = rc;
}

static void doWriterCrash1(int *pRc){
  const int nWrite = 2000;
  const int nStep = 10;
  const int iWriteStart = 20000;
  int rc = 0;
  TestDb *pDb = 0;
  Datasource *pData = 0;

  rc = tdb_lsm_open("autowork=0", "testdb.lsm", 1, &pDb);
  if( rc==0 ){
    int iDot = 0;
    char zCksum[TEST_CKSUM_BYTES];
    int i;
    setupDatabase1(pDb, &pData);
    testCksumDatabase(pDb, zCksum);
    testBegin(pDb, 2, &rc);
    for(i=0; rc==0 && i<nWrite; i+=nStep){
      testCaseProgress(i, nWrite, testCaseNDot(), &iDot);
      testWriteDatasourceRange(pDb, pData, iWriteStart+i, nStep, &rc);
      doLiveRecovery("testdb.lsm", zCksum, &rc);
    }
  }
  testCommit(pDb, 0, &rc);
  testClose(&pDb);
  testDatasourceFree(pData);
  *pRc = rc;
}

/*
** This test case verifies that inconsistent tree-headers in shared-memory
** are resolved correctly. 
*/
static void doWriterCrash2(int *pRc){
  int rc = 0;
  TestDb *pDb = 0;
  Datasource *pData = 0;

  rc = tdb_lsm_open("autowork=0", "testdb.lsm", 1, &pDb);
  if( rc==0 ){
    ShmHeader *pHdr1;
    ShmHeader *pHdr2;
    char zCksum1[TEST_CKSUM_BYTES];
    char zCksum2[TEST_CKSUM_BYTES];

    pHdr1 = testMalloc(sizeof(ShmHeader));
    pHdr2 = testMalloc(sizeof(ShmHeader));
    setupDatabase1(pDb, &pData);

    /* Grab a copy of the shared-memory header. And the db checksum */
    testReadFile("testdb.lsm-shm", 0, (void *)pHdr1, sizeof(ShmHeader), &rc);
    testCksumDatabase(pDb, zCksum1);

    /* Modify the database */
    testBegin(pDb, 2, &rc);
    testWriteDatasourceRange(pDb, pData, 30000, 200, &rc);
    testCommit(pDb, 0, &rc);

    /* Grab a second copy of the shared-memory header. And the db checksum */
    testReadFile("testdb.lsm-shm", 0, (void *)pHdr2, sizeof(ShmHeader), &rc);
    testCksumDatabase(pDb, zCksum2);
    doLiveRecovery("testdb.lsm", zCksum2, &rc);

    /* If both tree-headers are valid, tree-header-1 is used. */
    memcpy(&pHdr2->hdr1, &pHdr1->hdr1, sizeof(pHdr1->hdr1));
    pHdr2->bWriter = 1;
    testWriteFile("testdb.lsm-shm", 0, (void *)pHdr2, sizeof(ShmHeader), &rc);
    doLiveRecovery("testdb.lsm", zCksum1, &rc);

    /* If both tree-headers are valid, tree-header-1 is used. */
    memcpy(&pHdr2->hdr1, &pHdr2->hdr2, sizeof(pHdr1->hdr1));
    memcpy(&pHdr2->hdr2, &pHdr1->hdr1, sizeof(pHdr1->hdr1));
    pHdr2->bWriter = 1;
    testWriteFile("testdb.lsm-shm", 0, (void *)pHdr2, sizeof(ShmHeader), &rc);
    doLiveRecovery("testdb.lsm", zCksum2, &rc);

    /* If tree-header 1 is invalid, tree-header-2 is used */
    memcpy(&pHdr2->hdr2, &pHdr2->hdr1, sizeof(pHdr1->hdr1));
    pHdr2->hdr1.aCksum[0] = 5;
    pHdr2->hdr1.aCksum[0] = 6;
    pHdr2->bWriter = 1;
    testWriteFile("testdb.lsm-shm", 0, (void *)pHdr2, sizeof(ShmHeader), &rc);
    doLiveRecovery("testdb.lsm", zCksum2, &rc);

    /* If tree-header 2 is invalid, tree-header-1 is used */
    memcpy(&pHdr2->hdr1, &pHdr2->hdr2, sizeof(pHdr1->hdr1));
    pHdr2->hdr2.aCksum[0] = 5;
    pHdr2->hdr2.aCksum[0] = 6;
    pHdr2->bWriter = 1;
    testWriteFile("testdb.lsm-shm", 0, (void *)pHdr2, sizeof(ShmHeader), &rc);
    doLiveRecovery("testdb.lsm", zCksum2, &rc);

    testFree(pHdr1);
    testFree(pHdr2);
    testClose(&pDb);
  }

  *pRc = rc;
}

void do_writer_crash_test(const char *zPattern, int *pRc){
  struct Test {
    const char *zName;
    void (*xFunc)(int *);
  } aTest[] = {
    { "writercrash1.lsm", doWriterCrash1 },
    { "writercrash2.lsm", doWriterCrash2 },
  };
  int i;
  for(i=0; i<ArraySize(aTest); i++){
    struct Test *p = &aTest[i];
    if( testCaseBegin(pRc, zPattern, p->zName) ){
      p->xFunc(pRc);
      testCaseFinish(*pRc);
    }
  }

}

#include "lsmtest.h"

#define DATA_SEQUENTIAL TEST_DATASOURCE_SEQUENCE
#define DATA_RANDOM     TEST_DATASOURCE_RANDOM

typedef struct Datatest4 Datatest4;

/*
** Test overview:
**
**   1. Insert (Datatest4.nRec) records into a database.
**
**   2. Repeat (Datatest4.nRepeat) times:
**
**      2a. Delete 2/3 of the records in the database.
**
**      2b. Run lsm_work(nMerge=1).
**
**      2c. Insert as many records as were deleted in 2a.
**
**      2d. Check database content is as expected.
**
**      2e. If (Datatest4.bReopen) is true, close and reopen the database.
*/
struct Datatest4 {
  /* Datasource definition */
  DatasourceDefn defn;

  int nRec;
  int nRepeat;
  int bReopen;
};

static void doDataTest4(
  const char *zSystem,            /* Database system to test */
  Datatest4 *p,                   /* Structure containing test parameters */
  int *pRc                        /* OUT: Error code */
){
  lsm_db *db = 0;
  TestDb *pDb;
  TestDb *pControl;
  Datasource *pData;
  int i;
  int rc = 0;
  int iDot = 0;

  int nRecOn3 = (p->nRec / 3);
  int iData = 0;

  /* Start the test case, open a database and allocate the datasource. */
  rc = testControlDb(&pControl);
  pDb = testOpen(zSystem, 1, &rc);
  pData = testDatasourceNew(&p->defn);
  if( rc==0 ) db = tdb_lsm(pDb);

  testWriteDatasourceRange(pControl, pData, iData, nRecOn3*3, &rc);
  testWriteDatasourceRange(pDb,      pData, iData, nRecOn3*3, &rc);

  for(i=0; rc==0 && i<p->nRepeat; i++){

    testDeleteDatasourceRange(pControl, pData, iData, nRecOn3*2, &rc);
    testDeleteDatasourceRange(pDb,      pData, iData, nRecOn3*2, &rc);

    if( db ){
      int nDone;
#if 0
      fprintf(stderr, "lsm_work() start...\n"); fflush(stderr);
#endif
      do {
        nDone = 0;
        rc = lsm_work(db, 1, (1<<30), &nDone);
      }while( rc==0 && nDone>0 );
#if 0 
      fprintf(stderr, "lsm_work() done...\n"); fflush(stderr);
#endif
    }

if( i+1<p->nRepeat ){
    iData += (nRecOn3*2);
    testWriteDatasourceRange(pControl, pData, iData+nRecOn3, nRecOn3*2, &rc);
    testWriteDatasourceRange(pDb,      pData, iData+nRecOn3, nRecOn3*2, &rc);

    testCompareDb(pData, nRecOn3*3, iData, pControl, pDb, &rc);

    /* If Datatest4.bReopen is true, close and reopen the database */
    if( p->bReopen ){
      testReopen(&pDb, &rc);
      if( rc==0 ) db = tdb_lsm(pDb);
    }
}

    /* Update the progress dots... */
    testCaseProgress(i, p->nRepeat, testCaseNDot(), &iDot);
  }

  testClose(&pDb);
  testClose(&pControl);
  testDatasourceFree(pData);
  testCaseFinish(rc);
  *pRc = rc;
}

static char *getName4(const char *zSystem, Datatest4 *pTest){
  char *zRet;
  char *zData;
  zData = testDatasourceName(&pTest->defn);
  zRet = testMallocPrintf("data4.%s.%s.%d.%d.%d", 
      zSystem, zData, pTest->nRec, pTest->nRepeat, pTest->bReopen
  );
  testFree(zData);
  return zRet;
}

void test_data_4(
  const char *zSystem,            /* Database system name */
  const char *zPattern,           /* Run test cases that match this pattern */
  int *pRc                        /* IN/OUT: Error code */
){
  Datatest4 aTest[] = {
      /* defn,                                 nRec, nRepeat, bReopen */
    { {DATA_RANDOM,     20,25,     500,600}, 10000,      10,       0   },
    { {DATA_RANDOM,     20,25,     500,600}, 10000,      10,       1   },
  };

  int i;

  for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){
    char *zName = getName4(zSystem, &aTest[i]);
    if( testCaseBegin(pRc, zPattern, "%s", zName) ){
      doDataTest4(zSystem, &aTest[i], pRc);
    }
    testFree(zName);
  }
}

#include "lsmtest.h"
#include "bt.h"

int do_bt(int nArg, char **azArg){
  struct Option {
    const char *zName;
    int bPgno;
    int eOpt;
  } aOpt [] = { 
    { "dbhdr",          0, BT_INFO_HDRDUMP },
    { "filename",       0, BT_INFO_FILENAME },
    { "block_freelist", 0, BT_INFO_BLOCK_FREELIST },
    { "page_freelist",  0, BT_INFO_PAGE_FREELIST },
    { "filename",       0, BT_INFO_FILENAME },
    { "page",           1, BT_INFO_PAGEDUMP },
    { "page_ascii",     1, BT_INFO_PAGEDUMP_ASCII },
    { "leaks",          0, BT_INFO_PAGE_LEAKS },
    { 0, 0 } 
  };
  int iOpt;
  int rc;
  bt_info buf;
  char *zOpt;
  char *zFile;

  bt_db *db = 0;

  if( nArg<2 ){
    testPrintUsage("FILENAME OPTION ...");
    return -1;
  }
  zFile = azArg[0];
  zOpt = azArg[1];

  rc = testArgSelect(aOpt, "option", zOpt, &iOpt);
  if( rc!=0 ) return rc;
  if( nArg!=2+aOpt[iOpt].bPgno ){
    testPrintFUsage("FILENAME %s %s", zOpt, aOpt[iOpt].bPgno ? "PGNO" : "");
    return -4;
  }

  rc = sqlite4BtNew(sqlite4_env_default(), 0, &db);
  if( rc!=SQLITE4_OK ){
    testPrintError("sqlite4BtNew() failed: %d", rc);
    return -2;
  }
  rc = sqlite4BtOpen(db, zFile);
  if( rc!=SQLITE4_OK ){
    testPrintError("sqlite4BtOpen() failed: %d", rc);
    return -3;
  }

  buf.eType = aOpt[iOpt].eOpt;
  buf.pgno = 0;
  sqlite4_buffer_init(&buf.output, 0);

  if( aOpt[iOpt].bPgno ){
    buf.pgno = (u32)atoi(azArg[2]);
  }

  rc = sqlite4BtControl(db, BT_CONTROL_INFO, &buf);
  if( rc!=SQLITE4_OK ){
    testPrintError("sqlite4BtControl() failed: %d\n", rc);
    return -4;
  }

  printf("%s\n", (char*)buf.output.p);
  sqlite4_buffer_clear(&buf.output);
  return 0;
}

#include "lsmtest.h"

struct Datasource {
  int eType;

  int nMinKey;
  int nMaxKey;
  int nMinVal;
  int nMaxVal;

  char *aKey;
  char *aVal;
};

void testDatasourceEntry(
  Datasource *p, 
  int iData, 
  void **ppKey, int *pnKey,
  void **ppVal, int *pnVal
){
  assert( (ppKey==0)==(pnKey==0) );
  assert( (ppVal==0)==(pnVal==0) );

  if( ppKey ){
    int nKey = 0;
    switch( p->eType ){
      case TEST_DATASOURCE_RANDOM: {
        int nRange = (1 + p->nMaxKey - p->nMinKey);
        nKey = (int)( testPrngValue((u32)iData) % nRange ) + p->nMinKey; 
        testPrngString((u32)iData, p->aKey, nKey);
        break;
      }
      case TEST_DATASOURCE_SEQUENCE:
        nKey = sprintf(p->aKey, "%012d", iData);
        break;
    }
    *ppKey = p->aKey;
    *pnKey = nKey;
  }
  if( ppVal ){
    u32 nVal = testPrngValue((u32)iData)%(1+p->nMaxVal-p->nMinVal)+p->nMinVal;
    testPrngString((u32)~iData, p->aVal, (int)nVal);
    *ppVal = p->aVal;
    *pnVal = (int)nVal;
  }
}

void testDatasourceFree(Datasource *p){
  testFree(p);
}

/*
** Return a pointer to a nul-terminated string that corresponds to the
** contents of the datasource-definition passed as the first argument.
** The caller should eventually free the returned pointer using testFree().
*/
char *testDatasourceName(const DatasourceDefn *p){
  char *zRet;
  zRet = testMallocPrintf("%s.(%d-%d).(%d-%d)",
      (p->eType==TEST_DATASOURCE_SEQUENCE ? "seq" : "rnd"),
      p->nMinKey, p->nMaxKey,
      p->nMinVal, p->nMaxVal
  );
  return zRet;
}

Datasource *testDatasourceNew(const DatasourceDefn *pDefn){
  Datasource *p;
  int nMinKey; 
  int nMaxKey;
  int nMinVal;
  int nMaxVal; 

  if( pDefn->eType==TEST_DATASOURCE_SEQUENCE ){
    nMinKey = 128;
    nMaxKey = 128;
  }else{
    nMinKey = MAX(0, pDefn->nMinKey);
    nMaxKey = MAX(nMinKey, pDefn->nMaxKey);
  }
  nMinVal = MAX(0, pDefn->nMinVal);
  nMaxVal = MAX(nMinVal, pDefn->nMaxVal);

  p = (Datasource *)testMalloc(sizeof(Datasource) + nMaxKey + nMaxVal + 1);
  p->eType = pDefn->eType;
  p->nMinKey = nMinKey;
  p->nMinVal = nMinVal;
  p->nMaxKey = nMaxKey;
  p->nMaxVal = nMaxVal;
  
  p->aKey = (char *)&p[1];
  p->aVal = &p->aKey[nMaxKey];
  return p;
};

#include "lsmtest.h"


int do_work(int nArg, char **azArg){
  struct Option {
    const char *zName;
  } aOpt [] = {
    { "-nmerge" },
    { "-nkb" },
    { 0 }
  };

  lsm_db *pDb;
  int rc;
  int i;
  const char *zDb;
  int nMerge = 1;
  int nKB = (1<<30);

  if( nArg==0 ) goto usage;
  zDb = azArg[nArg-1];
  for(i=0; i<(nArg-1); i++){
    int iSel;
    rc = testArgSelect(aOpt, "option", azArg[i], &iSel);
    if( rc ) return rc;
    switch( iSel ){
      case 0:
        i++;
        if( i==(nArg-1) ) goto usage;
        nMerge = atoi(azArg[i]);
        break;
      case 1:
        i++;
        if( i==(nArg-1) ) goto usage;
        nKB = atoi(azArg[i]);
        break;
    }
  }

  rc = lsm_new(0, &pDb);
  if( rc!=LSM_OK ){
    testPrintError("lsm_open(): rc=%d\n", rc);
  }else{
    rc = lsm_open(pDb, zDb);
    if( rc!=LSM_OK ){
      testPrintError("lsm_open(): rc=%d\n", rc);
    }else{
      int n = -1;
      lsm_config(pDb, LSM_CONFIG_BLOCK_SIZE, &n);
      n = n*2;
      lsm_config(pDb, LSM_CONFIG_AUTOCHECKPOINT, &n);

      rc = lsm_work(pDb, nMerge, nKB, 0);
      if( rc!=LSM_OK ){
        testPrintError("lsm_work(): rc=%d\n", rc);
      }
    }
  }
  if( rc==LSM_OK ){
    rc = lsm_checkpoint(pDb, 0);
  }

  lsm_close(pDb);
  return rc;

 usage:
  testPrintUsage("?-optimize? ?-n N? DATABASE");
  return -1;
}


/*
**   lsmtest show ?-config LSM-CONFIG? DATABASE ?COMMAND ?PGNO??
*/
int do_show(int nArg, char **azArg){
  lsm_db *pDb;
  int rc;
  const char *zDb;

  int eOpt = LSM_INFO_DB_STRUCTURE;
  unsigned int iPg = 0;
  int bConfig = 0;
  const char *zConfig = "";

  struct Option {
    const char *zName;
    int bConfig;
    int eOpt;
  } aOpt [] = { 
    { "array",       0, LSM_INFO_ARRAY_STRUCTURE },
    { "array-pages", 0, LSM_INFO_ARRAY_PAGES },
    { "blocksize",   1, LSM_CONFIG_BLOCK_SIZE },
    { "pagesize",    1, LSM_CONFIG_PAGE_SIZE },
    { "freelist",    0, LSM_INFO_FREELIST },
    { "page-ascii",  0, LSM_INFO_PAGE_ASCII_DUMP },
    { "page-hex",    0, LSM_INFO_PAGE_HEX_DUMP },
    { 0, 0 } 
  };

  char *z = 0; 
  int iDb = 0;                    /* Index of DATABASE in azArg[] */

  /* Check if there is a "-config" option: */
  if( nArg>2 && strlen(azArg[0])>1 
   && memcmp(azArg[0], "-config", strlen(azArg[0]))==0
  ){
    zConfig = azArg[1];
    iDb = 2;
  }
  if( nArg<(iDb+1) ) goto usage;

  if( nArg>(iDb+1) ){
    rc = testArgSelect(aOpt, "option", azArg[iDb+1], &eOpt);
    if( rc!=0 ) return rc;
    bConfig = aOpt[eOpt].bConfig;
    eOpt = aOpt[eOpt].eOpt;
    if( (bConfig==0 && eOpt==LSM_INFO_FREELIST)
     || (bConfig==1 && eOpt==LSM_CONFIG_BLOCK_SIZE)
     || (bConfig==1 && eOpt==LSM_CONFIG_PAGE_SIZE)
    ){
      if( nArg!=(iDb+2) ) goto usage;
    }else{
      if( nArg!=(iDb+3) ) goto usage;
      iPg = atoi(azArg[iDb+2]);
    }
  }
  zDb = azArg[iDb];

  rc = lsm_new(0, &pDb);
  tdb_lsm_configure(pDb, zConfig);
  if( rc!=LSM_OK ){
    testPrintError("lsm_new(): rc=%d\n", rc);
  }else{
    rc = lsm_open(pDb, zDb);
    if( rc!=LSM_OK ){
      testPrintError("lsm_open(): rc=%d\n", rc);
    }
  }

  if( rc==LSM_OK ){
    if( bConfig==0 ){
      switch( eOpt ){
        case LSM_INFO_DB_STRUCTURE:
        case LSM_INFO_FREELIST:
          rc = lsm_info(pDb, eOpt, &z);
          break;
        case LSM_INFO_ARRAY_STRUCTURE:
        case LSM_INFO_ARRAY_PAGES:
        case LSM_INFO_PAGE_ASCII_DUMP:
        case LSM_INFO_PAGE_HEX_DUMP:
          rc = lsm_info(pDb, eOpt, iPg, &z);
          break;
        default:
          assert( !"no chance" );
      }

      if( rc==LSM_OK ){
        printf("%s\n", z ? z : "");
        fflush(stdout);
      }
      lsm_free(lsm_get_env(pDb), z);
    }else{
      int iRes = -1;
      lsm_config(pDb, eOpt, &iRes);
      printf("%d\n", iRes);
      fflush(stdout);
    }
  }

  lsm_close(pDb);
  return rc;

 usage:
  testPrintUsage("DATABASE ?array|page-ascii|page-hex PGNO?");
  return -1;
}

/*
** SUMMARY
**
**   This file implements the 'io' subcommand of the test program. It is used
**   for testing the performance of various combinations of write() and fsync()
**   system calls. All operations occur on a single file, which may or may not
**   exist when a test is started.
**
**   A test consists of a series of commands. Each command is either a write
**   or an fsync. A write is specified as "<amount>@<offset>", where <amount>
**   is the amount of data written, and <offset> is the offset of the file
**   to write to. An <amount> or an <offset> is specified as an integer number
**   of bytes. Or, if postfixed with a "K", "M" or "G", an integer number of
**   KB, MB or GB, respectively. An fsync is simply "S". All commands are
**   case-insensitive.
**
**   Example test program:
**
**        2M@6M 1492K@4M S 4096@4K S
**
**   This program writes 2 MB of data starting at the offset 6MB offset of
**   the file, followed by 1492 KB of data written at the 4MB offset of the
**   file, followed by a call to fsync(), a write of 4KB of data at byte
**   offset 4096, and finally another call to fsync().
**
**   Commands may either be specified on the command line (one command per
**   command line argument) or read from stdin. Commands read from stdin
**   must be separated by white-space.
**
** COMMAND LINE INVOCATION
**
**   The sub-command implemented in this file must be invoked with at least
**   two arguments - the path to the file to write to and the page-size to
**   use for writing. If there are more than two arguments, then each
**   subsequent argument is assumed to be a test command. If there are exactly
**   two arguments, the test commands are read from stdin.
**
**   A write command does not result in a single call to system call write().
**   Instead, the specified region is written sequentially using one or
**   more calls to write(), each of which writes not more than one page of
**   data. For example, if the page-size is 4KB, the command "2M@6M" results
**   in 512 calls to write(), each of which writes 4KB of data.
**
** EXAMPLES
**
**   Two equivalent examples:
**
**     $ lsmtest io testfile.db 4KB 2M@6M 1492K@4M S 4096@4K S
**     3544K written in 129 ms
**     $ echo "2M@6M 1492K@4M S 4096@4K S" | lsmtest io testfile.db 4096 
**     3544K written in 127 ms
**
*/

#include "lsmtest.h"

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <ctype.h>

typedef struct IoContext IoContext;

struct IoContext {
  int fd;
  int nWrite;
};

/*
** As isspace(3)
*/
static int safe_isspace(char c){
  if( c&0x80) return 0;
  return isspace(c);
}

/*
** As isdigit(3)
*/
static int safe_isdigit(char c){
  if( c&0x80) return 0;
  return isdigit(c);
}

static i64 getNextSize(char *zIn, char **pzOut, int *pRc){
  i64 iRet = 0;
  if( *pRc==0 ){
    char *z = zIn;

    if( !safe_isdigit(*z) ){
      *pRc = 1;
      return 0;
    }

    /* Process digits */
    while( safe_isdigit(*z) ){
      iRet = iRet*10 + (*z - '0');
      z++;
    }

    /* Process suffix */
    switch( *z ){
      case 'k': case 'K':
        iRet = iRet * 1024;
        z++;
        break;

      case 'm': case 'M':
        iRet = iRet * 1024 * 1024;
        z++;
        break;

      case 'g': case 'G':
        iRet = iRet * 1024 * 1024 * 1024;
        z++;
        break;
    }

    if( pzOut ) *pzOut = z;
  }
  return iRet;
}

static int doOneCmd(
  IoContext *pCtx,
  u8 *aData,
  int pgsz,
  char *zCmd,
  char **pzOut
){
  char c;
  char *z = zCmd;

  while( safe_isspace(*z) ) z++;
  c = *z;

  if( c==0 ){
    if( pzOut ) *pzOut = z;
    return 0;
  }

  if( c=='s' || c=='S' ){
    if( pzOut ) *pzOut = &z[1];
    return fdatasync(pCtx->fd);
  }

  if( safe_isdigit(c) ){
    i64 iOff = 0;
    int nByte = 0;
    int rc = 0;
    int nPg;
    int iPg;

    nByte = getNextSize(z, &z, &rc);
    if( rc || *z!='@' ) goto bad_command;
    z++;
    iOff = getNextSize(z, &z, &rc);
    if( rc || (safe_isspace(*z)==0 && *z!='\0') ) goto bad_command;
    if( pzOut ) *pzOut = z;

    nPg = (nByte+pgsz-1) / pgsz;
    lseek(pCtx->fd, iOff, SEEK_SET);
    for(iPg=0; iPg<nPg; iPg++){
      write(pCtx->fd, aData, pgsz);
    }
    pCtx->nWrite += nByte/1024;

    return 0;
  }

 bad_command:
  testPrintError("unrecognized command: %s", zCmd);
  return 1;
}

static int readStdin(char **pzOut){
  int nAlloc = 128;
  char *zOut = 0;
  int nOut = 0;

  while( !feof(stdin) ){
    int nRead;

    nAlloc = nAlloc*2;
    zOut = realloc(zOut, nAlloc);
    nRead = fread(&zOut[nOut], 1, nAlloc-nOut-1, stdin);

    if( nRead==0 ) break;
    nOut += nRead;
    zOut[nOut] = '\0';
  }

  *pzOut = zOut;
  return 0;
}

int do_io(int nArg, char **azArg){
  IoContext ctx;
  int pgsz;
  char *zFile;
  char *zPgsz;
  int i;
  int rc = 0;

  char *zStdin = 0;
  char *z;

  u8 *aData;

  memset(&ctx, 0, sizeof(IoContext));
  if( nArg<2 ){
    testPrintUsage("FILE PGSZ ?CMD-1 ...?");
    return -1;
  }
  zFile = azArg[0];
  zPgsz = azArg[1];

  pgsz = getNextSize(zPgsz, 0, &rc);
  if( pgsz<=0 ){
    testPrintError("Ridiculous page size: %d", pgsz);
    return -1;
  }
  aData = malloc(pgsz);
  memset(aData, 0x77, pgsz);

  ctx.fd = open(zFile, O_RDWR|O_CREAT, 0644);
  if( ctx.fd<0 ){
    perror("open: ");
    return -1;
  }

  if( nArg==2 ){
    readStdin(&zStdin);
    testTimeInit();
    z = zStdin;
    while( *z && rc==0 ){
      rc = doOneCmd(&ctx, aData, pgsz, z, &z);
    }
  }else{
    testTimeInit();
    for(i=2; i<nArg; i++){
      rc = doOneCmd(&ctx, aData, pgsz, azArg[i], 0);
    }
  }

  printf("%dK written in %d ms\n", ctx.nWrite, testTimeGet());

  free(zStdin);
  close(ctx.fd);

  return 0;
}

#include <stdarg.h>
#include "lsmtest.h"
#include "stdio.h"
#include "assert.h"
#include "string.h"
#include "stdlib.h"

#include <sqlite3.h>

#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>


void test_failed(){ 
  assert( 0 );
  return; 
}

#define testSetError(rc) testSetErrorFunc(rc, pRc, __FILE__, __LINE__)
static void testSetErrorFunc(int rc, int *pRc, const char *zFile, int iLine){
  if( rc ){
    *pRc = rc;
    printf("FAILED (%s:%d) rc=%d ", zFile, iLine, rc);
    test_failed();
  }
}

static int lsm_memcmp(u8 *a, u8 *b, int c){
  int i;
  for(i=0; i<c; i++){
    if( a[i]!=b[i] ) return a[i] - b[i];
  }
  return 0;
}

/*
** A test utility function.
*/
void testFetch(
  TestDb *pDb,                    /* Database handle */
  void *pKey, int nKey,           /* Key to query database for */
  void *pVal, int nVal,           /* Expected value */
  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==0 ){
    void *pDbVal;
    int nDbVal;
    int rc;

    static int nCall = 0; nCall++;

    rc = tdb_fetch(pDb, pKey, nKey, &pDbVal, &nDbVal);
    testSetError(rc);
    if( rc==0 && (nVal!=nDbVal || (nVal>0 && lsm_memcmp(pVal, pDbVal, nVal))) ){
      testSetError(1);
    }
  }
}

void testWrite(
  TestDb *pDb,                    /* Database handle */
  void *pKey, int nKey,           /* Key to query database for */
  void *pVal, int nVal,           /* Value to write */
  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==0 ){
    int rc;
static int nCall = 0;
nCall++;
    rc = tdb_write(pDb, pKey, nKey, pVal, nVal);
    testSetError(rc);
  }
}
void testDelete(
  TestDb *pDb,                    /* Database handle */
  void *pKey, int nKey,           /* Key to query database for */
  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==0 ){
    int rc;
    *pRc = rc = tdb_delete(pDb, pKey, nKey);
    testSetError(rc);
  }
}
void testDeleteRange(
  TestDb *pDb,                    /* Database handle */
  void *pKey1, int nKey1,
  void *pKey2, int nKey2,
  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==0 ){
    int rc;
    *pRc = rc = tdb_delete_range(pDb, pKey1, nKey1, pKey2, nKey2);
    testSetError(rc);
  }
}

void testBegin(TestDb *pDb, int iTrans, int *pRc){
  if( *pRc==0 ){
    int rc;
    rc = tdb_begin(pDb, iTrans);
    testSetError(rc);
  }
}
void testCommit(TestDb *pDb, int iTrans, int *pRc){
  if( *pRc==0 ){
    int rc;
    rc = tdb_commit(pDb, iTrans);
    testSetError(rc);
  }
}
static void testRollback(TestDb *pDb, int iTrans, int *pRc){
  if( *pRc==0 ){
    int rc;
    rc = tdb_rollback(pDb, iTrans);
    testSetError(rc);
  }
}

void testWriteStr(
  TestDb *pDb,                    /* Database handle */
  const char *zKey,               /* Key to query database for */
  const char *zVal,               /* Value to write */
  int *pRc                        /* IN/OUT: Error code */
){
  int nVal = (zVal ? strlen(zVal) : 0);
  testWrite(pDb, (void *)zKey, strlen(zKey), (void *)zVal, nVal, pRc);
}

static void testDeleteStr(TestDb *pDb, const char *zKey, int *pRc){
  testDelete(pDb, (void *)zKey, strlen(zKey), pRc);
}

void testFetchStr(
  TestDb *pDb,                    /* Database handle */
  const char *zKey,               /* Key to query database for */
  const char *zVal,               /* Value to write */
  int *pRc                        /* IN/OUT: Error code */
){
  int nVal = (zVal ? strlen(zVal) : 0);
  testFetch(pDb, (void *)zKey, strlen(zKey), (void *)zVal, nVal, pRc);
}

void testFetchCompare(
  TestDb *pControl, 
  TestDb *pDb, 
  void *pKey, int nKey, 
  int *pRc
){
  int rc;
  void *pDbVal1;
  void *pDbVal2;
  int nDbVal1;
  int nDbVal2;

  static int nCall = 0;
  nCall++;

  rc = tdb_fetch(pControl, pKey, nKey, &pDbVal1, &nDbVal1);
  testSetError(rc);

  rc = tdb_fetch(pDb, pKey, nKey, &pDbVal2, &nDbVal2);
  testSetError(rc);

  if( *pRc==0 
   && (nDbVal1!=nDbVal2 || (nDbVal1>0 && memcmp(pDbVal1, pDbVal2, nDbVal1)))
  ){
    testSetError(1);
  }
}

typedef struct ScanResult ScanResult;
struct ScanResult {
  TestDb *pDb;

  int nRow;
  u32 cksum1;
  u32 cksum2;
  void *pKey1; int nKey1;
  void *pKey2; int nKey2;

  int bReverse;
  int nPrevKey;
  u8 aPrevKey[256];
};

static int keyCompare(void *pKey1, int nKey1, void *pKey2, int nKey2){
  int res;
  res = memcmp(pKey1, pKey2, MIN(nKey1, nKey2));
  if( res==0 ){
    res = nKey1 - nKey2;
  }
  return res;
}

int test_scan_debug = 0;

static void scanCompareCb(
  void *pCtx, 
  void *pKey, int nKey,
  void *pVal, int nVal
){
  ScanResult *p = (ScanResult *)pCtx;
  u8 *aKey = (u8 *)pKey;
  u8 *aVal = (u8 *)pVal;
  int i;

  if( test_scan_debug ){
    printf("%d: %.*s\n", p->nRow, nKey, (char *)pKey);
    fflush(stdout);
  }
#if 0
  if( test_scan_debug ) printf("%.20s\n", (char *)pVal);
#endif

#if 0
  /* Check tdb_fetch() matches */
  int rc = 0;
  testFetch(p->pDb, pKey, nKey, pVal, nVal, &rc);
  assert( rc==0 );
#endif

  /* Update the checksum data */
  p->nRow++;
  for(i=0; i<nKey; i++){
    p->cksum1 += ((int)aKey[i] << (i&0x0F));
    p->cksum2 += p->cksum1;
  }
  for(i=0; i<nVal; i++){
    p->cksum1 += ((int)aVal[i] << (i&0x0F));
    p->cksum2 += p->cksum1;
  }

  /* Check that the delivered row is not out of order. */
  if( nKey<(int)sizeof(p->aPrevKey) ){
    if( p->nPrevKey ){
      int res = keyCompare(p->aPrevKey, p->nPrevKey, pKey, nKey);
      if( (res<0 && p->bReverse) || (res>0 && p->bReverse==0) ){
        testPrintError("Returned key out of order at %s:%d\n", 
            __FILE__, __LINE__
        );
      }
    }

    p->nPrevKey = nKey;
    memcpy(p->aPrevKey, pKey, MIN(p->nPrevKey, nKey));
  }

  /* Check that the delivered row is within range. */
  if( p->pKey1 && (
      (memcmp(p->pKey1, pKey, MIN(p->nKey1, nKey))>0)
   || (memcmp(p->pKey1, pKey, MIN(p->nKey1, nKey))==0 && p->nKey1>nKey)
  )){
    testPrintError("Returned key too small at %s:%d\n", __FILE__, __LINE__);
  }
  if( p->pKey2 && (
      (memcmp(p->pKey2, pKey, MIN(p->nKey2, nKey))<0)
   || (memcmp(p->pKey2, pKey, MIN(p->nKey2, nKey))==0 && p->nKey2<nKey)
  )){
    testPrintError("Returned key too large at %s:%d\n", __FILE__, __LINE__);
  }

}

/*
** Scan the contents of the two databases. Check that they match.
*/
void testScanCompare(
  TestDb *pDb1,                   /* Control (trusted) database */
  TestDb *pDb2,                   /* Database being tested */
  int bReverse,
  void *pKey1, int nKey1, 
  void *pKey2, int nKey2, 
  int *pRc
){
  static int nCall = 0; nCall++;
  if( *pRc==0 ){
    ScanResult res1;
    ScanResult res2;
    void *pRes1 = (void *)&res1;
    void *pRes2 = (void *)&res2;

    memset(&res1, 0, sizeof(ScanResult));
    memset(&res2, 0, sizeof(ScanResult));

    res1.pDb = pDb1;
    res1.nKey1 = nKey1; res1.pKey1 = pKey1;
    res1.nKey2 = nKey2; res1.pKey2 = pKey2;
    res1.bReverse = bReverse;
    res2.pDb = pDb2;
    res2.nKey1 = nKey1; res2.pKey1 = pKey1;
    res2.nKey2 = nKey2; res2.pKey2 = pKey2;
    res2.bReverse = bReverse;

    tdb_scan(pDb1, pRes1, bReverse, pKey1, nKey1, pKey2, nKey2, scanCompareCb);
if( test_scan_debug ) printf("\n\n\n");
    tdb_scan(pDb2, pRes2, bReverse, pKey1, nKey1, pKey2, nKey2, scanCompareCb);
if( test_scan_debug ) printf("\n\n\n");

    if( res1.nRow!=res2.nRow 
     || res1.cksum1!=res2.cksum1 
     || res1.cksum2!=res2.cksum2
    ){
      printf("expected: %d %X %X\n", res1.nRow, res1.cksum1, res1.cksum2);
      printf("got:      %d %X %X\n", res2.nRow, res2.cksum1, res2.cksum2);
      testSetError(1);
      *pRc = 1;
    }
  }
}

void testClose(TestDb **ppDb){
  tdb_close(*ppDb);
  *ppDb = 0;
}

TestDb *testOpen(const char *zSystem, int bClear, int *pRc){
  TestDb *pDb = 0;
  if( *pRc==0 ){
    int rc;
    rc = tdb_open(zSystem, 0, bClear, &pDb);
    if( rc!=0 ){
      testSetError(rc);
      *pRc = rc;
    }
  }
  return pDb;
}

void testReopen(TestDb **ppDb, int *pRc){
  if( *pRc==0 ){
    const char *zLib;
    zLib = tdb_library_name(*ppDb);
    testClose(ppDb);
    *pRc = tdb_open(zLib, 0, 0, ppDb);
  }
}


static void testSystemSelect(const char *zSys, int *piSel, int *pRc){
  if( *pRc==0 ){
    struct SysName { const char *zName; } *aName;
    int nSys;
    int i;

    for(nSys=0; tdb_system_name(nSys); nSys++);
    aName = malloc(sizeof(struct SysName) * (nSys+1));
    for(i=0; i<=nSys; i++){
      aName[i].zName = tdb_system_name(i);
    }

    *pRc = testArgSelect(aName, "db", zSys, piSel);
    free(aName);
  }
}

char *testMallocVPrintf(const char *zFormat, va_list ap){
  int nByte;
  va_list copy;
  char *zRet;

  va_copy(copy, ap);
  nByte = vsnprintf(0, 0, zFormat, copy);
  va_end(copy);

  assert( nByte>=0 );
  zRet = (char *)testMalloc(nByte+1);
  vsnprintf(zRet, nByte+1, zFormat, ap);
  return zRet;
}

char *testMallocPrintf(const char *zFormat, ...){
  va_list ap;
  char *zRet;

  va_start(ap, zFormat);
  zRet = testMallocVPrintf(zFormat, ap);
  va_end(ap);

  return zRet;
}


/*
** A wrapper around malloc(3).
**
** This function should be used for all allocations made by test procedures.
** It has the following properties:
**
**   * Test code may assume that allocations may not fail.
**   * Returned memory is always zeroed.
**
** Allocations made using testMalloc() should be freed using testFree().
*/
void *testMalloc(int n){
  u8 *p = (u8*)malloc(n + 8);
  memset(p, 0, n+8);
  *(int*)p = n;
  return (void*)&p[8];
}

void *testMallocCopy(void *pCopy, int nByte){
  void *pRet = testMalloc(nByte);
  memcpy(pRet, pCopy, nByte);
  return pRet;
}

void *testRealloc(void *ptr, int n){
  if( ptr ){
    u8 *p = (u8*)ptr - 8;
    int nOrig =  *(int*)p;
    p = (u8*)realloc(p, n+8);
    if( nOrig<n ){
      memset(&p[8+nOrig], 0, n-nOrig);
    }
    *(int*)p = n;
    return (void*)&p[8];
  }
  return testMalloc(n);
}

/*
** Free an allocation made by an earlier call to testMalloc().
*/
void testFree(void *ptr){
  if( ptr ){
    u8 *p = (u8*)ptr - 8;
    memset(p, 0x55, *(int*)p + 8);
    free(p);
  }
}

/*
** String zPattern contains a glob pattern. Return true if zStr matches 
** the pattern, or false if it does not.
*/
int testGlobMatch(const char *zPattern, const char *zStr){
  int i = 0;
  int j = 0;

  while( zPattern[i] ){
    char p = zPattern[i];

    if( p=='*' || p=='%' ){
      do {
        if( testGlobMatch(&zPattern[i+1], &zStr[j]) ) return 1;
      }while( zStr[j++] );
      return 0;
    }

    if( zStr[j]==0 || (p!='?' && p!=zStr[j]) ){
      /* Match failed. */
      return 0;
    }

    j++;
    i++;
  }

  return (zPattern[i]==0 && zStr[j]==0);
}

/* 
** End of test utilities 
**************************************************************************/

int do_test(int nArg, char **azArg){
  int j;
  int rc;
  int nFail = 0;
  const char *zPattern = 0;

  if( nArg>1 ){
    testPrintError("Usage: test ?PATTERN?\n");
    return 1;
  }
  if( nArg==1 ){
    zPattern = azArg[0];
  }

  for(j=0; tdb_system_name(j); j++){
    rc = 0;

    test_data_1(tdb_system_name(j), zPattern, &rc);
    test_data_2(tdb_system_name(j), zPattern, &rc);
    test_data_3(tdb_system_name(j), zPattern, &rc);
    test_data_4(tdb_system_name(j), zPattern, &rc);
    test_rollback(tdb_system_name(j), zPattern, &rc);
    test_mc(tdb_system_name(j), zPattern, &rc);
    test_mt(tdb_system_name(j), zPattern, &rc);

    if( rc ) nFail++;
  }

  rc = 0;
  test_oom(zPattern, &rc);
  if( rc ) nFail++;

  rc = 0;
  test_api(zPattern, &rc);
  if( rc ) nFail++;

  rc = 0;
  do_crash_test(zPattern, &rc);
  if( rc ) nFail++;

  rc = 0;
  do_writer_crash_test(zPattern, &rc);
  if( rc ) nFail++;

  return (nFail!=0);
}

static lsm_db *configure_lsm_db(TestDb *pDb){
  lsm_db *pLsm;
  pLsm = tdb_lsm(pDb);
  if( pLsm ){
    tdb_lsm_config_str(pDb, "mmap=1 autowork=1 automerge=4 worker_automerge=4");
  }
  return pLsm;
}

typedef struct WriteHookEvent WriteHookEvent;
struct WriteHookEvent {
  i64 iOff;
  int nData;
  int nUs;
};
WriteHookEvent prev = {0, 0, 0};

static void flushPrev(FILE *pOut){
  if( prev.nData ){
    fprintf(pOut, "w %s %lld %d %d\n", "d", prev.iOff, prev.nData, prev.nUs);
    prev.nData = 0;
  }
}

static void do_speed_write_hook2(
  void *pCtx,
  int bLog,
  i64 iOff,
  int nData,
  int nUs
){
  FILE *pOut = (FILE *)pCtx;
  if( bLog ) return;

  if( prev.nData && nData && iOff==prev.iOff+prev.nData ){
    prev.nData += nData;
    prev.nUs += nUs;
  }else{
    flushPrev(pOut);
    if( nData==0 ){
      fprintf(pOut, "s %s 0 0 %d\n", (bLog ? "l" : "d"), nUs);
    }else{
      prev.iOff = iOff;
      prev.nData = nData;
      prev.nUs = nUs;
    }
  }
}

#define ST_REPEAT  0
#define ST_WRITE   1
#define ST_PAUSE   2
#define ST_FETCH   3
#define ST_SCAN    4
#define ST_NSCAN   5
#define ST_KEYSIZE 6
#define ST_VALSIZE 7


static void print_speed_test_help(){
  printf(
"\n"
"Repeat the following $repeat times:\n"
"  1. Insert $write key-value pairs. One transaction for each write op.\n"
"  2. Pause for $pause ms.\n"
"  3. Perform $fetch queries on the database.\n"
"\n"
"  Keys are $keysize bytes in size. Values are $valsize bytes in size\n"
"  Both keys and values are pseudo-randomly generated\n"
"\n"
"Options are:\n"
"  -repeat  $repeat                 (default value 10)\n"
"  -write   $write                  (default value 10000)\n"
"  -pause   $pause                  (default value 0)\n"
"  -fetch   $fetch                  (default value 0)\n"
"  -keysize $keysize                (default value 12)\n"
"  -valsize $valsize                (default value 100)\n"
"  -system  $system                 (default value \"lsm\")\n"
"\n"
);
}

int do_speed_test2(int nArg, char **azArg){
  struct Option {
    const char *zOpt;
    int eVal;
    int iDefault;
  } aOpt[] = {
    { "-repeat",  ST_REPEAT,    10},
    { "-write",   ST_WRITE,  10000},
    { "-pause",   ST_PAUSE,      0},
    { "-fetch",   ST_FETCH,      0},
    { "-scan",    ST_SCAN,       0},
    { "-nscan",   ST_NSCAN,      0},
    { "-keysize", ST_KEYSIZE,   12},
    { "-valsize", ST_VALSIZE,  100},
    { "-system",  -1,            0},
    { "help",     -2,            0},
    {0, 0, 0}
  };
  int i;
  int aParam[8];
  int rc = 0;
  int bReadonly = 0;
  int nContent = 0;

  TestDb *pDb;
  Datasource *pData;
  DatasourceDefn defn = { TEST_DATASOURCE_RANDOM, 0, 0, 0, 0 };
  char *zSystem = "";
  int bLsm = 1;
  FILE *pLog = 0;

#ifdef NDEBUG
  /* If NDEBUG is defined, disable the dynamic memory related checks in
  ** lsmtest_mem.c. They slow things down.  */
  testMallocUninstall(tdb_lsm_env());
#endif

  /* Initialize aParam[] with default values. */
  for(i=0; i<ArraySize(aOpt); i++){
    if( aOpt[i].zOpt ) aParam[aOpt[i].eVal] = aOpt[i].iDefault;
  }

  /* Process the command line switches. */
  for(i=0; i<nArg; i+=2){
    int iSel;
    rc = testArgSelect(aOpt, "switch", azArg[i], &iSel);
    if( rc ){
      return rc;
    }
    if( aOpt[iSel].eVal==-2 ){
      print_speed_test_help();
      return 0;
    }
    if( i+1==nArg ){
      testPrintError("option %s requires an argument\n", aOpt[iSel].zOpt);
      return 1;
    }
    if( aOpt[iSel].eVal>=0 ){
      aParam[aOpt[iSel].eVal] = atoi(azArg[i+1]);
    }else{
      int j;
      zSystem = azArg[i+1];
      bLsm = 0;
#if 0
      for(j=0; zSystem[j]; j++){
        if( zSystem[j]=='=' ) bLsm = 1;
      }
#endif
    }
  }
  
  printf("#");
  for(i=0; i<ArraySize(aOpt); i++){
    if( aOpt[i].zOpt ){
      if( aOpt[i].eVal>=0 ){
        printf(" %s=%d", &aOpt[i].zOpt[1], aParam[aOpt[i].eVal]);
      }else if( aOpt[i].eVal==-1 ){
        printf(" %s=\"%s\"", &aOpt[i].zOpt[1], zSystem);
      }
    }
  }
  printf("\n");

  defn.nMinKey = defn.nMaxKey = aParam[ST_KEYSIZE];
  defn.nMinVal = defn.nMaxVal = aParam[ST_VALSIZE];
  pData = testDatasourceNew(&defn);

  if( aParam[ST_WRITE]==0 ){
    bReadonly = 1;
  }

  if( bLsm ){
    rc = tdb_lsm_open(zSystem, "testdb.lsm", !bReadonly, &pDb);
  }else{
    pDb = testOpen(zSystem, !bReadonly, &rc);
  }
  if( rc!=0 ) return rc;
  if( bReadonly ){
    nContent = testCountDatabase(pDb);
  }

#if 0
  pLog = fopen("/tmp/speed.log", "w");
  tdb_lsm_write_hook(pDb, do_speed_write_hook2, (void *)pLog);
#endif

  for(i=0; i<aParam[ST_REPEAT] && rc==0; i++){
    int msWrite, msFetch;
    int iFetch;
    int nWrite = aParam[ST_WRITE];

    if( bReadonly ){
      msWrite = 0;
    }else{
      testTimeInit();
      testWriteDatasourceRange(pDb, pData, i*nWrite, nWrite, &rc);
      msWrite = testTimeGet();
      nContent += nWrite;
    }

    if( aParam[ST_PAUSE] ){
      if( aParam[ST_PAUSE]/1000 ) sleep(aParam[ST_PAUSE]/1000);
      if( aParam[ST_PAUSE]%1000 ) usleep(1000 * (aParam[ST_PAUSE]%1000));
    }

    if( aParam[ST_FETCH] ){
      testTimeInit();
      for(iFetch=0; iFetch<aParam[ST_FETCH]; iFetch++){
        int iKey = testPrngValue(i*nWrite+iFetch) % nContent;
#ifndef NDEBUG
        testDatasourceFetch(pDb, pData, iKey, &rc);
#else
        void *pKey; int nKey;           /* Database key to query for */
        void *pVal; int nVal;           /* Result of query */

        testDatasourceEntry(pData, iKey, &pKey, &nKey, 0, 0);
        rc = tdb_fetch(pDb, pKey, nKey, &pVal, &nVal);
        if( rc==0 && nVal<0 ) rc = 1;
        if( rc ) break;
#endif
      }
      msFetch = testTimeGet();
    }else{
      msFetch = 0;
    }

    if( i==(aParam[ST_REPEAT]-1) ){
      testTimeInit();
      testClose(&pDb);
      msWrite += testTimeGet();
    }

    printf("%d %d %d\n", i, msWrite, msFetch);
    fflush(stdout);
  }

  testClose(&pDb);
  testDatasourceFree(pData);

  if( pLog ){
    flushPrev(pLog);
    fclose(pLog);
  }
  return rc;
}

int do_speed_tests(int nArg, char **azArg){

  struct DbSystem {
    const char *zLibrary;
    const char *zColor;
  } aSys[] = {
    { "sqlite3",      "black" },
    { "leveldb",      "blue" },
    { "lsm",          "red" },
    { "lsm_mt2",      "orange" },
    { "lsm_mt3",      "purple" },
    { "kyotocabinet", "green" },
    {0, 0}
  };

  int i;
  int j;
  int rc;
  int nSleep = 0;                 /* ms of rest allowed between INSERT tests */
  int nRow = 0;                   /* Number of rows to insert into database */
  int nStep;                      /* Measure INSERT time after this many rows */
  int nSelStep;                   /* Measure SELECT time after this many rows */
  int nSelTest;                   /* Number of SELECTs to run for timing */
  int doReadTest = 1;
  int doWriteTest = 1;

  int *aTime;                     /* INSERT timing data */
  int *aWrite;                    /* Writes per nStep inserts */
  int *aSelTime;                  /* SELECT timing data */
  int isFirst = 1;
  int bSleep = 0;

  /* File to write gnuplot script to. */
  const char *zOut = "lsmtest_speed.gnuplot";

  u32 sys_mask = 0;

  testMallocUninstall(tdb_lsm_env());

  for(i=0; i<nArg; i++){
    struct Opt { 
      const char *zOpt; 
      int isSwitch;
    } aOpt[] = {
      { "sqlite3" , 0},
      { "leveldb" , 0},
      { "lsm" , 0},
      { "lsm_mt2" , 0},
      { "lsm_mt3" , 0},
      { "kyotocabinet" , 0},
      { "-rows"     , 1},
      { "-sleep"    , 2},
      { "-testmode" , 3},
      { "-out"      , 4},
      { 0, 0}
    };
    int iSel;

    rc = testArgSelect(aOpt, "argument", azArg[i], &iSel);
    if( rc ) return rc;

    if( aOpt[iSel].isSwitch ){
      i++;

      if( i>=nArg ){
        testPrintError("option %s requires an argument\n", aOpt[iSel].zOpt);
        return 1;
      }
      if( aOpt[iSel].isSwitch==1 ){
        nRow = atoi(azArg[i]);
      }
      if( aOpt[iSel].isSwitch==2 ){
        nSleep = atoi(azArg[i]);
      }
      if( aOpt[iSel].isSwitch==3 ){
        struct Mode {
          const char *zMode;
          int doReadTest;
          int doWriteTest;
        } aMode[] = {{"ro", 1, 0} , {"rw", 1, 1}, {"wo", 0, 1}, {0, 0, 0}};
        int iMode;
        rc = testArgSelect(aMode, "option", azArg[i], &iMode);
        if( rc ) return rc;
        doReadTest = aMode[iMode].doReadTest;
        doWriteTest = aMode[iMode].doWriteTest;
      }
      if( aOpt[iSel].isSwitch==4 ){
        /* The "-out FILE" switch. This option is used to specify a file to
        ** write the gnuplot script to. */
        zOut = azArg[i];
      }
    }else{
      /* A db name */
      rc = testArgSelect(aOpt, "system", azArg[i], &iSel);
      if( rc ) return rc;
      sys_mask |= (1<<iSel);
    }
  }

  if( sys_mask==0 ) sys_mask = (1 << 0) | (1 << 1) | (1 << 2) | (1 << 3);
  nRow = MAX(nRow, 100000);
  nStep = nRow/100;
  nSelStep = nRow/10;
  nSelTest = (nSelStep > 100000) ? 100000 : nSelStep;

  aTime = malloc(sizeof(int) * ArraySize(aSys) * nRow/nStep);
  aWrite = malloc(sizeof(int) * nRow/nStep);
  aSelTime = malloc(sizeof(int) * ArraySize(aSys) * nRow/nSelStep);

  /* This loop collects the INSERT speed data. */
  if( doWriteTest ){
    printf("Writing output to file \"%s\".\n",  zOut);

    for(j=0; aSys[j].zLibrary; j++){
      FILE *pLog = 0;
      TestDb *pDb;                  /* Database being tested */
      lsm_db *pLsm;
      int iDot = 0;
  
      if( ((1<<j)&sys_mask)==0 ) continue;
      if( bSleep && nSleep ) sqlite3_sleep(nSleep);
      bSleep = 1;

      testCaseBegin(&rc, 0, "speed.insert.%s", aSys[j].zLibrary);

      rc = tdb_open(aSys[j].zLibrary, 0, 1, &pDb);
      if( rc ) return rc;

      pLsm = configure_lsm_db(pDb);
#if 0
      pLog = fopen("/tmp/speed.log", "w");
      tdb_lsm_write_hook(pDb, do_speed_write_hook2, (void *)pLog);
#endif
  
      testTimeInit();
      for(i=0; i<nRow; i+=nStep){
        int iStep;
        int nWrite1, nWrite2;
        testCaseProgress(i, nRow, testCaseNDot(), &iDot);
        if( pLsm ) lsm_info(pLsm, LSM_INFO_NWRITE, &nWrite1);
        for(iStep=0; iStep<nStep; iStep++){
          u32 aKey[4];                  /* 16-byte key */
          u32 aVal[25];                 /* 100 byte value */
          testPrngArray(i+iStep, aKey, ArraySize(aKey));
          testPrngArray(i+iStep, aVal, ArraySize(aVal));
          rc = tdb_write(pDb, aKey, sizeof(aKey), aVal, sizeof(aVal));
        }
        aTime[(j*nRow+i)/nStep] = testTimeGet();
        if( pLsm ) lsm_info(pLsm, LSM_INFO_NWRITE, &nWrite2);
        aWrite[i/nStep] = nWrite2 - nWrite1;
      }

      tdb_close(pDb);
      if( pLog ) fclose(pLog);
      testCaseFinish(rc);
    }
  }

  /* This loop collects the SELECT speed data. */
  if( doReadTest ){
    for(j=0; aSys[j].zLibrary; j++){
      int iDot = 0;
      TestDb *pDb;                  /* Database being tested */

      if( ((1<<j)&sys_mask)==0 ) continue;
      if( bSleep && nSleep ) sqlite3_sleep(nSleep);
      bSleep = 1;

      testCaseBegin(&rc, 0, "speed.select.%s", aSys[j].zLibrary);

      if( doWriteTest ){
        rc = tdb_open(aSys[j].zLibrary, 0, 1, &pDb);
        if( rc ) return rc;
        configure_lsm_db(pDb);

        for(i=0; i<nRow; i+=nSelStep){
          int iStep;
          int iSel;
          testCaseProgress(i, nRow, testCaseNDot(), &iDot);
          for(iStep=0; iStep<nSelStep; iStep++){
            u32 aKey[4];                  /* 16-byte key */
            u32 aVal[25];                 /* 100 byte value */
            testPrngArray(i+iStep, aKey, ArraySize(aKey));
            testPrngArray(i+iStep, aVal, ArraySize(aVal));
            rc = tdb_write(pDb, aKey, sizeof(aKey), aVal, sizeof(aVal));
          }
    
          testTimeInit();
          for(iSel=0; iSel<nSelTest; iSel++){
            void *pDummy;
            int nDummy;
            u32 iKey;
            u32 aKey[4];                  /* 16-byte key */
    
            iKey = testPrngValue(iSel) % (i+nSelStep);
            testPrngArray(iKey, aKey, ArraySize(aKey));
            rc = tdb_fetch(pDb, aKey, sizeof(aKey), &pDummy, &nDummy);
          }
          aSelTime[(j*nRow+i)/nSelStep] = testTimeGet();
          tdb_fetch(pDb, 0, 0, 0, 0);
        }
      }else{
        int t;
        int iSel;

        rc = tdb_open(aSys[j].zLibrary, 0, 0, &pDb);
        configure_lsm_db(pDb);

        testTimeInit();
        for(iSel=0; rc==LSM_OK && iSel<nSelTest; iSel++){
          void *pDummy;
          int nDummy;
          u32 iKey;
          u32 aKey[4];                  /* 16-byte key */

          testCaseProgress(iSel, nSelTest, testCaseNDot(), &iDot);
    
          iKey = testPrngValue(iSel) % nRow;
          testPrngArray(iKey, aKey, ArraySize(aKey));
          rc = tdb_fetch(pDb, aKey, sizeof(aKey), &pDummy, &nDummy);

#ifndef NDEBUG
          u32 aVal[25];                 /* 100 byte value */
          testPrngArray(iKey, aVal, ArraySize(aVal));
          assert( nDummy==100 && memcmp(aVal, pDummy, 100)==0 );
#endif
        }
        if( rc!=LSM_OK ) return rc;

        t = testTimeGet();
        tdb_fetch(pDb, 0, 0, 0, 0);

        printf("%s: %d selects/second\n", 
            aSys[j].zLibrary, (int)((double)nSelTest*1000.0/t)
        );
      }

      tdb_close(pDb);
      testCaseFinish(rc);
    }
  }


  if( doWriteTest ){
    FILE *pOut = fopen(zOut, "w");
    if( !pOut ){
      printf("fopen(\"%s\", \"w\"): %s\n", zOut, strerror(errno));
      return 1;
    }

    fprintf(pOut, "set xlabel \"Rows Inserted\"\n");
    fprintf(pOut, "set ylabel \"Inserts per second\"\n");
    if( doReadTest ){
      fprintf(pOut, "set y2label \"Selects per second\"\n");
    }else if( sys_mask==(1<<2) ){
      fprintf(pOut, "set y2label \"Page writes per insert\"\n");
    }
    fprintf(pOut, "set yrange [0:*]\n");
    fprintf(pOut, "set y2range [0:*]\n");
    fprintf(pOut, "set xrange [%d:*]\n", MAX(nStep, nRow/20) );
    fprintf(pOut, "set ytics nomirror\n");
    fprintf(pOut, "set y2tics nomirror\n");
    fprintf(pOut, "set key box lw 0.01\n");
    fprintf(pOut, "plot ");
  
    for(j=0; aSys[j].zLibrary; j++){
      if( (1<<j)&sys_mask ){
        const char *zLib = aSys[j].zLibrary;
        fprintf(pOut, "%s\"-\" ti \"%s INSERT\" with lines lc rgb \"%s\" ", 
            (isFirst?"":", "), zLib, aSys[j].zColor
        );
        if( doReadTest ){
          fprintf(pOut, ", \"-\" ti \"%s SELECT\" "
                 "axis x1y2 with points lw 3 lc rgb \"%s\""
              , zLib, aSys[j].zColor
          );
        }
        isFirst = 0;
      }
    }

    assert( strcmp(aSys[2].zLibrary, "lsm")==0 );
    if( sys_mask==(1<<2) && !doReadTest ){
      fprintf(pOut, ", \"-\" ti \"lsm pages written\" "
        "axis x1y2 with boxes lw 1 lc rgb \"grey\""
      );
    }
  
    fprintf(pOut, "\n");
  
    for(j=0; aSys[j].zLibrary; j++){
      if( ((1<<j)&sys_mask)==0 ) continue;
      fprintf(pOut, "# Rows    Inserts per second\n");
      for(i=0; i<nRow; i+=nStep){
        int iTime = aTime[(j*nRow+i)/nStep];
        int ips = (int)((i+nStep)*1000.0 / (double)iTime);
        fprintf(pOut, "%d %d\n", i+nStep, ips);
      }
      fprintf(pOut, "end\n");
  
      if( doReadTest ){
        fprintf(pOut, "# Rows    Selects per second\n");
        for(i=0; i<nRow; i+=nSelStep){
          int sps = (int)(nSelTest*1000.0/(double)aSelTime[(j*nRow+i)/nSelStep]);
          fprintf(pOut, "%d %d\n", i+nSelStep, sps);
        }
        fprintf(pOut, "end\n");
      }else if( sys_mask==(1<<2) ){
        for(i=0; i<(nRow/nStep); i++){
          fprintf(pOut, "%d %f\n", i*nStep, (double)aWrite[i] / (double)nStep);
        }
        fprintf(pOut, "end\n");
      }
    }
  
    fprintf(pOut, "pause -1\n");
    fclose(pOut);
  }

  free(aTime);
  free(aSelTime);
  free(aWrite);
  testMallocInstall(tdb_lsm_env());
  return 0;
}

/*
** Usage: lsmtest random ?N?
**
** This command prints a sequence of zero or more numbers from the PRNG
** system to stdout. If the "N" argument is missing, values the first 10
** values (i=0, i=1, ... i=9) are printed. Otherwise, the first N.
**
** This was added to verify that the PRNG values do not change between
** runs of the lsmtest program.
*/
int do_random_tests(int nArg, char **azArg){
  int i;
  int nRand;
  if( nArg==0 ){
    nRand = 10;
  }else if( nArg==1 ){
    nRand = atoi(azArg[0]);
  }else{
    testPrintError("Usage: random ?N?\n");
    return -1;
  }
  for(i=0; i<nRand; i++){
    printf("0x%x\n", testPrngValue(i));
  }
  return 0;
}

static int testFormatSize(char *aBuf, int nBuf, i64 nByte){
  int res;
  if( nByte<(1<<10) ){
    res = snprintf(aBuf, nBuf, "%d byte", (int)nByte);
  }else if( nByte<(1<<20) ){
    res = snprintf(aBuf, nBuf, "%dK", (int)(nByte/(1<<10)));
  }else{
    res = snprintf(aBuf, nBuf, "%dM", (int)(nByte/(1<<20)));
  }
  return res;
}

static i64 testReadSize(char *z){
  int n = strlen(z);
  char c = z[n-1];
  i64 nMul = 1;

  switch( c ){
    case 'g': case 'G':
      nMul = (1<<30);
      break;

    case 'm': case 'M':
      nMul = (1<<20);
      break;

    case 'k': case 'K':
      nMul = (1<<10);
      break;

    default:
      nMul = 1;
  }

  return nMul * (i64)atoi(z);
} 

/*
** Usage: lsmtest writespeed FILESIZE BLOCKSIZE SYNCSIZE
*/
static int do_writer_test(int nArg, char **azArg){
  int nBlock;
  int nSize;
  int i;
  int fd;
  int ms;
  char aFilesize[32];
  char aBlockSize[32];

  char *aPage;
  int *aOrder;
  int nSync;

  i64 filesize;
  i64 blocksize;
  i64 syncsize;
  int nPage = 4096;

  /* How long to sleep before running a trial (in ms). */
#if 0
  const int nSleep = 10000;
#endif
  const int nSleep = 0;

  if( nArg!=3 ){
    testPrintUsage("FILESIZE BLOCKSIZE SYNCSIZE");
    return -1;
  }

  filesize = testReadSize(azArg[0]);
  blocksize = testReadSize(azArg[1]);
  syncsize = testReadSize(azArg[2]);

  nBlock = (int)(filesize / blocksize);
  nSize = (int)blocksize;
  nSync = (int)(syncsize / blocksize);

  aPage = (char *)malloc(4096);
  aOrder = (int *)malloc(nBlock * sizeof(int));
  for(i=0; i<nBlock; i++) aOrder[i] = i;
  for(i=0; i<(nBlock*25); i++){
    int tmp;
    u32 a = testPrngValue(i);
    u32 b = testPrngValue(a);
    a = a % nBlock;
    b = b % nBlock;
    tmp = aOrder[a];
    aOrder[a] = aOrder[b];
    aOrder[b] = tmp;
  }

  testFormatSize(aFilesize, sizeof(aFilesize), (i64)nBlock * (i64)nSize);
  testFormatSize(aBlockSize, sizeof(aFilesize), nSize);

  printf("Testing writing a %s file using %s blocks. ", aFilesize, aBlockSize);
  if( nSync==1 ){
    printf("Sync after each block.\n");
  }else{
    printf("Sync after each %d blocks.\n", nSync);
  }

  printf("Preparing file... ");
  fflush(stdout);
  unlink("writer.out");
  fd = open("writer.out", O_RDWR|O_CREAT, 0664);
  if( fd<0 ){
    testPrintError("open(): %d - %s\n", errno, strerror(errno));
    return -1;
  }
  testTimeInit();
  for(i=0; i<nBlock; i++){
    int iPg;
    memset(aPage, i&0xFF, nPage);
    for(iPg=0; iPg<(nSize/nPage); iPg++){
      write(fd, aPage, nPage);
    }
  }
  fsync(fd);
  printf("ok (%d ms)\n", testTimeGet());

  for(i=0; i<5; i++){
    int j;

    sqlite3_sleep(nSleep);
    printf("Now writing sequentially...  ");
    fflush(stdout);

    lseek(fd, 0, SEEK_SET);
    testTimeInit();
    for(j=0; j<nBlock; j++){
      int iPg;
      if( ((j+1)%nSync)==0 ) fdatasync(fd);
      memset(aPage, j&0xFF, nPage);
      for(iPg=0; iPg<(nSize/nPage); iPg++){
        write(fd, aPage, nPage);
      }
    }
    fdatasync(fd);
    ms = testTimeGet();
    printf("%d ms\n", ms);
    sqlite3_sleep(nSleep);
    printf("Now in an arbitrary order... ");

    fflush(stdout);
    testTimeInit();
    for(j=0; j<nBlock; j++){
      int iPg;
      if( ((j+1)%nSync)==0 ) fdatasync(fd);
      lseek(fd, aOrder[j]*nSize, SEEK_SET);
      memset(aPage, j&0xFF, nPage);
      for(iPg=0; iPg<(nSize/nPage); iPg++){
        write(fd, aPage, nPage);
      }
    }
    fdatasync(fd);
    ms = testTimeGet();
    printf("%d ms\n", ms);
  }

  close(fd);
  free(aPage);
  free(aOrder);

  return 0;
}

static void do_insert_work_hook(lsm_db *db, void *p){
  char *z = 0;
  lsm_info(db, LSM_INFO_DB_STRUCTURE, &z);
  if( z ){
    printf("%s\n", z);
    fflush(stdout);
    lsm_free(lsm_get_env(db), z);
  }

  unused_parameter(p);
}

typedef struct InsertWriteHook InsertWriteHook;
struct InsertWriteHook {
  FILE *pOut;
  int bLog;
  i64 iOff;
  int nData;
};

static void flushHook(InsertWriteHook *pHook){
  if( pHook->nData ){
    fprintf(pHook->pOut, "write %s %d %d\n", 
        (pHook->bLog ? "log" : "db"), (int)pHook->iOff, pHook->nData
    );
    pHook->nData = 0;
    fflush(pHook->pOut);
  }
}

static void do_insert_write_hook(
  void *pCtx,
  int bLog,
  i64 iOff,
  int nData,
  int nUs
){
  InsertWriteHook *pHook = (InsertWriteHook *)pCtx;
  if( bLog ) return;

  if( nData==0 ){
    flushHook(pHook);
    fprintf(pHook->pOut, "sync %s\n", (bLog ? "log" : "db"));
  }else if( pHook->nData 
         && bLog==pHook->bLog 
         && iOff==(pHook->iOff+pHook->nData) 
  ){
    pHook->nData += nData;
  }else{
    flushHook(pHook);
    pHook->bLog = bLog;
    pHook->iOff = iOff;
    pHook->nData = nData;
  }
}

static int do_replay(int nArg, char **azArg){
  char aBuf[4096];
  FILE *pInput;
  FILE *pClose = 0;
  const char *zDb;

  lsm_env *pEnv;
  lsm_file *pOut;
  int rc;

  if( nArg!=2 ){
    testPrintError("Usage: replay WRITELOG FILE\n");
    return 1;
  }

  if( strcmp(azArg[0], "-")==0 ){
    pInput = stdin;
  }else{
    pClose = pInput = fopen(azArg[0], "r");
  }
  zDb = azArg[1];
  pEnv = tdb_lsm_env();
  rc = pEnv->xOpen(pEnv, zDb, 0, &pOut);
  if( rc!=LSM_OK ) return rc;

  while( feof(pInput)==0 ){
    char zLine[80];
    fgets(zLine, sizeof(zLine)-1, pInput);
    zLine[sizeof(zLine)-1] = '\0';

    if( 0==memcmp("sync db", zLine, 7) ){
      rc = pEnv->xSync(pOut);
      if( rc!=0 ) break;
    }else{
      int iOff;
      int nData;
      int nMatch;
      nMatch = sscanf(zLine, "write db %d %d", &iOff, &nData);
      if( nMatch==2 ){
        int i;
        for(i=0; i<nData; i+=sizeof(aBuf)){
          memset(aBuf, i&0xFF, sizeof(aBuf));
          rc = pEnv->xWrite(pOut, iOff+i, aBuf, sizeof(aBuf));
          if( rc!=0 ) break;
        }
      }
    }
  }
  if( pClose ) fclose(pClose);
  pEnv->xClose(pOut);

  return rc;
}

static int do_insert(int nArg, char **azArg){
  const char *zDb = "lsm";
  TestDb *pDb = 0;
  int i;
  int rc;
  const int nRow = 1 * 1000 * 1000;

  DatasourceDefn defn = { TEST_DATASOURCE_RANDOM, 8, 15, 80, 150 };
  Datasource *pData = 0;

  if( nArg>1 ){
    testPrintError("Usage: insert ?DATABASE?\n");
    return 1;
  }
  if( nArg==1 ){ zDb = azArg[0]; }

  testMallocUninstall(tdb_lsm_env());
  for(i=0; zDb[i] && zDb[i]!='='; i++);
  if( zDb[i] ){
    rc = tdb_lsm_open(zDb, "testdb.lsm", 1, &pDb);
  }else{
    rc = tdb_open(zDb, 0, 1, &pDb);
  }

  if( rc!=0 ){
    testPrintError("Error opening db \"%s\": %d\n", zDb, rc);
  }else{
    InsertWriteHook hook;
    memset(&hook, 0, sizeof(hook));
    hook.pOut = fopen("writelog.txt", "w");

    pData = testDatasourceNew(&defn);
    tdb_lsm_config_work_hook(pDb, do_insert_work_hook, 0);
    tdb_lsm_write_hook(pDb, do_insert_write_hook, (void *)&hook);

    if( rc==0 ){
      for(i=0; i<nRow; i++){
        void *pKey; int nKey;     /* Database key to insert */
        void *pVal; int nVal;     /* Database value to insert */
        testDatasourceEntry(pData, i, &pKey, &nKey, &pVal, &nVal);
        tdb_write(pDb, pKey, nKey, pVal, nVal);
      }
    }

    testDatasourceFree(pData);
    tdb_close(pDb);
    flushHook(&hook);
    fclose(hook.pOut);
  }
  testMallocInstall(tdb_lsm_env());

  return rc;
}

static int st_do_show(int a, char **b)      { return do_show(a, b); }
static int st_do_work(int a, char **b)      { return do_work(a, b); }
static int st_do_io(int a, char **b)        { return do_io(a, b); }

#ifdef __linux__
#include <sys/time.h>
#include <sys/resource.h>

static void lsmtest_rusage_report(void){
  struct rusage r;
  memset(&r, 0, sizeof(r));

  getrusage(RUSAGE_SELF, &r);
  printf("# getrusage: { ru_maxrss %d ru_oublock %d ru_inblock %d }\n", 
      (int)r.ru_maxrss, (int)r.ru_oublock, (int)r.ru_inblock
  );
}
#else
static void lsmtest_rusage_report(void){
  /* no-op */
}
#endif

int main(int argc, char **argv){
  struct TestFunc {
    const char *zName;
    int bRusageReport;
    int (*xFunc)(int, char **);
  } aTest[] = {
    {"random",      1, do_random_tests},
    {"writespeed",  1, do_writer_test},
    {"io",          1, st_do_io},

    {"insert",      1, do_insert},
    {"replay",      1, do_replay},

    {"speed",       1, do_speed_tests},
    {"speed2",      1, do_speed_test2},
    {"show",        0, st_do_show},
    {"work",        1, st_do_work},
    {"test",        1, do_test},

    {0, 0}
  };
  int rc;                         /* Return Code */
  int iFunc;                      /* Index into aTest[] */

  int nLeakAlloc = 0;             /* Allocations leaked by lsm */
  int nLeakByte = 0;              /* Bytes leaked by lsm */

#ifdef LSM_DEBUG_MEM
  FILE *pReport = 0;              /* lsm malloc() report file */
  const char *zReport = "malloc.txt generated";
#else
  const char *zReport = "malloc.txt NOT generated";
#endif

  testMallocInstall(tdb_lsm_env());

  if( argc<2 ){
    testPrintError("Usage: %s sub-command ?args...?\n", argv[0]);
    return -1;
  }

  /* Initialize error reporting */
  testErrorInit(argc, argv);

  /* Initialize PRNG system */
  testPrngInit();

  rc = testArgSelect(aTest, "sub-command", argv[1], &iFunc);
  if( rc==0 ){
    rc = aTest[iFunc].xFunc(argc-2, &argv[2]);
  }

#ifdef LSM_DEBUG_MEM
  pReport = fopen("malloc.txt", "w");
  testMallocCheck(tdb_lsm_env(), &nLeakAlloc, &nLeakByte, pReport);
  fclose(pReport);
#else
  testMallocCheck(tdb_lsm_env(), &nLeakAlloc, &nLeakByte, 0);
#endif

  if( nLeakAlloc ){
    testPrintError("Leaked %d bytes in %d allocations (%s)\n", 
        nLeakByte, nLeakAlloc, zReport
    );
    if( rc==0 ) rc = -1;
  }
  testMallocUninstall(tdb_lsm_env());

  if( aTest[iFunc].bRusageReport ){
    lsmtest_rusage_report();
  }
  return rc;
}

#include <stdio.h>
#include <assert.h>
#include <string.h>

#define ArraySize(x) ((int)(sizeof(x) / sizeof((x)[0])))

#define MIN(x,y) ((x)<(y) ? (x) : (y))

typedef unsigned int  u32;
typedef unsigned char u8;
typedef long long int i64;
typedef unsigned long long int u64;

#if defined(__GLIBC__) && defined(LSM_DEBUG_MEM)
  extern int backtrace(void**,int);
  extern void backtrace_symbols_fd(void*const*,int,int);
# define TM_BACKTRACE 12
#else
# define backtrace(A,B) 1
# define backtrace_symbols_fd(A,B,C)
#endif


typedef struct TmBlockHdr TmBlockHdr;
typedef struct TmAgg TmAgg;
typedef struct TmGlobal TmGlobal;

struct TmGlobal {
  /* Linked list of all currently outstanding allocations. And a table of
  ** all allocations, past and present, indexed by backtrace() info.  */
  TmBlockHdr *pFirst;
#ifdef TM_BACKTRACE
  TmAgg *aHash[10000];
#endif

  /* Underlying malloc/realloc/free functions */
  void *(*xMalloc)(int);          /* underlying malloc(3) function */
  void *(*xRealloc)(void *, int); /* underlying realloc(3) function */
  void (*xFree)(void *);          /* underlying free(3) function */

  /* Mutex to protect pFirst and aHash */
  void (*xEnterMutex)(TmGlobal*); /* Call this to enter the mutex */
  void (*xLeaveMutex)(TmGlobal*); /* Call this to leave mutex */
  void (*xDelMutex)(TmGlobal*);   /* Call this to delete mutex */
  void *pMutex;                   /* Mutex handle */

  void *xSaveMalloc;
  void *xSaveRealloc;
  void *xSaveFree;

  /* OOM injection scheduling. If nCountdown is greater than zero when a 
  ** malloc attempt is made, it is decremented. If this means nCountdown 
  ** transitions from 1 to 0, then the allocation fails. If bPersist is true 
  ** when this happens, nCountdown is then incremented back to 1 (so that the 
  ** next attempt fails too).  
  */
  int nCountdown;
  int bPersist;
  int bEnable;
  void (*xHook)(void *);
  void *pHookCtx;
};

struct TmBlockHdr {
  TmBlockHdr *pNext;
  TmBlockHdr *pPrev;
  int nByte;
#ifdef TM_BACKTRACE
  TmAgg *pAgg;
#endif
  u32 iForeGuard;
};

#ifdef TM_BACKTRACE
struct TmAgg {
  int nAlloc;                     /* Number of allocations at this path */
  int nByte;                      /* Total number of bytes allocated */
  int nOutAlloc;                  /* Number of outstanding allocations */
  int nOutByte;                   /* Number of outstanding bytes */
  void *aFrame[TM_BACKTRACE];     /* backtrace() output */
  TmAgg *pNext;                   /* Next object in hash-table collision */
};
#endif

#define FOREGUARD 0x80F5E153
#define REARGUARD 0xE4676B53
static const u32 rearguard = REARGUARD;

#define ROUND8(x) (((x)+7)&~7)

#define BLOCK_HDR_SIZE (ROUND8( sizeof(TmBlockHdr) ))

static void lsmtest_oom_error(void){
  static int nErr = 0;
  nErr++;
}

static void tmEnterMutex(TmGlobal *pTm){
  pTm->xEnterMutex(pTm);
}
static void tmLeaveMutex(TmGlobal *pTm){
  pTm->xLeaveMutex(pTm);
}

static void *tmMalloc(TmGlobal *pTm, int nByte){
  TmBlockHdr *pNew;               /* New allocation header block */
  u8 *pUser;                      /* Return value */
  int nReq;                       /* Total number of bytes requested */

  assert( sizeof(rearguard)==4 );
  nReq = BLOCK_HDR_SIZE + nByte + 4;
  pNew = (TmBlockHdr *)pTm->xMalloc(nReq);
  memset(pNew, 0, sizeof(TmBlockHdr));

  tmEnterMutex(pTm);
  assert( pTm->nCountdown>=0 );
  assert( pTm->bPersist==0 || pTm->bPersist==1 );

  if( pTm->bEnable && pTm->nCountdown==1 ){
    /* Simulate an OOM error. */
    lsmtest_oom_error();
    pTm->xFree(pNew);
    pTm->nCountdown = pTm->bPersist;
    if( pTm->xHook ) pTm->xHook(pTm->pHookCtx);
    pUser = 0;
  }else{
    if( pTm->bEnable && pTm->nCountdown ) pTm->nCountdown--;

    pNew->iForeGuard = FOREGUARD;
    pNew->nByte = nByte;
    pNew->pNext = pTm->pFirst;

    if( pTm->pFirst ){
      pTm->pFirst->pPrev = pNew;
    }
    pTm->pFirst = pNew;

    pUser = &((u8 *)pNew)[BLOCK_HDR_SIZE];
    memset(pUser, 0x56, nByte);
    memcpy(&pUser[nByte], &rearguard, 4);

#ifdef TM_BACKTRACE
    {
      TmAgg *pAgg;
      int i;
      u32 iHash = 0;
      void *aFrame[TM_BACKTRACE];
      memset(aFrame, 0, sizeof(aFrame));
      backtrace(aFrame, TM_BACKTRACE);

      for(i=0; i<ArraySize(aFrame); i++){
        iHash += (u64)(aFrame[i]) + (iHash<<3);
      }
      iHash = iHash % ArraySize(pTm->aHash);

      for(pAgg=pTm->aHash[iHash]; pAgg; pAgg=pAgg->pNext){
        if( memcmp(pAgg->aFrame, aFrame, sizeof(aFrame))==0 ) break;
      }
      if( !pAgg ){
        pAgg = (TmAgg *)pTm->xMalloc(sizeof(TmAgg));
        memset(pAgg, 0, sizeof(TmAgg));
        memcpy(pAgg->aFrame, aFrame, sizeof(aFrame));
        pAgg->pNext = pTm->aHash[iHash];
        pTm->aHash[iHash] = pAgg;
      }
      pAgg->nAlloc++;
      pAgg->nByte += nByte;
      pAgg->nOutAlloc++;
      pAgg->nOutByte += nByte;
      pNew->pAgg = pAgg;
    }
#endif
  }

  tmLeaveMutex(pTm);
  return pUser;
}

static void tmFree(TmGlobal *pTm, void *p){
  if( p ){
    TmBlockHdr *pHdr;
    u8 *pUser = (u8 *)p;

    tmEnterMutex(pTm);
    pHdr = (TmBlockHdr *)&pUser[BLOCK_HDR_SIZE * -1];
    assert( pHdr->iForeGuard==FOREGUARD );
    assert( 0==memcmp(&pUser[pHdr->nByte], &rearguard, 4) );

    if( pHdr->pPrev ){
      assert( pHdr->pPrev->pNext==pHdr );
      pHdr->pPrev->pNext = pHdr->pNext;
    }else{
      assert( pHdr==pTm->pFirst );
      pTm->pFirst = pHdr->pNext;
    }
    if( pHdr->pNext ){
      assert( pHdr->pNext->pPrev==pHdr );
      pHdr->pNext->pPrev = pHdr->pPrev;
    }

#ifdef TM_BACKTRACE
    pHdr->pAgg->nOutAlloc--;
    pHdr->pAgg->nOutByte -= pHdr->nByte;
#endif

    tmLeaveMutex(pTm);
    memset(pUser, 0x58, pHdr->nByte);
    memset(pHdr, 0x57, sizeof(TmBlockHdr));
    pTm->xFree(pHdr);
  }
}

static void *tmRealloc(TmGlobal *pTm, void *p, int nByte){
  void *pNew;

  pNew = tmMalloc(pTm, nByte);
  if( pNew && p ){
    TmBlockHdr *pHdr;
    u8 *pUser = (u8 *)p;
    pHdr = (TmBlockHdr *)&pUser[BLOCK_HDR_SIZE * -1];
    memcpy(pNew, p, MIN(nByte, pHdr->nByte));
    tmFree(pTm, p);
  }
  return pNew;
}

static void tmMallocOom(
  TmGlobal *pTm, 
  int nCountdown, 
  int bPersist,
  void (*xHook)(void *),
  void *pHookCtx
){
  assert( nCountdown>=0 );
  assert( bPersist==0 || bPersist==1 );
  pTm->nCountdown = nCountdown;
  pTm->bPersist = bPersist;
  pTm->xHook = xHook;
  pTm->pHookCtx = pHookCtx;
  pTm->bEnable = 1;
}

static void tmMallocOomEnable(
  TmGlobal *pTm, 
  int bEnable
){
  pTm->bEnable = bEnable;
}

static void tmMallocCheck(
  TmGlobal *pTm,
  int *pnLeakAlloc,
  int *pnLeakByte,
  FILE *pFile
){
  TmBlockHdr *pHdr;
  int nLeak = 0;
  int nByte = 0;

  if( pTm==0 ) return;

  for(pHdr=pTm->pFirst; pHdr; pHdr=pHdr->pNext){
    nLeak++; 
    nByte += pHdr->nByte;
  }
  if( pnLeakAlloc ) *pnLeakAlloc = nLeak;
  if( pnLeakByte ) *pnLeakByte = nByte;

#ifdef TM_BACKTRACE
  if( pFile ){
    int i;
    fprintf(pFile, "LEAKS\n");
    for(i=0; i<ArraySize(pTm->aHash); i++){
      TmAgg *pAgg;
      for(pAgg=pTm->aHash[i]; pAgg; pAgg=pAgg->pNext){
        if( pAgg->nOutAlloc ){
          int j;
          fprintf(pFile, "%d %d ", pAgg->nOutByte, pAgg->nOutAlloc);
          for(j=0; j<TM_BACKTRACE; j++){
            fprintf(pFile, "%p ", pAgg->aFrame[j]);
          }
          fprintf(pFile, "\n");
        }
      }
    }
    fprintf(pFile, "\nALLOCATIONS\n");
    for(i=0; i<ArraySize(pTm->aHash); i++){
      TmAgg *pAgg;
      for(pAgg=pTm->aHash[i]; pAgg; pAgg=pAgg->pNext){
        int j;
        fprintf(pFile, "%d %d ", pAgg->nByte, pAgg->nAlloc);
        for(j=0; j<TM_BACKTRACE; j++) fprintf(pFile, "%p ", pAgg->aFrame[j]);
        fprintf(pFile, "\n");
      }
    }
  }
#else
  (void)pFile;
#endif
}


#include "lsm.h"
#include "stdlib.h"

typedef struct LsmMutex LsmMutex;
struct LsmMutex {
  lsm_env *pEnv;
  lsm_mutex *pMutex;
};

static void tmLsmMutexEnter(TmGlobal *pTm){
  LsmMutex *p = (LsmMutex *)pTm->pMutex;
  p->pEnv->xMutexEnter(p->pMutex);
}
static void tmLsmMutexLeave(TmGlobal *pTm){
  LsmMutex *p = (LsmMutex *)(pTm->pMutex);
  p->pEnv->xMutexLeave(p->pMutex);
}
static void tmLsmMutexDel(TmGlobal *pTm){
  LsmMutex *p = (LsmMutex *)pTm->pMutex;
  pTm->xFree(p);
}
static void *tmLsmMalloc(int n){ return malloc(n); }
static void tmLsmFree(void *ptr){ free(ptr); }
static void *tmLsmRealloc(void *ptr, int n){ return realloc(ptr, n); }

static void *tmLsmEnvMalloc(lsm_env *p, int n){ 
  return tmMalloc((TmGlobal *)(p->pMemCtx), n); 
}
static void tmLsmEnvFree(lsm_env *p, void *ptr){ 
  tmFree((TmGlobal *)(p->pMemCtx), ptr); 
}
static void *tmLsmEnvRealloc(lsm_env *p, void *ptr, int n){ 
  return tmRealloc((TmGlobal *)(p->pMemCtx), ptr, n);
}

void testMallocInstall(lsm_env *pEnv){
  TmGlobal *pGlobal;
  LsmMutex *pMutex;
  assert( pEnv->pMemCtx==0 );

  /* Allocate and populate a TmGlobal structure. */
  pGlobal = (TmGlobal *)tmLsmMalloc(sizeof(TmGlobal));
  memset(pGlobal, 0, sizeof(TmGlobal));
  pGlobal->xMalloc = tmLsmMalloc;
  pGlobal->xRealloc = tmLsmRealloc;
  pGlobal->xFree = tmLsmFree;
  pMutex = (LsmMutex *)pGlobal->xMalloc(sizeof(LsmMutex));
  pMutex->pEnv = pEnv;
  pEnv->xMutexStatic(pEnv, LSM_MUTEX_HEAP, &pMutex->pMutex);
  pGlobal->xEnterMutex = tmLsmMutexEnter;
  pGlobal->xLeaveMutex = tmLsmMutexLeave;
  pGlobal->xDelMutex = tmLsmMutexDel;
  pGlobal->pMutex = (void *)pMutex;

  pGlobal->xSaveMalloc = (void *)pEnv->xMalloc;
  pGlobal->xSaveRealloc = (void *)pEnv->xRealloc;
  pGlobal->xSaveFree = (void *)pEnv->xFree;

  /* Set up pEnv to the use the new TmGlobal */
  pEnv->pMemCtx = (void *)pGlobal;
  pEnv->xMalloc = tmLsmEnvMalloc;
  pEnv->xRealloc = tmLsmEnvRealloc;
  pEnv->xFree = tmLsmEnvFree;
}

void testMallocUninstall(lsm_env *pEnv){
  TmGlobal *p = (TmGlobal *)pEnv->pMemCtx;
  pEnv->pMemCtx = 0;
  if( p ){
    pEnv->xMalloc = (void *(*)(lsm_env*, int))(p->xSaveMalloc);
    pEnv->xRealloc = (void *(*)(lsm_env*, void*, int))(p->xSaveRealloc);
    pEnv->xFree = (void (*)(lsm_env*, void*))(p->xSaveFree);
    p->xDelMutex(p);
    tmLsmFree(p);
  }
}

void testMallocCheck(
  lsm_env *pEnv,
  int *pnLeakAlloc,
  int *pnLeakByte,
  FILE *pFile
){
  if( pEnv->pMemCtx==0 ){
    *pnLeakAlloc = 0;
    *pnLeakByte = 0;
  }else{
    tmMallocCheck((TmGlobal *)(pEnv->pMemCtx), pnLeakAlloc, pnLeakByte, pFile);
  }
}

void testMallocOom(
  lsm_env *pEnv, 
  int nCountdown, 
  int bPersist,
  void (*xHook)(void *),
  void *pHookCtx
){
  TmGlobal *pTm = (TmGlobal *)(pEnv->pMemCtx);
  tmMallocOom(pTm, nCountdown, bPersist, xHook, pHookCtx);
}

void testMallocOomEnable(lsm_env *pEnv, int bEnable){
  TmGlobal *pTm = (TmGlobal *)(pEnv->pMemCtx);
  tmMallocOomEnable(pTm, bEnable);
}

/*
** This program attempts to test the correctness of some facets of the 
** LSM database library. Specifically, that the contents of the database
** are maintained correctly during a series of inserts and deletes.
*/


#include "lsmtest_tdb.h"
#include "lsm.h"

#include "lsmtest.h"

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <unistd.h>
#include <stdio.h>


typedef struct SqlDb SqlDb;

static int error_transaction_function(TestDb *p, int iLevel){ 
  unused_parameter(p);
  unused_parameter(iLevel);
  return -1; 
}


/*************************************************************************
** Begin wrapper for LevelDB.
*/
#ifdef HAVE_LEVELDB

#include <leveldb/c.h>

typedef struct LevelDb LevelDb;
struct LevelDb {
  TestDb base;
  leveldb_t *db;
  leveldb_options_t *pOpt;
  leveldb_writeoptions_t *pWriteOpt;
  leveldb_readoptions_t *pReadOpt;

  char *pVal;
};

static int test_leveldb_close(TestDb *pTestDb){
  LevelDb *pDb = (LevelDb *)pTestDb;

  leveldb_close(pDb->db);
  leveldb_writeoptions_destroy(pDb->pWriteOpt);
  leveldb_readoptions_destroy(pDb->pReadOpt);
  leveldb_options_destroy(pDb->pOpt);
  free(pDb->pVal);
  free(pDb);

  return 0;
}

static int test_leveldb_write(
  TestDb *pTestDb, 
  void *pKey, 
  int nKey, 
  void *pVal, 
  int nVal
){
  LevelDb *pDb = (LevelDb *)pTestDb;
  char *zErr = 0;
  leveldb_put(pDb->db, pDb->pWriteOpt, pKey, nKey, pVal, nVal, &zErr);
  return (zErr!=0);
}

static int test_leveldb_delete(TestDb *pTestDb, void *pKey, int nKey){
  LevelDb *pDb = (LevelDb *)pTestDb;
  char *zErr = 0;
  leveldb_delete(pDb->db, pDb->pWriteOpt, pKey, nKey, &zErr);
  return (zErr!=0);
}

static int test_leveldb_fetch(
  TestDb *pTestDb, 
  void *pKey, 
  int nKey, 
  void **ppVal, 
  int *pnVal
){
  LevelDb *pDb = (LevelDb *)pTestDb;
  char *zErr = 0;
  size_t nVal = 0;

  if( pKey==0 ) return 0;
  free(pDb->pVal);
  pDb->pVal = leveldb_get(pDb->db, pDb->pReadOpt, pKey, nKey, &nVal, &zErr);
  *ppVal = (void *)(pDb->pVal);
  if( pDb->pVal==0 ){
    *pnVal = -1;
  }else{
    *pnVal = (int)nVal;
  }

  return (zErr!=0);
}

static int test_leveldb_scan(
  TestDb *pTestDb,
  void *pCtx,
  int bReverse,
  void *pKey1, int nKey1,         /* Start of search */
  void *pKey2, int nKey2,         /* End of search */
  void (*xCallback)(void *, void *, int , void *, int)
){
  LevelDb *pDb = (LevelDb *)pTestDb;
  leveldb_iterator_t *iter;

  iter = leveldb_create_iterator(pDb->db, pDb->pReadOpt);

  if( bReverse==0 ){
    if( pKey1 ){
      leveldb_iter_seek(iter, pKey1, nKey1);
    }else{
      leveldb_iter_seek_to_first(iter);
    }
  }else{
    if( pKey2 ){
      leveldb_iter_seek(iter, pKey2, nKey2);

      if( leveldb_iter_valid(iter)==0 ){
        leveldb_iter_seek_to_last(iter);
      }else{
        const char *k; size_t n;
        int res;
        k = leveldb_iter_key(iter, &n);
        res = memcmp(k, pKey2, MIN(n, nKey2));
        if( res==0 ) res = n - nKey2;
        assert( res>=0 );
        if( res>0 ){
          leveldb_iter_prev(iter);
        }
      }
    }else{
      leveldb_iter_seek_to_last(iter);
    }
  }


  while( leveldb_iter_valid(iter) ){
    const char *k; size_t n;
    const char *v; size_t n2;
    int res;

    k = leveldb_iter_key(iter, &n);
    if( bReverse==0 && pKey2 ){
      res = memcmp(k, pKey2, MIN(n, nKey2));
      if( res==0 ) res = n - nKey2;
      if( res>0 ) break;
    }
    if( bReverse!=0 && pKey1 ){
      res = memcmp(k, pKey1, MIN(n, nKey1));
      if( res==0 ) res = n - nKey1;
      if( res<0 ) break;
    }

    v = leveldb_iter_value(iter, &n2);

    xCallback(pCtx, (void *)k, n, (void *)v, n2);

    if( bReverse==0 ){
      leveldb_iter_next(iter);
    }else{
      leveldb_iter_prev(iter);
    }
  }

  leveldb_iter_destroy(iter);
  return 0;
}

static int test_leveldb_open(
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  static const DatabaseMethods LeveldbMethods = {
    test_leveldb_close,
    test_leveldb_write,
    test_leveldb_delete,
    0,
    test_leveldb_fetch,
    test_leveldb_scan,
    error_transaction_function,
    error_transaction_function,
    error_transaction_function
  };

  LevelDb *pLevelDb;
  char *zErr = 0;

  if( bClear ){
    char *zCmd = sqlite3_mprintf("rm -rf %s\n", zFilename);
    system(zCmd);
    sqlite3_free(zCmd);
  }

  pLevelDb = (LevelDb *)malloc(sizeof(LevelDb));
  memset(pLevelDb, 0, sizeof(LevelDb));

  pLevelDb->pOpt = leveldb_options_create();
  leveldb_options_set_create_if_missing(pLevelDb->pOpt, 1);
  pLevelDb->pWriteOpt = leveldb_writeoptions_create();
  pLevelDb->pReadOpt = leveldb_readoptions_create();

  pLevelDb->db = leveldb_open(pLevelDb->pOpt, zFilename, &zErr);

  if( zErr ){
    test_leveldb_close((TestDb *)pLevelDb);
    *ppDb = 0;
    return 1;
  }

  *ppDb = (TestDb *)pLevelDb;
  pLevelDb->base.pMethods = &LeveldbMethods;
  return 0;
}
#endif  /* HAVE_LEVELDB */
/* 
** End wrapper for LevelDB.
*************************************************************************/

#ifdef HAVE_KYOTOCABINET
static int kc_close(TestDb *pTestDb){
  return test_kc_close(pTestDb);
}

static int kc_write(
  TestDb *pTestDb, 
  void *pKey, 
  int nKey, 
  void *pVal, 
  int nVal
){
  return test_kc_write(pTestDb, pKey, nKey, pVal, nVal);
}

static int kc_delete(TestDb *pTestDb, void *pKey, int nKey){
  return test_kc_delete(pTestDb, pKey, nKey);
}

static int kc_delete_range(
  TestDb *pTestDb, 
  void *pKey1, int nKey1,
  void *pKey2, int nKey2
){
  return test_kc_delete_range(pTestDb, pKey1, nKey1, pKey2, nKey2);
}

static int kc_fetch(
  TestDb *pTestDb, 
  void *pKey, 
  int nKey, 
  void **ppVal, 
  int *pnVal
){
  if( pKey==0 ) return LSM_OK;
  return test_kc_fetch(pTestDb, pKey, nKey, ppVal, pnVal);
}

static int kc_scan(
  TestDb *pTestDb,
  void *pCtx,
  int bReverse,
  void *pFirst, int nFirst,
  void *pLast, int nLast,
  void (*xCallback)(void *, void *, int , void *, int)
){
  return test_kc_scan(
      pTestDb, pCtx, bReverse, pFirst, nFirst, pLast, nLast, xCallback
  );
}

static int kc_open(
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  static const DatabaseMethods KcdbMethods = {
    kc_close,
    kc_write,
    kc_delete,
    kc_delete_range,
    kc_fetch,
    kc_scan,
    error_transaction_function,
    error_transaction_function,
    error_transaction_function
  };

  int rc;
  TestDb *pTestDb = 0;

  rc = test_kc_open(zFilename, bClear, &pTestDb);
  if( rc!=0 ){
    *ppDb = 0;
    return rc;
  }
  pTestDb->pMethods = &KcdbMethods;
  *ppDb = pTestDb;
  return 0;
}
#endif /* HAVE_KYOTOCABINET */
/* 
** End wrapper for Kyoto cabinet.
*************************************************************************/

#ifdef HAVE_MDB
static int mdb_close(TestDb *pTestDb){
  return test_mdb_close(pTestDb);
}

static int mdb_write(
  TestDb *pTestDb, 
  void *pKey, 
  int nKey, 
  void *pVal, 
  int nVal
){
  return test_mdb_write(pTestDb, pKey, nKey, pVal, nVal);
}

static int mdb_delete(TestDb *pTestDb, void *pKey, int nKey){
  return test_mdb_delete(pTestDb, pKey, nKey);
}

static int mdb_fetch(
  TestDb *pTestDb, 
  void *pKey, 
  int nKey, 
  void **ppVal, 
  int *pnVal
){
  if( pKey==0 ) return LSM_OK;
  return test_mdb_fetch(pTestDb, pKey, nKey, ppVal, pnVal);
}

static int mdb_scan(
  TestDb *pTestDb,
  void *pCtx,
  int bReverse,
  void *pFirst, int nFirst,
  void *pLast, int nLast,
  void (*xCallback)(void *, void *, int , void *, int)
){
  return test_mdb_scan(
      pTestDb, pCtx, bReverse, pFirst, nFirst, pLast, nLast, xCallback
  );
}

static int mdb_open(
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  static const DatabaseMethods KcdbMethods = {
    mdb_close,
    mdb_write,
    mdb_delete,
    0,
    mdb_fetch,
    mdb_scan,
    error_transaction_function,
    error_transaction_function,
    error_transaction_function
  };

  int rc;
  TestDb *pTestDb = 0;

  rc = test_mdb_open(zSpec, zFilename, bClear, &pTestDb);
  if( rc!=0 ){
    *ppDb = 0;
    return rc;
  }
  pTestDb->pMethods = &KcdbMethods;
  *ppDb = pTestDb;
  return 0;
}
#endif /* HAVE_MDB */

/*************************************************************************
** Begin wrapper for SQLite.
*/

/*
** nOpenTrans:
**   The number of open nested transactions, in the same sense as used
**   by the tdb_begin/commit/rollback and SQLite 4 KV interfaces. If this
**   value is 0, there are no transactions open at all. If it is 1, then
**   there is a read transaction. If it is 2 or greater, then there are
**   (nOpenTrans-1) nested write transactions open.
*/
struct SqlDb {
  TestDb base;
  sqlite3 *db;
  sqlite3_stmt *pInsert;
  sqlite3_stmt *pDelete;
  sqlite3_stmt *pDeleteRange;
  sqlite3_stmt *pFetch;
  sqlite3_stmt *apScan[8];

  int nOpenTrans;

  /* Used by sql_fetch() to allocate space for results */
  int nAlloc;
  u8 *aAlloc;
};

static int sql_close(TestDb *pTestDb){
  SqlDb *pDb = (SqlDb *)pTestDb;
  sqlite3_finalize(pDb->pInsert);
  sqlite3_finalize(pDb->pDelete);
  sqlite3_finalize(pDb->pDeleteRange);
  sqlite3_finalize(pDb->pFetch);
  sqlite3_finalize(pDb->apScan[0]);
  sqlite3_finalize(pDb->apScan[1]);
  sqlite3_finalize(pDb->apScan[2]);
  sqlite3_finalize(pDb->apScan[3]);
  sqlite3_finalize(pDb->apScan[4]);
  sqlite3_finalize(pDb->apScan[5]);
  sqlite3_finalize(pDb->apScan[6]);
  sqlite3_finalize(pDb->apScan[7]);
  sqlite3_close(pDb->db);
  free((char *)pDb->aAlloc);
  free((char *)pDb);
  return SQLITE_OK;
}

static int sql_write(
  TestDb *pTestDb, 
  void *pKey, 
  int nKey, 
  void *pVal, 
  int nVal
){
  SqlDb *pDb = (SqlDb *)pTestDb;
  sqlite3_bind_blob(pDb->pInsert, 1, pKey, nKey, SQLITE_STATIC);
  sqlite3_bind_blob(pDb->pInsert, 2, pVal, nVal, SQLITE_STATIC);
  sqlite3_step(pDb->pInsert);
  return sqlite3_reset(pDb->pInsert);
}

static int sql_delete(TestDb *pTestDb, void *pKey, int nKey){
  SqlDb *pDb = (SqlDb *)pTestDb;
  sqlite3_bind_blob(pDb->pDelete, 1, pKey, nKey, SQLITE_STATIC);
  sqlite3_step(pDb->pDelete);
  return sqlite3_reset(pDb->pDelete);
}

static int sql_delete_range(
  TestDb *pTestDb, 
  void *pKey1, int nKey1,
  void *pKey2, int nKey2
){
  SqlDb *pDb = (SqlDb *)pTestDb;
  sqlite3_bind_blob(pDb->pDeleteRange, 1, pKey1, nKey1, SQLITE_STATIC);
  sqlite3_bind_blob(pDb->pDeleteRange, 2, pKey2, nKey2, SQLITE_STATIC);
  sqlite3_step(pDb->pDeleteRange);
  return sqlite3_reset(pDb->pDeleteRange);
}

static int sql_fetch(
  TestDb *pTestDb, 
  void *pKey, 
  int nKey, 
  void **ppVal, 
  int *pnVal
){
  SqlDb *pDb = (SqlDb *)pTestDb;
  int rc;

  sqlite3_reset(pDb->pFetch);
  if( pKey==0 ){
    assert( ppVal==0 );
    assert( pnVal==0 );
    return LSM_OK;
  }

  sqlite3_bind_blob(pDb->pFetch, 1, pKey, nKey, SQLITE_STATIC);
  rc = sqlite3_step(pDb->pFetch);
  if( rc==SQLITE_ROW ){
    int nVal = sqlite3_column_bytes(pDb->pFetch, 0);
    u8 *aVal = (void *)sqlite3_column_blob(pDb->pFetch, 0);

    if( nVal>pDb->nAlloc ){
      free(pDb->aAlloc);
      pDb->aAlloc = (u8 *)malloc(nVal*2);
      pDb->nAlloc = nVal*2;
    }
    memcpy(pDb->aAlloc, aVal, nVal);
    *pnVal = nVal;
    *ppVal = (void *)pDb->aAlloc;
  }else{
    *pnVal = -1;
    *ppVal = 0;
  }

  rc = sqlite3_reset(pDb->pFetch);
  return rc;
}

static int sql_scan(
  TestDb *pTestDb,
  void *pCtx,
  int bReverse,
  void *pFirst, int nFirst,
  void *pLast, int nLast,
  void (*xCallback)(void *, void *, int , void *, int)
){
  SqlDb *pDb = (SqlDb *)pTestDb;
  sqlite3_stmt *pScan;

  assert( bReverse==1 || bReverse==0 );
  pScan = pDb->apScan[(pFirst==0) + (pLast==0)*2 + bReverse*4];

  if( pFirst ) sqlite3_bind_blob(pScan, 1, pFirst, nFirst, SQLITE_STATIC);
  if( pLast ) sqlite3_bind_blob(pScan, 2, pLast, nLast, SQLITE_STATIC);

  while( SQLITE_ROW==sqlite3_step(pScan) ){
    void *pKey; int nKey;
    void *pVal; int nVal;

    nKey = sqlite3_column_bytes(pScan, 0);
    pKey = (void *)sqlite3_column_blob(pScan, 0);
    nVal = sqlite3_column_bytes(pScan, 1);
    pVal = (void *)sqlite3_column_blob(pScan, 1);

    xCallback(pCtx, pKey, nKey, pVal, nVal);
  }
  return sqlite3_reset(pScan);
}

static int sql_begin(TestDb *pTestDb, int iLevel){
  int i;
  SqlDb *pDb = (SqlDb *)pTestDb;

  /* iLevel==0 is a no-op */
  if( iLevel==0 ) return 0;

  /* If there are no transactions at all open, open a read transaction. */
  if( pDb->nOpenTrans==0 ){
    int rc = sqlite3_exec(pDb->db, 
        "BEGIN; SELECT * FROM sqlite_master LIMIT 1;" , 0, 0, 0
    );
    if( rc!=0 ) return rc;
    pDb->nOpenTrans = 1;
  }

  /* Open any required write transactions */
  for(i=pDb->nOpenTrans; i<iLevel; i++){
    char *zSql = sqlite3_mprintf("SAVEPOINT x%d", i);
    int rc = sqlite3_exec(pDb->db, zSql, 0, 0, 0);
    sqlite3_free(zSql);
    if( rc!=SQLITE_OK ) return rc;
  }

  pDb->nOpenTrans = iLevel;
  return 0;
}

static int sql_commit(TestDb *pTestDb, int iLevel){
  SqlDb *pDb = (SqlDb *)pTestDb;
  assert( iLevel>=0 );

  /* Close the read transaction if requested. */
  if( pDb->nOpenTrans>=1 && iLevel==0 ){
    int rc = sqlite3_exec(pDb->db, "COMMIT", 0, 0, 0);
    if( rc!=0 ) return rc;
    pDb->nOpenTrans = 0;
  }

  /* Close write transactions as required */
  if( pDb->nOpenTrans>iLevel ){
    char *zSql = sqlite3_mprintf("RELEASE x%d", iLevel);
    int rc = sqlite3_exec(pDb->db, zSql, 0, 0, 0);
    sqlite3_free(zSql);
    if( rc!=0 ) return rc;
  }

  pDb->nOpenTrans = iLevel;
  return 0;
}

static int sql_rollback(TestDb *pTestDb, int iLevel){
  SqlDb *pDb = (SqlDb *)pTestDb;
  assert( iLevel>=0 );

  if( pDb->nOpenTrans>=1 && iLevel==0 ){
    /* Close the read transaction if requested. */
    int rc = sqlite3_exec(pDb->db, "ROLLBACK", 0, 0, 0);
    if( rc!=0 ) return rc;
  }else if( pDb->nOpenTrans>1 && iLevel==1 ){
    /* Or, rollback and close the top-level write transaction */
    int rc = sqlite3_exec(pDb->db, "ROLLBACK TO x1; RELEASE x1;", 0, 0, 0);
    if( rc!=0 ) return rc;
  }else{
    /* Or, just roll back some nested transactions */
    char *zSql = sqlite3_mprintf("ROLLBACK TO x%d", iLevel-1);
    int rc = sqlite3_exec(pDb->db, zSql, 0, 0, 0);
    sqlite3_free(zSql);
    if( rc!=0 ) return rc;
  }

  pDb->nOpenTrans = iLevel;
  return 0;
}

static int sql_open(
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  static const DatabaseMethods SqlMethods = {
    sql_close,
    sql_write,
    sql_delete,
    sql_delete_range,
    sql_fetch,
    sql_scan,
    sql_begin,
    sql_commit,
    sql_rollback
  };
  const char *zCreate = "CREATE TABLE IF NOT EXISTS t1(k PRIMARY KEY, v)";
  const char *zInsert = "REPLACE INTO t1 VALUES(?, ?)";
  const char *zDelete = "DELETE FROM t1 WHERE k = ?";
  const char *zRange = "DELETE FROM t1 WHERE k>? AND k<?";
  const char *zFetch  = "SELECT v FROM t1 WHERE k = ?";

  const char *zScan0  = "SELECT * FROM t1 WHERE k BETWEEN ?1 AND ?2 ORDER BY k";
  const char *zScan1  = "SELECT * FROM t1 WHERE k <= ?2 ORDER BY k";
  const char *zScan2  = "SELECT * FROM t1 WHERE k >= ?1 ORDER BY k";
  const char *zScan3  = "SELECT * FROM t1 ORDER BY k";

  const char *zScan4  = 
    "SELECT * FROM t1 WHERE k BETWEEN ?1 AND ?2 ORDER BY k DESC";
  const char *zScan5  = "SELECT * FROM t1 WHERE k <= ?2 ORDER BY k DESC";
  const char *zScan6  = "SELECT * FROM t1 WHERE k >= ?1 ORDER BY k DESC";
  const char *zScan7  = "SELECT * FROM t1 ORDER BY k DESC";

  int rc;
  SqlDb *pDb;
  char *zPragma;

  if( bClear && zFilename && zFilename[0] ){
    unlink(zFilename);
  }

  pDb = (SqlDb *)malloc(sizeof(SqlDb));
  memset(pDb, 0, sizeof(SqlDb));
  pDb->base.pMethods = &SqlMethods;

  if( 0!=(rc = sqlite3_open(zFilename, &pDb->db))
   || 0!=(rc = sqlite3_exec(pDb->db, zCreate, 0, 0, 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zInsert, -1, &pDb->pInsert, 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zDelete, -1, &pDb->pDelete, 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zRange, -1, &pDb->pDeleteRange, 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zFetch, -1, &pDb->pFetch, 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan0, -1, &pDb->apScan[0], 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan1, -1, &pDb->apScan[1], 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan2, -1, &pDb->apScan[2], 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan3, -1, &pDb->apScan[3], 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan4, -1, &pDb->apScan[4], 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan5, -1, &pDb->apScan[5], 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan6, -1, &pDb->apScan[6], 0))
   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan7, -1, &pDb->apScan[7], 0))
  ){
    *ppDb = 0;
    sql_close((TestDb *)pDb);
    return rc;
  }

  zPragma = sqlite3_mprintf("PRAGMA page_size=%d", TESTDB_DEFAULT_PAGE_SIZE);
  sqlite3_exec(pDb->db, zPragma, 0, 0, 0);
  sqlite3_free(zPragma);
  zPragma = sqlite3_mprintf("PRAGMA cache_size=%d", TESTDB_DEFAULT_CACHE_SIZE);
  sqlite3_exec(pDb->db, zPragma, 0, 0, 0);
  sqlite3_free(zPragma);

  /* sqlite3_exec(pDb->db, "PRAGMA locking_mode=EXCLUSIVE", 0, 0, 0); */
  sqlite3_exec(pDb->db, "PRAGMA synchronous=OFF", 0, 0, 0);
  sqlite3_exec(pDb->db, "PRAGMA journal_mode=WAL", 0, 0, 0);
  sqlite3_exec(pDb->db, "PRAGMA wal_autocheckpoint=4096", 0, 0, 0);

  *ppDb = (TestDb *)pDb;
  return 0;
}
/* 
** End wrapper for SQLite.
*************************************************************************/

/*************************************************************************
** Begin exported functions.
*/
static struct Lib {
  const char *zName;
  const char *zDefaultDb;
  int (*xOpen)(const char *, const char *zFilename, int bClear, TestDb **ppDb);
} aLib[] = {
  { "sqlite3",      "testdb.sqlite",    sql_open },
  { "lsm_small",    "testdb.lsm_small", test_lsm_small_open },
  { "lsm_lomem",    "testdb.lsm_lomem", test_lsm_lomem_open },
#ifdef HAVE_ZLIB
  { "lsm_zip",      "testdb.lsm_zip",   test_lsm_zip_open },
#endif
  { "lsm",          "testdb.lsm",       test_lsm_open },
#ifdef LSM_MUTEX_PTHREADS
  { "lsm_mt2",      "testdb.lsm_mt2",   test_lsm_mt2 },
  { "lsm_mt3",      "testdb.lsm_mt3",   test_lsm_mt3 },
#endif
#ifdef HAVE_LEVELDB
  { "leveldb",      "testdb.leveldb",   test_leveldb_open },
#endif
#ifdef HAVE_KYOTOCABINET
  { "kyotocabinet", "testdb.kc",        kc_open },
#endif
#ifdef HAVE_MDB
  { "mdb", "./testdb.mdb",        mdb_open }
#endif
};

const char *tdb_system_name(int i){
  if( i<0 || i>=ArraySize(aLib) ) return 0;
  return aLib[i].zName;
}

int tdb_open(const char *zLib, const char *zDb, int bClear, TestDb **ppDb){
  int i;
  int rc = 1;
  const char *zSpec = 0;

  int nLib = 0;
  while( zLib[nLib] && zLib[nLib]!=' ' ){
    nLib++;
  }
  zSpec = &zLib[nLib];
  while( *zSpec==' ' ) zSpec++;
  if( *zSpec=='\0' ) zSpec = 0;

  for(i=0; i<ArraySize(aLib); i++){
    if( strlen(aLib[i].zName)==nLib && 0==memcmp(zLib, aLib[i].zName, nLib) ){
      rc = aLib[i].xOpen(zSpec, (zDb ? zDb : aLib[i].zDefaultDb), bClear, ppDb);
      if( rc==0 ){
        (*ppDb)->zLibrary = aLib[i].zName;
      }
      break;
    }
  }

  if( rc ){
    /* Failed to find the requested database library. Return an error. */
    *ppDb = 0;
  }
  return rc;
}

int tdb_close(TestDb *pDb){
  if( pDb ){
    return pDb->pMethods->xClose(pDb);
  }
  return 0;
}

int tdb_write(TestDb *pDb, void *pKey, int nKey, void *pVal, int nVal){
  return pDb->pMethods->xWrite(pDb, pKey, nKey, pVal, nVal);
}

int tdb_delete(TestDb *pDb, void *pKey, int nKey){
  return pDb->pMethods->xDelete(pDb, pKey, nKey);
}

int tdb_delete_range(
    TestDb *pDb, void *pKey1, int nKey1, void *pKey2, int nKey2
){
  return pDb->pMethods->xDeleteRange(pDb, pKey1, nKey1, pKey2, nKey2);
}

int tdb_fetch(TestDb *pDb, void *pKey, int nKey, void **ppVal, int *pnVal){
  return pDb->pMethods->xFetch(pDb, pKey, nKey, ppVal, pnVal);
}

int tdb_scan(
  TestDb *pDb,                    /* Database handle */
  void *pCtx,                     /* Context pointer to pass to xCallback */
  int bReverse,                   /* True to scan in reverse order */
  void *pKey1, int nKey1,         /* Start of search */
  void *pKey2, int nKey2,         /* End of search */
  void (*xCallback)(void *pCtx, void *pKey, int nKey, void *pVal, int nVal)
){
  return pDb->pMethods->xScan(
      pDb, pCtx, bReverse, pKey1, nKey1, pKey2, nKey2, xCallback
  );
}

int tdb_begin(TestDb *pDb, int iLevel){
  return pDb->pMethods->xBegin(pDb, iLevel);
}
int tdb_commit(TestDb *pDb, int iLevel){
  return pDb->pMethods->xCommit(pDb, iLevel);
}
int tdb_rollback(TestDb *pDb, int iLevel){
  return pDb->pMethods->xRollback(pDb, iLevel);
}

int tdb_transaction_support(TestDb *pDb){
  return (pDb->pMethods->xBegin != error_transaction_function);
}

const char *tdb_library_name(TestDb *pDb){
  return pDb->zLibrary;
}

/* 
** End exported functions.
*************************************************************************/

/*
** This file is the interface to a very simple database library used for
** testing. The interface is similar to that of the LSM. The main virtue 
** of this library is that the same API may be used to access a key-value
** store implemented by LSM, SQLite or another database system. Which 
** makes it easy to use for correctness and performance tests.
*/

#ifndef __WRAPPER_H_
#define __WRAPPER_H_

#ifdef __cplusplus
extern "C" {
#endif

#include "lsm.h"

typedef struct TestDb TestDb;

/*
** Open a new database connection. The first argument is the name of the
** database library to use. e.g. something like:
**
**     "sqlite3"
**     "lsm"
**
** See function tdb_system_name() for a list of available database systems.
**
** The second argument is the name of the database to open (e.g. a filename).
**
** If the third parameter is non-zero, then any existing database by the
** name of zDb is removed before opening a new one. If it is zero, then an
** existing database may be opened.
*/
int tdb_open(const char *zLibrary, const char *zDb, int bClear, TestDb **ppDb);

/*
** Close a database handle.
*/
int tdb_close(TestDb *pDb);

/*
** Write a new key/value into the database.
*/
int tdb_write(TestDb *pDb, void *pKey, int nKey, void *pVal, int nVal);

/*
** Delete a key from the database.
*/
int tdb_delete(TestDb *pDb, void *pKey, int nKey);

/*
** Delete a range of keys from the database.
*/
int tdb_delete_range(TestDb *, void *pKey1, int nKey1, void *pKey2, int nKey2);

/*
** Query the database for key (pKey/nKey). If no entry is found, set *ppVal
** to 0 and *pnVal to -1 before returning. Otherwise, set *ppVal and *pnVal
** to a pointer to and size of the value associated with (pKey/nKey).
*/
int tdb_fetch(TestDb *pDb, void *pKey, int nKey, void **ppVal, int *pnVal);

/*
** Open and close nested transactions. Currently, these functions only 
** work for SQLite3 and LSM systems. Use the tdb_transaction_support() 
** function to determine if a given TestDb handle supports these methods.
**
** These functions and the iLevel parameter follow the same conventions as
** the SQLite 4 transaction interface. Note that this is slightly different
** from the way LSM does things. As follows:
**
** tdb_begin():
**   A successful call to tdb_begin() with (iLevel>1) guarantees that 
**   there are at least (iLevel-1) write transactions open. If iLevel==1,
**   then it guarantees that at least a read-transaction is open. Calling
**   tdb_begin() with iLevel==0 is a no-op.
**
** tdb_commit():
**   A successful call to tdb_commit() with (iLevel>1) guarantees that 
**   there are at most (iLevel-1) write transactions open. If iLevel==1,
**   then it guarantees that there are no write transactions open (although
**   a read-transaction may remain open).  Calling tdb_commit() with 
**   iLevel==0 ensures that all transactions, read or write, have been 
**   closed and committed.
**
** tdb_rollback():
**   This call is similar to tdb_commit(), except that instead of committing
**   transactions, it reverts them. For example, calling tdb_rollback() with
**   iLevel==2 ensures that there is at most one write transaction open, and
**   restores the database to the state that it was in when that transaction
**   was opened.
**
**   In other words, tdb_commit() just closes transactions - tdb_rollback()
**   closes transactions and then restores the database to the state it
**   was in before those transactions were even opened.
*/
int tdb_begin(TestDb *pDb, int iLevel);
int tdb_commit(TestDb *pDb, int iLevel);
int tdb_rollback(TestDb *pDb, int iLevel);

/*
** Return true if transactions are supported, or false otherwise.
*/
int tdb_transaction_support(TestDb *pDb);

/*
** Return the name of the database library (as passed to tdb_open()) used
** by the handled passed as the first argument.
*/
const char *tdb_library_name(TestDb *pDb);

/*
** Scan a range of database keys. Invoke the callback function for each
** key visited.
*/
int tdb_scan(
  TestDb *pDb,                    /* Database handle */
  void *pCtx,                     /* Context pointer to pass to xCallback */
  int bReverse,                   /* True to scan in reverse order */
  void *pKey1, int nKey1,         /* Start of search */
  void *pKey2, int nKey2,         /* End of search */
  void (*xCallback)(void *pCtx, void *pKey, int nKey, void *pVal, int nVal)
);

const char *tdb_system_name(int i);

int tdb_lsm_open(const char *zCfg, const char *zDb, int bClear, TestDb **ppDb);

/*
** If the TestDb handle passed as an argument is a wrapper around an LSM
** database, return the LSM handle. Otherwise, if the argument is some other
** database system, return NULL.
*/
lsm_db *tdb_lsm(TestDb *pDb);

/*
** Return a pointer to the lsm_env object used by all lsm database
** connections initialized as a copy of the object returned by 
** lsm_default_env(). It may be modified (e.g. to override functions)
** if the caller can guarantee that it is not already in use.
*/
lsm_env *tdb_lsm_env(void);

/*
** The following functions only work with LSM database handles. It is
** illegal to call them with any other type of database handle specified
** as an argument.
*/
void tdb_lsm_enable_log(TestDb *pDb, int bEnable);
void tdb_lsm_application_crash(TestDb *pDb);
void tdb_lsm_prepare_system_crash(TestDb *pDb);
void tdb_lsm_system_crash(TestDb *pDb);
void tdb_lsm_prepare_sync_crash(TestDb *pDb, int iSync);


void tdb_lsm_safety(TestDb *pDb, int eMode);
void tdb_lsm_config_work_hook(TestDb *pDb, void (*)(lsm_db *, void *), void *);
void tdb_lsm_write_hook(TestDb *, void(*)(void*,int,lsm_i64,int,int), void*);
int tdb_lsm_config_str(TestDb *pDb, const char *zStr);

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif

#endif

#include "lsmtest.h"
#include <stdlib.h>

#ifdef HAVE_KYOTOCABINET
#include "kcpolydb.h"
extern "C" {
  struct KcDb {
    TestDb base;
    kyotocabinet::TreeDB* db;
    char *pVal;
  };
}

int test_kc_open(const char *zFilename, int bClear, TestDb **ppDb){
  KcDb *pKcDb;
  int ok;
  int rc = 0;

  if( bClear ){
    char *zCmd = sqlite3_mprintf("rm -rf %s\n", zFilename);
    system(zCmd);
    sqlite3_free(zCmd);
  }

  pKcDb = (KcDb *)malloc(sizeof(KcDb));
  memset(pKcDb, 0, sizeof(KcDb));


  pKcDb->db = new kyotocabinet::TreeDB();
  pKcDb->db->tune_page(TESTDB_DEFAULT_PAGE_SIZE);
  pKcDb->db->tune_page_cache(
      TESTDB_DEFAULT_PAGE_SIZE * TESTDB_DEFAULT_CACHE_SIZE
  );
  ok = pKcDb->db->open(zFilename,
      kyotocabinet::PolyDB::OWRITER | kyotocabinet::PolyDB::OCREATE
  );
  if( ok==0 ){
    free(pKcDb);
    pKcDb = 0;
    rc = 1;
  }

  *ppDb = (TestDb *)pKcDb;
  return rc;
}

int test_kc_close(TestDb *pDb){
  KcDb *pKcDb = (KcDb *)pDb;
  if( pKcDb->pVal ){
    delete [] pKcDb->pVal;
  }
  pKcDb->db->close();
  delete pKcDb->db;
  free(pKcDb);
  return 0;
}

int test_kc_write(TestDb *pDb, void *pKey, int nKey, void *pVal, int nVal){
  KcDb *pKcDb = (KcDb *)pDb;
  int ok;

  ok = pKcDb->db->set((const char *)pKey, nKey, (const char *)pVal, nVal);
  return (ok ? 0 : 1);
}

int test_kc_delete(TestDb *pDb, void *pKey, int nKey){
  KcDb *pKcDb = (KcDb *)pDb;
  int ok;

  ok = pKcDb->db->remove((const char *)pKey, nKey);
  return (ok ? 0 : 1);
}

int test_kc_delete_range(
  TestDb *pDb, 
  void *pKey1, int nKey1,
  void *pKey2, int nKey2
){
  int res;
  KcDb *pKcDb = (KcDb *)pDb;
  kyotocabinet::DB::Cursor* pCur = pKcDb->db->cursor();

  if( pKey1 ){
    res = pCur->jump((const char *)pKey1, nKey1);
  }else{
    res = pCur->jump();
  }

  while( 1 ){
    const char *pKey; size_t nKey;
    const char *pVal; size_t nVal;

    pKey = pCur->get(&nKey, &pVal, &nVal);
    if( pKey==0 ) break;

#ifndef NDEBUG
    if( pKey1 ){
      res = memcmp(pKey, pKey1, MIN((size_t)nKey1, nKey));
      assert( res>0 || (res==0 && nKey>nKey1) );
    }
#endif

    if( pKey2 ){
      res = memcmp(pKey, pKey2, MIN((size_t)nKey2, nKey));
      if( res>0 || (res==0 && (size_t)nKey2<nKey) ){
        delete [] pKey;
        break;
      }
    }
    pCur->remove();
    delete [] pKey;
  }

  delete pCur;
  return 0;
}

int test_kc_fetch(
  TestDb *pDb, 
  void *pKey, 
  int nKey, 
  void **ppVal,
  int *pnVal
){
  KcDb *pKcDb = (KcDb *)pDb;
  size_t nVal;

  if( pKcDb->pVal ){
    delete [] pKcDb->pVal;
    pKcDb->pVal = 0;
  }

  pKcDb->pVal = pKcDb->db->get((const char *)pKey, nKey, &nVal);
  if( pKcDb->pVal ){
    *ppVal = pKcDb->pVal;
    *pnVal = nVal;
  }else{
    *ppVal = 0;
    *pnVal = -1;
  }

  return 0;
}

int test_kc_scan(
  TestDb *pDb,                    /* Database handle */
  void *pCtx,                     /* Context pointer to pass to xCallback */
  int bReverse,                   /* True for a reverse order scan */
  void *pKey1, int nKey1,         /* Start of search */
  void *pKey2, int nKey2,         /* End of search */
  void (*xCallback)(void *pCtx, void *pKey, int nKey, void *pVal, int nVal)
){
  KcDb *pKcDb = (KcDb *)pDb;
  kyotocabinet::DB::Cursor* pCur = pKcDb->db->cursor();
  int res;

  if( bReverse==0 ){
    if( pKey1 ){
      res = pCur->jump((const char *)pKey1, nKey1);
    }else{
      res = pCur->jump();
    }
  }else{
    if( pKey2 ){
      res = pCur->jump_back((const char *)pKey2, nKey2);
    }else{
      res = pCur->jump_back();
    }
  }

  while( res ){
    const char *pKey; size_t nKey;
    const char *pVal; size_t nVal;
    pKey = pCur->get(&nKey, &pVal, &nVal);

    if( bReverse==0 && pKey2 ){
      res = memcmp(pKey, pKey2, MIN((size_t)nKey2, nKey));
      if( res>0 || (res==0 && (size_t)nKey2<nKey) ){
        delete [] pKey;
        break;
      }
    }else if( bReverse!=0 && pKey1 ){
      res = memcmp(pKey, pKey1, MIN((size_t)nKey1, nKey));
      if( res<0 || (res==0 && (size_t)nKey1>nKey) ){
        delete [] pKey;
        break;
      }
    }

    xCallback(pCtx, (void *)pKey, (int)nKey, (void *)pVal, (int)nVal);
    delete [] pKey;

    if( bReverse ){
      res = pCur->step_back();
    }else{
      res = pCur->step();
    }
  }

  delete pCur;
  return 0;
}
#endif /* HAVE_KYOTOCABINET */

#ifdef HAVE_MDB 
#include "lmdb.h"

extern "C" {
  struct MdbDb {
    TestDb base;
    MDB_env *env;
    MDB_dbi dbi;
  };
}

int test_mdb_open(
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  MDB_txn *txn;
  MdbDb *pMdb;
  int rc;

  if( bClear ){
    char *zCmd = sqlite3_mprintf("rm -rf %s\n", zFilename);
    system(zCmd);
    sqlite3_free(zCmd);
  }

  pMdb = (MdbDb *)malloc(sizeof(MdbDb));
  memset(pMdb, 0, sizeof(MdbDb));

  rc = mdb_env_create(&pMdb->env);
  if( rc==0 ) rc = mdb_env_set_mapsize(pMdb->env, 1*1024*1024*1024);
  if( rc==0 ) rc = mdb_env_open(pMdb->env, zFilename, MDB_NOSYNC|MDB_NOSUBDIR, 0600);
  if( rc==0 ) rc = mdb_txn_begin(pMdb->env, NULL, 0, &txn);
  if( rc==0 ){
    rc = mdb_open(txn, NULL, 0, &pMdb->dbi);
    mdb_txn_commit(txn);
  }

  *ppDb = (TestDb *)pMdb;
  return rc;
}

int test_mdb_close(TestDb *pDb){
  MdbDb *pMdb = (MdbDb *)pDb;

  mdb_close(pMdb->env, pMdb->dbi);
  mdb_env_close(pMdb->env);
  free(pMdb);
  return 0;
}

int test_mdb_write(TestDb *pDb, void *pKey, int nKey, void *pVal, int nVal){
  int rc;
  MdbDb *pMdb = (MdbDb *)pDb;
  MDB_val val;
  MDB_val key;
  MDB_txn *txn;

  val.mv_size = nVal; 
  val.mv_data = pVal;
  key.mv_size = nKey; 
  key.mv_data = pKey;

  rc = mdb_txn_begin(pMdb->env, NULL, 0, &txn);
  if( rc==0 ){
    rc = mdb_put(txn, pMdb->dbi, &key, &val, 0);
    if( rc==0 ){
      rc = mdb_txn_commit(txn);
    }else{
      mdb_txn_abort(txn);
    }
  }
  
  return rc;
}

int test_mdb_delete(TestDb *pDb, void *pKey, int nKey){
  int rc;
  MdbDb *pMdb = (MdbDb *)pDb;
  MDB_val key;
  MDB_txn *txn;

  key.mv_size = nKey; 
  key.mv_data = pKey;
  rc = mdb_txn_begin(pMdb->env, NULL, 0, &txn);
  if( rc==0 ){
    rc = mdb_del(txn, pMdb->dbi, &key, 0);
    if( rc==0 ){
      rc = mdb_txn_commit(txn);
    }else{
      mdb_txn_abort(txn);
    }
  }
  
  return rc;
}

int test_mdb_fetch(
  TestDb *pDb, 
  void *pKey, 
  int nKey, 
  void **ppVal,
  int *pnVal
){
  int rc;
  MdbDb *pMdb = (MdbDb *)pDb;
  MDB_val key;
  MDB_txn *txn;

  key.mv_size = nKey;
  key.mv_data = pKey;

  rc = mdb_txn_begin(pMdb->env, NULL, MDB_RDONLY, &txn);
  if( rc==0 ){
    MDB_val val = {0, 0};
    rc = mdb_get(txn, pMdb->dbi, &key, &val);
    if( rc==MDB_NOTFOUND ){
      rc = 0;
      *ppVal = 0;
      *pnVal = -1;
    }else{
      *ppVal = val.mv_data;
      *pnVal = val.mv_size;
    }
    mdb_txn_commit(txn);
  }

  return rc;
}

int test_mdb_scan(
  TestDb *pDb,                    /* Database handle */
  void *pCtx,                     /* Context pointer to pass to xCallback */
  int bReverse,                   /* True for a reverse order scan */
  void *pKey1, int nKey1,         /* Start of search */
  void *pKey2, int nKey2,         /* End of search */
  void (*xCallback)(void *pCtx, void *pKey, int nKey, void *pVal, int nVal)
){
  MdbDb *pMdb = (MdbDb *)pDb;
  int rc;
  MDB_cursor_op op = bReverse ? MDB_PREV : MDB_NEXT;
  MDB_txn *txn;

  rc = mdb_txn_begin(pMdb->env, NULL, MDB_RDONLY, &txn);
  if( rc==0 ){
    MDB_cursor *csr;
    MDB_val key = {0, 0};
    MDB_val val = {0, 0};

    rc = mdb_cursor_open(txn, pMdb->dbi, &csr);
    if( rc==0 ){
      while( mdb_cursor_get(csr, &key, &val, op)==0 ){
        xCallback(pCtx, key.mv_data, key.mv_size, val.mv_data, val.mv_size);
      }
      mdb_cursor_close(csr);
    }
  }

  return rc;
}

#endif /* HAVE_MDB */