+/** @file cyclegraph.h @brief Data structure to track ordering
+ * constraints on modification order. The idea is to see whether a
+ * total order exists that satisfies the ordering constriants.*/
+
#ifndef CYCLEGRAPH_H
#define CYCLEGRAPH_H
#include "hashtable.h"
-#include "action.h"
#include <vector>
+#include <inttypes.h>
class CycleNode;
+class ModelAction;
/** @brief A graph of Model Actions for tracking cycles. */
class CycleGraph {
public:
CycleGraph();
- void addEdge(ModelAction *from, ModelAction *to);
+ ~CycleGraph();
+ void addEdge(const ModelAction *from, const ModelAction *to);
bool checkForCycles();
+ void addRMWEdge(const ModelAction *from, const ModelAction *rmw);
+
+ bool checkReachable(const ModelAction *from, const ModelAction *to);
private:
- CycleNode * getNode(ModelAction *);
- HashTable<class ModelAction *, class CycleNode *, uintptr_t, 4> actionToNode;
+ CycleNode * getNode(const ModelAction *);
+
+ /** @brief A table for mapping ModelActions to CycleNodes */
+ HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
+
bool checkReachable(CycleNode *from, CycleNode *to);
-
- bool hasCycles;
+ /** @brief A flag: true if this graph contains cycles */
+ bool hasCycles;
};
+/** @brief A node within a CycleGraph; corresponds to one ModelAction */
class CycleNode {
public:
- CycleNode(ModelAction *action);
+ CycleNode(const ModelAction *action);
void addEdge(CycleNode * node);
- std::vector<class CycleNode *> * getEdges();
+ std::vector<CycleNode *> * getEdges();
+ bool setRMW(CycleNode *);
+ CycleNode* getRMW();
private:
- ModelAction *action;
- std::vector<class CycleNode *> edges;
+ /** @brief The ModelAction that this node represents */
+ const ModelAction *action;
+
+ /** @brief The edges leading out from this node */
+ std::vector<CycleNode *> edges;
+
+ /** Pointer to a RMW node that reads from this node, or NULL, if none
+ * exists */
+ CycleNode * hasRMW;
};
#endif