SQLite

        delete.lo expr.lo fault.lo func.lo global.lo \
        hash.lo journal.lo insert.lo legacy.lo loadext.lo \
        main.lo malloc.lo mem0.lo mem1.lo mem2.lo mem3.lo mem5.lo \
        memjournal.lo \
        mutex.lo mutex_noop.lo mutex_os2.lo mutex_unix.lo mutex_w32.lo \
        notify.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
        pager.lo parse.lo pcache.lo pcache1.lo pragma.lo prepare.lo printf.lo \
        random.lo resolve.lo rowhash.lo rowset.lo select.lo status.lo \
        table.lo tokenize.lo trigger.lo update.lo \
        util.lo vacuum.lo \
        vdbe.lo vdbeapi.lo vdbeaux.lo vdbeblob.lo vdbemem.lo \
        walker.lo where.lo utf.lo vtab.lo

# Object files for the amalgamation.
#

  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \
  $(TOP)/src/rowhash.c \
  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \

random.lo:	$(TOP)/src/random.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/random.c

resolve.lo:	$(TOP)/src/resolve.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/resolve.c

rowhash.lo:	$(TOP)/src/rowhash.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowhash.c

rowset.lo:	$(TOP)/src/rowset.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowset.c

select.lo:	$(TOP)/src/select.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/select.c

status.lo:	$(TOP)/src/status.c $(HDR)

         func.o global.o hash.o \
         icu.o insert.o journal.o legacy.o loadext.o \
         main.o malloc.o mem0.o mem1.o mem2.o mem3.o mem5.o \
         memjournal.o \
         mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \
         notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \
         random.o resolve.o rowhash.o rowset.o rtree.o select.o status.o \
         table.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o \
         walker.o where.o utf.o vtab.o

  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \
  $(TOP)/src/rowhash.c \
  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \

/*
** 2009 April 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.
**
*************************************************************************
**
** This file contains the implementation of the RowHash data structure.
** A RowHash has the following properties:
**
**   *  A RowHash stores an unordered "bag" of 64-bit integer rowids.
**      There is no other content.
**
**   *  Primative operations are CREATE, INSERT, TEST, and DESTROY.
**      There is no way to remove individual elements from the RowHash
**      once they are inserted.
**
**   *  INSERT operations are batched.  TEST operation will ignore
**      elements in the current INSERT batch.  Only elements inserted
**      in prior batches will be seen by a TEST.
**
** The insert batch number is a parameter to the TEST primitive.  The
** hash table is rebuilt whenever the batch number increases.  TEST
** operations only look for INSERTs that occurred in prior batches.
**
** The caller is responsible for insuring that there are no duplicate
** INSERTs.
**
** $Id: rowhash.c,v 1.5 2009/04/22 00:47:01 drh Exp $
*/
#include "sqliteInt.h"

/*
** An upper bound on the size of heap allocations made by this module.
** Limiting the size of allocations helps to avoid memory fragmentation.
*/
#define ROWHASH_ALLOCATION 1024

/*
** If there are less than this number of elements in the RowHash, do not
** bother building a hash-table. Just do a linear search.
*/
#define ROWHASH_LINEAR_SEARCH_LIMIT 10

/*
** This value is what we want the average length of the collision hash
** chain to be.
*/
#define ROWHASH_COLLISION_LENGTH 3


/* Forward references to data structures. */
typedef struct RowHashElem RowHashElem;
typedef struct RowHashBlock RowHashBlock;
typedef union RowHashPtr RowHashPtr;
typedef struct RowHashPage RowHashPage;

/*
** Number of elements in the RowHashBlock.aElem[] array. This array is
** sized to make RowHashBlock very close to (without exceeding)
** ROWHASH_ALLOCATION bytes in size.
*/
#define ROWHASH_ELEM_PER_BLOCK (                                            \
    (ROWHASH_ALLOCATION - ROUND8(sizeof(struct RowHashBlockData))) /        \
    sizeof(RowHashElem)                                                     \
)

/*
** Number of pointers that fit into a single allocation of 
** ROWHASH_ALLOCATION bytes.
*/
#define ROWHASH_POINTER_PER_PAGE (ROWHASH_ALLOCATION/sizeof(RowHashPtr))

