SQLite

      return rc;
    }
  }else{
    return SQLITE_OK;
  }
}

/*
** This function is used to process a single interior node when searching
** a b-tree for a term or term prefix. The node data is passed to this 
** function via the zNode/nNode parameters. The term to search for is
** passed in zTerm/nTerm.
**
** If piFirst is not NULL, then this function sets *piFirst to the blockid
** of the child node that heads the sub-tree that may contain the term.
**
** If piLast is not NULL, then *piLast is set to the right-most child node
** that heads a sub-tree that may contain a term for which zTerm/nTerm is
** a prefix.
**
** If an OOM error occurs, SQLITE_NOMEM is returned. Otherwise, SQLITE_OK.
*/
static int fts3ScanInteriorNode(
  Fts3Table *p,                   /* Virtual table handle */
  const char *zTerm,              /* Term to select leaves for */
  int nTerm,                      /* Size of term zTerm in bytes */
  const char *zNode,              /* Buffer containing segment interior node */
  int nNode,                      /* Size of buffer at zNode */
  sqlite3_int64 *piFirst,         /* OUT: Selected child node */
  sqlite3_int64 *piLast           /* OUT: Selected child node */
){
  int rc = SQLITE_OK;             /* Return code */
  const char *zCsr = zNode;       /* Cursor to iterate through node */
  const char *zEnd = &zCsr[nNode];/* End of interior node buffer */
  char *zBuffer = 0;              /* Buffer to load terms into */
  int nAlloc = 0;                 /* Size of allocated buffer */

  int isFirstTerm = 1;            /* True when processing first term on page */

  sqlite3_int64 iChild;           /* Block id of child node to descend to */


  /* Skip over the 'height' varint that occurs at the start of every 
  ** interior node. Then load the blockid of the left-child of the b-tree
  ** node into variable iChild.  */
  zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);
  zCsr += sqlite3Fts3GetVarint(zCsr, &iChild);
  
  while( zCsr<zEnd && (piFirst || piLast) ){
    int cmp;                      /* memcmp() result */
    int nSuffix;                  /* Size of term suffix */
    int nPrefix = 0;              /* Size of term prefix */
    int nBuffer;                  /* Total term size */
  
    /* Load the next term on the node into zBuffer. Use realloc() to expand
    ** the size of zBuffer if required.  */
    if( !isFirstTerm ){
      zCsr += sqlite3Fts3GetVarint32(zCsr, &nPrefix);
    }
    isFirstTerm = 0;
    zCsr += sqlite3Fts3GetVarint32(zCsr, &nSuffix);
    if( nPrefix+nSuffix>nAlloc ){
      char *zNew;

  sqlite3_free(zBuffer);
  return rc;
}


/*
** The buffer pointed to by argument zNode (size nNode bytes) contains an
** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)
** contains a term. This function searches the sub-tree headed by the zNode
** node for the range of leaf nodes that may contain the specified term
** or terms for which the specified term is a prefix.
**
** If piLeaf is not NULL, then *piLeaf is set to the blockid of the 
** left-most leaf node in the tree that may contain the specified term.
** If piLeaf2 is not NULL, then *piLeaf2 is set to the blockid of the
** right-most leaf node that may contain a term for which the specified
** term is a prefix.
**
** It is possible that the range of returned leaf nodes does not contain 
** the specified term or any terms for which it is a prefix. However, if the 
** segment does contain any such terms, they are stored within the identified
** range. Because this function only inspects interior segment nodes (and
** never loads leaf nodes into memory), it is not possible to be sure.

**
** If an error occurs, an error code other than SQLITE_OK is returned.
*/ 
static int fts3SelectLeaf(
  Fts3Table *p,                   /* Virtual table handle */
  const char *zTerm,              /* Term to select leaves for */
  int nTerm,                      /* Size of term zTerm in bytes */
  const char *zNode,              /* Buffer containing segment interior node */
  int nNode,                      /* Size of buffer at zNode */
  sqlite3_int64 *piLeaf,          /* Selected leaf node */
  sqlite3_int64 *piLeaf2          /* Selected leaf node */
){
  int rc;                         /* Return code */
  int iHeight;                    /* Height of this node in tree */

  assert( piLeaf || piLeaf2 );

  sqlite3Fts3GetVarint32(zNode, &iHeight);
  rc = fts3ScanInteriorNode(p, zTerm, nTerm, zNode, nNode, piLeaf, piLeaf2);
  
  if( rc==SQLITE_OK && iHeight>1 ){
    char *zBlob = 0;              /* Blob read from %_segments table */
    int nBlob;                    /* Size of zBlob in bytes */

    if( piLeaf && piLeaf2 && (*piLeaf!=*piLeaf2) ){
      rc = sqlite3Fts3ReadBlock(p, *piLeaf, &zBlob, &nBlob);
      if( rc==SQLITE_OK ){
        rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, 0);
      }
      sqlite3_free(zBlob);
      piLeaf = 0;
      zBlob = 0;
    }

    rc = sqlite3Fts3ReadBlock(p, piLeaf ? *piLeaf : *piLeaf2, &zBlob, &nBlob);
    if( rc==SQLITE_OK ){
      rc = fts3SelectLeaf(p, zTerm, nTerm, zBlob, nBlob, piLeaf, piLeaf2);
    }
    sqlite3_free(zBlob);
  }

  return rc;
}

