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 *zFilename, 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_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);


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

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

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

  if( rc!=SQLITE4_OK && p ){
    bt_close(&p->base);
  }

  *ppDb = &p->base;
  return rc;
}










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

  if( rc!=SQLITE4_OK && p ){
    bt_close(&p->base);
  }

  *ppDb = &p->base;
  return rc;
}

int test_fbt_open(
  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;
}

** b-tree pages. 
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */

/* #define BT_STDERR_DEBUG 1 */

typedef struct BtCursor BtCursor;


struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
  BtCursor *pAllCsr;             /* List of all open cursors */
  int bFastInsertOp;              /* Set by CONTROL_FAST_INSERT_OP */
};

typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
................................................................................
/* 
** Base class for both cursor types (BtCursor and FiCursor).
*/
struct bt_cursor {
  int eType;                      /* Cursor type */
  void *pExtra;                   /* Extra allocated space */
  bt_db *pDb;                     /* Database this cursor belongs to */

};

/*
** Database b-tree cursor handle.
*/
struct BtCursor {
  bt_cursor base;                 /* Base cursor class */
................................................................................
  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */
  BtOvfl ovfl;                    /* Overflow cache (see above) */

  int bRequireReseek;             /* True if a btCsrReseek() is required */
  int bSkipNext;                  /* True if next CsrNext() is a no-op */
  int bSkipPrev;                  /* True if next CsrPrev() is a no-op */


  BtCursor *pNextCsr;            /* Next cursor opened by same db handle */








};

#ifndef btErrorBkpt
int btErrorBkpt(int rc){
  static int error_cnt = 0;
  error_cnt++;
  return rc;
................................................................................
}
#endif

#if !defined(NDEBUG) 
static void btCheckPageRefs(bt_db *pDb){
  int nActual = 0;                /* Outstanding refs according to pager */
  int nExpect = 0;                /* According to the set of open cursors */
  BtCursor *pCsr;                 /* Iterator variable */

  for(pCsr=pDb->pAllCsr; pCsr; pCsr=pCsr->pNextCsr){


    if( pCsr->nPg>0 ) nExpect += pCsr->nPg;







  }
  nActual = sqlite4BtPagerRefcount(pDb->pPager);
  assert( nActual==nExpect );
}
#else
# define btCheckPageRefs(x) 
#endif
................................................................................
  pCsr->base.pDb = db;
  pCsr->iRoot = iRoot;
  sqlite4_env_config(db->pEnv, SQLITE4_ENVCONFIG_GETMM, &pCsr->ovfl.buf.pMM);
}

int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
  int rc = SQLITE4_OK;            /* Return Code */
  int nByte;                      /* Total bytes of space to allocate */

  assert( sqlite4BtPagerTransactionLevel(db->pPager)>0 );

  if( db->bFastInsertOp ){
    assert( 0 );





  }else{








    BtCursor *pCsr;                /* New cursor object */
    nByte = sizeof(BtCursor) + nExtra;
    pCsr = (BtCursor*)sqlite4_malloc(db->pEnv, nByte);
    *ppCsr = (bt_cursor*)pCsr;
    if( pCsr==0 ){
      rc = btErrorBkpt(SQLITE4_NOMEM);
    }else{
      u32 iRoot = sqlite4BtPagerDbhdr(db->pPager)->iRoot;
      btCsrSetup(db, iRoot, pCsr);






      pCsr->pNextCsr = db->pAllCsr;
      db->pAllCsr = pCsr;
    }
  }


  btCheckPageRefs(db);
  db->bFastInsertOp = 0;
  return rc;
}

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













int sqlite4BtCsrClose(bt_cursor *pCsr){
  if( pCsr ){

    bt_db *pDb = pCsr->pDb;

    btCheckPageRefs(pDb);





    if( pCsr->eType==CSR_TYPE_BT ){
      /* A regular b-tree cursor */
      BtCursor *p = (BtCursor*)pCsr;
      BtCursor **pp;
      btCsrReset(p, 1);
      for(pp=&pDb->pAllCsr; *pp!=p; pp=&(*pp)->pNextCsr);
      *pp = p->pNextCsr;
      sqlite4_free(pDb->pEnv, p);
    }else{
      /* A fast-insert-tree cursor */
      assert( 0 );

    }

    btCheckPageRefs(pDb);
  }
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return pCsr->pExtra;
................................................................................

  if( rc!=SQLITE4_OK && rc!=SQLITE4_INEXACT && eCsrseek!=BT_CSRSEEK_UPDATE ){
    btCsrReset(pCsr, 0);
  }
  return rc;
}

