00001
00002
00003 #include "cddefines.h"
00004 #include "hash.h"
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 static unsigned long hashfunction(const void *t, const size_t len);
00020
00021
00022 static entry *lookup_key(const void *key, size_t *lkey, const hashtab *table,
00023 unsigned long *hk);
00024 static void extend(hashtab *table);
00025 static unsigned long getbin(unsigned long hk, const hashtab *table);
00026
00027
00028 hashtab *newhash(void (*freedata)(void *))
00029 {
00030 hashtab *self;
00031
00032 DEBUG_ENTRY("newhash()");
00033
00034 self = (hashtab *) MALLOC(sizeof(hashtab));
00035 self->freedata = freedata;
00036 self->nelem = 0;
00037 self->size = 0x1;
00038 self->fullmask = 0x1;
00039 self->frontmask = 0x0;
00040 self->space = 128;
00041 self->hashfunction = hashfunction;
00042 self->tab = (entry **) MALLOC(self->space*sizeof(entry *));
00043 self->tab[0] = NULL;
00044
00045 DEBUG_EXIT("newhash()");
00046
00047 return self;
00048 }
00049
00050 void freehash(hashtab *table)
00051 {
00052 entry *s, *t;
00053 unsigned long i;
00054
00055 DEBUG_ENTRY("freehash()");
00056
00057 for(i=0;i<table->size;i++)
00058 {
00059 s = table->tab[i];
00060 while (s != NULL)
00061 {
00062 t = s->next;
00063 if(table->freedata != NULL)
00064 {
00065 table->freedata(s->data.p);
00066 }
00067 free(s);
00068 s = t;
00069 }
00070 }
00071
00072 free(table->tab);
00073 free(table);
00074 DEBUG_EXIT("freehash()");
00075 }
00076
00077 data_u *addentry(const void *key, size_t lkey, hashtab *table, int *exists)
00078 {
00079 unsigned long hk, i;
00080 entry *s;
00081 void *p;
00082
00083 DEBUG_ENTRY("addentry()");
00084
00085 s = lookup_key(key,&lkey,table,&hk);
00086 if(s)
00087 {
00088 *exists = 1;
00089 DEBUG_EXIT("addentry()");
00090 return &(s->data);
00091 }
00092
00093 *exists = 0;
00094 p = MALLOC(sizeof(entry)+lkey);
00095 s = (entry *) p;
00096 s->hashval = hk;
00097 s->data.lkey = lkey;
00098 s->data.key = (void *)(((char *)p)+sizeof(entry));
00099 memcpy(s->data.key,key,lkey);
00100
00101 i = getbin(hk,table);
00102 s->next = table->tab[i];
00103 table->tab[i] = s;
00104
00105 table->nelem++;
00106
00107 extend(table);
00108
00109 DEBUG_EXIT("addentry()");
00110
00111 return &(s->data);
00112 }
00113
00114 data_u *lookup(const void *key, size_t lkey, const hashtab *table)
00115 {
00116 unsigned long hk;
00117 entry *s;
00118
00119 if(table->nelem == 0)
00120 return NULL;
00121 s = lookup_key(key,&lkey,table,&hk);
00122 if(s == NULL)
00123 return NULL;
00124 return &(s->data);
00125 }
00126
00127 int maxchain(const hashtab *table)
00128 {
00129 unsigned long i, l, max=0;
00130 entry *s;
00131
00132 DEBUG_ENTRY("maxchain()");
00133
00134 for(i=0;i<table->size;i++)
00135 {
00136 l = 0;
00137 for(s = table->tab[i];s != NULL;s=s->next)
00138 {
00139 l++;
00140 }
00141 if(l > max)
00142 max = l;
00143 }
00144
00145 DEBUG_EXIT("maxchain()");
00146
00147 return max;
00148 }
00149
00150
00151
00152
00153
00154
00155 enum {HASHINIT=5381,HASHMUL=33};
00156
00157 static unsigned long hashfunction(const void *t, const size_t len)
00158 {
00159 size_t i;
00160 unsigned long h = HASHINIT;
00161 unsigned char *s = (unsigned char *)t;
00162
00163 DEBUG_ENTRY("hashfunction()");
00164
00165 for( i=0; i<len; i++ )
00166 h = HASHMUL*h + s[i];
00167
00168 DEBUG_EXIT("hashfunction()");
00169
00170 return( h );
00171 }
00172
00173 static entry *lookup_key(const void *key, size_t *lkey, const hashtab *table,
00174 unsigned long *hk)
00175 {
00176 unsigned long i;
00177 entry *s;
00178
00179 DEBUG_ENTRY("lookup_key()");
00180
00181 if(*lkey == 0)
00182 *lkey = strlen((char *) key)+1;
00183
00184 *hk = table->hashfunction(key,*lkey);
00185 i = getbin(*hk,table);
00186
00187
00188 for(s = table->tab[i];s!=NULL;s=s->next)
00189 {
00190
00191 if(*hk == s->hashval &&
00192 *lkey == s->data.lkey &&
00193 !memcmp(key,s->data.key,*lkey))
00194 {
00195 DEBUG_EXIT("lookup_key()");
00196 return s;
00197 }
00198 }
00199
00200 DEBUG_EXIT("lookup_key()");
00201 return NULL;
00202 }
00203
00204 static void extend(hashtab *table)
00205 {
00206 unsigned long move, last, i, j;
00207 entry *t, *s;
00208
00209 DEBUG_ENTRY("extend()");
00210 last = table->size;
00211 table->size++;
00212 if(last > table->fullmask)
00213 {
00214 table->frontmask = table->fullmask;
00215 table->fullmask <<= 1;
00216 table->fullmask |= 1;
00217 if(table->fullmask+1 > table->space)
00218 {
00219 table->space = table->fullmask+1;
00220 table->tab = (entry **)
00221 REALLOC(table->tab,(table->space)*sizeof(entry *));
00222 }
00223 }
00224
00225
00226 i = last & table->frontmask;
00227 t = table->tab[i];
00228 table->tab[last] = table->tab[i] = NULL;
00229 move = table->frontmask ^ table->fullmask;
00230 while (t)
00231 {
00232 if(t->hashval & move)
00233 {
00234 j = last;
00235 }
00236 else
00237 {
00238 j = i;
00239 }
00240 s = t->next;
00241 t->next = table->tab[j];
00242 table->tab[j] = t;
00243 t = s;
00244 }
00245 DEBUG_EXIT("extend()");
00246 }
00247
00248 static unsigned long getbin(unsigned long hk, const hashtab *table)
00249 {
00250 unsigned long i;
00251
00252 DEBUG_ENTRY("getbin()");
00253 i = hk & table->fullmask;
00254 if(i >= table->size)
00255 i &= table->frontmask;
00256 assert (i < table->size && i < table->space);
00257 DEBUG_EXIT("getbin()");
00258 return i;
00259 }
00260
00261
00262
00263 unsigned long makelist(const hashtab *table, data_u **list,
00264 const unsigned long nlist, int (*maskfun)(data_u *dat))
00265 {
00266 unsigned long i, n;
00267 entry *s;
00268
00269 DEBUG_ENTRY("makelist()");
00270
00271 n = 0;
00272 for(i=0;i<table->size;i++)
00273 {
00274 for(s = table->tab[i];s != NULL;s = s->next)
00275 {
00276 if(maskfun == NULL || maskfun(&(s->data)))
00277 list[n++] = &(s->data);
00278 if(n > nlist)
00279 {
00280 fprintf(ioQQQ,"Too many list items for array provided in makelist\n");
00281 puts( "[Stop in makelist]" );
00282 cdEXIT(EXIT_FAILURE);
00283 }
00284 }
00285 }
00286 DEBUG_EXIT("makelist()");
00287 return n;
00288 }
00289 unsigned long makeplist(const hashtab *table, void **list,
00290 const unsigned long nlist, int (*maskfun)(data_u *dat))
00291 {
00292 unsigned long i, n;
00293 entry *s;
00294
00295 DEBUG_ENTRY("makeplist()");
00296 n = 0;
00297 for(i=0;i<table->size;i++)
00298 {
00299 for(s = table->tab[i];s != NULL;s = s->next)
00300 {
00301 if(maskfun == NULL || maskfun(&(s->data)))
00302 list[n++] = s->data.p;
00303 if(n > nlist)
00304 {
00305 fprintf(ioQQQ,"Too many list items for array provided in makeplist\n");
00306 puts( "[Stop in makelist]" );
00307 cdEXIT(EXIT_FAILURE);
00308 }
00309 }
00310 }
00311 DEBUG_EXIT("makeplist()");
00312 return n;
00313 }
00314
00315 #ifdef TEST
00316 main()
00317 {
00318 hashtab *table;
00319 data_u *data;
00320 int i, exists;
00321
00322 char strings[][15] = {"Hello","Goodbye","Thirteen","One",
00323 "Two","Three","Four","Five","Six",
00324 "Seven","Eight"};
00325
00326 table = newhash(NULL);
00327 for(i=0;i<sizeof(strings)/15;i++)
00328 {
00329 data = addentry(strings[i],0,table,&exists);
00330 data->i = i;
00331 }
00332
00333 for(i=0;i<sizeof(strings)/15;i++)
00334 {
00335 data = lookup(strings[i],0,table);
00336 if(data)
00337 {
00338 printf("Found data %d\n",data->i);
00339 }
00340 else
00341 {
00342 printf("Couldn't find data\n");
00343 }
00344 }
00345 data = lookup("Banana",0,table);
00346 if(data)
00347 {
00348 printf("Found data %d\n",data->i);
00349 }
00350 else
00351 {
00352 printf("Couldn't find data (as expected)\n");
00353 }
00354 printf("Longest chain is %d\n",maxchain(table));
00355 }
00356 #endif