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