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

   1 #include "altmlookup.h"
   2 #include "dsmlock.h"
   3 #include <sched.h>
   4
   5 mhashtable_t mlookup;   //Global hash table
   6
   7 // Creates a machine lookup table with size =" size"
   8 unsigned int mhashCreate(unsigned int size, double loadfactor) {
   9   mhashlistnode_t *nodes;
  10   // Allocate space for the hash table
  11   if((nodes = calloc(size, sizeof(mhashlistnode_t))) == NULL) {
  12     printf("Calloc error %s %d\n", __FILE__, __LINE__);
  13     return 1;
  14   }
  15
  16   mlookup.table = nodes;
  17   mlookup.size = size;
  18   mlookup.threshold=size*loadfactor;
  19   mlookup.mask = size -1;
  20   mlookup.numelements = 0;       // Initial number of elements in the hash
  21   mlookup.loadfactor = loadfactor;
  22   int i;
  23   for(i=0; i<NUMLOCKS; i++)
  24     mlookup.larray[i].lock=RW_LOCK_BIAS;
  25   //Initialize the pthread_mutex variable
  26   return 0;
  27 }
  28
  29 // Assign to keys to bins inside hash table
  30 unsigned int mhashFunction(unsigned int key) {
  31   return ( key & mlookup.mask) >>1;
  32 }
  33
  34 // Insert value and key mapping into the hash table
  35 void mhashInsert(unsigned int key, void *val) {
  36   mhashlistnode_t *node;
  37
  38   if (mlookup.numelements > mlookup.threshold) {
  39     //Resize Table
  40     unsigned int newsize = mlookup.size << 1;
  41     mhashResize(newsize);
  42   }
  43
  44   unsigned int keyindex=key>>1;
  45   volatile unsigned int * lockptr=&mlookup.larray[keyindex&LOCKMASK].lock;
  46   while(!write_trylock(lockptr)) {
  47     sched_yield();
  48   }
  49
  50   mhashlistnode_t * ptr = &mlookup.table[keyindex&mlookup.mask];
  51   atomic_inc(&mlookup.numelements);
  52
  53   if(ptr->key ==0) {
  54     ptr->key=key;
  55     ptr->val=val;
  56   } else {                              // Insert in the beginning of linked list
  57     node = calloc(1, sizeof(mhashlistnode_t));
  58     node->key = key;
  59     node->val = val;
  60     node->next = ptr->next;
  61     ptr->next=node;
  62   }
  63   write_unlock(lockptr);
  64 }
  65
  66 // Return val for a given key in the hash table
  67 void *mhashSearch(unsigned int key) {
  68   int index;
  69
  70   unsigned int keyindex=key>>1;
  71   volatile unsigned int * lockptr=&mlookup.larray[keyindex&LOCKMASK].lock;
  72
  73   while(!read_trylock(lockptr)) {
  74     sched_yield();
  75   }
  76
  77   mhashlistnode_t *node = &mlookup.table[keyindex&mlookup.mask];
  78
  79   do {
  80     if(node->key == key) {
  81       void * tmp=node->val;
  82       read_unlock(lockptr);
  83       return tmp;
  84     }
  85     node = node->next;
  86   } while (node!=NULL);
  87   read_unlock(lockptr);
  88   return NULL;
  89 }
  90
  91 // Remove an entry from the hash table
  92 unsigned int mhashRemove(unsigned int key) {
  93   int index;
  94   mhashlistnode_t *prev;
  95   mhashlistnode_t *ptr, *node;
  96
  97   unsigned int keyindex=key>>1;
  98   volatile unsigned int * lockptr=&mlookup.larray[keyindex&LOCKMASK].lock;
  99
 100   while(!write_trylock(lockptr)) {
 101     sched_yield();
 102   }
 103
 104   mhashlistnode_t *curr = &mlookup.table[keyindex&mlookup.mask];
 105
 106   for (; curr != NULL; curr = curr->next) {
 107     if (curr->key == key) {
 108       atomic_dec(&(mlookup.numelements));
 109       if ((curr == &ptr[index]) && (curr->next == NULL)) {
 110         curr->key = 0;
 111         curr->val = NULL;
 112       } else if ((curr == &ptr[index]) && (curr->next != NULL)) {
 113         curr->key = curr->next->key;
 114         curr->val = curr->next->val;
 115         node = curr->next;
 116         curr->next = curr->next->next;
 117         free(node);
 118       } else {
 119         prev->next = curr->next;
 120         free(curr);
 121       }
 122       write_unlock(lockptr);
 123       return 0;
 124     }
 125     prev = curr;
 126   }
 127   write_unlock(lockptr);
 128   return 1;
 129 }
 130
 131 // Resize table
 132 void mhashResize(unsigned int newsize) {
 133   mhashlistnode_t *node, *curr;
 134   int isfirst;
 135   unsigned int i,index;
 136   unsigned int mask;
 137
 138   for(i=0; i<NUMLOCKS; i++) {
 139     volatile unsigned int * lockptr=&mlookup.larray[i].lock;
 140
 141     while(!write_trylock(lockptr)) {
 142       sched_yield();
 143     }
 144   }
 145
 146   if (mlookup.numelements < mlookup.threshold) {
 147     //release lock and return
 148     for(i=0; i<NUMLOCKS; i++) {
 149       volatile unsigned int * lockptr=&mlookup.larray[i].lock;
 150       write_unlock(lockptr);
 151     }
 152     return;
 153   }
 154
 155   mhashlistnode_t * ptr = mlookup.table;
 156   unsigned int oldsize = mlookup.size;
 157
 158   if((node = calloc(newsize, sizeof(mhashlistnode_t))) == NULL) {
 159     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 160     return;
 161   }
 162
 163   mlookup.table = node;
 164   mlookup.size = newsize;
 165   mlookup.threshold=newsize*mlookup.loadfactor;
 166   mask=mlookup.mask = newsize -1;
 167
 168   for(i = 0; i < oldsize; i++) {
 169     curr = &ptr[i];
 170     isfirst = 1;
 171     do {
 172       unsigned int key;
 173       mhashlistnode_t *tmp,*next;
 174
 175       if ((key=curr->key) == 0) {
 176         break;
 177       }
 178       next = curr->next;
 179       index = (key >> 1) & mask;
 180       tmp=&mlookup.table[index];
 181
 182       if(tmp->key ==0) {
 183         tmp->key=curr->key;
 184         tmp->val=curr->val;
 185         if (!isfirst)
 186           free(curr);
 187       } /*
 188
 189            NOTE:  Add this case if you change this...
 190            This case currently never happens because of the way things rehash....
 191            else if (isfirst) {
 192            mhashlistnode_t *newnode = calloc(1, sizeof(mhashlistnode_t));
 193            newnode->key = curr->key;
 194            newnode->val = curr->val;
 195            newnode->next = tmp->next;
 196            tmp->next=newnode;
 197            } */
 198       else {
 199         curr->next=tmp->next;
 200         tmp->next=curr;
 201       }
 202       isfirst = 0;
 203       curr = next;
 204     } while(curr!=NULL);
 205   }
 206
 207   free(ptr);
 208   for(i=0; i<NUMLOCKS; i++) {
 209     volatile unsigned int * lockptr=&mlookup.larray[i].lock;
 210     write_unlock(lockptr);
 211   }
 212   return;
 213 }
 214 /*
 215    unsigned int *mhashGetKeys(unsigned int *numKeys) {
 216    unsigned int *keys;
 217    int i, keyindex;
 218    mhashlistnode_t *curr;
 219
 220    pthread_mutex_lock(&mlookup.locktable);
 221
 222  *numKeys = mlookup.numelements;
 223    keys = calloc(*numKeys, sizeof(unsigned int));
 224
 225    keyindex = 0;
 226    for (i = 0; i < mlookup.size; i++) {
 227     if (mlookup.table[i].key != 0) {
 228       curr = &mlookup.table[i];
 229       while (curr != NULL) {
 230         keys[keyindex++] = curr->key;
 231         curr = curr->next;
 232       }
 233     }
 234    }
 235
 236    if (keyindex != *numKeys)
 237     printf("mhashGetKeys(): WARNING: incorrect mlookup.numelements value!\n");
 238
 239    pthread_mutex_unlock(&mlookup.locktable);
 240    return keys;
 241    }*/
 242