Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / system / update_engine / e4ad2508de4d69d7a90d3ce441efe2c82c55bd1d / . / extent_ranges_unittest.cc
blob: b5a32d96a6501688df198ca0aa96c18d1c7ee492 [file] [log] [blame]
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -0700[diff] [blame]1// Copyright (c) 2010 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 <vector>
6
7#include <gtest/gtest.h>
8
9#include "update_engine/extent_ranges.h"
10#include "update_engine/test_utils.h"
11
12using std::vector;
13
14namespace chromeos_update_engine {
15
16class ExtentRangesTest : public ::testing::Test {};
17
18namespace {
19void ExpectRangeEq(const ExtentRanges& ranges,
20 uint64_t* expected,
21 size_t sz,
22 int line) {
23 uint64_t blocks = 0;
24 for (size_t i = 1; i < sz; i += 2) {
25 blocks += expected[i];
26 }
27 EXPECT_EQ(blocks, ranges.blocks()) << "line: " << line;
28
29 const ExtentRanges::ExtentSet& result = ranges.extent_set();
30 ExtentRanges::ExtentSet::const_iterator it = result.begin();
31 for (size_t i = 0; i < sz; i += 2) {
32 EXPECT_FALSE(it == result.end()) << "line: " << line;
33 EXPECT_EQ(expected[i], it->start_block()) << "line: " << line;
34 EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line;
35 ++it;
36 }
37}
38
39#define EXPECT_RANGE_EQ(ranges, var) \
40 do { \
41 ExpectRangeEq(ranges, var, arraysize(var), __LINE__); \
42 } while (0)
43
44void ExpectRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
45 uint64_t b_start, uint64_t b_num) {
46 EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
47 a_num),
48 ExtentForRange(b_start,
49 b_num)));
50 EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
51 b_num),
52 ExtentForRange(a_start,
53 a_num)));
54}
55
56void ExpectFalseRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
57 uint64_t b_start, uint64_t b_num) {
58 EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
59 a_num),
60 ExtentForRange(b_start,
61 b_num)));
62 EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
63 b_num),
64 ExtentForRange(a_start,
65 a_num)));
66 EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
67 a_num),
68 ExtentForRange(b_start,
69 b_num)));
70 EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
71 b_num),
72 ExtentForRange(a_start,
73 a_num)));
74}
75
76void ExpectRangesOverlap(uint64_t a_start, uint64_t a_num,
77 uint64_t b_start, uint64_t b_num) {
78 EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
79 a_num),
80 ExtentForRange(b_start,
81 b_num)));
82 EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
83 b_num),
84 ExtentForRange(a_start,
85 a_num)));
86 EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
87 a_num),
88 ExtentForRange(b_start,
89 b_num)));
90 EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
91 b_num),
92 ExtentForRange(a_start,
93 a_num)));
94}
95
96void ExpectFalseRangesOverlap(uint64_t a_start, uint64_t a_num,
97 uint64_t b_start, uint64_t b_num) {
98 EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
99 a_num),
100 ExtentForRange(b_start,
101 b_num)));
102 EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
103 b_num),
104 ExtentForRange(a_start,
105 a_num)));
106}
107
108} // namespace {}
109
110TEST(ExtentRangesTest, ExtentsOverlapTest) {
111 ExpectRangesOverlapOrTouch(10, 20, 30, 10);
112 ExpectRangesOverlap(10, 20, 25, 10);
113 ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
114 ExpectFalseRangesOverlap(10, 20, 30, 10);
115 ExpectRangesOverlap(12, 4, 12, 3);
116}
117
118TEST(ExtentRangesTest, SimpleTest) {
119 ExtentRanges ranges;
120 {
121 uint64_t expected[] = {};
122 // Can't use arraysize() on 0-length arrays:
123 ExpectRangeEq(ranges, expected, 0, __LINE__);
124 }
125 ranges.SubtractBlock(2);
126 {
127 uint64_t expected[] = {};
128 // Can't use arraysize() on 0-length arrays:
129 ExpectRangeEq(ranges, expected, 0, __LINE__);
130 }
131
132 ranges.AddBlock(0);
133 ranges.Dump();
134 ranges.AddBlock(1);
135 ranges.AddBlock(3);
136
137 {
138 uint64_t expected[] = {0, 2, 3, 1};
139 EXPECT_RANGE_EQ(ranges, expected);
140 }
141 ranges.AddBlock(2);
142 {
143 uint64_t expected[] = {0, 4};
144 EXPECT_RANGE_EQ(ranges, expected);
145 }
146 ranges.SubtractBlock(2);
147 {
148 uint64_t expected[] = {0, 2, 3, 1};
149 EXPECT_RANGE_EQ(ranges, expected);
150 }
151
152 for (uint64_t i = 100; i < 1000; i += 100) {
153 ranges.AddExtent(ExtentForRange(i, 50));
154 }
155 {
156 uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
157 500, 50, 600, 50, 700, 50, 800, 50, 900, 50};
158 EXPECT_RANGE_EQ(ranges, expected);
159 }
160
161 ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
162 {
163 uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
164 600, 50, 700, 50, 800, 50, 900, 50};
165 EXPECT_RANGE_EQ(ranges, expected);
166 }
167 ranges.AddExtent(ExtentForRange(100000, 0));
168 {
169 uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
170 600, 50, 700, 50, 800, 50, 900, 50};
171 EXPECT_RANGE_EQ(ranges, expected);
172 }
173 ranges.SubtractExtent(ExtentForRange(3, 0));
174 {
175 uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
176 600, 50, 700, 50, 800, 50, 900, 50};
177 EXPECT_RANGE_EQ(ranges, expected);
178 }
179}
180
181TEST(ExtentRangesTest, MultipleRanges) {
182 ExtentRanges ranges_a, ranges_b;
183 ranges_a.AddBlock(0);
184 ranges_b.AddBlock(4);
185 ranges_b.AddBlock(3);
186 {
187 uint64_t expected[] = {3, 2};
188 EXPECT_RANGE_EQ(ranges_b, expected);
189 }
190 ranges_a.AddRanges(ranges_b);
191 {
192 uint64_t expected[] = {0, 1, 3, 2};
193 EXPECT_RANGE_EQ(ranges_a, expected);
194 }
195 ranges_a.SubtractRanges(ranges_b);
196 {
197 uint64_t expected[] = {0, 1};
198 EXPECT_RANGE_EQ(ranges_a, expected);
199 }
200 {
201 uint64_t expected[] = {3, 2};
202 EXPECT_RANGE_EQ(ranges_b, expected);
203 }
204}
205
206TEST(ExtentRangesTest, GetExtentsForBlockCountTest) {
207 ExtentRanges ranges;
208 ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30)));
209 {
210 vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0);
211 EXPECT_TRUE(zero_extents.empty());
212 }
213 ::google::protobuf::RepeatedPtrField<Extent> rep_field;
214 *rep_field.Add() = ExtentForRange(30, 40);
215 ranges.AddRepeatedExtents(rep_field);
216 ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10)));
217 *rep_field.Mutable(0) = ExtentForRange(50, 10);
218 ranges.SubtractRepeatedExtents(rep_field);
219 EXPECT_EQ(40, ranges.blocks());
220
221 for (int i = 0; i < 2; i++) {
222 vector<Extent> expected(2);
223 expected[0] = ExtentForRange(10, 10);
224 expected[1] = ExtentForRange(30, i == 0 ? 10 : 20);
225 vector<Extent> actual =
226 ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks());
227 EXPECT_EQ(expected.size(), actual.size());
228 for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) {
229 EXPECT_EQ(expected[j].start_block(), actual[j].start_block())
230 << "j = " << j;
231 EXPECT_EQ(expected[j].num_blocks(), actual[j].num_blocks())
232 << "j = " << j;
233 }
234 }
235}
236
237} // namespace chromeos_update_engine