Use std::deque instead of std::list in IndexedList

We choose faster iteration over rare slower deletion in the middle.

3 files changed, 114 insertions, 2 deletions

diff --git a/test/IndexedListTest.cc b/test/IndexedListTest.cc
index 8673709f..fca9ed2c 100644
--- a/test/IndexedListTest.cc
+++ b/test/IndexedListTest.cc
@@ -22,6 +22,7 @@ class IndexedListTest:public CppUnit::TestFixture {
   CPPUNIT_TEST(testMove);
   CPPUNIT_TEST(testGet);
   CPPUNIT_TEST(testInsert);
+  CPPUNIT_TEST(testInsert_keyFunc);
   CPPUNIT_TEST_SUITE_END();
 public:
   void setUp()
@@ -34,6 +35,7 @@ public:
   void testMove();
   void testGet();
   void testInsert();
+  void testInsert_keyFunc();
 };
 
 CPPUNIT_TEST_SUITE_REGISTRATION( IndexedListTest );
@@ -203,9 +205,57 @@ void IndexedListTest::testGet()
   list.push_back(1, &b);
   CPPUNIT_ASSERT_EQUAL((int*)0, list.get(1000));
   CPPUNIT_ASSERT_EQUAL(&a, list.get(123));
+}
+
+namespace {
+struct KeyFunc {
+  int n;
+  KeyFunc(int n):n(n) {}
+  int operator()(const SharedHandle<std::string>& x)
+  {
+    return n++;
+  }
+};
+} // namespace
 
