1 /*
2 * Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd.
3 *
4 * All rights reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, and/or sell copies of the Software, and to permit persons
11 * to whom the Software is furnished to do so, provided that the above
12 * copyright notice(s) and this permission notice appear in all copies of
13 * the Software and that both the above copyright notice(s) and this
14 * permission notice appear in supporting documentation.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
17 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
19 * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
20 * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
21 * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
22 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
23 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
24 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
25 *
26 * Except as contained in this notice, the name of a copyright holder
27 * shall not be used in advertising or otherwise to promote the sale, use
28 * or other dealings in this Software without prior written authorization
29 * of the copyright holder.
30 */
31
32 /*
33 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
34 * Use is subject to license terms.
35 */
36
37 #include <stdlib.h>
38 #include <stdio.h>
39 #include <string.h>
40 #include <ctype.h>
41 #include <errno.h>
42
43 #include "hash.h"
44 #include "strngmem.h"
45 #include "freelist.h"
46
47 /*
48 * The following container object contains free-lists to be used
49 * for allocation of HashTable containers and nodes.
50 */
51 struct HashMemory {
52 FreeList *hash_memory; /* HashTable free-list */
53 FreeList *node_memory; /* HashNode free-list */
54 StringMem *string_memory; /* Memory used to allocate hash strings */
55 };
56
57 /*
58 * Define a hash symbol-table entry.
59 * See symbol.h for the definition of the Symbol container type.
60 */
61 typedef struct HashNode HashNode;
62 struct HashNode {
63 Symbol symbol; /* The symbol stored in the hash-entry */
64 HashNode *next; /* The next hash-table entry in a bucket list */
65 };
66
67 /*
68 * Each hash-table bucket contains a linked list of entries that
69 * hash to the same bucket.
70 */
71 typedef struct {
72 HashNode *head; /* The head of the bucket hash-node list */
73 int count; /* The number of entries in the list */
74 } HashBucket;
75
76 /*
77 * A hash-table consists of 'size' hash buckets.
78 * Note that the HashTable typedef for this struct is contained in hash.h.
79 */
80 struct HashTable {
81 HashMemory *mem; /* HashTable free-list */
82 int internal_mem; /* True if 'mem' was allocated by _new_HashTable() */
83 int case_sensitive; /* True if case is significant in lookup keys */
84 int size; /* The number of hash buckets */
85 HashBucket *bucket; /* An array of 'size' hash buckets */
86 int (*keycmp)(const char *, const char *); /* Key comparison function */
87 void *app_data; /* Application-provided data */
88 HASH_DEL_FN(*del_fn); /* Application-provided 'app_data' destructor */
89 };
90
91 static HashNode *_del_HashNode(HashTable *hash, HashNode *node);
92 static HashNode *_new_HashNode(HashTable *hash, const char *name, int code,
93 void (*fn)(void), void *data, SYM_DEL_FN(*del_fn));
94 static HashNode *_find_HashNode(HashTable *hash, HashBucket *bucket,
95 const char *name, HashNode **prev);
96 static HashBucket *_find_HashBucket(HashTable *hash, const char *name);
97 static int _ht_lower_strcmp(const char *node_key, const char *look_key);
98 static int _ht_strcmp(const char *node_key, const char *look_key);
99
100 /*.......................................................................
101 * Allocate a free-list for use in allocating hash tables and their nodes.
102 *
103 * Input:
104 * list_count int The number of HashTable containers per free-list
105 * block.
106 * node_count int The number of HashTable nodes per free-list block.
107 * Output:
108 * return HashMemory * The new free-list for use in allocating hash tables
109 * and their nodes.
110 */
_new_HashMemory(int hash_count,int node_count)111 HashMemory *_new_HashMemory(int hash_count, int node_count)
112 {
113 HashMemory *mem;
114 /*
115 * Allocate the free-list container.
116 */
117 mem = (HashMemory *) malloc(sizeof(HashMemory));
118 if(!mem) {
119 errno = ENOMEM;
120 return NULL;
121 };
122 /*
123 * Initialize the container at least up to the point at which it can
124 * safely be passed to _del_HashMemory().
125 */
126 mem->hash_memory = NULL;
127 mem->node_memory = NULL;
128 mem->string_memory = NULL;
129 /*
130 * Allocate the two free-lists.
131 */
132 mem->hash_memory = _new_FreeList(sizeof(HashTable), hash_count);
133 if(!mem->hash_memory)
134 return _del_HashMemory(mem, 1);
135 mem->node_memory = _new_FreeList(sizeof(HashNode), node_count);
136 if(!mem->node_memory)
137 return _del_HashMemory(mem, 1);
138 mem->string_memory = _new_StringMem(64);
139 if(!mem->string_memory)
140 return _del_HashMemory(mem, 1);
141 /*
142 * Return the free-list container.
143 */
144 return mem;
145 }
146
147 /*.......................................................................
148 * Delete a HashTable free-list. An error will be displayed if the list is
149 * still in use and the deletion will be aborted.
150 *
151 * Input:
152 * mem HashMemory * The free-list container to be deleted.
153 * force int If force==0 then _del_HashMemory() will complain
154 * and refuse to delete the free-list if any
155 * of nodes have not been returned to the free-list.
156 * If force!=0 then _del_HashMemory() will not check
157 * whether any nodes are still in use and will
158 * always delete the list.
159 * Output:
160 * return HashMemory * Always NULL (even if the memory could not be
161 * deleted).
162 */
_del_HashMemory(HashMemory * mem,int force)163 HashMemory *_del_HashMemory(HashMemory *mem, int force)
164 {
165 if(mem) {
166 if(!force && (_busy_FreeListNodes(mem->hash_memory) > 0 ||
167 _busy_FreeListNodes(mem->node_memory) > 0)) {
168 errno = EBUSY;
169 return NULL;
170 };
171 mem->hash_memory = _del_FreeList(mem->hash_memory, force);
172 mem->node_memory = _del_FreeList(mem->node_memory, force);
173 mem->string_memory = _del_StringMem(mem->string_memory, force);
174 free(mem);
175 };
176 return NULL;
177 }
178
179 /*.......................................................................
180 * Create a new hash table.
181 *
182 * Input:
183 * mem HashMemory * An optional free-list for use in allocating
184 * HashTable containers and nodes. See explanation
185 * in hash.h. If you are going to allocate more
186 * than one hash table, then it will be more
187 * efficient to allocate a single free-list for
188 * all of them than to force each hash table
189 * to allocate its own private free-list.
190 * size int The size of the hash table. Best performance
191 * will be acheived if this is a prime number.
192 * hcase HashCase Specify how symbol case is considered when
193 * looking up symbols, from:
194 * IGNORE_CASE - Upper and lower case versions
195 * of a letter are treated as
196 * being identical.
197 * HONOUR_CASE - Upper and lower case versions
198 * of a letter are treated as
199 * being distinct.
200 * characters in a lookup name is significant.
201 * app_data void * Optional application data to be registered
202 * to the table. This is presented to user
203 * provided SYM_DEL_FN() symbol destructors along
204 * with the symbol data.
205 * del_fn() HASH_DEL_FN(*) If you want app_data to be free'd when the
206 * hash-table is destroyed, register a suitable
207 * destructor function here.
208 * Output:
209 * return HashTable * The new hash table, or NULL on error.
210 */
_new_HashTable(HashMemory * mem,int size,HashCase hcase,void * app_data,HASH_DEL_FN (* del_fn))211 HashTable *_new_HashTable(HashMemory *mem, int size, HashCase hcase,
212 void *app_data, HASH_DEL_FN(*del_fn))
213 {
214 HashTable *hash; /* The table to be returned */
215 int allocate_mem = !mem; /* True if mem should be internally allocated */
216 int i;
217 /*
218 * Check arguments.
219 */
220 if(size <= 0) {
221 errno = EINVAL;
222 return NULL;
223 };
224 /*
225 * Allocate an internal free-list?
226 */
227 if(allocate_mem) {
228 mem = _new_HashMemory(1, 100);
229 if(!mem)
230 return NULL;
231 };
232 /*
233 * Allocate the container.
234 */
235 hash = (HashTable *) _new_FreeListNode(mem->hash_memory);
236 if(!hash) {
237 errno = ENOMEM;
238 if(allocate_mem)
239 mem = _del_HashMemory(mem, 1);
240 return NULL;
241 };
242 /*
243 * Before attempting any operation that might fail, initialize
244 * the container at least up to the point at which it can safely
245 * be passed to _del_HashTable().
246 */
247 hash->mem = mem;
248 hash->internal_mem = allocate_mem;
249 hash->case_sensitive = hcase==HONOUR_CASE;
250 hash->size = size;
251 hash->bucket = NULL;
252 hash->keycmp = hash->case_sensitive ? _ht_strcmp : _ht_lower_strcmp;
253 hash->app_data = app_data;
254 hash->del_fn = del_fn;
255 /*
256 * Allocate the array of 'size' hash buckets.
257 */
258 hash->bucket = (HashBucket *) malloc(sizeof(HashBucket) * size);
259 if(!hash->bucket) {
260 errno = ENOMEM;
261 return _del_HashTable(hash);
262 };
263 /*
264 * Initialize the bucket array.
265 */
266 for(i=0; i<size; i++) {
267 HashBucket *b = hash->bucket + i;
268 b->head = NULL;
269 b->count = 0;
270 };
271 /*
272 * The table is ready for use - albeit currently empty.
273 */
274 return hash;
275 }
276
277 /*.......................................................................
278 * Delete a hash-table.
279 *
280 * Input:
281 * hash HashTable * The hash table to be deleted.
282 * Output:
283 * return HashTable * The deleted hash table (always NULL).
284 */
_del_HashTable(HashTable * hash)285 HashTable *_del_HashTable(HashTable *hash)
286 {
287 if(hash) {
288 /*
289 * Clear and delete the bucket array.
290 */
291 if(hash->bucket) {
292 _clear_HashTable(hash);
293 free(hash->bucket);
294 hash->bucket = NULL;
295 };
296 /*
297 * Delete application data.
298 */
299 if(hash->del_fn)
300 hash->del_fn(hash->app_data);
301 /*
302 * If the hash table was allocated from an internal free-list, delete
303 * it and the hash table by deleting the free-list. Otherwise just
304 * return the hash-table to the external free-list.
305 */
306 if(hash->internal_mem)
307 _del_HashMemory(hash->mem, 1);
308 else
309 hash = (HashTable *) _del_FreeListNode(hash->mem->hash_memory, hash);
310 };
311 return NULL;
312 }
313
314 /*.......................................................................
315 * Create and install a new entry in a hash table. If an entry with the
316 * same name already exists, replace its contents with the new data.
317 *
318 * Input:
319 * hash HashTable * The hash table to insert the symbol into.
320 * name const char * The name to tag the entry with.
321 * code int An application-specific code to be stored in
322 * the entry.
323 * fn void (*)(void) An application-specific function to be stored
324 * in the entry.
325 * data void * An application-specific pointer to data to be
326 * associated with the entry, or NULL if not
327 * relevant.
328 * del_fn SYM_DEL_FN(*) An optional destructor function. When the
329 * symbol is deleted this function will be called
330 * with the 'code' and 'data' arguments given
331 * above. Any application data that was registered
332 * to the table via the app_data argument of
333 * _new_HashTable() will also be passed.
334 * Output:
335 * return HashNode * The new entry, or NULL if there was insufficient
336 * memory or the arguments were invalid.
337 */
_new_HashSymbol(HashTable * hash,const char * name,int code,void (* fn)(void),void * data,SYM_DEL_FN (* del_fn))338 Symbol *_new_HashSymbol(HashTable *hash, const char *name, int code,
339 void (*fn)(void), void *data, SYM_DEL_FN(*del_fn))
340 {
341 HashBucket *bucket; /* The hash-bucket associated with the name */
342 HashNode *node; /* The new node */
343 /*
344 * Check arguments.
345 */
346 if(!hash || !name) {
347 errno = EINVAL;
348 return NULL;
349 };
350 /*
351 * Get the hash bucket of the specified name.
352 */
353 bucket = _find_HashBucket(hash, name);
354 /*
355 * See if a node with the same name already exists.
356 */
357 node = _find_HashNode(hash, bucket, name, NULL);
358 /*
359 * If found, delete its contents by calling the user-supplied
360 * destructor function, if provided.
361 */
362 if(node) {
363 if(node->symbol.data && node->symbol.del_fn) {
364 node->symbol.data = node->symbol.del_fn(hash->app_data, node->symbol.code,
365 node->symbol.data);
366 };
367 /*
368 * Allocate a new node if necessary.
369 */
370 } else {
371 node = _new_HashNode(hash, name, code, fn, data, del_fn);
372 if(!node)
373 return NULL;
374 };
375 /*
376 * Install the node at the head of the hash-bucket list.
377 */
378 node->next = bucket->head;
379 bucket->head = node;
380 bucket->count++;
381 return &node->symbol;
382 }
383
384 /*.......................................................................
385 * Remove and delete a given hash-table entry.
386 *
387 * Input:
388 * hash HashTable * The hash table to find the symbol in.
389 * name const char * The name of the entry.
390 * Output:
391 * return HashNode * The deleted hash node (always NULL).
392 */
_del_HashSymbol(HashTable * hash,const char * name)393 Symbol *_del_HashSymbol(HashTable *hash, const char *name)
394 {
395 if(hash && name) {
396 HashBucket *bucket = _find_HashBucket(hash, name);
397 HashNode *prev; /* The node preceding the located node */
398 HashNode *node = _find_HashNode(hash, bucket, name, &prev);
399 /*
400 * Node found?
401 */
402 if(node) {
403 /*
404 * Remove the node from the bucket list.
405 */
406 if(prev) {
407 prev->next = node->next;
408 } else {
409 bucket->head = node->next;
410 };
411 /*
412 * Record the loss of a node.
413 */
414 bucket->count--;
415 /*
416 * Delete the node.
417 */
418 (void) _del_HashNode(hash, node);
419 };
420 };
421 return NULL;
422 }
423
424 /*.......................................................................
425 * Look up a symbol in the hash table.
426 *
427 * Input:
428 * hash HashTable * The table to look up the string in.
429 * name const char * The name of the symbol to look up.
430 * Output:
431 * return Symbol * The located hash-table symbol, or NULL if not
432 * found.
433 */
_find_HashSymbol(HashTable * hash,const char * name)434 Symbol *_find_HashSymbol(HashTable *hash, const char *name)
435 {
436 HashBucket *bucket; /* The hash-table bucket associated with name[] */
437 HashNode *node; /* The hash-table node of the requested symbol */
438 /*
439 * Check arguments.
440 */
441 if(!hash)
442 return NULL;
443 /*
444 * Nothing to lookup?
445 */
446 if(!name)
447 return NULL;
448 /*
449 * Hash the name to a hash-table bucket.
450 */
451 bucket = _find_HashBucket(hash, name);
452 /*
453 * Find the bucket entry that exactly matches the name.
454 */
455 node = _find_HashNode(hash, bucket, name, NULL);
456 if(!node)
457 return NULL;
458 return &node->symbol;
459 }
460
461 /*.......................................................................
462 * Private function used to allocate a hash-table node.
463 * The caller is responsible for checking that the specified symbol
464 * is unique and for installing the returned entry in the table.
465 *
466 * Input:
467 * hash HashTable * The table to allocate the node for.
468 * name const char * The name of the new entry.
469 * code int A user-supplied context code.
470 * fn void (*)(void) A user-supplied function pointer.
471 * data void * A user-supplied data pointer.
472 * del_fn SYM_DEL_FN(*) An optional 'data' destructor function.
473 * Output:
474 * return HashNode * The new node, or NULL on error.
475 */
_new_HashNode(HashTable * hash,const char * name,int code,void (* fn)(void),void * data,SYM_DEL_FN (* del_fn))476 static HashNode *_new_HashNode(HashTable *hash, const char *name, int code,
477 void (*fn)(void), void *data, SYM_DEL_FN(*del_fn))
478 {
479 HashNode *node; /* The new node */
480 size_t len;
481 /*
482 * Allocate the new node from the free list.
483 */
484 node = (HashNode *) _new_FreeListNode(hash->mem->node_memory);
485 if(!node)
486 return NULL;
487 /*
488 * Before attempting any operation that might fail, initialize the
489 * contents of 'node' at least up to the point at which it can be
490 * safely passed to _del_HashNode().
491 */
492 node->symbol.name = NULL;
493 node->symbol.code = code;
494 node->symbol.fn = fn;
495 node->symbol.data = data;
496 node->symbol.del_fn = del_fn;
497 node->next = NULL;
498 /*
499 * Allocate a copy of 'name'.
500 */
501 len = strlen(name) + 1;
502 node->symbol.name = _new_StringMemString(hash->mem->string_memory, len);
503 if(!node->symbol.name)
504 return _del_HashNode(hash, node);
505 /*
506 * If character-case is insignificant in the current table, convert the
507 * name to lower case while copying it.
508 */
509 if(hash->case_sensitive) {
510 strlcpy(node->symbol.name, name, len);
511 } else {
512 const char *src = name;
513 char *dst = node->symbol.name;
514 for( ; *src; src++,dst++)
515 *dst = tolower(*src);
516 *dst = '\0';
517 };
518 return node;
519 }
520
521 /*.......................................................................
522 * Private function used to delete a hash-table node.
523 * The node must have been removed from its list before calling this
524 * function.
525 *
526 * Input:
527 * hash HashTable * The table for which the node was originally
528 * allocated.
529 * node HashNode * The node to be deleted.
530 * Output:
531 * return HashNode * The deleted node (always NULL).
532 */
_del_HashNode(HashTable * hash,HashNode * node)533 static HashNode *_del_HashNode(HashTable *hash, HashNode *node)
534 {
535 if(node) {
536 node->symbol.name = _del_StringMemString(hash->mem->string_memory,
537 node->symbol.name);
538 /*
539 * Call the user-supplied data-destructor if provided.
540 */
541 if(node->symbol.data && node->symbol.del_fn)
542 node->symbol.data = node->symbol.del_fn(hash->app_data,
543 node->symbol.code,
544 node->symbol.data);
545 /*
546 * Return the node to the free-list.
547 */
548 node->next = NULL;
549 node = (HashNode *) _del_FreeListNode(hash->mem->node_memory, node);
550 };
551 return NULL;
552 }
553
554 /*.......................................................................
555 * Private function to locate the hash bucket associated with a given
556 * name.
557 *
558 * This uses a hash-function described in the dragon-book
559 * ("Compilers - Principles, Techniques and Tools", by Aho, Sethi and
560 * Ullman; pub. Adison Wesley) page 435.
561 *
562 * Input:
563 * hash HashTable * The table to look up the string in.
564 * name const char * The name of the symbol to look up.
565 * Output:
566 * return HashBucket * The located hash-bucket.
567 */
_find_HashBucket(HashTable * hash,const char * name)568 static HashBucket *_find_HashBucket(HashTable *hash, const char *name)
569 {
570 unsigned const char *kp;
571 unsigned long h = 0L;
572 if(hash->case_sensitive) {
573 for(kp=(unsigned const char *) name; *kp; kp++)
574 h = 65599UL * h + *kp; /* 65599 is a prime close to 2^16 */
575 } else {
576 for(kp=(unsigned const char *) name; *kp; kp++)
577 h = 65599UL * h + tolower((int)*kp); /* 65599 is a prime close to 2^16 */
578 };
579 return hash->bucket + (h % hash->size);
580 }
581
582 /*.......................................................................
583 * Search for a given name in the entries of a given bucket.
584 *
585 * Input:
586 * hash HashTable * The hash-table being searched.
587 * bucket HashBucket * The bucket to search (use _find_HashBucket()).
588 * name const char * The name to search for.
589 * Output:
590 * prev HashNode ** If prev!=NULL then the pointer to the node
591 * preceding the located node in the list will
592 * be recorded in *prev. This will be NULL either
593 * if the name is not found or the located node is
594 * at the head of the list of entries.
595 * return HashNode * The located hash-table node, or NULL if not
596 * found.
597 */
_find_HashNode(HashTable * hash,HashBucket * bucket,const char * name,HashNode ** prev)598 static HashNode *_find_HashNode(HashTable *hash, HashBucket *bucket,
599 const char *name, HashNode **prev)
600 {
601 HashNode *last; /* The previously searched node */
602 HashNode *node; /* The node that is being searched */
603 /*
604 * Search the list for a node containing the specified name.
605 */
606 for(last=NULL, node=bucket->head;
607 node && hash->keycmp(node->symbol.name, name)!=0;
608 last = node, node=node->next)
609 ;
610 if(prev)
611 *prev = node ? last : NULL;
612 return node;
613 }
614
615 /*.......................................................................
616 * When hash->case_sensitive is zero this function is called
617 * in place of strcmp(). In such cases the hash-table names are stored
618 * as lower-case versions of the original strings so this function
619 * performs the comparison against lower-case copies of the characters
620 * of the string being compared.
621 *
622 * Input:
623 * node_key const char * The lower-case hash-node key being compared
624 * against.
625 * look_key const char * The lookup key.
626 * Output:
627 * return int <0 if node_key < look_key.
628 * 0 if node_key == look_key.
629 * >0 if node_key > look_key.
630 */
_ht_lower_strcmp(const char * node_key,const char * look_key)631 static int _ht_lower_strcmp(const char *node_key, const char *look_key)
632 {
633 int cn; /* The latest character from node_key[] */
634 int cl; /* The latest character from look_key[] */
635 do {
636 cn = *node_key++;
637 cl = *look_key++;
638 } while(cn && cn==tolower(cl));
639 return cn - tolower(cl);
640 }
641
642 /*.......................................................................
643 * This is a wrapper around strcmp for comparing hash-keys in a case
644 * sensitive manner. The reason for having this wrapper, instead of using
645 * strcmp() directly, is to make some C++ compilers happy. The problem
646 * is that when the library is compiled with a C++ compiler, the
647 * declaration of the comparison function is a C++ declaration, whereas
648 * strcmp() is a pure C function and thus although it appears to have the
649 * same declaration, the compiler disagrees.
650 *
651 * Input:
652 * node_key char * The lower-case hash-node key being compared against.
653 * look_key char * The lookup key.
654 * Output:
655 * return int <0 if node_key < look_key.
656 * 0 if node_key == look_key.
657 * >0 if node_key > look_key.
658 */
_ht_strcmp(const char * node_key,const char * look_key)659 static int _ht_strcmp(const char *node_key, const char *look_key)
660 {
661 return strcmp(node_key, look_key);
662 }
663
664 /*.......................................................................
665 * Empty a hash-table by deleting all of its entries.
666 *
667 * Input:
668 * hash HashTable * The hash table to clear.
669 * Output:
670 * return int 0 - OK.
671 * 1 - Invalid arguments.
672 */
_clear_HashTable(HashTable * hash)673 int _clear_HashTable(HashTable *hash)
674 {
675 int i;
676 /*
677 * Check the arguments.
678 */
679 if(!hash)
680 return 1;
681 /*
682 * Clear the contents of the bucket array.
683 */
684 for(i=0; i<hash->size; i++) {
685 HashBucket *bucket = hash->bucket + i;
686 /*
687 * Delete the list of active hash nodes from the bucket.
688 */
689 HashNode *node = bucket->head;
690 while(node) {
691 HashNode *next = node->next;
692 (void) _del_HashNode(hash, node);
693 node = next;
694 };
695 /*
696 * Mark the bucket as empty.
697 */
698 bucket->head = NULL;
699 bucket->count = 0;
700 };
701 return 0;
702 }
703
704 /*.......................................................................
705 * Execute a given function on each entry of a hash table, returning
706 * before completion if the the specified function returns non-zero.
707 *
708 * Input:
709 * hash HashTable * The table to traverse.
710 * scan_fn HASH_SCAN_FN(*) The function to call.
711 * context void * Optional caller-specific context data
712 * to be passed to scan_fn().
713 * Output:
714 * return int 0 - OK.
715 * 1 - Either the arguments were invalid, or
716 * scan_fn() returned non-zero at some
717 * point.
718 */
_scan_HashTable(HashTable * hash,HASH_SCAN_FN (* scan_fn),void * context)719 int _scan_HashTable(HashTable *hash, HASH_SCAN_FN(*scan_fn), void *context)
720 {
721 int i;
722 /*
723 * Check the arguments.
724 */
725 if(!hash || !scan_fn)
726 return 1;
727 /*
728 * Iterate through the buckets of the table.
729 */
730 for(i=0; i<hash->size; i++) {
731 HashBucket *bucket = hash->bucket + i;
732 HashNode *node;
733 /*
734 * Iterate through the list of symbols that fall into bucket i,
735 * passing each one to the caller-specified function.
736 */
737 for(node=bucket->head; node; node=node->next) {
738 if(scan_fn(&node->symbol, context))
739 return 1;
740 };
741 };
742 return 0;
743 }
744