Azinix

st.c

Go to the documentation of this file.
00001 /** \file st.c
00002 
00003 \brief Hash code
00004 
00005 */
00006 
00007 #include <stdio.h>
00008 #include "util.h"
00009 #include "st.h"
00010 
00011 /**AutomaticStart*************************************************************/
00012 
00013 /*---------------------------------------------------------------------------*/
00014 /* Static function prototypes                                                */
00015 /*---------------------------------------------------------------------------*/
00016 
00017 
00018 /**AutomaticEnd***************************************************************/
00019 
00020 
00021 static inline int
00022 HASH_NUMCMP (int x, int y)
00023 {
00024   return (x != y);
00025 }
00026 
00027 static inline int
00028 HASH_NUMHASH (int x, int size)
00029 {
00030   return ABS ((long) x) % (size);
00031 }
00032 
00033 static inline int
00034 HASH_PTRHASH (void *x, int size)
00035 {
00036   return ((int) ((unsigned long) (x) >> 2) % (size));
00037 }
00038 
00039 // #define HASH_EQUAL(func, x, y) \
00040 //    ((((func) == Hash_NumCmp) || ((func) == Hash_PtrCmp)) ?\
00041 //      (HASH_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))
00042 
00043 static inline int HASH_EQUAL( int (*func)(), void *x, void *y ) {
00044   return ((((func) == (int(*)()) Hash_NumCmp) || ((func) == (int(*)()) Hash_PtrCmp)) ?
00045     (HASH_NUMCMP(((int) x),((int) y)) == 0) : 
00046         ( ( (* ( int(*)(void *,void *) ) func  ) ( x, y ) ) == 0) );
00047 }
00048 
00049 // #define do_hash(key, table)\
00050 //     ((table->hash == Hash_PtrHash) ? HASH_PTRHASH((key),(table)->num_bins) :\
00051 //      (table->hash == Hash_NumHash) ? HASH_NUMHASH((key), (table)->num_bins) :\
00052 //      (*table->hash)((key), (table)->num_bins))
00053 
00054 static inline int do_hash( void *key, Hash_t *table) {
00055     if ((table->hash == (ST_PFI) Hash_PtrHash) ) {
00056       return HASH_PTRHASH( key,(table)->num_bins);
00057     }
00058     if ((table->hash == (ST_PFI) Hash_NumHash) ) {
00059       return HASH_NUMHASH( (int) key,(table)->num_bins);
00060     }
00061     return ( ( * ( ( int(*)( void *, int ) ) (table->hash) ) )( key, (table)->num_bins ) );
00062 }
00063 
00064 static int rehash ( Hash_t *table );
00065 
00066 Hash_t *st_init_table_with_params( ST_PFI a, ST_PFI b, int c, int d, double e, int f) { 
00067   return Hash_InitTableWithParams (a, b, c, d, e, f ); 
00068 }
00069 
00070 Hash_t *st_init_table (ST_PFI a, ST_PFI b) {
00071   return Hash_InitTable( a, b );
00072 }
00073 
00074 void st_free_table (Hash_t * a) {
00075   return Hash_FreeTable( a );
00076 }
00077 
00078 int st_lookup (Hash_t * a, char * b, char ** c) {
00079   return Hash_Lookup( a, b, c );
00080 }
00081 
00082 int st_lookup_int (Hash_t * a, char * b, int * c) {
00083   return Hash_LookupInt( a, b,c );
00084 }
00085 
00086 int st_insert (Hash_t * a, char * b, char * c) {
00087   return Hash_Insert( a, b, c );
00088 }
00089 
00090 int st_add_direct (Hash_t * a, char * b, char * c) {
00091   return Hash_AddDirect( a, b, c );
00092 }
00093 
00094 int st_find_or_add (Hash_t * a, char * b, char *** c){
00095   return Hash_FindOrAdd( a, b, c );
00096 }
00097 
00098 int st_find (Hash_t * a, char * b, char *** c) {
00099   return Hash_Find( a, b, c );
00100 }
00101 
00102 Hash_t *st_copy (Hash_t * a) {
00103   return Hash_Copy( a );
00104 }
00105 
00106 int st_delete (Hash_t * a, char ** b, char ** c) {
00107   return Hash_Delete( a, b, c );
00108 }
00109 
00110 int st_delete_int (Hash_t * a, int * b, char ** c) {
00111   return Hash_DeleteInt( a, b, c );
00112 }
00113 
00114 int st_foreach (Hash_t * a, ST_PFSR b, char * c) {
00115   return Hash_ForEach( a, b, c );
00116 }
00117 
00118 int st_strhash (char * a, int b) {
00119   return Hash_StrHash( a, b );
00120 }
00121 
00122 int st_numhash (char * a, int b) {
00123   return Hash_NumHash( a, b );
00124 }
00125 
00126 int st_ptrhash (char * a, int b) {
00127   return Hash_PtrHash( a, b );
00128 }
00129 
00130 int st_numcmp  (int a, int b) {
00131   return Hash_NumCmp( a, b );
00132 }
00133 
00134 int st_ptrcmp (char * a, char * b) {
00135   return Hash_PtrCmp( a, b );
00136 }
00137 
00138 int st_gen (Hash_Generator_t * a, char ** b, char ** c) {
00139   return Hash_Gen( a, b, c );
00140 }
00141 
00142 int st_gen_int (Hash_Generator_t * a, char ** b, int * c) {
00143   return Hash_GenInt( a, b, c );
00144 }
00145 
00146 Hash_Generator_t *st_init_gen (Hash_t * a) {
00147   return Hash_InitGen( a );
00148 }
00149 
00150 void st_free_gen (Hash_Generator_t * a) {
00151   return Hash_FreeGen( a );
00152 }
00153 
00154 /** \brief The full blown table initializer.  
00155 
00156 <code>compare</code> and <code>hash</code> are the same
00157     as in <code>Hash_InitTable</code>. <code>density</code> is the largest the average number of
00158     entries per hash bin there should be before the table is grown.
00159     <code>grow_factor</code> is the factor the table is grown by when it becomes too
00160     full. <code>size</code> is the initial number of bins to be allocated for the hash
00161     table.  If <code>reorder_flag</code> is non-zero, then everytime an entry is found,
00162     it is moved to the top of the chain.
00163                                                                                                            
00164    <code>Hash_InitTable(compare, hash)</code> is equivelent to
00165 <pre>
00166    Hash_InitTableWithParams(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE,
00167                                      ST_DEFAULT_MAX_DENSITY,
00168                                      ST_DEFAULT_GROW_FACTOR,
00169                                      ST_DEFAULT_REORDER_FLAG);
00170 </pre>
00171 */
00172 
00173 Hash_t *
00174 Hash_InitTableWithParams (int (*compare) (), int (*hash) (), int size,
00175                int density, double grow_factor, int reorder_flag)
00176 {
00177   int i;
00178   Hash_t *newHash;
00179 
00180   newHash = ALLOC (Hash_t, 1);
00181   if (newHash == NIL (Hash_t))
00182     {
00183       return NIL (Hash_t);
00184     }
00185   newHash->compare = compare;
00186   newHash->hash = hash;
00187   newHash->num_entries = 0;
00188   newHash->max_density = density;
00189   newHash->grow_factor = grow_factor;
00190   newHash->reorder_flag = reorder_flag;
00191   if (size <= 0)
00192     {
00193       size = 1;
00194     }
00195   newHash->num_bins = size;
00196   newHash->bins = ALLOC (Hash_Entry_t *, size);
00197   if (newHash->bins == NIL (Hash_Entry_t *))
00198     {
00199       free (newHash);
00200       return NIL (Hash_t);
00201     }
00202   for (i = 0; i < size; i++)
00203     {
00204       newHash->bins[i] = 0;
00205     }
00206   return newHash;
00207 }
00208 
00209 
00210 /** \brief  Create and initialize a table with the comparison function compare_fn and
00211     hash function hash_fn. 
00212 
00213 compare_fn is
00214 
00215 <pre>                                                                                                           
00216         int compare_fn(char *key1, char *key2)
00217 </pre> returns <,=,> 0 depending on whether <code>key1 <,=,> key2</code> by some measure
00218 
00219 and  hash_fn is
00220 
00221 <pre>                                                                                                           
00222         int hash_fn(char *key, int modulus)
00223 </pre>
00224 returns a integer between 0 and modulus-1
00225 such that if <code>compare_fn(key1,key2) == 0</code> then
00226 <code>hash_fn(key1) == hash_fn(key2)</code>
00227                                                                                                            
00228      There are five predefined hash and comparison functions in st.
00229 <ul>
00230     <li> For keys as numbers:
00231          <pre>Hash_NumHash(key, modulus) { return (unsigned int) key % modulus; }</pre>
00232          <pre>Hash_NumCmp(x,y) { return (int) x - (int) y; }</pre>
00233 
00234      <li>For keys as pointers:
00235         <pre>Hash_PreHash(key, modulus) { return ((unsigned int) key/4) % modulus }</pre>
00236         <pre>Hash_PtrCmp(x,y) { return (int) x - (int) y; }</pre>
00237 
00238      <li> For keys as strings:
00239          <pre>Hash_StrHash(x,y)</pre> - a reasonable hashing function for strings
00240          <pre>strcmp(x,y)</pre> - the standard library function
00241    
00242 </ul>                                                                                                        
00243      It is recommended to use these particular functions if they fit your
00244      needs, since st will recognize certain of them and run more quickly
00245      because of it.
00246 */
00247 
00248 Hash_t *
00249 Hash_InitTable ( int (*compare) (), int (*hash) () )
00250 {
00251   return Hash_InitTableWithParams (compare, hash, HASH_DEFAULT_INIT_TABLE_SIZE,
00252                     HASH_DEFAULT_MAX_DENSITY,
00253                     HASH_DEFAULT_GROW_FACTOR,
00254                     HASH_DEFAULT_REORDER_FLAG);
00255 }
00256 
00257 
00258 /** \brief Free any internal storage associated with table.  
00259 
00260 It is the user's
00261 responsibility to free any storage associated with the pointers he
00262 placed in the table (by perhaps using Hash_ForEach).
00263 */
00264 
00265 void
00266 Hash_FreeTable (
00267      Hash_t *table )
00268 {
00269   Hash_Entry_t *ptr, *next;
00270   int i;
00271 
00272   for (i = 0; i < table->num_bins; i++)
00273     {
00274       ptr = table->bins[i];
00275       while (ptr != NIL (Hash_Entry_t))
00276     {
00277       next = ptr->next;
00278       free (ptr);
00279       ptr = next;
00280     }
00281     }
00282   free (table->bins);
00283   free (table);
00284 }
00285 
00286 #define PTR_NOT_EQUAL(table, ptr, user_key)\
00287 (ptr != NIL(Hash_Entry_t) && !HASH_EQUAL(table->compare, user_key, (ptr)->key))
00288 
00289 #define FIND_ENTRY(table, hash_val, key, ptr, last) \
00290     (last) = &(table)->bins[hash_val];\
00291     (ptr) = *(last);\
00292     while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
00293     (last) = &(ptr)->next; (ptr) = *(last);\
00294     }\
00295     if ((ptr) != NIL(Hash_Entry_t) && (table)->reorder_flag) {\
00296     *(last) = (ptr)->next;\
00297     (ptr)->next = (table)->bins[hash_val];\
00298     (table)->bins[hash_val] = (ptr);\
00299     }
00300 
00301 
00302 /** \brief Lookup up `key' in `table'. 
00303 
00304 If an entry is found, 1 is returned
00305 and if `value_ptr' is not nil, the variable it points to is set to
00306 associated value.  If an entry is not found, 0 is return and
00307 value_ptr is unchanged.
00308 */
00309 
00310 int
00311 Hash_Lookup(
00312      Hash_t *table,
00313      char *key,
00314      char **value
00315 )
00316 {
00317   int hash_val;
00318   Hash_Entry_t *ptr, **last;
00319 
00320   hash_val = do_hash (key, table);
00321 
00322   FIND_ENTRY (table, hash_val, key, ptr, last);
00323 
00324   if (ptr == NIL (Hash_Entry_t))
00325     {
00326       return 0;
00327     }
00328   else
00329     {
00330       if (value != NIL (char *))
00331     {
00332       *value = ptr->record;
00333     }
00334       return 1;
00335     }
00336 }
00337 
00338 
00339 /** \brief Lookup up int `key' in `table'. 
00340 
00341 If an entry is found, 1 is returned
00342 and if `int_ptr' is not nil, the variable it points to is set to
00343 associated integer value.  If an entry is not found, 0 is return and
00344 int_ptr is unchanged.
00345 */
00346 
00347 int
00348 Hash_LookupInt (
00349      Hash_t *table,
00350      char *key,
00351      int *value
00352 )
00353 {
00354   int hash_val;
00355    Hash_Entry_t *ptr, **last;
00356 
00357   hash_val = do_hash (key, table);
00358 
00359   FIND_ENTRY (table, hash_val, key, ptr, last);
00360 
00361   if (ptr == NIL (Hash_Entry_t))
00362     {
00363       return 0;
00364     }
00365   else
00366     {
00367       if (value != NIL (int))
00368     {
00369       *value = (long) ptr->record;
00370     }
00371       return 1;
00372     }
00373 }
00374 
00375 /* This macro does not check if memory allocation fails. Use at your own risk */
00376 #define ADD_DIRECT(table, key, value, hash_val, newHash)\
00377 {\
00378     if (table->num_entries/table->num_bins >= table->max_density) {\
00379     rehash(table);\
00380     hash_val = do_hash(key,table);\
00381     }\
00382     \
00383     newHash = ALLOC(Hash_Entry_t, 1);\
00384     \
00385     newHash->key = key;\
00386     newHash->record = value;\
00387     newHash->next = table->bins[hash_val];\
00388     table->bins[hash_val] = newHash;\
00389     table->num_entries++;\
00390 }
00391 
00392 /** \brief  Insert value in table under the key 'key'.  
00393 
00394 Returns 1 if there was
00395 an entry already under the key, 0 otherewise.  
00396 In either case the new value is added.
00397 */
00398 
00399 int
00400 Hash_Insert (
00401      Hash_t *table,
00402      char *key,
00403      char *value
00404 )
00405 {
00406   int hash_val;
00407   Hash_Entry_t *newHash;
00408   Hash_Entry_t *ptr, **last;
00409 
00410   hash_val = do_hash (key, table);
00411 
00412   FIND_ENTRY (table, hash_val, key, ptr, last);
00413 
00414   if (ptr == NIL (Hash_Entry_t))
00415     {
00416       if (table->num_entries / table->num_bins >= table->max_density)
00417     {
00418       if (rehash (table) == HASH_OUT_OF_MEM)
00419         {
00420           return HASH_OUT_OF_MEM;
00421         }
00422       hash_val = do_hash (key, table);
00423     }
00424       newHash = ALLOC (Hash_Entry_t, 1);
00425       if (newHash == NIL (Hash_Entry_t))
00426     {
00427       return HASH_OUT_OF_MEM;
00428     }
00429       newHash->key = key;
00430       newHash->record = value;
00431       newHash->next = table->bins[hash_val];
00432       table->bins[hash_val] = newHash;
00433       table->num_entries++;
00434       return 0;
00435     }
00436   else
00437     {
00438       ptr->record = value;
00439       return 1;
00440     }
00441 }
00442 
00443 
00444 /** \brief Place 'value' in 'table' under the key 'key'.  This is done
00445     without checking if 'key' is in 'table' already.  
00446 
00447 This should only be used if you are sure there is not already an entry for
00448 'key', since it is undefined which entry you would later get from
00449 Hash_Lookup or Hash_FindOrAdd.
00450 */
00451 
00452 int
00453 Hash_AddDirect (
00454      Hash_t *table,
00455      char *key,
00456      char *value
00457 )
00458 {
00459   int hash_val;
00460   Hash_Entry_t *newHash;
00461 
00462   hash_val = do_hash (key, table);
00463   if (table->num_entries / table->num_bins >= table->max_density)
00464     {
00465       if (rehash (table) == HASH_OUT_OF_MEM)
00466     {
00467       return HASH_OUT_OF_MEM;
00468     }
00469     }
00470   hash_val = do_hash (key, table);
00471   newHash = ALLOC (Hash_Entry_t, 1);
00472   if (newHash == NIL (Hash_Entry_t))
00473     {
00474       return HASH_OUT_OF_MEM;
00475     }
00476   newHash->key = key;
00477   newHash->record = value;
00478   newHash->next = table->bins[hash_val];
00479   table->bins[hash_val] = newHash;
00480   table->num_entries++;
00481   return 1;
00482 }
00483 
00484 /** \brief Lookup `key' in `table'.  If not found, create an entry.In either case
00485    set slot to point to the field in the entry where the value is stored.
00486    The value associated with `key' may then be changed by accessing
00487    directly through slot.  Returns 1 if an entry already existed, 0
00488    otherwise. 
00489 
00490 As an example:
00491 <pre>                                                                                                      
00492       char **slot;
00493       char *key;
00494       char *value = (char *) item_ptr // ptr to a malloc'd structure 
00495                                                                                                            
00496       if (Hash_FindOrAdd(table, key, &slot)) {
00497          FREE(*slot); // free the old value of the record 
00498       }
00499       *slot = value;  // attach the new value to the record 
00500 </pre>
00501                                                                                                            
00502 This replaces the equivelent code:
00503 <pre>                                                                                                      
00504       if (Hash_Lookup(table, key, &ovalue)) {
00505          FREE(ovalue);
00506       }
00507       Hash_Insert(table, key, value);
00508 </pre>
00509 
00510 */
00511 
00512 int
00513 Hash_FindOrAdd(
00514      Hash_t *table,
00515      char *key,
00516      char ***slot
00517 )
00518 {
00519   int hash_val;
00520   Hash_Entry_t *newHash, *ptr, **last;
00521 
00522   hash_val = do_hash (key, table);
00523 
00524   FIND_ENTRY (table, hash_val, key, ptr, last);
00525 
00526   if (ptr == NIL (Hash_Entry_t))
00527     {
00528       if (table->num_entries / table->num_bins >= table->max_density)
00529     {
00530       if (rehash (table) == HASH_OUT_OF_MEM)
00531         {
00532           return HASH_OUT_OF_MEM;
00533         }
00534       hash_val = do_hash (key, table);
00535     }
00536       newHash = ALLOC (Hash_Entry_t, 1);
00537       if (newHash == NIL (Hash_Entry_t))
00538     {
00539       return HASH_OUT_OF_MEM;
00540     }
00541       newHash->key = key;
00542       newHash->record = (char *) 0;
00543       newHash->next = table->bins[hash_val];
00544       table->bins[hash_val] = newHash;
00545       table->num_entries++;
00546       if (slot != NIL (char **))
00547      *slot = &newHash->record;
00548       return 0;
00549     }
00550   else
00551     {
00552       if (slot != NIL (char **))
00553      *slot = &ptr->record;
00554       return 1;
00555     }
00556 }
00557 
00558 
00559 /** \brief Like <code>Hash_FindOrAdd</code>, but does not create an entry if one is not found.
00560 */
00561 
00562 int
00563 Hash_Find (
00564      Hash_t *table,
00565      char *key,
00566      char ***slot
00567 )
00568 {
00569   int hash_val;
00570   Hash_Entry_t *ptr, **last;
00571 
00572   hash_val = do_hash (key, table);
00573 
00574   FIND_ENTRY (table, hash_val, key, ptr, last);
00575 
00576   if (ptr == NIL (Hash_Entry_t))
00577     {
00578       return 0;
00579     }
00580   else
00581     {
00582       if (slot != NIL (char **))
00583     {
00584       *slot = &ptr->record;
00585     }
00586       return 1;
00587     }
00588 }
00589 
00590 
00591 /** \brief Rehash a table
00592 
00593 */
00594 
00595 static int
00596 rehash ( Hash_t *table )
00597 {
00598    Hash_Entry_t *ptr, *next, **old_bins;
00599   int i, old_num_bins, hash_val, old_num_entries;
00600 
00601   /* save old values */
00602   old_bins = table->bins;
00603   old_num_bins = table->num_bins;
00604   old_num_entries = table->num_entries;
00605 
00606   /* rehash */
00607   table->num_bins = table->grow_factor * old_num_bins;
00608   if (table->num_bins % 2 == 0)
00609     {
00610       table->num_bins += 1;
00611     }
00612   table->num_entries = 0;
00613   table->bins = ALLOC (Hash_Entry_t *, table->num_bins);
00614   if (table->bins == NIL (Hash_Entry_t *))
00615     {
00616       table->bins = old_bins;
00617       table->num_bins = old_num_bins;
00618       table->num_entries = old_num_entries;
00619       return HASH_OUT_OF_MEM;
00620     }
00621   /* initialize */
00622   for (i = 0; i < table->num_bins; i++)
00623     {
00624       table->bins[i] = 0;
00625     }
00626 
00627   /* copy data over */
00628   for (i = 0; i < old_num_bins; i++)
00629     {
00630       ptr = old_bins[i];
00631       while (ptr != NIL (Hash_Entry_t))
00632     {
00633       next = ptr->next;
00634       hash_val = do_hash (ptr->key, table);
00635       ptr->next = table->bins[hash_val];
00636       table->bins[hash_val] = ptr;
00637       table->num_entries++;
00638       ptr = next;
00639     }
00640     }
00641   free (old_bins);
00642 
00643   return 1;
00644 }
00645 
00646 
00647 /** \brief Return a copy of old_table and all its members.  
00648 
00649 <code>(Hash_t *) 0</code> is
00650 returned if there was insufficient memory to do the copy.
00651 */
00652 
00653 Hash_t *
00654 Hash_Copy ( Hash_t *old_table )
00655 {
00656   Hash_t *new_table;
00657   Hash_Entry_t *ptr, *newptr, *next, *newHash;
00658   int i, j, num_bins = old_table->num_bins;
00659 
00660   new_table = ALLOC (Hash_t, 1);
00661   if (new_table == NIL (Hash_t))
00662     {
00663       return NIL (Hash_t);
00664     }
00665 
00666   *new_table = *old_table;
00667   new_table->bins = ALLOC (Hash_Entry_t *, num_bins);
00668   if (new_table->bins == NIL (Hash_Entry_t *))
00669     {
00670       free (new_table);
00671       return NIL (Hash_t);
00672     }
00673   for (i = 0; i < num_bins; i++)
00674     {
00675       new_table->bins[i] = NIL (Hash_Entry_t);
00676       ptr = old_table->bins[i];
00677       while (ptr != NIL (Hash_Entry_t))
00678     {
00679       newHash = ALLOC (Hash_Entry_t, 1);
00680       if (newHash == NIL (Hash_Entry_t))
00681         {
00682           for (j = 0; j <= i; j++)
00683         {
00684           newptr = new_table->bins[j];
00685           while (newptr != NIL (Hash_Entry_t))
00686             {
00687               next = newptr->next;
00688               free (newptr);
00689               newptr = next;
00690             }
00691         }
00692           free (new_table->bins);
00693           free (new_table);
00694           return NIL (Hash_t);
00695         }
00696       *newHash = *ptr;
00697       newHash->next = new_table->bins[i];
00698       new_table->bins[i] = newHash;
00699       ptr = ptr->next;
00700     }
00701     }
00702   return new_table;
00703 }
00704 
00705 /** \brief    Delete the entry with the key pointed to by `key_ptr'.  
00706 
00707 If the entry is found, 1 is returned and `key_ptr' is set to the actual key
00708 and `entry_ptr' is set to the corresponding entry (This allows the
00709 freeing of the associated storage).  If the entry is not found, then 0
00710 is returned and nothing is changed.
00711 */
00712 
00713 int
00714 Hash_Delete (
00715      Hash_t *table,
00716      char **keyp,
00717      char **value
00718 )
00719 {
00720   int hash_val;
00721   char *key = *keyp;
00722   Hash_Entry_t *ptr, **last;
00723 
00724   hash_val = do_hash (key, table);
00725 
00726   FIND_ENTRY (table, hash_val, key, ptr, last);
00727 
00728   if (ptr == NIL (Hash_Entry_t))
00729     {
00730       return 0;
00731     }
00732 
00733   *last = ptr->next;
00734   if (value != NIL (char *))
00735      *value = ptr->record;
00736   *keyp = ptr->key;
00737   free (ptr);
00738   table->num_entries--;
00739   return 1;
00740 }
00741 
00742 
00743 /** \brief Delete the entry with the key pointed to by `key_ptr'.  
00744 
00745 `key_ptr' should be specifically a pointer to an integer.  If the entry is found, 1 is
00746 returned and `key_ptr' is set to the actual key and `entry_ptr' is set to
00747 the corresponding entry (This allows the freeing of the associated storage).
00748 If the entry is not found, then 0 is returned and nothing is changed.
00749 */
00750 
00751 int
00752 Hash_DeleteInt (
00753      Hash_t *table,
00754      int *keyp,
00755      char **value
00756 )
00757 {
00758   int hash_val;
00759   char *key = (char *) *keyp;
00760   Hash_Entry_t *ptr, **last;
00761 
00762   hash_val = do_hash (key, table);
00763 
00764   FIND_ENTRY (table, hash_val, key, ptr, last);
00765 
00766   if (ptr == NIL (Hash_Entry_t))
00767     {
00768       return 0;
00769     }
00770 
00771   *last = ptr->next;
00772   if (value != NIL (char *))
00773      *value = ptr->record;
00774   *keyp = (long) ptr->key;
00775   free (ptr);
00776   table->num_entries--;
00777   return 1;
00778 }
00779 
00780 /** \brief   For each (key, value) record in `table', Hash_ForEach call func
00781      with the arguments <code>(*func)(key, value, arg)</code>
00782 
00783      If func returns ST_CONTINUE, Hash_ForEach continues processing entries.
00784      If func returns ST_STOP, Hash_ForEach stops processing and returns
00785      immediately. If func returns ST_DELETE, then the entry is
00786      deleted from the symbol table and Hash_ForEach continues.  In the
00787      case of ST_DELETE, it is func's responsibility to free the key
00788      and value, if necessary.
00789 
00790      The routine returns 1 if all items in the table were generated and
00791      0 if the generation sequence was aborted using ST_STOP.  The order
00792      in which the records are visited will be seemingly random.
00793 */
00794 
00795 int
00796 Hash_ForEach (
00797      Hash_t *table,
00798      enum st_retval (*func) (),
00799      char *arg
00800 )
00801 {
00802   Hash_Entry_t *ptr, **last;
00803   enum st_retval retval;
00804   int i;
00805 
00806   for (i = 0; i < table->num_bins; i++)
00807     {
00808       last = &table->bins[i];
00809       ptr = *last;
00810       while (ptr != NIL (Hash_Entry_t))
00811     {
00812 #ifdef __cplusplus
00813       retval = (* ( ( st_retval(*)( char *, char *, char * ) ) func ) ) (ptr->key, ptr->record, arg);
00814 #else
00815       retval = func(ptr->key, ptr->record, arg);
00816 #endif
00817       switch (retval)
00818         {
00819         case ST_CONTINUE:
00820           last = &ptr->next;
00821           ptr = *last;
00822           break;
00823         case ST_STOP:
00824           return 0;
00825         case ST_DELETE:
00826           *last = ptr->next;
00827           table->num_entries--; /* cstevens@ic */
00828           free (ptr);
00829           ptr = *last;
00830         }
00831     }
00832     }
00833   return 1;
00834 }
00835 
00836 int
00837 Hash_StrHash_orig ( char *string, int modulus)
00838 {
00839    int val = 0;
00840    int c;
00841 
00842   while ((c = *string++) != '\0')
00843     {
00844       val = val * 997 + c;
00845     }
00846 
00847   return ((val < 0) ? -val : val) % modulus;
00848 }
00849 
00850 
00851 /** \brief Hash function for strings.  */
00852 
00853 int
00854 Hash_StrHash( char *string, int modulus)
00855 {
00856   int val = Hash_StrHash_orig (string, modulus);
00857   return val;
00858 
00859   // this super-duper hash from google actually
00860   // seems to do worse that the 20 year old hash from cadgroup
00861   // int len = strlen( string );
00862   //  int val = util_fast_hash (string, len);
00863   // return ((val < 0) ? -val : val)%modulus;
00864 }
00865 
00866 
00867 /** \brief Hash function for numbers.  */
00868 
00869 int
00870 Hash_NumHash ( char *x, int size)
00871 {
00872   return HASH_NUMHASH ( (int) x, size);
00873 }
00874 
00875 /** \brief Hash function for pointers.  */
00876 
00877 int
00878 Hash_PtrHash ( char *x, int size)
00879 {
00880   return HASH_PTRHASH (x, size);
00881 }
00882 
00883 
00884 /** \brief Compare function for numbers.  */
00885 
00886 int
00887 Hash_NumCmp (int x, int y)
00888 {
00889   return HASH_NUMCMP (x, y);
00890 }
00891 
00892 
00893 /** \brief Compare function for pointers.  */
00894 
00895 int
00896 Hash_PtrCmp (char *x, char *y)
00897 {
00898   return HASH_NUMCMP ( (int) x, (int) y);
00899 }
00900 
00901 
00902 /** \brief    Returns a generator handle which when used with Hash_Gen() will
00903 progressively return each (key, value) record in `table'.
00904 */
00905 
00906 Hash_Generator_t *
00907 Hash_InitGen (Hash_t *table)
00908 {
00909   Hash_Generator_t *gen;
00910 
00911   gen = ALLOC (Hash_Generator_t, 1);
00912   if (gen == NIL (Hash_Generator_t))
00913     {
00914       return NIL (Hash_Generator_t);
00915     }
00916   gen->table = table;
00917   gen->entry = NIL (Hash_Entry_t);
00918   gen->index = 0;
00919   return gen;
00920 }
00921 
00922 
00923 /** \brief Given a generator returned by Hash_InitGen(),  this routine returns
00924 the next (key, value) pair in the generation sequence.  
00925 
00926 The pointer `value_p' can be zero which means no value will be returned.
00927 When there are no more items in the generation sequence,  the routine
00928 returns 0.
00929                                                                                                            
00930 While using a generation sequence,  deleting any (key, value)
00931 pair other than the one just generated may cause a fatal error
00932 when Hash_Gen() is called later in the sequence and is therefore
00933 not recommended.
00934 */
00935 
00936 int
00937 Hash_Gen (
00938      Hash_Generator_t *gen,
00939      char **key_p,
00940      char **value_p
00941 )
00942 {
00943    int i;
00944 
00945   if (gen->entry == NIL (Hash_Entry_t))
00946     {
00947       /* try to find next entry */
00948       for (i = gen->index; i < gen->table->num_bins; i++)
00949     {
00950       if (gen->table->bins[i] != NIL (Hash_Entry_t))
00951         {
00952           gen->index = i + 1;
00953           gen->entry = gen->table->bins[i];
00954           break;
00955         }
00956     }
00957       if (gen->entry == NIL (Hash_Entry_t))
00958     {
00959       return 0;     /* that's all folks ! */
00960     }
00961     }
00962   *key_p = gen->entry->key;
00963   if (value_p != 0)
00964     {
00965       *value_p = gen->entry->record;
00966     }
00967   gen->entry = gen->entry->next;
00968   return 1;
00969 }
00970 
00971 
00972 /** \brief Given a generator returned by Hash_InitGen(),  this routine returns
00973 the next (key, value) pair in the generation sequence.  
00974 
00975 `value' must be a pointer to an integer.  The pointer `value_p' can be zero which
00976 means no value will be returned.  When there are no more items in the
00977 generation sequence,  the routine returns 0.
00978 */
00979 
00980 int
00981 Hash_GenInt (
00982      Hash_Generator_t *gen,
00983      char **key_p,
00984      int *value_p
00985 )
00986 {
00987    int i;
00988 
00989   if (gen->entry == NIL (Hash_Entry_t))
00990     {
00991       /* try to find next entry */
00992       for (i = gen->index; i < gen->table->num_bins; i++)
00993     {
00994       if (gen->table->bins[i] != NIL (Hash_Entry_t))
00995         {
00996           gen->index = i + 1;
00997           gen->entry = gen->table->bins[i];
00998           break;
00999         }
01000     }
01001       if (gen->entry == NIL (Hash_Entry_t))
01002     {
01003       return 0;     /* that's all folks ! */
01004     }
01005     }
01006   *key_p = gen->entry->key;
01007   if (value_p != NIL (int))
01008     {
01009       *value_p = (int) gen->entry->record;
01010     }
01011   gen->entry = gen->entry->next;
01012   return 1;
01013 }
01014 
01015 /** \brief After generating all items in a generation sequence,  this
01016 routine must be called to reclaim the resources associated with `gen'.
01017 */
01018 
01019 void
01020 Hash_FreeGen ( Hash_Generator_t *gen )
01021 {
01022   free (gen);
01023 }
01024 
01025 
01026 /** \brief Simple test of the hash package
01027 
01028 */
01029 
01030 void 
01031 Hash_Test()
01032 {
01033   char *aValue;
01034   char *aString;
01035 
01036   Hash_t *stringTable = Hash_InitTable( (ST_PFI) strcmp, (ST_PFI) Hash_StrHash );
01037   aString = strdup( "adnan" );
01038   aValue = strdup( "aziz" );
01039   Hash_Insert( stringTable, aString, aValue);
01040   aString = strdup( "tanvi" );
01041   aValue = strdup( "chawla" );
01042   Hash_Insert( stringTable, aString, aValue );
01043 
01044   Hash_Generator_t *stGen;
01045   Hash_ForEachItem( stringTable, stGen, & aString, & aValue ) {
01046     assert( !strcmp( aString, "adnan" ) || !strcmp( aString, "tanvi" ) );
01047   }
01048   Hash_ForEachItemNew( stringTable, & aString, & aValue ) {
01049     assert( !strcmp( aString, "adnan" ) || !strcmp( aString, "tanvi" ) );
01050   }
01051 
01052   aString = strdup( "adnan" );
01053   Hash_Delete( stringTable, & aString, & aValue );
01054   assert( aValue != NIL( char ) );
01055   aString = strdup( "adnan" );
01056   aValue = NIL( char );
01057   Hash_Delete( stringTable, & aString, & aValue );
01058   assert( aValue == NIL( char ) );
01059 }