|
25
|
1 /* |
|
|
2 * This program is free software; you can redistribute it and/or modify |
|
|
3 * it under the terms of the GNU General Public License as published by |
|
|
4 * the Free Software Foundation; either version 2 of the License, or |
|
|
5 * (at your option) any later version. |
|
|
6 * |
|
|
7 * This program is distributed in the hope that it will be useful, |
|
|
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
|
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|
|
10 * GNU General Public License for more details. |
|
|
11 * |
|
|
12 * You should have received a copy of the GNU General Public License |
|
|
13 * along with this program; if not, write to the Free Software |
|
|
14 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
|
|
15 * |
|
|
16 * Jabber |
|
|
17 * Copyright (C) 1998-1999 The Jabber Team http://jabber.org/ |
|
|
18 */ |
|
|
19 #include <libxode.h> |
|
|
20 |
|
|
21 /***************************************************************************** |
|
|
22 * Internal type definitions |
|
|
23 */ |
|
|
24 |
|
|
25 typedef struct tagHNODE |
|
|
26 { |
|
|
27 struct tagHNODE *next; /* next node in list */ |
|
|
28 const void *key; /* key pointer */ |
|
|
29 void *value; /* value pointer */ |
|
|
30 } HNODE; |
|
|
31 |
|
|
32 #define SLAB_NUM_NODES 64 /* allocate this many nodes per slab */ |
|
|
33 |
|
|
34 typedef struct tagHSLAB |
|
|
35 { |
|
|
36 struct tagHSLAB *next; /* next slab pointer */ |
|
|
37 HNODE nodes[SLAB_NUM_NODES]; /* the actual nodes */ |
|
|
38 } HSLAB; |
|
|
39 |
|
|
40 #define HASH_NUM_BUCKETS 509 /* should be a prime number; see Knuth */ |
|
|
41 |
|
|
42 typedef struct tagHASHTABLE_INTERNAL |
|
|
43 { |
|
|
44 unsigned long sig1; /* first signature word */ |
|
|
45 KEYHASHFUNC hash; /* hash function */ |
|
|
46 KEYCOMPAREFUNC cmp; /* comparison function */ |
|
|
47 int count; /* table entry count */ |
|
|
48 int bcount; /* bucket count */ |
|
|
49 HNODE **buckets; /* the hash buckets */ |
|
|
50 unsigned long sig2; /* second signature word */ |
|
|
51 |
|
|
52 } HASHTABLE_INTERNAL; |
|
|
53 |
|
|
54 #define HASH_SIG1 0x68736148UL /* "Hash" */ |
|
|
55 #define HASH_SIG2 0x6F627245UL /* "Erbo" */ |
|
|
56 |
|
|
57 #define do_hash(tb,key) ((*((tb)->hash))(key) % ((tb)->bcount)) |
|
|
58 |
|
|
59 static HNODE *s_free_nodes = NULL; /* free nodes list */ |
|
|
60 static HSLAB *s_slabs = NULL; /* node slabs list */ |
|
|
61 |
|
|
62 /***************************************************************************** |
|
|
63 * Internal functions |
|
|
64 */ |
|
|
65 |
|
|
66 static HNODE *allocate_node( |
|
|
67 const void *key, /* key pointer for this node */ |
|
|
68 void *value) /* value pointer for this node */ |
|
|
69 /* |
|
|
70 allocate_node allocates a new hash node and fills it. Returns NULL if the |
|
|
71 node could not be allocated. |
|
|
72 */ |
|
|
73 { |
|
|
74 HNODE *rc; /* return from this function */ |
|
|
75 |
|
|
76 if (!s_free_nodes) |
|
|
77 { /* allocate a new slabful of nodes and chain them to make a new free list */ |
|
|
78 register int i; /* loop counter */ |
|
|
79 HSLAB *slab = (HSLAB *)malloc(sizeof(HSLAB)); |
|
|
80 if (!slab) |
|
|
81 return NULL; |
|
|
82 memset(slab,0,sizeof(HSLAB)); |
|
|
83 slab->next = s_slabs; |
|
|
84 for (i=0; i<(SLAB_NUM_NODES-1); i++) |
|
|
85 slab->nodes[i].next = &(slab->nodes[i+1]); |
|
|
86 s_free_nodes = &(slab->nodes[0]); |
|
|
87 s_slabs = slab; |
|
|
88 |
|
|
89 } /* end if */ |
|
|
90 |
|
|
91 /* grab a node off the fron of the free list and fill it */ |
|
|
92 rc = s_free_nodes; |
|
|
93 s_free_nodes = rc->next; |
|
|
94 rc->next = NULL; |
|
|
95 rc->key = key; |
|
|
96 rc->value = value; |
|
|
97 return rc; |
|
|
98 |
|
|
99 } /* end allocate_node */ |
|
|
100 |
|
|
101 static void free_node( |
|
|
102 HNODE *node) /* node to be freed */ |
|
|
103 /* |
|
|
104 free_node returns a hash node to the list. |
|
|
105 */ |
|
|
106 { |
|
|
107 /* zap the node contents to avoid problems later */ |
|
|
108 memset(node,0,sizeof(HNODE)); |
|
|
109 |
|
|
110 /* chain it onto the free list */ |
|
|
111 node->next = s_free_nodes; |
|
|
112 s_free_nodes = node; |
|
|
113 |
|
|
114 } /* end free_node */ |
|
|
115 |
|
|
116 static HNODE *find_node( |
|
|
117 HASHTABLE_INTERNAL *tab, /* pointer to hash table */ |
|
|
118 const void *key, /* key value to look up */ |
|
|
119 int bucket) /* bucket number (-1 to have function compute it) */ |
|
|
120 /* |
|
|
121 find_node walks a hash bucket to find a node whose key matches the named key value. |
|
|
122 Returns the node pointer, or NULL if it's not found. |
|
|
123 */ |
|
|
124 { |
|
|
125 register HNODE *p; /* search pointer/return from this function */ |
|
|
126 |
|
|
127 if (bucket<0) /* compute hash value if we don't know it already */ |
|
|
128 bucket = do_hash(tab,key); |
|
|
129 |
|
|
130 /* search through the bucket contents */ |
|
|
131 for (p=tab->buckets[bucket]; p; p=p->next) |
|
|
132 if ((*(tab->cmp))(key,p->key)==0) |
|
|
133 return p; /* found! */ |
|
|
134 |
|
|
135 return NULL; /* not found */ |
|
|
136 |
|
|
137 } /* end find_node */ |
|
|
138 |
|
|
139 static HASHTABLE_INTERNAL *handle2ptr( |
|
|
140 HASHTABLE tbl) /* hash table handle */ |
|
|
141 /* |
|
|
142 handle2ptr converts a hash table handle into a pointer and checks its signatures |
|
|
143 to make sure someone's not trying to pull a whizzer on this module. |
|
|
144 */ |
|
|
145 { |
|
|
146 register HASHTABLE_INTERNAL *rc = (HASHTABLE_INTERNAL *)tbl; |
|
|
147 if ((rc->sig1==HASH_SIG1) && (rc->sig2==HASH_SIG2)) |
|
|
148 return rc; /* signatures match */ |
|
|
149 else |
|
|
150 return NULL; /* yIkes! */ |
|
|
151 } |
|
|
152 |
|
|
153 /***************************************************************************** |
|
|
154 * External functions |
|
|
155 */ |
|
|
156 |
|
|
157 HASHTABLE ghash_create(int buckets, KEYHASHFUNC hash, KEYCOMPAREFUNC cmp) |
|
|
158 /* |
|
|
159 Description: |
|
|
160 Creates a new hash table. |
|
|
161 |
|
|
162 Input: |
|
|
163 Parameters: |
|
|
164 buckets - Number of buckets to allocate for the hash table; this value |
|
|
165 should be a prime number for maximum efficiency. |
|
|
166 hash - Key hash code function to use. |
|
|
167 cmp - Key comparison function to use. |
|
|
168 |
|
|
169 Output: |
|
|
170 Returns: |
|
|
171 NULL - Table could not be allocated. |
|
|
172 Other - Handle to the new hashtable. |
|
|
173 */ |
|
|
174 { |
|
|
175 HASHTABLE_INTERNAL *tab; /* new table structure */ |
|
|
176 char *allocated; |
|
|
177 |
|
|
178 if (!hash || !cmp) |
|
|
179 return NULL; /* bogus! */ |
|
|
180 |
|
|
181 if (buckets<=0) |
|
|
182 buckets = HASH_NUM_BUCKETS; |
|
|
183 |
|
|
184 /* allocate a hash table structure */ |
|
|
185 allocated = malloc(sizeof(HASHTABLE_INTERNAL) + (buckets * sizeof(HNODE *))); |
|
|
186 if (!allocated) |
|
|
187 return NULL; /* memory error */ |
|
|
188 |
|
|
189 /* fill the fields of the hash table */ |
|
|
190 tab = (HASHTABLE_INTERNAL *)allocated; |
|
|
191 allocated += sizeof(HASHTABLE_INTERNAL); |
|
|
192 memset(tab,0,sizeof(HASHTABLE_INTERNAL)); |
|
|
193 memset(allocated,0,buckets * sizeof(HNODE *)); |
|
|
194 tab->sig1 = HASH_SIG1; |
|
|
195 tab->hash = hash; |
|
|
196 tab->cmp = cmp; |
|
|
197 tab->bcount = buckets; |
|
|
198 tab->buckets = (HNODE **)allocated; |
|
|
199 tab->sig2 = HASH_SIG2; |
|
|
200 |
|
|
201 return (HASHTABLE)tab; /* Qa'pla! */ |
|
|
202 |
|
|
203 } /* end ghash_create */ |
|
|
204 |
|
|
205 void ghash_destroy(HASHTABLE tbl) |
|
|
206 /* |
|
|
207 Description: |
|
|
208 Destroys a hash table. |
|
|
209 |
|
|
210 Input: |
|
|
211 Parameters: |
|
|
212 tbl - Table to be destroyed. |
|
|
213 |
|
|
214 Output: |
|
|
215 Returns: |
|
|
216 Nothing. |
|
|
217 */ |
|
|
218 { |
|
|
219 HASHTABLE_INTERNAL *tab; /* new table structure */ |
|
|
220 int i; /* loop counter */ |
|
|
221 HNODE *p, *p2; /* temporary pointers */ |
|
|
222 |
|
|
223 if (!tbl) |
|
|
224 return; /* bogus! */ |
|
|
225 |
|
|
226 /* Convert the handle to a table pointer. */ |
|
|
227 tab = handle2ptr(tbl); |
|
|
228 if (!tab) |
|
|
229 return; |
|
|
230 |
|
|
231 /* Nuke the nodes it contains. */ |
|
|
232 for (i=0; i<tab->bcount; i++) |
|
|
233 { /* free the contents of each bucket */ |
|
|
234 p = tab->buckets[i]; |
|
|
235 while (p) |
|
|
236 { /* free each node in turn */ |
|
|
237 p2 = p->next; |
|
|
238 free_node(p); |
|
|
239 p = p2; |
|
|
240 |
|
|
241 } /* end while */ |
|
|
242 |
|
|
243 } /* end for */ |
|
|
244 |
|
|
245 free(tab); /* bye bye now! */ |
|
|
246 |
|
|
247 } /* end ghash_destroy */ |
|
|
248 |
|
|
249 void *ghash_get(HASHTABLE tbl, const void *key) |
|
|
250 /* |
|
|
251 Description: |
|
|
252 Retrieves a value stored in the hash table. |
|
|
253 |
|
|
254 Input: |
|
|
255 Parameters: |
|
|
256 tbl - The hash table to look in. |
|
|
257 key - The key value to search on. |
|
|
258 |
|
|
259 Output: |
|
|
260 Returns: |
|
|
261 NULL - Value not found. |
|
|
262 Other - Value corresponding to the specified key. |
|
|
263 */ |
|
|
264 { |
|
|
265 HASHTABLE_INTERNAL *tab; /* internal table pointer */ |
|
|
266 HNODE *node; /* hash node */ |
|
|
267 void *rc = NULL; /* return from this function */ |
|
|
268 |
|
|
269 if (!tbl || !key) |
|
|
270 return NULL; /* bogus! */ |
|
|
271 |
|
|
272 /* Convert the handle to a table pointer. */ |
|
|
273 tab = handle2ptr(tbl); |
|
|
274 if (!tab) |
|
|
275 return NULL; /* error */ |
|
|
276 |
|
|
277 /* Attempt to find the node. */ |
|
|
278 node = find_node(tab,key,-1); |
|
|
279 if (node) |
|
|
280 rc = node->value; /* found it! */ |
|
|
281 |
|
|
282 return rc; |
|
|
283 |
|
|
284 } /* end ghash_get */ |
|
|
285 |
|
|
286 int ghash_put(HASHTABLE tbl, const void *key, void *value) |
|
|
287 /* |
|
|
288 Description: |
|
|
289 Associates a key with a value in this hash table. |
|
|
290 |
|
|
291 Input: |
|
|
292 Parameters: |
|
|
293 tbl - Hash table to add. |
|
|
294 key - Key to use for the value in the table. |
|
|
295 value - Value to add for this key. |
|
|
296 |
|
|
297 Output: |
|
|
298 Returns: |
|
|
299 1 - Success. |
|
|
300 0 - Failure. |
|
|
301 |
|
|
302 Notes: |
|
|
303 If the specified key is already in the hashtable, its value will be replaced. |
|
|
304 */ |
|
|
305 { |
|
|
306 HASHTABLE_INTERNAL *tab; /* internal table pointer */ |
|
|
307 int bucket; /* bucket value goes into */ |
|
|
308 HNODE *node; /* hash node */ |
|
|
309 int rc = 1; /* return from this function */ |
|
|
310 |
|
|
311 if (!tbl || !key || !value) |
|
|
312 return 0; /* bogus! */ |
|
|
313 |
|
|
314 /* Convert the handle to a table pointer. */ |
|
|
315 tab = handle2ptr(tbl); |
|
|
316 if (!tab) |
|
|
317 return 0; /* error */ |
|
|
318 |
|
|
319 |
|
|
320 /* Compute the hash bucket and try to find an existing node. */ |
|
|
321 bucket = do_hash(tab,key); |
|
|
322 node = find_node(tab,key,bucket); |
|
|
323 if (!node) |
|
|
324 { /* OK, try to allocate a new node. */ |
|
|
325 node = allocate_node(key,value); |
|
|
326 if (node) |
|
|
327 { /* Chain the new node into the hash table. */ |
|
|
328 node->next = tab->buckets[bucket]; |
|
|
329 tab->buckets[bucket] = node; |
|
|
330 tab->count++; |
|
|
331 |
|
|
332 } /* end if */ |
|
|
333 else /* allocation error */ |
|
|
334 rc = 0; |
|
|
335 |
|
|
336 } /* end if */ |
|
|
337 else /* already in table - just reassign value */ |
|
|
338 node->value = value; |
|
|
339 |
|
|
340 return rc; |
|
|
341 |
|
|
342 } /* end ghash_put */ |
|
|
343 |
|
|
344 int ghash_remove(HASHTABLE tbl, const void *key) |
|
|
345 /* |
|
|
346 Description: |
|
|
347 Removes an entry from a hash table, given its key. |
|
|
348 |
|
|
349 Input: |
|
|
350 Parameters: |
|
|
351 tbl - Hash table to remove from. |
|
|
352 key - Key of value to remove. |
|
|
353 |
|
|
354 Output: |
|
|
355 Returns: |
|
|
356 1 - Success. |
|
|
357 0 - Failure; key not present in hash table. |
|
|
358 */ |
|
|
359 { |
|
|
360 HASHTABLE_INTERNAL *tab; /* internal table pointer */ |
|
|
361 int bucket; /* bucket value goes into */ |
|
|
362 HNODE *node; /* hash node */ |
|
|
363 register HNODE *p; /* removal pointer */ |
|
|
364 int rc = 1; /* return from this function */ |
|
|
365 |
|
|
366 if (!tbl || !key) |
|
|
367 return 0; /* bogus! */ |
|
|
368 |
|
|
369 /* Convert the handle to a table pointer. */ |
|
|
370 tab = handle2ptr(tbl); |
|
|
371 if (!tab) |
|
|
372 return 0; /* error */ |
|
|
373 |
|
|
374 |
|
|
375 /* Compute the hash bucket and try to find an existing node. */ |
|
|
376 bucket = do_hash(tab,key); |
|
|
377 node = find_node(tab,key,bucket); |
|
|
378 if (node) |
|
|
379 { /* look to unchain it from the bucket it's in */ |
|
|
380 if (node==tab->buckets[bucket]) |
|
|
381 tab->buckets[bucket] = node->next; /* unchain at head */ |
|
|
382 else |
|
|
383 { /* unchain in middle of list */ |
|
|
384 for (p=tab->buckets[bucket]; p->next!=node; p=p->next) ; |
|
|
385 p->next = node->next; |
|
|
386 |
|
|
387 } /* end else */ |
|
|
388 |
|
|
389 free_node(node); /* bye bye now! */ |
|
|
390 tab->count--; |
|
|
391 |
|
|
392 } /* end if */ |
|
|
393 else /* node not found */ |
|
|
394 rc = 0; |
|
|
395 |
|
|
396 return rc; |
|
|
397 |
|
|
398 } /* end ghash_remove */ |
|
|
399 |
|
|
400 int ghash_walk(HASHTABLE tbl, TABLEWALKFUNC func, void *user_data) |
|
|
401 /* |
|
|
402 Description: |
|
|
403 "Walks" through a hash table, calling a callback function for each element |
|
|
404 stored in it. |
|
|
405 |
|
|
406 Input: |
|
|
407 Parameters: |
|
|
408 tbl - Hash table to walk. |
|
|
409 func - Function to be called for each node. It takes three parameters, |
|
|
410 a user data pointer, a key value pointer, and a data value pointer. |
|
|
411 It returns 0 to stop the enumeration or 1 to keep it going. |
|
|
412 user_data - Value to use as the first parameter for the callback |
|
|
413 function. |
|
|
414 |
|
|
415 Output: |
|
|
416 Returns: |
|
|
417 0 - Error occurred. |
|
|
418 Other - Number of nodes visited up to and including the one for which |
|
|
419 the callback function returned 0, if it did; ranges from 1 |
|
|
420 to the number of nodes in the hashtable. |
|
|
421 */ |
|
|
422 { |
|
|
423 HASHTABLE_INTERNAL *tab; /* internal table pointer */ |
|
|
424 int i; /* loop counter */ |
|
|
425 int running = 1; /* we're still running */ |
|
|
426 int count = 0; /* number of nodes visited before stop node */ |
|
|
427 register HNODE *p, *p2; /* loop pointer */ |
|
|
428 |
|
|
429 if (!tbl || !func) |
|
|
430 return -1; /* bogus values! */ |
|
|
431 |
|
|
432 /* Convert the handle to a table pointer. */ |
|
|
433 tab = handle2ptr(tbl); |
|
|
434 if (!tab) |
|
|
435 return -1; /* error */ |
|
|
436 |
|
|
437 |
|
|
438 for (i=0; running && (i<tab->bcount); i++) |
|
|
439 { /* visit the contents of each bucket */ |
|
|
440 p = tab->buckets[i]; |
|
|
441 while (running && p) |
|
|
442 { /* visit each node in turn */ |
|
|
443 p2 = p->next; |
|
|
444 count++; |
|
|
445 running = (*func)(user_data,p->key,p->value); |
|
|
446 p = p2; |
|
|
447 |
|
|
448 } /* end while */ |
|
|
449 |
|
|
450 } /* end for */ |
|
|
451 |
|
|
452 return count; |
|
|
453 |
|
|
454 } /* end ghash_walk */ |
|
|
455 |
|
|
456 int str_hash_code(const char *s) |
|
|
457 /* |
|
|
458 Description: |
|
|
459 Generates a hash code for a string. This function uses the ELF hashing |
|
|
460 algorithm as reprinted in Andrew Binstock, "Hashing Rehashed," _Dr. |
|
|
461 Dobb's Journal_, April 1996. |
|
|
462 |
|
|
463 Input: |
|
|
464 Parameters: |
|
|
465 s - The string to be hashed. |
|
|
466 |
|
|
467 Output: |
|
|
468 Returns: |
|
|
469 A hash code for the string. |
|
|
470 */ |
|
|
471 { |
|
|
472 /* ELF hash uses unsigned chars and unsigned arithmetic for portability */ |
|
|
473 const unsigned char *name = (const unsigned char *)s; |
|
|
474 unsigned long h = 0, g; |
|
|
475 |
|
|
476 if (!name) |
|
|
477 return 0; /* anti-NULL guard not in the original */ |
|
|
478 |
|
|
479 while (*name) |
|
|
480 { /* do some fancy bitwanking on the string */ |
|
|
481 h = (h << 4) + (unsigned long)(*name++); |
|
|
482 if ((g = (h & 0xF0000000UL))!=0) |
|
|
483 h ^= (g >> 24); |
|
|
484 h &= ~g; |
|
|
485 |
|
|
486 } /* end while */ |
|
|
487 |
|
|
488 return (int)h; |
|
|
489 |
|
|
490 } |
