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