Home | History | Annotate | Download | only in include 
      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 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_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
    878