3 #define likely(x) __builtin_expect((x),1)
\r
4 #define unlikely(x) __builtin_expect((x),0)
\r
6 //Smallest Object Size with 1 ptr is 32bytes on on 64-bit machine and 24bytes on 32-bit machine
\r
13 __thread dchashlistnode_t *dc_c_table = NULL;
\r
14 __thread dchashlistnode_t *dc_c_list = NULL;
\r
15 __thread dcliststruct_t *dc_c_structs= NULL;
\r
16 __thread unsigned int dc_c_size;
\r
17 __thread unsigned INTPTR dc_c_mask;
\r
18 __thread unsigned int dc_c_numelements;
\r
19 __thread unsigned int dc_c_threshold;
\r
20 __thread double dc_c_loadfactor;
\r
22 void hashRCRCreate(unsigned int size, double loadfactor) {
\r
23 // Allocate space for the hash table
\r
25 dc_c_table = calloc(size, sizeof(dchashlistnode_t));
\r
26 dc_c_loadfactor = loadfactor;
\r
28 dc_c_threshold=size*loadfactor;
\r
29 dc_c_mask = (size << SHIFTBITS)-1;
\r
30 dc_c_structs=calloc(1, sizeof(dcliststruct_t));
\r
31 dc_c_numelements = 0; // Initial number of elements in the hash
\r
35 void hashRCRreset() {
\r
36 if(dc_c_table == NULL) {
\r
37 hashRCRCreate(128, 0.75);
\r
40 dchashlistnode_t *ptr = dc_c_table;
\r
42 if (dc_c_numelements<(dc_c_size>>SHIFTBITS)) {
\r
43 dchashlistnode_t *top=&ptr[dc_c_size];
\r
44 dchashlistnode_t *tmpptr=dc_c_list;
\r
45 while(tmpptr!=NULL) {
\r
46 dchashlistnode_t *next=tmpptr->lnext;
\r
47 if (tmpptr>=ptr&&tmpptr<top) {
\r
49 tmpptr->object=NULL;
\r
55 bzero(dc_c_table, sizeof(dchashlistnode_t)*dc_c_size);
\r
57 while(dc_c_structs->next!=NULL) {
\r
58 dcliststruct_t *next=dc_c_structs->next;
\r
62 dc_c_structs->num = 0;
\r
63 dc_c_numelements = 0;
\r
67 //Store objects and their pointers into hash
\r
69 //0 = object already exists / Add failed
\r
70 int hashRCRInsert(void * objectPtr, int traverserState) {
\r
71 dchashlistnode_t *ptr;
\r
73 if (unlikely(objectPtr==NULL)) {
\r
77 if(unlikely(dc_c_numelements > dc_c_threshold)) {
\r
79 unsigned int newsize = dc_c_size << 1;
\r
80 hashRCRResize(newsize);
\r
82 ptr = &dc_c_table[(((unsigned INTPTR)objectPtr)&dc_c_mask)>>SHIFTBITS];
\r
83 if(likely(ptr->object==0)) {
\r
84 ptr->object=objectPtr;
\r
85 ptr->traverserState = traverserState;
\r
86 ptr->lnext=dc_c_list;
\r
89 } else { // Insert in the beginning of linked list
\r
90 dchashlistnode_t * node;
\r
91 dchashlistnode_t *search=ptr;
\r
93 //make sure it isn't here
\r
95 if(search->object == objectPtr && search->traverserState == traverserState) {
\r
98 search=search->next;
\r
99 } while(search != NULL);
\r
101 dc_c_numelements++;
\r
102 if (dc_c_structs->num<NUMDCLIST) {
\r
103 node=&dc_c_structs->array[dc_c_structs->num];
\r
104 dc_c_structs->num++;
\r
107 dcliststruct_t *tcl=calloc(1,sizeof(dcliststruct_t));
\r
108 tcl->next=dc_c_structs;
\r
110 node=&tcl->array[0];
\r
113 node->object = objectPtr;
\r
114 node->traverserState=traverserState;
\r
115 node->next = ptr->next;
\r
117 node->lnext=dc_c_list;
\r
125 unsigned int hashRCRResize(unsigned int newsize) {
\r
126 dchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next chashlistnodes in a linked list
\r
127 unsigned int oldsize;
\r
128 int isfirst; // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
\r
129 unsigned int i,index;
\r
133 oldsize = dc_c_size;
\r
136 if((node = calloc(newsize, sizeof(dchashlistnode_t))) == NULL) {
\r
137 printf("Calloc error %s %d\n", __FILE__, __LINE__);
\r
141 dc_c_table = node; //Update the global hashtable upon resize()
\r
142 dc_c_size = newsize;
\r
143 dc_c_threshold = newsize * dc_c_loadfactor;
\r
144 mask=dc_c_mask = (newsize << SHIFTBITS)-1;
\r
146 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
\r
149 do { //Inner loop to go through linked lists
\r
151 dchashlistnode_t *tmp,*next;
\r
153 if ((key=curr->object) == 0) { //Exit inner loop if there the first element is 0
\r
154 break; //key = val =0 for element if not present within the hash table
\r
157 index = (((unsigned INTPTR)key) & mask) >>SHIFTBITS;
\r
160 // Insert into the new table
\r
161 if(tmp->object == 0) {
\r
163 tmp->traverserState = curr->traverserState;
\r
164 tmp->lnext=dc_c_list;
\r
167 NOTE: Add this case if you change this...
\r
168 This case currently never happens because of the way things rehash....
\r
169 else if (isfirst) {
\r
170 chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
\r
171 newnode->key = curr->key;
\r
172 newnode->val = curr->val;
\r
173 newnode->next = tmp->next;
\r
177 curr->next=tmp->next;
\r
179 curr->lnext=dc_c_list;
\r
185 } while(curr!=NULL);
\r
188 free(ptr); //Free the memory of the old hash table
\r
192 //Delete the entire hash table
\r
193 void hashRCRDelete() {
\r
194 dcliststruct_t *ptr=dc_c_structs;
\r
196 dcliststruct_t *next=ptr->next;
\r
206 // Search for an address for a given Address
\r
207 INLINE int hashRCRSearch(void * objectPtr, int traverserState) {
\r
208 //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
\r
209 dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)objectPtr) & dc_c_mask)>>SHIFTBITS];
\r
212 if(node->object == objectPtr && node->traverserState == traverserState) {
\r
216 } while(node != NULL);
\r