diff options
Diffstat (limited to '')
-rw-r--r-- | otautil/include/otautil/rangeset.h | 166 |
1 files changed, 15 insertions, 151 deletions
diff --git a/otautil/include/otautil/rangeset.h b/otautil/include/otautil/rangeset.h index f224a08be..c4234d181 100644 --- a/otautil/include/otautil/rangeset.h +++ b/otautil/include/otautil/rangeset.h @@ -22,103 +22,24 @@ #include <utility> #include <vector> -#include <android-base/logging.h> -#include <android-base/parseint.h> -#include <android-base/stringprintf.h> -#include <android-base/strings.h> - using Range = std::pair<size_t, size_t>; class RangeSet { public: RangeSet() : blocks_(0) {} - explicit RangeSet(std::vector<Range>&& pairs) { - CHECK_NE(pairs.size(), static_cast<size_t>(0)) << "Invalid number of tokens"; - - // 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; - } - - ranges_ = pairs; - blocks_ = result; - } - - static 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; - - 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; - - 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))); + explicit RangeSet(std::vector<Range>&& pairs); - pairs.emplace_back(first, second); - } + static RangeSet Parse(const std::string& range_text); - return RangeSet(std::move(pairs)); - } - - std::string ToString() const { - if (ranges_.empty()) { - return ""; - } - std::string result = std::to_string(ranges_.size() * 2); - for (const auto& r : ranges_) { - result += android::base::StringPrintf(",%zu,%zu", r.first, r.second); - } - - return result; - } + std::string ToString() const; // Get the block number for the i-th (starting from 0) block in the RangeSet. - size_t GetBlockNumber(size_t idx) const { - CHECK_LT(idx, blocks_) << "Out of bound index " << idx << " (total blocks: " << blocks_ << ")"; - - for (const auto& range : ranges_) { - if (idx < range.second - range.first) { - return range.first + idx; - } - idx -= (range.second - range.first); - } - - CHECK(false) << "Failed to find block number for index " << idx; - return 0; // Unreachable, but to make compiler happy. - } + 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. - bool Overlaps(const RangeSet& other) const { - for (const auto& range : ranges_) { - size_t start = range.first; - size_t end = range.second; - for (const auto& other_range : other.ranges_) { - size_t other_start = other_range.first; - size_t other_end = other_range.second; - // [start, end) vs [other_start, other_end) - if (!(other_start >= end || start >= other_end)) { - return true; - } - } - } - return false; - } + bool Overlaps(const RangeSet& other) const; // size() gives the number of Range's in this RangeSet. size_t size() const { @@ -176,8 +97,6 @@ class RangeSet { size_t blocks_; }; -static constexpr size_t kBlockSize = 4096; - // The class is a sorted version of a RangeSet; and it's useful in imgdiff to split the input // files when we're handling large zip files. Specifically, we can treat the input file as a // continuous RangeSet (i.e. RangeSet("0-99") for a 100 blocks file); and break it down into @@ -193,57 +112,21 @@ class SortedRangeSet : public RangeSet { SortedRangeSet() {} // Ranges in the the set should be mutually exclusive; and they're sorted by the start block. - explicit SortedRangeSet(std::vector<Range>&& pairs) : RangeSet(std::move(pairs)) { - std::sort(ranges_.begin(), ranges_.end()); - } + explicit SortedRangeSet(std::vector<Range>&& pairs); - void Insert(const Range& to_insert) { - SortedRangeSet rs({ to_insert }); - Insert(rs); - } + void Insert(const Range& to_insert); // Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges. - void Insert(const SortedRangeSet& rs) { - if (rs.size() == 0) { - return; - } - // Merge and sort the two RangeSets. - std::vector<Range> temp = std::move(ranges_); - std::copy(rs.begin(), rs.end(), std::back_inserter(temp)); - std::sort(temp.begin(), temp.end()); - - Clear(); - // Trim overlaps and insert the result back to ranges_. - Range to_insert = temp.front(); - for (auto it = temp.cbegin() + 1; it != temp.cend(); it++) { - if (it->first <= to_insert.second) { - to_insert.second = std::max(to_insert.second, it->second); - } else { - ranges_.push_back(to_insert); - blocks_ += (to_insert.second - to_insert.first); - to_insert = *it; - } - } - ranges_.push_back(to_insert); - blocks_ += (to_insert.second - to_insert.first); - } + void Insert(const SortedRangeSet& rs); - void Clear() { - blocks_ = 0; - ranges_.clear(); - } + // 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 { - RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } }); - return Overlaps(rs); - } - // Compute the block range the file occupies, and insert that range. - void Insert(size_t start, size_t len) { - Range to_insert{ start / kBlockSize, (start + len - 1) / kBlockSize + 1 }; - Insert(to_insert); - } + bool Overlaps(size_t start, size_t len) const; // Given an offset of the file, checks if the corresponding block (by considering the file as // 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset @@ -255,24 +138,5 @@ class SortedRangeSet : public RangeSet { // An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th // item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10 // + 10) in a range represented by this SortedRangeSet. - size_t GetOffsetInRangeSet(size_t old_offset) const { - size_t old_block_start = old_offset / kBlockSize; - size_t new_block_start = 0; - for (const auto& range : ranges_) { - // Find the index of old_block_start. - if (old_block_start >= range.second) { - new_block_start += (range.second - range.first); - } else if (old_block_start >= range.first) { - new_block_start += (old_block_start - range.first); - return (new_block_start * kBlockSize + old_offset % kBlockSize); - } else { - CHECK(false) << "block_start " << old_block_start - << " is missing between two ranges: " << this->ToString(); - return 0; - } - } - CHECK(false) << "block_start " << old_block_start - << " exceeds the limit of current RangeSet: " << this->ToString(); - return 0; - } -};
\ No newline at end of file + size_t GetOffsetInRangeSet(size_t old_offset) const; +}; |