Defines | Functions

icl_hash.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "icl_hash.h"
#include <limits.h>
Include dependency graph for icl_hash.c:

Go to the source code of this file.

Defines

#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

static long hash_pjw (char *datum)
icl_hash_t * icl_hash_create (int nbuckets, long(*hash_function)(char *))
void * icl_hash_find (icl_hash_t *ht, char *key)
icl_entry_t * icl_hash_insert (icl_hash_t *ht, char *key, void *data)
icl_entry_t * icl_hash_update_insert (icl_hash_t *ht, char *key, void *data, void **olddata)
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 :-)

Definition in file icl_hash.c.

Define Documentation

#define BITS_IN_int   ( sizeof(int) * CHAR_BIT )

Definition at line 19 of file icl_hash.c.

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

Definition at line 22 of file icl_hash.c.

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

Definition at line 21 of file icl_hash.c.

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

Definition at line 20 of file icl_hash.c.

Function Documentation

static long hash_pjw ( char *  datum  )  [static]

A simple string hash.

An adaptation of Peter Weinberger's (PJW) generic hashing algorithm based on Allen Holub's version. Accepts a pointer to a datum to be hashed and returns an unsigned integer. From: Keith Seymour's proxy library code

Parameters:
datum -- the string to be hashed
Returns:
the hash index

Definition at line 38 of file icl_hash.c.

{
  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);
}

Here is the caller graph for this function:

icl_hash_t* icl_hash_create ( int  nbuckets,
long(*)(char *)  hash_function 
)

Create a new hash table.

Parameters:
nbuckets -- number of buckets to create
hash_function -- pointer to the hashing function to be used
Returns:
pointer to new hash table.

Definition at line 62 of file icl_hash.c.

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 212 of file icl_hash.c.

{
  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 246 of file icl_hash.c.

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* icl_hash_find ( icl_hash_t *  ht,
char *  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 94 of file icl_hash.c.

{
  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;
}

Here is the caller graph for this function:

icl_entry_t* icl_hash_insert ( icl_hash_t *  ht,
char *  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 121 of file icl_hash.c.

{
  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;
}

Here is the caller graph for this function:

icl_entry_t* icl_hash_update_insert ( icl_hash_t *  ht,
char *  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 160 of file icl_hash.c.

{
  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;
}

Here is the caller graph for this function:

Generated on Mon May 10 2010 11:13:49 for GridSolve by  doxygen 1.6.3-20100507