icl_hash.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "icl_hash.h"
#include <limits.h>

Include dependency graph for icl_hash.c:

Go to the source code of this file.

Macros
#define	BITS_IN_int   ( sizeof(int) * CHAR_BIT )
#define	THREE_QUARTERS   ((int) ((BITS_IN_int * 3) / 4))
#define	ONE_EIGHTH   ((int) (BITS_IN_int / 8))
#define	HIGH_BITS   ( ~((unsigned int)(~0) >> ONE_EIGHTH ))

Functions/Subroutines
icl_hash_t *	icl_hash_create (int nbuckets, unsigned int(*hash_function)(void *), int(*hash_key_compare)(void *, void *))
void *	icl_hash_find (icl_hash_t *ht, void *key)
icl_entry_t *	icl_hash_insert (icl_hash_t *ht, void *key, void *data)
icl_entry_t *	icl_hash_update_insert (icl_hash_t *ht, void *key, void *data, void **olddata)
int	icl_hash_delete (icl_hash_t *ht, void *key, void(*free_key)(void *), void(*free_data)(void *))
int	icl_hash_destroy (icl_hash_t *ht, void(*free_key)(void *), void(*free_data)(void *))
int	icl_hash_dump (FILE *stream, icl_hash_t *ht)

---

Detailed Description

Dependency free hash table implementation.

This simple hash table implementation should be easy to drop into any other peice of code, it does not depend on anything else :-)

Author:

Jakub Kurzak

Definition in file icl_hash.c.

---

Macro Definition Documentation

#define BITS_IN_int   ( sizeof(int) * CHAR_BIT )

Definition at line 24 of file icl_hash.c.

#define HIGH_BITS   ( ~((unsigned int)(~0) >> ONE_EIGHTH ))

Definition at line 27 of file icl_hash.c.

#define ONE_EIGHTH   ((int) (BITS_IN_int / 8))

Definition at line 26 of file icl_hash.c.

#define THREE_QUARTERS   ((int) ((BITS_IN_int * 3) / 4))

Definition at line 25 of file icl_hash.c.

---

Function/Subroutine Documentation

icl_hash_t* icl_hash_create	(	int	nbuckets,
		unsigned int(*)(void *)	hash_function,
		int(*)(void *, void *)	hash_key_compare
	)

Create a new hash table.

Parameters:

[in]	nbuckets	– number of buckets to create
[in]	hash_function	– pointer to the hashing function to be used
[in]	hash_key_compare	– pointer to the hash key comparison function to be used

Returns:

pointer to new hash table.

Definition at line 73 of file icl_hash.c.

References icl_hash_s::buckets, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_hash_s::nbuckets, and icl_hash_s::nentries.

{
    icl_hash_t *ht;
    int i;

    ht = (icl_hash_t*) malloc(sizeof(icl_hash_t));
    assert(ht!=NULL);
    if(!ht) return NULL;

    ht->nentries = 0;
    ht->buckets = (icl_entry_t**)malloc(nbuckets * sizeof(icl_entry_t*));
    assert(ht->buckets!=NULL);
    if(!ht->buckets) return NULL;

    ht->nbuckets = nbuckets;
    for(i=0;i<ht->nbuckets;i++)
        ht->buckets[i] = NULL;

    ht->hash_function = hash_function ? hash_function : hash_pjw;
    ht->hash_key_compare = hash_key_compare ? hash_key_compare : string_compare;

    return ht;
}

Here is the caller graph for this function:

int icl_hash_delete	(	icl_hash_t *	ht,
		void *	key,
		void(*)(void *)	free_key,
		void(*)(void *)	free_data
	)

Free one hash table entry located by key (key and data are freed using functions).

Parameters:

ht	– the hash table to be freed
key	– the key of the new item
free_key	– pointer to function that frees the key
free_data	– pointer to function that frees the data

Returns:

0 on success, -1 on failure.

Definition at line 227 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_entry_s::key, icl_hash_s::nbuckets, icl_hash_s::nentries, and icl_entry_s::next.

{
    icl_entry_t *curr, *prev;
    unsigned int hash_val;

    if(!ht || !key) return -1;
    hash_val = (* ht->hash_function)(key) % ht->nbuckets;

    prev = NULL;
    for (curr=ht->buckets[hash_val]; curr != NULL; )  {
        if ( ht->hash_key_compare(curr->key, key)) {
            if (prev == NULL) {
                ht->buckets[hash_val] = curr->next;
            } else {
                prev->next = curr->next;
            }
            if (*free_key && curr->key) (*free_key)(curr->key);
            if (*free_data && curr->data) (*free_data)(curr->data);
            ht->nentries++;
            free(curr);
            return 0;
        }
        prev = curr;
        curr = curr->next;
    }
    return -1;
}

int icl_hash_destroy	(	icl_hash_t *	ht,
		void(*)(void *)	free_key,
		void(*)(void *)	free_data
	)

Free hash table structures (key and data are freed using functions).

Parameters:

ht	– the hash table to be freed
free_key	– pointer to function that frees the key
free_data	– pointer to function that frees the data

