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

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());