/*
** This function is used to create delta-encoded serialized lists of FTS3 

    if( sqlite3_column_int64(pStmt, 1)==0 ){
      /* The entire segment is stored on the root node (which must be a
      ** leaf). Do not bother inspecting any data in this case, just
      ** create a Fts3SegReader to scan the single leaf. 
      */
      rc = sqlite3Fts3SegReaderNew(p, iAge, 0, 0, 0, zRoot, nRoot, &pNew);
    }else{

      sqlite3_int64 i1;           /* First leaf that may contain zTerm */
      sqlite3_int64 i2;           /* Final leaf that may contain zTerm */
      rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &i1, (isPrefix?&i2:0));
      if( isPrefix==0 ) i2 = i1;
      if( rc==SQLITE_OK ){
        rc = sqlite3Fts3SegReaderNew(p, iAge, i1, i2, 0, 0, 0, &pNew);
      }
    }







    assert( (pNew==0)==(rc!=SQLITE_OK) );





    /* If a new Fts3SegReader was allocated, add it to the array. */

    if( rc==SQLITE_OK ){
      rc = fts3SegReaderArrayAdd(&pArray, pNew);


    }
    if( rc==SQLITE_OK ){
      rc = sqlite3Fts3SegReaderCost(pCsr, pNew, &pArray->nCost);
    }
    iAge++;
  }

  if( rc==SQLITE_DONE ){
    rc = sqlite3_reset(pStmt);
  }else{
    sqlite3_reset(pStmt);
  }

        }
      }
    }
  }
  return rc;
}

/*
** This function removes the position information from a doclist. When
** called, buffer aList (size *pnList bytes) contains a doclist that includes
** position information. This function removes the position information so
** that aList contains only docids, and adjusts *pnList to reflect the new
** (possibly reduced) size of the doclist.
*/
static void fts3DoclistStripPositions(
  char *aList,                    /* IN/OUT: Buffer containing doclist */
  int *pnList                     /* IN/OUT: Size of doclist in bytes */
){
  if( aList ){
    char *aEnd = &aList[*pnList]; /* Pointer to one byte after EOF */
    char *p = aList;              /* Input cursor */
    char *pOut = aList;           /* Output cursor */

  
    while( p<aEnd ){
      sqlite3_int64 delta;
      p += sqlite3Fts3GetVarint(p, &delta);
      fts3PoslistCopy(0, &p);
      pOut += sqlite3Fts3PutVarint(pOut, delta);
    }

    *pnOut = nOut;
  }else{
    sqlite3_free(pOut);
  }
  return rc;
}

/*
** This function merges two doclists according to the requirements of a
** NEAR operator.
**
** Both input doclists must include position information. The output doclist 
** includes position information if the first argument to this function
** is MERGE_POS_NEAR, or does not if it is MERGE_NEAR.
*/
static int fts3NearMerge(
  int mergetype,                  /* MERGE_POS_NEAR or MERGE_NEAR */
  int nNear,                      /* Parameter to NEAR operator */
  int nTokenLeft,                 /* Number of tokens in LHS phrase arg */
  char *aLeft,                    /* Doclist for LHS (incl. positions) */
  int nLeft,                      /* Size of LHS doclist in bytes */
  int nTokenRight,                /* As nTokenLeft */
  char *aRight,                   /* As aLeft */
  int nRight,                     /* As nRight */
  char **paOut,                   /* OUT: Results of merge (malloced) */
  int *pnOut                      /* OUT: Sized of output buffer */
){
  char *aOut;                     /* Buffer to write output doclist to */
  int rc;                         /* Return code */

  assert( mergetype==MERGE_POS_NEAR || MERGE_NEAR );

  aOut = sqlite3_malloc(nLeft+nRight+1);
  if( aOut==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = fts3DoclistMerge(mergetype, nNear+nTokenRight, nNear+nTokenLeft, 
      aOut, pnOut, aLeft, nLeft, aRight, nRight, 0
    );
    if( rc!=SQLITE_OK ){
      sqlite3_free(aOut);
      aOut = 0;
    }
  }

  *paOut = aOut;
  return rc;
}

