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         bool checkForRMWViolation();
  23         void addRMWEdge(const ModelAction *from, const ModelAction *rmw);
  24
  25         bool checkReachable(const ModelAction *from, const ModelAction *to);
  26         void startChanges();
  27         void commitChanges();
  28         void rollbackChanges();
  29
  30  private:
  31         CycleNode * getNode(const ModelAction *);
  32
  33         /** @brief A table for mapping ModelActions to CycleNodes */
  34         HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
  35
  36         bool checkReachable(CycleNode *from, CycleNode *to);
  37
  38         /** @brief A flag: true if this graph contains cycles */
  39         bool hasCycles;
  40         bool oldCycles;
  41
  42         bool hasRMWViolation;
  43         bool oldRMWViolation;
  44
  45         std::vector<CycleNode *> rollbackvector;
  46         std::vector<CycleNode *> rmwrollbackvector;
  47 };
  48
  49 /** @brief A node within a CycleGraph; corresponds to one ModelAction */
  50 class CycleNode {
  51  public:
  52         CycleNode(const ModelAction *action);
  53         void addEdge(CycleNode * node);
  54         std::vector<CycleNode *> * getEdges();
  55         bool setRMW(CycleNode *);
  56         CycleNode* getRMW();
  57         void popEdge() {
  58                 edges.pop_back();
  59         };
  60         void clearRMW() {
  61                 hasRMW=NULL;
  62         }
  63
  64  private:
  65         /** @brief The ModelAction that this node represents */
  66         const ModelAction *action;
  67
  68         /** @brief The edges leading out from this node */
  69         std::vector<CycleNode *> edges;
  70
  71         /** Pointer to a RMW node that reads from this node, or NULL, if none
  72          * exists */
  73         CycleNode * hasRMW;
  74 };
  75
  76 #endif