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.h b/payload_generator/extent_utils.h
index f8d36e7..52b6d1e 100644
--- a/payload_generator/extent_utils.h
+++ b/payload_generator/extent_utils.h
@@ -23,13 +23,21 @@
#include <base/logging.h>
-#include "google/protobuf/repeated_field.h"
+#include "update_engine/common/utils.h"
#include "update_engine/payload_consumer/payload_constants.h"
#include "update_engine/update_metadata.pb.h"
// Utility functions for manipulating Extents and lists of blocks.
namespace chromeos_update_engine {
+struct ExtentLess {
+ constexpr bool operator()(const Extent& x, const Extent& y) const {
+ if (x.start_block() == y.start_block()) {
+ return x.num_blocks() < y.num_blocks();
+ }
+ return x.start_block() < y.start_block();
+ }
+};
// |block| must either be the next block in the last extent or a block
// in the next extent. This function will not handle inserting block
@@ -130,6 +138,14 @@
std::ostream& operator<<(std::ostream& out, const Extent& extent);
std::ostream& operator<<(std::ostream& out, const std::vector<Extent>& extent);
+std::ostream& operator<<(std::ostream& out, const std::set<Extent>& extents);
+
+std::ostream& operator<<(std::ostream& out,
+ const std::set<Extent, ExtentLess>& extents);
+std::ostream& operator<<(
+ std::ostream& out,
+ Range<std::set<Extent, ExtentLess>::const_iterator> range);
+
std::ostream& operator<<(
std::ostream& out,
const google::protobuf::RepeatedPtrField<Extent>& extent);