3 #include "runtime_arch.h"
22 /* mgchash ********************************************************/
23 mgchashtable_t * mgchashCreate(unsigned int size, double loadfactor) {
24 mgchashtable_t *ctable;
25 mgchashlistnode_t *nodes;
32 printf("Negative Hashtable size Exception\n");
37 // Allocate space for the hash table
38 ctable = (mgchashtable_t *)RUNMALLOC(sizeof(mgchashtable_t));
40 // Run out of local memory
43 ctable->table = (mgchashlistnode_t*)RUNMALLOC(size*sizeof(mgchashlistnode_t));
44 if(ctable->table == NULL) {
45 // Run out of local memory
48 ctable->loadfactor = loadfactor;
50 ctable->threshold=size*loadfactor;
52 ctable->mask = (size << 6)-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->next;
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 mgcliststruct_t * next = tbl->structs;
81 while(/*tbl->structs->*/next!=NULL) {
82 /*mgcliststruct_t * next = tbl->structs->next;
83 RUNFREE(tbl->structs);
88 //tbl->structs->num = 0;
92 //Store objects and their pointers into hash
93 void mgchashInsert(mgchashtable_t * tbl, void * key, void *val) {
94 mgchashlistnode_t *ptr;
96 if(tbl->numelements > (tbl->threshold)) {
98 unsigned int newsize = tbl->size << 1 + 1;
99 mgchashResize(tbl, newsize);
102 ptr=&tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>6];
106 // the first time insert a value for the key
109 } else { // Insert in the beginning of linked list
110 mgchashlistnode_t * node;
111 if (tbl->structs->num<NUMMGCLIST) {
112 node=&tbl->structs->array[tbl->structs->num];
116 mgcliststruct_t *tcl=RUNMALLOC(1*sizeof(mgcliststruct_t));
117 tcl->next=tbl->structs;
124 node->next = ptr->next;
130 mgchashtable_t * mgchashCreate_I(unsigned int size, double loadfactor) {
131 mgchashtable_t *ctable;
132 mgchashlistnode_t *nodes;
139 printf("Negative Hashtable size Exception\n");
144 // Allocate space for the hash table
145 ctable = (mgchashtable_t*)RUNMALLOC_I(sizeof(mgchashtable_t));
147 // Run out of local memory
150 ctable->table=(mgchashlistnode_t*)RUNMALLOC_I(size*sizeof(mgchashlistnode_t));
151 if(ctable->table == NULL) {
152 // Run out of local memory
155 ctable->loadfactor = loadfactor;
157 ctable->threshold=size*loadfactor;
159 ctable->mask = (size << 6)-1;
161 ctable->structs = (mgcliststruct_t*)RUNMALLOC_I(1*sizeof(mgcliststruct_t));
162 ctable->numelements = 0; // Initial number of elements in the hash
167 void mgchashInsert_I(mgchashtable_t * tbl, void * key, void *val) {
168 mgchashlistnode_t *ptr;
170 if(tbl->numelements > (tbl->threshold)) {
172 unsigned int newsize = tbl->size << 1 + 1;
173 mgchashResize_I(tbl, newsize);
176 ptr = &tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>6];
183 } else { // Insert in the beginning of linked list
184 mgchashlistnode_t * node;
185 if (tbl->structs->num<NUMMGCLIST) {
186 node=&tbl->structs->array[tbl->structs->num];
190 mgcliststruct_t *tcl=RUNMALLOC_I(1*sizeof(mgcliststruct_t));
191 tcl->next=tbl->structs;
198 node->next = ptr->next;
204 // Search for an address for a given oid
205 INLINE void * mgchashSearch(mgchashtable_t * tbl, void * key) {
206 //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE]
207 mgchashlistnode_t *node = &tbl->table[(((unsigned INTPTR)key)&tbl->mask)>>6];
210 if(node->key == key) {
214 } while(node != NULL);
219 unsigned int mgchashResize(mgchashtable_t * tbl, unsigned int newsize) {
220 mgchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the
221 // current and the next
222 // mgchashlistnodes in a linked list
223 unsigned int oldsize;
224 int isfirst; // Keeps track of the first element in the
225 // chashlistnode_t for each bin in hashtable
226 unsigned int i,index;
232 if((node = RUNMALLOC(newsize*sizeof(mgchashlistnode_t))) == NULL) {
233 printf("Calloc error %s %d\n", __FILE__, __LINE__);
237 tbl->table = node; //Update the global hashtable upon resize()
239 tbl->threshold = newsize * tbl->loadfactor;
240 mask = tbl->mask = (newsize << 6) - 1;
242 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
245 do { //Inner loop to go through linked lists
247 mgchashlistnode_t *tmp,*next;
249 if ((key=curr->key) == 0) {
250 //Exit inner loop if there the first element is 0
252 //key = val =0 for element if not present within the hash table
254 index = (((unsigned INTPTR)key) & mask) >> 6;
257 // Insert into the new table
260 tmp->val = curr->val;
262 NOTE: Add this case if you change this...
263 This case currently never happens because of the way things rehash....*/
265 mgchashlistnode_t *newnode= RUNMALLOC(1*sizeof(mgchashlistnode_t));
266 newnode->key = curr->key;
267 newnode->val = curr->val;
268 newnode->next = tmp->next;
272 curr->next=tmp->next;
281 RUNFREE(ptr); //Free the memory of the old hash table
286 unsigned int mgchashResize_I(mgchashtable_t * tbl, unsigned int newsize) {
287 mgchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the
288 // current and the next
289 // mgchashlistnodes in a linked list
290 unsigned int oldsize;
291 int isfirst; // Keeps track of the first element in the chashlistnode_t
292 // for each bin in hashtable
293 unsigned int i,index;
299 if((node = RUNMALLOC_I(newsize*sizeof(mgchashlistnode_t))) == NULL) {
301 printf("Calloc error %s %d\n", __FILE__, __LINE__);
305 tbl->table = node; //Update the global hashtable upon resize()
307 tbl->threshold = newsize * tbl->loadfactor;
308 mask = tbl->mask = (newsize << 6)-1;
310 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
313 do { //Inner loop to go through linked lists
315 mgchashlistnode_t *tmp,*next;
317 if ((key=curr->key) == 0) {
318 //Exit inner loop if there the first element is 0
320 //key = val =0 for element if not present within the hash table
322 index = (((unsigned INTPTR)key) & mask) >>6;
325 // Insert into the new table
328 tmp->val = curr->val;
330 NOTE: Add this case if you change this...
331 This case currently never happens because of the way things rehash....*/
333 mgchashlistnode_t *newnode=RUNMALLOC_I(1*sizeof(mgchashlistnode_t));
334 newnode->key = curr->key;
335 newnode->val = curr->val;
336 newnode->next = tmp->next;
339 curr->next=tmp->next;
347 RUNFREE(ptr); //Free the memory of the old hash table
352 //Delete the entire hash table
353 void mgchashDelete(mgchashtable_t * tbl) {
355 mgcliststruct_t *ptr=tbl->structs;
357 mgcliststruct_t *next=ptr->next;
366 /* MGCHASH ********************************************************/
368 struct MGCHash * allocateMGCHash(int size,
370 struct MGCHash *thisvar;
375 printf("Negative Hashtable size Exception\n");
379 thisvar=(struct MGCHash *)RUNMALLOC(sizeof(struct MGCHash));
380 thisvar->size = size;
382 (struct MGCNode *) RUNMALLOC(sizeof(struct MGCNode)*size);
384 thisvar->num4conflicts = conflicts;
388 void freeMGCHash(struct MGCHash *thisvar) {
390 for(i=thisvar->size-1; i>=0; i--) {
392 for(ptr=thisvar->bucket[i].next; ptr!=NULL; ) {
393 struct MGCNode * nextptr=ptr->next;
398 RUNFREE(thisvar->bucket);
402 int MGCHashadd(struct MGCHash * thisvar, int data) {
404 unsigned int hashkey;
407 hashkey = (unsigned int)data % thisvar->size;
408 ptr = &thisvar->bucket[hashkey];
410 struct MGCNode * prev = NULL;
411 if(ptr->data < thisvar->num4conflicts) {
412 struct MGCNode *node=RUNMALLOC(sizeof(struct MGCNode));
414 node->next=(ptr->next);
418 while (ptr->next!=NULL) {
423 ptr->next = thisvar->bucket[hashkey].next;
424 thisvar->bucket[hashkey].next = ptr;
432 struct MGCHash * allocateMGCHash_I(int size,
434 struct MGCHash *thisvar;
439 printf("Negative Hashtable size Exception\n");
443 thisvar=(struct MGCHash *)RUNMALLOC_I(sizeof(struct MGCHash));
444 thisvar->size = size;
446 (struct MGCNode *) RUNMALLOC_I(sizeof(struct MGCNode)*size);
448 thisvar->num4conflicts = conflicts;
452 int MGCHashadd_I(struct MGCHash * thisvar, int data) {
454 unsigned int hashkey;
457 hashkey = (unsigned int)data % thisvar->size;
458 ptr = &thisvar->bucket[hashkey];
460 struct MGCNode * prev = NULL;
461 if(ptr->data < thisvar->num4conflicts) {
462 struct MGCNode *node=RUNMALLOC_I(sizeof(struct MGCNode));
464 node->next=(ptr->next);
468 while (ptr->next!=NULL) {
473 ptr->next = thisvar->bucket[hashkey].next;
474 thisvar->bucket[hashkey].next = ptr;
482 int MGCHashcontains(struct MGCHash *thisvar, int data) {
483 unsigned int hashkey = (unsigned int)data % thisvar->size;
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;