| 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 FTS3 module is being built as an extension | |
| 21 ** (in which case SQLITE_CORE is not defined), or | |
| 22 ** | |
| 23 ** * The FTS3 module is being built into the core of | |
| 24 ** SQLite (in which case SQLITE_ENABLE_FTS3 is defined). | |
| 25 */ | |
| 26 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) | |
| 27 | |
| 28 #include <assert.h> | |
| 29 #include <stdlib.h> | |
| 30 #include <string.h> | |
| 31 | |
| 32 #include "sqlite3.h" | |
| 33 #include "fts3_hash.h" | |
| 34 | |
| 35 /* | |
| 36 ** Malloc and Free functions | |
| 37 */ | |
| 38 static void *fts3HashMalloc(int n){ | |
| 39 void *p = sqlite3_malloc(n); | |
| 40 if( p ){ | |
| 41 memset(p, 0, n); | |
| 42 } | |
| 43 return p; | |
| 44 } | |
| 45 static void fts3HashFree(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 ** FTS3_HASH_BINARY or FTS3_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 sqlite3Fts3HashInit(fts3Hash *pNew, int keyClass, int copyKey){ | |
| 60 assert( pNew!=0 ); | |
| 61 assert( keyClass>=FTS3_HASH_STRING && keyClass<=FTS3_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 sqlite3Fts3HashClear(fts3Hash *pH){ | |
| 75 fts3HashElem *elem; /* For looping over all elements of the table */ | |
| 76 | |
| 77 assert( pH!=0 ); | |
| 78 elem = pH->first; | |
| 79 pH->first = 0; | |
| 80 fts3HashFree(pH->ht); | |
| 81 pH->ht = 0; | |
| 82 pH->htsize = 0; | |
| 83 while( elem ){ | |
| 84 fts3HashElem *next_elem = elem->next; | |
| 85 if( pH->copyKey && elem->pKey ){ | |
| 86 fts3HashFree(elem->pKey); | |
| 87 } | |
| 88 fts3HashFree(elem); | |
| 89 elem = next_elem; | |
| 90 } | |
| 91 pH->count = 0; | |
| 92 } | |
| 93 | |
| 94 /* | |
| 95 ** Hash and comparison functions when the mode is FTS3_HASH_STRING | |
| 96 */ | |
| 97 static int fts3StrHash(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 fts3StrCompare(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 FTS3_HASH_BINARY | |
| 114 */ | |
| 115 static int fts3BinHash(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 fts3BinCompare(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 "ftsHashFunction". The function takes a | |
| 135 ** single parameter "keyClass". The return value of ftsHashFunction() | |
| 136 ** is a pointer to another function. Specifically, the return value | |
| 137 ** of ftsHashFunction() 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 (*ftsHashFunction(int keyClass))(const void*,int){ | |
| 141 if( keyClass==FTS3_HASH_STRING ){ | |
| 142 return &fts3StrHash; | |
| 143 }else{ | |
| 144 assert( keyClass==FTS3_HASH_BINARY ); | |
| 145 return &fts3BinHash; | |
| 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 (*ftsCompareFunction(int keyClass))(const void*,int,const void*,int){ | |
| 156 if( keyClass==FTS3_HASH_STRING ){ | |
| 157 return &fts3StrCompare; | |
| 158 }else{ | |
| 159 assert( keyClass==FTS3_HASH_BINARY ); | |
| 160 return &fts3BinCompare; | |
| 161 } | |
| 162 } | |
| 163 | |
| 164 /* Link an element into the hash table | |
| 165 */ | |
| 166 static void fts3HashInsertElement( | |
| 167 fts3Hash *pH, /* The complete hash table */ | |
| 168 struct _fts3ht *pEntry, /* The entry into which pNew is inserted */ | |
| 169 fts3HashElem *pNew /* The element to be inserted */ | |
| 170 ){ | |
| 171 fts3HashElem *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 fts3Rehash(fts3Hash *pH, int new_size){ | |
| 195 struct _fts3ht *new_ht; /* The new hash table */ | |
| 196 fts3HashElem *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 _fts3ht *)fts3HashMalloc( new_size*sizeof(struct _fts3ht) ); | |
| 201 if( new_ht==0 ) return; | |
| 202 fts3HashFree(pH->ht); | |
| 203 pH->ht = new_ht; | |
| 204 pH->htsize = new_size; | |
| 205 xHash = ftsHashFunction(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 fts3HashInsertElement(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 fts3HashElem *fts3FindElementByHash( | |
| 218 const fts3Hash *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 fts3HashElem *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 _fts3ht *pEntry = &pH->ht[h]; | |
| 229 elem = pEntry->chain; | |
| 230 count = pEntry->count; | |
| 231 xCompare = ftsCompareFunction(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 fts3RemoveElementByHash( | |
| 246 fts3Hash *pH, /* The pH containing "elem" */ | |
| 247 fts3HashElem* elem, /* The element to be removed from the pH */ | |
| 248 int h /* Hash value for the element */ | |
| 249 ){ | |
| 250 struct _fts3ht *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 fts3HashFree(elem->pKey); | |
| 269 } | |
| 270 fts3HashFree( elem ); | |
| 271 pH->count--; | |
| 272 if( pH->count<=0 ){ | |
| 273 assert( pH->first==0 ); | |
| 274 assert( pH->count==0 ); | |
| 275 fts3HashClear(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 *sqlite3Fts3HashFind(const fts3Hash *pH, const void *pKey, int nKey){ | |
| 284 int h; /* A hash on key */ | |
| 285 fts3HashElem *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 = ftsHashFunction(pH->keyClass); | |
| 290 assert( xHash!=0 ); | |
| 291 h = (*xHash)(pKey,nKey); | |
| 292 assert( (pH->htsize & (pH->htsize-1))==0 ); | |
| 293 elem = fts3FindElementByHash(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 *sqlite3Fts3HashInsert( | |
| 313 fts3Hash *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 fts3HashElem *elem; /* Used to loop thru the element list */ | |
| 321 fts3HashElem *new_elem; /* New element added to the pH */ | |
| 322 int (*xHash)(const void*,int); /* The hash function */ | |
| 323 | |
| 324 assert( pH!=0 ); | |
| 325 xHash = ftsHashFunction(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 = fts3FindElementByHash(pH,pKey,nKey,h); | |
| 331 if( elem ){ | |
| 332 void *old_data = elem->data; | |
| 333 if( data==0 ){ | |
| 334 fts3RemoveElementByHash(pH,elem,h); | |
| 335 }else{ | |
| 336 elem->data = data; | |
| 337 } | |
| 338 return old_data; | |
| 339 } | |
| 340 if( data==0 ) return 0; | |
| 341 if( pH->htsize==0 ){ | |
| 342 fts3Rehash(pH,8); | |
| 343 if( pH->htsize==0 ){ | |
| 344 pH->count = 0; | |
| 345 return data; | |
| 346 } | |
| 347 } | |
| 348 new_elem = (fts3HashElem*)fts3HashMalloc( sizeof(fts3HashElem) ); | |
| 349 if( new_elem==0 ) return data; | |
| 350 if( pH->copyKey && pKey!=0 ){ | |
| 351 new_elem->pKey = fts3HashMalloc( nKey ); | |
| 352 if( new_elem->pKey==0 ){ | |
| 353 fts3HashFree(new_elem); | |
| 354 return data; | |
| 355 } | |
| 356 memcpy((void*)new_elem->pKey, pKey, nKey); | |
| 357 }else{ | |
| 358 new_elem->pKey = (void*)pKey; | |
| 359 } | |
| 360 new_elem->nKey = nKey; | |
| 361 pH->count++; | |
| 362 if( pH->count > pH->htsize ){ | |
| 363 fts3Rehash(pH,pH->htsize*2); | |
| 364 } | |
| 365 assert( pH->htsize>0 ); | |
| 366 assert( (pH->htsize & (pH->htsize-1))==0 ); | |
| 367 h = hraw & (pH->htsize-1); | |
| 368 fts3HashInsertElement(pH, &pH->ht[h], new_elem); | |
| 369 new_elem->data = data; | |
| 370 return 0; | |
| 371 } | |
| 372 | |
| 373 #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */ | |
| 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/