Implementing URL prefix match for history thumbnail cache.

chrome/browser/history/top_sites_cache.h

 // Copyright (c) 2012 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.
 
 #ifndef CHROME_BROWSER_HISTORY_TOP_SITES_CACHE_H_
 #define CHROME_BROWSER_HISTORY_TOP_SITES_CACHE_H_
 
 #include <map>
+#include <string>
 #include <utility>
 
 #include "base/memory/ref_counted.h"
 #include "chrome/browser/history/history_types.h"
 
 namespace history {
 
+// The entries in CanonicalURLs, see CanonicalURLs for details. The second
+// argument gives the index of the URL into MostVisitedURLs redirects.
+typedef std::pair<MostVisitedURL*, size_t> CanonicalURLEntry;
+
+// Defines the "path-prefix" compare of two URLs
+// Comparator used for CanonicalURLs.
+class CanonicalURLComparator {
+ public:
+  bool operator()(const CanonicalURLEntry& e1,
+                  const CanonicalURLEntry& e2) const;
+  static bool CompareString(const std::string& s1,
+                            const std::string& s2);
+};
+
 // TopSitesCache caches the top sites and thumbnails for TopSites.
 class TopSitesCache {
  public:
   TopSitesCache();
   ~TopSitesCache();
 
   // The top sites.
   void SetTopSites(const MostVisitedURLList& top_sites);
   const MostVisitedURLList& top_sites() const { return top_sites_; }
 
   // The thumbnails.
   void SetThumbnails(const URLToImagesMap& images);
   const URLToImagesMap& images() const { return images_; }
 
   // Returns the thumbnail as an Image for the specified url. This adds an entry
   // for |url| if one has not yet been added.
   Images* GetImage(const GURL& url);
 
   // Fetches the thumbnail for the specified url. Returns true if there is a
   // thumbnail for the specified url. It is possible for a URL to be in TopSites
   // but not have an thumbnail.
   bool GetPageThumbnail(const GURL& url,
                         scoped_refptr<base::RefCountedMemory>* bytes);
 
+  // Similar to GetPageThumbnail(), but rather than requiring URL exact match,

[beaudoin, 2013/09/03 23:22:39]

URL exact match --> an exact match

[huangs, 2013/09/04 02:02:05]

Done.

+  // only requires the specified URL to be the prefix of a URL in TopSites.
+  // If multiple matches exist, considers the lexicographically earliest one.

[beaudoin, 2013/09/03 23:22:39]

considers [...] --> returns the thumbnail for the first match in lexicographical
order.

[huangs, 2013/09/04 02:02:05]

Done.

+  bool GetPageThumbnailForPrefix(const GURL& prefix_url,
+                                 scoped_refptr<base::RefCountedMemory>* bytes);
+
   // Fetches the thumbnail score for the specified url. Returns true if
   // there is a thumbnail score for the specified url.
   bool GetPageThumbnailScore(const GURL& url, ThumbnailScore* score);
 
   // Returns the canonical URL for |url|.
   const GURL& GetCanonicalURL(const GURL& url);
 
+  // Returns the canonical URL for |url_prefix|, which specifies a prefix for
+  // stored URLs in |canonical_urls_|.

[beaudoin, 2013/09/03 23:22:39]

I think the comment about favoring the first URL in lexicographical order is
more important here. Rephrase a little, I suggest:

Returns the canonical URL for |url_prefix|. If |url_prefix| matches multiple
entries then the first one in lexicographical order is returned.

(Is it the first one in lexicographical order from |canonical_urls_| or the
canonical url of the first match in lexicographical order??)

[huangs, 2013/09/04 02:02:05]

Also performs canonicalization. Updated comments.

+  const GURL& GetCanonicalURLForPrefix(const GURL& url_prefix);
+
   // Returns true if |url| is known.
   bool IsKnownURL(const GURL& url);
 
   // Returns the index into |top_sites_| for |url|.
   size_t GetURLIndex(const GURL& url);
 
+  // Returns whether or not |url1| is a prefix of |url2|. Criteria:
+  // - Scheme, host, port: exact match required.
+  // - Path: considered as a list of path components (e.g., ["a", "bb"] in
+  //   "/a/bb"), and |url1|'s list must be a prefix of |url2|'s list.
+  // - Query: ignored.
+  // Note that "http://www.google.com/test" is NOT a prefix of
+  // "http://www.google.com/testing", even though "test" is prefix of "testing".

[beaudoin, 2013/09/03 23:22:39]

Nit: a prefix

[huangs, 2013/09/04 02:02:05]

Done.

+  // Also, "http://www.google.com" will not match "http://www.google.com:80".
+  static bool UrlIsPrefix(const GURL& url1, const GURL& url2);
+
  private:
-  // The entries in CanonicalURLs, see CanonicalURLs for details. The second
-  // argument gives the index of the URL into MostVisitedURLs redirects.
-  typedef std::pair<MostVisitedURL*, size_t> CanonicalURLEntry;
-
-  // Comparator used for CanonicalURLs.
-  class CanonicalURLComparator {
-   public:
-    bool operator()(const CanonicalURLEntry& e1,
-                    const CanonicalURLEntry& e2) const {
-      return e1.first->redirects[e1.second] < e2.first->redirects[e2.second];
-    }
-  };
-
   // This is used to map from redirect url to the MostVisitedURL the redirect is
   // from. Ideally this would be map<GURL, size_t> (second param indexing into
   // top_sites_), but this results in duplicating all redirect urls. As some
   // sites have a lot of redirects, we instead use the MostVisitedURL* and the
   // index of the redirect as the key, and the index into top_sites_ as the
   // value. This way we aren't duplicating GURLs. CanonicalURLComparator
   // enforces the ordering as if we were using GURLs.
   typedef std::map<CanonicalURLEntry, size_t,
                    CanonicalURLComparator> CanonicalURLs;
 
   // Generates the set of canonical urls from |top_sites_|.
   void GenerateCanonicalURLs();
 
   // Stores a set of redirects. This is used by GenerateCanonicalURLs.
   void StoreRedirectChain(const RedirectList& redirects, size_t destination);
 
-  // Returns the iterator into canconical_urls_ for the specified url.
-  CanonicalURLs::iterator GetCanonicalURLsIterator(const GURL& url);
+  // Returns the iterator into canonical_urls_ for the |url|. If |match_prefix|
+  // is true, then returns the first iterator into canonical_urls_ that has
+  // |urL| as a path-prefix.

[beaudoin, 2013/09/03 23:22:39]

Nit: |url|

[huangs, 2013/09/04 02:02:05]

Done.

+  CanonicalURLs::iterator GetCanonicalURLsIterator(const GURL& url,
+                                                   bool match_prefix);
 
   // The top sites.
   MostVisitedURLList top_sites_;
 
   // The images. These map from canonical url to image.
   URLToImagesMap images_;
 
   // Generated from the redirects to and from the most visited pages. See
   // description above typedef for details.
   CanonicalURLs canonical_urls_;
 
   DISALLOW_COPY_AND_ASSIGN(TopSitesCache);
 };
 
 }  // namespace history
 
 #endif  // CHROME_BROWSER_HISTORY_TOP_SITES_CACHE_H_