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

/*
** Page type flags.  An ORed combination of these flags appear as the
** first byte of every BTree page.
*/
#define PTF_INTKEY    0x01
#define PTF_ZERODATA  0x02

#define PTF_LEAF      0x04
/* Idea for the future:  PTF_LEAFDATA */

/*
** As each page of the file is loaded into memory, an instance of the following
** structure is appended and initialized to zero.  This structure stores
** information about the page that is decoded from the raw file page.
**
** The pParent field points back to the parent page.  This allows us to
................................................................................
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 */
  u8 needRelink;                 /* True if need to run relinkCellList() */
  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 */
................................................................................
){
  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
................................................................................
  hdr = pPage->hdrOffset;
  assert( hdr==(pPage->pgno==1 ? 100 : 0) );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  c = pPage->aData[hdr];
  if( pPage->isInit ){
    assert( pPage->leaf == ((c & PTF_LEAF)!=0) );
    assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) );

    assert( pPage->intKey == ((c & PTF_INTKEY)!=0) );


  }
  data = pPage->aData;
  memset(used, 0, pageSize);
  for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1;
  nFree = 0;
  pc = get2byte(&data[hdr+1]);
  while( pc ){
................................................................................
  }
  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->needRelink = 0;
  pPage->idxShift = 0;
  pageSize = pPage->pBt->pageSize;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
................................................................................
  put2byte(&data[hdr+1], first);
  put2byte(&data[first+2], pBt->pageSize - first);
  sqliteFree(pPage->aCell);
  pPage->aCell = 0;
  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->needRelink = 0;
  pPage->idxShift = 0;
  pPage->isInit = 1;
  pageIntegrity(pPage);
}
................................................................................
  if( rc ) return rc;
  memcpy(data, zMagicHeader, sizeof(zMagicHeader));
  assert( sizeof(zMagicHeader)==16 );
  put2byte(&data[16], SQLITE_PAGE_SIZE);
  data[18] = 1;
  data[19] = 1;
  put2byte(&data[22], (SQLITE_PAGE_SIZE-10)/4-12);
  zeroPage(pP1, PTF_INTKEY|PTF_LEAF);
  return SQLITE_OK;
}

/*
** Attempt to start a new transaction.
**
** A transaction must be started before attempting any changes
................................................................................
    assert( pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
    }
    if( !pPage->zeroData ){
      while( (0x80&*(cell++))!=0 ){}  /* Skip the data size number */
    }
    getVarint(cell, pSize);
  }
  return SQLITE_OK;
}

................................................................................
  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( pPage->isInit );
  pageIntegrity(pPage);
  if( pPage->zeroData ){
    *pSize = 0;
  }else{
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
................................................................................
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    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 ){
................................................................................
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    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 ){
................................................................................
        if( pCellKey==0 ) return SQLITE_NOMEM;
        rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey);
        c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey);
        sqliteFree(pCellKey);
        if( rc ) return rc;
      }
      if( c==0 ){



        pCur->iMatch = c;
        if( pRes ) *pRes = 0;
        return SQLITE_OK;

      }
      if( c<0 ){
        lwr = pCur->idx+1;
      }else{
        upr = pCur->idx-1;
      }
    }
................................................................................
** 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 = pCur->pPage;

  assert( pRes!=0 );
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pPage->isInit );
  assert( pCur->idx<pPage->nCell );
................................................................................
        pCur->isValid = 0;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;



    return SQLITE_OK;


  }
  *pRes = 0;
  if( pPage->leaf ){
    return SQLITE_OK;
  }
  rc = moveToLeftmost(pCur);
  return rc;
................................................................................
        *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;



    rc = SQLITE_OK;

  }
  *pRes = 0;
  return rc;
}

