3 #include "runtime_arch.h"
21 #define GC_SHIFT_BITS 4
23 /* mgchash ********************************************************/
24 mgchashtable_t * mgchashCreate(unsigned int size, double loadfactor) {
25 mgchashtable_t *ctable;
26 mgchashlistnode_t *nodes;
33 printf("Negative Hashtable size Exception\n");
38 // Allocate space for the hash table
39 ctable = (mgchashtable_t *)RUNMALLOC(sizeof(mgchashtable_t));
41 // Run out of local memory
44 ctable->table = (mgchashlistnode_t*)RUNMALLOC(size*sizeof(mgchashlistnode_t));
45 if(ctable->table == NULL) {
46 // Run out of local memory
49 ctable->loadfactor = loadfactor;
51 ctable->threshold=size*loadfactor;
53 ctable->mask = (size << (GC_SHIFT_BITS))-1;
54 ctable->structs = (mgcliststruct_t*)RUNMALLOC(1*sizeof(mgcliststruct_t));
55 ctable->numelements = 0; // Initial number of elements in the hash
60 void mgchashreset(mgchashtable_t * tbl) {
61 mgchashlistnode_t *ptr = tbl->table;
64 /*if (tbl->numelements<(tbl->size>>6)) {
65 mgchashlistnode_t *top=&ptr[tbl->size];
66 mgchashlistnode_t * list = tbl->list;
68 mgchashlistnode_t * next = list->lnext;
69 if ((list >= ptr) && (list < top)) {
77 BAMBOO_MEMSET_WH(tbl->table, '\0', sizeof(mgchashlistnode_t)*tbl->size);
79 // TODO now never release any allocated memory, may need to be changed
80 while(tbl->structs->next!=NULL) {
81 mgcliststruct_t * next = tbl->structs->next;
82 RUNFREE(tbl->structs);
85 tbl->structs->num = 0;
89 //Store objects and their pointers into hash
90 void mgchashInsert(mgchashtable_t * tbl, void * key, void *val) {
91 mgchashlistnode_t *ptr;
93 if(tbl->numelements > (tbl->threshold)) {
95 unsigned int newsize = tbl->size << 1 + 1;
96 mgchashResize(tbl, newsize);
99 ptr=&tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
103 // the first time insert a value for the key
106 } else { // Insert in the beginning of linked list
107 mgchashlistnode_t * node;
108 if (tbl->structs->num<NUMMGCLIST) {
109 node=&tbl->structs->array[tbl->structs->num];
113 mgcliststruct_t *tcl=RUNMALLOC(1*sizeof(mgcliststruct_t));
114 tcl->next=tbl->structs;
121 node->next = ptr->next;
127 mgchashtable_t * mgchashCreate_I(unsigned int size, double loadfactor) {
128 mgchashtable_t *ctable;
129 mgchashlistnode_t *nodes;
136 printf("Negative Hashtable size Exception\n");
141 // Allocate space for the hash table
142 ctable = (mgchashtable_t*)RUNMALLOC_I(sizeof(mgchashtable_t));
144 // Run out of local memory
147 ctable->table=(mgchashlistnode_t*)RUNMALLOC_I(size*sizeof(mgchashlistnode_t));
148 if(ctable->table == NULL) {
149 // Run out of local memory
152 ctable->loadfactor = loadfactor;
154 ctable->threshold=size*loadfactor;
156 ctable->mask = (size << (GC_SHIFT_BITS))-1;
157 ctable->structs = (mgcliststruct_t*)RUNMALLOC_I(1*sizeof(mgcliststruct_t));
158 ctable->numelements = 0; // Initial number of elements in the hash
163 void mgchashInsert_I(mgchashtable_t * tbl, void * key, void *val) {
164 mgchashlistnode_t *ptr;
166 if(tbl->numelements > (tbl->threshold)) {
168 unsigned int newsize = tbl->size << 1 + 1;
169 mgchashResize_I(tbl, newsize);
172 ptr = &tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
179 } else { // Insert in the beginning of linked list
180 mgchashlistnode_t * node;
181 if (tbl->structs->num<NUMMGCLIST) {
182 node=&tbl->structs->array[tbl->structs->num];
186 mgcliststruct_t *tcl=RUNMALLOC_I(1*sizeof(mgcliststruct_t));
187 tcl->next=tbl->structs;
194 node->next = ptr->next;
200 // Search for an address for a given oid
201 INLINE void * mgchashSearch(mgchashtable_t * tbl, void * key) {
202 //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE]
203 mgchashlistnode_t *node =
204 &tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>(GC_SHIFT_BITS)];
207 if(node->key == key) {
211 } while(node != NULL);
216 unsigned int mgchashResize(mgchashtable_t * tbl, unsigned int newsize) {
217 mgchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the
218 // current and the next
219 // mgchashlistnodes in a linked list
220 unsigned int oldsize;
221 int isfirst; // Keeps track of the first element in the
222 // chashlistnode_t for each bin in hashtable
223 unsigned int i,index;
229 if((node = RUNMALLOC(newsize*sizeof(mgchashlistnode_t))) == NULL) {
230 printf("Calloc error %s %d\n", __FILE__, __LINE__);
234 tbl->table = node; //Update the global hashtable upon resize()
236 tbl->threshold = newsize * tbl->loadfactor;
237 mask = tbl->mask = (newsize << (GC_SHIFT_BITS)) - 1;
239 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
242 do { //Inner loop to go through linked lists
244 mgchashlistnode_t *tmp,*next;
246 if ((key=curr->key) == 0) {
247 //Exit inner loop if there the first element is 0
249 //key = val =0 for element if not present within the hash table
251 index = (((unsigned INTPTR)key) & mask) >> (GC_SHIFT_BITS);
254 // Insert into the new table
257 tmp->val = curr->val;
259 NOTE: Add this case if you change this...
260 This case currently never happens because of the way things rehash....*/
262 mgchashlistnode_t *newnode= RUNMALLOC(1*sizeof(mgchashlistnode_t));
263 newnode->key = curr->key;
264 newnode->val = curr->val;
265 newnode->next = tmp->next;
269 curr->next=tmp->next;
278 RUNFREE(ptr); //Free the memory of the old hash table
283 unsigned int mgchashResize_I(mgchashtable_t * tbl, unsigned int newsize) {
284 mgchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the
285 // current and the next
286 // mgchashlistnodes in a linked list
287 unsigned int oldsize;
288 int isfirst; // Keeps track of the first element in the chashlistnode_t
289 // for each bin in hashtable
290 unsigned int i,index;
296 if((node = RUNMALLOC_I(newsize*sizeof(mgchashlistnode_t))) == NULL) {
298 printf("Calloc error %s %d\n", __FILE__, __LINE__);
302 tbl->table = node; //Update the global hashtable upon resize()
304 tbl->threshold = newsize * tbl->loadfactor;
305 mask = tbl->mask = (newsize << (GC_SHIFT_BITS))-1;
307 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
310 do { //Inner loop to go through linked lists
312 mgchashlistnode_t *tmp,*next;
314 if ((key=curr->key) == 0) {
315 //Exit inner loop if there the first element is 0
317 //key = val =0 for element if not present within the hash table
319 index = (((unsigned INTPTR)key) & mask) >> (GC_SHIFT_BITS);
322 // Insert into the new table
325 tmp->val = curr->val;
327 NOTE: Add this case if you change this...
328 This case currently never happens because of the way things rehash....*/
330 mgchashlistnode_t *newnode=RUNMALLOC_I(1*sizeof(mgchashlistnode_t));
331 newnode->key = curr->key;
332 newnode->val = curr->val;
333 newnode->next = tmp->next;
336 curr->next=tmp->next;
344 RUNFREE(ptr); //Free the memory of the old hash table
349 //Delete the entire hash table
350 void mgchashDelete(mgchashtable_t * tbl) {
352 mgcliststruct_t *ptr=tbl->structs;
354 mgcliststruct_t *next=ptr->next;
363 /* MGCHASH ********************************************************/
365 struct MGCHash * allocateMGCHash(int size,
367 struct MGCHash *thisvar;
372 printf("Negative Hashtable size Exception\n");
376 thisvar=(struct MGCHash *)RUNMALLOC(sizeof(struct MGCHash));
377 thisvar->size = size;
379 (struct MGCNode *) RUNMALLOC(sizeof(struct MGCNode)*size);
381 thisvar->num4conflicts = conflicts;
385 void freeMGCHash(struct MGCHash *thisvar) {
387 for(i=thisvar->size-1; i>=0; i--) {
389 for(ptr=thisvar->bucket[i].next; ptr!=NULL; ) {
390 struct MGCNode * nextptr=ptr->next;
395 RUNFREE(thisvar->bucket);
399 int MGCHashadd(struct MGCHash * thisvar, int data) {
401 unsigned int hashkey;
404 int mask = (thisvar->size << (GC_SHIFT_BITS))-1;
405 hashkey = (((unsigned INTPTR)data)&mask)>>(GC_SHIFT_BITS);
406 ptr = &thisvar->bucket[hashkey];
408 struct MGCNode * prev = NULL;
409 if(ptr->data < thisvar->num4conflicts) {
410 struct MGCNode *node=RUNMALLOC(sizeof(struct MGCNode));
412 node->next=(ptr->next);
416 while (ptr->next!=NULL) {
421 ptr->next = thisvar->bucket[hashkey].next;
422 thisvar->bucket[hashkey].next = ptr;
430 struct MGCHash * allocateMGCHash_I(int size,
432 struct MGCHash *thisvar;
437 printf("Negative Hashtable size Exception\n");
441 thisvar=(struct MGCHash *)RUNMALLOC_I(sizeof(struct MGCHash));
442 thisvar->size = size;
444 (struct MGCNode *) RUNMALLOC_I(sizeof(struct MGCNode)*size);
446 thisvar->num4conflicts = conflicts;
450 int MGCHashadd_I(struct MGCHash * thisvar, int data) {
452 unsigned int hashkey;
455 int mask = (thisvar->size << (GC_SHIFT_BITS))-1;
456 hashkey = (((unsigned INTPTR)data)&mask)>>(GC_SHIFT_BITS);
457 ptr = &thisvar->bucket[hashkey];
459 struct MGCNode * prev = NULL;
460 if(ptr->data < thisvar->num4conflicts) {
461 struct MGCNode *node=RUNMALLOC_I(sizeof(struct MGCNode));
463 node->next=(ptr->next);
467 while (ptr->next!=NULL) {
472 ptr->next = thisvar->bucket[hashkey].next;
473 thisvar->bucket[hashkey].next = ptr;
481 int MGCHashcontains(struct MGCHash *thisvar, int data) {
482 int mask = (thisvar->size << (GC_SHIFT_BITS))-1;
483 unsigned int hashkey = (((unsigned INTPTR)data)&mask)>>(GC_SHIFT_BITS);
485 struct MGCNode *ptr = thisvar->bucket[hashkey].next;
486 struct MGCNode *prev = NULL;
488 if (ptr->data == data) {
491 ptr->next = thisvar->bucket[hashkey].next;
492 thisvar->bucket[hashkey].next = ptr;