SQLite4  Check-in [fc9cdc6ca3]

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

**   call to the xSync() VFS method (on either the db or log file).
**   If nCrashSync==2, the following call to xSync(), and so on.
**
** bCrash:
**   After a crash is simulated, this variable is set. Any subsequent
**   attempts to write to a file or modify the file system in any way 
**   fail once this is set. All the caller can do is close the connection.
**
** bFastInsert:
**   If this variable is set to true, then a BT_CONTROL_FAST_INSERT_OP
**   control is issued before each callto BtReplace() or BtCsrOpen().
*/
struct BtDb {
  TestDb base;                    /* Base class */
  bt_db *pBt;                     /* bt database handle */
  sqlite4_env *pEnv;              /* SQLite environment (for malloc/free) */
  bt_env *pVfs;                   /* Underlying VFS */
  int bFastInsert;                /* True to use fast-insert */

  /* Space for bt_fetch() results */
  u8 *aBuffer;                    /* Space to store results */
  int nBuffer;                    /* Allocated size of aBuffer[] in bytes */
  int nRef;

  /* Background checkpointer used by mt connections */

static int bt_write(TestDb *pTestDb, void *pK, int nK, void *pV, int nV){
  BtDb *p = (BtDb*)pTestDb;
  int iLevel;
  int rc;

  rc = btMinTransaction(p, 2, &iLevel);
  if( rc==SQLITE4_OK ){
    if( p->bFastInsert ) sqlite4BtControl(p->pBt, BT_CONTROL_FAST_INSERT_OP, 0);
    rc = sqlite4BtReplace(p->pBt, pK, nK, pV, nV);
    rc = btRestoreTransaction(p, iLevel, rc);
  }
  return rc;
}

static int bt_delete(TestDb *pTestDb, void *pK, int nK){

  BtDb *p = (BtDb*)pTestDb;
  bt_cursor *pCsr = 0;
  int rc = SQLITE4_OK;
  int iLevel;

  rc = btMinTransaction(p, 2, &iLevel);
  if( rc==SQLITE4_OK ){
    if( p->bFastInsert ) sqlite4BtControl(p->pBt, BT_CONTROL_FAST_INSERT_OP, 0);
    rc = sqlite4BtCsrOpen(p->pBt, 0, &pCsr);
  }
  while( rc==SQLITE4_OK ){
    const void *pK;
    int n;
    int nCmp;
    int res;

  iLevel = sqlite4BtTransactionLevel(p->pBt);
  if( iLevel==0 ){ 
    rc = sqlite4BtBegin(p->pBt, 1); 
    if( rc!=SQLITE4_OK ) return rc;
  }

  if( p->bFastInsert ) sqlite4BtControl(p->pBt, BT_CONTROL_FAST_INSERT_OP, 0);
  rc = sqlite4BtCsrOpen(p->pBt, 0, &pCsr);
  if( rc==SQLITE4_OK ){
    rc = sqlite4BtCsrSeek(pCsr, pK, nK, BT_SEEK_EQ);
    if( rc==SQLITE4_OK ){
      const void *pV = 0;
      int nV = 0;
      rc = sqlite4BtCsrData(pCsr, 0, -1, &pV, &nV);

  bt_cursor *pCsr = 0;
  int rc;
  int iLevel;

  rc = btMinTransaction(p, 1, &iLevel);

  if( rc==SQLITE4_OK ){
    if( p->bFastInsert ) sqlite4BtControl(p->pBt, BT_CONTROL_FAST_INSERT_OP, 0);
    rc = sqlite4BtCsrOpen(p->pBt, 0, &pCsr);
  }
  if( rc==SQLITE4_OK ){
    if( bReverse ){
      if( pLast ){
        rc = sqlite4BtCsrSeek(pCsr, pLast, nLast, BT_SEEK_LE);
      }else{

  }

  if( *p ) return SQLITE4_ERROR;
  *piVal = i;
  return SQLITE4_OK;
}

static int testBtConfigure(BtDb *pDb, const char *zCfg, int *pbMt){
  int rc = SQLITE4_OK;

  if( zCfg ){
    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 *zOpt;
    const char *zArg;

    aSpace = (char*)testMalloc(n+2);
    while( rc==SQLITE4_OK && 0==testParseOption(&z, &zOpt, &zArg, aSpace) ){
      int i;
      int iVal;
      rc = testArgSelect(aParam, "param", zOpt, &i);
      if( rc!=SQLITE4_OK ) break;

      rc = testParseInt(zArg, &iVal);
      if( rc!=SQLITE4_OK ) break;

      switch( aParam[i].eParam ){
        case -1:
          *pbMt = iVal;
          break;
        case -2:
          pDb->bFastInsert = 1;
          break;
        default:
          rc = sqlite4BtControl(pDb->pBt, aParam[i].eParam, (void*)&iVal);
          break;
      }
    }
    testFree(aSpace);
  }

  return rc;
}

    p->env.xShmMap = btVfsShmMap;
    p->env.xShmBarrier = btVfsShmBarrier;
    p->env.xShmUnmap = btVfsShmUnmap;

    sqlite4BtControl(pBt, BT_CONTROL_GETVFS, (void*)&p->pVfs);
    sqlite4BtControl(pBt, BT_CONTROL_SETVFS, (void*)&p->env);

    rc = testBtConfigure(p, zSpec, &mt);
    if( rc==SQLITE4_OK ){
      rc = sqlite4BtOpen(pBt, zFilename);
    }

    if( rc==SQLITE4_OK && mt ){
      int nAuto = 0;
      rc = bgc_attach(p, zSpec);

  BtDb *pDb = 0;
  int rc;
  int mt;
  bt_ckpter *pCkpter = (bt_ckpter*)pArg;

  rc = test_bt_open("", (char*)pCkpter->file.p, 0, (TestDb**)&pDb);
  assert( rc==SQLITE4_OK );
  rc = testBtConfigure(pDb, (char*)pCkpter->spec.p, &mt);

  while( pCkpter->nRef>0 ){
    bt_db *db = pDb->pBt;
    int nLog = 0;

    sqlite4BtBegin(db, 1);
    sqlite4BtCommit(db, 0);

void testPrintError(const char *zFormat, ...){
  va_list ap;
  va_start(ap, zFormat);
  vfprintf(stderr, zFormat, ap);
  va_end(ap);
}

void testPrintFUsage(const char *zFormat, ...){
  va_list ap;
  va_start(ap, zFormat);
  fprintf(stderr, "Usage: %s %s ", g.argv[0], g.argv[1]);
  vfprintf(stderr, zFormat, ap);
  fprintf(stderr, "\n");
  va_end(ap);
}

void testPrintUsage(const char *zArgs){
  testPrintError("Usage: %s %s %s\n", g.argv[0], g.argv[1], zArgs);
}


static void argError(void *aData, const char *zType, int sz, const char *zArg){
  struct Entry { const char *zName; };
  struct Entry *pEntry;
  const char *zPrev = 0;

  testPrintError("unrecognized %s \"%s\": must be ", zType, zArg);

#ifndef MAX
# define MAX(a,b) (((a)>(b))?(a):(b))
#endif

/* By default pages are 1024 bytes in size. */
#define BT_DEFAULT_PGSZ 1024

/* By default blocks are 512K bytes in size. */
#define BT_DEFAULT_BLKSZ (512*1024)

typedef struct BtDbHdr BtDbHdr;
struct BtDbHdr {
  u32 pgsz;                       /* Page size in bytes */
  u32 nPg;                        /* Size of database file in pages */

  u32 iRoot;                      /* B-tree root page */
  u32 iMRoot;                     /* Root page of meta-tree */
  u32 iSRoot;                     /* Root page of schedule-tree */

  u32 iSubRoot;                   /* Root of current sub-tree */
  u32 nSubPg;                     /* Number of non-overflow pages in sub-tree */

  u32 iCookie;                    /* Current value of schema cookie */
  u32 iFreePg;                    /* First page in free-page list trunk */
  u32 iFreeBlk;                   /* First page in free-block list trunk */
};

/*************************************************************************
** Interface to bt_pager.c functionality.

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager*);

/* 
** Query for the db header values. Requires an open read transaction.
*/
BtDbHdr *sqlite4BtPagerDbhdr(BtPager*);

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager*, u32 pgno, BtPage **ppPage);
int sqlite4BtPageTrimPgno(BtPager*, u32 pgno);
int sqlite4BtPageWrite(BtPage*);

static void btLogChecksum32(
  int nativeCksum,                /* True for native byte-order, else false */
  u8 *a,                          /* Content to be checksummed */
  int nByte,                      /* Bytes of content in a[]. */
  const u32 *aIn,                 /* Initial checksum value input */
  u32 *aOut                       /* OUT: Final checksum value output */
){
  assert( nByte>=8 );
  if( nByte&0x00000007 ){
    btLogChecksum(nativeCksum, a, 8, aIn, aOut);
    btLogChecksum(nativeCksum, &a[4], nByte-4, aOut, aOut);
  }else{
    btLogChecksum(nativeCksum, a, nByte, aIn, aOut);
  }
}

#define BT_PAGE_DEBUG 0
#define BT_VAL_DEBUG  0
#define BT_HDR_DEBUG  0

static void btDebugTopology(BtLock *pLock, char *zStr, int iSide, u32 *aLog){

static int btLogUpdateSharedHdr(BtLog *pLog){
  bt_env *pVfs = pLog->pLock->pVfs;
  BtShmHdr *p = &pLog->snapshot;
  BtShm *pShm = btLogShm(pLog);

  /* Calculate a checksum for the private snapshot object. */
  btLogChecksum32(1, (u8*)p, offsetof(BtShmHdr, aCksum), 0, p->aCksum);

  /* Update the shared object. */
  pVfs->xShmBarrier(pLog->pFd);
  memcpy(&pShm->hdr1, p, sizeof(BtShmHdr));
  pVfs->xShmBarrier(pLog->pFd);
  memcpy(&pShm->hdr2, p, sizeof(BtShmHdr));

  aLog[5] = iLast;
  return btLogHashRollback(pLog, btLogFrameHash(pLog, iLast), iLast);
}

static void btLogDecodeDbhdr(BtLog *pLog, u8 *aData, BtDbHdr *pHdr){
  BtDbHdrCksum hdr;
  u32 aCksum[2] = {0,0};

  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.nPg = 2;
    hdr.hdr.iRoot = 2;

  return rc;
}

static int btLogUpdateDbhdr(BtLog *pLog, u8 *aData){
  BtDbHdrCksum hdr;

  memcpy(&hdr.hdr, &pLog->snapshot.dbhdr, sizeof(BtDbHdr));
  btLogChecksum32(1, (u8*)&hdr, offsetof(BtDbHdrCksum, aCksum), 0, hdr.aCksum);
  btDebugDbhdr(pLog->pLock, "update", &pLog->snapshot.dbhdr);

  assert( hdr.hdr.iRoot==2 );
  assert( hdr.hdr.pgsz>0 );
  memcpy(aData, &hdr, sizeof(BtDbHdrCksum));

#ifndef NDEBUG
  {
    BtDbHdr tst;
    btLogDecodeDbhdr(pLog, aData, &tst);
    assert( 0==memcmp(&tst, &pLog->snapshot.dbhdr, sizeof(tst)) );
  }
#endif

  return SQLITE4_OK;
}


/*
** Run log recovery. In other words, read the log file from disk and 

/*
** Return true if the checksum in BtShmHdr.aCksum[] matches the rest
** of the object.
*/
static int btLogChecksumOk(BtShmHdr *pHdr){
  u32 aCksum[2];
  btLogChecksum32(1, (u8*)pHdr, offsetof(BtShmHdr, aCksum), 0, aCksum);
  return (aCksum[0]==pHdr->aCksum[0] && aCksum[1]==pHdr->aCksum[1]);
}

static int btLogSnapshot(BtLog *pLog, BtShmHdr *pHdr){
  int rc;

  rc = btLogMapShm(pLog, 0);

** Values that make up the single byte flags field at the start of
** 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;
  sqlite4_buffer buf;
};

/*
** Candidate values for bt_cursor.eType.
*/
#define CSR_TYPE_BT    0          /* Regular b-tree cursor */
#define CSR_TYPE_FAST  1          /* Fast-insert-tree cursor */

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

  u32 iRoot;                      /* Root page of b-tree this cursor queries */
  int nPg;                        /* Number of valid entries in apPage[] */
  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 );
}

  return rc;
}

int sqlite4BtTransactionLevel(bt_db *db){
  return sqlite4BtPagerTransactionLevel(db->pPager);
}

static void btCsrSetup(bt_db *db, u32 iRoot, BtCursor *pCsr){
  memset(pCsr, 0, sizeof(BtCursor));
  pCsr->base.pExtra = (void*)&pCsr[1];
  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){
  int i;
  for(i=0; i<pCsr->nPg; i++){
    sqlite4BtPageRelease(pCsr->apPage[i]);
  }
  pCsr->nPg = 0;
}


static void btCsrReset(BtCursor *pCsr, int bFreeBuffer){
  btCsrReleaseAll(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;
}

/*
** Set pCsr->apPage[pCsr->nPg] to a reference to database page pgno.
*/
static int btCsrDescend(BtCursor *pCsr, u32 pgno){
  int rc;
  if( pCsr->nPg>=BT_MAX_DEPTH ){
    rc = btErrorBkpt(SQLITE4_CORRUPT);
  }else{
    bt_db *pDb = pCsr->base.pDb;
    rc = sqlite4BtPageGet(pDb->pPager, pgno, &pCsr->apPage[pCsr->nPg]);
    if( rc==SQLITE4_OK ){
      assert( pCsr->apPage[pCsr->nPg] );
      pCsr->nPg++;
    }
  }
  return rc;
}

/*
** Move the cursor from the current page to the parent. Return 
** SQLITE4_NOTFOUND if the cursor already points to the root page,
** or SQLITE4_OK otherwise.
*/
static int btCsrAscend(BtCursor *pCsr, int nLvl){
  int i;
  for(i=0; i<nLvl && ( pCsr->nPg>0 ); i++){
    pCsr->nPg--;
    sqlite4BtPageRelease(pCsr->apPage[pCsr->nPg]);
    pCsr->apPage[pCsr->nPg] = 0;
  }
  return (pCsr->nPg==0 ? SQLITE4_NOTFOUND : SQLITE4_OK);

  }
  sqlite4BtBufAppendf(pBuf, ")\n");

  for(i=0; i<nCell; i++){
    int nKey;
    int j;
    u8 *pCell = btCellFind(aData, nData, i);
    sqlite4BtBufAppendf(pBuf, "  Cell %d: ", i);

    pCell += sqlite4BtVarintGet32(pCell, &nKey);
    for(j=0; j<nKey; j++){
      sqlite4BtBufAppendf(pBuf, "%02X", (int)pCell[j]);
    }

    if( btFlags(aData) & BT_PGFLAGS_INTERNAL ){
      sqlite4BtBufAppendf(pBuf, "  child=%d ", (int)btGetU32(&pCell[j]));
    }else{
      int nVal;
      pCell += nKey;
      sqlite4BtBufAppendf(pBuf, "  ");
      pCell += sqlite4BtVarintGet32(pCell, &nVal);
      for(j=0; j<(nVal-1); j++){
        sqlite4BtBufAppendf(pBuf, "%02X", (int)pCell[j]);
      }
    }
    sqlite4BtBufAppendf(pBuf, "\n");
  }
}

int sqlite4BtDebugPage(sqlite4_buffer *pBuf, u32 pgno, char *aData, int nData){
  btPageToAscii(pgno, (u8*)aData, nData, pBuf);

**
**     *piRes = (C - K).
**
** In other words, *piRes is +ve, zero or -ve if C is respectively larger, 
** equal to or smaller than K.
*/
static int btCellKeyCompare(
  BtCursor *pCsr,                 /* Cursor handle */
  int bLeaf,                      /* True if cursor currently points to leaf */
  const void *pK, int nK,         /* Key to compare against cursor key */
  int *piRes                      /* OUT: Result of comparison */
){
  const void *pCsrKey;
  int nCsrKey;
  int nCmp;
  int nAscend = 0;
  int rc = SQLITE4_OK;
  int res;

  if( bLeaf ){
    rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pCsrKey, &nCsrKey);
  }else{
    const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);

    u8 *aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
    u8 *pCell = btCellFind(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);

    pCsrKey = pCell + sqlite4BtVarintGet32(pCell, &nCsrKey);
    if( nCsrKey==0 ){
      int iCell = pCsr->aiCell[pCsr->nPg-1]+1;
      while( 1 ){
        u8 *aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
        u32 pgno = btChildPgno(aData, pgsz, iCell);
        nAscend++;
        rc = btCsrDescend(pCsr, pgno);
        if( rc!=SQLITE4_OK ) break;
        aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
        pCsr->aiCell[pCsr->nPg-1] = 0;
        if( (btFlags(aData) & BT_PGFLAGS_INTERNAL)==0 ) break;
        iCell = 0;
      }
      rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pCsrKey, &nCsrKey);
    }
  }

  if( rc==SQLITE4_OK ){
    nCmp = MIN(nCsrKey, nK);
    res = memcmp(pCsrKey, pK, nCmp);
    if( res==0 ){

}

#define BT_CSRSEEK_SEEK   0
#define BT_CSRSEEK_UPDATE 1
#define BT_CSRSEEK_RESEEK 2

static int btCsrSeek(
  BtCursor *pCsr, 
  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 eCsrseek
){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  u32 pgno;                       /* Page number for next page to load */
  int rc = SQLITE4_OK;            /* Return Code */

  assert( eSeek==BT_SEEK_EQ || eCsrseek!=BT_CSRSEEK_RESEEK );
  assert( eSeek==BT_SEEK_GE || eCsrseek!=BT_CSRSEEK_UPDATE );

  /* 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 && pgno ){
    /* 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 iHi;                    /* pK/nK is <= than cell iHi */

              }
            }else{
              rc = SQLITE4_NOTFOUND;
            }
          }else{
            assert( BT_SEEK_LEFAST<0 && BT_SEEK_LE<0 );
            if( eSeek<0 ){
              rc = sqlite4BtCsrPrev((bt_cursor*)pCsr);
            }else{
              if( iHi==nCell ){
                if( eCsrseek==BT_CSRSEEK_UPDATE ){
                  rc = SQLITE4_NOTFOUND;
                }else{
                  rc = sqlite4BtCsrNext((bt_cursor*)pCsr);
                }
              }
            }
            if( rc==SQLITE4_OK ) rc = SQLITE4_INEXACT;
          }
        }
      }
    }
  }

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

  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 = 0;

}


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

}


