Annotation of embedaddon/sqlite3/ext/fts3/fts3_write.c, revision 1.1
1.1 ! misho 1: /*
! 2: ** 2009 Oct 23
! 3: **
! 4: ** The author disclaims copyright to this source code. In place of
! 5: ** a legal notice, here is a blessing:
! 6: **
! 7: ** May you do good and not evil.
! 8: ** May you find forgiveness for yourself and forgive others.
! 9: ** May you share freely, never taking more than you give.
! 10: **
! 11: ******************************************************************************
! 12: **
! 13: ** This file is part of the SQLite FTS3 extension module. Specifically,
! 14: ** this file contains code to insert, update and delete rows from FTS3
! 15: ** tables. It also contains code to merge FTS3 b-tree segments. Some
! 16: ** of the sub-routines used to merge segments are also used by the query
! 17: ** code in fts3.c.
! 18: */
! 19:
! 20: #include "fts3Int.h"
! 21: #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
! 22:
! 23: #include <string.h>
! 24: #include <assert.h>
! 25: #include <stdlib.h>
! 26:
! 27: /*
! 28: ** When full-text index nodes are loaded from disk, the buffer that they
! 29: ** are loaded into has the following number of bytes of padding at the end
! 30: ** of it. i.e. if a full-text index node is 900 bytes in size, then a buffer
! 31: ** of 920 bytes is allocated for it.
! 32: **
! 33: ** This means that if we have a pointer into a buffer containing node data,
! 34: ** it is always safe to read up to two varints from it without risking an
! 35: ** overread, even if the node data is corrupted.
! 36: */
! 37: #define FTS3_NODE_PADDING (FTS3_VARINT_MAX*2)
! 38:
! 39: /*
! 40: ** Under certain circumstances, b-tree nodes (doclists) can be loaded into
! 41: ** memory incrementally instead of all at once. This can be a big performance
! 42: ** win (reduced IO and CPU) if SQLite stops calling the virtual table xNext()
! 43: ** method before retrieving all query results (as may happen, for example,
! 44: ** if a query has a LIMIT clause).
! 45: **
! 46: ** Incremental loading is used for b-tree nodes FTS3_NODE_CHUNK_THRESHOLD
! 47: ** bytes and larger. Nodes are loaded in chunks of FTS3_NODE_CHUNKSIZE bytes.
! 48: ** The code is written so that the hard lower-limit for each of these values
! 49: ** is 1. Clearly such small values would be inefficient, but can be useful
! 50: ** for testing purposes.
! 51: **
! 52: ** If this module is built with SQLITE_TEST defined, these constants may
! 53: ** be overridden at runtime for testing purposes. File fts3_test.c contains
! 54: ** a Tcl interface to read and write the values.
! 55: */
! 56: #ifdef SQLITE_TEST
! 57: int test_fts3_node_chunksize = (4*1024);
! 58: int test_fts3_node_chunk_threshold = (4*1024)*4;
! 59: # define FTS3_NODE_CHUNKSIZE test_fts3_node_chunksize
! 60: # define FTS3_NODE_CHUNK_THRESHOLD test_fts3_node_chunk_threshold
! 61: #else
! 62: # define FTS3_NODE_CHUNKSIZE (4*1024)
! 63: # define FTS3_NODE_CHUNK_THRESHOLD (FTS3_NODE_CHUNKSIZE*4)
! 64: #endif
! 65:
! 66: typedef struct PendingList PendingList;
! 67: typedef struct SegmentNode SegmentNode;
! 68: typedef struct SegmentWriter SegmentWriter;
! 69:
! 70: /*
! 71: ** An instance of the following data structure is used to build doclists
! 72: ** incrementally. See function fts3PendingListAppend() for details.
! 73: */
! 74: struct PendingList {
! 75: int nData;
! 76: char *aData;
! 77: int nSpace;
! 78: sqlite3_int64 iLastDocid;
! 79: sqlite3_int64 iLastCol;
! 80: sqlite3_int64 iLastPos;
! 81: };
! 82:
! 83:
! 84: /*
! 85: ** Each cursor has a (possibly empty) linked list of the following objects.
! 86: */
! 87: struct Fts3DeferredToken {
! 88: Fts3PhraseToken *pToken; /* Pointer to corresponding expr token */
! 89: int iCol; /* Column token must occur in */
! 90: Fts3DeferredToken *pNext; /* Next in list of deferred tokens */
! 91: PendingList *pList; /* Doclist is assembled here */
! 92: };
! 93:
! 94: /*
! 95: ** An instance of this structure is used to iterate through the terms on
! 96: ** a contiguous set of segment b-tree leaf nodes. Although the details of
! 97: ** this structure are only manipulated by code in this file, opaque handles
! 98: ** of type Fts3SegReader* are also used by code in fts3.c to iterate through
! 99: ** terms when querying the full-text index. See functions:
! 100: **
! 101: ** sqlite3Fts3SegReaderNew()
! 102: ** sqlite3Fts3SegReaderFree()
! 103: ** sqlite3Fts3SegReaderIterate()
! 104: **
! 105: ** Methods used to manipulate Fts3SegReader structures:
! 106: **
! 107: ** fts3SegReaderNext()
! 108: ** fts3SegReaderFirstDocid()
! 109: ** fts3SegReaderNextDocid()
! 110: */
! 111: struct Fts3SegReader {
! 112: int iIdx; /* Index within level, or 0x7FFFFFFF for PT */
! 113:
! 114: sqlite3_int64 iStartBlock; /* Rowid of first leaf block to traverse */
! 115: sqlite3_int64 iLeafEndBlock; /* Rowid of final leaf block to traverse */
! 116: sqlite3_int64 iEndBlock; /* Rowid of final block in segment (or 0) */
! 117: sqlite3_int64 iCurrentBlock; /* Current leaf block (or 0) */
! 118:
! 119: char *aNode; /* Pointer to node data (or NULL) */
! 120: int nNode; /* Size of buffer at aNode (or 0) */
! 121: int nPopulate; /* If >0, bytes of buffer aNode[] loaded */
! 122: sqlite3_blob *pBlob; /* If not NULL, blob handle to read node */
! 123:
! 124: Fts3HashElem **ppNextElem;
! 125:
! 126: /* Variables set by fts3SegReaderNext(). These may be read directly
! 127: ** by the caller. They are valid from the time SegmentReaderNew() returns
! 128: ** until SegmentReaderNext() returns something other than SQLITE_OK
! 129: ** (i.e. SQLITE_DONE).
! 130: */
! 131: int nTerm; /* Number of bytes in current term */
! 132: char *zTerm; /* Pointer to current term */
! 133: int nTermAlloc; /* Allocated size of zTerm buffer */
! 134: char *aDoclist; /* Pointer to doclist of current entry */
! 135: int nDoclist; /* Size of doclist in current entry */
! 136:
! 137: /* The following variables are used by fts3SegReaderNextDocid() to iterate
! 138: ** through the current doclist (aDoclist/nDoclist).
! 139: */
! 140: char *pOffsetList;
! 141: int nOffsetList; /* For descending pending seg-readers only */
! 142: sqlite3_int64 iDocid;
! 143: };
! 144:
! 145: #define fts3SegReaderIsPending(p) ((p)->ppNextElem!=0)
! 146: #define fts3SegReaderIsRootOnly(p) ((p)->aNode==(char *)&(p)[1])
! 147:
! 148: /*
! 149: ** An instance of this structure is used to create a segment b-tree in the
! 150: ** database. The internal details of this type are only accessed by the
! 151: ** following functions:
! 152: **
! 153: ** fts3SegWriterAdd()
! 154: ** fts3SegWriterFlush()
! 155: ** fts3SegWriterFree()
! 156: */
! 157: struct SegmentWriter {
! 158: SegmentNode *pTree; /* Pointer to interior tree structure */
! 159: sqlite3_int64 iFirst; /* First slot in %_segments written */
! 160: sqlite3_int64 iFree; /* Next free slot in %_segments */
! 161: char *zTerm; /* Pointer to previous term buffer */
! 162: int nTerm; /* Number of bytes in zTerm */
! 163: int nMalloc; /* Size of malloc'd buffer at zMalloc */
! 164: char *zMalloc; /* Malloc'd space (possibly) used for zTerm */
! 165: int nSize; /* Size of allocation at aData */
! 166: int nData; /* Bytes of data in aData */
! 167: char *aData; /* Pointer to block from malloc() */
! 168: };
! 169:
! 170: /*
! 171: ** Type SegmentNode is used by the following three functions to create
! 172: ** the interior part of the segment b+-tree structures (everything except
! 173: ** the leaf nodes). These functions and type are only ever used by code
! 174: ** within the fts3SegWriterXXX() family of functions described above.
! 175: **
! 176: ** fts3NodeAddTerm()
! 177: ** fts3NodeWrite()
! 178: ** fts3NodeFree()
! 179: **
! 180: ** When a b+tree is written to the database (either as a result of a merge
! 181: ** or the pending-terms table being flushed), leaves are written into the
! 182: ** database file as soon as they are completely populated. The interior of
! 183: ** the tree is assembled in memory and written out only once all leaves have
! 184: ** been populated and stored. This is Ok, as the b+-tree fanout is usually
! 185: ** very large, meaning that the interior of the tree consumes relatively
! 186: ** little memory.
! 187: */
! 188: struct SegmentNode {
! 189: SegmentNode *pParent; /* Parent node (or NULL for root node) */
! 190: SegmentNode *pRight; /* Pointer to right-sibling */
! 191: SegmentNode *pLeftmost; /* Pointer to left-most node of this depth */
! 192: int nEntry; /* Number of terms written to node so far */
! 193: char *zTerm; /* Pointer to previous term buffer */
! 194: int nTerm; /* Number of bytes in zTerm */
! 195: int nMalloc; /* Size of malloc'd buffer at zMalloc */
! 196: char *zMalloc; /* Malloc'd space (possibly) used for zTerm */
! 197: int nData; /* Bytes of valid data so far */
! 198: char *aData; /* Node data */
! 199: };
! 200:
! 201: /*
! 202: ** Valid values for the second argument to fts3SqlStmt().
! 203: */
! 204: #define SQL_DELETE_CONTENT 0
! 205: #define SQL_IS_EMPTY 1
! 206: #define SQL_DELETE_ALL_CONTENT 2
! 207: #define SQL_DELETE_ALL_SEGMENTS 3
! 208: #define SQL_DELETE_ALL_SEGDIR 4
! 209: #define SQL_DELETE_ALL_DOCSIZE 5
! 210: #define SQL_DELETE_ALL_STAT 6
! 211: #define SQL_SELECT_CONTENT_BY_ROWID 7
! 212: #define SQL_NEXT_SEGMENT_INDEX 8
! 213: #define SQL_INSERT_SEGMENTS 9
! 214: #define SQL_NEXT_SEGMENTS_ID 10
! 215: #define SQL_INSERT_SEGDIR 11
! 216: #define SQL_SELECT_LEVEL 12
! 217: #define SQL_SELECT_LEVEL_RANGE 13
! 218: #define SQL_SELECT_LEVEL_COUNT 14
! 219: #define SQL_SELECT_SEGDIR_MAX_LEVEL 15
! 220: #define SQL_DELETE_SEGDIR_LEVEL 16
! 221: #define SQL_DELETE_SEGMENTS_RANGE 17
! 222: #define SQL_CONTENT_INSERT 18
! 223: #define SQL_DELETE_DOCSIZE 19
! 224: #define SQL_REPLACE_DOCSIZE 20
! 225: #define SQL_SELECT_DOCSIZE 21
! 226: #define SQL_SELECT_DOCTOTAL 22
! 227: #define SQL_REPLACE_DOCTOTAL 23
! 228:
! 229: #define SQL_SELECT_ALL_PREFIX_LEVEL 24
! 230: #define SQL_DELETE_ALL_TERMS_SEGDIR 25
! 231:
! 232: #define SQL_DELETE_SEGDIR_RANGE 26
! 233:
! 234: /*
! 235: ** This function is used to obtain an SQLite prepared statement handle
! 236: ** for the statement identified by the second argument. If successful,
! 237: ** *pp is set to the requested statement handle and SQLITE_OK returned.
! 238: ** Otherwise, an SQLite error code is returned and *pp is set to 0.
! 239: **
! 240: ** If argument apVal is not NULL, then it must point to an array with
! 241: ** at least as many entries as the requested statement has bound
! 242: ** parameters. The values are bound to the statements parameters before
! 243: ** returning.
! 244: */
! 245: static int fts3SqlStmt(
! 246: Fts3Table *p, /* Virtual table handle */
! 247: int eStmt, /* One of the SQL_XXX constants above */
! 248: sqlite3_stmt **pp, /* OUT: Statement handle */
! 249: sqlite3_value **apVal /* Values to bind to statement */
! 250: ){
! 251: const char *azSql[] = {
! 252: /* 0 */ "DELETE FROM %Q.'%q_content' WHERE rowid = ?",
! 253: /* 1 */ "SELECT NOT EXISTS(SELECT docid FROM %Q.'%q_content' WHERE rowid!=?)",
! 254: /* 2 */ "DELETE FROM %Q.'%q_content'",
! 255: /* 3 */ "DELETE FROM %Q.'%q_segments'",
! 256: /* 4 */ "DELETE FROM %Q.'%q_segdir'",
! 257: /* 5 */ "DELETE FROM %Q.'%q_docsize'",
! 258: /* 6 */ "DELETE FROM %Q.'%q_stat'",
! 259: /* 7 */ "SELECT %s WHERE rowid=?",
! 260: /* 8 */ "SELECT (SELECT max(idx) FROM %Q.'%q_segdir' WHERE level = ?) + 1",
! 261: /* 9 */ "INSERT INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)",
! 262: /* 10 */ "SELECT coalesce((SELECT max(blockid) FROM %Q.'%q_segments') + 1, 1)",
! 263: /* 11 */ "INSERT INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)",
! 264:
! 265: /* Return segments in order from oldest to newest.*/
! 266: /* 12 */ "SELECT idx, start_block, leaves_end_block, end_block, root "
! 267: "FROM %Q.'%q_segdir' WHERE level = ? ORDER BY idx ASC",
! 268: /* 13 */ "SELECT idx, start_block, leaves_end_block, end_block, root "
! 269: "FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?"
! 270: "ORDER BY level DESC, idx ASC",
! 271:
! 272: /* 14 */ "SELECT count(*) FROM %Q.'%q_segdir' WHERE level = ?",
! 273: /* 15 */ "SELECT max(level) FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?",
! 274:
! 275: /* 16 */ "DELETE FROM %Q.'%q_segdir' WHERE level = ?",
! 276: /* 17 */ "DELETE FROM %Q.'%q_segments' WHERE blockid BETWEEN ? AND ?",
! 277: /* 18 */ "INSERT INTO %Q.'%q_content' VALUES(%s)",
! 278: /* 19 */ "DELETE FROM %Q.'%q_docsize' WHERE docid = ?",
! 279: /* 20 */ "REPLACE INTO %Q.'%q_docsize' VALUES(?,?)",
! 280: /* 21 */ "SELECT size FROM %Q.'%q_docsize' WHERE docid=?",
! 281: /* 22 */ "SELECT value FROM %Q.'%q_stat' WHERE id=0",
! 282: /* 23 */ "REPLACE INTO %Q.'%q_stat' VALUES(0,?)",
! 283: /* 24 */ "",
! 284: /* 25 */ "",
! 285:
! 286: /* 26 */ "DELETE FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?",
! 287:
! 288: };
! 289: int rc = SQLITE_OK;
! 290: sqlite3_stmt *pStmt;
! 291:
! 292: assert( SizeofArray(azSql)==SizeofArray(p->aStmt) );
! 293: assert( eStmt<SizeofArray(azSql) && eStmt>=0 );
! 294:
! 295: pStmt = p->aStmt[eStmt];
! 296: if( !pStmt ){
! 297: char *zSql;
! 298: if( eStmt==SQL_CONTENT_INSERT ){
! 299: zSql = sqlite3_mprintf(azSql[eStmt], p->zDb, p->zName, p->zWriteExprlist);
! 300: }else if( eStmt==SQL_SELECT_CONTENT_BY_ROWID ){
! 301: zSql = sqlite3_mprintf(azSql[eStmt], p->zReadExprlist);
! 302: }else{
! 303: zSql = sqlite3_mprintf(azSql[eStmt], p->zDb, p->zName);
! 304: }
! 305: if( !zSql ){
! 306: rc = SQLITE_NOMEM;
! 307: }else{
! 308: rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, NULL);
! 309: sqlite3_free(zSql);
! 310: assert( rc==SQLITE_OK || pStmt==0 );
! 311: p->aStmt[eStmt] = pStmt;
! 312: }
! 313: }
! 314: if( apVal ){
! 315: int i;
! 316: int nParam = sqlite3_bind_parameter_count(pStmt);
! 317: for(i=0; rc==SQLITE_OK && i<nParam; i++){
! 318: rc = sqlite3_bind_value(pStmt, i+1, apVal[i]);
! 319: }
! 320: }
! 321: *pp = pStmt;
! 322: return rc;
! 323: }
! 324:
! 325: static int fts3SelectDocsize(
! 326: Fts3Table *pTab, /* FTS3 table handle */
! 327: int eStmt, /* Either SQL_SELECT_DOCSIZE or DOCTOTAL */
! 328: sqlite3_int64 iDocid, /* Docid to bind for SQL_SELECT_DOCSIZE */
! 329: sqlite3_stmt **ppStmt /* OUT: Statement handle */
! 330: ){
! 331: sqlite3_stmt *pStmt = 0; /* Statement requested from fts3SqlStmt() */
! 332: int rc; /* Return code */
! 333:
! 334: assert( eStmt==SQL_SELECT_DOCSIZE || eStmt==SQL_SELECT_DOCTOTAL );
! 335:
! 336: rc = fts3SqlStmt(pTab, eStmt, &pStmt, 0);
! 337: if( rc==SQLITE_OK ){
! 338: if( eStmt==SQL_SELECT_DOCSIZE ){
! 339: sqlite3_bind_int64(pStmt, 1, iDocid);
! 340: }
! 341: rc = sqlite3_step(pStmt);
! 342: if( rc!=SQLITE_ROW || sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB ){
! 343: rc = sqlite3_reset(pStmt);
! 344: if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;
! 345: pStmt = 0;
! 346: }else{
! 347: rc = SQLITE_OK;
! 348: }
! 349: }
! 350:
! 351: *ppStmt = pStmt;
! 352: return rc;
! 353: }
! 354:
! 355: int sqlite3Fts3SelectDoctotal(
! 356: Fts3Table *pTab, /* Fts3 table handle */
! 357: sqlite3_stmt **ppStmt /* OUT: Statement handle */
! 358: ){
! 359: return fts3SelectDocsize(pTab, SQL_SELECT_DOCTOTAL, 0, ppStmt);
! 360: }
! 361:
! 362: int sqlite3Fts3SelectDocsize(
! 363: Fts3Table *pTab, /* Fts3 table handle */
! 364: sqlite3_int64 iDocid, /* Docid to read size data for */
! 365: sqlite3_stmt **ppStmt /* OUT: Statement handle */
! 366: ){
! 367: return fts3SelectDocsize(pTab, SQL_SELECT_DOCSIZE, iDocid, ppStmt);
! 368: }
! 369:
! 370: /*
! 371: ** Similar to fts3SqlStmt(). Except, after binding the parameters in
! 372: ** array apVal[] to the SQL statement identified by eStmt, the statement
! 373: ** is executed.
! 374: **
! 375: ** Returns SQLITE_OK if the statement is successfully executed, or an
! 376: ** SQLite error code otherwise.
! 377: */
! 378: static void fts3SqlExec(
! 379: int *pRC, /* Result code */
! 380: Fts3Table *p, /* The FTS3 table */
! 381: int eStmt, /* Index of statement to evaluate */
! 382: sqlite3_value **apVal /* Parameters to bind */
! 383: ){
! 384: sqlite3_stmt *pStmt;
! 385: int rc;
! 386: if( *pRC ) return;
! 387: rc = fts3SqlStmt(p, eStmt, &pStmt, apVal);
! 388: if( rc==SQLITE_OK ){
! 389: sqlite3_step(pStmt);
! 390: rc = sqlite3_reset(pStmt);
! 391: }
! 392: *pRC = rc;
! 393: }
! 394:
! 395:
! 396: /*
! 397: ** This function ensures that the caller has obtained a shared-cache
! 398: ** table-lock on the %_content table. This is required before reading
! 399: ** data from the fts3 table. If this lock is not acquired first, then
! 400: ** the caller may end up holding read-locks on the %_segments and %_segdir
! 401: ** tables, but no read-lock on the %_content table. If this happens
! 402: ** a second connection will be able to write to the fts3 table, but
! 403: ** attempting to commit those writes might return SQLITE_LOCKED or
! 404: ** SQLITE_LOCKED_SHAREDCACHE (because the commit attempts to obtain
! 405: ** write-locks on the %_segments and %_segdir ** tables).
! 406: **
! 407: ** We try to avoid this because if FTS3 returns any error when committing
! 408: ** a transaction, the whole transaction will be rolled back. And this is
! 409: ** not what users expect when they get SQLITE_LOCKED_SHAREDCACHE. It can
! 410: ** still happen if the user reads data directly from the %_segments or
! 411: ** %_segdir tables instead of going through FTS3 though.
! 412: **
! 413: ** This reasoning does not apply to a content=xxx table.
! 414: */
! 415: int sqlite3Fts3ReadLock(Fts3Table *p){
! 416: int rc; /* Return code */
! 417: sqlite3_stmt *pStmt; /* Statement used to obtain lock */
! 418:
! 419: if( p->zContentTbl==0 ){
! 420: rc = fts3SqlStmt(p, SQL_SELECT_CONTENT_BY_ROWID, &pStmt, 0);
! 421: if( rc==SQLITE_OK ){
! 422: sqlite3_bind_null(pStmt, 1);
! 423: sqlite3_step(pStmt);
! 424: rc = sqlite3_reset(pStmt);
! 425: }
! 426: }else{
! 427: rc = SQLITE_OK;
! 428: }
! 429:
! 430: return rc;
! 431: }
! 432:
! 433: /*
! 434: ** Set *ppStmt to a statement handle that may be used to iterate through
! 435: ** all rows in the %_segdir table, from oldest to newest. If successful,
! 436: ** return SQLITE_OK. If an error occurs while preparing the statement,
! 437: ** return an SQLite error code.
! 438: **
! 439: ** There is only ever one instance of this SQL statement compiled for
! 440: ** each FTS3 table.
! 441: **
! 442: ** The statement returns the following columns from the %_segdir table:
! 443: **
! 444: ** 0: idx
! 445: ** 1: start_block
! 446: ** 2: leaves_end_block
! 447: ** 3: end_block
! 448: ** 4: root
! 449: */
! 450: int sqlite3Fts3AllSegdirs(
! 451: Fts3Table *p, /* FTS3 table */
! 452: int iIndex, /* Index for p->aIndex[] */
! 453: int iLevel, /* Level to select */
! 454: sqlite3_stmt **ppStmt /* OUT: Compiled statement */
! 455: ){
! 456: int rc;
! 457: sqlite3_stmt *pStmt = 0;
! 458:
! 459: assert( iLevel==FTS3_SEGCURSOR_ALL || iLevel>=0 );
! 460: assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
! 461: assert( iIndex>=0 && iIndex<p->nIndex );
! 462:
! 463: if( iLevel<0 ){
! 464: /* "SELECT * FROM %_segdir WHERE level BETWEEN ? AND ? ORDER BY ..." */
! 465: rc = fts3SqlStmt(p, SQL_SELECT_LEVEL_RANGE, &pStmt, 0);
! 466: if( rc==SQLITE_OK ){
! 467: sqlite3_bind_int(pStmt, 1, iIndex*FTS3_SEGDIR_MAXLEVEL);
! 468: sqlite3_bind_int(pStmt, 2, (iIndex+1)*FTS3_SEGDIR_MAXLEVEL-1);
! 469: }
! 470: }else{
! 471: /* "SELECT * FROM %_segdir WHERE level = ? ORDER BY ..." */
! 472: rc = fts3SqlStmt(p, SQL_SELECT_LEVEL, &pStmt, 0);
! 473: if( rc==SQLITE_OK ){
! 474: sqlite3_bind_int(pStmt, 1, iLevel+iIndex*FTS3_SEGDIR_MAXLEVEL);
! 475: }
! 476: }
! 477: *ppStmt = pStmt;
! 478: return rc;
! 479: }
! 480:
! 481:
! 482: /*
! 483: ** Append a single varint to a PendingList buffer. SQLITE_OK is returned
! 484: ** if successful, or an SQLite error code otherwise.
! 485: **
! 486: ** This function also serves to allocate the PendingList structure itself.
! 487: ** For example, to create a new PendingList structure containing two
! 488: ** varints:
! 489: **
! 490: ** PendingList *p = 0;
! 491: ** fts3PendingListAppendVarint(&p, 1);
! 492: ** fts3PendingListAppendVarint(&p, 2);
! 493: */
! 494: static int fts3PendingListAppendVarint(
! 495: PendingList **pp, /* IN/OUT: Pointer to PendingList struct */
! 496: sqlite3_int64 i /* Value to append to data */
! 497: ){
! 498: PendingList *p = *pp;
! 499:
! 500: /* Allocate or grow the PendingList as required. */
! 501: if( !p ){
! 502: p = sqlite3_malloc(sizeof(*p) + 100);
! 503: if( !p ){
! 504: return SQLITE_NOMEM;
! 505: }
! 506: p->nSpace = 100;
! 507: p->aData = (char *)&p[1];
! 508: p->nData = 0;
! 509: }
! 510: else if( p->nData+FTS3_VARINT_MAX+1>p->nSpace ){
! 511: int nNew = p->nSpace * 2;
! 512: p = sqlite3_realloc(p, sizeof(*p) + nNew);
! 513: if( !p ){
! 514: sqlite3_free(*pp);
! 515: *pp = 0;
! 516: return SQLITE_NOMEM;
! 517: }
! 518: p->nSpace = nNew;
! 519: p->aData = (char *)&p[1];
! 520: }
! 521:
! 522: /* Append the new serialized varint to the end of the list. */
! 523: p->nData += sqlite3Fts3PutVarint(&p->aData[p->nData], i);
! 524: p->aData[p->nData] = '\0';
! 525: *pp = p;
! 526: return SQLITE_OK;
! 527: }
! 528:
! 529: /*
! 530: ** Add a docid/column/position entry to a PendingList structure. Non-zero
! 531: ** is returned if the structure is sqlite3_realloced as part of adding
! 532: ** the entry. Otherwise, zero.
! 533: **
! 534: ** If an OOM error occurs, *pRc is set to SQLITE_NOMEM before returning.
! 535: ** Zero is always returned in this case. Otherwise, if no OOM error occurs,
! 536: ** it is set to SQLITE_OK.
! 537: */
! 538: static int fts3PendingListAppend(
! 539: PendingList **pp, /* IN/OUT: PendingList structure */
! 540: sqlite3_int64 iDocid, /* Docid for entry to add */
! 541: sqlite3_int64 iCol, /* Column for entry to add */
! 542: sqlite3_int64 iPos, /* Position of term for entry to add */
! 543: int *pRc /* OUT: Return code */
! 544: ){
! 545: PendingList *p = *pp;
! 546: int rc = SQLITE_OK;
! 547:
! 548: assert( !p || p->iLastDocid<=iDocid );
! 549:
! 550: if( !p || p->iLastDocid!=iDocid ){
! 551: sqlite3_int64 iDelta = iDocid - (p ? p->iLastDocid : 0);
! 552: if( p ){
! 553: assert( p->nData<p->nSpace );
! 554: assert( p->aData[p->nData]==0 );
! 555: p->nData++;
! 556: }
! 557: if( SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, iDelta)) ){
! 558: goto pendinglistappend_out;
! 559: }
! 560: p->iLastCol = -1;
! 561: p->iLastPos = 0;
! 562: p->iLastDocid = iDocid;
! 563: }
! 564: if( iCol>0 && p->iLastCol!=iCol ){
! 565: if( SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, 1))
! 566: || SQLITE_OK!=(rc = fts3PendingListAppendVarint(&p, iCol))
! 567: ){
! 568: goto pendinglistappend_out;
! 569: }
! 570: p->iLastCol = iCol;
! 571: p->iLastPos = 0;
! 572: }
! 573: if( iCol>=0 ){
! 574: assert( iPos>p->iLastPos || (iPos==0 && p->iLastPos==0) );
! 575: rc = fts3PendingListAppendVarint(&p, 2+iPos-p->iLastPos);
! 576: if( rc==SQLITE_OK ){
! 577: p->iLastPos = iPos;
! 578: }
! 579: }
! 580:
! 581: pendinglistappend_out:
! 582: *pRc = rc;
! 583: if( p!=*pp ){
! 584: *pp = p;
! 585: return 1;
! 586: }
! 587: return 0;
! 588: }
! 589:
! 590: /*
! 591: ** Free a PendingList object allocated by fts3PendingListAppend().
! 592: */
! 593: static void fts3PendingListDelete(PendingList *pList){
! 594: sqlite3_free(pList);
! 595: }
! 596:
! 597: /*
! 598: ** Add an entry to one of the pending-terms hash tables.
! 599: */
! 600: static int fts3PendingTermsAddOne(
! 601: Fts3Table *p,
! 602: int iCol,
! 603: int iPos,
! 604: Fts3Hash *pHash, /* Pending terms hash table to add entry to */
! 605: const char *zToken,
! 606: int nToken
! 607: ){
! 608: PendingList *pList;
! 609: int rc = SQLITE_OK;
! 610:
! 611: pList = (PendingList *)fts3HashFind(pHash, zToken, nToken);
! 612: if( pList ){
! 613: p->nPendingData -= (pList->nData + nToken + sizeof(Fts3HashElem));
! 614: }
! 615: if( fts3PendingListAppend(&pList, p->iPrevDocid, iCol, iPos, &rc) ){
! 616: if( pList==fts3HashInsert(pHash, zToken, nToken, pList) ){
! 617: /* Malloc failed while inserting the new entry. This can only
! 618: ** happen if there was no previous entry for this token.
! 619: */
! 620: assert( 0==fts3HashFind(pHash, zToken, nToken) );
! 621: sqlite3_free(pList);
! 622: rc = SQLITE_NOMEM;
! 623: }
! 624: }
! 625: if( rc==SQLITE_OK ){
! 626: p->nPendingData += (pList->nData + nToken + sizeof(Fts3HashElem));
! 627: }
! 628: return rc;
! 629: }
! 630:
! 631: /*
! 632: ** Tokenize the nul-terminated string zText and add all tokens to the
! 633: ** pending-terms hash-table. The docid used is that currently stored in
! 634: ** p->iPrevDocid, and the column is specified by argument iCol.
! 635: **
! 636: ** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.
! 637: */
! 638: static int fts3PendingTermsAdd(
! 639: Fts3Table *p, /* Table into which text will be inserted */
! 640: const char *zText, /* Text of document to be inserted */
! 641: int iCol, /* Column into which text is being inserted */
! 642: u32 *pnWord /* OUT: Number of tokens inserted */
! 643: ){
! 644: int rc;
! 645: int iStart;
! 646: int iEnd;
! 647: int iPos;
! 648: int nWord = 0;
! 649:
! 650: char const *zToken;
! 651: int nToken;
! 652:
! 653: sqlite3_tokenizer *pTokenizer = p->pTokenizer;
! 654: sqlite3_tokenizer_module const *pModule = pTokenizer->pModule;
! 655: sqlite3_tokenizer_cursor *pCsr;
! 656: int (*xNext)(sqlite3_tokenizer_cursor *pCursor,
! 657: const char**,int*,int*,int*,int*);
! 658:
! 659: assert( pTokenizer && pModule );
! 660:
! 661: /* If the user has inserted a NULL value, this function may be called with
! 662: ** zText==0. In this case, add zero token entries to the hash table and
! 663: ** return early. */
! 664: if( zText==0 ){
! 665: *pnWord = 0;
! 666: return SQLITE_OK;
! 667: }
! 668:
! 669: rc = pModule->xOpen(pTokenizer, zText, -1, &pCsr);
! 670: if( rc!=SQLITE_OK ){
! 671: return rc;
! 672: }
! 673: pCsr->pTokenizer = pTokenizer;
! 674:
! 675: xNext = pModule->xNext;
! 676: while( SQLITE_OK==rc
! 677: && SQLITE_OK==(rc = xNext(pCsr, &zToken, &nToken, &iStart, &iEnd, &iPos))
! 678: ){
! 679: int i;
! 680: if( iPos>=nWord ) nWord = iPos+1;
! 681:
! 682: /* Positions cannot be negative; we use -1 as a terminator internally.
! 683: ** Tokens must have a non-zero length.
! 684: */
! 685: if( iPos<0 || !zToken || nToken<=0 ){
! 686: rc = SQLITE_ERROR;
! 687: break;
! 688: }
! 689:
! 690: /* Add the term to the terms index */
! 691: rc = fts3PendingTermsAddOne(
! 692: p, iCol, iPos, &p->aIndex[0].hPending, zToken, nToken
! 693: );
! 694:
! 695: /* Add the term to each of the prefix indexes that it is not too
! 696: ** short for. */
! 697: for(i=1; rc==SQLITE_OK && i<p->nIndex; i++){
! 698: struct Fts3Index *pIndex = &p->aIndex[i];
! 699: if( nToken<pIndex->nPrefix ) continue;
! 700: rc = fts3PendingTermsAddOne(
! 701: p, iCol, iPos, &pIndex->hPending, zToken, pIndex->nPrefix
! 702: );
! 703: }
! 704: }
! 705:
! 706: pModule->xClose(pCsr);
! 707: *pnWord = nWord;
! 708: return (rc==SQLITE_DONE ? SQLITE_OK : rc);
! 709: }
! 710:
! 711: /*
! 712: ** Calling this function indicates that subsequent calls to
! 713: ** fts3PendingTermsAdd() are to add term/position-list pairs for the
! 714: ** contents of the document with docid iDocid.
! 715: */
! 716: static int fts3PendingTermsDocid(Fts3Table *p, sqlite_int64 iDocid){
! 717: /* TODO(shess) Explore whether partially flushing the buffer on
! 718: ** forced-flush would provide better performance. I suspect that if
! 719: ** we ordered the doclists by size and flushed the largest until the
! 720: ** buffer was half empty, that would let the less frequent terms
! 721: ** generate longer doclists.
! 722: */
! 723: if( iDocid<=p->iPrevDocid || p->nPendingData>p->nMaxPendingData ){
! 724: int rc = sqlite3Fts3PendingTermsFlush(p);
! 725: if( rc!=SQLITE_OK ) return rc;
! 726: }
! 727: p->iPrevDocid = iDocid;
! 728: return SQLITE_OK;
! 729: }
! 730:
! 731: /*
! 732: ** Discard the contents of the pending-terms hash tables.
! 733: */
! 734: void sqlite3Fts3PendingTermsClear(Fts3Table *p){
! 735: int i;
! 736: for(i=0; i<p->nIndex; i++){
! 737: Fts3HashElem *pElem;
! 738: Fts3Hash *pHash = &p->aIndex[i].hPending;
! 739: for(pElem=fts3HashFirst(pHash); pElem; pElem=fts3HashNext(pElem)){
! 740: PendingList *pList = (PendingList *)fts3HashData(pElem);
! 741: fts3PendingListDelete(pList);
! 742: }
! 743: fts3HashClear(pHash);
! 744: }
! 745: p->nPendingData = 0;
! 746: }
! 747:
! 748: /*
! 749: ** This function is called by the xUpdate() method as part of an INSERT
! 750: ** operation. It adds entries for each term in the new record to the
! 751: ** pendingTerms hash table.
! 752: **
! 753: ** Argument apVal is the same as the similarly named argument passed to
! 754: ** fts3InsertData(). Parameter iDocid is the docid of the new row.
! 755: */
! 756: static int fts3InsertTerms(Fts3Table *p, sqlite3_value **apVal, u32 *aSz){
! 757: int i; /* Iterator variable */
! 758: for(i=2; i<p->nColumn+2; i++){
! 759: const char *zText = (const char *)sqlite3_value_text(apVal[i]);
! 760: int rc = fts3PendingTermsAdd(p, zText, i-2, &aSz[i-2]);
! 761: if( rc!=SQLITE_OK ){
! 762: return rc;
! 763: }
! 764: aSz[p->nColumn] += sqlite3_value_bytes(apVal[i]);
! 765: }
! 766: return SQLITE_OK;
! 767: }
! 768:
! 769: /*
! 770: ** This function is called by the xUpdate() method for an INSERT operation.
! 771: ** The apVal parameter is passed a copy of the apVal argument passed by
! 772: ** SQLite to the xUpdate() method. i.e:
! 773: **
! 774: ** apVal[0] Not used for INSERT.
! 775: ** apVal[1] rowid
! 776: ** apVal[2] Left-most user-defined column
! 777: ** ...
! 778: ** apVal[p->nColumn+1] Right-most user-defined column
! 779: ** apVal[p->nColumn+2] Hidden column with same name as table
! 780: ** apVal[p->nColumn+3] Hidden "docid" column (alias for rowid)
! 781: */
! 782: static int fts3InsertData(
! 783: Fts3Table *p, /* Full-text table */
! 784: sqlite3_value **apVal, /* Array of values to insert */
! 785: sqlite3_int64 *piDocid /* OUT: Docid for row just inserted */
! 786: ){
! 787: int rc; /* Return code */
! 788: sqlite3_stmt *pContentInsert; /* INSERT INTO %_content VALUES(...) */
! 789:
! 790: if( p->zContentTbl ){
! 791: sqlite3_value *pRowid = apVal[p->nColumn+3];
! 792: if( sqlite3_value_type(pRowid)==SQLITE_NULL ){
! 793: pRowid = apVal[1];
! 794: }
! 795: if( sqlite3_value_type(pRowid)!=SQLITE_INTEGER ){
! 796: return SQLITE_CONSTRAINT;
! 797: }
! 798: *piDocid = sqlite3_value_int64(pRowid);
! 799: return SQLITE_OK;
! 800: }
! 801:
! 802: /* Locate the statement handle used to insert data into the %_content
! 803: ** table. The SQL for this statement is:
! 804: **
! 805: ** INSERT INTO %_content VALUES(?, ?, ?, ...)
! 806: **
! 807: ** The statement features N '?' variables, where N is the number of user
! 808: ** defined columns in the FTS3 table, plus one for the docid field.
! 809: */
! 810: rc = fts3SqlStmt(p, SQL_CONTENT_INSERT, &pContentInsert, &apVal[1]);
! 811: if( rc!=SQLITE_OK ){
! 812: return rc;
! 813: }
! 814:
! 815: /* There is a quirk here. The users INSERT statement may have specified
! 816: ** a value for the "rowid" field, for the "docid" field, or for both.
! 817: ** Which is a problem, since "rowid" and "docid" are aliases for the
! 818: ** same value. For example:
! 819: **
! 820: ** INSERT INTO fts3tbl(rowid, docid) VALUES(1, 2);
! 821: **
! 822: ** In FTS3, this is an error. It is an error to specify non-NULL values
! 823: ** for both docid and some other rowid alias.
! 824: */
! 825: if( SQLITE_NULL!=sqlite3_value_type(apVal[3+p->nColumn]) ){
! 826: if( SQLITE_NULL==sqlite3_value_type(apVal[0])
! 827: && SQLITE_NULL!=sqlite3_value_type(apVal[1])
! 828: ){
! 829: /* A rowid/docid conflict. */
! 830: return SQLITE_ERROR;
! 831: }
! 832: rc = sqlite3_bind_value(pContentInsert, 1, apVal[3+p->nColumn]);
! 833: if( rc!=SQLITE_OK ) return rc;
! 834: }
! 835:
! 836: /* Execute the statement to insert the record. Set *piDocid to the
! 837: ** new docid value.
! 838: */
! 839: sqlite3_step(pContentInsert);
! 840: rc = sqlite3_reset(pContentInsert);
! 841:
! 842: *piDocid = sqlite3_last_insert_rowid(p->db);
! 843: return rc;
! 844: }
! 845:
! 846:
! 847:
! 848: /*
! 849: ** Remove all data from the FTS3 table. Clear the hash table containing
! 850: ** pending terms.
! 851: */
! 852: static int fts3DeleteAll(Fts3Table *p, int bContent){
! 853: int rc = SQLITE_OK; /* Return code */
! 854:
! 855: /* Discard the contents of the pending-terms hash table. */
! 856: sqlite3Fts3PendingTermsClear(p);
! 857:
! 858: /* Delete everything from the shadow tables. Except, leave %_content as
! 859: ** is if bContent is false. */
! 860: assert( p->zContentTbl==0 || bContent==0 );
! 861: if( bContent ) fts3SqlExec(&rc, p, SQL_DELETE_ALL_CONTENT, 0);
! 862: fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGMENTS, 0);
! 863: fts3SqlExec(&rc, p, SQL_DELETE_ALL_SEGDIR, 0);
! 864: if( p->bHasDocsize ){
! 865: fts3SqlExec(&rc, p, SQL_DELETE_ALL_DOCSIZE, 0);
! 866: }
! 867: if( p->bHasStat ){
! 868: fts3SqlExec(&rc, p, SQL_DELETE_ALL_STAT, 0);
! 869: }
! 870: return rc;
! 871: }
! 872:
! 873: /*
! 874: ** The first element in the apVal[] array is assumed to contain the docid
! 875: ** (an integer) of a row about to be deleted. Remove all terms from the
! 876: ** full-text index.
! 877: */
! 878: static void fts3DeleteTerms(
! 879: int *pRC, /* Result code */
! 880: Fts3Table *p, /* The FTS table to delete from */
! 881: sqlite3_value *pRowid, /* The docid to be deleted */
! 882: u32 *aSz /* Sizes of deleted document written here */
! 883: ){
! 884: int rc;
! 885: sqlite3_stmt *pSelect;
! 886:
! 887: if( *pRC ) return;
! 888: rc = fts3SqlStmt(p, SQL_SELECT_CONTENT_BY_ROWID, &pSelect, &pRowid);
! 889: if( rc==SQLITE_OK ){
! 890: if( SQLITE_ROW==sqlite3_step(pSelect) ){
! 891: int i;
! 892: for(i=1; i<=p->nColumn; i++){
! 893: const char *zText = (const char *)sqlite3_column_text(pSelect, i);
! 894: rc = fts3PendingTermsAdd(p, zText, -1, &aSz[i-1]);
! 895: if( rc!=SQLITE_OK ){
! 896: sqlite3_reset(pSelect);
! 897: *pRC = rc;
! 898: return;
! 899: }
! 900: aSz[p->nColumn] += sqlite3_column_bytes(pSelect, i);
! 901: }
! 902: }
! 903: rc = sqlite3_reset(pSelect);
! 904: }else{
! 905: sqlite3_reset(pSelect);
! 906: }
! 907: *pRC = rc;
! 908: }
! 909:
! 910: /*
! 911: ** Forward declaration to account for the circular dependency between
! 912: ** functions fts3SegmentMerge() and fts3AllocateSegdirIdx().
! 913: */
! 914: static int fts3SegmentMerge(Fts3Table *, int, int);
! 915:
! 916: /*
! 917: ** This function allocates a new level iLevel index in the segdir table.
! 918: ** Usually, indexes are allocated within a level sequentially starting
! 919: ** with 0, so the allocated index is one greater than the value returned
! 920: ** by:
! 921: **
! 922: ** SELECT max(idx) FROM %_segdir WHERE level = :iLevel
! 923: **
! 924: ** However, if there are already FTS3_MERGE_COUNT indexes at the requested
! 925: ** level, they are merged into a single level (iLevel+1) segment and the
! 926: ** allocated index is 0.
! 927: **
! 928: ** If successful, *piIdx is set to the allocated index slot and SQLITE_OK
! 929: ** returned. Otherwise, an SQLite error code is returned.
! 930: */
! 931: static int fts3AllocateSegdirIdx(
! 932: Fts3Table *p,
! 933: int iIndex, /* Index for p->aIndex */
! 934: int iLevel,
! 935: int *piIdx
! 936: ){
! 937: int rc; /* Return Code */
! 938: sqlite3_stmt *pNextIdx; /* Query for next idx at level iLevel */
! 939: int iNext = 0; /* Result of query pNextIdx */
! 940:
! 941: /* Set variable iNext to the next available segdir index at level iLevel. */
! 942: rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pNextIdx, 0);
! 943: if( rc==SQLITE_OK ){
! 944: sqlite3_bind_int(pNextIdx, 1, iIndex*FTS3_SEGDIR_MAXLEVEL + iLevel);
! 945: if( SQLITE_ROW==sqlite3_step(pNextIdx) ){
! 946: iNext = sqlite3_column_int(pNextIdx, 0);
! 947: }
! 948: rc = sqlite3_reset(pNextIdx);
! 949: }
! 950:
! 951: if( rc==SQLITE_OK ){
! 952: /* If iNext is FTS3_MERGE_COUNT, indicating that level iLevel is already
! 953: ** full, merge all segments in level iLevel into a single iLevel+1
! 954: ** segment and allocate (newly freed) index 0 at level iLevel. Otherwise,
! 955: ** if iNext is less than FTS3_MERGE_COUNT, allocate index iNext.
! 956: */
! 957: if( iNext>=FTS3_MERGE_COUNT ){
! 958: rc = fts3SegmentMerge(p, iIndex, iLevel);
! 959: *piIdx = 0;
! 960: }else{
! 961: *piIdx = iNext;
! 962: }
! 963: }
! 964:
! 965: return rc;
! 966: }
! 967:
! 968: /*
! 969: ** The %_segments table is declared as follows:
! 970: **
! 971: ** CREATE TABLE %_segments(blockid INTEGER PRIMARY KEY, block BLOB)
! 972: **
! 973: ** This function reads data from a single row of the %_segments table. The
! 974: ** specific row is identified by the iBlockid parameter. If paBlob is not
! 975: ** NULL, then a buffer is allocated using sqlite3_malloc() and populated
! 976: ** with the contents of the blob stored in the "block" column of the
! 977: ** identified table row is. Whether or not paBlob is NULL, *pnBlob is set
! 978: ** to the size of the blob in bytes before returning.
! 979: **
! 980: ** If an error occurs, or the table does not contain the specified row,
! 981: ** an SQLite error code is returned. Otherwise, SQLITE_OK is returned. If
! 982: ** paBlob is non-NULL, then it is the responsibility of the caller to
! 983: ** eventually free the returned buffer.
! 984: **
! 985: ** This function may leave an open sqlite3_blob* handle in the
! 986: ** Fts3Table.pSegments variable. This handle is reused by subsequent calls
! 987: ** to this function. The handle may be closed by calling the
! 988: ** sqlite3Fts3SegmentsClose() function. Reusing a blob handle is a handy
! 989: ** performance improvement, but the blob handle should always be closed
! 990: ** before control is returned to the user (to prevent a lock being held
! 991: ** on the database file for longer than necessary). Thus, any virtual table
! 992: ** method (xFilter etc.) that may directly or indirectly call this function
! 993: ** must call sqlite3Fts3SegmentsClose() before returning.
! 994: */
! 995: int sqlite3Fts3ReadBlock(
! 996: Fts3Table *p, /* FTS3 table handle */
! 997: sqlite3_int64 iBlockid, /* Access the row with blockid=$iBlockid */
! 998: char **paBlob, /* OUT: Blob data in malloc'd buffer */
! 999: int *pnBlob, /* OUT: Size of blob data */
! 1000: int *pnLoad /* OUT: Bytes actually loaded */
! 1001: ){
! 1002: int rc; /* Return code */
! 1003:
! 1004: /* pnBlob must be non-NULL. paBlob may be NULL or non-NULL. */
! 1005: assert( pnBlob);
! 1006:
! 1007: if( p->pSegments ){
! 1008: rc = sqlite3_blob_reopen(p->pSegments, iBlockid);
! 1009: }else{
! 1010: if( 0==p->zSegmentsTbl ){
! 1011: p->zSegmentsTbl = sqlite3_mprintf("%s_segments", p->zName);
! 1012: if( 0==p->zSegmentsTbl ) return SQLITE_NOMEM;
! 1013: }
! 1014: rc = sqlite3_blob_open(
! 1015: p->db, p->zDb, p->zSegmentsTbl, "block", iBlockid, 0, &p->pSegments
! 1016: );
! 1017: }
! 1018:
! 1019: if( rc==SQLITE_OK ){
! 1020: int nByte = sqlite3_blob_bytes(p->pSegments);
! 1021: *pnBlob = nByte;
! 1022: if( paBlob ){
! 1023: char *aByte = sqlite3_malloc(nByte + FTS3_NODE_PADDING);
! 1024: if( !aByte ){
! 1025: rc = SQLITE_NOMEM;
! 1026: }else{
! 1027: if( pnLoad && nByte>(FTS3_NODE_CHUNK_THRESHOLD) ){
! 1028: nByte = FTS3_NODE_CHUNKSIZE;
! 1029: *pnLoad = nByte;
! 1030: }
! 1031: rc = sqlite3_blob_read(p->pSegments, aByte, nByte, 0);
! 1032: memset(&aByte[nByte], 0, FTS3_NODE_PADDING);
! 1033: if( rc!=SQLITE_OK ){
! 1034: sqlite3_free(aByte);
! 1035: aByte = 0;
! 1036: }
! 1037: }
! 1038: *paBlob = aByte;
! 1039: }
! 1040: }
! 1041:
! 1042: return rc;
! 1043: }
! 1044:
! 1045: /*
! 1046: ** Close the blob handle at p->pSegments, if it is open. See comments above
! 1047: ** the sqlite3Fts3ReadBlock() function for details.
! 1048: */
! 1049: void sqlite3Fts3SegmentsClose(Fts3Table *p){
! 1050: sqlite3_blob_close(p->pSegments);
! 1051: p->pSegments = 0;
! 1052: }
! 1053:
! 1054: static int fts3SegReaderIncrRead(Fts3SegReader *pReader){
! 1055: int nRead; /* Number of bytes to read */
! 1056: int rc; /* Return code */
! 1057:
! 1058: nRead = MIN(pReader->nNode - pReader->nPopulate, FTS3_NODE_CHUNKSIZE);
! 1059: rc = sqlite3_blob_read(
! 1060: pReader->pBlob,
! 1061: &pReader->aNode[pReader->nPopulate],
! 1062: nRead,
! 1063: pReader->nPopulate
! 1064: );
! 1065:
! 1066: if( rc==SQLITE_OK ){
! 1067: pReader->nPopulate += nRead;
! 1068: memset(&pReader->aNode[pReader->nPopulate], 0, FTS3_NODE_PADDING);
! 1069: if( pReader->nPopulate==pReader->nNode ){
! 1070: sqlite3_blob_close(pReader->pBlob);
! 1071: pReader->pBlob = 0;
! 1072: pReader->nPopulate = 0;
! 1073: }
! 1074: }
! 1075: return rc;
! 1076: }
! 1077:
! 1078: static int fts3SegReaderRequire(Fts3SegReader *pReader, char *pFrom, int nByte){
! 1079: int rc = SQLITE_OK;
! 1080: assert( !pReader->pBlob
! 1081: || (pFrom>=pReader->aNode && pFrom<&pReader->aNode[pReader->nNode])
! 1082: );
! 1083: while( pReader->pBlob && rc==SQLITE_OK
! 1084: && (pFrom - pReader->aNode + nByte)>pReader->nPopulate
! 1085: ){
! 1086: rc = fts3SegReaderIncrRead(pReader);
! 1087: }
! 1088: return rc;
! 1089: }
! 1090:
! 1091: /*
! 1092: ** Move the iterator passed as the first argument to the next term in the
! 1093: ** segment. If successful, SQLITE_OK is returned. If there is no next term,
! 1094: ** SQLITE_DONE. Otherwise, an SQLite error code.
! 1095: */
! 1096: static int fts3SegReaderNext(
! 1097: Fts3Table *p,
! 1098: Fts3SegReader *pReader,
! 1099: int bIncr
! 1100: ){
! 1101: int rc; /* Return code of various sub-routines */
! 1102: char *pNext; /* Cursor variable */
! 1103: int nPrefix; /* Number of bytes in term prefix */
! 1104: int nSuffix; /* Number of bytes in term suffix */
! 1105:
! 1106: if( !pReader->aDoclist ){
! 1107: pNext = pReader->aNode;
! 1108: }else{
! 1109: pNext = &pReader->aDoclist[pReader->nDoclist];
! 1110: }
! 1111:
! 1112: if( !pNext || pNext>=&pReader->aNode[pReader->nNode] ){
! 1113:
! 1114: if( fts3SegReaderIsPending(pReader) ){
! 1115: Fts3HashElem *pElem = *(pReader->ppNextElem);
! 1116: if( pElem==0 ){
! 1117: pReader->aNode = 0;
! 1118: }else{
! 1119: PendingList *pList = (PendingList *)fts3HashData(pElem);
! 1120: pReader->zTerm = (char *)fts3HashKey(pElem);
! 1121: pReader->nTerm = fts3HashKeysize(pElem);
! 1122: pReader->nNode = pReader->nDoclist = pList->nData + 1;
! 1123: pReader->aNode = pReader->aDoclist = pList->aData;
! 1124: pReader->ppNextElem++;
! 1125: assert( pReader->aNode );
! 1126: }
! 1127: return SQLITE_OK;
! 1128: }
! 1129:
! 1130: if( !fts3SegReaderIsRootOnly(pReader) ){
! 1131: sqlite3_free(pReader->aNode);
! 1132: sqlite3_blob_close(pReader->pBlob);
! 1133: pReader->pBlob = 0;
! 1134: }
! 1135: pReader->aNode = 0;
! 1136:
! 1137: /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf
! 1138: ** blocks have already been traversed. */
! 1139: assert( pReader->iCurrentBlock<=pReader->iLeafEndBlock );
! 1140: if( pReader->iCurrentBlock>=pReader->iLeafEndBlock ){
! 1141: return SQLITE_OK;
! 1142: }
! 1143:
! 1144: rc = sqlite3Fts3ReadBlock(
! 1145: p, ++pReader->iCurrentBlock, &pReader->aNode, &pReader->nNode,
! 1146: (bIncr ? &pReader->nPopulate : 0)
! 1147: );
! 1148: if( rc!=SQLITE_OK ) return rc;
! 1149: assert( pReader->pBlob==0 );
! 1150: if( bIncr && pReader->nPopulate<pReader->nNode ){
! 1151: pReader->pBlob = p->pSegments;
! 1152: p->pSegments = 0;
! 1153: }
! 1154: pNext = pReader->aNode;
! 1155: }
! 1156:
! 1157: assert( !fts3SegReaderIsPending(pReader) );
! 1158:
! 1159: rc = fts3SegReaderRequire(pReader, pNext, FTS3_VARINT_MAX*2);
! 1160: if( rc!=SQLITE_OK ) return rc;
! 1161:
! 1162: /* Because of the FTS3_NODE_PADDING bytes of padding, the following is
! 1163: ** safe (no risk of overread) even if the node data is corrupted. */
! 1164: pNext += sqlite3Fts3GetVarint32(pNext, &nPrefix);
! 1165: pNext += sqlite3Fts3GetVarint32(pNext, &nSuffix);
! 1166: if( nPrefix<0 || nSuffix<=0
! 1167: || &pNext[nSuffix]>&pReader->aNode[pReader->nNode]
! 1168: ){
! 1169: return FTS_CORRUPT_VTAB;
! 1170: }
! 1171:
! 1172: if( nPrefix+nSuffix>pReader->nTermAlloc ){
! 1173: int nNew = (nPrefix+nSuffix)*2;
! 1174: char *zNew = sqlite3_realloc(pReader->zTerm, nNew);
! 1175: if( !zNew ){
! 1176: return SQLITE_NOMEM;
! 1177: }
! 1178: pReader->zTerm = zNew;
! 1179: pReader->nTermAlloc = nNew;
! 1180: }
! 1181:
! 1182: rc = fts3SegReaderRequire(pReader, pNext, nSuffix+FTS3_VARINT_MAX);
! 1183: if( rc!=SQLITE_OK ) return rc;
! 1184:
! 1185: memcpy(&pReader->zTerm[nPrefix], pNext, nSuffix);
! 1186: pReader->nTerm = nPrefix+nSuffix;
! 1187: pNext += nSuffix;
! 1188: pNext += sqlite3Fts3GetVarint32(pNext, &pReader->nDoclist);
! 1189: pReader->aDoclist = pNext;
! 1190: pReader->pOffsetList = 0;
! 1191:
! 1192: /* Check that the doclist does not appear to extend past the end of the
! 1193: ** b-tree node. And that the final byte of the doclist is 0x00. If either
! 1194: ** of these statements is untrue, then the data structure is corrupt.
! 1195: */
! 1196: if( &pReader->aDoclist[pReader->nDoclist]>&pReader->aNode[pReader->nNode]
! 1197: || (pReader->nPopulate==0 && pReader->aDoclist[pReader->nDoclist-1])
! 1198: ){
! 1199: return FTS_CORRUPT_VTAB;
! 1200: }
! 1201: return SQLITE_OK;
! 1202: }
! 1203:
! 1204: /*
! 1205: ** Set the SegReader to point to the first docid in the doclist associated
! 1206: ** with the current term.
! 1207: */
! 1208: static int fts3SegReaderFirstDocid(Fts3Table *pTab, Fts3SegReader *pReader){
! 1209: int rc = SQLITE_OK;
! 1210: assert( pReader->aDoclist );
! 1211: assert( !pReader->pOffsetList );
! 1212: if( pTab->bDescIdx && fts3SegReaderIsPending(pReader) ){
! 1213: u8 bEof = 0;
! 1214: pReader->iDocid = 0;
! 1215: pReader->nOffsetList = 0;
! 1216: sqlite3Fts3DoclistPrev(0,
! 1217: pReader->aDoclist, pReader->nDoclist, &pReader->pOffsetList,
! 1218: &pReader->iDocid, &pReader->nOffsetList, &bEof
! 1219: );
! 1220: }else{
! 1221: rc = fts3SegReaderRequire(pReader, pReader->aDoclist, FTS3_VARINT_MAX);
! 1222: if( rc==SQLITE_OK ){
! 1223: int n = sqlite3Fts3GetVarint(pReader->aDoclist, &pReader->iDocid);
! 1224: pReader->pOffsetList = &pReader->aDoclist[n];
! 1225: }
! 1226: }
! 1227: return rc;
! 1228: }
! 1229:
! 1230: /*
! 1231: ** Advance the SegReader to point to the next docid in the doclist
! 1232: ** associated with the current term.
! 1233: **
! 1234: ** If arguments ppOffsetList and pnOffsetList are not NULL, then
! 1235: ** *ppOffsetList is set to point to the first column-offset list
! 1236: ** in the doclist entry (i.e. immediately past the docid varint).
! 1237: ** *pnOffsetList is set to the length of the set of column-offset
! 1238: ** lists, not including the nul-terminator byte. For example:
! 1239: */
! 1240: static int fts3SegReaderNextDocid(
! 1241: Fts3Table *pTab,
! 1242: Fts3SegReader *pReader, /* Reader to advance to next docid */
! 1243: char **ppOffsetList, /* OUT: Pointer to current position-list */
! 1244: int *pnOffsetList /* OUT: Length of *ppOffsetList in bytes */
! 1245: ){
! 1246: int rc = SQLITE_OK;
! 1247: char *p = pReader->pOffsetList;
! 1248: char c = 0;
! 1249:
! 1250: assert( p );
! 1251:
! 1252: if( pTab->bDescIdx && fts3SegReaderIsPending(pReader) ){
! 1253: /* A pending-terms seg-reader for an FTS4 table that uses order=desc.
! 1254: ** Pending-terms doclists are always built up in ascending order, so
! 1255: ** we have to iterate through them backwards here. */
! 1256: u8 bEof = 0;
! 1257: if( ppOffsetList ){
! 1258: *ppOffsetList = pReader->pOffsetList;
! 1259: *pnOffsetList = pReader->nOffsetList - 1;
! 1260: }
! 1261: sqlite3Fts3DoclistPrev(0,
! 1262: pReader->aDoclist, pReader->nDoclist, &p, &pReader->iDocid,
! 1263: &pReader->nOffsetList, &bEof
! 1264: );
! 1265: if( bEof ){
! 1266: pReader->pOffsetList = 0;
! 1267: }else{
! 1268: pReader->pOffsetList = p;
! 1269: }
! 1270: }else{
! 1271: char *pEnd = &pReader->aDoclist[pReader->nDoclist];
! 1272:
! 1273: /* Pointer p currently points at the first byte of an offset list. The
! 1274: ** following block advances it to point one byte past the end of
! 1275: ** the same offset list. */
! 1276: while( 1 ){
! 1277:
! 1278: /* The following line of code (and the "p++" below the while() loop) is
! 1279: ** normally all that is required to move pointer p to the desired
! 1280: ** position. The exception is if this node is being loaded from disk
! 1281: ** incrementally and pointer "p" now points to the first byte passed
! 1282: ** the populated part of pReader->aNode[].
! 1283: */
! 1284: while( *p | c ) c = *p++ & 0x80;
! 1285: assert( *p==0 );
! 1286:
! 1287: if( pReader->pBlob==0 || p<&pReader->aNode[pReader->nPopulate] ) break;
! 1288: rc = fts3SegReaderIncrRead(pReader);
! 1289: if( rc!=SQLITE_OK ) return rc;
! 1290: }
! 1291: p++;
! 1292:
! 1293: /* If required, populate the output variables with a pointer to and the
! 1294: ** size of the previous offset-list.
! 1295: */
! 1296: if( ppOffsetList ){
! 1297: *ppOffsetList = pReader->pOffsetList;
! 1298: *pnOffsetList = (int)(p - pReader->pOffsetList - 1);
! 1299: }
! 1300:
! 1301: while( p<pEnd && *p==0 ) p++;
! 1302:
! 1303: /* If there are no more entries in the doclist, set pOffsetList to
! 1304: ** NULL. Otherwise, set Fts3SegReader.iDocid to the next docid and
! 1305: ** Fts3SegReader.pOffsetList to point to the next offset list before
! 1306: ** returning.
! 1307: */
! 1308: if( p>=pEnd ){
! 1309: pReader->pOffsetList = 0;
! 1310: }else{
! 1311: rc = fts3SegReaderRequire(pReader, p, FTS3_VARINT_MAX);
! 1312: if( rc==SQLITE_OK ){
! 1313: sqlite3_int64 iDelta;
! 1314: pReader->pOffsetList = p + sqlite3Fts3GetVarint(p, &iDelta);
! 1315: if( pTab->bDescIdx ){
! 1316: pReader->iDocid -= iDelta;
! 1317: }else{
! 1318: pReader->iDocid += iDelta;
! 1319: }
! 1320: }
! 1321: }
! 1322: }
! 1323:
! 1324: return SQLITE_OK;
! 1325: }
! 1326:
! 1327:
! 1328: int sqlite3Fts3MsrOvfl(
! 1329: Fts3Cursor *pCsr,
! 1330: Fts3MultiSegReader *pMsr,
! 1331: int *pnOvfl
! 1332: ){
! 1333: Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
! 1334: int nOvfl = 0;
! 1335: int ii;
! 1336: int rc = SQLITE_OK;
! 1337: int pgsz = p->nPgsz;
! 1338:
! 1339: assert( p->bHasStat );
! 1340: assert( pgsz>0 );
! 1341:
! 1342: for(ii=0; rc==SQLITE_OK && ii<pMsr->nSegment; ii++){
! 1343: Fts3SegReader *pReader = pMsr->apSegment[ii];
! 1344: if( !fts3SegReaderIsPending(pReader)
! 1345: && !fts3SegReaderIsRootOnly(pReader)
! 1346: ){
! 1347: sqlite3_int64 jj;
! 1348: for(jj=pReader->iStartBlock; jj<=pReader->iLeafEndBlock; jj++){
! 1349: int nBlob;
! 1350: rc = sqlite3Fts3ReadBlock(p, jj, 0, &nBlob, 0);
! 1351: if( rc!=SQLITE_OK ) break;
! 1352: if( (nBlob+35)>pgsz ){
! 1353: nOvfl += (nBlob + 34)/pgsz;
! 1354: }
! 1355: }
! 1356: }
! 1357: }
! 1358: *pnOvfl = nOvfl;
! 1359: return rc;
! 1360: }
! 1361:
! 1362: /*
! 1363: ** Free all allocations associated with the iterator passed as the
! 1364: ** second argument.
! 1365: */
! 1366: void sqlite3Fts3SegReaderFree(Fts3SegReader *pReader){
! 1367: if( pReader && !fts3SegReaderIsPending(pReader) ){
! 1368: sqlite3_free(pReader->zTerm);
! 1369: if( !fts3SegReaderIsRootOnly(pReader) ){
! 1370: sqlite3_free(pReader->aNode);
! 1371: sqlite3_blob_close(pReader->pBlob);
! 1372: }
! 1373: }
! 1374: sqlite3_free(pReader);
! 1375: }
! 1376:
! 1377: /*
! 1378: ** Allocate a new SegReader object.
! 1379: */
! 1380: int sqlite3Fts3SegReaderNew(
! 1381: int iAge, /* Segment "age". */
! 1382: sqlite3_int64 iStartLeaf, /* First leaf to traverse */
! 1383: sqlite3_int64 iEndLeaf, /* Final leaf to traverse */
! 1384: sqlite3_int64 iEndBlock, /* Final block of segment */
! 1385: const char *zRoot, /* Buffer containing root node */
! 1386: int nRoot, /* Size of buffer containing root node */
! 1387: Fts3SegReader **ppReader /* OUT: Allocated Fts3SegReader */
! 1388: ){
! 1389: Fts3SegReader *pReader; /* Newly allocated SegReader object */
! 1390: int nExtra = 0; /* Bytes to allocate segment root node */
! 1391:
! 1392: assert( iStartLeaf<=iEndLeaf );
! 1393: if( iStartLeaf==0 ){
! 1394: nExtra = nRoot + FTS3_NODE_PADDING;
! 1395: }
! 1396:
! 1397: pReader = (Fts3SegReader *)sqlite3_malloc(sizeof(Fts3SegReader) + nExtra);
! 1398: if( !pReader ){
! 1399: return SQLITE_NOMEM;
! 1400: }
! 1401: memset(pReader, 0, sizeof(Fts3SegReader));
! 1402: pReader->iIdx = iAge;
! 1403: pReader->iStartBlock = iStartLeaf;
! 1404: pReader->iLeafEndBlock = iEndLeaf;
! 1405: pReader->iEndBlock = iEndBlock;
! 1406:
! 1407: if( nExtra ){
! 1408: /* The entire segment is stored in the root node. */
! 1409: pReader->aNode = (char *)&pReader[1];
! 1410: pReader->nNode = nRoot;
! 1411: memcpy(pReader->aNode, zRoot, nRoot);
! 1412: memset(&pReader->aNode[nRoot], 0, FTS3_NODE_PADDING);
! 1413: }else{
! 1414: pReader->iCurrentBlock = iStartLeaf-1;
! 1415: }
! 1416: *ppReader = pReader;
! 1417: return SQLITE_OK;
! 1418: }
! 1419:
! 1420: /*
! 1421: ** This is a comparison function used as a qsort() callback when sorting
! 1422: ** an array of pending terms by term. This occurs as part of flushing
! 1423: ** the contents of the pending-terms hash table to the database.
! 1424: */
! 1425: static int fts3CompareElemByTerm(const void *lhs, const void *rhs){
! 1426: char *z1 = fts3HashKey(*(Fts3HashElem **)lhs);
! 1427: char *z2 = fts3HashKey(*(Fts3HashElem **)rhs);
! 1428: int n1 = fts3HashKeysize(*(Fts3HashElem **)lhs);
! 1429: int n2 = fts3HashKeysize(*(Fts3HashElem **)rhs);
! 1430:
! 1431: int n = (n1<n2 ? n1 : n2);
! 1432: int c = memcmp(z1, z2, n);
! 1433: if( c==0 ){
! 1434: c = n1 - n2;
! 1435: }
! 1436: return c;
! 1437: }
! 1438:
! 1439: /*
! 1440: ** This function is used to allocate an Fts3SegReader that iterates through
! 1441: ** a subset of the terms stored in the Fts3Table.pendingTerms array.
! 1442: **
! 1443: ** If the isPrefixIter parameter is zero, then the returned SegReader iterates
! 1444: ** through each term in the pending-terms table. Or, if isPrefixIter is
! 1445: ** non-zero, it iterates through each term and its prefixes. For example, if
! 1446: ** the pending terms hash table contains the terms "sqlite", "mysql" and
! 1447: ** "firebird", then the iterator visits the following 'terms' (in the order
! 1448: ** shown):
! 1449: **
! 1450: ** f fi fir fire fireb firebi firebir firebird
! 1451: ** m my mys mysq mysql
! 1452: ** s sq sql sqli sqlit sqlite
! 1453: **
! 1454: ** Whereas if isPrefixIter is zero, the terms visited are:
! 1455: **
! 1456: ** firebird mysql sqlite
! 1457: */
! 1458: int sqlite3Fts3SegReaderPending(
! 1459: Fts3Table *p, /* Virtual table handle */
! 1460: int iIndex, /* Index for p->aIndex */
! 1461: const char *zTerm, /* Term to search for */
! 1462: int nTerm, /* Size of buffer zTerm */
! 1463: int bPrefix, /* True for a prefix iterator */
! 1464: Fts3SegReader **ppReader /* OUT: SegReader for pending-terms */
! 1465: ){
! 1466: Fts3SegReader *pReader = 0; /* Fts3SegReader object to return */
! 1467: Fts3HashElem *pE; /* Iterator variable */
! 1468: Fts3HashElem **aElem = 0; /* Array of term hash entries to scan */
! 1469: int nElem = 0; /* Size of array at aElem */
! 1470: int rc = SQLITE_OK; /* Return Code */
! 1471: Fts3Hash *pHash;
! 1472:
! 1473: pHash = &p->aIndex[iIndex].hPending;
! 1474: if( bPrefix ){
! 1475: int nAlloc = 0; /* Size of allocated array at aElem */
! 1476:
! 1477: for(pE=fts3HashFirst(pHash); pE; pE=fts3HashNext(pE)){
! 1478: char *zKey = (char *)fts3HashKey(pE);
! 1479: int nKey = fts3HashKeysize(pE);
! 1480: if( nTerm==0 || (nKey>=nTerm && 0==memcmp(zKey, zTerm, nTerm)) ){
! 1481: if( nElem==nAlloc ){
! 1482: Fts3HashElem **aElem2;
! 1483: nAlloc += 16;
! 1484: aElem2 = (Fts3HashElem **)sqlite3_realloc(
! 1485: aElem, nAlloc*sizeof(Fts3HashElem *)
! 1486: );
! 1487: if( !aElem2 ){
! 1488: rc = SQLITE_NOMEM;
! 1489: nElem = 0;
! 1490: break;
! 1491: }
! 1492: aElem = aElem2;
! 1493: }
! 1494:
! 1495: aElem[nElem++] = pE;
! 1496: }
! 1497: }
! 1498:
! 1499: /* If more than one term matches the prefix, sort the Fts3HashElem
! 1500: ** objects in term order using qsort(). This uses the same comparison
! 1501: ** callback as is used when flushing terms to disk.
! 1502: */
! 1503: if( nElem>1 ){
! 1504: qsort(aElem, nElem, sizeof(Fts3HashElem *), fts3CompareElemByTerm);
! 1505: }
! 1506:
! 1507: }else{
! 1508: /* The query is a simple term lookup that matches at most one term in
! 1509: ** the index. All that is required is a straight hash-lookup.
! 1510: **
! 1511: ** Because the stack address of pE may be accessed via the aElem pointer
! 1512: ** below, the "Fts3HashElem *pE" must be declared so that it is valid
! 1513: ** within this entire function, not just this "else{...}" block.
! 1514: */
! 1515: pE = fts3HashFindElem(pHash, zTerm, nTerm);
! 1516: if( pE ){
! 1517: aElem = &pE;
! 1518: nElem = 1;
! 1519: }
! 1520: }
! 1521:
! 1522: if( nElem>0 ){
! 1523: int nByte = sizeof(Fts3SegReader) + (nElem+1)*sizeof(Fts3HashElem *);
! 1524: pReader = (Fts3SegReader *)sqlite3_malloc(nByte);
! 1525: if( !pReader ){
! 1526: rc = SQLITE_NOMEM;
! 1527: }else{
! 1528: memset(pReader, 0, nByte);
! 1529: pReader->iIdx = 0x7FFFFFFF;
! 1530: pReader->ppNextElem = (Fts3HashElem **)&pReader[1];
! 1531: memcpy(pReader->ppNextElem, aElem, nElem*sizeof(Fts3HashElem *));
! 1532: }
! 1533: }
! 1534:
! 1535: if( bPrefix ){
! 1536: sqlite3_free(aElem);
! 1537: }
! 1538: *ppReader = pReader;
! 1539: return rc;
! 1540: }
! 1541:
! 1542: /*
! 1543: ** Compare the entries pointed to by two Fts3SegReader structures.
! 1544: ** Comparison is as follows:
! 1545: **
! 1546: ** 1) EOF is greater than not EOF.
! 1547: **
! 1548: ** 2) The current terms (if any) are compared using memcmp(). If one
! 1549: ** term is a prefix of another, the longer term is considered the
! 1550: ** larger.
! 1551: **
! 1552: ** 3) By segment age. An older segment is considered larger.
! 1553: */
! 1554: static int fts3SegReaderCmp(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
! 1555: int rc;
! 1556: if( pLhs->aNode && pRhs->aNode ){
! 1557: int rc2 = pLhs->nTerm - pRhs->nTerm;
! 1558: if( rc2<0 ){
! 1559: rc = memcmp(pLhs->zTerm, pRhs->zTerm, pLhs->nTerm);
! 1560: }else{
! 1561: rc = memcmp(pLhs->zTerm, pRhs->zTerm, pRhs->nTerm);
! 1562: }
! 1563: if( rc==0 ){
! 1564: rc = rc2;
! 1565: }
! 1566: }else{
! 1567: rc = (pLhs->aNode==0) - (pRhs->aNode==0);
! 1568: }
! 1569: if( rc==0 ){
! 1570: rc = pRhs->iIdx - pLhs->iIdx;
! 1571: }
! 1572: assert( rc!=0 );
! 1573: return rc;
! 1574: }
! 1575:
! 1576: /*
! 1577: ** A different comparison function for SegReader structures. In this
! 1578: ** version, it is assumed that each SegReader points to an entry in
! 1579: ** a doclist for identical terms. Comparison is made as follows:
! 1580: **
! 1581: ** 1) EOF (end of doclist in this case) is greater than not EOF.
! 1582: **
! 1583: ** 2) By current docid.
! 1584: **
! 1585: ** 3) By segment age. An older segment is considered larger.
! 1586: */
! 1587: static int fts3SegReaderDoclistCmp(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
! 1588: int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);
! 1589: if( rc==0 ){
! 1590: if( pLhs->iDocid==pRhs->iDocid ){
! 1591: rc = pRhs->iIdx - pLhs->iIdx;
! 1592: }else{
! 1593: rc = (pLhs->iDocid > pRhs->iDocid) ? 1 : -1;
! 1594: }
! 1595: }
! 1596: assert( pLhs->aNode && pRhs->aNode );
! 1597: return rc;
! 1598: }
! 1599: static int fts3SegReaderDoclistCmpRev(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
! 1600: int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);
! 1601: if( rc==0 ){
! 1602: if( pLhs->iDocid==pRhs->iDocid ){
! 1603: rc = pRhs->iIdx - pLhs->iIdx;
! 1604: }else{
! 1605: rc = (pLhs->iDocid < pRhs->iDocid) ? 1 : -1;
! 1606: }
! 1607: }
! 1608: assert( pLhs->aNode && pRhs->aNode );
! 1609: return rc;
! 1610: }
! 1611:
! 1612: /*
! 1613: ** Compare the term that the Fts3SegReader object passed as the first argument
! 1614: ** points to with the term specified by arguments zTerm and nTerm.
! 1615: **
! 1616: ** If the pSeg iterator is already at EOF, return 0. Otherwise, return
! 1617: ** -ve if the pSeg term is less than zTerm/nTerm, 0 if the two terms are
! 1618: ** equal, or +ve if the pSeg term is greater than zTerm/nTerm.
! 1619: */
! 1620: static int fts3SegReaderTermCmp(
! 1621: Fts3SegReader *pSeg, /* Segment reader object */
! 1622: const char *zTerm, /* Term to compare to */
! 1623: int nTerm /* Size of term zTerm in bytes */
! 1624: ){
! 1625: int res = 0;
! 1626: if( pSeg->aNode ){
! 1627: if( pSeg->nTerm>nTerm ){
! 1628: res = memcmp(pSeg->zTerm, zTerm, nTerm);
! 1629: }else{
! 1630: res = memcmp(pSeg->zTerm, zTerm, pSeg->nTerm);
! 1631: }
! 1632: if( res==0 ){
! 1633: res = pSeg->nTerm-nTerm;
! 1634: }
! 1635: }
! 1636: return res;
! 1637: }
! 1638:
! 1639: /*
! 1640: ** Argument apSegment is an array of nSegment elements. It is known that
! 1641: ** the final (nSegment-nSuspect) members are already in sorted order
! 1642: ** (according to the comparison function provided). This function shuffles
! 1643: ** the array around until all entries are in sorted order.
! 1644: */
! 1645: static void fts3SegReaderSort(
! 1646: Fts3SegReader **apSegment, /* Array to sort entries of */
! 1647: int nSegment, /* Size of apSegment array */
! 1648: int nSuspect, /* Unsorted entry count */
! 1649: int (*xCmp)(Fts3SegReader *, Fts3SegReader *) /* Comparison function */
! 1650: ){
! 1651: int i; /* Iterator variable */
! 1652:
! 1653: assert( nSuspect<=nSegment );
! 1654:
! 1655: if( nSuspect==nSegment ) nSuspect--;
! 1656: for(i=nSuspect-1; i>=0; i--){
! 1657: int j;
! 1658: for(j=i; j<(nSegment-1); j++){
! 1659: Fts3SegReader *pTmp;
! 1660: if( xCmp(apSegment[j], apSegment[j+1])<0 ) break;
! 1661: pTmp = apSegment[j+1];
! 1662: apSegment[j+1] = apSegment[j];
! 1663: apSegment[j] = pTmp;
! 1664: }
! 1665: }
! 1666:
! 1667: #ifndef NDEBUG
! 1668: /* Check that the list really is sorted now. */
! 1669: for(i=0; i<(nSuspect-1); i++){
! 1670: assert( xCmp(apSegment[i], apSegment[i+1])<0 );
! 1671: }
! 1672: #endif
! 1673: }
! 1674:
! 1675: /*
! 1676: ** Insert a record into the %_segments table.
! 1677: */
! 1678: static int fts3WriteSegment(
! 1679: Fts3Table *p, /* Virtual table handle */
! 1680: sqlite3_int64 iBlock, /* Block id for new block */
! 1681: char *z, /* Pointer to buffer containing block data */
! 1682: int n /* Size of buffer z in bytes */
! 1683: ){
! 1684: sqlite3_stmt *pStmt;
! 1685: int rc = fts3SqlStmt(p, SQL_INSERT_SEGMENTS, &pStmt, 0);
! 1686: if( rc==SQLITE_OK ){
! 1687: sqlite3_bind_int64(pStmt, 1, iBlock);
! 1688: sqlite3_bind_blob(pStmt, 2, z, n, SQLITE_STATIC);
! 1689: sqlite3_step(pStmt);
! 1690: rc = sqlite3_reset(pStmt);
! 1691: }
! 1692: return rc;
! 1693: }
! 1694:
! 1695: /*
! 1696: ** Insert a record into the %_segdir table.
! 1697: */
! 1698: static int fts3WriteSegdir(
! 1699: Fts3Table *p, /* Virtual table handle */
! 1700: int iLevel, /* Value for "level" field */
! 1701: int iIdx, /* Value for "idx" field */
! 1702: sqlite3_int64 iStartBlock, /* Value for "start_block" field */
! 1703: sqlite3_int64 iLeafEndBlock, /* Value for "leaves_end_block" field */
! 1704: sqlite3_int64 iEndBlock, /* Value for "end_block" field */
! 1705: char *zRoot, /* Blob value for "root" field */
! 1706: int nRoot /* Number of bytes in buffer zRoot */
! 1707: ){
! 1708: sqlite3_stmt *pStmt;
! 1709: int rc = fts3SqlStmt(p, SQL_INSERT_SEGDIR, &pStmt, 0);
! 1710: if( rc==SQLITE_OK ){
! 1711: sqlite3_bind_int(pStmt, 1, iLevel);
! 1712: sqlite3_bind_int(pStmt, 2, iIdx);
! 1713: sqlite3_bind_int64(pStmt, 3, iStartBlock);
! 1714: sqlite3_bind_int64(pStmt, 4, iLeafEndBlock);
! 1715: sqlite3_bind_int64(pStmt, 5, iEndBlock);
! 1716: sqlite3_bind_blob(pStmt, 6, zRoot, nRoot, SQLITE_STATIC);
! 1717: sqlite3_step(pStmt);
! 1718: rc = sqlite3_reset(pStmt);
! 1719: }
! 1720: return rc;
! 1721: }
! 1722:
! 1723: /*
! 1724: ** Return the size of the common prefix (if any) shared by zPrev and
! 1725: ** zNext, in bytes. For example,
! 1726: **
! 1727: ** fts3PrefixCompress("abc", 3, "abcdef", 6) // returns 3
! 1728: ** fts3PrefixCompress("abX", 3, "abcdef", 6) // returns 2
! 1729: ** fts3PrefixCompress("abX", 3, "Xbcdef", 6) // returns 0
! 1730: */
! 1731: static int fts3PrefixCompress(
! 1732: const char *zPrev, /* Buffer containing previous term */
! 1733: int nPrev, /* Size of buffer zPrev in bytes */
! 1734: const char *zNext, /* Buffer containing next term */
! 1735: int nNext /* Size of buffer zNext in bytes */
! 1736: ){
! 1737: int n;
! 1738: UNUSED_PARAMETER(nNext);
! 1739: for(n=0; n<nPrev && zPrev[n]==zNext[n]; n++);
! 1740: return n;
! 1741: }
! 1742:
! 1743: /*
! 1744: ** Add term zTerm to the SegmentNode. It is guaranteed that zTerm is larger
! 1745: ** (according to memcmp) than the previous term.
! 1746: */
! 1747: static int fts3NodeAddTerm(
! 1748: Fts3Table *p, /* Virtual table handle */
! 1749: SegmentNode **ppTree, /* IN/OUT: SegmentNode handle */
! 1750: int isCopyTerm, /* True if zTerm/nTerm is transient */
! 1751: const char *zTerm, /* Pointer to buffer containing term */
! 1752: int nTerm /* Size of term in bytes */
! 1753: ){
! 1754: SegmentNode *pTree = *ppTree;
! 1755: int rc;
! 1756: SegmentNode *pNew;
! 1757:
! 1758: /* First try to append the term to the current node. Return early if
! 1759: ** this is possible.
! 1760: */
! 1761: if( pTree ){
! 1762: int nData = pTree->nData; /* Current size of node in bytes */
! 1763: int nReq = nData; /* Required space after adding zTerm */
! 1764: int nPrefix; /* Number of bytes of prefix compression */
! 1765: int nSuffix; /* Suffix length */
! 1766:
! 1767: nPrefix = fts3PrefixCompress(pTree->zTerm, pTree->nTerm, zTerm, nTerm);
! 1768: nSuffix = nTerm-nPrefix;
! 1769:
! 1770: nReq += sqlite3Fts3VarintLen(nPrefix)+sqlite3Fts3VarintLen(nSuffix)+nSuffix;
! 1771: if( nReq<=p->nNodeSize || !pTree->zTerm ){
! 1772:
! 1773: if( nReq>p->nNodeSize ){
! 1774: /* An unusual case: this is the first term to be added to the node
! 1775: ** and the static node buffer (p->nNodeSize bytes) is not large
! 1776: ** enough. Use a separately malloced buffer instead This wastes
! 1777: ** p->nNodeSize bytes, but since this scenario only comes about when
! 1778: ** the database contain two terms that share a prefix of almost 2KB,
! 1779: ** this is not expected to be a serious problem.
! 1780: */
! 1781: assert( pTree->aData==(char *)&pTree[1] );
! 1782: pTree->aData = (char *)sqlite3_malloc(nReq);
! 1783: if( !pTree->aData ){
! 1784: return SQLITE_NOMEM;
! 1785: }
! 1786: }
! 1787:
! 1788: if( pTree->zTerm ){
! 1789: /* There is no prefix-length field for first term in a node */
! 1790: nData += sqlite3Fts3PutVarint(&pTree->aData[nData], nPrefix);
! 1791: }
! 1792:
! 1793: nData += sqlite3Fts3PutVarint(&pTree->aData[nData], nSuffix);
! 1794: memcpy(&pTree->aData[nData], &zTerm[nPrefix], nSuffix);
! 1795: pTree->nData = nData + nSuffix;
! 1796: pTree->nEntry++;
! 1797:
! 1798: if( isCopyTerm ){
! 1799: if( pTree->nMalloc<nTerm ){
! 1800: char *zNew = sqlite3_realloc(pTree->zMalloc, nTerm*2);
! 1801: if( !zNew ){
! 1802: return SQLITE_NOMEM;
! 1803: }
! 1804: pTree->nMalloc = nTerm*2;
! 1805: pTree->zMalloc = zNew;
! 1806: }
! 1807: pTree->zTerm = pTree->zMalloc;
! 1808: memcpy(pTree->zTerm, zTerm, nTerm);
! 1809: pTree->nTerm = nTerm;
! 1810: }else{
! 1811: pTree->zTerm = (char *)zTerm;
! 1812: pTree->nTerm = nTerm;
! 1813: }
! 1814: return SQLITE_OK;
! 1815: }
! 1816: }
! 1817:
! 1818: /* If control flows to here, it was not possible to append zTerm to the
! 1819: ** current node. Create a new node (a right-sibling of the current node).
! 1820: ** If this is the first node in the tree, the term is added to it.
! 1821: **
! 1822: ** Otherwise, the term is not added to the new node, it is left empty for
! 1823: ** now. Instead, the term is inserted into the parent of pTree. If pTree
! 1824: ** has no parent, one is created here.
! 1825: */
! 1826: pNew = (SegmentNode *)sqlite3_malloc(sizeof(SegmentNode) + p->nNodeSize);
! 1827: if( !pNew ){
! 1828: return SQLITE_NOMEM;
! 1829: }
! 1830: memset(pNew, 0, sizeof(SegmentNode));
! 1831: pNew->nData = 1 + FTS3_VARINT_MAX;
! 1832: pNew->aData = (char *)&pNew[1];
! 1833:
! 1834: if( pTree ){
! 1835: SegmentNode *pParent = pTree->pParent;
! 1836: rc = fts3NodeAddTerm(p, &pParent, isCopyTerm, zTerm, nTerm);
! 1837: if( pTree->pParent==0 ){
! 1838: pTree->pParent = pParent;
! 1839: }
! 1840: pTree->pRight = pNew;
! 1841: pNew->pLeftmost = pTree->pLeftmost;
! 1842: pNew->pParent = pParent;
! 1843: pNew->zMalloc = pTree->zMalloc;
! 1844: pNew->nMalloc = pTree->nMalloc;
! 1845: pTree->zMalloc = 0;
! 1846: }else{
! 1847: pNew->pLeftmost = pNew;
! 1848: rc = fts3NodeAddTerm(p, &pNew, isCopyTerm, zTerm, nTerm);
! 1849: }
! 1850:
! 1851: *ppTree = pNew;
! 1852: return rc;
! 1853: }
! 1854:
! 1855: /*
! 1856: ** Helper function for fts3NodeWrite().
! 1857: */
! 1858: static int fts3TreeFinishNode(
! 1859: SegmentNode *pTree,
! 1860: int iHeight,
! 1861: sqlite3_int64 iLeftChild
! 1862: ){
! 1863: int nStart;
! 1864: assert( iHeight>=1 && iHeight<128 );
! 1865: nStart = FTS3_VARINT_MAX - sqlite3Fts3VarintLen(iLeftChild);
! 1866: pTree->aData[nStart] = (char)iHeight;
! 1867: sqlite3Fts3PutVarint(&pTree->aData[nStart+1], iLeftChild);
! 1868: return nStart;
! 1869: }
! 1870:
! 1871: /*
! 1872: ** Write the buffer for the segment node pTree and all of its peers to the
! 1873: ** database. Then call this function recursively to write the parent of
! 1874: ** pTree and its peers to the database.
! 1875: **
! 1876: ** Except, if pTree is a root node, do not write it to the database. Instead,
! 1877: ** set output variables *paRoot and *pnRoot to contain the root node.
! 1878: **
! 1879: ** If successful, SQLITE_OK is returned and output variable *piLast is
! 1880: ** set to the largest blockid written to the database (or zero if no
! 1881: ** blocks were written to the db). Otherwise, an SQLite error code is
! 1882: ** returned.
! 1883: */
! 1884: static int fts3NodeWrite(
! 1885: Fts3Table *p, /* Virtual table handle */
! 1886: SegmentNode *pTree, /* SegmentNode handle */
! 1887: int iHeight, /* Height of this node in tree */
! 1888: sqlite3_int64 iLeaf, /* Block id of first leaf node */
! 1889: sqlite3_int64 iFree, /* Block id of next free slot in %_segments */
! 1890: sqlite3_int64 *piLast, /* OUT: Block id of last entry written */
! 1891: char **paRoot, /* OUT: Data for root node */
! 1892: int *pnRoot /* OUT: Size of root node in bytes */
! 1893: ){
! 1894: int rc = SQLITE_OK;
! 1895:
! 1896: if( !pTree->pParent ){
! 1897: /* Root node of the tree. */
! 1898: int nStart = fts3TreeFinishNode(pTree, iHeight, iLeaf);
! 1899: *piLast = iFree-1;
! 1900: *pnRoot = pTree->nData - nStart;
! 1901: *paRoot = &pTree->aData[nStart];
! 1902: }else{
! 1903: SegmentNode *pIter;
! 1904: sqlite3_int64 iNextFree = iFree;
! 1905: sqlite3_int64 iNextLeaf = iLeaf;
! 1906: for(pIter=pTree->pLeftmost; pIter && rc==SQLITE_OK; pIter=pIter->pRight){
! 1907: int nStart = fts3TreeFinishNode(pIter, iHeight, iNextLeaf);
! 1908: int nWrite = pIter->nData - nStart;
! 1909:
! 1910: rc = fts3WriteSegment(p, iNextFree, &pIter->aData[nStart], nWrite);
! 1911: iNextFree++;
! 1912: iNextLeaf += (pIter->nEntry+1);
! 1913: }
! 1914: if( rc==SQLITE_OK ){
! 1915: assert( iNextLeaf==iFree );
! 1916: rc = fts3NodeWrite(
! 1917: p, pTree->pParent, iHeight+1, iFree, iNextFree, piLast, paRoot, pnRoot
! 1918: );
! 1919: }
! 1920: }
! 1921:
! 1922: return rc;
! 1923: }
! 1924:
! 1925: /*
! 1926: ** Free all memory allocations associated with the tree pTree.
! 1927: */
! 1928: static void fts3NodeFree(SegmentNode *pTree){
! 1929: if( pTree ){
! 1930: SegmentNode *p = pTree->pLeftmost;
! 1931: fts3NodeFree(p->pParent);
! 1932: while( p ){
! 1933: SegmentNode *pRight = p->pRight;
! 1934: if( p->aData!=(char *)&p[1] ){
! 1935: sqlite3_free(p->aData);
! 1936: }
! 1937: assert( pRight==0 || p->zMalloc==0 );
! 1938: sqlite3_free(p->zMalloc);
! 1939: sqlite3_free(p);
! 1940: p = pRight;
! 1941: }
! 1942: }
! 1943: }
! 1944:
! 1945: /*
! 1946: ** Add a term to the segment being constructed by the SegmentWriter object
! 1947: ** *ppWriter. When adding the first term to a segment, *ppWriter should
! 1948: ** be passed NULL. This function will allocate a new SegmentWriter object
! 1949: ** and return it via the input/output variable *ppWriter in this case.
! 1950: **
! 1951: ** If successful, SQLITE_OK is returned. Otherwise, an SQLite error code.
! 1952: */
! 1953: static int fts3SegWriterAdd(
! 1954: Fts3Table *p, /* Virtual table handle */
! 1955: SegmentWriter **ppWriter, /* IN/OUT: SegmentWriter handle */
! 1956: int isCopyTerm, /* True if buffer zTerm must be copied */
! 1957: const char *zTerm, /* Pointer to buffer containing term */
! 1958: int nTerm, /* Size of term in bytes */
! 1959: const char *aDoclist, /* Pointer to buffer containing doclist */
! 1960: int nDoclist /* Size of doclist in bytes */
! 1961: ){
! 1962: int nPrefix; /* Size of term prefix in bytes */
! 1963: int nSuffix; /* Size of term suffix in bytes */
! 1964: int nReq; /* Number of bytes required on leaf page */
! 1965: int nData;
! 1966: SegmentWriter *pWriter = *ppWriter;
! 1967:
! 1968: if( !pWriter ){
! 1969: int rc;
! 1970: sqlite3_stmt *pStmt;
! 1971:
! 1972: /* Allocate the SegmentWriter structure */
! 1973: pWriter = (SegmentWriter *)sqlite3_malloc(sizeof(SegmentWriter));
! 1974: if( !pWriter ) return SQLITE_NOMEM;
! 1975: memset(pWriter, 0, sizeof(SegmentWriter));
! 1976: *ppWriter = pWriter;
! 1977:
! 1978: /* Allocate a buffer in which to accumulate data */
! 1979: pWriter->aData = (char *)sqlite3_malloc(p->nNodeSize);
! 1980: if( !pWriter->aData ) return SQLITE_NOMEM;
! 1981: pWriter->nSize = p->nNodeSize;
! 1982:
! 1983: /* Find the next free blockid in the %_segments table */
! 1984: rc = fts3SqlStmt(p, SQL_NEXT_SEGMENTS_ID, &pStmt, 0);
! 1985: if( rc!=SQLITE_OK ) return rc;
! 1986: if( SQLITE_ROW==sqlite3_step(pStmt) ){
! 1987: pWriter->iFree = sqlite3_column_int64(pStmt, 0);
! 1988: pWriter->iFirst = pWriter->iFree;
! 1989: }
! 1990: rc = sqlite3_reset(pStmt);
! 1991: if( rc!=SQLITE_OK ) return rc;
! 1992: }
! 1993: nData = pWriter->nData;
! 1994:
! 1995: nPrefix = fts3PrefixCompress(pWriter->zTerm, pWriter->nTerm, zTerm, nTerm);
! 1996: nSuffix = nTerm-nPrefix;
! 1997:
! 1998: /* Figure out how many bytes are required by this new entry */
! 1999: nReq = sqlite3Fts3VarintLen(nPrefix) + /* varint containing prefix size */
! 2000: sqlite3Fts3VarintLen(nSuffix) + /* varint containing suffix size */
! 2001: nSuffix + /* Term suffix */
! 2002: sqlite3Fts3VarintLen(nDoclist) + /* Size of doclist */
! 2003: nDoclist; /* Doclist data */
! 2004:
! 2005: if( nData>0 && nData+nReq>p->nNodeSize ){
! 2006: int rc;
! 2007:
! 2008: /* The current leaf node is full. Write it out to the database. */
! 2009: rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, nData);
! 2010: if( rc!=SQLITE_OK ) return rc;
! 2011:
! 2012: /* Add the current term to the interior node tree. The term added to
! 2013: ** the interior tree must:
! 2014: **
! 2015: ** a) be greater than the largest term on the leaf node just written
! 2016: ** to the database (still available in pWriter->zTerm), and
! 2017: **
! 2018: ** b) be less than or equal to the term about to be added to the new
! 2019: ** leaf node (zTerm/nTerm).
! 2020: **
! 2021: ** In other words, it must be the prefix of zTerm 1 byte longer than
! 2022: ** the common prefix (if any) of zTerm and pWriter->zTerm.
! 2023: */
! 2024: assert( nPrefix<nTerm );
! 2025: rc = fts3NodeAddTerm(p, &pWriter->pTree, isCopyTerm, zTerm, nPrefix+1);
! 2026: if( rc!=SQLITE_OK ) return rc;
! 2027:
! 2028: nData = 0;
! 2029: pWriter->nTerm = 0;
! 2030:
! 2031: nPrefix = 0;
! 2032: nSuffix = nTerm;
! 2033: nReq = 1 + /* varint containing prefix size */
! 2034: sqlite3Fts3VarintLen(nTerm) + /* varint containing suffix size */
! 2035: nTerm + /* Term suffix */
! 2036: sqlite3Fts3VarintLen(nDoclist) + /* Size of doclist */
! 2037: nDoclist; /* Doclist data */
! 2038: }
! 2039:
! 2040: /* If the buffer currently allocated is too small for this entry, realloc
! 2041: ** the buffer to make it large enough.
! 2042: */
! 2043: if( nReq>pWriter->nSize ){
! 2044: char *aNew = sqlite3_realloc(pWriter->aData, nReq);
! 2045: if( !aNew ) return SQLITE_NOMEM;
! 2046: pWriter->aData = aNew;
! 2047: pWriter->nSize = nReq;
! 2048: }
! 2049: assert( nData+nReq<=pWriter->nSize );
! 2050:
! 2051: /* Append the prefix-compressed term and doclist to the buffer. */
! 2052: nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nPrefix);
! 2053: nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nSuffix);
! 2054: memcpy(&pWriter->aData[nData], &zTerm[nPrefix], nSuffix);
! 2055: nData += nSuffix;
! 2056: nData += sqlite3Fts3PutVarint(&pWriter->aData[nData], nDoclist);
! 2057: memcpy(&pWriter->aData[nData], aDoclist, nDoclist);
! 2058: pWriter->nData = nData + nDoclist;
! 2059:
! 2060: /* Save the current term so that it can be used to prefix-compress the next.
! 2061: ** If the isCopyTerm parameter is true, then the buffer pointed to by
! 2062: ** zTerm is transient, so take a copy of the term data. Otherwise, just
! 2063: ** store a copy of the pointer.
! 2064: */
! 2065: if( isCopyTerm ){
! 2066: if( nTerm>pWriter->nMalloc ){
! 2067: char *zNew = sqlite3_realloc(pWriter->zMalloc, nTerm*2);
! 2068: if( !zNew ){
! 2069: return SQLITE_NOMEM;
! 2070: }
! 2071: pWriter->nMalloc = nTerm*2;
! 2072: pWriter->zMalloc = zNew;
! 2073: pWriter->zTerm = zNew;
! 2074: }
! 2075: assert( pWriter->zTerm==pWriter->zMalloc );
! 2076: memcpy(pWriter->zTerm, zTerm, nTerm);
! 2077: }else{
! 2078: pWriter->zTerm = (char *)zTerm;
! 2079: }
! 2080: pWriter->nTerm = nTerm;
! 2081:
! 2082: return SQLITE_OK;
! 2083: }
! 2084:
! 2085: /*
! 2086: ** Flush all data associated with the SegmentWriter object pWriter to the
! 2087: ** database. This function must be called after all terms have been added
! 2088: ** to the segment using fts3SegWriterAdd(). If successful, SQLITE_OK is
! 2089: ** returned. Otherwise, an SQLite error code.
! 2090: */
! 2091: static int fts3SegWriterFlush(
! 2092: Fts3Table *p, /* Virtual table handle */
! 2093: SegmentWriter *pWriter, /* SegmentWriter to flush to the db */
! 2094: int iLevel, /* Value for 'level' column of %_segdir */
! 2095: int iIdx /* Value for 'idx' column of %_segdir */
! 2096: ){
! 2097: int rc; /* Return code */
! 2098: if( pWriter->pTree ){
! 2099: sqlite3_int64 iLast = 0; /* Largest block id written to database */
! 2100: sqlite3_int64 iLastLeaf; /* Largest leaf block id written to db */
! 2101: char *zRoot = NULL; /* Pointer to buffer containing root node */
! 2102: int nRoot = 0; /* Size of buffer zRoot */
! 2103:
! 2104: iLastLeaf = pWriter->iFree;
! 2105: rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, pWriter->nData);
! 2106: if( rc==SQLITE_OK ){
! 2107: rc = fts3NodeWrite(p, pWriter->pTree, 1,
! 2108: pWriter->iFirst, pWriter->iFree, &iLast, &zRoot, &nRoot);
! 2109: }
! 2110: if( rc==SQLITE_OK ){
! 2111: rc = fts3WriteSegdir(
! 2112: p, iLevel, iIdx, pWriter->iFirst, iLastLeaf, iLast, zRoot, nRoot);
! 2113: }
! 2114: }else{
! 2115: /* The entire tree fits on the root node. Write it to the segdir table. */
! 2116: rc = fts3WriteSegdir(
! 2117: p, iLevel, iIdx, 0, 0, 0, pWriter->aData, pWriter->nData);
! 2118: }
! 2119: return rc;
! 2120: }
! 2121:
! 2122: /*
! 2123: ** Release all memory held by the SegmentWriter object passed as the
! 2124: ** first argument.
! 2125: */
! 2126: static void fts3SegWriterFree(SegmentWriter *pWriter){
! 2127: if( pWriter ){
! 2128: sqlite3_free(pWriter->aData);
! 2129: sqlite3_free(pWriter->zMalloc);
! 2130: fts3NodeFree(pWriter->pTree);
! 2131: sqlite3_free(pWriter);
! 2132: }
! 2133: }
! 2134:
! 2135: /*
! 2136: ** The first value in the apVal[] array is assumed to contain an integer.
! 2137: ** This function tests if there exist any documents with docid values that
! 2138: ** are different from that integer. i.e. if deleting the document with docid
! 2139: ** pRowid would mean the FTS3 table were empty.
! 2140: **
! 2141: ** If successful, *pisEmpty is set to true if the table is empty except for
! 2142: ** document pRowid, or false otherwise, and SQLITE_OK is returned. If an
! 2143: ** error occurs, an SQLite error code is returned.
! 2144: */
! 2145: static int fts3IsEmpty(Fts3Table *p, sqlite3_value *pRowid, int *pisEmpty){
! 2146: sqlite3_stmt *pStmt;
! 2147: int rc;
! 2148: if( p->zContentTbl ){
! 2149: /* If using the content=xxx option, assume the table is never empty */
! 2150: *pisEmpty = 0;
! 2151: rc = SQLITE_OK;
! 2152: }else{
! 2153: rc = fts3SqlStmt(p, SQL_IS_EMPTY, &pStmt, &pRowid);
! 2154: if( rc==SQLITE_OK ){
! 2155: if( SQLITE_ROW==sqlite3_step(pStmt) ){
! 2156: *pisEmpty = sqlite3_column_int(pStmt, 0);
! 2157: }
! 2158: rc = sqlite3_reset(pStmt);
! 2159: }
! 2160: }
! 2161: return rc;
! 2162: }
! 2163:
! 2164: /*
! 2165: ** Set *pnMax to the largest segment level in the database for the index
! 2166: ** iIndex.
! 2167: **
! 2168: ** Segment levels are stored in the 'level' column of the %_segdir table.
! 2169: **
! 2170: ** Return SQLITE_OK if successful, or an SQLite error code if not.
! 2171: */
! 2172: static int fts3SegmentMaxLevel(Fts3Table *p, int iIndex, int *pnMax){
! 2173: sqlite3_stmt *pStmt;
! 2174: int rc;
! 2175: assert( iIndex>=0 && iIndex<p->nIndex );
! 2176:
! 2177: /* Set pStmt to the compiled version of:
! 2178: **
! 2179: ** SELECT max(level) FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?
! 2180: **
! 2181: ** (1024 is actually the value of macro FTS3_SEGDIR_PREFIXLEVEL_STR).
! 2182: */
! 2183: rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR_MAX_LEVEL, &pStmt, 0);
! 2184: if( rc!=SQLITE_OK ) return rc;
! 2185: sqlite3_bind_int(pStmt, 1, iIndex*FTS3_SEGDIR_MAXLEVEL);
! 2186: sqlite3_bind_int(pStmt, 2, (iIndex+1)*FTS3_SEGDIR_MAXLEVEL - 1);
! 2187: if( SQLITE_ROW==sqlite3_step(pStmt) ){
! 2188: *pnMax = sqlite3_column_int(pStmt, 0);
! 2189: }
! 2190: return sqlite3_reset(pStmt);
! 2191: }
! 2192:
! 2193: /*
! 2194: ** This function is used after merging multiple segments into a single large
! 2195: ** segment to delete the old, now redundant, segment b-trees. Specifically,
! 2196: ** it:
! 2197: **
! 2198: ** 1) Deletes all %_segments entries for the segments associated with
! 2199: ** each of the SegReader objects in the array passed as the third
! 2200: ** argument, and
! 2201: **
! 2202: ** 2) deletes all %_segdir entries with level iLevel, or all %_segdir
! 2203: ** entries regardless of level if (iLevel<0).
! 2204: **
! 2205: ** SQLITE_OK is returned if successful, otherwise an SQLite error code.
! 2206: */
! 2207: static int fts3DeleteSegdir(
! 2208: Fts3Table *p, /* Virtual table handle */
! 2209: int iIndex, /* Index for p->aIndex */
! 2210: int iLevel, /* Level of %_segdir entries to delete */
! 2211: Fts3SegReader **apSegment, /* Array of SegReader objects */
! 2212: int nReader /* Size of array apSegment */
! 2213: ){
! 2214: int rc; /* Return Code */
! 2215: int i; /* Iterator variable */
! 2216: sqlite3_stmt *pDelete; /* SQL statement to delete rows */
! 2217:
! 2218: rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDelete, 0);
! 2219: for(i=0; rc==SQLITE_OK && i<nReader; i++){
! 2220: Fts3SegReader *pSegment = apSegment[i];
! 2221: if( pSegment->iStartBlock ){
! 2222: sqlite3_bind_int64(pDelete, 1, pSegment->iStartBlock);
! 2223: sqlite3_bind_int64(pDelete, 2, pSegment->iEndBlock);
! 2224: sqlite3_step(pDelete);
! 2225: rc = sqlite3_reset(pDelete);
! 2226: }
! 2227: }
! 2228: if( rc!=SQLITE_OK ){
! 2229: return rc;
! 2230: }
! 2231:
! 2232: assert( iLevel>=0 || iLevel==FTS3_SEGCURSOR_ALL );
! 2233: if( iLevel==FTS3_SEGCURSOR_ALL ){
! 2234: rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_RANGE, &pDelete, 0);
! 2235: if( rc==SQLITE_OK ){
! 2236: sqlite3_bind_int(pDelete, 1, iIndex*FTS3_SEGDIR_MAXLEVEL);
! 2237: sqlite3_bind_int(pDelete, 2, (iIndex+1) * FTS3_SEGDIR_MAXLEVEL - 1);
! 2238: }
! 2239: }else{
! 2240: rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_LEVEL, &pDelete, 0);
! 2241: if( rc==SQLITE_OK ){
! 2242: sqlite3_bind_int(pDelete, 1, iIndex*FTS3_SEGDIR_MAXLEVEL + iLevel);
! 2243: }
! 2244: }
! 2245:
! 2246: if( rc==SQLITE_OK ){
! 2247: sqlite3_step(pDelete);
! 2248: rc = sqlite3_reset(pDelete);
! 2249: }
! 2250:
! 2251: return rc;
! 2252: }
! 2253:
! 2254: /*
! 2255: ** When this function is called, buffer *ppList (size *pnList bytes) contains
! 2256: ** a position list that may (or may not) feature multiple columns. This
! 2257: ** function adjusts the pointer *ppList and the length *pnList so that they
! 2258: ** identify the subset of the position list that corresponds to column iCol.
! 2259: **
! 2260: ** If there are no entries in the input position list for column iCol, then
! 2261: ** *pnList is set to zero before returning.
! 2262: */
! 2263: static void fts3ColumnFilter(
! 2264: int iCol, /* Column to filter on */
! 2265: char **ppList, /* IN/OUT: Pointer to position list */
! 2266: int *pnList /* IN/OUT: Size of buffer *ppList in bytes */
! 2267: ){
! 2268: char *pList = *ppList;
! 2269: int nList = *pnList;
! 2270: char *pEnd = &pList[nList];
! 2271: int iCurrent = 0;
! 2272: char *p = pList;
! 2273:
! 2274: assert( iCol>=0 );
! 2275: while( 1 ){
! 2276: char c = 0;
! 2277: while( p<pEnd && (c | *p)&0xFE ) c = *p++ & 0x80;
! 2278:
! 2279: if( iCol==iCurrent ){
! 2280: nList = (int)(p - pList);
! 2281: break;
! 2282: }
! 2283:
! 2284: nList -= (int)(p - pList);
! 2285: pList = p;
! 2286: if( nList==0 ){
! 2287: break;
! 2288: }
! 2289: p = &pList[1];
! 2290: p += sqlite3Fts3GetVarint32(p, &iCurrent);
! 2291: }
! 2292:
! 2293: *ppList = pList;
! 2294: *pnList = nList;
! 2295: }
! 2296:
! 2297: /*
! 2298: ** Cache data in the Fts3MultiSegReader.aBuffer[] buffer (overwriting any
! 2299: ** existing data). Grow the buffer if required.
! 2300: **
! 2301: ** If successful, return SQLITE_OK. Otherwise, if an OOM error is encountered
! 2302: ** trying to resize the buffer, return SQLITE_NOMEM.
! 2303: */
! 2304: static int fts3MsrBufferData(
! 2305: Fts3MultiSegReader *pMsr, /* Multi-segment-reader handle */
! 2306: char *pList,
! 2307: int nList
! 2308: ){
! 2309: if( nList>pMsr->nBuffer ){
! 2310: char *pNew;
! 2311: pMsr->nBuffer = nList*2;
! 2312: pNew = (char *)sqlite3_realloc(pMsr->aBuffer, pMsr->nBuffer);
! 2313: if( !pNew ) return SQLITE_NOMEM;
! 2314: pMsr->aBuffer = pNew;
! 2315: }
! 2316:
! 2317: memcpy(pMsr->aBuffer, pList, nList);
! 2318: return SQLITE_OK;
! 2319: }
! 2320:
! 2321: int sqlite3Fts3MsrIncrNext(
! 2322: Fts3Table *p, /* Virtual table handle */
! 2323: Fts3MultiSegReader *pMsr, /* Multi-segment-reader handle */
! 2324: sqlite3_int64 *piDocid, /* OUT: Docid value */
! 2325: char **paPoslist, /* OUT: Pointer to position list */
! 2326: int *pnPoslist /* OUT: Size of position list in bytes */
! 2327: ){
! 2328: int nMerge = pMsr->nAdvance;
! 2329: Fts3SegReader **apSegment = pMsr->apSegment;
! 2330: int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
! 2331: p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
! 2332: );
! 2333:
! 2334: if( nMerge==0 ){
! 2335: *paPoslist = 0;
! 2336: return SQLITE_OK;
! 2337: }
! 2338:
! 2339: while( 1 ){
! 2340: Fts3SegReader *pSeg;
! 2341: pSeg = pMsr->apSegment[0];
! 2342:
! 2343: if( pSeg->pOffsetList==0 ){
! 2344: *paPoslist = 0;
! 2345: break;
! 2346: }else{
! 2347: int rc;
! 2348: char *pList;
! 2349: int nList;
! 2350: int j;
! 2351: sqlite3_int64 iDocid = apSegment[0]->iDocid;
! 2352:
! 2353: rc = fts3SegReaderNextDocid(p, apSegment[0], &pList, &nList);
! 2354: j = 1;
! 2355: while( rc==SQLITE_OK
! 2356: && j<nMerge
! 2357: && apSegment[j]->pOffsetList
! 2358: && apSegment[j]->iDocid==iDocid
! 2359: ){
! 2360: rc = fts3SegReaderNextDocid(p, apSegment[j], 0, 0);
! 2361: j++;
! 2362: }
! 2363: if( rc!=SQLITE_OK ) return rc;
! 2364: fts3SegReaderSort(pMsr->apSegment, nMerge, j, xCmp);
! 2365:
! 2366: if( pMsr->iColFilter>=0 ){
! 2367: fts3ColumnFilter(pMsr->iColFilter, &pList, &nList);
! 2368: }
! 2369:
! 2370: if( nList>0 ){
! 2371: if( fts3SegReaderIsPending(apSegment[0]) ){
! 2372: rc = fts3MsrBufferData(pMsr, pList, nList+1);
! 2373: if( rc!=SQLITE_OK ) return rc;
! 2374: *paPoslist = pMsr->aBuffer;
! 2375: assert( (pMsr->aBuffer[nList] & 0xFE)==0x00 );
! 2376: }else{
! 2377: *paPoslist = pList;
! 2378: }
! 2379: *piDocid = iDocid;
! 2380: *pnPoslist = nList;
! 2381: break;
! 2382: }
! 2383: }
! 2384: }
! 2385:
! 2386: return SQLITE_OK;
! 2387: }
! 2388:
! 2389: static int fts3SegReaderStart(
! 2390: Fts3Table *p, /* Virtual table handle */
! 2391: Fts3MultiSegReader *pCsr, /* Cursor object */
! 2392: const char *zTerm, /* Term searched for (or NULL) */
! 2393: int nTerm /* Length of zTerm in bytes */
! 2394: ){
! 2395: int i;
! 2396: int nSeg = pCsr->nSegment;
! 2397:
! 2398: /* If the Fts3SegFilter defines a specific term (or term prefix) to search
! 2399: ** for, then advance each segment iterator until it points to a term of
! 2400: ** equal or greater value than the specified term. This prevents many
! 2401: ** unnecessary merge/sort operations for the case where single segment
! 2402: ** b-tree leaf nodes contain more than one term.
! 2403: */
! 2404: for(i=0; pCsr->bRestart==0 && i<pCsr->nSegment; i++){
! 2405: Fts3SegReader *pSeg = pCsr->apSegment[i];
! 2406: do {
! 2407: int rc = fts3SegReaderNext(p, pSeg, 0);
! 2408: if( rc!=SQLITE_OK ) return rc;
! 2409: }while( zTerm && fts3SegReaderTermCmp(pSeg, zTerm, nTerm)<0 );
! 2410: }
! 2411: fts3SegReaderSort(pCsr->apSegment, nSeg, nSeg, fts3SegReaderCmp);
! 2412:
! 2413: return SQLITE_OK;
! 2414: }
! 2415:
! 2416: int sqlite3Fts3SegReaderStart(
! 2417: Fts3Table *p, /* Virtual table handle */
! 2418: Fts3MultiSegReader *pCsr, /* Cursor object */
! 2419: Fts3SegFilter *pFilter /* Restrictions on range of iteration */
! 2420: ){
! 2421: pCsr->pFilter = pFilter;
! 2422: return fts3SegReaderStart(p, pCsr, pFilter->zTerm, pFilter->nTerm);
! 2423: }
! 2424:
! 2425: int sqlite3Fts3MsrIncrStart(
! 2426: Fts3Table *p, /* Virtual table handle */
! 2427: Fts3MultiSegReader *pCsr, /* Cursor object */
! 2428: int iCol, /* Column to match on. */
! 2429: const char *zTerm, /* Term to iterate through a doclist for */
! 2430: int nTerm /* Number of bytes in zTerm */
! 2431: ){
! 2432: int i;
! 2433: int rc;
! 2434: int nSegment = pCsr->nSegment;
! 2435: int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
! 2436: p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
! 2437: );
! 2438:
! 2439: assert( pCsr->pFilter==0 );
! 2440: assert( zTerm && nTerm>0 );
! 2441:
! 2442: /* Advance each segment iterator until it points to the term zTerm/nTerm. */
! 2443: rc = fts3SegReaderStart(p, pCsr, zTerm, nTerm);
! 2444: if( rc!=SQLITE_OK ) return rc;
! 2445:
! 2446: /* Determine how many of the segments actually point to zTerm/nTerm. */
! 2447: for(i=0; i<nSegment; i++){
! 2448: Fts3SegReader *pSeg = pCsr->apSegment[i];
! 2449: if( !pSeg->aNode || fts3SegReaderTermCmp(pSeg, zTerm, nTerm) ){
! 2450: break;
! 2451: }
! 2452: }
! 2453: pCsr->nAdvance = i;
! 2454:
! 2455: /* Advance each of the segments to point to the first docid. */
! 2456: for(i=0; i<pCsr->nAdvance; i++){
! 2457: rc = fts3SegReaderFirstDocid(p, pCsr->apSegment[i]);
! 2458: if( rc!=SQLITE_OK ) return rc;
! 2459: }
! 2460: fts3SegReaderSort(pCsr->apSegment, i, i, xCmp);
! 2461:
! 2462: assert( iCol<0 || iCol<p->nColumn );
! 2463: pCsr->iColFilter = iCol;
! 2464:
! 2465: return SQLITE_OK;
! 2466: }
! 2467:
! 2468: /*
! 2469: ** This function is called on a MultiSegReader that has been started using
! 2470: ** sqlite3Fts3MsrIncrStart(). One or more calls to MsrIncrNext() may also
! 2471: ** have been made. Calling this function puts the MultiSegReader in such
! 2472: ** a state that if the next two calls are:
! 2473: **
! 2474: ** sqlite3Fts3SegReaderStart()
! 2475: ** sqlite3Fts3SegReaderStep()
! 2476: **
! 2477: ** then the entire doclist for the term is available in
! 2478: ** MultiSegReader.aDoclist/nDoclist.
! 2479: */
! 2480: int sqlite3Fts3MsrIncrRestart(Fts3MultiSegReader *pCsr){
! 2481: int i; /* Used to iterate through segment-readers */
! 2482:
! 2483: assert( pCsr->zTerm==0 );
! 2484: assert( pCsr->nTerm==0 );
! 2485: assert( pCsr->aDoclist==0 );
! 2486: assert( pCsr->nDoclist==0 );
! 2487:
! 2488: pCsr->nAdvance = 0;
! 2489: pCsr->bRestart = 1;
! 2490: for(i=0; i<pCsr->nSegment; i++){
! 2491: pCsr->apSegment[i]->pOffsetList = 0;
! 2492: pCsr->apSegment[i]->nOffsetList = 0;
! 2493: pCsr->apSegment[i]->iDocid = 0;
! 2494: }
! 2495:
! 2496: return SQLITE_OK;
! 2497: }
! 2498:
! 2499:
! 2500: int sqlite3Fts3SegReaderStep(
! 2501: Fts3Table *p, /* Virtual table handle */
! 2502: Fts3MultiSegReader *pCsr /* Cursor object */
! 2503: ){
! 2504: int rc = SQLITE_OK;
! 2505:
! 2506: int isIgnoreEmpty = (pCsr->pFilter->flags & FTS3_SEGMENT_IGNORE_EMPTY);
! 2507: int isRequirePos = (pCsr->pFilter->flags & FTS3_SEGMENT_REQUIRE_POS);
! 2508: int isColFilter = (pCsr->pFilter->flags & FTS3_SEGMENT_COLUMN_FILTER);
! 2509: int isPrefix = (pCsr->pFilter->flags & FTS3_SEGMENT_PREFIX);
! 2510: int isScan = (pCsr->pFilter->flags & FTS3_SEGMENT_SCAN);
! 2511: int isFirst = (pCsr->pFilter->flags & FTS3_SEGMENT_FIRST);
! 2512:
! 2513: Fts3SegReader **apSegment = pCsr->apSegment;
! 2514: int nSegment = pCsr->nSegment;
! 2515: Fts3SegFilter *pFilter = pCsr->pFilter;
! 2516: int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
! 2517: p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
! 2518: );
! 2519:
! 2520: if( pCsr->nSegment==0 ) return SQLITE_OK;
! 2521:
! 2522: do {
! 2523: int nMerge;
! 2524: int i;
! 2525:
! 2526: /* Advance the first pCsr->nAdvance entries in the apSegment[] array
! 2527: ** forward. Then sort the list in order of current term again.
! 2528: */
! 2529: for(i=0; i<pCsr->nAdvance; i++){
! 2530: rc = fts3SegReaderNext(p, apSegment[i], 0);
! 2531: if( rc!=SQLITE_OK ) return rc;
! 2532: }
! 2533: fts3SegReaderSort(apSegment, nSegment, pCsr->nAdvance, fts3SegReaderCmp);
! 2534: pCsr->nAdvance = 0;
! 2535:
! 2536: /* If all the seg-readers are at EOF, we're finished. return SQLITE_OK. */
! 2537: assert( rc==SQLITE_OK );
! 2538: if( apSegment[0]->aNode==0 ) break;
! 2539:
! 2540: pCsr->nTerm = apSegment[0]->nTerm;
! 2541: pCsr->zTerm = apSegment[0]->zTerm;
! 2542:
! 2543: /* If this is a prefix-search, and if the term that apSegment[0] points
! 2544: ** to does not share a suffix with pFilter->zTerm/nTerm, then all
! 2545: ** required callbacks have been made. In this case exit early.
! 2546: **
! 2547: ** Similarly, if this is a search for an exact match, and the first term
! 2548: ** of segment apSegment[0] is not a match, exit early.
! 2549: */
! 2550: if( pFilter->zTerm && !isScan ){
! 2551: if( pCsr->nTerm<pFilter->nTerm
! 2552: || (!isPrefix && pCsr->nTerm>pFilter->nTerm)
! 2553: || memcmp(pCsr->zTerm, pFilter->zTerm, pFilter->nTerm)
! 2554: ){
! 2555: break;
! 2556: }
! 2557: }
! 2558:
! 2559: nMerge = 1;
! 2560: while( nMerge<nSegment
! 2561: && apSegment[nMerge]->aNode
! 2562: && apSegment[nMerge]->nTerm==pCsr->nTerm
! 2563: && 0==memcmp(pCsr->zTerm, apSegment[nMerge]->zTerm, pCsr->nTerm)
! 2564: ){
! 2565: nMerge++;
! 2566: }
! 2567:
! 2568: assert( isIgnoreEmpty || (isRequirePos && !isColFilter) );
! 2569: if( nMerge==1
! 2570: && !isIgnoreEmpty
! 2571: && !isFirst
! 2572: && (p->bDescIdx==0 || fts3SegReaderIsPending(apSegment[0])==0)
! 2573: ){
! 2574: pCsr->nDoclist = apSegment[0]->nDoclist;
! 2575: if( fts3SegReaderIsPending(apSegment[0]) ){
! 2576: rc = fts3MsrBufferData(pCsr, apSegment[0]->aDoclist, pCsr->nDoclist);
! 2577: pCsr->aDoclist = pCsr->aBuffer;
! 2578: }else{
! 2579: pCsr->aDoclist = apSegment[0]->aDoclist;
! 2580: }
! 2581: if( rc==SQLITE_OK ) rc = SQLITE_ROW;
! 2582: }else{
! 2583: int nDoclist = 0; /* Size of doclist */
! 2584: sqlite3_int64 iPrev = 0; /* Previous docid stored in doclist */
! 2585:
! 2586: /* The current term of the first nMerge entries in the array
! 2587: ** of Fts3SegReader objects is the same. The doclists must be merged
! 2588: ** and a single term returned with the merged doclist.
! 2589: */
! 2590: for(i=0; i<nMerge; i++){
! 2591: fts3SegReaderFirstDocid(p, apSegment[i]);
! 2592: }
! 2593: fts3SegReaderSort(apSegment, nMerge, nMerge, xCmp);
! 2594: while( apSegment[0]->pOffsetList ){
! 2595: int j; /* Number of segments that share a docid */
! 2596: char *pList;
! 2597: int nList;
! 2598: int nByte;
! 2599: sqlite3_int64 iDocid = apSegment[0]->iDocid;
! 2600: fts3SegReaderNextDocid(p, apSegment[0], &pList, &nList);
! 2601: j = 1;
! 2602: while( j<nMerge
! 2603: && apSegment[j]->pOffsetList
! 2604: && apSegment[j]->iDocid==iDocid
! 2605: ){
! 2606: fts3SegReaderNextDocid(p, apSegment[j], 0, 0);
! 2607: j++;
! 2608: }
! 2609:
! 2610: if( isColFilter ){
! 2611: fts3ColumnFilter(pFilter->iCol, &pList, &nList);
! 2612: }
! 2613:
! 2614: if( !isIgnoreEmpty || nList>0 ){
! 2615:
! 2616: /* Calculate the 'docid' delta value to write into the merged
! 2617: ** doclist. */
! 2618: sqlite3_int64 iDelta;
! 2619: if( p->bDescIdx && nDoclist>0 ){
! 2620: iDelta = iPrev - iDocid;
! 2621: }else{
! 2622: iDelta = iDocid - iPrev;
! 2623: }
! 2624: assert( iDelta>0 || (nDoclist==0 && iDelta==iDocid) );
! 2625: assert( nDoclist>0 || iDelta==iDocid );
! 2626:
! 2627: nByte = sqlite3Fts3VarintLen(iDelta) + (isRequirePos?nList+1:0);
! 2628: if( nDoclist+nByte>pCsr->nBuffer ){
! 2629: char *aNew;
! 2630: pCsr->nBuffer = (nDoclist+nByte)*2;
! 2631: aNew = sqlite3_realloc(pCsr->aBuffer, pCsr->nBuffer);
! 2632: if( !aNew ){
! 2633: return SQLITE_NOMEM;
! 2634: }
! 2635: pCsr->aBuffer = aNew;
! 2636: }
! 2637:
! 2638: if( isFirst ){
! 2639: char *a = &pCsr->aBuffer[nDoclist];
! 2640: int nWrite;
! 2641:
! 2642: nWrite = sqlite3Fts3FirstFilter(iDelta, pList, nList, a);
! 2643: if( nWrite ){
! 2644: iPrev = iDocid;
! 2645: nDoclist += nWrite;
! 2646: }
! 2647: }else{
! 2648: nDoclist += sqlite3Fts3PutVarint(&pCsr->aBuffer[nDoclist], iDelta);
! 2649: iPrev = iDocid;
! 2650: if( isRequirePos ){
! 2651: memcpy(&pCsr->aBuffer[nDoclist], pList, nList);
! 2652: nDoclist += nList;
! 2653: pCsr->aBuffer[nDoclist++] = '\0';
! 2654: }
! 2655: }
! 2656: }
! 2657:
! 2658: fts3SegReaderSort(apSegment, nMerge, j, xCmp);
! 2659: }
! 2660: if( nDoclist>0 ){
! 2661: pCsr->aDoclist = pCsr->aBuffer;
! 2662: pCsr->nDoclist = nDoclist;
! 2663: rc = SQLITE_ROW;
! 2664: }
! 2665: }
! 2666: pCsr->nAdvance = nMerge;
! 2667: }while( rc==SQLITE_OK );
! 2668:
! 2669: return rc;
! 2670: }
! 2671:
! 2672:
! 2673: void sqlite3Fts3SegReaderFinish(
! 2674: Fts3MultiSegReader *pCsr /* Cursor object */
! 2675: ){
! 2676: if( pCsr ){
! 2677: int i;
! 2678: for(i=0; i<pCsr->nSegment; i++){
! 2679: sqlite3Fts3SegReaderFree(pCsr->apSegment[i]);
! 2680: }
! 2681: sqlite3_free(pCsr->apSegment);
! 2682: sqlite3_free(pCsr->aBuffer);
! 2683:
! 2684: pCsr->nSegment = 0;
! 2685: pCsr->apSegment = 0;
! 2686: pCsr->aBuffer = 0;
! 2687: }
! 2688: }
! 2689:
! 2690: /*
! 2691: ** Merge all level iLevel segments in the database into a single
! 2692: ** iLevel+1 segment. Or, if iLevel<0, merge all segments into a
! 2693: ** single segment with a level equal to the numerically largest level
! 2694: ** currently present in the database.
! 2695: **
! 2696: ** If this function is called with iLevel<0, but there is only one
! 2697: ** segment in the database, SQLITE_DONE is returned immediately.
! 2698: ** Otherwise, if successful, SQLITE_OK is returned. If an error occurs,
! 2699: ** an SQLite error code is returned.
! 2700: */
! 2701: static int fts3SegmentMerge(Fts3Table *p, int iIndex, int iLevel){
! 2702: int rc; /* Return code */
! 2703: int iIdx = 0; /* Index of new segment */
! 2704: int iNewLevel = 0; /* Level/index to create new segment at */
! 2705: SegmentWriter *pWriter = 0; /* Used to write the new, merged, segment */
! 2706: Fts3SegFilter filter; /* Segment term filter condition */
! 2707: Fts3MultiSegReader csr; /* Cursor to iterate through level(s) */
! 2708: int bIgnoreEmpty = 0; /* True to ignore empty segments */
! 2709:
! 2710: assert( iLevel==FTS3_SEGCURSOR_ALL
! 2711: || iLevel==FTS3_SEGCURSOR_PENDING
! 2712: || iLevel>=0
! 2713: );
! 2714: assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
! 2715: assert( iIndex>=0 && iIndex<p->nIndex );
! 2716:
! 2717: rc = sqlite3Fts3SegReaderCursor(p, iIndex, iLevel, 0, 0, 1, 0, &csr);
! 2718: if( rc!=SQLITE_OK || csr.nSegment==0 ) goto finished;
! 2719:
! 2720: if( iLevel==FTS3_SEGCURSOR_ALL ){
! 2721: /* This call is to merge all segments in the database to a single
! 2722: ** segment. The level of the new segment is equal to the the numerically
! 2723: ** greatest segment level currently present in the database for this
! 2724: ** index. The idx of the new segment is always 0. */
! 2725: if( csr.nSegment==1 ){
! 2726: rc = SQLITE_DONE;
! 2727: goto finished;
! 2728: }
! 2729: rc = fts3SegmentMaxLevel(p, iIndex, &iNewLevel);
! 2730: bIgnoreEmpty = 1;
! 2731:
! 2732: }else if( iLevel==FTS3_SEGCURSOR_PENDING ){
! 2733: iNewLevel = iIndex * FTS3_SEGDIR_MAXLEVEL;
! 2734: rc = fts3AllocateSegdirIdx(p, iIndex, 0, &iIdx);
! 2735: }else{
! 2736: /* This call is to merge all segments at level iLevel. find the next
! 2737: ** available segment index at level iLevel+1. The call to
! 2738: ** fts3AllocateSegdirIdx() will merge the segments at level iLevel+1 to
! 2739: ** a single iLevel+2 segment if necessary. */
! 2740: rc = fts3AllocateSegdirIdx(p, iIndex, iLevel+1, &iIdx);
! 2741: iNewLevel = iIndex * FTS3_SEGDIR_MAXLEVEL + iLevel+1;
! 2742: }
! 2743: if( rc!=SQLITE_OK ) goto finished;
! 2744: assert( csr.nSegment>0 );
! 2745: assert( iNewLevel>=(iIndex*FTS3_SEGDIR_MAXLEVEL) );
! 2746: assert( iNewLevel<((iIndex+1)*FTS3_SEGDIR_MAXLEVEL) );
! 2747:
! 2748: memset(&filter, 0, sizeof(Fts3SegFilter));
! 2749: filter.flags = FTS3_SEGMENT_REQUIRE_POS;
! 2750: filter.flags |= (bIgnoreEmpty ? FTS3_SEGMENT_IGNORE_EMPTY : 0);
! 2751:
! 2752: rc = sqlite3Fts3SegReaderStart(p, &csr, &filter);
! 2753: while( SQLITE_OK==rc ){
! 2754: rc = sqlite3Fts3SegReaderStep(p, &csr);
! 2755: if( rc!=SQLITE_ROW ) break;
! 2756: rc = fts3SegWriterAdd(p, &pWriter, 1,
! 2757: csr.zTerm, csr.nTerm, csr.aDoclist, csr.nDoclist);
! 2758: }
! 2759: if( rc!=SQLITE_OK ) goto finished;
! 2760: assert( pWriter );
! 2761:
! 2762: if( iLevel!=FTS3_SEGCURSOR_PENDING ){
! 2763: rc = fts3DeleteSegdir(p, iIndex, iLevel, csr.apSegment, csr.nSegment);
! 2764: if( rc!=SQLITE_OK ) goto finished;
! 2765: }
! 2766: rc = fts3SegWriterFlush(p, pWriter, iNewLevel, iIdx);
! 2767:
! 2768: finished:
! 2769: fts3SegWriterFree(pWriter);
! 2770: sqlite3Fts3SegReaderFinish(&csr);
! 2771: return rc;
! 2772: }
! 2773:
! 2774:
! 2775: /*
! 2776: ** Flush the contents of pendingTerms to level 0 segments.
! 2777: */
! 2778: int sqlite3Fts3PendingTermsFlush(Fts3Table *p){
! 2779: int rc = SQLITE_OK;
! 2780: int i;
! 2781: for(i=0; rc==SQLITE_OK && i<p->nIndex; i++){
! 2782: rc = fts3SegmentMerge(p, i, FTS3_SEGCURSOR_PENDING);
! 2783: if( rc==SQLITE_DONE ) rc = SQLITE_OK;
! 2784: }
! 2785: sqlite3Fts3PendingTermsClear(p);
! 2786: return rc;
! 2787: }
! 2788:
! 2789: /*
! 2790: ** Encode N integers as varints into a blob.
! 2791: */
! 2792: static void fts3EncodeIntArray(
! 2793: int N, /* The number of integers to encode */
! 2794: u32 *a, /* The integer values */
! 2795: char *zBuf, /* Write the BLOB here */
! 2796: int *pNBuf /* Write number of bytes if zBuf[] used here */
! 2797: ){
! 2798: int i, j;
! 2799: for(i=j=0; i<N; i++){
! 2800: j += sqlite3Fts3PutVarint(&zBuf[j], (sqlite3_int64)a[i]);
! 2801: }
! 2802: *pNBuf = j;
! 2803: }
! 2804:
! 2805: /*
! 2806: ** Decode a blob of varints into N integers
! 2807: */
! 2808: static void fts3DecodeIntArray(
! 2809: int N, /* The number of integers to decode */
! 2810: u32 *a, /* Write the integer values */
! 2811: const char *zBuf, /* The BLOB containing the varints */
! 2812: int nBuf /* size of the BLOB */
! 2813: ){
! 2814: int i, j;
! 2815: UNUSED_PARAMETER(nBuf);
! 2816: for(i=j=0; i<N; i++){
! 2817: sqlite3_int64 x;
! 2818: j += sqlite3Fts3GetVarint(&zBuf[j], &x);
! 2819: assert(j<=nBuf);
! 2820: a[i] = (u32)(x & 0xffffffff);
! 2821: }
! 2822: }
! 2823:
! 2824: /*
! 2825: ** Insert the sizes (in tokens) for each column of the document
! 2826: ** with docid equal to p->iPrevDocid. The sizes are encoded as
! 2827: ** a blob of varints.
! 2828: */
! 2829: static void fts3InsertDocsize(
! 2830: int *pRC, /* Result code */
! 2831: Fts3Table *p, /* Table into which to insert */
! 2832: u32 *aSz /* Sizes of each column, in tokens */
! 2833: ){
! 2834: char *pBlob; /* The BLOB encoding of the document size */
! 2835: int nBlob; /* Number of bytes in the BLOB */
! 2836: sqlite3_stmt *pStmt; /* Statement used to insert the encoding */
! 2837: int rc; /* Result code from subfunctions */
! 2838:
! 2839: if( *pRC ) return;
! 2840: pBlob = sqlite3_malloc( 10*p->nColumn );
! 2841: if( pBlob==0 ){
! 2842: *pRC = SQLITE_NOMEM;
! 2843: return;
! 2844: }
! 2845: fts3EncodeIntArray(p->nColumn, aSz, pBlob, &nBlob);
! 2846: rc = fts3SqlStmt(p, SQL_REPLACE_DOCSIZE, &pStmt, 0);
! 2847: if( rc ){
! 2848: sqlite3_free(pBlob);
! 2849: *pRC = rc;
! 2850: return;
! 2851: }
! 2852: sqlite3_bind_int64(pStmt, 1, p->iPrevDocid);
! 2853: sqlite3_bind_blob(pStmt, 2, pBlob, nBlob, sqlite3_free);
! 2854: sqlite3_step(pStmt);
! 2855: *pRC = sqlite3_reset(pStmt);
! 2856: }
! 2857:
! 2858: /*
! 2859: ** Record 0 of the %_stat table contains a blob consisting of N varints,
! 2860: ** where N is the number of user defined columns in the fts3 table plus
! 2861: ** two. If nCol is the number of user defined columns, then values of the
! 2862: ** varints are set as follows:
! 2863: **
! 2864: ** Varint 0: Total number of rows in the table.
! 2865: **
! 2866: ** Varint 1..nCol: For each column, the total number of tokens stored in
! 2867: ** the column for all rows of the table.
! 2868: **
! 2869: ** Varint 1+nCol: The total size, in bytes, of all text values in all
! 2870: ** columns of all rows of the table.
! 2871: **
! 2872: */
! 2873: static void fts3UpdateDocTotals(
! 2874: int *pRC, /* The result code */
! 2875: Fts3Table *p, /* Table being updated */
! 2876: u32 *aSzIns, /* Size increases */
! 2877: u32 *aSzDel, /* Size decreases */
! 2878: int nChng /* Change in the number of documents */
! 2879: ){
! 2880: char *pBlob; /* Storage for BLOB written into %_stat */
! 2881: int nBlob; /* Size of BLOB written into %_stat */
! 2882: u32 *a; /* Array of integers that becomes the BLOB */
! 2883: sqlite3_stmt *pStmt; /* Statement for reading and writing */
! 2884: int i; /* Loop counter */
! 2885: int rc; /* Result code from subfunctions */
! 2886:
! 2887: const int nStat = p->nColumn+2;
! 2888:
! 2889: if( *pRC ) return;
! 2890: a = sqlite3_malloc( (sizeof(u32)+10)*nStat );
! 2891: if( a==0 ){
! 2892: *pRC = SQLITE_NOMEM;
! 2893: return;
! 2894: }
! 2895: pBlob = (char*)&a[nStat];
! 2896: rc = fts3SqlStmt(p, SQL_SELECT_DOCTOTAL, &pStmt, 0);
! 2897: if( rc ){
! 2898: sqlite3_free(a);
! 2899: *pRC = rc;
! 2900: return;
! 2901: }
! 2902: if( sqlite3_step(pStmt)==SQLITE_ROW ){
! 2903: fts3DecodeIntArray(nStat, a,
! 2904: sqlite3_column_blob(pStmt, 0),
! 2905: sqlite3_column_bytes(pStmt, 0));
! 2906: }else{
! 2907: memset(a, 0, sizeof(u32)*(nStat) );
! 2908: }
! 2909: sqlite3_reset(pStmt);
! 2910: if( nChng<0 && a[0]<(u32)(-nChng) ){
! 2911: a[0] = 0;
! 2912: }else{
! 2913: a[0] += nChng;
! 2914: }
! 2915: for(i=0; i<p->nColumn+1; i++){
! 2916: u32 x = a[i+1];
! 2917: if( x+aSzIns[i] < aSzDel[i] ){
! 2918: x = 0;
! 2919: }else{
! 2920: x = x + aSzIns[i] - aSzDel[i];
! 2921: }
! 2922: a[i+1] = x;
! 2923: }
! 2924: fts3EncodeIntArray(nStat, a, pBlob, &nBlob);
! 2925: rc = fts3SqlStmt(p, SQL_REPLACE_DOCTOTAL, &pStmt, 0);
! 2926: if( rc ){
! 2927: sqlite3_free(a);
! 2928: *pRC = rc;
! 2929: return;
! 2930: }
! 2931: sqlite3_bind_blob(pStmt, 1, pBlob, nBlob, SQLITE_STATIC);
! 2932: sqlite3_step(pStmt);
! 2933: *pRC = sqlite3_reset(pStmt);
! 2934: sqlite3_free(a);
! 2935: }
! 2936:
! 2937: static int fts3DoOptimize(Fts3Table *p, int bReturnDone){
! 2938: int i;
! 2939: int bSeenDone = 0;
! 2940: int rc = SQLITE_OK;
! 2941: for(i=0; rc==SQLITE_OK && i<p->nIndex; i++){
! 2942: rc = fts3SegmentMerge(p, i, FTS3_SEGCURSOR_ALL);
! 2943: if( rc==SQLITE_DONE ){
! 2944: bSeenDone = 1;
! 2945: rc = SQLITE_OK;
! 2946: }
! 2947: }
! 2948: sqlite3Fts3SegmentsClose(p);
! 2949: sqlite3Fts3PendingTermsClear(p);
! 2950:
! 2951: return (rc==SQLITE_OK && bReturnDone && bSeenDone) ? SQLITE_DONE : rc;
! 2952: }
! 2953:
! 2954: /*
! 2955: ** This function is called when the user executes the following statement:
! 2956: **
! 2957: ** INSERT INTO <tbl>(<tbl>) VALUES('rebuild');
! 2958: **
! 2959: ** The entire FTS index is discarded and rebuilt. If the table is one
! 2960: ** created using the content=xxx option, then the new index is based on
! 2961: ** the current contents of the xxx table. Otherwise, it is rebuilt based
! 2962: ** on the contents of the %_content table.
! 2963: */
! 2964: static int fts3DoRebuild(Fts3Table *p){
! 2965: int rc; /* Return Code */
! 2966:
! 2967: rc = fts3DeleteAll(p, 0);
! 2968: if( rc==SQLITE_OK ){
! 2969: u32 *aSz = 0;
! 2970: u32 *aSzIns = 0;
! 2971: u32 *aSzDel = 0;
! 2972: sqlite3_stmt *pStmt = 0;
! 2973: int nEntry = 0;
! 2974:
! 2975: /* Compose and prepare an SQL statement to loop through the content table */
! 2976: char *zSql = sqlite3_mprintf("SELECT %s" , p->zReadExprlist);
! 2977: if( !zSql ){
! 2978: rc = SQLITE_NOMEM;
! 2979: }else{
! 2980: rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0);
! 2981: sqlite3_free(zSql);
! 2982: }
! 2983:
! 2984: if( rc==SQLITE_OK ){
! 2985: int nByte = sizeof(u32) * (p->nColumn+1)*3;
! 2986: aSz = (u32 *)sqlite3_malloc(nByte);
! 2987: if( aSz==0 ){
! 2988: rc = SQLITE_NOMEM;
! 2989: }else{
! 2990: memset(aSz, 0, nByte);
! 2991: aSzIns = &aSz[p->nColumn+1];
! 2992: aSzDel = &aSzIns[p->nColumn+1];
! 2993: }
! 2994: }
! 2995:
! 2996: while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
! 2997: int iCol;
! 2998: rc = fts3PendingTermsDocid(p, sqlite3_column_int64(pStmt, 0));
! 2999: aSz[p->nColumn] = 0;
! 3000: for(iCol=0; rc==SQLITE_OK && iCol<p->nColumn; iCol++){
! 3001: const char *z = (const char *) sqlite3_column_text(pStmt, iCol+1);
! 3002: rc = fts3PendingTermsAdd(p, z, iCol, &aSz[iCol]);
! 3003: aSz[p->nColumn] += sqlite3_column_bytes(pStmt, iCol+1);
! 3004: }
! 3005: if( p->bHasDocsize ){
! 3006: fts3InsertDocsize(&rc, p, aSz);
! 3007: }
! 3008: if( rc!=SQLITE_OK ){
! 3009: sqlite3_finalize(pStmt);
! 3010: pStmt = 0;
! 3011: }else{
! 3012: nEntry++;
! 3013: for(iCol=0; iCol<=p->nColumn; iCol++){
! 3014: aSzIns[iCol] += aSz[iCol];
! 3015: }
! 3016: }
! 3017: }
! 3018: if( p->bHasStat ){
! 3019: fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nEntry);
! 3020: }
! 3021: sqlite3_free(aSz);
! 3022:
! 3023: if( pStmt ){
! 3024: int rc2 = sqlite3_finalize(pStmt);
! 3025: if( rc==SQLITE_OK ){
! 3026: rc = rc2;
! 3027: }
! 3028: }
! 3029: }
! 3030:
! 3031: return rc;
! 3032: }
! 3033:
! 3034: /*
! 3035: ** Handle a 'special' INSERT of the form:
! 3036: **
! 3037: ** "INSERT INTO tbl(tbl) VALUES(<expr>)"
! 3038: **
! 3039: ** Argument pVal contains the result of <expr>. Currently the only
! 3040: ** meaningful value to insert is the text 'optimize'.
! 3041: */
! 3042: static int fts3SpecialInsert(Fts3Table *p, sqlite3_value *pVal){
! 3043: int rc; /* Return Code */
! 3044: const char *zVal = (const char *)sqlite3_value_text(pVal);
! 3045: int nVal = sqlite3_value_bytes(pVal);
! 3046:
! 3047: if( !zVal ){
! 3048: return SQLITE_NOMEM;
! 3049: }else if( nVal==8 && 0==sqlite3_strnicmp(zVal, "optimize", 8) ){
! 3050: rc = fts3DoOptimize(p, 0);
! 3051: }else if( nVal==7 && 0==sqlite3_strnicmp(zVal, "rebuild", 7) ){
! 3052: rc = fts3DoRebuild(p);
! 3053: #ifdef SQLITE_TEST
! 3054: }else if( nVal>9 && 0==sqlite3_strnicmp(zVal, "nodesize=", 9) ){
! 3055: p->nNodeSize = atoi(&zVal[9]);
! 3056: rc = SQLITE_OK;
! 3057: }else if( nVal>11 && 0==sqlite3_strnicmp(zVal, "maxpending=", 9) ){
! 3058: p->nMaxPendingData = atoi(&zVal[11]);
! 3059: rc = SQLITE_OK;
! 3060: #endif
! 3061: }else{
! 3062: rc = SQLITE_ERROR;
! 3063: }
! 3064:
! 3065: return rc;
! 3066: }
! 3067:
! 3068: /*
! 3069: ** Delete all cached deferred doclists. Deferred doclists are cached
! 3070: ** (allocated) by the sqlite3Fts3CacheDeferredDoclists() function.
! 3071: */
! 3072: void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *pCsr){
! 3073: Fts3DeferredToken *pDef;
! 3074: for(pDef=pCsr->pDeferred; pDef; pDef=pDef->pNext){
! 3075: fts3PendingListDelete(pDef->pList);
! 3076: pDef->pList = 0;
! 3077: }
! 3078: }
! 3079:
! 3080: /*
! 3081: ** Free all entries in the pCsr->pDeffered list. Entries are added to
! 3082: ** this list using sqlite3Fts3DeferToken().
! 3083: */
! 3084: void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *pCsr){
! 3085: Fts3DeferredToken *pDef;
! 3086: Fts3DeferredToken *pNext;
! 3087: for(pDef=pCsr->pDeferred; pDef; pDef=pNext){
! 3088: pNext = pDef->pNext;
! 3089: fts3PendingListDelete(pDef->pList);
! 3090: sqlite3_free(pDef);
! 3091: }
! 3092: pCsr->pDeferred = 0;
! 3093: }
! 3094:
! 3095: /*
! 3096: ** Generate deferred-doclists for all tokens in the pCsr->pDeferred list
! 3097: ** based on the row that pCsr currently points to.
! 3098: **
! 3099: ** A deferred-doclist is like any other doclist with position information
! 3100: ** included, except that it only contains entries for a single row of the
! 3101: ** table, not for all rows.
! 3102: */
! 3103: int sqlite3Fts3CacheDeferredDoclists(Fts3Cursor *pCsr){
! 3104: int rc = SQLITE_OK; /* Return code */
! 3105: if( pCsr->pDeferred ){
! 3106: int i; /* Used to iterate through table columns */
! 3107: sqlite3_int64 iDocid; /* Docid of the row pCsr points to */
! 3108: Fts3DeferredToken *pDef; /* Used to iterate through deferred tokens */
! 3109:
! 3110: Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
! 3111: sqlite3_tokenizer *pT = p->pTokenizer;
! 3112: sqlite3_tokenizer_module const *pModule = pT->pModule;
! 3113:
! 3114: assert( pCsr->isRequireSeek==0 );
! 3115: iDocid = sqlite3_column_int64(pCsr->pStmt, 0);
! 3116:
! 3117: for(i=0; i<p->nColumn && rc==SQLITE_OK; i++){
! 3118: const char *zText = (const char *)sqlite3_column_text(pCsr->pStmt, i+1);
! 3119: sqlite3_tokenizer_cursor *pTC = 0;
! 3120:
! 3121: rc = pModule->xOpen(pT, zText, -1, &pTC);
! 3122: while( rc==SQLITE_OK ){
! 3123: char const *zToken; /* Buffer containing token */
! 3124: int nToken; /* Number of bytes in token */
! 3125: int iDum1, iDum2; /* Dummy variables */
! 3126: int iPos; /* Position of token in zText */
! 3127:
! 3128: pTC->pTokenizer = pT;
! 3129: rc = pModule->xNext(pTC, &zToken, &nToken, &iDum1, &iDum2, &iPos);
! 3130: for(pDef=pCsr->pDeferred; pDef && rc==SQLITE_OK; pDef=pDef->pNext){
! 3131: Fts3PhraseToken *pPT = pDef->pToken;
! 3132: if( (pDef->iCol>=p->nColumn || pDef->iCol==i)
! 3133: && (pPT->bFirst==0 || iPos==0)
! 3134: && (pPT->n==nToken || (pPT->isPrefix && pPT->n<nToken))
! 3135: && (0==memcmp(zToken, pPT->z, pPT->n))
! 3136: ){
! 3137: fts3PendingListAppend(&pDef->pList, iDocid, i, iPos, &rc);
! 3138: }
! 3139: }
! 3140: }
! 3141: if( pTC ) pModule->xClose(pTC);
! 3142: if( rc==SQLITE_DONE ) rc = SQLITE_OK;
! 3143: }
! 3144:
! 3145: for(pDef=pCsr->pDeferred; pDef && rc==SQLITE_OK; pDef=pDef->pNext){
! 3146: if( pDef->pList ){
! 3147: rc = fts3PendingListAppendVarint(&pDef->pList, 0);
! 3148: }
! 3149: }
! 3150: }
! 3151:
! 3152: return rc;
! 3153: }
! 3154:
! 3155: int sqlite3Fts3DeferredTokenList(
! 3156: Fts3DeferredToken *p,
! 3157: char **ppData,
! 3158: int *pnData
! 3159: ){
! 3160: char *pRet;
! 3161: int nSkip;
! 3162: sqlite3_int64 dummy;
! 3163:
! 3164: *ppData = 0;
! 3165: *pnData = 0;
! 3166:
! 3167: if( p->pList==0 ){
! 3168: return SQLITE_OK;
! 3169: }
! 3170:
! 3171: pRet = (char *)sqlite3_malloc(p->pList->nData);
! 3172: if( !pRet ) return SQLITE_NOMEM;
! 3173:
! 3174: nSkip = sqlite3Fts3GetVarint(p->pList->aData, &dummy);
! 3175: *pnData = p->pList->nData - nSkip;
! 3176: *ppData = pRet;
! 3177:
! 3178: memcpy(pRet, &p->pList->aData[nSkip], *pnData);
! 3179: return SQLITE_OK;
! 3180: }
! 3181:
! 3182: /*
! 3183: ** Add an entry for token pToken to the pCsr->pDeferred list.
! 3184: */
! 3185: int sqlite3Fts3DeferToken(
! 3186: Fts3Cursor *pCsr, /* Fts3 table cursor */
! 3187: Fts3PhraseToken *pToken, /* Token to defer */
! 3188: int iCol /* Column that token must appear in (or -1) */
! 3189: ){
! 3190: Fts3DeferredToken *pDeferred;
! 3191: pDeferred = sqlite3_malloc(sizeof(*pDeferred));
! 3192: if( !pDeferred ){
! 3193: return SQLITE_NOMEM;
! 3194: }
! 3195: memset(pDeferred, 0, sizeof(*pDeferred));
! 3196: pDeferred->pToken = pToken;
! 3197: pDeferred->pNext = pCsr->pDeferred;
! 3198: pDeferred->iCol = iCol;
! 3199: pCsr->pDeferred = pDeferred;
! 3200:
! 3201: assert( pToken->pDeferred==0 );
! 3202: pToken->pDeferred = pDeferred;
! 3203:
! 3204: return SQLITE_OK;
! 3205: }
! 3206:
! 3207: /*
! 3208: ** SQLite value pRowid contains the rowid of a row that may or may not be
! 3209: ** present in the FTS3 table. If it is, delete it and adjust the contents
! 3210: ** of subsiduary data structures accordingly.
! 3211: */
! 3212: static int fts3DeleteByRowid(
! 3213: Fts3Table *p,
! 3214: sqlite3_value *pRowid,
! 3215: int *pnDoc,
! 3216: u32 *aSzDel
! 3217: ){
! 3218: int isEmpty = 0;
! 3219: int rc = fts3IsEmpty(p, pRowid, &isEmpty);
! 3220: if( rc==SQLITE_OK ){
! 3221: if( isEmpty ){
! 3222: /* Deleting this row means the whole table is empty. In this case
! 3223: ** delete the contents of all three tables and throw away any
! 3224: ** data in the pendingTerms hash table. */
! 3225: rc = fts3DeleteAll(p, 1);
! 3226: *pnDoc = *pnDoc - 1;
! 3227: }else{
! 3228: sqlite3_int64 iRemove = sqlite3_value_int64(pRowid);
! 3229: rc = fts3PendingTermsDocid(p, iRemove);
! 3230: fts3DeleteTerms(&rc, p, pRowid, aSzDel);
! 3231: if( p->zContentTbl==0 ){
! 3232: fts3SqlExec(&rc, p, SQL_DELETE_CONTENT, &pRowid);
! 3233: if( sqlite3_changes(p->db) ) *pnDoc = *pnDoc - 1;
! 3234: }else{
! 3235: *pnDoc = *pnDoc - 1;
! 3236: }
! 3237: if( p->bHasDocsize ){
! 3238: fts3SqlExec(&rc, p, SQL_DELETE_DOCSIZE, &pRowid);
! 3239: }
! 3240: }
! 3241: }
! 3242:
! 3243: return rc;
! 3244: }
! 3245:
! 3246: /*
! 3247: ** This function does the work for the xUpdate method of FTS3 virtual
! 3248: ** tables.
! 3249: */
! 3250: int sqlite3Fts3UpdateMethod(
! 3251: sqlite3_vtab *pVtab, /* FTS3 vtab object */
! 3252: int nArg, /* Size of argument array */
! 3253: sqlite3_value **apVal, /* Array of arguments */
! 3254: sqlite_int64 *pRowid /* OUT: The affected (or effected) rowid */
! 3255: ){
! 3256: Fts3Table *p = (Fts3Table *)pVtab;
! 3257: int rc = SQLITE_OK; /* Return Code */
! 3258: int isRemove = 0; /* True for an UPDATE or DELETE */
! 3259: u32 *aSzIns = 0; /* Sizes of inserted documents */
! 3260: u32 *aSzDel; /* Sizes of deleted documents */
! 3261: int nChng = 0; /* Net change in number of documents */
! 3262: int bInsertDone = 0;
! 3263:
! 3264: assert( p->pSegments==0 );
! 3265:
! 3266: /* Check for a "special" INSERT operation. One of the form:
! 3267: **
! 3268: ** INSERT INTO xyz(xyz) VALUES('command');
! 3269: */
! 3270: if( nArg>1
! 3271: && sqlite3_value_type(apVal[0])==SQLITE_NULL
! 3272: && sqlite3_value_type(apVal[p->nColumn+2])!=SQLITE_NULL
! 3273: ){
! 3274: rc = fts3SpecialInsert(p, apVal[p->nColumn+2]);
! 3275: goto update_out;
! 3276: }
! 3277:
! 3278: /* Allocate space to hold the change in document sizes */
! 3279: aSzIns = sqlite3_malloc( sizeof(aSzIns[0])*(p->nColumn+1)*2 );
! 3280: if( aSzIns==0 ){
! 3281: rc = SQLITE_NOMEM;
! 3282: goto update_out;
! 3283: }
! 3284: aSzDel = &aSzIns[p->nColumn+1];
! 3285: memset(aSzIns, 0, sizeof(aSzIns[0])*(p->nColumn+1)*2);
! 3286:
! 3287: /* If this is an INSERT operation, or an UPDATE that modifies the rowid
! 3288: ** value, then this operation requires constraint handling.
! 3289: **
! 3290: ** If the on-conflict mode is REPLACE, this means that the existing row
! 3291: ** should be deleted from the database before inserting the new row. Or,
! 3292: ** if the on-conflict mode is other than REPLACE, then this method must
! 3293: ** detect the conflict and return SQLITE_CONSTRAINT before beginning to
! 3294: ** modify the database file.
! 3295: */
! 3296: if( nArg>1 && p->zContentTbl==0 ){
! 3297: /* Find the value object that holds the new rowid value. */
! 3298: sqlite3_value *pNewRowid = apVal[3+p->nColumn];
! 3299: if( sqlite3_value_type(pNewRowid)==SQLITE_NULL ){
! 3300: pNewRowid = apVal[1];
! 3301: }
! 3302:
! 3303: if( sqlite3_value_type(pNewRowid)!=SQLITE_NULL && (
! 3304: sqlite3_value_type(apVal[0])==SQLITE_NULL
! 3305: || sqlite3_value_int64(apVal[0])!=sqlite3_value_int64(pNewRowid)
! 3306: )){
! 3307: /* The new rowid is not NULL (in this case the rowid will be
! 3308: ** automatically assigned and there is no chance of a conflict), and
! 3309: ** the statement is either an INSERT or an UPDATE that modifies the
! 3310: ** rowid column. So if the conflict mode is REPLACE, then delete any
! 3311: ** existing row with rowid=pNewRowid.
! 3312: **
! 3313: ** Or, if the conflict mode is not REPLACE, insert the new record into
! 3314: ** the %_content table. If we hit the duplicate rowid constraint (or any
! 3315: ** other error) while doing so, return immediately.
! 3316: **
! 3317: ** This branch may also run if pNewRowid contains a value that cannot
! 3318: ** be losslessly converted to an integer. In this case, the eventual
! 3319: ** call to fts3InsertData() (either just below or further on in this
! 3320: ** function) will return SQLITE_MISMATCH. If fts3DeleteByRowid is
! 3321: ** invoked, it will delete zero rows (since no row will have
! 3322: ** docid=$pNewRowid if $pNewRowid is not an integer value).
! 3323: */
! 3324: if( sqlite3_vtab_on_conflict(p->db)==SQLITE_REPLACE ){
! 3325: rc = fts3DeleteByRowid(p, pNewRowid, &nChng, aSzDel);
! 3326: }else{
! 3327: rc = fts3InsertData(p, apVal, pRowid);
! 3328: bInsertDone = 1;
! 3329: }
! 3330: }
! 3331: }
! 3332: if( rc!=SQLITE_OK ){
! 3333: goto update_out;
! 3334: }
! 3335:
! 3336: /* If this is a DELETE or UPDATE operation, remove the old record. */
! 3337: if( sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
! 3338: assert( sqlite3_value_type(apVal[0])==SQLITE_INTEGER );
! 3339: rc = fts3DeleteByRowid(p, apVal[0], &nChng, aSzDel);
! 3340: isRemove = 1;
! 3341: }
! 3342:
! 3343: /* If this is an INSERT or UPDATE operation, insert the new record. */
! 3344: if( nArg>1 && rc==SQLITE_OK ){
! 3345: if( bInsertDone==0 ){
! 3346: rc = fts3InsertData(p, apVal, pRowid);
! 3347: if( rc==SQLITE_CONSTRAINT && p->zContentTbl==0 ){
! 3348: rc = FTS_CORRUPT_VTAB;
! 3349: }
! 3350: }
! 3351: if( rc==SQLITE_OK && (!isRemove || *pRowid!=p->iPrevDocid ) ){
! 3352: rc = fts3PendingTermsDocid(p, *pRowid);
! 3353: }
! 3354: if( rc==SQLITE_OK ){
! 3355: assert( p->iPrevDocid==*pRowid );
! 3356: rc = fts3InsertTerms(p, apVal, aSzIns);
! 3357: }
! 3358: if( p->bHasDocsize ){
! 3359: fts3InsertDocsize(&rc, p, aSzIns);
! 3360: }
! 3361: nChng++;
! 3362: }
! 3363:
! 3364: if( p->bHasStat ){
! 3365: fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nChng);
! 3366: }
! 3367:
! 3368: update_out:
! 3369: sqlite3_free(aSzIns);
! 3370: sqlite3Fts3SegmentsClose(p);
! 3371: return rc;
! 3372: }
! 3373:
! 3374: /*
! 3375: ** Flush any data in the pending-terms hash table to disk. If successful,
! 3376: ** merge all segments in the database (including the new segment, if
! 3377: ** there was any data to flush) into a single segment.
! 3378: */
! 3379: int sqlite3Fts3Optimize(Fts3Table *p){
! 3380: int rc;
! 3381: rc = sqlite3_exec(p->db, "SAVEPOINT fts3", 0, 0, 0);
! 3382: if( rc==SQLITE_OK ){
! 3383: rc = fts3DoOptimize(p, 1);
! 3384: if( rc==SQLITE_OK || rc==SQLITE_DONE ){
! 3385: int rc2 = sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);
! 3386: if( rc2!=SQLITE_OK ) rc = rc2;
! 3387: }else{
! 3388: sqlite3_exec(p->db, "ROLLBACK TO fts3", 0, 0, 0);
! 3389: sqlite3_exec(p->db, "RELEASE fts3", 0, 0, 0);
! 3390: }
! 3391: }
! 3392: sqlite3Fts3SegmentsClose(p);
! 3393: return rc;
! 3394: }
! 3395:
! 3396: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to fts3_write.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / ext / fts3