/ Check-in [5b295897]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add further tests and fixes for fts5.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1:5b295897153e9b26cd0d2e7ea112a4d461d0a665
User & Date: dan 2015-01-22 19:13:08
Context
2015-01-23
06:50
Remove some redundant code from fts5. check-in: 939b7a5d user: dan tags: fts5
2015-01-22
19:13
Add further tests and fixes for fts5. check-in: 5b295897 user: dan tags: fts5
2015-01-21
20:30
Further tests and fixes for fts5. check-in: c020a291 user: dan tags: fts5
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5Int.h.

341
342
343
344
345
346
347



348
349
350
351
352
353
354
int sqlite3Fts5IndexReads(Fts5Index *p);

int sqlite3Fts5IndexReinit(Fts5Index *p);
int sqlite3Fts5IndexOptimize(Fts5Index *p);

int sqlite3Fts5IndexLoadConfig(Fts5Index *p);




/*
** End of interface to code in fts5_index.c.
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_hash.c. 
*/







>
>
>







341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
int sqlite3Fts5IndexReads(Fts5Index *p);

int sqlite3Fts5IndexReinit(Fts5Index *p);
int sqlite3Fts5IndexOptimize(Fts5Index *p);

int sqlite3Fts5IndexLoadConfig(Fts5Index *p);

int sqlite3Fts5GetVarint32(const unsigned char *p, u32 *v);
#define fts5GetVarint32(a,b) sqlite3Fts5GetVarint32(a,(u32*)&b)

/*
** End of interface to code in fts5_index.c.
**************************************************************************/

/**************************************************************************
** Interface to code in fts5_hash.c. 
*/

Changes to ext/fts5/fts5_hash.c.

107
108
109
110
111
112
113


114

115
116
117
118

119
120
121
122
123
124
125

/*
** Empty (but do not delete) a hash table.
*/
void sqlite3Fts5HashClear(Fts5Hash *pHash){
  int i;
  for(i=0; i<pHash->nSlot; i++){


    if( pHash->aSlot[i] ){

      sqlite3_free(pHash->aSlot[i]);
      pHash->aSlot[i] = 0;
    }
  }

  pHash->nEntry = 0;
}

static unsigned int fts5HashKey(int nSlot, const char *p, int n){
  int i;
  unsigned int h = 13;
  for(i=n-1; i>=0; i--){







>
>
|
>
|
<


>







107
108
109
110
111
112
113
114
115
116
117
118

119
120
121
122
123
124
125
126
127
128

/*
** Empty (but do not delete) a hash table.
*/
void sqlite3Fts5HashClear(Fts5Hash *pHash){
  int i;
  for(i=0; i<pHash->nSlot; i++){
    Fts5HashEntry *pNext;
    Fts5HashEntry *pSlot;
    for(pSlot=pHash->aSlot[i]; pSlot; pSlot=pNext){
      pNext = pSlot->pNext;
      sqlite3_free(pSlot);

    }
  }
  memset(pHash->aSlot, 0, pHash->nSlot * sizeof(Fts5HashEntry*));
  pHash->nEntry = 0;
}

static unsigned int fts5HashKey(int nSlot, const char *p, int n){
  int i;
  unsigned int h = 13;
  for(i=n-1; i>=0; i--){

Changes to ext/fts5/fts5_index.c.

599
600
601
602
603
604
605


































































606
607
608
609
610
611
612
...
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
...
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
....
1140
1141
1142
1143
1144
1145
1146

1147
1148
1149
1150
1151
1152
1153
....
1189
1190
1191
1192
1193
1194
1195
1196

1197
1198
1199
1200
1201
1202
1203
....
1204
1205
1206
1207
1208
1209
1210
1211

1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
....
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
....
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
....
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
....
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
....
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
....
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
....
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
....
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
....
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
....
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
....
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
....
2542
2543
2544
2545
2546
2547
2548

2549
2550
2551
2552
2553
2554


2555

2556
2557
2558
2559
2560
2561
2562

2563
2564
2565
2566
2567
2568
2569
....
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159



3160
3161
3162
3163
3164
3165
3166
....
3268
3269
3270
3271
3272
3273
3274

3275
3276
3277
3278
3279
3280
3281
....
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
....
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
....
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
....
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
....
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
....
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
  aOut[0] = (iVal>>8);
  aOut[1] = (iVal&0xFF);
}

static u16 fts5GetU16(const u8 *aIn){
  return ((u16)aIn[0] << 8) + aIn[1];
}



































































/*
** Allocate and return a buffer at least nByte bytes in size.
**
** If an OOM error is encountered, return NULL and set the error code in
** the Fts5Index handle passed as the first argument.
*/
................................................................................

  /* Grab the cookie value */
  if( piCookie ) *piCookie = sqlite3Fts5Get32(pData);
  i = 4;

  /* Read the total number of levels and segments from the start of the
  ** structure record.  */
  i += getVarint32(&pData[i], nLevel);
  i += getVarint32(&pData[i], nSegment);
  nByte = (
      sizeof(Fts5Structure) +                    /* Main structure */
      sizeof(Fts5StructureLevel) * (nLevel)      /* aLevel[] array */
  );
  pRet = (Fts5Structure*)sqlite3Fts5MallocZero(&rc, nByte);

  if( pRet ){
................................................................................
    i += sqlite3GetVarint(&pData[i], &pRet->nWriteCounter);

    for(iLvl=0; rc==SQLITE_OK && iLvl<nLevel; iLvl++){
      Fts5StructureLevel *pLvl = &pRet->aLevel[iLvl];
      int nTotal;
      int iSeg;

      i += getVarint32(&pData[i], pLvl->nMerge);
      i += getVarint32(&pData[i], nTotal);
      assert( nTotal>=pLvl->nMerge );
      pLvl->aSeg = (Fts5StructureSegment*)sqlite3Fts5MallocZero(&rc, 
          nTotal * sizeof(Fts5StructureSegment)
      );

      if( rc==SQLITE_OK ){
        pLvl->nSeg = nTotal;
        for(iSeg=0; iSeg<nTotal; iSeg++){
          i += getVarint32(&pData[i], pLvl->aSeg[iSeg].iSegid);
          i += getVarint32(&pData[i], pLvl->aSeg[iSeg].nHeight);
          i += getVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoFirst);
          i += getVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoLast);
        }
      }else{
        fts5StructureRelease(pRet);
        pRet = 0;
      }
    }
  }
................................................................................
  Fts5Structure *pStruct
){
  int il, is;
  Fts5StructureLevel *pOut = &pStruct->aLevel[iPromote];

  for(il=iPromote+1; il<pStruct->nLevel; il++){
    Fts5StructureLevel *pLvl = &pStruct->aLevel[il];

    for(is=pLvl->nSeg-1; is>=0; is--){
      int sz = fts5SegmentSize(&pLvl->aSeg[is]);
      if( sz>szPromote ) return;
      fts5StructureExtendLevel(&p->rc, pStruct, iPromote, 1, 1);
      if( p->rc ) return;
      memcpy(pOut->aSeg, &pLvl->aSeg[is], sizeof(Fts5StructureSegment));
      pOut->nSeg++;
................................................................................

    pSeg = &pStruct->aLevel[iLvl].aSeg[pStruct->aLevel[iLvl].nSeg-1];
    szSeg = (1 + pSeg->pgnoLast - pSeg->pgnoFirst);

    /* Check for condition (a) */
    for(iTst=iLvl-1; iTst>=0 && pStruct->aLevel[iTst].nSeg==0; iTst--);
    pTst = &pStruct->aLevel[iTst];
    if( iTst>=0 && pTst->nMerge==0 ){

      int i;
      int szMax = 0;
      for(i=0; i<pTst->nSeg; i++){
        int sz = pTst->aSeg[i].pgnoLast - pTst->aSeg[i].pgnoFirst + 1;
        if( sz>szMax ) szMax = sz;
      }
      if( szMax>=szSeg ){
................................................................................
        /* Condition (a) is true. Promote the newest segment on level 
        ** iLvl to level iTst.  */
        iPromote = iTst;
        szPromote = szMax;
      }
    }

    /* Check for condition (b) */

    if( iPromote<0 ){
      Fts5StructureLevel *pTst;
      for(iTst=iLvl+1; iTst<pStruct->nLevel; iTst++){
        pTst = &pStruct->aLevel[iTst];
        if( pTst->nSeg ) break;
      }
      if( iTst<pStruct->nLevel && pTst->nMerge==0 ){
        Fts5StructureSegment *pSeg2 = &pTst->aSeg[pTst->nSeg-1];
        int sz = pSeg2->pgnoLast - pSeg2->pgnoFirst + 1;
        if( sz<=szSeg ){
          iPromote = iLvl;
          szPromote = szSeg;
        }
      }
    }

    /* If iPromote is greater than or equal to zero at this point, then it
    ** is the level number of a level to which segments that consist of
    ** szPromote or fewer pages should be promoted. */ 
    if( iPromote>=0 ){
      fts5PrintStructure("BEFORE", pStruct);
      fts5StructurePromoteTo(p, iPromote, szPromote, pStruct);
      fts5PrintStructure("AFTER", pStruct);
    }
  }
}


/*
** If the pIter->iOff offset currently points to an entry indicating one
** or more term-less nodes, advance past it and set pIter->nEmpty to
** the number of empty child nodes.
*/
static void fts5NodeIterGobbleNEmpty(Fts5NodeIter *pIter){
  if( pIter->iOff<pIter->nData && 0==(pIter->aData[pIter->iOff] & 0xfe) ){
    pIter->bDlidx = pIter->aData[pIter->iOff] & 0x01;
    pIter->iOff++;
    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], pIter->nEmpty);
  }else{
    pIter->nEmpty = 0;
    pIter->bDlidx = 0;
  }
}