-  CPPUNIT_ASSERT(list.begin() == list.find(123));
-  CPPUNIT_ASSERT(list.end() == list.find(124));
+void IndexedListTest::testInsert_keyFunc()
+{
+  SharedHandle<std::string> s[] = {
+    SharedHandle<std::string>(new std::string("a")),
+    SharedHandle<std::string>(new std::string("b")),
+    SharedHandle<std::string>(new std::string("c")),
+    SharedHandle<std::string>(new std::string("d"))
+  };
+  size_t slen = sizeof(s)/sizeof(s[0]);
+  IndexedList<int, SharedHandle<std::string> > list;
+  list.insert(list.begin(), KeyFunc(0), vbegin(s), vend(s));
+  CPPUNIT_ASSERT_EQUAL((size_t)slen, list.size());
+  for(size_t i = 0; i < slen; ++i) {
+    CPPUNIT_ASSERT_EQUAL(*s[i], *list.get(i));
+  }
+  list.insert(list.begin()+2, KeyFunc(slen), vbegin(s), vend(s));
+  CPPUNIT_ASSERT_EQUAL((size_t)slen*2, list.size());
+  for(size_t i = slen; i < slen*2; ++i) {
+    CPPUNIT_ASSERT_EQUAL(*s[i - slen], *list.get(i));
+  }
+  IndexedList<int, SharedHandle<std::string> >::SeqType::iterator itr;
+  itr = list.begin();
+  CPPUNIT_ASSERT_EQUAL(std::string("a"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("b"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("a"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("b"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("c"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("d"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("c"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("d"), *(*itr++).second);
+
+  list.insert(list.begin(), KeyFunc(2*slen-1), vbegin(s), vend(s));
+  CPPUNIT_ASSERT_EQUAL((size_t)slen*3-1, list.size());
+  itr = list.begin();
+  CPPUNIT_ASSERT_EQUAL(std::string("b"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("c"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("d"), *(*itr++).second);
+  CPPUNIT_ASSERT_EQUAL(std::string("a"), *(*itr++).second);
 }
 
 void IndexedListTest::testInsert()
diff --git a/test/RequestGroupManTest.cc b/test/RequestGroupManTest.cc
index fa4fa39f..ade0633b 100644
--- a/test/RequestGroupManTest.cc
+++ b/test/RequestGroupManTest.cc
@@ -19,6 +19,7 @@
 #include "util.h"
 #include "DownloadEngine.h"
 #include "SelectEventPoll.h"
+#include "UriListParser.h"
 
 namespace aria2 {
 
@@ -31,6 +32,8 @@ class RequestGroupManTest : public CppUnit::TestFixture {
   CPPUNIT_TEST(testSaveServerStat);
   CPPUNIT_TEST(testChangeReservedGroupPosition);
   CPPUNIT_TEST(testFillRequestGroupFromReserver);
+  CPPUNIT_TEST(testFillRequestGroupFromReserver_uriParser);
+  CPPUNIT_TEST(testInsertReservedGroup);
   CPPUNIT_TEST_SUITE_END();
 private:
   SharedHandle<DownloadEngine> e_;
@@ -59,6 +62,8 @@ public:
   void testSaveServerStat();
   void testChangeReservedGroupPosition();
   void testFillRequestGroupFromReserver();
+  void testFillRequestGroupFromReserver_uriParser();
+  void testInsertReservedGroup();
 };
 
 
@@ -229,4 +234,59 @@ void RequestGroupManTest::testFillRequestGroupFromReserver()
   CPPUNIT_ASSERT_EQUAL((size_t)2, rgman_->getReservedGroups().size());
 }
 
+void RequestGroupManTest::testFillRequestGroupFromReserver_uriParser()
+{
+  SharedHandle<RequestGroup> rgs[] = {
+    createRequestGroup(0, 0, "mem1", "http://mem1", util::copy(option_)),
+    createRequestGroup(0, 0, "mem2", "http://mem2", util::copy(option_)),
+  };
+  rgs[0]->setPauseRequested(true);
+  for(SharedHandle<RequestGroup>* i = vbegin(rgs); i != vend(rgs); ++i) {
+    rgman_->addReservedGroup(*i);
+  }
+
+  SharedHandle<UriListParser> flp
+    (new UriListParser(A2_TEST_DIR"/filelist2.txt"));
+  rgman_->setUriListParser(flp);
+
+  rgman_->fillRequestGroupFromReserver(e_.get());
+
+  RequestGroupList::SeqType::const_iterator itr;
+  CPPUNIT_ASSERT_EQUAL((size_t)1, rgman_->getReservedGroups().size());
+  itr = rgman_->getReservedGroups().begin();
+  CPPUNIT_ASSERT_EQUAL(rgs[0]->getGID(), (*itr).second->getGID());
+  CPPUNIT_ASSERT_EQUAL((size_t)3, rgman_->getRequestGroups().size());
+}
+
+void RequestGroupManTest::testInsertReservedGroup()
+{
+  SharedHandle<RequestGroup> rgs1[] = {
+    SharedHandle<RequestGroup>(new RequestGroup(GroupId::create(),
+                                                util::copy(option_))),
+    SharedHandle<RequestGroup>(new RequestGroup(GroupId::create(),
+                                                util::copy(option_)))
+  };
+  SharedHandle<RequestGroup> rgs2[] = {
+    SharedHandle<RequestGroup>(new RequestGroup(GroupId::create(),
+                                                util::copy(option_))),
+    SharedHandle<RequestGroup>(new RequestGroup(GroupId::create(),
+                                                util::copy(option_)))
+  };
+  std::vector<SharedHandle<RequestGroup> > groups(vbegin(rgs1), vend(rgs1));
+  rgman_->insertReservedGroup(0, groups);
+  CPPUNIT_ASSERT_EQUAL((size_t)2, rgman_->getReservedGroups().size());
+  RequestGroupList::SeqType::const_iterator itr;
+  itr = rgman_->getReservedGroups().begin();
+  CPPUNIT_ASSERT_EQUAL(rgs1[0]->getGID(), (*itr++).second->getGID());
+  CPPUNIT_ASSERT_EQUAL(rgs1[1]->getGID(), (*itr++).second->getGID());
+
+  groups.assign(vbegin(rgs2), vend(rgs2));
+  rgman_->insertReservedGroup(1, groups);
+  CPPUNIT_ASSERT_EQUAL((size_t)4, rgman_->getReservedGroups().size());
+  itr = rgman_->getReservedGroups().begin();
+  ++itr;
+  CPPUNIT_ASSERT_EQUAL(rgs2[0]->getGID(), (*itr++).second->getGID());
+  CPPUNIT_ASSERT_EQUAL(rgs2[1]->getGID(), (*itr++).second->getGID());
+}
+
 } // namespace aria2
diff --git a/test/filelist2.txt b/test/filelist2.txt
new file mode 100644
index 00000000..e5cf33f6
--- /dev/null
+++ b/test/filelist2.txt
@@ -0,0 +1,2 @@
+http://fromfile1
+http://fromfile2