/* MERGE_COUNT controls how often we merge segments (see comment at
** top of file).
*/
#define MERGE_COUNT 16

/* utility functions */

















/* We may need up to VARINT_MAX bytes to store an encoded 64-bit integer. */
#define VARINT_MAX 10

/* Write a 64-bit variable-length integer to memory starting at p[0].
 * The length of data written will be between 1 and VARINT_MAX bytes.
 * The number of bytes written is returned. */
................................................................................
  pBuffer->pData = nCapacity==0 ? NULL : malloc(nCapacity);
}
static void dataBufferReset(DataBuffer *pBuffer){
  pBuffer->nData = 0;
}
static void dataBufferDestroy(DataBuffer *pBuffer){
  if( pBuffer->pData!=NULL ) free(pBuffer->pData);
#ifndef NDEBUG
  memset(pBuffer, 0x55, sizeof(*pBuffer));
#endif
}
static void dataBufferExpand(DataBuffer *pBuffer, int nAddCapacity){
  assert( nAddCapacity>0 );
  /* TODO(shess) Consider expanding more aggressively.  Note that the
  ** underlying malloc implementation may take care of such things for
  ** us already.
  */
................................................................................
  pReader->nElement = 0;
  pReader->iDocid = 0;

  /* Load the first element's data.  There must be a first element. */
  dlrStep(pReader);
}
static void dlrDestroy(DLReader *pReader){
#ifndef NDEBUG
  memset(pReader, 0x55, sizeof(pReader));
#endif
}

#ifndef NDEBUG
/* Verify that the doclist can be validly decoded.  Also returns the
** last docid found because it's convenient in other assertions for
** DLWriter.
*/
................................................................................
  pWriter->iType = iType;
#ifndef NDEBUG
  pWriter->has_prevDocid = 0;
  pWriter->iPrevDocid = 0;
#endif
}
static void dlwDestroy(DLWriter *pWriter){
#ifndef NDEBUG
  memset(pWriter, 0x55, sizeof(pWriter));
#endif
}
static void dlwAppend(DLWriter *pWriter,
                      const char *pData, int nData){
#ifndef NDEBUG
  sqlite_int64 iDocid;
  int n;
  n = getVarint(pData, &iDocid);
................................................................................
  pReader->iColumn = 0;
  pReader->iPosition = 0;
  pReader->iStartOffset = 0;
  pReader->iEndOffset = 0;
  plrStep(pReader);
}
static void plrDestroy(PLReader *pReader){
#ifndef NDEBUG
  memset(pReader, 0x55, sizeof(pReader));
#endif
}

/*******************************************************************/
/* PLWriter is used in constructing a document's position list.  As a
** convenience, if iType is DL_DOCIDS, PLWriter becomes a no-op.
**
** plwInit - init for writing a document's poslist.
................................................................................
static PLWriter *plwNew(sqlite_int64 iDocid, DocListType iType){
  PLWriter *pWriter = malloc(sizeof(PLWriter));
  plwInit(pWriter, iDocid, iType);
  return pWriter;
}
static void plwDestroy(PLWriter *pWriter){
  dataBufferDestroy(&pWriter->b);
#ifndef NDEBUG
  memset(pWriter, 0x55, sizeof(pWriter));
#endif
}
static void plwDelete(PLWriter *pWriter){
  plwDestroy(pWriter);
  free(pWriter);
}


................................................................................
  **             and snippet delimiters specification.
  */

  /* Make a copy of the complete argv[][] array in a single allocation.
  ** The argv[][] array is read-only and transient.  We can write to the
  ** copy in order to modify things and the copy is persistent.
  */
  memset(pSpec, 0, sizeof(*pSpec));
  for(i=n=0; i<argc; i++){
    n += strlen(argv[i]) + 1;
  }
  azArg = malloc( sizeof(char*)*argc + n );
  if( azArg==0 ){
    return SQLITE_NOMEM;
  }
