From bf5b77dbf73eef715bb49b43e113833efbcb2994 Mon Sep 17 00:00:00 2001 From: Tao Bao Date: Thu, 30 Mar 2017 16:57:29 -0700 Subject: Change the internal representation in RangeSet. This CL makes the following changes to RangeSet: - Uses std::pair to represent a Range; - Uses std::vector to represent a RangeSet; - Provides const iterators (forward and reverse); - Provides const accessor; - 'blocks()' returns the number of blocks (formerly 'size'); - 'size()' returns the number of Range's (formerly 'count'). Test: recovery_unit_test Test: Apply an incremental update with the new updater. Change-Id: Ia1fbb343370a152e1f7aa050cf914c2da09b1396 --- updater/include/updater/rangeset.h | 125 ++++++++++++++++++++++++++++--------- 1 file changed, 97 insertions(+), 28 deletions(-) (limited to 'updater/include') diff --git a/updater/include/updater/rangeset.h b/updater/include/updater/rangeset.h index afaa82dcd..fad038043 100644 --- a/updater/include/updater/rangeset.h +++ b/updater/include/updater/rangeset.h @@ -19,16 +19,35 @@ #include #include +#include #include #include #include #include -struct RangeSet { - size_t count; // Limit is INT_MAX. - size_t size; // The number of blocks in the RangeSet. - std::vector pos; // Actual limit is INT_MAX. +using Range = std::pair; + +class RangeSet { + public: + RangeSet() : blocks_(0) {} + + explicit RangeSet(std::vector&& pairs) { + CHECK_NE(pairs.size(), static_cast(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 pieces = android::base::Split(range_text, ","); @@ -42,44 +61,43 @@ struct RangeSet { CHECK_EQ(num % 2, static_cast(0)) << "Number of tokens must be even: " << range_text; CHECK_EQ(num, pieces.size() - 1) << "Mismatching number of tokens: " << range_text; - std::vector pairs(num); - size_t size = 0; + std::vector pairs; for (size_t i = 0; i < num; i += 2) { - CHECK(android::base::ParseUint(pieces[i + 1], &pairs[i], static_cast(INT_MAX))); - CHECK(android::base::ParseUint(pieces[i + 2], &pairs[i + 1], static_cast(INT_MAX))); - CHECK_LT(pairs[i], pairs[i + 1]) - << "Empty or negative range: " << pairs[i] << ", " << pairs[i + 1]; - - size_t sz = pairs[i + 1] - pairs[i]; - CHECK_LE(size, SIZE_MAX - sz) << "RangeSet size overflow"; - size += sz; + size_t first; + CHECK(android::base::ParseUint(pieces[i + 1], &first, static_cast(INT_MAX))); + size_t second; + CHECK(android::base::ParseUint(pieces[i + 2], &second, static_cast(INT_MAX))); + + pairs.emplace_back(first, second); } - return RangeSet{ num / 2, size, std::move(pairs) }; + return RangeSet(std::move(pairs)); } // 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, size) << "Index " << idx << " is greater than RangeSet size " << size; - for (size_t i = 0; i < pos.size(); i += 2) { - if (idx < pos[i + 1] - pos[i]) { - return pos[i] + idx; + 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 -= (pos[i + 1] - pos[i]); + idx -= (range.second - range.first); } - CHECK(false); + + CHECK(false) << "Failed to find block number for index " << idx; return 0; // Unreachable, but to make compiler happy. } // 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 (size_t i = 0; i < count; ++i) { - size_t start = pos[i * 2]; - size_t end = pos[i * 2 + 1]; - for (size_t j = 0; j < other.count; ++j) { - size_t other_start = other.pos[j * 2]; - size_t other_end = other.pos[j * 2 + 1]; + 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; @@ -89,7 +107,58 @@ struct RangeSet { return false; } + // size() gives 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. + size_t blocks() const { + return blocks_; + } + + // We provide const iterators only. + std::vector::const_iterator cbegin() const { + return ranges_.cbegin(); + } + + std::vector::const_iterator cend() const { + return ranges_.cend(); + } + + // Need to provide begin()/end() since range-based loop expects begin()/end(). + std::vector::const_iterator begin() const { + return ranges_.cbegin(); + } + + std::vector::const_iterator end() const { + return ranges_.cend(); + } + + // Reverse const iterators for MoveRange(). + std::vector::const_reverse_iterator crbegin() const { + return ranges_.crbegin(); + } + + std::vector::const_reverse_iterator crend() const { + return ranges_.crend(); + } + + const Range& operator[](size_t i) const { + return ranges_[i]; + } + bool operator==(const RangeSet& other) const { - return (count == other.count && size == other.size && pos == other.pos); + // The orders of Range's matter. "4,1,5,8,10" != "4,8,10,1,5". + return (ranges_ == other.ranges_); } + + bool operator!=(const RangeSet& other) const { + return ranges_ != other.ranges_; + } + + private: + // Actual limit for each value and the total number are both INT_MAX. + std::vector ranges_; + size_t blocks_; }; -- cgit v1.2.3