Programming Languages Research Group: Git - IRC.git/blob

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