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