Alex Deymo | aea4c1c | 2015-08-19 20:24:43 -0700 | [diff] [blame] | 1 | // |
| 2 | // Copyright (C) 2010 The Android Open Source Project |
| 3 | // |
| 4 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | // you may not use this file except in compliance with the License. |
| 6 | // You may obtain a copy of the License at |
| 7 | // |
| 8 | // http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | // |
| 10 | // Unless required by applicable law or agreed to in writing, software |
| 11 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | // See the License for the specific language governing permissions and |
| 14 | // limitations under the License. |
| 15 | // |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 16 | |
Alex Deymo | aab50e3 | 2014-11-10 19:55:35 -0800 | [diff] [blame] | 17 | #include "update_engine/payload_generator/topological_sort.h" |
| 18 | |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 19 | #include <utility> |
| 20 | #include <vector> |
Alex Deymo | 161c4a1 | 2014-05-16 15:56:21 -0700 | [diff] [blame] | 21 | |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 22 | #include <gtest/gtest.h> |
Alex Deymo | 161c4a1 | 2014-05-16 15:56:21 -0700 | [diff] [blame] | 23 | |
| 24 | #include "update_engine/payload_generator/graph_types.h" |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 25 | |
| 26 | using std::make_pair; |
| 27 | using std::vector; |
| 28 | |
| 29 | namespace chromeos_update_engine { |
| 30 | |
| 31 | class TopologicalSortTest : public ::testing::Test {}; |
| 32 | |
| 33 | namespace { |
| 34 | // Returns true if the value is found in vect. If found, the index is stored |
| 35 | // in out_index if out_index is not null. |
| 36 | template<typename T> |
| 37 | bool IndexOf(const vector<T>& vect, |
| 38 | const T& value, |
| 39 | typename vector<T>::size_type* out_index) { |
| 40 | for (typename vector<T>::size_type i = 0; i < vect.size(); i++) { |
| 41 | if (vect[i] == value) { |
| 42 | if (out_index) { |
| 43 | *out_index = i; |
| 44 | } |
| 45 | return true; |
| 46 | } |
| 47 | } |
| 48 | return false; |
| 49 | } |
Alex Vakulenko | d2779df | 2014-06-16 13:19:00 -0700 | [diff] [blame] | 50 | } // namespace |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 51 | |
| 52 | TEST(TopologicalSortTest, SimpleTest) { |
| 53 | int counter = 0; |
| 54 | const Vertex::Index n_a = counter++; |
| 55 | const Vertex::Index n_b = counter++; |
| 56 | const Vertex::Index n_c = counter++; |
| 57 | const Vertex::Index n_d = counter++; |
| 58 | const Vertex::Index n_e = counter++; |
| 59 | const Vertex::Index n_f = counter++; |
| 60 | const Vertex::Index n_g = counter++; |
| 61 | const Vertex::Index n_h = counter++; |
| 62 | const Vertex::Index n_i = counter++; |
| 63 | const Vertex::Index n_j = counter++; |
| 64 | const Graph::size_type kNodeCount = counter++; |
| 65 | |
| 66 | Graph graph(kNodeCount); |
Alex Deymo | 161c4a1 | 2014-05-16 15:56:21 -0700 | [diff] [blame] | 67 | |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 68 | graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties())); |
| 69 | graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties())); |
| 70 | graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties())); |
| 71 | graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties())); |
| 72 | graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties())); |
| 73 | graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); |
| 74 | graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties())); |
| 75 | graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties())); |
| 76 | graph[n_g].out_edges.insert(make_pair(n_d, EdgeProperties())); |
| 77 | graph[n_g].out_edges.insert(make_pair(n_f, EdgeProperties())); |
| 78 | graph[n_d].out_edges.insert(make_pair(n_a, EdgeProperties())); |
| 79 | |
| 80 | vector<Vertex::Index> sorted; |
| 81 | TopologicalSort(graph, &sorted); |
| 82 | |
| 83 | for (Vertex::Index i = 0; i < graph.size(); i++) { |
| 84 | vector<Vertex::Index>::size_type src_index = 0; |
| 85 | EXPECT_TRUE(IndexOf(sorted, i, &src_index)); |
| 86 | for (Vertex::EdgeMap::const_iterator it = graph[i].out_edges.begin(); |
| 87 | it != graph[i].out_edges.end(); ++it) { |
| 88 | vector<Vertex::Index>::size_type dst_index = 0; |
| 89 | EXPECT_TRUE(IndexOf(sorted, it->first, &dst_index)); |
| 90 | EXPECT_LT(dst_index, src_index); |
| 91 | } |
| 92 | } |
| 93 | } |
| 94 | |
| 95 | } // namespace chromeos_update_engine |