Robust/src/Runtime/SimpleHash.c

   1 #include "SimpleHash.h"
   2 #ifdef MULTICORE
   3 #include "runtime_arch.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 MULTICORE
  28     BAMBOO_EXIT(0xf101);
  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
  70   while (*ptr) {
  71     if ((*ptr)->key == key) {
  72       struct RuntimeNode *toremove=*ptr;
  73       *ptr=(*ptr)->next;
  74
  75       if (toremove->lprev!=NULL) {
  76         toremove->lprev->lnext=toremove->lnext;
  77       } else {
  78         thisvar->listhead=toremove->lnext;
  79       }
  80       if (toremove->lnext!=NULL) {
  81         toremove->lnext->lprev=toremove->lprev;
  82       } else {
  83         thisvar->listtail=toremove->lprev;
  84       }
  85       RUNFREE(toremove);
  86
  87       thisvar->numelements--;
  88       return 1;
  89     }
  90     ptr = &((*ptr)->next);
  91   }
  92
  93   return 0;
  94 }
  95
  96 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
  97   unsigned int hashkey = (unsigned int)key % thisvar->size;
  98
  99   struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
 100
 101   while (*ptr) {
 102     if ((*ptr)->key == key && (*ptr)->data == data) {
 103       struct RuntimeNode *toremove=*ptr;
 104       *ptr=(*ptr)->next;
 105
 106       if (toremove->lprev!=NULL) {
 107         toremove->lprev->lnext=toremove->lnext;
 108       } else {
 109         thisvar->listhead=toremove->lnext;
 110       }
 111       if (toremove->lnext!=NULL) {
 112         toremove->lnext->lprev=toremove->lprev;
 113       } else {
 114         thisvar->listtail=toremove->lprev;
 115       }
 116       RUNFREE(toremove);
 117
 118       thisvar->numelements--;
 119       return 1;
 120     }
 121     ptr = &((*ptr)->next);
 122   }
 123
 124   return 0;
 125 }
 126
 127 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
 128   int newsize=thisvar->size;
 129   struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
 130   int i;
 131   for(i=thisvar->size-1; i>=0; i--) {
 132     struct RuntimeNode *ptr;
 133     for(ptr=thisvar->bucket[i]; ptr!=NULL; ) {
 134       struct RuntimeNode * nextptr=ptr->next;
 135       unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 136       ptr->next=newbucket[newhashkey];
 137       newbucket[newhashkey]=ptr;
 138       ptr=nextptr;
 139     }
 140   }
 141   thisvar->size=newsize;
 142   RUNFREE(thisvar->bucket);
 143   thisvar->bucket=newbucket;
 144 }
 145
 146 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
 147   /* Rehash code */
 148   unsigned int hashkey;
 149   struct RuntimeNode **ptr;
 150
 151   if (thisvar->numelements>=thisvar->size) {
 152     int newsize=2*thisvar->size+1;
 153     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
 154     int i;
 155     for(i=thisvar->size-1; i>=0; i--) {
 156       struct RuntimeNode *ptr;
 157       for(ptr=thisvar->bucket[i]; ptr!=NULL; ) {
 158         struct RuntimeNode * nextptr=ptr->next;
 159         unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 160         ptr->next=newbucket[newhashkey];
 161         newbucket[newhashkey]=ptr;
 162         ptr=nextptr;
 163       }
 164     }
 165     thisvar->size=newsize;
 166     RUNFREE(thisvar->bucket);
 167     thisvar->bucket=newbucket;
 168   }
 169
 170   hashkey = (unsigned int)key % thisvar->size;
 171   ptr = &thisvar->bucket[hashkey];
 172
 173   /* check that thisvar key/object pair isn't already here */
 174   /* TBD can be optimized for set v. relation */
 175
 176   while (*ptr) {
 177     if ((*ptr)->key == key && (*ptr)->data == data) {
 178       return 0;
 179     }
 180     ptr = &((*ptr)->next);
 181   }
 182
 183   {
 184     struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
 185     node->data=data;
 186     node->key=key;
 187     node->next=(*ptr);
 188     *ptr=node;
 189     if (thisvar->listhead==NULL) {
 190       thisvar->listhead=node;
 191       thisvar->listtail=node;
 192       node->lnext=NULL;
 193       node->lprev=NULL;
 194     } else {
 195       node->lprev=NULL;
 196       node->lnext=thisvar->listhead;
 197       thisvar->listhead->lprev=node;
 198       thisvar->listhead=node;
 199     }
 200   }
 201
 202   thisvar->numelements++;
 203   return 1;
 204 }
 205
 206 #ifdef MULTICORE
 207 struct RuntimeHash * allocateRuntimeHash_I(int size) {
 208   struct RuntimeHash *thisvar;  //=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
 209   if (size <= 0) {
 210 #ifdef MULTICORE
 211     BAMBOO_EXIT(0xf101);
 212 #else
 213     printf("Negative Hashtable size Exception\n");
 214     exit(-1);
 215 #endif
 216   }
 217   thisvar=(struct RuntimeHash *)RUNMALLOC_I(sizeof(struct RuntimeHash));
 218   thisvar->size = size;
 219   thisvar->bucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*size);
 220   /* Set allocation blocks*/
 221   thisvar->listhead=NULL;
 222   thisvar->listtail=NULL;
 223   /*Set data counts*/
 224   thisvar->numelements = 0;
 225   return thisvar;
 226 }
 227
 228 int RuntimeHashadd_I(struct RuntimeHash * thisvar,int key, int data) {
 229   /* Rehash code */
 230   unsigned int hashkey;
 231   struct RuntimeNode **ptr;
 232
 233   if (thisvar->numelements>=thisvar->size) {
 234     int newsize=2*thisvar->size+1;
 235     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*newsize);
 236     int i;
 237     for(i=thisvar->size-1; i>=0; i--) {
 238       struct RuntimeNode *ptr;
 239       for(ptr=thisvar->bucket[i]; ptr!=NULL; ) {
 240         struct RuntimeNode * nextptr=ptr->next;
 241         unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 242         ptr->next=newbucket[newhashkey];
 243         newbucket[newhashkey]=ptr;
 244         ptr=nextptr;
 245       }
 246     }
 247     thisvar->size=newsize;
 248     RUNFREE(thisvar->bucket);
 249     thisvar->bucket=newbucket;
 250   }
 251
 252   hashkey = (unsigned int)key % thisvar->size;
 253   ptr = &thisvar->bucket[hashkey];
 254
 255   /* check that thisvar key/object pair isn't already here */
 256   /* TBD can be optimized for set v. relation */
 257
 258   while (*ptr) {
 259     if ((*ptr)->key == key && (*ptr)->data == data) {
 260       return 0;
 261     }
 262     ptr = &((*ptr)->next);
 263   }
 264
 265   {
 266     struct RuntimeNode *node=RUNMALLOC_I(sizeof(struct RuntimeNode));
 267     node->data=data;
 268     node->key=key;
 269     node->next=(*ptr);
 270     *ptr=node;
 271     if (thisvar->listhead==NULL) {
 272       thisvar->listhead=node;
 273       thisvar->listtail=node;
 274       node->lnext=NULL;
 275       node->lprev=NULL;
 276     } else {
 277       node->lprev=NULL;
 278       node->lnext=thisvar->listhead;
 279       thisvar->listhead->lprev=node;
 280       thisvar->listhead=node;
 281     }
 282   }
 283
 284   thisvar->numelements++;
 285   return 1;
 286 }
 287 #endif
 288
 289 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
 290   unsigned int hashkey = (unsigned int)key % thisvar->size;
 291
 292   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 293   while (ptr) {
 294     if (ptr->key == key) {
 295       /* we already have thisvar object
 296          stored in the hash so just return */
 297       return true;
 298     }
 299     ptr = ptr->next;
 300   }
 301   return false;
 302 }
 303
 304 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
 305   unsigned int hashkey = (unsigned int)key % thisvar->size;
 306
 307   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 308   while (ptr) {
 309     if (ptr->key == key && ptr->data == data) {
 310       /* we already have thisvar object
 311          stored in the hash so just return*/
 312       return true;
 313     }
 314     ptr = ptr->next;
 315   }
 316   return false;
 317 }
 318
 319 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
 320   unsigned int hashkey = (unsigned int)key % thisvar->size;
 321   int count = 0;
 322
 323   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 324   while (ptr) {
 325     if (ptr->key == key) {
 326       count++;
 327     }
 328     ptr = ptr->next;
 329   }
 330   return count;
 331 }
 332
 333 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
 334   struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
 335   unsigned int hashkey = (unsigned int)key % thisvar->size;
 336
 337   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 338   while (ptr) {
 339     if (ptr->key == key) {
 340       RuntimeHashadd(newset,ptr->data,ptr->data);
 341     }
 342     ptr = ptr->next;
 343   }
 344   return newset;
 345 }
 346
 347 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
 348   unsigned int hashkey = (unsigned int)key % thisvar->size;
 349
 350   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 351   while (ptr) {
 352     if (ptr->key == key) {
 353       *data = ptr->data;
 354       return 1;       /* success */
 355     }
 356     ptr = ptr->next;
 357   }
 358
 359   return 0;   /* failure */
 360 }
 361
 362 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
 363   return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 364 }
 365
 366 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
 367   struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 368   thisvar->cur = start;
 369   return thisvar;
 370 }
 371
 372 inline int RunhasNext(struct RuntimeIterator *thisvar) {
 373   return (thisvar->cur!=NULL);
 374 }
 375
 376 inline int Runnext(struct RuntimeIterator *thisvar) {
 377   int curr=thisvar->cur->data;
 378   thisvar->cur=thisvar->cur->lnext;
 379   return curr;
 380 }
 381
 382 inline int Runkey(struct RuntimeIterator *thisvar) {
 383   return thisvar->cur->key;
 384 }