/*
** Advance to the next entry in the tree.
*/
int sqlite4BtCsrNext(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrStep((BtCursor*)pCsr, 1);
  }else{
    assert( 0 );
  }
  return rc;
}

/*
** Retreat to the previous entry in the tree.
*/
int sqlite4BtCsrPrev(bt_cursor *pCsr){
  int rc;
  if( pCsr->eType==CSR_TYPE_BT ){
    rc = btCsrStep((BtCursor*)pCsr, 0);
  }else{
    assert( 0 );
  }
  return rc;
}

static int btOverflowArrayRead(
  bt_db *db,
  u8 *pOvfl,
  u8 *aOut,
  int nOut

  return rc;
}

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

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

/*
** Cursor pCsr currently points to a leaf page cell. If the leaf page
** cell contains an overflow array, all overflow pages are trimmed here.
**
** SQLITE4_OK is returned if no error occurs, or an SQLite4 error code
** otherwise.
*/
static int btOverflowDelete(BtCursor *pCsr){
  BtPager *pPager = pCsr->base.pDb->pPager;
  const int pgsz = sqlite4BtPagerPagesize(pPager);
  u8 *aData;
  u8 *pCell;
  u8 *pOvfl = 0;
  int iCell = pCsr->aiCell[pCsr->nPg-1];
  int n;
  int rc = SQLITE4_OK;

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


/*
** 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.
*/
static int btAllocateNonOverflow(bt_db *db, BtPage **ppPg){
  int rc = sqlite4BtPageAllocate(db->pPager, ppPg);
  if( rc==SQLITE4_OK && db->bFastInsertOp ){
    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
    pHdr->nSubPg++;
  }
  return rc;
}

/*
** Trim 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.
*/
static int btTrimNonOverflow(bt_db *db, BtPage *pPg){
  int rc = sqlite4BtPageTrim(pPg);
  if( rc==SQLITE4_OK && db->bFastInsertOp ){
    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
    pHdr->nSubPg--;
  }
  return rc;
}

/*
** Allocate and zero an overflow page.
*/
static int btAllocateAndZero(bt_db *db, BtPage **ppPg){
  BtPage *pPg = 0;                /* Allocated page handle */
  int rc;                         /* Return code */

  rc = sqlite4BtPageAllocate(db->pPager, &pPg);
  if( rc==SQLITE4_OK ){
    const int pgsz = sqlite4BtPagerPagesize(db->pPager);

  return rc;
}

typedef struct BalanceCtx BalanceCtx;
struct BalanceCtx {
  int pgsz;                       /* Database page size */
  int bLeaf;                      /* True if we are rebalancing leaf data */
  BtCursor *pCsr;                 /* Cursor identifying where to insert pKV */
  int nKV;                        /* Number of KV pairs */
  KeyValue *apKV;                 /* New KV pairs being inserted */

  /* Populated by btGatherSiblings */
  int nIn;                        /* Number of sibling pages */
  BtPage *apPg[5];                /* Array of sibling pages */

  u8 *apOut[5];                   /* Buffers to assemble output in */
  KeyValue aPCell[5];             /* Cells to push into the parent page */
  u8 *pTmp;                       /* Space for apCell[x].pKey if required */
  int iTmp;                       /* Offset to free space within pTmp */
};

static int btGatherSiblings(BalanceCtx *p){
  BtCursor *pCsr = p->pCsr;
  bt_db * const pDb = pCsr->base.pDb; 
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);

  int rc = SQLITE4_OK;
  int nCell;                      /* Number of cells in parent page */
  u8 *aParent;                    /* Buffer of parent page */
  int iChild;                     /* Index of child page within parent */
  int nSib;                       /* Number of siblings */

    }
  }

  return rc;
}

