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