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