** 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.307 2006/01/22 21:52:57 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................

  /* Restore the current cursor position (a no-op if the cursor is not in 
  ** CURSOR_REQUIRESEEK state) and save the positions of any other cursors 
  ** open on the same table. Then call sqlite3pager_write() on the page
  ** that the entry will be deleted from.
  */
  if( 
    (rc = restoreOrClearCursorPosition(pCur, 1)) ||
    (rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||
    (rc = sqlite3pager_write(pPage->aData))
  ){
    return rc;
  }

  /* Locate the cell within it's page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.

** 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.308 2006/01/23 13:00:36 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.
................................................................................

  /* Restore the current cursor position (a no-op if the cursor is not in 
  ** CURSOR_REQUIRESEEK state) and save the positions of any other cursors 
  ** open on the same table. Then call sqlite3pager_write() on the page
  ** that the entry will be deleted from.
  */
  if( 
    (rc = restoreOrClearCursorPosition(pCur, 1))!=0 ||
    (rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur))!=0 ||
    (rc = sqlite3pager_write(pPage->aData))!=0
  ){
    return rc;
  }

  /* Locate the cell within it's page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.

**    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.476 2006/01/23 00:04:55 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Extra interface definitions for those who need them
*/
................................................................................
/*
** If compiling for a processor that lacks floating point support,
** substitute integer for floating-point
*/
#ifdef SQLITE_OMIT_FLOATING_POINT
# define double sqlite_int64
# define LONGDOUBLE_TYPE sqlite_int64

# define SQLITE_BIG_DBL (0x7fffffffffffffff)

# define SQLITE_OMIT_DATETIME_FUNCS 1
# define SQLITE_OMIT_TRACE 1
#endif




/*
** The maximum number of in-memory pages to use for the main database
** table and for temporary tables. Internally, the MAX_PAGES and 
** TEMP_PAGES macros are used. To override the default values at
** compilation time, the SQLITE_DEFAULT_CACHE_SIZE and 
** SQLITE_DEFAULT_TEMP_CACHE_SIZE macros should be set.
................................................................................
  int nCol;        /* Number of columns in this table */
  Column *aCol;    /* Information about each column */
  int iPKey;       /* If not less then 0, use aCol[iPKey] as the primary key */
  Index *pIndex;   /* List of SQL indexes on this table. */
  int tnum;        /* Root BTree node for this table (see note above) */
  Select *pSelect; /* NULL for tables.  Points to definition if a view. */
  u8 readOnly;     /* True if this table should not be written by the user */
// u8 iDb;          /* Index into sqlite.aDb[] of the backend for this table */
  u8 isTransient;  /* True if automatically deleted when VDBE finishes */
  u8 hasPrimKey;   /* True if there exists a primary key */
  u8 keyConf;      /* What to do in case of uniqueness conflict on iPKey */
  u8 autoInc;      /* True if the integer primary key is autoincrement */
  int nRef;          /* Number of pointers to this Table */
  Trigger *pTrigger; /* List of SQL triggers on this table */
  FKey *pFKey;       /* Linked list of all foreign keys in this table */
