** 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.79 2003/01/04 19:44:08 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.
................................................................................
    c = nLocal - nKey;
  }
  *pResult = c;
  return SQLITE_OK;
}

/*
** Move the cursor down to a new child page.

*/
static int moveToChild(BtCursor *pCur, int newPgno){
  int rc;
  MemPage *pNewPage;
  Btree *pBt = pCur->pBt;


  rc = sqlitepager_get(pBt->pPager, newPgno, (void**)&pNewPage);
  if( rc ) return rc;
  rc = initPage(pBt, pNewPage, newPgno, pCur->pPage);
  if( rc ) return rc;
  assert( pCur->idx>=pCur->pPage->nCell
          || pCur->pPage->apCell[pCur->idx]->h.leftChild==SWAB32(pBt,newPgno) );
  assert( pCur->idx<pCur->pPage->nCell
................................................................................
** Move the cursor up to the parent page.
**
** pCur->idx is set to the cell index that contains the pointer
** to the page we are coming from.  If we are coming from the
** right-most child page then pCur->idx is set to one more than
** the largest cell index.
*/
static int moveToParent(BtCursor *pCur){
  Pgno oldPgno;
  MemPage *pParent;

  int idxParent;
  pParent = pCur->pPage->pParent;
  if( pParent==0 ) return SQLITE_INTERNAL;



  idxParent = pCur->pPage->idxParent;
  oldPgno = sqlitepager_pagenumber(pCur->pPage);
  sqlitepager_ref(pParent);
  sqlitepager_unref(pCur->pPage);
  pCur->pPage = pParent;
  assert( pParent->idxShift==0 );
  if( pParent->idxShift==0 ){
    pCur->idx = idxParent;
#ifndef NDEBUG  
    /* Verify that pCur->idx is the correct index to point back to the child
    ** page we just came from 
    */
    oldPgno = SWAB32(pCur->pBt, oldPgno);
    if( pCur->idx<pParent->nCell ){
      assert( pParent->apCell[idxParent]->h.leftChild==oldPgno );
    }else{
      assert( pParent->u.hdr.rightChild==oldPgno );
    }
#endif
  }else{
................................................................................
    /* The MemPage.idxShift flag indicates that cell indices might have 
    ** changed since idxParent was set and hence idxParent might be out
    ** of date.  So recompute the parent cell index by scanning all cells
    ** and locating the one that points to the child we just came from.
    */
    int i;
    pCur->idx = pParent->nCell;
    oldPgno = SWAB32(pCur->pBt, oldPgno);
    for(i=0; i<pParent->nCell; i++){
      if( pParent->apCell[i]->h.leftChild==oldPgno ){
        pCur->idx = i;
        break;
      }
    }
  }
  return SQLITE_OK;
}

/*
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pNew;
................................................................................
** entry to which it is currently pointing.
*/
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc;

  while( (pgno = pCur->pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
    rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno));
    if( rc ) return rc;
  }
  return SQLITE_OK;
}

/*
** Move the cursor down to the right-most leaf entry beneath the
................................................................................
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc;

  while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){
    pCur->idx = pCur->pPage->nCell;
    rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno));
    if( rc ) return rc;
  }
  pCur->idx = pCur->pPage->nCell - 1;
  return SQLITE_OK;
}

/* Move the cursor to the first entry in the table.  Return SQLITE_OK
................................................................................
    }
    if( chldPg==0 ){
      pCur->iMatch = c;
      if( pRes ) *pRes = c;
      return SQLITE_OK;
    }
    pCur->idx = lwr;
    rc = moveToChild(pCur, SWAB32(pCur->pBt, 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 sqliteBtreeNext(BtCursor *pCur, int *pRes){
  int rc;
  assert( pRes!=0 );
  /* assert( pCur->pPage!=0 ); */
  if( pCur->pPage==0 ){
    *pRes = 1;
    return SQLITE_ABORT;
  }
  assert( pCur->pPage->isInit );
  assert( pCur->eSkip!=SKIP_INVALID );
  if( pCur->pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  assert( pCur->idx<pCur->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>=pCur->pPage->nCell ){
    if( pCur->pPage->u.hdr.rightChild ){
      rc = moveToChild(pCur, SWAB32(pCur->pBt, pCur->pPage->u.hdr.rightChild));
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      *pRes = 0;
      return rc;
    }
    do{
      if( pCur->pPage->pParent==0 ){
        *pRes = 1;
        return SQLITE_OK;
      }
      rc = moveToParent(pCur);
    }while( rc==SQLITE_OK && pCur->idx>=pCur->pPage->nCell );

    *pRes = 0;
    return rc;
  }
  rc = moveToLeftmost(pCur);
  *pRes = 0;




  return rc;
}

