SQLite

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

/* Helper function for docListUpdate() and docListAccumulate().

** Splices a doclist element into the doclist represented by r,
** leaving r pointing after the newly spliced element.
*/
static void docListSpliceElement(DocListReader *r, sqlite_int64 iDocid,
                                 const char *pSource, int nSource){
  DocList *d = r->pDoclist;

  char *pTarget;
  int nTarget, found;






  found = skipToDocid(r, iDocid);

  /* Describe slice in d to place pSource/nSource. */
  pTarget = r->p;

  if( found ){
    skipDocument(r);


    nTarget = r->p-pTarget;
  }else{
    nTarget = 0;
  }

  /* The sense of the following is that there are three possibilities.
  ** If nTarget==nSource, we should not move any memory nor realloc.
  ** If nTarget>nSource, trim target and realloc.
  ** If nTarget<nSource, realloc then expand target.
  */
  if( nTarget>nSource ){
    memmove(pTarget+nSource, pTarget+nTarget, docListEnd(d)-(pTarget+nTarget));
  }
  if( nTarget!=nSource ){
    int iDoclist = pTarget-d->pData;
    d->pData = realloc(d->pData, d->nData+nSource-nTarget);
    pTarget = d->pData+iDoclist;
  }
  if( nTarget<nSource ){
    memmove(pTarget+nSource, pTarget+nTarget, docListEnd(d)-(pTarget+nTarget));
  }

  memcpy(pTarget, pSource, nSource);
  d->nData += nSource-nTarget;
  r->p = pTarget+nSource;
}

/* Insert/update pUpdate into the doclist. */
static void docListUpdate(DocList *d, DocList *pUpdate){
  DocListReader reader;

  assert( d!=NULL && pUpdate!=NULL );
  assert( d->iType==pUpdate->iType);

  readerInit(&reader, d);
  docListSpliceElement(&reader, firstDocid(pUpdate),
                       pUpdate->pData, pUpdate->nData);


}

/* Propagate elements from pUpdate to pAcc, overwriting elements with
** matching docids.
*/
static void docListAccumulate(DocList *pAcc, DocList *pUpdate){
  DocListReader accReader, updateReader;

  /* Handle edge cases where one doclist is empty. */
  assert( pAcc!=NULL );
  if( pUpdate==NULL || pUpdate->nData==0 ) return;
  if( pAcc->nData==0 ){
    pAcc->pData = malloc(pUpdate->nData);
    memcpy(pAcc->pData, pUpdate->pData, pUpdate->nData);
    pAcc->nData = pUpdate->nData;
    return;
  }



  readerInit(&accReader, pAcc);


  readerInit(&updateReader, pUpdate);

  while( !atEnd(&updateReader) ){
    char *pSource = updateReader.p;
    sqlite_int64 iDocid = readDocid(&updateReader);
    skipPositionList(&updateReader);
    docListSpliceElement(&accReader, iDocid, pSource, updateReader.p-pSource);
  }





}

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

 * A merge is performed using an integer [iPhrasePos] provided by the caller.
 * [iPhrasePos] 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.
*/
/* TODO(shess) Adam indicates that since we no longer can stream
** ordered doclist chunks, DocListMerge is no longer as useful and
** should be removed.  Not removing at this time so that the removal
** doesn't obscure the exponential-chunking change.
*/
typedef struct DocListMerge {
  DocListReader in;
  DocList *pOut;
  int iPhrasePos;
} DocListMerge;

