AU: Ranges class to managing unordered collection of blocks/extents.

extent_ranges_unittest.cc

Index: extent_ranges_unittest.cc
diff --git a/extent_ranges_unittest.cc b/extent_ranges_unittest.cc
new file mode 100755
index 0000000000000000000000000000000000000000..b5a32d96a6501688df198ca0aa96c18d1c7ee492
--- /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