| 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/cycle_breaker.h" | 5 #include "update_engine/cycle_breaker.h" |
| 6 #include <set> | 6 #include <set> |
| 7 #include <utility> | 7 #include <utility> |
| 8 #include "update_engine/graph_utils.h" | 8 #include "update_engine/graph_utils.h" |
| 9 #include "update_engine/tarjan.h" | 9 #include "update_engine/tarjan.h" |
| 10 #include "update_engine/utils.h" | 10 #include "update_engine/utils.h" |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 69 } | 69 } |
| 70 | 70 |
| 71 out_cut_edges->swap(cut_edges_); | 71 out_cut_edges->swap(cut_edges_); |
| 72 DCHECK(stack_.empty()); | 72 DCHECK(stack_.empty()); |
| 73 } | 73 } |
| 74 | 74 |
| 75 void CycleBreaker::HandleCircuit() { | 75 void CycleBreaker::HandleCircuit() { |
| 76 stack_.push_back(current_vertex_); | 76 stack_.push_back(current_vertex_); |
| 77 CHECK_GE(stack_.size(), 2); | 77 CHECK_GE(stack_.size(), 2); |
| 78 Edge min_edge = make_pair(stack_[0], stack_[1]); | 78 Edge min_edge = make_pair(stack_[0], stack_[1]); |
| 79 uint64 min_edge_weight = kuint64max; | 79 uint64_t min_edge_weight = kuint64max; |
| 80 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); | 80 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); |
| 81 it != (stack_.end() - 1); ++it) { | 81 it != (stack_.end() - 1); ++it) { |
| 82 Edge edge = make_pair(*it, *(it + 1)); | 82 Edge edge = make_pair(*it, *(it + 1)); |
| 83 if (cut_edges_.find(edge) != cut_edges_.end()) { | 83 if (cut_edges_.find(edge) != cut_edges_.end()) { |
| 84 stack_.pop_back(); | 84 stack_.pop_back(); |
| 85 return; | 85 return; |
| 86 } | 86 } |
| 87 uint64 edge_weight = graph_utils::EdgeWeight(subgraph_, edge); | 87 uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); |
| 88 if (edge_weight < min_edge_weight) { | 88 if (edge_weight < min_edge_weight) { |
| 89 min_edge_weight = edge_weight; | 89 min_edge_weight = edge_weight; |
| 90 min_edge = edge; | 90 min_edge = edge; |
| 91 } | 91 } |
| 92 } | 92 } |
| 93 cut_edges_.insert(min_edge); | 93 cut_edges_.insert(min_edge); |
| 94 stack_.pop_back(); | 94 stack_.pop_back(); |
| 95 } | 95 } |
| 96 | 96 |
| 97 void CycleBreaker::Unblock(Vertex::Index u) { | 97 void CycleBreaker::Unblock(Vertex::Index u) { |
| (...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 135 w != subgraph_[vertex].subgraph_edges.end(); ++w) { | 135 w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
| 136 subgraph_[*w].subgraph_edges.insert(vertex); | 136 subgraph_[*w].subgraph_edges.insert(vertex); |
| 137 } | 137 } |
| 138 } | 138 } |
| 139 CHECK_EQ(vertex, stack_.back()); | 139 CHECK_EQ(vertex, stack_.back()); |
| 140 stack_.pop_back(); | 140 stack_.pop_back(); |
| 141 return found; | 141 return found; |
| 142 } | 142 } |
| 143 | 143 |
| 144 } // namespace chromeos_update_engine | 144 } // namespace chromeos_update_engine |
| OLD | NEW |