1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <stddef.h> 20 21 #include <string> 22 #include <utility> 23 #include <vector> 24 25 #include <android-base/logging.h> 26 #include <android-base/parseint.h> 27 #include <android-base/strings.h> 28 29 using Range = std::pair<size_t, size_t>; 30 31 class RangeSet { 32 public: 33 RangeSet() : blocks_(0) {} 34 35 explicit RangeSet(std::vector<Range>&& pairs) { 36 CHECK_NE(pairs.size(), static_cast<size_t>(0)) << "Invalid number of tokens"; 37 38 // Sanity check the input. 39 size_t result = 0; 40 for (const auto& range : pairs) { 41 CHECK_LT(range.first, range.second) 42 << "Empty or negative range: " << range.first << ", " << range.second; 43 size_t sz = range.second - range.first; 44 CHECK_LE(result, SIZE_MAX - sz) << "RangeSet size overflow"; 45 result += sz; 46 } 47 48 ranges_ = pairs; 49 blocks_ = result; 50 } 51 52 static RangeSet Parse(const std::string& range_text) { 53 std::vector<std::string> pieces = android::base::Split(range_text, ","); 54 CHECK_GE(pieces.size(), static_cast<size_t>(3)) << "Invalid range text: " << range_text; 55 56 size_t num; 57 CHECK(android::base::ParseUint(pieces[0], &num, static_cast<size_t>(INT_MAX))) 58 << "Failed to parse the number of tokens: " << range_text; 59 60 CHECK_NE(num, static_cast<size_t>(0)) << "Invalid number of tokens: " << range_text; 61 CHECK_EQ(num % 2, static_cast<size_t>(0)) << "Number of tokens must be even: " << range_text; 62 CHECK_EQ(num, pieces.size() - 1) << "Mismatching number of tokens: " << range_text; 63 64 std::vector<Range> pairs; 65 for (size_t i = 0; i < num; i += 2) { 66 size_t first; 67 CHECK(android::base::ParseUint(pieces[i + 1], &first, static_cast<size_t>(INT_MAX))); 68 size_t second; 69 CHECK(android::base::ParseUint(pieces[i + 2], &second, static_cast<size_t>(INT_MAX))); 70 71 pairs.emplace_back(first, second); 72 } 73 74 return RangeSet(std::move(pairs)); 75 } 76 77 // Get the block number for the i-th (starting from 0) block in the RangeSet. 78 size_t GetBlockNumber(size_t idx) const { 79 CHECK_LT(idx, blocks_) << "Out of bound index " << idx << " (total blocks: " << blocks_ << ")"; 80 81 for (const auto& range : ranges_) { 82 if (idx < range.second - range.first) { 83 return range.first + idx; 84 } 85 idx -= (range.second - range.first); 86 } 87 88 CHECK(false) << "Failed to find block number for index " << idx; 89 return 0; // Unreachable, but to make compiler happy. 90 } 91 92 // RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" 93 // and "5,7" are not overlapped. 94 bool Overlaps(const RangeSet& other) const { 95 for (const auto& range : ranges_) { 96 size_t start = range.first; 97 size_t end = range.second; 98 for (const auto& other_range : other.ranges_) { 99 size_t other_start = other_range.first; 100 size_t other_end = other_range.second; 101 // [start, end) vs [other_start, other_end) 102 if (!(other_start >= end || start >= other_end)) { 103 return true; 104 } 105 } 106 } 107 return false; 108 } 109 110 // size() gives the number of Range's in this RangeSet. 111 size_t size() const { 112 return ranges_.size(); 113 } 114 115 // blocks() gives the number of all blocks in this RangeSet. 116 size_t blocks() const { 117 return blocks_; 118 } 119 120 // We provide const iterators only. 121 std::vector<Range>::const_iterator cbegin() const { 122 return ranges_.cbegin(); 123 } 124 125 std::vector<Range>::const_iterator cend() const { 126 return ranges_.cend(); 127 } 128 129 // Need to provide begin()/end() since range-based loop expects begin()/end(). 130 std::vector<Range>::const_iterator begin() const { 131 return ranges_.cbegin(); 132 } 133 134 std::vector<Range>::const_iterator end() const { 135 return ranges_.cend(); 136 } 137 138 // Reverse const iterators for MoveRange(). 139 std::vector<Range>::const_reverse_iterator crbegin() const { 140 return ranges_.crbegin(); 141 } 142 143 std::vector<Range>::const_reverse_iterator crend() const { 144 return ranges_.crend(); 145 } 146 147 const Range& operator[](size_t i) const { 148 return ranges_[i]; 149 } 150 151 bool operator==(const RangeSet& other) const { 152 // The orders of Range's matter. "4,1,5,8,10" != "4,8,10,1,5". 153 return (ranges_ == other.ranges_); 154 } 155 156 bool operator!=(const RangeSet& other) const { 157 return ranges_ != other.ranges_; 158 } 159 160 private: 161 // Actual limit for each value and the total number are both INT_MAX. 162 std::vector<Range> ranges_; 163 size_t blocks_; 164 }; 165
