cyclegraph.h

   1 /** @file cyclegraph.h @brief Data structure to track ordering
   2  *  constraints on modification order.  The idea is to see whether a
   3  *  total order exists that satisfies the ordering constriants.*/
   4
   5 #ifndef CYCLEGRAPH_H
   6 #define CYCLEGRAPH_H
   7
   8 #include "hashtable.h"
   9 #include <vector>
  10 #include <inttypes.h>
  11
  12 class CycleNode;
  13 class ModelAction;
  14
  15 /** @brief A graph of Model Actions for tracking cycles. */
  16 class CycleGraph {
  17  public:
  18         CycleGraph();
  19         ~CycleGraph();
  20         void addEdge(const ModelAction *from, const ModelAction *to);
  21         bool checkForCycles();
  22         void addRMWEdge(const ModelAction *from, const ModelAction *to);
  23
  24  private:
  25         CycleNode * getNode(const ModelAction *);
  26         HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
  27         bool checkReachable(CycleNode *from, CycleNode *to);
  28         bool hasCycles;
  29 };
  30
  31 class CycleNode {
  32  public:
  33         CycleNode(const ModelAction *action);
  34         void addEdge(CycleNode * node);
  35         std::vector<CycleNode *> * getEdges();
  36         bool setRMW(CycleNode *);
  37         CycleNode* getRMW();
  38
  39  private:
  40         const ModelAction *action;
  41         std::vector<CycleNode *> edges;
  42         CycleNode * hasRMW;
  43 };
  44
  45 #endif