SQLite

/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.496 2008/08/13 14:07:40 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

  int rc;
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState>=CURSOR_REQUIRESEEK );
  if( pCur->eState==CURSOR_FAULT ){
    return pCur->skip;
  }
  pCur->eState = CURSOR_INVALID;
  rc = sqlite3BtreeMoveto(pCur, pCur->pKey, 0, pCur->nKey, 0, &pCur->skip);
  if( rc==SQLITE_OK ){
    sqlite3_free(pCur->pKey);
    pCur->pKey = 0;
    assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_INVALID );
  }
  return rc;
}

      pCur->atLast = rc==SQLITE_OK;
    }
  }
  return rc;
}

/* Move the cursor so that it points to an entry near the key 
** specified by pKey/nKey/pUnKey. Return a success code.
**
** For INTKEY tables, only the nKey parameter is used.  pKey 
** and pUnKey must be NULL.  For index tables, either pUnKey
** must point to a key that has already been unpacked, or else
** pKey/nKey describes a blob containing the key.
**
** 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
** before or after the key.
**
** The result of comparing the key with the entry to which the

**     *pRes==0     The cursor is left pointing at an entry that
**                  exactly matches pKey.
**
**     *pRes>0      The cursor is left pointing at an entry that
**                  is larger than pKey.
**
*/
int sqlite3BtreeMoveto(
  BtCursor *pCur,        /* The cursor to be moved */
  const void *pKey,      /* The key content for indices.  Not used by tables */
  UnpackedRecord *pUnKey,/* Unpacked version of pKey */
  i64 nKey,              /* Size of pKey.  Or the key for tables */
  int biasRight,         /* If true, bias the search to the high end */
  int *pRes              /* Search result flag */
){
  int rc;
  char aSpace[200];

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) );

  /* If the cursor is already positioned at the point we are trying
  ** to move to, then just return without doing any work */
  if( pCur->eState==CURSOR_VALID && pCur->validNKey && pCur->pPage->intKey ){
    if( pCur->info.nKey==nKey ){
      *pRes = 0;
      return SQLITE_OK;
    }
    if( pCur->atLast && pCur->info.nKey<nKey ){
      *pRes = -1;
      return SQLITE_OK;
    }
  }


  rc = moveToRoot(pCur);
  if( rc ){
    return rc;
  }
  assert( pCur->pPage );
  assert( pCur->pPage->isInit );
  if( pCur->eState==CURSOR_INVALID ){
    *pRes = -1;
    assert( pCur->pPage->nCell==0 );
    return SQLITE_OK;
  }
  if( pCur->pPage->intKey ){
    /* We are given an SQL table to search.  The key is the integer
    ** rowid contained in nKey.  pKey and pUnKey should both be NULL */
    assert( pUnKey==0 );
    assert( pKey==0 );
  }else if( pUnKey==0 ){
    /* We are to search an SQL index using a key encoded as a blob.
    ** The blob is found at pKey and is nKey bytes in length.  Unpack
    ** this key so that we can use it. */
    assert( pKey!=0 );
    pUnKey = sqlite3VdbeRecordUnpack(pCur->pKeyInfo, nKey, pKey,
                                   aSpace, sizeof(aSpace));
    if( pUnKey==0 ) return SQLITE_NOMEM;
  }else{
    /* We are to search an SQL index using a key that is already unpacked
    ** and handed to us in pUnKey. */
    assert( pKey==0 );
  }
  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    int c = -1;  /* pRes return if table is empty must be -1 */
    lwr = 0;
    upr = pPage->nCell-1;
    if( !pPage->intKey && pUnKey==0 ){
      rc = SQLITE_CORRUPT_BKPT;
      goto moveto_finish;
    }
    if( biasRight ){
      pCur->idx = upr;
    }else{
      pCur->idx = (upr+lwr)/2;

        u8 *pCell;
        pCell = findCell(pPage, pCur->idx) + pPage->childPtrSize;
        if( pPage->hasData ){
          u32 dummy;
          pCell += getVarint32(pCell, dummy);
        }
        getVarint(pCell, (u64*)&nCellKey);
        if( nCellKey==nKey ){
          c = 0;
        }else if( nCellKey<nKey ){
          c = -1;
        }else{
          assert( nCellKey>nKey );
          c = +1;
        }
      }else{
        int available;
        pCellKey = (void *)fetchPayload(pCur, &available, 0);
        nCellKey = pCur->info.nKey;
        if( available>=nCellKey ){
          c = sqlite3VdbeRecordCompare(nCellKey, pCellKey, 0, pUnKey);
        }else{
          pCellKey = sqlite3Malloc( nCellKey );
          if( pCellKey==0 ){
            rc = SQLITE_NOMEM;
            goto moveto_finish;
          }
          rc = sqlite3BtreeKey(pCur, 0, nCellKey, (void *)pCellKey);
          c = sqlite3VdbeRecordCompare(nCellKey, pCellKey, 0, pUnKey);
          sqlite3_free(pCellKey);
          if( rc ) goto moveto_finish;
        }
      }
      if( c==0 ){
        pCur->info.nKey = nCellKey;
        if( pPage->intKey && !pPage->leaf ){

    pCur->idx = lwr;
    pCur->info.nSize = 0;
    pCur->validNKey = 0;
    rc = moveToChild(pCur, chldPg);
    if( rc ) goto moveto_finish;
  }
moveto_finish:



















  if( pKey ){
    /* If we created our own unpacked key at the top of this


    ** procedure, then destroy that key before returning. */





    sqlite3VdbeDeleteUnpackedRecord(pUnKey);
  }
  return rc;
}


