typedefvoid (*fts5_extension_function)( const Fts5ExtensionApi *pApi, /* API offered by current FTS version */
Fts5Context *pFts, /* First arg to pass to pApi functions */
sqlite3_context *pCtx, /* Context for returning result/error */
int nVal, /* Number of values in apVal[] array */
sqlite3_value **apVal /* Array of trailing arguments */
);
int (*xColumnCount)(Fts5Context*);
int (*xRowCount)(Fts5Context*, sqlite3_int64 *pnRow);
int (*xColumnTotalSize)(Fts5Context*, int iCol, sqlite3_int64 *pnToken);
int (*xTokenize)(Fts5Context*, const char *pText, int nText, /* Text to tokenize */ void *pCtx, /* Context passed to xToken() */
int (*xToken)(void*, int, const char*, int, int, int) /* Callback */
);
int (*xPhraseCount)(Fts5Context*);
int (*xPhraseSize)(Fts5Context*, int iPhrase);
int (*xInstCount)(Fts5Context*, int *pnInst);
int (*xInst)(Fts5Context*, int iIdx, int *piPhrase, int *piCol, int *piOff);
sqlite3_int64 (*xRowid)(Fts5Context*);
int (*xColumnText)(Fts5Context*, int iCol, const char **pz, int *pn);
int (*xColumnSize)(Fts5Context*, int iCol, int *pnToken);
int (*xQueryPhrase)(Fts5Context*, int iPhrase, void *pUserData,
int(*)(const Fts5ExtensionApi*,Fts5Context*,void*)
);
int (*xSetAuxdata)(Fts5Context*, void *pAux, void(*xDelete)(void*)); void *(*xGetAuxdata)(Fts5Context*, int bClear);
int (*xPhraseFirst)(Fts5Context*, int iPhrase, Fts5PhraseIter*, int*, int*); void (*xPhraseNext)(Fts5Context*, Fts5PhraseIter*, int *piCol, int *piOff);
int (*xPhraseFirstColumn)(Fts5Context*, int iPhrase, Fts5PhraseIter*, int*); void (*xPhraseNextColumn)(Fts5Context*, Fts5PhraseIter*, int *piCol);
/* Below this point are iVersion>=3 only */
int (*xQueryToken)(Fts5Context*,
int iPhrase, int iToken, const char **ppToken, int *pnToken
);
int (*xInstToken)(Fts5Context*, int iIdx, int iToken, const char**, int*);
/* Below this point are iVersion>=4 only */
int (*xColumnLocale)(Fts5Context*, int iCol, const char **pz, int *pn);
int (*xTokenize_v2)(Fts5Context*, const char *pText, int nText, /* Text to tokenize */ const char *pLocale, int nLocale, /* Locale to pass to tokenizer */ void *pCtx, /* Context passed to xToken() */
int (*xToken)(void*, int, const char*, int, int, int) /* Callback */
);
};
int (*xCreate)(void*, const char **azArg, int nArg, Fts5Tokenizer **ppOut); void (*xDelete)(Fts5Tokenizer*);
int (*xTokenize)(Fts5Tokenizer*, void *pCtx,
int flags, /* Mask of FTS5_TOKENIZE_* flags */ const char *pText, int nText, const char *pLocale, int nLocale,
int (*xToken)( void *pCtx, /* Copy of 2nd argument to xTokenize() */
int tflags, /* Mask of FTS5_TOKEN_* flags */ const char *pToken, /* Pointer to buffer containing token */
int nToken, /* Size of token in bytes */
int iStart, /* Byte offset of token within input text */
int iEnd /* Byte offset of end of token within input text */
)
);
};
/* **Newcodeshouldusethefts5_tokenizer_v2typetodefinetokenizer **implementations.Thefollowingtypeisincludedforlegacyapplications **thatstilluseit.
*/ typedefstruct fts5_tokenizer fts5_tokenizer; struct fts5_tokenizer {
int (*xCreate)(void*, const char **azArg, int nArg, Fts5Tokenizer **ppOut); void (*xDelete)(Fts5Tokenizer*);
int (*xTokenize)(Fts5Tokenizer*, void *pCtx,
int flags, /* Mask of FTS5_TOKENIZE_* flags */ const char *pText, int nText,
int (*xToken)( void *pCtx, /* Copy of 2nd argument to xTokenize() */
int tflags, /* Mask of FTS5_TOKEN_* flags */ const char *pToken, /* Pointer to buffer containing token */
int nToken, /* Size of token in bytes */
int iStart, /* Byte offset of token within input text */
int iEnd /* Byte offset of end of token within input text */
)
);
};
/* Flags that may be passed as the third argument to xTokenize() */ #define FTS5_TOKENIZE_QUERY 0x0001 #define FTS5_TOKENIZE_PREFIX 0x0002 #define FTS5_TOKENIZE_DOCUMENT 0x0004 #define FTS5_TOKENIZE_AUX 0x0008
/* Flags that may be passed by the tokenizer implementation back to FTS5
** as the third argument to the supplied xToken callback. */ #define FTS5_TOKEN_COLOCATED 0x0001 /* Same position as prev. token */
/************************************************************************* **FTS5EXTENSIONREGISTRATIONAPI
*/ typedefstruct fts5_api fts5_api; struct fts5_api {
int iVersion; /* Currently always set to 3 */
/* Create a new tokenizer */
int (*xCreateTokenizer)(
fts5_api *pApi, const char *zName, void *pUserData,
fts5_tokenizer *pTokenizer, void (*xDestroy)(void*)
);
/* Find an existing tokenizer */
int (*xFindTokenizer)(
fts5_api *pApi, const char *zName, void **ppUserData,
fts5_tokenizer *pTokenizer
);
/* Create a new auxiliary function */
int (*xCreateFunction)(
fts5_api *pApi, const char *zName, void *pUserData,
fts5_extension_function xFunction, void (*xDestroy)(void*)
);
/* APIs below this point are only available if iVersion>=3 */
/* Create a new tokenizer */
int (*xCreateTokenizer_v2)(
fts5_api *pApi, const char *zName, void *pUserData,
fts5_tokenizer_v2 *pTokenizer, void (*xDestroy)(void*)
);
/* Find an existing tokenizer */
int (*xFindTokenizer_v2)(
fts5_api *pApi, const char *zName, void **ppUserData,
fts5_tokenizer_v2 **ppTokenizer
);
};
/* Truncate very long tokens to this many bytes. Hard limit is **(65536-1-1-4-9)==65521bytes.Thelimitingfactoristhe16-bitoffset
** field that occurs at the start of each leaf page (see fts5_index.c). */ #define FTS5_MAX_TOKEN_SIZE 32768
/* If a NEAR() clump or phrase may only match a specific set of columns, **thenanobjectofthefollowingtypeisusedtorecordthesetofcolumns. **EachentryintheaiCol[]arrayisacolumnthatmaybematched. ** **Thisobjectisusedbyfts5_expr.candfts5_index.c.
*/ struct Fts5Colset {
int nCol;
int aiCol[FLEXARRAY];
};
/* Size (int bytes) of a complete Fts5Colset object with N columns. */ #define SZ_FTS5COLSET(N) (sizeof(i64)*((N+2)/2))
struct Fts5TokenizerConfig {
Fts5Tokenizer *pTok;
fts5_tokenizer_v2 *pApi2;
fts5_tokenizer *pApi1; const char **azArg;
int nArg;
int ePattern; /* FTS_PATTERN_XXX constant */ const char *pLocale; /* Current locale to use */
int nLocale; /* Size of pLocale in bytes */
};
/* **Aninstanceofthefollowingstructureencodesallinformationthatcan **begleanedfromtheCREATEVIRTUALTABLEstatement. ** **Andallinformationloadedfromthe%_configtable. ** **nAutomerge: **Theminimumnumberofsegmentsthatanauto-mergeoperationshould **attempttomergetogether.Avalueof1setstheobjecttousethe **compiletimedefault.Zerodisablesauto-mergealtogether. ** **bContentlessDelete: **Trueifthecontentless_deleteoptionwaspresentintheCREATE **VIRTUALTABLEstatement. ** **zContent: ** **zContentRowid: **Thevalueofthecontent_rowid=option,ifonewasspecified.Or **thestring"rowid"otherwise.Thistextisnotquoted-ifitis **usedaspartofanSQLstatementitneedstobequotedappropriately. ** **zContentExprlist: ** **pzErrmsg: **Thisexistsinordertoallowthefts5_index.cmoduletoreturna **decenterrormessageifitencountersafile-formatversionitdoes **notunderstand. ** **bColumnsize: **Trueifthe%_docsizetableiscreated. ** **bPrefixIndex: **Thisisonlyusedfordebugging.Ifsettofalse,anyprefixindexes **areignored.Thisvalueisconfiguredusing: ** **INSERTINTOtbl(tbl,rank)VALUES('prefix-index',$bPrefixIndex); ** **bLocale: **Settotrueiflocale=1wasspecifiedwhenthetablewascreated.
*/ struct Fts5Config {
sqlite3 *db; /* Database handle */
Fts5Global *pGlobal; /* Global fts5 object for handle db */
char *zDb; /* Database holding FTS index (e.g. "main") */
char *zName; /* Name of FTS index */
int nCol; /* Number of columns */
char **azCol; /* Column names */
u8 *abUnindexed; /* True for unindexed columns */
int nPrefix; /* Number of prefix indexes */
int *aPrefix; /* Sizes in bytes of nPrefix prefix indexes */
int eContent; /* An FTS5_CONTENT value */
int bContentlessDelete; /* "contentless_delete=" option (dflt==0) */
int bContentlessUnindexed; /* "contentless_unindexed=" option (dflt=0) */
char *zContent; /* content table */
char *zContentRowid; /* "content_rowid=" option value */
int bColumnsize; /* "columnsize=" option value (dflt==1) */
int bTokendata; /* "tokendata=" option value (dflt==0) */
int bLocale; /* "locale=" option value (dflt==0) */
int eDetail; /* FTS5_DETAIL_XXX value */
char *zContentExprlist;
Fts5TokenizerConfig t;
int bLock; /* True when table is preparing statement */
/* Values loaded from the %_config table */
int iVersion; /* fts5 file format 'version' */
int iCookie; /* Incremented when %_config is modified */
int pgsz; /* Approximate page size used in %_data */
int nAutomerge; /* 'automerge' setting */
int nCrisisMerge; /* Maximum allowed segments per level */
int nUsermerge; /* 'usermerge' setting */
int nHashSize; /* Bytes of memory for in-memory hash */
char *zRank; /* Name of rank function */
char *zRankArgs; /* Arguments to rank function */
int bSecureDelete; /* 'secure-delete' */
int nDeleteMerge; /* 'deletemerge' */
int bPrefixInsttoken; /* 'prefix-insttoken' */
/* If non-NULL, points to sqlite3_vtab.base.zErrmsg. Often NULL. */
char **pzErrmsg;
#ifdef SQLITE_DEBUG
int bPrefixIndex; /* True to use prefix-indexes */ #endif
};
/* Current expected value of %_config table 'version' field. And **theexpectedversionifthe'secure-delete'optionhaseverbeen
** set on the table. */ #define FTS5_CURRENT_VERSION 4 #define FTS5_CURRENT_VERSION_SECUREDELETE 5
typedefstruct Fts5PoslistReader Fts5PoslistReader; struct Fts5PoslistReader { /* Variables used only by sqlite3Fts5PoslistIterXXX() functions. */ const u8 *a; /* Position list to iterate through */
int n; /* Size of buffer at a[] in bytes */
int i; /* Current offset in a[] */
u8 bFlag; /* For client use (any custom purpose) */
/* Output variables */
u8 bEof; /* Set to true at EOF */
i64 iPos; /* (iCol<<32) + iPos */
}; static int sqlite3Fts5PoslistReaderInit( const u8 *a, int n, /* Poslist buffer to iterate through */
Fts5PoslistReader *pIter /* Iterator object to initialize */
); static int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader*);
static int sqlite3Fts5PoslistNext64( const u8 *a, int n, /* Buffer containing poslist */
int *pi, /* IN/OUT: Offset within a[] */
i64 *piOff /* IN/OUT: Current offset */
);
/* Character set tests (like isspace(), isalpha() etc.) */ static int sqlite3Fts5IsBareword(char t);
/* Bucket of terms object used by the integrity-check in offsets=0 mode. */ typedefstruct Fts5Termset Fts5Termset; static int sqlite3Fts5TermsetNew(Fts5Termset**); static int sqlite3Fts5TermsetAdd(Fts5Termset*, int, const char*, int, int *pbPresent); staticvoid sqlite3Fts5TermsetFree(Fts5Termset*);
/* **ValuesusedaspartoftheflagsargumentpassedtoIndexQuery().
*/ #define FTS5INDEX_QUERY_PREFIX 0x0001 /* Prefix query */ #define FTS5INDEX_QUERY_DESC 0x0002 /* Docs in descending rowid order */ #define FTS5INDEX_QUERY_TEST_NOIDX 0x0004 /* Do not use prefix index */ #define FTS5INDEX_QUERY_SCAN 0x0008 /* Scan query (fts5vocab) */
/* The following are used internally by the fts5_index.c module. They are **definedhereonlytomakeiteasiertoavoidclasheswiththeflags
** above. */ #define FTS5INDEX_QUERY_SKIPEMPTY 0x0010 #define FTS5INDEX_QUERY_NOOUTPUT 0x0020 #define FTS5INDEX_QUERY_SKIPHASH 0x0040 #define FTS5INDEX_QUERY_NOTOKENDATA 0x0080 #define FTS5INDEX_QUERY_SCANONETERM 0x0100
/* **Create/destroyanFts5Indexobject.
*/ static int sqlite3Fts5IndexOpen(Fts5Config *pConfig, int bCreate, Fts5Index**, char**); static int sqlite3Fts5IndexClose(Fts5Index *p);
/* **Returnasimplechecksumvaluebasedonthearguments.
*/ static u64 sqlite3Fts5IndexEntryCksum(
i64 iRowid,
int iCol,
int iPos,
int iIdx, const char *pTerm,
int nTerm
);
/* **Argumentppointstoabuffercontainingutf-8textthatisnbytesin **size.ReturnthenumberofbytesinthenCharcharacterprefixofthe **buffer,or0iftherearelessthannCharcharactersintotal.
*/ static int sqlite3Fts5IndexCharlenToBytelen( const char *p,
int nByte,
int nChar
);
/* **Openanewiteratortoiteratethoughallrowidsthatmatchthe **specifiedtokenortokenprefix.
*/ static 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 */
);
/* **Thevariousoperationsonopentokenortokenprefixiteratorsopened **usingsqlite3Fts5IndexQuery().
*/ static int sqlite3Fts5IterNext(Fts5IndexIter*); static int sqlite3Fts5IterNextFrom(Fts5IndexIter*, i64 iMatch);
/* **Thisinterfaceisusedbythefts5vocabmodule.
*/ staticconst char *sqlite3Fts5IterTerm(Fts5IndexIter*, int*); static int sqlite3Fts5IterNextScan(Fts5IndexIter*); staticvoid *sqlite3Fts5StructureRef(Fts5Index*); staticvoid sqlite3Fts5StructureRelease(void*); static int sqlite3Fts5StructureTest(Fts5Index*, void*);
/* **UsedbyxInstToken():
*/ static int sqlite3Fts5IterToken(
Fts5IndexIter *pIndexIter, const char *pToken, int nToken,
i64 iRowid,
int iCol,
int iOff, const char **ppOut, int *pnOut
);
/* **Insertorremovedatatoorfromtheindex.Eachtimeadocumentis **addedtoorremovedfromtheindex,thisfunctioniscalledoneormore **times. ** **Foraninsert,itmustbecalledonceforeachtokeninthenewdocument. **Iftheoperationisadelete,itmustbecalled(atleast)onceforeach **uniquetokeninthedocumentwithaniColvaluelessthanzero.TheiPos **argumentisignoredforadelete.
*/ static 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 */
);
/* **Indicatethatsubsequentcallstosqlite3Fts5IndexWrite()pertainto **documentiDocid.
*/ static int sqlite3Fts5IndexBeginWrite(
Fts5Index *p, /* Index to write to */
int bDelete, /* True if current operation is a delete */
i64 iDocid /* Docid to add or remove data from */
);
/* **Flushanydatastoredinthein-memoryhashtablestothedatabase. **Alsocloseanyopenblobhandles.
*/ static int sqlite3Fts5IndexSync(Fts5Index *p);
/* **Discardanydatastoredinthein-memoryhashtables.Donotwriteit **tothedatabase.Additionally,assumethatthecontentsofthe%_data **tablemayhavechangedondisk.Soanyin-memorycachesof%_data **recordsmustbeinvalidated.
*/ static int sqlite3Fts5IndexRollback(Fts5Index *p);
/* **Getorsetthe"averages"values.
*/ static int sqlite3Fts5IndexGetAverages(Fts5Index *p, i64 *pnRow, i64 *anSize); static int sqlite3Fts5IndexSetAverages(Fts5Index *p, const u8*, int);
/* **Functionscalledbythestoragemoduleaspartofintegrity-check.
*/ static int sqlite3Fts5IndexIntegrityCheck(Fts5Index*, u64 cksum, int bUseCksum);
/* **CalledduringvirtualmoduleinitializationtoregisterUDF **fts5_decode()withSQLite
*/ static int sqlite3Fts5IndexInit(sqlite3*);
static int sqlite3Fts5IndexSetCookie(Fts5Index*, int);
/* **Returnthetotalnumberofentriesreadfromthe%_datatableby **thisconnectionsinceitwascreated.
*/ static int sqlite3Fts5IndexReads(Fts5Index *p);
static int sqlite3Fts5IndexReinit(Fts5Index *p); static int sqlite3Fts5IndexOptimize(Fts5Index *p); static int sqlite3Fts5IndexMerge(Fts5Index *p, int nMerge); static int sqlite3Fts5IndexReset(Fts5Index *p);
static int sqlite3Fts5IndexLoadConfig(Fts5Index *p);
static int sqlite3Fts5IndexGetOrigin(Fts5Index *p, i64 *piOrigin); static int sqlite3Fts5IndexContentlessDelete(Fts5Index *p, i64 iOrigin, i64 iRowid);
/* Used to populate hash tables for xInstToken in detail=none/column mode. */ static int sqlite3Fts5IndexIterWriteTokendata(
Fts5IndexIter*, const char*, int, i64 iRowid, int iCol, int iOff
);
/* **Createahashtable,freeahashtable.
*/ static int sqlite3Fts5HashNew(Fts5Config*, Fts5Hash**, int *pnSize); staticvoid sqlite3Fts5HashFree(Fts5Hash*);
static int sqlite3Fts5HashWrite(
Fts5Hash*,
i64 iRowid, /* Rowid for this entry */
int iCol, /* Column token appears in (-ve -> delete) */
int iPos, /* Position of token within column */
char bByte, const char *pToken, int nToken /* Token to add or remove to or from index */
);
/* **Returntrueifthehashisempty,falseotherwise.
*/ static int sqlite3Fts5HashIsEmpty(Fts5Hash*);
static int sqlite3Fts5HashQuery(
Fts5Hash*, /* Hash table to query */
int nPre, const char *pTerm, int nTerm, /* Query term */ void **ppObj, /* OUT: Pointer to doclist for pTerm */
int *pnDoclist /* OUT: Size of doclist in bytes */
);
static int sqlite3Fts5HashScanInit(
Fts5Hash*, /* Hash table to query */ const char *pTerm, int nTerm /* Query prefix */
); staticvoid sqlite3Fts5HashScanNext(Fts5Hash*); static int sqlite3Fts5HashScanEof(Fts5Hash*); staticvoid sqlite3Fts5HashScanEntry(Fts5Hash *, const char **pzTerm, /* OUT: term (nul-terminated) */
int *pnTerm, /* OUT: Size of term in bytes */ const u8 **ppDoclist, /* OUT: pointer to doclist */
int *pnDoclist /* OUT: size of doclist in bytes */
);
#define FTS5_STMT_SCAN_ASC 0/* SELECT rowid, * FROM ... ORDER BY 1 ASC */ #define FTS5_STMT_SCAN_DESC 1/* SELECT rowid, * FROM ... ORDER BY 1 DESC */ #define FTS5_STMT_LOOKUP 2/* SELECT rowid, * FROM ... WHERE rowid=? */
typedefstruct Fts5Storage Fts5Storage;
static int sqlite3Fts5StorageOpen(Fts5Config*, Fts5Index*, int, Fts5Storage**, char**); static int sqlite3Fts5StorageClose(Fts5Storage *p); static int sqlite3Fts5StorageRename(Fts5Storage*, const char *zName);
static int sqlite3Fts5DropAll(Fts5Config*); static int sqlite3Fts5CreateTable(Fts5Config*, const char*, const char*, int, char **);
static int sqlite3Fts5StorageDelete(Fts5Storage *p, i64, sqlite3_value**, int); static int sqlite3Fts5StorageContentInsert(Fts5Storage *p, int, sqlite3_value**, i64*); static int sqlite3Fts5StorageIndexInsert(Fts5Storage *p, sqlite3_value**, i64);
static int sqlite3Fts5StorageIntegrity(Fts5Storage *p, int iArg);
static int sqlite3Fts5StorageStmt(Fts5Storage *p, int eStmt, sqlite3_stmt**, char**); staticvoid sqlite3Fts5StorageStmtRelease(Fts5Storage *p, int eStmt, sqlite3_stmt*);
static int sqlite3Fts5StorageDocsize(Fts5Storage *p, i64 iRowid, int *aCol); static int sqlite3Fts5StorageSize(Fts5Storage *p, int iCol, i64 *pnAvg); static int sqlite3Fts5StorageRowCount(Fts5Storage *p, i64 *pnRow);
static int sqlite3Fts5StorageSync(Fts5Storage *p); static int sqlite3Fts5StorageRollback(Fts5Storage *p);
static int sqlite3Fts5StorageConfigValue(
Fts5Storage *p, const char*, sqlite3_value*, int
);
static int sqlite3Fts5StorageDeleteAll(Fts5Storage *p); static int sqlite3Fts5StorageRebuild(Fts5Storage *p); static int sqlite3Fts5StorageOptimize(Fts5Storage *p); static int sqlite3Fts5StorageMerge(Fts5Storage *p, int nMerge); static int sqlite3Fts5StorageReset(Fts5Storage *p);
staticvoid sqlite3Fts5StorageReleaseDeleteRow(Fts5Storage*); static int sqlite3Fts5StorageFindDeleteRow(Fts5Storage *p, i64 iDel);
struct Fts5Token { const char *p; /* Token text (not NULL terminated) */
int n; /* Size of buffer p in bytes */
};
/* Parse a MATCH expression. */ static int sqlite3Fts5ExprNew(
Fts5Config *pConfig,
int bPhraseToAnd,
int iCol, /* Column on LHS of MATCH operator */ const char *zExpr,
Fts5Expr **ppNew,
char **pzErr
); static int sqlite3Fts5ExprPattern(
Fts5Config *pConfig,
int bGlob,
int iCol, const char *zText,
Fts5Expr **pp
);
/* **for(rc=sqlite3Fts5ExprFirst(pExpr,pIdx,bDesc); **rc==SQLITE_OK&&0==sqlite3Fts5ExprEof(pExpr); **rc=sqlite3Fts5ExprNext(pExpr) **){ **// The document with rowid iRowid matches the expression! **i64iRowid=sqlite3Fts5ExprRowid(pExpr); **}
*/ static int sqlite3Fts5ExprFirst(Fts5Expr*, Fts5Index *pIdx, i64 iMin, i64, int bDesc); static int sqlite3Fts5ExprNext(Fts5Expr*, i64 iMax); static int sqlite3Fts5ExprEof(Fts5Expr*); static i64 sqlite3Fts5ExprRowid(Fts5Expr*);
staticvoid sqlite3Fts5ExprFree(Fts5Expr*); static int sqlite3Fts5ExprAnd(Fts5Expr **pp1, Fts5Expr *p2);
/* Called during startup to register a UDF with SQLite */ static int sqlite3Fts5ExprInit(Fts5Global*, sqlite3*);
static int sqlite3Fts5ExprPhraseCount(Fts5Expr*); static int sqlite3Fts5ExprPhraseSize(Fts5Expr*, int iPhrase); static int sqlite3Fts5ExprPoslist(Fts5Expr*, int, const u8 **);
/******************************************* **Thefts5_expr.cAPIabovethispointisusedbytheotherhand-written **Ccodeinthismodule.Theinterfacesbelowthispointarecalledby
** the parser code in fts5parse.y. */
/************************************************************************** **Interfacetoautomaticallygeneratedcodeinfts5_unicode2.c.
*/ static int sqlite3Fts5UnicodeIsdiacritic(int c); static int sqlite3Fts5UnicodeFold(int c, int bRemoveDiacritic);
static int sqlite3Fts5UnicodeCatParse(const char*, u8*); static int sqlite3Fts5UnicodeCategory(u32 iCode); staticvoid sqlite3Fts5UnicodeAscii(u8*, u8*); /* **Endofinterfacetocodeinfts5_unicode2.c.
**************************************************************************/
/* Define the fts5yytestcase() macro to be a no-op if is not already defined **otherwise. ** **Applicationscanchoosetodefinefts5yytestcase()inthe%includesection **toamacrothatcanassistinverifyingcodecoverage.Forproduction **codethefts5yytestcase()macroshouldbeturnedoff.Butitisuseful **fortesting.
*/ #ifndef fts5yytestcase # define fts5yytestcase(X) #endif
/* Macro to determine if stack space has the ability to grow using **heapmemory.
*/ #if fts5YYSTACKDEPTH<=0 || fts5YYDYNSTACK # define fts5YYGROWABLESTACK 1 #else # define fts5YYGROWABLESTACK 0 #endif
/* Guarantee a minimum number of initial stack slots.
*/ #if fts5YYSTACKDEPTH<=0 # undef fts5YYSTACKDEPTH # define fts5YYSTACKDEPTH 2/* Need a minimum stack size */ #endif
/* The following structure represents a single element of the **parser'sstack.Informationstoredincludes: ** **+Thestatenumberfortheparseratthislevelofthestack. ** **+Thevalueofthetokenstoredatthislevelofthestack. **(Inotherwords,the"major"token.) ** **+Thesemanticvaluestoredatthislevelofthestack.Thisis **theinformationusedbytheactionroutinesinthegrammar. **Itissometimescalledthe"minor"token. ** **Afterthe"shift"halfofaSHIFTREDUCEaction,thestatenofield **actuallycontainsthereduceactionforthesecondhalfofthe **SHIFTREDUCE.
*/ struct fts5yyStackEntry {
fts5YYACTIONTYPE stateno; /* The state-number, or reduce action in SHIFTREDUCE */
fts5YYCODETYPE major; /* The major token value. This is the code
** number for the token at this stack level */
fts5YYMINORTYPE minor; /* The user-supplied minor token value. This
** is the value of the token */
}; typedefstruct fts5yyStackEntry fts5yyStackEntry;
/* The state of the parser is completely contained in an instance of
** the following structure */ struct fts5yyParser {
fts5yyStackEntry *fts5yytos; /* Pointer to top element of the stack */ #ifdef fts5YYTRACKMAXSTACKDEPTH
int fts5yyhwm; /* High-water mark of the stack */ #endif #ifndef fts5YYNOERRORRECOVERY
int fts5yyerrcnt; /* Shifts left before out of the error */ #endif
sqlite3Fts5ParserARG_SDECL /* A place to hold %extra_argument */
sqlite3Fts5ParserCTX_SDECL /* A place to hold %extra_context */
fts5yyStackEntry *fts5yystackEnd; /* Last entry in the stack */
fts5yyStackEntry *fts5yystack; /* The parser stack */
fts5yyStackEntry fts5yystk0[fts5YYSTACKDEPTH]; /* Initial stack space */
}; typedefstruct fts5yyParser fts5yyParser;
#if !fts5YYGROWABLESTACK /* For builds that do no have a growable stack, fts5yyGrowStack always **returnsanerror.
*/ # define fts5yyGrowStack(X) 1 #endif
/* Datatype of the argument to the memory allocated passed as the **secondargumenttosqlite3Fts5ParserAlloc()below.Thiscanbechangedby **puttinganappropriate#defineinthe%includesectionoftheinput **grammar.
*/ #ifndef fts5YYMALLOCARGTYPE # define fts5YYMALLOCARGTYPE size_t #endif
/* Initialize a new parser that has already been allocated.
*/ staticvoid sqlite3Fts5ParserInit(void *fts5yypRawParser sqlite3Fts5ParserCTX_PDECL){
fts5yyParser *fts5yypParser = (fts5yyParser*)fts5yypRawParser;
sqlite3Fts5ParserCTX_STORE #ifdef fts5YYTRACKMAXSTACKDEPTH
fts5yypParser->fts5yyhwm = 0; #endif
fts5yypParser->fts5yystack = fts5yypParser->fts5yystk0;
fts5yypParser->fts5yystackEnd = &fts5yypParser->fts5yystack[fts5YYSTACKDEPTH-1]; #ifndef fts5YYNOERRORRECOVERY
fts5yypParser->fts5yyerrcnt = -1; #endif
fts5yypParser->fts5yytos = fts5yypParser->fts5yystack;
fts5yypParser->fts5yystack[0].stateno = 0;
fts5yypParser->fts5yystack[0].major = 0;
}
/* This array of booleans keeps track of the parser statement **coverage.Theelementfts5yycoverage[X][Y]issetwhentheparser **isinstateXandhasalookaheadtokenY.Inawell-tested **systems,everyelementofthismatrixshouldendupbeingset.
*/ #ifdefined(fts5YYCOVERAGE) staticunsigned char fts5yycoverage[fts5YYNSTATE][fts5YYNFTS5TOKEN]; #endif
/* **Findtheappropriateactionforaparsergiventheterminal **look-aheadtokeniLookAhead.
*/ static fts5YYACTIONTYPE fts5yy_find_shift_action(
fts5YYCODETYPE iLookAhead, /* The look-ahead token */
fts5YYACTIONTYPE stateno /* Current state number */
){
int i;
/* **Performareduceactionandtheshiftthatmustimmediately **followthereduce. ** **Thefts5yyLookaheadandfts5yyLookaheadTokenparametersprovidereduceactions **accesstothelookaheadtoken(ifany).Thefts5yyLookaheadwillbefts5YYNOCODE **ifthelookaheadtokenhasalreadybeenconsumed.Asthisprocedureis **onlycalledfromoneplace,optimizingcompilerswillin-lineit,which **meansthattheextraparametershavenoperformanceimpact.
*/ static fts5YYACTIONTYPE fts5yy_reduce(
fts5yyParser *fts5yypParser, /* The parser */ unsigned int fts5yyruleno, /* Number of the rule by which to reduce */
int fts5yyLookahead, /* Lookahead token, or fts5YYNOCODE if none */
sqlite3Fts5ParserFTS5TOKENTYPE fts5yyLookaheadToken /* Value of the lookahead token */
sqlite3Fts5ParserCTX_PDECL /* %extra_context */
){
int fts5yygoto; /* The next state */
fts5YYACTIONTYPE fts5yyact; /* The next action */
fts5yyStackEntry *fts5yymsp; /* The top of the parser's stack */
int fts5yysize; /* Amount to pop the stack */
sqlite3Fts5ParserARG_FETCH
(void)fts5yyLookahead;
(void)fts5yyLookaheadToken;
fts5yymsp = fts5yypParser->fts5yytos;
/* There are no SHIFTREDUCE actions on nonterminals because the table
** generator has simplified them to pure REDUCE actions. */
assert( !(fts5yyact>fts5YY_MAX_SHIFT && fts5yyact<=fts5YY_MAX_SHIFTREDUCE) );
/* It is not possible for a REDUCE to be followed by an error */
assert( fts5yyact!=fts5YY_ERROR_ACTION );
/* **Thefollowingcodeexecuteswhentheparsefails
*/ #ifndef fts5YYNOERRORRECOVERY staticvoid fts5yy_parse_failed(
fts5yyParser *fts5yypParser /* The parser */
){
sqlite3Fts5ParserARG_FETCH
sqlite3Fts5ParserCTX_FETCH #ifndef NDEBUG
if( fts5yyTraceFILE ){
fprintf(fts5yyTraceFILE,"%sFail!\n",fts5yyTracePrompt);
} #endif while( fts5yypParser->fts5yytos>fts5yypParser->fts5yystack ) fts5yy_pop_parser_stack(fts5yypParser); /* Here code is inserted which will be executed whenever the
** parser fails */ /************ Begin %parse_failure code ***************************************/ /************ End %parse_failure code *****************************************/
sqlite3Fts5ParserARG_STORE /* Suppress warning about unused %extra_argument variable */
sqlite3Fts5ParserCTX_STORE
} #endif/* fts5YYNOERRORRECOVERY */
/* **Thefollowingcodeexecuteswhenasyntaxerrorfirstoccurs.
*/ staticvoid fts5yy_syntax_error(
fts5yyParser *fts5yypParser, /* The parser */
int fts5yymajor, /* The major type of the error token */
sqlite3Fts5ParserFTS5TOKENTYPE fts5yyminor /* The minor type of the error token */
){
sqlite3Fts5ParserARG_FETCH
sqlite3Fts5ParserCTX_FETCH #define FTS5TOKEN fts5yyminor /************ Begin %syntax_error code ****************************************/ #line30"fts5parse.y"
UNUSED_PARAM(fts5yymajor); /* Silence a compiler warning */
sqlite3Fts5ParseError(
pParse, "fts5: syntax error near \"%.*s\"",FTS5TOKEN.n,FTS5TOKEN.p
); #line1324"fts5parse.c" /************ End %syntax_error code ******************************************/
sqlite3Fts5ParserARG_STORE /* Suppress warning about unused %extra_argument variable */
sqlite3Fts5ParserCTX_STORE
}
/* **Thefollowingisexecutedwhentheparseraccepts
*/ staticvoid fts5yy_accept(
fts5yyParser *fts5yypParser /* The parser */
){
sqlite3Fts5ParserARG_FETCH
sqlite3Fts5ParserCTX_FETCH #ifndef NDEBUG
if( fts5yyTraceFILE ){
fprintf(fts5yyTraceFILE,"%sAccept!\n",fts5yyTracePrompt);
} #endif #ifndef fts5YYNOERRORRECOVERY
fts5yypParser->fts5yyerrcnt = -1; #endif
assert( fts5yypParser->fts5yytos==fts5yypParser->fts5yystack ); /* Here code is inserted which will be executed whenever the
** parser accepts */ /*********** Begin %parse_accept code *****************************************/ /*********** End %parse_accept code *******************************************/
sqlite3Fts5ParserARG_STORE /* Suppress warning about unused %extra_argument variable */
sqlite3Fts5ParserCTX_STORE
}
/* The main parser program. **Thefirstargumentisapointertoastructureobtainedfrom **"sqlite3Fts5ParserAlloc"whichdescribesthecurrentstateoftheparser. **Thesecondargumentisthemajortokennumber.Thethirdis **theminortoken.Thefourthoptionalargumentiswhateverthe **userwants(andspecifiedinthegrammar)andisavailablefor **usebytheactionroutines. ** **Inputs: **<ul> **<li>Apointertotheparser(anopaquestructure.) **<li>Themajortokennumber. **<li>Theminortokennumber. **<li>Anoptionargumentofagrammar-specifiedtype. **</ul> ** **Outputs: **None.
*/ staticvoid sqlite3Fts5Parser( void *fts5yyp, /* The parser */
int fts5yymajor, /* The major token code number */
sqlite3Fts5ParserFTS5TOKENTYPE fts5yyminor /* The value for the token */
sqlite3Fts5ParserARG_PDECL /* Optional %extra_argument parameter */
){
fts5YYMINORTYPE fts5yyminorunion;
fts5YYACTIONTYPE fts5yyact; /* The parser action. */ #if !defined(fts5YYERRORSYMBOL) && !defined(fts5YYNOERRORRECOVERY)
int fts5yyendofinput; /* True if we are at the end of input */ #endif #ifdef fts5YYERRORSYMBOL
int fts5yyerrorhit = 0; /* True if fts5yymajor has invoked an error */ #endif
fts5yyParser *fts5yypParser = (fts5yyParser*)fts5yyp; /* The parser */
sqlite3Fts5ParserCTX_FETCH
sqlite3Fts5ParserARG_STORE
/* **Objectusedtoiteratethroughall"coalescedphraseinstances"in **asinglecolumnofthecurrentrow.Ifthephraseinstancesinthe **columnbeingconsidereddonotoverlap,thisobjectsimplyiterates **throughthem.Or,iftheydooverlap(shareoneormoretokensin **common),eachsetofoverlappinginstancesistreatedasasingle **match.Seedocumentationforthehighlight()auxiliaryfunctionfor **details. ** **Usageis: ** **for(rc=fts5CInstIterNext(pApi,pFts,iCol,&iter); **(rc==SQLITE_OK&&0==fts5CInstIterEof(&iter); **rc=fts5CInstIterNext(&iter) **){ **printf("instancestartsat%d,endsat%d\n",iter.iStart,iter.iEnd); **} **
*/ typedefstruct CInstIter CInstIter; struct CInstIter { const Fts5ExtensionApi *pApi; /* API offered by current FTS version */
Fts5Context *pFts; /* First arg to pass to pApi functions */
int iCol; /* Column to search */
int iInst; /* Next phrase instance index */
int nInst; /* Total number of phrase instances */
/* Output variables */
int iStart; /* First token in coalesced phrase instance */
int iEnd; /* Last token in coalesced phrase instance */
};
/* **Advancetheiteratortothenextcoalescedphraseinstance.Return **anSQLiteerrorcodeifanerroroccurs,orSQLITE_OKotherwise.
*/ static int fts5CInstIterNext(CInstIter *pIter){
int rc = SQLITE_OK;
pIter->iStart = -1;
pIter->iEnd = -1;
/************************************************************************* **Startofhighlight()implementation.
*/ typedefstruct HighlightContext HighlightContext; struct HighlightContext { /* Constant parameters to fts5HighlightCb() */
int iRangeStart; /* First token to include */
int iRangeEnd; /* If non-zero, last token to include */ const char *zOpen; /* Opening highlight */ const char *zClose; /* Closing highlight */ const char *zIn; /* Input text */
int nIn; /* Size of input text in bytes */
/* Variables modified by fts5HighlightCb() */
CInstIter iter; /* Coalesced Instance Iterator */
int iPos; /* Current token offset in zIn[] */
int iOff; /* Have copied up to this offset in zIn[] */
int bOpen; /* True if highlight is open */
char *zOut; /* Output value */
};
/* **AppendtexttotheHighlightContextoutputstring-p->zOut.Argument **zpointstoabuffercontainingnbytesoftexttoappend.Ifnis **negative,everythingupuntilthefirst'\0'isappendedtotheoutput. ** **If*pRcissettoanyvalueotherthanSQLITE_OKwhenthisfunctionis **called,itisano-op.Ifanerror(i.e.anOOMcondition)isencountered, ***pRcissettoanerrorcodebeforereturning.
*/ staticvoid fts5HighlightAppend(
int *pRc,
HighlightContext *p, const char *z, int n
){
if( *pRc==SQLITE_OK && z ){
if( n<0 ) n = (int)strlen(z);
p->zOut = sqlite3_mprintf("%z%.*s", p->zOut, n, z);
if( p->zOut==0 ) *pRc = SQLITE_NOMEM;
}
}
/* **Tokenizercallbackusedbyimplementationofhighlight()function.
*/ static int fts5HighlightCb( void *pContext, /* Pointer to HighlightContext object */
int tflags, /* Mask of FTS5_TOKEN_* flags */ const char *pToken, /* Buffer containing token */
int nToken, /* Size of token in bytes */
int iStartOff, /* Start byte offset of token */
int iEndOff /* End byte offset of token */
){
HighlightContext *p = (HighlightContext*)pContext;
int rc = SQLITE_OK;
int iPos;
/* If the parenthesis is open, and this token is not part of the current **phrase,andthestartingbyteoffsetofthistokenispastthepoint **thathascurrentlybeencopiedintotheoutputbuffer,closethe
** parenthesis. */
if( p->bOpen
&& (iPos<=p->iter.iStart || p->iter.iStart<0)
&& iStartOff>p->iOff
){
fts5HighlightAppend(&rc, p, p->zClose, -1);
p->bOpen = 0;
}
/* If this is the start of a new phrase, and the highlight is not open: ** ***copytextfromtheinputuptothestartofthephrase,and ***openthehighlight.
*/
if( iPos==p->iter.iStart && p->bOpen==0 ){
fts5HighlightAppend(&rc, p, &p->zIn[p->iOff], iStartOff - p->iOff);
fts5HighlightAppend(&rc, p, p->zOpen, -1);
p->iOff = iStartOff;
p->bOpen = 1;
}
/* **Implementationofhighlight()function.
*/ staticvoid fts5HighlightFunction( const Fts5ExtensionApi *pApi, /* API offered by current FTS version */
Fts5Context *pFts, /* First arg to pass to pApi functions */
sqlite3_context *pCtx, /* Context for returning result/error */
int nVal, /* Number of values in apVal[] array */
sqlite3_value **apVal /* Array of trailing arguments */
){
HighlightContext ctx;
int rc;
int iCol;
if( nVal!=3 ){ const char *zErr = "wrong number of arguments to function highlight()";
sqlite3_result_error(pCtx, zErr, -1); return;
}
/* **Contextobjectpassedtothefts5SentenceFinderCb()function.
*/ typedefstruct Fts5SFinder Fts5SFinder; struct Fts5SFinder {
int iPos; /* Current token position */
int nFirstAlloc; /* Allocated size of aFirst[] */
int nFirst; /* Number of entries in aFirst[] */
int *aFirst; /* Array of first token in each sentence */ const char *zDoc; /* Document being tokenized */
};
/* **AddanentrytotheFts5SFinder.aFirst[]array.Growthearrayif **necessary.ReturnSQLITE_OKifsuccessful,orSQLITE_NOMEMifan **erroroccurs.
*/ static int fts5SentenceFinderAdd(Fts5SFinder *p, int iAdd){
if( p->nFirstAlloc==p->nFirst ){
int nNew = p->nFirstAlloc ? p->nFirstAlloc*2 : 64;
int *aNew;
/* **ThisfunctionisanxTokenize()callbackusedbytheauxiliarysnippet() **function.Itsjobistoidentifytokensthatarethefirstinasentence. **Foreachsuchtoken,anentryisaddedtotheSFinder.aFirst[]array.
*/ static int fts5SentenceFinderCb( void *pContext, /* Pointer to HighlightContext object */
int tflags, /* Mask of FTS5_TOKEN_* flags */ const char *pToken, /* Buffer containing token */
int nToken, /* Size of token in bytes */
int iStartOff, /* Start offset of token */
int iEndOff /* End offset of token */
){
int rc = SQLITE_OK;
static int fts5SnippetScore( const Fts5ExtensionApi *pApi, /* API offered by current FTS version */
Fts5Context *pFts, /* First arg to pass to pApi functions */
int nDocsize, /* Size of column in tokens */ unsigned char *aSeen, /* Array with one element per query phrase */
int iCol, /* Column to score */
int iPos, /* Starting offset to score */
int nToken, /* Max tokens per snippet */
int *pnScore, /* OUT: Score */
int *piPos /* OUT: Adjusted offset */
){
int rc;
int i;
int ip = 0;
int ic = 0;
int iOff = 0;
int iFirst = -1;
int nInst;
int nScore = 0;
int iLast = 0;
sqlite3_int64 iEnd = (sqlite3_int64)iPos + nToken;
/* **Implementationofsnippet()function.
*/ staticvoid fts5SnippetFunction( const Fts5ExtensionApi *pApi, /* API offered by current FTS version */
Fts5Context *pFts, /* First arg to pass to pApi functions */
sqlite3_context *pCtx, /* Context for returning result/error */
int nVal, /* Number of values in apVal[] array */
sqlite3_value **apVal /* Array of trailing arguments */
){
HighlightContext ctx;
int rc = SQLITE_OK; /* Return code */
int iCol; /* 1st argument to snippet() */ const char *zEllips; /* 4th argument to snippet() */
int nToken; /* 5th argument to snippet() */
int nInst = 0; /* Number of instance matches this row */
int i; /* Used to iterate through instances */
int nPhrase; /* Number of phrases in query */ unsigned char *aSeen; /* Array of "seen instance" flags */
int iBestCol; /* Column containing best snippet */
int iBestStart = 0; /* First token of best snippet */
int nBestScore = 0; /* Score of best snippet */
int nColSize = 0; /* Total size of iBestCol in tokens */
Fts5SFinder sFinder; /* Used to find the beginnings of sentences */
int nCol;
if( nVal!=5 ){ const char *zErr = "wrong number of arguments to function snippet()";
sqlite3_result_error(pCtx, zErr, -1); return;
}
/* Advance iterator ctx.iter so that it points to the first coalesced
** phrase instance at or following position iBestStart. */ while( ctx.iter.iStart>=0 && ctx.iter.iStart<iBestStart && rc==SQLITE_OK ){
rc = fts5CInstIterNext(&ctx.iter);
}
/* **Thefirsttimethebm25()functioniscalledforaquery,aninstance **ofthefollowingstructureisallocatedandpopulated.
*/ typedefstruct Fts5Bm25Data Fts5Bm25Data; struct Fts5Bm25Data {
int nPhrase; /* Number of phrases in query */ double avgdl; /* Average number of tokens in each row */ double *aIDF; /* IDF for each phrase */ double *aFreq; /* Array used to calculate phrase freq. */
};
/* **Set*ppDatatopointtotheFts5Bm25Dataobjectforthecurrentquery. **Iftheobjecthasnotalreadybeenallocated,allocateandpopulateit **now.
*/ static int fts5Bm25GetData( const Fts5ExtensionApi *pApi,
Fts5Context *pFts,
Fts5Bm25Data **ppData /* OUT: bm25-data object for this query */
){
int rc = SQLITE_OK; /* Return code */
Fts5Bm25Data *p; /* Object to return */
p = (Fts5Bm25Data*)pApi->xGetAuxdata(pFts, 0);
if( p==0 ){
int nPhrase; /* Number of phrases in query */
sqlite3_int64 nRow = 0; /* Number of rows in table */
sqlite3_int64 nToken = 0; /* Number of tokens in table */
sqlite3_int64 nByte; /* Bytes of space to allocate */
int i;
/* **Implementationofbm25()function.
*/ staticvoid fts5Bm25Function( const Fts5ExtensionApi *pApi, /* API offered by current FTS version */
Fts5Context *pFts, /* First arg to pass to pApi functions */
sqlite3_context *pCtx, /* Context for returning result/error */
int nVal, /* Number of values in apVal[] array */
sqlite3_value **apVal /* Array of trailing arguments */
){ constdouble k1 = 1.2; /* Constant "k1" from BM25 formula */ constdouble b = 0.75; /* Constant "b" from BM25 formula */
int rc; /* Error code */ double score = 0.0; /* SQL function return value */
Fts5Bm25Data *pData; /* Values allocated/calculated once only */
int i; /* Iterator variable */
int nInst = 0; /* Value returned by xInstCount() */ double D = 0.0; /* Total number of tokens in row */ double *aFreq = 0; /* Array of phrase freq. for current row */
/* Calculate the phrase frequency (symbol "f(qi,D)" in the documentation)
** for each phrase in the query for the current row. */
rc = fts5Bm25GetData(pApi, pFts, &pData);
if( rc==SQLITE_OK ){
aFreq = pData->aFreq;
memset(aFreq, 0, sizeof(double) * pData->nPhrase);
rc = pApi->xInstCount(pFts, &nInst);
}
for(i=0; rc==SQLITE_OK && i<nInst; i++){
int ip; int ic; int io;
rc = pApi->xInst(pFts, i, &ip, &ic, &io);
if( rc==SQLITE_OK ){ double w = (nVal > ic) ? sqlite3_value_double(apVal[ic]) : 1.0;
aFreq[ip] += w;
}
}
/* Figure out the total size of the current row in tokens. */
if( rc==SQLITE_OK ){
int nTok;
rc = pApi->xColumnSize(pFts, -1, &nTok);
D = (double)nTok;
}
/* Determine and return the BM25 score for the current row. Or, if an
** error has occurred, throw an exception. */
if( rc==SQLITE_OK ){
for(i=0; i<pData->nPhrase; i++){
score += pData->aIDF[i] * (
( aFreq[i] * (k1 + 1.0) ) /
( aFreq[i] + k1 * (1 - b + b * D / pData->avgdl) )
);
}
sqlite3_result_double(pCtx, -1.0 * score);
}else{
sqlite3_result_error_code(pCtx, rc);
}
}
/* **Implementationoffts5_get_locale()function.
*/ staticvoid fts5GetLocaleFunction( const Fts5ExtensionApi *pApi, /* API offered by current FTS version */
Fts5Context *pFts, /* First arg to pass to pApi functions */
sqlite3_context *pCtx, /* Context for returning result/error */
int nVal, /* Number of values in apVal[] array */
sqlite3_value **apVal /* Array of trailing arguments */
){
int iCol = 0;
int eType = 0;
int rc = SQLITE_OK; const char *zLocale = 0;
int nLocale = 0;
/* xColumnLocale() must be available */
assert( pApi->iVersion>=4 );
if( nVal!=1 ){ const char *z = "wrong number of arguments to function fts5_get_locale()";
sqlite3_result_error(pCtx, z, -1); return;
}
static int sqlite3Fts5TermsetNew(Fts5Termset **pp){
int rc = SQLITE_OK;
*pp = sqlite3Fts5MallocZero(&rc, sizeof(Fts5Termset)); return rc;
}
static int sqlite3Fts5TermsetAdd(
Fts5Termset *p,
int iIdx, const char *pTerm, int nTerm,
int *pbPresent
){
int rc = SQLITE_OK;
*pbPresent = 0;
if( p ){
int i;
u32 hash = 13;
Fts5TermsetEntry *pEntry;
/* Calculate a hash value for this term. This is the same hash checksum **usedbythefts5_hash.cmodule.Thisisnotimportantforcorrect **operationofthemodule,butisnecessarytoensurethatsometests
** designed to produce hash table collisions really do work. */
for(i=nTerm-1; i>=0; i--){
hash = (hash << 3) ^ hash ^ pTerm[i];
}
hash = (hash << 3) ^ hash ^ iIdx;
hash = hash % ArraySize(p->apHash);
default: /* maybe a number */
if( *p=='+' || *p=='-' ) p++; while( fts5_isdigit(*p) ) p++;
/* At this point, if the literal was an integer, the parse is **finished.Or,ifitisafloatingpointvalue,itmaycontinue
** with either a decimal point or an 'E' character. */
if( *p=='.' && fts5_isdigit(p[1]) ){
p += 2; while( fts5_isdigit(*p) ) p++;
}
if( p==pIn ) p = 0;
break;
}
return p;
}
/* **Thefirstcharacterofthestringpointedtobyargumentzisguaranteed **tobeanopen-quotecharacter(seefunctionfts5_isopenquote()). ** **Thisfunctionsearchesforthecorrespondingclose-quotecharacterwithin **thestringand,iffound,dequotesthestringinplaceandaddsanew **nul-terminatorbyte. ** **Iftheclose-quoteisfound,thevaluereturnedisthebyteoffsetof **thecharacterimmediatelyfollowingit.Or,iftheclose-quoteisnot **found,-1isreturned.If-1isreturned,thebufferisleftinan **undefinedstate.
*/ static int fts5Dequote(char *z){
char q;
int iIn = 1;
int iOut = 0;
q = z[0];
/* Set stack variable q to the close-quote character */
assert( q=='[' || q=='\'' || q=='"' || q=='`' );
if( q=='[' ) q = ']';
while( z[iIn] ){
if( z[iIn]==q ){
if( z[iIn+1]!=q ){ /* Character iIn was the close quote. */
iIn++; break;
}else{ /* Character iIn and iIn+1 form an escaped quote character. Skip **theinputcursorpastbothandcopyasinglequotecharacter
** to the output buffer. */
iIn += 2;
z[iOut++] = q;
}
}else{
z[iOut++] = z[iIn++];
}
}
/* We only allow contentless_delete=1 if the table is indeed contentless. */
if( rc==SQLITE_OK
&& pRet->bContentlessDelete
&& pRet->eContent!=FTS5_CONTENT_NONE
){
*pzErr = sqlite3_mprintf( "contentless_delete=1 requires a contentless table"
);
rc = SQLITE_ERROR;
}
/* We only allow contentless_delete=1 if columnsize=0 is not present. ** **Thisrestrictionmayberemovedatsomepoint.
*/
if( rc==SQLITE_OK && pRet->bContentlessDelete && pRet->bColumnsize==0 ){
*pzErr = sqlite3_mprintf( "contentless_delete=1 is incompatible with columnsize=0"
);
rc = SQLITE_ERROR;
}
/* We only allow contentless_unindexed=1 if the table is actually a **contentlessone.
*/
if( rc==SQLITE_OK
&& pRet->bContentlessUnindexed
&& pRet->eContent!=FTS5_CONTENT_NONE
){
*pzErr = sqlite3_mprintf( "contentless_unindexed=1 requires a contentless table"
);
rc = SQLITE_ERROR;
}
/* If no zContent option was specified, fill in the default values. */
if( rc==SQLITE_OK && pRet->zContent==0 ){ const char *zTail = 0;
assert( pRet->eContent==FTS5_CONTENT_NORMAL
|| pRet->eContent==FTS5_CONTENT_NONE
);
if( pRet->eContent==FTS5_CONTENT_NORMAL ){
zTail = "content";
}else if( bUnindexed && pRet->bContentlessUnindexed ){
pRet->eContent = FTS5_CONTENT_UNINDEXED;
zTail = "content";
}else if( pRet->bColumnsize ){
zTail = "docsize";
}
struct Fts5Expr {
Fts5Index *pIndex;
Fts5Config *pConfig;
Fts5ExprNode *pRoot;
int bDesc; /* Iterate in descending rowid order */
int nPhrase; /* Number of phrases in expression */
Fts5ExprPhrase **apExprPhrase; /* Pointers to phrase objects */
};
/* **eType: **Expressionnodetype.Usuallyoneof: ** **FTS5_AND(nChild,apChildvalid) **FTS5_OR(nChild,apChildvalid) **FTS5_NOT(nChild,apChildvalid) **FTS5_STRING(pNearvalid) **FTS5_TERM(pNearvalid) ** **AnexpressionnodewitheType==0mayalsoexist.Italwaysmatcheszero **rows.Thisiscreatedwhenaphrasecontainingnotokensisparsed. **e.g."". ** **iHeight: **Distancefromthisnodetofurthestleaf.Thisisalways0fornodes **oftypeFTS5_STRINGandFTS5_TERM.Forallothernodesitisone **greaterthanthelargestchildvalue.
*/ struct Fts5ExprNode {
int eType; /* Node type */
int bEof; /* True at EOF */
int bNomatch; /* True if entry is not a match */
int iHeight; /* Distance to tree leaf nodes */
/* Next method for this node. */
int (*xNext)(Fts5Expr*, Fts5ExprNode*, int, i64);
i64 iRowid; /* Current rowid */
Fts5ExprNearset *pNear; /* For FTS5_STRING - cluster of phrases */
/* Child nodes. For a NOT node, this array always contains 2 entries. For
** AND or OR nodes, it contains 2 or more entries. */
int nChild; /* Number of child nodes */
Fts5ExprNode *apChild[FLEXARRAY]; /* Array of child nodes */
};
/* Size (in bytes) of an Fts5ExprNode object that holds up to N children */ #define SZ_FTS5EXPRNODE(N) \
(offsetof(Fts5ExprNode,apChild) + (N)*sizeof(Fts5ExprNode*))
/* **Aninstanceofthefollowingstructurerepresentsasinglesearchterm **ortermprefix.
*/ struct Fts5ExprTerm {
u8 bPrefix; /* True for a prefix term */
u8 bFirst; /* True if token must be first in column */
char *pTerm; /* Term data */
int nQueryTerm; /* Effective size of term in bytes */
int nFullTerm; /* Size of term in bytes incl. tokendata */
Fts5IndexIter *pIter; /* Iterator for this term */
Fts5ExprTerm *pSynonym; /* Pointer to first in list of synonyms */
};
/* **Aphrase.Oneormoretermsthatmustappearinacontiguoussequence **withinadocumentforittomatch.
*/ struct Fts5ExprPhrase {
Fts5ExprNode *pNode; /* FTS5_STRING node this phrase is part of */
Fts5Buffer poslist; /* Current position list */
int nTerm; /* Number of entries in aTerm[] */
Fts5ExprTerm aTerm[FLEXARRAY]; /* Terms that make up this phrase */
};
/* Size (in bytes) of an Fts5ExprPhrase object that holds up to N terms */ #define SZ_FTS5EXPRPHRASE(N) \
(offsetof(Fts5ExprPhrase,aTerm) + (N)*sizeof(Fts5ExprTerm))
/* **Oneormorephrasesthatmustappearwithinacertaintokendistanceof **eachotherwithineachmatchingdocument.
*/ struct Fts5ExprNearset {
int nNear; /* NEAR parameter */
Fts5Colset *pColset; /* Columns to search (NULL -> all columns) */
int nPhrase; /* Number of entries in aPhrase[] array */
Fts5ExprPhrase *apPhrase[FLEXARRAY]; /* Array of phrase pointers */
};
/* Size (in bytes) of an Fts5ExprNearset object covering up to N phrases */ #define SZ_FTS5EXPRNEARSET(N) \
(offsetof(Fts5ExprNearset,apPhrase)+(N)*sizeof(Fts5ExprPhrase*))
/* **Parsecontext.
*/ struct Fts5Parse {
Fts5Config *pConfig;
char *zErr;
int rc;
int nPhrase; /* Size of apPhrase array */
Fts5ExprPhrase **apPhrase; /* Array of all phrases */
Fts5ExprNode *pExpr; /* Result of a successful parse */
int bPhraseToAnd; /* Convert "a+b" to "a AND b" */
};
/* If the LHS of the MATCH expression was a user column, apply the
** implicit column-filter. */
if( sParse.rc==SQLITE_OK && iCol<pConfig->nCol ){
int n = SZ_FTS5COLSET(1);
Fts5Colset *pColset = (Fts5Colset*)sqlite3Fts5MallocZero(&sParse.rc, n);
if( pColset ){
pColset->nCol = 1;
pColset->aiCol[0] = iCol;
sqlite3Fts5ParseSetColset(&sParse, sParse.pExpr, pColset);
}
}
/* **ArgumentpTermmustbeasynonymiterator.
*/ static int fts5ExprSynonymList(
Fts5ExprTerm *pTerm,
i64 iRowid,
Fts5Buffer *pBuf, /* Use this buffer for space if required */
u8 **pa, int *pn
){
Fts5PoslistReader aStatic[4];
Fts5PoslistReader *aIter = aStatic;
int nIter = 0;
int nAlloc = 4;
int rc = SQLITE_OK;
Fts5ExprTerm *p;
/* **AllindividualtermiteratorsinpPhraseareguaranteedtobevalidand **pointingtothesamerowidwhenthisfunctioniscalled.Thisfunction **checksifthecurrentrowidreallyisamatch,andifsopopulates **thepPhrase->poslistbufferaccordingly.Outputparameter*pbMatch **issettotrueifthisisreallyamatch,orfalseotherwise. ** **SQLITE_OKisreturnedifanerroroccurs,oranSQLiteerrorcode **otherwise.Itisnotconsideredanerrorcodeifthecurrentrowidis **notamatch.
*/ static int fts5ExprPhraseIsMatch(
Fts5ExprNode *pNode, /* Node pPhrase belongs to */
Fts5ExprPhrase *pPhrase, /* Phrase object to initialize */
int *pbMatch /* OUT: Set to true if really a match */
){
Fts5PoslistWriter writer = {0};
Fts5PoslistReader aStatic[4];
Fts5PoslistReader *aIter = aStatic;
int i;
int rc = SQLITE_OK;
int bFirst = pPhrase->aTerm[0].bFirst;
fts5BufferZero(&pPhrase->poslist);
/* If the aStatic[] array is not large enough, allocate a large array
** using sqlite3_malloc(). This approach could be improved upon. */
if( pPhrase->nTerm>ArraySize(aStatic) ){
sqlite3_int64 nByte = sizeof(Fts5PoslistReader) * pPhrase->nTerm;
aIter = (Fts5PoslistReader*)sqlite3_malloc64(nByte);
if( !aIter ) return SQLITE_NOMEM;
}
memset(aIter, 0, sizeof(Fts5PoslistReader) * pPhrase->nTerm);
/* Initialize a term iterator for each term in the phrase */
for(i=0; i<pPhrase->nTerm; i++){
Fts5ExprTerm *pTerm = &pPhrase->aTerm[i];
int n = 0;
int bFlag = 0;
u8 *a = 0;
if( pTerm->pSynonym ){
Fts5Buffer buf = {0, 0, 0};
rc = fts5ExprSynonymList(pTerm, pNode->iRowid, &buf, &a, &n);
if( rc ){
sqlite3_free(a);
goto ismatch_out;
}
if( a==buf.p ) bFlag = 1;
}else{
a = (u8*)pTerm->pIter->pData;
n = pTerm->pIter->nData;
}
sqlite3Fts5PoslistReaderInit(a, n, &aIter[i]);
aIter[i].bFlag = (u8)bFlag;
if( aIter[i].bEof ) goto ismatch_out;
}
typedefstruct Fts5LookaheadReader Fts5LookaheadReader; struct Fts5LookaheadReader { const u8 *a; /* Buffer containing position list */
int n; /* Size of buffer a[] in bytes */
int i; /* Current offset in position list */
i64 iPos; /* Current position */
i64 iLookahead; /* Next position */
};
static int fts5LookaheadReaderInit( const u8 *a, int n, /* Buffer to read position list from */
Fts5LookaheadReader *p /* Iterator object to initialize */
){
memset(p, 0, sizeof(Fts5LookaheadReader));
p->a = a;
p->n = n;
fts5LookaheadReaderNext(p); return fts5LookaheadReaderNext(p);
}
/* If the aStatic[] array is not large enough, allocate a large array
** using sqlite3_malloc(). This approach could be improved upon. */
if( pNear->nPhrase>ArraySize(aStatic) ){
sqlite3_int64 nByte = sizeof(Fts5NearTrimmer) * pNear->nPhrase;
a = (Fts5NearTrimmer*)sqlite3Fts5MallocZero(&rc, nByte);
}else{
memset(aStatic, 0, sizeof(aStatic));
}
if( rc!=SQLITE_OK ){
*pRc = rc; return0;
}
/* Initialize a lookahead iterator for each phrase. After passing the **bufferandbuffersizetothelookaside-readerinitfunction,zero **thephraseposlistbuffer.Thenewposlistforthephrase(containing **thesameentriesastheoriginalwithsomeentriesremovedonaccount **oftheNEARconstraint)iswrittenovertheoriginalevenasitis **beingread.Thisissafeastheentriesforthenewposlistarea **subsetoftheold,soitisnotpossiblefordatayettobereadto
** be overwritten. */
for(i=0; i<pNear->nPhrase; i++){
Fts5Buffer *pPoslist = &apPhrase[i]->poslist;
fts5LookaheadReaderInit(pPoslist->p, pPoslist->n, &a[i].reader);
pPoslist->n = 0;
a[i].pOut = pPoslist;
}
while( 1 ){
int iAdv;
i64 iMin;
i64 iMax;
/* This block advances the phrase iterators until they point to a set of
** entries that together comprise a match. */
iMax = a[0].reader.iPos; do {
bMatch = 1;
for(i=0; i<pNear->nPhrase; i++){
Fts5LookaheadReader *pPos = &a[i].reader;
iMin = iMax - pNear->apPhrase[i]->nTerm - pNear->nNear;
if( pPos->iPos<iMin || pPos->iPos>iMax ){
bMatch = 0; while( pPos->iPos<iMin ){
if( fts5LookaheadReaderNext(pPos) ) goto ismatch_out;
}
if( pPos->iPos>iMax ) iMax = pPos->iPos;
}
}
}while( bMatch==0 );
/* Add an entry to each output position list */
for(i=0; i<pNear->nPhrase; i++){
i64 iPos = a[i].reader.iPos;
Fts5PoslistWriter *pWriter = &a[i].writer;
if( a[i].pOut->n==0 || iPos!=pWriter->iPrev ){
sqlite3Fts5PoslistWriterAppend(a[i].pOut, pWriter, iPos);
}
}
/* **AdvanceiteratorpIteruntilitpointstoavalueequaltoorlaster **thantheinitialvalueof*piLast.Ifthismeanstheiteratorpoints **toavaluelasterthan*piLast,update*piLasttothenewlastestvalue. ** **IftheiteratorreachesEOF,set*pbEoftotruebeforereturning.If **anerroroccurs,set*pRctoanerrorcode.Ifeither*pbEofor*pRc **areset,returnanon-zerovalue.Otherwise,returnzero.
*/ static int fts5ExprAdvanceto(
Fts5IndexIter *pIter, /* Iterator to advance */
int bDesc, /* True if iterator is "rowid DESC" */
i64 *piLast, /* IN/OUT: Lastest rowid seen so far */
int *pRc, /* OUT: Error code */
int *pbEof /* OUT: Set to true if EOF */
){
i64 iLast = *piLast;
i64 iRowid;
static int fts5ExprSynonymAdvanceto(
Fts5ExprTerm *pTerm, /* Term iterator to advance */
int bDesc, /* True if iterator is "rowid DESC" */
i64 *piLast, /* IN/OUT: Lastest rowid seen so far */
int *pRc /* OUT: Error code */
){
int rc = SQLITE_OK;
i64 iLast = *piLast;
Fts5ExprTerm *p;
int bEof = 0;
static int fts5ExprNearTest(
int *pRc,
Fts5Expr *pExpr, /* Expression that pNear is a part of */
Fts5ExprNode *pNode /* The "NEAR" node (FTS5_STRING) */
){
Fts5ExprNearset *pNear = pNode->pNear;
int rc = *pRc;
/* **AllindividualtermiteratorsinpNearareguaranteedtobevalidwhen **thisfunctioniscalled.Thisfunctionchecksifalltermiterators **pointtothesamerowid,andifnot,advancesthemuntiltheydo. **IfanEOFisreachedbeforethishappens,*pbEofissettotruebefore **returning. ** **SQLITE_OKisreturnedifanerroroccurs,oranSQLiteerrorcode **otherwise.Itisnotconsideredanerrorcodeifaniteratorreaches **EOF.
*/ static int fts5ExprNodeTest_STRING(
Fts5Expr *pExpr, /* Expression pPhrase belongs to */
Fts5ExprNode *pNode
){
Fts5ExprNearset *pNear = pNode->pNear;
Fts5ExprPhrase *pLeft = pNear->apPhrase[0];
int rc = SQLITE_OK;
i64 iLast; /* Lastest rowid any iterator points to */
int i, j; /* Phrase and token index, respectively */
int bMatch; /* True if all terms are at the same rowid */ const int bDesc = pExpr->bDesc;
/* Check that this node should not be FTS5_TERM */
assert( pNear->nPhrase>1
|| pNear->apPhrase[0]->nTerm>1
|| pNear->apPhrase[0]->aTerm[0].pSynonym
|| pNear->apPhrase[0]->aTerm[0].bFirst
);
/* Initialize iLast, the "lastest" rowid any iterator points to. If the **iteratorskipsthroughrowidsinthedefaultascendingorder,thismeans **themaximumrowid.Or,iftheiteratoris"ORDERBYrowidDESC",thenit
** means the minimum rowid. */
if( pLeft->aTerm[0].pSynonym ){
iLast = fts5ExprSynonymRowid(&pLeft->aTerm[0], bDesc, 0);
}else{
iLast = pLeft->aTerm[0].pIter->iRowid;
}
/* Find the firstest rowid any synonym points to. */
i64 iRowid = fts5ExprSynonymRowid(pTerm, pExpr->bDesc, 0);
/* Advance each iterator that currently points to iRowid. Or, if iFrom
** is valid - each iterator that points to a rowid before iFrom. */
for(p=pTerm; p; p=p->pSynonym){
if( sqlite3Fts5IterEof(p->pIter)==0 ){
i64 ii = p->pIter->iRowid;
if( ii==iRowid
|| (bFromValid && ii!=iFrom && (ii>iFrom)==pExpr->bDesc)
){
if( bFromValid ){
rc = sqlite3Fts5IterNextFrom(p->pIter, iFrom);
}else{
rc = sqlite3Fts5IterNext(p->pIter);
}
if( rc!=SQLITE_OK ) break;
if( sqlite3Fts5IterEof(p->pIter)==0 ){
bEof = 0;
}
}else{
bEof = 0;
}
}
}
/* Set the EOF flag if either all synonym iterators are at EOF or an
** error has occurred. */
pNode->bEof = (rc || bEof);
}else{
Fts5IndexIter *pIter = pTerm->pIter;
static int fts5ExprNodeTest_TERM(
Fts5Expr *pExpr, /* Expression that pNear is a part of */
Fts5ExprNode *pNode /* The "NEAR" node (FTS5_TERM) */
){ /* As this "NEAR" object is actually a single phrase that consists **ofasingletermonly,grabpointersintotheposlistmanagedbythe **fts5_index.citeratorobject.Thisismuchfasterthansynthesizing **anewposlistthewaywehavetoformorecomplicatedphraseorNEAR
** expressions. */
Fts5ExprPhrase *pPhrase = pNode->pNear->apPhrase[0];
Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
staticvoid fts5ExprNodeTest_OR(
Fts5Expr *pExpr, /* Expression of which pNode is a part */
Fts5ExprNode *pNode /* Expression node to test */
){
Fts5ExprNode *pNext = pNode->apChild[0];
int i;
/* **ArgumentpNodeisanFTS5_ANDnode.
*/ static int fts5ExprNodeTest_AND(
Fts5Expr *pExpr, /* Expression pPhrase belongs to */
Fts5ExprNode *pAnd /* FTS5_AND node to advance */
){
int iChild;
i64 iLast = pAnd->iRowid;
int rc = SQLITE_OK;
int bMatch;
assert( pAnd->bEof==0 ); do {
pAnd->bNomatch = 0;
bMatch = 1;
for(iChild=0; iChild<pAnd->nChild; iChild++){
Fts5ExprNode *pChild = pAnd->apChild[iChild];
int cmp = fts5RowidCmp(pExpr, iLast, pChild->iRowid);
if( cmp>0 ){ /* Advance pChild until it points to iLast or laster */
rc = fts5ExprNodeNext(pExpr, pChild, 1, iLast);
if( rc!=SQLITE_OK ){
pAnd->bNomatch = 0; return rc;
}
}
/* If the child node is now at EOF, so is the parent AND node. Otherwise, **thechildnodeisguaranteedtohaveadvancedatleastasfaras **rowidiLast.SoifitisnotatexactlyiLast,pChild->iRowidisthe
** new lastest rowid seen so far. */
assert( pChild->bEof || fts5RowidCmp(pExpr, iLast, pChild->iRowid)<=0 );
if( pChild->bEof ){
fts5ExprSetEof(pAnd);
bMatch = 1; break;
}else if( iLast!=pChild->iRowid ){
bMatch = 0;
iLast = pChild->iRowid;
}
/* **IfpNodecurrentlypointstoamatch,thisfunctionreturnsSQLITE_OK **withoutmodifyingit.Otherwise,pNodeisadvanceduntilitdoespoint **toamatchorEOFisreached.
*/ static int fts5ExprNodeTest(
Fts5Expr *pExpr, /* Expression of which pNode is a part */
Fts5ExprNode *pNode /* Expression node to test */
){
int rc = SQLITE_OK;
if( pNode->bEof==0 ){ switch( pNode->eType ){
case FTS5_STRING: {
rc = fts5ExprNodeTest_STRING(pExpr, pNode); break;
}
case FTS5_TERM: {
rc = fts5ExprNodeTest_TERM(pExpr, pNode); break;
}
case FTS5_AND: {
rc = fts5ExprNodeTest_AND(pExpr, pNode); break;
}
case FTS5_OR: {
fts5ExprNodeTest_OR(pExpr, pNode); break;
}
/* If not at EOF but the current rowid occurs earlier than iFirst in
** the iteration order, move to document iFirst or later. */
if( rc==SQLITE_OK
&& 0==pRoot->bEof
&& fts5RowidCmp(p, pRoot->iRowid, iFirst)<0
){
rc = fts5ExprNodeNext(p, pRoot, 1, iFirst);
}
/* If the iterator is not at a real match, skip forward until it is. */ while( pRoot->bNomatch && rc==SQLITE_OK ){
assert( pRoot->bEof==0 );
rc = fts5ExprNodeNext(p, pRoot, 0, 0);
}
if( fts5RowidCmp(p, pRoot->iRowid, iLast)>0 ){
pRoot->bEof = 1;
} return rc;
}
/* **CallbackfortokenizingtermsusedbyParseTerm().
*/ static int fts5ParseTokenize( void *pContext, /* Pointer to Fts5InsertCtx object */
int tflags, /* Mask of FTS5_TOKEN_* flags */ const char *pToken, /* Buffer containing token */
int nToken, /* Size of token in bytes */
int iUnused1, /* Start offset of token */
int iUnused2 /* End offset of token */
){
int rc = SQLITE_OK; const int SZALLOC = 8;
TokenCtx *pCtx = (TokenCtx*)pContext;
Fts5ExprPhrase *pPhrase = pCtx->pPhrase;
UNUSED_PARAM2(iUnused1, iUnused2);
/* If an error has already occurred, this is a no-op */
if( pCtx->rc!=SQLITE_OK ) return pCtx->rc;
if( nToken>FTS5_MAX_TOKEN_SIZE ) nToken = FTS5_MAX_TOKEN_SIZE;
if( sCtx.pPhrase==0 ){ /* This happens when parsing a token or quoted phrase that contains
** no token characters at all. (e.g ... MATCH '""'). */
sCtx.pPhrase = sqlite3Fts5MallocZero(&pParse->rc, SZ_FTS5EXPRPHRASE(1));
}else if( sCtx.pPhrase->nTerm ){
sCtx.pPhrase->aTerm[sCtx.pPhrase->nTerm-1].bPrefix = (u8)bPrefix;
}
assert( pParse->apPhrase!=0 );
pParse->apPhrase[pParse->nPhrase-1] = sCtx.pPhrase;
}
#ifndef NDEBUG /* Check that the array is in order and contains no duplicate entries. */
for(i=1; i<pNew->nCol; i++) assert( pNew->aiCol[i]>pNew->aiCol[i-1] ); #endif
}
/* **RemovefromcolsetpColsetanycolumnsthatarenotalsoincolsetpMerge.
*/ staticvoid fts5MergeColset(Fts5Colset *pColset, Fts5Colset *pMerge){
int iIn = 0; /* Next input in pColset */
int iMerge = 0; /* Next input in pMerge */
int iOut = 0; /* Next output slot in pColset */
/* **Allocateandreturnanewexpressionobject.Ifanythinggoeswrong(i.e. **OOMerror),leaveanerrorcodeinpParseandreturnNULL.
*/ static Fts5ExprNode *sqlite3Fts5ParseNode(
Fts5Parse *pParse, /* Parse context */
int eType, /* FTS5_STRING, AND, OR or NOT */
Fts5ExprNode *pLeft, /* Left hand child expression */
Fts5ExprNode *pRight, /* Right hand child expression */
Fts5ExprNearset *pNear /* For STRING expressions, the near cluster */
){
Fts5ExprNode *pRet = 0;
if( pParse->rc==SQLITE_OK ){
int nChild = 0; /* Number of children of returned node */
sqlite3_int64 nByte; /* Bytes of space to allocate for this node */
/* **TODO:Makethismoreefficient!
*/ static int fts5ExprColsetTest(Fts5Colset *pColset, int iCol){
int i;
for(i=0; i<pColset->nCol; i++){
if( pColset->aiCol[i]==iCol ) return1;
} return0;
}
/* **pTokenisabuffernTokenbytesinsizethatmayormaynotcontain **anembedded0x00byte.Ifitdoes,returnthenumberofbytesin **thebufferbeforethe0x00.Ifitdoesnot,returnnToken.
*/ static int fts5QueryTerm(const char *pToken, int nToken){
int ii;
for(ii=0; ii<nToken && pToken[ii]; ii++){} return ii;
}
static int fts5ExprPopulatePoslistsCb( void *pCtx, /* Copy of 2nd argument to xTokenize() */
int tflags, /* Mask of FTS5_TOKEN_* flags */ const char *pToken, /* Pointer to buffer containing token */
int nToken, /* Size of token in bytes */
int iUnused1, /* Byte offset of token within input text */
int iUnused2 /* Byte offset of end of token within input text */
){
Fts5ExprCtx *p = (Fts5ExprCtx*)pCtx;
Fts5Expr *pExpr = p->pExpr;
int i;
int nQuery = nToken;
i64 iRowid = pExpr->pRoot->iRowid;
struct Fts5Hash {
int eDetail; /* Copy of Fts5Config.eDetail */
int *pnByte; /* Pointer to bytes counter */
int nEntry; /* Number of entries currently in hash */
int nSlot; /* Size of aSlot[] array */
Fts5HashEntry *pScan; /* Current ordered scan item */
Fts5HashEntry **aSlot; /* Array of hash slots */
};
/* **Eachentryinthehashtableisrepresentedbyanobjectofthe **followingtype.Eachobject,itskey,anditscurrentdataarestored **inasinglememoryallocation.Thekeyimmediatelyfollowstheobject **inmemory.Thepositionlistdataimmediatelyfollowsthekeydata **inmemory. ** **ThekeyisFts5HashEntry.nKeybytesinsize.Itconsistsofasingle **byteidentifyingtheindex(eitherthemaintermindexoraprefix-index), **followedbythetermdata.Forexample:"0token".Thereisno **nul-terminator-inthiscasenKey=6. ** **Thedatathatfollowsthekeyisinasimilar,butnotidenticalformat **tothedoclistdatastoredinthedatabase.Itis: ** ***Rowid,asavarint ***Positionlist,without0x00terminator. ***Sizeofpreviouspositionlistandrowid,asa4byte **big-endianinteger. ** **iRowidOff: **Offsetoflastrowidwrittentodataarea.Relativetofirstbyteof **structure. ** **nData: **BytesofdatawrittensinceiRowidOff.
*/ struct Fts5HashEntry {
Fts5HashEntry *pHashNext; /* Next hash entry with same hash-key */
Fts5HashEntry *pScanNext; /* Next entry in sorted order */
int nAlloc; /* Total size of allocation */
int iSzPoslist; /* Offset of space for 4-byte poslist size */
int nData; /* Total bytes of data (incl. structure) */
int nKey; /* Length of key in bytes */
u8 bDel; /* Set delete-flag @ iSzPoslist */
u8 bContent; /* Set content-flag (detail=none mode) */
i16 iCol; /* Column of last value written */
int iPos; /* Position of last value written */
i64 iRowid; /* Rowid of last value written */
};
staticunsigned int fts5HashKey(int nSlot, const u8 *p, int n){
int i; unsigned int h = 13;
for(i=n-1; i>=0; i--){
h = (h << 3) ^ h ^ p[i];
} return (h % nSlot);
}
staticunsigned int fts5HashKey2(int nSlot, u8 b, const u8 *p, int n){
int i; unsigned int h = 13;
for(i=n-1; i>=0; i--){
h = (h << 3) ^ h ^ p[i];
}
h = (h << 3) ^ h ^ b; return (h % nSlot);
}
/* **Resizethehashtablebydoublingthenumberofslots.
*/ static int fts5HashResize(Fts5Hash *pHash){
int nNew = pHash->nSlot*2;
int i;
Fts5HashEntry **apNew;
Fts5HashEntry **apOld = pHash->aSlot;
/* **Addanentrytothein-memoryhashtable.Thekeyistheconcatenation **ofbByteand(pToken/nToken).Thevalueis(iRowid/iCol/iPos). ** **(bByte||pToken)->(iRowid,iCol,iPos) ** **Or,ifiColisnegative,thenthevalueisadeletemarker.
*/ static int sqlite3Fts5HashWrite(
Fts5Hash *pHash,
i64 iRowid, /* Rowid for this entry */
int iCol, /* Column token appears in (-ve -> delete) */
int iPos, /* Position of token within column */
char bByte, /* First byte of token */ const char *pToken, int nToken /* Token to add or remove to or from index */
){ unsigned int iHash;
Fts5HashEntry *p;
u8 *pPtr;
int nIncr = 0; /* Amount to increment (*pHash->pnByte) by */
int bNew; /* If non-delete entry should be written */
/* If an existing hash entry cannot be found, create a new one. */
if( p==0 ){ /* Figure out how much space to allocate */
char *zKey;
sqlite3_int64 nByte = sizeof(Fts5HashEntry) + (nToken+1) + 1 + 64;
if( nByte<128 ) nByte = 128;
/* Grow the Fts5Hash.aSlot[] array if necessary. */
if( (pHash->nEntry*2)>=pHash->nSlot ){
int rc = fts5HashResize(pHash);
if( rc!=SQLITE_OK ) return rc;
iHash = fts5HashKey2(pHash->nSlot, (u8)bByte, (const u8*)pToken, nToken);
}
/* Allocate new Fts5HashEntry and add it to the hash table. */
p = (Fts5HashEntry*)sqlite3_malloc64(nByte);
if( !p ) return SQLITE_NOMEM;
memset(p, 0, sizeof(Fts5HashEntry));
p->nAlloc = (int)nByte;
zKey = fts5EntryKey(p);
zKey[0] = bByte;
memcpy(&zKey[1], pToken, nToken);
assert( iHash==fts5HashKey(pHash->nSlot, (u8*)zKey, nToken+1) );
p->nKey = nToken+1;
zKey[nToken+1] = '\0';
p->nData = nToken+1 + sizeof(Fts5HashEntry);
p->pHashNext = pHash->aSlot[iHash];
pHash->aSlot[iHash] = p;
pHash->nEntry++;
/* Add the first rowid field to the hash-entry */
p->nData += sqlite3Fts5PutVarint(&((u8*)p)[p->nData], iRowid);
p->iRowid = iRowid;
/* If this is a new rowid, append the 4-byte size field for the previous
** entry, and the new rowid for this entry. */
if( iRowid!=p->iRowid ){
u64 iDiff = (u64)iRowid - (u64)p->iRowid;
fts5HashAddPoslistSize(pHash, p, 0);
p->nData += sqlite3Fts5PutVarint(&pPtr[p->nData], iDiff);
p->iRowid = iRowid;
bNew = 1;
p->iSzPoslist = p->nData;
if( pHash->eDetail!=FTS5_DETAIL_NONE ){
p->nData += 1;
p->iCol = (pHash->eDetail==FTS5_DETAIL_FULL ? 0 : -1);
p->iPos = 0;
}
}
/* Append the new position offset, if necessary */
if( bNew ){
p->nData += sqlite3Fts5PutVarint(&pPtr[p->nData], iPos - p->iPos + 2);
p->iPos = iPos;
}
}
}else{ /* This is a delete. Set the delete flag. */
p->bDel = 1;
}
/* **Rowidsfortheaveragesandstructurerecordsinthe%_datatable.
*/ #define FTS5_AVERAGES_ROWID 1/* Rowid used for the averages record */ #define FTS5_STRUCTURE_ROWID 10/* The structure record */
/* **Macrosdeterminingtherowidsusedbysegmentleavesanddlidxleaves **andnodes.Allnodesandleavesarestoredinthe%_datatablewithlarge **positiverowids. ** **Eachsegmenthasauniquenon-zero16-bitid. ** **Therowidforeachsegmentleafisfoundbypassingthesegmentidand **theleafpagenumbertotheFTS5_SEGMENT_ROWIDmacro.Leavesarenumbered **sequentiallystartingfrom1.
*/ #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 */
struct Fts5Data {
u8 *p; /* Pointer to buffer containing record */
int nn; /* Size of record in bytes */
int szLeaf; /* Size of leaf without page-index */
};
/* **Oneobjectper%_datatable. ** **nContentlessDelete: **Thenumberofcontentlessdeleteoperationssincethemostrecent **calltofts5IndexFlush()orfts5IndexDiscardData().Thisistracked **sothatextraauto-mergeworkcanbedonebyfts5IndexFlush()to **accountforthedeleteoperations.
*/ struct Fts5Index {
Fts5Config *pConfig; /* Virtual table configuration */
char *zDataTbl; /* Name of %_data table */
int nWorkUnit; /* Leaf pages in a "unit" of work */
/* **Variablesrelatedtotheaccumulationoftokensanddoclistswithinthe **in-memoryhashtablesbeforetheyareflushedtodisk.
*/
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 */
int nContentlessDelete; /* Number of contentless delete ops */
int nPendingRow; /* Number of INSERT in hash table */
/* Error state. */
int rc; /* Current error code */
int flushRc;
/* 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;
sqlite3_stmt *pIdxNextSelect;
int nRead; /* Total number of blocks read */
sqlite3_stmt *pDeleteFromIdx;
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;
};
/* **Thecontentsofthe"structure"recordforeachindexarerepresented **usinganFts5Structurerecordinmemory.Whichusesinstancesofthe **otherFts5StructureXXXtypesascomponents. ** **nOriginCntr: **Thisvalueissettonon-zeroforstructurerecordscreatedfor **contentlessdelete=1tablesonly.Inthatcaseitrepresentsthe **originvaluetoapplytothenexttop-levelsegmentcreated.
*/ struct Fts5StructureSegment {
int iSegid; /* Segment id */
int pgnoFirst; /* First leaf page number in segment */
int pgnoLast; /* Last leaf page number in segment */
/* contentlessdelete=1 tables only: */
u64 iOrigin1;
u64 iOrigin2;
int nPgTombstone; /* Number of tombstone hash table pages */
u64 nEntryTombstone; /* Number of tombstone entries that "count" */
u64 nEntry; /* Number of rows in this 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 */
u64 nOriginCntr; /* Origin value for next top-level segment */
int nSegment; /* Total segments in this structure */
int nLevel; /* Number of levels in this index */
Fts5StructureLevel aLevel[FLEXARRAY]; /* Array of nLevel level objects */
};
/* Size (in bytes) of an Fts5Structure object holding up to N levels */ #define SZ_FTS5STRUCTURE(N) \
(offsetof(Fts5Structure,aLevel) + (N)*sizeof(Fts5StructureLevel))
/* **AnobjectoftypeFts5SegWriterisusedtowritetosegments.
*/ 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 */
};
typedefstruct Fts5CResult Fts5CResult; struct Fts5CResult {
u16 iFirst; /* aSeg[] index of firstest iterator */
u8 bTermEq; /* True if the terms are equal */
};
/* **Objectforiteratingthroughasinglesegment,visitingeachterm/rowid **pairinthesegment. ** **pSeg: **Thesegmenttoiteratethrough. ** **iLeafPgno: **Currentleafpagenumberwithinsegment. ** **iLeafOffset: **Byteoffsetwithinthecurrentleafthatisthefirstbyteofthe **positionlistdata(onebytepassedtheposition-listsizefield). ** **pLeaf: **Buffercontainingcurrentleafpagedata.SettoNULLatEOF. ** **iTermLeafPgno,iTermLeafOffset: **Leafpagenumbercontainingthelasttermreadfromthesegment.And **theoffsetimmediatelyfollowingthetermdata. ** **flags: **MaskofFTS5_SEGITER_XXXvalues.Interpretedasfollows: ** **FTS5_SEGITER_ONETERM: **Ifset,settheiteratortopointtoEOFafterthecurrentdoclist **hasbeenexhausted.Donotproceedtothenextterminthesegment. ** **FTS5_SEGITER_REVERSE: **ThisflagisonlyeversetifFTS5_SEGITER_ONETERMisalsoset.If **itisset,iteratethroughrowidindescendingorderinsteadofthe **defaultascendingorder. ** **iRowidOffset/nRowidOffset/aRowidOffset: **TheseareusediftheFTS5_SEGITER_REVERSEflagisset. ** **Foreachrowidonthepagecorrespondingtothecurrentterm,the **correspondingaRowidOffset[]entryissettothebyteoffsetofthe **startofthe"position-list-size"fieldwithinthepage. ** **iTermIdx: **IndexofcurrenttermoniTermLeafPgno. ** **apTombstone/nTombstone: **Theseareusedforcontentless_delete=1tablesonly.Whenthecursor **isfirstallocated,theapTombstone[]arrayisallocatedsothatit **islargeenoughforalltombstoneshashpagesassociatedwiththe **segment.Thepagesthemselvesareloadedlazilyfromthedatabaseas **theyarerequired.
*/ 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) */
i64 iLeafOffset; /* Byte offset within current leaf */
Fts5TombstoneArray *pTombArray; /* Array of tombstone pages */
/* 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 */
};
static int fts5IndexCorruptRowid(Fts5Index *pIdx, i64 iRowid){
pIdx->rc = FTS5_CORRUPT;
sqlite3Fts5ConfigErrmsg(pIdx->pConfig, "fts5: corruption found reading blob %lld from table \"%s\"",
iRowid, pIdx->pConfig->zName
); return SQLITE_CORRUPT_VTAB;
} #define FTS5_CORRUPT_ROWID(pIdx, iRowid) fts5IndexCorruptRowid(pIdx, iRowid)
/* **Arrayoftombstonepages.Referencecounted.
*/ struct Fts5TombstoneArray {
int nRef; /* Number of pointers to this object */
int nTombstone;
Fts5Data *apTombstone[FLEXARRAY]; /* Array of tombstone pages */
};
/* Size (in bytes) of an Fts5TombstoneArray holding up to N tombstones */ #define SZ_FTS5TOMBSTONEARRAY(N) \
(offsetof(Fts5TombstoneArray,apTombstone)+(N)*sizeof(Fts5Data*))
Fts5Index *pIndex; /* Index that owns 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[FLEXARRAY]; /* Array of segment iterators */
};
/* Size (in bytes) of an Fts5Iter object holding up to N segment iterators */ #define SZ_FTS5ITER(N) (offsetof(Fts5Iter,aSeg)+(N)*sizeof(Fts5SegIter))
/* **Aninstanceofthefollowingtypeisusedtoiteratethroughthecontents **ofadoclist-indexrecord. ** **pData: **Recordcontainingthedoclist-indexdata. ** **bEof: **SettotrueonceiteratorhasreachedEOF. ** **iOff: **SettothecurrentoffsetwithinrecordpData.
*/ 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[FLEXARRAY];
};
/* Size (in bytes) of an Fts5DlidxIter object with up to N levels */ #define SZ_FTS5DLIDXITER(N) \
(offsetof(Fts5DlidxIter,aLvl)+(N)*sizeof(Fts5DlidxLvl))
/* **ComparethecontentsofthepLeftbufferwiththepRight/nRightblob. ** **Return-veifpLeftissmallerthanpRight,0iftheyareequalor **+veifpRightissmallerthanpLeft.Inotherwords: ** **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
if( p->pReader ){ /* This call may return SQLITE_ABORT if there has been a savepoint **rollbacksinceitwaslastused.Inthiscaseanewblobhandle
** 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 ){
fts5IndexCloseReader(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 **abovereturnedSQLITE_ERROR,returnSQLITE_CORRUPT_VTABinstead. **AllthereasonsthosefunctionsmightreturnSQLITE_ERROR-missing **table,missingrow,non-blob/textinblockcolumn-indicate
** backing store corruption. */
if( rc==SQLITE_ERROR ) rc = FTS5_CORRUPT_ROWID(p, iRowid);
/* **Deserializeandreturnthestructurerecordcurrentlystoredinserialized **formwithinbufferpData/nData. ** **TheFts5Structure.aLevel[]andeachFts5StructureLevel.aSeg[]array **areover-allocatedbyoneslot.Thisallowsthestructurecontents **tobemoreeasilyedited. ** **Ifanerroroccurs,*ppOutissettoNULLandanSQLiteerrorcode **returned.Otherwise,*ppOutissettopointtothenewobjectand **SQLITE_OKreturned.
*/ 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;
sqlite3_int64 nByte; /* Bytes of space to allocate at pRet */
Fts5Structure *pRet = 0; /* Structure object to return */
int bStructureV2 = 0; /* True for FTS5_STRUCTURE_V2 */
u64 nOriginCntr = 0; /* Largest origin value seen so far */
/* Grab the cookie value */
if( piCookie ) *piCookie = sqlite3Fts5Get32(pData);
i = 4;
/* Check if this is a V2 structure record. Set bStructureV2 if it is. */
if( 0==memcmp(&pData[i], FTS5_STRUCTURE_V2, 4) ){
i += 4;
bStructureV2 = 1;
}
/* 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);
if( nLevel>FTS5_MAX_SEGMENT || nLevel<0
|| nSegment>FTS5_MAX_SEGMENT || nSegment<0
){ return FTS5_CORRUPT;
}
nByte = SZ_FTS5STRUCTURE(nLevel);
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;
/* **ReturnthetotalnumberofsegmentsinindexstructurepStruct.This **functionisonlyeverusedaspartofassert()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;
}
}
/* **Serializeandstorethe"structure"record. ** **Ifanerroroccurs,leaveanerrorcodeintheFts5Indexobject.Ifan **errorhasalreadyoccurred,thisfunctionisano-op.
*/ staticvoid 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 */
int nHdr = (pStruct->nOriginCntr>0 ? (4+4+9+9+9) : (4+9+9));
/* 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);
}
}
staticvoid 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;
/* **Freeadoclist-indexiteratorobjectallocatedbyfts5DlidxIterInit().
*/ staticvoid 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;
/* **InitializetheiteratorobjectpItertoiteratethroughtheentriesin **segmentpSeg.Theiteratorisleftpointingtothefirstentrywhen **thisfunctionreturns. ** **Ifanerroroccurs,Fts5Index.rcissettoanappropriateerrorcode.If **anerrorhasalreadyoccurredwhenthisfunctioniscalled,itisano-op.
*/ staticvoid 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 **mergeandalldatahasalreadybeen"trimmed".Seefunction **fts5TrimSegments()fordetails.Inthiscaseleavetheiteratorempty. **Thecallerwillseethe(pIter->pLeaf==0)andassumetheiteratoris
** at EOF already. */
assert( pIter->pLeaf==0 ); return;
}
/* **AdvanceiteratorpItertothenextentry. ** **Thisversionoffts5SegIterNext()isonlyusedifdetail=noneandthe **iteratorisnotareversedirectioniterator.
*/ staticvoid fts5SegIterNext_None(
Fts5Index *p, /* FTS5 backend object */
Fts5SegIter *pIter, /* Iterator to advance */
int *pbNewTerm /* OUT: Set for new term */
){
int iOff;
if( pDlidx && p->pConfig->iVersion==FTS5_CURRENT_VERSION ){
int iSegid = pIter->pSeg->iSegid;
pgnoLast = fts5DlidxIterPgno(pDlidx);
pLast = fts5LeafRead(p, FTS5_SEGMENT_ROWID(iSegid, pgnoLast));
}else{
Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */
/* Currently, Fts5SegIter.iLeafOffset points to the first byte of **position-listcontentforthecurrentrowid.Backitupsothatit
** 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 **termmaynotbestoredonthecurrentpage.Sosearchforwardto
** 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 = fts5LeafRead(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 **liesonthepagecurrentlyindicatedbytheiterator.Inthiscase **pIter->iLeafOffsetisalreadysettopointtotheposition-listsize **fieldassociatedwiththefirstrelevantrowidonthepage. ** **Or,ifpLastisnon-NULL,thenitisthepagethatcontainsthelast **rowid.Inthiscaseconfiguretheiteratorsothatitpointstothe **firstrowidonthispage.
*/
if( pLast ){
int iOff;
fts5DataRelease(pIter->pLeaf);
pIter->pLeaf = pLast;
pIter->iLeafPgno = pgnoLast;
if( p->rc==SQLITE_OK ){
iOff = fts5LeafFirstRowidOff(pLast);
if( iOff>pLast->szLeaf ){
FTS5_CORRUPT_ITER(p, pIter); return;
}
iOff += fts5GetVarint(&pLast->p[iOff], (u64*)&pIter->iRowid);
pIter->iLeafOffset = iOff;
/* Check if the current doclist ends on this page. If it does, return **earlywithoutloadingthedoclist-index(asitbelongstoadifferent
** term. */
if( pIter->iTermLeafPgno==pIter->iLeafPgno
&& pIter->iEndofDoclist<pLeaf->szLeaf
){ return;
}
/* Figure out how many new bytes are in this term */
fts5FastGetVarint32(a, iOff, nNew);
if( nKeep<nMatch ){
goto search_failed;
}
if( (iOff+nNew)>n ){
FTS5_CORRUPT_ITER(p, pIter); return;
}
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;
}
/* **InitializetheobjectpItertopointtotermpTerm/nTermwithinsegment **pSeg.Ifthereisnosuchtermintheindex,theiteratorissettoEOF. ** **Ifanerroroccurs,Fts5Index.rcissettoanappropriateerrorcode.If **anerrorhasalreadyoccurredwhenthisfunctioniscalled,itisano-op.
*/ staticvoid 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;
/* 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);
/* **Freetheiteratorobjectpassedasthesecondargument.
*/ staticvoid fts5MultiIterFree(Fts5Iter *pIter){
if( pIter ){
int i;
for(i=0; i<pIter->nSeg; i++){
fts5SegIterClear(&pIter->aSeg[i]);
}
fts5BufferFree(&pIter->poslist);
sqlite3_free(pIter);
}
}
staticvoid 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-iteratoriChangedofiteratorpIterhasjustbeenadvanced.Itstill **pointstothesametermthough-justadifferentrowid.Thisfunction **attemptstoupdatethecontentsofthepIter->aFirst[]accordingly. **Ifitdoessosuccessfully,0isreturned.Otherwise1. ** **Ifnon-zeroisreturned,thecallershouldcallfts5MultiIterAdvanced() **ontheiteratorinstead.Thatfunctiondoesthesameasthisone,except **thatitdealswithmorecomplicatedcasesaswell.
*/ 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];
/* **QueryasingletombstonehashtableforrowidiRowid.Returntrueif **itisfoundorfalseotherwise.Thetombstonehashtableisoneof **nHashTabletables.
*/ static int fts5IndexTombstoneQuery(
Fts5Data *pHash, /* Hash table page to query */
int nHashTable, /* Number of pages attached to segment */
u64 iRowid /* Rowid to query hash for */
){ const int szKey = TOMBSTONE_KEYSIZE(pHash); const int nSlot = TOMBSTONE_NSLOT(pHash);
int iSlot = (iRowid / nHashTable) % nSlot;
int nCollide = nSlot;
if( pSeg->pLeaf && pArray ){ /* Figure out which page the rowid might be present on. */
int iPg = ((u64)pSeg->iRowid) % pArray->nTombstone;
assert( iPg>=0 );
/* If tombstone hash page iPg has not yet been loaded from the
** database, load it now. */
if( pArray->apTombstone[iPg]==0 ){
pArray->apTombstone[iPg] = fts5DataRead(pIter->pIndex,
FTS5_TOMBSTONE_ROWID(pSeg->pSeg->iSegid, iPg)
);
if( pArray->apTombstone[iPg]==0 ) return0;
}
static Fts5Iter *fts5MultiIterAlloc(
Fts5Index *p, /* FTS5 backend to iterate within */
int nSeg
){
Fts5Iter *pNew;
i64 nSlot; /* Power of two >= nSeg */
typedefstruct PoslistCallbackCtx PoslistCallbackCtx; struct PoslistCallbackCtx {
Fts5Buffer *pBuf; /* Append to this buffer */
Fts5Colset *pColset; /* Restrict matches to this column */
int eState; /* See above */
};
typedefstruct PoslistOffsetsCtx PoslistOffsetsCtx; struct PoslistOffsetsCtx {
Fts5Buffer *pBuf; /* Append to this buffer */
Fts5Colset *pColset; /* Restrict matches to this column */
int iRead;
int iWrite;
};
/* **TODO:Makethismoreefficient!
*/ static int fts5IndexColsetTest(Fts5Colset *pColset, int iCol){
int i;
for(i=0; i<pColset->nCol; i++){
if( pColset->aiCol[i]==iCol ) return1;
} return0;
}
staticvoid 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;
/* **ParameterpPospointstoabuffercontainingapositionlist,sizenPos. **ThisfunctionfiltersitaccordingtopColset(whichmustbenon-NULL) **andsetspIter->base.pData/nDatatopointtothenewpositionlist. **Ifmemoryisrequiredforthenewpositionlist,usebufferpIter->poslist. **Or,ifthenewpositionlistisacontiguoussubsetoftheinput,set **pIter->base.pData/nDatatopointdirectlytoit. ** **Thisfunctionisano-opif*pRcisotherthanSQLITE_OKwhenitis **called.IfanOOMerrorisencountered,*pRcissettoSQLITE_NOMEM **beforereturning.
*/ staticvoid fts5IndexExtractColset(
int *pRc,
Fts5Colset *pColset, /* Colset to filter on */ const u8 *pPos, int nPos, /* Position list */
Fts5Iter *pIter
){
if( *pRc==SQLITE_OK ){ const u8 *p = pPos; const u8 *aCopy = p; const u8 *pEnd = &p[nPos]; /* One byte past end of position list */
int i = 0;
int iCurrent = 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<pEnd && (*p++ & 0x80) );
}
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.poslistbufferandthensettheoutputpointertopoint
** to this buffer. */
fts5BufferZero(&pIter->poslist);
fts5SegiterPoslist(pIter->pIndex, pSeg, 0, &pIter->poslist);
pIter->base.pData = pIter->poslist.p;
}
}
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];
int *pRc = &pIter->pIndex->rc;
fts5BufferZero(&pIter->poslist);
fts5IndexExtractColset(pRc, pColset, a, pSeg->nPos, pIter);
}else{ /* The data is distributed over two or more pages. Copy it into the **Fts5Iter.poslistbufferandthensettheoutputpointertopoint
** 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;
}
}
/* **AllocateanewFts5Iterobject. ** **ThenewobjectwillbeusedtoiteratethroughdatainstructurepStruct. **IfiLevelis-ve,thenalldatainallsegmentsismerged.Or,ifiLevel **iszeroorgreater,datafromthefirstnSegmentsegmentsonleveliLevel **ismerged. ** **Theiteratorinitiallypointstothefirstterm/rowidentryinthe **iterateddata.
*/ staticvoid 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;
/* If the above was successful, each component iterator now points **tothefirstentryinitssegment.Inthiscaseinitializethe **aFirst[]array.Or,ifanerrorhasoccurred,freetheiterator
** object and set the output variable to NULL. */
if( p->rc==SQLITE_OK ){
fts5MultiIterFinishSetup(p, pNew);
}else{
fts5MultiIterFree(pNew);
*ppOut = 0;
}
/* **Ifthecurrentdoclist-indexaccumulatinginpWriter->aDlidx[]islarge **enough,flushittodiskandreturn1.Otherwisediscarditandreturn **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;
}
/* **Thisfunctioniscalledwhenflushingaleafpagethatcontainsno **termsatalltodisk.
*/ staticvoid 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;
if( pDlidx->buf.n>=p->pConfig->pgsz ){ /* The current doclist-index page is full. Write it to disk and push **acopyofiRowid(whichwillbecomethefirstrowidonthenext **doclist-indexleafpage)upintothenextleveloftheb-tree **hierarchy.Ifthenodebeingflushediscurrentlytherootnode,
** 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;
}
/* 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;
}
/* **AppendtermpTerm/nTermtothesegmentbeingwrittenbythewriterpassed **asthesecondargument. ** **Ifanerroroccurs,settheFts5Index.rcerrorcode.Ifanerrorhas **alreadyoccurred,thisfunctionisano-op.
*/ staticvoid 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;
int nMin = MIN(pPage->term.n, nTerm);
if( pWriter->bFirstTermInPage ){
nPrefix = 0;
if( pPage->pgno!=1 ){ /* This is the first term on a leaf that is not the leftmost leaf in **thesegmentb-tree.Inthiscaseitisnecessarytoaddatermto **theb-treehierarchythatis(a)largerthanthelargestterm **alreadywrittentothesegmentand(b)smallerthanorequalto **thisterm.Inotherwords,aprefixof(pTerm/nTerm)thatisone **bytelongerthanthelongestprefix(pTerm/nTerm)shareswiththe **previousterm. ** **Usually,theprevioustermisavailableinpPage->term.Theexception **isifthisisthefirsttermwritteninanincremental-mergestep. **Inthiscasetheprevioustermisnotavailable,sojustwritea **copyof(pTerm/nTerm)intotheparentnode.Thisisslightly
** inefficient, but still correct. */
int n = nTerm;
if( pPage->term.n ){
n = 1 + fts5PrefixCompress(nMin, pPage->term.p, pTerm);
}
fts5WriteBtreeTerm(p, pWriter, n, pTerm);
if( p->rc!=SQLITE_OK ) return;
pPage = &pWriter->writer;
}
}else{
nPrefix = fts5PrefixCompress(nMin, 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]);
/* If this is to be the first rowid written to the page, set the **rowid-pointerinthepage-header.Alsoappendavaluetothedlidx
** buffer, in case a doclist-index is required. */
if( pWriter->bFirstRowidInPage ){
fts5PutU16(pPage->buf.p, (u16)pPage->buf.n);
fts5WriteDlidxAppend(p, pWriter, iRowid);
}
/* 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->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 **optimizationoverbindingthesamevalueoverandoverasrowsare
** inserted into %_idx by the current writer. */
sqlite3_bind_int(p->pIdxWriter, 1, pWriter->iSegid);
}
}
/* **IteratorpIterwasusedtoiteratethroughtheinputsegmentsofonan **incrementalmergeoperation.Thisfunctioniscallediftheincremental **mergestephasfinishedbuttheinputhasnotbeencompletelyexhausted.
*/ staticvoid fts5TrimSegments(Fts5Index *p, Fts5Iter *pIter){
int i;
Fts5Buffer buf;
memset(&buf, 0, sizeof(Fts5Buffer));
for(i=0; i<pIter->nSeg && p->rc==SQLITE_OK; 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. **Setboththefirstandlastpage-numbersto0toindicatethatthe
** 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 = fts5LeafRead(p, iLeafRowid);
if( pData ){
if( iOff>pData->szLeaf ){ /* This can occur if the pages that the segments occupy overlap - if **asinglepagehasbeenassignedtomorethanonesegment.In **thiscaseaprioriterationofthisloopmayhavecorruptedthe
** segment currently being trimmed. */
FTS5_CORRUPT_ROWID(p, iLeafRowid);
}else{
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
&& pSeg->iPgidxOff<=pData->nn
){
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]
);
}
/* **
*/ staticvoid 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 */
/* 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;
/* Set the range of origins that will go into the output segment. */
if( pStruct->nOriginCntr>0 ){
pSeg->iOrigin1 = pLvl->aSeg[0].iOrigin1;
pSeg->iOrigin2 = pLvl->aSeg[pLvl->nSeg-1].iOrigin2;
}
}
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;
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));
/* 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 pLvl is already the input level to an ongoing merge, look no **furtherforamergecandidate.Thecallershouldbeallowedto
** continue merging from pLvl first. */
if( pLvl->nMerge ) break;
}
} return iRet;
}
/* **DouptonPgpagesofautomergeworkontheindex. ** **Returntrueifanychangeswereactuallymade,orfalseotherwise.
*/ 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. Or to -1 if
** there is no level suitable to merge 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 = nMin;
} break;
}
if( pLvl->nSeg>nBest ){
nBest = pLvl->nSeg;
iBestLvl = iLvl;
}
}
if( nBest<nMin ){
iBestLvl = fts5IndexFindDeleteMerge(p, pStruct);
}
/* **AtotalofnLeafleafpagesofdatahasjustbeenflushedtoalevel-0 **segment.Thisfunctionupdatesthewrite-counteraccordinglyand,if **necessary,performsincrementalmergework. ** **Ifanerroroccurs,settheFts5Index.rcerrorcode.Ifanerrorhas **alreadyoccurred,thisfunctionisano-op.
*/ staticvoid 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 && ALWAYS((*ppStruct)!=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);
if( iNext==0 ){ /* The page contains no terms or rowids. Replace it with an empty
** page and move on to the right-hand peer. */ const u8 aEmpty[] = {0x00, 0x00, 0x00, 0x04};
assert_nc( bDetailNone==0 || pLeaf->nn==4 );
if( bDetailNone==0 ) fts5DataWrite(p, iRowid, aEmpty, sizeof(aEmpty));
fts5DataRelease(pLeaf);
pLeaf = 0;
}else if( bDetailNone ){ break;
}else if( iNext>=pLeaf->szLeaf || pLeaf->nn<pLeaf->szLeaf || iNext<4 ){
FTS5_CORRUPT_ROWID(p, iRowid); break;
}else{
int nShift = iNext - 4;
int nPg;
int nIdx = 0;
u8 *aIdx = 0;
/* Unless the current page footer is 0 bytes in size (in which case **thenewpagefooterwillbeaswell),allocateandpopulatea **buffercontainingthenewpagefooter.SetstackvariablesaIdx
** and nIdx accordingly. */
if( pLeaf->nn>pLeaf->szLeaf ){
int iFirst = 0;
int i1 = pLeaf->szLeaf;
int i2 = 0;
/* Modify the contents of buffer aPg[]. Set nPg to the new size
** in bytes. The new page is always smaller than the old. */
nPg = pLeaf->szLeaf - nShift;
memmove(&aPg[4], &aPg[4+nShift], nPg-4);
fts5PutU16(&aPg[2], nPg);
if( fts5GetU16(&aPg[0]) ) fts5PutU16(&aPg[>0], 4);
if( nIdx>0 ){
memcpy(&aPg[nPg], aIdx, nIdx);
nPg += nIdx;
}
sqlite3_free(aIdx);
/* Write the new page to disk and exit the loop */
assert( nPg>4 || fts5GetU16(aPg)==0 );
fts5DataWrite(p, iRowid, aPg, nPg); break;
}
}
fts5DataRelease(pLeaf);
}
/* **CompletelyremovetheentrythatpSegcurrentlypointstofrom **thedatabase.
*/ staticvoid fts5DoSecureDelete(
Fts5Index *p,
Fts5SegIter *pSeg
){ const int bDetailNone = (p->pConfig->eDetail==FTS5_DETAIL_NONE);
int iSegid = pSeg->pSeg->iSegid;
u8 *aPg = pSeg->pLeaf->p;
int nPg = pSeg->pLeaf->nn;
int iPgIdx = pSeg->pLeaf->szLeaf; /* Offset of page footer */
u64 iDelta = 0;
int iNextOff = 0;
int iOff = 0;
int nIdx = 0;
u8 *aIdx = 0;
int bLastInDoclist = 0;
int iIdx = 0;
int iStart = 0;
int iDelKeyOff = 0; /* Offset of deleted key, if any */
/* If the position-list for the entry being removed flows over past **theendofthispage,deletetheportionoftheposition-listonthe **nextpageandbeyond. ** **SetvariablebLastInDoclisttotrueifthisentryhappens
** to be the last rowid in the doclist for its term. */
if( iNextOff>=iPgIdx ){
int pgno = pSeg->iLeafPgno+1;
fts5SecureDeleteOverflow(p, pSeg->pSeg, pgno, &bLastInDoclist);
iNextOff = iPgIdx;
}
if( pSeg->bDel==0 ){
if( iNextOff!=iPgIdx ){ /* Loop through the page-footer. If iNextOff (offset of the **entryfollowingtheoneweareremoving)isequaltothe **offsetofakeyonthispage,thentheentryisthelast
** in its doclist. */
int iKeyOff = 0;
for(iIdx=0; iIdx<nIdx; /* no-op */){
u32 iVal = 0;
iIdx += fts5GetVarint32(&aIdx[iIdx], iVal);
iKeyOff += iVal;
if( iKeyOff==iNextOff ){
bLastInDoclist = 1;
}
}
}
/* If this is (a) the first rowid on a page and (b) is not followed by **anotherpositionlistonthesamepage,setthe"first-rowid"field
** of the header to 0. */
if( fts5GetU16(&aPg[0])==iStart && (bLastInDoclist || iNextOff==iPgIdx) ){
fts5PutU16(&aPg[0], 0);
}
}
if( pSeg->bDel ){
iOff += sqlite3Fts5PutVarint(&aPg[iOff], iDelta);
aPg[iOff++] = 0x01;
}else if( bLastInDoclist==0 ){
if( iNextOff!=iPgIdx ){
u64 iNextDelta = 0;
iNextOff += fts5GetVarint(&aPg[iNextOff], &iNextDelta);
iOff += sqlite3Fts5PutVarint(&aPg[iOff], iDelta + iNextDelta);
}
}else if(
pSeg->iLeafPgno==pSeg->iTermLeafPgno
&& iStart==pSeg->iTermLeafOffset
){ /* The entry being removed was the only position list in its
** doclist. Therefore the term needs to be removed as well. */
int iKey = 0;
int iKeyOff = 0;
/* Set iKeyOff to the offset of the term that will be removed - the
** last offset in the footer that is not greater than iStart. */
for(iIdx=0; iIdx<nIdx; iKey++){
u32 iVal = 0;
iIdx += fts5GetVarint32(&aIdx[iIdx], iVal);
if( (iKeyOff+iVal)>(u32)iStart ) break;
iKeyOff += iVal;
}
assert_nc( iKey>=1 );
/* Set iDelKeyOff to the value of the footer entry to remove from
** the page. */
iDelKeyOff = iOff = iKeyOff;
if( iNextOff!=iPgIdx ){ /* This is the only position-list associated with the term, and there **isanothertermfollowingitonthispage.Sothesubsequentterm **needstobemovedtoreplacethetermassociatedwiththeentry
** being removed. */
u64 nPrefix = 0;
u64 nSuffix = 0;
u64 nPrefix2 = 0;
u64 nSuffix2 = 0;
assert_nc( pSeg->iLeafPgno>pSeg->iTermLeafPgno ); /* The entry being removed may be the only position list in
** its doclist. */
for(iPgno=pSeg->iLeafPgno-1; iPgno>pSeg->iTermLeafPgno; iPgno-- ){
Fts5Data *pPg = fts5DataRead(p, FTS5_SEGMENT_ROWID(iSegid, iPgno));
int bEmpty = (pPg && pPg->nn==4);
fts5DataRelease(pPg);
if( bEmpty==0 ) break;
}
/* Assuming no error has occurred, this block does final edits to the **leafpagebeforewritingitbacktodisk.Inputvariablesare: ** **nPg:Totalinitialsizeofleafpage. **iPgIdx:Initialoffsetofpagefooter. ** **iOff:Offsettomovedatato **iNextOff:Offsettomovedatafrom
*/
if( p->rc==SQLITE_OK ){ const int nMove = nPg - iNextOff; /* Number of bytes to move */
int nShift = iNextOff - iOff; /* Distance to move them */
/* **Thisiscalledaspartofflushingadeletetodiskin'secure-delete' **mode.Iteditsthesegmentswithinthedatabasedescribedbyargument **pStructtoremovetheentriesfortermzTerm,rowidiRowid. ** **ReturnSQLITE_OKifsuccessful,oranSQLiteerrorcodeifanerror **hasoccurred.AnyerrorcodeisalsostoredintheFts5Indexhandle.
*/ static int fts5FlushSecureDelete(
Fts5Index *p,
Fts5Structure *pStruct, const char *zTerm,
int nTerm,
i64 iRowid
){ const int f = FTS5INDEX_QUERY_SKIPHASH;
Fts5Iter *pIter = 0; /* Used to find term instance */
/* If the version number has not been set to SECUREDELETE, do so now. */
if( p->pConfig->iVersion!=FTS5_CURRENT_VERSION_SECUREDELETE ){
Fts5Config *pConfig = p->pConfig;
sqlite3_stmt *pStmt = 0;
fts5IndexPrepareStmt(p, &pStmt, sqlite3_mprintf( "REPLACE INTO %Q.'%q_config' VALUES ('version', %d)",
pConfig->zDb, pConfig->zName, FTS5_CURRENT_VERSION_SECUREDELETE
));
if( p->rc==SQLITE_OK ){
int rc;
sqlite3_step(pStmt);
rc = sqlite3_finalize(pStmt);
if( p->rc==SQLITE_OK ) p->rc = rc;
pConfig->iCookie++;
pConfig->iVersion = FTS5_CURRENT_VERSION_SECUREDELETE;
}
}
/* **Flushthecontentsofin-memoryhashtableiHashtoanewlevel-0 **segmentondisk.Alsoupdatethecorrespondingstructurerecord. ** **Ifanerroroccurs,settheFts5Index.rcerrorcode.Ifanerrorhas **alreadyoccurred,thisfunctionisano-op.
*/ staticvoid 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);
fts5StructureInvalidate(p);
if( sqlite3Fts5HashIsEmpty(pHash)==0 ){
iSegid = fts5AllocateSegid(p, pStruct);
if( iSegid ){ const int pgsz = p->pConfig->pgsz;
int eDetail = p->pConfig->eDetail;
int bSecureDelete = p->pConfig->bSecureDelete;
Fts5StructureSegment *pSeg; /* New segment within pStruct */
Fts5Buffer *pBuf; /* Buffer in which to assemble leaf page */
Fts5Buffer *pPgidx; /* Buffer in which to assemble 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 */
int nTerm; /* Size of zTerm in bytes */ const u8 *pDoclist; /* Pointer to doclist for this term */
int nDoclist; /* Size of doclist in bytes */
/* Get the term and doclist for this entry. */
sqlite3Fts5HashScanEntry(pHash, &zTerm, &nTerm, &pDoclist, &nDoclist);
if( bSecureDelete==0 ){
fts5WriteAppendTerm(p, &writer, nTerm, (const u8*)zTerm);
if( p->rc!=SQLITE_OK ) break;
assert( writer.bFirstRowidInPage==0 );
}
if( !bSecureDelete && pgsz>=(pBuf->n + pPgidx->n + nDoclist + 1) ){ /* The entire doclist will fit on the current leaf. */
fts5BufferSafeAppendBlob(pBuf, pDoclist, nDoclist);
}else{
int bTermWritten = !bSecureDelete;
i64 iRowid = 0;
i64 iPrev = 0;
int iOff = 0;
/* The entire doclist will not fit on this leaf. The following **loopiteratesthroughtheposliststhatmakeupthecurrent
** doclist. */ while( p->rc==SQLITE_OK && iOff<nDoclist ){
u64 iDelta = 0;
iOff += fts5GetVarint(&pDoclist[iOff], &iDelta);
iRowid += iDelta;
/* If in secure delete mode, and if this entry in the poslist is **infactadelete,thenedittheexistingsegmentsdirectly
** using fts5FlushSecureDelete(). */
if( bSecureDelete ){
if( eDetail==FTS5_DETAIL_NONE ){
if( iOff<nDoclist && pDoclist[iOff]==0x00
&& !fts5FlushSecureDelete(p, pStruct, zTerm, nTerm, iRowid)
){
iOff++;
if( iOff<nDoclist && pDoclist[iOff]==0x00 ){
iOff++;
nDoclist = 0;
}else{ continue;
}
}
}else if( (pDoclist[iOff] & 0x01)
&& !fts5FlushSecureDelete(p, pStruct, zTerm, nTerm, iRowid)
){
if( p->rc!=SQLITE_OK || pDoclist[iOff]==0x01 ){
iOff++; continue;
}
}
}
typedefstruct PrefixMerger PrefixMerger; struct PrefixMerger {
Fts5DoclistIter iter; /* Doclist iterator */
i64 iPos; /* For iterating through a position list */
int iOff;
u8 *aPos;
PrefixMerger *pNext; /* Next in docid/poslist order */
};
/* **ArrayaBuf[]containsnBufdoclists.Theseareallmergedinwiththe **doclistinbufferp1.
*/ staticvoid fts5MergePrefixLists(
Fts5Index *p, /* FTS5 backend object */
Fts5Buffer *p1, /* First list to merge */
int nBuf, /* Number of buffers in array aBuf[] */
Fts5Buffer *aBuf /* Other lists to merge in */
){ #define fts5PrefixMergerNextPosition(p) \
sqlite3Fts5PoslistNext64((p)->aPos,(p)->iter.nPoslist,&(p)->iOff,&(p)->iPos) #define FTS5_MERGE_NLIST 16
PrefixMerger aMerger[FTS5_MERGE_NLIST];
PrefixMerger *pHead = 0;
int i;
int nOut = 0;
Fts5Buffer out = {0, 0, 0};
Fts5Buffer tmp = {0, 0, 0};
i64 iLastRowid = 0;
/* Initialize a doclist-iterator for each input buffer. Arrange them in **alinked-liststartingatpHeadinascendingorderofrowid.Avoid
** linking any iterators already at EOF into the linked list at all. */
assert( nBuf+1<=(int)(sizeof(aMerger)/sizeof(aMerger[0])) );
memset(aMerger, 0, sizeof(PrefixMerger)*(nBuf+1));
pHead = &aMerger[nBuf];
fts5DoclistIterInit(p1, &pHead->iter);
for(i=0; i<nBuf; i++){
fts5DoclistIterInit(&aBuf[i], &aMerger[i].iter);
fts5PrefixMergerInsertByRowid(&pHead, &aMerger[i]);
nOut += aBuf[i].n;
}
if( nOut==0 ) return;
nOut += p1->n + 9 + 10*nBuf;
/* The maximum size of the output is equal to the sum of the **inputsizes+1varint(9bytes).Theextravarintisbecauseifthe **firstrowidinoneinputisalargenegativenumber,andthefirstin **theotheranon-negativenumber,thedeltaforthenon-negative **numberwillbelargerondiskthantheliteralintegervalue **was. ** **Or,iftheinputposition-listsarecorrupt,thentheoutputmight **includeupto(nBuf+1)extra10-bytepositionscreatedbyinterpreting-1 **(thevaluePoslistNext64()usesforEOF)asapositionandappending **ittotheoutput.Thiscanhappenatmostonceforeachinput
** position-list, hence (nBuf+1) 10 byte paddings. */
if( sqlite3Fts5BufferSize(&p->rc, &out, nOut) ) return;
if( pHead->pNext && iLastRowid==pHead->pNext->iter.iRowid ){ /* Merge data from two or more poslists */
i64 iPrev = 0;
int nTmp = FTS5_DATA_ZERO_PADDING;
int nMerge = 0;
PrefixMerger *pSave = pHead;
PrefixMerger *pThis = 0;
int nTail = 0;
/* See the earlier comment in this function for an explanation of why **corruptinputpositionlistsmightcausetheoutputtoconsume
** at most nMerge*10 bytes of unexpected space. */
if( sqlite3Fts5BufferSize(&p->rc, &tmp, nTmp+nMerge*10) ){ break;
}
fts5BufferZero(&tmp);
/* **Usually,atokendata=1iterator(structFts5TokenDataIter)accumulatesan **arrayoftheseforeachrowitvisits(soalliRowidfieldsarethesame). **Or,foraniteratorusedbyan"ORDERBYrank"query,itaccumulatesan **arrayofthesefortheentirequery(inwhichcaseiRowidfieldsmaytake **avarietyofvalues). ** **Eachinstanceinthearrayindicatestheiterator(andthereforeterm) **associatedwithpositioniPosofrowidiRowid.Thisisusedbythe **xInstToken()API. ** **iRowid: **Rowidforthecurrententry. ** **iPos: **Positionofcurrententrywithinrow.Intheusual((iCol<<32)+iOff) **format(e.g.seemacrosFTS5_POS2COLUMN()andFTS5_POS2OFFSET()). ** **iIter: **IftheFts5TokenDataIteriteratorthattheentryispartofis **actuallyaniterator(i.e.withnIter>0,notjustacontainerfor **Fts5TokenDataMapstructures),thenthisvariableisanindexinto **theapIter[]array.Thecorrespondingtermisthatwhichtheiterator **atapIter[iIter]currentlypointsto. ** **Or,iftheFts5TokenDataIteriteratorisjustacontainerobject **(nIter==0),theniIterisanindexintotheterm.p[]bufferwhere **thetermisstored. ** **nByte: **InthecasewhereiIterisanindexintoterm.p[],thisvariable **isthesizeoftheterminbytes.IfiIterisanindexintoapIter[], **thisvariableisunused.
*/ struct Fts5TokenDataMap {
i64 iRowid; /* Row this token is located in */
i64 iPos; /* Position of token */
int iIter; /* Iterator token was read from */
int nByte; /* Length of token in bytes (or 0) */
};
/* **AnobjectusedtosupplementFts5Iterfortokendata=1iterators. ** **Thisobjectservestwopurposes.Thefirstisasacontainerforanarray **ofFts5TokenDataMapstructures,whichareusedtofindthetokenrequired **whenthexInstToken()APIisused.ThisisdonebythenMapAlloc,nMapand **aMap[]variables.
*/ struct Fts5TokenDataIter {
i64 nMapAlloc; /* Allocated size of aMap[] in entries */
i64 nMap; /* Number of valid entries in aMap[] */
Fts5TokenDataMap *aMap; /* Array of (rowid+pos -> token) mappings */
/* The following are used for prefix-queries only. */
Fts5Buffer terms;
/* The following are used for other full-token tokendata queries only. */
i64 nIter;
i64 nIterAlloc;
Fts5PoslistReader *aPoslistReader;
int *aPoslistToIter;
Fts5Iter *apIter[FLEXARRAY];
};
/* Size in bytes of an Fts5TokenDataIter object holding up to N iterators */ #define SZ_FTS5TOKENDATAITER(N) \
(offsetof(Fts5TokenDataIter,apIter) + (N)*sizeof(Fts5Iter))
/* **fts5VisitEntries()contextobjectusedbyfts5SetupPrefixIterTokendata() **topassdatatoprefixIterSetupTokendataCb().
*/ typedefstruct TokendataSetupCtx TokendataSetupCtx; struct TokendataSetupCtx {
Fts5TokenDataIter *pT; /* Object being populated with mappings */
int iTermOff; /* Offset of current term in terms.p[] */
int nTermByte; /* Size of current term in bytes */
};
staticvoid fts5SetupPrefixIter(
Fts5Index *p, /* Index to read from */
int bDesc, /* True for "ORDER BY rowid DESC" */
int iIdx, /* Index to scan for data */
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;
PrefixSetupCtx s;
TokendataSetupCtx s2;
/* If iIdx is non-zero, then it is the number of a prefix-index for **prefixes1characterlongerthantheprefixbeingqueriedfor.That **indexcontainsallthedoclistsrequired,exceptfortheone **correspondingtotheprefixitself.Thatoneisextractedfromthe
** main term index here. */
if( iIdx!=0 ){
pToken[0] = FTS5_MAIN_PREFIX;
fts5VisitEntries(p, pColset, pToken, nToken, 0, prefixIterSetupCb, pCtx);
}
/* **Indicatethatallsubsequentcallstosqlite3Fts5IndexWrite()pertain **tothedocumentwithrowidiRowid.
*/ static 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);
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.