/*
................................................................................
*/
static void fts5NodeIterNext(int *pRc, Fts5NodeIter *pIter){
  if( pIter->iOff>=pIter->nData ){
    pIter->aData = 0;
    pIter->iChild += pIter->nEmpty;
  }else{
    int nPre, nNew;
    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], nPre);
    pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], nNew);
    pIter->term.n = nPre-2;
    fts5BufferAppendBlob(pRc, &pIter->term, nNew, pIter->aData+pIter->iOff);
    pIter->iOff += nNew;
    pIter->iChild += (1 + pIter->nEmpty);
    fts5NodeIterGobbleNEmpty(pIter);
    if( *pRc ) pIter->aData = 0;
  }
................................................................................
** Initialize the iterator object pIter to iterate through the internal
** segment node in pData.
*/
static void fts5NodeIterInit(const u8 *aData, int nData, Fts5NodeIter *pIter){
  memset(pIter, 0, sizeof(*pIter));
  pIter->aData = aData;
  pIter->nData = nData;
  pIter->iOff = getVarint32(aData, pIter->iChild);
  fts5NodeIterGobbleNEmpty(pIter);
}

/*
** Free any memory allocated by the iterator object.
*/
static void fts5NodeIterFree(Fts5NodeIter *pIter){
................................................................................
** position list. The position list belonging to document pIter->iRowid.
*/
static void fts5SegIterLoadTerm(Fts5Index *p, Fts5SegIter *pIter, int nKeep){
  u8 *a = pIter->pLeaf->p;        /* Buffer to read data from */
  int iOff = pIter->iLeafOffset;  /* Offset to read at */
  int nNew;                       /* Bytes of new data */

  iOff += getVarint32(&a[iOff], nNew);
  pIter->term.n = nKeep;
  fts5BufferAppendBlob(&p->rc, &pIter->term, nNew, &a[iOff]);
  iOff += nNew;
  pIter->iTermLeafOffset = iOff;
  pIter->iTermLeafPgno = pIter->iLeafPgno;
  if( iOff>=pIter->pLeaf->n ){
    fts5SegIterNextPage(p, pIter);
................................................................................
  u8 *a = pIter->pLeaf->p;
  int iRowidOffset = 0;

  while( p->rc==SQLITE_OK && i<n ){
    i64 iDelta = 0;
    int nPos;

    i += getVarint32(&a[i], nPos);
    i += nPos;
    if( i>=n ) break;
    i += getVarint(&a[i], (u64*)&iDelta);
    if( iDelta==0 ) break;
    pIter->iRowid -= iDelta;

    if( iRowidOffset>=pIter->nRowidOffset ){
................................................................................
        u8 *a = pIter->pLeaf->p;
        int iOff;
        int nPos;
        i64 iDelta;
        pIter->iRowidOffset--;

        pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset];
        iOff += getVarint32(&a[iOff], nPos);
        iOff += nPos;
        getVarint(&a[iOff], (u64*)&iDelta);
        pIter->iRowid += iDelta;
      }else{
        fts5SegIterReverseNewPage(p, pIter);
      }
    }else{
................................................................................
      /* Search for the end of the position list within the current page. */
      u8 *a = pLeaf->p;
      int n = pLeaf->n;

      iOff = pIter->iLeafOffset;
      if( iOff<n ){
        int nPoslist;
        iOff += getVarint32(&a[iOff], nPoslist);
        iOff += nPoslist;
      }

      if( iOff<n ){
        /* The next entry is on the current page */
        u64 iDelta;
        iOff += sqlite3GetVarint(&a[iOff], &iDelta);
................................................................................
        pIter->iLeafOffset = iOff;
        if( iDelta==0 ){
          bNewTerm = 1;
          if( iOff>=n ){
            fts5SegIterNextPage(p, pIter);
            pIter->iLeafOffset = 4;
          }else if( iOff!=fts5GetU16(&a[2]) ){
            pIter->iLeafOffset += getVarint32(&a[iOff], nKeep);
          }
        }else{
          pIter->iRowid -= iDelta;
        }
      }else{
        iOff = 0;
        /* Next entry is not on the current page */
................................................................................
    pLast = fts5DataRead(p, FTS5_SEGMENT_ROWID(iIdx, iSegid, 0, pgnoLast));
  }else{
    while( iOff<pLeaf->n ){
      int nPos;
      i64 iDelta;

      /* Position list size in bytes */
      iOff += getVarint32(&pLeaf->p[iOff], nPos);
      iOff += nPos;
      if( iOff>=pLeaf->n ) break;

      /* Rowid delta. Or, if 0x00, the end of doclist marker. */
      nPos = getVarint(&pLeaf->p[iOff], (u64*)&iDelta);
      if( iDelta==0 ) break;
      iOff += nPos;
................................................................................
  ** term. */
  if( pIter->iTermLeafPgno==pIter->iLeafPgno ){
    while( iOff<pLeaf->n ){
      i64 iDelta;
      int nPoslist;

      /* iOff is currently the offset of the size field of a position list. */
      iOff += getVarint32(&pLeaf->p[iOff], nPoslist);
      iOff += nPoslist;

      if( iOff<pLeaf->n ){
        iOff += getVarint(&pLeaf->p[iOff], (u64*)&iDelta);
        if( iDelta==0 ) return;
      }
    }
................................................................................
    pIter->nRem = 1;
    fts5ChunkIterNext(p, pIter);
    if( p->rc ) return;
    iOff = 4;
    pLeaf = pIter->pLeaf;
  }

  iOff += getVarint32(&pLeaf->p[iOff], pIter->nRem);
  pIter->n = MIN(pLeaf->n - iOff, pIter->nRem);
  pIter->p = pLeaf->p + iOff;

  if( pIter->n==0 ){
    fts5ChunkIterNext(p, pIter);
  }
}
................................................................................
  int iVal = 0;
  if( p->rc==SQLITE_OK ){
    if( pIter->iOff>=pIter->chunk.n ){
      fts5ChunkIterNext(p, &pIter->chunk);
      if( fts5ChunkIterEof(p, &pIter->chunk) ) return 0;
      pIter->iOff = 0;
    }
    pIter->iOff += getVarint32(&pIter->chunk.p[pIter->iOff], iVal);
  }
  return iVal;
}

/*
** Advance the position list iterator to the next entry.
*/
................................................................................
  /* Whether or not it was written to disk, zero the doclist index at this
  ** point */
  sqlite3Fts5BufferZero(&pWriter->dlidx);
  pWriter->bDlidxPrevValid = 0;
}

static void fts5WriteBtreeGrow(Fts5Index *p, Fts5SegWriter *pWriter){

  Fts5PageWriter *aNew;
  Fts5PageWriter *pNew;
  int nNew = sizeof(Fts5PageWriter) * (pWriter->nWriter+1);

  aNew = (Fts5PageWriter*)sqlite3_realloc(pWriter->aWriter, nNew);
  if( aNew==0 ) return;




  pNew = &aNew[pWriter->nWriter];
  memset(pNew, 0, sizeof(Fts5PageWriter));
  pNew->pgno = 1;
  fts5BufferAppendVarint(&p->rc, &pNew->buf, 1);

  pWriter->nWriter++;
  pWriter->aWriter = aNew;

}

/*
** This is called once for each leaf page except the first that contains
** at least one term. Argument (nTerm/pTerm) is the split-key - a term that
** is larger than all terms written to earlier leaves, and equal to or
** smaller than the first term on the new leaf.
................................................................................
#ifdef SQLITE_DEBUG
      for(iLvl=0; nBest==0 && iLvl<pStruct->nLevel; iLvl++){
        assert( pStruct->aLevel[iLvl].nSeg==0 );
      }
#endif

      if( nBest<p->pConfig->nAutomerge 
          && pStruct->aLevel[iBestLvl].nMerge==0 
        ){
        break;
      }
      fts5IndexMergeLevel(p, iIdx, &pStruct, iBestLvl, &nRem);
      fts5StructurePromote(p, iBestLvl+1, pStruct);
      assert( nRem==0 || p->rc==SQLITE_OK );



      *ppStruct = pStruct;
    }
  }
}

static void fts5IndexCrisisMerge(
  Fts5Index *p,                   /* FTS5 backend object */
................................................................................
    if( p->rc==SQLITE_OK ){
      pSeg = &pStruct->aLevel[0].aSeg[ pStruct->aLevel[0].nSeg++ ];
      pSeg->iSegid = iSegid;
      pSeg->nHeight = nHeight;
      pSeg->pgnoFirst = 1;
      pSeg->pgnoLast = pgnoLast;
    }

  }

  if( p->pConfig->nAutomerge>0 ) fts5IndexWork(p, iHash, &pStruct, pgnoLast);
  fts5IndexCrisisMerge(p, iHash, &pStruct);
  fts5StructureWrite(p, iHash, pStruct);
  fts5StructureRelease(pStruct);
}
................................................................................
    ** to or larger than the split-key in iter.term.  */
    iOff = fts5GetU16(&pLeaf->p[2]);
    if( iOff==0 ){
      p->rc = FTS5_CORRUPT;
    }else{
      int nTerm;                  /* Size of term on leaf in bytes */
      int res;                    /* Comparison of term and split-key */
      iOff += getVarint32(&pLeaf->p[iOff], nTerm);
      res = memcmp(&pLeaf->p[iOff], iter.term.p, MIN(nTerm, iter.term.n));
      if( res==0 ) res = nTerm - iter.term.n;
      if( res<0 ){
        p->rc = FTS5_CORRUPT;
      }
    }
    fts5DataRelease(pLeaf);
