SQLite

  Fts5HashEntry *pHashNext;       /* Next hash entry with same hash-key */
  Fts5HashEntry *pScanNext;       /* Next entry in sorted order */
  
  int nAlloc;                     /* Total size of allocation */
  int iSzPoslist;                 /* Offset of space for 4-byte poslist size */
  int nData;                      /* Total bytes of data (incl. structure) */
  u8 bDel;                        /* Set delete-flag @ iSzPoslist */
  u8 bContent;                    /* Set content-flag (detail=none mode) */

  int iCol;                       /* Column of last value written */
  int iPos;                       /* Position of last value written */
  i64 iRowid;                     /* Rowid of last value written */
  char zKey[8];                   /* Nul-terminated entry key */
};

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
  pHash->aSlot = apNew;
  return SQLITE_OK;
}

static void fts5HashAddPoslistSize(Fts5Hash *pHash, Fts5HashEntry *p){
  if( p->iSzPoslist ){
    u8 *pPtr = (u8*)p;
    if( pHash->eDetail==FTS5_DETAIL_NONE ){
      assert( p->nData==p->iSzPoslist );
      if( p->bDel ){
        pPtr[p->nData++] = 0x00;
        if( p->bContent ){
          pPtr[p->nData++] = 0x00;
        }
      }
    }else{
      int nSz = (p->nData - p->iSzPoslist - 1);       /* Size in bytes */
      int nPos = nSz*2 + p->bDel;                     /* Value of nPos field */

      assert( p->bDel==0 || p->bDel==1 );
      if( nPos<=127 ){
        pPtr[p->iSzPoslist] = (u8)nPos;
      }else{
        int nByte = sqlite3Fts5GetVarintLen((u32)nPos);
        memmove(&pPtr[p->iSzPoslist + nByte], &pPtr[p->iSzPoslist + 1], nSz);
        sqlite3Fts5PutVarint(&pPtr[p->iSzPoslist], nPos);
        p->nData += (nByte-1);
      }
    }

    p->iSzPoslist = 0;
    p->bDel = 0;
    p->bContent = 0;
  }
}

