| 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 |