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

7 files changed, 155 insertions, 64 deletions

diff --git a/test/BitfieldManTest.cc b/test/BitfieldManTest.cc
index d7d6bf9c..0acd76ea 100644
--- a/test/BitfieldManTest.cc
+++ b/test/BitfieldManTest.cc
@@ -5,6 +5,7 @@
 #include <cppunit/extensions/HelperMacros.h>
 
 #include "FixedNumberRandomizer.h"
+#include "bitfield.h"
 
 namespace aria2 {
 
@@ -25,6 +26,7 @@ class BitfieldManTest:public CppUnit::TestFixture {
   CPPUNIT_TEST(testSetBitRange);
   CPPUNIT_TEST(testGetAllMissingIndexes);
   CPPUNIT_TEST(testGetAllMissingIndexes_noarg);
+  CPPUNIT_TEST(testGetAllMissingIndexes_checkLastByte);
   CPPUNIT_TEST(testGetAllMissingUnusedIndexes);
   CPPUNIT_TEST(testGetMissingUnusedIndex);
   CPPUNIT_TEST(testGetMissingIndex_noarg);
@@ -54,6 +56,7 @@ public:
   void testGetMissingUnusedIndex_noarg();
   void testGetAllMissingIndexes();
   void testGetAllMissingIndexes_noarg();
+  void testGetAllMissingIndexes_checkLastByte();
   void testGetAllMissingUnusedIndexes();
   
   void testIsAllBitSet();
@@ -607,83 +610,87 @@ void BitfieldManTest::testGetAllMissingIndexes_noarg()
 {
   size_t blockLength = 16*1024;
   uint64_t totalLength = 1024*1024;
+  size_t nbits = (totalLength+blockLength-1)/blockLength;
   BitfieldMan bf(blockLength, totalLength);
+  unsigned char misbitfield[8];
+  CPPUNIT_ASSERT(bf.getAllMissingIndexes(misbitfield, sizeof(misbitfield)));
+  CPPUNIT_ASSERT_EQUAL((size_t)64, bitfield::countSetBit(misbitfield, nbits));
 
-  {
-    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);
   }
-  {
-    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());
-  }
+  CPPUNIT_ASSERT(bf.getAllMissingIndexes(misbitfield, sizeof(misbitfield)));
+  CPPUNIT_ASSERT_EQUAL((size_t)1, bitfield::countSetBit(misbitfield, nbits));
+  CPPUNIT_ASSERT(bitfield::test(misbitfield, nbits, 63));
+}
+
+// See garbage bits of last byte are 0
+void BitfieldManTest::testGetAllMissingIndexes_checkLastByte()
+{
+  size_t blockLength = 16*1024;
+  uint64_t totalLength = blockLength*2;
+  size_t nbits = (totalLength+blockLength-1)/blockLength;
+  BitfieldMan bf(blockLength, totalLength);
+  unsigned char misbitfield[1];
+  CPPUNIT_ASSERT(bf.getAllMissingIndexes(misbitfield, sizeof(misbitfield)));
+  CPPUNIT_ASSERT_EQUAL((size_t)2, bitfield::countSetBit(misbitfield, nbits));
+  CPPUNIT_ASSERT(bitfield::test(misbitfield, nbits, 0));
+  CPPUNIT_ASSERT(bitfield::test(misbitfield, nbits, 1));
 }
 
 void BitfieldManTest::testGetAllMissingIndexes()
 {
   size_t blockLength = 16*1024;
   uint64_t totalLength = 1024*1024;
+  size_t nbits = (totalLength+blockLength-1)/blockLength;
   BitfieldMan bf(blockLength, totalLength);
   BitfieldMan peerBf(blockLength, totalLength);
   peerBf.setAllBit();
+  unsigned char misbitfield[8];
 
-  {
-    std::deque<size_t> indexes;
-    CPPUNIT_ASSERT(bf.getAllMissingIndexes(indexes,
-					   peerBf.getBitfield(),
-					   peerBf.getBitfieldLength()));
-    CPPUNIT_ASSERT_EQUAL((size_t)64, indexes.size());
-  }
+  CPPUNIT_ASSERT(bf.getAllMissingIndexes(misbitfield, sizeof(misbitfield),
+					 peerBf.getBitfield(),
+					 peerBf.getBitfieldLength()));
+  CPPUNIT_ASSERT_EQUAL((size_t)64, bitfield::countSetBit(misbitfield, nbits));
   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());
