Implementing URL prefix match for history thumbnail cache.

chrome/browser/history/top_sites_cache.cc

 // 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.
 
 #include "chrome/browser/history/top_sites_cache.h"
 
+#include <algorithm>
+
 #include "base/logging.h"
 #include "base/memory/ref_counted_memory.h"
 
 namespace history {
 
+bool CanonicalURLComparator::operator()(const CanonicalURLEntry& e1,
+                                        const CanonicalURLEntry& e2) const {
+  return CanonicalURLComparator::CompareString(
+      e1.first->redirects[e1.second].spec(),
+      e2.first->redirects[e2.second].spec());
+}
+
+// static
+bool CanonicalURLComparator::CompareString(const std::string& s1,
+                                           const std::string& s2) {
+  const std::string::value_type* ch1 = s1.c_str();
+  const std::string::value_type* ch2 = s2.c_str();
+  // Find first difference.
+  while (*ch1 && *ch2 && *ch1 == *ch2) {
+    ++ch1;
+    ++ch2;
+  }
+  if (!*ch1 || !*ch2)  // Identical strings, or one is strict prefix of other.
+    return *ch2 != '\0';  // true iff |e1| is strict prefix of |e2|.
+
+  // Now |*ch1| != |*ch2|. Compare using order '?' < '/' < other.
+  //   Table          : |*ch2| = '?' : |*ch2| = "/" : |*ch2| = other
+  // |*ch1| = '?'     :  (excluded)  :     true     :     true
+  // |*ch1| = '/'     :     false    :  (excluded)  :     true
+  // |*ch1| = 'other' :     false    :     false    : |*ch1| < |*ch2|
+  return (*ch1 == '?') || (*ch1 == '/' && *ch2 != '?') ||
+      (*ch2 != '?' && *ch2 != '/' && *ch1 < *ch2);
+}
+
+
 TopSitesCache::TopSitesCache() {
 }
 
 TopSitesCache::~TopSitesCache() {
 }
 
 void TopSitesCache::SetTopSites(const MostVisitedURLList& top_sites) {
   top_sites_ = top_sites;
   GenerateCanonicalURLs();
 }
@@ skipping 14 matching lines @@
   if (found != images_.end()) {
     base::RefCountedMemory* data = found->second.thumbnail.get();
     if (data) {
       *bytes = data;
       return true;
     }
   }
   return false;
 }
 