/*
** Return TRUE if the cursor is not pointing at an entry of the table.

    return pCur->skip;
  }

  /* Save the positions of any other cursors open on this table */
  clearCursorPosition(pCur);
  if( 
    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||
    SQLITE_OK!=(rc = sqlite3BtreeMoveto(pCur, pKey, 0, nKey, appendBias, &loc))
  ){
    return rc;
  }

  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->intKey );

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.102 2008/07/11 21:02:54 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

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

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

struct UnpackedRecord;  /* Forward declaration.  Definition in vdbeaux.c. */

int sqlite3BtreeCursor(
  Btree*,                              /* BTree containing table to open */
  int iTable,                          /* Index of root page */
  int wrFlag,                          /* 1 for writing.  0 for read-only */
  struct KeyInfo*,                     /* First argument to compare function */
  BtCursor *pCursor                    /* Space to write cursor structure */
);
int sqlite3BtreeCursorSize(void);

int sqlite3BtreeCloseCursor(BtCursor*);
int sqlite3BtreeMoveto(
  BtCursor*,
  const void *pKey,
  struct UnpackedRecord *pUnKey,
  i64 nKey,
  int bias,
  int *pRes







);
int sqlite3BtreeCursorHasMoved(BtCursor*, int*);
int sqlite3BtreeDelete(BtCursor*);
int sqlite3BtreeInsert(BtCursor*, const void *pKey, i64 nKey,
                                  const void *pData, int nData,
                                  int nZero, int bias);
int sqlite3BtreeFirst(BtCursor*, int *pRes);

/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.754 2008/08/13 14:07:40 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build

typedef struct StrAccum StrAccum;
typedef struct Table Table;
typedef struct TableLock TableLock;
typedef struct Token Token;
typedef struct TriggerStack TriggerStack;
typedef struct TriggerStep TriggerStep;
typedef struct Trigger Trigger;

typedef struct WhereInfo WhereInfo;
typedef struct WhereLevel WhereLevel;

/*
** Defer sourcing vdbe.h and btree.h until after the "u8" and 
** "BusyHandler" typedefs. vdbe.h also requires a few of the opaque
** pointer types (i.e. FuncDef) defined above.

#define OE_Default  99  /* Do whatever the default action is */


/*
** An instance of the following structure is passed as the first
** argument to sqlite3VdbeKeyCompare and is used to control the 
** comparison of the two index keys.
**
** If the KeyInfo.incrKey value is true and the comparison would
** otherwise be equal, then return a result as if the second key
** were larger.
*/
struct KeyInfo {
  sqlite3 *db;        /* The database connection */
  u8 enc;             /* Text encoding - one of the TEXT_Utf* values */
  u8 incrKey;         /* Increase 2nd key by epsilon before comparison */
  u8 ckPrefixOnly;    /* Records are equal if shorter is a prefix of longer */
  int nField;         /* Number of entries in aColl[] */
  u8 *aSortOrder;     /* If defined an aSortOrder[i] is true, sort DESC */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};































