#include "common.h"
#include "model.h"
-/** @brief Node constructor */
-Node::Node(ModelAction *act, int nthreads)
+/**
+ * @brief Node constructor
+ *
+ * Constructs a single Node for use in a NodeStack. Each Node is associated
+ * with exactly one ModelAction (exception: the first Node should be created
+ * as an empty stub, to represent the first thread "choice") and up to one
+ * parent.
+ *
+ * @param act The ModelAction to associate with this Node. May be NULL.
+ * @param par The parent Node in the NodeStack. May be NULL if there is no
+ * parent.
+ * @param nthreads The number of threads which exist at this point in the
+ * execution trace.
+ */
+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()
{
+ if (act)
+ act->set_node(this);
}
/** @brief Node desctructor */
*/
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
+ * Mark the appropriate backtracking infromation for exploring a thread choice.
+ * @param act The ModelAction to explore
*/
void Node::explore_child(ModelAction *act)
{
- act->set_node(this);
explore(act->get_tid());
}
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.push_back(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;
}
/* Record action */
get_head()->explore_child(act);
- node_list.push_back(new Node(act, model->get_num_threads()));
+ node_list.push_back(new Node(act, get_head(), model->get_num_threads()));
total_nodes++;
iter++;
return NULL;