#include 

#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

    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;isize; i++)

        {

        if ((table->table)[i] != NULL)

            {

            for (temp = (table->table)[i];

            NULL != temp;

            temp = temp -> next)

                {

                func(temp -> key, temp->data);

            }

        }

    }

}

#ifdef TEST

#include 

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