contrib/llvm-project/libcxx/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 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 355 size_t
 356 char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
 357 {
 358 #if __has_feature(cxx_constexpr_string_builtins)
 359     return __builtin_wcslen(__s);
 360 #elif _LIBCPP_STD_VER <= 14
 361     return wcslen(__s);
 362 #else
 363     size_t __len = 0;
 364     for (; !eq(*__s, char_type(0)); ++__s)
 365         ++__len;
 366     return __len;
 367 #endif
 368 }
 369
 370 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 371 const wchar_t*
 372 char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 373 {
 374     if (__n == 0)
 375         return nullptr;
 376 #if __has_feature(cxx_constexpr_string_builtins)
 377     return __builtin_wmemchr(__s, __a, __n);
 378 #elif _LIBCPP_STD_VER <= 14
 379     return wmemchr(__s, __a, __n);
 380 #else
 381     for (; __n; --__n)
 382     {
 383         if (eq(*__s, __a))
 384             return __s;
 385         ++__s;
 386     }
 387     return nullptr;
 388 #endif
 389 }
 390
 391
 392 #ifndef _LIBCPP_NO_HAS_CHAR8_T
 393
 394 template <>
 395 struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
 396 {
 397     typedef char8_t        char_type;
 398     typedef unsigned int   int_type;
 399     typedef streamoff      off_type;
 400     typedef u8streampos    pos_type;
 401     typedef mbstate_t      state_type;
 402
 403     static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
 404         {__c1 = __c2;}
 405     static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept
 406         {return __c1 == __c2;}
 407     static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept
 408         {return __c1 < __c2;}
 409
 410     static constexpr
 411     int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 412
 413     static constexpr
 414     size_t           length(const char_type* __s) _NOEXCEPT;
 415
 416     _LIBCPP_INLINE_VISIBILITY static constexpr
 417     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 418
 419     static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 420         {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}
 421
 422     static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 423        {
 424             _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 425             return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
 426        }
 427
 428     static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 429         {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);}
 430
 431     static inline constexpr int_type  not_eof(int_type __c) noexcept
 432         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 433     static inline constexpr char_type to_char_type(int_type __c) noexcept
 434         {return char_type(__c);}
 435     static inline constexpr int_type to_int_type(char_type __c) noexcept
 436         {return int_type(__c);}
 437     static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
 438         {return __c1 == __c2;}
 439     static inline constexpr int_type eof() noexcept
 440         {return int_type(EOF);}
 441 };
 442
 443 // TODO use '__builtin_strlen' if it ever supports char8_t ??
 444 inline constexpr
 445 size_t
 446 char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT
 447 {
 448     size_t __len = 0;
 449     for (; !eq(*__s, char_type(0)); ++__s)
 450         ++__len;
 451     return __len;
 452 }
 453
 454 inline constexpr
 455 int
 456 char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 457 {
 458 #if __has_feature(cxx_constexpr_string_builtins)
 459     return __builtin_memcmp(__s1, __s2, __n);
 460 #else
 461     for (; __n; --__n, ++__s1, ++__s2)
 462     {
 463         if (lt(*__s1, *__s2))
 464             return -1;
 465         if (lt(*__s2, *__s1))
 466             return 1;
 467     }
 468     return 0;
 469 #endif
 470 }
 471
 472 // TODO use '__builtin_char_memchr' if it ever supports char8_t ??
 473 inline constexpr
 474 const char8_t*
 475 char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 476 {
 477     for (; __n; --__n)
 478     {
 479         if (eq(*__s, __a))
 480             return __s;
 481         ++__s;
 482     }
 483     return 0;
 484 }
 485
 486 #endif // #_LIBCPP_NO_HAS_CHAR8_T
 487
 488 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
 489
 490 template <>
 491 struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
 492 {
 493     typedef char16_t       char_type;
 494     typedef uint_least16_t int_type;
 495     typedef streamoff      off_type;
 496     typedef u16streampos   pos_type;
 497     typedef mbstate_t      state_type;
 498
 499     static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 500     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 501     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 502         {return __c1 == __c2;}
 503     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 504         {return __c1 < __c2;}
 505
 506     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 507     int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 508     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 509     size_t           length(const char_type* __s) _NOEXCEPT;
 510     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 511     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 512     _LIBCPP_INLINE_VISIBILITY
 513     static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 514     _LIBCPP_INLINE_VISIBILITY
 515     static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 516     _LIBCPP_INLINE_VISIBILITY
 517     static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
 518
 519     static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 520         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 521     static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 522         {return char_type(__c);}
 523     static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 524         {return int_type(__c);}
 525     static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 526         {return __c1 == __c2;}
 527     static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 528         {return int_type(0xFFFF);}
 529 };
 530
 531 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 532 int
 533 char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 534 {
 535     for (; __n; --__n, ++__s1, ++__s2)
 536     {
 537         if (lt(*__s1, *__s2))
 538             return -1;
 539         if (lt(*__s2, *__s1))
 540             return 1;
 541     }
 542     return 0;
 543 }
 544
 545 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 546 size_t
 547 char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
 548 {
 549     size_t __len = 0;
 550     for (; !eq(*__s, char_type(0)); ++__s)
 551         ++__len;
 552     return __len;
 553 }
 554
 555 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 556 const char16_t*
 557 char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 558 {
 559     for (; __n; --__n)
 560     {
 561         if (eq(*__s, __a))
 562             return __s;
 563         ++__s;
 564     }
 565     return 0;
 566 }
 567
 568 inline
 569 char16_t*
 570 char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 571 {
 572     char_type* __r = __s1;
 573     if (__s1 < __s2)
 574     {
 575         for (; __n; --__n, ++__s1, ++__s2)
 576             assign(*__s1, *__s2);
 577     }
 578     else if (__s2 < __s1)
 579     {
 580         __s1 += __n;
 581         __s2 += __n;
 582         for (; __n; --__n)
 583             assign(*--__s1, *--__s2);
 584     }
 585     return __r;
 586 }
 587
 588 inline
 589 char16_t*
 590 char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 591 {
 592     _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 593     char_type* __r = __s1;
 594     for (; __n; --__n, ++__s1, ++__s2)
 595         assign(*__s1, *__s2);
 596     return __r;
 597 }
 598
 599 inline
 600 char16_t*
 601 char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 602 {
 603     char_type* __r = __s;
 604     for (; __n; --__n, ++__s)
 605         assign(*__s, __a);
 606     return __r;
 607 }
 608
 609 template <>
 610 struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
 611 {
 612     typedef char32_t       char_type;
 613     typedef uint_least32_t int_type;
 614     typedef streamoff      off_type;
 615     typedef u32streampos   pos_type;
 616     typedef mbstate_t      state_type;
 617
 618     static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 619     void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 620     static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 621         {return __c1 == __c2;}
 622     static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 623         {return __c1 < __c2;}
 624
 625     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 626     int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 627     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 628     size_t           length(const char_type* __s) _NOEXCEPT;
 629     _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 630     const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 631     _LIBCPP_INLINE_VISIBILITY
 632     static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 633     _LIBCPP_INLINE_VISIBILITY
 634     static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 635     _LIBCPP_INLINE_VISIBILITY
 636     static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
 637
 638     static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
 639         {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 640     static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 641         {return char_type(__c);}
 642     static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 643         {return int_type(__c);}
 644     static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 645         {return __c1 == __c2;}
 646     static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 647         {return int_type(0xFFFFFFFF);}
 648 };
 649
 650 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 651 int
 652 char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 653 {
 654     for (; __n; --__n, ++__s1, ++__s2)
 655     {
 656         if (lt(*__s1, *__s2))
 657             return -1;
 658         if (lt(*__s2, *__s1))
 659             return 1;
 660     }
 661     return 0;
 662 }
 663
 664 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 665 size_t
 666 char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
 667 {
 668     size_t __len = 0;
 669     for (; !eq(*__s, char_type(0)); ++__s)
 670         ++__len;
 671     return __len;
 672 }
 673
 674 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 675 const char32_t*
 676 char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
 677 {
 678     for (; __n; --__n)
 679     {
 680         if (eq(*__s, __a))
 681             return __s;
 682         ++__s;
 683     }
 684     return 0;
 685 }
 686
 687 inline
 688 char32_t*
 689 char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 690 {
 691     char_type* __r = __s1;
 692     if (__s1 < __s2)
 693     {
 694         for (; __n; --__n, ++__s1, ++__s2)
 695             assign(*__s1, *__s2);
 696     }
 697     else if (__s2 < __s1)
 698     {
 699         __s1 += __n;
 700         __s2 += __n;
 701         for (; __n; --__n)
 702             assign(*--__s1, *--__s2);
 703     }
 704     return __r;
 705 }
 706
 707 inline
 708 char32_t*
 709 char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 710 {
 711     _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 712     char_type* __r = __s1;
 713     for (; __n; --__n, ++__s1, ++__s2)
 714         assign(*__s1, *__s2);
 715     return __r;
 716 }
 717
 718 inline
 719 char32_t*
 720 char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 721 {
 722     char_type* __r = __s;
 723     for (; __n; --__n, ++__s)
 724         assign(*__s, __a);
 725     return __r;
 726 }
 727
 728 #endif  // _LIBCPP_HAS_NO_UNICODE_CHARS
 729
 730 // helper fns for basic_string and string_view
 731
 732 // __str_find
 733 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 734 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 735 __str_find(const _CharT *__p, _SizeT __sz,
 736              _CharT __c, _SizeT __pos) _NOEXCEPT
 737 {
 738     if (__pos >= __sz)
 739         return __npos;
 740     const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
 741     if (__r == 0)
 742         return __npos;
 743     return static_cast<_SizeT>(__r - __p);
 744 }
 745
 746 template <class _CharT, class _Traits>
 747 inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
 748 __search_substring(const _CharT *__first1, const _CharT *__last1,
 749                    const _CharT *__first2, const _CharT *__last2) {
 750   // Take advantage of knowing source and pattern lengths.
 751   // Stop short when source is smaller than pattern.
 752   const ptrdiff_t __len2 = __last2 - __first2;
 753   if (__len2 == 0)
 754     return __first1;
 755
 756   ptrdiff_t __len1 = __last1 - __first1;
 757   if (__len1 < __len2)
 758     return __last1;
 759
 760   // First element of __first2 is loop invariant.
 761   _CharT __f2 = *__first2;
 762   while (true) {
 763     __len1 = __last1 - __first1;
 764     // Check whether __first1 still has at least __len2 bytes.
 765     if (__len1 < __len2)
 766       return __last1;
 767
 768     // Find __f2 the first byte matching in __first1.
 769     __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
 770     if (__first1 == 0)
 771       return __last1;
 772
 773     // It is faster to compare from the first byte of __first1 even if we
 774     // already know that it matches the first byte of __first2: this is because
 775     // __first2 is most likely aligned, as it is user's "pattern" string, and
 776     // __first1 + 1 is most likely not aligned, as the match is in the middle of
 777     // the string.
 778     if (_Traits::compare(__first1, __first2, __len2) == 0)
 779       return __first1;
 780
 781     ++__first1;
 782   }
 783 }
 784
 785 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 786 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 787 __str_find(const _CharT *__p, _SizeT __sz,
 788        const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 789 {
 790     if (__pos > __sz)
 791         return __npos;
 792
 793     if (__n == 0) // There is nothing to search, just return __pos.
 794         return __pos;
 795
 796     const _CharT *__r = __search_substring<_CharT, _Traits>(
 797         __p + __pos, __p + __sz, __s, __s + __n);
 798
 799     if (__r == __p + __sz)
 800         return __npos;
 801     return static_cast<_SizeT>(__r - __p);
 802 }
 803
 804
 805 // __str_rfind
 806
 807 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 808 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 809 __str_rfind(const _CharT *__p, _SizeT __sz,
 810               _CharT __c, _SizeT __pos) _NOEXCEPT
 811 {
 812     if (__sz < 1)
 813         return __npos;
 814     if (__pos < __sz)
 815         ++__pos;
 816     else
 817         __pos = __sz;
 818     for (const _CharT* __ps = __p + __pos; __ps != __p;)
 819     {
 820         if (_Traits::eq(*--__ps, __c))
 821             return static_cast<_SizeT>(__ps - __p);
 822     }
 823     return __npos;
 824 }
 825
 826 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 827 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 828 __str_rfind(const _CharT *__p, _SizeT __sz,
 829         const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 830 {
 831     __pos = _VSTD::min(__pos, __sz);
 832     if (__n < __sz - __pos)
 833         __pos += __n;
 834     else
 835         __pos = __sz;
 836     const _CharT* __r = _VSTD::__find_end(
 837                   __p, __p + __pos, __s, __s + __n, _Traits::eq,
 838                         random_access_iterator_tag(), random_access_iterator_tag());
 839     if (__n > 0 && __r == __p + __pos)
 840         return __npos;
 841     return static_cast<_SizeT>(__r - __p);
 842 }
 843
 844 // __str_find_first_of
 845 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 846 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 847 __str_find_first_of(const _CharT *__p, _SizeT __sz,
 848                 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 849 {
 850     if (__pos >= __sz || __n == 0)
 851         return __npos;
 852     const _CharT* __r = _VSTD::__find_first_of_ce
 853         (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
 854     if (__r == __p + __sz)
 855         return __npos;
 856     return static_cast<_SizeT>(__r - __p);
 857 }
 858
 859
 860 // __str_find_last_of
 861 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 862 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 863 __str_find_last_of(const _CharT *__p, _SizeT __sz,
 864                const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 865     {
 866     if (__n != 0)
 867     {
 868         if (__pos < __sz)
 869             ++__pos;
 870         else
 871             __pos = __sz;
 872         for (const _CharT* __ps = __p + __pos; __ps != __p;)
 873         {
 874             const _CharT* __r = _Traits::find(__s, __n, *--__ps);
 875             if (__r)
 876                 return static_cast<_SizeT>(__ps - __p);
 877         }
 878     }
 879     return __npos;
 880 }
 881
 882
 883 // __str_find_first_not_of
 884 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 885 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 886 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
 887                     const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 888 {
 889     if (__pos < __sz)
 890     {
 891         const _CharT* __pe = __p + __sz;
 892         for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
 893             if (_Traits::find(__s, __n, *__ps) == 0)
 894                 return static_cast<_SizeT>(__ps - __p);
 895     }
 896     return __npos;
 897 }
 898
 899
 900 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 901 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 902 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
 903                           _CharT __c, _SizeT __pos) _NOEXCEPT
 904 {
 905     if (__pos < __sz)
 906     {
 907         const _CharT* __pe = __p + __sz;
 908         for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
 909             if (!_Traits::eq(*__ps, __c))
 910                 return static_cast<_SizeT>(__ps - __p);
 911     }
 912     return __npos;
 913 }
 914
 915
 916 // __str_find_last_not_of
 917 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 918 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 919 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
 920                    const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 921 {
 922     if (__pos < __sz)
 923         ++__pos;
 924     else
 925         __pos = __sz;
 926     for (const _CharT* __ps = __p + __pos; __ps != __p;)
 927         if (_Traits::find(__s, __n, *--__ps) == 0)
 928             return static_cast<_SizeT>(__ps - __p);
 929     return __npos;
 930 }
 931
 932
 933 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 934 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 935 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
 936                          _CharT __c, _SizeT __pos) _NOEXCEPT
 937 {
 938     if (__pos < __sz)
 939         ++__pos;
 940     else
 941         __pos = __sz;
 942     for (const _CharT* __ps = __p + __pos; __ps != __p;)
 943         if (!_Traits::eq(*--__ps, __c))
 944             return static_cast<_SizeT>(__ps - __p);
 945     return __npos;
 946 }
 947
 948 template<class _Ptr>
 949 inline _LIBCPP_INLINE_VISIBILITY
 950 size_t __do_string_hash(_Ptr __p, _Ptr __e)
 951 {
 952     typedef typename iterator_traits<_Ptr>::value_type value_type;
 953     return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
 954 }
 955
 956 template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
 957 struct __quoted_output_proxy
 958 {
 959     _Iter  __first;
 960     _Iter  __last;
 961     _CharT  __delim;
 962     _CharT  __escape;
 963
 964     __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
 965     : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
 966     //  This would be a nice place for a string_ref
 967 };
 968
 969 _LIBCPP_END_NAMESPACE_STD
 970
 971 _LIBCPP_POP_MACROS
 972
 973 #endif  // _LIBCPP___STRING