2010-02-11 Tatsuhiro Tsujikawa <t-tujikawa@users.sourceforge.net>

	Added BitfieldMan::getFirstNMissingUnusedIndex() to get multiple
	unused block indexes at once instead of calling
	getFirstMissingUnusedIndex() multiple times. Made use of it in
	Piece class and DefaultBtRequestFactory class via Piece class.
	* src/BitfieldMan.cc
	* src/BitfieldMan.h
	* src/DefaultBtRequestFactory.cc
	* src/Piece.cc
	* src/Piece.h
	* test/BitfieldManTest.cc

7 files changed, 130 insertions, 19 deletions

diff --git a/ChangeLog b/ChangeLog
index 7cfd4aa8..e76067c3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2010-02-11  Tatsuhiro Tsujikawa  <t-tujikawa@users.sourceforge.net>
+
+	Added BitfieldMan::getFirstNMissingUnusedIndex() to get multiple
+	unused block indexes at once instead of calling
+	getFirstMissingUnusedIndex() multiple times. Made use of it in
+	Piece class and DefaultBtRequestFactory class via Piece class.
+	* src/BitfieldMan.cc
+	* src/BitfieldMan.h
+	* src/DefaultBtRequestFactory.cc
+	* src/Piece.cc
+	* src/Piece.h
+	* test/BitfieldManTest.cc
+
 2010-02-10  Tatsuhiro Tsujikawa  <t-tujikawa@users.sourceforge.net>
 
 	Use std::make_pair(...)
diff --git a/src/BitfieldMan.cc b/src/BitfieldMan.cc
index e0868193..a11dcee8 100644
--- a/src/BitfieldMan.cc
+++ b/src/BitfieldMan.cc
@@ -268,6 +268,47 @@ bool BitfieldMan::getFirstMissingUnusedIndex(size_t& index) const
   }
 }
 