................................................................................
  int n;
  fulltext_vtab *v = 0;
  const sqlite3_tokenizer_module *m = NULL;
  char *schema;

  v = (fulltext_vtab *) malloc(sizeof(fulltext_vtab));
  if( v==0 ) return SQLITE_NOMEM;
  memset(v, 0, sizeof(*v));
  /* sqlite will initialize v->base */
  v->db = db;
  v->zName = spec->zName;   /* Freed when azColumn is freed */
  v->nColumn = spec->nColumn;
  v->azContentColumn = spec->azContentColumn;
  spec->azContentColumn = 0;
  v->azColumn = spec->azColumn;
................................................................................
*/
static void queryClear(Query *q){
  int i;
  for(i = 0; i < q->nTerms; ++i){
    free(q->pTerms[i].pTerm);
  }
  free(q->pTerms);
  memset(q, 0, sizeof(*q));
}

/* Free all of the dynamically allocated memory held by the
** Snippet
*/
static void snippetClear(Snippet *p){
  free(p->aMatch);
  free(p->zOffset);
  free(p->zSnippet);
  memset(p, 0, sizeof(*p));
}
/*
** Append a single entry to the p->aMatch[] log.
*/
static void snippetAppendMatch(
  Snippet *p,               /* Append the entry to this snippet */
  int iCol, int iTerm,      /* The column and query term */
................................................................................
  ++q->nTerms;
  q->pTerms = realloc(q->pTerms, q->nTerms * sizeof(q->pTerms[0]));
  if( q->pTerms==0 ){
    q->nTerms = 0;
    return;
  }
  t = &q->pTerms[q->nTerms - 1];
  memset(t, 0, sizeof(*t));
  t->pTerm = malloc(nTerm+1);
  memcpy(t->pTerm, pTerm, nTerm);
  t->pTerm[nTerm] = 0;
  t->nTerm = nTerm;
  t->isOr = q->nextIsOr;
  q->nextIsOr = 0;
  t->iColumn = q->nextColumn;
................................................................................
** next level down the tree.
*/
static void interiorWriterInit(int iHeight, const char *pTerm, int nTerm,
                               sqlite_int64 iChildBlock,
                               InteriorWriter *pWriter){
  InteriorBlock *block;
  assert( iHeight>0 );
  memset(pWriter, 0, sizeof(*pWriter));

  pWriter->iHeight = iHeight;
#ifndef NDEBUG
  pWriter->iLastChildBlock = iChildBlock;
#endif
  block = interiorBlockNew(iHeight, iChildBlock, pTerm, nTerm);
  pWriter->last = pWriter->first = block;
................................................................................
  while( block!=NULL ){
    InteriorBlock *b = block;
    block = block->next;
    dataBufferDestroy(&b->term);
    dataBufferDestroy(&b->data);
    free(b);
  }
#ifndef NDEBUG
  memset(pWriter, 0x55, sizeof(pWriter));
#endif
  return SQLITE_OK;
}

/* If pWriter can fit entirely in ROOT_MAX, return it as the root info
** directly, leaving *piEndBlockid unchanged.  Otherwise, flush
** pWriter to %_segments, building a new layer of interior nodes, and
** recursively ask for their root into.
................................................................................
  const char *pData;
  int nData;

  sqlite_int64 iBlockid;
} InteriorReader;

static void interiorReaderDestroy(InteriorReader *pReader){
#ifndef NDEBUG
  memset(pReader, 0x55, sizeof(pReader));
#endif
}

static void interiorReaderInit(const char *pData, int nData,
                               InteriorReader *pReader){
  int n;

  /* Require at least the leading flag byte */
  assert( nData>0 );
  assert( pData[0]!='\0' );

  memset(pReader, '\0', sizeof(pReader));

  /* Decode the base blockid, and set the cursor to the first term. */
  n = getVarint(pData+1, &pReader->iBlockid);
  assert( 1+n<=nData );
  pReader->pData = pData+1+n;
  pReader->nData = nData-(1+n);
}
................................................................................
  int has_parent;
} LeafWriter;

static void leafWriterInit(int iLevel, int idx, LeafWriter *pWriter){
  char c[VARINT_MAX];
  int n;

  memset(pWriter, 0, sizeof(*pWriter));
  pWriter->iLevel = iLevel;
  pWriter->idx = idx;

  dataBufferInit(&pWriter->term, 32);

  /* Start out with a reasonably sized block, though it can grow. */
  dataBufferInit(&pWriter->data, LEAF_MAX);
................................................................................

  const char *pData;        /* data for current term. */
  int nData;
} LeafReader;

