Robust/src/Runtime/bamboo/MGCHash.c

   1 #include "MGCHash.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 #define GC_SHIFT_BITS 4
  12
  13 /* mgchash ********************************************************/
  14 mgchashtable_t * mgchashCreate(unsigned int size, double loadfactor) {
  15   mgchashtable_t *ctable;
  16   mgchashlistnode_t *nodes;
  17   int i;
  18
  19   if (size <= 0) {
  20 #ifdef MULTICORE
  21     BAMBOO_EXIT();
  22 #else
  23     printf("Negative Hashtable size Exception\n");
  24     exit(-1);
  25 #endif
  26   }
  27
  28   // Allocate space for the hash table
  29   ctable = (mgchashtable_t *)RUNMALLOC(sizeof(mgchashtable_t));
  30   if(ctable == NULL) {
  31     // Run out of local memory
  32     BAMBOO_EXIT();
  33   }
  34   ctable->table = (mgchashlistnode_t*)RUNMALLOC(size*sizeof(mgchashlistnode_t));
  35   if(ctable->table == NULL) {
  36     // Run out of local memory
  37     BAMBOO_EXIT();
  38   }
  39   ctable->loadfactor = loadfactor;
  40   ctable->size = size;
  41   ctable->threshold=size*loadfactor;
  42
  43   ctable->mask = (size << (GC_SHIFT_BITS))-1;
  44   ctable->structs = (mgcliststruct_t*)RUNMALLOC(1*sizeof(mgcliststruct_t));
  45   ctable->numelements = 0; // Initial number of elements in the hash
  46
  47   return ctable;
  48 }
  49
  50 void mgchashreset(mgchashtable_t * tbl) {
  51   mgchashlistnode_t *ptr = tbl->table;
  52   int i;
  53
  54   /*if (tbl->numelements<(tbl->size>>6)) {
  55         mgchashlistnode_t *top=&ptr[tbl->size];
  56         mgchashlistnode_t * list = tbl->list;
  57         while(list != NULL) {
  58       mgchashlistnode_t * next = list->lnext;
  59       if ((list >= ptr) && (list < top)) {
  60                 //zero in list
  61         list->key=NULL;
  62         list->next=NULL;
  63       }
  64       list = next;
  65         }
  66   } else {*/
  67         BAMBOO_MEMSET_WH(tbl->table, '\0', sizeof(mgchashlistnode_t)*tbl->size);
  68   //}
  69   // TODO now never release any allocated memory, may need to be changed
  70   while(tbl->structs->next!=NULL) {
  71     mgcliststruct_t * next = tbl->structs->next;
  72     RUNFREE(tbl->structs);
  73     tbl->structs=next;
  74   }
  75   tbl->structs->num = 0;
  76   tbl->numelements = 0;
  77 }
  78
  79 //Store objects and their pointers into hash
  80 void mgchashInsert(mgchashtable_t * tbl, void * key, void *val) {
  81   mgchashlistnode_t *ptr;
  82
  83   if(tbl->numelements > (tbl->threshold)) {
  84     //Resize
  85     unsigned int newsize = tbl->size << 1 + 1;
  86     mgchashResize(tbl, newsize);
  87   }
  88
  89   ptr=&tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
  90   tbl->numelements++;
  91
  92   if(ptr->key==0) {
  93     // the first time insert a value for the key
  94     ptr->key=key;
  95     ptr->val=val;
  96   } else { // Insert in the beginning of linked list
  97     mgchashlistnode_t * node;
  98     if (tbl->structs->num<NUMMGCLIST) {
  99       node=&tbl->structs->array[tbl->structs->num];
 100       tbl->structs->num++;
 101     } else {
 102       //get new list
 103       mgcliststruct_t *tcl=RUNMALLOC(1*sizeof(mgcliststruct_t));
 104       tcl->next=tbl->structs;
 105       tbl->structs=tcl;
 106       node=&tcl->array[0];
 107       tcl->num=1;
 108     }
 109     node->key = key;
 110     node->val = val;
 111     node->next = ptr->next;
 112     ptr->next = node;
 113   }
 114 }
 115
 116 #ifdef MULTICORE_GC
 117 mgchashtable_t * mgchashCreate_I(unsigned int size, double loadfactor) {
 118   mgchashtable_t *ctable;
 119   mgchashlistnode_t *nodes;
 120   int i;
 121
 122   if (size <= 0) {
 123 #ifdef MULTICORE
 124     BAMBOO_EXIT();
 125 #else
 126     printf("Negative Hashtable size Exception\n");
 127     exit(-1);
 128 #endif
 129   }
 130
 131   // Allocate space for the hash table
 132   ctable = (mgchashtable_t*)RUNMALLOC_I(sizeof(mgchashtable_t));
 133   if(ctable == NULL) {
 134     // Run out of local memory
 135     BAMBOO_EXIT();
 136   }
 137   ctable->table=(mgchashlistnode_t*)RUNMALLOC_I(size*sizeof(mgchashlistnode_t));
 138   if(ctable->table == NULL) {
 139     // Run out of local memory
 140     BAMBOO_EXIT();
 141   }
 142   ctable->loadfactor = loadfactor;
 143   ctable->size = size;
 144   ctable->threshold=size*loadfactor;
 145
 146   ctable->mask = (size << (GC_SHIFT_BITS))-1;
 147   ctable->structs = (mgcliststruct_t*)RUNMALLOC_I(1*sizeof(mgcliststruct_t));
 148   ctable->numelements = 0; // Initial number of elements in the hash
 149
 150   return ctable;
 151 }
 152
 153 void mgchashInsert_I(mgchashtable_t * tbl, void * key, void *val) {
 154   mgchashlistnode_t *ptr;
 155
 156   if(tbl->numelements > (tbl->threshold)) {
 157     //Resize
 158     unsigned int newsize = tbl->size << 1 + 1;
 159     mgchashResize_I(tbl, newsize);
 160   }
 161
 162   ptr = &tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
 163   tbl->numelements++;
 164
 165   if(ptr->key==0) {
 166     ptr->key=key;
 167     ptr->val=val;
 168     return;
 169   } else { // Insert in the beginning of linked list
 170     mgchashlistnode_t * node;
 171     if (tbl->structs->num<NUMMGCLIST) {
 172       node=&tbl->structs->array[tbl->structs->num];
 173       tbl->structs->num++;
 174     } else {
 175       //get new list
 176       mgcliststruct_t *tcl=RUNMALLOC_I(1*sizeof(mgcliststruct_t));
 177       tcl->next=tbl->structs;
 178       tbl->structs=tcl;
 179       node=&tcl->array[0];
 180       tcl->num=1;
 181     }
 182     node->key = key;
 183     node->val = val;
 184     node->next = ptr->next;
 185     ptr->next = node;
 186   }
 187 }
 188 #endif
 189
 190 // Search for an address for a given oid
 191 INLINE void * mgchashSearch(mgchashtable_t * tbl, void * key) {
 192   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE]
 193   mgchashlistnode_t *node =
 194         &tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
 195
 196   do {
 197     if(node->key == key) {
 198       return node->val;
 199     }
 200     node = node->next;
 201   } while(node != NULL);
 202
 203   return NULL;
 204 }
 205
 206 unsigned int mgchashResize(mgchashtable_t * tbl, unsigned int newsize) {
 207   mgchashlistnode_t *node, *ptr, *curr;  // curr and next keep track of the
 208                                          // current and the next
 209                                                                                  // mgchashlistnodes in a linked list
 210   unsigned int oldsize;
 211   int isfirst;    // Keeps track of the first element in the
 212                   // chashlistnode_t for each bin in hashtable
 213   unsigned int i,index;
 214   unsigned int mask;
 215
 216   ptr = tbl->table;
 217   oldsize = tbl->size;
 218
 219   if((node = RUNMALLOC(newsize*sizeof(mgchashlistnode_t))) == NULL) {
 220     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 221     return 1;
 222   }
 223
 224   tbl->table = node; //Update the global hashtable upon resize()
 225   tbl->size = newsize;
 226   tbl->threshold = newsize * tbl->loadfactor;
 227   mask = tbl->mask = (newsize << (GC_SHIFT_BITS)) - 1;
 228
 229   for(i = 0; i < oldsize; i++) {   //Outer loop for each bin in hash table
 230     curr = &ptr[i];
 231     isfirst = 1;
 232     do {  //Inner loop to go through linked lists
 233       void * key;
 234       mgchashlistnode_t *tmp,*next;
 235
 236       if ((key=curr->key) == 0) {
 237                 //Exit inner loop if there the first element is 0
 238                 break;
 239                 //key = val =0 for element if not present within the hash table
 240           }
 241       index = (((unsigned INTPTR)key) & mask) >> (GC_SHIFT_BITS);
 242       tmp=&node[index];
 243       next = curr->next;
 244       // Insert into the new table
 245       if(tmp->key == 0) {
 246                 tmp->key = key;
 247                 tmp->val = curr->val;
 248       } /*
 249            NOTE:  Add this case if you change this...
 250            This case currently never happens because of the way things rehash....*/
 251            else if (isfirst) {
 252                  mgchashlistnode_t *newnode= RUNMALLOC(1*sizeof(mgchashlistnode_t));
 253                  newnode->key = curr->key;
 254                  newnode->val = curr->val;
 255                  newnode->next = tmp->next;
 256                  tmp->next=newnode;
 257            }
 258       else {
 259                 curr->next=tmp->next;
 260                 tmp->next=curr;
 261       }
 262
 263       isfirst = 0;
 264       curr = next;
 265     } while(curr!=NULL);
 266   }
 267
 268   RUNFREE(ptr);            //Free the memory of the old hash table
 269   return 0;
 270 }
 271
 272 #ifdef MULTICORE_GC
 273 unsigned int mgchashResize_I(mgchashtable_t * tbl, unsigned int newsize) {
 274   mgchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the
 275                                         // current and the next
 276                                                                                 // mgchashlistnodes in a linked list
 277   unsigned int oldsize;
 278   int isfirst; // Keeps track of the first element in the chashlistnode_t
 279                // for each bin in hashtable
 280   unsigned int i,index;
 281   unsigned int mask;
 282
 283   ptr = tbl->table;
 284   oldsize = tbl->size;
 285
 286   if((node = RUNMALLOC_I(newsize*sizeof(mgchashlistnode_t))) == NULL) {
 287     BAMBOO_EXIT();
 288     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 289     return 1;
 290   }
 291
 292   tbl->table = node;  //Update the global hashtable upon resize()
 293   tbl->size = newsize;
 294   tbl->threshold = newsize * tbl->loadfactor;
 295   mask = tbl->mask = (newsize << (GC_SHIFT_BITS))-1;
 296
 297   for(i = 0; i < oldsize; i++) {  //Outer loop for each bin in hash table
 298     curr = &ptr[i];
 299     isfirst = 1;
 300     do { //Inner loop to go through linked lists
 301       void * key;
 302       mgchashlistnode_t *tmp,*next;
 303
 304       if ((key=curr->key) == 0) {
 305         //Exit inner loop if there the first element is 0
 306         break;
 307         //key = val =0 for element if not present within the hash table
 308       }
 309       index = (((unsigned INTPTR)key) & mask) >> (GC_SHIFT_BITS);
 310       tmp=&node[index];
 311       next = curr->next;
 312       // Insert into the new table
 313       if(tmp->key == 0) {
 314         tmp->key = key;
 315         tmp->val = curr->val;
 316       } /*
 317            NOTE:  Add this case if you change this...
 318            This case currently never happens because of the way things rehash....*/
 319       else if (isfirst) {
 320         mgchashlistnode_t *newnode=RUNMALLOC_I(1*sizeof(mgchashlistnode_t));
 321         newnode->key = curr->key;
 322         newnode->val = curr->val;
 323         newnode->next = tmp->next;
 324         tmp->next=newnode;
 325       } else {
 326         curr->next=tmp->next;
 327         tmp->next=curr;
 328       }
 329
 330       isfirst = 0;
 331       curr = next;
 332     } while(curr!=NULL);
 333   }
 334   RUNFREE_I(ptr); //Free the memory of the old hash table
 335   return 0;
 336 }
 337 #endif
 338
 339 //Delete the entire hash table
 340 void mgchashDelete(mgchashtable_t * tbl) {
 341   int i;
 342   mgcliststruct_t *ptr=tbl->structs;
 343   while(ptr!=NULL) {
 344     mgcliststruct_t *next=ptr->next;
 345     RUNFREE(ptr);
 346     ptr=next;
 347   }
 348   RUNFREE(tbl->table);
 349   tbl->table=NULL;
 350   tbl->structs=NULL;
 351 }
 352
 353 /* MGCHASH ********************************************************/
 354
 355 struct MGCHash * allocateMGCHash(int size,
 356                                  int conflicts) {
 357   struct MGCHash *thisvar;
 358   if (size <= 0) {
 359 #ifdef MULTICORE
 360     BAMBOO_EXIT();
 361 #else
 362     printf("Negative Hashtable size Exception\n");
 363     exit(-1);
 364 #endif
 365   }
 366   thisvar=(struct MGCHash *)RUNMALLOC(sizeof(struct MGCHash));
 367   thisvar->size = size;
 368   thisvar->bucket =
 369     (struct MGCNode *) RUNMALLOC(sizeof(struct MGCNode)*size);
 370   //Set data counts
 371   thisvar->num4conflicts = conflicts;
 372   return thisvar;
 373 }
 374
 375 void freeMGCHash(struct MGCHash *thisvar) {
 376   int i = 0;
 377   for(i=thisvar->size-1; i>=0; i--) {
 378     struct MGCNode *ptr;
 379     for(ptr=thisvar->bucket[i].next; ptr!=NULL; ) {
 380       struct MGCNode * nextptr=ptr->next;
 381       RUNFREE(ptr);
 382       ptr=nextptr;
 383     }
 384   }
 385   RUNFREE(thisvar->bucket);
 386   RUNFREE(thisvar);
 387 }
 388
 389 int MGCHashadd(struct MGCHash * thisvar, int data) {
 390   // Rehash code
 391   unsigned int hashkey;
 392   struct MGCNode *ptr;
 393
 394   int mask = (thisvar->size << (GC_SHIFT_BITS))-1;
 395   hashkey = (((unsigned INTPTR)data)&mask)>>(GC_SHIFT_BITS);
 396   ptr = &thisvar->bucket[hashkey];
 397
 398   struct MGCNode * prev = NULL;
 399   if(ptr->data < thisvar->num4conflicts) {
 400     struct MGCNode *node=RUNMALLOC(sizeof(struct MGCNode));
 401     node->data=data;
 402     node->next=(ptr->next);
 403     ptr->next=node;
 404     ptr->data++;
 405   } else {
 406     while (ptr->next!=NULL) {
 407       prev = ptr;
 408       ptr = ptr->next;
 409     }
 410     ptr->data = data;
 411     ptr->next = thisvar->bucket[hashkey].next;
 412     thisvar->bucket[hashkey].next = ptr;
 413     prev->next = NULL;
 414   }
 415
 416   return 1;
 417 }
 418
 419 #ifdef MULTICORE
 420 struct MGCHash * allocateMGCHash_I(int size,
 421                                    int conflicts) {
 422   struct MGCHash *thisvar;
 423   if (size <= 0) {
 424 #ifdef MULTICORE
 425     BAMBOO_EXIT();
 426 #else
 427     printf("Negative Hashtable size Exception\n");
 428     exit(-1);
 429 #endif
 430   }
 431   thisvar=(struct MGCHash *)RUNMALLOC_I(sizeof(struct MGCHash));
 432   thisvar->size = size;
 433   thisvar->bucket =
 434     (struct MGCNode *) RUNMALLOC_I(sizeof(struct MGCNode)*size);
 435   //Set data counts
 436   thisvar->num4conflicts = conflicts;
 437   return thisvar;
 438 }
 439
 440 int MGCHashadd_I(struct MGCHash * thisvar, int data) {
 441   // Rehash code
 442   unsigned int hashkey;
 443   struct MGCNode *ptr;
 444
 445   int mask = (thisvar->size << (GC_SHIFT_BITS))-1;
 446   hashkey = (((unsigned INTPTR)data)&mask)>>(GC_SHIFT_BITS);
 447   ptr = &thisvar->bucket[hashkey];
 448
 449   struct MGCNode * prev = NULL;
 450   if(ptr->data < thisvar->num4conflicts) {
 451     struct MGCNode *node=RUNMALLOC_I(sizeof(struct MGCNode));
 452     node->data=data;
 453     node->next=(ptr->next);
 454     ptr->next=node;
 455     ptr->data++;
 456   } else {
 457     while (ptr->next!=NULL) {
 458       prev = ptr;
 459       ptr = ptr->next;
 460     }
 461     ptr->data = data;
 462     ptr->next = thisvar->bucket[hashkey].next;
 463     thisvar->bucket[hashkey].next = ptr;
 464     prev->next = NULL;
 465   }
 466
 467   return 1;
 468 }
 469 #endif
 470
 471 int MGCHashcontains(struct MGCHash *thisvar, int data) {
 472   int mask = (thisvar->size << (GC_SHIFT_BITS))-1;
 473   unsigned int hashkey = (((unsigned INTPTR)data)&mask)>>(GC_SHIFT_BITS);
 474
 475   struct MGCNode *ptr = thisvar->bucket[hashkey].next;
 476   struct MGCNode *prev = NULL;
 477   while (ptr!=NULL) {
 478     if (ptr->data == data) {
 479       if(prev != NULL) {
 480         prev->next = NULL;
 481         ptr->next = thisvar->bucket[hashkey].next;
 482         thisvar->bucket[hashkey].next = ptr;
 483       }
 484
 485       return 1;       // success
 486     }
 487     prev = ptr;
 488     ptr = ptr->next;
 489   }
 490
 491   return 0;   // failure
 492 }
 493