................................................................................
        pIter->iRowid += iDelta;
      }else{
        pIter->iRowid -= iDelta;
      }
    }else{
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid);
    }
    pIter->i += getVarint32(&pIter->a[pIter->i], pIter->nPoslist);
    pIter->aPoslist = &pIter->a[pIter->i];
    pIter->i += pIter->nPoslist;
  }else{
    pIter->aPoslist = 0;
  }
}

................................................................................
      assert( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 );
      if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break;

      if( doclist.n>0 
       && ((!bAsc && iRowid>=iLastRowid) || (bAsc && iRowid<=iLastRowid))
      ){

        for(i=0; doclist.n && p->rc==SQLITE_OK; i++){
          assert( i<nBuf );
          if( aBuf[i].n==0 ){
            fts5BufferSwap(&doclist, &aBuf[i]);
            fts5BufferZero(&doclist);
          }else{
            fts5MergePrefixLists(p, bAsc, &doclist, &aBuf[i]);
            fts5BufferZero(&aBuf[i]);
................................................................................
**
** The return value is the number of bytes read from the input buffer.
*/
static int fts5DecodePoslist(int *pRc, Fts5Buffer *pBuf, const u8 *a, int n){
  int iOff = 0;
  while( iOff<n ){
    int iVal;
    iOff += getVarint32(&a[iOff], iVal);
    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " %d", iVal);
  }
  return iOff;
}

/*
** The start of buffer (a/n) contains the start of a doclist. The doclist
................................................................................

  if( iOff<n ){
    iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDocid);
    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid);
  }
  while( iOff<n ){
    int nPos;
    iOff += getVarint32(&a[iOff], nPos);
    iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos));
    if( iOff<n ){
      i64 iDelta;
      iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDelta);
      if( iDelta==0 ) return iOff;
      iDocid -= iDelta;
      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid);
................................................................................
      if( iRowidOff ){
        iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], n-iOff);
      }

      assert( iTermOff==0 || iOff==iTermOff );
      while( iOff<n ){
        int nByte;
        iOff += getVarint32(&a[iOff], nByte);
        term.n= nKeep;
        fts5BufferAppendBlob(&rc, &term, nByte, &a[iOff]);
        iOff += nByte;

        sqlite3Fts5BufferAppendPrintf(
            &rc, &s, " term=%.*s", term.n, (const char*)term.p
        );
        iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], n-iOff);
        if( iOff<n ){
          iOff += getVarint32(&a[iOff], nKeep);
        }
      }
      fts5BufferFree(&term);
    }else{
      Fts5NodeIter ss;
      for(fts5NodeIterInit(a, n, &ss); ss.aData; fts5NodeIterNext(&rc, &ss)){
        if( ss.term.n==0 ){







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
|







 







|
|








|
|
|
|







 







>







 







|
>







 







|
>

<
<
<
<
<
<
<
<
<
|
|
|
<
<
<
<
<
<
<
<
|
<
<













|







 







|
|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







>
|
|
|

|
|
>
>
|
>
|
|
|
|

|
|
>







 







|
|



<

>
>
>







 







>







 







|







 







|







 







|







 







|







 







|







 







|









|







599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
...
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
...
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
....
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
....
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
....
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281









1282
1283
1284








1285


1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
....
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
....
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
....
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
....
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
....
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
....
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
....
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
....
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
....
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
....
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
....
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
....
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
....
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212

3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
....
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
....
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
....
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
....
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
....
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
....
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
....
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
  aOut[0] = (iVal>>8);
  aOut[1] = (iVal&0xFF);
}

static u16 fts5GetU16(const u8 *aIn){
  return ((u16)aIn[0] << 8) + aIn[1];
}

/*
** This is a copy of the sqlite3GetVarint32() routine from the SQLite core.
** Except, this version does handle the single byte case that the core
** version depends on being handled before its function is called.
*/
int sqlite3Fts5GetVarint32(const unsigned char *p, u32 *v){
  u32 a,b;

  /* The 1-byte case. Overwhelmingly the most common. */
  a = *p;
  /* a: p0 (unmasked) */
  if (!(a&0x80))
  {
    /* Values between 0 and 127 */
    *v = a;
    return 1;
  }

  /* The 2-byte case */
  p++;
  b = *p;
  /* b: p1 (unmasked) */
  if (!(b&0x80))
  {
    /* Values between 128 and 16383 */
    a &= 0x7f;
    a = a<<7;
    *v = a | b;
    return 2;
  }

  /* The 3-byte case */
  p++;
  a = a<<14;
  a |= *p;
  /* a: p0<<14 | p2 (unmasked) */
  if (!(a&0x80))
  {
    /* Values between 16384 and 2097151 */
    a &= (0x7f<<14)|(0x7f);
    b &= 0x7f;
    b = b<<7;
    *v = a | b;
    return 3;
  }

  /* A 32-bit varint is used to store size information in btrees.
  ** Objects are rarely larger than 2MiB limit of a 3-byte varint.
  ** A 3-byte varint is sufficient, for example, to record the size
  ** of a 1048569-byte BLOB or string.
  **
  ** We only unroll the first 1-, 2-, and 3- byte cases.  The very
  ** rare larger cases can be handled by the slower 64-bit varint
  ** routine.
  */
  {
    u64 v64;
    u8 n;
    p -= 2;
    n = sqlite3GetVarint(p, &v64);
    *v = (u32)v64;
    assert( n>3 && n<=9 );
    return n;
  }
}

/*
** Allocate and return a buffer at least nByte bytes in size.
**
** If an OOM error is encountered, return NULL and set the error code in
** the Fts5Index handle passed as the first argument.
*/
................................................................................

  /* Grab the cookie value */
  if( piCookie ) *piCookie = sqlite3Fts5Get32(pData);
  i = 4;

  /* Read the total number of levels and segments from the start of the
  ** structure record.  */
  i += fts5GetVarint32(&pData[i], nLevel);
  i += fts5GetVarint32(&pData[i], nSegment);
  nByte = (
      sizeof(Fts5Structure) +                    /* Main structure */
      sizeof(Fts5StructureLevel) * (nLevel)      /* aLevel[] array */
  );
  pRet = (Fts5Structure*)sqlite3Fts5MallocZero(&rc, nByte);

  if( pRet ){
................................................................................
    i += sqlite3GetVarint(&pData[i], &pRet->nWriteCounter);

    for(iLvl=0; rc==SQLITE_OK && iLvl<nLevel; iLvl++){
      Fts5StructureLevel *pLvl = &pRet->aLevel[iLvl];
      int nTotal;
      int iSeg;

      i += fts5GetVarint32(&pData[i], pLvl->nMerge);
      i += fts5GetVarint32(&pData[i], nTotal);
      assert( nTotal>=pLvl->nMerge );
      pLvl->aSeg = (Fts5StructureSegment*)sqlite3Fts5MallocZero(&rc, 
          nTotal * sizeof(Fts5StructureSegment)
      );

      if( rc==SQLITE_OK ){
        pLvl->nSeg = nTotal;
        for(iSeg=0; iSeg<nTotal; iSeg++){
          i += fts5GetVarint32(&pData[i], pLvl->aSeg[iSeg].iSegid);
          i += fts5GetVarint32(&pData[i], pLvl->aSeg[iSeg].nHeight);
          i += fts5GetVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoFirst);
          i += fts5GetVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoLast);
        }
      }else{
        fts5StructureRelease(pRet);
        pRet = 0;
      }
    }
  }
