Update sqlite to 3.7.3.

third_party/sqlite/src/ext/fts3/fts3_write.c

+/*
+** 2009 Oct 23
+**
+** 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 is part of the SQLite FTS3 extension module. Specifically,
+** this file contains code to insert, update and delete rows from FTS3
+** tables. It also contains code to merge FTS3 b-tree segments. Some
+** of the sub-routines used to merge segments are also used by the query 
+** code in fts3.c.
+*/
+
+#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
+
+#include "fts3Int.h"
+#include <string.h>
+#include <assert.h>
+#include <stdlib.h>
+
+typedef struct PendingList PendingList;
+typedef struct SegmentNode SegmentNode;
+typedef struct SegmentWriter SegmentWriter;
+
+/*
+** Data structure used while accumulating terms in the pending-terms hash
+** table. The hash table entry maps from term (a string) to a malloc'd
+** instance of this structure.
+*/
+struct PendingList {
+  int nData;
+  char *aData;
+  int nSpace;
+  sqlite3_int64 iLastDocid;
+  sqlite3_int64 iLastCol;
+  sqlite3_int64 iLastPos;
+};
+
+/*
+** An instance of this structure is used to iterate through the terms on
+** a contiguous set of segment b-tree leaf nodes. Although the details of
+** this structure are only manipulated by code in this file, opaque handles
+** of type Fts3SegReader* are also used by code in fts3.c to iterate through
+** terms when querying the full-text index. See functions:
+**
+**   sqlite3Fts3SegReaderNew()
+**   sqlite3Fts3SegReaderFree()
+**   sqlite3Fts3SegReaderIterate()
+**
+** Methods used to manipulate Fts3SegReader structures:
+**
+**   fts3SegReaderNext()
+**   fts3SegReaderFirstDocid()
+**   fts3SegReaderNextDocid()
+*/
+struct Fts3SegReader {
+  int iIdx;                       /* Index within level, or 0x7FFFFFFF for PT */
+  sqlite3_int64 iStartBlock;
+  sqlite3_int64 iEndBlock;
+  sqlite3_stmt *pStmt;            /* SQL Statement to access leaf nodes */
+  char *aNode;                    /* Pointer to node data (or NULL) */
+  int nNode;                      /* Size of buffer at aNode (or 0) */
+  int nTermAlloc;                 /* Allocated size of zTerm buffer */
+  Fts3HashElem **ppNextElem;
+
+  /* Variables set by fts3SegReaderNext(). These may be read directly
+  ** by the caller. They are valid from the time SegmentReaderNew() returns
+  ** until SegmentReaderNext() returns something other than SQLITE_OK
+  ** (i.e. SQLITE_DONE).
+  */
+  int nTerm;                      /* Number of bytes in current term */
+  char *zTerm;                    /* Pointer to current term */
+  char *aDoclist;                 /* Pointer to doclist of current entry */
+  int nDoclist;                   /* Size of doclist in current entry */
+
+  /* The following variables are used to iterate through the current doclist */
+  char *pOffsetList;
+  sqlite3_int64 iDocid;
+};
+
+#define fts3SegReaderIsPending(p) ((p)->ppNextElem!=0)
+
+/*
+** An instance of this structure is used to create a segment b-tree in the
+** database. The internal details of this type are only accessed by the
+** following functions:
+**
+**   fts3SegWriterAdd()
+**   fts3SegWriterFlush()
+**   fts3SegWriterFree()
+*/
+struct SegmentWriter {
+  SegmentNode *pTree;             /* Pointer to interior tree structure */
+  sqlite3_int64 iFirst;           /* First slot in %_segments written */
+  sqlite3_int64 iFree;            /* Next free slot in %_segments */
+  char *zTerm;                    /* Pointer to previous term buffer */
+  int nTerm;                      /* Number of bytes in zTerm */
+  int nMalloc;                    /* Size of malloc'd buffer at zMalloc */
+  char *zMalloc;                  /* Malloc'd space (possibly) used for zTerm */
+  int nSize;                      /* Size of allocation at aData */
+  int nData;                      /* Bytes of data in aData */
+  char *aData;                    /* Pointer to block from malloc() */
+};
+
+/*
+** Type SegmentNode is used by the following three functions to create
+** the interior part of the segment b+-tree structures (everything except
+** the leaf nodes). These functions and type are only ever used by code
+** within the fts3SegWriterXXX() family of functions described above.
+**
+**   fts3NodeAddTerm()
+**   fts3NodeWrite()
+**   fts3NodeFree()
+*/
+struct SegmentNode {
+  SegmentNode *pParent;           /* Parent node (or NULL for root node) */
+  SegmentNode *pRight;            /* Pointer to right-sibling */
+  SegmentNode *pLeftmost;         /* Pointer to left-most node of this depth */
+  int nEntry;                     /* Number of terms written to node so far */
+  char *zTerm;                    /* Pointer to previous term buffer */
+  int nTerm;                      /* Number of bytes in zTerm */
+  int nMalloc;                    /* Size of malloc'd buffer at zMalloc */
+  char *zMalloc;                  /* Malloc'd space (possibly) used for zTerm */
+  int nData;                      /* Bytes of valid data so far */
+  char *aData;                    /* Node data */
+};
+
+/*
+** Valid values for the second argument to fts3SqlStmt().
+*/
+#define SQL_DELETE_CONTENT             0
+#define SQL_IS_EMPTY                   1
+#define SQL_DELETE_ALL_CONTENT         2 
+#define SQL_DELETE_ALL_SEGMENTS        3
+#define SQL_DELETE_ALL_SEGDIR          4
+#define SQL_DELETE_ALL_DOCSIZE         5
+#define SQL_DELETE_ALL_STAT            6
+#define SQL_SELECT_CONTENT_BY_ROWID    7
+#define SQL_NEXT_SEGMENT_INDEX         8
+#define SQL_INSERT_SEGMENTS            9
+#define SQL_NEXT_SEGMENTS_ID          10
+#define SQL_INSERT_SEGDIR             11
+#define SQL_SELECT_LEVEL              12
+#define SQL_SELECT_ALL_LEVEL          13
+#define SQL_SELECT_LEVEL_COUNT        14
+#define SQL_SELECT_SEGDIR_COUNT_MAX   15
+#define SQL_DELETE_SEGDIR_BY_LEVEL    16
+#define SQL_DELETE_SEGMENTS_RANGE     17
+#define SQL_CONTENT_INSERT            18
+#define SQL_GET_BLOCK                 19
+#define SQL_DELETE_DOCSIZE            20
+#define SQL_REPLACE_DOCSIZE           21
+#define SQL_SELECT_DOCSIZE            22
+#define SQL_SELECT_DOCTOTAL           23
+#define SQL_REPLACE_DOCTOTAL          24
+
+/*
+** This function is used to obtain an SQLite prepared statement handle
+** for the statement identified by the second argument. If successful,
+** *pp is set to the requested statement handle and SQLITE_OK returned.
+** Otherwise, an SQLite error code is returned and *pp is set to 0.
+**
+** If argument apVal is not NULL, then it must point to an array with
+** at least as many entries as the requested statement has bound 
+** parameters. The values are bound to the statements parameters before
+** returning.
+*/
+static int fts3SqlStmt(
+  Fts3Table *p,                   /* Virtual table handle */
+  int eStmt,                      /* One of the SQL_XXX constants above */
+  sqlite3_stmt **pp,              /* OUT: Statement handle */
+  sqlite3_value **apVal           /* Values to bind to statement */
+){
+  const char *azSql[] = {
+/* 0  */  "DELETE FROM %Q.'%q_content' WHERE rowid = ?",
+/* 1  */  "SELECT NOT EXISTS(SELECT docid FROM %Q.'%q_content' WHERE rowid!=?)",
+/* 2  */  "DELETE FROM %Q.'%q_content'",
+/* 3  */  "DELETE FROM %Q.'%q_segments'",
+/* 4  */  "DELETE FROM %Q.'%q_segdir'",
+/* 5  */  "DELETE FROM %Q.'%q_docsize'",
+/* 6  */  "DELETE FROM %Q.'%q_stat'",
+/* 7  */  "SELECT * FROM %Q.'%q_content' WHERE rowid=?",
+/* 8  */  "SELECT (SELECT max(idx) FROM %Q.'%q_segdir' WHERE level = ?) + 1",
+/* 9  */  "INSERT INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)",
+/* 10 */  "SELECT coalesce((SELECT max(blockid) FROM %Q.'%q_segments') + 1, 1)",
+/* 11 */  "INSERT INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)",
+
+          /* Return segments in order from oldest to newest.*/ 
+/* 12 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
+            "FROM %Q.'%q_segdir' WHERE level = ? ORDER BY idx ASC",
+/* 13 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
+            "FROM %Q.'%q_segdir' ORDER BY level DESC, idx ASC",
+
+/* 14 */  "SELECT count(*) FROM %Q.'%q_segdir' WHERE level = ?",
+/* 15 */  "SELECT count(*), max(level) FROM %Q.'%q_segdir'",
+
+/* 16 */  "DELETE FROM %Q.'%q_segdir' WHERE level = ?",
+/* 17 */  "DELETE FROM %Q.'%q_segments' WHERE blockid BETWEEN ? AND ?",
+/* 18 */  "INSERT INTO %Q.'%q_content' VALUES(%z)",
+/* 19 */  "SELECT block FROM %Q.'%q_segments' WHERE blockid = ?",
+/* 20 */  "DELETE FROM %Q.'%q_docsize' WHERE docid = ?",
+/* 21 */  "REPLACE INTO %Q.'%q_docsize' VALUES(?,?)",
+/* 22 */  "SELECT size FROM %Q.'%q_docsize' WHERE docid=?",
+/* 23 */  "SELECT value FROM %Q.'%q_stat' WHERE id=0",
+/* 24 */  "REPLACE INTO %Q.'%q_stat' VALUES(0,?)",
+  };
+  int rc = SQLITE_OK;
+  sqlite3_stmt *pStmt;
+
+  assert( SizeofArray(azSql)==SizeofArray(p->aStmt) );
+  assert( eStmt<SizeofArray(azSql) && eStmt>=0 );
+  
+  pStmt = p->aStmt[eStmt];
+  if( !pStmt ){
+    char *zSql;
+    if( eStmt==SQL_CONTENT_INSERT ){
+      int i;                      /* Iterator variable */  
+      char *zVarlist;             /* The "?, ?, ..." string */
+      zVarlist = (char *)sqlite3_malloc(2*p->nColumn+2);
+      if( !zVarlist ){
+        *pp = 0;
+        return SQLITE_NOMEM;
+      }
+      zVarlist[0] = '?';
+      zVarlist[p->nColumn*2+1] = '\0';
+      for(i=1; i<=p->nColumn; i++){
+        zVarlist[i*2-1] = ',';
+        zVarlist[i*2] = '?';
+      }
+      zSql = sqlite3_mprintf(azSql[eStmt], p->zDb, p->zName, zVarlist);
+    }else{
+      zSql = sqlite3_mprintf(azSql[eStmt], p->zDb, p->zName);
+    }
+    if( !zSql ){
+      rc = SQLITE_NOMEM;
+    }else{
+      rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, NULL);
+      sqlite3_free(zSql);
+      assert( rc==SQLITE_OK || pStmt==0 );
+      p->aStmt[eStmt] = pStmt;
+    }
+  }
+  if( apVal ){
+    int i;
+    int nParam = sqlite3_bind_parameter_count(pStmt);
+    for(i=0; rc==SQLITE_OK && i<nParam; i++){
+      rc = sqlite3_bind_value(pStmt, i+1, apVal[i]);
+    }
+  }
+  *pp = pStmt;
+  return rc;
+}
+
+/*
+** Similar to fts3SqlStmt(). Except, after binding the parameters in
+** array apVal[] to the SQL statement identified by eStmt, the statement
+** is executed.
+**
+** Returns SQLITE_OK if the statement is successfully executed, or an
+** SQLite error code otherwise.
+*/
+static void fts3SqlExec(
+  int *pRC,                /* Result code */
+  Fts3Table *p,            /* The FTS3 table */
+  int eStmt,               /* Index of statement to evaluate */
+  sqlite3_value **apVal    /* Parameters to bind */
+){
+  sqlite3_stmt *pStmt;
+  int rc;
+  if( *pRC ) return;
+  rc = fts3SqlStmt(p, eStmt, &pStmt, apVal); 
+  if( rc==SQLITE_OK ){
+    sqlite3_step(pStmt);
+    rc = sqlite3_reset(pStmt);
+  }
+  *pRC = rc;
+}
+
+
+/*
+** Read a single block from the %_segments table. If the specified block
+** does not exist, return SQLITE_CORRUPT. If some other error (malloc, IO 
+** etc.) occurs, return the appropriate SQLite error code.
+**
+** Otherwise, if successful, set *pzBlock to point to a buffer containing
+** the block read from the database, and *pnBlock to the size of the read
+** block in bytes.
+**
+** WARNING: The returned buffer is only valid until the next call to 
+** sqlite3Fts3ReadBlock().
+*/
+int sqlite3Fts3ReadBlock(
+  Fts3Table *p,
+  sqlite3_int64 iBlock,
+  char const **pzBlock,
+  int *pnBlock
+){
+  sqlite3_stmt *pStmt;
+  int rc = fts3SqlStmt(p, SQL_GET_BLOCK, &pStmt, 0);
+  if( rc!=SQLITE_OK ) return rc;
+  sqlite3_reset(pStmt);
+
+  if( pzBlock ){
+    sqlite3_bind_int64(pStmt, 1, iBlock);
+    rc = sqlite3_step(pStmt); 
+    if( rc!=SQLITE_ROW ){
+      return (rc==SQLITE_DONE ? SQLITE_CORRUPT : rc);
+    }
+  
+    *pnBlock = sqlite3_column_bytes(pStmt, 0);
+    *pzBlock = (char *)sqlite3_column_blob(pStmt, 0);
+    if( sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB ){
+      return SQLITE_CORRUPT;
+    }
+  }
+  return SQLITE_OK;
+}
+
+/*
+** This function ensures that the caller has obtained a shared-cache
+** table-lock on the %_content table. This is required before reading
+** data from the fts3 table. If this lock is not acquired first, then
+** the caller may end up holding read-locks on the %_segments and %_segdir
+** tables, but no read-lock on the %_content table. If this happens 
+** a second connection will be able to write to the fts3 table, but
+** attempting to commit those writes might return SQLITE_LOCKED or
+** SQLITE_LOCKED_SHAREDCACHE (because the commit attempts to obtain 
+** write-locks on the %_segments and %_segdir ** tables). 
+**
+** We try to avoid this because if FTS3 returns any error when committing
+** a transaction, the whole transaction will be rolled back. And this is
+** not what users expect when they get SQLITE_LOCKED_SHAREDCACHE. It can
+** still happen if the user reads data directly from the %_segments or
+** %_segdir tables instead of going through FTS3 though.
+*/
+int sqlite3Fts3ReadLock(Fts3Table *p){
+  int rc;                         /* Return code */
+  sqlite3_stmt *pStmt;            /* Statement used to obtain lock */
+
+  rc = fts3SqlStmt(p, SQL_SELECT_CONTENT_BY_ROWID, &pStmt, 0);
+  if( rc==SQLITE_OK ){
+    sqlite3_bind_null(pStmt, 1);
+    sqlite3_step(pStmt);
+    rc = sqlite3_reset(pStmt);
+  }
+  return rc;
+}
+
+/*
+** Set *ppStmt to a statement handle that may be used to iterate through
+** all rows in the %_segdir table, from oldest to newest. If successful,
+** return SQLITE_OK. If an error occurs while preparing the statement, 
+** return an SQLite error code.
+**
+** There is only ever one instance of this SQL statement compiled for
+** each FTS3 table.
+**
+** The statement returns the following columns from the %_segdir table:
+**
+**   0: idx
+**   1: start_block
+**   2: leaves_end_block
+**   3: end_block
+**   4: root
+*/
+int sqlite3Fts3AllSegdirs(Fts3Table *p, sqlite3_stmt **ppStmt){
+  return fts3SqlStmt(p, SQL_SELECT_ALL_LEVEL, ppStmt, 0);
+}
+
+
+/*
+** Append a single varint to a PendingList buffer. SQLITE_OK is returned
+** if successful, or an SQLite error code otherwise.
+**
+** This function also serves to allocate the PendingList structure itself.
+** For example, to create a new PendingList structure containing two
+** varints:
+**
+**   PendingList *p = 0;
+**   fts3PendingListAppendVarint(&p, 1);
+**   fts3PendingListAppendVarint(&p, 2);
+*/
+static int fts3PendingListAppendVarint(
+  PendingList **pp,               /* IN/OUT: Pointer to PendingList struct */
+  sqlite3_int64 i                 /* Value to append to data */
+){
+  PendingList *p = *pp;
+
+  /* Allocate or grow the PendingList as required. */
+  if( !p ){
+    p = sqlite3_malloc(sizeof(*p) + 100);
+    if( !p ){
+      return SQLITE_NOMEM;
+    }
+    p->nSpace = 100;
+    p->aData = (char *)&p[1];
+    p->nData = 0;
+  }
+  else if( p->nData+FTS3_VARINT_MAX+1>p->nSpace ){
+    int nNew = p->nSpace * 2;
+    p = sqlite3_realloc(p, sizeof(*p) + nNew);
+    if( !p ){
+      sqlite3_free(*pp);
+      *pp = 0;
+      return SQLITE_NOMEM;
+    }
+    p->nSpace = nNew;
+    p->aData = (char *)&p[1];
+  }
+
+  /* Append the new serialized varint to the end of the list. */
+  p->nData += sqlite3Fts3PutVarint(&p->aData[p->nData], i);
+  p->aData[p->nData] = '\0';
+  *pp = p;
+  return SQLITE_OK;
+}
+
+/*
+** Add a docid/column/position entry to a PendingList structure. Non-zero
+** is returned if the structure is sqlite3_realloced as part of adding
+** the entry. Otherwise, zero.
+**
+** If an OOM error occurs, *pRc is set to SQLITE_NOMEM before returning.
+** Zero is always returned in this case. Otherwise, if no OOM error occurs,
+** it is set to SQLITE_OK.
+*/
+static int fts3PendingListAppend(
+  PendingList **pp,               /* IN/OUT: PendingList structure */
+  sqlite3_int64 iDocid,           /* Docid for entry to add */
+  sqlite3_int64 iCol,             /* Column for entry to add */
+  sqlite3_int64 iPos,             /* Position of term for entry to add */
+  int *pRc                        /* OUT: Return code */
+){
+  PendingList *p = *pp;
+  int rc = SQLITE_OK;
+
+  assert( !p || p->iLastDocid<=iDocid );
+
+  if( !p || p->iLastDocid!=iDocid ){
+    sqlite3_int64 iDelta = iDocid - (p ? p->iLastDocid : 0);
+    if( p ){
+      assert( p->nData<p->nSpace );
+      assert( p->aData[p->nData]==0 );
+      p->nData++;
+    }
+    if( SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, iDelta)) ){
+      goto pendinglistappend_out;
+    }
+    p->iLastCol = -1;
+    p->iLastPos = 0;
+    p->iLastDocid = iDocid;
+  }
+  if( iCol>0 && p->iLastCol!=iCol ){
+    if( SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, 1))
+     || SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, iCol))
+    ){
+      goto pendinglistappend_out;
+    }
+    p->iLastCol = iCol;
+    p->iLastPos = 0;
+  }
+  if( iCol>=0 ){
+    assert( iPos>p->iLastPos || (iPos==0 && p->iLastPos==0) );
+    rc = fts3PendingListAppendVarint(&p, 2+iPos-p->iLastPos);
+    if( rc==SQLITE_OK ){
+      p->iLastPos = iPos;
+    }
+  }
+
+ pendinglistappend_out:
+  *pRc = rc;
+  if( p!=*pp ){
+    *pp = p;
+    return 1;
+  }
+  return 0;
+}
+
+/*
+** Tokenize the nul-terminated string zText and add all tokens to the
+** pending-terms hash-table. The docid used is that currently stored in
+** p->iPrevDocid, and the column is specified by argument iCol.
+**
+** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.
+*/
+static int fts3PendingTermsAdd(
+  Fts3Table *p,          /* FTS table into which text will be inserted */
+  const char *zText,     /* Text of document to be inseted */
+  int iCol,              /* Column number into which text is inserted */
+  u32 *pnWord            /* OUT: Number of tokens inserted */
+){
+  int rc;
+  int iStart;
+  int iEnd;
+  int iPos;
+  int nWord = 0;
+
+  char const *zToken;
+  int nToken;
+
+  sqlite3_tokenizer *pTokenizer = p->pTokenizer;
+  sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;
+  sqlite3_tokenizer_cursor *pCsr;
+  int (*xNext)(sqlite3_tokenizer_cursor *pCursor,
+      const char**,int*,int*,int*,int*);
+
+  assert( pTokenizer && pModule );
+
+  rc = pModule->xOpen(pTokenizer, zText, -1, &pCsr);
+  if( rc!=SQLITE_OK ){
+    return rc;
+  }
+  pCsr->pTokenizer = pTokenizer;
+
+  xNext = pModule->xNext;
+  while( SQLITE_OK==rc
+      && SQLITE_OK==(rc = xNext(pCsr, &zToken, &nToken, &iStart, &iEnd, &iPos))
+  ){
+    PendingList *pList;
+ 
+    if( iPos>=nWord ) nWord = iPos+1;
+
+    /* Positions cannot be negative; we use -1 as a terminator internally.
+    ** Tokens must have a non-zero length.
+    */
+    if( iPos<0 || !zToken || nToken<=0 ){
+      rc = SQLITE_ERROR;
+      break;
+    }
+
+    pList = (PendingList *)fts3HashFind(&p->pendingTerms, zToken, nToken);
+    if( pList ){
+      p->nPendingData -= (pList->nData + nToken + sizeof(Fts3HashElem));
+    }
+    if( fts3PendingListAppend(&pList, p->iPrevDocid, iCol, iPos, &rc) ){
+      if( pList==fts3HashInsert(&p->pendingTerms, zToken, nToken, pList) ){
+        /* Malloc failed while inserting the new entry. This can only 
+        ** happen if there was no previous entry for this token.
+        */
+        assert( 0==fts3HashFind(&p->pendingTerms, zToken, nToken) );
+        sqlite3_free(pList);
+        rc = SQLITE_NOMEM;
+      }
+    }
+    if( rc==SQLITE_OK ){
+      p->nPendingData += (pList->nData + nToken + sizeof(Fts3HashElem));
+    }
+  }
+
+  pModule->xClose(pCsr);
+  *pnWord = nWord;
+  return (rc==SQLITE_DONE ? SQLITE_OK : rc);
+}
+
+/* 
+** Calling this function indicates that subsequent calls to 
+** fts3PendingTermsAdd() are to add term/position-list pairs for the
+** contents of the document with docid iDocid.
+*/
+static int fts3PendingTermsDocid(Fts3Table *p, sqlite_int64 iDocid){
+  /* TODO(shess) Explore whether partially flushing the buffer on
+  ** forced-flush would provide better performance.  I suspect that if
+  ** we ordered the doclists by size and flushed the largest until the
+  ** buffer was half empty, that would let the less frequent terms
+  ** generate longer doclists.
+  */
+  if( iDocid<=p->iPrevDocid || p->nPendingData>p->nMaxPendingData ){
+    int rc = sqlite3Fts3PendingTermsFlush(p);
+    if( rc!=SQLITE_OK ) return rc;
+  }
+  p->iPrevDocid = iDocid;
+  return SQLITE_OK;
+}
+
+void sqlite3Fts3PendingTermsClear(Fts3Table *p){
+  Fts3HashElem *pElem;
+  for(pElem=fts3HashFirst(&p->pendingTerms); pElem; pElem=fts3HashNext(pElem)){
+    sqlite3_free(fts3HashData(pElem));
+  }
+  fts3HashClear(&p->pendingTerms);
+  p->nPendingData = 0;
+}
+
+/*
+** This function is called by the xUpdate() method as part of an INSERT
+** operation. It adds entries for each term in the new record to the
+** pendingTerms hash table.
+**
+** Argument apVal is the same as the similarly named argument passed to
+** fts3InsertData(). Parameter iDocid is the docid of the new row.
+*/
+static int fts3InsertTerms(Fts3Table *p, sqlite3_value **apVal, u32 *aSz){
+  int i;                          /* Iterator variable */
+  for(i=2; i<p->nColumn+2; i++){
+    const char *zText = (const char *)sqlite3_value_text(apVal[i]);
+    if( zText ){
+      int rc = fts3PendingTermsAdd(p, zText, i-2, &aSz[i-2]);
+      if( rc!=SQLITE_OK ){
+        return rc;
+      }
+    }
+  }
+  return SQLITE_OK;
+}
+
+/*
+** This function is called by the xUpdate() method for an INSERT operation.
+** The apVal parameter is passed a copy of the apVal argument passed by
+** SQLite to the xUpdate() method. i.e:
+**
+**   apVal[0]                Not used for INSERT.
+**   apVal[1]                rowid
+**   apVal[2]                Left-most user-defined column
+**   ...
+**   apVal[p->nColumn+1]     Right-most user-defined column
+**   apVal[p->nColumn+2]     Hidden column with same name as table
+**   apVal[p->nColumn+3]     Hidden "docid" column (alias for rowid)
+*/
+static int fts3InsertData(
+  Fts3Table *p,                   /* Full-text table */
+  sqlite3_value **apVal,          /* Array of values to insert */
+  sqlite3_int64 *piDocid          /* OUT: Docid for row just inserted */
+){
+  int rc;                         /* Return code */
+  sqlite3_stmt *pContentInsert;   /* INSERT INTO %_content VALUES(...) */
+
+  /* Locate the statement handle used to insert data into the %_content
+  ** table. The SQL for this statement is:
+  **
+  **   INSERT INTO %_content VALUES(?, ?, ?, ...)
+  **
+  ** The statement features N '?' variables, where N is the number of user
+  ** defined columns in the FTS3 table, plus one for the docid field.
+  */
+  rc = fts3SqlStmt(p, SQL_CONTENT_INSERT, &pContentInsert, &apVal[1]);
+  if( rc!=SQLITE_OK ){
+    return rc;
+  }
+
+  /* There is a quirk here. The users INSERT statement may have specified
+  ** a value for the "rowid" field, for the "docid" field, or for both.
+  ** Which is a problem, since "rowid" and "docid" are aliases for the
+  ** same value. For example:
+  **
+  **   INSERT INTO fts3tbl(rowid, docid) VALUES(1, 2);
+  **
+  ** In FTS3, this is an error. It is an error to specify non-NULL values
+  ** for both docid and some other rowid alias.
+  */
+  if( SQLITE_NULL!=sqlite3_value_type(apVal[3+p->nColumn]) ){
+    if( SQLITE_NULL==sqlite3_value_type(apVal[0])
+     && SQLITE_NULL!=sqlite3_value_type(apVal[1])
+    ){
+      /* A rowid/docid conflict. */
+      return SQLITE_ERROR;
+    }
+    rc = sqlite3_bind_value(pContentInsert, 1, apVal[3+p->nColumn]);
+    if( rc!=SQLITE_OK ) return rc;
+  }
+
+  /* Execute the statement to insert the record. Set *piDocid to the 
+  ** new docid value. 
+  */
+  sqlite3_step(pContentInsert);
+  rc = sqlite3_reset(pContentInsert);
+
+  *piDocid = sqlite3_last_insert_rowid(p->db);
+  return rc;
+}
+
+
+
+/*
+** Remove all data from the FTS3 table. Clear the hash table containing
+** pending terms.
+*/
+static int fts3DeleteAll(Fts3Table *p){
+  int rc = SQLITE_OK;             /* Return code */
+
+  /* Discard the contents of the pending-terms hash table. */
+  sqlite3Fts3PendingTermsClear(p);
+
+  /* Delete everything from the %_content, %_segments and %_segdir tables. */
+  fts3SqlExec(&rc, p, SQL_DELETE_ALL_CONTENT, 0);
+  fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGMENTS, 0);
+  fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGDIR, 0);
+  if( p->bHasDocsize ){
+    fts3SqlExec(&rc, p, SQL_DELETE_ALL_DOCSIZE, 0);
+    fts3SqlExec(&rc, p, SQL_DELETE_ALL_STAT, 0);
+  }
+  return rc;
+}
+
+/*
+** The first element in the apVal[] array is assumed to contain the docid
+** (an integer) of a row about to be deleted. Remove all terms from the
+** full-text index.
+*/
+static void fts3DeleteTerms(
+  int *pRC,               /* Result code */
+  Fts3Table *p,           /* The FTS table to delete from */
+  sqlite3_value **apVal,  /* apVal[] contains the docid to be deleted */
+  u32 *aSz                /* Sizes of deleted document written here */
+){
+  int rc;
+  sqlite3_stmt *pSelect;
+
+  if( *pRC ) return;
+  rc = fts3SqlStmt(p, SQL_SELECT_CONTENT_BY_ROWID, &pSelect, apVal);
+  if( rc==SQLITE_OK ){
+    if( SQLITE_ROW==sqlite3_step(pSelect) ){
+      int i;
+      for(i=1; i<=p->nColumn; i++){
+        const char *zText = (const char *)sqlite3_column_text(pSelect, i);
+        rc = fts3PendingTermsAdd(p, zText, -1, &aSz[i-1]);
+        if( rc!=SQLITE_OK ){
+          sqlite3_reset(pSelect);
+          *pRC = rc;
+          return;
+        }
+      }
+    }
+    rc = sqlite3_reset(pSelect);
+  }else{
+    sqlite3_reset(pSelect);
+  }
+  *pRC = rc;
+}
+
+/*
+** Forward declaration to account for the circular dependency between
+** functions fts3SegmentMerge() and fts3AllocateSegdirIdx().
+*/
+static int fts3SegmentMerge(Fts3Table *, int);
+
+/* 
+** This function allocates a new level iLevel index in the segdir table.
+** Usually, indexes are allocated within a level sequentially starting
+** with 0, so the allocated index is one greater than the value returned
+** by:
+**
+**   SELECT max(idx) FROM %_segdir WHERE level = :iLevel
+**
+** However, if there are already FTS3_MERGE_COUNT indexes at the requested
+** level, they are merged into a single level (iLevel+1) segment and the 
+** allocated index is 0.
+**
+** If successful, *piIdx is set to the allocated index slot and SQLITE_OK
+** returned. Otherwise, an SQLite error code is returned.
+*/
+static int fts3AllocateSegdirIdx(Fts3Table *p, int iLevel, int *piIdx){
+  int rc;                         /* Return Code */
+  sqlite3_stmt *pNextIdx;         /* Query for next idx at level iLevel */
+  int iNext = 0;                  /* Result of query pNextIdx */
+
+  /* Set variable iNext to the next available segdir index at level iLevel. */
+  rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pNextIdx, 0);
+  if( rc==SQLITE_OK ){
+    sqlite3_bind_int(pNextIdx, 1, iLevel);
+    if( SQLITE_ROW==sqlite3_step(pNextIdx) ){
+      iNext = sqlite3_column_int(pNextIdx, 0);
+    }
+    rc = sqlite3_reset(pNextIdx);
+  }
+
+  if( rc==SQLITE_OK ){
+    /* If iNext is FTS3_MERGE_COUNT, indicating that level iLevel is already
+    ** full, merge all segments in level iLevel into a single iLevel+1
+    ** segment and allocate (newly freed) index 0 at level iLevel. Otherwise,
+    ** if iNext is less than FTS3_MERGE_COUNT, allocate index iNext.
+    */
+    if( iNext>=FTS3_MERGE_COUNT ){
+      rc = fts3SegmentMerge(p, iLevel);
+      *piIdx = 0;
+    }else{
+      *piIdx = iNext;
+    }
+  }
+
+  return rc;
+}
+
+/*
+** Move the iterator passed as the first argument to the next term in the
+** segment. If successful, SQLITE_OK is returned. If there is no next term,
+** SQLITE_DONE. Otherwise, an SQLite error code.
+*/
+static int fts3SegReaderNext(Fts3SegReader *pReader){
+  char *pNext;                    /* Cursor variable */
+  int nPrefix;                    /* Number of bytes in term prefix */
+  int nSuffix;                    /* Number of bytes in term suffix */
+
+  if( !pReader->aDoclist ){
+    pNext = pReader->aNode;
+  }else{
+    pNext = &pReader->aDoclist[pReader->nDoclist];
+  }
+
+  if( !pNext || pNext>=&pReader->aNode[pReader->nNode] ){
+    int rc;
+    if( fts3SegReaderIsPending(pReader) ){
+      Fts3HashElem *pElem = *(pReader->ppNextElem);
+      if( pElem==0 ){
+        pReader->aNode = 0;
+      }else{
+        PendingList *pList = (PendingList *)fts3HashData(pElem);
+        pReader->zTerm = (char *)fts3HashKey(pElem);
+        pReader->nTerm = fts3HashKeysize(pElem);
+        pReader->nNode = pReader->nDoclist = pList->nData + 1;
+        pReader->aNode = pReader->aDoclist = pList->aData;
+        pReader->ppNextElem++;
+        assert( pReader->aNode );
+      }
+      return SQLITE_OK;
+    }
+    if( !pReader->pStmt ){
+      pReader->aNode = 0;
+      return SQLITE_OK;
+    }
+    rc = sqlite3_step(pReader->pStmt);
+    if( rc!=SQLITE_ROW ){
+      pReader->aNode = 0;
+      return (rc==SQLITE_DONE ? SQLITE_OK : rc);
+    }
+    pReader->nNode = sqlite3_column_bytes(pReader->pStmt, 0);
+    pReader->aNode = (char *)sqlite3_column_blob(pReader->pStmt, 0);
+    pNext = pReader->aNode;
+  }
+  
+  pNext += sqlite3Fts3GetVarint32(pNext, &nPrefix);
+  pNext += sqlite3Fts3GetVarint32(pNext, &nSuffix);
+
+  if( nPrefix+nSuffix>pReader->nTermAlloc ){
+    int nNew = (nPrefix+nSuffix)*2;
+    char *zNew = sqlite3_realloc(pReader->zTerm, nNew);
+    if( !zNew ){
+      return SQLITE_NOMEM;
+    }
+    pReader->zTerm = zNew;
+    pReader->nTermAlloc = nNew;
+  }
+  memcpy(&pReader->zTerm[nPrefix], pNext, nSuffix);
+  pReader->nTerm = nPrefix+nSuffix;
+  pNext += nSuffix;
+  pNext += sqlite3Fts3GetVarint32(pNext, &pReader->nDoclist);
+  assert( pNext<&pReader->aNode[pReader->nNode] );
+  pReader->aDoclist = pNext;
+  pReader->pOffsetList = 0;
+  return SQLITE_OK;
+}
+
+/*
+** Set the SegReader to point to the first docid in the doclist associated
+** with the current term.
+*/
+static void fts3SegReaderFirstDocid(Fts3SegReader *pReader){
+  int n;
+  assert( pReader->aDoclist );
+  assert( !pReader->pOffsetList );
+  n = sqlite3Fts3GetVarint(pReader->aDoclist, &pReader->iDocid);
+  pReader->pOffsetList = &pReader->aDoclist[n];
+}
+
+/*
+** Advance the SegReader to point to the next docid in the doclist
+** associated with the current term.
+** 
+** If arguments ppOffsetList and pnOffsetList are not NULL, then 
+** *ppOffsetList is set to point to the first column-offset list
+** in the doclist entry (i.e. immediately past the docid varint).
+** *pnOffsetList is set to the length of the set of column-offset
+** lists, not including the nul-terminator byte. For example:
+*/
+static void fts3SegReaderNextDocid(
+  Fts3SegReader *pReader,
+  char **ppOffsetList,
+  int *pnOffsetList
+){
+  char *p = pReader->pOffsetList;
+  char c = 0;
+
+  /* Pointer p currently points at the first byte of an offset list. The
+  ** following two lines advance it to point one byte past the end of
+  ** the same offset list.
+  */
+  while( *p | c ) c = *p++ & 0x80;
+  p++;
+
+  /* If required, populate the output variables with a pointer to and the
+  ** size of the previous offset-list.
+  */
+  if( ppOffsetList ){
+    *ppOffsetList = pReader->pOffsetList;
+    *pnOffsetList = (int)(p - pReader->pOffsetList - 1);
+  }
+
+  /* If there are no more entries in the doclist, set pOffsetList to
+  ** NULL. Otherwise, set Fts3SegReader.iDocid to the next docid and
+  ** Fts3SegReader.pOffsetList to point to the next offset list before
+  ** returning.
+  */
+  if( p>=&pReader->aDoclist[pReader->nDoclist] ){
+    pReader->pOffsetList = 0;
+  }else{
+    sqlite3_int64 iDelta;
+    pReader->pOffsetList = p + sqlite3Fts3GetVarint(p, &iDelta);
+    pReader->iDocid += iDelta;
+  }
+}
+
+/*
+** Free all allocations associated with the iterator passed as the 
+** second argument.
+*/
+void sqlite3Fts3SegReaderFree(Fts3Table *p, Fts3SegReader *pReader){
+  if( pReader ){
+    if( pReader->pStmt ){
+      /* Move the leaf-range SELECT statement to the aLeavesStmt[] array,
+      ** so that it can be reused when required by another query.
+      */
+      assert( p->nLeavesStmt<p->nLeavesTotal );
+      sqlite3_reset(pReader->pStmt);
+      p->aLeavesStmt[p->nLeavesStmt++] = pReader->pStmt;
+    }
+    if( !fts3SegReaderIsPending(pReader) ){
+      sqlite3_free(pReader->zTerm);
+    }
+    sqlite3_free(pReader);
+  }
+}
+
+/*
+** Allocate a new SegReader object.
+*/
+int sqlite3Fts3SegReaderNew(
+  Fts3Table *p,                   /* Virtual table handle */
+  int iAge,                       /* Segment "age". */
+  sqlite3_int64 iStartLeaf,       /* First leaf to traverse */
+  sqlite3_int64 iEndLeaf,         /* Final leaf to traverse */
+  sqlite3_int64 iEndBlock,        /* Final block of segment */
+  const char *zRoot,              /* Buffer containing root node */
+  int nRoot,                      /* Size of buffer containing root node */
+  Fts3SegReader **ppReader        /* OUT: Allocated Fts3SegReader */
+){
+  int rc = SQLITE_OK;             /* Return code */
+  Fts3SegReader *pReader;         /* Newly allocated SegReader object */
+  int nExtra = 0;                 /* Bytes to allocate segment root node */
+
+  if( iStartLeaf==0 ){
+    nExtra = nRoot;
+  }
+
+  pReader = (Fts3SegReader *)sqlite3_malloc(sizeof(Fts3SegReader) + nExtra);
+  if( !pReader ){
+    return SQLITE_NOMEM;
+  }
+  memset(pReader, 0, sizeof(Fts3SegReader));
+  pReader->iStartBlock = iStartLeaf;
+  pReader->iIdx = iAge;
+  pReader->iEndBlock = iEndBlock;
+
+  if( nExtra ){
+    /* The entire segment is stored in the root node. */
+    pReader->aNode = (char *)&pReader[1];
+    pReader->nNode = nRoot;
+    memcpy(pReader->aNode, zRoot, nRoot);
+  }else{
+    /* If the text of the SQL statement to iterate through a contiguous
+    ** set of entries in the %_segments table has not yet been composed,
+    ** compose it now.
+    */
+    if( !p->zSelectLeaves ){
+      p->zSelectLeaves = sqlite3_mprintf(
+          "SELECT block FROM %Q.'%q_segments' WHERE blockid BETWEEN ? AND ? "
+          "ORDER BY blockid", p->zDb, p->zName
+      );
+      if( !p->zSelectLeaves ){
+        rc = SQLITE_NOMEM;
+        goto finished;
+      }
+    }
+
+    /* If there are no free statements in the aLeavesStmt[] array, prepare
+    ** a new statement now. Otherwise, reuse a prepared statement from
+    ** aLeavesStmt[].
+    */
+    if( p->nLeavesStmt==0 ){
+      if( p->nLeavesTotal==p->nLeavesAlloc ){
+        int nNew = p->nLeavesAlloc + 16;
+        sqlite3_stmt **aNew = (sqlite3_stmt **)sqlite3_realloc(
+            p->aLeavesStmt, nNew*sizeof(sqlite3_stmt *)
+        );
+        if( !aNew ){
+          rc = SQLITE_NOMEM;
+          goto finished;
+        }
+        p->nLeavesAlloc = nNew;
+        p->aLeavesStmt = aNew;
+      }
+      rc = sqlite3_prepare_v2(p->db, p->zSelectLeaves, -1, &pReader->pStmt, 0);
+      if( rc!=SQLITE_OK ){
+        goto finished;
+      }
+      p->nLeavesTotal++;
+    }else{
+      pReader->pStmt = p->aLeavesStmt[--p->nLeavesStmt];
+    }
+
+    /* Bind the start and end leaf blockids to the prepared SQL statement. */
+    sqlite3_bind_int64(pReader->pStmt, 1, iStartLeaf);
+    sqlite3_bind_int64(pReader->pStmt, 2, iEndLeaf);
+  }
+  rc = fts3SegReaderNext(pReader);
+
+ finished:
+  if( rc==SQLITE_OK ){
+    *ppReader = pReader;
+  }else{
+    sqlite3Fts3SegReaderFree(p, pReader);
+  }
+  return rc;
+}
+
+/*
+** This is a comparison function used as a qsort() callback when sorting
+** an array of pending terms by term. This occurs as part of flushing
+** the contents of the pending-terms hash table to the database.
+*/
+static int fts3CompareElemByTerm(const void *lhs, const void *rhs){
+  char *z1 = fts3HashKey(*(Fts3HashElem **)lhs);
+  char *z2 = fts3HashKey(*(Fts3HashElem **)rhs);
+  int n1 = fts3HashKeysize(*(Fts3HashElem **)lhs);
+  int n2 = fts3HashKeysize(*(Fts3HashElem **)rhs);
+
+  int n = (n1<n2 ? n1 : n2);
+  int c = memcmp(z1, z2, n);
+  if( c==0 ){
+    c = n1 - n2;
+  }
+  return c;
+}
+
+/*
+** This function is used to allocate an Fts3SegReader that iterates through
+** a subset of the terms stored in the Fts3Table.pendingTerms array.
+*/
+int sqlite3Fts3SegReaderPending(
+  Fts3Table *p,                   /* Virtual table handle */
+  const char *zTerm,              /* Term to search for */
+  int nTerm,                      /* Size of buffer zTerm */
+  int isPrefix,                   /* True for a term-prefix query */
+  Fts3SegReader **ppReader        /* OUT: SegReader for pending-terms */
+){
+  Fts3SegReader *pReader = 0;     /* Fts3SegReader object to return */
+  Fts3HashElem **aElem = 0;       /* Array of term hash entries to scan */
+  int nElem = 0;                  /* Size of array at aElem */
+  int rc = SQLITE_OK;             /* Return Code */
+
+  if( isPrefix ){
+    int nAlloc = 0;               /* Size of allocated array at aElem */
+    Fts3HashElem *pE = 0;         /* Iterator variable */
+
+    for(pE=fts3HashFirst(&p->pendingTerms); pE; pE=fts3HashNext(pE)){
+      char *zKey = (char *)fts3HashKey(pE);
+      int nKey = fts3HashKeysize(pE);
+      if( nTerm==0 || (nKey>=nTerm && 0==memcmp(zKey, zTerm, nTerm)) ){
+        if( nElem==nAlloc ){
+          Fts3HashElem **aElem2;
+          nAlloc += 16;
+          aElem2 = (Fts3HashElem **)sqlite3_realloc(
+              aElem, nAlloc*sizeof(Fts3HashElem *)
+          );
+          if( !aElem2 ){
+            rc = SQLITE_NOMEM;
+            nElem = 0;
+            break;
+          }
+          aElem = aElem2;
+        }
+        aElem[nElem++] = pE;
+      }
+    }
+
+    /* If more than one term matches the prefix, sort the Fts3HashElem
+    ** objects in term order using qsort(). This uses the same comparison
+    ** callback as is used when flushing terms to disk.
+    */
+    if( nElem>1 ){
+      qsort(aElem, nElem, sizeof(Fts3HashElem *), fts3CompareElemByTerm);
+    }
+
+  }else{
+    Fts3HashElem *pE = fts3HashFindElem(&p->pendingTerms, zTerm, nTerm);
+    if( pE ){
+      aElem = &pE;
+      nElem = 1;
+    }
+  }
+
+  if( nElem>0 ){
+    int nByte = sizeof(Fts3SegReader) + (nElem+1)*sizeof(Fts3HashElem *);
+    pReader = (Fts3SegReader *)sqlite3_malloc(nByte);
+    if( !pReader ){
+      rc = SQLITE_NOMEM;
+    }else{
+      memset(pReader, 0, nByte);
+      pReader->iIdx = 0x7FFFFFFF;
+      pReader->ppNextElem = (Fts3HashElem **)&pReader[1];
+      memcpy(pReader->ppNextElem, aElem, nElem*sizeof(Fts3HashElem *));
+      fts3SegReaderNext(pReader);
+    }
+  }
+
+  if( isPrefix ){
+    sqlite3_free(aElem);
+  }
+  *ppReader = pReader;
+  return rc;
+}
+
+
+/*
+** The second argument to this function is expected to be a statement of
+** the form:
+**
+**   SELECT 
+**     idx,                  -- col 0
+**     start_block,          -- col 1
+**     leaves_end_block,     -- col 2
+**     end_block,            -- col 3
+**     root                  -- col 4
+**   FROM %_segdir ...
+**
+** This function allocates and initializes a Fts3SegReader structure to
+** iterate through the terms stored in the segment identified by the
+** current row that pStmt is pointing to. 
+**
+** If successful, the Fts3SegReader is left pointing to the first term
+** in the segment and SQLITE_OK is returned. Otherwise, an SQLite error
+** code is returned.
+*/
+static int fts3SegReaderNew(
+  Fts3Table *p,                   /* Virtual table handle */
+  sqlite3_stmt *pStmt,            /* See above */
+  int iAge,                       /* Segment "age". */
+  Fts3SegReader **ppReader        /* OUT: Allocated Fts3SegReader */
+){
+  return sqlite3Fts3SegReaderNew(p, iAge, 
+      sqlite3_column_int64(pStmt, 1),
+      sqlite3_column_int64(pStmt, 2),
+      sqlite3_column_int64(pStmt, 3),
+      sqlite3_column_blob(pStmt, 4),
+      sqlite3_column_bytes(pStmt, 4),
+      ppReader
+  );
+}
+
+/*
+** Compare the entries pointed to by two Fts3SegReader structures. 
+** Comparison is as follows:
+**
+**   1) EOF is greater than not EOF.
+**
+**   2) The current terms (if any) are compared using memcmp(). If one
+**      term is a prefix of another, the longer term is considered the
+**      larger.
+**
+**   3) By segment age. An older segment is considered larger.
+*/
+static int fts3SegReaderCmp(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
+  int rc;
+  if( pLhs->aNode && pRhs->aNode ){
+    int rc2 = pLhs->nTerm - pRhs->nTerm;
+    if( rc2<0 ){
+      rc = memcmp(pLhs->zTerm, pRhs->zTerm, pLhs->nTerm);
+    }else{
+      rc = memcmp(pLhs->zTerm, pRhs->zTerm, pRhs->nTerm);
+    }
+    if( rc==0 ){
+      rc = rc2;
+    }
+  }else{
+    rc = (pLhs->aNode==0) - (pRhs->aNode==0);
+  }
+  if( rc==0 ){
+    rc = pRhs->iIdx - pLhs->iIdx;
+  }
+  assert( rc!=0 );
+  return rc;
+}
+
+/*
+** A different comparison function for SegReader structures. In this
+** version, it is assumed that each SegReader points to an entry in
+** a doclist for identical terms. Comparison is made as follows:
+**
+**   1) EOF (end of doclist in this case) is greater than not EOF.
+**
+**   2) By current docid.
+**
+**   3) By segment age. An older segment is considered larger.
+*/
+static int fts3SegReaderDoclistCmp(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
+  int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);
+  if( rc==0 ){
+    if( pLhs->iDocid==pRhs->iDocid ){
+      rc = pRhs->iIdx - pLhs->iIdx;
+    }else{
+      rc = (pLhs->iDocid > pRhs->iDocid) ? 1 : -1;
+    }
+  }
+  assert( pLhs->aNode && pRhs->aNode );
+  return rc;
+}
+
+/*
+** Compare the term that the Fts3SegReader object passed as the first argument
+** points to with the term specified by arguments zTerm and nTerm. 
+**
+** If the pSeg iterator is already at EOF, return 0. Otherwise, return
+** -ve if the pSeg term is less than zTerm/nTerm, 0 if the two terms are
+** equal, or +ve if the pSeg term is greater than zTerm/nTerm.
+*/
+static int fts3SegReaderTermCmp(
+  Fts3SegReader *pSeg,            /* Segment reader object */
+  const char *zTerm,              /* Term to compare to */
+  int nTerm                       /* Size of term zTerm in bytes */
+){
+  int res = 0;
+  if( pSeg->aNode ){
+    if( pSeg->nTerm>nTerm ){
+      res = memcmp(pSeg->zTerm, zTerm, nTerm);
+    }else{
+      res = memcmp(pSeg->zTerm, zTerm, pSeg->nTerm);
+    }
+    if( res==0 ){
+      res = pSeg->nTerm-nTerm;
+    }
+  }
+  return res;
+}
+
+/*
+** Argument apSegment is an array of nSegment elements. It is known that
+** the final (nSegment-nSuspect) members are already in sorted order
+** (according to the comparison function provided). This function shuffles
+** the array around until all entries are in sorted order.
+*/
+static void fts3SegReaderSort(
+  Fts3SegReader **apSegment,                     /* Array to sort entries of */
+  int nSegment,                                  /* Size of apSegment array */
+  int nSuspect,                                  /* Unsorted entry count */
+  int (*xCmp)(Fts3SegReader *, Fts3SegReader *)  /* Comparison function */
+){
+  int i;                          /* Iterator variable */
+
+  assert( nSuspect<=nSegment );
+
+  if( nSuspect==nSegment ) nSuspect--;
+  for(i=nSuspect-1; i>=0; i--){
+    int j;
+    for(j=i; j<(nSegment-1); j++){
+      Fts3SegReader *pTmp;
+      if( xCmp(apSegment[j], apSegment[j+1])<0 ) break;
+      pTmp = apSegment[j+1];
+      apSegment[j+1] = apSegment[j];
+      apSegment[j] = pTmp;
+    }
+  }
+
+#ifndef NDEBUG
+  /* Check that the list really is sorted now. */
+  for(i=0; i<(nSuspect-1); i++){
+    assert( xCmp(apSegment[i], apSegment[i+1])<0 );
+  }
+#endif
+}
+
+/* 
+** Insert a record into the %_segments table.
+*/
+static int fts3WriteSegment(
+  Fts3Table *p,                   /* Virtual table handle */
+  sqlite3_int64 iBlock,           /* Block id for new block */
+  char *z,                        /* Pointer to buffer containing block data */
+  int n                           /* Size of buffer z in bytes */
+){
+  sqlite3_stmt *pStmt;
+  int rc = fts3SqlStmt(p, SQL_INSERT_SEGMENTS, &pStmt, 0);
+  if( rc==SQLITE_OK ){
+    sqlite3_bind_int64(pStmt, 1, iBlock);
+    sqlite3_bind_blob(pStmt, 2, z, n, SQLITE_STATIC);
+    sqlite3_step(pStmt);
+    rc = sqlite3_reset(pStmt);
+  }
+  return rc;
+}
+
+/* 
+** Insert a record into the %_segdir table.
+*/
+static int fts3WriteSegdir(
+  Fts3Table *p,                   /* Virtual table handle */
+  int iLevel,                     /* Value for "level" field */
+  int iIdx,                       /* Value for "idx" field */
+  sqlite3_int64 iStartBlock,      /* Value for "start_block" field */
+  sqlite3_int64 iLeafEndBlock,    /* Value for "leaves_end_block" field */
+  sqlite3_int64 iEndBlock,        /* Value for "end_block" field */
+  char *zRoot,                    /* Blob value for "root" field */
+  int nRoot                       /* Number of bytes in buffer zRoot */
+){
+  sqlite3_stmt *pStmt;
+  int rc = fts3SqlStmt(p, SQL_INSERT_SEGDIR, &pStmt, 0);
+  if( rc==SQLITE_OK ){
+    sqlite3_bind_int(pStmt, 1, iLevel);
+    sqlite3_bind_int(pStmt, 2, iIdx);
+    sqlite3_bind_int64(pStmt, 3, iStartBlock);
+    sqlite3_bind_int64(pStmt, 4, iLeafEndBlock);
+    sqlite3_bind_int64(pStmt, 5, iEndBlock);
+    sqlite3_bind_blob(pStmt, 6, zRoot, nRoot, SQLITE_STATIC);
+    sqlite3_step(pStmt);
+    rc = sqlite3_reset(pStmt);
+  }
+  return rc;
+}
+
+/*
+** Return the size of the common prefix (if any) shared by zPrev and
+** zNext, in bytes. For example, 
+**
+**   fts3PrefixCompress("abc", 3, "abcdef", 6)   // returns 3
+**   fts3PrefixCompress("abX", 3, "abcdef", 6)   // returns 2
+**   fts3PrefixCompress("abX", 3, "Xbcdef", 6)   // returns 0
+*/
+static int fts3PrefixCompress(
+  const char *zPrev,              /* Buffer containing previous term */
+  int nPrev,                      /* Size of buffer zPrev in bytes */
+  const char *zNext,              /* Buffer containing next term */
+  int nNext                       /* Size of buffer zNext in bytes */
+){
+  int n;
+  UNUSED_PARAMETER(nNext);
+  for(n=0; n<nPrev && zPrev[n]==zNext[n]; n++);
+  return n;
+}
+
+/*
+** Add term zTerm to the SegmentNode. It is guaranteed that zTerm is larger
+** (according to memcmp) than the previous term.
+*/
+static int fts3NodeAddTerm(
+  Fts3Table *p,               /* Virtual table handle */
+  SegmentNode **ppTree,           /* IN/OUT: SegmentNode handle */ 
+  int isCopyTerm,                 /* True if zTerm/nTerm is transient */
+  const char *zTerm,              /* Pointer to buffer containing term */
+  int nTerm                       /* Size of term in bytes */
+){
+  SegmentNode *pTree = *ppTree;
+  int rc;
+  SegmentNode *pNew;
+
+  /* First try to append the term to the current node. Return early if 
+  ** this is possible.
+  */
+  if( pTree ){
+    int nData = pTree->nData;     /* Current size of node in bytes */
+    int nReq = nData;             /* Required space after adding zTerm */
+    int nPrefix;                  /* Number of bytes of prefix compression */
+    int nSuffix;                  /* Suffix length */
+
+    nPrefix = fts3PrefixCompress(pTree->zTerm, pTree->nTerm, zTerm, nTerm);
+    nSuffix = nTerm-nPrefix;
+
+    nReq += sqlite3Fts3VarintLen(nPrefix)+sqlite3Fts3VarintLen(nSuffix)+nSuffix;
+    if( nReq<=p->nNodeSize || !pTree->zTerm ){
+
+      if( nReq>p->nNodeSize ){
+        /* An unusual case: this is the first term to be added to the node
+        ** and the static node buffer (p->nNodeSize bytes) is not large
+        ** enough. Use a separately malloced buffer instead This wastes
+        ** p->nNodeSize bytes, but since this scenario only comes about when
+        ** the database contain two terms that share a prefix of almost 2KB, 
+        ** this is not expected to be a serious problem. 
+        */
+        assert( pTree->aData==(char *)&pTree[1] );
+        pTree->aData = (char *)sqlite3_malloc(nReq);
+        if( !pTree->aData ){
+          return SQLITE_NOMEM;
+        }
+      }
+
+      if( pTree->zTerm ){
+        /* There is no prefix-length field for first term in a node */
+        nData += sqlite3Fts3PutVarint(&pTree->aData[nData], nPrefix);
+      }
+
+      nData += sqlite3Fts3PutVarint(&pTree->aData[nData], nSuffix);
+      memcpy(&pTree->aData[nData], &zTerm[nPrefix], nSuffix);
+      pTree->nData = nData + nSuffix;
+      pTree->nEntry++;
+
+      if( isCopyTerm ){
+        if( pTree->nMalloc<nTerm ){
+          char *zNew = sqlite3_realloc(pTree->zMalloc, nTerm*2);
+          if( !zNew ){
+            return SQLITE_NOMEM;
+          }
+          pTree->nMalloc = nTerm*2;
+          pTree->zMalloc = zNew;
+        }
+        pTree->zTerm = pTree->zMalloc;
+        memcpy(pTree->zTerm, zTerm, nTerm);
+        pTree->nTerm = nTerm;
+      }else{
+        pTree->zTerm = (char *)zTerm;
+        pTree->nTerm = nTerm;
+      }
+      return SQLITE_OK;
+    }
+  }
+
+  /* If control flows to here, it was not possible to append zTerm to the
+  ** current node. Create a new node (a right-sibling of the current node).
+  ** If this is the first node in the tree, the term is added to it.
+  **
+  ** Otherwise, the term is not added to the new node, it is left empty for
+  ** now. Instead, the term is inserted into the parent of pTree. If pTree 
+  ** has no parent, one is created here.
+  */
+  pNew = (SegmentNode *)sqlite3_malloc(sizeof(SegmentNode) + p->nNodeSize);
+  if( !pNew ){
+    return SQLITE_NOMEM;
+  }
+  memset(pNew, 0, sizeof(SegmentNode));
+  pNew->nData = 1 + FTS3_VARINT_MAX;
+  pNew->aData = (char *)&pNew[1];
+
+  if( pTree ){
+    SegmentNode *pParent = pTree->pParent;
+    rc = fts3NodeAddTerm(p, &pParent, isCopyTerm, zTerm, nTerm);
+    if( pTree->pParent==0 ){
+      pTree->pParent = pParent;
+    }
+    pTree->pRight = pNew;
+    pNew->pLeftmost = pTree->pLeftmost;
+    pNew->pParent = pParent;
+    pNew->zMalloc = pTree->zMalloc;
+    pNew->nMalloc = pTree->nMalloc;
+    pTree->zMalloc = 0;
+  }else{
+    pNew->pLeftmost = pNew;
+    rc = fts3NodeAddTerm(p, &pNew, isCopyTerm, zTerm, nTerm); 
+  }
+
+  *ppTree = pNew;
+  return rc;
+}
+
+/*
+** Helper function for fts3NodeWrite().
+*/
+static int fts3TreeFinishNode(
+  SegmentNode *pTree, 
+  int iHeight, 
+  sqlite3_int64 iLeftChild
+){
+  int nStart;
+  assert( iHeight>=1 && iHeight<128 );
+  nStart = FTS3_VARINT_MAX - sqlite3Fts3VarintLen(iLeftChild);
+  pTree->aData[nStart] = (char)iHeight;
+  sqlite3Fts3PutVarint(&pTree->aData[nStart+1], iLeftChild);
+  return nStart;
+}
+
+/*
+** Write the buffer for the segment node pTree and all of its peers to the
+** database. Then call this function recursively to write the parent of 
+** pTree and its peers to the database. 
+**
+** Except, if pTree is a root node, do not write it to the database. Instead,
+** set output variables *paRoot and *pnRoot to contain the root node.
+**
+** If successful, SQLITE_OK is returned and output variable *piLast is
+** set to the largest blockid written to the database (or zero if no
+** blocks were written to the db). Otherwise, an SQLite error code is 
+** returned.
+*/
+static int fts3NodeWrite(
+  Fts3Table *p,                   /* Virtual table handle */
+  SegmentNode *pTree,             /* SegmentNode handle */
+  int iHeight,                    /* Height of this node in tree */
+  sqlite3_int64 iLeaf,            /* Block id of first leaf node */
+  sqlite3_int64 iFree,            /* Block id of next free slot in %_segments */
+  sqlite3_int64 *piLast,          /* OUT: Block id of last entry written */
+  char **paRoot,                  /* OUT: Data for root node */
+  int *pnRoot                     /* OUT: Size of root node in bytes */
+){
+  int rc = SQLITE_OK;
+
+  if( !pTree->pParent ){
+    /* Root node of the tree. */
+    int nStart = fts3TreeFinishNode(pTree, iHeight, iLeaf);
+    *piLast = iFree-1;
+    *pnRoot = pTree->nData - nStart;
+    *paRoot = &pTree->aData[nStart];
+  }else{
+    SegmentNode *pIter;
+    sqlite3_int64 iNextFree = iFree;
+    sqlite3_int64 iNextLeaf = iLeaf;
+    for(pIter=pTree->pLeftmost; pIter && rc==SQLITE_OK; pIter=pIter->pRight){
+      int nStart = fts3TreeFinishNode(pIter, iHeight, iNextLeaf);
+      int nWrite = pIter->nData - nStart;
+  
+      rc = fts3WriteSegment(p, iNextFree, &pIter->aData[nStart], nWrite);
+      iNextFree++;
+      iNextLeaf += (pIter->nEntry+1);
+    }
+    if( rc==SQLITE_OK ){
+      assert( iNextLeaf==iFree );
+      rc = fts3NodeWrite(
+          p, pTree->pParent, iHeight+1, iFree, iNextFree, piLast, paRoot, pnRoot
+      );
+    }
+  }
+
+  return rc;
+}
+
+/*
+** Free all memory allocations associated with the tree pTree.
+*/
+static void fts3NodeFree(SegmentNode *pTree){
+  if( pTree ){
+    SegmentNode *p = pTree->pLeftmost;
+    fts3NodeFree(p->pParent);
+    while( p ){
+      SegmentNode *pRight = p->pRight;
+      if( p->aData!=(char *)&p[1] ){
+        sqlite3_free(p->aData);
+      }
+      assert( pRight==0 || p->zMalloc==0 );
+      sqlite3_free(p->zMalloc);
+      sqlite3_free(p);
+      p = pRight;
+    }
+  }
+}
+
+/*
+** Add a term to the segment being constructed by the SegmentWriter object
+** *ppWriter. When adding the first term to a segment, *ppWriter should
+** be passed NULL. This function will allocate a new SegmentWriter object
+** and return it via the input/output variable *ppWriter in this case.
+**
+** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.
+*/
+static int fts3SegWriterAdd(
+  Fts3Table *p,                   /* Virtual table handle */
+  SegmentWriter **ppWriter,       /* IN/OUT: SegmentWriter handle */ 
+  int isCopyTerm,                 /* True if buffer zTerm must be copied */
+  const char *zTerm,              /* Pointer to buffer containing term */
+  int nTerm,                      /* Size of term in bytes */
+  const char *aDoclist,           /* Pointer to buffer containing doclist */
+  int nDoclist                    /* Size of doclist in bytes */
+){
+  int nPrefix;                    /* Size of term prefix in bytes */
+  int nSuffix;                    /* Size of term suffix in bytes */
+  int nReq;                       /* Number of bytes required on leaf page */
+  int nData;
+  SegmentWriter *pWriter = *ppWriter;
+
+  if( !pWriter ){
+    int rc;
+    sqlite3_stmt *pStmt;
+
+    /* Allocate the SegmentWriter structure */
+    pWriter = (SegmentWriter *)sqlite3_malloc(sizeof(SegmentWriter));
+    if( !pWriter ) return SQLITE_NOMEM;
+    memset(pWriter, 0, sizeof(SegmentWriter));
+    *ppWriter = pWriter;
+
+    /* Allocate a buffer in which to accumulate data */
+    pWriter->aData = (char *)sqlite3_malloc(p->nNodeSize);
+    if( !pWriter->aData ) return SQLITE_NOMEM;
+    pWriter->nSize = p->nNodeSize;
+
+    /* Find the next free blockid in the %_segments table */
+    rc = fts3SqlStmt(p, SQL_NEXT_SEGMENTS_ID, &pStmt, 0);
+    if( rc!=SQLITE_OK ) return rc;
+    if( SQLITE_ROW==sqlite3_step(pStmt) ){
+      pWriter->iFree = sqlite3_column_int64(pStmt, 0);
+      pWriter->iFirst = pWriter->iFree;
+    }
+    rc = sqlite3_reset(pStmt);
+    if( rc!=SQLITE_OK ) return rc;
+  }
+  nData = pWriter->nData;
+
+  nPrefix = fts3PrefixCompress(pWriter->zTerm, pWriter->nTerm, zTerm, nTerm);
+  nSuffix = nTerm-nPrefix;
+
+  /* Figure out how many bytes are required by this new entry */
+  nReq = sqlite3Fts3VarintLen(nPrefix) +    /* varint containing prefix size */
+    sqlite3Fts3VarintLen(nSuffix) +         /* varint containing suffix size */
+    nSuffix +                               /* Term suffix */
+    sqlite3Fts3VarintLen(nDoclist) +        /* Size of doclist */
+    nDoclist;                               /* Doclist data */
+
+  if( nData>0 && nData+nReq>p->nNodeSize ){
+    int rc;
+
+    /* The current leaf node is full. Write it out to the database. */
+    rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, nData);
+    if( rc!=SQLITE_OK ) return rc;
+
+    /* Add the current term to the interior node tree. The term added to
+    ** the interior tree must:
+    **
+    **   a) be greater than the largest term on the leaf node just written
+    **      to the database (still available in pWriter->zTerm), and
+    **
+    **   b) be less than or equal to the term about to be added to the new
+    **      leaf node (zTerm/nTerm).
+    **
+    ** In other words, it must be the prefix of zTerm 1 byte longer than
+    ** the common prefix (if any) of zTerm and pWriter->zTerm.
+    */
+    assert( nPrefix<nTerm );
+    rc = fts3NodeAddTerm(p, &pWriter->pTree, isCopyTerm, zTerm, nPrefix+1);
+    if( rc!=SQLITE_OK ) return rc;
+
+    nData = 0;
+    pWriter->nTerm = 0;
+
+    nPrefix = 0;
+    nSuffix = nTerm;
+    nReq = 1 +                              /* varint containing prefix size */
+      sqlite3Fts3VarintLen(nTerm) +         /* varint containing suffix size */
+      nTerm +                               /* Term suffix */
+      sqlite3Fts3VarintLen(nDoclist) +      /* Size of doclist */
+      nDoclist;                             /* Doclist data */
+  }
+
+  /* If the buffer currently allocated is too small for this entry, realloc
+  ** the buffer to make it large enough.
+  */
+  if( nReq>pWriter->nSize ){
+    char *aNew = sqlite3_realloc(pWriter->aData, nReq);
+    if( !aNew ) return SQLITE_NOMEM;
+    pWriter->aData = aNew;
+    pWriter->nSize = nReq;
+  }
+  assert( nData+nReq<=pWriter->nSize );
+
+  /* Append the prefix-compressed term and doclist to the buffer. */
+  nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nPrefix);
+  nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nSuffix);
+  memcpy(&pWriter->aData[nData], &zTerm[nPrefix], nSuffix);
+  nData += nSuffix;
+  nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nDoclist);
+  memcpy(&pWriter->aData[nData], aDoclist, nDoclist);
+  pWriter->nData = nData + nDoclist;
+
+  /* Save the current term so that it can be used to prefix-compress the next.
+  ** If the isCopyTerm parameter is true, then the buffer pointed to by
+  ** zTerm is transient, so take a copy of the term data. Otherwise, just
+  ** store a copy of the pointer.
+  */
+  if( isCopyTerm ){
+    if( nTerm>pWriter->nMalloc ){
+      char *zNew = sqlite3_realloc(pWriter->zMalloc, nTerm*2);
+      if( !zNew ){
+        return SQLITE_NOMEM;
+      }
+      pWriter->nMalloc = nTerm*2;
+      pWriter->zMalloc = zNew;
+      pWriter->zTerm = zNew;
+    }
+    assert( pWriter->zTerm==pWriter->zMalloc );
+    memcpy(pWriter->zTerm, zTerm, nTerm);
+  }else{
+    pWriter->zTerm = (char *)zTerm;
+  }
+  pWriter->nTerm = nTerm;
+
+  return SQLITE_OK;
+}
+
+/*
+** Flush all data associated with the SegmentWriter object pWriter to the
+** database. This function must be called after all terms have been added
+** to the segment using fts3SegWriterAdd(). If successful, SQLITE_OK is
+** returned. Otherwise, an SQLite error code.
+*/
+static int fts3SegWriterFlush(
+  Fts3Table *p,                   /* Virtual table handle */
+  SegmentWriter *pWriter,         /* SegmentWriter to flush to the db */
+  int iLevel,                     /* Value for 'level' column of %_segdir */
+  int iIdx                        /* Value for 'idx' column of %_segdir */
+){
+  int rc;                         /* Return code */
+  if( pWriter->pTree ){
+    sqlite3_int64 iLast = 0;      /* Largest block id written to database */
+    sqlite3_int64 iLastLeaf;      /* Largest leaf block id written to db */
+    char *zRoot = NULL;           /* Pointer to buffer containing root node */
+    int nRoot = 0;                /* Size of buffer zRoot */
+
+    iLastLeaf = pWriter->iFree;
+    rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, pWriter->nData);
+    if( rc==SQLITE_OK ){
+      rc = fts3NodeWrite(p, pWriter->pTree, 1,
+          pWriter->iFirst, pWriter->iFree, &iLast, &zRoot, &nRoot);
+    }
+    if( rc==SQLITE_OK ){
+      rc = fts3WriteSegdir(
+          p, iLevel, iIdx, pWriter->iFirst, iLastLeaf, iLast, zRoot, nRoot);
+    }
+  }else{
+    /* The entire tree fits on the root node. Write it to the segdir table. */
+    rc = fts3WriteSegdir(
+        p, iLevel, iIdx, 0, 0, 0, pWriter->aData, pWriter->nData);
+  }
+  return rc;
+}
+
+/*
+** Release all memory held by the SegmentWriter object passed as the 
+** first argument.
+*/
+static void fts3SegWriterFree(SegmentWriter *pWriter){
+  if( pWriter ){
+    sqlite3_free(pWriter->aData);
+    sqlite3_free(pWriter->zMalloc);
+    fts3NodeFree(pWriter->pTree);
+    sqlite3_free(pWriter);
+  }
+}
+
+/*
+** The first value in the apVal[] array is assumed to contain an integer.
+** This function tests if there exist any documents with docid values that
+** are different from that integer. i.e. if deleting the document with docid
+** apVal[0] would mean the FTS3 table were empty.
+**
+** If successful, *pisEmpty is set to true if the table is empty except for
+** document apVal[0], or false otherwise, and SQLITE_OK is returned. If an
+** error occurs, an SQLite error code is returned.
+*/
+static int fts3IsEmpty(Fts3Table *p, sqlite3_value **apVal, int *pisEmpty){
+  sqlite3_stmt *pStmt;
+  int rc;
+  rc = fts3SqlStmt(p, SQL_IS_EMPTY, &pStmt, apVal);
+  if( rc==SQLITE_OK ){
+    if( SQLITE_ROW==sqlite3_step(pStmt) ){
+      *pisEmpty = sqlite3_column_int(pStmt, 0);
+    }
+    rc = sqlite3_reset(pStmt);
+  }
+  return rc;
+}
+
+/*
+** Set *pnSegment to the number of segments of level iLevel in the database.
+**
+** Return SQLITE_OK if successful, or an SQLite error code if not.
+*/
+static int fts3SegmentCount(Fts3Table *p, int iLevel, int *pnSegment){
+  sqlite3_stmt *pStmt;
+  int rc;
+
+  assert( iLevel>=0 );
+  rc = fts3SqlStmt(p, SQL_SELECT_LEVEL_COUNT, &pStmt, 0);
+  if( rc!=SQLITE_OK ) return rc;
+  sqlite3_bind_int(pStmt, 1, iLevel);
+  if( SQLITE_ROW==sqlite3_step(pStmt) ){
+    *pnSegment = sqlite3_column_int(pStmt, 0);
+  }
+  return sqlite3_reset(pStmt);
+}
+
+/*
+** Set *pnSegment to the total number of segments in the database. Set
+** *pnMax to the largest segment level in the database (segment levels
+** are stored in the 'level' column of the %_segdir table).
+**
+** Return SQLITE_OK if successful, or an SQLite error code if not.
+*/
+static int fts3SegmentCountMax(Fts3Table *p, int *pnSegment, int *pnMax){
+  sqlite3_stmt *pStmt;
+  int rc;
+
+  rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR_COUNT_MAX, &pStmt, 0);
+  if( rc!=SQLITE_OK ) return rc;
+  if( SQLITE_ROW==sqlite3_step(pStmt) ){
+    *pnSegment = sqlite3_column_int(pStmt, 0);
+    *pnMax = sqlite3_column_int(pStmt, 1);
+  }
+  return sqlite3_reset(pStmt);
+}
+
+/*
+** This function is used after merging multiple segments into a single large
+** segment to delete the old, now redundant, segment b-trees. Specifically,
+** it:
+** 
+**   1) Deletes all %_segments entries for the segments associated with 
+**      each of the SegReader objects in the array passed as the third 
+**      argument, and
+**
+**   2) deletes all %_segdir entries with level iLevel, or all %_segdir
+**      entries regardless of level if (iLevel<0).
+**
+** SQLITE_OK is returned if successful, otherwise an SQLite error code.
+*/
+static int fts3DeleteSegdir(
+  Fts3Table *p,                   /* Virtual table handle */
+  int iLevel,                     /* Level of %_segdir entries to delete */
+  Fts3SegReader **apSegment,      /* Array of SegReader objects */
+  int nReader                     /* Size of array apSegment */
+){
+  int rc;                         /* Return Code */
+  int i;                          /* Iterator variable */
+  sqlite3_stmt *pDelete;          /* SQL statement to delete rows */
+
+  rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDelete, 0);
+  for(i=0; rc==SQLITE_OK && i<nReader; i++){
+    Fts3SegReader *pSegment = apSegment[i];
+    if( pSegment->iStartBlock ){
+      sqlite3_bind_int64(pDelete, 1, pSegment->iStartBlock);
+      sqlite3_bind_int64(pDelete, 2, pSegment->iEndBlock);
+      sqlite3_step(pDelete);
+      rc = sqlite3_reset(pDelete);
+    }
+  }
+  if( rc!=SQLITE_OK ){
+    return rc;
+  }
+
+  if( iLevel>=0 ){
+    rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_BY_LEVEL, &pDelete, 0);
+    if( rc==SQLITE_OK ){
+      sqlite3_bind_int(pDelete, 1, iLevel);
+      sqlite3_step(pDelete);
+      rc = sqlite3_reset(pDelete);
+    }
+  }else{
+    fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGDIR, 0);
+  }
+
+  return rc;
+}
+
+/*
+** When this function is called, buffer *ppList (size *pnList bytes) contains 
+** a position list that may (or may not) feature multiple columns. This
+** function adjusts the pointer *ppList and the length *pnList so that they
+** identify the subset of the position list that corresponds to column iCol.
+**
+** If there are no entries in the input position list for column iCol, then
+** *pnList is set to zero before returning.
+*/
+static void fts3ColumnFilter(
+  int iCol,                       /* Column to filter on */
+  char **ppList,                  /* IN/OUT: Pointer to position list */
+  int *pnList                     /* IN/OUT: Size of buffer *ppList in bytes */
+){
+  char *pList = *ppList;
+  int nList = *pnList;
+  char *pEnd = &pList[nList];
+  int iCurrent = 0;
+  char *p = pList;
+
+  assert( iCol>=0 );
+  while( 1 ){
+    char c = 0;
+    while( p<pEnd && (c | *p)&0xFE ) c = *p++ & 0x80;
+  
+    if( iCol==iCurrent ){
+      nList = (int)(p - pList);
+      break;
+    }
+
+    nList -= (int)(p - pList);
+    pList = p;
+    if( nList==0 ){
+      break;
+    }
+    p = &pList[1];
+    p += sqlite3Fts3GetVarint32(p, &iCurrent);
+  }
+
+  *ppList = pList;
+  *pnList = nList;
+}
+
+/*
+** sqlite3Fts3SegReaderIterate() callback used when merging multiple 
+** segments to create a single, larger segment.
+*/
+static int fts3MergeCallback(
+  Fts3Table *p,                   /* FTS3 Virtual table handle */
+  void *pContext,                 /* Pointer to SegmentWriter* to write with */
+  char *zTerm,                    /* Term to write to the db */
+  int nTerm,                      /* Number of bytes in zTerm */
+  char *aDoclist,                 /* Doclist associated with zTerm */
+  int nDoclist                    /* Number of bytes in doclist */
+){
+  SegmentWriter **ppW = (SegmentWriter **)pContext;
+  return fts3SegWriterAdd(p, ppW, 1, zTerm, nTerm, aDoclist, nDoclist);
+}
+
+/*
+** sqlite3Fts3SegReaderIterate() callback used when flushing the contents
+** of the pending-terms hash table to the database.
+*/
+static int fts3FlushCallback(
+  Fts3Table *p,                   /* FTS3 Virtual table handle */
+  void *pContext,                 /* Pointer to SegmentWriter* to write with */
+  char *zTerm,                    /* Term to write to the db */
+  int nTerm,                      /* Number of bytes in zTerm */
+  char *aDoclist,                 /* Doclist associated with zTerm */
+  int nDoclist                    /* Number of bytes in doclist */
+){
+  SegmentWriter **ppW = (SegmentWriter **)pContext;
+  return fts3SegWriterAdd(p, ppW, 0, zTerm, nTerm, aDoclist, nDoclist);
+}
+
+/*
+** This function is used to iterate through a contiguous set of terms 
+** stored in the full-text index. It merges data contained in one or 
+** more segments to support this.
+**
+** The second argument is passed an array of pointers to SegReader objects
+** allocated with sqlite3Fts3SegReaderNew(). This function merges the range 
+** of terms selected by each SegReader. If a single term is present in
+** more than one segment, the associated doclists are merged. For each
+** term and (possibly merged) doclist in the merged range, the callback
+** function xFunc is invoked with its arguments set as follows.
+**
+**   arg 0: Copy of 'p' parameter passed to this function
+**   arg 1: Copy of 'pContext' parameter passed to this function
+**   arg 2: Pointer to buffer containing term
+**   arg 3: Size of arg 2 buffer in bytes
+**   arg 4: Pointer to buffer containing doclist
+**   arg 5: Size of arg 2 buffer in bytes
+**
+** The 4th argument to this function is a pointer to a structure of type
+** Fts3SegFilter, defined in fts3Int.h. The contents of this structure
+** further restrict the range of terms that callbacks are made for and
+** modify the behaviour of this function. See comments above structure
+** definition for details.
+*/
+int sqlite3Fts3SegReaderIterate(
+  Fts3Table *p,                   /* Virtual table handle */
+  Fts3SegReader **apSegment,      /* Array of Fts3SegReader objects */
+  int nSegment,                   /* Size of apSegment array */
+  Fts3SegFilter *pFilter,         /* Restrictions on range of iteration */
+  int (*xFunc)(Fts3Table *, void *, char *, int, char *, int),  /* Callback */
+  void *pContext                  /* Callback context (2nd argument) */
+){
+  int i;                          /* Iterator variable */
+  char *aBuffer = 0;              /* Buffer to merge doclists in */
+  int nAlloc = 0;                 /* Allocated size of aBuffer buffer */
+  int rc = SQLITE_OK;             /* Return code */
+
+  int isIgnoreEmpty =  (pFilter->flags & FTS3_SEGMENT_IGNORE_EMPTY);
+  int isRequirePos =   (pFilter->flags & FTS3_SEGMENT_REQUIRE_POS);
+  int isColFilter =    (pFilter->flags & FTS3_SEGMENT_COLUMN_FILTER);
+  int isPrefix =       (pFilter->flags & FTS3_SEGMENT_PREFIX);
+
+  /* If there are zero segments, this function is a no-op. This scenario
+  ** comes about only when reading from an empty database.
+  */
+  if( nSegment==0 ) goto finished;
+
+  /* If the Fts3SegFilter defines a specific term (or term prefix) to search 
+  ** for, then advance each segment iterator until it points to a term of
+  ** equal or greater value than the specified term. This prevents many
+  ** unnecessary merge/sort operations for the case where single segment
+  ** b-tree leaf nodes contain more than one term.
+  */
+  if( pFilter->zTerm ){
+    int nTerm = pFilter->nTerm;
+    const char *zTerm = pFilter->zTerm;
+    for(i=0; i<nSegment; i++){
+      Fts3SegReader *pSeg = apSegment[i];
+      while( fts3SegReaderTermCmp(pSeg, zTerm, nTerm)<0 ){
+        rc = fts3SegReaderNext(pSeg);
+        if( rc!=SQLITE_OK ) goto finished; }
+    }
+  }
+
+  fts3SegReaderSort(apSegment, nSegment, nSegment, fts3SegReaderCmp);
+  while( apSegment[0]->aNode ){
+    int nTerm = apSegment[0]->nTerm;
+    char *zTerm = apSegment[0]->zTerm;
+    int nMerge = 1;
+
+    /* If this is a prefix-search, and if the term that apSegment[0] points
+    ** to does not share a suffix with pFilter->zTerm/nTerm, then all 
+    ** required callbacks have been made. In this case exit early.
+    **
+    ** Similarly, if this is a search for an exact match, and the first term
+    ** of segment apSegment[0] is not a match, exit early.
+    */
+    if( pFilter->zTerm ){
+      if( nTerm<pFilter->nTerm 
+       || (!isPrefix && nTerm>pFilter->nTerm)
+       || memcmp(zTerm, pFilter->zTerm, pFilter->nTerm) 
+    ){
+        goto finished;
+      }
+    }
+
+    while( nMerge<nSegment 
+        && apSegment[nMerge]->aNode
+        && apSegment[nMerge]->nTerm==nTerm 
+        && 0==memcmp(zTerm, apSegment[nMerge]->zTerm, nTerm)
+    ){
+      nMerge++;
+    }
+
+    assert( isIgnoreEmpty || (isRequirePos && !isColFilter) );
+    if( nMerge==1 && !isIgnoreEmpty ){
+      Fts3SegReader *p0 = apSegment[0];
+      rc = xFunc(p, pContext, zTerm, nTerm, p0->aDoclist, p0->nDoclist);
+      if( rc!=SQLITE_OK ) goto finished;
+    }else{
+      int nDoclist = 0;           /* Size of doclist */
+      sqlite3_int64 iPrev = 0;    /* Previous docid stored in doclist */
+
+      /* The current term of the first nMerge entries in the array
+      ** of Fts3SegReader objects is the same. The doclists must be merged
+      ** and a single term added to the new segment.
+      */
+      for(i=0; i<nMerge; i++){
+        fts3SegReaderFirstDocid(apSegment[i]);
+      }
+      fts3SegReaderSort(apSegment, nMerge, nMerge, fts3SegReaderDoclistCmp);
+      while( apSegment[0]->pOffsetList ){
+        int j;                    /* Number of segments that share a docid */
+        char *pList;
+        int nList;
+        int nByte;
+        sqlite3_int64 iDocid = apSegment[0]->iDocid;
+        fts3SegReaderNextDocid(apSegment[0], &pList, &nList);
+        j = 1;
+        while( j<nMerge
+            && apSegment[j]->pOffsetList
+            && apSegment[j]->iDocid==iDocid
+        ){
+          fts3SegReaderNextDocid(apSegment[j], 0, 0);
+          j++;
+        }
+
+        if( isColFilter ){
+          fts3ColumnFilter(pFilter->iCol, &pList, &nList);
+        }
+
+        if( !isIgnoreEmpty || nList>0 ){
+          nByte = sqlite3Fts3VarintLen(iDocid-iPrev) + (isRequirePos?nList+1:0);
+          if( nDoclist+nByte>nAlloc ){
+            char *aNew;
+            nAlloc = nDoclist+nByte*2;
+            aNew = sqlite3_realloc(aBuffer, nAlloc);
+            if( !aNew ){
+              rc = SQLITE_NOMEM;
+              goto finished;
+            }
+            aBuffer = aNew;
+          }
+          nDoclist += sqlite3Fts3PutVarint(&aBuffer[nDoclist], iDocid-iPrev);
+          iPrev = iDocid;
+          if( isRequirePos ){
+            memcpy(&aBuffer[nDoclist], pList, nList);
+            nDoclist += nList;
+            aBuffer[nDoclist++] = '\0';
+          }
+        }
+
+        fts3SegReaderSort(apSegment, nMerge, j, fts3SegReaderDoclistCmp);
+      }
+
+      if( nDoclist>0 ){
+        rc = xFunc(p, pContext, zTerm, nTerm, aBuffer, nDoclist);
+        if( rc!=SQLITE_OK ) goto finished;
+      }
+    }
+
+    /* If there is a term specified to filter on, and this is not a prefix
+    ** search, return now. The callback that corresponds to the required
+    ** term (if such a term exists in the index) has already been made.
+    */
+    if( pFilter->zTerm && !isPrefix ){
+      goto finished;
+    }
+
+    for(i=0; i<nMerge; i++){
+      rc = fts3SegReaderNext(apSegment[i]);
+      if( rc!=SQLITE_OK ) goto finished;
+    }
+    fts3SegReaderSort(apSegment, nSegment, nMerge, fts3SegReaderCmp);
+  }
+
+ finished:
+  sqlite3_free(aBuffer);
+  return rc;
+}
+
+/*
+** Merge all level iLevel segments in the database into a single 
+** iLevel+1 segment. Or, if iLevel<0, merge all segments into a
+** single segment with a level equal to the numerically largest level 
+** currently present in the database.
+**
+** If this function is called with iLevel<0, but there is only one
+** segment in the database, SQLITE_DONE is returned immediately. 
+** Otherwise, if successful, SQLITE_OK is returned. If an error occurs, 
+** an SQLite error code is returned.
+*/
+static int fts3SegmentMerge(Fts3Table *p, int iLevel){
+  int i;                          /* Iterator variable */
+  int rc;                         /* Return code */
+  int iIdx;                       /* Index of new segment */
+  int iNewLevel;                  /* Level to create new segment at */
+  sqlite3_stmt *pStmt = 0;
+  SegmentWriter *pWriter = 0;
+  int nSegment = 0;               /* Number of segments being merged */
+  Fts3SegReader **apSegment = 0;  /* Array of Segment iterators */
+  Fts3SegReader *pPending = 0;    /* Iterator for pending-terms */
+  Fts3SegFilter filter;           /* Segment term filter condition */
+
+  if( iLevel<0 ){
+    /* This call is to merge all segments in the database to a single
+    ** segment. The level of the new segment is equal to the the numerically 
+    ** greatest segment level currently present in the database. The index
+    ** of the new segment is always 0.
+    */
+    iIdx = 0;
+    rc = sqlite3Fts3SegReaderPending(p, 0, 0, 1, &pPending);
+    if( rc!=SQLITE_OK ) goto finished;
+    rc = fts3SegmentCountMax(p, &nSegment, &iNewLevel);
+    if( rc!=SQLITE_OK ) goto finished;
+    nSegment += (pPending!=0);
+    if( nSegment<=1 ){
+      return SQLITE_DONE;
+    }
+  }else{
+    /* This call is to merge all segments at level iLevel. Find the next
+    ** available segment index at level iLevel+1. The call to
+    ** fts3AllocateSegdirIdx() will merge the segments at level iLevel+1 to 
+    ** a single iLevel+2 segment if necessary.
+    */
+    iNewLevel = iLevel+1;
+    rc = fts3AllocateSegdirIdx(p, iNewLevel, &iIdx);
+    if( rc!=SQLITE_OK ) goto finished;
+    rc = fts3SegmentCount(p, iLevel, &nSegment);
+    if( rc!=SQLITE_OK ) goto finished;
+  }
+  assert( nSegment>0 );
+  assert( iNewLevel>=0 );
+
+  /* Allocate space for an array of pointers to segment iterators. */
+  apSegment = (Fts3SegReader**)sqlite3_malloc(sizeof(Fts3SegReader *)*nSegment);
+  if( !apSegment ){
+    rc = SQLITE_NOMEM;
+    goto finished;
+  }
+  memset(apSegment, 0, sizeof(Fts3SegReader *)*nSegment);
+
+  /* Allocate a Fts3SegReader structure for each segment being merged. A 
+  ** Fts3SegReader stores the state data required to iterate through all 
+  ** entries on all leaves of a single segment. 
+  */
+  assert( SQL_SELECT_LEVEL+1==SQL_SELECT_ALL_LEVEL);
+  rc = fts3SqlStmt(p, SQL_SELECT_LEVEL+(iLevel<0), &pStmt, 0);
+  if( rc!=SQLITE_OK ) goto finished;
+  sqlite3_bind_int(pStmt, 1, iLevel);
+  for(i=0; SQLITE_ROW==(sqlite3_step(pStmt)); i++){
+    rc = fts3SegReaderNew(p, pStmt, i, &apSegment[i]);
+    if( rc!=SQLITE_OK ){
+      goto finished;
+    }
+  }
+  rc = sqlite3_reset(pStmt);
+  if( pPending ){
+    apSegment[i] = pPending;
+    pPending = 0;
+  }
+  pStmt = 0;
+  if( rc!=SQLITE_OK ) goto finished;
+
+  memset(&filter, 0, sizeof(Fts3SegFilter));
+  filter.flags = FTS3_SEGMENT_REQUIRE_POS;
+  filter.flags |= (iLevel<0 ? FTS3_SEGMENT_IGNORE_EMPTY : 0);
+  rc = sqlite3Fts3SegReaderIterate(p, apSegment, nSegment,
+      &filter, fts3MergeCallback, (void *)&pWriter
+  );
+  if( rc!=SQLITE_OK ) goto finished;
+
+  rc = fts3DeleteSegdir(p, iLevel, apSegment, nSegment);
+  if( rc==SQLITE_OK ){
+    rc = fts3SegWriterFlush(p, pWriter, iNewLevel, iIdx);
+  }
+
+ finished:
+  fts3SegWriterFree(pWriter);
+  if( apSegment ){
+    for(i=0; i<nSegment; i++){
+      sqlite3Fts3SegReaderFree(p, apSegment[i]);
+    }
+    sqlite3_free(apSegment);
+  }
+  sqlite3Fts3SegReaderFree(p, pPending);
+  sqlite3_reset(pStmt);
+  return rc;
+}
+
+
+/* 
+** Flush the contents of pendingTerms to a level 0 segment.
+*/
+int sqlite3Fts3PendingTermsFlush(Fts3Table *p){
+  int rc;                         /* Return Code */
+  int idx;                        /* Index of new segment created */
+  SegmentWriter *pWriter = 0;     /* Used to write the segment */
+  Fts3SegReader *pReader = 0;     /* Used to iterate through the hash table */
+
+  /* Allocate a SegReader object to iterate through the contents of the
+  ** pending-terms table. If an error occurs, or if there are no terms
+  ** in the pending-terms table, return immediately.
+  */
+  rc = sqlite3Fts3SegReaderPending(p, 0, 0, 1, &pReader);
+  if( rc!=SQLITE_OK || pReader==0 ){
+    return rc;
+  }
+
+  /* Determine the next index at level 0. If level 0 is already full, this
+  ** call may merge all existing level 0 segments into a single level 1
+  ** segment.
+  */
+  rc = fts3AllocateSegdirIdx(p, 0, &idx);
+
+  /* If no errors have occured, iterate through the contents of the 
+  ** pending-terms hash table using the Fts3SegReader iterator. The callback
+  ** writes each term (along with its doclist) to the database via the
+  ** SegmentWriter handle pWriter.
+  */
+  if( rc==SQLITE_OK ){
+    void *c = (void *)&pWriter;   /* SegReaderIterate() callback context */
+    Fts3SegFilter f;              /* SegReaderIterate() parameters */
+
+    memset(&f, 0, sizeof(Fts3SegFilter));
+    f.flags = FTS3_SEGMENT_REQUIRE_POS;
+    rc = sqlite3Fts3SegReaderIterate(p, &pReader, 1, &f, fts3FlushCallback, c);
+  }
+  assert( pWriter || rc!=SQLITE_OK );
+
+  /* If no errors have occured, flush the SegmentWriter object to the
+  ** database. Then delete the SegmentWriter and Fts3SegReader objects
+  ** allocated by this function.
+  */
+  if( rc==SQLITE_OK ){
+    rc = fts3SegWriterFlush(p, pWriter, 0, idx);
+  }
+  fts3SegWriterFree(pWriter);
+  sqlite3Fts3SegReaderFree(p, pReader);
+
+  if( rc==SQLITE_OK ){
+    sqlite3Fts3PendingTermsClear(p);
+  }
+  return rc;
+}
+
+/*
+** Encode N integers as varints into a blob.
+*/
+static void fts3EncodeIntArray(
+  int N,             /* The number of integers to encode */
+  u32 *a,            /* The integer values */
+  char *zBuf,        /* Write the BLOB here */
+  int *pNBuf         /* Write number of bytes if zBuf[] used here */
+){
+  int i, j;
+  for(i=j=0; i<N; i++){
+    j += sqlite3Fts3PutVarint(&zBuf[j], (sqlite3_int64)a[i]);
+  }
+  *pNBuf = j;
+}
+
+/*
+** Decode a blob of varints into N integers
+*/
+static void fts3DecodeIntArray(
+  int N,             /* The number of integers to decode */
+  u32 *a,            /* Write the integer values */
+  const char *zBuf,  /* The BLOB containing the varints */
+  int nBuf           /* size of the BLOB */
+){
+  int i, j;
+  UNUSED_PARAMETER(nBuf);
+  for(i=j=0; i<N; i++){
+    sqlite3_int64 x;
+    j += sqlite3Fts3GetVarint(&zBuf[j], &x);
+    assert(j<=nBuf);
+    a[i] = (u32)(x & 0xffffffff);
+  }
+}
+
+/*
+** Fill in the document size auxiliary information for the matchinfo
+** structure.  The auxiliary information is:
+**
+**    N     Total number of documents in the full-text index
+**    a0    Average length of column 0 over the whole index
+**    n0    Length of column 0 on the matching row
+**    ...
+**    aM    Average length of column M over the whole index
+**    nM    Length of column M on the matching row
+**
+** The fts3MatchinfoDocsizeLocal() routine fills in the nX values.
+** The fts3MatchinfoDocsizeGlobal() routine fills in N and the aX values.
+*/
+int sqlite3Fts3MatchinfoDocsizeLocal(Fts3Cursor *pCur, u32 *a){
+  const char *pBlob;       /* The BLOB holding %_docsize info */
+  int nBlob;               /* Size of the BLOB */
+  sqlite3_stmt *pStmt;     /* Statement for reading and writing */
+  int i, j;                /* Loop counters */
+  sqlite3_int64 x;         /* Varint value */
+  int rc;                  /* Result code from subfunctions */
+  Fts3Table *p;            /* The FTS table */
+
+  p = (Fts3Table*)pCur->base.pVtab;
+  rc = fts3SqlStmt(p, SQL_SELECT_DOCSIZE, &pStmt, 0);
+  if( rc ){
+    return rc;
+  }
+  sqlite3_bind_int64(pStmt, 1, pCur->iPrevId);
+  if( sqlite3_step(pStmt)==SQLITE_ROW ){
+    nBlob = sqlite3_column_bytes(pStmt, 0);
+    pBlob = (const char*)sqlite3_column_blob(pStmt, 0);
+    for(i=j=0; i<p->nColumn && j<nBlob; i++){
+      j = sqlite3Fts3GetVarint(&pBlob[j], &x);
+      a[2+i*2] = (u32)(x & 0xffffffff);
+    }
+  }
+  sqlite3_reset(pStmt);
+  return SQLITE_OK; 
+}
+int sqlite3Fts3MatchinfoDocsizeGlobal(Fts3Cursor *pCur, u32 *a){
+  const char *pBlob;       /* The BLOB holding %_stat info */
+  int nBlob;               /* Size of the BLOB */
+  sqlite3_stmt *pStmt;     /* Statement for reading and writing */
+  int i, j;                /* Loop counters */
+  sqlite3_int64 x;         /* Varint value */
+  int nDoc;                /* Number of documents */
+  int rc;                  /* Result code from subfunctions */
+  Fts3Table *p;            /* The FTS table */
+
+  p = (Fts3Table*)pCur->base.pVtab;
+  rc = fts3SqlStmt(p, SQL_SELECT_DOCTOTAL, &pStmt, 0);
+  if( rc ){
+    return rc;
+  }
+  if( sqlite3_step(pStmt)==SQLITE_ROW ){
+    nBlob = sqlite3_column_bytes(pStmt, 0);
+    pBlob = (const char*)sqlite3_column_blob(pStmt, 0);
+    j = sqlite3Fts3GetVarint(pBlob, &x);
+    a[0] = nDoc = (u32)(x & 0xffffffff);
+    for(i=0; i<p->nColumn && j<nBlob; i++){
+      j = sqlite3Fts3GetVarint(&pBlob[j], &x);
+      a[1+i*2] = ((u32)(x & 0xffffffff) + nDoc/2)/nDoc;
+    }
+  }
+  sqlite3_reset(pStmt);
+  return SQLITE_OK; 
+}
+
+/*
+** Insert the sizes (in tokens) for each column of the document
+** with docid equal to p->iPrevDocid.  The sizes are encoded as
+** a blob of varints.
+*/
+static void fts3InsertDocsize(
+  int *pRC,         /* Result code */
+  Fts3Table *p,     /* Table into which to insert */
+  u32 *aSz          /* Sizes of each column */
+){
+  char *pBlob;             /* The BLOB encoding of the document size */
+  int nBlob;               /* Number of bytes in the BLOB */
+  sqlite3_stmt *pStmt;     /* Statement used to insert the encoding */
+  int rc;                  /* Result code from subfunctions */
+
+  if( *pRC ) return;
+  pBlob = sqlite3_malloc( 10*p->nColumn );
+  if( pBlob==0 ){
+    *pRC = SQLITE_NOMEM;
+    return;
+  }
+  fts3EncodeIntArray(p->nColumn, aSz, pBlob, &nBlob);
+  rc = fts3SqlStmt(p, SQL_REPLACE_DOCSIZE, &pStmt, 0);
+  if( rc ){
+    sqlite3_free(pBlob);
+    *pRC = rc;
+    return;
+  }
+  sqlite3_bind_int64(pStmt, 1, p->iPrevDocid);
+  sqlite3_bind_blob(pStmt, 2, pBlob, nBlob, sqlite3_free);
+  sqlite3_step(pStmt);
+  *pRC = sqlite3_reset(pStmt);
+}
+
+/*
+** Update the 0 record of the %_stat table so that it holds a blob
+** which contains the document count followed by the cumulative
+** document sizes for all columns.
+*/
+static void fts3UpdateDocTotals(
+  int *pRC,       /* The result code */
+  Fts3Table *p,   /* Table being updated */
+  u32 *aSzIns,    /* Size increases */
+  u32 *aSzDel,    /* Size decreases */
+  int nChng       /* Change in the number of documents */
+){
+  char *pBlob;             /* Storage for BLOB written into %_stat */
+  int nBlob;               /* Size of BLOB written into %_stat */
+  u32 *a;                  /* Array of integers that becomes the BLOB */
+  sqlite3_stmt *pStmt;     /* Statement for reading and writing */
+  int i;                   /* Loop counter */
+  int rc;                  /* Result code from subfunctions */
+
+  if( *pRC ) return;
+  a = sqlite3_malloc( (sizeof(u32)+10)*(p->nColumn+1) );
+  if( a==0 ){
+    *pRC = SQLITE_NOMEM;
+    return;
+  }
+  pBlob = (char*)&a[p->nColumn+1];
+  rc = fts3SqlStmt(p, SQL_SELECT_DOCTOTAL, &pStmt, 0);
+  if( rc ){
+    sqlite3_free(a);
+    *pRC = rc;
+    return;
+  }
+  if( sqlite3_step(pStmt)==SQLITE_ROW ){
+    fts3DecodeIntArray(p->nColumn+1, a,
+         sqlite3_column_blob(pStmt, 0),
+         sqlite3_column_bytes(pStmt, 0));
+  }else{
+    memset(a, 0, sizeof(u32)*(p->nColumn+1) );
+  }
+  sqlite3_reset(pStmt);
+  if( nChng<0 && a[0]<(u32)(-nChng) ){
+    a[0] = 0;
+  }else{
+    a[0] += nChng;
+  }
+  for(i=0; i<p->nColumn; i++){
+    u32 x = a[i+1];
+    if( x+aSzIns[i] < aSzDel[i] ){
+      x = 0;
+    }else{
+      x = x + aSzIns[i] - aSzDel[i];
+    }
+    a[i+1] = x;
+  }
+  fts3EncodeIntArray(p->nColumn+1, a, pBlob, &nBlob);
+  rc = fts3SqlStmt(p, SQL_REPLACE_DOCTOTAL, &pStmt, 0);
+  if( rc ){
+    sqlite3_free(a);
+    *pRC = rc;
+    return;
+  }
+  sqlite3_bind_blob(pStmt, 1, pBlob, nBlob, SQLITE_STATIC);
+  sqlite3_step(pStmt);
+  *pRC = sqlite3_reset(pStmt);
+  sqlite3_free(a);
+}
+
+/*
+** Handle a 'special' INSERT of the form:
+**
+**   "INSERT INTO tbl(tbl) VALUES(<expr>)"
+**
+** Argument pVal contains the result of <expr>. Currently the only 
+** meaningful value to insert is the text 'optimize'.
+*/
+static int fts3SpecialInsert(Fts3Table *p, sqlite3_value *pVal){
+  int rc;                         /* Return Code */
+  const char *zVal = (const char *)sqlite3_value_text(pVal);
+  int nVal = sqlite3_value_bytes(pVal);
+
+  if( !zVal ){
+    return SQLITE_NOMEM;
+  }else if( nVal==8 && 0==sqlite3_strnicmp(zVal, "optimize", 8) ){
+    rc = fts3SegmentMerge(p, -1);
+    if( rc==SQLITE_DONE ){
+      rc = SQLITE_OK;
+    }else{
+      sqlite3Fts3PendingTermsClear(p);
+    }
+#ifdef SQLITE_TEST
+  }else if( nVal>9 && 0==sqlite3_strnicmp(zVal, "nodesize=", 9) ){
+    p->nNodeSize = atoi(&zVal[9]);
+    rc = SQLITE_OK;
+  }else if( nVal>11 && 0==sqlite3_strnicmp(zVal, "maxpending=", 9) ){
+    p->nMaxPendingData = atoi(&zVal[11]);
+    rc = SQLITE_OK;
+#endif
+  }else{
+    rc = SQLITE_ERROR;
+  }
+
+  return rc;
+}
+
+/*
+** This function does the work for the xUpdate method of FTS3 virtual
+** tables.
+*/
+int sqlite3Fts3UpdateMethod(
+  sqlite3_vtab *pVtab,            /* FTS3 vtab object */
+  int nArg,                       /* Size of argument array */
+  sqlite3_value **apVal,          /* Array of arguments */
+  sqlite_int64 *pRowid            /* OUT: The affected (or effected) rowid */
+){
+  Fts3Table *p = (Fts3Table *)pVtab;
+  int rc = SQLITE_OK;             /* Return Code */
+  int isRemove = 0;               /* True for an UPDATE or DELETE */
+  sqlite3_int64 iRemove = 0;      /* Rowid removed by UPDATE or DELETE */
+  u32 *aSzIns;                    /* Sizes of inserted documents */
+  u32 *aSzDel;                    /* Sizes of deleted documents */
+  int nChng = 0;                  /* Net change in number of documents */
+
+
+  /* Allocate space to hold the change in document sizes */
+  aSzIns = sqlite3_malloc( sizeof(aSzIns[0])*p->nColumn*2 );
+  if( aSzIns==0 ) return SQLITE_NOMEM;
+  aSzDel = &aSzIns[p->nColumn];
+  memset(aSzIns, 0, sizeof(aSzIns[0])*p->nColumn*2);
+
+  /* If this is a DELETE or UPDATE operation, remove the old record. */
+  if( sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
+    int isEmpty;
+    rc = fts3IsEmpty(p, apVal, &isEmpty);
+    if( rc==SQLITE_OK ){
+      if( isEmpty ){
+        /* Deleting this row means the whole table is empty. In this case
+        ** delete the contents of all three tables and throw away any
+        ** data in the pendingTerms hash table.
+        */
+        rc = fts3DeleteAll(p);
+      }else{
+        isRemove = 1;
+        iRemove = sqlite3_value_int64(apVal[0]);
+        rc = fts3PendingTermsDocid(p, iRemove);
+        fts3DeleteTerms(&rc, p, apVal, aSzDel);
+        fts3SqlExec(&rc, p, SQL_DELETE_CONTENT, apVal);
+        if( p->bHasDocsize ){
+          fts3SqlExec(&rc, p, SQL_DELETE_DOCSIZE, apVal);
+          nChng--;
+        }
+      }
+    }
+  }else if( sqlite3_value_type(apVal[p->nColumn+2])!=SQLITE_NULL ){
+    sqlite3_free(aSzIns);
+    return fts3SpecialInsert(p, apVal[p->nColumn+2]);
+  }
+  
+  /* If this is an INSERT or UPDATE operation, insert the new record. */
+  if( nArg>1 && rc==SQLITE_OK ){
+    rc = fts3InsertData(p, apVal, pRowid);
+    if( rc==SQLITE_OK && (!isRemove || *pRowid!=iRemove) ){
+      rc = fts3PendingTermsDocid(p, *pRowid);
+    }
+    if( rc==SQLITE_OK ){
+      rc = fts3InsertTerms(p, apVal, aSzIns);
+    }
+    if( p->bHasDocsize ){
+      nChng++;
+      fts3InsertDocsize(&rc, p, aSzIns);
+    }
+  }
+
+  if( p->bHasDocsize ){
+    fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nChng);
+  }
+
+  sqlite3_free(aSzIns);
+  return rc;
+}
+
+/* 
+** Flush any data in the pending-terms hash table to disk. If successful,
+** merge all segments in the database (including the new segment, if 
+** there was any data to flush) into a single segment. 
+*/
+int sqlite3Fts3Optimize(Fts3Table *p){
+  int rc;
+  rc = sqlite3_exec(p->db, "SAVEPOINT fts3", 0, 0, 0);
+  if( rc==SQLITE_OK ){
+    rc = fts3SegmentMerge(p, -1);
+    if( rc==SQLITE_OK ){
+      rc = sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);
+      if( rc==SQLITE_OK ){
+        sqlite3Fts3PendingTermsClear(p);
+      }
+    }else{
+      sqlite3_exec(p->db, "ROLLBACK TO fts3", 0, 0, 0);
+      sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);
+    }
+  }
+  return rc;
+}
+
+#endif