contrib/libc++/include/__string

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