** 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.111 2004/05/07 17:57:50 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.
................................................................................
  BtCursor *pShared;        /* Loop of cursors with the same root page */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  u8 wrFlag;                /* True if writable */
  u8 eSkip;                 /* Determines if next step operation is a no-op */
  u8 iMatch;                /* compare result from last sqlite3BtreeMoveto() */


};

/*
** Legal values for BtCursor.eSkip.
*/
#define SKIP_NONE     0   /* Always step the cursor */
#define SKIP_NEXT     1   /* The next sqlite3BtreeNext() is a no-op */
#define SKIP_PREV     2   /* The next sqlite3BtreePrevious() is a no-op */
#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */

/*
** Read or write a two-, four-, and eight-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
static u32 get4byte(unsigned char *p){
................................................................................
  oldPage = pPage->aData;
  hdr = pPage->hdrOffset;
  addr = 3+hdr;
  n = 6+hdr;
  if( !pPage->leaf ){
    n += 4;
  }

  start = n;
  pc = get2byte(&oldPage[addr]);
  i = 0;
  while( pc>0 ){
    assert( n<pPage->pBt->pageSize );
    size = cellSize(pPage, &oldPage[pc]);
    memcpy(&newPage[n], &oldPage[pc], size);
    put2byte(&newPage[addr],n);
    pPage->aCell[i] = &oldPage[n];
    n += size;
    addr = pc;
    pc = get2byte(&oldPage[pc]);
  }

  leftover = pPage->pBt->pageSize - n;
  assert( leftover>=0 );
  assert( pPage->nFree==leftover );
  if( leftover<4 ){
    oldPage[hdr+5] = leftover;
    leftover = 0;
    n = pPage->pBt->pageSize;
  }
  memcpy(&oldPage[start], &newPage[start], n-start);
  if( leftover==0 ){
    put2byte(&oldPage[hdr+3], 0);
  }else if( leftover>=4 ){
    put2byte(&oldPage[hdr+3], n);
    put2byte(&oldPage[n], 0);
    put2byte(&oldPage[n+2], leftover);
    memset(&oldPage[n+4], 0, leftover-4);
  }

}

/*
** Allocate nByte bytes of space on a page.  If nByte is less than
** 4 it is rounded up to 4.
**
** Return the index into pPage->aData[] of the first byte of
................................................................................
  int rc;
  rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_commit(pBt->pPager);
  pBt->inTrans = 0;
  pBt->inStmt = 0;
  unlockBtreeIfUnused(pBt);
  return rc;
}

















/*
** 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.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeRollback(Btree *pBt){
  int rc;
  BtCursor *pCur;
  if( pBt->inTrans==0 ) return SQLITE_OK;
  pBt->inTrans = 0;
  pBt->inStmt = 0;
  rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_rollback(pBt->pPager);
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    MemPage *pPage = pCur->pPage;
    if( pPage && !pPage->isInit ){
      releasePage(pPage);
      pCur->pPage = 0;
    }
  }
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Set the checkpoint for the current transaction.  The checkpoint serves
** as a sub-transaction that can be rolled back independently of the
................................................................................
**
** 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.
*/
int sqlite3BtreeRollbackStmt(Btree *pBt){
  int rc;
  BtCursor *pCur;
  if( pBt->inStmt==0 || pBt->readOnly ) return SQLITE_OK;
  rc = sqlite3pager_stmt_rollback(pBt->pPager);
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    MemPage *pPage = pCur->pPage;
    if( pPage && !pPage->isInit ){
      releasePage(pPage);
      pCur->pPage = 0;
    }
  }

  pBt->inStmt = 0;
  return rc;
}

/*
** Default key comparison function to be used if no comparison function
** is specified on the sqlite3BtreeCursor() call.
................................................................................
    goto create_cursor_exception;
  }
  pCur->xCompare = xCmp ? xCmp : dfltCompare;
  pCur->pArg = pArg;
  pCur->pBt = pBt;
  pCur->wrFlag = wrFlag;
  pCur->idx = 0;
  pCur->eSkip = SKIP_INVALID;
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;
  pRing = pBt->pCursor;
  while( pRing && pRing->pgnoRoot!=pCur->pgnoRoot ){ pRing = pRing->pNext; }
................................................................................
  if( pRing ){
    pCur->pShared = pRing->pShared;
    pRing->pShared = pCur;
  }else{
    pCur->pShared = pCur;
  }
  pBt->pCursor = pCur;


  *ppCur = pCur;
  return SQLITE_OK;

create_cursor_exception:
  *ppCur = 0;
  if( pCur ){
    releasePage(pCur->pPage);
................................................................................
** 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;


  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    *pSize = 0;
  }else{



    unsigned char *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 */
    }
................................................................................
  int rc;
  MemPage *pPage;
  Btree *pBt;
  u64 nData, nKey;
  int maxLocal, ovflSize;

  assert( pCur!=0 && pCur->pPage!=0 );

  pBt = pCur->pBt;
  pPage = pCur->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 */
................................................................................
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  MemPage *pPage;

  assert( amt>=0 );
  assert( offset>=0 );



  assert( pCur->pPage!=0 );
  pPage = pCur->pPage;
  if( pCur->idx >= pPage->nCell || pPage->intKey ){
    assert( amt==0 );
    return SQLITE_OK;
  }
  return getPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}

/*
** Return a pointer to the key of record that cursor pCur
** is point to if the entire key is in contiguous memory.
** If the key is split up among multiple tables, return 0.
................................................................................
*/
void *sqlite3BtreeKeyFetch(BtCursor *pCur){
  unsigned char *aPayload;
  MemPage *pPage;
  Btree *pBt;
  u64 nData, nKey;

  assert( pCur!=0 && pCur->pPage!=0 );





  pBt = pCur->pBt;
  pPage = pCur->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 ){
    aPayload += getVarint(aPayload, &nData);
  }
  aPayload += getVarint(aPayload, &nKey);
  if( pPage->intKey || nKey>pBt->maxLocal ){
    return 0;
  }
  return aPayload;
}


