third_party/sqlite/sqlite-src-3080704/ext/fts3/fts3_write.c - Issue 2363173002: [sqlite] Remove obsolete reference version 3.8.7.4.

Side by Side Diff: third_party/sqlite/sqlite-src-3080704/ext/fts3/fts3_write.c

Issue 2363173002: [sqlite] Remove obsolete reference version 3.8.7.4. (Closed)

Patch Set: Created 4 years, 2 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

« no previous file with comments | « third_party/sqlite/sqlite-src-3080704/ext/fts3/fts3_unicode2.c ('k') | third_party/sqlite/sqlite-src-3080704/ext/fts3/fts3speed.tcl » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Hide Comments ('s')

OLD	NEW
	(Empty)
1 /*

2 ** 2009 Oct 23

3 **

4 ** The author disclaims copyright to this source code. In place of

5 ** a legal notice, here is a blessing:

6 **

7 ** May you do good and not evil.

8 ** May you find forgiveness for yourself and forgive others.

9 ** May you share freely, never taking more than you give.

10 **

11 ******************************************************************************

12 **

13 ** This file is part of the SQLite FTS3 extension module. Specifically,

14 ** this file contains code to insert, update and delete rows from FTS3

15 ** tables. It also contains code to merge FTS3 b-tree segments. Some

16 ** of the sub-routines used to merge segments are also used by the query

17 ** code in fts3.c.

18 */

19

20 #include "fts3Int.h"

21 #if !defined(SQLITE_CORE) \|\| defined(SQLITE_ENABLE_FTS3)

22

23 #include <string.h>

24 #include <assert.h>

25 #include <stdlib.h>

26

27

28 #define FTS_MAX_APPENDABLE_HEIGHT 16

29

30 /*

31 ** When full-text index nodes are loaded from disk, the buffer that they

32 ** are loaded into has the following number of bytes of padding at the end

33 ** of it. i.e. if a full-text index node is 900 bytes in size, then a buffer

34 ** of 920 bytes is allocated for it.

35 **

36 ** This means that if we have a pointer into a buffer containing node data,

37 ** it is always safe to read up to two varints from it without risking an

38 ** overread, even if the node data is corrupted.

39 */

40 #define FTS3_NODE_PADDING (FTS3_VARINT_MAX*2)

41

42 /*

43 ** Under certain circumstances, b-tree nodes (doclists) can be loaded into

44 ** memory incrementally instead of all at once. This can be a big performance

45 ** win (reduced IO and CPU) if SQLite stops calling the virtual table xNext()

46 ** method before retrieving all query results (as may happen, for example,

47 ** if a query has a LIMIT clause).

48 **

49 ** Incremental loading is used for b-tree nodes FTS3_NODE_CHUNK_THRESHOLD

50 ** bytes and larger. Nodes are loaded in chunks of FTS3_NODE_CHUNKSIZE bytes.

51 ** The code is written so that the hard lower-limit for each of these values

52 ** is 1. Clearly such small values would be inefficient, but can be useful

53 ** for testing purposes.

54 **

55 ** If this module is built with SQLITE_TEST defined, these constants may

56 ** be overridden at runtime for testing purposes. File fts3_test.c contains

57 ** a Tcl interface to read and write the values.

58 */

59 #ifdef SQLITE_TEST

60 int test_fts3_node_chunksize = (4*1024);

61 int test_fts3_node_chunk_threshold = (41024)4;

62 # define FTS3_NODE_CHUNKSIZE test_fts3_node_chunksize

63 # define FTS3_NODE_CHUNK_THRESHOLD test_fts3_node_chunk_threshold

64 #else

65 # define FTS3_NODE_CHUNKSIZE (4*1024)

66 # define FTS3_NODE_CHUNK_THRESHOLD (FTS3_NODE_CHUNKSIZE*4)

67 #endif

68

69 /*

70 ** The two values that may be meaningfully bound to the :1 parameter in

71 ** statements SQL_REPLACE_STAT and SQL_SELECT_STAT.

72 */

73 #define FTS_STAT_DOCTOTAL 0

74 #define FTS_STAT_INCRMERGEHINT 1

75 #define FTS_STAT_AUTOINCRMERGE 2

76

77 /*

78 ** If FTS_LOG_MERGES is defined, call sqlite3_log() to report each automatic

79 ** and incremental merge operation that takes place. This is used for

80 ** debugging FTS only, it should not usually be turned on in production

81 ** systems.

82 */

83 #ifdef FTS3_LOG_MERGES

84 static void fts3LogMerge(int nMerge, sqlite3_int64 iAbsLevel){

85 sqlite3_log(SQLITE_OK, "%d-way merge from level %d", nMerge, (int)iAbsLevel);

86 }

87 #else

88 #define fts3LogMerge(x, y)

89 #endif

90

91

92 typedef struct PendingList PendingList;

93 typedef struct SegmentNode SegmentNode;

94 typedef struct SegmentWriter SegmentWriter;

95

96 /*

97 ** An instance of the following data structure is used to build doclists

98 ** incrementally. See function fts3PendingListAppend() for details.

99 */

100 struct PendingList {

101 int nData;

102 char *aData;

103 int nSpace;

104 sqlite3_int64 iLastDocid;

105 sqlite3_int64 iLastCol;

106 sqlite3_int64 iLastPos;

107 };

108

109

110 /*

111 ** Each cursor has a (possibly empty) linked list of the following objects.

112 */

113 struct Fts3DeferredToken {

114 Fts3PhraseToken pToken; / Pointer to corresponding expr token */

115 int iCol; /* Column token must occur in */

116 Fts3DeferredToken pNext; / Next in list of deferred tokens */

117 PendingList pList; / Doclist is assembled here */

118 };

119

120 /*

121 ** An instance of this structure is used to iterate through the terms on

122 ** a contiguous set of segment b-tree leaf nodes. Although the details of

123 ** this structure are only manipulated by code in this file, opaque handles

124 ** of type Fts3SegReader* are also used by code in fts3.c to iterate through

125 ** terms when querying the full-text index. See functions:

126 **

127 ** sqlite3Fts3SegReaderNew()

128 ** sqlite3Fts3SegReaderFree()

129 ** sqlite3Fts3SegReaderIterate()

130 **

131 ** Methods used to manipulate Fts3SegReader structures:

132 **

133 ** fts3SegReaderNext()

134 ** fts3SegReaderFirstDocid()

135 ** fts3SegReaderNextDocid()

136 */

137 struct Fts3SegReader {

138 int iIdx; /* Index within level, or 0x7FFFFFFF for PT */

139 u8 bLookup; /* True for a lookup only */

140 u8 rootOnly; /* True for a root-only reader */

141

142 sqlite3_int64 iStartBlock; /* Rowid of first leaf block to traverse */

143 sqlite3_int64 iLeafEndBlock; /* Rowid of final leaf block to traverse */

144 sqlite3_int64 iEndBlock; /* Rowid of final block in segment (or 0) */

145 sqlite3_int64 iCurrentBlock; /* Current leaf block (or 0) */

146

147 char aNode; / Pointer to node data (or NULL) */

148 int nNode; /* Size of buffer at aNode (or 0) */

149 int nPopulate; /* If >0, bytes of buffer aNode[] loaded */

150 sqlite3_blob pBlob; / If not NULL, blob handle to read node */

151

152 Fts3HashElem **ppNextElem;

153

154 /* Variables set by fts3SegReaderNext(). These may be read directly

155 ** by the caller. They are valid from the time SegmentReaderNew() returns

156 ** until SegmentReaderNext() returns something other than SQLITE_OK

157 ** (i.e. SQLITE_DONE).

158 */

159 int nTerm; /* Number of bytes in current term */

160 char zTerm; / Pointer to current term */

161 int nTermAlloc; /* Allocated size of zTerm buffer */

162 char aDoclist; / Pointer to doclist of current entry */

163 int nDoclist; /* Size of doclist in current entry */

164

165 /* The following variables are used by fts3SegReaderNextDocid() to iterate

166 ** through the current doclist (aDoclist/nDoclist).

167 */

168 char *pOffsetList;

169 int nOffsetList; /* For descending pending seg-readers only */

170 sqlite3_int64 iDocid;

171 };

172

173 #define fts3SegReaderIsPending(p) ((p)->ppNextElem!=0)

174 #define fts3SegReaderIsRootOnly(p) ((p)->rootOnly!=0)

175

176 /*

177 ** An instance of this structure is used to create a segment b-tree in the

178 ** database. The internal details of this type are only accessed by the

179 ** following functions:

180 **

181 ** fts3SegWriterAdd()

182 ** fts3SegWriterFlush()

183 ** fts3SegWriterFree()

184 */

185 struct SegmentWriter {

186 SegmentNode pTree; / Pointer to interior tree structure */

187 sqlite3_int64 iFirst; /* First slot in %_segments written */

188 sqlite3_int64 iFree; /* Next free slot in %_segments */

189 char zTerm; / Pointer to previous term buffer */

190 int nTerm; /* Number of bytes in zTerm */

191 int nMalloc; /* Size of malloc'd buffer at zMalloc */

192 char zMalloc; / Malloc'd space (possibly) used for zTerm */

193 int nSize; /* Size of allocation at aData */

194 int nData; /* Bytes of data in aData */

195 char aData; / Pointer to block from malloc() */

196 i64 nLeafData; /* Number of bytes of leaf data written */

197 };

198

199 /*

200 ** Type SegmentNode is used by the following three functions to create

201 ** the interior part of the segment b+-tree structures (everything except

202 ** the leaf nodes). These functions and type are only ever used by code

203 ** within the fts3SegWriterXXX() family of functions described above.

204 **

205 ** fts3NodeAddTerm()

206 ** fts3NodeWrite()

207 ** fts3NodeFree()

208 **

209 ** When a b+tree is written to the database (either as a result of a merge

210 ** or the pending-terms table being flushed), leaves are written into the

211 ** database file as soon as they are completely populated. The interior of

212 ** the tree is assembled in memory and written out only once all leaves have

213 ** been populated and stored. This is Ok, as the b+-tree fanout is usually

214 ** very large, meaning that the interior of the tree consumes relatively

215 ** little memory.

216 */

217 struct SegmentNode {

218 SegmentNode pParent; / Parent node (or NULL for root node) */

219 SegmentNode pRight; / Pointer to right-sibling */

220 SegmentNode pLeftmost; / Pointer to left-most node of this depth */

221 int nEntry; /* Number of terms written to node so far */

222 char zTerm; / Pointer to previous term buffer */

223 int nTerm; /* Number of bytes in zTerm */

224 int nMalloc; /* Size of malloc'd buffer at zMalloc */

225 char zMalloc; / Malloc'd space (possibly) used for zTerm */

226 int nData; /* Bytes of valid data so far */

227 char aData; / Node data */

228 };

229

230 /*

231 ** Valid values for the second argument to fts3SqlStmt().

232 */

233 #define SQL_DELETE_CONTENT 0

234 #define SQL_IS_EMPTY 1

235 #define SQL_DELETE_ALL_CONTENT 2

236 #define SQL_DELETE_ALL_SEGMENTS 3

237 #define SQL_DELETE_ALL_SEGDIR 4

238 #define SQL_DELETE_ALL_DOCSIZE 5

239 #define SQL_DELETE_ALL_STAT 6

240 #define SQL_SELECT_CONTENT_BY_ROWID 7

241 #define SQL_NEXT_SEGMENT_INDEX 8

242 #define SQL_INSERT_SEGMENTS 9

243 #define SQL_NEXT_SEGMENTS_ID 10

244 #define SQL_INSERT_SEGDIR 11

245 #define SQL_SELECT_LEVEL 12

246 #define SQL_SELECT_LEVEL_RANGE 13

247 #define SQL_SELECT_LEVEL_COUNT 14

248 #define SQL_SELECT_SEGDIR_MAX_LEVEL 15

249 #define SQL_DELETE_SEGDIR_LEVEL 16

250 #define SQL_DELETE_SEGMENTS_RANGE 17

251 #define SQL_CONTENT_INSERT 18

252 #define SQL_DELETE_DOCSIZE 19

253 #define SQL_REPLACE_DOCSIZE 20

254 #define SQL_SELECT_DOCSIZE 21

255 #define SQL_SELECT_STAT 22

256 #define SQL_REPLACE_STAT 23

257

258 #define SQL_SELECT_ALL_PREFIX_LEVEL 24

259 #define SQL_DELETE_ALL_TERMS_SEGDIR 25

260 #define SQL_DELETE_SEGDIR_RANGE 26

261 #define SQL_SELECT_ALL_LANGID 27

262 #define SQL_FIND_MERGE_LEVEL 28

263 #define SQL_MAX_LEAF_NODE_ESTIMATE 29

264 #define SQL_DELETE_SEGDIR_ENTRY 30

265 #define SQL_SHIFT_SEGDIR_ENTRY 31

266 #define SQL_SELECT_SEGDIR 32

267 #define SQL_CHOMP_SEGDIR 33

268 #define SQL_SEGMENT_IS_APPENDABLE 34

269 #define SQL_SELECT_INDEXES 35

270 #define SQL_SELECT_MXLEVEL 36

271

272 #define SQL_SELECT_LEVEL_RANGE2 37

273 #define SQL_UPDATE_LEVEL_IDX 38

274 #define SQL_UPDATE_LEVEL 39

275

276 /*

277 ** This function is used to obtain an SQLite prepared statement handle

278 ** for the statement identified by the second argument. If successful,

279 ** *pp is set to the requested statement handle and SQLITE_OK returned.

280 ** Otherwise, an SQLite error code is returned and *pp is set to 0.

281 **

282 ** If argument apVal is not NULL, then it must point to an array with

283 ** at least as many entries as the requested statement has bound

284 ** parameters. The values are bound to the statements parameters before

285 ** returning.

286 */

287 static int fts3SqlStmt(

288 Fts3Table p, / Virtual table handle */

289 int eStmt, /* One of the SQL_XXX constants above */

290 sqlite3_stmt *pp, / OUT: Statement handle */

291 sqlite3_value *apVal / Values to bind to statement */

292 ){

293 const char *azSql[] = {

294 /* 0 */ "DELETE FROM %Q.'%q_content' WHERE rowid = ?",

295 /* 1 */ "SELECT NOT EXISTS(SELECT docid FROM %Q.'%q_content' WHERE rowid!=?)",

296 /* 2 */ "DELETE FROM %Q.'%q_content'",

297 /* 3 */ "DELETE FROM %Q.'%q_segments'",

298 /* 4 */ "DELETE FROM %Q.'%q_segdir'",

299 /* 5 */ "DELETE FROM %Q.'%q_docsize'",

300 /* 6 */ "DELETE FROM %Q.'%q_stat'",

301 /* 7 */ "SELECT %s WHERE rowid=?",

302 /* 8 */ "SELECT (SELECT max(idx) FROM %Q.'%q_segdir' WHERE level = ?) + 1",

303 /* 9 */ "REPLACE INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)",

304 /* 10 */ "SELECT coalesce((SELECT max(blockid) FROM %Q.'%q_segments') + 1, 1)",

305 /* 11 */ "REPLACE INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)",

306

307 /* Return segments in order from oldest to newest.*/

308 /* 12 */ "SELECT idx, start_block, leaves_end_block, end_block, root "

309 "FROM %Q.'%q_segdir' WHERE level = ? ORDER BY idx ASC",

310 /* 13 */ "SELECT idx, start_block, leaves_end_block, end_block, root "

311 "FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?"

312 "ORDER BY level DESC, idx ASC",

313

314 /* 14 / "SELECT count() FROM %Q.'%q_segdir' WHERE level = ?",

315 /* 15 */ "SELECT max(level) FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?",

316

317 /* 16 */ "DELETE FROM %Q.'%q_segdir' WHERE level = ?",

318 /* 17 */ "DELETE FROM %Q.'%q_segments' WHERE blockid BETWEEN ? AND ?",

319 /* 18 */ "INSERT INTO %Q.'%q_content' VALUES(%s)",

320 /* 19 */ "DELETE FROM %Q.'%q_docsize' WHERE docid = ?",

321 /* 20 */ "REPLACE INTO %Q.'%q_docsize' VALUES(?,?)",

322 /* 21 */ "SELECT size FROM %Q.'%q_docsize' WHERE docid=?",

323 /* 22 */ "SELECT value FROM %Q.'%q_stat' WHERE id=?",

324 /* 23 */ "REPLACE INTO %Q.'%q_stat' VALUES(?,?)",

325 /* 24 */ "",

326 /* 25 */ "",

327

328 /* 26 */ "DELETE FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?",

329 /* 27 / "SELECT DISTINCT level / (1024 ?) FROM %Q.'%q_segdir'",

330

331 /* This statement is used to determine which level to read the input from

332 ** when performing an incremental merge. It returns the absolute level number

333 ** of the oldest level in the db that contains at least ? segments. Or,

334 ** if no level in the FTS index contains more than ? segments, the statement

335 ** returns zero rows. */

336 /* 28 / "SELECT level FROM %Q.'%q_segdir' GROUP BY level HAVING count()>=?"

337 " ORDER BY (level %% 1024) ASC LIMIT 1",

338

339 /* Estimate the upper limit on the number of leaf nodes in a new segment

340 ** created by merging the oldest :2 segments from absolute level :1. See

341 ** function sqlite3Fts3Incrmerge() for details. */

342 /* 29 / "SELECT 2 total(1 + leaves_end_block - start_block) "

343 " FROM %Q.'%q_segdir' WHERE level = ? AND idx < ?",

344

345 /* SQL_DELETE_SEGDIR_ENTRY

346 ** Delete the %_segdir entry on absolute level :1 with index :2. */

347 /* 30 */ "DELETE FROM %Q.'%q_segdir' WHERE level = ? AND idx = ?",

348

349 /* SQL_SHIFT_SEGDIR_ENTRY

350 ** Modify the idx value for the segment with idx=:3 on absolute level :2

351 ** to :1. */

352 /* 31 */ "UPDATE %Q.'%q_segdir' SET idx = ? WHERE level=? AND idx=?",

353

354 /* SQL_SELECT_SEGDIR

355 ** Read a single entry from the %_segdir table. The entry from absolute

356 ** level :1 with index value :2. */

357 /* 32 */ "SELECT idx, start_block, leaves_end_block, end_block, root "

358 "FROM %Q.'%q_segdir' WHERE level = ? AND idx = ?",

359

360 /* SQL_CHOMP_SEGDIR

361 ** Update the start_block (:1) and root (:2) fields of the %_segdir

362 ** entry located on absolute level :3 with index :4. */

363 /* 33 */ "UPDATE %Q.'%q_segdir' SET start_block = ?, root = ?"

364 "WHERE level = ? AND idx = ?",

365

366 /* SQL_SEGMENT_IS_APPENDABLE

367 ** Return a single row if the segment with end_block=? is appendable. Or

368 ** no rows otherwise. */

369 /* 34 */ "SELECT 1 FROM %Q.'%q_segments' WHERE blockid=? AND block IS NULL",

370

371 /* SQL_SELECT_INDEXES

372 ** Return the list of valid segment indexes for absolute level ? */

373 /* 35 */ "SELECT idx FROM %Q.'%q_segdir' WHERE level=? ORDER BY 1 ASC",

374

375 /* SQL_SELECT_MXLEVEL

376 ** Return the largest relative level in the FTS index or indexes. */

377 /* 36 */ "SELECT max( level %% 1024 ) FROM %Q.'%q_segdir'",

378

379 /* Return segments in order from oldest to newest.*/

380 /* 37 */ "SELECT level, idx, end_block "

381 "FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ? "

382 "ORDER BY level DESC, idx ASC",

383

384 /* Update statements used while promoting segments */

385 /* 38 */ "UPDATE OR FAIL %Q.'%q_segdir' SET level=-1,idx=? "

386 "WHERE level=? AND idx=?",

387 /* 39 */ "UPDATE OR FAIL %Q.'%q_segdir' SET level=? WHERE level=-1"

388

389 };

390 int rc = SQLITE_OK;

391 sqlite3_stmt *pStmt;

392

393 assert( SizeofArray(azSql)==SizeofArray(p->aStmt) );

394 assert( eStmt<SizeofArray(azSql) && eStmt>=0 );

395

396 pStmt = p->aStmt[eStmt];

397 if( !pStmt ){

398 char *zSql;

399 if( eStmt==SQL_CONTENT_INSERT ){

400 zSql = sqlite3_mprintf(azSql[eStmt], p->zDb, p->zName, p->zWriteExprlist);

401 }else if( eStmt==SQL_SELECT_CONTENT_BY_ROWID ){

402 zSql = sqlite3_mprintf(azSql[eStmt], p->zReadExprlist);

403 }else{

404 zSql = sqlite3_mprintf(azSql[eStmt], p->zDb, p->zName);

405 }

406 if( !zSql ){

407 rc = SQLITE_NOMEM;

408 }else{

409 rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, NULL);

410 sqlite3_free(zSql);

411 assert( rc==SQLITE_OK \|\| pStmt==0 );

412 p->aStmt[eStmt] = pStmt;

413 }

414 }

415 if( apVal ){

416 int i;

417 int nParam = sqlite3_bind_parameter_count(pStmt);

418 for(i=0; rc==SQLITE_OK && i<nParam; i++){

419 rc = sqlite3_bind_value(pStmt, i+1, apVal[i]);

420 }

421 }

422 *pp = pStmt;

423 return rc;

424 }

425

426

427 static int fts3SelectDocsize(

428 Fts3Table pTab, / FTS3 table handle */

429 sqlite3_int64 iDocid, /* Docid to bind for SQL_SELECT_DOCSIZE */

430 sqlite3_stmt *ppStmt / OUT: Statement handle */

431 ){

432 sqlite3_stmt pStmt = 0; / Statement requested from fts3SqlStmt() */

433 int rc; /* Return code */

434

435 rc = fts3SqlStmt(pTab, SQL_SELECT_DOCSIZE, &pStmt, 0);

436 if( rc==SQLITE_OK ){

437 sqlite3_bind_int64(pStmt, 1, iDocid);

438 rc = sqlite3_step(pStmt);

439 if( rc!=SQLITE_ROW \|\| sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB ){

440 rc = sqlite3_reset(pStmt);

441 if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;

442 pStmt = 0;

443 }else{

444 rc = SQLITE_OK;

445 }

446 }

447

448 *ppStmt = pStmt;

449 return rc;

450 }

451

452 int sqlite3Fts3SelectDoctotal(

453 Fts3Table pTab, / Fts3 table handle */

454 sqlite3_stmt *ppStmt / OUT: Statement handle */

455 ){

456 sqlite3_stmt *pStmt = 0;

457 int rc;

458 rc = fts3SqlStmt(pTab, SQL_SELECT_STAT, &pStmt, 0);

459 if( rc==SQLITE_OK ){

460 sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);

461 if( sqlite3_step(pStmt)!=SQLITE_ROW

462 \|\| sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB

463 ){

464 rc = sqlite3_reset(pStmt);

465 if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;

466 pStmt = 0;

467 }

468 }

469 *ppStmt = pStmt;

470 return rc;

471 }

472

473 int sqlite3Fts3SelectDocsize(

474 Fts3Table pTab, / Fts3 table handle */

475 sqlite3_int64 iDocid, /* Docid to read size data for */

476 sqlite3_stmt *ppStmt / OUT: Statement handle */

477 ){

478 return fts3SelectDocsize(pTab, iDocid, ppStmt);

479 }

480

481 /*

482 ** Similar to fts3SqlStmt(). Except, after binding the parameters in

483 ** array apVal[] to the SQL statement identified by eStmt, the statement

484 ** is executed.

485 **

486 ** Returns SQLITE_OK if the statement is successfully executed, or an

487 ** SQLite error code otherwise.

488 */

489 static void fts3SqlExec(

490 int pRC, / Result code */

491 Fts3Table p, / The FTS3 table */

492 int eStmt, /* Index of statement to evaluate */

493 sqlite3_value *apVal / Parameters to bind */

494 ){

495 sqlite3_stmt *pStmt;

496 int rc;

497 if( *pRC ) return;

498 rc = fts3SqlStmt(p, eStmt, &pStmt, apVal);

499 if( rc==SQLITE_OK ){

500 sqlite3_step(pStmt);

501 rc = sqlite3_reset(pStmt);

502 }

503 *pRC = rc;

504 }

505

506

507 /*

508 ** This function ensures that the caller has obtained an exclusive

509 ** shared-cache table-lock on the %_segdir table. This is required before

510 ** writing data to the fts3 table. If this lock is not acquired first, then

511 ** the caller may end up attempting to take this lock as part of committing

512 ** a transaction, causing SQLite to return SQLITE_LOCKED or

513 ** LOCKED_SHAREDCACHEto a COMMIT command.

514 **

515 ** It is best to avoid this because if FTS3 returns any error when

516 ** committing a transaction, the whole transaction will be rolled back.

517 ** And this is not what users expect when they get SQLITE_LOCKED_SHAREDCACHE.

518 ** It can still happen if the user locks the underlying tables directly

519 ** instead of accessing them via FTS.

520 */

521 static int fts3Writelock(Fts3Table *p){

522 int rc = SQLITE_OK;

523

524 if( p->nPendingData==0 ){

525 sqlite3_stmt *pStmt;

526 rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_LEVEL, &pStmt, 0);

527 if( rc==SQLITE_OK ){

528 sqlite3_bind_null(pStmt, 1);

529 sqlite3_step(pStmt);

530 rc = sqlite3_reset(pStmt);

531 }

532 }

533

534 return rc;

535 }

536

537 /*

538 ** FTS maintains a separate indexes for each language-id (a 32-bit integer).

539 ** Within each language id, a separate index is maintained to store the

540 ** document terms, and each configured prefix size (configured the FTS

541 ** "prefix=" option). And each index consists of multiple levels ("relative

542 ** levels").

543 **

544 ** All three of these values (the language id, the specific index and the

545 ** level within the index) are encoded in 64-bit integer values stored

546 ** in the %_segdir table on disk. This function is used to convert three

547 ** separate component values into the single 64-bit integer value that

548 ** can be used to query the %_segdir table.

549 **

550 ** Specifically, each language-id/index combination is allocated 1024

551 ** 64-bit integer level values ("absolute levels"). The main terms index

552 ** for language-id 0 is allocate values 0-1023. The first prefix index

553 ** (if any) for language-id 0 is allocated values 1024-2047. And so on.

554 ** Language 1 indexes are allocated immediately following language 0.

555 **

556 ** So, for a system with nPrefix prefix indexes configured, the block of

557 ** absolute levels that corresponds to language-id iLangid and index

558 ** iIndex starts at absolute level ((iLangid * (nPrefix+1) + iIndex) * 1024).

559 */

560 static sqlite3_int64 getAbsoluteLevel(

561 Fts3Table p, / FTS3 table handle */

562 int iLangid, /* Language id */

563 int iIndex, /* Index in p->aIndex[] */

564 int iLevel /* Level of segments */

565 ){

566 sqlite3_int64 iBase; /* First absolute level for iLangid/iIndex */

567 assert( iLangid>=0 );

568 assert( p->nIndex>0 );

569 assert( iIndex>=0 && iIndex<p->nIndex );

570

571 iBase = ((sqlite3_int64)iLangid * p->nIndex + iIndex) * FTS3_SEGDIR_MAXLEVEL;

572 return iBase + iLevel;

573 }

574

575 /*

576 ** Set *ppStmt to a statement handle that may be used to iterate through

577 ** all rows in the %_segdir table, from oldest to newest. If successful,

578 ** return SQLITE_OK. If an error occurs while preparing the statement,

579 ** return an SQLite error code.

580 **

581 ** There is only ever one instance of this SQL statement compiled for

582 ** each FTS3 table.

583 **

584 ** The statement returns the following columns from the %_segdir table:

585 **

586 ** 0: idx

587 ** 1: start_block

588 ** 2: leaves_end_block

589 ** 3: end_block

590 ** 4: root

591 */

592 int sqlite3Fts3AllSegdirs(

593 Fts3Table p, / FTS3 table */

594 int iLangid, /* Language being queried */

595 int iIndex, /* Index for p->aIndex[] */

596 int iLevel, /* Level to select (relative level) */

597 sqlite3_stmt *ppStmt / OUT: Compiled statement */

598 ){

599 int rc;

600 sqlite3_stmt *pStmt = 0;

601

602 assert( iLevel==FTS3_SEGCURSOR_ALL \|\| iLevel>=0 );

603 assert( iLevel<FTS3_SEGDIR_MAXLEVEL );

604 assert( iIndex>=0 && iIndex<p->nIndex );

605

606 if( iLevel<0 ){

607 /* "SELECT * FROM %_segdir WHERE level BETWEEN ? AND ? ORDER BY ..." */

608 rc = fts3SqlStmt(p, SQL_SELECT_LEVEL_RANGE, &pStmt, 0);

609 if( rc==SQLITE_OK ){

610 sqlite3_bind_int64(pStmt, 1, getAbsoluteLevel(p, iLangid, iIndex, 0));

611 sqlite3_bind_int64(pStmt, 2,

612 getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1)

613 );

614 }

615 }else{

616 /* "SELECT * FROM %_segdir WHERE level = ? ORDER BY ..." */

617 rc = fts3SqlStmt(p, SQL_SELECT_LEVEL, &pStmt, 0);

618 if( rc==SQLITE_OK ){

619 sqlite3_bind_int64(pStmt, 1, getAbsoluteLevel(p, iLangid, iIndex,iLevel));

620 }

621 }

622 *ppStmt = pStmt;

623 return rc;

624 }

625

626

627 /*

628 ** Append a single varint to a PendingList buffer. SQLITE_OK is returned

629 ** if successful, or an SQLite error code otherwise.

630 **

631 ** This function also serves to allocate the PendingList structure itself.

632 ** For example, to create a new PendingList structure containing two

633 ** varints:

634 **

635 ** PendingList *p = 0;

636 ** fts3PendingListAppendVarint(&p, 1);

637 ** fts3PendingListAppendVarint(&p, 2);

638 */

639 static int fts3PendingListAppendVarint(

640 PendingList *pp, / IN/OUT: Pointer to PendingList struct */

641 sqlite3_int64 i /* Value to append to data */

642 ){

643 PendingList p = pp;

644

645 /* Allocate or grow the PendingList as required. */

646 if( !p ){

647 p = sqlite3_malloc(sizeof(*p) + 100);

648 if( !p ){

649 return SQLITE_NOMEM;

650 }

651 p->nSpace = 100;

652 p->aData = (char *)&p[1];

653 p->nData = 0;

654 }

655 else if( p->nData+FTS3_VARINT_MAX+1>p->nSpace ){

656 int nNew = p->nSpace * 2;

657 p = sqlite3_realloc(p, sizeof(*p) + nNew);

658 if( !p ){

659 sqlite3_free(*pp);

660 *pp = 0;

661 return SQLITE_NOMEM;

662 }

663 p->nSpace = nNew;

664 p->aData = (char *)&p[1];

665 }

666

667 /* Append the new serialized varint to the end of the list. */

668 p->nData += sqlite3Fts3PutVarint(&p->aData[p->nData], i);

669 p->aData[p->nData] = '\0';

670 *pp = p;

671 return SQLITE_OK;

672 }

