Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Cleanup the hash functions in FTS3. (CVS 4440) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
ac645c8f30aac0d98fc481260084c9bd |
User & Date: | drh 2007-09-20 12:53:28.000 |
Context
2007-09-20
| ||
14:39 | Replace "i64" with "sqlite3_int64" in the w32 VFS. (CVS 4441) (check-in: 138d3fcc5a user: drh tags: trunk) | |
12:53 | Cleanup the hash functions in FTS3. (CVS 4440) (check-in: ac645c8f30 user: drh tags: trunk) | |
11:34 | get rid of remaining GCC 4.3 -Wall compiler warnings by initializing two variables and one structure properly (although the code path was already rather safe) (CVS 4439) (check-in: d748694f8d user: rse tags: trunk) | |
Changes
Changes to ext/fts3/fts3_hash.c.
︙ | ︙ | |||
27 28 29 30 31 32 33 | #include <assert.h> #include <stdlib.h> #include <string.h> #include "fts3_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 "fts3_hash.h" /* ** Malloc and Free functions */ static void *fts3HashMalloc(int n){ void *p = sqlite3_malloc(n); if( p ){ memset(p, 0, n); } return p; } static void fts3HashFree(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>=FTS3_HASH_STRING && keyClass<=FTS3_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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 | assert( keyClass>=FTS3_HASH_STRING && keyClass<=FTS3_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 sqlite3Fts3HashClear(fts3Hash *pH){ fts3HashElem *elem; /* For looping over all elements of the table */ assert( pH!=0 ); elem = pH->first; pH->first = 0; fts3HashFree(pH->ht); pH->ht = 0; pH->htsize = 0; while( elem ){ fts3HashElem *next_elem = elem->next; if( pH->copyKey && elem->pKey ){ fts3HashFree(elem->pKey); } fts3HashFree(elem); elem = next_elem; } pH->count = 0; } /* ** Hash and comparison functions when the mode is FTS3_HASH_STRING */ static int fts3StrHash(const void *pKey, int nKey){ const char *z = (const char *)pKey; int h = 0; if( nKey<=0 ) nKey = (int) strlen(z); while( nKey > 0 ){ h = (h<<3) ^ h ^ *z++; nKey--; } return h & 0x7fffffff; } static int fts3StrCompare(const void *pKey1, int n1, const void *pKey2, int n2){ if( n1!=n2 ) return 1; return strncmp((const char*)pKey1,(const char*)pKey2,n1); } /* ** Hash and comparison functions when the mode is FTS3_HASH_BINARY */ static int fts3BinHash(const void *pKey, int nKey){ int h = 0; const char *z = (const char *)pKey; while( nKey-- > 0 ){ h = (h<<3) ^ h ^ *(z++); } return h & 0x7fffffff; } static int fts3BinCompare(const void *pKey1, int n1, const void *pKey2, int n2){ if( n1!=n2 ) return 1; return memcmp(pKey1,pKey2,n1); } /* ** Return a pointer to the appropriate hash function given the key class. ** ** The C syntax in this function definition may be unfamilar to some ** programmers, so we provide the following additional explanation: ** ** The name of the function is "hashFunction". The function takes a ** single parameter "keyClass". The return value of hashFunction() ** is a pointer to another function. Specifically, the return value ** of hashFunction() is a pointer to a function that takes two parameters ** with types "const void*" and "int" and returns an "int". */ static int (*hashFunction(int keyClass))(const void*,int){ if( keyClass==FTS3_HASH_STRING ){ return &fts3StrHash; }else{ assert( keyClass==FTS3_HASH_BINARY ); return &fts3BinHash; } } /* ** Return a pointer to the appropriate hash function given the key class. ** ** For help in interpreted the obscure C code in the function definition, ** see the header comment on the previous function. */ static int (*compareFunction(int keyClass))(const void*,int,const void*,int){ if( keyClass==FTS3_HASH_STRING ){ return &fts3StrCompare; }else{ assert( keyClass==FTS3_HASH_BINARY ); return &fts3BinCompare; } } /* Link an element into the hash table */ static void fts3HashInsertElement( fts3Hash *pH, /* The complete hash table */ struct _fts3ht *pEntry, /* The entry into which pNew is inserted */ fts3HashElem *pNew /* The element to be inserted */ ){ fts3HashElem *pHead; /* First element already in pEntry */ pHead = pEntry->chain; if( pHead ){ |
︙ | ︙ | |||
182 183 184 185 186 187 188 | } /* Resize the hash table so that it cantains "new_size" buckets. ** "new_size" must be a power of 2. The hash table might fail ** to resize if sqliteMalloc() fails. */ | | | | | | | 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 | } /* Resize the hash table so that it cantains "new_size" buckets. ** "new_size" must be a power of 2. The hash table might fail ** to resize if sqliteMalloc() fails. */ static void fts3Rehash(fts3Hash *pH, int new_size){ struct _fts3ht *new_ht; /* The new hash table */ fts3HashElem *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 _fts3ht *)fts3HashMalloc( new_size*sizeof(struct _fts3ht) ); if( new_ht==0 ) return; fts3HashFree(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; fts3HashInsertElement(pH, &new_ht[h], elem); } } /* This function (for internal use only) locates an element in an ** hash table that matches the given key. The hash for this key has ** already been computed and is passed as the 4th parameter. */ static fts3HashElem *fts3FindElementByHash( const fts3Hash *pH, /* The pH to be searched */ const void *pKey, /* The key we are searching for */ int nKey, int h /* The hash for this key. */ ){ fts3HashElem *elem; /* Used to loop thru the element list */ int count; /* Number of elements left to test */ |
︙ | ︙ | |||
233 234 235 236 237 238 239 | } return 0; } /* Remove a single entry from the hash table given a pointer to that ** element and a hash on the element's key. */ | | | 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 | } return 0; } /* Remove a single entry from the hash table given a pointer to that ** element and a hash on the element's key. */ static void fts3RemoveElementByHash( fts3Hash *pH, /* The pH containing "elem" */ fts3HashElem* elem, /* The element to be removed from the pH */ int h /* Hash value for the element */ ){ struct _fts3ht *pEntry; if( elem->prev ){ elem->prev->next = elem->next; |
︙ | ︙ | |||
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 ){ fts3HashFree(elem->pKey); } fts3HashFree( elem ); pH->count--; if( pH->count<=0 ){ assert( pH->first==0 ); assert( pH->count==0 ); fts3HashClear(pH); } } |
︙ | ︙ | |||
281 282 283 284 285 286 287 | int (*xHash)(const void*,int); /* The hash function */ if( pH==0 || pH->ht==0 ) return 0; xHash = hashFunction(pH->keyClass); assert( xHash!=0 ); h = (*xHash)(pKey,nKey); assert( (pH->htsize & (pH->htsize-1))==0 ); | | | 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 | int (*xHash)(const void*,int); /* The hash function */ if( pH==0 || pH->ht==0 ) return 0; xHash = hashFunction(pH->keyClass); assert( xHash!=0 ); h = (*xHash)(pKey,nKey); assert( (pH->htsize & (pH->htsize-1))==0 ); elem = fts3FindElementByHash(pH,pKey,nKey, h & (pH->htsize-1)); return elem ? elem->data : 0; } /* Insert an element into the hash table pH. The key is pKey,nKey ** and the data is "data". ** ** If no element exists with a matching key, then a new |
︙ | ︙ | |||
318 319 320 321 322 323 324 | assert( pH!=0 ); xHash = hashFunction(pH->keyClass); assert( xHash!=0 ); hraw = (*xHash)(pKey, nKey); assert( (pH->htsize & (pH->htsize-1))==0 ); h = hraw & (pH->htsize-1); | | | | | | | | | | | 322 323 324 325 326 327 328 329 330 331 332 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 366 367 368 369 370 371 372 373 | assert( pH!=0 ); xHash = hashFunction(pH->keyClass); assert( xHash!=0 ); hraw = (*xHash)(pKey, nKey); assert( (pH->htsize & (pH->htsize-1))==0 ); h = hraw & (pH->htsize-1); elem = fts3FindElementByHash(pH,pKey,nKey,h); if( elem ){ void *old_data = elem->data; if( data==0 ){ fts3RemoveElementByHash(pH,elem,h); }else{ elem->data = data; } return old_data; } if( data==0 ) return 0; new_elem = (fts3HashElem*)fts3HashMalloc( sizeof(fts3HashElem) ); if( new_elem==0 ) return data; if( pH->copyKey && pKey!=0 ){ new_elem->pKey = fts3HashMalloc( nKey ); if( new_elem->pKey==0 ){ fts3HashFree(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 ){ fts3Rehash(pH,8); if( pH->htsize==0 ){ pH->count = 0; fts3HashFree(new_elem); return data; } } if( pH->count > pH->htsize ){ fts3Rehash(pH,pH->htsize*2); } assert( pH->htsize>0 ); assert( (pH->htsize & (pH->htsize-1))==0 ); h = hraw & (pH->htsize-1); fts3HashInsertElement(pH, &pH->ht[h], new_elem); new_elem->data = data; return 0; } #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */ |
Changes to ext/fts3/fts3_hash.h.
︙ | ︙ | |||
30 31 32 33 34 35 36 | ** this structure opaque. */ struct fts3Hash { 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 */ fts3HashElem *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 fts3Hash { 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 */ fts3HashElem *first; /* The first element of the array */ int htsize; /* Number of buckets in the hash table */ struct _fts3ht { /* the hash table */ int count; /* Number of entries with this hash */ fts3HashElem *chain; /* Pointer to first entry with this hash */ } *ht; }; |
︙ | ︙ |