/*
................................................................................
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  MemPage *pPage;






  pPage = pCur->pPage;
  assert( pPage!=0 );

  if( pCur->idx >= pPage->nCell || pPage->zeroData ){
    *pSize = 0;
  }else{
    unsigned char *cell;
    u64 size;

    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
    }
    getVarint(cell, &size);
    assert( (size & 0x00000000ffffffff)==size );
................................................................................
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  MemPage *pPage;


  assert( amt>=0 );
  assert( offset>=0 );
  assert( pCur->pPage!=0 );
  pPage = pCur->pPage;
  if( pCur->idx >= pPage->nCell ){
    return 0;
  }
  return getPayload(pCur, offset, amt, pBuf, 1);
}

/*
** Move the cursor down to a new child page.  The newPgno argument is the
** page number of the child page in the byte order of the disk image.
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  int rc;
  MemPage *pNewPage;
  MemPage *pOldPage;
  Btree *pBt = pCur->pBt;


  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
  pOldPage->idxShift = 0;
  releasePage(pOldPage);
  pCur->pPage = pNewPage;
................................................................................
*/
static void moveToParent(BtCursor *pCur){
  Pgno oldPgno;
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;


  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !isRootPage(pPage) );
  pParent = pPage->pParent;
  assert( pParent!=0 );
  idxParent = pPage->idxParent;
  sqlite3pager_ref(pParent->aData);
................................................................................
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;
  int rc;
  Btree *pBt = pCur->pBt;

  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0);


  if( rc ) return rc;

  releasePage(pCur->pPage);
  pCur->pPage = pRoot;
  pCur->idx = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]);
    assert( subpage>0 );
    rc = moveToChild(pCur, subpage);
  }

  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
*/
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc;
  MemPage *pPage;


  while( !(pPage = pCur->pPage)->leaf ){
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    pgno = get4byte(&pPage->aCell[pCur->idx][2]);
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  return SQLITE_OK;
................................................................................
** finds the right-most entry beneath the *page*.
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc;
  MemPage *pPage;


  while( !(pPage = pCur->pPage)->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+6]);
    pCur->idx = pPage->nCell;
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  pCur->idx = pPage->nCell - 1;
................................................................................

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


  rc = moveToRoot(pCur);
  if( rc ) return rc;

  if( pCur->pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }

  *pRes = 0;
  rc = moveToLeftmost(pCur);
  pCur->eSkip = SKIP_NONE;
  return rc;
}

/* Move the cursor to the last entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeLast(BtCursor *pCur, int *pRes){
  int rc;
  if( pCur->pPage==0 ) return SQLITE_ABORT;


  rc = moveToRoot(pCur);
  if( rc ) return rc;
  assert( pCur->pPage->isInit );

  if( pCur->pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }

  *pRes = 0;
  rc = moveToRightmost(pCur);
  pCur->eSkip = SKIP_NONE;
  return rc;
}

/* Move the cursor so that it points to an entry near pKey/nKey.
** Return a success code.
**
** For INTKEY tables, only the nKey parameter is used.  pKey is
................................................................................
**                  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->pPage==0 ) return SQLITE_ABORT;

  pCur->eSkip = SKIP_NONE;


  rc = moveToRoot(pCur);
  if( rc ) return rc;






  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
................................................................................
    }else if( lwr>=pPage->nCell ){
      chldPg = get4byte(&pPage->aData[pPage->hdrOffset+6]);
    }else{
      chldPg = get4byte(&pPage->aCell[lwr][2]);
    }
    if( chldPg==0 ){
      pCur->iMatch = c;

      if( pRes ) *pRes = c;
      return SQLITE_OK;
    }
    pCur->idx = lwr;
    rc = moveToChild(pCur, chldPg);

    if( rc ) return rc;

  }
  /* NOT REACHED */
}












