2010-07-15 Tatsuhiro Tsujikawa <t-tujikawa@users.sourceforge.net>

	FeedbackURISelector now tries to select URI whose host is least
	used in aria2 globally. Reverted the previous change.
	* src/AdaptiveURISelector.cc
	* src/AdaptiveURISelector.h
	* src/CreateRequestCommand.cc
	* src/FeedbackURISelector.cc
	* src/FeedbackURISelector.h
	* src/FileEntry.cc
	* src/FileEntry.h
	* src/InOrderURISelector.cc
	* src/InOrderURISelector.h
	* src/RequestGroupMan.cc
	* src/RequestGroupMan.h
	* src/URISelector.h
	* src/a2algo.h
	* test/FeedbackURISelectorTest.cc
	* test/InOrderURISelectorTest.cc

16 files changed, 167 insertions, 56 deletions

diff --git a/ChangeLog b/ChangeLog
index 5adf6292..0dfcbd27 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,25 @@
 2010-07-15  Tatsuhiro Tsujikawa  <t-tujikawa@users.sourceforge.net>
 
+	FeedbackURISelector now tries to select URI whose host is least
+	used in aria2 globally. Reverted the previous change.
+	* src/AdaptiveURISelector.cc
+	* src/AdaptiveURISelector.h
+	* src/CreateRequestCommand.cc
+	* src/FeedbackURISelector.cc
+	* src/FeedbackURISelector.h
+	* src/FileEntry.cc
+	* src/FileEntry.h
+	* src/InOrderURISelector.cc
+	* src/InOrderURISelector.h
+	* src/RequestGroupMan.cc
+	* src/RequestGroupMan.h
+	* src/URISelector.h
+	* src/a2algo.h
+	* test/FeedbackURISelectorTest.cc
+	* test/InOrderURISelectorTest.cc
+
+2010-07-15  Tatsuhiro Tsujikawa  <t-tujikawa@users.sourceforge.net>
+
 	Prefer untested server in FeedbackURISelector
 	* src/FeedbackURISelector.cc
 
diff --git a/src/AdaptiveURISelector.cc b/src/AdaptiveURISelector.cc
index 43e947a8..bed9a64c 100644
--- a/src/AdaptiveURISelector.cc
+++ b/src/AdaptiveURISelector.cc
@@ -73,7 +73,8 @@ AdaptiveURISelector::AdaptiveURISelector
 AdaptiveURISelector::~AdaptiveURISelector() {}
 
 std::string AdaptiveURISelector::select