/*
** This function is used as part of the processing for the snippet() and
** offsets() functions.
**
** Both pLeft and pRight are expression nodes of type FTSQUERY_PHRASE. Both
** have their respective doclists (including position information) loaded
** in Fts3Expr.aDoclist/nDoclist. This function removes all entries from
** each doclist that are not within nNear tokens of a corresponding entry
** in the other doclist.
*/
int sqlite3Fts3ExprNearTrim(Fts3Expr *pLeft, Fts3Expr *pRight, int nNear){
  int rc;                         /* Return code */

  assert( pLeft->eType==FTSQUERY_PHRASE );
  assert( pRight->eType==FTSQUERY_PHRASE );
  assert( pLeft->isLoaded && pRight->isLoaded );

  if( pLeft->aDoclist==0 || pRight->aDoclist==0 ){
    sqlite3_free(pLeft->aDoclist);
    sqlite3_free(pRight->aDoclist);
    pRight->aDoclist = 0;
    pLeft->aDoclist = 0;
    rc = SQLITE_OK;
  }else{
    char *aOut;                   /* Buffer in which to assemble new doclist */
    int nOut;                     /* Size of buffer aOut in bytes */

    rc = fts3NearMerge(MERGE_POS_NEAR, nNear, 
        pLeft->pPhrase->nToken, pLeft->aDoclist, pLeft->nDoclist,
        pRight->pPhrase->nToken, pRight->aDoclist, pRight->nDoclist,
        &aOut, &nOut
    );
    if( rc!=SQLITE_OK ) return rc;

    sqlite3_free(pLeft->aDoclist);
    pLeft->aDoclist = aOut;
    pLeft->nDoclist = nOut;
  }
  return rc;
}









/*
** Allocate an Fts3SegReaderArray for each token in the expression pExpr. 
** The allocated objects are stored in the Fts3PhraseToken.pArray member










** variables of each token structure.













*/
static int fts3ExprAllocateSegReaders(
  Fts3Cursor *pCsr,               /* FTS3 table */
  Fts3Expr *pExpr,                /* Expression to create seg-readers for */
  int *pnExpr                     /* OUT: Number of AND'd expressions */
){
  int rc = SQLITE_OK;             /* Return code */

  if( pCsr->doDeferred ) return SQLITE_OK;
  if( pnExpr && pExpr->eType!=FTSQUERY_AND ){
    (*pnExpr)++;
    pnExpr = 0;
  }

  if( pExpr->eType==FTSQUERY_PHRASE ){

    Fts3Phrase *pPhrase = pExpr->pPhrase;
    int ii;

    for(ii=0; rc==SQLITE_OK && ii<pPhrase->nToken; ii++){
      Fts3PhraseToken *pTok = &pPhrase->aToken[ii];
      if( pTok->pArray==0 ){
        rc = fts3TermSegReaderArray(
            pCsr, pTok->z, pTok->n, pTok->isPrefix, &pTok->pArray
        );
      }
    }
  }else{ 
    rc = fts3ExprAllocateSegReaders(pCsr, pExpr->pLeft, pnExpr);
    if( rc==SQLITE_OK ){
      rc = fts3ExprAllocateSegReaders(pCsr, pExpr->pRight, pnExpr);
    }
  }
  return rc;
}

/*
** Free the Fts3SegReaderArray objects associated with each token in the
** expression pExpr. In other words, this function frees the resources
** allocated by fts3ExprAllocateSegReaders().
*/
static void fts3ExprFreeSegReaders(Fts3Expr *pExpr){
  if( pExpr ){
    Fts3Phrase *pPhrase = pExpr->pPhrase;
    if( pPhrase ){
      int kk;
      for(kk=0; kk<pPhrase->nToken; kk++){
        fts3SegReaderArrayFree(pPhrase->aToken[kk].pArray);
        pPhrase->aToken[kk].pArray = 0;
      }
    }
    fts3ExprFreeSegReaders(pExpr->pLeft);
    fts3ExprFreeSegReaders(pExpr->pRight);
  }
}

