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

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

Generated on Tue Dec 3 03:10:02 2024 for VMD Plugins (current) by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002