1 // 2 // Copyright (C) 2009 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/graph_utils.h" 18 19 #include <utility> 20 #include <vector> 21 22 #include <gtest/gtest.h> 23 24 #include "update_engine/payload_consumer/payload_constants.h" 25 #include "update_engine/payload_generator/extent_ranges.h" 26 #include "update_engine/payload_generator/extent_utils.h" 27 28 using std::make_pair; 29 using std::vector; 30 31 namespace chromeos_update_engine { 32 33 class GraphUtilsTest : public ::testing::Test {}; 34 35 TEST(GraphUtilsTest, SimpleTest) { 36 Graph graph(2); 37 38 graph[0].out_edges.insert(make_pair(1, EdgeProperties())); 39 40 vector<Extent>& extents = graph[0].out_edges[1].extents; 41 42 EXPECT_EQ(0U, extents.size()); 43 AppendBlockToExtents(&extents, 0); 44 EXPECT_EQ(1U, extents.size()); 45 AppendBlockToExtents(&extents, 1); 46 AppendBlockToExtents(&extents, 2); 47 EXPECT_EQ(1U, extents.size()); 48 AppendBlockToExtents(&extents, 4); 49 50 EXPECT_EQ(2U, extents.size()); 51 EXPECT_EQ(0U, extents[0].start_block()); 52 EXPECT_EQ(3U, extents[0].num_blocks()); 53 EXPECT_EQ(4U, extents[1].start_block()); 54 EXPECT_EQ(1U, extents[1].num_blocks()); 55 56 EXPECT_EQ(4U, graph_utils::EdgeWeight(graph, make_pair(0, 1))); 57 } 58 59 60 TEST(GraphUtilsTest, DepsTest) { 61 Graph graph(3); 62 63 graph_utils::AddReadBeforeDep(&graph[0], 1, 3); 64 EXPECT_EQ(1U, graph[0].out_edges.size()); 65 { 66 Extent& extent = graph[0].out_edges[1].extents[0]; 67 EXPECT_EQ(3U, extent.start_block()); 68 EXPECT_EQ(1U, extent.num_blocks()); 69 } 70 graph_utils::AddReadBeforeDep(&graph[0], 1, 4); 71 EXPECT_EQ(1U, graph[0].out_edges.size()); 72 { 73 Extent& extent = graph[0].out_edges[1].extents[0]; 74 EXPECT_EQ(3U, extent.start_block()); 75 EXPECT_EQ(2U, extent.num_blocks()); 76 } 77 graph_utils::AddReadBeforeDepExtents(&graph[2], 1, 78 vector<Extent>(1, ExtentForRange(5, 2))); 79 EXPECT_EQ(1U, graph[2].out_edges.size()); 80 { 81 Extent& extent = graph[2].out_edges[1].extents[0]; 82 EXPECT_EQ(5U, extent.start_block()); 83 EXPECT_EQ(2U, extent.num_blocks()); 84 } 85 // Change most recent edge from read-before to write-before 86 graph[2].out_edges[1].write_extents.swap(graph[2].out_edges[1].extents); 87 graph_utils::DropWriteBeforeDeps(&graph[2].out_edges); 88 EXPECT_EQ(0U, graph[2].out_edges.size()); 89 90 EXPECT_EQ(1U, graph[0].out_edges.size()); 91 graph_utils::DropIncomingEdgesTo(&graph, 1); 92 EXPECT_EQ(0U, graph[0].out_edges.size()); 93 } 94 95 } // namespace chromeos_update_engine 96