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

   1 #include "SimpleHash.h"
   2 #include <stdio.h>
   3 #ifdef DMALLOC
   4 #include "dmalloc.h"
   5 #endif
   6
   7 /* SIMPLE HASH ********************************************************/
   8 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
   9     return allocateRuntimeIterator(thisvar->listhead);
  10 }
  11
  12 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
  13   it->cur=thisvar->listhead;
  14 }
  15
  16 struct RuntimeHash * noargallocateRuntimeHash() {
  17     return allocateRuntimeHash(100);
  18 }
  19
  20 struct RuntimeHash * allocateRuntimeHash(int size) {
  21     struct RuntimeHash *thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
  22     if (size <= 0) {
  23         printf("Negative Hashtable size Exception\n");
  24         exit(-1);
  25     }
  26     thisvar->size = size;
  27     thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
  28     /* Set allocation blocks*/
  29     thisvar->listhead=NULL;
  30     thisvar->listtail=NULL;
  31     /*Set data counts*/
  32     thisvar->numelements = 0;
  33     return thisvar;
  34 }
  35
  36 void freeRuntimeHash(struct RuntimeHash *thisvar) {
  37     struct RuntimeNode *ptr=thisvar->listhead;
  38     RUNFREE(thisvar->bucket);
  39     while(ptr) {
  40         struct RuntimeNode *next=ptr->lnext;
  41         RUNFREE(ptr);
  42         ptr=next;
  43     }
  44     RUNFREE(thisvar);
  45 }
  46
  47 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
  48     return thisvar->numelements;
  49 }
  50
  51 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
  52   struct RuntimeNode *ptr=thisvar->listhead;
  53   return ptr->key;
  54 }
  55
  56 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
  57     unsigned int hashkey = (unsigned int)key % thisvar->size;
  58
  59     struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
  60     int i;
  61
  62     while (*ptr) {
  63         if ((*ptr)->key == key && (*ptr)->data == data) {
  64           struct RuntimeNode *toremove=*ptr;
  65           *ptr=(*ptr)->next;
  66
  67           if (toremove->lprev!=NULL)
  68             toremove->lprev->lnext=toremove->lnext;
  69           else
  70             thisvar->listhead=toremove->lnext;
  71           if (toremove->lnext!=NULL)
  72             toremove->lnext->lprev=toremove->lprev;
  73           else
  74             thisvar->listtail=toremove->lprev;
  75           RUNFREE(toremove);
  76
  77           thisvar->numelements--;
  78           return 1;
  79         }
  80         ptr = &((*ptr)->next);
  81     }
  82
  83     return 0;
  84 }
  85
  86 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
  87   int newsize=thisvar->size;
  88   struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
  89   int i;
  90   for(i=thisvar->size-1;i>=0;i--) {
  91     struct RuntimeNode *ptr;
  92     for(ptr=thisvar->bucket[i];ptr!=NULL;) {
  93       struct RuntimeNode * nextptr=ptr->next;
  94       unsigned int newhashkey=(unsigned int)ptr->key % newsize;
  95       ptr->next=newbucket[newhashkey];
  96       newbucket[newhashkey]=ptr;
  97       ptr=nextptr;
  98     }
  99   }
 100   thisvar->size=newsize;
 101   RUNFREE(thisvar->bucket);
 102   thisvar->bucket=newbucket;
 103 }
 104
 105 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
 106   /* Rehash code */
 107   unsigned int hashkey;
 108   struct RuntimeNode **ptr;
 109
 110   if (thisvar->numelements>=thisvar->size) {
 111     int newsize=2*thisvar->size+1;
 112     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
 113     int i;
 114     for(i=thisvar->size-1;i>=0;i--) {
 115         struct RuntimeNode *ptr;
 116         for(ptr=thisvar->bucket[i];ptr!=NULL;) {
 117             struct RuntimeNode * nextptr=ptr->next;
 118             unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 119             ptr->next=newbucket[newhashkey];
 120             newbucket[newhashkey]=ptr;
 121             ptr=nextptr;
 122         }
 123     }
 124     thisvar->size=newsize;
 125     RUNFREE(thisvar->bucket);
 126     thisvar->bucket=newbucket;
 127   }
 128
 129   hashkey = (unsigned int)key % thisvar->size;
 130   ptr = &thisvar->bucket[hashkey];
 131
 132   /* check that thisvar key/object pair isn't already here */
 133   /* TBD can be optimized for set v. relation */
 134
 135   while (*ptr) {
 136     if ((*ptr)->key == key && (*ptr)->data == data) {
 137       return 0;
 138     }
 139     ptr = &((*ptr)->next);
 140   }
 141
 142   {
 143     struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
 144     node->data=data;
 145     node->key=key;
 146     node->next=(*ptr);
 147     *ptr=node;
 148     if (thisvar->listhead==NULL) {
 149       thisvar->listhead=node;
 150       thisvar->listtail=node;
 151       node->lnext=NULL;
 152       node->lprev=NULL;
 153     } else {
 154       node->lprev=NULL;
 155       node->lnext=thisvar->listhead;
 156       thisvar->listhead->lprev=node;
 157       thisvar->listhead=node;
 158     }
 159   }
 160
 161   thisvar->numelements++;
 162   return 1;
 163 }
 164
 165 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
 166     unsigned int hashkey = (unsigned int)key % thisvar->size;
 167
 168     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 169     while (ptr) {
 170         if (ptr->key == key) {
 171             /* we already have thisvar object
 172                stored in the hash so just return */
 173             return true;
 174         }
 175         ptr = ptr->next;
 176     }
 177     return false;
 178 }
 179
 180 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
 181     unsigned int hashkey = (unsigned int)key % thisvar->size;
 182
 183     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 184     while (ptr) {
 185         if (ptr->key == key && ptr->data == data) {
 186             /* we already have thisvar object
 187                stored in the hash so just return*/
 188             return true;
 189         }
 190         ptr = ptr->next;
 191     }
 192     return false;
 193 }
 194
 195 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
 196     unsigned int hashkey = (unsigned int)key % thisvar->size;
 197     int count = 0;
 198
 199     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 200     while (ptr) {
 201         if (ptr->key == key) {
 202             count++;
 203         }
 204         ptr = ptr->next;
 205     }
 206     return count;
 207 }
 208
 209 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
 210   struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
 211   unsigned int hashkey = (unsigned int)key % thisvar->size;
 212
 213   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 214   while (ptr) {
 215     if (ptr->key == key) {
 216         RuntimeHashadd(newset,ptr->data,ptr->data);
 217     }
 218     ptr = ptr->next;
 219   }
 220   return newset;
 221 }
 222
 223 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
 224     unsigned int hashkey = (unsigned int)key % thisvar->size;
 225
 226     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 227     while (ptr) {
 228         if (ptr->key == key) {
 229             *data = ptr->data;
 230             return 1; /* success */
 231         }
 232         ptr = ptr->next;
 233     }
 234
 235     return 0; /* failure */
 236 }
 237
 238 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
 239     return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 240 }
 241
 242 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
 243     struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 244     thisvar->cur = start;
 245     return thisvar;
 246 }
 247
 248 inline int RunhasNext(struct RuntimeIterator *thisvar) {
 249   return (thisvar->cur!=NULL);
 250 }
 251
 252 inline int Runnext(struct RuntimeIterator *thisvar) {
 253   int curr=thisvar->cur->data;
 254   thisvar->cur=thisvar->cur->next;
 255 }
 256
 257 inline int Runkey(struct RuntimeIterator *thisvar) {
 258   return thisvar->cur->key;
 259 }