ext/fts5/fts5_hash.c

   1 /*
   2 ** 2014 August 11
   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
  17 #include "fts5Int.h"
  18
  19 typedef struct Fts5HashEntry Fts5HashEntry;
  20
  21 /*
  22 ** This file contains the implementation of an in-memory hash table used
  23 ** to accumuluate "term -> doclist" content before it is flused to a level-0
  24 ** segment.
  25 */
  26
  27
  28 struct Fts5Hash {
  29   int eDetail;                    /* Copy of Fts5Config.eDetail */
  30   int *pnByte;                    /* Pointer to bytes counter */
  31   int nEntry;                     /* Number of entries currently in hash */
  32   int nSlot;                      /* Size of aSlot[] array */
  33   Fts5HashEntry *pScan;           /* Current ordered scan item */
  34   Fts5HashEntry **aSlot;          /* Array of hash slots */
  35 };
  36
  37 /*
  38 ** Each entry in the hash table is represented by an object of the
  39 ** following type. Each object, its key, and its current data are stored
  40 ** in a single memory allocation. The key immediately follows the object
  41 ** in memory. The position list data immediately follows the key data
  42 ** in memory.
  43 **
  44 ** The key is Fts5HashEntry.nKey bytes in size. It consists of a single
  45 ** byte identifying the index (either the main term index or a prefix-index),
  46 ** followed by the term data. For example: "0token". There is no
  47 ** nul-terminator - in this case nKey=6.
  48 **
  49 ** The data that follows the key is in a similar, but not identical format
  50 ** to the doclist data stored in the database. It is:
  51 **
  52 **   * Rowid, as a varint
  53 **   * Position list, without 0x00 terminator.
  54 **   * Size of previous position list and rowid, as a 4 byte
  55 **     big-endian integer.
  56 **
  57 ** iRowidOff:
  58 **   Offset of last rowid written to data area. Relative to first byte of
  59 **   structure.
  60 **
  61 ** nData:
  62 **   Bytes of data written since iRowidOff.
  63 */
  64 struct Fts5HashEntry {
  65   Fts5HashEntry *pHashNext;       /* Next hash entry with same hash-key */
  66   Fts5HashEntry *pScanNext;       /* Next entry in sorted order */
  67
  68   int nAlloc;                     /* Total size of allocation */
  69   int iSzPoslist;                 /* Offset of space for 4-byte poslist size */
  70   int nData;                      /* Total bytes of data (incl. structure) */
  71   int nKey;                       /* Length of key in bytes */
  72   u8 bDel;                        /* Set delete-flag @ iSzPoslist */
  73   u8 bContent;                    /* Set content-flag (detail=none mode) */
  74   i16 iCol;                       /* Column of last value written */
  75   int iPos;                       /* Position of last value written */
  76   i64 iRowid;                     /* Rowid of last value written */
  77 };
  78
  79 /*
  80 ** Eqivalent to:
  81 **
  82 **   char *fts5EntryKey(Fts5HashEntry *pEntry){ return zKey; }
  83 */
  84 #define fts5EntryKey(p) ( ((char *)(&(p)[1])) )
  85
  86
  87 /*
  88 ** Allocate a new hash table.
  89 */
  90 int sqlite3Fts5HashNew(Fts5Config *pConfig, Fts5Hash **ppNew, int *pnByte){
  91   int rc = SQLITE_OK;
  92   Fts5Hash *pNew;
  93
  94   *ppNew = pNew = (Fts5Hash*)sqlite3_malloc(sizeof(Fts5Hash));
  95   if( pNew==0 ){
  96     rc = SQLITE_NOMEM;
  97   }else{
  98     sqlite3_int64 nByte;
  99     memset(pNew, 0, sizeof(Fts5Hash));
 100     pNew->pnByte = pnByte;
 101     pNew->eDetail = pConfig->eDetail;
 102
 103     pNew->nSlot = 1024;
 104     nByte = sizeof(Fts5HashEntry*) * pNew->nSlot;
 105     pNew->aSlot = (Fts5HashEntry**)sqlite3_malloc64(nByte);
 106     if( pNew->aSlot==0 ){
 107       sqlite3_free(pNew);
 108       *ppNew = 0;
 109       rc = SQLITE_NOMEM;
 110     }else{
 111       memset(pNew->aSlot, 0, (size_t)nByte);
 112     }
 113   }
 114   return rc;
 115 }
 116
 117 /*
 118 ** Free a hash table object.
 119 */
 120 void sqlite3Fts5HashFree(Fts5Hash *pHash){
 121   if( pHash ){
 122     sqlite3Fts5HashClear(pHash);
 123     sqlite3_free(pHash->aSlot);
 124     sqlite3_free(pHash);
 125   }
 126 }
 127
 128 /*
 129 ** Empty (but do not delete) a hash table.
 130 */
 131 void sqlite3Fts5HashClear(Fts5Hash *pHash){
 132   int i;
 133   for(i=0; i<pHash->nSlot; i++){
 134     Fts5HashEntry *pNext;
 135     Fts5HashEntry *pSlot;
 136     for(pSlot=pHash->aSlot[i]; pSlot; pSlot=pNext){
 137       pNext = pSlot->pHashNext;
 138       sqlite3_free(pSlot);
 139     }
 140   }
 141   memset(pHash->aSlot, 0, pHash->nSlot * sizeof(Fts5HashEntry*));
 142   pHash->nEntry = 0;
 143 }
 144
 145 static unsigned int fts5HashKey(int nSlot, const u8 *p, int n){
 146   int i;
 147   unsigned int h = 13;
 148   for(i=n-1; i>=0; i--){
 149     h = (h << 3) ^ h ^ p[i];
 150   }
 151   return (h % nSlot);
 152 }
 153
 154 static unsigned int fts5HashKey2(int nSlot, u8 b, const u8 *p, int n){
 155   int i;
 156   unsigned int h = 13;
 157   for(i=n-1; i>=0; i--){
 158     h = (h << 3) ^ h ^ p[i];
 159   }
 160   h = (h << 3) ^ h ^ b;
 161   return (h % nSlot);
 162 }
 163
 164 /*
 165 ** Resize the hash table by doubling the number of slots.
 166 */
 167 static int fts5HashResize(Fts5Hash *pHash){
 168   int nNew = pHash->nSlot*2;
 169   int i;
 170   Fts5HashEntry **apNew;
 171   Fts5HashEntry **apOld = pHash->aSlot;
 172
 173   apNew = (Fts5HashEntry**)sqlite3_malloc64(nNew*sizeof(Fts5HashEntry*));
 174   if( !apNew ) return SQLITE_NOMEM;
 175   memset(apNew, 0, nNew*sizeof(Fts5HashEntry*));
 176
 177   for(i=0; i<pHash->nSlot; i++){
 178     while( apOld[i] ){
 179       unsigned int iHash;
 180       Fts5HashEntry *p = apOld[i];
 181       apOld[i] = p->pHashNext;
 182       iHash = fts5HashKey(nNew, (u8*)fts5EntryKey(p), p->nKey);
 183       p->pHashNext = apNew[iHash];
 184       apNew[iHash] = p;
 185     }
 186   }
 187
 188   sqlite3_free(apOld);
 189   pHash->nSlot = nNew;
 190   pHash->aSlot = apNew;
 191   return SQLITE_OK;
 192 }
 193
 194 static int fts5HashAddPoslistSize(
 195   Fts5Hash *pHash,
 196   Fts5HashEntry *p,
 197   Fts5HashEntry *p2
 198 ){
 199   int nRet = 0;
 200   if( p->iSzPoslist ){
 201     u8 *pPtr = p2 ? (u8*)p2 : (u8*)p;
 202     int nData = p->nData;
 203     if( pHash->eDetail==FTS5_DETAIL_NONE ){
 204       assert( nData==p->iSzPoslist );
 205       if( p->bDel ){
 206         pPtr[nData++] = 0x00;
 207         if( p->bContent ){
 208           pPtr[nData++] = 0x00;
 209         }
 210       }
 211     }else{
 212       int nSz = (nData - p->iSzPoslist - 1);       /* Size in bytes */
 213       int nPos = nSz*2 + p->bDel;                     /* Value of nPos field */
 214
 215       assert( p->bDel==0 || p->bDel==1 );
 216       if( nPos<=127 ){
 217         pPtr[p->iSzPoslist] = (u8)nPos;
 218       }else{
 219         int nByte = sqlite3Fts5GetVarintLen((u32)nPos);
 220         memmove(&pPtr[p->iSzPoslist + nByte], &pPtr[p->iSzPoslist + 1], nSz);
 221         sqlite3Fts5PutVarint(&pPtr[p->iSzPoslist], nPos);
 222         nData += (nByte-1);
 223       }
 224     }
 225
 226     nRet = nData - p->nData;
 227     if( p2==0 ){
 228       p->iSzPoslist = 0;
 229       p->bDel = 0;
 230       p->bContent = 0;
 231       p->nData = nData;
 232     }
 233   }
 234   return nRet;
 235 }
 236
 237 /*
 238 ** Add an entry to the in-memory hash table. The key is the concatenation
 239 ** of bByte and (pToken/nToken). The value is (iRowid/iCol/iPos).
 240 **
 241 **     (bByte || pToken) -> (iRowid,iCol,iPos)
 242 **
 243 ** Or, if iCol is negative, then the value is a delete marker.
 244 */
 245 int sqlite3Fts5HashWrite(
 246   Fts5Hash *pHash,
 247   i64 iRowid,                     /* Rowid for this entry */
 248   int iCol,                       /* Column token appears in (-ve -> delete) */
 249   int iPos,                       /* Position of token within column */
 250   char bByte,                     /* First byte of token */
 251   const char *pToken, int nToken  /* Token to add or remove to or from index */
 252 ){
 253   unsigned int iHash;
 254   Fts5HashEntry *p;
 255   u8 *pPtr;
 256   int nIncr = 0;                  /* Amount to increment (*pHash->pnByte) by */
 257   int bNew;                       /* If non-delete entry should be written */
 258
 259   bNew = (pHash->eDetail==FTS5_DETAIL_FULL);
 260
 261   /* Attempt to locate an existing hash entry */
 262   iHash = fts5HashKey2(pHash->nSlot, (u8)bByte, (const u8*)pToken, nToken);
 263   for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
 264     char *zKey = fts5EntryKey(p);
 265     if( zKey[0]==bByte
 266      && p->nKey==nToken+1
 267      && memcmp(&zKey[1], pToken, nToken)==0
 268     ){
 269       break;
 270     }
 271   }
 272
 273   /* If an existing hash entry cannot be found, create a new one. */
 274   if( p==0 ){
 275     /* Figure out how much space to allocate */
 276     char *zKey;
 277     sqlite3_int64 nByte = sizeof(Fts5HashEntry) + (nToken+1) + 1 + 64;
 278     if( nByte<128 ) nByte = 128;
 279
 280     /* Grow the Fts5Hash.aSlot[] array if necessary. */
 281     if( (pHash->nEntry*2)>=pHash->nSlot ){
 282       int rc = fts5HashResize(pHash);
 283       if( rc!=SQLITE_OK ) return rc;
 284       iHash = fts5HashKey2(pHash->nSlot, (u8)bByte, (const u8*)pToken, nToken);
 285     }
 286
 287     /* Allocate new Fts5HashEntry and add it to the hash table. */
 288     p = (Fts5HashEntry*)sqlite3_malloc64(nByte);
 289     if( !p ) return SQLITE_NOMEM;
 290     memset(p, 0, sizeof(Fts5HashEntry));
 291     p->nAlloc = (int)nByte;
 292     zKey = fts5EntryKey(p);
 293     zKey[0] = bByte;
 294     memcpy(&zKey[1], pToken, nToken);
 295     assert( iHash==fts5HashKey(pHash->nSlot, (u8*)zKey, nToken+1) );
 296     p->nKey = nToken+1;
 297     zKey[nToken+1] = '\0';
 298     p->nData = nToken+1 + sizeof(Fts5HashEntry);
 299     p->pHashNext = pHash->aSlot[iHash];
 300     pHash->aSlot[iHash] = p;
 301     pHash->nEntry++;
 302
 303     /* Add the first rowid field to the hash-entry */
 304     p->nData += sqlite3Fts5PutVarint(&((u8*)p)[p->nData], iRowid);
 305     p->iRowid = iRowid;
 306
 307     p->iSzPoslist = p->nData;
 308     if( pHash->eDetail!=FTS5_DETAIL_NONE ){
 309       p->nData += 1;
 310       p->iCol = (pHash->eDetail==FTS5_DETAIL_FULL ? 0 : -1);
 311     }
 312
 313   }else{
 314
 315     /* Appending to an existing hash-entry. Check that there is enough
 316     ** space to append the largest possible new entry. Worst case scenario
 317     ** is:
 318     **
 319     **     + 9 bytes for a new rowid,
 320     **     + 4 byte reserved for the "poslist size" varint.
 321     **     + 1 byte for a "new column" byte,
 322     **     + 3 bytes for a new column number (16-bit max) as a varint,
 323     **     + 5 bytes for the new position offset (32-bit max).
 324     */
 325     if( (p->nAlloc - p->nData) < (9 + 4 + 1 + 3 + 5) ){
 326       sqlite3_int64 nNew = p->nAlloc * 2;
 327       Fts5HashEntry *pNew;
 328       Fts5HashEntry **pp;
 329       pNew = (Fts5HashEntry*)sqlite3_realloc64(p, nNew);
 330       if( pNew==0 ) return SQLITE_NOMEM;
 331       pNew->nAlloc = (int)nNew;
 332       for(pp=&pHash->aSlot[iHash]; *pp!=p; pp=&(*pp)->pHashNext);
 333       *pp = pNew;
 334       p = pNew;
 335     }
 336     nIncr -= p->nData;
 337   }
 338   assert( (p->nAlloc - p->nData) >= (9 + 4 + 1 + 3 + 5) );
 339
 340   pPtr = (u8*)p;
 341
 342   /* If this is a new rowid, append the 4-byte size field for the previous
 343   ** entry, and the new rowid for this entry.  */
 344   if( iRowid!=p->iRowid ){
 345     u64 iDiff = (u64)iRowid - (u64)p->iRowid;
 346     fts5HashAddPoslistSize(pHash, p, 0);
 347     p->nData += sqlite3Fts5PutVarint(&pPtr[p->nData], iDiff);
 348     p->iRowid = iRowid;
 349     bNew = 1;
 350     p->iSzPoslist = p->nData;
 351     if( pHash->eDetail!=FTS5_DETAIL_NONE ){
 352       p->nData += 1;
 353       p->iCol = (pHash->eDetail==FTS5_DETAIL_FULL ? 0 : -1);
 354       p->iPos = 0;
 355     }
 356   }
 357
 358   if( iCol>=0 ){
 359     if( pHash->eDetail==FTS5_DETAIL_NONE ){
 360       p->bContent = 1;
 361     }else{
 362       /* Append a new column value, if necessary */
 363       assert_nc( iCol>=p->iCol );
 364       if( iCol!=p->iCol ){
 365         if( pHash->eDetail==FTS5_DETAIL_FULL ){
 366           pPtr[p->nData++] = 0x01;
 367           p->nData += sqlite3Fts5PutVarint(&pPtr[p->nData], iCol);
 368           p->iCol = (i16)iCol;
 369           p->iPos = 0;
 370         }else{
 371           bNew = 1;
 372           p->iCol = (i16)(iPos = iCol);
 373         }
 374       }
 375
 376       /* Append the new position offset, if necessary */
 377       if( bNew ){
 378         p->nData += sqlite3Fts5PutVarint(&pPtr[p->nData], iPos - p->iPos + 2);
 379         p->iPos = iPos;
 380       }
 381     }
 382   }else{
 383     /* This is a delete. Set the delete flag. */
 384     p->bDel = 1;
 385   }
 386
 387   nIncr += p->nData;
 388   *pHash->pnByte += nIncr;
 389   return SQLITE_OK;
 390 }
 391
 392
 393 /*
 394 ** Arguments pLeft and pRight point to linked-lists of hash-entry objects,
 395 ** each sorted in key order. This function merges the two lists into a
 396 ** single list and returns a pointer to its first element.
 397 */
 398 static Fts5HashEntry *fts5HashEntryMerge(
 399   Fts5HashEntry *pLeft,
 400   Fts5HashEntry *pRight
 401 ){
 402   Fts5HashEntry *p1 = pLeft;
 403   Fts5HashEntry *p2 = pRight;
 404   Fts5HashEntry *pRet = 0;
 405   Fts5HashEntry **ppOut = &pRet;
 406
 407   while( p1 || p2 ){
 408     if( p1==0 ){
 409       *ppOut = p2;
 410       p2 = 0;
 411     }else if( p2==0 ){
 412       *ppOut = p1;
 413       p1 = 0;
 414     }else{
 415       char *zKey1 = fts5EntryKey(p1);
 416       char *zKey2 = fts5EntryKey(p2);
 417       int nMin = MIN(p1->nKey, p2->nKey);
 418
 419       int cmp = memcmp(zKey1, zKey2, nMin);
 420       if( cmp==0 ){
 421         cmp = p1->nKey - p2->nKey;
 422       }
 423       assert( cmp!=0 );
 424
 425       if( cmp>0 ){
 426         /* p2 is smaller */
 427         *ppOut = p2;
 428         ppOut = &p2->pScanNext;
 429         p2 = p2->pScanNext;
 430       }else{
 431         /* p1 is smaller */
 432         *ppOut = p1;
 433         ppOut = &p1->pScanNext;
 434         p1 = p1->pScanNext;
 435       }
 436       *ppOut = 0;
 437     }
 438   }
 439
 440   return pRet;
 441 }
 442
 443 /*
 444 ** Link all tokens from hash table iHash into a list in sorted order. The
 445 ** tokens are not removed from the hash table.
 446 */
 447 static int fts5HashEntrySort(
 448   Fts5Hash *pHash,
 449   const char *pTerm, int nTerm,   /* Query prefix, if any */
 450   Fts5HashEntry **ppSorted
 451 ){
 452   const int nMergeSlot = 32;
 453   Fts5HashEntry **ap;
 454   Fts5HashEntry *pList;
 455   int iSlot;
 456   int i;
 457
 458   *ppSorted = 0;
 459   ap = sqlite3_malloc64(sizeof(Fts5HashEntry*) * nMergeSlot);
 460   if( !ap ) return SQLITE_NOMEM;
 461   memset(ap, 0, sizeof(Fts5HashEntry*) * nMergeSlot);
 462
 463   for(iSlot=0; iSlot<pHash->nSlot; iSlot++){
 464     Fts5HashEntry *pIter;
 465     for(pIter=pHash->aSlot[iSlot]; pIter; pIter=pIter->pHashNext){
 466       if( pTerm==0
 467        || (pIter->nKey>=nTerm && 0==memcmp(fts5EntryKey(pIter), pTerm, nTerm))
 468       ){
 469         Fts5HashEntry *pEntry = pIter;
 470         pEntry->pScanNext = 0;
 471         for(i=0; ap[i]; i++){
 472           pEntry = fts5HashEntryMerge(pEntry, ap[i]);
 473           ap[i] = 0;
 474         }
 475         ap[i] = pEntry;
 476       }
 477     }
 478   }
 479
 480   pList = 0;
 481   for(i=0; i<nMergeSlot; i++){
 482     pList = fts5HashEntryMerge(pList, ap[i]);
 483   }
 484
 485   sqlite3_free(ap);
 486   *ppSorted = pList;
 487   return SQLITE_OK;
 488 }
 489
 490 /*
 491 ** Query the hash table for a doclist associated with term pTerm/nTerm.
 492 */
 493 int sqlite3Fts5HashQuery(
 494   Fts5Hash *pHash,                /* Hash table to query */
 495   int nPre,
 496   const char *pTerm, int nTerm,   /* Query term */
 497   void **ppOut,                   /* OUT: Pointer to new object */
 498   int *pnDoclist                  /* OUT: Size of doclist in bytes */
 499 ){
 500   unsigned int iHash = fts5HashKey(pHash->nSlot, (const u8*)pTerm, nTerm);
 501   char *zKey = 0;
 502   Fts5HashEntry *p;
 503
 504   for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
 505     zKey = fts5EntryKey(p);
 506     if( nTerm==p->nKey && memcmp(zKey, pTerm, nTerm)==0 ) break;
 507   }
 508
 509   if( p ){
 510     int nHashPre = sizeof(Fts5HashEntry) + nTerm;
 511     int nList = p->nData - nHashPre;
 512     u8 *pRet = (u8*)(*ppOut = sqlite3_malloc64(nPre + nList + 10));
 513     if( pRet ){
 514       Fts5HashEntry *pFaux = (Fts5HashEntry*)&pRet[nPre-nHashPre];
 515       memcpy(&pRet[nPre], &((u8*)p)[nHashPre], nList);
 516       nList += fts5HashAddPoslistSize(pHash, p, pFaux);
 517       *pnDoclist = nList;
 518     }else{
 519       *pnDoclist = 0;
 520       return SQLITE_NOMEM;
 521     }
 522   }else{
 523     *ppOut = 0;
 524     *pnDoclist = 0;
 525   }
 526
 527   return SQLITE_OK;
 528 }
 529
 530 int sqlite3Fts5HashScanInit(
 531   Fts5Hash *p,                    /* Hash table to query */
 532   const char *pTerm, int nTerm    /* Query prefix */
 533 ){
 534   return fts5HashEntrySort(p, pTerm, nTerm, &p->pScan);
 535 }
 536
 537 #ifdef SQLITE_DEBUG
 538 static int fts5HashCount(Fts5Hash *pHash){
 539   int nEntry = 0;
 540   int ii;
 541   for(ii=0; ii<pHash->nSlot; ii++){
 542     Fts5HashEntry *p = 0;
 543     for(p=pHash->aSlot[ii]; p; p=p->pHashNext){
 544       nEntry++;
 545     }
 546   }
 547   return nEntry;
 548 }
 549 #endif
 550
 551 /*
 552 ** Return true if the hash table is empty, false otherwise.
 553 */
 554 int sqlite3Fts5HashIsEmpty(Fts5Hash *pHash){
 555   assert( pHash->nEntry==fts5HashCount(pHash) );
 556   return pHash->nEntry==0;
 557 }
 558
 559 void sqlite3Fts5HashScanNext(Fts5Hash *p){
 560   assert( !sqlite3Fts5HashScanEof(p) );
 561   p->pScan = p->pScan->pScanNext;
 562 }
 563
 564 int sqlite3Fts5HashScanEof(Fts5Hash *p){
 565   return (p->pScan==0);
 566 }
 567
 568 void sqlite3Fts5HashScanEntry(
 569   Fts5Hash *pHash,
 570   const char **pzTerm,            /* OUT: term (nul-terminated) */
 571   int *pnTerm,                    /* OUT: Size of term in bytes */
 572   const u8 **ppDoclist,           /* OUT: pointer to doclist */
 573   int *pnDoclist                  /* OUT: size of doclist in bytes */
 574 ){
 575   Fts5HashEntry *p;
 576   if( (p = pHash->pScan) ){
 577     char *zKey = fts5EntryKey(p);
 578     int nTerm = p->nKey;
 579     fts5HashAddPoslistSize(pHash, p, 0);
 580     *pzTerm = zKey;
 581     *pnTerm = nTerm;
 582     *ppDoclist = (const u8*)&zKey[nTerm];
 583     *pnDoclist = p->nData - (sizeof(Fts5HashEntry) + nTerm);
 584   }else{
 585     *pzTerm = 0;
 586     *pnTerm = 0;
 587     *ppDoclist = 0;
 588     *pnDoclist = 0;
 589   }
 590 }