SQLite

/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.517 2008/09/26 17:31:55 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

  /* If this is an intKey table, then the above call to BtreeKeySize()
  ** stores the integer key in pCur->nKey. In this case this value is
  ** all that is required. Otherwise, if pCur is not open on an intKey
  ** table, then malloc space for and store the pCur->nKey bytes of key 
  ** data.
  */
  if( rc==SQLITE_OK && 0==pCur->pPage->intKey){
    void *pKey = sqlite3Malloc(pCur->nKey);
    if( pKey ){
      rc = sqlite3BtreeKey(pCur, 0, pCur->nKey, pKey);
      if( rc==SQLITE_OK ){
        pCur->pKey = pKey;
      }else{
        sqlite3_free(pKey);
      }
    }else{
      rc = SQLITE_NOMEM;
    }
  }
  assert( !pCur->pPage->intKey || !pCur->pKey );

  if( rc==SQLITE_OK ){


    releasePage(pCur->pPage);


    pCur->pPage = 0;
    pCur->eState = CURSOR_REQUIRESEEK;
  }

  invalidateOverflowCache(pCur);
  return rc;
}

  }
  return SQLITE_OK;
}

/*
** Initialize the auxiliary information for a disk block.
**
** The pParent parameter must be a pointer to the MemPage which
** is the parent of the page being initialized.  The root of a
** BTree has no parent and so for that page, pParent==NULL.
**
** Return SQLITE_OK on success.  If we see that the page does
** not contain a well-formed database page, then return 
** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not
** guarantee that the page is well-formed.  It only shows that
** we failed to detect any corruption.
*/
int sqlite3BtreeInitPage(
  MemPage *pPage,        /* The page to be initialized */





  MemPage *pParent       /* The parent.  Might be NULL */
){
  int pc;            /* Address of a freeblock within pPage->aData[] */
  int hdr;           /* Offset to beginning of page header */
  u8 *data;          /* Equal to pPage->aData */
  BtShared *pBt;        /* The main btree structure */
  int usableSize;    /* Amount of usable space on each page */
  int cellOffset;    /* Offset from start of page to first cell pointer */
  int nFree;         /* Number of unused bytes on the page */
  int top;           /* First byte of the cell content area */

  pBt = pPage->pBt;
  assert( pBt!=0 );
  assert( pParent==0 || pParent->pBt==pBt );
  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) );
  assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) );
  if( pPage==pParent ){
    return SQLITE_CORRUPT_BKPT;
  }
  if( (pPage->pParent!=pParent)
   && (pPage->pParent!=0 || pPage->isInit==PAGE_ISINIT_FULL) ){
    /* The parent page should never change unless the file is corrupt */
    return SQLITE_CORRUPT_BKPT;
  }
  if( pPage->isInit==PAGE_ISINIT_FULL ) return SQLITE_OK;
  if( pParent!=0 ){
    pPage->pParent = pParent;
    sqlite3PagerRef(pParent->pDbPage);
  }
  if( pPage->isInit==PAGE_ISINIT_NONE ){
    hdr = pPage->hdrOffset;
    data = pPage->aData;
    if( decodeFlags(pPage, data[hdr]) ) return SQLITE_CORRUPT_BKPT;
    assert( pBt->pageSize>=512 && pBt->pageSize<=32768 );
    pPage->maskPage = pBt->pageSize - 1;
    pPage->nOverflow = 0;
    pPage->idxShift = 0;
    usableSize = pBt->usableSize;
    pPage->cellOffset = cellOffset = hdr + 12 - 4*pPage->leaf;
    top = get2byte(&data[hdr+5]);
    pPage->nCell = get2byte(&data[hdr+3]);
    if( pPage->nCell>MX_CELL(pBt) ){
      /* To many cells for a single page.  The page must be corrupt */
      return SQLITE_CORRUPT_BKPT;
    }
    if( pPage->nCell==0 && pParent!=0 && pParent->pgno!=1 ){
      /* All pages must have at least one cell, except for root pages */
      return SQLITE_CORRUPT_BKPT;
    }
  
    /* Compute the total free space on the page */
    pc = get2byte(&data[hdr+1]);
    nFree = data[hdr+7] + top - (cellOffset + 2*pPage->nCell);
    while( pc>0 ){
      int next, size;
      if( pc>usableSize-4 ){

      pc = next;
    }
    pPage->nFree = nFree;
    if( nFree>=usableSize ){
      /* Free space cannot exceed total page size */
      return SQLITE_CORRUPT_BKPT; 
    }
  }

#if 0
  /* Check that all the offsets in the cell offset array are within range. 
  ** 
  ** Omitting this consistency check and using the pPage->maskPage mask
  ** to prevent overrunning the page buffer in findCell() results in a
  ** 2.5% performance gain.

    for(pOff=&data[cellOffset]; pOff!=pEnd && !((*pOff)&mask); pOff+=2);
    if( pOff!=pEnd ){
      return SQLITE_CORRUPT_BKPT;
    }
  }
#endif

  pPage->isInit = PAGE_ISINIT_FULL;

  return SQLITE_OK;
}

/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/

  pPage->hdrOffset = hdr;
  pPage->cellOffset = first;
  pPage->nOverflow = 0;
  assert( pBt->pageSize>=512 && pBt->pageSize<=32768 );
  pPage->maskPage = pBt->pageSize - 1;
  pPage->idxShift = 0;
  pPage->nCell = 0;
  pPage->isInit = PAGE_ISINIT_FULL;
}


/*
** Convert a DbPage obtained from the pager into a MemPage used by
** the btree layer.
*/

** Get a page from the pager and initialize it.  This routine
** is just a convenience wrapper around separate calls to
** sqlite3BtreeGetPage() and sqlite3BtreeInitPage().
*/
static int getAndInitPage(
  BtShared *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  DbPage *pDbPage;
  MemPage *pPage;

  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( !pParent || pParent->isInit==PAGE_ISINIT_FULL );
  if( pgno==0 ){
    return SQLITE_CORRUPT_BKPT; 
  }

  /* It is often the case that the page we want is already in cache.
  ** If so, get it directly.  This saves us from having to call
  ** pagerPagecount() to make sure pgno is within limits, which results

    if( pgno>pagerPagecount(pBt->pPager) ){
      return SQLITE_CORRUPT_BKPT; 
    }
    rc = sqlite3BtreeGetPage(pBt, pgno, ppPage, 0);
    if( rc ) return rc;
    pPage = *ppPage;
  }
  if( pPage->isInit!=PAGE_ISINIT_FULL ){
    rc = sqlite3BtreeInitPage(pPage, pParent);
  }else if( pParent && (pPage==pParent || pPage->pParent!=pParent) ){
    /* This condition indicates a loop in the b-tree structure (the scenario
    ** where database corruption has caused a page to be a direct or
    ** indirect descendant of itself).
    */ 
    rc = SQLITE_CORRUPT_BKPT;
  }
  if( rc!=SQLITE_OK ){
    releasePage(pPage);
    *ppPage = 0;
  }
  return rc;
}

    assert( sqlite3PagerGetExtra(pPage->pDbPage) == (void*)pPage );
    assert( sqlite3PagerGetData(pPage->pDbPage)==pPage->aData );
    assert( sqlite3_mutex_held(pPage->pBt->mutex) );
    sqlite3PagerUnref(pPage->pDbPage);
  }
}

/*
** This routine is called when the reference count for a page
** reaches zero.  We need to unref the pParent pointer when that
** happens.
*/
static void pageDestructor(DbPage *pData){
  MemPage *pPage;
  pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  if( pPage ){
    assert( pPage->isInit!=PAGE_ISINIT_FULL 
         || sqlite3_mutex_held(pPage->pBt->mutex) 
    );
    if( pPage->pParent ){
      MemPage *pParent = pPage->pParent;
      assert( pParent->pBt==pPage->pBt );
      pPage->pParent = 0;
      releasePage(pParent);
    }
    if( pPage->isInit==PAGE_ISINIT_FULL ){
      pPage->isInit = PAGE_ISINIT_DATA;
    }
  }
}

