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