/*
** A page of pointers used to construct a hash table.
**
** The hash table is actually a tree composed of instances of this
** object.  Leaves of the tree use the a[].pElem pointer to point
** to RowHashElem entries.  Interior nodes of the tree use the
** a[].pPage element to point to subpages.
**
** The hash table is split into a tree in order to avoid having
** to make large memory allocations, since large allocations can
** result in unwanted memory fragmentation.
*/
struct RowHashPage {
  union RowHashPtr {
    RowHashPage *pPage;   /* Used by interior nodes.  Pointer to subtree. */
    RowHashElem *pElem;   /* Used by leaves.  Pointer to hash entry. */
  } a[ROWHASH_POINTER_PER_PAGE];
};

/*
** Each 64-bit integer in a RowHash is stored as an instance of
** this object.  
**
** Instances of this object are not allocated separately.  They are
** allocated in large blocks using the RowHashBlock object as a container.
*/
struct RowHashElem {
  i64 iVal;              /* The value being stored.  A rowid. */
  RowHashElem *pNext;    /* Next element with the same hash */
};

/*
** In order to avoid many small allocations of RowHashElem objects,
** multiple RowHashElem objects are allocated at once, as an instance
** of this object, and then used as needed.
**
** A single RowHash object will allocate one or more of these RowHashBlock
** objects.  As many are allocated as are needed to store all of the
** content.  All RowHashBlocks are kept on a linked list formed using
** RowHashBlock.data.pNext so that they can be freed when the RowHash
** is destroyed.
**
** The linked list of RowHashBlock objects also provides a way to sequentially
** scan all elements in the RowHash.  This sequential scan is used when
** rebuilding the hash table.  The hash table is rebuilt after every 
** batch of inserts.
*/
struct RowHashBlock {
  struct RowHashBlockData {
    RowHashBlock *pNext;      /* Next RowHashBlock object in list of them all */
  } data;
  RowHashElem aElem[ROWHASH_ELEM_PER_BLOCK]; /* Available RowHashElem objects */
};

/*
** RowHash structure. References to a structure of this type are passed
** around and used as opaque handles by code in other modules.
*/
struct RowHash {
  unsigned int nEntry;    /* Number of used entries over all RowHashBlocks */
  int iBatch;             /* The current insert batch number */
  u16 nUsed;              /* Number of used entries in first RowHashBlock */
  u8 nHeight;             /* Height of tree of hash pages */
  u8 nLinearLimit;        /* Linear search limit (used if pHash==0) */
  int nBucket;            /* Number of buckets in hash table */
  RowHashPage *pHash;     /* Pointer to root of hash table tree */
  RowHashBlock *pBlock;   /* Linked list of RowHashBlocks */
  sqlite3 *db;            /* Associated database connection */
};


/*
** Allocate a hash table tree of height nHeight with *pnLeaf leaf pages. 
** Set *pp to point to the root of the tree.  If the maximum number of leaf 
** pages in a tree of height nHeight is less than *pnLeaf, allocate only
** that part of the tree that is necessary to account for all leaves.
**
** Before returning, subtract the number of leaves in the tree allocated
** from *pnLeaf.
**
** This routine returns SQLITE_NOMEM if a malloc() fails, or SQLITE_OK
** otherwise.
*/
static int allocHashTable(RowHashPage **pp, int nHeight, int *pnLeaf){
  RowHashPage *p = (RowHashPage *)sqlite3MallocZero(sizeof(*p));
  if( !p ){
    return SQLITE_NOMEM;
  }
  *pp = p;
  if( nHeight==0 ){
    (*pnLeaf)--;
  }else{
    int ii;
    for(ii=0; ii<ROWHASH_POINTER_PER_PAGE && *pnLeaf>0; ii++){
      if( allocHashTable(&p->a[ii].pPage, nHeight-1, pnLeaf) ){
        return SQLITE_NOMEM;
      }
    }
  }
  return SQLITE_OK;
}

/*
** Delete the hash table tree of height nHeight passed as the first argument.
*/
static void deleteHashTable(RowHashPage *p, int nHeight){
  if( p ){
    if( nHeight>0 ){
      int ii;
      for(ii=0; ii<ROWHASH_POINTER_PER_PAGE; ii++){
        deleteHashTable(p->a[ii].pPage, nHeight-1);
      }
    }
    sqlite3_free(p);
  }
}

