#include "common.h"
#include "model.h"
-Node::Node(ModelAction *act, int nthreads)
+/** @brief Node constructor */
+Node::Node(ModelAction *act, Node *par, int nthreads)
: action(act),
+ parent(par),
num_threads(nthreads),
explored_children(num_threads),
- backtrack(num_threads)
+ backtrack(num_threads),
+ numBacktracks(0),
+ may_read_from()
{
}
+/** @brief Node desctructor */
Node::~Node()
{
if (action)
delete action;
}
+/** Prints debugging info for the ModelAction associated with this Node */
void Node::print()
{
if (action)
printf("******** empty action ********\n");
}
+/**
+ * Checks if the Thread associated with this thread ID has been explored from
+ * this Node already.
+ * @param tid is the thread ID to check
+ * @return true if this thread choice has been explored already, false
+ * otherwise
+ */
bool Node::has_been_explored(thread_id_t tid)
{
int id = id_to_int(tid);
return explored_children[id];
}
+/**
+ * Checks if the backtracking set is empty.
+ * @return true if the backtracking set is empty
+ */
bool Node::backtrack_empty()
{
- unsigned int i;
- for (i = 0; i < backtrack.size(); i++)
- if (backtrack[i] == true)
- return false;
- return true;
+ return numBacktracks == 0;
}
+/**
+ * Explore a child Node using a given ModelAction. This updates both the
+ * Node-internal and the ModelAction data to associate the ModelAction with
+ * this Node.
+ * @param act is the ModelAction to explore
+ */
void Node::explore_child(ModelAction *act)
{
act->set_node(this);
explore(act->get_tid());
}
+/**
+ * Records a backtracking reference for a thread choice within this Node.
+ * Provides feedback as to whether this thread choice is already set for
+ * backtracking.
+ * @return false if the thread was already set to be backtracked, true
+ * otherwise
+ */
bool Node::set_backtrack(thread_id_t id)
{
int i = id_to_int(id);
if (backtrack[i])
return false;
backtrack[i] = true;
+ numBacktracks++;
return true;
}
if (i >= backtrack.size())
return THREAD_ID_T_NONE;
backtrack[i] = false;
+ numBacktracks--;
return int_to_id(i);
}
return id_to_int(t->get_id()) < num_threads;
}
+/**
+ * Add an action to the may_read_from set.
+ * @param act is the action to add
+ */
+void Node::add_read_from(ModelAction *act)
+{
+ may_read_from.insert(act);
+}
+
void Node::explore(thread_id_t tid)
{
int i = id_to_int(tid);
- backtrack[i] = false;
+ if (backtrack[i]) {
+ backtrack[i] = false;
+ numBacktracks--;
+ }
explored_children[i] = true;
}
ASSERT(!node_list.empty());
if (get_head()->has_been_explored(act->get_tid())) {
- /* Discard duplicate ModelAction */
- delete act;
- iter++;
- } else { /* Diverging from previous execution */
- /* Clear out remainder of list */
- node_list_t::iterator it = iter;
- it++;
- clear_node_list(&node_list, it, node_list.end());
-
- /* Record action */
- get_head()->explore_child(act);
- node_list.push_back(new Node(act, model->get_num_threads()));
- total_nodes++;
iter++;
+ return (*iter)->get_action();
}
- return (*iter)->get_action();
+
+ /* Diverging from previous execution; clear out remainder of list */
+ node_list_t::iterator it = iter;
+ it++;
+ clear_node_list(&node_list, it, node_list.end());
+
+ /* Record action */
+ get_head()->explore_child(act);
+ node_list.push_back(new Node(act, get_head(), model->get_num_threads()));
+ total_nodes++;
+ iter++;
+ return NULL;
}
Node * NodeStack::get_head()