int sqlite4BtCsrSeek(
  bt_cursor *pBase, 
  const void *pK,                 /* Key to seek for */
  int nK,                         /* Size of key pK in bytes */
  int eSeek                       /* Seek mode (a BT_SEEK_XXX constant) */
){
  int rc;
  btCheckPageRefs(pBase->pDb);
  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;
    rc = btCsrSeek(pCsr, pK, nK, eSeek, BT_CSRSEEK_SEEK);
  }else{
    /* fast-insert-tree cursor */
    assert( 0 );
  }
  btCheckPageRefs(pBase->pDb);
  return rc;
}

/*
** This function seeks the cursor as required for either sqlite4BtCsrFirst()
** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
*/
static int btCsrEnd(BtCursor *pCsr, int bLast){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;            /* Return Code */
  u32 pgno;                       /* Page number for next page to load */

  /* Reset the cursor */
  btCsrReset(pCsr, 0);

  /* Figure out the root page number */
  assert( pCsr->iRoot>1 && pCsr->nPg==0 );
  pgno = pCsr->iRoot;

  while( rc==SQLITE4_OK ){
    /* Load page number pgno into the b-tree */
    rc = btCsrDescend(pCsr, pgno);
    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);
        pCell += nByte;
        sqlite4BtVarintGet32(pCell, (int *)&pgno);
      }else{
        pgno = btGetU32(&aData[1]);
      }
    }
  }
  if( pCsr->aiCell[pCsr->nPg-1] ) pCsr->aiCell[pCsr->nPg-1]--;
  return rc;
}

/*
** Position cursor pCsr to point to the smallest key in the database.
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrEnd((BtCursor*)pCsr, 0);
  }else{
    assert( 0 );
  }
  return rc;
}

/*
** Position cursor pCsr to point to the largest key in the database.
*/
int sqlite4BtCsrLast(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrEnd((BtCursor*)pCsr, 1);
  }else{
    assert( 0 );
  }
  return rc;
}

static int btCsrReseek(BtCursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->bRequireReseek ){
    BtOvfl ovfl;
    memcpy(&ovfl, &pCsr->ovfl, sizeof(BtOvfl));

    pCsr->ovfl.buf.n = 0;
................................................................................
      pCsr->ovfl.buf.p = ovfl.buf.p;
    }else{
      sqlite4_buffer_clear(&ovfl.buf);
    }
  }
  return rc;
}


/*
** This function does the work of both sqlite4BtCsrNext() (if parameter
** bNext is true) and Pref() (if bNext is false).
*/
static int btCsrStep(BtCursor *pCsr, int bNext){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
................................................................................
      }
    }
  }

  return rc;
}





















































































































































































/*
** Advance to the next entry in the tree.
*/
int sqlite4BtCsrNext(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
................................................................................
      u32 rootpgno = btGetU32(&pOvfl[1 + nDirect*4]);
      rc = btOverflowTrimtree(pgsz, pPager, rootpgno, nDepth);
    }
  }

  return rc;
}

int sqlite4BtCsrKey(bt_cursor *pBase, const void **ppK, int *pnK){
  int rc = SQLITE4_OK;            /* Return code */
  
  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;
    if( pCsr->bRequireReseek ){
      *ppK = (const void*)pCsr->ovfl.buf.p;
      *pnK = pCsr->ovfl.nKey;
    }else{
      const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
      u8 *aData;
      u8 *pCell;
      int nK;
      int iCell = pCsr->aiCell[pCsr->nPg-1];

      aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
      assert( btCellCount(aData, pgsz)>iCell );
      pCell = btCellFind(aData, pgsz, iCell);
      pCell += sqlite4BtVarintGet32(pCell, &nK);

      if( nK==0 ){
        /* type (c) leaf cell */
        rc = btCsrBuffer(pCsr, 0);
        if( rc==SQLITE4_OK ){
          *ppK = pCsr->ovfl.buf.p;
          *pnK = pCsr->ovfl.nKey;
        }
      }else{
        *ppK = pCell;
        *pnK = nK;
      }
    }

























  }else{













































    assert( 0 );

  }

  return rc;
}

