Tested and Debugged versions of waitingQueue for the hashStructure.

diff --git a/Robust/src/Runtime/oooJava/WaitingQueue.c b/Robust/src/Runtime/oooJava/WaitingQueue.c
index c42ebcab86850a8b6f0b4998e5d4f89931b2d605..a96d7494273b1c7177b0d621b2894512b3541b64 100644 (file)
--- a/Robust/src/Runtime/oooJava/WaitingQueue.c
+++ b/Robust/src/Runtime/oooJava/WaitingQueue.c
@@ -1,113 +1,124 @@
 #include "mlp_lock.h"\r
+#include <stdio.h>\r
+#include <stdlib.h>\r
 #include "WaitingQueue.h"\r
-//TODO check that the right path is pionted to by the below #include\r
+//TODO check that the right path is pointed to by the below #include\r
 #include "RuntimeConflictResolver.h"\r
 \r
 //Note: is global to all processes\r
-struct BinVector * freeBinVectors = NULL;\r
-\r
-//TODO perhaps print a map of allocsites to arrayIndex?\r
+WaitingQueueBinVector * freeBinVectors;\r
 \r
+//TODO perhaps print a map of allocSites to arrayIndex?\r
 \r
 //NOTE: Only the HashTable calls this function\r
-struct WaitingQueue * mallocWaitingQueue(int size) {\r
-  //TODO perhaps in the future get rid of the WaitingQueue object all together to improve performance (but reduce clarity)\r
-  struct WaitingQueue * q = (struct WaitingQueue *) malloc(sizeof(struct WaitingQueue));\r
-  q->array = (struct BinElement *) malloc(sizeof(struct BinElement) * size);\r
-  return q;\r
+WaitingQueueBin * mallocWaitingQueue(int size) {\r
+  return (WaitingQueueBin *) malloc(sizeof(WaitingQueueBin) * size);\r
 }\r
 \r
 //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
-void put(int allocSiteID, struct WaitingQueue * queue, int effectType, void * resumePtr, int traverserID) {\r
+void putIntoWaitingQueue(int allocSiteID, WaitingQueueBin * queue, int effectType, void * resumePtr, int traverserID) {\r
   //lock bin\r
-  struct BinVector * head;\r
-  struct BinVector * currentVector;\r
-  struct TraverserData * b;\r
-  do {\r
-    head = (struct BinVector *) 0x1;\r
-    LOCKXCHG(((queue->array)[allocSiteID]).head, head);\r
-  } while (head == (struct BinVector *) 0x1);\r
+  WaitingQueueBinVector * currentVector;\r
+  TraverserResumeDataFromWaitingQ * b;\r
+\r
+\r
+  //since Put SHOULD be done only by 1 thread (from 1 hashtable), the locking mechanism is removed.\r
+  WaitingQueueBinVector * head = queue[allocSiteID].head;\r
+//  do {\r
+//    head = (WaitingQueueBinVector *) 0x1;\r
+//    head = LOCKXCHG(&(queue[allocSiteID]).head, head);\r
+//  } while (head == (WaitingQueueBinVector *) 0x1);\r
   //now the current bin is locked.\r
 \r
   //completely empty case\r
-  if (queue->array[allocSiteID].tail == NULL) {\r
-    currentVector = getUsableVector();\r
+  if (queue[allocSiteID].tail == NULL) {\r
+    currentVector = getUsableWaitingQueueBinVector();\r
     head = currentVector;\r
-    queue->array[allocSiteID].tail = currentVector; //We do not set the head here because we need lock\r
+    queue[allocSiteID].tail = currentVector; //We do not set the head here because we need lock\r
   }\r
   //Tail bin full\r
-  else if (queue->array[allocSiteID].tail->index == NUMITEMS) {\r
-    currentVector = getUsableVector();\r
-    queue->array[allocSiteID].tail->next = currentVector;\r
-    queue->array[allocSiteID].tail = currentVector;\r
+  else if (queue[allocSiteID].tail->tailIndex == NUMITEMS_WQ) {\r
+    currentVector = getUsableWaitingQueueBinVector();\r
+    queue[allocSiteID].tail->next = currentVector;\r
+    queue[allocSiteID].tail = currentVector;\r
   } else { //the bin not full case\r
-    currentVector = queue->array[allocSiteID].tail;\r
+    currentVector = queue[allocSiteID].tail;\r
   }\r
 \r
-  //add item\r
-  b = &(currentVector->array[currentVector->index++]);\r
 \r
-  b->resumePtr = resumePtr;\r
-  b->traverserID = traverserID;\r
-  b->effectType = effectType;\r
+  //For the case in which we try to add the same thing twice\r
+  b = &(currentVector->array[currentVector->tailIndex - 1]);\r
+  if(b->effectType == effectType && b->resumePtr == resumePtr && b->traverserID == traverserID) {\r
+    queue[allocSiteID].head = head; // release lock\r
+    return;\r
+  }\r
+  else {//add item\r
+    b = &(currentVector->array[currentVector->tailIndex++]);\r
+\r
+    b->resumePtr = resumePtr;\r
+    b->traverserID = traverserID;\r
+    b->effectType = effectType;\r
 \r
-  queue->array[allocSiteID].size++;\r
-  queue->array[allocSiteID].head = head; // release lock\r
+    queue[allocSiteID].size++;\r
+    queue[allocSiteID].head = head; // release lock\r
+  }\r
 }\r
 \r
-//!0 = no one in line.\r
-//=0 = someone is in line.\r
-int check(struct WaitingQueue * queue, int allocSiteID) {\r
-  return ((queue->array)[allocSiteID]).size == 0;\r
+\r
+int isEmptyForWaitingQ(WaitingQueueBin * queue, int allocSiteID) {\r
+  return (queue[allocSiteID]).size == 0;\r
 }\r
 \r
-//NOTE: Only the traverser should be able to call this function and it clears the entire chain.\r
-void resolveChain(struct WaitingQueue * queue, int allocSiteID) {\r
-  struct BinVector * head;\r
-  struct BinVector * next;\r
-  struct BinVector * currentVector;\r
-  int i;\r
+//This method should be called by the SESE block\r
+//Return is how many things are removed. -1 would indicate error\r
+int removeFromWaitingQueue(WaitingQueueBin * wQueue, int allocSiteID, int TraverserID) {\r
+  TraverserResumeDataFromWaitingQ * td;\r
+  WaitingQueueBin * be = &(wQueue[allocSiteID]);\r
+  int count = 0;\r
+\r
+  if(wQueue[allocSiteID].size == 0)\r
+    return -1; //error\r
+\r
   do {\r
-    head = (struct BinVector *) 0x1;\r
-    LOCKXCHG(((queue->array)[allocSiteID]).head, head);\r
-  } while (head == (struct BinVector *) 0x1);\r
-  //now the current bin is locked.\r
+    td = &(be->head->array[be->head->headIndex]);\r
 \r
-  //I don't think this case would ever happen, but just in case.\r
-  if(head == NULL) {\r
-    ((queue->array)[allocSiteID]).head = NULL; //release lock\r
-    return;\r
-  }\r
+    //TODO perhaps instead of using traverserID to track which variables are resolved, make\r
+    //individual IDs for each.\r
+    if(td->traverserID != TraverserID) {\r
+      return count;\r
+    }\r
 \r
-  //To prevent live lock, clear and unlock the chain and then process it on the side\r
-  currentVector = head;\r
-  ((queue->array)[allocSiteID]).size = 0;\r
-  ((queue->array)[allocSiteID]).tail = NULL;\r
-  ((queue->array)[allocSiteID]).head = NULL; //lock released\r
-\r
-  //processing the chain.\r
-  while(currentVector != NULL) {\r
-    for(i = 0; i < currentVector->index; i++) {\r
-      struct TraverserData * td = &(currentVector->array[i]);\r
-      runRCRTraverse(td->resumePtr, td->traverserID);\r
+    if(traverse(td->resumePtr, td->traverserID) == TRAVERSER_FINISHED) {\r
+      count++; // means we at least got rid of 1 item in the traverser\r
+      be->size--;\r
+\r
+      //fast case\r
+      if(be->size == 0) {\r
+        be->head->headIndex = 0;\r
+        be->head->tailIndex = 0;\r
+        return count;\r
+      }\r
+      else if(++(be->head->headIndex) == be->head->tailIndex){\r
+        //Note: be->head->next CANNOT be NULL since that would imply be->size == 0\r
+        be->head = returnWaitingQueueBinVectorToFreePool(be->head);\r
+      }\r
     }\r
+    else\r
+      return count;\r
 \r
-    //return this vector to the free-pool\r
-    next = currentVector->next;\r
-    returnVectorToFreePool(currentVector);\r
-    currentVector = next;\r
-  }\r
+  } while(1);\r
 }\r
 \r
-void returnVectorToFreePool(struct BinVector *ptr) {\r
-  struct BinVector * freeHead;\r
+WaitingQueueBinVector * returnWaitingQueueBinVectorToFreePool(WaitingQueueBinVector *ptr) {\r
+  WaitingQueueBinVector * freeHead;\r
+  WaitingQueueBinVector * ptrNext;\r
   do {\r
-    freeHead = (struct BinVector *) 0x1;\r
-    //TODO check if this cuts off part of the mem addr or not.\r
-    LOCKXCHG(freeBinVectors, freeHead);\r
-  } while (freeHead == (struct BinVector *) 0x1);\r
+    freeHead = (WaitingQueueBinVector *) 0x1;\r
+    freeHead = LOCKXCHG(&freeBinVectors, freeHead);\r
+  } while (freeHead == (WaitingQueueBinVector *) 0x1);\r
   //free bins locked\r
 \r
+  ptrNext = ptr->next;\r
   if(freeHead == NULL) {\r
     freeBinVectors = ptr; //lock released\r
   }\r
@@ -115,32 +126,36 @@ void returnVectorToFreePool(struct BinVector *ptr) {
     ptr->next = freeHead;\r
     freeBinVectors = ptr; //lock released\r
   }\r
+\r
+  return ptrNext;\r
 }\r
 \r
-struct BinVector * getUsableVector() {\r
+WaitingQueueBinVector * getUsableWaitingQueueBinVector() {\r
   //Attempt to take one from the free bin first\r
-  struct BinVector * ptr;\r
+  WaitingQueueBinVector * ptr;\r
   do {\r
-    ptr = (struct BinVector *) 0x1;\r
-    LOCKXCHG(freeBinVectors, ptr);\r
-  } while (ptr == (struct BinVector *) 0x1);\r
+    ptr = (WaitingQueueBinVector *) 0x1;\r
+    ptr = LOCKXCHG(&freeBinVectors, ptr);\r
+  } while (ptr == (WaitingQueueBinVector *) 0x1);\r
   //free bins locked\r
 \r
   if (ptr == NULL) {\r
     freeBinVectors = NULL; //lock released\r
-    return mallocNewVector();\r
+    return mallocNewWaitingQueueBinVector();\r
   } else {\r
     freeBinVectors = ptr->next; //lock released\r
     ptr->next = NULL;\r
-    ptr->index = 0;\r
+    ptr->headIndex = 0;\r
+    ptr->tailIndex = 0;\r
+    return ptr;\r
   }\r
 }\r
 \r
-struct BinVector * mallocNewVector() {\r
-  struct BinVector * retval = (struct BinVector *) malloc(\r
-      sizeof(struct BinVector));\r
+WaitingQueueBinVector * mallocNewWaitingQueueBinVector() {\r
+  WaitingQueueBinVector * retval = (WaitingQueueBinVector *) malloc(\r
+      sizeof(WaitingQueueBinVector));\r
   retval->next = NULL;\r
-  retval->index = 0;\r
+  retval->headIndex = 0;\r
+  retval->tailIndex = 0;\r
   return retval;\r
 }\r
-\r

diff --git a/Robust/src/Runtime/oooJava/WaitingQueue.h b/Robust/src/Runtime/oooJava/WaitingQueue.h
index 786d91047b14572415a01c668e0eb47307cfdddf..2fac31a6fce05dd730e1c6bcfbbd66bbb19c641b 100644 (file)
--- a/Robust/src/Runtime/oooJava/WaitingQueue.h
+++ b/Robust/src/Runtime/oooJava/WaitingQueue.h
@@ -1,46 +1,39 @@
-/*
- * waitingQueue.h
- *
- *  Created on: Sep 1, 2010
- *      Author: stephey
- */
-#ifndef WAITINGQUEUE_H_
-#define WAITINGQUEUE_H_
-
-#define NUMITEMS 20
-
-/* print header */
-struct TraverserData {
-  void * resumePtr;
-  int traverserID;
-  int effectType;
-};
-
-struct BinVector {
-  struct TraverserData array[NUMITEMS];
-  struct BinVector * next;
-  int index;
-};
-
-struct BinElement {
-  struct BinVector * head;
-  struct BinVector * tail;
-  int size;
-};
-
-
-//TODO in the future, remove this struct all together
-struct WaitingQueue {
-  struct BinElement * array;
-};
-
-void put(int allocSiteID, struct WaitingQueue * queue, int effectType, void * resumePtr, int traverserID);
-int check(struct WaitingQueue * queue, int allocSiteID);
-struct WaitingQueue * mallocWaitingQueue(int size);
-void returnVectorToFreePool(struct BinVector *ptr);
-void resolveChain(struct WaitingQueue * queue, int allocSiteID);
-struct BinVector * mallocNewVector();
-struct BinVector * getUsableVector();
-struct BinVector * getUsableVector();
-
-#endif /* WAITINGQUEUE_H_ */
+/*\r
+ * waitingQueue.h\r
+ *\r
+ *  Created on: Sep 1, 2010\r
+ *      Author: stephey\r
+ */\r
+#ifndef WAITINGQUEUE_H_\r
+#define WAITINGQUEUE_H_\r
+\r
+#define NUMITEMS_WQ 20\r
+\r
+/* print header */\r
+typedef struct TraverserData_WQ {\r
+  void * resumePtr;\r
+  int effectType;\r
+  int traverserID;\r
+} TraverserResumeDataFromWaitingQ;\r
+\r
+typedef struct BinVector_wq {\r
+  struct TraverserData_WQ array[NUMITEMS_WQ];\r
+  struct BinVector_wq * next;\r
+  int headIndex;\r
+  int tailIndex;\r
+} WaitingQueueBinVector;\r
+\r
+\r
+typedef struct BinElement_wq {\r
+  struct BinVector_wq * head;\r
+  struct BinVector_wq * tail;\r
+  int size;\r
+} WaitingQueueBin;\r
+\r
+void putIntoWaitingQueue(int allocSiteID, WaitingQueueBin * queue, int effectType, void * resumePtr, int traverserID);\r
+int isEmptyForWaitingQ(WaitingQueueBin * queue, int allocSiteID);\r
+WaitingQueueBin * mallocWaitingQueue(int size);\r
+WaitingQueueBinVector * returnWaitingQueueBinVectorToFreePool(struct BinVector_wq *ptr);\r
+int removeFromWaitingQueue(WaitingQueueBin * queue, int allocSiteID, int TraverserID);\r
+WaitingQueueBinVector * mallocNewWaitingQueueBinVector();\r
+WaitingQueueBinVector * getUsableWaitingQueueBinVector();\r