/*
** Add an entry to the in-memory hash table. The key is the concatenation
** of bByte and (pToken/nToken). The value is (iRowid/iCol/iPos).
**
**     (bByte || pToken) -> (iRowid,iCol,iPos)
**
** Or, if iCol is negative, then the value is a delete marker.
*/
int sqlite3Fts5HashWrite(
  Fts5Hash *pHash,
  i64 iRowid,                     /* Rowid for this entry */
  int iCol,                       /* Column token appears in (-ve -> delete) */
  int iPos,                       /* Position of token within column */
  char bByte,                     /* First byte of token */
  const char *pToken, int nToken  /* Token to add or remove to or from index */

    ){
      break;
    }
  }

  /* If an existing hash entry cannot be found, create a new one. */
  if( p==0 ){
    /* Figure out how much space to allocate */
    int nByte = FTS5_HASHENTRYSIZE + (nToken+1) + 1 + 64;
    if( nByte<128 ) nByte = 128;

    /* Grow the Fts5Hash.aSlot[] array if necessary. */
    if( (pHash->nEntry*2)>=pHash->nSlot ){
      int rc = fts5HashResize(pHash);
      if( rc!=SQLITE_OK ) return rc;
      iHash = fts5HashKey2(pHash->nSlot, (u8)bByte, (const u8*)pToken, nToken);
    }

    /* Allocate new Fts5HashEntry and add it to the hash table. */
    p = (Fts5HashEntry*)sqlite3_malloc(nByte);
    if( !p ) return SQLITE_NOMEM;
    memset(p, 0, FTS5_HASHENTRYSIZE);
    p->nAlloc = nByte;
    p->zKey[0] = bByte;
    memcpy(&p->zKey[1], pToken, nToken);
    assert( iHash==fts5HashKey(pHash->nSlot, (u8*)p->zKey, nToken+1) );
    p->zKey[nToken+1] = '\0';
    p->nData = nToken+1 + 1 + FTS5_HASHENTRYSIZE;





    p->pHashNext = pHash->aSlot[iHash];
    pHash->aSlot[iHash] = p;
    pHash->nEntry++;

    /* Add the first rowid field to the hash-entry */
    p->nData += sqlite3Fts5PutVarint(&((u8*)p)[p->nData], iRowid);
    p->iRowid = iRowid;

    p->iSzPoslist = p->nData;
    if( pHash->eDetail!=FTS5_DETAIL_NONE ){
      p->nData += 1;
      p->iCol = (pHash->eDetail==FTS5_DETAIL_FULL ? 0 : -1);
    }

    nIncr += p->nData;
  }else{

    /* Appending to an existing hash-entry. Check that there is enough 
    ** space to append the largest possible new entry. Worst case scenario 
    ** is:
    **
    **     + 9 bytes for a new rowid,
    **     + 4 byte reserved for the "poslist size" varint.
    **     + 1 byte for a "new column" byte,
    **     + 3 bytes for a new column number (16-bit max) as a varint,
    **     + 5 bytes for the new position offset (32-bit max).
    */
    if( (p->nAlloc - p->nData) < (9 + 4 + 1 + 3 + 5) ){
      int nNew = p->nAlloc * 2;
      Fts5HashEntry *pNew;
      Fts5HashEntry **pp;
      pNew = (Fts5HashEntry*)sqlite3_realloc(p, nNew);
      if( pNew==0 ) return SQLITE_NOMEM;
      pNew->nAlloc = nNew;
      for(pp=&pHash->aSlot[iHash]; *pp!=p; pp=&(*pp)->pHashNext);
      *pp = pNew;
      p = pNew;
    }

    nIncr -= p->nData;
  }
  assert( (p->nAlloc - p->nData) >= (9 + 4 + 1 + 3 + 5) );

  pPtr = (u8*)p;

  /* If this is a new rowid, append the 4-byte size field for the previous
  ** entry, and the new rowid for this entry.  */
  if( iRowid!=p->iRowid ){
    fts5HashAddPoslistSize(pHash, p);
    p->nData += sqlite3Fts5PutVarint(&pPtr[p->nData], iRowid - p->iRowid);
    p->iRowid = iRowid;
    bNew = 1;
    p->iSzPoslist = p->nData;
    if( pHash->eDetail!=FTS5_DETAIL_NONE ){
      p->nData += 1;
      p->iCol = (pHash->eDetail==FTS5_DETAIL_FULL ? 0 : -1);
      p->iPos = 0;


    }
  }

  if( iCol>=0 ){
    if( pHash->eDetail==FTS5_DETAIL_NONE ){
      p->bContent = 1;
    }else{
      /* Append a new column value, if necessary */
      assert( iCol>=p->iCol );
      if( iCol!=p->iCol ){
        if( pHash->eDetail==FTS5_DETAIL_FULL ){
          pPtr[p->nData++] = 0x01;
          p->nData += sqlite3Fts5PutVarint(&pPtr[p->nData], iCol);
          p->iCol = iCol;
          p->iPos = 0;
        }else{
          bNew = 1;
          p->iCol = iPos = iCol;
        }
      }

      /* Append the new position offset, if necessary */
      if( bNew ){
        p->nData += sqlite3Fts5PutVarint(&pPtr[p->nData], iPos - p->iPos + 2);
        p->iPos = iPos;
      }
    }
  }else{
    /* This is a delete. Set the delete flag. */
    p->bDel = 1;
  }


  nIncr += p->nData;
  *pHash->pnByte += nIncr;
  return SQLITE_OK;
}