int sqlite4BtCsrData(
  bt_cursor *pBase,               /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){
  const int pgsz = sqlite4BtPagerPagesize(pBase->pDb->pPager);
  int rc;
  u8 *aData;
  u8 *pCell;
  int nK = 0;
  int nV = 0;

  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;
    int iCell = pCsr->aiCell[pCsr->nPg-1];

    rc = btCsrReseek(pCsr);
    if( rc==SQLITE4_OK ){
      if( pCsr->bSkipNext || pCsr->bSkipPrev ){
        /* The row has been deleted out from under this cursor. So return
         ** NULL for data.  */
        *ppV = 0;
        *pnV = 0;

      }else{

        aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
        pCell = btCellFind(aData, pgsz, iCell);
        pCell += sqlite4BtVarintGet32(pCell, &nK);
        if( nK>0 ){
          pCell += nK;
          pCell += sqlite4BtVarintGet32(pCell, &nV);
        }

        if( nV==0 ){
          rc = btCsrBuffer(pCsr, 1);
          if( rc==SQLITE4_OK ){
            u8 *aBuf = (u8*)pCsr->ovfl.buf.p;
            *ppV = &aBuf[pCsr->ovfl.nKey];
            *pnV = pCsr->ovfl.nVal;
          }
        }else{
          *ppV = pCell;
          *pnV = (nV-1);
        }

#ifndef NDEBUG
        if( rc==SQLITE4_OK ){
          const void *pK; int nK;
          rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pK, &nK);
          if( rc==SQLITE4_OK ){
            BtLock *pLock = (BtLock*)pCsr->base.pDb->pPager;
            sqlite4BtDebugKV(pLock, "select", (u8*)pK, nK, (u8*)*ppV, *pnV);
          }
        }
#endif
      }
    }
  }else{

    assert( 0 );

  }

  return rc;
}

/*
** The argument points to a buffer containing an overflow array. Return
................................................................................
  nPg = (nContent + pgsz - 1) / pgsz;
  if( nPg<=BT_MAX_DIRECT_OVERFLOW ){
    return 1 + nPg*4;
  }
  return 1 + (BT_MAX_DIRECT_OVERFLOW+1) * 4;
}

static u32 btBlockToRoot(BtDbHdr *pHdr, u32 iBlk){
  assert( iBlk>0 );
  return (iBlk - 1) * (pHdr->blksz / pHdr->pgsz) + 1;
}

/*
** Allocate a non-overflow page.
**
** This function is a simple wrapper around sqlite4BtPageAllocate(),
** except that if the database is currenly in fast-insert mode the
** BtDbHdr.nSubPg counter is incremented.
*/
................................................................................
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

static int btSaveAllCursor(bt_db *pDb, BtCursor *pCsr){
  int rc = SQLITE4_OK;            /* Return code */
  BtCursor *p;                    /* Used to iterate through cursors */

  for(p=pDb->pAllCsr; rc==SQLITE4_OK && p; p=p->pNextCsr){


    if( p->nPg>0 ){
      assert( p->bRequireReseek==0 );
      rc = btCsrBuffer(p, 0);
      if( rc==SQLITE4_OK ){
        assert( p->ovfl.buf.p );
        p->bRequireReseek = 1;
        if( p!=pCsr ) btCsrReleaseAll(p);
      }
    }




  }

  return rc;
}

static int btFastInsertRoot(bt_db *db, BtDbHdr *pHdr, u32 *piRoot);

................................................................................
    rc = btFindNextLevel(db, pHdr, &iLevel);
    if( rc==SQLITE4_OK ){
      rc = btAllocateBlock(db, &iSubBlock);
    }

    if( rc==SQLITE4_OK ){
      u8 aKey[8];
      u8 aVal[8];
      pHdr->iSubBlock = iSubBlock;
      pHdr->nSubPg = 1;           /* Root page is automatically allocated */

      /* The key for the new entry consists of the concatentation of two 
      ** 32-bit big-endian integers - the <age> and <level-no>. The age
      ** of the new segment is 0. The level number is one greater than the
      ** level number of the previous segment.  */
      btPutU32(&aKey[0], 0);
      btPutU32(&aKey[4], ~iLevel);

      btPutU32(&aVal[0], iSubBlock);
      btPutU32(&aVal[4], 1);

      assert( db->bFastInsertOp==1 );
      db->bFastInsertOp = 0;
      rc = btReplaceEntry(db, pHdr->iMRoot, aKey, 8, aVal, 8);
      db->bFastInsertOp = 1;
    }
  }

  if( rc==SQLITE4_OK ){
    *piRoot = btBlockToRoot(pHdr, pHdr->iSubBlock);
  }
