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

   1 /************************************************************************************************
   2   IMP NOTE:
   3    All llookup hash function prototypes returns 0 on sucess and 1 otherwise
   4    llookup hash is an array of lhashlistnode_t
   5    oid = mid = 0 in a given lhashlistnode_t for each bin in the hash table ONLY if the entry is empty =>
   6    the OID's can be any unsigned int except 0
   7 ***************************************************************************************************/
   8 #include "llookup.h"
   9
  10 lhashtable_t llookup;           //Global Hash table
  11
  12 // Creates a hash table with default size HASH_SIZE and an array of lhashlistnode_t
  13 unsigned int lhashCreate(unsigned int size, float loadfactor) {
  14         lhashlistnode_t *nodes;
  15         int i;
  16
  17         // Allocate space for the hash table
  18         if((nodes = calloc(HASH_SIZE, sizeof(lhashlistnode_t))) == NULL) {
  19                 printf("Calloc error %s %d\n", __FILE__, __LINE__);
  20                 return 1;
  21         }
  22
  23         llookup.table = nodes;
  24         llookup.size = size;
  25         llookup.numelements = 0; // Initial number of elements in the hash
  26         llookup.loadfactor = loadfactor;
  27         return 0;
  28 }
  29
  30 // Assign to oids to bins inside hash table
  31 unsigned int lhashFunction(unsigned int oid) {
  32         return( oid % (llookup.size));
  33 }
  34
  35 // Insert oid and mid mapping into the hash table
  36 unsigned int lhashInsert(unsigned int oid, unsigned int mid) {
  37         unsigned int newsize;
  38         int index;
  39         lhashlistnode_t *ptr, *node;
  40
  41         if (llookup.numelements > (llookup.loadfactor * llookup.size)) {
  42                 //Resize Table
  43                 newsize = 2 * llookup.size + 1;
  44                 lhashResize(newsize);
  45         }
  46         ptr = llookup.table;
  47         llookup.numelements++;
  48
  49         index = lhashFunction(oid);
  50 #ifdef DEBUG
  51         printf("DEBUG(insert) oid = %d, mid =%d, index =%d\n",oid,mid, index);
  52 #endif
  53         if(ptr[index].next == NULL && ptr[index].oid == 0) {    // Insert at the first position in the hashtable
  54                 ptr[index].oid = oid;
  55                 ptr[index].mid = mid;
  56         } else {                        // Insert in the linked list
  57                 if ((node = calloc(1, sizeof(lhashlistnode_t))) == NULL) {
  58                         printf("Calloc error %s, %d\n", __FILE__, __LINE__);
  59                         return 1;
  60                 }
  61                 node->oid = oid;
  62                 node->mid = mid;
  63                 node->next = ptr[index].next;
  64                 ptr[index].next = node;
  65         }
  66         return 0;
  67 }
  68
  69 // Return mid for a given oid in the hash table
  70 unsigned int lhashSearch(unsigned int oid) {
  71         int index;
  72         lhashlistnode_t *ptr, *node;
  73
  74         ptr = llookup.table;    // Address of the beginning of hash table
  75         index = lhashFunction(oid);
  76         node = &ptr[index];
  77         while(node != NULL) {
  78                 if(node->oid == oid) {
  79                         return node->mid;
  80                 }
  81                 node = node->next;
  82         }
  83         return 0;
  84 }
  85
  86 // Remove an entry from the hash table
  87 unsigned int lhashRemove(unsigned int oid) {
  88         int index;
  89         lhashlistnode_t *curr, *prev;
  90         lhashlistnode_t *ptr, *node;
  91
  92         ptr = llookup.table;
  93         index = lhashFunction(oid);
  94         curr = &ptr[index];
  95
  96         for (; curr != NULL; curr = curr->next) {
  97                 if (curr->oid == oid) {         // Find a match in the hash table
  98                         llookup.numelements--;  // Decrement the number of elements in the global hashtable
  99                         if ((curr == &ptr[index]) && (curr->next == NULL))  { // Delete the first item inside the hashtable with no linked list of lhashlistnode_t
 100                                 curr->oid = 0;
 101                                 curr->mid = 0;
 102                         } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of lhashlistnode_t  connected
 103                                 curr->oid = curr->next->oid;
 104                                 curr->mid = curr->next->mid;
 105                                 node = curr->next;
 106                                 curr->next = curr->next->next;
 107                                 free(node);
 108                         } else {                                                // Regular delete from linked listed
 109                                 prev->next = curr->next;
 110                                 free(curr);
 111                         }
 112                         return 0;
 113                 }
 114                 prev = curr;
 115         }
 116         return 1;
 117 }
 118
 119 // Resize table
 120 unsigned int lhashResize(unsigned int newsize) {
 121         lhashlistnode_t *node, *ptr, *curr, *next;      // curr and next keep track of the current and the next lhashlistnodes in a linked list
 122         unsigned int oldsize;
 123         int isfirst;    // Keeps track of the first element in the lhashlistnode_t for each bin in hashtable
 124         int i,index;
 125         lhashlistnode_t *newnode;
 126
 127         ptr = llookup.table;
 128         oldsize = llookup.size;
 129
 130         if((node = calloc(newsize, sizeof(lhashlistnode_t))) == NULL) {
 131                 printf("Calloc error %s %d\n", __FILE__, __LINE__);
 132                 return 1;
 133         }
 134
 135         llookup.table = node;           //Update the global hashtable upon resize()
 136         llookup.size = newsize;
 137         llookup.numelements = 0;
 138
 139         for(i = 0; i < oldsize; i++) {                  //Outer loop for each bin in hash table
 140                 curr = &ptr[i];
 141                 isfirst = 1;
 142                 while (curr != NULL) {                  //Inner loop to go through linked lists
 143                         if (curr->oid == 0) {           //Exit inner loop if there the first element for a given bin/index is NULL
 144                                 break;                  //oid = mid =0 for element if not present within the hash table
 145                         }
 146                         next = curr->next;
 147                         index = lhashFunction(curr->oid);
 148                         // Insert into the new table
 149                         if(llookup.table[index].next == NULL && llookup.table[index].oid == 0) {
 150                                 llookup.table[index].oid = curr->oid;
 151                                 llookup.table[index].mid = curr->mid;
 152                                 llookup.numelements++;
 153                         }else {
 154                                 if((newnode = calloc(1, sizeof(lhashlistnode_t))) == NULL) {
 155                                         printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 156                                         return 1;
 157                                 }
 158                                 newnode->oid = curr->oid;
 159                                 newnode->mid = curr->mid;
 160                                 newnode->next = llookup.table[index].next;
 161                                 llookup.table[index].next = newnode;
 162                                 llookup.numelements++;
 163                         }
 164
 165                         //free the linked list of lhashlistnode_t if not the first element in the hash table
 166                         if (isfirst != 1) {
 167                                 free(curr);
 168                         }
 169
 170                         isfirst = 0;
 171                         curr = next;
 172
 173                 }
 174         }
 175
 176         free(ptr);              //Free the memory of the old hash table
 177         return 0;
 178 }