SQLite

  if( *pp>=pEnd ){
    *pp = 0;
  }else{
    fts3GetDeltaVarint(pp, pVal);
  }
}






/*
** The xDisconnect() virtual table method.
*/
static int fts3DisconnectMethod(sqlite3_vtab *pVtab){
  Fts3Table *p = (Fts3Table *)pVtab;
  int i;

  int nByte;                      /* Size of allocation used for *p */
  int iCol;
  int nString = 0;
  int nCol = 0;
  char *zCsr;
  int nDb;
  int nName;

#ifdef SQLITE_TEST
  char *zTestParam = 0;
  if( strncmp(argv[argc-1], "test:", 5)==0 ){
    zTestParam = argv[argc-1];
    argc--;
  }
#endif

  const char *zTokenizer = 0;               /* Name of tokenizer to use */
  sqlite3_tokenizer *pTokenizer = 0;        /* Tokenizer for this table */

  nDb = (int)strlen(argv[1]) + 1;
  nName = (int)strlen(argv[2]) + 1;
  for(i=3; i<argc; i++){

  memset(p, 0, nByte);

  p->db = db;
  p->nColumn = nCol;
  p->nPendingData = 0;
  p->azColumn = (char **)&p[1];
  p->pTokenizer = pTokenizer;
  p->nNodeSize = 1000;
  zCsr = (char *)&p->azColumn[nCol];

  fts3HashInit(&p->pendingTerms, FTS3_HASH_STRING, 1);

  /* Fill in the zName and zDb fields of the vtab structure. */
  p->zName = zCsr;
  memcpy(zCsr, argv[2], nName);

    rc = fts3CreateTables(p);
    if( rc!=SQLITE_OK ) goto fts3_init_out;
  }

  rc = fts3DeclareVtab(p);
  if( rc!=SQLITE_OK ) goto fts3_init_out;

#ifdef SQLITE_TEST
  if( zTestParam ){
    p->nNodeSize = atoi(&zTestParam[5]);
  }
#endif
  *ppVTab = &p->base;

fts3_init_out:
  assert( p || (pTokenizer && rc!=SQLITE_OK) );
  if( rc!=SQLITE_OK ){
    if( p ){
      fts3DisconnectMethod((sqlite3_vtab *)p);

    if( rc!=SQLITE_OK ) break;
    zEnd = &zCsr[nBlock];
  }
  sqlite3_free(zBuffer);
  return rc;
}

/*
** This function is used to create delta-encoded serialized lists of FTS3 
** varints. Each call to this function appends a single varint to a list.
*/
static void fts3PutDeltaVarint(
  char **pp,                      /* IN/OUT: Output pointer */
  sqlite3_int64 *piPrev,          /* IN/OUT: Previous value written to list */
  sqlite3_int64 iVal              /* Write this value to the list */
){
  assert( iVal-*piPrev > 0 || (*piPrev==0 && iVal==0) );
  *pp += sqlite3Fts3PutVarint(*pp, iVal-*piPrev);
  *piPrev = iVal;
}

static void fts3PoslistCopy(char **pp, char **ppPoslist){
  char *pEnd = *ppPoslist;
  char c = 0;

    }else{
      sqlite3_int64 i1;
      rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &i1);
      if( rc==SQLITE_OK ){
        sqlite3_int64 i2 = sqlite3_column_int64(pStmt, 2);
        rc = sqlite3Fts3SegReaderNew(p, iAge, i1, i2, 0, 0, 0, &pNew);
      }
      sqlite3Fts3ReadBlock(p, 0, 0, 0);
    }
    iAge++;

    /* If a new Fts3SegReader was allocated, add it to the apSegment array. */
    assert( (rc==SQLITE_OK)==(pNew!=0) );
    if( pNew ){
      if( nSegment==nAlloc ){

      char *aRight;
      int nLeft;
      int nRight;

      if( SQLITE_OK==(rc = evalFts3Expr(p, pExpr->pRight, &aRight, &nRight))
       && SQLITE_OK==(rc = evalFts3Expr(p, pExpr->pLeft, &aLeft, &nLeft))
      ){
        assert( pExpr->eType==FTSQUERY_NEAR || pExpr->eType==FTSQUERY_OR     
            || pExpr->eType==FTSQUERY_AND  || pExpr->eType==FTSQUERY_NOT
        );
        switch( pExpr->eType ){
          case FTSQUERY_NEAR: {
            Fts3Expr *pLeft;
            Fts3Expr *pRight;
            int mergetype = MERGE_NEAR;
            int nParam1;
            int nParam2;

                aLeft, nLeft, aRight, nRight
            );
            *paOut = aBuffer;
            sqlite3_free(aLeft);
            break;
          }


          default: {
            assert( FTSQUERY_NOT==MERGE_NOT && FTSQUERY_AND==MERGE_AND );
            fts3DoclistMerge(pExpr->eType, 0, 0, aLeft, pnOut,
                aLeft, nLeft, aRight, nRight
            );
            *paOut = aLeft;
            break;
          }

** This is the xEof method of the virtual table. SQLite calls this 
** routine to find out if it has reached the end of a result set.
*/
static int fts3EofMethod(sqlite3_vtab_cursor *pCursor){
  return ((Fts3Cursor *)pCursor)->isEof;
}

































/* 
** This is the xRowid method. The SQLite core calls this routine to
** retrieve the rowid for the current row of the result set. fts3
** exposes %_content.docid as the rowid for the virtual table. The
** 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{
    *pRowid = sqlite3_column_int64(pCsr->pStmt, 0);
  }
  return SQLITE_OK;
}

/* 
** This is the xColumn method, called by SQLite to request a value from
** the row that the supplied cursor currently points to.
*/
static int fts3ColumnMethod(
  sqlite3_vtab_cursor *pCursor,   /* Cursor to retrieve value from */
  sqlite3_context *pContext,      /* Context for sqlite3_result_xxx() calls */
  int iCol                        /* Index of column to read value from */
){
  int rc;                         /* Return Code */
  Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
  Fts3Table *p = (Fts3Table *)pCursor->pVtab;

  /* The column value supplied by SQLite must be in range. */
  assert( iCol>=0 && iCol<=p->nColumn+1 );

  rc = fts3CursorSeek(pCsr);
  if( rc==SQLITE_OK ){
    if( iCol==p->nColumn+1 ){
      /* This call is a request for the "docid" column. Since "docid" is an 
      ** alias for "rowid", use the xRowid() method to obtain the value.
      */
      sqlite3_int64 iRowid;
      rc = fts3RowidMethod(pCursor, &iRowid);
      sqlite3_result_int64(pContext, iRowid);
    }else if( iCol==p->nColumn ){
      /* The extra column whose name is the same as the table.
      ** Return a blob which is a pointer to the cursor.
      */
      sqlite3_result_blob(pContext, &pCsr, sizeof(pCsr), SQLITE_TRANSIENT);
    }else{
      sqlite3_result_value(pContext, sqlite3_column_value(pCsr->pStmt, iCol+1));
    }
  }
  return rc;
}

/* 
** This function is the implementation of the xUpdate callback used by 
** FTS3 virtual tables. It is invoked by SQLite each time a row is to be
** inserted, updated or deleted.
*/
static int fts3UpdateMethod(

  **    ORDER BY blockid"
  */
  char *zSelectLeaves;
  int nLeavesStmt;                /* Valid statements in aLeavesStmt */
  int nLeavesTotal;               /* Total number of prepared leaves stmts */
  int nLeavesAlloc;               /* Allocated size of aLeavesStmt */
  sqlite3_stmt **aLeavesStmt;     /* Array of prepared zSelectLeaves stmts */

  int nNodeSize;                  /* Soft limit for node size */

  /* 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 FTS3_MAX_PENDING_DATA, the buffer is flushed 
  ** automatically. Variable iPrevDocid is the docid of the most recently
  ** inserted record.

#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 malloced

  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 SQLITE_CORRUPT;
    }
  
    *pnBlock = sqlite3_column_bytes(pStmt, 0);
    *pzBlock = (char *)sqlite3_column_blob(pStmt, 0);
    if( !*pzBlock ){
      return SQLITE_NOMEM;
    }
  }
  return SQLITE_OK;
}

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

    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;

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

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

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

# fts3_malloc-1.*: Test OOM during CREATE and DROP table statements.
# fts3_malloc-2.*: Test OOM during SELECT operations.
# fts3_malloc-3.*: Test OOM during SELECT operations with a larger database.
# fts3_malloc-4.*: Test OOM during database write operations.
#
#


























































































































proc normal_list {l} {
  set ret [list]
  foreach elem $l {lappend ret $elem}
  set ret
}

# 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.
#
#***********************************************************************
#
# Brute force (random data) 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.
#
ifcapable !fts3 { finish_test ; return }
source $testdir/fts3_common.tcl

set nVocab 100
set lVocab [list]

# Generate a vocabulary of nVocab words. Each word is 3 characters long.
#
set lChar {a b c d e f g h i j k l m n o p q r s t u v w x y z}
for {set i 0} {$i < $nVocab} {incr i} {
  set    word [lindex $lChar [expr int(rand()*26)]]
  append word [lindex $lChar [expr int(rand()*26)]]
  append word [lindex $lChar [expr int(rand()*26)]]
  lappend lVocab $word
}

proc random_term {} {
  lindex $::lVocab [expr {int(rand()*$::nVocab)}]
}

# Return a document consisting of $nWord arbitrarily selected terms
# from the $::lVocab list.
#
proc generate_doc {nWord} {
  set doc [list]
  for {set i 0} {$i < $nWord} {incr i} {
    lappend doc [random_term]
  }
  return $doc
}



# Primitives to update the table.
#
proc insert_row {rowid} {
  set a [generate_doc [expr int((rand()*100))]]
  set b [generate_doc [expr int((rand()*100))]]
  set c [generate_doc [expr int((rand()*100))]]
  execsql { INSERT INTO t1(docid, a, b, c) VALUES($rowid, $a, $b, $c) }
  set ::t1($rowid) [list $a $b $c]
}
proc delete_row {rowid} {
  execsql { DELETE FROM t1 WHERE rowid = $rowid }
  catch {unset ::t1($rowid)}
}
proc update_row {rowid} {
  set cols {a b c}
  set iCol [expr int(rand()*3)]
  set doc  [generate_doc [expr int((rand()*100))]]
  lset ::t1($rowid) $iCol $doc
  execsql "UPDATE t1 SET [lindex $cols $iCol] = \$doc WHERE rowid = \$rowid"
}

# Primitives to query the in-memory table.
#
proc simple_term {zTerm} {
  set ret [list]
  foreach {key value} [array get ::t1] {
    if {[string first $zTerm $value]>=0} { lappend ret $key }
  }
  lsort -integer $ret
}

foreach nodesize {50 500 1000 2000} {
  catch { array unset ::t1 }

  # Create the FTS3 table. Populate it (and the Tcl array) with 100 rows.
  #
  db transaction {
    catchsql { DROP TABLE t1 }
    execsql "CREATE VIRTUAL TABLE t1 USING fts3(a, b, c, test:$nodesize)"
    for {set i 0} {$i < 100} {incr i} { insert_row $i }
  }
  
  for {set iTest 1} {$iTest <= 100} {incr iTest} {
  
    # Delete one row, update one row and insert one row.
    #
    set rows [array names ::t1]
    set nRow [llength $rows]
    set iUpdate [lindex $rows [expr {int(rand()*$nRow)}]]
    set iDelete $iUpdate
    while {$iDelete == $iUpdate} {
      set iDelete [lindex $rows [expr {int(rand()*$nRow)}]]
    }
    set iInsert $iUpdate
    while {[info exists ::t1($iInsert)]} {
      set iInsert [expr {int(rand()*1000000)}]
    }
    db transaction {
      insert_row $iInsert
      update_row $iUpdate
      delete_row $iDelete
    }
  
    # Pick 10 terms from the vocabulary. Check that the results of querying
    # the database for the set of documents containing each of these terms
    # is the same as the result obtained by scanning the contents of the Tcl 
    # array for each term.
    #
    set n [expr {$iTest % ([llength $::lVocab]-10)}]
    foreach term [lrange $::lVocab $n [expr $n+10]] {
      do_test fts3rnd-1.$nodesize.$iTest.$term {
        execsql { SELECT docid FROM t1 WHERE t1 MATCH $term }
      } [simple_term $term]
    }

    # Similar to the above, except for phrase queries.
    #
    for {set i 0} {$i < 10} {incr i} {
      set term [list [random_term] [random_term]]
      set match "\"$term\""
      do_test fts3rnd-1.$nodesize.$iTest.$match {
        execsql { SELECT docid FROM t1 WHERE t1 MATCH $match }
      } [simple_term $term]
    }
    
    # Three word phrases.
    #
    for {set i 0} {$i < 10} {incr i} {
      set term [list [random_term] [random_term] [random_term]]
      set match "\"$term\""
      do_test fts3rnd-1.$nodesize.$iTest.$match {
        execsql { SELECT docid FROM t1 WHERE t1 MATCH $match }
      } [simple_term $term]
    }
  }
}

finish_test

  crash2.test
  crash3.test
  crash4.test
  crash5.test
  crash6.test
  crash7.test
  delete3.test
  e_fts3.test
  fts3.test
  fts3fuzz.test
  fkey_malloc.test
  fuzz.test
  fuzz3.test
  fuzz_malloc.test
  in2.test
  loadext.test
  memleak.test