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