-  }
+
+  CPPUNIT_ASSERT(bf.getAllMissingIndexes(misbitfield, sizeof(misbitfield),
+					 peerBf.getBitfield(),
+					 peerBf.getBitfieldLength()));
+  CPPUNIT_ASSERT_EQUAL((size_t)1, bitfield::countSetBit(misbitfield, nbits));
+  CPPUNIT_ASSERT(bitfield::test(misbitfield, nbits, 63));
 }
 
 void BitfieldManTest::testGetAllMissingUnusedIndexes()
 {
   size_t blockLength = 16*1024;
   uint64_t totalLength = 1024*1024;
+  size_t nbits = (totalLength+blockLength-1)/blockLength;
   BitfieldMan bf(blockLength, totalLength);
   BitfieldMan peerBf(blockLength, totalLength);
   peerBf.setAllBit();
+  unsigned char misbitfield[8];
+
+  CPPUNIT_ASSERT(bf.getAllMissingUnusedIndexes(misbitfield,
+					       sizeof(misbitfield),
+					       peerBf.getBitfield(),
+					       peerBf.getBitfieldLength()));
+  CPPUNIT_ASSERT_EQUAL((size_t)64, bitfield::countSetBit(misbitfield, nbits));
 
-  {
-    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());
-  }
+  CPPUNIT_ASSERT(bf.getAllMissingUnusedIndexes(misbitfield,
+					       sizeof(misbitfield),
+					       peerBf.getBitfield(),
+					       peerBf.getBitfieldLength()));
+  CPPUNIT_ASSERT_EQUAL((size_t)1, bitfield::countSetBit(misbitfield, nbits));
+  CPPUNIT_ASSERT(bitfield::test(misbitfield, nbits, 63));
 }
 
 void BitfieldManTest::testGetMissingUnusedIndex()
diff --git a/test/LongestSequencePieceSelectorTest.cc b/test/LongestSequencePieceSelectorTest.cc
index d3b85593..23739a42 100644
--- a/test/LongestSequencePieceSelectorTest.cc
+++ b/test/LongestSequencePieceSelectorTest.cc
@@ -3,6 +3,7 @@
 #include <cppunit/extensions/HelperMacros.h>
 
 #include "array_fun.h"
