st.c

Go to the documentation of this file.

/** \file st.c

\brief Hash code

*/

#include <stdio.h>
#include "util.h"
#include "st.h"

/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/


/**AutomaticEnd***************************************************************/


static inline int
HASH_NUMCMP (int x, int y)
{
  return (x != y);
}

static inline int
HASH_NUMHASH (int x, int size)
{
  return ABS ((long) x) % (size);
}

static inline int
HASH_PTRHASH (void *x, int size)
{
  return ((int) ((unsigned long) (x) >> 2) % (size));
}

// #define HASH_EQUAL(func, x, y) \
//    ((((func) == Hash_NumCmp) || ((func) == Hash_PtrCmp)) ?\
//      (HASH_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))

static inline int HASH_EQUAL( int (*func)(), void *x, void *y ) {
  return ((((func) == (int(*)()) Hash_NumCmp) || ((func) == (int(*)()) Hash_PtrCmp)) ?
    (HASH_NUMCMP(((int) x),((int) y)) == 0) : 
        ( ( (* ( int(*)(void *,void *) ) func  ) ( x, y ) ) == 0) );
}

// #define do_hash(key, table)\
//     ((table->hash == Hash_PtrHash) ? HASH_PTRHASH((key),(table)->num_bins) :\
//      (table->hash == Hash_NumHash) ? HASH_NUMHASH((key), (table)->num_bins) :\
//      (*table->hash)((key), (table)->num_bins))

static inline int do_hash( void *key, Hash_t *table) {
    if ((table->hash == (ST_PFI) Hash_PtrHash) ) {
      return HASH_PTRHASH( key,(table)->num_bins);
    }
    if ((table->hash == (ST_PFI) Hash_NumHash) ) {
      return HASH_NUMHASH( (int) key,(table)->num_bins);
    }
    return ( ( * ( ( int(*)( void *, int ) ) (table->hash) ) )( key, (table)->num_bins ) );
}

static int rehash ( Hash_t *table );

Hash_t *st_init_table_with_params( ST_PFI a, ST_PFI b, int c, int d, double e, int f) { 
  return Hash_InitTableWithParams (a, b, c, d, e, f ); 
}

Hash_t *st_init_table (ST_PFI a, ST_PFI b) {
  return Hash_InitTable( a, b );
}

void st_free_table (Hash_t * a) {
  return Hash_FreeTable( a );
}

int st_lookup (Hash_t * a, char * b, char ** c) {
  return Hash_Lookup( a, b, c );
}

int st_lookup_int (Hash_t * a, char * b, int * c) {
  return Hash_LookupInt( a, b,c );
}

int st_insert (Hash_t * a, char * b, char * c) {
  return Hash_Insert( a, b, c );
}

int st_add_direct (Hash_t * a, char * b, char * c) {
  return Hash_AddDirect( a, b, c );
}

int st_find_or_add (Hash_t * a, char * b, char *** c){
  return Hash_FindOrAdd( a, b, c );
}

int st_find (Hash_t * a, char * b, char *** c) {
  return Hash_Find( a, b, c );
}

Hash_t *st_copy (Hash_t * a) {
  return Hash_Copy( a );
}

int st_delete (Hash_t * a, char ** b, char ** c) {
  return Hash_Delete( a, b, c );
}

int st_delete_int (Hash_t * a, int * b, char ** c) {
  return Hash_DeleteInt( a, b, c );
}

int st_foreach (Hash_t * a, ST_PFSR b, char * c) {
  return Hash_ForEach( a, b, c );
}

int st_strhash (char * a, int b) {
  return Hash_StrHash( a, b );
}

int st_numhash (char * a, int b) {
  return Hash_NumHash( a, b );
}

int st_ptrhash (char * a, int b) {
  return Hash_PtrHash( a, b );
}

int st_numcmp  (int a, int b) {
  return Hash_NumCmp( a, b );
}

int st_ptrcmp (char * a, char * b) {
  return Hash_PtrCmp( a, b );
}

int st_gen (Hash_Generator_t * a, char ** b, char ** c) {
  return Hash_Gen( a, b, c );
}