/*
** Return the sum of the costs of all tokens in the expression pExpr. This
** function must be called after Fts3SegReaderArrays have been allocated
** for all tokens using fts3ExprAllocateSegReaders().
*/
int fts3ExprCost(Fts3Expr *pExpr){
  int nCost;                      /* Return value */
  if( pExpr->eType==FTSQUERY_PHRASE ){
    Fts3Phrase *pPhrase = pExpr->pPhrase;
    int ii;
    nCost = 0;
    for(ii=0; ii<pPhrase->nToken; ii++){
      nCost += pPhrase->aToken[ii].pArray->nCost;
    }
  }else{
    nCost = fts3ExprCost(pExpr->pLeft) + fts3ExprCost(pExpr->pRight);
  }
  return nCost;
}

/*
** The following is a helper function (and type) for fts3EvalExpr(). It
** must be called after Fts3SegReaders have been allocated for every token
** in the expression. See the context it is called from in fts3EvalExpr()
** for further explanation.
*/
typedef struct ExprAndCost ExprAndCost;
struct ExprAndCost {
  Fts3Expr *pExpr;
  int nCost;
};
static void fts3ExprAssignCosts(
  Fts3Expr *pExpr,                /* Expression to create seg-readers for */
  ExprAndCost **ppExprCost        /* OUT: Write to *ppExprCost */
){
  if( pExpr->eType==FTSQUERY_AND ){
    fts3ExprAssignCosts(pExpr->pLeft, ppExprCost);
    fts3ExprAssignCosts(pExpr->pRight, ppExprCost);
  }else{
    (*ppExprCost)->pExpr = pExpr;
    (*ppExprCost)->nCost = fts3ExprCost(pExpr);;
    (*ppExprCost)++;
  }
}

/*
** Evaluate the full-text expression pExpr against FTS3 table pTab. Store
** the resulting doclist in *paOut and *pnOut. This routine mallocs for
** the space needed to store the output. The caller is responsible for
** freeing the space when it has finished.
**
** This function is called in two distinct contexts:
**
**   * From within the virtual table xFilter() method. In this case, the
**     output doclist contains entries for all rows in the table, based on
**     data read from the full-text index.
**
**     In this case, if the query expression contains one or more tokens that 
**     are very common, then the returned doclist may contain a superset of 
**     the documents that actually match the expression.
**
**   * From within the virtual table xNext() method. This call is only made
**     if the call from within xFilter() found that there were very common 
**     tokens in the query expression and did return a superset of the 
**     matching documents. In this case the returned doclist contains only
**     entries that correspond to the current row of the table. Instead of
**     reading the data for each token from the full-text index, the data is
**     already available in-memory in the Fts3PhraseToken.pDeferred structures.
**     See fts3EvalDeferred() for how it gets there.
**
** In the first case above, Fts3Cursor.doDeferred==0. In the second (if it is
** required) Fts3Cursor.doDeferred==1.
**
** If the SQLite invokes the snippet(), offsets() or matchinfo() function
** as part of a SELECT on an FTS3 table, this function is called on each
** individual phrase expression in the query. If there were very common tokens
** found in the xFilter() call, then this function is called once for phrase
** for each row visited, and the returned doclist contains entries for the
** current row only. Otherwise, if there were no very common tokens, then this
** function is called once only for each phrase in the query and the returned
** doclist contains entries for all rows of the table.
**
** Fts3Cursor.doDeferred==1 when this function is called on phrases as a
** result of a snippet(), offsets() or matchinfo() invocation.
*/
static int fts3EvalExpr(
  Fts3Cursor *p,                  /* Virtual table cursor handle */
  Fts3Expr *pExpr,                /* Parsed fts3 expression */
  char **paOut,                   /* OUT: Pointer to malloc'd result buffer */
  int *pnOut,                     /* OUT: Size of buffer at *paOut */
  int isReqPos                    /* Require positions in output buffer */

    }
  }

  return rc;
}

