SQLite

  d->pData = realloc(d->pData, d->nData + n);
  memcpy(d->pData + d->nData, c, n);
  d->nData += n;
}

static void docListAddDocid(DocList *d, sqlite_int64 iDocid){
  appendVarint(d, iDocid);
  if( d->iType>=DL_POSITIONS ){
    appendVarint(d, 0);  /* initially empty position list */
    d->iLastPos = 0;
  }
}

/* helper function for docListAddPos and docListAddPosOffset */
static void addPos(DocList *d, int iPos) {
  appendVarint(d, iPos-d->iLastPos+1);
  d->iLastPos = iPos;
}

/* Add a position to the last position list in a doclist. */
static void docListAddPos(DocList *d, int iPos){
  assert( d->iType==DL_POSITIONS );
  assert( d->nData>0 );
  --d->nData;  /* remove previous terminator */
  addPos(d, iPos);
  appendVarint(d, 0);  /* add new terminator */

}

static void docListAddPosOffset(DocList *d, int iPos,
                                int iStartOffset, int iEndOffset){
  assert( d->iType==DL_POSITIONS_OFFSETS );
  assert( d->nData>0 );
  --d->nData;  /* remove previous terminator */
  addPos(d, iPos);
  appendVarint(d, iStartOffset-d->iLastOffset);
  d->iLastOffset = iStartOffset;
  appendVarint(d, iEndOffset-iStartOffset);




  appendVarint(d, 0);  /* add new terminator */
}

typedef struct DocListReader {
  DocList *pDoclist;
  char *p;
  int iLastPos;  /* the last position read, or -1 when not in a position list */
} DocListReader;

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

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

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

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

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

  pReader->p += getVarint32(pReader->p, &i);
  if( i==0 ){
    pReader->iLastPos = -1;
    return -1;
  }
  pReader->iLastPos += ((int) i)-1;

    ;
}

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

/* Skip past all docids which are less than [iDocid].  Returns 1 if a docid
 * matching [iDocid] was found.  */
static int skipToDocid(DocListReader *pReader, sqlite_int64 iDocid){
  sqlite_int64 d = 0;
  while( !atEnd(pReader) && (d=peekDocid(pReader))<iDocid ){
    skipDocument(pReader);
  }
  return !atEnd(pReader) && d==iDocid;
}

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

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

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

  readerInit(&reader, d);

  found = skipToDocid(&reader, iDocid);


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

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


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

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

  const char *pSplitPoint = d->pData + d->nData / 2;
  DocListReader reader;

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

/* A DocListMerge computes the AND of an in-memory DocList [in] and a chunked

 * If [in] has positions, then the merge output contains only documents with
 * matching positions in the two input doclists.  If [in] does not have
 * positions, then the merge output contains all documents common to the two
 * input doclists.
 *
 * If [in] is NULL, then the on-disk doclist is copied to [out] directly.
 *
 * A merge is performed using an integer [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.
*/
typedef struct DocListMerge {
  DocListReader in;
  DocList *pOut;
  int iPhrasePos;
} DocListMerge;

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

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

/* A helper function for mergeBlock(), below.  Merge the position lists
 * pointed to by m->in and pBlockReader.
 * If the merge matches, write [iDocid] to m->pOut; if m->pOut
 * has positions then write all matching positions as well. */
static void mergePosList(DocListMerge *m, sqlite_int64 iDocid,
                         DocListReader *pBlockReader){
  int iBlockPos = readPosition(pBlockReader);
  int iInPos = readPosition(&m->in);
  int match = 0;

  /* Loop until we've reached the end of both position lists. */
  while( iBlockPos!=-1 || iInPos!=-1 ){
    if( iBlockPos-m->iPhrasePos==iInPos ){
      if( !match ){
        docListAddDocid(m->pOut, iDocid);
        match = 1;
      }
      if( m->pOut->iType>=DL_POSITIONS ){
        docListAddPos(m->pOut, iInPos);
      }
      iBlockPos = readPosition(pBlockReader);
      iInPos = readPosition(&m->in);
    } else if( iInPos==-1 || (iBlockPos!=-1 && iBlockPos-m->iPhrasePos<iInPos) ){
      iBlockPos = readPosition(pBlockReader);
    } else {
      iInPos = readPosition(&m->in);
    }
  }
}

/* A helper function for mergeBlock(), below.  Copy the docid and
 * position list (if wanted) from pBlockReader to pOut. */
static void copyDocument(DocList *pOut, sqlite_int64 iDocid,
                         DocListReader *pBlockReader){
  docListAddDocid(pOut, iDocid);
  if( pOut->iType<DL_POSITIONS ){
    skipPositionList(pBlockReader);
  } else {
    /* Copy all positions to the output doclist. */
    int pos;
    while( (pos = readPosition(pBlockReader))!=-1 ){
      docListAddPos(pOut, pos);
    }
  }
}

