using namespace std;
using namespace boost;
-enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp,
- foo_o, bar_cpp, bar_o, libfoobar_a,
- zig_cpp, zig_o, zag_cpp, zag_o,
- libzigzag_a, killerapp, N };
-const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",
- "foo.o", "bar.cpp", "bar.o", "libfoobar.a",
- "zig.cpp", "zig.o", "zag.cpp", "zag.o",
- "libzigzag.a", "killerapp" };
-
-
-struct print_visitor : public bfs_visitor<> {
- template <class Vertex, class Graph>
- void discover_vertex(Vertex v, Graph&) {
- cout << name[v] << " ";
- }
+enum files_e
+{
+ dax_h,
+ yow_h,
+ boz_h,
+ zow_h,
+ foo_cpp,
+ foo_o,
+ bar_cpp,
+ bar_o,
+ libfoobar_a,
+ zig_cpp,
+ zig_o,
+ zag_cpp,
+ zag_o,
+ libzigzag_a,
+ killerapp,
+ N
};
+const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp", "foo.o",
+ "bar.cpp", "bar.o", "libfoobar.a", "zig.cpp", "zig.o", "zag.cpp", "zag.o",
+ "libzigzag.a", "killerapp" };
+struct print_visitor : public bfs_visitor<>
+{
+ template < class Vertex, class Graph >
+ void discover_vertex(Vertex v, Graph&)
+ {
+ cout << name[v] << " ";
+ }
+};
struct cycle_detector : public dfs_visitor<>
{
- cycle_detector(bool& has_cycle)
- : m_has_cycle(has_cycle) { }
+ cycle_detector(bool& has_cycle) : m_has_cycle(has_cycle) {}
+
+ template < class Edge, class Graph > void back_edge(Edge, Graph&)
+ {
+ m_has_cycle = true;
+ }
- template <class Edge, class Graph>
- void back_edge(Edge, Graph&) { m_has_cycle = true; }
protected:
- bool& m_has_cycle;
+ bool& m_has_cycle;
};
-
-
-
-int main(int,char*[])
+int main(int, char*[])
{
- typedef pair<int,int> Edge;
- Edge used_by[] = {
- Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h),
- Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
- Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
- Edge(zow_h, foo_cpp),
- Edge(foo_cpp, foo_o),
- Edge(foo_o, libfoobar_a),
- Edge(bar_cpp, bar_o),
- Edge(bar_o, libfoobar_a),
- Edge(libfoobar_a, libzigzag_a),
- Edge(zig_cpp, zig_o),
- Edge(zig_o, libzigzag_a),
- Edge(zag_cpp, zag_o),
- Edge(zag_o, libzigzag_a),
- Edge(libzigzag_a, killerapp)
- };
- const std::size_t nedges = sizeof(used_by)/sizeof(Edge);
-
- typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
+ typedef pair< int, int > Edge;
+ Edge used_by[] = { Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp),
+ Edge(dax_h, yow_h), Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
+ Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
+ Edge(zow_h, foo_cpp), Edge(foo_cpp, foo_o), Edge(foo_o, libfoobar_a),
+ Edge(bar_cpp, bar_o), Edge(bar_o, libfoobar_a),
+ Edge(libfoobar_a, libzigzag_a), Edge(zig_cpp, zig_o),
+ Edge(zig_o, libzigzag_a), Edge(zag_cpp, zag_o),
+ Edge(zag_o, libzigzag_a), Edge(libzigzag_a, killerapp) };
+ const std::size_t nedges = sizeof(used_by) / sizeof(Edge);
+
+ typedef adjacency_list< vecS, vecS, bidirectionalS > Graph;
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- // VC++ can't handle the iterator constructor
- Graph g(N);
- for (std::size_t j = 0; j < nedges; ++j) {
- graph_traits<Graph>::edge_descriptor e; bool inserted;
- boost::tie(e, inserted) = add_edge(used_by[j].first, used_by[j].second, g);
- }
+ // VC++ can't handle the iterator constructor
+ Graph g(N);
+ for (std::size_t j = 0; j < nedges; ++j)
+ {
+ graph_traits< Graph >::edge_descriptor e;
+ bool inserted;
+ boost::tie(e, inserted)
+ = add_edge(used_by[j].first, used_by[j].second, g);
+ }
#else
- Graph g(used_by, used_by + nedges, N);
+ Graph g(used_by, used_by + nedges, N);
#endif
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
-
- // Determine ordering for a full recompilation
- // and the order with files that can be compiled in parallel
- {
- typedef list<Vertex> MakeOrder;
- MakeOrder::iterator i;
- MakeOrder make_order;
-
- topological_sort(g, std::front_inserter(make_order));
- cout << "make ordering: ";
- for (i = make_order.begin();
- i != make_order.end(); ++i)
- cout << name[*i] << " ";
-
- cout << endl << endl;
-
- // Parallel compilation ordering
- std::vector<int> time(N, 0);
- for (i = make_order.begin(); i != make_order.end(); ++i) {
- // Walk through the in_edges an calculate the maximum time.
- if (in_degree (*i, g) > 0) {
- Graph::in_edge_iterator j, j_end;
- int maxdist=0;
- // Through the order from topological sort, we are sure that every
- // time we are using here is already initialized.
- for (boost::tie(j, j_end) = in_edges(*i, g); j != j_end; ++j)
- maxdist=(std::max)(time[source(*j, g)], maxdist);
- time[*i]=maxdist+1;
- }
+ typedef graph_traits< Graph >::vertex_descriptor Vertex;
+
+ // Determine ordering for a full recompilation
+ // and the order with files that can be compiled in parallel
+ {
+ typedef list< Vertex > MakeOrder;
+ MakeOrder::iterator i;
+ MakeOrder make_order;
+
+ topological_sort(g, std::front_inserter(make_order));
+ cout << "make ordering: ";
+ for (i = make_order.begin(); i != make_order.end(); ++i)
+ cout << name[*i] << " ";
+
+ cout << endl << endl;
+
+ // Parallel compilation ordering
+ std::vector< int > time(N, 0);
+ for (i = make_order.begin(); i != make_order.end(); ++i)
+ {
+ // Walk through the in_edges an calculate the maximum time.
+ if (in_degree(*i, g) > 0)
+ {
+ Graph::in_edge_iterator j, j_end;
+ int maxdist = 0;
+ // Through the order from topological sort, we are sure that
+ // every time we are using here is already initialized.
+ for (boost::tie(j, j_end) = in_edges(*i, g); j != j_end; ++j)
+ maxdist = (std::max)(time[source(*j, g)], maxdist);
+ time[*i] = maxdist + 1;
+ }
+ }
+
+ cout << "parallel make ordering, " << endl
+ << "vertices with same group number can be made in parallel"
+ << endl;
+ {
+ graph_traits< Graph >::vertex_iterator i, iend;
+ for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
+ cout << "time_slot[" << name[*i] << "] = " << time[*i] << endl;
+ }
}
+ cout << endl;
- cout << "parallel make ordering, " << endl
- << "vertices with same group number can be made in parallel" << endl;
+ // if I change yow.h what files need to be re-made?
{
- graph_traits<Graph>::vertex_iterator i, iend;
- for (boost::tie(i,iend) = vertices(g); i != iend; ++i)
- cout << "time_slot[" << name[*i] << "] = " << time[*i] << endl;
+ cout << "A change to yow.h will cause what to be re-made?" << endl;
+ print_visitor vis;
+ breadth_first_search(g, vertex(yow_h, g), visitor(vis));
+ cout << endl;
}
+ cout << endl;
- }
- cout << endl;
+ // are there any cycles in the graph?
+ {
+ bool has_cycle = false;
+ cycle_detector vis(has_cycle);
+ depth_first_search(g, visitor(vis));
+ cout << "The graph has a cycle? " << has_cycle << endl;
+ }
+ cout << endl;
- // if I change yow.h what files need to be re-made?
- {
- cout << "A change to yow.h will cause what to be re-made?" << endl;
- print_visitor vis;
- breadth_first_search(g, vertex(yow_h, g), visitor(vis));
+ // add a dependency going from bar.cpp to dax.h
+ {
+ cout << "adding edge bar_cpp -> dax_h" << endl;
+ add_edge(bar_cpp, dax_h, g);
+ }
cout << endl;
- }
- cout << endl;
-
- // are there any cycles in the graph?
- {
- bool has_cycle = false;
- cycle_detector vis(has_cycle);
- depth_first_search(g, visitor(vis));
- cout << "The graph has a cycle? " << has_cycle << endl;
- }
- cout << endl;
-
- // add a dependency going from bar.cpp to dax.h
- {
- cout << "adding edge bar_cpp -> dax_h" << endl;
- add_edge(bar_cpp, dax_h, g);
- }
- cout << endl;
-
- // are there any cycles in the graph?
- {
- bool has_cycle = false;
- cycle_detector vis(has_cycle);
- depth_first_search(g, visitor(vis));
- cout << "The graph has a cycle now? " << has_cycle << endl;
- }
-
- return 0;
+
+ // are there any cycles in the graph?
+ {
+ bool has_cycle = false;
+ cycle_detector vis(has_cycle);
+ depth_first_search(g, visitor(vis));
+ cout << "The graph has a cycle now? " << has_cycle << endl;
+ }
+
+ return 0;
}
projects / ceph.git / blobdiff