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
allocate_node(const void * key,void * value)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
free_node(HNODE * node)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
find_node(HASHTABLE_INTERNAL * tab,const void * key,int bucket)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
handle2ptr(HASHTABLE tbl)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
ghash_create(int buckets,KEYHASHFUNC hash,KEYCOMPAREFUNC cmp)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
ghash_destroy(HASHTABLE tbl)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
ghash_get(HASHTABLE tbl,const void * key)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
ghash_put(HASHTABLE tbl,const void * key,void * value)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
ghash_remove(HASHTABLE tbl,const void * key)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
ghash_walk(HASHTABLE tbl,TABLEWALKFUNC func,void * user_data)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
str_hash_code(const char * s)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 }
491