................................................................................
** If the Expr is of type OP_Column, and the table it is selecting from
** is a disk table or the "old.*" pseudo-table, then pTab points to the
** corresponding table definition.
*/
struct Expr {
  u8 op;                 /* Operation performed by this node */
  char affinity;         /* The affinity of the column or 0 if not a column */
//u8 iDb;                /* Database referenced by this expression */
  u8 flags;              /* Various flags.  See below */
  CollSeq *pColl;        /* The collation type of the column or 0 */
  Expr *pLeft, *pRight;  /* Left and right subnodes */
  ExprList *pList;       /* A list of expressions used as function arguments
                         ** or in "<expr> IN (<expr-list)" */
  Token token;           /* An operand token */
  Token span;            /* Complete text of the expression */
................................................................................
Schema *sqlite3SchemaGet(Btree *);
int sqlite3SchemaToIndex(sqlite3 *db, Schema *);
KeyInfo *sqlite3IndexKeyinfo(Parse *, Index *);
int sqlite3CreateFunc(sqlite3 *, const char *, int, int, void *, 
  void (*)(sqlite3_context*,int,sqlite3_value **),
  void (*)(sqlite3_context*,int,sqlite3_value **), void (*)(sqlite3_context*));
int sqlite3ApiExit(sqlite3 *db, int);
int sqlite3MallocFailed();
void sqlite3FailedMalloc();

#ifndef SQLITE_OMIT_SHARED_CACHE
  void sqlite3TableLock(Parse *, int, int, u8, const char *);
#else
  #define sqlite3TableLock(v,w,x,y,z)
#endif

#ifdef SQLITE_MEMDEBUG
  void sqlite3MallocDisallow();
  void sqlite3MallocAllow();
  int sqlite3TestMallocFail();
#else
  #define sqlite3TestMallocFail() 0
  #define sqlite3MallocDisallow()
  #define sqlite3MallocAllow()
#endif

#ifdef SQLITE_SSE
#include "sseInt.h"
#endif

#endif

**    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.477 2006/01/23 13:00:38 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Extra interface definitions for those who need them
*/
................................................................................
/*
** If compiling for a processor that lacks floating point support,
** substitute integer for floating-point
*/
#ifdef SQLITE_OMIT_FLOATING_POINT
# define double sqlite_int64
# define LONGDOUBLE_TYPE sqlite_int64
# ifndef SQLITE_BIG_DBL
#   define SQLITE_BIG_DBL (0x7fffffffffffffff)
# endif
# define SQLITE_OMIT_DATETIME_FUNCS 1
# define SQLITE_OMIT_TRACE 1
#endif
#ifndef SQLITE_BIG_DBL
# define SQLITE_BIG_DBL (1e99)
#endif

/*
** The maximum number of in-memory pages to use for the main database
** table and for temporary tables. Internally, the MAX_PAGES and 
** TEMP_PAGES macros are used. To override the default values at
** compilation time, the SQLITE_DEFAULT_CACHE_SIZE and 
** SQLITE_DEFAULT_TEMP_CACHE_SIZE macros should be set.
................................................................................
  int nCol;        /* Number of columns in this table */
  Column *aCol;    /* Information about each column */
  int iPKey;       /* If not less then 0, use aCol[iPKey] as the primary key */
  Index *pIndex;   /* List of SQL indexes on this table. */
  int tnum;        /* Root BTree node for this table (see note above) */
  Select *pSelect; /* NULL for tables.  Points to definition if a view. */
  u8 readOnly;     /* True if this table should not be written by the user */

  u8 isTransient;  /* True if automatically deleted when VDBE finishes */
  u8 hasPrimKey;   /* True if there exists a primary key */
  u8 keyConf;      /* What to do in case of uniqueness conflict on iPKey */
  u8 autoInc;      /* True if the integer primary key is autoincrement */
  int nRef;          /* Number of pointers to this Table */
  Trigger *pTrigger; /* List of SQL triggers on this table */
  FKey *pFKey;       /* Linked list of all foreign keys in this table */
................................................................................
** If the Expr is of type OP_Column, and the table it is selecting from
** is a disk table or the "old.*" pseudo-table, then pTab points to the
** corresponding table definition.
*/
struct Expr {
  u8 op;                 /* Operation performed by this node */
  char affinity;         /* The affinity of the column or 0 if not a column */

