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