673

674 /*

675 ** Add a docid/column/position entry to a PendingList structure. Non-zero

676 ** is returned if the structure is sqlite3_realloced as part of adding

677 ** the entry. Otherwise, zero.

678 **

679 ** If an OOM error occurs, *pRc is set to SQLITE_NOMEM before returning.

680 ** Zero is always returned in this case. Otherwise, if no OOM error occurs,

681 ** it is set to SQLITE_OK.

682 */

683 static int fts3PendingListAppend(

684 PendingList *pp, / IN/OUT: PendingList structure */

685 sqlite3_int64 iDocid, /* Docid for entry to add */

686 sqlite3_int64 iCol, /* Column for entry to add */

687 sqlite3_int64 iPos, /* Position of term for entry to add */

688 int pRc / OUT: Return code */

689 ){

690 PendingList p = pp;

691 int rc = SQLITE_OK;

692

693 assert( !p \|\| p->iLastDocid<=iDocid );

694

695 if( !p \|\| p->iLastDocid!=iDocid ){

696 sqlite3_int64 iDelta = iDocid - (p ? p->iLastDocid : 0);

697 if( p ){

698 assert( p->nData<p->nSpace );

699 assert( p->aData[p->nData]==0 );

700 p->nData++;

701 }

702 if( SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, iDelta)) ){

703 goto pendinglistappend_out;

704 }

705 p->iLastCol = -1;

706 p->iLastPos = 0;

707 p->iLastDocid = iDocid;

708 }

709 if( iCol>0 && p->iLastCol!=iCol ){

710 if( SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, 1))

711 \|\| SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, iCol))

712 ){

713 goto pendinglistappend_out;

714 }

715 p->iLastCol = iCol;

716 p->iLastPos = 0;

717 }

718 if( iCol>=0 ){

719 assert( iPos>p->iLastPos \|\| (iPos==0 && p->iLastPos==0) );

720 rc = fts3PendingListAppendVarint(&p, 2+iPos-p->iLastPos);

721 if( rc==SQLITE_OK ){

722 p->iLastPos = iPos;

723 }

724 }

725

726 pendinglistappend_out:

727 *pRc = rc;

728 if( p!=*pp ){

729 *pp = p;

730 return 1;

731 }

732 return 0;

733 }

734

735 /*

736 ** Free a PendingList object allocated by fts3PendingListAppend().

737 */

738 static void fts3PendingListDelete(PendingList *pList){

739 sqlite3_free(pList);

740 }

741

742 /*

743 ** Add an entry to one of the pending-terms hash tables.

744 */

745 static int fts3PendingTermsAddOne(

746 Fts3Table *p,

747 int iCol,

748 int iPos,

749 Fts3Hash pHash, / Pending terms hash table to add entry to */

750 const char *zToken,

751 int nToken

752 ){

753 PendingList *pList;

754 int rc = SQLITE_OK;

755

756 pList = (PendingList *)fts3HashFind(pHash, zToken, nToken);

757 if( pList ){

758 p->nPendingData -= (pList->nData + nToken + sizeof(Fts3HashElem));

759 }

760 if( fts3PendingListAppend(&pList, p->iPrevDocid, iCol, iPos, &rc) ){

761 if( pList==fts3HashInsert(pHash, zToken, nToken, pList) ){

762 /* Malloc failed while inserting the new entry. This can only

763 ** happen if there was no previous entry for this token.

764 */

765 assert( 0==fts3HashFind(pHash, zToken, nToken) );

766 sqlite3_free(pList);

767 rc = SQLITE_NOMEM;

768 }

769 }

770 if( rc==SQLITE_OK ){

771 p->nPendingData += (pList->nData + nToken + sizeof(Fts3HashElem));

772 }

773 return rc;

774 }

775

776 /*

777 ** Tokenize the nul-terminated string zText and add all tokens to the

778 ** pending-terms hash-table. The docid used is that currently stored in

779 ** p->iPrevDocid, and the column is specified by argument iCol.

780 **

781 ** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.

782 */

783 static int fts3PendingTermsAdd(

784 Fts3Table p, / Table into which text will be inserted */

785 int iLangid, /* Language id to use */

786 const char zText, / Text of document to be inserted */

787 int iCol, /* Column into which text is being inserted */

788 u32 pnWord / IN/OUT: Incr. by number tokens inserted */

789 ){

790 int rc;

791 int iStart = 0;

792 int iEnd = 0;

793 int iPos = 0;

794 int nWord = 0;

795

796 char const *zToken;

797 int nToken = 0;

798

799 sqlite3_tokenizer *pTokenizer = p->pTokenizer;

800 sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;

801 sqlite3_tokenizer_cursor *pCsr;

802 int (xNext)(sqlite3_tokenizer_cursor pCursor,

803 const char*,int,int,int,int*);

804

805 assert( pTokenizer && pModule );

806

807 /* If the user has inserted a NULL value, this function may be called with

808 ** zText==0. In this case, add zero token entries to the hash table and

809 ** return early. */

810 if( zText==0 ){

811 *pnWord = 0;

812 return SQLITE_OK;

813 }

814

815 rc = sqlite3Fts3OpenTokenizer(pTokenizer, iLangid, zText, -1, &pCsr);

816 if( rc!=SQLITE_OK ){

817 return rc;

818 }

819

820 xNext = pModule->xNext;

821 while( SQLITE_OK==rc

822 && SQLITE_OK==(rc = xNext(pCsr, &zToken, &nToken, &iStart, &iEnd, &iPos))

823 ){

824 int i;

825 if( iPos>=nWord ) nWord = iPos+1;

826

827 /* Positions cannot be negative; we use -1 as a terminator internally.

828 ** Tokens must have a non-zero length.

829 */

830 if( iPos<0 \|\| !zToken \|\| nToken<=0 ){

831 rc = SQLITE_ERROR;

832 break;

833 }

834

835 /* Add the term to the terms index */

836 rc = fts3PendingTermsAddOne(

837 p, iCol, iPos, &p->aIndex[0].hPending, zToken, nToken

838 );

839

840 /* Add the term to each of the prefix indexes that it is not too

841 ** short for. */

842 for(i=1; rc==SQLITE_OK && i<p->nIndex; i++){

843 struct Fts3Index *pIndex = &p->aIndex[i];

844 if( nToken<pIndex->nPrefix ) continue;

845 rc = fts3PendingTermsAddOne(

846 p, iCol, iPos, &pIndex->hPending, zToken, pIndex->nPrefix

847 );

848 }

849 }

850

851 pModule->xClose(pCsr);

852 *pnWord += nWord;

853 return (rc==SQLITE_DONE ? SQLITE_OK : rc);

854 }

855

856 /*

857 ** Calling this function indicates that subsequent calls to

858 ** fts3PendingTermsAdd() are to add term/position-list pairs for the

859 ** contents of the document with docid iDocid.

860 */

861 static int fts3PendingTermsDocid(

862 Fts3Table p, / Full-text table handle */

863 int iLangid, /* Language id of row being written */

864 sqlite_int64 iDocid /* Docid of row being written */

865 ){

866 assert( iLangid>=0 );

867

868 /* TODO(shess) Explore whether partially flushing the buffer on

869 ** forced-flush would provide better performance. I suspect that if

870 ** we ordered the doclists by size and flushed the largest until the

871 ** buffer was half empty, that would let the less frequent terms

872 ** generate longer doclists.

873 */

874 if( iDocid<=p->iPrevDocid

875 \|\| p->iPrevLangid!=iLangid

876 \|\| p->nPendingData>p->nMaxPendingData

877 ){

878 int rc = sqlite3Fts3PendingTermsFlush(p);

879 if( rc!=SQLITE_OK ) return rc;

880 }

881 p->iPrevDocid = iDocid;

882 p->iPrevLangid = iLangid;

883 return SQLITE_OK;

884 }

885

886 /*

887 ** Discard the contents of the pending-terms hash tables.

888 */

889 void sqlite3Fts3PendingTermsClear(Fts3Table *p){

890 int i;

891 for(i=0; i<p->nIndex; i++){

892 Fts3HashElem *pElem;

893 Fts3Hash *pHash = &p->aIndex[i].hPending;

894 for(pElem=fts3HashFirst(pHash); pElem; pElem=fts3HashNext(pElem)){

895 PendingList pList = (PendingList )fts3HashData(pElem);

896 fts3PendingListDelete(pList);

897 }

898 fts3HashClear(pHash);

899 }

900 p->nPendingData = 0;

901 }

902

903 /*

904 ** This function is called by the xUpdate() method as part of an INSERT

905 ** operation. It adds entries for each term in the new record to the

906 ** pendingTerms hash table.

907 **

908 ** Argument apVal is the same as the similarly named argument passed to

909 ** fts3InsertData(). Parameter iDocid is the docid of the new row.

910 */

911 static int fts3InsertTerms(

912 Fts3Table *p,

913 int iLangid,

914 sqlite3_value **apVal,

915 u32 *aSz

916 ){

917 int i; /* Iterator variable */

918 for(i=2; i<p->nColumn+2; i++){

919 int iCol = i-2;

920 if( p->abNotindexed[iCol]==0 ){

921 const char zText = (const char )sqlite3_value_text(apVal[i]);

922 int rc = fts3PendingTermsAdd(p, iLangid, zText, iCol, &aSz[iCol]);

923 if( rc!=SQLITE_OK ){

924 return rc;

925 }

926 aSz[p->nColumn] += sqlite3_value_bytes(apVal[i]);

927 }

928 }

929 return SQLITE_OK;

930 }

931

932 /*

933 ** This function is called by the xUpdate() method for an INSERT operation.

934 ** The apVal parameter is passed a copy of the apVal argument passed by

935 ** SQLite to the xUpdate() method. i.e:

936 **

937 ** apVal[0] Not used for INSERT.

938 ** apVal[1] rowid

939 ** apVal[2] Left-most user-defined column

940 ** ...

941 ** apVal[p->nColumn+1] Right-most user-defined column

942 ** apVal[p->nColumn+2] Hidden column with same name as table

943 ** apVal[p->nColumn+3] Hidden "docid" column (alias for rowid)

944 ** apVal[p->nColumn+4] Hidden languageid column

945 */

946 static int fts3InsertData(

947 Fts3Table p, / Full-text table */

948 sqlite3_value *apVal, / Array of values to insert */

949 sqlite3_int64 piDocid / OUT: Docid for row just inserted */

950 ){

951 int rc; /* Return code */

952 sqlite3_stmt pContentInsert; / INSERT INTO %_content VALUES(...) */

953

954 if( p->zContentTbl ){

955 sqlite3_value *pRowid = apVal[p->nColumn+3];

956 if( sqlite3_value_type(pRowid)==SQLITE_NULL ){

957 pRowid = apVal[1];

958 }

959 if( sqlite3_value_type(pRowid)!=SQLITE_INTEGER ){

960 return SQLITE_CONSTRAINT;

961 }

962 *piDocid = sqlite3_value_int64(pRowid);

963 return SQLITE_OK;

964 }

965

966 /* Locate the statement handle used to insert data into the %_content

967 ** table. The SQL for this statement is:

968 **

969 ** INSERT INTO %_content VALUES(?, ?, ?, ...)

970 **

971 ** The statement features N '?' variables, where N is the number of user

972 ** defined columns in the FTS3 table, plus one for the docid field.

973 */

974 rc = fts3SqlStmt(p, SQL_CONTENT_INSERT, &pContentInsert, &apVal[1]);

975 if( rc==SQLITE_OK && p->zLanguageid ){

976 rc = sqlite3_bind_int(

977 pContentInsert, p->nColumn+2,

978 sqlite3_value_int(apVal[p->nColumn+4])

979 );

980 }

981 if( rc!=SQLITE_OK ) return rc;

982

983 /* There is a quirk here. The users INSERT statement may have specified

984 ** a value for the "rowid" field, for the "docid" field, or for both.

985 ** Which is a problem, since "rowid" and "docid" are aliases for the

986 ** same value. For example:

987 **

988 ** INSERT INTO fts3tbl(rowid, docid) VALUES(1, 2);

989 **

990 ** In FTS3, this is an error. It is an error to specify non-NULL values

991 ** for both docid and some other rowid alias.

992 */

993 if( SQLITE_NULL!=sqlite3_value_type(apVal[3+p->nColumn]) ){

994 if( SQLITE_NULL==sqlite3_value_type(apVal[0])

995 && SQLITE_NULL!=sqlite3_value_type(apVal[1])

996 ){

997 /* A rowid/docid conflict. */

998 return SQLITE_ERROR;

999 }

1000 rc = sqlite3_bind_value(pContentInsert, 1, apVal[3+p->nColumn]);

1001 if( rc!=SQLITE_OK ) return rc;

1002 }

1003

1004 /* Execute the statement to insert the record. Set *piDocid to the

1005 ** new docid value.

1006 */

1007 sqlite3_step(pContentInsert);

1008 rc = sqlite3_reset(pContentInsert);

1009

1010 *piDocid = sqlite3_last_insert_rowid(p->db);

1011 return rc;

1012 }

1013

1014

1015

1016 /*

1017 ** Remove all data from the FTS3 table. Clear the hash table containing

1018 ** pending terms.

1019 */

1020 static int fts3DeleteAll(Fts3Table *p, int bContent){

1021 int rc = SQLITE_OK; /* Return code */

1022

1023 /* Discard the contents of the pending-terms hash table. */

1024 sqlite3Fts3PendingTermsClear(p);

1025

1026 /* Delete everything from the shadow tables. Except, leave %_content as

1027 ** is if bContent is false. */

1028 assert( p->zContentTbl==0 \|\| bContent==0 );

1029 if( bContent ) fts3SqlExec(&rc, p, SQL_DELETE_ALL_CONTENT, 0);

1030 fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGMENTS, 0);

1031 fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGDIR, 0);

1032 if( p->bHasDocsize ){

1033 fts3SqlExec(&rc, p, SQL_DELETE_ALL_DOCSIZE, 0);

1034 }

1035 if( p->bHasStat ){

1036 fts3SqlExec(&rc, p, SQL_DELETE_ALL_STAT, 0);

1037 }

1038 return rc;

1039 }

1040

1041 /*

1042 **

1043 */

1044 static int langidFromSelect(Fts3Table p, sqlite3_stmt pSelect){

1045 int iLangid = 0;

1046 if( p->zLanguageid ) iLangid = sqlite3_column_int(pSelect, p->nColumn+1);

1047 return iLangid;

1048 }

1049

1050 /*

1051 ** The first element in the apVal[] array is assumed to contain the docid

1052 ** (an integer) of a row about to be deleted. Remove all terms from the

1053 ** full-text index.

1054 */

1055 static void fts3DeleteTerms(

1056 int pRC, / Result code */

1057 Fts3Table p, / The FTS table to delete from */

1058 sqlite3_value pRowid, / The docid to be deleted */

1059 u32 aSz, / Sizes of deleted document written here */

1060 int pbFound / OUT: Set to true if row really does exist */

1061 ){

1062 int rc;

1063 sqlite3_stmt *pSelect;

1064

1065 assert( *pbFound==0 );

1066 if( *pRC ) return;

1067 rc = fts3SqlStmt(p, SQL_SELECT_CONTENT_BY_ROWID, &pSelect, &pRowid);

1068 if( rc==SQLITE_OK ){

1069 if( SQLITE_ROW==sqlite3_step(pSelect) ){

1070 int i;

1071 int iLangid = langidFromSelect(p, pSelect);

1072 rc = fts3PendingTermsDocid(p, iLangid, sqlite3_column_int64(pSelect, 0));

1073 for(i=1; rc==SQLITE_OK && i<=p->nColumn; i++){

1074 int iCol = i-1;

1075 if( p->abNotindexed[iCol]==0 ){

1076 const char zText = (const char )sqlite3_column_text(pSelect, i);

1077 rc = fts3PendingTermsAdd(p, iLangid, zText, -1, &aSz[iCol]);

1078 aSz[p->nColumn] += sqlite3_column_bytes(pSelect, i);

1079 }

1080 }

1081 if( rc!=SQLITE_OK ){

1082 sqlite3_reset(pSelect);

1083 *pRC = rc;

1084 return;

1085 }

1086 *pbFound = 1;

1087 }

1088 rc = sqlite3_reset(pSelect);

1089 }else{

1090 sqlite3_reset(pSelect);

1091 }

1092 *pRC = rc;

1093 }

1094

1095 /*

1096 ** Forward declaration to account for the circular dependency between

1097 ** functions fts3SegmentMerge() and fts3AllocateSegdirIdx().

1098 */

1099 static int fts3SegmentMerge(Fts3Table *, int, int, int);

1100

1101 /*

1102 ** This function allocates a new level iLevel index in the segdir table.

1103 ** Usually, indexes are allocated within a level sequentially starting

1104 ** with 0, so the allocated index is one greater than the value returned

1105 ** by:

1106 **

1107 ** SELECT max(idx) FROM %_segdir WHERE level = :iLevel

1108 **

1109 ** However, if there are already FTS3_MERGE_COUNT indexes at the requested

1110 ** level, they are merged into a single level (iLevel+1) segment and the

1111 ** allocated index is 0.

1112 **

1113 ** If successful, *piIdx is set to the allocated index slot and SQLITE_OK

1114 ** returned. Otherwise, an SQLite error code is returned.

1115 */

1116 static int fts3AllocateSegdirIdx(

1117 Fts3Table *p,

1118 int iLangid, /* Language id */

1119 int iIndex, /* Index for p->aIndex */

1120 int iLevel,

1121 int *piIdx

1122 ){

1123 int rc; /* Return Code */

1124 sqlite3_stmt pNextIdx; / Query for next idx at level iLevel */

1125 int iNext = 0; /* Result of query pNextIdx */

1126

1127 assert( iLangid>=0 );

1128 assert( p->nIndex>=1 );

1129

1130 /* Set variable iNext to the next available segdir index at level iLevel. */

1131 rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pNextIdx, 0);

1132 if( rc==SQLITE_OK ){

1133 sqlite3_bind_int64(

1134 pNextIdx, 1, getAbsoluteLevel(p, iLangid, iIndex, iLevel)

1135 );

1136 if( SQLITE_ROW==sqlite3_step(pNextIdx) ){

1137 iNext = sqlite3_column_int(pNextIdx, 0);

1138 }

1139 rc = sqlite3_reset(pNextIdx);

1140 }

1141

1142 if( rc==SQLITE_OK ){

1143 /* If iNext is FTS3_MERGE_COUNT, indicating that level iLevel is already

1144 ** full, merge all segments in level iLevel into a single iLevel+1

1145 ** segment and allocate (newly freed) index 0 at level iLevel. Otherwise,

1146 ** if iNext is less than FTS3_MERGE_COUNT, allocate index iNext.

1147 */

1148 if( iNext>=FTS3_MERGE_COUNT ){

1149 fts3LogMerge(16, getAbsoluteLevel(p, iLangid, iIndex, iLevel));

1150 rc = fts3SegmentMerge(p, iLangid, iIndex, iLevel);

1151 *piIdx = 0;

1152 }else{

1153 *piIdx = iNext;

1154 }

1155 }

1156

1157 return rc;

1158 }

1159

1160 /*

1161 ** The %_segments table is declared as follows:

1162 **

1163 ** CREATE TABLE %_segments(blockid INTEGER PRIMARY KEY, block BLOB)

1164 **

1165 ** This function reads data from a single row of the %_segments table. The

1166 ** specific row is identified by the iBlockid parameter. If paBlob is not

1167 ** NULL, then a buffer is allocated using sqlite3_malloc() and populated

1168 ** with the contents of the blob stored in the "block" column of the

1169 ** identified table row is. Whether or not paBlob is NULL, *pnBlob is set

1170 ** to the size of the blob in bytes before returning.

1171 **

1172 ** If an error occurs, or the table does not contain the specified row,

1173 ** an SQLite error code is returned. Otherwise, SQLITE_OK is returned. If

1174 ** paBlob is non-NULL, then it is the responsibility of the caller to

1175 ** eventually free the returned buffer.

1176 **

1177 ** This function may leave an open sqlite3_blob* handle in the

1178 ** Fts3Table.pSegments variable. This handle is reused by subsequent calls

1179 ** to this function. The handle may be closed by calling the

1180 ** sqlite3Fts3SegmentsClose() function. Reusing a blob handle is a handy

1181 ** performance improvement, but the blob handle should always be closed

1182 ** before control is returned to the user (to prevent a lock being held

1183 ** on the database file for longer than necessary). Thus, any virtual table

1184 ** method (xFilter etc.) that may directly or indirectly call this function

1185 ** must call sqlite3Fts3SegmentsClose() before returning.

1186 */

1187 int sqlite3Fts3ReadBlock(

1188 Fts3Table p, / FTS3 table handle */

1189 sqlite3_int64 iBlockid, /* Access the row with blockid=$iBlockid */

1190 char *paBlob, / OUT: Blob data in malloc'd buffer */

1191 int pnBlob, / OUT: Size of blob data */

1192 int pnLoad / OUT: Bytes actually loaded */

1193 ){

1194 int rc; /* Return code */

1195

1196 /* pnBlob must be non-NULL. paBlob may be NULL or non-NULL. */

1197 assert( pnBlob );

1198

1199 if( p->pSegments ){

1200 rc = sqlite3_blob_reopen(p->pSegments, iBlockid);

1201 }else{

1202 if( 0==p->zSegmentsTbl ){

1203 p->zSegmentsTbl = sqlite3_mprintf("%s_segments", p->zName);

1204 if( 0==p->zSegmentsTbl ) return SQLITE_NOMEM;

1205 }

1206 rc = sqlite3_blob_open(

1207 p->db, p->zDb, p->zSegmentsTbl, "block", iBlockid, 0, &p->pSegments

1208 );

1209 }

1210

1211 if( rc==SQLITE_OK ){

1212 int nByte = sqlite3_blob_bytes(p->pSegments);

1213 *pnBlob = nByte;

1214 if( paBlob ){

1215 char *aByte = sqlite3_malloc(nByte + FTS3_NODE_PADDING);

1216 if( !aByte ){

1217 rc = SQLITE_NOMEM;

1218 }else{

1219 if( pnLoad && nByte>(FTS3_NODE_CHUNK_THRESHOLD) ){

1220 nByte = FTS3_NODE_CHUNKSIZE;

1221 *pnLoad = nByte;

1222 }

1223 rc = sqlite3_blob_read(p->pSegments, aByte, nByte, 0);

1224 memset(&aByte[nByte], 0, FTS3_NODE_PADDING);

1225 if( rc!=SQLITE_OK ){

1226 sqlite3_free(aByte);

1227 aByte = 0;

1228 }

1229 }

1230 *paBlob = aByte;

1231 }

1232 }

1233

1234 return rc;

1235 }

1236

1237 /*

1238 ** Close the blob handle at p->pSegments, if it is open. See comments above

1239 ** the sqlite3Fts3ReadBlock() function for details.

1240 */

1241 void sqlite3Fts3SegmentsClose(Fts3Table *p){

1242 sqlite3_blob_close(p->pSegments);

1243 p->pSegments = 0;

1244 }

1245

1246 static int fts3SegReaderIncrRead(Fts3SegReader *pReader){

1247 int nRead; /* Number of bytes to read */

1248 int rc; /* Return code */

1249

1250 nRead = MIN(pReader->nNode - pReader->nPopulate, FTS3_NODE_CHUNKSIZE);

1251 rc = sqlite3_blob_read(

1252 pReader->pBlob,

1253 &pReader->aNode[pReader->nPopulate],

1254 nRead,

1255 pReader->nPopulate

1256 );

1257

1258 if( rc==SQLITE_OK ){

1259 pReader->nPopulate += nRead;

1260 memset(&pReader->aNode[pReader->nPopulate], 0, FTS3_NODE_PADDING);

1261 if( pReader->nPopulate==pReader->nNode ){

1262 sqlite3_blob_close(pReader->pBlob);

1263 pReader->pBlob = 0;

1264 pReader->nPopulate = 0;

1265 }

1266 }

1267 return rc;

1268 }

1269

1270 static int fts3SegReaderRequire(Fts3SegReader pReader, char pFrom, int nByte){

1271 int rc = SQLITE_OK;

1272 assert( !pReader->pBlob

1273 \|\| (pFrom>=pReader->aNode && pFrom<&pReader->aNode[pReader->nNode])

1274 );

1275 while( pReader->pBlob && rc==SQLITE_OK

1276 && (pFrom - pReader->aNode + nByte)>pReader->nPopulate

1277 ){

1278 rc = fts3SegReaderIncrRead(pReader);

1279 }

1280 return rc;

1281 }

1282

1283 /*

1284 ** Set an Fts3SegReader cursor to point at EOF.

1285 */

1286 static void fts3SegReaderSetEof(Fts3SegReader *pSeg){

1287 if( !fts3SegReaderIsRootOnly(pSeg) ){

1288 sqlite3_free(pSeg->aNode);

1289 sqlite3_blob_close(pSeg->pBlob);

1290 pSeg->pBlob = 0;

1291 }

1292 pSeg->aNode = 0;

1293 }

1294

1295 /*

1296 ** Move the iterator passed as the first argument to the next term in the

1297 ** segment. If successful, SQLITE_OK is returned. If there is no next term,

1298 ** SQLITE_DONE. Otherwise, an SQLite error code.

1299 */

1300 static int fts3SegReaderNext(

1301 Fts3Table *p,

1302 Fts3SegReader *pReader,

1303 int bIncr

1304 ){

1305 int rc; /* Return code of various sub-routines */

1306 char pNext; / Cursor variable */

1307 int nPrefix; /* Number of bytes in term prefix */

1308 int nSuffix; /* Number of bytes in term suffix */

1309

1310 if( !pReader->aDoclist ){

1311 pNext = pReader->aNode;

1312 }else{

1313 pNext = &pReader->aDoclist[pReader->nDoclist];

1314 }

1315

1316 if( !pNext \|\| pNext>=&pReader->aNode[pReader->nNode] ){

1317

1318 if( fts3SegReaderIsPending(pReader) ){

1319 Fts3HashElem pElem = (pReader->ppNextElem);

1320 if( pElem==0 ){

1321 pReader->aNode = 0;

1322 }else{

1323 PendingList pList = (PendingList )fts3HashData(pElem);

1324 pReader->zTerm = (char *)fts3HashKey(pElem);

1325 pReader->nTerm = fts3HashKeysize(pElem);

1326 pReader->nNode = pReader->nDoclist = pList->nData + 1;

1327 pReader->aNode = pReader->aDoclist = pList->aData;

1328 pReader->ppNextElem++;

1329 assert( pReader->aNode );

1330 }

1331 return SQLITE_OK;

1332 }

1333

1334 fts3SegReaderSetEof(pReader);

1335

1336 /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf

1337 ** blocks have already been traversed. */

1338 assert( pReader->iCurrentBlock<=pReader->iLeafEndBlock );

1339 if( pReader->iCurrentBlock>=pReader->iLeafEndBlock ){

1340 return SQLITE_OK;

1341 }

1342

1343 rc = sqlite3Fts3ReadBlock(

1344 p, ++pReader->iCurrentBlock, &pReader->aNode, &pReader->nNode,

1345 (bIncr ? &pReader->nPopulate : 0)

1346 );

1347 if( rc!=SQLITE_OK ) return rc;

1348 assert( pReader->pBlob==0 );

1349 if( bIncr && pReader->nPopulate<pReader->nNode ){

1350 pReader->pBlob = p->pSegments;

1351 p->pSegments = 0;

1352 }

1353 pNext = pReader->aNode;

1354 }

1355

1356 assert( !fts3SegReaderIsPending(pReader) );

1357

1358 rc = fts3SegReaderRequire(pReader, pNext, FTS3_VARINT_MAX*2);

1359 if( rc!=SQLITE_OK ) return rc;

1360

1361 /* Because of the FTS3_NODE_PADDING bytes of padding, the following is

1362 ** safe (no risk of overread) even if the node data is corrupted. */

1363 pNext += fts3GetVarint32(pNext, &nPrefix);

1364 pNext += fts3GetVarint32(pNext, &nSuffix);

1365 if( nPrefix<0 \|\| nSuffix<=0

1366 \|\| &pNext[nSuffix]>&pReader->aNode[pReader->nNode]

1367 ){

1368 return FTS_CORRUPT_VTAB;

1369 }

1370

1371 if( nPrefix+nSuffix>pReader->nTermAlloc ){

1372 int nNew = (nPrefix+nSuffix)*2;

1373 char *zNew = sqlite3_realloc(pReader->zTerm, nNew);

1374 if( !zNew ){

1375 return SQLITE_NOMEM;

1376 }

1377 pReader->zTerm = zNew;

1378 pReader->nTermAlloc = nNew;

1379 }

1380

1381 rc = fts3SegReaderRequire(pReader, pNext, nSuffix+FTS3_VARINT_MAX);

1382 if( rc!=SQLITE_OK ) return rc;

1383

1384 memcpy(&pReader->zTerm[nPrefix], pNext, nSuffix);

1385 pReader->nTerm = nPrefix+nSuffix;

1386 pNext += nSuffix;

1387 pNext += fts3GetVarint32(pNext, &pReader->nDoclist);

1388 pReader->aDoclist = pNext;

1389 pReader->pOffsetList = 0;

1390

1391 /* Check that the doclist does not appear to extend past the end of the

1392 ** b-tree node. And that the final byte of the doclist is 0x00. If either

1393 ** of these statements is untrue, then the data structure is corrupt.

1394 */

1395 if( &pReader->aDoclist[pReader->nDoclist]>&pReader->aNode[pReader->nNode]

1396 \|\| (pReader->nPopulate==0 && pReader->aDoclist[pReader->nDoclist-1])

1397 ){

1398 return FTS_CORRUPT_VTAB;

1399 }

1400 return SQLITE_OK;

1401 }

1402

1403 /*

1404 ** Set the SegReader to point to the first docid in the doclist associated

1405 ** with the current term.

1406 */

1407 static int fts3SegReaderFirstDocid(Fts3Table pTab, Fts3SegReader pReader){

1408 int rc = SQLITE_OK;

1409 assert( pReader->aDoclist );

1410 assert( !pReader->pOffsetList );

1411 if( pTab->bDescIdx && fts3SegReaderIsPending(pReader) ){

1412 u8 bEof = 0;

1413 pReader->iDocid = 0;

1414 pReader->nOffsetList = 0;

1415 sqlite3Fts3DoclistPrev(0,

1416 pReader->aDoclist, pReader->nDoclist, &pReader->pOffsetList,

1417 &pReader->iDocid, &pReader->nOffsetList, &bEof

1418 );

1419 }else{

1420 rc = fts3SegReaderRequire(pReader, pReader->aDoclist, FTS3_VARINT_MAX);

1421 if( rc==SQLITE_OK ){

1422 int n = sqlite3Fts3GetVarint(pReader->aDoclist, &pReader->iDocid);

1423 pReader->pOffsetList = &pReader->aDoclist[n];

1424 }

1425 }

1426 return rc;

1427 }

