Programming Languages Research Group: Git - IRC.git/blob

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