/*
** The TRACE macro will print high-level status information about the
................................................................................
  int nHeader;

  /* Fill in the header. */
  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 ){
    pSrc = pData;
    nSrc = nData;
    nData = 0;
................................................................................
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  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 */
................................................................................
  /* 
  ** Return without doing any work if pPage is neither overfull nor
  ** underfull.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  if( !pPage->isOverfull && pPage->nFree<pBt->pageSize/2 && pPage->nCell>=2){
    relinkCellList(pPage);
    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be balanced.  If there is no parent,
  ** it means this page is the root page and special rules apply.
................................................................................
  ** into aTemp[].  In this wall, all cells in apCell[] are without
  ** child pointers.  If siblings are not leaves, then all cell in
  ** apCell[] include child pointers.  Either way, all cells in apCell[]
  ** are alike.
  */
  nCell = 0;
  leafCorrection = pPage->leaf*4;

  for(i=0; i<nOld; i++){
    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 );
      }
      nCell++;

    }
  }

  /*
  ** Figure out the number of pages needed to hold all nCell cells.
  ** Store this number in "k".  Also compute szNew[] which is the total
  ** size of all cells on the i-th page and cntNew[] which is the index
................................................................................
  */
  usableSpace = pBt->pageSize - 10 + leafCorrection;
  for(subtotal=k=i=0; i<nCell; i++){
    subtotal += szCell[i];
    if( subtotal > usableSpace ){
      szNew[k] = subtotal - szCell[i];
      cntNew[k] = i;

      subtotal = 0;
      k++;
    }
  }
  szNew[k] = subtotal;
  cntNew[k] = nCell;
  k++;
................................................................................
      insertCell(pNew, pNew->nCell, apCell[j], szCell[j], 0);
      j++;
    }
    assert( pNew->nCell>0 );
    assert( !pNew->isOverfull );
    relinkCellList(pNew);
    if( i<nNew-1 && j<nCell ){
      u8 *pCell = apCell[j];
      u8 *pTemp;



      if( !pNew->leaf ){
        memcpy(&pNew->aData[6], pCell+2, 4);
        pTemp = 0;









      }else{
        pCell -= 4;
        pTemp = aInsBuf[i];
      }
      insertCell(pParent, nxDiv, pCell, szCell[j]+leafCorrection, pTemp);
      put4byte(&pParent->aCell[nxDiv][2], pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
................................................................................
  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);
................................................................................
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;
    int notUsed;
    unsigned char tempCell[MX_CELL_SIZE];

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

** 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.129 2004/05/12 19:18:16 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.
................................................................................

/*
** Page type flags.  An ORed combination of these flags appear as the
** first byte of every BTree page.
*/
#define PTF_INTKEY    0x01
#define PTF_ZERODATA  0x02
#define PTF_LEAFDATA  0x04
#define PTF_LEAF      0x08


/*
** As each page of the file is loaded into memory, an instance of the following
** structure is appended and initialized to zero.  This structure stores
** information about the page that is decoded from the raw file page.
**
** The pParent field points back to the parent page.  This allows us to
................................................................................
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 table stores keys only */
  u8 leafData;                   /* True if tables stores data on leaves only */
  u8 hasData;                    /* True if this page stores data */
  u8 hdrOffset;                  /* 100 for page 1.  0 otherwise */
  u8 needRelink;                 /* True if need to run relinkCellList() */
  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 */
................................................................................
){
  int n;
  if( pPage->leaf ){
    n = 2;
  }else{
    n = 6;
  }
  if( pPage->hasData ){
    n += getVarint(&pCell[n], pnData);
  }else{
    *pnData = 0;
  }
  n += getVarint(&pCell[n], (u64*)pnKey);
  *pnHeader = n;
}

/*
** Compute the total number of bytes that a Cell needs on the main
................................................................................
  hdr = pPage->hdrOffset;
  assert( hdr==(pPage->pgno==1 ? 100 : 0) );
  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  c = pPage->aData[hdr];
  if( pPage->isInit ){
    assert( pPage->leaf == ((c & PTF_LEAF)!=0) );
    assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) );
    assert( pPage->leafData == ((c & PTF_LEAFDATA)!=0) );
    assert( pPage->intKey == ((c & (PTF_INTKEY|PTF_LEAFDATA))!=0) );
    assert( pPage->hasData ==
             !(pPage->zeroData || (!pPage->leaf && pPage->leafData)) );
  }
  data = pPage->aData;
  memset(used, 0, pageSize);
  for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1;
  nFree = 0;
  pc = get2byte(&data[hdr+1]);
  while( pc ){
................................................................................
  }
  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|PTF_LEAFDATA))!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leafData = (c & PTF_LEAFDATA)!=0;
  pPage->leaf = (c & PTF_LEAF)!=0;
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  pPage->isOverfull = 0;
  pPage->needRelink = 0;
  pPage->idxShift = 0;
  pageSize = pPage->pBt->pageSize;

  /* Initialize the cell count and cell pointers */
  pc = get2byte(&data[hdr+3]);
