00001
00002
00003
00004
00005 #include <stdio.h>
00006 #include <stdlib.h>
00007 #include <string.h>
00008 #include "hash.h"
00009
00010
00011
00012
00013 typedef struct hash_element_ {
00014 void *entry;
00015 struct hash_element_ *next;
00016 struct hash_element_ **prev;
00017 #ifdef STATISTICS
00018 int hits;
00019 int seeks;
00020 #endif
00021 } BUCKET;
00022
00023 typedef struct hash_tab_ {
00024 BUCKET **table;
00025 int size;
00026 int numsyms;
00027 BUCKET *lastpos;
00028 int (*compare)(
00029 #ifdef PROTOTYPE
00030 void *, void *
00031 #endif
00032 );
00033 unsigned (*hash)(
00034 #ifdef PROTOTYPE
00035 void *
00036 #endif
00037 );
00038 } HASH_TAB;
00039
00040
00041
00042
00043
00044
00045
00046
00047 HASH HashCreate (
00048 #ifdef PROTOTYPE
00049 int size, int (*compare)(void *entry1, void *entry2),
00050 unsigned (*hashfunc)(void *entry))
00051 #else
00052 size, compare, hashfunc)
00053 int size;
00054 int (*compare)();
00055 unsigned (*hashfunc)();
00056 #endif
00057 {
00058 HASH_TAB *tabp;
00059
00060 if (NULL == compare || NULL == hashfunc)
00061 return (NULL);
00062 if (size < 1) size = 11;
00063 tabp = (HASH_TAB *) malloc (sizeof(HASH_TAB) + size * sizeof(BUCKET *));
00064 if (NULL != tabp) {
00065 tabp->table = (BUCKET **)(tabp + 1);
00066 tabp->size = size;
00067 tabp->numsyms = 0;
00068 tabp->lastpos = NULL;
00069 tabp->compare = compare;
00070 tabp->hash = hashfunc;
00071 for (size = 0; size < tabp->size; size++)
00072 tabp->table[size] = NULL;
00073 }
00074 return ((HASH)tabp);
00075 }
00076
00077
00078
00079
00080
00081 void HashDestroy (
00082 #ifdef PROTOTYPE
00083 HASH hash, void (*freeentry)(void *entry))
00084 #else
00085 hash, freeentry)
00086 HASH hash;
00087 void (*freeentry)();
00088 #endif
00089 {
00090 HASH_TAB *tabp = (HASH_TAB *)hash;
00091 BUCKET *p, *next;
00092 int i;
00093
00094 for (i = 0; i < tabp->size; i++) {
00095 for (p = tabp->table[i]; p != NULL; p = next) {
00096 next = p->next;
00097 if (NULL != freeentry)
00098 (*freeentry) (p->entry);
00099 free (p);
00100 }
00101 }
00102 free (tabp);
00103 }
00104
00105
00106
00107
00108
00109
00110
00111 void *HashFind (
00112 #ifdef PROTOTYPE
00113 HASH hash, void *entry)
00114 #else
00115 hash, entry)
00116 HASH hash;
00117 void *entry;
00118 #endif
00119 {
00120 BUCKET *p, **pf;
00121 HASH_TAB *tabp = (HASH_TAB *)hash;
00122
00123 pf = &(tabp->table)[(*tabp->hash) (entry) % tabp->size];
00124 p = *pf;
00125
00126 while (NULL != p && (*tabp->compare) (entry, p->entry)) {
00127 #ifdef STATISTICS
00128 p->seeks++;
00129 #endif
00130 p = p->next;
00131 }
00132 if (NULL == p)
00133 return (NULL);
00134
00135 #ifdef STATISTICS
00136 p->hits++;
00137 #endif
00138 tabp->lastpos = p;
00139
00140
00141
00142
00143
00144
00145
00146
00147 #ifdef REORDER
00148 if (p != *pf) {
00149 BUCKET *sym = *pf;
00150 if ((*(p->prev) = p->next) != NULL)
00151 p->next->prev = p->prev;
00152 *pf = p;
00153 p->prev = pf;
00154 p->next = sym;
00155 sym->prev = &p->next;
00156 }
00157 #endif
00158
00159 return (p->entry);
00160 }
00161
00162
00163
00164
00165
00166
00167 void *HashAdd (
00168 #ifdef PROTOTYPE
00169 HASH hash, void *entry)
00170 #else
00171 hash, entry)
00172 HASH hash;
00173 void *entry;
00174 #endif
00175 {
00176 BUCKET **p, *tmp;
00177 BUCKET *sym;
00178 HASH_TAB *tabp = (HASH_TAB *)hash;
00179
00180 if ((sym = (BUCKET *) malloc (sizeof(BUCKET))) == NULL)
00181 return (NULL);
00182
00183 p = &(tabp->table)[(*tabp->hash) (entry) % tabp->size];
00184
00185 tmp = *p;
00186 *p = sym;
00187 sym->entry = entry;
00188 sym->prev = p;
00189 sym->next = tmp;
00190
00191 if (NULL != tmp)
00192 tmp->prev = &sym->next;
00193
00194 tabp->numsyms++;
00195 tabp->lastpos = NULL;
00196 return (entry);
00197 }
00198
00199
00200
00201
00202
00203 void *HashDelete (
00204 #ifdef PROTOTYPE
00205 HASH hash, void *entry)
00206 #else
00207 hash, entry)
00208 HASH hash;
00209 void *entry;
00210 #endif
00211 {
00212 BUCKET *p;
00213 HASH_TAB *tabp = (HASH_TAB *)hash;
00214
00215 if (NULL == tabp->lastpos || entry != tabp->lastpos->entry) {
00216 if (NULL == HashFind (hash, entry))
00217 return (NULL);
00218 }
00219 p = tabp->lastpos;
00220 tabp->numsyms--;
00221 if ((*(p->prev) = p->next) != NULL)
00222 p->next->prev = p->prev;
00223 free (p);
00224 return (entry);
00225 }
00226
00227
00228
00229
00230
00231 int HashList (
00232 #ifdef PROTOTYPE
00233 HASH hash, int (*listentry)(void *entry, void *userdata),
00234 void *userdata)
00235 #else
00236 hash, listentry, userdata)
00237 HASH hash;
00238 int (*listentry)();
00239 void *userdata;
00240 #endif
00241 {
00242 HASH_TAB *tabp = (HASH_TAB *)hash;
00243 BUCKET *p;
00244 int i, cnt = 0;
00245
00246 if (NULL == listentry)
00247 return (tabp->numsyms);
00248 for (i = 0; i < tabp->size; i++) {
00249 for (p = tabp->table[i]; p != NULL; p = p->next)
00250 cnt += (*listentry) (p->entry, userdata);
00251 }
00252 return (cnt);
00253 }
00254
00255
00256
00257
00258
00259 #define MAXINT (((unsigned) ~ 0) >> 1)
00260 #define MAXLEN 128
00261
00262 void HastStats (
00263 #ifdef PROTOTYPE
00264 HASH hash)
00265 #else
00266 hash)
00267 HASH hash;
00268 #endif
00269 {
00270 HASH_TAB *tabp = (HASH_TAB *)hash;
00271 BUCKET *p;
00272 int i;
00273 int chain_len;
00274 int chain_avg;
00275 int deviation = 0;
00276 int maxlen = 0;
00277 int minlen = MAXINT;
00278 int lengths[MAXLEN];
00279 int longer = 0;
00280 #ifdef STATISTICS
00281 long hits = 0;
00282 long seeks = 0;
00283 #endif
00284
00285 chain_avg = tabp->numsyms / tabp->size;
00286 memset (lengths, 0, sizeof(lengths));
00287
00288 for (i = 0; i < tabp->size; i++) {
00289 chain_len = 0;
00290 for (p = tabp->table[i]; p; p = p->next) {
00291 #ifdef STATISTICS
00292 hits += p->hits;
00293 seeks += p->seeks;
00294 #endif
00295 chain_len++;
00296 }
00297
00298 if (chain_len >= MAXLEN)
00299 longer++;
00300 else
00301 ++lengths[chain_len];
00302
00303 if (minlen > chain_len) minlen = chain_len;
00304 if (maxlen < chain_len) maxlen = chain_len;
00305
00306 deviation += abs (chain_len - chain_avg);
00307 }
00308
00309 printf ("%d entries in %d element hash table, ",
00310 tabp->numsyms, tabp->size);
00311 printf ("%d (%1.0f%%) empty.\n",
00312 lengths[0], ((double)lengths[0] / tabp->size) * 100.0);
00313 printf ("Mean chain length = %d, min = %d, max = %d, dev = %d\n",
00314 chain_avg, minlen, maxlen, deviation / tabp->size);
00315 #ifdef STATISTICS
00316 printf ("Table searchs = %ld, found = %ld, percent = %.2f\n", seeks, hits,
00317 (seeks ? (double)hits / seeks * 100.0 : (double)0));
00318 #endif
00319
00320 for (i = 0; i < MAXLEN; i++)
00321 if (lengths[i])
00322 printf ("%3d chains of length %d\n", lengths[i], i);
00323
00324 if (longer)
00325 printf ("%3d chains of length %d or longer\n", longer, MAXLEN);
00326 }
00327