/*
** This function is called from within xNext() for each row visited by
** an FTS3 query. If evaluating the FTS3 query expression within xFilter()
** was able to determine the exact set of matching rows, this function sets
** *pbRes to true and returns SQLITE_IO immediately.
**
** Otherwise, if evaluating the query expression within xFilter() returned a
** superset of the matching documents instead of an exact set (this happens
** when the query includes very common tokens and it is deemed too expensive to
** load their doclists from disk), this function tests if the current row
** really does match the FTS3 query.
**
** If an error occurs, an SQLite error code is returned. Otherwise, SQLITE_OK
** is returned and *pbRes is set to true if the current row matches the
** FTS3 query (and should be included in the results returned to SQLite), or
** false otherwise.
*/
static int fts3EvalDeferred(
  Fts3Cursor *pCsr,               /* FTS3 cursor pointing at row to test */
  int *pbRes                      /* OUT: Set to true if row is a match */
){
  int rc = SQLITE_OK;
  if( pCsr->pDeferred==0 ){
    *pbRes = 1;
  }else{
    rc = fts3CursorSeek(0, pCsr);
    if( rc==SQLITE_OK ){
      sqlite3Fts3FreeDeferredDoclists(pCsr);

** in the %_content table.
**
** If idxNum>=FTS3_FULLTEXT_SEARCH then use the full text index.  The
** column on the left-hand side of the MATCH operator is column
** number idxNum-FTS3_FULLTEXT_SEARCH, 0 indexed.  argv[0] is the right-hand
** side of the MATCH operator.
*/





static int fts3FilterMethod(
  sqlite3_vtab_cursor *pCursor,   /* The cursor used for this query */
  int idxNum,                     /* Strategy index */
  const char *idxStr,             /* Unused */
  int nVal,                       /* Number of elements in apVal */
  sqlite3_value **apVal           /* Arguments for the indexing scheme */
){

** rowid should be written to *pRowid.
*/
static int fts3RowidMethod(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
  Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
  if( pCsr->aDoclist ){
    *pRowid = pCsr->iPrevId;
  }else{
    /* This branch runs if the query is implemented using a full-table scan
    ** (not using the full-text index). In this case grab the rowid from the
    ** SELECT statement.
    */
    assert( pCsr->isRequireSeek==0 );
    *pRowid = sqlite3_column_int64(pCsr->pStmt, 0);
  }
  return SQLITE_OK;
}

/* 
** This is the xColumn method, called by SQLite to request a value from

static void hashDestroy(void *p){
  Fts3Hash *pHash = (Fts3Hash *)p;
  sqlite3Fts3HashClear(pHash);
  sqlite3_free(pHash);
}

/*
** The fts3 built-in tokenizers - "simple", "porter" and "icu"- are 
** implemented in files fts3_tokenizer1.c, fts3_porter.c and fts3_icu.c
** respectively. The following three forward declarations are for functions
** declared in these files used to retrieve the respective implementations.
**
** Calling sqlite3Fts3SimpleTokenizerModule() sets the value pointed
** to by the argument to point to the "simple" tokenizer implementation.

** And so on.
*/
void sqlite3Fts3SimpleTokenizerModule(sqlite3_tokenizer_module const**ppModule);
void sqlite3Fts3PorterTokenizerModule(sqlite3_tokenizer_module const**ppModule);
#ifdef SQLITE_ENABLE_ICU
void sqlite3Fts3IcuTokenizerModule(sqlite3_tokenizer_module const**ppModule);
#endif

/*
** Initialise the fts3 extension. If this extension is built as part
** of the sqlite library, then this function is called directly by
** SQLite. If fts3 is built as a dynamically loadable extension, this
** function is called by the sqlite3_extension_init() entry point.
*/

  int nColumn;                    /* number of named columns in virtual table */
  char **azColumn;                /* column names.  malloced */
  sqlite3_tokenizer *pTokenizer;  /* tokenizer for inserts and queries */

  /* Precompiled statements used by the implementation. Each of these 
  ** statements is run and reset within a single virtual table API call. 
  */
  sqlite3_stmt *aStmt[24];



  int nNodeSize;                  /* Soft limit for node size */
  u8 bHasContent;                 /* True if %_content table exists */
  u8 bHasDocsize;                 /* True if %_docsize table exists */
  int nPgsz;                      /* Page size for host database */
  char *zSegmentsTbl;             /* Name of %_segments table */
  sqlite3_blob *pSegments;        /* Blob handle open on %_segments table */

  /* The following hash table is used to buffer pending index updates during
  ** transactions. Variable nPendingData estimates the memory size of the 
  ** pending data, including hash table overhead, but not malloc overhead. 
  ** When nPendingData exceeds nMaxPendingData, the buffer is flushed 
  ** automatically. Variable iPrevDocid is the docid of the most recently

  Fts3DeferredToken *pDeferred;   /* Deferred search tokens, if any */
  sqlite3_int64 iPrevId;          /* Previous id read from aDoclist */
  char *pNextId;                  /* Pointer into the body of aDoclist */
  char *aDoclist;                 /* List of docids for full-text queries */
  int nDoclist;                   /* Size of buffer at aDoclist */
  int isMatchinfoNeeded;          /* True when aMatchinfo[] needs filling in */
  u32 *aMatchinfo;                /* Information about most recent match */

  int doDeferred;
  int nRowAvg;                    /* Average size of database rows, in pages */
};

/*
** The Fts3Cursor.eSearch member is always set to one of the following.
** Actualy, Fts3Cursor.eSearch can be greater than or equal to

/*
** A "phrase" is a sequence of one or more tokens that must match in
** sequence.  A single token is the base case and the most common case.
** For a sequence of tokens contained in double-quotes (i.e. "one two three")
** nToken will be the number of tokens in the string.
*/

struct Fts3PhraseToken {
  char *z;                        /* Text of the token */
  int n;                          /* Number of bytes in buffer z */
  int isPrefix;                   /* True if token ends with a "*" character */
  Fts3SegReaderArray *pArray;     /* Segment-reader for this token */
  Fts3DeferredToken *pDeferred;   /* Deferred token object for this token */
};

struct Fts3Phrase {
  int nToken;                /* Number of tokens in the phrase */
  int iColumn;               /* Index of column this phrase must match */
  int isNot;                 /* Phrase prefixed by unary not (-) operator */
  Fts3PhraseToken aToken[1]; /* One entry for each token in the phrase */

#define FTSQUERY_NEAR   1
#define FTSQUERY_NOT    2
#define FTSQUERY_AND    3
#define FTSQUERY_OR     4
#define FTSQUERY_PHRASE 5







/* fts3_write.c */
int sqlite3Fts3UpdateMethod(sqlite3_vtab*,int,sqlite3_value**,sqlite3_int64*);
int sqlite3Fts3PendingTermsFlush(Fts3Table *);
void sqlite3Fts3PendingTermsClear(Fts3Table *);
int sqlite3Fts3Optimize(Fts3Table *);
int sqlite3Fts3SegReaderNew(Fts3Table *,int, sqlite3_int64,
  sqlite3_int64, sqlite3_int64, const char *, int, Fts3SegReader**);
int sqlite3Fts3SegReaderPending(Fts3Table*,const char*,int,int,Fts3SegReader**);
void sqlite3Fts3SegReaderFree(Fts3Table *, Fts3SegReader *);
int sqlite3Fts3SegReaderIterate(
  Fts3Table *, Fts3SegReader **, int, Fts3SegFilter *,
  int (*)(Fts3Table *, void *, char *, int, char *, int),  void *
);
int sqlite3Fts3SegReaderCost(Fts3Cursor *, Fts3SegReader *, int *);
int sqlite3Fts3AllSegdirs(Fts3Table*, sqlite3_stmt **);
int sqlite3Fts3MatchinfoDocsizeLocal(Fts3Cursor*, u32*);
int sqlite3Fts3MatchinfoDocsizeGlobal(Fts3Cursor*, u32*);
int sqlite3Fts3ReadLock(Fts3Table *);
int sqlite3Fts3ReadBlock(Fts3Table*, sqlite3_int64, char **, int*);

void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *);
int sqlite3Fts3DeferToken(Fts3Cursor *, Fts3PhraseToken *, int);
int sqlite3Fts3CacheDeferredDoclists(Fts3Cursor *);
void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *);
char *sqlite3Fts3DeferredDoclist(Fts3DeferredToken *, int *);

struct Fts3SegReader {
  int iIdx;                       /* Index within level, or 0x7FFFFFFF for PT */

  sqlite3_int64 iStartBlock;      /* Rowid of first leaf block to traverse */
  sqlite3_int64 iLeafEndBlock;    /* Rowid of final leaf block to traverse */
  sqlite3_int64 iEndBlock;        /* Rowid of final block in segment (or 0) */
  sqlite3_int64 iCurrentBlock;    /* Current leaf block (or 0) */


  char *aNode;                    /* Pointer to node data (or NULL) */
  int nNode;                      /* Size of buffer at aNode (or 0) */

  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 */
  int nTermAlloc;                 /* Allocated size of zTerm buffer */
  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 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_DELETE_DOCSIZE            19
#define SQL_REPLACE_DOCSIZE           20
#define SQL_SELECT_DOCSIZE            21
#define SQL_SELECT_DOCTOTAL           22
#define SQL_REPLACE_DOCTOTAL          23

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

/* 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 */  "DELETE FROM %Q.'%q_docsize' WHERE docid = ?",
/* 20 */  "REPLACE INTO %Q.'%q_docsize' VALUES(?,?)",
/* 21 */  "SELECT size FROM %Q.'%q_docsize' WHERE docid=?",
/* 22 */  "SELECT value FROM %Q.'%q_stat' WHERE id=0",
/* 23 */  "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 );
  

    sqlite3_step(pStmt);
    rc = sqlite3_reset(pStmt);
  }
  *pRC = rc;
}









































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

    int rc = sqlite3Fts3PendingTermsFlush(p);
    if( rc!=SQLITE_OK ) return rc;
  }
  p->iPrevDocid = iDocid;
  return SQLITE_OK;
}

