** 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.523 2008/09/30 16:48:11 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 0
int sqlite3BtreeTrace=0;  /* True to enable tracing */
# define TRACE(X)  if(sqlite3BtreeTrace){printf X;fflush(stdout);}
#else
# define TRACE(X)
#endif

















#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** A list of BtShared objects that are eligible for participation
** in shared cache.  This variable has file scope during normal builds,
** but the test harness needs to access it so we make it global for 
................................................................................
** the database file should be truncated to during the commit process. 
** i.e. the database has been reorganized so that only the first *pnTrunc
** pages are in use.
*/
static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){
  int rc = SQLITE_OK;
  Pager *pPager = pBt->pPager;
#ifndef NDEBUG
  int nRef = sqlite3PagerRefcount(pPager);
#endif

  assert( sqlite3_mutex_held(pBt->mutex) );
  invalidateAllOverflowCache(pBt);
  assert(pBt->autoVacuum);
  if( !pBt->incrVacuum ){
    Pgno nFin = 0;

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

  pPage = pCur->apPage[pCur->iPage];
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );


  /* 
  ** Find the parent page.
  */
  assert( pCur->iPage>0 );
  assert( pPage->isInit );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
................................................................................
    ** its child (due to the 100 byte header that occurs at the beginning
    ** of the database fle), so it might not be able to hold all of the 
    ** information currently contained in the child.  If this is the 
    ** case, then do not do the transfer.  Leave page 1 empty except
    ** for the right-pointer to the child page.  The child page becomes
    ** the virtual root of the tree.
    */

    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);
................................................................................
  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( pCur->iPage==0 );
  assert( pCur->apPage[0]->nOverflow>0 );


  pPage = pCur->apPage[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;
................................................................................
  }
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->apPage[pCur->iPage];
  int idx;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
................................................................................
      tempCell = pBt->pTmpSpace;
      if( tempCell==0 ){
        rc = SQLITE_NOMEM;
      }
      if( rc==SQLITE_OK ){
        rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell, 0);
      }




















      if( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3)) &&
          (pLeafPage->nFree+2+szNext > pBt->usableSize*2/3)
      ){
        /* This branch is taken if the internal node is now either over or
        ** underfull and the leaf node will be underfull after the just cell 
        ** copied to the internal node is deleted from it. This is a special
        ** case because the call to balance() to correct the internal node
        ** may change the tree structure and invalidate the contents of
        ** the leafCur.apPage[] and leafCur.aiIdx[] arrays, which will be
        ** used by the balance() required to correct the underfull leaf
        ** node.
        **
        ** The formula used in the expression above are based on facets of
        ** the SQLite file-format that do not change over time.
        */


        leafCursorInvalid = 1;
      }        

      if( rc==SQLITE_OK ){
        put4byte(findOverflowCell(pPage, idx), pgnoChild);

        rc = balance(pCur, 0);
      }

      if( rc==SQLITE_OK && leafCursorInvalid ){
        /* The leaf-node is now underfull and so the tree needs to be 
        ** rebalanced. However, the balance() operation on the internal
        ** node above may have modified the structure of the B-Tree and
................................................................................
        ** calls restoreCursorPosition() to point the cursor to the copy
        ** stored on the internal node, then advances to the next entry,
        ** which happens to be the copy of the key on the internal node.
        ** Net effect: leafCur is pointing back to the duplicate cell
        ** that needs to be removed, and the leafCur.apPage[] and
        ** leafCur.aiIdx[] arrays are correct.
        */
      #ifndef NDEBUG
        Pgno leafPgno = pLeafPage->pgno;
      #endif
        rc = saveCursorPosition(&leafCur);
        if( rc==SQLITE_OK ){
          rc = sqlite3BtreeNext(&leafCur, &notUsed);
        }
        pLeafPage = leafCur.apPage[leafCur.iPage];
        assert( pLeafPage->pgno==leafPgno );
        assert( leafCur.aiIdx[leafCur.iPage]==0 );
      }

      if( rc==SQLITE_OK ){
        dropCell(pLeafPage, 0, szNext);

        rc = balance(&leafCur, 0);


      }
    }
    sqlite3BtreeReleaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, idx, cellSizePtr(pPage, pCell));

** 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.524 2008/09/30 17:18:17 drh 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 0
int sqlite3BtreeTrace=0;  /* True to enable tracing */
# define TRACE(X)  if(sqlite3BtreeTrace){printf X;fflush(stdout);}
#else
# define TRACE(X)
#endif

/*
** Sometimes we need a small amount of code such as a variable initialization
** to setup for a later assert() statement.  We do not want this code to
** appear when assert() is disabled.  The following macro is therefore
** used to contain that setup code.  The "VVA" acronym stands for
** "Verification, Validation, and Accreditation".  In other words, the
** code within VVA_ONLY() will only run during verification processes.
*/
#ifndef NDEBUG
# define VVA_ONLY(X)  X
#else
# define VVA_ONLY(X)
#endif



