SQLite

/*
** 2001 September 22
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the implementation of generic hash-tables used in SQLite.
** We've modified it slightly to serve as a standalone hash table
** implementation for the full-text indexing module.
*/
#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "ft_hash.h"

void *malloc_and_zero(int n){
  void *p = malloc(n);
  if( p ){
    memset(p, 0, n);
  }
  return p;
}

/* Turn bulk memory into a hash table object by initializing the
** fields of the Hash structure.
**
** "pNew" is a pointer to the hash table that is to be initialized.
** keyClass is one of the constants HASH_INT, HASH_POINTER,
** HASH_BINARY, or HASH_STRING.  The value of keyClass 
** determines what kind of key the hash table will use.  "copyKey" is
** true if the hash table should make its own private copy of keys and
** false if it should just use the supplied pointer.  CopyKey only makes
** sense for HASH_STRING and HASH_BINARY and is ignored
** for other key classes.
*/
void HashInit(Hash *pNew, int keyClass, int copyKey){
  assert( pNew!=0 );
  assert( keyClass>=HASH_STRING && keyClass<=HASH_BINARY );
  pNew->keyClass = keyClass;
#if 0
  if( keyClass==HASH_POINTER || keyClass==HASH_INT ) copyKey = 0;
#endif
  pNew->copyKey = copyKey;
  pNew->first = 0;
  pNew->count = 0;
  pNew->htsize = 0;
  pNew->ht = 0;
  pNew->xMalloc = malloc_and_zero;
  pNew->xFree = free;
}

/* Remove all entries from a hash table.  Reclaim all memory.
** Call this routine to delete a hash table or to reset a hash table
** to the empty state.
*/
void HashClear(Hash *pH){
  HashElem *elem;         /* For looping over all elements of the table */

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

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

#if 0 /* NOT USED */
/*
** Hash and comparison functions when the mode is HASH_POINTER
*/
static int ptrHash(const void *pKey, int nKey){
  uptr x = Addr(pKey);
  return x ^ (x<<8) ^ (x>>8);
}
static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  if( pKey1==pKey2 ) return 0;
  if( pKey1<pKey2 ) return -1;
  return 1;
}
#endif

/*
** Hash and comparison functions when the mode is HASH_STRING
*/
static int strHash(const void *pKey, int nKey){
  const char *z = (const char *)pKey;
  int h = 0;
  if( nKey<=0 ) nKey = (int) strlen(z);
  while( nKey > 0  ){
    h = (h<<3) ^ h ^ *z++;
    nKey--;
  }
  return h & 0x7fffffff;
}
static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  if( n1!=n2 ) return 1;
  return strncmp((const char*)pKey1,(const char*)pKey2,n1);
}

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

/*
** Return a pointer to the appropriate hash function given the key class.
**
** The C syntax in this function definition may be unfamilar to some 
** programmers, so we provide the following additional explanation:
**
** The name of the function is "hashFunction".  The function takes a
** single parameter "keyClass".  The return value of hashFunction()
** is a pointer to another function.  Specifically, the return value
** of hashFunction() is a pointer to a function that takes two parameters
** with types "const void*" and "int" and returns an "int".
*/
static int (*hashFunction(int keyClass))(const void*,int){
#if 0  /* HASH_INT and HASH_POINTER are never used */
  switch( keyClass ){
    case HASH_INT:     return &intHash;
    case HASH_POINTER: return &ptrHash;
    case HASH_STRING:  return &strHash;
    case HASH_BINARY:  return &binHash;;
    default: break;
  }
  return 0;
#else
  if( keyClass==HASH_STRING ){
    return &strHash;
  }else{
    assert( keyClass==HASH_BINARY );
    return &binHash;
  }
#endif
}

/*
** Return a pointer to the appropriate hash function given the key class.
**
** For help in interpreted the obscure C code in the function definition,
** see the header comment on the previous function.
*/
static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
#if 0 /* HASH_INT and HASH_POINTER are never used */
  switch( keyClass ){
    case HASH_INT:     return &intCompare;
    case HASH_POINTER: return &ptrCompare;
    case HASH_STRING:  return &strCompare;
    case HASH_BINARY:  return &binCompare;
    default: break;
  }
  return 0;
#else
  if( keyClass==HASH_STRING ){
    return &strCompare;
  }else{
    assert( keyClass==HASH_BINARY );
    return &binCompare;
  }
#endif
}

/* Link an element into the hash table
*/
static void insertElement(
  Hash *pH,              /* The complete hash table */
  struct _ht *pEntry,    /* The entry into which pNew is inserted */
  HashElem *pNew         /* The element to be inserted */
){
  HashElem *pHead;       /* First element already in pEntry */
  pHead = pEntry->chain;
  if( pHead ){
    pNew->next = pHead;
    pNew->prev = pHead->prev;
    if( pHead->prev ){ pHead->prev->next = pNew; }
    else             { pH->first = pNew; }
    pHead->prev = pNew;
  }else{
    pNew->next = pH->first;
    if( pH->first ){ pH->first->prev = pNew; }
    pNew->prev = 0;
    pH->first = pNew;
  }
  pEntry->count++;
  pEntry->chain = pNew;
}


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

  assert( (new_size & (new_size-1))==0 );
  new_ht = (struct _ht *)pH->xMalloc( new_size*sizeof(struct _ht) );
  if( new_ht==0 ) return;
  if( pH->ht ) pH->xFree(pH->ht);
  pH->ht = new_ht;
  pH->htsize = new_size;
  xHash = hashFunction(pH->keyClass);
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
    next_elem = elem->next;
    insertElement(pH, &new_ht[h], elem);
  }
}

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

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

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

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

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

/* Insert an element into the hash table pH.  The key is pKey,nKey
** and the data is "data".
**
** If no element exists with a matching key, then a new
** element is created.  A copy of the key is made if the copyKey
** flag is set.  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 a malloc fails, then
** the new data is returned and the hash table is unchanged.
**
** If the "data" parameter to this function is NULL, then the
** element corresponding to "key" is removed from the hash table.
*/
void *HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
  int hraw;             /* Raw hash value of the key */
  int h;                /* the hash of the key modulo hash table size */
  HashElem *elem;       /* Used to loop thru the element list */
  HashElem *new_elem;   /* New element added to the pH */
  int (*xHash)(const void*,int);  /* The hash function */

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

/*
** 2001 September 22
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the header file for the generic hash-table implemenation
** used in SQLite.  We've modified it slightly to serve as a standalone
** hash table implementation for the full-text indexing module.
**
*/
#ifndef _HASH_H_
#define _HASH_H_

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

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

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

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

/*
** Access routines.  To delete, insert a NULL pointer.
*/
void HashInit(Hash*, int keytype, int copyKey);
void *HashInsert(Hash*, const void *pKey, int nKey, void *pData);
void *HashFind(const Hash*, const void *pKey, int nKey);
void HashClear(Hash*);

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

/*
** Number of entries in a hash table
*/
#define HashCount(H)  ((H)->count)

#endif /* _HASH_H_ */

/* The author disclaims copyright to this source code.
 *
 * This is an SQLite module implementing full-text search.
 */

#include <assert.h>
#if !defined(__APPLE__)
#include <malloc.h>
#else
#include <stdlib.h>
#endif
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#include "fulltext.h"
#include "ft_hash.h"
#include "tokenizer.h"
#include "sqlite3.h"
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1

/* utility functions */

/* We encode variable-length integers in little-endian order using seven bits
 * per byte as follows:
**
** KEY:
**         A = 0xxxxxxx    7 bits of data and one flag bit
**         B = 1xxxxxxx    7 bits of data and one flag bit
**
**  7 bits - A
** 14 bits - BA
** 21 bits - BBA
** and so on.
*/

/* We may need up to VARINT_MAX bytes to store an encoded 64-bit integer. */
#define VARINT_MAX 10

/* Write a 64-bit variable-length integer to memory starting at p[0].
 * The length of data written will be between 1 and VARINT_MAX bytes.
 * The number of bytes written is returned. */
static int putVarint(char *p, sqlite_int64 v){
  unsigned char *q = (unsigned char *) p;
  sqlite_uint64 vu = v;
  do{
    *q++ = (unsigned char) ((vu & 0x7f) | 0x80);
    vu >>= 7;
  }while( vu!=0 );
  q[-1] &= 0x7f;  /* turn off high bit in final byte */
  assert( q - (unsigned char *)p <= VARINT_MAX );
  return (int) (q - (unsigned char *)p);
}

/* Read a 64-bit variable-length integer from memory starting at p[0].
 * Return the number of bytes read, or 0 on error.
 * The value is stored in *v. */
static int getVarint(const char *p, sqlite_int64 *v){
  const unsigned char *q = (const unsigned char *) p;
  sqlite_uint64 x = 0, y = 1;
  while( (*q & 0x80) == 0x80 ){
    x += y * (*q++ & 0x7f);
    y <<= 7;
    if( q - (unsigned char *)p >= VARINT_MAX ){  /* bad data */
      assert( 0 );
      return 0;
    }
  }
  x += y * (*q++);
  *v = (sqlite_int64) x;
  return (int) (q - (unsigned char *)p);
}

static int getVarint32(const char *p, int *pi){
 sqlite_int64 i;
 int ret = getVarint(p, &i);
 *pi = (int) i;
 assert( *pi==i );
 return ret;
}

/*** Document lists ***
 *
 * A document list holds a sorted list of varint-encoded document IDs.
 *
 * A doclist with type DL_POSITIONS_OFFSETS is stored like this:
 *
 * array {
 *   varint docid;
 *   array {
 *     varint position;     (delta from previous position plus 1, or 0 for end)
 *     varint startOffset;  (delta from previous startOffset)
 *     varint endOffset;    (delta from startOffset)
 *   }
 * }
 *
 * Here, array { X } means zero or more occurrences of X, adjacent in memory.
 *
 * A doclist with type DL_POSITIONS is like the above, but holds only docids
 * and positions without offset information.
 *
 * A doclist with type DL_DOCIDS is like the above, but holds only docids
 * without positions or offset information.
 *
 * On disk, every document list has positions and offsets, so we don't bother
 * to serialize a doclist's type.
 * 
 * We don't yet delta-encode document IDs; doing so will probably be a
 * modest win.
 *
 * NOTE(shess) I've thought of a slightly (1%) better offset encoding.
 * After the first offset, estimate the next offset by using the
 * current token position and the previous token position and offset,
 * offset to handle some variance.  So the estimate would be
 * (iPosition*w->iStartOffset/w->iPosition-64), which is delta-encoded
 * as normal.  Offsets more than 64 chars from the estimate are
 * encoded as the delta to the previous start offset + 128.  An
 * additional tiny increment can be gained by using the end offset of
 * the previous token to make the estimate a tiny bit more precise.
*/

typedef enum DocListType {
  DL_DOCIDS,              /* docids only */
  DL_POSITIONS,           /* docids + positions */
  DL_POSITIONS_OFFSETS    /* docids + positions + offsets */
} DocListType;

typedef struct DocList {
  char *pData;
  int nData;
  DocListType iType;
  int iLastPos;       /* the last position written */
  int iLastOffset;    /* the last start offset written */
} DocList;

/* Initialize a new DocList to hold the given data. */
static void docListInit(DocList *d, DocListType iType,
                        const char *pData, int nData){
  d->nData = nData;
  if( nData>0 ){
    d->pData = malloc(nData);
    memcpy(d->pData, pData, nData);
  } else {
    d->pData = NULL;
  }
  d->iType = iType;
  d->iLastPos = 0;
  d->iLastOffset = 0;
}

/* Create a new dynamically-allocated DocList. */
static DocList *docListNew(DocListType iType){
  DocList *d = (DocList *) malloc(sizeof(DocList));
  docListInit(d, iType, 0, 0);
  return d;
}

static void docListDestroy(DocList *d){
  free(d->pData);
#ifndef NDEBUG
  memset(d, 0x55, sizeof(*d));
#endif
}

static void docListDelete(DocList *d){
  docListDestroy(d);
  free(d);
}

static char *docListEnd(DocList *d){
  return d->pData + d->nData;
}

/* Append a varint to a DocList's data. */
static void appendVarint(DocList *d, sqlite_int64 i){
  char c[VARINT_MAX];
  int n = putVarint(c, i);
  d->pData = realloc(d->pData, d->nData + n);
  memcpy(d->pData + d->nData, c, n);
  d->nData += n;
}

static void docListAddDocid(DocList *d, sqlite_int64 iDocid){
  appendVarint(d, iDocid);
  d->iLastPos = 0;
}

/* Add a position to the last position list in a doclist. */
static void docListAddPos(DocList *d, int iPos){
  assert( d->iType>=DL_POSITIONS );
  appendVarint(d, iPos-d->iLastPos+1);
  d->iLastPos = iPos;
}

static void docListAddPosOffset(DocList *d, int iPos,
                                int iStartOffset, int iEndOffset){
  assert( d->iType==DL_POSITIONS_OFFSETS );
  docListAddPos(d, iPos);
  appendVarint(d, iStartOffset-d->iLastOffset);
  d->iLastOffset = iStartOffset;
  appendVarint(d, iEndOffset-iStartOffset);
}

/* Terminate the last position list in the given doclist. */
static void docListAddEndPos(DocList *d){
  appendVarint(d, 0);
}

typedef struct DocListReader {
  DocList *pDoclist;
  char *p;
  int iLastPos;    /* the last position read */
} DocListReader;

static void readerInit(DocListReader *r, DocList *pDoclist){
  r->pDoclist = pDoclist;
  if( pDoclist!=NULL ){
    r->p = pDoclist->pData;
  }
  r->iLastPos = 0;
}

static int readerAtEnd(DocListReader *pReader){
  return pReader->p >= docListEnd(pReader->pDoclist);
}

/* Peek at the next docid without advancing the read pointer. */
static sqlite_int64 peekDocid(DocListReader *pReader){
  sqlite_int64 ret;
  assert( !readerAtEnd(pReader) );
  getVarint(pReader->p, &ret);
  return ret;
}

/* Read the next docid. */
static sqlite_int64 readDocid(DocListReader *pReader){
  sqlite_int64 ret;
  assert( !readerAtEnd(pReader) );
  pReader->p += getVarint(pReader->p, &ret);
  pReader->iLastPos = 0;
  return ret;
}

/* Read the next position from a position list.
 * Returns the position, or -1 at the end of the list. */
static int readPosition(DocListReader *pReader){
  int i;
  int iType = pReader->pDoclist->iType;
  assert( iType>=DL_POSITIONS );
  assert( !readerAtEnd(pReader) );

  pReader->p += getVarint32(pReader->p, &i);
  if( i==0 ){
    pReader->iLastPos = -1;
    return -1;
  }
  pReader->iLastPos += ((int) i)-1;
  if( iType>=DL_POSITIONS_OFFSETS ){
    /* Skip over offsets, ignoring them for now. */
    int iStart, iEnd;
    pReader->p += getVarint32(pReader->p, &iStart);
    pReader->p += getVarint32(pReader->p, &iEnd);
  }
  return pReader->iLastPos;
}

/* Skip past the end of a position list. */
static void skipPositionList(DocListReader *pReader){
  while( readPosition(pReader)!=-1 )
    ;
}

/* Skip over a docid, including its position list if the doclist has
 * positions. */
static void skipDocument(DocListReader *pReader){
  readDocid(pReader);
  if( pReader->pDoclist->iType >= DL_POSITIONS ){
    skipPositionList(pReader);
  }
}

static sqlite_int64 firstDocid(DocList *d){
  DocListReader r;
  readerInit(&r, d);
  return readDocid(&r);
}

/* Doclist multi-tool.  Pass pUpdate==NULL to delete the indicated docid;
 * otherwise pUpdate, which must contain only the single docid [iDocid], is
 * inserted (if not present) or updated (if already present). */
static int docListUpdate(DocList *d, sqlite_int64 iDocid, DocList *pUpdate){
  int modified = 0;
  DocListReader reader;
  char *p;

  if( pUpdate!=NULL ){
    assert( d->iType==pUpdate->iType);
    assert( iDocid==firstDocid(pUpdate) );
  }

  readerInit(&reader, d);
  while( !readerAtEnd(&reader) && peekDocid(&reader)<iDocid ){
    skipDocument(&reader);
  }

  p = reader.p;
  /* Delete if there is a matching element. */
  if( !readerAtEnd(&reader) && iDocid==peekDocid(&reader) ){
    skipDocument(&reader);
    memmove(p, reader.p, docListEnd(d) - reader.p);
    d->nData -= (reader.p - p);
    modified = 1;
  }

  /* Insert if indicated. */
  if( pUpdate!=NULL ){
    int iDoclist = p-d->pData;
    docListAddEndPos(pUpdate);

    d->pData = realloc(d->pData, d->nData+pUpdate->nData);
    p = d->pData + iDoclist;

    memmove(p+pUpdate->nData, p, docListEnd(d) - p);
    memcpy(p, pUpdate->pData, pUpdate->nData);
    d->nData += pUpdate->nData;
    modified = 1;
  }

  return modified;
}

/* Split the second half of doclist d into a separate doclist d2.  Returns 1
 * if successful, or 0 if d contains a single document and hence can't be
 * split. */
static int docListSplit(DocList *d, DocList *d2){
  const char *pSplitPoint = d->pData + d->nData / 2;
  DocListReader reader;

  readerInit(&reader, d);
  while( reader.p<pSplitPoint ){
    skipDocument(&reader);
  }
  if( readerAtEnd(&reader) ) return 0;
  docListInit(d2, d->iType, reader.p, docListEnd(d) - reader.p);
  d->nData = reader.p - d->pData;
  d->pData = realloc(d->pData, d->nData);
  return 1;
}

/* A DocListMerge computes the AND of an in-memory DocList [in] and a chunked
 * on-disk doclist, resulting in another in-memory DocList [out].  [in]
 * and [out] may or may not store position information according to the
 * caller's wishes.  The on-disk doclist always comes with positions.
 *
 * The caller must read each chunk of the on-disk doclist in succession and
 * pass it to mergeBlock().
 *
 * If [in] has positions, then the merge output contains only documents with
 * matching positions in the two input doclists.  If [in] does not have
 * positions, then the merge output contains all documents common to the two
 * input doclists.
 *
 * If [in] is NULL, then the on-disk doclist is copied to [out] directly.
 *
 * A merge is performed using an integer [iOffset] provided by the caller.
 * [iOffset] is subtracted from each position in the on-disk doclist for the
 * purpose of position comparison; this is helpful in implementing phrase
 * searches.
 *
 * A DocListMerge is not yet able to propagate offsets through query
 * processing; we should add that capability soon.
*/
typedef struct DocListMerge {
  DocListReader in;
  DocList *pOut;
  int iOffset;
} DocListMerge;

static void mergeInit(DocListMerge *m,
                      DocList *pIn, int iOffset, DocList *pOut){
  readerInit(&m->in, pIn);
  m->pOut = pOut;
  m->iOffset = iOffset;

  /* can't handle offsets yet */
  assert( pIn==NULL || pIn->iType <= DL_POSITIONS );
  assert( pOut->iType <= DL_POSITIONS );
}

/* A helper function for mergeBlock(), below.  Merge the position lists
 * pointed to by m->in and pBlockReader.
 * If the merge matches, write [iDocid] to m->pOut; if m->pOut
 * has positions then write all matching positions as well. */
static void mergePosList(DocListMerge *m, sqlite_int64 iDocid,
                  DocListReader *pBlockReader){
  int block_pos = readPosition(pBlockReader);
  int in_pos = readPosition(&m->in);
  int match = 0;
  while( block_pos!=-1 || in_pos!=-1 ){
    if( block_pos-m->iOffset==in_pos ){
      if( !match ){
        docListAddDocid(m->pOut, iDocid);
        match = 1;
      }
      if( m->pOut->iType >= DL_POSITIONS ){
        docListAddPos(m->pOut, in_pos);
      }
      block_pos = readPosition(pBlockReader);
      in_pos = readPosition(&m->in);
    } else if( in_pos==-1 || (block_pos!=-1 && block_pos-m->iOffset<in_pos) ){
      block_pos = readPosition(pBlockReader);
    } else {
      in_pos = readPosition(&m->in);
    }
  }
  if( m->pOut->iType >= DL_POSITIONS && match ){
    docListAddEndPos(m->pOut);
  }
}

/* Merge one block of an on-disk doclist into a DocListMerge. */
static void mergeBlock(DocListMerge *m, DocList *pBlock){
  DocListReader blockReader;
  assert( pBlock->iType >= DL_POSITIONS );
  readerInit(&blockReader, pBlock);
  while( !readerAtEnd(&blockReader) ){
    sqlite_int64 iDocid = readDocid(&blockReader);
    if( m->in.pDoclist!=NULL ){
      while( 1 ){
        if( readerAtEnd(&m->in) ) return;  /* nothing more to merge */
        if( peekDocid(&m->in)>=iDocid ) break;
        skipDocument(&m->in);
      }
      if( peekDocid(&m->in)>iDocid ){  /* [pIn] has no match with iDocid */
        skipPositionList(&blockReader);  /* skip this docid in the block */
        continue;
      }
      readDocid(&m->in);
    }
    /* We have a document match. */
    if( m->in.pDoclist==NULL || m->in.pDoclist->iType < DL_POSITIONS ){
      /* We don't need to do a poslist merge. */
      docListAddDocid(m->pOut, iDocid);
      if( m->pOut->iType >= DL_POSITIONS ){
        /* Copy all positions to the output doclist. */
        while( 1 ){
          int pos = readPosition(&blockReader);
          if( pos==-1 ) break;
          docListAddPos(m->pOut, pos);
        }
        docListAddEndPos(m->pOut);
      } else skipPositionList(&blockReader);
      continue;
    }
    mergePosList(m, iDocid, &blockReader);
  }
}

static char *string_dup_n(const char *s, int n){
  char *str = malloc(n + 1);
  memcpy(str, s, n);
  str[n] = '\0';
  return str;
}

/* Duplicate a string; the caller must free() the returned string.
 * (We don't use strdup() since it's not part of the standard C library and
 * may not be available everywhere.) */
static char *string_dup(const char *s){
  return string_dup_n(s, strlen(s));
}

/* Format a string, replacing each occurrence of the % character with
 * zName.  This may be more convenient than sqlite_mprintf()
 * when one string is used repeatedly in a format string.
 * The caller must free() the returned string. */
static char *string_format(const char *zFormat, const char *zName){
  const char *p;
  size_t len = 0;
  size_t nName = strlen(zName);
  char *result;
  char *r;

  /* first compute length needed */
  for(p = zFormat ; *p ; ++p){
    len += (*p=='%' ? nName : 1);
  }
  len += 1;  /* for null terminator */

  r = result = malloc(len);
  for(p = zFormat; *p; ++p){
    if( *p=='%' ){
      memcpy(r, zName, nName);
      r += nName;
    } else {
      *r++ = *p;
    }
  }
  *r++ = '\0';
  assert( r == result + len );
  return result;
}

static int sql_exec(sqlite3 *db, const char *zName, const char *zFormat){
  char *zCommand = string_format(zFormat, zName);
  int rc = sqlite3_exec(db, zCommand, NULL, 0, NULL);
  free(zCommand);
  return rc;
}

static int sql_prepare(sqlite3 *db, const char *zName, sqlite3_stmt **ppStmt,
                const char *zFormat){
  char *zCommand = string_format(zFormat, zName);
  int rc = sqlite3_prepare(db, zCommand, -1, ppStmt, NULL);
  free(zCommand);
  return rc;
}

/* end utility functions */

#define QUERY_GENERIC 0
#define QUERY_FULLTEXT 1

#define CHUNK_MAX 1024

typedef enum fulltext_statement {
  CONTENT_INSERT_STMT,
  CONTENT_SELECT_STMT,
  CONTENT_DELETE_STMT,

  TERM_SELECT_STMT,
  TERM_CHUNK_SELECT_STMT,
  TERM_INSERT_STMT,
  TERM_UPDATE_STMT,
  TERM_DELETE_STMT,

  MAX_STMT                     /* Always at end! */
} fulltext_statement;

/* These must exactly match the enum above. */
/* TODO(adam): Is there some risk that a statement (in particular,
** pTermSelectStmt) will be used in two cursors at once, e.g.  if a
** query joins a virtual table to itself?  If so perhaps we should
** move some of these to the cursor object.
*/
static const char *fulltext_zStatement[MAX_STMT] = {
  /* CONTENT_INSERT */ "insert into %_content (rowid, content) values (?, ?)",
  /* CONTENT_SELECT */ "select content from %_content where rowid = ?",
  /* CONTENT_DELETE */ "delete from %_content where rowid = ?",

  /* TERM_SELECT */
  "select rowid, doclist from %_term where term = ? and first = ?",
  /* TERM_CHUNK_SELECT */
  "select max(first) from %_term where term = ? and first <= ?",
  /* TERM_INSERT */
  "insert into %_term (term, first, doclist) values (?, ?, ?)",
  /* TERM_UPDATE */ "update %_term set doclist = ? where rowid = ?",
  /* TERM_DELETE */ "delete from %_term where rowid = ?",
};

typedef struct fulltext_vtab {
  sqlite3_vtab base;
  sqlite3 *db;
  const char *zName;               /* virtual table name */
  sqlite3_tokenizer *pTokenizer;   /* tokenizer for inserts and queries */

  /* Precompiled statements which we keep as long as the table is
  ** open.
  */
  sqlite3_stmt *pFulltextStatements[MAX_STMT];
} fulltext_vtab;

typedef struct fulltext_cursor {
  sqlite3_vtab_cursor base;
  int iCursorType;  /* QUERY_GENERIC or QUERY_FULLTEXT */

  sqlite3_stmt *pStmt;

  int eof;

  /* The following is used only when iCursorType == QUERY_FULLTEXT. */
  DocListReader result;
} fulltext_cursor;