/*
** Discard the contents of the pending-terms hash table. 
*/
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;

  return rc;
}

/*
** The %_segments table is declared as follows:
**
**   CREATE TABLE %_segments(blockid INTEGER PRIMARY KEY, block BLOB)
**
** This function reads data from a single row of the %_segments table. The
** specific row is identified by the iBlockid parameter. If paBlob is not
** NULL, then a buffer is allocated using sqlite3_malloc() and populated
** with the contents of the blob stored in the "block" column of the 
** identified table row is. Whether or not paBlob is NULL, *pnBlob is set
** to the size of the blob in bytes before returning.
**
** If an error occurs, or the table does not contain the specified row,
** an SQLite error code is returned. Otherwise, SQLITE_OK is returned. If
** paBlob is non-NULL, then it is the responsibility of the caller to
** eventually free the returned buffer.
**
** This function may leave an open sqlite3_blob* handle in the
** Fts3Table.pSegments variable. This handle is reused by subsequent calls
** to this function. The handle may be closed by calling the
** sqlite3Fts3SegmentsClose() function. Reusing a blob handle is a handy
** performance improvement, but the blob handle should always be closed
** before control is returned to the user (to prevent a lock being held
** on the database file for longer than necessary). Thus, any virtual table
** method (xFilter etc.) that may directly or indirectly call this function
** must call sqlite3Fts3SegmentsClose() before returning.
*/
int sqlite3Fts3ReadBlock(
  Fts3Table *p,                   /* FTS3 table handle */
  sqlite3_int64 iBlockid,         /* Access the row with blockid=$iBlockid */
  char **paBlob,                  /* OUT: Blob data in malloc'd buffer */
  int *pnBlob                     /* OUT: Size of blob data */
){
  int rc;                         /* Return code */

  /* pnBlob must be non-NULL. paBlob may be NULL or non-NULL. */
  assert( pnBlob);

  if( p->pSegments ){
    rc = sqlite3_blob_reopen(p->pSegments, iBlockid);
  }else{
    if( 0==p->zSegmentsTbl ){
      p->zSegmentsTbl = sqlite3_mprintf("%s_segments", p->zName);
      if( 0==p->zSegmentsTbl ) return SQLITE_NOMEM;
    }
    rc = sqlite3_blob_open(
       p->db, p->zDb, p->zSegmentsTbl, "block", iBlockid, 0, &p->pSegments
    );
  }

  if( rc==SQLITE_OK ){
    int nByte = sqlite3_blob_bytes(p->pSegments);
    if( paBlob ){
      char *aByte = sqlite3_malloc(nByte);

    }
    *pnBlob = nByte;
  }

  return rc;
}

