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