From a6b02840fa79e3e7cb82e472ff5660fda86842c1 Mon Sep 17 00:00:00 2001
From: Tatsuhiro Tsujikawa <tatsuhiro.t@gmail.com>
Date: Sat, 28 Mar 2009 13:29:38 +0000
Subject: 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
---
 src/RarestPieceSelector.cc | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

(limited to 'src/RarestPieceSelector.cc')

diff --git a/src/RarestPieceSelector.cc b/src/RarestPieceSelector.cc
index fe5ca304..0b7aabb5 100644
--- a/src/RarestPieceSelector.cc
+++ b/src/RarestPieceSelector.cc
@@ -34,6 +34,7 @@
 /* copyright --> */
 #include "RarestPieceSelector.h"
 
+#include <cassert>
 #include <algorithm>
 
 #include "SimpleRandomizer.h"
@@ -121,23 +122,26 @@ RarestPieceSelector::RarestPieceSelector(size_t pieceNum, bool randomShuffle):
 class FindRarestPiece
 {
 private:
-  const std::deque<size_t>& _indexes;
+  const unsigned char* _misbitfield;
+  size_t _numbits;
 public:
-  FindRarestPiece(const std::deque<size_t>& indexes):_indexes(indexes) {}
+  FindRarestPiece(const unsigned char* misbitfield, size_t numbits):
+    _misbitfield(misbitfield), _numbits(numbits) {}
 
   bool operator()(const size_t& index)
   {
-    return std::binary_search(_indexes.begin(), _indexes.end(), index);
+    assert(index < _numbits);
+    unsigned char mask = (128 >> (index%8));
+    return _misbitfield[index/8]&mask;
   }
 };
 
 bool RarestPieceSelector::select
-(size_t& index,
- const std::deque<size_t>& candidateIndexes) const
+(size_t& index, const unsigned char* bitfield, size_t nbits) const
 {
   std::vector<size_t>::const_iterator i =
     std::find_if(_sortedPieceStatIndexes.begin(), _sortedPieceStatIndexes.end(),
-		 FindRarestPiece(candidateIndexes));
+		 FindRarestPiece(bitfield, nbits));
   if(i == _sortedPieceStatIndexes.end()) {
     return false;
   } else {
-- 
cgit