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