icl_hash.c

Go to the documentation of this file.

/* $Id: icl_hash.c,v 1.5 2004/09/12 05:21:15 seymour Exp $ */
/* $UTK_Copyright: $ */

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

#include "icl_hash.h"

#include <limits.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 long 
hash_pjw(char *datum)
{
  long 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);
}

icl_hash_t *
icl_hash_create(int nbuckets, long (*hash_function)(char*))
{
  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) 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;
  
  return ht;
}

void *
icl_hash_find(icl_hash_t *ht, char *key)
{
  icl_entry_t* curr;
  long 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 (strcmp(curr->key, key) == 0)
      return(curr->data);

  return NULL;
}

icl_entry_t * 
icl_hash_insert(icl_hash_t *ht, char *key, void *data)
{
  icl_entry_t *curr, *prev;
  long hash_val;

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

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

  for (prev=NULL,curr=ht->buckets[hash_val]; curr != NULL; prev=curr, curr=curr->next) 
    if (strcmp(curr->key, key) == 0) 
      return(NULL);     /* 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 start */

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

  return curr;
}

icl_entry_t *
icl_hash_update_insert(icl_hash_t *ht, char *key, void *data, void **olddata)
{
  icl_entry_t *curr, *prev;
  long 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 (strcmp(curr->key, key) == 0) {
      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));
  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;
}

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", curr->key, curr->data);
      curr=curr->next;
    }
  }

  return 0;
}