Robust/src/Runtime/GenericHashtable.c

   1 #ifdef RAW
   2 #include <raw.h>
   3 #else
   4 #include <stdio.h>
   5 #endif
   6 #include <sys/types.h>
   7 #include <sys/stat.h>
   8 #include <fcntl.h>
   9 #include <stdlib.h>
  10 #include <limits.h>
  11
  12 #include "GenericHashtable.h"
  13 #include "mem.h"
  14 #ifdef DMALLOC
  15 #include "dmalloc.h"
  16 #endif
  17
  18 void * getfirstkey(struct genhashtable *ht) {
  19         if(ht->list == NULL) {
  20                 return NULL;
  21         }
  22   return ht->list->src;
  23 }
  24
  25 int genputtable(struct genhashtable *ht, void * key, void * object) {
  26   unsigned int bin=genhashfunction(ht,key);
  27   struct genpointerlist * newptrlist=(struct genpointerlist *) RUNMALLOC(sizeof(struct genpointerlist));
  28   newptrlist->src=key;
  29   newptrlist->object=object;
  30   newptrlist->next=ht->bins[bin];
  31   newptrlist->inext=NULL;
  32   /* maintain linked list of ht entries for iteration*/
  33   if (ht->last==NULL) {
  34     ht->last=newptrlist;
  35     ht->list=newptrlist;
  36     newptrlist->iprev=NULL;
  37   } else {
  38     ht->last->inext=newptrlist;
  39     newptrlist->iprev=ht->last;
  40     ht->last=newptrlist;
  41   }
  42   ht->bins[bin]=newptrlist;
  43   ht->counter++;
  44   if(ht->counter>ht->currentsize&&ht->currentsize!=INT_MAX) {
  45     /* Expand hashtable */
  46     long newcurrentsize=(ht->currentsize<(INT_MAX/2))?ht->currentsize*2:INT_MAX;
  47     long oldcurrentsize=ht->currentsize;
  48     struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*newcurrentsize);
  49     struct genpointerlist **oldbins=ht->bins;
  50     long j,i;
  51     for(j=0;j<newcurrentsize;j++) newbins[j]=NULL;
  52     ht->currentsize=newcurrentsize;
  53     for(i=0;i<oldcurrentsize;i++) {
  54       struct genpointerlist * tmpptr=oldbins[i];
  55       while(tmpptr!=NULL) {
  56         unsigned int hashcode=genhashfunction(ht, tmpptr->src);
  57         struct genpointerlist *nextptr=tmpptr->next;
  58         tmpptr->next=newbins[hashcode];
  59         newbins[hashcode]=tmpptr;
  60         tmpptr=nextptr;
  61       }
  62     }
  63     ht->bins=newbins;
  64     RUNFREE(oldbins);
  65   }
  66   return 1;
  67 }
  68
  69 #ifdef RAW
  70 int genputtable_I(struct genhashtable *ht, void * key, void * object) {
  71   unsigned int bin=genhashfunction(ht,key);
  72   struct genpointerlist * newptrlist=(struct genpointerlist *) RUNMALLOC_I(sizeof(struct genpointerlist));
  73   newptrlist->src=key;
  74   newptrlist->object=object;
  75   newptrlist->next=ht->bins[bin];
  76   newptrlist->inext=NULL;
  77   /* maintain linked list of ht entries for iteration*/
  78   if (ht->last==NULL) {
  79     ht->last=newptrlist;
  80     ht->list=newptrlist;
  81     newptrlist->iprev=NULL;
  82   } else {
  83     ht->last->inext=newptrlist;
  84     newptrlist->iprev=ht->last;
  85     ht->last=newptrlist;
  86   }
  87   ht->bins[bin]=newptrlist;
  88   ht->counter++;
  89   if(ht->counter>ht->currentsize&&ht->currentsize!=INT_MAX) {
  90     /* Expand hashtable */
  91     long newcurrentsize=(ht->currentsize<(INT_MAX/2))?ht->currentsize*2:INT_MAX;
  92     long oldcurrentsize=ht->currentsize;
  93     struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC_I(sizeof (struct genpointerlist *)*newcurrentsize);
  94     struct genpointerlist **oldbins=ht->bins;
  95     long j,i;
  96     for(j=0;j<newcurrentsize;j++) newbins[j]=NULL;
  97     ht->currentsize=newcurrentsize;
  98     for(i=0;i<oldcurrentsize;i++) {
  99       struct genpointerlist * tmpptr=oldbins[i];
 100       while(tmpptr!=NULL) {
 101         unsigned int hashcode=genhashfunction(ht, tmpptr->src);
 102         struct genpointerlist *nextptr=tmpptr->next;
 103         tmpptr->next=newbins[hashcode];
 104         newbins[hashcode]=tmpptr;
 105         tmpptr=nextptr;
 106       }
 107     }
 108     ht->bins=newbins;
 109     RUNFREE(oldbins);
 110   }
 111   return 1;
 112 }
 113 #endif
 114
 115 int hashsize(struct genhashtable *ht) {
 116   return ht->counter;
 117 }
 118
 119 void genrehash(struct genhashtable * ht) {
 120   struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*ht->currentsize);
 121   struct genpointerlist **oldbins=ht->bins;
 122   long j,i;
 123
 124   for(i=0;i<ht->currentsize;i++) {
 125     struct genpointerlist * tmpptr=oldbins[i];
 126     while(tmpptr!=NULL) {
 127       unsigned int hashcode=genhashfunction(ht, tmpptr->src);
 128       struct genpointerlist *nextptr=tmpptr->next;
 129       tmpptr->next=newbins[hashcode];
 130       newbins[hashcode]=tmpptr;
 131       tmpptr=nextptr;
 132     }
 133   }
 134   ht->bins=newbins;
 135   RUNFREE(oldbins);
 136 }
 137
 138 void * gengettable(struct genhashtable *ht, void * key) {
 139   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
 140   while(ptr!=NULL) {
 141     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
 142       return ptr->object;
 143     ptr=ptr->next;
 144   }
 145 #ifndef RAW
 146   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
 147 #endif
 148   return NULL;
 149 }
 150
 151 void * getnext(struct genhashtable *ht, void * key) {
 152   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
 153   while(ptr!=NULL) {
 154     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
 155       if (ptr->inext!=NULL) {
 156         return ptr->inext->src;
 157       } else
 158         return NULL;
 159     ptr=ptr->next;
 160   }
 161 #ifndef RAW
 162   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p...\n Likely concurrent removal--bad user!!!\n",key);
 163 #endif
 164   return NULL;
 165 }
 166
 167 int gencontains(struct genhashtable *ht, void * key) {
 168   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
 169   //printf("In gencontains2\n");fflush(NULL);
 170   while(ptr!=NULL) {
 171     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
 172       return 1;
 173     ptr=ptr->next;
 174   }
 175   return 0;
 176 }
 177
 178
 179 void genfreekey(struct genhashtable *ht, void * key) {
 180   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
 181
 182   if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) {
 183     ht->bins[genhashfunction(ht,key)]=ptr->next;
 184
 185     if (ptr==ht->last)
 186       ht->last=ptr->iprev;
 187
 188     if (ptr==ht->list)
 189       ht->list=ptr->inext;
 190
 191     if (ptr->iprev!=NULL)
 192       ptr->iprev->inext=ptr->inext;
 193     if (ptr->inext!=NULL)
 194       ptr->inext->iprev=ptr->iprev;
 195
 196     RUNFREE(ptr);
 197     ht->counter--;
 198     return;
 199   }
 200   while(ptr->next!=NULL) {
 201     if (((ht->comp_function==NULL)&&(ptr->next->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->next->src,key))) {
 202       struct genpointerlist *tmpptr=ptr->next;
 203       ptr->next=tmpptr->next;
 204       if (tmpptr==ht->list)
 205         ht->list=tmpptr->inext;
 206       if (tmpptr==ht->last)
 207         ht->last=tmpptr->iprev;
 208       if (tmpptr->iprev!=NULL)
 209         tmpptr->iprev->inext=tmpptr->inext;
 210       if (tmpptr->inext!=NULL)
 211         tmpptr->inext->iprev=tmpptr->iprev;
 212       RUNFREE(tmpptr);
 213       ht->counter--;
 214       return;
 215     }
 216     ptr=ptr->next;
 217   }
 218 #ifndef RAW
 219   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
 220 #endif
 221 }
 222
 223 unsigned int genhashfunction(struct genhashtable *ht, void * key) {
 224   if (ht->hash_function==NULL)
 225     return ((long unsigned int)key) % ht->currentsize;
 226   else
 227     return ((*ht->hash_function)(key)) % ht->currentsize;
 228 }
 229
 230 struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *, void *)) {
 231   struct genhashtable *ght;
 232   struct genpointerlist **gpl;
 233   int i;
 234
 235 #ifdef RAWDEBUG
 236   raw_test_pass(0xf000);
 237 #endif
 238
 239   gpl=(struct genpointerlist **) RUNMALLOC(sizeof(struct genpointerlist *)*geninitialnumbins);
 240 #ifdef RAWDEBUG
 241   raw_test_pass(0xf001);
 242 #endif
 243   for(i=0;i<geninitialnumbins;i++) {
 244     gpl[i]=NULL;
 245   }
 246 #ifdef RAWDEBUG
 247   raw_test_pass(0xf002);
 248 #endif
 249   ght=(struct genhashtable *) RUNMALLOC(sizeof(struct genhashtable));
 250 #ifdef RAWDEBUG
 251   raw_test_pass(0xf003);
 252 #endif
 253   ght->hash_function=hash_function;
 254   ght->comp_function=comp_function;
 255   ght->currentsize=geninitialnumbins;
 256   ght->bins=gpl;
 257   ght->counter=0;
 258   ght->list=NULL;
 259   ght->last=NULL;
 260 #ifdef RAWDEBUG
 261   raw_test_pass(0xf004);
 262 #endif
 263   return ght;
 264 }
 265
 266 void genfreehashtable(struct genhashtable * ht) {
 267   int i;
 268   for (i=0;i<ht->currentsize;i++) {
 269     if (ht->bins[i]!=NULL) {
 270       struct genpointerlist *genptr=ht->bins[i];
 271       while(genptr!=NULL) {
 272         struct genpointerlist *tmpptr=genptr->next;
 273         RUNFREE(genptr);
 274         genptr=tmpptr;
 275       }
 276     }
 277   }
 278   RUNFREE(ht->bins);
 279   RUNFREE(ht);
 280 }
 281
 282 struct geniterator * gengetiterator(struct genhashtable *ht) {
 283   struct geniterator *gi=(struct geniterator*)RUNMALLOC(sizeof(struct geniterator));
 284   gi->ptr=ht->list;
 285   return gi;
 286 }
 287
 288 void * gennext(struct geniterator *it) {
 289   struct genpointerlist *curr=it->ptr;
 290   if (curr==NULL)
 291     return NULL;
 292   if (it->finished&&(curr->inext==NULL))
 293     return NULL;
 294   if (it->finished) {
 295     it->ptr=curr->inext;
 296     return it->ptr->src;
 297   }
 298   if(curr->inext!=NULL)
 299     it->ptr=curr->inext;
 300   else
 301     it->finished=1; /* change offsetting scheme */
 302   return curr->src;
 303 }
 304
 305 void genfreeiterator(struct geniterator *it) {
 306   RUNFREE(it);
 307 }