................................................................................
  put2byte(&data[hdr+1], first);
  put2byte(&data[first+2], pBt->pageSize - first);
  sqliteFree(pPage->aCell);
  pPage->aCell = 0;
  pPage->nCell = 0;
  pPage->nCellAlloc = 0;
  pPage->nFree = pBt->pageSize - first;
  pPage->intKey = (flags & (PTF_INTKEY|PTF_LEAFDATA))!=0;

  pPage->zeroData = (flags & PTF_ZERODATA)!=0;
  pPage->leafData = (flags & PTF_LEAFDATA)!=0;
  pPage->leaf = (flags & PTF_LEAF)!=0;
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  pPage->hdrOffset = hdr;
  pPage->isOverfull = 0;
  pPage->needRelink = 0;
  pPage->idxShift = 0;
  pPage->isInit = 1;
  pageIntegrity(pPage);
}
................................................................................
  if( rc ) return rc;
  memcpy(data, zMagicHeader, sizeof(zMagicHeader));
  assert( sizeof(zMagicHeader)==16 );
  put2byte(&data[16], SQLITE_PAGE_SIZE);
  data[18] = 1;
  data[19] = 1;
  put2byte(&data[22], (SQLITE_PAGE_SIZE-10)/4-12);
  zeroPage(pP1, PTF_INTKEY|PTF_LEAF );
  return SQLITE_OK;
}

/*
** Attempt to start a new transaction.
**
** A transaction must be started before attempting any changes
................................................................................
    assert( pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
    }
    if( pPage->hasData ){
      while( (0x80&*(cell++))!=0 ){}  /* Skip the data size number */
    }
    getVarint(cell, pSize);
  }
  return SQLITE_OK;
}

................................................................................
  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( pPage->isInit );
  pageIntegrity(pPage);
  if( !pPage->hasData ){
    *pSize = 0;
  }else{
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
................................................................................
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->hasData ){
    aPayload += getVarint(aPayload, &nData);
  }else{
    nData = 0;
  }
  aPayload += getVarint(aPayload, (u64*)&nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  assert( offset>=0 );
  if( skipKey ){
................................................................................
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
  if( pPage->hasData ){
    aPayload += getVarint(aPayload, &nData);
  }else{
    nData = 0;
  }
  aPayload += getVarint(aPayload, (u64*)&nKey);
  if( pPage->intKey ){
    nKey = 0;
  }
  maxLocal = pBt->maxLocal;
  if( skipKey ){
................................................................................
        if( pCellKey==0 ) return SQLITE_NOMEM;
        rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey);
        c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey);
        sqliteFree(pCellKey);
        if( rc ) return rc;
      }
      if( c==0 ){
        if( pPage->leafData && !pPage->leaf ){
          break;
        }else{
          pCur->iMatch = c;
          if( pRes ) *pRes = 0;
          return SQLITE_OK;
        }
      }
      if( c<0 ){
        lwr = pCur->idx+1;
      }else{
        upr = pCur->idx-1;
      }
    }
................................................................................
** 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 = pCur->pPage;

  assert( pRes!=0 );
  if( pCur->isValid==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pPage->isInit );
  assert( pCur->idx<pPage->nCell );
................................................................................
        pCur->isValid = 0;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;
    if( pPage->leafData ){
      rc = sqlite3BtreeNext(pCur, pRes);
    }else{
      rc = SQLITE_OK;
    }
    return rc;
  }
  *pRes = 0;
  if( pPage->leaf ){
    return SQLITE_OK;
  }
  rc = moveToLeftmost(pCur);
  return rc;
