nodestack.cc

   1 #include "nodestack.h"
   2 #include "action.h"
   3 #include "common.h"
   4 #include "model.h"
   5
   6 /** @brief Node constructor */
   7 Node::Node(ModelAction *act, int nthreads)
   8         : action(act),
   9         num_threads(nthreads),
  10         explored_children(num_threads),
  11         backtrack(num_threads)
  12 {
  13 }
  14
  15 /** @brief Node desctructor */
  16 Node::~Node()
  17 {
  18         if (action)
  19                 delete action;
  20 }
  21
  22 /** Prints debugging info for the ModelAction associated with this Node */
  23 void Node::print()
  24 {
  25         if (action)
  26                 action->print();
  27         else
  28                 printf("******** empty action ********\n");
  29 }
  30
  31 /**
  32  * Checks if the Thread associated with this thread ID has been explored from
  33  * this Node already.
  34  * @param tid is the thread ID to check
  35  * @return true if this thread choice has been explored already, false
  36  * otherwise
  37  */
  38 bool Node::has_been_explored(thread_id_t tid)
  39 {
  40         int id = id_to_int(tid);
  41         return explored_children[id];
  42 }
  43
  44 /**
  45  * Checks if the backtracking set is empty.
  46  * @return true if the backtracking set is empty
  47  */
  48 bool Node::backtrack_empty()
  49 {
  50         unsigned int i;
  51         for (i = 0; i < backtrack.size(); i++)
  52                 if (backtrack[i] == true)
  53                         return false;
  54         return true;
  55 }
  56
  57 /**
  58  * Explore a child Node using a given ModelAction. This updates both the
  59  * Node-internal and the ModelAction data to associate the ModelAction with
  60  * this Node.
  61  * @param act is the ModelAction to explore
  62  */
  63 void Node::explore_child(ModelAction *act)
  64 {
  65         act->set_node(this);
  66         explore(act->get_tid());
  67 }
  68
  69 /**
  70  * Records a backtracking reference for a thread choice within this Node.
  71  * Provides feedback as to whether this thread choice is already set for
  72  * backtracking.
  73  * @return false if the thread was already set to be backtracked, true
  74  * otherwise
  75  */
  76 bool Node::set_backtrack(thread_id_t id)
  77 {
  78         int i = id_to_int(id);
  79         if (backtrack[i])
  80                 return false;
  81         backtrack[i] = true;
  82         return true;
  83 }
  84
  85 thread_id_t Node::get_next_backtrack()
  86 {
  87         /* TODO: find next backtrack */
  88         unsigned int i;
  89         for (i = 0; i < backtrack.size(); i++)
  90                 if (backtrack[i] == true)
  91                         break;
  92         if (i >= backtrack.size())
  93                 return THREAD_ID_T_NONE;
  94         backtrack[i] = false;
  95         return int_to_id(i);
  96 }
  97
  98 bool Node::is_enabled(Thread *t)
  99 {
 100         return id_to_int(t->get_id()) < num_threads;
 101 }
 102
 103 void Node::explore(thread_id_t tid)
 104 {
 105         int i = id_to_int(tid);
 106         backtrack[i] = false;
 107         explored_children[i] = true;
 108 }
 109
 110 static void clear_node_list(node_list_t *list, node_list_t::iterator start,
 111                                                node_list_t::iterator end)
 112 {
 113         node_list_t::iterator it;
 114
 115         for (it = start; it != end; it++)
 116                 delete (*it);
 117         list->erase(start, end);
 118 }
 119
 120 NodeStack::NodeStack()
 121         : total_nodes(0)
 122 {
 123         node_list.push_back(new Node());
 124         total_nodes++;
 125         iter = node_list.begin();
 126 }
 127
 128 NodeStack::~NodeStack()
 129 {
 130         clear_node_list(&node_list, node_list.begin(), node_list.end());
 131 }
 132
 133 void NodeStack::print()
 134 {
 135         node_list_t::iterator it;
 136         printf("............................................\n");
 137         printf("NodeStack printing node_list:\n");
 138         for (it = node_list.begin(); it != node_list.end(); it++) {
 139                 if (it == this->iter)
 140                         printf("vvv following action is the current iterator vvv\n");
 141                 (*it)->print();
 142         }
 143         printf("............................................\n");
 144 }
 145
 146 ModelAction * NodeStack::explore_action(ModelAction *act)
 147 {
 148         DBG();
 149
 150         ASSERT(!node_list.empty());
 151
 152         if (get_head()->has_been_explored(act->get_tid())) {
 153                 /* Discard duplicate ModelAction */
 154                 delete act;
 155                 iter++;
 156         } else { /* Diverging from previous execution */
 157                 /* Clear out remainder of list */
 158                 node_list_t::iterator it = iter;
 159                 it++;
 160                 clear_node_list(&node_list, it, node_list.end());
 161
 162                 /* Record action */
 163                 get_head()->explore_child(act);
 164                 node_list.push_back(new Node(act, model->get_num_threads()));
 165                 total_nodes++;
 166                 iter++;
 167         }
 168         return (*iter)->get_action();
 169 }
 170
 171 Node * NodeStack::get_head()
 172 {
 173         if (node_list.empty())
 174                 return NULL;
 175         return *iter;
 176 }
 177
 178 Node * NodeStack::get_next()
 179 {
 180         node_list_t::iterator it = iter;
 181         if (node_list.empty()) {
 182                 DEBUG("Empty\n");
 183                 return NULL;
 184         }
 185         it++;
 186         if (it == node_list.end()) {
 187                 DEBUG("At end\n");
 188                 return NULL;
 189         }
 190         return *it;
 191 }
 192
 193 void NodeStack::reset_execution()
 194 {
 195         iter = node_list.begin();
 196 }