/*
** Find the hash-bucket associated with value iVal. Return a pointer to it.
**
** By "hash-bucket", we mean the RowHashPage.a[].pElem pointer that
** corresponds to a particular hash entry.
*/
static RowHashElem **findHashBucket(RowHash *pRowHash, i64 iVal){
  int aOffset[16];
  int n;
  RowHashPage *pPage = pRowHash->pHash;
  int h = (((u64)iVal) % pRowHash->nBucket);

  assert( pRowHash->nHeight < sizeof(aOffset)/sizeof(aOffset[0]) );
  for(n=0; n<pRowHash->nHeight; n++){
    int h1 = h / ROWHASH_POINTER_PER_PAGE;
    aOffset[n] = h - (h1 * ROWHASH_POINTER_PER_PAGE);
    h = h1;
  }
  aOffset[n] = h;
  for(n=pRowHash->nHeight; n>0; n--){
    pPage = pPage->a[aOffset[n]].pPage;
  }
  return &pPage->a[aOffset[0]].pElem;
}

/*
** Build a new hash table tree in p->pHash.  The new hash table should
** contain all p->nEntry entries in the p->pBlock list.  If there
** existed a prior tree, delete the old tree first before constructing
** the new one.
**
** If the number of entries (p->nEntry) is less than
** ROWHASH_LINEAR_SEARCH_LIMIT, then we are guessing that a linear
** search is going to be faster than a lookup, so do not bother
** building the hash table.
*/
static int makeHashTable(RowHash *p, int iBatch){
  RowHashBlock *pBlock;
  int nBucket;
  int nLeaf, n;
  
  /* Delete the old hash table. */
  deleteHashTable(p->pHash, p->nHeight);
  assert( p->iBatch!=iBatch );
  p->iBatch = iBatch;

  /* Skip building the hash table if the number of elements is small */
  if( p->nEntry<ROWHASH_LINEAR_SEARCH_LIMIT ){
    p->nLinearLimit = p->nEntry;
    p->pHash = 0;
    return SQLITE_OK;
  }

  /* Determine how many leaves the hash-table will comprise. */
  nLeaf = 1 + (p->nEntry / (ROWHASH_POINTER_PER_PAGE*ROWHASH_COLLISION_LENGTH));
  p->nBucket = nBucket = nLeaf*ROWHASH_POINTER_PER_PAGE;

  /* Set nHeight to the height of the tree that contains the leaf pages. If
  ** RowHash.nHeight is zero, then the whole hash-table fits on a single
  ** leaf. If RowHash.nHeight is 1, then RowHash.pHash points to an array
  ** of pointers to leaf pages. If 2, pHash points to an array of pointers
  ** to arrays of pointers to leaf pages. And so on.
  */
  p->nHeight = 0;
  n = nLeaf;
  while( n>1 ){
    n = (n+ROWHASH_POINTER_PER_PAGE-1) / ROWHASH_POINTER_PER_PAGE;
    p->nHeight++;
  }

  /* Allocate the hash-table. */
  if( allocHashTable(&p->pHash, p->nHeight, &nLeaf) ){
    return SQLITE_NOMEM;
  }

  /* Insert all values into the hash-table. */
  for(pBlock=p->pBlock; pBlock; pBlock=pBlock->data.pNext){
    RowHashElem * const pEnd = &pBlock->aElem[
      pBlock==p->pBlock?p->nUsed:ROWHASH_ELEM_PER_BLOCK
    ];
    RowHashElem *pIter;
    for(pIter=pBlock->aElem; pIter<pEnd; pIter++){
      RowHashElem **ppElem = findHashBucket(p, pIter->iVal);
      pIter->pNext = *ppElem;
      *ppElem = pIter;
    }
  }

  return SQLITE_OK;
}

