| 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 |
#include "fts3Int.h" |
| 27 |
#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) |
| 28 |
|
| 29 |
#include <assert.h> |
| 30 |
#include <stdlib.h> |
| 31 |
#include <string.h> |
| 32 |
|
| 33 |
#include "fts3_hash.h" |
| 34 |
|
| 35 |
/* |
| 36 |
** Malloc and Free functions |
| 37 |
*/ |
| 38 |
static void *fts3HashMalloc(sqlite3_int64 n){ |
| 39 |
void *p = sqlite3_malloc64(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, char keyClass, char 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 |
unsigned 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 (int)(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 contains "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 |
** Return non-zero if a memory allocation error occurs. |
| 195 |
*/ |
| 196 |
static int fts3Rehash(Fts3Hash *pH, int new_size){ |
| 197 |
struct _fts3ht *new_ht; /* The new hash table */ |
| 198 |
Fts3HashElem *elem, *next_elem; /* For looping over existing elements */ |
| 199 |
int (*xHash)(const void*,int); /* The hash function */ |
| 200 |
|
| 201 |
assert( (new_size & (new_size-1))==0 ); |
| 202 |
new_ht = (struct _fts3ht *)fts3HashMalloc( new_size*sizeof(struct _fts3ht) ); |
| 203 |
if( new_ht==0 ) return 1; |
| 204 |
fts3HashFree(pH->ht); |
| 205 |
pH->ht = new_ht; |
| 206 |
pH->htsize = new_size; |
| 207 |
xHash = ftsHashFunction(pH->keyClass); |
| 208 |
for(elem=pH->first, pH->first=0; elem; elem = next_elem){ |
| 209 |
int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1); |
| 210 |
next_elem = elem->next; |
| 211 |
fts3HashInsertElement(pH, &new_ht[h], elem); |
| 212 |
} |
| 213 |
return 0; |
| 214 |
} |
| 215 |
|
| 216 |
/* This function (for internal use only) locates an element in an |
| 217 |
** hash table that matches the given key. The hash for this key has |
| 218 |
** already been computed and is passed as the 4th parameter. |
| 219 |
*/ |
| 220 |
static Fts3HashElem *fts3FindElementByHash( |
| 221 |
const Fts3Hash *pH, /* The pH to be searched */ |
| 222 |
const void *pKey, /* The key we are searching for */ |
| 223 |
int nKey, |
| 224 |
int h /* The hash for this key. */ |
| 225 |
){ |
| 226 |
Fts3HashElem *elem; /* Used to loop thru the element list */ |
| 227 |
int count; /* Number of elements left to test */ |
| 228 |
int (*xCompare)(const void*,int,const void*,int); /* comparison function */ |
| 229 |
|
| 230 |
if( pH->ht ){ |
| 231 |
struct _fts3ht *pEntry = &pH->ht[h]; |
| 232 |
elem = pEntry->chain; |
| 233 |
count = pEntry->count; |
| 234 |
xCompare = ftsCompareFunction(pH->keyClass); |
| 235 |
while( count-- && elem ){ |
| 236 |
if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ |
| 237 |
return elem; |
| 238 |
} |
| 239 |
elem = elem->next; |
| 240 |
} |
| 241 |
} |
| 242 |
return 0; |
| 243 |
} |
| 244 |
|
| 245 |
/* Remove a single entry from the hash table given a pointer to that |
| 246 |
** element and a hash on the element's key. |
| 247 |
*/ |
| 248 |
static void fts3RemoveElementByHash( |
| 249 |
Fts3Hash *pH, /* The pH containing "elem" */ |
| 250 |
Fts3HashElem* elem, /* The element to be removed from the pH */ |
| 251 |
int h /* Hash value for the element */ |
| 252 |
){ |
| 253 |
struct _fts3ht *pEntry; |
| 254 |
if( elem->prev ){ |
| 255 |
elem->prev->next = elem->next; |
| 256 |
}else{ |
| 257 |
pH->first = elem->next; |
| 258 |
} |
| 259 |
if( elem->next ){ |
| 260 |
elem->next->prev = elem->prev; |
| 261 |
} |
| 262 |
pEntry = &pH->ht[h]; |
| 263 |
if( pEntry->chain==elem ){ |
| 264 |
pEntry->chain = elem->next; |
| 265 |
} |
| 266 |
pEntry->count--; |
| 267 |
if( pEntry->count<=0 ){ |
| 268 |
pEntry->chain = 0; |
| 269 |
} |
| 270 |
if( pH->copyKey && elem->pKey ){ |
| 271 |
fts3HashFree(elem->pKey); |
| 272 |
} |
| 273 |
fts3HashFree( elem ); |
| 274 |
pH->count--; |
| 275 |
if( pH->count<=0 ){ |
| 276 |
assert( pH->first==0 ); |
| 277 |
assert( pH->count==0 ); |
| 278 |
fts3HashClear(pH); |
| 279 |
} |
| 280 |
} |
| 281 |
|
| 282 |
Fts3HashElem *sqlite3Fts3HashFindElem( |
| 283 |
const Fts3Hash *pH, |
| 284 |
const void *pKey, |
| 285 |
int nKey |
| 286 |
){ |
| 287 |
int h; /* A hash on key */ |
| 288 |
int (*xHash)(const void*,int); /* The hash function */ |
| 289 |
|
| 290 |
if( pH==0 || pH->ht==0 ) return 0; |
| 291 |
xHash = ftsHashFunction(pH->keyClass); |
| 292 |
assert( xHash!=0 ); |
| 293 |
h = (*xHash)(pKey,nKey); |
| 294 |
assert( (pH->htsize & (pH->htsize-1))==0 ); |
| 295 |
return fts3FindElementByHash(pH,pKey,nKey, h & (pH->htsize-1)); |
| 296 |
} |
| 297 |
|
| 298 |
/* |
| 299 |
** Attempt to locate an element of the hash table pH with a key |
| 300 |
** that matches pKey,nKey. Return the data for this element if it is |
| 301 |
** found, or NULL if there is no match. |
| 302 |
*/ |
| 303 |
void *sqlite3Fts3HashFind(const Fts3Hash *pH, const void *pKey, int nKey){ |
| 304 |
Fts3HashElem *pElem; /* The element that matches key (if any) */ |
| 305 |
|
| 306 |
pElem = sqlite3Fts3HashFindElem(pH, pKey, nKey); |
| 307 |
return pElem ? pElem->data : 0; |
| 308 |
} |
| 309 |
|
| 310 |
/* Insert an element into the hash table pH. The key is pKey,nKey |
| 311 |
** and the data is "data". |
| 312 |
** |
| 313 |
** If no element exists with a matching key, then a new |
| 314 |
** element is created. A copy of the key is made if the copyKey |
| 315 |
** flag is set. NULL is returned. |
| 316 |
** |
| 317 |
** If another element already exists with the same key, then the |
| 318 |
** new data replaces the old data and the old data is returned. |
| 319 |
** The key is not copied in this instance. If a malloc fails, then |
| 320 |
** the new data is returned and the hash table is unchanged. |
| 321 |
** |
| 322 |
** If the "data" parameter to this function is NULL, then the |
| 323 |
** element corresponding to "key" is removed from the hash table. |
| 324 |
*/ |
| 325 |
void *sqlite3Fts3HashInsert( |
| 326 |
Fts3Hash *pH, /* The hash table to insert into */ |
| 327 |
const void *pKey, /* The key */ |
| 328 |
int nKey, /* Number of bytes in the key */ |
| 329 |
void *data /* The data */ |
| 330 |
){ |
| 331 |
int hraw; /* Raw hash value of the key */ |
| 332 |
int h; /* the hash of the key modulo hash table size */ |
| 333 |
Fts3HashElem *elem; /* Used to loop thru the element list */ |
| 334 |
Fts3HashElem *new_elem; /* New element added to the pH */ |
| 335 |
int (*xHash)(const void*,int); /* The hash function */ |
| 336 |
|
| 337 |
assert( pH!=0 ); |
| 338 |
xHash = ftsHashFunction(pH->keyClass); |
| 339 |
assert( xHash!=0 ); |
| 340 |
hraw = (*xHash)(pKey, nKey); |
| 341 |
assert( (pH->htsize & (pH->htsize-1))==0 ); |
| 342 |
h = hraw & (pH->htsize-1); |
| 343 |
elem = fts3FindElementByHash(pH,pKey,nKey,h); |
| 344 |
if( elem ){ |
| 345 |
void *old_data = elem->data; |
| 346 |
if( data==0 ){ |
| 347 |
fts3RemoveElementByHash(pH,elem,h); |
| 348 |
}else{ |
| 349 |
elem->data = data; |
| 350 |
} |
| 351 |
return old_data; |
| 352 |
} |
| 353 |
if( data==0 ) return 0; |
| 354 |
if( (pH->htsize==0 && fts3Rehash(pH,8)) |
| 355 |
|| (pH->count>=pH->htsize && fts3Rehash(pH, pH->htsize*2)) |
| 356 |
){ |
| 357 |
pH->count = 0; |
| 358 |
return data; |
| 359 |
} |
| 360 |
assert( pH->htsize>0 ); |
| 361 |
new_elem = (Fts3HashElem*)fts3HashMalloc( sizeof(Fts3HashElem) ); |
| 362 |
if( new_elem==0 ) return data; |
| 363 |
if( pH->copyKey && pKey!=0 ){ |
| 364 |
new_elem->pKey = fts3HashMalloc( nKey ); |
| 365 |
if( new_elem->pKey==0 ){ |
| 366 |
fts3HashFree(new_elem); |
| 367 |
return data; |
| 368 |
} |
| 369 |
memcpy((void*)new_elem->pKey, pKey, nKey); |
| 370 |
}else{ |
| 371 |
new_elem->pKey = (void*)pKey; |
| 372 |
} |
| 373 |
new_elem->nKey = nKey; |
| 374 |
pH->count++; |
| 375 |
assert( pH->htsize>0 ); |
| 376 |
assert( (pH->htsize & (pH->htsize-1))==0 ); |
| 377 |
h = hraw & (pH->htsize-1); |
| 378 |
fts3HashInsertElement(pH, &pH->ht[h], new_elem); |
| 379 |
new_elem->data = data; |
| 380 |
return 0; |
| 381 |
} |
| 382 |
|
| 383 |
#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */ |