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 * gengettable(struct genhashtable *ht, void * key) {
  62   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
  63   while(ptr!=NULL) {
  64     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
  65       return ptr->object;
  66     ptr=ptr->next;
  67   }
  68   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
  69   return NULL;
  70 }
  71
  72 void * getnext(struct genhashtable *ht, void * key) {
  73   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
  74   while(ptr!=NULL) {
  75     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
  76       if (ptr->inext!=NULL) {
  77         return ptr->inext->src;
  78       } else
  79         return NULL;
  80     ptr=ptr->next;
  81   }
  82   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p...\n Likely concurrent removal--bad user!!!\n",key);
  83   return NULL;
  84 }
  85
  86 int gencontains(struct genhashtable *ht, void * key) {
  87   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
  88   //printf("In gencontains2\n");fflush(NULL);
  89   while(ptr!=NULL) {
  90     if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
  91       return 1;
  92     ptr=ptr->next;
  93   }
  94   return 0;
  95 }
  96
  97
  98 void genfreekey(struct genhashtable *ht, void * key) {
  99   struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
 100
 101   if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) {
 102     ht->bins[genhashfunction(ht,key)]=ptr->next;
 103
 104     if (ptr==ht->last)
 105       ht->last=ptr->iprev;
 106
 107     if (ptr==ht->list)
 108       ht->list=ptr->inext;
 109
 110     if (ptr->iprev!=NULL)
 111       ptr->iprev->inext=ptr->inext;
 112     if (ptr->inext!=NULL)
 113       ptr->inext->iprev=ptr->iprev;
 114
 115     RUNFREE(ptr);
 116     ht->counter--;
 117     return;
 118   }
 119   while(ptr->next!=NULL) {
 120     if (((ht->comp_function==NULL)&&(ptr->next->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->next->src,key))) {
 121       struct genpointerlist *tmpptr=ptr->next;
 122       ptr->next=tmpptr->next;
 123       if (tmpptr==ht->list)
 124         ht->list=tmpptr->inext;
 125       if (tmpptr==ht->last)
 126         ht->last=tmpptr->iprev;
 127       if (tmpptr->iprev!=NULL)
 128         tmpptr->iprev->inext=tmpptr->inext;
 129       if (tmpptr->inext!=NULL)
 130         tmpptr->inext->iprev=tmpptr->iprev;
 131       RUNFREE(tmpptr);
 132       ht->counter--;
 133       return;
 134     }
 135     ptr=ptr->next;
 136   }
 137   printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
 138 }
 139
 140 unsigned int genhashfunction(struct genhashtable *ht, void * key) {
 141   if (ht->hash_function==NULL)
 142     return ((long unsigned int)key) % ht->currentsize;
 143   else
 144     return ((*ht->hash_function)(key)) % ht->currentsize;
 145 }
 146
 147 struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *, void *)) {
 148   struct genhashtable *ght=(struct genhashtable *) RUNMALLOC(sizeof(struct genhashtable));
 149   struct genpointerlist **gpl=(struct genpointerlist **) RUNMALLOC(sizeof(struct genpointerlist *)*geninitialnumbins);
 150   int i;
 151   for(i=0;i<geninitialnumbins;i++)
 152     gpl[i]=NULL;
 153   ght->hash_function=hash_function;
 154   ght->comp_function=comp_function;
 155   ght->currentsize=geninitialnumbins;
 156   ght->bins=gpl;
 157   ght->counter=0;
 158   ght->list=NULL;
 159   ght->last=NULL;
 160   return ght;
 161 }
 162
 163 void genfreehashtable(struct genhashtable * ht) {
 164   int i;
 165   for (i=0;i<ht->currentsize;i++) {
 166     if (ht->bins[i]!=NULL) {
 167       struct genpointerlist *genptr=ht->bins[i];
 168       while(genptr!=NULL) {
 169         struct genpointerlist *tmpptr=genptr->next;
 170         RUNFREE(genptr);
 171         genptr=tmpptr;
 172       }
 173     }
 174   }
 175   RUNFREE(ht->bins);
 176   RUNFREE(ht);
 177 }
 178
 179 struct geniterator * gengetiterator(struct genhashtable *ht) {
 180   struct geniterator *gi=(struct geniterator*)RUNMALLOC(sizeof(struct geniterator));
 181   gi->ptr=ht->list;
 182   return gi;
 183 }
 184
 185 void * gennext(struct geniterator *it) {
 186   struct genpointerlist *curr=it->ptr;
 187   if (curr==NULL)
 188     return NULL;
 189   if (it->finished&&(curr->inext==NULL))
 190     return NULL;
 191   if (it->finished) {
 192     it->ptr=curr->inext;
 193     return it->ptr->src;
 194   }
 195   if(curr->inext!=NULL)
 196     it->ptr=curr->inext;
 197   else
 198     it->finished=1; /* change offsetting scheme */
 199   return curr->src;
 200 }
 201
 202 void genfreeiterator(struct geniterator *it) {
 203   RUNFREE(it);
 204 }