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: hash.c 195361 2005-09-07 15:11:33Z iliaa $
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 : ** "new" 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 3525 : void sqliteHashInit(Hash *new, int keyClass, int copyKey){
33 : assert( new!=0 );
34 : assert( keyClass>=SQLITE_HASH_INT && keyClass<=SQLITE_HASH_BINARY );
35 3525 : new->keyClass = keyClass;
36 3525 : new->copyKey = copyKey &&
37 : (keyClass==SQLITE_HASH_STRING || keyClass==SQLITE_HASH_BINARY);
38 3525 : new->first = 0;
39 3525 : new->count = 0;
40 3525 : new->htsize = 0;
41 3525 : new->ht = 0;
42 3525 : }
43 :
44 : /* Remove all entries from a hash table. Reclaim all memory.
45 : ** Call this routine to delete a hash table or to reset a hash table
46 : ** to the empty state.
47 : */
48 4173 : void sqliteHashClear(Hash *pH){
49 : HashElem *elem; /* For looping over all elements of the table */
50 :
51 : assert( pH!=0 );
52 4173 : elem = pH->first;
53 4173 : pH->first = 0;
54 4173 : if( pH->ht ) sqliteFree(pH->ht);
55 4173 : pH->ht = 0;
56 4173 : pH->htsize = 0;
57 12470 : while( elem ){
58 4124 : HashElem *next_elem = elem->next;
59 4124 : if( pH->copyKey && elem->pKey ){
60 3750 : sqliteFree(elem->pKey);
61 : }
62 4124 : sqliteFree(elem);
63 4124 : elem = next_elem;
64 : }
65 4173 : pH->count = 0;
66 4173 : }
67 :
68 : /*
69 : ** Hash and comparison functions when the mode is SQLITE_HASH_INT
70 : */
71 2526 : static int intHash(const void *pKey, int nKey){
72 2526 : return nKey ^ (nKey<<8) ^ (nKey>>8);
73 : }
74 2091 : static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
75 2091 : return n2 - n1;
76 : }
77 :
78 : #if 0 /* NOT USED */
79 : /*
80 : ** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
81 : */
82 : static int ptrHash(const void *pKey, int nKey){
83 : uptr x = Addr(pKey);
84 : return x ^ (x<<8) ^ (x>>8);
85 : }
86 : static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
87 : if( pKey1==pKey2 ) return 0;
88 : if( pKey1<pKey2 ) return -1;
89 : return 1;
90 : }
91 : #endif
92 :
93 : /*
94 : ** Hash and comparison functions when the mode is SQLITE_HASH_STRING
95 : */
96 22652 : static int strHash(const void *pKey, int nKey){
97 22652 : return sqliteHashNoCase((const char*)pKey, nKey);
98 : }
99 16079 : static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
100 16079 : if( n1!=n2 ) return n2-n1;
101 10590 : return sqliteStrNICmp((const char*)pKey1,(const char*)pKey2,n1);
102 : }
103 :
104 : /*
105 : ** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
106 : */
107 48 : static int binHash(const void *pKey, int nKey){
108 48 : int h = 0;
109 48 : const char *z = (const char *)pKey;
110 722 : while( nKey-- > 0 ){
111 626 : h = (h<<3) ^ h ^ *(z++);
112 : }
113 48 : return h & 0x7fffffff;
114 : }
115 16 : static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
116 16 : if( n1!=n2 ) return n2-n1;
117 16 : return memcmp(pKey1,pKey2,n1);
118 : }
119 :
120 : /*
121 : ** Return a pointer to the appropriate hash function given the key class.
122 : **
123 : ** The C syntax in this function definition may be unfamilar to some
124 : ** programmers, so we provide the following additional explanation:
125 : **
126 : ** The name of the function is "hashFunction". The function takes a
127 : ** single parameter "keyClass". The return value of hashFunction()
128 : ** is a pointer to another function. Specifically, the return value
129 : ** of hashFunction() is a pointer to a function that takes two parameters
130 : ** with types "const void*" and "int" and returns an "int".
131 : */
132 22728 : static int (*hashFunction(int keyClass))(const void*,int){
133 22728 : switch( keyClass ){
134 2824 : case SQLITE_HASH_INT: return &intHash;
135 : /* case SQLITE_HASH_POINTER: return &ptrHash; // NOT USED */
136 19840 : case SQLITE_HASH_STRING: return &strHash;
137 64 : case SQLITE_HASH_BINARY: return &binHash;;
138 : default: break;
139 : }
140 0 : return 0;
141 : }
142 :
143 : /*
144 : ** Return a pointer to the appropriate hash function given the key class.
145 : **
146 : ** For help in interpreted the obscure C code in the function definition,
147 : ** see the header comment on the previous function.
148 : */
149 20804 : static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
150 20804 : switch( keyClass ){
151 2228 : case SQLITE_HASH_INT: return &intCompare;
152 : /* case SQLITE_HASH_POINTER: return &ptrCompare; // NOT USED */
153 18544 : case SQLITE_HASH_STRING: return &strCompare;
154 32 : case SQLITE_HASH_BINARY: return &binCompare;
155 : default: break;
156 : }
157 0 : return 0;
158 : }
159 :
160 :
161 : /* Resize the hash table so that it cantains "new_size" buckets.
162 : ** "new_size" must be a power of 2. The hash table might fail
163 : ** to resize if sqliteMalloc() fails.
164 : */
165 1102 : static void rehash(Hash *pH, int new_size){
166 : struct _ht *new_ht; /* The new hash table */
167 : HashElem *elem, *next_elem; /* For looping over existing elements */
168 : HashElem *x; /* Element being copied to new hash table */
169 : int (*xHash)(const void*,int); /* The hash function */
170 :
171 : assert( (new_size & (new_size-1))==0 );
172 1102 : new_ht = (struct _ht *)sqliteMalloc( new_size*sizeof(struct _ht) );
173 1102 : if( new_ht==0 ) return;
174 1102 : if( pH->ht ) sqliteFree(pH->ht);
175 1102 : pH->ht = new_ht;
176 1102 : pH->htsize = new_size;
177 1102 : xHash = hashFunction(pH->keyClass);
178 4702 : for(elem=pH->first, pH->first=0; elem; elem = next_elem){
179 3600 : int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
180 3600 : next_elem = elem->next;
181 3600 : x = new_ht[h].chain;
182 3600 : if( x ){
183 1050 : elem->next = x;
184 1050 : elem->prev = x->prev;
185 1050 : if( x->prev ) x->prev->next = elem;
186 750 : else pH->first = elem;
187 1050 : x->prev = elem;
188 : }else{
189 2550 : elem->next = pH->first;
190 2550 : if( pH->first ) pH->first->prev = elem;
191 2550 : elem->prev = 0;
192 2550 : pH->first = elem;
193 : }
194 3600 : new_ht[h].chain = elem;
195 3600 : new_ht[h].count++;
196 : }
197 : }
198 :
199 : /* This function (for internal use only) locates an element in an
200 : ** hash table that matches the given key. The hash for this key has
201 : ** already been computed and is passed as the 4th parameter.
202 : */
203 : static HashElem *findElementGivenHash(
204 : const Hash *pH, /* The pH to be searched */
205 : const void *pKey, /* The key we are searching for */
206 : int nKey,
207 : int h /* The hash for this key. */
208 21626 : ){
209 : HashElem *elem; /* Used to loop thru the element list */
210 : int count; /* Number of elements left to test */
211 : int (*xCompare)(const void*,int,const void*,int); /* comparison function */
212 :
213 21626 : if( pH->ht ){
214 20804 : elem = pH->ht[h].chain;
215 20804 : count = pH->ht[h].count;
216 20804 : xCompare = compareFunction(pH->keyClass);
217 48901 : while( count-- && elem ){
218 18186 : if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
219 10893 : return elem;
220 : }
221 7293 : elem = elem->next;
222 : }
223 : }
224 10733 : return 0;
225 : }
226 :
227 : /* Remove a single entry from the hash table given a pointer to that
228 : ** element and a hash on the element's key.
229 : */
230 : static void removeElementGivenHash(
231 : Hash *pH, /* The pH containing "elem" */
232 : HashElem* elem, /* The element to be removed from the pH */
233 : int h /* Hash value for the element */
234 367 : ){
235 367 : if( elem->prev ){
236 4 : elem->prev->next = elem->next;
237 : }else{
238 363 : pH->first = elem->next;
239 : }
240 367 : if( elem->next ){
241 101 : elem->next->prev = elem->prev;
242 : }
243 367 : if( pH->ht[h].chain==elem ){
244 367 : pH->ht[h].chain = elem->next;
245 : }
246 367 : pH->ht[h].count--;
247 367 : if( pH->ht[h].count<=0 ){
248 365 : pH->ht[h].chain = 0;
249 : }
250 367 : if( pH->copyKey && elem->pKey ){
251 0 : sqliteFree(elem->pKey);
252 : }
253 367 : sqliteFree( elem );
254 367 : pH->count--;
255 367 : }
256 :
257 : /* Attempt to locate an element of the hash table pH with a key
258 : ** that matches pKey,nKey. Return the data for this element if it is
259 : ** found, or NULL if there is no match.
260 : */
261 16294 : void *sqliteHashFind(const Hash *pH, const void *pKey, int nKey){
262 : int h; /* A hash on key */
263 : HashElem *elem; /* The element that matches key */
264 : int (*xHash)(const void*,int); /* The hash function */
265 :
266 16294 : if( pH==0 || pH->ht==0 ) return 0;
267 14882 : xHash = hashFunction(pH->keyClass);
268 : assert( xHash!=0 );
269 14882 : h = (*xHash)(pKey,nKey);
270 : assert( (pH->htsize & (pH->htsize-1))==0 );
271 14882 : elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
272 14882 : return elem ? elem->data : 0;
273 : }
274 :
275 : /* Insert an element into the hash table pH. The key is pKey,nKey
276 : ** and the data is "data".
277 : **
278 : ** If no element exists with a matching key, then a new
279 : ** element is created. A copy of the key is made if the copyKey
280 : ** flag is set. NULL is returned.
281 : **
282 : ** If another element already exists with the same key, then the
283 : ** new data replaces the old data and the old data is returned.
284 : ** The key is not copied in this instance. If a malloc fails, then
285 : ** the new data is returned and the hash table is unchanged.
286 : **
287 : ** If the "data" parameter to this function is NULL, then the
288 : ** element corresponding to "key" is removed from the hash table.
289 : */
290 6744 : void *sqliteHashInsert(Hash *pH, const void *pKey, int nKey, void *data){
291 : int hraw; /* Raw hash value of the key */
292 : int h; /* the hash of the key modulo hash table size */
293 : HashElem *elem; /* Used to loop thru the element list */
294 : HashElem *new_elem; /* New element added to the pH */
295 : int (*xHash)(const void*,int); /* The hash function */
296 :
297 : assert( pH!=0 );
298 6744 : xHash = hashFunction(pH->keyClass);
299 : assert( xHash!=0 );
300 6744 : hraw = (*xHash)(pKey, nKey);
301 : assert( (pH->htsize & (pH->htsize-1))==0 );
302 6744 : h = hraw & (pH->htsize-1);
303 6744 : elem = findElementGivenHash(pH,pKey,nKey,h);
304 6744 : if( elem ){
305 1567 : void *old_data = elem->data;
306 1567 : if( data==0 ){
307 367 : removeElementGivenHash(pH,elem,h);
308 : }else{
309 1200 : elem->data = data;
310 : }
311 1567 : return old_data;
312 : }
313 5177 : if( data==0 ) return 0;
314 5157 : new_elem = (HashElem*)sqliteMalloc( sizeof(HashElem) );
315 5157 : if( new_elem==0 ) return data;
316 9411 : if( pH->copyKey && pKey!=0 ){
317 4254 : new_elem->pKey = sqliteMallocRaw( nKey );
318 4254 : if( new_elem->pKey==0 ){
319 0 : sqliteFree(new_elem);
320 0 : return data;
321 : }
322 4254 : memcpy((void*)new_elem->pKey, pKey, nKey);
323 : }else{
324 903 : new_elem->pKey = (void*)pKey;
325 : }
326 5157 : new_elem->nKey = nKey;
327 5157 : pH->count++;
328 5157 : if( pH->htsize==0 ) rehash(pH,8);
329 5157 : if( pH->htsize==0 ){
330 0 : pH->count = 0;
331 0 : sqliteFree(new_elem);
332 0 : return data;
333 : }
334 5157 : if( pH->count > pH->htsize ){
335 300 : rehash(pH,pH->htsize*2);
336 : }
337 : assert( (pH->htsize & (pH->htsize-1))==0 );
338 5157 : h = hraw & (pH->htsize-1);
339 5157 : elem = pH->ht[h].chain;
340 5157 : if( elem ){
341 2108 : new_elem->next = elem;
342 2108 : new_elem->prev = elem->prev;
343 2108 : if( elem->prev ){ elem->prev->next = new_elem; }
344 156 : else { pH->first = new_elem; }
345 2108 : elem->prev = new_elem;
346 : }else{
347 3049 : new_elem->next = pH->first;
348 3049 : new_elem->prev = 0;
349 3049 : if( pH->first ){ pH->first->prev = new_elem; }
350 3049 : pH->first = new_elem;
351 : }
352 5157 : pH->ht[h].count++;
353 5157 : pH->ht[h].chain = new_elem;
354 5157 : new_elem->data = data;
355 5157 : return 0;
356 : }
|
