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

   1 #include "mlookup.h"
   2
   3 mhashtable_t mlookup;   //Global hash table
   4
   5 unsigned int mhashCreate(unsigned int size, float loadfactor)  {
   6         mhashlistnode_t *nodes;
   7         int i;
   8
   9         // Allocate space for the hash table
  10         if((nodes = calloc(HASH_SIZE, sizeof(mhashlistnode_t))) == NULL) {
  11                 printf("Calloc error %s %d\n", __FILE__, __LINE__);
  12                 return 1;
  13         }
  14
  15         mlookup.table = nodes;
  16         mlookup.size = size;
  17         mlookup.numelements = 0; // Initial number of elements in the hash
  18         mlookup.loadfactor = loadfactor;
  19         return 0;
  20 }
  21
  22 // Assign to keys to bins inside hash table
  23 unsigned int mhashFunction(unsigned int key) {
  24         return( key % (mlookup.size));
  25 }
  26
  27 // Insert value and key mapping into the hash table
  28 unsigned int mhashInsert(unsigned int key, void *val) {
  29         unsigned int newsize;
  30         int index;
  31         mhashlistnode_t *ptr, *node;
  32
  33         if (mlookup.numelements > (mlookup.loadfactor * mlookup.size)) {
  34                 //Resize Table
  35                 newsize = 2 * mlookup.size + 1;
  36                 mhashResize(newsize);
  37         }
  38         ptr = mlookup.table;
  39         mlookup.numelements++;
  40
  41         index = mhashFunction(key);
  42 #ifdef DEBUG
  43         printf("DEBUG -> index = %d, key = %d, val = %x\n", index, key, val);
  44 #endif
  45         if(ptr[index].next == NULL && ptr[index].key == 0) {    // Insert at the first position in the hashtable
  46                 ptr[index].key = key;
  47                 ptr[index].val = val;
  48         } else {                        // Insert in the beginning of linked list
  49                 if ((node = calloc(1, sizeof(mhashlistnode_t))) == NULL) {
  50                         printf("Calloc error %s, %d\n", __FILE__, __LINE__);
  51                         return 1;
  52                 }
  53                 node->key = key;
  54                 node->val = val ;
  55                 node->next = ptr[index].next;
  56                 ptr[index].next = node;
  57         }
  58         return 0;
  59 }
  60
  61 // Return val for a given key in the hash table
  62 void *mhashSearch(unsigned int key) {
  63         int index;
  64         mhashlistnode_t *ptr, *node;
  65
  66         ptr = mlookup.table;    // Address of the beginning of hash table
  67         index = mhashFunction(key);
  68         node = &ptr[index];
  69         while(node != NULL) {
  70                 if(node->key == key) {
  71                         return node->val;
  72                 }
  73                 node = node->next;
  74         }
  75         return NULL;
  76 }
  77
  78 // Remove an entry from the hash table
  79 unsigned int mhashRemove(unsigned int key) {
  80         int index;
  81         mhashlistnode_t *curr, *prev;
  82         mhashlistnode_t *ptr, *node;
  83
  84         ptr = mlookup.table;
  85         index = mhashFunction(key);
  86         curr = &ptr[index];
  87
  88         for (; curr != NULL; curr = curr->next) {
  89                 if (curr->key == key) {         // Find a match in the hash table
  90                         mlookup.numelements--;  // Decrement the number of elements in the global hashtable
  91                         if ((curr == &ptr[index]) && (curr->next == NULL))  { // Delete the first item inside the hashtable with no linked list of mhashlistnode_t
  92                                 curr->key = 0;
  93                                 curr->val = NULL;
  94                         } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of mhashlistnode_t  connected
  95                                 curr->key = curr->next->key;
  96                                 curr->val = curr->next->val;
  97                                 node = curr->next;
  98                                 curr->next = curr->next->next;
  99                                 free(node);
 100                         } else {                                                // Regular delete from linked listed
 101                                 prev->next = curr->next;
 102                                 free(curr);
 103                         }
 104                         return 0;
 105                 }
 106                 prev = curr;
 107         }
 108         return 1;
 109 }
 110
 111 // Resize table
 112 unsigned int mhashResize(unsigned int newsize) {
 113         mhashlistnode_t *node, *ptr, *curr, *next;      // curr and next keep track of the current and the next mhashlistnodes in a linked list
 114         unsigned int oldsize;
 115         int isfirst;    // Keeps track of the first element in the mhashlistnode_t for each bin in hashtable
 116         int i,index;
 117         mhashlistnode_t *newnode;
 118
 119         ptr = mlookup.table;
 120         oldsize = mlookup.size;
 121
 122         if((node = calloc(newsize, sizeof(mhashlistnode_t))) == NULL) {
 123                 printf("Calloc error %s %d\n", __FILE__, __LINE__);
 124                 return 1;
 125         }
 126
 127         mlookup.table = node;           //Update the global hashtable upon resize()
 128         mlookup.size = newsize;
 129         mlookup.numelements = 0;
 130
 131         for(i = 0; i < oldsize; i++) {                  //Outer loop for each bin in hash table
 132                 curr = &ptr[i];
 133                 isfirst = 1;
 134                 while (curr != NULL) {                  //Inner loop to go through linked lists
 135                         if (curr->key == 0) {           //Exit inner loop if there the first element for a given bin/index is NULL
 136                                 break;                  //key = val =0 for element if not present within the hash table
 137                         }
 138                         next = curr->next;
 139
 140                         index = mhashFunction(curr->key);
 141 #ifdef DEBUG
 142                         printf("DEBUG(resize) -> index = %d, key = %d, val = %x\n", index, curr->key, curr->val);
 143 #endif
 144                         // Insert into the new table
 145                         if(mlookup.table[index].next == NULL && mlookup.table[index].key == 0) {
 146                                 mlookup.table[index].key = curr->key;
 147                                 mlookup.table[index].val = curr->val;
 148                                 mlookup.numelements++;
 149                         }else {
 150                                 if((newnode = calloc(1, sizeof(mhashlistnode_t))) == NULL) {
 151                                         printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 152                                         return 1;
 153                                 }
 154                                 newnode->key = curr->key;
 155                                 newnode->val = curr->val;
 156                                 newnode->next = mlookup.table[index].next;
 157                                 mlookup.table[index].next = newnode;
 158                                 mlookup.numelements++;
 159                         }
 160
 161                         //free the linked list of mhashlistnode_t if not the first element in the hash table
 162                         if (isfirst != 1) {
 163                                 free(curr);
 164                         }
 165
 166                         isfirst = 0;
 167                         curr = next;
 168
 169                 }
 170         }
 171
 172         free(ptr);              //Free the memory of the old hash table
 173         return 0;
 174 }
 175
 176 #if 0
 177 // Hash Resize
 178 vkey resize(obj_addr_table_t * table){
 179         int newCapacity = 2*(table->size) + 1;
 180         obj_listnode_t **old;
 181         //if ((table->hash = (obj_listnode_t **) malloc(sizeof(obj_listnode_t *)*size)) == NULL) {
 182 }
 183
 184 // Hashing for the Key
 185 int hashKey(unsigned int key, obj_addr_table_t *table) {
 186         // hash32shiftmult
 187         int c2=0x27d4eb2d; // a prime or an odd constant
 188         key = (key ^ 61) ^ (key >> 16);
 189         key = key + (key << 3);
 190         key = key ^ (key >> 4);
 191         key = key * c2;
 192         key = key ^ (key >> 15);
 193         printf("The bucket number is %d\n", key % (table->size));
 194         return (key % (table->size));
 195 }
 196
 197 //Add key and its address to the new ob_listnode_t
 198 vkey addKey(unsigned int key, objheader_t *ptr, obj_addr_table_t *table) {
 199         int index;
 200         obj_listnode_t *node;
 201
 202         table->numelements++;
 203         if(table->numelements > (table->loadfactor * table->size)){
 204         //TODO : check if table is nearly full and then resize
 205         }
 206
 207         index = hashKey(key,table);
 208         if ((node = (obj_listnode_t *) malloc(sizeof(obj_listnode_t))) == NULL) {
 209                 printf("Malloc error %s %d\n", __FILE__, __LINE__);
 210                 exit(-1);
 211         }
 212         node->key = key;
 213         node->object = ptr;
 214         node->next = table->hash[index];
 215         table->hash[index] = node;
 216         return;
 217 }
 218 // Get the address of the object header for a given key
 219 objheader_t *findKey(unsigned int key, obj_addr_table_t *table) {
 220         int index;
 221         obj_listnode_t *ptr;
 222
 223         index = hashKey(key,table);
 224         ptr = table->hash[index];
 225         while(ptr != NULL) {
 226                 if (ptr->key == key) {
 227                         return ptr->object;
 228                 }
 229                 ptr = ptr->next;
 230         }
 231         return NULL;
 232 }
 233 // Remove the pointer to the object header from a linked list of obj_listnode_t given an key
 234 int removeKey(unsigned int key, obj_addr_table_t *table) {
 235         int index;
 236         obj_listnode_t *curr, *prev;            // prev points to previous node and curr points to the node to be deleted
 237
 238         index = hashKey(key,table);
 239         prev = curr = table->hash[index];
 240         for (; curr != NULL; curr = curr->next) {
 241                 if (curr->key == key) {         // Find a match in the hash table
 242                         table->numelements--;
 243                         prev->next = curr->next;
 244                         if (table->hash[index] == curr) { // Special case when there is one element pointed by  the hash table
 245                                 table->hash[index] = NULL;
 246                         }
 247                         free(curr);
 248                         return 0;
 249                 }
 250                 prev = curr;
 251         }
 252         return -1;
 253 }
 254
 255 #endif