2008-05-11 Tatsuhiro Tsujikawa <tujikawa at rednoah dot com>

	Implemented rarest piece first piece selection strategy.
	* src/AbstractBtMessage.cc
	* src/AbstractBtMessage.h
	* src/BitfieldMan.cc
	* src/BitfieldMan.h
	* src/BtBitfieldMessage.cc
	* src/BtHaveAllMessage.cc
	* src/BtHaveMessage.cc
	* src/DefaultPieceStorage.cc
	* src/DefaultPieceStorage.h
	* src/PeerInteractionCommand.cc
	* src/PieceStorage.h
	* src/UnknownLengthPieceStorage.h

12 files changed, 271 insertions, 3 deletions

diff --git a/src/AbstractBtMessage.cc b/src/AbstractBtMessage.cc
index bee248c7..feb9e770 100644
--- a/src/AbstractBtMessage.cc
+++ b/src/AbstractBtMessage.cc
@@ -107,6 +107,11 @@ SharedHandle<BtContext> AbstractBtMessage::getBtContext() const
   return btContext;
 }
 
+void AbstractBtMessage::setPieceStorage(const SharedHandle<PieceStorage>& pieceStorage)
+{
+  this->pieceStorage = pieceStorage;
+}
+
 void AbstractBtMessage::setBtMessageDispatcher(const WeakHandle<BtMessageDispatcher>& dispatcher)
 {
   this->dispatcher = dispatcher;
diff --git a/src/AbstractBtMessage.h b/src/AbstractBtMessage.h
index 67858565..d1663eb3 100644
--- a/src/AbstractBtMessage.h
+++ b/src/AbstractBtMessage.h
@@ -136,6 +136,8 @@ public:
 
   SharedHandle<BtContext> getBtContext() const;
 
+  void setPieceStorage(const SharedHandle<PieceStorage>& pieceStorage);
+
   void setBtMessageDispatcher(const WeakHandle<BtMessageDispatcher>& dispatcher);
 
   void setPeerConnection(const WeakHandle<PeerConnection>& peerConnection);
diff --git a/src/BitfieldMan.cc b/src/BitfieldMan.cc
index 42cc871e..d89deb29 100644
--- a/src/BitfieldMan.cc
+++ b/src/BitfieldMan.cc
@@ -424,6 +424,19 @@ std::deque<size_t> BitfieldMan::getAllMissingIndexes(const unsigned char* peerBi
   return getAllMissingIndexes(bf, bitfieldLength);
 }
 
+std::deque<size_t> BitfieldMan::getAllMissingUnusedIndexes(const unsigned char* peerBitfield, size_t peerBitfieldLength) const {
+  if(bitfieldLength != peerBitfieldLength) {
+    return std::deque<size_t>();
+  }
+  array_fun<unsigned char> bf = array_and(array_and(array_negate(bitfield),
+						    array_negate(useBitfield)),
+					  peerBitfield);
+  if(filterEnabled) {
+    bf = array_and(bf, filterBitfield);
+  }
+  return getAllMissingIndexes(bf, bitfieldLength);
+}
+
 size_t BitfieldMan::countMissingBlock() const {
   return cachedNumMissingBlock;
 }
diff --git a/src/BitfieldMan.h b/src/BitfieldMan.h
index ed0401c6..9e8ea0e0 100644
--- a/src/BitfieldMan.h
+++ b/src/BitfieldMan.h
@@ -145,6 +145,11 @@ public:
   /**
    * affected by filter
    */
+  std::deque<size_t> getAllMissingUnusedIndexes(const unsigned char* bitfield,
+						size_t len) const;
+  /**
+   * affected by filter
+   */
   size_t countMissingBlock() const;
   /**
    * affected by filter
diff --git a/src/BtBitfieldMessage.cc b/src/BtBitfieldMessage.cc
index 4cd935ef..13541777 100644
--- a/src/BtBitfieldMessage.cc
+++ b/src/BtBitfieldMessage.cc
@@ -39,6 +39,7 @@
 #include "message.h"
 #include "Peer.h"
 #include "StringFormat.h"
+#include "PieceStorage.h"
 #include <cstring>
 
 namespace aria2 {
@@ -72,6 +73,7 @@ BtBitfieldMessage::create(const unsigned char* data, size_t dataLength)
 }
 
 void BtBitfieldMessage::doReceivedAction() {
+  pieceStorage->updatePieceStats(bitfield, bitfieldLength, peer->getBitfield());
   peer->setBitfield(bitfield, bitfieldLength);
 }
 
diff --git a/src/BtHaveAllMessage.cc b/src/BtHaveAllMessage.cc
index 07a78f43..14469de7 100644
--- a/src/BtHaveAllMessage.cc
+++ b/src/BtHaveAllMessage.cc
@@ -38,6 +38,7 @@
 #include "message.h"
 #include "Peer.h"
 #include "StringFormat.h"
+#include "PieceStorage.h"
 
 namespace aria2 {
 
@@ -61,7 +62,9 @@ void BtHaveAllMessage::doReceivedAction() {
       (StringFormat("%s received while fast extension is disabled",
 		    toString().c_str()).str());
   }
+  pieceStorage->subtractPieceStats(peer->getBitfield(), peer->getBitfieldLength());
   peer->setAllBitfield();
+  pieceStorage->addPieceStats(peer->getBitfield(), peer->getBitfieldLength());
 }
 
 size_t BtHaveAllMessage::MESSAGE_LENGTH = 5;
diff --git a/src/BtHaveMessage.cc b/src/BtHaveMessage.cc
index 7aa445f9..92489311 100644
--- a/src/BtHaveMessage.cc
+++ b/src/BtHaveMessage.cc
@@ -39,6 +39,7 @@
 #include "message.h"
 #include "Peer.h"
 #include "StringFormat.h"
+#include "PieceStorage.h"
 
 namespace aria2 {
 
@@ -59,6 +60,7 @@ BtHaveMessageHandle BtHaveMessage::create(const unsigned char* data, size_t data
 
 void BtHaveMessage::doReceivedAction() {
   peer->updateBitfield(index, 1);
+  pieceStorage->addPieceStats(index);
 }
 
 size_t BtHaveMessage::MESSAGE_LENGTH = 9;
diff --git a/src/DefaultPieceStorage.cc b/src/DefaultPieceStorage.cc
index 6bbd9739..c52840ad 100644
--- a/src/DefaultPieceStorage.cc
+++ b/src/DefaultPieceStorage.cc
@@ -58,16 +58,57 @@
 
 namespace aria2 {
 
+class GenPieceStat {
+private:
+  size_t _index;
+public:
+  GenPieceStat():_index(0) {}
+
+  SharedHandle<PieceStat> operator()()
+  {
+    return SharedHandle<PieceStat>(new PieceStat(_index++));
+  }
+};
+
+class PieceRarer
+{
+public:
+  bool operator()(const SharedHandle<PieceStat>& left,
+		  const SharedHandle<PieceStat>& right)
+  {
+    if(left->getCount() == right->getCount()) {
+      return left->getOrder() < right->getOrder();
+    } else {
+      return left->getCount() < right->getCount();
+    }
+  }
+};
+
 DefaultPieceStorage::DefaultPieceStorage(const DownloadContextHandle& downloadContext, const Option* option):
   downloadContext(downloadContext),
   _diskWriterFactory(new DefaultDiskWriterFactory()),
   endGamePieceNum(END_GAME_PIECE_NUM),
-  option(option)
+  option(option),
+  _pieceStats(downloadContext->getNumPieces())
 {
   bitfieldMan =
     BitfieldManFactory::getFactoryInstance()->
     createBitfieldMan(downloadContext->getPieceLength(),
 		      downloadContext->getTotalLength());
+
+  std::generate(_pieceStats.begin(), _pieceStats.end(), GenPieceStat());
+  _sortedPieceStats = _pieceStats;
+  // we need some randomness in ordering.
+  std::random_shuffle(_sortedPieceStats.begin(), _sortedPieceStats.end());
+  {
+    size_t order = 0;
+    for(std::deque<SharedHandle<PieceStat> >::iterator i = _sortedPieceStats.begin();
+	i != _sortedPieceStats.end(); ++i) {
+      (*i)->setOrder(order++);
+    }
+  }
+  std::sort(_sortedPieceStats.begin(), _sortedPieceStats.end(), PieceRarer());
+
   logger = LogFactory::getInstance();
 }
 
@@ -86,14 +127,38 @@ bool DefaultPieceStorage::isEndGame()
   return bitfieldMan->countMissingBlock() <= endGamePieceNum;
 }
 
+class FindRarestPiece
+{
+private:
+  const std::deque<size_t>& _indexes;
+public:
+  FindRarestPiece(const std::deque<size_t>& indexes):_indexes(indexes) {}
+
+  bool operator()(const SharedHandle<PieceStat>& pieceStat)
+  {
+    return std::binary_search(_indexes.begin(), _indexes.end(), pieceStat->getIndex());
+  }
+};
+
 bool DefaultPieceStorage::getMissingPieceIndex(size_t& index, const PeerHandle& peer)
 {
   if(isEndGame()) {
     return bitfieldMan->getMissingIndex(index, peer->getBitfield(),
 					peer->getBitfieldLength());
   } else {
-    return bitfieldMan->getMissingUnusedIndex(index, peer->getBitfield(),
+    std::deque<size_t> indexes =
+      bitfieldMan->getAllMissingUnusedIndexes(peer->getBitfield(),
 					      peer->getBitfieldLength());
+    if(indexes.empty()) {
+      return false;
+    } else {
+      std::sort(indexes.begin(), indexes.end());
+      std::deque<SharedHandle<PieceStat> >::const_iterator i =
+	std::find_if(_sortedPieceStats.begin(), _sortedPieceStats.end(),
+		     FindRarestPiece(indexes));
+      index = (*i)->getIndex();
+      return true;
+    }
   }
 }
 
@@ -285,6 +350,7 @@ void DefaultPieceStorage::completePiece(const PieceHandle& piece)
   }
   bitfieldMan->setBit(piece->getIndex());
   bitfieldMan->unsetUseBit(piece->getIndex());
+  addPieceStats(piece->getIndex());
   if(downloadFinished()) {
     diskAdaptor->onDownloadComplete();
     if(isSelectiveDownloadingMode()) {
@@ -455,8 +521,9 @@ void DefaultPieceStorage::setBitfield(const unsigned char* bitfield,
 				      size_t bitfieldLength)
 {
   bitfieldMan->setBitfield(bitfield, bitfieldLength);
+  addPieceStats(bitfield, bitfieldLength);
 }
-  
+
 size_t DefaultPieceStorage::getBitfieldLength()
 {
   return bitfieldMan->getBitfieldLength();
@@ -576,4 +643,111 @@ void DefaultPieceStorage::setDiskWriterFactory(const DiskWriterFactoryHandle& di
   _diskWriterFactory = diskWriterFactory;
 }
 
+void DefaultPieceStorage::addPieceStats(const unsigned char* bitfield,
+					size_t bitfieldLength)
+{
+  size_t index = 0;
+  for(size_t bi = 0; bi < bitfieldLength; ++bi) {
+    
+    for(size_t i = 0; i < 8; ++i, ++index) {
+      unsigned char mask = 128 >> i;
+      if(bitfield[bi]&mask) {
+	_pieceStats[index]->addCount();
+      }
+    }
+
+  }
+  std::sort(_sortedPieceStats.begin(), _sortedPieceStats.end(), PieceRarer());
+}
+
+void DefaultPieceStorage::subtractPieceStats(const unsigned char* bitfield,
+					     size_t bitfieldLength)
+{
+  size_t index = 0;
+  for(size_t bi = 0; bi < bitfieldLength; ++bi) {
+    
+    for(size_t i = 0; i < 8; ++i, ++index) {
+      unsigned char mask = 128 >> i;
+      if(bitfield[bi]&mask) {
+	_pieceStats[index]->subCount();
+      }
+    }
+
+  }
+  std::sort(_sortedPieceStats.begin(), _sortedPieceStats.end(), PieceRarer());
+}
+
+void DefaultPieceStorage::updatePieceStats(const unsigned char* newBitfield,
+					   size_t newBitfieldLength,
+					   const unsigned char* oldBitfield)
+{
+  size_t index = 0;
+  for(size_t bi = 0; bi < newBitfieldLength; ++bi) {
+    
+    for(size_t i = 0; i < 8; ++i, ++index) {
+      unsigned char mask = 128 >> i;
+      if((newBitfield[bi]&mask) && !(oldBitfield[bi]&mask)) {
+	_pieceStats[index]->addCount();
+      } else if(!(newBitfield[bi]&mask) && (oldBitfield[bi]&mask)) {
+	_pieceStats[index]->subCount();
+      }
+    }
+
+  }
+  std::sort(_sortedPieceStats.begin(), _sortedPieceStats.end(), PieceRarer());
+}
+
+void DefaultPieceStorage::addPieceStats(size_t index)
+{
+  std::deque<SharedHandle<PieceStat> >::iterator cur =
+    std::lower_bound(_sortedPieceStats.begin(), _sortedPieceStats.end(),
+		     _pieceStats[index], PieceRarer());
+
+  (*cur)->addCount();
+
+  std::deque<SharedHandle<PieceStat> >::iterator last =
+    std::upper_bound(cur+1, _sortedPieceStats.end(), *cur, PieceRarer());
+
+  std::sort(cur, last, PieceRarer());
+//   for(std::deque<SharedHandle<PieceStat> >::const_iterator i = _sortedPieceStats.begin(); i != _sortedPieceStats.end(); ++i) {
+//     logger->debug("index = %u, count = %u", (*i)->getIndex(), (*i)->getCount());
+//   }
+}
+
+PieceStat::PieceStat(size_t index):_order(0), _index(index), _count(0) {}
+
+void PieceStat::addCount()
+{
+  if(_count < SIZE_MAX) {
+    ++_count;
+  }
+}
+
+void PieceStat::subCount()
+{
+  if(_count > 0) {
+    --_count;
+  }
+}
+
+size_t PieceStat::getIndex() const
+{
+  return _index;
+}
+
+size_t PieceStat::getCount() const
+{
+  return _count;
+}
+
+void PieceStat::setOrder(size_t order)
+{
+  _order = order;
+}
+
+size_t PieceStat::getOrder() const
+{
+  return _order;
+}
+
 } // namespace aria2
diff --git a/src/DefaultPieceStorage.h b/src/DefaultPieceStorage.h
index 61fe5a70..be068047 100644
--- a/src/DefaultPieceStorage.h
+++ b/src/DefaultPieceStorage.h
@@ -67,6 +67,23 @@ public:
 
 typedef std::deque<HaveEntry> Haves;
 
+class PieceStat {
+private:
+  size_t _order;
+  size_t _index;
+  size_t _count;
+public:
+  PieceStat(size_t index);
+
+  void addCount();
+  void subCount();
+
+  size_t getOrder() const;
+  void setOrder(size_t order);
+  size_t getIndex() const;
+  size_t getCount() const;
+};
+
 class DefaultPieceStorage : public PieceStorage {
 private:
   SharedHandle<DownloadContext> downloadContext;
@@ -74,10 +91,14 @@ private:
   SharedHandle<DiskAdaptor> diskAdaptor;
   SharedHandle<DiskWriterFactory> _diskWriterFactory;
   std::deque<SharedHandle<Piece> > usedPieces;
+
   size_t endGamePieceNum;
   Logger* logger;
   const Option* option;
   Haves haves;
+
+  std::deque<SharedHandle<PieceStat> > _pieceStats;
+  std::deque<SharedHandle<PieceStat> > _sortedPieceStats;
   
   bool getMissingPieceIndex(size_t& index, const SharedHandle<Peer>& peer);
   bool getMissingFastPieceIndex(size_t& index, const SharedHandle<Peer>& peer);
@@ -177,6 +198,18 @@ public:
 
   virtual std::deque<SharedHandle<Piece> > getInFlightPieces();
 
+  virtual void addPieceStats(size_t index);
+
+  virtual void addPieceStats(const unsigned char* bitfield,
+			     size_t bitfieldLength);
+  
+  virtual void subtractPieceStats(const unsigned char* bitfield,
+				  size_t bitfieldLength);
+
+  virtual void updatePieceStats(const unsigned char* newBitfield,
+				size_t newBitfieldLength,
+				const unsigned char* oldBitfield);
+
   /**
    * This method is made private for test purpose only.
    */
diff --git a/src/PeerInteractionCommand.cc b/src/PeerInteractionCommand.cc
index a954081a..edb6bbf2 100644
--- a/src/PeerInteractionCommand.cc
+++ b/src/PeerInteractionCommand.cc
@@ -62,6 +62,7 @@
 #include "DHTNode.h"
 #include "DHTSetup.h"
 #include "DHTRegistry.h"
+#include "PieceStorage.h"
 #include <algorithm>
 
 namespace aria2 {
@@ -169,6 +170,8 @@ PeerInteractionCommand::PeerInteractionCommand(int32_t cuid,
 }
 
 PeerInteractionCommand::~PeerInteractionCommand() {
+  pieceStorage->subtractPieceStats(peer->getBitfield(),
+				   peer->getBitfieldLength());
   peer->releaseSessionResource();
   PEER_OBJECT_CLUSTER(btContext)->unregisterHandle(peer->getID());
 					
diff --git a/src/PieceStorage.h b/src/PieceStorage.h
index 341371b7..d101c2f6 100644
--- a/src/PieceStorage.h
+++ b/src/PieceStorage.h
@@ -204,6 +204,19 @@ public:
   virtual size_t countInFlightPiece() = 0;
 
   virtual std::deque<SharedHandle<Piece> > getInFlightPieces() = 0;
+
+  virtual void addPieceStats(size_t index) = 0;
+
+  virtual void addPieceStats(const unsigned char* bitfield,
+			     size_t bitfieldLength) = 0;
+
+  virtual void subtractPieceStats(const unsigned char* bitfield,
+				  size_t bitfieldLength) = 0;
+
+  virtual void updatePieceStats(const unsigned char* newBitfield,
+				size_t newBitfieldLength,
+				const unsigned char* oldBitfield) = 0;
+
 };
 
 typedef SharedHandle<PieceStorage> PieceStorageHandle;
diff --git a/src/UnknownLengthPieceStorage.h b/src/UnknownLengthPieceStorage.h
index 460faa66..3e7b5b94 100644
--- a/src/UnknownLengthPieceStorage.h
+++ b/src/UnknownLengthPieceStorage.h
@@ -250,6 +250,19 @@ public:
 
   virtual std::deque<SharedHandle<Piece> > getInFlightPieces();
 
+  virtual void addPieceStats(size_t index) {}
+
+  virtual void addPieceStats(const unsigned char* bitfield,
+			     size_t bitfieldLength) {}
+
+  virtual void subtractPieceStats(const unsigned char* bitfield,
+				  size_t bitfieldLength) {}
+
+  virtual void updatePieceStats(const unsigned char* newBitfield,
+				size_t newBitfieldLength,
+				const unsigned char* oldBitfield) {}
+
+
   void setDiskWriterFactory(const SharedHandle<DiskWriterFactory>& diskWriterFactory);
 };