/*
** During a rollback, when the pager reloads information into the cache
** so that the cache is restored to its original state at the start of
** the transaction, for each page restored this routine is called.
**
** This routine needs to reset the extra data section at the end of the
** page to agree with the restored data.
*/
static void pageReinit(DbPage *pData){
  MemPage *pPage;
  pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  if( pPage->isInit==PAGE_ISINIT_FULL ){
    assert( sqlite3_mutex_held(pPage->pBt->mutex) );
    pPage->isInit = 0;

    sqlite3BtreeInitPage(pPage, pPage->pParent);
  }else if( pPage->isInit==PAGE_ISINIT_DATA ){
    pPage->isInit = 0;

  }
}

/*
** Invoke the busy handler for a btree.
*/
static int sqlite3BtreeInvokeBusyHandler(void *pArg, int n){

    pBt = sqlite3MallocZero( sizeof(*pBt) );
    if( pBt==0 ){
      rc = SQLITE_NOMEM;
      goto btree_open_out;
    }
    pBt->busyHdr.xFunc = sqlite3BtreeInvokeBusyHandler;
    pBt->busyHdr.pArg = pBt;
    rc = sqlite3PagerOpen(pVfs, &pBt->pPager, zFilename, pageDestructor,
                          EXTRA_SIZE, flags, vfsFlags);
    if( rc==SQLITE_OK ){
      rc = sqlite3PagerReadFileheader(pBt->pPager,sizeof(zDbHeader),zDbHeader);
    }
    if( rc!=SQLITE_OK ){
      goto btree_open_out;
    }

  int nCell;                         /* Number of cells in page pPage */
  int rc;                            /* Return code */
  BtShared *pBt = pPage->pBt;
  int isInitOrig = pPage->isInit;
  Pgno pgno = pPage->pgno;

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  rc = sqlite3BtreeInitPage(pPage, pPage->pParent);
  if( rc!=SQLITE_OK ){
    goto set_child_ptrmaps_out;
  }
  nCell = pPage->nCell;

  for(i=0; i<nCell; i++){
    u8 *pCell = findCell(pPage, i);

    }
    put4byte(pPage->aData, iTo);
  }else{
    int isInitOrig = pPage->isInit;
    int i;
    int nCell;

    sqlite3BtreeInitPage(pPage, 0);
    nCell = pPage->nCell;

    for(i=0; i<nCell; i++){
      u8 *pCell = findCell(pPage, i);
      if( eType==PTRMAP_OVERFLOW1 ){
        CellInfo info;
        sqlite3BtreeParseCellPtr(pPage, pCell, &info);

** 3:  The database must be writable (not on read-only media)
**
** 4:  There must be an active transaction.
**
** No checking is done to make sure that page iTable really is the
** root page of a b-tree.  If it is not, then the cursor acquired
** will not work correctly.



*/
static int btreeCursor(
  Btree *p,                              /* The btree */
  int iTable,                            /* Root page of table to open */
  int wrFlag,                            /* 1 to write. 0 read-only */
  struct KeyInfo *pKeyInfo,              /* First arg to comparison function */
  BtCursor *pCur                         /* Space for new cursor */

    }
  }
  pCur->pgnoRoot = (Pgno)iTable;
  if( iTable==1 && pagerPagecount(pBt->pPager)==0 ){
    rc = SQLITE_EMPTY;
    goto create_cursor_exception;
  }
  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }

  /* Now that no other errors can occur, finish filling in the BtCursor
  ** variables, link the cursor into the BtShared list and set *ppCur (the
  ** output argument to this function).

  }
  pBt->pCursor = pCur;
  pCur->eState = CURSOR_INVALID;

  return SQLITE_OK;

create_cursor_exception:
  releasePage(pCur->pPage);
  unlockBtreeIfUnused(pBt);
  return rc;
}
int sqlite3BtreeCursor(
  Btree *p,                                   /* The btree */
  int iTable,                                 /* Root page of table to open */
  int wrFlag,                                 /* 1 to write. 0 read-only */

/*
** Close a cursor.  The read lock on the database file is released
** when the last cursor is closed.
*/
int sqlite3BtreeCloseCursor(BtCursor *pCur){
  Btree *pBtree = pCur->pBtree;
  if( pBtree ){

    BtShared *pBt = pCur->pBt;
    sqlite3BtreeEnter(pBtree);
    pBt->db = pBtree->db;
    clearCursorPosition(pCur);
    if( pCur->pPrev ){
      pCur->pPrev->pNext = pCur->pNext;
    }else{
      pBt->pCursor = pCur->pNext;
    }
    if( pCur->pNext ){
      pCur->pNext->pPrev = pCur->pPrev;
    }

    releasePage(pCur->pPage);

    unlockBtreeIfUnused(pBt);
    invalidateOverflowCache(pCur);
    /* sqlite3_free(pCur); */
    sqlite3BtreeLeave(pBtree);
  }
  return SQLITE_OK;
}

/*
** Make a temporary cursor by filling in the fields of pTempCur.
** The temporary cursor is not on the cursor list for the Btree.
*/
void sqlite3BtreeGetTempCursor(BtCursor *pCur, BtCursor *pTempCur){

  assert( cursorHoldsMutex(pCur) );
  memcpy(pTempCur, pCur, sizeof(*pCur));
  pTempCur->pNext = 0;
  pTempCur->pPrev = 0;
  if( pTempCur->pPage ){
    sqlite3PagerRef(pTempCur->pPage->pDbPage);
  }
}

/*
** Delete a temporary cursor such as was made by the CreateTemporaryCursor()
** function above.
*/
void sqlite3BtreeReleaseTempCursor(BtCursor *pCur){

  assert( cursorHoldsMutex(pCur) );
  if( pCur->pPage ){
    sqlite3PagerUnref(pCur->pPage->pDbPage);
  }
}

/*
** Make sure the BtCursor* given in the argument has a valid
** BtCursor.info structure.  If it is not already valid, call
** sqlite3BtreeParseCell() to fill it in.

** (when less compiler optimizations like -Os or -O0 are used and the
** compiler is not doing agressive inlining.)  So we use a real function
** for MSVC and a macro for everything else.  Ticket #2457.
*/
#ifndef NDEBUG
  static void assertCellInfo(BtCursor *pCur){
    CellInfo info;

    memset(&info, 0, sizeof(info));
    sqlite3BtreeParseCell(pCur->pPage, pCur->idx, &info);
    assert( memcmp(&info, &pCur->info, sizeof(info))==0 );
  }
#else
  #define assertCellInfo(x)
#endif
#ifdef _MSC_VER
  /* Use a real function in MSVC to work around bugs in that compiler. */
  static void getCellInfo(BtCursor *pCur){
    if( pCur->info.nSize==0 ){

      sqlite3BtreeParseCell(pCur->pPage, pCur->idx, &pCur->info);
      pCur->validNKey = 1;
    }else{
      assertCellInfo(pCur);
    }
  }
#else /* if not _MSC_VER */
  /* Use a macro in all other compilers so that the function is inlined */
#define getCellInfo(pCur)                                               \
  if( pCur->info.nSize==0 ){                                            \

    sqlite3BtreeParseCell(pCur->pPage, pCur->idx, &pCur->info);         \
    pCur->validNKey = 1;                                                \
  }else{                                                                \
    assertCellInfo(pCur);                                               \
  }
#endif /* _MSC_VER */

/*
** Set *pSize to the size of the buffer needed to hold the value of
** the key for the current entry.  If the cursor is not pointing
** to a valid entry, *pSize is set to 0. 

  int skipKey,         /* offset begins at data if this is true */
  int eOp              /* zero to read. non-zero to write. */
){
  unsigned char *aPayload;
  int rc = SQLITE_OK;
  u32 nKey;
  int iIdx = 0;
  MemPage *pPage = pCur->pPage;     /* Btree page of current cursor entry */
  BtShared *pBt;                   /* Btree this cursor belongs to */

  assert( pPage );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  assert( offset>=0 );
  assert( cursorHoldsMutex(pCur) );

  getCellInfo(pCur);
  aPayload = pCur->info.pCell + pCur->info.nHeader;
  nKey = (pPage->intKey ? 0 : pCur->info.nKey);

int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->pPage!=0 );
    if( pCur->pPage->intKey ){
      return SQLITE_CORRUPT_BKPT;
    }
    assert( pCur->pPage->intKey==0 );
    assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
    rc = accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0, 0);
  }
  return rc;
}