1428

1429 /*

1430 ** Advance the SegReader to point to the next docid in the doclist

1431 ** associated with the current term.

1432 **

1433 ** If arguments ppOffsetList and pnOffsetList are not NULL, then

1434 ** *ppOffsetList is set to point to the first column-offset list

1435 ** in the doclist entry (i.e. immediately past the docid varint).

1436 ** *pnOffsetList is set to the length of the set of column-offset

1437 ** lists, not including the nul-terminator byte. For example:

1438 */

1439 static int fts3SegReaderNextDocid(

1440 Fts3Table *pTab,

1441 Fts3SegReader pReader, / Reader to advance to next docid */

1442 char *ppOffsetList, / OUT: Pointer to current position-list */

1443 int pnOffsetList / OUT: Length of ppOffsetList in bytes /

1444 ){

1445 int rc = SQLITE_OK;

1446 char *p = pReader->pOffsetList;

1447 char c = 0;

1448

1449 assert( p );

1450

1451 if( pTab->bDescIdx && fts3SegReaderIsPending(pReader) ){

1452 /* A pending-terms seg-reader for an FTS4 table that uses order=desc.

1453 ** Pending-terms doclists are always built up in ascending order, so

1454 ** we have to iterate through them backwards here. */

1455 u8 bEof = 0;

1456 if( ppOffsetList ){

1457 *ppOffsetList = pReader->pOffsetList;

1458 *pnOffsetList = pReader->nOffsetList - 1;

1459 }

1460 sqlite3Fts3DoclistPrev(0,

1461 pReader->aDoclist, pReader->nDoclist, &p, &pReader->iDocid,

1462 &pReader->nOffsetList, &bEof

1463 );

1464 if( bEof ){

1465 pReader->pOffsetList = 0;

1466 }else{

1467 pReader->pOffsetList = p;

1468 }

1469 }else{

1470 char *pEnd = &pReader->aDoclist[pReader->nDoclist];

1471

1472 /* Pointer p currently points at the first byte of an offset list. The

1473 ** following block advances it to point one byte past the end of

1474 ** the same offset list. */

1475 while( 1 ){

1476

1477 /* The following line of code (and the "p++" below the while() loop) is

1478 ** normally all that is required to move pointer p to the desired

1479 ** position. The exception is if this node is being loaded from disk

1480 ** incrementally and pointer "p" now points to the first byte past

1481 ** the populated part of pReader->aNode[].

1482 */

1483 while( p \| c ) c = p++ & 0x80;

1484 assert( *p==0 );

1485

1486 if( pReader->pBlob==0 \|\| p<&pReader->aNode[pReader->nPopulate] ) break;

1487 rc = fts3SegReaderIncrRead(pReader);

1488 if( rc!=SQLITE_OK ) return rc;

1489 }

1490 p++;

1491

1492 /* If required, populate the output variables with a pointer to and the

1493 ** size of the previous offset-list.

1494 */

1495 if( ppOffsetList ){

1496 *ppOffsetList = pReader->pOffsetList;

1497 *pnOffsetList = (int)(p - pReader->pOffsetList - 1);

1498 }

1499

1500 /* List may have been edited in place by fts3EvalNearTrim() */

1501 while( p<pEnd && *p==0 ) p++;

1502

1503 /* If there are no more entries in the doclist, set pOffsetList to

1504 ** NULL. Otherwise, set Fts3SegReader.iDocid to the next docid and

1505 ** Fts3SegReader.pOffsetList to point to the next offset list before

1506 ** returning.

1507 */

1508 if( p>=pEnd ){

1509 pReader->pOffsetList = 0;

1510 }else{

1511 rc = fts3SegReaderRequire(pReader, p, FTS3_VARINT_MAX);

1512 if( rc==SQLITE_OK ){

1513 sqlite3_int64 iDelta;

1514 pReader->pOffsetList = p + sqlite3Fts3GetVarint(p, &iDelta);

1515 if( pTab->bDescIdx ){

1516 pReader->iDocid -= iDelta;

1517 }else{

1518 pReader->iDocid += iDelta;

1519 }

1520 }

1521 }

1522 }

1523

1524 return SQLITE_OK;

1525 }

1526

1527

1528 int sqlite3Fts3MsrOvfl(

1529 Fts3Cursor *pCsr,

1530 Fts3MultiSegReader *pMsr,

1531 int *pnOvfl

1532 ){

1533 Fts3Table p = (Fts3Table)pCsr->base.pVtab;

1534 int nOvfl = 0;

1535 int ii;

1536 int rc = SQLITE_OK;

1537 int pgsz = p->nPgsz;

1538

1539 assert( p->bFts4 );

1540 assert( pgsz>0 );

1541

1542 for(ii=0; rc==SQLITE_OK && ii<pMsr->nSegment; ii++){

1543 Fts3SegReader *pReader = pMsr->apSegment[ii];

1544 if( !fts3SegReaderIsPending(pReader)

1545 && !fts3SegReaderIsRootOnly(pReader)

1546 ){

1547 sqlite3_int64 jj;

1548 for(jj=pReader->iStartBlock; jj<=pReader->iLeafEndBlock; jj++){

1549 int nBlob;

1550 rc = sqlite3Fts3ReadBlock(p, jj, 0, &nBlob, 0);

1551 if( rc!=SQLITE_OK ) break;

1552 if( (nBlob+35)>pgsz ){

1553 nOvfl += (nBlob + 34)/pgsz;

1554 }

1555 }

1556 }

1557 }

1558 *pnOvfl = nOvfl;

1559 return rc;

1560 }

1561

1562 /*

1563 ** Free all allocations associated with the iterator passed as the

1564 ** second argument.

1565 */

1566 void sqlite3Fts3SegReaderFree(Fts3SegReader *pReader){

1567 if( pReader && !fts3SegReaderIsPending(pReader) ){

1568 sqlite3_free(pReader->zTerm);

1569 if( !fts3SegReaderIsRootOnly(pReader) ){

1570 sqlite3_free(pReader->aNode);

1571 sqlite3_blob_close(pReader->pBlob);

1572 }

1573 }

1574 sqlite3_free(pReader);

1575 }

1576

1577 /*

1578 ** Allocate a new SegReader object.

1579 */

1580 int sqlite3Fts3SegReaderNew(

1581 int iAge, /* Segment "age". */

1582 int bLookup, /* True for a lookup only */

1583 sqlite3_int64 iStartLeaf, /* First leaf to traverse */

1584 sqlite3_int64 iEndLeaf, /* Final leaf to traverse */

1585 sqlite3_int64 iEndBlock, /* Final block of segment */

1586 const char zRoot, / Buffer containing root node */

1587 int nRoot, /* Size of buffer containing root node */

1588 Fts3SegReader *ppReader / OUT: Allocated Fts3SegReader */

1589 ){

1590 Fts3SegReader pReader; / Newly allocated SegReader object */

1591 int nExtra = 0; /* Bytes to allocate segment root node */

1592

1593 assert( iStartLeaf<=iEndLeaf );

1594 if( iStartLeaf==0 ){

1595 nExtra = nRoot + FTS3_NODE_PADDING;

1596 }

1597

1598 pReader = (Fts3SegReader *)sqlite3_malloc(sizeof(Fts3SegReader) + nExtra);

1599 if( !pReader ){

1600 return SQLITE_NOMEM;

1601 }

1602 memset(pReader, 0, sizeof(Fts3SegReader));

1603 pReader->iIdx = iAge;

1604 pReader->bLookup = bLookup!=0;

1605 pReader->iStartBlock = iStartLeaf;

1606 pReader->iLeafEndBlock = iEndLeaf;

1607 pReader->iEndBlock = iEndBlock;

1608

1609 if( nExtra ){

1610 /* The entire segment is stored in the root node. */

1611 pReader->aNode = (char *)&pReader[1];

1612 pReader->rootOnly = 1;

1613 pReader->nNode = nRoot;

1614 memcpy(pReader->aNode, zRoot, nRoot);

1615 memset(&pReader->aNode[nRoot], 0, FTS3_NODE_PADDING);

1616 }else{

1617 pReader->iCurrentBlock = iStartLeaf-1;

1618 }

1619 *ppReader = pReader;

1620 return SQLITE_OK;

1621 }

1622

1623 /*

1624 ** This is a comparison function used as a qsort() callback when sorting

1625 ** an array of pending terms by term. This occurs as part of flushing

1626 ** the contents of the pending-terms hash table to the database.

1627 */

1628 static int fts3CompareElemByTerm(const void lhs, const void rhs){

1629 char z1 = fts3HashKey((Fts3HashElem **)lhs);

1630 char z2 = fts3HashKey((Fts3HashElem **)rhs);

1631 int n1 = fts3HashKeysize((Fts3HashElem *)lhs);

1632 int n2 = fts3HashKeysize((Fts3HashElem *)rhs);

1633

1634 int n = (n1<n2 ? n1 : n2);

1635 int c = memcmp(z1, z2, n);

1636 if( c==0 ){

1637 c = n1 - n2;

1638 }

1639 return c;

1640 }

1641

1642 /*

1643 ** This function is used to allocate an Fts3SegReader that iterates through

1644 ** a subset of the terms stored in the Fts3Table.pendingTerms array.

1645 **

1646 ** If the isPrefixIter parameter is zero, then the returned SegReader iterates

1647 ** through each term in the pending-terms table. Or, if isPrefixIter is

1648 ** non-zero, it iterates through each term and its prefixes. For example, if

1649 ** the pending terms hash table contains the terms "sqlite", "mysql" and

1650 ** "firebird", then the iterator visits the following 'terms' (in the order

1651 ** shown):

1652 **

1653 ** f fi fir fire fireb firebi firebir firebird

1654 ** m my mys mysq mysql

1655 ** s sq sql sqli sqlit sqlite

1656 **

1657 ** Whereas if isPrefixIter is zero, the terms visited are:

1658 **

1659 ** firebird mysql sqlite

1660 */

1661 int sqlite3Fts3SegReaderPending(

1662 Fts3Table p, / Virtual table handle */

1663 int iIndex, /* Index for p->aIndex */

1664 const char zTerm, / Term to search for */

1665 int nTerm, /* Size of buffer zTerm */

1666 int bPrefix, /* True for a prefix iterator */

1667 Fts3SegReader *ppReader / OUT: SegReader for pending-terms */

1668 ){

1669 Fts3SegReader pReader = 0; / Fts3SegReader object to return */

1670 Fts3HashElem pE; / Iterator variable */

1671 Fts3HashElem *aElem = 0; / Array of term hash entries to scan */

1672 int nElem = 0; /* Size of array at aElem */

1673 int rc = SQLITE_OK; /* Return Code */

1674 Fts3Hash *pHash;

1675

1676 pHash = &p->aIndex[iIndex].hPending;

1677 if( bPrefix ){

1678 int nAlloc = 0; /* Size of allocated array at aElem */

1679

1680 for(pE=fts3HashFirst(pHash); pE; pE=fts3HashNext(pE)){

1681 char zKey = (char )fts3HashKey(pE);

1682 int nKey = fts3HashKeysize(pE);

1683 if( nTerm==0 \|\| (nKey>=nTerm && 0==memcmp(zKey, zTerm, nTerm)) ){

1684 if( nElem==nAlloc ){

1685 Fts3HashElem **aElem2;

1686 nAlloc += 16;

1687 aElem2 = (Fts3HashElem **)sqlite3_realloc(

1688 aElem, nAllocsizeof(Fts3HashElem )

1689 );

1690 if( !aElem2 ){

1691 rc = SQLITE_NOMEM;

1692 nElem = 0;

1693 break;

1694 }

1695 aElem = aElem2;

1696 }

1697

1698 aElem[nElem++] = pE;

1699 }

1700 }

1701

1702 /* If more than one term matches the prefix, sort the Fts3HashElem

1703 ** objects in term order using qsort(). This uses the same comparison

1704 ** callback as is used when flushing terms to disk.

1705 */

1706 if( nElem>1 ){

1707 qsort(aElem, nElem, sizeof(Fts3HashElem *), fts3CompareElemByTerm);

1708 }

1709

1710 }else{

1711 /* The query is a simple term lookup that matches at most one term in

1712 ** the index. All that is required is a straight hash-lookup.

1713 **

1714 ** Because the stack address of pE may be accessed via the aElem pointer

1715 ** below, the "Fts3HashElem *pE" must be declared so that it is valid

1716 ** within this entire function, not just this "else{...}" block.

1717 */

1718 pE = fts3HashFindElem(pHash, zTerm, nTerm);

1719 if( pE ){

1720 aElem = &pE;

1721 nElem = 1;

1722 }

1723 }

1724

1725 if( nElem>0 ){

1726 int nByte = sizeof(Fts3SegReader) + (nElem+1)sizeof(Fts3HashElem );

1727 pReader = (Fts3SegReader *)sqlite3_malloc(nByte);

1728 if( !pReader ){

1729 rc = SQLITE_NOMEM;

1730 }else{

1731 memset(pReader, 0, nByte);

1732 pReader->iIdx = 0x7FFFFFFF;

1733 pReader->ppNextElem = (Fts3HashElem **)&pReader[1];

1734 memcpy(pReader->ppNextElem, aElem, nElemsizeof(Fts3HashElem ));

1735 }

1736 }

1737

1738 if( bPrefix ){

1739 sqlite3_free(aElem);

1740 }

1741 *ppReader = pReader;

1742 return rc;

1743 }

1744

1745 /*

1746 ** Compare the entries pointed to by two Fts3SegReader structures.

1747 ** Comparison is as follows:

1748 **

1749 ** 1) EOF is greater than not EOF.

1750 **

1751 ** 2) The current terms (if any) are compared using memcmp(). If one

1752 ** term is a prefix of another, the longer term is considered the

1753 ** larger.

1754 **

1755 ** 3) By segment age. An older segment is considered larger.

1756 */

1757 static int fts3SegReaderCmp(Fts3SegReader pLhs, Fts3SegReader pRhs){

1758 int rc;

1759 if( pLhs->aNode && pRhs->aNode ){

1760 int rc2 = pLhs->nTerm - pRhs->nTerm;

1761 if( rc2<0 ){

1762 rc = memcmp(pLhs->zTerm, pRhs->zTerm, pLhs->nTerm);

1763 }else{

1764 rc = memcmp(pLhs->zTerm, pRhs->zTerm, pRhs->nTerm);

1765 }

1766 if( rc==0 ){

1767 rc = rc2;

1768 }

1769 }else{

1770 rc = (pLhs->aNode==0) - (pRhs->aNode==0);

1771 }

1772 if( rc==0 ){

1773 rc = pRhs->iIdx - pLhs->iIdx;

1774 }

1775 assert( rc!=0 );

1776 return rc;

1777 }

1778

1779 /*

1780 ** A different comparison function for SegReader structures. In this

1781 ** version, it is assumed that each SegReader points to an entry in

1782 ** a doclist for identical terms. Comparison is made as follows:

1783 **

1784 ** 1) EOF (end of doclist in this case) is greater than not EOF.

1785 **

1786 ** 2) By current docid.

1787 **

1788 ** 3) By segment age. An older segment is considered larger.

1789 */

1790 static int fts3SegReaderDoclistCmp(Fts3SegReader pLhs, Fts3SegReader pRhs){

1791 int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);

1792 if( rc==0 ){

1793 if( pLhs->iDocid==pRhs->iDocid ){

1794 rc = pRhs->iIdx - pLhs->iIdx;

1795 }else{

1796 rc = (pLhs->iDocid > pRhs->iDocid) ? 1 : -1;

1797 }

1798 }

1799 assert( pLhs->aNode && pRhs->aNode );

1800 return rc;

1801 }

1802 static int fts3SegReaderDoclistCmpRev(Fts3SegReader pLhs, Fts3SegReader pRhs){

1803 int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);

1804 if( rc==0 ){

1805 if( pLhs->iDocid==pRhs->iDocid ){

1806 rc = pRhs->iIdx - pLhs->iIdx;

1807 }else{

1808 rc = (pLhs->iDocid < pRhs->iDocid) ? 1 : -1;

1809 }

1810 }

1811 assert( pLhs->aNode && pRhs->aNode );

1812 return rc;

1813 }

1814

1815 /*

1816 ** Compare the term that the Fts3SegReader object passed as the first argument

1817 ** points to with the term specified by arguments zTerm and nTerm.

1818 **

1819 ** If the pSeg iterator is already at EOF, return 0. Otherwise, return

1820 ** -ve if the pSeg term is less than zTerm/nTerm, 0 if the two terms are

1821 ** equal, or +ve if the pSeg term is greater than zTerm/nTerm.

1822 */

1823 static int fts3SegReaderTermCmp(

1824 Fts3SegReader pSeg, / Segment reader object */

1825 const char zTerm, / Term to compare to */

1826 int nTerm /* Size of term zTerm in bytes */

1827 ){

1828 int res = 0;

1829 if( pSeg->aNode ){

1830 if( pSeg->nTerm>nTerm ){

1831 res = memcmp(pSeg->zTerm, zTerm, nTerm);

1832 }else{

1833 res = memcmp(pSeg->zTerm, zTerm, pSeg->nTerm);

1834 }

1835 if( res==0 ){

1836 res = pSeg->nTerm-nTerm;

1837 }

1838 }

1839 return res;

1840 }

1841

1842 /*

1843 ** Argument apSegment is an array of nSegment elements. It is known that

1844 ** the final (nSegment-nSuspect) members are already in sorted order

1845 ** (according to the comparison function provided). This function shuffles

1846 ** the array around until all entries are in sorted order.

1847 */

1848 static void fts3SegReaderSort(

1849 Fts3SegReader *apSegment, / Array to sort entries of */

1850 int nSegment, /* Size of apSegment array */

1851 int nSuspect, /* Unsorted entry count */

1852 int (xCmp)(Fts3SegReader , Fts3SegReader ) / Comparison function */

1853 ){

1854 int i; /* Iterator variable */

1855

1856 assert( nSuspect<=nSegment );

1857

1858 if( nSuspect==nSegment ) nSuspect--;

1859 for(i=nSuspect-1; i>=0; i--){

1860 int j;

1861 for(j=i; j<(nSegment-1); j++){

1862 Fts3SegReader *pTmp;

1863 if( xCmp(apSegment[j], apSegment[j+1])<0 ) break;

1864 pTmp = apSegment[j+1];

1865 apSegment[j+1] = apSegment[j];

1866 apSegment[j] = pTmp;

1867 }

1868 }

1869

1870 #ifndef NDEBUG

1871 /* Check that the list really is sorted now. */

1872 for(i=0; i<(nSuspect-1); i++){

1873 assert( xCmp(apSegment[i], apSegment[i+1])<0 );

1874 }

1875 #endif

1876 }

1877

1878 /*

1879 ** Insert a record into the %_segments table.

1880 */

1881 static int fts3WriteSegment(

1882 Fts3Table p, / Virtual table handle */

1883 sqlite3_int64 iBlock, /* Block id for new block */

1884 char z, / Pointer to buffer containing block data */

1885 int n /* Size of buffer z in bytes */

1886 ){

1887 sqlite3_stmt *pStmt;

1888 int rc = fts3SqlStmt(p, SQL_INSERT_SEGMENTS, &pStmt, 0);

1889 if( rc==SQLITE_OK ){

1890 sqlite3_bind_int64(pStmt, 1, iBlock);

1891 sqlite3_bind_blob(pStmt, 2, z, n, SQLITE_STATIC);

1892 sqlite3_step(pStmt);

1893 rc = sqlite3_reset(pStmt);

1894 }

1895 return rc;

1896 }

1897

1898 /*

1899 ** Find the largest relative level number in the table. If successful, set

1900 ** *pnMax to this value and return SQLITE_OK. Otherwise, if an error occurs,

1901 ** set *pnMax to zero and return an SQLite error code.

1902 */

1903 int sqlite3Fts3MaxLevel(Fts3Table p, int pnMax){

1904 int rc;

1905 int mxLevel = 0;

1906 sqlite3_stmt *pStmt = 0;

1907

1908 rc = fts3SqlStmt(p, SQL_SELECT_MXLEVEL, &pStmt, 0);

1909 if( rc==SQLITE_OK ){

1910 if( SQLITE_ROW==sqlite3_step(pStmt) ){

1911 mxLevel = sqlite3_column_int(pStmt, 0);

1912 }

1913 rc = sqlite3_reset(pStmt);

1914 }

1915 *pnMax = mxLevel;

1916 return rc;

1917 }

1918

1919 /*

1920 ** Insert a record into the %_segdir table.

1921 */

1922 static int fts3WriteSegdir(

1923 Fts3Table p, / Virtual table handle */

1924 sqlite3_int64 iLevel, /* Value for "level" field (absolute level) */

1925 int iIdx, /* Value for "idx" field */

1926 sqlite3_int64 iStartBlock, /* Value for "start_block" field */

1927 sqlite3_int64 iLeafEndBlock, /* Value for "leaves_end_block" field */

1928 sqlite3_int64 iEndBlock, /* Value for "end_block" field */

1929 sqlite3_int64 nLeafData, /* Bytes of leaf data in segment */

1930 char zRoot, / Blob value for "root" field */

1931 int nRoot /* Number of bytes in buffer zRoot */

1932 ){

1933 sqlite3_stmt *pStmt;

1934 int rc = fts3SqlStmt(p, SQL_INSERT_SEGDIR, &pStmt, 0);

1935 if( rc==SQLITE_OK ){

1936 sqlite3_bind_int64(pStmt, 1, iLevel);

1937 sqlite3_bind_int(pStmt, 2, iIdx);

1938 sqlite3_bind_int64(pStmt, 3, iStartBlock);

1939 sqlite3_bind_int64(pStmt, 4, iLeafEndBlock);

1940 if( nLeafData==0 ){

1941 sqlite3_bind_int64(pStmt, 5, iEndBlock);

1942 }else{

1943 char *zEnd = sqlite3_mprintf("%lld %lld", iEndBlock, nLeafData);

1944 if( !zEnd ) return SQLITE_NOMEM;

1945 sqlite3_bind_text(pStmt, 5, zEnd, -1, sqlite3_free);

1946 }

1947 sqlite3_bind_blob(pStmt, 6, zRoot, nRoot, SQLITE_STATIC);

1948 sqlite3_step(pStmt);

1949 rc = sqlite3_reset(pStmt);

1950 }

1951 return rc;

1952 }

1953

1954 /*

1955 ** Return the size of the common prefix (if any) shared by zPrev and

1956 ** zNext, in bytes. For example,

1957 **

1958 ** fts3PrefixCompress("abc", 3, "abcdef", 6) // returns 3

1959 ** fts3PrefixCompress("abX", 3, "abcdef", 6) // returns 2

1960 ** fts3PrefixCompress("abX", 3, "Xbcdef", 6) // returns 0

1961 */

1962 static int fts3PrefixCompress(

1963 const char zPrev, / Buffer containing previous term */

1964 int nPrev, /* Size of buffer zPrev in bytes */

1965 const char zNext, / Buffer containing next term */

1966 int nNext /* Size of buffer zNext in bytes */

1967 ){

1968 int n;

1969 UNUSED_PARAMETER(nNext);

1970 for(n=0; n<nPrev && zPrev[n]==zNext[n]; n++);

1971 return n;

1972 }

1973

1974 /*

1975 ** Add term zTerm to the SegmentNode. It is guaranteed that zTerm is larger

1976 ** (according to memcmp) than the previous term.

1977 */

1978 static int fts3NodeAddTerm(

1979 Fts3Table p, / Virtual table handle */

1980 SegmentNode *ppTree, / IN/OUT: SegmentNode handle */

1981 int isCopyTerm, /* True if zTerm/nTerm is transient */

1982 const char zTerm, / Pointer to buffer containing term */

1983 int nTerm /* Size of term in bytes */

1984 ){

1985 SegmentNode pTree = ppTree;

1986 int rc;

1987 SegmentNode *pNew;

1988

1989 /* First try to append the term to the current node. Return early if

1990 ** this is possible.

1991 */

1992 if( pTree ){

1993 int nData = pTree->nData; /* Current size of node in bytes */

1994 int nReq = nData; /* Required space after adding zTerm */

1995 int nPrefix; /* Number of bytes of prefix compression */

1996 int nSuffix; /* Suffix length */

1997

1998 nPrefix = fts3PrefixCompress(pTree->zTerm, pTree->nTerm, zTerm, nTerm);

1999 nSuffix = nTerm-nPrefix;

2000

2001 nReq += sqlite3Fts3VarintLen(nPrefix)+sqlite3Fts3VarintLen(nSuffix)+nSuffix;

2002 if( nReq<=p->nNodeSize \|\| !pTree->zTerm ){

2003

2004 if( nReq>p->nNodeSize ){

2005 /* An unusual case: this is the first term to be added to the node

2006 ** and the static node buffer (p->nNodeSize bytes) is not large

2007 ** enough. Use a separately malloced buffer instead This wastes

2008 ** p->nNodeSize bytes, but since this scenario only comes about when

2009 ** the database contain two terms that share a prefix of almost 2KB,

2010 ** this is not expected to be a serious problem.

2011 */

2012 assert( pTree->aData==(char *)&pTree[1] );

2013 pTree->aData = (char *)sqlite3_malloc(nReq);

2014 if( !pTree->aData ){

2015 return SQLITE_NOMEM;

2016 }

2017 }

2018

2019 if( pTree->zTerm ){

2020 /* There is no prefix-length field for first term in a node */

2021 nData += sqlite3Fts3PutVarint(&pTree->aData[nData], nPrefix);

2022 }

2023

2024 nData += sqlite3Fts3PutVarint(&pTree->aData[nData], nSuffix);

2025 memcpy(&pTree->aData[nData], &zTerm[nPrefix], nSuffix);

2026 pTree->nData = nData + nSuffix;

2027 pTree->nEntry++;

2028

2029 if( isCopyTerm ){

2030 if( pTree->nMalloc<nTerm ){

2031 char zNew = sqlite3_realloc(pTree->zMalloc, nTerm2);

2032 if( !zNew ){

2033 return SQLITE_NOMEM;

2034 }

2035 pTree->nMalloc = nTerm*2;

2036 pTree->zMalloc = zNew;

2037 }

2038 pTree->zTerm = pTree->zMalloc;

2039 memcpy(pTree->zTerm, zTerm, nTerm);

2040 pTree->nTerm = nTerm;

2041 }else{

2042 pTree->zTerm = (char *)zTerm;

2043 pTree->nTerm = nTerm;

2044 }

2045 return SQLITE_OK;

2046 }

2047 }

2048

2049 /* If control flows to here, it was not possible to append zTerm to the

2050 ** current node. Create a new node (a right-sibling of the current node).

2051 ** If this is the first node in the tree, the term is added to it.

2052 **

2053 ** Otherwise, the term is not added to the new node, it is left empty for

2054 ** now. Instead, the term is inserted into the parent of pTree. If pTree

2055 ** has no parent, one is created here.

2056 */

2057 pNew = (SegmentNode *)sqlite3_malloc(sizeof(SegmentNode) + p->nNodeSize);

2058 if( !pNew ){

2059 return SQLITE_NOMEM;

2060 }

2061 memset(pNew, 0, sizeof(SegmentNode));

2062 pNew->nData = 1 + FTS3_VARINT_MAX;

2063 pNew->aData = (char *)&pNew[1];

2064

2065 if( pTree ){

2066 SegmentNode *pParent = pTree->pParent;

2067 rc = fts3NodeAddTerm(p, &pParent, isCopyTerm, zTerm, nTerm);

2068 if( pTree->pParent==0 ){

2069 pTree->pParent = pParent;

2070 }

2071 pTree->pRight = pNew;

2072 pNew->pLeftmost = pTree->pLeftmost;

2073 pNew->pParent = pParent;

2074 pNew->zMalloc = pTree->zMalloc;

2075 pNew->nMalloc = pTree->nMalloc;

2076 pTree->zMalloc = 0;

2077 }else{

2078 pNew->pLeftmost = pNew;

2079 rc = fts3NodeAddTerm(p, &pNew, isCopyTerm, zTerm, nTerm);

2080 }

2081

2082 *ppTree = pNew;

2083 return rc;

2084 }

2085

2086 /*

2087 ** Helper function for fts3NodeWrite().

2088 */

2089 static int fts3TreeFinishNode(

2090 SegmentNode *pTree,

2091 int iHeight,

2092 sqlite3_int64 iLeftChild

2093 ){

2094 int nStart;

2095 assert( iHeight>=1 && iHeight<128 );

2096 nStart = FTS3_VARINT_MAX - sqlite3Fts3VarintLen(iLeftChild);

2097 pTree->aData[nStart] = (char)iHeight;

2098 sqlite3Fts3PutVarint(&pTree->aData[nStart+1], iLeftChild);

2099 return nStart;

2100 }

2101

2102 /*

2103 ** Write the buffer for the segment node pTree and all of its peers to the

2104 ** database. Then call this function recursively to write the parent of

2105 ** pTree and its peers to the database.

2106 **

2107 ** Except, if pTree is a root node, do not write it to the database. Instead,

2108 ** set output variables paRoot and pnRoot to contain the root node.

2109 **

2110 ** If successful, SQLITE_OK is returned and output variable *piLast is

2111 ** set to the largest blockid written to the database (or zero if no

2112 ** blocks were written to the db). Otherwise, an SQLite error code is

2113 ** returned.

2114 */

2115 static int fts3NodeWrite(

2116 Fts3Table p, / Virtual table handle */

2117 SegmentNode pTree, / SegmentNode handle */

2118 int iHeight, /* Height of this node in tree */

2119 sqlite3_int64 iLeaf, /* Block id of first leaf node */

2120 sqlite3_int64 iFree, /* Block id of next free slot in %_segments */

2121 sqlite3_int64 piLast, / OUT: Block id of last entry written */

2122 char *paRoot, / OUT: Data for root node */

2123 int pnRoot / OUT: Size of root node in bytes */

2124 ){

2125 int rc = SQLITE_OK;

2126

2127 if( !pTree->pParent ){

2128 /* Root node of the tree. */

2129 int nStart = fts3TreeFinishNode(pTree, iHeight, iLeaf);

2130 *piLast = iFree-1;

2131 *pnRoot = pTree->nData - nStart;

2132 *paRoot = &pTree->aData[nStart];

2133 }else{

2134 SegmentNode *pIter;

2135 sqlite3_int64 iNextFree = iFree;

2136 sqlite3_int64 iNextLeaf = iLeaf;

2137 for(pIter=pTree->pLeftmost; pIter && rc==SQLITE_OK; pIter=pIter->pRight){

2138 int nStart = fts3TreeFinishNode(pIter, iHeight, iNextLeaf);

2139 int nWrite = pIter->nData - nStart;

2140

2141 rc = fts3WriteSegment(p, iNextFree, &pIter->aData[nStart], nWrite);

2142 iNextFree++;

2143 iNextLeaf += (pIter->nEntry+1);

2144 }

2145 if( rc==SQLITE_OK ){

2146 assert( iNextLeaf==iFree );

2147 rc = fts3NodeWrite(

2148 p, pTree->pParent, iHeight+1, iFree, iNextFree, piLast, paRoot, pnRoot

2149 );

2150 }

2151 }

2152

2153 return rc;

2154 }