static void mergeBlock(DocListMerge *m, DocList *pBlock){
  DocListReader blockReader;
  assert( pBlock->iType>=DL_POSITIONS );
  readerInit(&blockReader, pBlock);
  while( !atEnd(&blockReader) ){
    sqlite_int64 iDocid = readDocid(&blockReader);
    if( m->in.pDoclist==NULL ){
      /* Skip document delete crumbs */
      if( *blockReader.p=='\0' ){
        skipPositionList(&blockReader);
      } else {
        copyDocument(m->pOut, iDocid, &blockReader);
      }
      continue;
    }
    if( skipToDocid(&m->in, iDocid) ){  /* we have a docid match */
      readDocid(&m->in);
      /* Skip document delete crumbs */
      if( *blockReader.p=='\0' ){
        skipPositionList(&blockReader);
      }else{
        if( m->in.pDoclist->iType>=DL_POSITIONS ){
          mergePosList(m, iDocid, &blockReader);
        } else {
          copyDocument(m->pOut, iDocid, &blockReader);
        }
      }
    } else if( !atEnd(&m->in) ){
      skipPositionList(&blockReader);  /* skip this docid in the block */
    } else return;  /* nothing more to merge */
  }
}

}

/* end utility functions */

#define QUERY_GENERIC 0
#define QUERY_FULLTEXT 1

/* TODO(shess) CHUNK_MAX controls how much data we allow in segment 0
** before we start aggregating into larger segments.  Lower CHUNK_MAX
** means that for a given input we have more individual segments per
** term, which means more rows in the table and a bigger index (due to
** both more rows and bigger rowids).  But it also reduces the average
** cost of adding new elements to the segment 0 doclist, and it seems
** to reduce the number of pages read and written during inserts.  256
** was chosen by measuring insertion times for a certain input (first
** 10k documents of Enron corpus), though including query performance
** in the decision may argue for a larger value.
*/
#define CHUNK_MAX 256

typedef enum fulltext_statement {
  CONTENT_INSERT_STMT,
  CONTENT_SELECT_STMT,
  CONTENT_DELETE_STMT,

  TERM_SELECT_STMT,
  TERM_SELECT_ALL_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 *const 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 segment = ?",
  /* TERM_SELECT_ALL */
  "select doclist from %_term where term = ? order by segment",
  /* TERM_INSERT */
  "insert into %_term (term, segment, 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;

  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 = [pTerm] and segment = [iSegment]
 * If found, returns SQLITE_ROW; the caller must free the
 * returned doclist.  If no rows found, returns SQLITE_DONE. */
static int term_select(fulltext_vtab *v, const char *pTerm, int nTerm,
                       int iSegment,
                       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, pTerm, nTerm, SQLITE_STATIC);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int(s, 2, iSegment);
  if( rc!=SQLITE_OK ) return rc;

  rc = sql_step_statement(v, TERM_SELECT_STMT, &s);
  if( rc!=SQLITE_ROW ) return 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_ROW : rc;
}

/* Load the segment doclists for term pTerm and merge them in
** appropriate order into out.  Returns SQLITE_OK if successful.  If
** there are no segments for pTerm, successfully returns an empty
** doclist in out.
*/
static int term_select_all(fulltext_vtab *v, const char *pTerm, int nTerm,

                           DocList *out){
  DocList doclist;
  sqlite3_stmt *s;
  int rc = sql_get_statement(v, TERM_SELECT_ALL_STMT, &s);
  if( rc!=SQLITE_OK ) return rc;

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

  docListInit(&doclist, DL_POSITIONS_OFFSETS, 0, 0);


  /* TODO(shess) Handle schema and busy errors. */
  while( (rc=sql_step_statement(v, TERM_SELECT_ALL_STMT, &s))==SQLITE_ROW ){
    DocList old;

    /* TODO(shess) If we processed doclists from oldest to newest, we
    ** could skip the malloc() involved with the following call.  For
    ** now, I'd rather keep this logic similar to index_insert_term().
    ** We could additionally drop elements when we see deletes, but
    ** that would require a distinct version of docListAccumulate().
    */
    docListInit(&old, doclist.iType,
                sqlite3_column_blob(s, 0), sqlite3_column_bytes(s, 0));

    /* doclist contains the newer data, so write it over old.  Then
    ** steal accumulated result for doclist.
    */
    docListAccumulate(&old, &doclist);
    docListDestroy(&doclist);
    doclist = old;
  }
  if( rc!=SQLITE_DONE ){





    docListDestroy(&doclist);
    return rc;
  }



  *out = doclist;
  return SQLITE_OK;
}

