Robust/src/Runtime/bamboo/GCSharedHash.c

   1 #ifdef MULTICORE_GC
   2
   3 #include "GCSharedHash.h"
   4 #ifdef MULTICORE
   5 #include "runtime_arch.h"
   6 #else
   7 #include <stdio.h>
   8 #endif
   9
  10 #define GC_SHIFT_BITS  4
  11
  12 /* GCSHARED HASH ********************************************************/
  13
  14 // params: startaddr -- the start addr of the shared memory
  15 //         rsize -- remaining size of the available shared memory
  16 struct GCSharedHash * noargallocateGCSharedHash() {
  17   return allocateGCSharedHash(100);
  18 }
  19
  20 struct GCSharedHash * allocateGCSharedHash(int size) {
  21   struct GCSharedHash *thisvar;
  22   if (size <= 0) {
  23 #ifdef MULTICORE
  24     BAMBOO_EXIT();
  25 #else
  26     printf("Negative Hashtable size Exception\n");
  27     exit(-1);
  28 #endif
  29   }
  30   thisvar=(struct GCSharedHash *)FREEMALLOC_NGC(sizeof(struct GCSharedHash));
  31   if(thisvar == NULL) {
  32         return NULL;
  33   }
  34   thisvar->size = size;
  35   thisvar->bucket =
  36         (struct GCSharedNode **)FREEMALLOC_NGC(sizeof(struct GCSharedNode *)*size);
  37   if(thisvar->bucket == NULL) {
  38         FREE_NGC(thisvar);
  39         return NULL;
  40   }
  41   /* Set allocation blocks*/
  42   thisvar->listhead=NULL;
  43   thisvar->listtail=NULL;
  44   /*Set data counts*/
  45   thisvar->numelements = 0;
  46   return thisvar;
  47 }
  48
  49 void freeGCSharedHash(struct GCSharedHash *thisvar) {
  50   struct GCSharedNode *ptr=thisvar->listhead;
  51   FREE_NGC(thisvar->bucket);
  52   while(ptr) {
  53     struct GCSharedNode *next=ptr->lnext;
  54     FREE_NGC(ptr);
  55     ptr=next;
  56   }
  57   FREE_NGC(thisvar);
  58 }
  59
  60 bool GCSharedHashrehash(struct GCSharedHash * thisvar) {
  61   int newsize=thisvar->size;
  62   struct GCSharedNode ** newbucket = (struct GCSharedNode **)
  63         FREEMALLOC_NGC(sizeof(struct GCSharedNode *)*newsize);
  64   if(newbucket == NULL) {
  65         return false;
  66   }
  67   int i;
  68   for(i=thisvar->size-1; i>=0; i--) {
  69     struct GCSharedNode *ptr;
  70     for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
  71       struct GCSharedNode * nextptr=ptr->next;
  72       unsigned int newhashkey=(unsigned int)ptr->key % newsize;
  73       ptr->next=newbucket[newhashkey];
  74       newbucket[newhashkey]=ptr;
  75       ptr=nextptr;
  76     }
  77   }
  78   thisvar->size=newsize;
  79   FREE_NGC(thisvar->bucket);
  80   thisvar->bucket=newbucket;
  81   return true;
  82 }
  83
  84 int GCSharedHashadd(struct GCSharedHash * thisvar,int key, int data) {
  85   /* Rehash code */
  86   unsigned int hashkey;
  87   struct GCSharedNode **ptr;
  88
  89   if (thisvar->numelements>=thisvar->size) {
  90     int newsize=2*thisvar->size+1;
  91     struct GCSharedNode ** newbucket =
  92           (struct GCSharedNode **)FREEMALLOC_NGC(
  93                   sizeof(struct GCSharedNode *)*newsize);
  94         if(newbucket == NULL) {
  95           return -1;
  96         }
  97     int i;
  98     for(i=thisvar->size-1; i>=0; i--) {
  99       struct GCSharedNode *ptr;
 100       for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
 101         struct GCSharedNode * nextptr=ptr->next;
 102         unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 103         ptr->next=newbucket[newhashkey];
 104         newbucket[newhashkey]=ptr;
 105         ptr=nextptr;
 106       }
 107     }
 108     thisvar->size=newsize;
 109     FREE_NGC(thisvar->bucket);
 110     thisvar->bucket=newbucket;
 111   }
 112
 113   hashkey = (unsigned int)key % thisvar->size;
 114   ptr = &thisvar->bucket[hashkey];
 115
 116   /* check that thisvar key/object pair isn't already here */
 117   /* TBD can be optimized for set v. relation */
 118
 119   while (*ptr) {
 120     if ((*ptr)->key == key && (*ptr)->data == data) {
 121       return 0;
 122     }
 123     ptr = &((*ptr)->next);
 124   }
 125
 126   {
 127     struct GCSharedNode *node=FREEMALLOC_NGC(sizeof(struct GCSharedNode));
 128         if(node == NULL) {
 129           return -1;
 130         }
 131     node->data=data;
 132     node->key=key;
 133     node->next=(*ptr);
 134     *ptr=node;
 135     if (thisvar->listhead==NULL) {
 136       thisvar->listhead=node;
 137       thisvar->listtail=node;
 138       node->lnext=NULL;
 139       node->lprev=NULL;
 140     } else {
 141       node->lprev=NULL;
 142       node->lnext=thisvar->listhead;
 143       thisvar->listhead->lprev=node;
 144       thisvar->listhead=node;
 145     }
 146   }
 147
 148   thisvar->numelements++;
 149   return 1;
 150 }
 151
 152 #ifdef MULTICORE
 153 struct GCSharedHash * allocateGCSharedHash_I(int size) {
 154   struct GCSharedHash *thisvar;
 155   if (size <= 0) {
 156 #ifdef MULTICORE
 157     BAMBOO_EXIT();
 158 #else
 159     printf("Negative Hashtable size Exception\n");
 160     exit(-1);
 161 #endif
 162   }
 163   thisvar=(struct GCSharedHash *)FREEMALLOC_NGC_I(sizeof(struct GCSharedHash));
 164   if(thisvar == NULL) {
 165         return NULL;
 166   }
 167   thisvar->size = size;
 168   thisvar->bucket =
 169         (struct GCSharedNode **)FREEMALLOC_NGC_I(
 170                 sizeof(struct GCSharedNode *)*size);
 171   if(thisvar->bucket == NULL) {
 172         FREE_NGC_I(thisvar);
 173         return NULL;
 174   }
 175   /* Set allocation blocks*/
 176   thisvar->listhead=NULL;
 177   thisvar->listtail=NULL;
 178   /*Set data counts*/
 179   thisvar->numelements = 0;
 180   return thisvar;
 181 }
 182
 183 int GCSharedHashadd_I(struct GCSharedHash * thisvar,int key, int data) {
 184   /* Rehash code */
 185   unsigned int hashkey;
 186   struct GCSharedNode **ptr;
 187
 188   if (thisvar->numelements>=thisvar->size) {
 189     int newsize=2*thisvar->size+1;
 190     struct GCSharedNode ** newbucket =
 191           (struct GCSharedNode **)FREEMALLOC_NGC_I(
 192                   sizeof(struct GCSharedNode *)*newsize);
 193         if(newbucket == NULL) {
 194           return -1;
 195         }
 196     int i;
 197     for(i=thisvar->size-1; i>=0; i--) {
 198       struct GCSharedNode *ptr;
 199       for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
 200         struct GCSharedNode * nextptr=ptr->next;
 201         unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 202         ptr->next=newbucket[newhashkey];
 203         newbucket[newhashkey]=ptr;
 204         ptr=nextptr;
 205       }
 206     }
 207     thisvar->size=newsize;
 208     FREE_NGC_I(thisvar->bucket);
 209     thisvar->bucket=newbucket;
 210   }
 211
 212   hashkey = (unsigned int)key % thisvar->size;
 213   ptr = &thisvar->bucket[hashkey];
 214
 215   /* check that thisvar key/object pair isn't already here */
 216   /* TBD can be optimized for set v. relation */
 217
 218   while (*ptr) {
 219     if ((*ptr)->key == key && (*ptr)->data == data) {
 220       return 0;
 221     }
 222     ptr = &((*ptr)->next);
 223   }
 224
 225   {
 226     struct GCSharedNode *node=FREEMALLOC_NGC_I(sizeof(struct GCSharedNode));
 227         if(node == NULL) {
 228           return -1;
 229         }
 230     node->data=data;
 231     node->key=key;
 232     node->next=(*ptr);
 233     *ptr=node;
 234     if (thisvar->listhead==NULL) {
 235       thisvar->listhead=node;
 236       thisvar->listtail=node;
 237       node->lnext=NULL;
 238       node->lprev=NULL;
 239     } else {
 240       node->lprev=NULL;
 241       node->lnext=thisvar->listhead;
 242       thisvar->listhead->lprev=node;
 243       thisvar->listhead=node;
 244     }
 245   }
 246
 247   thisvar->numelements++;
 248   return 1;
 249 }
 250 #endif
 251
 252 int GCSharedHashget(struct GCSharedHash *thisvar, int key, int *data) {
 253   unsigned int hashkey = (unsigned int)key % thisvar->size;
 254
 255   struct GCSharedNode *ptr = thisvar->bucket[hashkey];
 256   while (ptr) {
 257     if (ptr->key == key) {
 258       *data = ptr->data;
 259       return 1;       /* success */
 260     }
 261     ptr = ptr->next;
 262   }
 263
 264   return 0;   /* failure */
 265 }
 266
 267 /* MGCSHAREDHASH ********************************************************/
 268
 269 mgcsharedhashtbl_t * mgcsharedhashCreate(unsigned int size,
 270                                          double loadfactor) {
 271   mgcsharedhashtbl_t * ctable;
 272   mgcsharedhashlistnode_t * nodes;
 273   int i;
 274
 275   ctable = (mgcsharedhashtbl_t *)FREEMALLOC_NGC(sizeof(mgcsharedhashtbl_t));
 276   if(ctable == NULL) {
 277     // TODO
 278     BAMBOO_EXIT();
 279     return NULL;
 280   }
 281   // Allocate space for the hash table
 282   ctable->table = (mgcsharedhashlistnode_t *)FREEMALLOC_NGC(
 283           size*sizeof(mgcsharedhashlistnode_t));
 284   if(ctable->table == NULL) {
 285     BAMBOO_EXIT(); // TODO
 286     return NULL;
 287   }
 288   ctable->size = size;
 289   ctable->loadfactor = loadfactor;
 290   ctable->threshold = size*loadfactor;
 291
 292   ctable->mask = (size << (GC_SHIFT_BITS))-1;
 293
 294   ctable->structs = NULL ;
 295   ctable->numelements = 0; // Initial number of elements in the hash
 296   ctable->list = NULL;
 297
 298   return ctable;
 299 }
 300
 301 mgcsharedhashtbl_t * mgcsharedhashCreate_I(unsigned int size,
 302                                            double loadfactor) {
 303   mgcsharedhashtbl_t * ctable;
 304   mgcsharedhashlistnode_t * nodes;
 305   int i;
 306
 307   ctable = (mgcsharedhashtbl_t *)FREEMALLOC_NGC_I(sizeof(mgcsharedhashtbl_t));
 308   if(ctable == NULL) {
 309     // TODO
 310     BAMBOO_EXIT();
 311     return NULL;
 312   }
 313   // Allocate space for the hash table
 314   ctable->table = (mgcsharedhashlistnode_t *)FREEMALLOC_NGC_I(
 315           size*sizeof(mgcsharedhashlistnode_t));
 316   if(ctable->table == NULL) {
 317     BAMBOO_EXIT(); // TODO
 318     return NULL;
 319   }
 320   ctable->size = size;
 321   ctable->loadfactor = loadfactor;
 322   ctable->threshold = size*loadfactor;
 323
 324   ctable->mask = (size << (GC_SHIFT_BITS))-1;
 325
 326   ctable->structs = NULL ;
 327   ctable->numelements = 0; // Initial number of elements in the hash
 328   ctable->list = NULL;
 329
 330   return ctable;
 331 }
 332
 333 void mgcsharedhashReset(mgcsharedhashtbl_t * tbl) {
 334   mgcsharedhashlistnode_t * ptr = tbl->table;
 335
 336   if ((tbl->numelements) < (tbl->size>>6)) {
 337         mgcsharedhashlistnode_t *top = &ptr[tbl->size];
 338         mgcsharedhashlistnode_t * list = tbl->list;
 339         while(list != NULL) {
 340       mgcsharedhashlistnode_t * next = list->next;
 341       if ((list >= ptr) && (list < top)) {
 342                 //zero in list
 343         list->key=NULL;
 344         list->next=NULL;
 345       }
 346       list = next;
 347         }
 348   } else {
 349         BAMBOO_MEMSET_WH(tbl->table, '\0',
 350                 sizeof(mgcsharedhashlistnode_t)*tbl->size);
 351   }
 352
 353   mgcsharedliststruct_t * structs = tbl->structs;
 354   while(structs != NULL) {
 355     mgcsharedliststruct_t * next = structs->next;
 356         BAMBOO_MEMSET_WH(structs->array, '\0',
 357                 structs->num * sizeof(mgcsharedhashlistnode_t));
 358         structs->num = 0;
 359     structs = next;
 360   }
 361   tbl->numelements = 0;
 362 }
 363
 364 //Store objects and their pointers into hash
 365 //Using open addressing
 366 int mgcsharedhashInsert(mgcsharedhashtbl_t * tbl, void * key, void * val) {
 367   mgcsharedhashlistnode_t * ptr;
 368
 369   if(tbl->numelements > (tbl->threshold)) {
 370     //Never resize, simply don't insert any more
 371     return -1;
 372   }
 373
 374   ptr=&tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
 375
 376   if(ptr->key==0) {
 377     // the first time insert a value for the key
 378     ptr->key=key;
 379     ptr->val=val;
 380   } else { // Insert to the next empty place
 381         mgcsharedhashlistnode_t *top = &tbl->table[tbl->size];
 382     do {
 383           ptr++;
 384         } while((ptr < top) && (ptr->key != NULL));
 385         if(ptr >= top) {
 386           return -1;
 387         } else {
 388           ptr->key = key;
 389           ptr->val = val;
 390         }
 391   }
 392   ptr->next = tbl->list;
 393   tbl->list = ptr;
 394   tbl->numelements++;
 395   return 1;
 396 }
 397
 398 int mgcsharedhashInsert_I(mgcsharedhashtbl_t * tbl, void * key, void * val) {
 399   mgcsharedhashlistnode_t * ptr;
 400
 401   if(tbl->numelements > (tbl->threshold)) {
 402     //Never resize, simply don't insert any more
 403     return -1;
 404   }
 405
 406   ptr=&tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
 407
 408   if(ptr->key==0) {
 409     // the first time insert a value for the key
 410     ptr->key=key;
 411     ptr->val=val;
 412   } else { // Insert to the next empty place
 413         mgcsharedhashlistnode_t * top = &tbl->table[tbl->size];
 414         mgcsharedhashlistnode_t * start = ptr;
 415     do {
 416           ptr++;
 417           if(ptr->key == 0) {
 418                 break;
 419           }
 420         } while(ptr < top);
 421         if(ptr >= top) {
 422           return -1;
 423         } else {
 424           ptr->key = key;
 425           ptr->val = val;
 426         }
 427   }
 428   ptr->next = tbl->list;
 429   tbl->list = ptr;
 430   tbl->numelements++;
 431   return 1;
 432 }
 433
 434 // Search for an address for a given oid
 435 INLINE void * mgcsharedhashSearch(mgcsharedhashtbl_t * tbl, void * key) {
 436   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE]
 437   mgcsharedhashlistnode_t * node =
 438         &tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
 439   mgcsharedhashlistnode_t *top = &tbl->table[tbl->size];
 440
 441   do {
 442     if(node->key == key) {
 443       return node->val;
 444     }
 445     node++;
 446   } while(node < top);
 447
 448   return NULL;
 449 }
 450
 451 #endif