/*
** Advance the cursor to the next entry in the database.  If
** successful then set *pRes=0.  If the cursor
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  int rc;
  MemPage *pPage = pCur->pPage;
  assert( pRes!=0 );
  if( pPage==0 ){
    *pRes = 1;
    return SQLITE_ABORT;
  }
  assert( pPage->isInit );
  assert( pCur->eSkip!=SKIP_INVALID );
  if( pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }

  assert( pCur->idx<pPage->nCell );
  if( pCur->eSkip==SKIP_NEXT ){
    pCur->eSkip = SKIP_NONE;
    *pRes = 0;
    return SQLITE_OK;
  }
  pCur->eSkip = SKIP_NONE;
  pCur->idx++;
  if( pCur->idx>=pPage->nCell ){
    if( !pPage->leaf ){
      rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+6]));
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      *pRes = 0;
      return rc;
    }
    do{
      if( isRootPage(pPage) ){
        *pRes = 1;

        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;
    return SQLITE_OK;
................................................................................
** was already pointing to the first entry in the database before
** this routine was called, then set *pRes=1.
*/
int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;
  MemPage *pPage;
  pPage = pCur->pPage;
  if( pPage==0 ){
    *pRes = 1;
    return SQLITE_ABORT;
  }
  assert( pPage->isInit );
  assert( pCur->eSkip!=SKIP_INVALID );
  if( pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  if( pCur->eSkip==SKIP_PREV ){
    pCur->eSkip = SKIP_NONE;
    *pRes = 0;
    return SQLITE_OK;
  }
  pCur->eSkip = SKIP_NONE;
  assert( pCur->idx>=0 );
  if( !pPage->leaf ){
    pgno = get4byte(&pPage->aCell[pCur->idx][2]);
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
    while( pCur->idx==0 ){
      if( isRootPage(pPage) ){

        if( pRes ) *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;
    rc = SQLITE_OK;
................................................................................
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
  unsigned char *oldCell;
  unsigned char newCell[MX_CELL_SIZE];

  if( pCur->pPage==0 ){
    return SQLITE_ABORT;  /* A rollback destroyed this cursor */
  }
  if( !pBt->inTrans || nKey+nData==0 ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( !pCur->wrFlag ){
................................................................................
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew);
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  moveToRoot(pCur);
  pCur->eSkip = SKIP_INVALID;
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
** is left pointing at a random location.
*/
................................................................................
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild;
  Btree *pBt = pCur->pBt;

  assert( pPage->isInit );
  if( pCur->pPage==0 ){
    return SQLITE_ABORT;  /* A rollback destroyed this cursor */
  }
  if( !pBt->inTrans ){
    /* Must start a transaction before doing a delete */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){
................................................................................
  }
  if( !pPage->leaf ){
    printf("right_child: %d\n", get4byte(&pPage->aData[6]));
  }
  nFree = 0;
  i = 0;
  idx = get2byte(&pPage->aData[hdrOffset+1]);
  while( idx>0 && idx<SQLITE_USABLE_SIZE ){
    int sz = get2byte(&pPage->aData[idx+2]);
    sprintf(range,"%d..%d", idx, idx+sz-1);
    nFree += sz;
    printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
       i, range, sz, nFree);
    idx = get2byte(&pPage->aData[idx]);
    i++;
................................................................................
  }else{
    aResult[3] = 0;
    aResult[6] = 0;
  }
  aResult[4] = pPage->nFree;
  cnt = 0;
  idx = get2byte(&pPage->aData[pPage->hdrOffset+1]);
  while( idx>0 && idx<SQLITE_USABLE_SIZE ){
    cnt++;
    idx = get2byte(&pPage->aData[idx]);
  }
  aResult[5] = cnt;
  aResult[7] = pPage->leaf ? 0 : get4byte(&pPage->aData[pPage->hdrOffset+6]);
  return SQLITE_OK;
}
................................................................................
*/
int sqlite3BtreeCopyFile(Btree *pBtTo, Btree *pBtFrom){
  int rc = SQLITE_OK;
  Pgno i, nPage, nToPage;

  if( !pBtTo->inTrans || !pBtFrom->inTrans ) return SQLITE_ERROR;
  if( pBtTo->pCursor ) return SQLITE_BUSY;
  memcpy(pBtTo->pPage1, pBtFrom->pPage1, SQLITE_USABLE_SIZE);
  rc = sqlite3pager_overwrite(pBtTo->pPager, 1, pBtFrom->pPage1);
  nToPage = sqlite3pager_pagecount(pBtTo->pPager);
  nPage = sqlite3pager_pagecount(pBtFrom->pPager);
  for(i=2; rc==SQLITE_OK && i<=nPage; i++){
    void *pPage;
    rc = sqlite3pager_get(pBtFrom->pPager, i, &pPage);
    if( rc ) break;

** 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.112 2004/05/07 23:50:57 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.
................................................................................
  BtCursor *pShared;        /* Loop of cursors with the same root page */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  u8 wrFlag;                /* True if writable */

  u8 iMatch;                /* compare result from last sqlite3BtreeMoveto() */
  u8 isValid;               /* TRUE if points to a valid entry */
  u8 status;                /* Set to SQLITE_ABORT if cursors is invalidated */
};









/*
** Read or write a two-, four-, and eight-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
static u32 get4byte(unsigned char *p){
................................................................................
  oldPage = pPage->aData;
  hdr = pPage->hdrOffset;
  addr = 3+hdr;
  n = 6+hdr;
  if( !pPage->leaf ){
    n += 4;
  }
  memcpy(&newPage[hdr], &oldPage[hdr], n-hdr);
  start = n;
  pc = get2byte(&oldPage[addr]);
  i = 0;
  while( pc>0 ){
    assert( n<pPage->pBt->pageSize );
    size = cellSize(pPage, &oldPage[pc]);
    memcpy(&newPage[n], &oldPage[pc], size);
    put2byte(&newPage[addr],n);
    pPage->aCell[i++] = &oldPage[n];
    n += size;
    addr = pc;
    pc = get2byte(&oldPage[pc]);
  }
  assert( i==pPage->nCell );
  leftover = pPage->pBt->pageSize - n;
  assert( leftover>=0 );
  assert( pPage->nFree==leftover );
  if( leftover<4 ){
    oldPage[hdr+5] = leftover;
    leftover = 0;
    n = pPage->pBt->pageSize;
  }
  memcpy(&oldPage[hdr], &newPage[hdr], n-hdr);
  if( leftover==0 ){
    put2byte(&oldPage[hdr+1], 0);
  }else if( leftover>=4 ){
    put2byte(&oldPage[hdr+1], n);
    put2byte(&oldPage[n], 0);
    put2byte(&oldPage[n+2], leftover);
    memset(&oldPage[n+4], 0, leftover-4);
  }
  oldPage[hdr+5] = 0;
}

/*
** Allocate nByte bytes of space on a page.  If nByte is less than
** 4 it is rounded up to 4.
**
** Return the index into pPage->aData[] of the first byte of
................................................................................
  int rc;
  rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_commit(pBt->pPager);
  pBt->inTrans = 0;
  pBt->inStmt = 0;
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Invalidate all cursors
*/
static void invalidateCursors(Btree *pBt){
  BtCursor *pCur;
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    MemPage *pPage = pCur->pPage;
    if( pPage && !pPage->isInit ){
      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.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeRollback(Btree *pBt){
  int rc;

  if( pBt->inTrans==0 ) return SQLITE_OK;
  pBt->inTrans = 0;
  pBt->inStmt = 0;
  rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_rollback(pBt->pPager);
  invalidateCursors(pBt);






  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Set the checkpoint for the current transaction.  The checkpoint serves
** as a sub-transaction that can be rolled back independently of the
................................................................................
**
** 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.
*/
int sqlite3BtreeRollbackStmt(Btree *pBt){
  int rc;

  if( pBt->inStmt==0 || pBt->readOnly ) return SQLITE_OK;
  rc = sqlite3pager_stmt_rollback(pBt->pPager);







  invalidateCursors(pBt);
  pBt->inStmt = 0;
  return rc;
}

/*
** Default key comparison function to be used if no comparison function
** is specified on the sqlite3BtreeCursor() call.
................................................................................
    goto create_cursor_exception;
  }
  pCur->xCompare = xCmp ? xCmp : dfltCompare;
  pCur->pArg = pArg;
  pCur->pBt = pBt;
  pCur->wrFlag = wrFlag;
  pCur->idx = 0;

  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;
  pRing = pBt->pCursor;
  while( pRing && pRing->pgnoRoot!=pCur->pgnoRoot ){ pRing = pRing->pNext; }
................................................................................
  if( pRing ){
    pCur->pShared = pRing->pShared;
    pRing->pShared = pCur;
  }else{
    pCur->pShared = pCur;
  }
  pBt->pCursor = pCur;
  pCur->isValid = 0;
  pCur->status = SQLITE_OK;
  *ppCur = pCur;
  return SQLITE_OK;

create_cursor_exception:
  *ppCur = 0;
  if( pCur ){
    releasePage(pCur->pPage);
................................................................................
** 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;
    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 */
    }
................................................................................
  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;
  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 */
................................................................................
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){


  assert( amt>=0 );
  assert( offset>=0 );
  if( pCur->isValid==0 ){
    return pCur->status;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->pPage->intKey==0 );

  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );


  return getPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
}

/*
** Return a pointer to the key of record that cursor pCur
** is point to if the entire key is in contiguous memory.
** If the key is split up among multiple tables, return 0.
................................................................................
*/
void *sqlite3BtreeKeyFetch(BtCursor *pCur){
  unsigned char *aPayload;
  MemPage *pPage;
  Btree *pBt;
  u64 nData, nKey;

  assert( pCur!=0 );
  if( !pCur->isValid ){
    return 0;
  }
  assert( pCur->pPage!=0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  assert( pPage->intKey==0 );
  aPayload = pPage->aCell[pCur->idx];
  aPayload += 2;  /* Skip the next cell index */
  if( !pPage->leaf ){
    aPayload += 4;  /* Skip the child pointer */
  }
  if( !pPage->zeroData ){
    aPayload += getVarint(aPayload, &nData);
  }
  aPayload += getVarint(aPayload, &nKey);
  if( nKey>pBt->maxLocal ){
    return 0;
  }
  return aPayload;
}


/*
................................................................................
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  MemPage *pPage;
  unsigned char *cell;
  u64 size;

  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( pPage->isInit );
  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 */
    }
    getVarint(cell, &size);
    assert( (size & 0x00000000ffffffff)==size );
................................................................................
** begins at "offset".
**
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  assert( amt>=0 );
  assert( offset>=0 );
  assert( pCur->pPage!=0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );



  return getPayload(pCur, offset, amt, pBuf, 1);
}

/*
** Move the cursor down to a new child page.  The newPgno argument is the
** page number of the child page in the byte order of the disk image.
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  int rc;
  MemPage *pNewPage;
  MemPage *pOldPage;
  Btree *pBt = pCur->pBt;

  assert( pCur->isValid );
  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
  pOldPage->idxShift = 0;
  releasePage(pOldPage);
  pCur->pPage = pNewPage;
................................................................................
*/
static void moveToParent(BtCursor *pCur){
  Pgno oldPgno;
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;

  assert( pCur->isValid );
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !isRootPage(pPage) );
  pParent = pPage->pParent;
  assert( pParent!=0 );
  idxParent = pPage->idxParent;
  sqlite3pager_ref(pParent->aData);
................................................................................
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;
  int rc;
  Btree *pBt = pCur->pBt;

  rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0);
  if( rc ){
    pCur->isValid = 0;
    return rc;
  }
  releasePage(pCur->pPage);
  pCur->pPage = pRoot;
  pCur->idx = 0;
  if( pRoot->nCell==0 && !pRoot->leaf ){
    Pgno subpage;
    assert( pRoot->pgno==1 );
    subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]);
    assert( subpage>0 );
    rc = moveToChild(pCur, subpage);
  }
  pCur->isValid = pCur->pPage->nCell>0;
  return rc;
}