................................................................................
  Fts5Structure *pStruct
){
  int il, is;
  Fts5StructureLevel *pOut = &pStruct->aLevel[iPromote];

  for(il=iPromote+1; il<pStruct->nLevel; il++){
    Fts5StructureLevel *pLvl = &pStruct->aLevel[il];
    if( pLvl->nMerge ) return;
    for(is=pLvl->nSeg-1; is>=0; is--){
      int sz = fts5SegmentSize(&pLvl->aSeg[is]);
      if( sz>szPromote ) return;
      fts5StructureExtendLevel(&p->rc, pStruct, iPromote, 1, 1);
      if( p->rc ) return;
      memcpy(pOut->aSeg, &pLvl->aSeg[is], sizeof(Fts5StructureSegment));
      pOut->nSeg++;
................................................................................

    pSeg = &pStruct->aLevel[iLvl].aSeg[pStruct->aLevel[iLvl].nSeg-1];
    szSeg = (1 + pSeg->pgnoLast - pSeg->pgnoFirst);

    /* Check for condition (a) */
    for(iTst=iLvl-1; iTst>=0 && pStruct->aLevel[iTst].nSeg==0; iTst--);
    pTst = &pStruct->aLevel[iTst];
    assert( pTst->nMerge==0 );
    if( iTst>=0 ){
      int i;
      int szMax = 0;
      for(i=0; i<pTst->nSeg; i++){
        int sz = pTst->aSeg[i].pgnoLast - pTst->aSeg[i].pgnoFirst + 1;
        if( sz>szMax ) szMax = sz;
      }
      if( szMax>=szSeg ){
................................................................................
        /* Condition (a) is true. Promote the newest segment on level 
        ** iLvl to level iTst.  */
        iPromote = iTst;
        szPromote = szMax;
      }
    }

    /* If condition (a) is not met, assume (b) is true. StructurePromoteTo()
    ** is a no-op if it is not.  */
    if( iPromote<0 ){









      iPromote = iLvl;
      szPromote = szSeg;
    }








    fts5StructurePromoteTo(p, iPromote, szPromote, pStruct);


  }
}


/*
** If the pIter->iOff offset currently points to an entry indicating one
** or more term-less nodes, advance past it and set pIter->nEmpty to
** the number of empty child nodes.
*/
static void fts5NodeIterGobbleNEmpty(Fts5NodeIter *pIter){
  if( pIter->iOff<pIter->nData && 0==(pIter->aData[pIter->iOff] & 0xfe) ){
    pIter->bDlidx = pIter->aData[pIter->iOff] & 0x01;
    pIter->iOff++;
    pIter->iOff += fts5GetVarint32(&pIter->aData[pIter->iOff], pIter->nEmpty);
  }else{
    pIter->nEmpty = 0;
    pIter->bDlidx = 0;
  }
}

/*
................................................................................
*/
static void fts5NodeIterNext(int *pRc, Fts5NodeIter *pIter){
  if( pIter->iOff>=pIter->nData ){
    pIter->aData = 0;
    pIter->iChild += pIter->nEmpty;
  }else{
    int nPre, nNew;
    pIter->iOff += fts5GetVarint32(&pIter->aData[pIter->iOff], nPre);
    pIter->iOff += fts5GetVarint32(&pIter->aData[pIter->iOff], nNew);
    pIter->term.n = nPre-2;
    fts5BufferAppendBlob(pRc, &pIter->term, nNew, pIter->aData+pIter->iOff);
    pIter->iOff += nNew;
    pIter->iChild += (1 + pIter->nEmpty);
    fts5NodeIterGobbleNEmpty(pIter);
    if( *pRc ) pIter->aData = 0;
  }
................................................................................
** Initialize the iterator object pIter to iterate through the internal
** segment node in pData.
*/
static void fts5NodeIterInit(const u8 *aData, int nData, Fts5NodeIter *pIter){
  memset(pIter, 0, sizeof(*pIter));
  pIter->aData = aData;
  pIter->nData = nData;
  pIter->iOff = fts5GetVarint32(aData, pIter->iChild);
  fts5NodeIterGobbleNEmpty(pIter);
}

/*
** Free any memory allocated by the iterator object.
*/
static void fts5NodeIterFree(Fts5NodeIter *pIter){
................................................................................
** position list. The position list belonging to document pIter->iRowid.
*/
static void fts5SegIterLoadTerm(Fts5Index *p, Fts5SegIter *pIter, int nKeep){
  u8 *a = pIter->pLeaf->p;        /* Buffer to read data from */
  int iOff = pIter->iLeafOffset;  /* Offset to read at */
  int nNew;                       /* Bytes of new data */

  iOff += fts5GetVarint32(&a[iOff], nNew);
  pIter->term.n = nKeep;
  fts5BufferAppendBlob(&p->rc, &pIter->term, nNew, &a[iOff]);
  iOff += nNew;
  pIter->iTermLeafOffset = iOff;
  pIter->iTermLeafPgno = pIter->iLeafPgno;
  if( iOff>=pIter->pLeaf->n ){
    fts5SegIterNextPage(p, pIter);
................................................................................
  u8 *a = pIter->pLeaf->p;
  int iRowidOffset = 0;

  while( p->rc==SQLITE_OK && i<n ){
    i64 iDelta = 0;
    int nPos;

    i += fts5GetVarint32(&a[i], nPos);
    i += nPos;
    if( i>=n ) break;
    i += getVarint(&a[i], (u64*)&iDelta);
    if( iDelta==0 ) break;
    pIter->iRowid -= iDelta;

    if( iRowidOffset>=pIter->nRowidOffset ){
................................................................................
        u8 *a = pIter->pLeaf->p;
        int iOff;
        int nPos;
        i64 iDelta;
        pIter->iRowidOffset--;

        pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset];
        iOff += fts5GetVarint32(&a[iOff], nPos);
        iOff += nPos;
        getVarint(&a[iOff], (u64*)&iDelta);
        pIter->iRowid += iDelta;
      }else{
        fts5SegIterReverseNewPage(p, pIter);
      }
    }else{
................................................................................
      /* Search for the end of the position list within the current page. */
      u8 *a = pLeaf->p;
      int n = pLeaf->n;

      iOff = pIter->iLeafOffset;
      if( iOff<n ){
        int nPoslist;
        iOff += fts5GetVarint32(&a[iOff], nPoslist);
        iOff += nPoslist;
      }

      if( iOff<n ){
        /* The next entry is on the current page */
        u64 iDelta;
        iOff += sqlite3GetVarint(&a[iOff], &iDelta);
................................................................................
        pIter->iLeafOffset = iOff;
        if( iDelta==0 ){
          bNewTerm = 1;
          if( iOff>=n ){
            fts5SegIterNextPage(p, pIter);
            pIter->iLeafOffset = 4;
          }else if( iOff!=fts5GetU16(&a[2]) ){
            pIter->iLeafOffset += fts5GetVarint32(&a[iOff], nKeep);
          }
        }else{
          pIter->iRowid -= iDelta;
        }
      }else{
        iOff = 0;
        /* Next entry is not on the current page */
................................................................................
    pLast = fts5DataRead(p, FTS5_SEGMENT_ROWID(iIdx, iSegid, 0, pgnoLast));
  }else{
    while( iOff<pLeaf->n ){
      int nPos;
      i64 iDelta;

      /* Position list size in bytes */
      iOff += fts5GetVarint32(&pLeaf->p[iOff], nPos);
      iOff += nPos;
      if( iOff>=pLeaf->n ) break;

      /* Rowid delta. Or, if 0x00, the end of doclist marker. */
      nPos = getVarint(&pLeaf->p[iOff], (u64*)&iDelta);
      if( iDelta==0 ) break;
      iOff += nPos;
................................................................................
  ** term. */
  if( pIter->iTermLeafPgno==pIter->iLeafPgno ){
    while( iOff<pLeaf->n ){
      i64 iDelta;
      int nPoslist;

      /* iOff is currently the offset of the size field of a position list. */
      iOff += fts5GetVarint32(&pLeaf->p[iOff], nPoslist);
      iOff += nPoslist;

      if( iOff<pLeaf->n ){
        iOff += getVarint(&pLeaf->p[iOff], (u64*)&iDelta);
        if( iDelta==0 ) return;
      }
    }
................................................................................
    pIter->nRem = 1;
    fts5ChunkIterNext(p, pIter);
    if( p->rc ) return;
    iOff = 4;
    pLeaf = pIter->pLeaf;
  }

  iOff += fts5GetVarint32(&pLeaf->p[iOff], pIter->nRem);
  pIter->n = MIN(pLeaf->n - iOff, pIter->nRem);
  pIter->p = pLeaf->p + iOff;

  if( pIter->n==0 ){
    fts5ChunkIterNext(p, pIter);
  }
}
................................................................................
  int iVal = 0;
  if( p->rc==SQLITE_OK ){
    if( pIter->iOff>=pIter->chunk.n ){
      fts5ChunkIterNext(p, &pIter->chunk);
      if( fts5ChunkIterEof(p, &pIter->chunk) ) return 0;
      pIter->iOff = 0;
    }
    pIter->iOff += fts5GetVarint32(&pIter->chunk.p[pIter->iOff], iVal);
  }
  return iVal;
}

/*
** Advance the position list iterator to the next entry.
*/
................................................................................
  /* Whether or not it was written to disk, zero the doclist index at this
  ** point */
  sqlite3Fts5BufferZero(&pWriter->dlidx);
  pWriter->bDlidxPrevValid = 0;
}

static void fts5WriteBtreeGrow(Fts5Index *p, Fts5SegWriter *pWriter){
  if( p->rc==SQLITE_OK ){
    Fts5PageWriter *aNew;
    Fts5PageWriter *pNew;
    int nNew = sizeof(Fts5PageWriter) * (pWriter->nWriter+1);

    aNew = (Fts5PageWriter*)sqlite3_realloc(pWriter->aWriter, nNew);
    if( aNew==0 ){
      p->rc = SQLITE_NOMEM;
      return;
    }

    pNew = &aNew[pWriter->nWriter];
    memset(pNew, 0, sizeof(Fts5PageWriter));
    pNew->pgno = 1;
    fts5BufferAppendVarint(&p->rc, &pNew->buf, 1);

    pWriter->nWriter++;
    pWriter->aWriter = aNew;
  }
}

/*
** This is called once for each leaf page except the first that contains
** at least one term. Argument (nTerm/pTerm) is the split-key - a term that
** is larger than all terms written to earlier leaves, and equal to or
** smaller than the first term on the new leaf.
................................................................................
#ifdef SQLITE_DEBUG
      for(iLvl=0; nBest==0 && iLvl<pStruct->nLevel; iLvl++){
        assert( pStruct->aLevel[iLvl].nSeg==0 );
      }
#endif

      if( nBest<p->pConfig->nAutomerge 
       && pStruct->aLevel[iBestLvl].nMerge==0 
      ){
        break;
      }
      fts5IndexMergeLevel(p, iIdx, &pStruct, iBestLvl, &nRem);

      assert( nRem==0 || p->rc==SQLITE_OK );
      if( p->rc==SQLITE_OK && pStruct->aLevel[iBestLvl].nMerge==0 ){
        fts5StructurePromote(p, iBestLvl+1, pStruct);
      }
      *ppStruct = pStruct;
    }
  }
}

static void fts5IndexCrisisMerge(
  Fts5Index *p,                   /* FTS5 backend object */
................................................................................
    if( p->rc==SQLITE_OK ){
      pSeg = &pStruct->aLevel[0].aSeg[ pStruct->aLevel[0].nSeg++ ];
      pSeg->iSegid = iSegid;
      pSeg->nHeight = nHeight;
      pSeg->pgnoFirst = 1;
      pSeg->pgnoLast = pgnoLast;
    }
    fts5StructurePromote(p, 0, pStruct);
  }

  if( p->pConfig->nAutomerge>0 ) fts5IndexWork(p, iHash, &pStruct, pgnoLast);
  fts5IndexCrisisMerge(p, iHash, &pStruct);
  fts5StructureWrite(p, iHash, pStruct);
  fts5StructureRelease(pStruct);
}
................................................................................
    ** to or larger than the split-key in iter.term.  */
    iOff = fts5GetU16(&pLeaf->p[2]);
    if( iOff==0 ){
      p->rc = FTS5_CORRUPT;
    }else{
      int nTerm;                  /* Size of term on leaf in bytes */
      int res;                    /* Comparison of term and split-key */
      iOff += fts5GetVarint32(&pLeaf->p[iOff], nTerm);
      res = memcmp(&pLeaf->p[iOff], iter.term.p, MIN(nTerm, iter.term.n));
      if( res==0 ) res = nTerm - iter.term.n;
      if( res<0 ){
        p->rc = FTS5_CORRUPT;
      }
    }
    fts5DataRelease(pLeaf);
................................................................................
        pIter->iRowid += iDelta;
      }else{
        pIter->iRowid -= iDelta;
      }
    }else{
      pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid);
    }
    pIter->i += fts5GetVarint32(&pIter->a[pIter->i], pIter->nPoslist);
    pIter->aPoslist = &pIter->a[pIter->i];
    pIter->i += pIter->nPoslist;
  }else{
    pIter->aPoslist = 0;
  }
}