................................................................................
        *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;
    if( pPage->leafData ){
      rc = sqlite3BtreePrevious(pCur, pRes);
    }else{
      rc = SQLITE_OK;
    }
  }
  *pRes = 0;
  return rc;
}

/*
** The TRACE macro will print high-level status information about the
................................................................................
  int nHeader;

  /* Fill in the header. */
  nHeader = 2;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( pPage->hasData ){
    nHeader += putVarint(&pCell[nHeader], nData);
  }
  nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey);
  
  /* Fill in the payload */
  if( !pPage->hasData ){
    nData = 0;
  }
  nPayload = nData;
  if( pPage->intKey ){
    pSrc = pData;
    nSrc = nData;
    nData = 0;
................................................................................
  int nNew;                    /* Number of pages in apNew[] */
  int nDiv;                    /* Number of cells in apDiv[] */
  int i, j, k;                 /* Loop counters */
  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 leafData;                /* True if pPage is a leaf of a LEAFDATA tree */
  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 */
................................................................................
  /* 
  ** Return without doing any work if pPage is neither overfull nor
  ** underfull.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  if( !pPage->isOverfull && pPage->nFree<pBt->pageSize*2/3 && pPage->nCell>=2){
    relinkCellList(pPage);
    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be balanced.  If there is no parent,
  ** it means this page is the root page and special rules apply.
................................................................................
  ** into aTemp[].  In this wall, all cells in apCell[] are without
  ** child pointers.  If siblings are not leaves, then all cell in
  ** apCell[] include child pointers.  Either way, all cells in apCell[]
  ** are alike.
  */
  nCell = 0;
  leafCorrection = pPage->leaf*4;
  leafData = pPage->leafData && pPage->leaf;
  for(i=0; i<nOld; i++){
    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 ){
      if( leafData ){
        int sz = cellSize(pParent, apDiv[i]);
        dropCell(pParent, nxDiv, sz);
      }else{
        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 );
        }
        nCell++;
      }
    }
  }

  /*
  ** Figure out the number of pages needed to hold all nCell cells.
  ** Store this number in "k".  Also compute szNew[] which is the total
  ** size of all cells on the i-th page and cntNew[] which is the index
................................................................................
  */
  usableSpace = pBt->pageSize - 10 + leafCorrection;
  for(subtotal=k=i=0; i<nCell; i++){
    subtotal += szCell[i];
    if( subtotal > usableSpace ){
      szNew[k] = subtotal - szCell[i];
      cntNew[k] = i;
      if( leafData ){ i--; }
      subtotal = 0;
      k++;
    }
  }
  szNew[k] = subtotal;
  cntNew[k] = nCell;
  k++;
................................................................................
      insertCell(pNew, pNew->nCell, apCell[j], szCell[j], 0);
      j++;
    }
    assert( pNew->nCell>0 );
    assert( !pNew->isOverfull );
    relinkCellList(pNew);
    if( i<nNew-1 && j<nCell ){
      u8 *pCell;
      u8 *pTemp;
      int sz;
      pCell = apCell[j];
      sz = szCell[j] + leafCorrection;
      if( !pNew->leaf ){
        memcpy(&pNew->aData[6], pCell+2, 4);
        pTemp = 0;
      }else if( leafData ){
        i64 nKey;
        u64 nData;
        int nHeader;
        j--;
        parseCellHeader(pNew, apCell[j], &nData, &nKey, &nHeader);
        pCell = aInsBuf[i];
        fillInCell(pParent, pCell, 0, nKey, 0, 0, &sz);
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = aInsBuf[i];
      }
      insertCell(pParent, nxDiv, pCell, sz, pTemp);
      put4byte(&pParent->aCell[nxDiv][2], pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
................................................................................
  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 );
  assert( pPage->leaf || !pPage->leafData );
  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);
................................................................................
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    unsigned char *pNext;
    int szNext;
    int notUsed;
    unsigned char tempCell[MX_CELL_SIZE];
    assert( !pPage->leafData );
    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);
