SQLite

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.22 2001/09/13 13:46:56 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.

**
** All of the keys on the page that Ptr(0) points to have values less
** than Key(0).  All of the keys on page Ptr(1) and its subpages have
** values greater than Key(0) and less than Key(1).  All of the keys
** on Ptr(N+1) and its subpages have values greater than Key(N).  And
** so forth.
**
** Finding a particular key requires reading O(log(M)) pages from the 
** disk where M is the number of entries in the tree.
**
** In this implementation, a single file can hold one or more separate 
** BTrees.  Each BTree is identified by the index of its root page.  The
** key and data for any entry are combined to form the "payload".  Up to
** MX_LOCAL_PAYLOAD bytes of payload can be carried directly on the
** database page.  If the payload is larger than MX_LOCAL_PAYLOAD bytes
** then surplus bytes are stored on overflow pages.  The payload for an

** SQLite database in order to identify the file as a real database.
*/
static const char zMagicHeader[] = 
   "** This file contains an SQLite 2.0 database **";
#define MAGIC_SIZE (sizeof(zMagicHeader))

/*
** This is a magic integer also used to test the integrity of the database
** file.  This integer is used in addition to the string above so that
** if the file is written on a little-endian architecture and read
** on a big-endian architectures (or vice versa) we can detect the
** problem.
**
** The number used was obtained at random and has no special
** significance.

  if( pBt->inTrans ) return SQLITE_ERROR;
  if( pBt->page1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }
  if( !sqlitepager_isreadonly(pBt) ){
    rc = sqlitepager_write(pBt->page1);
    if( rc!=SQLITE_OK ){
      return rc;
    }

    rc = newDatabase(pBt);
  }
  pBt->inTrans = 1;
  return rc;
}

/*
** If there are no outstanding cursors and we are not in the middle
** of a transaction but there is a read lock on the database, then
** this routine unrefs the first page of the database file which 
** has the effect of releasing the read lock.
**
** If there are any outstanding cursors, this routine is a no-op.
**
** If there is a transaction in progress, this routine is a no-op.
*/
static void unlockBtreeIfUnused(Btree *pBt){
  if( pBt->inTrans==0 && pBt->pCursor==0 && pBt->page1!=0 ){
    sqlitepager_unref(pBt->page1);
    pBt->page1 = 0;
    pBt->inTrans = 0;
  }
}

/*
** Commit the transaction currently in progress.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqliteBtreeCommit(Btree *pBt){
  int rc;
  if( pBt->inTrans==0 ) return SQLITE_ERROR;
  rc = sqlitepager_commit(pBt->pPager);
  pBt->inTrans = 0;
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Rollback the transaction in progress.  All cursors must be
** closed before this routine is called.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqliteBtreeRollback(Btree *pBt){
  int rc;
  if( pBt->pCursor!=0 ) return SQLITE_ERROR;
  if( pBt->inTrans==0 ) return SQLITE_OK;
  pBt->inTrans = 0;
  rc = sqlitepager_rollback(pBt->pPager);
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Create a new cursor for the BTree whose root is on the page
** iTable.  The act of acquiring a cursor gets a read lock on 
** the database file.

create_cursor_exception:
  *ppCur = 0;
  if( pCur ){
    if( pCur->pPage ) sqlitepager_unref(pCur->pPage);
    sqliteFree(pCur);
  }
  unlockBtreeIfUnused(pBt);
  return rc;
}

/*
** Close a cursor.  The read lock on the database file is released
** when the last cursor is closed.
*/
int sqliteBtreeCloseCursor(BtCursor *pCur){
  Btree *pBt = pCur->pBt;
  if( pCur->pPrev ){
    pCur->pPrev->pNext = pCur->pNext;
  }else{
    pBt->pCursor = pCur->pNext;
  }
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur->pPrev;
  }
  sqlitepager_unref(pCur->pPage);
  unlockBtreeIfUnused(pBt);
  sqliteFree(pCur);
  return SQLITE_OK;
}

/*
** Make a temporary cursor by filling in the fields of pTempCur.
** The temporary cursor is not on the cursor list for the Btree.

    }
    sqlitepager_unref(pOvfl);
  }
  return amt==0 ? SQLITE_OK : SQLITE_CORRUPT;
}

/*
** Read part of the key associated with cursor pCur.  A maximum
** of "amt" bytes will be transfered into zBuf[].  The transfer
** begins at "offset".  The number of bytes actually read is
** returned.  The amount returned will be smaller than the
** amount requested if there are not enough bytes in the key
** to satisfy the request.

*/
int sqliteBtreeKey(BtCursor *pCur, int offset, int amt, char *zBuf){
  Cell *pCell;
  MemPage *pPage;

  if( amt<0 ) return 0;
  if( offset<0 ) return 0; 
  if( amt==0 ) return 0;
  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    return 0;
  }
  pCell = pPage->apCell[pCur->idx];
  if( amt+offset > pCell->h.nKey ){
    amt = pCell->h.nKey - offset;
    if( amt<=0 ){
      return 0;
    }
  }
  getPayload(pCur, offset, amt, zBuf);
  return amt;
}

/*
** Set *pSize to the number of bytes of data in the entry the
** 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

    pCell = pPage->apCell[pCur->idx];
    *pSize = pCell->h.nData;
  }
  return SQLITE_OK;
}

/*
** Read part of the data associated with cursor pCur.  A maximum
** of "amt" bytes will be transfered into zBuf[].  The transfer
** begins at "offset".  The number of bytes actually read is
** returned.  The amount returned will be smaller than the
** amount requested if there are not enough bytes in the data
** to satisfy the request.

*/
int sqliteBtreeData(BtCursor *pCur, int offset, int amt, char *zBuf){
  Cell *pCell;
  MemPage *pPage;

  if( amt<0 ) return 0;
  if( offset<0 ) return 0;
  if( amt==0 ) return 0;
  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    return 0;
  }
  pCell = pPage->apCell[pCur->idx];
  if( amt+offset > pCell->h.nData ){
    amt = pCell->h.nData - offset;
    if( amt<=0 ){
      return 0;
    }
  }
  getPayload(pCur, offset + pCell->h.nKey, amt, zBuf);
  return amt;
}

/*
** Compare the key for the entry that pCur points to against the 
** given key (pKey,nKeyOrig).  Put the comparison result in *pResult.
** The result is negative if pCur<pKey, zero if they are equal and
** positive if pCur>pKey.

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

/* 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 and there is no first element.
*/
int sqliteBtreeFirst(BtCursor *pCur, int *pRes){
  int rc;
  rc = moveToRoot(pCur);
  if( rc ) return rc;
  if( pCur->pPage->nCell==0 ){
    *pRes = 1;
    return SQLITE_OK;
  }
  *pRes = 0;
  rc = moveToLeftmost(pCur);
  return rc;
}

/* Move the cursor so that it points to an entry near pKey.
** Return a success code.
**
** If an exact match is not found, then the cursor is always
** left pointing at a leaf page which would hold the entry if it
** were present.  The cursor might point to an entry that comes

    sqlitepager_unref(pThis);
  }
}

/*
** Reparent all children of the given page to be the given page.
** In other words, for every child of pPage, invoke reparentPage()
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
*/
static void reparentChildPages(Pager *pPager, MemPage *pPage){
  int i;
  for(i=0; i<pPage->nCell; i++){

    pIdx = &pPage->apCell[i]->h.iNext;
  }
  *pIdx = 0;
}

/*
** Make a copy of the contents of pFrom into pTo.  The pFrom->apCell[]
** pointers that point into pFrom->u.aDisk[] must be adjusted to point
** into pTo->u.aDisk[] instead.  But some pFrom->apCell[] entries might
** not point to pFrom->u.aDisk[].  Those are unchanged.
*/
static void copyPage(MemPage *pTo, MemPage *pFrom){
  uptr from, to;
  int i;
  memcpy(pTo->u.aDisk, pFrom->u.aDisk, SQLITE_PAGE_SIZE);

** if the page is overfull.  Part of the job of this routine is to
** make sure all Cells for pPage once again fit in pPage->u.aDisk[].
**
** In the course of balancing the siblings of pPage, the parent of pPage
** might become overfull or underfull.  If that happens, then this routine
** is called recursively on the parent.
**
** If this routine fails for any reason, it might leave the database
** in a corrupted state.  So if this routine fails, the database should
** be rolled back.
*/
static int balance(Btree *pBt, MemPage *pPage, BtCursor *pCur){
  MemPage *pParent;            /* The parent of pPage */
  MemPage *apOld[3];           /* pPage and up to two siblings */
  Pgno pgnoOld[3];             /* Page numbers for each page in apOld[] */
  MemPage *apNew[4];           /* pPage and up to 3 siblings after balancing */
  Pgno pgnoNew[4];             /* Page numbers for each page in apNew[] */

  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  pCell = pPage->apCell[pCur->idx];
  pgnoChild = pCell->h.leftChild;
  clearCell(pCur->pBt, pCell);
  if( pgnoChild ){
    /*
    ** The entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    Cell *pNext;

      sprintf(zBuf, "Page %d is never used", i);
      checkAppendMsg(&sCheck, zBuf, 0);
    }
  }

  /* Make sure this analysis did not leave any unref() pages
  */
  unlockBtreeIfUnused(pBt);
  if( nRef != *sqlitepager_stats(pBt->pPager) ){
    char zBuf[100];
    sprintf(zBuf, 
      "Outstanding page count goes from %d to %d during this analysis",
      nRef, *sqlitepager_stats(pBt->pPager)
    );
    checkAppendMsg(&sCheck, zBuf, 0);

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.11 2001/09/13 13:46:56 drh Exp $
*/

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree);
int sqliteBtreeClose(Btree*);

int sqliteBtreeClearTable(Btree*, int);

int sqliteBtreeCursor(Btree*, int iTable, BtCursor **ppCur);
int sqliteBtreeMoveto(BtCursor*, const void *pKey, int nKey, int *pRes);
int sqliteBtreeDelete(BtCursor*);
int sqliteBtreeInsert(BtCursor*, const void *pKey, int nKey,
                                 const void *pData, int nData);
int sqliteBtreeFirst(BtCursor*, int *pRes);
int sqliteBtreeNext(BtCursor*, int *pRes);
int sqliteBtreeKeySize(BtCursor*, int *pSize);
int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeDataSize(BtCursor*, int *pSize);
int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeCloseCursor(BtCursor*);

**     DROP TABLE
**     CREATE INDEX
**     DROP INDEX
**     creating expressions and ID lists
**     COPY
**     VACUUM
**
** $Id: build.c,v 1.29 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 
** that statement.  Prior action routines should have already

      if( p && p->pHash==pIndex ){
        p->pHash = pIndex->pHash;
      }
    }
  }
  sqliteFree(pIndex);
}

/*
** Unlink the given  index from its table, then remove
** the index from the index hash table, and free its memory
** structures.
*/
static void sqliteUnlinkAndDeleteIndex(sqlite *db, Index *pIndex){
  if( pIndex->pTable->pIndex==pIndex ){
    pIndex->pTable->pIndex = pIndex->pNext;
  }else{
    Index *p;
    for(p=pIndex->pTable->pIndex; p && p->pNext!=pIndex; p=p->pNext){}
    if( p && p->pNext==pIndex ){
      p->pNext = pIndex->pNext;
    }
  }
  sqliteDeleteIndex(db, pIndex);
}

/*
** Remove the memory data structures associated with the given
** Table.  No changes are made to disk by this routine.
**
** This routine just deletes the data structure.  It does not unlink
** the table data structure from the hash table.  But it does destroy

    pNext = pIndex->pNext;
    sqliteDeleteIndex(db, pIndex);
  }
  sqliteFree(pTable->zName);
  sqliteFree(pTable->aCol);
  sqliteFree(pTable);
}

/*
** Check all Tables and Indexes in the internal hash table and commit
** any additions or deletions to those hash tables.
**
** When executing CREATE TABLE and CREATE INDEX statements, the Table
** and Index structures are created and added to the hash tables, but
** the "isCommit" field is not set.  This routine sets those fields.
** When executing DROP TABLE and DROP INDEX, the "isDelete" fields of
** Table and Index structures is set but the structures are not unlinked
** from the hash tables nor deallocated.  This routine handles that
** deallocation. 
**
** See also: sqliteRollbackInternalChanges()
*/
void sqliteCommitInternalChanges(sqlite *db){
  int i;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  for(i=0; i<N_HASH; i++){
    Table *pTable, *pNext;
    for(pTable = apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( pTable->isDelete ){
        sqliteDeleteTable(db, pTable);
      }else if( pTable->isCommit==0 ){
        pTable->isCommit = 1;
      }
    }
  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = apIdxHash[i]; pIndex; pIndex=pNext){
      pNext = pIndex->pHash;
      if( pIndex->isDelete ){
        sqliteUnlinkAndDeleteIndex(db, pIndex);
      }else if( pIndex->isCommit==0 ){
        pIndex->isCommit = 1;
      }
    }
  }
  db->flags &= ~SQLITE_InternChanges;
}

/*
** This routine runs when one or more CREATE TABLE, CREATE INDEX,
** DROP TABLE, or DROP INDEX statements get rolled back.  The
** additions or deletions of Table and Index structures in the
** internal hash tables are undone.
**
** See also: sqliteCommitInternalChanges()
*/
void sqliteRollbackInternalChanges(sqlite *db){
  int i;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  for(i=0; i<N_HASH; i++){
    Table *pTable, *pNext;
    for(pTable = apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( !pTable->isCommit ){
        sqliteDeleteTable(db, pTable);
      }else if( pTable->isDelete ){
        pTable->isDelete = 0;
      }
    }
  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = apIdxHash[i]; pIndex; pIndex=pNext){
      pNext = pIndex->pHash;
      if( !pIndex->isCommit ){
        sqliteUnlinkAndDeleteIndex(db, pIndex);
      }else if( pIndex->isDelete ){
        pIndex->isDelete = 0;
      }
    }
  }
  db->flags &= ~SQLITE_InternChanges;
}

/*
** Construct the name of a user table or index from a token.
**
** Space to hold the name is obtained from sqliteMalloc() and must
** be freed by the calling function.
*/

  pTable->zName = zName;
  pTable->pHash = 0;
  pTable->nCol = 0;
  pTable->aCol = 0;
  pTable->pIndex = 0;
  if( pParse->pNewTable ) sqliteDeleteTable(pParse->db, pParse->pNewTable);
  pParse->pNewTable = pTable;
  if( !pParse->initFlag && (pParse->db->flags & SQLITE_InTrans)==0 ){
    Vdbe *v = sqliteGetVdbe(pParse);
    if( v ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
  }
}

/*
** Add a new column to the table currently being constructed.
**
** The parser calls this routine once for each column declaration
** in a CREATE TABLE statement.  sqliteStartTable() gets called

** the master table because we just connected to the database, so 
** the entry for this table already exists in the master table.
** We do not want to create it again.
*/
void sqliteEndTable(Parse *pParse, Token *pEnd){
  Table *p;
  int h;


  if( pEnd==0 || pParse->nErr || sqlite_malloc_failed ) return;
  p = pParse->pNewTable;
  if( p==0 ) return;


  /* Add the table to the in-memory representation of the database
  */
  if( pParse->explain==0 ){
    h = sqliteHashNoCase(p->zName, 0) % N_HASH;
    p->pHash = pParse->db->apTblHash[h];
    pParse->db->apTblHash[h] = p;
    pParse->pNewTable = 0;
    pParse->db->nTable++;
    db->flags |= SQLITE_InternChanges;
  }

  /* If not initializing, then create the table on disk.
  */
  if( !pParse->initFlag ){
    static VdbeOp addTable[] = {
      { OP_Open,        0, 2, 0},
      { OP_NewRecno,    0, 0, 0},
      { OP_String,      0, 0, "table"     },
      { OP_String,      0, 0, 0},            /* 3 */
      { OP_CreateTable, 0, 0, 0},
      { OP_String,      0, 0, 0},            /* 5 */





      { OP_String,      0, 0, 0},            /* 6 */



      { OP_MakeRecord,  4, 0, 0},
      { OP_Put,         0, 0, 0},
    };
    int n, base;
    Vdbe *v;

    v = sqliteGetVdbe(pParse);
    if( v==0 ) return;
    n = (int)pEnd->z - (int)pParse->sFirstToken.z + 1;
    base = sqliteVdbeAddOpList(v, ArraySize(addTable), addTable);
    sqliteVdbeChangeP3(v, base+3, p->zName, 0);
    sqliteVdbeTableRootAddr(v, &p->tnum);
    sqliteVdbeChangeP3(v, base+5, p->zName, 0);
    sqliteVdbeChangeP3(v, base+6, pParse->sFirstToken.z, n);
    sqliteVdbeAddOp(v, OP_Close, 0, 0, 0, 0);
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }

  }
}

/*
** Given a token, look up a table with that name.  If not found, leave
** an error for the parser to find and return NULL.
*/

  /* Generate code to remove the table from the master table
  ** on disk.
  */
  v = sqliteGetVdbe(pParse);
  if( v ){
    static VdbeOp dropTable[] = {

      { OP_Open,       0, 2,        0},
      { OP_String,     0, 0,        0}, /* 1 */
      { OP_Next,       0, ADDR(9),  0}, /* 2 */
      { OP_Dup,        0, 0,        0},
      { OP_Column,     0, 3,        0},
      { OP_Ne,         0, ADDR(2),  0},
      { OP_Recno,      0, 0,        0},




      { OP_Delete,     0, 0,        0},
      { OP_Goto,       0, ADDR(2),  0},
      { OP_Destroy,    0, 0,        0}, /* 9 */
      { OP_Close,      0, 0,        0},
    };
    Index *pIdx;
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    base = sqliteVdbeAddOpList(v, ArraySize(dropTable), dropTable);
    sqliteVdbeChangeP1(v, base+9, pTable->tnum);

    for(pIdx=pTable->pIndex; pIdx; pIdx=pIdx->pNext){
      sqliteVdbeAddOp(v, OP_Destroy, pIdx->tnum, 0, 0, 0);
    }
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }

  /* Mark the in-memory Table structure as being deleted.  The actually
  ** deletion occurs inside of sqliteCommitInternalChanges().
  **
  ** Exception: if the SQL statement began with the EXPLAIN keyword,
  ** then no changes should be made.
  */
  if( !pParse->explain ){







    pTable->isDelete = 1;


    db->flags |= SQLITE_InternChanges;

  }
}

