* @param action The ModelAction to find a node for
* @return The CycleNode paired with this action
*/
-CycleNode * CycleGraph::getNode(const ModelAction *action)
+CycleNode * CycleGraph::getNode(ModelAction *action)
{
CycleNode *node = getNode_noCreate(action);
if (node == NULL) {
* @param tonode The edge points to this CycleNode
* @return True, if new edge(s) are added; otherwise false
*/
-void CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
+void CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode, bool forceedge)
{
//quick check whether edge is redundant
- if (checkReachable(fromnode, tonode))
+ if (checkReachable(fromnode, tonode) && !forceedge) {
return;
-
- CycleNode *edgeSrcNode = fromnode;
+ }
/*
* If the fromnode has a rmwnode, we should
* follow its RMW chain to add an edge at the end.
*/
- CycleNode *rmwnode = fromnode->getRMW();
- if (rmwnode) {
- while (rmwnode->getRMW())
- rmwnode = rmwnode->getRMW();
- edgeSrcNode = rmwnode;
+ while (CycleNode * nextnode = fromnode->getRMW()) {
+ if (nextnode == tonode)
+ break;
+ fromnode = nextnode;
}
- edgeSrcNode->addEdge(tonode); //Add edge to edgeSrcNode
+ fromnode->addEdge(tonode); //Add edge to edgeSrcNode
/* Propagate clock vector changes */
- if (tonode->cv->merge(edgeSrcNode->cv)) {
- queue->push_back(edgeSrcNode);
+ if (tonode->cv->merge(fromnode->cv)) {
+ queue->push_back(tonode);
while(!queue->empty()) {
const CycleNode *node = queue->back();
+ queue->pop_back();
unsigned int numedges = node->getNumEdges();
for(unsigned int i = 0;i < numedges;i++) {
CycleNode * enode = node->getEdge(i);
* @param rmw The edge points to this ModelAction; this action must read from
* the ModelAction from
*/
-void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw)
+void CycleGraph::addRMWEdge(ModelAction *from, ModelAction *rmw)
{
ASSERT(from);
ASSERT(rmw);
CycleNode *fromnode = getNode(from);
CycleNode *rmwnode = getNode(rmw);
-
/* We assume that this RMW has no RMW reading from it yet */
ASSERT(!rmwnode->getRMW());
if (tonode != rmwnode) {
rmwnode->addEdge(tonode);
}
+ tonode->removeInEdge(fromnode);
}
+ fromnode->edges.clear();
+
+ addNodeEdge(fromnode, rmwnode, true);
+}
- addNodeEdge(fromnode, rmwnode);
+void CycleGraph::addEdges(SnapList<ModelAction *> * edgeset, ModelAction *to) {
+ for(sllnode<ModelAction*> * it = edgeset->begin();it!=NULL;) {
+ ModelAction *act = it->getVal();
+ CycleNode *node = getNode(act);
+ sllnode<ModelAction*> * it2 = it;
+ it2=it2->getNext();
+ for(;it2!=NULL; ) {
+ ModelAction *act2 = it2->getVal();
+ CycleNode *node2 = getNode(act2);
+ if (checkReachable(node, node2)) {
+ it = edgeset->erase(it);
+ goto endouterloop;
+ } else if (checkReachable(node2, node)) {
+ it2 = edgeset->erase(it2);
+ goto endinnerloop;
+ }
+ it2=it2->getNext();
+endinnerloop:
+ ;
+ }
+ it=it->getNext();
+endouterloop:
+ ;
+ }
+ for(sllnode<ModelAction*> *it = edgeset->begin();it!=NULL;it=it->getNext()) {
+ ModelAction *from = it->getVal();
+ addEdge(from, to, from->get_tid() == to->get_tid());
+ }
}
/**
* @return True, if new edge(s) are added; otherwise false
*/
-void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to)
+void CycleGraph::addEdge(ModelAction *from, ModelAction *to)
{
ASSERT(from);
ASSERT(to);
CycleNode *fromnode = getNode(from);
CycleNode *tonode = getNode(to);
- addNodeEdge(fromnode, tonode);
+ addNodeEdge(fromnode, tonode, false);
+}
+
+void CycleGraph::addEdge(ModelAction *from, ModelAction *to, bool forceedge)
+{
+ ASSERT(from);
+ ASSERT(to);
+
+ CycleNode *fromnode = getNode(from);
+ CycleNode *tonode = getNode(to);
+
+ addNodeEdge(fromnode, tonode, forceedge);
}
#if SUPPORT_MOD_ORDER_DUMP
return checkReachable(fromnode, tonode);
}
+void CycleGraph::freeAction(const ModelAction * act) {
+ CycleNode *cn = actionToNode.remove(act);
+ for(unsigned int i=0;i<cn->edges.size();i++) {
+ CycleNode *dst = cn->edges[i];
+ dst->removeInEdge(cn);
+ }
+ for(unsigned int i=0;i<cn->inedges.size();i++) {
+ CycleNode *src = cn->inedges[i];
+ src->removeEdge(cn);
+ }
+ delete cn;
+}
+
/**
* @brief Constructor for a CycleNode
* @param act The ModelAction for this node
*/
-CycleNode::CycleNode(const ModelAction *act) :
+CycleNode::CycleNode(ModelAction *act) :
action(act),
hasRMW(NULL),
cv(new ClockVector(NULL, act))
{
}
+CycleNode::~CycleNode() {
+ delete cv;
+}
+
+void CycleNode::removeInEdge(CycleNode *src) {
+ for(unsigned int i=0;i < inedges.size();i++) {
+ if (inedges[i] == src) {
+ inedges[i] = inedges[inedges.size()-1];
+ inedges.pop_back();
+ break;
+ }
+ }
+}
+
+void CycleNode::removeEdge(CycleNode *dst) {
+ for(unsigned int i=0;i < edges.size();i++) {
+ if (edges[i] == dst) {
+ edges[i] = edges[edges.size()-1];
+ edges.pop_back();
+ break;
+ }
+ }
+}
+
/**
* @param i The index of the edge to return
* @returns The CycleNode edge indexed by i
}
/**
- * @brief Remove a (forward) edge from this CycleNode
- * @return The CycleNode which was popped, if one exists; otherwise NULL
+ * @param i The index of the edge to return
+ * @returns The CycleNode edge indexed by i
*/
-CycleNode * CycleNode::removeEdge()
+CycleNode * CycleNode::getInEdge(unsigned int i) const
{
- if (edges.empty())
- return NULL;
+ return inedges[i];
+}
- CycleNode *ret = edges.back();
- edges.pop_back();
- return ret;
+/** @returns The number of edges leaving this CycleNode */
+unsigned int CycleNode::getNumInEdges() const
+{
+ return inedges.size();
}
/**
if (edges[i] == node)
return;
edges.push_back(node);
+ node->inedges.push_back(this);
}
/** @returns the RMW CycleNode that reads from the current CycleNode */
projects / c11tester.git / blobdiff