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



/* 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);

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

    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);
................................................................................

    /* 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;
}

    fflush(stdout);
    iDot++;
  }
  *piDot = iDot;
}

int testCaseNDot(void){ return 20; }

/*
** If argument "db" is actually a bt database, check if there are any
** leaked pages or blocks. Output an error message and raise an exception 
** if there are.
**
** If "db" is not a bt database, this function is a no-op.
*/
void testCaseDbLeaks(TestDb *db, int *pRc){
  if( *pRc==SQLITE4_OK ){
    bt_db *pBt = tdb_bt(db);
    if( pBt ){
      int rc;
      bt_info i;
      i.eType = BT_INFO_PAGE_LEAKS;
      i.pgno = 0;
      sqlite4_buffer_init(&i.output, 0);

      rc = sqlite4BtControl(pBt, BT_CONTROL_INFO, (void*)&i);
      if( rc==SQLITE4_OK && (*(char*)i.output.p)!='\0' ){
        rc = 1;
        testPrintError("Page leaks: %s\n", (char*)i.output.p);
      }
      sqlite4_buffer_clear(&i.output);
      *pRc = rc;
      if( rc ) test_failed();
    }
  }
}

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

    /* 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);
  }

  /* Check that no pages or blocks were leaked (bt only) */
  testCaseDbLeaks(pDb, &rc);

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

static struct Lib {
  const char *zName;
  const char *zDefaultDb;
  int (*xOpen)(const char *, const char *zFilename, int bClear, TestDb **ppDb);
} aLib[] = {
  { "bt",           "testdb.bt",        test_bt_open },
  { "fbt",          "testdb.fbt",       test_fbt_open },

  { "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 },

static struct Lib {
  const char *zName;
  const char *zDefaultDb;
  int (*xOpen)(const char *, const char *zFilename, int bClear, TestDb **ppDb);
} aLib[] = {
  { "bt",           "testdb.bt",        test_bt_open },
  { "fbt",          "testdb.fbt",       test_fbt_open },
  { "fbts",         "testdb.fbts",      test_fbts_open },
  { "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 },

#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:
**
................................................................................
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);

/*************************************************************************
** Start of bt specific things. From lsmtest_tdb4.c.
*/


/*
** Simulate a system crash during the iSync'th call to xSync(). Passing
** iSync==1 means crash the next time xSync is called.
*/
void tdb_bt_prepare_sync_crash(TestDb *pDb, int iSync);

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

#endif

#define __WRAPPER_H_

#ifdef __cplusplus
extern "C" {
#endif

#include "lsm.h"
#include "bt.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:
**
................................................................................
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);

/*************************************************************************
** Start of bt specific things. From lsmtest_tdb4.c.
*/
bt_db *tdb_bt(TestDb *pDb);

/*
** Simulate a system crash during the iSync'th call to xSync(). Passing
** iSync==1 means crash the next time xSync is called.
*/
void tdb_bt_prepare_sync_crash(TestDb *pDb, int iSync);

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

#endif

  const char *p = z;

  while( *p>='0' && *p<='9' ){
    i = i*10 + (*p - '0');
    p++;
  }
  if( *p=='K' || *p=='k' ){
    i = i * 1000;
    p++;
  }else if( *p=='M' || *p=='m' ){
    i = i * 1000000;
    p++;
  }

  if( *p ) return SQLITE4_ERROR;
  *piVal = i;
  return SQLITE4_OK;
}
................................................................................
    struct CfgParam {
      const char *zParam;
      int eParam;
    } aParam[] = {
      { "safety",         BT_CONTROL_SAFETY },
      { "autockpt",       BT_CONTROL_AUTOCKPT },
      { "multiproc",      BT_CONTROL_MULTIPROC },


      { "mt",             -1 },
      { "fastinsert",     -2 },
      { 0, 0 }
    };
    const char *z = zCfg;
    int n = strlen(z);
    char *aSpace;
................................................................................
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  return test_bt_open("fast=1", zFilename, bClear, ppDb);
}











void tdb_bt_prepare_sync_crash(TestDb *pTestDb, int iSync){
  BtDb *p = (BtDb*)pTestDb;
  assert( pTestDb->pMethods->xClose==bt_close );
  assert( p->bCrash==0 );
  p->nCrashSync = iSync;
}








/*************************************************************************
** Beginning of code for background checkpointer.
*/

struct bt_ckpter {
  sqlite4_buffer file;            /* File name */

  const char *p = z;

  while( *p>='0' && *p<='9' ){
    i = i*10 + (*p - '0');
    p++;
  }
  if( *p=='K' || *p=='k' ){
    i = i * 1024;
    p++;
  }else if( *p=='M' || *p=='m' ){
    i = i * 1024 * 1024;
    p++;
  }

  if( *p ) return SQLITE4_ERROR;
  *piVal = i;
  return SQLITE4_OK;
}
................................................................................
    struct CfgParam {
      const char *zParam;
      int eParam;
    } aParam[] = {
      { "safety",         BT_CONTROL_SAFETY },
      { "autockpt",       BT_CONTROL_AUTOCKPT },
      { "multiproc",      BT_CONTROL_MULTIPROC },
      { "blksz",          BT_CONTROL_BLKSZ },
      { "pagesz",         BT_CONTROL_PAGESZ },
      { "mt",             -1 },
      { "fastinsert",     -2 },
      { 0, 0 }
    };
    const char *z = zCfg;
    int n = strlen(z);
    char *aSpace;
................................................................................
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  return test_bt_open("fast=1", zFilename, bClear, ppDb);
}