/*
** Arguments pLeft and pRight point to linked-lists of hash-entry objects,

  Fts5HashEntry *p;

  for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
    if( memcmp(p->zKey, pTerm, nTerm)==0 && p->zKey[nTerm]==0 ) break;
  }

  if( p ){
    fts5HashAddPoslistSize(pHash, p);
    *ppDoclist = (const u8*)&p->zKey[nTerm+1];
    *pnDoclist = p->nData - (FTS5_HASHENTRYSIZE + nTerm + 1);
  }else{
    *ppDoclist = 0;
    *pnDoclist = 0;
  }

  const char **pzTerm,            /* OUT: term (nul-terminated) */
  const u8 **ppDoclist,           /* OUT: pointer to doclist */
  int *pnDoclist                  /* OUT: size of doclist in bytes */
){
  Fts5HashEntry *p;
  if( (p = pHash->pScan) ){
    int nTerm = (int)strlen(p->zKey);
    fts5HashAddPoslistSize(pHash, p);
    *pzTerm = p->zKey;
    *ppDoclist = (const u8*)&p->zKey[nTerm+1];
    *pnDoclist = p->nData - (FTS5_HASHENTRYSIZE + nTerm + 1);
  }else{
    *pzTerm = 0;
    *ppDoclist = 0;
    *pnDoclist = 0;
  }
}

  Fts5DlidxIter *pDlidx;          /* If there is a doclist-index */

  /* Variables populated based on current entry. */
  Fts5Buffer term;                /* Current term */
  i64 iRowid;                     /* Current rowid */
  int nPos;                       /* Number of bytes in current position list */
  u8 bDel;                        /* True if the delete flag is set */
  // u8 bContent;                    /* True if has content (detail=none mode) */
};

/*
** Argument is a pointer to an Fts5Data structure that contains a 
** leaf page.
*/
#define ASSERT_SZLEAF_OK(x) assert( \
    (x)->szLeaf==(x)->nn || (x)->szLeaf==fts5GetU16(&(x)->p[2]) \
)

#define FTS5_SEGITER_ONETERM 0x01
#define FTS5_SEGITER_REVERSE 0x02


/* 
** Argument is a pointer to an Fts5Data structure that contains a leaf
** page. This macro evaluates to true if the leaf contains no terms, or
** false if it contains at least one term.
*/
#define fts5LeafIsTermless(x) ((x)->szLeaf >= (x)->nn)

**
** Leave Fts5SegIter.iLeafOffset pointing to the first byte of the 
** position list content (if any).
*/
static void fts5SegIterLoadNPos(Fts5Index *p, Fts5SegIter *pIter){
  if( p->rc==SQLITE_OK ){
    int iOff = pIter->iLeafOffset;  /* Offset to read at */

    ASSERT_SZLEAF_OK(pIter->pLeaf);
    if( p->pConfig->eDetail==FTS5_DETAIL_NONE ){
      pIter->bDel = 0;
      pIter->nPos = 1;
      if( iOff<pIter->pLeaf->szLeaf && pIter->pLeaf->p[iOff]==0 ){
        pIter->bDel = 1;
        iOff++;
        if( iOff<pIter->pLeaf->szLeaf && pIter->pLeaf->p[iOff]==0 ){
          pIter->nPos = 1;
          iOff++;
        }else{
          pIter->nPos = 0;
        }
      }
    }else{
      int nSz;
      fts5FastGetVarint32(pIter->pLeaf->p, iOff, nSz);
      pIter->bDel = (nSz & 0x0001);
      pIter->nPos = nSz>>1;

      assert_nc( pIter->nPos>=0 );
    }
    pIter->iLeafOffset = iOff;
  }
}

static void fts5SegIterLoadRowid(Fts5Index *p, Fts5SegIter *pIter){
  u8 *a = pIter->pLeaf->p;        /* Buffer to read data from */
  int iOff = pIter->iLeafOffset;

      int nKeep = 0;

      /* Search for the end of the position list within the current page. */
      u8 *a = pLeaf->p;
      int n = pLeaf->szLeaf;

      ASSERT_SZLEAF_OK(pLeaf);
      if( p->pConfig->eDetail==FTS5_DETAIL_NONE ){
        iOff = pIter->iLeafOffset;
      }else{
        iOff = pIter->iLeafOffset + pIter->nPos;
      }

      if( iOff<n ){
        /* The next entry is on the current page. */
        assert_nc( iOff<=pIter->iEndofDoclist );
        if( iOff>=pIter->iEndofDoclist ){
          bNewTerm = 1;
          if( iOff!=fts5LeafFirstTermOff(pLeaf) ){

            fts5SegIterLoadTerm(p, pIter, nKeep);
            fts5SegIterLoadNPos(p, pIter);
            if( pbNewTerm ) *pbNewTerm = 1;
          }
        }else{
          /* The following could be done by calling fts5SegIterLoadNPos(). But
          ** this block is particularly performance critical, so equivalent
          ** code is inlined. 
          **
          ** Later: Switched back to fts5SegIterLoadNPos() because it supports
          ** detail=none mode. Not ideal.
          */
#if 0
          int nSz;
          assert( p->rc==SQLITE_OK );
          fts5FastGetVarint32(pIter->pLeaf->p, pIter->iLeafOffset, nSz);
          pIter->bDel = (nSz & 0x0001);
          pIter->nPos = nSz>>1;
          assert_nc( pIter->nPos>=0 );
#endif
          fts5SegIterLoadNPos(p, pIter);
        }
      }
    }
  }
}