+bool TopSitesCache::GetPageThumbnailForPrefix(
+    const GURL& prefix_url,
+    scoped_refptr<base::RefCountedMemory>* bytes) {
+  std::map<GURL, Images>::const_iterator found =
+      images_.find(GetCanonicalURLForPrefix(prefix_url));
+  if (found != images_.end()) {
+    base::RefCountedMemory* data = found->second.thumbnail.get();
+    if (data) {
+      *bytes = data;
+      return true;
+    }
+  }
+  return false;
+}
+
 bool TopSitesCache::GetPageThumbnailScore(const GURL& url,
                                           ThumbnailScore* score) {
   std::map<GURL, Images>::const_iterator found =
       images_.find(GetCanonicalURL(url));
   if (found != images_.end()) {
     *score = found->second.thumbnail_score;
     return true;
   }
   return false;
 }
 
 const GURL& TopSitesCache::GetCanonicalURL(const GURL& url) {
-  CanonicalURLs::iterator i = TopSitesCache::GetCanonicalURLsIterator(url);
+  CanonicalURLs::iterator i = GetCanonicalURLsIterator(url, false);
+  return i == canonical_urls_.end() ? url : i->first.first->url;
+}
+
+const GURL& TopSitesCache::GetCanonicalURLForPrefix(const GURL& url) {
+  CanonicalURLs::iterator i = GetCanonicalURLsIterator(url, true);
   return i == canonical_urls_.end() ? url : i->first.first->url;
 }
 
 bool TopSitesCache::IsKnownURL(const GURL& url) {
-  return GetCanonicalURLsIterator(url) != canonical_urls_.end();
+  return GetCanonicalURLsIterator(url, false) != canonical_urls_.end();
 }
 
 size_t TopSitesCache::GetURLIndex(const GURL& url) {
   DCHECK(IsKnownURL(url));
-  return GetCanonicalURLsIterator(url)->second;
+  return GetCanonicalURLsIterator(url, false)->second;
+}
+
+// static
+bool TopSitesCache::UrlIsPrefix(const GURL& url1, const GURL& url2) {
+  if (url1.scheme() != url2.scheme() || url1.host() != url2.host() ||
+      url1.port() != url2.port()) {
+    return false;
+  }
+  // Only need to compare path now. Note that queries are ignored.
+  std::string p1(url1.path());
+  std::string p2(url2.path());
+  if (p1.length() > p2.length())
+    return false;
+  std::pair<std::string::iterator, std::string::iterator> first_diff =
+      std::mismatch(p1.begin(), p1.end(), p2.begin());
+  // Necessary condition: |p1| is a string prefix of |p2|.
+  if (first_diff.first != p1.end())
+    return false;  // E.g.: (|p1| = "/test", |p2| = "/exam") => false.
+
+  // |p1| is string prefix.
+  if (first_diff.second == p2.end())  // Is exact match?
+    return true;  // E.g.: ("/test", "/test") => true.
+  // |p1| is strict string prefix, check full match of last path component.
+  if (!p1.empty() && *p1.rbegin() == '/')  // Ends in '/'?
+    return true;  // E.g.: ("/test/", "/test/stuff") => true.
+
+  // Finally, |p1| does not end in "/": check first extra character in |p2|.
+  // E.g.: ("/test", "/test/stuff") => true; ("/test", "/testing") => false.
+  return *(first_diff.second) == '/';
 }
 
 void TopSitesCache::GenerateCanonicalURLs() {
   canonical_urls_.clear();
   for (size_t i = 0; i < top_sites_.size(); i++)
     StoreRedirectChain(top_sites_[i].redirects, i);
 }
 
 void TopSitesCache::StoreRedirectChain(const RedirectList& redirects,
                                        size_t destination) {
-  // redirects is empty if the user pinned a site and there are not enough top
+  // |redirects| is empty if the user pinned a site and there are not enough top
   // sites before the pinned site.
 
   // Map all the redirected URLs to the destination.
   for (size_t i = 0; i < redirects.size(); i++) {
     // If this redirect is already known, don't replace it with a new one.
     if (!IsKnownURL(redirects[i])) {
       CanonicalURLEntry entry;
       entry.first = &(top_sites_[destination]);
       entry.second = i;
       canonical_urls_[entry] = destination;
     }
   }
 }
 
 TopSitesCache::CanonicalURLs::iterator TopSitesCache::GetCanonicalURLsIterator(
-    const GURL& url) {
+    const GURL& url, bool match_prefix) {
   MostVisitedURL most_visited_url;
   most_visited_url.redirects.push_back(url);
   CanonicalURLEntry entry;
   entry.first = &most_visited_url;
   entry.second = 0u;
-  return canonical_urls_.find(entry);
+  if (!match_prefix)
+    return canonical_urls_.find(entry);
+
+  TopSitesCache::CanonicalURLs::iterator best_it =
+      canonical_urls_.lower_bound(entry);

[beaudoin, 2013/09/04 16:46:10]

Using lower_bound here is really quite clever, but IIUC it relies of the fact
that '/' is smaller than any other character you can find in a path segment.
Your custom comparator ensures that, but you should probably spend some time
detailing that algorithm here and maybe give an example of a sorted list or URLs
and that the first URL in this list that is >= |url| is necessarily of prefix of
|url| if such a prefix exists.

[huangs, 2013/09/04 23:27:39]

Wrote big tl;dr in top_sites_cache.h to explain the key ideas of the algorithms.

+  if (best_it == canonical_urls_.end())
+    return best_it;
+
+  const GURL& comp_url = best_it->first.first->redirects[best_it->first.second];
+  return UrlIsPrefix(url, comp_url) ? best_it : canonical_urls_.end();
 }
 
 }  // namespace history