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