1 // -*- C++ -*- 2 //===-------------------------- __string ----------------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is distributed under the University of Illinois Open Source 7 // License. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP___STRING 12 #define _LIBCPP___STRING 13 14 /* 15 string synopsis 16 17 namespace std 18 { 19 20 template <class charT> 21 struct char_traits 22 { 23 typedef charT char_type; 24 typedef ... int_type; 25 typedef streamoff off_type; 26 typedef streampos pos_type; 27 typedef mbstate_t state_type; 28 29 static constexpr void assign(char_type& c1, const char_type& c2) noexcept; 30 static constexpr bool eq(char_type c1, char_type c2) noexcept; 31 static constexpr bool lt(char_type c1, char_type c2) noexcept; 32 33 static constexpr int compare(const char_type* s1, const char_type* s2, size_t n); 34 static constexpr size_t length(const char_type* s); 35 static constexpr const char_type* 36 find(const char_type* s, size_t n, const char_type& a); 37 static char_type* move(char_type* s1, const char_type* s2, size_t n); 38 static char_type* copy(char_type* s1, const char_type* s2, size_t n); 39 static char_type* assign(char_type* s, size_t n, char_type a); 40 41 static constexpr int_type not_eof(int_type c) noexcept; 42 static constexpr char_type to_char_type(int_type c) noexcept; 43 static constexpr int_type to_int_type(char_type c) noexcept; 44 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept; 45 static constexpr int_type eof() noexcept; 46 }; 47 48 template <> struct char_traits<char>; 49 template <> struct char_traits<wchar_t>; 50 51 } // std 52 53 */ 54 55 #include <__config> 56 #include <algorithm> // for search and min 57 #include <cstdio> // For EOF. 58 #include <memory> // for __murmur2_or_cityhash 59 60 #include <__undef_min_max> 61 62 #include <__debug> 63 64 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 65 #pragma GCC system_header 66 #endif 67 68 _LIBCPP_BEGIN_NAMESPACE_STD 69 70 // char_traits 71 72 template <class _CharT> 73 struct _LIBCPP_TEMPLATE_VIS char_traits 74 { 75 typedef _CharT char_type; 76 typedef int int_type; 77 typedef streamoff off_type; 78 typedef streampos pos_type; 79 typedef mbstate_t state_type; 80 81 static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14 82 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 83 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 84 {return __c1 == __c2;} 85 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 86 {return __c1 < __c2;} 87 88 static _LIBCPP_CONSTEXPR_AFTER_CXX14 89 int compare(const char_type* __s1, const char_type* __s2, size_t __n); 90 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 91 size_t length(const char_type* __s); 92 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 93 const char_type* find(const char_type* __s, size_t __n, const char_type& __a); 94 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n); 95 _LIBCPP_INLINE_VISIBILITY 96 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n); 97 _LIBCPP_INLINE_VISIBILITY 98 static char_type* assign(char_type* __s, size_t __n, char_type __a); 99 100 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 101 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 102 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 103 {return char_type(__c);} 104 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 105 {return int_type(__c);} 106 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 107 {return __c1 == __c2;} 108 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 109 {return int_type(EOF);} 110 }; 111 112 template <class _CharT> 113 _LIBCPP_CONSTEXPR_AFTER_CXX14 int 114 char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n) 115 { 116 for (; __n; --__n, ++__s1, ++__s2) 117 { 118 if (lt(*__s1, *__s2)) 119 return -1; 120 if (lt(*__s2, *__s1)) 121 return 1; 122 } 123 return 0; 124 } 125 126 template <class _CharT> 127 inline 128 _LIBCPP_CONSTEXPR_AFTER_CXX14 size_t 129 char_traits<_CharT>::length(const char_type* __s) 130 { 131 size_t __len = 0; 132 for (; !eq(*__s, char_type(0)); ++__s) 133 ++__len; 134 return __len; 135 } 136 137 template <class _CharT> 138 inline 139 _LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT* 140 char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a) 141 { 142 for (; __n; --__n) 143 { 144 if (eq(*__s, __a)) 145 return __s; 146 ++__s; 147 } 148 return 0; 149 } 150 151 template <class _CharT> 152 _CharT* 153 char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n) 154 { 155 char_type* __r = __s1; 156 if (__s1 < __s2) 157 { 158 for (; __n; --__n, ++__s1, ++__s2) 159 assign(*__s1, *__s2); 160 } 161 else if (__s2 < __s1) 162 { 163 __s1 += __n; 164 __s2 += __n; 165 for (; __n; --__n) 166 assign(*--__s1, *--__s2); 167 } 168 return __r; 169 } 170 171 template <class _CharT> 172 inline 173 _CharT* 174 char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n) 175 { 176 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 177 char_type* __r = __s1; 178 for (; __n; --__n, ++__s1, ++__s2) 179 assign(*__s1, *__s2); 180 return __r; 181 } 182 183 template <class _CharT> 184 inline 185 _CharT* 186 char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a) 187 { 188 char_type* __r = __s; 189 for (; __n; --__n, ++__s) 190 assign(*__s, __a); 191 return __r; 192 } 193 194 // char_traits<char> 195 196 template <> 197 struct _LIBCPP_TEMPLATE_VIS char_traits<char> 198 { 199 typedef char char_type; 200 typedef int int_type; 201 typedef streamoff off_type; 202 typedef streampos pos_type; 203 typedef mbstate_t state_type; 204 205 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 206 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 207 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 208 {return __c1 == __c2;} 209 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 210 {return (unsigned char)__c1 < (unsigned char)__c2;} 211 212 static _LIBCPP_CONSTEXPR_AFTER_CXX14 213 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 214 static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14 215 length(const char_type* __s) _NOEXCEPT {return __builtin_strlen(__s);} 216 static _LIBCPP_CONSTEXPR_AFTER_CXX14 217 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 218 static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 219 {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);} 220 static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 221 { 222 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 223 return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n); 224 } 225 static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 226 {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);} 227 228 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 229 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 230 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 231 {return char_type(__c);} 232 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 233 {return int_type((unsigned char)__c);} 234 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 235 {return __c1 == __c2;} 236 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 237 {return int_type(EOF);} 238 }; 239 240 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 241 int 242 char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 243 { 244 if (__n == 0) 245 return 0; 246 #if __has_feature(cxx_constexpr_string_builtins) 247 return __builtin_memcmp(__s1, __s2, __n); 248 #elif _LIBCPP_STD_VER <= 14 249 return memcmp(__s1, __s2, __n); 250 #else 251 for (; __n; --__n, ++__s1, ++__s2) 252 { 253 if (lt(*__s1, *__s2)) 254 return -1; 255 if (lt(*__s2, *__s1)) 256 return 1; 257 } 258 return 0; 259 #endif 260 } 261 262 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 263 const char* 264 char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 265 { 266 if (__n == 0) 267 return NULL; 268 #if __has_feature(cxx_constexpr_string_builtins) 269 return __builtin_char_memchr(__s, to_int_type(__a), __n); 270 #elif _LIBCPP_STD_VER <= 14 271 return (const char_type*) memchr(__s, to_int_type(__a), __n); 272 #else 273 for (; __n; --__n) 274 { 275 if (eq(*__s, __a)) 276 return __s; 277 ++__s; 278 } 279 return NULL; 280 #endif 281 } 282 283 284 // char_traits<wchar_t> 285 286 template <> 287 struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t> 288 { 289 typedef wchar_t char_type; 290 typedef wint_t int_type; 291 typedef streamoff off_type; 292 typedef streampos pos_type; 293 typedef mbstate_t state_type; 294 295 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 296 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 297 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 298 {return __c1 == __c2;} 299 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 300 {return __c1 < __c2;} 301 302 static _LIBCPP_CONSTEXPR_AFTER_CXX14 303 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 304 static _LIBCPP_CONSTEXPR_AFTER_CXX14 305 size_t length(const char_type* __s) _NOEXCEPT; 306 static _LIBCPP_CONSTEXPR_AFTER_CXX14 307 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 308 static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 309 {return __n == 0 ? __s1 : (char_type*)wmemmove(__s1, __s2, __n);} 310 static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 311 { 312 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 313 return __n == 0 ? __s1 : (char_type*)wmemcpy(__s1, __s2, __n); 314 } 315 static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 316 {return __n == 0 ? __s : (char_type*)wmemset(__s, __a, __n);} 317 318 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 319 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 320 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 321 {return char_type(__c);} 322 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 323 {return int_type(__c);} 324 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 325 {return __c1 == __c2;} 326 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 327 {return int_type(WEOF);} 328 }; 329 330 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 331 int 332 char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 333 { 334 if (__n == 0) 335 return 0; 336 #if __has_feature(cxx_constexpr_string_builtins) 337 return __builtin_wmemcmp(__s1, __s2, __n); 338 #elif _LIBCPP_STD_VER <= 14 339 return wmemcmp(__s1, __s2, __n); 340 #else 341 for (; __n; --__n, ++__s1, ++__s2) 342 { 343 if (lt(*__s1, *__s2)) 344 return -1; 345 if (lt(*__s2, *__s1)) 346 return 1; 347 } 348 return 0; 349 #endif 350 } 351 352 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 353 size_t 354 char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT 355 { 356 #if __has_feature(cxx_constexpr_string_builtins) 357 return __builtin_wcslen(__s); 358 #elif _LIBCPP_STD_VER <= 14 359 return wcslen(__s); 360 #else 361 size_t __len = 0; 362 for (; !eq(*__s, char_type(0)); ++__s) 363 ++__len; 364 return __len; 365 #endif 366 } 367 368 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 369 const wchar_t* 370 char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 371 { 372 if (__n == 0) 373 return NULL; 374 #if __has_feature(cxx_constexpr_string_builtins) 375 return __builtin_wmemchr(__s, __a, __n); 376 #elif _LIBCPP_STD_VER <= 14 377 return wmemchr(__s, __a, __n); 378 #else 379 for (; __n; --__n) 380 { 381 if (eq(*__s, __a)) 382 return __s; 383 ++__s; 384 } 385 return NULL; 386 #endif 387 } 388 389 390 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS 391 392 template <> 393 struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t> 394 { 395 typedef char16_t char_type; 396 typedef uint_least16_t int_type; 397 typedef streamoff off_type; 398 typedef u16streampos pos_type; 399 typedef mbstate_t state_type; 400 401 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 402 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 403 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 404 {return __c1 == __c2;} 405 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 406 {return __c1 < __c2;} 407 408 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 409 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 410 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 411 size_t length(const char_type* __s) _NOEXCEPT; 412 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 413 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 414 _LIBCPP_INLINE_VISIBILITY 415 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 416 _LIBCPP_INLINE_VISIBILITY 417 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 418 _LIBCPP_INLINE_VISIBILITY 419 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT; 420 421 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 422 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 423 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 424 {return char_type(__c);} 425 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 426 {return int_type(__c);} 427 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 428 {return __c1 == __c2;} 429 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 430 {return int_type(0xFFFF);} 431 }; 432 433 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 434 int 435 char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 436 { 437 for (; __n; --__n, ++__s1, ++__s2) 438 { 439 if (lt(*__s1, *__s2)) 440 return -1; 441 if (lt(*__s2, *__s1)) 442 return 1; 443 } 444 return 0; 445 } 446 447 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 448 size_t 449 char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT 450 { 451 size_t __len = 0; 452 for (; !eq(*__s, char_type(0)); ++__s) 453 ++__len; 454 return __len; 455 } 456 457 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 458 const char16_t* 459 char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 460 { 461 for (; __n; --__n) 462 { 463 if (eq(*__s, __a)) 464 return __s; 465 ++__s; 466 } 467 return 0; 468 } 469 470 inline 471 char16_t* 472 char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 473 { 474 char_type* __r = __s1; 475 if (__s1 < __s2) 476 { 477 for (; __n; --__n, ++__s1, ++__s2) 478 assign(*__s1, *__s2); 479 } 480 else if (__s2 < __s1) 481 { 482 __s1 += __n; 483 __s2 += __n; 484 for (; __n; --__n) 485 assign(*--__s1, *--__s2); 486 } 487 return __r; 488 } 489 490 inline 491 char16_t* 492 char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 493 { 494 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 495 char_type* __r = __s1; 496 for (; __n; --__n, ++__s1, ++__s2) 497 assign(*__s1, *__s2); 498 return __r; 499 } 500 501 inline 502 char16_t* 503 char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 504 { 505 char_type* __r = __s; 506 for (; __n; --__n, ++__s) 507 assign(*__s, __a); 508 return __r; 509 } 510 511 template <> 512 struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t> 513 { 514 typedef char32_t char_type; 515 typedef uint_least32_t int_type; 516 typedef streamoff off_type; 517 typedef u32streampos pos_type; 518 typedef mbstate_t state_type; 519 520 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 521 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 522 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 523 {return __c1 == __c2;} 524 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 525 {return __c1 < __c2;} 526 527 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 528 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 529 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 530 size_t length(const char_type* __s) _NOEXCEPT; 531 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 532 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 533 _LIBCPP_INLINE_VISIBILITY 534 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 535 _LIBCPP_INLINE_VISIBILITY 536 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 537 _LIBCPP_INLINE_VISIBILITY 538 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT; 539 540 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 541 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 542 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 543 {return char_type(__c);} 544 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 545 {return int_type(__c);} 546 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 547 {return __c1 == __c2;} 548 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 549 {return int_type(0xFFFFFFFF);} 550 }; 551 552 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 553 int 554 char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 555 { 556 for (; __n; --__n, ++__s1, ++__s2) 557 { 558 if (lt(*__s1, *__s2)) 559 return -1; 560 if (lt(*__s2, *__s1)) 561 return 1; 562 } 563 return 0; 564 } 565 566 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 567 size_t 568 char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT 569 { 570 size_t __len = 0; 571 for (; !eq(*__s, char_type(0)); ++__s) 572 ++__len; 573 return __len; 574 } 575 576 inline _LIBCPP_CONSTEXPR_AFTER_CXX14 577 const char32_t* 578 char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 579 { 580 for (; __n; --__n) 581 { 582 if (eq(*__s, __a)) 583 return __s; 584 ++__s; 585 } 586 return 0; 587 } 588 589 inline 590 char32_t* 591 char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 592 { 593 char_type* __r = __s1; 594 if (__s1 < __s2) 595 { 596 for (; __n; --__n, ++__s1, ++__s2) 597 assign(*__s1, *__s2); 598 } 599 else if (__s2 < __s1) 600 { 601 __s1 += __n; 602 __s2 += __n; 603 for (; __n; --__n) 604 assign(*--__s1, *--__s2); 605 } 606 return __r; 607 } 608 609 inline 610 char32_t* 611 char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 612 { 613 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 614 char_type* __r = __s1; 615 for (; __n; --__n, ++__s1, ++__s2) 616 assign(*__s1, *__s2); 617 return __r; 618 } 619 620 inline 621 char32_t* 622 char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 623 { 624 char_type* __r = __s; 625 for (; __n; --__n, ++__s) 626 assign(*__s, __a); 627 return __r; 628 } 629 630 #endif // _LIBCPP_HAS_NO_UNICODE_CHARS 631 632 // helper fns for basic_string and string_view 633 634 // __str_find 635 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 636 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 637 __str_find(const _CharT *__p, _SizeT __sz, 638 _CharT __c, _SizeT __pos) _NOEXCEPT 639 { 640 if (__pos >= __sz) 641 return __npos; 642 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c); 643 if (__r == 0) 644 return __npos; 645 return static_cast<_SizeT>(__r - __p); 646 } 647 648 template <class _CharT, class _Traits> 649 inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT * 650 __search_substring(const _CharT *__first1, const _CharT *__last1, 651 const _CharT *__first2, const _CharT *__last2) { 652 // Take advantage of knowing source and pattern lengths. 653 // Stop short when source is smaller than pattern. 654 const ptrdiff_t __len2 = __last2 - __first2; 655 if (__len2 == 0) 656 return __first1; 657 658 ptrdiff_t __len1 = __last1 - __first1; 659 if (__len1 < __len2) 660 return __last1; 661 662 // First element of __first2 is loop invariant. 663 _CharT __f2 = *__first2; 664 while (true) { 665 __len1 = __last1 - __first1; 666 // Check whether __first1 still has at least __len2 bytes. 667 if (__len1 < __len2) 668 return __last1; 669 670 // Find __f2 the first byte matching in __first1. 671 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2); 672 if (__first1 == 0) 673 return __last1; 674 675 // It is faster to compare from the first byte of __first1 even if we 676 // already know that it matches the first byte of __first2: this is because 677 // __first2 is most likely aligned, as it is user's "pattern" string, and 678 // __first1 + 1 is most likely not aligned, as the match is in the middle of 679 // the string. 680 if (_Traits::compare(__first1, __first2, __len2) == 0) 681 return __first1; 682 683 ++__first1; 684 } 685 } 686 687 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 688 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 689 __str_find(const _CharT *__p, _SizeT __sz, 690 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 691 { 692 if (__pos > __sz) 693 return __npos; 694 695 if (__n == 0) // There is nothing to search, just return __pos. 696 return __pos; 697 698 const _CharT *__r = __search_substring<_CharT, _Traits>( 699 __p + __pos, __p + __sz, __s, __s + __n); 700 701 if (__r == __p + __sz) 702 return __npos; 703 return static_cast<_SizeT>(__r - __p); 704 } 705 706 707 // __str_rfind 708 709 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 710 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 711 __str_rfind(const _CharT *__p, _SizeT __sz, 712 _CharT __c, _SizeT __pos) _NOEXCEPT 713 { 714 if (__sz < 1) 715 return __npos; 716 if (__pos < __sz) 717 ++__pos; 718 else 719 __pos = __sz; 720 for (const _CharT* __ps = __p + __pos; __ps != __p;) 721 { 722 if (_Traits::eq(*--__ps, __c)) 723 return static_cast<_SizeT>(__ps - __p); 724 } 725 return __npos; 726 } 727 728 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 729 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 730 __str_rfind(const _CharT *__p, _SizeT __sz, 731 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 732 { 733 __pos = _VSTD::min(__pos, __sz); 734 if (__n < __sz - __pos) 735 __pos += __n; 736 else 737 __pos = __sz; 738 const _CharT* __r = _VSTD::__find_end( 739 __p, __p + __pos, __s, __s + __n, _Traits::eq, 740 random_access_iterator_tag(), random_access_iterator_tag()); 741 if (__n > 0 && __r == __p + __pos) 742 return __npos; 743 return static_cast<_SizeT>(__r - __p); 744 } 745 746 // __str_find_first_of 747 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 748 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 749 __str_find_first_of(const _CharT *__p, _SizeT __sz, 750 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 751 { 752 if (__pos >= __sz || __n == 0) 753 return __npos; 754 const _CharT* __r = _VSTD::__find_first_of_ce 755 (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq ); 756 if (__r == __p + __sz) 757 return __npos; 758 return static_cast<_SizeT>(__r - __p); 759 } 760 761 762 // __str_find_last_of 763 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 764 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 765 __str_find_last_of(const _CharT *__p, _SizeT __sz, 766 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 767 { 768 if (__n != 0) 769 { 770 if (__pos < __sz) 771 ++__pos; 772 else 773 __pos = __sz; 774 for (const _CharT* __ps = __p + __pos; __ps != __p;) 775 { 776 const _CharT* __r = _Traits::find(__s, __n, *--__ps); 777 if (__r) 778 return static_cast<_SizeT>(__ps - __p); 779 } 780 } 781 return __npos; 782 } 783 784 785 // __str_find_first_not_of 786 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 787 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 788 __str_find_first_not_of(const _CharT *__p, _SizeT __sz, 789 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 790 { 791 if (__pos < __sz) 792 { 793 const _CharT* __pe = __p + __sz; 794 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) 795 if (_Traits::find(__s, __n, *__ps) == 0) 796 return static_cast<_SizeT>(__ps - __p); 797 } 798 return __npos; 799 } 800 801 802 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 803 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 804 __str_find_first_not_of(const _CharT *__p, _SizeT __sz, 805 _CharT __c, _SizeT __pos) _NOEXCEPT 806 { 807 if (__pos < __sz) 808 { 809 const _CharT* __pe = __p + __sz; 810 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) 811 if (!_Traits::eq(*__ps, __c)) 812 return static_cast<_SizeT>(__ps - __p); 813 } 814 return __npos; 815 } 816 817 818 // __str_find_last_not_of 819 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 820 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 821 __str_find_last_not_of(const _CharT *__p, _SizeT __sz, 822 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 823 { 824 if (__pos < __sz) 825 ++__pos; 826 else 827 __pos = __sz; 828 for (const _CharT* __ps = __p + __pos; __ps != __p;) 829 if (_Traits::find(__s, __n, *--__ps) == 0) 830 return static_cast<_SizeT>(__ps - __p); 831 return __npos; 832 } 833 834 835 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 836 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 837 __str_find_last_not_of(const _CharT *__p, _SizeT __sz, 838 _CharT __c, _SizeT __pos) _NOEXCEPT 839 { 840 if (__pos < __sz) 841 ++__pos; 842 else 843 __pos = __sz; 844 for (const _CharT* __ps = __p + __pos; __ps != __p;) 845 if (!_Traits::eq(*--__ps, __c)) 846 return static_cast<_SizeT>(__ps - __p); 847 return __npos; 848 } 849 850 template<class _Ptr> 851 inline _LIBCPP_INLINE_VISIBILITY 852 size_t __do_string_hash(_Ptr __p, _Ptr __e) 853 { 854 typedef typename iterator_traits<_Ptr>::value_type value_type; 855 return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type)); 856 } 857 858 template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> > 859 struct __quoted_output_proxy 860 { 861 _Iter __first; 862 _Iter __last; 863 _CharT __delim; 864 _CharT __escape; 865 866 __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e) 867 : __first(__f), __last(__l), __delim(__d), __escape(__e) {} 868 // This would be a nice place for a string_ref 869 }; 870 871 _LIBCPP_END_NAMESPACE_STD 872 873 #endif // _LIBCPP___STRING 874