................................................................................
  sqlite4BtDebugKV((BtLock*)db->pPager, "replace", (u8*)pK, nK, (u8*)pV, nV);

  /* Save the position of any open cursors */
  rc = btSaveAllCursor(db, 0);
  assert( rc!=SQLITE4_NOTFOUND && rc!=SQLITE4_INEXACT );
  btCheckPageRefs(db);

  /* Seek stack cursor csr to the b-tree page that key pK/nK is/would be
  ** stored on.  */

  if( rc==SQLITE4_OK ){
    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
    u32 iRoot = 0;
    if( !db->bFastInsertOp ){

      iRoot = pHdr->iRoot;
    }
    if( rc==SQLITE4_OK ){
      rc = btReplaceEntry(db, iRoot, pK, nK, pV, nV);
    }
  }

................................................................................
    }
    if( rc==SQLITE4_OK ){
      rc = btBalanceIfUnderfull(pCsr);
    }

    btCsrReleaseAll(pCsr);
  }else{

    rc = btErrorBkpt(SQLITE4_MISUSE);
  }
  return rc;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);

** b-tree pages. 
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */

/* #define BT_STDERR_DEBUG 1 */

typedef struct BtCursor BtCursor;
typedef struct FiCursor FiCursor;

struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
  bt_cursor *pAllCsr;             /* List of all open cursors */
  int bFastInsertOp;              /* Set by CONTROL_FAST_INSERT_OP */
};

typedef struct BtOvfl BtOvfl;
struct BtOvfl {
  int nKey;
  int nVal;
................................................................................
/* 
** Base class for both cursor types (BtCursor and FiCursor).
*/
struct bt_cursor {
  int eType;                      /* Cursor type */
  void *pExtra;                   /* Extra allocated space */
  bt_db *pDb;                     /* Database this cursor belongs to */
  bt_cursor *pNextCsr;            /* Next cursor opened by same db handle */
};

/*
** Database b-tree cursor handle.
*/
struct BtCursor {
  bt_cursor base;                 /* Base cursor class */
................................................................................
  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */
  BtOvfl ovfl;                    /* Overflow cache (see above) */

  int bRequireReseek;             /* True if a btCsrReseek() is required */
  int bSkipNext;                  /* True if next CsrNext() is a no-op */
  int bSkipPrev;                  /* True if next CsrPrev() is a no-op */
};


/*
** Database f-tree cursor handle.
*/
struct FiCursor {
  bt_cursor base;                 /* Base cursor class */
  int iBt;                        /* Current sub-tree (or -1 for EOF) */
  int nBt;                        /* Number of entries in aBt[] array */
  BtCursor *aBt;                  /* Array of sub-tree cursors */
};

#ifndef btErrorBkpt
int btErrorBkpt(int rc){
  static int error_cnt = 0;
  error_cnt++;
  return rc;
................................................................................
}
#endif

#if !defined(NDEBUG) 
static void btCheckPageRefs(bt_db *pDb){
  int nActual = 0;                /* Outstanding refs according to pager */
  int nExpect = 0;                /* According to the set of open cursors */
  bt_cursor *pCsr;                /* Iterator variable */

  for(pCsr=pDb->pAllCsr; pCsr; pCsr=pCsr->pNextCsr){
    if( pCsr->eType==CSR_TYPE_BT ){
      BtCursor *p = (BtCursor*)pCsr;
      if( p->nPg>0 ) nExpect += p->nPg;
    }else{
      FiCursor *p = (FiCursor*)pCsr;
      int i;
      for(i=0; i<p->nBt; i++){
        if( p->aBt[i].nPg>0 ) nExpect += p->aBt[i].nPg;
      }
    }
  }
  nActual = sqlite4BtPagerRefcount(pDb->pPager);
  assert( nActual==nExpect );
}
#else
# define btCheckPageRefs(x) 
#endif
................................................................................
  pCsr->base.pDb = db;
  pCsr->iRoot = iRoot;
  sqlite4_env_config(db->pEnv, SQLITE4_ENVCONFIG_GETMM, &pCsr->ovfl.buf.pMM);
}

