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