summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog12
-rw-r--r--src/BitfieldMan.cc33
-rw-r--r--src/BitfieldMan.h14
-rw-r--r--src/DefaultBtRequestFactory.cc3
-rw-r--r--src/DefaultPieceStorage.cc33
-rw-r--r--src/Piece.cc4
-rw-r--r--src/Piece.h2
-rw-r--r--test/BitfieldManTest.cc63
8 files changed, 119 insertions, 45 deletions
diff --git a/ChangeLog b/ChangeLog
index 6ab9b2ad..a6e8dde6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,17 @@
2008-05-11 Tatsuhiro Tsujikawa <tujikawa at rednoah dot com>
+ In piece selection functions, Pass std::deque<...> by reference rather
+ than returning it.
+ * src/BitfieldMan.cc
+ * src/BitfieldMan.h
+ * src/DefaultBtRequestFactory.cc
+ * src/DefaultPieceStorage.cc
+ * src/Piece.cc
+ * src/Piece.h
+ * test/BitfieldManTest.cc
+
+2008-05-11 Tatsuhiro Tsujikawa <tujikawa at rednoah dot com>
+
Implemented rarest piece first piece selection strategy.
* src/AbstractBtMessage.cc
* src/AbstractBtMessage.h
diff --git a/src/BitfieldMan.cc b/src/BitfieldMan.cc
index d89deb29..cf3c2333 100644
--- a/src/BitfieldMan.cc
+++ b/src/BitfieldMan.cc
@@ -388,45 +388,52 @@ bool BitfieldMan::getSparseMissingUnusedIndex(size_t& index) const {
}
template<typename Array>
-std::deque<size_t>
-BitfieldMan::getAllMissingIndexes(const Array& bitfield, size_t bitfieldLength) const
+bool BitfieldMan::getAllMissingIndexes(std::deque<size_t>& indexes,
+ const Array& bitfield,
+ size_t bitfieldLength) const
{
- std::deque<size_t> missingIndexes;
for(size_t i = 0; i < bitfieldLength; ++i) {
size_t base = i*8;
for(size_t bi = 0; bi < 8 && base+bi < blocks; ++bi) {
unsigned char mask = 128 >> bi;
if(bitfield[i] & mask) {
- missingIndexes.push_back(base+bi);
+ indexes.push_back(base+bi);
}
}
}
- return missingIndexes;
+ return !indexes.empty();
}
-std::deque<size_t> BitfieldMan::getAllMissingIndexes() const {
+bool BitfieldMan::getAllMissingIndexes(std::deque<size_t>& indexes) const
+{
array_fun<unsigned char> bf = array_negate(bitfield);
if(filterEnabled) {
bf = array_and(bf, filterBitfield);
}
- return getAllMissingIndexes(bf, bitfieldLength);
+ return getAllMissingIndexes(indexes, bf, bitfieldLength);
}
-std::deque<size_t> BitfieldMan::getAllMissingIndexes(const unsigned char* peerBitfield, size_t peerBitfieldLength) const {
+bool BitfieldMan::getAllMissingIndexes(std::deque<size_t>& indexes,
+ const unsigned char* peerBitfield,
+ size_t peerBitfieldLength) const
+{
if(bitfieldLength != peerBitfieldLength) {
- return std::deque<size_t>();
+ return false;
}
array_fun<unsigned char> bf = array_and(array_negate(bitfield),
peerBitfield);
if(filterEnabled) {
bf = array_and(bf, filterBitfield);
}
- return getAllMissingIndexes(bf, bitfieldLength);
+ return getAllMissingIndexes(indexes, bf, bitfieldLength);
}
-std::deque<size_t> BitfieldMan::getAllMissingUnusedIndexes(const unsigned char* peerBitfield, size_t peerBitfieldLength) const {
+bool BitfieldMan::getAllMissingUnusedIndexes(std::deque<size_t>& indexes,
+ const unsigned char* peerBitfield,
+ size_t peerBitfieldLength) const
+{
if(bitfieldLength != peerBitfieldLength) {
- return std::deque<size_t>();
+ return false;
}
array_fun<unsigned char> bf = array_and(array_and(array_negate(bitfield),
array_negate(useBitfield)),
@@ -434,7 +441,7 @@ std::deque<size_t> BitfieldMan::getAllMissingUnusedIndexes(const unsigned char*
if(filterEnabled) {
bf = array_and(bf, filterBitfield);
}
- return getAllMissingIndexes(bf, bitfieldLength);
+ return getAllMissingIndexes(indexes, bf, bitfieldLength);
}
size_t BitfieldMan::countMissingBlock() const {
diff --git a/src/BitfieldMan.h b/src/BitfieldMan.h
index 9e8ea0e0..7150337d 100644
--- a/src/BitfieldMan.h
+++ b/src/BitfieldMan.h
@@ -73,7 +73,9 @@ private:
bool getFirstMissingIndex(size_t& index, const Array& bitfield, size_t bitfieldLength) const;
template<typename Array>
- std::deque<size_t> getAllMissingIndexes(const Array& bitfield, size_t bitfieldLength) const;
+ bool getAllMissingIndexes(std::deque<size_t>& indexes,
+ const Array& bitfield,
+ size_t bitfieldLength) const;
bool isBitSetInternal(const unsigned char* bitfield, size_t index) const;
bool setBitInternal(unsigned char* bitfield, size_t index, bool on);
@@ -137,16 +139,18 @@ public:
/**
* affected by filter
*/
- std::deque<size_t> getAllMissingIndexes() const;
+ bool getAllMissingIndexes(std::deque<size_t>&indexes) const;
/**
* affected by filter
*/
- std::deque<size_t> getAllMissingIndexes(const unsigned char* bitfield, size_t len) const;
+ bool getAllMissingIndexes(std::deque<size_t>& indexes,
+ const unsigned char* bitfield, size_t len) const;
/**
* affected by filter
*/
- std::deque<size_t> getAllMissingUnusedIndexes(const unsigned char* bitfield,
- size_t len) const;
+ bool getAllMissingUnusedIndexes(std::deque<size_t>& indexes,
+ const unsigned char* bitfield,
+ size_t len) const;
/**
* affected by filter
*/
diff --git a/src/DefaultBtRequestFactory.cc b/src/DefaultBtRequestFactory.cc
index 74825494..22e13868 100644
--- a/src/DefaultBtRequestFactory.cc
+++ b/src/DefaultBtRequestFactory.cc
@@ -126,7 +126,8 @@ BtMessages DefaultBtRequestFactory::createRequestMessagesOnEndGame(size_t max)
for(Pieces::iterator itr = pieces.begin();
itr != pieces.end() && requests.size() < max; itr++) {
PieceHandle& piece = *itr;
- std::deque<size_t> missingBlockIndexes = piece->getAllMissingBlockIndexes();
+ std::deque<size_t> missingBlockIndexes;
+ piece->getAllMissingBlockIndexes(missingBlockIndexes);
random_shuffle(missingBlockIndexes.begin(), missingBlockIndexes.end());
for(std::deque<size_t>::const_iterator bitr = missingBlockIndexes.begin();
bitr != missingBlockIndexes.end() && requests.size() < max; bitr++) {
diff --git a/src/DefaultPieceStorage.cc b/src/DefaultPieceStorage.cc
index c52840ad..75eb5fd4 100644
--- a/src/DefaultPieceStorage.cc
+++ b/src/DefaultPieceStorage.cc
@@ -142,23 +142,26 @@ public:
bool DefaultPieceStorage::getMissingPieceIndex(size_t& index, const PeerHandle& peer)
{
+ std::deque<size_t> indexes;
+ bool r;
if(isEndGame()) {
- return bitfieldMan->getMissingIndex(index, peer->getBitfield(),
- peer->getBitfieldLength());
+ r = bitfieldMan->getAllMissingIndexes(indexes, peer->getBitfield(),
+ peer->getBitfieldLength());
} else {
- std::deque<size_t> indexes =
- bitfieldMan->getAllMissingUnusedIndexes(peer->getBitfield(),
- peer->getBitfieldLength());
- if(indexes.empty()) {
- return false;
- } else {
- std::sort(indexes.begin(), indexes.end());
- std::deque<SharedHandle<PieceStat> >::const_iterator i =
- std::find_if(_sortedPieceStats.begin(), _sortedPieceStats.end(),
- FindRarestPiece(indexes));
- index = (*i)->getIndex();
- return true;
- }
+ r = bitfieldMan->getAllMissingUnusedIndexes(indexes,
+ peer->getBitfield(),
+ peer->getBitfieldLength());
+ }
+ if(r) {
+ // We assume indexes is sorted using comparator less.
+ //std::sort(indexes.begin(), indexes.end());
+ std::deque<SharedHandle<PieceStat> >::const_iterator i =
+ std::find_if(_sortedPieceStats.begin(), _sortedPieceStats.end(),
+ FindRarestPiece(indexes));
+ index = (*i)->getIndex();
+ return true;
+ } else {
+ return false;
}
}
diff --git a/src/Piece.cc b/src/Piece.cc
index aa56401e..f35520a3 100644
--- a/src/Piece.cc
+++ b/src/Piece.cc
@@ -169,8 +169,8 @@ bool Piece::getFirstMissingBlockIndexWithoutLock(size_t& index) const
return bitfield->getFirstMissingIndex(index);
}
-std::deque<size_t> Piece::getAllMissingBlockIndexes() const {
- return bitfield->getAllMissingIndexes();
+bool Piece::getAllMissingBlockIndexes(std::deque<size_t>& indexes) const {
+ return bitfield->getAllMissingIndexes(indexes);
}
std::string Piece::toString() const {
diff --git a/src/Piece.h b/src/Piece.h
index 67e61f43..c978f451 100644
--- a/src/Piece.h
+++ b/src/Piece.h
@@ -70,7 +70,7 @@ public:
bool getMissingUnusedBlockIndex(size_t& index) const;
bool getMissingBlockIndex(size_t& index) const;
bool getFirstMissingBlockIndexWithoutLock(size_t& index) const;
- std::deque<size_t> getAllMissingBlockIndexes() const;
+ bool getAllMissingBlockIndexes(std::deque<size_t>& indexes) const;
void completeBlock(size_t blockIndex);
void cancelBlock(size_t blockIndex);
diff --git a/test/BitfieldManTest.cc b/test/BitfieldManTest.cc
index 00451fbc..2ab8e936 100644
--- a/test/BitfieldManTest.cc
+++ b/test/BitfieldManTest.cc
@@ -21,6 +21,7 @@ class BitfieldManTest:public CppUnit::TestFixture {
CPPUNIT_TEST(testSetBitRange);
CPPUNIT_TEST(testGetAllMissingIndexes);
CPPUNIT_TEST(testGetAllMissingIndexes_noarg);
+ CPPUNIT_TEST(testGetAllMissingUnusedIndexes);
CPPUNIT_TEST(testGetMissingUnusedIndex);
CPPUNIT_TEST(testGetMissingIndex_noarg);
CPPUNIT_TEST(testGetMissingUnusedIndex_noarg);
@@ -48,7 +49,8 @@ public:
void testGetMissingUnusedIndex_noarg();
void testGetAllMissingIndexes();
void testGetAllMissingIndexes_noarg();
-
+ void testGetAllMissingUnusedIndexes();
+
void testIsAllBitSet();
void testFilter();
void testGetSparceMissingUnusedIndex();
@@ -594,12 +596,20 @@ void BitfieldManTest::testGetAllMissingIndexes_noarg()
uint64_t totalLength = 1024*1024;
BitfieldMan bf(blockLength, totalLength);
- CPPUNIT_ASSERT_EQUAL((size_t)64, bf.getAllMissingIndexes().size());
+ {
+ std::deque<size_t> indexes;
+ CPPUNIT_ASSERT(bf.getAllMissingIndexes(indexes));
+ CPPUNIT_ASSERT_EQUAL((size_t)64, indexes.size());
+ }
for(size_t i = 0; i < 63; ++i) {
bf.setBit(i);
}
- CPPUNIT_ASSERT_EQUAL((size_t)1, bf.getAllMissingIndexes().size());
- CPPUNIT_ASSERT_EQUAL((size_t)63, bf.getAllMissingIndexes().front());
+ {
+ std::deque<size_t> indexes;
+ CPPUNIT_ASSERT(bf.getAllMissingIndexes(indexes));
+ CPPUNIT_ASSERT_EQUAL((size_t)1, indexes.size());
+ CPPUNIT_ASSERT_EQUAL((size_t)63, indexes.front());
+ }
}
void BitfieldManTest::testGetAllMissingIndexes()
@@ -610,16 +620,53 @@ void BitfieldManTest::testGetAllMissingIndexes()
BitfieldMan peerBf(blockLength, totalLength);
peerBf.setAllBit();
- CPPUNIT_ASSERT_EQUAL((size_t)64, bf.getAllMissingIndexes(peerBf.getBitfield(),
- peerBf.getBitfieldLength()).size());
+ {
+ std::deque<size_t> indexes;
+ CPPUNIT_ASSERT(bf.getAllMissingIndexes(indexes,
+ peerBf.getBitfield(),
+ peerBf.getBitfieldLength()));
+ CPPUNIT_ASSERT_EQUAL((size_t)64, indexes.size());
+ }
for(size_t i = 0; i < 62; ++i) {
bf.setBit(i);
}
peerBf.unsetBit(62);
+ {
+ std::deque<size_t> indexes;
+ CPPUNIT_ASSERT(bf.getAllMissingIndexes(indexes,
+ peerBf.getBitfield(),
+ peerBf.getBitfieldLength()));
+
+ CPPUNIT_ASSERT_EQUAL((size_t)1, indexes.size());
+ CPPUNIT_ASSERT_EQUAL((size_t)63, indexes.front());
+ }
+}
+
+void BitfieldManTest::testGetAllMissingUnusedIndexes()
+{
+ size_t blockLength = 16*1024;
+ uint64_t totalLength = 1024*1024;
+ BitfieldMan bf(blockLength, totalLength);
+ BitfieldMan peerBf(blockLength, totalLength);
+ peerBf.setAllBit();
{
- std::deque<size_t> indexes = bf.getAllMissingIndexes(peerBf.getBitfield(),
- peerBf.getBitfieldLength());
+ std::deque<size_t> indexes;
+ CPPUNIT_ASSERT(bf.getAllMissingUnusedIndexes(indexes,
+ peerBf.getBitfield(),
+ peerBf.getBitfieldLength()));
+ CPPUNIT_ASSERT_EQUAL((size_t)64, indexes.size());
+ }
+ for(size_t i = 0; i < 61; ++i) {
+ bf.setBit(i);
+ }
+ bf.setUseBit(61);
+ peerBf.unsetBit(62);
+ {
+ std::deque<size_t> indexes;
+ CPPUNIT_ASSERT(bf.getAllMissingUnusedIndexes(indexes,
+ peerBf.getBitfield(),
+ peerBf.getBitfieldLength()));
CPPUNIT_ASSERT_EQUAL((size_t)1, indexes.size());
CPPUNIT_ASSERT_EQUAL((size_t)63, indexes.front());
generated by cgit (git 2.46.0) at 2026-10-12 07:20:48 +0000