| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 ** 2001 September 22 | |
| 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 ** This is the implementation of generic hash-tables used in SQLite. | |
| 13 ** We've modified it slightly to serve as a standalone hash table | |
| 14 ** implementation for the full-text indexing module. | |
| 15 */ | |
| 16 #include <assert.h> | |
| 17 #include <stdlib.h> | |
| 18 #include <string.h> | |
| 19 | |
| 20 /* | |
| 21 ** The code in this file is only compiled if: | |
| 22 ** | |
| 23 ** * The FTS1 module is being built as an extension | |
| 24 ** (in which case SQLITE_CORE is not defined), or | |
| 25 ** | |
| 26 ** * The FTS1 module is being built into the core of | |
| 27 ** SQLite (in which case SQLITE_ENABLE_FTS1 is defined). | |
| 28 */ | |
| 29 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS1) | |
| 30 | |
| 31 | |
| 32 #include "fts1_hash.h" | |
| 33 | |
| 34 static void *malloc_and_zero(int n){ | |
| 35 void *p = malloc(n); | |
| 36 if( p ){ | |
| 37 memset(p, 0, n); | |
| 38 } | |
| 39 return p; | |
| 40 } | |
| 41 | |
| 42 /* Turn bulk memory into a hash table object by initializing the | |
| 43 ** fields of the Hash structure. | |
| 44 ** | |
| 45 ** "pNew" is a pointer to the hash table that is to be initialized. | |
| 46 ** keyClass is one of the constants | |
| 47 ** FTS1_HASH_BINARY or FTS1_HASH_STRING. The value of keyClass | |
| 48 ** determines what kind of key the hash table will use. "copyKey" is | |
| 49 ** true if the hash table should make its own private copy of keys and | |
| 50 ** false if it should just use the supplied pointer. | |
| 51 */ | |
| 52 void sqlite3Fts1HashInit(fts1Hash *pNew, int keyClass, int copyKey){ | |
| 53 assert( pNew!=0 ); | |
| 54 assert( keyClass>=FTS1_HASH_STRING && keyClass<=FTS1_HASH_BINARY ); | |
| 55 pNew->keyClass = keyClass; | |
| 56 pNew->copyKey = copyKey; | |
| 57 pNew->first = 0; | |
| 58 pNew->count = 0; | |
| 59 pNew->htsize = 0; | |
| 60 pNew->ht = 0; | |
| 61 pNew->xMalloc = malloc_and_zero; | |
| 62 pNew->xFree = free; | |
| 63 } | |
| 64 | |
| 65 /* Remove all entries from a hash table. Reclaim all memory. | |
| 66 ** Call this routine to delete a hash table or to reset a hash table | |
| 67 ** to the empty state. | |
| 68 */ | |
| 69 void sqlite3Fts1HashClear(fts1Hash *pH){ | |
| 70 fts1HashElem *elem; /* For looping over all elements of the table */ | |
| 71 | |
| 72 assert( pH!=0 ); | |
| 73 elem = pH->first; | |
| 74 pH->first = 0; | |
| 75 if( pH->ht ) pH->xFree(pH->ht); | |
| 76 pH->ht = 0; | |
| 77 pH->htsize = 0; | |
| 78 while( elem ){ | |
| 79 fts1HashElem *next_elem = elem->next; | |
| 80 if( pH->copyKey && elem->pKey ){ | |
| 81 pH->xFree(elem->pKey); | |
| 82 } | |
| 83 pH->xFree(elem); | |
| 84 elem = next_elem; | |
| 85 } | |
| 86 pH->count = 0; | |
| 87 } | |
| 88 | |
| 89 /* | |
| 90 ** Hash and comparison functions when the mode is FTS1_HASH_STRING | |
| 91 */ | |
| 92 static int strHash(const void *pKey, int nKey){ | |
| 93 const char *z = (const char *)pKey; | |
| 94 int h = 0; | |
| 95 if( nKey<=0 ) nKey = (int) strlen(z); | |
| 96 while( nKey > 0 ){ | |
| 97 h = (h<<3) ^ h ^ *z++; | |
| 98 nKey--; | |
| 99 } | |
| 100 return h & 0x7fffffff; | |
| 101 } | |
| 102 static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){ | |
| 103 if( n1!=n2 ) return 1; | |
| 104 return strncmp((const char*)pKey1,(const char*)pKey2,n1); | |
| 105 } | |
| 106 | |
| 107 /* | |
| 108 ** Hash and comparison functions when the mode is FTS1_HASH_BINARY | |
| 109 */ | |
| 110 static int binHash(const void *pKey, int nKey){ | |
| 111 int h = 0; | |
| 112 const char *z = (const char *)pKey; | |
| 113 while( nKey-- > 0 ){ | |
| 114 h = (h<<3) ^ h ^ *(z++); | |
| 115 } | |
| 116 return h & 0x7fffffff; | |
| 117 } | |
| 118 static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){ | |
| 119 if( n1!=n2 ) return 1; | |
| 120 return memcmp(pKey1,pKey2,n1); | |
| 121 } | |
| 122 | |
| 123 /* | |
| 124 ** Return a pointer to the appropriate hash function given the key class. | |
| 125 ** | |
| 126 ** The C syntax in this function definition may be unfamilar to some | |
| 127 ** programmers, so we provide the following additional explanation: | |
| 128 ** | |
| 129 ** The name of the function is "hashFunction". The function takes a | |
| 130 ** single parameter "keyClass". The return value of hashFunction() | |
| 131 ** is a pointer to another function. Specifically, the return value | |
| 132 ** of hashFunction() is a pointer to a function that takes two parameters | |
| 133 ** with types "const void*" and "int" and returns an "int". | |
| 134 */ | |
| 135 static int (*hashFunction(int keyClass))(const void*,int){ | |
| 136 if( keyClass==FTS1_HASH_STRING ){ | |
| 137 return &strHash; | |
| 138 }else{ | |
| 139 assert( keyClass==FTS1_HASH_BINARY ); | |
| 140 return &binHash; | |
| 141 } | |
| 142 } | |
| 143 | |
| 144 /* | |
| 145 ** Return a pointer to the appropriate hash function given the key class. | |
| 146 ** | |
| 147 ** For help in interpreted the obscure C code in the function definition, | |
| 148 ** see the header comment on the previous function. | |
| 149 */ | |
| 150 static int (*compareFunction(int keyClass))(const void*,int,const void*,int){ | |
| 151 if( keyClass==FTS1_HASH_STRING ){ | |
| 152 return &strCompare; | |
| 153 }else{ | |
| 154 assert( keyClass==FTS1_HASH_BINARY ); | |
| 155 return &binCompare; | |
| 156 } | |
| 157 } | |
| 158 | |
| 159 /* Link an element into the hash table | |
| 160 */ | |
| 161 static void insertElement( | |
| 162 fts1Hash *pH, /* The complete hash table */ | |
| 163 struct _fts1ht *pEntry, /* The entry into which pNew is inserted */ | |
| 164 fts1HashElem *pNew /* The element to be inserted */ | |
| 165 ){ | |
| 166 fts1HashElem *pHead; /* First element already in pEntry */ | |
| 167 pHead = pEntry->chain; | |
| 168 if( pHead ){ | |
| 169 pNew->next = pHead; | |
| 170 pNew->prev = pHead->prev; | |
| 171 if( pHead->prev ){ pHead->prev->next = pNew; } | |
| 172 else { pH->first = pNew; } | |
| 173 pHead->prev = pNew; | |
| 174 }else{ | |
| 175 pNew->next = pH->first; | |
| 176 if( pH->first ){ pH->first->prev = pNew; } | |
| 177 pNew->prev = 0; | |
| 178 pH->first = pNew; | |
| 179 } | |
| 180 pEntry->count++; | |
| 181 pEntry->chain = pNew; | |
| 182 } | |
| 183 | |
| 184 | |
| 185 /* Resize the hash table so that it cantains "new_size" buckets. | |
| 186 ** "new_size" must be a power of 2. The hash table might fail | |
| 187 ** to resize if sqliteMalloc() fails. | |
| 188 */ | |
| 189 static void rehash(fts1Hash *pH, int new_size){ | |
| 190 struct _fts1ht *new_ht; /* The new hash table */ | |
| 191 fts1HashElem *elem, *next_elem; /* For looping over existing elements */ | |
| 192 int (*xHash)(const void*,int); /* The hash function */ | |
| 193 | |
| 194 assert( (new_size & (new_size-1))==0 ); | |
| 195 new_ht = (struct _fts1ht *)pH->xMalloc( new_size*sizeof(struct _fts1ht) ); | |
| 196 if( new_ht==0 ) return; | |
| 197 if( pH->ht ) pH->xFree(pH->ht); | |
| 198 pH->ht = new_ht; | |
| 199 pH->htsize = new_size; | |
| 200 xHash = hashFunction(pH->keyClass); | |
| 201 for(elem=pH->first, pH->first=0; elem; elem = next_elem){ | |
| 202 int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1); | |
| 203 next_elem = elem->next; | |
| 204 insertElement(pH, &new_ht[h], elem); | |
| 205 } | |
| 206 } | |
| 207 | |
| 208 /* This function (for internal use only) locates an element in an | |
| 209 ** hash table that matches the given key. The hash for this key has | |
| 210 ** already been computed and is passed as the 4th parameter. | |
| 211 */ | |
| 212 static fts1HashElem *findElementGivenHash( | |
| 213 const fts1Hash *pH, /* The pH to be searched */ | |
| 214 const void *pKey, /* The key we are searching for */ | |
| 215 int nKey, | |
| 216 int h /* The hash for this key. */ | |
| 217 ){ | |
| 218 fts1HashElem *elem; /* Used to loop thru the element list */ | |
| 219 int count; /* Number of elements left to test */ | |
| 220 int (*xCompare)(const void*,int,const void*,int); /* comparison function */ | |
| 221 | |
| 222 if( pH->ht ){ | |
| 223 struct _fts1ht *pEntry = &pH->ht[h]; | |
| 224 elem = pEntry->chain; | |
| 225 count = pEntry->count; | |
| 226 xCompare = compareFunction(pH->keyClass); | |
| 227 while( count-- && elem ){ | |
| 228 if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ | |
| 229 return elem; | |
| 230 } | |
| 231 elem = elem->next; | |
| 232 } | |
| 233 } | |
| 234 return 0; | |
| 235 } | |
| 236 | |
| 237 /* Remove a single entry from the hash table given a pointer to that | |
| 238 ** element and a hash on the element's key. | |
| 239 */ | |
| 240 static void removeElementGivenHash( | |
| 241 fts1Hash *pH, /* The pH containing "elem" */ | |
| 242 fts1HashElem* elem, /* The element to be removed from the pH */ | |
| 243 int h /* Hash value for the element */ | |
| 244 ){ | |
| 245 struct _fts1ht *pEntry; | |
| 246 if( elem->prev ){ | |
| 247 elem->prev->next = elem->next; | |
| 248 }else{ | |
| 249 pH->first = elem->next; | |
| 250 } | |
| 251 if( elem->next ){ | |
| 252 elem->next->prev = elem->prev; | |
| 253 } | |
| 254 pEntry = &pH->ht[h]; | |
| 255 if( pEntry->chain==elem ){ | |
| 256 pEntry->chain = elem->next; | |
| 257 } | |
| 258 pEntry->count--; | |
| 259 if( pEntry->count<=0 ){ | |
| 260 pEntry->chain = 0; | |
| 261 } | |
| 262 if( pH->copyKey && elem->pKey ){ | |
| 263 pH->xFree(elem->pKey); | |
| 264 } | |
| 265 pH->xFree( elem ); | |
| 266 pH->count--; | |
| 267 if( pH->count<=0 ){ | |
| 268 assert( pH->first==0 ); | |
| 269 assert( pH->count==0 ); | |
| 270 fts1HashClear(pH); | |
| 271 } | |
| 272 } | |
| 273 | |
| 274 /* Attempt to locate an element of the hash table pH with a key | |
| 275 ** that matches pKey,nKey. Return the data for this element if it is | |
| 276 ** found, or NULL if there is no match. | |
| 277 */ | |
| 278 void *sqlite3Fts1HashFind(const fts1Hash *pH, const void *pKey, int nKey){ | |
| 279 int h; /* A hash on key */ | |
| 280 fts1HashElem *elem; /* The element that matches key */ | |
| 281 int (*xHash)(const void*,int); /* The hash function */ | |
| 282 | |
| 283 if( pH==0 || pH->ht==0 ) return 0; | |
| 284 xHash = hashFunction(pH->keyClass); | |
| 285 assert( xHash!=0 ); | |
| 286 h = (*xHash)(pKey,nKey); | |
| 287 assert( (pH->htsize & (pH->htsize-1))==0 ); | |
| 288 elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1)); | |
| 289 return elem ? elem->data : 0; | |
| 290 } | |
| 291 | |
| 292 /* Insert an element into the hash table pH. The key is pKey,nKey | |
| 293 ** and the data is "data". | |
| 294 ** | |
| 295 ** If no element exists with a matching key, then a new | |
| 296 ** element is created. A copy of the key is made if the copyKey | |
| 297 ** flag is set. NULL is returned. | |
| 298 ** | |
| 299 ** If another element already exists with the same key, then the | |
| 300 ** new data replaces the old data and the old data is returned. | |
| 301 ** The key is not copied in this instance. If a malloc fails, then | |
| 302 ** the new data is returned and the hash table is unchanged. | |
| 303 ** | |
| 304 ** If the "data" parameter to this function is NULL, then the | |
| 305 ** element corresponding to "key" is removed from the hash table. | |
| 306 */ | |
| 307 void *sqlite3Fts1HashInsert( | |
| 308 fts1Hash *pH, /* The hash table to insert into */ | |
| 309 const void *pKey, /* The key */ | |
| 310 int nKey, /* Number of bytes in the key */ | |
| 311 void *data /* The data */ | |
| 312 ){ | |
| 313 int hraw; /* Raw hash value of the key */ | |
| 314 int h; /* the hash of the key modulo hash table size */ | |
| 315 fts1HashElem *elem; /* Used to loop thru the element list */ | |
| 316 fts1HashElem *new_elem; /* New element added to the pH */ | |
| 317 int (*xHash)(const void*,int); /* The hash function */ | |
| 318 | |
| 319 assert( pH!=0 ); | |
| 320 xHash = hashFunction(pH->keyClass); | |
| 321 assert( xHash!=0 ); | |
| 322 hraw = (*xHash)(pKey, nKey); | |
| 323 assert( (pH->htsize & (pH->htsize-1))==0 ); | |
| 324 h = hraw & (pH->htsize-1); | |
| 325 elem = findElementGivenHash(pH,pKey,nKey,h); | |
| 326 if( elem ){ | |
| 327 void *old_data = elem->data; | |
| 328 if( data==0 ){ | |
| 329 removeElementGivenHash(pH,elem,h); | |
| 330 }else{ | |
| 331 elem->data = data; | |
| 332 } | |
| 333 return old_data; | |
| 334 } | |
| 335 if( data==0 ) return 0; | |
| 336 new_elem = (fts1HashElem*)pH->xMalloc( sizeof(fts1HashElem) ); | |
| 337 if( new_elem==0 ) return data; | |
| 338 if( pH->copyKey && pKey!=0 ){ | |
| 339 new_elem->pKey = pH->xMalloc( nKey ); | |
| 340 if( new_elem->pKey==0 ){ | |
| 341 pH->xFree(new_elem); | |
| 342 return data; | |
| 343 } | |
| 344 memcpy((void*)new_elem->pKey, pKey, nKey); | |
| 345 }else{ | |
| 346 new_elem->pKey = (void*)pKey; | |
| 347 } | |
| 348 new_elem->nKey = nKey; | |
| 349 pH->count++; | |
| 350 if( pH->htsize==0 ){ | |
| 351 rehash(pH,8); | |
| 352 if( pH->htsize==0 ){ | |
| 353 pH->count = 0; | |
| 354 pH->xFree(new_elem); | |
| 355 return data; | |
| 356 } | |
| 357 } | |
| 358 if( pH->count > pH->htsize ){ | |
| 359 rehash(pH,pH->htsize*2); | |
| 360 } | |
| 361 assert( pH->htsize>0 ); | |
| 362 assert( (pH->htsize & (pH->htsize-1))==0 ); | |
| 363 h = hraw & (pH->htsize-1); | |
| 364 insertElement(pH, &pH->ht[h], new_elem); | |
| 365 new_elem->data = data; | |
| 366 return 0; | |
| 367 } | |
| 368 | |
| 369 #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS1) */ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2363173002:
[sqlite] Remove obsolete reference version 3.8.7.4. (Closed)
