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