Performance fix; delete unused data structures

[c11tester.git] / funcnode.cc

diff --git a/funcnode.cc b/funcnode.cc
index 9228dc773fd7f03cf2b88a3ff42af38f6aaa0795..b28fbd5bb5c8b925af9cc0573be8cecec1cd16b6 100644 (file)
--- a/funcnode.cc
+++ b/funcnode.cc
@@ -139,7 +139,7 @@ void FuncNode::update_tree(action_list_t * act_list)
        if (act_list == NULL || act_list->size() == 0)
                return;
 
-       HashTable<void *, value_set_t *, uintptr_t, 4> * write_history = history->getWriteHistory();
+       HashTable<void *, value_set_t *, uintptr_t, 0> * write_history = history->getWriteHistory();
 
        /* build inst_list from act_list for later processing */
        func_inst_list_t inst_list;
@@ -640,6 +640,51 @@ void FuncNode::add_out_edge(FuncNode * other)
        }
 }
 
+/* Compute the distance between this FuncNode and the target node.
+ * Return -1 if the target node is unreachable or the actual distance
+ * is greater than max_step.
+ */
+int FuncNode::compute_distance(FuncNode * target, int max_step)
+{
+       if (target == NULL)
+               return -1;
+       else if (target == this)
+               return 0;
+
+       SnapList<FuncNode *> queue;
+       HashTable<FuncNode *, int, uintptr_t, 0> distances(128);
+
+       queue.push_back(this);
+       distances.put(this, 0);
+
+       while (!queue.empty()) {
+               FuncNode * curr = queue.front();
+               queue.pop_front();
+               int dist = distances.get(curr);
+
+               if (max_step <= dist)
+                       return -1;
+
+               ModelList<FuncNode *> * outEdges = curr->get_out_edges();
+               mllnode<FuncNode *> * it;
+               for (it = outEdges->begin(); it != NULL; it = it->getNext()) {
+                       FuncNode * out_node = it->getVal();
+
+                       /* This node has not been visited before */
+                       if ( !distances.contains(out_node) ) {
+                               if (out_node == target)
+                                       return dist + 1;
+
+                               queue.push_back(out_node);
+                               distances.put(out_node, dist + 1);
+                       }
+               }
+       }
+
+       /* Target node is unreachable */
+       return -1;
+}
+
 void FuncNode::print_predicate_tree()
 {
        model_print("digraph function_%s {\n", func_name);