[WIP] [url_utils] Implement a contiguous SchemeSet to replace vector<SchemeWithType>

url/url_util.cc

 // Copyright 2013 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 "url/url_util.h"
 
 #include <stddef.h>
 #include <string.h>
 #include <vector>
 
 #include "base/debug/leak_annotations.h"
 #include "base/logging.h"
 #include "base/strings/string_util.h"
+#include "url/scheme_set.h"
 #include "url/url_canon_internal.h"
 #include "url/url_file.h"
 #include "url/url_util_internal.h"
 
 namespace url {
 
 namespace {
 
 const int kNumStandardURLSchemes = 10;
 const SchemeWithType kStandardURLSchemes[kNumStandardURLSchemes] = {
@@ skipping 13 matching lines @@
 };
 
 const int kNumReferrerURLSchemes = 4;
 const SchemeWithType kReferrerURLSchemes[kNumReferrerURLSchemes] = {
     {kHttpScheme, SCHEME_WITH_PORT},
     {kHttpsScheme, SCHEME_WITH_PORT},
     {kHttpSuboriginScheme, SCHEME_WITH_PORT},
     {kHttpsSuboriginScheme, SCHEME_WITH_PORT},
 };
 
+class SchemeWithTypeSet {
+ public:
+  SchemeWithTypeSet() {}
+
+  void add(const SchemeWithType& scheme_with_type) {
+    schemes_.add(scheme_with_type.scheme);
+    types_.push_back(scheme_with_type.type);
+  }
+
+  // Returns true and sets |type| to the SchemeType of the given scheme
+  // identified by |scheme| within |spec| if in |schemes|.
+  template <typename STR>
+  bool contains(base::BasicStringPiece<STR> scheme, SchemeType* type) {
+    size_t index = schemes_.find(scheme);
+    if (index == SchemeSet::npos)
+      return false;
+    if (type)
+      *type = types_[index];
+    return true;
+  }
+
+ private:
+  // Types and schemes must remain in-order with each other.
+  std::vector<SchemeType> types_;
+  SchemeSet schemes_;
+
+  DISALLOW_COPY_AND_ASSIGN(SchemeWithTypeSet);
+};
+
 // Lists of the currently installed standard and referrer schemes. These lists
 // are lazily initialized by InitStandardSchemes and InitReferrerSchemes and are
 // leaked on shutdown to prevent any destructors from being called that will
 // slow us down or cause problems.
-std::vector<SchemeWithType>* standard_schemes = nullptr;
-std::vector<SchemeWithType>* referrer_schemes = nullptr;
+SchemeWithTypeSet* standard_schemes = nullptr;
+SchemeWithTypeSet* referrer_schemes = nullptr;
 
 // See the LockSchemeRegistries declaration in the header.
 bool scheme_registries_locked = false;
 
 // This template converts a given character type to the corresponding
 // StringPiece type.
 template<typename CHAR> struct CharToStringPiece {
 };
 template<> struct CharToStringPiece<char> {
   typedef base::StringPiece Piece;
 };
 template<> struct CharToStringPiece<base::char16> {
   typedef base::StringPiece16 Piece;
 };
 
-void InitSchemes(std::vector<SchemeWithType>** schemes,
+void InitSchemes(SchemeWithTypeSet** schemes,
                  const SchemeWithType* initial_schemes,
                  size_t size) {
   if (*schemes)
     return;
-  *schemes = new std::vector<SchemeWithType>(size);
+  *schemes = new SchemeWithTypeSet();
   for (size_t i = 0; i < size; i++) {
-    (*schemes)->push_back(initial_schemes[i]);
+    (*schemes)->add(initial_schemes[i]);
   }
 }
 
 // Ensures that the standard_schemes list is initialized, does nothing if
 // it already has values.
 void InitStandardSchemes() {
   InitSchemes(&standard_schemes, kStandardURLSchemes, kNumStandardURLSchemes);
 }
 
 // Ensures that the referrer_schemes list is initialized, does nothing if
 // it already has values.
 void InitReferrerSchemes() {
   InitSchemes(&referrer_schemes, kReferrerURLSchemes, kNumReferrerURLSchemes);
 }
 
 // Given a string and a range inside the string, compares it to the given
 // lower-case |compare_to| buffer.
 template<typename CHAR>
 inline bool DoCompareSchemeComponent(const CHAR* spec,
                                      const Component& component,
                                      const char* compare_to) {
   if (!component.is_nonempty())
     return compare_to[0] == 0;  // When component is empty, match empty scheme.
   return base::LowerCaseEqualsASCII(
       typename CharToStringPiece<CHAR>::Piece(
           &spec[component.begin], component.len),
       compare_to);
 }
 
-// Returns true and sets |type| to the SchemeType of the given scheme
-// identified by |scheme| within |spec| if in |schemes|.
-template<typename CHAR>
-bool DoIsInSchemes(const CHAR* spec,
-                   const Component& scheme,
-                   SchemeType* type,
-                   const std::vector<SchemeWithType>& schemes) {
-  if (!scheme.is_nonempty())
-    return false;  // Empty or invalid schemes are non-standard.
-
-  for (const SchemeWithType& scheme_with_type : schemes) {
-    if (base::LowerCaseEqualsASCII(typename CharToStringPiece<CHAR>::Piece(
-                                       &spec[scheme.begin], scheme.len),
-                                   scheme_with_type.scheme)) {
-      *type = scheme_with_type.type;
-      return true;
-    }
-  }
-  return false;
-}
-
 template<typename CHAR>
 bool DoIsStandard(const CHAR* spec, const Component& scheme, SchemeType* type) {
   InitStandardSchemes();
-  return DoIsInSchemes(spec, scheme, type, *standard_schemes);
+  return standard_schemes->contains(
+      typename CharToStringPiece<CHAR>::Piece(&spec[scheme.begin], scheme.len),
+      type);
 }
 
 
 template<typename CHAR>
 bool DoFindAndCompareScheme(const CHAR* str,
                             int str_len,
                             const char* compare,
                             Component* found_scheme) {
   // Before extracting scheme, canonicalize the URL to remove any whitespace.
   // This matches the canonicalization done in DoCanonicalize function.
@@ skipping 48 matching lines @@
   }
 #endif
 
   Component scheme;
   if (!ExtractScheme(spec, spec_len, &scheme))
     return false;
 
   // This is the parsed version of the input URL, we have to canonicalize it
   // before storing it in our object.
   bool success;
-  SchemeType unused_scheme_type = SCHEME_WITH_PORT;
   if (DoCompareSchemeComponent(spec, scheme, url::kFileScheme)) {
     // File URLs are special.
     ParseFileURL(spec, spec_len, &parsed_input);
     success = CanonicalizeFileURL(spec, spec_len, parsed_input,
                                   charset_converter, output, output_parsed);
   } else if (DoCompareSchemeComponent(spec, scheme, url::kFileSystemScheme)) {
     // Filesystem URLs are special.
     ParseFileSystemURL(spec, spec_len, &parsed_input);
     success = CanonicalizeFileSystemURL(spec, spec_len, parsed_input,
                                         charset_converter, output,
                                         output_parsed);
 
-  } else if (DoIsStandard(spec, scheme, &unused_scheme_type)) {
+  } else if (DoIsStandard(spec, scheme, nullptr)) {
     // All "normal" URLs.
     ParseStandardURL(spec, spec_len, &parsed_input);
     success = CanonicalizeStandardURL(spec, spec_len, parsed_input,
                                       charset_converter, output, output_parsed);
 
   } else if (DoCompareSchemeComponent(spec, scheme, url::kMailToScheme)) {
     // Mailto URLs are treated like standard URLs, with only a scheme, path,
     // and query.
     ParseMailtoURL(spec, spec_len, &parsed_input);
     success = CanonicalizeMailtoURL(spec, spec_len, parsed_input, output,
@@ skipping 28 matching lines @@
   bool base_is_hierarchical = false;
   if (base_spec &&
       base_parsed.scheme.is_nonempty()) {
     int after_scheme = base_parsed.scheme.end() + 1;  // Skip past the colon.
     int num_slashes = CountConsecutiveSlashes(base_spec, after_scheme,
                                               base_spec_len);
     base_is_authority_based = num_slashes > 1;
     base_is_hierarchical = num_slashes > 0;
   }
 
-  SchemeType unused_scheme_type = SCHEME_WITH_PORT;
   bool standard_base_scheme =
       base_parsed.scheme.is_nonempty() &&
-      DoIsStandard(base_spec, base_parsed.scheme, &unused_scheme_type);
+      DoIsStandard(base_spec, base_parsed.scheme, nullptr);
 
   bool is_relative;
   Component relative_component;
   if (!IsRelativeURL(base_spec, base_parsed, relative, relative_length,
                      (base_is_hierarchical || standard_base_scheme),
                      &is_relative, &relative_component)) {
     // Error resolving.
     return false;
   }
 
@@ skipping 100 matching lines @@
   // If we get here, then we know the scheme doesn't need to be replaced, so can
   // just key off the scheme in the spec to know how to do the replacements.
   if (DoCompareSchemeComponent(spec, parsed.scheme, url::kFileScheme)) {
     return ReplaceFileURL(spec, parsed, replacements, charset_converter, output,
                           out_parsed);
   }
   if (DoCompareSchemeComponent(spec, parsed.scheme, url::kFileSystemScheme)) {
     return ReplaceFileSystemURL(spec, parsed, replacements, charset_converter,
                                 output, out_parsed);
   }
-  SchemeType unused_scheme_type = SCHEME_WITH_PORT;
-  if (DoIsStandard(spec, parsed.scheme, &unused_scheme_type)) {
+  if (DoIsStandard(spec, parsed.scheme, nullptr)) {
     return ReplaceStandardURL(spec, parsed, replacements, charset_converter,
                               output, out_parsed);
   }
   if (DoCompareSchemeComponent(spec, parsed.scheme, url::kMailToScheme)) {
     return ReplaceMailtoURL(spec, parsed, replacements, output, out_parsed);
   }
 
   // Default is a path URL.
   return ReplacePathURL(spec, parsed, replacements, output, out_parsed);
 }
 
 void DoAddScheme(const char* new_scheme,
                  SchemeType type,
-                 std::vector<SchemeWithType>* schemes) {
+                 SchemeWithTypeSet* schemes) {
   DCHECK(schemes);
   // If this assert triggers, it means you've called Add*Scheme after
   // LockSchemeRegistries has been called (see the header file for
   // LockSchemeRegistries for more).
   //
   // This normally means you're trying to set up a new scheme too late in your
   // application's init process. Locate where your app does this initialization
   // and calls LockSchemeRegistries, and add your new scheme there.
   DCHECK(!scheme_registries_locked)
       << "Trying to add a scheme after the lists have been locked.";
 
   size_t scheme_len = strlen(new_scheme);
   if (scheme_len == 0)
     return;
 
-  // Duplicate the scheme into a new buffer and add it to the list of standard
-  // schemes. This pointer will be leaked on shutdown.
-  char* dup_scheme = new char[scheme_len + 1];
-  ANNOTATE_LEAKING_OBJECT_PTR(dup_scheme);
-  memcpy(dup_scheme, new_scheme, scheme_len + 1);
-
   SchemeWithType scheme_with_type;
-  scheme_with_type.scheme = dup_scheme;
+  scheme_with_type.scheme = new_scheme;
   scheme_with_type.type = type;
-  schemes->push_back(scheme_with_type);
+  schemes->add(scheme_with_type);
 }
 
 }  // namespace
 
 void Initialize() {
   InitStandardSchemes();
   InitReferrerSchemes();
 }
 
 void Shutdown() {
@@ skipping 15 matching lines @@
 void AddReferrerScheme(const char* new_scheme, SchemeType type) {
   InitReferrerSchemes();
   DoAddScheme(new_scheme, type, referrer_schemes);
 }
 
 void LockSchemeRegistries() {
   scheme_registries_locked = true;
 }
 
 bool IsStandard(const char* spec, const Component& scheme) {
-  SchemeType unused_scheme_type;
-  return DoIsStandard(spec, scheme, &unused_scheme_type);
+  return DoIsStandard(spec, scheme, nullptr);
 }
 
 bool GetStandardSchemeType(const char* spec,
                            const Component& scheme,
                            SchemeType* type) {
   return DoIsStandard(spec, scheme, type);
 }
 
 bool IsStandard(const base::char16* spec, const Component& scheme) {
-  SchemeType unused_scheme_type;
-  return DoIsStandard(spec, scheme, &unused_scheme_type);
+  return DoIsStandard(spec, scheme, nullptr);
 }
 
 bool IsReferrerScheme(const char* spec, const Component& scheme) {
   InitReferrerSchemes();
-  SchemeType unused_scheme_type;
-  return DoIsInSchemes(spec, scheme, &unused_scheme_type, *referrer_schemes);
+  return referrer_schemes->contains(
+      base::StringPiece(&spec[scheme.begin], scheme.len), nullptr);
 }
 
 bool FindAndCompareScheme(const char* str,
                           int str_len,
                           const char* compare,
                           Component* found_scheme) {
   return DoFindAndCompareScheme(str, str_len, compare, found_scheme);
 }
 
 bool FindAndCompareScheme(const base::char16* str,
@@ skipping 174 matching lines @@
   return DoCompareSchemeComponent(spec, component, compare_to);
 }
 
 bool CompareSchemeComponent(const base::char16* spec,
                             const Component& component,
                             const char* compare_to) {
   return DoCompareSchemeComponent(spec, component, compare_to);
 }
 
 }  // namespace url