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