int st_gen_int (Hash_Generator_t * a, char ** b, int * c) {
  return Hash_GenInt( a, b, c );
}

Hash_Generator_t *st_init_gen (Hash_t * a) {
  return Hash_InitGen( a );
}

void st_free_gen (Hash_Generator_t * a) {
  return Hash_FreeGen( a );
}

/** \brief The full blown table initializer.  

<code>compare</code> and <code>hash</code> are the same
    as in <code>Hash_InitTable</code>. <code>density</code> is the largest the average number of
    entries per hash bin there should be before the table is grown.
    <code>grow_factor</code> is the factor the table is grown by when it becomes too
    full. <code>size</code> is the initial number of bins to be allocated for the hash
    table.  If <code>reorder_flag</code> is non-zero, then everytime an entry is found,
    it is moved to the top of the chain.
                                                                                                           
   <code>Hash_InitTable(compare, hash)</code> is equivelent to
<pre>
   Hash_InitTableWithParams(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE,
                                     ST_DEFAULT_MAX_DENSITY,
                                     ST_DEFAULT_GROW_FACTOR,
                                     ST_DEFAULT_REORDER_FLAG);
</pre>
*/

Hash_t *
Hash_InitTableWithParams (int (*compare) (), int (*hash) (), int size,
               int density, double grow_factor, int reorder_flag)
{
  int i;
  Hash_t *newHash;

  newHash = ALLOC (Hash_t, 1);
  if (newHash == NIL (Hash_t))
    {
      return NIL (Hash_t);
    }
  newHash->compare = compare;
  newHash->hash = hash;
  newHash->num_entries = 0;
  newHash->max_density = density;
  newHash->grow_factor = grow_factor;
  newHash->reorder_flag = reorder_flag;
  if (size <= 0)
    {
      size = 1;
    }
  newHash->num_bins = size;
  newHash->bins = ALLOC (Hash_Entry_t *, size);
  if (newHash->bins == NIL (Hash_Entry_t *))
    {
      free (newHash);
      return NIL (Hash_t);
    }
  for (i = 0; i < size; i++)
    {
      newHash->bins[i] = 0;
    }
  return newHash;
}


/** \brief  Create and initialize a table with the comparison function compare_fn and
    hash function hash_fn. 

compare_fn is

<pre>                                                                                                           
        int compare_fn(char *key1, char *key2)
</pre> returns <,=,> 0 depending on whether <code>key1 <,=,> key2</code> by some measure

and  hash_fn is

<pre>                                                                                                           
        int hash_fn(char *key, int modulus)
</pre>
returns a integer between 0 and modulus-1
such that if <code>compare_fn(key1,key2) == 0</code> then
<code>hash_fn(key1) == hash_fn(key2)</code>
                                                                                                           
     There are five predefined hash and comparison functions in st.
<ul>
    <li> For keys as numbers:
         <pre>Hash_NumHash(key, modulus) { return (unsigned int) key % modulus; }</pre>
         <pre>Hash_NumCmp(x,y) { return (int) x - (int) y; }</pre>

     <li>For keys as pointers:
        <pre>Hash_PreHash(key, modulus) { return ((unsigned int) key/4) % modulus }</pre>
        <pre>Hash_PtrCmp(x,y) { return (int) x - (int) y; }</pre>

     <li> For keys as strings:
         <pre>Hash_StrHash(x,y)</pre> - a reasonable hashing function for strings
         <pre>strcmp(x,y)</pre> - the standard library function
   
</ul>                                                                                                        
     It is recommended to use these particular functions if they fit your
     needs, since st will recognize certain of them and run more quickly
     because of it.
*/

Hash_t *
Hash_InitTable ( int (*compare) (), int (*hash) () )
{
  return Hash_InitTableWithParams (compare, hash, HASH_DEFAULT_INIT_TABLE_SIZE,
                    HASH_DEFAULT_MAX_DENSITY,
                    HASH_DEFAULT_GROW_FACTOR,
                    HASH_DEFAULT_REORDER_FLAG);
}


