Robust/src/Runtime/STM/stmlookup.c

   1 #include "stmlookup.h"
   2 #include "strings.h"
   3
   4 __thread chashlistnode_t *c_table;
   5 __thread chashlistnode_t *c_list;
   6 __thread unsigned int c_size;
   7 __thread unsigned INTPTR c_mask;
   8 __thread unsigned int c_numelements;
   9 __thread unsigned int c_threshold;
  10 __thread double c_loadfactor;
  11 __thread cliststruct_t *c_structs;
  12
  13 #ifdef DELAYCOMP
  14 __thread chashlistnode_t *dc_c_table;
  15 __thread chashlistnode_t *dc_c_list;
  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;
  21 __thread cliststruct_t *dc_c_structs;
  22
  23 void dc_t_chashCreate(unsigned int size, double loadfactor) {
  24   chashtable_t *ctable;
  25   chashlistnode_t *nodes;
  26   int i;
  27
  28   // Allocate space for the hash table
  29
  30   dc_c_table = calloc(size, sizeof(chashlistnode_t));
  31   dc_c_loadfactor = loadfactor;
  32   dc_c_size = size;
  33   dc_c_threshold=size*loadfactor;
  34   dc_c_mask = (size << 4)-1;
  35   dc_c_structs=calloc(1, sizeof(cliststruct_t));
  36   dc_c_numelements = 0; // Initial number of elements in the hash
  37   dc_c_list=NULL;
  38 }
  39
  40 void dc_t_chashreset() {
  41   chashlistnode_t *ptr = dc_c_table;
  42   int i;
  43
  44   if (dc_c_numelements<(dc_c_size>>4)) {
  45     chashlistnode_t *top=&ptr[dc_c_size];
  46     chashlistnode_t *tmpptr=dc_c_list;
  47     while(tmpptr!=NULL) {
  48       chashlistnode_t *next=tmpptr->lnext;
  49       if (tmpptr>=ptr&&tmpptr<top) {
  50         //zero in list
  51         tmpptr->key=0;
  52         tmpptr->next=NULL;
  53       }
  54       tmpptr=next;
  55     }
  56   } else {
  57     bzero(dc_c_table, sizeof(chashlistnode_t)*dc_c_size);
  58   }
  59   while(dc_c_structs->next!=NULL) {
  60     cliststruct_t *next=dc_c_structs->next;
  61     free(dc_c_structs);
  62     dc_c_structs=next;
  63   }
  64   dc_c_structs->num = 0;
  65   dc_c_numelements = 0;
  66   dc_c_list=NULL;
  67 }
  68
  69 //Store objects and their pointers into hash
  70 void dc_t_chashInsertOnce(void * key, void *val) {
  71   chashlistnode_t *ptr;
  72
  73
  74   if(dc_c_numelements > (dc_c_threshold)) {
  75     //Resize
  76     unsigned int newsize = dc_c_size << 1;
  77     dc_t_chashResize(newsize);
  78   }
  79
  80   ptr = &dc_c_table[(((unsigned INTPTR)key)&dc_c_mask)>>4];
  81
  82   if(ptr->key==0) {
  83     ptr->key=key;
  84     ptr->val=val;
  85     ptr->lnext=dc_c_list;
  86     dc_c_list=ptr;
  87     dc_c_numelements++;
  88   } else { // Insert in the beginning of linked list
  89     chashlistnode_t * node;
  90     chashlistnode_t *search=ptr;
  91
  92     //make sure it isn't here
  93     do {
  94       if(search->key == key) {
  95         return;
  96       }
  97       search=search->next;
  98     } while(search != NULL);
  99
 100     dc_c_numelements++;
 101     if (dc_c_structs->num<NUMCLIST) {
 102       node=&dc_c_structs->array[dc_c_structs->num];
 103       dc_c_structs->num++;
 104     } else {
 105       //get new list
 106       cliststruct_t *tcl=calloc(1,sizeof(cliststruct_t));
 107       tcl->next=dc_c_structs;
 108       dc_c_structs=tcl;
 109       node=&tcl->array[0];
 110       tcl->num=1;
 111     }
 112     node->key = key;
 113     node->val = val;
 114     node->next = ptr->next;
 115     ptr->next=node;
 116     node->lnext=dc_c_list;
 117     dc_c_list=node;
 118   }
 119 }
 120
 121 unsigned int dc_t_chashResize(unsigned int newsize) {
 122   chashlistnode_t *node, *ptr, *curr;    // curr and next keep track of the current and the next chashlistnodes in a linked list
 123   unsigned int oldsize;
 124   int isfirst;    // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
 125   unsigned int i,index;
 126   unsigned int mask;
 127
 128   ptr = dc_c_table;
 129   oldsize = dc_c_size;
 130   dc_c_list=NULL;
 131
 132   if((node = calloc(newsize, sizeof(chashlistnode_t))) == NULL) {
 133     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 134     return 1;
 135   }
 136
 137   dc_c_table = node;          //Update the global hashtable upon resize()
 138   dc_c_size = newsize;
 139   dc_c_threshold = newsize * dc_c_loadfactor;
 140   mask=dc_c_mask = (newsize << 4)-1;
 141
 142   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 143     curr = &ptr[i];
 144     isfirst = 1;
 145     do {                      //Inner loop to go through linked lists
 146       void * key;
 147       chashlistnode_t *tmp,*next;
 148
 149       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element is 0
 150         break;                  //key = val =0 for element if not present within the hash table
 151       }
 152       index = (((unsigned INTPTR)key) & mask) >>4;
 153       tmp=&node[index];
 154       next = curr->next;
 155       // Insert into the new table
 156       if(tmp->key == 0) {
 157         tmp->key = key;
 158         tmp->val = curr->val;
 159         tmp->lnext=dc_c_list;
 160         dc_c_list=tmp;
 161       } /*
 162           NOTE:  Add this case if you change this...
 163           This case currently never happens because of the way things rehash....
 164           else if (isfirst) {
 165           chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
 166           newnode->key = curr->key;
 167           newnode->val = curr->val;
 168           newnode->next = tmp->next;
 169           tmp->next=newnode;
 170           } */
 171       else {
 172         curr->next=tmp->next;
 173         tmp->next=curr;
 174         curr->lnext=dc_c_list;
 175         dc_c_list=curr;
 176       }
 177
 178       isfirst = 0;
 179       curr = next;
 180     } while(curr!=NULL);
 181   }
 182
 183   free(ptr);            //Free the memory of the old hash table
 184   return 0;
 185 }
 186
 187 //Delete the entire hash table
 188 void dc_t_chashDelete() {
 189   int i;
 190   cliststruct_t *ptr=dc_c_structs;
 191   while(ptr!=NULL) {
 192     cliststruct_t *next=ptr->next;
 193     free(ptr);
 194     ptr=next;
 195   }
 196   free(dc_c_table);
 197   dc_c_table=NULL;
 198   dc_c_structs=NULL;
 199   dc_c_list=NULL;
 200 }
 201 #endif
 202
 203 void t_chashCreate(unsigned int size, double loadfactor) {
 204   chashtable_t *ctable;
 205   chashlistnode_t *nodes;
 206   int i;
 207
 208   // Allocate space for the hash table
 209
 210
 211   c_table = calloc(size, sizeof(chashlistnode_t));
 212   c_loadfactor = loadfactor;
 213   c_size = size;
 214   c_threshold=size*loadfactor;
 215   c_mask = (size << 4)-1;
 216   c_structs=calloc(1, sizeof(cliststruct_t));
 217   c_numelements = 0; // Initial number of elements in the hash
 218   c_list=NULL;
 219 }
 220
 221 void t_chashreset() {
 222   chashlistnode_t *ptr = c_table;
 223   int i;
 224
 225   if (c_numelements<(c_size>>4)) {
 226     chashlistnode_t *top=&ptr[c_size];
 227     chashlistnode_t *tmpptr=c_list;
 228     while(tmpptr!=NULL) {
 229       chashlistnode_t *next=tmpptr->lnext;
 230       if (tmpptr>=ptr&&tmpptr<top) {
 231         //zero in list
 232         tmpptr->key=0;
 233         tmpptr->next=NULL;
 234       }
 235       tmpptr=next;
 236     }
 237   } else {
 238     bzero(c_table, sizeof(chashlistnode_t)*c_size);
 239   }
 240   while(c_structs->next!=NULL) {
 241     cliststruct_t *next=c_structs->next;
 242     free(c_structs);
 243     c_structs=next;
 244   }
 245   c_structs->num = 0;
 246   c_numelements = 0;
 247   c_list=NULL;
 248 }
 249
 250 //Store objects and their pointers into hash
 251 void t_chashInsert(void * key, void *val) {
 252   chashlistnode_t *ptr;
 253
 254
 255   if(c_numelements > (c_threshold)) {
 256     //Resize
 257     unsigned int newsize = c_size << 1;
 258     t_chashResize(newsize);
 259   }
 260
 261   ptr = &c_table[(((unsigned INTPTR)key)&c_mask)>>4];
 262   c_numelements++;
 263
 264   if(ptr->key==0) {
 265     ptr->key=key;
 266     ptr->val=val;
 267     ptr->lnext=c_list;
 268     c_list=ptr;
 269   } else { // Insert in the beginning of linked list
 270     chashlistnode_t * node;
 271     if (c_structs->num<NUMCLIST) {
 272       node=&c_structs->array[c_structs->num];
 273       c_structs->num++;
 274     } else {
 275       //get new list
 276       cliststruct_t *tcl=calloc(1,sizeof(cliststruct_t));
 277       tcl->next=c_structs;
 278       c_structs=tcl;
 279       node=&tcl->array[0];
 280       tcl->num=1;
 281     }
 282     node->key = key;
 283     node->val = val;
 284     node->next = ptr->next;
 285     ptr->next=node;
 286     node->lnext=c_list;
 287     c_list=node;
 288   }
 289 }
 290
 291 // Search for an address for a given oid
 292 INLINE void * t_chashSearch(void * key) {
 293   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
 294   chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
 295
 296   do {
 297     if(node->key == key) {
 298       return node->val;
 299     }
 300     node = node->next;
 301   } while(node != NULL);
 302
 303   return NULL;
 304 }
 305
 306 unsigned int t_chashResize(unsigned int newsize) {
 307   chashlistnode_t *node, *ptr, *curr;    // curr and next keep track of the current and the next chashlistnodes in a linked list
 308   unsigned int oldsize;
 309   int isfirst;    // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
 310   unsigned int i,index;
 311   unsigned int mask;
 312
 313   ptr = c_table;
 314   oldsize = c_size;
 315   c_list=NULL;
 316
 317   if((node = calloc(newsize, sizeof(chashlistnode_t))) == NULL) {
 318     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 319     return 1;
 320   }
 321
 322   c_table = node;          //Update the global hashtable upon resize()
 323   c_size = newsize;
 324   c_threshold = newsize * c_loadfactor;
 325   mask=c_mask = (newsize << 4)-1;
 326
 327   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 328     curr = &ptr[i];
 329     isfirst = 1;
 330     do {                      //Inner loop to go through linked lists
 331       void * key;
 332       chashlistnode_t *tmp,*next;
 333
 334       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element is 0
 335         break;                  //key = val =0 for element if not present within the hash table
 336       }
 337       index = (((unsigned INTPTR)key) & mask) >>4;
 338       tmp=&node[index];
 339       next = curr->next;
 340       // Insert into the new table
 341       if(tmp->key == 0) {
 342         tmp->key = key;
 343         tmp->val = curr->val;
 344         tmp->lnext=c_list;
 345         c_list=tmp;
 346       } /*
 347           NOTE:  Add this case if you change this...
 348           This case currently never happens because of the way things rehash....
 349           else if (isfirst) {
 350           chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
 351           newnode->key = curr->key;
 352           newnode->val = curr->val;
 353           newnode->next = tmp->next;
 354           tmp->next=newnode;
 355           } */
 356       else {
 357         curr->next=tmp->next;
 358         tmp->next=curr;
 359         curr->lnext=c_list;
 360         c_list=curr;
 361       }
 362
 363       isfirst = 0;
 364       curr = next;
 365     } while(curr!=NULL);
 366   }
 367
 368   free(ptr);            //Free the memory of the old hash table
 369   return 0;
 370 }
 371
 372 //Delete the entire hash table
 373 void t_chashDelete() {
 374   int i;
 375   cliststruct_t *ptr=c_structs;
 376   while(ptr!=NULL) {
 377     cliststruct_t *next=ptr->next;
 378     free(ptr);
 379     ptr=next;
 380   }
 381   free(c_table);
 382   c_table=NULL;
 383   c_structs=NULL;
 384   c_list=NULL;
 385 }