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
13 : ** used in SQLite.
14 : **
15 : ** $Id$
16 : */
17 : #include "sqliteInt.h"
18 : #include <assert.h>
19 :
20 : /* Turn bulk memory into a hash table object by initializing the
21 : ** fields of the Hash structure.
22 : **
23 : ** "pNew" is a pointer to the hash table that is to be initialized.
24 : ** keyClass is one of the constants SQLITE_HASH_INT, SQLITE_HASH_POINTER,
25 : ** SQLITE_HASH_BINARY, or SQLITE_HASH_STRING. The value of keyClass
26 : ** determines what kind of key the hash table will use. "copyKey" is
27 : ** true if the hash table should make its own private copy of keys and
28 : ** false if it should just use the supplied pointer. CopyKey only makes
29 : ** sense for SQLITE_HASH_STRING and SQLITE_HASH_BINARY and is ignored
30 : ** for other key classes.
31 : */
32 2462 : void sqlite3HashInit(Hash *pNew, int keyClass, int copyKey){
33 : assert( pNew!=0 );
34 : assert( keyClass>=SQLITE_HASH_STRING && keyClass<=SQLITE_HASH_BINARY );
35 2462 : pNew->keyClass = keyClass;
36 : #if 0
37 : if( keyClass==SQLITE_HASH_POINTER || keyClass==SQLITE_HASH_INT ) copyKey = 0;
38 : #endif
39 2462 : pNew->copyKey = copyKey;
40 2462 : pNew->first = 0;
41 2462 : pNew->count = 0;
42 2462 : pNew->htsize = 0;
43 2462 : pNew->ht = 0;
44 2462 : pNew->xMalloc = sqlite3MallocX;
45 2462 : pNew->xFree = sqlite3FreeX;
46 2462 : }
47 :
48 : /* Remove all entries from a hash table. Reclaim all memory.
49 : ** Call this routine to delete a hash table or to reset a hash table
50 : ** to the empty state.
51 : */
52 2477 : void sqlite3HashClear(Hash *pH){
53 : HashElem *elem; /* For looping over all elements of the table */
54 :
55 : assert( pH!=0 );
56 2477 : elem = pH->first;
57 2477 : pH->first = 0;
58 2477 : if( pH->ht ) pH->xFree(pH->ht);
59 2477 : pH->ht = 0;
60 2477 : pH->htsize = 0;
61 11194 : while( elem ){
62 6240 : HashElem *next_elem = elem->next;
63 6240 : if( pH->copyKey && elem->pKey ){
64 0 : pH->xFree(elem->pKey);
65 : }
66 6240 : pH->xFree(elem);
67 6240 : elem = next_elem;
68 : }
69 2477 : pH->count = 0;
70 2477 : }
71 :
72 : #if 0 /* NOT USED */
73 : /*
74 : ** Hash and comparison functions when the mode is SQLITE_HASH_INT
75 : */
76 : static int intHash(const void *pKey, int nKey){
77 : return nKey ^ (nKey<<8) ^ (nKey>>8);
78 : }
79 : static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
80 : return n2 - n1;
81 : }
82 : #endif
83 :
84 : #if 0 /* NOT USED */
85 : /*
86 : ** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
87 : */
88 : static int ptrHash(const void *pKey, int nKey){
89 : uptr x = Addr(pKey);
90 : return x ^ (x<<8) ^ (x>>8);
91 : }
92 : static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
93 : if( pKey1==pKey2 ) return 0;
94 : if( pKey1<pKey2 ) return -1;
95 : return 1;
96 : }
97 : #endif
98 :
99 : /*
100 : ** Hash and comparison functions when the mode is SQLITE_HASH_STRING
101 : */
102 34548 : static int strHash(const void *pKey, int nKey){
103 34548 : const char *z = (const char *)pKey;
104 34548 : int h = 0;
105 34548 : if( nKey<=0 ) nKey = strlen(z);
106 316369 : while( nKey > 0 ){
107 247273 : h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
108 247273 : nKey--;
109 : }
110 34548 : return h & 0x7fffffff;
111 : }
112 23361 : static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
113 23361 : if( n1!=n2 ) return 1;
114 11096 : return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
115 : }
116 :
117 : /*
118 : ** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
119 : */
120 142 : static int binHash(const void *pKey, int nKey){
121 142 : int h = 0;
122 142 : const char *z = (const char *)pKey;
123 2556 : while( nKey-- > 0 ){
124 2272 : h = (h<<3) ^ h ^ *(z++);
125 : }
126 142 : return h & 0x7fffffff;
127 : }
128 56 : static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
129 56 : if( n1!=n2 ) return 1;
130 56 : return memcmp(pKey1,pKey2,n1);
131 : }
132 :
133 : /*
134 : ** Return a pointer to the appropriate hash function given the key class.
135 : **
136 : ** The C syntax in this function definition may be unfamilar to some
137 : ** programmers, so we provide the following additional explanation:
138 : **
139 : ** The name of the function is "hashFunction". The function takes a
140 : ** single parameter "keyClass". The return value of hashFunction()
141 : ** is a pointer to another function. Specifically, the return value
142 : ** of hashFunction() is a pointer to a function that takes two parameters
143 : ** with types "const void*" and "int" and returns an "int".
144 : */
145 28335 : static int (*hashFunction(int keyClass))(const void*,int){
146 : #if 0 /* HASH_INT and HASH_POINTER are never used */
147 : switch( keyClass ){
148 : case SQLITE_HASH_INT: return &intHash;
149 : case SQLITE_HASH_POINTER: return &ptrHash;
150 : case SQLITE_HASH_STRING: return &strHash;
151 : case SQLITE_HASH_BINARY: return &binHash;;
152 : default: break;
153 : }
154 : return 0;
155 : #else
156 28335 : if( keyClass==SQLITE_HASH_STRING ){
157 28167 : return &strHash;
158 : }else{
159 : assert( keyClass==SQLITE_HASH_BINARY );
160 168 : return &binHash;
161 : }
162 : #endif
163 : }
164 :
165 : /*
166 : ** Return a pointer to the appropriate hash function given the key class.
167 : **
168 : ** For help in interpreted the obscure C code in the function definition,
169 : ** see the header comment on the previous function.
170 : */
171 26801 : static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
172 : #if 0 /* HASH_INT and HASH_POINTER are never used */
173 : switch( keyClass ){
174 : case SQLITE_HASH_INT: return &intCompare;
175 : case SQLITE_HASH_POINTER: return &ptrCompare;
176 : case SQLITE_HASH_STRING: return &strCompare;
177 : case SQLITE_HASH_BINARY: return &binCompare;
178 : default: break;
179 : }
180 : return 0;
181 : #else
182 26801 : if( keyClass==SQLITE_HASH_STRING ){
183 26685 : return &strCompare;
184 : }else{
185 : assert( keyClass==SQLITE_HASH_BINARY );
186 116 : return &binCompare;
187 : }
188 : #endif
189 : }
190 :
191 : /* Link an element into the hash table
192 : */
193 : static void insertElement(
194 : Hash *pH, /* The complete hash table */
195 : struct _ht *pEntry, /* The entry into which pNew is inserted */
196 : HashElem *pNew /* The element to be inserted */
197 13630 : ){
198 : HashElem *pHead; /* First element already in pEntry */
199 13630 : pHead = pEntry->chain;
200 13630 : if( pHead ){
201 5206 : pNew->next = pHead;
202 5206 : pNew->prev = pHead->prev;
203 5206 : if( pHead->prev ){ pHead->prev->next = pNew; }
204 1826 : else { pH->first = pNew; }
205 5206 : pHead->prev = pNew;
206 : }else{
207 8424 : pNew->next = pH->first;
208 8424 : if( pH->first ){ pH->first->prev = pNew; }
209 8424 : pNew->prev = 0;
210 8424 : pH->first = pNew;
211 : }
212 13630 : pEntry->count++;
213 13630 : pEntry->chain = pNew;
214 13630 : }
215 :
216 :
217 : /* Resize the hash table so that it cantains "new_size" buckets.
218 : ** "new_size" must be a power of 2. The hash table might fail
219 : ** to resize if sqliteMalloc() fails.
220 : */
221 925 : static void rehash(Hash *pH, int new_size){
222 : struct _ht *new_ht; /* The new hash table */
223 : HashElem *elem, *next_elem; /* For looping over existing elements */
224 : int (*xHash)(const void*,int); /* The hash function */
225 :
226 : assert( (new_size & (new_size-1))==0 );
227 925 : new_ht = (struct _ht *)pH->xMalloc( new_size*sizeof(struct _ht) );
228 925 : if( new_ht==0 ) return;
229 925 : if( pH->ht ) pH->xFree(pH->ht);
230 925 : pH->ht = new_ht;
231 925 : pH->htsize = new_size;
232 925 : xHash = hashFunction(pH->keyClass);
233 8205 : for(elem=pH->first, pH->first=0; elem; elem = next_elem){
234 7280 : int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
235 7280 : next_elem = elem->next;
236 7280 : insertElement(pH, &new_ht[h], elem);
237 : }
238 : }
239 :
240 : /* This function (for internal use only) locates an element in an
241 : ** hash table that matches the given key. The hash for this key has
242 : ** already been computed and is passed as the 4th parameter.
243 : */
244 : static HashElem *findElementGivenHash(
245 : const Hash *pH, /* The pH to be searched */
246 : const void *pKey, /* The key we are searching for */
247 : int nKey,
248 : int h /* The hash for this key. */
249 27410 : ){
250 : HashElem *elem; /* Used to loop thru the element list */
251 : int count; /* Number of elements left to test */
252 : int (*xCompare)(const void*,int,const void*,int); /* comparison function */
253 :
254 27410 : if( pH->ht ){
255 26801 : struct _ht *pEntry = &pH->ht[h];
256 26801 : elem = pEntry->chain;
257 26801 : count = pEntry->count;
258 26801 : xCompare = compareFunction(pH->keyClass);
259 68597 : while( count-- && elem ){
260 23417 : if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
261 8422 : return elem;
262 : }
263 14995 : elem = elem->next;
264 : }
265 : }
266 18988 : return 0;
267 : }
268 :
269 : /* Remove a single entry from the hash table given a pointer to that
270 : ** element and a hash on the element's key.
271 : */
272 : static void removeElementGivenHash(
273 : Hash *pH, /* The pH containing "elem" */
274 : HashElem* elem, /* The element to be removed from the pH */
275 : int h /* Hash value for the element */
276 60 : ){
277 : struct _ht *pEntry;
278 60 : if( elem->prev ){
279 0 : elem->prev->next = elem->next;
280 : }else{
281 60 : pH->first = elem->next;
282 : }
283 60 : if( elem->next ){
284 34 : elem->next->prev = elem->prev;
285 : }
286 60 : pEntry = &pH->ht[h];
287 60 : if( pEntry->chain==elem ){
288 60 : pEntry->chain = elem->next;
289 : }
290 60 : pEntry->count--;
291 60 : if( pEntry->count<=0 ){
292 60 : pEntry->chain = 0;
293 : }
294 60 : if( pH->copyKey ){
295 0 : pH->xFree(elem->pKey);
296 : }
297 60 : pH->xFree( elem );
298 60 : pH->count--;
299 60 : if( pH->count<=0 ){
300 : assert( pH->first==0 );
301 : assert( pH->count==0 );
302 26 : sqlite3HashClear(pH);
303 : }
304 60 : }
305 :
306 : /* Attempt to locate an element of the hash table pH with a key
307 : ** that matches pKey,nKey. Return the data for this element if it is
308 : ** found, or NULL if there is no match.
309 : */
310 20519 : void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
311 : int h; /* A hash on key */
312 : HashElem *elem; /* The element that matches key */
313 : int (*xHash)(const void*,int); /* The hash function */
314 :
315 20519 : if( pH==0 || pH->ht==0 ) return 0;
316 19103 : xHash = hashFunction(pH->keyClass);
317 : assert( xHash!=0 );
318 19103 : h = (*xHash)(pKey,nKey);
319 : assert( (pH->htsize & (pH->htsize-1))==0 );
320 19103 : elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
321 19103 : return elem ? elem->data : 0;
322 : }
323 :
324 : /* Insert an element into the hash table pH. The key is pKey,nKey
325 : ** and the data is "data".
326 : **
327 : ** If no element exists with a matching key, then a new
328 : ** element is created. A copy of the key is made if the copyKey
329 : ** flag is set. NULL is returned.
330 : **
331 : ** If another element already exists with the same key, then the
332 : ** new data replaces the old data and the old data is returned.
333 : ** The key is not copied in this instance. If a malloc fails, then
334 : ** the new data is returned and the hash table is unchanged.
335 : **
336 : ** If the "data" parameter to this function is NULL, then the
337 : ** element corresponding to "key" is removed from the hash table.
338 : */
339 8307 : void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
340 : int hraw; /* Raw hash value of the key */
341 : int h; /* the hash of the key modulo hash table size */
342 : HashElem *elem; /* Used to loop thru the element list */
343 : HashElem *new_elem; /* New element added to the pH */
344 : int (*xHash)(const void*,int); /* The hash function */
345 :
346 : assert( pH!=0 );
347 8307 : xHash = hashFunction(pH->keyClass);
348 : assert( xHash!=0 );
349 8307 : hraw = (*xHash)(pKey, nKey);
350 : assert( (pH->htsize & (pH->htsize-1))==0 );
351 8307 : h = hraw & (pH->htsize-1);
352 8307 : elem = findElementGivenHash(pH,pKey,nKey,h);
353 8307 : if( elem ){
354 1880 : void *old_data = elem->data;
355 1880 : if( data==0 ){
356 60 : removeElementGivenHash(pH,elem,h);
357 : }else{
358 1820 : elem->data = data;
359 : }
360 1880 : return old_data;
361 : }
362 6427 : if( data==0 ) return 0;
363 6350 : new_elem = (HashElem*)pH->xMalloc( sizeof(HashElem) );
364 6350 : if( new_elem==0 ) return data;
365 6350 : if( pH->copyKey && pKey!=0 ){
366 0 : new_elem->pKey = pH->xMalloc( nKey );
367 0 : if( new_elem->pKey==0 ){
368 0 : pH->xFree(new_elem);
369 0 : return data;
370 : }
371 0 : memcpy((void*)new_elem->pKey, pKey, nKey);
372 : }else{
373 6350 : new_elem->pKey = (void*)pKey;
374 : }
375 6350 : new_elem->nKey = nKey;
376 6350 : pH->count++;
377 6350 : if( pH->htsize==0 ){
378 535 : rehash(pH,8);
379 535 : if( pH->htsize==0 ){
380 0 : pH->count = 0;
381 0 : if( pH->copyKey ){
382 0 : pH->xFree(new_elem->pKey);
383 : }
384 0 : pH->xFree(new_elem);
385 0 : return data;
386 : }
387 : }
388 6350 : if( pH->count > pH->htsize ){
389 390 : rehash(pH,pH->htsize*2);
390 : }
391 : assert( pH->htsize>0 );
392 : assert( (pH->htsize & (pH->htsize-1))==0 );
393 6350 : h = hraw & (pH->htsize-1);
394 6350 : insertElement(pH, &pH->ht[h], new_elem);
395 6350 : new_elem->data = data;
396 6350 : return 0;
397 : }
|
