VB icon

Hash table functions

Email
Submitted on: 1/1/2015 11:50:00 AM
By: Bob Stout (republished under Open Content License) (from psc cd)  
Level: Intermediate
User Rating: By 4 Users
Compatibility: C, C++ (general), Microsoft Visual C++, Borland C++, UNIX C++
Views: 1216
 
     Hash table management by Jerry Coffin, with improvements by HenkJan Wolthuis.
 

INCLUDE files:

Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
//**************************************
//INCLUDE files for :Hash table functions
//**************************************
/* +++Date last modified: 05-Jul-1997 */
#ifndef HASH__H
#define HASH__H
#include <stddef.h>/* For size_t */
/*
** A hash table consists of an array of these buckets. Each bucket
** holds a copy of the key, a pointer to the data associated with the
** key, and a pointer to the next bucket that collided with this one,
** if there was one.
*/
typedef struct bucket {
char *key;
void *data;
struct bucket *next;
} bucket;
/*
** This is what you actually declare an instance of to create a table.
** You then call 'construct_table' with the address of this structure,
** and a guess at the size of the table. Note that more nodes than this
** can be inserted in the table, but performance degrades as this
** happens. Performance should still be quite adequate until 2 or 3
** times as many nodes have been inserted as the table was created with.
*/
typedef struct hash_table {
size_t size;
bucket **table;
} hash_table;
/*
** This is used to construct the table. If it doesn't succeed, it sets
** the table's size to 0, and the pointer to the table to NULL.
*/
hash_table *construct_table(hash_table *table,size_t size);
/*
** Inserts a pointer to 'data' in the table, with a copy of 'key' as its
** key. Note that this makes a copy of the key, but NOT of the
** associated data.
*/
void *insert(char *key,void *data,struct hash_table *table);
/*
** Returns a pointer to the data associated with a key. If the key has
** not been inserted in the table, returns NULL.
*/
void *lookup(char *key,struct hash_table *table);
/*
** Deletes an entry from the table. Returns a pointer to the data that
** was associated with the key so the calling code can dispose of it
** properly.
*/
void *del(char *key,struct hash_table *table);
/*
** Goes through a hash table and calls the function passed to it
** for each node that has been inserted. The function is passed
** a pointer to the key, and a pointer to the data associated
** with it.
*/
void enumerate(struct hash_table *table,void (*func)(char *,void *));
/*
** Frees a hash table. For each node that was inserted in the table,
** it calls the function whose address it was passed, with a pointer
** to the data that was in the table. The function is expected to
** free the data. Typical usage would be:
** free_table(&table, free);
** if the data placed in the table was dynamically allocated, or:
** free_table(&table, NULL);
** if not. ( If the parameter passed is NULL, it knows not to call
** any function with the data. )
*/
void free_table(hash_table *table, void (*func)(void *));
#endif /* HASH__H */
code:
Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
				
//**************************************
// Name: Hash table functions
// Description:Hash table management by Jerry Coffin, with improvements by HenkJan Wolthuis.
// By: Bob Stout (republished under Open Content License) (from psc cd)
//**************************************

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


Other 4 submission(s) by this author

 


Report Bad Submission
Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

Your Vote

What do you think of this code (in the Intermediate category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)
 

Other User Comments


 There are no comments on this submission.
 

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular code, please click here instead.)
 

To post feedback, first please login.