SQLite

# The library that programs using readline() must link against.
#
LIBREADLINE = @TARGET_READLINE_LIBS@

# Object files for the SQLite library.
#
LIBOBJ = btree.o build.o dbbe.o dbbegdbm.o dbbemem.o delete.o expr.o insert.o \
         main.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/build.c \
  $(TOP)/src/dbbe.c \
  $(TOP)/src/dbbe.h \
  $(TOP)/src/dbbegdbm.c \
  $(TOP)/src/dbbemem.c \
  $(TOP)/src/delete.c \
  $(TOP)/src/expr.c \
  $(TOP)/src/insert.c \
  $(TOP)/src/main.c \
  $(TOP)/src/pager.c \

  $(TOP)/src/parse.y \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/select.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqliteInt.h \

	$(BCC) -o lemon $(TOP)/tool/lemon.c
	cp $(TOP)/tool/lempar.c .

# Header files used by all library source files.
#
HDR = \
   sqlite.h  \
   $(TOP)/src/sqliteInt.h  \
   $(TOP)/src/dbbe.h  \
   $(TOP)/src/vdbe.h  \
   parse.h

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

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

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

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

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

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

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

parse.o:	parse.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c parse.c

parse.h:	parse.c

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.22 2001/09/13 13:46:56 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.

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

