Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Cleanup the hash functions in FTS2. Backports (4440) from fts3. (CVS 5452) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
e31d2f875c13ee41742c9aaee6291662 |
User & Date: | shess 2008-07-22 22:15:48.000 |
Context
2008-07-22
| ||
22:20 | fts2.c buildTerms() passes -1 for nInput. Backports (4511) from fts3. (CVS 5453) (check-in: d562515e1c user: shess tags: trunk) | |
22:15 | Cleanup the hash functions in FTS2. Backports (4440) from fts3. (CVS 5452) (check-in: e31d2f875c user: shess tags: trunk) | |
18:45 | Documentation updates. No changes to code. (CVS 5451) (check-in: e58b49779b user: drh tags: trunk) | |
Changes
Changes to ext/fts2/fts2_hash.c.
︙ | ︙ | |||
27 28 29 30 31 32 33 | #include <assert.h> #include <stdlib.h> #include <string.h> #include "fts2_hash.h" | > > > | | > > > | 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <assert.h> #include <stdlib.h> #include <string.h> #include "fts2_hash.h" /* ** Malloc and Free functions */ static void *fts2HashMalloc(int n){ void *p = sqlite3_malloc(n); if( p ){ memset(p, 0, n); } return p; } static void fts2HashFree(void *p){ sqlite3_free(p); } /* Turn bulk memory into a hash table object by initializing the ** fields of the Hash structure. ** ** "pNew" is a pointer to the hash table that is to be initialized. ** keyClass is one of the constants |
︙ | ︙ | |||
54 55 56 57 58 59 60 | assert( keyClass>=FTS2_HASH_STRING && keyClass<=FTS2_HASH_BINARY ); pNew->keyClass = keyClass; pNew->copyKey = copyKey; pNew->first = 0; pNew->count = 0; pNew->htsize = 0; pNew->ht = 0; | < < | | | | 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | assert( keyClass>=FTS2_HASH_STRING && keyClass<=FTS2_HASH_BINARY ); pNew->keyClass = keyClass; pNew->copyKey = copyKey; pNew->first = 0; pNew->count = 0; pNew->htsize = 0; pNew->ht = 0; } /* Remove all entries from a hash table. Reclaim all memory. ** Call this routine to delete a hash table or to reset a hash table ** to the empty state. */ void sqlite3Fts2HashClear(fts2Hash *pH){ fts2HashElem *elem; /* For looping over all elements of the table */ assert( pH!=0 ); elem = pH->first; pH->first = 0; fts2HashFree(pH->ht); pH->ht = 0; pH->htsize = 0; while( elem ){ fts2HashElem *next_elem = elem->next; if( pH->copyKey && elem->pKey ){ fts2HashFree(elem->pKey); } fts2HashFree(elem); elem = next_elem; } pH->count = 0; } /* ** Hash and comparison functions when the mode is FTS2_HASH_STRING |
︙ | ︙ | |||
188 189 190 191 192 193 194 | */ static void rehash(fts2Hash *pH, int new_size){ struct _fts2ht *new_ht; /* The new hash table */ fts2HashElem *elem, *next_elem; /* For looping over existing elements */ int (*xHash)(const void*,int); /* The hash function */ assert( (new_size & (new_size-1))==0 ); | | | | 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 | */ static void rehash(fts2Hash *pH, int new_size){ struct _fts2ht *new_ht; /* The new hash table */ fts2HashElem *elem, *next_elem; /* For looping over existing elements */ int (*xHash)(const void*,int); /* The hash function */ assert( (new_size & (new_size-1))==0 ); new_ht = (struct _fts2ht *)fts2HashMalloc( new_size*sizeof(struct _fts2ht) ); if( new_ht==0 ) return; fts2HashFree(pH->ht); pH->ht = new_ht; pH->htsize = new_size; xHash = hashFunction(pH->keyClass); for(elem=pH->first, pH->first=0; elem; elem = next_elem){ int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1); next_elem = elem->next; insertElement(pH, &new_ht[h], elem); |
︙ | ︙ | |||
256 257 258 259 260 261 262 | pEntry->chain = elem->next; } pEntry->count--; if( pEntry->count<=0 ){ pEntry->chain = 0; } if( pH->copyKey && elem->pKey ){ | | | | 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 | pEntry->chain = elem->next; } pEntry->count--; if( pEntry->count<=0 ){ pEntry->chain = 0; } if( pH->copyKey && elem->pKey ){ fts2HashFree(elem->pKey); } fts2HashFree( elem ); pH->count--; if( pH->count<=0 ){ assert( pH->first==0 ); assert( pH->count==0 ); fts2HashClear(pH); } } |
︙ | ︙ | |||
329 330 331 332 333 334 335 | removeElementGivenHash(pH,elem,h); }else{ elem->data = data; } return old_data; } if( data==0 ) return 0; | | | | | | 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 | removeElementGivenHash(pH,elem,h); }else{ elem->data = data; } return old_data; } if( data==0 ) return 0; new_elem = (fts2HashElem*)fts2HashMalloc( sizeof(fts2HashElem) ); if( new_elem==0 ) return data; if( pH->copyKey && pKey!=0 ){ new_elem->pKey = fts2HashMalloc( nKey ); if( new_elem->pKey==0 ){ fts2HashFree(new_elem); return data; } memcpy((void*)new_elem->pKey, pKey, nKey); }else{ new_elem->pKey = (void*)pKey; } new_elem->nKey = nKey; pH->count++; if( pH->htsize==0 ){ rehash(pH,8); if( pH->htsize==0 ){ pH->count = 0; fts2HashFree(new_elem); return data; } } if( pH->count > pH->htsize ){ rehash(pH,pH->htsize*2); } assert( pH->htsize>0 ); |
︙ | ︙ |
Changes to ext/fts2/fts2_hash.h.
︙ | ︙ | |||
30 31 32 33 34 35 36 | ** this structure opaque. */ struct fts2Hash { char keyClass; /* HASH_INT, _POINTER, _STRING, _BINARY */ char copyKey; /* True if copy of key made on insert */ int count; /* Number of entries in this table */ fts2HashElem *first; /* The first element of the array */ | < < | 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | ** this structure opaque. */ struct fts2Hash { char keyClass; /* HASH_INT, _POINTER, _STRING, _BINARY */ char copyKey; /* True if copy of key made on insert */ int count; /* Number of entries in this table */ fts2HashElem *first; /* The first element of the array */ int htsize; /* Number of buckets in the hash table */ struct _fts2ht { /* the hash table */ int count; /* Number of entries with this hash */ fts2HashElem *chain; /* Pointer to first entry with this hash */ } *ht; }; |
︙ | ︙ |