** 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.115 2004/05/08 10:56:11 drh 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.
................................................................................
** The pParent field points back to the parent page.  This allows us to
** walk up the BTree from any leaf to the root.  Care must be taken to
** unref() the parent page pointer when this page is no longer referenced.
** The pageDestructor() routine handles that chore.
*/
struct MemPage {
  u32 notUsed;
  struct Btree *pBt;             /* Pointer back to BTree structure */
  unsigned char *aData;          /* Pointer back to the start of the page */
  u8 isInit;                     /* True if previously initialized */
  u8 idxShift;                   /* True if Cell indices have changed */
  u8 isOverfull;                 /* Some aCell[] do not fit on page */
  u8 intKey;                     /* True if intkey flag is set */
  u8 leaf;                       /* True if leaf flag is set */
  u8 zeroData;                   /* True if zero data flag is set */
  u8 hdrOffset;                  /* 100 for page 1.  0 otherwise */
  Pgno pgno;                     /* Page number for this page */
  MemPage *pParent;              /* The parent of this page.  NULL for root */
  int idxParent;                 /* Index in pParent->aCell[] of this node */
  int nFree;                     /* Number of free bytes on the page */
  int nCell;                     /* Number of entries on this page */
  int nCellAlloc;                /* Number of slots allocated in aCell[] */
  unsigned char **aCell;         /* Pointer to start of each cell */





};

