tree.h

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