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

url/url_util.cc

Index: url/url_util.cc
diff --git a/url/url_util.cc b/url/url_util.cc
index 0a84d5e23cbed5d4254d8cf17c837ef937fefc53..36ff3bac84e985bc1519fe6dde0898f0b5a2c6a2 100644
--- a/url/url_util.cc
+++ b/url/url_util.cc
@@ -11,6 +11,7 @@
 #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"
@@ -44,12 +45,41 @@ const SchemeWithType kReferrerURLSchemes[kNumReferrerURLSchemes] = {
     {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;
@@ -65,14 +95,14 @@ 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]);
   }
 }
 
@@ -102,31 +132,12 @@ inline bool DoCompareSchemeComponent(const CHAR* spec,
       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);
 }
 
 
@@ -195,7 +206,6 @@ bool DoCanonicalize(const CHAR* in_spec,
   // 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);
@@ -208,7 +218,7 @@ bool DoCanonicalize(const CHAR* in_spec,
                                         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,
@@ -257,10 +267,9 @@ bool DoResolveRelative(const char* base_spec,
     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;
@@ -381,8 +390,7 @@ bool DoReplaceComponents(const char* spec,
     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);
   }
@@ -396,7 +404,7 @@ bool DoReplaceComponents(const char* spec,
 
 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
@@ -412,16 +420,10 @@ void DoAddScheme(const char* 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
@@ -457,8 +459,7 @@ void LockSchemeRegistries() {
 }
 
 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,
@@ -468,14 +469,13 @@ bool GetStandardSchemeType(const char* spec,
 }
 
 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,