1 /* <!-- copyright */ 2 /* 3 * aria2 - The high speed download utility 4 * 5 * Copyright (C) 2006 Tatsuhiro Tsujikawa 6 * 7 * This program is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation; either version 2 of the License, or 10 * (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 20 * 21 * In addition, as a special exception, the copyright holders give 22 * permission to link the code of portions of this program with the 23 * OpenSSL library under certain conditions as described in each 24 * individual source file, and distribute linked combinations 25 * including the two. 26 * You must obey the GNU General Public License in all respects 27 * for all of the code used other than OpenSSL. If you modify 28 * file(s) with this exception, you may extend this exception to your 29 * version of the file(s), but you are not obligated to do so. If you 30 * do not wish to do so, delete this exception statement from your 31 * version. If you delete this exception statement from all source 32 * files in the program, then also delete it here. 33 */ 34 /* copyright --> */ 35 #ifndef D_BITFIELD_MAN_H 36 #define D_BITFIELD_MAN_H 37 38 #include "common.h" 39 40 #include <vector> 41 42 namespace aria2 { 43 44 class BitfieldMan { 45 private: 46 int64_t totalLength_; 47 int64_t cachedCompletedLength_; 48 int64_t cachedFilteredCompletedLength_; 49 int64_t cachedFilteredTotalLength_; 50 51 unsigned char* bitfield_; 52 unsigned char* useBitfield_; 53 unsigned char* filterBitfield_; 54 55 size_t bitfieldLength_; 56 size_t cachedNumMissingBlock_; 57 size_t cachedNumFilteredBlock_; 58 size_t blocks_; 59 60 int32_t blockLength_; 61 62 bool filterEnabled_; 63 64 bool setBitInternal(unsigned char* bitfield, size_t index, bool on); 65 bool setFilterBit(size_t index); 66 67 size_t getStartIndex(size_t index) const; 68 size_t getEndIndex(size_t index) const; 69 70 int64_t getCompletedLength(bool useFilter) const; 71 72 // If filterBitfield_ is 0, allocate bitfieldLength_ bytes to it and 73 // set 0 to all bytes. 74 void ensureFilterBitfield(); 75 76 public: 77 // [startIndex, endIndex) 78 struct Range { 79 size_t startIndex; 80 size_t endIndex; 81 Range(size_t startIndex = 0, size_t endIndex = 0); 82 size_t getSize() const; 83 size_t getMidIndex() const; 84 bool operator<(const Range& range) const; 85 bool operator==(const Range& range) const; 86 }; 87 88 public: 89 BitfieldMan(int32_t blockLength, int64_t totalLength); 90 BitfieldMan(const BitfieldMan& bitfieldMan); 91 ~BitfieldMan(); 92 93 BitfieldMan& operator=(const BitfieldMan& bitfieldMan); 94 getBlockLength()95 int32_t getBlockLength() const { return blockLength_; } 96 97 int32_t getLastBlockLength() const; 98 99 int32_t getBlockLength(size_t index) const; 100 getTotalLength()101 int64_t getTotalLength() const { return totalLength_; } 102 103 // Returns true iff there is a bit index which is set in bitfield_, 104 // but not set in this object. 105 // 106 // affected by filter 107 bool hasMissingPiece(const unsigned char* bitfield, size_t len) const; 108 109 // affected by filter 110 bool getFirstMissingUnusedIndex(size_t& index) const; 111 112 // Appends at most n missing unused index to out. This function 113 // doesn't delete existing elements in out. Returns the number of 114 // appended elements. 115 // 116 // affected by filter 117 size_t getFirstNMissingUnusedIndex(std::vector<size_t>& out, size_t n) const; 118 119 // Stores first missing bit index to index. Returns true if such bit 120 // index is found. Otherwise returns false. 121 // 122 // affected by filter 123 bool getFirstMissingIndex(size_t& index) const; 124 125 // Stores missing bit index to index. index is selected so that it 126 // divides longest missing bit subarray into 2 equally sized 127 // subarray. Set bits in ignoreBitfield are excluded. Returns true 128 // if such bit index is found. Otherwise returns false. 129 // 130 // affected by filter 131 bool getSparseMissingUnusedIndex(size_t& index, int32_t minSplitSize, 132 const unsigned char* ignoreBitfield, 133 size_t ignoreBitfieldLength) const; 134 135 // Stores missing bit index to index. This function first try to 136 // select smallest index starting offsetIndex in the order: 137 // offsetIndex, offsetIndex+base**1, offsetIndex+base**2, ... For 138 // each sequence [offsetIndex+base**i, offsetIndex+base**(i+1)) 139 // (first sequence is special case and it is [offsetIndex, 140 // offsetIndex+base)) test isBitSet() and isUseBitSet() from the 141 // beginning of the sequence. If isBitSet(x) == false is found 142 // first, select x as index. If isUseBit(x) == true is found first 143 // or isBitSet(x) == false is not found, then quit search and go to 144 // the next sequence(increment i). If no index found in the above 145 // algorithm, call getSparseMissingUnusedIndex() and return its 146 // result. 147 // 148 // affected by filter 149 bool getGeomMissingUnusedIndex(size_t& index, int32_t minSplitSize, 150 const unsigned char* ignoreBitfield, 151 size_t ignoreBitfieldLength, double base, 152 size_t offsetIndex) const; 153 154 // Stores missing bit index to index. This function selects smallest 155 // index of missing piece, considering minSplitSize. Set bits in 156 // ignoreBitfield are excluded. Returns true if such bit index is 157 // found. Otherwise returns false. 158 // 159 // affected by filter 160 bool getInorderMissingUnusedIndex(size_t& index, int32_t minSplitSize, 161 const unsigned char* ignoreBitfield, 162 size_t ignoreBitfieldLength) const; 163 164 // Just like getInorderMissingUnusedIndex() above, but limit the 165 // search area in [startIndex, endIndex). |endIndex| is normalized 166 // to min(|endIndex|, blocks_) 167 // 168 // affected by filter 169 bool getInorderMissingUnusedIndex(size_t& index, size_t startIndex, 170 size_t endIndex, int32_t minSplitSize, 171 const unsigned char* ignoreBitfield, 172 size_t ignoreBitfieldLength) const; 173 174 // affected by filter 175 bool getAllMissingIndexes(unsigned char* misbitfield, size_t mislen) const; 176 177 // affected by filter 178 bool getAllMissingIndexes(unsigned char* misbitfield, size_t mislen, 179 const unsigned char* bitfield, size_t len) const; 180 // affected by filter 181 bool getAllMissingUnusedIndexes(unsigned char* misbitfield, size_t mislen, 182 const unsigned char* bitfield, 183 size_t len) const; 184 // affected by filter 185 size_t countMissingBlock() const; 186 187 // affected by filter 188 size_t countMissingBlockNow() const; 189 190 bool setUseBit(size_t index); 191 bool unsetUseBit(size_t index); 192 193 bool setBit(size_t index); 194 bool unsetBit(size_t index); 195 196 bool isBitSet(size_t index) const; 197 bool isUseBitSet(size_t index) const; 198 199 // affected by filter 200 bool isFilteredAllBitSet() const; 201 202 bool isAllBitSet() const; 203 204 bool isAllFilterBitSet() const; 205 // Returns true if index bit is set in filterBitfield_. If 206 // filterBitfield_ is NULL, returns false. 207 bool isFilterBitSet(size_t index) const; 208 getBitfield()209 const unsigned char* getBitfield() const { return bitfield_; } 210 getBitfieldLength()211 size_t getBitfieldLength() const { return bitfieldLength_; } 212 213 // affected by filter countFilteredBlock()214 size_t countFilteredBlock() const { return cachedNumFilteredBlock_; } 215 countBlock()216 size_t countBlock() const { return blocks_; } 217 218 // affected by filter 219 size_t countFilteredBlockNow() const; 220 getMaxIndex()221 size_t getMaxIndex() const { return blocks_ - 1; } 222 223 void setBitfield(const unsigned char* bitfield, size_t bitfieldLength); 224 225 void clearAllBit(); 226 void setAllBit(); 227 228 void clearAllUseBit(); 229 void setAllUseBit(); 230 231 void addFilter(int64_t offset, int64_t length); 232 void removeFilter(int64_t offset, int64_t length); 233 // Add filter not in the range of [offset, offset+length) bytes 234 void addNotFilter(int64_t offset, int64_t length); 235 236 // Clears filter and disables filter 237 void clearFilter(); 238 239 void enableFilter(); 240 void disableFilter(); isFilterEnabled()241 bool isFilterEnabled() const { return filterEnabled_; } 242 243 // affected by filter getFilteredTotalLength()244 int64_t getFilteredTotalLength() const { return cachedFilteredTotalLength_; } 245 246 // affected by filter 247 int64_t getFilteredTotalLengthNow() const; 248 getCompletedLength()249 int64_t getCompletedLength() const { return cachedCompletedLength_; } 250 251 int64_t getCompletedLengthNow() const; 252 253 // affected by filter getFilteredCompletedLength()254 int64_t getFilteredCompletedLength() const 255 { 256 return cachedFilteredCompletedLength_; 257 } 258 259 // affected by filter 260 int64_t getFilteredCompletedLengthNow() const; 261 262 void updateCache(); 263 264 bool isBitRangeSet(size_t startIndex, size_t endIndex) const; 265 266 void unsetBitRange(size_t startIndex, size_t endIndex); 267 268 void setBitRange(size_t startIndex, size_t endIndex); 269 270 bool isBitSetOffsetRange(int64_t offset, int64_t length) const; 271 272 // Returns completed length in bytes in range [offset, 273 // offset+length). This function will not affected by filter. 274 int64_t getOffsetCompletedLength(int64_t offset, int64_t length) const; 275 276 int64_t getMissingUnusedLength(size_t startingIndex) const; 277 getFilterBitfield()278 const unsigned char* getFilterBitfield() const { return filterBitfield_; } 279 }; 280 281 } // namespace aria2 282 283 #endif // D_BITFIELD_MAN_H 284