diff options
Diffstat (limited to 'otautil')
-rw-r--r-- | otautil/include/otautil/rangeset.h | 50 | ||||
-rw-r--r-- | otautil/rangeset.cpp | 125 |
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); |