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 // 16 17 #include "update_engine/payload_generator/topological_sort.h" 18 19 #include <utility> 20 #include <vector> 21 22 #include <gtest/gtest.h> 23 24 #include "update_engine/payload_generator/graph_types.h" 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 } 50 } // namespace 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); 67 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 96