/*
** 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.
*/
................................................................................
  int pageSize;
  int sumCell = 0;       /* Total size of all cells */

  assert( pPage->pBt!=0 );
  assert( pParent==0 || pParent->pBt==pPage->pBt );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] );
  assert( pPage->isInit==0 || pPage->pParent==pParent );
  if( pPage->isInit ) return SQLITE_OK;
  assert( pPage->pParent==0 );
  pPage->pParent = pParent;
  if( pParent ){
    sqlite3pager_ref(pParent->aData);
  }

  pPage->nCell = pPage->nCellAlloc = 0;
  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & PTF_INTKEY)!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leaf = (c & PTF_LEAF)!=0;


  pageSize = pPage->pBt->pageSize;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
  while( pc>0 ){
    if( pc>=pageSize ) return SQLITE_CORRUPT;
    if( pPage->nCell>pageSize ) return SQLITE_CORRUPT;
................................................................................
*/
static void zeroPage(MemPage *pPage, int flags){
  unsigned char *data = pPage->aData;
  Btree *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;



  assert( sqlite3pager_iswriteable(data) );
  memset(&data[hdr], 0, pBt->pageSize - hdr);
  data[hdr] = flags;
  first = hdr + 6 + 4*((flags&PTF_LEAF)==0);
  put2byte(&data[hdr+1], first);
  put2byte(&data[first+2], pBt->pageSize - first);
  sqliteFree(pPage->aCell);
................................................................................
  pPage->nCell = 0;
  pPage->nCellAlloc = 0;
  pPage->nFree = pBt->pageSize - first;
  pPage->intKey = (flags & PTF_INTKEY)!=0;
  pPage->leaf = (flags & PTF_LEAF)!=0;
  pPage->zeroData = (flags & PTF_ZERODATA)!=0;
  pPage->hdrOffset = hdr;



}

/*
** Get a page from the pager.  Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){
................................................................................
      releasePage(pPage);
      pCur->pPage = 0;
      pCur->isValid = 0;
      pCur->status = SQLITE_ABORT;
    }
  }
}



















/*
** Rollback the transaction in progress.  All cursors will be
** invalided by this operation.  Any attempt to use a cursor
** that was open at the beginning of this operation will result
** in an error.
**
................................................................................
** 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.
*/
static int isRootPage(MemPage *pPage){
  MemPage *pParent = pPage->pParent;
  assert( pParent==0 || pParent->isInit );
  if( pParent==0 || (pParent->pgno==1 && pParent->nCell==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
................................................................................
    assert( idx>pPage->hdrOffset && idx<pPage->pBt->pageSize );
    put2byte(&pPage->aData[idxFrom], idx);
    idxFrom = idx;
  }
  put2byte(&pPage->aData[idxFrom], 0);
}









/*
** Move the content of the page at pFrom over to pTo.  The pFrom->aCell[]
** pointers that point into pFrom->aData[] must be adjusted to point
** into pTo->aData[] instead.  But some pFrom->aCell[] entries might
** not point to pFrom->aData[].  Those are unchanged.
**
** Over this operation completes, the meta data for pFrom is zeroed.
*/
static void copyPage(MemPage *pTo, MemPage *pFrom){
  uptr from, to;
  int i;
  int pageSize;
  int ofst;

  assert( pTo->hdrOffset==0 );
  ofst = pFrom->hdrOffset;
  pageSize = pTo->pBt->pageSize;
  sqliteFree(pTo->aCell);
  memcpy(pTo->aData, &pFrom->aData[ofst], pageSize - ofst + sizeof(MemPage));
  memset(pFrom, 0, sizeof(MemPage));


  assert( pTo->aData[5]<155 );
  pTo->aData[5] += ofst;
  pTo->isOverfull = pFrom->isOverfull;
  to = Addr(pTo->aData);
  from = Addr(&pFrom->aData[ofst]);
  for(i=0; i<pTo->nCell; i++){
    uptr x = Addr(pTo->aCell[i]);
................................................................................
  int idx;                     /* Index of pPage in pParent->aCell[] */
  int nxDiv;                   /* Next divider slot in pParent->aCell[] */
  int rc;                      /* The return code */
  int leafCorrection;          /* 4 if pPage is a leaf.  0 if not */
  int usableSpace;             /* Bytes in pPage beyond the header */
  int pageFlags;               /* Value of pPage->aData[0] */
  int subtotal;                /* Subtotal of bytes in cells on one page */

  MemPage *apOld[NB];          /* pPage and up to two siblings */
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  MemPage *apNew[NB+1];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+1];          /* Page numbers for each page in apNew[] */
  int idxDiv[NB];              /* Indices of divider cells in pParent */
  u8 *apDiv[NB];               /* Divider cells in pParent */
................................................................................
    ** page an empty page with rightChild pointing to the new
    ** child.  Then fall thru to the code below which will cause
    ** the overfull child page to be split.
    */
    rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno);
    if( rc ) return rc;
    assert( sqlite3pager_iswriteable(pChild->aData) );
    copyPage(pChild, pPage);

    pChild->pParent = pPage;
    pChild->idxParent = 0;
    sqlite3pager_ref(pPage->aData);

    pChild->isOverfull = 1;
    zeroPage(pPage, pPage->aData[pPage->hdrOffset] & ~PTF_LEAF);

    put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno);
    pParent = pPage;
    pPage = pChild;

  }
  rc = sqlite3pager_write(pParent->aData);
  if( rc ) return rc;
  assert( pParent->isInit );
  
  /*
  ** Find the cell in the parent page whose left child points back
................................................................................
  /*
  ** Make copies of the content of pPage and its siblings into aOld[].
  ** The rest of this function will use data from the copies rather
  ** that the original pages since the original pages will be in the
  ** process of being overwritten.
  */
  for(i=0; i<nOld; i++){
    apCopy[i] = (MemPage*)&aCopy[i+1][-sizeof(MemPage)];
    memset(apCopy[i], 0, sizeof(MemPage));
    apCopy[i]->aData = &((u8*)apCopy)[-pBt->pageSize];


    copyPage(apCopy[i], apOld[i]);
  }

  /*
  ** Load pointers to all cells on sibling pages and the divider cells
  ** into the local apCell[] array.  Make copies of the divider cells
  ** into aTemp[] and remove the the divider Cells from pParent.
  **
................................................................................
    MemPage *pOld = apCopy[i];
    for(j=0; j<pOld->nCell; j++){
      apCell[nCell] = pOld->aCell[j];
      szCell[nCell] = cellSize(pOld, apCell[nCell]);
      nCell++;
    }
    if( i<nOld-1 ){
      szCell[nCell] = cellSize(pParent, apDiv[i]) - leafCorrection;
      memcpy(aTemp[i], apDiv[i], szCell[nCell] + leafCorrection);
      apCell[nCell] = &aTemp[i][leafCorrection];
      dropCell(pParent, nxDiv, szCell[nCell]);

      assert( get4byte(&apCell[nCell][2])==pgnoOld[i] );
      if( !pOld->leaf ){
        assert( leafCorrection==0 );
        /* The right pointer of the child page pOld becomes the left
        ** pointer of the divider cell */
        memcpy(&apCell[nCell][2], &pOld->aData[pOld->hdrOffset+6], 4);
      }else{
        assert( leafCorrection==4 );
................................................................................

  /*
  ** Allocate k new pages.  Reuse old pages where possible.
  */
  assert( pPage->pgno>1 );
  pageFlags = pPage->aData[0];
  for(i=0; i<k; i++){

    if( i<nOld ){
      apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlite3pager_write(apNew[i]);
    }else{
      rc = allocatePage(pBt, &apNew[i], &pgnoNew[i], pgnoNew[i-1]);
      if( rc ) goto balance_cleanup;

    }
    nNew++;
    zeroPage(apNew[i], pageFlags);
    apNew[i]->isInit = 1;
  }

  /* Free any old pages that were not reused as new pages.
  */
  while( i<nOld ){
    rc = freePage(apOld[i]);
    if( rc ) goto balance_cleanup;
    sqlite3pager_unref(apOld[i]->aData);
    apOld[i] = 0;
    i++;
  }

  /*
  ** Put the new pages in accending order.  This helps to
  ** keep entries in the disk file in order so that a scan
................................................................................
    reparentChildPages(apNew[i]);
  }
  reparentChildPages(pParent);

  /*
  ** balance the parent page.
  */


  rc = balance(pParent);


  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  for(i=0; i<nOld; i++){
    releasePage(apOld[i]);
    if( apCopy[i] ){
      releasePage(apCopy[i]->pParent);
      sqliteFree(apCopy[i]->aCell);
    }
  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }
  releasePage(pParent);

  return rc;
}

