update_engine: Implement FilterExtentRanges.
This patch includes a new FilterExtentRanges() function to filter out
a set of blocks from a list of extents. This function is useful to remove
overlapping lists of blocks when generating operations during delta
generation. While this function is included in the main update_engine
daemon as well, the whole extent_ranges.{cc,h} module will be migrated
to the payload_generator/ directory. This function will be used in a
follow up CL.
BUG=None
TEST=Added unittests.
Change-Id: Ia9d561550fd6f59d59a9e178dd866fd71a095375
Reviewed-on: https://chromium-review.googlesource.com/275802
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
diff --git a/extent_ranges_unittest.cc b/extent_ranges_unittest.cc
index b4de3bc..7624f3d 100644
--- a/extent_ranges_unittest.cc
+++ b/extent_ranges_unittest.cc
@@ -9,6 +9,7 @@
#include <gtest/gtest.h>
#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/test_utils.h"
using std::vector;
@@ -255,4 +256,59 @@
}
}
+TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
+ ExtentRanges ranges;
+ EXPECT_EQ(vector<Extent>(),
+ FilterExtentRanges(vector<Extent>(), ranges));
+ EXPECT_EQ(
+ vector<Extent>{ ExtentForRange(50, 10) },
+ FilterExtentRanges(vector<Extent>{ ExtentForRange(50, 10) }, ranges));
+ // Check that the empty Extents are ignored.
+ EXPECT_EQ(
+ (vector<Extent>{ ExtentForRange(10, 10), ExtentForRange(20, 10) }),
+ FilterExtentRanges(vector<Extent>{
+ ExtentForRange(10, 10),
+ ExtentForRange(3, 0),
+ ExtentForRange(20, 10) }, ranges));
+}
+
+TEST(ExtentRangesTest, FilterExtentRangesMultipleRanges) {
+ // Two overlaping extents, with three ranges to remove.
+ vector<Extent> extents {
+ ExtentForRange(10, 100),
+ ExtentForRange(30, 100) };
+ ExtentRanges ranges;
+ // This overlaps the beginning of the second extent.
+ ranges.AddExtent(ExtentForRange(28, 3));
+ ranges.AddExtent(ExtentForRange(50, 10));
+ ranges.AddExtent(ExtentForRange(70, 10));
+ // This overlaps the end of the second extent.
+ ranges.AddExtent(ExtentForRange(108, 6));
+ EXPECT_EQ(
+ (vector<Extent>{
+ // For the first extent:
+ ExtentForRange(10, 18),
+ ExtentForRange(31, 19),
+ ExtentForRange(60, 10),
+ ExtentForRange(80, 28),
+ // For the second extent:
+ ExtentForRange(31, 19),
+ ExtentForRange(60, 10),
+ ExtentForRange(80, 28),
+ ExtentForRange(114, 16)}),
+ FilterExtentRanges(extents, ranges));
+}
+
+TEST(ExtentRangesTest, FilterExtentRangesOvelapping) {
+ ExtentRanges ranges;
+ ranges.AddExtent(ExtentForRange(10, 3));
+ ranges.AddExtent(ExtentForRange(20, 5));
+ // Requested extent overlaps with one of the ranges.
+ EXPECT_EQ(vector<Extent>(),
+ FilterExtentRanges(vector<Extent>{
+ ExtentForRange(10, 1),
+ ExtentForRange(22, 1) },
+ ranges));
+}
+
} // namespace chromeos_update_engine