AU: Ranges class to managing unordered collection of blocks/extents.
Sometimes it's useful to have an unordered collection of ranges and
manipulate them. For example, we may want to do set subtraction on two
collections of extents. This class helps facilitate that.
BUG=7294
TEST=attached unittest
Review URL: http://codereview.chromium.org/3604005
diff --git a/extent_ranges_unittest.cc b/extent_ranges_unittest.cc
new file mode 100755
index 0000000..b5a32d9
--- /dev/null
+++ b/extent_ranges_unittest.cc
@@ -0,0 +1,237 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/extent_ranges.h"
+#include "update_engine/test_utils.h"
+
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class ExtentRangesTest : public ::testing::Test {};
+
+namespace {
+void ExpectRangeEq(const ExtentRanges& ranges,
+ uint64_t* expected,
+ size_t sz,
+ int line) {
+ uint64_t blocks = 0;
+ for (size_t i = 1; i < sz; i += 2) {
+ blocks += expected[i];
+ }
+ EXPECT_EQ(blocks, ranges.blocks()) << "line: " << line;
+
+ const ExtentRanges::ExtentSet& result = ranges.extent_set();
+ ExtentRanges::ExtentSet::const_iterator it = result.begin();
+ for (size_t i = 0; i < sz; i += 2) {
+ EXPECT_FALSE(it == result.end()) << "line: " << line;
+ EXPECT_EQ(expected[i], it->start_block()) << "line: " << line;
+ EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line;
+ ++it;
+ }
+}
+
+#define EXPECT_RANGE_EQ(ranges, var) \
+ do { \
+ ExpectRangeEq(ranges, var, arraysize(var), __LINE__); \
+ } while (0)
+
+void ExpectRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
+ uint64_t b_start, uint64_t b_num) {
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+}
+
+void ExpectFalseRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
+ uint64_t b_start, uint64_t b_num) {
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+}
+
+void ExpectRangesOverlap(uint64_t a_start, uint64_t a_num,
+ uint64_t b_start, uint64_t b_num) {
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+}
+
+void ExpectFalseRangesOverlap(uint64_t a_start, uint64_t a_num,
+ uint64_t b_start, uint64_t b_num) {
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+ a_num),
+ ExtentForRange(b_start,
+ b_num)));
+ EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+ b_num),
+ ExtentForRange(a_start,
+ a_num)));
+}
+
+} // namespace {}
+
+TEST(ExtentRangesTest, ExtentsOverlapTest) {
+ ExpectRangesOverlapOrTouch(10, 20, 30, 10);
+ ExpectRangesOverlap(10, 20, 25, 10);
+ ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
+ ExpectFalseRangesOverlap(10, 20, 30, 10);
+ ExpectRangesOverlap(12, 4, 12, 3);
+}
+
+TEST(ExtentRangesTest, SimpleTest) {
+ ExtentRanges ranges;
+ {
+ uint64_t expected[] = {};
+ // Can't use arraysize() on 0-length arrays:
+ ExpectRangeEq(ranges, expected, 0, __LINE__);
+ }
+ ranges.SubtractBlock(2);
+ {
+ uint64_t expected[] = {};
+ // Can't use arraysize() on 0-length arrays:
+ ExpectRangeEq(ranges, expected, 0, __LINE__);
+ }
+
+ ranges.AddBlock(0);
+ ranges.Dump();
+ ranges.AddBlock(1);
+ ranges.AddBlock(3);
+
+ {
+ uint64_t expected[] = {0, 2, 3, 1};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+ ranges.AddBlock(2);
+ {
+ uint64_t expected[] = {0, 4};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+ ranges.SubtractBlock(2);
+ {
+ uint64_t expected[] = {0, 2, 3, 1};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+
+ for (uint64_t i = 100; i < 1000; i += 100) {
+ ranges.AddExtent(ExtentForRange(i, 50));
+ }
+ {
+ uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
+ 500, 50, 600, 50, 700, 50, 800, 50, 900, 50};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+
+ ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
+ {
+ uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+ ranges.AddExtent(ExtentForRange(100000, 0));
+ {
+ uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+ ranges.SubtractExtent(ExtentForRange(3, 0));
+ {
+ uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50};
+ EXPECT_RANGE_EQ(ranges, expected);
+ }
+}
+
+TEST(ExtentRangesTest, MultipleRanges) {
+ ExtentRanges ranges_a, ranges_b;
+ ranges_a.AddBlock(0);
+ ranges_b.AddBlock(4);
+ ranges_b.AddBlock(3);
+ {
+ uint64_t expected[] = {3, 2};
+ EXPECT_RANGE_EQ(ranges_b, expected);
+ }
+ ranges_a.AddRanges(ranges_b);
+ {
+ uint64_t expected[] = {0, 1, 3, 2};
+ EXPECT_RANGE_EQ(ranges_a, expected);
+ }
+ ranges_a.SubtractRanges(ranges_b);
+ {
+ uint64_t expected[] = {0, 1};
+ EXPECT_RANGE_EQ(ranges_a, expected);
+ }
+ {
+ uint64_t expected[] = {3, 2};
+ EXPECT_RANGE_EQ(ranges_b, expected);
+ }
+}
+
+TEST(ExtentRangesTest, GetExtentsForBlockCountTest) {
+ ExtentRanges ranges;
+ ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30)));
+ {
+ vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0);
+ EXPECT_TRUE(zero_extents.empty());
+ }
+ ::google::protobuf::RepeatedPtrField<Extent> rep_field;
+ *rep_field.Add() = ExtentForRange(30, 40);
+ ranges.AddRepeatedExtents(rep_field);
+ ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10)));
+ *rep_field.Mutable(0) = ExtentForRange(50, 10);
+ ranges.SubtractRepeatedExtents(rep_field);
+ EXPECT_EQ(40, ranges.blocks());
+
+ for (int i = 0; i < 2; i++) {
+ vector<Extent> expected(2);
+ expected[0] = ExtentForRange(10, 10);
+ expected[1] = ExtentForRange(30, i == 0 ? 10 : 20);
+ vector<Extent> actual =
+ ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks());
+ EXPECT_EQ(expected.size(), actual.size());
+ for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) {
+ EXPECT_EQ(expected[j].start_block(), actual[j].start_block())
+ << "j = " << j;
+ EXPECT_EQ(expected[j].num_blocks(), actual[j].num_blocks())
+ << "j = " << j;
+ }
+ }
+}
+
+} // namespace chromeos_update_engine