  u8 flags;              /* Various flags.  See below */
  CollSeq *pColl;        /* The collation type of the column or 0 */
  Expr *pLeft, *pRight;  /* Left and right subnodes */
  ExprList *pList;       /* A list of expressions used as function arguments
                         ** or in "<expr> IN (<expr-list)" */
  Token token;           /* An operand token */
  Token span;            /* Complete text of the expression */
................................................................................
Schema *sqlite3SchemaGet(Btree *);
int sqlite3SchemaToIndex(sqlite3 *db, Schema *);
KeyInfo *sqlite3IndexKeyinfo(Parse *, Index *);
int sqlite3CreateFunc(sqlite3 *, const char *, int, int, void *, 
  void (*)(sqlite3_context*,int,sqlite3_value **),
  void (*)(sqlite3_context*,int,sqlite3_value **), void (*)(sqlite3_context*));
int sqlite3ApiExit(sqlite3 *db, int);
int sqlite3MallocFailed(void);
void sqlite3FailedMalloc(void);

#ifndef SQLITE_OMIT_SHARED_CACHE
  void sqlite3TableLock(Parse *, int, int, u8, const char *);
#else
  #define sqlite3TableLock(v,w,x,y,z)
#endif

#ifdef SQLITE_MEMDEBUG
  void sqlite3MallocDisallow(void);
  void sqlite3MallocAllow(void);
  int sqlite3TestMallocFail(void);
#else
  #define sqlite3TestMallocFail(void) 0
  #define sqlite3MallocDisallow(void)
  #define sqlite3MallocAllow(void)
#endif

#ifdef SQLITE_SSE
#include "sseInt.h"
#endif

#endif

**    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.
**
*************************************************************************
** A TCL Interface to SQLite
**
** $Id: tclsqlite.c,v 1.149 2006/01/09 23:40:25 drh Exp $
*/
#ifndef NO_TCL     /* Omit this whole file if TCL is unavailable */

#include "sqliteInt.h"
#include "hash.h"
#include "tcl.h"
#include <stdlib.h>
................................................................................
  rc = Tcl_Eval(pDb->interp, pDb->zProgress);
  if( rc!=TCL_OK || atoi(Tcl_GetStringResult(pDb->interp)) ){
    return 1;
  }
  return 0;
}


/*
** This routine is called by the SQLite trace handler whenever a new
** block of SQL is executed.  The TCL script in pDb->zTrace is executed.
*/
static void DbTraceHandler(void *cd, const char *zSql){
  SqliteDb *pDb = (SqliteDb*)cd;
  Tcl_DString str;
................................................................................
  Tcl_DStringInit(&str);
  Tcl_DStringAppend(&str, pDb->zTrace, -1);
  Tcl_DStringAppendElement(&str, zSql);
  Tcl_Eval(pDb->interp, Tcl_DStringValue(&str));
  Tcl_DStringFree(&str);
  Tcl_ResetResult(pDb->interp);
}



/*
** This routine is called by the SQLite profile handler after a statement
** SQL has executed.  The TCL script in pDb->zProfile is evaluated.
*/
static void DbProfileHandler(void *cd, const char *zSql, sqlite_uint64 tm){
  SqliteDb *pDb = (SqliteDb*)cd;
  Tcl_DString str;
................................................................................
  Tcl_DStringAppend(&str, pDb->zProfile, -1);
  Tcl_DStringAppendElement(&str, zSql);
  Tcl_DStringAppendElement(&str, zTm);
  Tcl_Eval(pDb->interp, Tcl_DStringValue(&str));
  Tcl_DStringFree(&str);
  Tcl_ResetResult(pDb->interp);
}


/*
** This routine is called when a transaction is committed.  The
** TCL script in pDb->zCommit is executed.  If it returns non-zero or
** if it throws an exception, the transaction is rolled back instead
** of being committed.
*/

**    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.
**
*************************************************************************
** A TCL Interface to SQLite
**
** $Id: tclsqlite.c,v 1.150 2006/01/23 13:00:38 drh Exp $
*/
#ifndef NO_TCL     /* Omit this whole file if TCL is unavailable */

#include "sqliteInt.h"
#include "hash.h"
#include "tcl.h"
#include <stdlib.h>
................................................................................
  rc = Tcl_Eval(pDb->interp, pDb->zProgress);
  if( rc!=TCL_OK || atoi(Tcl_GetStringResult(pDb->interp)) ){
    return 1;
  }
  return 0;
}

