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

   1 #include "mlookup.h"
   2
   3 mhashtable_t mlookup;   //Global hash table
   4
   5 // Creates a machine lookup table with size =" size"
   6 unsigned int mhashCreate(unsigned int size, float loadfactor)  {
   7         mhashlistnode_t *nodes;
   8         int i;
   9
  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.numelements = 0; // Initial number of elements in the hash
  19         mlookup.loadfactor = loadfactor;
  20         //Initialize the pthread_mutex variable
  21         pthread_mutex_init(&mlookup.locktable, NULL);
  22         return 0;
  23 }
  24
  25 // Assign to keys to bins inside hash table
  26 unsigned int mhashFunction(unsigned int key) {
  27         return( key % (mlookup.size));
  28 }
  29
  30 // Insert value and key mapping into the hash table
  31 unsigned int mhashInsert(unsigned int key, void *val) {
  32         unsigned int newsize;
  33         int index;
  34         mhashlistnode_t *ptr, *node;
  35
  36         if (mlookup.numelements > (mlookup.loadfactor * mlookup.size)) {
  37                 //Resize Table
  38                 newsize = 2 * mlookup.size + 1;
  39                 pthread_mutex_lock(&mlookup.locktable);
  40                 mhashResize(newsize);
  41                 pthread_mutex_unlock(&mlookup.locktable);
  42         }
  43         ptr = mlookup.table;
  44         mlookup.numelements++;
  45
  46         index = mhashFunction(key);
  47 #ifdef DEBUG
  48         printf("DEBUG -> index = %d, key = %d, val = %x\n", index, key, val);
  49 #endif
  50         pthread_mutex_lock(&mlookup.locktable);
  51         if(ptr[index].next == NULL && ptr[index].key == 0) {    // Insert at the first position in the hashtable
  52                 ptr[index].key = key;
  53                 ptr[index].val = val;
  54         } else {                        // Insert in the beginning of linked list
  55                 if ((node = calloc(1, sizeof(mhashlistnode_t))) == NULL) {
  56                         printf("Calloc error %s, %d\n", __FILE__, __LINE__);
  57                         pthread_mutex_unlock(&mlookup.locktable);
  58                         return 1;
  59                 }
  60                 node->key = key;
  61                 node->val = val ;
  62                 node->next = ptr[index].next;
  63                 ptr[index].next = node;
  64         }
  65         pthread_mutex_unlock(&mlookup.locktable);
  66         return 0;
  67 }
  68
  69 // Return val for a given key in the hash table
  70 void *mhashSearch(unsigned int key) {
  71         int index;
  72         mhashlistnode_t *ptr, *node;
  73
  74         ptr = mlookup.table;    // Address of the beginning of hash table
  75         index = mhashFunction(key);
  76         node = &ptr[index];
  77         pthread_mutex_lock(&mlookup.locktable);
  78         while(node != NULL) {
  79                 if(node->key == key) {
  80                         pthread_mutex_unlock(&mlookup.locktable);
  81                         return node->val;
  82                 }
  83                 node = node->next;
  84         }
  85         pthread_mutex_unlock(&mlookup.locktable);
  86         return NULL;
  87 }
  88
  89 // Remove an entry from the hash table
  90 unsigned int mhashRemove(unsigned int key) {
  91         int index;
  92         mhashlistnode_t *curr, *prev;
  93         mhashlistnode_t *ptr, *node;
  94
  95         ptr = mlookup.table;
  96         index = mhashFunction(key);
  97         curr = &ptr[index];
  98
  99         pthread_mutex_lock(&mlookup.locktable);
 100         for (; curr != NULL; curr = curr->next) {
 101                 if (curr->key == key) {         // Find a match in the hash table
 102                         mlookup.numelements--;  // Decrement the number of elements in the global hashtable
 103                         if ((curr == &ptr[index]) && (curr->next == NULL))  { // Delete the first item inside the hashtable with no linked list of mhashlistnode_t
 104                                 curr->key = 0;
 105                                 curr->val = NULL;
 106                         } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of mhashlistnode_t  connected
 107                                 curr->key = curr->next->key;
 108                                 curr->val = curr->next->val;
 109                                 node = curr->next;
 110                                 curr->next = curr->next->next;
 111                                 free(node);
 112                         } else {                                                // Regular delete from linked listed
 113                                 prev->next = curr->next;
 114                                 free(curr);
 115                         }
 116                         pthread_mutex_unlock(&mlookup.locktable);
 117                         return 0;
 118                 }
 119                 prev = curr;
 120         }
 121         pthread_mutex_unlock(&mlookup.locktable);
 122         return 1;
 123 }
 124
 125 // Resize table
 126 unsigned int mhashResize(unsigned int newsize) {
 127         mhashlistnode_t *node, *ptr, *curr, *next;      // curr and next keep track of the current and the next mhashlistnodes in a linked list
 128         unsigned int oldsize;
 129         int isfirst;    // Keeps track of the first element in the mhashlistnode_t for each bin in hashtable
 130         int i,index;
 131         mhashlistnode_t *newnode;
 132
 133         ptr = mlookup.table;
 134         oldsize = mlookup.size;
 135
 136         if((node = calloc(newsize, sizeof(mhashlistnode_t))) == NULL) {
 137                 printf("Calloc error %s %d\n", __FILE__, __LINE__);
 138                 return 1;
 139         }
 140
 141         mlookup.table = node;           //Update the global hashtable upon resize()
 142         mlookup.size = newsize;
 143         mlookup.numelements = 0;
 144
 145         for(i = 0; i < oldsize; i++) {                  //Outer loop for each bin in hash table
 146                 curr = &ptr[i];
 147                 isfirst = 1;
 148                 while (curr != NULL) {                  //Inner loop to go through linked lists
 149                         if (curr->key == 0) {           //Exit inner loop if there the first element for a given bin/index is NULL
 150                                 break;                  //key = val =0 for element if not present within the hash table
 151                         }
 152                         next = curr->next;
 153
 154                         index = mhashFunction(curr->key);
 155 #ifdef DEBUG
 156                         printf("DEBUG(resize) -> index = %d, key = %d, val = %x\n", index, curr->key, curr->val);
 157 #endif
 158                         // Insert into the new table
 159                         if(mlookup.table[index].next == NULL && mlookup.table[index].key == 0) {
 160                                 mlookup.table[index].key = curr->key;
 161                                 mlookup.table[index].val = curr->val;
 162                                 mlookup.numelements++;
 163                         }else {
 164                                 if((newnode = calloc(1, sizeof(mhashlistnode_t))) == NULL) {
 165                                         printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 166                                         return 1;
 167                                 }
 168                                 newnode->key = curr->key;
 169                                 newnode->val = curr->val;
 170                                 newnode->next = mlookup.table[index].next;
 171                                 mlookup.table[index].next = newnode;
 172                                 mlookup.numelements++;
 173                         }
 174
 175                         //free the linked list of mhashlistnode_t if not the first element in the hash table
 176                         if (isfirst != 1) {
 177                                 free(curr);
 178                         }
 179
 180                         isfirst = 0;
 181                         curr = next;
 182
 183                 }
 184         }
 185
 186         free(ptr);              //Free the memory of the old hash table
 187         return 0;
 188 }
 189
 190 unsigned int *mhashGetKeys(unsigned int *numKeys)
 191 {
 192         unsigned int *keys;
 193         int i, keyindex;
 194         mhashlistnode_t *curr;
 195
 196         pthread_mutex_lock(&mlookup.locktable);
 197
 198         *numKeys = mlookup.numelements;
 199         keys = calloc(*numKeys, sizeof(unsigned int));
 200
 201         keyindex = 0;
 202         for (i = 0; i < mlookup.size; i++)
 203         {
 204                 if (mlookup.table[i].key != 0)
 205                 {
 206                         curr = &mlookup.table[i];
 207                         while (curr != NULL)
 208                         {
 209                                 keys[keyindex++] = curr->key;
 210                                 curr = curr->next;
 211                         }
 212                 }
 213         }
 214
 215         if (keyindex != *numKeys)
 216                 printf("mhashGetKeys(): WARNING: incorrect mlookup.numelements value!\n");
 217
 218         pthread_mutex_unlock(&mlookup.locktable);
 219         return keys;
 220 }
 221