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