/*
** Read part of the data associated with cursor pCur.  Exactly

  }
#endif

  assert( cursorHoldsMutex(pCur) );
  rc = restoreCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
    rc = accessPayload(pCur, offset, amt, pBuf, 1, 0);
  }
  return rc;
}

/*
** Return a pointer to payload information from the entry that the 

  int skipKey          /* read beginning at data if this is true */
){
  unsigned char *aPayload;
  MemPage *pPage;
  u32 nKey;
  int nLocal;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  assert( cursorHoldsMutex(pCur) );
  pPage = pCur->pPage;
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell;
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
  }else{
    nKey = pCur->info.nKey;

/*
** Move the cursor down to a new child page.  The newPgno argument is the
** page number of the child page to move to.
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  int rc;

  MemPage *pNewPage;
  MemPage *pOldPage;
  BtShared *pBt = pCur->pBt;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );




  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
  pOldPage->idxShift = 0;
  releasePage(pOldPage);
  pCur->pPage = pNewPage;

  pCur->idx = 0;

  pCur->info.nSize = 0;
  pCur->validNKey = 0;
  if( pNewPage->nCell<1 ){
    return SQLITE_CORRUPT_BKPT;
  }
  return SQLITE_OK;
}

/*
** Return true if the page is the virtual root of its table.
**
** The virtual root page is the root page for most tables.  But
** for the table rooted on page 1, sometime the real root page
** is empty except for the right-pointer.  In such cases the
** virtual root page is the page that the right-pointer of page
** 1 is pointing to.
*/
int sqlite3BtreeIsRootPage(MemPage *pPage){
  MemPage *pParent;

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  pParent = pPage->pParent;
  if( pParent==0 ) return 1;
  if( pParent->pgno>1 ) return 0;
  if( get2byte(&pParent->aData[pParent->hdrOffset+3])==0 ) return 1;
  return 0;
}

/*
** Move the cursor up to the parent page.
**
** pCur->idx is set to the cell index that contains the pointer
** to the page we are coming from.  If we are coming from the
** right-most child page then pCur->idx is set to one more than
** the largest cell index.
*/
void sqlite3BtreeMoveToParent(BtCursor *pCur){
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !sqlite3BtreeIsRootPage(pPage) );
  pParent = pPage->pParent;
  assert( pParent!=0 );
  assert( pPage->pDbPage->nRef>0 );
  idxParent = pPage->idxParent;
  sqlite3PagerRef(pParent->pDbPage);
  releasePage(pPage);
  pCur->pPage = pParent;
  pCur->info.nSize = 0;
  pCur->validNKey = 0;
  assert( pParent->idxShift==0 );
  pCur->idx = idxParent;
}

/*
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;

  assert( CURSOR_FAULT   > CURSOR_REQUIRESEEK );
  if( pCur->eState>=CURSOR_REQUIRESEEK ){
    if( pCur->eState==CURSOR_FAULT ){
      return pCur->skip;
    }
    clearCursorPosition(pCur);
  }
  pRoot = pCur->pPage;
  if( pRoot && pRoot->isInit ){
    /* If the page the cursor is currently pointing to is fully initialized,
    ** then the root page can be found by following the MemPage.pParent
    ** pointers. This is faster than requesting a reference to the root
    ** page from the pager layer.
    */
    while( pRoot->pParent ){
      assert( pRoot->isInit==PAGE_ISINIT_FULL );
      pRoot = pRoot->pParent;
    }
    assert( pRoot->isInit==PAGE_ISINIT_FULL );
    if( pRoot!=pCur->pPage ){

      sqlite3PagerRef(pRoot->pDbPage);
      releasePage(pCur->pPage);
      pCur->pPage = pRoot;
    }
  }else{
    if( 
      SQLITE_OK!=(rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0))
    ){
      pCur->eState = CURSOR_INVALID;
      return rc;
    }
    releasePage(pCur->pPage);
    pCur->pPage = pRoot;
  }


  assert( pCur->pPage->pgno==pCur->pgnoRoot );
  pCur->idx = 0;

  pCur->info.nSize = 0;
  pCur->atLast = 0;
  pCur->validNKey = 0;

  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+8]);
    assert( subpage>0 );
    pCur->eState = CURSOR_VALID;
    rc = moveToChild(pCur, subpage);


  }
  pCur->eState = ((pCur->pPage->nCell>0)?CURSOR_VALID:CURSOR_INVALID);
  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
**
** The left-most leaf is the one with the smallest key - the first
** in ascending order.
*/
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    pgno = get4byte(findCell(pPage, pCur->idx));
    rc = moveToChild(pCur, pgno);
  }
  return rc;
}

/*
** Move the cursor down to the right-most leaf entry beneath the

static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    pCur->idx = pPage->nCell;
    rc = moveToChild(pCur, pgno);
  }
  if( rc==SQLITE_OK ){
    pCur->idx = pPage->nCell - 1;
    pCur->info.nSize = 0;
    pCur->validNKey = 0;
  }
  return rc;
}

/* Move the cursor to the first entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( pCur->eState==CURSOR_INVALID ){
      assert( pCur->pPage->nCell==0 );
      *pRes = 1;
      rc = SQLITE_OK;
    }else{
      assert( pCur->pPage->nCell>0 );
      *pRes = 0;
      rc = moveToLeftmost(pCur);
    }
  }
  return rc;
}

/* Move the cursor to the last entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeLast(BtCursor *pCur, int *pRes){
  int rc;
 
  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( CURSOR_INVALID==pCur->eState ){
      assert( pCur->pPage->nCell==0 );
      *pRes = 1;
    }else{
      assert( pCur->eState==CURSOR_VALID );
      *pRes = 0;
      rc = moveToRightmost(pCur);
      getCellInfo(pCur);
      pCur->atLast = rc==SQLITE_OK;

  int rc;

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );

  /* If the cursor is already positioned at the point we are trying
  ** to move to, then just return without doing any work */
  if( pCur->eState==CURSOR_VALID && pCur->validNKey && pCur->pPage->intKey ){


    if( pCur->info.nKey==intKey ){
      *pRes = 0;
      return SQLITE_OK;
    }
    if( pCur->atLast && pCur->info.nKey<intKey ){
      *pRes = -1;
      return SQLITE_OK;
    }
  }

  rc = moveToRoot(pCur);
  if( rc ){
    return rc;
  }
  assert( pCur->pPage );
  assert( pCur->pPage->isInit==PAGE_ISINIT_FULL );
  if( pCur->eState==CURSOR_INVALID ){
    *pRes = -1;
    assert( pCur->pPage->nCell==0 );
    return SQLITE_OK;
  }
  assert( pCur->pPage->intKey || pIdxKey );
  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
    if( !pPage->intKey && pIdxKey==0 ){
      rc = SQLITE_CORRUPT_BKPT;
      goto moveto_finish;
    }
    if( biasRight ){
      pCur->idx = upr;
    }else{
      pCur->idx = (upr+lwr)/2;
    }
    if( lwr<=upr ) for(;;){
      void *pCellKey;
      i64 nCellKey;

      pCur->info.nSize = 0;
      pCur->validNKey = 1;
      if( pPage->intKey ){
        u8 *pCell;
        pCell = findCell(pPage, pCur->idx) + pPage->childPtrSize;
        if( pPage->hasData ){
          u32 dummy;
          pCell += getVarint32(pCell, dummy);
        }
        getVarint(pCell, (u64*)&nCellKey);
        if( nCellKey==intKey ){
          c = 0;

          sqlite3_free(pCellKey);
          if( rc ) goto moveto_finish;
        }
      }
      if( c==0 ){
        pCur->info.nKey = nCellKey;
        if( pPage->intKey && !pPage->leaf ){
          lwr = pCur->idx;
          upr = lwr - 1;
          break;
        }else{
          if( pRes ) *pRes = 0;
          rc = SQLITE_OK;
          goto moveto_finish;
        }
      }
      if( c<0 ){
        lwr = pCur->idx+1;
      }else{
        upr = pCur->idx-1;
      }
      if( lwr>upr ){
        pCur->info.nKey = nCellKey;
        break;
      }
      pCur->idx = (lwr+upr)/2;
    }
    assert( lwr==upr+1 );
    assert( pPage->isInit==PAGE_ISINIT_FULL );
    if( pPage->leaf ){
      chldPg = 0;
    }else if( lwr>=pPage->nCell ){
      chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    }else{
      chldPg = get4byte(findCell(pPage, lwr));
    }
    if( chldPg==0 ){
      assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
      if( pRes ) *pRes = c;
      rc = SQLITE_OK;
      goto moveto_finish;
    }
    pCur->idx = lwr;
    pCur->info.nSize = 0;
    pCur->validNKey = 0;
    rc = moveToChild(pCur, chldPg);
    if( rc ) goto moveto_finish;
  }