/*
** Move the cursor down to the left-most leaf entry beneath the
** entry to which it is currently pointing.
*/
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc;
  MemPage *pPage;

  assert( pCur->isValid );
  while( !(pPage = pCur->pPage)->leaf ){
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    pgno = get4byte(&pPage->aCell[pCur->idx][2]);
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  return SQLITE_OK;
................................................................................
** finds the right-most entry beneath the *page*.
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc;
  MemPage *pPage;

  assert( pCur->isValid );
  while( !(pPage = pCur->pPage)->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+6]);
    pCur->idx = pPage->nCell;
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  pCur->idx = pPage->nCell - 1;
................................................................................

/* Move the cursor to the first entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
  int rc;
  if( pCur->status ){
    return pCur->status;
  }
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  if( pCur->isValid==0 ){
    assert( pCur->pPage->nCell==0 );
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pCur->pPage->nCell>0 );
  *pRes = 0;
  rc = moveToLeftmost(pCur);

  return rc;
}

/* Move the cursor to the last entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeLast(BtCursor *pCur, int *pRes){
  int rc;
  if( pCur->status ){
    return pCur->status;
  }
  rc = moveToRoot(pCur);
  if( rc ) return rc;

  if( pCur->isValid==0 ){
    assert( pCur->pPage->nCell==0 );
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pCur->isValid );
  *pRes = 0;
  rc = moveToRightmost(pCur);

  return rc;
}

/* Move the cursor so that it points to an entry near pKey/nKey.
** Return a success code.
**
** For INTKEY tables, only the nKey parameter is used.  pKey is
................................................................................
**                  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;
  assert( pCur->pPage );
  assert( pCur->pPage->isInit );
  if( pCur->isValid==0 ){
    assert( pCur->pPage->nCell==0 );
    return SQLITE_OK;
  }
  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
................................................................................
    }else if( lwr>=pPage->nCell ){
      chldPg = get4byte(&pPage->aData[pPage->hdrOffset+6]);
    }else{
      chldPg = get4byte(&pPage->aCell[lwr][2]);
    }
    if( chldPg==0 ){
      pCur->iMatch = c;
      assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
      if( pRes ) *pRes = c;
      return SQLITE_OK;
    }
    pCur->idx = lwr;
    rc = moveToChild(pCur, chldPg);
    if( rc ){
      return rc;
    }
  }
  /* NOT REACHED */
}

