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