Store in memory cookies in a hash set instead of a list.

The old code was performing expensive string searches against cookies stored in
a list. See the bug for Instruments/DTrace results of the performance benefits.

BUG=401629

Review URL: https://codereview.chromium.org/454623003

Cr-Commit-Position: refs/heads/master@{#290383}
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@290383 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 282 insertions, 154 deletions

diff --git a/chrome/browser/browsing_data/browsing_data_cookie_helper.cc b/chrome/browser/browsing_data/browsing_data_cookie_helper.cc
index 605c85c..acef30b 100644
--- a/chrome/browser/browsing_data/browsing_data_cookie_helper.cc
+++ b/chrome/browser/browsing_data/browsing_data_cookie_helper.cc
@@ -23,7 +23,7 @@
 using content::BrowserThread;
 
 namespace {
-const char kGlobalCookieListURL[] = "chrome://cookielist";
+const char kGlobalCookieSetURL[] = "chrome://cookieset";
 }
 
 BrowsingDataCookieHelper::BrowsingDataCookieHelper(
@@ -113,11 +113,11 @@ CannedBrowsingDataCookieHelper* CannedBrowsingDataCookieHelper::Clone() {
   CannedBrowsingDataCookieHelper* clone =
       new CannedBrowsingDataCookieHelper(request_context_getter());
 
-  for (OriginCookieListMap::iterator it = origin_cookie_list_map_.begin();
-       it != origin_cookie_list_map_.end();
+  for (OriginCookieSetMap::iterator it = origin_cookie_set_map_.begin();
+       it != origin_cookie_set_map_.end();
        ++it) {
-    net::CookieList* cookies = clone->GetCookiesFor(it->first);
-    cookies->insert(cookies->begin(), it->second->begin(), it->second->end());
+    canonical_cookie::CookieHashSet* cookies = clone->GetCookiesFor(it->first);
+    cookies->insert(it->second->begin(), it->second->end());
   }
   return clone;
 }
@@ -145,15 +145,14 @@ void CannedBrowsingDataCookieHelper::AddChangedCookie(
 }
 
 void CannedBrowsingDataCookieHelper::Reset() {
-  STLDeleteContainerPairSecondPointers(origin_cookie_list_map_.begin(),
-                                       origin_cookie_list_map_.end());
-  origin_cookie_list_map_.clear();
+  STLDeleteContainerPairSecondPointers(origin_cookie_set_map_.begin(),
+                                       origin_cookie_set_map_.end());
+  origin_cookie_set_map_.clear();
 }
 
 bool CannedBrowsingDataCookieHelper::empty() const {
-  for (OriginCookieListMap::const_iterator it =
-           origin_cookie_list_map_.begin();
-       it != origin_cookie_list_map_.end();
+  for (OriginCookieSetMap::const_iterator it = origin_cookie_set_map_.begin();
+       it != origin_cookie_set_map_.end();
        ++it) {
     if (!it->second->empty())
       return false;
@@ -164,8 +163,8 @@ bool CannedBrowsingDataCookieHelper::empty() const {
 
 size_t CannedBrowsingDataCookieHelper::GetCookieCount() const {
   size_t count = 0;
-  for (OriginCookieListMap::const_iterator it = origin_cookie_list_map_.begin();
-       it != origin_cookie_list_map_.end();
+  for (OriginCookieSetMap::const_iterator it = origin_cookie_set_map_.begin();
+       it != origin_cookie_set_map_.end();
        ++it) {
     count += it->second->size();
   }
@@ -177,8 +176,8 @@ void CannedBrowsingDataCookieHelper::StartFetching(
     const net::CookieMonster::GetCookieListCallback& callback) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   net::CookieList cookie_list;
-  for (OriginCookieListMap::iterator it = origin_cookie_list_map_.begin();
-       it != origin_cookie_list_map_.end();
+  for (OriginCookieSetMap::iterator it = origin_cookie_set_map_.begin();
+       it != origin_cookie_set_map_.end();
        ++it) {
     cookie_list.insert(cookie_list.begin(),
                        it->second->begin(),
@@ -189,8 +188,8 @@ void CannedBrowsingDataCookieHelper::StartFetching(
 
 void CannedBrowsingDataCookieHelper::DeleteCookie(
     const net::CanonicalCookie& cookie) {
-  for (OriginCookieListMap::iterator it = origin_cookie_list_map_.begin();
-       it != origin_cookie_list_map_.end();
+  for (OriginCookieSetMap::iterator it = origin_cookie_set_map_.begin();
+       it != origin_cookie_set_map_.end();
        ++it) {
     DeleteMatchingCookie(cookie, it->second);
   }
@@ -199,28 +198,20 @@ void CannedBrowsingDataCookieHelper::DeleteCookie(
 
 bool CannedBrowsingDataCookieHelper::DeleteMatchingCookie(
     const net::CanonicalCookie& add_cookie,
-    net::CookieList* cookie_list) {
-  typedef net::CookieList::iterator cookie_iterator;
-  for (cookie_iterator cookie = cookie_list->begin();
-      cookie != cookie_list->end(); ++cookie) {
-    if (cookie->Name() == add_cookie.Name() &&
-        cookie->Domain() == add_cookie.Domain() &&
-        cookie->Path() == add_cookie.Path()) {
-      cookie_list->erase(cookie);
-      return true;
-    }
-  }
-  return false;
+    canonical_cookie::CookieHashSet* cookie_set) {
+  return cookie_set->erase(add_cookie) > 0;
 }
 
-net::CookieList* CannedBrowsingDataCookieHelper::GetCookiesFor(
+canonical_cookie::CookieHashSet* CannedBrowsingDataCookieHelper::GetCookiesFor(
     const GURL& first_party_origin) {
-  OriginCookieListMap::iterator it =
-      origin_cookie_list_map_.find(first_party_origin);
-  if (it == origin_cookie_list_map_.end()) {
-    net::CookieList* cookies = new net::CookieList();
-    origin_cookie_list_map_.insert(
-        std::pair<GURL, net::CookieList*>(first_party_origin, cookies));
+  OriginCookieSetMap::iterator it =
+      origin_cookie_set_map_.find(first_party_origin);
+  if (it == origin_cookie_set_map_.end()) {
+    canonical_cookie::CookieHashSet* cookies =
+        new canonical_cookie::CookieHashSet;
+    origin_cookie_set_map_.insert(
+        std::pair<GURL, canonical_cookie::CookieHashSet*>(first_party_origin,
+                                                          cookies));
     return cookies;
   }
   return it->second;
@@ -229,23 +220,24 @@ net::CookieList* CannedBrowsingDataCookieHelper::GetCookiesFor(
 void CannedBrowsingDataCookieHelper::AddCookie(
     const GURL& frame_url,
     const net::CanonicalCookie& cookie) {
-  // Storing cookies in separate cookie lists per frame origin makes the
+  // Storing cookies in separate cookie sets per frame origin makes the
   // GetCookieCount method count a cookie multiple times if it is stored in
-  // multiple lists.
+  // multiple sets.
   // E.g. let "example.com" be redirected to "www.example.com". A cookie set
   // with the cookie string "A=B; Domain=.example.com" would be sent to both
-  // hosts. This means it would be stored in the separate cookie lists for both
+  // hosts. This means it would be stored in the separate cookie sets for both
   // hosts ("example.com", "www.example.com"). The method GetCookieCount would
   // count this cookie twice. To prevent this, we us a single global cookie
-  // list as a work-around to store all added cookies. Per frame URL cookie
-  // lists are currently not used. In the future they will be used for
+  // set as a work-around to store all added cookies. Per frame URL cookie
+  // sets are currently not used. In the future they will be used for
   // collecting cookies per origin in redirect chains.
   // TODO(markusheintz): A) Change the GetCookiesCount method to prevent
   // counting cookies multiple times if they are stored in multiple cookie
-  // lists.  B) Replace the GetCookieFor method call below with:
+  // sets.  B) Replace the GetCookieFor method call below with:
   // "GetCookiesFor(frame_url.GetOrigin());"
-  net::CookieList* cookie_list =
-      GetCookiesFor(GURL(kGlobalCookieListURL));
-  DeleteMatchingCookie(cookie, cookie_list);
-  cookie_list->push_back(cookie);
+  CR_DEFINE_STATIC_LOCAL(const GURL, origin_cookie_url, (kGlobalCookieSetURL));
+  canonical_cookie::CookieHashSet* cookie_set =
+      GetCookiesFor(origin_cookie_url);
+  DeleteMatchingCookie(cookie, cookie_set);
+  cookie_set->insert(cookie);
 }
diff --git a/chrome/browser/browsing_data/browsing_data_cookie_helper.h b/chrome/browser/browsing_data/browsing_data_cookie_helper.h
index cefd2b5..7c100f3 100644
--- a/chrome/browser/browsing_data/browsing_data_cookie_helper.h
+++ b/chrome/browser/browsing_data/browsing_data_cookie_helper.h
@@ -11,6 +11,7 @@
 #include "base/basictypes.h"
 #include "base/callback.h"
 #include "base/memory/ref_counted.h"
+#include "chrome/browser/browsing_data/canonical_cookie_hash.h"
 #include "net/cookies/cookie_monster.h"
 
 class GURL;
@@ -90,7 +91,7 @@ class BrowsingDataCookieHelper
 // cookies.
 class CannedBrowsingDataCookieHelper : public BrowsingDataCookieHelper {
  public:
-  typedef std::map<GURL, net::CookieList*> OriginCookieListMap;
+  typedef std::map<GURL, canonical_cookie::CookieHashSet*> OriginCookieSetMap;
 
   explicit CannedBrowsingDataCookieHelper(
       net::URLRequestContextGetter* request_context);
@@ -138,28 +139,28 @@ class CannedBrowsingDataCookieHelper : public BrowsingDataCookieHelper {
   size_t GetCookieCount() const;
 
   // Returns the map that contains the cookie lists for all frame urls.
-  const OriginCookieListMap& origin_cookie_list_map() {
-    return origin_cookie_list_map_;
+  const OriginCookieSetMap& origin_cookie_set_map() {
+    return origin_cookie_set_map_;
   }
 
  private:
-  // Check if the cookie list contains a cookie with the same name,
+  // Check if the cookie set contains a cookie with the same name,
   // domain, and path as the newly created cookie. Delete the old cookie
   // if does.
   bool DeleteMatchingCookie(const net::CanonicalCookie& add_cookie,
-                            net::CookieList* cookie_list);
+                            canonical_cookie::CookieHashSet* cookie_set);
 
   virtual ~CannedBrowsingDataCookieHelper();
 
-  // Returns the |CookieList| for the given |origin|.
-  net::CookieList* GetCookiesFor(const GURL& origin);
+  // Returns the |CookieSet| for the given |origin|.
+  canonical_cookie::CookieHashSet* GetCookiesFor(const GURL& origin);
 
-  // Adds the |cookie| to the cookie list for the given |frame_url|.
+  // Adds the |cookie| to the cookie set for the given |frame_url|.
   void AddCookie(const GURL& frame_url,
                  const net::CanonicalCookie& cookie);
 
-  // Map that contains the cookie lists for all frame origins.
-  OriginCookieListMap origin_cookie_list_map_;
+  // Map that contains the cookie sets for all frame origins.
+  OriginCookieSetMap origin_cookie_set_map_;
 
   DISALLOW_COPY_AND_ASSIGN(CannedBrowsingDataCookieHelper);
 };
diff --git a/chrome/browser/browsing_data/browsing_data_cookie_helper_unittest.cc b/chrome/browser/browsing_data/browsing_data_cookie_helper_unittest.cc
index faa861c..64a796d 100644
--- a/chrome/browser/browsing_data/browsing_data_cookie_helper_unittest.cc
+++ b/chrome/browser/browsing_data/browsing_data_cookie_helper_unittest.cc
@@ -15,12 +15,102 @@
 
 namespace {
 
+// Test expectations for a given cookie.
+class CookieExpectation {
+ public:
+  CookieExpectation() : matched_(false) {}
+
+  bool MatchesCookie(const net::CanonicalCookie& cookie) const {
+    if (!source_.empty() && source_ != cookie.Source())
+      return false;
+    if (!domain_.empty() && domain_ != cookie.Domain())
+      return false;
+    if (!path_.empty() && path_ != cookie.Path())
+      return false;
+    if (!name_.empty() && name_ != cookie.Name())
+      return false;
+    if (!value_.empty() && value_ != cookie.Value())
+      return false;
+    return true;
+  }
+
+  std::string source_;
+  std::string domain_;
+  std::string path_;
+  std::string name_;
+  std::string value_;
+  bool matched_;
+};
+
+// Matches a CookieExpectation against a Cookie.
+class CookieMatcher {
+ public:
+  explicit CookieMatcher(const net::CanonicalCookie& cookie)
+      : cookie_(cookie) {}
+  bool operator()(const CookieExpectation& expectation) {
+    return expectation.MatchesCookie(cookie_);
+  }
+  net::CanonicalCookie cookie_;
+};
+
+// Unary predicate to determine whether an expectation has been matched.
+bool ExpectationIsMatched(const CookieExpectation& expectation) {
+  return expectation.matched_;
+}
+
 class BrowsingDataCookieHelperTest : public testing::Test {
  public:
   BrowsingDataCookieHelperTest()
       : testing_profile_(new TestingProfile()) {
   }
 
+  virtual void SetUp() OVERRIDE { cookie_expectations_.clear(); }
+
+  // Adds an expectation for a cookie that satisfies the given parameters.
+  void AddCookieExpectation(const char* source,
+                            const char* domain,
+                            const char* path,
+                            const char* name,
+                            const char* value) {
+    CookieExpectation matcher;
+    if (source)
+      matcher.source_ = source;
+    if (domain)
+      matcher.domain_ = domain;
+    if (path)
+      matcher.path_ = path;
+    if (name)
+      matcher.name_ = name;
+    if (value)
+      matcher.value_ = value;
+    cookie_expectations_.push_back(matcher);
+  }
+
+  // Checks the existing expectations, and then clears all existing
+  // expectations.
+  void CheckCookieExpectations() {
+    ASSERT_EQ(cookie_expectations_.size(), cookie_list_.size());
+
+    // For each cookie, look for a matching expectation.
+    for (net::CookieList::iterator it = cookie_list_.begin();
+         it != cookie_list_.end();
+         ++it) {
+      CookieMatcher matcher(*it);
+      std::vector<CookieExpectation>::iterator match = std::find_if(
+          cookie_expectations_.begin(), cookie_expectations_.end(), matcher);
+      if (match != cookie_expectations_.end())
+        match->matched_ = true;
+    }
+
+    // Check that each expectation has been matched.
+    unsigned long match_count = std::count_if(cookie_expectations_.begin(),
+                                              cookie_expectations_.end(),
+                                              ExpectationIsMatched);
+    EXPECT_EQ(cookie_expectations_.size(), match_count);
+
+    cookie_expectations_.clear();
+  }
+
   void CreateCookiesForTest() {
     scoped_refptr<net::CookieMonster> cookie_monster =
         testing_profile_->GetCookieMonster();
@@ -44,135 +134,76 @@ class BrowsingDataCookieHelperTest : public testing::Test {
   }
 
   void FetchCallback(const net::CookieList& cookies) {
-    ASSERT_EQ(2UL, cookies.size());
     cookie_list_ = cookies;
-    net::CookieList::const_iterator it = cookies.begin();
 
-    // Correct because fetching cookies will get a sorted cookie list.
-    ASSERT_TRUE(it != cookies.end());
-    EXPECT_EQ("www.google.com", it->Domain());
-    EXPECT_EQ("A", it->Name());
-
-    ASSERT_TRUE(++it != cookies.end());
-    EXPECT_EQ("www.gmail.google.com", it->Domain());
-    EXPECT_EQ("B", it->Name());
-
-    ASSERT_TRUE(++it == cookies.end());
+    AddCookieExpectation(NULL, "www.google.com", NULL, "A", NULL);
+    AddCookieExpectation(NULL, "www.gmail.google.com", NULL, "B", NULL);
+    CheckCookieExpectations();
   }
 
   void DomainCookieCallback(const net::CookieList& cookies) {
-    ASSERT_EQ(2UL, cookies.size());
     cookie_list_ = cookies;
-    net::CookieList::const_iterator it = cookies.begin();
-
-    // Correct because fetching cookies will get a sorted cookie list.
-    ASSERT_TRUE(it != cookies.end());
-    EXPECT_EQ("www.google.com", it->Domain());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ("1", it->Value());
-
-    ASSERT_TRUE(++it != cookies.end());
-    EXPECT_EQ(".www.google.com", it->Domain());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ("2", it->Value());
 
-    ASSERT_TRUE(++it == cookies.end());
+    AddCookieExpectation(NULL, "www.google.com", NULL, "A", "1");
+    AddCookieExpectation(NULL, ".www.google.com", NULL, "A", "2");
+    CheckCookieExpectations();
   }
 
   void DeleteCallback(const net::CookieList& cookies) {
-    ASSERT_EQ(1UL, cookies.size());
-    net::CookieList::const_iterator it = cookies.begin();
-
-    ASSERT_TRUE(it != cookies.end());
-    EXPECT_EQ("www.gmail.google.com", it->Domain());
-    EXPECT_EQ("B", it->Name());
-
-    ASSERT_TRUE(++it == cookies.end());
+    cookie_list_ = cookies;
+    AddCookieExpectation(NULL, "www.gmail.google.com", NULL, "B", NULL);
+    CheckCookieExpectations();
   }
 
   void CannedUniqueCallback(const net::CookieList& cookies) {
-    EXPECT_EQ(1UL, cookies.size());
     cookie_list_ = cookies;
-    net::CookieList::const_iterator it = cookies.begin();
-
-    ASSERT_TRUE(it != cookies.end());
-    EXPECT_EQ("http://www.google.com/", it->Source());
-    EXPECT_EQ("www.google.com", it->Domain());
-    EXPECT_EQ("/", it->Path());
-    EXPECT_EQ("A", it->Name());
-
-    ASSERT_TRUE(++it == cookies.end());
+    AddCookieExpectation(
+        "http://www.google.com/", "www.google.com", "/", "A", NULL);
+    CheckCookieExpectations();
   }
 
   void CannedReplaceCookieCallback(const net::CookieList& cookies) {
-    EXPECT_EQ(5UL, cookies.size());
     cookie_list_ = cookies;
-    net::CookieList::const_iterator it = cookies.begin();
-
-    ASSERT_TRUE(it != cookies.end());
-    EXPECT_EQ("http://www.google.com/", it->Source());
-    EXPECT_EQ("www.google.com", it->Domain());
-    EXPECT_EQ("/", it->Path());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ("2", it->Value());
-
-    ASSERT_TRUE(++it != cookies.end());
-    EXPECT_EQ("http://www.google.com/", it->Source());
-    EXPECT_EQ("www.google.com", it->Domain());
-    EXPECT_EQ("/example/0", it->Path());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ("4", it->Value());
-
-    ASSERT_TRUE(++it != cookies.end());
-    EXPECT_EQ("http://www.google.com/", it->Source());
-    EXPECT_EQ(".google.com", it->Domain());
-    EXPECT_EQ("/", it->Path());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ("6", it->Value());
-
-    ASSERT_TRUE(++it != cookies.end());
-    EXPECT_EQ("http://www.google.com/", it->Source());
-    EXPECT_EQ(".google.com", it->Domain());
-    EXPECT_EQ("/example/1", it->Path());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ("8", it->Value());
-
-    ASSERT_TRUE(++it != cookies.end());
-    EXPECT_EQ("http://www.google.com/", it->Source());
-    EXPECT_EQ(".www.google.com", it->Domain());
-    EXPECT_EQ("/", it->Path());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ("10", it->Value());
-
-    ASSERT_TRUE(++it == cookies.end());
+    AddCookieExpectation(
+        "http://www.google.com/", "www.google.com", "/", "A", "2");
+    AddCookieExpectation(
+        "http://www.google.com/", "www.google.com", "/example/0", "A", "4");
+    AddCookieExpectation(
+        "http://www.google.com/", ".google.com", "/", "A", "6");
+    AddCookieExpectation(
+        "http://www.google.com/", ".google.com", "/example/1", "A", "8");
+    AddCookieExpectation(
+        "http://www.google.com/", ".www.google.com", "/", "A", "10");
+    CheckCookieExpectations();
   }
 
   void CannedDomainCookieCallback(const net::CookieList& cookies) {
-    ASSERT_EQ(2UL, cookies.size());
     cookie_list_ = cookies;
-    net::CookieList::const_iterator it = cookies.begin();
-
-    ASSERT_TRUE(it != cookies.end());
-    EXPECT_EQ("http://www.google.com/", it->Source());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ("www.google.com", it->Domain());
-
-    ASSERT_TRUE(++it != cookies.end());
-    EXPECT_EQ("http://www.google.com/", it->Source());
-    EXPECT_EQ("A", it->Name());
-    EXPECT_EQ(".www.google.com", it->Domain());
-
-    ASSERT_TRUE(++it == cookies.end());
+    AddCookieExpectation(
+        "http://www.google.com/", "www.google.com", NULL, "A", NULL);
+    AddCookieExpectation(
+        "http://www.google.com/", ".www.google.com", NULL, "A", NULL);
+    CheckCookieExpectations();
   }
 
   void CannedDifferentFramesCallback(const net::CookieList& cookie_list) {
     ASSERT_EQ(3U, cookie_list.size());
   }
 
+  void DeleteCookie(BrowsingDataCookieHelper* helper, const GURL origin) {
+    for (net::CookieList::iterator it = cookie_list_.begin();
+         it != cookie_list_.end();
+         ++it) {
+      if (it->Source() == net::CanonicalCookie::GetCookieSourceFromURL(origin))
+        helper->DeleteCookie(*it);
+    }
+  }
+
  protected:
   content::TestBrowserThreadBundle thread_bundle_;
   scoped_ptr<TestingProfile> testing_profile_;
 
+  std::vector<CookieExpectation> cookie_expectations_;
   net::CookieList cookie_list_;
 };
 
@@ -237,7 +268,7 @@ TEST_F(BrowsingDataCookieHelperTest, CannedDeleteCookie) {
 
   EXPECT_EQ(2u, helper->GetCookieCount());
 
-  helper->DeleteCookie(cookie_list_[0]);
+  DeleteCookie(helper.get(), origin1);
 
   EXPECT_EQ(1u, helper->GetCookieCount());
   helper->StartFetching(
diff --git a/chrome/browser/browsing_data/canonical_cookie_hash.cc b/chrome/browser/browsing_data/canonical_cookie_hash.cc
new file mode 100644
index 0000000..218555e
--- /dev/null
+++ b/chrome/browser/browsing_data/canonical_cookie_hash.cc
@@ -0,0 +1,18 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "chrome/browser/browsing_data/canonical_cookie_hash.h"
+
+#include "base/hash.h"
+
+namespace canonical_cookie {
+
+size_t FastHash(const net::CanonicalCookie& cookie) {
+  return base::SuperFastHash(cookie.Name().c_str(), cookie.Name().size()) +
+         3 * base::SuperFastHash(cookie.Domain().c_str(),
+                                 cookie.Domain().size()) +
+         7 * base::SuperFastHash(cookie.Path().c_str(), cookie.Path().size());
+}
+
+};  // namespace canonical_cookie
diff --git a/chrome/browser/browsing_data/canonical_cookie_hash.h b/chrome/browser/browsing_data/canonical_cookie_hash.h
new file mode 100644
index 0000000..a6905df
--- /dev/null
+++ b/chrome/browser/browsing_data/canonical_cookie_hash.h
@@ -0,0 +1,86 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Provides utility structures for inserting a CanonicalCookie into a hash set.
+// Two cookies are considered equal if their names, domains, and paths are
+// equivalent.
+
+#ifndef CHROME_BROWSER_BROWSING_DATA_CANONICAL_COOKIE_HASH_H_
+#define CHROME_BROWSER_BROWSING_DATA_CANONICAL_COOKIE_HASH_H_
+
+#if defined(COMPILER_MSVC)
+#include <functional>
+#endif  // COMPILER_MSVC
+
+#include "base/containers/hash_tables.h"
+#include "net/cookies/canonical_cookie.h"
+
+namespace canonical_cookie {
+
+// Returns a fast hash of a cookie, based on its name, domain, and path.
+size_t FastHash(const net::CanonicalCookie& cookie);
+
+#if defined(COMPILER_MSVC)
+struct CanonicalCookieTraits {
+  static const size_t bucket_size = 4;
+
+  // Returns a hash of |cookie|.
+  size_t operator()(const net::CanonicalCookie& cookie) const {
+    return FastHash(cookie);
+  }
+
+  // The 'less' operator on cookies. We need to create a total ordering. We
+  // order lexigraphically, first by name, then path, then domain. Name is most
+  // likely to be distinct, so it is compared first, and domain is least likely
+  // to be distinct, so it is compared last.
+  bool operator()(const net::CanonicalCookie& cookie1,
+                  const net::CanonicalCookie& cookie2) const {
+    std::less<std::string> less_than;
+    if (less_than(cookie1.Name(), cookie2.Name()))
+      return true;
+    if (less_than(cookie2.Name(), cookie1.Name()))
+      return false;
+    if (less_than(cookie1.Path(), cookie2.Path()))
+      return true;
+    if (less_than(cookie2.Path(), cookie1.Path()))
+      return false;
+    if (less_than(cookie1.Domain(), cookie2.Domain()))
+      return true;
+    if (less_than(cookie2.Domain(), cookie1.Domain()))
+      return false;
+
+    // The cookies are equivalent.
+    return false;
+  }
+};
+
+typedef base::hash_set<net::CanonicalCookie, CanonicalCookieTraits>
+    CookieHashSet;
+
+#else  // COMPILER_MSVC
+
+struct CanonicalCookieHasher {
+  std::size_t operator()(const net::CanonicalCookie& cookie) const {
+    return FastHash(cookie);
+  }
+};
+
+struct CanonicalCookieComparer {
+  bool operator()(const net::CanonicalCookie& cookie1,
+                  const net::CanonicalCookie& cookie2) const {
+    return cookie1.Name() == cookie2.Name() &&
+           cookie1.Domain() == cookie2.Domain() &&
+           cookie1.Path() == cookie2.Path();
+  }
+};
+
+typedef base::hash_set<net::CanonicalCookie,
+                       CanonicalCookieHasher,
+                       CanonicalCookieComparer> CookieHashSet;
+
+#endif  // COMPILER_MSVC
+
+};  // namespace canonical_cookie
+
+#endif  // CHROME_BROWSER_BROWSING_DATA_CANONICAL_COOKIE_HASH_H_