/*
** Close the blob handle at p->pSegments, if it is open. See comments above
** the sqlite3Fts3ReadBlock() function for details.
*/
void sqlite3Fts3SegmentsClose(Fts3Table *p){
  sqlite3_blob_close(p->pSegments);
  p->pSegments = 0;
}


/*
** 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(Fts3Table *p, 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;                       /* Return code from Fts3ReadBlock() */

    if( fts3SegReaderIsPending(pReader) ){
      Fts3HashElem *pElem = *(pReader->ppNextElem);
      if( pElem==0 ){
        pReader->aNode = 0;
      }else{
        PendingList *pList = (PendingList *)fts3HashData(pElem);

    if( !fts3SegReaderIsRootOnly(pReader) ){
      sqlite3_free(pReader->aNode);
    }
    pReader->aNode = 0;

    /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf 
    ** blocks have already been traversed.  */
    assert( pReader->iCurrentBlock<=pReader->iLeafEndBlock );
    if( pReader->iCurrentBlock>=pReader->iLeafEndBlock ){
      return SQLITE_OK;
    }

    rc = sqlite3Fts3ReadBlock(
        p, ++pReader->iCurrentBlock, &pReader->aNode, &pReader->nNode
    );

    if( rc!=SQLITE_OK ) return rc;


    pNext = pReader->aNode;
  }
  
  pNext += sqlite3Fts3GetVarint32(pNext, &nPrefix);
  pNext += sqlite3Fts3GetVarint32(pNext, &nSuffix);

  if( nPrefix+nSuffix>pReader->nTermAlloc ){

  Fts3Cursor *pCsr,               /* FTS3 cursor handle */
  Fts3SegReader *pReader,         /* Segment-reader handle */
  int *pnCost                     /* IN/OUT: Number of bytes read */
){
  Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
  int rc = SQLITE_OK;             /* Return code */
  int nCost = 0;                  /* Cost in bytes to return */

  int pgsz = p->nPgsz;            /* Database page size */

  /* If this seg-reader is reading the pending-terms table, or if all data
  ** for the segment is stored on the root page of the b-tree, then the cost
  ** is zero. In this case all required data is already in main memory.
  */
  if( p->bHasDocsize 

    }

    /* Assume that a blob flows over onto overflow pages if it is larger
    ** than (pgsz-35) bytes in size (the file-format documentation
    ** confirms this).
    */
    for(iBlock=pReader->iStartBlock; iBlock<=pReader->iLeafEndBlock; iBlock++){
      rc = sqlite3Fts3ReadBlock(p, iBlock, 0, &nBlob);
      if( rc!=SQLITE_OK ) break;
      if( (nBlob+35)>pgsz ){
        int nOvfl = (nBlob + 34)/pgsz;
        nCost += ((nOvfl + pCsr->nRowAvg - 1)/pCsr->nRowAvg);
      }
    }
  }

    pReader->nNode = nRoot;
    memcpy(pReader->aNode, zRoot, nRoot);
  }else{
    pReader->iCurrentBlock = iStartLeaf-1;
  }
  rc = fts3SegReaderNext(p, pReader);


  if( rc==SQLITE_OK ){
    *ppReader = pReader;
  }else{
    sqlite3Fts3SegReaderFree(p, pReader);
  }
  return rc;
}

}

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