#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** A list of BtShared objects that are eligible for participation
** in shared cache.  This variable has file scope during normal builds,
** but the test harness needs to access it so we make it global for 
................................................................................
** the database file should be truncated to during the commit process. 
** i.e. the database has been reorganized so that only the first *pnTrunc
** pages are in use.
*/
static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){
  int rc = SQLITE_OK;
  Pager *pPager = pBt->pPager;

  VVA_ONLY( int nRef = sqlite3PagerRefcount(pPager) );


  assert( sqlite3_mutex_held(pBt->mutex) );
  invalidateAllOverflowCache(pBt);
  assert(pBt->autoVacuum);
  if( !pBt->incrVacuum ){
    Pgno nFin = 0;

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

  pPage = pCur->apPage[pCur->iPage];
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  VVA_ONLY( pCur->pagesShuffled = 1 );

  /* 
  ** Find the parent page.
  */
  assert( pCur->iPage>0 );
  assert( pPage->isInit );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
................................................................................
    ** its child (due to the 100 byte header that occurs at the beginning
    ** of the database fle), so it might not be able to hold all of the 
    ** information currently contained in the child.  If this is the 
    ** case, then do not do the transfer.  Leave page 1 empty except
    ** for the right-pointer to the child page.  The child page becomes
    ** the virtual root of the tree.
    */
    VVA_ONLY( pCur->pagesShuffled = 1 );
    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);
................................................................................
  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( pCur->iPage==0 );
  assert( pCur->apPage[0]->nOverflow>0 );

  VVA_ONLY( pCur->pagesShuffled = 1 );
  pPage = pCur->apPage[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;
................................................................................
  }
end_insert:
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
** is left pointing at a arbitrary location.
*/
int sqlite3BtreeDelete(BtCursor *pCur){
  MemPage *pPage = pCur->apPage[pCur->iPage];
  int idx;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
................................................................................
      tempCell = pBt->pTmpSpace;
      if( tempCell==0 ){
        rc = SQLITE_NOMEM;
      }
      if( rc==SQLITE_OK ){
        rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell, 0);
      }


      /* The "if" statement in the next code block is critical.  The
      ** slightest error in that statement would allow SQLite to operate
      ** correctly most of the time but produce very rare failures.  To
      ** guard against this, the following macros help to verify that
      ** the "if" statement is well tested.
      */
      testcase( pPage->nOverflow==0 && pPage->nFree<pBt->usableSize*2/3 
                 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 );
      testcase( pPage->nOverflow==0 && pPage->nFree==pBt->usableSize*2/3 
                 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 );
      testcase( pPage->nOverflow==0 && pPage->nFree==pBt->usableSize*2/3+1 
                 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 );
      testcase( pPage->nOverflow>0 && pPage->nFree<=pBt->usableSize*2/3
                 && pLeafPage->nFree+2+szNext > pBt->usableSize*2/3 );
      testcase( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3))
                 && pLeafPage->nFree+2+szNext == pBt->usableSize*2/3 );


      if( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3)) &&
          (pLeafPage->nFree+2+szNext > pBt->usableSize*2/3)
      ){
        /* This branch is taken if the internal node is now either overflowing
        ** or underfull and the leaf node will be underfull after the just cell 
        ** copied to the internal node is deleted from it. This is a special
        ** case because the call to balance() to correct the internal node
        ** may change the tree structure and invalidate the contents of
        ** the leafCur.apPage[] and leafCur.aiIdx[] arrays, which will be
        ** used by the balance() required to correct the underfull leaf
        ** node.
        **
        ** The formula used in the expression above are based on facets of
        ** the SQLite file-format that do not change over time.
        */
        testcase( pPage->nFree==pBt->usableSize*2/3+1 );
        testcase( pLeafPage->nFree+2+szNext==pBt->usableSize*2/3+1 );
        leafCursorInvalid = 1;
      }        

      if( rc==SQLITE_OK ){
        put4byte(findOverflowCell(pPage, idx), pgnoChild);
        VVA_ONLY( pCur->pagesShuffled = 0 );
        rc = balance(pCur, 0);
      }

      if( rc==SQLITE_OK && leafCursorInvalid ){
        /* The leaf-node is now underfull and so the tree needs to be 
        ** rebalanced. However, the balance() operation on the internal
        ** node above may have modified the structure of the B-Tree and
................................................................................
        ** calls restoreCursorPosition() to point the cursor to the copy
        ** stored on the internal node, then advances to the next entry,
        ** which happens to be the copy of the key on the internal node.
        ** Net effect: leafCur is pointing back to the duplicate cell
        ** that needs to be removed, and the leafCur.apPage[] and
        ** leafCur.aiIdx[] arrays are correct.
        */

        VVA_ONLY( Pgno leafPgno = pLeafPage->pgno );

        rc = saveCursorPosition(&leafCur);
        if( rc==SQLITE_OK ){
          rc = sqlite3BtreeNext(&leafCur, &notUsed);
        }
        pLeafPage = leafCur.apPage[leafCur.iPage];
        assert( pLeafPage->pgno==leafPgno );
        assert( leafCur.aiIdx[leafCur.iPage]==0 );
      }

      if( rc==SQLITE_OK ){
        dropCell(pLeafPage, 0, szNext);
        VVA_ONLY( leafCur.pagesShuffled = 0 );
        rc = balance(&leafCur, 0);
        assert( leafCursorInvalid || !leafCur.pagesShuffled
                                   || !pCur->pagesShuffled );
      }
    }
    sqlite3BtreeReleaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, idx, cellSizePtr(pPage, pCell));

** 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.33 2008/09/29 15:53:26 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.
................................................................................
  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



  i16 iPage;                            /* Index of current page in apPage */
  MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
  u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */
};

/*
** Potential values for BtCursor.eState.

** 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.34 2008/09/30 17:18:17 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.
................................................................................
  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
#ifndef NDEBUG
  u8 pagesShuffled;         /* True if Btree pages are rearranged by balance()*/
#endif
  i16 iPage;                            /* Index of current page in apPage */
  MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
  u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */
};

/*
** Potential values for BtCursor.eState.