/*
** Return TRUE if the cursor is not pointing at an entry of the table.
**
** TRUE will be returned after a call to sqlite3BtreeNext() moves
** past the last entry in the table or sqlite3BtreePrev() moves past
** the first entry.  TRUE is also returned if the table is empty.
*/
int sqlite3BtreeEof(BtCursor *pCur){
  return pCur->isValid==0;
}

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






    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pPage->isInit );
  assert( pCur->idx<pPage->nCell );






  pCur->idx++;
  if( pCur->idx>=pPage->nCell ){
    if( !pPage->leaf ){
      rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+6]));
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      *pRes = 0;
      return rc;
    }
    do{
      if( isRootPage(pPage) ){
        *pRes = 1;
        pCur->isValid = 0;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;
    return SQLITE_OK;
................................................................................
** was already pointing to the first entry in the database before
** this routine was called, then set *pRes=1.
*/
int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;
  MemPage *pPage;
  if( pCur->isValid==0 ){







    *pRes = 1;
    return SQLITE_OK;
  }
  pPage = pCur->pPage;
  assert( pPage->isInit );




  assert( pCur->idx>=0 );
  if( !pPage->leaf ){
    pgno = get4byte(&pPage->aCell[pCur->idx][2]);
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
    while( pCur->idx==0 ){
      if( isRootPage(pPage) ){
        pCur->isValid = 0;
        *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;
    rc = SQLITE_OK;
................................................................................
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
  unsigned char *oldCell;
  unsigned char newCell[MX_CELL_SIZE];

  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( !pBt->inTrans || nKey+nData==0 ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( !pCur->wrFlag ){
................................................................................
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew);
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  moveToRoot(pCur);

  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
** is left pointing at a random location.
*/
................................................................................
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild;
  Btree *pBt = pCur->pBt;

  assert( pPage->isInit );
  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( !pBt->inTrans ){
    /* Must start a transaction before doing a delete */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){
................................................................................
  }
  if( !pPage->leaf ){
    printf("right_child: %d\n", get4byte(&pPage->aData[6]));
  }
  nFree = 0;
  i = 0;
  idx = get2byte(&pPage->aData[hdrOffset+1]);
  while( idx>0 && idx<pPage->pBt->pageSize ){
    int sz = get2byte(&pPage->aData[idx+2]);
    sprintf(range,"%d..%d", idx, idx+sz-1);
    nFree += sz;
    printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
       i, range, sz, nFree);
    idx = get2byte(&pPage->aData[idx]);
    i++;
................................................................................
  }else{
    aResult[3] = 0;
    aResult[6] = 0;
  }
  aResult[4] = pPage->nFree;
  cnt = 0;
  idx = get2byte(&pPage->aData[pPage->hdrOffset+1]);
  while( idx>0 && idx<pPage->pBt->pageSize ){
    cnt++;
    idx = get2byte(&pPage->aData[idx]);
  }
  aResult[5] = cnt;
  aResult[7] = pPage->leaf ? 0 : get4byte(&pPage->aData[pPage->hdrOffset+6]);
  return SQLITE_OK;
}
................................................................................
*/
int sqlite3BtreeCopyFile(Btree *pBtTo, Btree *pBtFrom){
  int rc = SQLITE_OK;
  Pgno i, nPage, nToPage;

  if( !pBtTo->inTrans || !pBtFrom->inTrans ) return SQLITE_ERROR;
  if( pBtTo->pCursor ) return SQLITE_BUSY;
  memcpy(pBtTo->pPage1, pBtFrom->pPage1, pBtFrom->pageSize);
  rc = sqlite3pager_overwrite(pBtTo->pPager, 1, pBtFrom->pPage1);
  nToPage = sqlite3pager_pagecount(pBtTo->pPager);
  nPage = sqlite3pager_pagecount(pBtFrom->pPager);
  for(i=2; rc==SQLITE_OK && i<=nPage; i++){
    void *pPage;
    rc = sqlite3pager_get(pBtFrom->pPager, i, &pPage);
    if( rc ) break;

**    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.38 2004/05/07 13:30:42 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/*
** Forward declarations of structure
*/
................................................................................
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 sqlite3BtreePrevious(BtCursor*, int *pRes);
int sqlite3BtreeKeySize(BtCursor*, u64 *pSize);
int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*);
void *sqlite3BtreeKeyFetch(BtCursor*);
int sqlite3BtreeDataSize(BtCursor*, u32 *pSize);
int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);

**    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.39 2004/05/07 23:50:57 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/*
** Forward declarations of structure
*/
................................................................................
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 sqlite3BtreePrevious(BtCursor*, int *pRes);
int sqlite3BtreeKeySize(BtCursor*, u64 *pSize);
int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*);
void *sqlite3BtreeKeyFetch(BtCursor*);
int sqlite3BtreeDataSize(BtCursor*, u32 *pSize);
int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);

**    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.27 2004/05/07 17:57:50 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sprintf(zBuf,"%d",res);
  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}



























/*
** Usage:   btree_keysize ID
**
** Return the number of bytes of key.  
*/
static int btree_keysize(
................................................................................
     { "btree_cursor",             (Tcl_CmdProc*)btree_cursor             },
     { "btree_close_cursor",       (Tcl_CmdProc*)btree_close_cursor       },
     { "btree_move_to",            (Tcl_CmdProc*)btree_move_to            },
     { "btree_delete",             (Tcl_CmdProc*)btree_delete             },
     { "btree_insert",             (Tcl_CmdProc*)btree_insert             },
     { "btree_next",               (Tcl_CmdProc*)btree_next               },
     { "btree_prev",               (Tcl_CmdProc*)btree_prev               },

     { "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        },

**    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.28 2004/05/07 23:50:57 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sprintf(zBuf,"%d",res);
  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}

/*
** Usage:   btree_eof ID
**
** Return TRUE if the given cursor is not pointing at a valid entry.
** Return FALSE if the cursor does point to a valid entry.
*/
static int btree_eof(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  BtCursor *pCur;
  char zBuf[50];

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

/*
** Usage:   btree_keysize ID
**
** Return the number of bytes of key.  
*/
static int btree_keysize(
................................................................................
     { "btree_cursor",             (Tcl_CmdProc*)btree_cursor             },
     { "btree_close_cursor",       (Tcl_CmdProc*)btree_close_cursor       },
     { "btree_move_to",            (Tcl_CmdProc*)btree_move_to            },
     { "btree_delete",             (Tcl_CmdProc*)btree_delete             },
     { "btree_insert",             (Tcl_CmdProc*)btree_insert             },
     { "btree_next",               (Tcl_CmdProc*)btree_next               },
     { "btree_prev",               (Tcl_CmdProc*)btree_prev               },
     { "btree_eof",                (Tcl_CmdProc*)btree_eof                },
     { "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        },

#    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.16 2004/05/07 17:57:50 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
do_test btree-3.18 {
  btree_next $::c1
  btree_key $::c1
} {600}
do_test btree-3.19 {
  btree_data $::c1
} {6.00}
do_test btree-3.20 {
  btree_next $::c1
  btree_key $::c1
} {0}
do_test btree-3.21 {
  btree_data $::c1
} {}





# Commit the changes, reopen and reread the data
#
do_test btree-3.22 {
  set rc [catch {btree_close_cursor $::c1} msg]
  lappend rc $msg
} {0 {}}
................................................................................
  btree_data $::c1
} {6.00}
do_test btree-3.39 {
  btree_next $::c1
  btree_key $::c1
} {0}
do_test btree-3.40 {
  btree_data $::c1
} {}

do_test btree-3.41 {
  lindex [btree_pager_stats $::b1] 1
} {1}


# Now try a delete
#
................................................................................
  btree_key $::c1
} {400}
do_test btree-4.4 {
  btree_move_to $::c1 0
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==0} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}

................................................................................
#
do_test btree-4.5 {
  btree_commit $::b1
  btree_move_to $::c1 0
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==0} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}

................................................................................
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-4.9 {
  set r {}
  btree_first $::c1
  while 1 {
    set key [btree_key $::c1]
    if {$key==0} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}

................................................................................
     140 150
  btree_commit $::b1
  btree_get_meta $::b1
} {0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150}

proc select_all {cursor} {
  set r {}
  btree_move_to $cursor {}
  while 1 {
    set key [btree_key $cursor]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $cursor]
    btree_next $cursor
  }
  return $r
}
proc select_all_intkey {cursor} {
  set r {}
  btree_move_to $cursor 0
  while 1 {
    set key [btree_key $cursor]
    if {$key==0} break
    lappend r $key
    lappend r [btree_data $cursor]
    btree_next $cursor
  }
  return $r
}
proc select_keys {cursor} {
  set r {}
  btree_move_to $cursor {}
  while 1 {
    set key [btree_key $cursor]
    if {$key==""} break
    lappend r $key
    btree_next $cursor
  }
  return $r
}

