*/
u32 sqlite4BtPagerRootpgno(BtPager*);

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

int sqlite4BtPageWrite(BtPage*);
int sqlite4BtPageTrim(BtPage*);
int sqlite4BtPageRelease(BtPage*);
void sqlite4BtPageReference(BtPage*);

/*
** Allocate a new database page and return a writable reference to it.

*/
u32 sqlite4BtPagerRootpgno(BtPager*);

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

/*
** Allocate a new database page and return a writable reference to it.

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

#ifndef MIN
# define MIN(a,b) (((a)<(b))?(a):(b))
#endif




#define BT_EXPENSIVE_ASSERT 0


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

................................................................................
    rc = btErrorBkpt(SQLITE4_NOMEM);
  }else{
    btCsrSetup(db, pCsr);
    pCsr->pNextCsr = db->pAllCsr;
    db->pAllCsr = pCsr;
  }


  return rc;
}

static void btCsrReset(bt_cursor *pCsr, int bFreeBuffer){
  int i;
  for(i=0; i<pCsr->nPg; i++){
    sqlite4BtPageRelease(pCsr->apPage[i]);
................................................................................
  }
  if( bFreeBuffer ) sqlite4_free(pCsr->pDb->pEnv, pCsr->ovfl.pBuf);
  pCsr->nPg = 0;
}

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

    bt_cursor **pp;

    btCsrReset(pCsr, 1);
    for(pp=&pCsr->pDb->pAllCsr; *pp!=pCsr; pp=&(*pp)->pNextCsr);
    *pp = pCsr->pNextCsr;
    sqlite4_free(pCsr->pDb->pEnv, pCsr);

  }
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return (void*)&pCsr[1];
}
................................................................................
static int btCsrDescend(bt_cursor *pCsr, u32 pgno){
  int rc;
  if( pCsr->nPg>=BT_MAX_DEPTH ){
    rc = btErrorBkpt(SQLITE4_CORRUPT);
  }else{
    rc = sqlite4BtPageGet(pCsr->pDb->pPager, pgno, &pCsr->apPage[pCsr->nPg]);
    if( rc==SQLITE4_OK ){

      pCsr->nPg++;
    }
  }
  return rc;
}

/*
................................................................................
** or SQLITE4_OK otherwise.
*/
static int btCsrAscend(bt_cursor *pCsr, int nLvl){
  int i;
  for(i=0; i<nLvl && ( pCsr->nPg>0 ); i++){
    pCsr->nPg--;
    sqlite4BtPageRelease(pCsr->apPage[pCsr->nPg]);

  }
  return (pCsr->nPg==0 ? SQLITE4_NOTFOUND : SQLITE4_OK);
}

/**************************************************************************
** The functions in this section are used to extract data from buffers
** containing formatted b-tree pages. They do not entirely encapsulate all
................................................................................
  return 0;
}
#endif


/*
** This function compares the key passed via parameters pK and nK to the
** key stored as part of cell iCell on the database page stored in buffer
** aData (size nData bytes).
**
** If the cell key is C, and the user key K, then this function sets:
**
**     *piRes = (C - K).
**
** In other workds, *piRes is +ve, zero or -ve if C is respectively larger, 
** equal to or smaller than K.
*/
#if 0
static int btCellKeyCompare(
  bt_cursor *pCsr,                /* Cursor handle */
  const u8 *aData, int nData,     /* Page data (nData is the page size) */
  int iCell,                      /* Cell to compare key from */
  const u8 *pK, int nK,           /* Key to compare to cell key */

  int *piRes                      /* OUT: Result of comparison */
){
  BtPage *pLeaf = 0;              /* Leaf page reference to release */
  int rc = SQLITE4_OK;
  int nCellKey;                   /* Number of bytes in cell key */
  int res;
  u8 *pCell = btCellFind((u8*)aData, nData, iCell);
  int nCmp;
  int nAscend = 0;

  pCell += sqlite4BtVarintGet32(pCell, &nCellKey);
  if( nCellKey==0 ){
    if( (btFlags(aData, nData) & BT_PGFLAGS_INTERNAL)==0 ){
      rc = sqlite4BtCsrKey(pCsr, &pCell, &nCellKey);
    }else{
      rc = btOverflowBuffer(pCsr, 0);
      if( rc!=SQLITE4_OK ) return rc;
      pK = pCsr->ovfl.pBuf;
    }else{
      assert( 0 );
    }
  }

  nCmp = MIN(nCellKey, nK);
  res = memcmp(pCell, pK, nCmp);
  if( res==0 ){
    res = nCellKey - nK;
  }

  *piRes = res;
  return rc;
}
#endif

