ENCODING = @ENCODING@

# You should not have to change anything below this line
###############################################################################

# Object files for the SQLite library.
#
LIBOBJ = btree.o build.o delete.o expr.o insert.o \
         main.o os.o pager.o parse.o printf.o random.o select.o table.o \
         tokenize.o update.o util.o vdbe.o where.o tclsqlite.o

# All of the source code files.
#
SRC = \
  $(TOP)/src/btree.c \
  $(TOP)/src/btree.h \
  $(TOP)/src/build.c \
  $(TOP)/src/delete.c \
  $(TOP)/src/expr.c \

  $(TOP)/src/insert.c \
  $(TOP)/src/main.c \
  $(TOP)/src/os.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pager.h \
  $(TOP)/src/parse.y \
  $(TOP)/src/printf.c \
................................................................................
	$(TCC) -c $(TOP)/src/where.c

delete.o:	$(TOP)/src/delete.c $(HDR)
	$(TCC) -c $(TOP)/src/delete.c

expr.o:	$(TOP)/src/expr.c $(HDR)
	$(TCC) -c $(TOP)/src/expr.c




insert.o:	$(TOP)/src/insert.c $(HDR)
	$(TCC) -c $(TOP)/src/insert.c

random.o:	$(TOP)/src/random.c $(HDR)
	$(TCC) -c $(TOP)/src/random.c

ENCODING = @ENCODING@

# You should not have to change anything below this line
###############################################################################

# Object files for the SQLite library.
#
LIBOBJ = btree.o build.o delete.o expr.o hash.o insert.o \
         main.o os.o pager.o parse.o printf.o random.o select.o table.o \
         tokenize.o update.o util.o vdbe.o where.o tclsqlite.o

# All of the source code files.
#
SRC = \
  $(TOP)/src/btree.c \
  $(TOP)/src/btree.h \
  $(TOP)/src/build.c \
  $(TOP)/src/delete.c \
  $(TOP)/src/expr.c \
  $(TOP)/src/hash.c \
  $(TOP)/src/insert.c \
  $(TOP)/src/main.c \
  $(TOP)/src/os.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pager.h \
  $(TOP)/src/parse.y \
  $(TOP)/src/printf.c \
................................................................................
	$(TCC) -c $(TOP)/src/where.c

delete.o:	$(TOP)/src/delete.c $(HDR)
	$(TCC) -c $(TOP)/src/delete.c

expr.o:	$(TOP)/src/expr.c $(HDR)
	$(TCC) -c $(TOP)/src/expr.c

hash.o:	$(TOP)/src/hash.c $(HDR)
	$(TCC) -c $(TOP)/src/hash.c

insert.o:	$(TOP)/src/insert.c $(HDR)
	$(TCC) -c $(TOP)/src/insert.c

random.o:	$(TOP)/src/random.c $(HDR)
	$(TCC) -c $(TOP)/src/random.c

**     COPY
**     VACUUM
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**     PRAGMA
**
** $Id: build.c,v 1.37 2001/09/17 20:25:58 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 
................................................................................

/*
** Locate the in-memory structure that describes the
** format of a particular database table given the name
** of that table.  Return NULL if not found.
*/
Table *sqliteFindTable(sqlite *db, char *zName){
  Table *pTable;
  int h;

  h = sqliteHashNoCase(zName, 0) % N_HASH;
  for(pTable=db->apTblHash[h]; pTable; pTable=pTable->pHash){
    if( sqliteStrICmp(pTable->zName, zName)==0 ) return pTable;
  }
  return 0;
}

/*
** Locate the in-memory structure that describes the
** format of a particular index given the name
** of that index.  Return NULL if not found.
*/
Index *sqliteFindIndex(sqlite *db, char *zName){
  Index *p;
  int h;

  h = sqliteHashNoCase(zName, 0) % N_HASH;
  for(p=db->apIdxHash[h]; p; p=p->pHash){
    if( sqliteStrICmp(p->zName, zName)==0 ) return p;
  }
  return 0;
}