-(FileEntry* fileEntry, const std::vector<std::string>& usedHosts)
+(FileEntry* fileEntry,
+ const std::vector<std::pair<size_t, std::string> >& usedHosts)
 {
   if(logger_->debug()) {
     logger_->debug("AdaptiveURISelector: called %d",
diff --git a/src/AdaptiveURISelector.h b/src/AdaptiveURISelector.h
index d2dae8dd..cb6d5fd2 100644
--- a/src/AdaptiveURISelector.h
+++ b/src/AdaptiveURISelector.h
@@ -79,7 +79,8 @@ public:
   virtual ~AdaptiveURISelector();
 
   virtual std::string select
-  (FileEntry* fileEntry, const std::vector<std::string>& usedHosts);
+  (FileEntry* fileEntry,
+   const std::vector<std::pair<size_t, std::string> >& usedHosts);
 
   virtual void tuneDownloadCommand(const std::deque<std::string>& uris,
                                    DownloadCommand* command);
diff --git a/src/CreateRequestCommand.cc b/src/CreateRequestCommand.cc
index c528ff19..cc62fef4 100644
--- a/src/CreateRequestCommand.cc
+++ b/src/CreateRequestCommand.cc
@@ -73,7 +73,7 @@ bool CreateRequestCommand::executeInternal()
     setFileEntry(getDownloadContext()->findFileEntryByOffset
                  (getSegments().front()->getPositionToWrite()));
   }
-  std::vector<std::string> usedHosts;
+  std::vector<std::pair<size_t, std::string> > usedHosts;
   getDownloadEngine()->getRequestGroupMan()->getUsedHosts(usedHosts);
   setRequest
     (getFileEntry()->getRequest(getRequestGroup()->getURISelector(),
diff --git a/src/FeedbackURISelector.cc b/src/FeedbackURISelector.cc
index e25e60f3..ab46952a 100644
--- a/src/FeedbackURISelector.cc
+++ b/src/FeedbackURISelector.cc
@@ -34,6 +34,7 @@
 /* copyright --> */
 #include "FeedbackURISelector.h"
 
+#include <cassert>
 #include <algorithm>
 
 #include "ServerStatMan.h"
@@ -41,12 +42,16 @@
 #include "Request.h"
 #include "A2STR.h"
 #include "FileEntry.h"
+#include "Logger.h"
+#include "LogFactory.h"
+#include "a2algo.h"
 
 namespace aria2 {
 
 FeedbackURISelector::FeedbackURISelector
 (const SharedHandle<ServerStatMan>& serverStatMan):
-  serverStatMan_(serverStatMan) {}
+  serverStatMan_(serverStatMan),
+  logger_(LogFactory::getInstance()) {}
 
 FeedbackURISelector::~FeedbackURISelector() {}
 
@@ -61,28 +66,77 @@ public:
 };
 
 std::string FeedbackURISelector::select
-(FileEntry* fileEntry, const std::vector<std::string>& usedHosts)
+(FileEntry* fileEntry,
+ const std::vector<std::pair<size_t, std::string> >& usedHosts)
 {
+  if(logger_->debug()) {
+    for(std::vector<std::pair<size_t, std::string> >::const_iterator i =
+          usedHosts.begin(), eoi = usedHosts.end(); i != eoi; ++i) {
+      logger_->debug("UsedHost=%lu, %s",
+                     static_cast<unsigned long>((*i).first),
+                     (*i).second.c_str());
+    }
+  }
   if(fileEntry->getRemainingUris().empty()) {
     return A2STR::NIL;
   }
   // Select URI with usedHosts first. If no URI is selected, then do
   // it again without usedHosts.
-  std::string uri = selectInternal(fileEntry->getRemainingUris(), usedHosts);
+  std::string uri = selectFaster(fileEntry->getRemainingUris(), usedHosts);
   if(uri.empty()) {
-    uri = selectInternal
-      (fileEntry->getRemainingUris(), std::vector<std::string>());
+    if(logger_->debug()) {
+      logger_->debug("No URI returned from selectFaster()");
+    }
+    uri = selectRarer(fileEntry->getRemainingUris(), usedHosts);
   } 
   if(!uri.empty()) {
     std::deque<std::string>& uris = fileEntry->getRemainingUris();
     uris.erase(std::find(uris.begin(), uris.end(), uri));
   }
+  if(logger_->debug()) {
+    logger_->debug("FeedbackURISelector selected %s", uri.c_str());
+  }
   return uri;
 }
 
-std::string FeedbackURISelector::selectInternal
+std::string FeedbackURISelector::selectRarer
 (const std::deque<std::string>& uris,
- const std::vector<std::string>& usedHosts)
+ const std::vector<std::pair<size_t, std::string> >& usedHosts)
+{
+  // pair of host and URI
+  std::vector<std::pair<std::string, std::string> > cands;
+  for(std::deque<std::string>::const_iterator i = uris.begin(),
+        eoi = uris.end(); i != eoi; ++i) {
+    Request r;
+    if(!r.setUri(*i)) {
+      continue;
+    }
+    SharedHandle<ServerStat> ss =
+      serverStatMan_->find(r.getHost(), r.getProtocol());
+    if(!ss.isNull() && ss->isError()) {
+      if(logger_->debug()) {
+        logger_->debug("Error not considered: %s", (*i).c_str());
+      }
+      continue;
+    }
+    cands.push_back(std::make_pair(r.getHost(), *i));
+  }
+  for(std::vector<std::pair<size_t, std::string> >::const_iterator i =
+        usedHosts.begin(), eoi = usedHosts.end(); i != eoi; ++i) {
+    for(std::vector<std::pair<std::string, std::string> >::const_iterator j =
+          cands.begin(), eoj = cands.end(); j != eoj; ++j) {
+      if((*i).second == (*j).first) {
+        return (*j).second;
+      }
+    }
+  }
+  assert(!uris.empty());
+  return uris.front();
+}
+
+std::string FeedbackURISelector::selectFaster
+(const std::deque<std::string>& uris,
+ const std::vector<std::pair<size_t, std::string> >& usedHosts)
 {
   // Use first 10 good URIs to introduce some randomness.
   const size_t NUM_URI = 10;
@@ -93,18 +147,21 @@ std::string FeedbackURISelector::selectInternal
   for(std::deque<std::string>::const_iterator i = uris.begin(),
         eoi = uris.end(); i != eoi && fastCands.size() < NUM_URI; ++i) {
     Request r;
-    r.setUri(*i);
-    if(std::find(usedHosts.begin(), usedHosts.end(), r.getHost())
-       != usedHosts.end()) {
+    if(!r.setUri(*i)) {
+      continue;
+    }
+    if(findSecond(usedHosts.begin(), usedHosts.end(), r.getHost()) !=
+       usedHosts.end()) {
+      if(logger_->debug()) {
+        logger_->debug("%s is in usedHosts, not considered", (*i).c_str());
+      }
       continue;
     }
     SharedHandle<ServerStat> ss =
       serverStatMan_->find(r.getHost(), r.getProtocol());
-    // We prefer untested one.
     if(ss.isNull()) {
-      return *i;
-    }
-    if(ss->isOK()) {
+      normCands.push_back(*i);
+    } else if(ss->isOK()) {
       if(ss->getDownloadSpeed() > SPEED_THRESHOLD) {
         fastCands.push_back(std::make_pair(ss, *i));
       } else {
@@ -114,19 +171,17 @@ std::string FeedbackURISelector::selectInternal
   }
   if(fastCands.empty()) {
     if(normCands.empty()) {
-      if(usedHosts.empty()) {
-        // All URIs are inspected but aria2 cannot find usable one.
-        // Return first URI anyway in this case.
-        return uris.front();
-      } else {
-        // If usedHosts is not empty, there is a possibility it
-        // includes usable host.
-        return A2STR::NIL;
-      }
+      return A2STR::NIL;
     } else {
+      if(logger_->debug()) {
+        logger_->debug("Selected from normCands");
+      }
       return normCands.front();
     }
   } else {
+    if(logger_->debug()) {
+      logger_->debug("Selected from fastCands");
+    }
     std::sort(fastCands.begin(), fastCands.end(), ServerStatFaster());
     return fastCands.front().second;
   }
diff --git a/src/FeedbackURISelector.h b/src/FeedbackURISelector.h
index 334ad48a..c748ef38 100644
--- a/src/FeedbackURISelector.h
+++ b/src/FeedbackURISelector.h
@@ -40,21 +40,30 @@
 namespace aria2 {
 
 class ServerStatMan;
+class Logger;
 
 class FeedbackURISelector:public URISelector {
 private:
   SharedHandle<ServerStatMan> serverStatMan_;
 
-  std::string selectInternal
+  Logger* logger_;
+
+  std::string selectRarer
+  (const std::deque<std::string>& uris,
+   const std::vector<std::pair<size_t, std::string> >& usedHosts);
+
+  std::string selectFaster
   (const std::deque<std::string>& uris,
-   const std::vector<std::string>& usedHosts);
+   const std::vector<std::pair<size_t, std::string> >& usedHosts);
 public:
   FeedbackURISelector(const SharedHandle<ServerStatMan>& serverStatMan);
 
   virtual ~FeedbackURISelector();
 
+  // This function expects ignoreHosts are ordered in ascending order.
   virtual std::string select
-  (FileEntry* fileEntry, const std::vector<std::string>& ignoreHosts);
+  (FileEntry* fileEntry,
+   const std::vector<std::pair<size_t, std::string> >& usedHosts);
 };
 
 } // namespace aria2
diff --git a/src/FileEntry.cc b/src/FileEntry.cc
index b6b8f925..982c6643 100644
--- a/src/FileEntry.cc
+++ b/src/FileEntry.cc
@@ -41,6 +41,7 @@
 #include "URISelector.h"
 #include "LogFactory.h"
 #include "wallclock.h"
+#include "a2algo.h"
 
 namespace aria2 {
 
@@ -121,7 +122,7 @@ SharedHandle<Request>
 FileEntry::getRequest
 (const SharedHandle<URISelector>& selector,
  bool uriReuse,
- const std::vector<std::string>& usedHosts,
+ const std::vector<std::pair<size_t, std::string> >& usedHosts,
  const std::string& referer,
  const std::string& method)
 {
@@ -131,7 +132,7 @@ FileEntry::getRequest
     for(std::deque<SharedHandle<Request> >::iterator i = requestPool_.begin(),
           eoi = requestPool_.end(); i != eoi; ++i) {
       r.setUri((*i)->getUri());
-      if(std::find(usedHosts.begin(), usedHosts.end(), r.getHost()) !=
+      if(findSecond(usedHosts.begin(), usedHosts.end(), r.getHost()) !=
          usedHosts.end()) {
         continue;
       }
diff --git a/src/FileEntry.h b/src/FileEntry.h
index e5f38f32..746d6ed6 100644
--- a/src/FileEntry.h
+++ b/src/FileEntry.h
@@ -168,7 +168,8 @@ public:
   SharedHandle<Request> getRequest
   (const SharedHandle<URISelector>& selector,
    bool uriReuse = true,
-   const std::vector<std::string>& usedHosts = std::vector<std::string>(),
+   const std::vector<std::pair<size_t, std::string> >& usedHosts
+     = std::vector<std::pair<size_t, std::string> >(),
    const std::string& referer = A2STR::NIL,
    const std::string& method = Request::METHOD_GET);
 
diff --git a/src/InOrderURISelector.cc b/src/InOrderURISelector.cc
index c91ad786..a0dc9975 100644
--- a/src/InOrderURISelector.cc
+++ b/src/InOrderURISelector.cc
@@ -43,7 +43,8 @@ InOrderURISelector::InOrderURISelector() {}
 InOrderURISelector::~InOrderURISelector() {}
 
 std::string InOrderURISelector::select
-(FileEntry* fileEntry, const std::vector<std::string>& usedHosts)
+(FileEntry* fileEntry,
+ const std::vector<std::pair<size_t, std::string> >& usedHosts)
 {
   std::deque<std::string>& uris = fileEntry->getRemainingUris();
   if(uris.empty()) {
diff --git a/src/InOrderURISelector.h b/src/InOrderURISelector.h
index e7fe35fc..c6234223 100644
--- a/src/InOrderURISelector.h
+++ b/src/InOrderURISelector.h
@@ -45,7 +45,8 @@ public:
   virtual ~InOrderURISelector();
 
   virtual std::string select
-  (FileEntry* fileEntry, const std::vector<std::string>& usedHosts);
+  (FileEntry* fileEntry,
+   const std::vector<std::pair<size_t, std::string> >& usedHosts);
 };
 
 } // namespace aria2
diff --git a/src/RequestGroupMan.cc b/src/RequestGroupMan.cc
index 6a3a5946..8f8d2573 100644
--- a/src/RequestGroupMan.cc
+++ b/src/RequestGroupMan.cc
@@ -896,7 +896,8 @@ bool RequestGroupMan::doesOverallUploadSpeedExceed()
     maxOverallUploadSpeedLimit_ < calculateStat().getUploadSpeed();
 }
 
-void RequestGroupMan::getUsedHosts(std::vector<std::string>& usedHosts)
+void RequestGroupMan::getUsedHosts
+(std::vector<std::pair<size_t, std::string> >& usedHosts)
 {
   Request r;
   for(std::deque<SharedHandle<RequestGroup> >::const_iterator i =
@@ -906,10 +907,22 @@ void RequestGroupMan::getUsedHosts(std::vector<std::string>& usedHosts)
     for(std::deque<SharedHandle<Request> >::const_iterator j =
           inFlightReqs.begin(), eoj = inFlightReqs.end(); j != eoj; ++j) {
       if(r.setUri((*j)->getUri())) {
-        usedHosts.push_back(r.getHost());
+        std::vector<std::pair<size_t, std::string> >::iterator k;
+        std::vector<std::pair<size_t, std::string> >::iterator eok =
+          usedHosts.end();
+        for(k =  usedHosts.begin(); k != eok; ++k) {
+          if((*k).second == r.getHost()) {
+            ++(*k).first;
+            break;
+          }
+        }
+        if(k == eok) {
+          usedHosts.push_back(std::make_pair(1, r.getHost()));
+        }
       }
     }
   }
+  std::sort(usedHosts.begin(), usedHosts.end());
 }
 
 } // namespace aria2
diff --git a/src/RequestGroupMan.h b/src/RequestGroupMan.h
index eda0b776..17128134 100644
--- a/src/RequestGroupMan.h
+++ b/src/RequestGroupMan.h
@@ -274,7 +274,8 @@ public:
     return queueCheck_;
   }
 
-  void getUsedHosts(std::vector<std::string>& usedHosts);
+  // Returns currently used hosts and its use count.
+  void getUsedHosts(std::vector<std::pair<size_t, std::string> >& usedHosts);
 };
 
 typedef SharedHandle<RequestGroupMan> RequestGroupManHandle;
diff --git a/src/URISelector.h b/src/URISelector.h
index 01448983..d05c020b 100644
--- a/src/URISelector.h
+++ b/src/URISelector.h
@@ -50,7 +50,8 @@ public:
   virtual ~URISelector() {}
 
   virtual std::string select
-  (FileEntry* fileEntry, const std::vector<std::string>& usedHosts) = 0;
+  (FileEntry* fileEntry,
+   const std::vector<std::pair<size_t, std::string> >& usedHosts) = 0;
 
   virtual void tuneDownloadCommand(const std::deque<std::string>& uris,
                                    DownloadCommand* command) {};
diff --git a/src/a2algo.h b/src/a2algo.h
index 377ca793..aede507d 100644
--- a/src/a2algo.h
+++ b/src/a2algo.h
@@ -94,6 +94,19 @@ static void forEachMemFunSH(InputIterator first, InputIterator last,
   }
 }
 
+template<typename InputIterator, typename T>
+InputIterator findSecond
+(InputIterator first, InputIterator last, const T& t)
+{
+  for(; first != last; ++first) {
+    if((*first).second == t) {
+      return first;
+    }
+  }
+  return last;
+}
+
+
 } // namespace aria2
 
 #endif // _D_A2_ALGO_H_
diff --git a/test/FeedbackURISelectorTest.cc b/test/FeedbackURISelectorTest.cc
index 59bc43ce..46a1d2b1 100644
--- a/test/FeedbackURISelectorTest.cc
+++ b/test/FeedbackURISelectorTest.cc
@@ -59,8 +59,8 @@ CPPUNIT_TEST_SUITE_REGISTRATION(FeedbackURISelectorTest);
 
 void FeedbackURISelectorTest::testSelect_withoutServerStat()
 {
-  std::vector<std::string> usedHosts;
-  // Without ServerStat, selector returns first URI
+  std::vector<std::pair<size_t, std::string> > usedHosts;
+  // Without ServerStat and usedHosts, selector returns first URI
   std::string uri = sel->select(&fileEntry_, usedHosts);
   CPPUNIT_ASSERT_EQUAL(std::string("http://alpha/file"), uri);
   CPPUNIT_ASSERT_EQUAL((size_t)2, fileEntry_.getRemainingUris().size());
@@ -75,7 +75,7 @@ void FeedbackURISelectorTest::testSelect()
   SharedHandle<ServerStat> alphaHTTP(new ServerStat("alpha", "http"));
   alphaHTTP->updateDownloadSpeed(180000);
   alphaHTTP->setError();
-  std::vector<std::string> usedHosts;
+  std::vector<std::pair<size_t, std::string> > usedHosts;
 
   ssm->add(bravo);
   ssm->add(alphaFTP);
@@ -92,26 +92,19 @@ void FeedbackURISelectorTest::testSelect()
 
 void FeedbackURISelectorTest::testSelect_withUsedHosts()
 {
-  SharedHandle<ServerStat> bravo(new ServerStat("bravo", "http"));
-  bravo->updateDownloadSpeed(100000);
-  SharedHandle<ServerStat> alphaHTTP(new ServerStat("alpha", "http"));
-  alphaHTTP->updateDownloadSpeed(180000);
-  alphaHTTP->setError();
-  std::vector<std::string> usedHosts;
-  usedHosts.push_back("bravo");
-
-  ssm->add(bravo);
-  ssm->add(alphaHTTP);
+  std::vector<std::pair<size_t, std::string> > usedHosts;
+  usedHosts.push_back(std::make_pair(1, "bravo"));
+  usedHosts.push_back(std::make_pair(2, "alpha"));
 
-  CPPUNIT_ASSERT_EQUAL(std::string("ftp://alpha/file"),
+  CPPUNIT_ASSERT_EQUAL(std::string("http://bravo/file"),
                        sel->select(&fileEntry_, usedHosts));
   CPPUNIT_ASSERT_EQUAL((size_t)2, fileEntry_.getRemainingUris().size());
 
-  CPPUNIT_ASSERT_EQUAL(std::string("http://bravo/file"),
+  CPPUNIT_ASSERT_EQUAL(std::string("http://alpha/file"),
                        sel->select(&fileEntry_, usedHosts));
   CPPUNIT_ASSERT_EQUAL((size_t)1, fileEntry_.getRemainingUris().size());
 
-  CPPUNIT_ASSERT_EQUAL(std::string("http://alpha/file"),
+  CPPUNIT_ASSERT_EQUAL(std::string("ftp://alpha/file"),
                        sel->select(&fileEntry_, usedHosts));
   CPPUNIT_ASSERT_EQUAL((size_t)0, fileEntry_.getRemainingUris().size());
 }
@@ -122,7 +115,7 @@ void FeedbackURISelectorTest::testSelect_skipErrorHost()
   alphaHTTP->setError();
   SharedHandle<ServerStat> alphaFTP(new ServerStat("alpha", "ftp"));
   alphaFTP->setError();
-  std::vector<std::string> usedHosts;
+  std::vector<std::pair<size_t, std::string> > usedHosts;
 
   ssm->add(alphaHTTP);
   ssm->add(alphaFTP);
diff --git a/test/InOrderURISelectorTest.cc b/test/InOrderURISelectorTest.cc
index c828d46a..765d9b04 100644
--- a/test/InOrderURISelectorTest.cc
+++ b/test/InOrderURISelectorTest.cc
@@ -45,7 +45,7 @@ CPPUNIT_TEST_SUITE_REGISTRATION(InOrderURISelectorTest);
 
 void InOrderURISelectorTest::testSelect()
 {
-  std::vector<std::string> usedHosts;
+  std::vector<std::pair<size_t, std::string> > usedHosts;
   CPPUNIT_ASSERT_EQUAL(std::string("http://alpha/file"),
                        sel->select(&fileEntry_, usedHosts));
   CPPUNIT_ASSERT_EQUAL(std::string("ftp://alpha/file"),