static int btCellKeyCompare(
  bt_cursor *pCsr, 
  int bLeaf, 
  const void *pK, 
  int nK, 
  int *piRes
){
  const void *pCsrKey;
  int nCsrKey;
  int nCmp;
  int nAscend = 0;
  int rc = SQLITE4_OK;
  int res;

................................................................................
    const int pgsz = sqlite4BtPagerPagesize(pCsr->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 ){

      while( 1 ){
        u8 *aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
        u32 pgno = btChildPgno(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);
        nAscend++;
        rc = btCsrDescend(pCsr, pgno);
        if( rc!=SQLITE4_OK ) break;
        aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
        pCsr->aiCell[pCsr->nPg-1] = btCellCount(aData, pgsz);
        if( (btFlags(aData) & BT_PGFLAGS_INTERNAL)==0 ) break;

      }
      pCsr->aiCell[pCsr->nPg-1]--;
      rc = sqlite4BtCsrKey(pCsr, &pCsrKey, &nCsrKey);
    }
  }

  if( rc==SQLITE4_OK ){
    nCmp = MIN(nCsrKey, nK);
    res = memcmp(pCsrKey, pK, nCmp);
................................................................................
        }else{
          /* Cell iTst is LARGER than pK/nK */
          iHi = iTst;
        }
      }
      if( rc!=SQLITE4_OK ) break;
      assert( iHi==iLo );
      pCsr->aiCell[pCsr->nPg-1] = iHi;


#if 0
printPage(stderr, pgno, aData, pgsz);
#endif

      if( bLeaf==0 ){
        pgno = btChildPgno(aData, pgsz, iHi);
      }else{
        pgno = 0;

        if( res!=0 ){
          assert( BT_SEEK_LEFAST<0 && BT_SEEK_LE<0 );
................................................................................

int sqlite4BtCsrSeek(
  bt_cursor *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) */
){


  return btCsrSeek(pCsr, pK, nK, eSeek, 0);


}

/*
** This function seeks the cursor as required for either sqlite4BtCsrFirst()
** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
*/
static int btCsrEnd(bt_cursor *pCsr, int bLast){
................................................................................
    }
  }

  assert( rc!=SQLITE4_OK || iCall==p->nCell );
  return rc;
}
























































int btBalance(
  bt_cursor *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 */
){
................................................................................

  /* The leaves are written. Now gather the keys and page numbers to
  ** push up into the parent page. This is only required when rebalancing
  ** b-tree leaves. When internal nodes are balanced, the btBalanceOutput
  ** loop accumulates the cells destined for the parent page.  */
  for(iPg=0; iPg<(ctx.nOut-1); iPg++){
    ctx.aPCell[iPg].pgno = sqlite4BtPagePgno(ctx.apPg[iPg]);
    assert( ctx.aPCell[iPg].nK==0 );

    if( bLeaf ){
#if 0
      u8 *aData = sqlite4BtPageData(ctx.apPg[iPg]);
      u8 *pCell;
      pCell = btCellFind(aData, pgsz, btCellCount(aData, pgsz)-1);
      pCell += sqlite4BtVarintGet32(pCell, &ctx.aPCell[iPg].nK);
      ctx.aPCell[iPg].pK = pCell;
#endif

    }
  }

  rc = btSetChildPgno(
      pDb, pPar, iSib+ctx.nIn-1, sqlite4BtPagePgno(ctx.apPg[ctx.nOut-1])
  );
  if( rc==SQLITE4_OK ){
................................................................................

  btCheckPageRefs(db);
  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  int rc;
  btCheckPageRefs(pCsr->pDb);
  rc =  btDeleteFromPage(pCsr, 1);
  if( rc==SQLITE4_OK ){
    rc = btBalanceIfUnderfull(pCsr);
  }
  btCheckPageRefs(pCsr->pDb);
  return rc;
}

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

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}

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

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