/*
** Step the cursor to the back to the previous entry in the database.  If
** successful and pRes!=NULL then set *pRes=0.  If the cursor
** was already pointing to the first entry in the database before
** this routine was called, then set *pRes=1 if pRes!=NULL.
*/
int sqliteBtreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;


  if( pCur->pPage==0 ){
    if( pRes ) *pRes = 1;
    return SQLITE_ABORT;
  }
  assert( pCur->pPage->isInit );
  assert( pCur->eSkip!=SKIP_INVALID );
  if( pCur->pPage->nCell==0 ){
    if( pRes ) *pRes = 1;
    return SQLITE_OK;
  }
  if( pCur->eSkip==SKIP_PREV ){
    pCur->eSkip = SKIP_NONE;
    if( pRes ) *pRes = 0;
    return SQLITE_OK;
  }
  pCur->eSkip = SKIP_NONE;
  assert( pCur->idx>=0 );
  if( (pgno = pCur->pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
    rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno));
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
    while( pCur->idx==0 ){
      if( pCur->pPage->pParent==0 ){
        if( pRes ) *pRes = 1;
        return SQLITE_OK;
      }
      rc = moveToParent(pCur);
      if( rc ) return rc;
    }
    pCur->idx--;
    rc = SQLITE_OK;
  }
  if( pRes ) *pRes = 0;
  return rc;
}

/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty.  (In other words, sqlitepager_write()

** 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.80 2003/01/05 21:41:41 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.
................................................................................
    c = nLocal - nKey;
  }
  *pResult = c;
  return SQLITE_OK;
}

/*
** 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, int newPgno){
  int rc;
  MemPage *pNewPage;
  Btree *pBt = pCur->pBt;

  newPgno = SWAB32(pBt, newPgno);
  rc = sqlitepager_get(pBt->pPager, newPgno, (void**)&pNewPage);
  if( rc ) return rc;
  rc = initPage(pBt, pNewPage, newPgno, pCur->pPage);
  if( rc ) return rc;
  assert( pCur->idx>=pCur->pPage->nCell
          || pCur->pPage->apCell[pCur->idx]->h.leftChild==SWAB32(pBt,newPgno) );
  assert( pCur->idx<pCur->pPage->nCell
................................................................................
** Move the cursor up to the parent page.
**
** pCur->idx is set to the cell index that contains the pointer
** to the page we are coming from.  If we are coming from the
** right-most child page then pCur->idx is set to one more than
** the largest cell index.
*/
static void moveToParent(BtCursor *pCur){
  Pgno oldPgno;
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;
  pPage = pCur->pPage;

  assert( pPage!=0 );
  pParent = pPage->pParent;
  assert( pParent!=0 );
  idxParent = pPage->idxParent;

  sqlitepager_ref(pParent);
  sqlitepager_unref(pPage);
  pCur->pPage = pParent;
  assert( pParent->idxShift==0 );
  if( pParent->idxShift==0 ){
    pCur->idx = idxParent;
#ifndef NDEBUG  
    /* Verify that pCur->idx is the correct index to point back to the child
    ** page we just came from 
    */
    oldPgno = SWAB32(pCur->pBt, sqlitepager_pagenumber(pPage));
    if( pCur->idx<pParent->nCell ){
      assert( pParent->apCell[idxParent]->h.leftChild==oldPgno );
    }else{
      assert( pParent->u.hdr.rightChild==oldPgno );
    }
#endif
  }else{
................................................................................
    /* The MemPage.idxShift flag indicates that cell indices might have 
    ** changed since idxParent was set and hence idxParent might be out
    ** of date.  So recompute the parent cell index by scanning all cells
    ** and locating the one that points to the child we just came from.
    */
    int i;
    pCur->idx = pParent->nCell;
    oldPgno = SWAB32(pCur->pBt, sqlitepager_pagenumber(pPage));
    for(i=0; i<pParent->nCell; i++){
      if( pParent->apCell[i]->h.leftChild==oldPgno ){
        pCur->idx = i;
        break;
      }
    }
  }

}