static struct fulltext_vtab *cursor_vtab(fulltext_cursor *c){
  return (fulltext_vtab *) c->base.pVtab;
}

static sqlite3_module fulltextModule;   /* forward declaration */

/* Puts a freshly-prepared statement determined by iStmt in *ppStmt.
** If the indicated statement has never been prepared, it is prepared
** and cached, otherwise the cached version is reset.
*/
static int sql_get_statement(fulltext_vtab *v, fulltext_statement iStmt,
                             sqlite3_stmt **ppStmt){
  assert( iStmt<MAX_STMT );
  if( v->pFulltextStatements[iStmt]==NULL ){
    int rc = sql_prepare(v->db, v->zName, &v->pFulltextStatements[iStmt],
                         fulltext_zStatement[iStmt]);
    if( rc!=SQLITE_OK ) return rc;
  } else {
    int rc = sqlite3_reset(v->pFulltextStatements[iStmt]);
    if( rc!=SQLITE_OK ) return rc;
  }

  *ppStmt = v->pFulltextStatements[iStmt];
  return SQLITE_OK;
}

/* Step the indicated statement, handling errors SQLITE_BUSY (by
** retrying) and SQLITE_SCHEMA (by re-preparing and transferring
** bindings to the new statement).
** TODO(adam): We should extend this function so that it can work with
** statements declared locally, not only globally cached statements.
*/
static int sql_step_statement(fulltext_vtab *v, fulltext_statement iStmt,
                              sqlite3_stmt **ppStmt){
  int rc;
  sqlite3_stmt *s = *ppStmt;
  assert( iStmt<MAX_STMT );
  assert( s==v->pFulltextStatements[iStmt] );

  while( (rc=sqlite3_step(s))!=SQLITE_DONE && rc!=SQLITE_ROW ){
    sqlite3_stmt *pNewStmt;

    if( rc==SQLITE_BUSY ) continue;
    if( rc!=SQLITE_ERROR ) return rc;

    rc = sqlite3_reset(s);
    if( rc!=SQLITE_SCHEMA ) return SQLITE_ERROR;

    v->pFulltextStatements[iStmt] = NULL;   /* Still in s */
    rc = sql_get_statement(v, iStmt, &pNewStmt);
    if( rc!=SQLITE_OK ) goto err;
    *ppStmt = pNewStmt;

    rc = sqlite3_transfer_bindings(s, pNewStmt);
    if( rc!=SQLITE_OK ) goto err;

    rc = sqlite3_finalize(s);
    if( rc!=SQLITE_OK ) return rc;
    s = pNewStmt;
  }
  return rc;

 err:
  sqlite3_finalize(s);
  return rc;
}

/* Like sql_step_statement(), but convert SQLITE_DONE to SQLITE_OK.
** Useful for statements like UPDATE, where we expect no results.
*/
static int sql_single_step_statement(fulltext_vtab *v,
                                     fulltext_statement iStmt,
                                     sqlite3_stmt **ppStmt){
  int rc = sql_step_statement(v, iStmt, ppStmt);
  return (rc==SQLITE_DONE) ? SQLITE_OK : rc;
}

/* insert into %_content (rowid, content) values ([rowid], [zContent]) */
static int content_insert(fulltext_vtab *v, sqlite3_value *rowid,
                          const char *zContent, int nContent){
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, CONTENT_INSERT_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_value(s, 1, rowid);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_text(s, 2, zContent, nContent, SQLITE_STATIC);
  if( rc!=SQLITE_OK ) return rc;

  return sql_single_step_statement(v, CONTENT_INSERT_STMT, &s);
}

/* select content from %_content where rowid = [iRow]
 * The caller must delete the returned string. */
static int content_select(fulltext_vtab *v, sqlite_int64 iRow,
                          char **pzContent){
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, CONTENT_SELECT_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int64(s, 1, iRow);
  if( rc!=SQLITE_OK ) return rc;

  rc = sql_step_statement(v, CONTENT_SELECT_STMT, &s);
  if( rc!=SQLITE_ROW ) return rc;

  *pzContent = string_dup((const char *)sqlite3_column_text(s, 0));

  /* We expect only one row.  We must execute another sqlite3_step()
   * to complete the iteration; otherwise the table will remain locked. */
  rc = sqlite3_step(s);
  if( rc==SQLITE_DONE ) return SQLITE_OK;

  free(*pzContent);
  return rc;
}

/* delete from %_content where rowid = [iRow ] */
static int content_delete(fulltext_vtab *v, sqlite_int64 iRow){
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, CONTENT_DELETE_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int64(s, 1, iRow);
  if( rc!=SQLITE_OK ) return rc;

  return sql_single_step_statement(v, CONTENT_DELETE_STMT, &s);
}

/* select rowid, doclist from %_term where term = [zTerm] and first = [iFirst]
 * If found, returns SQLITE_OK; the caller must free the returned doclist.
 * If no rows found, returns SQLITE_ERROR. */
static int term_select(fulltext_vtab *v, const char *zTerm, int nTerm,
                       sqlite_int64 iFirst,
                       sqlite_int64 *rowid,
                       DocList *out){
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, TERM_SELECT_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_text(s, 1, zTerm, nTerm, SQLITE_TRANSIENT);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int64(s, 2, iFirst);
  if( rc!=SQLITE_OK ) return rc;

  rc = sql_step_statement(v, TERM_SELECT_STMT, &s);
  if( rc!=SQLITE_ROW ) return rc==SQLITE_DONE ? SQLITE_ERROR : rc;

  *rowid = sqlite3_column_int64(s, 0);
  docListInit(out, DL_POSITIONS_OFFSETS,
              sqlite3_column_blob(s, 1), sqlite3_column_bytes(s, 1));

  /* We expect only one row.  We must execute another sqlite3_step()
   * to complete the iteration; otherwise the table will remain locked. */
  rc = sqlite3_step(s);
  return rc==SQLITE_DONE ? SQLITE_OK : rc;
}

/* select max(first) from %_term where term = [zTerm] and first <= [iFirst]
 * If found, returns SQLITE_ROW and result in *piResult; if the query returns
 * NULL (meaning no row found) returns SQLITE_DONE.
 */
static int term_chunk_select(fulltext_vtab *v, const char *zTerm, int nTerm,
                           sqlite_int64 iFirst, sqlite_int64 *piResult){
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, TERM_CHUNK_SELECT_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_text(s, 1, zTerm, nTerm, SQLITE_STATIC);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int64(s, 2, iFirst);
  if( rc!=SQLITE_OK ) return rc;

  rc = sql_step_statement(v, TERM_CHUNK_SELECT_STMT, &s);
  if( rc!=SQLITE_ROW ) return rc==SQLITE_DONE ? SQLITE_ERROR : rc;

  switch( sqlite3_column_type(s, 0) ){
    case SQLITE_NULL:
      rc = SQLITE_DONE;
      break;
    case SQLITE_INTEGER:
     *piResult = sqlite3_column_int64(s, 0);
     break;
    default:
      return SQLITE_ERROR;
  }
  /* We expect only one row.  We must execute another sqlite3_step()
   * to complete the iteration; otherwise the table will remain locked. */
  if( sqlite3_step(s) != SQLITE_DONE ) return SQLITE_ERROR;
  return rc;
}

/* insert into %_term (term, first, doclist)
               values ([zTerm], [iFirst], [doclist]) */
static int term_insert(fulltext_vtab *v, const char *zTerm, int nTerm,
                       sqlite_int64 iFirst, DocList *doclist){
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, TERM_INSERT_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_text(s, 1, zTerm, nTerm, SQLITE_STATIC);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int64(s, 2, iFirst);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_blob(s, 3, doclist->pData, doclist->nData, SQLITE_STATIC);
  if( rc!=SQLITE_OK ) return rc;

  return sql_single_step_statement(v, TERM_INSERT_STMT, &s);
}

/* update %_term set doclist = [doclist] where rowid = [rowid] */
static int term_update(fulltext_vtab *v, sqlite_int64 rowid,
                       DocList *doclist){
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, TERM_UPDATE_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_blob(s, 1, doclist->pData, doclist->nData,
                         SQLITE_STATIC);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int64(s, 2, rowid);
  if( rc!=SQLITE_OK ) return rc;

  return sql_single_step_statement(v, TERM_UPDATE_STMT, &s);
}

static int term_delete(fulltext_vtab *v, sqlite_int64 rowid){
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, TERM_DELETE_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int64(s, 1, rowid);
  if( rc!=SQLITE_OK ) return rc;

  return sql_single_step_statement(v, TERM_DELETE_STMT, &s);
}

static void fulltext_vtab_destroy(fulltext_vtab *v){
  int iStmt;

  for( iStmt=0; iStmt<MAX_STMT; iStmt++ ){
    if( v->pFulltextStatements[iStmt]!=NULL ){
      sqlite3_finalize(v->pFulltextStatements[iStmt]);
      v->pFulltextStatements[iStmt] = NULL;
    }
  }

  if( v->pTokenizer!=NULL ){
    v->pTokenizer->pModule->xDestroy(v->pTokenizer);
    v->pTokenizer = NULL;
  }

  free((void *) v->zName);
  free(v);
}

/* Current interface:
** argv[0] - module name
** argv[1] - database name
** argv[2] - table name
** argv[3] - tokenizer name (optional, a sensible default is provided)
** argv[4..] - passed to tokenizer (optional based on tokenizer)
**/
static int fulltextConnect(sqlite3 *db, void *pAux, int argc, char **argv,
                           sqlite3_vtab **ppVTab){
  int rc;
  fulltext_vtab *v;
  sqlite3_tokenizer_module *m = NULL;

  assert( argc>=3 );
  v = (fulltext_vtab *) malloc(sizeof(fulltext_vtab));
  /* sqlite will initialize v->base */
  v->db = db;
  v->zName = string_dup(argv[2]);
  v->pTokenizer = NULL;

  if( argc==3 ){
    get_simple_tokenizer_module(&m);
  } else {
    /* TODO(shess) For now, add new tokenizers as else if clauses. */
    if( !strcmp(argv[3], "simple") ){
      get_simple_tokenizer_module(&m);
    } else {
      assert( "unrecognized tokenizer"==NULL );
    }
  }

  /* TODO(shess) Since tokenization impacts the index, the parameters
  ** to the tokenizer need to be identical when a persistent virtual
  ** table is re-created.  One solution would be a meta-table to track
  ** such information in the database.  Then we could verify that the
  ** information is identical on subsequent creates.
  */
  /* TODO(shess) Why isn't argv already (const char **)? */
  rc = m->xCreate(argc-3, (const char **) (argv+3), &v->pTokenizer);
  if( rc!=SQLITE_OK ) return rc;
  v->pTokenizer->pModule = m;

  /* TODO: verify the existence of backing tables foo_content, foo_term */

  rc = sqlite3_declare_vtab(db, "create table x(content text)");
  if( rc!=SQLITE_OK ) return rc;

  memset(v->pFulltextStatements, 0, sizeof(v->pFulltextStatements));

  *ppVTab = &v->base;
  return SQLITE_OK;
}

static int fulltextCreate(sqlite3 *db, void *pAux, int argc, char **argv,
                          sqlite3_vtab **ppVTab){
  int rc;
  assert( argc>=3 );

  /* The %_content table holds the text of each full-text item, with
  ** the rowid used as the docid.
  **
  ** The %_term table maps each term to a document list blob
  ** containing elements sorted by ascending docid, each element
  ** encoded as:
  **
  **   docid varint-encoded
  **   token count varint-encoded
  **   "count" token elements (poslist):
  **     position varint-encoded as delta from previous position
  **     start offset varint-encoded as delta from previous start offset
  **     end offset varint-encoded as delta from start offset
  **
  ** Additionally, doclist blobs can be chunked into multiple rows,
  ** using "first" to order the blobs.  "first" is simply the first
  ** docid in the blob.
  */
  /*
  ** NOTE(shess) That last sentence is incorrect in the face of
  ** deletion, which can leave a doclist that doesn't contain the
  ** first from that row.  I _believe_ this does not matter to the
  ** operation of the system, but it might be reasonable to update
  ** appropriately in case this assumption becomes more important.
  */
  rc = sql_exec(db, argv[2],
    "create table %_content(content text);"
    "create table %_term(term text, first integer, doclist blob);"
    "create index %_index on %_term(term, first)");
  if( rc!=SQLITE_OK ) return rc;

  return fulltextConnect(db, pAux, argc, argv, ppVTab);
}

/* Decide how to handle an SQL query.
 * At the moment, MATCH queries can include implicit boolean ANDs; we
 * haven't implemented phrase searches or OR yet. */
static int fulltextBestIndex(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){
  int i;

  for(i=0; i<pInfo->nConstraint; ++i){
    const struct sqlite3_index_constraint *pConstraint;
    pConstraint = &pInfo->aConstraint[i];
    if( pConstraint->iColumn==0 &&
        pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH &&
        pConstraint->usable ){   /* a full-text search */
      pInfo->aConstraintUsage[i].argvIndex = 1;
      pInfo->aConstraintUsage[i].omit = 1;
      pInfo->idxNum = QUERY_FULLTEXT;
      pInfo->estimatedCost = 1.0;   /* an arbitrary value for now */
      return SQLITE_OK;
    }
  }
  pInfo->idxNum = QUERY_GENERIC;
  return SQLITE_OK;
}

static int fulltextDisconnect(sqlite3_vtab *pVTab){
  fulltext_vtab_destroy((fulltext_vtab *)pVTab);
  return SQLITE_OK;
}

static int fulltextDestroy(sqlite3_vtab *pVTab){
  fulltext_vtab *v = (fulltext_vtab *)pVTab;

  int rc = sql_exec(v->db, v->zName,
                    "drop table %_content; drop table %_term");
  if( rc!=SQLITE_OK ) return rc;

  fulltext_vtab_destroy((fulltext_vtab *)pVTab);
  return SQLITE_OK;
}

static int fulltextOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
  fulltext_cursor *c;

  c = (fulltext_cursor *) calloc(sizeof(fulltext_cursor), 1);
  /* sqlite will initialize c->base */
  *ppCursor = &c->base;

  return SQLITE_OK;
}

static int fulltextClose(sqlite3_vtab_cursor *pCursor){
  fulltext_cursor *c = (fulltext_cursor *) pCursor;
  sqlite3_finalize(c->pStmt);
  if( c->result.pDoclist!=NULL ){
    docListDelete(c->result.pDoclist);
  }
  free(c);
  return SQLITE_OK;
}

static int fulltextNext(sqlite3_vtab_cursor *pCursor){
  fulltext_cursor *c = (fulltext_cursor *) pCursor;
  sqlite_int64 iDocid;
  int rc;

  switch( c->iCursorType ){
    case QUERY_GENERIC:
      /* TODO(shess) Handle SQLITE_SCHEMA AND SQLITE_BUSY. */
      rc = sqlite3_step(c->pStmt);
      switch( rc ){
        case SQLITE_ROW:
          c->eof = 0;
          return SQLITE_OK;
        case SQLITE_DONE:
          c->eof = 1;
          return SQLITE_OK;
        default:
          c->eof = 1;
          return rc;
      }
    case QUERY_FULLTEXT:
      rc = sqlite3_reset(c->pStmt);
      if( rc!=SQLITE_OK ) return rc;

      if( readerAtEnd(&c->result)){
        c->eof = 1;
        return SQLITE_OK;
      }
      iDocid = readDocid(&c->result);
      rc = sqlite3_bind_int64(c->pStmt, 1, iDocid);
      if( rc!=SQLITE_OK ) return rc;
      /* TODO(shess) Handle SQLITE_SCHEMA AND SQLITE_BUSY. */
      rc = sqlite3_step(c->pStmt);
      if( rc==SQLITE_ROW ){   /* the case we expect */
        c->eof = 0;
        return SQLITE_OK;
      }
      /* an error occurred; abort */
      return rc==SQLITE_DONE ? SQLITE_ERROR : rc;
    default:
      assert( 0 );
      return SQLITE_ERROR;  /* not reached */
  }
}

static int term_select_doclist(fulltext_vtab *v, const char *pTerm, int nTerm,
                               sqlite3_stmt **ppStmt){
  int rc;
  if( *ppStmt ){
    rc = sqlite3_reset(*ppStmt);
  } else {
    rc = sql_prepare(v->db, v->zName, ppStmt,
      "select doclist from %_term where term = ? order by first");
  }
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_text(*ppStmt, 1, pTerm, nTerm, SQLITE_TRANSIENT);
  if( rc!=SQLITE_OK ) return rc;

  return sqlite3_step(*ppStmt);   /* TODO(adamd): handle schema error */
}

/* Read the posting list for [zTerm]; AND it with the doclist [in] to
 * produce the doclist [out], using the given offset [iOffset] for phrase
 * matching.
 * (*pSelect) is used to hold an SQLite statement used inside this function;
 * the caller should initialize *pSelect to NULL before the first call.
 */
static int query_merge(fulltext_vtab *v, sqlite3_stmt **pSelect,
                       const char *zTerm,
                       DocList *pIn, int iOffset, DocList *out){
  int rc;
  DocListMerge merge;

  if( pIn!=NULL && !pIn->nData ){
    /* If [pIn] is already empty, there's no point in reading the
     * posting list to AND it in; return immediately. */
      return SQLITE_OK;
  }

  rc = term_select_doclist(v, zTerm, -1, pSelect);
  if( rc!=SQLITE_ROW && rc!=SQLITE_DONE ) return rc;

  mergeInit(&merge, pIn, iOffset, out);
  while( rc==SQLITE_ROW ){
    DocList block;
    docListInit(&block, DL_POSITIONS_OFFSETS,
                sqlite3_column_blob(*pSelect, 0),
                sqlite3_column_bytes(*pSelect, 0));
    mergeBlock(&merge, &block);
    docListDestroy(&block);

    rc = sqlite3_step(*pSelect);
    if( rc!=SQLITE_ROW && rc!=SQLITE_DONE ){
      return rc;
    }
  }
  
  return SQLITE_OK;
}

typedef struct QueryTerm {
  int is_phrase;    /* true if this term begins a new phrase */
  const char *zTerm;
} QueryTerm;

/* A parsed query.
 *
 * As an example, parsing the query ["four score" years "new nation"] will
 * yield a Query with 5 terms:
 *   "four",   is_phrase = 1
 *   "score",  is_phrase = 0
 *   "years",  is_phrase = 1
 *   "new",    is_phrase = 1
 *   "nation", is_phrase = 0
 */
typedef struct Query {
  int nTerms;
  QueryTerm *pTerm;
} Query;

static void query_add(Query *q, int is_phrase, const char *zTerm){
  QueryTerm *t;
  ++q->nTerms;
  q->pTerm = realloc(q->pTerm, q->nTerms * sizeof(q->pTerm[0]));
  t = &q->pTerm[q->nTerms - 1];
  t->is_phrase = is_phrase;
  t->zTerm = zTerm;
}
    
static void query_free(Query *q){
  int i;
  for(i = 0; i < q->nTerms; ++i){
    free((void *) q->pTerm[i].zTerm);
  }
  free(q->pTerm);
}

static int tokenize_segment(sqlite3_tokenizer *pTokenizer,
                            const char *zQuery, int in_phrase,
                            Query *pQuery){
  sqlite3_tokenizer_module *pModule = pTokenizer->pModule;
  sqlite3_tokenizer_cursor *pCursor;
  int is_first = 1;
  
  int rc = pModule->xOpen(pTokenizer, zQuery, -1, &pCursor);
  if( rc!=SQLITE_OK ) return rc;
  pCursor->pTokenizer = pTokenizer;

  while( 1 ){
    const char *zToken;
    int nToken, iStartOffset, iEndOffset, dummy_pos;

    rc = pModule->xNext(pCursor,
                        &zToken, &nToken,
                        &iStartOffset, &iEndOffset,
                        &dummy_pos);
    if( rc!=SQLITE_OK ) break;
    query_add(pQuery, !in_phrase || is_first, string_dup_n(zToken, nToken));
    is_first = 0;
  }

  return pModule->xClose(pCursor);
}

/* Parse a query string, yielding a Query object. */
static int parse_query(fulltext_vtab *v, const char *zQuery, Query *pQuery){
  char *zQuery1 = string_dup(zQuery);
  int in_phrase = 0;
  char *s = zQuery1;
  pQuery->nTerms = 0;
  pQuery->pTerm = NULL;

  while( *s ){
    char *t = s;
    while( *t ){
      if( *t=='"' ){
        *t++ = '\0';
        break;
      }
      ++t;
    }
    if( *s ){
      tokenize_segment(v->pTokenizer, s, in_phrase, pQuery);
    }
    s = t;
    in_phrase = !in_phrase;
  }
  
  free(zQuery1);
  return SQLITE_OK;
}

/* Perform a full-text query; return a list of documents in [pResult]. */
static int fulltext_query(fulltext_vtab *v, const char *zQuery,
                          DocList **pResult){
  Query q;
  int phrase_start = -1;
  int i;
  sqlite3_stmt *pSelect = NULL;
  DocList *d = NULL;

  int rc = parse_query(v, zQuery, &q);
  if( rc!=SQLITE_OK ) return rc;

  /* Merge terms. */
  for(i = 0 ; i < q.nTerms ; ++i){
    /* In each merge step, we need to generate positions whenever we're
     * processing a phrase which hasn't ended yet. */
    int need_positions = i<q.nTerms-1 && !q.pTerm[i+1].is_phrase;
    DocList *next = docListNew(need_positions ? DL_POSITIONS : DL_DOCIDS);
    if( q.pTerm[i].is_phrase ){
      phrase_start = i;
    }
    rc = query_merge(v, &pSelect, q.pTerm[i].zTerm, d, i - phrase_start, next);
    if( rc!=SQLITE_OK ) break;
    if( d!=NULL ){
      docListDelete(d);
    }
    d = next;
  }

  sqlite3_finalize(pSelect);
  query_free(&q);
  *pResult = d;
  return rc;
}

static int fulltextFilter(sqlite3_vtab_cursor *pCursor,
                          int idxNum, const char *idxStr,
                          int argc, sqlite3_value **argv){
  fulltext_cursor *c = (fulltext_cursor *) pCursor;
  fulltext_vtab *v = cursor_vtab(c);
  int rc;
  const char *zStatement;

  c->iCursorType = idxNum;
  switch( idxNum ){
    case QUERY_GENERIC:
      zStatement = "select rowid, content from %_content";
      break;

    case QUERY_FULLTEXT:   /* full-text search */
    {
      const char *zQuery = (const char *)sqlite3_value_text(argv[0]);
      DocList *pResult;
      assert( argc==1 );
      rc = fulltext_query(v, zQuery, &pResult);
      if( rc!=SQLITE_OK ) return rc;
      readerInit(&c->result, pResult);
      zStatement = "select rowid, content from %_content where rowid = ?";
      break;
    }

    default:
      assert( 0 );
  }

  rc = sql_prepare(v->db, v->zName, &c->pStmt, zStatement);
  if( rc!=SQLITE_OK ) return rc;

  return fulltextNext(pCursor);
}

static int fulltextEof(sqlite3_vtab_cursor *pCursor){
  fulltext_cursor *c = (fulltext_cursor *) pCursor;
  return c->eof;
}

static int fulltextColumn(sqlite3_vtab_cursor *pCursor,
                          sqlite3_context *pContext, int idxCol){
  fulltext_cursor *c = (fulltext_cursor *) pCursor;
  const char *s;

  assert( idxCol==0 );
  s = (const char *) sqlite3_column_text(c->pStmt, 1);
  sqlite3_result_text(pContext, s, -1, SQLITE_TRANSIENT);

  return SQLITE_OK;
}

static int fulltextRowid(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
  fulltext_cursor *c = (fulltext_cursor *) pCursor;

  *pRowid = sqlite3_column_int64(c->pStmt, 0);
  return SQLITE_OK;
}

/* Build a hash table containing all terms in zText. */
static int build_terms(Hash *terms, sqlite3_tokenizer *pTokenizer,
                       const char *zText, sqlite_int64 iDocid){
  sqlite3_tokenizer_cursor *pCursor;
  const char *pToken;
  int nTokenBytes;
  int iStartOffset, iEndOffset, iPosition;

  int rc = pTokenizer->pModule->xOpen(pTokenizer, zText, -1, &pCursor);
  if( rc!=SQLITE_OK ) return rc;

  pCursor->pTokenizer = pTokenizer;
  HashInit(terms, HASH_STRING, 1);
  while( SQLITE_OK==pTokenizer->pModule->xNext(pCursor,
                                               &pToken, &nTokenBytes,
                                               &iStartOffset, &iEndOffset,
                                               &iPosition) ){
    DocList *p;

    /* Positions can't be negative; we use -1 as a terminator internally. */
    if( iPosition<0 ) {
      rc = SQLITE_ERROR;  
      goto err;
    }

    p = HashFind(terms, pToken, nTokenBytes);
    if( p==NULL ){
      p = docListNew(DL_POSITIONS_OFFSETS);
      docListAddDocid(p, iDocid);
      HashInsert(terms, pToken, nTokenBytes, p);
    }
    docListAddPosOffset(p, iPosition, iStartOffset, iEndOffset);
  }

err:
  /* TODO(shess) Check return?  Should this be able to cause errors at
  ** this point?  Actually, same question about sqlite3_finalize(),
  ** though one could argue that failure there means that the data is
  ** not durable.  *ponder*
  */
  pTokenizer->pModule->xClose(pCursor);
  return rc;
}
/* Update the %_terms table to map the term [zTerm] to the given rowid. */
static int index_insert_term(fulltext_vtab *v, const char *zTerm, int nTerm,
                             sqlite_int64 iDocid, DocList *p){
  sqlite_int64 iFirst;
  sqlite_int64 iIndexRow;
  DocList doclist;

  int rc = term_chunk_select(v, zTerm, nTerm, iDocid, &iFirst);
  if( rc==SQLITE_DONE ){
    docListInit(&doclist, DL_POSITIONS_OFFSETS, 0, 0);
    if( docListUpdate(&doclist, iDocid, p) ){
      rc = term_insert(v, zTerm, nTerm, iDocid, &doclist);
      docListDestroy(&doclist);
      return rc;
    }
    return SQLITE_OK;
  }
  if( rc!=SQLITE_ROW ) return SQLITE_ERROR;

  /* This word is in the index; add this document ID to its blob. */

  rc = term_select(v, zTerm, nTerm, iFirst, &iIndexRow, &doclist);
  if( rc!=SQLITE_OK ) return rc;

  if( docListUpdate(&doclist, iDocid, p) ){
    /* If the blob is too big, split it in half. */
    if( doclist.nData>CHUNK_MAX ){
      DocList half;
      if( docListSplit(&doclist, &half) ){
        rc = term_insert(v, zTerm, nTerm, firstDocid(&half), &half);
        docListDestroy(&half);
        if( rc!=SQLITE_OK ) goto err;
      }
    }
    rc = term_update(v, iIndexRow, &doclist);
  }

err:
  docListDestroy(&doclist);
  return rc;
}

