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_GC
 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       } else {
 289         curr->next=tmp->next;
 290         tmp->next=curr;
 291       }
 292
 293       isfirst = 0;
 294       curr = next;
 295     } while(curr!=NULL);
 296   }
 297   RUNFREE(ptr);            //Free the memory of the old hash table
 298   return 0;
 299 }
 300 #endif
 301
 302 //Delete the entire hash table
 303 void mgchashDelete() {
 304   int i;
 305   mgcliststruct_t *ptr=mgc_structs;
 306   while(ptr!=NULL) {
 307     mgcliststruct_t *next=ptr->next;
 308     RUNFREE(ptr);
 309     ptr=next;
 310   }
 311   RUNFREE(mgc_table);
 312   mgc_table=NULL;
 313   mgc_structs=NULL;
 314 }
 315
 316 struct MGCHash * allocateMGCHash(int size,
 317                                  int conflicts) {
 318   struct MGCHash *thisvar;
 319   if (size <= 0) {
 320 #ifdef MULTICORE
 321     BAMBOO_EXIT(0xf101);
 322 #else
 323     printf("Negative Hashtable size Exception\n");
 324     exit(-1);
 325 #endif
 326   }
 327   thisvar=(struct MGCHash *)RUNMALLOC(sizeof(struct MGCHash));
 328   thisvar->size = size;
 329   thisvar->bucket =
 330     (struct MGCNode *) RUNMALLOC(sizeof(struct MGCNode)*size);
 331   //Set data counts
 332   thisvar->num4conflicts = conflicts;
 333   return thisvar;
 334 }
 335
 336 void freeMGCHash(struct MGCHash *thisvar) {
 337   int i = 0;
 338   for(i=thisvar->size-1; i>=0; i--) {
 339     struct MGCNode *ptr;
 340     for(ptr=thisvar->bucket[i].next; ptr!=NULL; ) {
 341       struct MGCNode * nextptr=ptr->next;
 342       RUNFREE(ptr);
 343       ptr=nextptr;
 344     }
 345   }
 346   RUNFREE(thisvar->bucket);
 347   RUNFREE(thisvar);
 348 }
 349
 350 int MGCHashadd(struct MGCHash * thisvar, int data) {
 351   // Rehash code
 352   unsigned int hashkey;
 353   struct MGCNode *ptr;
 354
 355   hashkey = (unsigned int)data % thisvar->size;
 356   ptr = &thisvar->bucket[hashkey];
 357
 358   struct MGCNode * prev = NULL;
 359   if(ptr->data < thisvar->num4conflicts) {
 360     struct MGCNode *node=RUNMALLOC(sizeof(struct MGCNode));
 361     node->data=data;
 362     node->next=(ptr->next);
 363     ptr->next=node;
 364     ptr->data++;
 365   } else {
 366     while (ptr->next!=NULL) {
 367       prev = ptr;
 368       ptr = ptr->next;
 369     }
 370     ptr->data = data;
 371     ptr->next = thisvar->bucket[hashkey].next;
 372     thisvar->bucket[hashkey].next = ptr;
 373     prev->next = NULL;
 374   }
 375
 376   return 1;
 377 }
 378
 379 #ifdef MULTICORE
 380 struct MGCHash * allocateMGCHash_I(int size,
 381                                    int conflicts) {
 382   struct MGCHash *thisvar;
 383   if (size <= 0) {
 384 #ifdef MULTICORE
 385     BAMBOO_EXIT(0xf101);
 386 #else
 387     printf("Negative Hashtable size Exception\n");
 388     exit(-1);
 389 #endif
 390   }
 391   thisvar=(struct MGCHash *)RUNMALLOC_I(sizeof(struct MGCHash));
 392   thisvar->size = size;
 393   thisvar->bucket =
 394     (struct MGCNode *) RUNMALLOC_I(sizeof(struct MGCNode)*size);
 395   //Set data counts
 396   thisvar->num4conflicts = conflicts;
 397   return thisvar;
 398 }
 399
 400 int MGCHashadd_I(struct MGCHash * thisvar, int data) {
 401   // Rehash code
 402   unsigned int hashkey;
 403   struct MGCNode *ptr;
 404
 405   hashkey = (unsigned int)data % thisvar->size;
 406   ptr = &thisvar->bucket[hashkey];
 407
 408   struct MGCNode * prev = NULL;
 409   if(ptr->data < thisvar->num4conflicts) {
 410     struct MGCNode *node=RUNMALLOC_I(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 #endif
 429
 430 int MGCHashcontains(struct MGCHash *thisvar, int data) {
 431   unsigned int hashkey = (unsigned int)data % thisvar->size;
 432
 433   struct MGCNode *ptr = thisvar->bucket[hashkey].next;
 434   struct MGCNode *prev = NULL;
 435   while (ptr!=NULL) {
 436     if (ptr->data == data) {
 437       if(prev != NULL) {
 438         prev->next = NULL;
 439         ptr->next = thisvar->bucket[hashkey].next;
 440         thisvar->bucket[hashkey].next = ptr;
 441       }
 442
 443       return 1;       // success
 444     }
 445     prev = ptr;
 446     ptr = ptr->next;
 447   }
 448
 449   return 0;   // failure
 450 }
 451