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_ranges.h b/payload_generator/extent_ranges.h
index 08cf5fe..bd468a1 100644
--- a/payload_generator/extent_ranges.h
+++ b/payload_generator/extent_ranges.h
@@ -17,13 +17,13 @@
#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
#define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
-#include <map>
#include <set>
#include <vector>
#include <base/macros.h>
#include "update_engine/common/utils.h"
+#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/update_metadata.pb.h"
// An ExtentRanges object represents an unordered collection of extents (and
@@ -35,15 +35,6 @@
namespace chromeos_update_engine {
-struct ExtentLess {
- 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();
- }
-};
-
Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks);
Extent ExtentForBytes(uint64_t block_size,
uint64_t start_bytes,