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 void t_chashCreate(unsigned int size, double loadfactor) {
  14   chashtable_t *ctable;
  15   chashlistnode_t *nodes;
  16   int i;
  17
  18   // Allocate space for the hash table
  19
  20
  21   c_table = calloc(size, sizeof(chashlistnode_t));
  22   c_loadfactor = loadfactor;
  23   c_size = size;
  24   c_threshold=size*loadfactor;
  25   c_mask = (size << 4)-1;
  26   c_structs=calloc(1, sizeof(cliststruct_t));
  27   c_numelements = 0; // Initial number of elements in the hash
  28   c_list=NULL;
  29 }
  30
  31 void t_chashreset() {
  32   chashlistnode_t *ptr = c_table;
  33   int i;
  34
  35   if (c_numelements<(c_size>>4)) {
  36     chashlistnode_t *top=&ptr[c_size];
  37     chashlistnode_t *tmpptr=c_list;
  38     while(tmpptr!=NULL) {
  39       chashlistnode_t *next=tmpptr->lnext;
  40       if (tmpptr>=ptr&&tmpptr<top) {
  41         //zero in list
  42         tmpptr->key=0;
  43         tmpptr->next=NULL;
  44       }
  45       tmpptr=next;
  46     }
  47   } else {
  48     bzero(c_table, sizeof(chashlistnode_t)*c_size);
  49   }
  50   while(c_structs->next!=NULL) {
  51     cliststruct_t *next=c_structs->next;
  52     free(c_structs);
  53     c_structs=next;
  54   }
  55   c_structs->num = 0;
  56   c_numelements = 0;
  57   c_list=NULL;
  58 }
  59
  60 //Store objects and their pointers into hash
  61 void t_chashInsert(void * key, void *val) {
  62   chashlistnode_t *ptr;
  63
  64
  65   if(c_numelements > (c_threshold)) {
  66     //Resize
  67     unsigned int newsize = c_size << 1;
  68     t_chashResize(newsize);
  69   }
  70
  71   ptr = &c_table[(((unsigned INTPTR)key)&c_mask)>>4];
  72   c_numelements++;
  73
  74   if(ptr->key==0) {
  75     ptr->key=key;
  76     ptr->val=val;
  77     ptr->lnext=c_list;
  78     c_list=ptr;
  79   } else { // Insert in the beginning of linked list
  80     chashlistnode_t * node;
  81     if (c_structs->num<NUMCLIST) {
  82       node=&c_structs->array[c_structs->num];
  83       c_structs->num++;
  84     } else {
  85       //get new list
  86       cliststruct_t *tcl=calloc(1,sizeof(cliststruct_t));
  87       tcl->next=c_structs;
  88       c_structs=tcl;
  89       node=&tcl->array[0];
  90       tcl->num=1;
  91     }
  92     node->key = key;
  93     node->val = val;
  94     node->next = ptr->next;
  95     ptr->next=node;
  96     node->lnext=c_list;
  97     c_list=node;
  98   }
  99 }
 100
 101 // Search for an address for a given oid
 102 INLINE void * t_chashSearch(void * key) {
 103   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
 104   chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
 105
 106   do {
 107     if(node->key == key) {
 108       return node->val;
 109     }
 110     node = node->next;
 111   } while(node != NULL);
 112
 113   return NULL;
 114 }
 115
 116 unsigned int t_chashResize(unsigned int newsize) {
 117   chashlistnode_t *node, *ptr, *curr;    // curr and next keep track of the current and the next chashlistnodes in a linked list
 118   unsigned int oldsize;
 119   int isfirst;    // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
 120   unsigned int i,index;
 121   unsigned int mask;
 122
 123   ptr = c_table;
 124   oldsize = c_size;
 125   c_list=NULL;
 126
 127   if((node = calloc(newsize, sizeof(chashlistnode_t))) == NULL) {
 128     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 129     return 1;
 130   }
 131
 132   c_table = node;          //Update the global hashtable upon resize()
 133   c_size = newsize;
 134   c_threshold = newsize * c_loadfactor;
 135   mask=c_mask = (newsize << 4)-1;
 136
 137   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 138     curr = &ptr[i];
 139     isfirst = 1;
 140     do {                      //Inner loop to go through linked lists
 141       void * key;
 142       chashlistnode_t *tmp,*next;
 143
 144       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element is 0
 145         break;                  //key = val =0 for element if not present within the hash table
 146       }
 147       index = (((unsigned INTPTR)key) & mask) >>4;
 148       tmp=&node[index];
 149       next = curr->next;
 150       // Insert into the new table
 151       if(tmp->key == 0) {
 152         tmp->key = key;
 153         tmp->val = curr->val;
 154         tmp->lnext=c_list;
 155         c_list=tmp;
 156       } /*
 157           NOTE:  Add this case if you change this...
 158           This case currently never happens because of the way things rehash....
 159           else if (isfirst) {
 160           chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
 161           newnode->key = curr->key;
 162           newnode->val = curr->val;
 163           newnode->next = tmp->next;
 164           tmp->next=newnode;
 165           } */
 166       else {
 167         curr->next=tmp->next;
 168         tmp->next=curr;
 169         curr->lnext=c_list;
 170         c_list=curr;
 171       }
 172
 173       isfirst = 0;
 174       curr = next;
 175     } while(curr!=NULL);
 176   }
 177
 178   free(ptr);            //Free the memory of the old hash table
 179   return 0;
 180 }
 181
 182 //Delete the entire hash table
 183 void t_chashDelete() {
 184   int i;
 185   cliststruct_t *ptr=c_structs;
 186   while(ptr!=NULL) {
 187     cliststruct_t *next=ptr->next;
 188     free(ptr);
 189     ptr=next;
 190   }
 191   free(c_table);
 192   c_table=NULL;
 193   c_structs=NULL;
 194   c_list=NULL;
 195 }