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 |