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