/*
** 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
** by the aiColumn[] field of this structure.  For example, suppose
** we have the following table and index:

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.100 2008/07/12 14:52:20 drh Exp $
*/
#include "sqliteInt.h"
#include "btreeInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

  sqlite3BtreeEnter(pCur->pBtree);
  if( sqlite3BtreeFlags(pCur) & BTREE_INTKEY ){
    int iKey;
    if( Tcl_GetInt(interp, argv[2], &iKey) ){
      sqlite3BtreeLeave(pCur->pBtree);
      return TCL_ERROR;
    }
    rc = sqlite3BtreeMoveto(pCur, 0, 0, iKey, 0, &res);
  }else{
    rc = sqlite3BtreeMoveto(pCur, argv[2], 0, strlen(argv[2]), 0, &res);  
  }
  sqlite3BtreeLeave(pCur->pBtree);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  if( res<0 ) res = -1;

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

/*
** The following global variable is incremented every time a cursor

#ifdef VDBE_PROFILE
  u64 start;                 /* CPU clock count at start of opcode */
  int origPc;                /* Program counter at start of opcode */
#endif
#ifndef SQLITE_OMIT_PROGRESS_CALLBACK
  int nProgressOps = 0;      /* Opcodes executed since progress callback. */
#endif



  assert( p->magic==VDBE_MAGIC_RUN );  /* sqlite3_step() verifies this */
  assert( db->magic==SQLITE_MAGIC_BUSY );
  sqlite3BtreeMutexArrayEnter(&p->aMutex);
  if( p->rc==SQLITE_NOMEM ){
    /* This happens if a malloc() inside a call to sqlite3_column_text() or
    ** sqlite3_column_text16() failed.  */

  assert( i>=0 );
  pCur = allocateCursor(p, i, &pOp[-1], iDb, 1);
  if( pCur==0 ) goto no_mem;
  pCur->nullRow = 1;
  rc = sqlite3BtreeCursor(pX, p2, wrFlag, pOp->p4.p, pCur->pCursor);
  if( pOp->p4type==P4_KEYINFO ){
    pCur->pKeyInfo = pOp->p4.pKeyInfo;
    pCur->pIncrKey = &pCur->pKeyInfo->incrKey;
    pCur->pKeyInfo->enc = ENC(p->db);
  }else{
    pCur->pKeyInfo = 0;
    pCur->pIncrKey = &pCur->bogusIncrKey;
  }
  switch( rc ){
    case SQLITE_BUSY: {
      p->pc = pc;
      p->rc = rc = SQLITE_BUSY;
      goto vdbe_return;
    }

      rc = sqlite3BtreeCreateTable(pCx->pBt, &pgno, BTREE_ZERODATA); 
      if( rc==SQLITE_OK ){
        assert( pgno==MASTER_ROOT+1 );
        rc = sqlite3BtreeCursor(pCx->pBt, pgno, 1, 
                                (KeyInfo*)pOp->p4.z, pCx->pCursor);
        pCx->pKeyInfo = pOp->p4.pKeyInfo;
        pCx->pKeyInfo->enc = ENC(p->db);
        pCx->pIncrKey = &pCx->pKeyInfo->incrKey;
      }
      pCx->isTable = 0;
    }else{
      rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, pCx->pCursor);
      pCx->isTable = 1;
      pCx->pIncrKey = &pCx->bogusIncrKey;
    }
  }
  pCx->isIndex = !pCx->isTable;
  break;
}