................................................................................
      assert( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 );
      if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break;

      if( doclist.n>0 
       && ((!bAsc && iRowid>=iLastRowid) || (bAsc && 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{
            fts5MergePrefixLists(p, bAsc, &doclist, &aBuf[i]);
            fts5BufferZero(&aBuf[i]);
................................................................................
**
** The return value is the number of bytes read from the input buffer.
*/
static int fts5DecodePoslist(int *pRc, Fts5Buffer *pBuf, const u8 *a, int n){
  int iOff = 0;
  while( iOff<n ){
    int iVal;
    iOff += fts5GetVarint32(&a[iOff], iVal);
    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " %d", iVal);
  }
  return iOff;
}

/*
** The start of buffer (a/n) contains the start of a doclist. The doclist
................................................................................

  if( iOff<n ){
    iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDocid);
    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid);
  }
  while( iOff<n ){
    int nPos;
    iOff += fts5GetVarint32(&a[iOff], nPos);
    iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos));
    if( iOff<n ){
      i64 iDelta;
      iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDelta);
      if( iDelta==0 ) return iOff;
      iDocid -= iDelta;
      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid);
................................................................................
      if( iRowidOff ){
        iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], n-iOff);
      }

      assert( iTermOff==0 || iOff==iTermOff );
      while( iOff<n ){
        int nByte;
        iOff += fts5GetVarint32(&a[iOff], nByte);
        term.n= nKeep;
        fts5BufferAppendBlob(&rc, &term, nByte, &a[iOff]);
        iOff += nByte;

        sqlite3Fts5BufferAppendPrintf(
            &rc, &s, " term=%.*s", term.n, (const char*)term.p
        );
        iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], n-iOff);
        if( iOff<n ){
          iOff += fts5GetVarint32(&a[iOff], nKeep);
        }
      }
      fts5BufferFree(&term);
    }else{
      Fts5NodeIter ss;
      for(fts5NodeIterInit(a, n, &ss); ss.aData; fts5NodeIterNext(&rc, &ss)){
        if( ss.term.n==0 ){

Changes to ext/fts5/test/fts5_common.tcl.

110
111
112
113
114
115
116





117













    fts5_test_queryphrase
  } {
    sqlite3_fts5_create_function $db $f $f
  }
}


























>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

    fts5_test_queryphrase
  } {
    sqlite3_fts5_create_function $db $f $f
  }
}

proc fts5_level_segs {tbl} {
  set sql "SELECT fts5_decode(rowid,block) aS r FROM ${tbl}_data WHERE rowid=10"
  set ret [list]
  foreach L [lrange [db one $sql] 1 end] {
    lappend ret [expr [llength $L] - 2]
  }
  set ret
} 

proc fts5_rnddoc {n} {
  set map [list 0 a  1 b  2 c  3 d  4 e  5 f  6 g  7 h  8 i  9 j]
  set doc [list]
  for {set i 0} {$i < $n} {incr i} {
    lappend doc "x[string map $map [format %.3d [expr int(rand()*1000)]]]"
  }
  set doc
}

Changes to ext/fts5/test/fts5ab.test.

145
146
147
148
149
150
151


152


















































































153

  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.4.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid ASC
  } $res
}






















































































finish_test








>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
  7 {"abashing abases abasement abaft abashing"} {8}
} {
  do_execsql_test 3.4.$tn {
    SELECT rowid FROM t1 WHERE t1 MATCH $expr ORDER BY rowid ASC
  } $res
}

#-------------------------------------------------------------------------
# Documents with more than 2M tokens.
#

do_execsql_test 4.0 {
  CREATE VIRTUAL TABLE s1 USING fts5(x);
}
foreach {tn doc} [list \
  1 [string repeat {a x } 1500000]       \
  2 "[string repeat {a a } 1500000] x"   \
] {
  do_execsql_test 4.$tn { INSERT INTO s1 VALUES($doc) }
}

do_execsql_test 4.3 {
  SELECT rowid FROM s1 WHERE s1 MATCH 'x'
} {2 1}

do_execsql_test 4.4 {
  SELECT rowid FROM s1 WHERE s1 MATCH '"a x"'
} {2 1}

#-------------------------------------------------------------------------
# Check that a special case of segment promotion works. The case is where
# a new segment is written to level L, but the oldest segment within level
# (L-2) is larger than it.
#
do_execsql_test 5.0 {
  CREATE VIRTUAL TABLE s2 USING fts5(x);
  INSERT INTO s2(s2, rank) VALUES('pgsz', 32);
  INSERT INTO s2(s2, rank) VALUES('automerge', 0);
}

proc rnddoc {n} {
  set map [list 0 a  1 b  2 c  3 d  4 e  5 f  6 g  7 h  8 i  9 j]
  set doc [list]
  for {set i 0} {$i < $n} {incr i} {
    lappend doc [string map $map [format %.3d [expr int(rand()*1000)]]]
  }
  set doc
}
db func rnddoc rnddoc

do_test 5.1 {
  for {set i 1} {$i <= 65} {incr i} {
    execsql { INSERT INTO s2 VALUES(rnddoc(10)) }
  }
  for {set i 1} {$i <= 63} {incr i} {
    execsql { DELETE FROM s2 WHERE rowid = $i }
  }
  fts5_level_segs s2
} {0 8}

do_test 5.2 {
  execsql {
    INSERT INTO s2(s2, rank) VALUES('automerge', 8);
  }
  for {set i 0} {$i < 7} {incr i} {
    execsql { INSERT INTO s2 VALUES(rnddoc(50)) }
  }
  fts5_level_segs s2
} {8 0 0}

# Test also the other type of segment promotion - when a new segment is written
# that is larger than segments immediately following it.
do_test 5.3 {
  execsql {
    DROP TABLE s2;
    CREATE VIRTUAL TABLE s2 USING fts5(x);
    INSERT INTO s2(s2, rank) VALUES('pgsz', 32);
    INSERT INTO s2(s2, rank) VALUES('automerge', 0);
  }

  for {set i 1} {$i <= 16} {incr i} {
    execsql { INSERT INTO s2 VALUES(rnddoc(5)) }
  }
  fts5_level_segs s2
} {0 1}

do_test 5.4 {
  execsql { INSERT INTO s2 VALUES(rnddoc(160)) }
  fts5_level_segs s2
} {2 0}


finish_test

Changes to ext/fts5/test/fts5fault1.test.

206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
...
272
273
274
275
276
277
278
279
280

281
282
283
284
285
286
287
288


289


































































290
291
      SELECT max(rowid) FROM x1_data 
    )
  }
} -test {
  faultsim_test_result [list 0 1]
}

}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 6.0 {
  CREATE VIRTUAL TABLE x1 USING fts5(x);
  INSERT INTO x1(x1, rank) VALUES('automerge', 0);

................................................................................
  faultsim_restore_and_reopen
} -body {
  execsql { INSERT INTO x1(x1) VALUES('optimize') }
} -test {
  faultsim_test_result [list 0 {}]
}


#-------------------------------------------------------------------------

do_faultsim_test 7.0 -faults oom* -prep {
  catch { db close }
} -body {
  sqlite3 db test.db
} -test {
  faultsim_test_result [list 0 {}] [list 1 {}]
}






































































finish_test








<
<







 







<

>








>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


206
207
208
209
210
211
212


213
214
215
216
217
218
219
...
270
271
272
273
274
275
276

277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
      SELECT max(rowid) FROM x1_data 
    )
  }
} -test {
  faultsim_test_result [list 0 1]
}



#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 6.0 {
  CREATE VIRTUAL TABLE x1 USING fts5(x);
  INSERT INTO x1(x1, rank) VALUES('automerge', 0);

................................................................................
  faultsim_restore_and_reopen
} -body {
  execsql { INSERT INTO x1(x1) VALUES('optimize') }
} -test {
  faultsim_test_result [list 0 {}]
}


#-------------------------------------------------------------------------
#
do_faultsim_test 7.0 -faults oom* -prep {
  catch { db close }
} -body {
  sqlite3 db test.db
} -test {
  faultsim_test_result [list 0 {}] [list 1 {}]
}

#-------------------------------------------------------------------------
# A prefix query against a large document set.
#
proc rnddoc {n} {
  set map [list 0 a  1 b  2 c  3 d  4 e  5 f  6 g  7 h  8 i  9 j]
  set doc [list]
  for {set i 0} {$i < $n} {incr i} {
    lappend doc "x[string map $map [format %.3d [expr int(rand()*1000)]]]"
  }
  set doc
}

reset_db
db func rnddoc rnddoc

do_test 8.0 {
  execsql { CREATE VIRTUAL TABLE x1 USING fts5(a) }
  set ::res [list]
  for {set i 100} {$i>0} {incr i -1} {
    execsql { INSERT INTO x1 VALUES( rnddoc(50) ) }
    lappend ::res $i
  }
} {}

do_faultsim_test 8.1 -faults oom* -prep {
} -body {
  execsql { 
    SELECT rowid FROM x1 WHERE x1 MATCH 'x*'
  }
} -test {
  faultsim_test_result [list 0 $::res]
}

}

#-------------------------------------------------------------------------
# Segment promotion.
#
do_test 9.0 {
  reset_db
  db func rnddoc fts5_rnddoc
  execsql {
    CREATE VIRTUAL TABLE s2 USING fts5(x);
    INSERT INTO s2(s2, rank) VALUES('pgsz', 32);
    INSERT INTO s2(s2, rank) VALUES('automerge', 0);
  }

  for {set i 1} {$i <= 16} {incr i} {
    execsql { INSERT INTO s2 VALUES(rnddoc(5)) }
  }
  fts5_level_segs s2
} {0 1}
faultsim_save_and_close

do_faultsim_test 9.1 -faults oom-* -prep {
  faultsim_restore_and_reopen
  db func rnddoc fts5_rnddoc
} -body {
  execsql { INSERT INTO s2 VALUES(rnddoc(160)) }
} -test {
  faultsim_test_result {0 {}}
  if {$testrc==0} {
    set ls [fts5_level_segs s2]
    if {$ls != "2 0"} { error "fts5_level_segs says {$ls}" }
  }
}



finish_test