From ccc552cec90b9e71ca36db763fe2ea95bb2dd2ca Mon Sep 17 00:00:00 2001
From: Tatsuhiro Tsujikawa <tatsuhiro.t@gmail.com>
Date: Wed, 10 Feb 2010 15:07:06 +0000
Subject: 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
---
 src/BitfieldMan.cc | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

(limited to 'src/BitfieldMan.cc')

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) {
-- 
cgit