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