/** \brief Free any internal storage associated with table.  

It is the user's
responsibility to free any storage associated with the pointers he
placed in the table (by perhaps using Hash_ForEach).
*/

void
Hash_FreeTable (
     Hash_t *table )
{
  Hash_Entry_t *ptr, *next;
  int i;

  for (i = 0; i < table->num_bins; i++)
    {
      ptr = table->bins[i];
      while (ptr != NIL (Hash_Entry_t))
    {
      next = ptr->next;
      free (ptr);
      ptr = next;
    }
    }
  free (table->bins);
  free (table);
}

#define PTR_NOT_EQUAL(table, ptr, user_key)\
(ptr != NIL(Hash_Entry_t) && !HASH_EQUAL(table->compare, user_key, (ptr)->key))

#define FIND_ENTRY(table, hash_val, key, ptr, last) \
    (last) = &(table)->bins[hash_val];\
    (ptr) = *(last);\
    while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
    (last) = &(ptr)->next; (ptr) = *(last);\
    }\
    if ((ptr) != NIL(Hash_Entry_t) && (table)->reorder_flag) {\
    *(last) = (ptr)->next;\
    (ptr)->next = (table)->bins[hash_val];\
    (table)->bins[hash_val] = (ptr);\
    }


/** \brief Lookup up `key' in `table'. 

If an entry is found, 1 is returned
and if `value_ptr' is not nil, the variable it points to is set to
associated value.  If an entry is not found, 0 is return and
value_ptr is unchanged.
*/

int
Hash_Lookup(
     Hash_t *table,
     char *key,
     char **value
)
{
  int hash_val;
  Hash_Entry_t *ptr, **last;

  hash_val = do_hash (key, table);

  FIND_ENTRY (table, hash_val, key, ptr, last);

  if (ptr == NIL (Hash_Entry_t))
    {
      return 0;
    }
  else
    {
      if (value != NIL (char *))
    {
      *value = ptr->record;
    }
      return 1;
    }
}


/** \brief Lookup up int `key' in `table'. 

If an entry is found, 1 is returned
and if `int_ptr' is not nil, the variable it points to is set to
associated integer value.  If an entry is not found, 0 is return and
int_ptr is unchanged.
*/

int
Hash_LookupInt (
     Hash_t *table,
     char *key,
     int *value
)
{
  int hash_val;
   Hash_Entry_t *ptr, **last;

  hash_val = do_hash (key, table);

  FIND_ENTRY (table, hash_val, key, ptr, last);

  if (ptr == NIL (Hash_Entry_t))
    {
      return 0;
    }
  else
    {
      if (value != NIL (int))
    {
      *value = (long) ptr->record;
    }
      return 1;
    }
}

/* This macro does not check if memory allocation fails. Use at your own risk */
#define ADD_DIRECT(table, key, value, hash_val, newHash)\
{\
    if (table->num_entries/table->num_bins >= table->max_density) {\
    rehash(table);\
    hash_val = do_hash(key,table);\
    }\
    \
    newHash = ALLOC(Hash_Entry_t, 1);\
    \
    newHash->key = key;\
    newHash->record = value;\
    newHash->next = table->bins[hash_val];\
    table->bins[hash_val] = newHash;\
    table->num_entries++;\
}

/** \brief  Insert value in table under the key 'key'.  

Returns 1 if there was
an entry already under the key, 0 otherewise.  
In either case the new value is added.
*/

int
Hash_Insert (
     Hash_t *table,
     char *key,
     char *value
)
{
  int hash_val;
  Hash_Entry_t *newHash;
  Hash_Entry_t *ptr, **last;

  hash_val = do_hash (key, table);

  FIND_ENTRY (table, hash_val, key, ptr, last);

  if (ptr == NIL (Hash_Entry_t))
    {
      if (table->num_entries / table->num_bins >= table->max_density)
    {
      if (rehash (table) == HASH_OUT_OF_MEM)
        {
          return HASH_OUT_OF_MEM;
        }
      hash_val = do_hash (key, table);
    }
      newHash = ALLOC (Hash_Entry_t, 1);
      if (newHash == NIL (Hash_Entry_t))
    {
      return HASH_OUT_OF_MEM;
    }
      newHash->key = key;
      newHash->record = value;
      newHash->next = table->bins[hash_val];
      table->bins[hash_val] = newHash;
      table->num_entries++;
      return 0;
    }
  else
    {
      ptr->record = value;
      return 1;
    }
}


