Robust/src/Runtime/SimpleHash.c

   1 #include "SimpleHash.h"
   2 #ifdef MULTICORE
   3 #include "methodheaders.h"
   4 #include "multicore_arch.h"
   5 #include "runtime_arch.h"
   6 #else
   7 #include <stdio.h>
   8 #endif
   9 #ifdef DMALLOC
  10 #include "dmalloc.h"
  11 #endif
  12
  13 /* SIMPLE HASH ********************************************************/
  14 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
  15   return allocateRuntimeIterator(thisvar->listhead);
  16 }
  17
  18 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
  19   it->cur=thisvar->listhead;
  20 }
  21
  22 struct RuntimeHash * noargallocateRuntimeHash() {
  23   return allocateRuntimeHash(100);
  24 }
  25
  26 struct RuntimeHash * allocateRuntimeHash(int size) {
  27   struct RuntimeHash *thisvar;
  28   if (size <= 0) {
  29 #ifdef MULTICORE
  30     BAMBOO_EXIT();
  31 #else
  32     printf("Negative Hashtable size Exception\n");
  33     exit(-1);
  34 #endif
  35   }
  36   thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
  37   thisvar->size = size;
  38   thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
  39   /* Set allocation blocks*/
  40   thisvar->listhead=NULL;
  41   thisvar->listtail=NULL;
  42   /*Set data counts*/
  43   thisvar->numelements = 0;
  44   return thisvar;
  45 }
  46
  47 void freeRuntimeHash(struct RuntimeHash *thisvar) {
  48   struct RuntimeNode *ptr=thisvar->listhead;
  49   RUNFREE(thisvar->bucket);
  50   while(ptr) {
  51     struct RuntimeNode *next=ptr->lnext;
  52     RUNFREE(ptr);
  53     ptr=next;
  54   }
  55   RUNFREE(thisvar);
  56 }
  57
  58 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
  59   return thisvar->numelements;
  60 }
  61
  62 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
  63   struct RuntimeNode *ptr=thisvar->listhead;
  64   return ptr->key;
  65 }
  66
  67 int RuntimeHashremovekey(struct RuntimeHash *thisvar, int key) {
  68   unsigned int hashkey = (unsigned int)key % thisvar->size;
  69
  70   struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
  71
  72   while (*ptr) {
  73     if ((*ptr)->key == key) {
  74       struct RuntimeNode *toremove=*ptr;
  75       *ptr=(*ptr)->next;
  76
  77       if (toremove->lprev!=NULL) {
  78         toremove->lprev->lnext=toremove->lnext;
  79       } else {
  80         thisvar->listhead=toremove->lnext;
  81       }
  82       if (toremove->lnext!=NULL) {
  83         toremove->lnext->lprev=toremove->lprev;
  84       } else {
  85         thisvar->listtail=toremove->lprev;
  86       }
  87       RUNFREE(toremove);
  88
  89       thisvar->numelements--;
  90       return 1;
  91     }
  92     ptr = &((*ptr)->next);
  93   }
  94
  95   return 0;
  96 }
  97
  98 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
  99   unsigned int hashkey = (unsigned int)key % thisvar->size;
 100
 101   struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
 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 MULTICORE
 209 struct RuntimeHash * allocateRuntimeHash_I(int size) {
 210   struct RuntimeHash *thisvar;
 211   if (size <= 0) {
 212 #ifdef MULTICORE
 213     BAMBOO_EXIT();
 214 #else
 215     printf("Negative Hashtable size Exception\n");
 216     exit(-1);
 217 #endif
 218   }
 219   thisvar=(struct RuntimeHash *)RUNMALLOC_I(sizeof(struct RuntimeHash));
 220   thisvar->size = size;
 221   thisvar->bucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*size);
 222   /* Set allocation blocks*/
 223   thisvar->listhead=NULL;
 224   thisvar->listtail=NULL;
 225   /*Set data counts*/
 226   thisvar->numelements = 0;
 227   return thisvar;
 228 }
 229
 230 int RuntimeHashadd_I(struct RuntimeHash * thisvar,int key, int data) {
 231   /* Rehash code */
 232   unsigned int hashkey;
 233   struct RuntimeNode **ptr;
 234
 235   if (thisvar->numelements>=thisvar->size) {
 236     int newsize=2*thisvar->size+1;
 237     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*newsize);
 238     int i;
 239     for(i=thisvar->size-1; i>=0; i--) {
 240       struct RuntimeNode *ptr;
 241       for(ptr=thisvar->bucket[i]; ptr!=NULL; ) {
 242         struct RuntimeNode * nextptr=ptr->next;
 243         unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 244         ptr->next=newbucket[newhashkey];
 245         newbucket[newhashkey]=ptr;
 246         ptr=nextptr;
 247       }
 248     }
 249     thisvar->size=newsize;
 250     RUNFREE_I(thisvar->bucket);
 251     thisvar->bucket=newbucket;
 252   }
 253
 254   hashkey = (unsigned int)key % thisvar->size;
 255   ptr = &thisvar->bucket[hashkey];
 256
 257   /* check that thisvar key/object pair isn't already here */
 258   /* TBD can be optimized for set v. relation */
 259
 260   while (*ptr) {
 261     if ((*ptr)->key == key && (*ptr)->data == data) {
 262       return 0;
 263     }
 264     ptr = &((*ptr)->next);
 265   }
 266
 267   {
 268     struct RuntimeNode *node=RUNMALLOC_I(sizeof(struct RuntimeNode));
 269     node->data=data;
 270     node->key=key;
 271     node->next=(*ptr);
 272     *ptr=node;
 273     if (thisvar->listhead==NULL) {
 274       thisvar->listhead=node;
 275       thisvar->listtail=node;
 276       node->lnext=NULL;
 277       node->lprev=NULL;
 278     } else {
 279       node->lprev=NULL;
 280       node->lnext=thisvar->listhead;
 281       thisvar->listhead->lprev=node;
 282       thisvar->listhead=node;
 283     }
 284   }
 285
 286   thisvar->numelements++;
 287   return 1;
 288 }
 289 #endif
 290
 291 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
 292   unsigned int hashkey = (unsigned int)key % thisvar->size;
 293
 294   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 295   while (ptr) {
 296     if (ptr->key == key) {
 297       /* we already have thisvar object
 298          stored in the hash so just return */
 299       return true;
 300     }
 301     ptr = ptr->next;
 302   }
 303   return false;
 304 }
 305
 306 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
 307   unsigned int hashkey = (unsigned int)key % thisvar->size;
 308
 309   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 310   while (ptr) {
 311     if (ptr->key == key && ptr->data == data) {
 312       /* we already have thisvar object
 313          stored in the hash so just return*/
 314       return true;
 315     }
 316     ptr = ptr->next;
 317   }
 318   return false;
 319 }
 320
 321 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
 322   unsigned int hashkey = (unsigned int)key % thisvar->size;
 323   int count = 0;
 324
 325   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 326   while (ptr) {
 327     if (ptr->key == key) {
 328       count++;
 329     }
 330     ptr = ptr->next;
 331   }
 332   return count;
 333 }
 334
 335 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
 336   struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
 337   unsigned int hashkey = (unsigned int)key % thisvar->size;
 338
 339   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 340   while (ptr) {
 341     if (ptr->key == key) {
 342       RuntimeHashadd(newset,ptr->data,ptr->data);
 343     }
 344     ptr = ptr->next;
 345   }
 346   return newset;
 347 }
 348
 349 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
 350   unsigned int hashkey = (unsigned int)key % thisvar->size;
 351
 352   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 353   while (ptr) {
 354     if (ptr->key == key) {
 355       *data = ptr->data;
 356       return 1;       /* success */
 357     }
 358     ptr = ptr->next;
 359   }
 360
 361   return 0;   /* failure */
 362 }
 363
 364 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
 365   return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 366 }
 367
 368 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
 369   struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 370   thisvar->cur = start;
 371   return thisvar;
 372 }
 373
 374 inline int RunhasNext(struct RuntimeIterator *thisvar) {
 375   return (thisvar->cur!=NULL);
 376 }
 377
 378 inline int Runnext(struct RuntimeIterator *thisvar) {
 379   int curr=thisvar->cur->data;
 380   thisvar->cur=thisvar->cur->lnext;
 381   return curr;
 382 }
 383
 384 inline int Runkey(struct RuntimeIterator *thisvar) {
 385   return thisvar->cur->key;
 386 }