2155

2156 /*

2157 ** Free all memory allocations associated with the tree pTree.

2158 */

2159 static void fts3NodeFree(SegmentNode *pTree){

2160 if( pTree ){

2161 SegmentNode *p = pTree->pLeftmost;

2162 fts3NodeFree(p->pParent);

2163 while( p ){

2164 SegmentNode *pRight = p->pRight;

2165 if( p->aData!=(char *)&p[1] ){

2166 sqlite3_free(p->aData);

2167 }

2168 assert( pRight==0 \|\| p->zMalloc==0 );

2169 sqlite3_free(p->zMalloc);

2170 sqlite3_free(p);

2171 p = pRight;

2172 }

2173 }

2174 }

2175

2176 /*

2177 ** Add a term to the segment being constructed by the SegmentWriter object

2178 ** ppWriter. When adding the first term to a segment, ppWriter should

2179 ** be passed NULL. This function will allocate a new SegmentWriter object

2180 ** and return it via the input/output variable *ppWriter in this case.

2181 **

2182 ** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.

2183 */

2184 static int fts3SegWriterAdd(

2185 Fts3Table p, / Virtual table handle */

2186 SegmentWriter *ppWriter, / IN/OUT: SegmentWriter handle */

2187 int isCopyTerm, /* True if buffer zTerm must be copied */

2188 const char zTerm, / Pointer to buffer containing term */

2189 int nTerm, /* Size of term in bytes */

2190 const char aDoclist, / Pointer to buffer containing doclist */

2191 int nDoclist /* Size of doclist in bytes */

2192 ){

2193 int nPrefix; /* Size of term prefix in bytes */

2194 int nSuffix; /* Size of term suffix in bytes */

2195 int nReq; /* Number of bytes required on leaf page */

2196 int nData;

2197 SegmentWriter pWriter = ppWriter;

2198

2199 if( !pWriter ){

2200 int rc;

2201 sqlite3_stmt *pStmt;

2202

2203 /* Allocate the SegmentWriter structure */

2204 pWriter = (SegmentWriter *)sqlite3_malloc(sizeof(SegmentWriter));

2205 if( !pWriter ) return SQLITE_NOMEM;

2206 memset(pWriter, 0, sizeof(SegmentWriter));

2207 *ppWriter = pWriter;

2208

2209 /* Allocate a buffer in which to accumulate data */

2210 pWriter->aData = (char *)sqlite3_malloc(p->nNodeSize);

2211 if( !pWriter->aData ) return SQLITE_NOMEM;

2212 pWriter->nSize = p->nNodeSize;

2213

2214 /* Find the next free blockid in the %_segments table */

2215 rc = fts3SqlStmt(p, SQL_NEXT_SEGMENTS_ID, &pStmt, 0);

2216 if( rc!=SQLITE_OK ) return rc;

2217 if( SQLITE_ROW==sqlite3_step(pStmt) ){

2218 pWriter->iFree = sqlite3_column_int64(pStmt, 0);

2219 pWriter->iFirst = pWriter->iFree;

2220 }

2221 rc = sqlite3_reset(pStmt);

2222 if( rc!=SQLITE_OK ) return rc;

2223 }

2224 nData = pWriter->nData;

2225

2226 nPrefix = fts3PrefixCompress(pWriter->zTerm, pWriter->nTerm, zTerm, nTerm);

2227 nSuffix = nTerm-nPrefix;

2228

2229 /* Figure out how many bytes are required by this new entry */

2230 nReq = sqlite3Fts3VarintLen(nPrefix) + /* varint containing prefix size */

2231 sqlite3Fts3VarintLen(nSuffix) + /* varint containing suffix size */

2232 nSuffix + /* Term suffix */

2233 sqlite3Fts3VarintLen(nDoclist) + /* Size of doclist */

2234 nDoclist; /* Doclist data */

2235

2236 if( nData>0 && nData+nReq>p->nNodeSize ){

2237 int rc;

2238

2239 /* The current leaf node is full. Write it out to the database. */

2240 rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, nData);

2241 if( rc!=SQLITE_OK ) return rc;

2242 p->nLeafAdd++;

2243

2244 /* Add the current term to the interior node tree. The term added to

2245 ** the interior tree must:

2246 **

2247 ** a) be greater than the largest term on the leaf node just written

2248 ** to the database (still available in pWriter->zTerm), and

2249 **

2250 ** b) be less than or equal to the term about to be added to the new

2251 ** leaf node (zTerm/nTerm).

2252 **

2253 ** In other words, it must be the prefix of zTerm 1 byte longer than

2254 ** the common prefix (if any) of zTerm and pWriter->zTerm.

2255 */

2256 assert( nPrefix<nTerm );

2257 rc = fts3NodeAddTerm(p, &pWriter->pTree, isCopyTerm, zTerm, nPrefix+1);

2258 if( rc!=SQLITE_OK ) return rc;

2259

2260 nData = 0;

2261 pWriter->nTerm = 0;

2262

2263 nPrefix = 0;

2264 nSuffix = nTerm;

2265 nReq = 1 + /* varint containing prefix size */

2266 sqlite3Fts3VarintLen(nTerm) + /* varint containing suffix size */

2267 nTerm + /* Term suffix */

2268 sqlite3Fts3VarintLen(nDoclist) + /* Size of doclist */

2269 nDoclist; /* Doclist data */

2270 }

2271

2272 /* Increase the total number of bytes written to account for the new entry. */

2273 pWriter->nLeafData += nReq;

2274

2275 /* If the buffer currently allocated is too small for this entry, realloc

2276 ** the buffer to make it large enough.

2277 */

2278 if( nReq>pWriter->nSize ){

2279 char *aNew = sqlite3_realloc(pWriter->aData, nReq);

2280 if( !aNew ) return SQLITE_NOMEM;

2281 pWriter->aData = aNew;

2282 pWriter->nSize = nReq;

2283 }

2284 assert( nData+nReq<=pWriter->nSize );

2285

2286 /* Append the prefix-compressed term and doclist to the buffer. */

2287 nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nPrefix);

2288 nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nSuffix);

2289 memcpy(&pWriter->aData[nData], &zTerm[nPrefix], nSuffix);

2290 nData += nSuffix;

2291 nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nDoclist);

2292 memcpy(&pWriter->aData[nData], aDoclist, nDoclist);

2293 pWriter->nData = nData + nDoclist;

2294

2295 /* Save the current term so that it can be used to prefix-compress the next.

2296 ** If the isCopyTerm parameter is true, then the buffer pointed to by

2297 ** zTerm is transient, so take a copy of the term data. Otherwise, just

2298 ** store a copy of the pointer.

2299 */

2300 if( isCopyTerm ){

2301 if( nTerm>pWriter->nMalloc ){

2302 char zNew = sqlite3_realloc(pWriter->zMalloc, nTerm2);

2303 if( !zNew ){

2304 return SQLITE_NOMEM;

2305 }

2306 pWriter->nMalloc = nTerm*2;

2307 pWriter->zMalloc = zNew;

2308 pWriter->zTerm = zNew;

2309 }

2310 assert( pWriter->zTerm==pWriter->zMalloc );

2311 memcpy(pWriter->zTerm, zTerm, nTerm);

2312 }else{

2313 pWriter->zTerm = (char *)zTerm;

2314 }

2315 pWriter->nTerm = nTerm;

2316

2317 return SQLITE_OK;

2318 }

2319

2320 /*

2321 ** Flush all data associated with the SegmentWriter object pWriter to the

2322 ** database. This function must be called after all terms have been added

2323 ** to the segment using fts3SegWriterAdd(). If successful, SQLITE_OK is

2324 ** returned. Otherwise, an SQLite error code.

2325 */

2326 static int fts3SegWriterFlush(

2327 Fts3Table p, / Virtual table handle */

2328 SegmentWriter pWriter, / SegmentWriter to flush to the db */

2329 sqlite3_int64 iLevel, /* Value for 'level' column of %_segdir */

2330 int iIdx /* Value for 'idx' column of %_segdir */

2331 ){

2332 int rc; /* Return code */

2333 if( pWriter->pTree ){

2334 sqlite3_int64 iLast = 0; /* Largest block id written to database */

2335 sqlite3_int64 iLastLeaf; /* Largest leaf block id written to db */

2336 char zRoot = NULL; / Pointer to buffer containing root node */

2337 int nRoot = 0; /* Size of buffer zRoot */

2338

2339 iLastLeaf = pWriter->iFree;

2340 rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, pWriter->nData);

2341 if( rc==SQLITE_OK ){

2342 rc = fts3NodeWrite(p, pWriter->pTree, 1,

2343 pWriter->iFirst, pWriter->iFree, &iLast, &zRoot, &nRoot);

2344 }

2345 if( rc==SQLITE_OK ){

2346 rc = fts3WriteSegdir(p, iLevel, iIdx,

2347 pWriter->iFirst, iLastLeaf, iLast, pWriter->nLeafData, zRoot, nRoot);

2348 }

2349 }else{

2350 /* The entire tree fits on the root node. Write it to the segdir table. */

2351 rc = fts3WriteSegdir(p, iLevel, iIdx,

2352 0, 0, 0, pWriter->nLeafData, pWriter->aData, pWriter->nData);

2353 }

2354 p->nLeafAdd++;

2355 return rc;

2356 }

2357

2358 /*

2359 ** Release all memory held by the SegmentWriter object passed as the

2360 ** first argument.

2361 */

2362 static void fts3SegWriterFree(SegmentWriter *pWriter){

2363 if( pWriter ){

2364 sqlite3_free(pWriter->aData);

2365 sqlite3_free(pWriter->zMalloc);

2366 fts3NodeFree(pWriter->pTree);

2367 sqlite3_free(pWriter);

2368 }

2369 }

2370

2371 /*

2372 ** The first value in the apVal[] array is assumed to contain an integer.

2373 ** This function tests if there exist any documents with docid values that

2374 ** are different from that integer. i.e. if deleting the document with docid

2375 ** pRowid would mean the FTS3 table were empty.

2376 **

2377 ** If successful, *pisEmpty is set to true if the table is empty except for

2378 ** document pRowid, or false otherwise, and SQLITE_OK is returned. If an

2379 ** error occurs, an SQLite error code is returned.

2380 */

2381 static int fts3IsEmpty(Fts3Table p, sqlite3_value pRowid, int *pisEmpty){

2382 sqlite3_stmt *pStmt;

2383 int rc;

2384 if( p->zContentTbl ){

2385 /* If using the content=xxx option, assume the table is never empty */

2386 *pisEmpty = 0;

2387 rc = SQLITE_OK;

2388 }else{

2389 rc = fts3SqlStmt(p, SQL_IS_EMPTY, &pStmt, &pRowid);

2390 if( rc==SQLITE_OK ){

2391 if( SQLITE_ROW==sqlite3_step(pStmt) ){

2392 *pisEmpty = sqlite3_column_int(pStmt, 0);

2393 }

2394 rc = sqlite3_reset(pStmt);

2395 }

2396 }

2397 return rc;

2398 }

2399

2400 /*

2401 ** Set *pnMax to the largest segment level in the database for the index

2402 ** iIndex.

2403 **

2404 ** Segment levels are stored in the 'level' column of the %_segdir table.

2405 **

2406 ** Return SQLITE_OK if successful, or an SQLite error code if not.

2407 */

2408 static int fts3SegmentMaxLevel(

2409 Fts3Table *p,

2410 int iLangid,

2411 int iIndex,

2412 sqlite3_int64 *pnMax

2413 ){

2414 sqlite3_stmt *pStmt;

2415 int rc;

2416 assert( iIndex>=0 && iIndex<p->nIndex );

2417

2418 /* Set pStmt to the compiled version of:

2419 **

2420 ** SELECT max(level) FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?

2421 **

2422 ** (1024 is actually the value of macro FTS3_SEGDIR_PREFIXLEVEL_STR).

2423 */

2424 rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR_MAX_LEVEL, &pStmt, 0);

2425 if( rc!=SQLITE_OK ) return rc;

2426 sqlite3_bind_int64(pStmt, 1, getAbsoluteLevel(p, iLangid, iIndex, 0));

2427 sqlite3_bind_int64(pStmt, 2,

2428 getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1)

2429 );

2430 if( SQLITE_ROW==sqlite3_step(pStmt) ){

2431 *pnMax = sqlite3_column_int64(pStmt, 0);

2432 }

2433 return sqlite3_reset(pStmt);

2434 }

2435

2436 /*

2437 ** iAbsLevel is an absolute level that may be assumed to exist within

2438 ** the database. This function checks if it is the largest level number

2439 ** within its index. Assuming no error occurs, *pbMax is set to 1 if

2440 ** iAbsLevel is indeed the largest level, or 0 otherwise, and SQLITE_OK

2441 ** is returned. If an error occurs, an error code is returned and the

2442 ** final value of *pbMax is undefined.

2443 */

2444 static int fts3SegmentIsMaxLevel(Fts3Table p, i64 iAbsLevel, int pbMax){

2445

2446 /* Set pStmt to the compiled version of:

2447 **

2448 ** SELECT max(level) FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?

2449 **

2450 ** (1024 is actually the value of macro FTS3_SEGDIR_PREFIXLEVEL_STR).

2451 */

2452 sqlite3_stmt *pStmt;

2453 int rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR_MAX_LEVEL, &pStmt, 0);

2454 if( rc!=SQLITE_OK ) return rc;

2455 sqlite3_bind_int64(pStmt, 1, iAbsLevel+1);

2456 sqlite3_bind_int64(pStmt, 2,

2457 ((iAbsLevel/FTS3_SEGDIR_MAXLEVEL)+1) * FTS3_SEGDIR_MAXLEVEL

2458 );

2459

2460 *pbMax = 0;

2461 if( SQLITE_ROW==sqlite3_step(pStmt) ){

2462 *pbMax = sqlite3_column_type(pStmt, 0)==SQLITE_NULL;

2463 }

2464 return sqlite3_reset(pStmt);

2465 }

2466

2467 /*

2468 ** Delete all entries in the %_segments table associated with the segment

2469 ** opened with seg-reader pSeg. This function does not affect the contents

2470 ** of the %_segdir table.

2471 */

2472 static int fts3DeleteSegment(

2473 Fts3Table p, / FTS table handle */

2474 Fts3SegReader pSeg / Segment to delete */

2475 ){

2476 int rc = SQLITE_OK; /* Return code */

2477 if( pSeg->iStartBlock ){

2478 sqlite3_stmt pDelete; / SQL statement to delete rows */

2479 rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDelete, 0);

2480 if( rc==SQLITE_OK ){

2481 sqlite3_bind_int64(pDelete, 1, pSeg->iStartBlock);

2482 sqlite3_bind_int64(pDelete, 2, pSeg->iEndBlock);

2483 sqlite3_step(pDelete);

2484 rc = sqlite3_reset(pDelete);

2485 }

2486 }

2487 return rc;

2488 }

2489

2490 /*

2491 ** This function is used after merging multiple segments into a single large

2492 ** segment to delete the old, now redundant, segment b-trees. Specifically,

2493 ** it:

2494 **

2495 ** 1) Deletes all %_segments entries for the segments associated with

2496 ** each of the SegReader objects in the array passed as the third

2497 ** argument, and

2498 **

2499 ** 2) deletes all %_segdir entries with level iLevel, or all %_segdir

2500 ** entries regardless of level if (iLevel<0).

2501 **

2502 ** SQLITE_OK is returned if successful, otherwise an SQLite error code.

2503 */

2504 static int fts3DeleteSegdir(

2505 Fts3Table p, / Virtual table handle */

2506 int iLangid, /* Language id */

2507 int iIndex, /* Index for p->aIndex */

2508 int iLevel, /* Level of %_segdir entries to delete */

2509 Fts3SegReader *apSegment, / Array of SegReader objects */

2510 int nReader /* Size of array apSegment */

2511 ){

2512 int rc = SQLITE_OK; /* Return Code */

2513 int i; /* Iterator variable */

2514 sqlite3_stmt pDelete = 0; / SQL statement to delete rows */

2515

2516 for(i=0; rc==SQLITE_OK && i<nReader; i++){

2517 rc = fts3DeleteSegment(p, apSegment[i]);

2518 }

2519 if( rc!=SQLITE_OK ){

2520 return rc;

2521 }

2522

2523 assert( iLevel>=0 \|\| iLevel==FTS3_SEGCURSOR_ALL );

2524 if( iLevel==FTS3_SEGCURSOR_ALL ){

2525 rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_RANGE, &pDelete, 0);

2526 if( rc==SQLITE_OK ){

2527 sqlite3_bind_int64(pDelete, 1, getAbsoluteLevel(p, iLangid, iIndex, 0));

2528 sqlite3_bind_int64(pDelete, 2,

2529 getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1)

2530 );

2531 }

2532 }else{

2533 rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_LEVEL, &pDelete, 0);

2534 if( rc==SQLITE_OK ){

2535 sqlite3_bind_int64(

2536 pDelete, 1, getAbsoluteLevel(p, iLangid, iIndex, iLevel)

2537 );

2538 }

2539 }

2540

2541 if( rc==SQLITE_OK ){

2542 sqlite3_step(pDelete);

2543 rc = sqlite3_reset(pDelete);

2544 }

2545

2546 return rc;

2547 }

2548

2549 /*

2550 ** When this function is called, buffer ppList (size pnList bytes) contains

2551 ** a position list that may (or may not) feature multiple columns. This

2552 ** function adjusts the pointer ppList and the length pnList so that they

2553 ** identify the subset of the position list that corresponds to column iCol.

2554 **

2555 ** If there are no entries in the input position list for column iCol, then

2556 ** *pnList is set to zero before returning.

2557 **

2558 ** If parameter bZero is non-zero, then any part of the input list following

2559 ** the end of the output list is zeroed before returning.

2560 */

2561 static void fts3ColumnFilter(

2562 int iCol, /* Column to filter on */

2563 int bZero, /* Zero out anything following ppList /

2564 char *ppList, / IN/OUT: Pointer to position list */

2565 int pnList / IN/OUT: Size of buffer ppList in bytes /

2566 ){

2567 char pList = ppList;

2568 int nList = *pnList;

2569 char *pEnd = &pList[nList];

2570 int iCurrent = 0;

2571 char *p = pList;

2572

2573 assert( iCol>=0 );

2574 while( 1 ){

2575 char c = 0;

2576 while( p<pEnd && (c \| p)&0xFE ) c = p++ & 0x80;

2577

2578 if( iCol==iCurrent ){

2579 nList = (int)(p - pList);

2580 break;

2581 }

2582

2583 nList -= (int)(p - pList);

2584 pList = p;

2585 if( nList==0 ){

2586 break;

2587 }

2588 p = &pList[1];

2589 p += fts3GetVarint32(p, &iCurrent);

2590 }

2591

2592 if( bZero && &pList[nList]!=pEnd ){

2593 memset(&pList[nList], 0, pEnd - &pList[nList]);

2594 }

2595 *ppList = pList;

2596 *pnList = nList;

2597 }

2598

2599 /*

2600 ** Cache data in the Fts3MultiSegReader.aBuffer[] buffer (overwriting any

2601 ** existing data). Grow the buffer if required.

2602 **

2603 ** If successful, return SQLITE_OK. Otherwise, if an OOM error is encountered

2604 ** trying to resize the buffer, return SQLITE_NOMEM.

2605 */

2606 static int fts3MsrBufferData(

2607 Fts3MultiSegReader pMsr, / Multi-segment-reader handle */

2608 char *pList,

2609 int nList

2610 ){

2611 if( nList>pMsr->nBuffer ){

2612 char *pNew;

2613 pMsr->nBuffer = nList*2;

2614 pNew = (char *)sqlite3_realloc(pMsr->aBuffer, pMsr->nBuffer);

2615 if( !pNew ) return SQLITE_NOMEM;

2616 pMsr->aBuffer = pNew;

2617 }

2618

2619 memcpy(pMsr->aBuffer, pList, nList);

2620 return SQLITE_OK;

2621 }

2622

2623 int sqlite3Fts3MsrIncrNext(

2624 Fts3Table p, / Virtual table handle */

2625 Fts3MultiSegReader pMsr, / Multi-segment-reader handle */

2626 sqlite3_int64 piDocid, / OUT: Docid value */

2627 char *paPoslist, / OUT: Pointer to position list */

2628 int pnPoslist / OUT: Size of position list in bytes */

2629 ){

2630 int nMerge = pMsr->nAdvance;

2631 Fts3SegReader **apSegment = pMsr->apSegment;

2632 int (xCmp)(Fts3SegReader , Fts3SegReader *) = (

2633 p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp

2634 );

2635

2636 if( nMerge==0 ){

2637 *paPoslist = 0;

2638 return SQLITE_OK;

2639 }

2640

2641 while( 1 ){

2642 Fts3SegReader *pSeg;

2643 pSeg = pMsr->apSegment[0];

2644

2645 if( pSeg->pOffsetList==0 ){

2646 *paPoslist = 0;

2647 break;

2648 }else{

2649 int rc;

2650 char *pList;

2651 int nList;

2652 int j;

2653 sqlite3_int64 iDocid = apSegment[0]->iDocid;

2654

2655 rc = fts3SegReaderNextDocid(p, apSegment[0], &pList, &nList);

2656 j = 1;

2657 while( rc==SQLITE_OK

2658 && j<nMerge

2659 && apSegment[j]->pOffsetList

2660 && apSegment[j]->iDocid==iDocid

2661 ){

2662 rc = fts3SegReaderNextDocid(p, apSegment[j], 0, 0);

2663 j++;

2664 }

2665 if( rc!=SQLITE_OK ) return rc;

2666 fts3SegReaderSort(pMsr->apSegment, nMerge, j, xCmp);

2667

2668 if( nList>0 && fts3SegReaderIsPending(apSegment[0]) ){

2669 rc = fts3MsrBufferData(pMsr, pList, nList+1);

2670 if( rc!=SQLITE_OK ) return rc;

2671 assert( (pMsr->aBuffer[nList] & 0xFE)==0x00 );

2672 pList = pMsr->aBuffer;

2673 }

2674

2675 if( pMsr->iColFilter>=0 ){

2676 fts3ColumnFilter(pMsr->iColFilter, 1, &pList, &nList);

2677 }

2678

2679 if( nList>0 ){

2680 *paPoslist = pList;

2681 *piDocid = iDocid;

2682 *pnPoslist = nList;

2683 break;

2684 }

2685 }

2686 }

2687

2688 return SQLITE_OK;

2689 }

2690

2691 static int fts3SegReaderStart(

2692 Fts3Table p, / Virtual table handle */

2693 Fts3MultiSegReader pCsr, / Cursor object */

2694 const char zTerm, / Term searched for (or NULL) */

2695 int nTerm /* Length of zTerm in bytes */

2696 ){

2697 int i;

2698 int nSeg = pCsr->nSegment;

2699

2700 /* If the Fts3SegFilter defines a specific term (or term prefix) to search

2701 ** for, then advance each segment iterator until it points to a term of

2702 ** equal or greater value than the specified term. This prevents many

2703 ** unnecessary merge/sort operations for the case where single segment

2704 ** b-tree leaf nodes contain more than one term.

2705 */

2706 for(i=0; pCsr->bRestart==0 && i<pCsr->nSegment; i++){

2707 int res = 0;

2708 Fts3SegReader *pSeg = pCsr->apSegment[i];

2709 do {

2710 int rc = fts3SegReaderNext(p, pSeg, 0);

2711 if( rc!=SQLITE_OK ) return rc;

2712 }while( zTerm && (res = fts3SegReaderTermCmp(pSeg, zTerm, nTerm))<0 );

2713

2714 if( pSeg->bLookup && res!=0 ){

2715 fts3SegReaderSetEof(pSeg);

2716 }

2717 }

2718 fts3SegReaderSort(pCsr->apSegment, nSeg, nSeg, fts3SegReaderCmp);

2719

2720 return SQLITE_OK;

2721 }

2722

2723 int sqlite3Fts3SegReaderStart(

2724 Fts3Table p, / Virtual table handle */

2725 Fts3MultiSegReader pCsr, / Cursor object */

2726 Fts3SegFilter pFilter / Restrictions on range of iteration */

2727 ){

2728 pCsr->pFilter = pFilter;

2729 return fts3SegReaderStart(p, pCsr, pFilter->zTerm, pFilter->nTerm);

2730 }

2731

2732 int sqlite3Fts3MsrIncrStart(

2733 Fts3Table p, / Virtual table handle */

2734 Fts3MultiSegReader pCsr, / Cursor object */

2735 int iCol, /* Column to match on. */

2736 const char zTerm, / Term to iterate through a doclist for */

2737 int nTerm /* Number of bytes in zTerm */

2738 ){

2739 int i;

2740 int rc;

2741 int nSegment = pCsr->nSegment;

2742 int (xCmp)(Fts3SegReader , Fts3SegReader *) = (

2743 p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp

2744 );

2745

2746 assert( pCsr->pFilter==0 );

2747 assert( zTerm && nTerm>0 );

2748

2749 /* Advance each segment iterator until it points to the term zTerm/nTerm. */

2750 rc = fts3SegReaderStart(p, pCsr, zTerm, nTerm);

2751 if( rc!=SQLITE_OK ) return rc;

2752

2753 /* Determine how many of the segments actually point to zTerm/nTerm. */

2754 for(i=0; i<nSegment; i++){

2755 Fts3SegReader *pSeg = pCsr->apSegment[i];

2756 if( !pSeg->aNode \|\| fts3SegReaderTermCmp(pSeg, zTerm, nTerm) ){

2757 break;

2758 }

2759 }

2760 pCsr->nAdvance = i;

2761

2762 /* Advance each of the segments to point to the first docid. */

2763 for(i=0; i<pCsr->nAdvance; i++){

2764 rc = fts3SegReaderFirstDocid(p, pCsr->apSegment[i]);

2765 if( rc!=SQLITE_OK ) return rc;

2766 }

2767 fts3SegReaderSort(pCsr->apSegment, i, i, xCmp);

2768

2769 assert( iCol<0 \|\| iCol<p->nColumn );

2770 pCsr->iColFilter = iCol;

2771

2772 return SQLITE_OK;

2773 }

2774

2775 /*

2776 ** This function is called on a MultiSegReader that has been started using

2777 ** sqlite3Fts3MsrIncrStart(). One or more calls to MsrIncrNext() may also

2778 ** have been made. Calling this function puts the MultiSegReader in such

2779 ** a state that if the next two calls are:

2780 **

2781 ** sqlite3Fts3SegReaderStart()

2782 ** sqlite3Fts3SegReaderStep()

2783 **

2784 ** then the entire doclist for the term is available in

2785 ** MultiSegReader.aDoclist/nDoclist.

2786 */

2787 int sqlite3Fts3MsrIncrRestart(Fts3MultiSegReader *pCsr){

2788 int i; /* Used to iterate through segment-readers */

2789

2790 assert( pCsr->zTerm==0 );

2791 assert( pCsr->nTerm==0 );

2792 assert( pCsr->aDoclist==0 );

2793 assert( pCsr->nDoclist==0 );

2794

2795 pCsr->nAdvance = 0;

2796 pCsr->bRestart = 1;

2797 for(i=0; i<pCsr->nSegment; i++){

2798 pCsr->apSegment[i]->pOffsetList = 0;

2799 pCsr->apSegment[i]->nOffsetList = 0;

2800 pCsr->apSegment[i]->iDocid = 0;

2801 }

2802

2803 return SQLITE_OK;

2804 }

2805

2806