/** \brief Place 'value' in 'table' under the key 'key'.  This is done
    without checking if 'key' is in 'table' already.  

This should only be used if you are sure there is not already an entry for
'key', since it is undefined which entry you would later get from
Hash_Lookup or Hash_FindOrAdd.
*/

int
Hash_AddDirect (
     Hash_t *table,
     char *key,
     char *value
)
{
  int hash_val;
  Hash_Entry_t *newHash;

  hash_val = do_hash (key, table);
  if (table->num_entries / table->num_bins >= table->max_density)
    {
      if (rehash (table) == HASH_OUT_OF_MEM)
    {
      return HASH_OUT_OF_MEM;
    }
    }
  hash_val = do_hash (key, table);
  newHash = ALLOC (Hash_Entry_t, 1);
  if (newHash == NIL (Hash_Entry_t))
    {
      return HASH_OUT_OF_MEM;
    }
  newHash->key = key;
  newHash->record = value;
  newHash->next = table->bins[hash_val];
  table->bins[hash_val] = newHash;
  table->num_entries++;
  return 1;
}

/** \brief Lookup `key' in `table'.  If not found, create an entry.In either case
   set slot to point to the field in the entry where the value is stored.
   The value associated with `key' may then be changed by accessing
   directly through slot.  Returns 1 if an entry already existed, 0
   otherwise. 

As an example:
<pre>                                                                                                      
      char **slot;
      char *key;
      char *value = (char *) item_ptr // ptr to a malloc'd structure 
                                                                                                           
      if (Hash_FindOrAdd(table, key, &slot)) {
         FREE(*slot); // free the old value of the record 
      }
      *slot = value;  // attach the new value to the record 
</pre>
                                                                                                           
This replaces the equivelent code:
<pre>                                                                                                      
      if (Hash_Lookup(table, key, &ovalue)) {
         FREE(ovalue);
      }
      Hash_Insert(table, key, value);
</pre>

*/

int
Hash_FindOrAdd(
     Hash_t *table,
     char *key,
     char ***slot
)
{
  int hash_val;
  Hash_Entry_t *newHash, *ptr, **last;

  hash_val = do_hash (key, table);

  FIND_ENTRY (table, hash_val, key, ptr, last);

  if (ptr == NIL (Hash_Entry_t))
    {
      if (table->num_entries / table->num_bins >= table->max_density)
    {
      if (rehash (table) == HASH_OUT_OF_MEM)
        {
          return HASH_OUT_OF_MEM;
        }
      hash_val = do_hash (key, table);
    }
      newHash = ALLOC (Hash_Entry_t, 1);
      if (newHash == NIL (Hash_Entry_t))
    {
      return HASH_OUT_OF_MEM;
    }
      newHash->key = key;
      newHash->record = (char *) 0;
      newHash->next = table->bins[hash_val];
      table->bins[hash_val] = newHash;
      table->num_entries++;
      if (slot != NIL (char **))
     *slot = &newHash->record;
      return 0;
    }
  else
    {
      if (slot != NIL (char **))
     *slot = &ptr->record;
      return 1;
    }
}


/** \brief Like <code>Hash_FindOrAdd</code>, but does not create an entry if one is not found.
*/

int
Hash_Find (
     Hash_t *table,
     char *key,
     char ***slot
)
{
  int hash_val;
  Hash_Entry_t *ptr, **last;

  hash_val = do_hash (key, table);

  FIND_ENTRY (table, hash_val, key, ptr, last);

  if (ptr == NIL (Hash_Entry_t))
    {
      return 0;
    }
  else
    {
      if (slot != NIL (char **))
    {
      *slot = &ptr->record;
    }
      return 1;
    }
}


