SQLite4  Check-in [18ae7f9855]

  return iRet;
}
/*
** End of integer query implementations.
*************************************************************************/


static int bt_open(sqlite4_env *pEnv, const char *zFile, sqlite4 **pDb){
  char *zUri = sqlite3_mprintf("file:%s?kv=bt", zFile);
  int rc = sqlite4_open(pEnv, zUri, pDb);
  sqlite3_free(zUri);
  return rc;
}

static int do_insert1_test4(
  const char *zFile,
  int nRow,                       /* Number of rows to insert in total */
  int nRowPerTrans,               /* Number of rows per transaction */
  int nIdx,                       /* Number of aux indexes (aside from PK) */
  int iSync                       /* PRAGMA synchronous value (0, 1 or 2) */
){
  char *zCreateTbl;               /* Create table statement */
  char *zInsert;                  /* INSERT statement */
  sqlite4_stmt *pInsert;          /* Compiled INSERT statement */
  sqlite4 *db = 0;                /* Database handle */
  int i;                          /* Counter to count nRow rows */
  int nMs;                        /* Test time in ms */

  lsm_db *pLsm;

  if( zFile==0 ) zFile = SQLITE4_DB_FILE;
  unlink_db(zFile);
  EXPLODE(  bt_open(0, zFile, &db)  );
  sqlite4_kvstore_control(db, "main", SQLITE4_KVCTRL_LSM_HANDLE, &pLsm);
  i = iSync;
  lsm_config(pLsm, LSM_CONFIG_SAFETY, &i);
  assert( i==iSync );

  install_rblob_function4(db);

  sqlite4_stmt *pSelect = 0;
  char *zSelect;
  sqlite4 *db;
  int i;
  int nTblRow;

  if( zFile==0 ) zFile = SQLITE4_DB_FILE;
  EXPLODE( bt_open(0, zFile, &db) );
  install_rblob_function4(db);

  nTblRow = integer_query4(db, "SELECT count(*) FROM t1");

  /* Create the db schema and prepare the INSERT statement */
  zSelect = create_select_sql(iIdx);
  EXPLODE(  sqlite4_prepare(db, zSelect, -1, &pSelect, 0)  );

      }
    }
    *pp = (SqlDatabase *)p;
  }else{
    SqlDatabase4 *p = sqlite4_malloc(0, sizeof(SqlDatabase4));
    memset(p, 0, sizeof(SqlDatabase4));
    p->x.iDb = 4;
    rc = bt_open(0, zFile, &p->db);
    if( rc!=SQLITE4_OK ){
      sqlite4_free(0, p);
      p = 0;
    }else{
      install_rint_function4(p->db);
      if( zConfig ) {
        rc = sqlite4_exec(p->db, zConfig, 0, 0);

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

/* Default cache size in pages */
#define BT_DEFAULT_CACHESZ 1000

/*
** This structure is the in-memory representation of all data stored in
** the database header at the start of the db file.
**
** pgsz, blksz:
**   Byte offset 0 of the database file is the first byte of both page 1

  u32 *aLog = pLog->snapshot.aLog;
  int iSafeIdx = sqlite4BtLogFrameToIdx(aLog, iSafe);

  /* Loop through regions (c), (b) and (a) of the log file. In that order. */
  for(i=2; i>=0 && rc==SQLITE4_NOTFOUND; i--){
    u32 iLo = pLog->snapshot.aLog[i*2+0];
    if( iLo ){
      u32 iHi = pLog->snapshot.aLog[i*2+1];
      int iSide;
      int iHash;
      int iHashLast;

      iHash = btLogFrameHash(pLog, iHi);
      iHashLast = btLogFrameHash(pLog, iLo);
      iSide = (pLog->snapshot.iHashSide + (i==0)) % 2;

      for( ; rc==SQLITE4_NOTFOUND && iHash>=iHashLast; iHash--){
        rc = btLogHashSearch(pLog, iSide, iHash, iHi, pgno, &iFrame);
        if( rc==SQLITE4_OK ){
          if( iFrame<iLo || iFrame>iHi ){
            rc = SQLITE4_NOTFOUND;
          }else{
            assert( sqlite4BtLogFrameToIdx(aLog, iFrame)>=0 );
            if( iSafeIdx>=0 && sqlite4BtLogFrameToIdx(aLog, iFrame)>iSafeIdx ){
              return SQLITE4_NOTFOUND;
            }
          }
        }
      }
    }
  }

  btDebugLogSearch(pLog->pLock, pgno, iSafe, (rc==SQLITE4_OK ? iFrame : 0));

** If the log does not contain any version of page pgno, SQLITE4_NOTFOUND
** is returned and the contents of buffer aData[] are not modified.
**
** If any other error occurs, an SQLite4 error code is returned. The final
** state of buffer aData[] is undefined in this case.
*/
int sqlite4BtLogRead(BtLog *pLog, u32 pgno, u8 *aData){
  if( pLog->snapshot.aLog[4]==0 ){
    assert( pLog->snapshot.aLog[0]==0 && pLog->snapshot.aLog[2]==0 );
    return SQLITE4_NOTFOUND;
  }
  return btLogRead(pLog, pgno, aData, 0);
}

static int btLogZeroHash(BtLog *pLog, int iHash){
  int iSide = pLog->snapshot.iHashSide;
  ht_slot *aHash;
  u32 *aPgno;

*************************************************************************
**
*/

#include "btInt.h"
#include <string.h>
#include <assert.h>
#include <stddef.h>

#define BT_MAX_DEPTH 32           /* Maximum possible depth of tree */
#define BT_MAX_DIRECT_OVERFLOW 8  /* Maximum direct overflow pages per cell */

/* Maximum size of a key-prefix stored on an internal node. Parts of the
** code in this file assume that this value can be encoded as a single
** byte SQLite4 varint.  */
#define BT_MAX_INTERNAL_KEY 200   /* Maximum bytes of key on internal node */

/*
** 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_PGFLAGS_METATREE  0x02  /* True for a meta-tree page */
#define BT_PGFLAGS_SCHEDULE  0x04  /* True for a schedule-tree page */
#define BT_PGFLAGS_LARGEKEYS 0x08  /* True if keys larger than 200 bytes */

/*
** Maximum depth of fast-insert sub-trees.
*/
#define MAX_SUBTREE_DEPTH 8

/* #define BT_STDERR_DEBUG 1 */

typedef struct BtCursor BtCursor;
typedef struct FiCursor FiCursor;
typedef struct FiSubCursor FiSubCursor;

struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  sqlite4_mm *pMM;                /* Memory allocator for pEnv */
  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 */

  BtCursor *pFreeCsr;
};

/*
** Overflow buffer is valid if nKey!=0.
*/
typedef struct BtOvfl BtOvfl;
struct BtOvfl {

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


  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 *pNextFree;            /* Next in list of free BtCursor structures */

  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */
};

/*
** Database f-tree cursor handle.
*/
struct FiSubCursor {
  u8 aPrefix[8];                  /* Meta-tree key prefix for this age/level */

  a[0] = (u8)((i>>24) & 0xFF);
  a[1] = (u8)((i>>16) & 0xFF);
  a[2] = (u8)((i>>8) & 0xFF);
  a[3] = (u8)((i>>0) & 0xFF);
}
#define btPutU32(x,y) sqlite4BtPutU32(x,y)

struct FakePage { u8 *aData; };
#define btPageData(pPg) (((struct FakePage*)(pPg))->aData)

/*
** Allocate a new database handle.
*/
int sqlite4BtNew(sqlite4_env *pEnv, int nExtra, bt_db **ppDb){
  static const int MIN_MERGE = 2;
  static const int SCHEDULE_ALLOC = 4;

/*
** Close an existing database handle. Once this function has been 
** called, the handle may not be used for any purpose.
*/
int sqlite4BtClose(bt_db *db){
  if( db ){
    BtCursor *pCsr;
    BtCursor *pNext;
    for(pCsr=db->pFreeCsr; pCsr; pCsr=pNext){
      pNext = pCsr->pNextFree;
      sqlite4_free(db->pEnv, pCsr);
    }
    sqlite4BtPagerClose(db->pPager);
  }
  return SQLITE4_OK;
}

/*
** Return a pointer to the nExtra bytes of space allocated along with 
** the database handle. 
*/
void *sqlite4BtExtra(bt_db *db){
  return (void*)&db[1];
}

int sqlite4BtOpen(bt_db *db, const char *zFilename){
  int rc;
  sqlite4_env_config(db->pEnv, SQLITE4_ENVCONFIG_GETMM, &db->pMM);
  rc = sqlite4BtPagerOpen(db->pPager, zFilename);
  return rc;
}

int sqlite4BtBegin(bt_db *db, int iLevel){
  int rc;
  rc = sqlite4BtPagerBegin(db->pPager, iLevel);

}

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

static void btCsrSetup(bt_db *db, u32 iRoot, BtCursor *pCsr){
  memset(pCsr, 0, offsetof(BtCursor, aiCell));
  pCsr->base.flags = CSR_TYPE_BT;
  pCsr->base.pExtra = (void*)&pCsr[1];
  pCsr->base.pDb = db;
  pCsr->iRoot = iRoot;
  pCsr->ovfl.buf.pMM = db->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 );

      pCsr->base.pExtra = (void*)&pCsr[1];
      pCsr->base.pDb = db;
      pRet = (bt_cursor*)pCsr;
    }

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


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


 csr_open_out:
  *ppCsr = pRet;
  btCheckPageRefs(db);
  db->bFastInsertOp = 0;
  return rc;
}

static void btCsrReleaseAll(BtCursor *pCsr){
  int i;

    for(pp=&pDb->pAllCsr; *pp!=pCsr; pp=&(*pp)->pNextCsr);
    *pp = pCsr->pNextCsr;

    if( IsBtCsr(pCsr) ){
      /* A regular b-tree cursor */
      BtCursor *p = (BtCursor*)pCsr;
      btCsrReset(p, 1);
      p->pNextFree = pDb->pFreeCsr;
      pDb->pFreeCsr = p;
    }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;
}

/*
** Set pCsr->apPage[pCsr->nPg] to a reference to database page pgno.
*/
static int btCsrDescend(BtCursor *pCsr, u32 pgno, BtPage **ppPg){
  int rc;
  if( pCsr->nPg>=BT_MAX_DEPTH ){
    rc = btErrorBkpt(SQLITE4_CORRUPT);
  }else{

    assert( pCsr->nPg>=0 );
    rc = sqlite4BtPageGet(pCsr->base.pDb->pPager, pgno, ppPg);
    if( rc==SQLITE4_OK ){
      assert( *ppPg );
      pCsr->apPage[pCsr->nPg] = *ppPg;
      pCsr->nPg++;
    }
  }
  return rc;
}

/*

      for(i=0; i<=btCellCount(aData, nData); i++){
        BtPage *pChild;
        u8 *aChild;
        u32 child;

        child = btChildPgno(aData, nData, i);
        sqlite4BtPageGet(pPager, child, &pChild);
        aChild = btPageData(pChild);
        btPageToAscii(child, bAscii, pPager, aChild, nData, pBuf);
        sqlite4BtPageRelease(pChild);
      }
    }
  }
  sqlite4BtBufAppendf(pBuf, "\n");
}

static int btFreelistToAscii(bt_db *db, u32 iFirst, sqlite4_buffer *pBuf){
  int rc = SQLITE4_OK;
  u32 iTrunk = iFirst;
  while( iTrunk && rc==SQLITE4_OK ){
    BtPage *pPg = 0;
    rc = sqlite4BtPageGet(db->pPager, iTrunk, &pPg);
    if( rc==SQLITE4_OK ){
      u8 *aData = btPageData(pPg);
      u32 nFree = btGetU32(aData);
      u32 iNext = btGetU32(&aData[4]);
      int i;

      sqlite4BtBufAppendf(pBuf, "iTrunk=%d ", (int)iTrunk);
      sqlite4BtBufAppendf(pBuf, "nFree=%d iNext=%d (", (int)nFree, (int)iNext);
      for(i=0; i<(int)nFree; i++){

int printPgdataToStderr(u32 pgno, u8 *aData, int nData){
  printPage(stderr, pgno, aData, nData);
  return 0;
}

int printPgToStderr(BtPage *pPg){
  printPage(stderr, sqlite4BtPagePgno(pPg), btPageData(pPg), 1024);
  return 0;
}

static void btPrintMetaTree(BtPager *pPager, int bAscii, BtDbHdr *pHdr){
  u8 *aData;
  int nData;
  sqlite4_buffer buf;
  BtPage *pPg = 0;

  sqlite4BtPageGet(pPager, pHdr->iMRoot, &pPg);
  aData = btPageData(pPg);
  nData = pHdr->pgsz;
  sqlite4_buffer_init(&buf, 0);
  btPageToAscii(pHdr->iMRoot, bAscii, pPager, aData, nData, &buf);
  sqlite4_buffer_append(&buf, "", 1);

  fprintf(stderr, "%s", (char*)buf.p);
  sqlite4_buffer_clear(&buf);

  int nCsrKey;
  int nCmp;
  int nAscend = 0;
  int rc = SQLITE4_OK;
  int res;

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

    u8 *aData = btPageData(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 ){
        BtPage *pPg;
        u8 *aData = btPageData(pCsr->apPage[pCsr->nPg-1]);
        u32 pgno = btChildPgno(aData, pgsz, iCell);
        nAscend++;
        rc = btCsrDescend(pCsr, pgno, &pPg);
        if( rc!=SQLITE4_OK ) break;
        aData = btPageData(pPg);
        pCsr->aiCell[pCsr->nPg-1] = 0;
        if( (btFlags(aData) & BT_PGFLAGS_INTERNAL)==0 ) break;
        iCell = 0;
      }
      rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pCsrKey, &nCsrKey);
    }
  }

  }

 keycompare_done:
  btCsrAscend(pCsr, nAscend);
  *piRes = res;
  return rc;
}

/*
** Return an integer representing the result of (K1 - K2).
*/
static int btKeyCompare(
  const void *pKey1, int nKey1, 
  const void *pKey2, int nKey2
){
  int nCmp = MIN(nKey1, nKey2);
  int res;

  res = memcmp(pKey1, pKey2, nCmp);
  if( res==0 ){
    res = nKey1 - nKey2;
  }
  return res;
}


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

static int btCsrSeek(
  BtCursor *pCsr,                 /* Cursor object to seek */

  /* 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 */
    BtPage *pPg;
    rc = btCsrDescend(pCsr, pgno, &pPg);
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int iHi;                    /* pK/nK is <= than cell iHi */
      int iLo;                    /* pK/nK is > than cell (iLo-1) */
      int res;                    /* Result of comparison */

      u8 *aData = btPageData(pPg);
      u16 *aCellPtr = btCellPtrFind(aData, pgsz, 0);
      int bLeaf = ((btFlags(aData) & BT_PGFLAGS_INTERNAL)==0);

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

      if( btFlags(aData) & BT_PGFLAGS_LARGEKEYS ){
        while( iHi>iLo ){
          int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
          u8 *pCell = &aData[btGetU16(aCellPtr - iTst)];
          int n = *pCell;

          pCsr->aiCell[pCsr->nPg-1] = iTst;
          rc = btCellKeyCompare(pCsr, bLeaf, 0, pK, nK, &res);
          if( rc!=SQLITE4_OK ) break;

          if( res<0 ){
            /* Cell iTst is SMALLER than pK/nK */
            iLo = iTst+1;
          }else{
            /* Cell iTst is LARGER than (or equal to) pK/nK */
            iHi = iTst;
            if( res==0 ) break;
          }
        }
      }else{
        while( iHi>iLo ){
          int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
          u8 *pCell = &aData[btGetU16(aCellPtr - iTst)];
          int n = *pCell;
          res = memcmp(&pCell[1], pK, MIN(nK, n));

          if( res<0 || (res==0 && (res = n - nK)<0) ){
            /* Cell iTst is SMALLER than pK/nK */
            iLo = iTst+1;
          }else{
            /* Cell iTst is LARGER than (or equal to) pK/nK */
            iHi = iTst;
            if( res==0 ) break;
          }
        }
      }
      if( rc!=SQLITE4_OK ) break;


      iHi += (nCell>0 && bLeaf==0 && res==0);
      pCsr->aiCell[pCsr->nPg-1] = iHi;
      if( bLeaf==0 ){
        if( iHi==nCell ) pgno = btGetU32(&aData[1]);
        else{
          u8 *pCell = btCellFind(aData, pgsz, iHi);
          pgno = btGetU32(&pCell[1 + (int)*pCell]);
        }
      }else{
        pgno = 0;

        if( nCell==0 ){
          rc = SQLITE4_NOTFOUND;
        }else if( res!=0 ){
          if( eSeek==BT_SEEK_EQ ){

  pCsr->bSkipPrev = pCsr->bSkipNext = 0;

  while( rc==SQLITE4_OK ){
    int iPg = pCsr->nPg-1;
    int iCell = pCsr->aiCell[iPg];

    if( bNext ){
      u8 *aData = (u8*)btPageData(pCsr->apPage[iPg]);
      int nCell = btCellCount(aData, pgsz);
      assert( bRequireDescent==0 || bRequireDescent==1 );
      if( iCell<(nCell+bRequireDescent-1) ){
        pCsr->aiCell[iPg]++;
        break;
      }
    }else{
      if( pCsr->aiCell[iPg]>0 ){
        pCsr->aiCell[iPg]--;
        break;
      }
    }

    rc = btCsrAscend(pCsr, 1);
    bRequireDescent = 1;
  }

  if( bRequireDescent && rc==SQLITE4_OK ){
    u32 pgno;                   /* Child page number */
    u8 *aData = (u8*)btPageData(pCsr->apPage[pCsr->nPg-1]);

    pgno = btChildPgno(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);

    while( 1 ){
      BtPage *pPg;
      rc = btCsrDescend(pCsr, pgno, &pPg);
      if( rc!=SQLITE4_OK ){
        break;
      }else{
        int nCell;
        aData = (u8*)btPageData(pPg);
        nCell = btCellCount(aData, pgsz);
        if( btFlags(aData) & BT_PGFLAGS_INTERNAL ){
          pCsr->aiCell[pCsr->nPg-1] = (bNext ? 0 : nCell);
          pgno = btChildPgno(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);
        }else{
          pCsr->aiCell[pCsr->nPg-1] = (bNext ? 0 : nCell-1);
          break;

  /* 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 */
    BtPage *pPg;
    rc = btCsrDescend(pCsr, pgno, &pPg);
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)btPageData(pPg);

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

static int btCsrIsDelete(BtCursor *pCsr){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  int bRet;                       /* Return value */
  u8 *aData;
  u8 *pCell;
  int n;

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

  pCell += sqlite4BtVarintGet32(pCell, &n);
  if( n==0 ){
    /* Type (c) cell */
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pCell += n;

static int fiCsrIsDelete(FiCursor *pCsr){
  int res = 0;
  if( (pCsr->base.flags & CSR_VISIT_DEL)==0 ){
    BtCursor *p = &pCsr->aSub[pCsr->iBt].csr;
    res = btCsrIsDelete(p);
  }

















  return res;
}

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

  ** it has a depth of zero.  */
  for(iPg=0; rc==SQLITE4_OK && iPg<(nDirect+(nDepth==0)) && iOut<nOut; iPg++){
    u32 pgno = btGetU32(&pOvfl[1+iPg*4]);
    BtPage *pPg = 0;
    rc = sqlite4BtPageGet(db->pPager, pgno, &pPg);
    if( rc==SQLITE4_OK ){
      int nCopy = MIN(nOut-iOut, pgsz);
      u8 *a = btPageData(pPg);
      memcpy(&aOut[iOut], a, nCopy);
      sqlite4BtPageRelease(pPg);
      iOut += nCopy;
    }
  }

  /* Read from the overflow tree, if it was not read by the block above. */

    /* Initialize the apHier[] array. */
    pgno = btGetU32(&pOvfl[1+nDirect*4]);
    for(i=0; i<nDepth && rc==SQLITE4_OK; i++){
      u8 *a;
      rc = sqlite4BtPageGet(db->pPager, pgno, &apHier[i].pPg);
      if( rc==SQLITE4_OK ){
        a = btPageData(apHier[i].pPg);
        pgno = btGetU32(a);
      }
    }

    /* Loop runs once for each leaf page we read from. */
    while( iOut<nOut ){
      u8 *a;                      /* Data associated with some page */
      BtPage *pLeaf;              /* Leaf page */
      int nCopy;                  /* Bytes of data to read from leaf page */

      int iLvl;

      nCopy =  MIN(nOut-iOut, pgsz);
      assert( nCopy>0 );

      /* Read data from the current leaf page */
      rc = sqlite4BtPageGet(db->pPager, pgno, &pLeaf);
      if( rc!=SQLITE4_OK ) break;
      a = btPageData(pLeaf);
      memcpy(&aOut[iOut], a, nCopy);
      sqlite4BtPageRelease(pLeaf);
      iOut += nCopy;

      /* If all required data has been read, break out of the loop */
      if( iOut>=nOut ) break;

      for(iLvl=nDepth-1; iLvl>=0; iLvl--){
        if( apHier[iLvl].iCell<(nPgPtr-1) ) break;
      }
      if( iLvl<0 ) break; /* SQLITE4_CORRUPT? */
      apHier[iLvl].iCell++;

      for(; iLvl<nDepth && rc==SQLITE4_OK; iLvl++){
        a = btPageData(apHier[iLvl].pPg);
        pgno = btGetU32(&a[apHier[iLvl].iCell * 4]);
        if( iLvl<(nDepth-1) ){
          apHier[iLvl+1].iCell = 0;
          sqlite4BtPageRelease(apHier[iLvl+1].pPg);
          apHier[iLvl+1].pPg = 0;
          rc = sqlite4BtPageGet(db->pPager, pgno, &apHier[iLvl+1].pPg);
        }

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

  }else{
    const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
    u8 *aData;
    u8 *pCell;
    int nK;
    int iCell = pCsr->aiCell[pCsr->nPg-1];

    aData = btPageData(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);

  BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);

  assert( eSeek==BT_SEEK_LE || eSeek==BT_SEEK_EQ || eSeek==BT_SEEK_GE );
  assert( (pCsr->base.flags & CSR_VISIT_DEL)==0 || eSeek==BT_SEEK_GE );
  fiCsrReset(pCsr);

  if( pHdr->iMRoot ){
    u8 *pKey;
    FiLevelIter iter;

    /* Initialize the iterator used to skip through database levels */
    rc = fiLevelIterInit(db, &iter);
    if( rc!=SQLITE4_OK ) return rc;
    pKey = sqlite4_malloc(db->pEnv, nK+8);
    if( pKey==0 ) return SQLITE4_NOMEM;

    if( eSeek==BT_SEEK_EQ ){
      FiSubCursor *pSub;
      BtCursor *pM;

      pCsr->base.flags &= ~(CSR_NEXT_OK | CSR_PREV_OK);

      pSub = pCsr->aSub;
      pM = &pSub->mcsr;

      btCsrSetup(db, pHdr->iMRoot, pM);
      while( 0==fiLevelIterNext(&iter) ){

        fiFormatPrefix(pSub->aPrefix, iter.iAge, iter.iLvl);
        memcpy(pKey, pSub->aPrefix, sizeof(pSub->aPrefix));
        rc = btCsrSeek(pM, 0, pKey, nK+8, BT_SEEK_LE, BT_CSRSEEK_SEEK);

        if( rc==SQLITE4_INEXACT ){
          rc = fiSubCsrCheckPrefix(pSub);
        }

        if( rc==SQLITE4_NOTFOUND ){
          /* All keys in this level are greater than pK/nK. */

      /* This loop runs once for each sub-cursor */
      while( rc==SQLITE4_OK && 0==fiLevelIterNext(&iter) ){
        FiSubCursor *pSub = &pCsr->aSub[iter.iSub];
        BtCursor *pM = &pSub->mcsr;
        btCsrSetup(db, pHdr->iMRoot, pM);

        fiFormatPrefix(pSub->aPrefix, iter.iAge, iter.iLvl);
        memcpy(pKey, pSub->aPrefix, sizeof(pSub->aPrefix));

        rc = btCsrSeek(pM, 0, pKey, nK+8, BT_SEEK_LE, BT_CSRSEEK_SEEK);
        if( rc==SQLITE4_INEXACT ) rc = fiSubCsrCheckPrefix(pSub);
        if( rc==SQLITE4_NOTFOUND && eSeek==BT_SEEK_GE ){
          rc = btCsrSeek(pM, 0, pSub->aPrefix, sizeof(pSub->aPrefix), 
              BT_SEEK_GE, BT_CSRSEEK_SEEK
          );
          if( rc==SQLITE4_INEXACT ) rc = fiSubCsrCheckPrefix(pSub);
        }

        if( rc==SQLITE4_NOTFOUND ){
          /* No keys to visit in this level */
          assert( pSub->mcsr.nPg==0 );
          assert( pSub->csr.nPg==0 );

          }else if( bMatch==0 ){
            rc = (bHit ? SQLITE4_INEXACT : SQLITE4_NOTFOUND);
          }
        }
      }
    }

    sqlite4_free(db->pEnv, pKey);
    fiLevelIterCleanup(&iter);
  }

  return rc;
}

static int fiCsrEnd(FiCursor *pCsr, int bLast){

    const int nPgPtr = pgsz / 4;
    BtPage *pPg;
    u8 *aData;
    int i;

    rc = sqlite4BtPageGet(pPager, pgno, &pPg);
    if( rc!=SQLITE4_OK ) return rc;
    aData = btPageData(pPg);

    for(i=0; rc==SQLITE4_OK && i<nPgPtr; i++){
      u32 child = btGetU32(&aData[i*4]);
      if( child==0 ) break;
      rc = btOverflowTrimtree(pgsz, pPager, child, nDepth-1);
    }

  u8 *aData;
  u8 *pCell;
  u8 *pOvfl = 0;
  int iCell = pCsr->aiCell[pCsr->nPg-1];
  int n;
  int rc = SQLITE4_OK;
  
  aData = (u8*)btPageData(pCsr->apPage[pCsr->nPg-1]);
  assert( btCellCount(aData, pgsz)>iCell );
  pCell = btCellFind(aData, pgsz, iCell);
  pCell += sqlite4BtVarintGet32(pCell, &n);

  if( n==0 ){
    /* Type (c) cell */
    pCell += sqlite4BtVarintGet32(pCell, &n);

      /* 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*)btPageData(pCsr->apPage[pCsr->nPg-1]);
      pCell = btCellFind(aData, pgsz, iCell);
      pCell += sqlite4BtVarintGet32(pCell, &nK);
      if( nK>0 ){
        pCell += nK;
        pCell += sqlite4BtVarintGet32(pCell, &nV);
      }

  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  FiSubCursor *pSub;              /* Current sub-cursor */
  u8 *aData;                      /* Current page data */
  int iCell;

  assert( pCsr->iBt>=0 );
  pSub = &pCsr->aSub[pCsr->iBt];
  aData = btPageData(pSub->csr.apPage[pSub->csr.nPg-1]);
  iCell = pSub->csr.aiCell[pSub->csr.nPg-1];

  *ppCell = btCellFindSize(aData, pgsz, iCell, pnCell);
}

/*
** Return true if the cell that the cursor currently points to contains 
** pointers to one or more overflow pages. Or false otherwise.
*/
static int btCsrOverflow(BtCursor *pCsr){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
  u8 *aData;                      /* Current page data */
  int nKey;                       /* First varint in cell */
  int res;                       /* First varint in cell */

  aData = btPageData(pCsr->apPage[pCsr->nPg-1]);
  aData = btCellFind(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);

  aData += sqlite4BtVarintGet32(aData, &nKey);
  res = (nKey==0 || aData[nKey]==0);
  return res;
}

** Attach a buffer to an existing page object.
*/
static int btSetBuffer(bt_db *pDb, BtPage *pPg, u8 *aBuf){
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;
  rc = sqlite4BtPageWrite(pPg);
  if( rc==SQLITE4_OK ){
    u8 *aData = btPageData(pPg);
    memcpy(aData, aBuf, pgsz);
    sqlite4_free(pDb->pEnv, aBuf);
  }
  return rc;
}

/*

  int iWrite;                     /* Write next cell at this offset in aTmp[] */
  int i;                          /* Used to iterate through cells */
  int bLeaf;                      /* True if pPg is a leaf page */
  int nHdr;                       /* Bytes in header of this page */

  if( btNewBuffer(pDb, &aTmp) ) return SQLITE4_NOMEM;

  aData = btPageData(pPg);
  nCell = btCellCount(aData, pgsz);

  bLeaf = 0==(btFlags(aData) & BT_PGFLAGS_INTERNAL);
  nHdr = bLeaf ? 1 : 5;

  /* Set header bytes of new page */
  memcpy(aTmp, aData, nHdr);

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);
    memset(btPageData(pPg), 0, pgsz);
  }

  *ppPg = pPg;
  return rc;
}

static int btOverflowArrayPopulate(

  for(i=0; rc==SQLITE4_OK && i<nDepth; i++){
    u32 pgno;
    rc = btAllocateAndZero(db, &apHier[i].pPg);
    pgno = sqlite4BtPagePgno(apHier[i].pPg);
    if( i==0 ){
      btPutU32(&aOut[1 + BT_MAX_DIRECT_OVERFLOW*4], pgno);
    }else{
      u8 *a = btPageData(apHier[i-1].pPg);
      btPutU32(a, pgno);
      apHier[i-1].iCell++;
    }
  }

  for(iOvfl=0; rc==SQLITE4_OK && (n1<nBuf1 || n2<nBuf2); iOvfl++){
    int nCopy1, nCopy2;           /* Bytes to copy from pBuf1 and pBuf2 */
    u8 *aData;
    BtPage *pPg;
    u32 pgno;

    rc = sqlite4BtPageAllocate(db->pPager, &pPg);
    if( rc!=SQLITE4_OK ) break;
    aData = btPageData(pPg);
    pgno = sqlite4BtPagePgno(pPg);

    nCopy1 = MIN(pgsz, nBuf1 - n1);
    nCopy2 = MIN(pgsz - nCopy1, nBuf2 - n2);

    memcpy(aData, &pBuf1[n1], nCopy1); n1 += nCopy1;
    memcpy(&aData[nCopy1], &pBuf2[n2], nCopy2); n2 += nCopy2;
    rc = sqlite4BtPageRelease(pPg);
    if( rc!=SQLITE4_OK ) break;

    if( iOvfl<(BT_MAX_DIRECT_OVERFLOW+(nDepth==0)) ){
      btPutU32(&aOut[1 + iOvfl*4], pgno);
      nDirect++;
    }else{
      assert( nDepth>0 );
      for(i=nDepth-1; pgno && i>=0; i--){
        u8 *a = btPageData(apHier[i].pPg);
        if( apHier[i].iCell==nPgPtr ){
          BtPage *pNew = 0;
          rc = sqlite4BtPageRelease(apHier[i].pPg);
          if( rc==SQLITE4_OK ){
            rc = btAllocateAndZero(db, &pNew);
            if( rc==SQLITE4_OK ){
              u8 *a = btPageData(pNew);
              btPutU32(a, pgno);
              pgno = sqlite4BtPagePgno(pNew);
            }
          }

          if( rc!=SQLITE4_OK ){
            pgno = 0;

  u8 *aParent;                    /* Buffer of parent page */
  int iChild;                     /* Index of child page within parent */
  int nSib;                       /* Number of siblings */
  int iSib;                       /* Index of left-most sibling page */

  int i;

  aParent = btPageData(pCsr->apPage[pCsr->nPg-2]);
  iChild = pCsr->aiCell[pCsr->nPg-2];
  nCell = btCellCount(aParent, pgsz);

  if( nCell<2 ){
    nSib = nCell+1;
  }else{
    nSib = 3;

static int btSetChildPgno(bt_db *pDb, BtPage *pPg, int iChild, u32 pgno){
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;

  rc = sqlite4BtPageWrite(pPg);
  if( rc==SQLITE4_OK ){
    u8 *aData = btPageData(pPg);
    int nCell = btCellCount(aData, pgsz);
    if( iChild>=nCell ){
      btPutU32(&aData[1], pgno);
    }else{
      int nKey;
      u8 *pCell = btCellFind(aData, pgsz, iChild);
      pCell += sqlite4BtVarintGet32(pCell, &nKey);

  for(iPg=0; iPg<p->nIn && rc==SQLITE4_OK; iPg++){
    BtPage *pPg;                  /* Current page */
    u8 *aData;                    /* Page data */
    int nCell;                    /* Number of cells on page pPg */
    int iCell;                    /* Current cell in pPg */

    pPg = p->apPg[iPg];
    aData = btPageData(pPg);
    nCell = btCellCount(aData, pgsz);

    for(iCell=0; iCell<nCell && rc==SQLITE4_OK; iCell++){
      int nByte;
      u8 *pCell;

      if( pPg==pIns && iCell==iIns ){

    }

    /* If the siblings being balanced are not leaves, and the page just
    ** processed was not the right-most sibling, visit a cell from the
    ** parent page.  */
    if( p->bLeaf==0 && iPg<(p->nIn-1) && rc==SQLITE4_OK ){
      int iPar = p->pCsr->nPg-2;
      u8 *aParent = btPageData(p->pCsr->apPage[iPar]);
      u8 *pCell = btCellFind(aParent, pgsz, p->pCsr->aiCell[iPar] + iPg);
      KeyValue kv;
      btInternalCellToKeyValue(pCell, &kv);
      kv.pgno = btGetU32(&aData[1]);
      rc = xVisit(p, iCall++, 0, 0, &kv);
    }
  }

** set to the size of the prefix in bytes.
*/
static u8 *btKeyPrefix(const int pgsz, BtPage *pPg, int bLast, int *pnByte){
  u8 *p;
  int n;
  u8 *aData;

  aData = btPageData(pPg);
  p = btCellFind(aData, pgsz, bLast ? btCellCount(aData, pgsz)-1 : 0);
  p += sqlite4BtVarintGet32(p, &n);
  if( n==0 ) p += sqlite4BtVarintGet32(p, &n);

  *pnByte = n;
  return p;
}

**   * larger than all keys on pLeft, and 
**   * smaller than or equal to all keys on pRight.
*/
static void btPrefixKey(
    const int pgsz, BtPage *pLeft, BtPage *pRight, KeyValue *pKV
){
  int nMax;
  int nMaxPrefix = BT_MAX_INTERNAL_KEY;

  u8 *aLeft; int nLeft;
  u8 *aRight; int nRight;
  int i;

  aLeft = btKeyPrefix(pgsz, pLeft, 1, &nLeft);
  aRight = btKeyPrefix(pgsz, pRight, 0, &nRight);

  BalanceCtx ctx;
  memset(&ctx, 0, sizeof(ctx));
  ctx.pCsr = pCsr;
  ctx.nKV = nKV;
  ctx.apKV = apKV;
  ctx.pgsz = pgsz;
  ctx.bLeaf = bLeaf;
  ctx.flags = *(u8*)btPageData(pCsr->apPage[pCsr->nPg-1]);

  memset(anByteOut, 0, sizeof(anByteOut));

  /* Gather the sibling pages from which cells will be redistributed into
  ** the ctx.apPg[] array.  */
  assert( bLeaf==0 || bLeaf==1 );
  assert( pCsr->nPg>1 );
  rc = btGatherSiblings(&ctx);
  if( rc!=SQLITE4_OK ) goto rebalance_out;
  pPar = pCsr->apPage[pCsr->nPg-2];
  iSib = pCsr->aiCell[pCsr->nPg-2];

  /* Count the number of input cells. */
  ctx.nCell = nKV;
  for(iPg=0; iPg<ctx.nIn; iPg++){
    u8 *aData = btPageData(ctx.apPg[iPg]);
    ctx.nCell += btCellCount(aData, pgsz);
  }
  if( bLeaf==0 ) ctx.nCell += (ctx.nIn-1);
  assert( ctx.nCell>0 );

  /* Allocate and populate the anCellSz[] array */
  ctx.anCellSz = (int*)sqlite4_malloc(pDb->pEnv, sizeof(int)*ctx.nCell);

#ifdef BT_STDERR_DEBUG
  {
    int iDbg;
    fprintf(stderr, 
        "\nbtBalance(): bLeaf=%d nIn=%d anIn[] = ", ctx.bLeaf, ctx.nIn
    );
    for(iDbg=0; iDbg<ctx.nIn; iDbg++){
      u8 *aData = btPageData(ctx.apPg[iDbg]);
      fprintf(stderr, "%d ", btCellCount(aData, pgsz));
    }
    fprintf(stderr, " ->  nOut=%d anOut[] = ", ctx.nOut);
    for(iDbg=0; iDbg<ctx.nOut; iDbg++){
      fprintf(stderr, "%d ", ctx.anOut[iDbg]);
    }
    fprintf(stderr, "\n");

  /* Populate the new buffers with the new page images. */
  rc = btBalanceVisitCells(&ctx, btBalanceOutput);
  if( rc!=SQLITE4_OK ) goto rebalance_out;

  if( ctx.bLeaf==0 ){
    /* Set the right-child pointer of the rightmost new sibling to a copy
    ** of the same pointer from the rightmost original sibling.  */
    u8 *aRightSibling = btPageData(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;
  }

#ifdef BT_STDERR_DEBUG
  {
    int iDbg;
    for(iDbg=0; iDbg<ctx.nOut; iDbg++){
      u8 *aData = btPageData(ctx.apPg[iDbg]);
      printPage(stderr, sqlite4BtPagePgno(ctx.apPg[iDbg]), aData, pgsz);
    }
  }
#endif

  /* The leaves are written. Now gather the keys and page numbers to
  ** push up into the parent page. This is only required when rebalancing

  }
  if( rc==SQLITE4_OK && iPg==pCsr->nPg ){
    rc = btBalanceIfUnderfull(pCsr);
  }

#ifdef BT_STDERR_DEBUG
  {
    u8 *aData = btPageData(pPar);
    printPage(stderr, sqlite4BtPagePgno(pPar), aData, pgsz);
  }
#endif

 rebalance_out:
  for(iPg=0; iPg<array_size(ctx.apPg); iPg++){
    sqlite4BtPageRelease(ctx.apPg[iPg]);

  assert( pCsr->nPg==1 );

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

    memcpy(aData, aRoot, pgsz);
    aRoot[0] = BT_PGFLAGS_INTERNAL;
    if( pHdr->iMRoot==pCsr->iRoot ) aRoot[0] |= BT_PGFLAGS_METATREE;
    btPutU32(&aRoot[1], sqlite4BtPagePgno(pNew));
    btPutU16(&aRoot[pgsz-2], 0);
    btPutU16(&aRoot[pgsz-4], 5);

  for(i=0; i<nKV; i++){
    nReq += btKVCellSize(&apKV[i]) + 2;
  }

  iCell = pCsr->aiCell[pCsr->nPg-1];
  assert( pCsr->nPg>0 );
  pLeaf = pCsr->apPage[pCsr->nPg-1];
  aData = (u8*)btPageData(pLeaf);

  /* Set the bLeaf variable to true if inserting into a leaf page, or
  ** false otherwise. Return SQLITE4_CORRUPT if the page is a leaf but
  ** the KeyValue pairs being inserted are suitable for internal nodes,
  ** or vice-versa.  */
  assert( nKV>0 );
  if( (0==(btFlags(aData) & BT_PGFLAGS_INTERNAL))!=bLeaf ){

    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 = btPageData(pLeaf);
    }

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

  if( nFree>=nReq ){
    /* The new entry will fit on the page. So in this case all there
    ** is to do is update this single page. The easy case. */
    rc = sqlite4BtPageWrite(pLeaf);
    if( rc==SQLITE4_OK ){
      aData = btPageData(pLeaf);

      /* Make space within the cell pointer array */
      if( iCell!=nCell ){
        u8 *aFrom = btCellPtrFind(aData, pgsz, nCell-1);
        u8 *aTo = btCellPtrFind(aData, pgsz, nCell-1+nKV);
        memmove(aTo, aFrom, (nCell-iCell) * 2);
      }

    int i;                        /* Used to iterate through cells to delete */
    u8 *aData;                    /* Page buffer */
    int nCell;                    /* Number of cells initially on this page */
    int iDel;                     /* Index of cell to delete */
    int nFreed = 0;               /* Total bytes of space freed */

    iDel = pCsr->aiCell[pCsr->nPg-1];
    aData = (u8*)btPageData(pPg);
    nCell = btCellCount(aData, pgsz);

    for(i=iDel; i<(iDel+nDel); i++){
      int nByte;
      btCellFindSize(aData, pgsz, i, &nByte);
      nFreed += nByte + 2;
    }

}

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 = btPageData(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 = btPageData(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);
  }

  u32 iNew = 0;
  BtPage *pPg;
  int rc;

  assert( flag==BT_PGFLAGS_METATREE || flag==BT_PGFLAGS_SCHEDULE || flag==0 );
  rc = sqlite4BtPageAllocate(db->pPager, &pPg);
  if( rc==SQLITE4_OK ){
    u8 *aData = btPageData(pPg);
    aData[0] = (flag & 0xFF);
    iNew = sqlite4BtPagePgno(pPg);
    sqlite4BtPageRelease(pPg);
  }

  *piNew = iNew;
  return rc;

  return SQLITE4_OK;
}

static void btWriteSchedulePage(BtPage *pPg, BtSchedule *p, int *pRc){
  if( *pRc==SQLITE4_OK ){
    int rc = sqlite4BtPageWrite(pPg);
    if( rc==SQLITE4_OK ){
      u8 *aData = btPageData(pPg);
      btWriteSchedule(aData, p, &rc);
    }
    *pRc = rc;
  }
}

static int btAllocateBlock(

    delcsr.nPg = 1;
    delcsr.base.pDb = db;

    while( rc==SQLITE4_OK && iTrunk!=0 ){
      BtPage *pTrunk = 0;
      rc = sqlite4BtPageGet(db->pPager, iTrunk, &pTrunk);
      if( rc==SQLITE4_OK ){
        u8 *aTData = btPageData(pTrunk);
        int nOvfl = btGetU32(aTData);
        int i;

        for(i=0; i<nOvfl; i++){
          u32 lpgno = btGetU32(&aTData[8 + i*8]);
          delcsr.aiCell[0] = (int)btGetU32(&aTData[8 + i*8 + 4]);
          rc = sqlite4BtPageGet(db->pPager, lpgno, &delcsr.apPage[0]);

  u32 iMax;                       /* Maximum input level number */
  u32 iOutLvl;                    /* Output level number */

  /* Find the schedule page. If there is no schedule page, allocate it now. */
  if( pHdr->iSRoot==0 ){
    rc = sqlite4BtPageAllocate(db->pPager, &pPg);
    if( rc==SQLITE4_OK ){
      u8 *aData = btPageData(pPg);
      memset(aData, 0, pHdr->pgsz);
      sqlite4BtPagerDbhdrDirty(db->pPager);
      pHdr->iSRoot = sqlite4BtPagePgno(pPg);
    }
  }else{
    rc = sqlite4BtPageGet(db->pPager, pHdr->iSRoot, &pPg);
  }

  /* Check if the schedule page is busy. If so, no new merge may be 
  ** scheduled. If the schedule page is not busy, call btFindMerge() to
  ** figure out which levels should be scheduled for merge.  */
  if( rc==SQLITE4_OK ){
    aData = btPageData(pPg);
    
    switch( btGetU32(aData) ){
      case BT_SCHEDULE_BUSY:
        rc = SQLITE4_NOTFOUND;
        break;

      case BT_SCHEDULE_DONE: {

    if( rc==SQLITE4_OK ){
      u32 iRoot = btFirstOfBlock(pHdr, pHdr->iSubBlock);
      BtPage *pPg = 0;

      rc = sqlite4BtPageGet(db->pPager, iRoot, &pPg);
      if( rc==SQLITE4_OK ) rc = sqlite4BtPageWrite(pPg);
      if( rc==SQLITE4_OK ){
        u8 *aData = btPageData(pPg);
        memset(&aData[pHdr->pgsz-6], 0, 6);
        aData[0] = 0;
      }
      sqlite4BtPageRelease(pPg);
    }
  }

  BtPage *pPg;
  sqlite4_buffer buf;
  int pgsz;

  pgsz = sqlite4BtPagerPagesize(db->pPager);
  sqlite4_buffer_init(&buf, 0);
  sqlite4BtPageGet(db->pPager, iRoot, &pPg);
  btPageToAscii(iRoot, 1, db->pPager, btPageData(pPg), pgsz, &buf);
  fprintf(stderr, "%d TREE at %d:\n", iCall, (int)iRoot);
  fprintf(stderr, "%.*s", buf.n, (char*)buf.p);
  sqlite4_buffer_clear(&buf);
  sqlite4BtPageRelease(pPg);
}

void sqlite4BtDebugFastTree(bt_db *db, int iCall){

        BtPage *pPg = 0;
        rc = sqlite4BtPageGet(db->pPager, pInfo->pgno, &pPg);
        if( rc==SQLITE4_OK ){
          BtPager *p = db->pPager;
          int bAscii = (pInfo->eType==BT_INFO_PAGEDUMP_ASCII);
          u8 *aData;
          int nData;
          aData = btPageData(pPg);
          nData = sqlite4BtPagerPagesize(p);
          btPageToAscii(pInfo->pgno, bAscii, p, aData, nData, &pInfo->output);
          sqlite4_buffer_append(&pInfo->output, "", 1);
          sqlite4BtPageRelease(pPg);
        }
        btControlTransactionDone(db, iCtx);
      }

    while( rc==SQLITE4_OK && iTrunk ){
      BtPage *pPg = 0;
      rc = sqlite4BtPageGet(db->pPager, iTrunk, &pPg);
      if( rc==SQLITE4_OK ){
        int i;
        u32 nFree;
        u8 *aData = btPageData(pPg);

        nFree = btGetU32(aData);
        for(i=0; i<nFree; i++){
          u32 pgno = btGetU32(&aData[8 + i*4]);
          if( bBlocklist ){
            markBlockAsUsed(db, pgno, aUsed);
          }else{

    int rc;

    rc = sqlite4BtPageGet(db->pPager, pHdr->iSRoot, &pPg);
    if( rc==SQLITE4_OK ){
      BtSchedule s;
      int i;

      btReadSchedule(db, btPageData(pPg), &s);
      sqlite4BtPageRelease(pPg);

      assert( s.eBusy!=BT_SCHEDULE_BUSY || s.aRoot[0]==0 );
      if( s.eBusy!=BT_SCHEDULE_EMPTY ){
        for(i=0; rc==SQLITE4_OK && i<array_size(s.aBlock); i++){
          markBlockAsUsed(db, s.aBlock[i], aUsed);
        }

  BtPage *pPg;                    /* Pointer to page this object belongs to */
  u8 *aData;                      /* Saved data */
  BtSavepage *pNext;              /* Next saved page in the same savepoint */
  int iSavepoint;                 /* Transaction number of savepoint */
  BtSavepage *pNextSavepage;      /* Next saved page on the same BtPage */
};

/*
** See macro btPageData() in bt_main.c for why the aData variable must be
** first in this structure.
*/
struct BtPage {
  u8 *aData;                      /* Pointer to current data. MUST BE FIRST */
  BtPager *pPager;                /* Pager object that owns this page handle */
  u32 pgno;                       /* Current page number */
  int nRef;                       /* Number of references to this page */
  int flags;                      /* Mask of BTPAGE_XXX flags */

  BtPage *pNextHash;              /* Next entry with same hash key */
  BtPage *pNextDirty;             /* Next page in BtPager.pDirty list */
  BtPage *pNextLru;               /* Next page in LRU list */
  BtPage *pPrevLru;               /* Previous page in LRU list */
  BtSavepage *pSavepage;          /* List of saved page images */
};

/*
** Candidate values for BtPage.flags
*/
#define BT_PAGE_DIRTY 0x0001      /* Set for pages in BtPager.pDirty list */

  BtLock btl;                     /* Variables shared with bt_lock module */
  BtLog *pLog;                    /* Logging module */
  int iTransactionLevel;          /* Current transaction level (see bt.h) */
  char *zFile;                    /* Database file name */
  int nFile;                      /* Length of string zFile in bytes */
  BtPageHash hash;                /* Hash table */
  BtPage *pDirty;                 /* List of all dirty pages */
  BtPage *pLru;                   /* Head of LRU list */
  BtPage *pLruTail;               /* Tail of LRU list */
  int nPageAlloc;                 /* Number of page objects allocated */
  int nPageLimit;                 /* Maximum page objects to allocate */
  int nTotalRef;                  /* Total number of outstanding page refs */
  int bDoAutoCkpt;                /* Do auto-checkpoint after next unlock */
  BtSavepoint *aSavepoint;        /* Savepoint array */
  int nSavepoint;                 /* Number of entries in aSavepoint array */
  BtDbHdr *pHdr;                  /* Header object for current read snapshot */
  int bDirtyHdr;                  /* True if pHdr has been modified */
  void *pLogsizeCtx;              /* A copy of this is passed to xLogsize() */

    }
  }
}
#endif
/*
** End of BtPageHash object interface.
**************************************************************************/

static void btLruAdd(BtPager *pPager, BtPage *pPg){
  assert( pPg->pPrevLru==0 );
  assert( pPg->pNextLru==0 );
  if( pPager->pLru ){
    pPager->pLruTail->pNextLru = pPg;
    pPg->pPrevLru = pPager->pLruTail;
    pPager->pLruTail = pPg;
  }else{
    pPager->pLru = pPg;
    pPager->pLruTail = pPg;
  }
}

/*
** Remove page pPg from the LRU list. If pPg is not currently part of
** the LRU list, the results are undefined.
*/
static void btLruRemove(BtPager *pPager, BtPage *pPg){
  assert( (pPg==pPager->pLru)==(pPg->pPrevLru==0) );
  assert( (pPg==pPager->pLruTail)==(pPg->pNextLru==0) );

  if( pPg->pNextLru ){
    pPg->pNextLru->pPrevLru = pPg->pPrevLru;
  }else{
    pPager->pLruTail = pPg->pPrevLru;
  }
  if( pPg->pPrevLru ){
    pPg->pPrevLru->pNextLru = pPg->pNextLru;
  }else{
    pPager->pLru = pPg->pNextLru;
  }

  pPg->pNextLru = 0;
  pPg->pPrevLru = 0;
}

/*
** Open a new pager database handle.
*/
int sqlite4BtPagerNew(sqlite4_env *pEnv, int nExtra, BtPager **pp){
  BtPager *p;
  int nByte;

  nByte = sizeof(BtPager) + nExtra;
  p = (BtPager*)sqlite4_malloc(pEnv, nByte);
  if( !p ) return btErrorBkpt(SQLITE4_NOMEM); 
  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;
  p->nPageLimit = BT_DEFAULT_CACHESZ;
  *pp = p;
  return SQLITE4_OK;
}

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

    BtPage *pNext;
    for(pPg=p->hash.aHash[i]; pPg; pPg=pNext){
      pNext = pPg->pNextHash;
      btFreePage(p, pPg);
    }
  }
  btHashClear(p);

  p->pLruTail = 0;
  p->pLru = 0;
}

static int btCheckpoint(BtLock *pLock){
  BtPager *p = (BtPager*)pLock;
  if( p->pLog==0 ) return SQLITE4_BUSY;
  return sqlite4BtLogCheckpoint(p->pLog, 0);
}

  assert( p->pHdr );
  p->pHdr = 0;
  rc = sqlite4BtLogSnapshotClose(p->pLog);

  /* Purge the page cache. */
  assert( p->pDirty==0 );
  //btPurgeCache(p);

  if( rc==SQLITE4_OK && p->bDoAutoCkpt ){
    sqlite4BtLogCheckpoint(p->pLog, (p->btl.nAutoCkpt / 2));
  }
  p->bDoAutoCkpt = 0;

  return rc;

    pNext = pPg->pNextDirty;
    pPg->flags &= ~(BT_PAGE_DIRTY);
    pPg->pNextDirty = 0;
    if( rc==SQLITE4_OK ){
      int nPg = ((pNext==0) ? p->pHdr->nPg : 0);
      rc = sqlite4BtLogWrite(p->pLog, pPg->pgno, pPg->aData, nPg);
    }
    if( pPg->nRef==0 ) btLruAdd(p, pPg);
  }
  p->pDirty = pPg;
  sqlite4BtLogSnapshotEndWrite(p->pLog);

  nLogsize = sqlite4BtLogSize(p->pLog);

  if( p->btl.nAutoCkpt && nLogsize>=p->btl.nAutoCkpt ){
    p->bDoAutoCkpt = 1;
  }

    rc = p->btl.pVfs->xRead(p->btl.pFd, iOff, pPg->aData, p->pHdr->pgsz);
  }

  return rc;
}

static int btAllocatePage(BtPager *p, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */
  BtPage *pRet;

  if( p->hash.nEntry>=p->nPageLimit && p->pLru ){
    BtPage **pp;
    int h;

    /* Remove the page from the head of the LRU list. */
    pRet = p->pLru;
    assert( (pRet->pNextLru==0)==(pRet==p->pLruTail) );
    p->pLru = pRet->pNextLru;
    if( p->pLru==0 ){
      p->pLruTail = 0;
    }else{
      p->pLru->pPrevLru = 0;
    }

    /* Remove the page from the hash table. */
    btHashRemove(p, pRet);

    assert( pRet->pPrevLru==0 );
    assert( pRet->nRef==0 );
    assert( pRet->pSavepage==0 );
    pRet->flags = 0;
    pRet->pNextHash = 0;
    pRet->pNextDirty = 0;
    pRet->pNextLru = 0;
  }else{
    u8 *aData = (u8*)sqlite4_malloc(p->btl.pEnv, p->pHdr->pgsz);
    pRet = (BtPage*)sqlite4_malloc(p->btl.pEnv, sizeof(BtPage));

    if( pRet && aData ){
      memset(pRet, 0, sizeof(BtPage));
      pRet->aData = aData;
      pRet->pPager = p;

    }else{
      sqlite4_free(p->btl.pEnv, pRet);
      sqlite4_free(p->btl.pEnv, aData);
      rc = btErrorBkpt(SQLITE4_NOMEM);
      pRet = 0;
    }
  }

  *ppPg = pRet;
  return rc;
}

/*

      if( rc!=SQLITE4_OK ){
        btFreePage(p, pRet);
        pRet = 0;
      }else{
        sqlite4BtDebugReadPage(&p->btl, pgno, pRet->aData, p->pHdr->pgsz);
      }
    }
  }else if( pRet->nRef==0 && (pRet->flags & BT_PAGE_DIRTY)==0 ){
    btLruRemove(p, pRet);
  }

  assert( (pRet!=0)==(rc==SQLITE4_OK) );
  if( rc==SQLITE4_OK ){
    p->nTotalRef++;
    pRet->nRef++;
  }

*/
int sqlite4BtPageTrimPgno(BtPager *pPager, u32 pgno){
  return btFreelistAdd(pPager, 0, pgno);
}

int sqlite4BtPageRelease(BtPage *pPg){
  if( pPg ){
    BtPager *pPager = pPg->pPager;

    assert( pPg->nRef>=1 );
    pPg->nRef--;
    pPg->pPager->nTotalRef--;

    /* If the refcount is now zero and the page is not dirty, add it to
    ** the LRU list.  */
    if( pPg->nRef==0 && (pPg->flags & BT_PAGE_DIRTY)==0 ){
      btLruAdd(pPager, pPg);
    }
  }
  return SQLITE4_OK;
}

void sqlite4BtPageReference(BtPage *pPg){
  assert( pPg->nRef>=1 );
  pPg->nRef++;

# focus of this file is testing the SELECT statement.
#
# $Id: select1.test,v 1.70 2009/05/28 01:00:56 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl




# Try to select on a non-existant table.
#
do_test select1-1.1 {
  set v [catch {execsql {SELECT * FROM test1}} msg]
  lappend v $msg
} {1 {no such table: test1}}