cyclegraph.cc

   1 #include "cyclegraph.h"
   2 #include "action.h"
   3
   4 /** Initializes a CycleGraph object. */
   5 CycleGraph::CycleGraph() {
   6         hasCycles=false;
   7 }
   8
   9 CycleGraph::~CycleGraph() {
  10 }
  11
  12 /** Returns the CycleNode for a given ModelAction. */
  13 CycleNode * CycleGraph::getNode(const ModelAction * action) {
  14         CycleNode *node=actionToNode.get(action);
  15         if (node==NULL) {
  16                 node=new CycleNode(action);
  17                 actionToNode.put(action, node);
  18         }
  19         return node;
  20 }
  21
  22 /** Adds an edge between two ModelActions. */
  23
  24 //the event to happens after the event from
  25
  26 void CycleGraph::addEdge(const ModelAction *to, const ModelAction *from) {
  27         CycleNode *fromnode=getNode(from);
  28         CycleNode *tonode=getNode(to);
  29
  30         if (!hasCycles) {
  31                 // Check for Cycles
  32                 hasCycles=checkReachable(tonode, fromnode);
  33         }
  34         fromnode->addEdge(tonode);
  35
  36         CycleNode * rmwnode=fromnode->getRMW();
  37
  38         //If the fromnode has a rmwnode that is not the tonode, we
  39         //should add an edge between its rmwnode and the tonode
  40
  41         if (rmwnode!=NULL&&rmwnode!=tonode) {
  42                 if (!hasCycles) {
  43                         // Check for Cycles
  44                         hasCycles=checkReachable(tonode, rmwnode);
  45                 }
  46                 rmwnode->addEdge(tonode);
  47         }
  48 }
  49
  50 //event rmw that reads from the node from
  51
  52 void CycleGraph::addRMWEdge(const ModelAction *rmw, const ModelAction * from) {
  53         CycleNode *fromnode=getNode(from);
  54         CycleNode *rmwnode=getNode(rmw);
  55
  56         /* Two RMW actions cannot read from the same write. */
  57         if (fromnode->setRMW(rmwnode)) {
  58                 hasCycles=true;
  59         }
  60
  61         /* Transfer all outgoing edges from the from node to the rmw node */
  62         /* This process cannot add a cycle because rmw should not have any
  63                  incoming edges yet.*/
  64         std::vector<CycleNode *> * edges=fromnode->getEdges();
  65         for(unsigned int i=0;i<edges->size();i++) {
  66                 CycleNode * tonode=(*edges)[i];
  67                 rmwnode->addEdge(tonode);
  68         }
  69
  70         fromnode->addEdge(rmwnode);
  71 }
  72
  73
  74 /** Checks whether the first CycleNode can reach the second one. */
  75 bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
  76         std::vector<CycleNode *> queue;
  77         HashTable<CycleNode *, CycleNode *, uintptr_t, 4> discovered;
  78
  79         queue.push_back(from);
  80         discovered.put(from, from);
  81         while(!queue.empty()) {
  82                 CycleNode * node=queue.back();
  83                 queue.pop_back();
  84                 if (node==to)
  85                         return true;
  86
  87                 for(unsigned int i=0;i<node->getEdges()->size();i++) {
  88                         CycleNode *next=(*node->getEdges())[i];
  89                         if (!discovered.contains(next)) {
  90                                 discovered.put(next,next);
  91                                 queue.push_back(next);
  92                         }
  93                 }
  94         }
  95         return false;
  96 }
  97
  98 /** Returns whether a CycleGraph contains cycles. */
  99 bool CycleGraph::checkForCycles() {
 100         return hasCycles;
 101 }
 102
 103 /** Constructor for a CycleNode. */
 104 CycleNode::CycleNode(const ModelAction *modelaction) {
 105         action=modelaction;
 106         hasRMW=NULL;
 107 }
 108
 109 /** Returns a vector of the edges from a CycleNode. */
 110 std::vector<CycleNode *> * CycleNode::getEdges() {
 111         return &edges;
 112 }
 113
 114 /** Adds an edge to a CycleNode. */
 115 void CycleNode::addEdge(CycleNode * node) {
 116         edges.push_back(node);
 117 }
 118
 119 CycleNode* CycleNode::getRMW() {
 120         return hasRMW;
 121 }
 122
 123 bool CycleNode::setRMW(CycleNode * node) {
 124         CycleNode * oldhasRMW=hasRMW;
 125         hasRMW=node;
 126         return (oldhasRMW!=NULL);
 127 }