/*
** Create a new index for an SQL table.  pIndex is the name of the index 
** and pTable is the name of the table that is to be indexed.  Both will 
** be NULL for a primary key.  In that case, use pParse->pNewTable as the 

  */
  if( pParse->explain==0 ){
    h = sqliteHashNoCase(pIndex->zName, 0) % N_HASH;
    pIndex->pHash = pParse->db->apIdxHash[h];
    pParse->db->apIdxHash[h] = pIndex;
    pIndex->pNext = pTab->pIndex;
    pTab->pIndex = pIndex;
    db->flags |= SQLITE_InternChanges;
  }

  /* If the initFlag is 0 then create the index on disk.  This
  ** involves writing the index into the master table and filling in the
  ** index with the current table contents.
  **
  ** The initFlag is 0 when the user first enters a CREATE INDEX 
  ** command.  The initFlag is 1 when a database is opened and 
  ** CREATE INDEX statements are read out of the master table.  In
  ** the latter case the index already exists on disk, which is why
  ** we don't want to recreate it.
  */
  if( pParse->initFlag==0 ){
    static VdbeOp addTable[] = {
      { OP_Open,        2, 2, 0},
      { OP_NewRecno,    2, 0, 0},
      { OP_String,      0, 0, "index"},
      { OP_String,      0, 0, 0},  /* 3 */
      { OP_CreateIndex, 0, 0, 0},
      { OP_String,      0, 0, 0},  /* 5 */
      { OP_String,      0, 0, 0},  /* 6 */
      { OP_MakeRecord,  5, 0, 0},
      { OP_Put,         2, 0, 0},
      { OP_Close,       2, 0, 0},
    };
    int n;
    Vdbe *v = pParse->pVdbe;
    int lbl1, lbl2;
    int i;

    v = sqliteGetVdbe(pParse);
    if( v==0 ) goto exit_create_index;
    if( pTable!=0 && (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_Open, 0, pTab->tnum, pTab->zName, 0);
    sqliteVdbeAddOp(v, OP_Open, 1, pIndex->tnum, pIndex->zName, 0);
    if( pStart && pEnd ){
      int base;
      n = (int)pEnd->z - (int)pStart->z + 1;
      base = sqliteVdbeAddOpList(v, ArraySize(addTable), addTable);
      sqliteVdbeChangeP3(v, base+3, pIndex->zName, 0);
      sqliteVdbeIndexRootAddr(v, &pIndex->tnum);
      sqliteVdbeChangeP3(v, base+5, pTab->zName, 0);
      sqliteVdbeChangeP3(v, base+6, pStart->z, n);
    }
    lbl1 = sqliteVdbeMakeLabel(v);
    lbl2 = sqliteVdbeMakeLabel(v);
    sqliteVdbeAddOp(v, OP_Next, 0, lbl2, 0, lbl1);
    sqliteVdbeAddOp(v, OP_GetRecno, 0, 0, 0, 0);
    for(i=0; i<pIndex->nColumn; i++){
      sqliteVdbeAddOp(v, OP_Column, 0, pIndex->aiColumn[i], 0, 0);
    }
    sqliteVdbeAddOp(v, OP_MakeIdxKey, pIndex->nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_PutIdx, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, lbl1, 0, 0);
    sqliteVdbeAddOp(v, OP_Noop, 0, 0, 0, lbl2);
    sqliteVdbeAddOp(v, OP_Close, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Close, 0, 0, 0, 0);
    if( pTable!=0 && (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }

  /* Reclaim memory on an EXPLAIN call.
  */
  if( pParse->explain ){
    sqliteFree(pIndex);
  }

    return;
  }

  /* Generate code to remove the index and from the master table */
  v = sqliteGetVdbe(pParse);
  if( v ){
    static VdbeOp dropIndex[] = {

      { OP_Open,       0, 2,       0},
      { OP_String,     0, 0,       0}, /* 1 */
      { OP_Next,       0, ADDR(8), 0}, /* 2 */
      { OP_Dup,        0, 0,       0},
      { OP_Column,     0, 1,       0},
      { OP_Ne,         0, ADDR(2), 0},
      { OP_Key,        0, 0,       0},
      { OP_Delete,     0, 0,       0},
      { OP_Destroy,    0, 0,       0}, /* 8 */
      { OP_Close,      0, 0,       0},
    };
    int base;

    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    base = sqliteVdbeAddOpList(v, ArraySize(dropIndex), dropIndex);
    sqliteVdbeChangeP1(v, base+8, pIndex->tnum);
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }

  /* Mark the internal Index structure for deletion by the
  ** sqliteCommitInternalChanges routine.
  */
  if( !pParse->explain ){



    pIndex->isDelete = 1;


    db->flags |= SQLITE_InternChanges;



  }
}

/*
** Add a new element to the end of an expression list.  If pList is
** initially NULL, then create a new expression list.
*/

    sqliteSetString(&pParse->zErrMsg, "table ", pTab->zName,
        " may not be modified", 0);
    pParse->nErr++;
    goto copy_cleanup;
  }
  v = sqliteGetVdbe(pParse);
  if( v ){
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    addr = sqliteVdbeAddOp(v, OP_FileOpen, 0, 0, 0, 0);
    sqliteVdbeChangeP3(v, addr, pFilename->z, pFilename->n);
    sqliteVdbeDequoteP3(v, addr);
    sqliteVdbeAddOp(v, OP_Open, 0, pTab->tnum, pTab->zName, 0);
    for(i=1, pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext, i++){
      sqliteVdbeAddOp(v, OP_Open, i, pIdx->tnum, pIdx->zName, 0);
    }
    end = sqliteVdbeMakeLabel(v);
    addr = sqliteVdbeAddOp(v, OP_FileRead, pTab->nCol, end, 0, 0);
    if( pDelimiter ){
      sqliteVdbeChangeP3(v, addr, pDelimiter->z, pDelimiter->n);
      sqliteVdbeDequoteP3(v, addr);
    }else{
      sqliteVdbeChangeP3(v, addr, "\t", 1);
    }
    sqliteVdbeAddOp(v, OP_NewRecno, 0, 0, 0, 0);
    if( pTab->pIndex ){
      sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
    }
    for(i=0; i<pTab->nCol; i++){
      sqliteVdbeAddOp(v, OP_FileColumn, i, 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_MakeRecord, pTab->nCol, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Put, 0, 0, 0, 0);
    for(i=1, pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext, i++){
      if( pIdx->pNext ){
        sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
      }
      for(j=0; j<pIdx->nColumn; j++){
        sqliteVdbeAddOp(v, OP_FileColumn, pIdx->aiColumn[j], 0, 0, 0);
      }
      sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_PutIdx, i, 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);
    sqliteVdbeAddOp(v, OP_Noop, 0, 0, 0, end);
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }
  
copy_cleanup:
  return;
}

/*

    && sqliteFindTable(pParse->db, zName)==0 ){
    sqliteSetString(&pParse->zErrMsg, "no such table or index: ", zName, 0);
    pParse->nErr++;
    goto vacuum_cleanup;
  }
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto vacuum_cleanup;
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
  }
  if( zName ){
    sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, zName, 0);
  }else{
    int h;
    Table *pTab;
    Index *pIdx;
    for(h=0; h<N_HASH; h++){
      for(pTab=pParse->db->apTblHash[h]; pTab; pTab=pTab->pHash){
        sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, pTab->zName, 0);
        for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
          sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, pIdx->zName, 0);
        }
      }
    }
  }
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
  }

vacuum_cleanup:
  sqliteFree(zName);
  return;
}

/*
** Begin a transaction
*/
void sqliteBeginTransaction(Parse *pParse){
  int rc;

  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( db->flags & SQLITE_InTrans ) return;
  v = sqliteGetVdbe(pParse);
  if( v ){
    sqliteVdbeAddOp(v, OP_Transaction, 1, 0, 0, 0);


  }

  db->flags |= SQLITE_InTrans;

}

/*
** Commit a transaction
*/
void sqliteCommitTransaction(Parse *pParse){
  int rc;

  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( (db->flags & SQLITE_InTrans)==0 ) return;
  v = sqliteGetVdbe(pParse);
  if( v ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);


  }

  db->flags &= ~SQLITE_InTrans;

}

/*
** Rollback a transaction
*/
void sqliteRollbackTransaction(Parse *pParse){
  int rc;

  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( (db->flags & SQLITE_InTrans)==0 ) return;
  v = sqliteGetVdbe(pParse);
  if( v ){
    sqliteVdbeAddOp(v, OP_Rollback, 0, 0, 0, 0);


  }

  db->flags &= ~SQLITE_InTrans;
}

/*
** Copyright (c) 2001 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains code to implement the database backend (DBBE)
** for sqlite.  The database backend is the interface between
** sqlite and the code that does the actually reading and writing
** of information to the disk.
**
** This file uses a custom B-Tree implementation as the database backend.
**
** $Id: dbbebtree.c,v 1.1 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"
#include "btree.h"

/*
** The following structure contains all information used by B-Tree
** database driver.  This is a subclass of the Dbbe structure.
*/
typedef struct Dbbex Dbbex;
struct Dbbex {
  Dbbe dbbe;         /* The base class */
  int write;         /* True for write permission */
  int inTrans;       /* Currently in a transaction */
  char *zFile;       /* File containing the database */
  Btree *pBt;        /* Pointer to the open database */
  BtCursor *pCur;    /* Cursor for the main database table */
  DbbeCursor *pDCur; /* List of all Dbbe cursors */
};

/*
** An cursor into a database table is an instance of the following
** structure.
*/
struct DbbeCursor {
  DbbeCursor *pNext; /* Next on list of all cursors */
  DbbeCursor *pPrev; /* Previous on list of all cursors */
  Dbbex *pBe;        /* The database of which this record is a part */
  BtCursor *pCur;    /* The cursor */
  char *zTempFile;   /* Name of file if referring to a temporary table */
  Btree *pTempBt;    /* Database handle, if this is a temporary table */
  char *zKey;        /* Most recent key.  Memory obtained from sqliteMalloc() */
  int nKey;          /* Size of the key */
  char *zKeyBuf;     /* Space used during NextIndex() processing */
  char *zData;       /* Most recent data.  Memory from sqliteMalloc() */
  int needRewind;    /* Next call to Next() returns first entry in table */
  int skipNext;      /* Do not advance cursor for next NextIndex() call */
};

/*
** Forward declaration
*/
static void sqliteBtbeCloseCursor(DbbeCursor *pCursr);

/*
** Completely shutdown the given database.  Close all files.  Free all memory.
*/
static void sqliteBtbeClose(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  assert( pBe->pDCur==0 );
  if( pBe->pCur ){
    sqliteBtreeCloseCursor(pBe->pCur);
  }
  sqliteBtreeClose(pBe->pBt);
  sqliteFree(pBe->zFile);
  sqliteFree(pBe);
}

/*
** Translate a database table name into the table number for the database.
** The pBe->pCur cursor points to table number 2 of the database and that
** table maps all other database names into database number.  Return the
** database number of the table, or return 0 if not found.
*/
static int mapTableNameToNumber(Dbbex *pBe, char *zName){
  int nName = strlen(zName);
  int rc;
  int res;
  if( pBe->pCur==0 ){
    rc = sqliteBtreeCursor(pBe, 2, &pBe->pCur);
    if( rc!=SQLITE_OK ) return 0;
  }
  rc = sqliteBtreeMoveto(pBe->pCur, zName, nName, &res);
  if( rc!=SQLITE_OK || res!=0 ) return 0;
  rc = sqliteBtreeData(pBe->pCur, 0, sizeof(res), &res);
  if( rc!=SQLITE_OK ) return 0;
  return res;
}

/*
** Locate a directory where we can potentially create a temporary
** file.
*/
static const char *findTempDir(void){
  static const char *azDirs[] = {
     "/var/tmp",
     "/usr/tmp",
     "/tmp",
     "/temp",
     ".",
     "./temp",
  };
  int i;
  struct stat buf;
  for(i=0; i<sizeof(azDirs)/sizeof(azDirs[0]); i++){
    if( stat(azDirs[i], &buf)==0 && S_ISDIR(buf.st_mode)
         && S_IWUSR(buf.st_mode) ){
       return azDirs[i];
    }
  }
  return 0;
}

/*
** Open a new table cursor.  Write a pointer to the corresponding
** DbbeCursor structure into *ppCursr.  Return an integer success
** code:
**
**    SQLITE_OK          It worked!
**
**    SQLITE_NOMEM       sqliteMalloc() failed
**
**    SQLITE_PERM        Attempt to access a file for which file
**                       access permission is denied
**
**    SQLITE_BUSY        Another thread or process is already using
**                       the corresponding file and has that file locked.
**
**    SQLITE_READONLY    The current thread already has this file open
**                       readonly but you are trying to open for writing.
**                       (This can happen if a SELECT callback tries to
**                       do an UPDATE or DELETE.)
**
** If the table does not previously exist and writeable is TRUE then
** a new table is created.  If zTable is 0 or "", then a temporary 
** database table is created and a cursor to that temporary file is
** opened.  The temporary file will be deleted when it is closed.
*/
static int sqliteBtbeOpenCursor(
  Dbbe *pDbbe,            /* The database the table belongs to */
  const char *zTable,     /* The SQL name of the file to be opened */
  int writeable,          /* True to open for writing */
  int intKeyOnly,         /* True if only integer keys are used */
  DbbeCursor **ppCursr    /* Write the resulting table pointer here */
){
  char *zFile;            /* Name of the table file */
  DbbeCursor *pCursr;     /* The new table cursor */
  int rc = SQLITE_OK;     /* Return value */
  int rw_mask;            /* Permissions mask for opening a table */
  int mode;               /* Mode for opening a table */
  Dbbex *pBe = (Dbbex*)pDbbe;

  *ppCursr = 0;
  if( pBe->pCur==0 ){
    rc = sqliteBtreeCursor(pBe->pBt, 2, &pBe->pCur);
    if( rc!=SQLITE_OK ) return rc;
  }
  pCursr = sqliteMalloc( sizeof(*pCursr) );
  if( pCursr==0 ) return SQLITE_NOMEM;
  if( zTable ){
    char *zTab;
    int tabId, i;

    if( writeable && pBe->inTrans==0 ){
      rc = sqliteBeginTrans(pBe->pBt);
      if( rc!=SQLITE_OK ){
        sqliteFree(pCursr);
        return rc;
      }
      pBe->inTrans = 1;
    }
    zTab = sqliteStrDup(zTable);
    for(i=0; zTab[i]; i++){
       if( isupper(zTab[i]) ) zTab[i] = tolower(zTab[i]);
    }
    tabId = mapTableNameToNumber(pBe, zTab);
    if( tabId==0 ){
      if( writeable==0 ){
        pCursr->pCur = 0;
      }else{
        rc = sqliteBtreeCreateTable(pBe->pBt, &tabId);
        if( rc!=SQLITE_OK ){
          sqliteFree(pCursr);
          sqliteFree(zTab);
          return rc;
        }
        sqliteBtreeInsert(pBe->pCur, zTab, strlen(zTab), tabId, sizeof(tabId));
      }
    }
    sqliteFree(zTab);
    rc = sqliteBtreeCursor(pBe->pBt, tabId, &pCursr->pCur);
    if( rc!=SQLITE_OK ){
      sqliteFree(pCursr);
      return rc;
    }
    pCursr->zTempFile = 0;
    pCursr->pTempBt = 0;
  }else{
    int nTry = 5;
    char zFileName[200];
    while( nTry>0 ){
      nTry--;
      sprintf(zFileName,"%s/_sqlite_temp_file_%d",
           findTempDir(), sqliteRandomInteger());
      rc = sqliteBtreeOpen(zFileName, 0, 100, &pCursr->pTempBt);
      if( rc!=SQLITE_OK ) continue;
      rc = sqliteBtreeCursor(pCursr->pTempBt, 2, &pCursr->pCur*****
    pFile = 0;
    zFile = 0;
  }
  pCursr->pNext = pBe->pDCur;
  if( pBe->pDCur ){
    pBe->pDCur->pPrev = pCursr;
  }
  pCursr->pPrev = 0;
  pCursr->pBe = pBe;
  pCursr->skipNext = 0;
  pCursr->needRewind = 1;
  return SQLITE_OK;
}

/*
** Drop a table from the database. 
*/
static void sqliteBtbeDropTable(Dbbe *pDbbe, const char *zTable){
  int iTable;
  Dbbex *pBe = (Dbbex*)pDbbe;

  iTable = mapTableNameToNumber(zTable);
  if( iTable>0 ){
    sqliteBtreeDelete(pBe->pCur);
    sqliteBtreeDropTable(pBe->pBt, iTable);
  }
}

/*
** Clear the remembered key and data from the cursor.
*/
static void clearCursorCache(DbbeCursor *pCursr){
  if( pCursr->zKey ){
    sqliteFree(pCursr->zKey);
    pCursr->zKey = 0;
    pCursr->nKey = 0;
    pCursr->zKeyBuf = 0;
  }
  if( pCursr->zData ){
    sqliteFree(pCursr->zData);
    pCursr->zData = 0;
  }
}

/*
** Close a cursor previously opened by sqliteBtbeOpenCursor().
*/
static void sqliteBtbeCloseCursor(DbbeCursor *pCursr){
  Dbbex *pBe;
  if( pCursr==0 ) return;
  if( pCursr->pCur ){
    sqliteBtreeCloseCursor(pCursr->pCur);
  }
  if( pCursr->pTemp ){
    sqliteBtreeClose(pCursr->pTemp);
  }
  if( pCursr->zTempFile ){
    unlink(pCursr->zTempFile);
    sqliteFree(pCursr->zTempFile);
  }
  clearCursorCache(pCursr);
  pBe = pCursr->pBe;
  if( pCursr->pPrev ){
    pCursr->pPrev->pNext = pCursr->pNext;
  }else{
    pBe->pDCur = pCur->pNext;
  }
  if( pCursr->pNext ){
    pCursr->pNext->pPrev = pCursr->pPrev;
  }
  if( pBe->pDCur==0 && pBe->inTrans==0 && pBe->pCur!=0 ){
    sqliteBtreeCloseCursor(pBe->pCur);
    pBe->pCur = 0;
  }
  memset(pCursr, 0, sizeof(*pCursr));
  sqliteFree(pCursr);
}

/*
** Reorganize a table to reduce search times and disk usage.
*/
static int sqliteBtbeReorganizeTable(Dbbe *pBe, const char *zTable){
  return SQLITE_OK;
}

/*
** Move the cursor so that it points to the entry with a key that
** matches the argument.  Return 1 on success and 0 if no keys match
** the argument.
*/
static int sqliteBtbeFetch(DbbeCursor *pCursr, int nKey, char *pKey){
  int rc, res;
  clearCursorCache(pCursr);
  if( pCursr->pCur==0 ) return 0;
  rc = sqliteBtreeMoveto(pCursr->pCur, pKey, nKey, &res);
  return rc==SQLITE_OK && res==0;
}

/*
** Copy bytes from the current key or data into a buffer supplied by
** the calling function.  Return the number of bytes copied.
*/
static
int sqliteBtbeCopyKey(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  if( pCursr->pCur==0 ) return 0;
  int rc = sqliteBtreeKey(pCursr->pCur, offset, amt, zBuf);
  if( rc!=SQLITE_OK ) amt = 0;
  return amt;
}
static
int sqliteBtbeCopyData(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  if( pCursr->pCur==0 ) return 0;
  int rc = sqliteBtreeData(pCursr->pCur, offset, amt, zBuf);
  if( rc!=SQLITE_OK ) amt = 0;
  return amt;
}

/*
** Return a pointer to bytes from the key or data.  The data returned
** is ephemeral.
*/
static char *sqliteBtbeReadKey(DbbeCursor *pCursr, int offset){
  if( pCursr->zKey==0 && pCursr->pCur!=0 ){
    sqliteBtreeKeySize(pCursr->pCur, &pCursr->nKey);
    pCursr->zKey = sqliteMalloc( pCursr->nKey + 1 );
    if( pCursr->zKey==0 ) return 0;
    sqliteBtreeKey(pCursr->pCur, 0, pCursr->nKey, pCursr->zKey);
    pCursr->zKey[pCursor->nKey] = 0;
  }
  return pCursr->zKey;
}
static char *sqliteBtbeReadData(DbbeCursor *pCursr, int offset){
  if( pCursr->zData==0 && pCursr->pCur!=0 ){
    int nData;
    sqliteBtreeDataSize(pCursr->pCur, &nData);
    pCursr->zData = sqliteMalloc( nData + 1 );
    if( pCursr->zData==0 ) return 0;
    sqliteBtreeData(pCursr->pCur, 0, nData, pCursr->zData);
    pCursr->zData[nData] = 0;
  }
  return pCursr->zData;
}

/*
** Return the total number of bytes in either data or key.
*/
static int sqliteBtbeKeyLength(DbbeCursor *pCursr){
  int n;
  if( pCursr->pCur==0 ) return 0;
  sqliteBtreeKeySize(pCursr->pCur, &n);
  return n;
}
static int sqliteBtbeDataLength(DbbeCursor *pCursr){
  int n;
  if( pCursr->pCur==0 ) return 0;
  sqliteBtreeDataSize(pCursr->pCur, &n);
  return n;
}

/*
** Make is so that the next call to sqliteNextKey() finds the first
** key of the table.
*/
static int sqliteBtbeRewind(DbbeCursor *pCursr){
  pCursr->needRewind = 1;
  return SQLITE_OK;
}

/*
** Move the cursor so that it points to the next key in the table.
** Return 1 on success.  Return 0 if there are no more keys in this
** table.
**
** If the pCursr->needRewind flag is set, then move the cursor so
** that it points to the first key of the table.
*/
static int sqliteBtbeNextKey(DbbeCursor *pCursr){
  int rc, res;
  static char zNullKey[1] = { '\000' };
  assert( pCursr!=0 );
  clearCursorCache(pCursr);
  if( pCursr->pCur==0 ) return 0;
  if( pCursr->needRewind ){
    rc = sqliteBtreeFirst(pCursr->pCur, &res);
    return rc==SQLITE_OK && res==0;
  }
  rc = sqliteBtreeNext(pCursr->pCur);
  return rc==SQLITE_OK && res==0;
}

/*
** Get a new integer key.
*/
static int sqliteBtbeNew(DbbeCursor *pCursr){
  int rc;
  int res = 0;

  assert( pCursr->pCur!=0 );
  while( res==0 ){
    iKey = sqliteRandomInteger() & 0x7fffffff;
    if( iKey==0 ) continue;
    rc = sqliteBtreeMoveto(pCursr->pCur, &iKey, sizeof(iKey), &res);
    assert( rc==SQLITE_OK );
  }
  clearCursorCache(pCursr);
  return iKey;
}   

/*
** Write an entry into the table.  Overwrite any prior entry with the
** same key.
*/
static int sqliteBtbePut(
  DbbeCursor *pCursr,  /* Write to the database associated with this cursor */
  int nKey,            /* Number of bytes in the key */
  char *pKey,          /* The data for the key */
  int nData,           /* Number of bytes of data */
  char *pData          /* The data */
){
  clearCursorCache(pCursr);
  assert( pCursr->pCur!=0 );
  return sqliteBtreeInsert(pCursr->pCur, pKey, nKey, pData, nData);
}

/*
** Remove an entry from a table, if the entry exists.
*/
static int sqliteBtbeDelete(DbbeCursor *pCursr, int nKey, char *pKey){
  int rc;
  int res;
  clearCursorCache(pCursr);
  assert( pCursr->pCur!=0 );
  rc = sqliteBtreeMoveto(pCursr->pCur, pKey, nKey, &res);
  if( rc==SQLITE_OK && res==0 ){
    rc = sqliteBtreeDelete(pCursr->pCur);
  }
  return rc;
}

/*
** Begin a transaction.
*/
static int sqliteBtbeBeginTrans(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  if( pBe->inTrans ) return SQLITE_OK;
  sqliteBtreeBeginTrans(pBe->pBt);
  pBe->inTrans = 1;
  return SQLITE_OK;  
}

/*
** Commit a transaction.
*/
static int sqliteBtbeCommit(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  if( !pBe->inTrans ) return SQLITE_OK;
  pBe->inTrans = 0;
  return sqliteBtreeCommit(pBe->pBt);
}

/*
** Rollback a transaction.
*/
static int sqliteBtbeRollback(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  if( !pBe->inTrans ) return SQLITE_OK;
  if( pBt->pDCur!=0 ) return SQLITE_INTERNAL;
  pBe->inTrans = 0;
  if( pBe->pCur ){
    sqliteBtreeCloseCursor(pBe->pCur);
    pBe->pCur = 0;
  }
  return sqliteBtreeRollback(pBe->pBt);
}

/*
** Begin scanning an index for the given key.  Return 1 on success and
** 0 on failure.  (Vdbe ignores the return value.)
*/
static int sqliteBtbeBeginIndex(DbbeCursor *pCursr, int nKey, char *pKey){
  int rc;
  int res;
  clearCursorCache(pCursr);
  if( pCursr->pCur==0 ) return 0;
  pCursr->nKey = nKey;
  pCursr->zKey = sqliteMalloc( 2*(nKey + 1) );
  if( pCursr->zKey==0 ) return 0;
  pCursr->zKeyBuf = &pCursr->zKey[nKey+1];
  memcpy(pCursr->zKey, zKey, nKey);
  pCursr->zKey[nKey] = 0;
  rc = sqliteBtreeMoveTo(pCursr->pCur, pKey, nKey, res);
  pCursr->skipNext = res<0;
  return rc==SQLITE_OK;
}

/*
** Return an integer key which is the next record number in the index search
** that was started by a prior call to BeginIndex.  Return 0 if all records
** have already been searched.
*/
static int sqliteBtbeNextIndex(DbbeCursor *pCursr){
  int rc, res;
  int iRecno;
  BtCursor *pCur = pCursr->pCur;
  if( pCur==0 ) return 0;
  if( pCursr->zKey==0 || pCursr->zKeyBuf==0 ) return 0;
  if( !pCursr->skipNext ){
    rc = sqliteBtreeNext(pCur, &res);
    pCursr->skipNext = 0;
    if( res ) return 0;
  }
  if( sqliteBtreeKeySize(pCur)!=pCursr->nKey+4 ){
    return 0;
  }
  rc = sqliteBtreeKey(pCur, 0, pCursr->nKey, pCursr->zKeyBuf);
  if( rc!=SQLITE_OK || memcmp(pCursr->zKey, pCursr->zKeyBuf, pCursr->nKey)!=0 ){
    return 0;
  }
  sqliteBtreeKey(pCur, pCursr->nKey, 4, &iRecno);
  return iRecno;
}

/*
** Write a new record number and key into an index table.  Return a status
** code.
*/
static int sqliteBtbePutIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  char *zBuf;
  int rc;
  char zStaticSpace[200];

  assert( pCursr->pCur!=0 );
  if( nKey+4>sizeof(zStaticSpace){
    zBuf = sqliteMalloc( nKey + 4 );
    if( zBuf==0 ) return SQLITE_NOMEM;
  }else{
    zBuf = zStaticSpace;
  }
  memcpy(zBuf, pKey, nKey);
  memcpy(&zBuf[nKey], N, 4);
  rc = sqliteBtreeInsert(pCursr->pCur, zBuf, nKey+4, "", 0);
  if( zBuf!=zStaticSpace ){
    sqliteFree(zBuf);
  }
}

/*
** Delete an index entry.  Return a status code.
*/
static 
int sqliteBtbeDeleteIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  char *zBuf;
  int rc;
  char zStaticSpace[200];

  assert( pCursr->pCur!=0 );
  if( nKey+4>sizeof(zStaticSpace){
    zBuf = sqliteMalloc( nKey + 4 );
    if( zBuf==0 ) return SQLITE_NOMEM;
  }else{
    zBuf = zStaticSpace;
  }
  memcpy(zBuf, pKey, nKey);
  memcpy(&zBuf[nKey], N, 4);
  rc = sqliteBtreeMoveto(pCursr->pCur, zBuf, nKey+4, &res);
  if( rc==SQLITE_OK && res==0 ){
    sqliteBtreeDelete(pCursr->pCur);
  }
  if( zBuf!=zStaticSpace ){
    sqliteFree(zBuf);
  }
  return SQLITE_OK;
}

/*
** This variable contains pointers to all of the access methods
** used to implement the GDBM backend.
*/
static struct DbbeMethods btbeMethods = {
  /*           Close */   sqliteBtbeClose,
  /*      OpenCursor */   sqliteBtbeOpenCursor,
  /*       DropTable */   sqliteBtbeDropTable,
  /* ReorganizeTable */   sqliteBtbeReorganizeTable,
  /*     CloseCursor */   sqliteBtbeCloseCursor,
  /*           Fetch */   sqliteBtbeFetch,
  /*            Test */   sqliteBtbeFetch,
  /*         CopyKey */   sqliteBtbeCopyKey,
  /*        CopyData */   sqliteBtbeCopyData,
  /*         ReadKey */   sqliteBtbeReadKey,
  /*        ReadData */   sqliteBtbeReadData,
  /*       KeyLength */   sqliteBtbeKeyLength,
  /*      DataLength */   sqliteBtbeDataLength,
  /*         NextKey */   sqliteBtbeNextKey,
  /*          Rewind */   sqliteBtbeRewind,
  /*             New */   sqliteBtbeNew,
  /*             Put */   sqliteBtbePut,
  /*          Delete */   sqliteBtbeDelete,
  /*      BeginTrans */   sqliteBtbeBeginTrans,
  /*          Commit */   sqliteBtbeCommit,
  /*        Rollback */   sqliteBtbeRollback,
  /*      BeginIndex */   sqliteBtbeBeginIndex,
  /*       NextIndex */   sqliteBtbeNextIndex,
  /*        PutIndex */   sqliteBtbePutIndex,
  /*     DeleteIndex */   sqliteBtbeDeleteIndex,
};


/*
** This routine opens a new database.  For the BTree driver
** implemented here, the database name is the name of a single
** file that contains all tables of the database.
**
** If successful, a pointer to the Dbbe structure is returned.
** If there are errors, an appropriate error message is left
** in *pzErrMsg and NULL is returned.
*/
Dbbe *sqliteBtbeOpen(
  const char *zName,     /* The name of the database */
  int writeFlag,         /* True if we will be writing to the database */
  int createFlag,        /* True to create database if it doesn't exist */
  char **pzErrMsg        /* Write error messages (if any) here */
){
  Dbbex *pNew;
  char *zTemp;
  Btree *pBt;
  int rc;

  rc = sqliteBtreeOpen(zName, 0, 100, &pBt);
  if( rc!=SQLITE_OK ){
    sqliteSetString(pzErrMsg, "unable to open database file \"", zName, "\"",0);
    return 0;
  }
  pNew = sqliteMalloc(sizeof(Dbbex) + strlen(zName) + 1);
  if( pNew==0 ){
    sqliteBtreeCloseCursor(pCur);
    sqliteBtreeClose(pBt);
    sqliteSetString(pzErrMsg, "out of memory", 0);
    return 0;
  }
  pNew->dbbe.x = &btbeMethods;
  pNew->write = writeFlag;
  pNew->inTrans = 0;
  pNew->zFile = (char*)&pNew[1];
  strcpy(pNew->zFile, zName);
  pNew->pBt = pBt;
  pNew->pCur = 0;
  return &pNew->dbbe;
}
#endif /* DISABLE_GDBM */

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.10 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"

/*
** Process a DELETE FROM statement.
*/
void sqliteDeleteFrom(

    }
  }

  /* Begin generating code.
  */
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto delete_from_cleanup;
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
  }


  /* Special case: A DELETE without a WHERE clause deletes everything.
  ** It is easier just to deleted the database files directly.
  */
  if( pWhere==0 ){
    sqliteVdbeAddOp(v, OP_Destroy, pTab->tnum, 0, 0, 0);
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      sqliteVdbeAddOp(v, OP_Destroy, pIdx->tnum, 0, 0, 0);
    }
  }

  /* The usual case: There is a WHERE clause so we have to scan through
  ** the table an pick which records to delete.
  */
  else{

    /* Delete every item whose key was written to the list during the
    ** database scan.  We have to delete items after the scan is complete
    ** because deleting an item can change the scan order.
    */
    base = pParse->nTab;
    sqliteVdbeAddOp(v, OP_ListRewind, 0, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Open, base, pTab->tnum, 0, 0);
    for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
      sqliteVdbeAddOp(v, OP_Open, base+i, pIdx->tnum, 0, 0);
    }
    end = sqliteVdbeMakeLabel(v);
    addr = sqliteVdbeAddOp(v, OP_ListRead, 0, end, 0, 0);
    if( pTab->pIndex ){
      sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_Fetch, base, 0, 0, 0);
      for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
        int j;
        sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
        for(j=0; j<pIdx->nColumn; j++){
          sqliteVdbeAddOp(v, OP_Field, base, pIdx->aiColumn[j], 0, 0);
        }
        sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
        sqliteVdbeAddOp(v, OP_DeleteIdx, base+i, 0, 0, 0);
      }
    }
    sqliteVdbeAddOp(v, OP_Delete, base, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);
    sqliteVdbeAddOp(v, OP_ListClose, 0, 0, 0, end);
  }
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
  }