moveto_finish:
  return rc;

** Advance the cursor to the next entry in the database.  If
** successful then set *pRes=0.  If the cursor
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  int rc;

  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreCursorPosition(pCur);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  assert( pRes!=0 );
  pPage = pCur->pPage;
  if( CURSOR_INVALID==pCur->eState ){
    *pRes = 1;
    return SQLITE_OK;
  }
  if( pCur->skip>0 ){
    pCur->skip = 0;
    *pRes = 0;
    return SQLITE_OK;
  }
  pCur->skip = 0;



  assert( pPage->isInit==PAGE_ISINIT_FULL );
  assert( pCur->idx<pPage->nCell );

  pCur->idx++;
  pCur->info.nSize = 0;
  pCur->validNKey = 0;
  if( pCur->idx>=pPage->nCell ){
    if( !pPage->leaf ){
      rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8]));
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      *pRes = 0;
      return rc;
    }
    do{
      if( sqlite3BtreeIsRootPage(pPage) ){
        *pRes = 1;
        pCur->eState = CURSOR_INVALID;
        return SQLITE_OK;
      }
      sqlite3BtreeMoveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;
    if( pPage->intKey ){
      rc = sqlite3BtreeNext(pCur, pRes);
    }else{
      rc = SQLITE_OK;
    }
    return rc;

** Step the cursor to the back to the previous entry in the database.  If
** successful then set *pRes=0.  If the cursor
** was already pointing to the first entry in the database before
** this routine was called, then set *pRes=1.
*/
int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreCursorPosition(pCur);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  pCur->atLast = 0;
  if( CURSOR_INVALID==pCur->eState ){
    *pRes = 1;
    return SQLITE_OK;
  }
  if( pCur->skip<0 ){
    pCur->skip = 0;
    *pRes = 0;
    return SQLITE_OK;
  }
  pCur->skip = 0;

  pPage = pCur->pPage;
  assert( pPage->isInit==PAGE_ISINIT_FULL );
  assert( pCur->idx>=0 );
  if( !pPage->leaf ){
    pgno = get4byte( findCell(pPage, pCur->idx) );
    rc = moveToChild(pCur, pgno);
    if( rc ){
      return rc;
    }
    rc = moveToRightmost(pCur);
  }else{
    while( pCur->idx==0 ){
      if( sqlite3BtreeIsRootPage(pPage) ){
        pCur->eState = CURSOR_INVALID;
        *pRes = 1;
        return SQLITE_OK;
      }
      sqlite3BtreeMoveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;
    pCur->info.nSize = 0;
    pCur->validNKey = 0;



    if( pPage->intKey && !pPage->leaf ){
      rc = sqlite3BtreePrevious(pCur, pRes);
    }else{
      rc = SQLITE_OK;
    }
  }
  *pRes = 0;

  }

  assert( *pPgno!=PENDING_BYTE_PAGE(pBt) );

end_allocate_page:
  releasePage(pTrunk);
  releasePage(pPrevTrunk);
  if( rc==SQLITE_OK ){
    if( (*ppPage)->isInit==PAGE_ISINIT_FULL ){
      releasePage(*ppPage);
      return SQLITE_CORRUPT_BKPT;
    }
    (*ppPage)->isInit = 0;
  }
  return rc;
}

/*
** Add a page of the database file to the freelist.
**
** sqlite3PagerUnref() is NOT called for pPage.
*/
static int freePage(MemPage *pPage){
  BtShared *pBt = pPage->pBt;
  MemPage *pPage1 = pBt->pPage1;
  int rc, n, k;

  /* Prepare the page for freeing */
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( pPage->pgno>1 );
  pPage->isInit = 0;
  releasePage(pPage->pParent);
  pPage->pParent = 0;

  /* Increment the free page count on pPage1 */
  rc = sqlite3PagerWrite(pPage1->pDbPage);
  if( rc ) return rc;
  n = get4byte(&pPage1->aData[36]);
  put4byte(&pPage1->aData[36], n+1);

static int reparentPage(
  BtShared *pBt,                /* B-Tree structure */
  Pgno pgno,                    /* Page number of child being adopted */
  MemPage *pNewParent,          /* New parent of pgno */
  int idx,                      /* Index of child page pgno in pNewParent */
  int updatePtrmap              /* If true, update pointer-map for pgno */
){
  MemPage *pThis;
  DbPage *pDbPage;

  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pNewParent!=0 );
  if( pgno==0 ) return SQLITE_OK;
  assert( pBt->pPager!=0 );
  pDbPage = sqlite3PagerLookup(pBt->pPager, pgno);
  if( pDbPage ){
    pThis = (MemPage *)sqlite3PagerGetExtra(pDbPage);
    if( pThis->isInit==PAGE_ISINIT_FULL ){
      assert( pThis->aData==sqlite3PagerGetData(pDbPage) );
      if( pThis->pParent!=pNewParent ){
        if( pThis->pParent ) sqlite3PagerUnref(pThis->pParent->pDbPage);
        pThis->pParent = pNewParent;
        sqlite3PagerRef(pNewParent->pDbPage);
      }
      pThis->idxParent = idx;
    }
    sqlite3PagerUnref(pDbPage);
  }

  if( ISAUTOVACUUM && updatePtrmap ){
    return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno);
  }

#ifndef NDEBUG
  /* If the updatePtrmap flag was clear, assert that the entry in the
  ** pointer-map is already correct.

** in exchange for a larger degradation in INSERT and UPDATE performance.
** The value of NN appears to give the best results overall.
*/
#define NN 1             /* Number of neighbors on either side of pPage */
#define NB (NN*2+1)      /* Total pages involved in the balance */

/* Forward reference */
static int balance(MemPage*, int);

#ifndef SQLITE_OMIT_QUICKBALANCE
/*
** This version of balance() handles the common special case where
** a new entry is being inserted on the extreme right-end of the
** tree, in other words, when the new entry will become the largest
** entry in the tree.
**
** Instead of trying balance the 3 right-most leaf pages, just add
** a new page to the right-hand side and put the one new entry in
** that page.  This leaves the right side of the tree somewhat
** unbalanced.  But odds are that we will be inserting new entries
** at the end soon afterwards so the nearly empty page will quickly
** fill up.  On average.
**
** pPage is the leaf page which is the right-most page in the tree.
** pParent is its parent.  pPage must have a single overflow entry
** which is also the right-most entry on the page.
*/
static int balance_quick(MemPage *pPage, MemPage *pParent){
  int rc;
  MemPage *pNew = 0;
  Pgno pgnoNew;
  u8 *pCell;
  u16 szCell;
  CellInfo info;


  BtShared *pBt = pPage->pBt;
  int parentIdx = pParent->nCell;   /* pParent new divider cell index */
  int parentSize;                   /* Size of new divider cell */
  u8 parentCell[64];                /* Space for the new divider cell */

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );

  /* Allocate a new page. Insert the overflow cell from pPage
  ** into it. Then remove the overflow cell from pPage.
  */
  rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0);
  if( rc==SQLITE_OK ){
    pCell = pPage->aOvfl[0].pCell;
    szCell = cellSizePtr(pPage, pCell);
    zeroPage(pNew, pPage->aData[0]);
    assemblePage(pNew, 1, &pCell, &szCell);
    pPage->nOverflow = 0;
  
    /* Set the parent of the newly allocated page to pParent. */

    pNew->pParent = pParent;
    sqlite3PagerRef(pParent->pDbPage);

  
    /* pPage is currently the right-child of pParent. Change this
    ** so that the right-child is the new page allocated above and
    ** pPage is the next-to-right child. 
    **
    ** Ignore the return value of the call to fillInCell(). fillInCell()
    ** may only return other than SQLITE_OK if it is required to allocate

  ** not important, as they will be recalculated when the page is rolled
  ** back. But here, in balance_quick(), it is possible that pPage has 
  ** not yet been marked dirty or written into the journal file. Therefore
  ** it will not be rolled back and so it is important to make sure that
  ** the page data and contents of MemPage are consistent.
  */
  pPage->isInit = 0;
  sqlite3BtreeInitPage(pPage, pPage->pParent);
  sqlite3PagerUnref(pPage->pParent->pDbPage);

  /* If everything else succeeded, balance the parent page, in 
  ** case the divider cell inserted caused it to become overfull.
  */
  if( rc==SQLITE_OK ){


    rc = balance(pParent, 0);
  }
  return rc;
}
#endif /* SQLITE_OMIT_QUICKBALANCE */