** Insert a new record into the BTree.  The key is given by (pKey,nKey)
** and the data is given by (pData,nData).  The cursor is used only to
** define what database the record should be inserted into.  The cursor
** is left pointing at the new record.
*/
int sqliteBtreeInsert(
  BtCursor *pCur,                /* Insert data into the table of this cursor */
  const void *pKey,  int nKey,   /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  Cell newCell;
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;

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



typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

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

int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifdef SQLITE_TEST
int sqliteBtreePageDump(Btree*, int, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
Pager *sqliteBtreePager(Btree*);
char *sqliteBtreeSanityCheck(Btree*, int*, int);
#endif

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

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 
** that statement.  Prior action routines should have already
** constructed VDBE code to do the work of the SQL statement.
** This routine just has to execute the VDBE code.
**
** Note that if an error occurred, it might be the case that
** no VDBE code was generated.
*/
void sqliteExec(Parse *pParse){
  int rc = SQLITE_OK;

  if( sqlite_malloc_failed ) return;
  if( pParse->pVdbe ){
    if( pParse->explain ){
      rc = sqliteVdbeList(pParse->pVdbe, pParse->xCallback, pParse->pArg, 
                          &pParse->zErrMsg);
    }else{
      FILE *trace = (pParse->db->flags & SQLITE_VdbeTrace)!=0 ? stderr : 0;
      sqliteVdbeTrace(pParse->pVdbe, trace);
      rc = sqliteVdbeExec(pParse->pVdbe, pParse->xCallback, pParse->pArg, 
                          &pParse->zErrMsg, pParse->db->pBusyArg,
                          pParse->db->xBusyCallback);
    }
    sqliteVdbeDelete(pParse->pVdbe);
    pParse->pVdbe = 0;
    pParse->colNamesSet = 0;
    pParse->rc = rc;
  }
}

** See also: sqliteRollbackInternalChanges()
*/
void sqliteCommitInternalChanges(sqlite *db){
  int i;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  for(i=0; i<N_HASH; i++){
    Table *pTable, *pNext;
    for(pTable = apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( pTable->isDelete ){
        sqliteDeleteTable(db, pTable);
      }else if( pTable->isCommit==0 ){
        pTable->isCommit = 1;
      }
    }
  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = apIdxHash[i]; pIndex; pIndex=pNext){
      pNext = pIndex->pHash;
      if( pIndex->isDelete ){
        sqliteUnlinkAndDeleteIndex(db, pIndex);
      }else if( pIndex->isCommit==0 ){
        pIndex->isCommit = 1;
      }
    }

** See also: sqliteCommitInternalChanges()
*/
void sqliteRollbackInternalChanges(sqlite *db){
  int i;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  for(i=0; i<N_HASH; i++){
    Table *pTable, *pNext;
    for(pTable = apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( !pTable->isCommit ){
        sqliteDeleteTable(db, pTable);
      }else if( pTable->isDelete ){
        pTable->isDelete = 0;
      }
    }
  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = apIdxHash[i]; pIndex; pIndex=pNext){
      pNext = pIndex->pHash;
      if( !pIndex->isCommit ){
        sqliteUnlinkAndDeleteIndex(db, pIndex);
      }else if( pIndex->isDelete ){
        pIndex->isDelete = 0;
      }
    }

** The new table is constructed in files of the pParse structure.  As
** more of the CREATE TABLE statement is parsed, additional action
** routines are called to build up more of the table.
*/
void sqliteStartTable(Parse *pParse, Token *pStart, Token *pName){
  Table *pTable;
  char *zName;


  pParse->sFirstToken = *pStart;
  zName = sqliteTableNameFromToken(pName);
  if( zName==0 ) return;
  pTable = sqliteFindTable(pParse->db, zName);
  if( pTable!=0 ){
    sqliteSetNString(&pParse->zErrMsg, "table ", 0, pName->z, pName->n,
        " already exists", 0, 0);
    sqliteFree(zName);
    pParse->nErr++;
    return;
  }
  if( sqliteFindIndex(pParse->db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "there is already an index named ", 
       zName, 0);
    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(pParse->db, pParse->pNewTable);
  pParse->pNewTable = pTable;
  if( !pParse->initFlag && (pParse->db->flags & SQLITE_InTrans)==0 ){
    Vdbe *v = sqliteGetVdbe(pParse);
    if( v ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
  }
}

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


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

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

  /* If not initializing, then create the table on disk.
  */
  if( !pParse->initFlag ){
    static VdbeOp addTable[] = {

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

/*
** Given a token, look up a table with that name.  If not found, leave

/*
** This routine is called to do the work of a DROP TABLE statement.
** pName is the name of the table to be dropped.
*/
void sqliteDropTable(Parse *pParse, Token *pName){
  Table *pTable;
  int h;
  Vdbe *v;
  int base;

  if( pParse->nErr || sqlite_malloc_failed ) return;
  pTable = sqliteTableFromToken(pParse, pName);
  if( pTable==0 ) return;
  if( pTable->readOnly ){

  ** deletion occurs inside of sqliteCommitInternalChanges().
  **
  ** Exception: if the SQL statement began with the EXPLAIN keyword,
  ** then no changes should be made.
  */
  if( !pParse->explain ){
    pTable->isDelete = 1;
    db->flags |= SQLITE_InternChanges;
  }
}

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

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


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

  /*
  ** Find the table that is to be indexed.  Return early if not found.
  */
  if( pTable!=0 ){

  if( pName ){
    zName = sqliteTableNameFromToken(pName);
  }else{
    zName = 0;
    sqliteSetString(&zName, pTab->zName, "__primary_key", 0);
  }
  if( zName==0 ) goto exit_create_index;
  if( sqliteFindIndex(pParse->db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "index ", zName, 
       " already exists", 0);
    pParse->nErr++;
    goto exit_create_index;
  }
  if( sqliteFindTable(pParse->db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "there is already a table named ",
       zName, 0);
    pParse->nErr++;
    goto exit_create_index;
  }

  /* If pList==0, it means this routine was called to make a primary

  }

  /* Link the new Index structure to its table and to the other
  ** in-memory database structures.
  */
  if( pParse->explain==0 ){
    h = sqliteHashNoCase(pIndex->zName, 0) % N_HASH;
    pIndex->pHash = pParse->db->apIdxHash[h];
    pParse->db->apIdxHash[h] = pIndex;
    pIndex->pNext = pTab->pIndex;
    pTab->pIndex = pIndex;
    db->flags |= SQLITE_InternChanges;
  }

  /* If the initFlag is 0 then create the index on disk.  This
  ** involves writing the index into the master table and filling in the

    int n;
    Vdbe *v = pParse->pVdbe;
    int lbl1, lbl2;
    int i;

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

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

/*
** This routine will drop an existing named index.
*/
void sqliteDropIndex(Parse *pParse, Token *pName){
  Index *pIndex;
  char *zName;
  Vdbe *v;


  if( pParse->nErr || sqlite_malloc_failed ) return;
  zName = sqliteTableNameFromToken(pName);
  if( zName==0 ) return;
  pIndex = sqliteFindIndex(pParse->db, zName);
  sqliteFree(zName);
  if( pIndex==0 ){
    sqliteSetNString(&pParse->zErrMsg, "no such index: ", 0, 
        pName->z, pName->n, 0);
    pParse->nErr++;
    return;
  }

  /* Generate code to remove the index and from the master table */
  v = sqliteGetVdbe(pParse);
  if( v ){
    static VdbeOp dropIndex[] = {
      { OP_Open,       0, 2,       0},
      { OP_String,     0, 0,       0}, /* 1 */
      { OP_Next,       0, ADDR(8), 0}, /* 2 */
      { OP_Dup,        0, 0,       0},
      { OP_Column,     0, 1,       0},
      { OP_Ne,         0, ADDR(2), 0},
      { OP_Key,        0, 0,       0},
      { OP_Delete,     0, 0,       0},
      { OP_Destroy,    0, 0,       0}, /* 8 */
      { OP_Close,      0, 0,       0},
    };
    int base;

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

  /* Mark the internal Index structure for deletion by the
  ** sqliteCommitInternalChanges routine.
  */

){
  Table *pTab;
  char *zTab;
  int i, j;
  Vdbe *v;
  int addr, end;
  Index *pIdx;


  zTab = sqliteTableNameFromToken(pTableName);
  if( sqlite_malloc_failed || zTab==0 ) goto copy_cleanup;
  pTab = sqliteFindTable(pParse->db, zTab);
  sqliteFree(zTab);
  if( pTab==0 ){
    sqliteSetNString(&pParse->zErrMsg, "no such table: ", 0, 
        pTableName->z, pTableName->n, 0);
    pParse->nErr++;
    goto copy_cleanup;
  }
  if( pTab->readOnly ){
    sqliteSetString(&pParse->zErrMsg, "table ", pTab->zName,
        " may not be modified", 0);
    pParse->nErr++;
    goto copy_cleanup;
  }
  v = sqliteGetVdbe(pParse);
  if( v ){
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    addr = sqliteVdbeAddOp(v, OP_FileOpen, 0, 0, 0, 0);
    sqliteVdbeChangeP3(v, addr, pFilename->z, pFilename->n);
    sqliteVdbeDequoteP3(v, addr);
    sqliteVdbeAddOp(v, OP_Open, 0, pTab->tnum, pTab->zName, 0);
    for(i=1, pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext, i++){

        sqliteVdbeAddOp(v, OP_FileColumn, pIdx->aiColumn[j], 0, 0, 0);
      }
      sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_PutIdx, i, 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);
    sqliteVdbeAddOp(v, OP_Noop, 0, 0, 0, end);
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }
  
copy_cleanup:
  return;
}

/*
** The non-standard VACUUM command is used to clean up the database,
** collapse free space, etc.  It is modelled after the VACUUM command
** in PostgreSQL.
*/
void sqliteVacuum(Parse *pParse, Token *pTableName){
  char *zName;
  Vdbe *v;


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

vacuum_cleanup:
  sqliteFree(zName);
  return;
}

/*
** Begin a transaction
*/
void sqliteBeginTransaction(Parse *pParse){
  int rc;
  sqlite *db;
  Vdbe *v;

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

/*
** Commit a transaction
*/
void sqliteCommitTransaction(Parse *pParse){
  int rc;
  sqlite *db;
  Vdbe *v;

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

/*
** Rollback a transaction
*/
void sqliteRollbackTransaction(Parse *pParse){
  int rc;
  sqlite *db;
  Vdbe *v;

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

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

/*
** This routine opens a new database.  It looks at the first
** few characters of the database name to try to determine what
** kind of database to open.  If the first characters are "gdbm:",
** then it uses the GDBM driver.  If the first few characters are
** "memory:" then it uses the in-memory driver.  If there is no
** match, the default to the GDBM driver.
**
** If successful, a pointer to the Dbbe structure is returned.
** If there are errors, an appropriate error message is left
** in *pzErrMsg and NULL is returned.
*/
Dbbe *sqliteDbbeOpen(
  const char *zName,     /* The name of the database */
  int writeFlag,         /* True if we will be writing to the database */
  int createFlag,        /* True to create database if it doesn't exist */
  char **pzErrMsg        /* Write error messages (if any) here */
){
  extern Dbbe *sqliteMemOpen(const char*,int,int,char**);
#ifndef DISABLE_GDBM
  extern Dbbe *sqliteGdbmOpen(const char*,int,int,char**);
  if( strncmp(zName, "gdbm:", 5)==0 ){
    return sqliteGdbmOpen(&zName[5], writeFlag, createFlag, pzErrMsg);
  }
#endif
  if( strncmp(zName, "memory:", 7)==0 ){
    return sqliteMemOpen(&zName[7], writeFlag, createFlag, pzErrMsg);
  }
#ifndef DISABLE_GDBM
  return sqliteGdbmOpen(zName, writeFlag, createFlag, pzErrMsg);
#else
  return sqliteMemOpen(zName, writeFlag, createFlag, pzErrMsg);
#endif
}

#if 0  /* NOT USED */
/*
** Translate the name of an SQL table (or index) into the name 
** of a file that holds the key/data pairs for that table or
** index.  Space to hold the filename is obtained from
** sqliteMalloc() and must be freed by the calling function.
**
** zDir is the name of the directory in which the file should
** be located.  zSuffix is the filename extension to use for
** the file.
*/
char *sqliteDbbeNameToFile(
  const char *zDir,      /* Directory containing the file */
  const char *zTable,    /* Name of the SQL table that the file contains */
  const char *zSuffix    /* Suffix for the file.  Includes the "." */
){
  char *zFile = 0;
  int i, k, c;
  int nChar = 0;

  for(i=0; (c = zTable[i])!=0; i++){
    if( !isalnum(c) && c!='_' ){
      nChar += 3;
    }else{
      nChar ++;
    }
  }
  nChar += strlen(zDir) + strlen(zSuffix) + 2;
  zFile = sqliteMalloc( nChar );
  if( zFile==0 ) return 0;
  for(i=0; (c = zDir[i])!=0; i++){
    zFile[i] = c;
  }
  zFile[i++] = '/';
  for(k=0; (c = zTable[k])!=0; k++){
    if( isupper(c) ){
      zFile[i++] = tolower(c);
    }else if( isalnum(c) || c=='_' ){
      zFile[i++] = c;
    }else{
      zFile[i++] = '~';
      zFile[i++] = "0123456789abcdef"[c & 0xf];
      zFile[i++] = "0123456789abcdef"[(c>>8)&0xf];
    }
  }
  for(k=0; (c = zSuffix[k])!=0; k++){
    zFile[i++] = c;
  }
  zFile[i] = 0;
  return zFile;
}
#endif /* NOT USED */

/*
** Copyright (c) 1999, 2000 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file defines the interface to the database backend (Dbbe).
**
** The database backend is designed to be as general as possible
** so that it can easily be replaced by a different backend.
** This library was originally designed to support the following
** backends: GDBM, NDBM, SDBM, Berkeley DB.
**
** $Id: dbbe.h,v 1.14 2001/08/19 18:19:46 drh Exp $
*/
#ifndef _SQLITE_DBBE_H_
#define _SQLITE_DBBE_H_
#include <stdio.h>

/*
** The database backend supports two opaque structures.  A Dbbe is
** a context for the entire set of tables forming a complete
** database.  A DbbeCursor is a pointer into a single single table.
**
** Note that at this level, the term "table" can mean either an
** SQL table or an SQL index.  In this module, a table stores a
** single arbitrary-length key and corresponding arbitrary-length
** data.  The differences between tables and indices, and the
** segregation of data into various fields or columns is handled
** by software at higher layers.
**
** The DbbeCursor structure holds some state information, such as
** the key and data from the last retrieval.  For this reason, 
** the backend must allow the creation of multiple independent
** DbbeCursor structures for each table in the database.
*/
typedef struct Dbbe Dbbe;
typedef struct DbbeCursor DbbeCursor;
typedef struct DbbeMethods DbbeMethods;

/*
** Open a complete database.
**
** If the database name begins with "gdbm:" the GDBM driver is used.
** If the name begins with "memory:" the in-memory driver is used.
** The default driver is GDBM.
*/
Dbbe *sqliteDbbeOpen(const char *zName, int write, int create, char **pzErr);

/*
** Each of the various SQLite backends defines a set of methods for
** accessing the database.  Pointers to the methods are contained in
** an instance of the following structure.  A pointer to a static instance
** of this structure is assigned to the Dbbe structure that sqlileDbbeOpen
** returns.
*/
struct DbbeMethods {
  /* Close the whole database. */
  void (*Close)(Dbbe*);

  /* Open a cursor into a particular table of a previously opened database.
  ** Create the table if it doesn't already exist and writeable!=0.  zName
  ** is the base name of the table to be opened.  If the database is 
  ** implement as one file per table, then this routine will add an
  ** appropriate path and extension to the table name to locate the 
  ** actual file.
  **
  ** The intKeyOnly parameter is TRUE if this table will only be accessed
  ** using integer keys.  This parameter allows the database backend to
  ** use a faster algorithm for the special case of integer keys, if it
  ** wants to.
  **
  ** If zName is 0 or "", then a temporary table is created that
  ** will be deleted when closed.
  */
  int (*OpenCursor)(Dbbe*, const char *zName, int writeable, 
                    int intKeyOnly, DbbeCursor**);

  /* Delete a table from the database */
  void (*DropTable)(Dbbe*, const char *zTableName);

  /* Reorganize a table to speed access or reduce its disk usage */
  int (*ReorganizeTable)(Dbbe*, const char *zTableName);

  /* Close a cursor */
  void (*CloseCursor)(DbbeCursor*);

  /* Fetch an entry from a table with the given key.  Return 1 if
  ** successful and 0 if no such entry exists.
  */
  int (*Fetch)(DbbeCursor*, int nKey, char *pKey);

  /* Return 1 if the given key is already in the table.  Return 0
  ** if it is not.
  */
  int (*Test)(DbbeCursor*, int nKey, char *pKey);

  /* Retrieve the key or data used for the last fetch.  Only size
  ** bytes are read beginning with the offset-th byte.  The return
  ** value is the actual number of bytes read.
  */
  int (*CopyKey)(DbbeCursor*, int offset, int size, char *zBuf);
  int (*CopyData)(DbbeCursor*, int offset, int size, char *zBuf);

  /* Retrieve the key or data.  The result is ephemeral.  In other words,
  ** the result is stored in a buffer that might be overwritten on the next
  ** call to any DBBE routine.  If the results are needed for longer than
  ** that, you must make a copy.
  */
  char *(*ReadKey)(DbbeCursor*, int offset);
  char *(*ReadData)(DbbeCursor*, int offset);

  /* Return the length of the most recently fetched key or data. */
  int (*KeyLength)(DbbeCursor*);
  int (*DataLength)(DbbeCursor*);

  /* Retrieve the next entry in the table.  The first key is retrieved
  ** the first time this routine is called, or after a call to
  ** Dbbe.Rewind().  The return value is 1 if there is another
  ** entry, or 0 if there are no more entries. */
  int (*NextKey)(DbbeCursor*);

  /* Make it so that the next call to Dbbe.NextKey() returns
  ** the first entry of the table. */
  int (*Rewind)(DbbeCursor*);

  /* Get a new integer key for this table. */
  int (*New)(DbbeCursor*);

  /* Write an entry into a table.  If another entry already exists with
  ** the same key, the old entry is discarded first.
  */
  int (*Put)(DbbeCursor*, int nKey, char *pKey, int nData, char *pData);

  /* Remove an entry from the table */
  int (*Delete)(DbbeCursor*, int nKey, char *pKey);

  /* Begin a transaction. */
  int (*BeginTransaction)(Dbbe*);

  /* Commit a transaction. */
  int (*Commit)(Dbbe*);

  /* Rollback a transaction. */
  int (*Rollback)(Dbbe*);

  /* Begin searching an index where the key is given. */
  int (*BeginIndex)(DbbeCursor*, int nKey, char *pKey);

  /* Return the integer key for the next index entry, or return 0 if
  ** there are no more index entries. */
  int (*NextIndex)(DbbeCursor*);

  /* Add a new index entry to the file.  The key and record number are
  ** given. */
  int (*PutIndex)(DbbeCursor*, int nKey, char *pKey, int recno);

  /* Delete an index entry from the file.  The key and record number are
  ** given. */
  int (*DeleteIndex)(DbbeCursor*, int nKey, char *pKey, int recno);
};

/*
** This is the structure returned by sqliteDbbeOpen().  It contains
** information common to all the different backend drivers.
**
** The information in this structure (with the exception the method
** pointers in the Dbbe.x field) is intended to be visible to
** the backend drivers only.  Users should not access or modify
** this structure in any way other than the read the method pointers
** in Dbbe.x.
*/
struct Dbbe {
  struct DbbeMethods *x; /* Backend-specific methods for database access */
  /* There used to be other information here, but it has since
  ** been removed.  We'll keep the same design, though, in case we
  ** ever want to add some new fields in the future. */
};

#endif /* defined(_SQLITE_DBBE_H_) */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

/*
** Copyright (c) 2000 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains code to implement the database backend (DBBE)
** for sqlite.  The database backend is the interface between
** sqlite and the code that does the actually reading and writing
** of information to the disk.
**
** This file uses GDBM as the database backend.  It should be
** relatively simple to convert to a different database such
** as NDBM, SDBM, or BerkeleyDB.
**
** $Id: dbbegdbm.c,v 1.9 2001/08/19 18:19:46 drh Exp $
*/
#ifndef DISABLE_GDBM
#include "sqliteInt.h"
#include <gdbm.h>
#include <sys/stat.h>
#include <unistd.h>
#include <ctype.h>
#include <time.h>

/*
** Information about each open disk file is an instance of this 
** structure.  There will only be one such structure for each
** disk file.  If the VDBE opens the same file twice (as will happen
** for a self-join, for example) then two DbbeCursor structures are
** created but there is only a single BeFile structure with an
** nRef of 2.
**
** This backend uses a separate disk file for each database table
** and index.
*/
typedef struct BeFile BeFile;
struct BeFile {
  char *zName;            /* Name of the file */
  GDBM_FILE dbf;          /* The file itself */
  int nRef;               /* Number of references */
  int delOnClose;         /* Delete when closing */
  int writeable;          /* Opened for writing */
  BeFile *pNext, *pPrev;  /* Next and previous on list of open files */
};

/*
** The following structure contains all information used by GDBM
** database driver.  This is a subclass of the Dbbe structure.
*/
typedef struct Dbbex Dbbex;
struct Dbbex {
  Dbbe dbbe;         /* The base class */
  int write;         /* True for write permission */
  int inTrans;       /* Currently in a transaction */
  BeFile *pOpen;     /* List of open files */
  char *zDir;        /* Directory hold the database */
};

/*
** An cursor into a database file is an instance of the following structure.
** There can only be a single BeFile structure for each disk file, but
** there can be multiple DbbeCursor structures.  Each DbbeCursor represents
** a cursor pointing to a particular part of the open BeFile.  The
** BeFile.nRef field hold a count of the number of DbbeCursor structures
** associated with the same disk file.
*/
struct DbbeCursor {
  Dbbex *pBe;        /* The database of which this record is a part */
  BeFile *pFile;     /* The database file for this table */
  datum key;         /* Most recently used key */
  datum data;        /* Most recent data */
  int nextIndex;     /* Next index entry to search */
  int needRewind;    /* Next key should be the first */
  int readPending;   /* The fetch hasn't actually been done yet */
};

/*
** The "mkdir()" function only takes one argument under Windows.
*/
#if OS_WIN
# define mkdir(A,B) mkdir(A)
#endif

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

/*
** Completely shutdown the given database.  Close all files.  Free all memory.
*/
static void sqliteGdbmClose(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  BeFile *pFile, *pNext;
  for(pFile=pBe->pOpen; pFile; pFile=pNext){
    pNext = pFile->pNext;
    gdbm_close(pFile->dbf);
    memset(pFile, 0, sizeof(*pFile));   
    sqliteFree(pFile);
  }
  memset(pBe, 0, sizeof(*pBe));
  sqliteFree(pBe);
}

/*
** Translate the name of an SQL table (or index) into the name 
** of a file that holds the key/data pairs for that table or
** index.  Space to hold the filename is obtained from
** sqliteMalloc() and must be freed by the calling function.
*/
static char *sqliteFileOfTable(Dbbex *pBe, const char *zTable){
  char *zFile = 0;
  int i;
  sqliteSetString(&zFile, pBe->zDir, "/", zTable, ".tbl", 0);
  if( zFile==0 ) return 0;
  for(i=strlen(pBe->zDir)+1; zFile[i]; i++){
    int c = zFile[i];
    if( isupper(c) ){
      zFile[i] = tolower(c);
    }else if( !isalnum(c) && c!='-' && c!='_' && c!='.' ){
      zFile[i] = '+';
    }
  }
  return zFile;
}

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

  if( pBe->inTrans ) writeable = 1;
  *ppCursr = 0;
  pCursr = sqliteMalloc( sizeof(*pCursr) );
  if( pCursr==0 ) return SQLITE_NOMEM;
  if( zTable ){
    zFile = sqliteFileOfTable(pBe, zTable);
    if( zFile==0 ) return SQLITE_NOMEM;
    for(pFile=pBe->pOpen; pFile; pFile=pFile->pNext){
      if( strcmp(pFile->zName,zFile)==0 ) break;
    }
  }else{
    pFile = 0;
    zFile = 0;
  }
  if( pFile==0 ){
    if( writeable ){
      rw_mask = GDBM_WRCREAT | GDBM_FAST;
      mode = 0640;
    }else{
      rw_mask = GDBM_READER;
      mode = 0640;
    }
    pFile = sqliteMalloc( sizeof(*pFile) );
    if( pFile==0 ){
      sqliteFree(zFile);
      return SQLITE_NOMEM;
    }
    if( zFile ){
      if( !writeable || pBe->write ){
        pFile->dbf = gdbm_open(zFile, 0, rw_mask, mode, 0);
      }else{
        pFile->dbf = 0;
      }
    }else{
      int limit;
      char zRandom[50];
      zFile = 0;
      limit = 5;
      do {
        sqliteRandomName(zRandom, "_temp_table_");
        sqliteFree(zFile);
        zFile = sqliteFileOfTable(pBe, zRandom);
        pFile->dbf = gdbm_open(zFile, 0, rw_mask, mode, 0);
      }while( pFile->dbf==0 && limit-- >= 0);
      pFile->delOnClose = 1;
    }
    pFile->writeable = writeable;
    pFile->zName = zFile;
    pFile->nRef = 1 + pBe->inTrans;
    pFile->pPrev = 0;
    if( pBe->pOpen ){
      pBe->pOpen->pPrev = pFile;
    }
    pFile->pNext = pBe->pOpen;
    pBe->pOpen = pFile;
    if( pFile->dbf==0 ){
      if( !writeable && access(zFile,0) ){
        /* Trying to read a non-existant file.  This is OK.  All the
        ** reads will return empty, which is what we want. */
        rc = SQLITE_OK;   
      }else if( pBe->write==0 ){
        rc = SQLITE_READONLY;
      }else if( access(zFile,W_OK|R_OK) ){
        rc = SQLITE_PERM;
      }else{
        rc = SQLITE_BUSY;
      }
    }
  }else{
    sqliteFree(zFile);
    pFile->nRef++;
    if( writeable && !pFile->writeable ){
      rc = SQLITE_READONLY;
    }
  }
  pCursr->pBe = pBe;
  pCursr->pFile = pFile;
  pCursr->readPending = 0;
  pCursr->needRewind = 1;
  if( rc!=SQLITE_OK ){
    sqliteGdbmCloseCursor(pCursr);
    *ppCursr = 0;
  }else{
    *ppCursr = pCursr;
  }
  return rc;
}

/*
** Drop a table from the database.  The file on the disk that corresponds
** to this table is deleted.
*/
static void sqliteGdbmDropTable(Dbbe *pBe, const char *zTable){
  char *zFile;            /* Name of the table file */

  zFile = sqliteFileOfTable((Dbbex*)pBe, zTable);
  unlink(zFile);
  sqliteFree(zFile);
}

/*
** Unlink a file pointer
*/
static void sqliteUnlinkFile(Dbbex *pBe, BeFile *pFile){
  if( pFile->dbf!=NULL ){
    gdbm_close(pFile->dbf);
  }
  if( pFile->pPrev ){
    pFile->pPrev->pNext = pFile->pNext;
  }else{
    pBe->pOpen = pFile->pNext;
  }
  if( pFile->pNext ){
    pFile->pNext->pPrev = pFile->pPrev;
  }
  if( pFile->delOnClose ){
    unlink(pFile->zName);
  }
  sqliteFree(pFile->zName);
  memset(pFile, 0, sizeof(*pFile));
  sqliteFree(pFile);
}

/*
** Close a cursor previously opened by sqliteGdbmOpenCursor().
**
** There can be multiple cursors pointing to the same open file.
** The underlying file is not closed until all cursors have been
** closed.  This routine decrements the BeFile.nref field of the
** underlying file and closes the file when nref reaches 0.
*/
static void sqliteGdbmCloseCursor(DbbeCursor *pCursr){
  BeFile *pFile;
  Dbbex *pBe;
  if( pCursr==0 ) return;
  pFile = pCursr->pFile;
  pBe = pCursr->pBe;
  pFile->nRef--;
  if( pFile->dbf!=NULL ){
    gdbm_sync(pFile->dbf);
  }
  if( pFile->nRef<=0 ){
    sqliteUnlinkFile(pBe, pFile);
  }
  if( pCursr->key.dptr ) free(pCursr->key.dptr);
  if( pCursr->data.dptr ) free(pCursr->data.dptr);
  memset(pCursr, 0, sizeof(*pCursr));
  sqliteFree(pCursr);
}

/*
** Reorganize a table to reduce search times and disk usage.
*/
static int sqliteGdbmReorganizeTable(Dbbe *pBe, const char *zTable){
  DbbeCursor *pCursr;
  int rc;

  rc = sqliteGdbmOpenCursor(pBe, zTable, 1, 0, &pCursr);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  if( pCursr && pCursr->pFile && pCursr->pFile->dbf ){
    gdbm_reorganize(pCursr->pFile->dbf);
  }
  if( pCursr ){
    sqliteGdbmCloseCursor(pCursr);
  }
  return SQLITE_OK;
}

/*
** Clear the given datum
*/
static void datumClear(datum *p){
  if( p->dptr ) free(p->dptr);
  p->dptr = 0;
  p->dsize = 0;
}

/*
** Fetch a single record from an open cursor.  Return 1 on success
** and 0 on failure.
*/
static int sqliteGdbmFetch(DbbeCursor *pCursr, int nKey, char *pKey){
  datum key;
  key.dsize = nKey;
  key.dptr = pKey;
  datumClear(&pCursr->key);
  datumClear(&pCursr->data);
  if( pCursr->pFile && pCursr->pFile->dbf ){
    pCursr->data = gdbm_fetch(pCursr->pFile->dbf, key);
  }
  return pCursr->data.dptr!=0;
}

/*
** Return 1 if the given key is already in the table.  Return 0
** if it is not.
*/
static int sqliteGdbmTest(DbbeCursor *pCursr, int nKey, char *pKey){
  datum key;
  int result = 0;
  key.dsize = nKey;
  key.dptr = pKey;
  if( pCursr->pFile && pCursr->pFile->dbf ){
    result = gdbm_exists(pCursr->pFile->dbf, key);
  }
  return result;
}

/*
** Copy bytes from the current key or data into a buffer supplied by
** the calling function.  Return the number of bytes copied.
*/
static
int sqliteGdbmCopyKey(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  int n;
  if( offset>=pCursr->key.dsize ) return 0;
  if( offset+size>pCursr->key.dsize ){
    n = pCursr->key.dsize - offset;
  }else{
    n = size;
  }
  memcpy(zBuf, &pCursr->key.dptr[offset], n);
  return n;
}
static
int sqliteGdbmCopyData(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  int n;
  if( pCursr->readPending && pCursr->pFile && pCursr->pFile->dbf ){
    pCursr->data = gdbm_fetch(pCursr->pFile->dbf, pCursr->key);
    pCursr->readPending = 0;
  }
  if( offset>=pCursr->data.dsize ) return 0;
  if( offset+size>pCursr->data.dsize ){
    n = pCursr->data.dsize - offset;
  }else{
    n = size;
  }
  memcpy(zBuf, &pCursr->data.dptr[offset], n);
  return n;
}

/*
** Return a pointer to bytes from the key or data.  The data returned
** is ephemeral.
*/
static char *sqliteGdbmReadKey(DbbeCursor *pCursr, int offset){
  if( offset<0 || offset>=pCursr->key.dsize ) return "";
  return &pCursr->key.dptr[offset];
}
static char *sqliteGdbmReadData(DbbeCursor *pCursr, int offset){
  if( pCursr->readPending && pCursr->pFile && pCursr->pFile->dbf ){
    pCursr->data = gdbm_fetch(pCursr->pFile->dbf, pCursr->key);
    pCursr->readPending = 0;
  }
  if( offset<0 || offset>=pCursr->data.dsize ) return "";
  return &pCursr->data.dptr[offset];
}

/*
** Return the total number of bytes in either data or key.
*/
static int sqliteGdbmKeyLength(DbbeCursor *pCursr){
  return pCursr->key.dsize;
}
static int sqliteGdbmDataLength(DbbeCursor *pCursr){
  if( pCursr->readPending && pCursr->pFile && pCursr->pFile->dbf ){
    pCursr->data = gdbm_fetch(pCursr->pFile->dbf, pCursr->key);
    pCursr->readPending = 0;
  }
  return pCursr->data.dsize;
}

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

/*
** Read the next key from the table.  Return 1 on success.  Return
** 0 if there are no more keys.
*/
static int sqliteGdbmNextKey(DbbeCursor *pCursr){
  datum nextkey;
  int rc;
  if( pCursr==0 || pCursr->pFile==0 || pCursr->pFile->dbf==0 ){
    pCursr->readPending = 0;
    return 0;
  }
  if( pCursr->needRewind ){
    nextkey = gdbm_firstkey(pCursr->pFile->dbf);
    pCursr->needRewind = 0;
  }else{
    nextkey = gdbm_nextkey(pCursr->pFile->dbf, pCursr->key);
  }
  datumClear(&pCursr->key);
  datumClear(&pCursr->data);
  pCursr->key = nextkey;
  if( pCursr->key.dptr ){
    pCursr->readPending = 1;
    rc = 1;
  }else{
    pCursr->needRewind = 1;
    pCursr->readPending = 0;
    rc = 0;
  }
  return rc;
}

/*
** Get a new integer key.
*/
static int sqliteGdbmNew(DbbeCursor *pCursr){
  int iKey;
  datum key;
  int go = 1;

  if( pCursr->pFile==0 || pCursr->pFile->dbf==0 ) return 1;
  while( go ){
    iKey = sqliteRandomInteger() & 0x7fffffff;
    if( iKey==0 ) continue;
    key.dptr = (char*)&iKey;
    key.dsize = 4;
    go = gdbm_exists(pCursr->pFile->dbf, key);
  }
  return iKey;
}   

/*
** Write an entry into the table.  Overwrite any prior entry with the
** same key.
*/
static int sqliteGdbmPut(
  DbbeCursor *pCursr,  /* Write to the database associated with this cursor */
  int nKey,            /* Number of bytes in the key */
  char *pKey,          /* The data for the key */
  int nData,           /* Number of bytes of data */
  char *pData          /* The data */
){
  datum data, key;
  int rc;
  if( pCursr->pFile==0 || pCursr->pFile->dbf==0 ) return SQLITE_ERROR;
  data.dsize = nData;
  data.dptr = pData;
  key.dsize = nKey;
  key.dptr = pKey;
  rc = gdbm_store(pCursr->pFile->dbf, key, data, GDBM_REPLACE);
  if( rc ) rc = SQLITE_ERROR;
  datumClear(&pCursr->key);
  datumClear(&pCursr->data);
  return rc;
}

/*
** Remove an entry from a table, if the entry exists.
*/
static int sqliteGdbmDelete(DbbeCursor *pCursr, int nKey, char *pKey){
  datum key;
  int rc;
  datumClear(&pCursr->key);
  datumClear(&pCursr->data);
  if( pCursr->pFile==0 || pCursr->pFile->dbf==0 ) return SQLITE_ERROR;
  key.dsize = nKey;
  key.dptr = pKey;
  rc = gdbm_delete(pCursr->pFile->dbf, key);
  if( rc ) rc = SQLITE_ERROR;
  return rc;
}

/*
** Begin a transaction.
*/
static int sqliteGdbmBeginTrans(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  BeFile *pFile;
  if( pBe->inTrans ) return SQLITE_OK;
  for(pFile=pBe->pOpen; pFile; pFile=pFile->pNext){
    pFile->nRef++;
  }
  pBe->inTrans = 1;
  return SQLITE_OK;  
}

/*
** End a transaction.
*/
static int sqliteGdbmEndTrans(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  BeFile *pFile, *pNext;
  if( !pBe->inTrans ) return SQLITE_OK;
  for(pFile=pBe->pOpen; pFile; pFile=pNext){
    pNext = pFile->pNext;
    pFile->nRef--;
    if( pFile->nRef<=0 ){
      sqliteUnlinkFile(pBe, pFile);
    }
  }
  pBe->inTrans = 0;
  return SQLITE_OK;  
}

/*
** Begin scanning an index for the given key.  Return 1 on success and
** 0 on failure.
*/
static int sqliteGdbmBeginIndex(DbbeCursor *pCursr, int nKey, char *pKey){
  if( !sqliteGdbmFetch(pCursr, nKey, pKey) ) return 0;
  pCursr->nextIndex = 0;
  return 1;
}

/*
** Return an integer key which is the next record number in the index search
** that was started by a prior call to BeginIndex.  Return 0 if all records
** have already been searched.
*/
static int sqliteGdbmNextIndex(DbbeCursor *pCursr){
  int *aIdx;
  int nIdx;
  int k;
  nIdx = pCursr->data.dsize/sizeof(int);
  aIdx = (int*)pCursr->data.dptr;
  if( nIdx>1 ){
    k = *(aIdx++);
    if( k>nIdx-1 ) k = nIdx-1;
  }else{
    k = nIdx;
  }
  while( pCursr->nextIndex < k ){
    int recno = aIdx[pCursr->nextIndex++];
    if( recno!=0 ) return recno;
  }
  pCursr->nextIndex = 0;
  return 0;
}

/*
** Write a new record number and key into an index table.  Return a status
** code.
*/
static int sqliteGdbmPutIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  int r = sqliteGdbmFetch(pCursr, nKey, pKey);
  if( r==0 ){
    /* Create a new record for this index */
    sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int), (char*)&N);
  }else{
    /* Extend the existing record */
    int nIdx;
    int *aIdx;
    int k;
            
    nIdx = pCursr->data.dsize/sizeof(int);
    if( nIdx==1 ){
      aIdx = sqliteMalloc( sizeof(int)*4 );
      if( aIdx==0 ) return SQLITE_NOMEM;
      aIdx[0] = 2;
      sqliteGdbmCopyData(pCursr, 0, sizeof(int), (char*)&aIdx[1]);
      aIdx[2] = N;
      sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int)*4, (char*)aIdx);
      sqliteFree(aIdx);
    }else{
      aIdx = (int*)sqliteGdbmReadData(pCursr, 0);
      k = aIdx[0];
      if( k<nIdx-1 ){
        aIdx[k+1] = N;
        aIdx[0]++;
        sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
      }else{
        nIdx *= 2;
        aIdx = sqliteMalloc( sizeof(int)*nIdx );
        if( aIdx==0 ) return SQLITE_NOMEM;
        sqliteGdbmCopyData(pCursr, 0, sizeof(int)*(k+1), (char*)aIdx);
        aIdx[k+1] = N;
        aIdx[0]++;
        sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
        sqliteFree(aIdx);
      }
    }
  }
  return SQLITE_OK;
}

/*
** Delete an index entry.  Return a status code.
*/
static 
int sqliteGdbmDeleteIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  int *aIdx;
  int nIdx;
  int j, k;
  int rc;
  rc = sqliteGdbmFetch(pCursr, nKey, pKey);
  if( !rc ) return SQLITE_OK;
  nIdx = pCursr->data.dsize/sizeof(int);
  aIdx = (int*)sqliteGdbmReadData(pCursr, 0);
  if( (nIdx==1 && aIdx[0]==N) || (aIdx[0]==1 && aIdx[1]==N) ){
    sqliteGdbmDelete(pCursr, nKey, pKey);
  }else{
    k = aIdx[0];
    for(j=1; j<=k && aIdx[j]!=N; j++){}
    if( j>k ) return SQLITE_OK;
    aIdx[j] = aIdx[k];
    aIdx[k] = 0;
    aIdx[0]--;
    if( aIdx[0]*3 + 1 < nIdx ){
      nIdx /= 2;
    }
    sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
  }
  return SQLITE_OK;
}

/*
** This variable contains pointers to all of the access methods
** used to implement the GDBM backend.
*/
static struct DbbeMethods gdbmMethods = {
  /*           Close */   sqliteGdbmClose,
  /*      OpenCursor */   sqliteGdbmOpenCursor,
  /*       DropTable */   sqliteGdbmDropTable,
  /* ReorganizeTable */   sqliteGdbmReorganizeTable,
  /*     CloseCursor */   sqliteGdbmCloseCursor,
  /*           Fetch */   sqliteGdbmFetch,
  /*            Test */   sqliteGdbmTest,
  /*         CopyKey */   sqliteGdbmCopyKey,
  /*        CopyData */   sqliteGdbmCopyData,
  /*         ReadKey */   sqliteGdbmReadKey,
  /*        ReadData */   sqliteGdbmReadData,
  /*       KeyLength */   sqliteGdbmKeyLength,
  /*      DataLength */   sqliteGdbmDataLength,
  /*         NextKey */   sqliteGdbmNextKey,
  /*          Rewind */   sqliteGdbmRewind,
  /*             New */   sqliteGdbmNew,
  /*             Put */   sqliteGdbmPut,
  /*          Delete */   sqliteGdbmDelete,
  /*      BeginTrans */   sqliteGdbmBeginTrans,
  /*          Commit */   sqliteGdbmEndTrans,
  /*        Rollback */   sqliteGdbmEndTrans,
  /*      BeginIndex */   sqliteGdbmBeginIndex,
  /*       NextIndex */   sqliteGdbmNextIndex,
  /*        PutIndex */   sqliteGdbmPutIndex,
  /*     DeleteIndex */   sqliteGdbmDeleteIndex,
};


/*
** This routine opens a new database.  For the GDBM driver
** implemented here, the database name is the name of the directory
** containing all the files of the database.
**
** If successful, a pointer to the Dbbe structure is returned.
** If there are errors, an appropriate error message is left
** in *pzErrMsg and NULL is returned.
*/
Dbbe *sqliteGdbmOpen(
  const char *zName,     /* The name of the database */
  int writeFlag,         /* True if we will be writing to the database */
  int createFlag,        /* True to create database if it doesn't exist */
  char **pzErrMsg        /* Write error messages (if any) here */
){
  Dbbex *pNew;
  struct stat statbuf;
  char *zMaster;

  if( !writeFlag ) createFlag = 0;
  if( stat(zName, &statbuf)!=0 ){
    if( createFlag ) mkdir(zName, 0750);
    if( stat(zName, &statbuf)!=0 ){
      sqliteSetString(pzErrMsg, createFlag ? 
         "can't find or create directory \"" : "can't find directory \"",
         zName, "\"", 0);
      return 0;
    }
  }
  if( !S_ISDIR(statbuf.st_mode) ){
    sqliteSetString(pzErrMsg, "not a directory: \"", zName, "\"", 0);
    return 0;
  }
  if( access(zName, writeFlag ? (X_OK|W_OK|R_OK) : (X_OK|R_OK)) ){
    sqliteSetString(pzErrMsg, "access permission denied", 0);
    return 0;
  }
  zMaster = 0;
  sqliteSetString(&zMaster, zName, "/" MASTER_NAME ".tbl", 0);
  if( stat(zMaster, &statbuf)==0
   && access(zMaster, writeFlag ? (W_OK|R_OK) : R_OK)!=0 ){
    sqliteSetString(pzErrMsg, "access permission denied for ", zMaster, 0);
    sqliteFree(zMaster);
    return 0;
  }
  sqliteFree(zMaster);
  pNew = sqliteMalloc(sizeof(Dbbex) + strlen(zName) + 1);
  if( pNew==0 ){
    sqliteSetString(pzErrMsg, "out of memory", 0);
    return 0;
  }
  pNew->dbbe.x = &gdbmMethods;
  pNew->zDir = (char*)&pNew[1];
  strcpy(pNew->zDir, zName);
  pNew->write = writeFlag;
  pNew->pOpen = 0;
  return &pNew->dbbe;
}
#endif /* DISABLE_GDBM */

/*
** Copyright (c) 2000 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains code to implement the database backend (DBBE)
** for sqlite.  The database backend is the interface between
** sqlite and the code that does the actually reading and writing
** of information to the disk.
**
** This file uses an in-memory hash table as the database backend. 
** Nothing is ever written to disk using this backend.  All information
** is forgotten when the program exits.
**
** $Id: dbbemem.c,v 1.17 2001/08/20 00:33:58 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>


typedef struct Array Array;
typedef struct ArrayElem ArrayElem;
typedef struct Datum Datum;

/* A complete associative array 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 Array {
  int count;               /* Number of entries in the array */
  ArrayElem *first;        /* The first element of the array */
  int htsize;              /* Number of buckets in the hash table */
  struct _Array_ht {         /* the hash table */
    int count;               /* Number of entries with this hash */
    ArrayElem *chain;        /* Pointer to first entry with this hash */
  } *ht;
};

/*
** An instance of the following structure stores a single key or
** data element.
*/
struct Datum {
  int n;
  void *p;
};

/* Each element in the associative array 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 ArrayElem {
  ArrayElem *next, *prev;  /* Next and previous elements in the array */
  Datum key, data;         /* Key and data for this element */
};

/* Some routines are so simple that they can be implemented as macros
** These are given first. */

/* Return the number of entries in the array */
#define ArrayCount(X)    ((X)->count)

/* Return a pointer to the first element of the array */
#define ArrayFirst(X)    ((X)->first)

/* Return a pointer to the next (or previous) element of the array */
#define ArrayNext(X)     ((X)->next)
#define ArrayPrev(X)     ((X)->prev)

/* Return TRUE if the element given is the last element in the array */
#define ArrayIsLast(X)   ((X)->next==0)
#define ArrayIsFirst(X)  ((X)->prev==0)

/* Return the data or key for an element of the array */
#define ArrayData(X)     ((X)->data.p)
#define ArrayDataSize(X) ((X)->data.n)
#define ArrayKey(X)      ((X)->key.p)
#define ArrayKeySize(X)  ((X)->key.n)

/* Turn bulk memory into an associative array object by initializing the
** fields of the Array structure.
*/
static void ArrayInit(Array *new){
  new->first = 0;
  new->count = 0;
  new->htsize = 0;
  new->ht = 0;
}

/* Remove all entries from an associative array.  Reclaim all memory.
** This is the opposite of ArrayInit().
*/
static void ArrayClear(Array *array){
  ArrayElem *elem;         /* For looping over all elements of the array */

  elem = array->first;
  array->first = 0;
  array->count = 0;
  if( array->ht ) sqliteFree(array->ht);
  array->ht = 0;
  array->htsize = 0;
  while( elem ){
    ArrayElem *next_elem = elem->next;
    sqliteFree(elem);
    elem = next_elem;
  }
}

/*
** Generate a hash from an N-byte key
*/
static int ArrayHash(Datum d){
  int h = 0;
  while( d.n-- > 0 ){
    /* The funky case "*(char**)&d.p" is to work around a bug the
    ** c89 compiler of HPUX. */
    h = (h<<9) ^ (h<<3) ^ h ^ *((*(char**)&d.p)++);
  }
  if( h<0 ) h = -h; 
  return h;
}

/* Resize the hash table for a Array array
*/
static void ArrayRehash(Array *array, int new_size){
  struct _Array_ht *new_ht;       /* The new hash table */
  ArrayElem *elem, *next_elem;    /* For looping over existing elements */
  int i;                          /* Loop counter */
  ArrayElem *x;                   /* Element being copied to new hash table */

  new_ht = sqliteMalloc( new_size*sizeof(struct _Array_ht) );
  if( new_ht==0 ){ ArrayClear(array); return; }
  if( array->ht ) sqliteFree(array->ht);
  array->ht = new_ht;
  array->htsize = new_size;
  for(i=new_size-1; i>=0; i--){ 
    new_ht[i].count = 0;
    new_ht[i].chain = 0;
  }
  for(elem=array->first, array->first=0; elem; elem = next_elem){
    int h = ArrayHash(elem->key) & (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          array->first = elem;
      x->prev = elem;
    }else{
      elem->next = array->first;
      if( array->first ) array->first->prev = elem;
      elem->prev = 0;
      array->first = elem;
    }
    new_ht[h].chain = elem;
    new_ht[h].count++;
  }
}

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

  if( array->count ){
    elem = array->ht[h].chain;
    count = array->ht[h].count;
    while( count-- && elem ){
      if( elem->key.n==key.n && memcmp(elem->key.p,key.p,key.n)==0 ){ 
        return elem;
      }
      elem = elem->next;
    }
  }
  return 0;
}


/* Attempt to locate an element of the associative array with a key
** that matches "key".  Return the ArrayElement if found and NULL if
** if no match.
*/
static ArrayElem *ArrayFindElement(const Array *array, Datum key){
  int h;             /* A hash on key */
  if( array->count==0 ) return 0;
  h = ArrayHash(key);
  return ArrayFindElementGivenHash(array, key, h & (array->htsize-1));
}

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

/* Attempt to locate an element of the associative array with a key
** that matches "key".  Return the data for this element if it is
** found, or NULL if no match is found.
*/
static Datum ArrayFind(const Array *array, Datum key){
  int h;             /* A hash on key */
  ArrayElem *elem;   /* The element that matches key */
  static Datum nil = {0, 0};

  if( array->count==0 ) return nil;
  h = ArrayHash(key);
  elem = ArrayFindElementGivenHash(array, key, h & (array->htsize-1));
  return elem ? elem->data : nil;
}

/* Insert an element into the array.  The key will be "key" and
** the data will be "data".
**
** If no array element exists with a matching key, then a new
** array element is created.  The key is copied into the new element.
** But only a pointer to the data is stored.  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 array.
*/
static Datum ArrayInsert(Array *array, Datum key, Datum data){
  int hraw;              /* Raw hash value of the key */
  int h;                 /* the hash of the key modulo hash table size */
  ArrayElem *elem;       /* Used to loop thru the element list */
  ArrayElem *new_elem;   /* New element added to the array */
  Datum rv;              /* Return value */
  static Datum nil = {0, 0};

  hraw = ArrayHash(key);
  h = hraw & (array->htsize-1);
  elem = ArrayFindElementGivenHash(array,key,h);
  if( elem ){
    Datum old_data = elem->data;
    if( data.p==0 ){
      ArrayRemoveElementGivenHash(array,elem,h);
    }else{
      elem->data = data;
    }
    return old_data;
  }
  if( data.p==0 ) return nil;
  new_elem = (ArrayElem*)sqliteMalloc( sizeof(ArrayElem) + key.n );
  if( new_elem==0 ) return nil;
  new_elem->key.n = key.n;
  new_elem->key.p = (void*)&new_elem[1];
  memcpy(new_elem->key.p, key.p, key.n);
  array->count++;
  if( array->htsize==0 ) ArrayRehash(array,4);
  if( array->htsize==0 ) return nil;
  if( array->count > array->htsize ){
    ArrayRehash(array,array->htsize*2);
    if( array->htsize==0 ){
      sqliteFree(new_elem);
      return nil;
    }
  }
  h = hraw & (array->htsize-1);
  elem = array->ht[h].chain;
  if( elem ){
    new_elem->next = elem;
    new_elem->prev = elem->prev;
    if( elem->prev ){ elem->prev->next = new_elem; }
    else            { array->first = new_elem; }
    elem->prev = new_elem;
  }else{
    new_elem->next = array->first;
    new_elem->prev = 0;
    if( array->first ){ array->first->prev = new_elem; }
    array->first = new_elem;
  }
  array->ht[h].count++;
  array->ht[h].chain = new_elem;
  new_elem->data = data;
  rv.p = 0;
  rv.n = 0;
  return rv;
}

/*
** Information about each open database table is an instance of this 
** structure.  There will only be one such structure for each
** table.  If the VDBE opens the same table twice (as will happen
** for a self-join, for example) then two DbbeCursor structures are
** created but there is only a single MTable structure.
*/
typedef struct MTable MTable;
struct MTable {
  char *zName;            /* Name of the table */
  int delOnClose;         /* Delete when closing */
  int intKeyOnly;         /* Use only integer keys on this table */
  Array data;             /* The data in this stable */
};

/*
** The following structure contains all information used by GDBM
** database driver.  This is a subclass of the Dbbe structure.
*/
typedef struct Dbbex Dbbex;
struct Dbbex {
  Dbbe dbbe;         /* The base class */
  Array tables;      /* All tables of the database */
};

/*
** An cursor into a database file is an instance of the following structure.
** There can only be a single MTable structure for each disk file, but
** there can be multiple DbbeCursor structures.  Each DbbeCursor represents
** a cursor pointing to a particular part of the open MTable.  The
** MTable.nRef field hold a count of the number of DbbeCursor structures
** associated with the same disk file.
*/
struct DbbeCursor {
  Dbbex *pBe;        /* The database of which this record is a part */
  MTable *pTble;     /* The database file for this table */
  ArrayElem *elem;   /* Most recently accessed record */
  int needRewind;    /* Next key should be the first */
  int nextIndex;     /* Next recno in an index entry */
};

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

/*
** Erase all the memory of an MTable
*/
static void deleteMTable(MTable *p){
  ArrayElem *i;
  for(i=ArrayFirst(&p->data); i; i=ArrayNext(i)){
    void *data = ArrayData(i);
    sqliteFree(data);
  }
  ArrayClear(&p->data);
  sqliteFree(p->zName);
  sqliteFree(p);
}

/*
** Completely shutdown the given database.  Close all files.  Free all memory.
*/
static void sqliteMemClose(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  MTable *pTble;
  ArrayElem *j;
  for(j=ArrayFirst(&pBe->tables); j; j=ArrayNext(j)){
    pTble = ArrayData(j);
    deleteMTable(pTble);
  }
  ArrayClear(&pBe->tables);
  memset(pBe, 0, sizeof(*pBe));
  sqliteFree(pBe);
}

/*
** Translate the name of an SQL table (or index) into its
** canonical name.
** 
** Space to hold the canonical name is obtained from
** sqliteMalloc() and must be freed by the calling function.
*/
static char *sqliteNameOfTable(const char *zTable){
  char *zNew = 0;
  int i, c;
  sqliteSetString(&zNew, zTable, 0);
  if( zNew==0 ) return 0;
  for(i=0; (c = zNew[i])!=0; i++){
    if( isupper(c) ){
      zNew[i] = tolower(c);
    }
  }
  return zNew;
}

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

  *ppCursr = 0;
  pCursr = sqliteMalloc( sizeof(*pCursr) );
  if( pCursr==0 ) return SQLITE_NOMEM;
  if( zTable ){
    Datum key;
    zName = sqliteNameOfTable(zTable);
    if( zName==0 ) return SQLITE_NOMEM;
    key.p = zName;
    key.n = strlen(zName);
    pTble = ArrayFind(&pBe->tables, key).p;
  }else{
    zName = 0;
    pTble = 0;
  }
  if( pTble==0 ){
    pTble = sqliteMalloc( sizeof(*pTble) );
    if( pTble==0 ){
      sqliteFree(zName);
      return SQLITE_NOMEM;
    }
    if( zName ){
      Datum ins_key, ins_data;
      pTble->zName = zName;
      pTble->delOnClose = 0;
      ins_data.p = pTble;
      ins_data.n = sizeof( *pTble );
      ins_key.p = zName;
      ins_key.n = strlen(zName);
      ArrayInsert(&pBe->tables, ins_key, ins_data);
    }else{
      pTble->zName = 0;
      pTble->delOnClose = 1;
    }
    pTble->intKeyOnly = intKeyOnly;
    ArrayInit(&pTble->data);
  }else{
    assert( pTble->intKeyOnly==intKeyOnly );
    sqliteFree(zName);
  }
  pCursr->pBe = pBe;
  pCursr->pTble = pTble;
  pCursr->needRewind = 1;
  *ppCursr = pCursr;
  return rc;
}

/*
** Drop a table from the database.  The file on the disk that corresponds
** to this table is deleted.
*/
static void sqliteMemDropTable(Dbbe *pDbbe, const char *zTable){
  char *zName;            /* Name of the table file */
  Datum key, data;
  MTable *pTble;
  Dbbex *pBe = (Dbbex*)pDbbe;

  zName = sqliteNameOfTable(zTable);
  key.p = zName;
  key.n = strlen(zName);
  pTble = ArrayFind(&pBe->tables, key).p;
  if( pTble ){
    data.p = 0;
    data.n = 0;
    ArrayInsert(&pBe->tables, key, data);
    deleteMTable(pTble);
  }
  sqliteFree(zName);
}

/*
** Close a cursor previously opened by sqliteMemOpenCursor().
**
** There can be multiple cursors pointing to the same open file.
** The underlying file is not closed until all cursors have been
** closed.  This routine decrements the MTable.nref field of the
** underlying file and closes the file when nref reaches 0.
*/
static void sqliteMemCloseCursor(DbbeCursor *pCursr){
  MTable *pTble;
  Dbbex *pBe;
  if( pCursr==0 ) return;
  pTble = pCursr->pTble;
  pBe = pCursr->pBe;
  if( pTble->delOnClose ){
    deleteMTable(pTble);
  }
  sqliteFree(pCursr);
}

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

/*
** Fetch a single record from an open cursor.  Return 1 on success
** and 0 on failure.
*/
static int sqliteMemFetch(DbbeCursor *pCursr, int nKey, char *pKey){
  Datum key;
  key.n = nKey;
  key.p = pKey;
  assert( nKey==4 || pCursr->pTble->intKeyOnly==0 );
  pCursr->elem = ArrayFindElement(&pCursr->pTble->data, key);
  return pCursr->elem!=0;
}

/*
** Return 1 if the given key is already in the table.  Return 0
** if it is not.
*/
static int sqliteMemTest(DbbeCursor *pCursr, int nKey, char *pKey){
  return sqliteMemFetch(pCursr, nKey, pKey);
}

/*
** Copy bytes from the current key or data into a buffer supplied by
** the calling function.  Return the number of bytes copied.
*/
static
int sqliteMemCopyKey(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  int n;
  if( pCursr->elem==0 ) return 0;
  if( offset>=ArrayKeySize(pCursr->elem) ) return 0;
  if( offset+size>ArrayKeySize(pCursr->elem) ){
    n = ArrayKeySize(pCursr->elem) - offset;
  }else{
    n = size;
  }
  memcpy(zBuf, &((char*)ArrayKey(pCursr->elem))[offset], n);
  return n;
}
static
int sqliteMemCopyData(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  int n;
  if( pCursr->elem==0 ) return 0;
  if( offset>=ArrayDataSize(pCursr->elem) ) return 0;
  if( offset+size>ArrayDataSize(pCursr->elem) ){
    n = ArrayDataSize(pCursr->elem) - offset;
  }else{
    n = size;
  }
  memcpy(zBuf, &((char*)ArrayData(pCursr->elem))[offset], n);
  return n;
}

/*
** Return a pointer to bytes from the key or data.  The data returned
** is ephemeral.
*/
static char *sqliteMemReadKey(DbbeCursor *pCursr, int offset){
  if( pCursr->elem==0 || offset<0 || offset>=ArrayKeySize(pCursr->elem) ){
    return "";
  }
  return &((char*)ArrayKey(pCursr->elem))[offset];
}
static char *sqliteMemReadData(DbbeCursor *pCursr, int offset){
  if( pCursr->elem==0 || offset<0 || offset>=ArrayDataSize(pCursr->elem) ){
    return "";
  }
  return &((char*)ArrayData(pCursr->elem))[offset];
}

/*
** Return the total number of bytes in either data or key.
*/
static int sqliteMemKeyLength(DbbeCursor *pCursr){
  return pCursr->elem ? ArrayKeySize(pCursr->elem) : 0;
}
static int sqliteMemDataLength(DbbeCursor *pCursr){
  return pCursr->elem ? ArrayDataSize(pCursr->elem) : 0;
}

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

/*
** Read the next key from the table.  Return 1 on success.  Return
** 0 if there are no more keys.
*/
static int sqliteMemNextKey(DbbeCursor *pCursr){
  if( pCursr->needRewind || pCursr->elem==0 ){
    pCursr->elem = ArrayFirst(&pCursr->pTble->data);
    pCursr->needRewind = 0;
  }else{
    pCursr->elem = ArrayNext(pCursr->elem);
  }
  return pCursr->elem!=0;
}

/*
** Get a new integer key.
*/
static int sqliteMemNew(DbbeCursor *pCursr){
  int iKey;
  Datum key;
  int go = 1;

  while( go ){
    iKey = sqliteRandomInteger() & 0x7fffffff;
    if( iKey==0 ) continue;
    key.p = (char*)&iKey;
    key.n = 4;
    go = ArrayFindElement(&pCursr->pTble->data, key)!=0;
  }
  return iKey;
}   

/*
** Write an entry into the table.  Overwrite any prior entry with the
** same key.
*/
static int sqliteMemPut(
  DbbeCursor *pCursr,       /* Write new entry into this database table */
  int nKey, char *pKey,     /* The key of the new entry */
  int nData, char *pData    /* The data of the new entry */
){
  Datum data, key;
  data.n = nData;
  data.p = sqliteMalloc( data.n );
  if( data.p==0 ) return SQLITE_NOMEM;
  memcpy(data.p, pData, data.n);
  key.n = nKey;
  key.p = pKey;
  assert( nKey==4 || pCursr->pTble->intKeyOnly==0 );
  data = ArrayInsert(&pCursr->pTble->data, key, data);
  if( data.p ){
    sqliteFree(data.p);
  }
  return SQLITE_OK;
}

/*
** Remove an entry from a table, if the entry exists.
*/
static int sqliteMemDelete(DbbeCursor *pCursr, int nKey, char *pKey){
  Datum key, data;
  key.n = nKey;
  key.p = pKey;
  data.p = 0;
  data.n = 0;
  data = ArrayInsert(&pCursr->pTble->data, key, data);
  if( data.p ){
    sqliteFree(data.p);
  }
  return SQLITE_OK;
}

/*
** Begin scanning an index for the given key.  Return 1 on success and
** 0 on failure.
*/
static int sqliteMemBeginIndex(DbbeCursor *pCursr, int nKey, char *pKey){
  if( !sqliteMemFetch(pCursr, nKey, pKey) ) return 0;
  pCursr->nextIndex = 0;
  return 1;
}

/*
** Return an integer key which is the next record number in the index search
** that was started by a prior call to BeginIndex.  Return 0 if all records
** have already been searched.
*/
static int sqliteMemNextIndex(DbbeCursor *pCursr){
  int *aIdx;
  int nIdx;
  int k;
  nIdx = sqliteMemDataLength(pCursr)/sizeof(int);
  aIdx = (int*)sqliteMemReadData(pCursr, 0);
  if( nIdx>1 ){
    k = *(aIdx++);
    if( k>nIdx-1 ) k = nIdx-1;
  }else{
    k = nIdx;
  }
  while( pCursr->nextIndex < k ){
    int recno = aIdx[pCursr->nextIndex++];
    if( recno!=0 ) return recno;
  }
  pCursr->nextIndex = 0;
  return 0;
}

/*
** Write a new record number and key into an index table.  Return a status
** code.
*/
static int sqliteMemPutIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  int r = sqliteMemFetch(pCursr, nKey, pKey);
  if( r==0 ){
    /* Create a new record for this index */
    sqliteMemPut(pCursr, nKey, pKey, sizeof(int), (char*)&N);
  }else{
    /* Extend the existing record */
    int nIdx;
    int *aIdx;
    int k;
            
    nIdx = sqliteMemDataLength(pCursr)/sizeof(int);
    if( nIdx==1 ){
      aIdx = sqliteMalloc( sizeof(int)*4 );
      if( aIdx==0 ) return SQLITE_NOMEM;
      aIdx[0] = 2;
      sqliteMemCopyData(pCursr, 0, sizeof(int), (char*)&aIdx[1]);
      aIdx[2] = N;
      sqliteMemPut(pCursr, nKey, pKey, sizeof(int)*4, (char*)aIdx);
      sqliteFree(aIdx);
    }else{
      aIdx = (int*)sqliteMemReadData(pCursr, 0);
      k = aIdx[0];
      if( k<nIdx-1 ){
        aIdx[k+1] = N;
        aIdx[0]++;
        sqliteMemPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
      }else{
        nIdx *= 2;
        aIdx = sqliteMalloc( sizeof(int)*nIdx );
        if( aIdx==0 ) return SQLITE_NOMEM;
        sqliteMemCopyData(pCursr, 0, sizeof(int)*(k+1), (char*)aIdx);
        aIdx[k+1] = N;
        aIdx[0]++;
        sqliteMemPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
        sqliteFree(aIdx);
      }
    }
  }
  return SQLITE_OK;
}

/*
** Delete an index entry.  Return a status code.
*/
static int sqliteMemDeleteIndex(DbbeCursor *pCursr,int nKey,char *pKey, int N){
  int *aIdx;
  int nIdx;
  int j, k;
  int rc;
  rc = sqliteMemFetch(pCursr, nKey, pKey);
  if( !rc ) return SQLITE_OK;
  nIdx = sqliteMemDataLength(pCursr)/sizeof(int);
  if( nIdx==0 ) return SQLITE_OK;
  aIdx = (int*)sqliteMemReadData(pCursr, 0);
  if( (nIdx==1 && aIdx[0]==N) || (aIdx[0]==1 && aIdx[1]==N) ){
    sqliteMemDelete(pCursr, nKey, pKey);
  }else{
    k = aIdx[0];
    for(j=1; j<=k && aIdx[j]!=N; j++){}
    if( j>k ) return SQLITE_OK;
    aIdx[j] = aIdx[k];
    aIdx[k] = 0;
    aIdx[0]--;
    if( aIdx[0]*3 + 1 < nIdx ){
      nIdx /= 2;
    }
    sqliteMemPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
  }
  return SQLITE_OK;
}

/*
** This variable contains pointers to all of the access methods
** used to implement the MEMORY backend.
*/
static struct DbbeMethods memoryMethods = {
  /*           Close */   sqliteMemClose,
  /*      OpenCursor */   sqliteMemOpenCursor,
  /*       DropTable */   sqliteMemDropTable,
  /* ReorganizeTable */   sqliteMemReorganizeTable,
  /*     CloseCursor */   sqliteMemCloseCursor,
  /*           Fetch */   sqliteMemFetch,
  /*            Test */   sqliteMemTest,
  /*         CopyKey */   sqliteMemCopyKey,
  /*        CopyData */   sqliteMemCopyData,
  /*         ReadKey */   sqliteMemReadKey,
  /*        ReadData */   sqliteMemReadData,
  /*       KeyLength */   sqliteMemKeyLength,
  /*      DataLength */   sqliteMemDataLength,
  /*         NextKey */   sqliteMemNextKey,
  /*          Rewind */   sqliteMemRewind,
  /*             New */   sqliteMemNew,
  /*             Put */   sqliteMemPut,
  /*          Delete */   sqliteMemDelete,
  /*      BeginTrans */   0,
  /*          Commit */   0,
  /*        Rollback */   0,
  /*      BeginIndex */   sqliteMemBeginIndex,
  /*       NextIndex */   sqliteMemNextIndex,
  /*        PutIndex */   sqliteMemPutIndex,
  /*     DeleteIndex */   sqliteMemDeleteIndex,
};

/*
** This routine opens a new database.  For the MEMORY driver
** implemented here, the database name is ignored.  Every MEMORY database
** is unique and is erased when the database is closed.
**
** If successful, a pointer to the Dbbe structure is returned.
** If there are errors, an appropriate error message is left
** in *pzErrMsg and NULL is returned.
*/
Dbbe *sqliteMemOpen(
  const char *zName,     /* The name of the database */
  int writeFlag,         /* True if we will be writing to the database */
  int createFlag,        /* True to create database if it doesn't exist */
  char **pzErrMsg        /* Write error messages (if any) here */
){
  Dbbex *pNew;

  pNew = sqliteMalloc( sizeof(*pNew) );
  if( pNew==0 ){
    sqliteSetString(pzErrMsg, "out of memory", 0);
    return 0;
  }
  ArrayInit(&pNew->tables);
  pNew->dbbe.x = &memoryMethods;
  return &pNew->dbbe;
}

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

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

    for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
      sqliteVdbeAddOp(v, OP_Open, base+i, pIdx->tnum, 0, 0);
    }
    end = sqliteVdbeMakeLabel(v);
    addr = sqliteVdbeAddOp(v, OP_ListRead, 0, end, 0, 0);
    if( pTab->pIndex ){
      sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_Fetch, base, 0, 0, 0);
      for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
        int j;
        sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
        for(j=0; j<pIdx->nColumn; j++){
          sqliteVdbeAddOp(v, OP_Field, base, pIdx->aiColumn[j], 0, 0);
        }
        sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
        sqliteVdbeAddOp(v, OP_DeleteIdx, base+i, 0, 0, 0);
      }
    }
    sqliteVdbeAddOp(v, OP_Delete, base, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions.
**
** $Id: expr.c,v 1.25 2001/07/23 14:33:04 drh Exp $
*/
#include "sqliteInt.h"

/*
** Walk an expression tree.  Return 1 if the expression is constant
** and 0 if it involves variables.
*/

      if( pExpr->pSelect ){
        /* Case 1:     expr IN (SELECT ...)
        **
        ** Generate code to write the results of the select into a temporary
        ** table.  The cursor number of the temporary table has already
        ** been put in iTable by sqliteExprResolveInSelect().
        */
        sqliteVdbeAddOp(v, OP_OpenIdx, pExpr->iTable, 1, 0, 0);
        if( sqliteSelect(pParse, pExpr->pSelect, SRT_Set, pExpr->iTable) );
      }else if( pExpr->pList ){
        /* Case 2:     expr IN (exprlist)
        **
        ** Create a set to put the exprlist values in.  The Set id is stored
        ** in iTable.
        */

    default: break;
  }
  switch( pExpr->op ){
    case TK_COLUMN: {
      if( pParse->useAgg ){
        sqliteVdbeAddOp(v, OP_AggGet, 0, pExpr->iAgg, 0, 0);
      }else if( pExpr->iColumn>=0 ){
        sqliteVdbeAddOp(v, OP_Field, pExpr->iTable, pExpr->iColumn, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_Key, pExpr->iTable, 0, 0, 0);
      }
      break;
    }
    case TK_INTEGER: {
      int i = atoi(pExpr->token.z);
      sqliteVdbeAddOp(v, OP_Integer, i, 0, 0, 0);
      break;

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

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

  ** all the code to implement the SELECT statement and leave the data
  ** in a temporary table.  If data is coming from an expression list,
  ** then we just have to count the number of expressions.
  */
  if( pSelect ){
    int rc;
    srcTab = pParse->nTab++;
    sqliteVdbeAddOp(v, OP_OpenTbl, srcTab, 1, 0, 0);
    rc = sqliteSelect(pParse, pSelect, SRT_Table, srcTab);
    if( rc || pParse->nErr || sqlite_malloc_failed ) goto insert_cleanup;
    assert( pSelect->pEList );
    nColumn = pSelect->pEList->nExpr;
  }else{
    assert( pList!=0 );
    srcTab = -1;

    }
  }

  /* Open cursors into the table that is received the new data and
  ** all indices of that table.
  */
  base = pParse->nTab;
  sqliteVdbeAddOp(v, OP_OpenTbl, base, 1, pTab->zName, 0);
  for(idx=1, pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext, idx++){
    sqliteVdbeAddOp(v, OP_OpenIdx, idx+base, 1, pIdx->zName, 0);
  }

  /* If the data source is a SELECT statement, then we have to create
  ** a loop because there might be multiple rows of data.  If the data
  ** source is an expression list, then exactly one row will be inserted
  ** and the loop is not used.
  */
  if( srcTab>=0 ){
    sqliteVdbeAddOp(v, OP_Rewind, srcTab, 0, 0, 0);
    iBreak = sqliteVdbeMakeLabel(v);
    iCont = sqliteVdbeAddOp(v, OP_Next, srcTab, iBreak, 0, 0);
  }

  /* Create a new entry in the table and fill it with data.
  */
  sqliteVdbeAddOp(v, OP_New, 0, 0, 0, 0);
  if( pTab->pIndex ){
    sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
  }
  for(i=0; i<pTab->nCol; i++){
    if( pColumn==0 ){
      j = i;
    }else{
      for(j=0; j<pColumn->nId; j++){
        if( pColumn->a[j].idx==i ) break;
      }
    }
    if( pColumn && j>=pColumn->nId ){
      char *zDflt = pTab->aCol[i].zDflt;
      if( zDflt==0 ){
        sqliteVdbeAddOp(v, OP_Null, 0, 0, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_String, 0, 0, zDflt, 0);
      }
    }else if( srcTab>=0 ){
      sqliteVdbeAddOp(v, OP_Field, srcTab, i, 0, 0); 
    }else{
      sqliteExprCode(pParse, pList->a[j].pExpr);
    }
  }
  sqliteVdbeAddOp(v, OP_MakeRecord, pTab->nCol, 0, 0, 0);
  sqliteVdbeAddOp(v, OP_Put, base, 0, 0, 0);

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

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

/*

      default: {
        if( pzErrMsg ){
          sqliteSetString(pzErrMsg, "unable to open database: ", zFilename, 0);
        }
      }
    }
    sqliteFree(db);
    return rc;
  }

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

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

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

     "/temp",
     "./temp",
  };
  int i;
  struct stat buf;
  for(i=0; i<sizeof(azDirs)/sizeof(azDirs[0]); i++){
    if( stat(azDirs[i], &buf)==0 && S_ISDIR(buf.st_mode)
         && S_IWUSR(buf.st_mode) ){
       return azDirs[i];
    }
  }
  return 0;
}

/*

    if( fd<0 ){
      fd = open(zFilename, O_RDONLY, 0);
      readOnly = 1;
    }
    tempFile = 0;
  }else{
    int cnt = 8;
    char *zDir = findTempDir();
    if( zDir==0 ) return SQLITE_CANTOPEN;
    do{
      cnt--;
      sprintf(zTemp,"%s/_sqlite_%u",(unsigned)sqliteRandomInteger());
      fd = open(zTemp, O_RDWR|O_CREAT|O_EXCL, 0600);
    }while( cnt>0 && fd<0 );
    zFilename = zTemp;
    tempFile = 1;
  }
  if( fd<0 ){
    return SQLITE_CANTOPEN;

};

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

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

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

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

  if( pEList ){
    for(i=0; i<pEList->nExpr; i++){
      sqliteExprCode(pParse, pEList->a[i].pExpr);
    }
    nColumn = pEList->nExpr;
  }else{
    for(i=0; i<nColumn; i++){
      sqliteVdbeAddOp(v, OP_Field, srcTab, i, 0, 0);
    }
  }

  /* If the DISTINCT keyword was present on the SELECT statement
  ** and this row has been seen before, then do not make this row
  ** part of the result.
  */

    sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
  }else 

  /* Store the result as data using a unique key.
  */
  if( eDest==SRT_Table ){
    sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_New, iParm, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Pull, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
  }else 

  /* Construct a record from the query result, but instead of
  ** saving that record, use it as a key to delete elements from
  ** the temporary table iParm.

** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.43 2001/09/13 13:46:57 drh Exp $
*/
#include "sqlite.h"
#include "vdbe.h"
#include "parse.h"
#ifndef DISABLE_GDBM
#include <gdbm.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*
** The paging system deals with 32-bit integers.

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

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

*/
struct Index {
  char *zName;     /* Name of this index */
  Index *pHash;    /* Next index with the same hash on zName */
  int nColumn;     /* Number of columns in the table used by this index */
  int *aiColumn;   /* Which columns are used by this index.  1st is 0 */
  Table *pTable;   /* The SQL table being indexed */

  int isUnique;    /* True if keys must all be unique */
  int isCommit;    /* True if creation of this index has been committed */
  int isDelete;    /* True if deletion of this index has not been comitted */
  Index *pNext;    /* The next index associated with the same table */
};

/*

void sqliteExprResolveInSelect(Parse*, Expr*);
int sqliteExprAnalyzeAggregates(Parse*, Expr*);
void sqliteParseInfoReset(Parse*);
Vdbe *sqliteGetVdbe(Parse*);
int sqliteRandomByte(void);
int sqliteRandomInteger(void);
void sqliteRandomName(char*,char*);
char *sqliteDbbeNameToFile(const char*,const char*,const char*);
void sqliteBeginTransaction(Parse*);
void sqliteCommitTransaction(Parse*);
void sqliteRollbackTransaction(Parse*);
char *sqlite_mprintf(const char *, ...);
const char *sqliteErrStr(int);

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

/*
** SQL is translated into a sequence of instructions to be
** executed by a virtual machine.  Each instruction is an instance

};

/*
** An instance of the virtual machine
*/
struct Vdbe {
  sqlite *db;         /* The whole database */
  Dbbe *pBe;          /* Opaque context structure used by DB backend */
  FILE *trace;        /* Write an execution trace here, if not NULL */
  int nOp;            /* Number of instructions in the program */
  int nOpAlloc;       /* Number of slots allocated for aOp[] */
  Op *aOp;            /* Space to hold the virtual machine's program */
  int nLabel;         /* Number of labels used */
  int nLabelAlloc;    /* Number of slots allocated in aLabel[] */
  int *aLabel;        /* Space to hold the labels */

/*
** Create a new virtual database engine.
*/
Vdbe *sqliteVdbeCreate(sqlite *db){
  Vdbe *p;
  p = sqliteMalloc( sizeof(Vdbe) );
  if( p==0 ) return 0;
  p->pBe = db->pBe;
  p->db = db;
  return p;
}

/*
** Turn tracing on or off
*/

  "Recno",             "FullKey",           "Rewind",            "Next",
  "Destroy",           "CreateIndex",       "CreateTable",       "Reorganize",
  "BeginIdx",          "NextIdx",           "PutIdx",            "DeleteIdx",
  "MemLoad",           "MemStore",          "ListOpen",          "ListWrite",
  "ListRewind",        "ListRead",          "ListClose",         "SortOpen",
  "SortPut",           "SortMakeRec",       "SortMakeKey",       "Sort",
  "SortNext",          "SortKey",           "SortCallback",      "SortClose",
  "FileOpen",          "FileRead",          "FileField",         "FileClose",
  "AggReset",          "AggFocus",          "AggIncr",           "AggNext",
  "AggSet",            "AggGet",            "SetInsert",         "SetFound",
  "SetNotFound",       "SetClear",          "MakeRecord",        "MakeKey",
  "Goto",              "If",                "Halt",              "ColumnCount",
  "ColumnName",        "Callback",          "Integer",           "String",
  "Null",              "Pop",               "Dup",               "Pull",
  "Add",               "AddImm",            "Subtract",          "Multiply",
  "Divide",            "Min",               "Max",               "Like",
  "Glob",              "Eq",                "Ne",                "Lt",
  "Le",                "Gt",                "Ge",                "IsNull",
  "NotNull",           "Negative",          "And",               "Or",
  "Not",               "Concat",            "Noop",              "Strlen",
  "Substr",          
};

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

  char **pzErrMsg,           /* Error msg written here */
  void *pBusyArg,            /* 1st argument to the busy callback */
  int (*xBusy)(void*,const char*,int)  /* Called when a file is busy */
){
  int pc;                    /* The program counter */
  Op *pOp;                   /* Current operation */
  int rc;                    /* Value to return */
  Dbbe *pBe = p->pBe;        /* The backend driver */
  sqlite *db = p->db;        /* The database */
  int rollbackOnError = 0;   /* If TRUE, rollback if the script fails.
  char **zStack;             /* Text stack */
  Stack *aStack;             /* Additional stack information */
  char zBuf[100];            /* Space to sprintf() an integer */


  /* No instruction ever pushes more than a single element onto the
  ** stack.  And the stack never grows on successive executions of the

      memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
      j += aStack[i].n-1;
    }
    if( i<p->tos ) zNewKey[j++] = '\t';
  }
  zNewKey[j++] = 0;
  Integerify(p, p->tos-nField);
  memcpy(&zNewKey[j], aStack[p->tos-nField].i, sizeof(int));
  PopStack(p, nField+1);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  zStack[p->tos] = zNewKey;
  break;
}

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

/* Opcode: Commit * * *
**
** Cause all modifications to the database that have been made since the
** last Transaction to actually take effect.  No additional modifications
** are allowed until another transaction is started.
*/
case OP_Commit: {
  rc = sqliteBtreeCommit(pBe);
  if( rc==SQLITE_OK ){
    sqliteCommitInternalChanges(db);
  }else{
    sqliteRollbackInternalChanges(db);
  }
  break;
}

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

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

    if( p->aCsr==0 ){ p->nCursor = 0; goto no_mem; }
    for(j=p->nCursor; j<=i; j++) p->aCsr[j].pCursor = 0;
    p->nCursor = i+1;
  }else if( p->aCsr[i].pCursor ){
    sqliteBtreeCloseCursor(p->aCsr[i].pCursor);
  }
  memset(&p->aCsr[i], 0, sizeof(Cursor));
  do {
    rc = sqliteBtreeOpenCursor(pBe, pOp->p2, &p->aCsr[i].pCursor);
    switch( rc ){
      case SQLITE_BUSY: {
        if( xBusy==0 || (*xBusy)(pBusyArg, pOp->p3, ++busy)==0 ){
          sqliteSetString(pzErrMsg, sqliteErrStr(rc), 0);
          busy = 0;
        }
        break;

**
** Open a new cursor that points to a table in a temporary database
** file.  The temporary file is opened read/write event if the main
** database is read-only.  The temporary file is deleted when the
** cursor is closed.
*/
case OP_OpenTemp: {
  int busy = 0;
  int i = pOp->p1;
  Cursor *pCx;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i>=p->nCursor ){
    int j;
    p->aCsr = sqliteRealloc( p->aCsr, (i+1)*sizeof(Cursor) );
    if( p->aCsr==0 ){ p->nCursor = 0; goto no_mem; }
    for(j=p->nCursor; j<=i; j++) p->aCsr[j].pCursor = 0;
    p->nCursor = i+1;
  }else if( p->aCsr[i].pCursor ){
    sqliteBtreeCloseCursor(p->aCsr[i].pCursor);
  }
  pCx = &p->aCsr[i];
  memset(pCx, 0, sizeof(*pCx));
  rc = sqliteBtreeOpen(0, 0, 100, &pCx->pBt);
  if( rc==SQLITE_OK ){
    rc = sqliteBtreeOpenCursor(pCx->pBt, 2, &pCx->pCursor);
  }
  if( rc==SQLITE_OK ){
    rc = sqliteBtreeBeginTrans(pCx->pBt);
  }
  break;
}

case OP_MoveTo: {
  int i = pOp->p1;
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
    int res;
    if( aStack[tos].flags & STK_Int ){
      sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(int), 
                     (char*)&aStack[tos].i, &res);
      p->aCsr[i].lastRecno = aStack[tos].i;
      p->aCsr[i].recnoIsValid = 1;
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      pBex->Fetch(p->aCsr[i].pCursor, aStack[tos].n, 
                     zStack[tos], &res);
      p->aCsr[i].recnoIsValid = 0;
    }
    p->nFetch++;
  }
  POPSTACK;
  break;
}

  int i = pOp->p1;
  int tos = p->tos;
  int alreadyExists = 0;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor ){
    int res, rx;
    if( aStack[tos].flags & STK_Int ){
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(int), 
                                    (char*)&aStack[tos].i, &res);
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor,aStack[tos].n, 
                                     zStack[tos], &res);
    }
    alreadyExists = rx==SQLITE_OK && res==0;
  }
  if( pOp->opcode==OP_Found ){
    if( alreadyExists ) pc = pOp->p2 - 1;
  }else{
    if( !alreadyExists ) pc = pOp->p2 - 1;

  if( VERIFY( i<0 || i>=p->nCursor || ) p->aCsr[i].pCursor==0 ){
    v = 0;
  }else{
    int res, rx, cnt;
    cnt = 0;
    do{
      v = sqliteRandomInteger();
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(v), &v, &res);
      cnt++;
    }while( cnt<10 && rx==SQLITE_OK && res==0 );
  }
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].i = v;
  aStack[p->tos].flags = STK_Int;

      if( Stringify(p, nos) ) goto no_mem;
      nKey = aStack[nos].n;
      zKey = zStack[nos];
    }else{
      nKey = sizeof(int);
      zKey = (char*)&aStack[nos].i;
    }
    rc = sqliteBtreeInsert(p->aCsr[i].pCursor, nKey, zKey,
                        aStack[tos].n, zStack[tos]);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
  }
  POPSTACK;
  POPSTACK;
  break;
}