delete_from_cleanup:
  sqliteIdListDelete(pTabList);
  sqliteExprDelete(pWhere);
  return;
}

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle INSERT statements.
**
** $Id: insert.c,v 1.14 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"

/*
** This routine is call to handle SQL of the following forms:
**
**    insert into TABLE (IDLIST) values(EXPRLIST)

    goto insert_cleanup;
  }

  /* Allocate a VDBE
  */
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto insert_cleanup;
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
  }

  /* Figure out how many columns of data are supplied.  If the data
  ** is comming from a SELECT statement, then this step has to generate
  ** all the code to implement the SELECT statement and leave the data
  ** in a temporary table.  If data is coming from an expression list,
  ** then we just have to count the number of expressions.
  */

        }
      }else if( srcTab>=0 ){
        sqliteVdbeAddOp(v, OP_Field, srcTab, idx, 0, 0); 
      }else{
        sqliteExprCode(pParse, pList->a[j].pExpr);
      }
    }
    sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_PutIdx, idx+base, 0, 0, 0);
  }

  /* The bottom of the loop, if the data source is a SELECT statement
  */
  if( srcTab>=0 ){
    sqliteVdbeAddOp(v, OP_Goto, 0, iCont, 0, 0);
    sqliteVdbeAddOp(v, OP_Noop, 0, 0, 0, iBreak);
  }
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
  }


insert_cleanup:
  if( pList ) sqliteExprListDelete(pList);
  if( pSelect ) sqliteSelectDelete(pSelect);
  sqliteIdListDelete(pColumn);
}

**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.30 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"
#if defined(HAVE_USLEEP) && HAVE_USLEEP
#include <unistd.h>
#endif

/*

  /*
  ** The master database table has a structure like this
  */
  static char master_schema[] = 
     "CREATE TABLE " MASTER_NAME " (\n"
     "  type text,\n"
     "  name text,\n"
     "  tnum integer,\n"
     "  tbl_name text,\n"
     "  sql text\n"
     ")"
  ;

  /* The following program is used to initialize the internal
  ** structure holding the tables and indexes of the database.
  ** The database contains a special table named "sqlite_master"
  ** defined as follows:
  **
  **    CREATE TABLE sqlite_master (
  **        type       text,    --  Either "table" or "index" or "meta"
  **        name       text,    --  Name of table or index
  **        tnum       integer, --  The integer page number of root page
  **        tbl_name   text,    --  Associated table 
  **        sql        text     --  The CREATE statement for this object
  **    );
  **
  ** The sqlite_master table contains a single entry for each table
  ** and each index.  The "type" column tells whether the entry is
  ** a table or index.  The "name" column is the name of the object.

  ** The following program invokes its callback on the SQL for each
  ** table then goes back and invokes the callback on the
  ** SQL for each index.  The callback will invoke the
  ** parser to build the internal representation of the
  ** database scheme.
  */
  static VdbeOp initProg[] = {
    { OP_Open,     0, 2,  0},
    { OP_Next,     0, 9,  0},           /* 1 */
    { OP_Column,   0, 0,  0},
    { OP_String,   0, 0,  "meta"},
    { OP_Ne,       0, 1,  0},
    { OP_Column,   0, 0,  0},
    { OP_Column,   0, 4,  0},
    { OP_Callback, 2, 0,  0},
    { OP_Goto,     0, 1,  0},
    { OP_Rewind,   0, 0,  0},           /* 9 */
    { OP_Next,     0, 17, 0},           /* 10 */
    { OP_Column,   0, 0,  0},
    { OP_String,   0, 0,  "table"},
    { OP_Ne,       0, 10, 0},
    { OP_Column,   0, 4,  0},
    { OP_Callback, 1, 0,  0},
    { OP_Goto,     0, 10, 0},
    { OP_Rewind,   0, 0,  0},           /* 17 */
    { OP_Next,     0, 25, 0},           /* 18 */
    { OP_Column,   0, 0,  0},
    { OP_String,   0, 0,  "index"},
    { OP_Ne,       0, 18, 0},
    { OP_Column,   0, 4,  0},
    { OP_Callback, 1, 0,  0},
    { OP_Goto,     0, 18, 0},
    { OP_Close,    2, 0,  0},           /* 25 */
    { OP_Halt,     0, 0,  0},
  };

  /* Create a virtual machine to run the initialization program.  Run
  ** the program.  The delete the virtual machine.
  */
  vdbe = sqliteVdbeCreate(db);
  if( vdbe==0 ){

    azArg[1] = 0;
    sqliteOpenCb(db, 1, azArg, 0);
    pTab = sqliteFindTable(db, MASTER_NAME);
    if( pTab ){
      pTab->readOnly = 1;
    }
    db->flags |= SQLITE_Initialized;
    sqliteCommitInternalChanges(db);
  }
  return rc;
}

/*
** The version of the library
*/

  /* Allocate the sqlite data structure */
  db = sqliteMalloc( sizeof(sqlite) );
  if( pzErrMsg ) *pzErrMsg = 0;
  if( db==0 ) goto no_mem_on_open;
  
  /* Open the backend database driver */
  rc = sqliteBtreeOpen(zFilename, mode, 100, &db->pBe);
  if( rc!=SQLITE_OK ){
    switch( rc ){
      default: {
        if( pzErrMsg ){
          sqliteSetString(pzErrMsg, "unable to open database: ", zFilename, 0);
        }
      }
    }
    sqliteFree(db);

    return rc;
  }

  /* Assume file format 1 unless the database says otherwise */
  db->file_format = 1;

  /* Attempt to read the schema */
  rc = sqliteInit(db, pzErrMsg);

}

/*
** Close an existing SQLite database
*/
void sqlite_close(sqlite *db){
  int i;
  sqliteBtreeClose(db->pBe);
  for(i=0; i<N_HASH; i++){
    Table *pNext, *pList = db->apTblHash[i];
    db->apTblHash[i] = 0;
    while( pList ){
      pNext = pList->pHash;
      pList->pHash = 0;
      sqliteDeleteTable(db, pList);

    if( rc!=SQLITE_OK ){
      sqliteStrRealloc(pzErrMsg);
      return rc;
    }
  }
  memset(&sParse, 0, sizeof(sParse));
  sParse.db = db;
  sParse.pBe = db->pBe;
  sParse.xCallback = xCallback;
  sParse.pArg = pArg;
  sqliteRunParser(&sParse, zSql, pzErrMsg);
  if( sqlite_malloc_failed ){
    sqliteSetString(pzErrMsg, "out of memory", 0);
    sParse.rc = SQLITE_NOMEM;
  }

**   http://www.hwaci.com/drh/
**
*************************************************************************
** This is the implementation of the page cache subsystem.
** 
** The page cache is used to access a database file.  The pager journals
** all writes in order to support rollback.  Locking is used to limit
** access to one or more reader or to one writer.
**
** @(#) $Id: pager.c,v 1.14 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include <fcntl.h>
#include <sys/stat.h>
#include <unistd.h>
#include <assert.h>

  void (*xDestructor)(void*); /* Call this routine when freeing pages */
  int nPage;                  /* Total number of in-memory pages */
  int nRef;                   /* Number of in-memory pages with PgHdr.nRef>0 */
  int mxPage;                 /* Maximum number of pages to hold in cache */
  int nHit, nMiss, nOvfl;     /* Cache hits, missing, and LRU overflows */
  unsigned char state;        /* SQLITE_UNLOCK, _READLOCK or _WRITELOCK */
  unsigned char errMask;      /* One of several kinds of errors */
  unsigned char tempFile;     /* zFilename is a temporary file */
  unsigned char readOnly;     /* True for a read-only database */
  unsigned char *aInJournal;  /* One bit for each page in the database file */
  PgHdr *pFirst, *pLast;      /* List of free pages */
  PgHdr *pAll;                /* List of all pages */
  PgHdr *aHash[N_PG_HASH];    /* Hash table to map page number of PgHdr */
};

/*

typedef struct PageRecord PageRecord;
struct PageRecord {
  Pgno pgno;                     /* The page number */
  char aData[SQLITE_PAGE_SIZE];  /* Original data for page pgno */
};

/*
** Journal files begin with the following magic string.  The data
** was obtained from /dev/random.  It is used only as a sanity check.
*/
static const unsigned char aJournalMagic[] = {
  0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd4,
};

/*
** Hash a page number
*/
#define pager_hash(PN)  ((PN)%N_PG_HASH)

/*
** Enable reference count tracking here:
*/
#if SQLITE_TEST
  int pager_refinfo_enable = 0;
  static void pager_refinfo(PgHdr *p){
    static int cnt = 0;
    if( !pager_refinfo_enable ) return;
    printf(
       "REFCNT: %4d addr=0x%08x nRef=%d\n",
       p->pgno, (int)PGHDR_TO_DATA(p), p->nRef
    );

    pPager->errMask |= PAGER_ERR_CORRUPT;
    rc = SQLITE_CORRUPT;
  }else{
    rc = pager_unwritelock(pPager);
  }
  return rc;
}

/*
** Locate a directory where we can potentially create a temporary
** file.
*/
static const char *findTempDir(void){
  static const char *azDirs[] = {
     ".",
     "/var/tmp",
     "/usr/tmp",
     "/tmp",
     "/temp",
     "./temp",
  };
  int i;
  struct stat buf;
  for(i=0; i<sizeof(azDirs)/sizeof(azDirs[0]); i++){
    if( stat(azDirs[i], &buf)==0 && S_ISDIR(buf.st_mode)
         && S_IWUSR(buf.st_mode) ){
       return azDirs[i];
    }
  }
  return 0;
}

