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