** 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 = 0;              /* 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 */

    sqlite3_tokenizer *pT = p->pTokenizer;
    sqlite3_tokenizer_module const *pModule = pT->pModule;
   
    assert( pCsr->isRequireSeek==0 );
    iDocid = sqlite3_column_int64(pCsr->pStmt, 0);
  
    for(i=0; i<p->nColumn && rc==SQLITE_OK; i++){
      const char *zText = (const char *)sqlite3_column_text(pCsr->pStmt, i+1);
      sqlite3_tokenizer_cursor *pTC = 0;
  
      rc = pModule->xOpen(pT, zText, -1, &pTC);
      while( rc==SQLITE_OK ){
        char const *zToken;       /* Buffer containing token */
        int nToken;               /* Number of bytes in token */
        int iDum1, iDum2;         /* Dummy variables */

  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 = 0;
    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.
        */

# 2009 December 03
#
#    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.
#
#***********************************************************************
#
# The tests in this file are structural coverage tests for FTS3.


#

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

# If this build does not include FTS3, skip the tests in this file.
#

do_test fts3cov-2.2 {
  set root [db one {SELECT root FROM t1_segdir}]
  read_fts3varint [string range $root 1 end] left_child
  execsql { DELETE FROM t1_segments WHERE blockid = $left_child }
} {}
do_error_test fts3cov-2.3 {
  SELECT * FROM t1 WHERE t1 MATCH 'c*'
} {SQL logic error or missing database}

# Test the "replaced with NULL" case:
do_test fts3cov-2.4 {
  execsql { INSERT INTO t1_segments VALUES($left_child, NULL) }
} {}
do_error_test fts3cov-2.5 {
  SELECT * FROM t1 WHERE t1 MATCH 'cloud'
} {SQL logic error or missing database}

#--------------------------------------------------------------------------
# The following tests are to test the effects of OOM errors while storing
# terms in the pending-hash table. Specifically, while creating doclist
# blobs to store in the table. More specifically, to test OOM errors while
# appending column numbers to doclists. For example, if a doclist consists
# of: