OLD | NEW |
1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "update_engine/topological_sort.h" | 5 #include "update_engine/topological_sort.h" |
6 #include <set> | 6 #include <set> |
7 #include <vector> | 7 #include <vector> |
| 8 #include "base/logging.h" |
8 | 9 |
9 using std::set; | 10 using std::set; |
10 using std::vector; | 11 using std::vector; |
11 | 12 |
12 namespace chromeos_update_engine { | 13 namespace chromeos_update_engine { |
13 | 14 |
14 namespace { | 15 namespace { |
15 void TopologicalSortVisit(const Graph& graph, | 16 void TopologicalSortVisit(const Graph& graph, |
16 set<Vertex::Index>* visited_nodes, | 17 set<Vertex::Index>* visited_nodes, |
17 vector<Vertex::Index>* nodes, | 18 vector<Vertex::Index>* nodes, |
18 Vertex::Index node) { | 19 Vertex::Index node) { |
19 if (visited_nodes->find(node) != visited_nodes->end()) | 20 if (visited_nodes->find(node) != visited_nodes->end()) |
20 return; | 21 return; |
21 | 22 |
22 visited_nodes->insert(node); | 23 visited_nodes->insert(node); |
23 // Visit all children. | 24 // Visit all children. |
24 for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); | 25 for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); |
25 it != graph[node].out_edges.end(); ++it) { | 26 it != graph[node].out_edges.end(); ++it) { |
26 TopologicalSortVisit(graph, visited_nodes, nodes, it->first); | 27 TopologicalSortVisit(graph, visited_nodes, nodes, it->first); |
27 } | 28 } |
28 // Visit this node. | 29 // Visit this node. |
| 30 LOG(INFO) << graph[node].file_name << " " << graph[node].op.type() << " " |
| 31 << graph[node].op.data_length(); |
29 nodes->push_back(node); | 32 nodes->push_back(node); |
30 } | 33 } |
31 } // namespace {} | 34 } // namespace {} |
32 | 35 |
33 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { | 36 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { |
34 set<Vertex::Index> visited_nodes; | 37 set<Vertex::Index> visited_nodes; |
35 | 38 |
36 for (Vertex::Index i = 0; i < graph.size(); i++) { | 39 for (Vertex::Index i = 0; i < graph.size(); i++) { |
37 TopologicalSortVisit(graph, &visited_nodes, out, i); | 40 TopologicalSortVisit(graph, &visited_nodes, out, i); |
38 } | 41 } |
39 } | 42 } |
40 | 43 |
41 } // namespace chromeos_update_engine | 44 } // namespace chromeos_update_engine |
OLD | NEW |