int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
  int rc = SQLITE4_OK;            /* Return Code */
  bt_cursor *pRet = 0;

  assert( sqlite4BtPagerTransactionLevel(db->pPager)>0 );

  if( db->bFastInsertOp ){
    int nByte = sizeof(FiCursor) + nExtra;
    FiCursor *pCsr;

    pCsr = (FiCursor*)sqlite4_malloc(db->pEnv, nByte);
    if( pCsr==0 ){
      rc = btErrorBkpt(SQLITE4_NOMEM);
    }else{
      memset(pCsr, 0, nByte);
      pCsr->base.eType = CSR_TYPE_FAST;
      pCsr->base.pExtra = (void*)&pCsr[1];
      pCsr->base.pDb = db;
      pRet = (bt_cursor*)pCsr;
    }

  }else{
    BtCursor *pCsr;                /* New cursor object */
    int nByte = sizeof(BtCursor) + nExtra;
    pCsr = (BtCursor*)sqlite4_malloc(db->pEnv, nByte);

    if( pCsr==0 ){
      rc = btErrorBkpt(SQLITE4_NOMEM);
    }else{
      u32 iRoot = sqlite4BtPagerDbhdr(db->pPager)->iRoot;
      btCsrSetup(db, iRoot, pCsr);
      pRet = (bt_cursor*)pCsr;
    }
  }

  assert( (pRet==0)==(rc!=SQLITE4_OK) );
  if( rc==SQLITE4_OK ){
    pRet->pNextCsr = db->pAllCsr;
    db->pAllCsr = pRet;
  }

  *ppCsr = pRet;

  btCheckPageRefs(db);
  db->bFastInsertOp = 0;
  return rc;
}

static void btCsrReleaseAll(BtCursor *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->aBt[i], 1);
  }
  sqlite4_free(db->pEnv, pCsr->aBt);
  pCsr->aBt = 0;
  pCsr->nBt = 0;
  pCsr->iBt = -1;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  if( pCsr ){
    bt_cursor **pp;
    bt_db *pDb = pCsr->pDb;

    btCheckPageRefs(pDb);

    /* Remove this cursor from the all-cursors list. */
    for(pp=&pDb->pAllCsr; *pp!=pCsr; pp=&(*pp)->pNextCsr);
    *pp = pCsr->pNextCsr;

    if( pCsr->eType==CSR_TYPE_BT ){
      /* A regular b-tree cursor */
      BtCursor *p = (BtCursor*)pCsr;

      btCsrReset(p, 1);



    }else{
      /* A fast-insert-tree cursor */

      fiCsrReset((FiCursor*)pCsr);
    }
    sqlite4_free(pDb->pEnv, pCsr);
    btCheckPageRefs(pDb);
  }
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return pCsr->pExtra;
................................................................................

  if( rc!=SQLITE4_OK && rc!=SQLITE4_INEXACT && eCsrseek!=BT_CSRSEEK_UPDATE ){
    btCsrReset(pCsr, 0);
  }
  return rc;
}


































































































static int btCsrReseek(BtCursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->bRequireReseek ){
    BtOvfl ovfl;
    memcpy(&ovfl, &pCsr->ovfl, sizeof(BtOvfl));

    pCsr->ovfl.buf.n = 0;
................................................................................
      pCsr->ovfl.buf.p = ovfl.buf.p;
    }else{
      sqlite4_buffer_clear(&ovfl.buf);
    }
  }
  return rc;
}


/*
** This function does the work of both sqlite4BtCsrNext() (if parameter
** bNext is true) and Pref() (if bNext is false).
*/
static int btCsrStep(BtCursor *pCsr, int bNext){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
................................................................................
      }
    }
  }

  return rc;
}


/*
** This function seeks the cursor as required for either sqlite4BtCsrFirst()
** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
*/
static int btCsrEnd(BtCursor *pCsr, int bLast){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;            /* Return Code */
  u32 pgno;                       /* Page number for next page to load */

  /* Reset the cursor */
  btCsrReset(pCsr, 0);

  /* Figure out the root page number */
  assert( pCsr->iRoot>1 && pCsr->nPg==0 );
  pgno = pCsr->iRoot;

  while( rc==SQLITE4_OK ){
    /* Load page number pgno into the b-tree */
    rc = btCsrDescend(pCsr, pgno);
    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);
        pCell += nByte;
        sqlite4BtVarintGet32(pCell, (int *)&pgno);
      }else{
        pgno = btGetU32(&aData[1]);
      }
    }
  }
  if( pCsr->aiCell[pCsr->nPg-1] ) pCsr->aiCell[pCsr->nPg-1]--;
  return rc;
}


