projects
/
model-checker.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
model: add work queue loop
[model-checker.git]
/
cyclegraph.h
diff --git
a/cyclegraph.h
b/cyclegraph.h
index a98e68c972e77cf6b615cff94521bd872df4e26a..81d736962dcb6893c8ef213b9571454c24ac5ea6 100644
(file)
--- a/
cyclegraph.h
+++ b/
cyclegraph.h
@@
-1,3
+1,7
@@
+/** @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
#ifndef CYCLEGRAPH_H
#define CYCLEGRAPH_H
@@
-5,6
+9,8
@@
#include <vector>
#include <inttypes.h>
#include <vector>
#include <inttypes.h>
+#include "mymemory.h"
+
class CycleNode;
class ModelAction;
class CycleNode;
class ModelAction;
@@
-15,23
+21,60
@@
class CycleGraph {
~CycleGraph();
void addEdge(const ModelAction *from, const ModelAction *to);
bool checkForCycles();
~CycleGraph();
void addEdge(const ModelAction *from, const ModelAction *to);
bool checkForCycles();
+ bool checkForRMWViolation();
+ void addRMWEdge(const ModelAction *from, const ModelAction *rmw);
+
+ bool checkReachable(const ModelAction *from, const ModelAction *to);
+ void startChanges();
+ void commitChanges();
+ void rollbackChanges();
+ SNAPSHOTALLOC
private:
CycleNode * getNode(const ModelAction *);
private:
CycleNode * getNode(const ModelAction *);
+
+ /** @brief A table for mapping ModelActions to CycleNodes */
HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
+
bool checkReachable(CycleNode *from, CycleNode *to);
bool checkReachable(CycleNode *from, CycleNode *to);
+
+ /** @brief A flag: true if this graph contains cycles */
bool hasCycles;
bool hasCycles;
+ bool oldCycles;
+
+ bool hasRMWViolation;
+ bool oldRMWViolation;
+
+ std::vector<CycleNode *> rollbackvector;
+ std::vector<CycleNode *> rmwrollbackvector;
};
};
+/** @brief A node within a CycleGraph; corresponds to one ModelAction */
class CycleNode {
public:
CycleNode(const ModelAction *action);
void addEdge(CycleNode * node);
std::vector<CycleNode *> * getEdges();
class CycleNode {
public:
CycleNode(const ModelAction *action);
void addEdge(CycleNode * node);
std::vector<CycleNode *> * getEdges();
+ bool setRMW(CycleNode *);
+ CycleNode* getRMW();
+ void popEdge() {
+ edges.pop_back();
+ };
+ void clearRMW() {
+ hasRMW=NULL;
+ }
+ SNAPSHOTALLOC
private:
private:
+ /** @brief The ModelAction that this node represents */
const ModelAction *action;
const ModelAction *action;
+
+ /** @brief The edges leading out from this node */
std::vector<CycleNode *> edges;
std::vector<CycleNode *> edges;
+
+ /** Pointer to a RMW node that reads from this node, or NULL, if none
+ * exists */
+ CycleNode * hasRMW;
};
#endif
};
#endif