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