summaryrefslogtreecommitdiff
path: root/src/BitfieldMan.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/BitfieldMan.cc')
-rw-r--r--src/BitfieldMan.cc817
1 files changed, 419 insertions, 398 deletions
diff --git a/src/BitfieldMan.cc b/src/BitfieldMan.cc
index 4432253d..0a47b1a8 100644
--- a/src/BitfieldMan.cc
+++ b/src/BitfieldMan.cc
@@ -45,23 +45,23 @@ using namespace aria2::expr;
namespace aria2 {
BitfieldMan::BitfieldMan(int32_t blockLength, int64_t totalLength)
- : totalLength_(totalLength),
- cachedCompletedLength_(0),
- cachedFilteredCompletedLength_(0),
- cachedFilteredTotalLength_(0),
- bitfield_(nullptr),
- useBitfield_(nullptr),
- filterBitfield_(nullptr),
- bitfieldLength_(0),
- cachedNumMissingBlock_(0),
- cachedNumFilteredBlock_(0),
- blocks_(0),
- blockLength_(blockLength),
- filterEnabled_(false)
-{
- if(blockLength_ > 0 && totalLength_ > 0) {
- blocks_ = (totalLength_+blockLength_-1)/blockLength_;
- bitfieldLength_ = blocks_/8+(blocks_%8 ? 1 : 0);
+ : totalLength_(totalLength),
+ cachedCompletedLength_(0),
+ cachedFilteredCompletedLength_(0),
+ cachedFilteredTotalLength_(0),
+ bitfield_(nullptr),
+ useBitfield_(nullptr),
+ filterBitfield_(nullptr),
+ bitfieldLength_(0),
+ cachedNumMissingBlock_(0),
+ cachedNumFilteredBlock_(0),
+ blocks_(0),
+ blockLength_(blockLength),
+ filterEnabled_(false)
+{
+ if (blockLength_ > 0 && totalLength_ > 0) {
+ blocks_ = (totalLength_ + blockLength_ - 1) / blockLength_;
+ bitfieldLength_ = blocks_ / 8 + (blocks_ % 8 ? 1 : 0);
bitfield_ = new unsigned char[bitfieldLength_];
useBitfield_ = new unsigned char[bitfieldLength_];
memset(bitfield_, 0, bitfieldLength_);
@@ -71,23 +71,23 @@ BitfieldMan::BitfieldMan(int32_t blockLength, int64_t totalLength)
}
BitfieldMan::BitfieldMan(const BitfieldMan& bitfieldMan)
- : totalLength_(bitfieldMan.totalLength_),
- cachedCompletedLength_(0),
- cachedFilteredCompletedLength_(0),
- cachedFilteredTotalLength_(0),
- bitfield_(new unsigned char[bitfieldMan.bitfieldLength_]),
- useBitfield_(new unsigned char[bitfieldMan.bitfieldLength_]),
- filterBitfield_(nullptr),
- bitfieldLength_(bitfieldMan.bitfieldLength_),
- cachedNumMissingBlock_(0),
- cachedNumFilteredBlock_(0),
- blocks_(bitfieldMan.blocks_),
- blockLength_(bitfieldMan.blockLength_),
- filterEnabled_(bitfieldMan.filterEnabled_)
+ : totalLength_(bitfieldMan.totalLength_),
+ cachedCompletedLength_(0),
+ cachedFilteredCompletedLength_(0),
+ cachedFilteredTotalLength_(0),
+ bitfield_(new unsigned char[bitfieldMan.bitfieldLength_]),
+ useBitfield_(new unsigned char[bitfieldMan.bitfieldLength_]),
+ filterBitfield_(nullptr),
+ bitfieldLength_(bitfieldMan.bitfieldLength_),
+ cachedNumMissingBlock_(0),
+ cachedNumFilteredBlock_(0),
+ blocks_(bitfieldMan.blocks_),
+ blockLength_(bitfieldMan.blockLength_),
+ filterEnabled_(bitfieldMan.filterEnabled_)
{
memcpy(bitfield_, bitfieldMan.bitfield_, bitfieldLength_);
memcpy(useBitfield_, bitfieldMan.useBitfield_, bitfieldLength_);
- if(filterEnabled_) {
+ if (filterEnabled_) {
filterBitfield_ = new unsigned char[bitfieldLength_];
memcpy(filterBitfield_, bitfieldMan.filterBitfield_, bitfieldLength_);
}
@@ -96,26 +96,27 @@ BitfieldMan::BitfieldMan(const BitfieldMan& bitfieldMan)
BitfieldMan& BitfieldMan::operator=(const BitfieldMan& bitfieldMan)
{
- if(this != &bitfieldMan) {
+ if (this != &bitfieldMan) {
totalLength_ = bitfieldMan.totalLength_;
blockLength_ = bitfieldMan.blockLength_;
blocks_ = bitfieldMan.blocks_;
bitfieldLength_ = bitfieldMan.bitfieldLength_;
filterEnabled_ = bitfieldMan.filterEnabled_;
- delete [] bitfield_;
+ delete[] bitfield_;
bitfield_ = new unsigned char[bitfieldLength_];
memcpy(bitfield_, bitfieldMan.bitfield_, bitfieldLength_);
- delete [] useBitfield_;
+ delete[] useBitfield_;
useBitfield_ = new unsigned char[bitfieldLength_];
memcpy(useBitfield_, bitfieldMan.useBitfield_, bitfieldLength_);
- delete [] filterBitfield_;
- if(filterEnabled_) {
+ delete[] filterBitfield_;
+ if (filterEnabled_) {
filterBitfield_ = new unsigned char[bitfieldLength_];
memcpy(filterBitfield_, bitfieldMan.filterBitfield_, bitfieldLength_);
- } else {
+ }
+ else {
filterBitfield_ = nullptr;
}
@@ -124,41 +125,44 @@ BitfieldMan& BitfieldMan::operator=(const BitfieldMan& bitfieldMan)
return *this;
}
-BitfieldMan::~BitfieldMan() {
- delete [] bitfield_;
- delete [] useBitfield_;
- delete [] filterBitfield_;
+BitfieldMan::~BitfieldMan()
+{
+ delete[] bitfield_;
+ delete[] useBitfield_;
+ delete[] filterBitfield_;
}
int32_t BitfieldMan::getLastBlockLength() const
{
- return totalLength_-blockLength_*(blocks_-1);
+ return totalLength_ - blockLength_ * (blocks_ - 1);
}
int32_t BitfieldMan::getBlockLength(size_t index) const
{
- if(index == blocks_-1) {
+ if (index == blocks_ - 1) {
return getLastBlockLength();
- } else if(index < blocks_-1) {
+ }
+ else if (index < blocks_ - 1) {
return getBlockLength();
- } else {
+ }
+ else {
return 0;
}
}
-bool BitfieldMan::hasMissingPiece
-(const unsigned char* peerBitfield, size_t length) const
+bool BitfieldMan::hasMissingPiece(const unsigned char* peerBitfield,
+ size_t length) const
{
- if(bitfieldLength_ != length) {
+ if (bitfieldLength_ != length) {
return false;
}
bool retval = false;
- for(size_t i = 0; i < bitfieldLength_; ++i) {
+ for (size_t i = 0; i < bitfieldLength_; ++i) {
unsigned char temp = peerBitfield[i] & ~bitfield_[i];
- if(filterEnabled_) {
+ if (filterEnabled_) {
temp &= filterBitfield_[i];
}
- if(temp&0xffu) {
+ if (temp & 0xffu) {
retval = true;
break;
}
@@ -168,58 +172,66 @@ bool BitfieldMan::hasMissingPiece
bool BitfieldMan::getFirstMissingUnusedIndex(size_t& index) const
{
- if(filterEnabled_) {
- return bitfield::getFirstSetBitIndex
- (index, ~array(bitfield_)&~array(useBitfield_)&array(filterBitfield_),
- blocks_);
- } else {
- return bitfield::getFirstSetBitIndex
- (index, ~array(bitfield_)&~array(useBitfield_), blocks_);
+ if (filterEnabled_) {
+ return bitfield::getFirstSetBitIndex(index, ~array(bitfield_) &
+ ~array(useBitfield_) &
+ array(filterBitfield_),
+ blocks_);
+ }
+ else {
+ return bitfield::getFirstSetBitIndex(
+ index, ~array(bitfield_) & ~array(useBitfield_), blocks_);
}
}
-size_t BitfieldMan::getFirstNMissingUnusedIndex
-(std::vector<size_t>& out, size_t n) const
+size_t BitfieldMan::getFirstNMissingUnusedIndex(std::vector<size_t>& out,
+ size_t n) const
{
- if(filterEnabled_) {
- return bitfield::getFirstNSetBitIndex
- (std::back_inserter(out), n,
- ~array(bitfield_)&~array(useBitfield_)&array(filterBitfield_), blocks_);
- } else {
- return bitfield::getFirstNSetBitIndex
- (std::back_inserter(out), n,
- ~array(bitfield_)&~array(useBitfield_), blocks_);
+ if (filterEnabled_) {
+ return bitfield::getFirstNSetBitIndex(
+ std::back_inserter(out), n,
+ ~array(bitfield_) & ~array(useBitfield_) & array(filterBitfield_),
+ blocks_);
+ }
+ else {
+ return bitfield::getFirstNSetBitIndex(
+ std::back_inserter(out), n, ~array(bitfield_) & ~array(useBitfield_),
+ blocks_);
}
}
bool BitfieldMan::getFirstMissingIndex(size_t& index) const
{
- if(filterEnabled_) {
- return bitfield::getFirstSetBitIndex
- (index, ~array(bitfield_)&array(filterBitfield_), blocks_);
- } else {
+ if (filterEnabled_) {
+ return bitfield::getFirstSetBitIndex(
+ index, ~array(bitfield_) & array(filterBitfield_), blocks_);
+ }
+ else {
return bitfield::getFirstSetBitIndex(index, ~array(bitfield_), blocks_);
}
}
namespace {
-template<typename Array>
-size_t getStartIndex(size_t index, const Array& bitfield, size_t blocks) {
- while(index < blocks && bitfield::test(bitfield, blocks, index)) {
+template <typename Array>
+size_t getStartIndex(size_t index, const Array& bitfield, size_t blocks)
+{
+ while (index < blocks && bitfield::test(bitfield, blocks, index)) {
++index;
}
- if(blocks <= index) {
+ if (blocks <= index) {
return blocks;
- } else {
+ }
+ else {
return index;
}
}
} // namespace
namespace {
-template<typename Array>
-size_t getEndIndex(size_t index, const Array& bitfield, size_t blocks) {
- while(index < blocks && !bitfield::test(bitfield, blocks, index)) {
+template <typename Array>
+size_t getEndIndex(size_t index, const Array& bitfield, size_t blocks)
+{
+ while (index < blocks && !bitfield::test(bitfield, blocks, index)) {
++index;
}
return index;
@@ -227,194 +239,180 @@ size_t getEndIndex(size_t index, const Array& bitfield, size_t blocks) {
} // namespace
namespace {
-template<typename Array>
-bool getSparseMissingUnusedIndex
-(size_t& index,
- int32_t minSplitSize,
- const Array& bitfield,
- const unsigned char* useBitfield,
- int32_t blockLength,
- size_t blocks)
+template <typename Array>
+bool getSparseMissingUnusedIndex(size_t& index, int32_t minSplitSize,
+ const Array& bitfield,
+ const unsigned char* useBitfield,
+ int32_t blockLength, size_t blocks)
{
BitfieldMan::Range maxRange;
BitfieldMan::Range currentRange;
size_t nextIndex = 0;
- while(nextIndex < blocks) {
- currentRange.startIndex =
- getStartIndex(nextIndex, bitfield, blocks);
- if(currentRange.startIndex == blocks) {
+ while (nextIndex < blocks) {
+ currentRange.startIndex = getStartIndex(nextIndex, bitfield, blocks);
+ if (currentRange.startIndex == blocks) {
break;
}
currentRange.endIndex =
- getEndIndex(currentRange.startIndex, bitfield, blocks);
+ getEndIndex(currentRange.startIndex, bitfield, blocks);
- if(currentRange.startIndex > 0) {
- if(bitfield::test(useBitfield, blocks, currentRange.startIndex-1)) {
+ if (currentRange.startIndex > 0) {
+ if (bitfield::test(useBitfield, blocks, currentRange.startIndex - 1)) {
currentRange.startIndex = currentRange.getMidIndex();
}
}
// If range is equal, choose a range where its startIndex-1 is
// set.
- if(maxRange < currentRange ||
- (maxRange == currentRange &&
- maxRange.startIndex > 0 && currentRange.startIndex > 0 &&
- (!bitfield::test(bitfield, blocks, maxRange.startIndex-1) ||
- bitfield::test(useBitfield, blocks, maxRange.startIndex-1))
- &&
- bitfield::test(bitfield, blocks, currentRange.startIndex-1) &&
- !bitfield::test(useBitfield, blocks, currentRange.startIndex-1))) {
+ if (maxRange < currentRange ||
+ (maxRange == currentRange && maxRange.startIndex > 0 &&
+ currentRange.startIndex > 0 &&
+ (!bitfield::test(bitfield, blocks, maxRange.startIndex - 1) ||
+ bitfield::test(useBitfield, blocks, maxRange.startIndex - 1)) &&
+ bitfield::test(bitfield, blocks, currentRange.startIndex - 1) &&
+ !bitfield::test(useBitfield, blocks, currentRange.startIndex - 1))) {
maxRange = currentRange;
}
nextIndex = currentRange.endIndex;
-
}
- if(maxRange.getSize()) {
- if(maxRange.startIndex == 0) {
+ if (maxRange.getSize()) {
+ if (maxRange.startIndex == 0) {
index = 0;
return true;
- } else {
- if((!bitfield::test(useBitfield, blocks, maxRange.startIndex-1) &&
- bitfield::test(bitfield, blocks, maxRange.startIndex-1)) ||
- (static_cast<int64_t>(maxRange.endIndex-maxRange.startIndex)*
- blockLength >= minSplitSize)) {
+ }
+ else {
+ if ((!bitfield::test(useBitfield, blocks, maxRange.startIndex - 1) &&
+ bitfield::test(bitfield, blocks, maxRange.startIndex - 1)) ||
+ (static_cast<int64_t>(maxRange.endIndex - maxRange.startIndex) *
+ blockLength >=
+ minSplitSize)) {
index = maxRange.startIndex;
return true;
- } else {
+ }
+ else {
return false;
}
}
- } else {
+ }
+ else {
return false;
}
}
} // namespace
-bool BitfieldMan::getSparseMissingUnusedIndex
-(size_t& index,
- int32_t minSplitSize,
- const unsigned char* ignoreBitfield,
- size_t ignoreBitfieldLength) const
+bool BitfieldMan::getSparseMissingUnusedIndex(
+ size_t& index, int32_t minSplitSize, const unsigned char* ignoreBitfield,
+ size_t ignoreBitfieldLength) const
{
- if(filterEnabled_) {
- return aria2::getSparseMissingUnusedIndex
- (index, minSplitSize,
- array(ignoreBitfield)|~array(filterBitfield_)|
- array(bitfield_)|array(useBitfield_),
- useBitfield_, blockLength_, blocks_);
- } else {
- return aria2::getSparseMissingUnusedIndex
- (index, minSplitSize,
- array(ignoreBitfield)|array(bitfield_)|array(useBitfield_),
- useBitfield_, blockLength_, blocks_);
+ if (filterEnabled_) {
+ return aria2::getSparseMissingUnusedIndex(
+ index, minSplitSize, array(ignoreBitfield) | ~array(filterBitfield_) |
+ array(bitfield_) | array(useBitfield_),
+ useBitfield_, blockLength_, blocks_);
+ }
+ else {
+ return aria2::getSparseMissingUnusedIndex(
+ index, minSplitSize,
+ array(ignoreBitfield) | array(bitfield_) | array(useBitfield_),
+ useBitfield_, blockLength_, blocks_);
}
}
namespace {
-template<typename Array>
-bool getGeomMissingUnusedIndex
-(size_t& index,
- int32_t minSplitSize,
- const Array& bitfield,
- const unsigned char* useBitfield,
- int32_t blockLength,
- size_t blocks,
- double base,
- size_t offsetIndex)
+template <typename Array>
+bool getGeomMissingUnusedIndex(size_t& index, int32_t minSplitSize,
+ const Array& bitfield,
+ const unsigned char* useBitfield,
+ int32_t blockLength, size_t blocks, double base,
+ size_t offsetIndex)
{
double start = 0;
double end = 1;
- while(start+offsetIndex < blocks) {
+ while (start + offsetIndex < blocks) {
index = blocks;
- for(size_t i = start+offsetIndex,
- eoi = std::min(blocks, static_cast<size_t>(end+offsetIndex));
- i < eoi; ++i) {
- if(bitfield::test(useBitfield, blocks, i)) {
+ for (size_t i = start + offsetIndex,
+ eoi = std::min(blocks, static_cast<size_t>(end + offsetIndex));
+ i < eoi; ++i) {
+ if (bitfield::test(useBitfield, blocks, i)) {
break;
- } else if(!bitfield::test(bitfield, blocks, i)) {
+ }
+ else if (!bitfield::test(bitfield, blocks, i)) {
index = i;
break;
}
}
- if(index < blocks) {
+ if (index < blocks) {
return true;
- } else {
+ }
+ else {
start = end;
end *= base;
}
}
- return getSparseMissingUnusedIndex(index, minSplitSize,
- bitfield, useBitfield,
+ return getSparseMissingUnusedIndex(index, minSplitSize, bitfield, useBitfield,
blockLength, blocks);
}
} // namespace
-bool BitfieldMan::getGeomMissingUnusedIndex
-(size_t& index,
- int32_t minSplitSize,
- const unsigned char* ignoreBitfield,
- size_t ignoreBitfieldLength,
- double base,
- size_t offsetIndex) const
-{
- if(filterEnabled_) {
- return aria2::getGeomMissingUnusedIndex
- (index, minSplitSize,
- array(ignoreBitfield)|~array(filterBitfield_)|
- array(bitfield_)|array(useBitfield_),
- useBitfield_, blockLength_, blocks_,
- base, offsetIndex);
- } else {
- return aria2::getGeomMissingUnusedIndex
- (index, minSplitSize,
- array(ignoreBitfield)|array(bitfield_)|array(useBitfield_),
- useBitfield_, blockLength_, blocks_,
- base, offsetIndex);
+bool BitfieldMan::getGeomMissingUnusedIndex(size_t& index, int32_t minSplitSize,
+ const unsigned char* ignoreBitfield,
+ size_t ignoreBitfieldLength,
+ double base,
+ size_t offsetIndex) const
+{
+ if (filterEnabled_) {
+ return aria2::getGeomMissingUnusedIndex(
+ index, minSplitSize, array(ignoreBitfield) | ~array(filterBitfield_) |
+ array(bitfield_) | array(useBitfield_),
+ useBitfield_, blockLength_, blocks_, base, offsetIndex);
+ }
+ else {
+ return aria2::getGeomMissingUnusedIndex(
+ index, minSplitSize,
+ array(ignoreBitfield) | array(bitfield_) | array(useBitfield_),
+ useBitfield_, blockLength_, blocks_, base, offsetIndex);
}
}
namespace {
-template<typename Array>
-bool getInorderMissingUnusedIndex
-(size_t& index,
- size_t startIndex,
- size_t lastIndex,
- int32_t minSplitSize,
- const Array& bitfield,
- const unsigned char* useBitfield,
- int32_t blockLength,
- size_t blocks)
+template <typename Array>
+bool getInorderMissingUnusedIndex(size_t& index, size_t startIndex,
+ size_t lastIndex, int32_t minSplitSize,
+ const Array& bitfield,
+ const unsigned char* useBitfield,
+ int32_t blockLength, size_t blocks)
{
// We always return first piece if it is available.
- if(!bitfield::test(bitfield, blocks, startIndex) &&
- !bitfield::test(useBitfield, blocks, startIndex)) {
+ if (!bitfield::test(bitfield, blocks, startIndex) &&
+ !bitfield::test(useBitfield, blocks, startIndex)) {
index = startIndex;
return true;
}
- for(size_t i = startIndex + 1; i < lastIndex;) {
- if(!bitfield::test(bitfield, blocks, i) &&
- !bitfield::test(useBitfield, blocks, i)) {
+ for (size_t i = startIndex + 1; i < lastIndex;) {
+ if (!bitfield::test(bitfield, blocks, i) &&
+ !bitfield::test(useBitfield, blocks, i)) {
// If previous piece has already been retrieved, we can download
// from this index.
- if(!bitfield::test(useBitfield, blocks, i-1) &&
- bitfield::test(bitfield, blocks, i-1)) {
+ if (!bitfield::test(useBitfield, blocks, i - 1) &&
+ bitfield::test(bitfield, blocks, i - 1)) {
index = i;
return true;
}
// Check free space of minSplitSize. When checking this, we use
// blocks instead of lastIndex.
size_t j;
- for(j = i; j < blocks; ++j) {
- if(bitfield::test(bitfield, blocks, j) ||
- bitfield::test(useBitfield, blocks, j)) {
+ for (j = i; j < blocks; ++j) {
+ if (bitfield::test(bitfield, blocks, j) ||
+ bitfield::test(useBitfield, blocks, j)) {
break;
}
- if(static_cast<int64_t>(j-i+1)*blockLength >= minSplitSize) {
+ if (static_cast<int64_t>(j - i + 1) * blockLength >= minSplitSize) {
index = j;
return true;
}
}
- i = j+1;
- } else {
+ i = j + 1;
+ }
+ else {
++i;
}
}
@@ -422,73 +420,70 @@ bool getInorderMissingUnusedIndex
}
} // namespace
-bool BitfieldMan::getInorderMissingUnusedIndex
-(size_t& index,
- int32_t minSplitSize,
- const unsigned char* ignoreBitfield,
- size_t ignoreBitfieldLength) const
-{
- if(filterEnabled_) {
- return aria2::getInorderMissingUnusedIndex
- (index, 0, blocks_, minSplitSize,
- array(ignoreBitfield)|~array(filterBitfield_)|
- array(bitfield_)|array(useBitfield_),
- useBitfield_, blockLength_, blocks_);
- } else {
- return aria2::getInorderMissingUnusedIndex
- (index, 0, blocks_, minSplitSize,
- array(ignoreBitfield)|array(bitfield_)|array(useBitfield_),
- useBitfield_, blockLength_, blocks_);
- }
-}
-
-bool BitfieldMan::getInorderMissingUnusedIndex
-(size_t& index,
- size_t startIndex,
- size_t endIndex,
- int32_t minSplitSize,
- const unsigned char* ignoreBitfield,
- size_t ignoreBitfieldLength) const
+bool BitfieldMan::getInorderMissingUnusedIndex(
+ size_t& index, int32_t minSplitSize, const unsigned char* ignoreBitfield,
+ size_t ignoreBitfieldLength) const
+{
+ if (filterEnabled_) {
+ return aria2::getInorderMissingUnusedIndex(
+ index, 0, blocks_, minSplitSize,
+ array(ignoreBitfield) | ~array(filterBitfield_) | array(bitfield_) |
+ array(useBitfield_),
+ useBitfield_, blockLength_, blocks_);
+ }
+ else {
+ return aria2::getInorderMissingUnusedIndex(
+ index, 0, blocks_, minSplitSize,
+ array(ignoreBitfield) | array(bitfield_) | array(useBitfield_),
+ useBitfield_, blockLength_, blocks_);
+ }
+}
+
+bool BitfieldMan::getInorderMissingUnusedIndex(
+ size_t& index, size_t startIndex, size_t endIndex, int32_t minSplitSize,
+ const unsigned char* ignoreBitfield, size_t ignoreBitfieldLength) const
{
endIndex = std::min(endIndex, blocks_);
- if(filterEnabled_) {
- return aria2::getInorderMissingUnusedIndex
- (index, startIndex, endIndex, minSplitSize,
- array(ignoreBitfield)|~array(filterBitfield_)|
- array(bitfield_)|array(useBitfield_),
- useBitfield_, blockLength_, blocks_);
- } else {
- return aria2::getInorderMissingUnusedIndex
- (index, startIndex, endIndex, minSplitSize,
- array(ignoreBitfield)|array(bitfield_)|array(useBitfield_),
- useBitfield_, blockLength_, blocks_);
+ if (filterEnabled_) {
+ return aria2::getInorderMissingUnusedIndex(
+ index, startIndex, endIndex, minSplitSize,
+ array(ignoreBitfield) | ~array(filterBitfield_) | array(bitfield_) |
+ array(useBitfield_),
+ useBitfield_, blockLength_, blocks_);
+ }
+ else {
+ return aria2::getInorderMissingUnusedIndex(
+ index, startIndex, endIndex, minSplitSize,
+ array(ignoreBitfield) | array(bitfield_) | array(useBitfield_),
+ useBitfield_, blockLength_, blocks_);
}
}
namespace {
-template<typename Array>
+template <typename Array>
bool copyBitfield(unsigned char* dst, const Array& src, size_t blocks)
{
unsigned char bits = 0;
- size_t len = (blocks+7)/8;
- for(size_t i = 0; i < len-1; ++i) {
+ size_t len = (blocks + 7) / 8;
+ for (size_t i = 0; i < len - 1; ++i) {
dst[i] = src[i];
bits |= dst[i];
}
- dst[len-1] = src[len-1]&bitfield::lastByteMask(blocks);
- bits |= dst[len-1];
+ dst[len - 1] = src[len - 1] & bitfield::lastByteMask(blocks);
+ bits |= dst[len - 1];
return bits != 0;
}
} // namespace
-bool BitfieldMan::getAllMissingIndexes(unsigned char* misbitfield, size_t len)
- const
+bool BitfieldMan::getAllMissingIndexes(unsigned char* misbitfield,
+ size_t len) const
{
assert(len == bitfieldLength_);
- if(filterEnabled_) {
- return copyBitfield
- (misbitfield, ~array(bitfield_)&array(filterBitfield_), blocks_);
- } else {
+ if (filterEnabled_) {
+ return copyBitfield(misbitfield, ~array(bitfield_) & array(filterBitfield_),
+ blocks_);
+ }
+ else {
return copyBitfield(misbitfield, ~array(bitfield_), blocks_);
}
}
@@ -498,18 +493,17 @@ bool BitfieldMan::getAllMissingIndexes(unsigned char* misbitfield, size_t len,
size_t peerBitfieldLength) const
{
assert(len == bitfieldLength_);
- if(bitfieldLength_ != peerBitfieldLength) {
+ if (bitfieldLength_ != peerBitfieldLength) {
return false;
}
- if(filterEnabled_) {
- return copyBitfield
- (misbitfield,
- ~array(bitfield_)&array(peerBitfield)&array(filterBitfield_),
- blocks_);
- } else {
- return copyBitfield
- (misbitfield, ~array(bitfield_)&array(peerBitfield),
- blocks_);
+ if (filterEnabled_) {
+ return copyBitfield(misbitfield, ~array(bitfield_) & array(peerBitfield) &
+ array(filterBitfield_),
+ blocks_);
+ }
+ else {
+ return copyBitfield(misbitfield, ~array(bitfield_) & array(peerBitfield),
+ blocks_);
}
}
@@ -519,102 +513,112 @@ bool BitfieldMan::getAllMissingUnusedIndexes(unsigned char* misbitfield,
size_t peerBitfieldLength) const
{
assert(len == bitfieldLength_);
- if(bitfieldLength_ != peerBitfieldLength) {
+ if (bitfieldLength_ != peerBitfieldLength) {
return false;
}
- if(filterEnabled_) {
- return copyBitfield
- (misbitfield,
- ~array(bitfield_)&~array(useBitfield_)&array(peerBitfield)&
- array(filterBitfield_),
- blocks_);
- } else {
- return copyBitfield
- (misbitfield,
- ~array(bitfield_)&~array(useBitfield_)&array(peerBitfield),
- blocks_);
+ if (filterEnabled_) {
+ return copyBitfield(misbitfield,
+ ~array(bitfield_) & ~array(useBitfield_) &
+ array(peerBitfield) & array(filterBitfield_),
+ blocks_);
+ }
+ else {
+ return copyBitfield(misbitfield, ~array(bitfield_) & ~array(useBitfield_) &
+ array(peerBitfield),
+ blocks_);
}
}
-size_t BitfieldMan::countMissingBlock() const {
- return cachedNumMissingBlock_;
-}
+size_t BitfieldMan::countMissingBlock() const { return cachedNumMissingBlock_; }
-size_t BitfieldMan::countMissingBlockNow() const {
- if(filterEnabled_) {
+size_t BitfieldMan::countMissingBlockNow() const
+{
+ if (filterEnabled_) {
return bitfield::countSetBit(filterBitfield_, blocks_) -
- bitfield::countSetBitSlow(array(bitfield_)&array(filterBitfield_),
- blocks_);
- } else {
- return blocks_-bitfield::countSetBit(bitfield_, blocks_);
+ bitfield::countSetBitSlow(array(bitfield_) & array(filterBitfield_),
+ blocks_);
+ }
+ else {
+ return blocks_ - bitfield::countSetBit(bitfield_, blocks_);
}
}
-size_t BitfieldMan::countFilteredBlockNow() const {
- if(filterEnabled_) {
+size_t BitfieldMan::countFilteredBlockNow() const
+{
+ if (filterEnabled_) {
return bitfield::countSetBit(filterBitfield_, blocks_);
- } else {
+ }
+ else {
return 0;
}
}
-bool BitfieldMan::setBitInternal(unsigned char* bitfield, size_t index, bool on) {
- if(blocks_ <= index) { return false; }
- unsigned char mask = 128 >> (index%8);
- if(on) {
- bitfield[index/8] |= mask;
- } else {
- bitfield[index/8] &= ~mask;
+bool BitfieldMan::setBitInternal(unsigned char* bitfield, size_t index, bool on)
+{
+ if (blocks_ <= index) {
+ return false;
+ }
+ unsigned char mask = 128 >> (index % 8);
+ if (on) {
+ bitfield[index / 8] |= mask;
+ }
+ else {
+ bitfield[index / 8] &= ~mask;
}
return true;
}
-bool BitfieldMan::setUseBit(size_t index) {
+bool BitfieldMan::setUseBit(size_t index)
+{
return setBitInternal(useBitfield_, index, true);
}
-bool BitfieldMan::unsetUseBit(size_t index) {
+bool BitfieldMan::unsetUseBit(size_t index)
+{
return setBitInternal(useBitfield_, index, false);
}
-bool BitfieldMan::setBit(size_t index) {
+bool BitfieldMan::setBit(size_t index)
+{
bool b = setBitInternal(bitfield_, index, true);
updateCache();
return b;
}
-bool BitfieldMan::unsetBit(size_t index) {
+bool BitfieldMan::unsetBit(size_t index)
+{
bool b = setBitInternal(bitfield_, index, false);
updateCache();
return b;
}
-bool BitfieldMan::isFilteredAllBitSet() const {
- if(filterEnabled_) {
- for(size_t i = 0; i < bitfieldLength_; ++i) {
- if((bitfield_[i]&filterBitfield_[i]) != filterBitfield_[i]) {
+bool BitfieldMan::isFilteredAllBitSet() const
+{
+ if (filterEnabled_) {
+ for (size_t i = 0; i < bitfieldLength_; ++i) {
+ if ((bitfield_[i] & filterBitfield_[i]) != filterBitfield_[i]) {
return false;
}
}
return true;
- } else {
+ }
+ else {
return isAllBitSet();
}
}
namespace {
-bool testAllBitSet
-(const unsigned char* bitfield, size_t length, size_t blocks)
+bool testAllBitSet(const unsigned char* bitfield, size_t length, size_t blocks)
{
- if(length == 0) {
+ if (length == 0) {
return true;
}
- for(size_t i = 0; i < length-1; ++i) {
- if(bitfield[i] != 0xffu) {
+ for (size_t i = 0; i < length - 1; ++i) {
+ if (bitfield[i] != 0xffu) {
return false;
}
}
- return bitfield[length-1] == bitfield::lastByteMask(blocks);
+ return bitfield[length - 1] == bitfield::lastByteMask(blocks);
}
} // namespace
@@ -625,16 +629,18 @@ bool BitfieldMan::isAllBitSet() const
bool BitfieldMan::isAllFilterBitSet() const
{
- if(!filterBitfield_) {
+ if (!filterBitfield_) {
return false;
}
return testAllBitSet(filterBitfield_, bitfieldLength_, blocks_);
}
-bool BitfieldMan::isFilterBitSet(size_t index) const {
- if(filterBitfield_) {
+bool BitfieldMan::isFilterBitSet(size_t index) const
+{
+ if (filterBitfield_) {
return bitfield::test(filterBitfield_, blocks_, index);
- } else {
+ }
+ else {
return false;
}
}
@@ -649,8 +655,10 @@ bool BitfieldMan::isUseBitSet(size_t index) const
return bitfield::test(useBitfield_, blocks_, index);
}
-void BitfieldMan::setBitfield(const unsigned char* bitfield, size_t bitfieldLength) {
- if(bitfieldLength_ != bitfieldLength) {
+void BitfieldMan::setBitfield(const unsigned char* bitfield,
+ size_t bitfieldLength)
+{
+ if (bitfieldLength_ != bitfieldLength) {
return;
}
memcpy(bitfield_, bitfield, bitfieldLength_);
@@ -658,59 +666,66 @@ void BitfieldMan::setBitfield(const unsigned char* bitfield, size_t bitfieldLeng
updateCache();
}
-void BitfieldMan::clearAllBit() {
+void BitfieldMan::clearAllBit()
+{
memset(bitfield_, 0, bitfieldLength_);
updateCache();
}
-void BitfieldMan::setAllBit() {
- for(size_t i = 0; i < blocks_; ++i) {
+void BitfieldMan::setAllBit()
+{
+ for (size_t i = 0; i < blocks_; ++i) {
setBitInternal(bitfield_, i, true);
}
updateCache();
}
-void BitfieldMan::clearAllUseBit() {
+void BitfieldMan::clearAllUseBit()
+{
memset(useBitfield_, 0, bitfieldLength_);
updateCache();
}
-void BitfieldMan::setAllUseBit() {
- for(size_t i = 0; i < blocks_; ++i) {
+void BitfieldMan::setAllUseBit()
+{
+ for (size_t i = 0; i < blocks_; ++i) {
setBitInternal(useBitfield_, i, true);
}
}
-bool BitfieldMan::setFilterBit(size_t index) {
+bool BitfieldMan::setFilterBit(size_t index)
+{
return setBitInternal(filterBitfield_, index, true);
}
void BitfieldMan::ensureFilterBitfield()
{
- if(!filterBitfield_) {
+ if (!filterBitfield_) {
filterBitfield_ = new unsigned char[bitfieldLength_];
memset(filterBitfield_, 0, bitfieldLength_);
}
}
-void BitfieldMan::addFilter(int64_t offset, int64_t length) {
+void BitfieldMan::addFilter(int64_t offset, int64_t length)
+{
ensureFilterBitfield();
- if(length > 0) {
- size_t startBlock = offset/blockLength_;
- size_t endBlock = (offset+length-1)/blockLength_;
- for(size_t i = startBlock; i <= endBlock && i < blocks_; i++) {
+ if (length > 0) {
+ size_t startBlock = offset / blockLength_;
+ size_t endBlock = (offset + length - 1) / blockLength_;
+ for (size_t i = startBlock; i <= endBlock && i < blocks_; i++) {
setFilterBit(i);
}
}
updateCache();
}
-void BitfieldMan::removeFilter(int64_t offset, int64_t length) {
+void BitfieldMan::removeFilter(int64_t offset, int64_t length)
+{
ensureFilterBitfield();
- if(length > 0) {
- size_t startBlock = offset/blockLength_;
- size_t endBlock = (offset+length-1)/blockLength_;
- for(size_t i = startBlock; i <= endBlock && i < blocks_; i++) {
+ if (length > 0) {
+ size_t startBlock = offset / blockLength_;
+ size_t endBlock = (offset + length - 1) / blockLength_;
+ for (size_t i = startBlock; i <= endBlock && i < blocks_; i++) {
setBitInternal(filterBitfield_, i, false);
}
}
@@ -720,96 +735,106 @@ void BitfieldMan::removeFilter(int64_t offset, int64_t length) {
void BitfieldMan::addNotFilter(int64_t offset, int64_t length)
{
ensureFilterBitfield();
- if(length > 0 && blocks_ > 0) {
- size_t startBlock = offset/blockLength_;
- if(blocks_ <= startBlock) {
+ if (length > 0 && blocks_ > 0) {
+ size_t startBlock = offset / blockLength_;
+ if (blocks_ <= startBlock) {
startBlock = blocks_;
}
- size_t endBlock = (offset+length-1)/blockLength_;
- for(size_t i = 0; i < startBlock; ++i) {
+ size_t endBlock = (offset + length - 1) / blockLength_;
+ for (size_t i = 0; i < startBlock; ++i) {
setFilterBit(i);
}
- for(size_t i = endBlock+1; i < blocks_; ++i) {
+ for (size_t i = endBlock + 1; i < blocks_; ++i) {
setFilterBit(i);
}
}
updateCache();
}
-void BitfieldMan::enableFilter() {
+void BitfieldMan::enableFilter()
+{
ensureFilterBitfield();
filterEnabled_ = true;
updateCache();
}
-void BitfieldMan::disableFilter() {
+void BitfieldMan::disableFilter()
+{
filterEnabled_ = false;
updateCache();
}
-void BitfieldMan::clearFilter() {
- if(filterBitfield_) {
- delete [] filterBitfield_;
+void BitfieldMan::clearFilter()
+{
+ if (filterBitfield_) {
+ delete[] filterBitfield_;
filterBitfield_ = nullptr;
}
filterEnabled_ = false;
updateCache();
}
-int64_t BitfieldMan::getFilteredTotalLengthNow() const {
- if(!filterBitfield_) {
+int64_t BitfieldMan::getFilteredTotalLengthNow() const
+{
+ if (!filterBitfield_) {
return 0;
}
size_t filteredBlocks = bitfield::countSetBit(filterBitfield_, blocks_);
- if(filteredBlocks == 0) {
+ if (filteredBlocks == 0) {
return 0;
}
- if(bitfield::test(filterBitfield_, blocks_, blocks_-1)) {
- return ((int64_t)filteredBlocks-1)*blockLength_+getLastBlockLength();
- } else {
- return ((int64_t)filteredBlocks)*blockLength_;
+ if (bitfield::test(filterBitfield_, blocks_, blocks_ - 1)) {
+ return ((int64_t)filteredBlocks - 1) * blockLength_ + getLastBlockLength();
+ }
+ else {
+ return ((int64_t)filteredBlocks) * blockLength_;
}
}
namespace {
-template<typename Array, typename CountFun>
-int64_t computeCompletedLength(const Array& bitfield,
- const BitfieldMan* btman,
+template <typename Array, typename CountFun>
+int64_t computeCompletedLength(const Array& bitfield, const BitfieldMan* btman,
CountFun cntfun)
{
size_t nbits = btman->countBlock();
size_t completedBlocks = cntfun(bitfield, nbits);
int64_t completedLength = 0;
- if(completedBlocks == 0) {
+ if (completedBlocks == 0) {
completedLength = 0;
- } else {
- if(bitfield::test(bitfield, nbits, nbits - 1)) {
- completedLength = ((int64_t)completedBlocks-1)*btman->getBlockLength() +
- btman->getLastBlockLength();
- } else {
- completedLength = ((int64_t)completedBlocks)*btman->getBlockLength();
+ }
+ else {
+ if (bitfield::test(bitfield, nbits, nbits - 1)) {
+ completedLength =
+ ((int64_t)completedBlocks - 1) * btman->getBlockLength() +
+ btman->getLastBlockLength();
+ }
+ else {
+ completedLength = ((int64_t)completedBlocks) * btman->getBlockLength();
}
}
return completedLength;
}
} // namespace
-int64_t BitfieldMan::getCompletedLength(bool useFilter) const {
- if(useFilter && filterEnabled_) {
- auto arr = array(bitfield_)&array(filterBitfield_);
- return computeCompletedLength(arr,
- this,
+int64_t BitfieldMan::getCompletedLength(bool useFilter) const
+{
+ if (useFilter && filterEnabled_) {
+ auto arr = array(bitfield_) & array(filterBitfield_);
+ return computeCompletedLength(arr, this,
&bitfield::countSetBitSlow<decltype(arr)>);
- } else {
+ }
+ else {
return computeCompletedLength(bitfield_, this, &bitfield::countSetBit);
}
}
-int64_t BitfieldMan::getCompletedLengthNow() const {
+int64_t BitfieldMan::getCompletedLengthNow() const
+{
return getCompletedLength(false);
}
-int64_t BitfieldMan::getFilteredCompletedLengthNow() const {
+int64_t BitfieldMan::getFilteredCompletedLengthNow() const
+{
return getCompletedLength(true);
}
@@ -824,8 +849,8 @@ void BitfieldMan::updateCache()
bool BitfieldMan::isBitRangeSet(size_t startIndex, size_t endIndex) const
{
- for(size_t i = startIndex; i <= endIndex; ++i) {
- if(!isBitSet(i)) {
+ for (size_t i = startIndex; i <= endIndex; ++i) {
+ if (!isBitSet(i)) {
return false;
}
}
@@ -834,7 +859,7 @@ bool BitfieldMan::isBitRangeSet(size_t startIndex, size_t endIndex) const
void BitfieldMan::unsetBitRange(size_t startIndex, size_t endIndex)
{
- for(size_t i = startIndex; i <= endIndex; ++i) {
+ for (size_t i = startIndex; i <= endIndex; ++i) {
unsetBit(i);
}
updateCache();
@@ -842,7 +867,7 @@ void BitfieldMan::unsetBitRange(size_t startIndex, size_t endIndex)
void BitfieldMan::setBitRange(size_t startIndex, size_t endIndex)
{
- for(size_t i = startIndex; i <= endIndex; ++i) {
+ for (size_t i = startIndex; i <= endIndex; ++i) {
setBit(i);
}
updateCache();
@@ -850,53 +875,53 @@ void BitfieldMan::setBitRange(size_t startIndex, size_t endIndex)
bool BitfieldMan::isBitSetOffsetRange(int64_t offset, int64_t length) const
{
- if(length <= 0) {
+ if (length <= 0) {
return false;
}
- if(totalLength_ <= offset) {
+ if (totalLength_ <= offset) {
return false;
}
- if(totalLength_ < offset+length) {
- length = totalLength_-offset;
+ if (totalLength_ < offset + length) {
+ length = totalLength_ - offset;
}
- size_t startBlock = offset/blockLength_;
- size_t endBlock = (offset+length-1)/blockLength_;
- for(size_t i = startBlock; i <= endBlock; i++) {
- if(!isBitSet(i)) {
+ size_t startBlock = offset / blockLength_;
+ size_t endBlock = (offset + length - 1) / blockLength_;
+ for (size_t i = startBlock; i <= endBlock; i++) {
+ if (!isBitSet(i)) {
return false;
}
}
return true;
}
-int64_t BitfieldMan::getOffsetCompletedLength
-(int64_t offset,
- int64_t length) const
+int64_t BitfieldMan::getOffsetCompletedLength(int64_t offset,
+ int64_t length) const
{
int64_t res = 0;
- if(length == 0 || totalLength_ <= offset) {
+ if (length == 0 || totalLength_ <= offset) {
return 0;
}
- if(totalLength_ < offset+length) {
- length = totalLength_-offset;
+ if (totalLength_ < offset + length) {
+ length = totalLength_ - offset;
}
- size_t start = offset/blockLength_;
- size_t end = (offset+length-1)/blockLength_;
- if(start == end) {
- if(isBitSet(start)) {
+ size_t start = offset / blockLength_;
+ size_t end = (offset + length - 1) / blockLength_;
+ if (start == end) {
+ if (isBitSet(start)) {
res = length;
}
- } else {
- if(isBitSet(start)) {
- res += static_cast<int64_t>(start+1)*blockLength_-offset;
+ }
+ else {
+ if (isBitSet(start)) {
+ res += static_cast<int64_t>(start + 1) * blockLength_ - offset;
}
- for(size_t i = start+1; i <= end-1; ++i) {
- if(isBitSet(i)) {
+ for (size_t i = start + 1; i <= end - 1; ++i) {
+ if (isBitSet(i)) {
res += blockLength_;
}
}
- if(isBitSet(end)) {
- res += offset+length-static_cast<int64_t>(end)*blockLength_;
+ if (isBitSet(end)) {
+ res += offset + length - static_cast<int64_t>(end) * blockLength_;
}
}
return res;
@@ -904,12 +929,12 @@ int64_t BitfieldMan::getOffsetCompletedLength
int64_t BitfieldMan::getMissingUnusedLength(size_t startingIndex) const
{
- if(blocks_ <= startingIndex) {
+ if (blocks_ <= startingIndex) {
return 0;
}
int64_t length = 0;
- for(size_t i = startingIndex; i < blocks_; ++i) {
- if(isBitSet(i) || isUseBitSet(i)) {
+ for (size_t i = startingIndex; i < blocks_; ++i) {
+ if (isBitSet(i) || isUseBitSet(i)) {
break;
}
length += getBlockLength(i);
@@ -918,19 +943,15 @@ int64_t BitfieldMan::getMissingUnusedLength(size_t startingIndex) const
}
BitfieldMan::Range::Range(size_t startIndex, size_t endIndex)
- :
- startIndex(startIndex),
- endIndex(endIndex)
-{}
-
-size_t BitfieldMan::Range::getSize() const
+ : startIndex(startIndex), endIndex(endIndex)
{
- return endIndex-startIndex;
}
+size_t BitfieldMan::Range::getSize() const { return endIndex - startIndex; }
+
size_t BitfieldMan::Range::getMidIndex() const
{
- return (endIndex-startIndex)/2+startIndex;
+ return (endIndex - startIndex) / 2 + startIndex;
}
bool BitfieldMan::Range::operator<(const Range& range) const
generated by cgit (git 2.46.0) at 2026-10-12 00:59:54 +0000