graph_utils_unittest.cc revision 161c4a132743f15fc4757112b673085c2a7a7f29 
1// Copyright (c) 2009 The Chromium OS Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include <utility>
6#include <vector>
7
8#include <gtest/gtest.h>
9
10#include "update_engine/extent_ranges.h"
11#include "update_engine/payload_constants.h"
12#include "update_engine/payload_generator/graph_utils.h"
13
14using std::make_pair;
15using std::vector;
16
17namespace chromeos_update_engine {
18
19class GraphUtilsTest : public ::testing::Test {};
20
21TEST(GraphUtilsTest, SimpleTest) {
22  Graph graph(2);
23
24  graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
25
26  vector<Extent>& extents = graph[0].out_edges[1].extents;
27
28  EXPECT_EQ(0, extents.size());
29  graph_utils::AppendBlockToExtents(&extents, 0);
30  EXPECT_EQ(1, extents.size());
31  graph_utils::AppendBlockToExtents(&extents, 1);
32  graph_utils::AppendBlockToExtents(&extents, 2);
33  EXPECT_EQ(1, extents.size());
34  graph_utils::AppendBlockToExtents(&extents, 4);
35
36  EXPECT_EQ(2, extents.size());
37  EXPECT_EQ(0, extents[0].start_block());
38  EXPECT_EQ(3, extents[0].num_blocks());
39  EXPECT_EQ(4, extents[1].start_block());
40  EXPECT_EQ(1, extents[1].num_blocks());
41
42  EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
43}
44
45TEST(GraphUtilsTest, AppendSparseToExtentsTest) {
46  vector<Extent> extents;
47
48  EXPECT_EQ(0, extents.size());
49  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
50  EXPECT_EQ(1, extents.size());
51  graph_utils::AppendBlockToExtents(&extents, 0);
52  EXPECT_EQ(2, extents.size());
53  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
54  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
55
56  ASSERT_EQ(3, extents.size());
57  EXPECT_EQ(kSparseHole, extents[0].start_block());
58  EXPECT_EQ(1, extents[0].num_blocks());
59  EXPECT_EQ(0, extents[1].start_block());
60  EXPECT_EQ(1, extents[1].num_blocks());
61  EXPECT_EQ(kSparseHole, extents[2].start_block());
62  EXPECT_EQ(2, extents[2].num_blocks());
63}
64
65TEST(GraphUtilsTest, BlocksInExtentsTest) {
66  {
67    vector<Extent> extents;
68    EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
69    extents.push_back(ExtentForRange(0, 1));
70    EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
71    extents.push_back(ExtentForRange(23, 55));
72    EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
73    extents.push_back(ExtentForRange(1, 2));
74    EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
75  }
76  {
77    google::protobuf::RepeatedPtrField<Extent> extents;
78    EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
79    *extents.Add() = ExtentForRange(0, 1);
80    EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
81    *extents.Add() = ExtentForRange(23, 55);
82    EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
83    *extents.Add() = ExtentForRange(1, 2);
84    EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
85  }
86}
87
88TEST(GraphUtilsTest, DepsTest) {
89  Graph graph(3);
90
91  graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
92  EXPECT_EQ(1, graph[0].out_edges.size());
93  {
94    Extent& extent = graph[0].out_edges[1].extents[0];
95    EXPECT_EQ(3, extent.start_block());
96    EXPECT_EQ(1, extent.num_blocks());
97  }
98  graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
99  EXPECT_EQ(1, graph[0].out_edges.size());
100  {
101    Extent& extent = graph[0].out_edges[1].extents[0];
102    EXPECT_EQ(3, extent.start_block());
103    EXPECT_EQ(2, extent.num_blocks());
104  }
105  graph_utils::AddReadBeforeDepExtents(&graph[2], 1,
106    vector<Extent>(1, ExtentForRange(5, 2)));
107  EXPECT_EQ(1, graph[2].out_edges.size());
108  {
109    Extent& extent = graph[2].out_edges[1].extents[0];
110    EXPECT_EQ(5, extent.start_block());
111    EXPECT_EQ(2, extent.num_blocks());
112  }
113  // Change most recent edge from read-before to write-before
114  graph[2].out_edges[1].write_extents.swap(graph[2].out_edges[1].extents);
115  graph_utils::DropWriteBeforeDeps(&graph[2].out_edges);
116  EXPECT_EQ(0, graph[2].out_edges.size());
117
118  EXPECT_EQ(1, graph[0].out_edges.size());
119  graph_utils::DropIncomingEdgesTo(&graph, 1);
120  EXPECT_EQ(0, graph[0].out_edges.size());
121}
122
123}  // namespace chromeos_update_engine
124