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 <inttypes.h> |
7 #include <set> | 7 #include <set> |
8 #include <utility> | 8 #include <utility> |
9 #include "base/string_util.h" | 9 #include "base/string_util.h" |
10 #include "update_engine/graph_utils.h" | 10 #include "update_engine/graph_utils.h" |
(...skipping 16 matching lines...) Expand all Loading... |
27 subgraph_ = graph; | 27 subgraph_ = graph; |
28 | 28 |
29 // The paper calls for the "adjacency structure (i.e., graph) of | 29 // The paper calls for the "adjacency structure (i.e., graph) of |
30 // strong (-ly connected) component K with least vertex in subgraph | 30 // strong (-ly connected) component K with least vertex in subgraph |
31 // induced by {s, s + 1, ..., n}". | 31 // induced by {s, s + 1, ..., n}". |
32 // We arbitrarily order each vertex by its index in the graph. Thus, | 32 // We arbitrarily order each vertex by its index in the graph. Thus, |
33 // each iteration, we are looking at the subgraph {s, s + 1, ..., n} | 33 // each iteration, we are looking at the subgraph {s, s + 1, ..., n} |
34 // and looking for the strongly connected component with vertex s. | 34 // and looking for the strongly connected component with vertex s. |
35 | 35 |
36 TarjanAlgorithm tarjan; | 36 TarjanAlgorithm tarjan; |
| 37 skipped_ops_ = 0; |
37 | 38 |
38 for (Graph::size_type i = 0; i < subgraph_.size(); i++) { | 39 for (Graph::size_type i = 0; i < subgraph_.size(); i++) { |
| 40 DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type(); |
| 41 if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE || |
| 42 op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) { |
| 43 skipped_ops_++; |
| 44 continue; |
| 45 } |
| 46 |
39 if (i > 0) { | 47 if (i > 0) { |
40 // Erase node (i - 1) from subgraph_. First, erase what it points to | 48 // Erase node (i - 1) from subgraph_. First, erase what it points to |
41 subgraph_[i - 1].out_edges.clear(); | 49 subgraph_[i - 1].out_edges.clear(); |
42 // Now, erase any pointers to node (i - 1) | 50 // Now, erase any pointers to node (i - 1) |
43 for (Graph::size_type j = i; j < subgraph_.size(); j++) { | 51 for (Graph::size_type j = i; j < subgraph_.size(); j++) { |
44 subgraph_[j].out_edges.erase(i - 1); | 52 subgraph_[j].out_edges.erase(i - 1); |
45 } | 53 } |
46 } | 54 } |
47 | 55 |
48 // Calculate SCC (strongly connected component) with vertex i. | 56 // Calculate SCC (strongly connected component) with vertex i. |
(...skipping 15 matching lines...) Expand all Loading... |
64 | 72 |
65 current_vertex_ = i; | 73 current_vertex_ = i; |
66 blocked_.clear(); | 74 blocked_.clear(); |
67 blocked_.resize(subgraph_.size()); | 75 blocked_.resize(subgraph_.size()); |
68 blocked_graph_.clear(); | 76 blocked_graph_.clear(); |
69 blocked_graph_.resize(subgraph_.size()); | 77 blocked_graph_.resize(subgraph_.size()); |
70 Circuit(current_vertex_, 0); | 78 Circuit(current_vertex_, 0); |
71 } | 79 } |
72 | 80 |
73 out_cut_edges->swap(cut_edges_); | 81 out_cut_edges->swap(cut_edges_); |
| 82 LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops."; |
74 DCHECK(stack_.empty()); | 83 DCHECK(stack_.empty()); |
75 } | 84 } |
76 | 85 |
77 static const size_t kMaxEdgesToConsider = 2; | 86 static const size_t kMaxEdgesToConsider = 2; |
78 | 87 |
79 void CycleBreaker::HandleCircuit() { | 88 void CycleBreaker::HandleCircuit() { |
80 stack_.push_back(current_vertex_); | 89 stack_.push_back(current_vertex_); |
81 CHECK_GE(stack_.size(), 2); | 90 CHECK_GE(stack_.size(), 2); |
82 Edge min_edge = make_pair(stack_[0], stack_[1]); | 91 Edge min_edge = make_pair(stack_[0], stack_[1]); |
83 uint64_t min_edge_weight = kuint64max; | 92 uint64_t min_edge_weight = kuint64max; |
(...skipping 25 matching lines...) Expand all Loading... |
109 it != blocked_graph_[u].out_edges.end(); ) { | 118 it != blocked_graph_[u].out_edges.end(); ) { |
110 Vertex::Index w = it->first; | 119 Vertex::Index w = it->first; |
111 blocked_graph_[u].out_edges.erase(it++); | 120 blocked_graph_[u].out_edges.erase(it++); |
112 if (blocked_[w]) | 121 if (blocked_[w]) |
113 Unblock(w); | 122 Unblock(w); |
114 } | 123 } |
115 } | 124 } |
116 | 125 |
117 bool CycleBreaker::StackContainsCutEdge() const { | 126 bool CycleBreaker::StackContainsCutEdge() const { |
118 for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(), | 127 for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(), |
119 e = stack_.end(); it != e; ++it) { | 128 e = stack_.end(); it != e; ++it) { |
120 Edge edge = make_pair(*(it - 1), *it); | 129 Edge edge = make_pair(*(it - 1), *it); |
121 if (utils::SetContainsKey(cut_edges_, edge)) { | 130 if (utils::SetContainsKey(cut_edges_, edge)) { |
122 return true; | 131 return true; |
123 } | 132 } |
124 } | 133 } |
125 return false; | 134 return false; |
126 } | 135 } |
127 | 136 |
128 bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) { | 137 bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) { |
129 // "vertex" was "v" in the original paper. | 138 // "vertex" was "v" in the original paper. |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
175 EdgeProperties())); | 184 EdgeProperties())); |
176 } | 185 } |
177 } | 186 } |
178 } | 187 } |
179 CHECK_EQ(vertex, stack_.back()); | 188 CHECK_EQ(vertex, stack_.back()); |
180 stack_.pop_back(); | 189 stack_.pop_back(); |
181 return found; | 190 return found; |
182 } | 191 } |
183 | 192 |
184 } // namespace chromeos_update_engine | 193 } // namespace chromeos_update_engine |
OLD | NEW |