2807 int sqlite3Fts3SegReaderStep(

2808 Fts3Table p, / Virtual table handle */

2809 Fts3MultiSegReader pCsr / Cursor object */

2810 ){

2811 int rc = SQLITE_OK;

2812

2813 int isIgnoreEmpty = (pCsr->pFilter->flags & FTS3_SEGMENT_IGNORE_EMPTY);

2814 int isRequirePos = (pCsr->pFilter->flags & FTS3_SEGMENT_REQUIRE_POS);

2815 int isColFilter = (pCsr->pFilter->flags & FTS3_SEGMENT_COLUMN_FILTER);

2816 int isPrefix = (pCsr->pFilter->flags & FTS3_SEGMENT_PREFIX);

2817 int isScan = (pCsr->pFilter->flags & FTS3_SEGMENT_SCAN);

2818 int isFirst = (pCsr->pFilter->flags & FTS3_SEGMENT_FIRST);

2819

2820 Fts3SegReader **apSegment = pCsr->apSegment;

2821 int nSegment = pCsr->nSegment;

2822 Fts3SegFilter *pFilter = pCsr->pFilter;

2823 int (xCmp)(Fts3SegReader , Fts3SegReader *) = (

2824 p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp

2825 );

2826

2827 if( pCsr->nSegment==0 ) return SQLITE_OK;

2828

2829 do {

2830 int nMerge;

2831 int i;

2832

2833 /* Advance the first pCsr->nAdvance entries in the apSegment[] array

2834 ** forward. Then sort the list in order of current term again.

2835 */

2836 for(i=0; i<pCsr->nAdvance; i++){

2837 Fts3SegReader *pSeg = apSegment[i];

2838 if( pSeg->bLookup ){

2839 fts3SegReaderSetEof(pSeg);

2840 }else{

2841 rc = fts3SegReaderNext(p, pSeg, 0);

2842 }

2843 if( rc!=SQLITE_OK ) return rc;

2844 }

2845 fts3SegReaderSort(apSegment, nSegment, pCsr->nAdvance, fts3SegReaderCmp);

2846 pCsr->nAdvance = 0;

2847

2848 /* If all the seg-readers are at EOF, we're finished. return SQLITE_OK. */

2849 assert( rc==SQLITE_OK );

2850 if( apSegment[0]->aNode==0 ) break;

2851

2852 pCsr->nTerm = apSegment[0]->nTerm;

2853 pCsr->zTerm = apSegment[0]->zTerm;

2854

2855 /* If this is a prefix-search, and if the term that apSegment[0] points

2856 ** to does not share a suffix with pFilter->zTerm/nTerm, then all

2857 ** required callbacks have been made. In this case exit early.

2858 **

2859 ** Similarly, if this is a search for an exact match, and the first term

2860 ** of segment apSegment[0] is not a match, exit early.

2861 */

2862 if( pFilter->zTerm && !isScan ){

2863 if( pCsr->nTerm<pFilter->nTerm

2864 \|\| (!isPrefix && pCsr->nTerm>pFilter->nTerm)

2865 \|\| memcmp(pCsr->zTerm, pFilter->zTerm, pFilter->nTerm)

2866 ){

2867 break;

2868 }

2869 }

2870

2871 nMerge = 1;

2872 while( nMerge<nSegment

2873 && apSegment[nMerge]->aNode

2874 && apSegment[nMerge]->nTerm==pCsr->nTerm

2875 && 0==memcmp(pCsr->zTerm, apSegment[nMerge]->zTerm, pCsr->nTerm)

2876 ){

2877 nMerge++;

2878 }

2879

2880 assert( isIgnoreEmpty \|\| (isRequirePos && !isColFilter) );

2881 if( nMerge==1

2882 && !isIgnoreEmpty

2883 && !isFirst

2884 && (p->bDescIdx==0 \|\| fts3SegReaderIsPending(apSegment[0])==0)

2885 ){

2886 pCsr->nDoclist = apSegment[0]->nDoclist;

2887 if( fts3SegReaderIsPending(apSegment[0]) ){

2888 rc = fts3MsrBufferData(pCsr, apSegment[0]->aDoclist, pCsr->nDoclist);

2889 pCsr->aDoclist = pCsr->aBuffer;

2890 }else{

2891 pCsr->aDoclist = apSegment[0]->aDoclist;

2892 }

2893 if( rc==SQLITE_OK ) rc = SQLITE_ROW;

2894 }else{

2895 int nDoclist = 0; /* Size of doclist */

2896 sqlite3_int64 iPrev = 0; /* Previous docid stored in doclist */

2897

2898 /* The current term of the first nMerge entries in the array

2899 ** of Fts3SegReader objects is the same. The doclists must be merged

2900 ** and a single term returned with the merged doclist.

2901 */

2902 for(i=0; i<nMerge; i++){

2903 fts3SegReaderFirstDocid(p, apSegment[i]);

2904 }

2905 fts3SegReaderSort(apSegment, nMerge, nMerge, xCmp);

2906 while( apSegment[0]->pOffsetList ){

2907 int j; /* Number of segments that share a docid */

2908 char *pList = 0;

2909 int nList = 0;

2910 int nByte;

2911 sqlite3_int64 iDocid = apSegment[0]->iDocid;

2912 fts3SegReaderNextDocid(p, apSegment[0], &pList, &nList);

2913 j = 1;

2914 while( j<nMerge

2915 && apSegment[j]->pOffsetList

2916 && apSegment[j]->iDocid==iDocid

2917 ){

2918 fts3SegReaderNextDocid(p, apSegment[j], 0, 0);

2919 j++;

2920 }

2921

2922 if( isColFilter ){

2923 fts3ColumnFilter(pFilter->iCol, 0, &pList, &nList);

2924 }

2925

2926 if( !isIgnoreEmpty \|\| nList>0 ){

2927

2928 /* Calculate the 'docid' delta value to write into the merged

2929 ** doclist. */

2930 sqlite3_int64 iDelta;

2931 if( p->bDescIdx && nDoclist>0 ){

2932 iDelta = iPrev - iDocid;

2933 }else{

2934 iDelta = iDocid - iPrev;

2935 }

2936 assert( iDelta>0 \|\| (nDoclist==0 && iDelta==iDocid) );

2937 assert( nDoclist>0 \|\| iDelta==iDocid );

2938

2939 nByte = sqlite3Fts3VarintLen(iDelta) + (isRequirePos?nList+1:0);

2940 if( nDoclist+nByte>pCsr->nBuffer ){

2941 char *aNew;

2942 pCsr->nBuffer = (nDoclist+nByte)*2;

2943 aNew = sqlite3_realloc(pCsr->aBuffer, pCsr->nBuffer);

2944 if( !aNew ){

2945 return SQLITE_NOMEM;

2946 }

2947 pCsr->aBuffer = aNew;

2948 }

2949

2950 if( isFirst ){

2951 char *a = &pCsr->aBuffer[nDoclist];

2952 int nWrite;

2953

2954 nWrite = sqlite3Fts3FirstFilter(iDelta, pList, nList, a);

2955 if( nWrite ){

2956 iPrev = iDocid;

2957 nDoclist += nWrite;

2958 }

2959 }else{

2960 nDoclist += sqlite3Fts3PutVarint(&pCsr->aBuffer[nDoclist], iDelta);

2961 iPrev = iDocid;

2962 if( isRequirePos ){

2963 memcpy(&pCsr->aBuffer[nDoclist], pList, nList);

2964 nDoclist += nList;

2965 pCsr->aBuffer[nDoclist++] = '\0';

2966 }

2967 }

2968 }

2969

2970 fts3SegReaderSort(apSegment, nMerge, j, xCmp);

2971 }

2972 if( nDoclist>0 ){

2973 pCsr->aDoclist = pCsr->aBuffer;

2974 pCsr->nDoclist = nDoclist;

2975 rc = SQLITE_ROW;

2976 }

2977 }

2978 pCsr->nAdvance = nMerge;

2979 }while( rc==SQLITE_OK );

2980

2981 return rc;

2982 }

2983

2984

2985 void sqlite3Fts3SegReaderFinish(

2986 Fts3MultiSegReader pCsr / Cursor object */

2987 ){

2988 if( pCsr ){

2989 int i;

2990 for(i=0; i<pCsr->nSegment; i++){

2991 sqlite3Fts3SegReaderFree(pCsr->apSegment[i]);

2992 }

2993 sqlite3_free(pCsr->apSegment);

2994 sqlite3_free(pCsr->aBuffer);

2995

2996 pCsr->nSegment = 0;

2997 pCsr->apSegment = 0;

2998 pCsr->aBuffer = 0;

2999 }

3000 }

3001

3002 /*

3003 ** Decode the "end_block" field, selected by column iCol of the SELECT

3004 ** statement passed as the first argument.

3005 **

3006 ** The "end_block" field may contain either an integer, or a text field

3007 ** containing the text representation of two non-negative integers separated

3008 ** by one or more space (0x20) characters. In the first case, set *piEndBlock

3009 ** to the integer value and *pnByte to zero before returning. In the second,

3010 ** set piEndBlock to the first value and pnByte to the second.

3011 */

3012 static void fts3ReadEndBlockField(

3013 sqlite3_stmt *pStmt,

3014 int iCol,

3015 i64 *piEndBlock,

3016 i64 *pnByte

3017 ){

3018 const unsigned char *zText = sqlite3_column_text(pStmt, iCol);

3019 if( zText ){

3020 int i;

3021 int iMul = 1;

3022 i64 iVal = 0;

3023 for(i=0; zText[i]>='0' && zText[i]<='9'; i++){

3024 iVal = iVal*10 + (zText[i] - '0');

3025 }

3026 *piEndBlock = iVal;

3027 while( zText[i]==' ' ) i++;

3028 iVal = 0;

3029 if( zText[i]=='-' ){

3030 i++;

3031 iMul = -1;

3032 }

3033 for(/* no-op */; zText[i]>='0' && zText[i]<='9'; i++){

3034 iVal = iVal*10 + (zText[i] - '0');

3035 }

3036 pnByte = (iVal (i64)iMul);

3037 }

3038 }

3039

3040

3041 /*

3042 ** A segment of size nByte bytes has just been written to absolute level

3043 ** iAbsLevel. Promote any segments that should be promoted as a result.

3044 */

3045 static int fts3PromoteSegments(

3046 Fts3Table p, / FTS table handle */

3047 sqlite3_int64 iAbsLevel, /* Absolute level just updated */

3048 sqlite3_int64 nByte /* Size of new segment at iAbsLevel */

3049 ){

3050 int rc = SQLITE_OK;

3051 sqlite3_stmt *pRange;

3052

3053 rc = fts3SqlStmt(p, SQL_SELECT_LEVEL_RANGE2, &pRange, 0);

3054

3055 if( rc==SQLITE_OK ){

3056 int bOk = 0;

3057 i64 iLast = (iAbsLevel/FTS3_SEGDIR_MAXLEVEL + 1) * FTS3_SEGDIR_MAXLEVEL - 1;

3058 i64 nLimit = (nByte*3)/2;

3059

3060 /* Loop through all entries in the %_segdir table corresponding to

3061 ** segments in this index on levels greater than iAbsLevel. If there is

3062 ** at least one such segment, and it is possible to determine that all

3063 ** such segments are smaller than nLimit bytes in size, they will be

3064 ** promoted to level iAbsLevel. */

3065 sqlite3_bind_int64(pRange, 1, iAbsLevel+1);

3066 sqlite3_bind_int64(pRange, 2, iLast);

3067 while( SQLITE_ROW==sqlite3_step(pRange) ){

3068 i64 nSize = 0, dummy;

3069 fts3ReadEndBlockField(pRange, 2, &dummy, &nSize);

3070 if( nSize<=0 \|\| nSize>nLimit ){

3071 /* If nSize==0, then the %_segdir.end_block field does not not

3072 ** contain a size value. This happens if it was written by an

3073 ** old version of FTS. In this case it is not possible to determine

3074 ** the size of the segment, and so segment promotion does not

3075 ** take place. */

3076 bOk = 0;

3077 break;

3078 }

3079 bOk = 1;

3080 }

3081 rc = sqlite3_reset(pRange);

3082

3083 if( bOk ){

3084 int iIdx = 0;

3085 sqlite3_stmt *pUpdate1;

3086 sqlite3_stmt *pUpdate2;

3087

3088 if( rc==SQLITE_OK ){

3089 rc = fts3SqlStmt(p, SQL_UPDATE_LEVEL_IDX, &pUpdate1, 0);

3090 }

3091 if( rc==SQLITE_OK ){

3092 rc = fts3SqlStmt(p, SQL_UPDATE_LEVEL, &pUpdate2, 0);

3093 }

3094

3095 if( rc==SQLITE_OK ){

3096

3097 /* Loop through all %_segdir entries for segments in this index with

3098 ** levels equal to or greater than iAbsLevel. As each entry is visited,

3099 ** updated it to set (level = -1) and (idx = N), where N is 0 for the

3100 ** oldest segment in the range, 1 for the next oldest, and so on.

3101 **

3102 ** In other words, move all segments being promoted to level -1,

3103 ** setting the "idx" fields as appropriate to keep them in the same

3104 ** order. The contents of level -1 (which is never used, except

3105 ** transiently here), will be moved back to level iAbsLevel below. */

3106 sqlite3_bind_int64(pRange, 1, iAbsLevel);

3107 while( SQLITE_ROW==sqlite3_step(pRange) ){

3108 sqlite3_bind_int(pUpdate1, 1, iIdx++);

3109 sqlite3_bind_int(pUpdate1, 2, sqlite3_column_int(pRange, 0));

3110 sqlite3_bind_int(pUpdate1, 3, sqlite3_column_int(pRange, 1));

3111 sqlite3_step(pUpdate1);

3112 rc = sqlite3_reset(pUpdate1);

3113 if( rc!=SQLITE_OK ){

3114 sqlite3_reset(pRange);

3115 break;

3116 }

3117 }

3118 }

3119 if( rc==SQLITE_OK ){

3120 rc = sqlite3_reset(pRange);

3121 }

3122

3123 /* Move level -1 to level iAbsLevel */

3124 if( rc==SQLITE_OK ){

3125 sqlite3_bind_int64(pUpdate2, 1, iAbsLevel);

3126 sqlite3_step(pUpdate2);

3127 rc = sqlite3_reset(pUpdate2);

3128 }

3129 }

3130 }

3131

3132

3133 return rc;

3134 }

3135

3136 /*

3137 ** Merge all level iLevel segments in the database into a single

3138 ** iLevel+1 segment. Or, if iLevel<0, merge all segments into a

3139 ** single segment with a level equal to the numerically largest level

3140 ** currently present in the database.

3141 **

3142 ** If this function is called with iLevel<0, but there is only one

3143 ** segment in the database, SQLITE_DONE is returned immediately.

3144 ** Otherwise, if successful, SQLITE_OK is returned. If an error occurs,

3145 ** an SQLite error code is returned.

3146 */

3147 static int fts3SegmentMerge(

3148 Fts3Table *p,

3149 int iLangid, /* Language id to merge */

3150 int iIndex, /* Index in p->aIndex[] to merge */

3151 int iLevel /* Level to merge */

3152 ){

3153 int rc; /* Return code */

3154 int iIdx = 0; /* Index of new segment */

3155 sqlite3_int64 iNewLevel = 0; /* Level/index to create new segment at */

3156 SegmentWriter pWriter = 0; / Used to write the new, merged, segment */

3157 Fts3SegFilter filter; /* Segment term filter condition */

3158 Fts3MultiSegReader csr; /* Cursor to iterate through level(s) */

3159 int bIgnoreEmpty = 0; /* True to ignore empty segments */

3160 i64 iMaxLevel = 0; /* Max level number for this index/langid */

3161

3162 assert( iLevel==FTS3_SEGCURSOR_ALL

3163 \|\| iLevel==FTS3_SEGCURSOR_PENDING

3164 \|\| iLevel>=0

3165 );

3166 assert( iLevel<FTS3_SEGDIR_MAXLEVEL );

3167 assert( iIndex>=0 && iIndex<p->nIndex );

3168

3169 rc = sqlite3Fts3SegReaderCursor(p, iLangid, iIndex, iLevel, 0, 0, 1, 0, &csr);

3170 if( rc!=SQLITE_OK \|\| csr.nSegment==0 ) goto finished;

3171

3172 if( iLevel!=FTS3_SEGCURSOR_PENDING ){

3173 rc = fts3SegmentMaxLevel(p, iLangid, iIndex, &iMaxLevel);

3174 if( rc!=SQLITE_OK ) goto finished;

3175 }

3176

3177 if( iLevel==FTS3_SEGCURSOR_ALL ){

3178 /* This call is to merge all segments in the database to a single

3179 ** segment. The level of the new segment is equal to the numerically

3180 ** greatest segment level currently present in the database for this

3181 ** index. The idx of the new segment is always 0. */

3182 if( csr.nSegment==1 ){

3183 rc = SQLITE_DONE;

3184 goto finished;

3185 }

3186 iNewLevel = iMaxLevel;

3187 bIgnoreEmpty = 1;

3188

3189 }else{

3190 /* This call is to merge all segments at level iLevel. find the next

3191 ** available segment index at level iLevel+1. The call to

3192 ** fts3AllocateSegdirIdx() will merge the segments at level iLevel+1 to

3193 ** a single iLevel+2 segment if necessary. */

3194 assert( FTS3_SEGCURSOR_PENDING==-1 );

3195 iNewLevel = getAbsoluteLevel(p, iLangid, iIndex, iLevel+1);

3196 rc = fts3AllocateSegdirIdx(p, iLangid, iIndex, iLevel+1, &iIdx);

3197 bIgnoreEmpty = (iLevel!=FTS3_SEGCURSOR_PENDING) && (iNewLevel>iMaxLevel);

3198 }

3199 if( rc!=SQLITE_OK ) goto finished;

3200

3201 assert( csr.nSegment>0 );

3202 assert( iNewLevel>=getAbsoluteLevel(p, iLangid, iIndex, 0) );

3203 assert( iNewLevel<getAbsoluteLevel(p, iLangid, iIndex,FTS3_SEGDIR_MAXLEVEL) );

3204

3205 memset(&filter, 0, sizeof(Fts3SegFilter));

3206 filter.flags = FTS3_SEGMENT_REQUIRE_POS;

3207 filter.flags \|= (bIgnoreEmpty ? FTS3_SEGMENT_IGNORE_EMPTY : 0);

3208

3209 rc = sqlite3Fts3SegReaderStart(p, &csr, &filter);

3210 while( SQLITE_OK==rc ){

3211 rc = sqlite3Fts3SegReaderStep(p, &csr);

3212 if( rc!=SQLITE_ROW ) break;

3213 rc = fts3SegWriterAdd(p, &pWriter, 1,

3214 csr.zTerm, csr.nTerm, csr.aDoclist, csr.nDoclist);

3215 }

3216 if( rc!=SQLITE_OK ) goto finished;

3217 assert( pWriter \|\| bIgnoreEmpty );

3218

3219 if( iLevel!=FTS3_SEGCURSOR_PENDING ){

3220 rc = fts3DeleteSegdir(

3221 p, iLangid, iIndex, iLevel, csr.apSegment, csr.nSegment

3222 );

3223 if( rc!=SQLITE_OK ) goto finished;

3224 }

3225 if( pWriter ){

3226 rc = fts3SegWriterFlush(p, pWriter, iNewLevel, iIdx);

3227 if( rc==SQLITE_OK ){

3228 if( iLevel==FTS3_SEGCURSOR_PENDING \|\| iNewLevel<iMaxLevel ){

3229 rc = fts3PromoteSegments(p, iNewLevel, pWriter->nLeafData);

3230 }

3231 }

3232 }

3233

3234 finished:

3235 fts3SegWriterFree(pWriter);

3236 sqlite3Fts3SegReaderFinish(&csr);

3237 return rc;

3238 }

3239

3240

3241 /*

3242 ** Flush the contents of pendingTerms to level 0 segments.

3243 */

3244 int sqlite3Fts3PendingTermsFlush(Fts3Table *p){

3245 int rc = SQLITE_OK;

3246 int i;

3247

3248 for(i=0; rc==SQLITE_OK && i<p->nIndex; i++){

3249 rc = fts3SegmentMerge(p, p->iPrevLangid, i, FTS3_SEGCURSOR_PENDING);

3250 if( rc==SQLITE_DONE ) rc = SQLITE_OK;

3251 }

3252 sqlite3Fts3PendingTermsClear(p);

3253

3254 /* Determine the auto-incr-merge setting if unknown. If enabled,

3255 ** estimate the number of leaf blocks of content to be written

3256 */

3257 if( rc==SQLITE_OK && p->bHasStat

3258 && p->nAutoincrmerge==0xff && p->nLeafAdd>0

3259 ){

3260 sqlite3_stmt *pStmt = 0;

3261 rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pStmt, 0);

3262 if( rc==SQLITE_OK ){

3263 sqlite3_bind_int(pStmt, 1, FTS_STAT_AUTOINCRMERGE);

3264 rc = sqlite3_step(pStmt);

3265 if( rc==SQLITE_ROW ){

3266 p->nAutoincrmerge = sqlite3_column_int(pStmt, 0);

3267 if( p->nAutoincrmerge==1 ) p->nAutoincrmerge = 8;

3268 }else if( rc==SQLITE_DONE ){

3269 p->nAutoincrmerge = 0;

3270 }

3271 rc = sqlite3_reset(pStmt);

3272 }

3273 }

3274 return rc;

3275 }

3276

3277 /*

3278 ** Encode N integers as varints into a blob.

3279 */

3280 static void fts3EncodeIntArray(

3281 int N, /* The number of integers to encode */

3282 u32 a, / The integer values */

3283 char zBuf, / Write the BLOB here */

3284 int pNBuf / Write number of bytes if zBuf[] used here */

3285 ){

3286 int i, j;

3287 for(i=j=0; i<N; i++){

3288 j += sqlite3Fts3PutVarint(&zBuf[j], (sqlite3_int64)a[i]);

3289 }

3290 *pNBuf = j;

3291 }

3292

3293 /*

3294 ** Decode a blob of varints into N integers

3295 */

3296 static void fts3DecodeIntArray(

3297 int N, /* The number of integers to decode */

3298 u32 a, / Write the integer values */

3299 const char zBuf, / The BLOB containing the varints */

3300 int nBuf /* size of the BLOB */

3301 ){

3302 int i, j;

3303 UNUSED_PARAMETER(nBuf);

3304 for(i=j=0; i<N; i++){

3305 sqlite3_int64 x;

3306 j += sqlite3Fts3GetVarint(&zBuf[j], &x);

3307 assert(j<=nBuf);

3308 a[i] = (u32)(x & 0xffffffff);

3309 }

3310 }

3311

3312 /*

3313 ** Insert the sizes (in tokens) for each column of the document

3314 ** with docid equal to p->iPrevDocid. The sizes are encoded as

3315 ** a blob of varints.

3316 */

3317 static void fts3InsertDocsize(

3318 int pRC, / Result code */

3319 Fts3Table p, / Table into which to insert */

3320 u32 aSz / Sizes of each column, in tokens */

3321 ){

3322 char pBlob; / The BLOB encoding of the document size */

3323 int nBlob; /* Number of bytes in the BLOB */

3324 sqlite3_stmt pStmt; / Statement used to insert the encoding */

3325 int rc; /* Result code from subfunctions */

3326

3327 if( *pRC ) return;

3328 pBlob = sqlite3_malloc( 10*p->nColumn );

3329 if( pBlob==0 ){

3330 *pRC = SQLITE_NOMEM;

3331 return;

3332 }

3333 fts3EncodeIntArray(p->nColumn, aSz, pBlob, &nBlob);

3334 rc = fts3SqlStmt(p, SQL_REPLACE_DOCSIZE, &pStmt, 0);

3335 if( rc ){

3336 sqlite3_free(pBlob);

3337 *pRC = rc;

3338 return;

3339 }

3340 sqlite3_bind_int64(pStmt, 1, p->iPrevDocid);

3341 sqlite3_bind_blob(pStmt, 2, pBlob, nBlob, sqlite3_free);

3342 sqlite3_step(pStmt);

3343 *pRC = sqlite3_reset(pStmt);

3344 }

3345

3346 /*

3347 ** Record 0 of the %_stat table contains a blob consisting of N varints,

3348 ** where N is the number of user defined columns in the fts3 table plus

3349 ** two. If nCol is the number of user defined columns, then values of the

3350 ** varints are set as follows:

3351 **

3352 ** Varint 0: Total number of rows in the table.

3353 **

3354 ** Varint 1..nCol: For each column, the total number of tokens stored in

3355 ** the column for all rows of the table.

3356 **

3357 ** Varint 1+nCol: The total size, in bytes, of all text values in all

3358 ** columns of all rows of the table.

3359 **

3360 */

3361 static void fts3UpdateDocTotals(

3362 int pRC, / The result code */

3363 Fts3Table p, / Table being updated */

3364 u32 aSzIns, / Size increases */

3365 u32 aSzDel, / Size decreases */

3366 int nChng /* Change in the number of documents */

3367 ){

3368 char pBlob; / Storage for BLOB written into %_stat */

3369 int nBlob; /* Size of BLOB written into %_stat */

3370 u32 a; / Array of integers that becomes the BLOB */

3371 sqlite3_stmt pStmt; / Statement for reading and writing */

3372 int i; /* Loop counter */

3373 int rc; /* Result code from subfunctions */

3374

3375 const int nStat = p->nColumn+2;

3376

3377 if( *pRC ) return;

3378 a = sqlite3_malloc( (sizeof(u32)+10)*nStat );

3379 if( a==0 ){

3380 *pRC = SQLITE_NOMEM;

3381 return;

3382 }

3383 pBlob = (char*)&a[nStat];

3384 rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pStmt, 0);

3385 if( rc ){

3386 sqlite3_free(a);

3387 *pRC = rc;

3388 return;

3389 }

3390 sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);

3391 if( sqlite3_step(pStmt)==SQLITE_ROW ){

3392 fts3DecodeIntArray(nStat, a,

3393 sqlite3_column_blob(pStmt, 0),

3394 sqlite3_column_bytes(pStmt, 0));

3395 }else{

3396 memset(a, 0, sizeof(u32)*(nStat) );

3397 }

3398 rc = sqlite3_reset(pStmt);

3399 if( rc!=SQLITE_OK ){

3400 sqlite3_free(a);

3401 *pRC = rc;

3402 return;

3403 }

3404 if( nChng<0 && a[0]<(u32)(-nChng) ){

3405 a[0] = 0;

3406 }else{

3407 a[0] += nChng;

3408 }

3409 for(i=0; i<p->nColumn+1; i++){

3410 u32 x = a[i+1];

3411 if( x+aSzIns[i] < aSzDel[i] ){

3412 x = 0;

3413 }else{

3414 x = x + aSzIns[i] - aSzDel[i];

3415 }

3416 a[i+1] = x;

3417 }

3418 fts3EncodeIntArray(nStat, a, pBlob, &nBlob);

3419 rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pStmt, 0);

3420 if( rc ){

3421 sqlite3_free(a);

3422 *pRC = rc;

3423 return;

3424 }

3425 sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);

3426 sqlite3_bind_blob(pStmt, 2, pBlob, nBlob, SQLITE_STATIC);

3427 sqlite3_step(pStmt);

3428 *pRC = sqlite3_reset(pStmt);

3429 sqlite3_free(a);

3430 }

3431

3432 /*

3433 ** Merge the entire database so that there is one segment for each

3434 ** iIndex/iLangid combination.

3435 */

3436 static int fts3DoOptimize(Fts3Table *p, int bReturnDone){

3437 int bSeenDone = 0;

3438 int rc;

3439 sqlite3_stmt *pAllLangid = 0;

3440

3441 rc = fts3SqlStmt(p, SQL_SELECT_ALL_LANGID, &pAllLangid, 0);

3442 if( rc==SQLITE_OK ){

3443 int rc2;

3444 sqlite3_bind_int(pAllLangid, 1, p->nIndex);

3445 while( sqlite3_step(pAllLangid)==SQLITE_ROW ){

3446 int i;

3447 int iLangid = sqlite3_column_int(pAllLangid, 0);

3448 for(i=0; rc==SQLITE_OK && i<p->nIndex; i++){

3449 rc = fts3SegmentMerge(p, iLangid, i, FTS3_SEGCURSOR_ALL);

3450 if( rc==SQLITE_DONE ){

3451 bSeenDone = 1;

3452 rc = SQLITE_OK;

3453 }

3454 }

3455 }

3456 rc2 = sqlite3_reset(pAllLangid);

3457 if( rc==SQLITE_OK ) rc = rc2;

3458 }

3459

3460 sqlite3Fts3SegmentsClose(p);

3461 sqlite3Fts3PendingTermsClear(p);

3462

3463 return (rc==SQLITE_OK && bReturnDone && bSeenDone) ? SQLITE_DONE : rc;

3464 }

3465

3466 /*

3467 ** This function is called when the user executes the following statement:

3468 **

3469 ** INSERT INTO <tbl>(<tbl>) VALUES('rebuild');

3470 **

3471 ** The entire FTS index is discarded and rebuilt. If the table is one

3472 ** created using the content=xxx option, then the new index is based on

3473 ** the current contents of the xxx table. Otherwise, it is rebuilt based

3474 ** on the contents of the %_content table.

3475 */

3476 static int fts3DoRebuild(Fts3Table *p){

3477 int rc; /* Return Code */

3478

3479 rc = fts3DeleteAll(p, 0);

3480 if( rc==SQLITE_OK ){

3481 u32 *aSz = 0;

3482 u32 *aSzIns = 0;

3483 u32 *aSzDel = 0;

3484 sqlite3_stmt *pStmt = 0;

3485 int nEntry = 0;

3486

3487 /* Compose and prepare an SQL statement to loop through the content table */

3488 char *zSql = sqlite3_mprintf("SELECT %s" , p->zReadExprlist);

3489 if( !zSql ){

3490 rc = SQLITE_NOMEM;

3491 }else{

3492 rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0);

3493 sqlite3_free(zSql);

3494 }

3495

3496 if( rc==SQLITE_OK ){

3497 int nByte = sizeof(u32) * (p->nColumn+1)*3;

3498 aSz = (u32 *)sqlite3_malloc(nByte);

3499 if( aSz==0 ){

3500 rc = SQLITE_NOMEM;

3501 }else{

3502 memset(aSz, 0, nByte);

3503 aSzIns = &aSz[p->nColumn+1];

3504 aSzDel = &aSzIns[p->nColumn+1];

3505 }

3506 }

3507

3508 while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){

3509 int iCol;

3510 int iLangid = langidFromSelect(p, pStmt);

3511 rc = fts3PendingTermsDocid(p, iLangid, sqlite3_column_int64(pStmt, 0));

3512 memset(aSz, 0, sizeof(aSz[0]) * (p->nColumn+1));

3513 for(iCol=0; rc==SQLITE_OK && iCol<p->nColumn; iCol++){

3514 if( p->abNotindexed[iCol]==0 ){

3515 const char z = (const char ) sqlite3_column_text(pStmt, iCol+1);

3516 rc = fts3PendingTermsAdd(p, iLangid, z, iCol, &aSz[iCol]);

3517 aSz[p->nColumn] += sqlite3_column_bytes(pStmt, iCol+1);

3518 }

3519 }

3520 if( p->bHasDocsize ){

3521 fts3InsertDocsize(&rc, p, aSz);

3522 }

3523 if( rc!=SQLITE_OK ){

3524 sqlite3_finalize(pStmt);

3525 pStmt = 0;

3526 }else{

3527 nEntry++;

3528 for(iCol=0; iCol<=p->nColumn; iCol++){

3529 aSzIns[iCol] += aSz[iCol];

3530 }

3531 }

3532 }

3533 if( p->bFts4 ){

3534 fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nEntry);

3535 }

3536 sqlite3_free(aSz);

3537

3538 if( pStmt ){

3539 int rc2 = sqlite3_finalize(pStmt);

3540 if( rc==SQLITE_OK ){

3541 rc = rc2;

3542 }

3543 }

3544 }

3545

3546 return rc;

3547 }

3548

3549

3550 /*

3551 ** This function opens a cursor used to read the input data for an

3552 ** incremental merge operation. Specifically, it opens a cursor to scan

3553 ** the oldest nSeg segments (idx=0 through idx=(nSeg-1)) in absolute

3554 ** level iAbsLevel.

3555 */

3556 static int fts3IncrmergeCsr(

3557 Fts3Table p, / FTS3 table handle */

3558 sqlite3_int64 iAbsLevel, /* Absolute level to open */

3559 int nSeg, /* Number of segments to merge */

3560 Fts3MultiSegReader pCsr / Cursor object to populate */

3561 ){

3562 int rc; /* Return Code */

3563 sqlite3_stmt pStmt = 0; / Statement used to read %_segdir entry */

3564 int nByte; /* Bytes allocated at pCsr->apSegment[] */

3565

3566 /* Allocate space for the Fts3MultiSegReader.aCsr[] array */

3567 memset(pCsr, 0, sizeof(*pCsr));

3568 nByte = sizeof(Fts3SegReader ) nSeg;

3569 pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(nByte);

3570

3571 if( pCsr->apSegment==0 ){

3572 rc = SQLITE_NOMEM;

3573 }else{

3574 memset(pCsr->apSegment, 0, nByte);

3575 rc = fts3SqlStmt(p, SQL_SELECT_LEVEL, &pStmt, 0);

3576 }

3577 if( rc==SQLITE_OK ){

3578 int i;

3579 int rc2;

3580 sqlite3_bind_int64(pStmt, 1, iAbsLevel);

3581 assert( pCsr->nSegment==0 );

3582 for(i=0; rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW && i<nSeg; i++){

3583 rc = sqlite3Fts3SegReaderNew(i, 0,

3584 sqlite3_column_int64(pStmt, 1), /* segdir.start_block */

3585 sqlite3_column_int64(pStmt, 2), /* segdir.leaves_end_block */

3586 sqlite3_column_int64(pStmt, 3), /* segdir.end_block */

3587 sqlite3_column_blob(pStmt, 4), /* segdir.root */

3588 sqlite3_column_bytes(pStmt, 4), /* segdir.root */

3589 &pCsr->apSegment[i]

3590 );

3591 pCsr->nSegment++;

3592 }

3593 rc2 = sqlite3_reset(pStmt);

3594 if( rc==SQLITE_OK ) rc = rc2;

3595 }

3596

3597 return rc;

3598 }