/* Called recursively by btBalance(). todo: Fix this! */
static int btInsertAndBalance(BtCursor *, int, KeyValue *);
static int btDeleteFromPage(BtCursor *, int);
static int btBalanceIfUnderfull(BtCursor *pCsr);

static int btBalanceMeasure(
  BalanceCtx *p,                  /* Description of balance operation */
  int iCell,                      /* Cell number in this iteration */
  u8 *pCell, int nByte,           /* Binary cell */
  KeyValue *pKV                   /* Key-value cell */
){

  return SQLITE4_OK;
}

static int btBalanceVisitCells(
  BalanceCtx *p,
  int (*xVisit)(BalanceCtx*, int, u8*, int, KeyValue*)
){
  const int pgsz = sqlite4BtPagerPagesize(p->pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;            /* Return code */
  int iPg;                        /* Current page in apPg[] */
  int iCall = 0;
  int i;                          /* Used to iterate through KV pairs */

  BtPage *pIns = p->pCsr->apPage[p->pCsr->nPg-1];
  int iIns = p->pCsr->aiCell[p->pCsr->nPg-1];

    pKV->pK = aRight;
    pKV->nK = i + 1;
    assert( pKV->nK<=nRight );
  }
}

int btBalance(
  BtCursor *pCsr,                 /* Cursor pointed to page to rebalance */
  int bLeaf,                      /* True if rebalancing leaf pages */
  int nKV,                        /* Number of entries in apKV[] array */
  KeyValue *apKV                  /* Extra entries to add while rebalancing */
){
  bt_db * const pDb = pCsr->base.pDb; 
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  const int nSpacePerPage = (pgsz - 1 - 6 - (!bLeaf)*4);

  int iPg;                        /* Used to iterate through pages */
  int iCell;                      /* Used to iterate through cells */

  int anByteOut[5];               /* Bytes of content on each output page */

    u8 *aRightSibling = sqlite4BtPageData(ctx.apPg[ctx.nIn-1]);
    memcpy(&(ctx.apOut[ctx.nOut-1])[1], &aRightSibling[1], 4);
  }

  /* Clobber the old pages with the new buffers */
  for(iPg=0; iPg<ctx.nOut; iPg++){
    if( iPg>=ctx.nIn ){
      rc = btAllocateNonOverflow(pDb, &ctx.apPg[iPg]);
      if( rc!=SQLITE4_OK ) goto rebalance_out;
    }
    btSetBuffer(pDb, ctx.apPg[iPg], ctx.apOut[iPg]);
    ctx.apOut[iPg] = 0;
  }
  for(iPg=ctx.nOut; iPg<ctx.nIn; iPg++){
    rc = btTrimNonOverflow(pDb, ctx.apPg[iPg]);
    ctx.apPg[iPg] = 0;
    if( rc!=SQLITE4_OK ) goto rebalance_out;
  }

