Repair/RepairCompiler/structextract/GenericHashtable.c

   1 #include <stdio.h>
   2 #include <sys/types.h>
   3 #include <sys/stat.h>
   4 #include <fcntl.h>
   5 #include <stdlib.h>
   6 #include <values.h>
   7 #include "GenericHashtable.h"
   8 //#include "dmalloc.h"
   9
  10 int genputtable(struct genhashtable *ht, void * key, void * object) {
  11   unsigned int bin=genhashfunction(ht,key);
  12   struct genpointerlist * newptrlist=(struct genpointerlist *) calloc(1,sizeof(struct genpointerlist));
  13   newptrlist->src=key;
  14   newptrlist->object=object;
  15   newptrlist->next=ht->bins[bin];
  16   newptrlist->inext=NULL;
  17   /* maintain linked list of ht entries for iteration*/
  18   if (ht->last==NULL) {
  19     ht->last=newptrlist;
  20     ht->list=newptrlist;
  21     newptrlist->iprev=NULL;
  22   } else {
  23     ht->last->inext=newptrlist;
  24     newptrlist->iprev=ht->last;
  25     ht->last=newptrlist;
  26   }
  27   ht->bins[bin]=newptrlist;
  28   ht->counter++;
  29   if(ht->counter>ht->currentsize&&ht->currentsize!=MAXINT) {
  30     /* Expand hashtable */
  31     long newcurrentsize=(ht->currentsize<(MAXINT/2))?ht->currentsize*2:MAXINT;
  32     long oldcurrentsize=ht->currentsize;
  33     struct genpointerlist **newbins=(struct genpointerlist **) calloc(1,sizeof (struct genpointerlist *)*newcurrentsize);
  34     struct genpointerlist **oldbins=ht->bins;
  35     long j,i;
  36     for(j=0;j<newcurrentsize;j++) newbins[j]=NULL;
  37     ht->currentsize=newcurrentsize;
  38     for(i=0;i<oldcurrentsize;i++) {
  39       struct genpointerlist * tmpptr=oldbins[i];
  40       while(tmpptr!=NULL) {
  41         int hashcode=genhashfunction(ht, tmpptr->src);
  42         struct genpointerlist *nextptr=tmpptr->next;
  43         tmpptr->next=newbins[hashcode];
  44         newbins[hashcode]=tmpptr;
  45         tmpptr=nextptr;
  46       }
  47     }
  48     ht->bins=newbins;
  49     free(oldbins);
  50   }
  51   return 1;
  52 }
  53
  54 int hashsize(struct genhashtable *ht) {
  55   return ht->counter;
  56 }
  57
  58 void * gengettable(struct genhashtable *ht, void * key) {
  59   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
  60   while(ptr!=NULL) {
  61     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
  62       return ptr->object;
  63     ptr=ptr->next;
  64   }
  65   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
  66   return NULL;
  67 }
  68
  69 void * getnext(struct genhashtable *ht, void * key) {
  70   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
  71   while(ptr!=NULL) {
  72     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
  73       if (ptr->inext!=NULL) {
  74         return ptr->inext->src;
  75       } else
  76         return NULL;
  77     ptr=ptr->next;
  78   }
  79   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p...\n Likely concurrent removal--bad user!!!\n",key);
  80   return NULL;
  81 }
  82
  83 int gencontains(struct genhashtable *ht, void * key) {
  84   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
  85   //printf("In gencontains2\n");fflush(NULL);
  86   while(ptr!=NULL) {
  87     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
  88       return 1;
  89     ptr=ptr->next;
  90   }
  91   return 0;
  92 }
  93
  94
  95 void genfreekey(struct genhashtable *ht, void * key) {
  96   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
  97
  98   if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) {
  99     ht->bins[genhashfunction(ht,key)]=ptr->next;
 100
 101     if (ptr==ht->last)
 102       ht->last=ptr->iprev;
 103
 104     if (ptr==ht->list)
 105       ht->list=ptr->inext;
 106
 107     if (ptr->iprev!=NULL)
 108       ptr->iprev->inext=ptr->inext;
 109     if (ptr->inext!=NULL)
 110       ptr->inext->iprev=ptr->iprev;
 111
 112     free(ptr);
 113     ht->counter--;
 114     return;
 115   }
 116   while(ptr->next!=NULL) {
 117     if (((ht->comp_function==NULL)&&(ptr->next->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->next->src,key))) {
 118       struct genpointerlist *tmpptr=ptr->next;
 119       ptr->next=tmpptr->next;
 120       if (tmpptr==ht->list)
 121         ht->list=tmpptr->inext;
 122       if (tmpptr==ht->last)
 123         ht->last=tmpptr->iprev;
 124       if (tmpptr->iprev!=NULL)
 125         tmpptr->iprev->inext=tmpptr->inext;
 126       if (tmpptr->inext!=NULL)
 127         tmpptr->inext->iprev=tmpptr->iprev;
 128       free(tmpptr);
 129       ht->counter--;
 130       return;
 131     }
 132     ptr=ptr->next;
 133   }
 134   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
 135 }
 136
 137 unsigned int genhashfunction(struct genhashtable *ht, void * key) {
 138   if (ht->hash_function==NULL)
 139     return ((long unsigned int)key) % ht->currentsize;
 140   else
 141     return ((*ht->hash_function)(key)) % ht->currentsize;
 142 }
 143
 144 struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *, void *)) {
 145   struct genhashtable *ght=(struct genhashtable *) calloc(1,sizeof(struct genhashtable));
 146   struct genpointerlist **gpl=(struct genpointerlist **) calloc(1,sizeof(struct genpointerlist *)*geninitialnumbins);
 147   int i;
 148   for(i=0;i<geninitialnumbins;i++)
 149     gpl[i]=NULL;
 150   ght->hash_function=hash_function;
 151   ght->comp_function=comp_function;
 152   ght->currentsize=geninitialnumbins;
 153   ght->bins=gpl;
 154   ght->counter=0;
 155   ght->list=NULL;
 156   ght->last=NULL;
 157   return ght;
 158 }
 159
 160 void genfreehashtable(struct genhashtable * ht) {
 161   int i;
 162   for (i=0;i<ht->currentsize;i++) {
 163     if (ht->bins[i]!=NULL) {
 164       struct genpointerlist *genptr=ht->bins[i];
 165       while(genptr!=NULL) {
 166         struct genpointerlist *tmpptr=genptr->next;
 167         free(genptr);
 168         genptr=tmpptr;
 169       }
 170     }
 171   }
 172   free(ht->bins);
 173   free(ht);
 174 }
 175
 176 struct geniterator * gengetiterator(struct genhashtable *ht) {
 177   struct geniterator *gi=(struct geniterator*)calloc(1,sizeof(struct geniterator));
 178   gi->ptr=ht->list;
 179   return gi;
 180 }
 181
 182 void * gennext(struct geniterator *it) {
 183   struct genpointerlist *curr=it->ptr;
 184   if (curr==NULL)
 185     return NULL;
 186   if (it->finished&&(curr->inext==NULL))
 187     return NULL;
 188   if (it->finished) {
 189     it->ptr=curr->inext;
 190     return it->ptr->src;
 191   }
 192   if(curr->inext!=NULL)
 193     it->ptr=curr->inext;
 194   else
 195     it->finished=1; /* change offsetting scheme */
 196   return curr->src;
 197 }
 198
 199 void genfreeiterator(struct geniterator *it) {
 200   free(it);
 201 }