3 #include "GCSharedHash.h"
5 #include "runtime_arch.h"
21 #define INLINE inline __attribute__((always_inline))
22 #endif // #ifndef INLINE
25 /* GCSHARED HASH ********************************************************/
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);
33 struct GCSharedHash * allocateGCSharedHash(int size) {
34 struct GCSharedHash *thisvar;
39 printf("Negative Hashtable size Exception\n");
43 thisvar=(struct GCSharedHash *)FREEMALLOC_NGC(sizeof(struct GCSharedHash));
49 (struct GCSharedNode **)FREEMALLOC_NGC(sizeof(struct GCSharedNode *)*size);
50 if(thisvar->bucket == NULL) {
54 /* Set allocation blocks*/
55 thisvar->listhead=NULL;
56 thisvar->listtail=NULL;
58 thisvar->numelements = 0;
62 void freeGCSharedHash(struct GCSharedHash *thisvar) {
63 struct GCSharedNode *ptr=thisvar->listhead;
64 FREE_NGC(thisvar->bucket);
66 struct GCSharedNode *next=ptr->lnext;
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) {
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;
91 thisvar->size=newsize;
92 FREE_NGC(thisvar->bucket);
93 thisvar->bucket=newbucket;
97 int GCSharedHashadd(struct GCSharedHash * thisvar,int key, int data) {
100 struct GCSharedNode **ptr;
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) {
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;
121 thisvar->size=newsize;
122 FREE_NGC(thisvar->bucket);
123 thisvar->bucket=newbucket;
126 hashkey = (unsigned int)key % thisvar->size;
127 ptr = &thisvar->bucket[hashkey];
129 /* check that thisvar key/object pair isn't already here */
130 /* TBD can be optimized for set v. relation */
133 if ((*ptr)->key == key && (*ptr)->data == data) {
136 ptr = &((*ptr)->next);
140 struct GCSharedNode *node=FREEMALLOC_NGC(sizeof(struct GCSharedNode));
148 if (thisvar->listhead==NULL) {
149 thisvar->listhead=node;
150 thisvar->listtail=node;
155 node->lnext=thisvar->listhead;
156 thisvar->listhead->lprev=node;
157 thisvar->listhead=node;
161 thisvar->numelements++;
166 struct GCSharedHash * allocateGCSharedHash_I(int size) {
167 struct GCSharedHash *thisvar;
172 printf("Negative Hashtable size Exception\n");
176 thisvar=(struct GCSharedHash *)FREEMALLOC_NGC_I(sizeof(struct GCSharedHash));
177 if(thisvar == NULL) {
180 thisvar->size = size;
182 (struct GCSharedNode **)FREEMALLOC_NGC_I(
183 sizeof(struct GCSharedNode *)*size);
184 if(thisvar->bucket == NULL) {
188 /* Set allocation blocks*/
189 thisvar->listhead=NULL;
190 thisvar->listtail=NULL;
192 thisvar->numelements = 0;
196 int GCSharedHashadd_I(struct GCSharedHash * thisvar,int key, int data) {
198 unsigned int hashkey;
199 struct GCSharedNode **ptr;
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) {
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;
220 thisvar->size=newsize;
221 FREE_NGC_I(thisvar->bucket);
222 thisvar->bucket=newbucket;
225 hashkey = (unsigned int)key % thisvar->size;
226 ptr = &thisvar->bucket[hashkey];
228 /* check that thisvar key/object pair isn't already here */
229 /* TBD can be optimized for set v. relation */
232 if ((*ptr)->key == key && (*ptr)->data == data) {
235 ptr = &((*ptr)->next);
239 struct GCSharedNode *node=FREEMALLOC_NGC_I(sizeof(struct GCSharedNode));
247 if (thisvar->listhead==NULL) {
248 thisvar->listhead=node;
249 thisvar->listtail=node;
254 node->lnext=thisvar->listhead;
255 thisvar->listhead->lprev=node;
256 thisvar->listhead=node;
260 thisvar->numelements++;
265 int GCSharedHashget(struct GCSharedHash *thisvar, int key, int *data) {
266 unsigned int hashkey = (unsigned int)key % thisvar->size;
268 struct GCSharedNode *ptr = thisvar->bucket[hashkey];
270 if (ptr->key == key) {
272 return 1; /* success */
277 return 0; /* failure */
280 /* MGCSHAREDHASH ********************************************************/
282 mgcsharedhashtbl_t * mgcsharedhashCreate(unsigned int size,
284 mgcsharedhashtbl_t * ctable;
285 mgcsharedhashlistnode_t * nodes;
288 ctable = (mgcsharedhashtbl_t *)FREEMALLOC_NGC(sizeof(mgcsharedhashtbl_t));
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
302 ctable->loadfactor = loadfactor;
303 ctable->threshold = size*loadfactor;
305 ctable->mask = (size << 6)-1;
307 ctable->structs = NULL ; //FREEMALLOC_NGC(1*sizeof(mgcliststruct_t));
308 ctable->numelements = 0; // Initial number of elements in the hash
314 mgcsharedhashtbl_t * mgcsharedhashCreate_I(unsigned int size,
316 mgcsharedhashtbl_t * ctable;
317 mgcsharedhashlistnode_t * nodes;
320 ctable = (mgcsharedhashtbl_t *)FREEMALLOC_NGC_I(sizeof(mgcsharedhashtbl_t));
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
334 ctable->loadfactor = loadfactor;
335 ctable->threshold = size*loadfactor;
337 ctable->mask = (size << 6)-1;
339 ctable->structs = NULL ; //FREEMALLOC_NGC(1*sizeof(mgcliststruct_t));
340 ctable->numelements = 0; // Initial number of elements in the hash
346 void mgcsharedhashReset(mgcsharedhashtbl_t * tbl) {
347 mgcsharedhashlistnode_t * ptr = tbl->table;
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)) {
362 BAMBOO_MEMSET_WH(tbl->table, '\0',
363 sizeof(mgcsharedhashlistnode_t)*tbl->size);
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));
374 tbl->numelements = 0;
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;
382 if(tbl->numelements > (tbl->threshold)) {
383 //Never resize, simply don't insert any more
387 //int keyto = ((unsigned INTPTR)key) % (tbl->size);
388 //ptr=&tbl->table[keyto];
389 ptr=&tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>6];
392 // the first time insert a value for the key
395 } else { // Insert to the next empty place
396 mgcsharedhashlistnode_t *top = &tbl->table[tbl->size];
399 } while((ptr < top) && (ptr->key != NULL));
407 ptr->next = tbl->list;
413 int mgcsharedhashInsert_I(mgcsharedhashtbl_t * tbl, void * key, void * val) {
414 mgcsharedhashlistnode_t * ptr;
416 if(tbl->numelements > (tbl->threshold)) {
417 //Never resize, simply don't insert any more
421 //int keyto = ((unsigned INTPTR)key) % (tbl->size);
422 //ptr=&tbl->table[keyto];
423 ptr=&tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>6];
426 // the first time insert a value for the key
429 } else { // Insert to the next empty place
430 mgcsharedhashlistnode_t * top = &tbl->table[tbl->size];
431 mgcsharedhashlistnode_t * start = ptr;
445 ptr->next = tbl->list;
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];
462 if(node->key == key) {