Robust/src/Runtime/STM/stmlookup.c

   1 #include "stmlookup.h"
   2 #include "strings.h"
   3 #include "tm.h"
   4
   5 __thread chashlistnode_t *c_table;
   6 __thread chashlistnode_t *c_list;
   7 __thread unsigned int c_size;
   8 __thread unsigned INTPTR c_mask;
   9 __thread unsigned int c_numelements;
  10 __thread unsigned int c_threshold;
  11 __thread double c_loadfactor;
  12 __thread cliststruct_t *c_structs;
  13
  14 #ifdef READSET
  15 __thread rdchashlistnode_t *rd_c_table;
  16 __thread rdchashlistnode_t *rd_c_list;
  17 __thread unsigned int rd_c_size;
  18 __thread unsigned INTPTR rd_c_mask;
  19 __thread unsigned int rd_c_numelements;
  20 __thread unsigned int rd_c_threshold;
  21 __thread double rd_c_loadfactor;
  22 __thread rdcliststruct_t *rd_c_structs;
  23
  24 void rd_t_chashCreate(unsigned int size, double loadfactor) {
  25   chashtable_t *ctable;
  26   chashlistnode_t *nodes;
  27   int i;
  28
  29   // Allocate space for the hash table
  30   rd_c_table = calloc(size, sizeof(rdchashlistnode_t));
  31   rd_c_loadfactor = loadfactor;
  32   rd_c_size = size;
  33   rd_c_threshold=size*loadfactor;
  34   rd_c_mask = (size << 4)-1;
  35   rd_c_structs=calloc(1, sizeof(rdcliststruct_t));
  36   rd_c_numelements = 0; // Initial number of elements in the hash
  37   rd_c_list=NULL;
  38 }
  39
  40 void rd_t_chashreset() {
  41   rdchashlistnode_t *ptr = rd_c_table;
  42   int i;
  43
  44   if (rd_c_numelements<(rd_c_size>>4)) {
  45     rdchashlistnode_t *top=&ptr[rd_c_size];
  46     rdchashlistnode_t *tmpptr=rd_c_list;
  47     while(tmpptr!=NULL) {
  48       rdchashlistnode_t *next=tmpptr->lnext;
  49       if (tmpptr>=ptr&&tmpptr<top) {
  50         //zero in list
  51         tmpptr->key=NULL;
  52         tmpptr->next=NULL;
  53       }
  54       tmpptr=next;
  55     }
  56   } else {
  57     bzero(rd_c_table, sizeof(rdchashlistnode_t)*rd_c_size);
  58   }
  59   while(rd_c_structs->next!=NULL) {
  60     rdcliststruct_t *next=rd_c_structs->next;
  61     free(rd_c_structs);
  62     rd_c_structs=next;
  63   }
  64   rd_c_structs->num = 0;
  65   rd_c_numelements = 0;
  66   rd_c_list=NULL;
  67 }
  68
  69 //Store objects and their pointers into hash
  70 void rd_t_chashInsertOnce(void * key, unsigned int version) {
  71   rdchashlistnode_t *ptr;
  72
  73   if (unlikely(key==NULL))
  74     return;
  75
  76   if(unlikely(rd_c_numelements > (rd_c_threshold))) {
  77     //Resize
  78     unsigned int newsize = rd_c_size << 1;
  79     rd_t_chashResize(newsize);
  80   }
  81
  82   ptr = &rd_c_table[(((unsigned INTPTR)key)&rd_c_mask)>>4];
  83
  84   if(ptr->key==0) {
  85     ptr->key=key;
  86     ptr->version=version;
  87     ptr->lnext=rd_c_list;
  88     rd_c_list=ptr;
  89     rd_c_numelements++;
  90   } else { // Insert in the beginning of linked list
  91     rdchashlistnode_t * node;
  92     rdchashlistnode_t *search=ptr;
  93
  94     //make sure it isn't here
  95     do {
  96       if(search->key == key) {
  97         return;
  98       }
  99       search=search->next;
 100     } while(search != NULL);
 101
 102     rd_c_numelements++;
 103     if (rd_c_structs->num<NUMCLIST) {
 104       node=&rd_c_structs->array[rd_c_structs->num];
 105       rd_c_structs->num++;
 106     } else {
 107       //get new list
 108       rdcliststruct_t *tcl=calloc(1,sizeof(rdcliststruct_t));
 109       tcl->next=rd_c_structs;
 110       rd_c_structs=tcl;
 111       node=&tcl->array[0];
 112       tcl->num=1;
 113     }
 114     node->key = key;
 115     node->version = version;
 116     node->next = ptr->next;
 117     ptr->next=node;
 118     node->lnext=rd_c_list;
 119     rd_c_list=node;
 120   }
 121 }
 122
 123 unsigned int rd_t_chashResize(unsigned int newsize) {
 124   rdchashlistnode_t *node, *ptr, *curr;    // curr and next keep track of the current and the next chashlistnodes in a linked list
 125   unsigned int oldsize;
 126   int isfirst;    // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
 127   unsigned int i,index;
 128   unsigned int mask;
 129
 130   ptr = rd_c_table;
 131   oldsize = rd_c_size;
 132   rd_c_list=NULL;
 133
 134   if((node = calloc(newsize, sizeof(rdchashlistnode_t))) == NULL) {
 135     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 136     return 1;
 137   }
 138
 139   rd_c_table = node;          //Update the global hashtable upon resize()
 140   rd_c_size = newsize;
 141   rd_c_threshold = newsize * rd_c_loadfactor;
 142   mask=rd_c_mask = (newsize << 4)-1;
 143
 144   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 145     curr = &ptr[i];
 146     isfirst = 1;
 147     do {                      //Inner loop to go through linked lists
 148       void * key;
 149       rdchashlistnode_t *tmp,*next;
 150
 151       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element is 0
 152         break;                  //key = val =0 for element if not present within the hash table
 153       }
 154       index = (((unsigned INTPTR)key) & mask) >>4;
 155       tmp=&node[index];
 156       next = curr->next;
 157       // Insert into the new table
 158       if(tmp->key == 0) {
 159         tmp->key = key;
 160         tmp->version = curr->version;
 161         tmp->lnext=rd_c_list;
 162         rd_c_list=tmp;
 163       } /*
 164           NOTE:  Add this case if you change this...
 165           This case currently never happens because of the way things rehash....
 166           else if (isfirst) {
 167           chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
 168           newnode->key = curr->key;
 169           newnode->val = curr->val;
 170           newnode->next = tmp->next;
 171           tmp->next=newnode;
 172           } */
 173       else {
 174         curr->next=tmp->next;
 175         tmp->next=curr;
 176         curr->lnext=rd_c_list;
 177         rd_c_list=curr;
 178       }
 179
 180       isfirst = 0;
 181       curr = next;
 182     } while(curr!=NULL);
 183   }
 184
 185   free(ptr);            //Free the memory of the old hash table
 186   return 0;
 187 }
 188
 189 //Delete the entire hash table
 190 void rd_t_chashDelete() {
 191   int i;
 192   rdcliststruct_t *ptr=rd_c_structs;
 193   while(ptr!=NULL) {
 194     rdcliststruct_t *next=ptr->next;
 195     free(ptr);
 196     ptr=next;
 197   }
 198   free(rd_c_table);
 199   rd_c_table=NULL;
 200   rd_c_structs=NULL;
 201   rd_c_list=NULL;
 202 }
 203 #endif
 204
 205 #ifdef DELAYCOMP
 206 __thread dchashlistnode_t *dc_c_table;
 207 __thread dchashlistnode_t *dc_c_list;
 208 __thread unsigned int dc_c_size;
 209 __thread unsigned INTPTR dc_c_mask;
 210 __thread unsigned int dc_c_numelements;
 211 __thread unsigned int dc_c_threshold;
 212 __thread double dc_c_loadfactor;
 213 __thread dcliststruct_t *dc_c_structs;
 214
 215 void dc_t_chashCreate(unsigned int size, double loadfactor) {
 216   dchashlistnode_t *nodes;
 217   int i;
 218
 219   // Allocate space for the hash table
 220
 221   dc_c_table = calloc(size, sizeof(dchashlistnode_t));
 222   dc_c_loadfactor = loadfactor;
 223   dc_c_size = size;
 224   dc_c_threshold=size*loadfactor;
 225   dc_c_mask = (size << 4)-1;
 226   dc_c_structs=calloc(1, sizeof(dcliststruct_t));
 227   dc_c_numelements = 0; // Initial number of elements in the hash
 228   dc_c_list=NULL;
 229 }
 230
 231 void dc_t_chashreset() {
 232   dchashlistnode_t *ptr = dc_c_table;
 233   int i;
 234
 235   if (dc_c_numelements<(dc_c_size>>4)) {
 236     dchashlistnode_t *top=&ptr[dc_c_size];
 237     dchashlistnode_t *tmpptr=dc_c_list;
 238     while(tmpptr!=NULL) {
 239       dchashlistnode_t *next=tmpptr->lnext;
 240       if (tmpptr>=ptr&&tmpptr<top) {
 241         //zero in list
 242         tmpptr->key=NULL;
 243         tmpptr->next=NULL;
 244       }
 245       tmpptr=next;
 246     }
 247   } else {
 248     bzero(dc_c_table, sizeof(dchashlistnode_t)*dc_c_size);
 249   }
 250   while(dc_c_structs->next!=NULL) {
 251     dcliststruct_t *next=dc_c_structs->next;
 252     free(dc_c_structs);
 253     dc_c_structs=next;
 254   }
 255   dc_c_structs->num = 0;
 256   dc_c_numelements = 0;
 257   dc_c_list=NULL;
 258 }
 259
 260 //Store objects and their pointers into hash
 261 void dc_t_chashInsertOnce(void * key) {
 262   dchashlistnode_t *ptr;
 263
 264   if (unlikely(key==NULL)) {
 265     return;
 266   }
 267
 268   if(unlikely(dc_c_numelements > dc_c_threshold)) {
 269     //Resize
 270     unsigned int newsize = dc_c_size << 1;
 271     dc_t_chashResize(newsize);
 272   }
 273   ptr = &dc_c_table[(((unsigned INTPTR)key)&dc_c_mask)>>4];
 274   if(likely(ptr->key==0)) {
 275     ptr->key=key;
 276 #if defined(STMARRAY)&&!defined(DUALVIEW)
 277     ptr->intkey=-1;
 278 #endif
 279     ptr->lnext=dc_c_list;
 280     dc_c_list=ptr;
 281     dc_c_numelements++;
 282   } else { // Insert in the beginning of linked list
 283     dchashlistnode_t * node;
 284     dchashlistnode_t *search=ptr;
 285
 286     //make sure it isn't here
 287     do {
 288       if(search->key == key) {
 289         return;
 290       }
 291       search=search->next;
 292     } while(search != NULL);
 293
 294     dc_c_numelements++;
 295     if (likely(dc_c_structs->num<NUMCLIST)) {
 296       node=&dc_c_structs->array[dc_c_structs->num];
 297       dc_c_structs->num++;
 298     } else {
 299       //get new list
 300       dcliststruct_t *tcl=calloc(1,sizeof(dcliststruct_t));
 301       tcl->next=dc_c_structs;
 302       dc_c_structs=tcl;
 303       node=&tcl->array[0];
 304       tcl->num=1;
 305     }
 306 #if defined(STMARRAY)&&!defined(DUALVIEW)
 307     node->intkey=-1;
 308 #endif
 309     node->key = key;
 310     node->next = ptr->next;
 311     ptr->next=node;
 312     node->lnext=dc_c_list;
 313     dc_c_list=node;
 314   }
 315 }
 316
 317 #if defined(STMARRAY)&&!defined(DUALVIEW)
 318 //Store objects and their pointers into hash
 319 void dc_t_chashInsertOnceArray(void * key, unsigned int intkey) {
 320   dchashlistnode_t *ptr;
 321
 322   if (unlikely(key==NULL))
 323     return;
 324
 325   if(unlikely(dc_c_numelements > dc_c_threshold)) {
 326     //Resize
 327     unsigned int newsize = dc_c_size << 1;
 328     dc_t_chashResize(newsize);
 329   }
 330
 331   ptr = &dc_c_table[(((unsigned INTPTR)key^(intkey<<4))&dc_c_mask)>>4];
 332
 333   if(ptr->key==0) {
 334     ptr->key=key;
 335     ptr->intkey=intkey;
 336     ptr->lnext=dc_c_list;
 337     dc_c_list=ptr;
 338     dc_c_numelements++;
 339   } else { // Insert in the beginning of linked list
 340     dchashlistnode_t * node;
 341     dchashlistnode_t *search=ptr;
 342
 343     //make sure it isn't here
 344     do {
 345       if(search->key == key&&search->intkey==intkey) {
 346         return;
 347       }
 348       search=search->next;
 349     } while(search != NULL);
 350
 351     dc_c_numelements++;
 352     if (likely(dc_c_structs->num<NUMCLIST)) {
 353       node=&dc_c_structs->array[dc_c_structs->num];
 354       dc_c_structs->num++;
 355     } else {
 356       //get new list
 357       dcliststruct_t *tcl=calloc(1,sizeof(dcliststruct_t));
 358       tcl->next=dc_c_structs;
 359       dc_c_structs=tcl;
 360       node=&tcl->array[0];
 361       tcl->num=1;
 362     }
 363     node->key = key;
 364     node->intkey = intkey;
 365     node->next = ptr->next;
 366     ptr->next=node;
 367     node->lnext=dc_c_list;
 368     dc_c_list=node;
 369   }
 370 }
 371 #endif
 372
 373 unsigned int dc_t_chashResize(unsigned int newsize) {
 374   dchashlistnode_t *node, *ptr, *curr;    // curr and next keep track of the current and the next chashlistnodes in a linked list
 375   unsigned int oldsize;
 376   int isfirst;    // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
 377   unsigned int i,index;
 378   unsigned int mask;
 379
 380   ptr = dc_c_table;
 381   oldsize = dc_c_size;
 382   dc_c_list=NULL;
 383
 384   if((node = calloc(newsize, sizeof(dchashlistnode_t))) == NULL) {
 385     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 386     return 1;
 387   }
 388
 389   dc_c_table = node;          //Update the global hashtable upon resize()
 390   dc_c_size = newsize;
 391   dc_c_threshold = newsize * dc_c_loadfactor;
 392   mask=dc_c_mask = (newsize << 4)-1;
 393
 394   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 395     curr = &ptr[i];
 396     isfirst = 1;
 397     do {                      //Inner loop to go through linked lists
 398       void * key;
 399 #if defined(STMARRAY)&&!defined(DUALVIEW)
 400       unsigned int intkey;
 401 #endif
 402       dchashlistnode_t *tmp,*next;
 403
 404       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element is 0
 405         break;                  //key = val =0 for element if not present within the hash table
 406       }
 407 #if defined(STMARRAY)&&!defined(DUALVIEW)
 408       intkey=curr->intkey;
 409       index = (((unsigned INTPTR)key^(intkey<<4)) & mask) >>4;
 410 #else
 411       index = (((unsigned INTPTR)key) & mask) >>4;
 412 #endif
 413       tmp=&node[index];
 414       next = curr->next;
 415       // Insert into the new table
 416       if(tmp->key == 0) {
 417         tmp->key = key;
 418 #if defined(STMARRAY)&!defined(DUALVIEW)
 419         tmp->intkey = intkey;
 420 #endif
 421         tmp->lnext=dc_c_list;
 422         dc_c_list=tmp;
 423       } /*
 424           NOTE:  Add this case if you change this...
 425           This case currently never happens because of the way things rehash....
 426           else if (isfirst) {
 427           chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
 428           newnode->key = curr->key;
 429           newnode->val = curr->val;
 430           newnode->next = tmp->next;
 431           tmp->next=newnode;
 432           } */
 433       else {
 434         curr->next=tmp->next;
 435         tmp->next=curr;
 436         curr->lnext=dc_c_list;
 437         dc_c_list=curr;
 438       }
 439
 440       isfirst = 0;
 441       curr = next;
 442     } while(curr!=NULL);
 443   }
 444
 445   free(ptr);            //Free the memory of the old hash table
 446   return 0;
 447 }
 448
 449 //Delete the entire hash table
 450 void dc_t_chashDelete() {
 451   int i;
 452   dcliststruct_t *ptr=dc_c_structs;
 453   while(ptr!=NULL) {
 454     dcliststruct_t *next=ptr->next;
 455     free(ptr);
 456     ptr=next;
 457   }
 458   free(dc_c_table);
 459   dc_c_table=NULL;
 460   dc_c_structs=NULL;
 461   dc_c_list=NULL;
 462 }
 463
 464 // Search for an address for a given oid
 465 INLINE int dc_t_chashSearch(void * key) {
 466   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
 467   dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)key) & dc_c_mask)>>4];
 468
 469   do {
 470     if(node->key == key) {
 471       return 1;
 472     }
 473     node = node->next;
 474   } while(node != NULL);
 475
 476   return 0;
 477 }
 478
 479 #if defined(STMARRAY)&!defined(DUALVIEW)
 480 // Search for an address for a given oid
 481 INLINE int dc_t_chashSearchArray(void * key, unsigned int intkey) {
 482   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
 483   dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)key^intkey) & dc_c_mask)>>4];
 484
 485   do {
 486     if(node->key == key && node->intkey==intkey) {
 487       return 1;
 488     }
 489     node = node->next;
 490   } while(node != NULL);
 491
 492   return 0;
 493 }
 494 #endif
 495
 496 #endif
 497
 498 void t_chashCreate(unsigned int size, double loadfactor) {
 499   chashtable_t *ctable;
 500   chashlistnode_t *nodes;
 501   int i;
 502
 503   // Allocate space for the hash table
 504
 505
 506   c_table = calloc(size, sizeof(chashlistnode_t));
 507   c_loadfactor = loadfactor;
 508   c_size = size;
 509   c_threshold=size*loadfactor;
 510 #ifdef BIT64
 511   c_mask = ((size << 4)-1)&~(15UL);
 512 #else
 513   c_mask = ((size << 4)-1)&~15;
 514 #endif
 515   c_structs=calloc(1, sizeof(cliststruct_t));
 516   c_numelements = 0; // Initial number of elements in the hash
 517   c_list=NULL;
 518 }
 519
 520 void t_chashreset() {
 521   chashlistnode_t *ptr = c_table;
 522   int i;
 523
 524   if (c_numelements<(c_size>>4)) {
 525     chashlistnode_t *top=&ptr[c_size];
 526     chashlistnode_t *tmpptr=c_list;
 527     while(tmpptr!=NULL) {
 528       chashlistnode_t *next=tmpptr->lnext;
 529       if (tmpptr>=ptr&&tmpptr<top) {
 530         //zero in list
 531         tmpptr->key=NULL;
 532         tmpptr->next=NULL;
 533       }
 534       tmpptr=next;
 535     }
 536   } else {
 537     bzero(c_table, sizeof(chashlistnode_t)*c_size);
 538   }
 539   while(c_structs->next!=NULL) {
 540     cliststruct_t *next=c_structs->next;
 541     free(c_structs);
 542     c_structs=next;
 543   }
 544   c_structs->num = 0;
 545   c_numelements = 0;
 546   c_list=NULL;
 547 }
 548
 549 //Store objects and their pointers into hash
 550 void t_chashInsert(void * key, void *val) {
 551   chashlistnode_t *ptr;
 552
 553
 554   if(c_numelements > (c_threshold)) {
 555     //Resize
 556     unsigned int newsize = c_size << 1;
 557     t_chashResize(newsize);
 558   }
 559
 560   ptr = &c_table[(((unsigned INTPTR)key)&c_mask)>>4];
 561   c_numelements++;
 562
 563   if(ptr->key==0) {
 564     ptr->key=key;
 565     ptr->val=val;
 566     ptr->lnext=c_list;
 567     c_list=ptr;
 568   } else { // Insert in the beginning of linked list
 569     chashlistnode_t * node;
 570     if (c_structs->num<NUMCLIST) {
 571       node=&c_structs->array[c_structs->num];
 572       c_structs->num++;
 573     } else {
 574       //get new list
 575       cliststruct_t *tcl=calloc(1,sizeof(cliststruct_t));
 576       tcl->next=c_structs;
 577       c_structs=tcl;
 578       node=&tcl->array[0];
 579       tcl->num=1;
 580     }
 581     node->key = key;
 582     node->val = val;
 583     node->next = ptr->next;
 584     ptr->next=node;
 585     node->lnext=c_list;
 586     c_list=node;
 587   }
 588 }
 589
 590 // Search for an address for a given oid
 591 INLINE void * t_chashSearch(void * key) {
 592   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
 593   chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
 594
 595   do {
 596     if(node->key == key) {
 597       return node->val;
 598     }
 599     node = node->next;
 600   } while(node != NULL);
 601
 602   return NULL;
 603 }
 604
 605 unsigned int t_chashResize(unsigned int newsize) {
 606   chashlistnode_t *node, *ptr, *curr;    // curr and next keep track of the current and the next chashlistnodes in a linked list
 607   unsigned int oldsize;
 608   int isfirst;    // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
 609   unsigned int i,index;
 610   unsigned int mask;
 611
 612   ptr = c_table;
 613   oldsize = c_size;
 614   c_list=NULL;
 615
 616   if((node = calloc(newsize, sizeof(chashlistnode_t))) == NULL) {
 617     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 618     return 1;
 619   }
 620
 621   c_table = node;          //Update the global hashtable upon resize()
 622   c_size = newsize;
 623   c_threshold = newsize * c_loadfactor;
 624   mask=c_mask = (newsize << 4)-1;
 625
 626   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 627     curr = &ptr[i];
 628     isfirst = 1;
 629     do {                      //Inner loop to go through linked lists
 630       void * key;
 631       chashlistnode_t *tmp,*next;
 632
 633       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element is 0
 634         break;                  //key = val =0 for element if not present within the hash table
 635       }
 636       index = (((unsigned INTPTR)key) & mask) >>4;
 637       tmp=&node[index];
 638       next = curr->next;
 639       // Insert into the new table
 640       if(tmp->key == 0) {
 641         tmp->key = key;
 642         tmp->val = curr->val;
 643         tmp->lnext=c_list;
 644         c_list=tmp;
 645       } /*
 646           NOTE:  Add this case if you change this...
 647           This case currently never happens because of the way things rehash....
 648           else if (isfirst) {
 649           chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
 650           newnode->key = curr->key;
 651           newnode->val = curr->val;
 652           newnode->next = tmp->next;
 653           tmp->next=newnode;
 654           } */
 655       else {
 656         curr->next=tmp->next;
 657         tmp->next=curr;
 658         curr->lnext=c_list;
 659         c_list=curr;
 660       }
 661
 662       isfirst = 0;
 663       curr = next;
 664     } while(curr!=NULL);
 665   }
 666
 667   free(ptr);            //Free the memory of the old hash table
 668   return 0;
 669 }
 670
 671 //Delete the entire hash table
 672 void t_chashDelete() {
 673   int i;
 674   cliststruct_t *ptr=c_structs;
 675   while(ptr!=NULL) {
 676     cliststruct_t *next=ptr->next;
 677     free(ptr);
 678     ptr=next;
 679   }
 680   free(c_table);
 681   c_table=NULL;
 682   c_structs=NULL;
 683   c_list=NULL;
 684 }