/* Insert a row into the full-text index; set *piRowid to be the ID of the
 * new row. */
static int index_insert(fulltext_vtab *v,
                        sqlite3_value *pRequestRowid, const char *zText,
                        sqlite_int64 *piRowid){
  Hash terms;  /* maps term string -> PosList */
  HashElem *e;

  int rc = content_insert(v, pRequestRowid, zText, -1);
  if( rc!=SQLITE_OK ) return rc;
  *piRowid = sqlite3_last_insert_rowid(v->db);

  if( !zText ) return SQLITE_OK;   /* nothing to index */

  rc = build_terms(&terms, v->pTokenizer, zText, *piRowid);
  if( rc!=SQLITE_OK ) return rc;

  for(e=HashFirst(&terms); e; e=HashNext(e)){
    DocList *p = HashData(e);
    rc = index_insert_term(v, HashKey(e), HashKeysize(e), *piRowid, p);
    if( rc!=SQLITE_OK ) break;
  }

  for(e=HashFirst(&terms); e; e=HashNext(e)){
    DocList *p = HashData(e);
    docListDelete(p);
  }
  HashClear(&terms);
  return rc;
}

static int index_delete_term(fulltext_vtab *v, const char *zTerm, int nTerm,
                             sqlite_int64 iDocid){
  sqlite_int64 iFirst;
  sqlite_int64 iIndexRow;
  DocList doclist;

  int rc = term_chunk_select(v, zTerm, nTerm, iDocid, &iFirst);
  if( rc!=SQLITE_ROW ) return SQLITE_ERROR;

  rc = term_select(v, zTerm, nTerm, iFirst, &iIndexRow, &doclist);
  if( rc!=SQLITE_OK ) return rc;

  if( docListUpdate(&doclist, iDocid, NULL) ){
    if( doclist.nData>0 ){
      rc = term_update(v, iIndexRow, &doclist);
    } else {  /* empty posting list */
      rc = term_delete(v, iIndexRow);
    }
  }
  docListDestroy(&doclist);
  return rc;
}

/* Delete a row from the full-text index. */
static int index_delete(fulltext_vtab *v, sqlite_int64 iRow){
  char *zText;
  Hash terms;
  HashElem *e;

  int rc = content_select(v, iRow, &zText);
  if( rc!=SQLITE_OK ) return rc;

  rc = build_terms(&terms, v->pTokenizer, zText, iRow);
  free(zText);
  if( rc!=SQLITE_OK ) return rc;

  for(e=HashFirst(&terms); e; e=HashNext(e)){
    rc = index_delete_term(v, HashKey(e), HashKeysize(e), iRow);
    if( rc!=SQLITE_OK ) break;
  }
  for(e=HashFirst(&terms); e; e=HashNext(e)){
    DocList *p = HashData(e);
    docListDelete(p);
  }
  HashClear(&terms);

  return content_delete(v, iRow);
}

static int fulltextUpdate(sqlite3_vtab *pVtab, int nArg, sqlite3_value **ppArg,
                   sqlite_int64 *pRowid){
  fulltext_vtab *v = (fulltext_vtab *) pVtab;

  if( nArg<2 ){
    return index_delete(v, sqlite3_value_int64(ppArg[0]));
  }

  if( sqlite3_value_type(ppArg[0]) != SQLITE_NULL ){
    return SQLITE_ERROR;   /* an update; not yet supported */
  }

  assert( nArg==3 );    /* ppArg[1] = rowid, ppArg[2] = content */
  return index_insert(v, ppArg[1],
                      (const char *)sqlite3_value_text(ppArg[2]), pRowid);
}

static sqlite3_module fulltextModule = {
  0,
  fulltextCreate,
  fulltextConnect,
  fulltextBestIndex,
  fulltextDisconnect,
  fulltextDestroy,
  fulltextOpen,
  fulltextClose,
  fulltextFilter,
  fulltextNext,
  fulltextEof,
  fulltextColumn,
  fulltextRowid,
  fulltextUpdate
};

int fulltext_init(sqlite3 *db){
 return sqlite3_create_module(db, "fulltext", &fulltextModule, 0);
}

#if !SQLITE_CORE
int sqlite3_extension_init(sqlite3 *db, char **pzErrMsg,
                           const sqlite3_api_routines *pApi){
 SQLITE_EXTENSION_INIT2(pApi)
 return fulltext_init(db);
}
#endif

#include "sqlite3.h"

#ifdef __cplusplus
extern "C" {
#endif  /* __cplusplus */

int fulltext_init(sqlite3 *db);

#ifdef __cplusplus
}  /* extern "C" */
#endif  /* __cplusplus */

/*
** The author disclaims copyright to this source code.
**
*************************************************************************
** Implementation of the "simple" full-text-search tokenizer.
*/

#include <assert.h>
#if !defined(__APPLE__)
#include <malloc.h>
#else
#include <stdlib.h>
#endif
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#include "tokenizer.h"

/* Duplicate a string; the caller must free() the returned string.
 * (We don't use strdup() since it's not part of the standard C library and
 * may not be available everywhere.) */
/* TODO(shess) Copied from fulltext.c, consider util.c for such
** things. */
static char *string_dup(const char *s){
  char *str = malloc(strlen(s) + 1);
  strcpy(str, s);
  return str;
}

typedef struct simple_tokenizer {
  sqlite3_tokenizer base;
  const char *zDelim;          /* token delimiters */
} simple_tokenizer;

typedef struct simple_tokenizer_cursor {
  sqlite3_tokenizer_cursor base;
  const char *pInput;          /* input we are tokenizing */
  int nBytes;                  /* size of the input */
  const char *pCurrent;        /* current position in pInput */
  int iToken;                  /* index of next token to be returned */
  char *zToken;                /* storage for current token */
  int nTokenBytes;             /* actual size of current token */
  int nTokenAllocated;         /* space allocated to zToken buffer */
} simple_tokenizer_cursor;

static sqlite3_tokenizer_module simpleTokenizerModule;/* forward declaration */

static int simpleCreate(
  int argc, const char **argv,
  sqlite3_tokenizer **ppTokenizer
){
  simple_tokenizer *t;

  t = (simple_tokenizer *) malloc(sizeof(simple_tokenizer));
  /* TODO(shess) Delimiters need to remain the same from run to run,
  ** else we need to reindex.  One solution would be a meta-table to
  ** track such information in the database, then we'd only want this
  ** information on the initial create.
  */
  if( argc>1 ){
    t->zDelim = string_dup(argv[1]);
  } else {
    /* Build a string excluding alphanumeric ASCII characters */
    char zDelim[0x80];               /* nul-terminated, so nul not a member */
    int i, j;
    for(i=1, j=0; i<0x80; i++){
      if( !isalnum(i) ){
        zDelim[j++] = i;
      }
    }
    zDelim[j++] = '\0';
    assert( j<=sizeof(zDelim) );
    t->zDelim = string_dup(zDelim);
  }

  *ppTokenizer = &t->base;
  return SQLITE_OK;
}

static int simpleDestroy(sqlite3_tokenizer *pTokenizer){
  simple_tokenizer *t = (simple_tokenizer *) pTokenizer;

  free((void *) t->zDelim);
  free(t);

  return SQLITE_OK;
}

static int simpleOpen(
  sqlite3_tokenizer *pTokenizer,
  const char *pInput, int nBytes,
  sqlite3_tokenizer_cursor **ppCursor
){
  simple_tokenizer_cursor *c;

  c = (simple_tokenizer_cursor *) malloc(sizeof(simple_tokenizer_cursor));
  c->pInput = pInput;
  c->nBytes = nBytes<0 ? (int) strlen(pInput) : nBytes;
  c->pCurrent = c->pInput;        /* start tokenizing at the beginning */
  c->iToken = 0;
  c->zToken = NULL;               /* no space allocated, yet. */
  c->nTokenBytes = 0;
  c->nTokenAllocated = 0;

  *ppCursor = &c->base;
  return SQLITE_OK;
}

static int simpleClose(sqlite3_tokenizer_cursor *pCursor){
  simple_tokenizer_cursor *c = (simple_tokenizer_cursor *) pCursor;

  if( NULL!=c->zToken ){
    free(c->zToken);
  }
  free(c);

  return SQLITE_OK;
}

static int simpleNext(
  sqlite3_tokenizer_cursor *pCursor,
  const char **ppToken, int *pnBytes,
  int *piStartOffset, int *piEndOffset, int *piPosition
){
  simple_tokenizer_cursor *c = (simple_tokenizer_cursor *) pCursor;
  simple_tokenizer *t = (simple_tokenizer *) pCursor->pTokenizer;
  int ii;

  while( c->pCurrent-c->pInput<c->nBytes ){
    int n = (int) strcspn(c->pCurrent, t->zDelim);
    if( n>0 ){
      if( n+1>c->nTokenAllocated ){
        c->zToken = realloc(c->zToken, n+1);
      }
      for(ii=0; ii<n; ii++){
        /* TODO(shess) This needs expansion to handle UTF-8
        ** case-insensitivity.
        */
        char ch = c->pCurrent[ii];
        c->zToken[ii] = (unsigned char)ch<0x80 ? tolower(ch) : ch;
      }
      c->zToken[n] = '\0';
      *ppToken = c->zToken;
      *pnBytes = n;
      *piStartOffset = (int) (c->pCurrent-c->pInput);
      *piEndOffset = *piStartOffset+n;
      *piPosition = c->iToken++;
      c->pCurrent += n + 1;

      return SQLITE_OK;
    }
    c->pCurrent += n + 1;
    /* TODO(shess) could strspn() to skip delimiters en masse.  Needs
    ** to happen in two places, though, which is annoying.
    */
  }
  return SQLITE_DONE;
}

static sqlite3_tokenizer_module simpleTokenizerModule = {
  0,
  simpleCreate,
  simpleDestroy,
  simpleOpen,
  simpleClose,
  simpleNext,
};

void get_simple_tokenizer_module(
  sqlite3_tokenizer_module **ppModule
){
  *ppModule = &simpleTokenizerModule;
}

/*
** 2006 July 10
**
** The author disclaims copyright to this source code.
**
*************************************************************************
** Defines the interface to tokenizers used by fulltext-search.  There
** are three basic components:
**
** sqlite3_tokenizer_module is a singleton defining the tokenizer
** interface functions.  This is essentially the class structure for
** tokenizers.
**
** sqlite3_tokenizer is used to define a particular tokenizer, perhaps
** including customization information defined at creation time.
**
** sqlite3_tokenizer_cursor is generated by a tokenizer to generate
** tokens from a particular input.
*/
#ifndef _TOKENIZER_H_
#define _TOKENIZER_H_

/* TODO(shess) Only used for SQLITE_OK and SQLITE_DONE at this time.
** If tokenizers are to be allowed to call sqlite3_*() functions, then
** we will need a way to register the API consistently.
*/
#include "sqlite3.h"

/*
** Structures used by the tokenizer interface.
*/
typedef struct sqlite3_tokenizer sqlite3_tokenizer;
typedef struct sqlite3_tokenizer_cursor sqlite3_tokenizer_cursor;
typedef struct sqlite3_tokenizer_module sqlite3_tokenizer_module;

struct sqlite3_tokenizer_module {
  int iVersion;                  /* currently 0 */

  /*
  ** Create and destroy a tokenizer.  argc/argv are passed down from
  ** the fulltext virtual table creation to allow customization.
  */
  int (*xCreate)(int argc, const char **argv,
                 sqlite3_tokenizer **ppTokenizer);
  int (*xDestroy)(sqlite3_tokenizer *pTokenizer);

  /*
  ** Tokenize a particular input.  Call xOpen() to prepare to
  ** tokenize, xNext() repeatedly until it returns SQLITE_DONE, then
  ** xClose() to free any internal state.  The pInput passed to
  ** xOpen() must exist until the cursor is closed.  The ppToken
  ** result from xNext() is only valid until the next call to xNext()
  ** or until xClose() is called.
  */
  /* TODO(shess) current implementation requires pInput to be
  ** nul-terminated.  This should either be fixed, or pInput/nBytes
  ** should be converted to zInput.
  */
  int (*xOpen)(sqlite3_tokenizer *pTokenizer,
               const char *pInput, int nBytes,
               sqlite3_tokenizer_cursor **ppCursor);
  int (*xClose)(sqlite3_tokenizer_cursor *pCursor);
  int (*xNext)(sqlite3_tokenizer_cursor *pCursor,
               const char **ppToken, int *pnBytes,
               int *piStartOffset, int *piEndOffset, int *piPosition);
};

struct sqlite3_tokenizer {
  sqlite3_tokenizer_module *pModule;  /* The module for this tokenizer */
  /* Tokenizer implementations will typically add additional fields */
};

struct sqlite3_tokenizer_cursor {
  sqlite3_tokenizer *pTokenizer;       /* Tokenizer for this cursor. */
  /* Tokenizer implementations will typically add additional fields */
};

/*
** Get the module for a tokenizer which generates tokens based on a
** set of non-token characters.  The default is to break tokens at any
** non-alnum character, though the set of delimiters can also be
** specified by the first argv argument to xCreate().
*/
/* TODO(shess) This doesn't belong here.  Need some sort of
** registration process.
*/
void get_simple_tokenizer_module(sqlite3_tokenizer_module **ppModule);

#endif /* _TOKENIZER_H_ */

EXPORTS
sqlite3_aggregate_context
sqlite3_aggregate_count
sqlite3_bind_blob
sqlite3_bind_double
sqlite3_bind_int
sqlite3_bind_int64
sqlite3_bind_null
sqlite3_bind_parameter_count
sqlite3_bind_parameter_index
sqlite3_bind_parameter_name
sqlite3_bind_text
sqlite3_bind_text16
sqlite3_busy_handler
sqlite3_busy_timeout
sqlite3_changes
sqlite3_close
sqlite3_collation_needed
sqlite3_collation_needed16
sqlite3_column_blob
sqlite3_column_bytes
sqlite3_column_bytes16
sqlite3_column_count
sqlite3_column_decltype
sqlite3_column_decltype16
sqlite3_column_double
sqlite3_column_int
sqlite3_column_int64
sqlite3_column_name
sqlite3_column_name16
sqlite3_column_text
sqlite3_column_text16
sqlite3_column_type
sqlite3_commit_hook
sqlite3_complete
sqlite3_complete16
sqlite3_create_collation
sqlite3_create_collation16
sqlite3_create_function
sqlite3_create_function16
sqlite3_data_count
sqlite3_db_handle
sqlite3_enable_load_extension
sqlite3_enable_shared_cache
sqlite3_errcode
sqlite3_errmsg
sqlite3_errmsg16
sqlite3_exec
sqlite3_expired
sqlite3_finalize
sqlite3_free
sqlite3_free_table
sqlite3_get_autocommit
sqlite3_get_auxdata
sqlite3_get_table
sqlite3_global_recover
sqlite3_interrupt
sqlite3_last_insert_rowid
sqlite3_libversion
sqlite3_libversion_number
sqlite3_load_extension
sqlite3_malloc
sqlite3_mprintf
sqlite3_open
sqlite3_open16
sqlite3_prepare
sqlite3_prepare16
sqlite3_progress_handler
sqlite3_realloc
sqlite3_reset
sqlite3_result_blob
sqlite3_result_double
sqlite3_result_error
sqlite3_result_error16
sqlite3_result_int
sqlite3_result_int64
sqlite3_result_null
sqlite3_result_text
sqlite3_result_text16
sqlite3_result_text16be
sqlite3_result_text16le
sqlite3_result_value
sqlite3_rollback_hook
sqlite3_set_authorizer
sqlite3_set_auxdata
sqlite3_snprintf
sqlite3_step
sqlite3_thread_cleanup
sqlite3_total_changes
sqlite3_trace
sqlite3_transfer_bindings
sqlite3_update_hook
sqlite3_user_data
sqlite3_value_blob
sqlite3_value_bytes
sqlite3_value_bytes16
sqlite3_value_double
sqlite3_value_int
sqlite3_value_int64
sqlite3_value_text
sqlite3_value_text16
sqlite3_value_text16be
sqlite3_value_text16le
sqlite3_value_type
sqlite3_vmprintf

/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.358 2007/04/24 17:35:59 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.

        rc = ptrmapPutOvfl(pPage, i);
        if( rc!=SQLITE_OK ){
          goto end_shallow_balance;
        }
      }
    }
#endif
    if( rc!=SQLITE_OK ) goto end_shallow_balance;
    releasePage(pChild);
  }
end_shallow_balance:
  sqliteFree(apCell);
  return rc;
}

/*
** 2005 January 20
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are not a part of the official
** SQLite API.  These routines are unsupported.
**
** $Id: experimental.c,v 1.4 2006/01/31 20:49:13 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"

/*
** Set all the parameters in the compiled SQL statement to NULL.
*/
int sqlite3_clear_bindings(sqlite3_stmt *pStmt){
  int i;
  int rc = SQLITE_OK;
  for(i=1; rc==SQLITE_OK && i<=sqlite3_bind_parameter_count(pStmt); i++){
    rc = sqlite3_bind_null(pStmt, i);
  }
  return rc;
}

/*
** Sleep for a little while.  Return the amount of time slept.
*/
int sqlite3_sleep(int ms){
  return sqlite3OsSleep(ms);
}

/*
** SQLite uses this code for testing only.  It is not a part of
** the SQLite library.  This file implements two new TCL commands
** "md5" and "md5file" that compute md5 checksums on arbitrary text
** and on complete files.  These commands are used by the "testfixture"
** program to help verify the correct operation of the SQLite library.
**
** The original use of these TCL commands was to test the ROLLBACK
** feature of SQLite.  First compute the MD5-checksum of the database.
** Then make some changes but rollback the changes rather than commit
** them.  Compute a second MD5-checksum of the file and verify that the
** two checksums are the same.  Such is the original use of this code.
** New uses may have been added since this comment was written.
*/
/*
 * This code implements the MD5 message-digest algorithm.
 * The algorithm is due to Ron Rivest.  This code was
 * written by Colin Plumb in 1993, no copyright is claimed.
 * This code is in the public domain; do with it what you wish.
 *
 * Equivalent code is available from RSA Data Security, Inc.
 * This code has been tested against that, and is equivalent,
 * except that you don't need to include two pages of legalese
 * with every copy.
 *
 * To compute the message digest of a chunk of bytes, declare an
 * MD5Context structure, pass it to MD5Init, call MD5Update as
 * needed on buffers full of bytes, and then call MD5Final, which
 * will fill a supplied 16-byte array with the digest.
 */
#include <tcl.h>
#include <string.h>
#include "sqlite3.h"

/*
 * If compiled on a machine that doesn't have a 32-bit integer,
 * you just set "uint32" to the appropriate datatype for an
 * unsigned 32-bit integer.  For example:
 *
 *       cc -Duint32='unsigned long' md5.c
 *
 */
#ifndef uint32
#  define uint32 unsigned int
#endif

struct Context {
  uint32 buf[4];
  uint32 bits[2];
  unsigned char in[64];
};
typedef char MD5Context[88];

/*
 * Note: this code is harmless on little-endian machines.
 */
static void byteReverse (unsigned char *buf, unsigned longs){
        uint32 t;
        do {
                t = (uint32)((unsigned)buf[3]<<8 | buf[2]) << 16 |
                            ((unsigned)buf[1]<<8 | buf[0]);
                *(uint32 *)buf = t;
                buf += 4;
        } while (--longs);
}
/* The four core functions - F1 is optimized somewhat */

/* #define F1(x, y, z) (x & y | ~x & z) */
#define F1(x, y, z) (z ^ (x & (y ^ z)))
#define F2(x, y, z) F1(z, x, y)
#define F3(x, y, z) (x ^ y ^ z)
#define F4(x, y, z) (y ^ (x | ~z))

/* This is the central step in the MD5 algorithm. */
#define MD5STEP(f, w, x, y, z, data, s) \
        ( w += f(x, y, z) + data,  w = w<<s | w>>(32-s),  w += x )

/*
 * The core of the MD5 algorithm, this alters an existing MD5 hash to
 * reflect the addition of 16 longwords of new data.  MD5Update blocks
 * the data and converts bytes into longwords for this routine.
 */
static void MD5Transform(uint32 buf[4], const uint32 in[16]){
        register uint32 a, b, c, d;

        a = buf[0];
        b = buf[1];
        c = buf[2];
        d = buf[3];

        MD5STEP(F1, a, b, c, d, in[ 0]+0xd76aa478,  7);
        MD5STEP(F1, d, a, b, c, in[ 1]+0xe8c7b756, 12);
        MD5STEP(F1, c, d, a, b, in[ 2]+0x242070db, 17);
        MD5STEP(F1, b, c, d, a, in[ 3]+0xc1bdceee, 22);
        MD5STEP(F1, a, b, c, d, in[ 4]+0xf57c0faf,  7);
        MD5STEP(F1, d, a, b, c, in[ 5]+0x4787c62a, 12);
        MD5STEP(F1, c, d, a, b, in[ 6]+0xa8304613, 17);
        MD5STEP(F1, b, c, d, a, in[ 7]+0xfd469501, 22);
        MD5STEP(F1, a, b, c, d, in[ 8]+0x698098d8,  7);
        MD5STEP(F1, d, a, b, c, in[ 9]+0x8b44f7af, 12);
        MD5STEP(F1, c, d, a, b, in[10]+0xffff5bb1, 17);
        MD5STEP(F1, b, c, d, a, in[11]+0x895cd7be, 22);
        MD5STEP(F1, a, b, c, d, in[12]+0x6b901122,  7);
        MD5STEP(F1, d, a, b, c, in[13]+0xfd987193, 12);
        MD5STEP(F1, c, d, a, b, in[14]+0xa679438e, 17);
        MD5STEP(F1, b, c, d, a, in[15]+0x49b40821, 22);

        MD5STEP(F2, a, b, c, d, in[ 1]+0xf61e2562,  5);
        MD5STEP(F2, d, a, b, c, in[ 6]+0xc040b340,  9);
        MD5STEP(F2, c, d, a, b, in[11]+0x265e5a51, 14);
        MD5STEP(F2, b, c, d, a, in[ 0]+0xe9b6c7aa, 20);
        MD5STEP(F2, a, b, c, d, in[ 5]+0xd62f105d,  5);
        MD5STEP(F2, d, a, b, c, in[10]+0x02441453,  9);
        MD5STEP(F2, c, d, a, b, in[15]+0xd8a1e681, 14);
        MD5STEP(F2, b, c, d, a, in[ 4]+0xe7d3fbc8, 20);
        MD5STEP(F2, a, b, c, d, in[ 9]+0x21e1cde6,  5);
        MD5STEP(F2, d, a, b, c, in[14]+0xc33707d6,  9);
        MD5STEP(F2, c, d, a, b, in[ 3]+0xf4d50d87, 14);
        MD5STEP(F2, b, c, d, a, in[ 8]+0x455a14ed, 20);
        MD5STEP(F2, a, b, c, d, in[13]+0xa9e3e905,  5);
        MD5STEP(F2, d, a, b, c, in[ 2]+0xfcefa3f8,  9);
        MD5STEP(F2, c, d, a, b, in[ 7]+0x676f02d9, 14);
        MD5STEP(F2, b, c, d, a, in[12]+0x8d2a4c8a, 20);

        MD5STEP(F3, a, b, c, d, in[ 5]+0xfffa3942,  4);
        MD5STEP(F3, d, a, b, c, in[ 8]+0x8771f681, 11);
        MD5STEP(F3, c, d, a, b, in[11]+0x6d9d6122, 16);
        MD5STEP(F3, b, c, d, a, in[14]+0xfde5380c, 23);
        MD5STEP(F3, a, b, c, d, in[ 1]+0xa4beea44,  4);
        MD5STEP(F3, d, a, b, c, in[ 4]+0x4bdecfa9, 11);
        MD5STEP(F3, c, d, a, b, in[ 7]+0xf6bb4b60, 16);
        MD5STEP(F3, b, c, d, a, in[10]+0xbebfbc70, 23);
        MD5STEP(F3, a, b, c, d, in[13]+0x289b7ec6,  4);
        MD5STEP(F3, d, a, b, c, in[ 0]+0xeaa127fa, 11);
        MD5STEP(F3, c, d, a, b, in[ 3]+0xd4ef3085, 16);
        MD5STEP(F3, b, c, d, a, in[ 6]+0x04881d05, 23);
        MD5STEP(F3, a, b, c, d, in[ 9]+0xd9d4d039,  4);
        MD5STEP(F3, d, a, b, c, in[12]+0xe6db99e5, 11);
        MD5STEP(F3, c, d, a, b, in[15]+0x1fa27cf8, 16);
        MD5STEP(F3, b, c, d, a, in[ 2]+0xc4ac5665, 23);

        MD5STEP(F4, a, b, c, d, in[ 0]+0xf4292244,  6);
        MD5STEP(F4, d, a, b, c, in[ 7]+0x432aff97, 10);
        MD5STEP(F4, c, d, a, b, in[14]+0xab9423a7, 15);
        MD5STEP(F4, b, c, d, a, in[ 5]+0xfc93a039, 21);
        MD5STEP(F4, a, b, c, d, in[12]+0x655b59c3,  6);
        MD5STEP(F4, d, a, b, c, in[ 3]+0x8f0ccc92, 10);
        MD5STEP(F4, c, d, a, b, in[10]+0xffeff47d, 15);
        MD5STEP(F4, b, c, d, a, in[ 1]+0x85845dd1, 21);
        MD5STEP(F4, a, b, c, d, in[ 8]+0x6fa87e4f,  6);
        MD5STEP(F4, d, a, b, c, in[15]+0xfe2ce6e0, 10);
        MD5STEP(F4, c, d, a, b, in[ 6]+0xa3014314, 15);
        MD5STEP(F4, b, c, d, a, in[13]+0x4e0811a1, 21);
        MD5STEP(F4, a, b, c, d, in[ 4]+0xf7537e82,  6);
        MD5STEP(F4, d, a, b, c, in[11]+0xbd3af235, 10);
        MD5STEP(F4, c, d, a, b, in[ 2]+0x2ad7d2bb, 15);
        MD5STEP(F4, b, c, d, a, in[ 9]+0xeb86d391, 21);

        buf[0] += a;
        buf[1] += b;
        buf[2] += c;
        buf[3] += d;
}