3599

3600 typedef struct IncrmergeWriter IncrmergeWriter;

3601 typedef struct NodeWriter NodeWriter;

3602 typedef struct Blob Blob;

3603 typedef struct NodeReader NodeReader;

3604

3605 /*

3606 ** An instance of the following structure is used as a dynamic buffer

3607 ** to build up nodes or other blobs of data in.

3608 **

3609 ** The function blobGrowBuffer() is used to extend the allocation.

3610 */

3611 struct Blob {

3612 char a; / Pointer to allocation */

3613 int n; /* Number of valid bytes of data in a[] */

3614 int nAlloc; /* Allocated size of a[] (nAlloc>=n) */

3615 };

3616

3617 /*

3618 ** This structure is used to build up buffers containing segment b-tree

3619 ** nodes (blocks).

3620 */

3621 struct NodeWriter {

3622 sqlite3_int64 iBlock; /* Current block id */

3623 Blob key; /* Last key written to the current block */

3624 Blob block; /* Current block image */

3625 };

3626

3627 /*

3628 ** An object of this type contains the state required to create or append

3629 ** to an appendable b-tree segment.

3630 */

3631 struct IncrmergeWriter {

3632 int nLeafEst; /* Space allocated for leaf blocks */

3633 int nWork; /* Number of leaf pages flushed */

3634 sqlite3_int64 iAbsLevel; /* Absolute level of input segments */

3635 int iIdx; /* Index of output segment in iAbsLevel+1 */

3636 sqlite3_int64 iStart; /* Block number of first allocated block */

3637 sqlite3_int64 iEnd; /* Block number of last allocated block */

3638 sqlite3_int64 nLeafData; /* Bytes of leaf page data so far */

3639 u8 bNoLeafData; /* If true, store 0 for segment size */

3640 NodeWriter aNodeWriter[FTS_MAX_APPENDABLE_HEIGHT];

3641 };

3642

3643 /*

3644 ** An object of the following type is used to read data from a single

3645 ** FTS segment node. See the following functions:

3646 **

3647 ** nodeReaderInit()

3648 ** nodeReaderNext()

3649 ** nodeReaderRelease()

3650 */

3651 struct NodeReader {

3652 const char *aNode;

3653 int nNode;

3654 int iOff; /* Current offset within aNode[] */

3655

3656 /* Output variables. Containing the current node entry. */

3657 sqlite3_int64 iChild; /* Pointer to child node */

3658 Blob term; /* Current term */

3659 const char aDoclist; / Pointer to doclist */

3660 int nDoclist; /* Size of doclist in bytes */

3661 };

3662

3663 /*

3664 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.

3665 ** Otherwise, if the allocation at pBlob->a is not already at least nMin

3666 ** bytes in size, extend (realloc) it to be so.

3667 **

3668 ** If an OOM error occurs, set *pRc to SQLITE_NOMEM and leave pBlob->a

3669 ** unmodified. Otherwise, if the allocation succeeds, update pBlob->nAlloc

3670 ** to reflect the new size of the pBlob->a[] buffer.

3671 */

3672 static void blobGrowBuffer(Blob pBlob, int nMin, int pRc){

3673 if( *pRc==SQLITE_OK && nMin>pBlob->nAlloc ){

3674 int nAlloc = nMin;

3675 char a = (char )sqlite3_realloc(pBlob->a, nAlloc);

3676 if( a ){

3677 pBlob->nAlloc = nAlloc;

3678 pBlob->a = a;

3679 }else{

3680 *pRc = SQLITE_NOMEM;

3681 }

3682 }

3683 }

3684

3685 /*

3686 ** Attempt to advance the node-reader object passed as the first argument to

3687 ** the next entry on the node.

3688 **

3689 ** Return an error code if an error occurs (SQLITE_NOMEM is possible).

3690 ** Otherwise return SQLITE_OK. If there is no next entry on the node

3691 ** (e.g. because the current entry is the last) set NodeReader->aNode to

3692 ** NULL to indicate EOF. Otherwise, populate the NodeReader structure output

3693 ** variables for the new entry.

3694 */

3695 static int nodeReaderNext(NodeReader *p){

3696 int bFirst = (p->term.n==0); /* True for first term on the node */

3697 int nPrefix = 0; /* Bytes to copy from previous term */

3698 int nSuffix = 0; /* Bytes to append to the prefix */

3699 int rc = SQLITE_OK; /* Return code */

3700

3701 assert( p->aNode );

3702 if( p->iChild && bFirst==0 ) p->iChild++;

3703 if( p->iOff>=p->nNode ){

3704 /* EOF */

3705 p->aNode = 0;

3706 }else{

3707 if( bFirst==0 ){

3708 p->iOff += fts3GetVarint32(&p->aNode[p->iOff], &nPrefix);

3709 }

3710 p->iOff += fts3GetVarint32(&p->aNode[p->iOff], &nSuffix);

3711

3712 blobGrowBuffer(&p->term, nPrefix+nSuffix, &rc);

3713 if( rc==SQLITE_OK ){

3714 memcpy(&p->term.a[nPrefix], &p->aNode[p->iOff], nSuffix);

3715 p->term.n = nPrefix+nSuffix;

3716 p->iOff += nSuffix;

3717 if( p->iChild==0 ){

3718 p->iOff += fts3GetVarint32(&p->aNode[p->iOff], &p->nDoclist);

3719 p->aDoclist = &p->aNode[p->iOff];

3720 p->iOff += p->nDoclist;

3721 }

3722 }

3723 }

3724

3725 assert( p->iOff<=p->nNode );

3726

3727 return rc;

3728 }

3729

3730 /*

3731 ** Release all dynamic resources held by node-reader object *p.

3732 */

3733 static void nodeReaderRelease(NodeReader *p){

3734 sqlite3_free(p->term.a);

3735 }

3736

3737 /*

3738 ** Initialize a node-reader object to read the node in buffer aNode/nNode.

3739 **

3740 ** If successful, SQLITE_OK is returned and the NodeReader object set to

3741 ** point to the first entry on the node (if any). Otherwise, an SQLite

3742 ** error code is returned.

3743 */

3744 static int nodeReaderInit(NodeReader p, const char aNode, int nNode){

3745 memset(p, 0, sizeof(NodeReader));

3746 p->aNode = aNode;

3747 p->nNode = nNode;

3748

3749 /* Figure out if this is a leaf or an internal node. */

3750 if( p->aNode[0] ){

3751 /* An internal node. */

3752 p->iOff = 1 + sqlite3Fts3GetVarint(&p->aNode[1], &p->iChild);

3753 }else{

3754 p->iOff = 1;

3755 }

3756

3757 return nodeReaderNext(p);

3758 }

3759

3760 /*

3761 ** This function is called while writing an FTS segment each time a leaf o

3762 ** node is finished and written to disk. The key (zTerm/nTerm) is guaranteed

3763 ** to be greater than the largest key on the node just written, but smaller

3764 ** than or equal to the first key that will be written to the next leaf

3765 ** node.

3766 **

3767 ** The block id of the leaf node just written to disk may be found in

3768 ** (pWriter->aNodeWriter[0].iBlock) when this function is called.

3769 */

3770 static int fts3IncrmergePush(

3771 Fts3Table p, / Fts3 table handle */

3772 IncrmergeWriter pWriter, / Writer object */

3773 const char zTerm, / Term to write to internal node */

3774 int nTerm /* Bytes at zTerm */

3775 ){

3776 sqlite3_int64 iPtr = pWriter->aNodeWriter[0].iBlock;

3777 int iLayer;

3778

3779 assert( nTerm>0 );

3780 for(iLayer=1; ALWAYS(iLayer<FTS_MAX_APPENDABLE_HEIGHT); iLayer++){

3781 sqlite3_int64 iNextPtr = 0;

3782 NodeWriter *pNode = &pWriter->aNodeWriter[iLayer];

3783 int rc = SQLITE_OK;

3784 int nPrefix;

3785 int nSuffix;

3786 int nSpace;

3787

3788 /* Figure out how much space the key will consume if it is written to

3789 ** the current node of layer iLayer. Due to the prefix compression,

3790 ** the space required changes depending on which node the key is to

3791 ** be added to. */

3792 nPrefix = fts3PrefixCompress(pNode->key.a, pNode->key.n, zTerm, nTerm);

3793 nSuffix = nTerm - nPrefix;

3794 nSpace = sqlite3Fts3VarintLen(nPrefix);

3795 nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;

3796

3797 if( pNode->key.n==0 \|\| (pNode->block.n + nSpace)<=p->nNodeSize ){

3798 /* If the current node of layer iLayer contains zero keys, or if adding

3799 ** the key to it will not cause it to grow to larger than nNodeSize

3800 ** bytes in size, write the key here. */

3801

3802 Blob *pBlk = &pNode->block;

3803 if( pBlk->n==0 ){

3804 blobGrowBuffer(pBlk, p->nNodeSize, &rc);

3805 if( rc==SQLITE_OK ){

3806 pBlk->a[0] = (char)iLayer;

3807 pBlk->n = 1 + sqlite3Fts3PutVarint(&pBlk->a[1], iPtr);

3808 }

3809 }

3810 blobGrowBuffer(pBlk, pBlk->n + nSpace, &rc);

3811 blobGrowBuffer(&pNode->key, nTerm, &rc);

3812

3813 if( rc==SQLITE_OK ){

3814 if( pNode->key.n ){

3815 pBlk->n += sqlite3Fts3PutVarint(&pBlk->a[pBlk->n], nPrefix);

3816 }

3817 pBlk->n += sqlite3Fts3PutVarint(&pBlk->a[pBlk->n], nSuffix);

3818 memcpy(&pBlk->a[pBlk->n], &zTerm[nPrefix], nSuffix);

3819 pBlk->n += nSuffix;

3820

3821 memcpy(pNode->key.a, zTerm, nTerm);

3822 pNode->key.n = nTerm;

3823 }

3824 }else{

3825 /* Otherwise, flush the current node of layer iLayer to disk.

3826 ** Then allocate a new, empty sibling node. The key will be written

3827 ** into the parent of this node. */

3828 rc = fts3WriteSegment(p, pNode->iBlock, pNode->block.a, pNode->block.n);

3829

3830 assert( pNode->block.nAlloc>=p->nNodeSize );

3831 pNode->block.a[0] = (char)iLayer;

3832 pNode->block.n = 1 + sqlite3Fts3PutVarint(&pNode->block.a[1], iPtr+1);

3833

3834 iNextPtr = pNode->iBlock;

3835 pNode->iBlock++;

3836 pNode->key.n = 0;

3837 }

3838

3839 if( rc!=SQLITE_OK \|\| iNextPtr==0 ) return rc;

3840 iPtr = iNextPtr;

3841 }

3842

3843 assert( 0 );

3844 return 0;

3845 }

3846

3847 /*

3848 ** Append a term and (optionally) doclist to the FTS segment node currently

3849 ** stored in blob *pNode. The node need not contain any terms, but the

3850 ** header must be written before this function is called.

3851 **

3852 ** A node header is a single 0x00 byte for a leaf node, or a height varint

3853 ** followed by the left-hand-child varint for an internal node.

3854 **

3855 ** The term to be appended is passed via arguments zTerm/nTerm. For a

3856 ** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal

3857 ** node, both aDoclist and nDoclist must be passed 0.

3858 **

3859 ** If the size of the value in blob pPrev is zero, then this is the first

3860 ** term written to the node. Otherwise, pPrev contains a copy of the

3861 ** previous term. Before this function returns, it is updated to contain a

3862 ** copy of zTerm/nTerm.

3863 **

3864 ** It is assumed that the buffer associated with pNode is already large

3865 ** enough to accommodate the new entry. The buffer associated with pPrev

3866 ** is extended by this function if requrired.

3867 **

3868 ** If an error (i.e. OOM condition) occurs, an SQLite error code is

3869 ** returned. Otherwise, SQLITE_OK.

3870 */

3871 static int fts3AppendToNode(

3872 Blob pNode, / Current node image to append to */

3873 Blob pPrev, / Buffer containing previous term written */

3874 const char zTerm, / New term to write */

3875 int nTerm, /* Size of zTerm in bytes */

3876 const char aDoclist, / Doclist (or NULL) to write */

3877 int nDoclist /* Size of aDoclist in bytes */

3878 ){

3879 int rc = SQLITE_OK; /* Return code */

3880 int bFirst = (pPrev->n==0); /* True if this is the first term written */

3881 int nPrefix; /* Size of term prefix in bytes */

3882 int nSuffix; /* Size of term suffix in bytes */

3883

3884 /* Node must have already been started. There must be a doclist for a

3885 ** leaf node, and there must not be a doclist for an internal node. */

3886 assert( pNode->n>0 );

3887 assert( (pNode->a[0]=='\0')==(aDoclist!=0) );

3888

3889 blobGrowBuffer(pPrev, nTerm, &rc);

3890 if( rc!=SQLITE_OK ) return rc;

3891

3892 nPrefix = fts3PrefixCompress(pPrev->a, pPrev->n, zTerm, nTerm);

3893 nSuffix = nTerm - nPrefix;

3894 memcpy(pPrev->a, zTerm, nTerm);

3895 pPrev->n = nTerm;

3896

3897 if( bFirst==0 ){

3898 pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nPrefix);

3899 }

3900 pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nSuffix);

3901 memcpy(&pNode->a[pNode->n], &zTerm[nPrefix], nSuffix);

3902 pNode->n += nSuffix;

3903

3904 if( aDoclist ){

3905 pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nDoclist);

3906 memcpy(&pNode->a[pNode->n], aDoclist, nDoclist);

3907 pNode->n += nDoclist;

3908 }

3909

3910 assert( pNode->n<=pNode->nAlloc );

3911

3912 return SQLITE_OK;

3913 }

3914

3915 /*

3916 ** Append the current term and doclist pointed to by cursor pCsr to the

3917 ** appendable b-tree segment opened for writing by pWriter.

3918 **

3919 ** Return SQLITE_OK if successful, or an SQLite error code otherwise.

3920 */

3921 static int fts3IncrmergeAppend(

3922 Fts3Table p, / Fts3 table handle */

3923 IncrmergeWriter pWriter, / Writer object */

3924 Fts3MultiSegReader pCsr / Cursor containing term and doclist */

3925 ){

3926 const char *zTerm = pCsr->zTerm;

3927 int nTerm = pCsr->nTerm;

3928 const char *aDoclist = pCsr->aDoclist;

3929 int nDoclist = pCsr->nDoclist;

3930 int rc = SQLITE_OK; /* Return code */

3931 int nSpace; /* Total space in bytes required on leaf */

3932 int nPrefix; /* Size of prefix shared with previous term */

3933 int nSuffix; /* Size of suffix (nTerm - nPrefix) */

3934 NodeWriter pLeaf; / Object used to write leaf nodes */

3935

3936 pLeaf = &pWriter->aNodeWriter[0];

3937 nPrefix = fts3PrefixCompress(pLeaf->key.a, pLeaf->key.n, zTerm, nTerm);

3938 nSuffix = nTerm - nPrefix;

3939

3940 nSpace = sqlite3Fts3VarintLen(nPrefix);

3941 nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;

3942 nSpace += sqlite3Fts3VarintLen(nDoclist) + nDoclist;

3943

3944 /* If the current block is not empty, and if adding this term/doclist

3945 ** to the current block would make it larger than Fts3Table.nNodeSize

3946 ** bytes, write this block out to the database. */

3947 if( pLeaf->block.n>0 && (pLeaf->block.n + nSpace)>p->nNodeSize ){

3948 rc = fts3WriteSegment(p, pLeaf->iBlock, pLeaf->block.a, pLeaf->block.n);

3949 pWriter->nWork++;

3950

3951 /* Add the current term to the parent node. The term added to the

3952 ** parent must:

3953 **

3954 ** a) be greater than the largest term on the leaf node just written

3955 ** to the database (still available in pLeaf->key), and

3956 **

3957 ** b) be less than or equal to the term about to be added to the new

3958 ** leaf node (zTerm/nTerm).

3959 **

3960 ** In other words, it must be the prefix of zTerm 1 byte longer than

3961 ** the common prefix (if any) of zTerm and pWriter->zTerm.

3962 */

3963 if( rc==SQLITE_OK ){

3964 rc = fts3IncrmergePush(p, pWriter, zTerm, nPrefix+1);

3965 }

3966

3967 /* Advance to the next output block */

3968 pLeaf->iBlock++;

3969 pLeaf->key.n = 0;

3970 pLeaf->block.n = 0;

3971

3972 nSuffix = nTerm;

3973 nSpace = 1;

3974 nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;

3975 nSpace += sqlite3Fts3VarintLen(nDoclist) + nDoclist;

3976 }

3977

3978 pWriter->nLeafData += nSpace;

3979 blobGrowBuffer(&pLeaf->block, pLeaf->block.n + nSpace, &rc);

3980 if( rc==SQLITE_OK ){

3981 if( pLeaf->block.n==0 ){

3982 pLeaf->block.n = 1;

3983 pLeaf->block.a[0] = '\0';

3984 }

3985 rc = fts3AppendToNode(

3986 &pLeaf->block, &pLeaf->key, zTerm, nTerm, aDoclist, nDoclist

3987 );

3988 }

3989

3990 return rc;

3991 }

3992

3993 /*

3994 ** This function is called to release all dynamic resources held by the

3995 ** merge-writer object pWriter, and if no error has occurred, to flush

3996 ** all outstanding node buffers held by pWriter to disk.

3997 **

3998 ** If *pRc is not SQLITE_OK when this function is called, then no attempt

3999 ** is made to write any data to disk. Instead, this function serves only

4000 ** to release outstanding resources.

4001 **

4002 ** Otherwise, if *pRc is initially SQLITE_OK and an error occurs while

4003 ** flushing buffers to disk, *pRc is set to an SQLite error code before

4004 ** returning.

4005 */

4006 static void fts3IncrmergeRelease(

4007 Fts3Table p, / FTS3 table handle */

4008 IncrmergeWriter pWriter, / Merge-writer object */

4009 int pRc / IN/OUT: Error code */

4010 ){

4011 int i; /* Used to iterate through non-root layers */

4012 int iRoot; /* Index of root in pWriter->aNodeWriter */

4013 NodeWriter pRoot; / NodeWriter for root node */

4014 int rc = pRc; / Error code */

4015

4016 /* Set iRoot to the index in pWriter->aNodeWriter[] of the output segment

4017 ** root node. If the segment fits entirely on a single leaf node, iRoot

4018 ** will be set to 0. If the root node is the parent of the leaves, iRoot

4019 ** will be 1. And so on. */

4020 for(iRoot=FTS_MAX_APPENDABLE_HEIGHT-1; iRoot>=0; iRoot--){

4021 NodeWriter *pNode = &pWriter->aNodeWriter[iRoot];

4022 if( pNode->block.n>0 ) break;

4023 assert( *pRc \|\| pNode->block.nAlloc==0 );

4024 assert( *pRc \|\| pNode->key.nAlloc==0 );

4025 sqlite3_free(pNode->block.a);

4026 sqlite3_free(pNode->key.a);

4027 }

4028

4029 /* Empty output segment. This is a no-op. */

4030 if( iRoot<0 ) return;

4031

4032 /* The entire output segment fits on a single node. Normally, this means

4033 ** the node would be stored as a blob in the "root" column of the %_segdir

4034 ** table. However, this is not permitted in this case. The problem is that

4035 ** space has already been reserved in the %_segments table, and so the

4036 ** start_block and end_block fields of the %_segdir table must be populated.

4037 ** And, by design or by accident, released versions of FTS cannot handle

4038 ** segments that fit entirely on the root node with start_block!=0.

4039 **

4040 ** Instead, create a synthetic root node that contains nothing but a

4041 ** pointer to the single content node. So that the segment consists of a

4042 ** single leaf and a single interior (root) node.

4043 **

4044 ** Todo: Better might be to defer allocating space in the %_segments

4045 ** table until we are sure it is needed.

4046 */

4047 if( iRoot==0 ){

4048 Blob *pBlock = &pWriter->aNodeWriter[1].block;

4049 blobGrowBuffer(pBlock, 1 + FTS3_VARINT_MAX, &rc);

4050 if( rc==SQLITE_OK ){

4051 pBlock->a[0] = 0x01;

4052 pBlock->n = 1 + sqlite3Fts3PutVarint(

4053 &pBlock->a[1], pWriter->aNodeWriter[0].iBlock

4054 );

4055 }

4056 iRoot = 1;

4057 }

4058 pRoot = &pWriter->aNodeWriter[iRoot];

4059

4060 /* Flush all currently outstanding nodes to disk. */

4061 for(i=0; i<iRoot; i++){

4062 NodeWriter *pNode = &pWriter->aNodeWriter[i];

4063 if( pNode->block.n>0 && rc==SQLITE_OK ){

4064 rc = fts3WriteSegment(p, pNode->iBlock, pNode->block.a, pNode->block.n);

4065 }

4066 sqlite3_free(pNode->block.a);

4067 sqlite3_free(pNode->key.a);

4068 }

4069

4070 /* Write the %_segdir record. */

4071 if( rc==SQLITE_OK ){

4072 rc = fts3WriteSegdir(p,

4073 pWriter->iAbsLevel+1, /* level */

4074 pWriter->iIdx, /* idx */

4075 pWriter->iStart, /* start_block */

4076 pWriter->aNodeWriter[0].iBlock, /* leaves_end_block */

4077 pWriter->iEnd, /* end_block */

4078 (pWriter->bNoLeafData==0 ? pWriter->nLeafData : 0), /* end_block */

4079 pRoot->block.a, pRoot->block.n /* root */

4080 );

4081 }

4082 sqlite3_free(pRoot->block.a);

4083 sqlite3_free(pRoot->key.a);

4084

4085 *pRc = rc;

4086 }

4087

4088 /*

4089 ** Compare the term in buffer zLhs (size in bytes nLhs) with that in

4090 ** zRhs (size in bytes nRhs) using memcmp. If one term is a prefix of

4091 ** the other, it is considered to be smaller than the other.

4092 **

4093 ** Return -ve if zLhs is smaller than zRhs, 0 if it is equal, or +ve

4094 ** if it is greater.

4095 */

4096 static int fts3TermCmp(

4097 const char zLhs, int nLhs, / LHS of comparison */

4098 const char zRhs, int nRhs / RHS of comparison */

4099 ){

4100 int nCmp = MIN(nLhs, nRhs);

4101 int res;

4102

4103 res = memcmp(zLhs, zRhs, nCmp);

4104 if( res==0 ) res = nLhs - nRhs;

4105

4106 return res;

4107 }

4108

4109

4110 /*

4111 ** Query to see if the entry in the %_segments table with blockid iEnd is

4112 ** NULL. If no error occurs and the entry is NULL, set *pbRes 1 before

4113 ** returning. Otherwise, set *pbRes to 0.

4114 **

4115 ** Or, if an error occurs while querying the database, return an SQLite

4116 ** error code. The final value of *pbRes is undefined in this case.

4117 **

4118 ** This is used to test if a segment is an "appendable" segment. If it

4119 ** is, then a NULL entry has been inserted into the %_segments table

4120 ** with blockid %_segdir.end_block.

4121 */

4122 static int fts3IsAppendable(Fts3Table p, sqlite3_int64 iEnd, int pbRes){

4123 int bRes = 0; /* Result to set pbRes to /

4124 sqlite3_stmt pCheck = 0; / Statement to query database with */

4125 int rc; /* Return code */

4126

4127 rc = fts3SqlStmt(p, SQL_SEGMENT_IS_APPENDABLE, &pCheck, 0);

4128 if( rc==SQLITE_OK ){

4129 sqlite3_bind_int64(pCheck, 1, iEnd);

4130 if( SQLITE_ROW==sqlite3_step(pCheck) ) bRes = 1;

4131 rc = sqlite3_reset(pCheck);

4132 }

4133

4134 *pbRes = bRes;

4135 return rc;

4136 }

4137

4138 /*

4139 ** This function is called when initializing an incremental-merge operation.

4140 ** It checks if the existing segment with index value iIdx at absolute level

4141 ** (iAbsLevel+1) can be appended to by the incremental merge. If it can, the

4142 ** merge-writer object *pWriter is initialized to write to it.

4143 **

4144 ** An existing segment can be appended to by an incremental merge if:

4145 **

4146 ** * It was initially created as an appendable segment (with all required

4147 ** space pre-allocated), and

4148 **

4149 ** * The first key read from the input (arguments zKey and nKey) is

4150 ** greater than the largest key currently stored in the potential

4151 ** output segment.

4152 */

4153 static int fts3IncrmergeLoad(

4154 Fts3Table p, / Fts3 table handle */

4155 sqlite3_int64 iAbsLevel, /* Absolute level of input segments */

4156 int iIdx, /* Index of candidate output segment */

4157 const char zKey, / First key to write */

4158 int nKey, /* Number of bytes in nKey */

4159 IncrmergeWriter pWriter / Populate this object */

4160 ){

4161 int rc; /* Return code */

4162 sqlite3_stmt pSelect = 0; / SELECT to read %_segdir entry */

4163

4164 rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pSelect, 0);

4165 if( rc==SQLITE_OK ){

4166 sqlite3_int64 iStart = 0; /* Value of %_segdir.start_block */

4167 sqlite3_int64 iLeafEnd = 0; /* Value of %_segdir.leaves_end_block */

4168 sqlite3_int64 iEnd = 0; /* Value of %_segdir.end_block */

4169 const char aRoot = 0; / Pointer to %_segdir.root buffer */

4170 int nRoot = 0; /* Size of aRoot[] in bytes */

4171 int rc2; /* Return code from sqlite3_reset() */

4172 int bAppendable = 0; /* Set to true if segment is appendable */

4173

4174 /* Read the %_segdir entry for index iIdx absolute level (iAbsLevel+1) */

4175 sqlite3_bind_int64(pSelect, 1, iAbsLevel+1);

4176 sqlite3_bind_int(pSelect, 2, iIdx);

4177 if( sqlite3_step(pSelect)==SQLITE_ROW ){

4178 iStart = sqlite3_column_int64(pSelect, 1);

4179 iLeafEnd = sqlite3_column_int64(pSelect, 2);

4180 fts3ReadEndBlockField(pSelect, 3, &iEnd, &pWriter->nLeafData);

4181 if( pWriter->nLeafData<0 ){

4182 pWriter->nLeafData = pWriter->nLeafData * -1;

4183 }

4184 pWriter->bNoLeafData = (pWriter->nLeafData==0);

4185 nRoot = sqlite3_column_bytes(pSelect, 4);

4186 aRoot = sqlite3_column_blob(pSelect, 4);

4187 }else{

4188 return sqlite3_reset(pSelect);

4189 }

4190

4191 /* Check for the zero-length marker in the %_segments table */

4192 rc = fts3IsAppendable(p, iEnd, &bAppendable);

4193

4194 /* Check that zKey/nKey is larger than the largest key the candidate */

4195 if( rc==SQLITE_OK && bAppendable ){

4196 char *aLeaf = 0;

4197 int nLeaf = 0;

4198

4199 rc = sqlite3Fts3ReadBlock(p, iLeafEnd, &aLeaf, &nLeaf, 0);

4200 if( rc==SQLITE_OK ){

4201 NodeReader reader;

4202 for(rc = nodeReaderInit(&reader, aLeaf, nLeaf);

4203 rc==SQLITE_OK && reader.aNode;

4204 rc = nodeReaderNext(&reader)

4205 ){

4206 assert( reader.aNode );

4207 }

4208 if( fts3TermCmp(zKey, nKey, reader.term.a, reader.term.n)<=0 ){

4209 bAppendable = 0;

4210 }

4211 nodeReaderRelease(&reader);

4212 }

4213 sqlite3_free(aLeaf);

4214 }

4215

4216 if( rc==SQLITE_OK && bAppendable ){

4217 /* It is possible to append to this segment. Set up the IncrmergeWriter

4218 ** object to do so. */

4219 int i;

4220 int nHeight = (int)aRoot[0];

4221 NodeWriter *pNode;

4222

4223 pWriter->nLeafEst = (int)((iEnd - iStart) + 1)/FTS_MAX_APPENDABLE_HEIGHT;

4224 pWriter->iStart = iStart;

4225 pWriter->iEnd = iEnd;

4226 pWriter->iAbsLevel = iAbsLevel;

4227 pWriter->iIdx = iIdx;

4228

4229 for(i=nHeight+1; i<FTS_MAX_APPENDABLE_HEIGHT; i++){

4230 pWriter->aNodeWriter[i].iBlock = pWriter->iStart + i*pWriter->nLeafEst;

4231 }

4232

4233 pNode = &pWriter->aNodeWriter[nHeight];

4234 pNode->iBlock = pWriter->iStart + pWriter->nLeafEst*nHeight;

4235 blobGrowBuffer(&pNode->block, MAX(nRoot, p->nNodeSize), &rc);

4236 if( rc==SQLITE_OK ){

4237 memcpy(pNode->block.a, aRoot, nRoot);

4238 pNode->block.n = nRoot;

4239 }

4240

4241 for(i=nHeight; i>=0 && rc==SQLITE_OK; i--){

4242 NodeReader reader;

4243 pNode = &pWriter->aNodeWriter[i];

4244

4245 rc = nodeReaderInit(&reader, pNode->block.a, pNode->block.n);

4246 while( reader.aNode && rc==SQLITE_OK ) rc = nodeReaderNext(&reader);

4247 blobGrowBuffer(&pNode->key, reader.term.n, &rc);

4248 if( rc==SQLITE_OK ){

4249 memcpy(pNode->key.a, reader.term.a, reader.term.n);

4250 pNode->key.n = reader.term.n;

4251 if( i>0 ){

4252 char *aBlock = 0;

4253 int nBlock = 0;

4254 pNode = &pWriter->aNodeWriter[i-1];

4255 pNode->iBlock = reader.iChild;

4256 rc = sqlite3Fts3ReadBlock(p, reader.iChild, &aBlock, &nBlock, 0);

4257 blobGrowBuffer(&pNode->block, MAX(nBlock, p->nNodeSize), &rc);

4258 if( rc==SQLITE_OK ){

4259 memcpy(pNode->block.a, aBlock, nBlock);

4260 pNode->block.n = nBlock;

4261 }

4262 sqlite3_free(aBlock);

4263 }

4264 }

4265 nodeReaderRelease(&reader);

4266 }

4267 }

4268

4269 rc2 = sqlite3_reset(pSelect);

4270 if( rc==SQLITE_OK ) rc = rc2;

4271 }

4272

4273 return rc;

4274 }

4275

4276 /*

4277 ** Determine the largest segment index value that exists within absolute

4278 ** level iAbsLevel+1. If no error occurs, set *piIdx to this value plus

4279 ** one before returning SQLITE_OK. Or, if there are no segments at all

4280 ** within level iAbsLevel, set *piIdx to zero.

4281 **

4282 ** If an error occurs, return an SQLite error code. The final value of

4283 ** *piIdx is undefined in this case.

4284 */

