3 #include "runtime_arch.h"
22 /* MGCHASH ********************************************************/
23 mgchashlistnode_t *mgc_table;
24 unsigned int mgc_size;
25 unsigned INTPTR mgc_mask;
26 unsigned int mgc_numelements;
27 unsigned int mgc_threshold;
28 double mgc_loadfactor;
29 mgcliststruct_t *mgc_structs;
31 void mgchashCreate(unsigned int size, double loadfactor) {
32 mgchashtable_t *ctable;
33 mgchashlistnode_t *nodes;
36 // Allocate space for the hash table
37 mgc_table = RUNMALLOC(size*sizeof(mgchashlistnode_t));
38 mgc_loadfactor = loadfactor;
40 mgc_threshold=size*loadfactor;
43 mgc_mask = ((size << 6)-1)&~(15UL);
45 mgc_mask = ((size << 6)-1)&~15;
48 mgc_structs=RUNMALLOC(1*sizeof(mgcliststruct_t));
49 mgc_numelements = 0; // Initial number of elements in the hash
53 mgchashlistnode_t *ptr = mgc_table;
56 /*if (mgc_numelements<(mgc_size>>6)) {
57 mgchashlistnode_t *top=&ptr[mgc_size];
58 mgchashlistnode_t *tmpptr=mgc_list;
60 mgchashlistnode_t *next=tmpptr->lnext;
61 if (tmpptr>=ptr&&tmpptr<top) {
69 BAMBOO_MEMSET_WH(mgc_table, '\0', sizeof(mgchashlistnode_t)*mgc_size);
71 while(mgc_structs->next!=NULL) {
72 mgcliststruct_t *next=mgc_structs->next;
80 //Store objects and their pointers into hash
81 void mgchashInsert(void * key, void *val) {
82 mgchashlistnode_t *ptr;
84 if(mgc_numelements > (mgc_threshold)) {
86 unsigned int newsize = mgc_size << 1 + 1;
87 mgchashResize(newsize);
90 //int hashkey = (unsigned int)key % mgc_size;
91 ptr=&mgc_table[(((unsigned INTPTR)key)&mgc_mask)>>6];//&mgc_table[hashkey];
95 // the first time insert a value for the key
98 } else { // Insert in the beginning of linked list
99 mgchashlistnode_t * node;
100 if (mgc_structs->num<NUMMGCLIST) {
101 node=&mgc_structs->array[mgc_structs->num];
105 mgcliststruct_t *tcl=RUNMALLOC(1*sizeof(mgcliststruct_t));
106 tcl->next=mgc_structs;
113 node->next = ptr->next;
119 void mgchashInsert_I(void * key, void *val) {
120 mgchashlistnode_t *ptr;
122 if(mgc_numelements > (mgc_threshold)) {
124 unsigned int newsize = mgc_size << 1 + 1;
125 mgchashResize_I(newsize);
128 //int hashkey = (unsigned int)key % mgc_size;
129 //ptr=&mgc_table[hashkey];
130 ptr = &mgc_table[(((unsigned INTPTR)key)&mgc_mask)>>6];
137 } else { // Insert in the beginning of linked list
138 mgchashlistnode_t * node;
139 if (mgc_structs->num<NUMMGCLIST) {
140 node=&mgc_structs->array[mgc_structs->num];
144 mgcliststruct_t *tcl=RUNMALLOC_I(1*sizeof(mgcliststruct_t));
145 tcl->next=mgc_structs;
152 node->next = ptr->next;
158 // Search for an address for a given oid
159 INLINE void * mgchashSearch(void * key) {
160 //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE]
161 //int hashkey = (unsigned int)key % mgc_size;
162 mgchashlistnode_t *node = &mgc_table[(((unsigned INTPTR)key)&mgc_mask)>>6];
163 //&mgc_table[hashkey];
166 if(node->key == key) {
170 } while(node != NULL);
175 unsigned int mgchashResize(unsigned int newsize) {
176 mgchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next mgchashlistnodes in a linked list
177 unsigned int oldsize;
178 int isfirst; // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
179 unsigned int i,index;
185 if((node = RUNMALLOC(newsize*sizeof(mgchashlistnode_t))) == NULL) {
186 printf("Calloc error %s %d\n", __FILE__, __LINE__);
190 mgc_table = node; //Update the global hashtable upon resize()
192 mgc_threshold = newsize * mgc_loadfactor;
193 mask=mgc_mask = (newsize << 6)-1;
195 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
198 do { //Inner loop to go through linked lists
200 mgchashlistnode_t *tmp,*next;
202 if ((key=curr->key) == 0) { //Exit inner loop if there the first element is 0
203 break; //key = val =0 for element if not present within the hash table
205 //index = (unsigned int)key % mgc_size;
206 index = (((unsigned INTPTR)key) & mask) >>6;
209 // Insert into the new table
212 tmp->val = curr->val;
214 NOTE: Add this case if you change this...
215 This case currently never happens because of the way things rehash....
217 chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
218 newnode->key = curr->key;
219 newnode->val = curr->val;
220 newnode->next = tmp->next;
224 curr->next=tmp->next;
233 RUNFREE(ptr); //Free the memory of the old hash table
238 unsigned int mgchashResize_I(unsigned int newsize) {
239 mgchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next mgchashlistnodes in a linked list
240 unsigned int oldsize;
241 int isfirst; // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
242 unsigned int i,index;
248 if((node = RUNMALLOC_I(newsize*sizeof(mgchashlistnode_t))) == NULL) {
250 printf("Calloc error %s %d\n", __FILE__, __LINE__);
254 mgc_table = node; //Update the global hashtable upon resize()
256 mgc_threshold = newsize * mgc_loadfactor;
257 mask=mgc_mask = (newsize << 6)-1;
259 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
262 do { //Inner loop to go through linked lists
264 mgchashlistnode_t *tmp,*next;
266 if ((key=curr->key) == 0) {
267 //Exit inner loop if there the first element is 0
269 //key = val =0 for element if not present within the hash table
271 //index = (unsigned int)key % mgc_size;
272 index = (((unsigned INTPTR)key) & mask) >>6;
275 // Insert into the new table
278 tmp->val = curr->val;
280 NOTE: Add this case if you change this...
281 This case currently never happens because of the way things rehash....*/
283 mgchashlistnode_t *newnode=RUNMALLOC_I(1*sizeof(mgchashlistnode_t));
284 newnode->key = curr->key;
285 newnode->val = curr->val;
286 newnode->next = tmp->next;
290 curr->next=tmp->next;
298 RUNFREE(ptr); //Free the memory of the old hash table
303 //Delete the entire hash table
304 void mgchashDelete() {
306 mgcliststruct_t *ptr=mgc_structs;
308 mgcliststruct_t *next=ptr->next;
317 struct MGCHash * allocateMGCHash(int size,
319 struct MGCHash *thisvar;
324 printf("Negative Hashtable size Exception\n");
328 thisvar=(struct MGCHash *)RUNMALLOC(sizeof(struct MGCHash));
329 thisvar->size = size;
331 (struct MGCNode *) RUNMALLOC(sizeof(struct MGCNode)*size);
332 // zero out all the buckets
333 BAMBOO_MEMSET_WH(thisvar->bucket, '\0', sizeof(struct MGCNode)*size);
335 thisvar->num4conflicts = conflicts;
339 void freeMGCHash(struct MGCHash *thisvar) {
341 for(i=thisvar->size-1; i>=0; i--) {
343 for(ptr=thisvar->bucket[i].next; ptr!=NULL;) {
344 struct MGCNode * nextptr=ptr->next;
349 RUNFREE(thisvar->bucket);
353 void MGCHashrehash(struct MGCHash * thisvar) {
354 int newsize=thisvar->size;
355 struct MGCNode ** newbucket = (struct MGCNode **) RUNMALLOC(sizeof(struct MGCNode *)*newsize);
357 for(i=thisvar->size-1; i>=0; i--) {
359 for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
360 struct MGCNode * nextptr=ptr->next;
361 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
362 ptr->next=newbucket[newhashkey];
363 newbucket[newhashkey]=ptr;
367 thisvar->size=newsize;
368 RUNFREE(thisvar->bucket);
369 thisvar->bucket=newbucket;
372 int MGCHashadd(struct MGCHash * thisvar, int data) {
374 unsigned int hashkey;
377 /*if (thisvar->numelements>=thisvar->size) {
378 int newsize=2*thisvar->size+1;
379 struct MGCNode ** newbucket = (struct MGCNode **) RUNMALLOC(sizeof(struct MGCNode *)*newsize);
381 for(i=thisvar->size-1; i>=0; i--) {
383 for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
384 struct MGCNode * nextptr=ptr->next;
385 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
386 ptr->next=newbucket[newhashkey];
387 newbucket[newhashkey]=ptr;
391 thisvar->size=newsize;
392 RUNFREE(thisvar->bucket);
393 thisvar->bucket=newbucket;
396 hashkey = (unsigned int)data % thisvar->size;
397 ptr = &thisvar->bucket[hashkey];
399 struct MGCNode * prev = NULL;
400 if(ptr->data < thisvar->num4conflicts) {
401 struct MGCNode *node=RUNMALLOC(sizeof(struct MGCNode));
403 node->next=(ptr->next);
407 while (ptr->next!=NULL) {
412 ptr->next = thisvar->bucket[hashkey].next;
413 thisvar->bucket[hashkey].next = ptr;
421 int MGCHashadd_I(struct MGCHash * thisvar, int data) {
423 unsigned int hashkey;
426 /*if (thisvar->numelements>=thisvar->size) {
427 int newsize=2*thisvar->size+1;
428 struct MGCNode ** newbucket = (struct MGCNode **) RUNMALLOC_I(sizeof(struct MGCNode *)*newsize);
430 for(i=thisvar->size-1; i>=0; i--) {
432 for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
433 struct MGCNode * nextptr=ptr->next;
434 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
435 ptr->next=newbucket[newhashkey];
436 newbucket[newhashkey]=ptr;
440 thisvar->size=newsize;
441 RUNFREE(thisvar->bucket);
442 thisvar->bucket=newbucket;
445 hashkey = (unsigned int)data % thisvar->size;
446 ptr = &thisvar->bucket[hashkey];
448 struct MGCNode * prev = NULL;
449 if(ptr->data < thisvar->num4conflicts) {
450 struct MGCNode *node=RUNMALLOC_I(sizeof(struct MGCNode));
452 node->next=(ptr->next);
456 while (ptr->next!=NULL) {
461 ptr->next = thisvar->bucket[hashkey].next;
462 thisvar->bucket[hashkey].next = ptr;
470 int MGCHashcontains(struct MGCHash *thisvar, int data) {
471 unsigned int hashkey = (unsigned int)data % thisvar->size;
473 struct MGCNode *ptr = thisvar->bucket[hashkey].next;
474 struct MGCNode *prev = NULL;
476 if (ptr->data == data) {
479 ptr->next = thisvar->bucket[hashkey].next;
480 thisvar->bucket[hashkey].next = ptr;