Implementing URL prefix match for history thumbnail cache.

chrome/browser/history/url_utils.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/url_utils.h"
+
+#include <algorithm>
+
+namespace history {
+
+namespace {
+
+// Comparator to enforce '\0' < '?' < '#' < '/' < other characters.
+int GetURLCharPriority(char ch) {
+  switch (ch) {
+    case '\0': return 0;
+    case '?': return 1;
+    case '#': return 2;
+    case '/': return 3;
+  }
+  return 4;
+}
+
+}  // namespace
+
+// Instead of splitting URLs and extract path components, we can implement
+// CanonicalURLStringCompare() using string operations only. The key idea is,
+// treating '/' to be less than any valid path characters would make it behave
+// as a separator, so e.g., "test" < "test-case" would be enforced by
+// "test/..." < "test-case/...". We also force "?" < "/", so "test?query" <
+// "test/stuff". Since the routine is merely lexicographical string comparison
+// with remapping of chracter ordering, so it is a valid strict-weak ordering.
+bool CanonicalURLStringCompare(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();
+  while (*ch1 && *ch2 && *ch1 == *ch2) {
+    ++ch1;
+    ++ch2;
+  }
+  int pri_diff = GetURLCharPriority(*ch1) - GetURLCharPriority(*ch2);
+  // We want false to be returned if |pri_diff| > 0.
+  return (pri_diff != 0) ? pri_diff < 0 : *ch1 < *ch2;
+}
+
+bool 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) == '/';
+}
+
+}  // namespace history