+#include "BitfieldMan.h"
 
 namespace aria2 {
 
@@ -25,19 +26,23 @@ CPPUNIT_TEST_SUITE_REGISTRATION(LongestSequencePieceSelectorTest);
 void LongestSequencePieceSelectorTest::testSelect()
 {
   size_t A[] = { 1,2,3,4,7,10,11,12,13,14,15,100,112,113,114 };
-  std::deque<size_t> indexes(&A[0], &A[arrayLength(A)]);
+  BitfieldMan bf(1024, 1024*256);
+  for(size_t i = 0; i < arrayLength(A); ++i) {
+    bf.setBit(A[i]);
+  }
 
   LongestSequencePieceSelector selector;
   size_t index;
 
-  CPPUNIT_ASSERT(selector.select(index, indexes));
+  CPPUNIT_ASSERT(selector.select(index, bf.getBitfield(), bf.countBlock()));
   CPPUNIT_ASSERT_EQUAL((size_t)15, index);
 
-  std::deque<size_t> zeroindexes;
-  CPPUNIT_ASSERT(!selector.select(index, zeroindexes));
+  bf.clearAllBit();
+  CPPUNIT_ASSERT(!selector.select(index, bf.getBitfield(), bf.countBlock()));
 
-  std::deque<size_t> oneseq(&A[0], &A[4]);
-  CPPUNIT_ASSERT(selector.select(index, oneseq));
+  // See it works in just one range
+  bf.setBitRange(1, 4);
+  CPPUNIT_ASSERT(selector.select(index, bf.getBitfield(), bf.countBlock()));
   CPPUNIT_ASSERT_EQUAL((size_t)4, index);
 }
 
diff --git a/test/Makefile.am b/test/Makefile.am
index 7bda5b09..0bdfedc6 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -67,7 +67,8 @@ aria2c_SOURCES = AllTest.cc\
 	SequentialPickerTest.cc\
 	RarestPieceSelectorTest.cc\
 	LongestSequencePieceSelectorTest.cc\
-	a2algoTest.cc
+	a2algoTest.cc\
+	bitfieldTest.cc
 
 if HAVE_POSIX_FALLOCATE
 aria2c_SOURCES += FallocFileAllocationIteratorTest.cc
diff --git a/test/Makefile.in b/test/Makefile.in
index bbd12d90..0a881e1d 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -194,8 +194,9 @@ am__aria2c_SOURCES_DIST = AllTest.cc TestUtil.cc TestUtil.h \
 	SimpleDNSCacheTest.cc DownloadHelperTest.cc BencodeTest.cc \
 	SequentialPickerTest.cc RarestPieceSelectorTest.cc \
 	LongestSequencePieceSelectorTest.cc a2algoTest.cc \
-	FallocFileAllocationIteratorTest.cc GZipDecoderTest.cc \
-	Sqlite3MozCookieParserTest.cc MessageDigestHelperTest.cc \
+	bitfieldTest.cc FallocFileAllocationIteratorTest.cc \
+	GZipDecoderTest.cc Sqlite3MozCookieParserTest.cc \
+	MessageDigestHelperTest.cc \
 	IteratableChunkChecksumValidatorTest.cc \
 	IteratableChecksumValidatorTest.cc BtAllowedFastMessageTest.cc \
 	BtBitfieldMessageTest.cc BtCancelMessageTest.cc \
@@ -364,9 +365,9 @@ am_aria2c_OBJECTS = AllTest.$(OBJEXT) TestUtil.$(OBJEXT) \
 	SequentialPickerTest.$(OBJEXT) \
 	RarestPieceSelectorTest.$(OBJEXT) \
 	LongestSequencePieceSelectorTest.$(OBJEXT) \
-	a2algoTest.$(OBJEXT) $(am__objects_1) $(am__objects_2) \
-	$(am__objects_3) $(am__objects_4) $(am__objects_5) \
-	$(am__objects_6)
+	a2algoTest.$(OBJEXT) bitfieldTest.$(OBJEXT) $(am__objects_1) \
+	$(am__objects_2) $(am__objects_3) $(am__objects_4) \
+	$(am__objects_5) $(am__objects_6)
 aria2c_OBJECTS = $(am_aria2c_OBJECTS)
 am__DEPENDENCIES_1 =
 aria2c_DEPENDENCIES = ../src/libaria2c.a ../src/download_helper.o \
@@ -591,8 +592,9 @@ aria2c_SOURCES = AllTest.cc TestUtil.cc TestUtil.h SocketCoreTest.cc \
 	SimpleDNSCacheTest.cc DownloadHelperTest.cc BencodeTest.cc \
 	SequentialPickerTest.cc RarestPieceSelectorTest.cc \
 	LongestSequencePieceSelectorTest.cc a2algoTest.cc \
-	$(am__append_1) $(am__append_2) $(am__append_3) \
-	$(am__append_4) $(am__append_5) $(am__append_6)
+	bitfieldTest.cc $(am__append_1) $(am__append_2) \
+	$(am__append_3) $(am__append_4) $(am__append_5) \
+	$(am__append_6)
 
 #aria2c_CXXFLAGS = ${CPPUNIT_CFLAGS} -I../src -I../lib -Wall -D_FILE_OFFSET_BITS=64
 #aria2c_LDFLAGS = ${CPPUNIT_LIBS}
@@ -828,6 +830,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/a2algoTest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/a2functionalTest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/array_funTest.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/bitfieldTest.Po@am__quote@
 
 .cc.o:
 @am__fastdepCXX_TRUE@	$(CXXCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $<
diff --git a/test/RarestPieceSelectorTest.cc b/test/RarestPieceSelectorTest.cc
index c8d22ccc..0549aca9 100644
--- a/test/RarestPieceSelectorTest.cc
+++ b/test/RarestPieceSelectorTest.cc
@@ -7,6 +7,7 @@
 
 #include "Exception.h"
 #include "Util.h"
+#include "BitfieldMan.h"
 
 namespace aria2 {
 
@@ -17,6 +18,7 @@ class RarestPieceSelectorTest:public CppUnit::TestFixture {
   CPPUNIT_TEST(testAddPieceStats_bitfield);
   CPPUNIT_TEST(testUpdatePieceStats);
   CPPUNIT_TEST(testSubtractPieceStats);
+  CPPUNIT_TEST(testSelect);
   CPPUNIT_TEST_SUITE_END();
 public:
   void setUp() {}
@@ -27,6 +29,7 @@ public:
   void testAddPieceStats_bitfield();
   void testUpdatePieceStats();
   void testSubtractPieceStats();
+  void testSelect();
 };
 
 
@@ -189,5 +192,24 @@ void RarestPieceSelectorTest::testSubtractPieceStats()
   }
 }
 
+void RarestPieceSelectorTest::testSelect()
+{
+  RarestPieceSelector selector(10, false);
+  BitfieldMan bf(1024, 10*1024);
+  bf.setBitRange(0, 2);
+  size_t index;
+
+  selector.addPieceStats(0);
+
+  CPPUNIT_ASSERT(selector.select(index, bf.getBitfield(),
+				 bf.countBlock()));
+  CPPUNIT_ASSERT_EQUAL((size_t)1, index);
+
+  selector.addPieceStats(1);
+
+  CPPUNIT_ASSERT(selector.select(index, bf.getBitfield(),
+				 bf.countBlock()));
+  CPPUNIT_ASSERT_EQUAL((size_t)2, index);
+}
 
 } // namespace aria2