/*
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pNew;
................................................................................
** entry to which it is currently pointing.
*/
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc;

  while( (pgno = pCur->pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  return SQLITE_OK;
}

/*
** Move the cursor down to the right-most leaf entry beneath the
................................................................................
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc;

  while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){
    pCur->idx = pCur->pPage->nCell;
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
  }
  pCur->idx = pCur->pPage->nCell - 1;
  return SQLITE_OK;
}

/* Move the cursor to the first entry in the table.  Return SQLITE_OK
................................................................................
    }
    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 sqliteBtreeNext(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->u.hdr.rightChild ){
      rc = moveToChild(pCur, pPage->u.hdr.rightChild);
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      *pRes = 0;
      return rc;
    }
    do{
      if( pPage->pParent==0 ){
        *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }while( pCur->idx>=pPage->nCell );
    *pRes = 0;
    return SQLITE_OK;
  }

  *pRes = 0;
  if( pPage->u.hdr.rightChild==0 ){
    return SQLITE_OK;
  }
  rc = moveToLeftmost(pCur);
  return rc;
}

/*
** Step the cursor to the back to the previous entry in the database.  If
** successful then set *pRes=0.  If the cursor
** was already pointing to the first entry in the database before
** this routine was called, then set *pRes=1.
*/
int sqliteBtreePrevious(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( (pgno = pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
    rc = moveToChild(pCur, pgno);
    if( rc ) return rc;
    rc = moveToRightmost(pCur);
  }else{
    while( pCur->idx==0 ){
      if( pPage->pParent==0 ){
        if( pRes ) *pRes = 1;
        return SQLITE_OK;
      }
      moveToParent(pCur);
      pPage = pCur->pPage;
    }
    pCur->idx--;
    rc = SQLITE_OK;
  }
  *pRes = 0;
  return rc;
}

/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty.  (In other words, sqlitepager_write()

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.189 2003/01/02 14:43:57 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The makefile scans this source file and creates the following
** array of string constants which are the names of all VDBE opcodes.
................................................................................

/*
** Convert the given stack entity into a string if it isn't one
** already.  Return non-zero if we run out of memory.
**
** NULLs are converted into an empty string.
*/
#define Stringify(P,I) \
   ((P->aStack[I].flags & STK_Str)==0 ? hardStringify(P,I) : 0)
static int hardStringify(Vdbe *p, int i){
  Stack *pStack = &p->aStack[i];
  char **pzStack = &p->zStack[i];
  int fg = pStack->flags;
  if( fg & STK_Real ){
    sprintf(pStack->z,"%.15g",pStack->r);
  }else if( fg & STK_Int ){
................................................................................
  int undoTransOnError = 0;   /* If error, either ROLLBACK or COMMIT */
  int inTempTrans = 0;        /* True if temp database is transactioned */
  char zBuf[100];             /* Space to sprintf() an integer */
  int returnStack[100];     /* Return address stack for OP_Gosub & OP_Return */
  int returnDepth = 0;      /* Next unused element in returnStack[] */
#ifdef VDBE_PROFILE
  unsigned long long start;

#endif


  /* No instruction ever pushes more than a single element onto the
  ** stack.  And the stack never grows on successive executions of the
  ** same loop.  So the total number of instructions is an upper bound
  ** on the maximum stack depth required.
................................................................................
    p->trace = stdout;
  }
#endif
  if( sqlite_malloc_failed ) goto no_mem;
  for(pc=0; !sqlite_malloc_failed && rc==SQLITE_OK && pc<p->nOp
             VERIFY(&& pc>=0); pc++){
#ifdef VDBE_PROFILE

    start = hwtime();
#endif
    pOp = &p->aOp[pc];

    /* Interrupt processing if requested.
    */
    if( db->flags & SQLITE_Interrupt ){
................................................................................
** by 6 spaces.  But the left-most 6 spaces have been removed to improve the
** readability.  From this point on down, the normal indentation rules are
** restored.
*****************************************************************************/
    }

#ifdef VDBE_PROFILE

    pOp->cycles += hwtime() - start;

    pOp->cnt++;





#endif

    /* The following code adds nothing to the actual functionality
    ** of the program.  It is only here for testing and debugging.
    ** On the other hand, it does burn CPU cycles every time through
    ** the evaluator loop.  So we can leave it out when NDEBUG is defined.
    */

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.190 2003/01/05 21:41:42 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The makefile scans this source file and creates the following
** array of string constants which are the names of all VDBE opcodes.
................................................................................

/*
** Convert the given stack entity into a string if it isn't one
** already.  Return non-zero if we run out of memory.
**
** NULLs are converted into an empty string.
*/

#define Stringify(P,I) ((aStack[I].flags & STK_Str)==0 ? hardStringify(P,I) : 0)
static int hardStringify(Vdbe *p, int i){
  Stack *pStack = &p->aStack[i];
  char **pzStack = &p->zStack[i];
  int fg = pStack->flags;
  if( fg & STK_Real ){
    sprintf(pStack->z,"%.15g",pStack->r);
  }else if( fg & STK_Int ){
................................................................................
  int undoTransOnError = 0;   /* If error, either ROLLBACK or COMMIT */
  int inTempTrans = 0;        /* True if temp database is transactioned */
  char zBuf[100];             /* Space to sprintf() an integer */
  int returnStack[100];     /* Return address stack for OP_Gosub & OP_Return */
  int returnDepth = 0;      /* Next unused element in returnStack[] */
#ifdef VDBE_PROFILE
  unsigned long long start;
  int origPc;
#endif


  /* No instruction ever pushes more than a single element onto the
  ** stack.  And the stack never grows on successive executions of the
  ** same loop.  So the total number of instructions is an upper bound
  ** on the maximum stack depth required.
................................................................................
    p->trace = stdout;
  }
#endif
  if( sqlite_malloc_failed ) goto no_mem;
  for(pc=0; !sqlite_malloc_failed && rc==SQLITE_OK && pc<p->nOp
             VERIFY(&& pc>=0); pc++){
#ifdef VDBE_PROFILE
    origPc = pc;
    start = hwtime();
#endif
    pOp = &p->aOp[pc];

    /* Interrupt processing if requested.
    */
    if( db->flags & SQLITE_Interrupt ){
................................................................................
** by 6 spaces.  But the left-most 6 spaces have been removed to improve the
** readability.  From this point on down, the normal indentation rules are
** restored.
*****************************************************************************/
    }

#ifdef VDBE_PROFILE
    {
      long long elapse = hwtime() - start;
      pOp->cycles += elapse;
      pOp->cnt++;
#if 0
        fprintf(stdout, "%10lld ", elapse);
        vdbePrintOp(stdout, origPc, &p->aOp[origPc]);
#endif
    }
#endif

    /* The following code adds nothing to the actual functionality
    ** of the program.  It is only here for testing and debugging.
    ** On the other hand, it does burn CPU cycles every time through
    ** the evaluator loop.  So we can leave it out when NDEBUG is defined.
    */