/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
................................................................................
    ** 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 szNext;
    int notUsed;

    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) return rc;
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    pNext = leafCur.pPage->aCell[leafCur.idx];
    szNext = cellSize(leafCur.pPage, pNext);
    insertCell(pPage, pCur->idx, &pNext[-4], szNext+4);
    put4byte(&pNext[-2], pgnoChild);

    rc = balance(pPage);
    if( rc ) return rc;

    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    rc = balance(pPage);
  }
................................................................................
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
*/
#ifdef SQLITE_TEST
int sqlite3BtreePageDump(Btree *pBt, int pgno, int recursive){
  int rc;
  MemPage *pPage;
  int i, j;
  int nFree;
  u16 idx;
  int hdr;
  unsigned char *data;
  char range[20];
  unsigned char payload[20];

  rc = getPage(pBt, (Pgno)pgno, &pPage);
  if( rc ){
    return rc;
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;




  printf("PAGE %d:  flags=0x%02x  frag=%d\n", pgno,
    data[hdr], data[hdr+5]);
  i = 0;
  assert( hdr == (pgno==1 ? 100 : 0) );
  idx = get2byte(&data[hdr+3]);
  while( idx>0 && idx<=pBt->pageSize ){
    u64 nData, nKey;

** 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.116 2004/05/08 20:07:40 drh 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.
................................................................................
** The pParent field points back to the parent page.  This allows us to
** walk up the BTree from any leaf to the root.  Care must be taken to
** unref() the parent page pointer when this page is no longer referenced.
** The pageDestructor() routine handles that chore.
*/
struct MemPage {
  u32 notUsed;


  u8 isInit;                     /* True if previously initialized */
  u8 idxShift;                   /* True if Cell indices have changed */
  u8 isOverfull;                 /* Some aCell[] do not fit on page */
  u8 intKey;                     /* True if intkey flag is set */
  u8 leaf;                       /* True if leaf flag is set */
  u8 zeroData;                   /* True if zero data flag is set */
  u8 hdrOffset;                  /* 100 for page 1.  0 otherwise */


  int idxParent;                 /* Index in pParent->aCell[] of this node */
  int nFree;                     /* Number of free bytes on the page */
  int nCell;                     /* Number of entries on this page */
  int nCellAlloc;                /* Number of slots allocated in aCell[] */
  unsigned char **aCell;         /* Pointer to start of each cell */
  struct Btree *pBt;             /* Pointer back to BTree structure */

  unsigned char *aData;          /* Pointer back to the start of the page */
  Pgno pgno;                     /* Page number for this page */
  MemPage *pParent;              /* The parent of this page.  NULL for root */
};

/*
** 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.
*/
................................................................................
  int pageSize;
  int sumCell = 0;       /* Total size of all cells */

  assert( pPage->pBt!=0 );
  assert( pParent==0 || pParent->pBt==pPage->pBt );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] );
  assert( pPage->pParent==0 || pPage->pParent==pParent );

  if( pPage->pParent==0 && pParent!=0 ){
    pPage->pParent = pParent;

    sqlite3pager_ref(pParent->aData);
  }
  if( pPage->isInit ) return SQLITE_OK;
  pPage->nCell = pPage->nCellAlloc = 0;
  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & PTF_INTKEY)!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leaf = (c & PTF_LEAF)!=0;
  pPage->isOverfull = 0;
  pPage->idxShift = 0;
  pageSize = pPage->pBt->pageSize;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
  while( pc>0 ){
    if( pc>=pageSize ) return SQLITE_CORRUPT;
    if( pPage->nCell>pageSize ) return SQLITE_CORRUPT;
................................................................................
*/
static void zeroPage(MemPage *pPage, int flags){
  unsigned char *data = pPage->aData;
  Btree *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;

  assert( sqlite3pager_pagenumber(data)==pPage->pgno );
  assert( &data[pBt->pageSize] == (unsigned char*)pPage );
  assert( sqlite3pager_iswriteable(data) );
  memset(&data[hdr], 0, pBt->pageSize - hdr);
  data[hdr] = flags;
  first = hdr + 6 + 4*((flags&PTF_LEAF)==0);
  put2byte(&data[hdr+1], first);
  put2byte(&data[first+2], pBt->pageSize - first);
  sqliteFree(pPage->aCell);
................................................................................
  pPage->nCell = 0;
  pPage->nCellAlloc = 0;
  pPage->nFree = pBt->pageSize - first;
  pPage->intKey = (flags & PTF_INTKEY)!=0;
  pPage->leaf = (flags & PTF_LEAF)!=0;
  pPage->zeroData = (flags & PTF_ZERODATA)!=0;
  pPage->hdrOffset = hdr;
  pPage->isOverfull = 0;
  pPage->idxShift = 0;
  pPage->isInit = 1;
}

/*
** Get a page from the pager.  Initialize the MemPage.pBt and
** MemPage.aData elements if needed.
*/
static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){
................................................................................
      releasePage(pPage);
      pCur->pPage = 0;
      pCur->isValid = 0;
      pCur->status = SQLITE_ABORT;
    }
  }
}

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