................................................................................
  rc = getPage(pBt, (Pgno)pgno, &pPage);
  if( rc ){
    return rc;
  }
  hdr = pPage->hdrOffset;
  data = pPage->aData;
  c = data[hdr];
  pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (c & PTF_ZERODATA)!=0;
  pPage->leafData = (c & PTF_LEAFDATA)!=0;
  pPage->leaf = (c & PTF_LEAF)!=0;
  pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
  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 ){

**    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.
*/
................................................................................

const char *sqlite3BtreeGetFilename(Btree *);
int sqlite3BtreeCopyFile(Btree *, Btree *);

/* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR
** of the following flags:
*/
#define BTREE_INTKEY     1      /* Table has only 64-bit integer keys */
#define BTREE_ZERODATA   2      /* Table has keys only - no data */


int sqlite3BtreeDropTable(Btree*, int);
int sqlite3BtreeClearTable(Btree*, int);
int sqlite3BtreeGetMeta(Btree*, int idx, u32 *pValue);
int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);

int sqlite3BtreeCursor(

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

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................

const char *sqlite3BtreeGetFilename(Btree *);
int sqlite3BtreeCopyFile(Btree *, Btree *);

/* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR
** of the following flags:
*/
#define BTREE_INTKEY     1    /* Table has only 64-bit signed integer keys */
#define BTREE_ZERODATA   2    /* Table has keys only - no data */
#define BTREE_LEAFDATA   4    /* Data stored in leaves only.  Implies INTKEY */

int sqlite3BtreeDropTable(Btree*, int);
int sqlite3BtreeClearTable(Btree*, int);
int sqlite3BtreeGetMeta(Btree*, int idx, u32 *pValue);
int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);