#ifndef SQLITE_OMIT_TRACE
/*
** This routine is called by the SQLite trace handler whenever a new
** block of SQL is executed.  The TCL script in pDb->zTrace is executed.
*/
static void DbTraceHandler(void *cd, const char *zSql){
  SqliteDb *pDb = (SqliteDb*)cd;
  Tcl_DString str;
................................................................................
  Tcl_DStringInit(&str);
  Tcl_DStringAppend(&str, pDb->zTrace, -1);
  Tcl_DStringAppendElement(&str, zSql);
  Tcl_Eval(pDb->interp, Tcl_DStringValue(&str));
  Tcl_DStringFree(&str);
  Tcl_ResetResult(pDb->interp);
}
#endif

#ifndef SQLITE_OMIT_TRACE
/*
** This routine is called by the SQLite profile handler after a statement
** SQL has executed.  The TCL script in pDb->zProfile is evaluated.
*/
static void DbProfileHandler(void *cd, const char *zSql, sqlite_uint64 tm){
  SqliteDb *pDb = (SqliteDb*)cd;
  Tcl_DString str;
................................................................................
  Tcl_DStringAppend(&str, pDb->zProfile, -1);
  Tcl_DStringAppendElement(&str, zSql);
  Tcl_DStringAppendElement(&str, zTm);
  Tcl_Eval(pDb->interp, Tcl_DStringValue(&str));
  Tcl_DStringFree(&str);
  Tcl_ResetResult(pDb->interp);
}
#endif

/*
** This routine is called when a transaction is committed.  The
** TCL script in pDb->zCommit is executed.  If it returns non-zero or
** if it throws an exception, the transaction is rolled back instead
** of being committed.
*/

**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.180 2006/01/20 17:56:33 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <stdarg.h>
#include <ctype.h>

/*
................................................................................
** Allocate and return N bytes of uninitialised memory by calling
** sqlite3OsMalloc(). If the Malloc() call fails, attempt to free memory 
** by calling sqlite3_release_memory().
*/
void *sqlite3MallocRaw(int n){
  void *p = 0;
  if( n>0 && !sqlite3MallocFailed() && !handleSoftLimit(n) ){
    while( !(p = OSMALLOC(n)) && sqlite3_release_memory(n) );
    if( !p ){
      /* If the allocation failed, call handleSoftLimit() again, this time
      ** with the additive inverse of the argument passed to 
      ** handleSoftLimit() above. This is so the ThreadData.nAlloc variable is
      ** still correct after a malloc() failure. 
      */
      (void)handleSoftLimit(n * -1);
................................................................................
  }

  if( !p ){
    return sqlite3Malloc(n);
  }else{
    void *np = 0;
    if( !handleSoftLimit(n - OSSIZEOF(p)) ){
      while( !(np = OSREALLOC(p, n)) && sqlite3_release_memory(n) );
      if( !np ){
        /* If the allocation failed, call handleSoftLimit() again, this time
        ** with the additive inverse of the argument passed to 
        ** handleSoftLimit() above. This is so the ThreadData.nAlloc variable is
        ** still correct after a malloc() failure. 
        */
        (void)handleSoftLimit(OSSIZEOF(p) - n);
................................................................................
** encoded in UTF-8.
**
** To clear the most recent error for sqlite handle "db", sqlite3Error
** should be called with err_code set to SQLITE_OK and zFormat set
** to NULL.
*/
void sqlite3Error(sqlite3 *db, int err_code, const char *zFormat, ...){
  if( db && (db->pErr || (db->pErr = sqlite3ValueNew()))!=0 ){
    db->errCode = err_code;
    if( zFormat ){
      char *z;
      va_list ap;
      va_start(ap, zFormat);
      z = sqlite3VMPrintf(zFormat, ap);
      va_end(ap);
................................................................................

/*
** Return a pointer to the ThreadData associated with the calling thread.
** If no ThreadData has been allocated to this thread yet, return a pointer
** to a substitute ThreadData structure that is all zeros. 
*/
const ThreadData *sqlite3ThreadDataReadOnly(){
  static const ThreadData zeroData;

  const ThreadData *pTd = sqlite3OsThreadSpecificData(0);
  return pTd ? pTd : &zeroData;
}

/*
** Check to see if the ThreadData for this thread is all zero.  If it
** is, then deallocate it. 

**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.181 2006/01/23 13:00:38 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <stdarg.h>
#include <ctype.h>

/*
................................................................................
** Allocate and return N bytes of uninitialised memory by calling
** sqlite3OsMalloc(). If the Malloc() call fails, attempt to free memory 
** by calling sqlite3_release_memory().
*/
void *sqlite3MallocRaw(int n){
  void *p = 0;
  if( n>0 && !sqlite3MallocFailed() && !handleSoftLimit(n) ){
    while( (p = OSMALLOC(n))==0 && sqlite3_release_memory(n) );
    if( !p ){
      /* If the allocation failed, call handleSoftLimit() again, this time
      ** with the additive inverse of the argument passed to 
      ** handleSoftLimit() above. This is so the ThreadData.nAlloc variable is
      ** still correct after a malloc() failure. 
      */
      (void)handleSoftLimit(n * -1);
................................................................................
  }

  if( !p ){
    return sqlite3Malloc(n);
  }else{
    void *np = 0;
    if( !handleSoftLimit(n - OSSIZEOF(p)) ){
      while( (np = OSREALLOC(p, n))==0 && sqlite3_release_memory(n) );
      if( !np ){
        /* If the allocation failed, call handleSoftLimit() again, this time
        ** with the additive inverse of the argument passed to 
        ** handleSoftLimit() above. This is so the ThreadData.nAlloc variable is
        ** still correct after a malloc() failure. 
        */
        (void)handleSoftLimit(OSSIZEOF(p) - n);
................................................................................
** encoded in UTF-8.
**
** To clear the most recent error for sqlite handle "db", sqlite3Error
** should be called with err_code set to SQLITE_OK and zFormat set
** to NULL.
*/
void sqlite3Error(sqlite3 *db, int err_code, const char *zFormat, ...){
  if( db && (db->pErr || (db->pErr = sqlite3ValueNew())!=0) ){
    db->errCode = err_code;
    if( zFormat ){
      char *z;
      va_list ap;
      va_start(ap, zFormat);
      z = sqlite3VMPrintf(zFormat, ap);
      va_end(ap);
................................................................................

/*
** Return a pointer to the ThreadData associated with the calling thread.
** If no ThreadData has been allocated to this thread yet, return a pointer
** to a substitute ThreadData structure that is all zeros. 
*/
const ThreadData *sqlite3ThreadDataReadOnly(){
  static const ThreadData zeroData = {0};  /* Initializer to silence warnings
                                           ** from broken compilers */
  const ThreadData *pTd = sqlite3OsThreadSpecificData(0);
  return pTd ? pTd : &zeroData;
}

/*
** Check to see if the ThreadData for this thread is all zero.  If it
** is, then deallocate it. 

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible 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.200 2006/01/20 18:10:57 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
int sqlite3_where_trace = 0;
# define TRACE(X)  if(sqlite3_where_trace) sqlite3DebugPrintf X
#else
# define TRACE(X)
#endif

/*
** A large value which is the maximum cost of using an index.
** By default this is a large floating point value.  When compiling
** SQLite for a processor that lacks floating point support, simply
** redefine this constant to a large integer.
*/
#ifndef SQLITE_BIG_DBL
# define SQLITE_BIG_DBL (1.0e+99)
#endif

/* Forward reference
*/
typedef struct WhereClause WhereClause;

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible 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.201 2006/01/23 13:00:38 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
int sqlite3_where_trace = 0;
# define TRACE(X)  if(sqlite3_where_trace) sqlite3DebugPrintf X
#else
# define TRACE(X)
#endif











/* Forward reference
*/
typedef struct WhereClause WhereClause;

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE