summaryrefslogtreecommitdiffstats
path: root/otautil
diff options
context:
space:
mode:
Diffstat (limited to 'otautil')
-rw-r--r--otautil/include/otautil/rangeset.h8
-rw-r--r--otautil/rangeset.cpp40
2 files changed, 48 insertions, 0 deletions
diff --git a/otautil/include/otautil/rangeset.h b/otautil/include/otautil/rangeset.h
index af8ae2dee..e91d02ca6 100644
--- a/otautil/include/otautil/rangeset.h
+++ b/otautil/include/otautil/rangeset.h
@@ -49,6 +49,14 @@ class RangeSet {
// 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;
+ // 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();
diff --git a/otautil/rangeset.cpp b/otautil/rangeset.cpp
index 532cba4a8..96955b9d0 100644
--- a/otautil/rangeset.cpp
+++ b/otautil/rangeset.cpp
@@ -103,6 +103,46 @@ void RangeSet::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 "";