/*
** Remove the given index from the index hash table, and free
** its memory structures.
**
** The index is removed from the database hash table if db!=NULL.
** But it is not unlinked from the Table that is being indexed.  
** Unlinking from the Table must be done by the calling function.
*/
static void sqliteDeleteIndex(sqlite *db, Index *pIndex){
  int h;
  if( pIndex->zName && db ){
    h = sqliteHashNoCase(pIndex->zName, 0) % N_HASH;
    if( db->apIdxHash[h]==pIndex ){
      db->apIdxHash[h] = pIndex->pHash;
    }else{
      Index *p;
      for(p=db->apIdxHash[h]; p && p->pHash!=pIndex; p=p->pHash){}
      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{
................................................................................

/*
** Unlink the given table from the hash tables and the delete the
** table structure and all its indices.
*/
static void sqliteUnlinkAndDeleteTable(sqlite *db, Table *pTable){
  if( pTable->zName && db ){
    int h = sqliteHashNoCase(pTable->zName, 0) % N_HASH;
    if( db->apTblHash[h]==pTable ){
      db->apTblHash[h] = pTable->pHash;
    }else{
      Table *p;
      for(p=db->apTblHash[h]; p && p->pHash!=pTable; p=p->pHash){}
      if( p && p->pHash==pTable ){
        p->pHash = pTable->pHash;
      }
    }
  }
  sqliteDeleteTable(db, pTable);
}

/*
** Check all Tables and Indexes in the internal hash table and commit
** any additions or deletions to those hash tables.
................................................................................
** 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;

  db->schema_cookie = db->next_cookie;
  for(i=0; i<N_HASH; i++){

    Table *pTable, *pNext;
    for(pTable = db->apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( pTable->isDelete ){
        sqliteUnlinkAndDeleteTable(db, pTable);
      }else if( pTable->isCommit==0 ){
        pTable->isCommit = 1;
      }
    }



  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = db->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;

  db->next_cookie = db->schema_cookie;
  for(i=0; i<N_HASH; i++){

    Table *pTable, *pNext;
    for(pTable = db->apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( !pTable->isCommit ){
        sqliteUnlinkAndDeleteTable(db, pTable);
      }else if( pTable->isDelete ){
        pTable->isDelete = 0;
      }
    }



  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = db->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
................................................................................
    sqliteFree(zName);
    pParse->nErr++;
    return;
  }
  pTable = sqliteMalloc( sizeof(Table) );
  if( pTable==0 ) return;
  pTable->zName = zName;
  pTable->pHash = 0;
  pTable->nCol = 0;
  pTable->aCol = 0;
  pTable->pIndex = 0;
  if( pParse->pNewTable ) sqliteDeleteTable(db, pParse->pNewTable);
  pParse->pNewTable = pTable;
  if( !pParse->initFlag && (db->flags & SQLITE_InTrans)==0 ){
    Vdbe *v = sqliteGetVdbe(pParse);
................................................................................
** unless initFlag==1.  When initFlag==1, it means we are reading
** 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;
  sqlite *db = pParse->db;

  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 = db->apTblHash[h];
    db->apTblHash[h] = p;
    pParse->pNewTable = 0;
    db->nTable++;
    db->flags |= SQLITE_InternChanges;
  }

  /* If the initFlag is 1 it means we are reading the SQL off the
  ** "sqlite_master" table on the disk.  So do not write to the disk
................................................................................
  IdList *pList,   /* A list of columns to be indexed */
  Token *pStart,   /* The CREATE token that begins a CREATE TABLE statement */
  Token *pEnd      /* The ")" that closes the CREATE INDEX statement */
){
  Table *pTab;     /* Table to be indexed */
  Index *pIndex;   /* The index to be created */
  char *zName = 0;
  int i, j, h;
  Token nullId;    /* Fake token for an empty ID list */
  sqlite *db = pParse->db;

  if( pParse->nErr || sqlite_malloc_failed ) goto exit_create_index;

  /*
  ** Find the table that is to be indexed.  Return early if not found.
................................................................................

  /* Link the new Index structure to its table and to the other
  ** in-memory database structures.  Note that primary key indices
  ** do not appear in the index hash table.
  */
  if( pParse->explain==0 ){
    if( pName!=0 ){
      h = sqliteHashNoCase(pIndex->zName, 0) % N_HASH;
      pIndex->pHash = db->apIdxHash[h];
      db->apIdxHash[h] = pIndex;
    }
    pIndex->pNext = pTab->pIndex;
    pTab->pIndex = pIndex;
    db->flags |= SQLITE_InternChanges;
  }

  /* If the initFlag is 1 it means we are reading the SQL off the
................................................................................
  if( (db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_VerifyCookie, db->schema_cookie, 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=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( (db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
  }

**     COPY
**     VACUUM
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**     PRAGMA
**
** $Id: build.c,v 1.38 2001/09/22 18:12:10 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 
................................................................................

/*
** Locate the in-memory structure that describes the
** format of a particular database table given the name
** of that table.  Return NULL if not found.
*/
Table *sqliteFindTable(sqlite *db, char *zName){
  return sqliteHashFind(&db->tblHash, zName, strlen(zName)+1);







}

/*
** Locate the in-memory structure that describes the
** format of a particular index given the name
** of that index.  Return NULL if not found.
*/
Index *sqliteFindIndex(sqlite *db, char *zName){
  return sqliteHashFind(&db->idxHash, zName, strlen(zName)+1);







}

/*
** Remove the given index from the index hash table, and free
** its memory structures.
**
** The index is removed from the database hash table if db!=NULL.
** But it is not unlinked from the Table that is being indexed.  
** Unlinking from the Table must be done by the calling function.
*/
static void sqliteDeleteIndex(sqlite *db, Index *pIndex){

  if( pIndex->zName && db ){










    sqliteHashInsert(&db->idxHash, pIndex->zName, strlen(pIndex->zName)+1, 0);
  }
  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{
................................................................................

/*
** Unlink the given table from the hash tables and the delete the
** table structure and all its indices.
*/
static void sqliteUnlinkAndDeleteTable(sqlite *db, Table *pTable){
  if( pTable->zName && db ){
    sqliteHashInsert(&db->tblHash, pTable->zName, strlen(pTable->zName)+1, 0);









  }
  sqliteDeleteTable(db, pTable);
}

/*
** Check all Tables and Indexes in the internal hash table and commit
** any additions or deletions to those hash tables.
................................................................................
** 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){
  Hash toDelete;
  HashElem *pElem;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  sqliteHashInit(&toDelete, SQLITE_HASH_POINTER, 0);
  db->schema_cookie = db->next_cookie;

  for(pElem=sqliteHashFirst(&db->tblHash); pElem; pElem=sqliteHashNext(pElem)){
    Table *pTable = sqliteHashData(pElem);


    if( pTable->isDelete ){
      sqliteHashInsert(&toDelete, pTable, 0, pTable);
    }else{
      pTable->isCommit = 1;
    }
  }
  for(pElem=sqliteHashFirst(&toDelete); pElem; pElem=sqliteHashNext(pElem)){
    Table *pTable = sqliteHashData(pElem);
    sqliteUnlinkAndDeleteTable(db, pTable);
  }



  sqliteHashClear(&toDelete);
  for(pElem=sqliteHashFirst(&db->idxHash); pElem; pElem=sqliteHashNext(pElem)){
    Table *pIndex = sqliteHashData(pElem);
    if( pIndex->isDelete ){


      sqliteHashInsert(&toDelete, pIndex, 0, pIndex);
    }else{
      pIndex->isCommit = 1;
    }
  }
  for(pElem=sqliteHashFirst(&toDelete); pElem; pElem=sqliteHashNext(pElem)){
    Index *pIndex = sqliteHashData(pElem);
    sqliteUnlinkAndDeleteIndex(db, pIndex);
  }
  sqliteHashClear(&toDelete);
  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){
  Hash toDelete;
  HashElem *pElem;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  sqliteHashInit(&toDelete, SQLITE_HASH_POINTER, 0);
  db->next_cookie = db->schema_cookie;

  for(pElem=sqliteHashFirst(&db->tblHash); pElem; pElem=sqliteHashNext(pElem)){
    Table *pTable = sqliteHashData(pElem);


    if( !pTable->isCommit ){
      sqliteHashInsert(&toDelete, pTable, 0, pTable);
    }else{
      pTable->isDelete = 0;
    }
  }
  for(pElem=sqliteHashFirst(&toDelete); pElem; pElem=sqliteHashNext(pElem)){
    Table *pTable = sqliteHashData(pElem);
    sqliteUnlinkAndDeleteTable(db, pTable);
  }



  sqliteHashClear(&toDelete);
  for(pElem=sqliteHashFirst(&db->idxHash); pElem; pElem=sqliteHashNext(pElem)){
    Table *pIndex = sqliteHashData(pElem);
    if( !pIndex->isCommit ){


      sqliteHashInsert(&toDelete, pIndex, 0, pIndex);
    }else{
      pIndex->isDelete = 0;
    }
  }
  for(pElem=sqliteHashFirst(&toDelete); pElem; pElem=sqliteHashNext(pElem)){
    Index *pIndex = sqliteHashData(pElem);
    sqliteUnlinkAndDeleteIndex(db, pIndex);
  }
  sqliteHashClear(&toDelete);
  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
................................................................................
    sqliteFree(zName);
    pParse->nErr++;
    return;
  }
  pTable = sqliteMalloc( sizeof(Table) );
  if( pTable==0 ) return;
  pTable->zName = zName;

  pTable->nCol = 0;
  pTable->aCol = 0;
  pTable->pIndex = 0;
  if( pParse->pNewTable ) sqliteDeleteTable(db, pParse->pNewTable);
  pParse->pNewTable = pTable;
  if( !pParse->initFlag && (db->flags & SQLITE_InTrans)==0 ){
    Vdbe *v = sqliteGetVdbe(pParse);
................................................................................
** unless initFlag==1.  When initFlag==1, it means we are reading
** 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;

  sqlite *db = pParse->db;

  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 ){
    sqliteHashInsert(&db->tblHash, p->zName, strlen(p->zName)+1, p);


    pParse->pNewTable = 0;
    db->nTable++;
    db->flags |= SQLITE_InternChanges;
  }

  /* If the initFlag is 1 it means we are reading the SQL off the
  ** "sqlite_master" table on the disk.  So do not write to the disk
................................................................................
  IdList *pList,   /* A list of columns to be indexed */
  Token *pStart,   /* The CREATE token that begins a CREATE TABLE statement */
  Token *pEnd      /* The ")" that closes the CREATE INDEX statement */
){
  Table *pTab;     /* Table to be indexed */
  Index *pIndex;   /* The index to be created */
  char *zName = 0;
  int i, j;
  Token nullId;    /* Fake token for an empty ID list */
  sqlite *db = pParse->db;

  if( pParse->nErr || sqlite_malloc_failed ) goto exit_create_index;

  /*
  ** Find the table that is to be indexed.  Return early if not found.
................................................................................

  /* Link the new Index structure to its table and to the other
  ** in-memory database structures.  Note that primary key indices
  ** do not appear in the index hash table.
  */
  if( pParse->explain==0 ){
    if( pName!=0 ){
      char *zName = pIndex->zName;;
      sqliteHashInsert(&db->idxHash, zName, strlen(zName)+1, pIndex);

    }
    pIndex->pNext = pTab->pIndex;
    pTab->pIndex = pIndex;
    db->flags |= SQLITE_InternChanges;
  }

  /* If the initFlag is 1 it means we are reading the SQL off the
................................................................................
  if( (db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_VerifyCookie, db->schema_cookie, 0, 0, 0);
  }
  if( zName ){
    sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, zName, 0);
  }else{

    Table *pTab;
    Index *pIdx;
    HashElem *pE;
    for(pE=sqliteHashFirst(&db->tblHash); pE; pE=sqliteHashNext(pE)){
      pTab = sqliteHashData(pE);
      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( (db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
  }

/*
** 2001 September 22
**
** 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 is the implementation of generic hash-tables
** used in SQLite.
**
** $Id: hash.c,v 1.1 2001/09/22 18:12:10 drh Exp $
*/
#include "sqliteInt.h"
#include <assert.h>

/* Turn bulk memory into a hash table object by initializing the
** fields of the Hash structure.
*/
void sqliteHashInit(Hash *new, int keyClass, int copyKey){
  assert( new!=0 );
  assert( keyClass>=SQLITE_HASH_INT && keyClass<=SQLITE_HASH_BINARY );
  new->keyClass = keyClass;
  new->copyKey = copyKey &&
                (keyClass==SQLITE_HASH_STRING || keyClass==SQLITE_HASH_BINARY);
  new->first = 0;
  new->count = 0;
  new->htsize = 0;
  new->ht = 0;
}

/* Remove all entries from a hash table.  Reclaim all memory.
*/
void sqliteHashClear(Hash *pH){
  HashElem *elem;         /* For looping over all elements of the table */

  assert( pH!=0 );
  elem = pH->first;
  pH->first = 0;
  if( pH->ht ) sqliteFree(pH->ht);
  pH->ht = 0;
  pH->htsize = 0;
  while( elem ){
    HashElem *next_elem = elem->next;
    if( pH->copyKey && elem->pKey ){
      sqliteFree(elem->pKey);
    }
    sqliteFree(elem);
    elem = next_elem;
  }
  pH->count = 0;
}

/*
** Hash and comparison functions when the mode is SQLITE_HASH_INT
*/
static int intHash(const void *pKey, int nKey){
  return nKey ^ (nKey<<8) ^ (nKey>>8);
}
static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  return n2 - n1;
}

/*
** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
*/
static int ptrHash(const void *pKey, int nKey){
  nKey = (int)pKey;
  return nKey ^ (nKey<<8) ^ (nKey>>8);
}
static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  return ((int)pKey2) - (int)pKey1;
}

/*
** Hash and comparison functions when the mode is SQLITE_HASH_STRING
*/
static int strHash(const void *pKey, int nKey){
  return sqliteHashNoCase((const char*)pKey, nKey); 
}
static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  if( n1!=n2 ) return n2-n1;
  return sqliteStrNICmp((const char*)pKey1,(const char*)pKey2,n1);
}

/*
** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
*/
static int binHash(const void *pKey, int nKey){
  int h = 0;
  const char *z = (const char *)pKey;
  while( nKey-- > 0 ){
    h = (h<<3) ^ h ^ *(z++);
  }
  if( h<0 ) h = -h;
  return h;
}
static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  if( n1!=n2 ) return n2-n1;
  return memcmp(pKey1,pKey2,n1);
}

/*
** Return a pointer to the appropriate hash function given the key class.
*/
static int (*hashFunction(int keyClass))(const void*,int){
  switch( keyClass ){
    case SQLITE_HASH_INT:     return intHash;
    case SQLITE_HASH_POINTER: return ptrHash;
    case SQLITE_HASH_STRING:  return strHash;
    case SQLITE_HASH_BINARY:  return binHash;;
    default: break;
  }
  return 0;
}

/*
** Return a pointer to the appropriate hash function given the key class.
*/
static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
  switch( keyClass ){
    case SQLITE_HASH_INT:     return intCompare;
    case SQLITE_HASH_POINTER: return ptrCompare;
    case SQLITE_HASH_STRING:  return strCompare;
    case SQLITE_HASH_BINARY:  return binCompare;
    default: break;
  }
  return 0;
}


/* Resize the hash table. new_size must be a power of 2.
** The hash table might fail to resize if sqliteMalloc() fails.
*/
static void rehash(Hash *pH, int new_size){
  struct _ht *new_ht;            /* The new hash table */
  HashElem *elem, *next_elem;    /* For looping over existing elements */
  HashElem *x;                   /* Element being copied to new hash table */
  int (*xHash)(const void*,int); /* The hash function */

  assert( (new_size & (new_size-1))==0 );
  new_ht = (struct _ht *)sqliteMalloc( new_size*sizeof(struct _ht) );
  if( new_ht==0 ) return;
  if( pH->ht ) sqliteFree(pH->ht);
  pH->ht = new_ht;
  pH->htsize = new_size;
  xHash = hashFunction(pH->keyClass);
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
    next_elem = elem->next;
    x = new_ht[h].chain;
    if( x ){
      elem->next = x;
      elem->prev = x->prev;
      if( x->prev ) x->prev->next = elem;
      else          pH->first = elem;
      x->prev = elem;
    }else{
      elem->next = pH->first;
      if( pH->first ) pH->first->prev = elem;
      elem->prev = 0;
      pH->first = elem;
    }
    new_ht[h].chain = elem;
    new_ht[h].count++;
  }
}

