Improve ExtentRanges::AddExtent() runtime from O(n) to O(log n)
Old algorithm iterates over all extents to detect if there's any
intersection, use binary search instead.
Test: Add ~200K extents from an actual OTA, runtime improves from 13s to
0.4s
Bug: 315215541
Change-Id: Ia99eda3a22e726a9c02bfe2a152dc0a5c16efcfc
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
index 612fd67..851db8a 100644
--- a/payload_generator/extent_utils.cc
+++ b/payload_generator/extent_utils.cc
@@ -19,16 +19,13 @@
#include <inttypes.h>
#include <string>
-#include <utility>
#include <vector>
#include <base/logging.h>
#include <base/macros.h>
#include <base/strings/stringprintf.h>
-#include "update_engine/common/utils.h"
#include "update_engine/payload_consumer/payload_constants.h"
-#include "update_engine/payload_generator/annotated_operation.h"
#include "update_engine/payload_generator/extent_ranges.h"
using std::string;
@@ -171,8 +168,7 @@
}
std::ostream& operator<<(std::ostream& out, const Extent& extent) {
- out << "[" << extent.start_block() << " - "
- << extent.start_block() + extent.num_blocks() - 1 << "]";
+ out << "(" << extent.start_block() << " - " << extent.num_blocks() << ")";
return out;
}
@@ -202,4 +198,19 @@
return PrintExtents(out, extents);
}
+std::ostream& operator<<(std::ostream& out, const std::set<Extent>& extents) {
+ return PrintExtents(out, extents);
+}
+
+std::ostream& operator<<(std::ostream& out,
+ const std::set<Extent, ExtentLess>& extents) {
+ return PrintExtents(out, extents);
+}
+
+std::ostream& operator<<(
+ std::ostream& out,
+ Range<std::set<Extent, ExtentLess>::const_iterator> range) {
+ return PrintExtents(out, range);
+}
+
} // namespace chromeos_update_engine