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

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

2 files changed, 91 insertions, 82 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);