Rewrite CookieStorage

1 files changed, 122 insertions, 97 deletions

diff --git a/src/CookieStorage.h b/src/CookieStorage.h
index 530e0d62..de3eaebc 100644
--- a/src/CookieStorage.h
+++ b/src/CookieStorage.h
@@ -2,7 +2,7 @@
 /*
  * aria2 - The high speed download utility
  *
- * Copyright (C) 2006 Tatsuhiro Tsujikawa
+ * Copyright (C) 2013 Tatsuhiro Tsujikawa
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -42,6 +42,7 @@
 #include <vector>
 #include <set>
 #include <algorithm>
+#include <unordered_map>
 
 #include "a2time.h"
 #include "Cookie.h"
@@ -51,89 +52,97 @@ namespace aria2 {
 
 class BufferedFile;
 
-class CookieStorage {
+// This object represents one domain label.
+class DomainNode {
 public:
+  DomainNode(std::string label, DomainNode* parent);
+  // Stores the matching cookies in |out|. The |now| is used to update
+  // the last access time of this node.
+  void findCookie
+  (std::vector<const Cookie*>& out,
+   const std::string& requestHost,
+   const std::string& requestPath,
+   time_t now, bool secure);
+  // Returns the number of cookies this node has.
+  size_t countCookie() const;
+  // Add |cookie| using update time |now|. Returns true if the
+  // function succeeds.
+  bool addCookie(std::unique_ptr<Cookie> cookie, time_t now);
+  // Sets the last access time of this node.
+  void setLastAccessTime(time_t lastAccessTime);
+  // Returns the last access time of this node.
+  time_t getLastAccessTime() const;
+  // Sets the time |t| as a time used as key in LRU tracker.
+  void setLruAccessTime(time_t t);
+  time_t getLruAccessTime() const;
+
+  bool writeCookie(BufferedFile& fp) const;
+  // Returns true if this node contains the |cookie|.
+  bool contains(const Cookie& cookie) const;
+  // Returns true if this node contains no cookie.
+  bool empty() const;
+  // Returns true if this node has any next nodes.
+  bool hasNext() const;
+  // Returns the parent node. If this is the root node, returns
+  // nullptr.
+  DomainNode* getParent() const;
+  // Removes the child node |node|. Nothing happens if |node| is not a
+  // child of this node.
+  void removeNode(DomainNode* node);
+  // Returns the child node having label |label. Returns nullptr if
+  // there is no such node.
+  DomainNode* findNext(const std::string& label) const;
+  // Add the |node| as a child using label |label and returns the raw
+  // pointer of |node|.
+  DomainNode* addNext(std::string label, std::unique_ptr<DomainNode> node);
+  // Returns the |label|.
+  const std::string& getLabel() const;
+  // Deletes all cookies this node has.
+  void clearCookie();
+  // Returns value set by setInLru(). This is typically used to know
+  // this node is tracked by LRU tracker or not.
+  bool getInLru() const;
+  void setInLru(bool f);
 
-  static const size_t MAX_COOKIE_PER_DOMAIN = 50;
-
-  class DomainEntry {
-  private:
-    // This is reversed domain level string.
-    // e.g. net.sourceforge.aria2
-    // e.g. 192.168.0.1
-    std::string key_;
-
-    time_t lastAccessTime_;
-
-    std::deque<Cookie> cookies_;
-  public:
-    DomainEntry(const std::string& domain);
-    DomainEntry(const DomainEntry& c);
-    ~DomainEntry();
-
-    void swap(DomainEntry& c);
-
-    DomainEntry& operator=(const DomainEntry& c);
-
-    const std::string& getKey() const
-    {
-      return key_;
-    }
-
-    void findCookie
-    (std::vector<Cookie>& out,
-     const std::string& requestHost,
-     const std::string& requestPath,
-     time_t now, bool secure);
-
-    size_t countCookie() const;
-
-    bool addCookie(const Cookie& cookie, time_t now);
-
-    void setLastAccessTime(time_t lastAccessTime)
-    {
-      lastAccessTime_ = lastAccessTime;
-    }
-
-    time_t getLastAccessTime() const
-    {
-      return lastAccessTime_;
-    }
-
-    bool writeCookie(BufferedFile& fp) const;
-
-    bool contains(const Cookie& cookie) const;
-
-    template<typename OutputIterator>
-    OutputIterator dumpCookie(OutputIterator out) const
-    {
-      return std::copy(cookies_.begin(), cookies_.end(), out);
+  template<typename OutputIterator>
+  OutputIterator dumpCookie(OutputIterator out) const
+  {
+    if(cookies_) {
+      for(auto& c : *cookies_) {
+        out++ = c.get();
+      }
     }
+    return out;
+  }
+private:
+  std::string label_;
+  DomainNode* parent_;
+  time_t lastAccessTime_;
+  time_t lruAccessTime_;
+  bool inLru_;
+  std::unique_ptr<std::deque<std::unique_ptr<Cookie>>> cookies_;
+  // domain label string to DomainNode
+  // e.g. net, sourceforge
+  // For numerical addresses, this is address itself.
+  // e.g. 192.168.0.1
+  std::unordered_map<std::string, std::unique_ptr<DomainNode>> next_;
+};
 
-    bool operator==(const DomainEntry& de) const;
-    bool operator<(const DomainEntry& de) const;
-  };
+class CookieStorage {
+public:
+  static const size_t MAX_COOKIE_PER_DOMAIN = 50;
 private:
-  typedef std::set<std::shared_ptr<DomainEntry>,
-                   DerefLess<std::shared_ptr<DomainEntry> > > DomainEntrySet;
-  DomainEntrySet domains_;
+  // typedef std::set<std::shared_ptr<DomainEntry>,
+  //                  DerefLess<std::shared_ptr<DomainEntry> > > DomainEntrySet;
+  // DomainEntrySet domains_;
 
-  template<typename InputIterator>
-  void storeCookies(InputIterator first, InputIterator last, time_t now)
-  {
-    for(; first != last; ++first) {
-      store(*first, now);
-    }
-  }
 public:
   CookieStorage();
 
-  ~CookieStorage();
-
   // Returns true if cookie is stored or updated existing cookie.
   // Returns false if cookie is expired. now is used as last access
   // time.
-  bool store(const Cookie& cookie, time_t now);
+  bool store(std::unique_ptr<Cookie> cookie, time_t now);
 
   // Returns true if cookie is stored or updated existing cookie.
   // Otherwise, returns false. now is used as creation time and last
@@ -146,9 +155,10 @@ public:
 
   // Finds cookies matched with given criteria and returns them.
   // Matched cookies' lastAccess_ property is updated.
-  std::vector<Cookie> criteriaFind(const std::string& requestHost,
-                                   const std::string& requestPath,
-                                   time_t now, bool secure);
+  std::vector<const Cookie*>
+  criteriaFind(const std::string& requestHost,
+               const std::string& requestPath,
+               time_t now, bool secure);
 
   // Loads Cookies from file denoted by filename.  If compiled with
   // libsqlite3, this method automatically detects the specified file
@@ -170,36 +180,51 @@ public:
   // satisfies.
   bool contains(const Cookie& cookie) const;
 
-  // Searches Cookie using given domain, requestHost, requestPath,
-  // current time and secure flag. The found Cookies are stored in
-  // out.
-  void searchCookieByDomainSuffix
-  (std::vector<Cookie>& out,
-   const std::string& domain,
-   const std::string& requestHost,
-   const std::string& requestPath,
-   time_t now, bool secure);
-
   template<typename OutputIterator>
   OutputIterator dumpCookie(OutputIterator out) const
   {
-    for(DomainEntrySet::iterator i = domains_.begin(), eoi = domains_.end();
-        i != eoi; ++i) {
-      out = (*i)->dumpCookie(out);
+    for(auto& i : lruTracker_) {
+      out = i.second->dumpCookie(out);
     }
     return out;
   }
-};
 
-void swap(CookieStorage::DomainEntry& a, CookieStorage::DomainEntry& b);
+  // Force eviction of delnum nodes. Exposed for unittest
+  void evictNode(size_t delnum);
+  // Returns size of LRU tracker. Exposed for unittest
+  size_t getLruTrackerSize() const;
+  // Returns root node. Exposed for unittest
+  const DomainNode* getRootNode() const;
+private:
+  template<typename InputIterator>
+  void storeCookies(InputIterator first, InputIterator last, time_t now)
+  {
+    for(; first != last; ++first) {
+      store(*first, now);
+    }
+  }
+
+  void updateLru(DomainNode* node, time_t now);
+
+  // rootNode_ is a root node of tree structure of reversed domain
+  // labels.  rootNode_ always contans no cookie. It has the child
+  // nodes of the top level domain label (e.g., net, com and org). And
+  // those top level domain nodes have 2nd doman label (e.g.,
+  // sourcforge, github), and so on. The numeric host name are always
+  // stored as a child node of rootNode_. So the domain name of a
+  // paricular node is constructed as follows. First traverse the
+  // target node from root node. The concatenation of the visited
+  // node's label in the reverse order, delimited by ".", is the
+  std::unique_ptr<DomainNode> rootNode_;
+  // This object tracks the node which has cookies or it once had. The
+  // order is sorted by the least recent updated node first. This
+  // object does not track the node which has not contan cookie. For
+  // example, adding cookies in aria2.sourceforge.net, and no node
+  // labeled "sourceforge" is present, only node labelded "aria2" is
+  // tracked and node labeled "sourceforge" and "net" are not.
+  std::set<std::pair<time_t, DomainNode*>> lruTracker_;
+};
 
 } // namespace aria2
 
-namespace std {
-template<>
-void swap<aria2::CookieStorage::DomainEntry>
-(aria2::CookieStorage::DomainEntry& a,
- aria2::CookieStorage::DomainEntry& b);
-} // namespace std
-
 #endif // D_COOKIE_STORAGE_H