/* Opcode: OpenPseudo P1 P2 * * *

  Cursor *pCx;
  assert( i>=0 );
  pCx = allocateCursor(p, i, &pOp[-1], -1, 0);
  if( pCx==0 ) goto no_mem;
  pCx->nullRow = 1;
  pCx->pseudoTable = 1;
  pCx->ephemPseudoTable = pOp->p2;
  pCx->pIncrKey = &pCx->bogusIncrKey;
  pCx->isTable = 1;
  pCx->isIndex = 0;
  break;
}

/* Opcode: Close P1 * * * *
**

  assert( i>=0 && i<p->nCursor );
  pC = p->apCsr[i];
  assert( pC!=0 );
  if( pC->pCursor!=0 ){
    int res, oc;
    oc = pOp->opcode;
    pC->nullRow = 0;
    *pC->pIncrKey = oc==OP_MoveGt || oc==OP_MoveLe;
    if( pC->isTable ){
      i64 iKey = sqlite3VdbeIntValue(pIn3);
      if( pOp->p2==0 ){
        assert( pOp->opcode==OP_MoveGe );
        pC->movetoTarget = iKey;
        pC->rowidIsValid = 0;
        pC->deferredMoveto = 1;
        break;
      }
      rc = sqlite3BtreeMoveto(pC->pCursor, 0, 0, (u64)iKey, 0, &res);
      if( rc!=SQLITE_OK ){
        goto abort_due_to_error;
      }
      pC->lastRowid = iKey;
      pC->rowidIsValid = res==0;
    }else{
      UnpackedRecord r;
      int nField = pOp->p4.i;
      assert( pOp->p4type==P4_INT32 );
      assert( nField>0 );
      r.pKeyInfo = pC->pKeyInfo;
      r.nField = nField;

      r.needFree = 0;

      r.needDestroy = 0;

      r.aMem = &p->aMem[pOp->p3];
      rc = sqlite3BtreeMoveto(pC->pCursor, 0, &r, 0, 0, &res);
      if( rc!=SQLITE_OK ){
        goto abort_due_to_error;
      }
      pC->rowidIsValid = 0;
    }
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
    *pC->pIncrKey = 0;
#ifdef SQLITE_TEST
    sqlite3_search_count++;
#endif
    if( oc==OP_MoveGe || oc==OP_MoveGt ){
      if( res<0 ){
        rc = sqlite3BtreeNext(pC->pCursor, &res);
        if( rc!=SQLITE_OK ) goto abort_due_to_error;

  int i = pOp->p1;
  int alreadyExists = 0;
  Cursor *pC;
  assert( i>=0 && i<p->nCursor );
  assert( p->apCsr[i]!=0 );
  if( (pC = p->apCsr[i])->pCursor!=0 ){
    int res;


    assert( pC->isTable==0 );
    assert( pIn3->flags & MEM_Blob );





    if( pOp->opcode==OP_Found ){
      pC->pKeyInfo->ckPrefixOnly = 1;

    }
    rc = sqlite3BtreeMoveto(pC->pCursor, pIn3->z, 0, pIn3->n, 0, &res);
    pC->pKeyInfo->ckPrefixOnly = 0;

    if( rc!=SQLITE_OK ){
      break;
    }
    alreadyExists = (res==0);
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
  }
  if( pOp->opcode==OP_Found ){
    if( alreadyExists ) pc = pOp->p2 - 1;
  }else{
    if( !alreadyExists ) pc = pOp->p2 - 1;
  }
  break;
}

/* Opcode: IsUnique P1 P2 P3 P4 *
**
** The P3 register contains an integer record number.  Call this
** record number R.  The P4 register contains an index key created
** using MakeIdxRec.  Call it K.
**
** P1 is an index.  So it has no data and its key consists of a
** record generated by OP_MakeRecord where the last field is the 
** rowid of the entry that the index refers to.
** 
** This instruction asks if there is an entry in P1 where the
** fields matches K but the rowid is different from R.

  R = pIn3->u.i;
  assert( i>=0 && i<p->nCursor );
  pCx = p->apCsr[i];
  assert( pCx!=0 );
  pCrsr = pCx->pCursor;
  if( pCrsr!=0 ){
    int res;
    i64 v;         /* The record number on the P1 entry that matches K */
    char *zKey;    /* The value of K */
    int nKey;      /* Number of bytes in K */
    int len;       /* Number of bytes in K without the rowid at the end */
    int szRowid;   /* Size of the rowid column at the end of zKey */

    /* Make sure K is a string and make zKey point to K
    */
    assert( pK->flags & MEM_Blob );
    zKey = pK->z;

    nKey = pK->n;


    /* sqlite3VdbeIdxRowidLen() only returns other than SQLITE_OK when the
    ** record passed as an argument corrupt. Since the record in this case
    ** has just been created by an OP_MakeRecord instruction, and not loaded
    ** from the database file, it is not possible for it to be corrupt.
    ** Therefore, assert(rc==SQLITE_OK).
    */
    rc = sqlite3VdbeIdxRowidLen((u8*)zKey, nKey, &szRowid);
    assert(rc==SQLITE_OK);
    len = nKey-szRowid;

    /* Search for an entry in P1 where all but the last four bytes match K.
    ** If there is no such entry, jump immediately to P2.
    */
    assert( pCx->deferredMoveto==0 );
    pCx->cacheStatus = CACHE_STALE;
    rc = sqlite3BtreeMoveto(pCrsr, zKey, 0, len, 0, &res);
    if( rc!=SQLITE_OK ){

      goto abort_due_to_error;
    }
    if( res<0 ){
      rc = sqlite3BtreeNext(pCrsr, &res);
      if( res ){
        pc = pOp->p2 - 1;

        break;
      }
    }
    rc = sqlite3VdbeIdxKeyCompare(pCx, 0, len, (u8*)zKey, &res); 

    if( rc!=SQLITE_OK ) goto abort_due_to_error;
    if( res>0 ){
      pc = pOp->p2 - 1;
      break;
    }

    /* At this point, pCrsr is pointing to an entry in P1 where all but

  assert( p->apCsr[i]!=0 );
  if( (pCrsr = (pC = p->apCsr[i])->pCursor)!=0 ){
    int res;
    u64 iKey;
    assert( pIn3->flags & MEM_Int );
    assert( p->apCsr[i]->isTable );
    iKey = intToKey(pIn3->u.i);
    rc = sqlite3BtreeMoveto(pCrsr, 0, 0, iKey, 0,&res);
    pC->lastRowid = pIn3->u.i;
    pC->rowidIsValid = res==0;
    pC->nullRow = 0;
    pC->cacheStatus = CACHE_STALE;
    /* res might be uninitialized if rc!=SQLITE_OK.  But if rc!=SQLITE_OK
    ** processing is about to abort so we really do not care whether or not
    ** the following jump is taken.  (In other words, do not stress over

          v++;
        }else{
          sqlite3_randomness(sizeof(v), &v);
          if( cnt<5 ) v &= 0xffffff;
        }
        if( v==0 ) continue;
        x = intToKey(v);
        rx = sqlite3BtreeMoveto(pC->pCursor, 0, 0, (u64)x, 0, &res);
        cnt++;
      }while( cnt<100 && rx==SQLITE_OK && res==0 );
      db->priorNewRowid = v;
      if( rx==SQLITE_OK && res==0 ){
        rc = SQLITE_FULL;
        goto abort_due_to_error;
      }

  assert( i>=0 && i<p->nCursor );
  assert( p->apCsr[i]!=0 );
  if( (pCrsr = (pC = p->apCsr[i])->pCursor)!=0 ){
    int res;
    UnpackedRecord r;
    r.pKeyInfo = pC->pKeyInfo;
    r.nField = pOp->p3;
    r.needFree = 0;
    r.needDestroy = 0;
    r.aMem = &p->aMem[pOp->p2];
    rc = sqlite3BtreeMoveto(pCrsr, 0, &r, 0, 0, &res);
    if( rc==SQLITE_OK && res==0 ){
      rc = sqlite3BtreeDelete(pCrsr);
    }
    assert( pC->deferredMoveto==0 );
    pC->cacheStatus = CACHE_STALE;
  }
  break;

    int res;
    UnpackedRecord r;
    assert( pC->deferredMoveto==0 );
    assert( pOp->p5==0 || pOp->p5==1 );
    assert( pOp->p4type==P4_INT32 );
    r.pKeyInfo = pC->pKeyInfo;
    r.nField = pOp->p4.i;


    r.needFree = 0;
    r.needDestroy = 0;

    r.aMem = &p->aMem[pOp->p3];
    *pC->pIncrKey = pOp->p5;
    rc = sqlite3VdbeIdxKeyCompare(pC, &r, 0, 0, &res);
    *pC->pIncrKey = 0;
    if( pOp->opcode==OP_IdxLT ){
      res = -res;
    }else{
      assert( pOp->opcode==OP_IdxGE );
      res++;
    }
    if( res>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.136 2008/08/13 14:07:41 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines
** in the source file sqliteVdbe.c are allowed to see the insides
** of this structure.
*/
typedef struct Vdbe Vdbe;

/*
** The names of the following types declared in vdbeInt.h are required
** for the VdbeOp definition.
*/
typedef struct VdbeFunc VdbeFunc;
typedef struct Mem Mem;
typedef struct UnpackedRecord UnpackedRecord;

/*
** A single instruction of the virtual machine has an opcode
** and as many as three operands.  The instruction is recorded
** as an instance of the following structure:
*/
struct VdbeOp {

void sqlite3VdbeSwap(Vdbe*,Vdbe*);

#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
int sqlite3VdbeReleaseMemory(int);
#endif
UnpackedRecord *sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,void*,int);
void sqlite3VdbeDeleteUnpackedRecord(UnpackedRecord*);
int sqlite3VdbeRecordCompare(int,const void*,int,UnpackedRecord*);


#ifndef NDEBUG
  void sqlite3VdbeComment(Vdbe*, const char*, ...);
# define VdbeComment(X)  sqlite3VdbeComment X
  void sqlite3VdbeNoopComment(Vdbe*, const char*, ...);
# define VdbeNoopComment(X)  sqlite3VdbeNoopComment X
#else
# define VdbeComment(X)
# define VdbeNoopComment(X)
#endif

#endif

*************************************************************************
** This is the header file for information that is private to the
** VDBE.  This information used to all be at the top of the single
** source code file "vdbe.c".  When that file became too big (over
** 6000 lines long) it was split up into several smaller files and
** this header information was factored out.
**
** $Id: vdbeInt.h,v 1.153 2008/08/02 03:50:39 drh Exp $
*/
#ifndef _VDBEINT_H_
#define _VDBEINT_H_

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

  Bool nullRow;         /* True if pointing to a row with no data */
  Bool nextRowidValid;  /* True if the nextRowid field is valid */
  Bool pseudoTable;     /* This is a NEW or OLD pseudo-tables of a trigger */
  Bool ephemPseudoTable;
  Bool deferredMoveto;  /* A call to sqlite3BtreeMoveto() is needed */
  Bool isTable;         /* True if a table requiring integer keys */
  Bool isIndex;         /* True if an index containing keys only - no data */
  u8 bogusIncrKey;      /* Something for pIncrKey to point to if pKeyInfo==0 */
  i64 movetoTarget;     /* Argument to the deferred sqlite3BtreeMoveto() */
  Btree *pBt;           /* Separate file holding temporary table */
  int nData;            /* Number of bytes in pData */
  char *pData;          /* Data for a NEW or OLD pseudo-table */
  i64 iKey;             /* Key for the NEW or OLD pseudo-table row */
  u8 *pIncrKey;         /* Pointer to pKeyInfo->incrKey */
  KeyInfo *pKeyInfo;    /* Info about index keys needed by index cursors */
  int nField;           /* Number of fields in the header */
  i64 seqCount;         /* Sequence counter */
  sqlite3_vtab_cursor *pVtabCursor;  /* The cursor for a virtual table */
  const sqlite3_module *pModule;     /* Module for cursor pVtabCursor */

  /* Cached information about the header for the data record that the

#endif
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  Vdbe *pLruPrev;
  Vdbe *pLruNext;
#endif
};

/*
** An instance of the following structure holds information about a
** single index record that has already been parsed out into individual
** values.
**
** A record is an object that contains one or more fields of data.
** Records are used to store the content of a table row and to store
** the key of an index.  A blob encoding of a record is created by
** the OP_MakeRecord opcode of the VDBE and is disassemblied by the
** OP_Column opcode.
**
** This structure holds a record that has already been disassembled
** into its constitutent fields.
*/
struct UnpackedRecord {
  KeyInfo *pKeyInfo;  /* Collation and sort-order information */
  u16 nField;         /* Number of entries in apMem[] */
  u8 needFree;        /* True if memory obtained from sqlite3_malloc() */
  u8 needDestroy;     /* True if apMem[]s should be destroyed on close */
  Mem *aMem;          /* Values */
};

