Robust/src/Runtime/GenericHashtable.c

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