/*
** Create a new page cache and put a pointer to the page cache in *ppPager.
** The file to be cached need not exist.  The file is not locked until
** the first call to sqlitepager_get() and is only held open until the
** last page is released using sqlitepager_unref().
*/
int sqlitepager_open(
  Pager **ppPager,         /* Return the Pager structure here */
  const char *zFilename,   /* Name of the database file to open */
  int mxPage,              /* Max number of in-memory cache pages */
  int nExtra               /* Extra bytes append to each in-memory page */
){
  Pager *pPager;
  int nameLen;
  int fd;
  int tempFile;
  int readOnly = 0;
  char zTemp[300];

  *ppPager = 0;
  if( sqlite_malloc_failed ){
    return SQLITE_NOMEM;
  }
  if( zFilename ){
    fd = open(zFilename, O_RDWR|O_CREAT, 0644);
    if( fd<0 ){
      fd = open(zFilename, O_RDONLY, 0);
      readOnly = 1;
    }
    tempFile = 0;
  }else{
    int cnt = 8;
    char *zDir = findTempDir();
    if( zDir==0 ) return SQLITE_CANTOPEN;
    do{
      cnt--;
      sprintf(zTemp,"%s/_sqlite_%u",(unsigned)sqliteRandomInteger());
      fd = open(zTemp, O_RDWR|O_CREAT|O_EXCL, 0600);
    }while( cnt>0 && fd<0 );
    zFilename = zTemp;
    tempFile = 1;
  }
  if( fd<0 ){
    return SQLITE_CANTOPEN;
  }
  nameLen = strlen(zFilename);
  pPager = sqliteMalloc( sizeof(*pPager) + nameLen*2 + 30 );
  if( pPager==0 ){
    close(fd);

  pPager->jfd = -1;
  pPager->nRef = 0;
  pPager->dbSize = -1;
  pPager->nPage = 0;
  pPager->mxPage = mxPage>5 ? mxPage : 10;
  pPager->state = SQLITE_UNLOCK;
  pPager->errMask = 0;
  pPager->tempFile = tempFile;
  pPager->readOnly = readOnly;
  pPager->pFirst = 0;
  pPager->pLast = 0;
  pPager->nExtra = nExtra;
  memset(pPager->aHash, 0, sizeof(pPager->aHash));
  *ppPager = pPager;
  return SQLITE_OK;
}

/*
** Set the destructor for this pager.  If not NULL, the destructor is called
** when the reference count on each page reaches zero.  The destructor can
** be used to clean up information in the extra segment appended to each page.
**
** The destructor is not called as a result sqlitepager_close().  
** Destructors are only called by sqlitepager_unref().
*/
void sqlitepager_set_destructor(Pager *pPager, void (*xDesc)(void*)){
  pPager->xDestructor = xDesc;
}

/*
** Return the total number of pages in the disk file associated with
** pPager.
*/
int sqlitepager_pagecount(Pager *pPager){
  int n;
  struct stat statbuf;
  assert( pPager!=0 );
  if( pPager->dbSize>=0 ){
    return pPager->dbSize;

  }
  for(pPg=pPager->pAll; pPg; pPg=pNext){
    pNext = pPg->pNextAll;
    sqliteFree(pPg);
  }
  if( pPager->fd>=0 ) close(pPager->fd);
  assert( pPager->jfd<0 );
  if( pPager->tempFile ){
    unlink(pPager->zFilename);
  }
  sqliteFree(pPager);
  return SQLITE_OK;
}

/*
** Return the page number for the given page data.
*/
Pgno sqlitepager_pagenumber(void *pData){
  PgHdr *p = DATA_TO_PGHDR(pData);
  return p->pgno;
}

/*

  page_ref(pPg);
  return SQLITE_OK;
}

/*
** Acquire a page.
**
** A read lock on the disk file is obtained when the first page acquired. 
** This read lock is dropped when the last page is released.
**
** A _get works for any page number greater than 0.  If the database
** file is smaller than the requested page, then no actual disk
** read occurs and the memory image of the page is initialized to
** all zeros.  The extra data appended to a page is always initialized
** to zeros the first time a page is loaded into memory.
**
** The acquisition might fail for several reasons.  In all cases,
** an appropriate error code is returned and *ppPage is set to NULL.
**
** See also sqlitepager_lookup().  Both this routine and _lookup() attempt
** to find a page in the in-memory cache first.  If the page is not already
** in memory, this routine goes to disk to read it in whereas _lookup()
** just returns 0.  This routine acquires a read-lock the first time it
** has to go to disk, and could also playback an old journal if necessary.
** Since _lookup() never goes to disk, it never has to deal with locks
** or journal files.
*/
int sqlitepager_get(Pager *pPager, Pgno pgno, void **ppPage){
  PgHdr *pPg;

** Acquire a page if it is already in the in-memory cache.  Do
** not read the page from disk.  Return a pointer to the page,
** or 0 if the page is not in cache.
**
** See also sqlitepager_get().  The difference between this routine
** and sqlitepager_get() is that _get() will go to the disk and read
** in the page if the page is not already in cache.  This routine
** returns NULL if the page is not in cache or if a disk I/O error 
** has ever happened.
*/
void *sqlitepager_lookup(Pager *pPager, Pgno pgno){
  PgHdr *pPg;

  /* Make sure we have not hit any critical errors.
  */ 
  if( pPager==0 || pgno==0 ){

int sqlitepager_write(void *pData){
  PgHdr *pPg = DATA_TO_PGHDR(pData);
  Pager *pPager = pPg->pPager;
  int rc = SQLITE_OK;

  if( pPager->errMask ){ 
    return pager_errcode(pPager);
  }
  if( pPager->readOnly ){
    return SQLITE_PERM;
  }
  pPg->dirty = 1;
  if( pPg->inJournal ){ return SQLITE_OK; }
  assert( pPager->state!=SQLITE_UNLOCK );
  if( pPager->state==SQLITE_READLOCK ){
    assert( pPager->aInJournal==0 );
    pPager->aInJournal = sqliteMalloc( pPager->dbSize/8 + 1 );

  if( rc!=SQLITE_OK ){
    rc = SQLITE_CORRUPT;
    pPager->errMask |= PAGER_ERR_CORRUPT;
  }
  pPager->dbSize = -1;
  return rc;
};

/*
** Return TRUE if the database file is opened read-only.  Return FALSE
** if the database is (in theory) writable.
*/
int sqlitepager_isreadonly(Pager *pPager){
  return pPager->readonly;
}

/*
** This routine is used for testing and analysis only.
*/
int *sqlitepager_stats(Pager *pPager){
  static int a[9];
  a[0] = pPager->nRef;

**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite page cache
** subsystem.  The page cache subsystem reads and writes a file a page
** at a time and provides a journal for rollback.
**
** @(#) $Id: pager.h,v 1.8 2001/09/13 13:46:57 drh Exp $
*/

/*
** The size of one page
*/
#define SQLITE_PAGE_SIZE 1024

int sqlitepager_unref(void*);
Pgno sqlitepager_pagenumber(void*);
int sqlitepager_write(void*);
int sqlitepager_iswriteable(void*);
int sqlitepager_pagecount(Pager*);
int sqlitepager_commit(Pager*);
int sqlitepager_rollback(Pager*);
int sqlitepager_isreadonly(Pager*);
int *sqlitepager_stats(Pager*);

#ifdef SQLITE_TEST
void sqlitepager_refdump(Pager*);
int pager_refinfo_enable;
#endif

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements.
**
** $Id: select.c,v 1.32 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/

        */
        unionTab = pParse->nTab++;
        if( p->pOrderBy 
        && matchOrderbyToColumn(pParse, p, p->pOrderBy, unionTab, 1) ){
          return 1;
        }
        if( p->op!=TK_ALL ){
          sqliteVdbeAddOp(v, OP_OpenTemp, unionTab, 0, 0, 0);
          sqliteVdbeAddOp(v, OP_KeyAsData, unionTab, 1, 0, 0);
        }else{
          sqliteVdbeAddOp(v, OP_OpenTemp, unionTab, 0, 0, 0);
        }
      }

      /* Code the SELECT statements to our left
      */
      rc = sqliteSelect(pParse, pPrior, priorOp, unionTab);
      if( rc ) return rc;

      ** by allocating the tables we will need.
      */
      tab1 = pParse->nTab++;
      tab2 = pParse->nTab++;
      if( p->pOrderBy && matchOrderbyToColumn(pParse,p,p->pOrderBy,tab1,1) ){
        return 1;
      }
      sqliteVdbeAddOp(v, OP_OpenTemp, tab1, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_KeyAsData, tab1, 1, 0, 0);

      /* Code the SELECTs to our left into temporary table "tab1".
      */
      rc = sqliteSelect(pParse, pPrior, SRT_Union, tab1);
      if( rc ) return rc;

      /* Code the current SELECT into temporary table "tab2"
      */
      sqliteVdbeAddOp(v, OP_OpenTemp, tab2, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_KeyAsData, tab2, 1, 0, 0);
      p->pPrior = 0;
      rc = sqliteSelect(pParse, p, SRT_Union, tab2);
      p->pPrior = pPrior;
      if( rc ) return rc;

      /* Generate code to take the intersection of the two temporary

    sqliteVdbeAddOp(v, OP_Null, 0, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_MemStore, iParm, 0, 0, 0);
  }

  /* Begin the database scan
  */
  if( isDistinct ){
    sqliteVdbeAddOp(v, OP_OpenTemp, distinct, 0, 0, 0);
  }
  pWInfo = sqliteWhereBegin(pParse, pTabList, pWhere, 0);
  if( pWInfo==0 ) return 1;

  /* Use the standard inner loop if we are not dealing with
  ** aggregates
  */

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains code to implement the "sqlite" command line
** utility for accessing SQLite databases.
**
** $Id: shell.c,v 1.32 2001/09/13 13:46:57 drh Exp $
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "sqlite.h"
#include <unistd.h>
#include <ctype.h>
#ifdef OS_UNIX
# include <signal.h>
#endif

#if defined(HAVE_READLINE) && HAVE_READLINE==1
# include <readline/readline.h>
# include <readline/history.h>
#else
# define readline(p) getline(p,stdin)
# define add_history(X) 
#endif

/*
** The following is the open SQLite database.  We make a pointer
** to this database a static variable so that it can be accessed
** by the SIGINT handler to interrupt database processing.

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.14 2001/09/13 13:46:57 drh Exp $
*/
#ifndef _SQLITE_H_
#define _SQLITE_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** The version of the SQLite library.

#define SQLITE_INTERRUPT 8    /* Operation terminated by sqlite_interrupt() */
#define SQLITE_IOERR     9    /* Disk full or other I/O error */
#define SQLITE_CORRUPT   10   /* The database disk image is malformed */
#define SQLITE_NOTFOUND  11   /* Table or record not found */
#define SQLITE_FULL      12   /* Insertion failed because database is full */
#define SQLITE_CANTOPEN  13   /* Unable to open the database file */
#define SQLITE_PROTOCOL  14   /* Database lock protocol error */
#define SQLITE_EMPTY     15   /* Database table is empty */

/* This function causes any pending database operation to abort and
** return at its earliest opportunity.  This routine is typically
** called in response to a user action such as pressing "Cancel"
** or Ctrl-C where the user wants a long query operation to halt
** immediately.
*/

** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.43 2001/09/13 13:46:57 drh Exp $
*/
#include "sqlite.h"

#include "vdbe.h"
#include "parse.h"
#ifndef DISABLE_GDBM
#include <gdbm.h>
#endif
#include <stdio.h>
#include <stdlib.h>

typedef struct Select Select;
typedef struct AggExpr AggExpr;

/*
** Each database is an instance of the following structure
*/
struct sqlite {
  Btree *pBe;                   /* The B*Tree backend */
  int flags;                    /* Miscellanous flags. See below */
  int file_format;              /* What file format version is this database? */
  int nTable;                   /* Number of tables in the database */
  void *pBusyArg;               /* 1st Argument to the busy callback */
  int (*xBusyCallback)(void *,const char*,int);  /* The busy callback */
  Table *apTblHash[N_HASH];     /* All tables of the database */
  Index *apIdxHash[N_HASH];     /* All indices of the database */
};

/*
** Possible values for the sqlite.flags.
*/
#define SQLITE_VdbeTrace      0x00000001  /* True to trace VDBE execution */
#define SQLITE_Initialized    0x00000002  /* True after initialization */
#define SQLITE_Interrupt      0x00000004  /* Cancel current operation */
#define SQLITE_InTrans        0x00000008  /* True if in a transaction */
#define SQLITE_InternChanges  0x00000010  /* Uncommitted Hash table changes */

/*
** Current file format version
*/
#define SQLITE_FileFormat 2

/*

** an instance of the following structure.
*/
struct Table {
  char *zName;     /* Name of the table */
  Table *pHash;    /* Next table with same hash on zName */
  int nCol;        /* Number of columns in this table */
  Column *aCol;    /* Information about each column */
  Index *pIndex;   /* List of SQL indexes on this table. */
  int tnum;        /* Page containing root for this table */
  int readOnly;    /* True if this table should not be written by the user */
  int isCommit;    /* True if creation of this table has been committed */
  int isDelete;    /* True if deletion of this table has not been comitted */    
};

/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**
** The columns of the table that are to be indexed are described

struct Index {
  char *zName;     /* Name of this index */
  Index *pHash;    /* Next index with the same hash on zName */
  int nColumn;     /* Number of columns in the table used by this index */
  int *aiColumn;   /* Which columns are used by this index.  1st is 0 */
  Table *pTable;   /* The SQL table being indexed */
  int isUnique;    /* True if keys must all be unique */
  int isCommit;    /* True if creation of this index has been committed */
  int isDelete;    /* True if deletion of this index has not been comitted */
  Index *pNext;    /* The next index associated with the same table */
};

/*
** Each token coming out of the lexer is an instance of
** this structure.
*/

};

/*
** An SQL parser context
*/
struct Parse {
  sqlite *db;          /* The main database structure */
  Btree *pBe;          /* The database backend */
  int rc;              /* Return code from execution */
  sqlite_callback xCallback;  /* The callback function */
  void *pArg;          /* First argument to the callback function */
  char *zErrMsg;       /* An error message */
  Token sErrToken;     /* The token at which the error occurred */
  Token sFirstToken;   /* The first token parsed */
  Token sLastToken;    /* The last token parsed */

void sqliteExec(Parse*);
Expr *sqliteExpr(int, Expr*, Expr*, Token*);
void sqliteExprSpan(Expr*,Token*,Token*);
Expr *sqliteExprFunction(ExprList*, Token*);
void sqliteExprDelete(Expr*);
ExprList *sqliteExprListAppend(ExprList*,Expr*,Token*);
void sqliteExprListDelete(ExprList*);
void sqliteCommitInternalChanges(sqlite*);
void sqliteRollbackInternalChanges(sqlite*);
void sqliteStartTable(Parse*,Token*,Token*);
void sqliteAddColumn(Parse*,Token*);
void sqliteAddDefaultValue(Parse*,Token*,int);
void sqliteEndTable(Parse*,Token*);
void sqliteDropTable(Parse*, Token*);
void sqliteDeleteTable(sqlite*, Table*);
void sqliteInsert(Parse*, Token*, ExprList*, Select*, IdList*);

int sqliteRandomInteger(void);
void sqliteRandomName(char*,char*);
char *sqliteDbbeNameToFile(const char*,const char*,const char*);
void sqliteBeginTransaction(Parse*);
void sqliteCommitTransaction(Parse*);
void sqliteRollbackTransaction(Parse*);
char *sqlite_mprintf(const char *, ...);
const char *sqliteErrStr(int);

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle UPDATE statements.
**
** $Id: update.c,v 1.12 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
*/
void sqliteUpdate(

    if( i<pIdx->nColumn ) apIdx[nIdx++] = pIdx;
  }

  /* Begin generating code.
  */
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto update_cleanup;
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
  }

  /* Begin the database scan
  */
  sqliteVdbeAddOp(v, OP_ListOpen, 0, 0, 0, 0);
  pWInfo = sqliteWhereBegin(pParse, pTabList, pWhere, 1);
  if( pWInfo==0 ) goto update_cleanup;

  /* Remember the index of every item to be updated.
  */
  sqliteVdbeAddOp(v, OP_ListWrite, 0, 0, 0, 0);

  /* End the database scan loop.
  */
  sqliteWhereEnd(pWInfo);

  /* Rewind the list of records that need to be updated and
  ** open every index that needs updating.
  */
  sqliteVdbeAddOp(v, OP_ListRewind, 0, 0, 0, 0);
  base = pParse->nTab;
  sqliteVdbeAddOp(v, OP_Open, base, pTab->tnum, 0, 0);
  for(i=0; i<nIdx; i++){
    sqliteVdbeAddOp(v, OP_Open, base+i+1, apIdx[i]->tnum, 0, 0);
  }

  /* Loop over every record that needs updating.  We have to load
  ** the old data for each record to be updated because some columns
  ** might not change and we will need to copy the old value.
  ** Also, the old data is needed to delete the old index entires.
  */
  end = sqliteVdbeMakeLabel(v);
  addr = sqliteVdbeAddOp(v, OP_ListRead, 0, end, 0, 0);
  sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
  sqliteVdbeAddOp(v, OP_MoveTo, base, 0, 0, 0);

  /* Delete the old indices for the current record.
  */
  for(i=0; i<nIdx; i++){
    sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
    pIdx = apIdx[i];
    for(j=0; j<pIdx->nColumn; j++){
      sqliteVdbeAddOp(v, OP_Column, base, pIdx->aiColumn[j], 0, 0);
    }
    sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_DeleteIdx, base+i+1, 0, 0, 0);
  }

  /* Compute a completely new data for this record.  
  */
  for(i=0; i<pTab->nCol; i++){
    j = aXRef[i];
    if( j<0 ){
      sqliteVdbeAddOp(v, OP_Column, base, i, 0, 0);
    }else{
      sqliteExprCode(pParse, pChanges->a[j].pExpr);
    }
  }

  /* Insert new index entries that correspond to the new data
  */
  for(i=0; i<nIdx; i++){
    sqliteVdbeAddOp(v, OP_Dup, pTab->nCol, 0, 0, 0); /* The KEY */
    pIdx = apIdx[i];
    for(j=0; j<pIdx->nColumn; j++){
      sqliteVdbeAddOp(v, OP_Dup, j+pTab->nCol-pIdx->aiColumn[j], 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_PutIdx, base+i+1, 0, 0, 0);
  }

  /* Write the new data back into the database.
  */
  sqliteVdbeAddOp(v, OP_MakeRecord, pTab->nCol, 0, 0, 0);
  sqliteVdbeAddOp(v, OP_Put, base, 0, 0, 0);

  /* Repeat the above with the next record to be updated, until
  ** all record selected by the WHERE clause have been updated.
  */
  sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);
  sqliteVdbeAddOp(v, OP_ListClose, 0, 0, 0, end);
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
  }

update_cleanup:
  sqliteFree(apIdx);
  sqliteFree(aXRef);
  sqliteIdListDelete(pTabList);
  sqliteExprListDelete(pChanges);
  sqliteExprDelete(pWhere);
  return;
}

**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.22 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.

        zString++;
        break;
      }
    }
  }
  return *zString==0;
}

/*
** Return a static string that describes the kind of error specified in the
** argument.
*/
const char *sqliteErrStr(int rc){
  char *z = 0;
  switch( rc ){
    case SQLITE_OK:          z = "not an error";  break;
    case SQLITE_ERROR:       z = "SQL logic error or missing database"; break;
    case SQLITE_INTERNAL:    z = "internal SQLite implementation flaw"; break;
    case SQLITE_PERM:        z = "access permission denied"; break;
    case SQLITE_ABORT:       z = "callback requested query abort"; break;
    case SQLITE_BUSY:        z = "database in use by another process"; break;
    case SQLITE_NOMEM:       z = "out of memory"; break;
    case SQLITE_READONLY:    z = "attempt to write a readonly database"; break;
    case SQLITE_INTERRUPT:   z = "interrupted"; break;
    case SQLITE_IOERR:       z = "disk I/O error"; break;
    case SQLITE_CORRUPT:     z = "database disk image is malformed"; break;
    case SQLITE_NOTFOUND:    z = "table or record not found"; break;
    case SQLITE_FULL:        z = "database is full"; break;
    case SQLITE_CANTOPEN:    z = "unable to open database file"; break;
    case SQLITE_PROTOCOL:    z = "database locking protocol failure"; break;
    case SQLITE_EMPTY:       z = "table contains no data";
    default:
  }
  return z;
}

** inplicit conversion from one type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.60 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** SQL is translated into a sequence of instructions to be
** executed by a virtual machine.  Each instruction is an instance
** of the following structure.
*/
typedef struct VdbeOp Op;

/*
** Boolean values
*/
typedef unsigned char Bool;

/*
** A cursor is a pointer into a database file.  The database file
** can represent either an SQL table or an SQL index.  Each file is
** a bag of key/data pairs.  The cursor can loop over all key/data
** pairs (in an arbitrary order) or it can retrieve a particular
** key/data pair given a copy of the key.
** 
** Every cursor that the virtual machine has open is represented by an
** instance of the following structure.
*/
struct Cursor {
  BtCursor *pCursor;    /* The cursor structure of the backend */

  int lastRecno;        /* Last recno from a Next or NextIdx operation */
  Bool recnoIsValid;    /* True if lastRecno is valid */
  Bool keyAsData;       /* The OP_Column command works on key instead of data */
  Bool atFirst;         /* True if pointing to first entry */
  Btree *pBt;           /* Separate file holding temporary table */
  char *zKey;           /* Key used in BeginIdx and NextIdx operators */
  int nKey;             /* Number of bytes in zKey[] */
  char *zBuf;           /* Buffer space used to hold a copy of zKey[] */
};
typedef struct Cursor Cursor;

/*
** A sorter builds a list of elements to be sorted.  Each element of
** the list is an instance of the following structure.
*/

  char *zLine;        /* A single line from the input file */
  int nLineAlloc;     /* Number of spaces allocated for zLine */
  int nMem;           /* Number of memory locations currently allocated */
  Mem *aMem;          /* The memory locations */
  Agg agg;            /* Aggregate information */
  int nSet;           /* Number of sets allocated */
  Set *aSet;          /* An array of sets */
  int *pTableRoot;    /* Write root page no. for new tables to this addr */
  int *pIndexRoot;    /* Write root page no. for new indices to this addr */
  int nFetch;         /* Number of OP_Fetch instructions executed */
};

/*
** Create a new virtual database engine.
*/
Vdbe *sqliteVdbeCreate(sqlite *db){

/*
** Turn tracing on or off
*/
void sqliteVdbeTrace(Vdbe *p, FILE *trace){
  p->trace = trace;
}

/*
** Cause the next OP_CreateTable or OP_CreateIndex instruction that executes
** to write the page number of the root page for the new table or index it
** creates into the memory location *pAddr.
**
** The pointer to the place to write the page number is cleared after
** the OP_Create* statement.  If OP_Create* is executed and the pointer
** is NULL, an error results.  Hence the address can only be used once.
** If the root address fields are set but OP_Create* operations never
** execute, that too is an error.
*/
void sqliteVdbeTableRootAddr(Vdbe *p, int *pAddr){
  p->pTableRoot = pAddr;
}
void sqliteVdbeIndexRootAddr(Vdbe *p, int *pAddr){
  p->pIndexRoot = pAddr;
}

/*
** Add a new instruction to the list of instructions current in the
** VDBE.  Return the address of the new instruction.
**
** Parameters:
**

      int p2 = aOp[i].p2;
      if( p2<0 ) p2 = addr + ADDR(p2);
      sqliteVdbeAddOp(p, aOp[i].opcode, aOp[i].p1, p2, aOp[i].p3, 0);
    }
  }
  return addr;
}

/*
** Change the value of the P1 operand for a specific instruction.
** This routine is useful when a large program is loaded from a
** static array using sqliteVdbeAddOpList but we want to make a
** few minor changes to the program.
*/
void sqliteVdbeChangeP1(Vdbe *p, int addr, int val){
  if( p && addr>=0 && p->nOp>addr ){
    p->aOp[addr].p1 = val;
  }
}

/*
** Change the value of the P3 operand for a specific instruction.
** This routine is useful when a large program is loaded from a
** static array using sqliteVdbeAddOpList but we want to make a
** few minor changes to the program.
*/

    p = pNext;
  }
}