/* This function (for internal use only) locates an element in an
** pH that matches the given key.  The hash for this key has
** already been computed and is passed as the 3rd parameter.
*/
static HashElem *findElementGivenHash(
  const Hash *pH,     /* The pH to be searched */
  const void *pKey,   /* The key we are searching for */
  int nKey,
  int h               /* The hash for this key. */
){
  HashElem *elem;                /* Used to loop thru the element list */
  int count;                     /* Number of elements left to test */
  int (*xCompare)(const void*,int,const void*,int);  /* comparison function */

  if( pH->ht ){
    elem = pH->ht[h].chain;
    count = pH->ht[h].count;
    xCompare = compareFunction(pH->keyClass);
    while( count-- && elem ){
      if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 
        return elem;
      }
      elem = elem->next;
    }
  }
  return 0;
}

/* Remove a single entry from the pH given a pointer to that
** element and a hash on the element's key.
*/
static void removeElementGivenHash(
  Hash *pH,         /* The pH containing "elem" */
  HashElem* elem,   /* The element to be removed from the pH */
  int h              /* Hash value for the element */
){
  if( elem->prev ){
    elem->prev->next = elem->next; 
  }else{
    pH->first = elem->next;
  }
  if( elem->next ){
    elem->next->prev = elem->prev;
  }
  if( pH->ht[h].chain==elem ){
    pH->ht[h].chain = elem->next;
  }
  pH->ht[h].count--;
  if( pH->ht[h].count<=0 ){
    pH->ht[h].chain = 0;
  }
  if( pH->copyKey && elem->pKey ){
    sqliteFree(elem->pKey);
  }
  sqliteFree( elem );
  pH->count--;
}