#ifdef BT_STDERR_DEBUG
  {
    int iDbg;

    sqlite4BtPageRelease(ctx.apPg[iPg]);
  }
  btFreeBuffer(pDb, ctx.pTmp);
  sqlite4_free(pDb->pEnv, ctx.anCellSz);
  return rc;
}

static int btExtendTree(BtCursor *pCsr){
  bt_db * const pDb = pCsr->base.pDb;
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;                         /* Return code */
  BtPage *pNew;                   /* New (and only) child of root page */
  BtPage *pRoot = pCsr->apPage[0];

  assert( pCsr->nPg==1 );

  rc = sqlite4BtPageWrite(pRoot);
  if( rc==SQLITE4_OK ){
    rc = btAllocateNonOverflow(pDb, &pNew);
  }
  if( rc==SQLITE4_OK ){
    u8 *aRoot = sqlite4BtPageData(pRoot);
    u8 *aData = sqlite4BtPageData(pNew);

    memcpy(aData, aRoot, pgsz);
    aRoot[0] = BT_PGFLAGS_INTERNAL;

**
**     * nKV entries are inserted in their place.
**
** The tree balancing routine is called if this causes the page to
** become either overfull or to contain no entries at all.
*/
static int btInsertAndBalance(
  BtCursor *pCsr,                 /* Cursor identifying page to modify */
  int nKV,                        /* Number of entries in apKV */
  KeyValue *apKV                  /* New cells to insert into the page */
){
  int rc = SQLITE4_OK;
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  u8 *aData;                      /* Page buffer */
  int nCell;                      /* Number of cells on this page already */
  int nFree;                      /* Contiguous free space on this page */
  int nReq = 0;                   /* Space required for type (a) cells */
  int iCell;                      /* Position to insert new key */
  int iWrite;                     /* Byte offset at which to write new cell */
  int i;

    iWrite = (bLeaf ? 1 : 5);
    nFree = pgsz - iWrite - 6;
  }else{
    if( btFreeContiguous(aData, pgsz)<nReq && btFreeSpace(aData, pgsz)>=nReq ){
      /* Special case - the new entry will not fit on the page at present
      ** but would if the page were defragmented. So defragment it before
      ** continuing.  */
      rc = btDefragmentPage(pCsr->base.pDb, pLeaf);
      aData = sqlite4BtPageData(pLeaf);
    }

    iWrite = btFreeOffset(aData, pgsz);
    nFree = btFreeContiguous(aData, pgsz);
  }

      rc = btBalance(pCsr, bLeaf, nKV, apKV);
    }
  }

  return rc;
}

static int btDeleteFromPage(BtCursor *pCsr, int nDel){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;            /* Return code */
  BtPage *pPg;                    /* Page to delete entries from */

  pPg = pCsr->apPage[pCsr->nPg-1];
  rc = sqlite4BtPageWrite(pPg);
  if( rc==SQLITE4_OK ){
    int i;                        /* Used to iterate through cells to delete */

    /* Increase total free space */
    btPutU16(&aData[pgsz-4], btFreeSpace(aData, pgsz) + nFreed);
  }
  
  return rc;
}

static int btBalanceIfUnderfull(BtCursor *pCsr){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int rc = SQLITE4_OK;
  int iPg = pCsr->nPg-1;
  BtPage *pPg = pCsr->apPage[iPg];
  u8 *aData = sqlite4BtPageData(pPg);
  int nCell = btCellCount(aData, pgsz);
  int nFree = btFreeSpace(aData, pgsz);
  int bLeaf = (0==(btFlags(aData) & BT_PGFLAGS_INTERNAL));

  if( iPg==0 ){
    /* Root page. If it contains no cells at all and is not already
    ** a leaf, shorten the tree by one here by copying the contents 
    ** of the only child into the root. */
    if( nCell==0 && bLeaf==0 ){
      BtPager *pPager = pCsr->base.pDb->pPager;
      u32 pgno = btChildPgno(aData, pgsz, 0);
      BtPage *pChild;

      rc = sqlite4BtPageWrite(pPg);
      if( rc==SQLITE4_OK ){
        rc = sqlite4BtPageGet(pPager, pgno, &pChild);
      }
      if( rc==SQLITE4_OK ){
        u8 *a = sqlite4BtPageData(pChild);
        memcpy(aData, a, pgsz);
        rc = btTrimNonOverflow(pCsr->base.pDb, pChild);
      }
    }
  }else if( nCell==0 || (nFree>(2*pgsz/3) && bLeaf==0) ){
    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 btReplace(
  bt_db *db,                      /* Database handle */
  u32 iRoot,                      /* Root page of b-tree to update */
  const void *pK, int nK,         /* Key to insert */
  const void *pV, int nV          /* Value to insert. (nV<0) -> delete */
){
  int rc;                         /* Return code */
  BtCursor csr;                  /* Cursor object to seek to insert point */

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


  ** stored on.  */

  btCsrSetup(db, iRoot, &csr);
  rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, BT_CSRSEEK_UPDATE);


  if( rc==SQLITE4_OK ){
    /* The cursor currently points to an entry with key pK/nK. This call
    ** should therefore replace that entry. So delete it and then re-seek
    ** the cursor.  */
    rc = sqlite4BtDelete(&csr.base);

    if( rc==SQLITE4_OK && nV>=0 ){
      rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, BT_CSRSEEK_UPDATE);
      if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT);
    }
  }

      rc = btInsertAndBalance(&csr, 1, &kv);
    }
    if( kv.eType==KV_CELL ){
      sqlite4_free(db->pEnv, (void*)kv.pV);
    }
  }
  btCsrReset(&csr, 1);

  return rc;
}

static int btAllocateNewRoot(bt_db *db, u32 *piNew){
  u32 iNew = 0;
  BtPage *pPg;
  int rc;

  rc = btAllocateNonOverflow(db, &pPg);
  if( rc==SQLITE4_OK ){
    iNew = sqlite4BtPagePgno(pPg);
    sqlite4BtPageRelease(pPg);
  }

  *piNew = iNew;
  return rc;
}

static int btFastInsertMaxLevel(
  bt_db *db, 
  BtDbHdr *pHdr, 
  u32 *piLevel
){
  int rc;
  BtCursor csr;

  btCsrSetup(db, pHdr->iMRoot, &csr);
  rc = btCsrEnd(&csr, 1);
  assert( rc!=SQLITE4_INEXACT );
  if( rc==SQLITE4_OK ){
    u8 *aK; int nK;
    rc = sqlite4BtCsrKey(&csr.base, (const void**)&aK, &nK);
    if( rc==SQLITE4_OK ){
      *piLevel = btGetU32(&aK[0]);
    }
  }else if( rc==SQLITE4_NOTFOUND ){
    rc = SQLITE4_OK;
    *piLevel = 0;
  }
  btCsrReset(&csr, 1);

  return rc;
}

static int btFastInsertRoot(
  bt_db *db, 
  BtDbHdr *pHdr, 
  u32 *piRoot
){
  int rc = SQLITE4_OK;
  u32 iSubRoot = 0;

  if( pHdr->iMRoot==0 ){
    rc = btAllocateNewRoot(db, &pHdr->iMRoot);
  }
  iSubRoot = pHdr->iSubRoot;

  /* If the current writable sub-tree is full, start a new one. */
  if( pHdr->nSubPg >= (BT_DEFAULT_BLKSZ / pHdr->pgsz) ){
    iSubRoot = 0;
  }

  /* If no writable sub-tree has been discovered, create one now. */
  if( iSubRoot==0 ){
    u32 iMaxLevel = 0;

    u8 aKey[4];
    u8 aVal[8];

    if( rc==SQLITE4_OK ){
      rc = btFastInsertMaxLevel(db, pHdr, &iMaxLevel);
    }
    if( rc==SQLITE4_OK ){
      rc = btAllocateNewRoot(db, &iSubRoot);
    }
    if( rc==SQLITE4_OK ){
      pHdr->iSubRoot = iSubRoot;
      pHdr->nSubPg = 0;

      btPutU32(aKey, iMaxLevel+1);
      btPutU32(&aVal[0], iSubRoot);
      btPutU32(&aVal[4], 1);
      rc = btReplace(db, pHdr->iMRoot, aKey, 4, aVal, 8);
    }
  }

  *piRoot = iSubRoot;
  return rc;
}

