1b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Copyright (c) 2012 The Chromium Authors. All rights reserved. 2b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Use of this source code is governed by a BSD-style license that can be 3b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// found in the LICENSE file. 4b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// Copied from strings/stringpiece.cc with modifications 5b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 6b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include "base/strings/string_piece.h" 7b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 8cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko#include <limits.h> 9cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko 10b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include <algorithm> 11b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#include <ostream> 12b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 13cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko#include "base/logging.h" 14cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko 15b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratnamespace base { 16b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratnamespace { 17b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 18b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// For each character in characters_wanted, sets the index corresponding 19b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// to the ASCII code of that character to 1 in table. This is used by 20b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// the find_.*_of methods below to tell whether or not a character is in 21b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// the lookup table in constant time. 22b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// The argument `table' must be an array that is large enough to hold all 23b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// the possible values of an unsigned char. Thus it should be be declared 24b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// as follows: 25b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// bool table[UCHAR_MAX + 1] 26b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratinline void BuildLookupTable(const StringPiece& characters_wanted, 27b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat bool* table) { 28b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const size_t length = characters_wanted.length(); 29b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const char* const data = characters_wanted.data(); 30b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t i = 0; i < length; ++i) { 31b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat table[static_cast<unsigned char>(data[i])] = true; 32b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 33b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 34b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 35b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} // namespace 36b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 37b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// MSVC doesn't like complex extern templates and DLLs. 38b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#if !defined(COMPILER_MSVC) 39b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate class BasicStringPiece<std::string>; 40b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate class BasicStringPiece<string16>; 41b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat#endif 42b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 43b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratbool operator==(const StringPiece& x, const StringPiece& y) { 44b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (x.size() != y.size()) 45b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return false; 46b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 47b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::wordmemcmp(x.data(), y.data(), x.size()) == 0; 48b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 49b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 50b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratstd::ostream& operator<<(std::ostream& o, const StringPiece& piece) { 51b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat o.write(piece.data(), static_cast<std::streamsize>(piece.size())); 52b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return o; 53b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 54b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 55b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratnamespace internal { 56b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 57b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 58b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid CopyToStringT(const BasicStringPiece<STR>& self, STR* target) { 59b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.empty()) 60b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat target->clear(); 61b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat else 62b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat target->assign(self.data(), self.size()); 63b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 64b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 65b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid CopyToString(const StringPiece& self, std::string* target) { 66b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat CopyToStringT(self, target); 67b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 68b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 69b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid CopyToString(const StringPiece16& self, string16* target) { 70b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat CopyToStringT(self, target); 71b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 72b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 73b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 74b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid AppendToStringT(const BasicStringPiece<STR>& self, STR* target) { 75b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!self.empty()) 76b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat target->append(self.data(), self.size()); 77b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 78b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 79b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid AppendToString(const StringPiece& self, std::string* target) { 80b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat AppendToStringT(self, target); 81b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 82b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 83b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratvoid AppendToString(const StringPiece16& self, string16* target) { 84b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat AppendToStringT(self, target); 85b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 86b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 87b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 88b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t copyT(const BasicStringPiece<STR>& self, 89b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename STR::value_type* buf, 90b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t n, 91b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 92b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t ret = std::min(self.size() - pos, n); 93b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat memcpy(buf, self.data() + pos, ret * sizeof(typename STR::value_type)); 94b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return ret; 95b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 96b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 97b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t copy(const StringPiece& self, char* buf, size_t n, size_t pos) { 98b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return copyT(self, buf, n, pos); 99b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 100b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 101b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t copy(const StringPiece16& self, char16* buf, size_t n, size_t pos) { 102b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return copyT(self, buf, n, pos); 103b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 104b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 105b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 106b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t findT(const BasicStringPiece<STR>& self, 107b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const BasicStringPiece<STR>& s, 108b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 109b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (pos > self.size()) 110b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 111b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 112b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename BasicStringPiece<STR>::const_iterator result = 113b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::search(self.begin() + pos, self.end(), s.begin(), s.end()); 114b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const size_t xpos = 115b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat static_cast<size_t>(result - self.begin()); 116b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return xpos + s.size() <= self.size() ? xpos : BasicStringPiece<STR>::npos; 117b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 118b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 119b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find(const StringPiece& self, const StringPiece& s, size_t pos) { 120b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return findT(self, s, pos); 121b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 122b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 123b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find(const StringPiece16& self, const StringPiece16& s, size_t pos) { 124b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return findT(self, s, pos); 125b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 126b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 127b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 128b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t findT(const BasicStringPiece<STR>& self, 129b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename STR::value_type c, 130b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 131b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (pos >= self.size()) 132b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 133b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 134b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename BasicStringPiece<STR>::const_iterator result = 135b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::find(self.begin() + pos, self.end(), c); 136b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return result != self.end() ? 137b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat static_cast<size_t>(result - self.begin()) : BasicStringPiece<STR>::npos; 138b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 139b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 140b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find(const StringPiece& self, char c, size_t pos) { 141b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return findT(self, c, pos); 142b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 143b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 144b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find(const StringPiece16& self, char16 c, size_t pos) { 145b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return findT(self, c, pos); 146b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 147b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 148b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 149b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t rfindT(const BasicStringPiece<STR>& self, 150b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const BasicStringPiece<STR>& s, 151b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 152b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() < s.size()) 153b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 154b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 155b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (s.empty()) 156b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return std::min(self.size(), pos); 157b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 158b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename BasicStringPiece<STR>::const_iterator last = 159b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat self.begin() + std::min(self.size() - s.size(), pos) + s.size(); 160b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename BasicStringPiece<STR>::const_iterator result = 161b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::find_end(self.begin(), last, s.begin(), s.end()); 162b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return result != last ? 163b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat static_cast<size_t>(result - self.begin()) : BasicStringPiece<STR>::npos; 164b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 165b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 166b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t rfind(const StringPiece& self, const StringPiece& s, size_t pos) { 167b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return rfindT(self, s, pos); 168b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 169b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 170b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t rfind(const StringPiece16& self, const StringPiece16& s, size_t pos) { 171b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return rfindT(self, s, pos); 172b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 173b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 174b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 175b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t rfindT(const BasicStringPiece<STR>& self, 176b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename STR::value_type c, 177b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 178b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0) 179b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 180b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 181b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t i = std::min(pos, self.size() - 1); ; 182b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat --i) { 183b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.data()[i] == c) 184b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return i; 185b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (i == 0) 186b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat break; 187b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 188b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 189b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 190b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 191b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t rfind(const StringPiece& self, char c, size_t pos) { 192b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return rfindT(self, c, pos); 193b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 194b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 195b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t rfind(const StringPiece16& self, char16 c, size_t pos) { 196b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return rfindT(self, c, pos); 197b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 198b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 199b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 8-bit version using lookup table. 200b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_first_of(const StringPiece& self, 201b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const StringPiece& s, 202b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 203b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0 || s.size() == 0) 204b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 205b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 206b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // Avoid the cost of BuildLookupTable() for a single-character search. 207b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (s.size() == 1) 208b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return find(self, s.data()[0], pos); 209b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 210b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat bool lookup[UCHAR_MAX + 1] = { false }; 211b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat BuildLookupTable(s, lookup); 212b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t i = pos; i < self.size(); ++i) { 213b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (lookup[static_cast<unsigned char>(self.data()[i])]) { 214b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return i; 215b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 216b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 217b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 218b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 219b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 220b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 16-bit brute force version. 221b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_first_of(const StringPiece16& self, 222b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const StringPiece16& s, 223b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 224b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat StringPiece16::const_iterator found = 225b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat std::find_first_of(self.begin() + pos, self.end(), s.begin(), s.end()); 226b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (found == self.end()) 227b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece16::npos; 228b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return found - self.begin(); 229b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 230b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 231b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 8-bit version using lookup table. 232b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_first_not_of(const StringPiece& self, 233b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const StringPiece& s, 234b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 235b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0) 236b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 237b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 238b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (s.size() == 0) 239b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return 0; 240b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 241b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // Avoid the cost of BuildLookupTable() for a single-character search. 242b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (s.size() == 1) 243b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return find_first_not_of(self, s.data()[0], pos); 244b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 245b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat bool lookup[UCHAR_MAX + 1] = { false }; 246b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat BuildLookupTable(s, lookup); 247b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t i = pos; i < self.size(); ++i) { 248b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!lookup[static_cast<unsigned char>(self.data()[i])]) { 249b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return i; 250b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 251b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 252b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 253b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 254b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 255b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 16-bit brute-force version. 256b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratBASE_EXPORT size_t find_first_not_of(const StringPiece16& self, 257b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const StringPiece16& s, 258b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 259b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0) 260b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece16::npos; 261b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 262b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t self_i = pos; self_i < self.size(); ++self_i) { 263b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat bool found = false; 264b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t s_i = 0; s_i < s.size(); ++s_i) { 265b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self[self_i] == s[s_i]) { 266b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat found = true; 267b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat break; 268b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 269b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 270b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!found) 271b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return self_i; 272b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 273b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece16::npos; 274b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 275b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 276b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 277b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_first_not_ofT(const BasicStringPiece<STR>& self, 278b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename STR::value_type c, 279b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 280b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0) 281b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 282b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 283b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (; pos < self.size(); ++pos) { 284b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.data()[pos] != c) { 285b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return pos; 286b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 287b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 288b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 289b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 290b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 291b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_first_not_of(const StringPiece& self, 292b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat char c, 293b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 294b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return find_first_not_ofT(self, c, pos); 295b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 296b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 297b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_first_not_of(const StringPiece16& self, 298b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat char16 c, 299b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 300b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return find_first_not_ofT(self, c, pos); 301b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 302b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 303b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 8-bit version using lookup table. 304b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_last_of(const StringPiece& self, const StringPiece& s, size_t pos) { 305b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0 || s.size() == 0) 306b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 307b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 308b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // Avoid the cost of BuildLookupTable() for a single-character search. 309b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (s.size() == 1) 310b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return rfind(self, s.data()[0], pos); 311b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 312b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat bool lookup[UCHAR_MAX + 1] = { false }; 313b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat BuildLookupTable(s, lookup); 314b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t i = std::min(pos, self.size() - 1); ; --i) { 315b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (lookup[static_cast<unsigned char>(self.data()[i])]) 316b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return i; 317b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (i == 0) 318b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat break; 319b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 320b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 321b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 322b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 323b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 16-bit brute-force version. 324b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_last_of(const StringPiece16& self, 325b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const StringPiece16& s, 326b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 327b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0) 328b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece16::npos; 329b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 330b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t self_i = std::min(pos, self.size() - 1); ; 331b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat --self_i) { 332b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t s_i = 0; s_i < s.size(); s_i++) { 333b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.data()[self_i] == s[s_i]) 334b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return self_i; 335b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 336b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self_i == 0) 337b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat break; 338b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 339b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece16::npos; 340b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 341b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 342b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 8-bit version using lookup table. 343b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_last_not_of(const StringPiece& self, 344b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const StringPiece& s, 345b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 346b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0) 347b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 348b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 349b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t i = std::min(pos, self.size() - 1); 350b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (s.size() == 0) 351b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return i; 352b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 353b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat // Avoid the cost of BuildLookupTable() for a single-character search. 354b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (s.size() == 1) 355b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return find_last_not_of(self, s.data()[0], pos); 356b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 357b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat bool lookup[UCHAR_MAX + 1] = { false }; 358b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat BuildLookupTable(s, lookup); 359b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (; ; --i) { 360b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!lookup[static_cast<unsigned char>(self.data()[i])]) 361b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return i; 362b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (i == 0) 363b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat break; 364b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 365b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 366b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 367b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 368b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat// 16-bit brute-force version. 369b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_last_not_of(const StringPiece16& self, 370b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat const StringPiece16& s, 371b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 372b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0) 373b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece::npos; 374b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 375b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t self_i = std::min(pos, self.size() - 1); ; --self_i) { 376b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat bool found = false; 377b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t s_i = 0; s_i < s.size(); s_i++) { 378b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.data()[self_i] == s[s_i]) { 379b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat found = true; 380b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat break; 381b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 382b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 383b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (!found) 384b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return self_i; 385b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self_i == 0) 386b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat break; 387b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 388b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return StringPiece16::npos; 389b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 390b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 391b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 392b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_last_not_ofT(const BasicStringPiece<STR>& self, 393b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat typename STR::value_type c, 394b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 395b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.size() == 0) 396b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 397b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 398b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat for (size_t i = std::min(pos, self.size() - 1); ; --i) { 399b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (self.data()[i] != c) 400b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return i; 401b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (i == 0) 402b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat break; 403b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat } 404b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>::npos; 405b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 406b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 407b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_last_not_of(const StringPiece& self, 408b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat char c, 409b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 410b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return find_last_not_ofT(self, c, pos); 411b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 412b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 413b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Eratsize_t find_last_not_of(const StringPiece16& self, 414b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat char16 c, 415b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos) { 416b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return find_last_not_ofT(self, c, pos); 417b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 418b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 419b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erattemplate<typename STR> 420b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratBasicStringPiece<STR> substrT(const BasicStringPiece<STR>& self, 421b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos, 422b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t n) { 423b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (pos > self.size()) pos = self.size(); 424b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat if (n > self.size() - pos) n = self.size() - pos; 425b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return BasicStringPiece<STR>(self.data() + pos, n); 426b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 427b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 428b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratStringPiece substr(const StringPiece& self, 429b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos, 430b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t n) { 431b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return substrT(self, pos, n); 432b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 433b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 434b8cf94937c52feb53b55c39e3f82094d27de464cDaniel EratStringPiece16 substr(const StringPiece16& self, 435b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t pos, 436b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat size_t n) { 437b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat return substrT(self, pos, n); 438b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} 439b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat 440cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko#if DCHECK_IS_ON() 441cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenkovoid AssertIteratorsInOrder(std::string::const_iterator begin, 442cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko std::string::const_iterator end) { 443cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko DCHECK(begin <= end) << "StringPiece iterators swapped or invalid."; 444cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko} 445cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenkovoid AssertIteratorsInOrder(string16::const_iterator begin, 446cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko string16::const_iterator end) { 447cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko DCHECK(begin <= end) << "StringPiece iterators swapped or invalid."; 448cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko} 449cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko#endif 450cce46a0c214b37e8da48c522c83037e8ffa4f9fdAlex Vakulenko 451b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} // namespace internal 452b8cf94937c52feb53b55c39e3f82094d27de464cDaniel Erat} // namespace base 453