aria2/src/BitfieldMan.cc

/* <!-- copyright */
/*
 * aria2 - The high speed download utility
 *
 * Copyright (C) 2006 Tatsuhiro Tsujikawa
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 *
 * In addition, as a special exception, the copyright holders give
 * permission to link the code of portions of this program with the
 * OpenSSL library under certain conditions as described in each
 * individual source file, and distribute linked combinations
 * including the two.
 * You must obey the GNU General Public License in all respects
 * for all of the code used other than OpenSSL.  If you modify
 * file(s) with this exception, you may extend this exception to your
 * version of the file(s), but you are not obligated to do so.  If you
 * do not wish to do so, delete this exception statement from your
 * version.  If you delete this exception statement from all source
 * files in the program, then also delete it here.
 */
/* copyright --> */
#include "BitfieldMan.h"

#include <cassert>
#include <cstring>

#include "array_fun.h"
#include "bitfield.h"

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);
    bitfield_ = new unsigned char[bitfieldLength_];
    useBitfield_ = new unsigned char[bitfieldLength_];
    memset(bitfield_, 0, bitfieldLength_);
    memset(useBitfield_, 0, bitfieldLength_);
    updateCache();
  }
}

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_)
{
  memcpy(bitfield_, bitfieldMan.bitfield_, bitfieldLength_);
  memcpy(useBitfield_, bitfieldMan.useBitfield_, bitfieldLength_);
  if(filterEnabled_) {
    filterBitfield_ = new unsigned char[bitfieldLength_];
    memcpy(filterBitfield_, bitfieldMan.filterBitfield_, bitfieldLength_);
  }
  updateCache();
}

BitfieldMan& BitfieldMan::operator=(const BitfieldMan& bitfieldMan)
{
  if(this != &bitfieldMan) {
    totalLength_ = bitfieldMan.totalLength_;
    blockLength_ = bitfieldMan.blockLength_;
    blocks_ = bitfieldMan.blocks_;
    bitfieldLength_ = bitfieldMan.bitfieldLength_;
    filterEnabled_ = bitfieldMan.filterEnabled_;

    delete [] bitfield_;
    bitfield_ = new unsigned char[bitfieldLength_];
    memcpy(bitfield_, bitfieldMan.bitfield_, bitfieldLength_);

    delete [] useBitfield_;
    useBitfield_ = new unsigned char[bitfieldLength_];
    memcpy(useBitfield_, bitfieldMan.useBitfield_, bitfieldLength_);

    delete [] filterBitfield_;
    if(filterEnabled_) {
      filterBitfield_ = new unsigned char[bitfieldLength_];
      memcpy(filterBitfield_, bitfieldMan.filterBitfield_, bitfieldLength_);
    } else {
      filterBitfield_ = nullptr;
    }

    updateCache();
  }
  return *this;
}

BitfieldMan::~BitfieldMan() {
  delete [] bitfield_;
  delete [] useBitfield_;
  delete [] filterBitfield_;
}

int32_t BitfieldMan::getLastBlockLength() const
{
  return totalLength_-blockLength_*(blocks_-1);
}

int32_t BitfieldMan::getBlockLength(size_t index) const
{
  if(index == blocks_-1) {
    return getLastBlockLength();
  } else if(index < blocks_-1) {
    return getBlockLength();
  } else {
    return 0;
  }
}

bool BitfieldMan::hasMissingPiece
(const unsigned char* peerBitfield, size_t length) const
{
  if(bitfieldLength_ != length) {
    return false;
  }
  bool retval = false;
  for(size_t i = 0; i < bitfieldLength_; ++i) {
    unsigned char temp = peerBitfield[i] & ~bitfield_[i];
    if(filterEnabled_) {
      temp &= filterBitfield_[i];
    }
    if(temp&0xffu) {
      retval = true;
      break;
    }
  }
  return retval;
}

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_);
  }
}

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_);
  }
}

