/ Check-in [ad6286ab]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Remove a potentially undefined behaviour involving signed integers and bitshift operations from fts5_hash.c.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5-btree-index
Files: files | file ages | folders
SHA1: ad6286ab1f40e4716456a67b719f9cd733f988eb
User & Date: dan 2015-07-27 11:01:19
Context
2015-07-27
11:43
Minor tweak to the SQL schema used by fts5. check-in: 427bf09b user: dan tags: fts5-btree-index
11:01
Remove a potentially undefined behaviour involving signed integers and bitshift operations from fts5_hash.c. check-in: ad6286ab user: dan tags: fts5-btree-index
10:46
Merge latest trunk changes with this branch. check-in: 5ec933c2 user: dan tags: fts5-btree-index
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_hash.c.

129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
...
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
...
206
207
208
209
210
211
212
213
214
215
216
217
218

219
220
221
222
223
224
225
...
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
...
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
      sqlite3_free(pSlot);
    }
  }
  memset(pHash->aSlot, 0, pHash->nSlot * sizeof(Fts5HashEntry*));
  pHash->nEntry = 0;
}

static unsigned int fts5HashKey(int nSlot, const char *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);
}

static unsigned int fts5HashKey2(int nSlot, char b, const char *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);
................................................................................
  memset(apNew, 0, nNew*sizeof(Fts5HashEntry*));

  for(i=0; i<pHash->nSlot; i++){
    while( apOld[i] ){
      int iHash;
      Fts5HashEntry *p = apOld[i];
      apOld[i] = p->pHashNext;
      iHash = fts5HashKey(nNew, p->zKey, strlen(p->zKey));
      p->pHashNext = apNew[iHash];
      apNew[iHash] = p;
    }
  }

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
................................................................................
  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 = fts5HashKey2(pHash->nSlot, bByte, pToken, nToken);
  Fts5HashEntry *p;
  u8 *pPtr;
  int nIncr = 0;                  /* Amount to increment (*pHash->pnByte) by */

  /* Attempt to locate an existing hash entry */

  for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
    if( p->zKey[0]==bByte 
     && memcmp(&p->zKey[1], pToken, nToken)==0 
     && p->zKey[nToken+1]==0 
    ){
      break;
    }
................................................................................
  if( p==0 ){
    int nByte = FTS5_HASHENTRYSIZE + (nToken+1) + 1 + 64;
    if( nByte<128 ) nByte = 128;

    if( (pHash->nEntry*2)>=pHash->nSlot ){
      int rc = fts5HashResize(pHash);
      if( rc!=SQLITE_OK ) return rc;
      iHash = fts5HashKey2(pHash->nSlot, bByte, pToken, nToken);
    }

    p = (Fts5HashEntry*)sqlite3_malloc(nByte);
    if( !p ) return SQLITE_NOMEM;
    memset(p, 0, FTS5_HASHENTRYSIZE);
    p->nAlloc = nByte;
    p->zKey[0] = bByte;
    memcpy(&p->zKey[1], pToken, nToken);
    assert( iHash==fts5HashKey(pHash->nSlot, p->zKey, nToken+1) );
    p->zKey[nToken+1] = '\0';
    p->nData = nToken+1 + 1 + FTS5_HASHENTRYSIZE;
    p->nData += sqlite3Fts5PutVarint(&((u8*)p)[p->nData], iRowid);
    p->iSzPoslist = p->nData;
    p->nData += 1;
    p->iRowid = iRowid;
    p->pHashNext = pHash->aSlot[iHash];
................................................................................
*/
int sqlite3Fts5HashQuery(
  Fts5Hash *pHash,                /* Hash table to query */
  const char *pTerm, int nTerm,   /* Query term */
  const u8 **ppDoclist,           /* OUT: Pointer to doclist for pTerm */
  int *pnDoclist                  /* OUT: Size of doclist in bytes */
){
  unsigned int iHash = fts5HashKey(pHash->nSlot, pTerm, nTerm);
  Fts5HashEntry *p;

  for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
    if( memcmp(p->zKey, pTerm, nTerm)==0 && p->zKey[nTerm]==0 ) break;
  }

  if( p ){







|








|







 







|







 







|





>







 







|








|







 







|







129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
...
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
...
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
...
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
...
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
      sqlite3_free(pSlot);
    }
  }
  memset(pHash->aSlot, 0, pHash->nSlot * sizeof(Fts5HashEntry*));
  pHash->nEntry = 0;
}

static unsigned 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);
}

static unsigned 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);
................................................................................
  memset(apNew, 0, nNew*sizeof(Fts5HashEntry*));

  for(i=0; i<pHash->nSlot; i++){
    while( apOld[i] ){
      int iHash;
      Fts5HashEntry *p = apOld[i];
      apOld[i] = p->pHashNext;
      iHash = fts5HashKey(nNew, (u8*)p->zKey, strlen(p->zKey));
      p->pHashNext = apNew[iHash];
      apNew[iHash] = p;
    }
  }

  sqlite3_free(apOld);
  pHash->nSlot = nNew;
................................................................................
  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 */

  /* Attempt to locate an existing hash entry */
  iHash = fts5HashKey2(pHash->nSlot, (u8)bByte, (const u8*)pToken, nToken);
  for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
    if( p->zKey[0]==bByte 
     && memcmp(&p->zKey[1], pToken, nToken)==0 
     && p->zKey[nToken+1]==0 
    ){
      break;
    }
................................................................................
  if( p==0 ){
    int nByte = FTS5_HASHENTRYSIZE + (nToken+1) + 1 + 64;
    if( nByte<128 ) nByte = 128;

    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);
    }

    p = (Fts5HashEntry*)sqlite3_malloc(nByte);
    if( !p ) return SQLITE_NOMEM;
    memset(p, 0, FTS5_HASHENTRYSIZE);
    p->nAlloc = nByte;
    p->zKey[0] = bByte;
    memcpy(&p->zKey[1], pToken, nToken);
    assert( iHash==fts5HashKey(pHash->nSlot, (u8*)p->zKey, nToken+1) );
    p->zKey[nToken+1] = '\0';
    p->nData = nToken+1 + 1 + FTS5_HASHENTRYSIZE;
    p->nData += sqlite3Fts5PutVarint(&((u8*)p)[p->nData], iRowid);
    p->iSzPoslist = p->nData;
    p->nData += 1;
    p->iRowid = iRowid;
    p->pHashNext = pHash->aSlot[iHash];
................................................................................
*/
int sqlite3Fts5HashQuery(
  Fts5Hash *pHash,                /* Hash table to query */
  const char *pTerm, int nTerm,   /* Query term */
  const u8 **ppDoclist,           /* OUT: Pointer to doclist for pTerm */
  int *pnDoclist                  /* OUT: Size of doclist in bytes */
){
  unsigned int iHash = fts5HashKey(pHash->nSlot, (const u8*)pTerm, nTerm);
  Fts5HashEntry *p;

  for(p=pHash->aSlot[iHash]; p; p=p->pHashNext){
    if( memcmp(p->zKey, pTerm, nTerm)==0 && p->zKey[nTerm]==0 ) break;
  }

  if( p ){