Hash table functions

#include <stdlib.h>
#include "hash.h"
/*
** public domain code by Jerry Coffin, with improvements by HenkJan Wolthuis.
**
** Tested with Visual C 1.0 and Borland C 3.1.
** Compiles without warnings, and seems like it should be pretty
** portable.
*/
/*
** These are used in freeing a table. Perhaps I should code up
** something a little less grungy, but it works, so what the heck.
*/
static void (*function)(void *) = (void (*)(void *))NULL;
static hash_table *the_table = NULL;

/* Initialize the hash_table to the size asked for. Allocates space
** for the correct number of pointers and sets them to NULL. If it
** can't allocate sufficient memory, signals error by setting the size
** of the table to 0.
*/
hash_table *construct_table(hash_table *table, size_t size)
{
   size_t i;
   bucket **temp;
   table -> size = size;
   table -> table = (bucket * *)malloc(sizeof(bucket *) * size);
   temp = table -> table;
   if ( temp == NULL )
   {
      table -> size = 0;
      return table;
   }
   for (i=0;i<size;i++)
      temp[i] = NULL;
   return table;
}

/*
** Hashes a string to produce an unsigned short, which should be
** sufficient for most purposes.
*/
static unsigned hash(char *string)
{
   unsigned ret_val = 0;
   int i;
   while (*string)
   {
      i = *( int *)string;
      ret_val ^= i;
      ret_val <<= 1;
      string ++;
   }
   return ret_val;
}
/*
** Insert 'key' into hash table.
** Returns pointer to old data associated with the key, if any, or
** NULL if the key wasn't in the table previously.
*/
void *insert(char *key, void *data, hash_table *table)
{
   unsigned val = hash(key) % table->size;
   bucket *ptr;
   /*
   ** NULL means this bucket hasn't been used yet. We'll simply
   ** allocate space for our new bucket and put our data there, with
   ** the table pointing at it.
   */
   if (NULL == (table->table)[val])
   {
      (table->table)[val] = (bucket *)malloc(sizeof(bucket));
      if (NULL==(table->table)[val])
         return NULL;
      (table->table)[val] -> key = strdup(key);
      (table->table)[val] -> next = NULL;
      (table->table)[val] -> data = data;
      return (table->table)[val] -> data;
   }
   /*
   ** This spot in the table is already in use. See if the current string
   ** has already been inserted, and if so, increment its count.
   */
   for (ptr = (table->table)[val];NULL != ptr; ptr = ptr -> next)
      if (0 == strcmp(key, ptr->key))
      {
         void *old_data;
         old_data = ptr->data;
         ptr -> data = data;
         return old_data;
      }
   /*
   ** This key must not be in the table yet. We'll add it to the head of
   ** the list at this spot in the hash table. Speed would be
   ** slightly improved if the list was kept sorted instead. In this case,
   ** this code would be moved into the loop above, and the insertion would
   ** take place as soon as it was determined that the present key in the
   ** list was larger than this one.
   */
   ptr = (bucket *)malloc(sizeof(bucket));
   if (NULL==ptr)
      return 0;
   ptr -> key = strdup(key);
   ptr -> data = data;
   ptr -> next = (table->table)[val];
   (table->table)[val] = ptr;
   return data;
}

/*
** Look up a key and return the associated data. Returns NULL if
** the key is not in the table.
*/
void *lookup(char *key, hash_table *table)
{
   unsigned val = hash(key) % table->size;
   bucket *ptr;
   if (NULL == (table->table)[val])
      return NULL;
   for ( ptr = (table->table)[val];NULL != ptr; ptr = ptr->next )
   {
      if (0 == strcmp(key, ptr -> key ) )
         return ptr->data;
   }
   return NULL;
}
/*
** Delete a key from the hash table and return associated
** data, or NULL if not present.
*/
void *del(char *key, hash_table *table)
{
   unsigned val = hash(key) % table->size;
   void *data;
   bucket *ptr, *last = NULL;
   if (NULL == (table->table)[val])
      return NULL;
   /*
   ** Traverse the list, keeping track of the previous node in the list.
   ** When we find the node to delete, we set the previous node's next
   ** pointer to point to the node after ourself instead. We then delete
   ** the key from the present node, and return a pointer to the data it
   ** contains.
   */
   for (last = NULL, ptr = (table->table)[val];
      NULL != ptr;
      last = ptr, ptr = ptr->next)
   {
      if (0 == strcmp(key, ptr -> key))
      {
         if (last != NULL )
         {
            data = ptr -> data;
            last -> next = ptr -> next;
            free(ptr->key);
            free(ptr);
            return data;
         }
         /*
         ** If 'last' still equals NULL, it means that we need to
         ** delete the first node in the list. This simply consists
         ** of putting our own 'next' pointer in the array holding
         ** the head of the list. We then dispose of the current
         ** node as above.
         */
         else
         {
            data = ptr->data;
            (table->table)[val] = ptr->next;
            free(ptr->key);
            free(ptr);
            return data;
         }
      }
   }
   /*
   ** If we get here, it means we didn't find the item in the table.
   ** Signal this by returning NULL.
   */
   return NULL;
}
/*
** free_table iterates the table, calling this repeatedly to free
** each individual node. This, in turn, calls one or two other
** functions - one to free the storage used for the key, the other
** passes a pointer to the data back to a function defined by the user,
** process the data as needed.
*/
static void free_node(char *key, void *data)
{
   (void) data;
   if (function)
      function(del(key,the_table));
   else del(key,the_table);
}
/*
** Frees a complete table by iterating over it and freeing each node.
** the second parameter is the address of a function it will call with a
** pointer to the data associated with each node. This function is
** responsible for freeing the data, or doing whatever is needed with
** it.
*/
void free_table(hash_table *table, void (*func)(void *))
{
   function = func;
   the_table = table;
   enumerate( table, free_node);
   free(table->table);
   table->table = NULL;
   table->size = 0;
   the_table = NULL;
   function = (void (*)(void *))NULL;
}
/*
** Simply invokes the function given as the second parameter for each
** node in the table, passing it the key and the associated data.
*/
void enumerate( hash_table *table, void (*func)(char *, void *))
{
   unsigned i;
   bucket *temp;
   for (i=0;i<table->size; i++)
   {
      if ((table->table)[i] != NULL)
      {
         for (temp = (table->table)[i];
            NULL != temp;
            temp = temp -> next)
         {
            func(temp -> key, temp->data);
         }
      }
   }
}

#ifdef TEST
#include <stdio.h>
void printer(char *string, void *data)
{
   printf("%s: %s\n", string, (char *)data);
}
int main(void)
{
   hash_table table;
   char *strings[] = {
      "The first string",
      "The second string",
      "The third string",
      "The fourth string",
      "A much longer string than the rest in this example.",
      "The last string",
      NULL
      };
   char *junk[] = {
      "The first data",
      "The second data",
      "The third data",
      "The fourth data",
      "The fifth datum",
      "The sixth piece of data"
      };
   int i;
   void *j;
   construct_table(&table,200);
   for (i = 0; NULL != strings[i]; i++ )
      insert(strings[i], junk[i], &table);
   for (i=0;NULL != strings[i];i++)
   {
      printf("\n");
      enumerate(&table, printer);
      del(strings[i],&table);
   }
   for (i=0;NULL != strings[i];i++)
   {
      j = lookup(strings[i], &table);
      if (NULL == j)
         printf("\n'%s' is not in table",strings[i]);
      else printf("\nERROR: %s was deleted but is still in table.",
         strings[i]);
   }
   free_table(&table, NULL);
   return 0;
}
#endif /* TEST */