+template<typename Array, typename OutputIterator>
+static bool getFirstNMissingIndex
+(OutputIterator out, size_t n,
+ const Array& bitfield, size_t bitfieldLength, size_t blocks)
+{
+  if(n == 0) {
+    return false;
+  }
+  const size_t origN = n;
+  for(size_t i = 0; i < bitfieldLength; ++i) {
+    unsigned char bits = bitfield[i];
+    unsigned char mask = 128;
+    size_t tindex = i*8;
+    for(size_t bi = 0; bi < 8 && tindex < blocks; ++bi, mask >>= 1, ++tindex) {
+      if(bits & mask) {
+        *out++ = tindex;
+        if(--n == 0) {
+          return true;
+        }
+      }
+    }
+  }
+  return origN > n;
+}
+
+bool BitfieldMan::getFirstNMissingUnusedIndex
+(std::vector<size_t>& out, size_t n) const
+{
+  if(filterEnabled) {
+    return getFirstNMissingIndex
+      (std::back_inserter(out), n,
+       ~array(bitfield)&~array(useBitfield)&array(filterBitfield),
+       bitfieldLength, blocks);
+  } else {
+    return getFirstNMissingIndex
+      (std::back_inserter(out), n,
+       ~array(bitfield)&~array(useBitfield),
+       bitfieldLength, blocks);
+  }
+}
+
 bool BitfieldMan::getFirstMissingIndex(size_t& index) const
 {
   if(filterEnabled) {
diff --git a/src/BitfieldMan.h b/src/BitfieldMan.h
index ee0668bf..11ba95c5 100644
--- a/src/BitfieldMan.h
+++ b/src/BitfieldMan.h
@@ -38,6 +38,7 @@
 #include "common.h"
 #include "SharedHandle.h"
 #include <deque>
+#include <vector>
 
 namespace aria2 {
 
@@ -144,11 +145,14 @@ public:
   /**
    * affected by filter
    */
-  bool getFirstMissingUnusedIndex(size_t& index, const unsigned char* bitfield, size_t len) const;
+  bool getFirstMissingUnusedIndex(size_t& index) const;
   /**
+   * Stores at most n missing unused index in out. This function
+   * doesn't delete existing elements in out.
+   *
    * affected by filter
    */
-  bool getFirstMissingUnusedIndex(size_t& index) const;
+  bool getFirstNMissingUnusedIndex(std::vector<size_t>& out, size_t n) const;
   /**
    * affected by filter
    */
diff --git a/src/DefaultBtRequestFactory.cc b/src/DefaultBtRequestFactory.cc
index c7ab09ed..3e55ddb2 100644
--- a/src/DefaultBtRequestFactory.cc
+++ b/src/DefaultBtRequestFactory.cc
@@ -152,20 +152,30 @@ void DefaultBtRequestFactory::removeAllTargetPiece() {
 void DefaultBtRequestFactory::createRequestMessages
 (std::deque<SharedHandle<BtMessage> >& requests, size_t max)
 {
+  if(requests.size() >= max) {
+    return;
+  }
+  size_t getnum = max-requests.size();
+  std::vector<size_t> blockIndexes;
+  blockIndexes.reserve(getnum);
   for(Pieces::iterator itr = pieces.begin();
-      itr != pieces.end() && requests.size() < max; ++itr) {
-    PieceHandle& piece = *itr;
-    size_t blockIndex;
-    while(requests.size() < max &&
-          piece->getMissingUnusedBlockIndex(blockIndex)) {
-      if(_logger->debug()) {
-        _logger->debug("Creating RequestMessage index=%u, begin=%u,"
-                       " blockIndex=%u",
-                       piece->getIndex(),
-                       blockIndex*piece->getBlockLength(),
-                       blockIndex);
+      itr != pieces.end() && getnum; ++itr) {
+    SharedHandle<Piece>& piece = *itr;
+    if(piece->getMissingUnusedBlockIndex(blockIndexes, getnum)) {
+      getnum -= blockIndexes.size();
+      for(std::vector<size_t>::const_iterator i = blockIndexes.begin();
+          i != blockIndexes.end(); ++i) {
+        if(_logger->debug()) {
+          _logger->debug("Creating RequestMessage index=%u, begin=%u,"
+                         " blockIndex=%u",
+                         piece->getIndex(),
+                         (*i)*piece->getBlockLength(),
+                         (*i));
+        }
+        requests.push_back
+          (messageFactory->createRequestMessage(piece, *i));
       }
-      requests.push_back(messageFactory->createRequestMessage(piece, blockIndex));
+      blockIndexes.clear();
     }
   }
 }
diff --git a/src/Piece.cc b/src/Piece.cc
index 26f50fe2..2d5a689b 100644
--- a/src/Piece.cc
+++ b/src/Piece.cc
@@ -173,10 +173,14 @@ bool Piece::getMissingUnusedBlockIndex(size_t& index) const
   }
 }
 
-bool Piece::getMissingBlockIndex(size_t& index) const
+bool Piece::getMissingUnusedBlockIndex
+(std::vector<size_t>& indexes, size_t n) const
 {
-  if(bitfield->getMissingIndex(index)) {
-    bitfield->setUseBit(index);
+  if(bitfield->getFirstNMissingUnusedIndex(indexes, n)) {
+    for(std::vector<size_t>::const_iterator i = indexes.begin();
+        i != indexes.end(); ++i) {
+      bitfield->setUseBit(*i);
+    }
     return true;
   } else {
     return false;
diff --git a/src/Piece.h b/src/Piece.h
index 4a7b8e93..3177ac89 100644
--- a/src/Piece.h
+++ b/src/Piece.h
@@ -36,11 +36,14 @@
 #define _D_PIECE_H_
 
 #include "common.h"
-#include "SharedHandle.h"
+
 #include <stdint.h>
 #include <deque>
+#include <vector>
 #include <string>
 
+#include "SharedHandle.h"
+
 namespace aria2 {
 
 class BitfieldMan;
@@ -92,8 +95,15 @@ public:
     return index < piece.index;
   }
 
+  // TODO This function only used by unit tests
   bool getMissingUnusedBlockIndex(size_t& index) const;
-  bool getMissingBlockIndex(size_t& index) const;
+
+  // Stores at most n missing unused block index to indexes. For all i
+  // in indexes, call bitfield->setUseBit(i). This function just add
+  // index to indexes and it doesn't remove anything from
+  // it. Therefore Caller must pass empty indexes.
+  bool getMissingUnusedBlockIndex(std::vector<size_t>& indexes, size_t n) const;
+
   bool getFirstMissingBlockIndexWithoutLock(size_t& index) const;
   bool getAllMissingBlockIndexes(unsigned char* misbitfield,
                                  size_t mislen) const;
diff --git a/test/BitfieldManTest.cc b/test/BitfieldManTest.cc
index c0532ff5..80a6f980 100644
--- a/test/BitfieldManTest.cc
+++ b/test/BitfieldManTest.cc
@@ -1,6 +1,7 @@
 #include "BitfieldMan.h"
 
 #include <cstring>
+#include <vector>
 
 #include <cppunit/extensions/HelperMacros.h>
 
@@ -37,6 +38,7 @@ class BitfieldManTest:public CppUnit::TestFixture {
   CPPUNIT_TEST(testCountFilteredBlock);
   CPPUNIT_TEST(testCountMissingBlock);
   CPPUNIT_TEST(testZeroLengthFilter);
+  CPPUNIT_TEST(testGetFirstNMissingUnusedIndex);
   CPPUNIT_TEST_SUITE_END();
 private:
   SharedHandle<Randomizer> fixedNumberRandomizer;
@@ -77,6 +79,7 @@ public:
   void testCountFilteredBlock();
   void testCountMissingBlock();
   void testZeroLengthFilter();
+  void testGetFirstNMissingUnusedIndex();
 };
 
 
@@ -843,4 +846,30 @@ void BitfieldManTest::testZeroLengthFilter()
   CPPUNIT_ASSERT_EQUAL((size_t)0, bt.countMissingBlock());
 }
 
+void BitfieldManTest::testGetFirstNMissingUnusedIndex()
+{
+  BitfieldMan bt(1024, 1024*10);
+  bt.setUseBit(1);
+  bt.setBit(5);
+  std::vector<size_t> out;
+  bt.getFirstNMissingUnusedIndex(out, 256);
+  CPPUNIT_ASSERT_EQUAL((size_t)8, out.size());
+  const size_t ans[] = {0, 2, 3, 4, 6, 7, 8, 9};
+  for(size_t i = 0; i < out.size(); ++i) {
+    CPPUNIT_ASSERT_EQUAL(ans[i], out[i]);
+  }
+  out.clear();
+  bt.getFirstNMissingUnusedIndex(out, 3);
+  CPPUNIT_ASSERT_EQUAL((size_t)3, out.size());
+  for(size_t i = 0; i < out.size(); ++i) {
+    CPPUNIT_ASSERT_EQUAL(ans[i], out[i]);
+  }  
+  out.clear();
+  bt.addFilter(1024*9, 1024);
+  bt.enableFilter();
+  bt.getFirstNMissingUnusedIndex(out, 256);
+  CPPUNIT_ASSERT_EQUAL((size_t)1, out.size());
+  CPPUNIT_ASSERT_EQUAL((size_t)9, out[0]);
+}
+
 } // namespace aria2