/*
** The following are allowed values for Vdbe.magic
*/
#define VDBE_MAGIC_INIT     0x26bceaa5    /* Building a VDBE program */
#define VDBE_MAGIC_RUN      0xbdf20da3    /* VDBE is ready to execute */
#define VDBE_MAGIC_HALT     0x519c2973    /* VDBE has completed execution */
#define VDBE_MAGIC_DEAD     0xb606c3c8    /* The VDBE has been deallocated */

int sqlite3VdbeSerialTypeLen(u32);
u32 sqlite3VdbeSerialType(Mem*, int);
int sqlite3VdbeSerialPut(unsigned char*, int, Mem*, int);
int sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*);
void sqlite3VdbeDeleteAuxData(VdbeFunc*, int);

int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *);
int sqlite3VdbeIdxKeyCompare(Cursor*,UnpackedRecord *,int,const unsigned char*,int*);
int sqlite3VdbeIdxRowid(BtCursor *, i64 *);
int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*);
int sqlite3VdbeIdxRowidLen(const u8*, int, int*);
int sqlite3VdbeExec(Vdbe*);
int sqlite3VdbeList(Vdbe*);
int sqlite3VdbeHalt(Vdbe*);
int sqlite3VdbeChangeEncoding(Mem *, int);
int sqlite3VdbeMemTooBig(Mem*);
int sqlite3VdbeMemCopy(Mem*, const Mem*);
void sqlite3VdbeMemShallowCopy(Mem*, const Mem*, int);

