graph_utils_unittest.cc revision aea4c1cea20dda7ae7e85fc8924a2d784f70d806 
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_constants.h"
25#include "update_engine/payload_generator/extent_ranges.h"
26#include "update_engine/payload_generator/extent_utils.h"
27
28using std::make_pair;
29using std::vector;
30
31namespace chromeos_update_engine {
32
33class GraphUtilsTest : public ::testing::Test {};
34
35TEST(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(0, extents.size());
43  AppendBlockToExtents(&extents, 0);
44  EXPECT_EQ(1, extents.size());
45  AppendBlockToExtents(&extents, 1);
46  AppendBlockToExtents(&extents, 2);
47  EXPECT_EQ(1, extents.size());
48  AppendBlockToExtents(&extents, 4);
49
50  EXPECT_EQ(2, extents.size());
51  EXPECT_EQ(0, extents[0].start_block());
52  EXPECT_EQ(3, extents[0].num_blocks());
53  EXPECT_EQ(4, extents[1].start_block());
54  EXPECT_EQ(1, extents[1].num_blocks());
55
56  EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
57}
58
59
60TEST(GraphUtilsTest, DepsTest) {
61  Graph graph(3);
62
63  graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
64  EXPECT_EQ(1, graph[0].out_edges.size());
65  {
66    Extent& extent = graph[0].out_edges[1].extents[0];
67    EXPECT_EQ(3, extent.start_block());
68    EXPECT_EQ(1, extent.num_blocks());
69  }
70  graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
71  EXPECT_EQ(1, graph[0].out_edges.size());
72  {
73    Extent& extent = graph[0].out_edges[1].extents[0];
74    EXPECT_EQ(3, extent.start_block());
75    EXPECT_EQ(2, extent.num_blocks());
76  }
77  graph_utils::AddReadBeforeDepExtents(&graph[2], 1,
78    vector<Extent>(1, ExtentForRange(5, 2)));
79  EXPECT_EQ(1, graph[2].out_edges.size());
80  {
81    Extent& extent = graph[2].out_edges[1].extents[0];
82    EXPECT_EQ(5, extent.start_block());
83    EXPECT_EQ(2, 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(0, graph[2].out_edges.size());
89
90  EXPECT_EQ(1, graph[0].out_edges.size());
91  graph_utils::DropIncomingEdgesTo(&graph, 1);
92  EXPECT_EQ(0, graph[0].out_edges.size());
93}
94
95}  // namespace chromeos_update_engine
96