/*
 * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
 * initialization constants.
 */
static void MD5Init(MD5Context *pCtx){
        struct Context *ctx = (struct Context *)pCtx;
        ctx->buf[0] = 0x67452301;
        ctx->buf[1] = 0xefcdab89;
        ctx->buf[2] = 0x98badcfe;
        ctx->buf[3] = 0x10325476;
        ctx->bits[0] = 0;
        ctx->bits[1] = 0;
}

/*
 * Update context to reflect the concatenation of another buffer full
 * of bytes.
 */
static 
void MD5Update(MD5Context *pCtx, const unsigned char *buf, unsigned int len){
        struct Context *ctx = (struct Context *)pCtx;
        uint32 t;

        /* Update bitcount */

        t = ctx->bits[0];
        if ((ctx->bits[0] = t + ((uint32)len << 3)) < t)
                ctx->bits[1]++; /* Carry from low to high */
        ctx->bits[1] += len >> 29;

        t = (t >> 3) & 0x3f;    /* Bytes already in shsInfo->data */

        /* Handle any leading odd-sized chunks */

        if ( t ) {
                unsigned char *p = (unsigned char *)ctx->in + t;

                t = 64-t;
                if (len < t) {
                        memcpy(p, buf, len);
                        return;
                }
                memcpy(p, buf, t);
                byteReverse(ctx->in, 16);
                MD5Transform(ctx->buf, (uint32 *)ctx->in);
                buf += t;
                len -= t;
        }

        /* Process data in 64-byte chunks */

        while (len >= 64) {
                memcpy(ctx->in, buf, 64);
                byteReverse(ctx->in, 16);
                MD5Transform(ctx->buf, (uint32 *)ctx->in);
                buf += 64;
                len -= 64;
        }

        /* Handle any remaining bytes of data. */

        memcpy(ctx->in, buf, len);
}

/*
 * Final wrapup - pad to 64-byte boundary with the bit pattern 
 * 1 0* (64-bit count of bits processed, MSB-first)
 */
static void MD5Final(unsigned char digest[16], MD5Context *pCtx){
        struct Context *ctx = (struct Context *)pCtx;
        unsigned count;
        unsigned char *p;

        /* Compute number of bytes mod 64 */
        count = (ctx->bits[0] >> 3) & 0x3F;

        /* Set the first char of padding to 0x80.  This is safe since there is
           always at least one byte free */
        p = ctx->in + count;
        *p++ = 0x80;

        /* Bytes of padding needed to make 64 bytes */
        count = 64 - 1 - count;

        /* Pad out to 56 mod 64 */
        if (count < 8) {
                /* Two lots of padding:  Pad the first block to 64 bytes */
                memset(p, 0, count);
                byteReverse(ctx->in, 16);
                MD5Transform(ctx->buf, (uint32 *)ctx->in);

                /* Now fill the next block with 56 bytes */
                memset(ctx->in, 0, 56);
        } else {
                /* Pad block to 56 bytes */
                memset(p, 0, count-8);
        }
        byteReverse(ctx->in, 14);

        /* Append length in bits and transform */
        ((uint32 *)ctx->in)[ 14 ] = ctx->bits[0];
        ((uint32 *)ctx->in)[ 15 ] = ctx->bits[1];

        MD5Transform(ctx->buf, (uint32 *)ctx->in);
        byteReverse((unsigned char *)ctx->buf, 4);
        memcpy(digest, ctx->buf, 16);
        memset(ctx, 0, sizeof(ctx));    /* In case it's sensitive */
}

/*
** Convert a digest into base-16.  digest should be declared as
** "unsigned char digest[16]" in the calling function.  The MD5
** digest is stored in the first 16 bytes.  zBuf should
** be "char zBuf[33]".
*/
static void DigestToBase16(unsigned char *digest, char *zBuf){
  static char const zEncode[] = "0123456789abcdef";
  int i, j;

  for(j=i=0; i<16; i++){
    int a = digest[i];
    zBuf[j++] = zEncode[(a>>4)&0xf];
    zBuf[j++] = zEncode[a & 0xf];
  }
  zBuf[j] = 0;
}

/*
** A TCL command for md5.  The argument is the text to be hashed.  The
** Result is the hash in base64.  
*/
static int md5_cmd(void*cd, Tcl_Interp *interp, int argc, const char **argv){
  MD5Context ctx;
  unsigned char digest[16];

  if( argc!=2 ){
    Tcl_AppendResult(interp,"wrong # args: should be \"", argv[0], 
        " TEXT\"", 0);
    return TCL_ERROR;
  }
  MD5Init(&ctx);
  MD5Update(&ctx, (unsigned char*)argv[1], (unsigned)strlen(argv[1]));
  MD5Final(digest, &ctx);
  DigestToBase16(digest, interp->result);
  return TCL_OK;
}

/*
** A TCL command to take the md5 hash of a file.  The argument is the
** name of the file.
*/
static int md5file_cmd(void*cd, Tcl_Interp*interp, int argc, const char **argv){
  FILE *in;
  MD5Context ctx;
  unsigned char digest[16];
  char zBuf[10240];

  if( argc!=2 ){
    Tcl_AppendResult(interp,"wrong # args: should be \"", argv[0], 
        " FILENAME\"", 0);
    return TCL_ERROR;
  }
  in = fopen(argv[1],"rb");
  if( in==0 ){
    Tcl_AppendResult(interp,"unable to open file \"", argv[1], 
         "\" for reading", 0);
    return TCL_ERROR;
  }
  MD5Init(&ctx);
  for(;;){
    int n;
    n = fread(zBuf, 1, sizeof(zBuf), in);
    if( n<=0 ) break;
    MD5Update(&ctx, (unsigned char*)zBuf, (unsigned)n);
  }
  fclose(in);
  MD5Final(digest, &ctx);
  DigestToBase16(digest, interp->result);
  return TCL_OK;
}

/*
** Register the two TCL commands above with the TCL interpreter.
*/
int Md5_Init(Tcl_Interp *interp){
  Tcl_CreateCommand(interp, "md5", (Tcl_CmdProc*)md5_cmd, 0, 0);
  Tcl_CreateCommand(interp, "md5file", (Tcl_CmdProc*)md5file_cmd, 0, 0);
  return TCL_OK;
}

/*
** During testing, the special md5sum() aggregate function is available.
** inside SQLite.  The following routines implement that function.
*/
static void md5step(sqlite3_context *context, int argc, sqlite3_value **argv){
  MD5Context *p;
  int i;
  if( argc<1 ) return;
  p = sqlite3_aggregate_context(context, sizeof(*p));
  if( p==0 ) return;
  if( sqlite3_aggregate_count(context)==1 ){
    MD5Init(p);
  }
  for(i=0; i<argc; i++){
    const char *zData = (char*)sqlite3_value_text(argv[i]);
    if( zData ){
      MD5Update(p, (unsigned char*)zData, strlen(zData));
    }
  }
}
static void md5finalize(sqlite3_context *context){
  MD5Context *p;
  unsigned char digest[16];
  char zBuf[33];
  p = sqlite3_aggregate_context(context, sizeof(*p));
  MD5Final(digest,p);
  DigestToBase16(digest, zBuf);
  sqlite3_result_text(context, zBuf, -1, SQLITE_TRANSIENT);
}
void Md5_Register(sqlite3 *db){
  sqlite3_create_function(db, "md5sum", -1, SQLITE_UTF8, 0, 0, 
      md5step, md5finalize);
}

/*
** 2004 May 22
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** This file contains code that is specific to Unix systems. It is used
** for testing SQLite only.
*/
#if OS_TEST              /* This file is used for the test backend only */
#include "sqliteInt.h"
#include "os.h"          /* Must be first to enable large file support */

#define sqlite3OsOpenReadWrite     sqlite3RealOpenReadWrite
#define sqlite3OsOpenExclusive     sqlite3RealOpenExclusive
#define sqlite3OsOpenReadOnly      sqlite3RealOpenReadOnly
#define sqlite3OsOpenDirectory     sqlite3RealOpenDirectory
#define sqlite3OsClose             sqlite3RealClose
#define sqlite3OsRead              sqlite3RealRead
#define sqlite3OsWrite             sqlite3RealWrite
#define sqlite3OsSeek              sqlite3RealSeek
#define sqlite3OsSync              sqlite3RealSync
#define sqlite3OsTruncate          sqlite3RealTruncate
#define sqlite3OsFileSize          sqlite3RealFileSize
#define sqlite3OsLock              sqlite3RealLock
#define sqlite3OsUnlock            sqlite3RealUnlock
#define sqlite3OsCheckReservedLock sqlite3RealCheckReservedLock

#define OsFile OsRealFile
#define OS_UNIX 1
#include "os_unix.c"
#undef OS_UNIX
#undef OsFile

#undef sqlite3OsOpenReadWrite     
#undef sqlite3OsOpenExclusive     
#undef sqlite3OsOpenReadOnly      
#undef sqlite3OsOpenDirectory     
#undef sqlite3OsClose             
#undef sqlite3OsRead              
#undef sqlite3OsWrite             
#undef sqlite3OsSeek              
#undef sqlite3OsSync              
#undef sqlite3OsTruncate          
#undef sqlite3OsFileSize          
#undef sqlite3OsLock              
#undef sqlite3OsUnlock            
#undef sqlite3OsCheckReservedLock 

#define BLOCKSIZE 512
#define BLOCK_OFFSET(x) ((x) * BLOCKSIZE)


/*
** The following variables control when a simulated crash occurs.
**
** If iCrashDelay is non-zero, then zCrashFile contains (full path) name of
** a file that SQLite will call sqlite3OsSync() on. Each time this happens
** iCrashDelay is decremented. If iCrashDelay is zero after being
** decremented, a "crash" occurs during the sync() operation.
**
** In other words, a crash occurs the iCrashDelay'th time zCrashFile is
** synced.
*/
static int iCrashDelay = 0;
char zCrashFile[256];

/*
** Set the value of the two crash parameters.
*/
void sqlite3SetCrashParams(int iDelay, char const *zFile){
  sqlite3OsEnterMutex();
  assert( strlen(zFile)<256 );
  strcpy(zCrashFile, zFile);
  iCrashDelay = iDelay;
  sqlite3OsLeaveMutex();
}

/*
** File zPath is being sync()ed. Return non-zero if this should
** cause a crash.
*/
static int crashRequired(char const *zPath){
  int r;
  int n;
  sqlite3OsEnterMutex();
  n = strlen(zCrashFile);
  if( zCrashFile[n-1]=='*' ){
    n--;
  }else if( strlen(zPath)>n ){
    n = strlen(zPath);
  }
  r = 0;
  if( iCrashDelay>0 && strncmp(zPath, zCrashFile, n)==0 ){
    iCrashDelay--;
    if( iCrashDelay<=0 ){
      r = 1;
    }
  }
  sqlite3OsLeaveMutex();
  return r;
}


static OsTestFile *pAllFiles = 0;

/*
** Initialise the os_test.c specific fields of pFile.
*/
static void initFile(OsFile *id, char const *zName){
  OsTestFile *pFile = (OsTestFile *)
      sqliteMalloc(sizeof(OsTestFile) + strlen(zName)+1);
  pFile->nMaxWrite = 0; 
  pFile->nBlk = 0; 
  pFile->apBlk = 0; 
  pFile->zName = (char *)(&pFile[1]);
  strcpy(pFile->zName, zName);
  *id = pFile;
  pFile->pNext = pAllFiles;
  pAllFiles = pFile;
}

/*
** Undo the work done by initFile. Delete the OsTestFile structure
** and unlink the structure from the pAllFiles list.
*/
static void closeFile(OsFile *id){
  OsTestFile *pFile = *id;
  if( pFile==pAllFiles ){
    pAllFiles = pFile->pNext;
  }else{
    OsTestFile *p;
    for(p=pAllFiles; p->pNext!=pFile; p=p->pNext ){
      assert( p );
    }
    p->pNext = pFile->pNext;
  }
  sqliteFree(pFile);
  *id = 0;
}

/*
** Return the current seek offset from the start of the file. This
** is unix-only code.
*/
static i64 osTell(OsTestFile *pFile){
  return lseek(pFile->fd.h, 0, SEEK_CUR);
}

/*
** Load block 'blk' into the cache of pFile.
*/
static int cacheBlock(OsTestFile *pFile, int blk){
  if( blk>=pFile->nBlk ){
    int n = ((pFile->nBlk * 2) + 100 + blk);
    /* if( pFile->nBlk==0 ){ printf("DIRTY %s\n", pFile->zName); } */
    pFile->apBlk = (u8 **)sqliteRealloc(pFile->apBlk, n * sizeof(u8*));
    if( !pFile->apBlk ) return SQLITE_NOMEM;
    memset(&pFile->apBlk[pFile->nBlk], 0, (n - pFile->nBlk)*sizeof(u8*));
    pFile->nBlk = n;
  }

  if( !pFile->apBlk[blk] ){
    i64 filesize;
    int rc;

    u8 *p = sqliteMalloc(BLOCKSIZE);
    if( !p ) return SQLITE_NOMEM;
    pFile->apBlk[blk] = p;

    rc = sqlite3RealFileSize(&pFile->fd, &filesize);
    if( rc!=SQLITE_OK ) return rc;

    if( BLOCK_OFFSET(blk)<filesize ){
      int len = BLOCKSIZE;
      rc = sqlite3RealSeek(&pFile->fd, blk*BLOCKSIZE);
      if( BLOCK_OFFSET(blk+1)>filesize ){
        len = filesize - BLOCK_OFFSET(blk);
      }
      if( rc!=SQLITE_OK ) return rc;
      rc = sqlite3RealRead(&pFile->fd, p, len);
      if( rc!=SQLITE_OK ) return rc;
    }
  }

  return SQLITE_OK;
}

/* #define TRACE_WRITECACHE */

/*
** Write the cache of pFile to disk. If crash is non-zero, randomly
** skip blocks when writing. The cache is deleted before returning.
*/
static int writeCache2(OsTestFile *pFile, int crash){
  int i;
  int nMax = pFile->nMaxWrite;
  i64 offset;
  int rc = SQLITE_OK;

  offset = osTell(pFile);
  for(i=0; i<pFile->nBlk; i++){
    u8 *p = pFile->apBlk[i];
    if( p ){
      int skip = 0;
      int trash = 0;
      if( crash ){
        char random;
        sqlite3Randomness(1, &random);
        if( random & 0x01 ){
          if( random & 0x02 ){
            trash = 1;
#ifdef TRACE_WRITECACHE
printf("Trashing block %d of %s\n", i, pFile->zName); 
#endif
          }else{
            skip = 1;
#ifdef TRACE_WRITECACHE
printf("Skiping block %d of %s\n", i, pFile->zName); 
#endif
          }
        }else{
#ifdef TRACE_WRITECACHE
printf("Writing block %d of %s\n", i, pFile->zName); 
#endif
        }
      }
      if( rc==SQLITE_OK ){
        rc = sqlite3RealSeek(&pFile->fd, BLOCK_OFFSET(i));
      }
      if( rc==SQLITE_OK && !skip ){
        int len = BLOCKSIZE;
        if( BLOCK_OFFSET(i+1)>nMax ){
          len = nMax-BLOCK_OFFSET(i);
        }
        if( len>0 ){
          if( trash ){
            sqlite3Randomness(len, p);
          }
          rc = sqlite3RealWrite(&pFile->fd, p, len);
        }
      }
      sqliteFree(p);
    }
  }
  sqliteFree(pFile->apBlk);
  pFile->nBlk = 0;
  pFile->apBlk = 0;
  pFile->nMaxWrite = 0;

  if( rc==SQLITE_OK ){
    rc = sqlite3RealSeek(&pFile->fd, offset);
  }
  return rc;
}

/*
** Write the cache to disk.
*/
static int writeCache(OsTestFile *pFile){
  if( pFile->apBlk ){
    int c = crashRequired(pFile->zName);
    if( c ){
      OsTestFile *p;
#ifdef TRACE_WRITECACHE
      printf("\nCrash during sync of %s\n", pFile->zName);
#endif
      for(p=pAllFiles; p; p=p->pNext){
        writeCache2(p, 1);
      }
      exit(-1);
    }else{
      return writeCache2(pFile, 0);
    }
  }
  return SQLITE_OK;
}

/*
** Close the file.
*/
int sqlite3OsClose(OsFile *id){
  if( !(*id) ) return SQLITE_OK;
  if( (*id)->fd.isOpen ){
    /* printf("CLOSE %s (%d blocks)\n", (*id)->zName, (*id)->nBlk); */
    writeCache(*id);
    sqlite3RealClose(&(*id)->fd);
  }
  closeFile(id);
  return SQLITE_OK;
}

int sqlite3OsRead(OsFile *id, void *pBuf, int amt){
  i64 offset;       /* The current offset from the start of the file */
  i64 end;          /* The byte just past the last byte read */
  int blk;            /* Block number the read starts on */
  int i;
  u8 *zCsr;
  int rc = SQLITE_OK;
  OsTestFile *pFile = *id;

  offset = osTell(pFile);
  end = offset+amt;
  blk = (offset/BLOCKSIZE);

  zCsr = (u8 *)pBuf;
  for(i=blk; i*BLOCKSIZE<end; i++){
    int off = 0;
    int len = 0;


    if( BLOCK_OFFSET(i) < offset ){
      off = offset-BLOCK_OFFSET(i);
    }
    len = BLOCKSIZE - off;
    if( BLOCK_OFFSET(i+1) > end ){
      len = len - (BLOCK_OFFSET(i+1)-end);
    }

    if( i<pFile->nBlk && pFile->apBlk[i]){
      u8 *pBlk = pFile->apBlk[i];
      memcpy(zCsr, &pBlk[off], len);
    }else{
      rc = sqlite3RealSeek(&pFile->fd, BLOCK_OFFSET(i) + off);
      if( rc!=SQLITE_OK ) return rc;
      rc = sqlite3RealRead(&pFile->fd, zCsr, len);
      if( rc!=SQLITE_OK ) return rc;
    }

    zCsr += len;
  }
  assert( zCsr==&((u8 *)pBuf)[amt] );

  rc = sqlite3RealSeek(&pFile->fd, end);
  return rc;
}

int sqlite3OsWrite(OsFile *id, const void *pBuf, int amt){
  i64 offset;       /* The current offset from the start of the file */
  i64 end;          /* The byte just past the last byte written */
  int blk;            /* Block number the write starts on */
  int i;
  const u8 *zCsr;
  int rc = SQLITE_OK;
  OsTestFile *pFile = *id;

  offset = osTell(pFile);
  end = offset+amt;
  blk = (offset/BLOCKSIZE);

  zCsr = (u8 *)pBuf;
  for(i=blk; i*BLOCKSIZE<end; i++){
    u8 *pBlk;
    int off = 0;
    int len = 0;

    /* Make sure the block is in the cache */
    rc = cacheBlock(pFile, i);
    if( rc!=SQLITE_OK ) return rc;

    /* Write into the cache */
    pBlk = pFile->apBlk[i];
    assert( pBlk );

    if( BLOCK_OFFSET(i) < offset ){
      off = offset-BLOCK_OFFSET(i);
    }
    len = BLOCKSIZE - off;
    if( BLOCK_OFFSET(i+1) > end ){
      len = len - (BLOCK_OFFSET(i+1)-end);
    }
    memcpy(&pBlk[off], zCsr, len);
    zCsr += len;
  }
  if( pFile->nMaxWrite<end ){
    pFile->nMaxWrite = end;
  }
  assert( zCsr==&((u8 *)pBuf)[amt] );

  rc = sqlite3RealSeek(&pFile->fd, end);
  return rc;
}

/*
** Sync the file. First flush the write-cache to disk, then call the
** real sync() function.
*/
int sqlite3OsSync(OsFile *id, int dataOnly){
  int rc;
  /* printf("SYNC %s (%d blocks)\n", (*id)->zName, (*id)->nBlk); */
  rc = writeCache(*id);
  if( rc!=SQLITE_OK ) return rc;
  rc = sqlite3RealSync(&(*id)->fd, dataOnly);
  return rc;
}

/*
** Truncate the file. Set the internal OsFile.nMaxWrite variable to the new
** file size to ensure that nothing in the write-cache past this point
** is written to disk.
*/
int sqlite3OsTruncate(OsFile *id, i64 nByte){
  (*id)->nMaxWrite = nByte;
  return sqlite3RealTruncate(&(*id)->fd, nByte);
}

/*
** Return the size of the file. If the cache contains a write that extended
** the file, then return this size instead of the on-disk size.
*/
int sqlite3OsFileSize(OsFile *id, i64 *pSize){
  int rc = sqlite3RealFileSize(&(*id)->fd, pSize);
  if( rc==SQLITE_OK && pSize && *pSize<(*id)->nMaxWrite ){
    *pSize = (*id)->nMaxWrite;
  }
  return rc;
}

/*
** The three functions used to open files. All that is required is to
** initialise the os_test.c specific fields and then call the corresponding
** os_unix.c function to really open the file.
*/
int sqlite3OsOpenReadWrite(const char *zFilename, OsFile *id, int *pReadonly){
  initFile(id, zFilename);
  return sqlite3RealOpenReadWrite(zFilename, &(*id)->fd, pReadonly);
}
int sqlite3OsOpenExclusive(const char *zFilename, OsFile *id, int delFlag){
  initFile(id, zFilename);
  return sqlite3RealOpenExclusive(zFilename, &(*id)->fd, delFlag);
}
int sqlite3OsOpenReadOnly(const char *zFilename, OsFile *id){
  initFile(id, zFilename);
  return sqlite3RealOpenReadOnly(zFilename, &(*id)->fd);
}

/*
** These six function calls are passed straight through to the os_unix.c
** backend.
*/
int sqlite3OsSeek(OsFile *id, i64 offset){
  return sqlite3RealSeek(&(*id)->fd, offset);
}
int sqlite3OsCheckReservedLock(OsFile *id){
  return sqlite3RealCheckReservedLock(&(*id)->fd);
}
int sqlite3OsLock(OsFile *id, int locktype){
  return sqlite3RealLock(&(*id)->fd, locktype);
}
int sqlite3OsUnlock(OsFile *id, int locktype){
  return sqlite3RealUnlock(&(*id)->fd, locktype);
}
int sqlite3OsOpenDirectory(const char *zDirname, OsFile *id){
  return sqlite3RealOpenDirectory(zDirname, &(*id)->fd);
}

#endif /* OS_TEST */

/*
** 2004 May 22
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
*/
#ifndef _SQLITE_OS_TEST_H_
#define _SQLITE_OS_TEST_H_

#define OsFile OsRealFile
#define OS_UNIX 1
#include "os_unix.h"
#undef OS_UNIX
#undef OsFile
#undef SET_FULLSYNC

/* Include sqliteInt.h now to get the type u8. */
#include "sqliteInt.h"

typedef struct OsTestFile* OsFile;
typedef struct OsTestFile OsTestFile;
struct OsTestFile {
  u8 **apBlk;       /* Array of blocks that have been written to. */
  int nBlk;         /* Size of apBlock. */
  int nMaxWrite;    /* Largest offset written to. */
  char *zName;      /* File name */
  OsRealFile fd;
  OsTestFile *pNext;
};

void sqlite3SetCrashParams(int iDelay, char const *zFile);

#endif /* _SQLITE_OS_UNIX_H_ */

/*
** 2004 May 22
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** This header file defined OS-specific features for Unix.
*/
#ifndef _SQLITE_OS_UNIX_H_
#define _SQLITE_OS_UNIX_H_

/*
** Helpful hint:  To get this to compile on HP/UX, add -D_INCLUDE_POSIX_SOURCE
** to the compiler command line.
*/

/*
** These #defines should enable >2GB file support on Posix if the
** underlying operating system supports it.  If the OS lacks
** large file support, or if the OS is windows, these should be no-ops.
**
** Large file support can be disabled using the -DSQLITE_DISABLE_LFS switch
** on the compiler command line.  This is necessary if you are compiling
** on a recent machine (ex: RedHat 7.2) but you want your code to work
** on an older machine (ex: RedHat 6.0).  If you compile on RedHat 7.2
** without this option, LFS is enable.  But LFS does not exist in the kernel
** in RedHat 6.0, so the code won't work.  Hence, for maximum binary
** portability you should omit LFS.
**
** Similar is true for MacOS.  LFS is only supported on MacOS 9 and later.
*/
#ifndef SQLITE_DISABLE_LFS
# define _LARGE_FILE       1
# ifndef _FILE_OFFSET_BITS
#   define _FILE_OFFSET_BITS 64
# endif
# define _LARGEFILE_SOURCE 1
#endif