/** \brief Rehash a table

*/

static int
rehash ( Hash_t *table )
{
   Hash_Entry_t *ptr, *next, **old_bins;
  int i, old_num_bins, hash_val, old_num_entries;

  /* save old values */
  old_bins = table->bins;
  old_num_bins = table->num_bins;
  old_num_entries = table->num_entries;

  /* rehash */
  table->num_bins = table->grow_factor * old_num_bins;
  if (table->num_bins % 2 == 0)
    {
      table->num_bins += 1;
    }
  table->num_entries = 0;
  table->bins = ALLOC (Hash_Entry_t *, table->num_bins);
  if (table->bins == NIL (Hash_Entry_t *))
    {
      table->bins = old_bins;
      table->num_bins = old_num_bins;
      table->num_entries = old_num_entries;
      return HASH_OUT_OF_MEM;
    }
  /* initialize */
  for (i = 0; i < table->num_bins; i++)
    {
      table->bins[i] = 0;
    }

  /* copy data over */
  for (i = 0; i < old_num_bins; i++)
    {
      ptr = old_bins[i];
      while (ptr != NIL (Hash_Entry_t))
    {
      next = ptr->next;
      hash_val = do_hash (ptr->key, table);
      ptr->next = table->bins[hash_val];
      table->bins[hash_val] = ptr;
      table->num_entries++;
      ptr = next;
    }
    }
  free (old_bins);

  return 1;
}


/** \brief Return a copy of old_table and all its members.  

<code>(Hash_t *) 0</code> is
returned if there was insufficient memory to do the copy.
*/

Hash_t *
Hash_Copy ( Hash_t *old_table )
{
  Hash_t *new_table;
  Hash_Entry_t *ptr, *newptr, *next, *newHash;
  int i, j, num_bins = old_table->num_bins;

  new_table = ALLOC (Hash_t, 1);
  if (new_table == NIL (Hash_t))
    {
      return NIL (Hash_t);
    }

  *new_table = *old_table;
  new_table->bins = ALLOC (Hash_Entry_t *, num_bins);
  if (new_table->bins == NIL (Hash_Entry_t *))
    {
      free (new_table);
      return NIL (Hash_t);
    }
  for (i = 0; i < num_bins; i++)
    {
      new_table->bins[i] = NIL (Hash_Entry_t);
      ptr = old_table->bins[i];
      while (ptr != NIL (Hash_Entry_t))
    {
      newHash = ALLOC (Hash_Entry_t, 1);
      if (newHash == NIL (Hash_Entry_t))
        {
          for (j = 0; j <= i; j++)
        {
          newptr = new_table->bins[j];
          while (newptr != NIL (Hash_Entry_t))
            {
              next = newptr->next;
              free (newptr);
              newptr = next;
            }
        }
          free (new_table->bins);
          free (new_table);
          return NIL (Hash_t);
        }
      *newHash = *ptr;
      newHash->next = new_table->bins[i];
      new_table->bins[i] = newHash;
      ptr = ptr->next;
    }
    }
  return new_table;
}

/** \brief    Delete the entry with the key pointed to by `key_ptr'.  

If the entry is found, 1 is returned and `key_ptr' is set to the actual key
and `entry_ptr' is set to the corresponding entry (This allows the
freeing of the associated storage).  If the entry is not found, then 0
is returned and nothing is changed.
*/

int
Hash_Delete (
     Hash_t *table,
     char **keyp,
     char **value
)
{
  int hash_val;
  char *key = *keyp;
  Hash_Entry_t *ptr, **last;

  hash_val = do_hash (key, table);

  FIND_ENTRY (table, hash_val, key, ptr, last);

  if (ptr == NIL (Hash_Entry_t))
    {
      return 0;
    }

  *last = ptr->next;
  if (value != NIL (char *))
     *value = ptr->record;
  *keyp = ptr->key;
  free (ptr);
  table->num_entries--;
  return 1;
}


/** \brief Delete the entry with the key pointed to by `key_ptr'.  

`key_ptr' should be specifically a pointer to an integer.  If the entry is found, 1 is
returned and `key_ptr' is set to the actual key and `entry_ptr' is set to
the corresponding entry (This allows the freeing of the associated storage).
If the entry is not found, then 0 is returned and nothing is changed.
*/

int
Hash_DeleteInt (
     Hash_t *table,
     int *keyp,
     char **value
)
{
  int hash_val;
  char *key = (char *) *keyp;
  Hash_Entry_t *ptr, **last;

  hash_val = do_hash (key, table);

  FIND_ENTRY (table, hash_val, key, ptr, last);

  if (ptr == NIL (Hash_Entry_t))
    {
      return 0;
    }

  *last = ptr->next;
  if (value != NIL (char *))
     *value = ptr->record;
  *keyp = (long) ptr->key;
  free (ptr);
  table->num_entries--;
  return 1;
}

/** \brief   For each (key, value) record in `table', Hash_ForEach call func
     with the arguments <code>(*func)(key, value, arg)</code>

     If func returns ST_CONTINUE, Hash_ForEach continues processing entries.
     If func returns ST_STOP, Hash_ForEach stops processing and returns
     immediately. If func returns ST_DELETE, then the entry is
     deleted from the symbol table and Hash_ForEach continues.  In the
     case of ST_DELETE, it is func's responsibility to free the key
     and value, if necessary.

     The routine returns 1 if all items in the table were generated and
     0 if the generation sequence was aborted using ST_STOP.  The order
     in which the records are visited will be seemingly random.
*/

int
Hash_ForEach (
     Hash_t *table,
     enum st_retval (*func) (),
     char *arg
)
{
  Hash_Entry_t *ptr, **last;
  enum st_retval retval;
  int i;

  for (i = 0; i < table->num_bins; i++)
    {
      last = &table->bins[i];
      ptr = *last;
      while (ptr != NIL (Hash_Entry_t))
    {
#ifdef __cplusplus
      retval = (* ( ( st_retval(*)( char *, char *, char * ) ) func ) ) (ptr->key, ptr->record, arg);
#else
      retval = func(ptr->key, ptr->record, arg);
#endif
      switch (retval)
        {
        case ST_CONTINUE:
          last = &ptr->next;
          ptr = *last;
          break;
        case ST_STOP:
          return 0;
        case ST_DELETE:
          *last = ptr->next;
          table->num_entries--; /* cstevens@ic */
          free (ptr);
          ptr = *last;
        }
    }
    }
  return 1;
}

int
Hash_StrHash_orig ( char *string, int modulus)
{
   int val = 0;
   int c;

  while ((c = *string++) != '\0')
    {
      val = val * 997 + c;
    }

  return ((val < 0) ? -val : val) % modulus;
}


/** \brief Hash function for strings.  */

int
Hash_StrHash( char *string, int modulus)
{
  int val = Hash_StrHash_orig (string, modulus);
  return val;

  // this super-duper hash from google actually
  // seems to do worse that the 20 year old hash from cadgroup
  // int len = strlen( string );
  //  int val = util_fast_hash (string, len);
  // return ((val < 0) ? -val : val)%modulus;
}


/** \brief Hash function for numbers.  */

int
Hash_NumHash ( char *x, int size)
{
  return HASH_NUMHASH ( (int) x, size);
}

/** \brief Hash function for pointers.  */

int
Hash_PtrHash ( char *x, int size)
{
  return HASH_PTRHASH (x, size);
}


/** \brief Compare function for numbers.  */

int
Hash_NumCmp (int x, int y)
{
  return HASH_NUMCMP (x, y);
}


/** \brief Compare function for pointers.  */

int
Hash_PtrCmp (char *x, char *y)
{
  return HASH_NUMCMP ( (int) x, (int) y);
}


/** \brief    Returns a generator handle which when used with Hash_Gen() will
progressively return each (key, value) record in `table'.
*/

