icl_hash.c

Go to the documentation of this file.
00001 
00009 /* $Id: icl_hash.c,v 1.5 2004/09/12 05:21:15 seymour Exp $ */
00010 /* $UTK_Copyright: $ */
00011 
00012 #include <stdlib.h>
00013 #include <stdio.h>
00014 #include <string.h>
00015 
00016 #include "icl_hash.h"
00017 
00018 #include <limits.h>
00019 #define BITS_IN_int     ( sizeof(int) * CHAR_BIT )
00020 #define THREE_QUARTERS  ((int) ((BITS_IN_int * 3) / 4))
00021 #define ONE_EIGHTH      ((int) (BITS_IN_int / 8))
00022 #define HIGH_BITS       ( ~((unsigned int)(~0) >> ONE_EIGHTH ))
00023 
00037 static long 
00038 hash_pjw(char *datum)
00039 {
00040   long hash_value, i;
00041 
00042   if(!datum) return 0;
00043 
00044   for (hash_value = 0; *datum; ++datum) {
00045     hash_value = (hash_value << ONE_EIGHTH) + *datum;
00046     if ((i = hash_value & HIGH_BITS) != 0)
00047       hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
00048   }
00049   return (hash_value);
00050 }
00051 
00061 icl_hash_t *
00062 icl_hash_create(int nbuckets, long (*hash_function)(char*))
00063 {
00064   icl_hash_t *ht;
00065   int i;
00066 
00067   ht = (icl_hash_t*) malloc(sizeof(icl_hash_t));
00068   if(!ht) return NULL;
00069 
00070   ht->nentries = 0;
00071   ht->buckets = (icl_entry_t**)malloc(nbuckets * sizeof(icl_entry_t*));
00072   if(!ht->buckets) return NULL;
00073 
00074   ht->nbuckets = nbuckets;
00075   for(i=0;i<ht->nbuckets;i++)
00076     ht->buckets[i] = NULL;
00077 
00078   ht->hash_function = hash_function ? hash_function : hash_pjw;
00079   
00080   return ht;
00081 }
00082 
00093 void *
00094 icl_hash_find(icl_hash_t *ht, char *key)
00095 {
00096   icl_entry_t* curr;
00097   long hash_val;
00098 
00099   if(!ht || !key) return NULL;
00100   
00101   hash_val = (* ht->hash_function)(key) % ht->nbuckets;
00102 
00103   for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next) 
00104     if (strcmp(curr->key, key) == 0)
00105       return(curr->data);
00106 
00107   return NULL;
00108 }
00109 
00120 icl_entry_t * 
00121 icl_hash_insert(icl_hash_t *ht, char *key, void *data)
00122 {
00123   icl_entry_t *curr, *prev;
00124   long hash_val;
00125 
00126   if(!ht || !key) return NULL;
00127 
00128   hash_val = (* ht->hash_function)(key) % ht->nbuckets;
00129 
00130   for (prev=NULL,curr=ht->buckets[hash_val]; curr != NULL; prev=curr, curr=curr->next) 
00131     if (strcmp(curr->key, key) == 0) 
00132       return(NULL);     /* key already exists */
00133 
00134   /* if key was not found */
00135   curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
00136   if(!curr) return NULL;
00137 
00138   curr->key = key;
00139   curr->data = data;
00140   curr->next = ht->buckets[hash_val];   /* add at start */
00141 
00142   ht->buckets[hash_val] = curr;
00143   ht->nentries++;
00144 
00145   return curr;
00146 }
00147 
00159 icl_entry_t *
00160 icl_hash_update_insert(icl_hash_t *ht, char *key, void *data, void **olddata)
00161 {
00162   icl_entry_t *curr, *prev;
00163   long hash_val;
00164 
00165   if(!ht || !key) return NULL;
00166 
00167   hash_val = (* ht->hash_function)(key) % ht->nbuckets;
00168 
00169   /* Scan bucket[hash_val] for key */
00170   for (prev=NULL,curr=ht->buckets[hash_val]; curr != NULL; prev=curr, curr=curr->next) 
00171     /* If key found, remove node from list, free old key, and setup olddata for the return */
00172     if (strcmp(curr->key, key) == 0) {
00173       if (olddata != NULL) {
00174     *olddata = curr->data;
00175     free(curr->key);
00176       }
00177 
00178       if (prev == NULL) 
00179         ht->buckets[hash_val] = curr->next;
00180       else 
00181         prev->next = curr->next;
00182     }
00183 
00184   /* Since key was either not found, or found-and-removed, create and prepend new node */
00185   curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
00186   if(curr == NULL) return NULL; /* out of memory */
00187 
00188   curr->key = key;
00189   curr->data = data;
00190   curr->next = ht->buckets[hash_val];   /* add at start */
00191 
00192   ht->buckets[hash_val] = curr;
00193   ht->nentries++;
00194 
00195   if(olddata!=NULL && *olddata!=NULL) 
00196     *olddata = NULL;
00197 
00198   return curr;
00199 }
00200 
00211 int 
00212 icl_hash_destroy(icl_hash_t *ht, void (*free_key)(void*), void (*free_data)(void*))
00213 {
00214   icl_entry_t *bucket, *curr, *next;
00215   int i;
00216 
00217   if(!ht) return -1;
00218 
00219   for (i=0; i<ht->nbuckets; i++) {
00220     bucket = ht->buckets[i];
00221     for (curr=bucket; curr!=NULL; ) {
00222       next=curr->next;
00223       if (*free_key && curr->key) (*free_key)(curr->key);
00224       if (*free_data && curr->data) (*free_data)(curr->data);
00225       free(curr);
00226       curr=next;
00227     }
00228   }
00229 
00230   if(ht->buckets) free(ht->buckets);
00231   if(ht) free(ht);
00232 
00233   return 0;
00234 }
00235 
00245 int 
00246 icl_hash_dump(FILE* stream, icl_hash_t* ht) 
00247 {
00248   icl_entry_t *bucket, *curr;
00249   int i;
00250   
00251   if(!ht) return -1;
00252 
00253   for(i=0; i<ht->nbuckets; i++) {
00254     bucket = ht->buckets[i];
00255     for(curr=bucket; curr!=NULL; ) {
00256       if(curr->key) 
00257     fprintf(stream, "icl_hash_dump: %s: %p\n", curr->key, curr->data);
00258       curr=curr->next;
00259     }
00260   }
00261 
00262   return 0;
00263 }