#define SWAPVAL(T, a, b) { T tmp; tmp=a; a=b; b=tmp; }

  assert( (prev & 0x80)==0 );
  while( p<pEnd && ((prev & 0x80) || *p!=0x01) ){
    prev = *p++;
  }
  return p - (*pa);
}

static int fts5AppendRowid(
  Fts5Index *p,
  i64 iDelta,
  Fts5IndexIter *pMulti,
  Fts5Colset *pColset,
  Fts5Buffer *pBuf
){
  fts5BufferAppendVarint(&p->rc, pBuf, iDelta);
  return 0;
}

/*
** Iterator pMulti currently points to a valid entry (not EOF). This
** function appends the following to buffer pBuf:
**
**   * The varint iDelta, and
**   * the position list that currently points to, including the size field.

#endif

#define fts5MergeAppendDocid(pBuf, iLastRowid, iRowid) {       \
  assert( (pBuf)->n!=0 || (iLastRowid)==0 );                   \
  fts5BufferSafeAppendVarint((pBuf), (iRowid) - (iLastRowid)); \
  (iLastRowid) = (iRowid);                                     \
}

/*
** Swap the contents of buffer *p1 with that of *p2.
*/
static void fts5BufferSwap(Fts5Buffer *p1, Fts5Buffer *p2){
  Fts5Buffer tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

static void fts5NextRowid(Fts5Buffer *pBuf, int *piOff, i64 *piRowid){
  int i = *piOff;
  if( i>=pBuf->n ){
    *piOff = -1;
  }else{
    u64 iVal;
    *piOff = i + sqlite3Fts5GetVarint(&pBuf->p[i], &iVal);
    *piRowid += iVal;
  }
}

/*
** This is the equivalent of fts5MergePrefixLists() for detail=none mode.
** In this case the buffers consist of a delta-encoded list of rowids only.
*/
static void fts5MergeRowidLists(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5Buffer *p1,                 /* First list to merge */
  Fts5Buffer *p2                  /* Second list to merge */
){
  int i1 = 0;
  int i2 = 0;
  i64 iRowid1 = 0;
  i64 iRowid2 = 0;
  i64 iOut = 0;

  Fts5Buffer out;
  memset(&out, 0, sizeof(out));
  sqlite3Fts5BufferSize(&p->rc, &out, p1->n + p2->n);
  if( p->rc ) return;

  fts5NextRowid(p1, &i1, &iRowid1);
  fts5NextRowid(p1, &i2, &iRowid2);
  while( i1>=0 || i2>=0 ){
    if( i1>=0 && (i2<0 || iRowid1<iRowid2) ){
      fts5BufferSafeAppendVarint(&out, iRowid1 - iOut);
      iOut = iRowid1;
      fts5NextRowid(p1, &i1, &iRowid1);
    }else{
      fts5BufferSafeAppendVarint(&out, iRowid2 - iOut);
      iOut = iRowid2;
      fts5NextRowid(p2, &i2, &iRowid2);
      if( i1>=0 && iRowid1==iRowid2 ){
        fts5NextRowid(p1, &i1, &iRowid1);
      }
    }
  }

  fts5BufferSwap(&out, p1);
  fts5BufferFree(&out);
}

/*
** Buffers p1 and p2 contain doclists. This function merges the content
** of the two doclists together and sets buffer p1 to the result before
** returning.
**
** If an error occurs, an error code is left in p->rc. If an error has

    fts5BufferSet(&p->rc, p1, out.n, out.p);
    fts5BufferFree(&tmp);
    fts5BufferFree(&out);
  }
}










static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bDesc,                      /* True for "ORDER BY rowid DESC" */
  const u8 *pToken,               /* Buffer containing prefix to match */
  int nToken,                     /* Size of buffer pToken in bytes */
  Fts5Colset *pColset,            /* Restrict matches to these columns */
  Fts5IndexIter **ppIter          /* OUT: New iterator */
){
  Fts5Structure *pStruct;
  Fts5Buffer *aBuf;
  const int nBuf = 32;

  void (*xMerge)(Fts5Index*, Fts5Buffer*, Fts5Buffer*);
  int (*xAppend)(Fts5Index*, i64, Fts5IndexIter*, Fts5Colset*, Fts5Buffer*);
  if( p->pConfig->eDetail==FTS5_DETAIL_NONE ){
    xMerge = fts5MergeRowidLists;
    xAppend = fts5AppendRowid;
  }else{
    xMerge = fts5MergePrefixLists;
    xAppend = fts5AppendPoslist;
  }

  aBuf = (Fts5Buffer*)fts5IdxMalloc(p, sizeof(Fts5Buffer)*nBuf);
  pStruct = fts5StructureRead(p);

  if( aBuf && pStruct ){
    const int flags = FTS5INDEX_QUERY_SCAN;
    int i;

      if( doclist.n>0 && iRowid<=iLastRowid ){
        for(i=0; p->rc==SQLITE_OK && doclist.n; i++){
          assert( i<nBuf );
          if( aBuf[i].n==0 ){
            fts5BufferSwap(&doclist, &aBuf[i]);
            fts5BufferZero(&doclist);
          }else{
            xMerge(p, &doclist, &aBuf[i]);
            fts5BufferZero(&aBuf[i]);
          }
        }
        iLastRowid = 0;
      }

      if( !xAppend(p, iRowid-iLastRowid, p1, pColset, &doclist) ){
        iLastRowid = iRowid;
      }
    }

    for(i=0; i<nBuf; i++){
      if( p->rc==SQLITE_OK ){
        xMerge(p, &doclist, &aBuf[i]);
      }
      fts5BufferFree(&aBuf[i]);
    }
    fts5MultiIterFree(p, p1);

    pData = fts5IdxMalloc(p, sizeof(Fts5Data) + doclist.n);
    if( pData ){

  i64 *piRowid                    /* OUT: Current rowid */
){
  Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ];
  int eDetail = pIter->pIndex->pConfig->eDetail;

  assert( pIter->pIndex->rc==SQLITE_OK );
  *piRowid = pSeg->iRowid;
  if( eDetail==FTS5_DETAIL_NONE ){
    *pn = pSeg->nPos;
  }else
  if( eDetail==FTS5_DETAIL_FULL 
   && pSeg->iLeafOffset+pSeg->nPos<=pSeg->pLeaf->szLeaf 
  ){
    u8 *pPos = &pSeg->pLeaf->p[pSeg->iLeafOffset];
    if( pColset==0 || pIter->bFiltered ){
      *pn = pSeg->nPos;
      *pp = pPos;

# 2015 September 05
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    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.
#
#*************************************************************************
#

source [file join [file dirname [info script]] fts5_common.tcl]
set testprefix fts5simple2

# If SQLITE_ENABLE_FTS5 is defined, omit this file.
ifcapable !fts5 {
  finish_test
  return
}

do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a, detail=none);
  INSERT INTO t1 VALUES('a b c');
}
do_execsql_test 1.1 {
  SELECT rowid FROM t1('c a b')
} {1}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 2.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a, detail=none);
  BEGIN;
    INSERT INTO t1 VALUES('b c d');
    INSERT INTO t1 VALUES('b c d');
  COMMIT;
}
do_execsql_test 2.1 {
  SELECT rowid FROM t1('b c d')
} {1 2}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a, detail=none);
  BEGIN;
    INSERT INTO t1 VALUES('b c d');
    INSERT INTO t1 VALUES('b c d');
}
do_execsql_test 3.1 {
  SELECT rowid FROM t1('b c d'); COMMIT;
} {1 2}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a, detail=none);
  BEGIN;
    INSERT INTO t1 VALUES('a1 b1 c1');
    INSERT INTO t1 VALUES('a2 b2 c2');
    INSERT INTO t1 VALUES('a3 b3 c3');
  COMMIT;
}
breakpoint
do_execsql_test 4.1 {
  SELECT rowid FROM t1('b*');
} {1 2 3}


finish_test