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