xref: /illumos-gate/usr/src/lib/libtecla/common/hash.c (revision 1da57d551424de5a9d469760be7c4b4d4f10a755)
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