/*
** Check to see if iVal has been inserted into the hash table "p"
** in some batch prior to iBatch.  If so, set *pExists to 1.
** If not, set *pExists to 0.
**
** The hash table is rebuilt whenever iBatch changes.  A hash table
** rebuild might encounter an out-of-memory condition.  If that happens,
** return SQLITE_NOMEM.  If there are no problems, return SQLITE_OK.
**
** The initial "batch" is 0.  So, if there were prior calls to
** sqlite3RowhashInsert() and then this routine is invoked with iBatch==0,
** because all prior inserts where in the same batch, none of the prior
** inserts will be visible and this routine will indicate not found.
** Hence, the first invocation of this routine should probably use
** a batch number of 1.
*/
int sqlite3RowhashTest(
  RowHash *p,     /* The RowHash to search in */
  int iBatch,     /* Look for values inserted in batches prior to this batch */
  i64 iVal,       /* The rowid value we are looking for */
  int *pExists    /* Store 0 or 1 hear to indicate not-found or found */
){
  *pExists = 0;
  if( p ){
    assert( p->pBlock );
    if( iBatch!=p->iBatch && makeHashTable(p, iBatch) ){
      return SQLITE_NOMEM;
    }
    if( p->pHash ){
      RowHashElem *pElem = *findHashBucket(p, iVal);
      for(; pElem; pElem=pElem->pNext){
        if( pElem->iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }else{
      int ii;
      RowHashElem *aElem = p->pBlock->aElem;
      for(ii=0; ii<p->nLinearLimit; ii++){
        if( aElem[ii].iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }
  }
  return SQLITE_OK;
}

/*
** Insert value iVal into the RowHash object.  Allocate a new RowHash
** object if necessary.
**
** Return SQLITE_OK if all goes as planned. If a malloc() fails, return
** SQLITE_NOMEM.
*/
int sqlite3RowhashInsert(sqlite3 *db, RowHash **pp, i64 iVal){
  RowHash *p = *pp;
  
  /* If the RowHash structure has not been allocated, allocate it now. */
  if( !p ){
    p = (RowHash*)sqlite3DbMallocZero(db, sizeof(RowHash));
    if( !p ){
      return SQLITE_NOMEM;
    }
    p->db = db;
    *pp = p;
  }

  /* If the current RowHashBlock is full, or if the first RowHashBlock has
  ** not yet been allocated, allocate one now. */ 
  if( !p->pBlock || p->nUsed==ROWHASH_ELEM_PER_BLOCK ){
    RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock));
    if( !pBlock ){
      return SQLITE_NOMEM;
    }
    pBlock->data.pNext = p->pBlock;
    p->pBlock = pBlock;
    p->nUsed = 0;
  }
  assert( p->nUsed==(p->nEntry % ROWHASH_ELEM_PER_BLOCK) );

  /* Add iVal to the current RowHashBlock. */
  p->pBlock->aElem[p->nUsed].iVal = iVal;
  p->nUsed++;
  p->nEntry++;
  return SQLITE_OK;
}

/*
** Destroy the RowHash object passed as the first argument.
*/
void sqlite3RowhashDestroy(RowHash *p){
  if( p ){
    RowHashBlock *pBlock, *pNext;
    deleteHashTable(p->pHash, p->nHeight);
    for(pBlock=p->pBlock; pBlock; pBlock=pNext){
      pNext = pBlock->data.pNext;
      sqlite3_free(pBlock);
    }
    sqlite3DbFree(p->db, p);
  }
}

/*
** 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.857 2009/04/22 00:47:01 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

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

/*
** Forward references to structures
*/
typedef struct AggInfo AggInfo;
typedef struct AuthContext AuthContext;
typedef struct Bitvec Bitvec;
typedef struct RowHash RowHash;
typedef struct RowSet RowSet;
typedef struct CollSeq CollSeq;
typedef struct Column Column;
typedef struct Db Db;
typedef struct Schema Schema;
typedef struct Expr Expr;
typedef struct ExprList ExprList;

#define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
#define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_FILL_ROWSET      0x0008  /* Save results in a RowSet object */
#define WHERE_OMIT_OPEN        0x0010  /* Table cursor are already open */
#define WHERE_OMIT_CLOSE       0x0020  /* Omit close of table & index cursors */
#define WHERE_FILL_ROWHASH     0x0040  /* Save results in a RowHash object */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;       /* Parsing and code generating context */
  u16 wctrlFlags;      /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  int regRowSet;                 /* Store rowids in this rowset/rowhash */
  int iRowidHandler;             /* Address of OP_RowSet or OP_RowHash */
  SrcList *pTabList;             /* List of tables in the join */
  int iTop;                      /* The very beginning of the WHERE loop */
  int iContinue;                 /* Jump here to continue with next record */
  int iBreak;                    /* Jump here to break out of the loop */
  int nLevel;                    /* Number of nested loop */
  struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
  WhereLevel a[1];               /* Information about each nest loop in WHERE */

RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int);
void sqlite3RowSetClear(RowSet*);
void sqlite3RowSetInsert(RowSet*, i64);
int sqlite3RowSetTest(RowSet*, u8 iBatch, i64);
int sqlite3RowSetNext(RowSet*, i64*);

int sqlite3RowhashInsert(sqlite3*, RowHash **pp, i64 iVal);
int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists);
void sqlite3RowhashDestroy(RowHash *p);

