ext/fts5/fts5_buffer.c

   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_malloc(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 "subsitute" 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 }