/* Attempt to locate an element of the associative pH with a key
** that matches "key".  Return the data for this element if it is
** found, or NULL if no match is found.
*/
void *sqliteHashFind(const Hash *pH, const void *pKey, int nKey){
  int h;             /* A hash on key */
  HashElem *elem;    /* The element that matches key */
  int (*xHash)(const void*,int);  /* The hash function */

  if( pH==0 || pH->ht==0 ) return 0;
  xHash = hashFunction(pH->keyClass);
  assert( xHash!=0 );
  h = (*xHash)(pKey,nKey);
  assert( (pH->htsize & (pH->htsize-1))==0 );
  elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
  return elem ? elem->data : 0;
}

/* Insert an element into the pH.  The key will be "key" and
** the data will be "data".
**
** If no pH element exists with a matching key, then a new
** pH element is created.  The key is copied (using the copy
** function of the key class) into the new element.  NULL is returned.
**
** If another element already exists with the same key, then the
** new data replaces the old data and the old data is returned.
** The key is not copied in this instance.
**
** If the "data" parameter to this function is NULL, then the
** element corresponding to "key" is removed from the pH.
*/
void *sqliteHashInsert(Hash *pH, void *pKey, int nKey, void *data){
  int hraw;             /* Raw hash value of the key */
  int h;                /* the hash of the key modulo hash table size */
  HashElem *elem;       /* Used to loop thru the element list */
  HashElem *new_elem;   /* New element added to the pH */
  int (*xHash)(const void*,int);  /* The hash function */

  assert( pH!=0 );
  xHash = hashFunction(pH->keyClass);
  assert( xHash!=0 );
  hraw = (*xHash)(pKey, nKey);
  assert( (pH->htsize & (pH->htsize-1))==0 );
  h = hraw & (pH->htsize-1);
  elem = findElementGivenHash(pH,pKey,nKey,h);
  if( elem ){
    void *old_data = elem->data;
    if( data==0 ){
      removeElementGivenHash(pH,elem,h);
    }else{
      elem->data = data;
    }
    return old_data;
  }
  if( data==0 ) return 0;
  new_elem = (HashElem*)sqliteMalloc( sizeof(HashElem) );
  if( new_elem==0 ) return 0;
  if( pH->copyKey && pKey!=0 ){
    new_elem->pKey = sqliteMalloc( nKey );
    if( new_elem->pKey==0 ){
      sqliteFree(new_elem);
      return 0;
    }
    memcpy((void*)new_elem->pKey, pKey, nKey);
  }else{
    new_elem->pKey = pKey;
  }
  new_elem->nKey = nKey;
  pH->count++;
  if( pH->htsize==0 ) rehash(pH,8);
  if( pH->htsize==0 ){
    pH->count = 0;
    sqliteFree(new_elem);
    return 0;
  }
  if( pH->count > pH->htsize ){
    rehash(pH,pH->htsize*2);
  }
  assert( (pH->htsize & (pH->htsize-1))==0 );
  h = hraw & (pH->htsize-1);
  elem = pH->ht[h].chain;
  if( elem ){
    new_elem->next = elem;
    new_elem->prev = elem->prev;
    if( elem->prev ){ elem->prev->next = new_elem; }
    else            { pH->first = new_elem; }
    elem->prev = new_elem;
  }else{
    new_elem->next = pH->first;
    new_elem->prev = 0;
    if( pH->first ){ pH->first->prev = new_elem; }
    pH->first = new_elem;
  }
  pH->ht[h].count++;
  pH->ht[h].chain = new_elem;
  new_elem->data = data;
  return 0;
}

/*
** 2001 September 22
**
** 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 is the header file for the generic hash-table implemenation
** used in SQLite.
**
** $Id: hash.h,v 1.1 2001/09/22 18:12:10 drh Exp $
*/
#ifndef _SQLITE_HASH_H_
#define _SQLITE_HASH_H_

/* Forward declarations of structures. */
typedef struct Hash Hash;
typedef struct HashElem HashElem;

/* A complete hash table is an instance of the following structure.
** The internals of this structure are intended to be opaque -- client
** code should not attempt to access or modify the fields of this structure
** directly.  Change this structure only by using the routines below.
** However, many of the "procedures" and "functions" for modifying and
** accessing this structure are really macros, so we can't really make
** this structure opaque.
*/
struct Hash {
  char keyClass;          /* SQLITE_HASH_INT, ..._STRING, or _BINARY */
  char copyKey;           /* True if copy of key made on insert */
  int count;              /* Number of entries in this table */
  HashElem *first;        /* The first element of the array */
  int htsize;             /* Number of buckets in the hash table */
  struct _ht {            /* the hash table */
    int count;               /* Number of entries with this hash */
    HashElem *chain;         /* Pointer to first entry with this hash */
  } *ht;
};

/* Each element in the hash table is an instance of the following 
** structure.  All elements are stored on a single doubly-linked list.
**
** Again, this structure is intended to be opaque, but it can't really
** be opaque because it is used by macros.
*/
struct HashElem {
  HashElem *next, *prev;   /* Next and previous elements in the table */
  void *data;              /* Data associated with this element */
  void *pKey; int nKey;    /* Key associated with this element */
};

/*
** There are 4 different modes of operation for a hash table:
**
**   SQLITE_HASH_INT         nKey is used as the key and pKey is ignored.
**
**   SQLITE_HASH_POINTER     pKey is used as the key and nKey is ignored.
**
**   SQLITE_HASH_STRING      pKey points to a string that is nKey bytes long
**                           (including the null-terminator, if any).  Case
**                           is ignored in comparisons.
**
**   SQLITE_HASH_BINARY      pKey points to binary data nKey bytes long. 
**                           memcmp() is used to compare keys.
**
** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY
** if the copyKey parameter to HashInit is 1.  
*/
#define SQLITE_HASH_INT       1
#define SQLITE_HASH_POINTER   2
#define SQLITE_HASH_STRING    3
#define SQLITE_HASH_BINARY    4

/*
** Access routines.  To delete, insert a NULL pointer.
*/
void sqliteHashInit(Hash*, int keytype, int copyKey);
void *sqliteHashInsert(Hash*, void *pKey, int nKey, void *pData);
void *sqliteHashFind(const Hash*, const void *pKey, int nKey);
void sqliteHashClear(Hash*);

/*
** Macros for looping over all elements of a hash table.  The idiom is
** like this:
**
**   Hash h;
**   HashElem *p;
**   ...
**   for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){
**     SomeStructure *pData = sqliteHashData(p);
**     // do something with pData
**   }
*/
#define sqliteHashFirst(H)  ((H)->first)
#define sqliteHashNext(E)   ((E)->next)
#define sqliteHashData(E)   ((E)->data)

#endif /* _SQLITE_HASH_H_ */

**
*************************************************************************
** 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.39 2001/09/19 13:22:40 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"

/*
** This is the callback routine for the code that initializes the
** database.  Each callback contains the following information:
................................................................................
  sqlite *db;
  int rc;

  /* 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, MAX_PAGES, &db->pBe);
  if( rc!=SQLITE_OK ){
    switch( rc ){
      default: {
        if( pzErrMsg ){
................................................................................
** The database schema is normally read in once when the database
** is first opened and stored in a hash table in the sqlite structure.
** This routine erases the stored schema.  This erasure occurs because
** either the database is being closed or because some other process
** changed the schema and this process needs to reread it.
*/
static void clearHashTable(sqlite *db){
  int i;
  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);
      pList = pNext;
    }
  }

  db->flags &= ~SQLITE_Initialized;
}

/*
** Close an existing SQLite database
*/
void sqlite_close(sqlite *db){

**
*************************************************************************
** 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.40 2001/09/22 18:12:10 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"

/*
** This is the callback routine for the code that initializes the
** database.  Each callback contains the following information:
................................................................................
  sqlite *db;
  int rc;

  /* Allocate the sqlite data structure */
  db = sqliteMalloc( sizeof(sqlite) );
  if( pzErrMsg ) *pzErrMsg = 0;
  if( db==0 ) goto no_mem_on_open;
  sqliteHashInit(&db->tblHash, SQLITE_HASH_STRING, 0);
  sqliteHashInit(&db->idxHash, SQLITE_HASH_STRING, 0);
  
  /* Open the backend database driver */
  rc = sqliteBtreeOpen(zFilename, mode, MAX_PAGES, &db->pBe);
  if( rc!=SQLITE_OK ){
    switch( rc ){
      default: {
        if( pzErrMsg ){
................................................................................
** The database schema is normally read in once when the database
** is first opened and stored in a hash table in the sqlite structure.
** This routine erases the stored schema.  This erasure occurs because
** either the database is being closed or because some other process
** changed the schema and this process needs to reread it.
*/
static void clearHashTable(sqlite *db){
  HashElem *pElem;
  Hash temp1;
  temp1 = db->tblHash;
  sqliteHashInit(&db->tblHash, SQLITE_HASH_STRING, 0);
  sqliteHashClear(&db->idxHash);
  for(pElem=sqliteHashFirst(&temp1); pElem; pElem=sqliteHashNext(pElem)){
    Table *pTbl = sqliteHashData(pElem);
    sqliteDeleteTable(db, pTbl);

  }

  sqliteHashClear(&temp1);
  db->flags &= ~SQLITE_Initialized;
}

/*
** Close an existing SQLite database
*/
void sqlite_close(sqlite *db){

**    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.52 2001/09/17 20:25:58 drh Exp $
*/
#include "sqlite.h"

#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
................................................................................
  int flags;                    /* Miscellanous flags. See below */
  int file_format;              /* What file format version is this database? */
  int schema_cookie;            /* Magic number that changes with the schema */
  int next_cookie;              /* Value of schema_cookie after commit */
  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 */
................................................................................

/*
** Each SQL table is represented in memory by
** 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 this table is being deleted */
................................................................................
** The value of aiColumn is {2, 0}.  aiColumn[0]==2 because the 
** first column to be indexed (c3) has an index of 2 in Ex1.aCol[].
** The second column to be indexed (c1) has an index of 0 in
** Ex1.aCol[], hence Ex2.aiColumn[1]==0.
*/
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 tnum;        /* Page containing root of this index in database file */
  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 */

**    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.53 2001/09/22 18:12:10 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
................................................................................
  int flags;                    /* Miscellanous flags. See below */
  int file_format;              /* What file format version is this database? */
  int schema_cookie;            /* Magic number that changes with the schema */
  int next_cookie;              /* Value of schema_cookie after commit */
  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 */
  Hash tblHash;                 /* All tables indexed by name */
  Hash idxHash;                 /* All (named) indices indexed by name */
};

/*
** Possible values for the sqlite.flags.
*/
#define SQLITE_VdbeTrace      0x00000001  /* True to trace VDBE execution */
#define SQLITE_Initialized    0x00000002  /* True after initialization */
................................................................................

/*
** Each SQL table is represented in memory by
** an instance of the following structure.
*/
struct Table {
  char *zName;     /* Name of the table */

  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 this table is being deleted */
................................................................................
** The value of aiColumn is {2, 0}.  aiColumn[0]==2 because the 
** first column to be indexed (c3) has an index of 2 in Ex1.aCol[].
** The second column to be indexed (c1) has an index of 0 in
** Ex1.aCol[], hence Ex2.aiColumn[1]==0.
*/
struct Index {
  char *zName;     /* Name of this index */

  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 tnum;        /* Page containing root of this index in database file */
  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 */

** 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.72 2001/09/18 22:17:44 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include <unistd.h>

/*
** SQL is translated into a sequence of instructions to be
................................................................................
** a key and one or more values.  The values are used in processing
** aggregate functions in a SELECT.  The key is used to implement
** the GROUP BY clause of a select.
*/
typedef struct Agg Agg;
typedef struct AggElem AggElem;
struct Agg {
  int nMem;              /* Number of values stored in each AggElem */
  AggElem *pCurrent;     /* The AggElem currently in focus */
  int nElem;             /* The number of AggElems */
  int nHash;             /* Number of slots in apHash[] */
  AggElem **apHash;      /* A hash array for looking up AggElems by zKey */
  AggElem *pFirst;       /* A list of all AggElems */
};
struct AggElem {
  char *zKey;            /* The key to this AggElem */
  int nKey;              /* Number of bytes in the key, including '\0' at end */
  AggElem *pHash;        /* Next AggElem with the same hash on zKey */
  AggElem *pNext;        /* Next AggElem in a list of them all */
  Mem aMem[1];           /* The values for this AggElem */
};

/*
** A Set structure is used for quick testing to see if a value
** is part of a small set.  Sets are used to implement code like
** this:
**            x.y IN ('hi','hoo','hum')
*/
typedef struct Set Set;
typedef struct SetElem SetElem;
struct Set {
  SetElem *pAll;         /* All elements of this set */
  SetElem *apHash[41];   /* A hash array for all elements in this set */
};
struct SetElem {
  SetElem *pHash;        /* Next element with the same hash on zKey */
  SetElem *pNext;        /* Next element in a list of them all */
  char zKey[1];          /* Value of this key */

};

/*
** A Keylist is a bunch of keys into a table.  The keylist can
** grow without bound.  The keylist stores the keys of database
** records that need to be deleted.
*/
................................................................................
  p->aLabel[i] = -1;
  return -1-i;
}

/*
** Reset an Agg structure.  Delete all its contents.
*/
static void AggReset(Agg *p){
  int i;
  while( p->pFirst ){

    AggElem *pElem = p->pFirst;
    p->pFirst = pElem->pNext;
    for(i=0; i<p->nMem; i++){
      if( pElem->aMem[i].s.flags & STK_Dyn ){
        sqliteFree(pElem->aMem[i].z);
      }
    }
    sqliteFree(pElem);
  }
  sqliteFree(p->apHash);
  memset(p, 0, sizeof(*p));
}

/*
** Add the given AggElem to the hash array
*/
static void AggEnhash(Agg *p, AggElem *pElem){
  int h = sqliteHashNoCase(pElem->zKey, pElem->nKey) % p->nHash;
  pElem->pHash = p->apHash[h];
  p->apHash[h] = pElem;
}

/*
** Change the size of the hash array to the amount given.
*/
static void AggRehash(Agg *p, int nHash){
  int size;
  AggElem *pElem;
  if( p->nHash==nHash ) return;
  size = nHash * sizeof(AggElem*);
  p->apHash = sqliteRealloc(p->apHash, size );
  if( p->apHash==0 ){
    AggReset(p);
    return;
  }
  memset(p->apHash, 0, size);
  p->nHash = nHash;
  for(pElem=p->pFirst; pElem; pElem=pElem->pNext){
    AggEnhash(p, pElem);
  }


}

/*
** Insert a new element and make it the current element.  
**
** Return 0 on success and 1 if memory is exhausted.
*/
static int AggInsert(Agg *p, char *zKey, int nKey){
  AggElem *pElem;
  int i;
  if( p->nHash <= p->nElem*2 ){
    AggRehash(p, p->nElem*2 + 19);
  }
  if( p->nHash==0 ) return 1;
  pElem = sqliteMalloc( sizeof(AggElem) + nKey +
                        (p->nMem-1)*sizeof(pElem->aMem[0]) );
  if( pElem==0 ) return 1;
  pElem->zKey = (char*)&pElem->aMem[p->nMem];
  memcpy(pElem->zKey, zKey, nKey);
  pElem->nKey = nKey;
  AggEnhash(p, pElem);
  pElem->pNext = p->pFirst;
  p->pFirst = pElem;
  p->nElem++;
  p->pCurrent = pElem;
  for(i=0; i<p->nMem; i++){
    pElem->aMem[i].s.flags = STK_Null;
  }

  return 0;
}

/*
** Get the AggElem currently in focus
*/
#define AggInFocus(P)   ((P).pCurrent ? (P).pCurrent : _AggInFocus(&(P)))
static AggElem *_AggInFocus(Agg *p){
  AggElem *pFocus = p->pFirst;
  if( pFocus ){
    p->pCurrent = pFocus;
  }else{
    AggInsert(p,"",1);
    pFocus = p->pCurrent = p->pFirst;

  }
  return pFocus;
}

/*
** Erase all information from a Set
*/
static void SetClear(Set *p){
  SetElem *pElem, *pNext;
  for(pElem=p->pAll; pElem; pElem=pNext){
    pNext = pElem->pNext;
    sqliteFree(pElem);
  }
  memset(p, 0, sizeof(*p));
}

/*
** Insert a new element into the set
*/
static void SetInsert(Set *p, char *zKey){
  SetElem *pElem;
  int h = sqliteHashNoCase(zKey, 0) % ArraySize(p->apHash);
  for(pElem=p->apHash[h]; pElem; pElem=pElem->pHash){
    if( strcmp(pElem->zKey, zKey)==0 ) return;
  }
  pElem = sqliteMalloc( sizeof(*pElem) + strlen(zKey) );
  if( pElem==0 ){
    SetClear(p);
    return;
  }
  strcpy(pElem->zKey, zKey);
  pElem->pNext = p->pAll;
  p->pAll = pElem;
  pElem->pHash = p->apHash[h];
  p->apHash[h] = pElem;
}

/*
** Return TRUE if an element is in the set.  Return FALSE if not.
*/
static int SetTest(Set *p, char *zKey){
  SetElem *pElem;
  int h = sqliteHashNoCase(zKey, 0) % ArraySize(p->apHash);
  for(pElem=p->apHash[h]; pElem; pElem=pElem->pHash){
    if( strcmp(pElem->zKey, zKey)==0 ) return 1;
  }
  return 0;

}

/*
** Convert the given stack entity into a string if it isn't one
** already.  Return non-zero if we run out of memory.
**
** NULLs are converted into an empty string.
................................................................................
  if( p->zLine ){
    sqliteFree(p->zLine);
    p->zLine = 0;
  }
  p->nLineAlloc = 0;
  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;
}
................................................................................
  **
  ** Allocation all the stack space we will ever need.
  */
  NeedStack(p, p->nOp);
  zStack = p->zStack;
  aStack = p->aStack;
  p->tos = -1;






  rc = SQLITE_OK;
#ifdef MEMORY_DEBUG
  if( access("vdbe_trace",0)==0 ){
    p->trace = stdout;
  }
#endif
................................................................................
  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) % p->agg.nHash;
    for(pElem=p->agg.apHash[h]; pElem; pElem=pElem->pHash){
      if( pElem->nKey==nKey && memcmp(pElem->zKey, zKey, nKey)==0 ) break;
    }
  }
  if( pElem ){
    p->agg.pCurrent = pElem;
    pc = pOp->p2 - 1;
  }else{
    AggInsert(&p->agg, zKey, nKey);
    if( sqlite_malloc_failed ) goto no_mem;
  }
................................................................................
** 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 *
................................................................................
** 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 *
................................................................................
** 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 * * *

** 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.73 2001/09/22 18:12:10 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include <unistd.h>

/*
** SQL is translated into a sequence of instructions to be
................................................................................
** a key and one or more values.  The values are used in processing
** aggregate functions in a SELECT.  The key is used to implement
** the GROUP BY clause of a select.
*/
typedef struct Agg Agg;
typedef struct AggElem AggElem;
struct Agg {
  int nMem;            /* Number of values stored in each AggElem */
  AggElem *pCurrent;   /* The AggElem currently in focus */
  HashElem *pSearch;   /* The hash element for pCurrent */
  Hash hash;           /* Hash table of all aggregate elements */


};
struct AggElem {
  char *zKey;          /* The key to this AggElem */
  int nKey;            /* Number of bytes in the key, including '\0' at end */


  Mem aMem[1];         /* The values for this AggElem */
};

/*
** A Set structure is used for quick testing to see if a value
** is part of a small set.  Sets are used to implement code like
** this:
**            x.y IN ('hi','hoo','hum')
*/
typedef struct Set Set;

struct Set {







  Hash hash;             /* A set is just a hash table */
};

/*
** A Keylist is a bunch of keys into a table.  The keylist can
** grow without bound.  The keylist stores the keys of database
** records that need to be deleted.
*/
................................................................................
  p->aLabel[i] = -1;
  return -1-i;
}

/*
** Reset an Agg structure.  Delete all its contents.
*/
static void AggReset(Agg *pAgg){
  int i;
  HashElem *p;
  for(p = sqliteHashFirst(&pAgg->hash); p; p = sqliteHashNext(p)){
    AggElem *pElem = sqliteHashData(p);

    for(i=0; i<pAgg->nMem; i++){
      if( pElem->aMem[i].s.flags & STK_Dyn ){
        sqliteFree(pElem->aMem[i].z);
      }
    }
    sqliteFree(pElem);
  }
  sqliteHashClear(&pAgg->hash);
  pAgg->pCurrent = 0;





























  pAgg->pSearch = 0;
  pAgg->nMem = 0;
}

/*
** Insert a new element and make it the current element.  
**
** Return 0 on success and 1 if memory is exhausted.
*/
static int AggInsert(Agg *p, char *zKey, int nKey){
  AggElem *pElem;
  int i;




  pElem = sqliteMalloc( sizeof(AggElem) + nKey +
                        (p->nMem-1)*sizeof(pElem->aMem[0]) );
  if( pElem==0 ) return 1;
  pElem->zKey = (char*)&pElem->aMem[p->nMem];
  memcpy(pElem->zKey, zKey, nKey);
  pElem->nKey = nKey;
  sqliteHashInsert(&p->hash, pElem->zKey, pElem->nKey, pElem);




  for(i=0; i<p->nMem; i++){
    pElem->aMem[i].s.flags = STK_Null;
  }
  p->pCurrent = pElem;
  return 0;
}

/*
** Get the AggElem currently in focus
*/
#define AggInFocus(P)   ((P).pCurrent ? (P).pCurrent : _AggInFocus(&(P)))
static AggElem *_AggInFocus(Agg *p){
  HashElem *pElem = sqliteHashFirst(&p->hash);
  if( pElem==0 ){


    AggInsert(p,"",1);

    pElem = sqliteHashFirst(&p->hash);
  }














































  return pElem ? sqliteHashData(pElem) : 0;
}

/*
** Convert the given stack entity into a string if it isn't one
** already.  Return non-zero if we run out of memory.
**
** NULLs are converted into an empty string.
................................................................................
  if( p->zLine ){
    sqliteFree(p->zLine);
    p->zLine = 0;
  }
  p->nLineAlloc = 0;
  AggReset(&p->agg);
  for(i=0; i<p->nSet; i++){
    sqliteHashClear(&p->aSet[i].hash);
  }
  sqliteFree(p->aSet);
  p->aSet = 0;
  p->nSet = 0;
  p->pTableRoot = 0;
  p->pIndexRoot = 0;
}
................................................................................
  **
  ** Allocation all the stack space we will ever need.
  */
  NeedStack(p, p->nOp);
  zStack = p->zStack;
  aStack = p->aStack;
  p->tos = -1;

  /* Initialize the aggregrate hash table.
  */
  sqliteHashInit(&p->agg.hash, SQLITE_HASH_BINARY, 0);
  p->agg.pSearch = 0;

  rc = SQLITE_OK;
#ifdef MEMORY_DEBUG
  if( access("vdbe_trace",0)==0 ){
    p->trace = stdout;
  }
#endif
................................................................................
  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;
  pElem = sqliteHashFind(&p->agg.hash, zKey, nKey);







  if( pElem ){
    p->agg.pCurrent = pElem;
    pc = pOp->p2 - 1;
  }else{
    AggInsert(&p->agg, zKey, nKey);
    if( sqlite_malloc_failed ) goto no_mem;
  }
................................................................................
** 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.pSearch==0 ){
    p->agg.pSearch = sqliteHashFirst(&p->agg.hash);
  }else{
    p->agg.pSearch = sqliteHashNext(p->agg.pSearch);







  }





  if( p->agg.pSearch==0 ){
    pc = pOp->p2 - 1;
  } else {
    p->agg.pCurrent = sqliteHashData(p->agg.pSearch);
  }
  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 ){
    sqliteHashClear(&p->aSet[i].hash);
  }
  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 ){
    int k;
    p->aSet = sqliteRealloc(p->aSet, (i+1)*sizeof(p->aSet[0]) );
    if( p->aSet==0 ) goto no_mem;

    for(k=p->nSet; k<=i; k++){
      sqliteHashInit(&p->aSet[k].hash, SQLITE_HASH_BINARY, 1);
    }
    p->nSet = i+1;
  }
  if( pOp->p3 ){
    sqliteHashInsert(&p->aSet[i].hash, pOp->p3, strlen(pOp->p3)+1, p);
  }else{
    int tos = p->tos;
    if( tos<0 ) goto not_enough_stack;
    if( Stringify(p, tos) ) goto no_mem;
    sqliteHashInsert(&p->aSet[i].hash, zStack[tos], aStack[tos].n, p);
    POPSTACK;
  }
  if( sqlite_malloc_failed ) goto no_mem;
  break;
}

/* Opcode: SetFound P1 P2 *
................................................................................
** 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 &&) 
       sqliteHashFind(&p->aSet[i].hash, zStack[tos], aStack[tos].n)){
    pc = pOp->p2 - 1;
  }
  POPSTACK;
  break;
}

/* Opcode: SetNotFound P1 P2 *
................................................................................
** 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 &&)
       sqliteHashFind(&p->aSet[i].hash, zStack[tos], aStack[tos].n)==0 ){
    pc = pOp->p2 - 1;
  }
  POPSTACK;
  break;
}

/* Opcode: Strlen * * *