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 <inttypes.h> |
6 #include <set> | 7 #include <set> |
7 #include <utility> | 8 #include <utility> |
| 9 #include "base/string_util.h" |
8 #include "update_engine/graph_utils.h" | 10 #include "update_engine/graph_utils.h" |
9 #include "update_engine/tarjan.h" | 11 #include "update_engine/tarjan.h" |
10 #include "update_engine/utils.h" | 12 #include "update_engine/utils.h" |
11 | 13 |
12 using std::make_pair; | 14 using std::make_pair; |
13 using std::set; | 15 using std::set; |
14 using std::vector; | 16 using std::vector; |
15 | 17 |
16 namespace chromeos_update_engine { | 18 namespace chromeos_update_engine { |
17 | 19 |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
58 if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt)) | 60 if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt)) |
59 subgraph_[*it].subgraph_edges.insert(*jt); | 61 subgraph_[*it].subgraph_edges.insert(*jt); |
60 } | 62 } |
61 } | 63 } |
62 | 64 |
63 current_vertex_ = i; | 65 current_vertex_ = i; |
64 blocked_.clear(); | 66 blocked_.clear(); |
65 blocked_.resize(subgraph_.size()); | 67 blocked_.resize(subgraph_.size()); |
66 blocked_graph_.clear(); | 68 blocked_graph_.clear(); |
67 blocked_graph_.resize(subgraph_.size()); | 69 blocked_graph_.resize(subgraph_.size()); |
68 Circuit(current_vertex_); | 70 Circuit(current_vertex_, 0); |
69 } | 71 } |
70 | 72 |
71 out_cut_edges->swap(cut_edges_); | 73 out_cut_edges->swap(cut_edges_); |
72 DCHECK(stack_.empty()); | 74 DCHECK(stack_.empty()); |
73 } | 75 } |
74 | 76 |
| 77 static const size_t kMaxEdgesToConsider = 2; |
| 78 |
75 void CycleBreaker::HandleCircuit() { | 79 void CycleBreaker::HandleCircuit() { |
76 stack_.push_back(current_vertex_); | 80 stack_.push_back(current_vertex_); |
77 CHECK_GE(stack_.size(), 2); | 81 CHECK_GE(stack_.size(), 2); |
78 Edge min_edge = make_pair(stack_[0], stack_[1]); | 82 Edge min_edge = make_pair(stack_[0], stack_[1]); |
79 uint64_t min_edge_weight = kuint64max; | 83 uint64_t min_edge_weight = kuint64max; |
80 const int kMaxEdgesToConsider = 4; | 84 size_t edges_considered = 0; |
81 int edges_considered = 0; | |
82 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); | 85 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); |
83 it != (stack_.end() - 1); ++it) { | 86 it != (stack_.end() - 1); ++it) { |
84 Edge edge = make_pair(*it, *(it + 1)); | 87 Edge edge = make_pair(*it, *(it + 1)); |
85 if (cut_edges_.find(edge) != cut_edges_.end()) { | 88 if (cut_edges_.find(edge) != cut_edges_.end()) { |
86 stack_.pop_back(); | 89 stack_.pop_back(); |
87 return; | 90 return; |
88 } | 91 } |
89 uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); | 92 uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); |
90 if (edge_weight < min_edge_weight) { | 93 if (edge_weight < min_edge_weight) { |
91 min_edge_weight = edge_weight; | 94 min_edge_weight = edge_weight; |
(...skipping 23 matching lines...) Expand all Loading... |
115 for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(), | 118 for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(), |
116 e = stack_.end(); it != e; ++it) { | 119 e = stack_.end(); it != e; ++it) { |
117 Edge edge = make_pair(*(it - 1), *it); | 120 Edge edge = make_pair(*(it - 1), *it); |
118 if (utils::SetContainsKey(cut_edges_, edge)) { | 121 if (utils::SetContainsKey(cut_edges_, edge)) { |
119 return true; | 122 return true; |
120 } | 123 } |
121 } | 124 } |
122 return false; | 125 return false; |
123 } | 126 } |
124 | 127 |
125 bool CycleBreaker::Circuit(Vertex::Index vertex) { | 128 bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) { |
126 // "vertex" was "v" in the original paper. | 129 // "vertex" was "v" in the original paper. |
127 bool found = false; // Was "f" in the original paper. | 130 bool found = false; // Was "f" in the original paper. |
128 stack_.push_back(vertex); | 131 stack_.push_back(vertex); |
129 blocked_[vertex] = true; | 132 blocked_[vertex] = true; |
| 133 { |
| 134 static int counter = 0; |
| 135 counter++; |
| 136 if (counter == 10000) { |
| 137 counter = 0; |
| 138 std::string stack_str; |
| 139 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); |
| 140 it != stack_.end(); ++it) { |
| 141 stack_str += StringPrintf("%lu -> ", |
| 142 static_cast<long unsigned int>(*it)); |
| 143 } |
| 144 LOG(INFO) << "stack: " << stack_str; |
| 145 } |
| 146 } |
130 | 147 |
131 for (Vertex::SubgraphEdgeMap::iterator w = | 148 for (Vertex::SubgraphEdgeMap::iterator w = |
132 subgraph_[vertex].subgraph_edges.begin(); | 149 subgraph_[vertex].subgraph_edges.begin(); |
133 w != subgraph_[vertex].subgraph_edges.end(); ++w) { | 150 w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
134 if (*w == current_vertex_) { | 151 if (*w == current_vertex_) { |
135 // The original paper called for printing stack_ followed by | 152 // The original paper called for printing stack_ followed by |
136 // current_vertex_ here, which is a cycle. Instead, we call | 153 // current_vertex_ here, which is a cycle. Instead, we call |
137 // HandleCircuit() to break it. | 154 // HandleCircuit() to break it. |
138 HandleCircuit(); | 155 HandleCircuit(); |
139 found = true; | 156 found = true; |
140 } else if (!blocked_[*w]) { | 157 } else if (!blocked_[*w]) { |
141 if (Circuit(*w)) { | 158 if (Circuit(*w, depth + 1)) { |
142 found = true; | 159 found = true; |
143 if (StackContainsCutEdge()) | 160 if ((depth > kMaxEdgesToConsider) || StackContainsCutEdge()) |
144 break; | 161 break; |
145 } | 162 } |
146 } | 163 } |
147 } | 164 } |
148 | 165 |
149 if (found) { | 166 if (found) { |
150 Unblock(vertex); | 167 Unblock(vertex); |
151 } else { | 168 } else { |
152 for (Vertex::SubgraphEdgeMap::iterator w = | 169 for (Vertex::SubgraphEdgeMap::iterator w = |
153 subgraph_[vertex].subgraph_edges.begin(); | 170 subgraph_[vertex].subgraph_edges.begin(); |
154 w != subgraph_[vertex].subgraph_edges.end(); ++w) { | 171 w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
155 if (blocked_graph_[*w].out_edges.find(vertex) == | 172 if (blocked_graph_[*w].out_edges.find(vertex) == |
156 blocked_graph_[*w].out_edges.end()) { | 173 blocked_graph_[*w].out_edges.end()) { |
157 blocked_graph_[*w].out_edges.insert(make_pair(vertex, | 174 blocked_graph_[*w].out_edges.insert(make_pair(vertex, |
158 EdgeProperties())); | 175 EdgeProperties())); |
159 } | 176 } |
160 } | 177 } |
161 } | 178 } |
162 CHECK_EQ(vertex, stack_.back()); | 179 CHECK_EQ(vertex, stack_.back()); |
163 stack_.pop_back(); | 180 stack_.pop_back(); |
164 return found; | 181 return found; |
165 } | 182 } |
166 | 183 |
167 } // namespace chromeos_update_engine | 184 } // namespace chromeos_update_engine |
OLD | NEW |