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