** 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.127 2004/05/11 09:31:32 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.
................................................................................
/*
** Parse a cell header and fill in the CellInfo structure.
*/
static void parseCellHeader(
  MemPage *pPage,         /* Page containing the cell */
  unsigned char *pCell,   /* The cell */
  u64 *pnData,            /* Number of bytes of data in payload */
  u64 *pnKey,             /* Number of bytes of key, or key value for intKey */
  int *pnHeader           /* Size of header in bytes.  Offset to payload */
){
  int n;
  if( pPage->leaf ){
    n = 2;
  }else{
    n = 6;
  }
  if( pPage->zeroData ){
    *pnData = 0;
  }else{
    n += getVarint(&pCell[n], pnData);
  }
  n += getVarint(&pCell[n], pnKey);
  *pnHeader = n;
}

/*
** Compute the total number of bytes that a Cell needs on the main
** database page.  The number returned includes the Cell header,
** local payload storage, and the pointer to overflow pages (if
** applicable).  Additional space allocated on overflow pages
** is NOT included in the value returned from this routine.
*/
static int cellSize(MemPage *pPage, unsigned char *pCell){
  int n;
  u64 nData, nKey;

  int nPayload, maxPayload;

  parseCellHeader(pPage, pCell, &nData, &nKey, &n);
  nPayload = (int)nData;
  if( !pPage->intKey ){
    nPayload += (int)nKey;
  }
................................................................................
  int rc;

  /*
  ** The following asserts make sure that structures used by the btree are
  ** the right size.  This is to guard against size changes that result
  ** when compiling on a different architecture.
  */

  assert( sizeof(u64)==8 );
  assert( sizeof(u32)==4 );
  assert( sizeof(u16)==2 );
  assert( sizeof(Pgno)==4 );
  assert( sizeof(ptr)==sizeof(char*) );
  assert( sizeof(uptr)==sizeof(ptr) );

................................................................................
** 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. 
**
** For a table with the INTKEY flag set, this routine returns the key
** itself, not the number of bytes in the key.
*/
int sqlite3BtreeKeySize(BtCursor *pCur, u64 *pSize){
  MemPage *pPage;
  unsigned char *cell;

  if( !pCur->isValid ){
    *pSize = 0;
  }else{
    pPage = pCur->pPage;
................................................................................
  int skipKey          /* offset begins at data if this is true */
){
  unsigned char *aPayload;
  Pgno nextPage;
  int rc;
  MemPage *pPage;
  Btree *pBt;
  u64 nData, nKey;

  int maxLocal, ovflSize;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
................................................................................
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->zeroData ){
    nData = 0;
  }else{
    aPayload += getVarint(aPayload, &nData);
  }
  aPayload += getVarint(aPayload, &nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  assert( offset>=0 );
  if( skipKey ){
    offset += nKey;
  }
................................................................................
  BtCursor *pCur,      /* Cursor pointing to entry to read from */
  int amt,             /* Amount requested */
  int skipKey          /* read beginning at data if this is true */
){
  unsigned char *aPayload;
  MemPage *pPage;
  Btree *pBt;
  u64 nData, nKey;

  int maxLocal;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
................................................................................
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->zeroData ){
    nData = 0;
  }else{
    aPayload += getVarint(aPayload, &nData);
  }
  aPayload += getVarint(aPayload, &nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  maxLocal = pBt->maxLocal;
  if( skipKey ){
    aPayload += nKey;
    maxLocal -= nKey;
................................................................................
**
**     *pRes==0     The cursor is left pointing at an entry that
**                  exactly matches pKey.
**
**     *pRes>0      The cursor is left pointing at an entry that
**                  is larger than pKey.
*/
int sqlite3BtreeMoveto(BtCursor *pCur, const void *pKey, u64 nKey, int *pRes){
  int rc;

  if( pCur->status ){
    return pCur->status;
  }
  rc = moveToRoot(pCur);
  if( rc ) return rc;
................................................................................
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
    pageIntegrity(pPage);
    while( lwr<=upr ){
      const void *pCellKey;
      u64 nCellKey;
      pCur->idx = (lwr+upr)/2;
      sqlite3BtreeKeySize(pCur, &nCellKey);
      if( pPage->intKey ){
        if( nCellKey<nKey ){
          c = -1;
        }else if( nCellKey>nKey ){
          c = +1;
................................................................................

/*
** Free any overflow pages associated with the given Cell.
*/
static int clearCell(MemPage *pPage, unsigned char *pCell){
  Btree *pBt = pPage->pBt;
  int rc, n, nPayload;
  u64 nData, nKey;

  Pgno ovflPgno;

  parseCellHeader(pPage, pCell, &nData, &nKey, &n);
  assert( (nData&0x000000007fffffff)==nData );
  nPayload = (int)nData;
  if( !pPage->intKey ){
    nPayload += nKey;
................................................................................
** area.  pCell might point to some temporary storage.  The cell will
** be constructed in this temporary area then copied into pPage->aData
** later.
*/
static int fillInCell(
  MemPage *pPage,                /* The page that contains the cell */
  unsigned char *pCell,          /* Complete text of the cell */
  const void *pKey, u64 nKey,    /* The key */
  const void *pData,int nData,   /* The data */
  int *pnSize                    /* Write cell size here */
){
  int nPayload;
  const void *pSrc;
  int nSrc, n, rc;
  int spaceLeft;
................................................................................
  nHeader = 2;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( !pPage->zeroData ){
    nHeader += putVarint(&pCell[nHeader], nData);
  }
  nHeader += putVarint(&pCell[nHeader], nKey);
  
  /* Fill in the payload */
  if( pPage->zeroData ){
    nData = 0;
  }
  nPayload = nData;
  if( pPage->intKey ){
................................................................................
** is left pointing at a random location.
**
** For an INTKEY table, only the nKey value of the key is used.  pKey is
** ignored.  For a ZERODATA table, the pData and nData are both ignored.
*/
int sqlite3BtreeInsert(
  BtCursor *pCur,                /* Insert data into the table of this cursor */
  const void *pKey, u64 nKey,    /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
................................................................................
  }
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;

  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 );
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;
  rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew);
................................................................................
  printf("PAGE %d:  flags=0x%02x  frag=%d   parent=%d\n", pgno,
    data[hdr], data[hdr+5], 
    (pPage->isInit && pPage->pParent) ? pPage->pParent->pgno : 0);
  i = 0;
  assert( hdr == (pgno==1 ? 100 : 0) );
  idx = get2byte(&data[hdr+3]);
  while( idx>0 && idx<=pBt->pageSize ){
    u64 nData, nKey;

    int nHeader;
    Pgno child;
    unsigned char *pCell = &data[idx];
    int sz = cellSize(pPage, pCell);
    sprintf(range,"%d..%d", idx, idx+sz-1);
    parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader);
    if( pPage->leaf ){
................................................................................

  /* Check out all the cells.
  */
  depth = 0;
  cur.pPage = pPage;
  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = pPage->aCell[i];
    u64 nKey, nData;

    int sz, nHeader;

    /* Check payload overflow pages
    */
    sprintf(zContext, "On tree page %d cell %d: ", iPage, i);
    parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader);
    sz = nData;

** 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.128 2004/05/12 15:15:47 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.
................................................................................
/*
** Parse a cell header and fill in the CellInfo structure.
*/
static void parseCellHeader(
  MemPage *pPage,         /* Page containing the cell */
  unsigned char *pCell,   /* The cell */
  u64 *pnData,            /* Number of bytes of data in payload */
  i64 *pnKey,             /* Number of bytes of key, or key value for intKey */
  int *pnHeader           /* Size of header in bytes.  Offset to payload */
){
  int n;
  if( pPage->leaf ){
    n = 2;
  }else{
    n = 6;
  }
  if( pPage->zeroData ){
    *pnData = 0;
  }else{
    n += getVarint(&pCell[n], pnData);
  }
  n += getVarint(&pCell[n], (u64*)pnKey);
  *pnHeader = n;
}

/*
** Compute the total number of bytes that a Cell needs on the main
** database page.  The number returned includes the Cell header,
** local payload storage, and the pointer to overflow pages (if
** applicable).  Additional space allocated on overflow pages
** is NOT included in the value returned from this routine.
*/
static int cellSize(MemPage *pPage, unsigned char *pCell){
  int n;
  u64 nData;
  i64 nKey;
  int nPayload, maxPayload;

  parseCellHeader(pPage, pCell, &nData, &nKey, &n);
  nPayload = (int)nData;
  if( !pPage->intKey ){
    nPayload += (int)nKey;
  }
................................................................................
  int rc;

  /*
  ** The following asserts make sure that structures used by the btree are
  ** the right size.  This is to guard against size changes that result
  ** when compiling on a different architecture.
  */
  assert( sizeof(i64)==8 );
  assert( sizeof(u64)==8 );
  assert( sizeof(u32)==4 );
  assert( sizeof(u16)==2 );
  assert( sizeof(Pgno)==4 );
  assert( sizeof(ptr)==sizeof(char*) );
  assert( sizeof(uptr)==sizeof(ptr) );

................................................................................
** 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. 
**
** For a table with the INTKEY flag set, this routine returns the key
** itself, not the number of bytes in the key.
*/
int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
  MemPage *pPage;
  unsigned char *cell;

  if( !pCur->isValid ){
    *pSize = 0;
  }else{
    pPage = pCur->pPage;
................................................................................
  int skipKey          /* offset begins at data if this is true */
){
  unsigned char *aPayload;
  Pgno nextPage;
  int rc;
  MemPage *pPage;
  Btree *pBt;
  u64 nData;
  i64 nKey;
  int maxLocal, ovflSize;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
................................................................................
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->zeroData ){
    nData = 0;
  }else{
    aPayload += getVarint(aPayload, &nData);
  }
  aPayload += getVarint(aPayload, (u64*)&nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  assert( offset>=0 );
  if( skipKey ){
    offset += nKey;
  }
................................................................................
  BtCursor *pCur,      /* Cursor pointing to entry to read from */
  int amt,             /* Amount requested */
  int skipKey          /* read beginning at data if this is true */
){
  unsigned char *aPayload;
  MemPage *pPage;
  Btree *pBt;
  u64 nData;
  i64 nKey;
  int maxLocal;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
................................................................................
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->zeroData ){
    nData = 0;
  }else{
    aPayload += getVarint(aPayload, &nData);
  }
  aPayload += getVarint(aPayload, (u64*)&nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  maxLocal = pBt->maxLocal;
  if( skipKey ){
    aPayload += nKey;
    maxLocal -= nKey;
................................................................................
**
**     *pRes==0     The cursor is left pointing at an entry that
**                  exactly matches pKey.
**
**     *pRes>0      The cursor is left pointing at an entry that
**                  is larger than pKey.
*/
int sqlite3BtreeMoveto(BtCursor *pCur, const void *pKey, i64 nKey, int *pRes){
  int rc;

  if( pCur->status ){
    return pCur->status;
  }
  rc = moveToRoot(pCur);
  if( rc ) return rc;
................................................................................
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
    pageIntegrity(pPage);
    while( lwr<=upr ){
      const void *pCellKey;
      i64 nCellKey;
      pCur->idx = (lwr+upr)/2;
      sqlite3BtreeKeySize(pCur, &nCellKey);
      if( pPage->intKey ){
        if( nCellKey<nKey ){
          c = -1;
        }else if( nCellKey>nKey ){
          c = +1;
................................................................................

/*
** Free any overflow pages associated with the given Cell.
*/
static int clearCell(MemPage *pPage, unsigned char *pCell){
  Btree *pBt = pPage->pBt;
  int rc, n, nPayload;
  u64 nData;
  i64 nKey;
  Pgno ovflPgno;

  parseCellHeader(pPage, pCell, &nData, &nKey, &n);
  assert( (nData&0x000000007fffffff)==nData );
  nPayload = (int)nData;
  if( !pPage->intKey ){
    nPayload += nKey;
................................................................................
** area.  pCell might point to some temporary storage.  The cell will
** be constructed in this temporary area then copied into pPage->aData
** later.
*/
static int fillInCell(
  MemPage *pPage,                /* The page that contains the cell */
  unsigned char *pCell,          /* Complete text of the cell */
  const void *pKey, i64 nKey,    /* The key */
  const void *pData,int nData,   /* The data */
  int *pnSize                    /* Write cell size here */
){
  int nPayload;
  const void *pSrc;
  int nSrc, n, rc;
  int spaceLeft;
................................................................................
  nHeader = 2;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( !pPage->zeroData ){
    nHeader += putVarint(&pCell[nHeader], nData);
  }
  nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey);
  
  /* Fill in the payload */
  if( pPage->zeroData ){
    nData = 0;
  }
  nPayload = nData;
  if( pPage->intKey ){
................................................................................
** is left pointing at a random location.
**
** For an INTKEY table, only the nKey value of the key is used.  pKey is
** ignored.  For a ZERODATA table, the pData and nData are both ignored.
*/
int sqlite3BtreeInsert(
  BtCursor *pCur,                /* Insert data into the table of this cursor */
  const void *pKey, i64 nKey,    /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
................................................................................
  }
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );
  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 );
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;
  rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew);
................................................................................
  printf("PAGE %d:  flags=0x%02x  frag=%d   parent=%d\n", pgno,
    data[hdr], data[hdr+5], 
    (pPage->isInit && pPage->pParent) ? pPage->pParent->pgno : 0);
  i = 0;
  assert( hdr == (pgno==1 ? 100 : 0) );
  idx = get2byte(&data[hdr+3]);
  while( idx>0 && idx<=pBt->pageSize ){
    u64 nData;
    i64 nKey;
    int nHeader;
    Pgno child;
    unsigned char *pCell = &data[idx];
    int sz = cellSize(pPage, pCell);
    sprintf(range,"%d..%d", idx, idx+sz-1);
    parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader);
    if( pPage->leaf ){
................................................................................

  /* Check out all the cells.
  */
  depth = 0;
  cur.pPage = pPage;
  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = pPage->aCell[i];
    i64 nKey;
    u64 nData;
    int sz, nHeader;

    /* Check payload overflow pages
    */
    sprintf(zContext, "On tree page %d cell %d: ", iPage, i);
    parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader);
    sz = nData;

**    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.45 2004/05/11 00:58:56 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................
  int wrFlag,                          /* 1 for writing.  0 for read-only */
  int(*)(void*,int,const void*,int,const void*),  /* Key comparison function */
  void*,                               /* First argument to compare function */
  BtCursor **ppCursor                  /* Returned cursor */
);

int sqlite3BtreeCloseCursor(BtCursor*);
int sqlite3BtreeMoveto(BtCursor*, const void *pKey, u64 nKey, int *pRes);
int sqlite3BtreeDelete(BtCursor*);
int sqlite3BtreeInsert(BtCursor*, const void *pKey, u64 nKey,
                                  const void *pData, int nData);
int sqlite3BtreeFirst(BtCursor*, int *pRes);
int sqlite3BtreeLast(BtCursor*, int *pRes);
int sqlite3BtreeNext(BtCursor*, int *pRes);
int sqlite3BtreeEof(BtCursor*);
int sqlite3BtreeFlags(BtCursor*);
int sqlite3BtreePrevious(BtCursor*, int *pRes);
int sqlite3BtreeKeySize(BtCursor*, u64 *pSize);
int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*);
const void *sqlite3BtreeKeyFetch(BtCursor*, int amt);
const void *sqlite3BtreeDataFetch(BtCursor*, int amt);
int sqlite3BtreeDataSize(BtCursor*, u32 *pSize);
int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);

char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot);

**    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.46 2004/05/12 15:15:47 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................
  int wrFlag,                          /* 1 for writing.  0 for read-only */
  int(*)(void*,int,const void*,int,const void*),  /* Key comparison function */
  void*,                               /* First argument to compare function */
  BtCursor **ppCursor                  /* Returned cursor */
);

int sqlite3BtreeCloseCursor(BtCursor*);
int sqlite3BtreeMoveto(BtCursor*, const void *pKey, i64 nKey, int *pRes);
int sqlite3BtreeDelete(BtCursor*);
int sqlite3BtreeInsert(BtCursor*, const void *pKey, i64 nKey,
                                  const void *pData, int nData);
int sqlite3BtreeFirst(BtCursor*, int *pRes);
int sqlite3BtreeLast(BtCursor*, int *pRes);
int sqlite3BtreeNext(BtCursor*, int *pRes);
int sqlite3BtreeEof(BtCursor*);
int sqlite3BtreeFlags(BtCursor*);
int sqlite3BtreePrevious(BtCursor*, int *pRes);
int sqlite3BtreeKeySize(BtCursor*, i64 *pSize);
int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*);
const void *sqlite3BtreeKeyFetch(BtCursor*, int amt);
const void *sqlite3BtreeDataFetch(BtCursor*, int amt);
int sqlite3BtreeDataSize(BtCursor*, u32 *pSize);
int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);

char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot);

** VDBE.  This information used to all be at the top of the single
** source code file "vdbe.c".  When that file became too big (over
** 6000 lines long) it was split up into several smaller files and
** this header information was factored out.
*/

/*
** In the btree layer, a rowid is an unsigned 64-bit integer.  In the
** schema layer, a rowid is a signed 64-bit integer.  The following macros
** convert between the two in such a way as to preserve sort order.
*/
#define keyToInt(X)   (X ^ 0x8000000000000000)
#define intToKey(X)   (X ^ 0x8000000000000000)

/*
** The makefile scans this source file and creates the following
** array of string constants which are the names of all VDBE opcodes.
** This array is defined in a separate source code file named opcode.c
** which is automatically generated by the makefile.
*/

** VDBE.  This information used to all be at the top of the single
** source code file "vdbe.c".  When that file became too big (over
** 6000 lines long) it was split up into several smaller files and
** this header information was factored out.
*/

/*
** intToKey() and keyToInt() used to transform the rowid.  But with
** the latest versions of the design they are no-ops.

*/
#define keyToInt(X)   (X)
#define intToKey(X)   (X)

/*
** The makefile scans this source file and creates the following
** array of string constants which are the names of all VDBE opcodes.
** This array is defined in a separate source code file named opcode.c
** which is automatically generated by the makefile.
*/