icl_hash.c

Go to the documentation of this file.

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

#include "icl_hash.h"

#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))

static unsigned int hash_pjw(void *key);
static int string_compare(void *a, void *b);


static unsigned int hash_pjw(void *key)
{
    char *datum = (char*)key;
    unsigned int hash_value, i;

    if(!datum)
        return 0;

    for (hash_value = 0; *datum; ++datum) {
        hash_value = (hash_value << ONE_EIGHTH) + *datum;
        if ((i = hash_value & HIGH_BITS) != 0)
            hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
    }
    return (hash_value);
}

static int string_compare(void *a, void *b)
{
    return (strcmp( (char*)a, (char*)b ) == 0);
}


icl_hash_t* icl_hash_create(
    int nbuckets,
    unsigned int (*hash_function)(void*),
    int (*hash_key_compare)(void*, void*))
{
    icl_hash_t *ht;
    int i;

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

    ht->nentries = 0;
    ht->buckets = (icl_entry_t**)malloc(nbuckets*sizeof(icl_entry_t*));
    if(!ht->buckets) {
        free(ht);
        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;
}


void *icl_hash_find(icl_hash_t *ht, void* key)
{
    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;
}


icl_entry_t* icl_hash_insert(icl_hash_t *ht, void* key, void *data)
{
    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); // The key already exists.

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

    curr->key = key;
    curr->data = data;
    curr->next = ht->buckets[hash_val]; // Add at the start.

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

    return curr;
}


icl_entry_t *icl_hash_update_insert(
    icl_hash_t *ht, void* key, void *data, void **olddata)
{
    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 the key.
    for (prev = NULL, curr=ht->buckets[hash_val];
         curr != NULL;
         prev = curr, curr = curr->next)
        // IF key found, remove the node from the list,
        // free the 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 the key was either not found,
    // or found-and-removed, create and prepend a new node.
    curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
    if(curr == NULL)
        return NULL; // Out of memory.

    curr->key = key;
    curr->data = data;
    curr->next = ht->buckets[hash_val]; // Add at the start.

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

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

    return curr;
}


int icl_hash_delete(
    icl_hash_t *ht, void* key,
    void (*free_key)(void*),
    void (*free_data)(void*))
{
    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 (*free_key)(void*),
    void (*free_data)(void*))
{
    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;
}


int icl_hash_dump(FILE *stream, icl_hash_t *ht)
{
    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;
}