static int fiCsrAllocateSubs(bt_db *db, FiCursor *pCsr, int nBt){
  int rc = SQLITE4_OK;            /* Return code */
  BtCursor *aNew;                 /* Allocated array */
  int nByte;                      /* Bytes of space to allocate */

  assert( pCsr->nBt==0 && nBt>0 );
  nByte = sizeof(BtCursor) * nBt;
  aNew = (BtCursor*)sqlite4_malloc(db->pEnv, nByte);
  if( aNew ){
    memset(aNew, 0, nByte);
    pCsr->aBt = aNew;
    pCsr->nBt = nBt;
  }else{
    rc = btErrorBkpt(SQLITE4_NOMEM);
  }

  return rc;
}

static u32 btBlockToRoot(BtDbHdr *pHdr, u32 iBlk){
  assert( iBlk>0 );
  return (iBlk - 1) * (pHdr->blksz / pHdr->pgsz) + 1;
}

/*
** Seek a fast-insert cursor.
*/
static int fiCsrSeek(FiCursor *pCsr, const void *pK, int nK, int eSeek){
  int rc = SQLITE4_OK;            /* Return code */
  bt_db *db = pCsr->base.pDb;     /* Database handle */
  BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);

  assert( eSeek==BT_SEEK_LE || eSeek==BT_SEEK_EQ || eSeek==BT_SEEK_GE );
  fiCsrReset(pCsr);

  if( pHdr->iMRoot ){
    if( eSeek==BT_SEEK_EQ ){
      /* A BT_SEEK_EQ is a special case. There is no need to set up a cursor
      ** that can be advanced (in either direction) in this case. All that
      ** is required is to search each level in order for the requested key 
      ** (or a corresponding delete marker). Once a match is found, there
      ** is no need to search any further.  */
      rc = fiCsrAllocateSubs(db, pCsr, 1);

      if( rc==SQLITE4_OK ){
        BtCursor mcsr;            /* Used to iterate through the meta-tree */
        BtCursor *pSub = pCsr->aBt;

        /* Loop through the set of f-tree levels */
        btCsrSetup(db, pHdr->iMRoot, &mcsr);
        for(rc=btCsrEnd(&mcsr, 0); rc==SQLITE4_OK; rc=btCsrStep(&mcsr, 1)){
          const void *pV; int nV; /* Value associated with meta-tree entry */
          u32 iBlk;               /* Block containing sub-tree */

          sqlite4BtCsrData(&mcsr.base, 0, 4, &pV, &nV);
          iBlk = sqlite4BtGetU32((const u8*)pV);
          btCsrReset(pSub, 1);
          btCsrSetup(db, btBlockToRoot(pHdr, iBlk), pSub);
          rc = btCsrSeek(pSub, pK, nK, BT_SEEK_EQ, BT_CSRSEEK_SEEK);
          if( rc!=SQLITE4_NOTFOUND && rc!=SQLITE4_INEXACT ){
            /* A hit on the requested key or an error has occurred. Either
            ** way, break out of the loop. If this is a hit, set iBt to
            ** zero so that the BtCsrKey() and BtCsrData() routines know
            ** to return data from the first (only) sub-cursor. */
            if( rc==SQLITE4_OK ) pCsr->iBt = 0;
            break;
          }
        }
        btCsrReset(&mcsr, 1);
      }
    }else{
      /* Deal with this later... */
      assert( 0 );
    }
  }else{
    rc = SQLITE4_NOTFOUND;
  }

  return rc;
}

int sqlite4BtCsrSeek(
  bt_cursor *pBase, 
  const void *pK,                 /* Key to seek for */
  int nK,                         /* Size of key pK in bytes */
  int eSeek                       /* Seek mode (a BT_SEEK_XXX constant) */
){
  int rc;
  btCheckPageRefs(pBase->pDb);
  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;
    rc = btCsrSeek(pCsr, pK, nK, eSeek, BT_CSRSEEK_SEEK);
  }else{
    rc = fiCsrSeek((FiCursor*)pBase, pK, nK, eSeek);
  }
  btCheckPageRefs(pBase->pDb);
  return rc;
}