/*
** Insert a new key/value pair or replace an existing one.
**
** This function may modify either the b-tree or fast-insert-tree, depending
** on whether or not the db->bFastInsertOp flag is set.
*/
int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
  int rc = SQLITE4_OK;

  /* Debugging output. */
  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;
    if( db->bFastInsertOp ){
      rc = btFastInsertRoot(db, pHdr, &iRoot);
    }else{
      iRoot = pHdr->iRoot;
    }
    if( rc==SQLITE4_OK ){
      rc = btReplace(db, iRoot, pK, nK, pV, nV);
    }
  }

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


/*
** Delete the entry that the cursor currently points to.
*/
int sqlite4BtDelete(bt_cursor *pBase){
  int rc;

  if( pBase->eType==CSR_TYPE_BT ){
    BtCursor *pCsr = (BtCursor*)pBase;

    rc = btCsrReseek(pCsr);
    if( rc==SQLITE4_OK ){
      rc = btSaveAllCursor(pBase->pDb, pCsr);
    }
    if( rc==SQLITE4_OK ){
      rc = btOverflowDelete(pCsr);
    }
    if( rc==SQLITE4_OK ){
      rc =  btDeleteFromPage(pCsr, 1);
    }
    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);
}

  /* assert( p->iTransactionLevel>=1 && p->btl.pFd ); */
  return (int)p->pHdr->pgsz;
}

/* 
** Query for the root page number. Requires an open read transaction.
*/
BtDbHdr *sqlite4BtPagerDbhdr(BtPager *p){

  return p->pHdr;
}

/*
** Request a reference to page pgno of the database.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */

** or SQLITE4_OK otherwise.
*/
int sqlite4BtPagerHdrdump(BtPager *pPager, sqlite4_buffer *pBuf){
  BtDbHdr *pHdr = pPager->pHdr;
  int rc = SQLITE4_OK;

  sqlite4BtBufAppendf(pBuf, 
      "pgsz=%d nPg=%d"
      " iRoot=%d iMRoot=%d iSRoot=%d"
      " iCookie=%d iFreePg=%d iFreeBlk=%d",
      pHdr->pgsz, pHdr->nPg, pHdr->iRoot, pHdr->iMRoot, pHdr->iSRoot,
      pHdr->iCookie, pHdr->iFreePg, pHdr->iFreeBlk
  );

  return rc;
}

#ifndef NDEBUG
int sqlite4BtPagerRefcount(BtPager *p){
  return p->nTotalRef;
}
#endif