Robust/src/Runtime/DSTM/interface/clookup.c

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