/*
** Clean up the VM after execution.
**
** This routine will automatically close any cursors, lists, and/or
** sorters that were left open.
*/
static void Cleanup(Vdbe *p){
  int i;
  PopStack(p, p->tos+1);
  sqliteFree(p->azColName);
  p->azColName = 0;
  for(i=0; i<p->nCursor; i++){
    Cursor *pCx = &p->aCsr[i];
    if( pCx->pCursor ){
      sqliteBtreeCloseCursor(pCx->pCursor);
      pCx->pCursor = 0;
    }
    if( pCx->zKey ){
      sqliteFree(pCx->zKey);
      pCx->zKey = 0;
    }
    if( pCx->pBt ){
      sqliteBtreeClose(pCx->pBt);
      pCx->pBt = 0;
    }
  }
  sqliteFree(p->aCsr);
  p->aCsr = 0;
  p->nCursor = 0;
  for(i=0; i<p->nMem; i++){
    if( p->aMem[i].s.flags & STK_Dyn ){

  AggReset(&p->agg);
  for(i=0; i<p->nSet; i++){
    SetClear(&p->aSet[i]);
  }
  sqliteFree(p->aSet);
  p->aSet = 0;
  p->nSet = 0;
  p->pTableRoot = 0;
  p->pIndexRoot = 0;
}

/*
** Delete an entire VDBE.
*/
void sqliteVdbeDelete(Vdbe *p){
  int i;

**
** If any of the numeric OP_ values for opcodes defined in sqliteVdbe.h
** change, be sure to change this array to match.  You can use the
** "opNames.awk" awk script which is part of the source tree to regenerate
** this array, then copy and paste it into this file, if you want.
*/
static char *zOpName[] = { 0,
  "Transaction",       "Commit",            "Rollback",          "Open",
  "OpenTemp",          "Close",             "MoveTo",            "Fcnt",
  "NewRecno",          "Put",               "Distinct",          "Found",
  "NotFound",          "Delete",            "Column",            "KeyAsData",
  "Recno",             "FullKey",           "Rewind",            "Next",
  "Destroy",           "CreateIndex",       "CreateTable",       "Reorganize",
  "BeginIdx",          "NextIdx",           "PutIdx",            "DeleteIdx",
  "MemLoad",           "MemStore",          "ListOpen",          "ListWrite",
  "ListRewind",        "ListRead",          "ListClose",         "SortOpen",
  "SortPut",           "SortMakeRec",       "SortMakeKey",       "Sort",
  "SortNext",          "SortKey",           "SortCallback",      "SortClose",
  "FileOpen",          "FileRead",          "FileField",         "FileClose",
  "AggReset",          "AggFocus",          "AggIncr",           "AggNext",
  "AggSet",            "AggGet",            "SetInsert",         "SetFound",
  "SetNotFound",       "SetClear",          "MakeRecord",        "MakeKey",
  "Goto",              "If",                "Halt",              "ColumnCount",
  "ColumnName",        "Callback",          "Integer",           "String",
  "Null",              "Pop",               "Dup",               "Pull",
  "Add",               "AddImm",            "Subtract",          "Multiply",
  "Divide",            "Min",               "Max",               "Like",
  "Glob",              "Eq",                "Ne",                "Lt",
  "Le",                "Gt",                "Ge",                "IsNull",
  "NotNull",           "Negative",          "And",               "Or",
  "Not",               "Concat",            "Noop",              "Strlen",
  "Substr",          
};

/*
** Given the name of an opcode, return its number.  Return 0 if
** there is no match.
**
** This routine is used for testing and debugging.

  void *pBusyArg,            /* 1st argument to the busy callback */
  int (*xBusy)(void*,const char*,int)  /* Called when a file is busy */
){
  int pc;                    /* The program counter */
  Op *pOp;                   /* Current operation */
  int rc;                    /* Value to return */
  Dbbe *pBe = p->pBe;        /* The backend driver */

  sqlite *db = p->db;        /* The database */
  int rollbackOnError = 0;   /* If TRUE, rollback if the script fails.
  char **zStack;             /* Text stack */
  Stack *aStack;             /* Additional stack information */
  char zBuf[100];            /* Space to sprintf() an integer */


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

      fprintf(p->trace,"%4d %-12s %4d %4d %s\n",
        pc, zOpName[pOp->opcode], pOp->p1, pOp->p2,
           pOp->p3 ? pOp->p3 : "");
    }
#endif

    switch( pOp->opcode ){

/*****************************************************************************
** What follows is a massive switch statement where each case implements a
** separate instruction in the virtual machine.  If we follow the usual
** indentation conventions, each case should be indented by 6 spaces.  But
** that is a lot of wasted space on the left margin.  So the code within
** the switch statement will break with convention and be flush-left. Another
** big comment (similar to this one) will mark the point in the code where
** we transition back to normal indentation.
*****************************************************************************/

/* Opcode:  Goto P2 * *
**
** An unconditional jump to address P2.
** The next instruction executed will be 
** the one at index P2 from the beginning of
** the program.
*/
case OP_Goto: {
  pc = pOp->p2 - 1;
  break;
}

/* Opcode:  Halt * * *
**
** Exit immediately.  All open DBs, Lists, Sorts, etc are closed
** automatically.
*/
case OP_Halt: {
  pc = p->nOp-1;
  break;
}

/* Opcode: Integer P1 * *
**
** The integer value P1 is pushed onto the stack.
*/
case OP_Integer: {
  int i = ++p->tos;
  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  aStack[i].i = pOp->p1;
  aStack[i].flags = STK_Int;
  break;
}

/* Opcode: String * * P3
**
** The string value P3 is pushed onto the stack.
*/
case OP_String: {
  int i = ++p->tos;
  char *z;
  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  z = pOp->p3;
  if( z==0 ) z = "";
  zStack[i] = z;
  aStack[i].n = strlen(z) + 1;
  aStack[i].flags = STK_Str;
  break;
}

/* Opcode: Null * * *
**
** Push a NULL value onto the stack.
*/
case OP_Null: {
  int i = ++p->tos;
  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  zStack[i] = 0;
  aStack[i].flags = STK_Null;
  break;
}

/* Opcode: Pop P1 * *
**
** P1 elements are popped off of the top of stack and discarded.
*/
case OP_Pop: {
  PopStack(p, pOp->p1);
  break;
}

/* Opcode: Dup P1 * *
**
** A copy of the P1-th element of the stack 
** is made and pushed onto the top of the stack.
** The top of the stack is element 0.  So the
** instruction "Dup 0 0 0" will make a copy of the
** top of the stack.
*/
case OP_Dup: {
  int i = p->tos - pOp->p1;
  int j = ++p->tos;
  VERIFY( if( i<0 ) goto not_enough_stack; )
  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  aStack[j] = aStack[i];
  if( aStack[i].flags & STK_Dyn ){
    zStack[j] = sqliteMalloc( aStack[j].n );
    if( zStack[j]==0 ) goto no_mem;
    memcpy(zStack[j], zStack[i], aStack[j].n);
  }else{
    zStack[j] = zStack[i];
  }
  break;
}

/* Opcode: Pull P1 * *
**
** The P1-th element is removed from its current location on 
** the stack and pushed back on top of the stack.  The
** top of the stack is element 0, so "Pull 0 0 0" is
** a no-op.
*/
case OP_Pull: {
  int from = p->tos - pOp->p1;
  int to = p->tos;
  int i;
  Stack ts;
  char *tz;
  VERIFY( if( from<0 ) goto not_enough_stack; )
  ts = aStack[from];
  tz = zStack[from];
  for(i=from; i<to; i++){
    aStack[i] = aStack[i+1];
    zStack[i] = zStack[i+1];
  }
  aStack[to] = ts;
  zStack[to] = tz;
  break;
}

/* Opcode: ColumnCount P1 * *
**
** Specify the number of column values that will appear in the
** array passed as the 4th parameter to the callback.  No checking
** is done.  If this value is wrong, a coredump can result.
*/
case OP_ColumnCount: {
  p->azColName = sqliteRealloc(p->azColName, (pOp->p1+1)*sizeof(char*));
  if( p->azColName==0 ) goto no_mem;
  p->azColName[pOp->p1] = 0;
  break;
}

/* Opcode: ColumnName P1 * P3
**
** P3 becomes the P1-th column name (first is 0).  An array of pointers
** to all column names is passed as the 4th parameter to the callback.
** The ColumnCount opcode must be executed first to allocate space to
** hold the column names.  Failure to do this will likely result in
** a coredump.
*/
case OP_ColumnName: {
  p->azColName[pOp->p1] = pOp->p3 ? pOp->p3 : "";
  break;
}

/* Opcode: Callback P1 * *
**
** Pop P1 values off the stack and form them into an array.  Then
** invoke the callback function using the newly formed array as the
** 3rd parameter.
*/
case OP_Callback: {
  int i = p->tos - pOp->p1 + 1;
  int j;
  VERIFY( if( i<0 ) goto not_enough_stack; )
  VERIFY( if( NeedStack(p, p->tos+2) ) goto no_mem; )
  for(j=i; j<=p->tos; j++){
    if( (aStack[j].flags & STK_Null)==0 ){
      if( Stringify(p, j) ) goto no_mem;
    }
  }
  zStack[p->tos+1] = 0;
  if( xCallback!=0 ){
    if( xCallback(pArg, pOp->p1, &zStack[i], p->azColName)!=0 ){
      rc = SQLITE_ABORT;
    }
  }
  PopStack(p, pOp->p1);
  break;
}

/* Opcode: Concat P1 P2 P3
**
** Look at the first P1 elements of the stack.  Append them all 
** together with the lowest element first.  Use P3 as a separator.  
** Put the result on the top of the stack.  The original P1 elements
** are popped from the stack if P2==0 and retained if P2==1.
**
** If P3 is NULL, then use no separator.  When P1==1, this routine
** makes a copy of the top stack element into memory obtained
** from sqliteMalloc().
*/
case OP_Concat: {
  char *zNew;
  int nByte;
  int nField;
  int i, j;
  char *zSep;
  int nSep;

  nField = pOp->p1;
  zSep = pOp->p3;
  if( zSep==0 ) zSep = "";
  nSep = strlen(zSep);
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = 1 - nSep;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( aStack[i].flags & STK_Null ){
      nByte += nSep;
    }else{
      if( Stringify(p, i) ) goto no_mem;
      nByte += aStack[i].n - 1 + nSep;
    }
  }
  zNew = sqliteMalloc( nByte );
  if( zNew==0 ) goto no_mem;
  j = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      memcpy(&zNew[j], zStack[i], aStack[i].n-1);
      j += aStack[i].n-1;
    }
    if( nSep>0 && i<p->tos ){
      memcpy(&zNew[j], zSep, nSep);
      j += nSep;
    }
  }
  zNew[j] = 0;
  if( pOp->p2==0 ) PopStack(p, nField);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  zStack[p->tos] = zNew;
  break;
}

/* Opcode: Add * * *
**
** Pop the top two elements from the stack, add them together,
** and push the result back onto the stack.  If either element
** is a string then it is converted to a double using the atof()
** function before the addition.
*/
/* Opcode: Multiply * * *
**
** Pop the top two elements from the stack, multiply them together,
** and push the result back onto the stack.  If either element
** is a string then it is converted to a double using the atof()
** function before the multiplication.
*/
/* Opcode: Subtract * * *
**
** Pop the top two elements from the stack, subtract the
** first (what was on top of the stack) from the second (the
** next on stack)
** and push the result back onto the stack.  If either element
** is a string then it is converted to a double using the atof()
** function before the subtraction.
*/
/* Opcode: Divide * * *
**
** Pop the top two elements from the stack, divide the
** first (what was on top of the stack) from the second (the
** next on stack)
** and push the result back onto the stack.  If either element
** is a string then it is converted to a double using the atof()
** function before the division.  Division by zero returns NULL.
*/
case OP_Add:
case OP_Subtract:
case OP_Multiply:
case OP_Divide: {
  int tos = p->tos;
  int nos = tos - 1;
  VERIFY( if( nos<0 ) goto not_enough_stack; )
  if( (aStack[tos].flags & aStack[nos].flags & STK_Int)==STK_Int ){
    int a, b;
    a = aStack[tos].i;
    b = aStack[nos].i;
    switch( pOp->opcode ){
      case OP_Add:         b += a;       break;
      case OP_Subtract:    b -= a;       break;
      case OP_Multiply:    b *= a;       break;
      default: {
        if( a==0 ) goto divide_by_zero;
        b /= a;
        break;
      }
    }
    POPSTACK;
    Release(p, nos);
    aStack[nos].i = b;
    aStack[nos].flags = STK_Int;
  }else{
    double a, b;
    Realify(p, tos);
    Realify(p, nos);
    a = aStack[tos].r;
    b = aStack[nos].r;
    switch( pOp->opcode ){
      case OP_Add:         b += a;       break;
      case OP_Subtract:    b -= a;       break;
      case OP_Multiply:    b *= a;       break;
      default: {
        if( a==0.0 ) goto divide_by_zero;
        b /= a;
        break;
      }
    }
    POPSTACK;
    Release(p, nos);
    aStack[nos].r = b;
    aStack[nos].flags = STK_Real;
  }
  break;

divide_by_zero:
  PopStack(p, 2);
  p->tos = nos;
  aStack[nos].flags = STK_Null;
  break;
}

/* Opcode: Max * * *
**
** Pop the top two elements from the stack then push back the
** largest of the two.
*/
case OP_Max: {
  int tos = p->tos;
  int nos = tos - 1;
  int ft, fn;
  int copy = 0;
  VERIFY( if( nos<0 ) goto not_enough_stack; )
  ft = aStack[tos].flags;
  fn = aStack[nos].flags;
  if( fn & STK_Null ){
    copy = 1;
  }else if( (ft & fn & STK_Int)==STK_Int ){
    copy = aStack[nos].i<aStack[tos].i;
  }else if( ( (ft|fn) & (STK_Int|STK_Real) ) !=0 ){
    Realify(p, tos);
    Realify(p, nos);
    copy = aStack[tos].r>aStack[nos].r;
  }else{
    if( Stringify(p, tos) || Stringify(p, nos) ) goto no_mem;
    copy = sqliteCompare(zStack[tos],zStack[nos])>0;
  }
  if( copy ){
    Release(p, nos);
    aStack[nos] = aStack[tos];
    zStack[nos] = zStack[tos];
    zStack[tos] = 0;
    aStack[tos].flags = 0;
  }else{
    Release(p, tos);
  }
  p->tos = nos;
  break;
}

/* Opcode: Min * * *
**
** Pop the top two elements from the stack then push back the
** smaller of the two. 
*/
case OP_Min: {
  int tos = p->tos;
  int nos = tos - 1;
  int ft, fn;
  int copy = 0;
  VERIFY( if( nos<0 ) goto not_enough_stack; )
  ft = aStack[tos].flags;
  fn = aStack[nos].flags;
  if( fn & STK_Null ){
    copy = 1;
  }else if( ft & STK_Null ){
    copy = 0;
  }else if( (ft & fn & STK_Int)==STK_Int ){
    copy = aStack[nos].i>aStack[tos].i;
  }else if( ( (ft|fn) & (STK_Int|STK_Real) ) !=0 ){
    Realify(p, tos);
    Realify(p, nos);
    copy = aStack[tos].r<aStack[nos].r;
  }else{
    if( Stringify(p, tos) || Stringify(p, nos) ) goto no_mem;
    copy = sqliteCompare(zStack[tos],zStack[nos])<0;
  }
  if( copy ){
    Release(p, nos);
    aStack[nos] = aStack[tos];
    zStack[nos] = zStack[tos];
    zStack[tos] = 0;
    aStack[tos].flags = 0;
  }else{
    Release(p, tos);
  }
  p->tos = nos;
  break;
}

/* Opcode: AddImm  P1 * *
** 
** Add the value P1 to whatever is on top of the stack.
*/
case OP_AddImm: {
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  Integerify(p, tos);
  aStack[tos].i += pOp->p1;
  break;
}

/* Opcode: Eq * P2 *
**
** Pop the top two elements from the stack.  If they are equal, then
** jump to instruction P2.  Otherwise, continue to the next instruction.
*/
/* Opcode: Ne * P2 *
**
** Pop the top two elements from the stack.  If they are not equal, then
** jump to instruction P2.  Otherwise, continue to the next instruction.
*/
/* Opcode: Lt * P2 *
**
** Pop the top two elements from the stack.  If second element (the
** next on stack) is less than the first (the top of stack), then
** jump to instruction P2.  Otherwise, continue to the next instruction.
** In other words, jump if NOS<TOS.
*/
/* Opcode: Le * P2 *
**
** Pop the top two elements from the stack.  If second element (the
** next on stack) is less than or equal to the first (the top of stack),
** then jump to instruction P2. In other words, jump if NOS<=TOS.
*/
/* Opcode: Gt * P2 *
**
** Pop the top two elements from the stack.  If second element (the
** next on stack) is greater than the first (the top of stack),
** then jump to instruction P2. In other words, jump if NOS>TOS.
*/
/* Opcode: Ge * P2 *
**
** Pop the top two elements from the stack.  If second element (the next
** on stack) is greater than or equal to the first (the top of stack),
** then jump to instruction P2. In other words, jump if NOS>=TOS.
*/
case OP_Eq:
case OP_Ne:
case OP_Lt:
case OP_Le:
case OP_Gt:
case OP_Ge: {
  int tos = p->tos;
  int nos = tos - 1;
  int c;
  int ft, fn;
  VERIFY( if( nos<0 ) goto not_enough_stack; )
  ft = aStack[tos].flags;
  fn = aStack[nos].flags;
  if( (ft & fn)==STK_Int ){
    c = aStack[nos].i - aStack[tos].i;
  }else{
    if( Stringify(p, tos) || Stringify(p, nos) ) goto no_mem;
    c = sqliteCompare(zStack[nos], zStack[tos]);
  }
  switch( pOp->opcode ){
    case OP_Eq:    c = c==0;     break;
    case OP_Ne:    c = c!=0;     break;
    case OP_Lt:    c = c<0;      break;
    case OP_Le:    c = c<=0;     break;
    case OP_Gt:    c = c>0;      break;
    default:       c = c>=0;     break;
  }
  POPSTACK;
  POPSTACK;
  if( c ) pc = pOp->p2-1;
  break;
}

/* Opcode: Like P1 P2 *
**
** Pop the top two elements from the stack.  The top-most is a
** "like" pattern -- the right operand of the SQL "LIKE" operator.
** The lower element is the string to compare against the like
** pattern.  Jump to P2 if the two compare, and fall through without
** jumping if they do not.  The '%' in the top-most element matches
** any sequence of zero or more characters in the lower element.  The
** '_' character in the topmost matches any single character of the
** lower element.  Case is ignored for this comparison.
**
** If P1 is not zero, the sense of the test is inverted and we
** have a "NOT LIKE" operator.  The jump is made if the two values
** are different.
*/
case OP_Like: {
  int tos = p->tos;
  int nos = tos - 1;
  int c;
  VERIFY( if( nos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) || Stringify(p, nos) ) goto no_mem;
  c = sqliteLikeCompare(zStack[tos], zStack[nos]);
  POPSTACK;
  POPSTACK;
  if( pOp->p1 ) c = !c;
  if( c ) pc = pOp->p2-1;
  break;
}

/* Opcode: Glob P1 P2 *
**
** Pop the top two elements from the stack.  The top-most is a
** "glob" pattern.  The lower element is the string to compare 
** against the glob pattern.
**
** Jump to P2 if the two compare, and fall through without
** jumping if they do not.  The '*' in the top-most element matches
** any sequence of zero or more characters in the lower element.  The
** '?' character in the topmost matches any single character of the
** lower element.  [...] matches a range of characters.  [^...]
** matches any character not in the range.  Case is significant
** for globs.
**
** If P1 is not zero, the sense of the test is inverted and we
** have a "NOT GLOB" operator.  The jump is made if the two values
** are different.
*/
case OP_Glob: {
  int tos = p->tos;
  int nos = tos - 1;
  int c;
  VERIFY( if( nos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) || Stringify(p, nos) ) goto no_mem;
  c = sqliteGlobCompare(zStack[tos], zStack[nos]);
  POPSTACK;
  POPSTACK;
  if( pOp->p1 ) c = !c;
  if( c ) pc = pOp->p2-1;
  break;
}

