summaryrefslogtreecommitdiffstats
path: root/otautil
diff options
context:
space:
mode:
Diffstat (limited to 'otautil')
-rw-r--r--otautil/include/otautil/rangeset.h50
-rw-r--r--otautil/rangeset.cpp125
2 files changed, 135 insertions, 40 deletions
diff --git a/otautil/include/otautil/rangeset.h b/otautil/include/otautil/rangeset.h
index c4234d181..e91d02ca6 100644
--- a/otautil/include/otautil/rangeset.h
+++ b/otautil/include/otautil/rangeset.h
@@ -30,28 +30,43 @@ class RangeSet {
explicit RangeSet(std::vector<Range>&& pairs);
+ // Parses the given string into a RangeSet. Returns the parsed RangeSet, or an empty RangeSet on
+ // errors.
static RangeSet Parse(const std::string& range_text);
+ // Appends the given Range to the current RangeSet.
+ bool PushBack(Range range);
+
+ // Clears all the ranges from the RangeSet.
+ void Clear();
+
std::string ToString() const;
- // Get the block number for the i-th (starting from 0) block in the RangeSet.
+ // Gets the block number for the i-th (starting from 0) block in the RangeSet.
size_t GetBlockNumber(size_t idx) const;
- // RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5"
- // and "5,7" are not overlapped.
+ // Returns whether the current RangeSet overlaps with other. RangeSet has half-closed half-open
+ // bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" and "5,7" are not overlapped.
bool Overlaps(const RangeSet& other) const;
- // size() gives the number of Range's in this RangeSet.
+ // Returns a vector of RangeSets that contain the same set of blocks represented by the current
+ // RangeSet. The RangeSets in the vector contain similar number of blocks, with a maximum delta
+ // of 1-block between any two of them. For example, 14 blocks would be split into 4 + 4 + 3 + 3,
+ // as opposed to 4 + 4 + 4 + 2. If the total number of blocks (T) is less than groups, it
+ // returns a vector of T 1-block RangeSets. Otherwise the number of the returned RangeSets must
+ // equal to groups. The current RangeSet remains intact after the split.
+ std::vector<RangeSet> Split(size_t groups) const;
+
+ // Returns the number of Range's in this RangeSet.
size_t size() const {
return ranges_.size();
}
- // blocks() gives the number of all blocks in this RangeSet.
+ // Returns the total number of blocks in this RangeSet.
size_t blocks() const {
return blocks_;
}
- // We provide const iterators only.
std::vector<Range>::const_iterator cbegin() const {
return ranges_.cbegin();
}
@@ -60,13 +75,20 @@ class RangeSet {
return ranges_.cend();
}
- // Need to provide begin()/end() since range-based loop expects begin()/end().
+ std::vector<Range>::iterator begin() {
+ return ranges_.begin();
+ }
+
+ std::vector<Range>::iterator end() {
+ return ranges_.end();
+ }
+
std::vector<Range>::const_iterator begin() const {
- return ranges_.cbegin();
+ return ranges_.begin();
}
std::vector<Range>::const_iterator end() const {
- return ranges_.cend();
+ return ranges_.end();
}
// Reverse const iterators for MoveRange().
@@ -78,6 +100,11 @@ class RangeSet {
return ranges_.crend();
}
+ // Returns whether the RangeSet is valid (i.e. non-empty).
+ explicit operator bool() const {
+ return !ranges_.empty();
+ }
+
const Range& operator[](size_t i) const {
return ranges_[i];
}
@@ -109,6 +136,9 @@ class RangeSet {
// every block in the original source.
class SortedRangeSet : public RangeSet {
public:
+ // The block size when working with offset and file length.
+ static constexpr size_t kBlockSize = 4096;
+
SortedRangeSet() {}
// Ranges in the the set should be mutually exclusive; and they're sorted by the start block.
@@ -122,8 +152,6 @@ class SortedRangeSet : public RangeSet {
// Compute the block range the file occupies, and insert that range.
void Insert(size_t start, size_t len);
- void Clear();
-
using RangeSet::Overlaps;
bool Overlaps(size_t start, size_t len) const;
diff --git a/otautil/rangeset.cpp b/otautil/rangeset.cpp
index a121a4efc..96955b9d0 100644
--- a/otautil/rangeset.cpp
+++ b/otautil/rangeset.cpp
@@ -16,8 +16,10 @@
#include "otautil/rangeset.h"
+#include <limits.h>
#include <stddef.h>
+#include <algorithm>
#include <string>
#include <utility>
#include <vector>
@@ -28,47 +30,119 @@
#include <android-base/strings.h>
RangeSet::RangeSet(std::vector<Range>&& pairs) {
- CHECK_NE(pairs.size(), static_cast<size_t>(0)) << "Invalid number of tokens";
+ blocks_ = 0;
+ if (pairs.empty()) {
+ LOG(ERROR) << "Invalid number of tokens";
+ return;
+ }
- // Sanity check the input.
- size_t result = 0;
for (const auto& range : pairs) {
- CHECK_LT(range.first, range.second) << "Empty or negative range: " << range.first << ", "
- << range.second;
- size_t sz = range.second - range.first;
- CHECK_LE(result, SIZE_MAX - sz) << "RangeSet size overflow";
- result += sz;
+ if (!PushBack(range)) {
+ Clear();
+ return;
+ }
}
-
- ranges_ = pairs;
- blocks_ = result;
}
RangeSet RangeSet::Parse(const std::string& range_text) {
std::vector<std::string> pieces = android::base::Split(range_text, ",");
- CHECK_GE(pieces.size(), static_cast<size_t>(3)) << "Invalid range text: " << range_text;
+ if (pieces.size() < 3) {
+ LOG(ERROR) << "Invalid range text: " << range_text;
+ return {};
+ }
size_t num;
- CHECK(android::base::ParseUint(pieces[0], &num, static_cast<size_t>(INT_MAX)))
- << "Failed to parse the number of tokens: " << range_text;
-
- CHECK_NE(num, static_cast<size_t>(0)) << "Invalid number of tokens: " << range_text;
- CHECK_EQ(num % 2, static_cast<size_t>(0)) << "Number of tokens must be even: " << range_text;
- CHECK_EQ(num, pieces.size() - 1) << "Mismatching number of tokens: " << range_text;
+ if (!android::base::ParseUint(pieces[0], &num, static_cast<size_t>(INT_MAX))) {
+ LOG(ERROR) << "Failed to parse the number of tokens: " << range_text;
+ return {};
+ }
+ if (num == 0) {
+ LOG(ERROR) << "Invalid number of tokens: " << range_text;
+ return {};
+ }
+ if (num % 2 != 0) {
+ LOG(ERROR) << "Number of tokens must be even: " << range_text;
+ return {};
+ }
+ if (num != pieces.size() - 1) {
+ LOG(ERROR) << "Mismatching number of tokens: " << range_text;
+ return {};
+ }
std::vector<Range> pairs;
for (size_t i = 0; i < num; i += 2) {
size_t first;
- CHECK(android::base::ParseUint(pieces[i + 1], &first, static_cast<size_t>(INT_MAX)));
size_t second;
- CHECK(android::base::ParseUint(pieces[i + 2], &second, static_cast<size_t>(INT_MAX)));
-
+ if (!android::base::ParseUint(pieces[i + 1], &first, static_cast<size_t>(INT_MAX)) ||
+ !android::base::ParseUint(pieces[i + 2], &second, static_cast<size_t>(INT_MAX))) {
+ return {};
+ }
pairs.emplace_back(first, second);
}
-
return RangeSet(std::move(pairs));
}
+bool RangeSet::PushBack(Range range) {
+ if (range.first >= range.second) {
+ LOG(ERROR) << "Empty or negative range: " << range.first << ", " << range.second;
+ return false;
+ }
+ size_t sz = range.second - range.first;
+ if (blocks_ >= SIZE_MAX - sz) {
+ LOG(ERROR) << "RangeSet size overflow";
+ return false;
+ }
+
+ ranges_.push_back(std::move(range));
+ blocks_ += sz;
+ return true;
+}
+
+void RangeSet::Clear() {
+ ranges_.clear();
+ blocks_ = 0;
+}
+
+std::vector<RangeSet> RangeSet::Split(size_t groups) const {
+ if (ranges_.empty() || groups == 0) return {};
+
+ if (blocks_ < groups) {
+ groups = blocks_;
+ }
+
+ // Evenly distribute blocks, with the first few groups possibly containing one more.
+ size_t mean = blocks_ / groups;
+ std::vector<size_t> blocks_per_group(groups, mean);
+ std::fill_n(blocks_per_group.begin(), blocks_ % groups, mean + 1);
+
+ std::vector<RangeSet> result;
+
+ // Forward iterate Ranges and fill up each group with the desired number of blocks.
+ auto it = ranges_.cbegin();
+ Range range = *it;
+ for (const auto& blocks : blocks_per_group) {
+ RangeSet buffer;
+ size_t needed = blocks;
+ while (needed > 0) {
+ size_t range_blocks = range.second - range.first;
+ if (range_blocks > needed) {
+ // Split the current range and don't advance the iterator.
+ buffer.PushBack({ range.first, range.first + needed });
+ range.first = range.first + needed;
+ break;
+ }
+ buffer.PushBack(range);
+ it++;
+ if (it != ranges_.cend()) {
+ range = *it;
+ }
+ needed -= range_blocks;
+ }
+ result.push_back(std::move(buffer));
+ }
+ return result;
+}
+
std::string RangeSet::ToString() const {
if (ranges_.empty()) {
return "";
@@ -114,8 +188,6 @@ bool RangeSet::Overlaps(const RangeSet& other) const {
return false;
}
-static constexpr size_t kBlockSize = 4096;
-
// Ranges in the the set should be mutually exclusive; and they're sorted by the start block.
SortedRangeSet::SortedRangeSet(std::vector<Range>&& pairs) : RangeSet(std::move(pairs)) {
std::sort(ranges_.begin(), ranges_.end());
@@ -158,11 +230,6 @@ void SortedRangeSet::Insert(size_t start, size_t len) {
Insert(to_insert);
}
-void SortedRangeSet::Clear() {
- blocks_ = 0;
- ranges_.clear();
-}
-
bool SortedRangeSet::Overlaps(size_t start, size_t len) const {
RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } });
return Overlaps(rs);
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-31 00:13:43 +0100