/*
** This routine redistributes Cells on pPage and up to NN*2 siblings

** might become overfull or underfull.  If that happens, then this routine
** is called recursively on the parent.
**
** If this routine fails for any reason, it might leave the database
** in a corrupted state.  So if this routine fails, the database should
** be rolled back.
*/
static int balance_nonroot(MemPage *pPage){

  MemPage *pParent;            /* The parent of pPage */
  BtShared *pBt;               /* The whole database */
  int nCell = 0;               /* Number of cells in apCell[] */
  int nMaxCells = 0;           /* Allocated size of apCell, szCell, aFrom. */
  int nOld;                    /* Number of pages in apOld[] */
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */

  u8 **apCell = 0;             /* All cells begin balanced */
  u16 *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];         /* Space for holding data of apCopy[] */
  u8 *aSpace1;           /* Space for copies of dividers cells before balance */
  u8 *aSpace2 = 0;       /* Space for overflow dividers cells after balance */
  u8 *aFrom = 0;


  assert( sqlite3_mutex_held(pPage->pBt->mutex) );

  /* 
  ** Find the parent page.
  */

  assert( pPage->isInit==PAGE_ISINIT_FULL );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  assert( pParent );
  if( SQLITE_OK!=(rc = sqlite3PagerWrite(pParent->pDbPage)) ){
    return rc;
  }

  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));

#ifndef SQLITE_OMIT_QUICKBALANCE
  /*
  ** A special case:  If a new entry has just been inserted into a
  ** table (that is, a btree with integer keys and all data at the leaves)
  ** and the new entry is the right-most entry in the tree (it has the
  ** largest key) then use the special balance_quick() routine for
  ** balancing.  balance_quick() is much faster and results in a tighter
  ** packing of data in the common case.
  */
  if( pPage->leaf &&
      pPage->intKey &&
      pPage->nOverflow==1 &&
      pPage->aOvfl[0].idx==pPage->nCell &&
      pPage->pParent->pgno!=1 &&
      get4byte(&pParent->aData[pParent->hdrOffset+8])==pPage->pgno
  ){
    assert( pPage->intKey );
    /*
    ** TODO: Check the siblings to the left of pPage. It may be that
    ** they are not full and no new page is required.
    */
    return balance_quick(pPage, pParent);
  }
#endif

  if( SQLITE_OK!=(rc = sqlite3PagerWrite(pPage->pDbPage)) ){
    return rc;
  }

      if( get4byte(findCell(pParent, idx))==pgno ){
        break;
      }
    }
    assert( idx<pParent->nCell
             || get4byte(&pParent->aData[pParent->hdrOffset+8])==pgno );
  }else{
    idx = pPage->idxParent;
  }

  /*
  ** Initialize variables so that it will be safe to jump
  ** directly to balance_cleanup at any moment.
  */
  nOld = nNew = 0;
  sqlite3PagerRef(pParent->pDbPage);

  /*
  ** Find sibling pages to pPage and the cells in pParent that divide
  ** the siblings.  An attempt is made to find NN siblings on either
  ** side of pPage.  More siblings are taken from one side, however, if
  ** pPage there are fewer than NN siblings on the other side.  If pParent
  ** has NB or fewer children then all children of pParent are taken.

      assert( !pParent->leaf );
      pgnoOld[i] = get4byte(apDiv[i]);
    }else if( k==pParent->nCell ){
      pgnoOld[i] = get4byte(&pParent->aData[pParent->hdrOffset+8]);
    }else{
      break;
    }
    rc = getAndInitPage(pBt, pgnoOld[i], &apOld[i], pParent);
    if( rc ) goto balance_cleanup;
    apOld[i]->idxParent = k;
    apCopy[i] = 0;
    assert( i==nOld );
    nOld++;
    nMaxCells += 1+apOld[i]->nCell+apOld[i]->nOverflow;
  }

  /* Make nMaxCells a multiple of 4 in order to preserve 8-byte

#endif

  /*
  ** Balance the parent page.  Note that the current page (pPage) might
  ** have been added to the freelist so it might no longer be initialized.
  ** But the parent page will always be initialized.
  */
  assert( pParent->isInit==PAGE_ISINIT_FULL );
  sqlite3ScratchFree(apCell);
  apCell = 0;


  rc = balance(pParent, 0);
  
  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  sqlite3PageFree(aSpace2);
  sqlite3ScratchFree(apCell);
  for(i=0; i<nOld; i++){
    releasePage(apOld[i]);
  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }

  releasePage(pParent);
  TRACE(("BALANCE: finished with %d: old=%d new=%d cells=%d\n",
          pPage->pgno, nOld, nNew, nCell));

  return rc;
}

/*
** This routine is called for the root page of a btree when the root
** page contains no cells.  This is an opportunity to make the tree
** shallower by one level.
*/
static int balance_shallower(MemPage *pPage){

  MemPage *pChild;             /* The only child page of pPage */
  Pgno pgnoChild;              /* Page number for pChild */
  int rc = SQLITE_OK;          /* Return code from subprocedures */
  BtShared *pBt;                  /* The main BTree structure */
  int mxCellPerPage;           /* Maximum number of cells per page */
  u8 **apCell;                 /* All cells from pages being balanced */
  u16 *szCell;                 /* Local size of all cells */

  assert( pPage->pParent==0 );


  assert( pPage->nCell==0 );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  pBt = pPage->pBt;
  mxCellPerPage = MX_CELL(pBt);
  apCell = sqlite3Malloc( mxCellPerPage*(sizeof(u8*)+sizeof(u16)) );
  if( apCell==0 ) return SQLITE_NOMEM;
  szCell = (u16*)&apCell[mxCellPerPage];

    */
    pgnoChild = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    assert( pgnoChild>0 );
    assert( pgnoChild<=pagerPagecount(pPage->pBt->pPager) );
    rc = sqlite3BtreeGetPage(pPage->pBt, pgnoChild, &pChild, 0);
    if( rc ) goto end_shallow_balance;
    if( pPage->pgno==1 ){
      rc = sqlite3BtreeInitPage(pChild, pPage);
      if( rc ) goto end_shallow_balance;
      assert( pChild->nOverflow==0 );
      if( pChild->nFree>=100 ){
        /* The child information will fit on the root page, so do the
        ** copy */
        int i;
        zeroPage(pPage, pChild->aData[0]);

        /* The child has more information that will fit on the root.
        ** The tree is already balanced.  Do nothing. */
        TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
      }
    }else{
      memcpy(pPage->aData, pChild->aData, pPage->pBt->usableSize);
      pPage->isInit = 0;
      pPage->pParent = 0;
      rc = sqlite3BtreeInitPage(pPage, 0);
      assert( rc==SQLITE_OK );
      freePage(pChild);
      TRACE(("BALANCE: transfer child %d into root %d\n",
              pChild->pgno, pPage->pgno));
    }
    rc = reparentChildPages(pPage, 1);
    assert( pPage->nOverflow==0 );

**
** When this happens, Create a new child page and copy the
** contents of the root into the child.  Then make the root
** page an empty page with rightChild pointing to the new
** child.   Finally, call balance_internal() on the new child
** to cause it to split.
*/
static int balance_deeper(MemPage *pPage){
  int rc;             /* Return value from subprocedures */

  MemPage *pChild;    /* Pointer to a new child page */
  Pgno pgnoChild;     /* Page number of the new child page */
  BtShared *pBt;         /* The BTree */
  int usableSize;     /* Total usable size of a page */
  u8 *data;           /* Content of the parent page */
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int cbrk;           /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );


  pBt = pPage->pBt;
  assert( sqlite3_mutex_held(pBt->mutex) );
  rc = allocateBtreePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3PagerIswriteable(pChild->pDbPage) );
  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  cbrk = get2byte(&data[hdr+5]);
  cdata = pChild->aData;
  memcpy(cdata, &data[hdr], pPage->cellOffset+2*pPage->nCell-hdr);
  memcpy(&cdata[cbrk], &data[cbrk], usableSize-cbrk);
  if( pChild->isInit==PAGE_ISINIT_FULL ) return SQLITE_CORRUPT;
  rc = sqlite3BtreeInitPage(pChild, pPage);
  if( rc ) goto balancedeeper_out;

  memcpy(pChild->aOvfl, pPage->aOvfl, pPage->nOverflow*sizeof(pPage->aOvfl[0]));
  pChild->nOverflow = pPage->nOverflow;
  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }
  assert( pChild->nCell==pPage->nCell );
  zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));
  if( ISAUTOVACUUM ){
    int i;
    rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
    if( rc ) goto balancedeeper_out;
    for(i=0; i<pChild->nCell; i++){
      rc = ptrmapPutOvfl(pChild, i);

      if( rc!=SQLITE_OK ){
        goto balancedeeper_out;

      }
    }
    rc = reparentChildPages(pChild, 1);
  }

  if( rc==SQLITE_OK ){


    rc = balance_nonroot(pChild);


  }

