Robust/src/Runtime/oooJava/WaitingQueue.c

   1 #include "mlp_lock.h"\r
   2 #include <stdio.h>\r
   3 #include <stdlib.h>\r
   4 #include "WaitingQueue.h"\r
   5 #include "hashStructure.h"\r
   6 //TODO check that the right path is pointed to by the below #include\r
   7 #include "RuntimeConflictResolver.h"\r
   8 \r
   9 //Note: is global to all processes\r
  10 WaitingQueueBinVector * freeBinVectors;\r
  11 \r
  12 //TODO perhaps print a map of allocSites to arrayIndex?\r
  13 \r
  14 //NOTE: Only the HashTable calls this function\r
  15 WaitingQueueBin * mallocWaitingQueue(int size) {\r
  16   return (WaitingQueueBin *) malloc(sizeof(WaitingQueueBin) * size);\r
  17 }\r
  18 \r
  19 //NOTE: allocSiteID is NOT the same as allocsite, rather it's an ID generated by the traverser for an alloc site for a traversal.\r
  20 void putIntoWaitingQueue(int allocSiteID, WaitingQueueBin * queue, void * resumePtr, int traverserID) {\r
  21   //since Put SHOULD be done only by 1 thread (from 1 hashtable), the locking mechanism is removed.\r
  22   WaitingQueueBin *qptr=&queue[allocSiteID];\r
  23   WaitingQueueBinVector * tail = qptr->tail;\r
  24   int effectType=0;//PLACEHOLDER....EITHER GET RID OF VARIABLE OR PASS IN\r
  25 \r
  26   if (tail == NULL) {\r
  27     //completely empty case\r
  28     WaitingQueueBinVector * currentVector = getUsableWaitingQueueBinVector();\r
  29     TraverserResumeDataFromWaitingQ * b = &(currentVector->array[currentVector->tailIndex++]);\r
  30     //Add new bin to list\r
  31     qptr->head = currentVector;\r
  32     qptr->tail = currentVector;\r
  33     //Insert item into bin\r
  34     b->resumePtr = resumePtr;\r
  35     b->traverserID = traverserID;\r
  36     b->effectType = effectType;\r
  37     qptr->size++;\r
  38   } else if (tail->tailIndex == NUMITEMS_WQ) {\r
  39     //Tail bin full\r
  40     WaitingQueueBinVector * currentVector = tail;\r
  41     TraverserResumeDataFromWaitingQ * b = &(currentVector->array[currentVector->tailIndex-1]);\r
  42     //Not a duplicate\r
  43     if(b->effectType != effectType || b->resumePtr != resumePtr || b->traverserID != traverserID) {\r
  44       //should add item\r
  45       currentVector = getUsableWaitingQueueBinVector();\r
  46       tail->next = currentVector;\r
  47       qptr->tail = currentVector;\r
  48       b = &(currentVector->array[currentVector->tailIndex++]);\r
  49       b->resumePtr = resumePtr;\r
  50       b->traverserID = traverserID;\r
  51       b->effectType = effectType;\r
  52       qptr->size++;\r
  53     }\r
  54   } else { //the bin not full case\r
  55     WaitingQueueBinVector * currentVector = tail;\r
  56     TraverserResumeDataFromWaitingQ * b = &(currentVector->array[currentVector->tailIndex-1]);\r
  57     //Not a duplicate\r
  58     if(b->effectType != effectType || b->resumePtr != resumePtr || b->traverserID != traverserID) {\r
  59       //should add item\r
  60       b = &(currentVector->array[currentVector->tailIndex++]);\r
  61       b->resumePtr = resumePtr;\r
  62       b->traverserID = traverserID;\r
  63       b->effectType = effectType;\r
  64       qptr->size++;\r
  65     }\r
  66   }\r
  67 }\r
  68 \r
  69 int isEmptyForWaitingQ(WaitingQueueBin * queue, int allocSiteID) {\r
  70   return queue[allocSiteID].size;\r
  71 }\r
  72 \r
  73 //This method should be called by the SESE block\r
  74 //Return is how many things are removed. -1 would indicate error\r
  75 int removeFromWaitingQueue(WaitingQueueBin * wQueue, int allocSiteID, int TraverserID) {\r
  76   TraverserResumeDataFromWaitingQ * td;\r
  77   WaitingQueueBin * be = &(wQueue[allocSiteID]);\r
  78   int count = 0;\r
  79 \r
  80   if(wQueue[allocSiteID].size == 0)\r
  81     return -1; //error\r
  82 \r
  83   do {\r
  84     td = &(be->head->array[be->head->headIndex]);\r
  85 \r
  86     //TODO perhaps instead of using traverserID to track which variables are resolved, make\r
  87     //individual IDs for each.\r
  88     if(td->traverserID != TraverserID) {\r
  89       return count;\r
  90     }\r
  91 \r
  92     if(traverse(td->resumePtr, td->traverserID) == TRAVERSER_FINISHED) {\r
  93       count++; // means we at least got rid of 1 item in the traverser\r
  94       be->size--;\r
  95 \r
  96       //fast case\r
  97       if(be->size == 0) {\r
  98         be->head->headIndex = 0;\r
  99         be->head->tailIndex = 0;\r
 100         return count;\r
 101       }\r
 102       else if(++(be->head->headIndex) == be->head->tailIndex){\r
 103         //Note: be->head->next CANNOT be NULL since that would imply be->size == 0\r
 104         be->head = returnWaitingQueueBinVectorToFreePool(be->head);\r
 105       }\r
 106     }\r
 107     else\r
 108       return count;\r
 109 \r
 110   } while(1);\r
 111 }\r
 112 \r
 113 WaitingQueueBinVector * returnWaitingQueueBinVectorToFreePool(WaitingQueueBinVector *ptr) {\r
 114   WaitingQueueBinVector * freeHead;\r
 115   WaitingQueueBinVector * ptrNext;\r
 116   do {\r
 117     freeHead = (WaitingQueueBinVector *) 0x1;\r
 118     freeHead = (WaitingQueueBinVector *) LOCKXCHG((unsigned INTPTR *)&freeBinVectors, (unsigned INTPTR) freeHead);\r
 119   } while (freeHead == (WaitingQueueBinVector *) 0x1);\r
 120   //free bins locked\r
 121 \r
 122   ptrNext = ptr->next;\r
 123   if(freeHead == NULL) {\r
 124     freeBinVectors = ptr; //lock released\r
 125   }\r
 126   else {\r
 127     ptr->next = freeHead;\r
 128     freeBinVectors = ptr; //lock released\r
 129   }\r
 130 \r
 131   return ptrNext;\r
 132 }\r
 133 \r
 134 WaitingQueueBinVector * getUsableWaitingQueueBinVector() {\r
 135   //Attempt to take one from the free bin first\r
 136   WaitingQueueBinVector * ptr;\r
 137   do {\r
 138     ptr = (WaitingQueueBinVector *) 0x1;\r
 139     ptr = (WaitingQueueBinVector *) LOCKXCHG((unsigned INTPTR *) &freeBinVectors, (unsigned INTPTR) ptr);\r
 140   } while (ptr == (WaitingQueueBinVector *) 0x1);\r
 141   //free bins locked\r
 142 \r
 143   if (ptr == NULL) {\r
 144     freeBinVectors = NULL; //lock released\r
 145     return mallocNewWaitingQueueBinVector();\r
 146   } else {\r
 147     freeBinVectors = ptr->next; //lock released\r
 148     ptr->next = NULL;\r
 149     ptr->headIndex = 0;\r
 150     ptr->tailIndex = 0;\r
 151     return ptr;\r
 152   }\r
 153 }\r
 154 \r
 155 WaitingQueueBinVector * mallocNewWaitingQueueBinVector() {\r
 156   WaitingQueueBinVector * retval = (WaitingQueueBinVector *) malloc(\r
 157       sizeof(WaitingQueueBinVector));\r
 158   retval->next = NULL;\r
 159   retval->headIndex = 0;\r
 160   retval->tailIndex = 0;\r
 161   return retval;\r
 162 }\r