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 <set> | 5 #include <set> |
6 #include <string> | 6 #include <string> |
7 #include <utility> | 7 #include <utility> |
8 #include <vector> | 8 #include <vector> |
9 #include <gtest/gtest.h> | 9 #include <gtest/gtest.h> |
10 #include "chromeos/obsolete_logging.h" | 10 #include "chromeos/obsolete_logging.h" |
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
73 namespace { | 73 namespace { |
74 pair<Vertex::Index, EdgeProperties> EdgeWithWeight(Vertex::Index dest, | 74 pair<Vertex::Index, EdgeProperties> EdgeWithWeight(Vertex::Index dest, |
75 uint64_t weight) { | 75 uint64_t weight) { |
76 EdgeProperties props; | 76 EdgeProperties props; |
77 props.extents.resize(1); | 77 props.extents.resize(1); |
78 props.extents[0].set_num_blocks(weight); | 78 props.extents[0].set_num_blocks(weight); |
79 return make_pair(dest, props); | 79 return make_pair(dest, props); |
80 } | 80 } |
81 } // namespace {} | 81 } // namespace {} |
82 | 82 |
| 83 |
| 84 // This creates a bunch of cycles like this: |
| 85 // |
| 86 // root <------. |
| 87 // (t)-> / | \ | |
| 88 // V V V | |
| 89 // N N N | |
| 90 // \ | / | |
| 91 // VVV | |
| 92 // N | |
| 93 // / | \ | |
| 94 // V V V | |
| 95 // N N N | |
| 96 // ... | |
| 97 // (s)-> \ | / | |
| 98 // VVV | |
| 99 // N | |
| 100 // \_________/ |
| 101 // |
| 102 // such that the original cutting algo would cut edges (s). We changed |
| 103 // the algorithm to cut cycles (t) instead, since they are closer to the |
| 104 // root, and that can massively speed up cycle cutting. |
| 105 TEST(CycleBreakerTest, AggressiveCutTest) { |
| 106 int counter = 0; |
| 107 |
| 108 const int kNodesPerGroup = 4; |
| 109 const int kGroups = 33; |
| 110 |
| 111 Graph graph(kGroups * kNodesPerGroup + 1); // + 1 for the root node |
| 112 |
| 113 const Vertex::Index n_root = counter++; |
| 114 |
| 115 Vertex::Index last_hub = n_root; |
| 116 for (int i = 0; i < kGroups; i++) { |
| 117 uint64_t weight = 5; |
| 118 if (i == 0) |
| 119 weight = 2; |
| 120 else if (i == (kGroups - 1)) |
| 121 weight = 1; |
| 122 |
| 123 const Vertex::Index next_hub = counter++; |
| 124 |
| 125 for (int j = 0; j < (kNodesPerGroup - 1); j++) { |
| 126 const Vertex::Index node = counter++; |
| 127 graph[last_hub].out_edges.insert(EdgeWithWeight(node, weight)); |
| 128 graph[node].out_edges.insert(EdgeWithWeight(next_hub, weight)); |
| 129 } |
| 130 last_hub = next_hub; |
| 131 } |
| 132 |
| 133 graph[last_hub].out_edges.insert(EdgeWithWeight(n_root, 5)); |
| 134 |
| 135 |
| 136 EXPECT_EQ(counter, graph.size()); |
| 137 |
| 138 CycleBreaker breaker; |
| 139 |
| 140 set<Edge> broken_edges; |
| 141 LOG(INFO) << "If this hangs for more than 1 second, the test has failed."; |
| 142 breaker.BreakCycles(graph, &broken_edges); |
| 143 |
| 144 set<Edge> expected_cuts; |
| 145 |
| 146 for (Vertex::EdgeMap::const_iterator it = graph[n_root].out_edges.begin(), |
| 147 e = graph[n_root].out_edges.end(); it != e; ++it) { |
| 148 expected_cuts.insert(make_pair(n_root, it->first)); |
| 149 } |
| 150 |
| 151 EXPECT_TRUE(broken_edges == expected_cuts); |
| 152 } |
| 153 |
83 TEST(CycleBreakerTest, WeightTest) { | 154 TEST(CycleBreakerTest, WeightTest) { |
84 int counter = 0; | 155 int counter = 0; |
85 const Vertex::Index n_a = counter++; | 156 const Vertex::Index n_a = counter++; |
86 const Vertex::Index n_b = counter++; | 157 const Vertex::Index n_b = counter++; |
87 const Vertex::Index n_c = counter++; | 158 const Vertex::Index n_c = counter++; |
88 const Vertex::Index n_d = counter++; | 159 const Vertex::Index n_d = counter++; |
89 const Vertex::Index n_e = counter++; | 160 const Vertex::Index n_e = counter++; |
90 const Vertex::Index n_f = counter++; | 161 const Vertex::Index n_f = counter++; |
91 const Vertex::Index n_g = counter++; | 162 const Vertex::Index n_g = counter++; |
92 const Vertex::Index n_h = counter++; | 163 const Vertex::Index n_h = counter++; |
(...skipping 29 matching lines...) Expand all Loading... |
122 | 193 |
123 // These are required to be broken: | 194 // These are required to be broken: |
124 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a))); | 195 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a))); |
125 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c))); | 196 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c))); |
126 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e))); | 197 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e))); |
127 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g))); | 198 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g))); |
128 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i))); | 199 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i))); |
129 } | 200 } |
130 | 201 |
131 } // namespace chromeos_update_engine | 202 } // namespace chromeos_update_engine |
OLD | NEW |