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