00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include <cstdlib>
00012 #include <cstdio>
00013 #include "depGraph.hpp"
00014
00015
00016
00017
00018
00020 bool DepNode::depends (int xi, bool recursive,
00021 std::set <DepNode *, compNode> *already_visited) const {
00022
00023
00024 for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin ();
00025 i != depList_ -> end (); ++i) {
00026
00027 if (!already_visited ||
00028 (already_visited -> find (*i) == already_visited -> end ())) {
00029
00030 if (((*i) -> Index () == xi) ||
00031 (recursive &&
00032 ((*i) -> depends (xi, recursive, already_visited))))
00033 {
00034 #ifdef DEBUG
00035 printf ("%d <- ", (*i) -> Index ());
00036 fflush (stdout);
00037 #endif
00038 return true;
00039 } else {
00040 if (already_visited) {
00041 already_visited -> insert (*i);
00042
00043
00044
00045
00046
00047 }
00048 }
00049 }
00050 }
00051
00052 return false;
00053 }
00054
00055
00057 void DepNode::createOrder (DepGraph *g) {
00058
00059 if (order_ != -1) return;
00060
00061 if (order_ == -2) {
00062
00063 printf ("detected cycle in creating order, exiting\n");
00064 exit (-1);
00065 }
00066
00067 order_ = -2;
00068
00069 for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin();
00070 i != depList_ -> end (); ++i)
00071 if ((*i) -> Order () == -1)
00072 (*i) -> createOrder (g);
00073
00074 if (order_ == -2)
00075 order_ = g -> Counter () ++;
00076 }
00077
00078
00080 void DepNode::print (int indent, bool descend) const {
00081
00082 printf ("%d ", index_);
00083 if (order_ >= 0) printf ("[%d]", order_);
00084 fflush (stdout);
00085
00086 if (depList_ -> size () > 0) {
00087 printf ("("); fflush (stdout);
00088
00089 for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin();
00090 i != depList_ -> end (); ++i)
00091 if (descend)
00092 (*i) -> print (indent + 1, descend);
00093 else printf ("%d ", (*i) -> Index ());
00094
00095 printf (") "); fflush (stdout);
00096 }
00097 }
00098
00099
00100
00101
00102
00104 void DepGraph::insert (exprVar *var) {
00105
00106 DepNode *el = new DepNode (var -> Index ());
00107 std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
00108
00109 if (i == vertices_ . end ())
00110 vertices_.insert (el);
00111 else delete el;
00112 }
00113
00114
00116 void DepGraph::insert (exprAux *aux) {
00117
00118 if (!aux) return;
00119
00120 DepNode *el = new DepNode (aux -> Index ());
00121 std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
00122
00123 if (i == vertices_ . end ()) {
00124 vertices_.insert (el);
00125 aux -> Image () -> fillDepSet (el -> DepList (), this);
00126 } else {
00127 aux -> Image () -> fillDepSet ((*i) -> DepList (), this);
00128 delete el;
00129 }
00130 }
00131
00132
00134 void DepGraph::erase (exprVar *var) {
00135
00136 DepNode *el = new DepNode (var -> Index ());
00137 std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
00138
00139 if (i != vertices_ . end ())
00140 vertices_.erase (i);
00141 delete el;
00142 }
00143
00145 bool DepGraph::depends (int wi, int xi, bool recursive) {
00146
00147 DepNode *el = new DepNode (wi);
00148 std::set <DepNode *, compNode>::iterator i = vertices_. find (el);
00149 delete el;
00150
00151 std::set <DepNode *, compNode> already_visited;
00152
00153 if (i != vertices_. end ())
00154 return (*i) -> depends (xi, recursive, &already_visited);
00155 else return false;
00156 }
00157
00158
00160 void DepGraph::createOrder () {
00161
00162 for (std::set <DepNode *, compNode>::iterator i = vertices_. begin();
00163 i != vertices_. end (); ++i)
00164 (*i) -> createOrder (this);
00165 }
00166
00167
00169 void DepGraph::print (bool descend) {
00170
00171 printf ("Dependence graph: \n");
00172 for (std::set <DepNode *, compNode>::iterator i = vertices_. begin();
00173 i != vertices_. end (); ++i) {
00174 (*i) -> print (0, descend);
00175 printf ("\n");
00176 }
00177 }
00178
00179
00181 DepNode *DepGraph::lookup (int index) {
00182
00183 DepNode *el = new DepNode (index), *ret;
00184 std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
00185
00186 ret = (i == vertices_.end ()) ? NULL : (*i);
00187
00188 delete el;
00189 return ret;
00190 }