#define BT_EXPENSIVE_ASSERT 0
/* #define BT_STDERR_DEBUG 1 */

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

................................................................................
    rc = btErrorBkpt(SQLITE4_NOMEM);
  }else{
    btCsrSetup(db, pCsr);
    pCsr->pNextCsr = db->pAllCsr;
    db->pAllCsr = pCsr;
  }

  btCheckPageRefs(db);
  return rc;
}

static void btCsrReset(bt_cursor *pCsr, int bFreeBuffer){
  int i;
  for(i=0; i<pCsr->nPg; i++){
    sqlite4BtPageRelease(pCsr->apPage[i]);
................................................................................
  }
  if( bFreeBuffer ) sqlite4_free(pCsr->pDb->pEnv, pCsr->ovfl.pBuf);
  pCsr->nPg = 0;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  if( pCsr ){
    bt_db *pDb = pCsr->pDb;
    bt_cursor **pp;
    btCheckPageRefs(pDb);
    btCsrReset(pCsr, 1);
    for(pp=&pDb->pAllCsr; *pp!=pCsr; pp=&(*pp)->pNextCsr);
    *pp = pCsr->pNextCsr;
    sqlite4_free(pDb->pEnv, pCsr);
    btCheckPageRefs(pDb);
  }
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return (void*)&pCsr[1];
}
................................................................................
static int btCsrDescend(bt_cursor *pCsr, u32 pgno){
  int rc;
  if( pCsr->nPg>=BT_MAX_DEPTH ){
    rc = btErrorBkpt(SQLITE4_CORRUPT);
  }else{
    rc = sqlite4BtPageGet(pCsr->pDb->pPager, pgno, &pCsr->apPage[pCsr->nPg]);
    if( rc==SQLITE4_OK ){
      assert( pCsr->apPage[pCsr->nPg] );
      pCsr->nPg++;
    }
  }
  return rc;
}

/*
................................................................................
** or SQLITE4_OK otherwise.
*/
static int btCsrAscend(bt_cursor *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);
}

