include/__string

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