| /* |
| ** 2014 May 31 |
| ** |
| ** The author disclaims copyright to this source code. In place of |
| ** a legal notice, here is a blessing: |
| ** |
| ** May you do good and not evil. |
| ** May you find forgiveness for yourself and forgive others. |
| ** May you share freely, never taking more than you give. |
| ** |
| ****************************************************************************** |
| ** |
| ** Low level access to the FTS index stored in the database file. The |
| ** routines in this file file implement all read and write access to the |
| ** %_data table. Other parts of the system access this functionality via |
| ** the interface defined in fts5Int.h. |
| */ |
| |
| |
| #include "fts5Int.h" |
| |
| /* |
| ** Overview: |
| ** |
| ** The %_data table contains all the FTS indexes for an FTS5 virtual table. |
| ** As well as the main term index, there may be up to 31 prefix indexes. |
| ** The format is similar to FTS3/4, except that: |
| ** |
| ** * all segment b-tree leaf data is stored in fixed size page records |
| ** (e.g. 1000 bytes). A single doclist may span multiple pages. Care is |
| ** taken to ensure it is possible to iterate in either direction through |
| ** the entries in a doclist, or to seek to a specific entry within a |
| ** doclist, without loading it into memory. |
| ** |
| ** * large doclists that span many pages have associated "doclist index" |
| ** records that contain a copy of the first rowid on each page spanned by |
| ** the doclist. This is used to speed up seek operations, and merges of |
| ** large doclists with very small doclists. |
| ** |
| ** * extra fields in the "structure record" record the state of ongoing |
| ** incremental merge operations. |
| ** |
| */ |
| |
| |
| #define FTS5_OPT_WORK_UNIT 1000 /* Number of leaf pages per optimize step */ |
| #define FTS5_WORK_UNIT 64 /* Number of leaf pages in unit of work */ |
| |
| #define FTS5_MIN_DLIDX_SIZE 4 /* Add dlidx if this many empty pages */ |
| |
| #define FTS5_MAIN_PREFIX '0' |
| |
| #if FTS5_MAX_PREFIX_INDEXES > 31 |
| # error "FTS5_MAX_PREFIX_INDEXES is too large" |
| #endif |
| |
| /* |
| ** Details: |
| ** |
| ** The %_data table managed by this module, |
| ** |
| ** CREATE TABLE %_data(id INTEGER PRIMARY KEY, block BLOB); |
| ** |
| ** , contains the following 5 types of records. See the comments surrounding |
| ** the FTS5_*_ROWID macros below for a description of how %_data rowids are |
| ** assigned to each fo them. |
| ** |
| ** 1. Structure Records: |
| ** |
| ** The set of segments that make up an index - the index structure - are |
| ** recorded in a single record within the %_data table. The record consists |
| ** of a single 32-bit configuration cookie value followed by a list of |
| ** SQLite varints. If the FTS table features more than one index (because |
| ** there are one or more prefix indexes), it is guaranteed that all share |
| ** the same cookie value. |
| ** |
| ** Immediately following the configuration cookie, the record begins with |
| ** three varints: |
| ** |
| ** + number of levels, |
| ** + total number of segments on all levels, |
| ** + value of write counter. |
| ** |
| ** Then, for each level from 0 to nMax: |
| ** |
| ** + number of input segments in ongoing merge. |
| ** + total number of segments in level. |
| ** + for each segment from oldest to newest: |
| ** + segment id (always > 0) |
| ** + first leaf page number (often 1, always greater than 0) |
| ** + final leaf page number |
| ** |
| ** 2. The Averages Record: |
| ** |
| ** A single record within the %_data table. The data is a list of varints. |
| ** The first value is the number of rows in the index. Then, for each column |
| ** from left to right, the total number of tokens in the column for all |
| ** rows of the table. |
| ** |
| ** 3. Segment leaves: |
| ** |
| ** TERM/DOCLIST FORMAT: |
| ** |
| ** Most of each segment leaf is taken up by term/doclist data. The |
| ** general format of term/doclist, starting with the first term |
| ** on the leaf page, is: |
| ** |
| ** varint : size of first term |
| ** blob: first term data |
| ** doclist: first doclist |
| ** zero-or-more { |
| ** varint: number of bytes in common with previous term |
| ** varint: number of bytes of new term data (nNew) |
| ** blob: nNew bytes of new term data |
| ** doclist: next doclist |
| ** } |
| ** |
| ** doclist format: |
| ** |
| ** varint: first rowid |
| ** poslist: first poslist |
| ** zero-or-more { |
| ** varint: rowid delta (always > 0) |
| ** poslist: next poslist |
| ** } |
| ** |
| ** poslist format: |
| ** |
| ** varint: size of poslist in bytes multiplied by 2, not including |
| ** this field. Plus 1 if this entry carries the "delete" flag. |
| ** collist: collist for column 0 |
| ** zero-or-more { |
| ** 0x01 byte |
| ** varint: column number (I) |
| ** collist: collist for column I |
| ** } |
| ** |
| ** collist format: |
| ** |
| ** varint: first offset + 2 |
| ** zero-or-more { |
| ** varint: offset delta + 2 |
| ** } |
| ** |
| ** PAGE FORMAT |
| ** |
| ** Each leaf page begins with a 4-byte header containing 2 16-bit |
| ** unsigned integer fields in big-endian format. They are: |
| ** |
| ** * The byte offset of the first rowid on the page, if it exists |
| ** and occurs before the first term (otherwise 0). |
| ** |
| ** * The byte offset of the start of the page footer. If the page |
| ** footer is 0 bytes in size, then this field is the same as the |
| ** size of the leaf page in bytes. |
| ** |
| ** The page footer consists of a single varint for each term located |
| ** on the page. Each varint is the byte offset of the current term |
| ** within the page, delta-compressed against the previous value. In |
| ** other words, the first varint in the footer is the byte offset of |
| ** the first term, the second is the byte offset of the second less that |
| ** of the first, and so on. |
| ** |
| ** The term/doclist format described above is accurate if the entire |
| ** term/doclist data fits on a single leaf page. If this is not the case, |
| ** the format is changed in two ways: |
| ** |
| ** + if the first rowid on a page occurs before the first term, it |
| ** is stored as a literal value: |
| ** |
| ** varint: first rowid |
| ** |
| ** + the first term on each page is stored in the same way as the |
| ** very first term of the segment: |
| ** |
| ** varint : size of first term |
| ** blob: first term data |
| ** |
| ** 5. Segment doclist indexes: |
| ** |
| ** Doclist indexes are themselves b-trees, however they usually consist of |
| ** a single leaf record only. The format of each doclist index leaf page |
| ** is: |
| ** |
| ** * Flags byte. Bits are: |
| ** 0x01: Clear if leaf is also the root page, otherwise set. |
| ** |
| ** * Page number of fts index leaf page. As a varint. |
| ** |
| ** * First rowid on page indicated by previous field. As a varint. |
| ** |
| ** * A list of varints, one for each subsequent termless page. A |
| ** positive delta if the termless page contains at least one rowid, |
| ** or an 0x00 byte otherwise. |
| ** |
| ** Internal doclist index nodes are: |
| ** |
| ** * Flags byte. Bits are: |
| ** 0x01: Clear for root page, otherwise set. |
| ** |
| ** * Page number of first child page. As a varint. |
| ** |
| ** * Copy of first rowid on page indicated by previous field. As a varint. |
| ** |
| ** * A list of delta-encoded varints - the first rowid on each subsequent |
| ** child page. |
| ** |
| */ |
| |
| /* |
| ** Rowids for the averages and structure records in the %_data table. |
| */ |
| #define FTS5_AVERAGES_ROWID 1 /* Rowid used for the averages record */ |
| #define FTS5_STRUCTURE_ROWID 10 /* The structure record */ |
| |
| /* |
| ** Macros determining the rowids used by segment leaves and dlidx leaves |
| ** and nodes. All nodes and leaves are stored in the %_data table with large |
| ** positive rowids. |
| ** |
| ** Each segment has a unique non-zero 16-bit id. |
| ** |
| ** The rowid for each segment leaf is found by passing the segment id and |
| ** the leaf page number to the FTS5_SEGMENT_ROWID macro. Leaves are numbered |
| ** sequentially starting from 1. |
| */ |
| #define FTS5_DATA_ID_B 16 /* Max seg id number 65535 */ |
| #define FTS5_DATA_DLI_B 1 /* Doclist-index flag (1 bit) */ |
| #define FTS5_DATA_HEIGHT_B 5 /* Max dlidx tree height of 32 */ |
| #define FTS5_DATA_PAGE_B 31 /* Max page number of 2147483648 */ |
| |
| #define fts5_dri(segid, dlidx, height, pgno) ( \ |
| ((i64)(segid) << (FTS5_DATA_PAGE_B+FTS5_DATA_HEIGHT_B+FTS5_DATA_DLI_B)) + \ |
| ((i64)(dlidx) << (FTS5_DATA_PAGE_B + FTS5_DATA_HEIGHT_B)) + \ |
| ((i64)(height) << (FTS5_DATA_PAGE_B)) + \ |
| ((i64)(pgno)) \ |
| ) |
| |
| #define FTS5_SEGMENT_ROWID(segid, pgno) fts5_dri(segid, 0, 0, pgno) |
| #define FTS5_DLIDX_ROWID(segid, height, pgno) fts5_dri(segid, 1, height, pgno) |
| |
| /* |
| ** Maximum segments permitted in a single index |
| */ |
| #define FTS5_MAX_SEGMENT 2000 |
| |
| #ifdef SQLITE_DEBUG |
| int sqlite3Fts5Corrupt() { return SQLITE_CORRUPT_VTAB; } |
| #endif |
| |
| |
| /* |
| ** Each time a blob is read from the %_data table, it is padded with this |
| ** many zero bytes. This makes it easier to decode the various record formats |
| ** without overreading if the records are corrupt. |
| */ |
| #define FTS5_DATA_ZERO_PADDING 8 |
| #define FTS5_DATA_PADDING 20 |
| |
| typedef struct Fts5Data Fts5Data; |
| typedef struct Fts5DlidxIter Fts5DlidxIter; |
| typedef struct Fts5DlidxLvl Fts5DlidxLvl; |
| typedef struct Fts5DlidxWriter Fts5DlidxWriter; |
| typedef struct Fts5Iter Fts5Iter; |
| typedef struct Fts5PageWriter Fts5PageWriter; |
| typedef struct Fts5SegIter Fts5SegIter; |
| typedef struct Fts5DoclistIter Fts5DoclistIter; |
| typedef struct Fts5SegWriter Fts5SegWriter; |
| typedef struct Fts5Structure Fts5Structure; |
| typedef struct Fts5StructureLevel Fts5StructureLevel; |
| typedef struct Fts5StructureSegment Fts5StructureSegment; |
| |
| struct Fts5Data { |
| u8 *p; /* Pointer to buffer containing record */ |
| int nn; /* Size of record in bytes */ |
| int szLeaf; /* Size of leaf without page-index */ |
| }; |
| |
| /* |
| ** One object per %_data table. |
| */ |
| struct Fts5Index { |
| Fts5Config *pConfig; /* Virtual table configuration */ |
| char *zDataTbl; /* Name of %_data table */ |
| int nWorkUnit; /* Leaf pages in a "unit" of work */ |
| |
| /* |
| ** Variables related to the accumulation of tokens and doclists within the |
| ** in-memory hash tables before they are flushed to disk. |
| */ |
| Fts5Hash *pHash; /* Hash table for in-memory data */ |
| int nPendingData; /* Current bytes of pending data */ |
| i64 iWriteRowid; /* Rowid for current doc being written */ |
| int bDelete; /* Current write is a delete */ |
| |
| /* Error state. */ |
| int rc; /* Current error code */ |
| |
| /* State used by the fts5DataXXX() functions. */ |
| sqlite3_blob *pReader; /* RO incr-blob open on %_data table */ |
| sqlite3_stmt *pWriter; /* "INSERT ... %_data VALUES(?,?)" */ |
| sqlite3_stmt *pDeleter; /* "DELETE FROM %_data ... id>=? AND id<=?" */ |
| sqlite3_stmt *pIdxWriter; /* "INSERT ... %_idx VALUES(?,?,?,?)" */ |
| sqlite3_stmt *pIdxDeleter; /* "DELETE FROM %_idx WHERE segid=? */ |
| sqlite3_stmt *pIdxSelect; |
| int nRead; /* Total number of blocks read */ |
| |
| sqlite3_stmt *pDataVersion; |
| i64 iStructVersion; /* data_version when pStruct read */ |
| Fts5Structure *pStruct; /* Current db structure (or NULL) */ |
| }; |
| |
| struct Fts5DoclistIter { |
| u8 *aEof; /* Pointer to 1 byte past end of doclist */ |
| |
| /* Output variables. aPoslist==0 at EOF */ |
| i64 iRowid; |
| u8 *aPoslist; |
| int nPoslist; |
| int nSize; |
| }; |
| |
| /* |
| ** The contents of the "structure" record for each index are represented |
| ** using an Fts5Structure record in memory. Which uses instances of the |
| ** other Fts5StructureXXX types as components. |
| */ |
| struct Fts5StructureSegment { |
| int iSegid; /* Segment id */ |
| int pgnoFirst; /* First leaf page number in segment */ |
| int pgnoLast; /* Last leaf page number in segment */ |
| }; |
| struct Fts5StructureLevel { |
| int nMerge; /* Number of segments in incr-merge */ |
| int nSeg; /* Total number of segments on level */ |
| Fts5StructureSegment *aSeg; /* Array of segments. aSeg[0] is oldest. */ |
| }; |
| struct Fts5Structure { |
| int nRef; /* Object reference count */ |
| u64 nWriteCounter; /* Total leaves written to level 0 */ |
| int nSegment; /* Total segments in this structure */ |
| int nLevel; /* Number of levels in this index */ |
| Fts5StructureLevel aLevel[1]; /* Array of nLevel level objects */ |
| }; |
| |
| /* |
| ** An object of type Fts5SegWriter is used to write to segments. |
| */ |
| struct Fts5PageWriter { |
| int pgno; /* Page number for this page */ |
| int iPrevPgidx; /* Previous value written into pgidx */ |
| Fts5Buffer buf; /* Buffer containing leaf data */ |
| Fts5Buffer pgidx; /* Buffer containing page-index */ |
| Fts5Buffer term; /* Buffer containing previous term on page */ |
| }; |
| struct Fts5DlidxWriter { |
| int pgno; /* Page number for this page */ |
| int bPrevValid; /* True if iPrev is valid */ |
| i64 iPrev; /* Previous rowid value written to page */ |
| Fts5Buffer buf; /* Buffer containing page data */ |
| }; |
| struct Fts5SegWriter { |
| int iSegid; /* Segid to write to */ |
| Fts5PageWriter writer; /* PageWriter object */ |
| i64 iPrevRowid; /* Previous rowid written to current leaf */ |
| u8 bFirstRowidInDoclist; /* True if next rowid is first in doclist */ |
| u8 bFirstRowidInPage; /* True if next rowid is first in page */ |
| /* TODO1: Can use (writer.pgidx.n==0) instead of bFirstTermInPage */ |
| u8 bFirstTermInPage; /* True if next term will be first in leaf */ |
| int nLeafWritten; /* Number of leaf pages written */ |
| int nEmpty; /* Number of contiguous term-less nodes */ |
| |
| int nDlidx; /* Allocated size of aDlidx[] array */ |
| Fts5DlidxWriter *aDlidx; /* Array of Fts5DlidxWriter objects */ |
| |
| /* Values to insert into the %_idx table */ |
| Fts5Buffer btterm; /* Next term to insert into %_idx table */ |
| int iBtPage; /* Page number corresponding to btterm */ |
| }; |
| |
| typedef struct Fts5CResult Fts5CResult; |
| struct Fts5CResult { |
| u16 iFirst; /* aSeg[] index of firstest iterator */ |
| u8 bTermEq; /* True if the terms are equal */ |
| }; |
| |
| /* |
| ** Object for iterating through a single segment, visiting each term/rowid |
| ** pair in the segment. |
| ** |
| ** pSeg: |
| ** The segment to iterate through. |
| ** |
| ** iLeafPgno: |
| ** Current leaf page number within segment. |
| ** |
| ** iLeafOffset: |
| ** Byte offset within the current leaf that is the first byte of the |
| ** position list data (one byte passed the position-list size field). |
| ** rowid field of the current entry. Usually this is the size field of the |
| ** position list data. The exception is if the rowid for the current entry |
| ** is the last thing on the leaf page. |
| ** |
| ** pLeaf: |
| ** Buffer containing current leaf page data. Set to NULL at EOF. |
| ** |
| ** iTermLeafPgno, iTermLeafOffset: |
| ** Leaf page number containing the last term read from the segment. And |
| ** the offset immediately following the term data. |
| ** |
| ** flags: |
| ** Mask of FTS5_SEGITER_XXX values. Interpreted as follows: |
| ** |
| ** FTS5_SEGITER_ONETERM: |
| ** If set, set the iterator to point to EOF after the current doclist |
| ** has been exhausted. Do not proceed to the next term in the segment. |
| ** |
| ** FTS5_SEGITER_REVERSE: |
| ** This flag is only ever set if FTS5_SEGITER_ONETERM is also set. If |
| ** it is set, iterate through rowid in descending order instead of the |
| ** default ascending order. |
| ** |
| ** iRowidOffset/nRowidOffset/aRowidOffset: |
| ** These are used if the FTS5_SEGITER_REVERSE flag is set. |
| ** |
| ** For each rowid on the page corresponding to the current term, the |
| ** corresponding aRowidOffset[] entry is set to the byte offset of the |
| ** start of the "position-list-size" field within the page. |
| ** |
| ** iTermIdx: |
| ** Index of current term on iTermLeafPgno. |
| */ |
| struct Fts5SegIter { |
| Fts5StructureSegment *pSeg; /* Segment to iterate through */ |
| int flags; /* Mask of configuration flags */ |
| int iLeafPgno; /* Current leaf page number */ |
| Fts5Data *pLeaf; /* Current leaf data */ |
| Fts5Data *pNextLeaf; /* Leaf page (iLeafPgno+1) */ |
| int iLeafOffset; /* Byte offset within current leaf */ |
| |
| /* Next method */ |
| void (*xNext)(Fts5Index*, Fts5SegIter*, int*); |
| |
| /* The page and offset from which the current term was read. The offset |
| ** is the offset of the first rowid in the current doclist. */ |
| int iTermLeafPgno; |
| int iTermLeafOffset; |
| |
| int iPgidxOff; /* Next offset in pgidx */ |
| int iEndofDoclist; |
| |
| /* The following are only used if the FTS5_SEGITER_REVERSE flag is set. */ |
| int iRowidOffset; /* Current entry in aRowidOffset[] */ |
| int nRowidOffset; /* Allocated size of aRowidOffset[] array */ |
| int *aRowidOffset; /* Array of offset to rowid fields */ |
| |
| Fts5DlidxIter *pDlidx; /* If there is a doclist-index */ |
| |
| /* Variables populated based on current entry. */ |
| Fts5Buffer term; /* Current term */ |
| i64 iRowid; /* Current rowid */ |
| int nPos; /* Number of bytes in current position list */ |
| u8 bDel; /* True if the delete flag is set */ |
| }; |
| |
| /* |
| ** Argument is a pointer to an Fts5Data structure that contains a |
| ** leaf page. |
| */ |
| #define ASSERT_SZLEAF_OK(x) assert( \ |
| (x)->szLeaf==(x)->nn || (x)->szLeaf==fts5GetU16(&(x)->p[2]) \ |
| ) |
| |
| #define FTS5_SEGITER_ONETERM 0x01 |
| #define FTS5_SEGITER_REVERSE 0x02 |
| |
| /* |
| ** Argument is a pointer to an Fts5Data structure that contains a leaf |
| ** page. This macro evaluates to true if the leaf contains no terms, or |
| ** false if it contains at least one term. |
| */ |
| #define fts5LeafIsTermless(x) ((x)->szLeaf >= (x)->nn) |
| |
| #define fts5LeafTermOff(x, i) (fts5GetU16(&(x)->p[(x)->szLeaf + (i)*2])) |
| |
| #define fts5LeafFirstRowidOff(x) (fts5GetU16((x)->p)) |
| |
| /* |
| ** Object for iterating through the merged results of one or more segments, |
| ** visiting each term/rowid pair in the merged data. |
| ** |
| ** nSeg is always a power of two greater than or equal to the number of |
| ** segments that this object is merging data from. Both the aSeg[] and |
| ** aFirst[] arrays are sized at nSeg entries. The aSeg[] array is padded |
| ** with zeroed objects - these are handled as if they were iterators opened |
| ** on empty segments. |
| ** |
| ** The results of comparing segments aSeg[N] and aSeg[N+1], where N is an |
| ** even number, is stored in aFirst[(nSeg+N)/2]. The "result" of the |
| ** comparison in this context is the index of the iterator that currently |
| ** points to the smaller term/rowid combination. Iterators at EOF are |
| ** considered to be greater than all other iterators. |
| ** |
| ** aFirst[1] contains the index in aSeg[] of the iterator that points to |
| ** the smallest key overall. aFirst[0] is unused. |
| ** |
| ** poslist: |
| ** Used by sqlite3Fts5IterPoslist() when the poslist needs to be buffered. |
| ** There is no way to tell if this is populated or not. |
| */ |
| struct Fts5Iter { |
| Fts5IndexIter base; /* Base class containing output vars */ |
| |
| Fts5Index *pIndex; /* Index that owns this iterator */ |
| Fts5Structure *pStruct; /* Database structure for this iterator */ |
| Fts5Buffer poslist; /* Buffer containing current poslist */ |
| Fts5Colset *pColset; /* Restrict matches to these columns */ |
| |
| /* Invoked to set output variables. */ |
| void (*xSetOutputs)(Fts5Iter*, Fts5SegIter*); |
| |
| int nSeg; /* Size of aSeg[] array */ |
| int bRev; /* True to iterate in reverse order */ |
| u8 bSkipEmpty; /* True to skip deleted entries */ |
| |
| i64 iSwitchRowid; /* Firstest rowid of other than aFirst[1] */ |
| Fts5CResult *aFirst; /* Current merge state (see above) */ |
| Fts5SegIter aSeg[1]; /* Array of segment iterators */ |
| }; |
| |
| |
| /* |
| ** An instance of the following type is used to iterate through the contents |
| ** of a doclist-index record. |
| ** |
| ** pData: |
| ** Record containing the doclist-index data. |
| ** |
| ** bEof: |
| ** Set to true once iterator has reached EOF. |
| ** |
| ** iOff: |
| ** Set to the current offset within record pData. |
| */ |
| struct Fts5DlidxLvl { |
| Fts5Data *pData; /* Data for current page of this level */ |
| int iOff; /* Current offset into pData */ |
| int bEof; /* At EOF already */ |
| int iFirstOff; /* Used by reverse iterators */ |
| |
| /* Output variables */ |
| int iLeafPgno; /* Page number of current leaf page */ |
| i64 iRowid; /* First rowid on leaf iLeafPgno */ |
| }; |
| struct Fts5DlidxIter { |
| int nLvl; |
| int iSegid; |
| Fts5DlidxLvl aLvl[1]; |
| }; |
| |
| static void fts5PutU16(u8 *aOut, u16 iVal){ |
| aOut[0] = (iVal>>8); |
| aOut[1] = (iVal&0xFF); |
| } |
| |
| static u16 fts5GetU16(const u8 *aIn){ |
| return ((u16)aIn[0] << 8) + aIn[1]; |
| } |
| |
| /* |
| ** Allocate and return a buffer at least nByte bytes in size. |
| ** |
| ** If an OOM error is encountered, return NULL and set the error code in |
| ** the Fts5Index handle passed as the first argument. |
| */ |
| static void *fts5IdxMalloc(Fts5Index *p, int nByte){ |
| return sqlite3Fts5MallocZero(&p->rc, nByte); |
| } |
| |
| /* |
| ** Compare the contents of the pLeft buffer with the pRight/nRight blob. |
| ** |
| ** Return -ve if pLeft is smaller than pRight, 0 if they are equal or |
| ** +ve if pRight is smaller than pLeft. In other words: |
| ** |
| ** res = *pLeft - *pRight |
| */ |
| #ifdef SQLITE_DEBUG |
| static int fts5BufferCompareBlob( |
| Fts5Buffer *pLeft, /* Left hand side of comparison */ |
| const u8 *pRight, int nRight /* Right hand side of comparison */ |
| ){ |
| int nCmp = MIN(pLeft->n, nRight); |
| int res = memcmp(pLeft->p, pRight, nCmp); |
| return (res==0 ? (pLeft->n - nRight) : res); |
| } |
| #endif |
| |
| /* |
| ** Compare the contents of the two buffers using memcmp(). If one buffer |
| ** is a prefix of the other, it is considered the lesser. |
| ** |
| ** Return -ve if pLeft is smaller than pRight, 0 if they are equal or |
| ** +ve if pRight is smaller than pLeft. In other words: |
| ** |
| ** res = *pLeft - *pRight |
| */ |
| static int fts5BufferCompare(Fts5Buffer *pLeft, Fts5Buffer *pRight){ |
| int nCmp = MIN(pLeft->n, pRight->n); |
| int res = memcmp(pLeft->p, pRight->p, nCmp); |
| return (res==0 ? (pLeft->n - pRight->n) : res); |
| } |
| |
| static int fts5LeafFirstTermOff(Fts5Data *pLeaf){ |
| int ret; |
| fts5GetVarint32(&pLeaf->p[pLeaf->szLeaf], ret); |
| return ret; |
| } |
| |
| /* |
| ** Close the read-only blob handle, if it is open. |
| */ |
| static void fts5CloseReader(Fts5Index *p){ |
| if( p->pReader ){ |
| sqlite3_blob *pReader = p->pReader; |
| p->pReader = 0; |
| sqlite3_blob_close(pReader); |
| } |
| } |
| |
| /* |
| ** Retrieve a record from the %_data table. |
| ** |
| ** If an error occurs, NULL is returned and an error left in the |
| ** Fts5Index object. |
| */ |
| static Fts5Data *fts5DataRead(Fts5Index *p, i64 iRowid){ |
| Fts5Data *pRet = 0; |
| if( p->rc==SQLITE_OK ){ |
| int rc = SQLITE_OK; |
| |
| if( p->pReader ){ |
| /* This call may return SQLITE_ABORT if there has been a savepoint |
| ** rollback since it was last used. In this case a new blob handle |
| ** is required. */ |
| sqlite3_blob *pBlob = p->pReader; |
| p->pReader = 0; |
| rc = sqlite3_blob_reopen(pBlob, iRowid); |
| assert( p->pReader==0 ); |
| p->pReader = pBlob; |
| if( rc!=SQLITE_OK ){ |
| fts5CloseReader(p); |
| } |
| if( rc==SQLITE_ABORT ) rc = SQLITE_OK; |
| } |
| |
| /* If the blob handle is not open at this point, open it and seek |
| ** to the requested entry. */ |
| if( p->pReader==0 && rc==SQLITE_OK ){ |
| Fts5Config *pConfig = p->pConfig; |
| rc = sqlite3_blob_open(pConfig->db, |
| pConfig->zDb, p->zDataTbl, "block", iRowid, 0, &p->pReader |
| ); |
| } |
| |
| /* If either of the sqlite3_blob_open() or sqlite3_blob_reopen() calls |
| ** above returned SQLITE_ERROR, return SQLITE_CORRUPT_VTAB instead. |
| ** All the reasons those functions might return SQLITE_ERROR - missing |
| ** table, missing row, non-blob/text in block column - indicate |
| ** backing store corruption. */ |
| if( rc==SQLITE_ERROR ) rc = FTS5_CORRUPT; |
| |
| if( rc==SQLITE_OK ){ |
| u8 *aOut = 0; /* Read blob data into this buffer */ |
| int nByte = sqlite3_blob_bytes(p->pReader); |
| int nAlloc = sizeof(Fts5Data) + nByte + FTS5_DATA_PADDING; |
| pRet = (Fts5Data*)sqlite3_malloc(nAlloc); |
| if( pRet ){ |
| pRet->nn = nByte; |
| aOut = pRet->p = (u8*)&pRet[1]; |
| }else{ |
| rc = SQLITE_NOMEM; |
| } |
| |
| if( rc==SQLITE_OK ){ |
| rc = sqlite3_blob_read(p->pReader, aOut, nByte, 0); |
| } |
| if( rc!=SQLITE_OK ){ |
| sqlite3_free(pRet); |
| pRet = 0; |
| }else{ |
| /* TODO1: Fix this */ |
| pRet->szLeaf = fts5GetU16(&pRet->p[2]); |
| } |
| } |
| p->rc = rc; |
| p->nRead++; |
| } |
| |
| assert( (pRet==0)==(p->rc!=SQLITE_OK) ); |
| return pRet; |
| } |
| |
| /* |
| ** Release a reference to data record returned by an earlier call to |
| ** fts5DataRead(). |
| */ |
| static void fts5DataRelease(Fts5Data *pData){ |
| sqlite3_free(pData); |
| } |
| |
| static Fts5Data *fts5LeafRead(Fts5Index *p, i64 iRowid){ |
| Fts5Data *pRet = fts5DataRead(p, iRowid); |
| if( pRet ){ |
| if( pRet->szLeaf>pRet->nn ){ |
| p->rc = FTS5_CORRUPT; |
| fts5DataRelease(pRet); |
| pRet = 0; |
| } |
| } |
| return pRet; |
| } |
| |
| static int fts5IndexPrepareStmt( |
| Fts5Index *p, |
| sqlite3_stmt **ppStmt, |
| char *zSql |
| ){ |
| if( p->rc==SQLITE_OK ){ |
| if( zSql ){ |
| p->rc = sqlite3_prepare_v3(p->pConfig->db, zSql, -1, |
| SQLITE_PREPARE_PERSISTENT, ppStmt, 0); |
| }else{ |
| p->rc = SQLITE_NOMEM; |
| } |
| } |
| sqlite3_free(zSql); |
| return p->rc; |
| } |
| |
| |
| /* |
| ** INSERT OR REPLACE a record into the %_data table. |
| */ |
| static void fts5DataWrite(Fts5Index *p, i64 iRowid, const u8 *pData, int nData){ |
| if( p->rc!=SQLITE_OK ) return; |
| |
| if( p->pWriter==0 ){ |
| Fts5Config *pConfig = p->pConfig; |
| fts5IndexPrepareStmt(p, &p->pWriter, sqlite3_mprintf( |
| "REPLACE INTO '%q'.'%q_data'(id, block) VALUES(?,?)", |
| pConfig->zDb, pConfig->zName |
| )); |
| if( p->rc ) return; |
| } |
| |
| sqlite3_bind_int64(p->pWriter, 1, iRowid); |
| sqlite3_bind_blob(p->pWriter, 2, pData, nData, SQLITE_STATIC); |
| sqlite3_step(p->pWriter); |
| p->rc = sqlite3_reset(p->pWriter); |
| sqlite3_bind_null(p->pWriter, 2); |
| } |
| |
| /* |
| ** Execute the following SQL: |
| ** |
| ** DELETE FROM %_data WHERE id BETWEEN $iFirst AND $iLast |
| */ |
| static void fts5DataDelete(Fts5Index *p, i64 iFirst, i64 iLast){ |
| if( p->rc!=SQLITE_OK ) return; |
| |
| if( p->pDeleter==0 ){ |
| int rc; |
| Fts5Config *pConfig = p->pConfig; |
| char *zSql = sqlite3_mprintf( |
| "DELETE FROM '%q'.'%q_data' WHERE id>=? AND id<=?", |
| pConfig->zDb, pConfig->zName |
| ); |
| if( zSql==0 ){ |
| rc = SQLITE_NOMEM; |
| }else{ |
| rc = sqlite3_prepare_v3(pConfig->db, zSql, -1, |
| SQLITE_PREPARE_PERSISTENT, &p->pDeleter, 0); |
| sqlite3_free(zSql); |
| } |
| if( rc!=SQLITE_OK ){ |
| p->rc = rc; |
| return; |
| } |
| } |
| |
| sqlite3_bind_int64(p->pDeleter, 1, iFirst); |
| sqlite3_bind_int64(p->pDeleter, 2, iLast); |
| sqlite3_step(p->pDeleter); |
| p->rc = sqlite3_reset(p->pDeleter); |
| } |
| |
| /* |
| ** Remove all records associated with segment iSegid. |
| */ |
| static void fts5DataRemoveSegment(Fts5Index *p, int iSegid){ |
| i64 iFirst = FTS5_SEGMENT_ROWID(iSegid, 0); |
| i64 iLast = FTS5_SEGMENT_ROWID(iSegid+1, 0)-1; |
| fts5DataDelete(p, iFirst, iLast); |
| if( p->pIdxDeleter==0 ){ |
| Fts5Config *pConfig = p->pConfig; |
| fts5IndexPrepareStmt(p, &p->pIdxDeleter, sqlite3_mprintf( |
| "DELETE FROM '%q'.'%q_idx' WHERE segid=?", |
| pConfig->zDb, pConfig->zName |
| )); |
| } |
| if( p->rc==SQLITE_OK ){ |
| sqlite3_bind_int(p->pIdxDeleter, 1, iSegid); |
| sqlite3_step(p->pIdxDeleter); |
| p->rc = sqlite3_reset(p->pIdxDeleter); |
| } |
| } |
| |
| /* |
| ** Release a reference to an Fts5Structure object returned by an earlier |
| ** call to fts5StructureRead() or fts5StructureDecode(). |
| */ |
| static void fts5StructureRelease(Fts5Structure *pStruct){ |
| if( pStruct && 0>=(--pStruct->nRef) ){ |
| int i; |
| assert( pStruct->nRef==0 ); |
| for(i=0; i<pStruct->nLevel; i++){ |
| sqlite3_free(pStruct->aLevel[i].aSeg); |
| } |
| sqlite3_free(pStruct); |
| } |
| } |
| |
| static void fts5StructureRef(Fts5Structure *pStruct){ |
| pStruct->nRef++; |
| } |
| |
| /* |
| ** Deserialize and return the structure record currently stored in serialized |
| ** form within buffer pData/nData. |
| ** |
| ** The Fts5Structure.aLevel[] and each Fts5StructureLevel.aSeg[] array |
| ** are over-allocated by one slot. This allows the structure contents |
| ** to be more easily edited. |
| ** |
| ** If an error occurs, *ppOut is set to NULL and an SQLite error code |
| ** returned. Otherwise, *ppOut is set to point to the new object and |
| ** SQLITE_OK returned. |
| */ |
| static int fts5StructureDecode( |
| const u8 *pData, /* Buffer containing serialized structure */ |
| int nData, /* Size of buffer pData in bytes */ |
| int *piCookie, /* Configuration cookie value */ |
| Fts5Structure **ppOut /* OUT: Deserialized object */ |
| ){ |
| int rc = SQLITE_OK; |
| int i = 0; |
| int iLvl; |
| int nLevel = 0; |
| int nSegment = 0; |
| int nByte; /* Bytes of space to allocate at pRet */ |
| Fts5Structure *pRet = 0; /* Structure object to return */ |
| |
| /* Grab the cookie value */ |
| if( piCookie ) *piCookie = sqlite3Fts5Get32(pData); |
| i = 4; |
| |
| /* Read the total number of levels and segments from the start of the |
| ** structure record. */ |
| i += fts5GetVarint32(&pData[i], nLevel); |
| i += fts5GetVarint32(&pData[i], nSegment); |
| nByte = ( |
| sizeof(Fts5Structure) + /* Main structure */ |
| sizeof(Fts5StructureLevel) * (nLevel-1) /* aLevel[] array */ |
| ); |
| pRet = (Fts5Structure*)sqlite3Fts5MallocZero(&rc, nByte); |
| |
| if( pRet ){ |
| pRet->nRef = 1; |
| pRet->nLevel = nLevel; |
| pRet->nSegment = nSegment; |
| i += sqlite3Fts5GetVarint(&pData[i], &pRet->nWriteCounter); |
| |
| for(iLvl=0; rc==SQLITE_OK && iLvl<nLevel; iLvl++){ |
| Fts5StructureLevel *pLvl = &pRet->aLevel[iLvl]; |
| int nTotal = 0; |
| int iSeg; |
| |
| if( i>=nData ){ |
| rc = FTS5_CORRUPT; |
| }else{ |
| i += fts5GetVarint32(&pData[i], pLvl->nMerge); |
| i += fts5GetVarint32(&pData[i], nTotal); |
| assert( nTotal>=pLvl->nMerge ); |
| pLvl->aSeg = (Fts5StructureSegment*)sqlite3Fts5MallocZero(&rc, |
| nTotal * sizeof(Fts5StructureSegment) |
| ); |
| } |
| |
| if( rc==SQLITE_OK ){ |
| pLvl->nSeg = nTotal; |
| for(iSeg=0; iSeg<nTotal; iSeg++){ |
| if( i>=nData ){ |
| rc = FTS5_CORRUPT; |
| break; |
| } |
| i += fts5GetVarint32(&pData[i], pLvl->aSeg[iSeg].iSegid); |
| i += fts5GetVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoFirst); |
| i += fts5GetVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoLast); |
| } |
| } |
| } |
| if( rc!=SQLITE_OK ){ |
| fts5StructureRelease(pRet); |
| pRet = 0; |
| } |
| } |
| |
| *ppOut = pRet; |
| return rc; |
| } |
| |
| /* |
| ** |
| */ |
| static void fts5StructureAddLevel(int *pRc, Fts5Structure **ppStruct){ |
| if( *pRc==SQLITE_OK ){ |
| Fts5Structure *pStruct = *ppStruct; |
| int nLevel = pStruct->nLevel; |
| int nByte = ( |
| sizeof(Fts5Structure) + /* Main structure */ |
| sizeof(Fts5StructureLevel) * (nLevel+1) /* aLevel[] array */ |
| ); |
| |
| pStruct = sqlite3_realloc(pStruct, nByte); |
| if( pStruct ){ |
| memset(&pStruct->aLevel[nLevel], 0, sizeof(Fts5StructureLevel)); |
| pStruct->nLevel++; |
| *ppStruct = pStruct; |
| }else{ |
| *pRc = SQLITE_NOMEM; |
| } |
| } |
| } |
| |
| /* |
| ** Extend level iLvl so that there is room for at least nExtra more |
| ** segments. |
| */ |
| static void fts5StructureExtendLevel( |
| int *pRc, |
| Fts5Structure *pStruct, |
| int iLvl, |
| int nExtra, |
| int bInsert |
| ){ |
| if( *pRc==SQLITE_OK ){ |
| Fts5StructureLevel *pLvl = &pStruct->aLevel[iLvl]; |
| Fts5StructureSegment *aNew; |
| int nByte; |
| |
| nByte = (pLvl->nSeg + nExtra) * sizeof(Fts5StructureSegment); |
| aNew = sqlite3_realloc(pLvl->aSeg, nByte); |
| if( aNew ){ |
| if( bInsert==0 ){ |
| memset(&aNew[pLvl->nSeg], 0, sizeof(Fts5StructureSegment) * nExtra); |
| }else{ |
| int nMove = pLvl->nSeg * sizeof(Fts5StructureSegment); |
| memmove(&aNew[nExtra], aNew, nMove); |
| memset(aNew, 0, sizeof(Fts5StructureSegment) * nExtra); |
| } |
| pLvl->aSeg = aNew; |
| }else{ |
| *pRc = SQLITE_NOMEM; |
| } |
| } |
| } |
| |
| static Fts5Structure *fts5StructureReadUncached(Fts5Index *p){ |
| Fts5Structure *pRet = 0; |
| Fts5Config *pConfig = p->pConfig; |
| int iCookie; /* Configuration cookie */ |
| Fts5Data *pData; |
| |
| pData = fts5DataRead(p, FTS5_STRUCTURE_ROWID); |
| if( p->rc==SQLITE_OK ){ |
| /* TODO: Do we need this if the leaf-index is appended? Probably... */ |
| memset(&pData->p[pData->nn], 0, FTS5_DATA_PADDING); |
| p->rc = fts5StructureDecode(pData->p, pData->nn, &iCookie, &pRet); |
| if( p->rc==SQLITE_OK && pConfig->iCookie!=iCookie ){ |
| p->rc = sqlite3Fts5ConfigLoad(pConfig, iCookie); |
| } |
| fts5DataRelease(pData); |
| if( p->rc!=SQLITE_OK ){ |
| fts5StructureRelease(pRet); |
| pRet = 0; |
| } |
| } |
| |
| return pRet; |
| } |
| |
| static i64 fts5IndexDataVersion(Fts5Index *p){ |
| i64 iVersion = 0; |
| |
| if( p->rc==SQLITE_OK ){ |
| if( p->pDataVersion==0 ){ |
| p->rc = fts5IndexPrepareStmt(p, &p->pDataVersion, |
| sqlite3_mprintf("PRAGMA %Q.data_version", p->pConfig->zDb) |
| ); |
| if( p->rc ) return 0; |
| } |
| |
| if( SQLITE_ROW==sqlite3_step(p->pDataVersion) ){ |
| iVersion = sqlite3_column_int64(p->pDataVersion, 0); |
| } |
| p->rc = sqlite3_reset(p->pDataVersion); |
| } |
| |
| return iVersion; |
| } |
| |
| /* |
| ** Read, deserialize and return the structure record. |
| ** |
| ** The Fts5Structure.aLevel[] and each Fts5StructureLevel.aSeg[] array |
| ** are over-allocated as described for function fts5StructureDecode() |
| ** above. |
| ** |
| ** If an error occurs, NULL is returned and an error code left in the |
| ** Fts5Index handle. If an error has already occurred when this function |
| ** is called, it is a no-op. |
| */ |
| static Fts5Structure *fts5StructureRead(Fts5Index *p){ |
| |
| if( p->pStruct==0 ){ |
| p->iStructVersion = fts5IndexDataVersion(p); |
| if( p->rc==SQLITE_OK ){ |
| p->pStruct = fts5StructureReadUncached(p); |
| } |
| } |
| |
| #if 0 |
| else{ |
| Fts5Structure *pTest = fts5StructureReadUncached(p); |
| if( pTest ){ |
| int i, j; |
| assert_nc( p->pStruct->nSegment==pTest->nSegment ); |
| assert_nc( p->pStruct->nLevel==pTest->nLevel ); |
| for(i=0; i<pTest->nLevel; i++){ |
| assert_nc( p->pStruct->aLevel[i].nMerge==pTest->aLevel[i].nMerge ); |
| assert_nc( p->pStruct->aLevel[i].nSeg==pTest->aLevel[i].nSeg ); |
| for(j=0; j<pTest->aLevel[i].nSeg; j++){ |
| Fts5StructureSegment *p1 = &pTest->aLevel[i].aSeg[j]; |
| Fts5StructureSegment *p2 = &p->pStruct->aLevel[i].aSeg[j]; |
| assert_nc( p1->iSegid==p2->iSegid ); |
| assert_nc( p1->pgnoFirst==p2->pgnoFirst ); |
| assert_nc( p1->pgnoLast==p2->pgnoLast ); |
| } |
| } |
| fts5StructureRelease(pTest); |
| } |
| } |
| #endif |
| |
| if( p->rc!=SQLITE_OK ) return 0; |
| assert( p->iStructVersion!=0 ); |
| assert( p->pStruct!=0 ); |
| fts5StructureRef(p->pStruct); |
| return p->pStruct; |
| } |
| |
| static void fts5StructureInvalidate(Fts5Index *p){ |
| if( p->pStruct ){ |
| fts5StructureRelease(p->pStruct); |
| p->pStruct = 0; |
| } |
| } |
| |
| /* |
| ** Return the total number of segments in index structure pStruct. This |
| ** function is only ever used as part of assert() conditions. |
| */ |
| #ifdef SQLITE_DEBUG |
| static int fts5StructureCountSegments(Fts5Structure *pStruct){ |
| int nSegment = 0; /* Total number of segments */ |
| if( pStruct ){ |
| int iLvl; /* Used to iterate through levels */ |
| for(iLvl=0; iLvl<pStruct->nLevel; iLvl++){ |
| nSegment += pStruct->aLevel[iLvl].nSeg; |
| } |
| } |
| |
| return nSegment; |
| } |
| #endif |
| |
| #define fts5BufferSafeAppendBlob(pBuf, pBlob, nBlob) { \ |
| assert( (pBuf)->nSpace>=((pBuf)->n+nBlob) ); \ |
| memcpy(&(pBuf)->p[(pBuf)->n], pBlob, nBlob); \ |
| (pBuf)->n += nBlob; \ |
| } |
| |
| #define fts5BufferSafeAppendVarint(pBuf, iVal) { \ |
| (pBuf)->n += sqlite3Fts5PutVarint(&(pBuf)->p[(pBuf)->n], (iVal)); \ |
| assert( (pBuf)->nSpace>=(pBuf)->n ); \ |
| } |
| |
| |
| /* |
| ** Serialize and store the "structure" record. |
| ** |
| ** If an error occurs, leave an error code in the Fts5Index object. If an |
| ** error has already occurred, this function is a no-op. |
| */ |
| static void fts5StructureWrite(Fts5Index *p, Fts5Structure *pStruct){ |
| if( p->rc==SQLITE_OK ){ |
| Fts5Buffer buf; /* Buffer to serialize record into */ |
| int iLvl; /* Used to iterate through levels */ |
| int iCookie; /* Cookie value to store */ |
| |
| assert( pStruct->nSegment==fts5StructureCountSegments(pStruct) ); |
| memset(&buf, 0, sizeof(Fts5Buffer)); |
| |
| /* Append the current configuration cookie */ |
| iCookie = p->pConfig->iCookie; |
| if( iCookie<0 ) iCookie = 0; |
| |
| if( 0==sqlite3Fts5BufferSize(&p->rc, &buf, 4+9+9+9) ){ |
| sqlite3Fts5Put32(buf.p, iCookie); |
| buf.n = 4; |
| fts5BufferSafeAppendVarint(&buf, pStruct->nLevel); |
| fts5BufferSafeAppendVarint(&buf, pStruct->nSegment); |
| fts5BufferSafeAppendVarint(&buf, (i64)pStruct->nWriteCounter); |
| } |
| |
| for(iLvl=0; iLvl<pStruct->nLevel; iLvl++){ |
| int iSeg; /* Used to iterate through segments */ |
| Fts5StructureLevel *pLvl = &pStruct->aLevel[iLvl]; |
| fts5BufferAppendVarint(&p->rc, &buf, pLvl->nMerge); |
| fts5BufferAppendVarint(&p->rc, &buf, pLvl->nSeg); |
| assert( pLvl->nMerge<=pLvl->nSeg ); |
| |
| for(iSeg=0; iSeg<pLvl->nSeg; iSeg++){ |
| fts5BufferAppendVarint(&p->rc, &buf, pLvl->aSeg[iSeg].iSegid); |
| fts5BufferAppendVarint(&p->rc, &buf, pLvl->aSeg[iSeg].pgnoFirst); |
| fts5BufferAppendVarint(&p->rc, &buf, pLvl->aSeg[iSeg].pgnoLast); |
| } |
| } |
| |
| fts5DataWrite(p, FTS5_STRUCTURE_ROWID, buf.p, buf.n); |
| fts5BufferFree(&buf); |
| } |
| } |
| |
| #if 0 |
| static void fts5DebugStructure(int*,Fts5Buffer*,Fts5Structure*); |
| static void fts5PrintStructure(const char *zCaption, Fts5Structure *pStruct){ |
| int rc = SQLITE_OK; |
| Fts5Buffer buf; |
| memset(&buf, 0, sizeof(buf)); |
| fts5DebugStructure(&rc, &buf, pStruct); |
| fprintf(stdout, "%s: %s\n", zCaption, buf.p); |
| fflush(stdout); |
| fts5BufferFree(&buf); |
| } |
| #else |
| # define fts5PrintStructure(x,y) |
| #endif |
| |
| static int fts5SegmentSize(Fts5StructureSegment *pSeg){ |
| return 1 + pSeg->pgnoLast - pSeg->pgnoFirst; |
| } |
| |
| /* |
| ** Return a copy of index structure pStruct. Except, promote as many |
| ** segments as possible to level iPromote. If an OOM occurs, NULL is |
| ** returned. |
| */ |
| static void fts5StructurePromoteTo( |
| Fts5Index *p, |
| int iPromote, |
| int szPromote, |
| Fts5Structure *pStruct |
| ){ |
| int il, is; |
| Fts5StructureLevel *pOut = &pStruct->aLevel[iPromote]; |
| |
| if( pOut->nMerge==0 ){ |
| for(il=iPromote+1; il<pStruct->nLevel; il++){ |
| Fts5StructureLevel *pLvl = &pStruct->aLevel[il]; |
| if( pLvl->nMerge ) return; |
| for(is=pLvl->nSeg-1; is>=0; is--){ |
| int sz = fts5SegmentSize(&pLvl->aSeg[is]); |
| if( sz>szPromote ) return; |
| fts5StructureExtendLevel(&p->rc, pStruct, iPromote, 1, 1); |
| if( p->rc ) return; |
| memcpy(pOut->aSeg, &pLvl->aSeg[is], sizeof(Fts5StructureSegment)); |
| pOut->nSeg++; |
| pLvl->nSeg--; |
| } |
| } |
| } |
| } |
| |
| /* |
| ** A new segment has just been written to level iLvl of index structure |
| ** pStruct. This function determines if any segments should be promoted |
| ** as a result. Segments are promoted in two scenarios: |
| ** |
| ** a) If the segment just written is smaller than one or more segments |
| ** within the previous populated level, it is promoted to the previous |
| ** populated level. |
| ** |
| ** b) If the segment just written is larger than the newest segment on |
| ** the next populated level, then that segment, and any other adjacent |
| ** segments that are also smaller than the one just written, are |
| ** promoted. |
| ** |
| ** If one or more segments are promoted, the structure object is updated |
| ** to reflect this. |
| */ |
| static void fts5StructurePromote( |
| Fts5Index *p, /* FTS5 backend object */ |
| int iLvl, /* Index level just updated */ |
| Fts5Structure *pStruct /* Index structure */ |
| ){ |
| if( p->rc==SQLITE_OK ){ |
| int iTst; |
| int iPromote = -1; |
| int szPromote = 0; /* Promote anything this size or smaller */ |
| Fts5StructureSegment *pSeg; /* Segment just written */ |
| int szSeg; /* Size of segment just written */ |
| int nSeg = pStruct->aLevel[iLvl].nSeg; |
| |
| if( nSeg==0 ) return; |
| pSeg = &pStruct->aLevel[iLvl].aSeg[pStruct->aLevel[iLvl].nSeg-1]; |
| szSeg = (1 + pSeg->pgnoLast - pSeg->pgnoFirst); |
| |
| /* Check for condition (a) */ |
| for(iTst=iLvl-1; iTst>=0 && pStruct->aLevel[iTst].nSeg==0; iTst--); |
| if( iTst>=0 ){ |
| int i; |
| int szMax = 0; |
| Fts5StructureLevel *pTst = &pStruct->aLevel[iTst]; |
| assert( pTst->nMerge==0 ); |
| for(i=0; i<pTst->nSeg; i++){ |
| int sz = pTst->aSeg[i].pgnoLast - pTst->aSeg[i].pgnoFirst + 1; |
| if( sz>szMax ) szMax = sz; |
| } |
| if( szMax>=szSeg ){ |
| /* Condition (a) is true. Promote the newest segment on level |
| ** iLvl to level iTst. */ |
| iPromote = iTst; |
| szPromote = szMax; |
| } |
| } |
| |
| /* If condition (a) is not met, assume (b) is true. StructurePromoteTo() |
| ** is a no-op if it is not. */ |
| if( iPromote<0 ){ |
| iPromote = iLvl; |
| szPromote = szSeg; |
| } |
| fts5StructurePromoteTo(p, iPromote, szPromote, pStruct); |
| } |
| } |
| |
| |
| /* |
| ** Advance the iterator passed as the only argument. If the end of the |
| ** doclist-index page is reached, return non-zero. |
| */ |
| static int fts5DlidxLvlNext(Fts5DlidxLvl *pLvl){ |
| Fts5Data *pData = pLvl->pData; |
| |
| if( pLvl->iOff==0 ){ |
| assert( pLvl->bEof==0 ); |
| pLvl->iOff = 1; |
| pLvl->iOff += fts5GetVarint32(&pData->p[1], pLvl->iLeafPgno); |
| pLvl->iOff += fts5GetVarint(&pData->p[pLvl->iOff], (u64*)&pLvl->iRowid); |
| pLvl->iFirstOff = pLvl->iOff; |
| }else{ |
| int iOff; |
| for(iOff=pLvl->iOff; iOff<pData->nn; iOff++){ |
| if( pData->p[iOff] ) break; |
| } |
| |
| if( iOff<pData->nn ){ |
| i64 iVal; |
| pLvl->iLeafPgno += (iOff - pLvl->iOff) + 1; |
| iOff += fts5GetVarint(&pData->p[iOff], (u64*)&iVal); |
| pLvl->iRowid += iVal; |
| pLvl->iOff = iOff; |
| }else{ |
| pLvl->bEof = 1; |
| } |
| } |
| |
| return pLvl->bEof; |
| } |
| |
| /* |
| ** Advance the iterator passed as the only argument. |
| */ |
| static int fts5DlidxIterNextR(Fts5Index *p, Fts5DlidxIter *pIter, int iLvl){ |
| Fts5DlidxLvl *pLvl = &pIter->aLvl[iLvl]; |
| |
| assert( iLvl<pIter->nLvl ); |
| if( fts5DlidxLvlNext(pLvl) ){ |
| if( (iLvl+1) < pIter->nLvl ){ |
| fts5DlidxIterNextR(p, pIter, iLvl+1); |
| if( pLvl[1].bEof==0 ){ |
| fts5DataRelease(pLvl->pData); |
| memset(pLvl, 0, sizeof(Fts5DlidxLvl)); |
| pLvl->pData = fts5DataRead(p, |
| FTS5_DLIDX_ROWID(pIter->iSegid, iLvl, pLvl[1].iLeafPgno) |
| ); |
| if( pLvl->pData ) fts5DlidxLvlNext(pLvl); |
| } |
| } |
| } |
| |
| return pIter->aLvl[0].bEof; |
| } |
| static int fts5DlidxIterNext(Fts5Index *p, Fts5DlidxIter *pIter){ |
| return fts5DlidxIterNextR(p, pIter, 0); |
| } |
| |
| /* |
| ** The iterator passed as the first argument has the following fields set |
| ** as follows. This function sets up the rest of the iterator so that it |
| ** points to the first rowid in the doclist-index. |
| ** |
| ** pData: |
| ** pointer to doclist-index record, |
| ** |
| ** When this function is called pIter->iLeafPgno is the page number the |
| ** doclist is associated with (the one featuring the term). |
| */ |
| static int fts5DlidxIterFirst(Fts5DlidxIter *pIter){ |
| int i; |
| for(i=0; i<pIter->nLvl; i++){ |
| fts5DlidxLvlNext(&pIter->aLvl[i]); |
| } |
| return pIter->aLvl[0].bEof; |
| } |
| |
| |
| static int fts5DlidxIterEof(Fts5Index *p, Fts5DlidxIter *pIter){ |
| return p->rc!=SQLITE_OK || pIter->aLvl[0].bEof; |
| } |
| |
| static void fts5DlidxIterLast(Fts5Index *p, Fts5DlidxIter *pIter){ |
| int i; |
| |
| /* Advance each level to the last entry on the last page */ |
| for(i=pIter->nLvl-1; p->rc==SQLITE_OK && i>=0; i--){ |
| Fts5DlidxLvl *pLvl = &pIter->aLvl[i]; |
| while( fts5DlidxLvlNext(pLvl)==0 ); |
| pLvl->bEof = 0; |
| |
| if( i>0 ){ |
| Fts5DlidxLvl *pChild = &pLvl[-1]; |
| fts5DataRelease(pChild->pData); |
| memset(pChild, 0, sizeof(Fts5DlidxLvl)); |
| pChild->pData = fts5DataRead(p, |
| FTS5_DLIDX_ROWID(pIter->iSegid, i-1, pLvl->iLeafPgno) |
| ); |
| } |
| } |
| } |
| |
| /* |
| ** Move the iterator passed as the only argument to the previous entry. |
| */ |
| static int fts5DlidxLvlPrev(Fts5DlidxLvl *pLvl){ |
| int iOff = pLvl->iOff; |
| |
| assert( pLvl->bEof==0 ); |
| if( iOff<=pLvl->iFirstOff ){ |
| pLvl->bEof = 1; |
| }else{ |
| u8 *a = pLvl->pData->p; |
| i64 iVal; |
| int iLimit; |
| int ii; |
| int nZero = 0; |
| |
| /* Currently iOff points to the first byte of a varint. This block |
| ** decrements iOff until it points to the first byte of the previous |
| ** varint. Taking care not to read any memory locations that occur |
| ** before the buffer in memory. */ |
| iLimit = (iOff>9 ? iOff-9 : 0); |
| for(iOff--; iOff>iLimit; iOff--){ |
| if( (a[iOff-1] & 0x80)==0 ) break; |
| } |
| |
| fts5GetVarint(&a[iOff], (u64*)&iVal); |
| pLvl->iRowid -= iVal; |
| pLvl->iLeafPgno--; |
| |
| /* Skip backwards past any 0x00 varints. */ |
| for(ii=iOff-1; ii>=pLvl->iFirstOff && a[ii]==0x00; ii--){ |
| nZero++; |
| } |
| if( ii>=pLvl->iFirstOff && (a[ii] & 0x80) ){ |
| /* The byte immediately before the last 0x00 byte has the 0x80 bit |
| ** set. So the last 0x00 is only a varint 0 if there are 8 more 0x80 |
| ** bytes before a[ii]. */ |
| int bZero = 0; /* True if last 0x00 counts */ |
| if( (ii-8)>=pLvl->iFirstOff ){ |
| int j; |
| for(j=1; j<=8 && (a[ii-j] & 0x80); j++); |
| bZero = (j>8); |
| } |
| if( bZero==0 ) nZero--; |
| } |
| pLvl->iLeafPgno -= nZero; |
| pLvl->iOff = iOff - nZero; |
| } |
| |
| return pLvl->bEof; |
| } |
| |
| static int fts5DlidxIterPrevR(Fts5Index *p, Fts5DlidxIter *pIter, int iLvl){ |
| Fts5DlidxLvl *pLvl = &pIter->aLvl[iLvl]; |
| |
| assert( iLvl<pIter->nLvl ); |
| if( fts5DlidxLvlPrev(pLvl) ){ |
| if( (iLvl+1) < pIter->nLvl ){ |
| fts5DlidxIterPrevR(p, pIter, iLvl+1); |
| if( pLvl[1].bEof==0 ){ |
| fts5DataRelease(pLvl->pData); |
| memset(pLvl, 0, sizeof(Fts5DlidxLvl)); |
| pLvl->pData = fts5DataRead(p, |
| FTS5_DLIDX_ROWID(pIter->iSegid, iLvl, pLvl[1].iLeafPgno) |
| ); |
| if( pLvl->pData ){ |
| while( fts5DlidxLvlNext(pLvl)==0 ); |
| pLvl->bEof = 0; |
| } |
| } |
| } |
| } |
| |
| return pIter->aLvl[0].bEof; |
| } |
| static int fts5DlidxIterPrev(Fts5Index *p, Fts5DlidxIter *pIter){ |
| return fts5DlidxIterPrevR(p, pIter, 0); |
| } |
| |
| /* |
| ** Free a doclist-index iterator object allocated by fts5DlidxIterInit(). |
| */ |
| static void fts5DlidxIterFree(Fts5DlidxIter *pIter){ |
| if( pIter ){ |
| int i; |
| for(i=0; i<pIter->nLvl; i++){ |
| fts5DataRelease(pIter->aLvl[i].pData); |
| } |
| sqlite3_free(pIter); |
| } |
| } |
| |
| static Fts5DlidxIter *fts5DlidxIterInit( |
| Fts5Index *p, /* Fts5 Backend to iterate within */ |
| int bRev, /* True for ORDER BY ASC */ |
| int iSegid, /* Segment id */ |
| int iLeafPg /* Leaf page number to load dlidx for */ |
| ){ |
| Fts5DlidxIter *pIter = 0; |
| int i; |
| int bDone = 0; |
| |
| for(i=0; p->rc==SQLITE_OK && bDone==0; i++){ |
| int nByte = sizeof(Fts5DlidxIter) + i * sizeof(Fts5DlidxLvl); |
| Fts5DlidxIter *pNew; |
| |
| pNew = (Fts5DlidxIter*)sqlite3_realloc(pIter, nByte); |
| if( pNew==0 ){ |
| p->rc = SQLITE_NOMEM; |
| }else{ |
| i64 iRowid = FTS5_DLIDX_ROWID(iSegid, i, iLeafPg); |
| Fts5DlidxLvl *pLvl = &pNew->aLvl[i]; |
| pIter = pNew; |
| memset(pLvl, 0, sizeof(Fts5DlidxLvl)); |
| pLvl->pData = fts5DataRead(p, iRowid); |
| if( pLvl->pData && (pLvl->pData->p[0] & 0x0001)==0 ){ |
| bDone = 1; |
| } |
| pIter->nLvl = i+1; |
| } |
| } |
| |
| if( p->rc==SQLITE_OK ){ |
| pIter->iSegid = iSegid; |
| if( bRev==0 ){ |
| fts5DlidxIterFirst(pIter); |
| }else{ |
| fts5DlidxIterLast(p, pIter); |
| } |
| } |
| |
| if( p->rc!=SQLITE_OK ){ |
| fts5DlidxIterFree(pIter); |
| pIter = 0; |
| } |
| |
| return pIter; |
| } |
| |
| static i64 fts5DlidxIterRowid(Fts5DlidxIter *pIter){ |
| return pIter->aLvl[0].iRowid; |
| } |
| static int fts5DlidxIterPgno(Fts5DlidxIter *pIter){ |
| return pIter->aLvl[0].iLeafPgno; |
| } |
| |
| /* |
| ** Load the next leaf page into the segment iterator. |
| */ |
| static void fts5SegIterNextPage( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5SegIter *pIter /* Iterator to advance to next page */ |
| ){ |
| Fts5Data *pLeaf; |
| Fts5StructureSegment *pSeg = pIter->pSeg; |
| fts5DataRelease(pIter->pLeaf); |
| pIter->iLeafPgno++; |
| if( pIter->pNextLeaf ){ |
| pIter->pLeaf = pIter->pNextLeaf; |
| pIter->pNextLeaf = 0; |
| }else if( pIter->iLeafPgno<=pSeg->pgnoLast ){ |
| pIter->pLeaf = fts5LeafRead(p, |
| FTS5_SEGMENT_ROWID(pSeg->iSegid, pIter->iLeafPgno) |
| ); |
| }else{ |
| pIter->pLeaf = 0; |
| } |
| pLeaf = pIter->pLeaf; |
| |
| if( pLeaf ){ |
| pIter->iPgidxOff = pLeaf->szLeaf; |
| if( fts5LeafIsTermless(pLeaf) ){ |
| pIter->iEndofDoclist = pLeaf->nn+1; |
| }else{ |
| pIter->iPgidxOff += fts5GetVarint32(&pLeaf->p[pIter->iPgidxOff], |
| pIter->iEndofDoclist |
| ); |
| } |
| } |
| } |
| |
| /* |
| ** Argument p points to a buffer containing a varint to be interpreted as a |
| ** position list size field. Read the varint and return the number of bytes |
| ** read. Before returning, set *pnSz to the number of bytes in the position |
| ** list, and *pbDel to true if the delete flag is set, or false otherwise. |
| */ |
| static int fts5GetPoslistSize(const u8 *p, int *pnSz, int *pbDel){ |
| int nSz; |
| int n = 0; |
| fts5FastGetVarint32(p, n, nSz); |
| assert_nc( nSz>=0 ); |
| *pnSz = nSz/2; |
| *pbDel = nSz & 0x0001; |
| return n; |
| } |
| |
| /* |
| ** Fts5SegIter.iLeafOffset currently points to the first byte of a |
| ** position-list size field. Read the value of the field and store it |
| ** in the following variables: |
| ** |
| ** Fts5SegIter.nPos |
| ** Fts5SegIter.bDel |
| ** |
| ** Leave Fts5SegIter.iLeafOffset pointing to the first byte of the |
| ** position list content (if any). |
| */ |
| static void fts5SegIterLoadNPos(Fts5Index *p, Fts5SegIter *pIter){ |
| if( p->rc==SQLITE_OK ){ |
| int iOff = pIter->iLeafOffset; /* Offset to read at */ |
| ASSERT_SZLEAF_OK(pIter->pLeaf); |
| if( p->pConfig->eDetail==FTS5_DETAIL_NONE ){ |
| int iEod = MIN(pIter->iEndofDoclist, pIter->pLeaf->szLeaf); |
| pIter->bDel = 0; |
| pIter->nPos = 1; |
| if( iOff<iEod && pIter->pLeaf->p[iOff]==0 ){ |
| pIter->bDel = 1; |
| iOff++; |
| if( iOff<iEod && pIter->pLeaf->p[iOff]==0 ){ |
| pIter->nPos = 1; |
| iOff++; |
| }else{ |
| pIter->nPos = 0; |
| } |
| } |
| }else{ |
| int nSz; |
| fts5FastGetVarint32(pIter->pLeaf->p, iOff, nSz); |
| pIter->bDel = (nSz & 0x0001); |
| pIter->nPos = nSz>>1; |
| assert_nc( pIter->nPos>=0 ); |
| } |
| pIter->iLeafOffset = iOff; |
| } |
| } |
| |
| static void fts5SegIterLoadRowid(Fts5Index *p, Fts5SegIter *pIter){ |
| u8 *a = pIter->pLeaf->p; /* Buffer to read data from */ |
| int iOff = pIter->iLeafOffset; |
| |
| ASSERT_SZLEAF_OK(pIter->pLeaf); |
| if( iOff>=pIter->pLeaf->szLeaf ){ |
| fts5SegIterNextPage(p, pIter); |
| if( pIter->pLeaf==0 ){ |
| if( p->rc==SQLITE_OK ) p->rc = FTS5_CORRUPT; |
| return; |
| } |
| iOff = 4; |
| a = pIter->pLeaf->p; |
| } |
| iOff += sqlite3Fts5GetVarint(&a[iOff], (u64*)&pIter->iRowid); |
| pIter->iLeafOffset = iOff; |
| } |
| |
| /* |
| ** Fts5SegIter.iLeafOffset currently points to the first byte of the |
| ** "nSuffix" field of a term. Function parameter nKeep contains the value |
| ** of the "nPrefix" field (if there was one - it is passed 0 if this is |
| ** the first term in the segment). |
| ** |
| ** This function populates: |
| ** |
| ** Fts5SegIter.term |
| ** Fts5SegIter.rowid |
| ** |
| ** accordingly and leaves (Fts5SegIter.iLeafOffset) set to the content of |
| ** the first position list. The position list belonging to document |
| ** (Fts5SegIter.iRowid). |
| */ |
| static void fts5SegIterLoadTerm(Fts5Index *p, Fts5SegIter *pIter, int nKeep){ |
| u8 *a = pIter->pLeaf->p; /* Buffer to read data from */ |
| int iOff = pIter->iLeafOffset; /* Offset to read at */ |
| int nNew; /* Bytes of new data */ |
| |
| iOff += fts5GetVarint32(&a[iOff], nNew); |
| if( iOff+nNew>pIter->pLeaf->nn ){ |
| p->rc = FTS5_CORRUPT; |
| return; |
| } |
| pIter->term.n = nKeep; |
| fts5BufferAppendBlob(&p->rc, &pIter->term, nNew, &a[iOff]); |
| iOff += nNew; |
| pIter->iTermLeafOffset = iOff; |
| pIter->iTermLeafPgno = pIter->iLeafPgno; |
| pIter->iLeafOffset = iOff; |
| |
| if( pIter->iPgidxOff>=pIter->pLeaf->nn ){ |
| pIter->iEndofDoclist = pIter->pLeaf->nn+1; |
| }else{ |
| int nExtra; |
| pIter->iPgidxOff += fts5GetVarint32(&a[pIter->iPgidxOff], nExtra); |
| pIter->iEndofDoclist += nExtra; |
| } |
| |
| fts5SegIterLoadRowid(p, pIter); |
| } |
| |
| static void fts5SegIterNext(Fts5Index*, Fts5SegIter*, int*); |
| static void fts5SegIterNext_Reverse(Fts5Index*, Fts5SegIter*, int*); |
| static void fts5SegIterNext_None(Fts5Index*, Fts5SegIter*, int*); |
| |
| static void fts5SegIterSetNext(Fts5Index *p, Fts5SegIter *pIter){ |
| if( pIter->flags & FTS5_SEGITER_REVERSE ){ |
| pIter->xNext = fts5SegIterNext_Reverse; |
| }else if( p->pConfig->eDetail==FTS5_DETAIL_NONE ){ |
| pIter->xNext = fts5SegIterNext_None; |
| }else{ |
| pIter->xNext = fts5SegIterNext; |
| } |
| } |
| |
| /* |
| ** Initialize the iterator object pIter to iterate through the entries in |
| ** segment pSeg. The iterator is left pointing to the first entry when |
| ** this function returns. |
| ** |
| ** If an error occurs, Fts5Index.rc is set to an appropriate error code. If |
| ** an error has already occurred when this function is called, it is a no-op. |
| */ |
| static void fts5SegIterInit( |
| Fts5Index *p, /* FTS index object */ |
| Fts5StructureSegment *pSeg, /* Description of segment */ |
| Fts5SegIter *pIter /* Object to populate */ |
| ){ |
| if( pSeg->pgnoFirst==0 ){ |
| /* This happens if the segment is being used as an input to an incremental |
| ** merge and all data has already been "trimmed". See function |
| ** fts5TrimSegments() for details. In this case leave the iterator empty. |
| ** The caller will see the (pIter->pLeaf==0) and assume the iterator is |
| ** at EOF already. */ |
| assert( pIter->pLeaf==0 ); |
| return; |
| } |
| |
| if( p->rc==SQLITE_OK ){ |
| memset(pIter, 0, sizeof(*pIter)); |
| fts5SegIterSetNext(p, pIter); |
| pIter->pSeg = pSeg; |
| pIter->iLeafPgno = pSeg->pgnoFirst-1; |
| fts5SegIterNextPage(p, pIter); |
| } |
| |
| if( p->rc==SQLITE_OK ){ |
| pIter->iLeafOffset = 4; |
| assert_nc( pIter->pLeaf->nn>4 ); |
| assert( fts5LeafFirstTermOff(pIter->pLeaf)==4 ); |
| pIter->iPgidxOff = pIter->pLeaf->szLeaf+1; |
| fts5SegIterLoadTerm(p, pIter, 0); |
| fts5SegIterLoadNPos(p, pIter); |
| } |
| } |
| |
| /* |
| ** This function is only ever called on iterators created by calls to |
| ** Fts5IndexQuery() with the FTS5INDEX_QUERY_DESC flag set. |
| ** |
| ** The iterator is in an unusual state when this function is called: the |
| ** Fts5SegIter.iLeafOffset variable is set to the offset of the start of |
| ** the position-list size field for the first relevant rowid on the page. |
| ** Fts5SegIter.rowid is set, but nPos and bDel are not. |
| ** |
| ** This function advances the iterator so that it points to the last |
| ** relevant rowid on the page and, if necessary, initializes the |
| ** aRowidOffset[] and iRowidOffset variables. At this point the iterator |
| ** is in its regular state - Fts5SegIter.iLeafOffset points to the first |
| ** byte of the position list content associated with said rowid. |
| */ |
| static void fts5SegIterReverseInitPage(Fts5Index *p, Fts5SegIter *pIter){ |
| int eDetail = p->pConfig->eDetail; |
| int n = pIter->pLeaf->szLeaf; |
| int i = pIter->iLeafOffset; |
| u8 *a = pIter->pLeaf->p; |
| int iRowidOffset = 0; |
| |
| if( n>pIter->iEndofDoclist ){ |
| n = pIter->iEndofDoclist; |
| } |
| |
| ASSERT_SZLEAF_OK(pIter->pLeaf); |
| while( 1 ){ |
| i64 iDelta = 0; |
| |
| if( eDetail==FTS5_DETAIL_NONE ){ |
| /* todo */ |
| if( i<n && a[i]==0 ){ |
| i++; |
| if( i<n && a[i]==0 ) i++; |
| } |
| }else{ |
| int nPos; |
| int bDummy; |
| i += fts5GetPoslistSize(&a[i], &nPos, &bDummy); |
| i += nPos; |
| } |
| if( i>=n ) break; |
| i += fts5GetVarint(&a[i], (u64*)&iDelta); |
| pIter->iRowid += iDelta; |
| |
| /* If necessary, grow the pIter->aRowidOffset[] array. */ |
| if( iRowidOffset>=pIter->nRowidOffset ){ |
| int nNew = pIter->nRowidOffset + 8; |
| int *aNew = (int*)sqlite3_realloc(pIter->aRowidOffset, nNew*sizeof(int)); |
| if( aNew==0 ){ |
| p->rc = SQLITE_NOMEM; |
| break; |
| } |
| pIter->aRowidOffset = aNew; |
| pIter->nRowidOffset = nNew; |
| } |
| |
| pIter->aRowidOffset[iRowidOffset++] = pIter->iLeafOffset; |
| pIter->iLeafOffset = i; |
| } |
| pIter->iRowidOffset = iRowidOffset; |
| fts5SegIterLoadNPos(p, pIter); |
| } |
| |
| /* |
| ** |
| */ |
| static void fts5SegIterReverseNewPage(Fts5Index *p, Fts5SegIter *pIter){ |
| assert( pIter->flags & FTS5_SEGITER_REVERSE ); |
| assert( pIter->flags & FTS5_SEGITER_ONETERM ); |
| |
| fts5DataRelease(pIter->pLeaf); |
| pIter->pLeaf = 0; |
| while( p->rc==SQLITE_OK && pIter->iLeafPgno>pIter->iTermLeafPgno ){ |
| Fts5Data *pNew; |
| pIter->iLeafPgno--; |
| pNew = fts5DataRead(p, FTS5_SEGMENT_ROWID( |
| pIter->pSeg->iSegid, pIter->iLeafPgno |
| )); |
| if( pNew ){ |
| /* iTermLeafOffset may be equal to szLeaf if the term is the last |
| ** thing on the page - i.e. the first rowid is on the following page. |
| ** In this case leave pIter->pLeaf==0, this iterator is at EOF. */ |
| if( pIter->iLeafPgno==pIter->iTermLeafPgno ){ |
| assert( pIter->pLeaf==0 ); |
| if( pIter->iTermLeafOffset<pNew->szLeaf ){ |
| pIter->pLeaf = pNew; |
| pIter->iLeafOffset = pIter->iTermLeafOffset; |
| } |
| }else{ |
| int iRowidOff; |
| iRowidOff = fts5LeafFirstRowidOff(pNew); |
| if( iRowidOff ){ |
| pIter->pLeaf = pNew; |
| pIter->iLeafOffset = iRowidOff; |
| } |
| } |
| |
| if( pIter->pLeaf ){ |
| u8 *a = &pIter->pLeaf->p[pIter->iLeafOffset]; |
| pIter->iLeafOffset += fts5GetVarint(a, (u64*)&pIter->iRowid); |
| break; |
| }else{ |
| fts5DataRelease(pNew); |
| } |
| } |
| } |
| |
| if( pIter->pLeaf ){ |
| pIter->iEndofDoclist = pIter->pLeaf->nn+1; |
| fts5SegIterReverseInitPage(p, pIter); |
| } |
| } |
| |
| /* |
| ** Return true if the iterator passed as the second argument currently |
| ** points to a delete marker. A delete marker is an entry with a 0 byte |
| ** position-list. |
| */ |
| static int fts5MultiIterIsEmpty(Fts5Index *p, Fts5Iter *pIter){ |
| Fts5SegIter *pSeg = &pIter->aSeg[pIter->aFirst[1].iFirst]; |
| return (p->rc==SQLITE_OK && pSeg->pLeaf && pSeg->nPos==0); |
| } |
| |
| /* |
| ** Advance iterator pIter to the next entry. |
| ** |
| ** This version of fts5SegIterNext() is only used by reverse iterators. |
| */ |
| static void fts5SegIterNext_Reverse( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5SegIter *pIter, /* Iterator to advance */ |
| int *pbUnused /* Unused */ |
| ){ |
| assert( pIter->flags & FTS5_SEGITER_REVERSE ); |
| assert( pIter->pNextLeaf==0 ); |
| UNUSED_PARAM(pbUnused); |
| |
| if( pIter->iRowidOffset>0 ){ |
| u8 *a = pIter->pLeaf->p; |
| int iOff; |
| i64 iDelta; |
| |
| pIter->iRowidOffset--; |
| pIter->iLeafOffset = pIter->aRowidOffset[pIter->iRowidOffset]; |
| fts5SegIterLoadNPos(p, pIter); |
| iOff = pIter->iLeafOffset; |
| if( p->pConfig->eDetail!=FTS5_DETAIL_NONE ){ |
| iOff += pIter->nPos; |
| } |
| fts5GetVarint(&a[iOff], (u64*)&iDelta); |
| pIter->iRowid -= iDelta; |
| }else{ |
| fts5SegIterReverseNewPage(p, pIter); |
| } |
| } |
| |
| /* |
| ** Advance iterator pIter to the next entry. |
| ** |
| ** This version of fts5SegIterNext() is only used if detail=none and the |
| ** iterator is not a reverse direction iterator. |
| */ |
| static void fts5SegIterNext_None( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5SegIter *pIter, /* Iterator to advance */ |
| int *pbNewTerm /* OUT: Set for new term */ |
| ){ |
| int iOff; |
| |
| assert( p->rc==SQLITE_OK ); |
| assert( (pIter->flags & FTS5_SEGITER_REVERSE)==0 ); |
| assert( p->pConfig->eDetail==FTS5_DETAIL_NONE ); |
| |
| ASSERT_SZLEAF_OK(pIter->pLeaf); |
| iOff = pIter->iLeafOffset; |
| |
| /* Next entry is on the next page */ |
| if( pIter->pSeg && iOff>=pIter->pLeaf->szLeaf ){ |
| fts5SegIterNextPage(p, pIter); |
| if( p->rc || pIter->pLeaf==0 ) return; |
| pIter->iRowid = 0; |
| iOff = 4; |
| } |
| |
| if( iOff<pIter->iEndofDoclist ){ |
| /* Next entry is on the current page */ |
| i64 iDelta; |
| iOff += sqlite3Fts5GetVarint(&pIter->pLeaf->p[iOff], (u64*)&iDelta); |
| pIter->iLeafOffset = iOff; |
| pIter->iRowid += iDelta; |
| }else if( (pIter->flags & FTS5_SEGITER_ONETERM)==0 ){ |
| if( pIter->pSeg ){ |
| int nKeep = 0; |
| if( iOff!=fts5LeafFirstTermOff(pIter->pLeaf) ){ |
| iOff += fts5GetVarint32(&pIter->pLeaf->p[iOff], nKeep); |
| } |
| pIter->iLeafOffset = iOff; |
| fts5SegIterLoadTerm(p, pIter, nKeep); |
| }else{ |
| const u8 *pList = 0; |
| const char *zTerm = 0; |
| int nList; |
| sqlite3Fts5HashScanNext(p->pHash); |
| sqlite3Fts5HashScanEntry(p->pHash, &zTerm, &pList, &nList); |
| if( pList==0 ) goto next_none_eof; |
| pIter->pLeaf->p = (u8*)pList; |
| pIter->pLeaf->nn = nList; |
| pIter->pLeaf->szLeaf = nList; |
| pIter->iEndofDoclist = nList; |
| sqlite3Fts5BufferSet(&p->rc,&pIter->term, (int)strlen(zTerm), (u8*)zTerm); |
| pIter->iLeafOffset = fts5GetVarint(pList, (u64*)&pIter->iRowid); |
| } |
| |
| if( pbNewTerm ) *pbNewTerm = 1; |
| }else{ |
| goto next_none_eof; |
| } |
| |
| fts5SegIterLoadNPos(p, pIter); |
| |
| return; |
| next_none_eof: |
| fts5DataRelease(pIter->pLeaf); |
| pIter->pLeaf = 0; |
| } |
| |
| |
| /* |
| ** Advance iterator pIter to the next entry. |
| ** |
| ** If an error occurs, Fts5Index.rc is set to an appropriate error code. It |
| ** is not considered an error if the iterator reaches EOF. If an error has |
| ** already occurred when this function is called, it is a no-op. |
| */ |
| static void fts5SegIterNext( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5SegIter *pIter, /* Iterator to advance */ |
| int *pbNewTerm /* OUT: Set for new term */ |
| ){ |
| Fts5Data *pLeaf = pIter->pLeaf; |
| int iOff; |
| int bNewTerm = 0; |
| int nKeep = 0; |
| u8 *a; |
| int n; |
| |
| assert( pbNewTerm==0 || *pbNewTerm==0 ); |
| assert( p->pConfig->eDetail!=FTS5_DETAIL_NONE ); |
| |
| /* Search for the end of the position list within the current page. */ |
| a = pLeaf->p; |
| n = pLeaf->szLeaf; |
| |
| ASSERT_SZLEAF_OK(pLeaf); |
| iOff = pIter->iLeafOffset + pIter->nPos; |
| |
| if( iOff<n ){ |
| /* The next entry is on the current page. */ |
| assert_nc( iOff<=pIter->iEndofDoclist ); |
| if( iOff>=pIter->iEndofDoclist ){ |
| bNewTerm = 1; |
| if( iOff!=fts5LeafFirstTermOff(pLeaf) ){ |
| iOff += fts5GetVarint32(&a[iOff], nKeep); |
| } |
| }else{ |
| u64 iDelta; |
| iOff += sqlite3Fts5GetVarint(&a[iOff], &iDelta); |
| pIter->iRowid += iDelta; |
| assert_nc( iDelta>0 ); |
| } |
| pIter->iLeafOffset = iOff; |
| |
| }else if( pIter->pSeg==0 ){ |
| const u8 *pList = 0; |
| const char *zTerm = 0; |
| int nList = 0; |
| assert( (pIter->flags & FTS5_SEGITER_ONETERM) || pbNewTerm ); |
| if( 0==(pIter->flags & FTS5_SEGITER_ONETERM) ){ |
| sqlite3Fts5HashScanNext(p->pHash); |
| sqlite3Fts5HashScanEntry(p->pHash, &zTerm, &pList, &nList); |
| } |
| if( pList==0 ){ |
| fts5DataRelease(pIter->pLeaf); |
| pIter->pLeaf = 0; |
| }else{ |
| pIter->pLeaf->p = (u8*)pList; |
| pIter->pLeaf->nn = nList; |
| pIter->pLeaf->szLeaf = nList; |
| pIter->iEndofDoclist = nList+1; |
| sqlite3Fts5BufferSet(&p->rc, &pIter->term, (int)strlen(zTerm), |
| (u8*)zTerm); |
| pIter->iLeafOffset = fts5GetVarint(pList, (u64*)&pIter->iRowid); |
| *pbNewTerm = 1; |
| } |
| }else{ |
| iOff = 0; |
| /* Next entry is not on the current page */ |
| while( iOff==0 ){ |
| fts5SegIterNextPage(p, pIter); |
| pLeaf = pIter->pLeaf; |
| if( pLeaf==0 ) break; |
| ASSERT_SZLEAF_OK(pLeaf); |
| if( (iOff = fts5LeafFirstRowidOff(pLeaf)) && iOff<pLeaf->szLeaf ){ |
| iOff += sqlite3Fts5GetVarint(&pLeaf->p[iOff], (u64*)&pIter->iRowid); |
| pIter->iLeafOffset = iOff; |
| |
| if( pLeaf->nn>pLeaf->szLeaf ){ |
| pIter->iPgidxOff = pLeaf->szLeaf + fts5GetVarint32( |
| &pLeaf->p[pLeaf->szLeaf], pIter->iEndofDoclist |
| ); |
| } |
| } |
| else if( pLeaf->nn>pLeaf->szLeaf ){ |
| pIter->iPgidxOff = pLeaf->szLeaf + fts5GetVarint32( |
| &pLeaf->p[pLeaf->szLeaf], iOff |
| ); |
| pIter->iLeafOffset = iOff; |
| pIter->iEndofDoclist = iOff; |
| bNewTerm = 1; |
| } |
| assert_nc( iOff<pLeaf->szLeaf ); |
| if( iOff>pLeaf->szLeaf ){ |
| p->rc = FTS5_CORRUPT; |
| return; |
| } |
| } |
| } |
| |
| /* Check if the iterator is now at EOF. If so, return early. */ |
| if( pIter->pLeaf ){ |
| if( bNewTerm ){ |
| if( pIter->flags & FTS5_SEGITER_ONETERM ){ |
| fts5DataRelease(pIter->pLeaf); |
| pIter->pLeaf = 0; |
| }else{ |
| fts5SegIterLoadTerm(p, pIter, nKeep); |
| fts5SegIterLoadNPos(p, pIter); |
| if( pbNewTerm ) *pbNewTerm = 1; |
| } |
| }else{ |
| /* The following could be done by calling fts5SegIterLoadNPos(). But |
| ** this block is particularly performance critical, so equivalent |
| ** code is inlined. |
| ** |
| ** Later: Switched back to fts5SegIterLoadNPos() because it supports |
| ** detail=none mode. Not ideal. |
| */ |
| int nSz; |
| assert( p->rc==SQLITE_OK ); |
| assert( pIter->iLeafOffset<=pIter->pLeaf->nn ); |
| fts5FastGetVarint32(pIter->pLeaf->p, pIter->iLeafOffset, nSz); |
| pIter->bDel = (nSz & 0x0001); |
| pIter->nPos = nSz>>1; |
| assert_nc( pIter->nPos>=0 ); |
| } |
| } |
| } |
| |
| #define SWAPVAL(T, a, b) { T tmp; tmp=a; a=b; b=tmp; } |
| |
| #define fts5IndexSkipVarint(a, iOff) { \ |
| int iEnd = iOff+9; \ |
| while( (a[iOff++] & 0x80) && iOff<iEnd ); \ |
| } |
| |
| /* |
| ** Iterator pIter currently points to the first rowid in a doclist. This |
| ** function sets the iterator up so that iterates in reverse order through |
| ** the doclist. |
| */ |
| static void fts5SegIterReverse(Fts5Index *p, Fts5SegIter *pIter){ |
| Fts5DlidxIter *pDlidx = pIter->pDlidx; |
| Fts5Data *pLast = 0; |
| int pgnoLast = 0; |
| |
| if( pDlidx ){ |
| int iSegid = pIter->pSeg->iSegid; |
| pgnoLast = fts5DlidxIterPgno(pDlidx); |
| pLast = fts5DataRead(p, FTS5_SEGMENT_ROWID(iSegid, pgnoLast)); |
| }else{ |
| Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */ |
| |
| /* Currently, Fts5SegIter.iLeafOffset points to the first byte of |
| ** position-list content for the current rowid. Back it up so that it |
| ** points to the start of the position-list size field. */ |
| int iPoslist; |
| if( pIter->iTermLeafPgno==pIter->iLeafPgno ){ |
| iPoslist = pIter->iTermLeafOffset; |
| }else{ |
| iPoslist = 4; |
| } |
| fts5IndexSkipVarint(pLeaf->p, iPoslist); |
| pIter->iLeafOffset = iPoslist; |
| |
| /* If this condition is true then the largest rowid for the current |
| ** term may not be stored on the current page. So search forward to |
| ** see where said rowid really is. */ |
| if( pIter->iEndofDoclist>=pLeaf->szLeaf ){ |
| int pgno; |
| Fts5StructureSegment *pSeg = pIter->pSeg; |
| |
| /* The last rowid in the doclist may not be on the current page. Search |
| ** forward to find the page containing the last rowid. */ |
| for(pgno=pIter->iLeafPgno+1; !p->rc && pgno<=pSeg->pgnoLast; pgno++){ |
| i64 iAbs = FTS5_SEGMENT_ROWID(pSeg->iSegid, pgno); |
| Fts5Data *pNew = fts5DataRead(p, iAbs); |
| if( pNew ){ |
| int iRowid, bTermless; |
| iRowid = fts5LeafFirstRowidOff(pNew); |
| bTermless = fts5LeafIsTermless(pNew); |
| if( iRowid ){ |
| SWAPVAL(Fts5Data*, pNew, pLast); |
| pgnoLast = pgno; |
| } |
| fts5DataRelease(pNew); |
| if( bTermless==0 ) break; |
| } |
| } |
| } |
| } |
| |
| /* If pLast is NULL at this point, then the last rowid for this doclist |
| ** lies on the page currently indicated by the iterator. In this case |
| ** pIter->iLeafOffset is already set to point to the position-list size |
| ** field associated with the first relevant rowid on the page. |
| ** |
| ** Or, if pLast is non-NULL, then it is the page that contains the last |
| ** rowid. In this case configure the iterator so that it points to the |
| ** first rowid on this page. |
| */ |
| if( pLast ){ |
| int iOff; |
| fts5DataRelease(pIter->pLeaf); |
| pIter->pLeaf = pLast; |
| pIter->iLeafPgno = pgnoLast; |
| iOff = fts5LeafFirstRowidOff(pLast); |
| iOff += fts5GetVarint(&pLast->p[iOff], (u64*)&pIter->iRowid); |
| pIter->iLeafOffset = iOff; |
| |
| if( fts5LeafIsTermless(pLast) ){ |
| pIter->iEndofDoclist = pLast->nn+1; |
| }else{ |
| pIter->iEndofDoclist = fts5LeafFirstTermOff(pLast); |
| } |
| |
| } |
| |
| fts5SegIterReverseInitPage(p, pIter); |
| } |
| |
| /* |
| ** Iterator pIter currently points to the first rowid of a doclist. |
| ** There is a doclist-index associated with the final term on the current |
| ** page. If the current term is the last term on the page, load the |
| ** doclist-index from disk and initialize an iterator at (pIter->pDlidx). |
| */ |
| static void fts5SegIterLoadDlidx(Fts5Index *p, Fts5SegIter *pIter){ |
| int iSeg = pIter->pSeg->iSegid; |
| int bRev = (pIter->flags & FTS5_SEGITER_REVERSE); |
| Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */ |
| |
| assert( pIter->flags & FTS5_SEGITER_ONETERM ); |
| assert( pIter->pDlidx==0 ); |
| |
| /* Check if the current doclist ends on this page. If it does, return |
| ** early without loading the doclist-index (as it belongs to a different |
| ** term. */ |
| if( pIter->iTermLeafPgno==pIter->iLeafPgno |
| && pIter->iEndofDoclist<pLeaf->szLeaf |
| ){ |
| return; |
| } |
| |
| pIter->pDlidx = fts5DlidxIterInit(p, bRev, iSeg, pIter->iTermLeafPgno); |
| } |
| |
| /* |
| ** The iterator object passed as the second argument currently contains |
| ** no valid values except for the Fts5SegIter.pLeaf member variable. This |
| ** function searches the leaf page for a term matching (pTerm/nTerm). |
| ** |
| ** If the specified term is found on the page, then the iterator is left |
| ** pointing to it. If argument bGe is zero and the term is not found, |
| ** the iterator is left pointing at EOF. |
| ** |
| ** If bGe is non-zero and the specified term is not found, then the |
| ** iterator is left pointing to the smallest term in the segment that |
| ** is larger than the specified term, even if this term is not on the |
| ** current page. |
| */ |
| static void fts5LeafSeek( |
| Fts5Index *p, /* Leave any error code here */ |
| int bGe, /* True for a >= search */ |
| Fts5SegIter *pIter, /* Iterator to seek */ |
| const u8 *pTerm, int nTerm /* Term to search for */ |
| ){ |
| int iOff; |
| const u8 *a = pIter->pLeaf->p; |
| int szLeaf = pIter->pLeaf->szLeaf; |
| int n = pIter->pLeaf->nn; |
| |
| int nMatch = 0; |
| int nKeep = 0; |
| int nNew = 0; |
| int iTermOff; |
| int iPgidx; /* Current offset in pgidx */ |
| int bEndOfPage = 0; |
| |
| assert( p->rc==SQLITE_OK ); |
| |
| iPgidx = szLeaf; |
| iPgidx += fts5GetVarint32(&a[iPgidx], iTermOff); |
| iOff = iTermOff; |
| if( iOff>n ){ |
| p->rc = FTS5_CORRUPT; |
| return; |
| } |
| |
| while( 1 ){ |
| |
| /* Figure out how many new bytes are in this term */ |
| fts5FastGetVarint32(a, iOff, nNew); |
| if( nKeep<nMatch ){ |
| goto search_failed; |
| } |
| |
| assert( nKeep>=nMatch ); |
| if( nKeep==nMatch ){ |
| int nCmp; |
| int i; |
| nCmp = MIN(nNew, nTerm-nMatch); |
| for(i=0; i<nCmp; i++){ |
| if( a[iOff+i]!=pTerm[nMatch+i] ) break; |
| } |
| nMatch += i; |
| |
| if( nTerm==nMatch ){ |
| if( i==nNew ){ |
| goto search_success; |
| }else{ |
| goto search_failed; |
| } |
| }else if( i<nNew && a[iOff+i]>pTerm[nMatch] ){ |
| goto search_failed; |
| } |
| } |
| |
| if( iPgidx>=n ){ |
| bEndOfPage = 1; |
| break; |
| } |
| |
| iPgidx += fts5GetVarint32(&a[iPgidx], nKeep); |
| iTermOff += nKeep; |
| iOff = iTermOff; |
| |
| if( iOff>=n ){ |
| p->rc = FTS5_CORRUPT; |
| return; |
| } |
| |
| /* Read the nKeep field of the next term. */ |
| fts5FastGetVarint32(a, iOff, nKeep); |
| } |
| |
| search_failed: |
| if( bGe==0 ){ |
| fts5DataRelease(pIter->pLeaf); |
| pIter->pLeaf = 0; |
| return; |
| }else if( bEndOfPage ){ |
| do { |
| fts5SegIterNextPage(p, pIter); |
| if( pIter->pLeaf==0 ) return; |
| a = pIter->pLeaf->p; |
| if( fts5LeafIsTermless(pIter->pLeaf)==0 ){ |
| iPgidx = pIter->pLeaf->szLeaf; |
| iPgidx += fts5GetVarint32(&pIter->pLeaf->p[iPgidx], iOff); |
| if( iOff<4 || iOff>=pIter->pLeaf->szLeaf ){ |
| p->rc = FTS5_CORRUPT; |
| }else{ |
| nKeep = 0; |
| iTermOff = iOff; |
| n = pIter->pLeaf->nn; |
| iOff += fts5GetVarint32(&a[iOff], nNew); |
| break; |
| } |
| } |
| }while( 1 ); |
| } |
| |
| search_success: |
| |
| pIter->iLeafOffset = iOff + nNew; |
| pIter->iTermLeafOffset = pIter->iLeafOffset; |
| pIter->iTermLeafPgno = pIter->iLeafPgno; |
| |
| fts5BufferSet(&p->rc, &pIter->term, nKeep, pTerm); |
| fts5BufferAppendBlob(&p->rc, &pIter->term, nNew, &a[iOff]); |
| |
| if( iPgidx>=n ){ |
| pIter->iEndofDoclist = pIter->pLeaf->nn+1; |
| }else{ |
| int nExtra; |
| iPgidx += fts5GetVarint32(&a[iPgidx], nExtra); |
| pIter->iEndofDoclist = iTermOff + nExtra; |
| } |
| pIter->iPgidxOff = iPgidx; |
| |
| fts5SegIterLoadRowid(p, pIter); |
| fts5SegIterLoadNPos(p, pIter); |
| } |
| |
| static sqlite3_stmt *fts5IdxSelectStmt(Fts5Index *p){ |
| if( p->pIdxSelect==0 ){ |
| Fts5Config *pConfig = p->pConfig; |
| fts5IndexPrepareStmt(p, &p->pIdxSelect, sqlite3_mprintf( |
| "SELECT pgno FROM '%q'.'%q_idx' WHERE " |
| "segid=? AND term<=? ORDER BY term DESC LIMIT 1", |
| pConfig->zDb, pConfig->zName |
| )); |
| } |
| return p->pIdxSelect; |
| } |
| |
| /* |
| ** Initialize the object pIter to point to term pTerm/nTerm within segment |
| ** pSeg. If there is no such term in the index, the iterator is set to EOF. |
| ** |
| ** If an error occurs, Fts5Index.rc is set to an appropriate error code. If |
| ** an error has already occurred when this function is called, it is a no-op. |
| */ |
| static void fts5SegIterSeekInit( |
| Fts5Index *p, /* FTS5 backend */ |
| const u8 *pTerm, int nTerm, /* Term to seek to */ |
| int flags, /* Mask of FTS5INDEX_XXX flags */ |
| Fts5StructureSegment *pSeg, /* Description of segment */ |
| Fts5SegIter *pIter /* Object to populate */ |
| ){ |
| int iPg = 1; |
| int bGe = (flags & FTS5INDEX_QUERY_SCAN); |
| int bDlidx = 0; /* True if there is a doclist-index */ |
| sqlite3_stmt *pIdxSelect = 0; |
| |
| assert( bGe==0 || (flags & FTS5INDEX_QUERY_DESC)==0 ); |
| assert( pTerm && nTerm ); |
| memset(pIter, 0, sizeof(*pIter)); |
| pIter->pSeg = pSeg; |
| |
| /* This block sets stack variable iPg to the leaf page number that may |
| ** contain term (pTerm/nTerm), if it is present in the segment. */ |
| pIdxSelect = fts5IdxSelectStmt(p); |
| if( p->rc ) return; |
| sqlite3_bind_int(pIdxSelect, 1, pSeg->iSegid); |
| sqlite3_bind_blob(pIdxSelect, 2, pTerm, nTerm, SQLITE_STATIC); |
| if( SQLITE_ROW==sqlite3_step(pIdxSelect) ){ |
| i64 val = sqlite3_column_int(pIdxSelect, 0); |
| iPg = (int)(val>>1); |
| bDlidx = (val & 0x0001); |
| } |
| p->rc = sqlite3_reset(pIdxSelect); |
| sqlite3_bind_null(pIdxSelect, 2); |
| |
| if( iPg<pSeg->pgnoFirst ){ |
| iPg = pSeg->pgnoFirst; |
| bDlidx = 0; |
| } |
| |
| pIter->iLeafPgno = iPg - 1; |
| fts5SegIterNextPage(p, pIter); |
| |
| if( pIter->pLeaf ){ |
| fts5LeafSeek(p, bGe, pIter, pTerm, nTerm); |
| } |
| |
| if( p->rc==SQLITE_OK && bGe==0 ){ |
| pIter->flags |= FTS5_SEGITER_ONETERM; |
| if( pIter->pLeaf ){ |
| if( flags & FTS5INDEX_QUERY_DESC ){ |
| pIter->flags |= FTS5_SEGITER_REVERSE; |
| } |
| if( bDlidx ){ |
| fts5SegIterLoadDlidx(p, pIter); |
| } |
| if( flags & FTS5INDEX_QUERY_DESC ){ |
| fts5SegIterReverse(p, pIter); |
| } |
| } |
| } |
| |
| fts5SegIterSetNext(p, pIter); |
| |
| /* Either: |
| ** |
| ** 1) an error has occurred, or |
| ** 2) the iterator points to EOF, or |
| ** 3) the iterator points to an entry with term (pTerm/nTerm), or |
| ** 4) the FTS5INDEX_QUERY_SCAN flag was set and the iterator points |
| ** to an entry with a term greater than or equal to (pTerm/nTerm). |
| */ |
| assert( p->rc!=SQLITE_OK /* 1 */ |
| || pIter->pLeaf==0 /* 2 */ |
| || fts5BufferCompareBlob(&pIter->term, pTerm, nTerm)==0 /* 3 */ |
| || (bGe && fts5BufferCompareBlob(&pIter->term, pTerm, nTerm)>0) /* 4 */ |
| ); |
| } |
| |
| /* |
| ** Initialize the object pIter to point to term pTerm/nTerm within the |
| ** in-memory hash table. If there is no such term in the hash-table, the |
| ** iterator is set to EOF. |
| ** |
| ** If an error occurs, Fts5Index.rc is set to an appropriate error code. If |
| ** an error has already occurred when this function is called, it is a no-op. |
| */ |
| static void fts5SegIterHashInit( |
| Fts5Index *p, /* FTS5 backend */ |
| const u8 *pTerm, int nTerm, /* Term to seek to */ |
| int flags, /* Mask of FTS5INDEX_XXX flags */ |
| Fts5SegIter *pIter /* Object to populate */ |
| ){ |
| const u8 *pList = 0; |
| int nList = 0; |
| const u8 *z = 0; |
| int n = 0; |
| |
| assert( p->pHash ); |
| assert( p->rc==SQLITE_OK ); |
| |
| if( pTerm==0 || (flags & FTS5INDEX_QUERY_SCAN) ){ |
| p->rc = sqlite3Fts5HashScanInit(p->pHash, (const char*)pTerm, nTerm); |
| sqlite3Fts5HashScanEntry(p->pHash, (const char**)&z, &pList, &nList); |
| n = (z ? (int)strlen((const char*)z) : 0); |
| }else{ |
| pIter->flags |= FTS5_SEGITER_ONETERM; |
| sqlite3Fts5HashQuery(p->pHash, (const char*)pTerm, nTerm, &pList, &nList); |
| z = pTerm; |
| n = nTerm; |
| } |
| |
| if( pList ){ |
| Fts5Data *pLeaf; |
| sqlite3Fts5BufferSet(&p->rc, &pIter->term, n, z); |
| pLeaf = fts5IdxMalloc(p, sizeof(Fts5Data)); |
| if( pLeaf==0 ) return; |
| pLeaf->p = (u8*)pList; |
| pLeaf->nn = pLeaf->szLeaf = nList; |
| pIter->pLeaf = pLeaf; |
| pIter->iLeafOffset = fts5GetVarint(pLeaf->p, (u64*)&pIter->iRowid); |
| pIter->iEndofDoclist = pLeaf->nn; |
| |
| if( flags & FTS5INDEX_QUERY_DESC ){ |
| pIter->flags |= FTS5_SEGITER_REVERSE; |
| fts5SegIterReverseInitPage(p, pIter); |
| }else{ |
| fts5SegIterLoadNPos(p, pIter); |
| } |
| } |
| |
| fts5SegIterSetNext(p, pIter); |
| } |
| |
| /* |
| ** Zero the iterator passed as the only argument. |
| */ |
| static void fts5SegIterClear(Fts5SegIter *pIter){ |
| fts5BufferFree(&pIter->term); |
| fts5DataRelease(pIter->pLeaf); |
| fts5DataRelease(pIter->pNextLeaf); |
| fts5DlidxIterFree(pIter->pDlidx); |
| sqlite3_free(pIter->aRowidOffset); |
| memset(pIter, 0, sizeof(Fts5SegIter)); |
| } |
| |
| #ifdef SQLITE_DEBUG |
| |
| /* |
| ** This function is used as part of the big assert() procedure implemented by |
| ** fts5AssertMultiIterSetup(). It ensures that the result currently stored |
| ** in *pRes is the correct result of comparing the current positions of the |
| ** two iterators. |
| */ |
| static void fts5AssertComparisonResult( |
| Fts5Iter *pIter, |
| Fts5SegIter *p1, |
| Fts5SegIter *p2, |
| Fts5CResult *pRes |
| ){ |
| int i1 = p1 - pIter->aSeg; |
| int i2 = p2 - pIter->aSeg; |
| |
| if( p1->pLeaf || p2->pLeaf ){ |
| if( p1->pLeaf==0 ){ |
| assert( pRes->iFirst==i2 ); |
| }else if( p2->pLeaf==0 ){ |
| assert( pRes->iFirst==i1 ); |
| }else{ |
| int nMin = MIN(p1->term.n, p2->term.n); |
| int res = memcmp(p1->term.p, p2->term.p, nMin); |
| if( res==0 ) res = p1->term.n - p2->term.n; |
| |
| if( res==0 ){ |
| assert( pRes->bTermEq==1 ); |
| assert( p1->iRowid!=p2->iRowid ); |
| res = ((p1->iRowid > p2->iRowid)==pIter->bRev) ? -1 : 1; |
| }else{ |
| assert( pRes->bTermEq==0 ); |
| } |
| |
| if( res<0 ){ |
| assert( pRes->iFirst==i1 ); |
| }else{ |
| assert( pRes->iFirst==i2 ); |
| } |
| } |
| } |
| } |
| |
| /* |
| ** This function is a no-op unless SQLITE_DEBUG is defined when this module |
| ** is compiled. In that case, this function is essentially an assert() |
| ** statement used to verify that the contents of the pIter->aFirst[] array |
| ** are correct. |
| */ |
| static void fts5AssertMultiIterSetup(Fts5Index *p, Fts5Iter *pIter){ |
| if( p->rc==SQLITE_OK ){ |
| Fts5SegIter *pFirst = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; |
| int i; |
| |
| assert( (pFirst->pLeaf==0)==pIter->base.bEof ); |
| |
| /* Check that pIter->iSwitchRowid is set correctly. */ |
| for(i=0; i<pIter->nSeg; i++){ |
| Fts5SegIter *p1 = &pIter->aSeg[i]; |
| assert( p1==pFirst |
| || p1->pLeaf==0 |
| || fts5BufferCompare(&pFirst->term, &p1->term) |
| || p1->iRowid==pIter->iSwitchRowid |
| || (p1->iRowid<pIter->iSwitchRowid)==pIter->bRev |
| ); |
| } |
| |
| for(i=0; i<pIter->nSeg; i+=2){ |
| Fts5SegIter *p1 = &pIter->aSeg[i]; |
| Fts5SegIter *p2 = &pIter->aSeg[i+1]; |
| Fts5CResult *pRes = &pIter->aFirst[(pIter->nSeg + i) / 2]; |
| fts5AssertComparisonResult(pIter, p1, p2, pRes); |
| } |
| |
| for(i=1; i<(pIter->nSeg / 2); i+=2){ |
| Fts5SegIter *p1 = &pIter->aSeg[ pIter->aFirst[i*2].iFirst ]; |
| Fts5SegIter *p2 = &pIter->aSeg[ pIter->aFirst[i*2+1].iFirst ]; |
| Fts5CResult *pRes = &pIter->aFirst[i]; |
| fts5AssertComparisonResult(pIter, p1, p2, pRes); |
| } |
| } |
| } |
| #else |
| # define fts5AssertMultiIterSetup(x,y) |
| #endif |
| |
| /* |
| ** Do the comparison necessary to populate pIter->aFirst[iOut]. |
| ** |
| ** If the returned value is non-zero, then it is the index of an entry |
| ** in the pIter->aSeg[] array that is (a) not at EOF, and (b) pointing |
| ** to a key that is a duplicate of another, higher priority, |
| ** segment-iterator in the pSeg->aSeg[] array. |
| */ |
| static int fts5MultiIterDoCompare(Fts5Iter *pIter, int iOut){ |
| int i1; /* Index of left-hand Fts5SegIter */ |
| int i2; /* Index of right-hand Fts5SegIter */ |
| int iRes; |
| Fts5SegIter *p1; /* Left-hand Fts5SegIter */ |
| Fts5SegIter *p2; /* Right-hand Fts5SegIter */ |
| Fts5CResult *pRes = &pIter->aFirst[iOut]; |
| |
| assert( iOut<pIter->nSeg && iOut>0 ); |
| assert( pIter->bRev==0 || pIter->bRev==1 ); |
| |
| if( iOut>=(pIter->nSeg/2) ){ |
| i1 = (iOut - pIter->nSeg/2) * 2; |
| i2 = i1 + 1; |
| }else{ |
| i1 = pIter->aFirst[iOut*2].iFirst; |
| i2 = pIter->aFirst[iOut*2+1].iFirst; |
| } |
| p1 = &pIter->aSeg[i1]; |
| p2 = &pIter->aSeg[i2]; |
| |
| pRes->bTermEq = 0; |
| if( p1->pLeaf==0 ){ /* If p1 is at EOF */ |
| iRes = i2; |
| }else if( p2->pLeaf==0 ){ /* If p2 is at EOF */ |
| iRes = i1; |
| }else{ |
| int res = fts5BufferCompare(&p1->term, &p2->term); |
| if( res==0 ){ |
| assert( i2>i1 ); |
| assert( i2!=0 ); |
| pRes->bTermEq = 1; |
| if( p1->iRowid==p2->iRowid ){ |
| p1->bDel = p2->bDel; |
| return i2; |
| } |
| res = ((p1->iRowid > p2->iRowid)==pIter->bRev) ? -1 : +1; |
| } |
| assert( res!=0 ); |
| if( res<0 ){ |
| iRes = i1; |
| }else{ |
| iRes = i2; |
| } |
| } |
| |
| pRes->iFirst = (u16)iRes; |
| return 0; |
| } |
| |
| /* |
| ** Move the seg-iter so that it points to the first rowid on page iLeafPgno. |
| ** It is an error if leaf iLeafPgno does not exist or contains no rowids. |
| */ |
| static void fts5SegIterGotoPage( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5SegIter *pIter, /* Iterator to advance */ |
| int iLeafPgno |
| ){ |
| assert( iLeafPgno>pIter->iLeafPgno ); |
| |
| if( iLeafPgno>pIter->pSeg->pgnoLast ){ |
| p->rc = FTS5_CORRUPT; |
| }else{ |
| fts5DataRelease(pIter->pNextLeaf); |
| pIter->pNextLeaf = 0; |
| pIter->iLeafPgno = iLeafPgno-1; |
| fts5SegIterNextPage(p, pIter); |
| assert( p->rc!=SQLITE_OK || pIter->iLeafPgno==iLeafPgno ); |
| |
| if( p->rc==SQLITE_OK ){ |
| int iOff; |
| u8 *a = pIter->pLeaf->p; |
| int n = pIter->pLeaf->szLeaf; |
| |
| iOff = fts5LeafFirstRowidOff(pIter->pLeaf); |
| if( iOff<4 || iOff>=n ){ |
| p->rc = FTS5_CORRUPT; |
| }else{ |
| iOff += fts5GetVarint(&a[iOff], (u64*)&pIter->iRowid); |
| pIter->iLeafOffset = iOff; |
| fts5SegIterLoadNPos(p, pIter); |
| } |
| } |
| } |
| } |
| |
| /* |
| ** Advance the iterator passed as the second argument until it is at or |
| ** past rowid iFrom. Regardless of the value of iFrom, the iterator is |
| ** always advanced at least once. |
| */ |
| static void fts5SegIterNextFrom( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5SegIter *pIter, /* Iterator to advance */ |
| i64 iMatch /* Advance iterator at least this far */ |
| ){ |
| int bRev = (pIter->flags & FTS5_SEGITER_REVERSE); |
| Fts5DlidxIter *pDlidx = pIter->pDlidx; |
| int iLeafPgno = pIter->iLeafPgno; |
| int bMove = 1; |
| |
| assert( pIter->flags & FTS5_SEGITER_ONETERM ); |
| assert( pIter->pDlidx ); |
| assert( pIter->pLeaf ); |
| |
| if( bRev==0 ){ |
| while( !fts5DlidxIterEof(p, pDlidx) && iMatch>fts5DlidxIterRowid(pDlidx) ){ |
| iLeafPgno = fts5DlidxIterPgno(pDlidx); |
| fts5DlidxIterNext(p, pDlidx); |
| } |
| assert_nc( iLeafPgno>=pIter->iLeafPgno || p->rc ); |
| if( iLeafPgno>pIter->iLeafPgno ){ |
| fts5SegIterGotoPage(p, pIter, iLeafPgno); |
| bMove = 0; |
| } |
| }else{ |
| assert( pIter->pNextLeaf==0 ); |
| assert( iMatch<pIter->iRowid ); |
| while( !fts5DlidxIterEof(p, pDlidx) && iMatch<fts5DlidxIterRowid(pDlidx) ){ |
| fts5DlidxIterPrev(p, pDlidx); |
| } |
| iLeafPgno = fts5DlidxIterPgno(pDlidx); |
| |
| assert( fts5DlidxIterEof(p, pDlidx) || iLeafPgno<=pIter->iLeafPgno ); |
| |
| if( iLeafPgno<pIter->iLeafPgno ){ |
| pIter->iLeafPgno = iLeafPgno+1; |
| fts5SegIterReverseNewPage(p, pIter); |
| bMove = 0; |
| } |
| } |
| |
| do{ |
| if( bMove && p->rc==SQLITE_OK ) pIter->xNext(p, pIter, 0); |
| if( pIter->pLeaf==0 ) break; |
| if( bRev==0 && pIter->iRowid>=iMatch ) break; |
| if( bRev!=0 && pIter->iRowid<=iMatch ) break; |
| bMove = 1; |
| }while( p->rc==SQLITE_OK ); |
| } |
| |
| |
| /* |
| ** Free the iterator object passed as the second argument. |
| */ |
| static void fts5MultiIterFree(Fts5Iter *pIter){ |
| if( pIter ){ |
| int i; |
| for(i=0; i<pIter->nSeg; i++){ |
| fts5SegIterClear(&pIter->aSeg[i]); |
| } |
| fts5StructureRelease(pIter->pStruct); |
| fts5BufferFree(&pIter->poslist); |
| sqlite3_free(pIter); |
| } |
| } |
| |
| static void fts5MultiIterAdvanced( |
| Fts5Index *p, /* FTS5 backend to iterate within */ |
| Fts5Iter *pIter, /* Iterator to update aFirst[] array for */ |
| int iChanged, /* Index of sub-iterator just advanced */ |
| int iMinset /* Minimum entry in aFirst[] to set */ |
| ){ |
| int i; |
| for(i=(pIter->nSeg+iChanged)/2; i>=iMinset && p->rc==SQLITE_OK; i=i/2){ |
| int iEq; |
| if( (iEq = fts5MultiIterDoCompare(pIter, i)) ){ |
| Fts5SegIter *pSeg = &pIter->aSeg[iEq]; |
| assert( p->rc==SQLITE_OK ); |
| pSeg->xNext(p, pSeg, 0); |
| i = pIter->nSeg + iEq; |
| } |
| } |
| } |
| |
| /* |
| ** Sub-iterator iChanged of iterator pIter has just been advanced. It still |
| ** points to the same term though - just a different rowid. This function |
| ** attempts to update the contents of the pIter->aFirst[] accordingly. |
| ** If it does so successfully, 0 is returned. Otherwise 1. |
| ** |
| ** If non-zero is returned, the caller should call fts5MultiIterAdvanced() |
| ** on the iterator instead. That function does the same as this one, except |
| ** that it deals with more complicated cases as well. |
| */ |
| static int fts5MultiIterAdvanceRowid( |
| Fts5Iter *pIter, /* Iterator to update aFirst[] array for */ |
| int iChanged, /* Index of sub-iterator just advanced */ |
| Fts5SegIter **ppFirst |
| ){ |
| Fts5SegIter *pNew = &pIter->aSeg[iChanged]; |
| |
| if( pNew->iRowid==pIter->iSwitchRowid |
| || (pNew->iRowid<pIter->iSwitchRowid)==pIter->bRev |
| ){ |
| int i; |
| Fts5SegIter *pOther = &pIter->aSeg[iChanged ^ 0x0001]; |
| pIter->iSwitchRowid = pIter->bRev ? SMALLEST_INT64 : LARGEST_INT64; |
| for(i=(pIter->nSeg+iChanged)/2; 1; i=i/2){ |
| Fts5CResult *pRes = &pIter->aFirst[i]; |
| |
| assert( pNew->pLeaf ); |
| assert( pRes->bTermEq==0 || pOther->pLeaf ); |
| |
| if( pRes->bTermEq ){ |
| if( pNew->iRowid==pOther->iRowid ){ |
| return 1; |
| }else if( (pOther->iRowid>pNew->iRowid)==pIter->bRev ){ |
| pIter->iSwitchRowid = pOther->iRowid; |
| pNew = pOther; |
| }else if( (pOther->iRowid>pIter->iSwitchRowid)==pIter->bRev ){ |
| pIter->iSwitchRowid = pOther->iRowid; |
| } |
| } |
| pRes->iFirst = (u16)(pNew - pIter->aSeg); |
| if( i==1 ) break; |
| |
| pOther = &pIter->aSeg[ pIter->aFirst[i ^ 0x0001].iFirst ]; |
| } |
| } |
| |
| *ppFirst = pNew; |
| return 0; |
| } |
| |
| /* |
| ** Set the pIter->bEof variable based on the state of the sub-iterators. |
| */ |
| static void fts5MultiIterSetEof(Fts5Iter *pIter){ |
| Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; |
| pIter->base.bEof = pSeg->pLeaf==0; |
| pIter->iSwitchRowid = pSeg->iRowid; |
| } |
| |
| /* |
| ** Move the iterator to the next entry. |
| ** |
| ** If an error occurs, an error code is left in Fts5Index.rc. It is not |
| ** considered an error if the iterator reaches EOF, or if it is already at |
| ** EOF when this function is called. |
| */ |
| static void fts5MultiIterNext( |
| Fts5Index *p, |
| Fts5Iter *pIter, |
| int bFrom, /* True if argument iFrom is valid */ |
| i64 iFrom /* Advance at least as far as this */ |
| ){ |
| int bUseFrom = bFrom; |
| assert( pIter->base.bEof==0 ); |
| while( p->rc==SQLITE_OK ){ |
| int iFirst = pIter->aFirst[1].iFirst; |
| int bNewTerm = 0; |
| Fts5SegIter *pSeg = &pIter->aSeg[iFirst]; |
| assert( p->rc==SQLITE_OK ); |
| if( bUseFrom && pSeg->pDlidx ){ |
| fts5SegIterNextFrom(p, pSeg, iFrom); |
| }else{ |
| pSeg->xNext(p, pSeg, &bNewTerm); |
| } |
| |
| if( pSeg->pLeaf==0 || bNewTerm |
| || fts5MultiIterAdvanceRowid(pIter, iFirst, &pSeg) |
| ){ |
| fts5MultiIterAdvanced(p, pIter, iFirst, 1); |
| fts5MultiIterSetEof(pIter); |
| pSeg = &pIter->aSeg[pIter->aFirst[1].iFirst]; |
| if( pSeg->pLeaf==0 ) return; |
| } |
| |
| fts5AssertMultiIterSetup(p, pIter); |
| assert( pSeg==&pIter->aSeg[pIter->aFirst[1].iFirst] && pSeg->pLeaf ); |
| if( pIter->bSkipEmpty==0 || pSeg->nPos ){ |
| pIter->xSetOutputs(pIter, pSeg); |
| return; |
| } |
| bUseFrom = 0; |
| } |
| } |
| |
| static void fts5MultiIterNext2( |
| Fts5Index *p, |
| Fts5Iter *pIter, |
| int *pbNewTerm /* OUT: True if *might* be new term */ |
| ){ |
| assert( pIter->bSkipEmpty ); |
| if( p->rc==SQLITE_OK ){ |
| *pbNewTerm = 0; |
| do{ |
| int iFirst = pIter->aFirst[1].iFirst; |
| Fts5SegIter *pSeg = &pIter->aSeg[iFirst]; |
| int bNewTerm = 0; |
| |
| assert( p->rc==SQLITE_OK ); |
| pSeg->xNext(p, pSeg, &bNewTerm); |
| if( pSeg->pLeaf==0 || bNewTerm |
| || fts5MultiIterAdvanceRowid(pIter, iFirst, &pSeg) |
| ){ |
| fts5MultiIterAdvanced(p, pIter, iFirst, 1); |
| fts5MultiIterSetEof(pIter); |
| *pbNewTerm = 1; |
| } |
| fts5AssertMultiIterSetup(p, pIter); |
| |
| }while( fts5MultiIterIsEmpty(p, pIter) ); |
| } |
| } |
| |
| static void fts5IterSetOutputs_Noop(Fts5Iter *pUnused1, Fts5SegIter *pUnused2){ |
| UNUSED_PARAM2(pUnused1, pUnused2); |
| } |
| |
| static Fts5Iter *fts5MultiIterAlloc( |
| Fts5Index *p, /* FTS5 backend to iterate within */ |
| int nSeg |
| ){ |
| Fts5Iter *pNew; |
| int nSlot; /* Power of two >= nSeg */ |
| |
| for(nSlot=2; nSlot<nSeg; nSlot=nSlot*2); |
| pNew = fts5IdxMalloc(p, |
| sizeof(Fts5Iter) + /* pNew */ |
| sizeof(Fts5SegIter) * (nSlot-1) + /* pNew->aSeg[] */ |
| sizeof(Fts5CResult) * nSlot /* pNew->aFirst[] */ |
| ); |
| if( pNew ){ |
| pNew->nSeg = nSlot; |
| pNew->aFirst = (Fts5CResult*)&pNew->aSeg[nSlot]; |
| pNew->pIndex = p; |
| pNew->xSetOutputs = fts5IterSetOutputs_Noop; |
| } |
| return pNew; |
| } |
| |
| static void fts5PoslistCallback( |
| Fts5Index *pUnused, |
| void *pContext, |
| const u8 *pChunk, int nChunk |
| ){ |
| UNUSED_PARAM(pUnused); |
| assert_nc( nChunk>=0 ); |
| if( nChunk>0 ){ |
| fts5BufferSafeAppendBlob((Fts5Buffer*)pContext, pChunk, nChunk); |
| } |
| } |
| |
| typedef struct PoslistCallbackCtx PoslistCallbackCtx; |
| struct PoslistCallbackCtx { |
| Fts5Buffer *pBuf; /* Append to this buffer */ |
| Fts5Colset *pColset; /* Restrict matches to this column */ |
| int eState; /* See above */ |
| }; |
| |
| typedef struct PoslistOffsetsCtx PoslistOffsetsCtx; |
| struct PoslistOffsetsCtx { |
| Fts5Buffer *pBuf; /* Append to this buffer */ |
| Fts5Colset *pColset; /* Restrict matches to this column */ |
| int iRead; |
| int iWrite; |
| }; |
| |
| /* |
| ** TODO: Make this more efficient! |
| */ |
| static int fts5IndexColsetTest(Fts5Colset *pColset, int iCol){ |
| int i; |
| for(i=0; i<pColset->nCol; i++){ |
| if( pColset->aiCol[i]==iCol ) return 1; |
| } |
| return 0; |
| } |
| |
| static void fts5PoslistOffsetsCallback( |
| Fts5Index *pUnused, |
| void *pContext, |
| const u8 *pChunk, int nChunk |
| ){ |
| PoslistOffsetsCtx *pCtx = (PoslistOffsetsCtx*)pContext; |
| UNUSED_PARAM(pUnused); |
| assert_nc( nChunk>=0 ); |
| if( nChunk>0 ){ |
| int i = 0; |
| while( i<nChunk ){ |
| int iVal; |
| i += fts5GetVarint32(&pChunk[i], iVal); |
| iVal += pCtx->iRead - 2; |
| pCtx->iRead = iVal; |
| if( fts5IndexColsetTest(pCtx->pColset, iVal) ){ |
| fts5BufferSafeAppendVarint(pCtx->pBuf, iVal + 2 - pCtx->iWrite); |
| pCtx->iWrite = iVal; |
| } |
| } |
| } |
| } |
| |
| static void fts5PoslistFilterCallback( |
| Fts5Index *pUnused, |
| void *pContext, |
| const u8 *pChunk, int nChunk |
| ){ |
| PoslistCallbackCtx *pCtx = (PoslistCallbackCtx*)pContext; |
| UNUSED_PARAM(pUnused); |
| assert_nc( nChunk>=0 ); |
| if( nChunk>0 ){ |
| /* Search through to find the first varint with value 1. This is the |
| ** start of the next columns hits. */ |
| int i = 0; |
| int iStart = 0; |
| |
| if( pCtx->eState==2 ){ |
| int iCol; |
| fts5FastGetVarint32(pChunk, i, iCol); |
| if( fts5IndexColsetTest(pCtx->pColset, iCol) ){ |
| pCtx->eState = 1; |
| fts5BufferSafeAppendVarint(pCtx->pBuf, 1); |
| }else{ |
| pCtx->eState = 0; |
| } |
| } |
| |
| do { |
| while( i<nChunk && pChunk[i]!=0x01 ){ |
| while( pChunk[i] & 0x80 ) i++; |
| i++; |
| } |
| if( pCtx->eState ){ |
| fts5BufferSafeAppendBlob(pCtx->pBuf, &pChunk[iStart], i-iStart); |
| } |
| if( i<nChunk ){ |
| int iCol; |
| iStart = i; |
| i++; |
| if( i>=nChunk ){ |
| pCtx->eState = 2; |
| }else{ |
| fts5FastGetVarint32(pChunk, i, iCol); |
| pCtx->eState = fts5IndexColsetTest(pCtx->pColset, iCol); |
| if( pCtx->eState ){ |
| fts5BufferSafeAppendBlob(pCtx->pBuf, &pChunk[iStart], i-iStart); |
| iStart = i; |
| } |
| } |
| } |
| }while( i<nChunk ); |
| } |
| } |
| |
| static void fts5ChunkIterate( |
| Fts5Index *p, /* Index object */ |
| Fts5SegIter *pSeg, /* Poslist of this iterator */ |
| void *pCtx, /* Context pointer for xChunk callback */ |
| void (*xChunk)(Fts5Index*, void*, const u8*, int) |
| ){ |
| int nRem = pSeg->nPos; /* Number of bytes still to come */ |
| Fts5Data *pData = 0; |
| u8 *pChunk = &pSeg->pLeaf->p[pSeg->iLeafOffset]; |
| int nChunk = MIN(nRem, pSeg->pLeaf->szLeaf - pSeg->iLeafOffset); |
| int pgno = pSeg->iLeafPgno; |
| int pgnoSave = 0; |
| |
| /* This function does notmwork with detail=none databases. */ |
| assert( p->pConfig->eDetail!=FTS5_DETAIL_NONE ); |
| |
| if( (pSeg->flags & FTS5_SEGITER_REVERSE)==0 ){ |
| pgnoSave = pgno+1; |
| } |
| |
| while( 1 ){ |
| xChunk(p, pCtx, pChunk, nChunk); |
| nRem -= nChunk; |
| fts5DataRelease(pData); |
| if( nRem<=0 ){ |
| break; |
| }else{ |
| pgno++; |
| pData = fts5LeafRead(p, FTS5_SEGMENT_ROWID(pSeg->pSeg->iSegid, pgno)); |
| if( pData==0 ) break; |
| pChunk = &pData->p[4]; |
| nChunk = MIN(nRem, pData->szLeaf - 4); |
| if( pgno==pgnoSave ){ |
| assert( pSeg->pNextLeaf==0 ); |
| pSeg->pNextLeaf = pData; |
| pData = 0; |
| } |
| } |
| } |
| } |
| |
| /* |
| ** Iterator pIter currently points to a valid entry (not EOF). This |
| ** function appends the position list data for the current entry to |
| ** buffer pBuf. It does not make a copy of the position-list size |
| ** field. |
| */ |
| static void fts5SegiterPoslist( |
| Fts5Index *p, |
| Fts5SegIter *pSeg, |
| Fts5Colset *pColset, |
| Fts5Buffer *pBuf |
| ){ |
| if( 0==fts5BufferGrow(&p->rc, pBuf, pSeg->nPos) ){ |
| if( pColset==0 ){ |
| fts5ChunkIterate(p, pSeg, (void*)pBuf, fts5PoslistCallback); |
| }else{ |
| if( p->pConfig->eDetail==FTS5_DETAIL_FULL ){ |
| PoslistCallbackCtx sCtx; |
| sCtx.pBuf = pBuf; |
| sCtx.pColset = pColset; |
| sCtx.eState = fts5IndexColsetTest(pColset, 0); |
| assert( sCtx.eState==0 || sCtx.eState==1 ); |
| fts5ChunkIterate(p, pSeg, (void*)&sCtx, fts5PoslistFilterCallback); |
| }else{ |
| PoslistOffsetsCtx sCtx; |
| memset(&sCtx, 0, sizeof(sCtx)); |
| sCtx.pBuf = pBuf; |
| sCtx.pColset = pColset; |
| fts5ChunkIterate(p, pSeg, (void*)&sCtx, fts5PoslistOffsetsCallback); |
| } |
| } |
| } |
| } |
| |
| /* |
| ** IN/OUT parameter (*pa) points to a position list n bytes in size. If |
| ** the position list contains entries for column iCol, then (*pa) is set |
| ** to point to the sub-position-list for that column and the number of |
| ** bytes in it returned. Or, if the argument position list does not |
| ** contain any entries for column iCol, return 0. |
| */ |
| static int fts5IndexExtractCol( |
| const u8 **pa, /* IN/OUT: Pointer to poslist */ |
| int n, /* IN: Size of poslist in bytes */ |
| int iCol /* Column to extract from poslist */ |
| ){ |
| int iCurrent = 0; /* Anything before the first 0x01 is col 0 */ |
| const u8 *p = *pa; |
| const u8 *pEnd = &p[n]; /* One byte past end of position list */ |
| |
| while( iCol>iCurrent ){ |
| /* Advance pointer p until it points to pEnd or an 0x01 byte that is |
| ** not part of a varint. Note that it is not possible for a negative |
| ** or extremely large varint to occur within an uncorrupted position |
| ** list. So the last byte of each varint may be assumed to have a clear |
| ** 0x80 bit. */ |
| while( *p!=0x01 ){ |
| while( *p++ & 0x80 ); |
| if( p>=pEnd ) return 0; |
| } |
| *pa = p++; |
| iCurrent = *p++; |
| if( iCurrent & 0x80 ){ |
| p--; |
| p += fts5GetVarint32(p, iCurrent); |
| } |
| } |
| if( iCol!=iCurrent ) return 0; |
| |
| /* Advance pointer p until it points to pEnd or an 0x01 byte that is |
| ** not part of a varint */ |
| while( p<pEnd && *p!=0x01 ){ |
| while( *p++ & 0x80 ); |
| } |
| |
| return p - (*pa); |
| } |
| |
| static void fts5IndexExtractColset( |
| int *pRc, |
| Fts5Colset *pColset, /* Colset to filter on */ |
| const u8 *pPos, int nPos, /* Position list */ |
| Fts5Buffer *pBuf /* Output buffer */ |
| ){ |
| if( *pRc==SQLITE_OK ){ |
| int i; |
| fts5BufferZero(pBuf); |
| for(i=0; i<pColset->nCol; i++){ |
| const u8 *pSub = pPos; |
| int nSub = fts5IndexExtractCol(&pSub, nPos, pColset->aiCol[i]); |
| if( nSub ){ |
| fts5BufferAppendBlob(pRc, pBuf, nSub, pSub); |
| } |
| } |
| } |
| } |
| |
| /* |
| ** xSetOutputs callback used by detail=none tables. |
| */ |
| static void fts5IterSetOutputs_None(Fts5Iter *pIter, Fts5SegIter *pSeg){ |
| assert( pIter->pIndex->pConfig->eDetail==FTS5_DETAIL_NONE ); |
| pIter->base.iRowid = pSeg->iRowid; |
| pIter->base.nData = pSeg->nPos; |
| } |
| |
| /* |
| ** xSetOutputs callback used by detail=full and detail=col tables when no |
| ** column filters are specified. |
| */ |
| static void fts5IterSetOutputs_Nocolset(Fts5Iter *pIter, Fts5SegIter *pSeg){ |
| pIter->base.iRowid = pSeg->iRowid; |
| pIter->base.nData = pSeg->nPos; |
| |
| assert( pIter->pIndex->pConfig->eDetail!=FTS5_DETAIL_NONE ); |
| assert( pIter->pColset==0 ); |
| |
| if( pSeg->iLeafOffset+pSeg->nPos<=pSeg->pLeaf->szLeaf ){ |
| /* All data is stored on the current page. Populate the output |
| ** variables to point into the body of the page object. */ |
| pIter->base.pData = &pSeg->pLeaf->p[pSeg->iLeafOffset]; |
| }else{ |
| /* The data is distributed over two or more pages. Copy it into the |
| ** Fts5Iter.poslist buffer and then set the output pointer to point |
| ** to this buffer. */ |
| fts5BufferZero(&pIter->poslist); |
| fts5SegiterPoslist(pIter->pIndex, pSeg, 0, &pIter->poslist); |
| pIter->base.pData = pIter->poslist.p; |
| } |
| } |
| |
| /* |
| ** xSetOutputs callback used when the Fts5Colset object has nCol==0 (match |
| ** against no columns at all). |
| */ |
| static void fts5IterSetOutputs_ZeroColset(Fts5Iter *pIter, Fts5SegIter *pSeg){ |
| UNUSED_PARAM(pSeg); |
| pIter->base.nData = 0; |
| } |
| |
| /* |
| ** xSetOutputs callback used by detail=col when there is a column filter |
| ** and there are 100 or more columns. Also called as a fallback from |
| ** fts5IterSetOutputs_Col100 if the column-list spans more than one page. |
| */ |
| static void fts5IterSetOutputs_Col(Fts5Iter *pIter, Fts5SegIter *pSeg){ |
| fts5BufferZero(&pIter->poslist); |
| fts5SegiterPoslist(pIter->pIndex, pSeg, pIter->pColset, &pIter->poslist); |
| pIter->base.iRowid = pSeg->iRowid; |
| pIter->base.pData = pIter->poslist.p; |
| pIter->base.nData = pIter->poslist.n; |
| } |
| |
| /* |
| ** xSetOutputs callback used when: |
| ** |
| ** * detail=col, |
| ** * there is a column filter, and |
| ** * the table contains 100 or fewer columns. |
| ** |
| ** The last point is to ensure all column numbers are stored as |
| ** single-byte varints. |
| */ |
| static void fts5IterSetOutputs_Col100(Fts5Iter *pIter, Fts5SegIter *pSeg){ |
| |
| assert( pIter->pIndex->pConfig->eDetail==FTS5_DETAIL_COLUMNS ); |
| assert( pIter->pColset ); |
| |
| if( pSeg->iLeafOffset+pSeg->nPos>pSeg->pLeaf->szLeaf ){ |
| fts5IterSetOutputs_Col(pIter, pSeg); |
| }else{ |
| u8 *a = (u8*)&pSeg->pLeaf->p[pSeg->iLeafOffset]; |
| u8 *pEnd = (u8*)&a[pSeg->nPos]; |
| int iPrev = 0; |
| int *aiCol = pIter->pColset->aiCol; |
| int *aiColEnd = &aiCol[pIter->pColset->nCol]; |
| |
| u8 *aOut = pIter->poslist.p; |
| int iPrevOut = 0; |
| |
| pIter->base.iRowid = pSeg->iRowid; |
| |
| while( a<pEnd ){ |
| iPrev += (int)a++[0] - 2; |
| while( *aiCol<iPrev ){ |
| aiCol++; |
| if( aiCol==aiColEnd ) goto setoutputs_col_out; |
| } |
| if( *aiCol==iPrev ){ |
| *aOut++ = (u8)((iPrev - iPrevOut) + 2); |
| iPrevOut = iPrev; |
| } |
| } |
| |
| setoutputs_col_out: |
| pIter->base.pData = pIter->poslist.p; |
| pIter->base.nData = aOut - pIter->poslist.p; |
| } |
| } |
| |
| /* |
| ** xSetOutputs callback used by detail=full when there is a column filter. |
| */ |
| static void fts5IterSetOutputs_Full(Fts5Iter *pIter, Fts5SegIter *pSeg){ |
| Fts5Colset *pColset = pIter->pColset; |
| pIter->base.iRowid = pSeg->iRowid; |
| |
| assert( pIter->pIndex->pConfig->eDetail==FTS5_DETAIL_FULL ); |
| assert( pColset ); |
| |
| if( pSeg->iLeafOffset+pSeg->nPos<=pSeg->pLeaf->szLeaf ){ |
| /* All data is stored on the current page. Populate the output |
| ** variables to point into the body of the page object. */ |
| const u8 *a = &pSeg->pLeaf->p[pSeg->iLeafOffset]; |
| if( pColset->nCol==1 ){ |
| pIter->base.nData = fts5IndexExtractCol(&a, pSeg->nPos,pColset->aiCol[0]); |
| pIter->base.pData = a; |
| }else{ |
| int *pRc = &pIter->pIndex->rc; |
| fts5BufferZero(&pIter->poslist); |
| fts5IndexExtractColset(pRc, pColset, a, pSeg->nPos, &pIter->poslist); |
| pIter->base.pData = pIter->poslist.p; |
| pIter->base.nData = pIter->poslist.n; |
| } |
| }else{ |
| /* The data is distributed over two or more pages. Copy it into the |
| ** Fts5Iter.poslist buffer and then set the output pointer to point |
| ** to this buffer. */ |
| fts5BufferZero(&pIter->poslist); |
| fts5SegiterPoslist(pIter->pIndex, pSeg, pColset, &pIter->poslist); |
| pIter->base.pData = pIter->poslist.p; |
| pIter->base.nData = pIter->poslist.n; |
| } |
| } |
| |
| static void fts5IterSetOutputCb(int *pRc, Fts5Iter *pIter){ |
| if( *pRc==SQLITE_OK ){ |
| Fts5Config *pConfig = pIter->pIndex->pConfig; |
| if( pConfig->eDetail==FTS5_DETAIL_NONE ){ |
| pIter->xSetOutputs = fts5IterSetOutputs_None; |
| } |
| |
| else if( pIter->pColset==0 ){ |
| pIter->xSetOutputs = fts5IterSetOutputs_Nocolset; |
| } |
| |
| else if( pIter->pColset->nCol==0 ){ |
| pIter->xSetOutputs = fts5IterSetOutputs_ZeroColset; |
| } |
| |
| else if( pConfig->eDetail==FTS5_DETAIL_FULL ){ |
| pIter->xSetOutputs = fts5IterSetOutputs_Full; |
| } |
| |
| else{ |
| assert( pConfig->eDetail==FTS5_DETAIL_COLUMNS ); |
| if( pConfig->nCol<=100 ){ |
| pIter->xSetOutputs = fts5IterSetOutputs_Col100; |
| sqlite3Fts5BufferSize(pRc, &pIter->poslist, pConfig->nCol); |
| }else{ |
| pIter->xSetOutputs = fts5IterSetOutputs_Col; |
| } |
| } |
| } |
| } |
| |
| |
| /* |
| ** Allocate a new Fts5Iter object. |
| ** |
| ** The new object will be used to iterate through data in structure pStruct. |
| ** If iLevel is -ve, then all data in all segments is merged. Or, if iLevel |
| ** is zero or greater, data from the first nSegment segments on level iLevel |
| ** is merged. |
| ** |
| ** The iterator initially points to the first term/rowid entry in the |
| ** iterated data. |
| */ |
| static void fts5MultiIterNew( |
| Fts5Index *p, /* FTS5 backend to iterate within */ |
| Fts5Structure *pStruct, /* Structure of specific index */ |
| int flags, /* FTS5INDEX_QUERY_XXX flags */ |
| Fts5Colset *pColset, /* Colset to filter on (or NULL) */ |
| const u8 *pTerm, int nTerm, /* Term to seek to (or NULL/0) */ |
| int iLevel, /* Level to iterate (-1 for all) */ |
| int nSegment, /* Number of segments to merge (iLevel>=0) */ |
| Fts5Iter **ppOut /* New object */ |
| ){ |
| int nSeg = 0; /* Number of segment-iters in use */ |
| int iIter = 0; /* */ |
| int iSeg; /* Used to iterate through segments */ |
| Fts5StructureLevel *pLvl; |
| Fts5Iter *pNew; |
| |
| assert( (pTerm==0 && nTerm==0) || iLevel<0 ); |
| |
| /* Allocate space for the new multi-seg-iterator. */ |
| if( p->rc==SQLITE_OK ){ |
| if( iLevel<0 ){ |
| assert( pStruct->nSegment==fts5StructureCountSegments(pStruct) ); |
| nSeg = pStruct->nSegment; |
| nSeg += (p->pHash ? 1 : 0); |
| }else{ |
| nSeg = MIN(pStruct->aLevel[iLevel].nSeg, nSegment); |
| } |
| } |
| *ppOut = pNew = fts5MultiIterAlloc(p, nSeg); |
| if( pNew==0 ) return; |
| pNew->bRev = (0!=(flags & FTS5INDEX_QUERY_DESC)); |
| pNew->bSkipEmpty = (0!=(flags & FTS5INDEX_QUERY_SKIPEMPTY)); |
| pNew->pStruct = pStruct; |
| pNew->pColset = pColset; |
| fts5StructureRef(pStruct); |
| if( (flags & FTS5INDEX_QUERY_NOOUTPUT)==0 ){ |
| fts5IterSetOutputCb(&p->rc, pNew); |
| } |
| |
| /* Initialize each of the component segment iterators. */ |
| if( p->rc==SQLITE_OK ){ |
| if( iLevel<0 ){ |
| Fts5StructureLevel *pEnd = &pStruct->aLevel[pStruct->nLevel]; |
| if( p->pHash ){ |
| /* Add a segment iterator for the current contents of the hash table. */ |
| Fts5SegIter *pIter = &pNew->aSeg[iIter++]; |
| fts5SegIterHashInit(p, pTerm, nTerm, flags, pIter); |
| } |
| for(pLvl=&pStruct->aLevel[0]; pLvl<pEnd; pLvl++){ |
| for(iSeg=pLvl->nSeg-1; iSeg>=0; iSeg--){ |
| Fts5StructureSegment *pSeg = &pLvl->aSeg[iSeg]; |
| Fts5SegIter *pIter = &pNew->aSeg[iIter++]; |
| if( pTerm==0 ){ |
| fts5SegIterInit(p, pSeg, pIter); |
| }else{ |
| fts5SegIterSeekInit(p, pTerm, nTerm, flags, pSeg, pIter); |
| } |
| } |
| } |
| }else{ |
| pLvl = &pStruct->aLevel[iLevel]; |
| for(iSeg=nSeg-1; iSeg>=0; iSeg--){ |
| fts5SegIterInit(p, &pLvl->aSeg[iSeg], &pNew->aSeg[iIter++]); |
| } |
| } |
| assert( iIter==nSeg ); |
| } |
| |
| /* If the above was successful, each component iterators now points |
| ** to the first entry in its segment. In this case initialize the |
| ** aFirst[] array. Or, if an error has occurred, free the iterator |
| ** object and set the output variable to NULL. */ |
| if( p->rc==SQLITE_OK ){ |
| for(iIter=pNew->nSeg-1; iIter>0; iIter--){ |
| int iEq; |
| if( (iEq = fts5MultiIterDoCompare(pNew, iIter)) ){ |
| Fts5SegIter *pSeg = &pNew->aSeg[iEq]; |
| if( p->rc==SQLITE_OK ) pSeg->xNext(p, pSeg, 0); |
| fts5MultiIterAdvanced(p, pNew, iEq, iIter); |
| } |
| } |
| fts5MultiIterSetEof(pNew); |
| fts5AssertMultiIterSetup(p, pNew); |
| |
| if( pNew->bSkipEmpty && fts5MultiIterIsEmpty(p, pNew) ){ |
| fts5MultiIterNext(p, pNew, 0, 0); |
| }else if( pNew->base.bEof==0 ){ |
| Fts5SegIter *pSeg = &pNew->aSeg[pNew->aFirst[1].iFirst]; |
| pNew->xSetOutputs(pNew, pSeg); |
| } |
| |
| }else{ |
| fts5MultiIterFree(pNew); |
| *ppOut = 0; |
| } |
| } |
| |
| /* |
| ** Create an Fts5Iter that iterates through the doclist provided |
| ** as the second argument. |
| */ |
| static void fts5MultiIterNew2( |
| Fts5Index *p, /* FTS5 backend to iterate within */ |
| Fts5Data *pData, /* Doclist to iterate through */ |
| int bDesc, /* True for descending rowid order */ |
| Fts5Iter **ppOut /* New object */ |
| ){ |
| Fts5Iter *pNew; |
| pNew = fts5MultiIterAlloc(p, 2); |
| if( pNew ){ |
| Fts5SegIter *pIter = &pNew->aSeg[1]; |
| |
| pIter->flags = FTS5_SEGITER_ONETERM; |
| if( pData->szLeaf>0 ){ |
| pIter->pLeaf = pData; |
| pIter->iLeafOffset = fts5GetVarint(pData->p, (u64*)&pIter->iRowid); |
| pIter->iEndofDoclist = pData->nn; |
| pNew->aFirst[1].iFirst = 1; |
| if( bDesc ){ |
| pNew->bRev = 1; |
| pIter->flags |= FTS5_SEGITER_REVERSE; |
| fts5SegIterReverseInitPage(p, pIter); |
| }else{ |
| fts5SegIterLoadNPos(p, pIter); |
| } |
| pData = 0; |
| }else{ |
| pNew->base.bEof = 1; |
| } |
| fts5SegIterSetNext(p, pIter); |
| |
| *ppOut = pNew; |
| } |
| |
| fts5DataRelease(pData); |
| } |
| |
| /* |
| ** Return true if the iterator is at EOF or if an error has occurred. |
| ** False otherwise. |
| */ |
| static int fts5MultiIterEof(Fts5Index *p, Fts5Iter *pIter){ |
| assert( p->rc |
| || (pIter->aSeg[ pIter->aFirst[1].iFirst ].pLeaf==0)==pIter->base.bEof |
| ); |
| return (p->rc || pIter->base.bEof); |
| } |
| |
| /* |
| ** Return the rowid of the entry that the iterator currently points |
| ** to. If the iterator points to EOF when this function is called the |
| ** results are undefined. |
| */ |
| static i64 fts5MultiIterRowid(Fts5Iter *pIter){ |
| assert( pIter->aSeg[ pIter->aFirst[1].iFirst ].pLeaf ); |
| return pIter->aSeg[ pIter->aFirst[1].iFirst ].iRowid; |
| } |
| |
| /* |
| ** Move the iterator to the next entry at or following iMatch. |
| */ |
| static void fts5MultiIterNextFrom( |
| Fts5Index *p, |
| Fts5Iter *pIter, |
| i64 iMatch |
| ){ |
| while( 1 ){ |
| i64 iRowid; |
| fts5MultiIterNext(p, pIter, 1, iMatch); |
| if( fts5MultiIterEof(p, pIter) ) break; |
| iRowid = fts5MultiIterRowid(pIter); |
| if( pIter->bRev==0 && iRowid>=iMatch ) break; |
| if( pIter->bRev!=0 && iRowid<=iMatch ) break; |
| } |
| } |
| |
| /* |
| ** Return a pointer to a buffer containing the term associated with the |
| ** entry that the iterator currently points to. |
| */ |
| static const u8 *fts5MultiIterTerm(Fts5Iter *pIter, int *pn){ |
| Fts5SegIter *p = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; |
| *pn = p->term.n; |
| return p->term.p; |
| } |
| |
| /* |
| ** Allocate a new segment-id for the structure pStruct. The new segment |
| ** id must be between 1 and 65335 inclusive, and must not be used by |
| ** any currently existing segment. If a free segment id cannot be found, |
| ** SQLITE_FULL is returned. |
| ** |
| ** If an error has already occurred, this function is a no-op. 0 is |
| ** returned in this case. |
| */ |
| static int fts5AllocateSegid(Fts5Index *p, Fts5Structure *pStruct){ |
| int iSegid = 0; |
| |
| if( p->rc==SQLITE_OK ){ |
| if( pStruct->nSegment>=FTS5_MAX_SEGMENT ){ |
| p->rc = SQLITE_FULL; |
| }else{ |
| /* FTS5_MAX_SEGMENT is currently defined as 2000. So the following |
| ** array is 63 elements, or 252 bytes, in size. */ |
| u32 aUsed[(FTS5_MAX_SEGMENT+31) / 32]; |
| int iLvl, iSeg; |
| int i; |
| u32 mask; |
| memset(aUsed, 0, sizeof(aUsed)); |
| for(iLvl=0; iLvl<pStruct->nLevel; iLvl++){ |
| for(iSeg=0; iSeg<pStruct->aLevel[iLvl].nSeg; iSeg++){ |
| int iId = pStruct->aLevel[iLvl].aSeg[iSeg].iSegid; |
| if( iId<=FTS5_MAX_SEGMENT ){ |
| aUsed[(iId-1) / 32] |= 1 << ((iId-1) % 32); |
| } |
| } |
| } |
| |
| for(i=0; aUsed[i]==0xFFFFFFFF; i++); |
| mask = aUsed[i]; |
| for(iSegid=0; mask & (1 << iSegid); iSegid++); |
| iSegid += 1 + i*32; |
| |
| #ifdef SQLITE_DEBUG |
| for(iLvl=0; iLvl<pStruct->nLevel; iLvl++){ |
| for(iSeg=0; iSeg<pStruct->aLevel[iLvl].nSeg; iSeg++){ |
| assert( iSegid!=pStruct->aLevel[iLvl].aSeg[iSeg].iSegid ); |
| } |
| } |
| assert( iSegid>0 && iSegid<=FTS5_MAX_SEGMENT ); |
| |
| { |
| sqlite3_stmt *pIdxSelect = fts5IdxSelectStmt(p); |
| if( p->rc==SQLITE_OK ){ |
| u8 aBlob[2] = {0xff, 0xff}; |
| sqlite3_bind_int(pIdxSelect, 1, iSegid); |
| sqlite3_bind_blob(pIdxSelect, 2, aBlob, 2, SQLITE_STATIC); |
| assert( sqlite3_step(pIdxSelect)!=SQLITE_ROW ); |
| p->rc = sqlite3_reset(pIdxSelect); |
| sqlite3_bind_null(pIdxSelect, 2); |
| } |
| } |
| #endif |
| } |
| } |
| |
| return iSegid; |
| } |
| |
| /* |
| ** Discard all data currently cached in the hash-tables. |
| */ |
| static void fts5IndexDiscardData(Fts5Index *p){ |
| assert( p->pHash || p->nPendingData==0 ); |
| if( p->pHash ){ |
| sqlite3Fts5HashClear(p->pHash); |
| p->nPendingData = 0; |
| } |
| } |
| |
| /* |
| ** Return the size of the prefix, in bytes, that buffer |
| ** (pNew/<length-unknown>) shares with buffer (pOld/nOld). |
| ** |
| ** Buffer (pNew/<length-unknown>) is guaranteed to be greater |
| ** than buffer (pOld/nOld). |
| */ |
| static int fts5PrefixCompress(int nOld, const u8 *pOld, const u8 *pNew){ |
| int i; |
| for(i=0; i<nOld; i++){ |
| if( pOld[i]!=pNew[i] ) break; |
| } |
| return i; |
| } |
| |
| static void fts5WriteDlidxClear( |
| Fts5Index *p, |
| Fts5SegWriter *pWriter, |
| int bFlush /* If true, write dlidx to disk */ |
| ){ |
| int i; |
| assert( bFlush==0 || (pWriter->nDlidx>0 && pWriter->aDlidx[0].buf.n>0) ); |
| for(i=0; i<pWriter->nDlidx; i++){ |
| Fts5DlidxWriter *pDlidx = &pWriter->aDlidx[i]; |
| if( pDlidx->buf.n==0 ) break; |
| if( bFlush ){ |
| assert( pDlidx->pgno!=0 ); |
| fts5DataWrite(p, |
| FTS5_DLIDX_ROWID(pWriter->iSegid, i, pDlidx->pgno), |
| pDlidx->buf.p, pDlidx->buf.n |
| ); |
| } |
| sqlite3Fts5BufferZero(&pDlidx->buf); |
| pDlidx->bPrevValid = 0; |
| } |
| } |
| |
| /* |
| ** Grow the pWriter->aDlidx[] array to at least nLvl elements in size. |
| ** Any new array elements are zeroed before returning. |
| */ |
| static int fts5WriteDlidxGrow( |
| Fts5Index *p, |
| Fts5SegWriter *pWriter, |
| int nLvl |
| ){ |
| if( p->rc==SQLITE_OK && nLvl>=pWriter->nDlidx ){ |
| Fts5DlidxWriter *aDlidx = (Fts5DlidxWriter*)sqlite3_realloc( |
| pWriter->aDlidx, sizeof(Fts5DlidxWriter) * nLvl |
| ); |
| if( aDlidx==0 ){ |
| p->rc = SQLITE_NOMEM; |
| }else{ |
| int nByte = sizeof(Fts5DlidxWriter) * (nLvl - pWriter->nDlidx); |
| memset(&aDlidx[pWriter->nDlidx], 0, nByte); |
| pWriter->aDlidx = aDlidx; |
| pWriter->nDlidx = nLvl; |
| } |
| } |
| return p->rc; |
| } |
| |
| /* |
| ** If the current doclist-index accumulating in pWriter->aDlidx[] is large |
| ** enough, flush it to disk and return 1. Otherwise discard it and return |
| ** zero. |
| */ |
| static int fts5WriteFlushDlidx(Fts5Index *p, Fts5SegWriter *pWriter){ |
| int bFlag = 0; |
| |
| /* If there were FTS5_MIN_DLIDX_SIZE or more empty leaf pages written |
| ** to the database, also write the doclist-index to disk. */ |
| if( pWriter->aDlidx[0].buf.n>0 && pWriter->nEmpty>=FTS5_MIN_DLIDX_SIZE ){ |
| bFlag = 1; |
| } |
| fts5WriteDlidxClear(p, pWriter, bFlag); |
| pWriter->nEmpty = 0; |
| return bFlag; |
| } |
| |
| /* |
| ** This function is called whenever processing of the doclist for the |
| ** last term on leaf page (pWriter->iBtPage) is completed. |
| ** |
| ** The doclist-index for that term is currently stored in-memory within the |
| ** Fts5SegWriter.aDlidx[] array. If it is large enough, this function |
| ** writes it out to disk. Or, if it is too small to bother with, discards |
| ** it. |
| ** |
| ** Fts5SegWriter.btterm currently contains the first term on page iBtPage. |
| */ |
| static void fts5WriteFlushBtree(Fts5Index *p, Fts5SegWriter *pWriter){ |
| int bFlag; |
| |
| assert( pWriter->iBtPage || pWriter->nEmpty==0 ); |
| if( pWriter->iBtPage==0 ) return; |
| bFlag = fts5WriteFlushDlidx(p, pWriter); |
| |
| if( p->rc==SQLITE_OK ){ |
| const char *z = (pWriter->btterm.n>0?(const char*)pWriter->btterm.p:""); |
| /* The following was already done in fts5WriteInit(): */ |
| /* sqlite3_bind_int(p->pIdxWriter, 1, pWriter->iSegid); */ |
| sqlite3_bind_blob(p->pIdxWriter, 2, z, pWriter->btterm.n, SQLITE_STATIC); |
| sqlite3_bind_int64(p->pIdxWriter, 3, bFlag + ((i64)pWriter->iBtPage<<1)); |
| sqlite3_step(p->pIdxWriter); |
| p->rc = sqlite3_reset(p->pIdxWriter); |
| sqlite3_bind_null(p->pIdxWriter, 2); |
| } |
| pWriter->iBtPage = 0; |
| } |
| |
| /* |
| ** This is called once for each leaf page except the first that contains |
| ** at least one term. Argument (nTerm/pTerm) is the split-key - a term that |
| ** is larger than all terms written to earlier leaves, and equal to or |
| ** smaller than the first term on the new leaf. |
| ** |
| ** If an error occurs, an error code is left in Fts5Index.rc. If an error |
| ** has already occurred when this function is called, it is a no-op. |
| */ |
| static void fts5WriteBtreeTerm( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5SegWriter *pWriter, /* Writer object */ |
| int nTerm, const u8 *pTerm /* First term on new page */ |
| ){ |
| fts5WriteFlushBtree(p, pWriter); |
| fts5BufferSet(&p->rc, &pWriter->btterm, nTerm, pTerm); |
| pWriter->iBtPage = pWriter->writer.pgno; |
| } |
| |
| /* |
| ** This function is called when flushing a leaf page that contains no |
| ** terms at all to disk. |
| */ |
| static void fts5WriteBtreeNoTerm( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5SegWriter *pWriter /* Writer object */ |
| ){ |
| /* If there were no rowids on the leaf page either and the doclist-index |
| ** has already been started, append an 0x00 byte to it. */ |
| if( pWriter->bFirstRowidInPage && pWriter->aDlidx[0].buf.n>0 ){ |
| Fts5DlidxWriter *pDlidx = &pWriter->aDlidx[0]; |
| assert( pDlidx->bPrevValid ); |
| sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, 0); |
| } |
| |
| /* Increment the "number of sequential leaves without a term" counter. */ |
| pWriter->nEmpty++; |
| } |
| |
| static i64 fts5DlidxExtractFirstRowid(Fts5Buffer *pBuf){ |
| i64 iRowid; |
| int iOff; |
| |
| iOff = 1 + fts5GetVarint(&pBuf->p[1], (u64*)&iRowid); |
| fts5GetVarint(&pBuf->p[iOff], (u64*)&iRowid); |
| return iRowid; |
| } |
| |
| /* |
| ** Rowid iRowid has just been appended to the current leaf page. It is the |
| ** first on the page. This function appends an appropriate entry to the current |
| ** doclist-index. |
| */ |
| static void fts5WriteDlidxAppend( |
| Fts5Index *p, |
| Fts5SegWriter *pWriter, |
| i64 iRowid |
| ){ |
| int i; |
| int bDone = 0; |
| |
| for(i=0; p->rc==SQLITE_OK && bDone==0; i++){ |
| i64 iVal; |
| Fts5DlidxWriter *pDlidx = &pWriter->aDlidx[i]; |
| |
| if( pDlidx->buf.n>=p->pConfig->pgsz ){ |
| /* The current doclist-index page is full. Write it to disk and push |
| ** a copy of iRowid (which will become the first rowid on the next |
| ** doclist-index leaf page) up into the next level of the b-tree |
| ** hierarchy. If the node being flushed is currently the root node, |
| ** also push its first rowid upwards. */ |
| pDlidx->buf.p[0] = 0x01; /* Not the root node */ |
| fts5DataWrite(p, |
| FTS5_DLIDX_ROWID(pWriter->iSegid, i, pDlidx->pgno), |
| pDlidx->buf.p, pDlidx->buf.n |
| ); |
| fts5WriteDlidxGrow(p, pWriter, i+2); |
| pDlidx = &pWriter->aDlidx[i]; |
| if( p->rc==SQLITE_OK && pDlidx[1].buf.n==0 ){ |
| i64 iFirst = fts5DlidxExtractFirstRowid(&pDlidx->buf); |
| |
| /* This was the root node. Push its first rowid up to the new root. */ |
| pDlidx[1].pgno = pDlidx->pgno; |
| sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx[1].buf, 0); |
| sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx[1].buf, pDlidx->pgno); |
| sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx[1].buf, iFirst); |
| pDlidx[1].bPrevValid = 1; |
| pDlidx[1].iPrev = iFirst; |
| } |
| |
| sqlite3Fts5BufferZero(&pDlidx->buf); |
| pDlidx->bPrevValid = 0; |
| pDlidx->pgno++; |
| }else{ |
| bDone = 1; |
| } |
| |
| if( pDlidx->bPrevValid ){ |
| iVal = iRowid - pDlidx->iPrev; |
| }else{ |
| i64 iPgno = (i==0 ? pWriter->writer.pgno : pDlidx[-1].pgno); |
| assert( pDlidx->buf.n==0 ); |
| sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, !bDone); |
| sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, iPgno); |
| iVal = iRowid; |
| } |
| |
| sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, iVal); |
| pDlidx->bPrevValid = 1; |
| pDlidx->iPrev = iRowid; |
| } |
| } |
| |
| static void fts5WriteFlushLeaf(Fts5Index *p, Fts5SegWriter *pWriter){ |
| static const u8 zero[] = { 0x00, 0x00, 0x00, 0x00 }; |
| Fts5PageWriter *pPage = &pWriter->writer; |
| i64 iRowid; |
| |
| assert( (pPage->pgidx.n==0)==(pWriter->bFirstTermInPage) ); |
| |
| /* Set the szLeaf header field. */ |
| assert( 0==fts5GetU16(&pPage->buf.p[2]) ); |
| fts5PutU16(&pPage->buf.p[2], (u16)pPage->buf.n); |
| |
| if( pWriter->bFirstTermInPage ){ |
| /* No term was written to this page. */ |
| assert( pPage->pgidx.n==0 ); |
| fts5WriteBtreeNoTerm(p, pWriter); |
| }else{ |
| /* Append the pgidx to the page buffer. Set the szLeaf header field. */ |
| fts5BufferAppendBlob(&p->rc, &pPage->buf, pPage->pgidx.n, pPage->pgidx.p); |
| } |
| |
| /* Write the page out to disk */ |
| iRowid = FTS5_SEGMENT_ROWID(pWriter->iSegid, pPage->pgno); |
| fts5DataWrite(p, iRowid, pPage->buf.p, pPage->buf.n); |
| |
| /* Initialize the next page. */ |
| fts5BufferZero(&pPage->buf); |
| fts5BufferZero(&pPage->pgidx); |
| fts5BufferAppendBlob(&p->rc, &pPage->buf, 4, zero); |
| pPage->iPrevPgidx = 0; |
| pPage->pgno++; |
| |
| /* Increase the leaves written counter */ |
| pWriter->nLeafWritten++; |
| |
| /* The new leaf holds no terms or rowids */ |
| pWriter->bFirstTermInPage = 1; |
| pWriter->bFirstRowidInPage = 1; |
| } |
| |
| /* |
| ** Append term pTerm/nTerm to the segment being written by the writer passed |
| ** as the second argument. |
| ** |
| ** If an error occurs, set the Fts5Index.rc error code. If an error has |
| ** already occurred, this function is a no-op. |
| */ |
| static void fts5WriteAppendTerm( |
| Fts5Index *p, |
| Fts5SegWriter *pWriter, |
| int nTerm, const u8 *pTerm |
| ){ |
| int nPrefix; /* Bytes of prefix compression for term */ |
| Fts5PageWriter *pPage = &pWriter->writer; |
| Fts5Buffer *pPgidx = &pWriter->writer.pgidx; |
| |
| assert( p->rc==SQLITE_OK ); |
| assert( pPage->buf.n>=4 ); |
| assert( pPage->buf.n>4 || pWriter->bFirstTermInPage ); |
| |
| /* If the current leaf page is full, flush it to disk. */ |
| if( (pPage->buf.n + pPgidx->n + nTerm + 2)>=p->pConfig->pgsz ){ |
| if( pPage->buf.n>4 ){ |
| fts5WriteFlushLeaf(p, pWriter); |
| } |
| fts5BufferGrow(&p->rc, &pPage->buf, nTerm+FTS5_DATA_PADDING); |
| } |
| |
| /* TODO1: Updating pgidx here. */ |
| pPgidx->n += sqlite3Fts5PutVarint( |
| &pPgidx->p[pPgidx->n], pPage->buf.n - pPage->iPrevPgidx |
| ); |
| pPage->iPrevPgidx = pPage->buf.n; |
| #if 0 |
| fts5PutU16(&pPgidx->p[pPgidx->n], pPage->buf.n); |
| pPgidx->n += 2; |
| #endif |
| |
| if( pWriter->bFirstTermInPage ){ |
| nPrefix = 0; |
| if( pPage->pgno!=1 ){ |
| /* This is the first term on a leaf that is not the leftmost leaf in |
| ** the segment b-tree. In this case it is necessary to add a term to |
| ** the b-tree hierarchy that is (a) larger than the largest term |
| ** already written to the segment and (b) smaller than or equal to |
| ** this term. In other words, a prefix of (pTerm/nTerm) that is one |
| ** byte longer than the longest prefix (pTerm/nTerm) shares with the |
| ** previous term. |
| ** |
| ** Usually, the previous term is available in pPage->term. The exception |
| ** is if this is the first term written in an incremental-merge step. |
| ** In this case the previous term is not available, so just write a |
| ** copy of (pTerm/nTerm) into the parent node. This is slightly |
| ** inefficient, but still correct. */ |
| int n = nTerm; |
| if( pPage->term.n ){ |
| n = 1 + fts5PrefixCompress(pPage->term.n, pPage->term.p, pTerm); |
| } |
| fts5WriteBtreeTerm(p, pWriter, n, pTerm); |
| pPage = &pWriter->writer; |
| } |
| }else{ |
| nPrefix = fts5PrefixCompress(pPage->term.n, pPage->term.p, pTerm); |
| fts5BufferAppendVarint(&p->rc, &pPage->buf, nPrefix); |
| } |
| |
| /* Append the number of bytes of new data, then the term data itself |
| ** to the page. */ |
| fts5BufferAppendVarint(&p->rc, &pPage->buf, nTerm - nPrefix); |
| fts5BufferAppendBlob(&p->rc, &pPage->buf, nTerm - nPrefix, &pTerm[nPrefix]); |
| |
| /* Update the Fts5PageWriter.term field. */ |
| fts5BufferSet(&p->rc, &pPage->term, nTerm, pTerm); |
| pWriter->bFirstTermInPage = 0; |
| |
| pWriter->bFirstRowidInPage = 0; |
| pWriter->bFirstRowidInDoclist = 1; |
| |
| assert( p->rc || (pWriter->nDlidx>0 && pWriter->aDlidx[0].buf.n==0) ); |
| pWriter->aDlidx[0].pgno = pPage->pgno; |
| } |
| |
| /* |
| ** Append a rowid and position-list size field to the writers output. |
| */ |
| static void fts5WriteAppendRowid( |
| Fts5Index *p, |
| Fts5SegWriter *pWriter, |
| i64 iRowid |
| ){ |
| if( p->rc==SQLITE_OK ){ |
| Fts5PageWriter *pPage = &pWriter->writer; |
| |
| if( (pPage->buf.n + pPage->pgidx.n)>=p->pConfig->pgsz ){ |
| fts5WriteFlushLeaf(p, pWriter); |
| } |
| |
| /* If this is to be the first rowid written to the page, set the |
| ** rowid-pointer in the page-header. Also append a value to the dlidx |
| ** buffer, in case a doclist-index is required. */ |
| if( pWriter->bFirstRowidInPage ){ |
| fts5PutU16(pPage->buf.p, (u16)pPage->buf.n); |
| fts5WriteDlidxAppend(p, pWriter, iRowid); |
| } |
| |
| /* Write the rowid. */ |
| if( pWriter->bFirstRowidInDoclist || pWriter->bFirstRowidInPage ){ |
| fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid); |
| }else{ |
| assert( p->rc || iRowid>pWriter->iPrevRowid ); |
| fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid - pWriter->iPrevRowid); |
| } |
| pWriter->iPrevRowid = iRowid; |
| pWriter->bFirstRowidInDoclist = 0; |
| pWriter->bFirstRowidInPage = 0; |
| } |
| } |
| |
| static void fts5WriteAppendPoslistData( |
| Fts5Index *p, |
| Fts5SegWriter *pWriter, |
| const u8 *aData, |
| int nData |
| ){ |
| Fts5PageWriter *pPage = &pWriter->writer; |
| const u8 *a = aData; |
| int n = nData; |
| |
| assert( p->pConfig->pgsz>0 ); |
| while( p->rc==SQLITE_OK |
| && (pPage->buf.n + pPage->pgidx.n + n)>=p->pConfig->pgsz |
| ){ |
| int nReq = p->pConfig->pgsz - pPage->buf.n - pPage->pgidx.n; |
| int nCopy = 0; |
| while( nCopy<nReq ){ |
| i64 dummy; |
| nCopy += fts5GetVarint(&a[nCopy], (u64*)&dummy); |
| } |
| fts5BufferAppendBlob(&p->rc, &pPage->buf, nCopy, a); |
| a += nCopy; |
| n -= nCopy; |
| fts5WriteFlushLeaf(p, pWriter); |
| } |
| if( n>0 ){ |
| fts5BufferAppendBlob(&p->rc, &pPage->buf, n, a); |
| } |
| } |
| |
| /* |
| ** Flush any data cached by the writer object to the database. Free any |
| ** allocations associated with the writer. |
| */ |
| static void fts5WriteFinish( |
| Fts5Index *p, |
| Fts5SegWriter *pWriter, /* Writer object */ |
| int *pnLeaf /* OUT: Number of leaf pages in b-tree */ |
| ){ |
| int i; |
| Fts5PageWriter *pLeaf = &pWriter->writer; |
| if( p->rc==SQLITE_OK ){ |
| assert( pLeaf->pgno>=1 ); |
| if( pLeaf->buf.n>4 ){ |
| fts5WriteFlushLeaf(p, pWriter); |
| } |
| *pnLeaf = pLeaf->pgno-1; |
| if( pLeaf->pgno>1 ){ |
| fts5WriteFlushBtree(p, pWriter); |
| } |
| } |
| fts5BufferFree(&pLeaf->term); |
| fts5BufferFree(&pLeaf->buf); |
| fts5BufferFree(&pLeaf->pgidx); |
| fts5BufferFree(&pWriter->btterm); |
| |
| for(i=0; i<pWriter->nDlidx; i++){ |
| sqlite3Fts5BufferFree(&pWriter->aDlidx[i].buf); |
| } |
| sqlite3_free(pWriter->aDlidx); |
| } |
| |
| static void fts5WriteInit( |
| Fts5Index *p, |
| Fts5SegWriter *pWriter, |
| int iSegid |
| ){ |
| const int nBuffer = p->pConfig->pgsz + FTS5_DATA_PADDING; |
| |
| memset(pWriter, 0, sizeof(Fts5SegWriter)); |
| pWriter->iSegid = iSegid; |
| |
| fts5WriteDlidxGrow(p, pWriter, 1); |
| pWriter->writer.pgno = 1; |
| pWriter->bFirstTermInPage = 1; |
| pWriter->iBtPage = 1; |
| |
| assert( pWriter->writer.buf.n==0 ); |
| assert( pWriter->writer.pgidx.n==0 ); |
| |
| /* Grow the two buffers to pgsz + padding bytes in size. */ |
| sqlite3Fts5BufferSize(&p->rc, &pWriter->writer.pgidx, nBuffer); |
| sqlite3Fts5BufferSize(&p->rc, &pWriter->writer.buf, nBuffer); |
| |
| if( p->pIdxWriter==0 ){ |
| Fts5Config *pConfig = p->pConfig; |
| fts5IndexPrepareStmt(p, &p->pIdxWriter, sqlite3_mprintf( |
| "INSERT INTO '%q'.'%q_idx'(segid,term,pgno) VALUES(?,?,?)", |
| pConfig->zDb, pConfig->zName |
| )); |
| } |
| |
| if( p->rc==SQLITE_OK ){ |
| /* Initialize the 4-byte leaf-page header to 0x00. */ |
| memset(pWriter->writer.buf.p, 0, 4); |
| pWriter->writer.buf.n = 4; |
| |
| /* Bind the current output segment id to the index-writer. This is an |
| ** optimization over binding the same value over and over as rows are |
| ** inserted into %_idx by the current writer. */ |
| sqlite3_bind_int(p->pIdxWriter, 1, pWriter->iSegid); |
| } |
| } |
| |
| /* |
| ** Iterator pIter was used to iterate through the input segments of on an |
| ** incremental merge operation. This function is called if the incremental |
| ** merge step has finished but the input has not been completely exhausted. |
| */ |
| static void fts5TrimSegments(Fts5Index *p, Fts5Iter *pIter){ |
| int i; |
| Fts5Buffer buf; |
| memset(&buf, 0, sizeof(Fts5Buffer)); |
| for(i=0; i<pIter->nSeg; i++){ |
| Fts5SegIter *pSeg = &pIter->aSeg[i]; |
| if( pSeg->pSeg==0 ){ |
| /* no-op */ |
| }else if( pSeg->pLeaf==0 ){ |
| /* All keys from this input segment have been transfered to the output. |
| ** Set both the first and last page-numbers to 0 to indicate that the |
| ** segment is now empty. */ |
| pSeg->pSeg->pgnoLast = 0; |
| pSeg->pSeg->pgnoFirst = 0; |
| }else{ |
| int iOff = pSeg->iTermLeafOffset; /* Offset on new first leaf page */ |
| i64 iLeafRowid; |
| Fts5Data *pData; |
| int iId = pSeg->pSeg->iSegid; |
| u8 aHdr[4] = {0x00, 0x00, 0x00, 0x00}; |
| |
| iLeafRowid = FTS5_SEGMENT_ROWID(iId, pSeg->iTermLeafPgno); |
| pData = fts5DataRead(p, iLeafRowid); |
| if( pData ){ |
| fts5BufferZero(&buf); |
| fts5BufferGrow(&p->rc, &buf, pData->nn); |
| fts5BufferAppendBlob(&p->rc, &buf, sizeof(aHdr), aHdr); |
| fts5BufferAppendVarint(&p->rc, &buf, pSeg->term.n); |
| fts5BufferAppendBlob(&p->rc, &buf, pSeg->term.n, pSeg->term.p); |
| fts5BufferAppendBlob(&p->rc, &buf, pData->szLeaf-iOff, &pData->p[iOff]); |
| if( p->rc==SQLITE_OK ){ |
| /* Set the szLeaf field */ |
| fts5PutU16(&buf.p[2], (u16)buf.n); |
| } |
| |
| /* Set up the new page-index array */ |
| fts5BufferAppendVarint(&p->rc, &buf, 4); |
| if( pSeg->iLeafPgno==pSeg->iTermLeafPgno |
| && pSeg->iEndofDoclist<pData->szLeaf |
| ){ |
| int nDiff = pData->szLeaf - pSeg->iEndofDoclist; |
| fts5BufferAppendVarint(&p->rc, &buf, buf.n - 1 - nDiff - 4); |
| fts5BufferAppendBlob(&p->rc, &buf, |
| pData->nn - pSeg->iPgidxOff, &pData->p[pSeg->iPgidxOff] |
| ); |
| } |
| |
| fts5DataRelease(pData); |
| pSeg->pSeg->pgnoFirst = pSeg->iTermLeafPgno; |
| fts5DataDelete(p, FTS5_SEGMENT_ROWID(iId, 1), iLeafRowid); |
| fts5DataWrite(p, iLeafRowid, buf.p, buf.n); |
| } |
| } |
| } |
| fts5BufferFree(&buf); |
| } |
| |
| static void fts5MergeChunkCallback( |
| Fts5Index *p, |
| void *pCtx, |
| const u8 *pChunk, int nChunk |
| ){ |
| Fts5SegWriter *pWriter = (Fts5SegWriter*)pCtx; |
| fts5WriteAppendPoslistData(p, pWriter, pChunk, nChunk); |
| } |
| |
| /* |
| ** |
| */ |
| static void fts5IndexMergeLevel( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5Structure **ppStruct, /* IN/OUT: Stucture of index */ |
| int iLvl, /* Level to read input from */ |
| int *pnRem /* Write up to this many output leaves */ |
| ){ |
| Fts5Structure *pStruct = *ppStruct; |
| Fts5StructureLevel *pLvl = &pStruct->aLevel[iLvl]; |
| Fts5StructureLevel *pLvlOut; |
| Fts5Iter *pIter = 0; /* Iterator to read input data */ |
| int nRem = pnRem ? *pnRem : 0; /* Output leaf pages left to write */ |
| int nInput; /* Number of input segments */ |
| Fts5SegWriter writer; /* Writer object */ |
| Fts5StructureSegment *pSeg; /* Output segment */ |
| Fts5Buffer term; |
| int bOldest; /* True if the output segment is the oldest */ |
| int eDetail = p->pConfig->eDetail; |
| const int flags = FTS5INDEX_QUERY_NOOUTPUT; |
| int bTermWritten = 0; /* True if current term already output */ |
| |
| assert( iLvl<pStruct->nLevel ); |
| assert( pLvl->nMerge<=pLvl->nSeg ); |
| |
| memset(&writer, 0, sizeof(Fts5SegWriter)); |
| memset(&term, 0, sizeof(Fts5Buffer)); |
| if( pLvl->nMerge ){ |
| pLvlOut = &pStruct->aLevel[iLvl+1]; |
| assert( pLvlOut->nSeg>0 ); |
| nInput = pLvl->nMerge; |
| pSeg = &pLvlOut->aSeg[pLvlOut->nSeg-1]; |
| |
| fts5WriteInit(p, &writer, pSeg->iSegid); |
| writer.writer.pgno = pSeg->pgnoLast+1; |
| writer.iBtPage = 0; |
| }else{ |
| int iSegid = fts5AllocateSegid(p, pStruct); |
| |
| /* Extend the Fts5Structure object as required to ensure the output |
| ** segment exists. */ |
| if( iLvl==pStruct->nLevel-1 ){ |
| fts5StructureAddLevel(&p->rc, ppStruct); |
| pStruct = *ppStruct; |
| } |
| fts5StructureExtendLevel(&p->rc, pStruct, iLvl+1, 1, 0); |
| if( p->rc ) return; |
| pLvl = &pStruct->aLevel[iLvl]; |
| pLvlOut = &pStruct->aLevel[iLvl+1]; |
| |
| fts5WriteInit(p, &writer, iSegid); |
| |
| /* Add the new segment to the output level */ |
| pSeg = &pLvlOut->aSeg[pLvlOut->nSeg]; |
| pLvlOut->nSeg++; |
| pSeg->pgnoFirst = 1; |
| pSeg->iSegid = iSegid; |
| pStruct->nSegment++; |
| |
| /* Read input from all segments in the input level */ |
| nInput = pLvl->nSeg; |
| } |
| bOldest = (pLvlOut->nSeg==1 && pStruct->nLevel==iLvl+2); |
| |
| assert( iLvl>=0 ); |
| for(fts5MultiIterNew(p, pStruct, flags, 0, 0, 0, iLvl, nInput, &pIter); |
| fts5MultiIterEof(p, pIter)==0; |
| fts5MultiIterNext(p, pIter, 0, 0) |
| ){ |
| Fts5SegIter *pSegIter = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; |
| int nPos; /* position-list size field value */ |
| int nTerm; |
| const u8 *pTerm; |
| |
| pTerm = fts5MultiIterTerm(pIter, &nTerm); |
| if( nTerm!=term.n || memcmp(pTerm, term.p, nTerm) ){ |
| if( pnRem && writer.nLeafWritten>nRem ){ |
| break; |
| } |
| fts5BufferSet(&p->rc, &term, nTerm, pTerm); |
| bTermWritten =0; |
| } |
| |
| /* Check for key annihilation. */ |
| if( pSegIter->nPos==0 && (bOldest || pSegIter->bDel==0) ) continue; |
| |
| if( p->rc==SQLITE_OK && bTermWritten==0 ){ |
| /* This is a new term. Append a term to the output segment. */ |
| fts5WriteAppendTerm(p, &writer, nTerm, pTerm); |
| bTermWritten = 1; |
| } |
| |
| /* Append the rowid to the output */ |
| /* WRITEPOSLISTSIZE */ |
| fts5WriteAppendRowid(p, &writer, fts5MultiIterRowid(pIter)); |
| |
| if( eDetail==FTS5_DETAIL_NONE ){ |
| if( pSegIter->bDel ){ |
| fts5BufferAppendVarint(&p->rc, &writer.writer.buf, 0); |
| if( pSegIter->nPos>0 ){ |
| fts5BufferAppendVarint(&p->rc, &writer.writer.buf, 0); |
| } |
| } |
| }else{ |
| /* Append the position-list data to the output */ |
| nPos = pSegIter->nPos*2 + pSegIter->bDel; |
| fts5BufferAppendVarint(&p->rc, &writer.writer.buf, nPos); |
| fts5ChunkIterate(p, pSegIter, (void*)&writer, fts5MergeChunkCallback); |
| } |
| } |
| |
| /* Flush the last leaf page to disk. Set the output segment b-tree height |
| ** and last leaf page number at the same time. */ |
| fts5WriteFinish(p, &writer, &pSeg->pgnoLast); |
| |
| if( fts5MultiIterEof(p, pIter) ){ |
| int i; |
| |
| /* Remove the redundant segments from the %_data table */ |
| for(i=0; i<nInput; i++){ |
| fts5DataRemoveSegment(p, pLvl->aSeg[i].iSegid); |
| } |
| |
| /* Remove the redundant segments from the input level */ |
| if( pLvl->nSeg!=nInput ){ |
| int nMove = (pLvl->nSeg - nInput) * sizeof(Fts5StructureSegment); |
| memmove(pLvl->aSeg, &pLvl->aSeg[nInput], nMove); |
| } |
| pStruct->nSegment -= nInput; |
| pLvl->nSeg -= nInput; |
| pLvl->nMerge = 0; |
| if( pSeg->pgnoLast==0 ){ |
| pLvlOut->nSeg--; |
| pStruct->nSegment--; |
| } |
| }else{ |
| assert( pSeg->pgnoLast>0 ); |
| fts5TrimSegments(p, pIter); |
| pLvl->nMerge = nInput; |
| } |
| |
| fts5MultiIterFree(pIter); |
| fts5BufferFree(&term); |
| if( pnRem ) *pnRem -= writer.nLeafWritten; |
| } |
| |
| /* |
| ** Do up to nPg pages of automerge work on the index. |
| ** |
| ** Return true if any changes were actually made, or false otherwise. |
| */ |
| static int fts5IndexMerge( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5Structure **ppStruct, /* IN/OUT: Current structure of index */ |
| int nPg, /* Pages of work to do */ |
| int nMin /* Minimum number of segments to merge */ |
| ){ |
| int nRem = nPg; |
| int bRet = 0; |
| Fts5Structure *pStruct = *ppStruct; |
| while( nRem>0 && p->rc==SQLITE_OK ){ |
| int iLvl; /* To iterate through levels */ |
| int iBestLvl = 0; /* Level offering the most input segments */ |
| int nBest = 0; /* Number of input segments on best level */ |
| |
| /* Set iBestLvl to the level to read input segments from. */ |
| assert( pStruct->nLevel>0 ); |
| for(iLvl=0; iLvl<pStruct->nLevel; iLvl++){ |
| Fts5StructureLevel *pLvl = &pStruct->aLevel[iLvl]; |
| if( pLvl->nMerge ){ |
| if( pLvl->nMerge>nBest ){ |
| iBestLvl = iLvl; |
| nBest = pLvl->nMerge; |
| } |
| break; |
| } |
| if( pLvl->nSeg>nBest ){ |
| nBest = pLvl->nSeg; |
| iBestLvl = iLvl; |
| } |
| } |
| |
| /* If nBest is still 0, then the index must be empty. */ |
| #ifdef SQLITE_DEBUG |
| for(iLvl=0; nBest==0 && iLvl<pStruct->nLevel; iLvl++){ |
| assert( pStruct->aLevel[iLvl].nSeg==0 ); |
| } |
| #endif |
| |
| if( nBest<nMin && pStruct->aLevel[iBestLvl].nMerge==0 ){ |
| break; |
| } |
| bRet = 1; |
| fts5IndexMergeLevel(p, &pStruct, iBestLvl, &nRem); |
| if( p->rc==SQLITE_OK && pStruct->aLevel[iBestLvl].nMerge==0 ){ |
| fts5StructurePromote(p, iBestLvl+1, pStruct); |
| } |
| } |
| *ppStruct = pStruct; |
| return bRet; |
| } |
| |
| /* |
| ** A total of nLeaf leaf pages of data has just been flushed to a level-0 |
| ** segment. This function updates the write-counter accordingly and, if |
| ** necessary, performs incremental merge work. |
| ** |
| ** If an error occurs, set the Fts5Index.rc error code. If an error has |
| ** already occurred, this function is a no-op. |
| */ |
| static void fts5IndexAutomerge( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5Structure **ppStruct, /* IN/OUT: Current structure of index */ |
| int nLeaf /* Number of output leaves just written */ |
| ){ |
| if( p->rc==SQLITE_OK && p->pConfig->nAutomerge>0 ){ |
| Fts5Structure *pStruct = *ppStruct; |
| u64 nWrite; /* Initial value of write-counter */ |
| int nWork; /* Number of work-quanta to perform */ |
| int nRem; /* Number of leaf pages left to write */ |
| |
| /* Update the write-counter. While doing so, set nWork. */ |
| nWrite = pStruct->nWriteCounter; |
| nWork = (int)(((nWrite + nLeaf) / p->nWorkUnit) - (nWrite / p->nWorkUnit)); |
| pStruct->nWriteCounter += nLeaf; |
| nRem = (int)(p->nWorkUnit * nWork * pStruct->nLevel); |
| |
| fts5IndexMerge(p, ppStruct, nRem, p->pConfig->nAutomerge); |
| } |
| } |
| |
| static void fts5IndexCrisismerge( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5Structure **ppStruct /* IN/OUT: Current structure of index */ |
| ){ |
| const int nCrisis = p->pConfig->nCrisisMerge; |
| Fts5Structure *pStruct = *ppStruct; |
| int iLvl = 0; |
| |
| assert( p->rc!=SQLITE_OK || pStruct->nLevel>0 ); |
| while( p->rc==SQLITE_OK && pStruct->aLevel[iLvl].nSeg>=nCrisis ){ |
| fts5IndexMergeLevel(p, &pStruct, iLvl, 0); |
| assert( p->rc!=SQLITE_OK || pStruct->nLevel>(iLvl+1) ); |
| fts5StructurePromote(p, iLvl+1, pStruct); |
| iLvl++; |
| } |
| *ppStruct = pStruct; |
| } |
| |
| static int fts5IndexReturn(Fts5Index *p){ |
| int rc = p->rc; |
| p->rc = SQLITE_OK; |
| return rc; |
| } |
| |
| typedef struct Fts5FlushCtx Fts5FlushCtx; |
| struct Fts5FlushCtx { |
| Fts5Index *pIdx; |
| Fts5SegWriter writer; |
| }; |
| |
| /* |
| ** Buffer aBuf[] contains a list of varints, all small enough to fit |
| ** in a 32-bit integer. Return the size of the largest prefix of this |
| ** list nMax bytes or less in size. |
| */ |
| static int fts5PoslistPrefix(const u8 *aBuf, int nMax){ |
| int ret; |
| u32 dummy; |
| ret = fts5GetVarint32(aBuf, dummy); |
| if( ret<nMax ){ |
| while( 1 ){ |
| int i = fts5GetVarint32(&aBuf[ret], dummy); |
| if( (ret + i) > nMax ) break; |
| ret += i; |
| } |
| } |
| return ret; |
| } |
| |
| /* |
| ** Flush the contents of in-memory hash table iHash to a new level-0 |
| ** segment on disk. Also update the corresponding structure record. |
| ** |
| ** If an error occurs, set the Fts5Index.rc error code. If an error has |
| ** already occurred, this function is a no-op. |
| */ |
| static void fts5FlushOneHash(Fts5Index *p){ |
| Fts5Hash *pHash = p->pHash; |
| Fts5Structure *pStruct; |
| int iSegid; |
| int pgnoLast = 0; /* Last leaf page number in segment */ |
| |
| /* Obtain a reference to the index structure and allocate a new segment-id |
| ** for the new level-0 segment. */ |
| pStruct = fts5StructureRead(p); |
| iSegid = fts5AllocateSegid(p, pStruct); |
| fts5StructureInvalidate(p); |
| |
| if( iSegid ){ |
| const int pgsz = p->pConfig->pgsz; |
| int eDetail = p->pConfig->eDetail; |
| Fts5StructureSegment *pSeg; /* New segment within pStruct */ |
| Fts5Buffer *pBuf; /* Buffer in which to assemble leaf page */ |
| Fts5Buffer *pPgidx; /* Buffer in which to assemble pgidx */ |
| |
| Fts5SegWriter writer; |
| fts5WriteInit(p, &writer, iSegid); |
| |
| pBuf = &writer.writer.buf; |
| pPgidx = &writer.writer.pgidx; |
| |
| /* fts5WriteInit() should have initialized the buffers to (most likely) |
| ** the maximum space required. */ |
| assert( p->rc || pBuf->nSpace>=(pgsz + FTS5_DATA_PADDING) ); |
| assert( p->rc || pPgidx->nSpace>=(pgsz + FTS5_DATA_PADDING) ); |
| |
| /* Begin scanning through hash table entries. This loop runs once for each |
| ** term/doclist currently stored within the hash table. */ |
| if( p->rc==SQLITE_OK ){ |
| p->rc = sqlite3Fts5HashScanInit(pHash, 0, 0); |
| } |
| while( p->rc==SQLITE_OK && 0==sqlite3Fts5HashScanEof(pHash) ){ |
| const char *zTerm; /* Buffer containing term */ |
| const u8 *pDoclist; /* Pointer to doclist for this term */ |
| int nDoclist; /* Size of doclist in bytes */ |
| |
| /* Write the term for this entry to disk. */ |
| sqlite3Fts5HashScanEntry(pHash, &zTerm, &pDoclist, &nDoclist); |
| fts5WriteAppendTerm(p, &writer, (int)strlen(zTerm), (const u8*)zTerm); |
| |
| assert( writer.bFirstRowidInPage==0 ); |
| if( pgsz>=(pBuf->n + pPgidx->n + nDoclist + 1) ){ |
| /* The entire doclist will fit on the current leaf. */ |
| fts5BufferSafeAppendBlob(pBuf, pDoclist, nDoclist); |
| }else{ |
| i64 iRowid = 0; |
| i64 iDelta = 0; |
| int iOff = 0; |
| |
| /* The entire doclist will not fit on this leaf. The following |
| ** loop iterates through the poslists that make up the current |
| ** doclist. */ |
| while( p->rc==SQLITE_OK && iOff<nDoclist ){ |
| iOff += fts5GetVarint(&pDoclist[iOff], (u64*)&iDelta); |
| iRowid += iDelta; |
| |
| if( writer.bFirstRowidInPage ){ |
| fts5PutU16(&pBuf->p[0], (u16)pBuf->n); /* first rowid on page */ |
| pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iRowid); |
| writer.bFirstRowidInPage = 0; |
| fts5WriteDlidxAppend(p, &writer, iRowid); |
| }else{ |
| pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iDelta); |
| } |
| assert( pBuf->n<=pBuf->nSpace ); |
| |
| if( eDetail==FTS5_DETAIL_NONE ){ |
| if( iOff<nDoclist && pDoclist[iOff]==0 ){ |
| pBuf->p[pBuf->n++] = 0; |
| iOff++; |
| if( iOff<nDoclist && pDoclist[iOff]==0 ){ |
| pBuf->p[pBuf->n++] = 0; |
| iOff++; |
| } |
| } |
| if( (pBuf->n + pPgidx->n)>=pgsz ){ |
| fts5WriteFlushLeaf(p, &writer); |
| } |
| }else{ |
| int bDummy; |
| int nPos; |
| int nCopy = fts5GetPoslistSize(&pDoclist[iOff], &nPos, &bDummy); |
| nCopy += nPos; |
| if( (pBuf->n + pPgidx->n + nCopy) <= pgsz ){ |
| /* The entire poslist will fit on the current leaf. So copy |
| ** it in one go. */ |
| fts5BufferSafeAppendBlob(pBuf, &pDoclist[iOff], nCopy); |
| }else{ |
| /* The entire poslist will not fit on this leaf. So it needs |
| ** to be broken into sections. The only qualification being |
| ** that each varint must be stored contiguously. */ |
| const u8 *pPoslist = &pDoclist[iOff]; |
| int iPos = 0; |
| while( p->rc==SQLITE_OK ){ |
| int nSpace = pgsz - pBuf->n - pPgidx->n; |
| int n = 0; |
| if( (nCopy - iPos)<=nSpace ){ |
| n = nCopy - iPos; |
| }else{ |
| n = fts5PoslistPrefix(&pPoslist[iPos], nSpace); |
| } |
| assert( n>0 ); |
| fts5BufferSafeAppendBlob(pBuf, &pPoslist[iPos], n); |
| iPos += n; |
| if( (pBuf->n + pPgidx->n)>=pgsz ){ |
| fts5WriteFlushLeaf(p, &writer); |
| } |
| if( iPos>=nCopy ) break; |
| } |
| } |
| iOff += nCopy; |
| } |
| } |
| } |
| |
| /* TODO2: Doclist terminator written here. */ |
| /* pBuf->p[pBuf->n++] = '\0'; */ |
| assert( pBuf->n<=pBuf->nSpace ); |
| sqlite3Fts5HashScanNext(pHash); |
| } |
| sqlite3Fts5HashClear(pHash); |
| fts5WriteFinish(p, &writer, &pgnoLast); |
| |
| /* Update the Fts5Structure. It is written back to the database by the |
| ** fts5StructureRelease() call below. */ |
| if( pStruct->nLevel==0 ){ |
| fts5StructureAddLevel(&p->rc, &pStruct); |
| } |
| fts5StructureExtendLevel(&p->rc, pStruct, 0, 1, 0); |
| if( p->rc==SQLITE_OK ){ |
| pSeg = &pStruct->aLevel[0].aSeg[ pStruct->aLevel[0].nSeg++ ]; |
| pSeg->iSegid = iSegid; |
| pSeg->pgnoFirst = 1; |
| pSeg->pgnoLast = pgnoLast; |
| pStruct->nSegment++; |
| } |
| fts5StructurePromote(p, 0, pStruct); |
| } |
| |
| fts5IndexAutomerge(p, &pStruct, pgnoLast); |
| fts5IndexCrisismerge(p, &pStruct); |
| fts5StructureWrite(p, pStruct); |
| fts5StructureRelease(pStruct); |
| } |
| |
| /* |
| ** Flush any data stored in the in-memory hash tables to the database. |
| */ |
| static void fts5IndexFlush(Fts5Index *p){ |
| /* Unless it is empty, flush the hash table to disk */ |
| if( p->nPendingData ){ |
| assert( p->pHash ); |
| p->nPendingData = 0; |
| fts5FlushOneHash(p); |
| } |
| } |
| |
| static Fts5Structure *fts5IndexOptimizeStruct( |
| Fts5Index *p, |
| Fts5Structure *pStruct |
| ){ |
| Fts5Structure *pNew = 0; |
| int nByte = sizeof(Fts5Structure); |
| int nSeg = pStruct->nSegment; |
| int i; |
| |
| /* Figure out if this structure requires optimization. A structure does |
| ** not require optimization if either: |
| ** |
| ** + it consists of fewer than two segments, or |
| ** + all segments are on the same level, or |
| ** + all segments except one are currently inputs to a merge operation. |
| ** |
| ** In the first case, return NULL. In the second, increment the ref-count |
| ** on *pStruct and return a copy of the pointer to it. |
| */ |
| if( nSeg<2 ) return 0; |
| for(i=0; i<pStruct->nLevel; i++){ |
| int nThis = pStruct->aLevel[i].nSeg; |
| if( nThis==nSeg || (nThis==nSeg-1 && pStruct->aLevel[i].nMerge==nThis) ){ |
| fts5StructureRef(pStruct); |
| return pStruct; |
| } |
| assert( pStruct->aLevel[i].nMerge<=nThis ); |
| } |
| |
| nByte += (pStruct->nLevel+1) * sizeof(Fts5StructureLevel); |
| pNew = (Fts5Structure*)sqlite3Fts5MallocZero(&p->rc, nByte); |
| |
| if( pNew ){ |
| Fts5StructureLevel *pLvl; |
| nByte = nSeg * sizeof(Fts5StructureSegment); |
| pNew->nLevel = pStruct->nLevel+1; |
| pNew->nRef = 1; |
| pNew->nWriteCounter = pStruct->nWriteCounter; |
| pLvl = &pNew->aLevel[pStruct->nLevel]; |
| pLvl->aSeg = (Fts5StructureSegment*)sqlite3Fts5MallocZero(&p->rc, nByte); |
| if( pLvl->aSeg ){ |
| int iLvl, iSeg; |
| int iSegOut = 0; |
| /* Iterate through all segments, from oldest to newest. Add them to |
| ** the new Fts5Level object so that pLvl->aSeg[0] is the oldest |
| ** segment in the data structure. */ |
| for(iLvl=pStruct->nLevel-1; iLvl>=0; iLvl--){ |
| for(iSeg=0; iSeg<pStruct->aLevel[iLvl].nSeg; iSeg++){ |
| pLvl->aSeg[iSegOut] = pStruct->aLevel[iLvl].aSeg[iSeg]; |
| iSegOut++; |
| } |
| } |
| pNew->nSegment = pLvl->nSeg = nSeg; |
| }else{ |
| sqlite3_free(pNew); |
| pNew = 0; |
| } |
| } |
| |
| return pNew; |
| } |
| |
| int sqlite3Fts5IndexOptimize(Fts5Index *p){ |
| Fts5Structure *pStruct; |
| Fts5Structure *pNew = 0; |
| |
| assert( p->rc==SQLITE_OK ); |
| fts5IndexFlush(p); |
| pStruct = fts5StructureRead(p); |
| fts5StructureInvalidate(p); |
| |
| if( pStruct ){ |
| pNew = fts5IndexOptimizeStruct(p, pStruct); |
| } |
| fts5StructureRelease(pStruct); |
| |
| assert( pNew==0 || pNew->nSegment>0 ); |
| if( pNew ){ |
| int iLvl; |
| for(iLvl=0; pNew->aLevel[iLvl].nSeg==0; iLvl++){} |
| while( p->rc==SQLITE_OK && pNew->aLevel[iLvl].nSeg>0 ){ |
| int nRem = FTS5_OPT_WORK_UNIT; |
| fts5IndexMergeLevel(p, &pNew, iLvl, &nRem); |
| } |
| |
| fts5StructureWrite(p, pNew); |
| fts5StructureRelease(pNew); |
| } |
| |
| return fts5IndexReturn(p); |
| } |
| |
| /* |
| ** This is called to implement the special "VALUES('merge', $nMerge)" |
| ** INSERT command. |
| */ |
| int sqlite3Fts5IndexMerge(Fts5Index *p, int nMerge){ |
| Fts5Structure *pStruct = fts5StructureRead(p); |
| if( pStruct ){ |
| int nMin = p->pConfig->nUsermerge; |
| fts5StructureInvalidate(p); |
| if( nMerge<0 ){ |
| Fts5Structure *pNew = fts5IndexOptimizeStruct(p, pStruct); |
| fts5StructureRelease(pStruct); |
| pStruct = pNew; |
| nMin = 2; |
| nMerge = nMerge*-1; |
| } |
| if( pStruct && pStruct->nLevel ){ |
| if( fts5IndexMerge(p, &pStruct, nMerge, nMin) ){ |
| fts5StructureWrite(p, pStruct); |
| } |
| } |
| fts5StructureRelease(pStruct); |
| } |
| return fts5IndexReturn(p); |
| } |
| |
| static void fts5AppendRowid( |
| Fts5Index *p, |
| i64 iDelta, |
| Fts5Iter *pUnused, |
| Fts5Buffer *pBuf |
| ){ |
| UNUSED_PARAM(pUnused); |
| fts5BufferAppendVarint(&p->rc, pBuf, iDelta); |
| } |
| |
| static void fts5AppendPoslist( |
| Fts5Index *p, |
| i64 iDelta, |
| Fts5Iter *pMulti, |
| Fts5Buffer *pBuf |
| ){ |
| int nData = pMulti->base.nData; |
| assert( nData>0 ); |
| if( p->rc==SQLITE_OK && 0==fts5BufferGrow(&p->rc, pBuf, nData+9+9) ){ |
| fts5BufferSafeAppendVarint(pBuf, iDelta); |
| fts5BufferSafeAppendVarint(pBuf, nData*2); |
| fts5BufferSafeAppendBlob(pBuf, pMulti->base.pData, nData); |
| } |
| } |
| |
| |
| static void fts5DoclistIterNext(Fts5DoclistIter *pIter){ |
| u8 *p = pIter->aPoslist + pIter->nSize + pIter->nPoslist; |
| |
| assert( pIter->aPoslist ); |
| if( p>=pIter->aEof ){ |
| pIter->aPoslist = 0; |
| }else{ |
| i64 iDelta; |
| |
| p += fts5GetVarint(p, (u64*)&iDelta); |
| pIter->iRowid += iDelta; |
| |
| /* Read position list size */ |
| if( p[0] & 0x80 ){ |
| int nPos; |
| pIter->nSize = fts5GetVarint32(p, nPos); |
| pIter->nPoslist = (nPos>>1); |
| }else{ |
| pIter->nPoslist = ((int)(p[0])) >> 1; |
| pIter->nSize = 1; |
| } |
| |
| pIter->aPoslist = p; |
| } |
| } |
| |
| static void fts5DoclistIterInit( |
| Fts5Buffer *pBuf, |
| Fts5DoclistIter *pIter |
| ){ |
| memset(pIter, 0, sizeof(*pIter)); |
| pIter->aPoslist = pBuf->p; |
| pIter->aEof = &pBuf->p[pBuf->n]; |
| fts5DoclistIterNext(pIter); |
| } |
| |
| #if 0 |
| /* |
| ** Append a doclist to buffer pBuf. |
| ** |
| ** This function assumes that space within the buffer has already been |
| ** allocated. |
| */ |
| static void fts5MergeAppendDocid( |
| Fts5Buffer *pBuf, /* Buffer to write to */ |
| i64 *piLastRowid, /* IN/OUT: Previous rowid written (if any) */ |
| i64 iRowid /* Rowid to append */ |
| ){ |
| assert( pBuf->n!=0 || (*piLastRowid)==0 ); |
| fts5BufferSafeAppendVarint(pBuf, iRowid - *piLastRowid); |
| *piLastRowid = iRowid; |
| } |
| #endif |
| |
| #define fts5MergeAppendDocid(pBuf, iLastRowid, iRowid) { \ |
| assert( (pBuf)->n!=0 || (iLastRowid)==0 ); \ |
| fts5BufferSafeAppendVarint((pBuf), (iRowid) - (iLastRowid)); \ |
| (iLastRowid) = (iRowid); \ |
| } |
| |
| /* |
| ** Swap the contents of buffer *p1 with that of *p2. |
| */ |
| static void fts5BufferSwap(Fts5Buffer *p1, Fts5Buffer *p2){ |
| Fts5Buffer tmp = *p1; |
| *p1 = *p2; |
| *p2 = tmp; |
| } |
| |
| static void fts5NextRowid(Fts5Buffer *pBuf, int *piOff, i64 *piRowid){ |
| int i = *piOff; |
| if( i>=pBuf->n ){ |
| *piOff = -1; |
| }else{ |
| u64 iVal; |
| *piOff = i + sqlite3Fts5GetVarint(&pBuf->p[i], &iVal); |
| *piRowid += iVal; |
| } |
| } |
| |
| /* |
| ** This is the equivalent of fts5MergePrefixLists() for detail=none mode. |
| ** In this case the buffers consist of a delta-encoded list of rowids only. |
| */ |
| static void fts5MergeRowidLists( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5Buffer *p1, /* First list to merge */ |
| Fts5Buffer *p2 /* Second list to merge */ |
| ){ |
| int i1 = 0; |
| int i2 = 0; |
| i64 iRowid1 = 0; |
| i64 iRowid2 = 0; |
| i64 iOut = 0; |
| |
| Fts5Buffer out; |
| memset(&out, 0, sizeof(out)); |
| sqlite3Fts5BufferSize(&p->rc, &out, p1->n + p2->n); |
| if( p->rc ) return; |
| |
| fts5NextRowid(p1, &i1, &iRowid1); |
| fts5NextRowid(p2, &i2, &iRowid2); |
| while( i1>=0 || i2>=0 ){ |
| if( i1>=0 && (i2<0 || iRowid1<iRowid2) ){ |
| assert( iOut==0 || iRowid1>iOut ); |
| fts5BufferSafeAppendVarint(&out, iRowid1 - iOut); |
| iOut = iRowid1; |
| fts5NextRowid(p1, &i1, &iRowid1); |
| }else{ |
| assert( iOut==0 || iRowid2>iOut ); |
| fts5BufferSafeAppendVarint(&out, iRowid2 - iOut); |
| iOut = iRowid2; |
| if( i1>=0 && iRowid1==iRowid2 ){ |
| fts5NextRowid(p1, &i1, &iRowid1); |
| } |
| fts5NextRowid(p2, &i2, &iRowid2); |
| } |
| } |
| |
| fts5BufferSwap(&out, p1); |
| fts5BufferFree(&out); |
| } |
| |
| /* |
| ** Buffers p1 and p2 contain doclists. This function merges the content |
| ** of the two doclists together and sets buffer p1 to the result before |
| ** returning. |
| ** |
| ** If an error occurs, an error code is left in p->rc. If an error has |
| ** already occurred, this function is a no-op. |
| */ |
| static void fts5MergePrefixLists( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5Buffer *p1, /* First list to merge */ |
| Fts5Buffer *p2 /* Second list to merge */ |
| ){ |
| if( p2->n ){ |
| i64 iLastRowid = 0; |
| Fts5DoclistIter i1; |
| Fts5DoclistIter i2; |
| Fts5Buffer out = {0, 0, 0}; |
| Fts5Buffer tmp = {0, 0, 0}; |
| |
| /* The maximum size of the output is equal to the sum of the two |
| ** input sizes + 1 varint (9 bytes). The extra varint is because if the |
| ** first rowid in one input is a large negative number, and the first in |
| ** the other a non-negative number, the delta for the non-negative |
| ** number will be larger on disk than the literal integer value |
| ** was. */ |
| if( sqlite3Fts5BufferSize(&p->rc, &out, p1->n + p2->n + 9) ) return; |
| fts5DoclistIterInit(p1, &i1); |
| fts5DoclistIterInit(p2, &i2); |
| |
| while( 1 ){ |
| if( i1.iRowid<i2.iRowid ){ |
| /* Copy entry from i1 */ |
| fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid); |
| fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.nPoslist+i1.nSize); |
| fts5DoclistIterNext(&i1); |
| if( i1.aPoslist==0 ) break; |
| } |
| else if( i2.iRowid!=i1.iRowid ){ |
| /* Copy entry from i2 */ |
| fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid); |
| fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.nPoslist+i2.nSize); |
| fts5DoclistIterNext(&i2); |
| if( i2.aPoslist==0 ) break; |
| } |
| else{ |
| /* Merge the two position lists. */ |
| i64 iPos1 = 0; |
| i64 iPos2 = 0; |
| int iOff1 = 0; |
| int iOff2 = 0; |
| u8 *a1 = &i1.aPoslist[i1.nSize]; |
| u8 *a2 = &i2.aPoslist[i2.nSize]; |
| |
| i64 iPrev = 0; |
| Fts5PoslistWriter writer; |
| memset(&writer, 0, sizeof(writer)); |
| |
| fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid); |
| fts5BufferZero(&tmp); |
| sqlite3Fts5BufferSize(&p->rc, &tmp, i1.nPoslist + i2.nPoslist); |
| if( p->rc ) break; |
| |
| sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1); |
| sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2); |
| assert( iPos1>=0 && iPos2>=0 ); |
| |
| if( iPos1<iPos2 ){ |
| sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos1); |
| sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1); |
| }else{ |
| sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos2); |
| sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2); |
| } |
| |
| if( iPos1>=0 && iPos2>=0 ){ |
| while( 1 ){ |
| if( iPos1<iPos2 ){ |
| if( iPos1!=iPrev ){ |
| sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos1); |
| } |
| sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1); |
| if( iPos1<0 ) break; |
| }else{ |
| assert( iPos2!=iPrev ); |
| sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos2); |
| sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2); |
| if( iPos2<0 ) break; |
| } |
| } |
| } |
| |
| if( iPos1>=0 ){ |
| if( iPos1!=iPrev ){ |
| sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos1); |
| } |
| fts5BufferSafeAppendBlob(&tmp, &a1[iOff1], i1.nPoslist-iOff1); |
| }else{ |
| assert( iPos2>=0 && iPos2!=iPrev ); |
| sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos2); |
| fts5BufferSafeAppendBlob(&tmp, &a2[iOff2], i2.nPoslist-iOff2); |
| } |
| |
| /* WRITEPOSLISTSIZE */ |
| fts5BufferSafeAppendVarint(&out, tmp.n * 2); |
| fts5BufferSafeAppendBlob(&out, tmp.p, tmp.n); |
| fts5DoclistIterNext(&i1); |
| fts5DoclistIterNext(&i2); |
| if( i1.aPoslist==0 || i2.aPoslist==0 ) break; |
| } |
| } |
| |
| if( i1.aPoslist ){ |
| fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid); |
| fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.aEof - i1.aPoslist); |
| } |
| else if( i2.aPoslist ){ |
| fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid); |
| fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.aEof - i2.aPoslist); |
| } |
| assert( out.n<=(p1->n+p2->n+9) ); |
| |
| fts5BufferSet(&p->rc, p1, out.n, out.p); |
| fts5BufferFree(&tmp); |
| fts5BufferFree(&out); |
| } |
| } |
| |
| static void fts5SetupPrefixIter( |
| Fts5Index *p, /* Index to read from */ |
| int bDesc, /* True for "ORDER BY rowid DESC" */ |
| const u8 *pToken, /* Buffer containing prefix to match */ |
| int nToken, /* Size of buffer pToken in bytes */ |
| Fts5Colset *pColset, /* Restrict matches to these columns */ |
| Fts5Iter **ppIter /* OUT: New iterator */ |
| ){ |
| Fts5Structure *pStruct; |
| Fts5Buffer *aBuf; |
| const int nBuf = 32; |
| |
| void (*xMerge)(Fts5Index*, Fts5Buffer*, Fts5Buffer*); |
| void (*xAppend)(Fts5Index*, i64, Fts5Iter*, Fts5Buffer*); |
| if( p->pConfig->eDetail==FTS5_DETAIL_NONE ){ |
| xMerge = fts5MergeRowidLists; |
| xAppend = fts5AppendRowid; |
| }else{ |
| xMerge = fts5MergePrefixLists; |
| xAppend = fts5AppendPoslist; |
| } |
| |
| aBuf = (Fts5Buffer*)fts5IdxMalloc(p, sizeof(Fts5Buffer)*nBuf); |
| pStruct = fts5StructureRead(p); |
| |
| if( aBuf && pStruct ){ |
| const int flags = FTS5INDEX_QUERY_SCAN |
| | FTS5INDEX_QUERY_SKIPEMPTY |
| | FTS5INDEX_QUERY_NOOUTPUT; |
| int i; |
| i64 iLastRowid = 0; |
| Fts5Iter *p1 = 0; /* Iterator used to gather data from index */ |
| Fts5Data *pData; |
| Fts5Buffer doclist; |
| int bNewTerm = 1; |
| |
| memset(&doclist, 0, sizeof(doclist)); |
| fts5MultiIterNew(p, pStruct, flags, pColset, pToken, nToken, -1, 0, &p1); |
| fts5IterSetOutputCb(&p->rc, p1); |
| for( /* no-op */ ; |
| fts5MultiIterEof(p, p1)==0; |
| fts5MultiIterNext2(p, p1, &bNewTerm) |
| ){ |
| Fts5SegIter *pSeg = &p1->aSeg[ p1->aFirst[1].iFirst ]; |
| int nTerm = pSeg->term.n; |
| const u8 *pTerm = pSeg->term.p; |
| p1->xSetOutputs(p1, pSeg); |
| |
| assert_nc( memcmp(pToken, pTerm, MIN(nToken, nTerm))<=0 ); |
| if( bNewTerm ){ |
| if( nTerm<nToken || memcmp(pToken, pTerm, nToken) ) break; |
| } |
| |
| if( p1->base.nData==0 ) continue; |
| |
| if( p1->base.iRowid<=iLastRowid && doclist.n>0 ){ |
| for(i=0; p->rc==SQLITE_OK && doclist.n; i++){ |
| assert( i<nBuf ); |
| if( aBuf[i].n==0 ){ |
| fts5BufferSwap(&doclist, &aBuf[i]); |
| fts5BufferZero(&doclist); |
| }else{ |
| xMerge(p, &doclist, &aBuf[i]); |
| fts5BufferZero(&aBuf[i]); |
| } |
| } |
| iLastRowid = 0; |
| } |
| |
| xAppend(p, p1->base.iRowid-iLastRowid, p1, &doclist); |
| iLastRowid = p1->base.iRowid; |
| } |
| |
| for(i=0; i<nBuf; i++){ |
| if( p->rc==SQLITE_OK ){ |
| xMerge(p, &doclist, &aBuf[i]); |
| } |
| fts5BufferFree(&aBuf[i]); |
| } |
| fts5MultiIterFree(p1); |
| |
| pData = fts5IdxMalloc(p, sizeof(Fts5Data) + doclist.n); |
| if( pData ){ |
| pData->p = (u8*)&pData[1]; |
| pData->nn = pData->szLeaf = doclist.n; |
| if( doclist.n ) memcpy(pData->p, doclist.p, doclist.n); |
| fts5MultiIterNew2(p, pData, bDesc, ppIter); |
| } |
| fts5BufferFree(&doclist); |
| } |
| |
| fts5StructureRelease(pStruct); |
| sqlite3_free(aBuf); |
| } |
| |
| |
| /* |
| ** Indicate that all subsequent calls to sqlite3Fts5IndexWrite() pertain |
| ** to the document with rowid iRowid. |
| */ |
| int sqlite3Fts5IndexBeginWrite(Fts5Index *p, int bDelete, i64 iRowid){ |
| assert( p->rc==SQLITE_OK ); |
| |
| /* Allocate the hash table if it has not already been allocated */ |
| if( p->pHash==0 ){ |
| p->rc = sqlite3Fts5HashNew(p->pConfig, &p->pHash, &p->nPendingData); |
| } |
| |
| /* Flush the hash table to disk if required */ |
| if( iRowid<p->iWriteRowid |
| || (iRowid==p->iWriteRowid && p->bDelete==0) |
| || (p->nPendingData > p->pConfig->nHashSize) |
| ){ |
| fts5IndexFlush(p); |
| } |
| |
| p->iWriteRowid = iRowid; |
| p->bDelete = bDelete; |
| return fts5IndexReturn(p); |
| } |
| |
| /* |
| ** Commit data to disk. |
| */ |
| int sqlite3Fts5IndexSync(Fts5Index *p){ |
| assert( p->rc==SQLITE_OK ); |
| fts5IndexFlush(p); |
| fts5CloseReader(p); |
| return fts5IndexReturn(p); |
| } |
| |
| /* |
| ** Discard any data stored in the in-memory hash tables. Do not write it |
| ** to the database. Additionally, assume that the contents of the %_data |
| ** table may have changed on disk. So any in-memory caches of %_data |
| ** records must be invalidated. |
| */ |
| int sqlite3Fts5IndexRollback(Fts5Index *p){ |
| fts5CloseReader(p); |
| fts5IndexDiscardData(p); |
| fts5StructureInvalidate(p); |
| /* assert( p->rc==SQLITE_OK ); */ |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** The %_data table is completely empty when this function is called. This |
| ** function populates it with the initial structure objects for each index, |
| ** and the initial version of the "averages" record (a zero-byte blob). |
| */ |
| int sqlite3Fts5IndexReinit(Fts5Index *p){ |
| Fts5Structure s; |
| fts5StructureInvalidate(p); |
| memset(&s, 0, sizeof(Fts5Structure)); |
| fts5DataWrite(p, FTS5_AVERAGES_ROWID, (const u8*)"", 0); |
| fts5StructureWrite(p, &s); |
| return fts5IndexReturn(p); |
| } |
| |
| /* |
| ** Open a new Fts5Index handle. If the bCreate argument is true, create |
| ** and initialize the underlying %_data table. |
| ** |
| ** If successful, set *pp to point to the new object and return SQLITE_OK. |
| ** Otherwise, set *pp to NULL and return an SQLite error code. |
| */ |
| int sqlite3Fts5IndexOpen( |
| Fts5Config *pConfig, |
| int bCreate, |
| Fts5Index **pp, |
| char **pzErr |
| ){ |
| int rc = SQLITE_OK; |
| Fts5Index *p; /* New object */ |
| |
| *pp = p = (Fts5Index*)sqlite3Fts5MallocZero(&rc, sizeof(Fts5Index)); |
| if( rc==SQLITE_OK ){ |
| p->pConfig = pConfig; |
| p->nWorkUnit = FTS5_WORK_UNIT; |
| p->zDataTbl = sqlite3Fts5Mprintf(&rc, "%s_data", pConfig->zName); |
| if( p->zDataTbl && bCreate ){ |
| rc = sqlite3Fts5CreateTable( |
| pConfig, "data", "id INTEGER PRIMARY KEY, block BLOB", 0, pzErr |
| ); |
| if( rc==SQLITE_OK ){ |
| rc = sqlite3Fts5CreateTable(pConfig, "idx", |
| "segid, term, pgno, PRIMARY KEY(segid, term)", |
| 1, pzErr |
| ); |
| } |
| if( rc==SQLITE_OK ){ |
| rc = sqlite3Fts5IndexReinit(p); |
| } |
| } |
| } |
| |
| assert( rc!=SQLITE_OK || p->rc==SQLITE_OK ); |
| if( rc ){ |
| sqlite3Fts5IndexClose(p); |
| *pp = 0; |
| } |
| return rc; |
| } |
| |
| /* |
| ** Close a handle opened by an earlier call to sqlite3Fts5IndexOpen(). |
| */ |
| int sqlite3Fts5IndexClose(Fts5Index *p){ |
| int rc = SQLITE_OK; |
| if( p ){ |
| assert( p->pReader==0 ); |
| fts5StructureInvalidate(p); |
| sqlite3_finalize(p->pWriter); |
| sqlite3_finalize(p->pDeleter); |
| sqlite3_finalize(p->pIdxWriter); |
| sqlite3_finalize(p->pIdxDeleter); |
| sqlite3_finalize(p->pIdxSelect); |
| sqlite3_finalize(p->pDataVersion); |
| sqlite3Fts5HashFree(p->pHash); |
| sqlite3_free(p->zDataTbl); |
| sqlite3_free(p); |
| } |
| return rc; |
| } |
| |
| /* |
| ** Argument p points to a buffer containing utf-8 text that is n bytes in |
| ** size. Return the number of bytes in the nChar character prefix of the |
| ** buffer, or 0 if there are less than nChar characters in total. |
| */ |
| int sqlite3Fts5IndexCharlenToBytelen( |
| const char *p, |
| int nByte, |
| int nChar |
| ){ |
| int n = 0; |
| int i; |
| for(i=0; i<nChar; i++){ |
| if( n>=nByte ) return 0; /* Input contains fewer than nChar chars */ |
| if( (unsigned char)p[n++]>=0xc0 ){ |
| while( (p[n] & 0xc0)==0x80 ){ |
| n++; |
| if( n>=nByte ) break; |
| } |
| } |
| } |
| return n; |
| } |
| |
| /* |
| ** pIn is a UTF-8 encoded string, nIn bytes in size. Return the number of |
| ** unicode characters in the string. |
| */ |
| static int fts5IndexCharlen(const char *pIn, int nIn){ |
| int nChar = 0; |
| int i = 0; |
| while( i<nIn ){ |
| if( (unsigned char)pIn[i++]>=0xc0 ){ |
| while( i<nIn && (pIn[i] & 0xc0)==0x80 ) i++; |
| } |
| nChar++; |
| } |
| return nChar; |
| } |
| |
| /* |
| ** Insert or remove data to or from the index. Each time a document is |
| ** added to or removed from the index, this function is called one or more |
| ** times. |
| ** |
| ** For an insert, it must be called once for each token in the new document. |
| ** If the operation is a delete, it must be called (at least) once for each |
| ** unique token in the document with an iCol value less than zero. The iPos |
| ** argument is ignored for a delete. |
| */ |
| int sqlite3Fts5IndexWrite( |
| Fts5Index *p, /* Index to write to */ |
| int iCol, /* Column token appears in (-ve -> delete) */ |
| int iPos, /* Position of token within column */ |
| const char *pToken, int nToken /* Token to add or remove to or from index */ |
| ){ |
| int i; /* Used to iterate through indexes */ |
| int rc = SQLITE_OK; /* Return code */ |
| Fts5Config *pConfig = p->pConfig; |
| |
| assert( p->rc==SQLITE_OK ); |
| assert( (iCol<0)==p->bDelete ); |
| |
| /* Add the entry to the main terms index. */ |
| rc = sqlite3Fts5HashWrite( |
| p->pHash, p->iWriteRowid, iCol, iPos, FTS5_MAIN_PREFIX, pToken, nToken |
| ); |
| |
| for(i=0; i<pConfig->nPrefix && rc==SQLITE_OK; i++){ |
| const int nChar = pConfig->aPrefix[i]; |
| int nByte = sqlite3Fts5IndexCharlenToBytelen(pToken, nToken, nChar); |
| if( nByte ){ |
| rc = sqlite3Fts5HashWrite(p->pHash, |
| p->iWriteRowid, iCol, iPos, (char)(FTS5_MAIN_PREFIX+i+1), pToken, |
| nByte |
| ); |
| } |
| } |
| |
| return rc; |
| } |
| |
| /* |
| ** Open a new iterator to iterate though all rowid that match the |
| ** specified token or token prefix. |
| */ |
| int sqlite3Fts5IndexQuery( |
| Fts5Index *p, /* FTS index to query */ |
| const char *pToken, int nToken, /* Token (or prefix) to query for */ |
| int flags, /* Mask of FTS5INDEX_QUERY_X flags */ |
| Fts5Colset *pColset, /* Match these columns only */ |
| Fts5IndexIter **ppIter /* OUT: New iterator object */ |
| ){ |
| Fts5Config *pConfig = p->pConfig; |
| Fts5Iter *pRet = 0; |
| Fts5Buffer buf = {0, 0, 0}; |
| |
| /* If the QUERY_SCAN flag is set, all other flags must be clear. */ |
| assert( (flags & FTS5INDEX_QUERY_SCAN)==0 || flags==FTS5INDEX_QUERY_SCAN ); |
| |
| if( sqlite3Fts5BufferSize(&p->rc, &buf, nToken+1)==0 ){ |
| int iIdx = 0; /* Index to search */ |
| if( nToken ) memcpy(&buf.p[1], pToken, nToken); |
| |
| /* Figure out which index to search and set iIdx accordingly. If this |
| ** is a prefix query for which there is no prefix index, set iIdx to |
| ** greater than pConfig->nPrefix to indicate that the query will be |
| ** satisfied by scanning multiple terms in the main index. |
| ** |
| ** If the QUERY_TEST_NOIDX flag was specified, then this must be a |
| ** prefix-query. Instead of using a prefix-index (if one exists), |
| ** evaluate the prefix query using the main FTS index. This is used |
| ** for internal sanity checking by the integrity-check in debug |
| ** mode only. */ |
| #ifdef SQLITE_DEBUG |
| if( pConfig->bPrefixIndex==0 || (flags & FTS5INDEX_QUERY_TEST_NOIDX) ){ |
| assert( flags & FTS5INDEX_QUERY_PREFIX ); |
| iIdx = 1+pConfig->nPrefix; |
| }else |
| #endif |
| if( flags & FTS5INDEX_QUERY_PREFIX ){ |
| int nChar = fts5IndexCharlen(pToken, nToken); |
| for(iIdx=1; iIdx<=pConfig->nPrefix; iIdx++){ |
| if( pConfig->aPrefix[iIdx-1]==nChar ) break; |
| } |
| } |
| |
| if( iIdx<=pConfig->nPrefix ){ |
| /* Straight index lookup */ |
| Fts5Structure *pStruct = fts5StructureRead(p); |
| buf.p[0] = (u8)(FTS5_MAIN_PREFIX + iIdx); |
| if( pStruct ){ |
| fts5MultiIterNew(p, pStruct, flags | FTS5INDEX_QUERY_SKIPEMPTY, |
| pColset, buf.p, nToken+1, -1, 0, &pRet |
| ); |
| fts5StructureRelease(pStruct); |
| } |
| }else{ |
| /* Scan multiple terms in the main index */ |
| int bDesc = (flags & FTS5INDEX_QUERY_DESC)!=0; |
| buf.p[0] = FTS5_MAIN_PREFIX; |
| fts5SetupPrefixIter(p, bDesc, buf.p, nToken+1, pColset, &pRet); |
| assert( p->rc!=SQLITE_OK || pRet->pColset==0 ); |
| fts5IterSetOutputCb(&p->rc, pRet); |
| if( p->rc==SQLITE_OK ){ |
| Fts5SegIter *pSeg = &pRet->aSeg[pRet->aFirst[1].iFirst]; |
| if( pSeg->pLeaf ) pRet->xSetOutputs(pRet, pSeg); |
| } |
| } |
| |
| if( p->rc ){ |
| sqlite3Fts5IterClose((Fts5IndexIter*)pRet); |
| pRet = 0; |
| fts5CloseReader(p); |
| } |
| |
| *ppIter = &pRet->base; |
| sqlite3Fts5BufferFree(&buf); |
| } |
| return fts5IndexReturn(p); |
| } |
| |
| /* |
| ** Return true if the iterator passed as the only argument is at EOF. |
| */ |
| /* |
| ** Move to the next matching rowid. |
| */ |
| int sqlite3Fts5IterNext(Fts5IndexIter *pIndexIter){ |
| Fts5Iter *pIter = (Fts5Iter*)pIndexIter; |
| assert( pIter->pIndex->rc==SQLITE_OK ); |
| fts5MultiIterNext(pIter->pIndex, pIter, 0, 0); |
| return fts5IndexReturn(pIter->pIndex); |
| } |
| |
| /* |
| ** Move to the next matching term/rowid. Used by the fts5vocab module. |
| */ |
| int sqlite3Fts5IterNextScan(Fts5IndexIter *pIndexIter){ |
| Fts5Iter *pIter = (Fts5Iter*)pIndexIter; |
| Fts5Index *p = pIter->pIndex; |
| |
| assert( pIter->pIndex->rc==SQLITE_OK ); |
| |
| fts5MultiIterNext(p, pIter, 0, 0); |
| if( p->rc==SQLITE_OK ){ |
| Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; |
| if( pSeg->pLeaf && pSeg->term.p[0]!=FTS5_MAIN_PREFIX ){ |
| fts5DataRelease(pSeg->pLeaf); |
| pSeg->pLeaf = 0; |
| pIter->base.bEof = 1; |
| } |
| } |
| |
| return fts5IndexReturn(pIter->pIndex); |
| } |
| |
| /* |
| ** Move to the next matching rowid that occurs at or after iMatch. The |
| ** definition of "at or after" depends on whether this iterator iterates |
| ** in ascending or descending rowid order. |
| */ |
| int sqlite3Fts5IterNextFrom(Fts5IndexIter *pIndexIter, i64 iMatch){ |
| Fts5Iter *pIter = (Fts5Iter*)pIndexIter; |
| fts5MultiIterNextFrom(pIter->pIndex, pIter, iMatch); |
| return fts5IndexReturn(pIter->pIndex); |
| } |
| |
| /* |
| ** Return the current term. |
| */ |
| const char *sqlite3Fts5IterTerm(Fts5IndexIter *pIndexIter, int *pn){ |
| int n; |
| const char *z = (const char*)fts5MultiIterTerm((Fts5Iter*)pIndexIter, &n); |
| *pn = n-1; |
| return &z[1]; |
| } |
| |
| /* |
| ** Close an iterator opened by an earlier call to sqlite3Fts5IndexQuery(). |
| */ |
| void sqlite3Fts5IterClose(Fts5IndexIter *pIndexIter){ |
| if( pIndexIter ){ |
| Fts5Iter *pIter = (Fts5Iter*)pIndexIter; |
| Fts5Index *pIndex = pIter->pIndex; |
| fts5MultiIterFree(pIter); |
| fts5CloseReader(pIndex); |
| } |
| } |
| |
| /* |
| ** Read and decode the "averages" record from the database. |
| ** |
| ** Parameter anSize must point to an array of size nCol, where nCol is |
| ** the number of user defined columns in the FTS table. |
| */ |
| int sqlite3Fts5IndexGetAverages(Fts5Index *p, i64 *pnRow, i64 *anSize){ |
| int nCol = p->pConfig->nCol; |
| Fts5Data *pData; |
| |
| *pnRow = 0; |
| memset(anSize, 0, sizeof(i64) * nCol); |
| pData = fts5DataRead(p, FTS5_AVERAGES_ROWID); |
| if( p->rc==SQLITE_OK && pData->nn ){ |
| int i = 0; |
| int iCol; |
| i += fts5GetVarint(&pData->p[i], (u64*)pnRow); |
| for(iCol=0; i<pData->nn && iCol<nCol; iCol++){ |
| i += fts5GetVarint(&pData->p[i], (u64*)&anSize[iCol]); |
| } |
| } |
| |
| fts5DataRelease(pData); |
| return fts5IndexReturn(p); |
| } |
| |
| /* |
| ** Replace the current "averages" record with the contents of the buffer |
| ** supplied as the second argument. |
| */ |
| int sqlite3Fts5IndexSetAverages(Fts5Index *p, const u8 *pData, int nData){ |
| assert( p->rc==SQLITE_OK ); |
| fts5DataWrite(p, FTS5_AVERAGES_ROWID, pData, nData); |
| return fts5IndexReturn(p); |
| } |
| |
| /* |
| ** Return the total number of blocks this module has read from the %_data |
| ** table since it was created. |
| */ |
| int sqlite3Fts5IndexReads(Fts5Index *p){ |
| return p->nRead; |
| } |
| |
| /* |
| ** Set the 32-bit cookie value stored at the start of all structure |
| ** records to the value passed as the second argument. |
| ** |
| ** Return SQLITE_OK if successful, or an SQLite error code if an error |
| ** occurs. |
| */ |
| int sqlite3Fts5IndexSetCookie(Fts5Index *p, int iNew){ |
| int rc; /* Return code */ |
| Fts5Config *pConfig = p->pConfig; /* Configuration object */ |
| u8 aCookie[4]; /* Binary representation of iNew */ |
| sqlite3_blob *pBlob = 0; |
| |
| assert( p->rc==SQLITE_OK ); |
| sqlite3Fts5Put32(aCookie, iNew); |
| |
| rc = sqlite3_blob_open(pConfig->db, pConfig->zDb, p->zDataTbl, |
| "block", FTS5_STRUCTURE_ROWID, 1, &pBlob |
| ); |
| if( rc==SQLITE_OK ){ |
| sqlite3_blob_write(pBlob, aCookie, 4, 0); |
| rc = sqlite3_blob_close(pBlob); |
| } |
| |
| return rc; |
| } |
| |
| int sqlite3Fts5IndexLoadConfig(Fts5Index *p){ |
| Fts5Structure *pStruct; |
| pStruct = fts5StructureRead(p); |
| fts5StructureRelease(pStruct); |
| return fts5IndexReturn(p); |
| } |
| |
| |
| /************************************************************************* |
| ************************************************************************** |
| ** Below this point is the implementation of the integrity-check |
| ** functionality. |
| */ |
| |
| /* |
| ** Return a simple checksum value based on the arguments. |
| */ |
| u64 sqlite3Fts5IndexEntryCksum( |
| i64 iRowid, |
| int iCol, |
| int iPos, |
| int iIdx, |
| const char *pTerm, |
| int nTerm |
| ){ |
| int i; |
| u64 ret = iRowid; |
| ret += (ret<<3) + iCol; |
| ret += (ret<<3) + iPos; |
| if( iIdx>=0 ) ret += (ret<<3) + (FTS5_MAIN_PREFIX + iIdx); |
| for(i=0; i<nTerm; i++) ret += (ret<<3) + pTerm[i]; |
| return ret; |
| } |
| |
| #ifdef SQLITE_DEBUG |
| /* |
| ** This function is purely an internal test. It does not contribute to |
| ** FTS functionality, or even the integrity-check, in any way. |
| ** |
| ** Instead, it tests that the same set of pgno/rowid combinations are |
| ** visited regardless of whether the doclist-index identified by parameters |
| ** iSegid/iLeaf is iterated in forwards or reverse order. |
| */ |
| static void fts5TestDlidxReverse( |
| Fts5Index *p, |
| int iSegid, /* Segment id to load from */ |
| int iLeaf /* Load doclist-index for this leaf */ |
| ){ |
| Fts5DlidxIter *pDlidx = 0; |
| u64 cksum1 = 13; |
| u64 cksum2 = 13; |
| |
| for(pDlidx=fts5DlidxIterInit(p, 0, iSegid, iLeaf); |
| fts5DlidxIterEof(p, pDlidx)==0; |
| fts5DlidxIterNext(p, pDlidx) |
| ){ |
| i64 iRowid = fts5DlidxIterRowid(pDlidx); |
| int pgno = fts5DlidxIterPgno(pDlidx); |
| assert( pgno>iLeaf ); |
| cksum1 += iRowid + ((i64)pgno<<32); |
| } |
| fts5DlidxIterFree(pDlidx); |
| pDlidx = 0; |
| |
| for(pDlidx=fts5DlidxIterInit(p, 1, iSegid, iLeaf); |
| fts5DlidxIterEof(p, pDlidx)==0; |
| fts5DlidxIterPrev(p, pDlidx) |
| ){ |
| i64 iRowid = fts5DlidxIterRowid(pDlidx); |
| int pgno = fts5DlidxIterPgno(pDlidx); |
| assert( fts5DlidxIterPgno(pDlidx)>iLeaf ); |
| cksum2 += iRowid + ((i64)pgno<<32); |
| } |
| fts5DlidxIterFree(pDlidx); |
| pDlidx = 0; |
| |
| if( p->rc==SQLITE_OK && cksum1!=cksum2 ) p->rc = FTS5_CORRUPT; |
| } |
| |
| static int fts5QueryCksum( |
| Fts5Index *p, /* Fts5 index object */ |
| int iIdx, |
| const char *z, /* Index key to query for */ |
| int n, /* Size of index key in bytes */ |
| int flags, /* Flags for Fts5IndexQuery */ |
| u64 *pCksum /* IN/OUT: Checksum value */ |
| ){ |
| int eDetail = p->pConfig->eDetail; |
| u64 cksum = *pCksum; |
| Fts5IndexIter *pIter = 0; |
| int rc = sqlite3Fts5IndexQuery(p, z, n, flags, 0, &pIter); |
| |
| while( rc==SQLITE_OK && 0==sqlite3Fts5IterEof(pIter) ){ |
| i64 rowid = pIter->iRowid; |
| |
| if( eDetail==FTS5_DETAIL_NONE ){ |
| cksum ^= sqlite3Fts5IndexEntryCksum(rowid, 0, 0, iIdx, z, n); |
| }else{ |
| Fts5PoslistReader sReader; |
| for(sqlite3Fts5PoslistReaderInit(pIter->pData, pIter->nData, &sReader); |
| sReader.bEof==0; |
| sqlite3Fts5PoslistReaderNext(&sReader) |
| ){ |
| int iCol = FTS5_POS2COLUMN(sReader.iPos); |
| int iOff = FTS5_POS2OFFSET(sReader.iPos); |
| cksum ^= sqlite3Fts5IndexEntryCksum(rowid, iCol, iOff, iIdx, z, n); |
| } |
| } |
| if( rc==SQLITE_OK ){ |
| rc = sqlite3Fts5IterNext(pIter); |
| } |
| } |
| sqlite3Fts5IterClose(pIter); |
| |
| *pCksum = cksum; |
| return rc; |
| } |
| |
| |
| /* |
| ** This function is also purely an internal test. It does not contribute to |
| ** FTS functionality, or even the integrity-check, in any way. |
| */ |
| static void fts5TestTerm( |
| Fts5Index *p, |
| Fts5Buffer *pPrev, /* Previous term */ |
| const char *z, int n, /* Possibly new term to test */ |
| u64 expected, |
| u64 *pCksum |
| ){ |
| int rc = p->rc; |
| if( pPrev->n==0 ){ |
| fts5BufferSet(&rc, pPrev, n, (const u8*)z); |
| }else |
| if( rc==SQLITE_OK && (pPrev->n!=n || memcmp(pPrev->p, z, n)) ){ |
| u64 cksum3 = *pCksum; |
| const char *zTerm = (const char*)&pPrev->p[1]; /* term sans prefix-byte */ |
| int nTerm = pPrev->n-1; /* Size of zTerm in bytes */ |
| int iIdx = (pPrev->p[0] - FTS5_MAIN_PREFIX); |
| int flags = (iIdx==0 ? 0 : FTS5INDEX_QUERY_PREFIX); |
| u64 ck1 = 0; |
| u64 ck2 = 0; |
| |
| /* Check that the results returned for ASC and DESC queries are |
| ** the same. If not, call this corruption. */ |
| rc = fts5QueryCksum(p, iIdx, zTerm, nTerm, flags, &ck1); |
| if( rc==SQLITE_OK ){ |
| int f = flags|FTS5INDEX_QUERY_DESC; |
| rc = fts5QueryCksum(p, iIdx, zTerm, nTerm, f, &ck2); |
| } |
| if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT; |
| |
| /* If this is a prefix query, check that the results returned if the |
| ** the index is disabled are the same. In both ASC and DESC order. |
| ** |
| ** This check may only be performed if the hash table is empty. This |
| ** is because the hash table only supports a single scan query at |
| ** a time, and the multi-iter loop from which this function is called |
| ** is already performing such a scan. */ |
| if( p->nPendingData==0 ){ |
| if( iIdx>0 && rc==SQLITE_OK ){ |
| int f = flags|FTS5INDEX_QUERY_TEST_NOIDX; |
| ck2 = 0; |
| rc = fts5QueryCksum(p, iIdx, zTerm, nTerm, f, &ck2); |
| if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT; |
| } |
| if( iIdx>0 && rc==SQLITE_OK ){ |
| int f = flags|FTS5INDEX_QUERY_TEST_NOIDX|FTS5INDEX_QUERY_DESC; |
| ck2 = 0; |
| rc = fts5QueryCksum(p, iIdx, zTerm, nTerm, f, &ck2); |
| if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT; |
| } |
| } |
| |
| cksum3 ^= ck1; |
| fts5BufferSet(&rc, pPrev, n, (const u8*)z); |
| |
| if( rc==SQLITE_OK && cksum3!=expected ){ |
| rc = FTS5_CORRUPT; |
| } |
| *pCksum = cksum3; |
| } |
| p->rc = rc; |
| } |
| |
| #else |
| # define fts5TestDlidxReverse(x,y,z) |
| # define fts5TestTerm(u,v,w,x,y,z) |
| #endif |
| |
| /* |
| ** Check that: |
| ** |
| ** 1) All leaves of pSeg between iFirst and iLast (inclusive) exist and |
| ** contain zero terms. |
| ** 2) All leaves of pSeg between iNoRowid and iLast (inclusive) exist and |
| ** contain zero rowids. |
| */ |
| static void fts5IndexIntegrityCheckEmpty( |
| Fts5Index *p, |
| Fts5StructureSegment *pSeg, /* Segment to check internal consistency */ |
| int iFirst, |
| int iNoRowid, |
| int iLast |
| ){ |
| int i; |
| |
| /* Now check that the iter.nEmpty leaves following the current leaf |
| ** (a) exist and (b) contain no terms. */ |
| for(i=iFirst; p->rc==SQLITE_OK && i<=iLast; i++){ |
| Fts5Data *pLeaf = fts5DataRead(p, FTS5_SEGMENT_ROWID(pSeg->iSegid, i)); |
| if( pLeaf ){ |
| if( !fts5LeafIsTermless(pLeaf) ) p->rc = FTS5_CORRUPT; |
| if( i>=iNoRowid && 0!=fts5LeafFirstRowidOff(pLeaf) ) p->rc = FTS5_CORRUPT; |
| } |
| fts5DataRelease(pLeaf); |
| } |
| } |
| |
| static void fts5IntegrityCheckPgidx(Fts5Index *p, Fts5Data *pLeaf){ |
| int iTermOff = 0; |
| int ii; |
| |
| Fts5Buffer buf1 = {0,0,0}; |
| Fts5Buffer buf2 = {0,0,0}; |
| |
| ii = pLeaf->szLeaf; |
| while( ii<pLeaf->nn && p->rc==SQLITE_OK ){ |
| int res; |
| int iOff; |
| int nIncr; |
| |
| ii += fts5GetVarint32(&pLeaf->p[ii], nIncr); |
| iTermOff += nIncr; |
| iOff = iTermOff; |
| |
| if( iOff>=pLeaf->szLeaf ){ |
| p->rc = FTS5_CORRUPT; |
| }else if( iTermOff==nIncr ){ |
| int nByte; |
| iOff += fts5GetVarint32(&pLeaf->p[iOff], nByte); |
| if( (iOff+nByte)>pLeaf->szLeaf ){ |
| p->rc = FTS5_CORRUPT; |
| }else{ |
| fts5BufferSet(&p->rc, &buf1, nByte, &pLeaf->p[iOff]); |
| } |
| }else{ |
| int nKeep, nByte; |
| iOff += fts5GetVarint32(&pLeaf->p[iOff], nKeep); |
| iOff += fts5GetVarint32(&pLeaf->p[iOff], nByte); |
| if( nKeep>buf1.n || (iOff+nByte)>pLeaf->szLeaf ){ |
| p->rc = FTS5_CORRUPT; |
| }else{ |
| buf1.n = nKeep; |
| fts5BufferAppendBlob(&p->rc, &buf1, nByte, &pLeaf->p[iOff]); |
| } |
| |
| if( p->rc==SQLITE_OK ){ |
| res = fts5BufferCompare(&buf1, &buf2); |
| if( res<=0 ) p->rc = FTS5_CORRUPT; |
| } |
| } |
| fts5BufferSet(&p->rc, &buf2, buf1.n, buf1.p); |
| } |
| |
| fts5BufferFree(&buf1); |
| fts5BufferFree(&buf2); |
| } |
| |
| static void fts5IndexIntegrityCheckSegment( |
| Fts5Index *p, /* FTS5 backend object */ |
| Fts5StructureSegment *pSeg /* Segment to check internal consistency */ |
| ){ |
| Fts5Config *pConfig = p->pConfig; |
| sqlite3_stmt *pStmt = 0; |
| int rc2; |
| int iIdxPrevLeaf = pSeg->pgnoFirst-1; |
| int iDlidxPrevLeaf = pSeg->pgnoLast; |
| |
| if( pSeg->pgnoFirst==0 ) return; |
| |
| fts5IndexPrepareStmt(p, &pStmt, sqlite3_mprintf( |
| "SELECT segid, term, (pgno>>1), (pgno&1) FROM %Q.'%q_idx' WHERE segid=%d", |
| pConfig->zDb, pConfig->zName, pSeg->iSegid |
| )); |
| |
| /* Iterate through the b-tree hierarchy. */ |
| while( p->rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){ |
| i64 iRow; /* Rowid for this leaf */ |
| Fts5Data *pLeaf; /* Data for this leaf */ |
| |
| int nIdxTerm = sqlite3_column_bytes(pStmt, 1); |
| const char *zIdxTerm = (const char*)sqlite3_column_text(pStmt, 1); |
| int iIdxLeaf = sqlite3_column_int(pStmt, 2); |
| int bIdxDlidx = sqlite3_column_int(pStmt, 3); |
| |
| /* If the leaf in question has already been trimmed from the segment, |
| ** ignore this b-tree entry. Otherwise, load it into memory. */ |
| if( iIdxLeaf<pSeg->pgnoFirst ) continue; |
| iRow = FTS5_SEGMENT_ROWID(pSeg->iSegid, iIdxLeaf); |
| pLeaf = fts5LeafRead(p, iRow); |
| if( pLeaf==0 ) break; |
| |
| /* Check that the leaf contains at least one term, and that it is equal |
| ** to or larger than the split-key in zIdxTerm. Also check that if there |
| ** is also a rowid pointer within the leaf page header, it points to a |
| ** location before the term. */ |
| if( pLeaf->nn<=pLeaf->szLeaf ){ |
| p->rc = FTS5_CORRUPT; |
| }else{ |
| int iOff; /* Offset of first term on leaf */ |
| int iRowidOff; /* Offset of first rowid on leaf */ |
| int nTerm; /* Size of term on leaf in bytes */ |
| int res; /* Comparison of term and split-key */ |
| |
| iOff = fts5LeafFirstTermOff(pLeaf); |
| iRowidOff = fts5LeafFirstRowidOff(pLeaf); |
| if( iRowidOff>=iOff ){ |
| p->rc = FTS5_CORRUPT; |
| }else{ |
| iOff += fts5GetVarint32(&pLeaf->p[iOff], nTerm); |
| res = memcmp(&pLeaf->p[iOff], zIdxTerm, MIN(nTerm, nIdxTerm)); |
| if( res==0 ) res = nTerm - nIdxTerm; |
| if( res<0 ) p->rc = FTS5_CORRUPT; |
| } |
| |
| fts5IntegrityCheckPgidx(p, pLeaf); |
| } |
| fts5DataRelease(pLeaf); |
| if( p->rc ) break; |
| |
| /* Now check that the iter.nEmpty leaves following the current leaf |
| ** (a) exist and (b) contain no terms. */ |
| fts5IndexIntegrityCheckEmpty( |
| p, pSeg, iIdxPrevLeaf+1, iDlidxPrevLeaf+1, iIdxLeaf-1 |
| ); |
| if( p->rc ) break; |
| |
| /* If there is a doclist-index, check that it looks right. */ |
| if( bIdxDlidx ){ |
| Fts5DlidxIter *pDlidx = 0; /* For iterating through doclist index */ |
| int iPrevLeaf = iIdxLeaf; |
| int iSegid = pSeg->iSegid; |
| int iPg = 0; |
| i64 iKey; |
| |
| for(pDlidx=fts5DlidxIterInit(p, 0, iSegid, iIdxLeaf); |
| fts5DlidxIterEof(p, pDlidx)==0; |
| fts5DlidxIterNext(p, pDlidx) |
| ){ |
| |
| /* Check any rowid-less pages that occur before the current leaf. */ |
| for(iPg=iPrevLeaf+1; iPg<fts5DlidxIterPgno(pDlidx); iPg++){ |
| iKey = FTS5_SEGMENT_ROWID(iSegid, iPg); |
| pLeaf = fts5DataRead(p, iKey); |
| if( pLeaf ){ |
| if( fts5LeafFirstRowidOff(pLeaf)!=0 ) p->rc = FTS5_CORRUPT; |
| fts5DataRelease(pLeaf); |
| } |
| } |
| iPrevLeaf = fts5DlidxIterPgno(pDlidx); |
| |
| /* Check that the leaf page indicated by the iterator really does |
| ** contain the rowid suggested by the same. */ |
| iKey = FTS5_SEGMENT_ROWID(iSegid, iPrevLeaf); |
| pLeaf = fts5DataRead(p, iKey); |
| if( pLeaf ){ |
| i64 iRowid; |
| int iRowidOff = fts5LeafFirstRowidOff(pLeaf); |
| ASSERT_SZLEAF_OK(pLeaf); |
| if( iRowidOff>=pLeaf->szLeaf ){ |
| p->rc = FTS5_CORRUPT; |
| }else{ |
| fts5GetVarint(&pLeaf->p[iRowidOff], (u64*)&iRowid); |
| if( iRowid!=fts5DlidxIterRowid(pDlidx) ) p->rc = FTS5_CORRUPT; |
| } |
| fts5DataRelease(pLeaf); |
| } |
| } |
| |
| iDlidxPrevLeaf = iPg; |
| fts5DlidxIterFree(pDlidx); |
| fts5TestDlidxReverse(p, iSegid, iIdxLeaf); |
| }else{ |
| iDlidxPrevLeaf = pSeg->pgnoLast; |
| /* TODO: Check there is no doclist index */ |
| } |
| |
| iIdxPrevLeaf = iIdxLeaf; |
| } |
| |
| rc2 = sqlite3_finalize(pStmt); |
| if( p->rc==SQLITE_OK ) p->rc = rc2; |
| |
| /* Page iter.iLeaf must now be the rightmost leaf-page in the segment */ |
| #if 0 |
| if( p->rc==SQLITE_OK && iter.iLeaf!=pSeg->pgnoLast ){ |
| p->rc = FTS5_CORRUPT; |
| } |
| #endif |
| } |
| |
| |
| /* |
| ** Run internal checks to ensure that the FTS index (a) is internally |
| ** consistent and (b) contains entries for which the XOR of the checksums |
| ** as calculated by sqlite3Fts5IndexEntryCksum() is cksum. |
| ** |
| ** Return SQLITE_CORRUPT if any of the internal checks fail, or if the |
| ** checksum does not match. Return SQLITE_OK if all checks pass without |
| ** error, or some other SQLite error code if another error (e.g. OOM) |
| ** occurs. |
| */ |
| int sqlite3Fts5IndexIntegrityCheck(Fts5Index *p, u64 cksum){ |
| int eDetail = p->pConfig->eDetail; |
| u64 cksum2 = 0; /* Checksum based on contents of indexes */ |
| Fts5Buffer poslist = {0,0,0}; /* Buffer used to hold a poslist */ |
| Fts5Iter *pIter; /* Used to iterate through entire index */ |
| Fts5Structure *pStruct; /* Index structure */ |
| |
| #ifdef SQLITE_DEBUG |
| /* Used by extra internal tests only run if NDEBUG is not defined */ |
| u64 cksum3 = 0; /* Checksum based on contents of indexes */ |
| Fts5Buffer term = {0,0,0}; /* Buffer used to hold most recent term */ |
| #endif |
| const int flags = FTS5INDEX_QUERY_NOOUTPUT; |
| |
| /* Load the FTS index structure */ |
| pStruct = fts5StructureRead(p); |
| |
| /* Check that the internal nodes of each segment match the leaves */ |
| if( pStruct ){ |
| int iLvl, iSeg; |
| for(iLvl=0; iLvl<pStruct->nLevel; iLvl++){ |
| for(iSeg=0; iSeg<pStruct->aLevel[iLvl].nSeg; iSeg++){ |
| Fts5StructureSegment *pSeg = &pStruct->aLevel[iLvl].aSeg[iSeg]; |
| fts5IndexIntegrityCheckSegment(p, pSeg); |
| } |
| } |
| } |
| |
| /* The cksum argument passed to this function is a checksum calculated |
| ** based on all expected entries in the FTS index (including prefix index |
| ** entries). This block checks that a checksum calculated based on the |
| ** actual contents of FTS index is identical. |
| ** |
| ** Two versions of the same checksum are calculated. The first (stack |
| ** variable cksum2) based on entries extracted from the full-text index |
| ** while doing a linear scan of each individual index in turn. |
| ** |
| ** As each term visited by the linear scans, a separate query for the |
| ** same term is performed. cksum3 is calculated based on the entries |
| ** extracted by these queries. |
| */ |
| for(fts5MultiIterNew(p, pStruct, flags, 0, 0, 0, -1, 0, &pIter); |
| fts5MultiIterEof(p, pIter)==0; |
| fts5MultiIterNext(p, pIter, 0, 0) |
| ){ |
| int n; /* Size of term in bytes */ |
| i64 iPos = 0; /* Position read from poslist */ |
| int iOff = 0; /* Offset within poslist */ |
| i64 iRowid = fts5MultiIterRowid(pIter); |
| char *z = (char*)fts5MultiIterTerm(pIter, &n); |
| |
| /* If this is a new term, query for it. Update cksum3 with the results. */ |
| fts5TestTerm(p, &term, z, n, cksum2, &cksum3); |
| |
| if( eDetail==FTS5_DETAIL_NONE ){ |
| if( 0==fts5MultiIterIsEmpty(p, pIter) ){ |
| cksum2 ^= sqlite3Fts5IndexEntryCksum(iRowid, 0, 0, -1, z, n); |
| } |
| }else{ |
| poslist.n = 0; |
| fts5SegiterPoslist(p, &pIter->aSeg[pIter->aFirst[1].iFirst], 0, &poslist); |
| while( 0==sqlite3Fts5PoslistNext64(poslist.p, poslist.n, &iOff, &iPos) ){ |
| int iCol = FTS5_POS2COLUMN(iPos); |
| int iTokOff = FTS5_POS2OFFSET(iPos); |
| cksum2 ^= sqlite3Fts5IndexEntryCksum(iRowid, iCol, iTokOff, -1, z, n); |
| } |
| } |
| } |
| fts5TestTerm(p, &term, 0, 0, cksum2, &cksum3); |
| |
| fts5MultiIterFree(pIter); |
| if( p->rc==SQLITE_OK && cksum!=cksum2 ) p->rc = FTS5_CORRUPT; |
| |
| fts5StructureRelease(pStruct); |
| #ifdef SQLITE_DEBUG |
| fts5BufferFree(&term); |
| #endif |
| fts5BufferFree(&poslist); |
| return fts5IndexReturn(p); |
| } |
| |
| /************************************************************************* |
| ************************************************************************** |
| ** Below this point is the implementation of the fts5_decode() scalar |
| ** function only. |
| */ |
| |
| /* |
| ** Decode a segment-data rowid from the %_data table. This function is |
| ** the opposite of macro FTS5_SEGMENT_ROWID(). |
| */ |
| static void fts5DecodeRowid( |
| i64 iRowid, /* Rowid from %_data table */ |
| int *piSegid, /* OUT: Segment id */ |
| int *pbDlidx, /* OUT: Dlidx flag */ |
| int *piHeight, /* OUT: Height */ |
| int *piPgno /* OUT: Page number */ |
| ){ |
| *piPgno = (int)(iRowid & (((i64)1 << FTS5_DATA_PAGE_B) - 1)); |
| iRowid >>= FTS5_DATA_PAGE_B; |
| |
| *piHeight = (int)(iRowid & (((i64)1 << FTS5_DATA_HEIGHT_B) - 1)); |
| iRowid >>= FTS5_DATA_HEIGHT_B; |
| |
| *pbDlidx = (int)(iRowid & 0x0001); |
| iRowid >>= FTS5_DATA_DLI_B; |
| |
| *piSegid = (int)(iRowid & (((i64)1 << FTS5_DATA_ID_B) - 1)); |
| } |
| |
| static void fts5DebugRowid(int *pRc, Fts5Buffer *pBuf, i64 iKey){ |
| int iSegid, iHeight, iPgno, bDlidx; /* Rowid compenents */ |
| fts5DecodeRowid(iKey, &iSegid, &bDlidx, &iHeight, &iPgno); |
| |
| if( iSegid==0 ){ |
| if( iKey==FTS5_AVERAGES_ROWID ){ |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "{averages} "); |
| }else{ |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "{structure}"); |
| } |
| } |
| else{ |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "{%ssegid=%d h=%d pgno=%d}", |
| bDlidx ? "dlidx " : "", iSegid, iHeight, iPgno |
| ); |
| } |
| } |
| |
| static void fts5DebugStructure( |
| int *pRc, /* IN/OUT: error code */ |
| Fts5Buffer *pBuf, |
| Fts5Structure *p |
| ){ |
| int iLvl, iSeg; /* Iterate through levels, segments */ |
| |
| for(iLvl=0; iLvl<p->nLevel; iLvl++){ |
| Fts5StructureLevel *pLvl = &p->aLevel[iLvl]; |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, |
| " {lvl=%d nMerge=%d nSeg=%d", iLvl, pLvl->nMerge, pLvl->nSeg |
| ); |
| for(iSeg=0; iSeg<pLvl->nSeg; iSeg++){ |
| Fts5StructureSegment *pSeg = &pLvl->aSeg[iSeg]; |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " {id=%d leaves=%d..%d}", |
| pSeg->iSegid, pSeg->pgnoFirst, pSeg->pgnoLast |
| ); |
| } |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "}"); |
| } |
| } |
| |
| /* |
| ** This is part of the fts5_decode() debugging aid. |
| ** |
| ** Arguments pBlob/nBlob contain a serialized Fts5Structure object. This |
| ** function appends a human-readable representation of the same object |
| ** to the buffer passed as the second argument. |
| */ |
| static void fts5DecodeStructure( |
| int *pRc, /* IN/OUT: error code */ |
| Fts5Buffer *pBuf, |
| const u8 *pBlob, int nBlob |
| ){ |
| int rc; /* Return code */ |
| Fts5Structure *p = 0; /* Decoded structure object */ |
| |
| rc = fts5StructureDecode(pBlob, nBlob, 0, &p); |
| if( rc!=SQLITE_OK ){ |
| *pRc = rc; |
| return; |
| } |
| |
| fts5DebugStructure(pRc, pBuf, p); |
| fts5StructureRelease(p); |
| } |
| |
| /* |
| ** This is part of the fts5_decode() debugging aid. |
| ** |
| ** Arguments pBlob/nBlob contain an "averages" record. This function |
| ** appends a human-readable representation of record to the buffer passed |
| ** as the second argument. |
| */ |
| static void fts5DecodeAverages( |
| int *pRc, /* IN/OUT: error code */ |
| Fts5Buffer *pBuf, |
| const u8 *pBlob, int nBlob |
| ){ |
| int i = 0; |
| const char *zSpace = ""; |
| |
| while( i<nBlob ){ |
| u64 iVal; |
| i += sqlite3Fts5GetVarint(&pBlob[i], &iVal); |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "%s%d", zSpace, (int)iVal); |
| zSpace = " "; |
| } |
| } |
| |
| /* |
| ** Buffer (a/n) is assumed to contain a list of serialized varints. Read |
| ** each varint and append its string representation to buffer pBuf. Return |
| ** after either the input buffer is exhausted or a 0 value is read. |
| ** |
| ** The return value is the number of bytes read from the input buffer. |
| */ |
| static int fts5DecodePoslist(int *pRc, Fts5Buffer *pBuf, const u8 *a, int n){ |
| int iOff = 0; |
| while( iOff<n ){ |
| int iVal; |
| iOff += fts5GetVarint32(&a[iOff], iVal); |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " %d", iVal); |
| } |
| return iOff; |
| } |
| |
| /* |
| ** The start of buffer (a/n) contains the start of a doclist. The doclist |
| ** may or may not finish within the buffer. This function appends a text |
| ** representation of the part of the doclist that is present to buffer |
| ** pBuf. |
| ** |
| ** The return value is the number of bytes read from the input buffer. |
| */ |
| static int fts5DecodeDoclist(int *pRc, Fts5Buffer *pBuf, const u8 *a, int n){ |
| i64 iDocid = 0; |
| int iOff = 0; |
| |
| if( n>0 ){ |
| iOff = sqlite3Fts5GetVarint(a, (u64*)&iDocid); |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " id=%lld", iDocid); |
| } |
| while( iOff<n ){ |
| int nPos; |
| int bDel; |
| iOff += fts5GetPoslistSize(&a[iOff], &nPos, &bDel); |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " nPos=%d%s", nPos, bDel?"*":""); |
| iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos)); |
| if( iOff<n ){ |
| i64 iDelta; |
| iOff += sqlite3Fts5GetVarint(&a[iOff], (u64*)&iDelta); |
| iDocid += iDelta; |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " id=%lld", iDocid); |
| } |
| } |
| |
| return iOff; |
| } |
| |
| /* |
| ** This function is part of the fts5_decode() debugging function. It is |
| ** only ever used with detail=none tables. |
| ** |
| ** Buffer (pData/nData) contains a doclist in the format used by detail=none |
| ** tables. This function appends a human-readable version of that list to |
| ** buffer pBuf. |
| ** |
| ** If *pRc is other than SQLITE_OK when this function is called, it is a |
| ** no-op. If an OOM or other error occurs within this function, *pRc is |
| ** set to an SQLite error code before returning. The final state of buffer |
| ** pBuf is undefined in this case. |
| */ |
| static void fts5DecodeRowidList( |
| int *pRc, /* IN/OUT: Error code */ |
| Fts5Buffer *pBuf, /* Buffer to append text to */ |
| const u8 *pData, int nData /* Data to decode list-of-rowids from */ |
| ){ |
| int i = 0; |
| i64 iRowid = 0; |
| |
| while( i<nData ){ |
| const char *zApp = ""; |
| u64 iVal; |
| i += sqlite3Fts5GetVarint(&pData[i], &iVal); |
| iRowid += iVal; |
| |
| if( i<nData && pData[i]==0x00 ){ |
| i++; |
| if( i<nData && pData[i]==0x00 ){ |
| i++; |
| zApp = "+"; |
| }else{ |
| zApp = "*"; |
| } |
| } |
| |
| sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " %lld%s", iRowid, zApp); |
| } |
| } |
| |
| /* |
| ** The implementation of user-defined scalar function fts5_decode(). |
| */ |
| static void fts5DecodeFunction( |
| sqlite3_context *pCtx, /* Function call context */ |
| int nArg, /* Number of args (always 2) */ |
| sqlite3_value **apVal /* Function arguments */ |
| ){ |
| i64 iRowid; /* Rowid for record being decoded */ |
| int iSegid,iHeight,iPgno,bDlidx;/* Rowid components */ |
| const u8 *aBlob; int n; /* Record to decode */ |
| u8 *a = 0; |
| Fts5Buffer s; /* Build up text to return here */ |
| int rc = SQLITE_OK; /* Return code */ |
| int nSpace = 0; |
| int eDetailNone = (sqlite3_user_data(pCtx)!=0); |
| |
| assert( nArg==2 ); |
| UNUSED_PARAM(nArg); |
| memset(&s, 0, sizeof(Fts5Buffer)); |
| iRowid = sqlite3_value_int64(apVal[0]); |
| |
| /* Make a copy of the second argument (a blob) in aBlob[]. The aBlob[] |
| ** copy is followed by FTS5_DATA_ZERO_PADDING 0x00 bytes, which prevents |
| ** buffer overreads even if the record is corrupt. */ |
| n = sqlite3_value_bytes(apVal[1]); |
| aBlob = sqlite3_value_blob(apVal[1]); |
| nSpace = n + FTS5_DATA_ZERO_PADDING; |
| a = (u8*)sqlite3Fts5MallocZero(&rc, nSpace); |
| if( a==0 ) goto decode_out; |
| memcpy(a, aBlob, n); |
| |
| |
| fts5DecodeRowid(iRowid, &iSegid, &bDlidx, &iHeight, &iPgno); |
| |
| fts5DebugRowid(&rc, &s, iRowid); |
| if( bDlidx ){ |
| Fts5Data dlidx; |
| Fts5DlidxLvl lvl; |
| |
| dlidx.p = a; |
| dlidx.nn = n; |
| |
| memset(&lvl, 0, sizeof(Fts5DlidxLvl)); |
| lvl.pData = &dlidx; |
| lvl.iLeafPgno = iPgno; |
| |
| for(fts5DlidxLvlNext(&lvl); lvl.bEof==0; fts5DlidxLvlNext(&lvl)){ |
| sqlite3Fts5BufferAppendPrintf(&rc, &s, |
| " %d(%lld)", lvl.iLeafPgno, lvl.iRowid |
| ); |
| } |
| }else if( iSegid==0 ){ |
| if( iRowid==FTS5_AVERAGES_ROWID ){ |
| fts5DecodeAverages(&rc, &s, a, n); |
| }else{ |
| fts5DecodeStructure(&rc, &s, a, n); |
| } |
| }else if( eDetailNone ){ |
| Fts5Buffer term; /* Current term read from page */ |
| int szLeaf; |
| int iPgidxOff = szLeaf = fts5GetU16(&a[2]); |
| int iTermOff; |
| int nKeep = 0; |
| int iOff; |
| |
| memset(&term, 0, sizeof(Fts5Buffer)); |
| |
| /* Decode any entries that occur before the first term. */ |
| if( szLeaf<n ){ |
| iPgidxOff += fts5GetVarint32(&a[iPgidxOff], iTermOff); |
| }else{ |
| iTermOff = szLeaf; |
| } |
| fts5DecodeRowidList(&rc, &s, &a[4], iTermOff-4); |
| |
| iOff = iTermOff; |
| while( iOff<szLeaf ){ |
| int nAppend; |
| |
| /* Read the term data for the next term*/ |
| iOff += fts5GetVarint32(&a[iOff], nAppend); |
| term.n = nKeep; |
| fts5BufferAppendBlob(&rc, &term, nAppend, &a[iOff]); |
| sqlite3Fts5BufferAppendPrintf( |
| &rc, &s, " term=%.*s", term.n, (const char*)term.p |
| ); |
| iOff += nAppend; |
| |
| /* Figure out where the doclist for this term ends */ |
| if( iPgidxOff<n ){ |
| int nIncr; |
| iPgidxOff += fts5GetVarint32(&a[iPgidxOff], nIncr); |
| iTermOff += nIncr; |
| }else{ |
| iTermOff = szLeaf; |
| } |
| |
| fts5DecodeRowidList(&rc, &s, &a[iOff], iTermOff-iOff); |
| iOff = iTermOff; |
| if( iOff<szLeaf ){ |
| iOff += fts5GetVarint32(&a[iOff], nKeep); |
| } |
| } |
| |
| fts5BufferFree(&term); |
| }else{ |
| Fts5Buffer term; /* Current term read from page */ |
| int szLeaf; /* Offset of pgidx in a[] */ |
| int iPgidxOff; |
| int iPgidxPrev = 0; /* Previous value read from pgidx */ |
| int iTermOff = 0; |
| int iRowidOff = 0; |
| int iOff; |
| int nDoclist; |
| |
| memset(&term, 0, sizeof(Fts5Buffer)); |
| |
| if( n<4 ){ |
| sqlite3Fts5BufferSet(&rc, &s, 7, (const u8*)"corrupt"); |
| goto decode_out; |
| }else{ |
| iRowidOff = fts5GetU16(&a[0]); |
| iPgidxOff = szLeaf = fts5GetU16(&a[2]); |
| if( iPgidxOff<n ){ |
| fts5GetVarint32(&a[iPgidxOff], iTermOff); |
| } |
| } |
| |
| /* Decode the position list tail at the start of the page */ |
| if( iRowidOff!=0 ){ |
| iOff = iRowidOff; |
| }else if( iTermOff!=0 ){ |
| iOff = iTermOff; |
| }else{ |
| iOff = szLeaf; |
| } |
| fts5DecodePoslist(&rc, &s, &a[4], iOff-4); |
| |
| /* Decode any more doclist data that appears on the page before the |
| ** first term. */ |
| nDoclist = (iTermOff ? iTermOff : szLeaf) - iOff; |
| fts5DecodeDoclist(&rc, &s, &a[iOff], nDoclist); |
| |
| while( iPgidxOff<n ){ |
| int bFirst = (iPgidxOff==szLeaf); /* True for first term on page */ |
| int nByte; /* Bytes of data */ |
| int iEnd; |
| |
| iPgidxOff += fts5GetVarint32(&a[iPgidxOff], nByte); |
| iPgidxPrev += nByte; |
| iOff = iPgidxPrev; |
| |
| if( iPgidxOff<n ){ |
| fts5GetVarint32(&a[iPgidxOff], nByte); |
| iEnd = iPgidxPrev + nByte; |
| }else{ |
| iEnd = szLeaf; |
| } |
| |
| if( bFirst==0 ){ |
| iOff += fts5GetVarint32(&a[iOff], nByte); |
| term.n = nByte; |
| } |
| iOff += fts5GetVarint32(&a[iOff], nByte); |
| fts5BufferAppendBlob(&rc, &term, nByte, &a[iOff]); |
| iOff += nByte; |
| |
| sqlite3Fts5BufferAppendPrintf( |
| &rc, &s, " term=%.*s", term.n, (const char*)term.p |
| ); |
| iOff += fts5DecodeDoclist(&rc, &s, &a[iOff], iEnd-iOff); |
| } |
| |
| fts5BufferFree(&term); |
| } |
| |
| decode_out: |
| sqlite3_free(a); |
| if( rc==SQLITE_OK ){ |
| sqlite3_result_text(pCtx, (const char*)s.p, s.n, SQLITE_TRANSIENT); |
| }else{ |
| sqlite3_result_error_code(pCtx, rc); |
| } |
| fts5BufferFree(&s); |
| } |
| |
| /* |
| ** The implementation of user-defined scalar function fts5_rowid(). |
| */ |
| static void fts5RowidFunction( |
| sqlite3_context *pCtx, /* Function call context */ |
| int nArg, /* Number of args (always 2) */ |
| sqlite3_value **apVal /* Function arguments */ |
| ){ |
| const char *zArg; |
| if( nArg==0 ){ |
| sqlite3_result_error(pCtx, "should be: fts5_rowid(subject, ....)", -1); |
| }else{ |
| zArg = (const char*)sqlite3_value_text(apVal[0]); |
| if( 0==sqlite3_stricmp(zArg, "segment") ){ |
| i64 iRowid; |
| int segid, pgno; |
| if( nArg!=3 ){ |
| sqlite3_result_error(pCtx, |
| "should be: fts5_rowid('segment', segid, pgno))", -1 |
| ); |
| }else{ |
| segid = sqlite3_value_int(apVal[1]); |
| pgno = sqlite3_value_int(apVal[2]); |
| iRowid = FTS5_SEGMENT_ROWID(segid, pgno); |
| sqlite3_result_int64(pCtx, iRowid); |
| } |
| }else{ |
| sqlite3_result_error(pCtx, |
| "first arg to fts5_rowid() must be 'segment'" , -1 |
| ); |
| } |
| } |
| } |
| |
| /* |
| ** This is called as part of registering the FTS5 module with database |
| ** connection db. It registers several user-defined scalar functions useful |
| ** with FTS5. |
| ** |
| ** If successful, SQLITE_OK is returned. If an error occurs, some other |
| ** SQLite error code is returned instead. |
| */ |
| int sqlite3Fts5IndexInit(sqlite3 *db){ |
| int rc = sqlite3_create_function( |
| db, "fts5_decode", 2, SQLITE_UTF8, 0, fts5DecodeFunction, 0, 0 |
| ); |
| |
| if( rc==SQLITE_OK ){ |
| rc = sqlite3_create_function( |
| db, "fts5_decode_none", 2, |
| SQLITE_UTF8, (void*)db, fts5DecodeFunction, 0, 0 |
| ); |
| } |
| |
| if( rc==SQLITE_OK ){ |
| rc = sqlite3_create_function( |
| db, "fts5_rowid", -1, SQLITE_UTF8, 0, fts5RowidFunction, 0, 0 |
| ); |
| } |
| return rc; |
| } |
| |
| |
| int sqlite3Fts5IndexReset(Fts5Index *p){ |
| assert( p->pStruct==0 || p->iStructVersion!=0 ); |
| if( fts5IndexDataVersion(p)!=p->iStructVersion ){ |
| fts5StructureInvalidate(p); |
| } |
| return fts5IndexReturn(p); |
| } |