/*
** Rollback the transaction in progress.  All cursors will be
** invalided by this operation.  Any attempt to use a cursor
** that was open at the beginning of this operation will result
** in an error.
**
................................................................................
** 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.
*/
static int isRootPage(MemPage *pPage){
  MemPage *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
................................................................................
    assert( idx>pPage->hdrOffset && idx<pPage->pBt->pageSize );
    put2byte(&pPage->aData[idxFrom], idx);
    idxFrom = idx;
  }
  put2byte(&pPage->aData[idxFrom], 0);
}

/*
** GCC does not define the offsetof() macro so we'll have to do it
** ourselves.
*/
#ifndef offsetof
#define offsetof(STRUCTURE,FIELD) ((int)((char*)&((STRUCTURE*)0)->FIELD))
#endif

/*
** Move the content of the page at pFrom over to pTo.  The pFrom->aCell[]
** pointers that point into pFrom->aData[] must be adjusted to point
** into pTo->aData[] instead.  But some pFrom->aCell[] entries might
** not point to pFrom->aData[].  Those are unchanged.
**
** Over this operation completes, the meta data for pFrom is zeroed.
*/
static void movePage(MemPage *pTo, MemPage *pFrom){
  uptr from, to;
  int i;
  int pageSize;
  int ofst;

  assert( pTo->hdrOffset==0 );
  ofst = pFrom->hdrOffset;
  pageSize = pFrom->pBt->pageSize;
  sqliteFree(pTo->aCell);
  memcpy(pTo->aData, &pFrom->aData[ofst], pageSize - ofst);
  memcpy(pTo, pFrom, offsetof(MemPage, aData));
  pFrom->isInit = 0;
  pFrom->aCell = 0;
  assert( pTo->aData[5]<155 );
  pTo->aData[5] += ofst;
  pTo->isOverfull = pFrom->isOverfull;
  to = Addr(pTo->aData);
  from = Addr(&pFrom->aData[ofst]);
  for(i=0; i<pTo->nCell; i++){
    uptr x = Addr(pTo->aCell[i]);
................................................................................
  int idx;                     /* Index of pPage in pParent->aCell[] */
  int nxDiv;                   /* Next divider slot in pParent->aCell[] */
  int rc;                      /* The return code */
  int leafCorrection;          /* 4 if pPage is a leaf.  0 if not */
  int usableSpace;             /* Bytes in pPage beyond the header */
  int pageFlags;               /* Value of pPage->aData[0] */
  int subtotal;                /* Subtotal of bytes in cells on one page */
  MemPage *extraUnref = 0;     /* Unref this page if not zero */
  MemPage *apOld[NB];          /* pPage and up to two siblings */
  Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
  MemPage *apCopy[NB];         /* Private copies of apOld[] pages */
  MemPage *apNew[NB+1];        /* pPage and up to NB siblings after balancing */
  Pgno pgnoNew[NB+1];          /* Page numbers for each page in apNew[] */
  int idxDiv[NB];              /* Indices of divider cells in pParent */
  u8 *apDiv[NB];               /* Divider cells in pParent */
................................................................................
    ** page an empty page with rightChild pointing to the new
    ** child.  Then fall thru to the code below which will cause
    ** the overfull child page to be split.
    */
    rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno);
    if( rc ) return rc;
    assert( sqlite3pager_iswriteable(pChild->aData) );
    movePage(pChild, pPage);
    assert( pChild->aData[0]==pPage->aData[pPage->hdrOffset] );
    pChild->pParent = pPage;

    sqlite3pager_ref(pPage->aData);
    pChild->idxParent = 0;
    pChild->isOverfull = 1;

    zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
    put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno);
    pParent = pPage;
    pPage = pChild;
    extraUnref = pChild;
  }
  rc = sqlite3pager_write(pParent->aData);
  if( rc ) return rc;
  assert( pParent->isInit );
  
  /*
  ** Find the cell in the parent page whose left child points back
................................................................................
  /*
  ** Make copies of the content of pPage and its siblings into aOld[].
  ** The rest of this function will use data from the copies rather
  ** that the original pages since the original pages will be in the
  ** process of being overwritten.
  */
  for(i=0; i<nOld; i++){
    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i+1][-sizeof(MemPage)];

    p->aData = &((u8*)p)[-pBt->pageSize];
    p->aCell = 0;
    p->hdrOffset = 0;
    movePage(p, apOld[i]);
  }

  /*
  ** Load pointers to all cells on sibling pages and the divider cells
  ** into the local apCell[] array.  Make copies of the divider cells
  ** into aTemp[] and remove the the divider Cells from pParent.
  **
................................................................................
    MemPage *pOld = apCopy[i];
    for(j=0; j<pOld->nCell; j++){
      apCell[nCell] = pOld->aCell[j];
      szCell[nCell] = cellSize(pOld, apCell[nCell]);
      nCell++;
    }
    if( i<nOld-1 ){
      szCell[nCell] = cellSize(pParent, apDiv[i]);
      memcpy(aTemp[i], apDiv[i], szCell[nCell]);
      apCell[nCell] = &aTemp[i][leafCorrection];
      dropCell(pParent, nxDiv, szCell[nCell]);
      szCell[nCell] -= leafCorrection;
      assert( get4byte(&aTemp[i][2])==pgnoOld[i] );
      if( !pOld->leaf ){
        assert( leafCorrection==0 );
        /* The right pointer of the child page pOld becomes the left
        ** pointer of the divider cell */
        memcpy(&apCell[nCell][2], &pOld->aData[pOld->hdrOffset+6], 4);
      }else{
        assert( leafCorrection==4 );
................................................................................

  /*
  ** Allocate k new pages.  Reuse old pages where possible.
  */
  assert( pPage->pgno>1 );
  pageFlags = pPage->aData[0];
  for(i=0; i<k; i++){
    MemPage *pNew;
    if( i<nOld ){
      pNew = apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlite3pager_write(pNew->aData);
    }else{
      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1]);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);

  }

  /* Free any old pages that were not reused as new pages.
  */
  while( i<nOld ){
    rc = freePage(apOld[i]);
    if( rc ) goto balance_cleanup;
    releasePage(apOld[i]);
    apOld[i] = 0;
    i++;
  }

  /*
  ** Put the new pages in accending order.  This helps to
  ** keep entries in the disk file in order so that a scan
................................................................................
    reparentChildPages(apNew[i]);
  }
  reparentChildPages(pParent);

  /*
  ** balance the parent page.
  */
  assert( pPage->isInit );
  assert( pParent->isInit );
  rc = balance(pParent);
  

  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  for(i=0; i<nOld; i++){
    releasePage(apOld[i]);
    if( apCopy[i] ){

      sqliteFree(apCopy[i]->aCell);
    }
  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }
  releasePage(pParent);
  releasePage(extraUnref);
  return rc;
}