Returns:

0 on success, -1 on failure.

Definition at line 265 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_entry_s::key, icl_hash_s::nbuckets, and icl_entry_s::next.

{
    icl_entry_t *bucket, *curr, *next;
    int i;

    if(!ht) return -1;

    for (i=0; i<ht->nbuckets; i++) {
        bucket = ht->buckets[i];
        for (curr=bucket; curr!=NULL; ) {
            next=curr->next;
            if (*free_key && curr->key) (*free_key)(curr->key);
            if (*free_data && curr->data) (*free_data)(curr->data);
            free(curr);
            curr=next;
        }
    }

    if(ht->buckets) free(ht->buckets);
    if(ht) free(ht);

    return 0;
}

Here is the caller graph for this function:

int icl_hash_dump	(	FILE *	stream,
		icl_hash_t *	ht
	)

Dump the hash table's contents to the given file pointer.

Parameters:

stream	– the file to which the hash table should be dumped
ht	– the hash table to be dumped

Returns:

0 on success, -1 on failure.

Definition at line 300 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_entry_s::key, icl_hash_s::nbuckets, and icl_entry_s::next.

{
    icl_entry_t *bucket, *curr;
    int i;

    if(!ht) return -1;

    for(i=0; i<ht->nbuckets; i++) {
        bucket = ht->buckets[i];
        for(curr=bucket; curr!=NULL; ) {
            if(curr->key)
                fprintf(stream, "icl_hash_dump: %s: %p\n", (char *)curr->key, curr->data);
            curr=curr->next;
        }
    }

    return 0;
}

void* icl_hash_find	(	icl_hash_t *	ht,
		void *	key
	)

Search for an entry in a hash table.

Parameters:

ht	– the hash table to be searched
key	– the key of the item to search for

Returns:

pointer to the data corresponding to the key. If the key was not found, returns NULL.

Definition at line 108 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_entry_s::key, icl_hash_s::nbuckets, and icl_entry_s::next.

{
    icl_entry_t* curr;
    unsigned int hash_val;

    if(!ht || !key) return NULL;

    hash_val = (* ht->hash_function)(key) % ht->nbuckets;

    for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
        if ( ht->hash_key_compare(curr->key, key))
            return(curr->data);

    return NULL;
}

Here is the caller graph for this function:

icl_entry_t* icl_hash_insert	(	icl_hash_t *	ht,
		void *	key,
		void *	data
	)

Insert an item into the hash table.

Parameters:

ht	– the hash table
key	– the key of the new item
data	– pointer to the new item's data

Returns:

pointer to the new item. Returns NULL on error.

Definition at line 135 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_entry_s::key, icl_hash_s::nbuckets, icl_hash_s::nentries, and icl_entry_s::next.

{
    icl_entry_t *curr;
    unsigned int hash_val;

    if(!ht || !key) return NULL;

    hash_val = (* ht->hash_function)(key) % ht->nbuckets;

    for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
        if ( ht->hash_key_compare(curr->key, key))
            return(NULL); /* key already exists */

    /* if key was not found */
    curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
    assert(curr != NULL);
    if(!curr) return NULL;

    curr->key = key;
    curr->data = data;
    curr->next = ht->buckets[hash_val]; /* add at start */

    ht->buckets[hash_val] = curr;
    ht->nentries++;

    return curr;
}

Here is the caller graph for this function:

icl_entry_t* icl_hash_update_insert	(	icl_hash_t *	ht,
		void *	key,
		void *	data,
		void **	olddata
	)

Replace entry in hash table with the given entry.

Parameters:

ht	– the hash table
key	– the key of the new item
data	– pointer to the new item's data
olddata	– pointer to the old item's data (set upon return)

Returns:

pointer to the new item. Returns NULL on error.

Definition at line 175 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_entry_s::key, icl_hash_s::nbuckets, icl_hash_s::nentries, and icl_entry_s::next.

{
    icl_entry_t *curr, *prev;
    unsigned int hash_val;

    if(!ht || !key) return NULL;

    hash_val = (* ht->hash_function)(key) % ht->nbuckets;

    /* Scan bucket[hash_val] for key */
    for (prev=NULL,curr=ht->buckets[hash_val]; curr != NULL; prev=curr, curr=curr->next)
        /* If key found, remove node from list, free old key, and setup olddata for the return */
        if ( ht->hash_key_compare(curr->key, key)) {
            if (olddata != NULL) {
                *olddata = curr->data;
                free(curr->key);
            }

            if (prev == NULL)
                ht->buckets[hash_val] = curr->next;
            else
                prev->next = curr->next;
        }

    /* Since key was either not found, or found-and-removed, create and prepend new node */
    curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
    assert(curr!=NULL);
    if(curr == NULL) return NULL; /* out of memory */

    curr->key = key;
    curr->data = data;
    curr->next = ht->buckets[hash_val]; /* add at start */

    ht->buckets[hash_val] = curr;
    ht->nentries++;

    if(olddata!=NULL && *olddata!=NULL)
        *olddata = NULL;

    return curr;
}