tree.h

   1 #include <set>
   2 #include <map>
   3 #include "threads.h"
   4
   5 typedef thread_id_t tree_t;
   6
   7 /*
   8  * An n-ary tree
   9  *
  10  * A tree with n possible branches from each node - used for recording the
  11  * execution paths we've executed / backtracked
  12  */
  13 class TreeNode {
  14 public:
  15         TreeNode(TreeNode *par);
  16         ~TreeNode();
  17         bool hasBeenExplored(tree_t id) { return children.find(id) != children.end(); }
  18         TreeNode *exploreChild(tree_t id);
  19         tree_t getNextBacktrack();
  20
  21         /* Return 1 if already in backtrack, 0 otherwise */
  22         int setBacktrack(tree_t id);
  23         TreeNode *getRoot();
  24         static int getTotalNodes() { return TreeNode::totalNodes; }
  25 private:
  26         TreeNode *parent;
  27         std::map<tree_t, class TreeNode *> children;
  28         std::set<tree_t> backtrack;
  29         static int totalNodes;
  30 };