int test_fbts_open(
  const char *zSpec, 
  const char *zFilename, 
  int bClear, 
  TestDb **ppDb
){
  return test_bt_open("fast=1 blksz=32K pagesz=512", zFilename, bClear, ppDb);
}


void tdb_bt_prepare_sync_crash(TestDb *pTestDb, int iSync){
  BtDb *p = (BtDb*)pTestDb;
  assert( pTestDb->pMethods->xClose==bt_close );
  assert( p->bCrash==0 );
  p->nCrashSync = iSync;
}

bt_db *tdb_bt(TestDb *pDb){
  if( pDb->pMethods->xClose==bt_close ){
    return ((BtDb *)pDb)->pBt;
  }
  return 0;
}

/*************************************************************************
** Beginning of code for background checkpointer.
*/

struct bt_ckpter {
  sqlite4_buffer file;            /* File name */

**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
*/




#include <sqlite4.h>

typedef struct bt_db bt_db;
typedef struct bt_cursor bt_cursor;

/* 
................................................................................
#define BT_CONTROL_SAFETY         7706392
#define BT_CONTROL_AUTOCKPT       7706393
#define BT_CONTROL_LOGSIZE        7706394
#define BT_CONTROL_MULTIPROC      7706395
#define BT_CONTROL_LOGSIZECB      7706396
#define BT_CONTROL_CHECKPOINT     7706397
#define BT_CONTROL_FAST_INSERT_OP 7706498



int sqlite4BtControl(bt_db*, int op, void *pArg);

#define BT_SAFETY_OFF    0
#define BT_SAFETY_NORMAL 1
#define BT_SAFETY_FULL   2

................................................................................
** Flags for xOpen
*/
#define BT_OPEN_DATABASE   0x0001
#define BT_OPEN_LOG        0x0002
#define BT_OPEN_SHARED     0x0004
#define BT_OPEN_READONLY   0x0008

**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
*/

#ifndef __BT_H
#define __BT_H

#include <sqlite4.h>

typedef struct bt_db bt_db;
typedef struct bt_cursor bt_cursor;

/* 
................................................................................
#define BT_CONTROL_SAFETY         7706392
#define BT_CONTROL_AUTOCKPT       7706393
#define BT_CONTROL_LOGSIZE        7706394
#define BT_CONTROL_MULTIPROC      7706395
#define BT_CONTROL_LOGSIZECB      7706396
#define BT_CONTROL_CHECKPOINT     7706397
#define BT_CONTROL_FAST_INSERT_OP 7706498
#define BT_CONTROL_BLKSZ          7706499
#define BT_CONTROL_PAGESZ         7706500

int sqlite4BtControl(bt_db*, int op, void *pArg);

#define BT_SAFETY_OFF    0
#define BT_SAFETY_NORMAL 1
#define BT_SAFETY_FULL   2

................................................................................
** Flags for xOpen
*/
#define BT_OPEN_DATABASE   0x0001
#define BT_OPEN_LOG        0x0002
#define BT_OPEN_SHARED     0x0004
#define BT_OPEN_READONLY   0x0008

#endif /* ifndef __BT_H */