/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
................................................................................
    ** 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 szNext;
    int notUsed;
    unsigned char tempbuf[4];
    getTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) return rc;
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    pNext = leafCur.pPage->aCell[leafCur.idx];
    szNext = cellSize(leafCur.pPage, pNext);
    memcpy(tempbuf, &pNext[-2], 4);
    put4byte(&pNext[-2], pgnoChild);
    insertCell(pPage, pCur->idx, &pNext[-4], szNext+4);
    rc = balance(pPage);
    if( rc ) return rc;
    memcpy(&pNext[-2], tempbuf, 4);
    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    rc = balance(pPage);
  }
................................................................................
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
*/
#ifdef SQLITE_TEST
int sqlite3BtreePageDump(Btree *pBt, int pgno, int recursive){
  int rc;
  MemPage *pPage;
  int i, j, c;
  int nFree;
  u16 idx;
  int hdr;
  unsigned char *data;
  char range[20];
  unsigned char payload[20];

  rc = getPage(pBt, (Pgno)pgno, &pPage);
  if( rc ){
    return rc;
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & PTF_INTKEY)!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leaf = (c & PTF_LEAF)!=0;
  printf("PAGE %d:  flags=0x%02x  frag=%d\n", pgno,
    data[hdr], data[hdr+5]);
  i = 0;
  assert( hdr == (pgno==1 ? 100 : 0) );
  idx = get2byte(&data[hdr+3]);
  while( idx>0 && idx<=pBt->pageSize ){
    u64 nData, nKey;

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.40 2004/05/08 08:23:23 danielk1977 Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................
int sqlite3BtreeKeyCompare(BtCursor *, const void *, int, int, int *);

char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot);
struct Pager *sqlite3BtreePager(Btree*);

#ifdef SQLITE_TEST
int sqlite3BtreeCursorDump(BtCursor*, int*);

int sqlite3BtreeFlags(BtCursor*);
int sqlite3BtreePageDump(Btree*, int, int recursive);
#endif


#endif /* _BTREE_H_ */

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.41 2004/05/08 20:07:40 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................
int sqlite3BtreeKeyCompare(BtCursor *, const void *, int, int, int *);

char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot);
struct Pager *sqlite3BtreePager(Btree*);