static void leafReaderDestroy(LeafReader *pReader){
  dataBufferDestroy(&pReader->term);
#ifndef NDEBUG
  memset(pReader, 0x55, sizeof(pReader));
#endif
}

static int leafReaderAtEnd(LeafReader *pReader){
  return pReader->nData<=0;
}

/* Access the current term. */
................................................................................
static void leafReaderInit(const char *pData, int nData,
                           LeafReader *pReader){
  int nTerm, n;

  assert( nData>0 );
  assert( pData[0]=='\0' );

  memset(pReader, '\0', sizeof(pReader));

  /* Read the first term, skipping the header byte. */
  n = getVarint32(pData+1, &nTerm);
  dataBufferInit(&pReader->term, nTerm);
  dataBufferReplace(&pReader->term, pData+1+n, nTerm);

  /* Position after the first term. */
................................................................................
static int leavesReaderAtEnd(LeavesReader *pReader){
  return pReader->eof;
}

static void leavesReaderDestroy(LeavesReader *pReader){
  leafReaderDestroy(&pReader->leafReader);
  dataBufferDestroy(&pReader->rootData);
#ifndef NDEBUG
  memset(pReader, 0x55, sizeof(pReader));
#endif
}

/* Initialize pReader with the given root data (if iStartBlockid==0
** the leaf data was entirely contained in the root), or from the
** stream of blocks between iStartBlockid and iEndBlockid, inclusive.
*/
static int leavesReaderInit(fulltext_vtab *v,
                            int idx,
                            sqlite_int64 iStartBlockid,
                            sqlite_int64 iEndBlockid,
                            const char *pRootData, int nRootData,
                            LeavesReader *pReader){
  memset(pReader, 0, sizeof(*pReader));
  pReader->idx = idx;

  dataBufferInit(&pReader->rootData, 0);
  if( iStartBlockid==0 ){
    /* Entire leaf level fit in root data. */
    dataBufferReplace(&pReader->rootData, pRootData, nRootData);
    leafReaderInit(pReader->rootData.pData, pReader->rootData.nData,

/* MERGE_COUNT controls how often we merge segments (see comment at
** top of file).
*/
#define MERGE_COUNT 16

/* utility functions */

/* CLEAR() and SCRAMBLE() abstract memset() on a pointer to a single
** record to prevent errors of the form:
**
** my_function(SomeType *b){
**   memset(b, '\0', sizeof(b));  // sizeof(b)!=sizeof(*b)
** }
*/
/* TODO(shess) Obvious candidates for a header file. */
#define CLEAR(b) memset(b, '\0', sizeof(*(b)))

#ifndef NDEBUG
#  define SCRAMBLE(b) memset(b, 0x55, sizeof(*(b)))
#else
#  define SCRAMBLE(b)
#endif

/* We may need up to VARINT_MAX bytes to store an encoded 64-bit integer. */
#define VARINT_MAX 10

/* Write a 64-bit variable-length integer to memory starting at p[0].
 * The length of data written will be between 1 and VARINT_MAX bytes.
 * The number of bytes written is returned. */
................................................................................
  pBuffer->pData = nCapacity==0 ? NULL : malloc(nCapacity);
}
static void dataBufferReset(DataBuffer *pBuffer){
  pBuffer->nData = 0;
}
static void dataBufferDestroy(DataBuffer *pBuffer){
  if( pBuffer->pData!=NULL ) free(pBuffer->pData);
  SCRAMBLE(pBuffer);


}
static void dataBufferExpand(DataBuffer *pBuffer, int nAddCapacity){
  assert( nAddCapacity>0 );
  /* TODO(shess) Consider expanding more aggressively.  Note that the
  ** underlying malloc implementation may take care of such things for
  ** us already.
  */
................................................................................
  pReader->nElement = 0;
  pReader->iDocid = 0;

  /* Load the first element's data.  There must be a first element. */
  dlrStep(pReader);
}
static void dlrDestroy(DLReader *pReader){
  SCRAMBLE(pReader);


}

#ifndef NDEBUG
/* Verify that the doclist can be validly decoded.  Also returns the
** last docid found because it's convenient in other assertions for
** DLWriter.
*/
................................................................................
  pWriter->iType = iType;
#ifndef NDEBUG
  pWriter->has_prevDocid = 0;
  pWriter->iPrevDocid = 0;
#endif
}
static void dlwDestroy(DLWriter *pWriter){
  SCRAMBLE(pWriter);


}
static void dlwAppend(DLWriter *pWriter,
                      const char *pData, int nData){
#ifndef NDEBUG
  sqlite_int64 iDocid;
  int n;
  n = getVarint(pData, &iDocid);
................................................................................
  pReader->iColumn = 0;
  pReader->iPosition = 0;
  pReader->iStartOffset = 0;
  pReader->iEndOffset = 0;
  plrStep(pReader);
}
static void plrDestroy(PLReader *pReader){
  SCRAMBLE(pReader);


}

/*******************************************************************/
/* PLWriter is used in constructing a document's position list.  As a
** convenience, if iType is DL_DOCIDS, PLWriter becomes a no-op.
**
** plwInit - init for writing a document's poslist.
................................................................................
static PLWriter *plwNew(sqlite_int64 iDocid, DocListType iType){
  PLWriter *pWriter = malloc(sizeof(PLWriter));
  plwInit(pWriter, iDocid, iType);
  return pWriter;
}
static void plwDestroy(PLWriter *pWriter){
  dataBufferDestroy(&pWriter->b);
  SCRAMBLE(pWriter);


}
static void plwDelete(PLWriter *pWriter){
  plwDestroy(pWriter);
  free(pWriter);
}


................................................................................
  **             and snippet delimiters specification.
  */

  /* Make a copy of the complete argv[][] array in a single allocation.
  ** The argv[][] array is read-only and transient.  We can write to the
  ** copy in order to modify things and the copy is persistent.
  */
  CLEAR(pSpec);
  for(i=n=0; i<argc; i++){
    n += strlen(argv[i]) + 1;
  }
  azArg = malloc( sizeof(char*)*argc + n );
  if( azArg==0 ){
    return SQLITE_NOMEM;
  }
................................................................................
  int n;
  fulltext_vtab *v = 0;
  const sqlite3_tokenizer_module *m = NULL;
  char *schema;

  v = (fulltext_vtab *) malloc(sizeof(fulltext_vtab));
  if( v==0 ) return SQLITE_NOMEM;
  CLEAR(v);
  /* sqlite will initialize v->base */
  v->db = db;
  v->zName = spec->zName;   /* Freed when azColumn is freed */
  v->nColumn = spec->nColumn;
  v->azContentColumn = spec->azContentColumn;
  spec->azContentColumn = 0;
  v->azColumn = spec->azColumn;
................................................................................
*/
static void queryClear(Query *q){
  int i;
  for(i = 0; i < q->nTerms; ++i){
    free(q->pTerms[i].pTerm);
  }
  free(q->pTerms);
  CLEAR(q);
}

/* Free all of the dynamically allocated memory held by the
** Snippet
*/
static void snippetClear(Snippet *p){
  free(p->aMatch);
  free(p->zOffset);
  free(p->zSnippet);
  CLEAR(p);
}
/*
** Append a single entry to the p->aMatch[] log.
*/
static void snippetAppendMatch(
  Snippet *p,               /* Append the entry to this snippet */
  int iCol, int iTerm,      /* The column and query term */
................................................................................
  ++q->nTerms;
  q->pTerms = realloc(q->pTerms, q->nTerms * sizeof(q->pTerms[0]));
  if( q->pTerms==0 ){
    q->nTerms = 0;
    return;
  }
  t = &q->pTerms[q->nTerms - 1];
  CLEAR(t);
  t->pTerm = malloc(nTerm+1);
  memcpy(t->pTerm, pTerm, nTerm);
  t->pTerm[nTerm] = 0;
  t->nTerm = nTerm;
  t->isOr = q->nextIsOr;
  q->nextIsOr = 0;
  t->iColumn = q->nextColumn;
................................................................................
** next level down the tree.
*/
static void interiorWriterInit(int iHeight, const char *pTerm, int nTerm,
                               sqlite_int64 iChildBlock,
                               InteriorWriter *pWriter){
  InteriorBlock *block;
  assert( iHeight>0 );
  CLEAR(pWriter);

  pWriter->iHeight = iHeight;
#ifndef NDEBUG
  pWriter->iLastChildBlock = iChildBlock;
#endif
  block = interiorBlockNew(iHeight, iChildBlock, pTerm, nTerm);
  pWriter->last = pWriter->first = block;
................................................................................
  while( block!=NULL ){
    InteriorBlock *b = block;
    block = block->next;
    dataBufferDestroy(&b->term);
    dataBufferDestroy(&b->data);
    free(b);
  }
  SCRAMBLE(pWriter);


  return SQLITE_OK;
}

/* If pWriter can fit entirely in ROOT_MAX, return it as the root info
** directly, leaving *piEndBlockid unchanged.  Otherwise, flush
** pWriter to %_segments, building a new layer of interior nodes, and
** recursively ask for their root into.
................................................................................
  const char *pData;
  int nData;

  sqlite_int64 iBlockid;
} InteriorReader;

static void interiorReaderDestroy(InteriorReader *pReader){
  SCRAMBLE(pReader);


}

static void interiorReaderInit(const char *pData, int nData,
                               InteriorReader *pReader){
  int n;

  /* Require at least the leading flag byte */
  assert( nData>0 );
  assert( pData[0]!='\0' );

  CLEAR(pReader);

  /* Decode the base blockid, and set the cursor to the first term. */
  n = getVarint(pData+1, &pReader->iBlockid);
  assert( 1+n<=nData );
  pReader->pData = pData+1+n;
  pReader->nData = nData-(1+n);
}
................................................................................
  int has_parent;
} LeafWriter;

static void leafWriterInit(int iLevel, int idx, LeafWriter *pWriter){
  char c[VARINT_MAX];
  int n;

  CLEAR(pWriter);
  pWriter->iLevel = iLevel;
  pWriter->idx = idx;

  dataBufferInit(&pWriter->term, 32);

  /* Start out with a reasonably sized block, though it can grow. */
  dataBufferInit(&pWriter->data, LEAF_MAX);
................................................................................

  const char *pData;        /* data for current term. */
  int nData;
} LeafReader;

static void leafReaderDestroy(LeafReader *pReader){
  dataBufferDestroy(&pReader->term);
  SCRAMBLE(pReader);


}

static int leafReaderAtEnd(LeafReader *pReader){
  return pReader->nData<=0;
}

/* Access the current term. */
................................................................................
static void leafReaderInit(const char *pData, int nData,
                           LeafReader *pReader){
  int nTerm, n;

  assert( nData>0 );
  assert( pData[0]=='\0' );

  CLEAR(pReader);

  /* Read the first term, skipping the header byte. */
  n = getVarint32(pData+1, &nTerm);
  dataBufferInit(&pReader->term, nTerm);
  dataBufferReplace(&pReader->term, pData+1+n, nTerm);

  /* Position after the first term. */
................................................................................
static int leavesReaderAtEnd(LeavesReader *pReader){
  return pReader->eof;
}

static void leavesReaderDestroy(LeavesReader *pReader){
  leafReaderDestroy(&pReader->leafReader);
  dataBufferDestroy(&pReader->rootData);
  SCRAMBLE(pReader);


}

/* Initialize pReader with the given root data (if iStartBlockid==0
** the leaf data was entirely contained in the root), or from the
** stream of blocks between iStartBlockid and iEndBlockid, inclusive.
*/
static int leavesReaderInit(fulltext_vtab *v,
                            int idx,
                            sqlite_int64 iStartBlockid,
                            sqlite_int64 iEndBlockid,
                            const char *pRootData, int nRootData,
                            LeavesReader *pReader){
  CLEAR(pReader);
  pReader->idx = idx;

  dataBufferInit(&pReader->rootData, 0);
  if( iStartBlockid==0 ){
    /* Entire leaf level fit in root data. */
    dataBufferReplace(&pReader->rootData, pRootData, nRootData);
    leafReaderInit(pReader->rootData.pData, pReader->rootData.nData,