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 26using std::make_pair; 27using std::vector; 28 29namespace chromeos_update_engine { 30 31class TopologicalSortTest : public ::testing::Test {}; 32 33namespace { 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. 36template<typename T> 37bool 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 52TEST(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