Hash_Generator_t *
Hash_InitGen (Hash_t *table)
{
  Hash_Generator_t *gen;

  gen = ALLOC (Hash_Generator_t, 1);
  if (gen == NIL (Hash_Generator_t))
    {
      return NIL (Hash_Generator_t);
    }
  gen->table = table;
  gen->entry = NIL (Hash_Entry_t);
  gen->index = 0;
  return gen;
}


/** \brief Given a generator returned by Hash_InitGen(),  this routine returns
the next (key, value) pair in the generation sequence.  

The pointer `value_p' can be zero which means no value will be returned.
When there are no more items in the generation sequence,  the routine
returns 0.
                                                                                                           
While using a generation sequence,  deleting any (key, value)
pair other than the one just generated may cause a fatal error
when Hash_Gen() is called later in the sequence and is therefore
not recommended.
*/

int
Hash_Gen (
     Hash_Generator_t *gen,
     char **key_p,
     char **value_p
)
{
   int i;

  if (gen->entry == NIL (Hash_Entry_t))
    {
      /* try to find next entry */
      for (i = gen->index; i < gen->table->num_bins; i++)
    {
      if (gen->table->bins[i] != NIL (Hash_Entry_t))
        {
          gen->index = i + 1;
          gen->entry = gen->table->bins[i];
          break;
        }
    }
      if (gen->entry == NIL (Hash_Entry_t))
    {
      return 0;     /* that's all folks ! */
    }
    }
  *key_p = gen->entry->key;
  if (value_p != 0)
    {
      *value_p = gen->entry->record;
    }
  gen->entry = gen->entry->next;
  return 1;
}


/** \brief Given a generator returned by Hash_InitGen(),  this routine returns
the next (key, value) pair in the generation sequence.  

`value' must be a pointer to an integer.  The pointer `value_p' can be zero which
means no value will be returned.  When there are no more items in the
generation sequence,  the routine returns 0.
*/

int
Hash_GenInt (
     Hash_Generator_t *gen,
     char **key_p,
     int *value_p
)
{
   int i;

  if (gen->entry == NIL (Hash_Entry_t))
    {
      /* try to find next entry */
      for (i = gen->index; i < gen->table->num_bins; i++)
    {
      if (gen->table->bins[i] != NIL (Hash_Entry_t))
        {
          gen->index = i + 1;
          gen->entry = gen->table->bins[i];
          break;
        }
    }
      if (gen->entry == NIL (Hash_Entry_t))
    {
      return 0;     /* that's all folks ! */
    }
    }
  *key_p = gen->entry->key;
  if (value_p != NIL (int))
    {
      *value_p = (int) gen->entry->record;
    }
  gen->entry = gen->entry->next;
  return 1;
}

/** \brief After generating all items in a generation sequence,  this
routine must be called to reclaim the resources associated with `gen'.
*/

void
Hash_FreeGen ( Hash_Generator_t *gen )
{
  free (gen);
}


/** \brief Simple test of the hash package

*/

void 
Hash_Test()
{
  char *aValue;
  char *aString;

  Hash_t *stringTable = Hash_InitTable( (ST_PFI) strcmp, (ST_PFI) Hash_StrHash );
  aString = strdup( "adnan" );
  aValue = strdup( "aziz" );
  Hash_Insert( stringTable, aString, aValue);
  aString = strdup( "tanvi" );
  aValue = strdup( "chawla" );
  Hash_Insert( stringTable, aString, aValue );

  Hash_Generator_t *stGen;
  Hash_ForEachItem( stringTable, stGen, & aString, & aValue ) {
    assert( !strcmp( aString, "adnan" ) || !strcmp( aString, "tanvi" ) );
  }
  Hash_ForEachItemNew( stringTable, & aString, & aValue ) {
    assert( !strcmp( aString, "adnan" ) || !strcmp( aString, "tanvi" ) );
  }

  aString = strdup( "adnan" );
  Hash_Delete( stringTable, & aString, & aValue );
  assert( aValue != NIL( char ) );
  aString = strdup( "adnan" );
  aValue = NIL( char );
  Hash_Delete( stringTable, & aString, & aValue );
  assert( aValue == NIL( char ) );
}