/* Opcode: Delete P1 * *
**
** The top of the stack is a key.  Remove this key and its data
** from database file P1.  Then pop the stack to discard the key.
*/
case OP_Delete: {
  int tos = p->tos;
  int i = pOp->p1;

  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor!=0 ){
    char *zKey;
    int nKey;
    if( aStack[tos].flags & STK_Int ){
      nKey = sizeof(int);
      zKey = (char*)&aStack[tos].i;
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      nKey = aStack[tos].n;
      zKey = zStack[tos];
    }

    rc = sqliteBtreeDelete(p->aCsr[i].pCursor, nKey, zKey);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
  }
  POPSTACK;
  break;
}

/* Opcode: KeyAsData P1 P2 *
**

** "Concat 1 0 0") if it needs to persist longer than that.
**
** If the KeyAsData opcode has previously executed on this cursor,
** then the field might be extracted from the key rather than the
** data.
*/
case OP_Column: {
  int *pAddr;
  int amt, offset, nCol, payloadSize;
  int aHdr[10];
  const int mxHdr = sizeof(aHdr)/sizeof(aHdr[0]);
  int i = pOp->p1;
  int p2 = pOp->p2;
  int tos = ++p->tos;
  BtCursor *pCrsr;
  char *z;

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

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

    */
    (*xSize)(pCrsr, &payloadSize);
    if( payloadSize < sizeof(int)*(p2+1) ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
    }
    if( p2+1<mxHdr ){
      (*xRead)(pCrsr, 0, sizeof(aHdr[0])*(p2+2), aHdr);
      nCol = aHdr[0];
      offset = aHdr[p2];
      if( p2 == nCol-1 ){
        amt = payloadSize - offset;
      }else{
        amt = aHdr[p2+1] - offset;
      }
    }else{
      sqliteBtreeData(pCrsr, 0, sizeof(int), &nCol);
      nCol /= sizeof(int);
      if( p2 == nCol-1 ){
        (*xRead)(pCrsr, sizeof(int)*p2, sizeof(int), &offset);
        amt = payloadSize - offset;
      }else{
        (*xRead)(pCrsr, sizeof(int)*p2, sizeof(int)*2, aHdr);
        offset = aHdr[0];
        amt = aHdr[1] - offset;
      }
    }
    if( payloadSize < nCol || amt<0 || offset<0 ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;

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

    if( Stringify(p, tos) ) goto no_mem;
    pCrsr->nKey = aStack[tos].n;
    pCrsr->zKey = sqliteMalloc( 2*(pCrsr->nKey + 1) );
    if( pCrsr->zKey==0 ) goto no_mem;
    pCrsr->zBuf = &pCrsr->zKey[pCrsr->nKey+1];
    strncpy(pCrsr->zKey, zStack[tos], aStack[tos].n);
    pCrsr->zKey[aStack[tos].n] = 0;
    rx = sqliteBtreeMoveTo(pCrsr->pCursor, aStack[tos].n, zStack[tos], &res);
    pCrsr->atFirst = rx==SQLITE_OK && res>0;
    pCrsr->recnoIsValid = 0;
  }
  POPSTACK;
  break;
}

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

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

