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