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 #include "base/logging.h" |
9 | 9 |
10 using std::set; | 10 using std::set; |
11 using std::vector; | 11 using std::vector; |
12 | 12 |
13 namespace chromeos_update_engine { | 13 namespace chromeos_update_engine { |
14 | 14 |
15 namespace { | 15 namespace { |
16 void TopologicalSortVisit(const Graph& graph, | 16 void TopologicalSortVisit(const Graph& graph, |
17 set<Vertex::Index>* visited_nodes, | 17 set<Vertex::Index>* visited_nodes, |
18 vector<Vertex::Index>* nodes, | 18 vector<Vertex::Index>* nodes, |
19 Vertex::Index node) { | 19 Vertex::Index node) { |
20 if (visited_nodes->find(node) != visited_nodes->end()) | 20 if (visited_nodes->find(node) != visited_nodes->end()) |
21 return; | 21 return; |
22 | 22 |
23 visited_nodes->insert(node); | 23 visited_nodes->insert(node); |
24 // Visit all children. | 24 // Visit all children. |
25 for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); | 25 for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); |
26 it != graph[node].out_edges.end(); ++it) { | 26 it != graph[node].out_edges.end(); ++it) { |
27 TopologicalSortVisit(graph, visited_nodes, nodes, it->first); | 27 TopologicalSortVisit(graph, visited_nodes, nodes, it->first); |
28 } | 28 } |
29 // Visit this node. | 29 // Visit this node. |
30 LOG(INFO) << graph[node].file_name << " " << graph[node].op.type() << " " | |
31 << graph[node].op.data_length(); | |
32 nodes->push_back(node); | 30 nodes->push_back(node); |
33 } | 31 } |
34 } // namespace {} | 32 } // namespace {} |
35 | 33 |
36 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { | 34 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { |
37 set<Vertex::Index> visited_nodes; | 35 set<Vertex::Index> visited_nodes; |
38 | 36 |
39 for (Vertex::Index i = 0; i < graph.size(); i++) { | 37 for (Vertex::Index i = 0; i < graph.size(); i++) { |
40 TopologicalSortVisit(graph, &visited_nodes, out, i); | 38 TopologicalSortVisit(graph, &visited_nodes, out, i); |
41 } | 39 } |
42 } | 40 } |
43 | 41 |
44 } // namespace chromeos_update_engine | 42 } // namespace chromeos_update_engine |
OLD | NEW |