From 7c90236bf072b62fc1ec83c3e9bd2c535c84a592 Mon Sep 17 00:00:00 2001
From: stephey <stephey>
Date: Sun, 26 Sep 2010 05:44:16 +0000
Subject: [PATCH] Tested and Debugged versions of waitingQueue for the
 hashStructure.

---
 Robust/src/Runtime/oooJava/WaitingQueue.c | 185 ++++++++++++----------
 Robust/src/Runtime/oooJava/WaitingQueue.h |  85 +++++-----
 2 files changed, 139 insertions(+), 131 deletions(-)

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