bool BitfieldMan::getFirstMissingIndex(size_t& index) const
{
  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)) {
    ++index;
  }
  if(blocks <= index) {
    return blocks;
  } 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)) {
    ++index;
  }
  return index;
}
} // 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)
{
  BitfieldMan::Range maxRange;
  BitfieldMan::Range currentRange;
  size_t nextIndex = 0;
  while(nextIndex < blocks) {
    currentRange.startIndex =
      getStartIndex(nextIndex, bitfield, blocks);
    if(currentRange.startIndex == blocks) {
      break;
    }
    currentRange.endIndex =
      getEndIndex(currentRange.startIndex, bitfield, blocks);

    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))) {
      maxRange = currentRange;
    }
    nextIndex = currentRange.endIndex;

  }
  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)) {
        index = maxRange.startIndex;
        return true;
      } else {
        return false;
      }
    }
  } else {
    return false;
  }
}
} // namespace

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_);
  }
}

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)
{
  double start = 0;
  double end = 1;
  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)) {
        break;
      } else if(!bitfield::test(bitfield, blocks, i)) {
        index = i;
        break;
      }
    }
    if(index < blocks) {
      return true;
    } else {
      start = end;
      end *= base;
    }
  }
  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);
  }
}

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)
{
  // We always return first piece if it is available.
  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)) {
      // 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)) {
        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)) {
          break;
        }
        if(static_cast<int64_t>(j-i+1)*blockLength >= minSplitSize) {
          index = j;
          return true;
        }
      }
      i = j+1;
    } else {
      ++i;
    }
  }
  return false;
}
} // 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
{
  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_);
  }
}

namespace {
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) {
    dst[i] = src[i];
    bits |= dst[i];
  }
  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
{
  assert(len == bitfieldLength_);
  if(filterEnabled_) {
    return copyBitfield
      (misbitfield, ~array(bitfield_)&array(filterBitfield_), blocks_);
  } else {
    return copyBitfield(misbitfield, ~array(bitfield_), blocks_);
  }
}

bool BitfieldMan::getAllMissingIndexes(unsigned char* misbitfield, size_t len,
                                       const unsigned char* peerBitfield,
                                       size_t peerBitfieldLength) const
{
  assert(len == bitfieldLength_);
  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_);
  }
}

bool BitfieldMan::getAllMissingUnusedIndexes(unsigned char* misbitfield,
                                             size_t len,
                                             const unsigned char* peerBitfield,
                                             size_t peerBitfieldLength) const
{
  assert(len == bitfieldLength_);
  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_);
  }
}

size_t BitfieldMan::countMissingBlock() const {
  return cachedNumMissingBlock_;
}

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_);
  }
}

size_t BitfieldMan::countFilteredBlockNow() const {
  if(filterEnabled_) {
    return bitfield::countSetBit(filterBitfield_, blocks_);
  } 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;
  }
  return true;
}

bool BitfieldMan::setUseBit(size_t index) {
  return setBitInternal(useBitfield_, index, true);
}

bool BitfieldMan::unsetUseBit(size_t index) {
  return setBitInternal(useBitfield_, index, false);
}

bool BitfieldMan::setBit(size_t index) {
  bool b = setBitInternal(bitfield_, index, true);
  updateCache();
  return b;
}

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]) {
        return false;
      }
    }
    return true;
  } else {
    return isAllBitSet();
  }
}

namespace {
bool testAllBitSet
(const unsigned char* bitfield, size_t length, size_t blocks)
{
  if(length == 0) {
    return true;
  }
  for(size_t i = 0; i < length-1; ++i) {
    if(bitfield[i] != 0xffu) {
      return false;
    }
  }
  return bitfield[length-1] == bitfield::lastByteMask(blocks);
}
} // namespace

bool BitfieldMan::isAllBitSet() const
{
  return testAllBitSet(bitfield_, bitfieldLength_, blocks_);
}

bool BitfieldMan::isAllFilterBitSet() const
{
  if(!filterBitfield_) {
    return false;
  }
  return testAllBitSet(filterBitfield_, bitfieldLength_, blocks_);
}

bool BitfieldMan::isFilterBitSet(size_t index) const {
  if(filterBitfield_) {
    return bitfield::test(filterBitfield_, blocks_, index);
  } else {
    return false;
  }
}

bool BitfieldMan::isBitSet(size_t index) const
{
  return bitfield::test(bitfield_, blocks_, index);
}

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) {
    return;
  }
  memcpy(bitfield_, bitfield, bitfieldLength_);
  memset(useBitfield_, 0, bitfieldLength_);
  updateCache();
}

void BitfieldMan::clearAllBit() {
  memset(bitfield_, 0, bitfieldLength_);
  updateCache();
}

void BitfieldMan::setAllBit() {
  for(size_t i = 0; i < blocks_; ++i) {
    setBitInternal(bitfield_, i, true);
  }
  updateCache();
}

void BitfieldMan::clearAllUseBit() {
  memset(useBitfield_, 0, bitfieldLength_);
  updateCache();
}

void BitfieldMan::setAllUseBit() {
  for(size_t i = 0; i < blocks_; ++i) {
    setBitInternal(useBitfield_, i, true);
  }
}

bool BitfieldMan::setFilterBit(size_t index) {
  return setBitInternal(filterBitfield_, index, true);
}

