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

   1 /* LOCK THE ENTIRE HASH TABLE */
   2 #include "prelookup.h"
   3
   4 prehashtable_t pflookup; //Global prefetch cache table
   5
   6 unsigned int prehashCreate(unsigned int size, float loadfactor) {
   7   prehashlistnode_t *nodes;
   8   int i;
   9
  10   // Allocate space for the hash table
  11   if((nodes = calloc(size, sizeof(prehashlistnode_t))) == NULL) {
  12     printf("Calloc error %s %d\n", __FILE__, __LINE__);
  13     return 1;
  14   }
  15
  16   pflookup.table = nodes;
  17   pflookup.size = size;
  18   pflookup.numelements = 0; // Initial number of elements in the hash
  19   pflookup.loadfactor = loadfactor;
  20
  21   //Intiliaze and set prefetch table mutex attribute
  22   pthread_mutexattr_init(&pflookup.prefetchmutexattr);
  23   //NOTE:PTHREAD_MUTEX_RECURSIVE is currently inside a #if_def UNIX98 in the pthread.h file
  24   //Therefore use PTHREAD_MUTEX_RECURSIVE_NP instead
  25   pthread_mutexattr_settype(&pflookup.prefetchmutexattr, PTHREAD_MUTEX_RECURSIVE_NP);
  26
  27   //Initialize mutex var
  28   pthread_mutex_init(&pflookup.lock, &pflookup.prefetchmutexattr);
  29   //pthread_mutex_init(&pflookup.lock, NULL);
  30   pthread_cond_init(&pflookup.cond, NULL);
  31   return 0;
  32 }
  33
  34 //Assign keys to bins inside hash table
  35 unsigned int prehashFunction(unsigned int key) {
  36   return ( key % (pflookup.size));
  37 }
  38
  39 //Store oids and their pointers into hash
  40 unsigned int prehashInsert(unsigned int key, void *val) {
  41   unsigned int newsize;
  42   int index;
  43   prehashlistnode_t *ptr, *node;
  44
  45   if(pflookup.numelements > (pflookup.loadfactor * pflookup.size)) {
  46     //Resize
  47     newsize = 2 * pflookup.size + 1;
  48     pthread_mutex_lock(&pflookup.lock);
  49     prehashResize(newsize);
  50     pthread_mutex_unlock(&pflookup.lock);
  51   }
  52
  53   ptr = pflookup.table;
  54   pflookup.numelements++;
  55
  56   pthread_mutex_lock(&pflookup.lock);
  57   index = prehashFunction(key);
  58   if(ptr[index].next == NULL && ptr[index].key == 0) {  // Insert at the first position in the hashtable
  59     ptr[index].key = key;
  60     ptr[index].val = val;
  61   } else {                      // Insert in the beginning of linked list
  62     if ((node = calloc(1, sizeof(prehashlistnode_t))) == NULL) {
  63       printf("Calloc error %s, %d\n", __FILE__, __LINE__);
  64       pthread_mutex_unlock(&pflookup.lock);
  65       return 1;
  66     }
  67     node->key = key;
  68     node->val = val ;
  69     node->next = ptr[index].next;
  70     ptr[index].next = node;
  71   }
  72   pthread_mutex_unlock(&pflookup.lock);
  73   return 0;
  74 }
  75
  76 // Search for an address for a given oid
  77 void *prehashSearch(unsigned int key) {
  78   int index;
  79   prehashlistnode_t *ptr, *node;
  80
  81   pthread_mutex_lock(&pflookup.lock);
  82   ptr = pflookup.table;
  83   index = prehashFunction(key);
  84   node = &ptr[index];
  85   while(node != NULL) {
  86     if(node->key == key) {
  87       pthread_mutex_unlock(&pflookup.lock);
  88       return node->val;
  89     }
  90     node = node->next;
  91   }
  92   pthread_mutex_unlock(&pflookup.lock);
  93   return NULL;
  94 }
  95
  96 unsigned int prehashRemove(unsigned int key) {
  97   int index;
  98   prehashlistnode_t *curr, *prev;
  99   prehashlistnode_t *ptr, *node;
 100
 101   pthread_mutex_lock(&pflookup.lock);
 102     ptr = pflookup.table;
 103   index = prehashFunction(key);
 104   curr = &ptr[index];
 105
 106   for (; curr != NULL; curr = curr->next) {
 107     if (curr->key == key) {         // Find a match in the hash table
 108       pflookup.numelements--;  // Decrement the number of elements in the global hashtable
 109       if ((curr == &ptr[index]) && (curr->next == NULL))  { // Delete the first item inside the hashtable with no linked list of prehashlistnode_t
 110         curr->key = 0;
 111         curr->val = NULL;
 112       } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of prehashlistnode_t  connected
 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 {                                          // Regular delete from linked listed
 119         prev->next = curr->next;
 120         free(curr);
 121       }
 122       pthread_mutex_unlock(&pflookup.lock);
 123       return 0;
 124     }
 125     prev = curr;
 126   }
 127   pthread_mutex_unlock(&pflookup.lock);
 128   return 1;
 129 }
 130
 131 unsigned int prehashResize(unsigned int newsize) {
 132   prehashlistnode_t *node, *ptr, *curr, *next;  // curr and next keep track of the current and the next chashlistnodes in a linked list
 133   unsigned int oldsize;
 134   int isfirst;    // Keeps track of the first element in the prehashlistnode_t for each bin in hashtable
 135   int i,index;
 136   prehashlistnode_t *newnode;
 137
 138   ptr = pflookup.table;
 139   oldsize = pflookup.size;
 140
 141   if((node = calloc(newsize, sizeof(prehashlistnode_t))) == NULL) {
 142     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 143     return 1;
 144   }
 145
 146   pflookup.table = node;                //Update the global hashtable upon resize()
 147   pflookup.size = newsize;
 148   pflookup.numelements = 0;
 149
 150   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 151     curr = &ptr[i];
 152     isfirst = 1;
 153     while (curr != NULL) {                      //Inner loop to go through linked lists
 154       if (curr->key == 0) {             //Exit inner loop if there the first element for a given bin/index is NULL
 155         break;                  //key = val =0 for element if not present within the hash table
 156       }
 157       next = curr->next;
 158       index = prehashFunction(curr->key);
 159       // Insert into the new table
 160       if(pflookup.table[index].next == NULL && pflookup.table[index].key == 0) {
 161         pflookup.table[index].key = curr->key;
 162         pflookup.table[index].val = curr->val;
 163         pflookup.numelements++;
 164       }else {
 165         if((newnode = calloc(1, sizeof(prehashlistnode_t))) == NULL) {
 166           printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 167           return 1;
 168         }
 169         newnode->key = curr->key;
 170         newnode->val = curr->val;
 171         newnode->next = pflookup.table[index].next;
 172         pflookup.table[index].next = newnode;
 173         pflookup.numelements++;
 174       }
 175
 176       //free the linked list of prehashlistnode_t if not the first element in the hash table
 177       if (isfirst != 1) {
 178         free(curr);
 179       }
 180
 181       isfirst = 0;
 182       curr = next;
 183     }
 184   }
 185
 186   free(ptr);            //Free the memory of the old hash table
 187   return 0;
 188 }
 189
 190 //Note: This is based on the implementation of the inserting a key in the first position of the hashtable
 191 void prehashClear() {
 192   int i, isFirstBin;
 193   prehashlistnode_t *ptr, *prev, *curr;
 194
 195   pthread_mutex_lock(&pflookup.lock);
 196   ptr = pflookup.table;
 197   for(i = 0; i < pflookup.size; i++) {
 198     prev = &ptr[i];
 199     isFirstBin = 1;
 200     while(prev->next != NULL) {
 201       isFirstBin = 0;
 202       curr = prev->next;
 203       prev->next = curr->next;
 204       free(curr);
 205     }
 206     if(isFirstBin == 1) {
 207       prev->key = 0;
 208       prev->next = NULL;
 209     }
 210   }
 211   pthread_mutex_unlock(&pflookup.lock);
 212 }
 213