#ifdef SQLITE_TEST
int sqlite3BtreeCursorDump(BtCursor*, int*);
void sqlite3BtreeCursorList(Btree*);
int sqlite3BtreeFlags(BtCursor*);
int sqlite3BtreePageDump(Btree*, int, int recursive);
#endif


#endif /* _BTREE_H_ */

** 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.104 2004/05/08 08:23:28 danielk1977 Exp $
*/
#include "os.h"         /* Must be first to enable large file support */
#include "sqliteInt.h"
#include "pager.h"
#include <assert.h>
#include <string.h>

................................................................................
*/
Pgno sqlite3pager_pagenumber(void *pData){
  PgHdr *p = DATA_TO_PGHDR(pData);
  return p->pgno;
}

/*
** Increment the reference count for a page.  If the page is
** currently on the freelist (the reference count is zero) then
** remove it from the freelist.




*/
#define page_ref(P)   ((P)->nRef==0?_page_ref(P):(void)(P)->nRef++)
static void _page_ref(PgHdr *pPg){
  if( pPg->nRef==0 ){
    /* The page is currently on the freelist.  Remove it. */
    if( pPg==pPg->pPager->pFirstSynced ){
      PgHdr *p = pPg->pNextFree;
      while( p && p->needSync ){ p = p->pNextFree; }
      pPg->pPager->pFirstSynced = p;
................................................................................
      pPg->pPager->pLast = pPg->pPrevFree;
    }
    pPg->pPager->nRef++;
  }
  pPg->nRef++;
  REFINFO(pPg);
}













