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