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;
        pReader->aNode = pReader->aDoclist = pList->aData;
        pReader->ppNextElem++;

      }
      return SQLITE_OK;
    }
    if( !pReader->pStmt ){
      pReader->aNode = 0;
      return SQLITE_OK;
    }
................................................................................
){
  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 ){

    Fts3HashElem *pE = 0;         /* Iterator variable */

    for(pE=fts3HashFirst(&p->pendingTerms); pE; pE=fts3HashNext(pE)){
      char *zKey = (char *)fts3HashKey(pE);
      int nKey = fts3HashKeysize(pE);
      if( nKey>=nTerm && 0==memcmp(zKey, zTerm, nTerm) ){

        int nByte = (1+nElem * sizeof(Fts3HashElem *));

        Fts3HashElem **aElem2 = (Fts3HashElem **)sqlite3_realloc(aElem, nByte);


        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.
................................................................................
  int rc;                         /* Return code */
  int iIdx;                       /* Index of new segment */
  int iNewLevel;                  /* Level to create new segment at */
  sqlite3_stmt *pStmt;
  SegmentWriter *pWriter = 0;
  int nSegment = 0;               /* Number of segments being merged */
  Fts3SegReader **apSegment = 0;  /* Array of Segment iterators */

  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 = fts3SegmentCountMax(p, &nSegment, &iNewLevel);

    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.
................................................................................
  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);



  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,
................................................................................
}


/* 
** Flush the contents of pendingTerms to a level 0 segment.
*/
int sqlite3Fts3PendingTermsFlush(Fts3Table *p){
  Fts3HashElem *pElem;
  int idx, rc, i;
  Fts3HashElem **apElem;          /* Array of pointers to hash elements */
  int nElem;                      /* Number of terms in new segment */

  SegmentWriter *pWriter = 0;     /* Used to write the segment */



  /* Find the number of terms that will make up the new segment. If there
  ** are no terms, return early (do not bother to write an empty segment).
  */
  nElem = fts3HashCount(&p->pendingTerms);
  if( nElem==0 ){
    assert( p->nPendingData==0 );
    return SQLITE_OK;
  }

  /* Determine the next index at level 0, merging as necessary. */



  rc = fts3AllocateSegdirIdx(p, 0, &idx);
  if( rc!=SQLITE_OK ){
    return rc;
  } 


  apElem = sqlite3_malloc(nElem*sizeof(Fts3HashElem *));
  if( !apElem ){
    return SQLITE_NOMEM;
  }

  i = 0;
  for(pElem=fts3HashFirst(&p->pendingTerms); pElem; pElem=fts3HashNext(pElem)){
    apElem[i++] = pElem;
  }
  assert( i==nElem );

  /* TODO(shess) Should we allow user-defined collation sequences,
  ** here?  I think we only need that once we support prefix searches.
  ** Also, should we be using qsort()?
  */
  if( nElem>1 ){
    qsort(apElem, nElem, sizeof(Fts3HashElem *), fts3CompareElemByTerm);



  }






  /* Write the segment tree into the database. */
  for(i=0; rc==SQLITE_OK && i<nElem; i++){
    const char *z = fts3HashKey(apElem[i]);
    int n = fts3HashKeysize(apElem[i]);
    PendingList *pList = fts3HashData(apElem[i]);
    rc = fts3SegWriterAdd(p, &pWriter, 0, z, n, pList->aData, pList->nData+1);
  }




  if( rc==SQLITE_OK ){
    rc = fts3SegWriterFlush(p, pWriter, 0, idx);
  }

  /* Free all allocated resources before returning */
  fts3SegWriterFree(pWriter);


  sqlite3_free(apElem);
  sqlite3Fts3PendingTermsClear(p);





























  return rc;
}

/*
** This function does the work for the xUpdate method of FTS3 virtual
** tables.
*/
................................................................................
  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 */


  /* 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 ){
................................................................................
          rc = fts3DeleteTerms(p, apVal);
          if( rc==SQLITE_OK ){
            rc = fts3SqlExec(p, SQL_DELETE_CONTENT, apVal);
          }
        }
      }
    }


  }
  
  /* 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);
................................................................................
** 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 = sqlite3Fts3PendingTermsFlush(p);
    if( rc==SQLITE_OK ){
      rc = fts3SegmentMerge(p, -1);
    }
    if( rc==SQLITE_OK ){
      rc = sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);



    }else{
      sqlite3_exec(p->db, "ROLLBACK TO fts3", 0, 0, 0);
      sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);
    }
  }
  return rc;
}

#endif

      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;
    }
................................................................................
){
  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.
................................................................................
  int rc;                         /* Return code */
  int iIdx;                       /* Index of new segment */
  int iNewLevel;                  /* Level to create new segment at */
  sqlite3_stmt *pStmt;
  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.
    */
    rc = sqlite3Fts3SegReaderPending(p, 0, 0, 1, &pPending);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    iIdx = 0;
    rc = fts3SegmentCountMax(p, &nSegment, &iNewLevel);
    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.
................................................................................
  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;
  }
  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,
................................................................................
}


/* 
** 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, fts3MergeCallback, 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;
}

/*
** 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 = 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 ){
      rc = SQLITE_OK;
      sqlite3Fts3PendingTermsClear(p);
    }
  }else{
    rc = SQLITE_ERROR;
  }

  return rc;
}

/*
** This function does the work for the xUpdate method of FTS3 virtual
** tables.
*/
................................................................................
  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 */


  /* 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 ){
................................................................................
          rc = fts3DeleteTerms(p, apVal);
          if( rc==SQLITE_OK ){
            rc = fts3SqlExec(p, SQL_DELETE_CONTENT, apVal);
          }
        }
      }
    }
  }else if( sqlite3_value_type(apVal[p->nColumn+2])!=SQLITE_NULL ){
    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);
................................................................................
** 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

  INSERT INTO docs VALUES('"which is for Solomon," meaning that');
}
write_test 1.2.2.4 docs_content {
  INSERT INTO docs VALUES('the book is dedicated to Solomon.');
}
read_test  1.2.2.5 { SELECT count(*) FROM docs_segdir } {3}
write_test 1.2.2.6 docs_segdir {
  SELECT * FROM (SELECT optimize(docs) FROM docs LIMIT 1) WHERE 0;
}
read_test  1.2.2.7 { SELECT count(*) FROM docs_segdir } {1}
ddl_test   1.2.2.8 { DROP TABLE docs }

##########################################################################
# Test the examples in section 1.3 (querying FTS3 tables)
#

  INSERT INTO docs VALUES('"which is for Solomon," meaning that');
}
write_test 1.2.2.4 docs_content {
  INSERT INTO docs VALUES('the book is dedicated to Solomon.');
}
read_test  1.2.2.5 { SELECT count(*) FROM docs_segdir } {3}
write_test 1.2.2.6 docs_segdir {
  INSERT INTO docs(docs) VALUES('optimize');
}
read_test  1.2.2.7 { SELECT count(*) FROM docs_segdir } {1}
ddl_test   1.2.2.8 { DROP TABLE docs }

##########################################################################
# Test the examples in section 1.3 (querying FTS3 tables)
#