/* Opcode: PutIdx P1 * *
**
** The top of the stack hold an SQL index key made using the
** MakeIdxKey instruction.  This opcode writes that key into the
** index P1.  Data for the entry is nil.
*/
case OP_PutIdx: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    sqliteBtreePut(pCrsr, aStack[tos].n, zStack[tos], 0, "");
  }
  POPSTACK;
  break;
}

/* Opcode: DeleteIdx P1 * *
**
** The top of the stack is an index key built using the MakeIdxKey opcode.
** This opcode removes that entry from the index.
*/
case OP_DeleteIdx: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int rx, res;
    rx = sqliteBtreeMoveTo(pCrsr, aStack[tos].n, zStack[tos], &res);
    if( rx==SQLITE_OK && res==0 ){
      sqliteBtreeDelete(pCrsr);
    }
  }
  POPSTACK;
  break;
}

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

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

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

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

    }
#endif
  }

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

  /* Jump to here if a malloc() fails.  It's hard to get a malloc()
  ** to fail on a modern VM computer, so this code is untested.
  */
no_mem:
  sqliteSetString(pzErrMsg, "out or memory", 0);
  rc = SQLITE_NOMEM;
  goto cleanup;

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

  /* Jump to here if a operator is encountered that requires more stack
  ** operands than are currently available on the stack.
  */
