hash.c

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

                  ** node as above.
                  */
                  else
                  {
                        /* HW: changed this bit to match the comments above */
                        data = ptr->data;
                        (table->table)[val] = ptr->next;
                        free( ptr->key );
                        free( ptr );
                        table->count--; /* HW */
                        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;

      assert( NULL != key );

      if( NULL != function )
      {
            function( hash_del( key, the_table ) );
      }
      else
            hash_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 hash_free_table( hash_table *table, void (*func)(void *) )
{
      function = func;
      the_table = table;

      hash_enumerate( table, free_node );
      free( table->table );
      table->table = NULL;
      table->size = 0;
      table->count = 0; /* HW */

      the_table = NULL;
      function = 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 hash_enumerate( hash_table *table, void (*func)(char *, void *) )
{
      unsigned i;
      bucket *temp;
      bucket *swap;

      for( i=0; i<table->size; i++ )
      {
            if( NULL != (table->table)[i] )
            {
                  /* HW: changed this loop */
                  temp = (table->table)[i];
                  while( NULL != temp )
                  {
                        /* HW: swap trick, in case temp is freed by 'func' */
                        swap = temp->next;
                        func( temp -> key, temp->data );
                        temp = swap;
                  }
            }
      }
}

/*      HW: added hash_sorted_enum()

      hash_sorted_enum is like hash_enumerate but gives
      sorted output. This is much slower than hash_enumerate, but
      sometimes nice for printing to a file...
*/

typedef struct sort_struct
      {
      char *key;
      void *data;
      } sort_struct;
static sort_struct *sortmap = NULL;

static int counter = 0;

/* HW: used as 'func' for hash_enumerate */
static void key_get( char *key, void *data )
{
      sortmap[ counter ].key = key;
      sortmap[ counter ].data = data;
      counter++;
}

/* HW: used for comparing the keys in qsort */
static int key_comp( const void* a, const void *b )
{
      return strcmp( (*(sort_struct*)a).key, (*(sort_struct*)b).key );
}

/*    HW: it's a compromise between speed and space. this one needs
      table->count * sizeof( sort_struct) memory.
      Another approach only takes count*sizeof(char*), but needs
      to hash_lookup the data of every key after sorting the key.
      returns 0 on malloc failure, 1 on success
*/
int hash_sorted_enum( hash_table *table, void (*func)( char *, void *) )
{
      int i;

      /* nothing to do ! */
      if( NULL == table || 0 == table->count || NULL == func )
            return 0;

      /* malloc an pointerarray for all hashkey's and datapointers */
      if( NULL == ( sortmap = malloc( sizeof( sort_struct ) * table->count)) )
            return 0;

      /* copy the pointers to the hashkey's */
      counter = 0;
      hash_enumerate( table, key_get );

      /* sort the pointers to the keys */
      qsort( sortmap, table->count, sizeof(sort_struct), key_comp );

      /* call the function for each node */
      for( i=0; i< table->count; i++ )
      {
            func( sortmap[i].key, sortmap[i].data );
      }

      /* free the pointerarray */
      free( sortmap );
      sortmap = NULL;

      return 1;
}

/* HW: changed testmain */
#define TEST
#ifdef TEST

#include <stdio.h>
//#include "snip_str.h" /* for strdup() */

FILE *o;

void fprinter(char *string, void *data)
{
      fprintf(o,"%s:    %s\n", string, (char *)data);
}

void printer(char *string, void *data)
{
      printf("%s:    %s\n", string, (char *)data);
}

/* function to pass to hash_free_table */
void strfree( void *d )
{
      /* any additional processing goes here (if you use structures as data) */
      /* free the datapointer */
      free(d);
}


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;

      hash_construct_table(&table,211);

      /* I know, no checking on strdup ;-)), but using strdup
            to demonstrate hash_table_free with a functionpointer */
      for (i = 0; NULL != strings[i]; i++ )
            hash_insert( strings[i], strdup(junk[i]), &table );

      /* enumerating to a file */
      if( NULL != (o = fopen("HASH.HSH","wb")) )
      {
            fprintf( o, "%d strings in the table:\n\n", table.count );
            hash_enumerate( &table, fprinter );
            fprintf( o, "\nsorted by key:\n");
            hash_sorted_enum( &table, fprinter );
            fclose( o );
      }

      /* enumerating to screen */
      hash_sorted_enum( &table, printer );
      printf("\n");

      /* delete 3 strings, should be 3 left */
      for( i=0; i<3; i++ )
      {
            /* hash_del returns a pointer to the data */
            strfree( hash_del( strings[i], &table) );
      }
      hash_enumerate( &table, printer);

      for (i=0;NULL != strings[i];i++)
      {
            j = hash_lookup(strings[i], &table);
            if (NULL == j)
                  printf("\n'%s' is not in the table", strings[i]);
            else
                  printf("\n%s is still in the table.", strings[i]);
      }

      hash_free_table( &table, strfree );

      return 0;
}
#endif /* TEST */