/*
** Position cursor pCsr to point to the smallest key in the database.
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrEnd((BtCursor*)pCsr, 0);
  }else{
    assert( 0 );
  }
  return rc;
}

/*
** Position cursor pCsr to point to the largest key in the database.
*/
int sqlite4BtCsrLast(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrEnd((BtCursor*)pCsr, 1);
  }else{
    assert( 0 );
  }
  return rc;
}


/*
** Advance to the next entry in the tree.
*/
int sqlite4BtCsrNext(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
................................................................................
      u32 rootpgno = btGetU32(&pOvfl[1 + nDirect*4]);
      rc = btOverflowTrimtree(pgsz, pPager, rootpgno, nDepth);
    }
  }

  return rc;
}

static int btCsrKey(BtCursor *pCsr, const void **ppK, int *pnK){
  int rc = SQLITE4_OK;



  if( pCsr->bRequireReseek ){
    *ppK = (const void*)pCsr->ovfl.buf.p;
    *pnK = pCsr->ovfl.nKey;
  }else{
    const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
    u8 *aData;
    u8 *pCell;
    int nK;
    int iCell = pCsr->aiCell[pCsr->nPg-1];

    aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
    assert( btCellCount(aData, pgsz)>iCell );
    pCell = btCellFind(aData, pgsz, iCell);
    pCell += sqlite4BtVarintGet32(pCell, &nK);

    if( nK==0 ){
      /* type (c) leaf cell */
      rc = btCsrBuffer(pCsr, 0);
      if( rc==SQLITE4_OK ){
        *ppK = pCsr->ovfl.buf.p;
        *pnK = pCsr->ovfl.nKey;
      }
    }else{
      *ppK = pCell;
      *pnK = nK;
    }
  }

  return rc;
}

static int btCsrData(
  BtCursor *pCsr,                 /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc;
  u8 *aData;
  u8 *pCell;
  int nK = 0;
  int nV = 0;

  rc = btCsrReseek(pCsr);
  if( rc==SQLITE4_OK ){
    if( pCsr->bSkipNext || pCsr->bSkipPrev ){
      /* The row has been deleted out from under this cursor. So return
       ** NULL for data.  */
      *ppV = 0;
      *pnV = 0;
    }else{
      int iCell = pCsr->aiCell[pCsr->nPg-1];

      aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
      pCell = btCellFind(aData, pgsz, iCell);
      pCell += sqlite4BtVarintGet32(pCell, &nK);
      if( nK>0 ){
        pCell += nK;
        pCell += sqlite4BtVarintGet32(pCell, &nV);
      }

      if( nV==0 ){
        rc = btCsrBuffer(pCsr, 1);
        if( rc==SQLITE4_OK ){
          u8 *aBuf = (u8*)pCsr->ovfl.buf.p;
          *ppV = &aBuf[pCsr->ovfl.nKey];
          *pnV = pCsr->ovfl.nVal;
        }
      }else{
        *ppV = pCell;
        *pnV = (nV-1);
      }

#ifndef NDEBUG
      if( rc==SQLITE4_OK ){
        const void *pK; int nK;
        rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pK, &nK);
        if( rc==SQLITE4_OK ){
          BtLock *pLock = (BtLock*)pCsr->base.pDb->pPager;
          sqlite4BtDebugKV(pLock, "select", (u8*)pK, nK, (u8*)*ppV, *pnV);
        }
      }
#endif
    }
  }

  return rc;
}

int sqlite4BtCsrKey(bt_cursor *pBase, const void **ppK, int *pnK){
  int rc = SQLITE4_OK;            /* Return code */
  
  if( pBase->eType==CSR_TYPE_BT ){
    rc = btCsrKey((BtCursor*)pBase, ppK, pnK);
  }else{
    FiCursor *pCsr = (FiCursor*)pBase;
    assert( pCsr->iBt>=0 );
    rc = btCsrKey(&pCsr->aBt[pCsr->iBt], ppK, pnK);
  }

  return rc;
}