not_enough_stack:

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

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

#define OP_SortNext           41
#define OP_SortKey            42
#define OP_SortCallback       43
#define OP_SortClose          44

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

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

**   http://www.hwaci.com/drh/
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.16 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.

  /* Open all tables in the pTabList and all indices in aIdx[].
  */
  for(i=0; i<pTabList->nId; i++){
    sqliteVdbeAddOp(v, OP_Open, base+i, pTabList->a[i].pTab->tnum,
         pTabList->a[i].pTab->zName, 0);
    if( i<ARRAYSIZE(aIdx) && aIdx[i]!=0 ){
      sqliteVdbeAddOp(v, OP_Open, base+pTabList->nId+i, aIdx[i]->tnum
          aIdx[i]->zName, 0);
    }
  }
  memcpy(pWInfo->aIdx, aIdx, sizeof(aIdx));

  /* Generate the code to do the search
  */

          break;
        }
      }
      sqliteVdbeAddOp(v, OP_AddImm, 0, 0, 0, 0);
      if( i==pTabList->nId-1 && pushKey ){
        haveKey = 1;
      }else{
        sqliteVdbeAddOp(v, OP_Fetch, base+idx, 0, 0, 0);
        haveKey = 0;
      }
    }else if( pIdx==0 ){
      /* Case 2:  There was no usable index.  We must do a complete
      ** scan of the table.
      */
      cont = sqliteVdbeMakeLabel(v);

      }
      sqliteVdbeAddOp(v, OP_MakeKey, pIdx->nColumn, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_BeginIdx, base+pTabList->nId+i, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_NextIdx, base+pTabList->nId+i, brk, 0, cont);
      if( i==pTabList->nId-1 && pushKey ){
        haveKey = 1;
      }else{
        sqliteVdbeAddOp(v, OP_Fetch, base+idx, 0, 0, 0);
        haveKey = 0;
      }
    }
    loopMask |= 1<<idx;

    /* Insert code to test every subexpression that can be completely
    ** computed using the current set of tables.
    */
    for(j=0; j<nExpr; j++){
      if( aExpr[j].p==0 ) continue;
      if( (aExpr[j].prereqRight & loopMask)!=aExpr[j].prereqRight ) continue;
      if( (aExpr[j].prereqLeft & loopMask)!=aExpr[j].prereqLeft ) continue;
      if( haveKey ){
        haveKey = 0;
        sqliteVdbeAddOp(v, OP_Fetch, base+idx, 0, 0, 0);
      }
      sqliteExprIfFalse(pParse, aExpr[j].p, cont);
      aExpr[j].p = 0;
    }
    brk = cont;
  }
  pWInfo->iContinue = cont;
  if( pushKey && !haveKey ){
    sqliteVdbeAddOp(v, OP_Key, base, 0, 0, 0);
  }
  sqliteFree(aOrder);
  return pWInfo;
}

/*
** Generate the end of the WHERE loop.

#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree2.test,v 1.4 2001/08/20 00:33:58 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl

if {[info commands btree_open]!=""} {

# Repeat this test sequence on database of various sizes
#
set testno 2
foreach {N L} {
  10 2
  50 2
  200 3

} {
#  2000 5
  puts "**** N=$N L=$L ****"
  set hash [md5file test2.bt]
  do_test btree2-$testno.1 [subst -nocommands {
    set ::c2 [btree_cursor $::b 2]
    set ::c3 [btree_cursor $::b 3]
    set ::c4 [btree_cursor $::b 4]
    set ::c5 [btree_cursor $::b 5]