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