3 #define likely(x) __builtin_expect((x),1)
4 #define unlikely(x) __builtin_expect((x),0)
6 //Smallest Object Size with 1 ptr is 32bytes on on 64-bit machine and 24bytes on 32-bit machine
13 __thread dchashlistnode_t *dc_c_table;
14 __thread dchashlistnode_t *dc_c_list;
15 __thread dcliststruct_t *dc_c_structs;
16 __thread unsigned int dc_c_size;
17 __thread unsigned INTPTR dc_c_mask;
18 __thread unsigned int dc_c_numelements;
19 __thread unsigned int dc_c_threshold;
20 __thread double dc_c_loadfactor;
22 void hashRCRCreate(unsigned int size, double loadfactor) {
23 // Allocate space for the hash table
25 dc_c_table = calloc(size, sizeof(dchashlistnode_t));
26 dc_c_loadfactor = loadfactor;
28 dc_c_threshold=size*loadfactor;
29 dc_c_mask = (size << SHIFTBITS)-1;
30 dc_c_structs=calloc(1, sizeof(dcliststruct_t));
31 dc_c_numelements = 0; // Initial number of elements in the hash
36 dchashlistnode_t *ptr = dc_c_table;
38 if (dc_c_numelements<(dc_c_size>>SHIFTBITS)) {
39 dchashlistnode_t *top=&ptr[dc_c_size];
40 dchashlistnode_t *tmpptr=dc_c_list;
42 dchashlistnode_t *next=tmpptr->lnext;
43 if (tmpptr>=ptr&&tmpptr<top) {
51 bzero(dc_c_table, sizeof(dchashlistnode_t)*dc_c_size);
53 while(dc_c_structs->next!=NULL) {
54 dcliststruct_t *next=dc_c_structs->next;
58 dc_c_structs->num = 0;
63 //Store objects and their pointers into hash
65 //0 = object already exists / Add failed
66 int hashRCRInsert(void * key) {
67 dchashlistnode_t *ptr;
69 if (unlikely(key==NULL)) {
73 if(unlikely(dc_c_numelements > dc_c_threshold)) {
75 unsigned int newsize = dc_c_size << 1;
76 hashRCRResize(newsize);
78 ptr = &dc_c_table[(((unsigned INTPTR)key)&dc_c_mask)>>SHIFTBITS];
79 if(likely(ptr->key==0)) {
84 } else { // Insert in the beginning of linked list
85 dchashlistnode_t * node;
86 dchashlistnode_t *search=ptr;
88 //make sure it isn't here
90 if(search->key == key) {
94 } while(search != NULL);
97 if (dc_c_structs->num<NUMDCLIST) {
98 node=&dc_c_structs->array[dc_c_structs->num];
102 dcliststruct_t *tcl=calloc(1,sizeof(dcliststruct_t));
103 tcl->next=dc_c_structs;
109 node->next = ptr->next;
111 node->lnext=dc_c_list;
119 unsigned int hashRCRResize(unsigned int newsize) {
120 dchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next chashlistnodes in a linked list
121 unsigned int oldsize;
122 int isfirst; // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
123 unsigned int i,index;
130 if((node = calloc(newsize, sizeof(dchashlistnode_t))) == NULL) {
131 printf("Calloc error %s %d\n", __FILE__, __LINE__);
135 dc_c_table = node; //Update the global hashtable upon resize()
137 dc_c_threshold = newsize * dc_c_loadfactor;
138 mask=dc_c_mask = (newsize << SHIFTBITS)-1;
140 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
143 do { //Inner loop to go through linked lists
145 dchashlistnode_t *tmp,*next;
147 if ((key=curr->key) == 0) { //Exit inner loop if there the first element is 0
148 break; //key = val =0 for element if not present within the hash table
151 index = (((unsigned INTPTR)key) & mask) >>SHIFTBITS;
154 // Insert into the new table
157 tmp->lnext=dc_c_list;
160 NOTE: Add this case if you change this...
161 This case currently never happens because of the way things rehash....
163 chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
164 newnode->key = curr->key;
165 newnode->val = curr->val;
166 newnode->next = tmp->next;
170 curr->next=tmp->next;
172 curr->lnext=dc_c_list;
181 free(ptr); //Free the memory of the old hash table
185 //Delete the entire hash table
186 void hashRCRDelete() {
187 dcliststruct_t *ptr=dc_c_structs;
189 dcliststruct_t *next=ptr->next;
199 // Search for an address for a given Address
200 INLINE int hashRCRSearch(void * key) {
201 //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
202 dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)key) & dc_c_mask)>>SHIFTBITS];
205 if(node->key == key) {
209 } while(node != NULL);