/* Opcode: And * * *
**
** Pop two values off the stack.  Take the logical AND of the
** two values and push the resulting boolean value back onto the
** stack. 
*/
/* Opcode: Or * * *
**
** Pop two values off the stack.  Take the logical OR of the
** two values and push the resulting boolean value back onto the
** stack. 
*/
case OP_And:
case OP_Or: {
  int tos = p->tos;
  int nos = tos - 1;
  int c;
  VERIFY( if( nos<0 ) goto not_enough_stack; )
  Integerify(p, tos);
  Integerify(p, nos);
  if( pOp->opcode==OP_And ){
    c = aStack[tos].i && aStack[nos].i;
  }else{
    c = aStack[tos].i || aStack[nos].i;
  }
  POPSTACK;
  Release(p, nos);     
  aStack[nos].i = c;
  aStack[nos].flags = STK_Int;
  break;
}

/* Opcode: Negative * * *
**
** Treat the top of the stack as a numeric quantity.  Replace it
** with its additive inverse.
*/
case OP_Negative: {
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( aStack[tos].flags & STK_Real ){
    Release(p, tos);
    aStack[tos].r = -aStack[tos].r;
    aStack[tos].flags = STK_Real;
  }else if( aStack[tos].flags & STK_Int ){
    Release(p, tos);
    aStack[tos].i = -aStack[tos].i;
    aStack[tos].flags = STK_Int;
  }else{
    Realify(p, tos);
    Release(p, tos);
    aStack[tos].r = -aStack[tos].r;
    aStack[tos].flags = STK_Real;
  }
  break;
}

/* Opcode: Not * * *
**
** Interpret the top of the stack as a boolean value.  Replace it
** with its complement.
*/
case OP_Not: {
  int tos = p->tos;
  VERIFY( if( p->tos<0 ) goto not_enough_stack; )
  Integerify(p, tos);
  Release(p, tos);
  aStack[tos].i = !aStack[tos].i;
  aStack[tos].flags = STK_Int;
  break;
}

/* Opcode: Noop * * *
**
** Do nothing.  This instruction is often useful as a jump
** destination.
*/
case OP_Noop: {
  break;
}

/* Opcode: If * P2 *
**
** Pop a single boolean from the stack.  If the boolean popped is
** true, then jump to p2.  Otherwise continue to the next instruction.
** An integer is false if zero and true otherwise.  A string is
** false if it has zero length and true otherwise.
*/
case OP_If: {
  int c;
  VERIFY( if( p->tos<0 ) goto not_enough_stack; )
  Integerify(p, p->tos);
  c = aStack[p->tos].i;
  POPSTACK;
  if( c ) pc = pOp->p2-1;
  break;
}

/* Opcode: IsNull * P2 *
**
** Pop a single value from the stack.  If the value popped is NULL
** then jump to p2.  Otherwise continue to the next 
** instruction.
*/
case OP_IsNull: {
  int c;
  VERIFY( if( p->tos<0 ) goto not_enough_stack; )
  c = (aStack[p->tos].flags & STK_Null)!=0;
  POPSTACK;
  if( c ) pc = pOp->p2-1;
  break;
}

/* Opcode: NotNull * P2 *
**
** Pop a single value from the stack.  If the value popped is not an
** empty string, then jump to p2.  Otherwise continue to the next 
** instruction.
*/
case OP_NotNull: {
  int c;
  VERIFY( if( p->tos<0 ) goto not_enough_stack; )
  c = (aStack[p->tos].flags & STK_Null)==0;
  POPSTACK;
  if( c ) pc = pOp->p2-1;
  break;
}

/* Opcode: MakeRecord P1 * *
**
** Convert the top P1 entries of the stack into a single entry
** suitable for use as a data record in a database table.  To do this
** all entries (except NULLs) are converted to strings and 
** concatenated.  The null-terminators are preserved by the concatation
** and serve as a boundry marker between columns.  The lowest entry
** on the stack is the first in the concatenation and the top of
** the stack is the last.  After all columns are concatenated, an
** index header is added.  The index header consists of P1 integers
** which hold the offset of the beginning of each column data from the
** beginning of the completed record including the header.  Header
** entries for NULL fields point to where the first byte of the column
** would have been stored if the column had held any bytes.
*/
case OP_MakeRecord: {
  char *zNewRecord;
  int nByte;
  int nField;
  int i, j;
  int addr;

  nField = pOp->p1;
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      if( Stringify(p, i) ) goto no_mem;
      nByte += aStack[i].n;
    }
  }
  nByte += sizeof(int)*nField;
  zNewRecord = sqliteMalloc( nByte );
  if( zNewRecord==0 ) goto no_mem;
  j = 0;
  addr = sizeof(int)*nField;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){




      addr += aStack[i].n;
    }
    memcpy(&zNewRecord[j], (char*)&addr, sizeof(int));
    j += sizeof(int);
  }
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      memcpy(&zNewRecord[j], zStack[i], aStack[i].n);
      j += aStack[i].n;
    }
  }
  PopStack(p, nField);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str | STK_Dyn;
  zStack[p->tos] = zNewRecord;
  break;
}

/* Opcode: MakeKey P1 P2 *
**
** Convert the top P1 entries of the stack into a single entry suitable
** for use as the key in an index or a sort.  The top P1 records are
** concatenated with a tab character (ASCII 0x09) used as a record
** separator.  The entire concatenation is null-terminated.  The
** lowest entry in the stack is the first field and the top of the
** stack becomes the last.
**
** If P2 is not zero, then the original entries remain on the stack
** and the new key is pushed on top.  If P2 is zero, the original
** data is popped off the stack first then the new key is pushed
** back in its place.
**
** See also: MakeIdxKey, SortMakeKey
*/
case OP_MakeKey: {
  char *zNewKey;
  int nByte;
  int nField;
  int i, j;

  nField = pOp->p1;
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( aStack[i].flags & STK_Null ){
      nByte++;
    }else{
      if( Stringify(p, i) ) goto no_mem;
      nByte += aStack[i].n;
    }
  }
  zNewKey = sqliteMalloc( nByte );
  if( zNewKey==0 ) goto no_mem;
  j = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
      j += aStack[i].n-1;
    }
    if( i<p->tos ) zNewKey[j++] = '\t';
  }
  zNewKey[j] = 0;
  if( pOp->p2==0 ) PopStack(p, nField);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  zStack[p->tos] = zNewKey;
  break;
}

/* Opcode: MakeIdxKey P1 * *
**
** Convert the top P1 entries of the stack into a single entry suitable
** for use as the key in an index.  In addition, take one additional integer
** off of the stack, treat that integer as a four-byte record number, and
** append the four bytes to the key.  Thus a total of P1+1 entries are
** popped from the stack for this instruction and a single entry is pushed
** back.  The first P1 entries that are popped are strings and the last
** entry (the lowest on the stack) is an integer record number.
**

** The converstion of the first P1 string entries occurs just like in
** MakeKey.  Each entry is separated from the others by a tab (ASCII 0x09).
** The entire concatenation is null-terminated.  The lowest entry
** in the stack is the first field and the top of the stack becomes the
** last.
**
** See also:  MakeKey, SortMakeKey
*/
case OP_MakeIdxKey: {
  char *zNewKey;
  int nByte;
  int nField;
  int i, j;

  nField = pOp->p1;
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = sizeof(int);
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( aStack[i].flags & STK_Null ){
      nByte++;
    }else{
      if( Stringify(p, i) ) goto no_mem;
      nByte += aStack[i].n;
    }
  }
  zNewKey = sqliteMalloc( nByte );
  if( zNewKey==0 ) goto no_mem;
  j = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
      j += aStack[i].n-1;
    }
    if( i<p->tos ) zNewKey[j++] = '\t';
  }
  zNewKey[j++] = 0;
  Integerify(p, p->tos-nField);
  memcpy(&zNewKey[j], aStack[p->tos-nField].i, sizeof(int));
  PopStack(p, nField+1);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  zStack[p->tos] = zNewKey;
  break;
}

/* Opcode: Transaction * * *
**
** Begin a transaction.  The transaction ends when a Commit or Rollback
** opcode is encountered or whenever there is an execution error that causes
** a script to abort.  
**
** A transaction must be started before any changes can be made to the
** database.
*/
case OP_Transaction: {
  rc = sqliteBtreeBeginTrans(pBe);
  break;
}

/* Opcode: Commit * * *
**
** Cause all modifications to the database that have been made since the


** last Transaction to actually take effect.  No additional modifications
** are allowed until another transaction is started.
*/
case OP_Commit: {
  rc = sqliteBtreeCommit(pBe);
  if( rc==SQLITE_OK ){
    sqliteCommitInternalChanges(db);
  }else{
    sqliteRollbackInternalChanges(db);
  }
  break;
}

/* Opcode: Rollback * * *
**
** Cause all modifications to the database that have been made since the
** last Transaction to be undone. The database is restored to its state
** before the Transaction opcode was executed.  No additional modifications
** are allowed until another transaction is started.
*/
case OP_Rollback: {
  rc = sqliteBtreeRollback(pBe);
  sqliteRollbackInternalChanges(db);
  break;
}

/* Opcode: Open P1 P2 P3
**
** Open a new cursor for the database table whose root page is

** P2 in the main database file.  Give the new cursor an identifier
** of P1.  The P1 values need not be contiguous but all P1 values
** should be small integers.  It is an error for P1 to be negative.
**
** The P3 value is the name of the table or index being opened.
** The P3 value is not actually used by this opcode and may be
** omitted.  But the code generator usually inserts the index or
** table name into P3 to make the code easier to read.
*/
case OP_Open: {
  int busy = 0;
  int i = pOp->p1;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i>=p->nCursor ){
    int j;
    p->aCsr = sqliteRealloc( p->aCsr, (i+1)*sizeof(Cursor) );
    if( p->aCsr==0 ){ p->nCursor = 0; goto no_mem; }
    for(j=p->nCursor; j<=i; j++) p->aCsr[j].pCursor = 0;
    p->nCursor = i+1;
  }else if( p->aCsr[i].pCursor ){
    sqliteBtreeCloseCursor(p->aCsr[i].pCursor);
  }
  memset(&p->aCsr[i], 0, sizeof(Cursor));
  do {
    rc = sqliteBtreeOpenCursor(pBe, pOp->p2, &p->aCsr[i].pCursor);
    switch( rc ){
      case SQLITE_BUSY: {
        if( xBusy==0 || (*xBusy)(pBusyArg, pOp->p3, ++busy)==0 ){
          sqliteSetString(pzErrMsg, sqliteErrStr(rc), 0);
          busy = 0;
        }
        break;
      }
      case SQLITE_OK: {
        busy = 0;
        break;
      }
      default: {
        goto abort_due_to_error;
      }
    }
  }while( busy );
  break;
}

/* Opcode: OpenTemp P1 * *
**
** Open a new cursor that points to a table in a temporary database
** file.  The temporary file is opened read/write event if the main
** database is read-only.  The temporary file is deleted when the

** cursor is closed.
*/

case OP_OpenTemp: {
  int busy = 0;
  int i = pOp->p1;
  Cursor *pCx;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i>=p->nCursor ){
    int j;
    p->aCsr = sqliteRealloc( p->aCsr, (i+1)*sizeof(Cursor) );
    if( p->aCsr==0 ){ p->nCursor = 0; goto no_mem; }
    for(j=p->nCursor; j<=i; j++) p->aCsr[j].pCursor = 0;
    p->nCursor = i+1;
  }else if( p->aCsr[i].pCursor ){
    sqliteBtreeCloseCursor(p->aCsr[i].pCursor);
  }


  pCx = &p->aCsr[i];




  memset(pCx, 0, sizeof(*pCx));




  rc = sqliteBtreeOpen(0, 0, 100, &pCx->pBt);



  if( rc==SQLITE_OK ){
    rc = sqliteBtreeOpenCursor(pCx->pBt, 2, &pCx->pCursor);


  }



  if( rc==SQLITE_OK ){
    rc = sqliteBtreeBeginTrans(pCx->pBt);

  }




  break;
}

/* Opcode: Close P1 * *
**
** Close a cursor previously opened as P1.  If P1 is not
** currently open, this instruction is a no-op.
*/
case OP_Close: {
  int i = pOp->p1;
  if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
    Cursor *pCx = &p->aCsr[i];
    sqliteBtreeCloseCursor(pCx->pCursor);
    pCx->pCursor = 0;
    if( pCx->zKey ){
      sqliteFree(pCx->zKey);
      pCx->zKey = 0;
    }
    if( pCx->pBt ){
      sqliteBtreeClose(pCx->pBt);
      pCx->pBt = 0;
    }
  }
  break;
}

/* Opcode: MoveTo P1 * *
**
** Pop the top of the stack and use its value as a key.  Reposition
** cursor P1 so that it points to an entry with a matching key.  If
** the table contains no record with a matching key, then the cursor
** is left pointing at a nearby record.
*/
case OP_MoveTo: {
  int i = pOp->p1;
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
    int res;
    if( aStack[tos].flags & STK_Int ){
      sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(int), 
                     (char*)&aStack[tos].i, &res);
      p->aCsr[i].lastRecno = aStack[tos].i;
      p->aCsr[i].recnoIsValid = 1;
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      pBex->Fetch(p->aCsr[i].pCursor, aStack[tos].n, 
                     zStack[tos], &res);
      p->aCsr[i].recnoIsValid = 0;
    }
    p->nFetch++;
  }
  POPSTACK;
  break;
}

/* Opcode: Fcnt * * *
**
** Push an integer onto the stack which is the total number of
** OP_Fetch opcodes that have been executed by this virtual machine.
**
** This instruction is used to implement the special fcnt() function
** in the SQL dialect that SQLite understands.  fcnt() is used for
** testing purposes.
*/
case OP_Fcnt: {
  int i = ++p->tos;
  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  aStack[i].i = p->nFetch;
  aStack[i].flags = STK_Int;
  break;
}

/* Opcode: Distinct P1 P2 *
**
** Use the top of the stack as a key.  If a record with that key
** does not exist in file P1, then jump to P2.  If the record
** does already exist, then fall thru.  The record is not retrieved.
** The key is not popped from the stack.
**
** This operation is similar to NotFound except that this operation
** does not pop the key from the stack.
*/
/* Opcode: Found P1 P2 *
**
** Use the top of the stack as a key.  If a record with that key
** does exist in file P1, then jump to P2.  If the record
** does not exist, then fall thru.  The record is not retrieved.
** The key is popped from the stack.
*/
/* Opcode: NotFound P1 P2 *
**
** Use the top of the stack as a key.  If a record with that key
** does not exist in file P1, then jump to P2.  If the record
** does exist, then fall thru.  The record is not retrieved.
** The key is popped from the stack.
**
** The difference between this operation and Distinct is that
** Distinct does not pop the key from the stack.
*/
case OP_Distinct:
case OP_NotFound:
case OP_Found: {
  int i = pOp->p1;
  int tos = p->tos;
  int alreadyExists = 0;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor ){
    int res, rx;
    if( aStack[tos].flags & STK_Int ){
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(int), 
                                    (char*)&aStack[tos].i, &res);
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor,aStack[tos].n, 
                                     zStack[tos], &res);
    }
    alreadyExists = rx==SQLITE_OK && res==0;
  }
  if( pOp->opcode==OP_Found ){
    if( alreadyExists ) pc = pOp->p2 - 1;
  }else{
    if( !alreadyExists ) pc = pOp->p2 - 1;
  }
  if( pOp->opcode!=OP_Distinct ){
    POPSTACK;
  }
  break;
}

/* Opcode: NewRecno P1 * *
**
** Get a new integer record number used as the key to a table.
** The record number is not previous used by the database file
** associated with cursor P1.  The new record number pushed 
** onto the stack.
*/
case OP_NewRecno: {
  int i = pOp->p1;
  int v;
  if( VERIFY( i<0 || i>=p->nCursor || ) p->aCsr[i].pCursor==0 ){
    v = 0;
  }else{
    int res, rx, cnt;
    cnt = 0;
    do{
      v = sqliteRandomInteger();
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(v), &v, &res);
      cnt++;
    }while( cnt<10 && rx==SQLITE_OK && res==0 );
  }
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].i = v;
  aStack[p->tos].flags = STK_Int;
  break;
}

/* Opcode: Put P1 * *
**
** Write an entry into the database file P1.  A new entry is
** created if it doesn't already exist, or the data for an existing
** entry is overwritten.  The data is the value on the top of the
** stack.  The key is the next value down on the stack.  The stack
** is popped twice by this instruction.
*/
case OP_Put: {
  int tos = p->tos;
  int nos = p->tos-1;
  int i = pOp->p1;
  VERIFY( if( nos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor!=0 ){
    char *zKey;
    int nKey;
    if( (aStack[nos].flags & STK_Int)==0 ){
      if( Stringify(p, nos) ) goto no_mem;
      nKey = aStack[nos].n;
      zKey = zStack[nos];
    }else{
      nKey = sizeof(int);
      zKey = (char*)&aStack[nos].i;
    }
    rc = sqliteBtreeInsert(p->aCsr[i].pCursor, nKey, zKey,
                        aStack[tos].n, zStack[tos]);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
  }
  POPSTACK;
  POPSTACK;
  break;
}

/* Opcode: Delete P1 * *
**
** The top of the stack is a key.  Remove this key and its data
** from database file P1.  Then pop the stack to discard the key.
*/
case OP_Delete: {
  int tos = p->tos;
  int i = pOp->p1;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor!=0 ){
    char *zKey;
    int nKey;
    if( aStack[tos].flags & STK_Int ){
      nKey = sizeof(int);
      zKey = (char*)&aStack[tos].i;
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      nKey = aStack[tos].n;
      zKey = zStack[tos];
    }
    rc = sqliteBtreeDelete(p->aCsr[i].pCursor, nKey, zKey);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
  }
  POPSTACK;
  break;
}

/* Opcode: KeyAsData P1 P2 *
**
** Turn the key-as-data mode for cursor P1 either on (if P2==1) or
** off (if P2==0).  In key-as-data mode, the OP_Field opcode pulls
** data off of the key rather than the data.  This is useful for
** processing compound selects.
*/
case OP_KeyAsData: {
  int i = pOp->p1;
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor!=0 ){
    p->aCsr[i].keyAsData = pOp->p2;
  }
  break;
}

/* Opcode: Column P1 P2 *
**
** Interpret the data in the most recent fetch from cursor P1
** is a structure built using the MakeRecord instruction.
** Push onto the stack the value of the P2-th field of that
** structure.
** 
** The value pushed is a pointer to the data stored in the cursor.
** The value will go away the next time the cursor is modified in
** any way.  Make a copy of the string (using
** "Concat 1 0 0") if it needs to persist longer than that.
**
** If the KeyAsData opcode has previously executed on this cursor,
** then the field might be extracted from the key rather than the
** data.





*/
case OP_Column: {
  int *pAddr;
  int amt, offset, nCol, payloadSize;
  int aHdr[10];
  const int mxHdr = sizeof(aHdr)/sizeof(aHdr[0]);
  int i = pOp->p1;
  int p2 = pOp->p2;
  int tos = ++p->tos;
  BtCursor *pCrsr;
  char *z;

  VERIFY( if( NeedStack(p, tos) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int (*xSize)(BtCursor*, int*);
    int (*xRead)(BtCursor*, int, int, void*);

    /* Use different access functions depending on whether the information
    ** is coming from the key or the data of the record.
    */
    if( p->aCsr[i].keyAsData ){
      xSize = sqliteBtreeKeySize;
      xRead = sqliteBtreeKey;
    }else{
      xSize = sqliteBtreeDataSize;
      xRead = sqliteBtreeData;
    }

    /* 
    ** The code is complicated by efforts to minimize the number
    ** of invocations of xRead() since that call can be expensive.
    ** For the common case where P2 is small, xRead() is invoked
    ** twice.  For larger values of P2, it has to be called
    ** three times.
    */
    (*xSize)(pCrsr, &payloadSize);
    if( payloadSize < sizeof(int)*(p2+1) ){
      rc = SQLITE_CORRUPT;

      goto abort_due_to_error;
    }

    if( p2+1<mxHdr ){
      (*xRead)(pCrsr, 0, sizeof(aHdr[0])*(p2+2), aHdr);
      nCol = aHdr[0];
      offset = aHdr[p2];
      if( p2 == nCol-1 ){
        amt = payloadSize - offset;
      }else{
        amt = aHdr[p2+1] - offset;
      }

    }else{
      sqliteBtreeData(pCrsr, 0, sizeof(int), &nCol);
      nCol /= sizeof(int);
      if( p2 == nCol-1 ){
        (*xRead)(pCrsr, sizeof(int)*p2, sizeof(int), &offset);
        amt = payloadSize - offset;
      }else{
        (*xRead)(pCrsr, sizeof(int)*p2, sizeof(int)*2, aHdr);
        offset = aHdr[0];
        amt = aHdr[1] - offset;
      }




    }
    if( payloadSize < nCol || amt<0 || offset<0 ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
    }
    if( amt==0 ){
      aStack[tos].flags = STK_Null;
    }else{
      z = sqliteMalloc( amt );
      if( z==0 ) goto no_mem;
      (*xRead)(pCrsr, offset, amt, z);
      aStack[tos].flags = STK_Str | STK_Dyn;
      zStack[tos] = z;
      aStack[tos].n = amt;

    }
  }
  break;
}

/* Opcode: Recno P1 * *
**
** Push onto the stack an integer which is the first 4 bytes of the
** the key to the current entry in a sequential scan of the database
** file P1.  The sequential scan should have been started using the 
** Next opcode.
*/
case OP_Recno: {
  int i = pOp->p1;
  int tos = ++p->tos;
  BtCursor *pCrsr;

  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int v;
    if( p->aCsr[i].recnoIsValid ){
      v = p->aCsr[i].lastRecno;
    }else{
      sqliteBtreeKey(pCrsr, 0, sizeof(int), &v);
    }
    aStack[tos].i = v;
    aStack[tos].flags = STK_Int;
  }
  break;
}

