Debian Codegraph @

ext/fts3/fts3_write.c

raw
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 #include <stdio.h>
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 = (4*1024)*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 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 sqlite3_int64 nData;
102 char *aData;
103 sqlite3_int64 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 ** Wrapper around sqlite3_prepare_v3() to ensure that SQLITE_PREPARE_FROM_DDL
278 ** is always set.
279 */
280 int sqlite3Fts3PrepareStmt(
281 Fts3Table *p, /* Prepare for this connection */
282 const char *zSql, /* SQL to prepare */
283 int bPersist, /* True to set SQLITE_PREPARE_PERSISTENT */
284 int bAllowVtab, /* True to omit SQLITE_PREPARE_NO_VTAB */
285 sqlite3_stmt **pp /* OUT: Prepared statement */
286 ){
287 int f = SQLITE_PREPARE_FROM_DDL
288 |((bAllowVtab==0) ? SQLITE_PREPARE_NO_VTAB : 0)
289 |(bPersist ? SQLITE_PREPARE_PERSISTENT : 0);
290
291 return sqlite3_prepare_v3(p->db, zSql, -1, f, pp, NULL);
292 }
293
294 /*
295 ** This function is used to obtain an SQLite prepared statement handle
296 ** for the statement identified by the second argument. If successful,
297 ** *pp is set to the requested statement handle and SQLITE_OK returned.
298 ** Otherwise, an SQLite error code is returned and *pp is set to 0.
299 **
300 ** If argument apVal is not NULL, then it must point to an array with
301 ** at least as many entries as the requested statement has bound
302 ** parameters. The values are bound to the statements parameters before
303 ** returning.
304 */
305 static int fts3SqlStmt(
306 Fts3Table *p, /* Virtual table handle */
307 int eStmt, /* One of the SQL_XXX constants above */
308 sqlite3_stmt **pp, /* OUT: Statement handle */
309 sqlite3_value **apVal /* Values to bind to statement */
310 ){
311 const char *azSql[] = {
312 /* 0 */ "DELETE FROM %Q.'%q_content' WHERE rowid = ?",
313 /* 1 */ "SELECT NOT EXISTS(SELECT docid FROM %Q.'%q_content' WHERE rowid!=?)",
314 /* 2 */ "DELETE FROM %Q.'%q_content'",
315 /* 3 */ "DELETE FROM %Q.'%q_segments'",
316 /* 4 */ "DELETE FROM %Q.'%q_segdir'",
317 /* 5 */ "DELETE FROM %Q.'%q_docsize'",
318 /* 6 */ "DELETE FROM %Q.'%q_stat'",
319 /* 7 */ "SELECT %s WHERE rowid=?",
320 /* 8 */ "SELECT (SELECT max(idx) FROM %Q.'%q_segdir' WHERE level = ?) + 1",
321 /* 9 */ "REPLACE INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)",
322 /* 10 */ "SELECT coalesce((SELECT max(blockid) FROM %Q.'%q_segments') + 1, 1)",
323 /* 11 */ "REPLACE INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)",
324
325 /* Return segments in order from oldest to newest.*/
326 /* 12 */ "SELECT idx, start_block, leaves_end_block, end_block, root "
327 "FROM %Q.'%q_segdir' WHERE level = ? ORDER BY idx ASC",
328 /* 13 */ "SELECT idx, start_block, leaves_end_block, end_block, root "
329 "FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?"
330 "ORDER BY level DESC, idx ASC",
331
332 /* 14 */ "SELECT count(*) FROM %Q.'%q_segdir' WHERE level = ?",
333 /* 15 */ "SELECT max(level) FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?",
334
335 /* 16 */ "DELETE FROM %Q.'%q_segdir' WHERE level = ?",
336 /* 17 */ "DELETE FROM %Q.'%q_segments' WHERE blockid BETWEEN ? AND ?",
337 /* 18 */ "INSERT INTO %Q.'%q_content' VALUES(%s)",
338 /* 19 */ "DELETE FROM %Q.'%q_docsize' WHERE docid = ?",
339 /* 20 */ "REPLACE INTO %Q.'%q_docsize' VALUES(?,?)",
340 /* 21 */ "SELECT size FROM %Q.'%q_docsize' WHERE docid=?",
341 /* 22 */ "SELECT value FROM %Q.'%q_stat' WHERE id=?",
342 /* 23 */ "REPLACE INTO %Q.'%q_stat' VALUES(?,?)",
343 /* 24 */ "",
344 /* 25 */ "",
345
346 /* 26 */ "DELETE FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?",
347 /* 27 */ "SELECT ? UNION SELECT level / (1024 * ?) FROM %Q.'%q_segdir'",
348
349 /* This statement is used to determine which level to read the input from
350 ** when performing an incremental merge. It returns the absolute level number
351 ** of the oldest level in the db that contains at least ? segments. Or,
352 ** if no level in the FTS index contains more than ? segments, the statement
353 ** returns zero rows. */
354 /* 28 */ "SELECT level, count(*) AS cnt FROM %Q.'%q_segdir' "
355 " GROUP BY level HAVING cnt>=?"
356 " ORDER BY (level %% 1024) ASC, 2 DESC LIMIT 1",
357
358 /* Estimate the upper limit on the number of leaf nodes in a new segment
359 ** created by merging the oldest :2 segments from absolute level :1. See
360 ** function sqlite3Fts3Incrmerge() for details. */
361 /* 29 */ "SELECT 2 * total(1 + leaves_end_block - start_block) "
362 " FROM (SELECT * FROM %Q.'%q_segdir' "
363 " WHERE level = ? ORDER BY idx ASC LIMIT ?"
364 " )",
365
366 /* SQL_DELETE_SEGDIR_ENTRY
367 ** Delete the %_segdir entry on absolute level :1 with index :2. */
368 /* 30 */ "DELETE FROM %Q.'%q_segdir' WHERE level = ? AND idx = ?",
369
370 /* SQL_SHIFT_SEGDIR_ENTRY
371 ** Modify the idx value for the segment with idx=:3 on absolute level :2
372 ** to :1. */
373 /* 31 */ "UPDATE %Q.'%q_segdir' SET idx = ? WHERE level=? AND idx=?",
374
375 /* SQL_SELECT_SEGDIR
376 ** Read a single entry from the %_segdir table. The entry from absolute
377 ** level :1 with index value :2. */
378 /* 32 */ "SELECT idx, start_block, leaves_end_block, end_block, root "
379 "FROM %Q.'%q_segdir' WHERE level = ? AND idx = ?",
380
381 /* SQL_CHOMP_SEGDIR
382 ** Update the start_block (:1) and root (:2) fields of the %_segdir
383 ** entry located on absolute level :3 with index :4. */
384 /* 33 */ "UPDATE %Q.'%q_segdir' SET start_block = ?, root = ?"
385 "WHERE level = ? AND idx = ?",
386
387 /* SQL_SEGMENT_IS_APPENDABLE
388 ** Return a single row if the segment with end_block=? is appendable. Or
389 ** no rows otherwise. */
390 /* 34 */ "SELECT 1 FROM %Q.'%q_segments' WHERE blockid=? AND block IS NULL",
391
392 /* SQL_SELECT_INDEXES
393 ** Return the list of valid segment indexes for absolute level ? */
394 /* 35 */ "SELECT idx FROM %Q.'%q_segdir' WHERE level=? ORDER BY 1 ASC",
395
396 /* SQL_SELECT_MXLEVEL
397 ** Return the largest relative level in the FTS index or indexes. */
398 /* 36 */ "SELECT max( level %% 1024 ) FROM %Q.'%q_segdir'",
399
400 /* Return segments in order from oldest to newest.*/
401 /* 37 */ "SELECT level, idx, end_block "
402 "FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ? "
403 "ORDER BY level DESC, idx ASC",
404
405 /* Update statements used while promoting segments */
406 /* 38 */ "UPDATE OR FAIL %Q.'%q_segdir' SET level=-1,idx=? "
407 "WHERE level=? AND idx=?",
408 /* 39 */ "UPDATE OR FAIL %Q.'%q_segdir' SET level=? WHERE level=-1"
409
410 };
411 int rc = SQLITE_OK;
412 sqlite3_stmt *pStmt;
413
414 assert( SizeofArray(azSql)==SizeofArray(p->aStmt) );
415 assert( eStmt<SizeofArray(azSql) && eStmt>=0 );
416
417 pStmt = p->aStmt[eStmt];
418 if( !pStmt ){
419 int bAllowVtab = 0;
420 char *zSql;
421 if( eStmt==SQL_CONTENT_INSERT ){
422 zSql = sqlite3_mprintf(azSql[eStmt], p->zDb, p->zName, p->zWriteExprlist);
423 }else if( eStmt==SQL_SELECT_CONTENT_BY_ROWID ){
424 bAllowVtab = 1;
425 zSql = sqlite3_mprintf(azSql[eStmt], p->zReadExprlist);
426 }else{
427 zSql = sqlite3_mprintf(azSql[eStmt], p->zDb, p->zName);
428 }
429 if( !zSql ){
430 rc = SQLITE_NOMEM;
431 }else{
432 rc = sqlite3Fts3PrepareStmt(p, zSql, 1, bAllowVtab, &pStmt);
433 sqlite3_free(zSql);
434 assert( rc==SQLITE_OK || pStmt==0 );
435 p->aStmt[eStmt] = pStmt;
436 }
437 }
438 if( apVal ){
439 int i;
440 int nParam = sqlite3_bind_parameter_count(pStmt);
441 for(i=0; rc==SQLITE_OK && i<nParam; i++){
442 rc = sqlite3_bind_value(pStmt, i+1, apVal[i]);
443 }
444 }
445 *pp = pStmt;
446 return rc;
447 }
448
449
450 static int fts3SelectDocsize(
451 Fts3Table *pTab, /* FTS3 table handle */
452 sqlite3_int64 iDocid, /* Docid to bind for SQL_SELECT_DOCSIZE */
453 sqlite3_stmt **ppStmt /* OUT: Statement handle */
454 ){
455 sqlite3_stmt *pStmt = 0; /* Statement requested from fts3SqlStmt() */
456 int rc; /* Return code */
457
458 rc = fts3SqlStmt(pTab, SQL_SELECT_DOCSIZE, &pStmt, 0);
459 if( rc==SQLITE_OK ){
460 sqlite3_bind_int64(pStmt, 1, iDocid);
461 rc = sqlite3_step(pStmt);
462 if( rc!=SQLITE_ROW || sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB ){
463 rc = sqlite3_reset(pStmt);
464 if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;
465 pStmt = 0;
466 }else{
467 rc = SQLITE_OK;
468 }
469 }
470
471 *ppStmt = pStmt;
472 return rc;
473 }
474
475 int sqlite3Fts3SelectDoctotal(
476 Fts3Table *pTab, /* Fts3 table handle */
477 sqlite3_stmt **ppStmt /* OUT: Statement handle */
478 ){
479 sqlite3_stmt *pStmt = 0;
480 int rc;
481 rc = fts3SqlStmt(pTab, SQL_SELECT_STAT, &pStmt, 0);
482 if( rc==SQLITE_OK ){
483 sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
484 if( sqlite3_step(pStmt)!=SQLITE_ROW
485 || sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB
486 ){
487 rc = sqlite3_reset(pStmt);
488 if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;
489 pStmt = 0;
490 }
491 }
492 *ppStmt = pStmt;
493 return rc;
494 }
495
496 int sqlite3Fts3SelectDocsize(
497 Fts3Table *pTab, /* Fts3 table handle */
498 sqlite3_int64 iDocid, /* Docid to read size data for */
499 sqlite3_stmt **ppStmt /* OUT: Statement handle */
500 ){
501 return fts3SelectDocsize(pTab, iDocid, ppStmt);
502 }
503
504 /*
505 ** Similar to fts3SqlStmt(). Except, after binding the parameters in
506 ** array apVal[] to the SQL statement identified by eStmt, the statement
507 ** is executed.
508 **
509 ** Returns SQLITE_OK if the statement is successfully executed, or an
510 ** SQLite error code otherwise.
511 */
512 static void fts3SqlExec(
513 int *pRC, /* Result code */
514 Fts3Table *p, /* The FTS3 table */
515 int eStmt, /* Index of statement to evaluate */
516 sqlite3_value **apVal /* Parameters to bind */
517 ){
518 sqlite3_stmt *pStmt;
519 int rc;
520 if( *pRC ) return;
521 rc = fts3SqlStmt(p, eStmt, &pStmt, apVal);
522 if( rc==SQLITE_OK ){
523 sqlite3_step(pStmt);
524 rc = sqlite3_reset(pStmt);
525 }
526 *pRC = rc;
527 }
528
529
530 /*
531 ** This function ensures that the caller has obtained an exclusive
532 ** shared-cache table-lock on the %_segdir table. This is required before
533 ** writing data to the fts3 table. If this lock is not acquired first, then
534 ** the caller may end up attempting to take this lock as part of committing
535 ** a transaction, causing SQLite to return SQLITE_LOCKED or
536 ** LOCKED_SHAREDCACHEto a COMMIT command.
537 **
538 ** It is best to avoid this because if FTS3 returns any error when
539 ** committing a transaction, the whole transaction will be rolled back.
540 ** And this is not what users expect when they get SQLITE_LOCKED_SHAREDCACHE.
541 ** It can still happen if the user locks the underlying tables directly
542 ** instead of accessing them via FTS.
543 */
544 static int fts3Writelock(Fts3Table *p){
545 int rc = SQLITE_OK;
546
547 if( p->nPendingData==0 ){
548 sqlite3_stmt *pStmt;
549 rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_LEVEL, &pStmt, 0);
550 if( rc==SQLITE_OK ){
551 sqlite3_bind_null(pStmt, 1);
552 sqlite3_step(pStmt);
553 rc = sqlite3_reset(pStmt);
554 }
555 }
556
557 return rc;
558 }
559
560 /*
561 ** FTS maintains a separate indexes for each language-id (a 32-bit integer).
562 ** Within each language id, a separate index is maintained to store the
563 ** document terms, and each configured prefix size (configured the FTS
564 ** "prefix=" option). And each index consists of multiple levels ("relative
565 ** levels").
566 **
567 ** All three of these values (the language id, the specific index and the
568 ** level within the index) are encoded in 64-bit integer values stored
569 ** in the %_segdir table on disk. This function is used to convert three
570 ** separate component values into the single 64-bit integer value that
571 ** can be used to query the %_segdir table.
572 **
573 ** Specifically, each language-id/index combination is allocated 1024
574 ** 64-bit integer level values ("absolute levels"). The main terms index
575 ** for language-id 0 is allocate values 0-1023. The first prefix index
576 ** (if any) for language-id 0 is allocated values 1024-2047. And so on.
577 ** Language 1 indexes are allocated immediately following language 0.
578 **
579 ** So, for a system with nPrefix prefix indexes configured, the block of
580 ** absolute levels that corresponds to language-id iLangid and index
581 ** iIndex starts at absolute level ((iLangid * (nPrefix+1) + iIndex) * 1024).
582 */
583 static sqlite3_int64 getAbsoluteLevel(
584 Fts3Table *p, /* FTS3 table handle */
585 int iLangid, /* Language id */
586 int iIndex, /* Index in p->aIndex[] */
587 int iLevel /* Level of segments */
588 ){
589 sqlite3_int64 iBase; /* First absolute level for iLangid/iIndex */
590 assert_fts3_nc( iLangid>=0 );
591 assert( p->nIndex>0 );
592 assert( iIndex>=0 && iIndex<p->nIndex );
593
594 iBase = ((sqlite3_int64)iLangid * p->nIndex + iIndex) * FTS3_SEGDIR_MAXLEVEL;
595 return iBase + iLevel;
596 }
597
598 /*
599 ** Set *ppStmt to a statement handle that may be used to iterate through
600 ** all rows in the %_segdir table, from oldest to newest. If successful,
601 ** return SQLITE_OK. If an error occurs while preparing the statement,
602 ** return an SQLite error code.
603 **
604 ** There is only ever one instance of this SQL statement compiled for
605 ** each FTS3 table.
606 **
607 ** The statement returns the following columns from the %_segdir table:
608 **
609 ** 0: idx
610 ** 1: start_block
611 ** 2: leaves_end_block
612 ** 3: end_block
613 ** 4: root
614 */
615 int sqlite3Fts3AllSegdirs(
616 Fts3Table *p, /* FTS3 table */
617 int iLangid, /* Language being queried */
618 int iIndex, /* Index for p->aIndex[] */
619 int iLevel, /* Level to select (relative level) */
620 sqlite3_stmt **ppStmt /* OUT: Compiled statement */
621 ){
622 int rc;
623 sqlite3_stmt *pStmt = 0;
624
625 assert( iLevel==FTS3_SEGCURSOR_ALL || iLevel>=0 );
626 assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
627 assert( iIndex>=0 && iIndex<p->nIndex );
628
629 if( iLevel<0 ){
630 /* "SELECT * FROM %_segdir WHERE level BETWEEN ? AND ? ORDER BY ..." */
631 rc = fts3SqlStmt(p, SQL_SELECT_LEVEL_RANGE, &pStmt, 0);
632 if( rc==SQLITE_OK ){
633 sqlite3_bind_int64(pStmt, 1, getAbsoluteLevel(p, iLangid, iIndex, 0));
634 sqlite3_bind_int64(pStmt, 2,
635 getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1)
636 );
637 }
638 }else{
639 /* "SELECT * FROM %_segdir WHERE level = ? ORDER BY ..." */
640 rc = fts3SqlStmt(p, SQL_SELECT_LEVEL, &pStmt, 0);
641 if( rc==SQLITE_OK ){
642 sqlite3_bind_int64(pStmt, 1, getAbsoluteLevel(p, iLangid, iIndex,iLevel));
643 }
644 }
645 *ppStmt = pStmt;
646 return rc;
647 }
648
649
650 /*
651 ** Append a single varint to a PendingList buffer. SQLITE_OK is returned
652 ** if successful, or an SQLite error code otherwise.
653 **
654 ** This function also serves to allocate the PendingList structure itself.
655 ** For example, to create a new PendingList structure containing two
656 ** varints:
657 **
658 ** PendingList *p = 0;
659 ** fts3PendingListAppendVarint(&p, 1);
660 ** fts3PendingListAppendVarint(&p, 2);
661 */
662 static int fts3PendingListAppendVarint(
663 PendingList **pp, /* IN/OUT: Pointer to PendingList struct */
664 sqlite3_int64 i /* Value to append to data */
665 ){
666 PendingList *p = *pp;
667
668 /* Allocate or grow the PendingList as required. */
669 if( !p ){
670 p = sqlite3_malloc64(sizeof(*p) + 100);
671 if( !p ){
672 return SQLITE_NOMEM;
673 }
674 p->nSpace = 100;
675 p->aData = (char *)&p[1];
676 p->nData = 0;
677 }
678 else if( p->nData+FTS3_VARINT_MAX+1>p->nSpace ){
679 i64 nNew = p->nSpace * 2;
680 p = sqlite3_realloc64(p, sizeof(*p) + nNew);
681 if( !p ){
682 sqlite3_free(*pp);
683 *pp = 0;
684 return SQLITE_NOMEM;
685 }
686 p->nSpace = (int)nNew;
687 p->aData = (char *)&p[1];
688 }
689
690 /* Append the new serialized varint to the end of the list. */
691 p->nData += sqlite3Fts3PutVarint(&p->aData[p->nData], i);
692 p->aData[p->nData] = '\0';
693 *pp = p;
694 return SQLITE_OK;
695 }
696
697 /*
698 ** Add a docid/column/position entry to a PendingList structure. Non-zero
699 ** is returned if the structure is sqlite3_realloced as part of adding
700 ** the entry. Otherwise, zero.
701 **
702 ** If an OOM error occurs, *pRc is set to SQLITE_NOMEM before returning.
703 ** Zero is always returned in this case. Otherwise, if no OOM error occurs,
704 ** it is set to SQLITE_OK.
705 */
706 static int fts3PendingListAppend(
707 PendingList **pp, /* IN/OUT: PendingList structure */
708 sqlite3_int64 iDocid, /* Docid for entry to add */
709 sqlite3_int64 iCol, /* Column for entry to add */
710 sqlite3_int64 iPos, /* Position of term for entry to add */
711 int *pRc /* OUT: Return code */
712 ){
713 PendingList *p = *pp;
714 int rc = SQLITE_OK;
715
716 assert( !p || p->iLastDocid<=iDocid );
717
718 if( !p || p->iLastDocid!=iDocid ){
719 u64 iDelta = (u64)iDocid - (u64)(p ? p->iLastDocid : 0);
720 if( p ){
721 assert( p->nData<p->nSpace );
722 assert( p->aData[p->nData]==0 );
723 p->nData++;
724 }
725 if( SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, iDelta)) ){
726 goto pendinglistappend_out;
727 }
728 p->iLastCol = -1;
729 p->iLastPos = 0;
730 p->iLastDocid = iDocid;
731 }
732 if( iCol>0 && p->iLastCol!=iCol ){
733 if( SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, 1))
734 || SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, iCol))
735 ){
736 goto pendinglistappend_out;
737 }
738 p->iLastCol = iCol;
739 p->iLastPos = 0;
740 }
741 if( iCol>=0 ){
742 assert( iPos>p->iLastPos || (iPos==0 && p->iLastPos==0) );
743 rc = fts3PendingListAppendVarint(&p, 2+iPos-p->iLastPos);
744 if( rc==SQLITE_OK ){
745 p->iLastPos = iPos;
746 }
747 }
748
749 pendinglistappend_out:
750 *pRc = rc;
751 if( p!=*pp ){
752 *pp = p;
753 return 1;
754 }
755 return 0;
756 }
757
758 /*
759 ** Free a PendingList object allocated by fts3PendingListAppend().
760 */
761 static void fts3PendingListDelete(PendingList *pList){
762 sqlite3_free(pList);
763 }
764
765 /*
766 ** Add an entry to one of the pending-terms hash tables.
767 */
768 static int fts3PendingTermsAddOne(
769 Fts3Table *p,
770 int iCol,
771 int iPos,
772 Fts3Hash *pHash, /* Pending terms hash table to add entry to */
773 const char *zToken,
774 int nToken
775 ){
776 PendingList *pList;
777 int rc = SQLITE_OK;
778
779 pList = (PendingList *)fts3HashFind(pHash, zToken, nToken);
780 if( pList ){
781 assert( (i64)pList->nData+(i64)nToken+(i64)sizeof(Fts3HashElem)
782 <= (i64)p->nPendingData );
783 p->nPendingData -= (int)(pList->nData + nToken + sizeof(Fts3HashElem));
784 }
785 if( fts3PendingListAppend(&pList, p->iPrevDocid, iCol, iPos, &rc) ){
786 if( pList==fts3HashInsert(pHash, zToken, nToken, pList) ){
787 /* Malloc failed while inserting the new entry. This can only
788 ** happen if there was no previous entry for this token.
789 */
790 assert( 0==fts3HashFind(pHash, zToken, nToken) );
791 sqlite3_free(pList);
792 rc = SQLITE_NOMEM;
793 }
794 }
795 if( rc==SQLITE_OK ){
796 assert( (i64)p->nPendingData + pList->nData + nToken
797 + sizeof(Fts3HashElem) <= 0x3fffffff );
798 p->nPendingData += (int)(pList->nData + nToken + sizeof(Fts3HashElem));
799 }
800 return rc;
801 }
802
803 /*
804 ** Tokenize the nul-terminated string zText and add all tokens to the
805 ** pending-terms hash-table. The docid used is that currently stored in
806 ** p->iPrevDocid, and the column is specified by argument iCol.
807 **
808 ** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.
809 */
810 static int fts3PendingTermsAdd(
811 Fts3Table *p, /* Table into which text will be inserted */
812 int iLangid, /* Language id to use */
813 const char *zText, /* Text of document to be inserted */
814 int iCol, /* Column into which text is being inserted */
815 u32 *pnWord /* IN/OUT: Incr. by number tokens inserted */
816 ){
817 int rc;
818 int iStart = 0;
819 int iEnd = 0;
820 int iPos = 0;
821 int nWord = 0;
822
823 char const *zToken;
824 int nToken = 0;
825
826 sqlite3_tokenizer *pTokenizer = p->pTokenizer;
827 sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;
828 sqlite3_tokenizer_cursor *pCsr;
829 int (*xNext)(sqlite3_tokenizer_cursor *pCursor,
830 const char**,int*,int*,int*,int*);
831
832 assert( pTokenizer && pModule );
833
834 /* If the user has inserted a NULL value, this function may be called with
835 ** zText==0. In this case, add zero token entries to the hash table and
836 ** return early. */
837 if( zText==0 ){
838 *pnWord = 0;
839 return SQLITE_OK;
840 }
841
842 rc = sqlite3Fts3OpenTokenizer(pTokenizer, iLangid, zText, -1, &pCsr);
843 if( rc!=SQLITE_OK ){
844 return rc;
845 }
846
847 xNext = pModule->xNext;
848 while( SQLITE_OK==rc
849 && SQLITE_OK==(rc = xNext(pCsr, &zToken, &nToken, &iStart, &iEnd, &iPos))
850 ){
851 int i;
852 if( iPos>=nWord ) nWord = iPos+1;
853
854 /* Positions cannot be negative; we use -1 as a terminator internally.
855 ** Tokens must have a non-zero length.
856 */
857 if( iPos<0 || !zToken || nToken<=0 ){
858 rc = SQLITE_ERROR;
859 break;
860 }
861
862 /* Add the term to the terms index */
863 rc = fts3PendingTermsAddOne(
864 p, iCol, iPos, &p->aIndex[0].hPending, zToken, nToken
865 );
866
867 /* Add the term to each of the prefix indexes that it is not too
868 ** short for. */
869 for(i=1; rc==SQLITE_OK && i<p->nIndex; i++){
870 struct Fts3Index *pIndex = &p->aIndex[i];
871 if( nToken<pIndex->nPrefix ) continue;
872 rc = fts3PendingTermsAddOne(
873 p, iCol, iPos, &pIndex->hPending, zToken, pIndex->nPrefix
874 );
875 }
876 }
877
878 pModule->xClose(pCsr);
879 *pnWord += nWord;
880 return (rc==SQLITE_DONE ? SQLITE_OK : rc);
881 }
882
883 /*
884 ** Calling this function indicates that subsequent calls to
885 ** fts3PendingTermsAdd() are to add term/position-list pairs for the
886 ** contents of the document with docid iDocid.
887 */
888 static int fts3PendingTermsDocid(
889 Fts3Table *p, /* Full-text table handle */
890 int bDelete, /* True if this op is a delete */
891 int iLangid, /* Language id of row being written */
892 sqlite_int64 iDocid /* Docid of row being written */
893 ){
894 assert( iLangid>=0 );
895 assert( bDelete==1 || bDelete==0 );
896
897 /* TODO(shess) Explore whether partially flushing the buffer on
898 ** forced-flush would provide better performance. I suspect that if
899 ** we ordered the doclists by size and flushed the largest until the
900 ** buffer was half empty, that would let the less frequent terms
901 ** generate longer doclists.
902 */
903 if( iDocid<p->iPrevDocid
904 || (iDocid==p->iPrevDocid && p->bPrevDelete==0)
905 || p->iPrevLangid!=iLangid
906 || p->nPendingData>p->nMaxPendingData
907 ){
908 int rc = sqlite3Fts3PendingTermsFlush(p);
909 if( rc!=SQLITE_OK ) return rc;
910 }
911 p->iPrevDocid = iDocid;
912 p->iPrevLangid = iLangid;
913 p->bPrevDelete = bDelete;
914 return SQLITE_OK;
915 }
916
917 /*
918 ** Discard the contents of the pending-terms hash tables.
919 */
920 void sqlite3Fts3PendingTermsClear(Fts3Table *p){
921 int i;
922 for(i=0; i<p->nIndex; i++){
923 Fts3HashElem *pElem;
924 Fts3Hash *pHash = &p->aIndex[i].hPending;
925 for(pElem=fts3HashFirst(pHash); pElem; pElem=fts3HashNext(pElem)){
926 PendingList *pList = (PendingList *)fts3HashData(pElem);
927 fts3PendingListDelete(pList);
928 }
929 fts3HashClear(pHash);
930 }
931 p->nPendingData = 0;
932 }
933
934 /*
935 ** This function is called by the xUpdate() method as part of an INSERT
936 ** operation. It adds entries for each term in the new record to the
937 ** pendingTerms hash table.
938 **
939 ** Argument apVal is the same as the similarly named argument passed to
940 ** fts3InsertData(). Parameter iDocid is the docid of the new row.
941 */
942 static int fts3InsertTerms(
943 Fts3Table *p,
944 int iLangid,
945 sqlite3_value **apVal,
946 u32 *aSz
947 ){
948 int i; /* Iterator variable */
949 for(i=2; i<p->nColumn+2; i++){
950 int iCol = i-2;
951 if( p->abNotindexed[iCol]==0 ){
952 const char *zText = (const char *)sqlite3_value_text(apVal[i]);
953 int rc = fts3PendingTermsAdd(p, iLangid, zText, iCol, &aSz[iCol]);
954 if( rc!=SQLITE_OK ){
955 return rc;
956 }
957 aSz[p->nColumn] += sqlite3_value_bytes(apVal[i]);
958 }
959 }
960 return SQLITE_OK;
961 }
962
963 /*
964 ** This function is called by the xUpdate() method for an INSERT operation.
965 ** The apVal parameter is passed a copy of the apVal argument passed by
966 ** SQLite to the xUpdate() method. i.e:
967 **
968 ** apVal[0] Not used for INSERT.
969 ** apVal[1] rowid
970 ** apVal[2] Left-most user-defined column
971 ** ...
972 ** apVal[p->nColumn+1] Right-most user-defined column
973 ** apVal[p->nColumn+2] Hidden column with same name as table
974 ** apVal[p->nColumn+3] Hidden "docid" column (alias for rowid)
975 ** apVal[p->nColumn+4] Hidden languageid column
976 */
977 static int fts3InsertData(
978 Fts3Table *p, /* Full-text table */
979 sqlite3_value **apVal, /* Array of values to insert */
980 sqlite3_int64 *piDocid /* OUT: Docid for row just inserted */
981 ){
982 int rc; /* Return code */
983 sqlite3_stmt *pContentInsert; /* INSERT INTO %_content VALUES(...) */
984
985 if( p->zContentTbl ){
986 sqlite3_value *pRowid = apVal[p->nColumn+3];
987 if( sqlite3_value_type(pRowid)==SQLITE_NULL ){
988 pRowid = apVal[1];
989 }
990 if( sqlite3_value_type(pRowid)!=SQLITE_INTEGER ){
991 return SQLITE_CONSTRAINT;
992 }
993 *piDocid = sqlite3_value_int64(pRowid);
994 return SQLITE_OK;
995 }
996
997 /* Locate the statement handle used to insert data into the %_content
998 ** table. The SQL for this statement is:
999 **
1000 ** INSERT INTO %_content VALUES(?, ?, ?, ...)
1001 **
1002 ** The statement features N '?' variables, where N is the number of user
1003 ** defined columns in the FTS3 table, plus one for the docid field.
1004 */
1005 rc = fts3SqlStmt(p, SQL_CONTENT_INSERT, &pContentInsert, &apVal[1]);
1006 if( rc==SQLITE_OK && p->zLanguageid ){
1007 rc = sqlite3_bind_int(
1008 pContentInsert, p->nColumn+2,
1009 sqlite3_value_int(apVal[p->nColumn+4])
1010 );
1011 }
1012 if( rc!=SQLITE_OK ) return rc;
1013
1014 /* There is a quirk here. The users INSERT statement may have specified
1015 ** a value for the "rowid" field, for the "docid" field, or for both.
1016 ** Which is a problem, since "rowid" and "docid" are aliases for the
1017 ** same value. For example:
1018 **
1019 ** INSERT INTO fts3tbl(rowid, docid) VALUES(1, 2);
1020 **
1021 ** In FTS3, this is an error. It is an error to specify non-NULL values
1022 ** for both docid and some other rowid alias.
1023 */
1024 if( SQLITE_NULL!=sqlite3_value_type(apVal[3+p->nColumn]) ){
1025 if( SQLITE_NULL==sqlite3_value_type(apVal[0])
1026 && SQLITE_NULL!=sqlite3_value_type(apVal[1])
1027 ){
1028 /* A rowid/docid conflict. */
1029 return SQLITE_ERROR;
1030 }
1031 rc = sqlite3_bind_value(pContentInsert, 1, apVal[3+p->nColumn]);
1032 if( rc!=SQLITE_OK ) return rc;
1033 }
1034
1035 /* Execute the statement to insert the record. Set *piDocid to the
1036 ** new docid value.
1037 */
1038 sqlite3_step(pContentInsert);
1039 rc = sqlite3_reset(pContentInsert);
1040
1041 *piDocid = sqlite3_last_insert_rowid(p->db);
1042 return rc;
1043 }
1044
1045
1046
1047 /*
1048 ** Remove all data from the FTS3 table. Clear the hash table containing
1049 ** pending terms.
1050 */
1051 static int fts3DeleteAll(Fts3Table *p, int bContent){
1052 int rc = SQLITE_OK; /* Return code */
1053
1054 /* Discard the contents of the pending-terms hash table. */
1055 sqlite3Fts3PendingTermsClear(p);
1056
1057 /* Delete everything from the shadow tables. Except, leave %_content as
1058 ** is if bContent is false. */
1059 assert( p->zContentTbl==0 || bContent==0 );
1060 if( bContent ) fts3SqlExec(&rc, p, SQL_DELETE_ALL_CONTENT, 0);
1061 fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGMENTS, 0);
1062 fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGDIR, 0);
1063 if( p->bHasDocsize ){
1064 fts3SqlExec(&rc, p, SQL_DELETE_ALL_DOCSIZE, 0);
1065 }
1066 if( p->bHasStat ){
1067 fts3SqlExec(&rc, p, SQL_DELETE_ALL_STAT, 0);
1068 }
1069 return rc;
1070 }
1071
1072 /*
1073 **
1074 */
1075 static int langidFromSelect(Fts3Table *p, sqlite3_stmt *pSelect){
1076 int iLangid = 0;
1077 if( p->zLanguageid ) iLangid = sqlite3_column_int(pSelect, p->nColumn+1);
1078 return iLangid;
1079 }
1080
1081 /*
1082 ** The first element in the apVal[] array is assumed to contain the docid
1083 ** (an integer) of a row about to be deleted. Remove all terms from the
1084 ** full-text index.
1085 */
1086 static void fts3DeleteTerms(
1087 int *pRC, /* Result code */
1088 Fts3Table *p, /* The FTS table to delete from */
1089 sqlite3_value *pRowid, /* The docid to be deleted */
1090 u32 *aSz, /* Sizes of deleted document written here */
1091 int *pbFound /* OUT: Set to true if row really does exist */
1092 ){
1093 int rc;
1094 sqlite3_stmt *pSelect;
1095
1096 assert( *pbFound==0 );
1097 if( *pRC ) return;
1098 rc = fts3SqlStmt(p, SQL_SELECT_CONTENT_BY_ROWID, &pSelect, &pRowid);
1099 if( rc==SQLITE_OK ){
1100 if( SQLITE_ROW==sqlite3_step(pSelect) ){
1101 int i;
1102 int iLangid = langidFromSelect(p, pSelect);
1103 i64 iDocid = sqlite3_column_int64(pSelect, 0);
1104 rc = fts3PendingTermsDocid(p, 1, iLangid, iDocid);
1105 for(i=1; rc==SQLITE_OK && i<=p->nColumn; i++){
1106 int iCol = i-1;
1107 if( p->abNotindexed[iCol]==0 ){
1108 const char *zText = (const char *)sqlite3_column_text(pSelect, i);
1109 rc = fts3PendingTermsAdd(p, iLangid, zText, -1, &aSz[iCol]);
1110 aSz[p->nColumn] += sqlite3_column_bytes(pSelect, i);
1111 }
1112 }
1113 if( rc!=SQLITE_OK ){
1114 sqlite3_reset(pSelect);
1115 *pRC = rc;
1116 return;
1117 }
1118 *pbFound = 1;
1119 }
1120 rc = sqlite3_reset(pSelect);
1121 }else{
1122 sqlite3_reset(pSelect);
1123 }
1124 *pRC = rc;
1125 }
1126
1127 /*
1128 ** Forward declaration to account for the circular dependency between
1129 ** functions fts3SegmentMerge() and fts3AllocateSegdirIdx().
1130 */
1131 static int fts3SegmentMerge(Fts3Table *, int, int, int);
1132
1133 /*
1134 ** This function allocates a new level iLevel index in the segdir table.
1135 ** Usually, indexes are allocated within a level sequentially starting
1136 ** with 0, so the allocated index is one greater than the value returned
1137 ** by:
1138 **
1139 ** SELECT max(idx) FROM %_segdir WHERE level = :iLevel
1140 **
1141 ** However, if there are already FTS3_MERGE_COUNT indexes at the requested
1142 ** level, they are merged into a single level (iLevel+1) segment and the
1143 ** allocated index is 0.
1144 **
1145 ** If successful, *piIdx is set to the allocated index slot and SQLITE_OK
1146 ** returned. Otherwise, an SQLite error code is returned.
1147 */
1148 static int fts3AllocateSegdirIdx(
1149 Fts3Table *p,
1150 int iLangid, /* Language id */
1151 int iIndex, /* Index for p->aIndex */
1152 int iLevel,
1153 int *piIdx
1154 ){
1155 int rc; /* Return Code */
1156 sqlite3_stmt *pNextIdx; /* Query for next idx at level iLevel */
1157 int iNext = 0; /* Result of query pNextIdx */
1158
1159 assert( iLangid>=0 );
1160 assert( p->nIndex>=1 );
1161
1162 /* Set variable iNext to the next available segdir index at level iLevel. */
1163 rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pNextIdx, 0);
1164 if( rc==SQLITE_OK ){
1165 sqlite3_bind_int64(
1166 pNextIdx, 1, getAbsoluteLevel(p, iLangid, iIndex, iLevel)
1167 );
1168 if( SQLITE_ROW==sqlite3_step(pNextIdx) ){
1169 iNext = sqlite3_column_int(pNextIdx, 0);
1170 }
1171 rc = sqlite3_reset(pNextIdx);
1172 }
1173
1174 if( rc==SQLITE_OK ){
1175 /* If iNext is FTS3_MERGE_COUNT, indicating that level iLevel is already
1176 ** full, merge all segments in level iLevel into a single iLevel+1
1177 ** segment and allocate (newly freed) index 0 at level iLevel. Otherwise,
1178 ** if iNext is less than FTS3_MERGE_COUNT, allocate index iNext.
1179 */
1180 if( iNext>=MergeCount(p) ){
1181 fts3LogMerge(16, getAbsoluteLevel(p, iLangid, iIndex, iLevel));
1182 rc = fts3SegmentMerge(p, iLangid, iIndex, iLevel);
1183 *piIdx = 0;
1184 }else{
1185 *piIdx = iNext;
1186 }
1187 }
1188
1189 return rc;
1190 }
1191
1192 /*
1193 ** The %_segments table is declared as follows:
1194 **
1195 ** CREATE TABLE %_segments(blockid INTEGER PRIMARY KEY, block BLOB)
1196 **
1197 ** This function reads data from a single row of the %_segments table. The
1198 ** specific row is identified by the iBlockid parameter. If paBlob is not
1199 ** NULL, then a buffer is allocated using sqlite3_malloc() and populated
1200 ** with the contents of the blob stored in the "block" column of the
1201 ** identified table row is. Whether or not paBlob is NULL, *pnBlob is set
1202 ** to the size of the blob in bytes before returning.
1203 **
1204 ** If an error occurs, or the table does not contain the specified row,
1205 ** an SQLite error code is returned. Otherwise, SQLITE_OK is returned. If
1206 ** paBlob is non-NULL, then it is the responsibility of the caller to
1207 ** eventually free the returned buffer.
1208 **
1209 ** This function may leave an open sqlite3_blob* handle in the
1210 ** Fts3Table.pSegments variable. This handle is reused by subsequent calls
1211 ** to this function. The handle may be closed by calling the
1212 ** sqlite3Fts3SegmentsClose() function. Reusing a blob handle is a handy
1213 ** performance improvement, but the blob handle should always be closed
1214 ** before control is returned to the user (to prevent a lock being held
1215 ** on the database file for longer than necessary). Thus, any virtual table
1216 ** method (xFilter etc.) that may directly or indirectly call this function
1217 ** must call sqlite3Fts3SegmentsClose() before returning.
1218 */
1219 int sqlite3Fts3ReadBlock(
1220 Fts3Table *p, /* FTS3 table handle */
1221 sqlite3_int64 iBlockid, /* Access the row with blockid=$iBlockid */
1222 char **paBlob, /* OUT: Blob data in malloc'd buffer */
1223 int *pnBlob, /* OUT: Size of blob data */
1224 int *pnLoad /* OUT: Bytes actually loaded */
1225 ){
1226 int rc; /* Return code */
1227
1228 /* pnBlob must be non-NULL. paBlob may be NULL or non-NULL. */
1229 assert( pnBlob );
1230
1231 if( p->pSegments ){
1232 rc = sqlite3_blob_reopen(p->pSegments, iBlockid);
1233 }else{
1234 if( 0==p->zSegmentsTbl ){
1235 p->zSegmentsTbl = sqlite3_mprintf("%s_segments", p->zName);
1236 if( 0==p->zSegmentsTbl ) return SQLITE_NOMEM;
1237 }
1238 rc = sqlite3_blob_open(
1239 p->db, p->zDb, p->zSegmentsTbl, "block", iBlockid, 0, &p->pSegments
1240 );
1241 }
1242
1243 if( rc==SQLITE_OK ){
1244 int nByte = sqlite3_blob_bytes(p->pSegments);
1245 *pnBlob = nByte;
1246 if( paBlob ){
1247 char *aByte = sqlite3_malloc64((i64)nByte + FTS3_NODE_PADDING);
1248 if( !aByte ){
1249 rc = SQLITE_NOMEM;
1250 }else{
1251 if( pnLoad && nByte>(FTS3_NODE_CHUNK_THRESHOLD) ){
1252 nByte = FTS3_NODE_CHUNKSIZE;
1253 *pnLoad = nByte;
1254 }
1255 rc = sqlite3_blob_read(p->pSegments, aByte, nByte, 0);
1256 memset(&aByte[nByte], 0, FTS3_NODE_PADDING);
1257 if( rc!=SQLITE_OK ){
1258 sqlite3_free(aByte);
1259 aByte = 0;
1260 }
1261 }
1262 *paBlob = aByte;
1263 }
1264 }else if( rc==SQLITE_ERROR ){
1265 rc = FTS_CORRUPT_VTAB;
1266 }
1267
1268 return rc;
1269 }
1270
1271 /*
1272 ** Close the blob handle at p->pSegments, if it is open. See comments above
1273 ** the sqlite3Fts3ReadBlock() function for details.
1274 */
1275 void sqlite3Fts3SegmentsClose(Fts3Table *p){
1276 sqlite3_blob_close(p->pSegments);
1277 p->pSegments = 0;
1278 }
1279
1280 static int fts3SegReaderIncrRead(Fts3SegReader *pReader){
1281 int nRead; /* Number of bytes to read */
1282 int rc; /* Return code */
1283
1284 nRead = MIN(pReader->nNode - pReader->nPopulate, FTS3_NODE_CHUNKSIZE);
1285 rc = sqlite3_blob_read(
1286 pReader->pBlob,
1287 &pReader->aNode[pReader->nPopulate],
1288 nRead,
1289 pReader->nPopulate
1290 );
1291
1292 if( rc==SQLITE_OK ){
1293 pReader->nPopulate += nRead;
1294 memset(&pReader->aNode[pReader->nPopulate], 0, FTS3_NODE_PADDING);
1295 if( pReader->nPopulate==pReader->nNode ){
1296 sqlite3_blob_close(pReader->pBlob);
1297 pReader->pBlob = 0;
1298 pReader->nPopulate = 0;
1299 }
1300 }
1301 return rc;
1302 }
1303
1304 static int fts3SegReaderRequire(Fts3SegReader *pReader, char *pFrom, int nByte){
1305 int rc = SQLITE_OK;
1306 assert( !pReader->pBlob
1307 || (pFrom>=pReader->aNode && pFrom<&pReader->aNode[pReader->nNode])
1308 );
1309 while( pReader->pBlob && rc==SQLITE_OK
1310 && (pFrom - pReader->aNode + nByte)>pReader->nPopulate
1311 ){
1312 rc = fts3SegReaderIncrRead(pReader);
1313 }
1314 return rc;
1315 }
1316
1317 /*
1318 ** Set an Fts3SegReader cursor to point at EOF.
1319 */
1320 static void fts3SegReaderSetEof(Fts3SegReader *pSeg){
1321 if( !fts3SegReaderIsRootOnly(pSeg) ){
1322 sqlite3_free(pSeg->aNode);
1323 sqlite3_blob_close(pSeg->pBlob);
1324 pSeg->pBlob = 0;
1325 }
1326 pSeg->aNode = 0;
1327 }
1328
1329 /*
1330 ** Move the iterator passed as the first argument to the next term in the
1331 ** segment. If successful, SQLITE_OK is returned. If there is no next term,
1332 ** SQLITE_DONE. Otherwise, an SQLite error code.
1333 */
1334 static int fts3SegReaderNext(
1335 Fts3Table *p,
1336 Fts3SegReader *pReader,
1337 int bIncr
1338 ){
1339 int rc; /* Return code of various sub-routines */
1340 char *pNext; /* Cursor variable */
1341 int nPrefix; /* Number of bytes in term prefix */
1342 int nSuffix; /* Number of bytes in term suffix */
1343
1344 if( !pReader->aDoclist ){
1345 pNext = pReader->aNode;
1346 }else{
1347 pNext = &pReader->aDoclist[pReader->nDoclist];
1348 }
1349
1350 if( !pNext || pNext>=&pReader->aNode[pReader->nNode] ){
1351
1352 if( fts3SegReaderIsPending(pReader) ){
1353 Fts3HashElem *pElem = *(pReader->ppNextElem);
1354 sqlite3_free(pReader->aNode);
1355 pReader->aNode = 0;
1356 if( pElem ){
1357 char *aCopy;
1358 PendingList *pList = (PendingList *)fts3HashData(pElem);
1359 int nCopy = pList->nData+1;
1360
1361 int nTerm = fts3HashKeysize(pElem);
1362 if( (nTerm+1)>pReader->nTermAlloc ){
1363 sqlite3_free(pReader->zTerm);
1364 pReader->zTerm = (char*)sqlite3_malloc64(((i64)nTerm+1)*2);
1365 if( !pReader->zTerm ) return SQLITE_NOMEM;
1366 pReader->nTermAlloc = (nTerm+1)*2;
1367 }
1368 memcpy(pReader->zTerm, fts3HashKey(pElem), nTerm);
1369 pReader->zTerm[nTerm] = '\0';
1370 pReader->nTerm = nTerm;
1371
1372 aCopy = (char*)sqlite3_malloc64(nCopy);
1373 if( !aCopy ) return SQLITE_NOMEM;
1374 memcpy(aCopy, pList->aData, nCopy);
1375 pReader->nNode = pReader->nDoclist = nCopy;
1376 pReader->aNode = pReader->aDoclist = aCopy;
1377 pReader->ppNextElem++;
1378 assert( pReader->aNode );
1379 }
1380 return SQLITE_OK;
1381 }
1382
1383 fts3SegReaderSetEof(pReader);
1384
1385 /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf
1386 ** blocks have already been traversed. */
1387 #ifdef CORRUPT_DB
1388 assert( pReader->iCurrentBlock<=pReader->iLeafEndBlock || CORRUPT_DB );
1389 #endif
1390 if( pReader->iCurrentBlock>=pReader->iLeafEndBlock ){
1391 return SQLITE_OK;
1392 }
1393
1394 rc = sqlite3Fts3ReadBlock(
1395 p, ++pReader->iCurrentBlock, &pReader->aNode, &pReader->nNode,
1396 (bIncr ? &pReader->nPopulate : 0)
1397 );
1398 if( rc!=SQLITE_OK ) return rc;
1399 assert( pReader->pBlob==0 );
1400 if( bIncr && pReader->nPopulate<pReader->nNode ){
1401 pReader->pBlob = p->pSegments;
1402 p->pSegments = 0;
1403 }
1404 pNext = pReader->aNode;
1405 }
1406
1407 assert( !fts3SegReaderIsPending(pReader) );
1408
1409 rc = fts3SegReaderRequire(pReader, pNext, FTS3_VARINT_MAX*2);
1410 if( rc!=SQLITE_OK ) return rc;
1411
1412 /* Because of the FTS3_NODE_PADDING bytes of padding, the following is
1413 ** safe (no risk of overread) even if the node data is corrupted. */
1414 pNext += fts3GetVarint32(pNext, &nPrefix);
1415 pNext += fts3GetVarint32(pNext, &nSuffix);
1416 if( nSuffix<=0
1417 || (&pReader->aNode[pReader->nNode] - pNext)<nSuffix
1418 || nPrefix>pReader->nTerm
1419 ){
1420 return FTS_CORRUPT_VTAB;
1421 }
1422
1423 /* Both nPrefix and nSuffix were read by fts3GetVarint32() and so are
1424 ** between 0 and 0x7FFFFFFF. But the sum of the two may cause integer
1425 ** overflow - hence the (i64) casts. */
1426 if( (i64)nPrefix+nSuffix>(i64)pReader->nTermAlloc ){
1427 i64 nNew = ((i64)nPrefix+nSuffix)*2;
1428 char *zNew = sqlite3_realloc64(pReader->zTerm, nNew);
1429 if( !zNew ){
1430 return SQLITE_NOMEM;
1431 }
1432 pReader->zTerm = zNew;
1433 pReader->nTermAlloc = nNew;
1434 }
1435
1436 rc = fts3SegReaderRequire(pReader, pNext, nSuffix+FTS3_VARINT_MAX);
1437 if( rc!=SQLITE_OK ) return rc;
1438
1439 memcpy(&pReader->zTerm[nPrefix], pNext, nSuffix);
1440 pReader->nTerm = nPrefix+nSuffix;
1441 pNext += nSuffix;
1442 pNext += fts3GetVarint32(pNext, &pReader->nDoclist);
1443 pReader->aDoclist = pNext;
1444 pReader->pOffsetList = 0;
1445
1446 /* Check that the doclist does not appear to extend past the end of the
1447 ** b-tree node. And that the final byte of the doclist is 0x00. If either
1448 ** of these statements is untrue, then the data structure is corrupt.
1449 */
1450 if( pReader->nDoclist > pReader->nNode-(pReader->aDoclist-pReader->aNode)
1451 || (pReader->nPopulate==0 && pReader->aDoclist[pReader->nDoclist-1])
1452 || pReader->nDoclist==0
1453 ){
1454 return FTS_CORRUPT_VTAB;
1455 }
1456 return SQLITE_OK;
1457 }
1458
1459 /*
1460 ** Set the SegReader to point to the first docid in the doclist associated
1461 ** with the current term.
1462 */
1463 static int fts3SegReaderFirstDocid(Fts3Table *pTab, Fts3SegReader *pReader){
1464 int rc = SQLITE_OK;
1465 assert( pReader->aDoclist );
1466 assert( !pReader->pOffsetList );
1467 if( pTab->bDescIdx && fts3SegReaderIsPending(pReader) ){
1468 u8 bEof = 0;
1469 pReader->iDocid = 0;
1470 pReader->nOffsetList = 0;
1471 sqlite3Fts3DoclistPrev(0,
1472 pReader->aDoclist, pReader->nDoclist, &pReader->pOffsetList,
1473 &pReader->iDocid, &pReader->nOffsetList, &bEof
1474 );
1475 }else{
1476 rc = fts3SegReaderRequire(pReader, pReader->aDoclist, FTS3_VARINT_MAX);
1477 if( rc==SQLITE_OK ){
1478 int n = sqlite3Fts3GetVarint(pReader->aDoclist, &pReader->iDocid);
1479 pReader->pOffsetList = &pReader->aDoclist[n];
1480 }
1481 }
1482 return rc;
1483 }
1484
1485 /*
1486 ** Advance the SegReader to point to the next docid in the doclist
1487 ** associated with the current term.
1488 **
1489 ** If arguments ppOffsetList and pnOffsetList are not NULL, then
1490 ** *ppOffsetList is set to point to the first column-offset list
1491 ** in the doclist entry (i.e. immediately past the docid varint).
1492 ** *pnOffsetList is set to the length of the set of column-offset
1493 ** lists, not including the nul-terminator byte. For example:
1494 */
1495 static int fts3SegReaderNextDocid(
1496 Fts3Table *pTab,
1497 Fts3SegReader *pReader, /* Reader to advance to next docid */
1498 char **ppOffsetList, /* OUT: Pointer to current position-list */
1499 int *pnOffsetList /* OUT: Length of *ppOffsetList in bytes */
1500 ){
1501 int rc = SQLITE_OK;
1502 char *p = pReader->pOffsetList;
1503 char c = 0;
1504
1505 assert( p );
1506
1507 if( pTab->bDescIdx && fts3SegReaderIsPending(pReader) ){
1508 /* A pending-terms seg-reader for an FTS4 table that uses order=desc.
1509 ** Pending-terms doclists are always built up in ascending order, so
1510 ** we have to iterate through them backwards here. */
1511 u8 bEof = 0;
1512 if( ppOffsetList ){
1513 *ppOffsetList = pReader->pOffsetList;
1514 *pnOffsetList = pReader->nOffsetList - 1;
1515 }
1516 sqlite3Fts3DoclistPrev(0,
1517 pReader->aDoclist, pReader->nDoclist, &p, &pReader->iDocid,
1518 &pReader->nOffsetList, &bEof
1519 );
1520 if( bEof ){
1521 pReader->pOffsetList = 0;
1522 }else{
1523 pReader->pOffsetList = p;
1524 }
1525 }else{
1526 char *pEnd = &pReader->aDoclist[pReader->nDoclist];
1527
1528 /* Pointer p currently points at the first byte of an offset list. The
1529 ** following block advances it to point one byte past the end of
1530 ** the same offset list. */
1531 while( 1 ){
1532
1533 /* The following line of code (and the "p++" below the while() loop) is
1534 ** normally all that is required to move pointer p to the desired
1535 ** position. The exception is if this node is being loaded from disk
1536 ** incrementally and pointer "p" now points to the first byte past
1537 ** the populated part of pReader->aNode[].
1538 */
1539 while( *p | c ) c = *p++ & 0x80;
1540 assert( *p==0 );
1541
1542 if( pReader->pBlob==0 || p<&pReader->aNode[pReader->nPopulate] ) break;
1543 rc = fts3SegReaderIncrRead(pReader);
1544 if( rc!=SQLITE_OK ) return rc;
1545 }
1546 p++;
1547
1548 /* If required, populate the output variables with a pointer to and the
1549 ** size of the previous offset-list.
1550 */
1551 if( ppOffsetList ){
1552 *ppOffsetList = pReader->pOffsetList;
1553 *pnOffsetList = (int)(p - pReader->pOffsetList - 1);
1554 }
1555
1556 /* List may have been edited in place by fts3EvalNearTrim() */
1557 while( p<pEnd && *p==0 ) p++;
1558
1559 /* If there are no more entries in the doclist, set pOffsetList to
1560 ** NULL. Otherwise, set Fts3SegReader.iDocid to the next docid and
1561 ** Fts3SegReader.pOffsetList to point to the next offset list before
1562 ** returning.
1563 */
1564 if( p>=pEnd ){
1565 pReader->pOffsetList = 0;
1566 }else{
1567 rc = fts3SegReaderRequire(pReader, p, FTS3_VARINT_MAX);
1568 if( rc==SQLITE_OK ){
1569 u64 iDelta;
1570 pReader->pOffsetList = p + sqlite3Fts3GetVarintU(p, &iDelta);
1571 if( pTab->bDescIdx ){
1572 pReader->iDocid = (i64)((u64)pReader->iDocid - iDelta);
1573 }else{
1574 pReader->iDocid = (i64)((u64)pReader->iDocid + iDelta);
1575 }
1576 }
1577 }
1578 }
1579
1580 return rc;
1581 }
1582
1583
1584 int sqlite3Fts3MsrOvfl(
1585 Fts3Cursor *pCsr,
1586 Fts3MultiSegReader *pMsr,
1587 int *pnOvfl
1588 ){
1589 Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
1590 int nOvfl = 0;
1591 int ii;
1592 int rc = SQLITE_OK;
1593 int pgsz = p->nPgsz;
1594
1595 assert( p->bFts4 );
1596 assert( pgsz>0 );
1597
1598 for(ii=0; rc==SQLITE_OK && ii<pMsr->nSegment; ii++){
1599 Fts3SegReader *pReader = pMsr->apSegment[ii];
1600 if( !fts3SegReaderIsPending(pReader)
1601 && !fts3SegReaderIsRootOnly(pReader)
1602 ){
1603 sqlite3_int64 jj;
1604 for(jj=pReader->iStartBlock; jj<=pReader->iLeafEndBlock; jj++){
1605 int nBlob;
1606 rc = sqlite3Fts3ReadBlock(p, jj, 0, &nBlob, 0);
1607 if( rc!=SQLITE_OK ) break;
1608 if( (nBlob+35)>pgsz ){
1609 nOvfl += (nBlob + 34)/pgsz;
1610 }
1611 }
1612 }
1613 }
1614 *pnOvfl = nOvfl;
1615 return rc;
1616 }
1617
1618 /*
1619 ** Free all allocations associated with the iterator passed as the
1620 ** second argument.
1621 */
1622 void sqlite3Fts3SegReaderFree(Fts3SegReader *pReader){
1623 if( pReader ){
1624 sqlite3_free(pReader->zTerm);
1625 if( !fts3SegReaderIsRootOnly(pReader) ){
1626 sqlite3_free(pReader->aNode);
1627 }
1628 sqlite3_blob_close(pReader->pBlob);
1629 }
1630 sqlite3_free(pReader);
1631 }
1632
1633 /*
1634 ** Allocate a new SegReader object.
1635 */
1636 int sqlite3Fts3SegReaderNew(
1637 int iAge, /* Segment "age". */
1638 int bLookup, /* True for a lookup only */
1639 sqlite3_int64 iStartLeaf, /* First leaf to traverse */
1640 sqlite3_int64 iEndLeaf, /* Final leaf to traverse */
1641 sqlite3_int64 iEndBlock, /* Final block of segment */
1642 const char *zRoot, /* Buffer containing root node */
1643 int nRoot, /* Size of buffer containing root node */
1644 Fts3SegReader **ppReader /* OUT: Allocated Fts3SegReader */
1645 ){
1646 Fts3SegReader *pReader; /* Newly allocated SegReader object */
1647 int nExtra = 0; /* Bytes to allocate segment root node */
1648
1649 assert( zRoot!=0 || nRoot==0 );
1650 #ifdef CORRUPT_DB
1651 assert( zRoot!=0 || CORRUPT_DB );
1652 #endif
1653
1654 if( iStartLeaf==0 ){
1655 if( iEndLeaf!=0 ) return FTS_CORRUPT_VTAB;
1656 nExtra = nRoot + FTS3_NODE_PADDING;
1657 }
1658
1659 pReader = (Fts3SegReader *)sqlite3_malloc64(sizeof(Fts3SegReader) + nExtra);
1660 if( !pReader ){
1661 return SQLITE_NOMEM;
1662 }
1663 memset(pReader, 0, sizeof(Fts3SegReader));
1664 pReader->iIdx = iAge;
1665 pReader->bLookup = bLookup!=0;
1666 pReader->iStartBlock = iStartLeaf;
1667 pReader->iLeafEndBlock = iEndLeaf;
1668 pReader->iEndBlock = iEndBlock;
1669
1670 if( nExtra ){
1671 /* The entire segment is stored in the root node. */
1672 pReader->aNode = (char *)&pReader[1];
1673 pReader->rootOnly = 1;
1674 pReader->nNode = nRoot;
1675 if( nRoot ) memcpy(pReader->aNode, zRoot, nRoot);
1676 memset(&pReader->aNode[nRoot], 0, FTS3_NODE_PADDING);
1677 }else{
1678 pReader->iCurrentBlock = iStartLeaf-1;
1679 }
1680 *ppReader = pReader;
1681 return SQLITE_OK;
1682 }
1683
1684 /*
1685 ** This is a comparison function used as a qsort() callback when sorting
1686 ** an array of pending terms by term. This occurs as part of flushing
1687 ** the contents of the pending-terms hash table to the database.
1688 */
1689 static int SQLITE_CDECL fts3CompareElemByTerm(
1690 const void *lhs,
1691 const void *rhs
1692 ){
1693 char *z1 = fts3HashKey(*(Fts3HashElem **)lhs);
1694 char *z2 = fts3HashKey(*(Fts3HashElem **)rhs);
1695 int n1 = fts3HashKeysize(*(Fts3HashElem **)lhs);
1696 int n2 = fts3HashKeysize(*(Fts3HashElem **)rhs);
1697
1698 int n = (n1<n2 ? n1 : n2);
1699 int c = memcmp(z1, z2, n);
1700 if( c==0 ){
1701 c = n1 - n2;
1702 }
1703 return c;
1704 }
1705
1706 /*
1707 ** This function is used to allocate an Fts3SegReader that iterates through
1708 ** a subset of the terms stored in the Fts3Table.pendingTerms array.
1709 **
1710 ** If the isPrefixIter parameter is zero, then the returned SegReader iterates
1711 ** through each term in the pending-terms table. Or, if isPrefixIter is
1712 ** non-zero, it iterates through each term and its prefixes. For example, if
1713 ** the pending terms hash table contains the terms "sqlite", "mysql" and
1714 ** "firebird", then the iterator visits the following 'terms' (in the order
1715 ** shown):
1716 **
1717 ** f fi fir fire fireb firebi firebir firebird
1718 ** m my mys mysq mysql
1719 ** s sq sql sqli sqlit sqlite
1720 **
1721 ** Whereas if isPrefixIter is zero, the terms visited are:
1722 **
1723 ** firebird mysql sqlite
1724 */
1725 int sqlite3Fts3SegReaderPending(
1726 Fts3Table *p, /* Virtual table handle */
1727 int iIndex, /* Index for p->aIndex */
1728 const char *zTerm, /* Term to search for */
1729 int nTerm, /* Size of buffer zTerm */
1730 int bPrefix, /* True for a prefix iterator */
1731 Fts3SegReader **ppReader /* OUT: SegReader for pending-terms */
1732 ){
1733 Fts3SegReader *pReader = 0; /* Fts3SegReader object to return */
1734 Fts3HashElem *pE; /* Iterator variable */
1735 Fts3HashElem **aElem = 0; /* Array of term hash entries to scan */
1736 int nElem = 0; /* Size of array at aElem */
1737 int rc = SQLITE_OK; /* Return Code */
1738 Fts3Hash *pHash;
1739
1740 pHash = &p->aIndex[iIndex].hPending;
1741 if( bPrefix ){
1742 int nAlloc = 0; /* Size of allocated array at aElem */
1743
1744 for(pE=fts3HashFirst(pHash); pE; pE=fts3HashNext(pE)){
1745 char *zKey = (char *)fts3HashKey(pE);
1746 int nKey = fts3HashKeysize(pE);
1747 if( nTerm==0 || (nKey>=nTerm && 0==memcmp(zKey, zTerm, nTerm)) ){
1748 if( nElem==nAlloc ){
1749 Fts3HashElem **aElem2;
1750 nAlloc += 16;
1751 aElem2 = (Fts3HashElem **)sqlite3_realloc64(
1752 aElem, nAlloc*sizeof(Fts3HashElem *)
1753 );
1754 if( !aElem2 ){
1755 rc = SQLITE_NOMEM;
1756 nElem = 0;
1757 break;
1758 }
1759 aElem = aElem2;
1760 }
1761
1762 aElem[nElem++] = pE;
1763 }
1764 }
1765
1766 /* If more than one term matches the prefix, sort the Fts3HashElem
1767 ** objects in term order using qsort(). This uses the same comparison
1768 ** callback as is used when flushing terms to disk.
1769 */
1770 if( nElem>1 ){
1771 qsort(aElem, nElem, sizeof(Fts3HashElem *), fts3CompareElemByTerm);
1772 }
1773
1774 }else{
1775 /* The query is a simple term lookup that matches at most one term in
1776 ** the index. All that is required is a straight hash-lookup.
1777 **
1778 ** Because the stack address of pE may be accessed via the aElem pointer
1779 ** below, the "Fts3HashElem *pE" must be declared so that it is valid
1780 ** within this entire function, not just this "else{...}" block.
1781 */
1782 pE = fts3HashFindElem(pHash, zTerm, nTerm);
1783 if( pE ){
1784 aElem = &pE;
1785 nElem = 1;
1786 }
1787 }
1788
1789 if( nElem>0 ){
1790 sqlite3_int64 nByte;
1791 nByte = sizeof(Fts3SegReader) + (nElem+1)*sizeof(Fts3HashElem *);
1792 pReader = (Fts3SegReader *)sqlite3_malloc64(nByte);
1793 if( !pReader ){
1794 rc = SQLITE_NOMEM;
1795 }else{
1796 memset(pReader, 0, nByte);
1797 pReader->iIdx = 0x7FFFFFFF;
1798 pReader->ppNextElem = (Fts3HashElem **)&pReader[1];
1799 memcpy(pReader->ppNextElem, aElem, nElem*sizeof(Fts3HashElem *));
1800 }
1801 }
1802
1803 if( bPrefix ){
1804 sqlite3_free(aElem);
1805 }
1806 *ppReader = pReader;
1807 return rc;
1808 }
1809
1810 /*
1811 ** Compare the entries pointed to by two Fts3SegReader structures.
1812 ** Comparison is as follows:
1813 **
1814 ** 1) EOF is greater than not EOF.
1815 **
1816 ** 2) The current terms (if any) are compared using memcmp(). If one
1817 ** term is a prefix of another, the longer term is considered the
1818 ** larger.
1819 **
1820 ** 3) By segment age. An older segment is considered larger.
1821 */
1822 static int fts3SegReaderCmp(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
1823 int rc;
1824 if( pLhs->aNode && pRhs->aNode ){
1825 int rc2 = pLhs->nTerm - pRhs->nTerm;
1826 if( rc2<0 ){
1827 rc = memcmp(pLhs->zTerm, pRhs->zTerm, pLhs->nTerm);
1828 }else{
1829 rc = memcmp(pLhs->zTerm, pRhs->zTerm, pRhs->nTerm);
1830 }
1831 if( rc==0 ){
1832 rc = rc2;
1833 }
1834 }else{
1835 rc = (pLhs->aNode==0) - (pRhs->aNode==0);
1836 }
1837 if( rc==0 ){
1838 rc = pRhs->iIdx - pLhs->iIdx;
1839 }
1840 assert_fts3_nc( rc!=0 );
1841 return rc;
1842 }
1843
1844 /*
1845 ** A different comparison function for SegReader structures. In this
1846 ** version, it is assumed that each SegReader points to an entry in
1847 ** a doclist for identical terms. Comparison is made as follows:
1848 **
1849 ** 1) EOF (end of doclist in this case) is greater than not EOF.
1850 **
1851 ** 2) By current docid.
1852 **
1853 ** 3) By segment age. An older segment is considered larger.
1854 */
1855 static int fts3SegReaderDoclistCmp(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
1856 int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);
1857 if( rc==0 ){
1858 if( pLhs->iDocid==pRhs->iDocid ){
1859 rc = pRhs->iIdx - pLhs->iIdx;
1860 }else{
1861 rc = (pLhs->iDocid > pRhs->iDocid) ? 1 : -1;
1862 }
1863 }
1864 assert( pLhs->aNode && pRhs->aNode );
1865 return rc;
1866 }
1867 static int fts3SegReaderDoclistCmpRev(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
1868 int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);
1869 if( rc==0 ){
1870 if( pLhs->iDocid==pRhs->iDocid ){
1871 rc = pRhs->iIdx - pLhs->iIdx;
1872 }else{
1873 rc = (pLhs->iDocid < pRhs->iDocid) ? 1 : -1;
1874 }
1875 }
1876 assert( pLhs->aNode && pRhs->aNode );
1877 return rc;
1878 }
1879
1880 /*
1881 ** Compare the term that the Fts3SegReader object passed as the first argument
1882 ** points to with the term specified by arguments zTerm and nTerm.
1883 **
1884 ** If the pSeg iterator is already at EOF, return 0. Otherwise, return
1885 ** -ve if the pSeg term is less than zTerm/nTerm, 0 if the two terms are
1886 ** equal, or +ve if the pSeg term is greater than zTerm/nTerm.
1887 */
1888 static int fts3SegReaderTermCmp(
1889 Fts3SegReader *pSeg, /* Segment reader object */
1890 const char *zTerm, /* Term to compare to */
1891 int nTerm /* Size of term zTerm in bytes */
1892 ){
1893 int res = 0;
1894 if( pSeg->aNode ){
1895 if( pSeg->nTerm>nTerm ){
1896 res = memcmp(pSeg->zTerm, zTerm, nTerm);
1897 }else{
1898 res = memcmp(pSeg->zTerm, zTerm, pSeg->nTerm);
1899 }
1900 if( res==0 ){
1901 res = pSeg->nTerm-nTerm;
1902 }
1903 }
1904 return res;
1905 }
1906
1907 /*
1908 ** Argument apSegment is an array of nSegment elements. It is known that
1909 ** the final (nSegment-nSuspect) members are already in sorted order
1910 ** (according to the comparison function provided). This function shuffles
1911 ** the array around until all entries are in sorted order.
1912 */
1913 static void fts3SegReaderSort(
1914 Fts3SegReader **apSegment, /* Array to sort entries of */
1915 int nSegment, /* Size of apSegment array */
1916 int nSuspect, /* Unsorted entry count */
1917 int (*xCmp)(Fts3SegReader *, Fts3SegReader *) /* Comparison function */
1918 ){
1919 int i; /* Iterator variable */
1920
1921 assert( nSuspect<=nSegment );
1922
1923 if( nSuspect==nSegment ) nSuspect--;
1924 for(i=nSuspect-1; i>=0; i--){
1925 int j;
1926 for(j=i; j<(nSegment-1); j++){
1927 Fts3SegReader *pTmp;
1928 if( xCmp(apSegment[j], apSegment[j+1])<0 ) break;
1929 pTmp = apSegment[j+1];
1930 apSegment[j+1] = apSegment[j];
1931 apSegment[j] = pTmp;
1932 }
1933 }
1934
1935 #ifndef NDEBUG
1936 /* Check that the list really is sorted now. */
1937 for(i=0; i<(nSuspect-1); i++){
1938 assert( xCmp(apSegment[i], apSegment[i+1])<0 );
1939 }
1940 #endif
1941 }
1942
1943 /*
1944 ** Insert a record into the %_segments table.
1945 */
1946 static int fts3WriteSegment(
1947 Fts3Table *p, /* Virtual table handle */
1948 sqlite3_int64 iBlock, /* Block id for new block */
1949 char *z, /* Pointer to buffer containing block data */
1950 int n /* Size of buffer z in bytes */
1951 ){
1952 sqlite3_stmt *pStmt;
1953 int rc = fts3SqlStmt(p, SQL_INSERT_SEGMENTS, &pStmt, 0);
1954 if( rc==SQLITE_OK ){
1955 sqlite3_bind_int64(pStmt, 1, iBlock);
1956 sqlite3_bind_blob(pStmt, 2, z, n, SQLITE_STATIC);
1957 sqlite3_step(pStmt);
1958 rc = sqlite3_reset(pStmt);
1959 sqlite3_bind_null(pStmt, 2);
1960 }
1961 return rc;
1962 }
1963
1964 /*
1965 ** Find the largest relative level number in the table. If successful, set
1966 ** *pnMax to this value and return SQLITE_OK. Otherwise, if an error occurs,
1967 ** set *pnMax to zero and return an SQLite error code.
1968 */
1969 int sqlite3Fts3MaxLevel(Fts3Table *p, int *pnMax){
1970 int rc;
1971 int mxLevel = 0;
1972 sqlite3_stmt *pStmt = 0;
1973
1974 rc = fts3SqlStmt(p, SQL_SELECT_MXLEVEL, &pStmt, 0);
1975 if( rc==SQLITE_OK ){
1976 if( SQLITE_ROW==sqlite3_step(pStmt) ){
1977 mxLevel = sqlite3_column_int(pStmt, 0);
1978 }
1979 rc = sqlite3_reset(pStmt);
1980 }
1981 *pnMax = mxLevel;
1982 return rc;
1983 }
1984
1985 /*
1986 ** Insert a record into the %_segdir table.
1987 */
1988 static int fts3WriteSegdir(
1989 Fts3Table *p, /* Virtual table handle */
1990 sqlite3_int64 iLevel, /* Value for "level" field (absolute level) */
1991 int iIdx, /* Value for "idx" field */
1992 sqlite3_int64 iStartBlock, /* Value for "start_block" field */
1993 sqlite3_int64 iLeafEndBlock, /* Value for "leaves_end_block" field */
1994 sqlite3_int64 iEndBlock, /* Value for "end_block" field */
1995 sqlite3_int64 nLeafData, /* Bytes of leaf data in segment */
1996 char *zRoot, /* Blob value for "root" field */
1997 int nRoot /* Number of bytes in buffer zRoot */
1998 ){
1999 sqlite3_stmt *pStmt;
2000 int rc = fts3SqlStmt(p, SQL_INSERT_SEGDIR, &pStmt, 0);
2001 if( rc==SQLITE_OK ){
2002 sqlite3_bind_int64(pStmt, 1, iLevel);
2003 sqlite3_bind_int(pStmt, 2, iIdx);
2004 sqlite3_bind_int64(pStmt, 3, iStartBlock);
2005 sqlite3_bind_int64(pStmt, 4, iLeafEndBlock);
2006 if( nLeafData==0 ){
2007 sqlite3_bind_int64(pStmt, 5, iEndBlock);
2008 }else{
2009 char *zEnd = sqlite3_mprintf("%lld %lld", iEndBlock, nLeafData);
2010 if( !zEnd ) return SQLITE_NOMEM;
2011 sqlite3_bind_text(pStmt, 5, zEnd, -1, sqlite3_free);
2012 }
2013 sqlite3_bind_blob(pStmt, 6, zRoot, nRoot, SQLITE_STATIC);
2014 sqlite3_step(pStmt);
2015 rc = sqlite3_reset(pStmt);
2016 sqlite3_bind_null(pStmt, 6);
2017 }
2018 return rc;
2019 }
2020
2021 /*
2022 ** Return the size of the common prefix (if any) shared by zPrev and
2023 ** zNext, in bytes. For example,
2024 **
2025 ** fts3PrefixCompress("abc", 3, "abcdef", 6) // returns 3
2026 ** fts3PrefixCompress("abX", 3, "abcdef", 6) // returns 2
2027 ** fts3PrefixCompress("abX", 3, "Xbcdef", 6) // returns 0
2028 */
2029 static int fts3PrefixCompress(
2030 const char *zPrev, /* Buffer containing previous term */
2031 int nPrev, /* Size of buffer zPrev in bytes */
2032 const char *zNext, /* Buffer containing next term */
2033 int nNext /* Size of buffer zNext in bytes */
2034 ){
2035 int n;
2036 for(n=0; n<nPrev && n<nNext && zPrev[n]==zNext[n]; n++);
2037 assert_fts3_nc( n<nNext );
2038 return n;
2039 }
2040
2041 /*
2042 ** Add term zTerm to the SegmentNode. It is guaranteed that zTerm is larger
2043 ** (according to memcmp) than the previous term.
2044 */
2045 static int fts3NodeAddTerm(
2046 Fts3Table *p, /* Virtual table handle */
2047 SegmentNode **ppTree, /* IN/OUT: SegmentNode handle */
2048 int isCopyTerm, /* True if zTerm/nTerm is transient */
2049 const char *zTerm, /* Pointer to buffer containing term */
2050 int nTerm /* Size of term in bytes */
2051 ){
2052 SegmentNode *pTree = *ppTree;
2053 int rc;
2054 SegmentNode *pNew;
2055
2056 /* First try to append the term to the current node. Return early if
2057 ** this is possible.
2058 */
2059 if( pTree ){
2060 int nData = pTree->nData; /* Current size of node in bytes */
2061 int nReq = nData; /* Required space after adding zTerm */
2062 int nPrefix; /* Number of bytes of prefix compression */
2063 int nSuffix; /* Suffix length */
2064
2065 nPrefix = fts3PrefixCompress(pTree->zTerm, pTree->nTerm, zTerm, nTerm);
2066 nSuffix = nTerm-nPrefix;
2067
2068 /* If nSuffix is zero or less, then zTerm/nTerm must be a prefix of
2069 ** pWriter->zTerm/pWriter->nTerm. i.e. must be equal to or less than when
2070 ** compared with BINARY collation. This indicates corruption. */
2071 if( nSuffix<=0 ) return FTS_CORRUPT_VTAB;
2072
2073 nReq += sqlite3Fts3VarintLen(nPrefix)+sqlite3Fts3VarintLen(nSuffix)+nSuffix;
2074 if( nReq<=p->nNodeSize || !pTree->zTerm ){
2075
2076 if( nReq>p->nNodeSize ){
2077 /* An unusual case: this is the first term to be added to the node
2078 ** and the static node buffer (p->nNodeSize bytes) is not large
2079 ** enough. Use a separately malloced buffer instead This wastes
2080 ** p->nNodeSize bytes, but since this scenario only comes about when
2081 ** the database contain two terms that share a prefix of almost 2KB,
2082 ** this is not expected to be a serious problem.
2083 */
2084 assert( pTree->aData==(char *)&pTree[1] );
2085 pTree->aData = (char *)sqlite3_malloc64(nReq);
2086 if( !pTree->aData ){
2087 return SQLITE_NOMEM;
2088 }
2089 }
2090
2091 if( pTree->zTerm ){
2092 /* There is no prefix-length field for first term in a node */
2093 nData += sqlite3Fts3PutVarint(&pTree->aData[nData], nPrefix);
2094 }
2095
2096 nData += sqlite3Fts3PutVarint(&pTree->aData[nData], nSuffix);
2097 memcpy(&pTree->aData[nData], &zTerm[nPrefix], nSuffix);
2098 pTree->nData = nData + nSuffix;
2099 pTree->nEntry++;
2100
2101 if( isCopyTerm ){
2102 if( pTree->nMalloc<nTerm ){
2103 char *zNew = sqlite3_realloc64(pTree->zMalloc, (i64)nTerm*2);
2104 if( !zNew ){
2105 return SQLITE_NOMEM;
2106 }
2107 pTree->nMalloc = nTerm*2;
2108 pTree->zMalloc = zNew;
2109 }
2110 pTree->zTerm = pTree->zMalloc;
2111 memcpy(pTree->zTerm, zTerm, nTerm);
2112 pTree->nTerm = nTerm;
2113 }else{
2114 pTree->zTerm = (char *)zTerm;
2115 pTree->nTerm = nTerm;
2116 }
2117 return SQLITE_OK;
2118 }
2119 }
2120
2121 /* If control flows to here, it was not possible to append zTerm to the
2122 ** current node. Create a new node (a right-sibling of the current node).
2123 ** If this is the first node in the tree, the term is added to it.
2124 **
2125 ** Otherwise, the term is not added to the new node, it is left empty for
2126 ** now. Instead, the term is inserted into the parent of pTree. If pTree
2127 ** has no parent, one is created here.
2128 */
2129 pNew = (SegmentNode *)sqlite3_malloc64(sizeof(SegmentNode) + p->nNodeSize);
2130 if( !pNew ){
2131 return SQLITE_NOMEM;
2132 }
2133 memset(pNew, 0, sizeof(SegmentNode));
2134 pNew->nData = 1 + FTS3_VARINT_MAX;
2135 pNew->aData = (char *)&pNew[1];
2136
2137 if( pTree ){
2138 SegmentNode *pParent = pTree->pParent;
2139 rc = fts3NodeAddTerm(p, &pParent, isCopyTerm, zTerm, nTerm);
2140 if( pTree->pParent==0 ){
2141 pTree->pParent = pParent;
2142 }
2143 pTree->pRight = pNew;
2144 pNew->pLeftmost = pTree->pLeftmost;
2145 pNew->pParent = pParent;
2146 pNew->zMalloc = pTree->zMalloc;
2147 pNew->nMalloc = pTree->nMalloc;
2148 pTree->zMalloc = 0;
2149 }else{
2150 pNew->pLeftmost = pNew;
2151 rc = fts3NodeAddTerm(p, &pNew, isCopyTerm, zTerm, nTerm);
2152 }
2153
2154 *ppTree = pNew;
2155 return rc;
2156 }
2157
2158 /*
2159 ** Helper function for fts3NodeWrite().
2160 */
2161 static int fts3TreeFinishNode(
2162 SegmentNode *pTree,
2163 int iHeight,
2164 sqlite3_int64 iLeftChild
2165 ){
2166 int nStart;
2167 assert( iHeight>=1 && iHeight<128 );
2168 nStart = FTS3_VARINT_MAX - sqlite3Fts3VarintLen(iLeftChild);
2169 pTree->aData[nStart] = (char)iHeight;
2170 sqlite3Fts3PutVarint(&pTree->aData[nStart+1], iLeftChild);
2171 return nStart;
2172 }
2173
2174 /*
2175 ** Write the buffer for the segment node pTree and all of its peers to the
2176 ** database. Then call this function recursively to write the parent of
2177 ** pTree and its peers to the database.
2178 **
2179 ** Except, if pTree is a root node, do not write it to the database. Instead,
2180 ** set output variables *paRoot and *pnRoot to contain the root node.
2181 **
2182 ** If successful, SQLITE_OK is returned and output variable *piLast is
2183 ** set to the largest blockid written to the database (or zero if no
2184 ** blocks were written to the db). Otherwise, an SQLite error code is
2185 ** returned.
2186 */
2187 static int fts3NodeWrite(
2188 Fts3Table *p, /* Virtual table handle */
2189 SegmentNode *pTree, /* SegmentNode handle */
2190 int iHeight, /* Height of this node in tree */
2191 sqlite3_int64 iLeaf, /* Block id of first leaf node */
2192 sqlite3_int64 iFree, /* Block id of next free slot in %_segments */
2193 sqlite3_int64 *piLast, /* OUT: Block id of last entry written */
2194 char **paRoot, /* OUT: Data for root node */
2195 int *pnRoot /* OUT: Size of root node in bytes */
2196 ){
2197 int rc = SQLITE_OK;
2198
2199 if( !pTree->pParent ){
2200 /* Root node of the tree. */
2201 int nStart = fts3TreeFinishNode(pTree, iHeight, iLeaf);
2202 *piLast = iFree-1;
2203 *pnRoot = pTree->nData - nStart;
2204 *paRoot = &pTree->aData[nStart];
2205 }else{
2206 SegmentNode *pIter;
2207 sqlite3_int64 iNextFree = iFree;
2208 sqlite3_int64 iNextLeaf = iLeaf;
2209 for(pIter=pTree->pLeftmost; pIter && rc==SQLITE_OK; pIter=pIter->pRight){
2210 int nStart = fts3TreeFinishNode(pIter, iHeight, iNextLeaf);
2211 int nWrite = pIter->nData - nStart;
2212
2213 rc = fts3WriteSegment(p, iNextFree, &pIter->aData[nStart], nWrite);
2214 iNextFree++;
2215 iNextLeaf += (pIter->nEntry+1);
2216 }
2217 if( rc==SQLITE_OK ){
2218 assert( iNextLeaf==iFree );
2219 rc = fts3NodeWrite(
2220 p, pTree->pParent, iHeight+1, iFree, iNextFree, piLast, paRoot, pnRoot
2221 );
2222 }
2223 }
2224
2225 return rc;
2226 }
2227
2228 /*
2229 ** Free all memory allocations associated with the tree pTree.
2230 */
2231 static void fts3NodeFree(SegmentNode *pTree){
2232 if( pTree ){
2233 SegmentNode *p = pTree->pLeftmost;
2234 fts3NodeFree(p->pParent);
2235 while( p ){
2236 SegmentNode *pRight = p->pRight;
2237 if( p->aData!=(char *)&p[1] ){
2238 sqlite3_free(p->aData);
2239 }
2240 assert( pRight==0 || p->zMalloc==0 );
2241 sqlite3_free(p->zMalloc);
2242 sqlite3_free(p);
2243 p = pRight;
2244 }
2245 }
2246 }
2247
2248 /*
2249 ** Add a term to the segment being constructed by the SegmentWriter object
2250 ** *ppWriter. When adding the first term to a segment, *ppWriter should
2251 ** be passed NULL. This function will allocate a new SegmentWriter object
2252 ** and return it via the input/output variable *ppWriter in this case.
2253 **
2254 ** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.
2255 */
2256 static int fts3SegWriterAdd(
2257 Fts3Table *p, /* Virtual table handle */
2258 SegmentWriter **ppWriter, /* IN/OUT: SegmentWriter handle */
2259 int isCopyTerm, /* True if buffer zTerm must be copied */
2260 const char *zTerm, /* Pointer to buffer containing term */
2261 int nTerm, /* Size of term in bytes */
2262 const char *aDoclist, /* Pointer to buffer containing doclist */
2263 int nDoclist /* Size of doclist in bytes */
2264 ){
2265 int nPrefix; /* Size of term prefix in bytes */
2266 int nSuffix; /* Size of term suffix in bytes */
2267 i64 nReq; /* Number of bytes required on leaf page */
2268 int nData;
2269 SegmentWriter *pWriter = *ppWriter;
2270
2271 if( !pWriter ){
2272 int rc;
2273 sqlite3_stmt *pStmt;
2274
2275 /* Allocate the SegmentWriter structure */
2276 pWriter = (SegmentWriter *)sqlite3_malloc64(sizeof(SegmentWriter));
2277 if( !pWriter ) return SQLITE_NOMEM;
2278 memset(pWriter, 0, sizeof(SegmentWriter));
2279 *ppWriter = pWriter;
2280
2281 /* Allocate a buffer in which to accumulate data */
2282 pWriter->aData = (char *)sqlite3_malloc64(p->nNodeSize);
2283 if( !pWriter->aData ) return SQLITE_NOMEM;
2284 pWriter->nSize = p->nNodeSize;
2285
2286 /* Find the next free blockid in the %_segments table */
2287 rc = fts3SqlStmt(p, SQL_NEXT_SEGMENTS_ID, &pStmt, 0);
2288 if( rc!=SQLITE_OK ) return rc;
2289 if( SQLITE_ROW==sqlite3_step(pStmt) ){
2290 pWriter->iFree = sqlite3_column_int64(pStmt, 0);
2291 pWriter->iFirst = pWriter->iFree;
2292 }
2293 rc = sqlite3_reset(pStmt);
2294 if( rc!=SQLITE_OK ) return rc;
2295 }
2296 nData = pWriter->nData;
2297
2298 nPrefix = fts3PrefixCompress(pWriter->zTerm, pWriter->nTerm, zTerm, nTerm);
2299 nSuffix = nTerm-nPrefix;
2300
2301 /* If nSuffix is zero or less, then zTerm/nTerm must be a prefix of
2302 ** pWriter->zTerm/pWriter->nTerm. i.e. must be equal to or less than when
2303 ** compared with BINARY collation. This indicates corruption. */
2304 if( nSuffix<=0 ) return FTS_CORRUPT_VTAB;
2305
2306 /* Figure out how many bytes are required by this new entry */
2307 nReq = sqlite3Fts3VarintLen(nPrefix) + /* varint containing prefix size */
2308 sqlite3Fts3VarintLen(nSuffix) + /* varint containing suffix size */
2309 nSuffix + /* Term suffix */
2310 sqlite3Fts3VarintLen(nDoclist) + /* Size of doclist */
2311 nDoclist; /* Doclist data */
2312
2313 if( nData>0 && nData+nReq>p->nNodeSize ){
2314 int rc;
2315
2316 /* The current leaf node is full. Write it out to the database. */
2317 if( pWriter->iFree==LARGEST_INT64 ) return FTS_CORRUPT_VTAB;
2318 rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, nData);
2319 if( rc!=SQLITE_OK ) return rc;
2320 p->nLeafAdd++;
2321
2322 /* Add the current term to the interior node tree. The term added to
2323 ** the interior tree must:
2324 **
2325 ** a) be greater than the largest term on the leaf node just written
2326 ** to the database (still available in pWriter->zTerm), and
2327 **
2328 ** b) be less than or equal to the term about to be added to the new
2329 ** leaf node (zTerm/nTerm).
2330 **
2331 ** In other words, it must be the prefix of zTerm 1 byte longer than
2332 ** the common prefix (if any) of zTerm and pWriter->zTerm.
2333 */
2334 assert( nPrefix<nTerm );
2335 rc = fts3NodeAddTerm(p, &pWriter->pTree, isCopyTerm, zTerm, nPrefix+1);
2336 if( rc!=SQLITE_OK ) return rc;
2337
2338 nData = 0;
2339 pWriter->nTerm = 0;
2340
2341 nPrefix = 0;
2342 nSuffix = nTerm;
2343 nReq = 1 + /* varint containing prefix size */
2344 sqlite3Fts3VarintLen(nTerm) + /* varint containing suffix size */
2345 nTerm + /* Term suffix */
2346 sqlite3Fts3VarintLen(nDoclist) + /* Size of doclist */
2347 nDoclist; /* Doclist data */
2348 }
2349
2350 /* Increase the total number of bytes written to account for the new entry. */
2351 pWriter->nLeafData += nReq;
2352
2353 /* If the buffer currently allocated is too small for this entry, realloc
2354 ** the buffer to make it large enough.
2355 */
2356 if( nReq>pWriter->nSize ){
2357 char *aNew = sqlite3_realloc64(pWriter->aData, nReq);
2358 if( !aNew ) return SQLITE_NOMEM;
2359 pWriter->aData = aNew;
2360 pWriter->nSize = nReq;
2361 }
2362 assert( nData+nReq<=pWriter->nSize );
2363
2364 /* Append the prefix-compressed term and doclist to the buffer. */
2365 nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nPrefix);
2366 nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nSuffix);
2367 assert( nSuffix>0 );
2368 memcpy(&pWriter->aData[nData], &zTerm[nPrefix], nSuffix);
2369 nData += nSuffix;
2370 nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nDoclist);
2371 assert( nDoclist>0 );
2372 memcpy(&pWriter->aData[nData], aDoclist, nDoclist);
2373 pWriter->nData = nData + nDoclist;
2374
2375 /* Save the current term so that it can be used to prefix-compress the next.
2376 ** If the isCopyTerm parameter is true, then the buffer pointed to by
2377 ** zTerm is transient, so take a copy of the term data. Otherwise, just
2378 ** store a copy of the pointer.
2379 */
2380 if( isCopyTerm ){
2381 if( nTerm>pWriter->nMalloc ){
2382 char *zNew = sqlite3_realloc64(pWriter->zMalloc, (i64)nTerm*2);
2383 if( !zNew ){
2384 return SQLITE_NOMEM;
2385 }
2386 pWriter->nMalloc = nTerm*2;
2387 pWriter->zMalloc = zNew;
2388 pWriter->zTerm = zNew;
2389 }
2390 assert( pWriter->zTerm==pWriter->zMalloc );
2391 assert( nTerm>0 );
2392 memcpy(pWriter->zTerm, zTerm, nTerm);
2393 }else{
2394 pWriter->zTerm = (char *)zTerm;
2395 }
2396 pWriter->nTerm = nTerm;
2397
2398 return SQLITE_OK;
2399 }
2400
2401 /*
2402 ** Flush all data associated with the SegmentWriter object pWriter to the
2403 ** database. This function must be called after all terms have been added
2404 ** to the segment using fts3SegWriterAdd(). If successful, SQLITE_OK is
2405 ** returned. Otherwise, an SQLite error code.
2406 */
2407 static int fts3SegWriterFlush(
2408 Fts3Table *p, /* Virtual table handle */
2409 SegmentWriter *pWriter, /* SegmentWriter to flush to the db */
2410 sqlite3_int64 iLevel, /* Value for 'level' column of %_segdir */
2411 int iIdx /* Value for 'idx' column of %_segdir */
2412 ){
2413 int rc; /* Return code */
2414 if( pWriter->pTree ){
2415 sqlite3_int64 iLast = 0; /* Largest block id written to database */
2416 sqlite3_int64 iLastLeaf; /* Largest leaf block id written to db */
2417 char *zRoot = NULL; /* Pointer to buffer containing root node */
2418 int nRoot = 0; /* Size of buffer zRoot */
2419
2420 iLastLeaf = pWriter->iFree;
2421 rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, pWriter->nData);
2422 if( rc==SQLITE_OK ){
2423 rc = fts3NodeWrite(p, pWriter->pTree, 1,
2424 pWriter->iFirst, pWriter->iFree, &iLast, &zRoot, &nRoot);
2425 }
2426 if( rc==SQLITE_OK ){
2427 rc = fts3WriteSegdir(p, iLevel, iIdx,
2428 pWriter->iFirst, iLastLeaf, iLast, pWriter->nLeafData, zRoot, nRoot);
2429 }
2430 }else{
2431 /* The entire tree fits on the root node. Write it to the segdir table. */
2432 rc = fts3WriteSegdir(p, iLevel, iIdx,
2433 0, 0, 0, pWriter->nLeafData, pWriter->aData, pWriter->nData);
2434 }
2435 p->nLeafAdd++;
2436 return rc;
2437 }
2438
2439 /*
2440 ** Release all memory held by the SegmentWriter object passed as the
2441 ** first argument.
2442 */
2443 static void fts3SegWriterFree(SegmentWriter *pWriter){
2444 if( pWriter ){
2445 sqlite3_free(pWriter->aData);
2446 sqlite3_free(pWriter->zMalloc);
2447 fts3NodeFree(pWriter->pTree);
2448 sqlite3_free(pWriter);
2449 }
2450 }
2451
2452 /*
2453 ** The first value in the apVal[] array is assumed to contain an integer.
2454 ** This function tests if there exist any documents with docid values that
2455 ** are different from that integer. i.e. if deleting the document with docid
2456 ** pRowid would mean the FTS3 table were empty.
2457 **
2458 ** If successful, *pisEmpty is set to true if the table is empty except for
2459 ** document pRowid, or false otherwise, and SQLITE_OK is returned. If an
2460 ** error occurs, an SQLite error code is returned.
2461 */
2462 static int fts3IsEmpty(Fts3Table *p, sqlite3_value *pRowid, int *pisEmpty){
2463 sqlite3_stmt *pStmt;
2464 int rc;
2465 if( p->zContentTbl ){
2466 /* If using the content=xxx option, assume the table is never empty */
2467 *pisEmpty = 0;
2468 rc = SQLITE_OK;
2469 }else{
2470 rc = fts3SqlStmt(p, SQL_IS_EMPTY, &pStmt, &pRowid);
2471 if( rc==SQLITE_OK ){
2472 if( SQLITE_ROW==sqlite3_step(pStmt) ){
2473 *pisEmpty = sqlite3_column_int(pStmt, 0);
2474 }
2475 rc = sqlite3_reset(pStmt);
2476 }
2477 }
2478 return rc;
2479 }
2480
2481 /*
2482 ** Set *pnMax to the largest segment level in the database for the index
2483 ** iIndex.
2484 **
2485 ** Segment levels are stored in the 'level' column of the %_segdir table.
2486 **
2487 ** Return SQLITE_OK if successful, or an SQLite error code if not.
2488 */
2489 static int fts3SegmentMaxLevel(
2490 Fts3Table *p,
2491 int iLangid,
2492 int iIndex,
2493 sqlite3_int64 *pnMax
2494 ){
2495 sqlite3_stmt *pStmt;
2496 int rc;
2497 assert( iIndex>=0 && iIndex<p->nIndex );
2498
2499 /* Set pStmt to the compiled version of:
2500 **
2501 ** SELECT max(level) FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?
2502 **
2503 ** (1024 is actually the value of macro FTS3_SEGDIR_PREFIXLEVEL_STR).
2504 */
2505 rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR_MAX_LEVEL, &pStmt, 0);
2506 if( rc!=SQLITE_OK ) return rc;
2507 sqlite3_bind_int64(pStmt, 1, getAbsoluteLevel(p, iLangid, iIndex, 0));
2508 sqlite3_bind_int64(pStmt, 2,
2509 getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1)
2510 );
2511 if( SQLITE_ROW==sqlite3_step(pStmt) ){
2512 *pnMax = sqlite3_column_int64(pStmt, 0);
2513 }
2514 return sqlite3_reset(pStmt);
2515 }
2516
2517 /*
2518 ** iAbsLevel is an absolute level that may be assumed to exist within
2519 ** the database. This function checks if it is the largest level number
2520 ** within its index. Assuming no error occurs, *pbMax is set to 1 if
2521 ** iAbsLevel is indeed the largest level, or 0 otherwise, and SQLITE_OK
2522 ** is returned. If an error occurs, an error code is returned and the
2523 ** final value of *pbMax is undefined.
2524 */
2525 static int fts3SegmentIsMaxLevel(Fts3Table *p, i64 iAbsLevel, int *pbMax){
2526
2527 /* Set pStmt to the compiled version of:
2528 **
2529 ** SELECT max(level) FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?
2530 **
2531 ** (1024 is actually the value of macro FTS3_SEGDIR_PREFIXLEVEL_STR).
2532 */
2533 sqlite3_stmt *pStmt;
2534 int rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR_MAX_LEVEL, &pStmt, 0);
2535 if( rc!=SQLITE_OK ) return rc;
2536 sqlite3_bind_int64(pStmt, 1, iAbsLevel+1);
2537 sqlite3_bind_int64(pStmt, 2,
2538 (((u64)iAbsLevel/FTS3_SEGDIR_MAXLEVEL)+1) * FTS3_SEGDIR_MAXLEVEL
2539 );
2540
2541 *pbMax = 0;
2542 if( SQLITE_ROW==sqlite3_step(pStmt) ){
2543 *pbMax = sqlite3_column_type(pStmt, 0)==SQLITE_NULL;
2544 }
2545 return sqlite3_reset(pStmt);
2546 }
2547
2548 /*
2549 ** Delete all entries in the %_segments table associated with the segment
2550 ** opened with seg-reader pSeg. This function does not affect the contents
2551 ** of the %_segdir table.
2552 */
2553 static int fts3DeleteSegment(
2554 Fts3Table *p, /* FTS table handle */
2555 Fts3SegReader *pSeg /* Segment to delete */
2556 ){
2557 int rc = SQLITE_OK; /* Return code */
2558 if( pSeg->iStartBlock ){
2559 sqlite3_stmt *pDelete; /* SQL statement to delete rows */
2560 rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDelete, 0);
2561 if( rc==SQLITE_OK ){
2562 sqlite3_bind_int64(pDelete, 1, pSeg->iStartBlock);
2563 sqlite3_bind_int64(pDelete, 2, pSeg->iEndBlock);
2564 sqlite3_step(pDelete);
2565 rc = sqlite3_reset(pDelete);
2566 }
2567 }
2568 return rc;
2569 }
2570
2571 /*
2572 ** This function is used after merging multiple segments into a single large
2573 ** segment to delete the old, now redundant, segment b-trees. Specifically,
2574 ** it:
2575 **
2576 ** 1) Deletes all %_segments entries for the segments associated with
2577 ** each of the SegReader objects in the array passed as the third
2578 ** argument, and
2579 **
2580 ** 2) deletes all %_segdir entries with level iLevel, or all %_segdir
2581 ** entries regardless of level if (iLevel<0).
2582 **
2583 ** SQLITE_OK is returned if successful, otherwise an SQLite error code.
2584 */
2585 static int fts3DeleteSegdir(
2586 Fts3Table *p, /* Virtual table handle */
2587 int iLangid, /* Language id */
2588 int iIndex, /* Index for p->aIndex */
2589 int iLevel, /* Level of %_segdir entries to delete */
2590 Fts3SegReader **apSegment, /* Array of SegReader objects */
2591 int nReader /* Size of array apSegment */
2592 ){
2593 int rc = SQLITE_OK; /* Return Code */
2594 int i; /* Iterator variable */
2595 sqlite3_stmt *pDelete = 0; /* SQL statement to delete rows */
2596
2597 for(i=0; rc==SQLITE_OK && i<nReader; i++){
2598 rc = fts3DeleteSegment(p, apSegment[i]);
2599 }
2600 if( rc!=SQLITE_OK ){
2601 return rc;
2602 }
2603
2604 assert( iLevel>=0 || iLevel==FTS3_SEGCURSOR_ALL );
2605 if( iLevel==FTS3_SEGCURSOR_ALL ){
2606 rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_RANGE, &pDelete, 0);
2607 if( rc==SQLITE_OK ){
2608 sqlite3_bind_int64(pDelete, 1, getAbsoluteLevel(p, iLangid, iIndex, 0));
2609 sqlite3_bind_int64(pDelete, 2,
2610 getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1)
2611 );
2612 }
2613 }else{
2614 rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_LEVEL, &pDelete, 0);
2615 if( rc==SQLITE_OK ){
2616 sqlite3_bind_int64(
2617 pDelete, 1, getAbsoluteLevel(p, iLangid, iIndex, iLevel)
2618 );
2619 }
2620 }
2621
2622 if( rc==SQLITE_OK ){
2623 sqlite3_step(pDelete);
2624 rc = sqlite3_reset(pDelete);
2625 }
2626
2627 return rc;
2628 }
2629
2630 /*
2631 ** When this function is called, buffer *ppList (size *pnList bytes) contains
2632 ** a position list that may (or may not) feature multiple columns. This
2633 ** function adjusts the pointer *ppList and the length *pnList so that they
2634 ** identify the subset of the position list that corresponds to column iCol.
2635 **
2636 ** If there are no entries in the input position list for column iCol, then
2637 ** *pnList is set to zero before returning.
2638 **
2639 ** If parameter bZero is non-zero, then any part of the input list following
2640 ** the end of the output list is zeroed before returning.
2641 */
2642 static void fts3ColumnFilter(
2643 int iCol, /* Column to filter on */
2644 int bZero, /* Zero out anything following *ppList */
2645 char **ppList, /* IN/OUT: Pointer to position list */
2646 int *pnList /* IN/OUT: Size of buffer *ppList in bytes */
2647 ){
2648 char *pList = *ppList;
2649 int nList = *pnList;
2650 char *pEnd = &pList[nList];
2651 int iCurrent = 0;
2652 char *p = pList;
2653
2654 assert( iCol>=0 );
2655 while( 1 ){
2656 char c = 0;
2657 while( p<pEnd && (c | *p)&0xFE ) c = *p++ & 0x80;
2658
2659 if( iCol==iCurrent ){
2660 nList = (int)(p - pList);
2661 break;
2662 }
2663
2664 nList -= (int)(p - pList);
2665 pList = p;
2666 if( nList<=0 ){
2667 break;
2668 }
2669 p = &pList[1];
2670 p += fts3GetVarint32(p, &iCurrent);
2671 }
2672
2673 if( bZero && (pEnd - &pList[nList])>0){
2674 memset(&pList[nList], 0, pEnd - &pList[nList]);
2675 }
2676 *ppList = pList;
2677 *pnList = nList;
2678 }
2679
2680 /*
2681 ** Cache data in the Fts3MultiSegReader.aBuffer[] buffer (overwriting any
2682 ** existing data). Grow the buffer if required.
2683 **
2684 ** If successful, return SQLITE_OK. Otherwise, if an OOM error is encountered
2685 ** trying to resize the buffer, return SQLITE_NOMEM.
2686 */
2687 static int fts3MsrBufferData(
2688 Fts3MultiSegReader *pMsr, /* Multi-segment-reader handle */
2689 char *pList,
2690 i64 nList
2691 ){
2692 if( (nList+FTS3_NODE_PADDING)>pMsr->nBuffer ){
2693 char *pNew;
2694 int nNew = nList*2 + FTS3_NODE_PADDING;
2695 pNew = (char *)sqlite3_realloc64(pMsr->aBuffer, nNew);
2696 if( !pNew ) return SQLITE_NOMEM;
2697 pMsr->aBuffer = pNew;
2698 pMsr->nBuffer = nNew;
2699 }
2700
2701 assert( nList>0 );
2702 memcpy(pMsr->aBuffer, pList, nList);
2703 memset(&pMsr->aBuffer[nList], 0, FTS3_NODE_PADDING);
2704 return SQLITE_OK;
2705 }
2706
2707 int sqlite3Fts3MsrIncrNext(
2708 Fts3Table *p, /* Virtual table handle */
2709 Fts3MultiSegReader *pMsr, /* Multi-segment-reader handle */
2710 sqlite3_int64 *piDocid, /* OUT: Docid value */
2711 char **paPoslist, /* OUT: Pointer to position list */
2712 int *pnPoslist /* OUT: Size of position list in bytes */
2713 ){
2714 int nMerge = pMsr->nAdvance;
2715 Fts3SegReader **apSegment = pMsr->apSegment;
2716 int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
2717 p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
2718 );
2719
2720 if( nMerge==0 ){
2721 *paPoslist = 0;
2722 return SQLITE_OK;
2723 }
2724
2725 while( 1 ){
2726 Fts3SegReader *pSeg;
2727 pSeg = pMsr->apSegment[0];
2728
2729 if( pSeg->pOffsetList==0 ){
2730 *paPoslist = 0;
2731 break;
2732 }else{
2733 int rc;
2734 char *pList;
2735 int nList;
2736 int j;
2737 sqlite3_int64 iDocid = apSegment[0]->iDocid;
2738
2739 rc = fts3SegReaderNextDocid(p, apSegment[0], &pList, &nList);
2740 j = 1;
2741 while( rc==SQLITE_OK
2742 && j<nMerge
2743 && apSegment[j]->pOffsetList
2744 && apSegment[j]->iDocid==iDocid
2745 ){
2746 rc = fts3SegReaderNextDocid(p, apSegment[j], 0, 0);
2747 j++;
2748 }
2749 if( rc!=SQLITE_OK ) return rc;
2750 fts3SegReaderSort(pMsr->apSegment, nMerge, j, xCmp);
2751
2752 if( nList>0 && fts3SegReaderIsPending(apSegment[0]) ){
2753 rc = fts3MsrBufferData(pMsr, pList, (i64)nList+1);
2754 if( rc!=SQLITE_OK ) return rc;
2755 assert( (pMsr->aBuffer[nList] & 0xFE)==0x00 );
2756 pList = pMsr->aBuffer;
2757 }
2758
2759 if( pMsr->iColFilter>=0 ){
2760 fts3ColumnFilter(pMsr->iColFilter, 1, &pList, &nList);
2761 }
2762
2763 if( nList>0 ){
2764 *paPoslist = pList;
2765 *piDocid = iDocid;
2766 *pnPoslist = nList;
2767 break;
2768 }
2769 }
2770 }
2771
2772 return SQLITE_OK;
2773 }
2774
2775 static int fts3SegReaderStart(
2776 Fts3Table *p, /* Virtual table handle */
2777 Fts3MultiSegReader *pCsr, /* Cursor object */
2778 const char *zTerm, /* Term searched for (or NULL) */
2779 int nTerm /* Length of zTerm in bytes */
2780 ){
2781 int i;
2782 int nSeg = pCsr->nSegment;
2783
2784 /* If the Fts3SegFilter defines a specific term (or term prefix) to search
2785 ** for, then advance each segment iterator until it points to a term of
2786 ** equal or greater value than the specified term. This prevents many
2787 ** unnecessary merge/sort operations for the case where single segment
2788 ** b-tree leaf nodes contain more than one term.
2789 */
2790 for(i=0; pCsr->bRestart==0 && i<pCsr->nSegment; i++){
2791 int res = 0;
2792 Fts3SegReader *pSeg = pCsr->apSegment[i];
2793 do {
2794 int rc = fts3SegReaderNext(p, pSeg, 0);
2795 if( rc!=SQLITE_OK ) return rc;
2796 }while( zTerm && (res = fts3SegReaderTermCmp(pSeg, zTerm, nTerm))<0 );
2797
2798 if( pSeg->bLookup && res!=0 ){
2799 fts3SegReaderSetEof(pSeg);
2800 }
2801 }
2802 fts3SegReaderSort(pCsr->apSegment, nSeg, nSeg, fts3SegReaderCmp);
2803
2804 return SQLITE_OK;
2805 }
2806
2807 int sqlite3Fts3SegReaderStart(
2808 Fts3Table *p, /* Virtual table handle */
2809 Fts3MultiSegReader *pCsr, /* Cursor object */
2810 Fts3SegFilter *pFilter /* Restrictions on range of iteration */
2811 ){
2812 pCsr->pFilter = pFilter;
2813 return fts3SegReaderStart(p, pCsr, pFilter->zTerm, pFilter->nTerm);
2814 }
2815
2816 int sqlite3Fts3MsrIncrStart(
2817 Fts3Table *p, /* Virtual table handle */
2818 Fts3MultiSegReader *pCsr, /* Cursor object */
2819 int iCol, /* Column to match on. */
2820 const char *zTerm, /* Term to iterate through a doclist for */
2821 int nTerm /* Number of bytes in zTerm */
2822 ){
2823 int i;
2824 int rc;
2825 int nSegment = pCsr->nSegment;
2826 int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
2827 p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
2828 );
2829
2830 assert( pCsr->pFilter==0 );
2831 assert( zTerm && nTerm>0 );
2832
2833 /* Advance each segment iterator until it points to the term zTerm/nTerm. */
2834 rc = fts3SegReaderStart(p, pCsr, zTerm, nTerm);
2835 if( rc!=SQLITE_OK ) return rc;
2836
2837 /* Determine how many of the segments actually point to zTerm/nTerm. */
2838 for(i=0; i<nSegment; i++){
2839 Fts3SegReader *pSeg = pCsr->apSegment[i];
2840 if( !pSeg->aNode || fts3SegReaderTermCmp(pSeg, zTerm, nTerm) ){
2841 break;
2842 }
2843 }
2844 pCsr->nAdvance = i;
2845
2846 /* Advance each of the segments to point to the first docid. */
2847 for(i=0; i<pCsr->nAdvance; i++){
2848 rc = fts3SegReaderFirstDocid(p, pCsr->apSegment[i]);
2849 if( rc!=SQLITE_OK ) return rc;
2850 }
2851 fts3SegReaderSort(pCsr->apSegment, i, i, xCmp);
2852
2853 assert( iCol<0 || iCol<p->nColumn );
2854 pCsr->iColFilter = iCol;
2855
2856 return SQLITE_OK;
2857 }
2858
2859 /*
2860 ** This function is called on a MultiSegReader that has been started using
2861 ** sqlite3Fts3MsrIncrStart(). One or more calls to MsrIncrNext() may also
2862 ** have been made. Calling this function puts the MultiSegReader in such
2863 ** a state that if the next two calls are:
2864 **
2865 ** sqlite3Fts3SegReaderStart()
2866 ** sqlite3Fts3SegReaderStep()
2867 **
2868 ** then the entire doclist for the term is available in
2869 ** MultiSegReader.aDoclist/nDoclist.
2870 */
2871 int sqlite3Fts3MsrIncrRestart(Fts3MultiSegReader *pCsr){
2872 int i; /* Used to iterate through segment-readers */
2873
2874 assert( pCsr->zTerm==0 );
2875 assert( pCsr->nTerm==0 );
2876 assert( pCsr->aDoclist==0 );
2877 assert( pCsr->nDoclist==0 );
2878
2879 pCsr->nAdvance = 0;
2880 pCsr->bRestart = 1;
2881 for(i=0; i<pCsr->nSegment; i++){
2882 pCsr->apSegment[i]->pOffsetList = 0;
2883 pCsr->apSegment[i]->nOffsetList = 0;
2884 pCsr->apSegment[i]->iDocid = 0;
2885 }
2886
2887 return SQLITE_OK;
2888 }
2889
2890 static int fts3GrowSegReaderBuffer(Fts3MultiSegReader *pCsr, i64 nReq){
2891 if( nReq>pCsr->nBuffer ){
2892 char *aNew;
2893 pCsr->nBuffer = nReq*2;
2894 aNew = sqlite3_realloc64(pCsr->aBuffer, pCsr->nBuffer);
2895 if( !aNew ){
2896 return SQLITE_NOMEM;
2897 }
2898 pCsr->aBuffer = aNew;
2899 }
2900 return SQLITE_OK;
2901 }
2902
2903
2904 int sqlite3Fts3SegReaderStep(
2905 Fts3Table *p, /* Virtual table handle */
2906 Fts3MultiSegReader *pCsr /* Cursor object */
2907 ){
2908 int rc = SQLITE_OK;
2909
2910 int isIgnoreEmpty = (pCsr->pFilter->flags & FTS3_SEGMENT_IGNORE_EMPTY);
2911 int isRequirePos = (pCsr->pFilter->flags & FTS3_SEGMENT_REQUIRE_POS);
2912 int isColFilter = (pCsr->pFilter->flags & FTS3_SEGMENT_COLUMN_FILTER);
2913 int isPrefix = (pCsr->pFilter->flags & FTS3_SEGMENT_PREFIX);
2914 int isScan = (pCsr->pFilter->flags & FTS3_SEGMENT_SCAN);
2915 int isFirst = (pCsr->pFilter->flags & FTS3_SEGMENT_FIRST);
2916
2917 Fts3SegReader **apSegment = pCsr->apSegment;
2918 int nSegment = pCsr->nSegment;
2919 Fts3SegFilter *pFilter = pCsr->pFilter;
2920 int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
2921 p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
2922 );
2923
2924 if( pCsr->nSegment==0 ) return SQLITE_OK;
2925
2926 do {
2927 int nMerge;
2928 int i;
2929
2930 /* Advance the first pCsr->nAdvance entries in the apSegment[] array
2931 ** forward. Then sort the list in order of current term again.
2932 */
2933 for(i=0; i<pCsr->nAdvance; i++){
2934 Fts3SegReader *pSeg = apSegment[i];
2935 if( pSeg->bLookup ){
2936 fts3SegReaderSetEof(pSeg);
2937 }else{
2938 rc = fts3SegReaderNext(p, pSeg, 0);
2939 }
2940 if( rc!=SQLITE_OK ) return rc;
2941 }
2942 fts3SegReaderSort(apSegment, nSegment, pCsr->nAdvance, fts3SegReaderCmp);
2943 pCsr->nAdvance = 0;
2944
2945 /* If all the seg-readers are at EOF, we're finished. return SQLITE_OK. */
2946 assert( rc==SQLITE_OK );
2947 if( apSegment[0]->aNode==0 ) break;
2948
2949 pCsr->nTerm = apSegment[0]->nTerm;
2950 pCsr->zTerm = apSegment[0]->zTerm;
2951
2952 /* If this is a prefix-search, and if the term that apSegment[0] points
2953 ** to does not share a suffix with pFilter->zTerm/nTerm, then all
2954 ** required callbacks have been made. In this case exit early.
2955 **
2956 ** Similarly, if this is a search for an exact match, and the first term
2957 ** of segment apSegment[0] is not a match, exit early.
2958 */
2959 if( pFilter->zTerm && !isScan ){
2960 if( pCsr->nTerm<pFilter->nTerm
2961 || (!isPrefix && pCsr->nTerm>pFilter->nTerm)
2962 || memcmp(pCsr->zTerm, pFilter->zTerm, pFilter->nTerm)
2963 ){
2964 break;
2965 }
2966 }
2967
2968 nMerge = 1;
2969 while( nMerge<nSegment
2970 && apSegment[nMerge]->aNode
2971 && apSegment[nMerge]->nTerm==pCsr->nTerm
2972 && 0==memcmp(pCsr->zTerm, apSegment[nMerge]->zTerm, pCsr->nTerm)
2973 ){
2974 nMerge++;
2975 }
2976
2977 assert( isIgnoreEmpty || (isRequirePos && !isColFilter) );
2978 if( nMerge==1
2979 && !isIgnoreEmpty
2980 && !isFirst
2981 && (p->bDescIdx==0 || fts3SegReaderIsPending(apSegment[0])==0)
2982 ){
2983 pCsr->nDoclist = apSegment[0]->nDoclist;
2984 if( fts3SegReaderIsPending(apSegment[0]) ){
2985 rc = fts3MsrBufferData(pCsr, apSegment[0]->aDoclist,
2986 (i64)pCsr->nDoclist);
2987 pCsr->aDoclist = pCsr->aBuffer;
2988 }else{
2989 pCsr->aDoclist = apSegment[0]->aDoclist;
2990 }
2991 if( rc==SQLITE_OK ) rc = SQLITE_ROW;
2992 }else{
2993 int nDoclist = 0; /* Size of doclist */
2994 sqlite3_int64 iPrev = 0; /* Previous docid stored in doclist */
2995
2996 /* The current term of the first nMerge entries in the array
2997 ** of Fts3SegReader objects is the same. The doclists must be merged
2998 ** and a single term returned with the merged doclist.
2999 */
3000 for(i=0; i<nMerge; i++){
3001 fts3SegReaderFirstDocid(p, apSegment[i]);
3002 }
3003 fts3SegReaderSort(apSegment, nMerge, nMerge, xCmp);
3004 while( apSegment[0]->pOffsetList ){
3005 int j; /* Number of segments that share a docid */
3006 char *pList = 0;
3007 int nList = 0;
3008 int nByte;
3009 sqlite3_int64 iDocid = apSegment[0]->iDocid;
3010 fts3SegReaderNextDocid(p, apSegment[0], &pList, &nList);
3011 j = 1;
3012 while( j<nMerge
3013 && apSegment[j]->pOffsetList
3014 && apSegment[j]->iDocid==iDocid
3015 ){
3016 fts3SegReaderNextDocid(p, apSegment[j], 0, 0);
3017 j++;
3018 }
3019
3020 if( isColFilter ){
3021 fts3ColumnFilter(pFilter->iCol, 0, &pList, &nList);
3022 }
3023
3024 if( !isIgnoreEmpty || nList>0 ){
3025
3026 /* Calculate the 'docid' delta value to write into the merged
3027 ** doclist. */
3028 sqlite3_int64 iDelta;
3029 if( p->bDescIdx && nDoclist>0 ){
3030 if( iPrev<=iDocid ) return FTS_CORRUPT_VTAB;
3031 iDelta = (i64)((u64)iPrev - (u64)iDocid);
3032 }else{
3033 if( nDoclist>0 && iPrev>=iDocid ) return FTS_CORRUPT_VTAB;
3034 iDelta = (i64)((u64)iDocid - (u64)iPrev);
3035 }
3036
3037 nByte = sqlite3Fts3VarintLen(iDelta) + (isRequirePos?nList+1:0);
3038
3039 rc = fts3GrowSegReaderBuffer(pCsr,
3040 (i64)nByte+nDoclist+FTS3_NODE_PADDING);
3041 if( rc ) return rc;
3042
3043 if( isFirst ){
3044 char *a = &pCsr->aBuffer[nDoclist];
3045 int nWrite;
3046
3047 nWrite = sqlite3Fts3FirstFilter(iDelta, pList, nList, a);
3048 if( nWrite ){
3049 iPrev = iDocid;
3050 nDoclist += nWrite;
3051 }
3052 }else{
3053 nDoclist += sqlite3Fts3PutVarint(&pCsr->aBuffer[nDoclist], iDelta);
3054 iPrev = iDocid;
3055 if( isRequirePos ){
3056 memcpy(&pCsr->aBuffer[nDoclist], pList, nList);
3057 nDoclist += nList;
3058 pCsr->aBuffer[nDoclist++] = '\0';
3059 }
3060 }
3061 }
3062
3063 fts3SegReaderSort(apSegment, nMerge, j, xCmp);
3064 }
3065 if( nDoclist>0 ){
3066 rc = fts3GrowSegReaderBuffer(pCsr, (i64)nDoclist+FTS3_NODE_PADDING);
3067 if( rc ) return rc;
3068 memset(&pCsr->aBuffer[nDoclist], 0, FTS3_NODE_PADDING);
3069 pCsr->aDoclist = pCsr->aBuffer;
3070 pCsr->nDoclist = nDoclist;
3071 rc = SQLITE_ROW;
3072 }
3073 }
3074 pCsr->nAdvance = nMerge;
3075 }while( rc==SQLITE_OK );
3076
3077 return rc;
3078 }
3079
3080
3081 void sqlite3Fts3SegReaderFinish(
3082 Fts3MultiSegReader *pCsr /* Cursor object */
3083 ){
3084 if( pCsr ){
3085 int i;
3086 for(i=0; i<pCsr->nSegment; i++){
3087 sqlite3Fts3SegReaderFree(pCsr->apSegment[i]);
3088 }
3089 sqlite3_free(pCsr->apSegment);
3090 sqlite3_free(pCsr->aBuffer);
3091
3092 pCsr->nSegment = 0;
3093 pCsr->apSegment = 0;
3094 pCsr->aBuffer = 0;
3095 }
3096 }
3097
3098 /*
3099 ** Decode the "end_block" field, selected by column iCol of the SELECT
3100 ** statement passed as the first argument.
3101 **
3102 ** The "end_block" field may contain either an integer, or a text field
3103 ** containing the text representation of two non-negative integers separated
3104 ** by one or more space (0x20) characters. In the first case, set *piEndBlock
3105 ** to the integer value and *pnByte to zero before returning. In the second,
3106 ** set *piEndBlock to the first value and *pnByte to the second.
3107 */
3108 static void fts3ReadEndBlockField(
3109 sqlite3_stmt *pStmt,
3110 int iCol,
3111 i64 *piEndBlock,
3112 i64 *pnByte
3113 ){
3114 const unsigned char *zText = sqlite3_column_text(pStmt, iCol);
3115 if( zText ){
3116 int i;
3117 int iMul = 1;
3118 u64 iVal = 0;
3119 for(i=0; zText[i]>='0' && zText[i]<='9'; i++){
3120 iVal = iVal*10 + (zText[i] - '0');
3121 }
3122 *piEndBlock = (i64)iVal;
3123 while( zText[i]==' ' ) i++;
3124 iVal = 0;
3125 if( zText[i]=='-' ){
3126 i++;
3127 iMul = -1;
3128 }
3129 for(/* no-op */; zText[i]>='0' && zText[i]<='9'; i++){
3130 iVal = iVal*10 + (zText[i] - '0');
3131 }
3132 *pnByte = ((i64)iVal * (i64)iMul);
3133 }
3134 }
3135
3136
3137 /*
3138 ** A segment of size nByte bytes has just been written to absolute level
3139 ** iAbsLevel. Promote any segments that should be promoted as a result.
3140 */
3141 static int fts3PromoteSegments(
3142 Fts3Table *p, /* FTS table handle */
3143 sqlite3_int64 iAbsLevel, /* Absolute level just updated */
3144 sqlite3_int64 nByte /* Size of new segment at iAbsLevel */
3145 ){
3146 int rc = SQLITE_OK;
3147 sqlite3_stmt *pRange;
3148
3149 rc = fts3SqlStmt(p, SQL_SELECT_LEVEL_RANGE2, &pRange, 0);
3150
3151 if( rc==SQLITE_OK ){
3152 int bOk = 0;
3153 i64 iLast = (iAbsLevel/FTS3_SEGDIR_MAXLEVEL + 1) * FTS3_SEGDIR_MAXLEVEL - 1;
3154 i64 nLimit = (nByte*3)/2;
3155
3156 /* Loop through all entries in the %_segdir table corresponding to
3157 ** segments in this index on levels greater than iAbsLevel. If there is
3158 ** at least one such segment, and it is possible to determine that all
3159 ** such segments are smaller than nLimit bytes in size, they will be
3160 ** promoted to level iAbsLevel. */
3161 sqlite3_bind_int64(pRange, 1, iAbsLevel+1);
3162 sqlite3_bind_int64(pRange, 2, iLast);
3163 while( SQLITE_ROW==sqlite3_step(pRange) ){
3164 i64 nSize = 0, dummy;
3165 fts3ReadEndBlockField(pRange, 2, &dummy, &nSize);
3166 if( nSize<=0 || nSize>nLimit ){
3167 /* If nSize==0, then the %_segdir.end_block field does not not
3168 ** contain a size value. This happens if it was written by an
3169 ** old version of FTS. In this case it is not possible to determine
3170 ** the size of the segment, and so segment promotion does not
3171 ** take place. */
3172 bOk = 0;
3173 break;
3174 }
3175 bOk = 1;
3176 }
3177 rc = sqlite3_reset(pRange);
3178
3179 if( bOk ){
3180 int iIdx = 0;
3181 sqlite3_stmt *pUpdate1 = 0;
3182 sqlite3_stmt *pUpdate2 = 0;
3183
3184 if( rc==SQLITE_OK ){
3185 rc = fts3SqlStmt(p, SQL_UPDATE_LEVEL_IDX, &pUpdate1, 0);
3186 }
3187 if( rc==SQLITE_OK ){
3188 rc = fts3SqlStmt(p, SQL_UPDATE_LEVEL, &pUpdate2, 0);
3189 }
3190
3191 if( rc==SQLITE_OK ){
3192
3193 /* Loop through all %_segdir entries for segments in this index with
3194 ** levels equal to or greater than iAbsLevel. As each entry is visited,
3195 ** updated it to set (level = -1) and (idx = N), where N is 0 for the
3196 ** oldest segment in the range, 1 for the next oldest, and so on.
3197 **
3198 ** In other words, move all segments being promoted to level -1,
3199 ** setting the "idx" fields as appropriate to keep them in the same
3200 ** order. The contents of level -1 (which is never used, except
3201 ** transiently here), will be moved back to level iAbsLevel below. */
3202 sqlite3_bind_int64(pRange, 1, iAbsLevel);
3203 while( SQLITE_ROW==sqlite3_step(pRange) ){
3204 sqlite3_bind_int(pUpdate1, 1, iIdx++);
3205 sqlite3_bind_int(pUpdate1, 2, sqlite3_column_int(pRange, 0));
3206 sqlite3_bind_int(pUpdate1, 3, sqlite3_column_int(pRange, 1));
3207 sqlite3_step(pUpdate1);
3208 rc = sqlite3_reset(pUpdate1);
3209 if( rc!=SQLITE_OK ){
3210 sqlite3_reset(pRange);
3211 break;
3212 }
3213 }
3214 }
3215 if( rc==SQLITE_OK ){
3216 rc = sqlite3_reset(pRange);
3217 }
3218
3219 /* Move level -1 to level iAbsLevel */
3220 if( rc==SQLITE_OK ){
3221 sqlite3_bind_int64(pUpdate2, 1, iAbsLevel);
3222 sqlite3_step(pUpdate2);
3223 rc = sqlite3_reset(pUpdate2);
3224 }
3225 }
3226 }
3227
3228
3229 return rc;
3230 }
3231
3232 /*
3233 ** Merge all level iLevel segments in the database into a single
3234 ** iLevel+1 segment. Or, if iLevel<0, merge all segments into a
3235 ** single segment with a level equal to the numerically largest level
3236 ** currently present in the database.
3237 **
3238 ** If this function is called with iLevel<0, but there is only one
3239 ** segment in the database, SQLITE_DONE is returned immediately.
3240 ** Otherwise, if successful, SQLITE_OK is returned. If an error occurs,
3241 ** an SQLite error code is returned.
3242 */
3243 static int fts3SegmentMerge(
3244 Fts3Table *p,
3245 int iLangid, /* Language id to merge */
3246 int iIndex, /* Index in p->aIndex[] to merge */
3247 int iLevel /* Level to merge */
3248 ){
3249 int rc; /* Return code */
3250 int iIdx = 0; /* Index of new segment */
3251 sqlite3_int64 iNewLevel = 0; /* Level/index to create new segment at */
3252 SegmentWriter *pWriter = 0; /* Used to write the new, merged, segment */
3253 Fts3SegFilter filter; /* Segment term filter condition */
3254 Fts3MultiSegReader csr; /* Cursor to iterate through level(s) */
3255 int bIgnoreEmpty = 0; /* True to ignore empty segments */
3256 i64 iMaxLevel = 0; /* Max level number for this index/langid */
3257
3258 assert( iLevel==FTS3_SEGCURSOR_ALL
3259 || iLevel==FTS3_SEGCURSOR_PENDING
3260 || iLevel>=0
3261 );
3262 assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
3263 assert( iIndex>=0 && iIndex<p->nIndex );
3264
3265 rc = sqlite3Fts3SegReaderCursor(p, iLangid, iIndex, iLevel, 0, 0, 1, 0, &csr);
3266 if( rc!=SQLITE_OK || csr.nSegment==0 ) goto finished;
3267
3268 if( iLevel!=FTS3_SEGCURSOR_PENDING ){
3269 rc = fts3SegmentMaxLevel(p, iLangid, iIndex, &iMaxLevel);
3270 if( rc!=SQLITE_OK ) goto finished;
3271 }
3272
3273 if( iLevel==FTS3_SEGCURSOR_ALL ){
3274 /* This call is to merge all segments in the database to a single
3275 ** segment. The level of the new segment is equal to the numerically
3276 ** greatest segment level currently present in the database for this
3277 ** index. The idx of the new segment is always 0. */
3278 if( csr.nSegment==1 && 0==fts3SegReaderIsPending(csr.apSegment[0]) ){
3279 rc = SQLITE_DONE;
3280 goto finished;
3281 }
3282 iNewLevel = iMaxLevel;
3283 bIgnoreEmpty = 1;
3284
3285 }else{
3286 /* This call is to merge all segments at level iLevel. find the next
3287 ** available segment index at level iLevel+1. The call to
3288 ** fts3AllocateSegdirIdx() will merge the segments at level iLevel+1 to
3289 ** a single iLevel+2 segment if necessary. */
3290 assert( FTS3_SEGCURSOR_PENDING==-1 );
3291 iNewLevel = getAbsoluteLevel(p, iLangid, iIndex, iLevel+1);
3292 rc = fts3AllocateSegdirIdx(p, iLangid, iIndex, iLevel+1, &iIdx);
3293 bIgnoreEmpty = (iLevel!=FTS3_SEGCURSOR_PENDING) && (iNewLevel>iMaxLevel);
3294 }
3295 if( rc!=SQLITE_OK ) goto finished;
3296
3297 assert( csr.nSegment>0 );
3298 assert_fts3_nc( iNewLevel>=getAbsoluteLevel(p, iLangid, iIndex, 0) );
3299 assert_fts3_nc(
3300 iNewLevel<getAbsoluteLevel(p, iLangid, iIndex,FTS3_SEGDIR_MAXLEVEL)
3301 );
3302
3303 memset(&filter, 0, sizeof(Fts3SegFilter));
3304 filter.flags = FTS3_SEGMENT_REQUIRE_POS;
3305 filter.flags |= (bIgnoreEmpty ? FTS3_SEGMENT_IGNORE_EMPTY : 0);
3306
3307 rc = sqlite3Fts3SegReaderStart(p, &csr, &filter);
3308 while( SQLITE_OK==rc ){
3309 rc = sqlite3Fts3SegReaderStep(p, &csr);
3310 if( rc!=SQLITE_ROW ) break;
3311 rc = fts3SegWriterAdd(p, &pWriter, 1,
3312 csr.zTerm, csr.nTerm, csr.aDoclist, csr.nDoclist);
3313 }
3314 if( rc!=SQLITE_OK ) goto finished;
3315 assert_fts3_nc( pWriter || bIgnoreEmpty );
3316
3317 if( iLevel!=FTS3_SEGCURSOR_PENDING ){
3318 rc = fts3DeleteSegdir(
3319 p, iLangid, iIndex, iLevel, csr.apSegment, csr.nSegment
3320 );
3321 if( rc!=SQLITE_OK ) goto finished;
3322 }
3323 if( pWriter ){
3324 rc = fts3SegWriterFlush(p, pWriter, iNewLevel, iIdx);
3325 if( rc==SQLITE_OK ){
3326 if( iLevel==FTS3_SEGCURSOR_PENDING || iNewLevel<iMaxLevel ){
3327 rc = fts3PromoteSegments(p, iNewLevel, pWriter->nLeafData);
3328 }
3329 }
3330 }
3331
3332 finished:
3333 fts3SegWriterFree(pWriter);
3334 sqlite3Fts3SegReaderFinish(&csr);
3335 return rc;
3336 }
3337
3338
3339 /*
3340 ** Flush the contents of pendingTerms to level 0 segments.
3341 */
3342 int sqlite3Fts3PendingTermsFlush(Fts3Table *p){
3343 int rc = SQLITE_OK;
3344 int i;
3345
3346 for(i=0; rc==SQLITE_OK && i<p->nIndex; i++){
3347 rc = fts3SegmentMerge(p, p->iPrevLangid, i, FTS3_SEGCURSOR_PENDING);
3348 if( rc==SQLITE_DONE ) rc = SQLITE_OK;
3349 }
3350
3351 /* Determine the auto-incr-merge setting if unknown. If enabled,
3352 ** estimate the number of leaf blocks of content to be written
3353 */
3354 if( rc==SQLITE_OK && p->bHasStat
3355 && p->nAutoincrmerge==0xff && p->nLeafAdd>0
3356 ){
3357 sqlite3_stmt *pStmt = 0;
3358 rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pStmt, 0);
3359 if( rc==SQLITE_OK ){
3360 sqlite3_bind_int(pStmt, 1, FTS_STAT_AUTOINCRMERGE);
3361 rc = sqlite3_step(pStmt);
3362 if( rc==SQLITE_ROW ){
3363 p->nAutoincrmerge = sqlite3_column_int(pStmt, 0);
3364 if( p->nAutoincrmerge==1 ) p->nAutoincrmerge = 8;
3365 }else if( rc==SQLITE_DONE ){
3366 p->nAutoincrmerge = 0;
3367 }
3368 rc = sqlite3_reset(pStmt);
3369 }
3370 }
3371
3372 if( rc==SQLITE_OK ){
3373 sqlite3Fts3PendingTermsClear(p);
3374 }
3375 return rc;
3376 }
3377
3378 /*
3379 ** Encode N integers as varints into a blob.
3380 */
3381 static void fts3EncodeIntArray(
3382 int N, /* The number of integers to encode */
3383 u32 *a, /* The integer values */
3384 char *zBuf, /* Write the BLOB here */
3385 int *pNBuf /* Write number of bytes if zBuf[] used here */
3386 ){
3387 int i, j;
3388 for(i=j=0; i<N; i++){
3389 j += sqlite3Fts3PutVarint(&zBuf[j], (sqlite3_int64)a[i]);
3390 }
3391 *pNBuf = j;
3392 }
3393
3394 /*
3395 ** Decode a blob of varints into N integers
3396 */
3397 static void fts3DecodeIntArray(
3398 int N, /* The number of integers to decode */
3399 u32 *a, /* Write the integer values */
3400 const char *zBuf, /* The BLOB containing the varints */
3401 int nBuf /* size of the BLOB */
3402 ){
3403 int i = 0;
3404 if( nBuf && (zBuf[nBuf-1]&0x80)==0 ){
3405 int j;
3406 for(i=j=0; i<N && j<nBuf; i++){
3407 sqlite3_int64 x;
3408 j += sqlite3Fts3GetVarint(&zBuf[j], &x);
3409 a[i] = (u32)(x & 0xffffffff);
3410 }
3411 }
3412 while( i<N ) a[i++] = 0;
3413 }
3414
3415 /*
3416 ** Insert the sizes (in tokens) for each column of the document
3417 ** with docid equal to p->iPrevDocid. The sizes are encoded as
3418 ** a blob of varints.
3419 */
3420 static void fts3InsertDocsize(
3421 int *pRC, /* Result code */
3422 Fts3Table *p, /* Table into which to insert */
3423 u32 *aSz /* Sizes of each column, in tokens */
3424 ){
3425 char *pBlob; /* The BLOB encoding of the document size */
3426 int nBlob; /* Number of bytes in the BLOB */
3427 sqlite3_stmt *pStmt; /* Statement used to insert the encoding */
3428 int rc; /* Result code from subfunctions */
3429
3430 if( *pRC ) return;
3431 pBlob = sqlite3_malloc64( 10*(sqlite3_int64)p->nColumn );
3432 if( pBlob==0 ){
3433 *pRC = SQLITE_NOMEM;
3434 return;
3435 }
3436 fts3EncodeIntArray(p->nColumn, aSz, pBlob, &nBlob);
3437 rc = fts3SqlStmt(p, SQL_REPLACE_DOCSIZE, &pStmt, 0);
3438 if( rc ){
3439 sqlite3_free(pBlob);
3440 *pRC = rc;
3441 return;
3442 }
3443 sqlite3_bind_int64(pStmt, 1, p->iPrevDocid);
3444 sqlite3_bind_blob(pStmt, 2, pBlob, nBlob, sqlite3_free);
3445 sqlite3_step(pStmt);
3446 *pRC = sqlite3_reset(pStmt);
3447 }
3448
3449 /*
3450 ** Record 0 of the %_stat table contains a blob consisting of N varints,
3451 ** where N is the number of user defined columns in the fts3 table plus
3452 ** two. If nCol is the number of user defined columns, then values of the
3453 ** varints are set as follows:
3454 **
3455 ** Varint 0: Total number of rows in the table.
3456 **
3457 ** Varint 1..nCol: For each column, the total number of tokens stored in
3458 ** the column for all rows of the table.
3459 **
3460 ** Varint 1+nCol: The total size, in bytes, of all text values in all
3461 ** columns of all rows of the table.
3462 **
3463 */
3464 static void fts3UpdateDocTotals(
3465 int *pRC, /* The result code */
3466 Fts3Table *p, /* Table being updated */
3467 u32 *aSzIns, /* Size increases */
3468 u32 *aSzDel, /* Size decreases */
3469 int nChng /* Change in the number of documents */
3470 ){
3471 char *pBlob; /* Storage for BLOB written into %_stat */
3472 int nBlob; /* Size of BLOB written into %_stat */
3473 u32 *a; /* Array of integers that becomes the BLOB */
3474 sqlite3_stmt *pStmt; /* Statement for reading and writing */
3475 int i; /* Loop counter */
3476 int rc; /* Result code from subfunctions */
3477
3478 const int nStat = p->nColumn+2;
3479
3480 if( *pRC ) return;
3481 a = sqlite3_malloc64( (sizeof(u32)+10)*(sqlite3_int64)nStat );
3482 if( a==0 ){
3483 *pRC = SQLITE_NOMEM;
3484 return;
3485 }
3486 pBlob = (char*)&a[nStat];
3487 rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pStmt, 0);
3488 if( rc ){
3489 sqlite3_free(a);
3490 *pRC = rc;
3491 return;
3492 }
3493 sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
3494 if( sqlite3_step(pStmt)==SQLITE_ROW ){
3495 fts3DecodeIntArray(nStat, a,
3496 sqlite3_column_blob(pStmt, 0),
3497 sqlite3_column_bytes(pStmt, 0));
3498 }else{
3499 memset(a, 0, sizeof(u32)*(nStat) );
3500 }
3501 rc = sqlite3_reset(pStmt);
3502 if( rc!=SQLITE_OK ){
3503 sqlite3_free(a);
3504 *pRC = rc;
3505 return;
3506 }
3507 if( nChng<0 && a[0]<(u32)(-nChng) ){
3508 a[0] = 0;
3509 }else{
3510 a[0] += nChng;
3511 }
3512 for(i=0; i<p->nColumn+1; i++){
3513 u32 x = a[i+1];
3514 if( x+aSzIns[i] < aSzDel[i] ){
3515 x = 0;
3516 }else{
3517 x = x + aSzIns[i] - aSzDel[i];
3518 }
3519 a[i+1] = x;
3520 }
3521 fts3EncodeIntArray(nStat, a, pBlob, &nBlob);
3522 rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pStmt, 0);
3523 if( rc ){
3524 sqlite3_free(a);
3525 *pRC = rc;
3526 return;
3527 }
3528 sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
3529 sqlite3_bind_blob(pStmt, 2, pBlob, nBlob, SQLITE_STATIC);
3530 sqlite3_step(pStmt);
3531 *pRC = sqlite3_reset(pStmt);
3532 sqlite3_bind_null(pStmt, 2);
3533 sqlite3_free(a);
3534 }
3535
3536 /*
3537 ** Merge the entire database so that there is one segment for each
3538 ** iIndex/iLangid combination.
3539 */
3540 static int fts3DoOptimize(Fts3Table *p, int bReturnDone){
3541 int bSeenDone = 0;
3542 int rc;
3543 sqlite3_stmt *pAllLangid = 0;
3544
3545 rc = sqlite3Fts3PendingTermsFlush(p);
3546 if( rc==SQLITE_OK ){
3547 rc = fts3SqlStmt(p, SQL_SELECT_ALL_LANGID, &pAllLangid, 0);
3548 }
3549 if( rc==SQLITE_OK ){
3550 int rc2;
3551 sqlite3_bind_int(pAllLangid, 1, p->iPrevLangid);
3552 sqlite3_bind_int(pAllLangid, 2, p->nIndex);
3553 while( sqlite3_step(pAllLangid)==SQLITE_ROW ){
3554 int i;
3555 int iLangid = sqlite3_column_int(pAllLangid, 0);
3556 for(i=0; rc==SQLITE_OK && i<p->nIndex; i++){
3557 rc = fts3SegmentMerge(p, iLangid, i, FTS3_SEGCURSOR_ALL);
3558 if( rc==SQLITE_DONE ){
3559 bSeenDone = 1;
3560 rc = SQLITE_OK;
3561 }
3562 }
3563 }
3564 rc2 = sqlite3_reset(pAllLangid);
3565 if( rc==SQLITE_OK ) rc = rc2;
3566 }
3567
3568 sqlite3Fts3SegmentsClose(p);
3569
3570 return (rc==SQLITE_OK && bReturnDone && bSeenDone) ? SQLITE_DONE : rc;
3571 }
3572
3573 /*
3574 ** This function is called when the user executes the following statement:
3575 **
3576 ** INSERT INTO <tbl>(<tbl>) VALUES('rebuild');
3577 **
3578 ** The entire FTS index is discarded and rebuilt. If the table is one
3579 ** created using the content=xxx option, then the new index is based on
3580 ** the current contents of the xxx table. Otherwise, it is rebuilt based
3581 ** on the contents of the %_content table.
3582 */
3583 static int fts3DoRebuild(Fts3Table *p){
3584 int rc; /* Return Code */
3585
3586 rc = fts3DeleteAll(p, 0);
3587 if( rc==SQLITE_OK ){
3588 u32 *aSz = 0;
3589 u32 *aSzIns = 0;
3590 u32 *aSzDel = 0;
3591 sqlite3_stmt *pStmt = 0;
3592 int nEntry = 0;
3593
3594 /* Compose and prepare an SQL statement to loop through the content table */
3595 char *zSql = sqlite3_mprintf("SELECT %s" , p->zReadExprlist);
3596 if( !zSql ){
3597 rc = SQLITE_NOMEM;
3598 }else{
3599 rc = sqlite3Fts3PrepareStmt(p, zSql, 0, 1, &pStmt);
3600 sqlite3_free(zSql);
3601 }
3602
3603 if( rc==SQLITE_OK ){
3604 sqlite3_int64 nByte = sizeof(u32) * ((sqlite3_int64)p->nColumn+1)*3;
3605 aSz = (u32 *)sqlite3_malloc64(nByte);
3606 if( aSz==0 ){
3607 rc = SQLITE_NOMEM;
3608 }else{
3609 memset(aSz, 0, nByte);
3610 aSzIns = &aSz[p->nColumn+1];
3611 aSzDel = &aSzIns[p->nColumn+1];
3612 }
3613 }
3614
3615 while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
3616 int iCol;
3617 int iLangid = langidFromSelect(p, pStmt);
3618 rc = fts3PendingTermsDocid(p, 0, iLangid, sqlite3_column_int64(pStmt, 0));
3619 memset(aSz, 0, sizeof(aSz[0]) * (p->nColumn+1));
3620 for(iCol=0; rc==SQLITE_OK && iCol<p->nColumn; iCol++){
3621 if( p->abNotindexed[iCol]==0 ){
3622 const char *z = (const char *) sqlite3_column_text(pStmt, iCol+1);
3623 rc = fts3PendingTermsAdd(p, iLangid, z, iCol, &aSz[iCol]);
3624 aSz[p->nColumn] += sqlite3_column_bytes(pStmt, iCol+1);
3625 }
3626 }
3627 if( p->bHasDocsize ){
3628 fts3InsertDocsize(&rc, p, aSz);
3629 }
3630 if( rc!=SQLITE_OK ){
3631 sqlite3_finalize(pStmt);
3632 pStmt = 0;
3633 }else{
3634 nEntry++;
3635 for(iCol=0; iCol<=p->nColumn; iCol++){
3636 aSzIns[iCol] += aSz[iCol];
3637 }
3638 }
3639 }
3640 if( p->bFts4 ){
3641 fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nEntry);
3642 }
3643 sqlite3_free(aSz);
3644
3645 if( pStmt ){
3646 int rc2 = sqlite3_finalize(pStmt);
3647 if( rc==SQLITE_OK ){
3648 rc = rc2;
3649 }
3650 }
3651 }
3652
3653 return rc;
3654 }
3655
3656
3657 /*
3658 ** This function opens a cursor used to read the input data for an
3659 ** incremental merge operation. Specifically, it opens a cursor to scan
3660 ** the oldest nSeg segments (idx=0 through idx=(nSeg-1)) in absolute
3661 ** level iAbsLevel.
3662 */
3663 static int fts3IncrmergeCsr(
3664 Fts3Table *p, /* FTS3 table handle */
3665 sqlite3_int64 iAbsLevel, /* Absolute level to open */
3666 int nSeg, /* Number of segments to merge */
3667 Fts3MultiSegReader *pCsr /* Cursor object to populate */
3668 ){
3669 int rc; /* Return Code */
3670 sqlite3_stmt *pStmt = 0; /* Statement used to read %_segdir entry */
3671 sqlite3_int64 nByte; /* Bytes allocated at pCsr->apSegment[] */
3672
3673 /* Allocate space for the Fts3MultiSegReader.aCsr[] array */
3674 memset(pCsr, 0, sizeof(*pCsr));
3675 nByte = sizeof(Fts3SegReader *) * nSeg;
3676 pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc64(nByte);
3677
3678 if( pCsr->apSegment==0 ){
3679 rc = SQLITE_NOMEM;
3680 }else{
3681 memset(pCsr->apSegment, 0, nByte);
3682 rc = fts3SqlStmt(p, SQL_SELECT_LEVEL, &pStmt, 0);
3683 }
3684 if( rc==SQLITE_OK ){
3685 int i;
3686 int rc2;
3687 sqlite3_bind_int64(pStmt, 1, iAbsLevel);
3688 assert( pCsr->nSegment==0 );
3689 for(i=0; rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW && i<nSeg; i++){
3690 rc = sqlite3Fts3SegReaderNew(i, 0,
3691 sqlite3_column_int64(pStmt, 1), /* segdir.start_block */
3692 sqlite3_column_int64(pStmt, 2), /* segdir.leaves_end_block */
3693 sqlite3_column_int64(pStmt, 3), /* segdir.end_block */
3694 sqlite3_column_blob(pStmt, 4), /* segdir.root */
3695 sqlite3_column_bytes(pStmt, 4), /* segdir.root */
3696 &pCsr->apSegment[i]
3697 );
3698 pCsr->nSegment++;
3699 }
3700 rc2 = sqlite3_reset(pStmt);
3701 if( rc==SQLITE_OK ) rc = rc2;
3702 }
3703
3704 return rc;
3705 }
3706
3707 typedef struct IncrmergeWriter IncrmergeWriter;
3708 typedef struct NodeWriter NodeWriter;
3709 typedef struct Blob Blob;
3710 typedef struct NodeReader NodeReader;
3711
3712 /*
3713 ** An instance of the following structure is used as a dynamic buffer
3714 ** to build up nodes or other blobs of data in.
3715 **
3716 ** The function blobGrowBuffer() is used to extend the allocation.
3717 */
3718 struct Blob {
3719 char *a; /* Pointer to allocation */
3720 int n; /* Number of valid bytes of data in a[] */
3721 int nAlloc; /* Allocated size of a[] (nAlloc>=n) */
3722 };
3723
3724 /*
3725 ** This structure is used to build up buffers containing segment b-tree
3726 ** nodes (blocks).
3727 */
3728 struct NodeWriter {
3729 sqlite3_int64 iBlock; /* Current block id */
3730 Blob key; /* Last key written to the current block */
3731 Blob block; /* Current block image */
3732 };
3733
3734 /*
3735 ** An object of this type contains the state required to create or append
3736 ** to an appendable b-tree segment.
3737 */
3738 struct IncrmergeWriter {
3739 i64 nLeafEst; /* Space allocated for leaf blocks */
3740 i64 nWork; /* Number of leaf pages flushed */
3741 sqlite3_int64 iAbsLevel; /* Absolute level of input segments */
3742 int iIdx; /* Index of *output* segment in iAbsLevel+1 */
3743 sqlite3_int64 iStart; /* Block number of first allocated block */
3744 sqlite3_int64 iEnd; /* Block number of last allocated block */
3745 sqlite3_int64 nLeafData; /* Bytes of leaf page data so far */
3746 u8 bNoLeafData; /* If true, store 0 for segment size */
3747 NodeWriter aNodeWriter[FTS_MAX_APPENDABLE_HEIGHT];
3748 };
3749
3750 /*
3751 ** An object of the following type is used to read data from a single
3752 ** FTS segment node. See the following functions:
3753 **
3754 ** nodeReaderInit()
3755 ** nodeReaderNext()
3756 ** nodeReaderRelease()
3757 */
3758 struct NodeReader {
3759 const char *aNode;
3760 int nNode;
3761 int iOff; /* Current offset within aNode[] */
3762
3763 /* Output variables. Containing the current node entry. */
3764 sqlite3_int64 iChild; /* Pointer to child node */
3765 Blob term; /* Current term */
3766 const char *aDoclist; /* Pointer to doclist */
3767 int nDoclist; /* Size of doclist in bytes */
3768 };
3769
3770 /*
3771 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
3772 ** Otherwise, if the allocation at pBlob->a is not already at least nMin
3773 ** bytes in size, extend (realloc) it to be so.
3774 **
3775 ** If an OOM error occurs, set *pRc to SQLITE_NOMEM and leave pBlob->a
3776 ** unmodified. Otherwise, if the allocation succeeds, update pBlob->nAlloc
3777 ** to reflect the new size of the pBlob->a[] buffer.
3778 */
3779 static void blobGrowBuffer(Blob *pBlob, int nMin, int *pRc){
3780 if( *pRc==SQLITE_OK && nMin>pBlob->nAlloc ){
3781 int nAlloc = nMin;
3782 char *a = (char *)sqlite3_realloc64(pBlob->a, nAlloc);
3783 if( a ){
3784 pBlob->nAlloc = nAlloc;
3785 pBlob->a = a;
3786 }else{
3787 *pRc = SQLITE_NOMEM;
3788 }
3789 }
3790 }
3791
3792 /*
3793 ** Attempt to advance the node-reader object passed as the first argument to
3794 ** the next entry on the node.
3795 **
3796 ** Return an error code if an error occurs (SQLITE_NOMEM is possible).
3797 ** Otherwise return SQLITE_OK. If there is no next entry on the node
3798 ** (e.g. because the current entry is the last) set NodeReader->aNode to
3799 ** NULL to indicate EOF. Otherwise, populate the NodeReader structure output
3800 ** variables for the new entry.
3801 */
3802 static int nodeReaderNext(NodeReader *p){
3803 int bFirst = (p->term.n==0); /* True for first term on the node */
3804 int nPrefix = 0; /* Bytes to copy from previous term */
3805 int nSuffix = 0; /* Bytes to append to the prefix */
3806 int rc = SQLITE_OK; /* Return code */
3807
3808 assert( p->aNode );
3809 if( p->iChild && bFirst==0 ) p->iChild++;
3810 if( p->iOff>=p->nNode ){
3811 /* EOF */
3812 p->aNode = 0;
3813 }else{
3814 if( bFirst==0 ){
3815 p->iOff += fts3GetVarint32(&p->aNode[p->iOff], &nPrefix);
3816 }
3817 p->iOff += fts3GetVarint32(&p->aNode[p->iOff], &nSuffix);
3818
3819 if( nPrefix>p->term.n || nSuffix>p->nNode-p->iOff || nSuffix==0 ){
3820 return FTS_CORRUPT_VTAB;
3821 }
3822 blobGrowBuffer(&p->term, nPrefix+nSuffix, &rc);
3823 if( rc==SQLITE_OK && ALWAYS(p->term.a!=0) ){
3824 memcpy(&p->term.a[nPrefix], &p->aNode[p->iOff], nSuffix);
3825 p->term.n = nPrefix+nSuffix;
3826 p->iOff += nSuffix;
3827 if( p->iChild==0 ){
3828 p->iOff += fts3GetVarint32(&p->aNode[p->iOff], &p->nDoclist);
3829 if( (p->nNode-p->iOff)<p->nDoclist ){
3830 return FTS_CORRUPT_VTAB;
3831 }
3832 p->aDoclist = &p->aNode[p->iOff];
3833 p->iOff += p->nDoclist;
3834 }
3835 }
3836 }
3837
3838 assert_fts3_nc( p->iOff<=p->nNode );
3839 return rc;
3840 }
3841
3842 /*
3843 ** Release all dynamic resources held by node-reader object *p.
3844 */
3845 static void nodeReaderRelease(NodeReader *p){
3846 sqlite3_free(p->term.a);
3847 }
3848
3849 /*
3850 ** Initialize a node-reader object to read the node in buffer aNode/nNode.
3851 **
3852 ** If successful, SQLITE_OK is returned and the NodeReader object set to
3853 ** point to the first entry on the node (if any). Otherwise, an SQLite
3854 ** error code is returned.
3855 */
3856 static int nodeReaderInit(NodeReader *p, const char *aNode, int nNode){
3857 memset(p, 0, sizeof(NodeReader));
3858 p->aNode = aNode;
3859 p->nNode = nNode;
3860
3861 /* Figure out if this is a leaf or an internal node. */
3862 if( aNode && aNode[0] ){
3863 /* An internal node. */
3864 p->iOff = 1 + sqlite3Fts3GetVarint(&p->aNode[1], &p->iChild);
3865 }else{
3866 p->iOff = 1;
3867 }
3868
3869 return aNode ? nodeReaderNext(p) : SQLITE_OK;
3870 }
3871
3872 /*
3873 ** This function is called while writing an FTS segment each time a leaf o
3874 ** node is finished and written to disk. The key (zTerm/nTerm) is guaranteed
3875 ** to be greater than the largest key on the node just written, but smaller
3876 ** than or equal to the first key that will be written to the next leaf
3877 ** node.
3878 **
3879 ** The block id of the leaf node just written to disk may be found in
3880 ** (pWriter->aNodeWriter[0].iBlock) when this function is called.
3881 */
3882 static int fts3IncrmergePush(
3883 Fts3Table *p, /* Fts3 table handle */
3884 IncrmergeWriter *pWriter, /* Writer object */
3885 const char *zTerm, /* Term to write to internal node */
3886 int nTerm /* Bytes at zTerm */
3887 ){
3888 sqlite3_int64 iPtr = pWriter->aNodeWriter[0].iBlock;
3889 int iLayer;
3890
3891 assert( nTerm>0 );
3892 for(iLayer=1; ALWAYS(iLayer<FTS_MAX_APPENDABLE_HEIGHT); iLayer++){
3893 sqlite3_int64 iNextPtr = 0;
3894 NodeWriter *pNode = &pWriter->aNodeWriter[iLayer];
3895 int rc = SQLITE_OK;
3896 int nPrefix;
3897 int nSuffix;
3898 int nSpace;
3899
3900 /* Figure out how much space the key will consume if it is written to
3901 ** the current node of layer iLayer. Due to the prefix compression,
3902 ** the space required changes depending on which node the key is to
3903 ** be added to. */
3904 nPrefix = fts3PrefixCompress(pNode->key.a, pNode->key.n, zTerm, nTerm);
3905 nSuffix = nTerm - nPrefix;
3906 if(nSuffix<=0 ) return FTS_CORRUPT_VTAB;
3907 nSpace = sqlite3Fts3VarintLen(nPrefix);
3908 nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;
3909
3910 if( pNode->key.n==0 || (pNode->block.n + nSpace)<=p->nNodeSize ){
3911 /* If the current node of layer iLayer contains zero keys, or if adding
3912 ** the key to it will not cause it to grow to larger than nNodeSize
3913 ** bytes in size, write the key here. */
3914
3915 Blob *pBlk = &pNode->block;
3916 if( pBlk->n==0 ){
3917 blobGrowBuffer(pBlk, p->nNodeSize, &rc);
3918 if( rc==SQLITE_OK ){
3919 pBlk->a[0] = (char)iLayer;
3920 pBlk->n = 1 + sqlite3Fts3PutVarint(&pBlk->a[1], iPtr);
3921 }
3922 }
3923 blobGrowBuffer(pBlk, pBlk->n + nSpace, &rc);
3924 blobGrowBuffer(&pNode->key, nTerm, &rc);
3925
3926 if( rc==SQLITE_OK ){
3927 if( pNode->key.n ){
3928 pBlk->n += sqlite3Fts3PutVarint(&pBlk->a[pBlk->n], nPrefix);
3929 }
3930 pBlk->n += sqlite3Fts3PutVarint(&pBlk->a[pBlk->n], nSuffix);
3931 assert( nPrefix+nSuffix<=nTerm );
3932 assert( nPrefix>=0 );
3933 memcpy(&pBlk->a[pBlk->n], &zTerm[nPrefix], nSuffix);
3934 pBlk->n += nSuffix;
3935
3936 memcpy(pNode->key.a, zTerm, nTerm);
3937 pNode->key.n = nTerm;
3938 }
3939 }else{
3940 /* Otherwise, flush the current node of layer iLayer to disk.
3941 ** Then allocate a new, empty sibling node. The key will be written
3942 ** into the parent of this node. */
3943 rc = fts3WriteSegment(p, pNode->iBlock, pNode->block.a, pNode->block.n);
3944
3945 assert( pNode->block.nAlloc>=p->nNodeSize );
3946 pNode->block.a[0] = (char)iLayer;
3947 pNode->block.n = 1 + sqlite3Fts3PutVarint(&pNode->block.a[1], iPtr+1);
3948
3949 iNextPtr = pNode->iBlock;
3950 pNode->iBlock++;
3951 pNode->key.n = 0;
3952 }
3953
3954 if( rc!=SQLITE_OK || iNextPtr==0 ) return rc;
3955 iPtr = iNextPtr;
3956 }
3957
3958 assert( 0 );
3959 return 0;
3960 }
3961
3962 /*
3963 ** Append a term and (optionally) doclist to the FTS segment node currently
3964 ** stored in blob *pNode. The node need not contain any terms, but the
3965 ** header must be written before this function is called.
3966 **
3967 ** A node header is a single 0x00 byte for a leaf node, or a height varint
3968 ** followed by the left-hand-child varint for an internal node.
3969 **
3970 ** The term to be appended is passed via arguments zTerm/nTerm. For a
3971 ** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal
3972 ** node, both aDoclist and nDoclist must be passed 0.
3973 **
3974 ** If the size of the value in blob pPrev is zero, then this is the first
3975 ** term written to the node. Otherwise, pPrev contains a copy of the
3976 ** previous term. Before this function returns, it is updated to contain a
3977 ** copy of zTerm/nTerm.
3978 **
3979 ** It is assumed that the buffer associated with pNode is already large
3980 ** enough to accommodate the new entry. The buffer associated with pPrev
3981 ** is extended by this function if required.
3982 **
3983 ** If an error (i.e. OOM condition) occurs, an SQLite error code is
3984 ** returned. Otherwise, SQLITE_OK.
3985 */
3986 static int fts3AppendToNode(
3987 Blob *pNode, /* Current node image to append to */
3988 Blob *pPrev, /* Buffer containing previous term written */
3989 const char *zTerm, /* New term to write */
3990 int nTerm, /* Size of zTerm in bytes */
3991 const char *aDoclist, /* Doclist (or NULL) to write */
3992 int nDoclist /* Size of aDoclist in bytes */
3993 ){
3994 int rc = SQLITE_OK; /* Return code */
3995 int bFirst = (pPrev->n==0); /* True if this is the first term written */
3996 int nPrefix; /* Size of term prefix in bytes */
3997 int nSuffix; /* Size of term suffix in bytes */
3998
3999 /* Node must have already been started. There must be a doclist for a
4000 ** leaf node, and there must not be a doclist for an internal node. */
4001 assert( pNode->n>0 );
4002 assert_fts3_nc( (pNode->a[0]=='\0')==(aDoclist!=0) );
4003
4004 blobGrowBuffer(pPrev, nTerm, &rc);
4005 if( rc!=SQLITE_OK ) return rc;
4006 assert( pPrev!=0 );
4007 assert( pPrev->a!=0 );
4008
4009 nPrefix = fts3PrefixCompress(pPrev->a, pPrev->n, zTerm, nTerm);
4010 nSuffix = nTerm - nPrefix;
4011 if( nSuffix<=0 ) return FTS_CORRUPT_VTAB;
4012 memcpy(pPrev->a, zTerm, nTerm);
4013 pPrev->n = nTerm;
4014
4015 if( bFirst==0 ){
4016 pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nPrefix);
4017 }
4018 pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nSuffix);
4019 memcpy(&pNode->a[pNode->n], &zTerm[nPrefix], nSuffix);
4020 pNode->n += nSuffix;
4021
4022 if( aDoclist ){
4023 pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nDoclist);
4024 memcpy(&pNode->a[pNode->n], aDoclist, nDoclist);
4025 pNode->n += nDoclist;
4026 }
4027
4028 assert( pNode->n<=pNode->nAlloc );
4029
4030 return SQLITE_OK;
4031 }
4032
4033 /*
4034 ** Append the current term and doclist pointed to by cursor pCsr to the
4035 ** appendable b-tree segment opened for writing by pWriter.
4036 **
4037 ** Return SQLITE_OK if successful, or an SQLite error code otherwise.
4038 */
4039 static int fts3IncrmergeAppend(
4040 Fts3Table *p, /* Fts3 table handle */
4041 IncrmergeWriter *pWriter, /* Writer object */
4042 Fts3MultiSegReader *pCsr /* Cursor containing term and doclist */
4043 ){
4044 const char *zTerm = pCsr->zTerm;
4045 int nTerm = pCsr->nTerm;
4046 const char *aDoclist = pCsr->aDoclist;
4047 int nDoclist = pCsr->nDoclist;
4048 int rc = SQLITE_OK; /* Return code */
4049 int nSpace; /* Total space in bytes required on leaf */
4050 int nPrefix; /* Size of prefix shared with previous term */
4051 int nSuffix; /* Size of suffix (nTerm - nPrefix) */
4052 NodeWriter *pLeaf; /* Object used to write leaf nodes */
4053
4054 pLeaf = &pWriter->aNodeWriter[0];
4055 nPrefix = fts3PrefixCompress(pLeaf->key.a, pLeaf->key.n, zTerm, nTerm);
4056 nSuffix = nTerm - nPrefix;
4057 if(nSuffix<=0 ) return FTS_CORRUPT_VTAB;
4058
4059 nSpace = sqlite3Fts3VarintLen(nPrefix);
4060 nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;
4061 nSpace += sqlite3Fts3VarintLen(nDoclist) + nDoclist;
4062
4063 /* If the current block is not empty, and if adding this term/doclist
4064 ** to the current block would make it larger than Fts3Table.nNodeSize bytes,
4065 ** and if there is still room for another leaf page, write this block out to
4066 ** the database. */
4067 if( pLeaf->block.n>0
4068 && (pLeaf->block.n + nSpace)>p->nNodeSize
4069 && pLeaf->iBlock < (pWriter->iStart + pWriter->nLeafEst)
4070 ){
4071 rc = fts3WriteSegment(p, pLeaf->iBlock, pLeaf->block.a, pLeaf->block.n);
4072 pWriter->nWork++;
4073
4074 /* Add the current term to the parent node. The term added to the
4075 ** parent must:
4076 **
4077 ** a) be greater than the largest term on the leaf node just written
4078 ** to the database (still available in pLeaf->key), and
4079 **
4080 ** b) be less than or equal to the term about to be added to the new
4081 ** leaf node (zTerm/nTerm).
4082 **
4083 ** In other words, it must be the prefix of zTerm 1 byte longer than
4084 ** the common prefix (if any) of zTerm and pWriter->zTerm.
4085 */
4086 if( rc==SQLITE_OK ){
4087 rc = fts3IncrmergePush(p, pWriter, zTerm, nPrefix+1);
4088 }
4089
4090 /* Advance to the next output block */
4091 pLeaf->iBlock++;
4092 pLeaf->key.n = 0;
4093 pLeaf->block.n = 0;
4094
4095 nSuffix = nTerm;
4096 nSpace = 1;
4097 nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;
4098 nSpace += sqlite3Fts3VarintLen(nDoclist) + nDoclist;
4099 }
4100
4101 pWriter->nLeafData += nSpace;
4102 blobGrowBuffer(&pLeaf->block, pLeaf->block.n + nSpace, &rc);
4103 if( rc==SQLITE_OK ){
4104 if( pLeaf->block.n==0 ){
4105 pLeaf->block.n = 1;
4106 pLeaf->block.a[0] = '\0';
4107 }
4108 rc = fts3AppendToNode(
4109 &pLeaf->block, &pLeaf->key, zTerm, nTerm, aDoclist, nDoclist
4110 );
4111 }
4112
4113 return rc;
4114 }
4115
4116 /*
4117 ** This function is called to release all dynamic resources held by the
4118 ** merge-writer object pWriter, and if no error has occurred, to flush
4119 ** all outstanding node buffers held by pWriter to disk.
4120 **
4121 ** If *pRc is not SQLITE_OK when this function is called, then no attempt
4122 ** is made to write any data to disk. Instead, this function serves only
4123 ** to release outstanding resources.
4124 **
4125 ** Otherwise, if *pRc is initially SQLITE_OK and an error occurs while
4126 ** flushing buffers to disk, *pRc is set to an SQLite error code before
4127 ** returning.
4128 */
4129 static void fts3IncrmergeRelease(
4130 Fts3Table *p, /* FTS3 table handle */
4131 IncrmergeWriter *pWriter, /* Merge-writer object */
4132 int *pRc /* IN/OUT: Error code */
4133 ){
4134 int i; /* Used to iterate through non-root layers */
4135 int iRoot; /* Index of root in pWriter->aNodeWriter */
4136 NodeWriter *pRoot; /* NodeWriter for root node */
4137 int rc = *pRc; /* Error code */
4138
4139 /* Set iRoot to the index in pWriter->aNodeWriter[] of the output segment
4140 ** root node. If the segment fits entirely on a single leaf node, iRoot
4141 ** will be set to 0. If the root node is the parent of the leaves, iRoot
4142 ** will be 1. And so on. */
4143 for(iRoot=FTS_MAX_APPENDABLE_HEIGHT-1; iRoot>=0; iRoot--){
4144 NodeWriter *pNode = &pWriter->aNodeWriter[iRoot];
4145 if( pNode->block.n>0 ) break;
4146 assert( *pRc || pNode->block.nAlloc==0 );
4147 assert( *pRc || pNode->key.nAlloc==0 );
4148 sqlite3_free(pNode->block.a);
4149 sqlite3_free(pNode->key.a);
4150 }
4151
4152 /* Empty output segment. This is a no-op. */
4153 if( iRoot<0 ) return;
4154
4155 /* The entire output segment fits on a single node. Normally, this means
4156 ** the node would be stored as a blob in the "root" column of the %_segdir
4157 ** table. However, this is not permitted in this case. The problem is that
4158 ** space has already been reserved in the %_segments table, and so the
4159 ** start_block and end_block fields of the %_segdir table must be populated.
4160 ** And, by design or by accident, released versions of FTS cannot handle
4161 ** segments that fit entirely on the root node with start_block!=0.
4162 **
4163 ** Instead, create a synthetic root node that contains nothing but a
4164 ** pointer to the single content node. So that the segment consists of a
4165 ** single leaf and a single interior (root) node.
4166 **
4167 ** Todo: Better might be to defer allocating space in the %_segments
4168 ** table until we are sure it is needed.
4169 */
4170 if( iRoot==0 ){
4171 Blob *pBlock = &pWriter->aNodeWriter[1].block;
4172 blobGrowBuffer(pBlock, 1 + FTS3_VARINT_MAX, &rc);
4173 if( rc==SQLITE_OK ){
4174 pBlock->a[0] = 0x01;
4175 pBlock->n = 1 + sqlite3Fts3PutVarint(
4176 &pBlock->a[1], pWriter->aNodeWriter[0].iBlock
4177 );
4178 }
4179 iRoot = 1;
4180 }
4181 pRoot = &pWriter->aNodeWriter[iRoot];
4182
4183 /* Flush all currently outstanding nodes to disk. */
4184 for(i=0; i<iRoot; i++){
4185 NodeWriter *pNode = &pWriter->aNodeWriter[i];
4186 if( pNode->block.n>0 && rc==SQLITE_OK ){
4187 rc = fts3WriteSegment(p, pNode->iBlock, pNode->block.a, pNode->block.n);
4188 }
4189 sqlite3_free(pNode->block.a);
4190 sqlite3_free(pNode->key.a);
4191 }
4192
4193 /* Write the %_segdir record. */
4194 if( rc==SQLITE_OK ){
4195 rc = fts3WriteSegdir(p,
4196 pWriter->iAbsLevel+1, /* level */
4197 pWriter->iIdx, /* idx */
4198 pWriter->iStart, /* start_block */
4199 pWriter->aNodeWriter[0].iBlock, /* leaves_end_block */
4200 pWriter->iEnd, /* end_block */
4201 (pWriter->bNoLeafData==0 ? pWriter->nLeafData : 0), /* end_block */
4202 pRoot->block.a, pRoot->block.n /* root */
4203 );
4204 }
4205 sqlite3_free(pRoot->block.a);
4206 sqlite3_free(pRoot->key.a);
4207
4208 *pRc = rc;
4209 }
4210
4211 /*
4212 ** Compare the term in buffer zLhs (size in bytes nLhs) with that in
4213 ** zRhs (size in bytes nRhs) using memcmp. If one term is a prefix of
4214 ** the other, it is considered to be smaller than the other.
4215 **
4216 ** Return -ve if zLhs is smaller than zRhs, 0 if it is equal, or +ve
4217 ** if it is greater.
4218 */
4219 static int fts3TermCmp(
4220 const char *zLhs, int nLhs, /* LHS of comparison */
4221 const char *zRhs, int nRhs /* RHS of comparison */
4222 ){
4223 int nCmp = MIN(nLhs, nRhs);
4224 int res;
4225
4226 if( nCmp && ALWAYS(zLhs) && ALWAYS(zRhs) ){
4227 res = memcmp(zLhs, zRhs, nCmp);
4228 }else{
4229 res = 0;
4230 }
4231 if( res==0 ) res = nLhs - nRhs;
4232
4233 return res;
4234 }
4235
4236
4237 /*
4238 ** Query to see if the entry in the %_segments table with blockid iEnd is
4239 ** NULL. If no error occurs and the entry is NULL, set *pbRes 1 before
4240 ** returning. Otherwise, set *pbRes to 0.
4241 **
4242 ** Or, if an error occurs while querying the database, return an SQLite
4243 ** error code. The final value of *pbRes is undefined in this case.
4244 **
4245 ** This is used to test if a segment is an "appendable" segment. If it
4246 ** is, then a NULL entry has been inserted into the %_segments table
4247 ** with blockid %_segdir.end_block.
4248 */
4249 static int fts3IsAppendable(Fts3Table *p, sqlite3_int64 iEnd, int *pbRes){
4250 int bRes = 0; /* Result to set *pbRes to */
4251 sqlite3_stmt *pCheck = 0; /* Statement to query database with */
4252 int rc; /* Return code */
4253
4254 rc = fts3SqlStmt(p, SQL_SEGMENT_IS_APPENDABLE, &pCheck, 0);
4255 if( rc==SQLITE_OK ){
4256 sqlite3_bind_int64(pCheck, 1, iEnd);
4257 if( SQLITE_ROW==sqlite3_step(pCheck) ) bRes = 1;
4258 rc = sqlite3_reset(pCheck);
4259 }
4260
4261 *pbRes = bRes;
4262 return rc;
4263 }
4264
4265 /*
4266 ** This function is called when initializing an incremental-merge operation.
4267 ** It checks if the existing segment with index value iIdx at absolute level
4268 ** (iAbsLevel+1) can be appended to by the incremental merge. If it can, the
4269 ** merge-writer object *pWriter is initialized to write to it.
4270 **
4271 ** An existing segment can be appended to by an incremental merge if:
4272 **
4273 ** * It was initially created as an appendable segment (with all required
4274 ** space pre-allocated), and
4275 **
4276 ** * The first key read from the input (arguments zKey and nKey) is
4277 ** greater than the largest key currently stored in the potential
4278 ** output segment.
4279 */
4280 static int fts3IncrmergeLoad(
4281 Fts3Table *p, /* Fts3 table handle */
4282 sqlite3_int64 iAbsLevel, /* Absolute level of input segments */
4283 int iIdx, /* Index of candidate output segment */
4284 const char *zKey, /* First key to write */
4285 int nKey, /* Number of bytes in nKey */
4286 IncrmergeWriter *pWriter /* Populate this object */
4287 ){
4288 int rc; /* Return code */
4289 sqlite3_stmt *pSelect = 0; /* SELECT to read %_segdir entry */
4290
4291 rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pSelect, 0);
4292 if( rc==SQLITE_OK ){
4293 sqlite3_int64 iStart = 0; /* Value of %_segdir.start_block */
4294 sqlite3_int64 iLeafEnd = 0; /* Value of %_segdir.leaves_end_block */
4295 sqlite3_int64 iEnd = 0; /* Value of %_segdir.end_block */
4296 const char *aRoot = 0; /* Pointer to %_segdir.root buffer */
4297 int nRoot = 0; /* Size of aRoot[] in bytes */
4298 int rc2; /* Return code from sqlite3_reset() */
4299 int bAppendable = 0; /* Set to true if segment is appendable */
4300
4301 /* Read the %_segdir entry for index iIdx absolute level (iAbsLevel+1) */
4302 sqlite3_bind_int64(pSelect, 1, iAbsLevel+1);
4303 sqlite3_bind_int(pSelect, 2, iIdx);
4304 if( sqlite3_step(pSelect)==SQLITE_ROW ){
4305 iStart = sqlite3_column_int64(pSelect, 1);
4306 iLeafEnd = sqlite3_column_int64(pSelect, 2);
4307 fts3ReadEndBlockField(pSelect, 3, &iEnd, &pWriter->nLeafData);
4308 if( pWriter->nLeafData<0 ){
4309 pWriter->nLeafData = pWriter->nLeafData * -1;
4310 }
4311 pWriter->bNoLeafData = (pWriter->nLeafData==0);
4312 nRoot = sqlite3_column_bytes(pSelect, 4);
4313 aRoot = sqlite3_column_blob(pSelect, 4);
4314 if( aRoot==0 ){
4315 sqlite3_reset(pSelect);
4316 return nRoot ? SQLITE_NOMEM : FTS_CORRUPT_VTAB;
4317 }
4318 }else{
4319 return sqlite3_reset(pSelect);
4320 }
4321
4322 /* Check for the zero-length marker in the %_segments table */
4323 rc = fts3IsAppendable(p, iEnd, &bAppendable);
4324
4325 /* Check that zKey/nKey is larger than the largest key the candidate */
4326 if( rc==SQLITE_OK && bAppendable ){
4327 char *aLeaf = 0;
4328 int nLeaf = 0;
4329
4330 rc = sqlite3Fts3ReadBlock(p, iLeafEnd, &aLeaf, &nLeaf, 0);
4331 if( rc==SQLITE_OK ){
4332 NodeReader reader;
4333 for(rc = nodeReaderInit(&reader, aLeaf, nLeaf);
4334 rc==SQLITE_OK && reader.aNode;
4335 rc = nodeReaderNext(&reader)
4336 ){
4337 assert( reader.aNode );
4338 }
4339 if( fts3TermCmp(zKey, nKey, reader.term.a, reader.term.n)<=0 ){
4340 bAppendable = 0;
4341 }
4342 nodeReaderRelease(&reader);
4343 }
4344 sqlite3_free(aLeaf);
4345 }
4346
4347 if( rc==SQLITE_OK && bAppendable ){
4348 /* It is possible to append to this segment. Set up the IncrmergeWriter
4349 ** object to do so. */
4350 int i;
4351 int nHeight = (int)aRoot[0];
4352 NodeWriter *pNode;
4353 if( nHeight<1 || nHeight>=FTS_MAX_APPENDABLE_HEIGHT ){
4354 sqlite3_reset(pSelect);
4355 return FTS_CORRUPT_VTAB;
4356 }
4357
4358 pWriter->nLeafEst = (int)((iEnd - iStart) + 1)/FTS_MAX_APPENDABLE_HEIGHT;
4359 pWriter->iStart = iStart;
4360 pWriter->iEnd = iEnd;
4361 pWriter->iAbsLevel = iAbsLevel;
4362 pWriter->iIdx = iIdx;
4363
4364 for(i=nHeight+1; i<FTS_MAX_APPENDABLE_HEIGHT; i++){
4365 pWriter->aNodeWriter[i].iBlock = pWriter->iStart + i*pWriter->nLeafEst;
4366 }
4367
4368 pNode = &pWriter->aNodeWriter[nHeight];
4369 pNode->iBlock = pWriter->iStart + pWriter->nLeafEst*nHeight;
4370 blobGrowBuffer(&pNode->block,
4371 MAX(nRoot, p->nNodeSize)+FTS3_NODE_PADDING, &rc
4372 );
4373 if( rc==SQLITE_OK ){
4374 memcpy(pNode->block.a, aRoot, nRoot);
4375 pNode->block.n = nRoot;
4376 memset(&pNode->block.a[nRoot], 0, FTS3_NODE_PADDING);
4377 }
4378
4379 for(i=nHeight; i>=0 && rc==SQLITE_OK; i--){
4380 NodeReader reader;
4381 memset(&reader, 0, sizeof(reader));
4382 pNode = &pWriter->aNodeWriter[i];
4383
4384 if( pNode->block.a){
4385 rc = nodeReaderInit(&reader, pNode->block.a, pNode->block.n);
4386 while( reader.aNode && rc==SQLITE_OK ) rc = nodeReaderNext(&reader);
4387 blobGrowBuffer(&pNode->key, reader.term.n, &rc);
4388 if( rc==SQLITE_OK ){
4389 assert_fts3_nc( reader.term.n>0 || reader.aNode==0 );
4390 if( reader.term.n>0 ){
4391 memcpy(pNode->key.a, reader.term.a, reader.term.n);
4392 }
4393 pNode->key.n = reader.term.n;
4394 if( i>0 ){
4395 char *aBlock = 0;
4396 int nBlock = 0;
4397 pNode = &pWriter->aNodeWriter[i-1];
4398 pNode->iBlock = reader.iChild;
4399 rc = sqlite3Fts3ReadBlock(p, reader.iChild, &aBlock, &nBlock,0);
4400 blobGrowBuffer(&pNode->block,
4401 MAX(nBlock, p->nNodeSize)+FTS3_NODE_PADDING, &rc
4402 );
4403 if( rc==SQLITE_OK ){
4404 memcpy(pNode->block.a, aBlock, nBlock);
4405 pNode->block.n = nBlock;
4406 memset(&pNode->block.a[nBlock], 0, FTS3_NODE_PADDING);
4407 }
4408 sqlite3_free(aBlock);
4409 }
4410 }
4411 }
4412 nodeReaderRelease(&reader);
4413 }
4414 }
4415
4416 rc2 = sqlite3_reset(pSelect);
4417 if( rc==SQLITE_OK ) rc = rc2;
4418 }
4419
4420 return rc;
4421 }
4422
4423 /*
4424 ** Determine the largest segment index value that exists within absolute
4425 ** level iAbsLevel+1. If no error occurs, set *piIdx to this value plus
4426 ** one before returning SQLITE_OK. Or, if there are no segments at all
4427 ** within level iAbsLevel, set *piIdx to zero.
4428 **
4429 ** If an error occurs, return an SQLite error code. The final value of
4430 ** *piIdx is undefined in this case.
4431 */
4432 static int fts3IncrmergeOutputIdx(
4433 Fts3Table *p, /* FTS Table handle */
4434 sqlite3_int64 iAbsLevel, /* Absolute index of input segments */
4435 int *piIdx /* OUT: Next free index at iAbsLevel+1 */
4436 ){
4437 int rc;
4438 sqlite3_stmt *pOutputIdx = 0; /* SQL used to find output index */
4439
4440 rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pOutputIdx, 0);
4441 if( rc==SQLITE_OK ){
4442 sqlite3_bind_int64(pOutputIdx, 1, iAbsLevel+1);
4443 sqlite3_step(pOutputIdx);
4444 *piIdx = sqlite3_column_int(pOutputIdx, 0);
4445 rc = sqlite3_reset(pOutputIdx);
4446 }
4447
4448 return rc;
4449 }
4450
4451 /*
4452 ** Allocate an appendable output segment on absolute level iAbsLevel+1
4453 ** with idx value iIdx.
4454 **
4455 ** In the %_segdir table, a segment is defined by the values in three
4456 ** columns:
4457 **
4458 ** start_block
4459 ** leaves_end_block
4460 ** end_block
4461 **
4462 ** When an appendable segment is allocated, it is estimated that the
4463 ** maximum number of leaf blocks that may be required is the sum of the
4464 ** number of leaf blocks consumed by the input segments, plus the number
4465 ** of input segments, multiplied by two. This value is stored in stack
4466 ** variable nLeafEst.
4467 **
4468 ** A total of 16*nLeafEst blocks are allocated when an appendable segment
4469 ** is created ((1 + end_block - start_block)==16*nLeafEst). The contiguous
4470 ** array of leaf nodes starts at the first block allocated. The array
4471 ** of interior nodes that are parents of the leaf nodes start at block
4472 ** (start_block + (1 + end_block - start_block) / 16). And so on.
4473 **
4474 ** In the actual code below, the value "16" is replaced with the
4475 ** pre-processor macro FTS_MAX_APPENDABLE_HEIGHT.
4476 */
4477 static int fts3IncrmergeWriter(
4478 Fts3Table *p, /* Fts3 table handle */
4479 sqlite3_int64 iAbsLevel, /* Absolute level of input segments */
4480 int iIdx, /* Index of new output segment */
4481 Fts3MultiSegReader *pCsr, /* Cursor that data will be read from */
4482 IncrmergeWriter *pWriter /* Populate this object */
4483 ){
4484 int rc; /* Return Code */
4485 int i; /* Iterator variable */
4486 i64 nLeafEst = 0; /* Blocks allocated for leaf nodes */
4487 sqlite3_stmt *pLeafEst = 0; /* SQL used to determine nLeafEst */
4488 sqlite3_stmt *pFirstBlock = 0; /* SQL used to determine first block */
4489
4490 /* Calculate nLeafEst. */
4491 rc = fts3SqlStmt(p, SQL_MAX_LEAF_NODE_ESTIMATE, &pLeafEst, 0);
4492 if( rc==SQLITE_OK ){
4493 sqlite3_bind_int64(pLeafEst, 1, iAbsLevel);
4494 sqlite3_bind_int64(pLeafEst, 2, pCsr->nSegment);
4495 if( SQLITE_ROW==sqlite3_step(pLeafEst) ){
4496 nLeafEst = sqlite3_column_int64(pLeafEst, 0);
4497 }
4498 rc = sqlite3_reset(pLeafEst);
4499 }
4500 if( rc!=SQLITE_OK ) return rc;
4501
4502 /* Calculate the first block to use in the output segment */
4503 rc = fts3SqlStmt(p, SQL_NEXT_SEGMENTS_ID, &pFirstBlock, 0);
4504 if( rc==SQLITE_OK ){
4505 if( SQLITE_ROW==sqlite3_step(pFirstBlock) ){
4506 pWriter->iStart = sqlite3_column_int64(pFirstBlock, 0);
4507 pWriter->iEnd = pWriter->iStart - 1;
4508 pWriter->iEnd += nLeafEst * FTS_MAX_APPENDABLE_HEIGHT;
4509 }
4510 rc = sqlite3_reset(pFirstBlock);
4511 }
4512 if( rc!=SQLITE_OK ) return rc;
4513
4514 /* Insert the marker in the %_segments table to make sure nobody tries
4515 ** to steal the space just allocated. This is also used to identify
4516 ** appendable segments. */
4517 rc = fts3WriteSegment(p, pWriter->iEnd, 0, 0);
4518 if( rc!=SQLITE_OK ) return rc;
4519
4520 pWriter->iAbsLevel = iAbsLevel;
4521 pWriter->nLeafEst = nLeafEst;
4522 pWriter->iIdx = iIdx;
4523
4524 /* Set up the array of NodeWriter objects */
4525 for(i=0; i<FTS_MAX_APPENDABLE_HEIGHT; i++){
4526 pWriter->aNodeWriter[i].iBlock = pWriter->iStart + i*pWriter->nLeafEst;
4527 }
4528 return SQLITE_OK;
4529 }
4530
4531 /*
4532 ** Remove an entry from the %_segdir table. This involves running the
4533 ** following two statements:
4534 **
4535 ** DELETE FROM %_segdir WHERE level = :iAbsLevel AND idx = :iIdx
4536 ** UPDATE %_segdir SET idx = idx - 1 WHERE level = :iAbsLevel AND idx > :iIdx
4537 **
4538 ** The DELETE statement removes the specific %_segdir level. The UPDATE
4539 ** statement ensures that the remaining segments have contiguously allocated
4540 ** idx values.
4541 */
4542 static int fts3RemoveSegdirEntry(
4543 Fts3Table *p, /* FTS3 table handle */
4544 sqlite3_int64 iAbsLevel, /* Absolute level to delete from */
4545 int iIdx /* Index of %_segdir entry to delete */
4546 ){
4547 int rc; /* Return code */
4548 sqlite3_stmt *pDelete = 0; /* DELETE statement */
4549
4550 rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_ENTRY, &pDelete, 0);
4551 if( rc==SQLITE_OK ){
4552 sqlite3_bind_int64(pDelete, 1, iAbsLevel);
4553 sqlite3_bind_int(pDelete, 2, iIdx);
4554 sqlite3_step(pDelete);
4555 rc = sqlite3_reset(pDelete);
4556 }
4557
4558 return rc;
4559 }
4560
4561 /*
4562 ** One or more segments have just been removed from absolute level iAbsLevel.
4563 ** Update the 'idx' values of the remaining segments in the level so that
4564 ** the idx values are a contiguous sequence starting from 0.
4565 */
4566 static int fts3RepackSegdirLevel(
4567 Fts3Table *p, /* FTS3 table handle */
4568 sqlite3_int64 iAbsLevel /* Absolute level to repack */
4569 ){
4570 int rc; /* Return code */
4571 int *aIdx = 0; /* Array of remaining idx values */
4572 int nIdx = 0; /* Valid entries in aIdx[] */
4573 int nAlloc = 0; /* Allocated size of aIdx[] */
4574 int i; /* Iterator variable */
4575 sqlite3_stmt *pSelect = 0; /* Select statement to read idx values */
4576 sqlite3_stmt *pUpdate = 0; /* Update statement to modify idx values */
4577
4578 rc = fts3SqlStmt(p, SQL_SELECT_INDEXES, &pSelect, 0);
4579 if( rc==SQLITE_OK ){
4580 int rc2;
4581 sqlite3_bind_int64(pSelect, 1, iAbsLevel);
4582 while( SQLITE_ROW==sqlite3_step(pSelect) ){
4583 if( nIdx>=nAlloc ){
4584 int *aNew;
4585 nAlloc += 16;
4586 aNew = sqlite3_realloc64(aIdx, nAlloc*sizeof(int));
4587 if( !aNew ){
4588 rc = SQLITE_NOMEM;
4589 break;
4590 }
4591 aIdx = aNew;
4592 }
4593 aIdx[nIdx++] = sqlite3_column_int(pSelect, 0);
4594 }
4595 rc2 = sqlite3_reset(pSelect);
4596 if( rc==SQLITE_OK ) rc = rc2;
4597 }
4598
4599 if( rc==SQLITE_OK ){
4600 rc = fts3SqlStmt(p, SQL_SHIFT_SEGDIR_ENTRY, &pUpdate, 0);
4601 }
4602 if( rc==SQLITE_OK ){
4603 sqlite3_bind_int64(pUpdate, 2, iAbsLevel);
4604 }
4605
4606 assert( p->bIgnoreSavepoint==0 );
4607 p->bIgnoreSavepoint = 1;
4608 for(i=0; rc==SQLITE_OK && i<nIdx; i++){
4609 if( aIdx[i]!=i ){
4610 sqlite3_bind_int(pUpdate, 3, aIdx[i]);
4611 sqlite3_bind_int(pUpdate, 1, i);
4612 sqlite3_step(pUpdate);
4613 rc = sqlite3_reset(pUpdate);
4614 }
4615 }
4616 p->bIgnoreSavepoint = 0;
4617
4618 sqlite3_free(aIdx);
4619 return rc;
4620 }
4621
4622 static void fts3StartNode(Blob *pNode, int iHeight, sqlite3_int64 iChild){
4623 pNode->a[0] = (char)iHeight;
4624 if( iChild ){
4625 assert( pNode->nAlloc>=1+sqlite3Fts3VarintLen(iChild) );
4626 pNode->n = 1 + sqlite3Fts3PutVarint(&pNode->a[1], iChild);
4627 }else{
4628 assert( pNode->nAlloc>=1 );
4629 pNode->n = 1;
4630 }
4631 }
4632
4633 /*
4634 ** The first two arguments are a pointer to and the size of a segment b-tree
4635 ** node. The node may be a leaf or an internal node.
4636 **
4637 ** This function creates a new node image in blob object *pNew by copying
4638 ** all terms that are greater than or equal to zTerm/nTerm (for leaf nodes)
4639 ** or greater than zTerm/nTerm (for internal nodes) from aNode/nNode.
4640 */
4641 static int fts3TruncateNode(
4642 const char *aNode, /* Current node image */
4643 int nNode, /* Size of aNode in bytes */
4644 Blob *pNew, /* OUT: Write new node image here */
4645 const char *zTerm, /* Omit all terms smaller than this */
4646 int nTerm, /* Size of zTerm in bytes */
4647 sqlite3_int64 *piBlock /* OUT: Block number in next layer down */
4648 ){
4649 NodeReader reader; /* Reader object */
4650 Blob prev = {0, 0, 0}; /* Previous term written to new node */
4651 int rc = SQLITE_OK; /* Return code */
4652 int bLeaf; /* True for a leaf node */
4653
4654 if( nNode<1 ) return FTS_CORRUPT_VTAB;
4655 bLeaf = aNode[0]=='\0';
4656
4657 /* Allocate required output space */
4658 blobGrowBuffer(pNew, nNode, &rc);
4659 if( rc!=SQLITE_OK ) return rc;
4660 pNew->n = 0;
4661
4662 /* Populate new node buffer */
4663 for(rc = nodeReaderInit(&reader, aNode, nNode);
4664 rc==SQLITE_OK && reader.aNode;
4665 rc = nodeReaderNext(&reader)
4666 ){
4667 if( pNew->n==0 ){
4668 int res = fts3TermCmp(reader.term.a, reader.term.n, zTerm, nTerm);
4669 if( res<0 || (bLeaf==0 && res==0) ) continue;
4670 fts3StartNode(pNew, (int)aNode[0], reader.iChild);
4671 *piBlock = reader.iChild;
4672 }
4673 rc = fts3AppendToNode(
4674 pNew, &prev, reader.term.a, reader.term.n,
4675 reader.aDoclist, reader.nDoclist
4676 );
4677 if( rc!=SQLITE_OK ) break;
4678 }
4679 if( pNew->n==0 ){
4680 fts3StartNode(pNew, (int)aNode[0], reader.iChild);
4681 *piBlock = reader.iChild;
4682 }
4683 assert( pNew->n<=pNew->nAlloc );
4684
4685 nodeReaderRelease(&reader);
4686 sqlite3_free(prev.a);
4687 return rc;
4688 }
4689
4690 /*
4691 ** Remove all terms smaller than zTerm/nTerm from segment iIdx in absolute
4692 ** level iAbsLevel. This may involve deleting entries from the %_segments
4693 ** table, and modifying existing entries in both the %_segments and %_segdir
4694 ** tables.
4695 **
4696 ** SQLITE_OK is returned if the segment is updated successfully. Or an
4697 ** SQLite error code otherwise.
4698 */
4699 static int fts3TruncateSegment(
4700 Fts3Table *p, /* FTS3 table handle */
4701 sqlite3_int64 iAbsLevel, /* Absolute level of segment to modify */
4702 int iIdx, /* Index within level of segment to modify */
4703 const char *zTerm, /* Remove terms smaller than this */
4704 int nTerm /* Number of bytes in buffer zTerm */
4705 ){
4706 int rc = SQLITE_OK; /* Return code */
4707 Blob root = {0,0,0}; /* New root page image */
4708 Blob block = {0,0,0}; /* Buffer used for any other block */
4709 sqlite3_int64 iBlock = 0; /* Block id */
4710 sqlite3_int64 iNewStart = 0; /* New value for iStartBlock */
4711 sqlite3_int64 iOldStart = 0; /* Old value for iStartBlock */
4712 sqlite3_stmt *pFetch = 0; /* Statement used to fetch segdir */
4713
4714 rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pFetch, 0);
4715 if( rc==SQLITE_OK ){
4716 int rc2; /* sqlite3_reset() return code */
4717 sqlite3_bind_int64(pFetch, 1, iAbsLevel);
4718 sqlite3_bind_int(pFetch, 2, iIdx);
4719 if( SQLITE_ROW==sqlite3_step(pFetch) ){
4720 const char *aRoot = sqlite3_column_blob(pFetch, 4);
4721 int nRoot = sqlite3_column_bytes(pFetch, 4);
4722 iOldStart = sqlite3_column_int64(pFetch, 1);
4723 rc = fts3TruncateNode(aRoot, nRoot, &root, zTerm, nTerm, &iBlock);
4724 }
4725 rc2 = sqlite3_reset(pFetch);
4726 if( rc==SQLITE_OK ) rc = rc2;
4727 }
4728
4729 while( rc==SQLITE_OK && iBlock ){
4730 char *aBlock = 0;
4731 int nBlock = 0;
4732 iNewStart = iBlock;
4733
4734 rc = sqlite3Fts3ReadBlock(p, iBlock, &aBlock, &nBlock, 0);
4735 if( rc==SQLITE_OK ){
4736 rc = fts3TruncateNode(aBlock, nBlock, &block, zTerm, nTerm, &iBlock);
4737 }
4738 if( rc==SQLITE_OK ){
4739 rc = fts3WriteSegment(p, iNewStart, block.a, block.n);
4740 }
4741 sqlite3_free(aBlock);
4742 }
4743
4744 /* Variable iNewStart now contains the first valid leaf node. */
4745 if( rc==SQLITE_OK && iNewStart ){
4746 sqlite3_stmt *pDel = 0;
4747 rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDel, 0);
4748 if( rc==SQLITE_OK ){
4749 sqlite3_bind_int64(pDel, 1, iOldStart);
4750 sqlite3_bind_int64(pDel, 2, iNewStart-1);
4751 sqlite3_step(pDel);
4752 rc = sqlite3_reset(pDel);
4753 }
4754 }
4755
4756 if( rc==SQLITE_OK ){
4757 sqlite3_stmt *pChomp = 0;
4758 rc = fts3SqlStmt(p, SQL_CHOMP_SEGDIR, &pChomp, 0);
4759 if( rc==SQLITE_OK ){
4760 sqlite3_bind_int64(pChomp, 1, iNewStart);
4761 sqlite3_bind_blob(pChomp, 2, root.a, root.n, SQLITE_STATIC);
4762 sqlite3_bind_int64(pChomp, 3, iAbsLevel);
4763 sqlite3_bind_int(pChomp, 4, iIdx);
4764 sqlite3_step(pChomp);
4765 rc = sqlite3_reset(pChomp);
4766 sqlite3_bind_null(pChomp, 2);
4767 }
4768 }
4769
4770 sqlite3_free(root.a);
4771 sqlite3_free(block.a);
4772 return rc;
4773 }
4774
4775 /*
4776 ** This function is called after an incrmental-merge operation has run to
4777 ** merge (or partially merge) two or more segments from absolute level
4778 ** iAbsLevel.
4779 **
4780 ** Each input segment is either removed from the db completely (if all of
4781 ** its data was copied to the output segment by the incrmerge operation)
4782 ** or modified in place so that it no longer contains those entries that
4783 ** have been duplicated in the output segment.
4784 */
4785 static int fts3IncrmergeChomp(
4786 Fts3Table *p, /* FTS table handle */
4787 sqlite3_int64 iAbsLevel, /* Absolute level containing segments */
4788 Fts3MultiSegReader *pCsr, /* Chomp all segments opened by this cursor */
4789 int *pnRem /* Number of segments not deleted */
4790 ){
4791 int i;
4792 int nRem = 0;
4793 int rc = SQLITE_OK;
4794
4795 for(i=pCsr->nSegment-1; i>=0 && rc==SQLITE_OK; i--){
4796 Fts3SegReader *pSeg = 0;
4797 int j;
4798
4799 /* Find the Fts3SegReader object with Fts3SegReader.iIdx==i. It is hiding
4800 ** somewhere in the pCsr->apSegment[] array. */
4801 for(j=0; ALWAYS(j<pCsr->nSegment); j++){
4802 pSeg = pCsr->apSegment[j];
4803 if( pSeg->iIdx==i ) break;
4804 }
4805 assert( j<pCsr->nSegment && pSeg->iIdx==i );
4806
4807 if( pSeg->aNode==0 ){
4808 /* Seg-reader is at EOF. Remove the entire input segment. */
4809 rc = fts3DeleteSegment(p, pSeg);
4810 if( rc==SQLITE_OK ){
4811 rc = fts3RemoveSegdirEntry(p, iAbsLevel, pSeg->iIdx);
4812 }
4813 *pnRem = 0;
4814 }else{
4815 /* The incremental merge did not copy all the data from this
4816 ** segment to the upper level. The segment is modified in place
4817 ** so that it contains no keys smaller than zTerm/nTerm. */
4818 const char *zTerm = pSeg->zTerm;
4819 int nTerm = pSeg->nTerm;
4820 rc = fts3TruncateSegment(p, iAbsLevel, pSeg->iIdx, zTerm, nTerm);
4821 nRem++;
4822 }
4823 }
4824
4825 if( rc==SQLITE_OK && nRem!=pCsr->nSegment ){
4826 rc = fts3RepackSegdirLevel(p, iAbsLevel);
4827 }
4828
4829 *pnRem = nRem;
4830 return rc;
4831 }
4832
4833 /*
4834 ** Store an incr-merge hint in the database.
4835 */
4836 static int fts3IncrmergeHintStore(Fts3Table *p, Blob *pHint){
4837 sqlite3_stmt *pReplace = 0;
4838 int rc; /* Return code */
4839
4840 rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pReplace, 0);
4841 if( rc==SQLITE_OK ){
4842 sqlite3_bind_int(pReplace, 1, FTS_STAT_INCRMERGEHINT);
4843 sqlite3_bind_blob(pReplace, 2, pHint->a, pHint->n, SQLITE_STATIC);
4844 sqlite3_step(pReplace);
4845 rc = sqlite3_reset(pReplace);
4846 sqlite3_bind_null(pReplace, 2);
4847 }
4848
4849 return rc;
4850 }
4851
4852 /*
4853 ** Load an incr-merge hint from the database. The incr-merge hint, if one
4854 ** exists, is stored in the rowid==1 row of the %_stat table.
4855 **
4856 ** If successful, populate blob *pHint with the value read from the %_stat
4857 ** table and return SQLITE_OK. Otherwise, if an error occurs, return an
4858 ** SQLite error code.
4859 */
4860 static int fts3IncrmergeHintLoad(Fts3Table *p, Blob *pHint){
4861 sqlite3_stmt *pSelect = 0;
4862 int rc;
4863
4864 pHint->n = 0;
4865 rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pSelect, 0);
4866 if( rc==SQLITE_OK ){
4867 int rc2;
4868 sqlite3_bind_int(pSelect, 1, FTS_STAT_INCRMERGEHINT);
4869 if( SQLITE_ROW==sqlite3_step(pSelect) ){
4870 const char *aHint = sqlite3_column_blob(pSelect, 0);
4871 int nHint = sqlite3_column_bytes(pSelect, 0);
4872 if( aHint ){
4873 blobGrowBuffer(pHint, nHint, &rc);
4874 if( rc==SQLITE_OK ){
4875 if( ALWAYS(pHint->a!=0) ) memcpy(pHint->a, aHint, nHint);
4876 pHint->n = nHint;
4877 }
4878 }
4879 }
4880 rc2 = sqlite3_reset(pSelect);
4881 if( rc==SQLITE_OK ) rc = rc2;
4882 }
4883
4884 return rc;
4885 }
4886
4887 /*
4888 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
4889 ** Otherwise, append an entry to the hint stored in blob *pHint. Each entry
4890 ** consists of two varints, the absolute level number of the input segments
4891 ** and the number of input segments.
4892 **
4893 ** If successful, leave *pRc set to SQLITE_OK and return. If an error occurs,
4894 ** set *pRc to an SQLite error code before returning.
4895 */
4896 static void fts3IncrmergeHintPush(
4897 Blob *pHint, /* Hint blob to append to */
4898 i64 iAbsLevel, /* First varint to store in hint */
4899 int nInput, /* Second varint to store in hint */
4900 int *pRc /* IN/OUT: Error code */
4901 ){
4902 blobGrowBuffer(pHint, pHint->n + 2*FTS3_VARINT_MAX, pRc);
4903 if( *pRc==SQLITE_OK ){
4904 pHint->n += sqlite3Fts3PutVarint(&pHint->a[pHint->n], iAbsLevel);
4905 pHint->n += sqlite3Fts3PutVarint(&pHint->a[pHint->n], (i64)nInput);
4906 }
4907 }
4908
4909 /*
4910 ** Read the last entry (most recently pushed) from the hint blob *pHint
4911 ** and then remove the entry. Write the two values read to *piAbsLevel and
4912 ** *pnInput before returning.
4913 **
4914 ** If no error occurs, return SQLITE_OK. If the hint blob in *pHint does
4915 ** not contain at least two valid varints, return SQLITE_CORRUPT_VTAB.
4916 */
4917 static int fts3IncrmergeHintPop(Blob *pHint, i64 *piAbsLevel, int *pnInput){
4918 const int nHint = pHint->n;
4919 int i;
4920
4921 i = pHint->n-1;
4922 if( (pHint->a[i] & 0x80) ) return FTS_CORRUPT_VTAB;
4923 while( i>0 && (pHint->a[i-1] & 0x80) ) i--;
4924 if( i==0 ) return FTS_CORRUPT_VTAB;
4925 i--;
4926 while( i>0 && (pHint->a[i-1] & 0x80) ) i--;
4927
4928 pHint->n = i;
4929 i += sqlite3Fts3GetVarint(&pHint->a[i], piAbsLevel);
4930 i += fts3GetVarint32(&pHint->a[i], pnInput);
4931 assert( i<=nHint );
4932 if( i!=nHint ) return FTS_CORRUPT_VTAB;
4933
4934 return SQLITE_OK;
4935 }
4936
4937
4938 /*
4939 ** Attempt an incremental merge that writes nMerge leaf blocks.
4940 **
4941 ** Incremental merges happen nMin segments at a time. The segments
4942 ** to be merged are the nMin oldest segments (the ones with the smallest
4943 ** values for the _segdir.idx field) in the highest level that contains
4944 ** at least nMin segments. Multiple merges might occur in an attempt to
4945 ** write the quota of nMerge leaf blocks.
4946 */
4947 int sqlite3Fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){
4948 int rc; /* Return code */
4949 int nRem = nMerge; /* Number of leaf pages yet to be written */
4950 Fts3MultiSegReader *pCsr; /* Cursor used to read input data */
4951 Fts3SegFilter *pFilter; /* Filter used with cursor pCsr */
4952 IncrmergeWriter *pWriter; /* Writer object */
4953 int nSeg = 0; /* Number of input segments */
4954 sqlite3_int64 iAbsLevel = 0; /* Absolute level number to work on */
4955 Blob hint = {0, 0, 0}; /* Hint read from %_stat table */
4956 int bDirtyHint = 0; /* True if blob 'hint' has been modified */
4957
4958 /* Allocate space for the cursor, filter and writer objects */
4959 const int nAlloc = sizeof(*pCsr) + sizeof(*pFilter) + sizeof(*pWriter);
4960 pWriter = (IncrmergeWriter *)sqlite3_malloc64(nAlloc);
4961 if( !pWriter ) return SQLITE_NOMEM;
4962 pFilter = (Fts3SegFilter *)&pWriter[1];
4963 pCsr = (Fts3MultiSegReader *)&pFilter[1];
4964
4965 rc = fts3IncrmergeHintLoad(p, &hint);
4966 while( rc==SQLITE_OK && nRem>0 ){
4967 const i64 nMod = FTS3_SEGDIR_MAXLEVEL * p->nIndex;
4968 sqlite3_stmt *pFindLevel = 0; /* SQL used to determine iAbsLevel */
4969 int bUseHint = 0; /* True if attempting to append */
4970 int iIdx = 0; /* Largest idx in level (iAbsLevel+1) */
4971
4972 /* Search the %_segdir table for the absolute level with the smallest
4973 ** relative level number that contains at least nMin segments, if any.
4974 ** If one is found, set iAbsLevel to the absolute level number and
4975 ** nSeg to nMin. If no level with at least nMin segments can be found,
4976 ** set nSeg to -1.
4977 */
4978 rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0);
4979 sqlite3_bind_int(pFindLevel, 1, MAX(2, nMin));
4980 if( sqlite3_step(pFindLevel)==SQLITE_ROW ){
4981 iAbsLevel = sqlite3_column_int64(pFindLevel, 0);
4982 nSeg = sqlite3_column_int(pFindLevel, 1);
4983 assert( nSeg>=2 );
4984 }else{
4985 nSeg = -1;
4986 }
4987 rc = sqlite3_reset(pFindLevel);
4988
4989 /* If the hint read from the %_stat table is not empty, check if the
4990 ** last entry in it specifies a relative level smaller than or equal
4991 ** to the level identified by the block above (if any). If so, this
4992 ** iteration of the loop will work on merging at the hinted level.
4993 */
4994 if( rc==SQLITE_OK && hint.n ){
4995 int nHint = hint.n;
4996 sqlite3_int64 iHintAbsLevel = 0; /* Hint level */
4997 int nHintSeg = 0; /* Hint number of segments */
4998
4999 rc = fts3IncrmergeHintPop(&hint, &iHintAbsLevel, &nHintSeg);
5000 if( nSeg<0 || (iAbsLevel % nMod) >= (iHintAbsLevel % nMod) ){
5001 /* Based on the scan in the block above, it is known that there
5002 ** are no levels with a relative level smaller than that of
5003 ** iAbsLevel with more than nSeg segments, or if nSeg is -1,
5004 ** no levels with more than nMin segments. Use this to limit the
5005 ** value of nHintSeg to avoid a large memory allocation in case the
5006 ** merge-hint is corrupt*/
5007 iAbsLevel = iHintAbsLevel;
5008 nSeg = MIN(MAX(nMin,nSeg), nHintSeg);
5009 bUseHint = 1;
5010 bDirtyHint = 1;
5011 }else{
5012 /* This undoes the effect of the HintPop() above - so that no entry
5013 ** is removed from the hint blob. */
5014 hint.n = nHint;
5015 }
5016 }
5017
5018 /* If nSeg is less that zero, then there is no level with at least
5019 ** nMin segments and no hint in the %_stat table. No work to do.
5020 ** Exit early in this case. */
5021 if( nSeg<=0 ) break;
5022
5023 assert( nMod<=0x7FFFFFFF );
5024 if( iAbsLevel<0 || iAbsLevel>(nMod<<32) ){
5025 rc = FTS_CORRUPT_VTAB;
5026 break;
5027 }
5028
5029 /* Open a cursor to iterate through the contents of the oldest nSeg
5030 ** indexes of absolute level iAbsLevel. If this cursor is opened using
5031 ** the 'hint' parameters, it is possible that there are less than nSeg
5032 ** segments available in level iAbsLevel. In this case, no work is
5033 ** done on iAbsLevel - fall through to the next iteration of the loop
5034 ** to start work on some other level. */
5035 memset(pWriter, 0, nAlloc);
5036 pFilter->flags = FTS3_SEGMENT_REQUIRE_POS;
5037
5038 if( rc==SQLITE_OK ){
5039 rc = fts3IncrmergeOutputIdx(p, iAbsLevel, &iIdx);
5040 assert( bUseHint==1 || bUseHint==0 );
5041 if( iIdx==0 || (bUseHint && iIdx==1) ){
5042 int bIgnore = 0;
5043 rc = fts3SegmentIsMaxLevel(p, iAbsLevel+1, &bIgnore);
5044 if( bIgnore ){
5045 pFilter->flags |= FTS3_SEGMENT_IGNORE_EMPTY;
5046 }
5047 }
5048 }
5049
5050 if( rc==SQLITE_OK ){
5051 rc = fts3IncrmergeCsr(p, iAbsLevel, nSeg, pCsr);
5052 }
5053 if( SQLITE_OK==rc && pCsr->nSegment==nSeg
5054 && SQLITE_OK==(rc = sqlite3Fts3SegReaderStart(p, pCsr, pFilter))
5055 ){
5056 int bEmpty = 0;
5057 rc = sqlite3Fts3SegReaderStep(p, pCsr);
5058 if( rc==SQLITE_OK ){
5059 bEmpty = 1;
5060 }else if( rc!=SQLITE_ROW ){
5061 sqlite3Fts3SegReaderFinish(pCsr);
5062 break;
5063 }
5064 if( bUseHint && iIdx>0 ){
5065 const char *zKey = pCsr->zTerm;
5066 int nKey = pCsr->nTerm;
5067 rc = fts3IncrmergeLoad(p, iAbsLevel, iIdx-1, zKey, nKey, pWriter);
5068 }else{
5069 rc = fts3IncrmergeWriter(p, iAbsLevel, iIdx, pCsr, pWriter);
5070 }
5071
5072 if( rc==SQLITE_OK && pWriter->nLeafEst ){
5073 fts3LogMerge(nSeg, iAbsLevel);
5074 if( bEmpty==0 ){
5075 do {
5076 rc = fts3IncrmergeAppend(p, pWriter, pCsr);
5077 if( rc==SQLITE_OK ) rc = sqlite3Fts3SegReaderStep(p, pCsr);
5078 if( pWriter->nWork>=nRem && rc==SQLITE_ROW ) rc = SQLITE_OK;
5079 }while( rc==SQLITE_ROW );
5080 }
5081
5082 /* Update or delete the input segments */
5083 if( rc==SQLITE_OK ){
5084 nRem -= (1 + pWriter->nWork);
5085 rc = fts3IncrmergeChomp(p, iAbsLevel, pCsr, &nSeg);
5086 if( nSeg!=0 ){
5087 bDirtyHint = 1;
5088 fts3IncrmergeHintPush(&hint, iAbsLevel, nSeg, &rc);
5089 }
5090 }
5091 }
5092
5093 if( nSeg!=0 ){
5094 pWriter->nLeafData = pWriter->nLeafData * -1;
5095 }
5096 fts3IncrmergeRelease(p, pWriter, &rc);
5097 if( nSeg==0 && pWriter->bNoLeafData==0 ){
5098 fts3PromoteSegments(p, iAbsLevel+1, pWriter->nLeafData);
5099 }
5100 }
5101
5102 sqlite3Fts3SegReaderFinish(pCsr);
5103 }
5104
5105 /* Write the hint values into the %_stat table for the next incr-merger */
5106 if( bDirtyHint && rc==SQLITE_OK ){
5107 rc = fts3IncrmergeHintStore(p, &hint);
5108 }
5109
5110 sqlite3_free(pWriter);
5111 sqlite3_free(hint.a);
5112 return rc;
5113 }
5114
5115 /*
5116 ** Convert the text beginning at *pz into an integer and return
5117 ** its value. Advance *pz to point to the first character past
5118 ** the integer.
5119 **
5120 ** This function used for parameters to merge= and incrmerge=
5121 ** commands.
5122 */
5123 static int fts3Getint(const char **pz){
5124 const char *z = *pz;
5125 int i = 0;
5126 while( (*z)>='0' && (*z)<='9' && i<214748363 ) i = 10*i + *(z++) - '0';
5127 *pz = z;
5128 return i;
5129 }
5130
5131 /*
5132 ** Process statements of the form:
5133 **
5134 ** INSERT INTO table(table) VALUES('merge=A,B');
5135 **
5136 ** A and B are integers that decode to be the number of leaf pages
5137 ** written for the merge, and the minimum number of segments on a level
5138 ** before it will be selected for a merge, respectively.
5139 */
5140 static int fts3DoIncrmerge(
5141 Fts3Table *p, /* FTS3 table handle */
5142 const char *zParam /* Nul-terminated string containing "A,B" */
5143 ){
5144 int rc;
5145 int nMin = (MergeCount(p) / 2);
5146 int nMerge = 0;
5147 const char *z = zParam;
5148
5149 /* Read the first integer value */
5150 nMerge = fts3Getint(&z);
5151
5152 /* If the first integer value is followed by a ',', read the second
5153 ** integer value. */
5154 if( z[0]==',' && z[1]!='\0' ){
5155 z++;
5156 nMin = fts3Getint(&z);
5157 }
5158
5159 if( z[0]!='\0' || nMin<2 ){
5160 rc = SQLITE_ERROR;
5161 }else{
5162 rc = SQLITE_OK;
5163 if( !p->bHasStat ){
5164 assert( p->bFts4==0 );
5165 sqlite3Fts3CreateStatTable(&rc, p);
5166 }
5167 if( rc==SQLITE_OK ){
5168 rc = sqlite3Fts3Incrmerge(p, nMerge, nMin);
5169 }
5170 sqlite3Fts3SegmentsClose(p);
5171 }
5172 return rc;
5173 }
5174
5175 /*
5176 ** Process statements of the form:
5177 **
5178 ** INSERT INTO table(table) VALUES('automerge=X');
5179 **
5180 ** where X is an integer. X==0 means to turn automerge off. X!=0 means
5181 ** turn it on. The setting is persistent.
5182 */
5183 static int fts3DoAutoincrmerge(
5184 Fts3Table *p, /* FTS3 table handle */
5185 const char *zParam /* Nul-terminated string containing boolean */
5186 ){
5187 int rc = SQLITE_OK;
5188 sqlite3_stmt *pStmt = 0;
5189 p->nAutoincrmerge = fts3Getint(&zParam);
5190 if( p->nAutoincrmerge==1 || p->nAutoincrmerge>MergeCount(p) ){
5191 p->nAutoincrmerge = 8;
5192 }
5193 if( !p->bHasStat ){
5194 assert( p->bFts4==0 );
5195 sqlite3Fts3CreateStatTable(&rc, p);
5196 if( rc ) return rc;
5197 }
5198 rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pStmt, 0);
5199 if( rc ) return rc;
5200 sqlite3_bind_int(pStmt, 1, FTS_STAT_AUTOINCRMERGE);
5201 sqlite3_bind_int(pStmt, 2, p->nAutoincrmerge);
5202 sqlite3_step(pStmt);
5203 rc = sqlite3_reset(pStmt);
5204 return rc;
5205 }
5206
5207 /*
5208 ** Return a 64-bit checksum for the FTS index entry specified by the
5209 ** arguments to this function.
5210 */
5211 static u64 fts3ChecksumEntry(
5212 const char *zTerm, /* Pointer to buffer containing term */
5213 int nTerm, /* Size of zTerm in bytes */
5214 int iLangid, /* Language id for current row */
5215 int iIndex, /* Index (0..Fts3Table.nIndex-1) */
5216 i64 iDocid, /* Docid for current row. */
5217 int iCol, /* Column number */
5218 int iPos /* Position */
5219 ){
5220 int i;
5221 u64 ret = (u64)iDocid;
5222
5223 ret += (ret<<3) + iLangid;
5224 ret += (ret<<3) + iIndex;
5225 ret += (ret<<3) + iCol;
5226 ret += (ret<<3) + iPos;
5227 for(i=0; i<nTerm; i++) ret += (ret<<3) + zTerm[i];
5228
5229 return ret;
5230 }
5231
5232 /*
5233 ** Return a checksum of all entries in the FTS index that correspond to
5234 ** language id iLangid. The checksum is calculated by XORing the checksums
5235 ** of each individual entry (see fts3ChecksumEntry()) together.
5236 **
5237 ** If successful, the checksum value is returned and *pRc set to SQLITE_OK.
5238 ** Otherwise, if an error occurs, *pRc is set to an SQLite error code. The
5239 ** return value is undefined in this case.
5240 */
5241 static u64 fts3ChecksumIndex(
5242 Fts3Table *p, /* FTS3 table handle */
5243 int iLangid, /* Language id to return cksum for */
5244 int iIndex, /* Index to cksum (0..p->nIndex-1) */
5245 int *pRc /* OUT: Return code */
5246 ){
5247 Fts3SegFilter filter;
5248 Fts3MultiSegReader csr;
5249 int rc;
5250 u64 cksum = 0;
5251
5252 if( *pRc ) return 0;
5253
5254 memset(&filter, 0, sizeof(filter));
5255 memset(&csr, 0, sizeof(csr));
5256 filter.flags = FTS3_SEGMENT_REQUIRE_POS|FTS3_SEGMENT_IGNORE_EMPTY;
5257 filter.flags |= FTS3_SEGMENT_SCAN;
5258
5259 rc = sqlite3Fts3SegReaderCursor(
5260 p, iLangid, iIndex, FTS3_SEGCURSOR_ALL, 0, 0, 0, 1,&csr
5261 );
5262 if( rc==SQLITE_OK ){
5263 rc = sqlite3Fts3SegReaderStart(p, &csr, &filter);
5264 }
5265
5266 if( rc==SQLITE_OK ){
5267 while( SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, &csr)) ){
5268 char *pCsr = csr.aDoclist;
5269 char *pEnd = &pCsr[csr.nDoclist];
5270
5271 i64 iDocid = 0;
5272 i64 iCol = 0;
5273 u64 iPos = 0;
5274
5275 pCsr += sqlite3Fts3GetVarint(pCsr, &iDocid);
5276 while( pCsr<pEnd ){
5277 u64 iVal = 0;
5278 pCsr += sqlite3Fts3GetVarintU(pCsr, &iVal);
5279 if( pCsr<pEnd ){
5280 if( iVal==0 || iVal==1 ){
5281 iCol = 0;
5282 iPos = 0;
5283 if( iVal ){
5284 pCsr += sqlite3Fts3GetVarint(pCsr, &iCol);
5285 }else{
5286 pCsr += sqlite3Fts3GetVarintU(pCsr, &iVal);
5287 if( p->bDescIdx ){
5288 iDocid = (i64)((u64)iDocid - iVal);
5289 }else{
5290 iDocid = (i64)((u64)iDocid + iVal);
5291 }
5292 }
5293 }else{
5294 iPos += (iVal - 2);
5295 cksum = cksum ^ fts3ChecksumEntry(
5296 csr.zTerm, csr.nTerm, iLangid, iIndex, iDocid,
5297 (int)iCol, (int)iPos
5298 );
5299 }
5300 }
5301 }
5302 }
5303 }
5304 sqlite3Fts3SegReaderFinish(&csr);
5305
5306 *pRc = rc;
5307 return cksum;
5308 }
5309
5310 /*
5311 ** Check if the contents of the FTS index match the current contents of the
5312 ** content table. If no error occurs and the contents do match, set *pbOk
5313 ** to true and return SQLITE_OK. Or if the contents do not match, set *pbOk
5314 ** to false before returning.
5315 **
5316 ** If an error occurs (e.g. an OOM or IO error), return an SQLite error
5317 ** code. The final value of *pbOk is undefined in this case.
5318 */
5319 int sqlite3Fts3IntegrityCheck(Fts3Table *p, int *pbOk){
5320 int rc = SQLITE_OK; /* Return code */
5321 u64 cksum1 = 0; /* Checksum based on FTS index contents */
5322 u64 cksum2 = 0; /* Checksum based on %_content contents */
5323 sqlite3_stmt *pAllLangid = 0; /* Statement to return all language-ids */
5324
5325 /* This block calculates the checksum according to the FTS index. */
5326 rc = fts3SqlStmt(p, SQL_SELECT_ALL_LANGID, &pAllLangid, 0);
5327 if( rc==SQLITE_OK ){
5328 int rc2;
5329 sqlite3_bind_int(pAllLangid, 1, p->iPrevLangid);
5330 sqlite3_bind_int(pAllLangid, 2, p->nIndex);
5331 while( rc==SQLITE_OK && sqlite3_step(pAllLangid)==SQLITE_ROW ){
5332 int iLangid = sqlite3_column_int(pAllLangid, 0);
5333 int i;
5334 for(i=0; i<p->nIndex; i++){
5335 cksum1 = cksum1 ^ fts3ChecksumIndex(p, iLangid, i, &rc);
5336 }
5337 }
5338 rc2 = sqlite3_reset(pAllLangid);
5339 if( rc==SQLITE_OK ) rc = rc2;
5340 }
5341
5342 /* This block calculates the checksum according to the %_content table */
5343 if( rc==SQLITE_OK ){
5344 sqlite3_tokenizer_module const *pModule = p->pTokenizer->pModule;
5345 sqlite3_stmt *pStmt = 0;
5346 char *zSql;
5347
5348 zSql = sqlite3_mprintf("SELECT %s" , p->zReadExprlist);
5349 if( !zSql ){
5350 rc = SQLITE_NOMEM;
5351 }else{
5352 rc = sqlite3Fts3PrepareStmt(p, zSql, 0, 1, &pStmt);
5353 sqlite3_free(zSql);
5354 }
5355
5356 while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
5357 i64 iDocid = sqlite3_column_int64(pStmt, 0);
5358 int iLang = langidFromSelect(p, pStmt);
5359 int iCol;
5360
5361 for(iCol=0; rc==SQLITE_OK && iCol<p->nColumn; iCol++){
5362 if( p->abNotindexed[iCol]==0 ){
5363 const char *zText = (const char *)sqlite3_column_text(pStmt, iCol+1);
5364 sqlite3_tokenizer_cursor *pT = 0;
5365
5366 rc = sqlite3Fts3OpenTokenizer(p->pTokenizer, iLang, zText, -1, &pT);
5367 while( rc==SQLITE_OK ){
5368 char const *zToken; /* Buffer containing token */
5369 int nToken = 0; /* Number of bytes in token */
5370 int iDum1 = 0, iDum2 = 0; /* Dummy variables */
5371 int iPos = 0; /* Position of token in zText */
5372
5373 rc = pModule->xNext(pT, &zToken, &nToken, &iDum1, &iDum2, &iPos);
5374 if( rc==SQLITE_OK ){
5375 int i;
5376 cksum2 = cksum2 ^ fts3ChecksumEntry(
5377 zToken, nToken, iLang, 0, iDocid, iCol, iPos
5378 );
5379 for(i=1; i<p->nIndex; i++){
5380 if( p->aIndex[i].nPrefix<=nToken ){
5381 cksum2 = cksum2 ^ fts3ChecksumEntry(
5382 zToken, p->aIndex[i].nPrefix, iLang, i, iDocid, iCol, iPos
5383 );
5384 }
5385 }
5386 }
5387 }
5388 if( pT ) pModule->xClose(pT);
5389 if( rc==SQLITE_DONE ) rc = SQLITE_OK;
5390 }
5391 }
5392 }
5393
5394 sqlite3_finalize(pStmt);
5395 }
5396
5397 if( rc==SQLITE_CORRUPT_VTAB ){
5398 rc = SQLITE_OK;
5399 *pbOk = 0;
5400 }else{
5401 *pbOk = (rc==SQLITE_OK && cksum1==cksum2);
5402 }
5403 return rc;
5404 }
5405
5406 /*
5407 ** Run the integrity-check. If no error occurs and the current contents of
5408 ** the FTS index are correct, return SQLITE_OK. Or, if the contents of the
5409 ** FTS index are incorrect, return SQLITE_CORRUPT_VTAB.
5410 **
5411 ** Or, if an error (e.g. an OOM or IO error) occurs, return an SQLite
5412 ** error code.
5413 **
5414 ** The integrity-check works as follows. For each token and indexed token
5415 ** prefix in the document set, a 64-bit checksum is calculated (by code
5416 ** in fts3ChecksumEntry()) based on the following:
5417 **
5418 ** + The index number (0 for the main index, 1 for the first prefix
5419 ** index etc.),
5420 ** + The token (or token prefix) text itself,
5421 ** + The language-id of the row it appears in,
5422 ** + The docid of the row it appears in,
5423 ** + The column it appears in, and
5424 ** + The tokens position within that column.
5425 **
5426 ** The checksums for all entries in the index are XORed together to create
5427 ** a single checksum for the entire index.
5428 **
5429 ** The integrity-check code calculates the same checksum in two ways:
5430 **
5431 ** 1. By scanning the contents of the FTS index, and
5432 ** 2. By scanning and tokenizing the content table.
5433 **
5434 ** If the two checksums are identical, the integrity-check is deemed to have
5435 ** passed.
5436 */
5437 static int fts3DoIntegrityCheck(
5438 Fts3Table *p /* FTS3 table handle */
5439 ){
5440 int rc;
5441 int bOk = 0;
5442 rc = sqlite3Fts3IntegrityCheck(p, &bOk);
5443 if( rc==SQLITE_OK && bOk==0 ) rc = FTS_CORRUPT_VTAB;
5444 return rc;
5445 }
5446
5447 /*
5448 ** Handle a 'special' INSERT of the form:
5449 **
5450 ** "INSERT INTO tbl(tbl) VALUES(<expr>)"
5451 **
5452 ** Argument pVal contains the result of <expr>. Currently the only
5453 ** meaningful value to insert is the text 'optimize'.
5454 */
5455 static int fts3SpecialInsert(Fts3Table *p, sqlite3_value *pVal){
5456 int rc = SQLITE_ERROR; /* Return Code */
5457 const char *zVal = (const char *)sqlite3_value_text(pVal);
5458 int nVal = sqlite3_value_bytes(pVal);
5459
5460 if( !zVal ){
5461 return SQLITE_NOMEM;
5462 }else if( nVal==8 && 0==sqlite3_strnicmp(zVal, "optimize", 8) ){
5463 rc = fts3DoOptimize(p, 0);
5464 }else if( nVal==7 && 0==sqlite3_strnicmp(zVal, "rebuild", 7) ){
5465 rc = fts3DoRebuild(p);
5466 }else if( nVal==15 && 0==sqlite3_strnicmp(zVal, "integrity-check", 15) ){
5467 rc = fts3DoIntegrityCheck(p);
5468 }else if( nVal>6 && 0==sqlite3_strnicmp(zVal, "merge=", 6) ){
5469 rc = fts3DoIncrmerge(p, &zVal[6]);
5470 }else if( nVal>10 && 0==sqlite3_strnicmp(zVal, "automerge=", 10) ){
5471 rc = fts3DoAutoincrmerge(p, &zVal[10]);
5472 }else if( nVal==5 && 0==sqlite3_strnicmp(zVal, "flush", 5) ){
5473 rc = sqlite3Fts3PendingTermsFlush(p);
5474 }
5475 #if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
5476 else{
5477 int v;
5478 if( nVal>9 && 0==sqlite3_strnicmp(zVal, "nodesize=", 9) ){
5479 v = atoi(&zVal[9]);
5480 if( v>=24 && v<=p->nPgsz-35 ) p->nNodeSize = v;
5481 rc = SQLITE_OK;
5482 }else if( nVal>11 && 0==sqlite3_strnicmp(zVal, "maxpending=", 11) ){
5483 v = atoi(&zVal[11]);
5484 if( v>=64 && v<=FTS3_MAX_PENDING_DATA ) p->nMaxPendingData = v;
5485 rc = SQLITE_OK;
5486 }else if( nVal>21 && 0==sqlite3_strnicmp(zVal,"test-no-incr-doclist=",21) ){
5487 p->bNoIncrDoclist = atoi(&zVal[21]);
5488 rc = SQLITE_OK;
5489 }else if( nVal>11 && 0==sqlite3_strnicmp(zVal,"mergecount=",11) ){
5490 v = atoi(&zVal[11]);
5491 if( v>=4 && v<=FTS3_MERGE_COUNT && (v&1)==0 ) p->nMergeCount = v;
5492 rc = SQLITE_OK;
5493 }
5494 }
5495 #endif
5496 return rc;
5497 }
5498
5499 #ifndef SQLITE_DISABLE_FTS4_DEFERRED
5500 /*
5501 ** Delete all cached deferred doclists. Deferred doclists are cached
5502 ** (allocated) by the sqlite3Fts3CacheDeferredDoclists() function.
5503 */
5504 void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *pCsr){
5505 Fts3DeferredToken *pDef;
5506 for(pDef=pCsr->pDeferred; pDef; pDef=pDef->pNext){
5507 fts3PendingListDelete(pDef->pList);
5508 pDef->pList = 0;
5509 }
5510 }
5511
5512 /*
5513 ** Free all entries in the pCsr->pDeffered list. Entries are added to
5514 ** this list using sqlite3Fts3DeferToken().
5515 */
5516 void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *pCsr){
5517 Fts3DeferredToken *pDef;
5518 Fts3DeferredToken *pNext;
5519 for(pDef=pCsr->pDeferred; pDef; pDef=pNext){
5520 pNext = pDef->pNext;
5521 fts3PendingListDelete(pDef->pList);
5522 sqlite3_free(pDef);
5523 }
5524 pCsr->pDeferred = 0;
5525 }
5526
5527 /*
5528 ** Generate deferred-doclists for all tokens in the pCsr->pDeferred list
5529 ** based on the row that pCsr currently points to.
5530 **
5531 ** A deferred-doclist is like any other doclist with position information
5532 ** included, except that it only contains entries for a single row of the
5533 ** table, not for all rows.
5534 */
5535 int sqlite3Fts3CacheDeferredDoclists(Fts3Cursor *pCsr){
5536 int rc = SQLITE_OK; /* Return code */
5537 if( pCsr->pDeferred ){
5538 int i; /* Used to iterate through table columns */
5539 sqlite3_int64 iDocid; /* Docid of the row pCsr points to */
5540 Fts3DeferredToken *pDef; /* Used to iterate through deferred tokens */
5541
5542 Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
5543 sqlite3_tokenizer *pT = p->pTokenizer;
5544 sqlite3_tokenizer_module const *pModule = pT->pModule;
5545
5546 assert( pCsr->isRequireSeek==0 );
5547 iDocid = sqlite3_column_int64(pCsr->pStmt, 0);
5548
5549 for(i=0; i<p->nColumn && rc==SQLITE_OK; i++){
5550 if( p->abNotindexed[i]==0 ){
5551 const char *zText = (const char *)sqlite3_column_text(pCsr->pStmt, i+1);
5552 sqlite3_tokenizer_cursor *pTC = 0;
5553
5554 rc = sqlite3Fts3OpenTokenizer(pT, pCsr->iLangid, zText, -1, &pTC);
5555 while( rc==SQLITE_OK ){
5556 char const *zToken; /* Buffer containing token */
5557 int nToken = 0; /* Number of bytes in token */
5558 int iDum1 = 0, iDum2 = 0; /* Dummy variables */
5559 int iPos = 0; /* Position of token in zText */
5560
5561 rc = pModule->xNext(pTC, &zToken, &nToken, &iDum1, &iDum2, &iPos);
5562 for(pDef=pCsr->pDeferred; pDef && rc==SQLITE_OK; pDef=pDef->pNext){
5563 Fts3PhraseToken *pPT = pDef->pToken;
5564 if( (pDef->iCol>=p->nColumn || pDef->iCol==i)
5565 && (pPT->bFirst==0 || iPos==0)
5566 && (pPT->n==nToken || (pPT->isPrefix && pPT->n<nToken))
5567 && (0==memcmp(zToken, pPT->z, pPT->n))
5568 ){
5569 fts3PendingListAppend(&pDef->pList, iDocid, i, iPos, &rc);
5570 }
5571 }
5572 }
5573 if( pTC ) pModule->xClose(pTC);
5574 if( rc==SQLITE_DONE ) rc = SQLITE_OK;
5575 }
5576 }
5577
5578 for(pDef=pCsr->pDeferred; pDef && rc==SQLITE_OK; pDef=pDef->pNext){
5579 if( pDef->pList ){
5580 rc = fts3PendingListAppendVarint(&pDef->pList, 0);
5581 }
5582 }
5583 }
5584
5585 return rc;
5586 }
5587
5588 int sqlite3Fts3DeferredTokenList(
5589 Fts3DeferredToken *p,
5590 char **ppData,
5591 int *pnData
5592 ){
5593 char *pRet;
5594 int nSkip;
5595 sqlite3_int64 dummy;
5596
5597 *ppData = 0;
5598 *pnData = 0;
5599
5600 if( p->pList==0 ){
5601 return SQLITE_OK;
5602 }
5603
5604 pRet = (char *)sqlite3_malloc64(p->pList->nData);
5605 if( !pRet ) return SQLITE_NOMEM;
5606
5607 nSkip = sqlite3Fts3GetVarint(p->pList->aData, &dummy);
5608 *pnData = p->pList->nData - nSkip;
5609 *ppData = pRet;
5610
5611 memcpy(pRet, &p->pList->aData[nSkip], *pnData);
5612 return SQLITE_OK;
5613 }
5614
5615 /*
5616 ** Add an entry for token pToken to the pCsr->pDeferred list.
5617 */
5618 int sqlite3Fts3DeferToken(
5619 Fts3Cursor *pCsr, /* Fts3 table cursor */
5620 Fts3PhraseToken *pToken, /* Token to defer */
5621 int iCol /* Column that token must appear in (or -1) */
5622 ){
5623 Fts3DeferredToken *pDeferred;
5624 pDeferred = sqlite3_malloc64(sizeof(*pDeferred));
5625 if( !pDeferred ){
5626 return SQLITE_NOMEM;
5627 }
5628 memset(pDeferred, 0, sizeof(*pDeferred));
5629 pDeferred->pToken = pToken;
5630 pDeferred->pNext = pCsr->pDeferred;
5631 pDeferred->iCol = iCol;
5632 pCsr->pDeferred = pDeferred;
5633
5634 assert( pToken->pDeferred==0 );
5635 pToken->pDeferred = pDeferred;
5636
5637 return SQLITE_OK;
5638 }
5639 #endif
5640
5641 /*
5642 ** SQLite value pRowid contains the rowid of a row that may or may not be
5643 ** present in the FTS3 table. If it is, delete it and adjust the contents
5644 ** of subsidiary data structures accordingly.
5645 */
5646 static int fts3DeleteByRowid(
5647 Fts3Table *p,
5648 sqlite3_value *pRowid,
5649 int *pnChng, /* IN/OUT: Decrement if row is deleted */
5650 u32 *aSzDel
5651 ){
5652 int rc = SQLITE_OK; /* Return code */
5653 int bFound = 0; /* True if *pRowid really is in the table */
5654
5655 fts3DeleteTerms(&rc, p, pRowid, aSzDel, &bFound);
5656 if( bFound && rc==SQLITE_OK ){
5657 int isEmpty = 0; /* Deleting *pRowid leaves the table empty */
5658 rc = fts3IsEmpty(p, pRowid, &isEmpty);
5659 if( rc==SQLITE_OK ){
5660 if( isEmpty ){
5661 /* Deleting this row means the whole table is empty. In this case
5662 ** delete the contents of all three tables and throw away any
5663 ** data in the pendingTerms hash table. */
5664 rc = fts3DeleteAll(p, 1);
5665 *pnChng = 0;
5666 memset(aSzDel, 0, sizeof(u32) * (p->nColumn+1) * 2);
5667 }else{
5668 *pnChng = *pnChng - 1;
5669 if( p->zContentTbl==0 ){
5670 fts3SqlExec(&rc, p, SQL_DELETE_CONTENT, &pRowid);
5671 }
5672 if( p->bHasDocsize ){
5673 fts3SqlExec(&rc, p, SQL_DELETE_DOCSIZE, &pRowid);
5674 }
5675 }
5676 }
5677 }
5678
5679 return rc;
5680 }
5681
5682 /*
5683 ** This function does the work for the xUpdate method of FTS3 virtual
5684 ** tables. The schema of the virtual table being:
5685 **
5686 ** CREATE TABLE <table name>(
5687 ** <user columns>,
5688 ** <table name> HIDDEN,
5689 ** docid HIDDEN,
5690 ** <langid> HIDDEN
5691 ** );
5692 **
5693 **
5694 */
5695 int sqlite3Fts3UpdateMethod(
5696 sqlite3_vtab *pVtab, /* FTS3 vtab object */
5697 int nArg, /* Size of argument array */
5698 sqlite3_value **apVal, /* Array of arguments */
5699 sqlite_int64 *pRowid /* OUT: The affected (or effected) rowid */
5700 ){
5701 Fts3Table *p = (Fts3Table *)pVtab;
5702 int rc = SQLITE_OK; /* Return Code */
5703 u32 *aSzIns = 0; /* Sizes of inserted documents */
5704 u32 *aSzDel = 0; /* Sizes of deleted documents */
5705 int nChng = 0; /* Net change in number of documents */
5706 int bInsertDone = 0;
5707
5708 /* At this point it must be known if the %_stat table exists or not.
5709 ** So bHasStat may not be 2. */
5710 assert( p->bHasStat==0 || p->bHasStat==1 );
5711
5712 assert( p->pSegments==0 );
5713 assert(
5714 nArg==1 /* DELETE operations */
5715 || nArg==(2 + p->nColumn + 3) /* INSERT or UPDATE operations */
5716 );
5717
5718 /* Check for a "special" INSERT operation. One of the form:
5719 **
5720 ** INSERT INTO xyz(xyz) VALUES('command');
5721 */
5722 if( nArg>1
5723 && sqlite3_value_type(apVal[0])==SQLITE_NULL
5724 && sqlite3_value_type(apVal[p->nColumn+2])!=SQLITE_NULL
5725 ){
5726 rc = fts3SpecialInsert(p, apVal[p->nColumn+2]);
5727 goto update_out;
5728 }
5729
5730 if( nArg>1 && sqlite3_value_int(apVal[2 + p->nColumn + 2])<0 ){
5731 rc = SQLITE_CONSTRAINT;
5732 goto update_out;
5733 }
5734
5735 /* Allocate space to hold the change in document sizes */
5736 aSzDel = sqlite3_malloc64(sizeof(aSzDel[0])*((sqlite3_int64)p->nColumn+1)*2);
5737 if( aSzDel==0 ){
5738 rc = SQLITE_NOMEM;
5739 goto update_out;
5740 }
5741 aSzIns = &aSzDel[p->nColumn+1];
5742 memset(aSzDel, 0, sizeof(aSzDel[0])*(p->nColumn+1)*2);
5743
5744 rc = fts3Writelock(p);
5745 if( rc!=SQLITE_OK ) goto update_out;
5746
5747 /* If this is an INSERT operation, or an UPDATE that modifies the rowid
5748 ** value, then this operation requires constraint handling.
5749 **
5750 ** If the on-conflict mode is REPLACE, this means that the existing row
5751 ** should be deleted from the database before inserting the new row. Or,
5752 ** if the on-conflict mode is other than REPLACE, then this method must
5753 ** detect the conflict and return SQLITE_CONSTRAINT before beginning to
5754 ** modify the database file.
5755 */
5756 if( nArg>1 && p->zContentTbl==0 ){
5757 /* Find the value object that holds the new rowid value. */
5758 sqlite3_value *pNewRowid = apVal[3+p->nColumn];
5759 if( sqlite3_value_type(pNewRowid)==SQLITE_NULL ){
5760 pNewRowid = apVal[1];
5761 }
5762
5763 if( sqlite3_value_type(pNewRowid)!=SQLITE_NULL && (
5764 sqlite3_value_type(apVal[0])==SQLITE_NULL
5765 || sqlite3_value_int64(apVal[0])!=sqlite3_value_int64(pNewRowid)
5766 )){
5767 /* The new rowid is not NULL (in this case the rowid will be
5768 ** automatically assigned and there is no chance of a conflict), and
5769 ** the statement is either an INSERT or an UPDATE that modifies the
5770 ** rowid column. So if the conflict mode is REPLACE, then delete any
5771 ** existing row with rowid=pNewRowid.
5772 **
5773 ** Or, if the conflict mode is not REPLACE, insert the new record into
5774 ** the %_content table. If we hit the duplicate rowid constraint (or any
5775 ** other error) while doing so, return immediately.
5776 **
5777 ** This branch may also run if pNewRowid contains a value that cannot
5778 ** be losslessly converted to an integer. In this case, the eventual
5779 ** call to fts3InsertData() (either just below or further on in this
5780 ** function) will return SQLITE_MISMATCH. If fts3DeleteByRowid is
5781 ** invoked, it will delete zero rows (since no row will have
5782 ** docid=$pNewRowid if $pNewRowid is not an integer value).
5783 */
5784 if( sqlite3_vtab_on_conflict(p->db)==SQLITE_REPLACE ){
5785 rc = fts3DeleteByRowid(p, pNewRowid, &nChng, aSzDel);
5786 }else{
5787 rc = fts3InsertData(p, apVal, pRowid);
5788 bInsertDone = 1;
5789 }
5790 }
5791 }
5792 if( rc!=SQLITE_OK ){
5793 goto update_out;
5794 }
5795
5796 /* If this is a DELETE or UPDATE operation, remove the old record. */
5797 if( sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
5798 assert( sqlite3_value_type(apVal[0])==SQLITE_INTEGER );
5799 rc = fts3DeleteByRowid(p, apVal[0], &nChng, aSzDel);
5800 }
5801
5802 /* If this is an INSERT or UPDATE operation, insert the new record. */
5803 if( nArg>1 && rc==SQLITE_OK ){
5804 int iLangid = sqlite3_value_int(apVal[2 + p->nColumn + 2]);
5805 if( bInsertDone==0 ){
5806 rc = fts3InsertData(p, apVal, pRowid);
5807 if( rc==SQLITE_CONSTRAINT && p->zContentTbl==0 ){
5808 rc = FTS_CORRUPT_VTAB;
5809 }
5810 }
5811 if( rc==SQLITE_OK ){
5812 rc = fts3PendingTermsDocid(p, 0, iLangid, *pRowid);
5813 }
5814 if( rc==SQLITE_OK ){
5815 assert( p->iPrevDocid==*pRowid );
5816 rc = fts3InsertTerms(p, iLangid, apVal, aSzIns);
5817 }
5818 if( p->bHasDocsize ){
5819 fts3InsertDocsize(&rc, p, aSzIns);
5820 }
5821 nChng++;
5822 }
5823
5824 if( p->bFts4 ){
5825 fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nChng);
5826 }
5827
5828 update_out:
5829 sqlite3_free(aSzDel);
5830 sqlite3Fts3SegmentsClose(p);
5831 return rc;
5832 }
5833
5834 /*
5835 ** Flush any data in the pending-terms hash table to disk. If successful,
5836 ** merge all segments in the database (including the new segment, if
5837 ** there was any data to flush) into a single segment.
5838 */
5839 int sqlite3Fts3Optimize(Fts3Table *p){
5840 int rc;
5841 rc = sqlite3_exec(p->db, "SAVEPOINT fts3", 0, 0, 0);
5842 if( rc==SQLITE_OK ){
5843 rc = fts3DoOptimize(p, 1);
5844 if( rc==SQLITE_OK || rc==SQLITE_DONE ){
5845 int rc2 = sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);
5846 if( rc2!=SQLITE_OK ) rc = rc2;
5847 }else{
5848 sqlite3_exec(p->db, "ROLLBACK TO fts3", 0, 0, 0);
5849 sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);
5850 }
5851 }
5852 sqlite3Fts3SegmentsClose(p);
5853 return rc;
5854 }
5855
5856 #endif