  **
  ** iSafetyLevel:
  **   Current safety level. 0==off, 1==normal, 2=full.
  */
  int iSafetyLevel;               /* 0==OFF, 1==NORMAL, 2==FULL */
  int nAutoCkpt;                  /* Auto-checkpoint when log is this large */
  int bRequestMultiProc;          /* Request multi-proc support */



  /* These are used only by the bt_lock module. */
  BtShared *pShared;              /* Shared by all handles on this file */
  BtLock *pNext;                  /* Next connection using pShared */
  u32 mExclLock;                  /* Mask of exclusive locks held */
  u32 mSharedLock;                /* Mask of shared locks held */
  BtFile *pBtFile;                /* Used to defer close if necessary */

  **
  ** iSafetyLevel:
  **   Current safety level. 0==off, 1==normal, 2=full.
  */
  int iSafetyLevel;               /* 0==OFF, 1==NORMAL, 2==FULL */
  int nAutoCkpt;                  /* Auto-checkpoint when log is this large */
  int bRequestMultiProc;          /* Request multi-proc support */
  int nBlksz;                     /* Requested block-size in bytes */
  int nPgsz;                      /* Requested page-size in bytes */

  /* These are used only by the bt_lock module. */
  BtShared *pShared;              /* Shared by all handles on this file */
  BtLock *pNext;                  /* Next connection using pShared */
  u32 mExclLock;                  /* Mask of exclusive locks held */
  u32 mSharedLock;                /* Mask of shared locks held */
  BtFile *pBtFile;                /* Used to defer close if necessary */

  if( aData ){
    memcpy(&hdr, aData, sizeof(BtDbHdrCksum));
    btLogChecksum32(1, (u8*)&hdr, offsetof(BtDbHdrCksum, aCksum), 0, aCksum);
  }

  if( aData==0 || aCksum[0]!=hdr.aCksum[0] || aCksum[1]!=hdr.aCksum[1] ){
    memset(&hdr, 0, sizeof(BtDbHdrCksum));
    hdr.hdr.pgsz = BT_DEFAULT_PGSZ;
    hdr.hdr.blksz = BT_DEFAULT_BLKSZ;
    hdr.hdr.nPg = 2;
    hdr.hdr.iRoot = 2;
  }

  memcpy(pHdr, &hdr, sizeof(BtDbHdr));
}

  if( aData ){
    memcpy(&hdr, aData, sizeof(BtDbHdrCksum));
    btLogChecksum32(1, (u8*)&hdr, offsetof(BtDbHdrCksum, aCksum), 0, aCksum);
  }

  if( aData==0 || aCksum[0]!=hdr.aCksum[0] || aCksum[1]!=hdr.aCksum[1] ){
    memset(&hdr, 0, sizeof(BtDbHdrCksum));
    hdr.hdr.pgsz = pLog->pLock->nPgsz;
    hdr.hdr.blksz = pLog->pLock->nBlksz;
    hdr.hdr.nPg = 2;
    hdr.hdr.iRoot = 2;
  }

  memcpy(pHdr, &hdr, sizeof(BtDbHdr));
}

  BtPager *pPager;                /* Underlying page-based database */
  bt_cursor *pAllCsr;             /* List of all open cursors */
  int nMinMerge;
  int nScheduleAlloc;
  int bFastInsertOp;              /* Set by CONTROL_FAST_INSERT_OP */
};




typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
  sqlite4_buffer buf;
};

................................................................................
  btCsrReleaseAll(pCsr);
  if( bFreeBuffer ){
    sqlite4_buffer_clear(&pCsr->ovfl.buf);
  }
  pCsr->bSkipNext = 0;
  pCsr->bSkipPrev = 0;
  pCsr->bRequireReseek = 0;

}

static void fiCsrReset(FiCursor *pCsr){
  int i;
  bt_db *db = pCsr->base.pDb;
  for(i=0; i<pCsr->nBt; i++){
    btCsrReset(&pCsr->aSub[i].csr, 1);
................................................................................
      int iLo;                    /* pK/nK is > than cell (iLo-1) */
      int res;                    /* Result of comparison */
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
      int bLeaf = ((btFlags(aData) & BT_PGFLAGS_INTERNAL)==0);

      iLo = 0;
      iHi = nCell = btCellCount(aData, pgsz);
      if( nCell==0 ){
        rc = SQLITE4_NOTFOUND;
        break;
      }

      while( iHi>iLo ){
        int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
        pCsr->aiCell[pCsr->nPg-1] = iTst;
        rc = btCellKeyCompare(pCsr, bLeaf, aPrefix, pK, nK, &res);
        if( rc!=SQLITE4_OK || res==0 ){
          /* Cell iTst is EQUAL to pK/nK */
................................................................................
          /* Cell iTst is LARGER than pK/nK */
          iHi = iTst;
        }
      }
      if( rc!=SQLITE4_OK ) break;
      assert( iHi==iLo );

      iHi += (bLeaf==0 && res==0);
      pCsr->aiCell[pCsr->nPg-1] = iHi;
      if( bLeaf==0 ){
        pgno = btChildPgno(aData, pgsz, iHi);
      }else{
        pgno = 0;



        if( res!=0 ){
          if( eSeek==BT_SEEK_EQ ){
            if( eCsrseek==BT_CSRSEEK_RESEEK ){
              rc = SQLITE4_OK;
              if( iHi==nCell ){
                assert( pCsr->aiCell[pCsr->nPg-1]>0 );
                pCsr->aiCell[pCsr->nPg-1]--;
                pCsr->bSkipPrev = 1;
................................................................................
** bNext is true) and Pref() (if bNext is false).
*/
static int btCsrStep(BtCursor *pCsr, int bNext){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;
  int bRequireDescent = 0;


  rc = btCsrReseek(pCsr);
  if( rc==SQLITE4_OK && pCsr->nPg==0 ){
    rc = SQLITE4_NOTFOUND;
  }

  if( (pCsr->bSkipNext && bNext) || (pCsr->bSkipPrev && bNext==0) ){
    pCsr->bSkipPrev = pCsr->bSkipNext = 0;
................................................................................
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      nCell = btCellCount(aData, pgsz);




      if( nCell==0 ){
        btCsrReset(pCsr, 0);
        return SQLITE4_NOTFOUND;
      }


      /* If the cursor has descended to a leaf break out of the loop. */
      pCsr->aiCell[pCsr->nPg-1] = (bLast ? nCell : 0);
      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break;
      
      /* Otherwise, set pgno to the left or rightmost child of the page
      ** just loaded, depending on whether the cursor is seeking to the
      ** start or end of the tree.  */
      if( bLast==0 ){
        pCell = btCellFind(aData, pgsz, 0);
        pCell += sqlite4BtVarintGet32(pCell, &nByte);
................................................................................


/*
** Buffer the key and value belonging to the current cursor position
** in pCsr->ovfl.
*/
static int btCsrBuffer(BtCursor *pCsr, int bVal){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;            /* Return code */


  u8 *aData;                      /* Page data */
  u8 *pCell;                      /* Pointer to cell within aData[] */
  int nReq;                       /* Total required space */
  u8 *aOut;                       /* Output buffer */
  u8 *pKLocal = 0;                /* Pointer to local part of key */
  u8 *pVLocal = 0;                /* Pointer to local part of value (if any) */
  int nKLocal = 0;                /* Bytes of key on page */
  int nVLocal = 0;                /* Bytes of value on page */
  int nKOvfl = 0;                 /* Bytes of key on overflow pages */
  int nVOvfl = 0;                 /* Bytes of value on overflow pages */

  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
  pCell = btCellFind(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);
  pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
  if( nKLocal==0 ){
    /* Type (c) leaf cell. */
    pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
    pKLocal = pCell;
    pCell += nKLocal;
    pCell += sqlite4BtVarintGet32(pCell, &nKOvfl);
    pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
    if( nVOvfl>0 ) nVOvfl -= 1;

  }else{
    pKLocal = pCell;
    pCell += nKLocal;
    pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
    if( nVLocal==0 ){
      /* Type (b) */
      pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
      pVLocal = pCell;
      pCell += nVLocal;
      pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
    }else{
      /* Type (a) */
      pVLocal = pCell;
      nVLocal -= 2;
    }
  }

  /* A delete-key */
  if( nVLocal<0 ) nVLocal = 0;

  pCsr->ovfl.nKey = nKLocal + nKOvfl;
  pCsr->ovfl.nVal = nVLocal + nVOvfl;

  nReq = pCsr->ovfl.nKey + pCsr->ovfl.nVal;
  assert( nReq>0 );
  rc = sqlite4_buffer_resize(&pCsr->ovfl.buf, nReq);
  if( rc!=SQLITE4_OK ) return rc;

  /* Copy in local data */
  aOut = (u8*)pCsr->ovfl.buf.p;
  memcpy(aOut, pKLocal, nKLocal);
  memcpy(&aOut[nKLocal], pVLocal, nVLocal);

  /* Load in overflow data */
  if( nKOvfl || nVOvfl ){
    rc = btOverflowArrayRead(
        pCsr->base.pDb, pCell, &aOut[nKLocal + nVLocal], nKOvfl + nVOvfl
    );

  }

  return rc;
}


static int btCsrKey(BtCursor *pCsr, const void **ppK, int *pnK){
................................................................................
      break;
    }

    case BT_CONTROL_FAST_INSERT_OP: {
      db->bFastInsertOp = 1;
      break;
    }













  }

  return rc;
}

#ifndef NDEBUG

................................................................................
/*
** Iterate through the b-tree with root page iRoot. For each page used
** by the b-tree, set the corresponding entry in the aUsed[] array.
*/
static void assert_pages_used(
  bt_db *db,                      /* Database handle */
  u32 iRoot,                      /* Root page of b-tree to iterate through */

  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==SQLITE4_OK && iRoot ){
    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
    int nPgPerBlk = (pHdr->blksz / pHdr->pgsz);
    int bMeta = (iRoot==pHdr->iMRoot);
    BtLock *pLock = (BtLock*)(db->pPager);
    u8 *aUsed = pLock->aUsed;
    int rc;
    BtCursor csr;

    btCsrSetup(db, iRoot, &csr);

    rc = btCsrEnd(&csr, 0);








    while( rc==SQLITE4_OK ){
      rc = btCsrBuffer(&csr, 1);
      if( bMeta && rc==SQLITE4_OK ){
        u8 *aVal;
        int nVal;

        btCsrKey(&csr, (const void**)&aVal, &nVal);
        if( nVal!=sizeof(aSummaryKey) || memcmp(aVal, aSummaryKey, nVal) ){

          u32 iSubRoot;
          u32 iBlk;
          int i;
          btCsrData(&csr, 0, 4, (const void**)&aVal, &nVal);
          iSubRoot = btGetU32(aVal);
          iBlk = (iSubRoot / nPgPerBlk) + 1;
          assert_pages_used(db, iSubRoot, &rc);
          markBlockAsUsed(db, iBlk, aUsed);
        }
      }
      if( rc==SQLITE4_OK ) rc = btCsrStep(&csr, 1);
    }
  }
}
................................................................................
      aUsed[0] = 1;                 /* Page 1 is always in use */
      pLock->aUsed = &aUsed[-1];

      /* The scheduled-merge page, if it is allocated */
      assert_schedule_page_used(db, pLock->aUsed, &rc);

      /* Walk the main b-tree */
      assert_pages_used(db, pHdr->iRoot, &rc);

      /* Walk the meta-tree */
      assert_pages_used(db, pHdr->iMRoot, &rc);

      /* Walk the free-page list */
      assert_freelist_pages_used(db, 0, pLock->aUsed, &rc);

      /* The free-block list */
      assert_freelist_pages_used(db, 1, pLock->aUsed, &rc);

  BtPager *pPager;                /* Underlying page-based database */
  bt_cursor *pAllCsr;             /* List of all open cursors */
  int nMinMerge;
  int nScheduleAlloc;
  int bFastInsertOp;              /* Set by CONTROL_FAST_INSERT_OP */
};

/*
** Overflow buffer is valid if nKey!=0.
*/
typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
  sqlite4_buffer buf;
};

................................................................................
  btCsrReleaseAll(pCsr);
  if( bFreeBuffer ){
    sqlite4_buffer_clear(&pCsr->ovfl.buf);
  }
  pCsr->bSkipNext = 0;
  pCsr->bSkipPrev = 0;
  pCsr->bRequireReseek = 0;
  pCsr->ovfl.nKey = 0;
}

static void fiCsrReset(FiCursor *pCsr){
  int i;
  bt_db *db = pCsr->base.pDb;
  for(i=0; i<pCsr->nBt; i++){
    btCsrReset(&pCsr->aSub[i].csr, 1);
................................................................................
      int iLo;                    /* pK/nK is > than cell (iLo-1) */
      int res;                    /* Result of comparison */
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
      int bLeaf = ((btFlags(aData) & BT_PGFLAGS_INTERNAL)==0);

      iLo = 0;
      iHi = nCell = btCellCount(aData, pgsz);





      while( iHi>iLo ){
        int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
        pCsr->aiCell[pCsr->nPg-1] = iTst;
        rc = btCellKeyCompare(pCsr, bLeaf, aPrefix, pK, nK, &res);
        if( rc!=SQLITE4_OK || res==0 ){
          /* Cell iTst is EQUAL to pK/nK */
................................................................................
          /* Cell iTst is LARGER than pK/nK */
          iHi = iTst;
        }
      }
      if( rc!=SQLITE4_OK ) break;
      assert( iHi==iLo );

      iHi += (nCell>0 && bLeaf==0 && res==0);
      pCsr->aiCell[pCsr->nPg-1] = iHi;
      if( bLeaf==0 ){
        pgno = btChildPgno(aData, pgsz, iHi);
      }else{
        pgno = 0;

        if( nCell==0 ){
          rc = SQLITE4_NOTFOUND;
        }else if( res!=0 ){
          if( eSeek==BT_SEEK_EQ ){
            if( eCsrseek==BT_CSRSEEK_RESEEK ){
              rc = SQLITE4_OK;
              if( iHi==nCell ){
                assert( pCsr->aiCell[pCsr->nPg-1]>0 );
                pCsr->aiCell[pCsr->nPg-1]--;
                pCsr->bSkipPrev = 1;
................................................................................
** bNext is true) and Pref() (if bNext is false).
*/
static int btCsrStep(BtCursor *pCsr, int bNext){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;
  int bRequireDescent = 0;

  pCsr->ovfl.nKey = 0;
  rc = btCsrReseek(pCsr);
  if( rc==SQLITE4_OK && pCsr->nPg==0 ){
    rc = SQLITE4_NOTFOUND;
  }

  if( (pCsr->bSkipNext && bNext) || (pCsr->bSkipPrev && bNext==0) ){
    pCsr->bSkipPrev = pCsr->bSkipNext = 0;
................................................................................
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      nCell = btCellCount(aData, pgsz);
      pCsr->aiCell[pCsr->nPg-1] = (bLast ? nCell : 0);

      /* If the cursor has descended to a leaf break out of the loop. */
      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ){
        if( nCell==0 ){
          btCsrReset(pCsr, 0);
          rc = SQLITE4_NOTFOUND;
        }
        break;
      }



      
      /* Otherwise, set pgno to the left or rightmost child of the page
      ** just loaded, depending on whether the cursor is seeking to the
      ** start or end of the tree.  */
      if( bLast==0 ){
        pCell = btCellFind(aData, pgsz, 0);
        pCell += sqlite4BtVarintGet32(pCell, &nByte);
................................................................................


/*
** Buffer the key and value belonging to the current cursor position
** in pCsr->ovfl.
*/
static int btCsrBuffer(BtCursor *pCsr, int bVal){

  int rc = SQLITE4_OK;            /* Return code */
  if( pCsr->ovfl.nKey<=0 ){
    const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
    u8 *aData;                      /* Page data */
    u8 *pCell;                      /* Pointer to cell within aData[] */
    int nReq;                       /* Total required space */
    u8 *aOut;                       /* Output buffer */
    u8 *pKLocal = 0;                /* Pointer to local part of key */
    u8 *pVLocal = 0;                /* Pointer to local part of value, if any */
    int nKLocal = 0;                /* Bytes of key on page */
    int nVLocal = 0;                /* Bytes of value on page */
    int nKOvfl = 0;                 /* Bytes of key on overflow pages */
    int nVOvfl = 0;                 /* Bytes of value on overflow pages */

    aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
    pCell = btCellFind(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);
    pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
    if( nKLocal==0 ){
      /* Type (c) leaf cell. */
      pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
      pKLocal = pCell;
      pCell += nKLocal;
      pCell += sqlite4BtVarintGet32(pCell, &nKOvfl);
      pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
      if( nVOvfl>0 ) nVOvfl -= 1;

    }else{
      pKLocal = pCell;
      pCell += nKLocal;
      pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
      if( nVLocal==0 ){
        /* Type (b) */
        pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
        pVLocal = pCell;
        pCell += nVLocal;
        pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
      }else{
        /* Type (a) */
        pVLocal = pCell;
        nVLocal -= 2;
      }
    }

    /* A delete-key */
    if( nVLocal<0 ) nVLocal = 0;

    pCsr->ovfl.nKey = nKLocal + nKOvfl;
    pCsr->ovfl.nVal = nVLocal + nVOvfl;

    nReq = pCsr->ovfl.nKey + pCsr->ovfl.nVal;
    assert( nReq>0 );
    rc = sqlite4_buffer_resize(&pCsr->ovfl.buf, nReq);
    if( rc!=SQLITE4_OK ) return rc;

    /* Copy in local data */
    aOut = (u8*)pCsr->ovfl.buf.p;
    memcpy(aOut, pKLocal, nKLocal);
    memcpy(&aOut[nKLocal], pVLocal, nVLocal);

    /* Load in overflow data */
    if( nKOvfl || nVOvfl ){
      rc = btOverflowArrayRead(
          pCsr->base.pDb, pCell, &aOut[nKLocal + nVLocal], nKOvfl + nVOvfl
          );
    }
  }

  return rc;
}


static int btCsrKey(BtCursor *pCsr, const void **ppK, int *pnK){
................................................................................
      break;
    }

    case BT_CONTROL_FAST_INSERT_OP: {
      db->bFastInsertOp = 1;
      break;
    }

    case BT_CONTROL_BLKSZ: {
      int *pInt = (int*)pArg;
      ((BtLock*)db->pPager)->nBlksz = *pInt;
      break;
    }

    case BT_CONTROL_PAGESZ: {
      int *pInt = (int*)pArg;
      ((BtLock*)db->pPager)->nPgsz = *pInt;
      break;
    }

  }

  return rc;
}

#ifndef NDEBUG

................................................................................
/*
** Iterate through the b-tree with root page iRoot. For each page used
** by the b-tree, set the corresponding entry in the aUsed[] array.
*/
static void assert_pages_used(
  bt_db *db,                      /* Database handle */
  u32 iRoot,                      /* Root page of b-tree to iterate through */
  const void *pFirst, int nFirst, /* Starting with this key (if pFirst!=0) */
  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==SQLITE4_OK && iRoot ){
    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
    int nPgPerBlk = (pHdr->blksz / pHdr->pgsz);
    int bMeta = (iRoot==pHdr->iMRoot);
    BtLock *pLock = (BtLock*)(db->pPager);
    u8 *aUsed = pLock->aUsed;
    int rc;
    BtCursor csr;

    btCsrSetup(db, iRoot, &csr);
    if( nFirst==0 ){
      rc = btCsrEnd(&csr, 0);
    }else{
      pLock->aUsed = 0;
      rc = btCsrSeek(&csr, 0, pFirst, nFirst, BT_SEEK_GE, BT_CSRSEEK_SEEK);
      if( rc==SQLITE4_INEXACT ) rc = SQLITE4_OK;
      pLock->aUsed = aUsed;
      csr.ovfl.nKey = 0;
    }

    while( rc==SQLITE4_OK ){
      rc = btCsrBuffer(&csr, 1);
      if( bMeta && rc==SQLITE4_OK ){
        u8 *aKey; int nKey;


        btCsrKey(&csr, (const void**)&aKey, &nKey);
        if( nKey!=sizeof(aSummaryKey) || memcmp(aKey, aSummaryKey, nKey) ){
          u8 *aVal; int nVal;
          u32 iSubRoot;
          u32 iBlk;
          int i;
          btCsrData(&csr, 0, 4, (const void**)&aVal, &nVal);
          iSubRoot = btGetU32(aVal);
          iBlk = (iSubRoot / nPgPerBlk) + 1;
          assert_pages_used(db, iSubRoot, &aKey[8], nKey-8, &rc);
          markBlockAsUsed(db, iBlk, aUsed);
        }
      }
      if( rc==SQLITE4_OK ) rc = btCsrStep(&csr, 1);
    }
  }
}
................................................................................
      aUsed[0] = 1;                 /* Page 1 is always in use */
      pLock->aUsed = &aUsed[-1];

      /* The scheduled-merge page, if it is allocated */
      assert_schedule_page_used(db, pLock->aUsed, &rc);

      /* Walk the main b-tree */
      assert_pages_used(db, pHdr->iRoot, 0, 0, &rc);

      /* Walk the meta-tree */
      assert_pages_used(db, pHdr->iMRoot, 0, 0, &rc);

      /* Walk the free-page list */
      assert_freelist_pages_used(db, 0, pLock->aUsed, &rc);

      /* The free-block list */
      assert_freelist_pages_used(db, 1, pLock->aUsed, &rc);

  memset(p, 0, nByte);

  p->btl.pEnv = pEnv;
  p->btl.pVfs = sqlite4BtEnvDefault();
  p->btl.iSafetyLevel = BT_DEFAULT_SAFETY;
  p->btl.nAutoCkpt = BT_DEFAULT_AUTOCKPT;
  p->btl.bRequestMultiProc = BT_DEFAULT_MULTIPROC;


  *pp = p;
  return SQLITE4_OK;
}

static void btFreePage(BtPager *p, BtPage *pPg){
  if( pPg ){
    sqlite4_free(p->btl.pEnv, pPg->aData);

  memset(p, 0, nByte);

  p->btl.pEnv = pEnv;
  p->btl.pVfs = sqlite4BtEnvDefault();
  p->btl.iSafetyLevel = BT_DEFAULT_SAFETY;
  p->btl.nAutoCkpt = BT_DEFAULT_AUTOCKPT;
  p->btl.bRequestMultiProc = BT_DEFAULT_MULTIPROC;
  p->btl.nBlksz = BT_DEFAULT_BLKSZ;
  p->btl.nPgsz = BT_DEFAULT_PGSZ;
  *pp = p;
  return SQLITE4_OK;
}

static void btFreePage(BtPager *p, BtPage *pPg){
  if( pPg ){
    sqlite4_free(p->btl.pEnv, pPg->aData);