balancedeeper_out:
  releasePage(pChild);
  return rc;
}

/*


** Decide if the page pPage needs to be balanced.  If balancing is
** required, call the appropriate balancing routine.



*/
static int balance(MemPage *pPage, int insert){
  int rc = SQLITE_OK;


  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( pPage->pParent==0 ){
    rc = sqlite3PagerWrite(pPage->pDbPage);
    if( rc==SQLITE_OK && pPage->nOverflow>0 ){
      rc = balance_deeper(pPage);
    }
    if( rc==SQLITE_OK && pPage->nCell==0 ){
      rc = balance_shallower(pPage);
    }
  }else{
    if( pPage->nOverflow>0 || 
        (!insert && pPage->nFree>pPage->pBt->usableSize*2/3) ){
      rc = balance_nonroot(pPage);
    }
  }
  return rc;
}

/*
** This routine checks all cursors that point to table pgnoRoot.

  const void *pData, int nData,  /* The data of the new record */
  int nZero,                     /* Number of extra 0 bytes to append to data */
  int appendBias                 /* True if this is likely an append */
){
  int rc;
  int loc;
  int szNew;

  MemPage *pPage;
  Btree *p = pCur->pBtree;
  BtShared *pBt = p->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;

  assert( cursorHoldsMutex(pCur) );

  if( 
    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||
    SQLITE_OK!=(rc = sqlite3BtreeMoveto(pCur, pKey, nKey, appendBias, &loc))
  ){
    return rc;
  }

  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->intKey );
  TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
          pCur->pgnoRoot, nKey, nData, pPage->pgno,
          loc==0 ? "overwrite" : "new entry"));
  assert( pPage->isInit==PAGE_ISINIT_FULL );
  allocateTempSpace(pBt);
  newCell = pBt->pTmpSpace;
  if( newCell==0 ) return SQLITE_NOMEM;
  rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, nZero, &szNew);
  if( rc ) goto end_insert;
  assert( szNew==cellSizePtr(pPage, newCell) );
  assert( szNew<=MX_CELL_SIZE(pBt) );

  if( loc==0 && CURSOR_VALID==pCur->eState ){
    u16 szOld;
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    rc = sqlite3PagerWrite(pPage->pDbPage);
    if( rc ){
      goto end_insert;
    }
    oldCell = findCell(pPage, pCur->idx);
    if( !pPage->leaf ){
      memcpy(newCell, oldCell, 4);
    }
    szOld = cellSizePtr(pPage, oldCell);
    rc = clearCell(pPage, oldCell);
    if( rc ) goto end_insert;
    dropCell(pPage, pCur->idx, szOld);
  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->leaf );
    pCur->idx++;
    pCur->info.nSize = 0;
    pCur->validNKey = 0;
  }else{
    assert( pPage->leaf );
  }
  rc = insertCell(pPage, pCur->idx, newCell, szNew, 0, 0);
  if( rc!=SQLITE_OK ) goto end_insert;
  rc = balance(pPage, 1);
  if( rc==SQLITE_OK ){
    /* balance() may have messed up the chain of MemPage.pParent pointers.
    ** To prevent moveToRoot() from trying to use them to locate the root
    ** page of this table, release the reference to the current page before
    ** calling it.
    */
    releasePage(pCur->pPage);
    pCur->pPage = 0;
    moveToRoot(pCur);
  }
end_insert:
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
** is left pointing at a random location.
*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->pPage;

  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  Btree *p = pCur->pBtree;
  BtShared *pBt = p->pBt;

  assert( cursorHoldsMutex(pCur) );
  assert( pPage->isInit==PAGE_ISINIT_FULL );
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
    return rc;
  }
  assert( !pBt->readOnly );
  if( pCur->eState==CURSOR_FAULT ){
    return pCur->skip;
  }
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  if( !pCur->wrFlag ){
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur, pCur->info.nKey) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */

    return rc;
  }

  /* Locate the cell within its page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.
  */

  pCell = findCell(pPage, pCur->idx);
  if( !pPage->leaf ){
    pgnoChild = get4byte(pCell);
  }
  rc = clearCell(pPage, pCell);
  if( rc ){
    return rc;
  }

  if( !pPage->leaf ){
    /*
    ** The entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;



    unsigned char *pNext;
    int notUsed;
    unsigned char *tempCell = 0;
    assert( !pPage->intKey );
    sqlite3BtreeGetTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc==SQLITE_OK ){


      rc = sqlite3PagerWrite(leafCur.pPage->pDbPage);
    }
    if( rc==SQLITE_OK ){
      u16 szNext;
      TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
         pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
      dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
      pNext = findCell(leafCur.pPage, leafCur.idx);
      szNext = cellSizePtr(leafCur.pPage, pNext);
      assert( MX_CELL_SIZE(pBt)>=szNext+4 );
      allocateTempSpace(pBt);
      tempCell = pBt->pTmpSpace;
      if( tempCell==0 ){
        rc = SQLITE_NOMEM;
      }
      if( rc==SQLITE_OK ){
        rc = insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell, 0);
      }
      if( rc==SQLITE_OK ){
        put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
        rc = balance(pPage, 0);
      }
      if( rc==SQLITE_OK ){
        dropCell(leafCur.pPage, leafCur.idx, szNext);
        rc = balance(leafCur.pPage, 0);
      }
    }
    sqlite3BtreeReleaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    rc = balance(pPage, 0);
  }
  if( rc==SQLITE_OK ){
    /* balance() may have messed up the chain of MemPage.pParent pointers.
    ** To prevent moveToRoot() from trying to use them to locate the root
    ** page of this table, release the reference to the current page before
    ** calling it.
    */
    releasePage(pCur->pPage);
    pCur->pPage = 0;
    moveToRoot(pCur);
  }
  return rc;
}

/*
** Create a new BTree table.  Write into *piTable the page

  int i;

  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pgno>pagerPagecount(pBt->pPager) ){
    return SQLITE_CORRUPT_BKPT;
  }

  rc = getAndInitPage(pBt, pgno, &pPage, pParent);
  if( rc ) goto cleardatabasepage_out;
  for(i=0; i<pPage->nCell; i++){
    pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = clearDatabasePage(pBt, get4byte(pCell), pPage, 1);
      if( rc ) goto cleardatabasepage_out;
    }

*/
int sqlite3BtreeFlags(BtCursor *pCur){
  /* TODO: What about CURSOR_REQUIRESEEK state? Probably need to call
  ** restoreCursorPosition() here.
  */
  MemPage *pPage;
  restoreCursorPosition(pCur);
  pPage = pCur->pPage;
  assert( cursorHoldsMutex(pCur) );
  assert( pPage->pBt==pCur->pBt );
  return pPage ? pPage->aData[pPage->hdrOffset] : 0;
}


