nodestack.cc

   1 #include "nodestack.h"
   2 #include "action.h"
   3 #include "common.h"
   4
   5 int Node::total_nodes = 0;
   6
   7 Node::Node(ModelAction *act, Node *parent)
   8         : action(act),
   9         num_threads(parent ? parent->num_threads : 1),
  10         explored_children(num_threads),
  11         backtrack(num_threads)
  12 {
  13         total_nodes++;
  14         if (act && act->get_type() == THREAD_CREATE) {
  15                 num_threads++;
  16                 explored_children.resize(num_threads);
  17                 backtrack.resize(num_threads);
  18         }
  19 }
  20
  21 Node::~Node()
  22 {
  23         if (action)
  24                 delete action;
  25 }
  26
  27 void Node::print()
  28 {
  29         if (action)
  30                 action->print();
  31         else
  32                 printf("******** empty action ********\n");
  33 }
  34
  35 bool Node::has_been_explored(thread_id_t tid)
  36 {
  37         int id = id_to_int(tid);
  38         return explored_children[id];
  39 }
  40
  41 bool Node::backtrack_empty()
  42 {
  43         unsigned int i;
  44         for (i = 0; i < backtrack.size(); i++)
  45                 if (backtrack[i] == true)
  46                         return false;
  47         return true;
  48 }
  49
  50 void Node::explore_child(ModelAction *act)
  51 {
  52         act->set_node(this);
  53         explore(act->get_tid());
  54 }
  55
  56 bool Node::set_backtrack(thread_id_t id)
  57 {
  58         int i = id_to_int(id);
  59         if (backtrack[i])
  60                 return false;
  61         backtrack[i] = true;
  62         return true;
  63 }
  64
  65 thread_id_t Node::get_next_backtrack()
  66 {
  67         /* TODO: find next backtrack */
  68         unsigned int i;
  69         for (i = 0; i < backtrack.size(); i++)
  70                 if (backtrack[i] == true)
  71                         break;
  72         if (i >= backtrack.size())
  73                 return THREAD_ID_T_NONE;
  74         backtrack[i] = false;
  75         return int_to_id(i);
  76 }
  77
  78 bool Node::is_enabled(Thread *t)
  79 {
  80         return id_to_int(t->get_id()) < num_threads;
  81 }
  82
  83 void Node::explore(thread_id_t tid)
  84 {
  85         int i = id_to_int(tid);
  86         backtrack[i] = false;
  87         explored_children[i] = true;
  88 }
  89
  90 static void clear_node_list(node_list_t *list, node_list_t::iterator start,
  91                                                node_list_t::iterator end)
  92 {
  93         node_list_t::iterator it;
  94
  95         for (it = start; it != end; it++)
  96                 delete (*it);
  97         list->erase(start, end);
  98 }
  99
 100 NodeStack::NodeStack()
 101 {
 102         node_list.push_back(new Node());
 103         iter = node_list.begin();
 104 }
 105
 106 NodeStack::~NodeStack()
 107 {
 108         clear_node_list(&node_list, node_list.begin(), node_list.end());
 109 }
 110
 111 void NodeStack::print()
 112 {
 113         node_list_t::iterator it;
 114         printf("............................................\n");
 115         printf("NodeStack printing node_list:\n");
 116         for (it = node_list.begin(); it != node_list.end(); it++) {
 117                 if (it == this->iter)
 118                         printf("vvv following action is the current iterator vvv\n");
 119                 (*it)->print();
 120         }
 121         printf("............................................\n");
 122 }
 123
 124 ModelAction * NodeStack::explore_action(ModelAction *act)
 125 {
 126         DBG();
 127
 128         ASSERT(!node_list.empty());
 129
 130         if (get_head()->has_been_explored(act->get_tid())) {
 131                 /* Discard duplicate ModelAction */
 132                 delete act;
 133                 iter++;
 134         } else { /* Diverging from previous execution */
 135                 /* Clear out remainder of list */
 136                 node_list_t::iterator it = iter;
 137                 it++;
 138                 clear_node_list(&node_list, it, node_list.end());
 139
 140                 /* Record action */
 141                 get_head()->explore_child(act);
 142                 node_list.push_back(new Node(act, get_head()));
 143                 iter++;
 144         }
 145         return (*iter)->get_action();
 146 }
 147
 148 Node * NodeStack::get_head()
 149 {
 150         if (node_list.empty())
 151                 return NULL;
 152         return *iter;
 153 }
 154
 155 Node * NodeStack::get_next()
 156 {
 157         node_list_t::iterator it = iter;
 158         if (node_list.empty()) {
 159                 DEBUG("Empty\n");
 160                 return NULL;
 161         }
 162         it++;
 163         if (it == node_list.end()) {
 164                 DEBUG("At end\n");
 165                 return NULL;
 166         }
 167         return *it;
 168 }
 169
 170 void NodeStack::reset_execution()
 171 {
 172         iter = node_list.begin();
 173 }