4285 static int fts3IncrmergeOutputIdx(

4286 Fts3Table p, / FTS Table handle */

4287 sqlite3_int64 iAbsLevel, /* Absolute index of input segments */

4288 int piIdx / OUT: Next free index at iAbsLevel+1 */

4289 ){

4290 int rc;

4291 sqlite3_stmt pOutputIdx = 0; / SQL used to find output index */

4292

4293 rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pOutputIdx, 0);

4294 if( rc==SQLITE_OK ){

4295 sqlite3_bind_int64(pOutputIdx, 1, iAbsLevel+1);

4296 sqlite3_step(pOutputIdx);

4297 *piIdx = sqlite3_column_int(pOutputIdx, 0);

4298 rc = sqlite3_reset(pOutputIdx);

4299 }

4300

4301 return rc;

4302 }

4303

4304 /*

4305 ** Allocate an appendable output segment on absolute level iAbsLevel+1

4306 ** with idx value iIdx.

4307 **

4308 ** In the %_segdir table, a segment is defined by the values in three

4309 ** columns:

4310 **

4311 ** start_block

4312 ** leaves_end_block

4313 ** end_block

4314 **

4315 ** When an appendable segment is allocated, it is estimated that the

4316 ** maximum number of leaf blocks that may be required is the sum of the

4317 ** number of leaf blocks consumed by the input segments, plus the number

4318 ** of input segments, multiplied by two. This value is stored in stack

4319 ** variable nLeafEst.

4320 **

4321 ** A total of 16*nLeafEst blocks are allocated when an appendable segment

4322 ** is created ((1 + end_block - start_block)==16*nLeafEst). The contiguous

4323 ** array of leaf nodes starts at the first block allocated. The array

4324 ** of interior nodes that are parents of the leaf nodes start at block

4325 ** (start_block + (1 + end_block - start_block) / 16). And so on.

4326 **

4327 ** In the actual code below, the value "16" is replaced with the

4328 ** pre-processor macro FTS_MAX_APPENDABLE_HEIGHT.

4329 */

4330 static int fts3IncrmergeWriter(

4331 Fts3Table p, / Fts3 table handle */

4332 sqlite3_int64 iAbsLevel, /* Absolute level of input segments */

4333 int iIdx, /* Index of new output segment */

4334 Fts3MultiSegReader pCsr, / Cursor that data will be read from */

4335 IncrmergeWriter pWriter / Populate this object */

4336 ){

4337 int rc; /* Return Code */

4338 int i; /* Iterator variable */

4339 int nLeafEst = 0; /* Blocks allocated for leaf nodes */

4340 sqlite3_stmt pLeafEst = 0; / SQL used to determine nLeafEst */

4341 sqlite3_stmt pFirstBlock = 0; / SQL used to determine first block */

4342

4343 /* Calculate nLeafEst. */

4344 rc = fts3SqlStmt(p, SQL_MAX_LEAF_NODE_ESTIMATE, &pLeafEst, 0);

4345 if( rc==SQLITE_OK ){

4346 sqlite3_bind_int64(pLeafEst, 1, iAbsLevel);

4347 sqlite3_bind_int64(pLeafEst, 2, pCsr->nSegment);

4348 if( SQLITE_ROW==sqlite3_step(pLeafEst) ){

4349 nLeafEst = sqlite3_column_int(pLeafEst, 0);

4350 }

4351 rc = sqlite3_reset(pLeafEst);

4352 }

4353 if( rc!=SQLITE_OK ) return rc;

4354

4355 /* Calculate the first block to use in the output segment */

4356 rc = fts3SqlStmt(p, SQL_NEXT_SEGMENTS_ID, &pFirstBlock, 0);

4357 if( rc==SQLITE_OK ){

4358 if( SQLITE_ROW==sqlite3_step(pFirstBlock) ){

4359 pWriter->iStart = sqlite3_column_int64(pFirstBlock, 0);

4360 pWriter->iEnd = pWriter->iStart - 1;

4361 pWriter->iEnd += nLeafEst * FTS_MAX_APPENDABLE_HEIGHT;

4362 }

4363 rc = sqlite3_reset(pFirstBlock);

4364 }

4365 if( rc!=SQLITE_OK ) return rc;

4366

4367 /* Insert the marker in the %_segments table to make sure nobody tries

4368 ** to steal the space just allocated. This is also used to identify

4369 ** appendable segments. */

4370 rc = fts3WriteSegment(p, pWriter->iEnd, 0, 0);

4371 if( rc!=SQLITE_OK ) return rc;

4372

4373 pWriter->iAbsLevel = iAbsLevel;

4374 pWriter->nLeafEst = nLeafEst;

4375 pWriter->iIdx = iIdx;

4376

4377 /* Set up the array of NodeWriter objects */

4378 for(i=0; i<FTS_MAX_APPENDABLE_HEIGHT; i++){

4379 pWriter->aNodeWriter[i].iBlock = pWriter->iStart + i*pWriter->nLeafEst;

4380 }

4381 return SQLITE_OK;

4382 }

4383

4384 /*

4385 ** Remove an entry from the %_segdir table. This involves running the

4386 ** following two statements:

4387 **

4388 ** DELETE FROM %_segdir WHERE level = :iAbsLevel AND idx = :iIdx

4389 ** UPDATE %_segdir SET idx = idx - 1 WHERE level = :iAbsLevel AND idx > :iIdx

4390 **

4391 ** The DELETE statement removes the specific %_segdir level. The UPDATE

4392 ** statement ensures that the remaining segments have contiguously allocated

4393 ** idx values.

4394 */

4395 static int fts3RemoveSegdirEntry(

4396 Fts3Table p, / FTS3 table handle */

4397 sqlite3_int64 iAbsLevel, /* Absolute level to delete from */

4398 int iIdx /* Index of %_segdir entry to delete */

4399 ){

4400 int rc; /* Return code */

4401 sqlite3_stmt pDelete = 0; / DELETE statement */

4402

4403 rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_ENTRY, &pDelete, 0);

4404 if( rc==SQLITE_OK ){

4405 sqlite3_bind_int64(pDelete, 1, iAbsLevel);

4406 sqlite3_bind_int(pDelete, 2, iIdx);

4407 sqlite3_step(pDelete);

4408 rc = sqlite3_reset(pDelete);

4409 }

4410

4411 return rc;

4412 }

4413

4414 /*

4415 ** One or more segments have just been removed from absolute level iAbsLevel.

4416 ** Update the 'idx' values of the remaining segments in the level so that

4417 ** the idx values are a contiguous sequence starting from 0.

4418 */

4419 static int fts3RepackSegdirLevel(

4420 Fts3Table p, / FTS3 table handle */

4421 sqlite3_int64 iAbsLevel /* Absolute level to repack */

4422 ){

4423 int rc; /* Return code */

4424 int aIdx = 0; / Array of remaining idx values */

4425 int nIdx = 0; /* Valid entries in aIdx[] */

4426 int nAlloc = 0; /* Allocated size of aIdx[] */

4427 int i; /* Iterator variable */

4428 sqlite3_stmt pSelect = 0; / Select statement to read idx values */

4429 sqlite3_stmt pUpdate = 0; / Update statement to modify idx values */

4430

4431 rc = fts3SqlStmt(p, SQL_SELECT_INDEXES, &pSelect, 0);

4432 if( rc==SQLITE_OK ){

4433 int rc2;

4434 sqlite3_bind_int64(pSelect, 1, iAbsLevel);

4435 while( SQLITE_ROW==sqlite3_step(pSelect) ){

4436 if( nIdx>=nAlloc ){

4437 int *aNew;

4438 nAlloc += 16;

4439 aNew = sqlite3_realloc(aIdx, nAlloc*sizeof(int));

4440 if( !aNew ){

4441 rc = SQLITE_NOMEM;

4442 break;

4443 }

4444 aIdx = aNew;

4445 }

4446 aIdx[nIdx++] = sqlite3_column_int(pSelect, 0);

4447 }

4448 rc2 = sqlite3_reset(pSelect);

4449 if( rc==SQLITE_OK ) rc = rc2;

4450 }

4451

4452 if( rc==SQLITE_OK ){

4453 rc = fts3SqlStmt(p, SQL_SHIFT_SEGDIR_ENTRY, &pUpdate, 0);

4454 }

4455 if( rc==SQLITE_OK ){

4456 sqlite3_bind_int64(pUpdate, 2, iAbsLevel);

4457 }

4458

4459 assert( p->bIgnoreSavepoint==0 );

4460 p->bIgnoreSavepoint = 1;

4461 for(i=0; rc==SQLITE_OK && i<nIdx; i++){

4462 if( aIdx[i]!=i ){

4463 sqlite3_bind_int(pUpdate, 3, aIdx[i]);

4464 sqlite3_bind_int(pUpdate, 1, i);

4465 sqlite3_step(pUpdate);

4466 rc = sqlite3_reset(pUpdate);

4467 }

4468 }

4469 p->bIgnoreSavepoint = 0;

4470

4471 sqlite3_free(aIdx);

4472 return rc;

4473 }

4474

4475 static void fts3StartNode(Blob *pNode, int iHeight, sqlite3_int64 iChild){

4476 pNode->a[0] = (char)iHeight;

4477 if( iChild ){

4478 assert( pNode->nAlloc>=1+sqlite3Fts3VarintLen(iChild) );

4479 pNode->n = 1 + sqlite3Fts3PutVarint(&pNode->a[1], iChild);

4480 }else{

4481 assert( pNode->nAlloc>=1 );

4482 pNode->n = 1;

4483 }

4484 }

4485

4486 /*

4487 ** The first two arguments are a pointer to and the size of a segment b-tree

4488 ** node. The node may be a leaf or an internal node.

4489 **

4490 ** This function creates a new node image in blob object *pNew by copying

4491 ** all terms that are greater than or equal to zTerm/nTerm (for leaf nodes)

4492 ** or greater than zTerm/nTerm (for internal nodes) from aNode/nNode.

4493 */

4494 static int fts3TruncateNode(

4495 const char aNode, / Current node image */

4496 int nNode, /* Size of aNode in bytes */

4497 Blob pNew, / OUT: Write new node image here */

4498 const char zTerm, / Omit all terms smaller than this */

4499 int nTerm, /* Size of zTerm in bytes */

4500 sqlite3_int64 piBlock / OUT: Block number in next layer down */

4501 ){

4502 NodeReader reader; /* Reader object */

4503 Blob prev = {0, 0, 0}; /* Previous term written to new node */

4504 int rc = SQLITE_OK; /* Return code */

4505 int bLeaf = aNode[0]=='\0'; /* True for a leaf node */

4506

4507 /* Allocate required output space */

4508 blobGrowBuffer(pNew, nNode, &rc);

4509 if( rc!=SQLITE_OK ) return rc;

4510 pNew->n = 0;

4511

4512 /* Populate new node buffer */

4513 for(rc = nodeReaderInit(&reader, aNode, nNode);

4514 rc==SQLITE_OK && reader.aNode;

4515 rc = nodeReaderNext(&reader)

4516 ){

4517 if( pNew->n==0 ){

4518 int res = fts3TermCmp(reader.term.a, reader.term.n, zTerm, nTerm);

4519 if( res<0 \|\| (bLeaf==0 && res==0) ) continue;

4520 fts3StartNode(pNew, (int)aNode[0], reader.iChild);

4521 *piBlock = reader.iChild;

4522 }

4523 rc = fts3AppendToNode(

4524 pNew, &prev, reader.term.a, reader.term.n,

4525 reader.aDoclist, reader.nDoclist

4526 );

4527 if( rc!=SQLITE_OK ) break;

4528 }

4529 if( pNew->n==0 ){

4530 fts3StartNode(pNew, (int)aNode[0], reader.iChild);

4531 *piBlock = reader.iChild;

4532 }

4533 assert( pNew->n<=pNew->nAlloc );

4534

4535 nodeReaderRelease(&reader);

4536 sqlite3_free(prev.a);

4537 return rc;

4538 }

4539

4540 /*

4541 ** Remove all terms smaller than zTerm/nTerm from segment iIdx in absolute

4542 ** level iAbsLevel. This may involve deleting entries from the %_segments

4543 ** table, and modifying existing entries in both the %_segments and %_segdir

4544 ** tables.

4545 **

4546 ** SQLITE_OK is returned if the segment is updated successfully. Or an

4547 ** SQLite error code otherwise.

4548 */

4549 static int fts3TruncateSegment(

4550 Fts3Table p, / FTS3 table handle */

4551 sqlite3_int64 iAbsLevel, /* Absolute level of segment to modify */

4552 int iIdx, /* Index within level of segment to modify */

4553 const char zTerm, / Remove terms smaller than this */

4554 int nTerm /* Number of bytes in buffer zTerm */

4555 ){

4556 int rc = SQLITE_OK; /* Return code */

4557 Blob root = {0,0,0}; /* New root page image */

4558 Blob block = {0,0,0}; /* Buffer used for any other block */

4559 sqlite3_int64 iBlock = 0; /* Block id */

4560 sqlite3_int64 iNewStart = 0; /* New value for iStartBlock */

4561 sqlite3_int64 iOldStart = 0; /* Old value for iStartBlock */

4562 sqlite3_stmt pFetch = 0; / Statement used to fetch segdir */

4563

4564 rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pFetch, 0);

4565 if( rc==SQLITE_OK ){

4566 int rc2; /* sqlite3_reset() return code */

4567 sqlite3_bind_int64(pFetch, 1, iAbsLevel);

4568 sqlite3_bind_int(pFetch, 2, iIdx);

4569 if( SQLITE_ROW==sqlite3_step(pFetch) ){

4570 const char *aRoot = sqlite3_column_blob(pFetch, 4);

4571 int nRoot = sqlite3_column_bytes(pFetch, 4);

4572 iOldStart = sqlite3_column_int64(pFetch, 1);

4573 rc = fts3TruncateNode(aRoot, nRoot, &root, zTerm, nTerm, &iBlock);

4574 }

4575 rc2 = sqlite3_reset(pFetch);

4576 if( rc==SQLITE_OK ) rc = rc2;

4577 }

4578

4579 while( rc==SQLITE_OK && iBlock ){

4580 char *aBlock = 0;

4581 int nBlock = 0;

4582 iNewStart = iBlock;

4583

4584 rc = sqlite3Fts3ReadBlock(p, iBlock, &aBlock, &nBlock, 0);

4585 if( rc==SQLITE_OK ){

4586 rc = fts3TruncateNode(aBlock, nBlock, &block, zTerm, nTerm, &iBlock);

4587 }

4588 if( rc==SQLITE_OK ){

4589 rc = fts3WriteSegment(p, iNewStart, block.a, block.n);

4590 }

4591 sqlite3_free(aBlock);

4592 }

4593

4594 /* Variable iNewStart now contains the first valid leaf node. */

4595 if( rc==SQLITE_OK && iNewStart ){

4596 sqlite3_stmt *pDel = 0;

4597 rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDel, 0);

4598 if( rc==SQLITE_OK ){

4599 sqlite3_bind_int64(pDel, 1, iOldStart);

4600 sqlite3_bind_int64(pDel, 2, iNewStart-1);

4601 sqlite3_step(pDel);

4602 rc = sqlite3_reset(pDel);

4603 }

4604 }

4605

4606 if( rc==SQLITE_OK ){

4607 sqlite3_stmt *pChomp = 0;

4608 rc = fts3SqlStmt(p, SQL_CHOMP_SEGDIR, &pChomp, 0);

4609 if( rc==SQLITE_OK ){

4610 sqlite3_bind_int64(pChomp, 1, iNewStart);

4611 sqlite3_bind_blob(pChomp, 2, root.a, root.n, SQLITE_STATIC);

4612 sqlite3_bind_int64(pChomp, 3, iAbsLevel);

4613 sqlite3_bind_int(pChomp, 4, iIdx);

4614 sqlite3_step(pChomp);

4615 rc = sqlite3_reset(pChomp);

4616 }

4617 }

4618

4619 sqlite3_free(root.a);

4620 sqlite3_free(block.a);

4621 return rc;

4622 }

4623

4624 /*

4625 ** This function is called after an incrmental-merge operation has run to

4626 ** merge (or partially merge) two or more segments from absolute level

4627 ** iAbsLevel.

4628 **

4629 ** Each input segment is either removed from the db completely (if all of

4630 ** its data was copied to the output segment by the incrmerge operation)

4631 ** or modified in place so that it no longer contains those entries that

4632 ** have been duplicated in the output segment.

4633 */

4634 static int fts3IncrmergeChomp(

4635 Fts3Table p, / FTS table handle */

4636 sqlite3_int64 iAbsLevel, /* Absolute level containing segments */

4637 Fts3MultiSegReader pCsr, / Chomp all segments opened by this cursor */

4638 int pnRem / Number of segments not deleted */

4639 ){

4640 int i;

4641 int nRem = 0;

4642 int rc = SQLITE_OK;

4643

4644 for(i=pCsr->nSegment-1; i>=0 && rc==SQLITE_OK; i--){

4645 Fts3SegReader *pSeg = 0;

4646 int j;

4647

4648 /* Find the Fts3SegReader object with Fts3SegReader.iIdx==i. It is hiding

4649 ** somewhere in the pCsr->apSegment[] array. */

4650 for(j=0; ALWAYS(j<pCsr->nSegment); j++){

4651 pSeg = pCsr->apSegment[j];

4652 if( pSeg->iIdx==i ) break;

4653 }

4654 assert( j<pCsr->nSegment && pSeg->iIdx==i );

4655

4656 if( pSeg->aNode==0 ){

4657 /* Seg-reader is at EOF. Remove the entire input segment. */

4658 rc = fts3DeleteSegment(p, pSeg);

4659 if( rc==SQLITE_OK ){

4660 rc = fts3RemoveSegdirEntry(p, iAbsLevel, pSeg->iIdx);

4661 }

4662 *pnRem = 0;

4663 }else{

4664 /* The incremental merge did not copy all the data from this

4665 ** segment to the upper level. The segment is modified in place

4666 ** so that it contains no keys smaller than zTerm/nTerm. */

4667 const char *zTerm = pSeg->zTerm;

4668 int nTerm = pSeg->nTerm;

4669 rc = fts3TruncateSegment(p, iAbsLevel, pSeg->iIdx, zTerm, nTerm);

4670 nRem++;

4671 }

4672 }

4673

4674 if( rc==SQLITE_OK && nRem!=pCsr->nSegment ){

4675 rc = fts3RepackSegdirLevel(p, iAbsLevel);

4676 }

4677

4678 *pnRem = nRem;

4679 return rc;

4680 }

4681

4682 /*

4683 ** Store an incr-merge hint in the database.

4684 */

4685 static int fts3IncrmergeHintStore(Fts3Table p, Blob pHint){

4686 sqlite3_stmt *pReplace = 0;

4687 int rc; /* Return code */

4688

4689 rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pReplace, 0);

4690 if( rc==SQLITE_OK ){

4691 sqlite3_bind_int(pReplace, 1, FTS_STAT_INCRMERGEHINT);

4692 sqlite3_bind_blob(pReplace, 2, pHint->a, pHint->n, SQLITE_STATIC);

4693 sqlite3_step(pReplace);

4694 rc = sqlite3_reset(pReplace);

4695 }

4696

4697 return rc;

4698 }

4699

4700 /*

4701 ** Load an incr-merge hint from the database. The incr-merge hint, if one

4702 ** exists, is stored in the rowid==1 row of the %_stat table.

4703 **

4704 ** If successful, populate blob *pHint with the value read from the %_stat

4705 ** table and return SQLITE_OK. Otherwise, if an error occurs, return an

4706 ** SQLite error code.

4707 */

4708 static int fts3IncrmergeHintLoad(Fts3Table p, Blob pHint){

4709 sqlite3_stmt *pSelect = 0;

4710 int rc;

4711

4712 pHint->n = 0;

4713 rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pSelect, 0);

4714 if( rc==SQLITE_OK ){

4715 int rc2;

4716 sqlite3_bind_int(pSelect, 1, FTS_STAT_INCRMERGEHINT);

4717 if( SQLITE_ROW==sqlite3_step(pSelect) ){

4718 const char *aHint = sqlite3_column_blob(pSelect, 0);

4719 int nHint = sqlite3_column_bytes(pSelect, 0);

4720 if( aHint ){

4721 blobGrowBuffer(pHint, nHint, &rc);

4722 if( rc==SQLITE_OK ){

4723 memcpy(pHint->a, aHint, nHint);

4724 pHint->n = nHint;

4725 }

4726 }

4727 }

4728 rc2 = sqlite3_reset(pSelect);

4729 if( rc==SQLITE_OK ) rc = rc2;

4730 }

4731

4732 return rc;

4733 }

4734

4735 /*

4736 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.

4737 ** Otherwise, append an entry to the hint stored in blob *pHint. Each entry

4738 ** consists of two varints, the absolute level number of the input segments

4739 ** and the number of input segments.

4740 **

4741 ** If successful, leave *pRc set to SQLITE_OK and return. If an error occurs,

4742 ** set *pRc to an SQLite error code before returning.

4743 */

4744 static void fts3IncrmergeHintPush(

4745 Blob pHint, / Hint blob to append to */

4746 i64 iAbsLevel, /* First varint to store in hint */

4747 int nInput, /* Second varint to store in hint */

4748 int pRc / IN/OUT: Error code */

4749 ){

4750 blobGrowBuffer(pHint, pHint->n + 2*FTS3_VARINT_MAX, pRc);

4751 if( *pRc==SQLITE_OK ){

4752 pHint->n += sqlite3Fts3PutVarint(&pHint->a[pHint->n], iAbsLevel);

4753 pHint->n += sqlite3Fts3PutVarint(&pHint->a[pHint->n], (i64)nInput);

4754 }

4755 }

4756

4757 /*

4758 ** Read the last entry (most recently pushed) from the hint blob *pHint

4759 ** and then remove the entry. Write the two values read to *piAbsLevel and

4760 ** *pnInput before returning.

4761 **

4762 ** If no error occurs, return SQLITE_OK. If the hint blob in *pHint does

4763 ** not contain at least two valid varints, return SQLITE_CORRUPT_VTAB.

4764 */

4765 static int fts3IncrmergeHintPop(Blob pHint, i64 piAbsLevel, int *pnInput){

4766 const int nHint = pHint->n;

4767 int i;

4768

4769 i = pHint->n-2;

4770 while( i>0 && (pHint->a[i-1] & 0x80) ) i--;

4771 while( i>0 && (pHint->a[i-1] & 0x80) ) i--;

4772

4773 pHint->n = i;

4774 i += sqlite3Fts3GetVarint(&pHint->a[i], piAbsLevel);

4775 i += fts3GetVarint32(&pHint->a[i], pnInput);

4776 if( i!=nHint ) return SQLITE_CORRUPT_VTAB;

4777

4778 return SQLITE_OK;

4779 }

4780

4781

4782 /*

4783 ** Attempt an incremental merge that writes nMerge leaf blocks.

4784 **

4785 ** Incremental merges happen nMin segments at a time. The segments

4786 ** to be merged are the nMin oldest segments (the ones with the smallest

4787 ** values for the _segdir.idx field) in the highest level that contains

4788 ** at least nMin segments. Multiple merges might occur in an attempt to

4789 ** write the quota of nMerge leaf blocks.

4790 */

4791 int sqlite3Fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){

4792 int rc; /* Return code */

4793 int nRem = nMerge; /* Number of leaf pages yet to be written */

4794 Fts3MultiSegReader pCsr; / Cursor used to read input data */

4795 Fts3SegFilter pFilter; / Filter used with cursor pCsr */

4796 IncrmergeWriter pWriter; / Writer object */

4797 int nSeg = 0; /* Number of input segments */

4798 sqlite3_int64 iAbsLevel = 0; /* Absolute level number to work on */

4799 Blob hint = {0, 0, 0}; /* Hint read from %_stat table */

4800 int bDirtyHint = 0; /* True if blob 'hint' has been modified */

4801

4802 /* Allocate space for the cursor, filter and writer objects */

4803 const int nAlloc = sizeof(pCsr) + sizeof(pFilter) + sizeof(*pWriter);

4804 pWriter = (IncrmergeWriter *)sqlite3_malloc(nAlloc);

4805 if( !pWriter ) return SQLITE_NOMEM;

4806 pFilter = (Fts3SegFilter *)&pWriter[1];

4807 pCsr = (Fts3MultiSegReader *)&pFilter[1];

4808

4809 rc = fts3IncrmergeHintLoad(p, &hint);

4810 while( rc==SQLITE_OK && nRem>0 ){

4811 const i64 nMod = FTS3_SEGDIR_MAXLEVEL * p->nIndex;

4812 sqlite3_stmt pFindLevel = 0; / SQL used to determine iAbsLevel */

4813 int bUseHint = 0; /* True if attempting to append */

4814 int iIdx = 0; /* Largest idx in level (iAbsLevel+1) */

4815

4816 /* Search the %_segdir table for the absolute level with the smallest

4817 ** relative level number that contains at least nMin segments, if any.

4818 ** If one is found, set iAbsLevel to the absolute level number and

4819 ** nSeg to nMin. If no level with at least nMin segments can be found,

4820 ** set nSeg to -1.

4821 */

4822 rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0);

4823 sqlite3_bind_int(pFindLevel, 1, nMin);

4824 if( sqlite3_step(pFindLevel)==SQLITE_ROW ){

4825 iAbsLevel = sqlite3_column_int64(pFindLevel, 0);

4826 nSeg = nMin;

4827 }else{

4828 nSeg = -1;

4829 }

4830 rc = sqlite3_reset(pFindLevel);

4831

4832 /* If the hint read from the %_stat table is not empty, check if the

4833 ** last entry in it specifies a relative level smaller than or equal

4834 ** to the level identified by the block above (if any). If so, this

4835 ** iteration of the loop will work on merging at the hinted level.

4836 */

4837 if( rc==SQLITE_OK && hint.n ){

4838 int nHint = hint.n;

4839 sqlite3_int64 iHintAbsLevel = 0; /* Hint level */

4840 int nHintSeg = 0; /* Hint number of segments */

4841

4842 rc = fts3IncrmergeHintPop(&hint, &iHintAbsLevel, &nHintSeg);

4843 if( nSeg<0 \|\| (iAbsLevel % nMod) >= (iHintAbsLevel % nMod) ){

4844 iAbsLevel = iHintAbsLevel;

4845 nSeg = nHintSeg;

4846 bUseHint = 1;

4847 bDirtyHint = 1;

4848 }else{

4849 /* This undoes the effect of the HintPop() above - so that no entry

4850 ** is removed from the hint blob. */

4851 hint.n = nHint;

4852 }

4853 }

4854

4855 /* If nSeg is less that zero, then there is no level with at least

4856 ** nMin segments and no hint in the %_stat table. No work to do.

4857 ** Exit early in this case. */

4858 if( nSeg<0 ) break;

4859

4860 /* Open a cursor to iterate through the contents of the oldest nSeg

4861 ** indexes of absolute level iAbsLevel. If this cursor is opened using

4862 ** the 'hint' parameters, it is possible that there are less than nSeg

4863 ** segments available in level iAbsLevel. In this case, no work is

4864 ** done on iAbsLevel - fall through to the next iteration of the loop

4865 ** to start work on some other level. */

4866 memset(pWriter, 0, nAlloc);

4867 pFilter->flags = FTS3_SEGMENT_REQUIRE_POS;

4868

4869 if( rc==SQLITE_OK ){

4870 rc = fts3IncrmergeOutputIdx(p, iAbsLevel, &iIdx);

4871 assert( bUseHint==1 \|\| bUseHint==0 );

4872 if( iIdx==0 \|\| (bUseHint && iIdx==1) ){

4873 int bIgnore = 0;

4874 rc = fts3SegmentIsMaxLevel(p, iAbsLevel+1, &bIgnore);

4875 if( bIgnore ){

4876 pFilter->flags \|= FTS3_SEGMENT_IGNORE_EMPTY;

4877 }

4878 }

4879 }

4880

4881 if( rc==SQLITE_OK ){

4882 rc = fts3IncrmergeCsr(p, iAbsLevel, nSeg, pCsr);

4883 }

4884 if( SQLITE_OK==rc && pCsr->nSegment==nSeg

4885 && SQLITE_OK==(rc = sqlite3Fts3SegReaderStart(p, pCsr, pFilter))

4886 && SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pCsr))

4887 ){

4888 if( bUseHint && iIdx>0 ){

4889 const char *zKey = pCsr->zTerm;

4890 int nKey = pCsr->nTerm;

4891 rc = fts3IncrmergeLoad(p, iAbsLevel, iIdx-1, zKey, nKey, pWriter);

4892 }else{

4893 rc = fts3IncrmergeWriter(p, iAbsLevel, iIdx, pCsr, pWriter);

4894 }

4895

4896 if( rc==SQLITE_OK && pWriter->nLeafEst ){

4897 fts3LogMerge(nSeg, iAbsLevel);

4898 do {

4899 rc = fts3IncrmergeAppend(p, pWriter, pCsr);

4900 if( rc==SQLITE_OK ) rc = sqlite3Fts3SegReaderStep(p, pCsr);

4901 if( pWriter->nWork>=nRem && rc==SQLITE_ROW ) rc = SQLITE_OK;

4902 }while( rc==SQLITE_ROW );

4903

4904 /* Update or delete the input segments */

4905 if( rc==SQLITE_OK ){

4906 nRem -= (1 + pWriter->nWork);

4907 rc = fts3IncrmergeChomp(p, iAbsLevel, pCsr, &nSeg);

4908 if( nSeg!=0 ){

4909 bDirtyHint = 1;

4910 fts3IncrmergeHintPush(&hint, iAbsLevel, nSeg, &rc);

4911 }

4912 }

4913 }

4914

4915 if( nSeg!=0 ){

4916 pWriter->nLeafData = pWriter->nLeafData * -1;

4917 }

4918 fts3IncrmergeRelease(p, pWriter, &rc);

4919 if( nSeg==0 && pWriter->bNoLeafData==0 ){

4920 fts3PromoteSegments(p, iAbsLevel+1, pWriter->nLeafData);

4921 }

4922 }

4923

4924 sqlite3Fts3SegReaderFinish(pCsr);

4925 }

4926

4927 /* Write the hint values into the %_stat table for the next incr-merger */

4928 if( bDirtyHint && rc==SQLITE_OK ){

4929 rc = fts3IncrmergeHintStore(p, &hint);

4930 }

4931

4932 sqlite3_free(pWriter);

4933 sqlite3_free(hint.a);

4934 return rc;

4935 }

4936

4937 /*

4938 ** Convert the text beginning at *pz into an integer and return

4939 ** its value. Advance *pz to point to the first character past

4940 ** the integer.

4941 */

4942 static int fts3Getint(const char **pz){

4943 const char z = pz;

4944 int i = 0;

4945 while( (z)>='0' && (z)<='9' ) i = 10i + (z++) - '0';

4946 *pz = z;

4947 return i;

4948 }

