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

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

  $(TOP)/src/dbbe.h \
  $(TOP)/src/dbbemem.c \
  $(TOP)/src/delete.c \
  $(TOP)/src/expr.c \
  $(TOP)/src/insert.c \
  $(TOP)/src/main.c \
  $(TOP)/src/parse.y \
................................................................................

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




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

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

parse.h:	parse.c

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

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

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

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

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

parse.h:	parse.c

1.0.12

1.0.13

** 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.19 2000/08/17 09:50:00 drh Exp $
*/
#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.
*/
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 holds the current state of the RC4 algorithm.
** We use RC4 as a random number generator.  Each call to RC4 gives
** a random 8-bit number.
**
** Nothing in this file or anywhere else in SQLite does any kind of
** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random
** number generator) not as an encryption device.
*/
struct rc4 {
  int i, j;
  int s[256];
};

/*
** The complete database is an instance of the following structure.
*/
struct Dbbe {
  char *zDir;        /* The directory containing the database */
  int write;         /* True for write permission */
  BeFile *pOpen;     /* List of open files */
  int nTemp;         /* Number of temporary files created */
  FILE **apTemp;     /* Space to hold temporary file pointers */
  char **azTemp;     /* Names of the temporary files */
  struct rc4 rc4;    /* The random number generator */
};

/*
** 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 {
  Dbbe *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 needRewind;    /* Next key should be the first */
  int readPending;   /* The fetch hasn't actually been done yet */
};

/*
** Initialize the RC4 PRNG.  "seed" is a pointer to some random
** data used to initialize the PRNG.  
*/
static void rc4init(struct rc4 *p, char *seed, int seedlen){
  int i;
  char k[256];
  p->j = 0;
  p->i = 0;
  for(i=0; i<256; i++){
    p->s[i] = i;
    k[i] = seed[i%seedlen];
  }
  for(i=0; i<256; i++){
    int t;
    p->j = (p->j + p->s[i] + k[i]) & 0xff;
    t = p->s[p->j];
    p->s[p->j] = p->s[i];
    p->s[i] = t;
  }
}

/*
** Get a single 8-bit random value from the RC4 PRNG.
*/
static int rc4byte(struct rc4 *p){
  int t;
  p->i = (p->i + 1) & 0xff;
  p->j = (p->j + p->s[p->i]) & 0xff;
  t = p->s[p->i];
  p->s[p->i] = p->s[p->j];
  p->s[p->j] = t;
  t = p->s[p->i] + p->s[p->j];
  return t & 0xff;
}

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

/*
** 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 *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 */
){
  Dbbe *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(Dbbe) + strlen(zName) + 1);
  if( pNew==0 ){
    sqliteSetString(pzErrMsg, "out of memory", 0);
    return 0;
  }
  pNew->zDir = (char*)&pNew[1];
  strcpy(pNew->zDir, zName);
  pNew->write = writeFlag;
  pNew->pOpen = 0;
  time(&statbuf.st_ctime);
  rc4init(&pNew->rc4, (char*)&statbuf, sizeof(statbuf));
  return pNew;
}