/*

  if( iPage==0 ) return 0;
  if( checkRef(pCheck, iPage, zParentContext) ) return 0;
  if( (rc = sqlite3BtreeGetPage(pBt, (Pgno)iPage, &pPage, 0))!=0 ){
    checkAppendMsg(pCheck, zContext,
       "unable to get the page. error code=%d", rc);
    return 0;
  }
  if( (rc = sqlite3BtreeInitPage(pPage, pParent))!=0 ){
    checkAppendMsg(pCheck, zContext, 
                   "sqlite3BtreeInitPage() returns error code %d", rc);
    releasePage(pPage);
    return 0;
  }

  /* Check out all the cells.

    return SQLITE_READONLY;
  }
  assert( !pCsr->pBt->readOnly 
          && pCsr->pBt->inTransaction==TRANS_WRITE );
  if( checkReadLocks(pCsr->pBtree, pCsr->pgnoRoot, pCsr, 0) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  if( pCsr->eState==CURSOR_INVALID || !pCsr->pPage->intKey ){
    return SQLITE_ERROR;
  }

  return accessPayload(pCsr, offset, amt, (unsigned char *)z, 0, 1);
}

/* 

/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btreeInt.h,v 1.31 2008/09/18 17:34:44 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.

  u8 leaf;             /* True if leaf flag is set */
  u8 hasData;          /* True if this page stores data */
  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
  u16 maxLocal;        /* Copy of BtShared.maxLocal or BtShared.maxLeaf */
  u16 minLocal;        /* Copy of BtShared.minLocal or BtShared.minLeaf */
  u16 cellOffset;      /* Index in aData of first cell pointer */
  u16 idxParent;       /* Index in parent of this node */
  u16 nFree;           /* Number of free bytes on the page */
  u16 nCell;           /* Number of cells on this page, local and ovfl */
  u16 maskPage;        /* Mask for page offset */
  struct _OvflCell {   /* Cells that will not fit on aData[] */
    u8 *pCell;          /* Pointers to the body of the overflow cell */
    u16 idx;            /* Insert this cell before idx-th non-overflow cell */
  } aOvfl[5];
  BtShared *pBt;       /* Pointer to BtShared that this page is part of */
  u8 *aData;           /* Pointer to disk image of the page data */
  DbPage *pDbPage;     /* Pager page handle */
  Pgno pgno;           /* Page number for this page */
  MemPage *pParent;    /* The parent of this page.  NULL for root */
};

/*
** Possible values for the MemPage.isInit variable. When a page is first
** loaded or if the data stored in the MemPage struct is invalidated, 
** MemPage.isInit is set to PAGE_ISINIT_NONE. If the MemPage structure
** is fully initialized, then MemPage.isInit is set to PAGE_ISINIT_FULL.
** MemPage.isInit is set to PAGE_ISINIT_DATA when the MemPage struct is
** populated, but the MemPage.pParent variable is not necessarily correct.
*/
#define PAGE_ISINIT_NONE 0
#define PAGE_ISINIT_DATA 1
#define PAGE_ISINIT_FULL 2

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
*/
#define EXTRA_SIZE sizeof(MemPage)

  u32 nPayload;  /* Total amount of payload */
  u16 nHeader;   /* Size of the cell content header in bytes */
  u16 nLocal;    /* Amount of payload held locally */
  u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */
  u16 nSize;     /* Size of the cell content on the main b-tree page */
};












/*
** A cursor is a pointer to a particular entry within a particular
** b-tree within a database file.
**
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
**
** When a single database file can shared by two more database connections,
** but cursors cannot be shared.  Each cursor is associated with a
** particular database connection identified BtCursor.pBtree.db.
**
** Fields in this structure are accessed under the BtShared.mutex
** found at self->pBt->mutex. 
*/
struct BtCursor {
  Btree *pBtree;            /* The Btree to which this cursor belongs */
  BtShared *pBt;            /* The BtShared this cursor points to */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  struct KeyInfo *pKeyInfo; /* Argument passed to comparison function */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 atLast;                /* Cursor pointing to the last entry */
  u8 validNKey;             /* True if info.nKey is valid */
  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
  void *pKey;      /* Saved key that was cursor's last known position */
  i64 nKey;        /* Size of pKey, or last integer key */
  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
#ifndef SQLITE_OMIT_INCRBLOB
  u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
  Pgno *aOverflow;          /* Cache of overflow page locations */
#endif




};

/*
** Potential values for BtCursor.eState.
**
** CURSOR_VALID:
**   Cursor points to a valid entry. getPayload() etc. may be called.

#define get4byte sqlite3Get4byte
#define put4byte sqlite3Put4byte

/*
** Internal routines that should be accessed by the btree layer only.
*/
int sqlite3BtreeGetPage(BtShared*, Pgno, MemPage**, int);
int sqlite3BtreeInitPage(MemPage *pPage, MemPage *pParent);
void sqlite3BtreeParseCellPtr(MemPage*, u8*, CellInfo*);
void sqlite3BtreeParseCell(MemPage*, int, CellInfo*);
int sqlite3BtreeRestoreCursorPosition(BtCursor *pCur);
void sqlite3BtreeGetTempCursor(BtCursor *pCur, BtCursor *pTempCur);
void sqlite3BtreeReleaseTempCursor(BtCursor *pCur);
int sqlite3BtreeIsRootPage(MemPage *pPage);
void sqlite3BtreeMoveToParent(BtCursor *pCur);

** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.495 2008/09/26 21:08:08 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"

/*
** Macros for troubleshooting.  Normally turned off
*/

