X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=nodestack.cc;h=f74a2938992078a9eeaabc90e9a5100da8b7fabf;hb=4e8626fa3721aededd84133382625e20ae6490cf;hp=74e6a11a43bbeacab4cc0e3dc39a9ee0dc279760;hpb=b8bcaaa5a4b4d2413e3a0f419bbb91c540b28e50;p=model-checker.git

diff --git a/nodestack.cc b/nodestack.cc
index 74e6a11..f74a293 100644
--- a/nodestack.cc
+++ b/nodestack.cc
@@ -3,20 +3,41 @@
 #include "common.h"
 #include "model.h"
 
-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 */
 Node::~Node()
 {
 	if (action)
 		delete action;
 }
 
+/** Prints debugging info for the ModelAction associated with this Node */
 void Node::print()
 {
 	if (action)
@@ -25,33 +46,51 @@ void Node::print()
 		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;
 }
 
+/**
+ * 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());
 }
 
+/**
+ * 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;
 }
 
@@ -65,6 +104,7 @@ thread_id_t Node::get_next_backtrack()
 	if (i >= backtrack.size())
 		return THREAD_ID_T_NONE;
 	backtrack[i] = false;
+	numBacktracks--;
 	return int_to_id(i);
 }
 
@@ -73,10 +113,22 @@ bool Node::is_enabled(Thread *t)
 	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;
 }
 
@@ -123,22 +175,21 @@ ModelAction * NodeStack::explore_action(ModelAction *act)
 	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()