update_engine: Further move Extent manipulation to extent_utils.
This patch moves more Extent manipulation functions to extent_utils.
It moves NormalizeExtents() and creates a new ExtentsSublist() function
that will be used by a follow up CL.
BUG=None
TEST=Added unittests.
Change-Id: Icf0ef0af208aa45c9f44e1a73662b3efd8bbbb45
Reviewed-on: https://chromium-review.googlesource.com/275801
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
index dcb8bf8..6896678 100644
--- a/payload_generator/extent_utils.cc
+++ b/payload_generator/extent_utils.cc
@@ -11,6 +11,7 @@
#include <base/logging.h>
#include <base/macros.h>
+#include "update_engine/extent_ranges.h"
#include "update_engine/payload_constants.h"
#include "update_engine/payload_generator/annotated_operation.h"
@@ -46,6 +47,60 @@
return collection.Get(index);
}
+void NormalizeExtents(vector<Extent>* extents) {
+ vector<Extent> new_extents;
+ for (const Extent& curr_ext : *extents) {
+ if (new_extents.empty()) {
+ new_extents.push_back(curr_ext);
+ continue;
+ }
+ Extent& last_ext = new_extents.back();
+ if (last_ext.start_block() + last_ext.num_blocks() ==
+ curr_ext.start_block()) {
+ // If the extents are touching, we want to combine them.
+ last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks());
+ } else {
+ // Otherwise just include the extent as is.
+ new_extents.push_back(curr_ext);
+ }
+ }
+ *extents = new_extents;
+}
+
+vector<Extent> ExtentsSublist(const vector<Extent>& extents,
+ uint64_t block_offset, uint64_t block_count) {
+ vector<Extent> result;
+ uint64_t scanned_blocks = 0;
+ if (block_count == 0)
+ return result;
+ uint64_t end_block_offset = block_offset + block_count;
+ for (const Extent& extent : extents) {
+ // The loop invariant is that if |extents| has enough blocks, there's
+ // still some extent to add to |result|. This implies that at the beginning
+ // of the loop scanned_blocks < block_offset + block_count.
+ if (scanned_blocks + extent.num_blocks() > block_offset) {
+ // This case implies that |extent| has some overlapping with the requested
+ // subsequence.
+ uint64_t new_start = extent.start_block();
+ uint64_t new_num_blocks = extent.num_blocks();
+ if (scanned_blocks + new_num_blocks > end_block_offset) {
+ // Cut the end part of the extent.
+ new_num_blocks = end_block_offset - scanned_blocks;
+ }
+ if (block_offset > scanned_blocks) {
+ // Cut the begin part of the extent.
+ new_num_blocks -= block_offset - scanned_blocks;
+ new_start += block_offset - scanned_blocks;
+ }
+ result.push_back(ExtentForRange(new_start, new_num_blocks));
+ }
+ scanned_blocks += extent.num_blocks();
+ if (scanned_blocks >= end_block_offset)
+ break;
+ }
+ return result;
+}
+
bool operator==(const Extent& a, const Extent& b) {
return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
}