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

	Moved getFirstNMissingIndex to bitfield.h and made it return the
	number of appended indexes.
	* src/BitfieldMan.cc
	* src/BitfieldMan.h
	* src/Piece.cc
	* src/Piece.h
	* src/bitfield.h
	* test/BitfieldManTest.cc

5 files changed, 46 insertions, 46 deletions

diff --git a/src/BitfieldMan.cc b/src/BitfieldMan.cc
index a11dcee8..2ab00812 100644
--- a/src/BitfieldMan.cc
+++ b/src/BitfieldMan.cc
@@ -268,44 +268,17 @@ 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
+size_t BitfieldMan::getFirstNMissingUnusedIndex
 (std::vector<size_t>& out, size_t n) const
 {
   if(filterEnabled) {
-    return getFirstNMissingIndex
+    return bitfield::getFirstNMissingIndex
       (std::back_inserter(out), n,
-       ~array(bitfield)&~array(useBitfield)&array(filterBitfield),
-       bitfieldLength, blocks);
+       ~array(bitfield)&~array(useBitfield)&array(filterBitfield), blocks);
   } else {
-    return getFirstNMissingIndex
+    return bitfield::getFirstNMissingIndex
       (std::back_inserter(out), n,
-       ~array(bitfield)&~array(useBitfield),
-       bitfieldLength, blocks);
+       ~array(bitfield)&~array(useBitfield), blocks);
   }
 }
 
diff --git a/src/BitfieldMan.h b/src/BitfieldMan.h
index 11ba95c5..0a6c3359 100644
--- a/src/BitfieldMan.h
+++ b/src/BitfieldMan.h
@@ -147,12 +147,13 @@ public:
    */
   bool getFirstMissingUnusedIndex(size_t& index) const;
   /**
-   * Stores at most n missing unused index in out. This function
-   * doesn't delete existing elements in out.
+   * Appends at most n missing unused index to out. This function
+   * doesn't delete existing elements in out.  Returns the number of
+   * appended elements.
    *
    * affected by filter
    */
-  bool getFirstNMissingUnusedIndex(std::vector<size_t>& out, size_t n) const;
+  size_t getFirstNMissingUnusedIndex(std::vector<size_t>& out, size_t n) const;
   /**
    * affected by filter
    */
diff --git a/src/Piece.cc b/src/Piece.cc
index 2d5a689b..79c848da 100644
--- a/src/Piece.cc
+++ b/src/Piece.cc
@@ -173,18 +173,17 @@ bool Piece::getMissingUnusedBlockIndex(size_t& index) const
   }
 }
 
-bool Piece::getMissingUnusedBlockIndex
+size_t Piece::getMissingUnusedBlockIndex
 (std::vector<size_t>& indexes, size_t n) const
 {
-  if(bitfield->getFirstNMissingUnusedIndex(indexes, n)) {
-    for(std::vector<size_t>::const_iterator i = indexes.begin();
+  size_t num = bitfield->getFirstNMissingUnusedIndex(indexes, n);
+  if(num) {
+    for(std::vector<size_t>::const_iterator i = indexes.end()-num;
         i != indexes.end(); ++i) {
       bitfield->setUseBit(*i);
     }
-    return true;
-  } else {
-    return false;
   }
+  return num;
 }
 
 bool Piece::getFirstMissingBlockIndexWithoutLock(size_t& index) const
diff --git a/src/Piece.h b/src/Piece.h
index 3177ac89..af2a7a92 100644
--- a/src/Piece.h
+++ b/src/Piece.h
@@ -98,11 +98,12 @@ public:
   // TODO This function only used by unit tests
   bool getMissingUnusedBlockIndex(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;
+  // Appends at most n missing unused block index to indexes. For all
+  // i in retrieved indexes, call bitfield->setUseBit(i). This
+  // function just append index to indexes and it doesn't remove
+  // anything from it. Returns the number of indexes to retrieved.
+  size_t getMissingUnusedBlockIndex
+  (std::vector<size_t>& indexes, size_t n) const;
 
   bool getFirstMissingBlockIndexWithoutLock(size_t& index) const;
   bool getAllMissingBlockIndexes(unsigned char* misbitfield,
diff --git a/src/bitfield.h b/src/bitfield.h
index e4088b88..0a253124 100644
--- a/src/bitfield.h
+++ b/src/bitfield.h
@@ -118,6 +118,32 @@ inline size_t countSetBit(const unsigned char* bitfield, size_t nbits)
 
 void flipBit(unsigned char* data, size_t length, size_t bitIndex);
 
+// Appends first at most n set bit index in bitfield to out.  bitfield
+// contains nbits bits.  Returns the number of appended bit indexes.
+template<typename Array, typename OutputIterator>
+size_t getFirstNMissingIndex
+(OutputIterator out, size_t n, const Array& bitfield, size_t nbits)
+{
+  if(n == 0) {
+    return 0;
+  }
+  const size_t origN = n;
+  const size_t bitfieldLength = (nbits+7)/8;
+  for(size_t i = 0; i < bitfieldLength; ++i) {
+    unsigned char mask = 128;
+    size_t tindex = i*8;
+    for(size_t bi = 0; bi < 8 && tindex < nbits; ++bi, mask >>= 1, ++tindex) {
+      if(bitfield[i] & mask) {
+        *out++ = tindex;
+        if(--n == 0) {
+          return origN;
+        }
+      }
+    }
+  }
+  return origN-n;
+}
+
 } // namespace bitfield
 
 } // namespace aria2