/*
** standard include files.
*/
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

/*
** Macros used to determine whether or not to use threads.  The
** SQLITE_UNIX_THREADS macro is defined if we are synchronizing for
** Posix threads and SQLITE_W32_THREADS is defined if we are
** synchronizing using Win32 threads.
*/
#if defined(THREADSAFE) && THREADSAFE
# include <pthread.h>
# define SQLITE_UNIX_THREADS 1
#endif

/*
** The OsFile structure is a operating-system independing representation
** of an open file handle.  It is defined differently for each architecture.
**
** This is the definition for Unix.
**
** OsFile.locktype takes one of the values SHARED_LOCK, RESERVED_LOCK,
** PENDING_LOCK or EXCLUSIVE_LOCK.
*/
typedef struct OsFile OsFile;
struct OsFile {
  struct Pager *pPager;     /* The pager that owns this OsFile.  Might be 0 */
  struct openCnt *pOpen;    /* Info about all open fd's on this inode */
  struct lockInfo *pLock;   /* Info about locks on this inode */
  int h;                    /* The file descriptor */
  unsigned char locktype;   /* The type of lock held on this fd */
  unsigned char isOpen;     /* True if needs to be closed */
  unsigned char fullSync;   /* Use F_FULLSYNC if available */
  int dirfd;                /* File descriptor for the directory */
#ifdef SQLITE_UNIX_THREADS
  pthread_t tid;            /* The thread authorized to use this OsFile */
#endif
};

/*
** A macro to set the OsFile.fullSync flag, if it exists.
*/
#define SET_FULLSYNC(x,y)  ((x).fullSync = (y))

/*
** Maximum number of characters in a temporary file name
*/
#define SQLITE_TEMPNAME_SIZE 200

/*
** Minimum interval supported by sqlite3OsSleep().
*/
#if defined(HAVE_USLEEP) && HAVE_USLEEP
# define SQLITE_MIN_SLEEP_MS 1
#else
# define SQLITE_MIN_SLEEP_MS 1000
#endif

/*
** Default permissions when creating a new file
*/
#ifndef SQLITE_DEFAULT_FILE_PERMISSIONS
# define SQLITE_DEFAULT_FILE_PERMISSIONS 0644
#endif


#endif /* _SQLITE_OS_UNIX_H_ */

/*
** 2004 May 22
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** This header file defines OS-specific features for Win32
*/
#ifndef _SQLITE_OS_WIN_H_
#define _SQLITE_OS_WIN_H_

#include <windows.h>
#include <winbase.h>

/*
** The OsFile structure is a operating-system independing representation
** of an open file handle.  It is defined differently for each architecture.
**
** This is the definition for Win32.
*/
typedef struct OsFile OsFile;
struct OsFile {
  HANDLE h;               /* Handle for accessing the file */
  unsigned char locktype; /* Type of lock currently held on this file */
  unsigned char isOpen;   /* True if needs to be closed */
  short sharedLockByte;   /* Randomly chosen byte used as a shared lock */
};


#define SQLITE_TEMPNAME_SIZE (MAX_PATH+50)
#define SQLITE_MIN_SLEEP_MS 1


#endif /* _SQLITE_OS_WIN_H_ */

** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.329 2007/04/16 15:02:19 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>

**
** If the second argument is SQLITE_IOERR, SQLITE_CORRUPT, or SQLITE_FULL
** the error becomes persistent. All subsequent API calls on this Pager
** will immediately return the same error code.
*/
static int pager_error(Pager *pPager, int rc){
  int rc2 = rc & 0xff;

  assert( pPager->errCode==SQLITE_FULL || pPager->errCode==SQLITE_OK );



  if(
    rc2==SQLITE_FULL ||
    rc2==SQLITE_IOERR ||
    rc2==SQLITE_CORRUPT
  ){
    pPager->errCode = rc;
  }

  }

  assert( pPager->state==PAGER_RESERVED || pPager->state>=PAGER_EXCLUSIVE );

  /* If the pager is in RESERVED state, then there must be a copy of this
  ** page in the pager cache. In this case just update the pager cache,
  ** not the database file. The page is left marked dirty in this case.




  **
  ** If in EXCLUSIVE state, then we update the pager cache if it exists
  ** and the main file. The page is then marked not dirty.
  **
  ** Ticket #1171:  The statement journal might contain page content that is
  ** different from the page content at the start of the transaction.
  ** This occurs when a page is changed prior to the start of a statement
  ** then changed again within the statement.  When rolling back such a
  ** statement we must not write to the original database unless we know
  ** for certain that original page contents are in the main rollback
  ** journal.  Otherwise, if a full ROLLBACK occurs after the statement

  ** rollback the full ROLLBACK will not restore the page to its original
  ** content.  Two conditions must be met before writing to the database
  ** files. (1) the database must be locked.  (2) we know that the original
  ** page content is in the main journal either because the page is not in
  ** cache or else it is marked as needSync==0.
  */
  pPg = pager_lookup(pPager, pgno);
  assert( pPager->state>=PAGER_EXCLUSIVE || pPg!=0 );
  PAGERTRACE3("PLAYBACK %d page %d\n", PAGERID(pPager), pgno);
  if( pPager->state>=PAGER_EXCLUSIVE && (pPg==0 || pPg->needSync==0) ){
    rc = sqlite3OsSeek(pPager->fd, (pgno-1)*(i64)pPager->pageSize);
    if( rc==SQLITE_OK ){
      rc = sqlite3OsWrite(pPager->fd, aData, pPager->pageSize);
    }
    if( pPg ){

    */
    if( nRec==0xffffffff ){
      assert( pPager->journalOff==JOURNAL_HDR_SZ(pPager) );
      nRec = (szJ - JOURNAL_HDR_SZ(pPager))/JOURNAL_PG_SZ(pPager);
    }

    /* If nRec is 0 and this rollback is of a transaction created by this

    ** process. In this case the rest of the journal file consists of
    ** journalled copies of pages that need to be read back into the cache.



    */
    if( nRec==0 && !isHot ){

      nRec = (szJ - pPager->journalOff) / JOURNAL_PG_SZ(pPager);
    }

    /* If this is the first header read from the journal, truncate the
    ** database file back to it's original size.
    */
    if( pPager->journalOff==JOURNAL_HDR_SZ(pPager) ){

        if( pPg==pPager->pAll ){
           pPager->pAll = pPg->pNextAll;
        }else{
          for( pTmp=pPager->pAll; pTmp->pNextAll!=pPg; pTmp=pTmp->pNextAll ){}
          pTmp->pNextAll = pPg->pNextAll;
        }
        nReleased += sqliteAllocSize(pPg);
        IOTRACE(("PGFREE %p %d\n", pPager, pPg->pgno));
        PAGER_INCR(sqlite3_pager_pgfree_count);
        sqliteFree(pPg);
      }

      if( rc!=SQLITE_OK ){
        /* An error occured whilst writing to the database file or 
        ** journal in pager_recycle(). The error is not returned to the 
        ** caller of this function. Instead, set the Pager.errCode variable.
        ** The error will be returned to the user (or users, in the case 
        ** of a shared pager cache) of the pager for which the error occured.
        */

        assert( (rc&0xff)==SQLITE_IOERR || rc==SQLITE_FULL );



        assert( pPager->state>=PAGER_RESERVED );
        pager_error(pPager, rc);
      }
    }
  }

  return nReleased;

  pPager->xCodec = xCodec;
  pPager->pCodecArg = pCodecArg;
}
#endif

#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** Move the page identified by pData to location pgno in the file. 
**
** There must be no references to the current page pgno. If current page


