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

   1 #include "threadnotify.h"
   2
   3 notifyhashtable_t nlookup; //Global hash table
   4
   5 /* This function creates a new node in the linked list of threads waiting
   6  * for an update notification from a particular object.
   7  * This takes in the head of the linked list and inserts the new node to it */
   8 threadlist_t *insNode(threadlist_t *head, unsigned int threadid, unsigned int mid) {
   9         threadlist_t *ptr;
  10         if(head == NULL) {
  11                 if((head = calloc(1, sizeof(threadlist_t))) == NULL) {
  12                         printf("Calloc Error %s, %d,\n", __FILE__, __LINE__);
  13                         return;
  14                 }
  15                 head->threadid = threadid;
  16                 head->mid = mid;
  17                 head->next = NULL;
  18         } else {
  19                 if((ptr = calloc(1, sizeof(threadlist_t))) == NULL) {
  20                         printf("Calloc Error %s, %d,\n", __FILE__, __LINE__);
  21                         return;
  22                 }
  23                 ptr->threadid = threadid;
  24                 ptr->mid = mid;
  25                 ptr->next = head;
  26                 head = ptr;
  27         }
  28
  29         return head;
  30 }
  31
  32 /* This function displays the linked list of threads waiting on update notification
  33  * from an object */
  34 void display(threadlist_t *head) {
  35         threadlist_t *ptr;
  36         if(head == NULL) {
  37                 printf("No thread is waiting\n");
  38                 return;
  39         } else {
  40                 while(head != NULL) {
  41                         ptr = head;
  42                         printf("The threadid waiting is = %d\n", ptr->threadid);
  43                         printf("The mid on which thread present = %d\n", ptr->mid);
  44                         head = ptr->next;
  45                 }
  46         }
  47 }
  48
  49 /* This function creates a new hash table that stores a mapping between the threadid and
  50  * a pointer to the thread notify data */
  51 unsigned int notifyhashCreate(unsigned int size, float loadfactor) {
  52         notifylistnode_t *nodes;
  53
  54         // Allocate space for the hash table
  55         if((nodes = calloc(size, sizeof(notifylistnode_t))) == NULL) {
  56                 printf("Calloc error %s %d\n", __FILE__, __LINE__);
  57                 return 1;
  58         }
  59
  60         nlookup.table = nodes;
  61         nlookup.size = size;
  62         nlookup.numelements = 0; // Initial number of elements in the hash
  63         nlookup.loadfactor = loadfactor;
  64         //Initialize the pthread_mutex variable
  65         pthread_mutex_init(&nlookup.locktable, NULL);
  66         return 0;
  67 }
  68
  69 // Assign to tids to bins inside hash table
  70 unsigned int notifyhashFunction(unsigned int tid) {
  71         return( tid % (nlookup.size));
  72 }
  73
  74 // Insert pointer to the notify data and threadid mapping into the hash table
  75 unsigned int notifyhashInsert(unsigned int tid, notifydata_t *ndata) {
  76         unsigned int newsize;
  77         int index;
  78         notifylistnode_t *ptr, *node, *tmp;
  79         int isFound = 0;
  80
  81         if (nlookup.numelements > (nlookup.loadfactor * nlookup.size)) {
  82                 //Resize Table
  83                 newsize = 2 * nlookup.size + 1;
  84                 pthread_mutex_lock(&nlookup.locktable);
  85                 notifyhashResize(newsize);
  86                 pthread_mutex_unlock(&nlookup.locktable);
  87         }
  88         /*
  89         ptr = nlookup.table;
  90         nlookup.numelements++;
  91
  92         index = notifyhashFunction(tid);
  93 #ifdef DEBUG
  94         printf("DEBUG -> index = %d, threadid = %d\n", index, tid);
  95 #endif
  96         pthread_mutex_lock(&nlookup.locktable);
  97         if(ptr[index].next == NULL && ptr[index].threadid == 0) {       // Insert at the first position in the hashtable
  98                 ptr[index].threadid = tid;
  99                 ptr[index].ndata = ndata;
 100         } else {                        // Insert in the beginning of linked list
 101                 if ((node = calloc(1, sizeof(notifylistnode_t))) == NULL) {
 102                         printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 103                         pthread_mutex_unlock(&nlookup.locktable);
 104                         return 1;
 105                 }
 106                 node->threadid = tid;
 107                 node->ndata = ndata;
 108                 node->next = ptr[index].next;
 109                 ptr[index].next = node;
 110         }
 111         pthread_mutex_unlock(&nlookup.locktable);
 112         */
 113         ptr = nlookup.table;
 114         index = notifyhashFunction(tid);
 115         pthread_mutex_lock(&nlookup.locktable);
 116         if(ptr[index].next == NULL && ptr[index].threadid == 0) {       // Insert at the first position in the hashtable
 117                 ptr[index].threadid = tid;
 118                 ptr[index].ndata = ndata;
 119         } else {
 120                 tmp = &ptr[index];
 121                 while(tmp != NULL) {
 122                         if(tmp->threadid == tid) {
 123                                 isFound = 1;
 124                                 tmp->ndata = ndata;
 125                         }
 126                         tmp = tmp->next;
 127                 }
 128                 if(!isFound) {
 129                         if ((node = calloc(1, sizeof(notifylistnode_t))) == NULL) {
 130                                 printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 131                                 pthread_mutex_unlock(&nlookup.locktable);
 132                                 return 1;
 133                         }
 134                         node->threadid = tid;
 135                         node->ndata = ndata;
 136                         node->next = ptr[index].next;
 137                         ptr[index].next = node;
 138                 }
 139         }
 140         pthread_mutex_unlock(&nlookup.locktable);
 141
 142         return 0;
 143 }
 144
 145 // Return pointer to thread notify data for a given threadid in the hash table
 146 notifydata_t  *notifyhashSearch(unsigned int tid) {
 147         int index;
 148         notifylistnode_t *ptr, *node;
 149
 150         ptr = nlookup.table;    // Address of the beginning of hash table
 151         index = notifyhashFunction(tid);
 152         node = &ptr[index];
 153         pthread_mutex_lock(&nlookup.locktable);
 154         while(node != NULL) {
 155                 if(node->threadid == tid) {
 156                         pthread_mutex_unlock(&nlookup.locktable);
 157                         return node->ndata;
 158                 }
 159                 node = node->next;
 160         }
 161         pthread_mutex_unlock(&nlookup.locktable);
 162         return NULL;
 163 }
 164
 165 // Remove an entry from the hash table
 166 unsigned int notifyhashRemove(unsigned int tid) {
 167         int index;
 168         notifylistnode_t *curr, *prev, *ptr, *node;
 169
 170         ptr = nlookup.table;
 171         index = notifyhashFunction(tid);
 172         curr = &ptr[index];
 173
 174         pthread_mutex_lock(&nlookup.locktable);
 175         for (; curr != NULL; curr = curr->next) {
 176                 if (curr->threadid == tid) {         // Find a match in the hash table
 177                         nlookup.numelements--;  // Decrement the number of elements in the global hashtable
 178                         if ((curr == &ptr[index]) && (curr->next == NULL))  { // Delete the first item inside the hashtable with no linked list of notifylistnode_t
 179                                 curr->threadid = 0;
 180                                 curr->ndata = NULL;
 181                         } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first bin item with a linked list of notifylistnode_t  connected
 182                                 curr->threadid = curr->next->threadid;
 183                                 curr->ndata = curr->next->ndata;
 184                                 node = curr->next;
 185                                 curr->next = curr->next->next;
 186                                 free(node);
 187                         } else {                                                // Regular delete from linked listed
 188                                 prev->next = curr->next;
 189                                 free(curr);
 190                         }
 191                         pthread_mutex_unlock(&nlookup.locktable);
 192                         return 0;
 193                 }
 194                 prev = curr;
 195         }
 196         pthread_mutex_unlock(&nlookup.locktable);
 197         return 1;
 198 }
 199
 200 // Resize table
 201 unsigned int notifyhashResize(unsigned int newsize) {
 202         notifylistnode_t *node, *ptr, *curr, *next;     // curr and next keep track of the current and the next notifyhashlistnodes in a linked list
 203         unsigned int oldsize;
 204         int isfirst;    // Keeps track of the first element in the notifylistnode_t for each bin in hashtable
 205         int i,index;
 206         notifylistnode_t *newnode;
 207
 208         ptr = nlookup.table;
 209         oldsize = nlookup.size;
 210
 211         if((node = calloc(newsize, sizeof(notifylistnode_t))) == NULL) {
 212                 printf("Calloc error %s %d\n", __FILE__, __LINE__);
 213                 return 1;
 214         }
 215
 216         nlookup.table = node;           //Update the global hashtable upon resize()
 217         nlookup.size = newsize;
 218         nlookup.numelements = 0;
 219
 220         for(i = 0; i < oldsize; i++) {                  //Outer loop for each bin in hash table
 221                 curr = &ptr[i];
 222                 isfirst = 1;
 223                 while (curr != NULL) {                  //Inner loop to go through linked lists
 224                         if (curr->threadid == 0) {              //Exit inner loop if there the first element for a given bin/index is NULL
 225                                 break;                  //threadid = threadcond =0 for element if not present within the hash table
 226                         }
 227                         next = curr->next;
 228                         index = notifyhashFunction(curr->threadid);
 229 #ifdef DEBUG
 230                         printf("DEBUG(resize) -> index = %d, threadid = %d\n", index, curr->threadid);
 231 #endif
 232                         // Insert into the new table
 233                         if(nlookup.table[index].next == NULL && nlookup.table[index].threadid == 0) {
 234                                 nlookup.table[index].threadid = curr->threadid;
 235                                 nlookup.table[index].ndata = curr->ndata;
 236                                 nlookup.numelements++;
 237                         }else {
 238                                 if((newnode = calloc(1, sizeof(notifylistnode_t))) == NULL) {
 239                                         printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 240                                         return 1;
 241                                 }
 242                                 newnode->threadid = curr->threadid;
 243                                 newnode->ndata = curr->ndata;
 244                                 newnode->next = nlookup.table[index].next;
 245                                 nlookup.table[index].next = newnode;
 246                                 nlookup.numelements++;
 247                         }
 248
 249                         //free the linked list of notifylistnode_t if not the first element in the hash table
 250                         if (isfirst != 1) {
 251                                 free(curr);
 252                         }
 253
 254                         isfirst = 0;
 255                         curr = next;
 256                 }
 257         }
 258
 259         free(ptr);              //Free the memory of the old hash table
 260         ptr = NULL;
 261         return 0;
 262 }