Robust/src/Runtime/STM/stmlookup.c

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