Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

hash.c

Go to the documentation of this file.
00001 /***************************************************************************
00002  *cr
00003  *cr            (C) Copyright 1995-2016 The Board of Trustees of the
00004  *cr                        University of Illinois
00005  *cr                         All Rights Reserved
00006  *cr
00007  ***************************************************************************/
00008 
00009 /***************************************************************************
00010  * RCS INFORMATION:
00011  *
00012  *      $RCSfile: hash.c,v $
00013  *      $Author: johns $        $Locker:  $             $State: Exp $
00014  *      $Revision: 1.7 $      $Date: 2016/11/28 05:01:54 $
00015  *
00016  ***************************************************************************
00017  * DESCRIPTION:
00018  *   A simple hash table implementation for strings, contributed by John Stone,
00019  *   derived from his ray tracer code.
00020  ***************************************************************************/
00021 
00022 #include <stdio.h>
00023 #include <stdlib.h>
00024 #include <string.h>
00025 #include "hash.h"
00026 
00027 #define HASH_LIMIT 0.5
00028 
00030 typedef struct hash_node_t {
00031   int data;                           /* data in hash node */
00032   const char * key;                   /* key for hash lookup */
00033   struct hash_node_t *next;           /* next node in hash chain */
00034 } hash_node_t;
00035 
00036 /*
00037  *  hash() - Hash function returns a hash number for a given key.
00038  *
00039  *  tptr: Pointer to a hash table
00040  *  key: The key to create a hash number for
00041  */
00042 static int hash(const hash_t *tptr, const char *key) {
00043   int i=0;
00044   int hashvalue;
00045  
00046   while (*key != '\0')
00047     i=(i<<3)+(*key++ - '0');
00048  
00049   hashvalue = (((i*1103515249)>>tptr->downshift) & tptr->mask);
00050   if (hashvalue < 0) {
00051     hashvalue = 0;
00052   }    
00053 
00054   return hashvalue;
00055 }
00056 
00057 /*
00058  *  hash_init() - Initialize a new hash table.
00059  *
00060  *  tptr: Pointer to the hash table to initialize
00061  *  buckets: The number of initial buckets to create
00062  */
00063 VMDEXTERNSTATIC void hash_init(hash_t *tptr, int buckets) {
00064 
00065   /* make sure we allocate something */
00066   if (buckets==0)
00067     buckets=16;
00068 
00069   /* initialize the table */
00070   tptr->entries=0;
00071   tptr->size=2;
00072   tptr->mask=1;
00073   tptr->downshift=29;
00074 
00075   /* ensure buckets is a power of 2 */
00076   while (tptr->size<buckets) {
00077     tptr->size<<=1;
00078     tptr->mask=(tptr->mask<<1)+1;
00079     tptr->downshift--;
00080   } /* while */
00081 
00082   /* allocate memory for table */
00083   tptr->bucket=(hash_node_t **) calloc(tptr->size, sizeof(hash_node_t *));
00084 
00085   return;
00086 }
00087 
00088 /*
00089  *  rebuild_table() - Create new hash table when old one fills up.
00090  *
00091  *  tptr: Pointer to a hash table
00092  */
00093 static void rebuild_table(hash_t *tptr) {
00094   hash_node_t **old_bucket, *old_hash, *tmp;
00095   int old_size, h, i;
00096 
00097   old_bucket=tptr->bucket;
00098   old_size=tptr->size;
00099 
00100   /* create a new table and rehash old buckets */
00101   hash_init(tptr, old_size<<1);
00102   for (i=0; i<old_size; i++) {
00103     old_hash=old_bucket[i];
00104     while(old_hash) {
00105       tmp=old_hash;
00106       old_hash=old_hash->next;
00107       h=hash(tptr, tmp->key);
00108       tmp->next=tptr->bucket[h];
00109       tptr->bucket[h]=tmp;
00110       tptr->entries++;
00111     } /* while */
00112   } /* for */
00113 
00114   /* free memory used by old table */
00115   free(old_bucket);
00116 
00117   return;
00118 }
00119 
00120 /*
00121  *  hash_lookup() - Lookup an entry in the hash table and return a pointer to
00122  *    it or HASH_FAIL if it wasn't found.
00123  *
00124  *  tptr: Pointer to the hash table
00125  *  key: The key to lookup
00126  */
00127 VMDEXTERNSTATIC int hash_lookup(const hash_t *tptr, const char *key) {
00128   int h;
00129   hash_node_t *node;
00130 
00131 
00132   /* find the entry in the hash table */
00133   h=hash(tptr, key);
00134   for (node=tptr->bucket[h]; node!=NULL; node=node->next) {
00135     if (!strcmp(node->key, key))
00136       break;
00137   }
00138 
00139   /* return the entry if it exists, or HASH_FAIL */
00140   return(node ? node->data : HASH_FAIL);
00141 }
00142 
00143 /*
00144  *  hash_insert() - Insert an entry into the hash table.  If the entry already
00145  *  exists return a pointer to it, otherwise return HASH_FAIL.
00146  *
00147  *  tptr: A pointer to the hash table
00148  *  key: The key to insert into the hash table
00149  *  data: A pointer to the data to insert into the hash table
00150  */
00151 VMDEXTERNSTATIC int hash_insert(hash_t *tptr, const char *key, int data) {
00152   int tmp;
00153   hash_node_t *node;
00154   int h;
00155 
00156   /* check to see if the entry exists */
00157   if ((tmp=hash_lookup(tptr, key)) != HASH_FAIL)
00158     return(tmp);
00159 
00160   /* expand the table if needed */
00161   while (tptr->entries>=HASH_LIMIT*tptr->size)
00162     rebuild_table(tptr);
00163 
00164   /* insert the new entry */
00165   h=hash(tptr, key);
00166   node=(struct hash_node_t *) malloc(sizeof(hash_node_t));
00167   node->data=data;
00168   node->key=key;
00169   node->next=tptr->bucket[h];
00170   tptr->bucket[h]=node;
00171   tptr->entries++;
00172 
00173   return HASH_FAIL;
00174 }
00175 
00176 /*
00177  *  hash_delete() - Remove an entry from a hash table and return a pointer
00178  *  to its data or HASH_FAIL if it wasn't found.
00179  *
00180  *  tptr: A pointer to the hash table
00181  *  key: The key to remove from the hash table
00182  */
00183 VMDEXTERNSTATIC int hash_delete(hash_t *tptr, const char *key) {
00184   hash_node_t *node, *last;
00185   int data;
00186   int h;
00187 
00188   /* find the node to remove */
00189   h=hash(tptr, key);
00190   for (node=tptr->bucket[h]; node; node=node->next) {
00191     if (!strcmp(node->key, key))
00192       break;
00193   }
00194 
00195   /* Didn't find anything, return HASH_FAIL */
00196   if (node==NULL)
00197     return HASH_FAIL;
00198 
00199   /* if node is at head of bucket, we have it easy */
00200   if (node==tptr->bucket[h])
00201     tptr->bucket[h]=node->next;
00202   else {
00203     /* find the node before the node we want to remove */
00204     for (last=tptr->bucket[h]; last && last->next; last=last->next) {
00205       if (last->next==node)
00206         break;
00207     }
00208     last->next=node->next;
00209   }
00210 
00211   /* free memory and return the data */
00212   data=node->data;
00213   free(node);
00214 
00215   return(data);
00216 }
00217 
00218 
00219 /*
00220  * inthash_entries() - return the number of hash table entries.
00221  *
00222  */
00223 VMDEXTERNSTATIC int hash_entries(hash_t *tptr) {
00224   return tptr->entries;
00225 }
00226 
00227 
00228 
00229 
00230 /*
00231  * hash_destroy() - Delete the entire table, and all remaining entries.
00232  * 
00233  */
00234 VMDEXTERNSTATIC void hash_destroy(hash_t *tptr) {
00235   hash_node_t *node, *last;
00236   int i;
00237 
00238   for (i=0; i<tptr->size; i++) {
00239     node = tptr->bucket[i];
00240     while (node != NULL) { 
00241       last = node;   
00242       node = node->next;
00243       free(last);
00244     }
00245   }     
00246 
00247   /* free the entire array of buckets */
00248   if (tptr->bucket != NULL) {
00249     free(tptr->bucket);
00250     memset(tptr, 0, sizeof(hash_t));
00251   }
00252 }
00253 
00254 /*
00255  *  alos() - Find the average length of search.
00256  *
00257  *  tptr: Pointer to a hash table
00258  */
00259 static float alos(hash_t *tptr) {
00260   int i,j;
00261   float alos=0;
00262   hash_node_t *node;
00263 
00264 
00265   for (i=0; i<tptr->size; i++) {
00266     for (node=tptr->bucket[i], j=0; node!=NULL; node=node->next, j++);
00267     if (j)
00268       alos+=((j*(j+1))>>1);
00269   } /* for */
00270 
00271   return(tptr->entries ? alos/tptr->entries : 0);
00272 }
00273 
00274 
00275 /*
00276  *  hash_stats() - Return a string with stats about a hash table.
00277  *
00278  *  tptr: A pointer to the hash table
00279  */
00280 VMDEXTERNSTATIC char * hash_stats(hash_t *tptr) {
00281   static char buf[1024];
00282 
00283   sprintf(buf, "%u slots, %u entries, and %1.2f ALOS",
00284     (int)tptr->size, (int)tptr->entries, alos(tptr));
00285 
00286   return(buf);
00287 }
00288 
00289 
00290 
00291 

Generated on Thu Dec 12 03:09:33 2024 for VMD Plugins (current) by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002