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

url/scheme_set.h

+// Copyright 2016 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 URL_SCHEME_SET_H_
+#define URL_SCHEME_SET_H_
+
+#include <string>
+#include <vector>
+
+#include "base/macros.h"
+#include "base/strings/string_piece.h"
+#include "base/strings/string_util.h"
+
+namespace url {
+
+// Data structure for fast |contains| operations. Schemes are kepts in a
+// contiguous block of memory.
+// TODO(csharrison): Add a remove method, and use this in the SchemeRegistry in
+// Blink.
+class SchemeSet {
+ public:
+  static const size_t npos = static_cast<size_t>(-1);
+  SchemeSet();
+  ~SchemeSet();
+
+  void add(const char* scheme);
+
+  // TODO(csharrison): Implement a fast path for schemes guaranteed to be
+  // canonicalized, so equality checking can be done in a case sensitive manner.
+  template <typename STR>
+  size_t find(const base::BasicStringPiece<STR>& scheme) {
+    if (scheme.empty())
+      return false;  // Empty or invalid schemes are non-standard.
+    for (size_t i = 0; i < pieces_.size(); ++i) {
+      const auto& scheme_piece = pieces_[i];
+      base::StringPiece piece = base::StringPiece(
+          backing_string_.c_str() + scheme_piece.begin, scheme_piece.end);
+      if (base::LowerCaseEqualsASCII(scheme, piece))
+        return i;
+    }
+    return npos;
+  }
+
+ private:
+  struct SchemeIndex {
+    SchemeIndex(size_t begin, size_t end) : begin(begin), end(end) {}
+    size_t begin;
+    size_t end;
+  };
+  std::vector<SchemeIndex> pieces_;
+  std::string backing_string_;
+
+  DISALLOW_COPY_AND_ASSIGN(SchemeSet);
+};
+
+}  // namespace url
+
+#endif  // URL_SCHEME_SET_H_