void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int);

#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
  int sqlite3ViewGetColumnNames(Parse*,Table*);
#else
# define sqlite3ViewGetColumnNames(A,B) 0
#endif

**
** 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.836 2009/04/22 00:47:01 drh Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_SeekXX, OP_Next, or OP_Prev opcodes.  The test

    /* A value was pulled from the index */
    assert( pOp->p3>0 && pOp->p3<=p->nMem );
    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}

/* Opcode: RowHash P1 P2 P3 P4
**
** Register P3 is assumed to hold a 64-bit integer value. If register P1
** contains a rowid-hash object and the rowid-hash object contains
** the value held in P3, jump to register P2. Otherwise, insert the
** integer in P3 into the rowid-hash container and continue on to the
** next opcode.
**
** The rowid-hash is optimized for the case where successive sets
** of integers, where each set contains no duplicates. Each set
** of values is identified by a unique P4 value. The first set
** must have P4==0, the final set P4=-1.


**
** This allows optimizations: (a) when P4==0 there is no need to test
** the row-hash object for P3, as it is guaranteed not to contain it,
** (b) when P4==-1 there is no need to insert the value, as it will
** never be tested for, and (c) when a value that is part of set X is
** inserted, there is no need to search to see if the same value was
** previously inserted as part of set X (only if it was previously
** inserted as part of some other set).
*/
case OP_RowHash: {                     /* jump, in1, in3 */
  int iSet = pOp->p4.i;
  assert( pIn3->flags&MEM_Int );

  /* If there is anything other than a row-hash object in memory cell P1,
  ** delete it now and initialize P1 with an empty row-hash (a null pointer
  ** is an acceptable representation of an empty row-hash).
  */
  if( (pIn1->flags & MEM_RowSet)==0 ){
    sqlite3VdbeMemSetRowSet(pIn1);
    if( (pIn1->flags & MEM_RowSet)==0 ) goto no_mem;
  }

  assert( pOp->p4type==P4_INT32 );

  if( iSet ){
    int exists;
    exists = sqlite3RowSetTest(pIn1->u.pRowSet, iSet>=0 ? iSet & 0xf : 0xff,
                               pIn3->u.i);
    if( exists ){
      pc = pOp->p2 - 1;
      break;

*************************************************************************
** 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.168 2009/04/21 09:02:47 danielk1977 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.

*/
struct Mem {
  union {
    i64 i;              /* Integer value. */
    int nZero;          /* Used when bit MEM_Zero is set in flags */
    FuncDef *pDef;      /* Used only when flags==MEM_Agg */
    RowSet *pRowSet;    /* Used only when flags==MEM_RowSet */
    RowHash *pRowHash;  /* Used only when flags==MEM_RowHash */
  } u;
  double r;           /* Real value */
  sqlite3 *db;        /* The associated database connection */
  char *z;            /* String or BLOB value */
  int n;              /* Number of characters in string value, excluding '\0' */
  u16 flags;          /* Some combination of MEM_Null, MEM_Str, MEM_Dyn, etc. */
  u8  type;           /* One of SQLITE_NULL, SQLITE_TEXT, SQLITE_INTEGER, etc */

*/
#define MEM_Null      0x0001   /* Value is NULL */
#define MEM_Str       0x0002   /* Value is a string */
#define MEM_Int       0x0004   /* Value is an integer */
#define MEM_Real      0x0008   /* Value is a real number */
#define MEM_Blob      0x0010   /* Value is a BLOB */
#define MEM_RowSet    0x0020   /* Value is a RowSet object */
#define MEM_RowHash   0x0040   /* Value is a RowHash object */
#define MEM_TypeMask  0x00ff   /* Mask of type bits */

/* Whenever Mem contains a valid string or blob representation, one of
** the following flags must be set to determine the memory management
** policy for Mem.z.  The MEM_Term flag tells us whether or not the
** string is \000 or \u0000 terminated
*/

**
*************************************************************************
** 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.452 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"



/*

  sqlite3 *db = p->db;
  Mem *pMem;
  closeAllCursorsExceptActiveVtabs(p);
  for(pMem=&p->aMem[1], i=1; i<=p->nMem; i++, pMem++){
    if( pMem->flags & MEM_RowSet ){
      sqlite3RowSetClear(pMem->u.pRowSet);
    }
    if( pMem->flags & MEM_RowHash ){
      sqlite3RowhashDestroy(pMem->u.pRowHash);
    }
    MemSetTypeFlag(pMem, MEM_Null);
  }
  releaseMemArray(&p->aMem[1], p->nMem);
  if( p->contextStack ){
    sqlite3DbFree(db, p->contextStack);
  }
  p->contextStack = 0;

*************************************************************************
**
** This file contains code use to manipulate "Mem" structure.  A "Mem"
** stores a single value in the VDBE.  Mem is an opaque structure visible
** only within the VDBE.  Interface routines refer to a Mem using the
** name sqlite_value
**
** $Id: vdbemem.c,v 1.141 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** Call sqlite3VdbeMemExpandBlob() on the supplied value (type Mem*)
** P if required.

/*
** If the memory cell contains a string value that must be freed by
** invoking an external callback, free it now. Calling this function
** does not free any Mem.zMalloc buffer.
*/
void sqlite3VdbeMemReleaseExternal(Mem *p){
  assert( p->db==0 || sqlite3_mutex_held(p->db->mutex) );
  if( p->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet|MEM_RowHash) ){
    if( p->flags&MEM_Agg ){
      sqlite3VdbeMemFinalize(p, p->u.pDef);
      assert( (p->flags & MEM_Agg)==0 );
      sqlite3VdbeMemRelease(p);
    }else if( p->flags&MEM_Dyn && p->xDel ){
      assert( (p->flags&MEM_RowSet)==0 );
      p->xDel((void *)p->z);
      p->xDel = 0;
    }else if( p->flags&MEM_RowSet ){
      sqlite3RowSetClear(p->u.pRowSet);
    }else if( p->flags&MEM_RowHash ){
      sqlite3RowhashDestroy(p->u.pRowHash);
      p->u.pRowHash = 0;
    }
  }
}

/*
** Release any memory held by the Mem. This may leave the Mem in an
** inconsistent state, for example with (Mem.z==0) and

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.384 2009/04/21 17:23:05 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)

  /* Sometimes, this function is required to generate code to do 
  ** something with the rowid of each row scanned. Specifically:
  **
  **   1) If pWInfo->regRowSet is non-zero, then the rowid must be inserted
  **      into the RowSet object stored in register pWInfo->regRowSet.
  **
  **   2) If pWInfo->regRowHash is non-zero, then the rowid must be inserted
  **      into the RowHash object stored in register pWInfo->regRowHash.
  **
  ** Extracting a rowid value from a VDBE cursor is not always a cheap
  ** operation, especially if the rowid is being extracted from an index
  ** cursor. If the rowid value is available as a by-product of the code
  ** generated to create the top of the scan loop, then it can be reused
  ** for either of the two purposes enumerated above without extracting
  ** it from a cursor. The following two variables are used to communicate
  ** the availability of the rowid value to the C-code at the end of this
  ** function that generates the rowid-handling VDBE code.
  */
  int iRowidReg = 0;              /* Rowid is stored in this register */
  int iReleaseReg = 0;            /* Temp register to free before returning */

  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = pWInfo->pWC;
  pLevel = &pWInfo->a[iLevel];
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 
           && (wctrlFlags & WHERE_FILL_ROWHASH)==0;
  regRowSet = pWInfo->regRowSet;
  codeRowSetEarly = 0;

  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.

    **   CREATE INDEX i3 ON t1(c);
    **
    **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
    **
    ** In the example, there are three indexed terms connected by OR.
    ** The top of the loop looks like this:
    **
    **          Null       1                # Zero the row-hash in reg 1
    **
    ** Then, for each indexed term, the following. The arguments to
    ** RowHash are such that the rowid of the current row is inserted
    ** into the row-hash. If it is already present, control skips the
    ** Gosub opcode and jumps straight to the code generated by WhereEnd().
    **
    **        sqlite3WhereBegin(<term>)
    **          RowHash                     # Insert rowid into rowhash
    **          Gosub      2 A
    **        sqlite3WhereEnd()
    **
    ** Following the above, code to terminate the loop. Label A, the target
    ** of the Gosub above, jumps to the instruction right after the Goto.
    **
    **          Null       1                # Zero the row-hash in reg 1
    **          Goto       B                # The loop is finished.
    **
    **       A: <loop body>                 # Return data, whatever.
    **
    **          Return     2                # Jump back to the Gosub
    **
    **       B: <after the loop>
    **
    */
    const int f = WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FILL_ROWHASH;

    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
    WhereTerm *pFinal;     /* Final subterm within the OR-clause. */
    SrcList oneTab;        /* Shortened table list */

    int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
    int regRowhash = ++pParse->nMem;          /* Register for RowHash object */
    int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
    int iRetInit;                             /* Address of regReturn init */
    int ii;
   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator==WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    pFinal = &pOrWc->a[pOrWc->nTerm-1];

    /* Set up a SrcList containing just the table being scanned by this loop. */
    oneTab.nSrc = 1;
    oneTab.nAlloc = 1;
    oneTab.a[0] = *pTabItem;

    /* Initialize the row-hash register to contain NULL. An SQL NULL is 
    ** equivalent to an empty row-hash. 
    **
    ** Also initialize regReturn to contain the address of the instruction 
    ** immediately following the OP_Return at the bottom of the loop. This
    ** is required in a few obscure LEFT JOIN cases where control jumps
    ** over the top of the loop into the body of it. In this case the 
    ** correct response for the end-of-loop code (the OP_Return) is to 
    ** fall through to the next instruction, just as an OP_Next does if
    ** called on an uninitialized cursor.
    */
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash);
    iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);

    /* iReleaseReg = iRowidReg = sqlite3GetTempReg(pParse); */
    for(ii=0; ii<pOrWc->nTerm; ii++){
      WhereTerm *pOrTerm = &pOrWc->a[ii];
      if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
        WhereInfo *pSubWInfo;          /* Info for single OR-term scan */

        /* Loop through table entries that match term pOrTerm. */
        pSubWInfo = sqlite3WhereBegin(
            pParse, &oneTab, pOrTerm->pExpr, 0, f, regRowhash);
        if( pSubWInfo ){
          int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
          /* The call to sqlite3WhereBegin has coded an OP_RowHash 
          ** at instruction iRowHash. Set P2 (the jump target) of this
          ** instruction to jump past the OP_Gosub coded below. This way,
          ** if the rowid is already in the hash-table, the body of the
          ** loop is not executed.
          */
          int iRowHash = pSubWInfo->iRowidHandler;
          sqlite3VdbeChangeP2(v, iRowHash, sqlite3VdbeCurrentAddr(v) + 1);
          sqlite3VdbeChangeP4(v, iRowHash, (char *)iSet, P4_INT32);
          sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);

          /* Finish the loop through table entries that match term pOrTerm. */
          sqlite3WhereEnd(pSubWInfo);
        }
      }
    }
    sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash);
    sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
    sqlite3VdbeResolveLabel(v, iLoopBody);

    pLevel->op = OP_Return;
    pLevel->p1 = regReturn;
    disableTerm(pLevel, pTerm);
  }else

      }
    }
    
    pWInfo->iRowidHandler = sqlite3VdbeCurrentAddr(v);
    if( pWInfo->wctrlFlags&WHERE_FILL_ROWSET ){
      sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, iRowidReg);
    }else{
      assert( pWInfo->wctrlFlags&WHERE_FILL_ROWHASH );
      sqlite3VdbeAddOp3(v, OP_RowHash, regRowSet, 0, iRowidReg);
    }
  }
  sqlite3ReleaseTempReg(pParse, iReleaseReg);

  return notReady;
}

  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->regRowSet = regRowSet;
  pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pMaskSet = (WhereMaskSet*)&pWC[1];
  assert( regRowSet==0 || (wctrlFlags&(WHERE_FILL_ROWSET|WHERE_FILL_ROWHASH)) );

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(pWC, pParse, pMaskSet);
  sqlite3ExprCodeConstants(pParse, pWhere);

   hash.c
   opcodes.c

   os_os2.c
   os_unix.c
   os_win.c

   rowhash.c
   bitvec.c
   pcache.c
   pcache1.c
   rowset.c
   pager.c

   btmutex.c