summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/IndexedList.h130
-rw-r--r--src/RequestGroupMan.cc43
-rw-r--r--test/IndexedListTest.cc54
-rw-r--r--test/RequestGroupManTest.cc60
-rw-r--r--test/filelist2.txt2
5 files changed, 205 insertions, 84 deletions
diff --git a/src/IndexedList.h b/src/IndexedList.h
index fac92d28..5fc68ae4 100644
--- a/src/IndexedList.h
+++ b/src/IndexedList.h
@@ -37,8 +37,10 @@
#include "common.h"
-#include <list>
+#include <deque>
#include <map>
+#include <vector>
+#include <algorithm>
namespace aria2 {
@@ -48,15 +50,14 @@ enum A2_HOW {
A2_POS_END
};
-// List with O(logN) look-up using std::map as an index.
template<typename KeyType, typename ValuePtrType>
class IndexedList {
public:
IndexedList() {}
~IndexedList() {}
- typedef std::list<std::pair<KeyType, ValuePtrType> > SeqType;
- typedef std::map<KeyType, typename SeqType::iterator> IndexType;
+ typedef std::deque<std::pair<KeyType, ValuePtrType> > SeqType;
+ typedef std::map<KeyType, ValuePtrType> IndexType;
// Inserts (|key|, |value|) to the end of the list. If the same key
// has been already added, this function fails. This function
@@ -65,10 +66,9 @@ public:
{
typename IndexType::iterator i = index_.lower_bound(key);
if(i == index_.end() || (*i).first != key) {
- seq_.push_back(std::make_pair(key, value));
- typename SeqType::iterator j = seq_.end();
- --j;
- index_.insert(i, std::make_pair(key, j));
+ std::pair<KeyType, ValuePtrType> p(key, value);
+ seq_.push_back(p);
+ index_.insert(i, p);
return true;
} else {
return false;
@@ -82,9 +82,9 @@ public:
{
typename IndexType::iterator i = index_.lower_bound(key);
if(i == index_.end() || (*i).first != key) {
- seq_.push_front(std::make_pair(key, value));
- typename SeqType::iterator j = seq_.begin();
- index_.insert(i, std::make_pair(key, j));
+ std::pair<KeyType, ValuePtrType> p(key, value);
+ seq_.push_front(p);
+ index_.insert(i, p);
return true;
} else {
return false;
@@ -105,8 +105,9 @@ public:
if(i == index_.end() || (*i).first != key) {
typename SeqType::iterator j = seq_.begin();
std::advance(j, dest);
- j = seq_.insert(j, std::make_pair(key, value));
- index_.insert(i, std::make_pair(key, j));
+ std::pair<KeyType, ValuePtrType> p(key, value);
+ j = seq_.insert(j, p);
+ index_.insert(i, p);
return j;
} else {
return seq_.end();
@@ -116,32 +117,61 @@ public:
// Inserts (|key|, |value|) to the position |dest|. If the same key
// has been already added, this function fails. This function
// returns the iterator to the newly added element if it is
- // succeeds, or end(). Complexity: O(logN)
+ // succeeds, or end(). Complexity: O(logN) if inserted to the first
+ // or last, otherwise O(N)
typename SeqType::iterator insert(typename SeqType::iterator dest,
KeyType key,
ValuePtrType value)
{
typename IndexType::iterator i = index_.lower_bound(key);
if(i == index_.end() || (*i).first != key) {
- dest = seq_.insert(dest, std::make_pair(key, value));
- index_.insert(i, std::make_pair(key, dest));
+ std::pair<KeyType, ValuePtrType> p(key, value);
+ dest = seq_.insert(dest, p);
+ index_.insert(i, p);
return dest;
} else {
return seq_.end();
}
}
+ // Inserts values in iterator range [first, last). The key for each
+ // value is retrieved by functor |keyFunc|. The insertion position
+ // is given by |dest|.
+ template<typename KeyFunc, typename InputIterator>
+ void insert(typename SeqType::iterator dest, KeyFunc keyFunc,
+ InputIterator first, InputIterator last)
+ {
+ std::vector<typename SeqType::value_type> v;
+ v.reserve(std::distance(first, last));
+ for(; first != last; ++first) {
+ KeyType key = keyFunc(*first);
+ typename IndexType::iterator i = index_.lower_bound(key);
+ if(i == index_.end() || (*i).first != key) {
+ std::pair<KeyType, ValuePtrType> p(key, *first);
+ v.push_back(p);
+ index_.insert(i, p);
+ }
+ }
+ seq_.insert(dest, v.begin(), v.end());
+ }
+
// Removes |key| from the list. If the element is not found, this
// function fails. This function returns true if it
- // succeeds. Complexity: O(logN)
+ // succeeds. Complexity: O(N)
bool erase(KeyType key)
{
typename IndexType::iterator i = index_.find(key);
if(i == index_.end()) {
return false;
}
- seq_.erase((*i).second);
index_.erase(i);
+ for(typename SeqType::iterator j = seq_.begin(), eoj = seq_.end();
+ j != eoj; ++j) {
+ if((*j).first == key) {
+ seq_.erase(j);
+ break;
+ }
+ }
return true;
}
@@ -174,40 +204,38 @@ public:
if(idxent == index_.end()) {
return -1;
}
+ typename SeqType::iterator x = seq_.begin(), eseq = seq_.end();
+ for(; x != eseq; ++x) {
+ if((*x).first == key) {
+ break;
+ }
+ }
+ ssize_t xp = std::distance(seq_.begin(), x);
+ ssize_t size = index_.size();
ssize_t dest;
- typename SeqType::iterator x = (*idxent).second;
- typename SeqType::iterator d;
if(how == A2_POS_CUR) {
- // Because aria2.changePosition() RPC method must return the
- // absolute position after move, we have to calculate absolute
- // position here.
if(offset > 0) {
- d = x;
- for(; offset >= 0 && d != seq_.end(); --offset, ++d);
- dest = std::distance(seq_.begin(), d)-1;
+ dest = std::min(xp+offset, static_cast<ssize_t>(size-1));
} else {
- d = x;
- for(; offset < 0 && d != seq_.begin(); ++offset, --d);
- dest = std::distance(seq_.begin(), d);
+ dest = std::max(xp+offset, static_cast<ssize_t>(0));
}
} else {
- ssize_t size = index_.size();
if(how == A2_POS_END) {
- dest = std::min(size-1, size-1+offset);
+ dest = std::min(size-1+offset, size-1);
} else if(how == A2_POS_SET) {
- dest = std::min(size-1, offset);
+ dest = std::min(offset, size-1);
} else {
return -1;
}
dest = std::max(dest, static_cast<ssize_t>(0));
- d = seq_.begin();
- for(ssize_t i = 0; i < dest; ++i, ++d) {
- if(d == x) {
- ++d;
- }
- }
}
- seq_.splice(d, seq_, x);
+ typename SeqType::iterator d = seq_.begin();
+ std::advance(d, dest);
+ if(xp < dest) {
+ std::rotate(x, x+1, d+1);
+ } else {
+ std::rotate(d, x, x+1);
+ }
return dest;
}
@@ -219,30 +247,6 @@ public:
if(idxent == index_.end()) {
return ValuePtrType();
} else {
- return (*(*idxent).second).second;
- }
- }
-
- // Returns the iterator to the element associated by |key|. If it is
- // not found, end() is returned. Complexity: O(logN)
- typename SeqType::iterator find(KeyType key)
- {
- typename IndexType::iterator idxent = index_.find(key);
- if(idxent == index_.end()) {
- return seq_.end();
- } else {
- return (*idxent).second;
- }
- }
-
- // Returns the iterator to the element associated by |key|. If it is
- // not found, end() is returned. Complexity: O(logN)
- typename SeqType::const_iterator find(KeyType key) const
- {
- typename IndexType::const_iterator idxent = index_.find(key);
- if(idxent == index_.end()) {
- return seq_.end();
- } else {
return (*idxent).second;
}
}
diff --git a/src/RequestGroupMan.cc b/src/RequestGroupMan.cc
index feff9950..2eeccede 100644
--- a/src/RequestGroupMan.cc
+++ b/src/RequestGroupMan.cc
@@ -151,6 +151,15 @@ void RequestGroupMan::addReservedGroup
reservedGroups_.push_back(group->getGID(), group);
}
+namespace {
+struct RequestGroupKeyFunc {
+ a2_gid_t operator()(const SharedHandle<RequestGroup>& rg) const
+ {
+ return rg->getGID();
+ }
+};
+} // namespace
+
void RequestGroupMan::insertReservedGroup
(size_t pos, const std::vector<SharedHandle<RequestGroup> >& groups)
{
@@ -158,10 +167,8 @@ void RequestGroupMan::insertReservedGroup
pos = std::min(reservedGroups_.size(), pos);
RequestGroupList::SeqType::iterator dest = reservedGroups_.begin();
std::advance(dest, pos);
- for(std::vector<SharedHandle<RequestGroup> >::const_iterator i =
- groups.begin(), eoi = groups.end(); i != eoi; ++i, ++dest) {
- dest = reservedGroups_.insert(dest, (*i)->getGID(), *i);
- }
+ reservedGroups_.insert(dest, RequestGroupKeyFunc(),
+ groups.begin(), groups.end());
}
void RequestGroupMan::insertReservedGroup
@@ -482,42 +489,36 @@ void RequestGroupMan::fillRequestGroupFromReserver(DownloadEngine* e)
}
int count = 0;
int num = maxSimultaneousDownloads_-requestGroups_.size();
- // In the following loop, the download which is not ready to start
- // is kept in reservedGroups_. We use iterator to see if we
- // evaluated them all. So don't use empty() for this. Compare to
- // reservedGroups_.end() instead.
- RequestGroupList::SeqType::iterator resitr = reservedGroups_.begin();
- while(count < num && (uriListParser_ || resitr != reservedGroups_.end())) {
- if(uriListParser_ && resitr == reservedGroups_.end()) {
+ std::vector<SharedHandle<RequestGroup> > pending;
+
+ while(count < num && (uriListParser_ || !reservedGroups_.empty())) {
+ if(uriListParser_ && reservedGroups_.empty()) {
std::vector<SharedHandle<RequestGroup> > groups;
// May throw exception
bool ok = createRequestGroupFromUriListParser(groups, option_,
uriListParser_.get());
if(ok) {
appendReservedGroup(reservedGroups_, groups.begin(), groups.end());
- resitr = reservedGroups_.end();
- std::advance(resitr, -static_cast<ssize_t>(groups.size()));
} else {
uriListParser_.reset();
- if(resitr == reservedGroups_.end()) {
+ if(reservedGroups_.empty()) {
break;
}
}
}
- SharedHandle<RequestGroup> groupToAdd = (*resitr).second;
- std::vector<Command*> commands;
+ SharedHandle<RequestGroup> groupToAdd = (*reservedGroups_.begin()).second;
+ reservedGroups_.pop_front();
if((rpc_ && groupToAdd->isPauseRequested()) ||
!groupToAdd->isDependencyResolved()) {
- ++resitr;
+ pending.push_back(groupToAdd);
continue;
}
- ++resitr;
- reservedGroups_.erase(groupToAdd->getGID());
// Drop pieceStorage here because paused download holds its
// reference.
groupToAdd->dropPieceStorage();
configureRequestGroup(groupToAdd);
groupToAdd->setRequestGroupMan(this);
+ std::vector<Command*> commands;
try {
createInitialCommand(groupToAdd, commands, e);
++count;
@@ -543,6 +544,10 @@ void RequestGroupMan::fillRequestGroupFromReserver(DownloadEngine* e)
PREF_ON_DOWNLOAD_START);
notifyDownloadEvent(Notifier::ON_DOWNLOAD_START, groupToAdd);
}
+ if(!pending.empty()) {
+ reservedGroups_.insert(reservedGroups_.begin(), RequestGroupKeyFunc(),
+ pending.begin(), pending.end());
+ }
if(count > 0) {
e->setNoWait(true);
e->setRefreshInterval(0);
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
generated by cgit (git 2.46.0) at 2026-10-12 04:47:15 +0000