hash.c

00001 /***************************************************************************
00002 *cr
00003 *cr (C) Copyright 1995-2019 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.17 $ $Date: 2019年01月17日 21:21:03 $
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