diff --git a/test/UtilTest.cc b/test/UtilTest.cc
index 15697eab..051696e1 100644
--- a/test/UtilTest.cc
+++ b/test/UtilTest.cc
@@ -30,7 +30,6 @@ class UtilTest:public CppUnit::TestFixture {
   CPPUNIT_TEST(testToUpper);
   CPPUNIT_TEST(testToLower);
   CPPUNIT_TEST(testUrldecode);
-  CPPUNIT_TEST(testCountBit);
   CPPUNIT_TEST(testGetRealSize);
   CPPUNIT_TEST(testAbbrevSize);
   CPPUNIT_TEST(testToStream);
@@ -75,7 +74,6 @@ public:
   void testToUpper();
   void testToLower();
   void testUrldecode();
-  void testCountBit();
   void testGetRealSize();
   void testAbbrevSize();
   void testToStream();
@@ -338,11 +336,6 @@ void UtilTest::testUrldecode() {
   CPPUNIT_ASSERT_EQUAL(std::string("/"), Util::urldecode(src6));
 }
 
-void UtilTest::testCountBit() {
-  CPPUNIT_ASSERT_EQUAL((unsigned int)32, Util::countBit(UINT32_MAX));
-  CPPUNIT_ASSERT_EQUAL((unsigned int)8, Util::countBit(255));
-}
-
 void UtilTest::testGetRealSize()
 {
   CPPUNIT_ASSERT_EQUAL((int64_t)4294967296LL, Util::getRealSize("4096M"));
diff --git a/test/bitfieldTest.cc b/test/bitfieldTest.cc
new file mode 100644
index 00000000..b6b95e77
--- /dev/null
+++ b/test/bitfieldTest.cc
@@ -0,0 +1,60 @@
+#include "bitfield.h"
+
+#include <cppunit/extensions/HelperMacros.h>
+
+namespace aria2 {
+
+class bitfieldTest:public CppUnit::TestFixture {
+
+  CPPUNIT_TEST_SUITE(bitfieldTest);
+  CPPUNIT_TEST(testTest);
+  CPPUNIT_TEST(testCountBit32);
+  CPPUNIT_TEST(testCountSetBit);
+  CPPUNIT_TEST(testLastByteMask);
+  CPPUNIT_TEST_SUITE_END();
+private:
+
+public:
+  void testTest();
+  void testCountBit32();
+  void testCountSetBit();
+  void testLastByteMask();
+};
+
+
+CPPUNIT_TEST_SUITE_REGISTRATION( bitfieldTest );
+
+void bitfieldTest::testTest()
+{
+  unsigned char bitfield[] = { 0xaa };
+
+  CPPUNIT_ASSERT(bitfield::test(bitfield, 8, 0));
+  CPPUNIT_ASSERT(!bitfield::test(bitfield, 8, 1));
+}
+
+void bitfieldTest::testCountBit32()
+{
+  CPPUNIT_ASSERT_EQUAL((size_t)32, bitfield::countBit32(UINT32_MAX));
+  CPPUNIT_ASSERT_EQUAL((size_t)8, bitfield::countBit32(255));
+}
+
+void bitfieldTest::testCountSetBit()
+{
+  unsigned char bitfield[] = { 0xff, 0xff, 0xff, 0xf0, 0xff, 0x01 };
+
+  CPPUNIT_ASSERT_EQUAL((size_t)37, bitfield::countSetBit(bitfield, 48));
+  CPPUNIT_ASSERT_EQUAL((size_t)36, bitfield::countSetBit(bitfield, 47));
+  CPPUNIT_ASSERT_EQUAL((size_t)28, bitfield::countSetBit(bitfield, 32));
+}
+
+void bitfieldTest::testLastByteMask()
+{
+  CPPUNIT_ASSERT_EQUAL((unsigned int)128,
+		       (unsigned int)bitfield::lastByteMask(9));
+  CPPUNIT_ASSERT_EQUAL((unsigned int)240,
+		       (unsigned int)bitfield::lastByteMask(12));
+  CPPUNIT_ASSERT_EQUAL((unsigned int)255,
+		       (unsigned int)bitfield::lastByteMask(16));
+}
+
+} // namespace aria2