** It is never written to disk.  This can be used to implement an
** in-memory database.
*/
int sqlite3PagerOpen(
  sqlite3_vfs *pVfs,       /* The virtual file system to use */
  Pager **ppPager,         /* Return the Pager structure here */
  const char *zFilename,   /* Name of the database file to open */
  void (*xDesc)(DbPage*),  /* Page destructor function */
  int nExtra,              /* Extra bytes append to each in-memory page */
  int flags,               /* flags controlling this file */
  int vfsFlags             /* flags passed through to sqlite3_vfs.xOpen() */
){
  u8 *pPtr;
  Pager *pPager = 0;
  int rc = SQLITE_OK;

  */
  if( !pPager || !pPager->pTmpSpace ){
    sqlite3OsClose(pPager->fd);
    sqlite3_free(pPager);
    return ((rc==SQLITE_OK)?SQLITE_NOMEM:rc);
  }
  nExtra = FORCE_ALIGNMENT(nExtra);
  sqlite3PcacheOpen(szPageDflt, nExtra, !memDb, xDesc, 
                    !memDb?pagerStress:0, (void *)pPager, pPager->pPCache);

  PAGERTRACE3("OPEN %d %s\n", FILEHANDLEID(pPager->fd), pPager->zFilename);
  IOTRACE(("OPEN %p %s\n", pPager, pPager->zFilename))

  /* Fill in Pager.zDirectory[] */
  memcpy(pPager->zDirectory, pPager->zFilename, nPathname+1);

/*
** Return the number of references to the pager.
*/
int sqlite3PagerRefcount(Pager *pPager){
  return sqlite3PcacheRefCount(pPager->pPCache);
}








#ifdef SQLITE_TEST
/*
** This routine is used for testing and analysis only.
*/
int *sqlite3PagerStats(Pager *pPager){
  static int a[11];

}
#endif

/*
** Return a pointer to the data for the specified page.
*/
void *sqlite3PagerGetData(DbPage *pPg){
  assert( pPg->nRef>0 );
  return pPg->pData;
}

/*
** Return a pointer to the Pager.nExtra bytes of "extra" space 
** allocated along with the specified page.
*/

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite page cache
** subsystem.  The page cache subsystem reads and writes a file a page
** at a time and provides a journal for rollback.
**
** @(#) $Id: pager.h,v 1.84 2008/09/26 21:08:08 drh Exp $
*/

#ifndef _PAGER_H_
#define _PAGER_H_

/*
** If defined as non-zero, auto-vacuum is enabled by default. Otherwise

#define PAGER_JOURNALMODE_OFF         2   /* Journal omitted.  */
#define PAGER_JOURNALMODE_TRUNCATE    3   /* Commit by truncating journal */

/*
** See source code comments for a detailed description of the following
** routines:
*/
int sqlite3PagerOpen(sqlite3_vfs *, Pager **ppPager, const char*, void(*)(DbPage*), int,int,int);
void sqlite3PagerSetBusyhandler(Pager*, BusyHandler *pBusyHandler);
void sqlite3PagerSetReiniter(Pager*, void(*)(DbPage*));
int sqlite3PagerSetPagesize(Pager*, u16*);
int sqlite3PagerMaxPageCount(Pager*, int);
int sqlite3PagerReadFileheader(Pager*, int, unsigned char*);
void sqlite3PagerSetCachesize(Pager*, int);
int sqlite3PagerClose(Pager *pPager);
int sqlite3PagerAcquire(Pager *pPager, Pgno pgno, DbPage **ppPage, int clrFlag);
#define sqlite3PagerGet(A,B,C) sqlite3PagerAcquire(A,B,C,0)
DbPage *sqlite3PagerLookup(Pager *pPager, Pgno pgno);

int sqlite3PagerRef(DbPage*);
int sqlite3PagerUnref(DbPage*);
int sqlite3PagerWrite(DbPage*);
int sqlite3PagerPagecount(Pager*, int*);
int sqlite3PagerTruncate(Pager*,Pgno);
int sqlite3PagerBegin(DbPage*, int exFlag);
int sqlite3PagerCommitPhaseOne(Pager*,const char *zMaster, Pgno, int);

/*
** 2008 August 05
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file implements that page cache.
**
** @(#) $Id: pcache.c,v 1.32 2008/09/24 09:12:47 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
**
** A cache may only be deleted by its owner and while holding the

  ** the cache owner or by any thread holding the the mutex.  Non-owner
  ** threads must hold the mutex when reading these elements to prevent
  ** the entire PCache object from being deleted during the read.
  */
  int szPage;                         /* Size of every page in this cache */
  int szExtra;                        /* Size of extra space for each page */
  int bPurgeable;                     /* True if pages are on backing store */
  void (*xDestroy)(PgHdr*);           /* Called when refcnt goes 1->0 */
  int (*xStress)(void*,PgHdr*);       /* Call to try make a page clean */
  void *pStress;                      /* Argument to xStress */
  /**********************************************************************
  ** The final group of elements can only be accessed while holding the
  ** mutex.  Both the cache owner and any other thread must hold the mutex
  ** to read or write any of these elements.
  */

** Create a new PCache object.  Storage space to hold the object
** has already been allocated and is passed in as the p pointer.
*/
void sqlite3PcacheOpen(
  int szPage,                  /* Size of every page */
  int szExtra,                 /* Extra space associated with each page */
  int bPurgeable,              /* True if pages are on backing store */
  void (*xDestroy)(PgHdr*),    /* Called to destroy a page */
  int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
  void *pStress,               /* Argument to xStress */
  PCache *p                    /* Preallocated space for the PCache */
){
  assert( pcache_g.isInit );
  memset(p, 0, sizeof(PCache));
  p->szPage = szPage;
  p->szExtra = szExtra;
  p->bPurgeable = bPurgeable;
  p->xDestroy = xDestroy;
  p->xStress = xStress;
  p->pStress = pStress;
  p->nMax = 100;
  p->nMin = 10;

  pcacheEnterMutex();
  if( bPurgeable ){

** move the page to the LRU list if it is clean.
*/
void sqlite3PcacheRelease(PgHdr *p){
  assert( p->nRef>0 );
  p->nRef--;
  if( p->nRef==0 ){
    PCache *pCache = p->pCache;
    if( p->pCache->xDestroy ){
      p->pCache->xDestroy(p);
    }
    pCache->nRef--;
    if( (p->flags&PGHDR_DIRTY)==0 ){
      pCache->nPinned--;
      pcacheEnterMutex();
      if( pcache_g.nCurrentPage>pcache_g.nMaxPage ){
        pcacheRemoveFromList(&pCache->pClean, p);
        pcacheRemoveFromHash(p);

/* 
** Return the total number of outstanding page references.
*/
int sqlite3PcacheRefCount(PCache *pCache){
  return pCache->nRef;
}





/* 
** Return the total number of pages in the cache.
*/
int sqlite3PcachePagecount(PCache *pCache){
  assert( pCache->nPage>=0 );
  return pCache->nPage;

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite page cache
** subsystem. 
**
** @(#) $Id: pcache.h,v 1.11 2008/09/18 17:34:44 danielk1977 Exp $
*/

#ifndef _PCACHE_H_

typedef struct PgHdr PgHdr;
typedef struct PCache PCache;

** Under memory stress, invoke xStress to try to make pages clean.
** Only clean and unpinned pages can be reclaimed.
*/
void sqlite3PcacheOpen(
  int szPage,                    /* Size of every page */
  int szExtra,                   /* Extra space associated with each page */
  int bPurgeable,                /* True if pages are on backing store */
  void (*xDestroy)(PgHdr *),     /* Called to destroy a page */
  int (*xStress)(void*, PgHdr*), /* Call to try to make pages clean */
  void *pStress,                 /* Argument to xStress */
  PCache *pToInit                /* Preallocated space for the PCache */
);

/* Modify the page-size after the cache has been created. */
void sqlite3PcacheSetPageSize(PCache *, int);

int sqlite3PcacheClear(PCache*);

/* Return the total number of outstanding page references */
int sqlite3PcacheRefCount(PCache*);

/* Increment the reference count of an existing page */
void sqlite3PcacheRef(PgHdr*);



/* Return the total number of pages stored in the cache */
int sqlite3PcachePagecount(PCache*);

/* Iterate through all pages currently stored in the cache. This interface
** is only available if SQLITE_CHECK_PAGES is defined when the library is 
** built.

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the pager.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test2.c,v 1.61 2008/08/26 18:05:48 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

  char zBuf[100];
  if( argc!=3 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " FILENAME N-PAGE\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[2], &nPage) ) return TCL_ERROR;
  rc = sqlite3PagerOpen(sqlite3_vfs_find(0), &pPager, argv[1], 0, 0, 0,
      SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_MAIN_DB);
  if( rc!=SQLITE_OK ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sqlite3PagerSetCachesize(pPager, nPage);
  pageSize = test_pagesize;

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test_btree.c,v 1.7 2008/09/02 00:52:52 drh Exp $
*/
#include "btreeInt.h"
#include <tcl.h>

/*
** Usage: sqlite3_shared_cache_report
**

** Print debugging information about all cursors to standard output.
*/
void sqlite3BtreeCursorList(Btree *p){
#ifdef SQLITE_DEBUG
  BtCursor *pCur;
  BtShared *pBt = p->pBt;
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    MemPage *pPage = pCur->pPage;
    char *zMode = pCur->wrFlag ? "rw" : "ro";
    sqlite3DebugPrintf("CURSOR %p rooted at %4d(%s) currently at %d.%d%s\n",
       pCur, pCur->pgnoRoot, zMode,
       pPage ? pPage->pgno : 0, pCur->idx,
       (pCur->eState==CURSOR_VALID) ? "" : " eof"
    );
  }
#endif
}

**   aResult[8] =  Local payload size
**   aResult[9] =  Parent page number
**   aResult[10]=  Page number of the first overflow page
**
** This routine is used for testing and debugging only.
*/
int sqlite3BtreeCursorInfo(BtCursor *pCur, int *aResult, int upCnt){

  int cnt, idx;
  MemPage *pPage = pCur->pPage;
  BtCursor tmpCur;
  int rc;

  if( pCur->eState==CURSOR_REQUIRESEEK ){
    rc = sqlite3BtreeRestoreCursorPosition(pCur);
    if( rc!=SQLITE_OK ){
      return rc;

  }
  if( tmpCur.info.iOverflow ){
    aResult[10] = get4byte(&tmpCur.info.pCell[tmpCur.info.iOverflow]);
  }else{
    aResult[10] = 0;
  }
  sqlite3BtreeReleaseTempCursor(&tmpCur);

  return SQLITE_OK;
}

#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests to make sure SQLite does not crash or
# segfault if it sees a corrupt database file.
#
# $Id: corrupt2.test,v 1.17 2008/09/10 11:28:38 danielk1977 Exp $

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

# The following tests - corrupt2-1.* - create some databases corrupted in
# specific ways and ensure that SQLite detects them as corrupt.
#

  sqlite3 db2 corrupt.db 
  db2 eval {SELECT rowid FROM t1} {
    set result [db2 eval {pragma integrity_check}]
    break
  }
  set result
} {{*** in database main ***
Page 10: sqlite3BtreeInitPage() returns error code 11
On tree page 3 cell 1: Child page depth differs
On tree page 2 cell 0: 2nd reference to page 10
On tree page 2 cell 1: Child page depth differs
Page 4 is never used}}

db2 close

proc corruption_test {args} {