/*
** Increment the reference count for a page.  The input pointer is
** a reference to the page data.
*/
int sqlite3pager_ref(void *pData){
  PgHdr *pPg = DATA_TO_PGHDR(pData);
................................................................................
  for(pPg=pPager->pAll; pPg; pPg=pPg->pNextAll){
    if( pPg->nRef<=0 ) continue;
    printf("PAGE %3d addr=0x%08x nRef=%d\n", 
       pPg->pgno, (int)PGHDR_TO_DATA(pPg), pPg->nRef);
  }
}
#endif

** 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.105 2004/05/08 20:07:40 drh Exp $
*/
#include "os.h"         /* Must be first to enable large file support */
#include "sqliteInt.h"
#include "pager.h"
#include <assert.h>
#include <string.h>

................................................................................
*/
Pgno sqlite3pager_pagenumber(void *pData){
  PgHdr *p = DATA_TO_PGHDR(pData);
  return p->pgno;
}

/*
** The page_ref() function increments the reference count for a page.
** If the page is currently on the freelist (the reference count is zero) then
** remove it from the freelist.
**
** For non-test systems, page_ref() is a macro that calls _page_ref()
** online of the reference count is zero.  For test systems, page_ref()
** is a real function so that we can set breakpoints and trace it.
*/

static void _page_ref(PgHdr *pPg){
  if( pPg->nRef==0 ){
    /* The page is currently on the freelist.  Remove it. */
    if( pPg==pPg->pPager->pFirstSynced ){
      PgHdr *p = pPg->pNextFree;
      while( p && p->needSync ){ p = p->pNextFree; }
      pPg->pPager->pFirstSynced = p;
................................................................................
      pPg->pPager->pLast = pPg->pPrevFree;
    }
    pPg->pPager->nRef++;
  }
  pPg->nRef++;
  REFINFO(pPg);
}
#ifdef SQLITE_TEST
  static void page_ref(PgHdr *pPg){
    if( pPg->nRef==0 ){
      _page_ref(pPg);
    }else{
      pPg->nRef++;
      REFINFO(pPg);
    }
  }
#else
# define page_ref(P)   ((P)->nRef==0?_page_ref(P):(void)(P)->nRef++)
#endif

/*
** Increment the reference count for a page.  The input pointer is
** a reference to the page data.
*/
int sqlite3pager_ref(void *pData){
  PgHdr *pPg = DATA_TO_PGHDR(pData);
................................................................................
  for(pPg=pPager->pAll; pPg; pPg=pPg->pNextAll){
    if( pPg->nRef<=0 ) continue;
    printf("PAGE %3d addr=0x%08x nRef=%d\n", 
       pPg->pgno, (int)PGHDR_TO_DATA(pPg), pPg->nRef);
  }
}
#endif

**    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: test3.c,v 1.30 2004/05/08 08:23:39 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  zResult = sqlite3BtreeIntegrityCheck(pBt, aRoot, nRoot);
  if( zResult ){
    Tcl_AppendResult(interp, zResult, 0);
    sqliteFree(zResult); 
  }
  return TCL_OK;
}
























/*
** Usage:   btree_cursor ID TABLENUM WRITEABLE
**
** Create a new cursor.  Return the ID for the cursor.
*/
static int btree_cursor(
................................................................................
     { "btree_keysize",            (Tcl_CmdProc*)btree_keysize            },
     { "btree_key",                (Tcl_CmdProc*)btree_key                },
     { "btree_data",               (Tcl_CmdProc*)btree_data               },
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_dump",        (Tcl_CmdProc*)btree_cursor_dump        },

     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
     { "btree_breakpoint",         (Tcl_CmdProc*)btree_breakpoint         },
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  return TCL_OK;
}

**    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: test3.c,v 1.31 2004/05/08 20:07:40 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  zResult = sqlite3BtreeIntegrityCheck(pBt, aRoot, nRoot);
  if( zResult ){
    Tcl_AppendResult(interp, zResult, 0);
    sqliteFree(zResult); 
  }
  return TCL_OK;
}

/*
** Usage:   btree_cursor_list ID
**
** Print information about all cursors to standard output for debugging.
*/
static int btree_cursor_list(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  Btree *pBt;

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pBt) ) return TCL_ERROR;
  sqlite3BtreeCursorList(pBt);
  return SQLITE_OK;
}

