| 1 |
/* |
| 2 |
** 2014 May 31 |
| 3 |
** |
| 4 |
** The author disclaims copyright to this source code. In place of |
| 5 |
** a legal notice, here is a blessing: |
| 6 |
** |
| 7 |
** May you do good and not evil. |
| 8 |
** May you find forgiveness for yourself and forgive others. |
| 9 |
** May you share freely, never taking more than you give. |
| 10 |
** |
| 11 |
****************************************************************************** |
| 12 |
*/ |
| 13 |
|
| 14 |
|
| 15 |
|
| 16 |
#include "fts5Int.h" |
| 17 |
|
| 18 |
int sqlite3Fts5BufferSize(int *pRc, Fts5Buffer *pBuf, u32 nByte){ |
| 19 |
if( (u32)pBuf->nSpace<nByte ){ |
| 20 |
u64 nNew = pBuf->nSpace ? pBuf->nSpace : 64; |
| 21 |
u8 *pNew; |
| 22 |
while( nNew<nByte ){ |
| 23 |
nNew = nNew * 2; |
| 24 |
} |
| 25 |
pNew = sqlite3_realloc64(pBuf->p, nNew); |
| 26 |
if( pNew==0 ){ |
| 27 |
*pRc = SQLITE_NOMEM; |
| 28 |
return 1; |
| 29 |
}else{ |
| 30 |
pBuf->nSpace = (int)nNew; |
| 31 |
pBuf->p = pNew; |
| 32 |
} |
| 33 |
} |
| 34 |
return 0; |
| 35 |
} |
| 36 |
|
| 37 |
|
| 38 |
/* |
| 39 |
** Encode value iVal as an SQLite varint and append it to the buffer object |
| 40 |
** pBuf. If an OOM error occurs, set the error code in p. |
| 41 |
*/ |
| 42 |
void sqlite3Fts5BufferAppendVarint(int *pRc, Fts5Buffer *pBuf, i64 iVal){ |
| 43 |
if( fts5BufferGrow(pRc, pBuf, 9) ) return; |
| 44 |
pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iVal); |
| 45 |
} |
| 46 |
|
| 47 |
void sqlite3Fts5Put32(u8 *aBuf, int iVal){ |
| 48 |
aBuf[0] = (iVal>>24) & 0x00FF; |
| 49 |
aBuf[1] = (iVal>>16) & 0x00FF; |
| 50 |
aBuf[2] = (iVal>> 8) & 0x00FF; |
| 51 |
aBuf[3] = (iVal>> 0) & 0x00FF; |
| 52 |
} |
| 53 |
|
| 54 |
int sqlite3Fts5Get32(const u8 *aBuf){ |
| 55 |
return (int)((((u32)aBuf[0])<<24) + (aBuf[1]<<16) + (aBuf[2]<<8) + aBuf[3]); |
| 56 |
} |
| 57 |
|
| 58 |
/* |
| 59 |
** Append buffer nData/pData to buffer pBuf. If an OOM error occurs, set |
| 60 |
** the error code in p. If an error has already occurred when this function |
| 61 |
** is called, it is a no-op. |
| 62 |
*/ |
| 63 |
void sqlite3Fts5BufferAppendBlob( |
| 64 |
int *pRc, |
| 65 |
Fts5Buffer *pBuf, |
| 66 |
u32 nData, |
| 67 |
const u8 *pData |
| 68 |
){ |
| 69 |
if( nData ){ |
| 70 |
if( fts5BufferGrow(pRc, pBuf, nData) ) return; |
| 71 |
assert( pBuf->p!=0 ); |
| 72 |
memcpy(&pBuf->p[pBuf->n], pData, nData); |
| 73 |
pBuf->n += nData; |
| 74 |
} |
| 75 |
} |
| 76 |
|
| 77 |
/* |
| 78 |
** Append the nul-terminated string zStr to the buffer pBuf. This function |
| 79 |
** ensures that the byte following the buffer data is set to 0x00, even |
| 80 |
** though this byte is not included in the pBuf->n count. |
| 81 |
*/ |
| 82 |
void sqlite3Fts5BufferAppendString( |
| 83 |
int *pRc, |
| 84 |
Fts5Buffer *pBuf, |
| 85 |
const char *zStr |
| 86 |
){ |
| 87 |
int nStr = (int)strlen(zStr); |
| 88 |
sqlite3Fts5BufferAppendBlob(pRc, pBuf, nStr+1, (const u8*)zStr); |
| 89 |
pBuf->n--; |
| 90 |
} |
| 91 |
|
| 92 |
/* |
| 93 |
** Argument zFmt is a printf() style format string. This function performs |
| 94 |
** the printf() style processing, then appends the results to buffer pBuf. |
| 95 |
** |
| 96 |
** Like sqlite3Fts5BufferAppendString(), this function ensures that the byte |
| 97 |
** following the buffer data is set to 0x00, even though this byte is not |
| 98 |
** included in the pBuf->n count. |
| 99 |
*/ |
| 100 |
void sqlite3Fts5BufferAppendPrintf( |
| 101 |
int *pRc, |
| 102 |
Fts5Buffer *pBuf, |
| 103 |
char *zFmt, ... |
| 104 |
){ |
| 105 |
if( *pRc==SQLITE_OK ){ |
| 106 |
char *zTmp; |
| 107 |
va_list ap; |
| 108 |
va_start(ap, zFmt); |
| 109 |
zTmp = sqlite3_vmprintf(zFmt, ap); |
| 110 |
va_end(ap); |
| 111 |
|
| 112 |
if( zTmp==0 ){ |
| 113 |
*pRc = SQLITE_NOMEM; |
| 114 |
}else{ |
| 115 |
sqlite3Fts5BufferAppendString(pRc, pBuf, zTmp); |
| 116 |
sqlite3_free(zTmp); |
| 117 |
} |
| 118 |
} |
| 119 |
} |
| 120 |
|
| 121 |
char *sqlite3Fts5Mprintf(int *pRc, const char *zFmt, ...){ |
| 122 |
char *zRet = 0; |
| 123 |
if( *pRc==SQLITE_OK ){ |
| 124 |
va_list ap; |
| 125 |
va_start(ap, zFmt); |
| 126 |
zRet = sqlite3_vmprintf(zFmt, ap); |
| 127 |
va_end(ap); |
| 128 |
if( zRet==0 ){ |
| 129 |
*pRc = SQLITE_NOMEM; |
| 130 |
} |
| 131 |
} |
| 132 |
return zRet; |
| 133 |
} |
| 134 |
|
| 135 |
|
| 136 |
/* |
| 137 |
** Free any buffer allocated by pBuf. Zero the structure before returning. |
| 138 |
*/ |
| 139 |
void sqlite3Fts5BufferFree(Fts5Buffer *pBuf){ |
| 140 |
sqlite3_free(pBuf->p); |
| 141 |
memset(pBuf, 0, sizeof(Fts5Buffer)); |
| 142 |
} |
| 143 |
|
| 144 |
/* |
| 145 |
** Zero the contents of the buffer object. But do not free the associated |
| 146 |
** memory allocation. |
| 147 |
*/ |
| 148 |
void sqlite3Fts5BufferZero(Fts5Buffer *pBuf){ |
| 149 |
pBuf->n = 0; |
| 150 |
} |
| 151 |
|
| 152 |
/* |
| 153 |
** Set the buffer to contain nData/pData. If an OOM error occurs, leave an |
| 154 |
** the error code in p. If an error has already occurred when this function |
| 155 |
** is called, it is a no-op. |
| 156 |
*/ |
| 157 |
void sqlite3Fts5BufferSet( |
| 158 |
int *pRc, |
| 159 |
Fts5Buffer *pBuf, |
| 160 |
int nData, |
| 161 |
const u8 *pData |
| 162 |
){ |
| 163 |
pBuf->n = 0; |
| 164 |
sqlite3Fts5BufferAppendBlob(pRc, pBuf, nData, pData); |
| 165 |
} |
| 166 |
|
| 167 |
int sqlite3Fts5PoslistNext64( |
| 168 |
const u8 *a, int n, /* Buffer containing poslist */ |
| 169 |
int *pi, /* IN/OUT: Offset within a[] */ |
| 170 |
i64 *piOff /* IN/OUT: Current offset */ |
| 171 |
){ |
| 172 |
int i = *pi; |
| 173 |
assert( a!=0 || i==0 ); |
| 174 |
if( i>=n ){ |
| 175 |
/* EOF */ |
| 176 |
*piOff = -1; |
| 177 |
return 1; |
| 178 |
}else{ |
| 179 |
i64 iOff = *piOff; |
| 180 |
u32 iVal; |
| 181 |
assert( a!=0 ); |
| 182 |
fts5FastGetVarint32(a, i, iVal); |
| 183 |
if( iVal<=1 ){ |
| 184 |
if( iVal==0 ){ |
| 185 |
*pi = i; |
| 186 |
return 0; |
| 187 |
} |
| 188 |
fts5FastGetVarint32(a, i, iVal); |
| 189 |
iOff = ((i64)iVal) << 32; |
| 190 |
assert( iOff>=0 ); |
| 191 |
fts5FastGetVarint32(a, i, iVal); |
| 192 |
if( iVal<2 ){ |
| 193 |
/* This is a corrupt record. So stop parsing it here. */ |
| 194 |
*piOff = -1; |
| 195 |
return 1; |
| 196 |
} |
| 197 |
*piOff = iOff + ((iVal-2) & 0x7FFFFFFF); |
| 198 |
}else{ |
| 199 |
*piOff = (iOff & (i64)0x7FFFFFFF<<32)+((iOff + (iVal-2)) & 0x7FFFFFFF); |
| 200 |
} |
| 201 |
*pi = i; |
| 202 |
assert_nc( *piOff>=iOff ); |
| 203 |
return 0; |
| 204 |
} |
| 205 |
} |
| 206 |
|
| 207 |
|
| 208 |
/* |
| 209 |
** Advance the iterator object passed as the only argument. Return true |
| 210 |
** if the iterator reaches EOF, or false otherwise. |
| 211 |
*/ |
| 212 |
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader *pIter){ |
| 213 |
if( sqlite3Fts5PoslistNext64(pIter->a, pIter->n, &pIter->i, &pIter->iPos) ){ |
| 214 |
pIter->bEof = 1; |
| 215 |
} |
| 216 |
return pIter->bEof; |
| 217 |
} |
| 218 |
|
| 219 |
int sqlite3Fts5PoslistReaderInit( |
| 220 |
const u8 *a, int n, /* Poslist buffer to iterate through */ |
| 221 |
Fts5PoslistReader *pIter /* Iterator object to initialize */ |
| 222 |
){ |
| 223 |
memset(pIter, 0, sizeof(*pIter)); |
| 224 |
pIter->a = a; |
| 225 |
pIter->n = n; |
| 226 |
sqlite3Fts5PoslistReaderNext(pIter); |
| 227 |
return pIter->bEof; |
| 228 |
} |
| 229 |
|
| 230 |
/* |
| 231 |
** Append position iPos to the position list being accumulated in buffer |
| 232 |
** pBuf, which must be already be large enough to hold the new data. |
| 233 |
** The previous position written to this list is *piPrev. *piPrev is set |
| 234 |
** to iPos before returning. |
| 235 |
*/ |
| 236 |
void sqlite3Fts5PoslistSafeAppend( |
| 237 |
Fts5Buffer *pBuf, |
| 238 |
i64 *piPrev, |
| 239 |
i64 iPos |
| 240 |
){ |
| 241 |
if( iPos>=*piPrev ){ |
| 242 |
static const i64 colmask = ((i64)(0x7FFFFFFF)) << 32; |
| 243 |
if( (iPos & colmask) != (*piPrev & colmask) ){ |
| 244 |
pBuf->p[pBuf->n++] = 1; |
| 245 |
pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos>>32)); |
| 246 |
*piPrev = (iPos & colmask); |
| 247 |
} |
| 248 |
pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos-*piPrev)+2); |
| 249 |
*piPrev = iPos; |
| 250 |
} |
| 251 |
} |
| 252 |
|
| 253 |
int sqlite3Fts5PoslistWriterAppend( |
| 254 |
Fts5Buffer *pBuf, |
| 255 |
Fts5PoslistWriter *pWriter, |
| 256 |
i64 iPos |
| 257 |
){ |
| 258 |
int rc = 0; /* Initialized only to suppress erroneous warning from Clang */ |
| 259 |
if( fts5BufferGrow(&rc, pBuf, 5+5+5) ) return rc; |
| 260 |
sqlite3Fts5PoslistSafeAppend(pBuf, &pWriter->iPrev, iPos); |
| 261 |
return SQLITE_OK; |
| 262 |
} |
| 263 |
|
| 264 |
void *sqlite3Fts5MallocZero(int *pRc, sqlite3_int64 nByte){ |
| 265 |
void *pRet = 0; |
| 266 |
if( *pRc==SQLITE_OK ){ |
| 267 |
pRet = sqlite3_malloc64(nByte); |
| 268 |
if( pRet==0 ){ |
| 269 |
if( nByte>0 ) *pRc = SQLITE_NOMEM; |
| 270 |
}else{ |
| 271 |
memset(pRet, 0, (size_t)nByte); |
| 272 |
} |
| 273 |
} |
| 274 |
return pRet; |
| 275 |
} |
| 276 |
|
| 277 |
/* |
| 278 |
** Return a nul-terminated copy of the string indicated by pIn. If nIn |
| 279 |
** is non-negative, then it is the length of the string in bytes. Otherwise, |
| 280 |
** the length of the string is determined using strlen(). |
| 281 |
** |
| 282 |
** It is the responsibility of the caller to eventually free the returned |
| 283 |
** buffer using sqlite3_free(). If an OOM error occurs, NULL is returned. |
| 284 |
*/ |
| 285 |
char *sqlite3Fts5Strndup(int *pRc, const char *pIn, int nIn){ |
| 286 |
char *zRet = 0; |
| 287 |
if( *pRc==SQLITE_OK ){ |
| 288 |
if( nIn<0 ){ |
| 289 |
nIn = (int)strlen(pIn); |
| 290 |
} |
| 291 |
zRet = (char*)sqlite3_malloc64((i64)nIn+1); |
| 292 |
if( zRet ){ |
| 293 |
memcpy(zRet, pIn, nIn); |
| 294 |
zRet[nIn] = '\0'; |
| 295 |
}else{ |
| 296 |
*pRc = SQLITE_NOMEM; |
| 297 |
} |
| 298 |
} |
| 299 |
return zRet; |
| 300 |
} |
| 301 |
|
| 302 |
|
| 303 |
/* |
| 304 |
** Return true if character 't' may be part of an FTS5 bareword, or false |
| 305 |
** otherwise. Characters that may be part of barewords: |
| 306 |
** |
| 307 |
** * All non-ASCII characters, |
| 308 |
** * The 52 upper and lower case ASCII characters, and |
| 309 |
** * The 10 integer ASCII characters. |
| 310 |
** * The underscore character "_" (0x5F). |
| 311 |
** * The unicode "substitute" character (0x1A). |
| 312 |
*/ |
| 313 |
int sqlite3Fts5IsBareword(char t){ |
| 314 |
u8 aBareword[128] = { |
| 315 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x00 .. 0x0F */ |
| 316 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, /* 0x10 .. 0x1F */ |
| 317 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x20 .. 0x2F */ |
| 318 |
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /* 0x30 .. 0x3F */ |
| 319 |
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 0x40 .. 0x4F */ |
| 320 |
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, /* 0x50 .. 0x5F */ |
| 321 |
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 0x60 .. 0x6F */ |
| 322 |
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0 /* 0x70 .. 0x7F */ |
| 323 |
}; |
| 324 |
|
| 325 |
return (t & 0x80) || aBareword[(int)t]; |
| 326 |
} |
| 327 |
|
| 328 |
|
| 329 |
/************************************************************************* |
| 330 |
*/ |
| 331 |
typedef struct Fts5TermsetEntry Fts5TermsetEntry; |
| 332 |
struct Fts5TermsetEntry { |
| 333 |
char *pTerm; |
| 334 |
int nTerm; |
| 335 |
int iIdx; /* Index (main or aPrefix[] entry) */ |
| 336 |
Fts5TermsetEntry *pNext; |
| 337 |
}; |
| 338 |
|
| 339 |
struct Fts5Termset { |
| 340 |
Fts5TermsetEntry *apHash[512]; |
| 341 |
}; |
| 342 |
|
| 343 |
int sqlite3Fts5TermsetNew(Fts5Termset **pp){ |
| 344 |
int rc = SQLITE_OK; |
| 345 |
*pp = sqlite3Fts5MallocZero(&rc, sizeof(Fts5Termset)); |
| 346 |
return rc; |
| 347 |
} |
| 348 |
|
| 349 |
int sqlite3Fts5TermsetAdd( |
| 350 |
Fts5Termset *p, |
| 351 |
int iIdx, |
| 352 |
const char *pTerm, int nTerm, |
| 353 |
int *pbPresent |
| 354 |
){ |
| 355 |
int rc = SQLITE_OK; |
| 356 |
*pbPresent = 0; |
| 357 |
if( p ){ |
| 358 |
int i; |
| 359 |
u32 hash = 13; |
| 360 |
Fts5TermsetEntry *pEntry; |
| 361 |
|
| 362 |
/* Calculate a hash value for this term. This is the same hash checksum |
| 363 |
** used by the fts5_hash.c module. This is not important for correct |
| 364 |
** operation of the module, but is necessary to ensure that some tests |
| 365 |
** designed to produce hash table collisions really do work. */ |
| 366 |
for(i=nTerm-1; i>=0; i--){ |
| 367 |
hash = (hash << 3) ^ hash ^ pTerm[i]; |
| 368 |
} |
| 369 |
hash = (hash << 3) ^ hash ^ iIdx; |
| 370 |
hash = hash % ArraySize(p->apHash); |
| 371 |
|
| 372 |
for(pEntry=p->apHash[hash]; pEntry; pEntry=pEntry->pNext){ |
| 373 |
if( pEntry->iIdx==iIdx |
| 374 |
&& pEntry->nTerm==nTerm |
| 375 |
&& memcmp(pEntry->pTerm, pTerm, nTerm)==0 |
| 376 |
){ |
| 377 |
*pbPresent = 1; |
| 378 |
break; |
| 379 |
} |
| 380 |
} |
| 381 |
|
| 382 |
if( pEntry==0 ){ |
| 383 |
pEntry = sqlite3Fts5MallocZero(&rc, sizeof(Fts5TermsetEntry) + nTerm); |
| 384 |
if( pEntry ){ |
| 385 |
pEntry->pTerm = (char*)&pEntry[1]; |
| 386 |
pEntry->nTerm = nTerm; |
| 387 |
pEntry->iIdx = iIdx; |
| 388 |
memcpy(pEntry->pTerm, pTerm, nTerm); |
| 389 |
pEntry->pNext = p->apHash[hash]; |
| 390 |
p->apHash[hash] = pEntry; |
| 391 |
} |
| 392 |
} |
| 393 |
} |
| 394 |
|
| 395 |
return rc; |
| 396 |
} |
| 397 |
|
| 398 |
void sqlite3Fts5TermsetFree(Fts5Termset *p){ |
| 399 |
if( p ){ |
| 400 |
u32 i; |
| 401 |
for(i=0; i<ArraySize(p->apHash); i++){ |
| 402 |
Fts5TermsetEntry *pEntry = p->apHash[i]; |
| 403 |
while( pEntry ){ |
| 404 |
Fts5TermsetEntry *pDel = pEntry; |
| 405 |
pEntry = pEntry->pNext; |
| 406 |
sqlite3_free(pDel); |
| 407 |
} |
| 408 |
} |
| 409 |
sqlite3_free(p); |
| 410 |
} |
| 411 |
} |