/* insert into %_term (term, segment, doclist)
               values ([pTerm], [iSegment], [doclist]) */
static int term_insert(fulltext_vtab *v, const char *pTerm, int nTerm,
                       int iSegment, 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, pTerm, nTerm, SQLITE_STATIC);
  if( rc!=SQLITE_OK ) return rc;

  rc = sqlite3_bind_int(s, 2, iSegment);
  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);
}

  ** 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 elements:

  **     position+1 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
  **
  ** The sentinel position of 0 indicates the end of the token list.
  **
  ** Additionally, doclist blobs are chunked into multiple segments,
  ** using segment to order the segments.  New elements are added to
  ** the segment at segment 0, until it exceeds CHUNK_MAX.  Then
  ** segment 0 is deleted, and the doclist is inserted at segment 1.
  ** If there is already a doclist at segment 1, the segment 0 doclist
  ** is merged with it, the segment 1 doclist is deleted, and the
  ** merged doclist is inserted at segment 2, repeating those
  ** operations until an insert succeeds.
  **
  ** Since this structure doesn't allow us to update elements in place
  ** in case of deletion or update, these are simply written to
  ** segment 0 (with an empty token list in case of deletion), with
  ** docListAccumulate() taking care to retain lower-segment
  ** information in preference to higher-segment information.
  */

  /* TODO(shess) Provide a VACUUM type operation which both removes
  ** deleted elements which are no longer necessary, and duplicated



  ** elements.  I suspect this will probably not be necessary in
  ** practice, though.
  */
  rc = sql_exec(db, argv[2],
    "create table %_content(content text);"
    "create table %_term(term text, segment integer, doclist blob, "
                        "primary key(term, segment));");
  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

      return rc==SQLITE_DONE ? SQLITE_ERROR : rc;
    default:
      assert( 0 );
      return SQLITE_ERROR;  /* not reached */
  }
}


















/* Read the posting list for [pTerm]; AND it with the doclist [pIn] to
 * produce the doclist [out], using the given phrase position [iPhrasePos].
 * (*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 mergeQuery(fulltext_vtab *v, const char *pTerm, int nTerm,

                       DocList *pIn, int iPhrasePos, DocList *out){
  int rc;
  DocListMerge merge;
  DocList doclist;

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

  rc = term_select_all(v, pTerm, nTerm, &doclist);
  if( rc!=SQLITE_OK ) return rc;

  mergeInit(&merge, pIn, iPhrasePos, out);





  mergeBlock(&merge, &doclist);
  docListDestroy(&doclist);





  return SQLITE_OK;
}

typedef struct QueryTerm {
  int isPhrase;    /* true if this term begins a new phrase */
  char *pTerm;
  int nTerm;

/* Perform a full-text query; return a list of documents in [pResult]. */
static int fulltextQuery(fulltext_vtab *v, const char *pInput, int nInput,
                          DocList **pResult){
  Query q;
  int phrase_start = -1;
  int i;

  DocList *d = NULL;

  int rc = parseQuery(v, pInput, nInput, &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 needPositions = i<q.nTerms-1 && !q.pTerms[i+1].isPhrase;
    DocList *next = docListNew(needPositions ? DL_POSITIONS : DL_DOCIDS);
    if( q.pTerms[i].isPhrase ){
      phrase_start = i;
    }
    rc = mergeQuery(v, q.pTerms[i].pTerm, q.pTerms[i].nTerm,
                     d, i-phrase_start, next);
    if( rc!=SQLITE_OK ) break;
    if( d!=NULL ){
      docListDelete(d);
    }
    d = next;
  }


  queryDestroy(&q);
  *pResult = d;
  return rc;
}