/*
** Usage:   btree_cursor ID TABLENUM WRITEABLE
**
** Create a new cursor.  Return the ID for the cursor.
*/
static int btree_cursor(
................................................................................
     { "btree_keysize",            (Tcl_CmdProc*)btree_keysize            },
     { "btree_key",                (Tcl_CmdProc*)btree_key                },
     { "btree_data",               (Tcl_CmdProc*)btree_data               },
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_dump",        (Tcl_CmdProc*)btree_cursor_dump        },
     { "btree_cursor_list",        (Tcl_CmdProc*)btree_cursor_list        },
     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
     { "btree_breakpoint",         (Tcl_CmdProc*)btree_breakpoint         },
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  return TCL_OK;
}

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.19 2004/05/08 10:56:20 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-10.2 {
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-10.3 {
  for {set i 1} {$i<=20} {incr i} {
    set key [format %03d $i]
    set data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
  }
  select_keys $::c1
} {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020}
#btree_page_dump $::b1 7
btree_page_dump $::b1 1
#btree_page_dump $::b1 6
do_test btree-10.4 {



  btree_move_to $::c1 011
  btree_delete $::c1
  select_keys $::c1
} {001 002 003 004 005 006 007 008 009 010 012 013 014 015 016 017 018 019 020}
#btree_tree_dump $::b1 2
#btree_pager_ref_dump $::b1

for {set i 1} {$i<=20} {incr i} {


  do_test btree-10.5.$i {
    btree_move_to $::c1 [format %03d $i]
    lindex [btree_pager_stats $::b1] 1
  } {2}
  #btree_pager_ref_dump $::b1
  #btree_tree_dump $::b1 2
}

# Create a tree with lots more pages
#
catch {unset ::data}
catch {unset ::key}
for {set i 21} {$i<=1000} {incr i} {






  do_test btree-11.1.$i.1 {
    set key [format %03d $i]
    set ::data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data

    btree_key $::c1
  } [format %03d $i]






  do_test btree-11.1.$i.2 {
    btree_data $::c1
  } $::data
  set ::key [format %03d [expr {$i/2}]]
  if {$::key=="011"} {set ::key 010}
  do_test btree-11.1.$i.3 {
    btree_move_to $::c1 $::key
    btree_key $::c1
  } $::key
}
catch {unset ::data}
catch {unset ::key}

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.20 2004/05/08 20:07:40 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-10.2 {
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-10.3 {
  for {set i 1} {$i<=30} {incr i} {
    set key [format %03d $i]
    set data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
  }
  select_keys $::c1
} {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030}

#btree_tree_dump $::b1 2

do_test btree-10.4 {
  # The divider entry is 012.  This is found by uncommenting the 
  # btree_tree_dump call above and looking at the tree.  If the page size
  # changes, this test will no longer work.
  btree_move_to $::c1 012
  btree_delete $::c1
  select_keys $::c1
} {001 002 003 004 005 006 007 008 009 010 011 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030}

#btree_pager_ref_dump $::b1
#btree_tree_dump $::b1 2
for {set i 1} {$i<=30} {incr i} {
  # Check the number of unreference pages.  This should be 3 in most cases,
  # but 2 when the cursor is pointing to the divider entry which is now 013.
  do_test btree-10.5.$i {
    btree_move_to $::c1 [format %03d $i]
    lindex [btree_pager_stats $::b1] 1
  } [expr {$i==13?2:3}]
  #btree_pager_ref_dump $::b1
  #btree_tree_dump $::b1 2
}

# Create a tree with lots more pages
#
catch {unset ::data}
catch {unset ::key}
for {set i 31} {$i<=1000} {incr i} {
if {$i==88} {
set pager_refinfo_enable 1
btree_tree_dump $b1 2
btree_pager_ref_dump $b1
btree_cursor_list $b1
}
  do_test btree-11.1.$i.1 {
    set key [format %03d $i]
    set ::data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
    btree_move_to $::c1 $key
    btree_key $::c1
  } [format %03d $i]
if {$i==88} {
btree_pager_ref_dump $b1
btree_cursor_list $b1
btree_tree_dump $b1 2
exit
}
  do_test btree-11.1.$i.2 {
    btree_data $::c1
  } $::data
  set ::key [format %03d [expr {$i/2}]]
  if {$::key=="012"} {set ::key 013}
  do_test btree-11.1.$i.3 {
    btree_move_to $::c1 $::key
    btree_key $::c1
  } $::key
}
catch {unset ::data}
catch {unset ::key}