/*
** Completely shutdown the given database.  Close all files.  Free all memory.
*/
void sqliteDbbeClose(Dbbe *pBe){
  BeFile *pFile, *pNext;
  int i;
  for(pFile=pBe->pOpen; pFile; pFile=pNext){
    pNext = pFile->pNext;
    gdbm_close(pFile->dbf);
    memset(pFile, 0, sizeof(*pFile));   
    sqliteFree(pFile);
  }
  for(i=0; i<pBe->nTemp; i++){
    if( pBe->apTemp[i]!=0 ){
      unlink(pBe->azTemp[i]);
      fclose(pBe->apTemp[i]);
      sqliteFree(pBe->azTemp[i]);
      pBe->apTemp[i] = 0;
      pBe->azTemp[i] = 0;
      break;
    }
  }
  sqliteFree(pBe->azTemp);
  sqliteFree(pBe->apTemp);
  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(Dbbe *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;
}

/*
** Generate a random filename with the given prefix.  The new filename
** is written into zBuf[].  The calling function must insure that
** zBuf[] is big enough to hold the prefix plus 20 or so extra
** characters.
**
** Very random names are chosen so that the chance of a
** collision with an existing filename is very very small.
*/
static void randomName(struct rc4 *pRc4, char *zBuf, char *zPrefix){
  int i, j;
  static const char zRandomChars[] = "abcdefghijklmnopqrstuvwxyz0123456789";
  strcpy(zBuf, zPrefix);
  j = strlen(zBuf);
  for(i=0; i<15; i++){
    int c = rc4byte(pRc4) % (sizeof(zRandomChars) - 1);
    zBuf[j++] = zRandomChars[c];
  }
  zBuf[j] = 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 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.
*/
int sqliteDbbeOpenCursor(
  Dbbe *pBe,              /* 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 */
  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 */

  *ppCursr = 0;
  pCursr = sqliteMalloc( sizeof(*pCursr) );
  if( pCursr==0 ) return SQLITE_NOMEM;
  if( zTable ){
    zFile = sqliteFileOfTable(pBe, zTable);
    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;
      struct rc4 *pRc4;
      char zRandom[50];
      pRc4 = &pBe->rc4;
      zFile = 0;
      limit = 5;
      do {
        randomName(&pBe->rc4, 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;
    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 ){
    sqliteDbbeCloseCursor(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.
*/
void sqliteDbbeDropTable(Dbbe *pBe, const char *zTable){
  char *zFile;            /* Name of the table file */

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

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

  rc = sqliteDbbeOpenCursor(pBe, zTable, 1, &pCrsr);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  if( pCrsr && pCrsr->pFile && pCrsr->pFile->dbf ){
    gdbm_reorganize(pCrsr->pFile->dbf);
  }
  if( pCrsr ){
    sqliteDbbeCloseCursor(pCrsr);
  }
  return SQLITE_OK;
}

/*
** Close a cursor previously opened by sqliteDbbeOpenCursor().
**
** 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.
*/
void sqliteDbbeCloseCursor(DbbeCursor *pCursr){
  BeFile *pFile;
  Dbbe *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 ){
    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);
  }
  if( pCursr->key.dptr ) free(pCursr->key.dptr);
  if( pCursr->data.dptr ) free(pCursr->data.dptr);
  memset(pCursr, 0, sizeof(*pCursr));
  sqliteFree(pCursr);
}

/*
** 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.
*/
int sqliteDbbeFetch(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.
*/
int sqliteDbbeTest(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.
*/
int sqliteDbbeCopyKey(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;
}
int sqliteDbbeCopyData(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.
*/
char *sqliteDbbeReadKey(DbbeCursor *pCursr, int offset){
  if( offset<0 || offset>=pCursr->key.dsize ) return "";
  return &pCursr->key.dptr[offset];
}
char *sqliteDbbeReadData(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.
*/
int sqliteDbbeKeyLength(DbbeCursor *pCursr){
  return pCursr->key.dsize;
}
int sqliteDbbeDataLength(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.
*/
int sqliteDbbeRewind(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.
*/
int sqliteDbbeNextKey(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.
*/
int sqliteDbbeNew(DbbeCursor *pCursr){
  int iKey;
  datum key;
  int go = 1;
  int i;
  struct rc4 *pRc4;

  if( pCursr->pFile==0 || pCursr->pFile->dbf==0 ) return 1;
  pRc4 = &pCursr->pBe->rc4;
  while( go ){
    iKey = 0;
    for(i=0; i<4; i++){
      iKey = (iKey<<8) + rc4byte(pRc4);
    }
    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.
*/
int sqliteDbbePut(DbbeCursor *pCursr, int nKey,char *pKey,int nData,char *pData){
  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.
*/
int sqliteDbbeDelete(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;
}

/*
** Open a temporary file.  The file should be deleted when closed.
**
** Note that we can't use the old Unix trick of opening the file
** and then immediately unlinking the file.  That works great
** under Unix, but fails when we try to port to Windows.
*/
int sqliteDbbeOpenTempFile(Dbbe *pBe, FILE **ppFile){
  char *zFile;         /* Full name of the temporary file */
  char zBuf[50];       /* Base name of the temporary file */
  int i;               /* Loop counter */
  int limit;           /* Prevent an infinite loop */
  int rc = SQLITE_OK;  /* Value returned by this function */

  for(i=0; i<pBe->nTemp; i++){
    if( pBe->apTemp[i]==0 ) break;
  }
  if( i>=pBe->nTemp ){
    pBe->nTemp++;
    pBe->apTemp = sqliteRealloc(pBe->apTemp, pBe->nTemp*sizeof(FILE*) );
    pBe->azTemp = sqliteRealloc(pBe->azTemp, pBe->nTemp*sizeof(char*) );
  }
  if( pBe->apTemp==0 ){
    *ppFile = 0;
    return SQLITE_NOMEM;
  }
  limit = 4;
  zFile = 0;
  do{
    randomName(&pBe->rc4, zBuf, "/_temp_file_");
    sqliteFree(zFile);
    zFile = 0;
    sqliteSetString(&zFile, pBe->zDir, zBuf, 0);
  }while( access(zFile,0)==0 && limit-- >= 0 );
  *ppFile = pBe->apTemp[i] = fopen(zFile, "w+");
  if( pBe->apTemp[i]==0 ){
    rc = SQLITE_ERROR;
    sqliteFree(zFile);
    pBe->azTemp[i] = 0;
  }else{
    pBe->azTemp[i] = zFile;
  }
  return rc;
}

/*
** Close a temporary file opened using sqliteDbbeOpenTempFile()
*/
void sqliteDbbeCloseTempFile(Dbbe *pBe, FILE *f){
  int i;
  for(i=0; i<pBe->nTemp; i++){
    if( pBe->apTemp[i]==f ){
      unlink(pBe->azTemp[i]);
      sqliteFree(pBe->azTemp[i]);
      pBe->apTemp[i] = 0;
      pBe->azTemp[i] = 0;
      break;
    }
  }
  fclose(f);
}

** 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.20 2000/10/19 01:49:02 drh Exp $
*/
#include "sqliteInt.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 *sqliteGdbmOpen(const char*,int,int,char**);
  if( strncmp(zName, "gdbm:", 5)==0 ){
    return sqliteGdbmOpen(&zName[5], writeFlag, createFlag, pzErrMsg);
  }








#if 0
  if( strncmp(zName, "memory:", 7)==0 ){
    extern Dbbe *sqliteMemOpen(const char*,int,int,char**);
    return sqliteMemOpen(&zName[7], writeFlag, createFlag, pzErrMsg);
  }
#endif
  return sqliteGdbmOpen(zName, writeFlag, createFlag, pzErrMsg);
}

** 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.7 2000/08/17 09:50:00 drh Exp $
*/
#ifndef _SQLITE_DBBE_H_
#define _SQLITE_DBBE_H_
#include <stdio.h>

/*
** The database backend supports two opaque structures.  A Dbbe is
................................................................................
** 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;


/*
** The 18 interface routines.





*/

/* Open a complete database */
Dbbe *sqliteDbbeOpen(const char *zName, int write, int create, char **pzErr);






/* Close the whole database. */
void sqliteDbbeClose(Dbbe*);


/* Open a cursor into particular file of a previously opened database.
** Create the file if it doesn't already exist and writeable!=0.  zName
** is the base name of the file to be opened.  This routine will add
** an appropriate path and extension to the filename to locate the 
** actual file.
**
** If zName is 0 or "", then a temporary file is created that
** will be deleted when closed.
*/
int sqliteDbbeOpenCursor(Dbbe*, const char *zName, int writeable, DbbeCursor**);

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

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

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

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

/* Return 1 if the given key is already in the table.  Return 0
** if it is not.
*/
int sqliteDbbeTest(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 sqliteDbbeCopyKey(DbbeCursor*, int offset, int size, char *zBuf);
int sqliteDbbeCopyData(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 *sqliteDbbeReadKey(DbbeCursor*, int offset);
char *sqliteDbbeReadData(DbbeCursor*, int offset);

/* Return the length of the most recently fetched key or data. */
int sqliteDbbeKeyLength(DbbeCursor*);
int sqliteDbbeDataLength(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
** sqliteDbbeRewind().  The return value is 1 if there is another
** entry, or 0 if there are no more entries. */
int sqliteDbbeNextKey(DbbeCursor*);

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

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

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

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

/* Open a file suitable for temporary storage */
int sqliteDbbeOpenTempFile(Dbbe*, FILE**);

/* Close a temporary file */
void sqliteDbbeCloseTempFile(Dbbe *, FILE *);


#endif /* defined(_SQLITE_DBBE_H_) */

** 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.8 2000/10/19 01:49:02 drh Exp $
*/
#ifndef _SQLITE_DBBE_H_
#define _SQLITE_DBBE_H_
#include <stdio.h>

/*
** The database backend supports two opaque structures.  A Dbbe is
................................................................................
** 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;


/*

** 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);

/*
** This is the structure returned by sqliteDbbeOpen().  It contains pointers
** to all access routines for the database backend.
*/
struct Dbbe {
  /* Close the whole database. */

  void (*Close)(Dbbe*);

  /* Open a cursor into particular file of a previously opened database.
  ** Create the file if it doesn't already exist and writeable!=0.  zName
  ** is the base name of the file to be opened.  This routine will add
  ** an appropriate path and extension to the filename to locate the 
  ** actual file.
  **
  ** If zName is 0 or "", then a temporary file is created that
  ** will be deleted when closed.
  */
  int (*OpenCursor)(Dbbe*, const char *zName, int writeable, 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);

  /* Open a file suitable for temporary storage */
  int (*OpenTempFile)(Dbbe*, FILE**);

  /* Close a temporary file */
  void (*CloseTempFile)(Dbbe *, FILE *);
};

#endif /* defined(_SQLITE_DBBE_H_) */

/*
** 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.1 2000/10/19 01:49:02 drh Exp $
*/
#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.
*/
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 holds the current state of the RC4 algorithm.
** We use RC4 as a random number generator.  Each call to RC4 gives
** a random 8-bit number.
**
** Nothing in this file or anywhere else in SQLite does any kind of
** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random
** number generator) not as an encryption device.
*/
struct rc4 {
  int i, j;
  int s[256];
};

/*
** 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 */
  char *zDir;        /* The directory containing the database */
  int write;         /* True for write permission */
  BeFile *pOpen;     /* List of open files */
  int nTemp;         /* Number of temporary files created */
  FILE **apTemp;     /* Space to hold temporary file pointers */
  char **azTemp;     /* Names of the temporary files */
  struct rc4 rc4;    /* The random number generator */
};

/*
** 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 needRewind;    /* Next key should be the first */
  int readPending;   /* The fetch hasn't actually been done yet */
};

/*
** Initialize the RC4 PRNG.  "seed" is a pointer to some random
** data used to initialize the PRNG.  
*/
static void rc4init(struct rc4 *p, char *seed, int seedlen){
  int i;
  char k[256];
  p->j = 0;
  p->i = 0;
  for(i=0; i<256; i++){
    p->s[i] = i;
    k[i] = seed[i%seedlen];
  }
  for(i=0; i<256; i++){
    int t;
    p->j = (p->j + p->s[i] + k[i]) & 0xff;
    t = p->s[p->j];
    p->s[p->j] = p->s[i];
    p->s[i] = t;
  }
}

/*
** Get a single 8-bit random value from the RC4 PRNG.
*/
static int rc4byte(struct rc4 *p){
  int t;
  p->i = (p->i + 1) & 0xff;
  p->j = (p->j + p->s[p->i]) & 0xff;
  t = p->s[p->i];
  p->s[p->i] = p->s[p->j];
  p->s[p->j] = t;
  t = p->s[p->i] + p->s[p->j];
  return t & 0xff;
}

/*
** 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;
  int i;
  for(pFile=pBe->pOpen; pFile; pFile=pNext){
    pNext = pFile->pNext;
    gdbm_close(pFile->dbf);
    memset(pFile, 0, sizeof(*pFile));   
    sqliteFree(pFile);
  }
  for(i=0; i<pBe->nTemp; i++){
    if( pBe->apTemp[i]!=0 ){
      unlink(pBe->azTemp[i]);
      fclose(pBe->apTemp[i]);
      sqliteFree(pBe->azTemp[i]);
      pBe->apTemp[i] = 0;
      pBe->azTemp[i] = 0;
      break;
    }
  }
  sqliteFree(pBe->azTemp);
  sqliteFree(pBe->apTemp);
  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;
}

/*
** Generate a random filename with the given prefix.  The new filename
** is written into zBuf[].  The calling function must insure that
** zBuf[] is big enough to hold the prefix plus 20 or so extra
** characters.
**
** Very random names are chosen so that the chance of a
** collision with an existing filename is very very small.
*/
static void randomName(struct rc4 *pRc4, char *zBuf, char *zPrefix){
  int i, j;
  static const char zRandomChars[] = "abcdefghijklmnopqrstuvwxyz0123456789";
  strcpy(zBuf, zPrefix);
  j = strlen(zBuf);
  for(i=0; i<15; i++){
    int c = rc4byte(pRc4) % (sizeof(zRandomChars) - 1);
    zBuf[j++] = zRandomChars[c];
  }
  zBuf[j] = 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 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 */
  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;

  *ppCursr = 0;
  pCursr = sqliteMalloc( sizeof(*pCursr) );
  if( pCursr==0 ) return SQLITE_NOMEM;
  if( zTable ){
    zFile = sqliteFileOfTable(pBe, zTable);
    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;
      struct rc4 *pRc4;
      char zRandom[50];
      pRc4 = &pBe->rc4;
      zFile = 0;
      limit = 5;
      do {
        randomName(&pBe->rc4, 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;
    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);
}

/*
** 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 ){
    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);
  }
  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 *pCrsr;
  int rc;

  rc = sqliteGdbmOpenCursor(pBe, zTable, 1, &pCrsr);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  if( pCrsr && pCrsr->pFile && pCrsr->pFile->dbf ){
    gdbm_reorganize(pCrsr->pFile->dbf);
  }
  if( pCrsr ){
    sqliteGdbmCloseCursor(pCrsr);
  }
  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;
  int i;
  struct rc4 *pRc4;

  if( pCursr->pFile==0 || pCursr->pFile->dbf==0 ) return 1;
  pRc4 = &pCursr->pBe->rc4;
  while( go ){
    iKey = 0;
    for(i=0; i<4; i++){
      iKey = (iKey<<8) + rc4byte(pRc4);
    }
    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, int nKey,char *pKey,int nData,char *pData){
  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;
}

/*
** Open a temporary file.  The file should be deleted when closed.
**
** Note that we can't use the old Unix trick of opening the file
** and then immediately unlinking the file.  That works great
** under Unix, but fails when we try to port to Windows.
*/
static int sqliteGdbmOpenTempFile(Dbbe *pDbbe, FILE **ppFile){
  char *zFile;         /* Full name of the temporary file */
  char zBuf[50];       /* Base name of the temporary file */
  int i;               /* Loop counter */
  int limit;           /* Prevent an infinite loop */
  int rc = SQLITE_OK;  /* Value returned by this function */
  Dbbex *pBe = (Dbbex*)pDbbe;

  for(i=0; i<pBe->nTemp; i++){
    if( pBe->apTemp[i]==0 ) break;
  }
  if( i>=pBe->nTemp ){
    pBe->nTemp++;
    pBe->apTemp = sqliteRealloc(pBe->apTemp, pBe->nTemp*sizeof(FILE*) );
    pBe->azTemp = sqliteRealloc(pBe->azTemp, pBe->nTemp*sizeof(char*) );
  }
  if( pBe->apTemp==0 ){
    *ppFile = 0;
    return SQLITE_NOMEM;
  }
  limit = 4;
  zFile = 0;
  do{
    randomName(&pBe->rc4, zBuf, "/_temp_file_");
    sqliteFree(zFile);
    zFile = 0;
    sqliteSetString(&zFile, pBe->zDir, zBuf, 0);
  }while( access(zFile,0)==0 && limit-- >= 0 );
  *ppFile = pBe->apTemp[i] = fopen(zFile, "w+");
  if( pBe->apTemp[i]==0 ){
    rc = SQLITE_ERROR;
    sqliteFree(zFile);
    pBe->azTemp[i] = 0;
  }else{
    pBe->azTemp[i] = zFile;
  }
  return rc;
}

/*
** Close a temporary file opened using sqliteGdbmOpenTempFile()
*/
static void sqliteGdbmCloseTempFile(Dbbe *pDbbe, FILE *f){
  int i;
  Dbbex *pBe = (Dbbex*)pDbbe;
  for(i=0; i<pBe->nTemp; i++){
    if( pBe->apTemp[i]==f ){
      unlink(pBe->azTemp[i]);
      sqliteFree(pBe->azTemp[i]);
      pBe->apTemp[i] = 0;
      pBe->azTemp[i] = 0;
      break;
    }
  }
  fclose(f);
}


/*
** 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.Close = sqliteGdbmClose;
  pNew->dbbe.OpenCursor = sqliteGdbmOpenCursor;
  pNew->dbbe.DropTable = sqliteGdbmDropTable;
  pNew->dbbe.ReorganizeTable = sqliteGdbmReorganizeTable;
  pNew->dbbe.CloseCursor = sqliteGdbmCloseCursor;
  pNew->dbbe.Fetch = sqliteGdbmFetch;
  pNew->dbbe.Test = sqliteGdbmTest;
  pNew->dbbe.CopyKey = sqliteGdbmCopyKey;
  pNew->dbbe.CopyData = sqliteGdbmCopyData;
  pNew->dbbe.ReadKey = sqliteGdbmReadKey;
  pNew->dbbe.ReadData = sqliteGdbmReadData;
  pNew->dbbe.KeyLength = sqliteGdbmKeyLength;
  pNew->dbbe.DataLength = sqliteGdbmDataLength;
  pNew->dbbe.NextKey = sqliteGdbmNextKey;
  pNew->dbbe.Rewind = sqliteGdbmRewind;
  pNew->dbbe.New = sqliteGdbmNew;
  pNew->dbbe.Put = sqliteGdbmPut;
  pNew->dbbe.Delete = sqliteGdbmDelete;
  pNew->dbbe.OpenTempFile = sqliteGdbmOpenTempFile;
  pNew->dbbe.CloseTempFile = sqliteGdbmCloseTempFile;
  pNew->zDir = (char*)&pNew[1];
  strcpy(pNew->zDir, zName);
  pNew->write = writeFlag;
  pNew->pOpen = 0;
  time(&statbuf.st_ctime);
  rc4init(&pNew->rc4, (char*)&statbuf, sizeof(statbuf));
  return &pNew->dbbe;
}

**
*************************************************************************
** 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.20 2000/10/16 22:06:42 drh Exp $
*/
#include "sqliteInt.h"

/*
** This is the callback routine for the code that initializes the
** database.  Each callback contains text of a CREATE TABLE or
** CREATE INDEX statement that must be parsed to yield the internal
................................................................................
}

/*
** Close an existing SQLite database
*/
void sqlite_close(sqlite *db){
  int i;
  sqliteDbbeClose(db->pBe);
  for(i=0; i<N_HASH; i++){
    Table *pNext, *pList = db->apTblHash[i];
    db->apTblHash[i] = 0;
    while( pList ){
      pNext = pList->pHash;
      pList->pHash = 0;
      sqliteDeleteTable(db, pList);

**
*************************************************************************
** 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.21 2000/10/19 01:49:02 drh Exp $
*/
#include "sqliteInt.h"

/*
** This is the callback routine for the code that initializes the
** database.  Each callback contains text of a CREATE TABLE or
** CREATE INDEX statement that must be parsed to yield the internal
................................................................................
}

/*
** Close an existing SQLite database
*/
void sqlite_close(sqlite *db){
  int i;
  db->pBe->Close(db->pBe);
  for(i=0; i<N_HASH; i++){
    Table *pNext, *pList = db->apTblHash[i];
    db->apTblHash[i] = 0;
    while( pList ){
      pNext = pList->pHash;
      pList->pHash = 0;
      sqliteDeleteTable(db, pList);

** 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.43 2000/10/16 22:06:43 drh Exp $
*/
#include "sqliteInt.h"
#include <unistd.h>
#include <ctype.h>

/*
** SQL is translated into a sequence of instructions to be
................................................................................
static void Cleanup(Vdbe *p){
  int i;
  PopStack(p, p->tos+1);
  sqliteFree(p->azColName);
  p->azColName = 0;
  for(i=0; i<p->nCursor; i++){
    if( p->aCsr[i].pCursor ){
      sqliteDbbeCloseCursor(p->aCsr[i].pCursor);
      p->aCsr[i].pCursor = 0;
    }
  }
  sqliteFree(p->aCsr);
  p->aCsr = 0;
  p->nCursor = 0;
  for(i=0; i<p->nMem; i++){
................................................................................
    }
  }
  sqliteFree(p->aMem);
  p->aMem = 0;
  p->nMem = 0;
  for(i=0; i<p->nList; i++){
    if( p->apList[i] ){
      sqliteDbbeCloseTempFile(p->pBe, p->apList[i]);
      p->apList[i] = 0;
    }
  }
  sqliteFree(p->apList);
  p->apList = 0;
  p->nList = 0;
  for(i=0; i<p->nSort; i++){
................................................................................
  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 */

  char zBuf[100];            /* Space to sprintf() and integer */

  p->tos = -1;
  rc = SQLITE_OK;
#ifdef MEMORY_DEBUG
  if( access("vdbe_trace",0)==0 ){
    p->trace = stderr;
................................................................................
        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 ){
          sqliteDbbeCloseCursor(p->aCsr[i].pCursor);
        }
        do {
          rc = sqliteDbbeOpenCursor(p->pBe,pOp->p3,pOp->p2,&p->aCsr[i].pCursor);
          switch( rc ){
            case SQLITE_BUSY: {
              if( xBusy==0 || (*xBusy)(pBusyArg, pOp->p3, ++busy)==0 ){
                sqliteSetString(pzErrMsg,"table ", pOp->p3, " is locked", 0);
                busy = 0;
              }
              break;
................................................................................
      **
      ** Close a cursor previously opened as P1.  If P1 is not
      ** currently open, this instruction is a no-op.
      */
      case OP_Close: {
        int i = pOp->p1;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
          sqliteDbbeCloseCursor(p->aCsr[i].pCursor);
          p->aCsr[i].pCursor = 0;
        }
        break;
      }

      /* Opcode: Fetch P1 * *
      **
................................................................................
      */
      case OP_Fetch: {
        int i = pOp->p1;
        int tos = p->tos;
        if( tos<0 ) goto not_enough_stack;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
          if( p->aStack[tos].flags & STK_Int ){
            sqliteDbbeFetch(p->aCsr[i].pCursor, sizeof(int), 
                           (char*)&p->aStack[tos].i);
          }else{
            if( Stringify(p, tos) ) goto no_mem;
            sqliteDbbeFetch(p->aCsr[i].pCursor, p->aStack[tos].n, 
                           p->zStack[tos]);
          }
          p->nFetch++;
        }
        PopStack(p, 1);
        break;
      }
................................................................................
      case OP_Found: {
        int i = pOp->p1;
        int tos = p->tos;
        int alreadyExists = 0;
        if( tos<0 ) goto not_enough_stack;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
          if( p->aStack[tos].flags & STK_Int ){
            alreadyExists = sqliteDbbeTest(p->aCsr[i].pCursor, sizeof(int), 
                                          (char*)&p->aStack[tos].i);
          }else{
            if( Stringify(p, tos) ) goto no_mem;
            alreadyExists = sqliteDbbeTest(p->aCsr[i].pCursor,p->aStack[tos].n, 
                                           p->zStack[tos]);
          }
        }
        if( pOp->opcode==OP_Found ){
          if( alreadyExists ) pc = pOp->p2 - 1;
        }else{
          if( !alreadyExists ) pc = pOp->p2 - 1;
................................................................................
      */
      case OP_New: {
        int i = pOp->p1;
        int v;
        if( i<0 || i>=p->nCursor || p->aCsr[i].pCursor==0 ){
          v = 0;
        }else{
          v = sqliteDbbeNew(p->aCsr[i].pCursor);
        }
        NeedStack(p, p->tos+1);
        p->tos++;
        p->aStack[p->tos].i = v;
        p->aStack[p->tos].flags = STK_Int;
        break;
      }
................................................................................
            if( Stringify(p, nos) ) goto no_mem;
            nKey = p->aStack[nos].n;
            zKey = p->zStack[nos];
          }else{
            nKey = sizeof(int);
            zKey = (char*)&p->aStack[nos].i;
          }
          sqliteDbbePut(p->aCsr[i].pCursor, nKey, zKey,
                        p->aStack[tos].n, p->zStack[tos]);
        }
        PopStack(p, 2);
        break;
      }

      /* Opcode: Delete P1 * *
................................................................................
            nKey = sizeof(int);
            zKey = (char*)&p->aStack[tos].i;
          }else{
            if( Stringify(p, tos) ) goto no_mem;
            nKey = p->aStack[tos].n;
            zKey = p->zStack[tos];
          }
          sqliteDbbeDelete(p->aCsr[i].pCursor, nKey, zKey);
        }
        PopStack(p, 1);
        break;
      }

      /* Opcode: KeyAsData P1 P2 *
      **
................................................................................
        int tos = ++p->tos;
        DbbeCursor *pCrsr;
        char *z;

        if( NeedStack(p, tos) ) goto no_mem;
        if( i>=0 && i<p->nCursor && (pCrsr = p->aCsr[i].pCursor)!=0 ){
          if( p->aCsr[i].keyAsData ){
            amt = sqliteDbbeKeyLength(pCrsr);
            if( amt<=sizeof(int)*(p2+1) ){
              p->aStack[tos].flags = STK_Null;
              break;
            }
            pAddr = (int*)sqliteDbbeReadKey(pCrsr, sizeof(int)*p2);
            if( *pAddr==0 ){
              p->aStack[tos].flags = STK_Null;
              break;
            }
            z = sqliteDbbeReadKey(pCrsr, *pAddr);
          }else{
            amt = sqliteDbbeDataLength(pCrsr);
            if( amt<=sizeof(int)*(p2+1) ){
              p->aStack[tos].flags = STK_Null;
              break;
            }
            pAddr = (int*)sqliteDbbeReadData(pCrsr, sizeof(int)*p2);
            if( *pAddr==0 ){
              p->aStack[tos].flags = STK_Null;
              break;
            }
            z = sqliteDbbeReadData(pCrsr, *pAddr);
          }
          p->zStack[tos] = z;
          p->aStack[tos].n = strlen(z) + 1;
          p->aStack[tos].flags = STK_Str;
        }
        break;
      }
................................................................................
      case OP_Key: {
        int i = pOp->p1;
        int tos = ++p->tos;
        DbbeCursor *pCrsr;

        if( NeedStack(p, p->tos) ) goto no_mem;
        if( i>=0 && i<p->nCursor && (pCrsr = p->aCsr[i].pCursor)!=0 ){
          char *z = sqliteDbbeReadKey(pCrsr, 0);
          if( p->aCsr[i].keyAsData ){
            p->zStack[tos] = z;
            p->aStack[tos].flags = STK_Str;
            p->aStack[tos].n = sqliteDbbeKeyLength(pCrsr);
          }else{
            memcpy(&p->aStack[tos].i, z, sizeof(int));
            p->aStack[tos].flags = STK_Int;
          }
        }
        break;
      }
................................................................................
      **
      ** The next use of the Key or Field or Next instruction for P1 
      ** will refer to the first entry in the database file.
      */
      case OP_Rewind: {
        int i = pOp->p1;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor!=0 ){
          sqliteDbbeRewind(p->aCsr[i].pCursor);
        }
        break;
      }

      /* Opcode: Next P1 P2 *
      **
      ** Advance P1 to the next key/data pair in the file.  Or, if there are no
      ** more key/data pairs, rewind P1 and jump to location P2.
      */
      case OP_Next: {
        int i = pOp->p1;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor!=0 ){
          if( sqliteDbbeNextKey(p->aCsr[i].pCursor)==0 ){
            pc = pOp->p2 - 1;
          }else{
            p->nFetch++;
          }
        }
        break;
      }
................................................................................

        if( NeedStack(p, p->tos) ) goto no_mem;
        p->zStack[tos] = 0;
        if( i>=0 && i<p->nCursor && (pCrsr = p->aCsr[i].pCursor)!=0 ){
          int *aIdx;
          int nIdx;
          int j, k;
          nIdx = sqliteDbbeDataLength(pCrsr)/sizeof(int);
          aIdx = (int*)sqliteDbbeReadData(pCrsr, 0);
          if( nIdx>1 ){
            k = *(aIdx++);
            if( k>nIdx-1 ) k = nIdx-1;
          }else{
            k = nIdx;
          }
          for(j=p->aCsr[i].index; j<k; j++){
................................................................................
        if( nos<0 ) goto not_enough_stack;
        if( i>=0 && i<p->nCursor && (pCrsr = p->aCsr[i].pCursor)!=0 ){
          int r;
          int newVal;
          Integerify(p, nos);
          newVal = p->aStack[nos].i;
          if( Stringify(p, tos) ) goto no_mem;
          r = sqliteDbbeFetch(pCrsr, p->aStack[tos].n, p->zStack[tos]);
          if( r==0 ){
            /* Create a new record for this index */
            sqliteDbbePut(pCrsr, p->aStack[tos].n, p->zStack[tos],
                          sizeof(int), (char*)&newVal);
          }else{
            /* Extend the existing record */
            int nIdx;
            int *aIdx;
            int k;
            
            nIdx = sqliteDbbeDataLength(pCrsr)/sizeof(int);
            if( nIdx==1 ){
              aIdx = sqliteMalloc( sizeof(int)*4 );
              if( aIdx==0 ) goto no_mem;
              aIdx[0] = 2;
              sqliteDbbeCopyData(pCrsr, 0, sizeof(int), (char*)&aIdx[1]);
              aIdx[2] = newVal;
              sqliteDbbePut(pCrsr, p->aStack[tos].n, p->zStack[tos],
                    sizeof(int)*4, (char*)aIdx);
              sqliteFree(aIdx);
            }else{
              aIdx = (int*)sqliteDbbeReadData(pCrsr, 0);
              k = aIdx[0];
              if( k<nIdx-1 ){
                aIdx[k+1] = newVal;
                aIdx[0]++;
                sqliteDbbePut(pCrsr, p->aStack[tos].n, p->zStack[tos],
                    sizeof(int)*nIdx, (char*)aIdx);
              }else{
                nIdx *= 2;
                aIdx = sqliteMalloc( sizeof(int)*nIdx );
                if( aIdx==0 ) goto no_mem;
                sqliteDbbeCopyData(pCrsr, 0, sizeof(int)*(k+1), (char*)aIdx);
                aIdx[k+1] = newVal;
                aIdx[0]++;
                sqliteDbbePut(pCrsr, p->aStack[tos].n, p->zStack[tos],
                      sizeof(int)*nIdx, (char*)aIdx);
                sqliteFree(aIdx);
              }
            }              
          }
        }
        PopStack(p, 2);
................................................................................
          int nIdx;
          int j, k;
          int r;
          int oldVal;
          Integerify(p, nos);
          oldVal = p->aStack[nos].i;
          if( Stringify(p, tos) ) goto no_mem;
          r = sqliteDbbeFetch(pCrsr, p->aStack[tos].n, p->zStack[tos]);
          if( r==0 ) break;
          nIdx = sqliteDbbeDataLength(pCrsr)/sizeof(int);
          aIdx = (int*)sqliteDbbeReadData(pCrsr, 0);
          if( (nIdx==1 && aIdx[0]==oldVal) || (aIdx[0]==1 && aIdx[1]==oldVal) ){
            sqliteDbbeDelete(pCrsr, p->aStack[tos].n, p->zStack[tos]);
          }else{
            k = aIdx[0];
            for(j=1; j<=k && aIdx[j]!=oldVal; j++){}
            if( j>k ) break;
            aIdx[j] = aIdx[k];
            aIdx[k] = 0;
            aIdx[0]--;
            if( aIdx[0]*3 + 1 < nIdx ){
              nIdx /= 2;
            }
            sqliteDbbePut(pCrsr, p->aStack[tos].n, p->zStack[tos], 
                          sizeof(int)*nIdx, (char*)aIdx);
          }
        }
        PopStack(p, 2);
        break;
      }

................................................................................
      /* Opcode: Destroy * * P3
      **
      ** Drop the disk file whose name is P3.  All key/data pairs in
      ** the file are deleted and the file itself is removed
      ** from the disk.
      */
      case OP_Destroy: {
        sqliteDbbeDropTable(p->pBe, pOp->p3);
        break;
      }

      /* Opcode: Reorganize * * P3
      **
      ** Compress, optimize, and tidy up the GDBM file named by P3.
      */
      case OP_Reorganize: {
        sqliteDbbeReorganizeTable(p->pBe, pOp->p3);
        break;
      }

      /* Opcode: ListOpen P1 * *
      **
      ** Open a file used for temporary storage of integer table keys.  P1
      ** will server as a handle to this temporary file for future
................................................................................
        if( i>=p->nList ){
          int j;
          p->apList = sqliteRealloc( p->apList, (i+1)*sizeof(FILE*) );
          if( p->apList==0 ){ p->nList = 0; goto no_mem; }
          for(j=p->nList; j<=i; j++) p->apList[j] = 0;
          p->nList = i+1;
        }else if( p->apList[i] ){
          sqliteDbbeCloseTempFile(p->pBe, p->apList[i]);
        }
        rc = sqliteDbbeOpenTempFile(p->pBe, &p->apList[i]);
        if( rc!=SQLITE_OK ){
          sqliteSetString(pzErrMsg, "unable to open a temporary file", 0);
        }
        break;
      }

      /* Opcode: ListWrite P1 * *
................................................................................
      **
      ** Close the temporary storage buffer and discard its contents.
      */
      case OP_ListClose: {
        int i = pOp->p1;
        if( i<0 ) goto bad_instruction;
        if( i<p->nList && p->apList[i]!=0 ){
          sqliteDbbeCloseTempFile(p->pBe, p->apList[i]);
          p->apList[i] = 0;
        }
        break;
      }

      /* Opcode: SortOpen P1 * *
      **

** 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.44 2000/10/19 01:49:03 drh Exp $
*/
#include "sqliteInt.h"
#include <unistd.h>
#include <ctype.h>

/*
** SQL is translated into a sequence of instructions to be
................................................................................
static void Cleanup(Vdbe *p){
  int i;
  PopStack(p, p->tos+1);
  sqliteFree(p->azColName);
  p->azColName = 0;
  for(i=0; i<p->nCursor; i++){
    if( p->aCsr[i].pCursor ){
      p->pBe->CloseCursor(p->aCsr[i].pCursor);
      p->aCsr[i].pCursor = 0;
    }
  }
  sqliteFree(p->aCsr);
  p->aCsr = 0;
  p->nCursor = 0;
  for(i=0; i<p->nMem; i++){
................................................................................
    }
  }
  sqliteFree(p->aMem);
  p->aMem = 0;
  p->nMem = 0;
  for(i=0; i<p->nList; i++){
    if( p->apList[i] ){
      p->pBe->CloseTempFile(p->pBe, p->apList[i]);
      p->apList[i] = 0;
    }
  }
  sqliteFree(p->apList);
  p->apList = 0;
  p->nList = 0;
  for(i=0; i<p->nSort; i++){
................................................................................
  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 */
  char zBuf[100];            /* Space to sprintf() and integer */

  p->tos = -1;
  rc = SQLITE_OK;
#ifdef MEMORY_DEBUG
  if( access("vdbe_trace",0)==0 ){
    p->trace = stderr;
................................................................................
        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 ){
          pBe->CloseCursor(p->aCsr[i].pCursor);
        }
        do {
          rc = pBe->OpenCursor(pBe,pOp->p3,pOp->p2,&p->aCsr[i].pCursor);
          switch( rc ){
            case SQLITE_BUSY: {
              if( xBusy==0 || (*xBusy)(pBusyArg, pOp->p3, ++busy)==0 ){
                sqliteSetString(pzErrMsg,"table ", pOp->p3, " is locked", 0);
                busy = 0;
              }
              break;
................................................................................
      **
      ** Close a cursor previously opened as P1.  If P1 is not
      ** currently open, this instruction is a no-op.
      */
      case OP_Close: {
        int i = pOp->p1;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
          pBe->CloseCursor(p->aCsr[i].pCursor);
          p->aCsr[i].pCursor = 0;
        }
        break;
      }

      /* Opcode: Fetch P1 * *
      **
................................................................................
      */
      case OP_Fetch: {
        int i = pOp->p1;
        int tos = p->tos;
        if( tos<0 ) goto not_enough_stack;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
          if( p->aStack[tos].flags & STK_Int ){
            pBe->Fetch(p->aCsr[i].pCursor, sizeof(int), 
                           (char*)&p->aStack[tos].i);
          }else{
            if( Stringify(p, tos) ) goto no_mem;
            pBe->Fetch(p->aCsr[i].pCursor, p->aStack[tos].n, 
                           p->zStack[tos]);
          }
          p->nFetch++;
        }
        PopStack(p, 1);
        break;
      }
................................................................................
      case OP_Found: {
        int i = pOp->p1;
        int tos = p->tos;
        int alreadyExists = 0;
        if( tos<0 ) goto not_enough_stack;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
          if( p->aStack[tos].flags & STK_Int ){
            alreadyExists = pBe->Test(p->aCsr[i].pCursor, sizeof(int), 
                                          (char*)&p->aStack[tos].i);
          }else{
            if( Stringify(p, tos) ) goto no_mem;
            alreadyExists = pBe->Test(p->aCsr[i].pCursor,p->aStack[tos].n, 
                                           p->zStack[tos]);
          }
        }
        if( pOp->opcode==OP_Found ){
          if( alreadyExists ) pc = pOp->p2 - 1;
        }else{
          if( !alreadyExists ) pc = pOp->p2 - 1;
................................................................................
      */
      case OP_New: {
        int i = pOp->p1;
        int v;
        if( i<0 || i>=p->nCursor || p->aCsr[i].pCursor==0 ){
          v = 0;
        }else{
          v = pBe->New(p->aCsr[i].pCursor);
        }
        NeedStack(p, p->tos+1);
        p->tos++;
        p->aStack[p->tos].i = v;
        p->aStack[p->tos].flags = STK_Int;
        break;
      }
................................................................................
            if( Stringify(p, nos) ) goto no_mem;
            nKey = p->aStack[nos].n;
            zKey = p->zStack[nos];
          }else{
            nKey = sizeof(int);
            zKey = (char*)&p->aStack[nos].i;
          }
          pBe->Put(p->aCsr[i].pCursor, nKey, zKey,
                        p->aStack[tos].n, p->zStack[tos]);
        }
        PopStack(p, 2);
        break;
      }

      /* Opcode: Delete P1 * *
................................................................................
            nKey = sizeof(int);
            zKey = (char*)&p->aStack[tos].i;
          }else{
            if( Stringify(p, tos) ) goto no_mem;
            nKey = p->aStack[tos].n;
            zKey = p->zStack[tos];
          }
          pBe->Delete(p->aCsr[i].pCursor, nKey, zKey);
        }
        PopStack(p, 1);
        break;
      }

      /* Opcode: KeyAsData P1 P2 *
      **
................................................................................
        int tos = ++p->tos;
        DbbeCursor *pCrsr;
        char *z;

        if( NeedStack(p, tos) ) goto no_mem;
        if( i>=0 && i<p->nCursor && (pCrsr = p->aCsr[i].pCursor)!=0 ){
          if( p->aCsr[i].keyAsData ){
            amt = pBe->KeyLength(pCrsr);
            if( amt<=sizeof(int)*(p2+1) ){
              p->aStack[tos].flags = STK_Null;
              break;
            }
            pAddr = (int*)pBe->ReadKey(pCrsr, sizeof(int)*p2);
            if( *pAddr==0 ){
              p->aStack[tos].flags = STK_Null;
              break;
            }
            z = pBe->ReadKey(pCrsr, *pAddr);
          }else{
            amt = pBe->DataLength(pCrsr);
            if( amt<=sizeof(int)*(p2+1) ){
              p->aStack[tos].flags = STK_Null;
              break;
            }
            pAddr = (int*)pBe->ReadData(pCrsr, sizeof(int)*p2);
            if( *pAddr==0 ){
              p->aStack[tos].flags = STK_Null;
              break;
            }
            z = pBe->ReadData(pCrsr, *pAddr);
          }
          p->zStack[tos] = z;
          p->aStack[tos].n = strlen(z) + 1;
          p->aStack[tos].flags = STK_Str;
        }
        break;
      }
................................................................................
      case OP_Key: {
        int i = pOp->p1;
        int tos = ++p->tos;
        DbbeCursor *pCrsr;

        if( NeedStack(p, p->tos) ) goto no_mem;
        if( i>=0 && i<p->nCursor && (pCrsr = p->aCsr[i].pCursor)!=0 ){
          char *z = pBe->ReadKey(pCrsr, 0);
          if( p->aCsr[i].keyAsData ){
            p->zStack[tos] = z;
            p->aStack[tos].flags = STK_Str;
            p->aStack[tos].n = pBe->KeyLength(pCrsr);
          }else{
            memcpy(&p->aStack[tos].i, z, sizeof(int));
            p->aStack[tos].flags = STK_Int;
          }
        }
        break;
      }
................................................................................
      **
      ** The next use of the Key or Field or Next instruction for P1 
      ** will refer to the first entry in the database file.
      */
      case OP_Rewind: {
        int i = pOp->p1;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor!=0 ){
          pBe->Rewind(p->aCsr[i].pCursor);
        }
        break;
      }

      /* Opcode: Next P1 P2 *
      **
      ** Advance P1 to the next key/data pair in the file.  Or, if there are no
      ** more key/data pairs, rewind P1 and jump to location P2.
      */
      case OP_Next: {
        int i = pOp->p1;
        if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor!=0 ){
          if( pBe->NextKey(p->aCsr[i].pCursor)==0 ){
            pc = pOp->p2 - 1;
          }else{
            p->nFetch++;
          }
        }
        break;
      }
................................................................................

        if( NeedStack(p, p->tos) ) goto no_mem;
        p->zStack[tos] = 0;
        if( i>=0 && i<p->nCursor && (pCrsr = p->aCsr[i].pCursor)!=0 ){
          int *aIdx;
          int nIdx;
          int j, k;
          nIdx = pBe->DataLength(pCrsr)/sizeof(int);
          aIdx = (int*)pBe->ReadData(pCrsr, 0);
          if( nIdx>1 ){
            k = *(aIdx++);
            if( k>nIdx-1 ) k = nIdx-1;
          }else{
            k = nIdx;
          }
          for(j=p->aCsr[i].index; j<k; j++){
................................................................................
        if( nos<0 ) goto not_enough_stack;
        if( i>=0 && i<p->nCursor && (pCrsr = p->aCsr[i].pCursor)!=0 ){
          int r;
          int newVal;
          Integerify(p, nos);
          newVal = p->aStack[nos].i;
          if( Stringify(p, tos) ) goto no_mem;
          r = pBe->Fetch(pCrsr, p->aStack[tos].n, p->zStack[tos]);
          if( r==0 ){
            /* Create a new record for this index */
            pBe->Put(pCrsr, p->aStack[tos].n, p->zStack[tos],
                          sizeof(int), (char*)&newVal);
          }else{
            /* Extend the existing record */
            int nIdx;
            int *aIdx;
            int k;
            
            nIdx = pBe->DataLength(pCrsr)/sizeof(int);
            if( nIdx==1 ){
              aIdx = sqliteMalloc( sizeof(int)*4 );
              if( aIdx==0 ) goto no_mem;
              aIdx[0] = 2;
              pBe->CopyData(pCrsr, 0, sizeof(int), (char*)&aIdx[1]);
              aIdx[2] = newVal;
              pBe->Put(pCrsr, p->aStack[tos].n, p->zStack[tos],
                    sizeof(int)*4, (char*)aIdx);
              sqliteFree(aIdx);
            }else{
              aIdx = (int*)pBe->ReadData(pCrsr, 0);
              k = aIdx[0];
              if( k<nIdx-1 ){
                aIdx[k+1] = newVal;
                aIdx[0]++;
                pBe->Put(pCrsr, p->aStack[tos].n, p->zStack[tos],
                    sizeof(int)*nIdx, (char*)aIdx);
              }else{
                nIdx *= 2;
                aIdx = sqliteMalloc( sizeof(int)*nIdx );
                if( aIdx==0 ) goto no_mem;
                pBe->CopyData(pCrsr, 0, sizeof(int)*(k+1), (char*)aIdx);
                aIdx[k+1] = newVal;
                aIdx[0]++;
                pBe->Put(pCrsr, p->aStack[tos].n, p->zStack[tos],
                      sizeof(int)*nIdx, (char*)aIdx);
                sqliteFree(aIdx);
              }
            }              
          }
        }
        PopStack(p, 2);
................................................................................
          int nIdx;
          int j, k;
          int r;
          int oldVal;
          Integerify(p, nos);
          oldVal = p->aStack[nos].i;
          if( Stringify(p, tos) ) goto no_mem;
          r = pBe->Fetch(pCrsr, p->aStack[tos].n, p->zStack[tos]);
          if( r==0 ) break;
          nIdx = pBe->DataLength(pCrsr)/sizeof(int);
          aIdx = (int*)pBe->ReadData(pCrsr, 0);
          if( (nIdx==1 && aIdx[0]==oldVal) || (aIdx[0]==1 && aIdx[1]==oldVal) ){
            pBe->Delete(pCrsr, p->aStack[tos].n, p->zStack[tos]);
          }else{
            k = aIdx[0];
            for(j=1; j<=k && aIdx[j]!=oldVal; j++){}
            if( j>k ) break;
            aIdx[j] = aIdx[k];
            aIdx[k] = 0;
            aIdx[0]--;
            if( aIdx[0]*3 + 1 < nIdx ){
              nIdx /= 2;
            }
            pBe->Put(pCrsr, p->aStack[tos].n, p->zStack[tos], 
                          sizeof(int)*nIdx, (char*)aIdx);
          }
        }
        PopStack(p, 2);
        break;
      }

................................................................................
      /* Opcode: Destroy * * P3
      **
      ** Drop the disk file whose name is P3.  All key/data pairs in
      ** the file are deleted and the file itself is removed
      ** from the disk.
      */
      case OP_Destroy: {
        pBe->DropTable(pBe, pOp->p3);
        break;
      }

      /* Opcode: Reorganize * * P3
      **
      ** Compress, optimize, and tidy up the GDBM file named by P3.
      */
      case OP_Reorganize: {
        pBe->ReorganizeTable(pBe, pOp->p3);
        break;
      }

      /* Opcode: ListOpen P1 * *
      **
      ** Open a file used for temporary storage of integer table keys.  P1
      ** will server as a handle to this temporary file for future
................................................................................
        if( i>=p->nList ){
          int j;
          p->apList = sqliteRealloc( p->apList, (i+1)*sizeof(FILE*) );
          if( p->apList==0 ){ p->nList = 0; goto no_mem; }
          for(j=p->nList; j<=i; j++) p->apList[j] = 0;
          p->nList = i+1;
        }else if( p->apList[i] ){
          pBe->CloseTempFile(pBe, p->apList[i]);
        }
        rc = pBe->OpenTempFile(pBe, &p->apList[i]);
        if( rc!=SQLITE_OK ){
          sqliteSetString(pzErrMsg, "unable to open a temporary file", 0);
        }
        break;
      }

      /* Opcode: ListWrite P1 * *
................................................................................
      **
      ** Close the temporary storage buffer and discard its contents.
      */
      case OP_ListClose: {
        int i = pOp->p1;
        if( i<0 ) goto bad_instruction;
        if( i<p->nList && p->apList[i]!=0 ){
          pBe->CloseTempFile(pBe, p->apList[i]);
          p->apList[i] = 0;
        }
        break;
      }

      /* Opcode: SortOpen P1 * *
      **

}


proc chng {date desc} {
  puts "<DT><B>$date</B></DT>"
  puts "<DD><P><UL>$desc</UL></P></DD>"
}








chng {2000 Oct 16 (1.0.12)} {
<li>Fixed an off-by-one error that was causing a coredump in 
    the '%q' format directive of the new
    <b>sqlite_..._printf()</b> routines.</li>
<li>Added the <b>sqlite_interrupt()</b> interface.</li>
<li>In the shell, <b>sqlite_interrupt()</b> is invoked when the

}


proc chng {date desc} {
  puts "<DT><B>$date</B></DT>"
  puts "<DD><P><UL>$desc</UL></P></DD>"
}

chng {2000 Oct 18 (1.0.13)} {
<li>Break out the GDBM driver into a separate file in anticipation
    to added new drivers.</li>
<li>Allow the name of a database to be prefixed by the driver type.
    For now, the only driver type is "gdbm:".<li>
}

chng {2000 Oct 16 (1.0.12)} {
<li>Fixed an off-by-one error that was causing a coredump in 
    the '%q' format directive of the new
    <b>sqlite_..._printf()</b> routines.</li>
<li>Added the <b>sqlite_interrupt()</b> interface.</li>
<li>In the shell, <b>sqlite_interrupt()</b> is invoked when the