/* Opcode: FullKey P1 * *
**
** Push a string onto the stack which is the full text key associated
** with the last Next operation on file P1.  Compare this with the
** Key operator which pushs an integer key.
*/
case OP_FullKey: {
  int i = pOp->p1;
  int tos = ++p->tos;
  BtCursor *pCrsr;

  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  VERIFY( if( !p->aCsr[i].keyAsData ) goto bad_instruction; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int amt;
    char *z;

    sqliteBtreeKeySize(pCrsr, &amt);
    if( amt<=0 ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
    }
    z = sqliteMalloc( amt );
    sqliteBtreeKey(pCrsr, 0, amt, z);
    zStack[tos] = z;
    aStack[tos].flags = STK_Str | STK_Dyn;
    aStack[tos].n = amt;
  }
  break;
}

/* Opcode: Rewind P1 * *
**
** The next use of the Recno or Column or Next instruction for P1 
** will refer to the first entry in the database file.
*/
case OP_Rewind: {
  int i = pOp->p1;
  BtCursor *pCrsr;

  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int res;
    sqliteBtreeFirst(pCrsr, &res);
    p->aCsr[i].atFirst = res==0;
  }
  break;
}

/* Opcode: Next P1 P2 *
**
** Advance cursor P1 so that it points to the next key/data pair in its
** table.  Or, if there are no more key/data pairs, jump to location P2.
*/
case OP_Next: {
  int i = pOp->p1;
  BtCursor *pCrsr;

  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    if( !p->aCsr[i].atFirst ){
      int res;
      sqliteBtreeNext(pCrsr, &res);
      if( res ){
        pc = pOp->p2 - 1;
      }else{
        p->nFetch++;
      }
    }
    p->aCsr[i].atFirst = 0;
    p->aCsr[i].recnoIsValid = 0;
  }
  break;
}

/* Opcode: BeginIdx P1 * *
**
** Begin searching an index for records with the key found on the
** top of the stack.  The key on the top of the stack should be built
** using the MakeKey opcode.  Subsequent calls to NextIdx will push
** record numbers onto the stack until all records with the same key
** have been returned.
**
** Note that the key for this opcode should be built using MakeKey
** but the key used for PutIdx and DeleteIdx should be built using
** MakeIdxKey.  The difference is that MakeIdxKey adds a 4-bytes
** record number to the end of the key in order to specify a particular
** entry in the index.  MakeKey specifies zero or more entries in the
** index that all have common values.
*/
case OP_BeginIdx: {
  int i = pOp->p1;
  int tos = p->tos;
  int res, rx;
  Cursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( i>=0 && i<p->nCursor && (pCrsr = &p->aCsr[i])->pCursor!=0 ){
    if( Stringify(p, tos) ) goto no_mem;
    pCrsr->nKey = aStack[tos].n;
    pCrsr->zKey = sqliteMalloc( 2*(pCrsr->nKey + 1) );
    if( pCrsr->zKey==0 ) goto no_mem;
    pCrsr->zBuf = &pCrsr->zKey[pCrsr->nKey+1];
    strncpy(pCrsr->zKey, zStack[tos], aStack[tos].n);
    pCrsr->zKey[aStack[tos].n] = 0;
    rx = sqliteBtreeMoveTo(pCrsr->pCursor, aStack[tos].n, zStack[tos], &res);
    pCrsr->atFirst = rx==SQLITE_OK && res>0;
    pCrsr->recnoIsValid = 0;
  }
  POPSTACK;
  break;
}

/* Opcode: NextIdx P1 P2 *
**
** The P1 cursor points to an SQL index for which a BeginIdx operation
** has been issued.  This operation retrieves the next record number and
** pushes that record number onto the stack.  Or, if there are no more
** record numbers for the given key, this opcode pushes nothing onto the
** stack but instead jumps to instruction P2.
*/
case OP_NextIdx: {
  int i = pOp->p1;
  int tos = ++p->tos;
  Cursor *pCrsr;
  BtCursr *pCur;
  int rx, res, size;

  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  zStack[tos] = 0;
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = &p->aCsr[i])->pCursor)!=0 ){
    pCur = pCrsr->pCursor;
    rx = sqliteBtreeNext(pCur, &res);
    if( rx!=SQLITE_OK ) goto abort_due_to_error;
    sqliteBtreeKeySzie(pCur, &size);
    if( res>0 || size!=pCrsr->nKey+sizeof(int) ||
      sqliteBtreeKey(pCur, 0, pCrsr->nKey, pCrsr->zBuf)!=pCrsr->nKey ||
      strncmp(pCrsr->zKey, pCrsr->zBuf, pCrsr->nKey)!=0
    ){
      pc = pOp->p2 - 1;
      POPSTACK;
    }else{
      int recno;
      sqliteBtreeKey(pCur, pCrsr->nKey, sizeof(int), &recno);
      p->aCsr[i].lastRecno = aStack[tos].i = recno;
      p->aCsr[i].recnoIsValid = 1;
      aStack[tos].flags = STK_Int;



    }
  }
  break;
}

/* Opcode: PutIdx P1 * *
**
** The top of the stack hold an SQL index key made using the
** MakeIdxKey instruction.  This opcode writes that key into the

** index P1.  Data for the entry is nil.

*/
case OP_PutIdx: {
  int i = pOp->p1;
  int tos = p->tos;

  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){


    sqliteBtreePut(pCrsr, aStack[tos].n, zStack[tos], 0, "");
  }

  POPSTACK;
  break;
}

/* Opcode: DeleteIdx P1 * *
**
** The top of the stack is an index key built using the MakeIdxKey opcode.
** This opcode removes that entry from the index.


*/
case OP_DeleteIdx: {
  int i = pOp->p1;
  int tos = p->tos;

  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int rx, res;

    rx = sqliteBtreeMoveTo(pCrsr, aStack[tos].n, zStack[tos], &res);
    if( rx==SQLITE_OK && res==0 ){
      sqliteBtreeDelete(pCrsr);
    }
  }
  POPSTACK;

  break;
}


/* Opcode: Destroy P1 * *
**


** Delete an entire database table or index whose root page in the database
** file is given by P1.
*/
case OP_Destroy: {
  sqliteBtreeDropTable(pBe, pOp->p1);
  break;
}

/* Opcode: Reorganize P1 * *
**
** Compress, optimize, and tidy up table or index whose root page in the
** database file is P1.
*/
case OP_Reorganize: {

  /* This is currently a no-op */
  break;
}

/* Opcode: ListOpen P1 * *
**
** Open a "List" structure used for temporary storage of integer 
** table keys.  P1
** will server as a handle to this list for future
** interactions.  If another list with the P1 handle is
** already opened, the prior list is closed and a new one opened
** in its place.
*/
case OP_ListOpen: {
  int i = pOp->p1;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i>=p->nList ){
    int j;
    p->apList = sqliteRealloc( p->apList, (i+1)*sizeof(Keylist*) );
    if( p->apList==0 ){ p->nList = 0; goto no_mem; }
    for(j=p->nList; j<=i; j++) p->apList[j] = 0;
    p->nList = i+1;
  }else if( p->apList[i] ){
    KeylistFree(p->apList[i]);
    p->apList[i] = 0;
  }
  break;
}

/* Opcode: ListWrite P1 * *
**
** Write the integer on the top of the stack
** into the temporary storage list P1.
*/
case OP_ListWrite: {
  int i = pOp->p1;
  Keylist *pKeylist;
  VERIFY( if( i<0 || i>=p->nList ) goto bad_instruction; )
  VERIFY( if( p->tos<0 ) goto not_enough_stack; )
  pKeylist = p->apList[i];
  if( pKeylist==0 || pKeylist->nUsed>=pKeylist->nKey ){
    pKeylist = sqliteMalloc( sizeof(Keylist)+999*sizeof(int) );
    if( pKeylist==0 ) goto no_mem;
    pKeylist->nKey = 1000;
    pKeylist->nRead = 0;
    pKeylist->nUsed = 0;
    pKeylist->pNext = p->apList[i];
    p->apList[i] = pKeylist;
  }
  Integerify(p, p->tos);
  pKeylist->aKey[pKeylist->nUsed++] = aStack[p->tos].i;
  POPSTACK;
  break;
}

/* Opcode: ListRewind P1 * *
**
** Rewind the temporary buffer P1 back to the beginning.
*/
case OP_ListRewind: {
  int i = pOp->p1;
  VERIFY( if( i<0 ) goto bad_instruction; )
  /* This is now a no-op */
  break;
}

/* Opcode: ListRead P1 P2 *
**
** Attempt to read an integer from temporary storage buffer P1
** and push it onto the stack.  If the storage buffer is empty, 
** push nothing but instead jump to P2.
*/
case OP_ListRead: {
  int i = pOp->p1;
  Keylist *pKeylist;
  VERIFY(if( i<0 || i>=p->nList ) goto bad_instruction;)
  pKeylist = p->apList[i];
  if( pKeylist!=0 ){
    VERIFY(
      if( pKeylist->nRead<0 
        || pKeylist->nRead>=pKeylist->nUsed
        || pKeylist->nRead>=pKeylist->nKey ) goto bad_instruction;
    )
    p->tos++;
    if( NeedStack(p, p->tos) ) goto no_mem;
    aStack[p->tos].i = pKeylist->aKey[pKeylist->nRead++];
    aStack[p->tos].flags = STK_Int;
    zStack[p->tos] = 0;
    if( pKeylist->nRead>=pKeylist->nUsed ){
      p->apList[i] = pKeylist->pNext;
      sqliteFree(pKeylist);
    }
  }else{
    pc = pOp->p2 - 1;
  }
  break;
}

/* Opcode: ListClose P1 * *
**
** Close the temporary storage buffer and discard its contents.
*/
case OP_ListClose: {
  int i = pOp->p1;
  VERIFY( if( i<0 ) goto bad_instruction; )
  VERIFY( if( i>=p->nList ) goto bad_instruction; )
  KeylistFree(p->apList[i]);
  p->apList[i] = 0;
  break;
}

/* Opcode: SortOpen P1 * *
**
** Create a new sorter with index P1
*/
case OP_SortOpen: {
  int i = pOp->p1;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i>=p->nSort ){
    int j;
    p->apSort = sqliteRealloc( p->apSort, (i+1)*sizeof(Sorter*) );
    if( p->apSort==0 ){ p->nSort = 0; goto no_mem; }
    for(j=p->nSort; j<=i; j++) p->apSort[j] = 0;
    p->nSort = i+1;
  }
  break;
}

/* Opcode: SortPut P1 * *
**
** The TOS is the key and the NOS is the data.  Pop both from the stack
** and put them on the sorter.
*/
case OP_SortPut: {
  int i = pOp->p1;
  int tos = p->tos;
  int nos = tos - 1;
  Sorter *pSorter;
  VERIFY( if( i<0 || i>=p->nSort ) goto bad_instruction; )
  VERIFY( if( tos<1 ) goto not_enough_stack; )
  if( Stringify(p, tos) || Stringify(p, nos) ) goto no_mem;
  pSorter = sqliteMalloc( sizeof(Sorter) );
  if( pSorter==0 ) goto no_mem;
  pSorter->pNext = p->apSort[i];
  p->apSort[i] = pSorter;
  pSorter->nKey = aStack[tos].n;
  pSorter->zKey = zStack[tos];
  pSorter->nData = aStack[nos].n;
  pSorter->pData = zStack[nos];
  aStack[tos].flags = 0;
  aStack[nos].flags = 0;
  zStack[tos] = 0;
  zStack[nos] = 0;
  p->tos -= 2;
  break;
}

/* Opcode: SortMakeRec P1 * *
**
** The top P1 elements are the arguments to a callback.  Form these
** elements into a single data entry that can be stored on a sorter
** using SortPut and later fed to a callback using SortCallback.
*/
case OP_SortMakeRec: {
  char *z;
  char **azArg;
  int nByte;
  int nField;
  int i, j;

  nField = pOp->p1;
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)==0 ){
      if( Stringify(p, i) ) goto no_mem;
      nByte += aStack[i].n;
    }
  }
  nByte += sizeof(char*)*(nField+1);
  azArg = sqliteMalloc( nByte );
  if( azArg==0 ) goto no_mem;
  z = (char*)&azArg[nField+1];
  for(j=0, i=p->tos-nField+1; i<=p->tos; i++, j++){
    if( aStack[i].flags & STK_Null ){
      azArg[j] = 0;
    }else{
      azArg[j] = z;
      strcpy(z, zStack[i]);
      z += aStack[i].n;
    }
  }
  PopStack(p, nField);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  zStack[p->tos] = (char*)azArg;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  break;
}

/* Opcode: SortMakeKey P1 * P3
**
** Convert the top few entries of the stack into a sort key.  The
** number of stack entries consumed is the number of characters in 
** the string P3.  One character from P3 is prepended to each entry.
** The first character of P3 is prepended to the element lowest in
** the stack and the last character of P3 is appended to the top of
** the stack.  All stack entries are separated by a \000 character
** in the result.  The whole key is terminated by two \000 characters
** in a row.
**
** See also the MakeKey opcode.
*/
case OP_SortMakeKey: {
  char *zNewKey;
  int nByte;
  int nField;
  int i, j, k;

  nField = strlen(pOp->p3);
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = 1;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( Stringify(p, i) ) goto no_mem;
    nByte += aStack[i].n+2;
  }
  zNewKey = sqliteMalloc( nByte );
  if( zNewKey==0 ) goto no_mem;
  j = 0;
  k = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    zNewKey[j++] = pOp->p3[k++];
    memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
    j += aStack[i].n-1;
    zNewKey[j++] = 0;
  }
  zNewKey[j] = 0;
  PopStack(p, nField);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  zStack[p->tos] = zNewKey;
  break;
}

/* Opcode: Sort P1 * *
**
** Sort all elements on the given sorter.  The algorithm is a
** mergesort.
*/
case OP_Sort: {
  int j;
  j = pOp->p1;
  VERIFY( if( j<0 ) goto bad_instruction; )
  if( j<p->nSort ){
    int i;
    Sorter *pElem;
    Sorter *apSorter[NSORT];
    for(i=0; i<NSORT; i++){
      apSorter[i] = 0;
    }
    while( p->apSort[j] ){
      pElem = p->apSort[j];
      p->apSort[j] = pElem->pNext;
      pElem->pNext = 0;
      for(i=0; i<NSORT-1; i++){
        if( apSorter[i]==0 ){
          apSorter[i] = pElem;
          break;
        }else{
          pElem = Merge(apSorter[i], pElem);
          apSorter[i] = 0;
        }
      }
      if( i>=NSORT-1 ){
        apSorter[NSORT-1] = Merge(apSorter[NSORT-1],pElem);
      }
    }
    pElem = 0;
    for(i=0; i<NSORT; i++){
      pElem = Merge(apSorter[i], pElem);
    }
    p->apSort[j] = pElem;
  }
  break;
}

/* Opcode: SortNext P1 P2 *
**
** Push the data for the topmost element in the given sorter onto the
** stack, then remove the element from the sorter.
*/
case OP_SortNext: {
  int i = pOp->p1;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( VERIFY( i<p->nSort && ) p->apSort[i]!=0 ){
    Sorter *pSorter = p->apSort[i];
    p->apSort[i] = pSorter->pNext;
    p->tos++;
    VERIFY( NeedStack(p, p->tos); )
    zStack[p->tos] = pSorter->pData;
    aStack[p->tos].n = pSorter->nData;
    aStack[p->tos].flags = STK_Str|STK_Dyn;
    sqliteFree(pSorter->zKey);
    sqliteFree(pSorter);
  }else{
    pc = pOp->p2 - 1;
  }
  break;
}

/* Opcode: SortKey P1 * *
**
** Push the key for the topmost element of the sorter onto the stack.
** But don't change the sorter an any other way.
*/
case OP_SortKey: {
  int i = pOp->p1;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i<p->nSort && p->apSort[i]!=0 ){
    Sorter *pSorter = p->apSort[i];
    p->tos++;
    VERIFY( NeedStack(p, p->tos); )
    sqliteSetString(&zStack[p->tos], pSorter->zKey, 0);
    aStack[p->tos].n = pSorter->nKey;
    aStack[p->tos].flags = STK_Str|STK_Dyn;
  }
  break;
}

/* Opcode: SortCallback P1 P2 *
**
** The top of the stack contains a callback record built using
** the SortMakeRec operation with the same P1 value as this
** instruction.  Pop this record from the stack and invoke the
** callback on it.
*/
case OP_SortCallback: {
  int i = p->tos;
  VERIFY( if( i<0 ) goto not_enough_stack; )
  if( xCallback!=0 ){
    if( xCallback(pArg, pOp->p1, (char**)zStack[i], p->azColName) ){
      rc = SQLITE_ABORT;
    }
  }
  POPSTACK;
  break;
}

/* Opcode: SortClose P1 * *
**
** Close the given sorter and remove all its elements.
*/
case OP_SortClose: {
  Sorter *pSorter;
  int i = pOp->p1;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i<p->nSort ){
     while( (pSorter = p->apSort[i])!=0 ){
       p->apSort[i] = pSorter->pNext;
       sqliteFree(pSorter->zKey);
       sqliteFree(pSorter->pData);
       sqliteFree(pSorter);
     }
  }
  break;
}

/* Opcode: FileOpen * * P3
**
** Open the file named by P3 for reading using the FileRead opcode.
** If P3 is "stdin" then open standard input for reading.
*/
case OP_FileOpen: {
  VERIFY( if( pOp->p3==0 ) goto bad_instruction; )
  if( p->pFile ){
    if( p->pFile!=stdin ) fclose(p->pFile);
    p->pFile = 0;
  }
  if( sqliteStrICmp(pOp->p3,"stdin")==0 ){
    p->pFile = stdin;
  }else{
    p->pFile = fopen(pOp->p3, "r");
  }
  if( p->pFile==0 ){
    sqliteSetString(pzErrMsg,"unable to open file: ", pOp->p3, 0);
    rc = SQLITE_ERROR;
    goto cleanup;
  }
  break;
}

/* Opcode: FileClose * * *
**
** Close a file previously opened using FileOpen.  This is a no-op
** if there is no prior FileOpen call.
*/
case OP_FileClose: {
  if( p->pFile ){
    if( p->pFile!=stdin ) fclose(p->pFile);
    p->pFile = 0;
  }
  if( p->azField ){
    sqliteFree(p->azField);
    p->azField = 0;
  }
  p->nField = 0;
  if( p->zLine ){
    sqliteFree(p->zLine);
    p->zLine = 0;
  }
  p->nLineAlloc = 0;
  break;
}

/* Opcode: FileRead P1 P2 P3
**
** Read a single line of input from the open file (the file opened using
** FileOpen).  If we reach end-of-file, jump immediately to P2.  If
** we are able to get another line, split the line apart using P3 as
** a delimiter.  There should be P1 fields.  If the input line contains
** more than P1 fields, ignore the excess.  If the input line contains
** fewer than P1 fields, assume the remaining fields contain an
** empty string.
*/
case OP_FileRead: {
  int n, eol, nField, i, c, nDelim;
  char *zDelim, *z;
  if( p->pFile==0 ) goto fileread_jump;
  nField = pOp->p1;
  if( nField<=0 ) goto fileread_jump;
  if( nField!=p->nField || p->azField==0 ){
    p->azField = sqliteRealloc(p->azField, sizeof(char*)*nField+1);
    if( p->azField==0 ){
      p->nField = 0;
      goto fileread_jump;
    }
    p->nField = nField;
  }
  n = 0;
  eol = 0;
  while( eol==0 ){
    if( p->zLine==0 || n+200>p->nLineAlloc ){
      p->nLineAlloc = p->nLineAlloc*2 + 300;
      p->zLine = sqliteRealloc(p->zLine, p->nLineAlloc);
      if( p->zLine==0 ){
        p->nLineAlloc = 0;
        goto fileread_jump;
      }
    }
    if( fgets(&p->zLine[n], p->nLineAlloc-n, p->pFile)==0 ){
      eol = 1;
      p->zLine[n] = 0;
    }else{
      while( p->zLine[n] ){ n++; }
      if( n>0 && p->zLine[n-1]=='\n' ){
        n--;
        p->zLine[n] = 0;
        eol = 1;
      }
    }
  }
  if( n==0 ) goto fileread_jump;
  z = p->zLine;
  if( z[0]=='\\' && z[1]=='.' && z[2]==0 ){
    goto fileread_jump;
  }
  zDelim = pOp->p3;
  if( zDelim==0 ) zDelim = "\t";
  c = zDelim[0];
  nDelim = strlen(zDelim);
  p->azField[0] = z;
  for(i=1; *z!=0 && i<=nField; i++){
    int from, to;
    from = to = 0;
    while( z[from] ){
      if( z[from]=='\\' && z[from+1]!=0 ){
        z[to++] = z[from+1];
        from += 2;
        continue;
      }
      if( z[from]==c && strncmp(&z[from],zDelim,nDelim)==0 ) break;
      z[to++] = z[from++];
    }
    if( z[from] ){
      z[to] = 0;
      z += from + nDelim;
      if( i<nField ) p->azField[i] = z;
    }else{
      z[to] = 0;
      z = "";
    }
  }
  while( i<nField ){
    p->azField[i++] = "";
  }
  break;

  /* If we reach end-of-file, or if anything goes wrong, jump here.
  ** This code will cause a jump to P2 */
fileread_jump:
  pc = pOp->p2 - 1;
  break;
}