4949

4950 /*

4951 ** Process statements of the form:

4952 **

4953 ** INSERT INTO table(table) VALUES('merge=A,B');

4954 **

4955 ** A and B are integers that decode to be the number of leaf pages

4956 ** written for the merge, and the minimum number of segments on a level

4957 ** before it will be selected for a merge, respectively.

4958 */

4959 static int fts3DoIncrmerge(

4960 Fts3Table p, / FTS3 table handle */

4961 const char zParam / Nul-terminated string containing "A,B" */

4962 ){

4963 int rc;

4964 int nMin = (FTS3_MERGE_COUNT / 2);

4965 int nMerge = 0;

4966 const char *z = zParam;

4967

4968 /* Read the first integer value */

4969 nMerge = fts3Getint(&z);

4970

4971 /* If the first integer value is followed by a ',', read the second

4972 ** integer value. */

4973 if( z[0]==',' && z[1]!='\0' ){

4974 z++;

4975 nMin = fts3Getint(&z);

4976 }

4977

4978 if( z[0]!='\0' \|\| nMin<2 ){

4979 rc = SQLITE_ERROR;

4980 }else{

4981 rc = SQLITE_OK;

4982 if( !p->bHasStat ){

4983 assert( p->bFts4==0 );

4984 sqlite3Fts3CreateStatTable(&rc, p);

4985 }

4986 if( rc==SQLITE_OK ){

4987 rc = sqlite3Fts3Incrmerge(p, nMerge, nMin);

4988 }

4989 sqlite3Fts3SegmentsClose(p);

4990 }

4991 return rc;

4992 }

4993

4994 /*

4995 ** Process statements of the form:

4996 **

4997 ** INSERT INTO table(table) VALUES('automerge=X');

4998 **

4999 ** where X is an integer. X==0 means to turn automerge off. X!=0 means

5000 ** turn it on. The setting is persistent.

5001 */

5002 static int fts3DoAutoincrmerge(

5003 Fts3Table p, / FTS3 table handle */

5004 const char zParam / Nul-terminated string containing boolean */

5005 ){

5006 int rc = SQLITE_OK;

5007 sqlite3_stmt *pStmt = 0;

5008 p->nAutoincrmerge = fts3Getint(&zParam);

5009 if( p->nAutoincrmerge==1 \|\| p->nAutoincrmerge>FTS3_MERGE_COUNT ){

5010 p->nAutoincrmerge = 8;

5011 }

5012 if( !p->bHasStat ){

5013 assert( p->bFts4==0 );

5014 sqlite3Fts3CreateStatTable(&rc, p);

5015 if( rc ) return rc;

5016 }

5017 rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pStmt, 0);

5018 if( rc ) return rc;

5019 sqlite3_bind_int(pStmt, 1, FTS_STAT_AUTOINCRMERGE);

5020 sqlite3_bind_int(pStmt, 2, p->nAutoincrmerge);

5021 sqlite3_step(pStmt);

5022 rc = sqlite3_reset(pStmt);

5023 return rc;

5024 }

5025

5026 /*

5027 ** Return a 64-bit checksum for the FTS index entry specified by the

5028 ** arguments to this function.

5029 */

5030 static u64 fts3ChecksumEntry(

5031 const char zTerm, / Pointer to buffer containing term */

5032 int nTerm, /* Size of zTerm in bytes */

5033 int iLangid, /* Language id for current row */

5034 int iIndex, /* Index (0..Fts3Table.nIndex-1) */

5035 i64 iDocid, /* Docid for current row. */

5036 int iCol, /* Column number */

5037 int iPos /* Position */

5038 ){

5039 int i;

5040 u64 ret = (u64)iDocid;

5041

5042 ret += (ret<<3) + iLangid;

5043 ret += (ret<<3) + iIndex;

5044 ret += (ret<<3) + iCol;

5045 ret += (ret<<3) + iPos;

5046 for(i=0; i<nTerm; i++) ret += (ret<<3) + zTerm[i];

5047

5048 return ret;

5049 }

5050

5051 /*

5052 ** Return a checksum of all entries in the FTS index that correspond to

5053 ** language id iLangid. The checksum is calculated by XORing the checksums

5054 ** of each individual entry (see fts3ChecksumEntry()) together.

5055 **

5056 ** If successful, the checksum value is returned and *pRc set to SQLITE_OK.

5057 ** Otherwise, if an error occurs, *pRc is set to an SQLite error code. The

5058 ** return value is undefined in this case.

5059 */

5060 static u64 fts3ChecksumIndex(

5061 Fts3Table p, / FTS3 table handle */

5062 int iLangid, /* Language id to return cksum for */

5063 int iIndex, /* Index to cksum (0..p->nIndex-1) */

5064 int pRc / OUT: Return code */

5065 ){

5066 Fts3SegFilter filter;

5067 Fts3MultiSegReader csr;

5068 int rc;

5069 u64 cksum = 0;

5070

5071 assert( *pRc==SQLITE_OK );

5072

5073 memset(&filter, 0, sizeof(filter));

5074 memset(&csr, 0, sizeof(csr));

5075 filter.flags = FTS3_SEGMENT_REQUIRE_POS\|FTS3_SEGMENT_IGNORE_EMPTY;

5076 filter.flags \|= FTS3_SEGMENT_SCAN;

5077

5078 rc = sqlite3Fts3SegReaderCursor(

5079 p, iLangid, iIndex, FTS3_SEGCURSOR_ALL, 0, 0, 0, 1,&csr

5080 );

5081 if( rc==SQLITE_OK ){

5082 rc = sqlite3Fts3SegReaderStart(p, &csr, &filter);

5083 }

5084

5085 if( rc==SQLITE_OK ){

5086 while( SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, &csr)) ){

5087 char *pCsr = csr.aDoclist;

5088 char *pEnd = &pCsr[csr.nDoclist];

5089

5090 i64 iDocid = 0;

5091 i64 iCol = 0;

5092 i64 iPos = 0;

5093

5094 pCsr += sqlite3Fts3GetVarint(pCsr, &iDocid);

5095 while( pCsr<pEnd ){

5096 i64 iVal = 0;

5097 pCsr += sqlite3Fts3GetVarint(pCsr, &iVal);

5098 if( pCsr<pEnd ){

5099 if( iVal==0 \|\| iVal==1 ){

5100 iCol = 0;

5101 iPos = 0;

5102 if( iVal ){

5103 pCsr += sqlite3Fts3GetVarint(pCsr, &iCol);

5104 }else{

5105 pCsr += sqlite3Fts3GetVarint(pCsr, &iVal);

5106 iDocid += iVal;

5107 }

5108 }else{

5109 iPos += (iVal - 2);

5110 cksum = cksum ^ fts3ChecksumEntry(

5111 csr.zTerm, csr.nTerm, iLangid, iIndex, iDocid,

5112 (int)iCol, (int)iPos

5113 );

5114 }

5115 }

5116 }

5117 }

5118 }

5119 sqlite3Fts3SegReaderFinish(&csr);

5120

5121 *pRc = rc;

5122 return cksum;

5123 }

5124

5125 /*

5126 ** Check if the contents of the FTS index match the current contents of the

5127 ** content table. If no error occurs and the contents do match, set *pbOk

5128 ** to true and return SQLITE_OK. Or if the contents do not match, set *pbOk

5129 ** to false before returning.

5130 **

5131 ** If an error occurs (e.g. an OOM or IO error), return an SQLite error

5132 ** code. The final value of *pbOk is undefined in this case.

5133 */

5134 static int fts3IntegrityCheck(Fts3Table p, int pbOk){

5135 int rc = SQLITE_OK; /* Return code */

5136 u64 cksum1 = 0; /* Checksum based on FTS index contents */

5137 u64 cksum2 = 0; /* Checksum based on %_content contents */

5138 sqlite3_stmt pAllLangid = 0; / Statement to return all language-ids */

5139

5140 /* This block calculates the checksum according to the FTS index. */

5141 rc = fts3SqlStmt(p, SQL_SELECT_ALL_LANGID, &pAllLangid, 0);

5142 if( rc==SQLITE_OK ){

5143 int rc2;

5144 sqlite3_bind_int(pAllLangid, 1, p->nIndex);

5145 while( rc==SQLITE_OK && sqlite3_step(pAllLangid)==SQLITE_ROW ){

5146 int iLangid = sqlite3_column_int(pAllLangid, 0);

5147 int i;

5148 for(i=0; i<p->nIndex; i++){

5149 cksum1 = cksum1 ^ fts3ChecksumIndex(p, iLangid, i, &rc);

5150 }

5151 }

5152 rc2 = sqlite3_reset(pAllLangid);

5153 if( rc==SQLITE_OK ) rc = rc2;

5154 }

5155

5156 /* This block calculates the checksum according to the %_content table */

5157 rc = fts3SqlStmt(p, SQL_SELECT_ALL_LANGID, &pAllLangid, 0);

5158 if( rc==SQLITE_OK ){

5159 sqlite3_tokenizer_module const *pModule = p->pTokenizer->pModule;

5160 sqlite3_stmt *pStmt = 0;

5161 char *zSql;

5162

5163 zSql = sqlite3_mprintf("SELECT %s" , p->zReadExprlist);

5164 if( !zSql ){

5165 rc = SQLITE_NOMEM;

5166 }else{

5167 rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0);

5168 sqlite3_free(zSql);

5169 }

5170

5171 while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){

5172 i64 iDocid = sqlite3_column_int64(pStmt, 0);

5173 int iLang = langidFromSelect(p, pStmt);

5174 int iCol;

5175

5176 for(iCol=0; rc==SQLITE_OK && iCol<p->nColumn; iCol++){

5177 if( p->abNotindexed[iCol]==0 ){

5178 const char zText = (const char )sqlite3_column_text(pStmt, iCol+1);

5179 int nText = sqlite3_column_bytes(pStmt, iCol+1);

5180 sqlite3_tokenizer_cursor *pT = 0;

5181

5182 rc = sqlite3Fts3OpenTokenizer(p->pTokenizer, iLang, zText, nText,&pT);

5183 while( rc==SQLITE_OK ){

5184 char const zToken; / Buffer containing token */

5185 int nToken = 0; /* Number of bytes in token */

5186 int iDum1 = 0, iDum2 = 0; /* Dummy variables */

5187 int iPos = 0; /* Position of token in zText */

5188

5189 rc = pModule->xNext(pT, &zToken, &nToken, &iDum1, &iDum2, &iPos);

5190 if( rc==SQLITE_OK ){

5191 int i;

5192 cksum2 = cksum2 ^ fts3ChecksumEntry(

5193 zToken, nToken, iLang, 0, iDocid, iCol, iPos

5194 );

5195 for(i=1; i<p->nIndex; i++){

5196 if( p->aIndex[i].nPrefix<=nToken ){

5197 cksum2 = cksum2 ^ fts3ChecksumEntry(

5198 zToken, p->aIndex[i].nPrefix, iLang, i, iDocid, iCol, iPos

5199 );

5200 }

5201 }

5202 }

5203 }

5204 if( pT ) pModule->xClose(pT);

5205 if( rc==SQLITE_DONE ) rc = SQLITE_OK;

5206 }

5207 }

5208 }

5209

5210 sqlite3_finalize(pStmt);

5211 }

5212

5213 *pbOk = (cksum1==cksum2);

5214 return rc;

5215 }

5216

5217 /*

5218 ** Run the integrity-check. If no error occurs and the current contents of

5219 ** the FTS index are correct, return SQLITE_OK. Or, if the contents of the

5220 ** FTS index are incorrect, return SQLITE_CORRUPT_VTAB.

5221 **

5222 ** Or, if an error (e.g. an OOM or IO error) occurs, return an SQLite

5223 ** error code.

5224 **

5225 ** The integrity-check works as follows. For each token and indexed token

5226 ** prefix in the document set, a 64-bit checksum is calculated (by code

5227 ** in fts3ChecksumEntry()) based on the following:

5228 **

5229 ** + The index number (0 for the main index, 1 for the first prefix

5230 ** index etc.),

5231 ** + The token (or token prefix) text itself,

5232 ** + The language-id of the row it appears in,

5233 ** + The docid of the row it appears in,

5234 ** + The column it appears in, and

5235 ** + The tokens position within that column.

5236 **

5237 ** The checksums for all entries in the index are XORed together to create

5238 ** a single checksum for the entire index.

5239 **

5240 ** The integrity-check code calculates the same checksum in two ways:

5241 **

5242 ** 1. By scanning the contents of the FTS index, and

5243 ** 2. By scanning and tokenizing the content table.

5244 **

5245 ** If the two checksums are identical, the integrity-check is deemed to have

5246 ** passed.

5247 */

5248 static int fts3DoIntegrityCheck(

5249 Fts3Table p / FTS3 table handle */

5250 ){

5251 int rc;

5252 int bOk = 0;

5253 rc = fts3IntegrityCheck(p, &bOk);

5254 if( rc==SQLITE_OK && bOk==0 ) rc = SQLITE_CORRUPT_VTAB;

5255 return rc;

5256 }

5257

5258 /*

5259 ** Handle a 'special' INSERT of the form:

5260 **

5261 ** "INSERT INTO tbl(tbl) VALUES(<expr>)"

5262 **

5263 ** Argument pVal contains the result of <expr>. Currently the only

5264 ** meaningful value to insert is the text 'optimize'.

5265 */

5266 static int fts3SpecialInsert(Fts3Table p, sqlite3_value pVal){

5267 int rc; /* Return Code */

5268 const char zVal = (const char )sqlite3_value_text(pVal);

5269 int nVal = sqlite3_value_bytes(pVal);

5270

5271 if( !zVal ){

5272 return SQLITE_NOMEM;

5273 }else if( nVal==8 && 0==sqlite3_strnicmp(zVal, "optimize", 8) ){

5274 rc = fts3DoOptimize(p, 0);

5275 }else if( nVal==7 && 0==sqlite3_strnicmp(zVal, "rebuild", 7) ){

5276 rc = fts3DoRebuild(p);

5277 }else if( nVal==15 && 0==sqlite3_strnicmp(zVal, "integrity-check", 15) ){

5278 rc = fts3DoIntegrityCheck(p);

5279 }else if( nVal>6 && 0==sqlite3_strnicmp(zVal, "merge=", 6) ){

5280 rc = fts3DoIncrmerge(p, &zVal[6]);

5281 }else if( nVal>10 && 0==sqlite3_strnicmp(zVal, "automerge=", 10) ){

5282 rc = fts3DoAutoincrmerge(p, &zVal[10]);

5283 #ifdef SQLITE_TEST

5284 }else if( nVal>9 && 0==sqlite3_strnicmp(zVal, "nodesize=", 9) ){

5285 p->nNodeSize = atoi(&zVal[9]);

5286 rc = SQLITE_OK;

5287 }else if( nVal>11 && 0==sqlite3_strnicmp(zVal, "maxpending=", 9) ){

5288 p->nMaxPendingData = atoi(&zVal[11]);

5289 rc = SQLITE_OK;

5290 }else if( nVal>21 && 0==sqlite3_strnicmp(zVal, "test-no-incr-doclist=", 21) ){

5291 p->bNoIncrDoclist = atoi(&zVal[21]);

5292 rc = SQLITE_OK;

5293 #endif

5294 }else{

5295 rc = SQLITE_ERROR;

5296 }

5297

5298 return rc;

5299 }

5300

5301 #ifndef SQLITE_DISABLE_FTS4_DEFERRED

5302 /*

5303 ** Delete all cached deferred doclists. Deferred doclists are cached

5304 ** (allocated) by the sqlite3Fts3CacheDeferredDoclists() function.

5305 */

5306 void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *pCsr){

5307 Fts3DeferredToken *pDef;

5308 for(pDef=pCsr->pDeferred; pDef; pDef=pDef->pNext){

5309 fts3PendingListDelete(pDef->pList);

5310 pDef->pList = 0;

5311 }

5312 }

5313

5314 /*

5315 ** Free all entries in the pCsr->pDeffered list. Entries are added to

5316 ** this list using sqlite3Fts3DeferToken().

5317 */

5318 void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *pCsr){

5319 Fts3DeferredToken *pDef;

5320 Fts3DeferredToken *pNext;

5321 for(pDef=pCsr->pDeferred; pDef; pDef=pNext){

5322 pNext = pDef->pNext;

5323 fts3PendingListDelete(pDef->pList);

5324 sqlite3_free(pDef);

5325 }

5326 pCsr->pDeferred = 0;

5327 }

5328

5329 /*

5330 ** Generate deferred-doclists for all tokens in the pCsr->pDeferred list

5331 ** based on the row that pCsr currently points to.

5332 **

5333 ** A deferred-doclist is like any other doclist with position information

5334 ** included, except that it only contains entries for a single row of the

5335 ** table, not for all rows.

5336 */

5337 int sqlite3Fts3CacheDeferredDoclists(Fts3Cursor *pCsr){

5338 int rc = SQLITE_OK; /* Return code */

5339 if( pCsr->pDeferred ){

5340 int i; /* Used to iterate through table columns */

5341 sqlite3_int64 iDocid; /* Docid of the row pCsr points to */

5342 Fts3DeferredToken pDef; / Used to iterate through deferred tokens */

5343

5344 Fts3Table p = (Fts3Table )pCsr->base.pVtab;

5345 sqlite3_tokenizer *pT = p->pTokenizer;

5346 sqlite3_tokenizer_module const *pModule = pT->pModule;

5347

5348 assert( pCsr->isRequireSeek==0 );

5349 iDocid = sqlite3_column_int64(pCsr->pStmt, 0);

5350

5351 for(i=0; i<p->nColumn && rc==SQLITE_OK; i++){

5352 if( p->abNotindexed[i]==0 ){

5353 const char zText = (const char )sqlite3_column_text(pCsr->pStmt, i+1);

5354 sqlite3_tokenizer_cursor *pTC = 0;

5355

5356 rc = sqlite3Fts3OpenTokenizer(pT, pCsr->iLangid, zText, -1, &pTC);

5357 while( rc==SQLITE_OK ){

5358 char const zToken; / Buffer containing token */

5359 int nToken = 0; /* Number of bytes in token */

5360 int iDum1 = 0, iDum2 = 0; /* Dummy variables */

5361 int iPos = 0; /* Position of token in zText */

5362

5363 rc = pModule->xNext(pTC, &zToken, &nToken, &iDum1, &iDum2, &iPos);

5364 for(pDef=pCsr->pDeferred; pDef && rc==SQLITE_OK; pDef=pDef->pNext){

5365 Fts3PhraseToken *pPT = pDef->pToken;

5366 if( (pDef->iCol>=p->nColumn \|\| pDef->iCol==i)

5367 && (pPT->bFirst==0 \|\| iPos==0)

5368 && (pPT->n==nToken \|\| (pPT->isPrefix && pPT->n<nToken))

5369 && (0==memcmp(zToken, pPT->z, pPT->n))

5370 ){

5371 fts3PendingListAppend(&pDef->pList, iDocid, i, iPos, &rc);

5372 }

5373 }

5374 }

5375 if( pTC ) pModule->xClose(pTC);

5376 if( rc==SQLITE_DONE ) rc = SQLITE_OK;

5377 }

5378 }

5379

5380 for(pDef=pCsr->pDeferred; pDef && rc==SQLITE_OK; pDef=pDef->pNext){

5381 if( pDef->pList ){

5382 rc = fts3PendingListAppendVarint(&pDef->pList, 0);

5383 }

5384 }

5385 }

5386

5387 return rc;

5388 }

5389

5390 int sqlite3Fts3DeferredTokenList(

5391 Fts3DeferredToken *p,

5392 char **ppData,

5393 int *pnData

5394 ){

5395 char *pRet;

5396 int nSkip;

5397 sqlite3_int64 dummy;

5398

5399 *ppData = 0;

5400 *pnData = 0;

5401

5402 if( p->pList==0 ){

5403 return SQLITE_OK;

5404 }

5405

5406 pRet = (char *)sqlite3_malloc(p->pList->nData);

5407 if( !pRet ) return SQLITE_NOMEM;

5408

5409 nSkip = sqlite3Fts3GetVarint(p->pList->aData, &dummy);

5410 *pnData = p->pList->nData - nSkip;

5411 *ppData = pRet;

5412

5413 memcpy(pRet, &p->pList->aData[nSkip], *pnData);

5414 return SQLITE_OK;

5415 }

5416

5417 /*

5418 ** Add an entry for token pToken to the pCsr->pDeferred list.

5419 */

5420 int sqlite3Fts3DeferToken(

5421 Fts3Cursor pCsr, / Fts3 table cursor */

5422 Fts3PhraseToken pToken, / Token to defer */

5423 int iCol /* Column that token must appear in (or -1) */

5424 ){

5425 Fts3DeferredToken *pDeferred;

5426 pDeferred = sqlite3_malloc(sizeof(*pDeferred));

5427 if( !pDeferred ){

5428 return SQLITE_NOMEM;

5429 }

5430 memset(pDeferred, 0, sizeof(*pDeferred));

5431 pDeferred->pToken = pToken;

5432 pDeferred->pNext = pCsr->pDeferred;

5433 pDeferred->iCol = iCol;

5434 pCsr->pDeferred = pDeferred;

5435

5436 assert( pToken->pDeferred==0 );

5437 pToken->pDeferred = pDeferred;

5438

5439 return SQLITE_OK;

5440 }

5441 #endif

5442

5443 /*

5444 ** SQLite value pRowid contains the rowid of a row that may or may not be

5445 ** present in the FTS3 table. If it is, delete it and adjust the contents

5446 ** of subsiduary data structures accordingly.

5447 */

5448 static int fts3DeleteByRowid(

5449 Fts3Table *p,

5450 sqlite3_value *pRowid,

5451 int pnChng, / IN/OUT: Decrement if row is deleted */

5452 u32 *aSzDel

5453 ){

5454 int rc = SQLITE_OK; /* Return code */

5455 int bFound = 0; /* True if pRowid really is in the table /

5456

5457 fts3DeleteTerms(&rc, p, pRowid, aSzDel, &bFound);

5458 if( bFound && rc==SQLITE_OK ){

5459 int isEmpty = 0; /* Deleting pRowid leaves the table empty /

5460 rc = fts3IsEmpty(p, pRowid, &isEmpty);

5461 if( rc==SQLITE_OK ){

5462 if( isEmpty ){

5463 /* Deleting this row means the whole table is empty. In this case

5464 ** delete the contents of all three tables and throw away any

5465 ** data in the pendingTerms hash table. */

5466 rc = fts3DeleteAll(p, 1);

5467 *pnChng = 0;

5468 memset(aSzDel, 0, sizeof(u32) * (p->nColumn+1) * 2);

5469 }else{

5470 pnChng = pnChng - 1;

5471 if( p->zContentTbl==0 ){

5472 fts3SqlExec(&rc, p, SQL_DELETE_CONTENT, &pRowid);

5473 }

5474 if( p->bHasDocsize ){

5475 fts3SqlExec(&rc, p, SQL_DELETE_DOCSIZE, &pRowid);

5476 }

5477 }

5478 }

5479 }

5480

5481 return rc;

5482 }

5483

5484 /*

5485 ** This function does the work for the xUpdate method of FTS3 virtual

5486 ** tables. The schema of the virtual table being:

5487 **

5488 ** CREATE TABLE <table name>(

5489 ** <user columns>,

5490 ** <table name> HIDDEN,

5491 ** docid HIDDEN,

5492 ** <langid> HIDDEN

5493 ** );

5494 **

5495 **

5496 */

5497 int sqlite3Fts3UpdateMethod(

5498 sqlite3_vtab pVtab, / FTS3 vtab object */

5499 int nArg, /* Size of argument array */

5500 sqlite3_value *apVal, / Array of arguments */

5501 sqlite_int64 pRowid / OUT: The affected (or effected) rowid */

5502 ){

5503 Fts3Table p = (Fts3Table )pVtab;

5504 int rc = SQLITE_OK; /* Return Code */

5505 int isRemove = 0; /* True for an UPDATE or DELETE */

5506 u32 aSzIns = 0; / Sizes of inserted documents */

5507 u32 aSzDel = 0; / Sizes of deleted documents */

5508 int nChng = 0; /* Net change in number of documents */

5509 int bInsertDone = 0;

5510

5511 /* At this point it must be known if the %_stat table exists or not.

5512 ** So bHasStat may not be 2. */

5513 assert( p->bHasStat==0 \|\| p->bHasStat==1 );

5514

5515 assert( p->pSegments==0 );

5516 assert(

5517 nArg==1 /* DELETE operations */

5518 \|\| nArg==(2 + p->nColumn + 3) /* INSERT or UPDATE operations */

5519 );

5520

5521 /* Check for a "special" INSERT operation. One of the form:

5522 **

5523 ** INSERT INTO xyz(xyz) VALUES('command');

5524 */

5525 if( nArg>1

5526 && sqlite3_value_type(apVal[0])==SQLITE_NULL

5527 && sqlite3_value_type(apVal[p->nColumn+2])!=SQLITE_NULL

5528 ){

5529 rc = fts3SpecialInsert(p, apVal[p->nColumn+2]);

5530 goto update_out;

5531 }

5532

5533 if( nArg>1 && sqlite3_value_int(apVal[2 + p->nColumn + 2])<0 ){

5534 rc = SQLITE_CONSTRAINT;

5535 goto update_out;

5536 }

5537

5538 /* Allocate space to hold the change in document sizes */

5539 aSzDel = sqlite3_malloc( sizeof(aSzDel[0])(p->nColumn+1)2 );

5540 if( aSzDel==0 ){

5541 rc = SQLITE_NOMEM;

5542 goto update_out;

5543 }

5544 aSzIns = &aSzDel[p->nColumn+1];

5545 memset(aSzDel, 0, sizeof(aSzDel[0])(p->nColumn+1)2);

5546

5547 rc = fts3Writelock(p);

5548 if( rc!=SQLITE_OK ) goto update_out;

5549

5550 /* If this is an INSERT operation, or an UPDATE that modifies the rowid

5551 ** value, then this operation requires constraint handling.

5552 **

5553 ** If the on-conflict mode is REPLACE, this means that the existing row

5554 ** should be deleted from the database before inserting the new row. Or,

5555 ** if the on-conflict mode is other than REPLACE, then this method must

5556 ** detect the conflict and return SQLITE_CONSTRAINT before beginning to

5557 ** modify the database file.

5558 */

5559 if( nArg>1 && p->zContentTbl==0 ){

5560 /* Find the value object that holds the new rowid value. */

5561 sqlite3_value *pNewRowid = apVal[3+p->nColumn];

5562 if( sqlite3_value_type(pNewRowid)==SQLITE_NULL ){

5563 pNewRowid = apVal[1];

5564 }

5565

5566 if( sqlite3_value_type(pNewRowid)!=SQLITE_NULL && (

5567 sqlite3_value_type(apVal[0])==SQLITE_NULL

5568 \|\| sqlite3_value_int64(apVal[0])!=sqlite3_value_int64(pNewRowid)

5569 )){

5570 /* The new rowid is not NULL (in this case the rowid will be

5571 ** automatically assigned and there is no chance of a conflict), and

5572 ** the statement is either an INSERT or an UPDATE that modifies the

5573 ** rowid column. So if the conflict mode is REPLACE, then delete any

5574 ** existing row with rowid=pNewRowid.

5575 **

5576 ** Or, if the conflict mode is not REPLACE, insert the new record into

5577 ** the %_content table. If we hit the duplicate rowid constraint (or any

5578 ** other error) while doing so, return immediately.

5579 **

5580 ** This branch may also run if pNewRowid contains a value that cannot

5581 ** be losslessly converted to an integer. In this case, the eventual

5582 ** call to fts3InsertData() (either just below or further on in this

5583 ** function) will return SQLITE_MISMATCH. If fts3DeleteByRowid is

5584 ** invoked, it will delete zero rows (since no row will have

5585 ** docid=$pNewRowid if $pNewRowid is not an integer value).

5586 */

5587 if( sqlite3_vtab_on_conflict(p->db)==SQLITE_REPLACE ){

5588 rc = fts3DeleteByRowid(p, pNewRowid, &nChng, aSzDel);

5589 }else{

5590 rc = fts3InsertData(p, apVal, pRowid);

5591 bInsertDone = 1;

5592 }

5593 }

5594 }

5595 if( rc!=SQLITE_OK ){

5596 goto update_out;

5597 }

5598

5599 /* If this is a DELETE or UPDATE operation, remove the old record. */

5600 if( sqlite3_value_type(apVal[0])!=SQLITE_NULL ){

5601 assert( sqlite3_value_type(apVal[0])==SQLITE_INTEGER );

5602 rc = fts3DeleteByRowid(p, apVal[0], &nChng, aSzDel);

5603 isRemove = 1;

5604 }

5605

5606 /* If this is an INSERT or UPDATE operation, insert the new record. */

5607 if( nArg>1 && rc==SQLITE_OK ){

5608 int iLangid = sqlite3_value_int(apVal[2 + p->nColumn + 2]);

5609 if( bInsertDone==0 ){

5610 rc = fts3InsertData(p, apVal, pRowid);

5611 if( rc==SQLITE_CONSTRAINT && p->zContentTbl==0 ){

5612 rc = FTS_CORRUPT_VTAB;

5613 }

5614 }

5615 if( rc==SQLITE_OK && (!isRemove \|\| *pRowid!=p->iPrevDocid ) ){

5616 rc = fts3PendingTermsDocid(p, iLangid, *pRowid);

5617 }

5618 if( rc==SQLITE_OK ){

5619 assert( p->iPrevDocid==*pRowid );

5620 rc = fts3InsertTerms(p, iLangid, apVal, aSzIns);

5621 }

5622 if( p->bHasDocsize ){

5623 fts3InsertDocsize(&rc, p, aSzIns);

5624 }

5625 nChng++;

5626 }

5627

5628 if( p->bFts4 ){

5629 fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nChng);

5630 }

5631

5632 update_out:

5633 sqlite3_free(aSzDel);

5634 sqlite3Fts3SegmentsClose(p);

5635 return rc;

5636 }

5637

5638 /*

5639 ** Flush any data in the pending-terms hash table to disk. If successful,

5640 ** merge all segments in the database (including the new segment, if

5641 ** there was any data to flush) into a single segment.

5642 */

5643 int sqlite3Fts3Optimize(Fts3Table *p){

5644 int rc;

5645 rc = sqlite3_exec(p->db, "SAVEPOINT fts3", 0, 0, 0);

5646 if( rc==SQLITE_OK ){

5647 rc = fts3DoOptimize(p, 1);

5648 if( rc==SQLITE_OK \|\| rc==SQLITE_DONE ){

5649 int rc2 = sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);

5650 if( rc2!=SQLITE_OK ) rc = rc2;

5651 }else{

5652 sqlite3_exec(p->db, "ROLLBACK TO fts3", 0, 0, 0);

5653 sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);

5654 }

5655 }

5656 sqlite3Fts3SegmentsClose(p);

5657 return rc;

5658 }

5659

5660 #endif

OLD	NEW