int sqlite3BtreeCursor(

#    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: btree5.test,v 1.2 2004/05/11 00:58:56 drh Exp $


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

# Attempting to read table 1 of an empty file gives an SQLITE_EMPTY
# error.
................................................................................
    if {[set data [btree_data $c1]] ne "data-for-[btree_key $c1]"} {
      return "wrong data for entry $cnt"
    }
    set n [string length $data]
    set fdata1 [btree_fetch_data $c1 $n]
    set fdata2 [btree_fetch_data $c1 -1]
    if {$fdata1 ne "" && $fdata1 ne $data} {
puts "fdata1=[list $fdata1] data=[list $data]"
      return "DataFetch returned the wrong value with amt=$n"
    }
    if {$fdata1 ne $fdata2} {
      return "DataFetch returned the wrong value when amt=-1"
    }
    if {$n>10} {
      set fdata3 [btree_fetch_data $c1 10]
................................................................................
set c1 [btree_cursor $b1 1 1]
set btree_trace 0

# Do the tests.
#
set cnt 0
for {set i 1} {$i<=100} {incr i} {
  do_test test5-2.$i.1 {
    random_inserts 200
    incr cnt 200
    check_table $cnt
  } {}
  do_test test5-2.$i.2 {
    btree_integrity_check $b1 1
  } {}
  do_test test5-2.$i.3 {
    random_deletes 190
    incr cnt -190
    check_table $cnt
  } {}
  do_test test5-2.$i.4 {
    btree_integrity_check $b1 1
  } {}
}

btree_close_cursor $c1
btree_commit $b1
btree_begin_transaction $b1

#    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: btree5.test,v 1.3 2004/05/12 19:18:17 drh Exp $


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

# Attempting to read table 1 of an empty file gives an SQLITE_EMPTY
# error.
................................................................................
    if {[set data [btree_data $c1]] ne "data-for-[btree_key $c1]"} {
      return "wrong data for entry $cnt"
    }
    set n [string length $data]
    set fdata1 [btree_fetch_data $c1 $n]
    set fdata2 [btree_fetch_data $c1 -1]
    if {$fdata1 ne "" && $fdata1 ne $data} {

      return "DataFetch returned the wrong value with amt=$n"
    }
    if {$fdata1 ne $fdata2} {
      return "DataFetch returned the wrong value when amt=-1"
    }
    if {$n>10} {
      set fdata3 [btree_fetch_data $c1 10]
................................................................................
set c1 [btree_cursor $b1 1 1]
set btree_trace 0

# Do the tests.
#
set cnt 0
for {set i 1} {$i<=100} {incr i} {
  do_test btree5-2.$i.1 {
    random_inserts 200
    incr cnt 200
    check_table $cnt
  } {}
  do_test btree5-2.$i.2 {
    btree_integrity_check $b1 1
  } {}
  do_test btree5-2.$i.3 {
    random_deletes 190
    incr cnt -190
    check_table $cnt
  } {}
  do_test btree5-2.$i.4 {
    btree_integrity_check $b1 1
  } {}
}

btree_close_cursor $c1
btree_commit $b1
btree_begin_transaction $b1

# 2004 May 10
#
# 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 regression tests for SQLite library.  The
# focus of this script is btree database backend - specifically
# the B+tree tables.  B+trees store all data on the leaves rather
# that storing data with keys on interior nodes.
#
# $Id: btree6.test,v 1.1 2004/05/12 19:18:17 drh Exp $


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


# Insert many entries into the table that cursor $cur points to.
# The table should be an INTKEY table.
#
# Stagger the inserts.  After the inserts complete, go back and do
# deletes.  Stagger the deletes too.  Repeat this several times.
#

# Do N inserts into table $tab using random keys between 0 and 1000000
#
proc random_inserts {cur N} {
  global inscnt
  while {$N>0} {
    set k [expr {int(rand()*1000000)}]
    if {[btree_move_to $cur $k]==0} {
      continue;  # entry already exists
    }
    incr inscnt
    btree_insert $cur $k data-for-$k
    incr N -1
  }
}
set inscnt 0

# Do N delete from the table that $cur points to.
#
proc random_deletes {cur N} {
  while {$N>0} {
    set k [expr {int(rand()*1000000)}]
    btree_move_to $cur $k
    btree_delete $cur
    incr N -1
  }
}

# Make sure the table that $cur points to has exactly N entries.  
# Make sure the data for each entry agrees with its key.
#
proc check_table {cur N} {
  btree_first $cur
  set cnt 0
  while {![btree_eof $cur]} {
    if {[set data [btree_data $cur]] ne "data-for-[btree_key $cur]"} {
      return "wrong data for entry $cnt"
    }
    set n [string length $data]
    set fdata1 [btree_fetch_data $cur $n]
    set fdata2 [btree_fetch_data $cur -1]
    if {$fdata1 ne "" && $fdata1 ne $data} {
      return "DataFetch returned the wrong value with amt=$n"
    }
    if {$fdata1 ne $fdata2} {
      return "DataFetch returned the wrong value when amt=-1"
    }
    if {$n>10} {
      set fdata3 [btree_fetch_data $cur 10]
      if {$fdata3 ne [string range $data 0 9]} {
        return "DataFetch returned the wrong value when amt=10"
      }
    }
    incr cnt
    btree_next $cur
  }
  if {$cnt!=$N} {
    return "wrong number of entries.  Got $cnt.  Looking for $N"
  }
  return {}
}

# Initialize the database
#
file delete -force test1.bt
file delete -force test1.bt-journal
set b1 [btree_open test1.bt 2000 0]
btree_begin_transaction $b1
set tab [btree_create_table $b1 5]
set cur [btree_cursor $b1 $tab 1]
set btree_trace 0
expr srand(1)

# Do the tests.
#
set cnt 0
for {set i 1} {$i<=100} {incr i} {
  do_test btree6-1.$i.1 {
    random_inserts $cur 200
    incr cnt 200
    check_table $cur $cnt
  } {}
  do_test btree6-1.$i.2 {
    btree_integrity_check $b1 1 $tab
  } {}
  do_test btree6-1.$i.3 {
    random_deletes $cur 190
    incr cnt -190
    check_table $cur $cnt
  } {}
  do_test btree6-1.$i.4 {
    btree_integrity_check $b1 1 $tab
  } {}
}

btree_close_cursor $cur
btree_commit $b1

finish_test