/* Opcode: FileField P1 * *
**
** Push onto the stack the P1-th field of the most recently read line
** from the input file.
*/
case OP_FileField: {
  int i = pOp->p1;
  char *z;
  VERIFY( if( NeedStack(p, p->tos+1) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nField && ) p->azField ){
    z = p->azField[i];
  }else{
    z = 0;
  }
  if( z==0 ) z = "";
  p->tos++;
  aStack[p->tos].n = strlen(z) + 1;
  zStack[p->tos] = z;
  aStack[p->tos].flags = STK_Str;
  break;
}

/* Opcode: MemStore P1 * *
**
** Pop a single value of the stack and store that value into memory
** location P1.  P1 should be a small integer since space is allocated
** for all memory locations between 0 and P1 inclusive.
*/
case OP_MemStore: {
  int i = pOp->p1;
  int tos = p->tos;
  Mem *pMem;
  char *zOld;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( i>=p->nMem ){
    int nOld = p->nMem;
    p->nMem = i + 5;
    p->aMem = sqliteRealloc(p->aMem, p->nMem*sizeof(p->aMem[0]));
    if( p->aMem==0 ) goto no_mem;
    if( nOld<p->nMem ){
      memset(&p->aMem[nOld], 0, sizeof(p->aMem[0])*(p->nMem-nOld));
    }
  }
  pMem = &p->aMem[i];
  if( pMem->s.flags & STK_Dyn ){
    zOld = pMem->z;
  }else{
    zOld = 0;
  }
  pMem->s = aStack[tos];
  if( pMem->s.flags & STK_Str ){
    pMem->z = sqliteStrNDup(zStack[tos], pMem->s.n);
    pMem->s.flags |= STK_Dyn;
  }
  if( zOld ) sqliteFree(zOld);
  POPSTACK;
  break;
}

/* Opcode: MemLoad P1 * *
**
** Push a copy of the value in memory location P1 onto the stack.
*/
case OP_MemLoad: {
  int tos = ++p->tos;
  int i = pOp->p1;
  VERIFY( if( NeedStack(p, tos) ) goto no_mem; )
  if( i<0 || i>=p->nMem ){
    aStack[tos].flags = STK_Null;
    zStack[tos] = 0;
  }else{
    aStack[tos] = p->aMem[i].s;
    if( aStack[tos].flags & STK_Str ){
      char *z = sqliteMalloc(aStack[tos].n);
      if( z==0 ) goto no_mem;
      memcpy(z, p->aMem[i].z, aStack[tos].n);
      zStack[tos] = z;
      aStack[tos].flags |= STK_Dyn;
    }
  }
  break;
}

/* Opcode: AggReset * P2 *
**
** Reset the aggregator so that it no longer contains any data.
** Future aggregator elements will contain P2 values each.
*/
case OP_AggReset: {
  AggReset(&p->agg);
  p->agg.nMem = pOp->p2;
  break;
}

/* Opcode: AggFocus * P2 *
**
** Pop the top of the stack and use that as an aggregator key.  If
** an aggregator with that same key already exists, then make the
** aggregator the current aggregator and jump to P2.  If no aggregator
** with the given key exists, create one and make it current but
** do not jump.
**
** The order of aggregator opcodes is important.  The order is:
** AggReset AggFocus AggNext.  In other words, you must execute
** AggReset first, then zero or more AggFocus operations, then
** zero or more AggNext operations.  You must not execute an AggFocus
** in between an AggNext and an AggReset.
*/
case OP_AggFocus: {
  int tos = p->tos;
  AggElem *pElem;
  char *zKey;
  int nKey;

  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) ) goto no_mem;
  zKey = zStack[tos]; 
  nKey = aStack[tos].n;
  if( p->agg.nHash<=0 ){
    pElem = 0;
  }else{
    int h = sqliteHashNoCase(zKey, nKey-1) % p->agg.nHash;
    for(pElem=p->agg.apHash[h]; pElem; pElem=pElem->pHash){
      if( strcmp(pElem->zKey, zKey)==0 ) break;
    }
  }
  if( pElem ){
    p->agg.pCurrent = pElem;
    pc = pOp->p2 - 1;
  }else{
    AggInsert(&p->agg, zKey);
    if( sqlite_malloc_failed ) goto no_mem;
  }
  POPSTACK;
  break; 
}

/* Opcode: AggIncr P1 P2 *
**
** Increase the integer value in the P2-th field of the aggregate
** element current in focus by an amount P1.
*/
case OP_AggIncr: {
  AggElem *pFocus = AggInFocus(p->agg);
  int i = pOp->p2;
  if( pFocus==0 ) goto no_mem;
  if( i>=0 && i<p->agg.nMem ){
    Mem *pMem = &pFocus->aMem[i];
    if( pMem->s.flags!=STK_Int ){
      if( pMem->s.flags & STK_Int ){
        /* Do nothing */
      }else if( pMem->s.flags & STK_Real ){
        pMem->s.i = pMem->s.r;
      }else if( pMem->s.flags & STK_Str ){
        pMem->s.i = atoi(pMem->z);
      }else{
        pMem->s.i = 0;
      }
      if( pMem->s.flags & STK_Dyn ) sqliteFree(pMem->z);
      pMem->z = 0;
      pMem->s.flags = STK_Int;
    }
    pMem->s.i += pOp->p1;
  }
  break;
}

/* Opcode: AggSet * P2 *
**
** Move the top of the stack into the P2-th field of the current
** aggregate.  String values are duplicated into new memory.
*/
case OP_AggSet: {
  AggElem *pFocus = AggInFocus(p->agg);
  int i = pOp->p2;
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( pFocus==0 ) goto no_mem;
  if( VERIFY( i>=0 && ) i<p->agg.nMem ){
    Mem *pMem = &pFocus->aMem[i];
    char *zOld;
    if( pMem->s.flags & STK_Dyn ){
      zOld = pMem->z;
    }else{
      zOld = 0;
    }
    pMem->s = aStack[tos];
    if( pMem->s.flags & STK_Str ){
      pMem->z = sqliteMalloc( aStack[tos].n );
      if( pMem->z==0 ) goto no_mem;
      memcpy(pMem->z, zStack[tos], pMem->s.n);
      pMem->s.flags |= STK_Str|STK_Dyn;
    }
    if( zOld ) sqliteFree(zOld);
  }
  POPSTACK;
  break;
}

/* Opcode: AggGet * P2 *
**
** Push a new entry onto the stack which is a copy of the P2-th field
** of the current aggregate.  Strings are not duplicated so
** string values will be ephemeral.
*/
case OP_AggGet: {
  AggElem *pFocus = AggInFocus(p->agg);
  int i = pOp->p2;
  int tos = ++p->tos;
  VERIFY( if( NeedStack(p, tos) ) goto no_mem; )
  if( pFocus==0 ) goto no_mem;
  if( VERIFY( i>=0 && ) i<p->agg.nMem ){
    Mem *pMem = &pFocus->aMem[i];
    aStack[tos] = pMem->s;
    zStack[tos] = pMem->z;
    aStack[tos].flags &= ~STK_Dyn;
  }
  break;
}

/* Opcode: AggNext * P2 *
**
** Make the next aggregate value the current aggregate.  The prior
** aggregate is deleted.  If all aggregate values have been consumed,
** jump to P2.
**
** The order of aggregator opcodes is important.  The order is:
** AggReset AggFocus AggNext.  In other words, you must execute
** AggReset first, then zero or more AggFocus operations, then
** zero or more AggNext operations.  You must not execute an AggFocus
** in between an AggNext and an AggReset.
*/
case OP_AggNext: {
  if( p->agg.nHash ){
    p->agg.nHash = 0;
    sqliteFree(p->agg.apHash);
    p->agg.apHash = 0;
    p->agg.pCurrent = p->agg.pFirst;
  }else if( p->agg.pCurrent==p->agg.pFirst && p->agg.pCurrent!=0 ){
    int i;
    AggElem *pElem = p->agg.pCurrent;
    for(i=0; i<p->agg.nMem; i++){
      if( pElem->aMem[i].s.flags & STK_Dyn ){
        sqliteFree(pElem->aMem[i].z);
      }
    }
    p->agg.pCurrent = p->agg.pFirst = pElem->pNext;
    sqliteFree(pElem);
    p->agg.nElem--;
  }
  if( p->agg.pCurrent==0 ){
    pc = pOp->p2-1;
  }
  break;
}

/* Opcode: SetClear P1 * *
**
** Remove all elements from the P1-th Set.
*/
case OP_SetClear: {
  int i = pOp->p1;
  if( i>=0 && i<p->nSet ){
    SetClear(&p->aSet[i]);
  }
  break;
}

/* Opcode: SetInsert P1 * P3
**
** If Set P1 does not exist then create it.  Then insert value
** P3 into that set.  If P3 is NULL, then insert the top of the
** stack into the set.
*/
case OP_SetInsert: {
  int i = pOp->p1;
  if( p->nSet<=i ){
    p->aSet = sqliteRealloc(p->aSet, (i+1)*sizeof(p->aSet[0]) );
    if( p->aSet==0 ) goto no_mem;
    memset(&p->aSet[p->nSet], 0, sizeof(p->aSet[0])*(i+1 - p->nSet));
    p->nSet = i+1;
  }
  if( pOp->p3 ){
    SetInsert(&p->aSet[i], pOp->p3);
  }else{
    int tos = p->tos;
    if( tos<0 ) goto not_enough_stack;
    if( Stringify(p, tos) ) goto no_mem;
    SetInsert(&p->aSet[i], zStack[tos]);
    POPSTACK;
  }
  if( sqlite_malloc_failed ) goto no_mem;
  break;
}

/* Opcode: SetFound P1 P2 *
**
** Pop the stack once and compare the value popped off with the
** contents of set P1.  If the element popped exists in set P1,
** then jump to P2.  Otherwise fall through.
*/
case OP_SetFound: {
  int i = pOp->p1;
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) ) goto no_mem;
  if( VERIFY( i>=0 && i<p->nSet &&) SetTest(&p->aSet[i], zStack[tos])){
    pc = pOp->p2 - 1;
  }
  POPSTACK;
  break;
}

/* Opcode: SetNotFound P1 P2 *
**
** Pop the stack once and compare the value popped off with the
** contents of set P1.  If the element popped does not exists in 
** set P1, then jump to P2.  Otherwise fall through.
*/
case OP_SetNotFound: {
  int i = pOp->p1;
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) ) goto no_mem;
  if(VERIFY( i>=0 && i<p->nSet &&) !SetTest(&p->aSet[i], zStack[tos])){
    pc = pOp->p2 - 1;
  }
  POPSTACK;
  break;
}

/* Opcode: Strlen * * *
**
** Interpret the top of the stack as a string.  Replace the top of
** stack with an integer which is the length of the string.
*/
case OP_Strlen: {
  int tos = p->tos;
  int len;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) ) goto no_mem;
#ifdef SQLITE_UTF8
  {
    char *z = zStack[tos];
    for(len=0; *z; z++){ if( (0xc0&*z)!=0x80 ) len++; }
  }
#else
  len = aStack[tos].n-1;
#endif
  POPSTACK;
  p->tos++;
  aStack[tos].i = len;
  aStack[tos].flags = STK_Int;
  break;
}

/* Opcode: Substr P1 P2 *
**
** This operation pops between 1 and 3 elements from the stack and
** pushes back a single element.  The bottom-most element popped from
** the stack is a string and the element pushed back is also a string.
** The other two elements popped are integers.  The integers are taken
** from the stack only if P1 and/or P2 are 0.  When P1 or P2 are
** not zero, the value of the operand is used rather than the integer
** from the stack.  In the sequel, we will use P1 and P2 to describe
** the two integers, even if those integers are really taken from the
** stack.
**
** The string pushed back onto the stack is a substring of the string
** that was popped.  There are P2 characters in the substring.  The
** first character of the substring is the P1-th character of the
** original string where the left-most character is 1 (not 0).  If P1
** is negative, then counting begins at the right instead of at the
** left.
*/
case OP_Substr: {
  int cnt;
  int start;
  int n;
  char *z;

  if( pOp->p2==0 ){
    VERIFY( if( p->tos<0 ) goto not_enough_stack; )
    Integerify(p, p->tos);
    cnt = aStack[p->tos].i;
    POPSTACK;
  }else{
    cnt = pOp->p2;
  }
  if( pOp->p1==0 ){
    VERIFY( if( p->tos<0 ) goto not_enough_stack; )
    Integerify(p, p->tos);
    start = aStack[p->tos].i - 1;
    POPSTACK;
  }else{
    start = pOp->p1 - 1;
  }
  VERIFY( if( p->tos<0 ) goto not_enough_stack; )
  if( Stringify(p, p->tos) ) goto no_mem;

  /* "n" will be the number of characters in the input string.
  ** For iso8859, the number of characters is the number of bytes.
  ** Buf for UTF-8, some characters can use multiple bytes and the
  ** situation is more complex. 
  */
#ifdef SQLITE_UTF8
  z = zStack[p->tos];
  for(n=0; *z; z++){ if( (0xc0&*z)!=0x80 ) n++; }
#else
  n = aStack[p->tos].n - 1;
#endif
  if( start<0 ){
    start += n + 1;
    if( start<0 ){
      cnt += start;
      start = 0;
    }
  }
  if( start>n ){
    start = n;
  }
  if( cnt<0 ) cnt = 0;
  if( cnt > n ){
    cnt = n;
  }

  /* At this point, "start" is the index of the first character to
  ** extract and "cnt" is the number of characters to extract.  We
  ** need to convert units on these variable from characters into
  ** bytes.  For iso8859, the conversion is a no-op, but for UTF-8
  ** we have to do a little work.
  */
#ifdef SQLITE_UTF8
  {
    int c_start = start;
    int c_cnt = cnt;
    int i;
    z = zStack[p->tos];
    for(start=i=0; i<c_start; i++){
      while( (0xc0&z[++start])==0x80 ){}
    }
    for(cnt=i=0; i<c_cnt; i++){
      while( (0xc0&z[(++cnt)+start])==0x80 ){}
    }
  }
#endif
  z = sqliteMalloc( cnt+1 );
  if( z==0 ) goto no_mem;
  strncpy(z, &zStack[p->tos][start], cnt);
  z[cnt] = 0;
  POPSTACK;
  p->tos++;
  zStack[p->tos] = z;
  aStack[p->tos].n = cnt + 1;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  break;
}

/* An other opcode is illegal...
*/
default: {
  sprintf(zBuf,"%d",pOp->opcode);
  sqliteSetString(pzErrMsg, "unknown opcode ", zBuf, 0);
  rc = SQLITE_INTERNAL;
  break;
}

/*****************************************************************************
** The cases of the switch statement above this line should all be indented
** 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.
*****************************************************************************/
    }

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

      fprintf(p->trace,"\n");
    }
#endif
  }

cleanup:
  Cleanup(p);
  if( rc!=SQLITE_OK && (db->flags & SQLITE_InTrans)!=0 ){
    sqliteBtreeRollback(pBe);
    sqliteRollbackInternalChanges(db);
    db->flags &= ~SQLITE_InTrans;
  }
  return rc;

  /* Jump to here if a malloc() fails.  It's hard to get a malloc()
  ** to fail on a modern VM computer, so this code is untested.
  */
no_mem:

  sqliteSetString(pzErrMsg, "out or memory", 0);
  rc = SQLITE_NOMEM;
  goto cleanup;

  /* Jump to here for any other kind of fatal error.  The "rc" variable
  ** should hold the error number.
  */
abort_due_to_err:
  sqliteSetString(pzErrMsg, sqliteErrStr(rc), 0);
  goto cleanup;

  /* Jump to here if a operator is encountered that requires more stack
  ** operands than are currently available on the stack.
  */
not_enough_stack:
  sprintf(zBuf,"%d",pc);
  sqliteSetString(pzErrMsg, "too few operands on stack at ", zBuf, 0);

*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.19 2001/09/13 13:46:57 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines

** If any of the values changes or if opcodes are added or removed,
** be sure to also update the zOpName[] array in sqliteVdbe.c to
** mirror the change.
**
** The source tree contains an AWK script named renumberOps.awk that
** can be used to renumber these opcodes when new opcodes are inserted.
*/
#define OP_Transaction         1
#define OP_Commit              2
#define OP_Rollback            3

#define OP_Open                4
#define OP_OpenTemp            5
#define OP_Close               6
#define OP_MoveTo              7
#define OP_Fcnt                8
#define OP_NewRecno            9
#define OP_Put                10
#define OP_Distinct           11
#define OP_Found              12
#define OP_NotFound           13
#define OP_Delete             14
#define OP_Column             15
#define OP_KeyAsData          16
#define OP_Recno              17
#define OP_FullKey            18
#define OP_Rewind             19
#define OP_Next               20

#define OP_Destroy            21
#define OP_CreateIndex        22
#define OP_CreateTable        23
#define OP_Reorganize         24

#define OP_BeginIdx           25
#define OP_NextIdx            26
#define OP_PutIdx             27
#define OP_DeleteIdx          28

#define OP_MemLoad            29
#define OP_MemStore           30

#define OP_ListOpen           31
#define OP_ListWrite          32
#define OP_ListRewind         33
#define OP_ListRead           34
#define OP_ListClose          35

#define OP_SortOpen           36
#define OP_SortPut            37
#define OP_SortMakeRec        38
#define OP_SortMakeKey        39
#define OP_Sort               40
#define OP_SortNext           41
#define OP_SortKey            42
#define OP_SortCallback       43
#define OP_SortClose          44

#define OP_FileOpen           45
#define OP_FileRead           46
#define OP_FileField          47
#define OP_FileClose          48

#define OP_AggReset           49
#define OP_AggFocus           50
#define OP_AggIncr            51
#define OP_AggNext            52
#define OP_AggSet             53
#define OP_AggGet             54

#define OP_SetInsert          55
#define OP_SetFound           56
#define OP_SetNotFound        57
#define OP_SetClear           58

#define OP_MakeRecord         59
#define OP_MakeKey            60
#define OP_MakeIdxKey         61

#define OP_Goto               62
#define OP_If                 63
#define OP_Halt               64

#define OP_ColumnCount        65
#define OP_ColumnName         66
#define OP_Callback           67

#define OP_Integer            68
#define OP_String             69
#define OP_Null               70
#define OP_Pop                71
#define OP_Dup                72
#define OP_Pull               73

#define OP_Add                74
#define OP_AddImm             75
#define OP_Subtract           76
#define OP_Multiply           77
#define OP_Divide             78
#define OP_Min                79
#define OP_Max                80
#define OP_Like               81
#define OP_Glob               82
#define OP_Eq                 83
#define OP_Ne                 84
#define OP_Lt                 85
#define OP_Le                 86
#define OP_Gt                 87
#define OP_Ge                 88
#define OP_IsNull             89
#define OP_NotNull            90
#define OP_Negative           91
#define OP_And                92
#define OP_Or                 93
#define OP_Not                94
#define OP_Concat             95
#define OP_Noop               96

#define OP_Strlen             97
#define OP_Substr             98

#define OP_MAX                98

/*
** Prototypes for the VDBE interface.  See comments on the implementation
** for a description of what each of these routines does.
*/
Vdbe *sqliteVdbeCreate(sqlite*);
void sqliteVdbeCreateCallback(Vdbe*, int*);
void sqliteVdbeTableRootAddr(Vdbe*, int*);
void sqliteVdbeIndexRootAddr(Vdbe*, int*);
int sqliteVdbeAddOp(Vdbe*,int,int,int,const char*,int);
int sqliteVdbeAddOpList(Vdbe*, int nOp, VdbeOp const *aOp);
void sqliteVdbeChangeP1(Vdbe*, int addr, int P1);
void sqliteVdbeChangeP3(Vdbe*, int addr, const char *zP1, int N);
void sqliteVdbeDequoteP3(Vdbe*, int addr);
int sqliteVdbeMakeLabel(Vdbe*);
void sqliteVdbeDelete(Vdbe*);
int sqliteVdbeOpcode(const char *zName);
int sqliteVdbeExec(Vdbe*,sqlite_callback,void*,char**,void*,
                   int(*)(void*,const char*,int));