OLD | NEW |
---|---|
(Empty) | |
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 | |
3 // found in the LICENSE file. | |
4 | |
5 #include <set> | |
6 #include <string> | |
7 #include <utility> | |
8 #include <vector> | |
9 #include <gtest/gtest.h> | |
10 #include "chromeos/obsolete_logging.h" | |
11 #include "update_engine/cycle_breaker.h" | |
12 #include "update_engine/graph_types.h" | |
13 #include "update_engine/utils.h" | |
14 | |
15 using std::make_pair; | |
16 using std::pair; | |
17 using std::set; | |
18 using std::string; | |
19 using std::vector; | |
20 | |
21 namespace chromeos_update_engine { | |
22 | |
23 class CycleBreakerTest : public ::testing::Test {}; | |
24 | |
25 TEST(CycleBreakerTest, SimpleTest) { | |
26 int counter = 0; | |
27 const Vertex::Index n_a = counter++; | |
28 const Vertex::Index n_b = counter++; | |
29 const Vertex::Index n_c = counter++; | |
30 const Vertex::Index n_d = counter++; | |
31 const Vertex::Index n_e = counter++; | |
32 const Vertex::Index n_f = counter++; | |
33 const Vertex::Index n_g = counter++; | |
34 const Vertex::Index n_h = counter++; | |
35 const Graph::size_type kNodeCount = counter++; | |
36 | |
37 Graph graph(kNodeCount); | |
38 | |
39 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties())); | |
40 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties())); | |
41 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); | |
42 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties())); | |
43 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties())); | |
44 graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties())); | |
45 graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties())); | |
46 graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties())); | |
47 graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties())); | |
48 graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties())); | |
49 graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties())); | |
50 graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties())); | |
51 | |
52 CycleBreaker breaker; | |
53 | |
54 set<Edge> broken_edges; | |
55 breaker.BreakCycles(graph, &broken_edges); | |
56 | |
57 // The following cycles must be cut: | |
58 // A->E->B | |
59 // C->D->E | |
60 // G->H | |
61 | |
62 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_e)) || | |
63 utils::SetContainsKey(broken_edges, make_pair(n_e, n_b)) || | |
64 utils::SetContainsKey(broken_edges, make_pair(n_b, n_a))); | |
65 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_c, n_d)) || | |
66 utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)) || | |
67 utils::SetContainsKey(broken_edges, make_pair(n_e, n_c))); | |
68 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_g, n_h)) || | |
69 utils::SetContainsKey(broken_edges, make_pair(n_h, n_g))); | |
Daniel Erat
2010/03/10 22:50:01
also check that there are exactly three edges in t
adlr
2010/03/11 00:41:42
Done.
| |
70 } | |
71 | |
72 namespace { | |
73 pair<Vertex::Index, EdgeProperties> EdgeWithWeight(Vertex::Index dest, | |
74 uint64 weight) { | |
75 EdgeProperties props; | |
76 props.extents.resize(1); | |
77 props.extents[0].set_num_blocks(weight); | |
78 return make_pair(dest, props); | |
79 } | |
80 } // namespace {} | |
81 | |
82 TEST(CycleBreakerTest, WeightTest) { | |
83 int counter = 0; | |
84 const Vertex::Index n_a = counter++; | |
85 const Vertex::Index n_b = counter++; | |
86 const Vertex::Index n_c = counter++; | |
87 const Vertex::Index n_d = counter++; | |
88 const Vertex::Index n_e = counter++; | |
89 const Vertex::Index n_f = counter++; | |
90 const Vertex::Index n_g = counter++; | |
91 const Vertex::Index n_h = counter++; | |
92 const Vertex::Index n_i = counter++; | |
93 const Vertex::Index n_j = counter++; | |
94 const Graph::size_type kNodeCount = counter++; | |
95 | |
96 Graph graph(kNodeCount); | |
97 | |
98 graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 4)); | |
99 graph[n_a].out_edges.insert(EdgeWithWeight(n_f, 3)); | |
100 graph[n_a].out_edges.insert(EdgeWithWeight(n_h, 2)); | |
101 graph[n_b].out_edges.insert(EdgeWithWeight(n_a, 3)); | |
102 graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 4)); | |
103 graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 5)); | |
104 graph[n_c].out_edges.insert(EdgeWithWeight(n_d, 3)); | |
105 graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 6)); | |
106 graph[n_d].out_edges.insert(EdgeWithWeight(n_e, 3)); | |
107 graph[n_e].out_edges.insert(EdgeWithWeight(n_d, 4)); | |
108 graph[n_e].out_edges.insert(EdgeWithWeight(n_g, 5)); | |
109 graph[n_f].out_edges.insert(EdgeWithWeight(n_g, 2)); | |
110 graph[n_g].out_edges.insert(EdgeWithWeight(n_f, 3)); | |
111 graph[n_g].out_edges.insert(EdgeWithWeight(n_d, 5)); | |
112 graph[n_h].out_edges.insert(EdgeWithWeight(n_i, 8)); | |
113 graph[n_i].out_edges.insert(EdgeWithWeight(n_e, 4)); | |
114 graph[n_i].out_edges.insert(EdgeWithWeight(n_h, 9)); | |
115 graph[n_i].out_edges.insert(EdgeWithWeight(n_j, 6)); | |
116 | |
117 CycleBreaker breaker; | |
118 | |
119 set<Edge> broken_edges; | |
120 breaker.BreakCycles(graph, &broken_edges); | |
121 | |
122 // These are required to be broken: | |
123 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a))); | |
124 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c))); | |
125 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e))); | |
126 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g))); | |
127 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i))); | |
128 } | |
129 | |
130 } // namespace chromeos_update_engine | |
OLD | NEW |