2009-03-28 Tatsuhiro Tsujikawa <t-tujikawa@users.sourceforge.net>

	BitfieldMan::getMissingIndexes family functions now takes
	unsigned char* bitfield instead of stl container for efficiency.
	PieceSelector::select now takes this
	bitfield. RarestPieceSelector::select now also performs
	efficiently for this change.  bitfield namespace is introduced
	and it has several helper functions to handle basic bitfield
	operations such as test, count set bits, etc.
	* src/BitfieldMan.cc
	* src/BitfieldMan.h
	* src/DefaultBtRequestFactory.cc
	* src/DefaultPieceStorage.cc
	* src/DefaultPieceStorage.h
	* src/LongestSequencePieceSelector.cc
	* src/LongestSequencePieceSelector.h
	* src/Makefile.am
	* src/Piece.cc
	* src/Piece.h
	* src/PieceSelector.h
	* src/RarestPieceSelector.cc
	* src/RarestPieceSelector.h
	* src/Util.cc
	* src/Util.h
	* src/bitfield.h
	* test/BitfieldManTest.cc
	* test/LongestSequencePieceSelectorTest.cc
	* test/Makefile.am
	* test/RarestPieceSelectorTest.cc
	* test/UtilTest.cc
	* test/bitfieldTest.cc

1 files changed, 17 insertions, 2 deletions

diff --git a/src/DefaultBtRequestFactory.cc b/src/DefaultBtRequestFactory.cc
index 2a272437..8330efeb 100644
--- a/src/DefaultBtRequestFactory.cc
+++ b/src/DefaultBtRequestFactory.cc
@@ -47,6 +47,7 @@
 #include "BtMessage.h"
 #include "a2functional.h"
 #include "SimpleRandomizer.h"
+#include "array_fun.h"
 
 namespace aria2 {
 
@@ -170,13 +171,27 @@ void DefaultBtRequestFactory::createRequestMessagesOnEndGame
   for(Pieces::iterator itr = pieces.begin();
       itr != pieces.end() && requests.size() < max; ++itr) {
     PieceHandle& piece = *itr;
+    const size_t mislen = piece->getBitfieldLength();
+    array_ptr<unsigned char> misbitfield(new unsigned char[mislen]);
+
+    piece->getAllMissingBlockIndexes(misbitfield, mislen);
+
     std::deque<size_t> missingBlockIndexes;
-    piece->getAllMissingBlockIndexes(missingBlockIndexes);
+    size_t blockIndex = 0;
+    for(size_t i = 0; i < mislen; ++i) {
+      unsigned char bits = misbitfield[i];
+      unsigned char mask = 128;
+      for(size_t bi = 0; bi < 8; ++bi, mask >>= 1, ++blockIndex) {
+	if(bits & mask) {
+	  missingBlockIndexes.push_back(blockIndex);
+	}
+      }
+    }
     std::random_shuffle(missingBlockIndexes.begin(), missingBlockIndexes.end(),
 			*(SimpleRandomizer::getInstance().get()));
     for(std::deque<size_t>::const_iterator bitr = missingBlockIndexes.begin();
 	bitr != missingBlockIndexes.end() && requests.size() < max; bitr++) {
-      size_t blockIndex = *bitr;
+      const size_t& blockIndex = *bitr;
       if(!dispatcher->isOutstandingRequest(piece->getIndex(),
 					   blockIndex)) {
       _logger->debug("Creating RequestMessage index=%u, begin=%u, blockIndex=%u",