hash.c

来自「国外网站上的一些精典的C程序」· C语言 代码 · 共 525 行 · 第 1/2 页

#include <string.h>
#include <stdlib.h>
/* #define NDEBUG */
#include <assert.h>

#include "hash.h"


/*
** public domain code by Jerry Coffin.
**
** Tested with Visual C 1.0 and Borland C 3.1.
** Compiles without warnings, and seems like it should be pretty
** portable.
*/

/* HW: HenkJan Wolthuis, 1997, public domain

      changed functionnames, all public functions now have a 'hash_' prefix
      minor editing, marked 'm all(?) with a description
      removed a bug in hash_del and one in hash_enumerate
      added some assertions
      added a 'count' member to hold the number of elements
      added hash_sorted_enum, sometimes useful
      changed the testmain
*/

/*
** RBS: Bob Stout, 2003, public domain
**
**  1. Fixed some problems in hash() static function.
**  2. Use unsigned shorts for hash values. This was implicit in the original
**     which was written for PC's using early Microsoft and Borland compilers.
*/

/* HW: #define to allow duplicate keys, they're added before the existing
      key so hash_lookup finds the last one inserted first (LIFO)
      when not defined, hash_insert swaps the datapointers, returning a
      pointer to the old data
*/
/* #define DUPLICATE_KEYS */

/*
** 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 *) = 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.
*/
/*HW: changed, now returns NULL on malloc-failure */
hash_table *hash_construct_table( hash_table *table, size_t size )
{
      size_t i;
      bucket **temp;

      table->size  = size;
      table->count = 0;
      table->table = (bucket **)malloc(sizeof(bucket *) * size);
      temp = table->table;

      if( NULL == temp )
      {
            table->size = 0;
            return NULL;      /*HW: was '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.
** RBS: fixed per user feedback from Steve Greenland
*/

static unsigned short hash(char *string)
{
      unsigned short ret_val = 0;
      int i;

      while (*string)
      {
            /*
            ** RBS: Added conditional to account for strings in which the
            ** length is less than an integral multiple of sizeof(int).
            **
            ** Note: This fixes the problem of hasing trailing garbage, but
            ** doesn't fix the problem with some CPU's which can't align on
            ** byte boundries. Any decent C compiler *should* fix this, but
            ** it still might extract a performance hit. Also unaddressed is
            ** what happens when using a CPU which addresses data only on
            ** 4-byte boundries when it tries to work with a pointer to a
            ** 2-byte unsigned short.
            */

            if (strlen(string) >= sizeof(unsigned short))
                  i = *(unsigned short *)string;
            else  i = (unsigned short)(*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.
*/
/* HW: returns NULL if malloc failed */
void *hash_insert( char *key, void *data, hash_table *table )
{
      unsigned short val = hash(key) % table->size;
      bucket *ptr;

      assert( NULL != key );

      /*
      ** 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;

            if( NULL ==  ((table->table)[val]->key = malloc(strlen(key)+1)) )
            {
                  free( (table->table)[val] );
                  (table->table)[val] = NULL;
                  return NULL;
            }
            strcpy( (table->table)[val]->key, key);
            (table->table)[val] -> next = NULL;
            (table->table)[val] -> data = data;
            table->count++; /* HW */
            return (table->table)[val] -> data;
      }

/* HW: added a #define so the hashtable can accept duplicate keys */
#ifndef DUPLICATE_KEYS
        /*
        ** This spot in the table is already in use.  See if the current string
        ** has already been inserted, and if so, increment its count.
        */                                             /* HW: ^^^^^^^^ ?? */
      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;
            }
#endif
      /*
      ** 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 NULL;      /*HW: was 0 */

      if( NULL == (ptr -> key = malloc(strlen(key)+1)) )
            {
            free(ptr);
            return NULL;
            }
      strcpy( ptr->key, key );
      ptr -> data = data;
      ptr -> next = (table->table)[val];
      (table->table)[val] = ptr;
      table->count++; /* HW */

      return data;
}


/*
** Look up a key and return the associated data.  Returns NULL if
** the key is not in the table.
*/
void *hash_lookup( char *key, hash_table *table )
{
      unsigned short val = hash(key) % table->size;
      bucket *ptr;

      assert( NULL != key );

      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 *hash_del(char *key, hash_table *table)
{
      unsigned short val = hash(key) % table->size;
      void *data;
      bucket *ptr, *last = NULL;

      assert( NULL != key );

      if( NULL == (table->table)[val] )
            return NULL;      /* HW: was 'return 0' */

      /*
      ** 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 );
                        table->count--; /* HW */
                        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