** pgno is not already in the rollback journal, it is not written there by
** by this routine. The same applies to the page pData refers to on entry to
** this routine.
**
** References to the page refered to by pData remain valid. Updating any
** meta-data associated with page pData (i.e. data stored in the nExtra bytes
** allocated along with the page) is the responsibility of the caller.
**
** A transaction must be active when this routine is called. It used to be
** required that a statement transaction was not active, but this restriction
** has been removed (CREATE INDEX needs to move a page when a statement
** transaction is active).
*/
int sqlite3PagerMovepage(Pager *pPager, DbPage *pPg, Pgno pgno){
  PgHdr *pPgOld; 
  int h;
  Pgno needSyncPgno = 0;

  assert( pPg->nRef>0 );

  PAGERTRACE5("MOVE %d page %d (needSync=%d) moves to %d\n", 
      PAGERID(pPager), pPg->pgno, pPg->needSync, pgno);

  unlinkHashChain(pPager, pPg);

  /* If the cache contains a page with page-number pgno, remove it
  ** from it's hash chain. Also, if the PgHdr.needSync was set for 
  ** page pgno before the 'move' operation, it needs to be retained 
  ** for the page moved there.
  */

  pPgOld = pager_lookup(pPager, pgno);
  if( pPgOld ){
    assert( pPgOld->nRef==0 );
    unlinkHashChain(pPager, pPgOld);
    makeClean(pPgOld);
    if( pPgOld->needSync ){
      assert( pPgOld->inJournal );
      pPg->inJournal = 1;
      pPg->needSync = 1;
      assert( pPager->needSync );
    }







  }

  /* Change the page number for pPg and insert it into the new hash-chain. */
  assert( pgno!=0 );
  pPg->pgno = pgno;
  h = pgno & (pPager->nHash-1);
  if( pPager->aHash[h] ){

/*
** 2006 January 07
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
******************************************************************************
**
** This file contains demonstration code.  Nothing in this file gets compiled
** or linked into the SQLite library unless you use a non-standard option:
**
**      -DSQLITE_SERVER=1
**
** The configure script will never generate a Makefile with the option
** above.  You will need to manually modify the Makefile if you want to
** include any of the code from this file in your project.  Or, at your
** option, you may copy and paste the code from this file and
** thereby avoiding a recompile of SQLite.
**
**
** This source file demonstrates how to use SQLite to create an SQL database 
** server thread in a multiple-threaded program.  One or more client threads
** send messages to the server thread and the server thread processes those
** messages in the order received and returns the results to the client.
**
** One might ask:  "Why bother?  Why not just let each thread connect
** to the database directly?"  There are a several of reasons to
** prefer the client/server approach.
**
**    (1)  Some systems (ex: Redhat9) have broken threading implementations
**         that prevent SQLite database connections from being used in
**         a thread different from the one where they were created.  With
**         the client/server approach, all database connections are created
**         and used within the server thread.  Client calls to the database
**         can be made from multiple threads (though not at the same time!)
**
**    (2)  Beginning with SQLite version 3.3.0, when two or more 
**         connections to the same database occur within the same thread,
**         they can optionally share their database cache.  This reduces
**         I/O and memory requirements.  Cache shared is controlled using
**         the sqlite3_enable_shared_cache() API.
**
**    (3)  Database connections on a shared cache use table-level locking
**         instead of file-level locking for improved concurrency.
**
**    (4)  Database connections on a shared cache can by optionally
**         set to READ UNCOMMITTED isolation.  (The default isolation for
**         SQLite is SERIALIZABLE.)  When this occurs, readers will
**         never be blocked by a writer and writers will not be
**         blocked by readers.  There can still only be a single writer
**         at a time, but multiple readers can simultaneously exist with
**         that writer.  This is a huge increase in concurrency.
**
** To summarize the rational for using a client/server approach: prior
** to SQLite version 3.3.0 it probably was not worth the trouble.  But
** with SQLite version 3.3.0 and beyond you can get significant performance
** and concurrency improvements and memory usage reductions by going
** client/server.
**
** Note:  The extra features of version 3.3.0 described by points (2)
** through (4) above are only available if you compile without the
** option -DSQLITE_OMIT_SHARED_CACHE. 
**
** Here is how the client/server approach works:  The database server
** thread is started on this procedure:
**
**       void *sqlite3_server(void *NotUsed);
**
** The sqlite_server procedure runs as long as the g.serverHalt variable
** is false.  A mutex is used to make sure no more than one server runs
** at a time.  The server waits for messages to arrive on a message
** queue and processes the messages in order.
**
** Two convenience routines are provided for starting and stopping the
** server thread:
**
**       void sqlite3_server_start(void);
**       void sqlite3_server_stop(void);
**
** Both of the convenience routines return immediately.  Neither will
** ever give an error.  If a server is already started or already halted,
** then the routines are effectively no-ops.
**
** Clients use the following interfaces:
**
**       sqlite3_client_open
**       sqlite3_client_prepare
**       sqlite3_client_step
**       sqlite3_client_reset
**       sqlite3_client_finalize
**       sqlite3_client_close
**
** These interfaces work exactly like the standard core SQLite interfaces
** having the same names without the "_client_" infix.  Many other SQLite
** interfaces can be used directly without having to send messages to the
** server as long as SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined.
** The following interfaces fall into this second category:
**
**       sqlite3_bind_*
**       sqlite3_changes
**       sqlite3_clear_bindings
**       sqlite3_column_*
**       sqlite3_complete
**       sqlite3_create_collation
**       sqlite3_create_function
**       sqlite3_data_count
**       sqlite3_db_handle
**       sqlite3_errcode
**       sqlite3_errmsg
**       sqlite3_last_insert_rowid
**       sqlite3_total_changes
**       sqlite3_transfer_bindings
**
** A single SQLite connection (an sqlite3* object) or an SQLite statement
** (an sqlite3_stmt* object) should only be passed to a single interface
** function at a time.  The connections and statements can be passed from
** any thread to any of the functions listed in the second group above as
** long as the same connection is not in use by two threads at once and
** as long as SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined.  Additional
** information about the SQLITE_ENABLE_MEMORY_MANAGEMENT constraint is
** below.
**
** The busy handler for all database connections should remain turned
** off.  That means that any lock contention will cause the associated
** sqlite3_client_step() call to return immediately with an SQLITE_BUSY
** error code.  If a busy handler is enabled and lock contention occurs,
** then the entire server thread will block.  This will cause not only
** the requesting client to block but every other database client as
** well.  It is possible to enhance the code below so that lock
** contention will cause the message to be placed back on the top of
** the queue to be tried again later.  But such enhanced processing is
** not included here, in order to keep the example simple.
**
** This example code assumes the use of pthreads.  Pthreads
** implementations are available for windows.  (See, for example
** http://sourceware.org/pthreads-win32/announcement.html.)  Or, you
** can translate the locking and thread synchronization code to use
** windows primitives easily enough.  The details are left as an
** exercise to the reader.
**
**** Restrictions Associated With SQLITE_ENABLE_MEMORY_MANAGEMENT ****
**
** If you compile with SQLITE_ENABLE_MEMORY_MANAGEMENT defined, then
** SQLite includes code that tracks how much memory is being used by
** each thread.  These memory counts can become confused if memory
** is allocated by one thread and then freed by another.  For that
** reason, when SQLITE_ENABLE_MEMORY_MANAGEMENT is used, all operations
** that might allocate or free memory should be performanced in the same
** thread that originally created the database connection.  In that case,
** many of the operations that are listed above as safe to be performed
** in separate threads would need to be sent over to the server to be
** done there.  If SQLITE_ENABLE_MEMORY_MANAGEMENT is defined, then
** the following functions can be used safely from different threads
** without messing up the allocation counts:
**
**       sqlite3_bind_parameter_name
**       sqlite3_bind_parameter_index
**       sqlite3_changes
**       sqlite3_column_blob
**       sqlite3_column_count
**       sqlite3_complete
**       sqlite3_data_count
**       sqlite3_db_handle
**       sqlite3_errcode
**       sqlite3_errmsg
**       sqlite3_last_insert_rowid
**       sqlite3_total_changes
**
** The remaining functions are not thread-safe when memory management
** is enabled.  So one would have to define some new interface routines
** along the following lines:
**
**       sqlite3_client_bind_*
**       sqlite3_client_clear_bindings
**       sqlite3_client_column_*
**       sqlite3_client_create_collation
**       sqlite3_client_create_function
**       sqlite3_client_transfer_bindings
**
** The example code in this file is intended for use with memory
** management turned off.  So the implementation of these additional
** client interfaces is left as an exercise to the reader.
**
** It may seem surprising to the reader that the list of safe functions
** above does not include things like sqlite3_bind_int() or
** sqlite3_column_int().  But those routines might, in fact, allocate
** or deallocate memory.  In the case of sqlite3_bind_int(), if the
** parameter was previously bound to a string that string might need
** to be deallocated before the new integer value is inserted.  In
** the case of sqlite3_column_int(), the value of the column might be
** a UTF-16 string which will need to be converted to UTF-8 then into
** an integer.
*/

/*
** Only compile the code in this file on UNIX with a THREADSAFE build
** and only if the SQLITE_SERVER macro is defined.
*/
#ifdef SQLITE_SERVER
#if defined(OS_UNIX) && OS_UNIX && defined(THREADSAFE) && THREADSAFE

/*
** We require only pthreads and the public interface of SQLite.
*/
#include <pthread.h>
#include "sqlite3.h"

/*
** Messages are passed from client to server and back again as 
** instances of the following structure.
*/
typedef struct SqlMessage SqlMessage;
struct SqlMessage {
  int op;                      /* Opcode for the message */
  sqlite3 *pDb;                /* The SQLite connection */
  sqlite3_stmt *pStmt;         /* A specific statement */
  int errCode;                 /* Error code returned */
  const char *zIn;             /* Input filename or SQL statement */
  int nByte;                   /* Size of the zIn parameter for prepare() */
  const char *zOut;            /* Tail of the SQL statement */
  SqlMessage *pNext;           /* Next message in the queue */
  SqlMessage *pPrev;           /* Previous message in the queue */
  pthread_mutex_t clientMutex; /* Hold this mutex to access the message */
  pthread_cond_t clientWakeup; /* Signal to wake up the client */
};

/*
** Legal values for SqlMessage.op
*/
#define MSG_Open       1  /* sqlite3_open(zIn, &pDb) */
#define MSG_Prepare    2  /* sqlite3_prepare(pDb, zIn, nByte, &pStmt, &zOut) */
#define MSG_Step       3  /* sqlite3_step(pStmt) */
#define MSG_Reset      4  /* sqlite3_reset(pStmt) */
#define MSG_Finalize   5  /* sqlite3_finalize(pStmt) */
#define MSG_Close      6  /* sqlite3_close(pDb) */
#define MSG_Done       7  /* Server has finished with this message */


/*
** State information about the server is stored in a static variable
** named "g" as follows:
*/
static struct ServerState {
  pthread_mutex_t queueMutex;   /* Hold this mutex to access the msg queue */
  pthread_mutex_t serverMutex;  /* Held by the server while it is running */
  pthread_cond_t serverWakeup;  /* Signal this condvar to wake up the server */
  volatile int serverHalt;      /* Server halts itself when true */
  SqlMessage *pQueueHead;       /* Head of the message queue */
  SqlMessage *pQueueTail;       /* Tail of the message queue */
} g = {
  PTHREAD_MUTEX_INITIALIZER,
  PTHREAD_MUTEX_INITIALIZER,
  PTHREAD_COND_INITIALIZER,
};

/*
** Send a message to the server.  Block until we get a reply.
**
** The mutex and condition variable in the message are uninitialized
** when this routine is called.  This routine takes care of 
** initializing them and destroying them when it has finished.
*/
static void sendToServer(SqlMessage *pMsg){
  /* Initialize the mutex and condition variable on the message
  */
  pthread_mutex_init(&pMsg->clientMutex, 0);
  pthread_cond_init(&pMsg->clientWakeup, 0);

  /* Add the message to the head of the server's message queue.
  */
  pthread_mutex_lock(&g.queueMutex);
  pMsg->pNext = g.pQueueHead;
  if( g.pQueueHead==0 ){
    g.pQueueTail = pMsg;
  }else{
    g.pQueueHead->pPrev = pMsg;
  }
  pMsg->pPrev = 0;
  g.pQueueHead = pMsg;
  pthread_mutex_unlock(&g.queueMutex);

  /* Signal the server that the new message has be queued, then
  ** block waiting for the server to process the message.
  */
  pthread_mutex_lock(&pMsg->clientMutex);
  pthread_cond_signal(&g.serverWakeup);
  while( pMsg->op!=MSG_Done ){
    pthread_cond_wait(&pMsg->clientWakeup, &pMsg->clientMutex);
  }
  pthread_mutex_unlock(&pMsg->clientMutex);

  /* Destroy the mutex and condition variable of the message.
  */
  pthread_mutex_destroy(&pMsg->clientMutex);
  pthread_cond_destroy(&pMsg->clientWakeup);
}

/*
** The following 6 routines are client-side implementations of the
** core SQLite interfaces:
**
**        sqlite3_open
**        sqlite3_prepare
**        sqlite3_step
**        sqlite3_reset
**        sqlite3_finalize
**        sqlite3_close
**
** Clients should use the following client-side routines instead of 
** the core routines above.
**
**        sqlite3_client_open
**        sqlite3_client_prepare
**        sqlite3_client_step
**        sqlite3_client_reset
**        sqlite3_client_finalize
**        sqlite3_client_close
**
** Each of these routines creates a message for the desired operation,
** sends that message to the server, waits for the server to process
** then message and return a response.
*/
int sqlite3_client_open(const char *zDatabaseName, sqlite3 **ppDb){
  SqlMessage msg;
  msg.op = MSG_Open;
  msg.zIn = zDatabaseName;
  sendToServer(&msg);
  *ppDb = msg.pDb;
  return msg.errCode;
}
int sqlite3_client_prepare(
  sqlite3 *pDb,
  const char *zSql,
  int nByte,
  sqlite3_stmt **ppStmt,
  const char **pzTail
){
  SqlMessage msg;
  msg.op = MSG_Prepare;
  msg.pDb = pDb;
  msg.zIn = zSql;
  msg.nByte = nByte;
  sendToServer(&msg);
  *ppStmt = msg.pStmt;
  if( pzTail ) *pzTail = msg.zOut;
  return msg.errCode;
}
int sqlite3_client_step(sqlite3_stmt *pStmt){
  SqlMessage msg;
  msg.op = MSG_Step;
  msg.pStmt = pStmt;
  sendToServer(&msg);
  return msg.errCode;
}
int sqlite3_client_reset(sqlite3_stmt *pStmt){
  SqlMessage msg;
  msg.op = MSG_Reset;
  msg.pStmt = pStmt;
  sendToServer(&msg);
  return msg.errCode;
}
int sqlite3_client_finalize(sqlite3_stmt *pStmt){
  SqlMessage msg;
  msg.op = MSG_Finalize;
  msg.pStmt = pStmt;
  sendToServer(&msg);
  return msg.errCode;
}
int sqlite3_client_close(sqlite3 *pDb){
  SqlMessage msg;
  msg.op = MSG_Close;
  msg.pDb = pDb;
  sendToServer(&msg);
  return msg.errCode;
}

/*
** This routine implements the server.  To start the server, first
** make sure g.serverHalt is false, then create a new detached thread
** on this procedure.  See the sqlite3_server_start() routine below
** for an example.  This procedure loops until g.serverHalt becomes
** true.
*/
void *sqlite3_server(void *NotUsed){
  sqlite3_enable_shared_cache(1);
  if( pthread_mutex_trylock(&g.serverMutex) ){
    sqlite3_enable_shared_cache(0);
    return 0;  /* Another server is already running */
  }
  while( !g.serverHalt ){
    SqlMessage *pMsg;

    /* Remove the last message from the message queue.
    */
    pthread_mutex_lock(&g.queueMutex);
    while( g.pQueueTail==0 && g.serverHalt==0 ){
      pthread_cond_wait(&g.serverWakeup, &g.queueMutex);
    }
    pMsg = g.pQueueTail;
    if( pMsg ){
      if( pMsg->pPrev ){
        pMsg->pPrev->pNext = 0;
      }else{
        g.pQueueHead = 0;
      }
      g.pQueueTail = pMsg->pPrev;
    }
    pthread_mutex_unlock(&g.queueMutex);
    if( pMsg==0 ) break;

    /* Process the message just removed
    */
    pthread_mutex_lock(&pMsg->clientMutex);
    switch( pMsg->op ){
      case MSG_Open: {
        pMsg->errCode = sqlite3_open(pMsg->zIn, &pMsg->pDb);
        break;
      }
      case MSG_Prepare: {
        pMsg->errCode = sqlite3_prepare(pMsg->pDb, pMsg->zIn, pMsg->nByte,
                                        &pMsg->pStmt, &pMsg->zOut);
        break;
      }
      case MSG_Step: {
        pMsg->errCode = sqlite3_step(pMsg->pStmt);
        break;
      }
      case MSG_Reset: {
        pMsg->errCode = sqlite3_reset(pMsg->pStmt);
        break;
      }
      case MSG_Finalize: {
        pMsg->errCode = sqlite3_finalize(pMsg->pStmt);
        break;
      }
      case MSG_Close: {
        pMsg->errCode = sqlite3_close(pMsg->pDb);
        break;
      }
    }

    /* Signal the client that the message has been processed.
    */
    pMsg->op = MSG_Done;
    pthread_mutex_unlock(&pMsg->clientMutex);
    pthread_cond_signal(&pMsg->clientWakeup);
  }
  pthread_mutex_unlock(&g.serverMutex);
  sqlite3_thread_cleanup();
  return 0;
}

/*
** Start a server thread if one is not already running.  If there
** is aleady a server thread running, the new thread will quickly
** die and this routine is effectively a no-op.
*/
void sqlite3_server_start(void){
  pthread_t x;
  int rc;
  g.serverHalt = 0;
  rc = pthread_create(&x, 0, sqlite3_server, 0);
  if( rc==0 ){
    pthread_detach(x);
  }
}

/*
** If a server thread is running, then stop it.  If no server is
** running, this routine is effectively a no-op.
**
** This routine returns immediately without waiting for the server
** thread to stop.  But be assured that the server will eventually stop.
*/
void sqlite3_server_stop(void){
  g.serverHalt = 1;
  pthread_cond_broadcast(&g.serverWakeup);
}

#endif /* defined(OS_UNIX) && OS_UNIX && defined(THREADSAFE) && THREADSAFE */
#endif /* defined(SQLITE_SERVER) */

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing the ATTACH and DETACH commands
# and related functionality.
#
# $Id: attach2.test,v 1.35 2006/01/03 00:33:50 drh Exp $
#

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

# Ticket #354
#

  catchsql {
    INSERT INTO t1 VALUES(1, 2)
  } db2 
} {1 {database is locked}}

lock_status 4.4.1 db {main shared temp closed file2 unlocked}
lock_status 4.4.2 db2 {main unlocked temp closed file2 unlocked}










do_test attach2-4.5 {
  # Handle 'db2' reserves file2.
  execsql {BEGIN} db2
  execsql {INSERT INTO file2.t1 VALUES(1, 2)} db2
  # Lock status:
  #    db  - shared(main)

do_test attach2-4.15 {
  execsql {SELECT * FROM t1} db2
} {1 2 1 2}

db close
db2 close
file delete -force test2.db


# These tests - attach2-5.* - check that the master journal file is deleted
# correctly when a multi-file transaction is committed or rolled back.
#
# Update: It's not actually created if a rollback occurs, so that test
# doesn't really prove too much.
foreach f [glob test.db*] {file delete -force $f}

#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script testing the callback-free C/C++ API and in
# particular the behavior of sqlite3_step() when trying to commit
# with lock contention.
#
# $Id: capi3b.test,v 1.3 2006/01/03 00:33:50 drh Exp $
#

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










set DB [sqlite3_connection_pointer db]
sqlite3 db2 test.db
set DB2 [sqlite3_connection_pointer db2]

# Create some data in the database
#

do_test capi3b-2.12 {
  sqlite3_finalize $VM1
  sqlite3_finalize $VM2
  execsql {SELECT * FROM t1}
} {1 2 3 4}

catch {db2 close}


finish_test

/*
** This program tests the ability of SQLite database to recover from a crash.
** This program runs under Unix only, but the results are applicable to all
** systems.
**
** The main process first constructs a test database, then starts creating
** subprocesses that write to that database.  Each subprocess is killed off,
** without a chance to clean up its database connection, after a random
** delay.  This killing of the subprocesses simulates a crash or power
** failure.  The next subprocess to open the database should rollback
** whatever operation was in process at the time of the simulated crash.
**
** If any problems are encountered, an error is reported and the test stops.
** If no problems are seen after a large number of tests, we assume that
** the rollback mechanism is working.
*/
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <signal.h>
#include <stdlib.h>
#include <string.h>
#include <sched.h>
#include "sqlite.h"

static void do_some_sql(int parent){
  char *zErr;
  int rc = SQLITE_OK;
  sqlite *db;
  int cnt = 0;
  static char zBig[] = 
    "-abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "-abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

  if( access("./test.db-journal",0)==0 ){
    /*printf("pid %d: journal exists.  rollback will be required\n",getpid());*/    unlink("test.db-saved");
    system("cp test.db test.db-saved");
    unlink("test.db-journal-saved");
    system("cp test.db-journal test.db-journal-saved");
  }
  db = sqlite_open("./test.db", 0, &zErr);
  if( db==0 ){
    printf("ERROR: %s\n", zErr);
    if( strcmp(zErr,"database disk image is malformed")==0 ){
      kill(parent, SIGKILL);
    }
    exit(1);
  }
  srand(getpid());
  while( rc==SQLITE_OK ){
    cnt++;
    rc = sqlite_exec_printf(db, 
       "INSERT INTO t1 VALUES(%d,'%d%s')", 0, 0, &zErr,
       rand(), rand(), zBig);
  }
  if( rc!=SQLITE_OK ){
    printf("ERROR #%d: %s\n", rc, zErr);
    if( rc==SQLITE_CORRUPT ){
      kill(parent, SIGKILL);
    }
  }
  printf("pid %d: cnt=%d\n", getpid(), cnt);
}


int main(int argc, char **argv){
  int i;
  sqlite *db;
  char *zErr;
  int status;
  int parent = getpid();

  unlink("test.db");
  unlink("test.db-journal");
  db = sqlite_open("test.db", 0, &zErr);
  if( db==0 ){
    printf("Cannot initialize: %s\n", zErr);
    return 1;
  }
  sqlite_exec(db, "CREATE TABLE t1(a,b)", 0, 0, 0);
  sqlite_close(db);
  for(i=0; i<10000; i++){
    int pid = fork();
    if( pid==0 ){
      sched_yield();
      do_some_sql(parent);
      return 0;
    }
    printf("test %d, pid=%d\n", i, pid);
    usleep(rand()%10000 + 1000);
    kill(pid, SIGKILL);
    waitpid(pid, &status, 0);
  }
  return 0;
}

# 2001 September 15
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements some common TCL routines used for regression
# testing the SQLite library
#
# $Id: tester.tcl,v 1.79 2007/04/19 12:30:54 drh Exp $

# Make sure tclsqlite3 was compiled correctly.  Abort now with an
# error message if not.
#
if {[sqlite3 -tcl-uses-utf]} {
  if {"\u1234"=="u1234"} {
    puts stderr "***** BUILD PROBLEM *****"

    exit 1
  }
}

set tcl_precision 15
set sqlite_pending_byte 0x0010000





















# Use the pager codec if it is available
#
if {[sqlite3 -has-codec] && [info command sqlite_orig]==""} {
  rename sqlite3 sqlite_orig
  proc sqlite3 {args} {
    if {[llength $args]==2 && [string index [lindex $args 0] 0]!="-"} {
      lappend args -key {xyzzy}

  catch {
    pp_check_for_leaks
  }
  sqlite3 db {}
  # sqlite3_clear_tsd_memdebug
  db close








  if {$::sqlite3_tsd_count} {
     puts "Thread-specific data leak: $::sqlite3_tsd_count instances"
     incr nErr
  } else {
     puts "Thread-specific data deallocated properly"
  }
  incr nTest

set rcsid {$Id: capi3ref.tcl,v 1.55 2007/04/16 15:35:24 drh Exp $}
source common.tcl
header {C/C++ Interface For SQLite Version 3}
puts {
<h2 class=pdf_section>C/C++ Interface For SQLite Version 3</h2>
}

proc api {name prototype desc {notused x}} {
  global apilist specialname
  if {$name==""} {
    regsub -all {sqlite3_[a-z0-9_]+\(} $prototype \
      {[lappend name [string trimright & (]]} x1
    subst $x1
  } else {
    lappend specialname $name
  }
  lappend apilist [list $name $prototype $desc]
}

api {extended-result-codes} {
#define SQLITE_IOERR_READ       
#define SQLITE_IOERR_SHORT_READ 
#define SQLITE_IOERR_WRITE      
#define SQLITE_IOERR_FSYNC      
#define SQLITE_IOERR_DIR_FSYNC  
#define SQLITE_IOERR_TRUNCATE   
#define SQLITE_IOERR_FSTAT      
#define SQLITE_IOERR_UNLOCK     
#define SQLITE_IOERR_RDLOCK     
...
} {
In its default configuration, SQLite API routines return one of 26 integer
result codes described at result-codes.  However, experience has shown that
many of these result codes are too course-grained.  They do not provide as
much information about problems as users might like.  In an effort to
address this, newer versions of SQLite (version 3.3.8 and later) include
support for additional result codes that provide more detailed information
about errors.  The extended result codes are enabled (or disabled) for 
each database
connection using the sqlite3_extended_result_codes() API.

Some of the available extended result codes are listed above.
We expect the number of extended result codes will be expand
over time.  Software that uses extended result codes should expect
to see new result codes in future releases of SQLite.

The symbolic name for an extended result code always contains a related
primary result code as a prefix.  Primary result codes contain a single
"_" character.  Extended result codes contain two or more "_" characters.
The numeric value of an extended result code can be converted to its
corresponding primary result code by masking off the lower 8 bytes.

A complete list of available extended result codes and
details about the meaning of the various extended result codes can be
found by consulting the C code, especially the sqlite3.h header
file and its antecedent sqlite.h.in.  Additional information
is also available at the SQLite wiki:
http://www.sqlite.org/cvstrac/wiki?p=ExtendedResultCodes
}


api {result-codes} {
#define SQLITE_OK           0   /* Successful result */
#define SQLITE_ERROR        1   /* SQL error or missing database */
#define SQLITE_INTERNAL     2   /* An internal logic error in SQLite */
#define SQLITE_PERM         3   /* Access permission denied */
#define SQLITE_ABORT        4   /* Callback routine requested an abort */
#define SQLITE_BUSY         5   /* The database file is locked */
#define SQLITE_LOCKED       6   /* A table in the database is locked */
#define SQLITE_NOMEM        7   /* A malloc() failed */
#define SQLITE_READONLY     8   /* Attempt to write a readonly database */
#define SQLITE_INTERRUPT    9   /* Operation terminated by sqlite_interrupt() */
#define SQLITE_IOERR       10   /* Some kind of disk I/O error occurred */
#define SQLITE_CORRUPT     11   /* The database disk image is malformed */
#define SQLITE_NOTFOUND    12   /* (Internal Only) Table or record not found */
#define SQLITE_FULL        13   /* Insertion failed because database is full */
#define SQLITE_CANTOPEN    14   /* Unable to open the database file */
#define SQLITE_PROTOCOL    15   /* Database lock protocol error */
#define SQLITE_EMPTY       16   /* (Internal Only) Database table is empty */
#define SQLITE_SCHEMA      17   /* The database schema changed */
#define SQLITE_TOOBIG      18   /* Too much data for one row of a table */
#define SQLITE_CONSTRAINT  19   /* Abort due to constraint violation */
#define SQLITE_MISMATCH    20   /* Data type mismatch */
#define SQLITE_MISUSE      21   /* Library used incorrectly */
#define SQLITE_NOLFS       22   /* Uses OS features not supported on host */
#define SQLITE_AUTH        23   /* Authorization denied */
#define SQLITE_ROW         100  /* sqlite_step() has another row ready */
#define SQLITE_DONE        101  /* sqlite_step() has finished executing */
} {
Many SQLite functions return an integer result code from the set shown
above in order to indicates success or failure.

The result codes above are the only ones returned by SQLite in its
default configuration.  However, the sqlite3_extended_result_codes()
API can be used to set a database connectoin to return more detailed
result codes.  See the documentation on sqlite3_extended_result_codes()
or extended-result-codes for additional information.
}

api {} {
  int sqlite3_extended_result_codes(sqlite3*, int onoff);
} {
This routine enables or disabled extended-result-codes feature.
By default, SQLite API routines return one of only 26 integer
result codes described at result-codes.  When extended result codes
are enabled by this routine, the repetoire of result codes can be
much larger and can (hopefully) provide more detailed information
about the cause of an error.

The second argument is a boolean value that turns extended result
codes on and off.  Extended result codes are off by default for
backwards compatibility with older versions of SQLite.
}

api {} {
  const char *sqlite3_libversion(void);
} {
  Return a pointer to a string which contains the version number of
  the library.  The same string is available in the global
  variable named "sqlite3_version".  This interface is provided since
  windows is unable to access global variables in DLLs.
}

api {} {
  void *sqlite3_aggregate_context(sqlite3_context*, int nBytes);
} {
  Aggregate functions use this routine to allocate
  a structure for storing their state.  The first time this routine
  is called for a particular aggregate, a new structure of size nBytes
  is allocated, zeroed, and returned.  On subsequent calls (for the
  same aggregate instance) the same buffer is returned.  The implementation
  of the aggregate can use the returned buffer to accumulate data.

  The buffer is freed automatically by SQLite when the query that
  invoked the aggregate function terminates.
}

api {} {
  int sqlite3_aggregate_count(sqlite3_context*);
} {
  This function is deprecated.   It continues to exist so as not to
  break any legacy code that might happen to use it.  But it should not
  be used in any new code.

  In order to encourage people to not use this function, we are not going
  to tell you what it does.
}

api {} {
  int sqlite3_bind_blob(sqlite3_stmt*, int, const void*, int n, void(*)(void*));
  int sqlite3_bind_double(sqlite3_stmt*, int, double);
  int sqlite3_bind_int(sqlite3_stmt*, int, int);
  int sqlite3_bind_int64(sqlite3_stmt*, int, long long int);
  int sqlite3_bind_null(sqlite3_stmt*, int);
  int sqlite3_bind_text(sqlite3_stmt*, int, const char*, int n, void(*)(void*));
  int sqlite3_bind_text16(sqlite3_stmt*, int, const void*, int n, void(*)(void*));
  #define SQLITE_STATIC      ((void(*)(void *))0)
  #define SQLITE_TRANSIENT   ((void(*)(void *))-1)
} {
 In the SQL strings input to sqlite3_prepare_v2() and sqlite3_prepare16_v2(),
 one or more literals can be replace by a parameter "?" or ":AAA" or 
 "@AAA" or "\$VVV"
 where AAA is an alphanumeric identifier and VVV is a variable name according
 to the syntax rules of the TCL programming language.
 The values of these parameters (also called "host parameter names")
 can be set using the sqlite3_bind_*() routines.

 The first argument to the sqlite3_bind_*() routines always is a pointer
 to the sqlite3_stmt structure returned from sqlite3_prepare_v2().  The second
 argument is the index of the parameter to be set.  The first parameter has
 an index of 1. When the same named parameter is used more than once, second
 and subsequent
 occurrences have the same index as the first occurrence.  The index for
 named parameters can be looked up using the
 sqlite3_bind_parameter_name() API if desired.

 The third argument is the value to bind to the parameter.

 In those
 routines that have a fourth argument, its value is the number of bytes
 in the parameter.  To be clear: the value is the number of bytes in the
 string, not the number of characters.  The number
 of bytes does not include the zero-terminator at the end of strings.
 If the fourth parameter is negative, the length of the string is
 number of bytes up to the first zero terminator.

 The fifth argument to sqlite3_bind_blob(), sqlite3_bind_text(), and
 sqlite3_bind_text16() is a destructor used to dispose of the BLOB or
 text after SQLite has finished with it.  If the fifth argument is the
 special value SQLITE_STATIC, then the library assumes that the information
 is in static, unmanaged space and does not need to be freed.  If the
 fifth argument has the value SQLITE_TRANSIENT, then SQLite makes its
 own private copy of the data immediately, before the sqlite3_bind_*()
 routine returns.

 The sqlite3_bind_*() routines must be called after
 sqlite3_prepare_v2() or sqlite3_reset() and before sqlite3_step().
 Bindings are not cleared by the sqlite3_reset() routine.
 Unbound parameters are interpreted as NULL.

 These routines return SQLITE_OK on success or an error code if
 anything goes wrong.  SQLITE_RANGE is returned if the parameter
 index is out of range.  SQLITE_NOMEM is returned if malloc fails.
 SQLITE_MISUSE is returned if these routines are called on a virtual
 machine that is the wrong state or which has already been finalized.
}

api {} {
  int sqlite3_bind_parameter_count(sqlite3_stmt*);
} {
  Return the number of parameters in the precompiled statement given as
  the argument.
}

api {} {
  const char *sqlite3_bind_parameter_name(sqlite3_stmt*, int n);
} {
  Return the name of the n-th parameter in the precompiled statement.
  Parameters of the form ":AAA" or "@AAA" or "\$VVV" have a name which is the
  string ":AAA" or "\$VVV".  In other words, the initial ":" or "$" or "@"
  is included as part of the name.
  Parameters of the form "?" have no name.

  The first bound parameter has an index of 1, not 0.

  If the value n is out of range or if the n-th parameter is nameless,
  then NULL is returned.  The returned string is always in the
  UTF-8 encoding.
}

api {} {
  int sqlite3_bind_parameter_index(sqlite3_stmt*, const char *zName);
} {
  Return the index of the parameter with the given name.
  The name must match exactly.
  If there is no parameter with the given name, return 0.
  The string zName is always in the UTF-8 encoding.
}

api {} {
  int sqlite3_busy_handler(sqlite3*, int(*)(void*,int), void*);
} {
 This routine identifies a callback function that might be invoked
 whenever an attempt is made to open a database table 
 that another thread or process has locked.
 If the busy callback is NULL, then SQLITE_BUSY is returned immediately
 upon encountering the lock.
 If the busy callback is not NULL, then the
 callback will be invoked with two arguments.  The
 first argument to the handler is a copy of the void* pointer which
 is the third argument to this routine.  The second argument to
 the handler is the number of times that the busy handler has
 been invoked for this locking event. If the
 busy callback returns 0, then no additional attempts are made to
 access the database and SQLITE_BUSY is returned.
 If the callback returns non-zero, then another attempt is made to open the
 database for reading and the cycle repeats.

 The presence of a busy handler does not guarantee that
 it will be invoked when there is lock contention.
 If SQLite determines that invoking the busy handler could result in
 a deadlock, it will return SQLITE_BUSY instead.
 Consider a scenario where one process is holding a read lock that
 it is trying to promote to a reserved lock and
 a second process is holding a reserved lock that it is trying
 to promote to an exclusive lock.  The first process cannot proceed
 because it is blocked by the second and the second process cannot
 proceed because it is blocked by the first.  If both processes
 invoke the busy handlers, neither will make any progress.  Therefore,
 SQLite returns SQLITE_BUSY for the first process, hoping that this
 will induce the first process to release its read lock and allow
 the second process to proceed.

 The default busy callback is NULL.

 Sqlite is re-entrant, so the busy handler may start a new query. 
 (It is not clear why anyone would every want to do this, but it
 is allowed, in theory.)  But the busy handler may not close the
 database.  Closing the database from a busy handler will delete 
 data structures out from under the executing query and will 
 probably result in a coredump.

 There can only be a single busy handler defined for each database
 connection.  Setting a new busy handler clears any previous one.
 Note that calling sqlite3_busy_timeout() will also set or clear
 the busy handler.
}

api {} {
  int sqlite3_busy_timeout(sqlite3*, int ms);
} {
 This routine sets a busy handler that sleeps for a while when a
 table is locked.  The handler will sleep multiple times until 
 at least "ms" milliseconds of sleeping have been done.  After
 "ms" milliseconds of sleeping, the handler returns 0 which
 causes sqlite3_exec() to return SQLITE_BUSY.

 Calling this routine with an argument less than or equal to zero
 turns off all busy handlers.

 There can only be a single busy handler for a particular database
 connection.  If another busy handler was defined  
 (using sqlite3_busy_handler()) prior to calling
 this routine, that other busy handler is cleared.
}

api {} {
  int sqlite3_changes(sqlite3*);
} {
 This function returns the number of database rows that were changed
 (or inserted or deleted) by the most recently completed
 INSERT, UPDATE, or DELETE
 statement.  Only changes that are directly specified by the INSERT,
 UPDATE, or DELETE statement are counted.  Auxiliary changes caused by
 triggers are not counted.  Use the sqlite3_total_changes() function
 to find the total number of changes including changes caused by triggers.

 Within the body of a trigger, the sqlite3_changes() function does work
 to report the number of rows that were changed for the most recently
 completed INSERT, UPDATE, or DELETE statement within the trigger body.

 SQLite implements the command "DELETE FROM table" without a WHERE clause
 by dropping and recreating the table.  (This is much faster than going
 through and deleting individual elements from the table.)  Because of
 this optimization, the change count for "DELETE FROM table" will be
 zero regardless of the number of elements that were originally in the
 table. To get an accurate count of the number of rows deleted, use
 "DELETE FROM table WHERE 1" instead.
}

api {} {
  int sqlite3_total_changes(sqlite3*);
} {
  This function returns the total number of database rows that have
  be modified, inserted, or deleted since the database connection was
  created using sqlite3_open().  All changes are counted, including
  changes by triggers and changes to TEMP and auxiliary databases.
  Except, changes to the SQLITE_MASTER table (caused by statements 
  such as CREATE TABLE) are not counted.  Nor are changes counted when
  an entire table is deleted using DROP TABLE.

  See also the sqlite3_changes() API.

  SQLite implements the command "DELETE FROM table" without a WHERE clause
  by dropping and recreating the table.  (This is much faster than going
  through and deleting individual elements form the table.)  Because of
  this optimization, the change count for "DELETE FROM table" will be
  zero regardless of the number of elements that were originally in the
  table. To get an accurate count of the number of rows deleted, use
  "DELETE FROM table WHERE 1" instead.
}

api {} {
  int sqlite3_close(sqlite3*);
} {
  Call this function with a pointer to a structure that was previously
  returned from sqlite3_open() or sqlite3_open16()
  and the corresponding database will by closed.

  SQLITE_OK is returned if the close is successful.  If there are
  prepared statements that have not been finalized, then SQLITE_BUSY
  is returned.  SQLITE_ERROR might be returned if the argument is not
  a valid connection pointer returned by sqlite3_open() or if the connection
  pointer has been closed previously.
}

api {} {
const void *sqlite3_column_blob(sqlite3_stmt*, int iCol);
int sqlite3_column_bytes(sqlite3_stmt*, int iCol);
int sqlite3_column_bytes16(sqlite3_stmt*, int iCol);
double sqlite3_column_double(sqlite3_stmt*, int iCol);
int sqlite3_column_int(sqlite3_stmt*, int iCol);
long long int sqlite3_column_int64(sqlite3_stmt*, int iCol);
const unsigned char *sqlite3_column_text(sqlite3_stmt*, int iCol);
const void *sqlite3_column_text16(sqlite3_stmt*, int iCol);
int sqlite3_column_type(sqlite3_stmt*, int iCol);
#define SQLITE_INTEGER  1
#define SQLITE_FLOAT    2
#define SQLITE_TEXT     3
#define SQLITE_BLOB     4
#define SQLITE_NULL     5
} {
 These routines return information about the information
 in a single column of the current result row of a query.  In every
 case the first argument is a pointer to the SQL statement that is being
 executed (the sqlite_stmt* that was returned from sqlite3_prepare_v2()) and
 the second argument is the index of the column for which information 
 should be returned.  iCol is zero-indexed.  The left-most column has an
 index of 0.

 If the SQL statement is not currently point to a valid row, or if the
 the column index is out of range, the result is undefined.

 If the result is a BLOB then the sqlite3_column_bytes() routine returns
 the number of bytes in that BLOB.  No type conversions occur.
 If the result is a string (or a number since a number can be converted
 into a string) then sqlite3_column_bytes() converts
 the value into a UTF-8 string and returns
 the number of bytes in the resulting string.  The value returned does
 not include the \\000 terminator at the end of the string.  The
 sqlite3_column_bytes16() routine converts the value into a UTF-16
 encoding and returns the number of bytes (not characters) in the
 resulting string.  The \\u0000 terminator is not included in this count.

 These routines attempt to convert the value where appropriate.  For
 example, if the internal representation is FLOAT and a text result
 is requested, sprintf() is used internally to do the conversion
 automatically.  The following table details the conversions that
 are applied:

<blockquote>
<table border="1">
<tr><th>Internal Type</th><th>Requested Type</th><th>Conversion</th></tr>
<tr><td> NULL    </td><td> INTEGER</td><td>Result is 0</td></tr>
<tr><td> NULL </td><td>    FLOAT </td><td> Result is 0.0</td></tr>
<tr><td> NULL </td><td>    TEXT </td><td>  Result is NULL pointer</td></tr>
<tr><td> NULL </td><td>    BLOB </td><td>  Result is NULL pointer</td></tr>
<tr><td> INTEGER </td><td> FLOAT </td><td> Convert from integer to float</td></tr>
<tr><td> INTEGER </td><td> TEXT </td><td>  ASCII rendering of the integer</td></tr>
<tr><td> INTEGER </td><td> BLOB </td><td>  Same as for INTEGER->TEXT</td></tr>
<tr><td> FLOAT </td><td>   INTEGER</td><td>Convert from float to integer</td></tr>
<tr><td> FLOAT </td><td>   TEXT </td><td>  ASCII rendering of the float</td></tr>
<tr><td> FLOAT </td><td>   BLOB </td><td>  Same as FLOAT->TEXT</td></tr>
<tr><td> TEXT </td><td>    INTEGER</td><td>Use atoi()</td></tr>
<tr><td> TEXT </td><td>    FLOAT </td><td> Use atof()</td></tr>
<tr><td> TEXT </td><td>    BLOB </td><td>  No change</td></tr>
<tr><td> BLOB </td><td>    INTEGER</td><td>Convert to TEXT then use atoi()</td></tr>
<tr><td> BLOB </td><td>    FLOAT </td><td> Convert to TEXT then use atof()</td></tr>
<tr><td> BLOB </td><td>    TEXT </td><td>  Add a \\000 terminator if needed</td></tr>
</table>
</blockquote>

  Note that when type conversions occur, pointers returned by prior
  calls to sqlite3_column_blob(), sqlite3_column_text(), and/or
  sqlite3_column_text16() may be invalidated.  So, for example, if
  you initially call sqlite3_column_text() and get back a pointer to
  a UTF-8 string, then you call sqlite3_column_text16(), after the
  call to sqlite3_column_text16() the pointer returned by the prior
  call to sqlite3_column_text() will likely point to deallocated memory.
  Attempting to use the original pointer might lead to heap corruption
  or a segfault.  Note also that calls  to sqlite3_column_bytes()
  and sqlite3_column_bytes16() can also cause type conversion that
  and deallocate prior buffers.  Use these routines carefully.
}

api {} {
int sqlite3_column_count(sqlite3_stmt *pStmt);
} {
 Return the number of columns in the result set returned by the prepared
 SQL statement. This routine returns 0 if pStmt is an SQL statement
 that does not return data (for example an UPDATE).

 See also sqlite3_data_count().
}

api {} {
const char *sqlite3_column_decltype(sqlite3_stmt *, int i);
const void *sqlite3_column_decltype16(sqlite3_stmt*,int);
} {
 The first argument is a prepared SQL statement. If this statement
 is a SELECT statement, the Nth column of the returned result set 
 of the SELECT is a table column then the declared type of the table
 column is returned. If the Nth column of the result set is not a table
 column, then a NULL pointer is returned. The returned string is 
 UTF-8 encoded for sqlite3_column_decltype() and UTF-16 encoded
 for sqlite3_column_decltype16(). For example, in the database schema:

 <blockquote><pre>
 CREATE TABLE t1(c1 INTEGER);
 </pre></blockquote>

 And the following statement compiled:

 <blockquote><pre>
 SELECT c1 + 1, c1 FROM t1;
 </pre></blockquote>

 Then this routine would return the string "INTEGER" for the second
 result column (i==1), and a NULL pointer for the first result column
 (i==0).

 If the following statements were compiled then this routine would
 return "INTEGER" for the first (only) result column.

 <blockquote><pre>
 SELECT (SELECT c1) FROM t1;
 SELECT (SELECT c1 FROM t1);
 SELECT c1 FROM (SELECT c1 FROM t1);
 SELECT * FROM (SELECT c1 FROM t1);
 SELECT * FROM (SELECT * FROM t1);
 </pre></blockquote>
}

api {} {
  int sqlite3_table_column_metadata(
    sqlite3 *db,                /* Connection handle */
    const char *zDbName,        /* Database name or NULL */
    const char *zTableName,     /* Table name */
    const char *zColumnName,    /* Column name */
    char const **pzDataType,    /* OUTPUT: Declared data type */
    char const **pzCollSeq,     /* OUTPUT: Collation sequence name */
    int *pNotNull,              /* OUTPUT: True if NOT NULL constraint exists */
    int *pPrimaryKey,           /* OUTPUT: True if column part of PK */
    int *pAutoinc               /* OUTPUT: True if colums is auto-increment */
  );
} {
 This routine is used to obtain meta information about a specific column of a
 specific database table accessible using the connection handle passed as the
 first function argument.

 The column is identified by the second, third and fourth parameters to 
 this function. The second parameter is either the name of the database
 (i.e. "main", "temp" or an attached database) containing the specified
 table or NULL. If it is NULL, then all attached databases are searched
 for the table using the same algorithm as the database engine uses to 
 resolve unqualified table references.

 The third and fourth parameters to this function are the table and column 
 name of the desired column, respectively. Neither of these parameters 
 may be NULL.

 Meta information is returned by writing to the memory locations passed as
 the 5th and subsequent parameters to this function. Any of these 
 arguments may be NULL, in which case the corresponding element of meta 
 information is ommitted.

<pre>
 Parameter     Output Type      Description
 -----------------------------------
   5th         const char*      Declared data type 
   6th         const char*      Name of the columns default collation sequence 
   7th         int              True if the column has a NOT NULL constraint
   8th         int              True if the column is part of the PRIMARY KEY
   9th         int              True if the column is AUTOINCREMENT
</pre>

 The memory pointed to by the character pointers returned for the 
 declaration type and collation sequence is valid only until the next 
 call to any sqlite API function.

 This function may load one or more schemas from database files. If an
 error occurs during this process, or if the requested table or column
 cannot be found, an SQLITE error code is returned and an error message
 left in the database handle (to be retrieved using sqlite3_errmsg()).
 Specifying an SQL view instead of a table as the third argument is also
 considered an error.

 If the specified column is "rowid", "oid" or "_rowid_" and an 
 INTEGER PRIMARY KEY column has been explicitly declared, then the output 
 parameters are set for the explicitly declared column. If there is no
 explicitly declared IPK column, then the data-type is "INTEGER", the
 collation sequence "BINARY" and the primary-key flag is set. Both
 the not-null and auto-increment flags are clear.

 This API is only available if the library was compiled with the
 SQLITE_ENABLE_COLUMN_METADATA preprocessor symbol defined.
}

api {} {
const char *sqlite3_column_database_name(sqlite3_stmt *pStmt, int N);
const void *sqlite3_column_database_name16(sqlite3_stmt *pStmt, int N);
} {
If the Nth column returned by statement pStmt is a column reference,
these functions may be used to access the name of the database (either 
"main", "temp" or the name of an attached database) that contains
the column. If the Nth column is not a column reference, NULL is
returned.

See the description of function sqlite3_column_decltype() for a
description of exactly which expressions are considered column references.

Function sqlite3_column_database_name() returns a pointer to a UTF-8
encoded string. sqlite3_column_database_name16() returns a pointer
to a UTF-16 encoded string. 
}

api {} {
const char *sqlite3_column_origin_name(sqlite3_stmt *pStmt, int N);
const void *sqlite3_column_origin_name16(sqlite3_stmt *pStmt, int N);
} {
If the Nth column returned by statement pStmt is a column reference,
these functions may be used to access the schema name of the referenced 
column in the database schema. If the Nth column is not a column 
reference, NULL is returned.

See the description of function sqlite3_column_decltype() for a
description of exactly which expressions are considered column references.

Function sqlite3_column_origin_name() returns a pointer to a UTF-8
encoded string. sqlite3_column_origin_name16() returns a pointer
to a UTF-16 encoded string. 
}

api {} {
const char *sqlite3_column_table_name(sqlite3_stmt *pStmt, int N);
const void *sqlite3_column_table_name16(sqlite3_stmt *pStmt, int N);
} {
If the Nth column returned by statement pStmt is a column reference, 
these functions may be used to access the name of the table that 
contains the column.  If the Nth column is not a column reference, 
NULL is returned.

See the description of function sqlite3_column_decltype() for a
description of exactly which expressions are considered column references.

Function sqlite3_column_table_name() returns a pointer to a UTF-8
encoded string. sqlite3_column_table_name16() returns a pointer
to a UTF-16 encoded string. 
}

api {} {
const char *sqlite3_column_name(sqlite3_stmt*,int);
const void *sqlite3_column_name16(sqlite3_stmt*,int);
} {
 The first argument is a prepared SQL statement. This function returns
 the column heading for the Nth column of that statement, where N is the
 second function argument.  The string returned is UTF-8 for
 sqlite3_column_name() and UTF-16 for sqlite3_column_name16().
}

api {} {
void *sqlite3_commit_hook(sqlite3*, int(*xCallback)(void*), void *pArg);
} {
 <i>Experimental</i>

 Register a callback function to be invoked whenever a new transaction
 is committed.  The pArg argument is passed through to the callback.
 callback.  If the callback function returns non-zero, then the commit
 is converted into a rollback.

 If another function was previously registered, its pArg value is returned.
 Otherwise NULL is returned.

 Registering a NULL function disables the callback.  Only a single commit
 hook callback can be registered at a time.
}

api {} {
int sqlite3_complete(const char *sql);
int sqlite3_complete16(const void *sql);
} {
 These functions return true if the given input string comprises
 one or more complete SQL statements.
 The argument must be a nul-terminated UTF-8 string for sqlite3_complete()
 and a nul-terminated UTF-16 string for sqlite3_complete16().

 These routines do not check to see if the SQL statement is well-formed.
 They only check to see that the statement is terminated by a semicolon
 that is not part of a string literal and is not inside
 the body of a trigger.
} {}

api {} {
int sqlite3_create_collation(
  sqlite3*, 
  const char *zName, 
  int pref16, 
  void*,
  int(*xCompare)(void*,int,const void*,int,const void*)
);
int sqlite3_create_collation16(
  sqlite3*, 
  const char *zName, 
  int pref16, 
  void*,
  int(*xCompare)(void*,int,const void*,int,const void*)
);
#define SQLITE_UTF8     1
#define SQLITE_UTF16BE  2
#define SQLITE_UTF16LE  3
#define SQLITE_UTF16    4
} {
 These two functions are used to add new collation sequences to the
 sqlite3 handle specified as the first argument. 

 The name of the new collation sequence is specified as a UTF-8 string
 for sqlite3_create_collation() and a UTF-16 string for
 sqlite3_create_collation16(). In both cases the name is passed as the
 second function argument.

 The third argument must be one of the constants SQLITE_UTF8,
 SQLITE_UTF16LE or SQLITE_UTF16BE, indicating that the user-supplied
 routine expects to be passed pointers to strings encoded using UTF-8,
 UTF-16 little-endian or UTF-16 big-endian respectively.  The
 SQLITE_UTF16 constant indicates that text strings are expected in
 UTF-16 in the native byte order of the host machine.

 A pointer to the user supplied routine must be passed as the fifth
 argument. If it is NULL, this is the same as deleting the collation
 sequence (so that SQLite cannot call it anymore). Each time the user
 supplied function is invoked, it is passed a copy of the void* passed as
 the fourth argument to sqlite3_create_collation() or
 sqlite3_create_collation16() as its first argument.

 The remaining arguments to the user-supplied routine are two strings,
 each represented by a [length, data] pair and encoded in the encoding
 that was passed as the third argument when the collation sequence was
 registered. The user routine should return negative, zero or positive if
 the first string is less than, equal to, or greater than the second
 string. i.e. (STRING1 - STRING2).
}

api {} {
int sqlite3_collation_needed(
  sqlite3*, 
  void*, 
  void(*)(void*,sqlite3*,int eTextRep,const char*)
);
int sqlite3_collation_needed16(
  sqlite3*, 
  void*,
  void(*)(void*,sqlite3*,int eTextRep,const void*)
);
} {
 To avoid having to register all collation sequences before a database
 can be used, a single callback function may be registered with the
 database handle to be called whenever an undefined collation sequence is
 required.

 If the function is registered using the sqlite3_collation_needed() API,
 then it is passed the names of undefined collation sequences as strings
 encoded in UTF-8. If sqlite3_collation_needed16() is used, the names
 are passed as UTF-16 in machine native byte order. A call to either
 function replaces any existing callback.

 When the user-function is invoked, the first argument passed is a copy
 of the second argument to sqlite3_collation_needed() or
 sqlite3_collation_needed16(). The second argument is the database
 handle. The third argument is one of SQLITE_UTF8, SQLITE_UTF16BE or
 SQLITE_UTF16LE, indicating the most desirable form of the collation
 sequence function required. The fourth argument is the name of the
 required collation sequence.

 The collation sequence is returned to SQLite by a collation-needed
 callback using the sqlite3_create_collation() or
 sqlite3_create_collation16() APIs, described above.
}

api {} {
int sqlite3_create_function(
  sqlite3 *,
  const char *zFunctionName,
  int nArg,
  int eTextRep,
  void *pUserData,
  void (*xFunc)(sqlite3_context*,int,sqlite3_value**),
  void (*xStep)(sqlite3_context*,int,sqlite3_value**),
  void (*xFinal)(sqlite3_context*)
);
int sqlite3_create_function16(
  sqlite3*,
  const void *zFunctionName,
  int nArg,
  int eTextRep,
  void *pUserData,
  void (*xFunc)(sqlite3_context*,int,sqlite3_value**),
  void (*xStep)(sqlite3_context*,int,sqlite3_value**),
  void (*xFinal)(sqlite3_context*)
);
#define SQLITE_UTF8     1
#define SQLITE_UTF16    2
#define SQLITE_UTF16BE  3
#define SQLITE_UTF16LE  4
#define SQLITE_ANY      5
} {
 These two functions are used to add SQL functions or aggregates
 implemented in C. The
 only difference between these two routines is that the second argument, the
 name of the (scalar) function or aggregate, is encoded in UTF-8 for
 sqlite3_create_function() and UTF-16 for sqlite3_create_function16().
 The length of the name is limited to 255 bytes, exclusive of the 
 zero-terminator.  Note that the name length limit is in bytes, not
 characters.  Any attempt to create a function with a longer name
 will result in an SQLITE_ERROR error.
 
 The first argument is the database handle that the new function or
 aggregate is to be added to. If a single program uses more than one
 database handle internally, then user functions or aggregates must 
 be added individually to each database handle with which they will be
 used.

 The third argument is the number of arguments that the function or
 aggregate takes. If this argument is -1 then the function or
 aggregate may take any number of arguments.  The maximum number
 of arguments to a new SQL function is 127.  A number larger than
 127 for the third argument results in an SQLITE_ERROR error.

 The fourth argument, eTextRep, specifies what type of text arguments
 this function prefers to receive.  Any function should be able to work
 work with UTF-8, UTF-16le, or UTF-16be.  But some implementations may be
 more efficient with one representation than another.  Users are allowed
 to specify separate implementations for the same function which are called
 depending on the text representation of the arguments.  The the implementation
 which provides the best match is used.  If there is only a single
 implementation which does not care what text representation is used,
 then the fourth argument should be SQLITE_ANY.

 The fifth argument is an arbitrary pointer.  The function implementations
 can gain access to this pointer using the sqlite_user_data() API.

 The sixth, seventh and  eighth argumens, xFunc, xStep and xFinal, are
 pointers to user implemented C functions that implement the user
 function or aggregate. A scalar function requires an implementation of
 the xFunc callback only, NULL pointers should be passed as the xStep
 and xFinal arguments. An aggregate function requires an implementation
 of xStep and xFinal, and NULL should be passed for xFunc. To delete an
 existing user function or aggregate, pass NULL for all three function
 callbacks. Specifying an inconstant set of callback values, such as an
 xFunc and an xFinal, or an xStep but no xFinal, results in an SQLITE_ERROR
 return.
}

api {} {
int sqlite3_data_count(sqlite3_stmt *pStmt);
} {
 Return the number of values in the current row of the result set.

 After a call to sqlite3_step() that returns SQLITE_ROW, this routine
 will return the same value as the sqlite3_column_count() function.
 After sqlite3_step() has returned an SQLITE_DONE, SQLITE_BUSY or
 error code, or before sqlite3_step() has been called on a 
 prepared SQL statement, this routine returns zero.
}

api {} {
int sqlite3_errcode(sqlite3 *db);
} {
 Return the error code for the most recent failed sqlite3_* API call associated
 with sqlite3 handle 'db'.  If a prior API call failed but the most recent
 API call succeeded, the return value from this routine is undefined. 

 Calls to many sqlite3_* functions set the error code and string returned
 by sqlite3_errcode(), sqlite3_errmsg() and sqlite3_errmsg16()
 (overwriting the previous values). Note that calls to sqlite3_errcode(),
 sqlite3_errmsg() and sqlite3_errmsg16() themselves do not affect the
 results of future invocations.  Calls to API routines that do not return
 an error code (examples: sqlite3_data_count() or sqlite3_mprintf()) do
 not change the error code returned by this routine.

 Assuming no other intervening sqlite3_* API calls are made, the error
 code returned by this function is associated with the same error as
 the strings returned by sqlite3_errmsg() and sqlite3_errmsg16().
} {}

api {} {
const char *sqlite3_errmsg(sqlite3*);
const void *sqlite3_errmsg16(sqlite3*);
} {
 Return a pointer to a UTF-8 encoded string (sqlite3_errmsg)
 or a UTF-16 encoded string (sqlite3_errmsg16) describing in English the
 error condition for the most recent sqlite3_* API call. The returned
 string is always terminated by an 0x00 byte.

 The string "not an error" is returned when the most recent API call was
 successful.
}

api {} {
int sqlite3_exec(
  sqlite3*,                     /* An open database */
  const char *sql,              /* SQL to be executed */
  sqlite_callback,              /* Callback function */
  void *,                       /* 1st argument to callback function */
  char **errmsg                 /* Error msg written here */
);
} {
 A function to executes one or more statements of SQL.

 If one or more of the SQL statements are queries, then
 the callback function specified by the 3rd argument is
 invoked once for each row of the query result.  This callback
 should normally return 0.  If the callback returns a non-zero
 value then the query is aborted, all subsequent SQL statements
 are skipped and the sqlite3_exec() function returns the SQLITE_ABORT.

 The 1st argument is an arbitrary pointer that is passed
 to the callback function as its first argument.

 The 2nd argument to the callback function is the number of
 columns in the query result.  The 3rd argument to the callback
 is an array of strings holding the values for each column.
 The 4th argument to the callback is an array of strings holding
 the names of each column.

 The callback function may be NULL, even for queries.  A NULL
 callback is not an error.  It just means that no callback
 will be invoked.

 If an error occurs while parsing or evaluating the SQL (but
 not while executing the callback) then an appropriate error
 message is written into memory obtained from malloc() and
 *errmsg is made to point to that message.  The calling function
 is responsible for freeing the memory that holds the error
 message.   Use sqlite3_free() for this.  If errmsg==NULL,
 then no error message is ever written.

 The return value is is SQLITE_OK if there are no errors and
 some other return code if there is an error.  The particular
 return value depends on the type of error. 

 If the query could not be executed because a database file is
 locked or busy, then this function returns SQLITE_BUSY.  (This
 behavior can be modified somewhat using the sqlite3_busy_handler()
 and sqlite3_busy_timeout() functions.)
} {}

api {} {
int sqlite3_finalize(sqlite3_stmt *pStmt);
} {
 The sqlite3_finalize() function is called to delete a prepared
 SQL statement obtained by a previous call to sqlite3_prepare(),
 sqlite3_prepare_v2(), sqlite3_prepare16(), or sqlite3_prepare16_v2().
 If the statement was executed successfully, or
 not executed at all, then SQLITE_OK is returned. If execution of the
 statement failed then an error code is returned. 

 All prepared statements must finalized before sqlite3_close() is
 called or else the close will fail with a return code of SQLITE_BUSY.

 This routine can be called at any point during the execution of the
 virtual machine.  If the virtual machine has not completed execution
 when this routine is called, that is like encountering an error or
 an interrupt.  (See sqlite3_interrupt().)  Incomplete updates may be
 rolled back and transactions canceled,  depending on the circumstances,
 and the result code returned will be SQLITE_ABORT.
}

api {} {
void *sqlite3_malloc(int);
void *sqlite3_realloc(void*, int);
void sqlite3_free(void*);
} {
 These routines provide access to the memory allocator used by SQLite.
 Depending on how SQLite has been compiled and the OS-layer backend,
 the memory allocator used by SQLite might be the standard system
 malloc()/realloc()/free(), or it might be something different.  With
 certain compile-time flags, SQLite will add wrapper logic around the
 memory allocator to add memory leak and buffer overrun detection.  The
 OS layer might substitute a completely different memory allocator.
 Use these APIs to be sure you are always using the correct memory
 allocator.
 
 The sqlite3_free() API, not the standard free() from the system library,
 should always be used to free the memory buffer returned by
 sqlite3_mprintf() or sqlite3_vmprintf() and to free the error message
 string returned by sqlite3_exec().  Using free() instead of sqlite3_free()
 might accidentally work on some systems and build configurations but 
 will fail on others.

 Compatibility Note:  Prior to version 3.4.0, the sqlite3_free API
 was prototyped to take a <tt>char*</tt> parameter rather than 
 <tt>void*</tt>.  Like this:
<blockquote><pre>
void sqlite3_free(char*);
</pre></blockquote>
 The change to using <tt>void*</tt> might cause warnings when 
 compiling older code against
 newer libraries, but everything should still work correctly.
}

api {} {
int sqlite3_get_table(
  sqlite3*,              /* An open database */
  const char *sql,       /* SQL to be executed */
  char ***resultp,       /* Result written to a char *[]  that this points to */
  int *nrow,             /* Number of result rows written here */
  int *ncolumn,          /* Number of result columns written here */
  char **errmsg          /* Error msg written here */
);
void sqlite3_free_table(char **result);
} {
 This next routine is really just a wrapper around sqlite3_exec().
 Instead of invoking a user-supplied callback for each row of the
 result, this routine remembers each row of the result in memory
 obtained from malloc(), then returns all of the result after the
 query has finished. 

 As an example, suppose the query result where this table:

 <pre>
        Name        | Age
        -----------------------
        Alice       | 43
        Bob         | 28
        Cindy       | 21
 </pre>

 If the 3rd argument were &azResult then after the function returns
 azResult will contain the following data:

 <pre>
        azResult[0] = "Name";
        azResult[1] = "Age";
        azResult[2] = "Alice";
        azResult[3] = "43";
        azResult[4] = "Bob";
        azResult[5] = "28";
        azResult[6] = "Cindy";
        azResult[7] = "21";
 </pre>

 Notice that there is an extra row of data containing the column
 headers.  But the *nrow return value is still 3.  *ncolumn is
 set to 2.  In general, the number of values inserted into azResult
 will be ((*nrow) + 1)*(*ncolumn).

 After the calling function has finished using the result, it should 
 pass the result data pointer to sqlite3_free_table() in order to 
 release the memory that was malloc-ed.  Because of the way the 
 malloc() happens, the calling function must not try to call 
 malloc() directly.  Only sqlite3_free_table() is able to release 
 the memory properly and safely.

 The return value of this routine is the same as from sqlite3_exec().
}

api {sqlite3_interrupt} {
 void sqlite3_interrupt(sqlite3*);
} {
 This function causes any pending database operation to abort and
 return at its earliest opportunity.  This routine is typically
 called in response to a user action such as pressing "Cancel"
 or Ctrl-C where the user wants a long query operation to halt
 immediately.
} {}

api {} {
long long int sqlite3_last_insert_rowid(sqlite3*);
} {
 Each entry in an SQLite table has a unique integer key called the "rowid".
 The rowid is always available as an undeclared column
 named ROWID, OID, or _ROWID_.
 If the table has a column of type INTEGER PRIMARY KEY then that column
 is another an alias for the rowid.

 This routine
 returns the rowid of the most recent INSERT into the database
 from the database connection given in the first argument.  If
 no inserts have ever occurred on this database connection, zero
 is returned.

 If an INSERT occurs within a trigger, then the rowid of the
 inserted row is returned by this routine as long as the trigger
 is running.  But once the trigger terminates, the value returned
 by this routine reverts to the last value inserted before the
 trigger fired.
} {}

api {} {
char *sqlite3_mprintf(const char*,...);
char *sqlite3_vmprintf(const char*, va_list);
} {
 These routines are variants of the "sprintf()" from the
 standard C library.  The resulting string is written into memory
 obtained from malloc() so that there is never a possibility of buffer
 overflow.  These routines also implement some additional formatting
 options that are useful for constructing SQL statements.

 The strings returned by these routines should be freed by calling
 sqlite3_free().

 All of the usual printf formatting options apply.  In addition, there
 is a "%q" option.  %q works like %s in that it substitutes a null-terminated
 string from the argument list.  But %q also doubles every '\\'' character.
 %q is designed for use inside a string literal.  By doubling each '\\''
 character it escapes that character and allows it to be inserted into
 the string.

 For example, so some string variable contains text as follows:

 <blockquote><pre>
  char *zText = "It's a happy day!";
 </pre></blockquote>

 One can use this text in an SQL statement as follows:

 <blockquote><pre>
  sqlite3_exec_printf(db, "INSERT INTO table VALUES('%q')",
       callback1, 0, 0, zText);
  </pre></blockquote>

 Because the %q format string is used, the '\\'' character in zText
 is escaped and the SQL generated is as follows:

 <blockquote><pre>
  INSERT INTO table1 VALUES('It''s a happy day!')
 </pre></blockquote>

 This is correct.  Had we used %s instead of %q, the generated SQL
 would have looked like this:

  <blockquote><pre>
  INSERT INTO table1 VALUES('It's a happy day!');
  </pre></blockquote>

 This second example is an SQL syntax error.  As a general rule you
 should always use %q instead of %s when inserting text into a string 
 literal.
} {}

api {} {
int sqlite3_open(
  const char *filename,   /* Database filename (UTF-8) */
  sqlite3 **ppDb          /* OUT: SQLite db handle */
);
int sqlite3_open16(
  const void *filename,   /* Database filename (UTF-16) */
  sqlite3 **ppDb          /* OUT: SQLite db handle */
);
} {
 Open the sqlite database file "filename".  The "filename" is UTF-8
 encoded for sqlite3_open() and UTF-16 encoded in the native byte order
 for sqlite3_open16().  An sqlite3* handle is returned in *ppDb, even
 if an error occurs. If the database is opened (or created) successfully,
 then SQLITE_OK is returned. Otherwise an error code is returned. The
 sqlite3_errmsg() or sqlite3_errmsg16()  routines can be used to obtain
 an English language description of the error.

 If the database file does not exist, then a new database will be created
 as needed.
 The encoding for the database will be UTF-8 if sqlite3_open() is called and
 UTF-16 if sqlite3_open16 is used.

 Whether or not an error occurs when it is opened, resources associated
 with the sqlite3* handle should be released by passing it to
 sqlite3_close() when it is no longer required.

 The returned sqlite3* can only be used in the same thread in which it
 was created.  It is an error to call sqlite3_open() in one thread then
 pass the resulting database handle off to another thread to use.  This
 restriction is due to goofy design decisions (bugs?) in the way some
 threading implementations interact with file locks.

 Note to windows users:  The encoding used for the filename argument
 of sqlite3_open() must be UTF-8, not whatever codepage is currently
 defined.  Filenames containing international characters must be converted
 to UTF-8 prior to passing them into sqlite3_open().
}

api {} {
int sqlite3_prepare_v2(
  sqlite3 *db,            /* Database handle */
  const char *zSql,       /* SQL statement, UTF-8 encoded */
  int nBytes,             /* Length of zSql in bytes. */
  sqlite3_stmt **ppStmt,  /* OUT: Statement handle */
  const char **pzTail     /* OUT: Pointer to unused portion of zSql */
);
int sqlite3_prepare16_v2(
  sqlite3 *db,            /* Database handle */
  const void *zSql,       /* SQL statement, UTF-16 encoded */
  int nBytes,             /* Length of zSql in bytes. */
  sqlite3_stmt **ppStmt,  /* OUT: Statement handle */
  const void **pzTail     /* OUT: Pointer to unused portion of zSql */
);

/* Legacy Interfaces */
int sqlite3_prepare(
  sqlite3 *db,            /* Database handle */
  const char *zSql,       /* SQL statement, UTF-8 encoded */
  int nBytes,             /* Length of zSql in bytes. */
  sqlite3_stmt **ppStmt,  /* OUT: Statement handle */
  const char **pzTail     /* OUT: Pointer to unused portion of zSql */
);
int sqlite3_prepare16(
  sqlite3 *db,            /* Database handle */
  const void *zSql,       /* SQL statement, UTF-16 encoded */
  int nBytes,             /* Length of zSql in bytes. */
  sqlite3_stmt **ppStmt,  /* OUT: Statement handle */
  const void **pzTail     /* OUT: Pointer to unused portion of zSql */
);
} {
 To execute an SQL query, it must first be compiled into a byte-code
 program using one of these routines. 

 The first argument "db" is an SQLite database handle. The second
 argument "zSql" is the statement to be compiled, encoded as either
 UTF-8 or UTF-16.  The sqlite3_prepare_v2()
 interfaces uses UTF-8 and sqlite3_prepare16_v2()
 use UTF-16. If the next argument, "nBytes", is less
 than zero, then zSql is read up to the first nul terminator.  If
 "nBytes" is not less than zero, then it is the length of the string zSql
 in bytes (not characters).

 *pzTail is made to point to the first byte past the end of the first
 SQL statement in zSql.  This routine only compiles the first statement
 in zSql, so *pzTail is left pointing to what remains uncompiled.

 *ppStmt is left pointing to a compiled SQL statement that can be
 executed using sqlite3_step().  Or if there is an error, *ppStmt may be
 set to NULL.  If the input text contained no SQL (if the input is and
 empty string or a comment) then *ppStmt is set to NULL.  The calling
 procedure is responsible for deleting this compiled SQL statement
 using sqlite3_finalize() after it has finished with it.

 On success, SQLITE_OK is returned.  Otherwise an error code is returned.

 The sqlite3_prepare_v2() and sqlite3_prepare16_v2() interfaces are
 recommended for all new programs. The two older interfaces are retained
 for backwards compatibility, but their use is discouraged.
 In the "v2" interfaces, the prepared statement
 that is returned (the sqlite3_stmt object) contains a copy of the original
 SQL. This causes the sqlite3_step() interface to behave a differently in
 two ways:

 <ol>
 <li>
 If the database schema changes, instead of returning SQLITE_SCHEMA as it
 always used to do, sqlite3_step() will automatically recompile the SQL
 statement and try to run it again.  If the schema has changed in a way
 that makes the statement no longer valid, sqlite3_step() will still
 return SQLITE_SCHEMA.  But unlike the legacy behavior, SQLITE_SCHEMA is
 now a fatal error.  Calling sqlite3_prepare_v2() again will not make the
 error go away.  Note: use sqlite3_errmsg() to find the text of the parsing
 error that results in an SQLITE_SCHEMA return.
 </li>

 <li>
 When an error occurs, 
 sqlite3_step() will return one of the detailed result-codes
 like SQLITE_IOERR or SQLITE_FULL or SQLITE_SCHEMA directly. The
 legacy behavior was that sqlite3_step() would only return a generic
 SQLITE_ERROR code and you would have to make a second call to
 sqlite3_reset() in order to find the underlying cause of the problem.
 With the "v2" prepare interfaces, the underlying reason for the error is
 returned directly.
 </li>
 </ol>
}

api {} {
void sqlite3_progress_handler(sqlite3*, int, int(*)(void*), void*);
} {
 <i>Experimental</i>

 This routine configures a callback function - the progress callback - that
 is invoked periodically during long running calls to sqlite3_exec(),
 sqlite3_step() and sqlite3_get_table().
 An example use for this API is to keep
 a GUI updated during a large query.

 The progress callback is invoked once for every N virtual machine opcodes,
 where N is the second argument to this function. The progress callback
 itself is identified by the third argument to this function. The fourth
 argument to this function is a void pointer passed to the progress callback
 function each time it is invoked.

 If a call to sqlite3_exec(), sqlite3_step() or sqlite3_get_table() results 
 in less than N opcodes being executed, then the progress callback is not
 invoked.
 
 To remove the progress callback altogether, pass NULL as the third
 argument to this function.

 If the progress callback returns a result other than 0, then the current 
 query is immediately terminated and any database changes rolled back. If the
 query was part of a larger transaction, then the transaction is not rolled
 back and remains active. The sqlite3_exec() call returns SQLITE_ABORT. 

}

api {} {
int sqlite3_reset(sqlite3_stmt *pStmt);
} {
 The sqlite3_reset() function is called to reset a prepared SQL
 statement obtained by a previous call to 
 sqlite3_prepare_v2() or
 sqlite3_prepare16_v2() back to it's initial state, ready to be re-executed.
 Any SQL statement variables that had values bound to them using
 the sqlite3_bind_*() API retain their values.
}

api {} {
void sqlite3_result_blob(sqlite3_context*, const void*, int n, void(*)(void*));
void sqlite3_result_double(sqlite3_context*, double);
void sqlite3_result_error(sqlite3_context*, const char*, int);
void sqlite3_result_error16(sqlite3_context*, const void*, int);
void sqlite3_result_int(sqlite3_context*, int);
void sqlite3_result_int64(sqlite3_context*, long long int);
void sqlite3_result_null(sqlite3_context*);
void sqlite3_result_text(sqlite3_context*, const char*, int n, void(*)(void*));
void sqlite3_result_text16(sqlite3_context*, const void*, int n, void(*)(void*));
void sqlite3_result_text16be(sqlite3_context*, const void*, int n, void(*)(void*));
void sqlite3_result_text16le(sqlite3_context*, const void*, int n, void(*)(void*));
void sqlite3_result_value(sqlite3_context*, sqlite3_value*);
} {
 User-defined functions invoke these routines in order to
 set their return value.  The sqlite3_result_value() routine is used
 to return an exact copy of one of the arguments to the function.

 The operation of these routines is very similar to the operation of
 sqlite3_bind_blob() and its cousins.  Refer to the documentation there
 for additional information.
}

api {} {
int sqlite3_set_authorizer(
  sqlite3*,
  int (*xAuth)(void*,int,const char*,const char*,const char*,const char*),
  void *pUserData
);
#define SQLITE_CREATE_INDEX          1   /* Index Name      Table Name      */
#define SQLITE_CREATE_TABLE          2   /* Table Name      NULL            */
#define SQLITE_CREATE_TEMP_INDEX     3   /* Index Name      Table Name      */
#define SQLITE_CREATE_TEMP_TABLE     4   /* Table Name      NULL            */
#define SQLITE_CREATE_TEMP_TRIGGER   5   /* Trigger Name    Table Name      */
#define SQLITE_CREATE_TEMP_VIEW      6   /* View Name       NULL            */
#define SQLITE_CREATE_TRIGGER        7   /* Trigger Name    Table Name      */
#define SQLITE_CREATE_VIEW           8   /* View Name       NULL            */
#define SQLITE_DELETE                9   /* Table Name      NULL            */
#define SQLITE_DROP_INDEX           10   /* Index Name      Table Name      */
#define SQLITE_DROP_TABLE           11   /* Table Name      NULL            */
#define SQLITE_DROP_TEMP_INDEX      12   /* Index Name      Table Name      */
#define SQLITE_DROP_TEMP_TABLE      13   /* Table Name      NULL            */
#define SQLITE_DROP_TEMP_TRIGGER    14   /* Trigger Name    Table Name      */
#define SQLITE_DROP_TEMP_VIEW       15   /* View Name       NULL            */
#define SQLITE_DROP_TRIGGER         16   /* Trigger Name    Table Name      */
#define SQLITE_DROP_VIEW            17   /* View Name       NULL            */
#define SQLITE_INSERT               18   /* Table Name      NULL            */
#define SQLITE_PRAGMA               19   /* Pragma Name     1st arg or NULL */
#define SQLITE_READ                 20   /* Table Name      Column Name     */
#define SQLITE_SELECT               21   /* NULL            NULL            */
#define SQLITE_TRANSACTION          22   /* NULL            NULL            */
#define SQLITE_UPDATE               23   /* Table Name      Column Name     */
#define SQLITE_ATTACH               24   /* Filename        NULL            */
#define SQLITE_DETACH               25   /* Database Name   NULL            */
#define SQLITE_ALTER_TABLE          26   /* Database Name   Table Name      */
#define SQLITE_REINDEX              27   /* Index Name      NULL            */
#define SQLITE_ANALYZE              28   /* Table Name      NULL            */
#define SQLITE_CREATE_VTABLE        29   /* Table Name      Module Name     */
#define SQLITE_DROP_VTABLE          30   /* Table Name      Module Name     */
#define SQLITE_FUNCTION             31   /* Function Name   NULL            */

#define SQLITE_DENY   1   /* Abort the SQL statement with an error */
#define SQLITE_IGNORE 2   /* Don't allow access, but don't generate an error */
} {
 This routine registers a callback with the SQLite library.  The
 callback is invoked by sqlite3_prepare_v2() to authorize various
 operations against the database.  The callback should
 return SQLITE_OK if access is allowed, SQLITE_DENY if the entire
 SQL statement should be aborted with an error and SQLITE_IGNORE
 if the operation should be treated as a no-op.

 Each database connection have at most one authorizer registered
 at a time one time.  Each call
 to sqlite3_set_authorizer() overrides the previous authorizer.
 Setting the callback to NULL disables the authorizer.

 The second argument to the access authorization function will be one
 of the defined constants shown.  These values signify what kind of operation
 is to be authorized.  The 3rd and 4th arguments to the authorization
 function will be arguments or NULL depending on which of the 
 codes is used as the second argument.  For example, if the the
 2nd argument code is SQLITE_READ then the 3rd argument will be the name
 of the table that is being read from and the 4th argument will be the
 name of the column that is being read from.  Or if the 2nd argument
 is SQLITE_FUNCTION then the 3rd argument will be the name of the
 function that is being invoked and the 4th argument will be NULL.

 The 5th argument is the name
 of the database ("main", "temp", etc.) where applicable.  The 6th argument
 is the name of the inner-most trigger or view that is responsible for
 the access attempt or NULL if this access attempt is directly from 
 input SQL code.

 The return value of the authorization callback function should be one of the
 constants SQLITE_OK, SQLITE_DENY, or SQLITE_IGNORE.  A return of
 SQLITE_OK means that the operation is permitted and that 
 sqlite3_prepare_v2() can proceed as normal.
 A return of SQLITE_DENY means that the sqlite3_prepare_v2()
 should fail with an error.  A return of SQLITE_IGNORE causes the 
 sqlite3_prepare_v2() to continue as normal but the requested 
 operation is silently converted into a no-op.  A return of SQLITE_IGNORE
 in response to an SQLITE_READ or SQLITE_FUNCTION causes the column
 being read or the function being invoked to return a NULL.

 The intent of this routine is to allow applications to safely execute
 user-entered SQL.  An appropriate callback can deny the user-entered
 SQL access certain operations (ex: anything that changes the database)
 or to deny access to certain tables or columns within the database.

 SQLite is not reentrant through the authorization callback function.
 The authorization callback function should not attempt to invoke
 any other SQLite APIs for the same database connection.  If the
 authorization callback function invokes some other SQLite API, an
 SQLITE_MISUSE error or a segmentation fault may result.
}

api {} {
int sqlite3_step(sqlite3_stmt*);
} {
 After an SQL query has been prepared with a call to either
 sqlite3_prepare_v2() or sqlite3_prepare16_v2() or to one of
 the legacy interfaces sqlite3_prepare() or sqlite3_prepare16(),
 then this function must be
 called one or more times to execute the statement.

 The details of the behavior of this sqlite3_step() interface depend
 on whether the statement was prepared using the newer "v2" interface
 sqlite3_prepare_v2() and sqlite3_prepare16_v2() or the older legacy
 interface sqlite3_prepare() and sqlite3_prepare16().  The use of the
 new "v2" interface is recommended for new applications but the legacy
 interface will continue to be supported.

 In the lagacy interface, the return value will be either SQLITE_BUSY, 
 SQLITE_DONE, SQLITE_ROW, SQLITE_ERROR, or SQLITE_MISUSE.  With the "v2"
 interface, any of the other SQLite result-codes might be returned as
 well.

 SQLITE_BUSY means that the database engine attempted to open
 a locked database and there is no busy callback registered.
 Call sqlite3_step() again to retry the open.

 SQLITE_DONE means that the statement has finished executing
 successfully.  sqlite3_step() should not be called again on this virtual
 machine without first calling sqlite3_reset() to reset the virtual
 machine back to its initial state.

 If the SQL statement being executed returns any data, then 
 SQLITE_ROW is returned each time a new row of data is ready
 for processing by the caller. The values may be accessed using
 the sqlite3_column_int(), sqlite3_column_text(), and similar functions.
 sqlite3_step() is called again to retrieve the next row of data.
 
 SQLITE_ERROR means that a run-time error (such as a constraint
 violation) has occurred.  sqlite3_step() should not be called again on
 the VM. More information may be found by calling sqlite3_errmsg().
 A more specific error code (example: SQLITE_INTERRUPT, SQLITE_SCHEMA,
 SQLITE_CORRUPT, and so forth) can be obtained by calling
 sqlite3_reset() on the prepared statement.  In the "v2" interface,
 the more specific error code is returned directly by sqlite3_step().

 SQLITE_MISUSE means that the this routine was called inappropriately.
 Perhaps it was called on a virtual machine that had already been
 finalized or on one that had previously returned SQLITE_ERROR or
 SQLITE_DONE.  Or it could be the case that a database connection
 is being used by a different thread than the one it was created it.

 <b>Goofy Interface Alert:</b>
 In the legacy interface, 
 the sqlite3_step() API always returns a generic error code,
 SQLITE_ERROR, following any error other than SQLITE_BUSY and SQLITE_MISUSE.
 You must call sqlite3_reset() (or sqlite3_finalize()) in order to find
 one of the specific result-codes that better describes the error.
 We admit that this is a goofy design.  The problem has been fixed
 with the "v2" interface.  If you prepare all of your SQL statements
 using either sqlite3_prepare_v2() or sqlite3_prepare16_v2() instead
 of the legacy sqlite3_prepare() and sqlite3_prepare16(), then the 
 more specific result-codes are returned directly by sqlite3_step().
 The use of the "v2" interface is recommended.
}

api {} {
void *sqlite3_trace(sqlite3*, void(*xTrace)(void*,const char*), void*);
} {
 Register a function that is called each time an SQL statement is evaluated.
 The callback function is invoked on the first call to sqlite3_step() after
 calls to sqlite3_prepare_v2() or sqlite3_reset().
 This function can be used (for example) to generate
 a log file of all SQL executed against a database.  This can be
 useful when debugging an application that uses SQLite.
}

api {} {
void *sqlite3_user_data(sqlite3_context*);
} {
 The pUserData argument to the sqlite3_create_function() and
 sqlite3_create_function16() routines used to register user functions
 is available to the implementation of the function using this
 call.
}

api {} {
const void *sqlite3_value_blob(sqlite3_value*);
int sqlite3_value_bytes(sqlite3_value*);
int sqlite3_value_bytes16(sqlite3_value*);
double sqlite3_value_double(sqlite3_value*);
int sqlite3_value_int(sqlite3_value*);
long long int sqlite3_value_int64(sqlite3_value*);
const unsigned char *sqlite3_value_text(sqlite3_value*);
const void *sqlite3_value_text16(sqlite3_value*);
const void *sqlite3_value_text16be(sqlite3_value*);
const void *sqlite3_value_text16le(sqlite3_value*);
int sqlite3_value_type(sqlite3_value*);
} {
 This group of routines returns information about arguments to
 a user-defined function.  Function implementations use these routines
 to access their arguments.  These routines are the same as the
 sqlite3_column_... routines except that these routines take a single
 sqlite3_value* pointer instead of an sqlite3_stmt* and an integer
 column number.

 See the documentation under sqlite3_column_blob for additional
 information.
}

api {} {
  int sqlite3_sleep(int);
} {
 Sleep for a little while. The second parameter is the number of
 miliseconds to sleep for. 

 If the operating system does not support sleep requests with 
 milisecond time resolution, then the time will be rounded up to 
 the nearest second. The number of miliseconds of sleep actually 
 requested from the operating system is returned.
}

api {} {
  int sqlite3_expired(sqlite3_stmt*);
} {
 Return TRUE (non-zero) if the statement supplied as an argument needs
 to be recompiled.  A statement needs to be recompiled whenever the
 execution environment changes in a way that would alter the program
 that sqlite3_prepare() generates.  For example, if new functions or
 collating sequences are registered or if an authorizer function is
 added or changed.
}

api {} {
  int sqlite3_transfer_bindings(sqlite3_stmt*, sqlite3_stmt*);
} {
 Move all bindings from the first prepared statement over to the second.
 This routine is useful, for example, if the first prepared statement
 fails with an SQLITE_SCHEMA error.  The same SQL can be prepared into
 the second prepared statement then all of the bindings transfered over
 to the second statement before the first statement is finalized.
}

api {} {
  int sqlite3_global_recover();
} {
 This function used to be involved in recovering from out-of-memory
 errors.  But as of SQLite version 3.3.0, out-of-memory recovery is
 automatic and this routine now does nothing.  THe interface is retained
 to avoid link errors with legacy code.
}

api {} {
  int sqlite3_get_autocommit(sqlite3*);
} {
 Test to see whether or not the database connection is in autocommit
 mode.  Return TRUE if it is and FALSE if not.  Autocommit mode is on
 by default.  Autocommit is disabled by a BEGIN statement and reenabled
 by the next COMMIT or ROLLBACK.
}

api {} {
  int sqlite3_clear_bindings(sqlite3_stmt*);
} {
 Set all the parameters in the compiled SQL statement back to NULL.
}

api {} {
  sqlite3 *sqlite3_db_handle(sqlite3_stmt*);
} {
 Return the sqlite3* database handle to which the prepared statement given
 in the argument belongs.  This is the same database handle that was
 the first argument to the sqlite3_prepare() that was used to create
 the statement in the first place.
}

api {} {
  void *sqlite3_update_hook(
    sqlite3*, 
    void(*)(void *,int ,char const *,char const *,sqlite_int64),
    void*
  );
} {
 Register a callback function with the database connection identified by the 
 first argument to be invoked whenever a row is updated, inserted or deleted.
 Any callback set by a previous call to this function for the same 
 database connection is overridden.

 The second argument is a pointer to the function to invoke when a 
 row is updated, inserted or deleted. The first argument to the callback is
 a copy of the third argument to sqlite3_update_hook. The second callback 
 argument is one of SQLITE_INSERT, SQLITE_DELETE or SQLITE_UPDATE, depending
 on the operation that caused the callback to be invoked. The third and 
 fourth arguments to the callback contain pointers to the database and 
 table name containing the affected row. The final callback parameter is 
 the rowid of the row. In the case of an update, this is the rowid after 
 the update takes place.

 The update hook is not invoked when internal system tables are
 modified (i.e. sqlite_master and sqlite_sequence).

 If another function was previously registered, its pArg value is returned.
 Otherwise NULL is returned.

 See also: sqlite3_commit_hook(), sqlite3_rollback_hook()
}

api {} {
  void *sqlite3_rollback_hook(sqlite3*, void(*)(void *), void*);
} {
 Register a callback to be invoked whenever a transaction is rolled
 back. 

 The new callback function overrides any existing rollback-hook
 callback. If there was an existing callback, then it's pArg value 
 (the third argument to sqlite3_rollback_hook() when it was registered) 
 is returned. Otherwise, NULL is returned.

 For the purposes of this API, a transaction is said to have been 
 rolled back if an explicit "ROLLBACK" statement is executed, or
 an error or constraint causes an implicit rollback to occur. The 
 callback is not invoked if a transaction is automatically rolled
 back because the database connection is closed.
}

api {} {
  int sqlite3_enable_shared_cache(int);
} {
  This routine enables or disables the sharing of the database cache
  and schema data structures between connections to the same database.
  Sharing is enabled if the argument is true and disabled if the argument
  is false.

  Cache sharing is enabled and disabled on a thread-by-thread basis.
  Each call to this routine enables or disables cache sharing only for
  connections created in the same thread in which this routine is called.
  There is no mechanism for sharing cache between database connections
  running in different threads.

  Sharing must be disabled prior to shutting down a thread or else
  the thread will leak memory.  Call this routine with an argument of
  0 to turn off sharing.  Or use the sqlite3_thread_cleanup() API.

  This routine must not be called when any database connections
  are active in the current thread.  Enabling or disabling shared
  cache while there are active database connections will result
  in memory corruption.

  When the shared cache is enabled, the
  following routines must always be called from the same thread:
  sqlite3_open(), sqlite3_prepare_v2(), sqlite3_step(), sqlite3_reset(),
  sqlite3_finalize(), and sqlite3_close().
  This is due to the fact that the shared cache makes use of
  thread-specific storage so that it will be available for sharing
  with other connections.

  Virtual tables cannot be used with a shared cache.  When shared
  cache is enabled, the sqlite3_create_module() API used to register
  virtual tables will always return an error.

  This routine returns SQLITE_OK if shared cache was
  enabled or disabled successfully.  An error code is returned
  otherwise.

  Shared cache is disabled by default for backward compatibility.
}

api {} {
  void sqlite3_thread_cleanup(void);
} {
  This routine makes sure that all thread local storage used by SQLite
  in the current thread has been deallocated.  A thread can call this
  routine prior to terminating in order to make sure there are no memory
  leaks.

  This routine is not strictly necessary.  If cache sharing has been
  disabled using sqlite3_enable_shared_cache() and if all database
  connections have been closed and if SQLITE_ENABLE_MEMORY_MANAGMENT is
  on and all memory has been freed, then the thread local storage will
  already have been automatically deallocated.  This routine is provided
  as a convenience to the program who just wants to make sure that there
  are no leaks.
}

api {} {
  int sqlite3_release_memory(int N);
} {
  This routine attempts to free at least N bytes of memory from the caches
  of database connecions that were created in the same thread from which this
  routine is called.  The value returned is the number of bytes actually
  freed.  

  This routine is only available if memory management has been enabled
  by compiling with the SQLITE_ENABLE_MEMORY_MANAGMENT macro.
}

api {} {
  void sqlite3_soft_heap_limit(int N);
} {
  This routine sets the soft heap limit for the current thread to N.
  If the total heap usage by SQLite in the current thread exceeds N,
  then sqlite3_release_memory() is called to try to reduce the memory usage
  below the soft limit.

  Prior to shutting down a thread sqlite3_soft_heap_limit() must be set to 
  zero (the default) or else the thread will leak memory. Alternatively, use
  the sqlite3_thread_cleanup() API.

  A negative or zero value for N means that there is no soft heap limit and
  sqlite3_release_memory() will only be called when memory is exhaused.
  The default value for the soft heap limit is zero.

  SQLite makes a best effort to honor the soft heap limit.  But if it
  is unable to reduce memory usage below the soft limit, execution will
  continue without error or notification.  This is why the limit is 
  called a "soft" limit.  It is advisory only.

  This routine is only available if memory management has been enabled
  by compiling with the SQLITE_ENABLE_MEMORY_MANAGMENT macro.
}

api {} {
  void sqlite3_thread_cleanup(void);
} {
  This routine ensures that a thread that has used SQLite in the past
  has released any thread-local storage it might have allocated.  
  When the rest of the API is used properly, the cleanup of 
  thread-local storage should be completely automatic.  You should
  never really need to invoke this API.  But it is provided to you
  as a precaution and as a potential work-around for future
  thread-releated memory-leaks.
}

set n 0
set i 0
foreach item $apilist {
  set namelist [lindex $item 0]
  foreach name $namelist {
    set n_to_name($n) $name
    set n_to_idx($n) $i
    set name_to_idx($name) $i
    incr n
  }
  incr i
}
set i 0
foreach name [lsort [array names name_to_idx]] {
  set sname($i) $name
  incr i
}
#parray n_to_name
#parray n_to_idx
#parray name_to_idx
#parray sname
incr n -1
puts "<DIV class=pdf_ignore>"
puts {<table width="100%" cellpadding="5"><tr>}
set nrow [expr {($n+2)/3}]
set i 0
for {set j 0} {$j<3} {incr j} {
  if {$j>0} {puts {<td width="10"></td>}}
  puts {<td valign="top">}
  set limit [expr {$i+$nrow}]
  puts {<ul>}
  while {$i<$limit && $i<$n} {
    set name $sname($i)
    if {[regexp {^sqlite} $name]} {set display $name} {set display <i>$name</i>}
    puts "<li><a href=\"#$name\">$display</a></li>"
    incr i
  }
  puts {</ul></td>}
}
puts "</table>"
puts "<!-- $n entries.  $nrow rows in 3 columns -->"
puts "</DIV>"

proc resolve_name {ignore_list name} {
  global name_to_idx
  if {![info exists name_to_idx($name)] || [lsearch $ignore_list $name]>=0} {
    return $name
  } else {
    return "<a href=\"#$name\">$name</a>"
  }
}

foreach name [lsort [array names name_to_idx]] {
  set i $name_to_idx($name)
  if {[info exists done($i)]} continue
  set done($i) 1
  foreach {namelist prototype desc} [lindex $apilist $i] break
  foreach name $namelist {
    puts "<a name=\"$name\"></a>"
  }
  puts "<p><hr></p>"
  puts "<blockquote><pre>"
  regsub "^( *\n)+" $prototype {} p2
  regsub "(\n *)+\$" $p2 {} p3
  puts $p3
  puts "</pre></blockquote>"
  regsub -all {\[} $desc {\[} desc
  regsub -all {sqlite3_[a-z0-9_]+} $desc "\[resolve_name $name &\]" d2
  foreach x $specialname {
    regsub -all $x $d2 "\[resolve_name $name &\]" d2
  }
  regsub -all "\n( *\n)+" [subst $d2] "</p>\n\n<p>" d3
  puts "<p>$d3</p>"
}

puts "<DIV class=pdf_ignore>"
footer $rcsid
puts "</DIV>"