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 11 namespace base { 12 namespace { 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] 22 inline 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) 35 template class BasicStringPiece<std::string>; 36 template class BasicStringPiece<string16>; 37 #endif 38 39 bool 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 46 std::ostream& operator<<(std::ostream& o, const StringPiece& piece) { 47 o.write(piece.data(), static_cast<std::streamsize>(piece.size())); 48 return o; 49 } 50 51 namespace internal { 52 53 template<typename STR> 54 void 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 61 void CopyToString(const StringPiece& self, std::string* target) { 62 CopyToStringT(self, target); 63 } 64 65 void CopyToString(const StringPiece16& self, string16* target) { 66 CopyToStringT(self, target); 67 } 68 69 template<typename STR> 70 void AppendToStringT(const BasicStringPiece<STR>& self, STR* target) { 71 if (!self.empty()) 72 target->append(self.data(), self.size()); 73 } 74 75 void AppendToString(const StringPiece& self, std::string* target) { 76 AppendToStringT(self, target); 77 } 78 79 void AppendToString(const StringPiece16& self, string16* target) { 80 AppendToStringT(self, target); 81 } 82 83 template<typename STR> 84 size_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 93 size_t copy(const StringPiece& self, char* buf, size_t n, size_t pos) { 94 return copyT(self, buf, n, pos); 95 } 96 97 size_t copy(const StringPiece16& self, char16* buf, size_t n, size_t pos) { 98 return copyT(self, buf, n, pos); 99 } 100 101 template<typename STR> 102 size_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 115 size_t find(const StringPiece& self, const StringPiece& s, size_t pos) { 116 return findT(self, s, pos); 117 } 118 119 size_t find(const StringPiece16& self, const StringPiece16& s, size_t pos) { 120 return findT(self, s, pos); 121 } 122 123 template<typename STR> 124 size_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 136 size_t find(const StringPiece& self, char c, size_t pos) { 137 return findT(self, c, pos); 138 } 139 140 size_t find(const StringPiece16& self, char16 c, size_t pos) { 141 return findT(self, c, pos); 142 } 143 144 template<typename STR> 145 size_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 162 size_t rfind(const StringPiece& self, const StringPiece& s, size_t pos) { 163 return rfindT(self, s, pos); 164 } 165 166 size_t rfind(const StringPiece16& self, const StringPiece16& s, size_t pos) { 167 return rfindT(self, s, pos); 168 } 169 170 template<typename STR> 171 size_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 187 size_t rfind(const StringPiece& self, char c, size_t pos) { 188 return rfindT(self, c, pos); 189 } 190 191 size_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. 196 size_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. 217 size_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. 228 size_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. 252 BASE_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 272 template<typename STR> 273 size_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 287 size_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 293 size_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. 300 size_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. 320 size_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. 339 size_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. 365 size_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 387 template<typename STR> 388 size_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 403 size_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 409 size_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 415 template<typename STR> 416 BasicStringPiece<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 424 StringPiece substr(const StringPiece& self, 425 size_t pos, 426 size_t n) { 427 return substrT(self, pos, n); 428 } 429 430 StringPiece16 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