/* Merge one block of an on-disk doclist into a DocListMerge. */
static void mergeBlock(DocListMerge *m, DocList *pBlock){
  DocListReader blockReader;
  assert( pBlock->iType>=DL_POSITIONS );
  readerInit(&blockReader, pBlock);
  while( !atEnd(&blockReader) ){
    sqlite_int64 iDocid = readDocid(&blockReader);
    if( m->in.pDoclist==NULL ){



      copyDocument(m->pOut, iDocid, &blockReader);



      continue;
    }
    if( skipToDocid(&m->in, iDocid) ){  /* we have a docid match */
      readDocid(&m->in);


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

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

          c->eof = 1;
          return rc;
      }
    case QUERY_FULLTEXT:
      rc = sqlite3_reset(c->pStmt);
      if( rc!=SQLITE_OK ) return rc;

      if( atEnd(&c->result)){
        c->eof = 1;
        return SQLITE_OK;
      }
      iDocid = readDocid(&c->result);
      rc = sqlite3_bind_int64(c->pStmt, 1, iDocid);
      if( rc!=SQLITE_OK ) return rc;
      /* TODO(shess) Handle SQLITE_SCHEMA AND SQLITE_BUSY. */

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

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

/* Read the posting list for [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, sqlite3_stmt **pSelect,
                       const char *pTerm, int nTerm,
                       DocList *pIn, int iPhrasePos, DocList *out){
  int rc;
  DocListMerge merge;


  /* 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_doclist(v, pTerm, nTerm, pSelect);
  if( rc!=SQLITE_ROW && rc!=SQLITE_DONE ) return rc;

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

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


  }
  
  return SQLITE_OK;
}

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

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

static void queryAdd(Query *q, int isPhrase, const char *pTerm, int nTerm){
  QueryTerm *t;
  ++q->nTerms;
  q->pTerms = realloc(q->pTerms, q->nTerms * sizeof(q->pTerms[0]));
  t = &q->pTerms[q->nTerms - 1];
  t->isPhrase = isPhrase;
  t->pTerm = malloc(nTerm);
  memcpy(t->pTerm, pTerm, nTerm);
  t->nTerm = nTerm;
}
    
static void queryDestroy(Query *q){
  int i;
  for(i = 0; i < q->nTerms; ++i){
    free(q->pTerms[i].pTerm);
  }
  free(q->pTerms);
}

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

  while( 1 ){
    const char *pToken;
    int nToken, iDummyOffset, iDummyPos;

    rc = pModule->xNext(pCursor,
                        &pToken, &nToken,
                        &iDummyOffset, &iDummyOffset,
                        &iDummyPos);
    if( rc!=SQLITE_OK ) break;
    queryAdd(pQuery, !inPhrase || is_first, pToken, nToken);
    is_first = 0;
  }

  return pModule->xClose(pCursor);
}

/* Parse a query string, yielding a Query object [pQuery], which the caller
 * must free. */
static int parseQuery(fulltext_vtab *v, const char *pInput, int nInput,
                      Query *pQuery){
  int iInput, inPhrase = 0;

  if( nInput<0 ) nInput = strlen(pInput);
  pQuery->nTerms = 0;
  pQuery->pTerms = NULL;

  for(iInput=0; iInput<nInput; ++iInput){
    int i;
    for(i=iInput; i<nInput && pInput[i]!='"'; ++i)
      ;
    if( i>iInput ){
      tokenizeSegment(v->pTokenizer, pInput+iInput, i-iInput, inPhrase,
                       pQuery);
    }
    iInput = i;
    if( i<nInput ){
      assert( pInput[i]=='"' );
      inPhrase = !inPhrase;
    }
  }

  if(inPhrase) {  /* unmatched quote */
    queryDestroy(pQuery);
    return SQLITE_ERROR;
  }
  return SQLITE_OK;
}

/* 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;
  sqlite3_stmt *pSelect = NULL;
  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, &pSelect, 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;
  }

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

static int fulltextFilter(sqlite3_vtab_cursor *pCursor,
                          int idxNum, const char *idxStr,
                          int argc, sqlite3_value **argv){

      break;

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

    default:

  fulltext_cursor *c = (fulltext_cursor *) pCursor;

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

/* Build a hash table containing all terms in pText. */
static int buildTerms(fts1Hash *terms, sqlite3_tokenizer *pTokenizer,
                       const char *pText, int nText, sqlite_int64 iDocid){
  sqlite3_tokenizer_cursor *pCursor;
  const char *pToken;
  int nTokenBytes;
  int iStartOffset, iEndOffset, iPosition;
  int rc;

  rc = content_insert(v, pRequestRowid, pText, nText);
  if( rc!=SQLITE_OK ) return rc;
  *piRowid = sqlite3_last_insert_rowid(v->db);

  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), *piRowid, p);
    if( rc!=SQLITE_OK ) break;
  }

  int nText;
  fts1Hash terms;
  fts1HashElem *e;

  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;

  for(e=fts1HashFirst(&terms); e; e=fts1HashNext(e)){
    rc = index_delete_term(v, fts1HashKey(e), fts1HashKeysize(e), iRow);
    if( rc!=SQLITE_OK ) break;
  }