static int fulltextFilter(sqlite3_vtab_cursor *pCursor,
                          int idxNum, const char *idxStr,

  ** 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 [pTerm] to the given rowid. */
static int index_insert_term(fulltext_vtab *v, const char *pTerm, int nTerm,
                             DocList *d){

  sqlite_int64 iIndexRow;
  DocList doclist;
  int iSegment = 0, rc;

  rc = term_select(v, pTerm, nTerm, iSegment, &iIndexRow, &doclist);
  if( rc==SQLITE_DONE ){
    docListInit(&doclist, DL_POSITIONS_OFFSETS, 0, 0);
    docListUpdate(&doclist, d);
    /* TODO(shess) Consider length(doclist)>CHUNK_MAX? */
    rc = term_insert(v, pTerm, nTerm, iSegment, &doclist);

    goto err;
  }


  if( rc!=SQLITE_ROW ) return SQLITE_ERROR;






  docListUpdate(&doclist, d);

  if( doclist.nData<=CHUNK_MAX ){







    rc = term_update(v, iIndexRow, &doclist);
    goto err;
  }

  /* Doclist doesn't fit, delete what's there, and accumulate
  ** forward.
  */
  rc = term_delete(v, iIndexRow);
  if( rc!=SQLITE_OK ) goto err;

  /* Try to insert the doclist into a higher segment bucket.  On
  ** failure, accumulate existing doclist with the doclist from that
  ** bucket, and put results in the next bucket.
  */
  iSegment++;
  while( (rc=term_insert(v, pTerm, nTerm, iSegment, &doclist))!=SQLITE_OK ){
    DocList old;
    int rc2;

    /* Retain old error in case the term_insert() error was really an
    ** error rather than a bounced insert.
    */
    rc2 = term_select(v, pTerm, nTerm, iSegment, &iIndexRow, &old);
    if( rc2!=SQLITE_ROW ) goto err;

    rc = term_delete(v, iIndexRow);
    if( rc!=SQLITE_OK ) goto err;

    /* doclist contains the newer data, so accumulate it over old.
    ** Then steal accumulated data for doclist.
    */
    docListAccumulate(&old, &doclist);
    docListDestroy(&doclist);
    doclist = old;

    iSegment++;
  }

 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,

  if( !pText || !nText ) return SQLITE_OK;   /* nothing to index */

  rc = buildTerms(&terms, v->pTokenizer, pText, nText, *piRowid);
  if( rc!=SQLITE_OK ) return rc;

  for(e=fts1HashFirst(&terms); e; e=fts1HashNext(e)){
    DocList *p = fts1HashData(e);
    rc = index_insert_term(v, fts1HashKey(e), fts1HashKeysize(e), p);
    if( rc!=SQLITE_OK ) break;
  }

  for(e=fts1HashFirst(&terms); e; e=fts1HashNext(e)){
    DocList *p = fts1HashData(e);
    docListDelete(p);
  }
  fts1HashClear(&terms);
  return rc;
}



























/* Delete a row from the full-text index. */
static int index_delete(fulltext_vtab *v, sqlite_int64 iRow){
  char *pText = 0;
  int nText = 0;
  fts1Hash terms;
  fts1HashElem *e;
  DocList doclist;

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

  rc = buildTerms(&terms, v->pTokenizer, pText, nText, iRow);
  free(pText);
  if( rc!=SQLITE_OK ) return rc;

  /* Delete by inserting a doclist with no positions.  This will
  ** overwrite existing data as it is merged forward by
  ** index_insert_term().
  */
  docListInit(&doclist, DL_POSITIONS_OFFSETS, 0, 0);
  docListAddDocid(&doclist, iRow);

  for(e=fts1HashFirst(&terms); e; e=fts1HashNext(e)){
    rc = index_insert_term(v, fts1HashKey(e), fts1HashKeysize(e), &doclist);
    if( rc!=SQLITE_OK ) break;
  }
  for(e=fts1HashFirst(&terms); e; e=fts1HashNext(e)){
    DocList *p = fts1HashData(e);
    docListDelete(p);
  }
  fts1HashClear(&terms);
  docListDestroy(&doclist);

  if( rc!=SQLITE_OK ) return rc;
  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;