commit bf357c65e5bd973e64aa44657284e0dcb1ee6aa8
author Kelvin Zhang <zhangkelvin@google.com> Mon Aug 09 18:31:12 2021 -0400
committer Tianjie Xu <xunchang@google.com> Fri Aug 27 04:26:12 2021 +0000
tree 8c7646dc5b5c824f9c02f2f938f4782065b2ab55
parent bef99c3da12d495790e4e49704898455432a42ff

Use binary search for ExtentRanges::OverlapsWithExtent

Test: th

Change-Id: I774be2206a482d5360139eab2e3f99827ea471be

payload_generator/extent_ranges.cc

diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index b742611..eecc8b3 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -210,7 +210,7 @@
 }
 
 bool ExtentRanges::OverlapsWithExtent(const Extent& extent) const {
-  for (const auto& entry : extent_set_) {
+  for (const auto& entry : GetCandidateRange(extent)) {
     if (ExtentsOverlap(entry, extent)) {
       return true;
     }

payload_generator/extent_ranges_unittest.cc

diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
index a2053aa..f7a4cd2 100644
--- a/payload_generator/extent_ranges_unittest.cc
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -376,4 +376,18 @@
   ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(8, 4)));
 }
 
+TEST(ExtentRangesTest, OverlapsWithExtent) {
+  ExtentRanges ranges;
+  ranges.AddExtent(ExtentForRange(5, 5));
+  ranges.AddExtent(ExtentForRange(15, 5));
+  ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(3, 10)));
+  ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(17, 10)));
+  ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(0, 10)));
+  ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(10, 5)));
+  ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(20, 5)));
+  ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(7, 1)));
+  ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(0, 100)));
+  ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(19, 1)));
+}
+
 }  // namespace chromeos_update_engine