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

   1 #include "SimpleHash.h"
   2 #ifdef RAW
   3 #include <raw.h>
   4 #else
   5 #include <stdio.h>
   6 #endif
   7 #ifdef DMALLOC
   8 #include "dmalloc.h"
   9 #endif
  10
  11 /* SIMPLE HASH ********************************************************/
  12 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
  13   return allocateRuntimeIterator(thisvar->listhead);
  14 }
  15
  16 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
  17   it->cur=thisvar->listhead;
  18 }
  19
  20 struct RuntimeHash * noargallocateRuntimeHash() {
  21   return allocateRuntimeHash(100);
  22 }
  23
  24 struct RuntimeHash * allocateRuntimeHash(int size) {
  25   struct RuntimeHash *thisvar;  //=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
  26   if (size <= 0) {
  27 #ifdef RAW
  28     raw_test_done(0xb001);
  29 #else
  30     printf("Negative Hashtable size Exception\n");
  31     exit(-1);
  32 #endif
  33   }
  34   thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
  35   thisvar->size = size;
  36   thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
  37   /* Set allocation blocks*/
  38   thisvar->listhead=NULL;
  39   thisvar->listtail=NULL;
  40   /*Set data counts*/
  41   thisvar->numelements = 0;
  42   return thisvar;
  43 }
  44
  45 void freeRuntimeHash(struct RuntimeHash *thisvar) {
  46   struct RuntimeNode *ptr=thisvar->listhead;
  47   RUNFREE(thisvar->bucket);
  48   while(ptr) {
  49     struct RuntimeNode *next=ptr->lnext;
  50     RUNFREE(ptr);
  51     ptr=next;
  52   }
  53   RUNFREE(thisvar);
  54 }
  55
  56 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
  57   return thisvar->numelements;
  58 }
  59
  60 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
  61   struct RuntimeNode *ptr=thisvar->listhead;
  62   return ptr->key;
  63 }
  64
  65 int RuntimeHashremovekey(struct RuntimeHash *thisvar, int key) {
  66   unsigned int hashkey = (unsigned int)key % thisvar->size;
  67
  68   struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
  69   int i;
  70
  71   while (*ptr) {
  72     if ((*ptr)->key == key) {
  73       struct RuntimeNode *toremove=*ptr;
  74       *ptr=(*ptr)->next;
  75
  76       if (toremove->lprev!=NULL) {
  77         toremove->lprev->lnext=toremove->lnext;
  78       } else {
  79         thisvar->listhead=toremove->lnext;
  80       }
  81       if (toremove->lnext!=NULL) {
  82         toremove->lnext->lprev=toremove->lprev;
  83       } else {
  84         thisvar->listtail=toremove->lprev;
  85       }
  86       RUNFREE(toremove);
  87
  88       thisvar->numelements--;
  89       return 1;
  90     }
  91     ptr = &((*ptr)->next);
  92   }
  93
  94   return 0;
  95 }
  96
  97 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
  98   unsigned int hashkey = (unsigned int)key % thisvar->size;
  99
 100   struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
 101   int i;
 102
 103   while (*ptr) {
 104     if ((*ptr)->key == key && (*ptr)->data == data) {
 105       struct RuntimeNode *toremove=*ptr;
 106       *ptr=(*ptr)->next;
 107
 108       if (toremove->lprev!=NULL) {
 109         toremove->lprev->lnext=toremove->lnext;
 110       } else {
 111         thisvar->listhead=toremove->lnext;
 112       }
 113       if (toremove->lnext!=NULL) {
 114         toremove->lnext->lprev=toremove->lprev;
 115       } else {
 116         thisvar->listtail=toremove->lprev;
 117       }
 118       RUNFREE(toremove);
 119
 120       thisvar->numelements--;
 121       return 1;
 122     }
 123     ptr = &((*ptr)->next);
 124   }
 125
 126   return 0;
 127 }
 128
 129 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
 130   int newsize=thisvar->size;
 131   struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
 132   int i;
 133   for(i=thisvar->size-1; i>=0; i--) {
 134     struct RuntimeNode *ptr;
 135     for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
 136       struct RuntimeNode * nextptr=ptr->next;
 137       unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 138       ptr->next=newbucket[newhashkey];
 139       newbucket[newhashkey]=ptr;
 140       ptr=nextptr;
 141     }
 142   }
 143   thisvar->size=newsize;
 144   RUNFREE(thisvar->bucket);
 145   thisvar->bucket=newbucket;
 146 }
 147
 148 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
 149   /* Rehash code */
 150   unsigned int hashkey;
 151   struct RuntimeNode **ptr;
 152
 153   if (thisvar->numelements>=thisvar->size) {
 154     int newsize=2*thisvar->size+1;
 155     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
 156     int i;
 157     for(i=thisvar->size-1; i>=0; i--) {
 158       struct RuntimeNode *ptr;
 159       for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
 160         struct RuntimeNode * nextptr=ptr->next;
 161         unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 162         ptr->next=newbucket[newhashkey];
 163         newbucket[newhashkey]=ptr;
 164         ptr=nextptr;
 165       }
 166     }
 167     thisvar->size=newsize;
 168     RUNFREE(thisvar->bucket);
 169     thisvar->bucket=newbucket;
 170   }
 171
 172   hashkey = (unsigned int)key % thisvar->size;
 173   ptr = &thisvar->bucket[hashkey];
 174
 175   /* check that thisvar key/object pair isn't already here */
 176   /* TBD can be optimized for set v. relation */
 177
 178   while (*ptr) {
 179     if ((*ptr)->key == key && (*ptr)->data == data) {
 180       return 0;
 181     }
 182     ptr = &((*ptr)->next);
 183   }
 184
 185   {
 186     struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
 187     node->data=data;
 188     node->key=key;
 189     node->next=(*ptr);
 190     *ptr=node;
 191     if (thisvar->listhead==NULL) {
 192       thisvar->listhead=node;
 193       thisvar->listtail=node;
 194       node->lnext=NULL;
 195       node->lprev=NULL;
 196     } else {
 197       node->lprev=NULL;
 198       node->lnext=thisvar->listhead;
 199       thisvar->listhead->lprev=node;
 200       thisvar->listhead=node;
 201     }
 202   }
 203
 204   thisvar->numelements++;
 205   return 1;
 206 }
 207
 208 #ifdef RAW
 209 int RuntimeHashadd_I(struct RuntimeHash * thisvar,int key, int data) {
 210   /* Rehash code */
 211   unsigned int hashkey;
 212   struct RuntimeNode **ptr;
 213
 214   if (thisvar->numelements>=thisvar->size) {
 215     int newsize=2*thisvar->size+1;
 216     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*newsize);
 217     int i;
 218     for(i=thisvar->size-1; i>=0; i--) {
 219       struct RuntimeNode *ptr;
 220       for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
 221         struct RuntimeNode * nextptr=ptr->next;
 222         unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 223         ptr->next=newbucket[newhashkey];
 224         newbucket[newhashkey]=ptr;
 225         ptr=nextptr;
 226       }
 227     }
 228     thisvar->size=newsize;
 229     RUNFREE(thisvar->bucket);
 230     thisvar->bucket=newbucket;
 231   }
 232
 233   hashkey = (unsigned int)key % thisvar->size;
 234   ptr = &thisvar->bucket[hashkey];
 235
 236   /* check that thisvar key/object pair isn't already here */
 237   /* TBD can be optimized for set v. relation */
 238
 239   while (*ptr) {
 240     if ((*ptr)->key == key && (*ptr)->data == data) {
 241       return 0;
 242     }
 243     ptr = &((*ptr)->next);
 244   }
 245
 246   {
 247     struct RuntimeNode *node=RUNMALLOC_I(sizeof(struct RuntimeNode));
 248     node->data=data;
 249     node->key=key;
 250     node->next=(*ptr);
 251     *ptr=node;
 252     if (thisvar->listhead==NULL) {
 253       thisvar->listhead=node;
 254       thisvar->listtail=node;
 255       node->lnext=NULL;
 256       node->lprev=NULL;
 257     } else {
 258       node->lprev=NULL;
 259       node->lnext=thisvar->listhead;
 260       thisvar->listhead->lprev=node;
 261       thisvar->listhead=node;
 262     }
 263   }
 264
 265   thisvar->numelements++;
 266   return 1;
 267 }
 268 #endif
 269
 270 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
 271   unsigned int hashkey = (unsigned int)key % thisvar->size;
 272
 273   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 274   while (ptr) {
 275     if (ptr->key == key) {
 276       /* we already have thisvar object
 277          stored in the hash so just return */
 278       return true;
 279     }
 280     ptr = ptr->next;
 281   }
 282   return false;
 283 }
 284
 285 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
 286   unsigned int hashkey = (unsigned int)key % thisvar->size;
 287
 288   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 289   while (ptr) {
 290     if (ptr->key == key && ptr->data == data) {
 291       /* we already have thisvar object
 292          stored in the hash so just return*/
 293       return true;
 294     }
 295     ptr = ptr->next;
 296   }
 297   return false;
 298 }
 299
 300 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
 301   unsigned int hashkey = (unsigned int)key % thisvar->size;
 302   int count = 0;
 303
 304   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 305   while (ptr) {
 306     if (ptr->key == key) {
 307       count++;
 308     }
 309     ptr = ptr->next;
 310   }
 311   return count;
 312 }
 313
 314 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
 315   struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
 316   unsigned int hashkey = (unsigned int)key % thisvar->size;
 317
 318   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 319   while (ptr) {
 320     if (ptr->key == key) {
 321       RuntimeHashadd(newset,ptr->data,ptr->data);
 322     }
 323     ptr = ptr->next;
 324   }
 325   return newset;
 326 }
 327
 328 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
 329   unsigned int hashkey = (unsigned int)key % thisvar->size;
 330
 331   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 332   while (ptr) {
 333     if (ptr->key == key) {
 334       *data = ptr->data;
 335       return 1;       /* success */
 336     }
 337     ptr = ptr->next;
 338   }
 339
 340   return 0;   /* failure */
 341 }
 342
 343 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
 344   return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 345 }
 346
 347 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
 348   struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 349   thisvar->cur = start;
 350   return thisvar;
 351 }
 352
 353 inline int RunhasNext(struct RuntimeIterator *thisvar) {
 354   return (thisvar->cur!=NULL);
 355 }
 356
 357 inline int Runnext(struct RuntimeIterator *thisvar) {
 358   int curr=thisvar->cur->data;
 359   thisvar->cur=thisvar->cur->lnext;
 360   return curr;
 361 }
 362
 363 inline int Runkey(struct RuntimeIterator *thisvar) {
 364   return thisvar->cur->key;
 365 }