void BitfieldMan::ensureFilterBitfield()
{
  if(!filterBitfield_) {
    filterBitfield_ = new unsigned char[bitfieldLength_];
    memset(filterBitfield_, 0, bitfieldLength_);
  }
}

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++) {
      setFilterBit(i);
    }
  }
  updateCache();
}

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++) {
      setBitInternal(filterBitfield_, i, false);
    }
  }
  updateCache();
}

void BitfieldMan::addNotFilter(int64_t offset, int64_t length)
{
  ensureFilterBitfield();
  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) {
      setFilterBit(i);
    }
    for(size_t i = endBlock+1; i < blocks_; ++i) {
      setFilterBit(i);
    }
  }
  updateCache();
}

void BitfieldMan::enableFilter() {
  ensureFilterBitfield();
  filterEnabled_ = true;
  updateCache();
}

void BitfieldMan::disableFilter() {
  filterEnabled_ = false;
  updateCache();
}

void BitfieldMan::clearFilter() {
  if(filterBitfield_) {
    delete [] filterBitfield_;
    filterBitfield_ = nullptr;
  }
  filterEnabled_ = false;
  updateCache();
}

int64_t BitfieldMan::getFilteredTotalLengthNow() const {
  if(!filterBitfield_) {
    return 0;
  }
  size_t filteredBlocks = bitfield::countSetBit(filterBitfield_, blocks_);
  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_;
  }
}

namespace {
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) {
    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();
    }
  }
  return completedLength;
}
} // namespace

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 {
    return computeCompletedLength(bitfield_, this, &bitfield::countSetBit);
  }
}

int64_t BitfieldMan::getCompletedLengthNow() const {
  return getCompletedLength(false);
}

int64_t BitfieldMan::getFilteredCompletedLengthNow() const {
  return getCompletedLength(true);
}

void BitfieldMan::updateCache()
{
  cachedNumMissingBlock_ = countMissingBlockNow();
  cachedNumFilteredBlock_ = countFilteredBlockNow();
  cachedFilteredTotalLength_ = getFilteredTotalLengthNow();
  cachedCompletedLength_ = getCompletedLengthNow();
  cachedFilteredCompletedLength_ = getFilteredCompletedLengthNow();
}

bool BitfieldMan::isBitRangeSet(size_t startIndex, size_t endIndex) const
{
  for(size_t i =  startIndex; i <= endIndex; ++i) {
    if(!isBitSet(i)) {
      return false;
    }
  }
  return true;
}

void BitfieldMan::unsetBitRange(size_t startIndex, size_t endIndex)
{
  for(size_t i = startIndex; i <= endIndex; ++i) {
    unsetBit(i);
  }
  updateCache();
}

void BitfieldMan::setBitRange(size_t startIndex, size_t endIndex)
{
  for(size_t i = startIndex; i <= endIndex; ++i) {
    setBit(i);
  }
  updateCache();
}

bool BitfieldMan::isBitSetOffsetRange(int64_t offset, int64_t length) const
{
  if(length <= 0) {
    return false;
  }
  if(totalLength_ <= offset) {
    return false;
  }
  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)) {
      return false;
    }
  }
  return true;
}

int64_t BitfieldMan::getOffsetCompletedLength
(int64_t offset,
 int64_t length) const
{
  int64_t res = 0;
  if(length == 0 || totalLength_ <= offset) {
    return 0;
  }
  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)) {
      res = length;
    }
  } 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)) {
        res += blockLength_;
      }
    }
    if(isBitSet(end)) {
      res += offset+length-static_cast<int64_t>(end)*blockLength_;
    }
  }
  return res;
}

int64_t BitfieldMan::getMissingUnusedLength(size_t startingIndex) const
{
  if(blocks_ <= startingIndex) {
    return 0;
  }
  int64_t length = 0;
  for(size_t i = startingIndex; i < blocks_; ++i) {
    if(isBitSet(i) || isUseBitSet(i)) {
      break;
    }
    length += getBlockLength(i);
  }
  return length;
}

BitfieldMan::Range::Range(size_t startIndex, size_t endIndex)
 :
  startIndex(startIndex),
  endIndex(endIndex)
{}

size_t BitfieldMan::Range::getSize() const
{
  return endIndex-startIndex;
}

size_t BitfieldMan::Range::getMidIndex() const
{
  return (endIndex-startIndex)/2+startIndex;
}

bool BitfieldMan::Range::operator<(const Range& range) const
{
  return getSize() < range.getSize();
}

bool BitfieldMan::Range::operator==(const Range& range) const
{
  return getSize() == range.getSize();
}

} // namespace aria2