/**************************************************************************
** The functions in this section are used to extract data from buffers
** containing formatted b-tree pages. They do not entirely encapsulate all
................................................................................
  return 0;
}
#endif


/*
** This function compares the key passed via parameters pK and nK to the
** key that cursor pCsr currently points to.

**
** If the cursor key is C, and the user key K, then this function sets:
**
**     *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(
  bt_cursor *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;

................................................................................
    const int pgsz = sqlite4BtPagerPagesize(pCsr->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(pCsr, &pCsrKey, &nCsrKey);
    }
  }

  if( rc==SQLITE4_OK ){
    nCmp = MIN(nCsrKey, nK);
    res = memcmp(pCsrKey, pK, nCmp);
................................................................................
        }else{
          /* Cell iTst is LARGER than pK/nK */
          iHi = iTst;
        }
      }
      if( rc!=SQLITE4_OK ) break;
      assert( iHi==iLo );


      iHi += (bLeaf==0 && res==0);
      pCsr->aiCell[pCsr->nPg-1] = iHi;



      if( bLeaf==0 ){
        pgno = btChildPgno(aData, pgsz, iHi);
      }else{
        pgno = 0;

        if( res!=0 ){
          assert( BT_SEEK_LEFAST<0 && BT_SEEK_LE<0 );
................................................................................

int sqlite4BtCsrSeek(
  bt_cursor *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 rc;
  btCheckPageRefs(pCsr->pDb);
  rc = btCsrSeek(pCsr, pK, nK, eSeek, 0);
  btCheckPageRefs(pCsr->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(bt_cursor *pCsr, int bLast){
................................................................................
    }
  }

  assert( rc!=SQLITE4_OK || iCall==p->nCell );
  return rc;
}

/*
** Extract a key-prefix from page pPg, which resides in a database with
** page size pgsz. If parameter bLast is true, the key-prefix is extracted
** from the right-most cell on the page. If bLast is false, the key-prefix
** is extracted from the left-most cell.
**
** A pointer to the key-prefix is returned. Before returning, *pnByte is
** 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 = sqlite4BtPageData(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;
}

/*
** Parameters pLeft and pRight point to a pair of adjacent leaf pages in
** a database with page size pgsz. The keys in pRight are larger than those
** in pLeft. This function populates pKV->pK and pKV->nK with a separator
** key that is:
**
**   * 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 = pgsz/4;

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

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

  nMax = MIN(nLeft, nMaxPrefix);
  for(i=0; i<nMax && aLeft[i]==aRight[i]; i++);
  if( i<nMaxPrefix ){
    pKV->pK = aRight;
    pKV->nK = i + 1;
    assert( pKV->nK<=nRight );
  }
}

int btBalance(
  bt_cursor *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 */
){
................................................................................

  /* The leaves are written. Now gather the keys and page numbers to
  ** push up into the parent page. This is only required when rebalancing
  ** b-tree leaves. When internal nodes are balanced, the btBalanceOutput
  ** loop accumulates the cells destined for the parent page.  */
  for(iPg=0; iPg<(ctx.nOut-1); iPg++){
    ctx.aPCell[iPg].pgno = sqlite4BtPagePgno(ctx.apPg[iPg]);


    if( bLeaf ){





      assert( ctx.aPCell[iPg].nK==0 );

      btPrefixKey(pgsz, ctx.apPg[iPg], ctx.apPg[iPg+1], &ctx.aPCell[iPg]);
    }
  }

  rc = btSetChildPgno(
      pDb, pPar, iSib+ctx.nIn-1, sqlite4BtPagePgno(ctx.apPg[ctx.nOut-1])
  );
  if( rc==SQLITE4_OK ){
................................................................................

  btCheckPageRefs(db);
  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  int rc;

  rc =  btDeleteFromPage(pCsr, 1);
  if( rc==SQLITE4_OK ){
    rc = btBalanceIfUnderfull(pCsr);
  }

  return rc;
}

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

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}

      if( rc!=SQLITE4_OK ){
        btFreePage(p, pRet);
        pRet = 0;
      }
    }
  }


  if( rc==SQLITE4_OK ){
    p->nTotalRef++;
    pRet->nRef++;
    *ppPg = pRet;
  }

  return rc;
}

int sqlite4BtPageWrite(BtPage *pPg){
  if( (pPg->flags & BT_PAGE_DIRTY)==0 ){
    pPg->flags |= BT_PAGE_DIRTY;
    pPg->pNextDirty = pPg->pPager->pDirty;
................................................................................
** no longer in use.
*/
int sqlite4BtPageTrim(BtPage *pPg){
  /* assert( !"todo" ); */
  sqlite4BtPageRelease(pPg);
  return SQLITE4_OK;
}








int sqlite4BtPageRelease(BtPage *pPg){
  if( pPg ){
    assert( pPg->nRef>=1 );
    pPg->nRef--;
    pPg->pPager->nTotalRef--;
  }

      if( rc!=SQLITE4_OK ){
        btFreePage(p, pRet);
        pRet = 0;
      }
    }
  }

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

  }
  *ppPg = pRet;
  return rc;
}

int sqlite4BtPageWrite(BtPage *pPg){
  if( (pPg->flags & BT_PAGE_DIRTY)==0 ){
    pPg->flags |= BT_PAGE_DIRTY;
    pPg->pNextDirty = pPg->pPager->pDirty;
................................................................................
** no longer in use.
*/
int sqlite4BtPageTrim(BtPage *pPg){
  /* assert( !"todo" ); */
  sqlite4BtPageRelease(pPg);
  return SQLITE4_OK;
}

/*
** Page number pgno is no longer in use.
*/
int sqlite4BtPageTrimPgno(BtPager *pPager, u32 pgno){
  return SQLITE4_OK;
}

int sqlite4BtPageRelease(BtPage *pPg){
  if( pPg ){
    assert( pPg->nRef>=1 );
    pPg->nRef--;
    pPg->pPager->nTotalRef--;
  }