int sqlite4BtCsrData(
  bt_cursor *pBase,               /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){
  int rc = SQLITE4_OK;            /* Return code */





  
  if( pBase->eType==CSR_TYPE_BT ){










    rc = btCsrData((BtCursor*)pBase, iOffset, nByte, ppV, pnV);
  }else{


































    FiCursor *pCsr = (FiCursor*)pBase;
    assert( pCsr->iBt>=0 );
    rc = btCsrData(&pCsr->aBt[pCsr->iBt], iOffset, nByte, ppV, pnV);
  }

  return rc;
}

/*
** The argument points to a buffer containing an overflow array. Return
................................................................................
  nPg = (nContent + pgsz - 1) / pgsz;
  if( nPg<=BT_MAX_DIRECT_OVERFLOW ){
    return 1 + nPg*4;
  }
  return 1 + (BT_MAX_DIRECT_OVERFLOW+1) * 4;
}






/*
** Allocate a non-overflow page.
**
** This function is a simple wrapper around sqlite4BtPageAllocate(),
** except that if the database is currenly in fast-insert mode the
** BtDbHdr.nSubPg counter is incremented.
*/
................................................................................
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

static int btSaveAllCursor(bt_db *pDb, BtCursor *pCsr){
  int rc = SQLITE4_OK;            /* Return code */
  bt_cursor *p;                   /* Used to iterate through cursors */

  for(p=pDb->pAllCsr; rc==SQLITE4_OK && p; p=p->pNextCsr){
    if( p->eType==CSR_TYPE_BT ){
      BtCursor *pCsr = (BtCursor*)p;
      if( pCsr->nPg>0 ){
        assert( pCsr->bRequireReseek==0 );
        rc = btCsrBuffer(pCsr, 0);
        if( rc==SQLITE4_OK ){
          assert( pCsr->ovfl.buf.p );
          pCsr->bRequireReseek = 1;
          if( pCsr!=pCsr ) btCsrReleaseAll(pCsr);
        }
      }
    }else{
      /* ?? */
    }

  }

  return rc;
}

static int btFastInsertRoot(bt_db *db, BtDbHdr *pHdr, u32 *piRoot);

................................................................................
    rc = btFindNextLevel(db, pHdr, &iLevel);
    if( rc==SQLITE4_OK ){
      rc = btAllocateBlock(db, &iSubBlock);
    }

    if( rc==SQLITE4_OK ){
      u8 aKey[8];
      u8 aVal[4];
      pHdr->iSubBlock = iSubBlock;
      pHdr->nSubPg = 1;           /* Root page is automatically allocated */

      /* The key for the new entry consists of the concatentation of two 
      ** 32-bit big-endian integers - the <age> and <level-no>. The age
      ** of the new segment is 0. The level number is one greater than the
      ** level number of the previous segment.  */
      btPutU32(&aKey[0], 0);
      btPutU32(&aKey[4], ~iLevel);

      btPutU32(&aVal[0], iSubBlock);


      assert( db->bFastInsertOp==1 );
      db->bFastInsertOp = 0;
      rc = btReplaceEntry(db, pHdr->iMRoot, aKey, 8, aVal, 4);
      db->bFastInsertOp = 1;
    }
  }

  if( rc==SQLITE4_OK ){
    *piRoot = btBlockToRoot(pHdr, pHdr->iSubBlock);
  }
................................................................................
  sqlite4BtDebugKV((BtLock*)db->pPager, "replace", (u8*)pK, nK, (u8*)pV, nV);

  /* Save the position of any open cursors */
  rc = btSaveAllCursor(db, 0);
  assert( rc!=SQLITE4_NOTFOUND && rc!=SQLITE4_INEXACT );
  btCheckPageRefs(db);

  /* Call btReplaceEntry() to update either the main b-tree or the top-level
  ** sub-tree. Pass iRoot=0 to update the sub-tree, or the root page number
  ** of the b-tree to update the b-tree.  */
  if( rc==SQLITE4_OK ){

    u32 iRoot = 0;
    if( !db->bFastInsertOp ){
      BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
      iRoot = pHdr->iRoot;
    }
    if( rc==SQLITE4_OK ){
      rc = btReplaceEntry(db, iRoot, pK, nK, pV, nV);
    }
  }

................................................................................
    }
    if( rc==SQLITE4_OK ){
      rc = btBalanceIfUnderfull(pCsr);
    }

    btCsrReleaseAll(pCsr);
  }else{
    /* Fast-insert cursors do not support BtDelete(). */
    rc = btErrorBkpt(SQLITE4_MISUSE);
  }
  return rc;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);