**
*************************************************************************
** This file contains code used for creating, destroying, and populating
** a VDBE (or an "sqlite3_stmt" as it is known to the outside world.)  Prior
** to version 2.8.7, all this code was combined into the vdbe.c source file.
** But that file was getting too big so this subroutines were split out.
**
** $Id: vdbeaux.c,v 1.406 2008/08/13 14:07:41 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

int sqlite3VdbeCursorMoveto(Cursor *p){
  if( p->deferredMoveto ){
    int res, rc;
#ifdef SQLITE_TEST
    extern int sqlite3_search_count;
#endif
    assert( p->isTable );
    rc = sqlite3BtreeMoveto(p->pCursor, 0, 0, p->movetoTarget, 0, &res);
    if( rc ) return rc;
    *p->pIncrKey = 0;
    p->lastRowid = keyToInt(p->movetoTarget);
    p->rowidIsValid = res==0;
    if( res<0 ){
      rc = sqlite3BtreeNext(p->pCursor, &res);
      if( rc ) return rc;
    }
#ifdef SQLITE_TEST

  Mem *pMem;
  
  assert( sizeof(Mem)>sizeof(*p) );
  nByte = sizeof(Mem)*(pKeyInfo->nField+2);
  if( nByte>szSpace ){
    p = sqlite3DbMallocRaw(pKeyInfo->db, nByte);
    if( p==0 ) return 0;
    p->needFree = 1;
  }else{
    p = pSpace;
    p->needFree = 0;
  }
  p->pKeyInfo = pKeyInfo;
  p->nField = pKeyInfo->nField + 1;
  p->needDestroy = 1;
  p->aMem = pMem = &((Mem*)p)[1];
  idx = getVarint32(aKey, szHdr);
  d = szHdr;
  u = 0;
  while( idx<szHdr && u<p->nField ){
    u32 serial_type;

}

/*
** This routine destroys a UnpackedRecord object
*/
void sqlite3VdbeDeleteUnpackedRecord(UnpackedRecord *p){
  if( p ){
    if( p->needDestroy ){
      int i;
      Mem *pMem;
      for(i=0, pMem=p->aMem; i<p->nField; i++, pMem++){
        if( pMem->zMalloc ){
          sqlite3VdbeMemRelease(pMem);
        }
      }
    }
    if( p->needFree ){
      sqlite3DbFree(p->pKeyInfo->db, p);
    }
  }
}

/*
** This function compares the two table rows or index records
** specified by {nKey1, pKey1} and pPKey2.  It returns a negative, zero
** or positive integer if {nKey1, pKey1} is less than, equal to or 
** greater than pPKey2.  The {nKey1, pKey1} key must be a blob
** created by th OP_MakeRecord opcode of the VDBE.  The pPKey2
** key must be a parsed key such as obtained from
** sqlite3VdbeParseRecord.
**
** Key1 and Key2 do not have to contain the same number of fields.
** The key with fewer fields is usually considered lessor than the 
** longer.  However if pPKey2->pKeyInfo->incrKey is set and
** the common prefixes are equal, then key1 is less than key2.
** Or if pPKey2->pKeyInfo->ckPrefixOnly flag is set and the 
** prefixes are equal, then the keys are considered to be equal and
** the parts beyond the common prefix are ignored.
**

** The last nHdrIgnore1 bytes of the header of pKey1 are ignored,
** as if they do not exist.  Usually nHdrIgnore1 is 0 which means
** that we look at the entire key.  But sometimes nHdrIgnore1 is 1.
** When nHdrIgnore1 is 1, the keys are index records and so the last
** column is a rowid.  The type code is always one byte in length.
** Hence, setting nHdrIgnore1 to 1 means that the final rowid at the
** end of the record should be treated as if it does not exist.
**
** Historical note: In earlier versions of this routine both Key1
** and Key2 were blobs obtained from OP_MakeRecord.  But we found
** that in typical use the same Key2 would be submitted multiple times
** in a row.  So an optimization was added to parse the Key2 key
** separately and submit the parsed version.  In this way, we avoid
** parsing the same Key2 multiple times.
*/
int sqlite3VdbeRecordCompare(
  int nKey1, const void *pKey1, /* Left key */
  int nHdrIgnore1,              /* Omit this much from end of key1 header */
  UnpackedRecord *pPKey2        /* Right key */
){
  u32 d1;            /* Offset into aKey[] of next data element */
  u32 idx1;          /* Offset into aKey[] of next header element */
  u32 szHdr1;        /* Number of bytes in header */
  int i = 0;
  int nField;
  int rc = 0;
  const unsigned char *aKey1 = (const unsigned char *)pKey1;
  KeyInfo *pKeyInfo;
  Mem mem1;

  pKeyInfo = pPKey2->pKeyInfo;
  mem1.enc = pKeyInfo->enc;
  mem1.db = pKeyInfo->db;
  mem1.flags = 0;
  mem1.zMalloc = 0;
  
  idx1 = getVarint32(aKey1, szHdr1);
  d1 = szHdr1;

  szHdr1 -= nHdrIgnore1;

  nField = pKeyInfo->nField;
  while( idx1<szHdr1 && i<pPKey2->nField ){
    u32 serial_type1;

    /* Read the serial types for the next element in each key. */
    idx1 += getVarint32( aKey1+idx1, serial_type1 );
    if( d1>=nKey1 && sqlite3VdbeSerialTypeLen(serial_type1)>0 ) break;

    }
    i++;
  }
  if( mem1.zMalloc ) sqlite3VdbeMemRelease(&mem1);

  if( rc==0 ){
    /* rc==0 here means that one of the keys ran out of fields and
    ** all the fields up to that point were equal. If the incrKey 
    ** flag is true, then break the tie by treating the second key 
    ** as larger.  If ckPrefixOnly is true, then keys with common prefixes
    ** are considered to be equal.  Otherwise, the longer key is the 
    ** larger.  As it happens, the pPKey2 will always be the longer
    ** if there is a difference.
    */
    if( pKeyInfo->incrKey ){
      rc = -1;
    }else if( pKeyInfo->ckPrefixOnly ){
      /* Leave rc==0 */
    }else if( idx1<szHdr1 ){
      rc = 1;
    }
  }else if( pKeyInfo->aSortOrder && i<pKeyInfo->nField
               && pKeyInfo->aSortOrder[i] ){
    rc = -rc;
  }

  return rc;
}
  
/*
** The argument is an index entry composed using the OP_MakeRecord opcode.
** The last entry in this record should be an integer (specifically
** an integer rowid).  This routine returns the number of bytes in
** that integer.
*/
int sqlite3VdbeIdxRowidLen(const u8 *aKey, int nKey, int *pRowidLen){
  u32 szHdr;        /* Size of the header */
  u32 typeRowid;    /* Serial type of the rowid */

  (void)getVarint32(aKey, szHdr);
  if( szHdr>nKey ){
    return SQLITE_CORRUPT_BKPT;
  }
  (void)getVarint32(&aKey[szHdr-1], typeRowid);
  *pRowidLen = sqlite3VdbeSerialTypeLen(typeRowid);
  return SQLITE_OK;
}
 

/*
** pCur points at an index entry created using the OP_MakeRecord opcode.
** Read the rowid (the last field in the record) and store it in *rowid.
** Return SQLITE_OK if everything works, or an error code otherwise.
*/

**
** pUnpacked may be an unpacked version of pKey,nKey.  If pUnpacked is
** supplied it is used in place of pKey,nKey.
*/
int sqlite3VdbeIdxKeyCompare(
  Cursor *pC,                 /* The cursor to compare against */
  UnpackedRecord *pUnpacked,  /* Unpacked version of pKey and nKey */
  int nKey, const u8 *pKey,   /* The key to compare */
  int *res                    /* Write the comparison result here */
){
  i64 nCellKey = 0;
  int rc;
  BtCursor *pCur = pC->pCursor;
  Mem m;
  UnpackedRecord *pRec;
  char zSpace[200];

  sqlite3BtreeKeySize(pCur, &nCellKey);
  if( nCellKey<=0 ){
    *res = 0;
    return SQLITE_OK;
  }
  m.db = 0;
  m.flags = 0;
  m.zMalloc = 0;
  rc = sqlite3VdbeMemFromBtree(pC->pCursor, 0, nCellKey, 1, &m);
  if( rc ){
    return rc;
  }
  if( !pUnpacked ){
    pRec = sqlite3VdbeRecordUnpack(pC->pKeyInfo, nKey, pKey,
                                zSpace, sizeof(zSpace));
  }else{
    pRec = pUnpacked;
  }
  if( pRec==0 ){
    return SQLITE_NOMEM;
  }
  *res = sqlite3VdbeRecordCompare(m.n, m.z, 1, pRec);
  if( !pUnpacked ){
    sqlite3VdbeDeleteUnpackedRecord(pRec);
  }
  sqlite3VdbeMemRelease(&m);
  return SQLITE_OK;
}

/*
** This routine sets the value to be returned by subsequent calls to
** sqlite3_changes() on the database handle 'db'.