# Try to create a new table in the database file
................................................................................
} {1}
do_test btree-6.2.2 {
  set ::c2 [btree_cursor $::b1 $::t2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-6.2.3 {
  btree_insert $::c2 ten 10

  btree_key $::c2
} {ten}
do_test btree-6.3 {
  btree_commit $::b1
  set ::c1 [btree_cursor $::b1 1 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-6.3.1 {
  select_all_intkey $::c1
} {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
#btree_page_dump $::b1 3
do_test btree-6.4 {
  select_all $::c2
} {ten 10}

# Drop the new table, then create it again anew.
................................................................................
} {2}

do_test btree-6.9.1 {
  btree_move_to $::c2 {}
  btree_key $::c2
} {}

# If we drop table 2 it just clears the table.  Table 2 always exists.
#
do_test btree-6.10 {
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  set ::c1 [btree_cursor $::b1 2 1]
  btree_move_to $::c1 {}
  btree_key $::c1
} {}
do_test btree-6.11 {
  btree_commit $::b1
  select_all $::c1
} {}
do_test btree-6.12 {
  select_all $::c2
} {}
do_test btree-6.13 {
  btree_close_cursor $::c2
  lindex [btree_pager_stats $::b1] 1
} {2}

# Check to see that pages defragment properly.  To do this test we will
# 
#   1.  Fill the first page table 2 with data.
#   2.  Delete every other entry of table 2. 
#   3.  Insert a single entry that requires more contiguous
#       space than is available.
#
do_test btree-7.1 {
  btree_begin_transaction $::b1
} {}
catch {unset key}
catch {unset data}
do_test btree-7.2 {
  for {set i 0} {$i<36} {incr i} {






    set key [format %03d $i]
    set data "*** $key ***"
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {8 1}
do_test btree-7.3 {

  btree_move_to $::c1 000
  while {[btree_key $::c1]!=""} {
    btree_delete $::c1
    btree_next $::c1
    btree_next $::c1
  }


  lrange [btree_cursor_dump $::c1] 4 5
} {512 19}
#btree_page_dump $::b1 2
do_test btree-7.4 {



  btree_insert $::c1 018 {*** 018 ***+++}

  btree_key $::c1
} {018}
do_test btree-7.5 {
  lrange [btree_cursor_dump $::c1] 4 5
} {480 1}
#btree_page_dump $::b1 2

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#



do_test btree-7.6 {
  btree_move_to $::c1 007
  btree_delete $::c1
  btree_move_to $::c1 011
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lindex [btree_cursor_dump $::c1] 5
} {3}
#btree_page_dump $::b1 2
do_test btree-7.8 {
  btree_insert $::c1 007 {*** 007 ***}
  lindex [btree_cursor_dump $::c1] 5
} {2}
#btree_page_dump $::b1 2

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 013
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {536 2}
do_test btree-7.10 {
  btree_move_to $::c1 009
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {564 2}
do_test btree-7.11 {
  btree_move_to $::c1 018
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {596 2}
do_test btree-7.13 {
  btree_move_to $::c1 033
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {624 3}
do_test btree-7.14 {
  btree_move_to $::c1 035
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {652 2}
#btree_page_dump $::b1 2
do_test btree-7.15 {
  lindex [btree_pager_stats $::b1] 1
} {2}

# Check to see that data on overflow pages work correctly.
#
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<256} {append data $data}
  set ::data $data
  btree_insert $::c1 020 $data
} {}
#btree_page_dump $::b1 2
do_test btree-8.1.1 {
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_pager_ref_dump $::b1
do_test btree-8.2 {

  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.3 {
  btree_data $::c1
} $::data
do_test btree-8.4 {
  btree_delete $::c1
................................................................................
do_test btree-8.4.1 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]
do_test btree-8.5 {
  set data "*** This is an even longer key"
  while {[string length $data]<2000} {append data $data}
  set ::data $data
  btree_insert $::c1 020 $data
} {}
do_test btree-8.6 {

  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.7 {
  btree_data $::c1
} $::data
do_test btree-8.8 {
  btree_commit $::b1
  btree_data $::c1
} $::data
do_test btree-8.9 {
  btree_close_cursor $::c1
  btree_close $::b1
  set ::b1 [btree_open test1.bt 2000 0]
  set ::c1 [btree_cursor $::b1 2 1]
  btree_move_to $::c1 020
  btree_data $::c1
} $::data
do_test btree-8.10 {
  btree_begin_transaction $::b1
  btree_delete $::c1
} {}
do_test btree-8.11 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]

# Now check out keys on overflow pages.
#
do_test btree-8.12 {
  set ::keyprefix "This is a long prefix to a key "
  while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix}
  btree_close_cursor $::c1

#    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.17 2004/05/07 23:50:58 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
do_test btree-3.18 {
  btree_next $::c1
  btree_key $::c1
} {600}
do_test btree-3.19 {
  btree_data $::c1
} {6.00}
do_test btree-3.20.1 {
  btree_next $::c1
  btree_key $::c1
} {0}
do_test btree-3.20.2 {
  btree_eof $::c1
} {1}
do_test btree-3.21 {
  set rc [catch {btree_data $::c1} res]
  lappend rc $res
} {1 SQLITE_INTERNAL}

# Commit the changes, reopen and reread the data
#
do_test btree-3.22 {
  set rc [catch {btree_close_cursor $::c1} msg]
  lappend rc $msg
} {0 {}}
................................................................................
  btree_data $::c1
} {6.00}
do_test btree-3.39 {
  btree_next $::c1
  btree_key $::c1
} {0}
do_test btree-3.40 {
  set rc [catch {btree_data $::c1} res]
  lappend rc $res
} {1 SQLITE_INTERNAL}
do_test btree-3.41 {
  lindex [btree_pager_stats $::b1] 1
} {1}


# Now try a delete
#
................................................................................
  btree_key $::c1
} {400}
do_test btree-4.4 {
  btree_move_to $::c1 0
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {[btree_eof $::c1]} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}

................................................................................
#
do_test btree-4.5 {
  btree_commit $::b1
  btree_move_to $::c1 0
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {[btree_eof $::c1]} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}

................................................................................
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-4.9 {
  set r {}
  btree_first $::c1
  while 1 {
    set key [btree_key $::c1]
    if {[btree_eof $::c1]} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}

................................................................................
     140 150
  btree_commit $::b1
  btree_get_meta $::b1
} {0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150}

proc select_all {cursor} {
  set r {}
  btree_first $cursor
  while {![btree_eof $cursor]} {
    set key [btree_key $cursor]













    lappend r $key
    lappend r [btree_data $cursor]
    btree_next $cursor
  }
  return $r
}
proc select_keys {cursor} {
  set r {}
  btree_first $cursor
  while {![btree_eof $cursor]} {
    set key [btree_key $cursor]

    lappend r $key
    btree_next $cursor
  }
  return $r
}

# Try to create a new table in the database file
................................................................................
} {1}
do_test btree-6.2.2 {
  set ::c2 [btree_cursor $::b1 $::t2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-6.2.3 {
  btree_insert $::c2 ten 10
  btree_move_to $::c2 ten
  btree_key $::c2
} {ten}
do_test btree-6.3 {
  btree_commit $::b1
  set ::c1 [btree_cursor $::b1 1 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-6.3.1 {
  select_all $::c1
} {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
#btree_page_dump $::b1 3
do_test btree-6.4 {
  select_all $::c2
} {ten 10}

# Drop the new table, then create it again anew.
................................................................................
} {2}

do_test btree-6.9.1 {
  btree_move_to $::c2 {}
  btree_key $::c2
} {}

# If we drop table 1 it just clears the table.  Table 1 always exists.
#
do_test btree-6.10 {
  btree_close_cursor $::c1
  btree_drop_table $::b1 1
  set ::c1 [btree_cursor $::b1 1 1]
  btree_first $::c1
  btree_eof $::c1
} {1}
do_test btree-6.11 {
  btree_commit $::b1
  select_all $::c1
} {}
do_test btree-6.12 {
  select_all $::c2
} {}
do_test btree-6.13 {
  btree_close_cursor $::c2
  lindex [btree_pager_stats $::b1] 1
} {1}

# Check to see that pages defragment properly.  To do this test we will
# 
#   1.  Fill the first page of table 1 with data.
#   2.  Delete every other entry of table 1.
#   3.  Insert a single entry that requires more contiguous
#       space than is available.
#
do_test btree-7.1 {
  btree_begin_transaction $::b1
} {}
catch {unset key}
catch {unset data}
do_test btree-7.2 {
  # Each record will be 10 bytes in size.
  #   + 100 bytes of database header
  #   + 6 bytes of table header
  #   + 91*10=910 bytes of cells
  # Totals 1016 bytes.  8 bytes left over
  # Keys are 1000 through 1090.
  for {set i 1000} {$i<1091} {incr i} {
    set key $i
    set data [format %5d $i]
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {8 1}
do_test btree-7.3 {
  for {set i 1001} {$i<1091} {incr i 2} {
    btree_move_to $::c1 $i

    btree_delete $::c1


  }
  # Freed 45 blocks.  Total freespace is 458
  # Keys remaining are even numbers between 1000 and 1090, inclusive
  lrange [btree_cursor_dump $::c1] 4 5
} {458 46}
#btree_page_dump $::b1 2
do_test btree-7.4 {
  # The largest free block is 10 bytes long.  So if we insert
  # a record bigger than 10 bytes it should force a defrag
  # The record is 20 bytes long.
  btree_insert $::c1 2000 {123456789_12345}
  btree_move_to $::c1 2000
  btree_key $::c1
} {2000}
do_test btree-7.5 {
  lrange [btree_cursor_dump $::c1] 4 5
} {438 1}
#btree_page_dump $::b1 2

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
# Keys are even numbers between 1000 and 1090 and one record of 2000.
# There are 47 keys total.
#
do_test btree-7.6 {
  btree_move_to $::c1 1006
  btree_delete $::c1
  btree_move_to $::c1 1010
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lrange [btree_cursor_dump $::c1] 4 5
} {458 3}   ;# Create two new holes of 10 bytes each
#btree_page_dump $::b1 2
do_test btree-7.8 {
  btree_insert $::c1 1006 { 1006}
  lrange [btree_cursor_dump $::c1] 4 5
} {448 2}   ;# Filled in the first hole
#btree_page_dump $::b1 2

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 1012
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {458 2}  ;# Coalesce with the whole before
do_test btree-7.10 {
  btree_move_to $::c1 1008
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {468 2}  ;# Coalesce with whole after
do_test btree-7.11 {
  btree_move_to $::c1 1030
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {478 3}   ;# Make a new hole
do_test btree-7.13 {
  btree_move_to $::c1 1034
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {488 4}   ;# Make another hole
do_test btree-7.14 {
  btree_move_to $::c1 1032
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {498 3}   ;# The freed space should coalesce on both ends
#btree_page_dump $::b1 2
do_test btree-7.15 {
  lindex [btree_pager_stats $::b1] 1
} {1}

# Check to see that data on overflow pages work correctly.
#
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<1234} {append data $data}
  set ::data $data
  btree_insert $::c1 2020 $data
} {}
#btree_page_dump $::b1 2
do_test btree-8.1.1 {
  lindex [btree_pager_stats $::b1] 1
} {1}
#btree_pager_ref_dump $::b1
do_test btree-8.2 {
  btree_move_to $::c1 2020
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.3 {
  btree_data $::c1
} $::data
do_test btree-8.4 {
  btree_delete $::c1
................................................................................
do_test btree-8.4.1 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]
do_test btree-8.5 {
  set data "*** This is an even longer key"
  while {[string length $data]<2000} {append data $data}
  set ::data $data
  btree_insert $::c1 2030 $data
} {}
do_test btree-8.6 {
  btree_move_to 2030
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.7 {
  btree_data $::c1
} $::data
do_test btree-8.8 {
  btree_commit $::b1
  btree_data $::c1
} $::data
do_test btree-8.9 {
  btree_close_cursor $::c1
  btree_close $::b1
  set ::b1 [btree_open test1.bt 2000 0]
  set ::c1 [btree_cursor $::b1 1 1]
  btree_move_to $::c1 2030
  btree_data $::c1
} $::data
do_test btree-8.10 {
  btree_begin_transaction $::b1
  btree_delete $::c1
} {}
do_test btree-8.11 {
  lindex [btree_get_meta $::b1] 0
} {}

# Now check out keys on overflow pages.
#
do_test btree-8.12 {
  set ::keyprefix "This is a long prefix to a key "
  while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix}
  btree_close_cursor $::c1