libcxx/include/__string/char_traits.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___STRING_CHAR_TRAITS_H
  10 #define _LIBCPP___STRING_CHAR_TRAITS_H
  11
  12 #include <__algorithm/fill_n.h>
  13 #include <__algorithm/find.h>
  14 #include <__algorithm/find_end.h>
  15 #include <__algorithm/find_first_of.h>
  16 #include <__algorithm/min.h>
  17 #include <__assert>
  18 #include <__compare/ordering.h>
  19 #include <__config>
  20 #include <__cstddef/ptrdiff_t.h>
  21 #include <__functional/hash.h>
  22 #include <__functional/identity.h>
  23 #include <__iterator/iterator_traits.h>
  24 #include <__std_mbstate_t.h>
  25 #include <__string/constexpr_c_functions.h>
  26 #include <__type_traits/is_constant_evaluated.h>
  27 #include <__utility/is_pointer_in_range.h>
  28 #include <cstdint>
  29 #include <cstdio>
  30 #include <iosfwd>
  31
  32 #if _LIBCPP_HAS_WIDE_CHARACTERS
  33 #  include <cwchar> // for wmemcpy
  34 #endif
  35
  36 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  37 #  pragma GCC system_header
  38 #endif
  39
  40 _LIBCPP_PUSH_MACROS
  41 #include <__undef_macros>
  42
  43 _LIBCPP_BEGIN_NAMESPACE_STD
  44
  45 template <class _CharT>
  46 struct char_traits;
  47 /*
  48 The Standard does not define the base template for char_traits because it is impossible to provide
  49 a correct definition for arbitrary character types. Instead, it requires implementations to provide
  50 specializations for predefined character types like `char`, `wchar_t` and others. We provide this as
  51 exposition-only to document what members a char_traits specialization should provide:
  52 {
  53     using char_type  = _CharT;
  54     using int_type   = ...;
  55     using off_type   = ...;
  56     using pos_type   = ...;
  57     using state_type = ...;
  58
  59     static void assign(char_type&, const char_type&);
  60     static bool eq(char_type, char_type);
  61     static bool lt(char_type, char_type);
  62
  63     static int              compare(const char_type*, const char_type*, size_t);
  64     static size_t           length(const char_type*);
  65     static const char_type* find(const char_type*, size_t, const char_type&);
  66     static char_type*       move(char_type*, const char_type*, size_t);
  67     static char_type*       copy(char_type*, const char_type*, size_t);
  68     static char_type*       assign(char_type*, size_t, char_type);
  69
  70     static int_type  not_eof(int_type);
  71     static char_type to_char_type(int_type);
  72     static int_type  to_int_type(char_type);
  73     static bool      eq_int_type(int_type, int_type);
  74     static int_type  eof();
  75 };
  76 */
  77
  78 // char_traits<char>
  79
  80 template <>
  81 struct _LIBCPP_TEMPLATE_VIS char_traits<char> {
  82   using char_type  = char;
  83   using int_type   = int;
  84   using off_type   = streamoff;
  85   using pos_type   = streampos;
  86   using state_type = mbstate_t;
  87 #if _LIBCPP_STD_VER >= 20
  88   using comparison_category = strong_ordering;
  89 #endif
  90
  91   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void
  92   assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {
  93     __c1 = __c2;
  94   }
  95
  96   // TODO: Make this _LIBCPP_HIDE_FROM_ABI
  97   static inline _LIBCPP_HIDDEN _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT {
  98     return __c1 == __c2;
  99   }
 100   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT {
 101     return (unsigned char)__c1 < (unsigned char)__c2;
 102   }
 103
 104   // __constexpr_memcmp requires a trivially lexicographically comparable type, but char is not when char is a signed
 105   // type
 106   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int
 107   compare(const char_type* __lhs, const char_type* __rhs, size_t __count) _NOEXCEPT {
 108     if (__libcpp_is_constant_evaluated()) {
 109 #ifdef _LIBCPP_COMPILER_CLANG_BASED
 110       return __builtin_memcmp(__lhs, __rhs, __count);
 111 #else
 112       while (__count != 0) {
 113         if (lt(*__lhs, *__rhs))
 114           return -1;
 115         if (lt(*__rhs, *__lhs))
 116           return 1;
 117
 118         __count -= sizeof(char_type);
 119         ++__lhs;
 120         ++__rhs;
 121       }
 122       return 0;
 123 #endif // _LIBCPP_COMPILER_CLANG_BASED
 124     } else {
 125       return __builtin_memcmp(__lhs, __rhs, __count);
 126     }
 127   }
 128
 129   static inline _LIBCPP_HIDE_FROM_ABI size_t _LIBCPP_CONSTEXPR_SINCE_CXX17 length(const char_type* __s) _NOEXCEPT {
 130     return std::__constexpr_strlen(__s);
 131   }
 132
 133   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type*
 134   find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
 135     if (__n == 0)
 136       return nullptr;
 137     return std::__constexpr_memchr(__s, __a, __n);
 138   }
 139
 140   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
 141   move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 142     return std::__constexpr_memmove(__s1, __s2, __element_count(__n));
 143   }
 144
 145   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
 146   copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 147     _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__s1, __s1 + __n, __s2),
 148                                           "char_traits::copy: source and destination ranges overlap");
 149     std::__constexpr_memmove(__s1, __s2, __element_count(__n));
 150     return __s1;
 151   }
 152
 153   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
 154   assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT {
 155     std::fill_n(__s, __n, __a);
 156     return __s;
 157   }
 158
 159   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT {
 160     return eq_int_type(__c, eof()) ? ~eof() : __c;
 161   }
 162   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT {
 163     return char_type(__c);
 164   }
 165   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT {
 166     return int_type((unsigned char)__c);
 167   }
 168   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT {
 169     return __c1 == __c2;
 170   }
 171   static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT { return int_type(EOF); }
 172 };
 173
 174 template <class _CharT, class _IntT, _IntT _EOFVal>
 175 struct __char_traits_base {
 176   using char_type  = _CharT;
 177   using int_type   = _IntT;
 178   using off_type   = streamoff;
 179   using state_type = mbstate_t;
 180 #if _LIBCPP_STD_VER >= 20
 181   using comparison_category = strong_ordering;
 182 #endif
 183
 184   // There are different aliases for the different char types, but they are all aliases to this type
 185   using pos_type = fpos<mbstate_t>;
 186
 187   _LIBCPP_HIDE_FROM_ABI static inline _LIBCPP_CONSTEXPR_SINCE_CXX17 void
 188   assign(char_type& __lhs, const char_type& __rhs) _NOEXCEPT {
 189     __lhs = __rhs;
 190   }
 191
 192   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool eq(char_type __lhs, char_type __rhs) _NOEXCEPT {
 193     return __lhs == __rhs;
 194   }
 195
 196   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool lt(char_type __lhs, char_type __rhs) _NOEXCEPT {
 197     return __lhs < __rhs;
 198   }
 199
 200   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
 201   move(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT {
 202     return std::__constexpr_memmove(__dest, __src, __element_count(__n));
 203   }
 204
 205   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
 206   copy(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT {
 207     _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__dest, __dest + __n, __src),
 208                                           "char_traits::copy: source and destination ranges overlap");
 209     return std::__constexpr_memmove(__dest, __src, __element_count(__n));
 210   }
 211
 212   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
 213   assign(char_type* __str, size_t __n, char_type __fill_char) _NOEXCEPT {
 214     std::fill_n(__str, __n, __fill_char);
 215     return __str;
 216   }
 217
 218   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT {
 219     return char_type(__c);
 220   }
 221
 222   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT { return int_type(__c); }
 223
 224   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool eq_int_type(int_type __lhs, int_type __rhs) _NOEXCEPT {
 225     return __lhs == __rhs;
 226   }
 227
 228   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT { return _EOFVal; }
 229
 230   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT {
 231     return eq_int_type(__c, eof()) ? static_cast<int_type>(~eof()) : __c;
 232   }
 233 };
 234
 235 // char_traits<wchar_t>
 236
 237 #if _LIBCPP_HAS_WIDE_CHARACTERS
 238 template <>
 239 struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t> : __char_traits_base<wchar_t, wint_t, static_cast<wint_t>(WEOF)> {
 240   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int
 241   compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 242     if (__n == 0)
 243       return 0;
 244     return std::__constexpr_wmemcmp(__s1, __s2, __n);
 245   }
 246
 247   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT {
 248     return std::__constexpr_wcslen(__s);
 249   }
 250
 251   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type*
 252   find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
 253     if (__n == 0)
 254       return nullptr;
 255     return std::__constexpr_wmemchr(__s, __a, __n);
 256   }
 257 };
 258 #endif // _LIBCPP_HAS_WIDE_CHARACTERS
 259
 260 #if _LIBCPP_HAS_CHAR8_T
 261
 262 template <>
 263 struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
 264     : __char_traits_base<char8_t, unsigned int, static_cast<unsigned int>(EOF)> {
 265   static _LIBCPP_HIDE_FROM_ABI constexpr int
 266   compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept {
 267     return std::__constexpr_memcmp(__s1, __s2, __element_count(__n));
 268   }
 269
 270   static _LIBCPP_HIDE_FROM_ABI constexpr size_t length(const char_type* __str) noexcept {
 271     return std::__constexpr_strlen(__str);
 272   }
 273
 274   _LIBCPP_HIDE_FROM_ABI static constexpr const char_type*
 275   find(const char_type* __s, size_t __n, const char_type& __a) noexcept {
 276     return std::__constexpr_memchr(__s, __a, __n);
 277   }
 278 };
 279
 280 #endif // _LIBCPP_HAS_CHAR8_T
 281
 282 template <>
 283 struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
 284     : __char_traits_base<char16_t, uint_least16_t, static_cast<uint_least16_t>(0xFFFF)> {
 285   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 int
 286   compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 287   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT;
 288
 289   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type*
 290   find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
 291     __identity __proj;
 292     const char_type* __match = std::__find(__s, __s + __n, __a, __proj);
 293     if (__match == __s + __n)
 294       return nullptr;
 295     return __match;
 296   }
 297 };
 298
 299 inline _LIBCPP_CONSTEXPR_SINCE_CXX17 int
 300 char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 301   for (; __n; --__n, ++__s1, ++__s2) {
 302     if (lt(*__s1, *__s2))
 303       return -1;
 304     if (lt(*__s2, *__s1))
 305       return 1;
 306   }
 307   return 0;
 308 }
 309
 310 inline _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT {
 311   size_t __len = 0;
 312   for (; !eq(*__s, char_type(0)); ++__s)
 313     ++__len;
 314   return __len;
 315 }
 316
 317 template <>
 318 struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
 319     : __char_traits_base<char32_t, uint_least32_t, static_cast<uint_least32_t>(0xFFFFFFFF)> {
 320   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 int
 321   compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 322   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT;
 323
 324   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type*
 325   find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
 326     __identity __proj;
 327     const char_type* __match = std::__find(__s, __s + __n, __a, __proj);
 328     if (__match == __s + __n)
 329       return nullptr;
 330     return __match;
 331   }
 332 };
 333
 334 inline _LIBCPP_CONSTEXPR_SINCE_CXX17 int
 335 char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
 336   for (; __n; --__n, ++__s1, ++__s2) {
 337     if (lt(*__s1, *__s2))
 338       return -1;
 339     if (lt(*__s2, *__s1))
 340       return 1;
 341   }
 342   return 0;
 343 }
 344
 345 inline _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT {
 346   size_t __len = 0;
 347   for (; !eq(*__s, char_type(0)); ++__s)
 348     ++__len;
 349   return __len;
 350 }
 351
 352 // helper fns for basic_string and string_view
 353
 354 // __str_find
 355 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 356 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 357 __str_find(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
 358   if (__pos >= __sz)
 359     return __npos;
 360   const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
 361   if (__r == nullptr)
 362     return __npos;
 363   return static_cast<_SizeT>(__r - __p);
 364 }
 365
 366 template <class _CharT, class _Traits>
 367 _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX14 const _CharT* __search_substring(
 368     const _CharT* __first1, const _CharT* __last1, const _CharT* __first2, const _CharT* __last2) _NOEXCEPT {
 369   // Take advantage of knowing source and pattern lengths.
 370   // Stop short when source is smaller than pattern.
 371   const ptrdiff_t __len2 = __last2 - __first2;
 372   if (__len2 == 0)
 373     return __first1;
 374
 375   ptrdiff_t __len1 = __last1 - __first1;
 376   if (__len1 < __len2)
 377     return __last1;
 378
 379   // First element of __first2 is loop invariant.
 380   _CharT __f2 = *__first2;
 381   while (true) {
 382     __len1 = __last1 - __first1;
 383     // Check whether __first1 still has at least __len2 bytes.
 384     if (__len1 < __len2)
 385       return __last1;
 386
 387     // Find __f2 the first byte matching in __first1.
 388     __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
 389     if (__first1 == nullptr)
 390       return __last1;
 391
 392     // It is faster to compare from the first byte of __first1 even if we
 393     // already know that it matches the first byte of __first2: this is because
 394     // __first2 is most likely aligned, as it is user's "pattern" string, and
 395     // __first1 + 1 is most likely not aligned, as the match is in the middle of
 396     // the string.
 397     if (_Traits::compare(__first1, __first2, __len2) == 0)
 398       return __first1;
 399
 400     ++__first1;
 401   }
 402 }
 403
 404 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 405 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 406 __str_find(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
 407   if (__pos > __sz)
 408     return __npos;
 409
 410   if (__n == 0) // There is nothing to search, just return __pos.
 411     return __pos;
 412
 413   const _CharT* __r = std::__search_substring<_CharT, _Traits>(__p + __pos, __p + __sz, __s, __s + __n);
 414
 415   if (__r == __p + __sz)
 416     return __npos;
 417   return static_cast<_SizeT>(__r - __p);
 418 }
 419
 420 // __str_rfind
 421
 422 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 423 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 424 __str_rfind(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
 425   if (__sz < 1)
 426     return __npos;
 427   if (__pos < __sz)
 428     ++__pos;
 429   else
 430     __pos = __sz;
 431   for (const _CharT* __ps = __p + __pos; __ps != __p;) {
 432     if (_Traits::eq(*--__ps, __c))
 433       return static_cast<_SizeT>(__ps - __p);
 434   }
 435   return __npos;
 436 }
 437
 438 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 439 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 440 __str_rfind(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
 441   __pos = std::min(__pos, __sz);
 442   if (__n < __sz - __pos)
 443     __pos += __n;
 444   else
 445     __pos = __sz;
 446   const _CharT* __r = std::__find_end_classic(__p, __p + __pos, __s, __s + __n, _Traits::eq);
 447   if (__n > 0 && __r == __p + __pos)
 448     return __npos;
 449   return static_cast<_SizeT>(__r - __p);
 450 }
 451
 452 // __str_find_first_of
 453 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 454 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 455 __str_find_first_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
 456   if (__pos >= __sz || __n == 0)
 457     return __npos;
 458   const _CharT* __r = std::__find_first_of_ce(__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq);
 459   if (__r == __p + __sz)
 460     return __npos;
 461   return static_cast<_SizeT>(__r - __p);
 462 }
 463
 464 // __str_find_last_of
 465 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 466 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 467 __str_find_last_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
 468   if (__n != 0) {
 469     if (__pos < __sz)
 470       ++__pos;
 471     else
 472       __pos = __sz;
 473     for (const _CharT* __ps = __p + __pos; __ps != __p;) {
 474       const _CharT* __r = _Traits::find(__s, __n, *--__ps);
 475       if (__r)
 476         return static_cast<_SizeT>(__ps - __p);
 477     }
 478   }
 479   return __npos;
 480 }
 481
 482 // __str_find_first_not_of
 483 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 484 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 485 __str_find_first_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
 486   if (__pos < __sz) {
 487     const _CharT* __pe = __p + __sz;
 488     for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
 489       if (_Traits::find(__s, __n, *__ps) == nullptr)
 490         return static_cast<_SizeT>(__ps - __p);
 491   }
 492   return __npos;
 493 }
 494
 495 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 496 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 497 __str_find_first_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
 498   if (__pos < __sz) {
 499     const _CharT* __pe = __p + __sz;
 500     for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
 501       if (!_Traits::eq(*__ps, __c))
 502         return static_cast<_SizeT>(__ps - __p);
 503   }
 504   return __npos;
 505 }
 506
 507 // __str_find_last_not_of
 508 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 509 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 510 __str_find_last_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
 511   if (__pos < __sz)
 512     ++__pos;
 513   else
 514     __pos = __sz;
 515   for (const _CharT* __ps = __p + __pos; __ps != __p;)
 516     if (_Traits::find(__s, __n, *--__ps) == nullptr)
 517       return static_cast<_SizeT>(__ps - __p);
 518   return __npos;
 519 }
 520
 521 template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 522 inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
 523 __str_find_last_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
 524   if (__pos < __sz)
 525     ++__pos;
 526   else
 527     __pos = __sz;
 528   for (const _CharT* __ps = __p + __pos; __ps != __p;)
 529     if (!_Traits::eq(*--__ps, __c))
 530       return static_cast<_SizeT>(__ps - __p);
 531   return __npos;
 532 }
 533
 534 template <class _Ptr>
 535 inline _LIBCPP_HIDE_FROM_ABI size_t __do_string_hash(_Ptr __p, _Ptr __e) {
 536   typedef typename iterator_traits<_Ptr>::value_type value_type;
 537   return __murmur2_or_cityhash<size_t>()(__p, (__e - __p) * sizeof(value_type));
 538 }
 539
 540 _LIBCPP_END_NAMESPACE_STD
 541
 542 _LIBCPP_POP_MACROS
 543
 544 #endif // _LIBCPP___STRING_CHAR_TRAITS_H