2 //===-------------------------- __string ----------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is distributed under the University of Illinois Open Source
7 // License. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP___STRING
12 #define _LIBCPP___STRING
20 template <class charT>
23 typedef charT char_type;
25 typedef streamoff off_type;
26 typedef streampos pos_type;
27 typedef mbstate_t state_type;
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;
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);
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;
48 template <> struct char_traits<char>;
49 template <> struct char_traits<wchar_t>;
56 #include <algorithm> // for search and min
57 #include <cstdio> // For EOF.
58 #include <memory> // for __murmur2_or_cityhash
62 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
63 #pragma GCC system_header
67 #include <__undef_macros>
70 _LIBCPP_BEGIN_NAMESPACE_STD
74 template <class _CharT>
75 struct _LIBCPP_TEMPLATE_VIS char_traits
77 typedef _CharT char_type;
79 typedef streamoff off_type;
80 typedef streampos pos_type;
81 typedef mbstate_t state_type;
83 static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14
84 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
85 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
86 {return __c1 == __c2;}
87 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
90 static _LIBCPP_CONSTEXPR_AFTER_CXX14
91 int compare(const char_type* __s1, const char_type* __s2, size_t __n);
92 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
93 size_t length(const char_type* __s);
94 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
95 const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
96 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n);
97 _LIBCPP_INLINE_VISIBILITY
98 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n);
99 _LIBCPP_INLINE_VISIBILITY
100 static char_type* assign(char_type* __s, size_t __n, char_type __a);
102 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
103 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
104 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
105 {return char_type(__c);}
106 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
107 {return int_type(__c);}
108 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
109 {return __c1 == __c2;}
110 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
111 {return int_type(EOF);}
114 template <class _CharT>
115 _LIBCPP_CONSTEXPR_AFTER_CXX14 int
116 char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
118 for (; __n; --__n, ++__s1, ++__s2)
120 if (lt(*__s1, *__s2))
122 if (lt(*__s2, *__s1))
128 template <class _CharT>
130 _LIBCPP_CONSTEXPR_AFTER_CXX14 size_t
131 char_traits<_CharT>::length(const char_type* __s)
134 for (; !eq(*__s, char_type(0)); ++__s)
139 template <class _CharT>
141 _LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT*
142 char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
153 template <class _CharT>
155 char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
157 char_type* __r = __s1;
160 for (; __n; --__n, ++__s1, ++__s2)
161 assign(*__s1, *__s2);
163 else if (__s2 < __s1)
168 assign(*--__s1, *--__s2);
173 template <class _CharT>
176 char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
178 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
179 char_type* __r = __s1;
180 for (; __n; --__n, ++__s1, ++__s2)
181 assign(*__s1, *__s2);
185 template <class _CharT>
188 char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
190 char_type* __r = __s;
191 for (; __n; --__n, ++__s)
199 struct _LIBCPP_TEMPLATE_VIS char_traits<char>
201 typedef char char_type;
202 typedef int int_type;
203 typedef streamoff off_type;
204 typedef streampos pos_type;
205 typedef mbstate_t state_type;
207 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
208 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
209 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
210 {return __c1 == __c2;}
211 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
212 {return (unsigned char)__c1 < (unsigned char)__c2;}
214 static _LIBCPP_CONSTEXPR_AFTER_CXX14
215 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
216 static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14
217 length(const char_type* __s) _NOEXCEPT {return __builtin_strlen(__s);}
218 static _LIBCPP_CONSTEXPR_AFTER_CXX14
219 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
220 static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
221 {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}
222 static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
224 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
225 return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
227 static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
228 {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);}
230 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
231 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
232 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
233 {return char_type(__c);}
234 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
235 {return int_type((unsigned char)__c);}
236 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
237 {return __c1 == __c2;}
238 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
239 {return int_type(EOF);}
242 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
244 char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
248 #if __has_feature(cxx_constexpr_string_builtins)
249 return __builtin_memcmp(__s1, __s2, __n);
250 #elif _LIBCPP_STD_VER <= 14
251 return memcmp(__s1, __s2, __n);
253 for (; __n; --__n, ++__s1, ++__s2)
255 if (lt(*__s1, *__s2))
257 if (lt(*__s2, *__s1))
264 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
266 char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
270 #if __has_feature(cxx_constexpr_string_builtins)
271 return __builtin_char_memchr(__s, to_int_type(__a), __n);
272 #elif _LIBCPP_STD_VER <= 14
273 return (const char_type*) memchr(__s, to_int_type(__a), __n);
286 // char_traits<wchar_t>
289 struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
291 typedef wchar_t char_type;
292 typedef wint_t int_type;
293 typedef streamoff off_type;
294 typedef streampos pos_type;
295 typedef mbstate_t state_type;
297 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
298 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
299 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
300 {return __c1 == __c2;}
301 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
302 {return __c1 < __c2;}
304 static _LIBCPP_CONSTEXPR_AFTER_CXX14
305 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
306 static _LIBCPP_CONSTEXPR_AFTER_CXX14
307 size_t length(const char_type* __s) _NOEXCEPT;
308 static _LIBCPP_CONSTEXPR_AFTER_CXX14
309 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
310 static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
311 {return __n == 0 ? __s1 : (char_type*)wmemmove(__s1, __s2, __n);}
312 static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
314 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
315 return __n == 0 ? __s1 : (char_type*)wmemcpy(__s1, __s2, __n);
317 static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
318 {return __n == 0 ? __s : (char_type*)wmemset(__s, __a, __n);}
320 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
321 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
322 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
323 {return char_type(__c);}
324 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
325 {return int_type(__c);}
326 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
327 {return __c1 == __c2;}
328 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
329 {return int_type(WEOF);}
332 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
334 char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
338 #if __has_feature(cxx_constexpr_string_builtins)
339 return __builtin_wmemcmp(__s1, __s2, __n);
340 #elif _LIBCPP_STD_VER <= 14
341 return wmemcmp(__s1, __s2, __n);
343 for (; __n; --__n, ++__s1, ++__s2)
345 if (lt(*__s1, *__s2))
347 if (lt(*__s2, *__s1))
354 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
356 char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
358 #if __has_feature(cxx_constexpr_string_builtins)
359 return __builtin_wcslen(__s);
360 #elif _LIBCPP_STD_VER <= 14
364 for (; !eq(*__s, char_type(0)); ++__s)
370 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
372 char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
376 #if __has_feature(cxx_constexpr_string_builtins)
377 return __builtin_wmemchr(__s, __a, __n);
378 #elif _LIBCPP_STD_VER <= 14
379 return wmemchr(__s, __a, __n);
392 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
395 struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
397 typedef char16_t char_type;
398 typedef uint_least16_t int_type;
399 typedef streamoff off_type;
400 typedef u16streampos pos_type;
401 typedef mbstate_t state_type;
403 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
404 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
405 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
406 {return __c1 == __c2;}
407 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
408 {return __c1 < __c2;}
410 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
411 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
412 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
413 size_t length(const char_type* __s) _NOEXCEPT;
414 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
415 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
416 _LIBCPP_INLINE_VISIBILITY
417 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
418 _LIBCPP_INLINE_VISIBILITY
419 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
420 _LIBCPP_INLINE_VISIBILITY
421 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
423 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
424 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
425 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
426 {return char_type(__c);}
427 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
428 {return int_type(__c);}
429 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
430 {return __c1 == __c2;}
431 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
432 {return int_type(0xFFFF);}
435 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
437 char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
439 for (; __n; --__n, ++__s1, ++__s2)
441 if (lt(*__s1, *__s2))
443 if (lt(*__s2, *__s1))
449 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
451 char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
454 for (; !eq(*__s, char_type(0)); ++__s)
459 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
461 char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
474 char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
476 char_type* __r = __s1;
479 for (; __n; --__n, ++__s1, ++__s2)
480 assign(*__s1, *__s2);
482 else if (__s2 < __s1)
487 assign(*--__s1, *--__s2);
494 char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
496 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
497 char_type* __r = __s1;
498 for (; __n; --__n, ++__s1, ++__s2)
499 assign(*__s1, *__s2);
505 char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
507 char_type* __r = __s;
508 for (; __n; --__n, ++__s)
514 struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
516 typedef char32_t char_type;
517 typedef uint_least32_t int_type;
518 typedef streamoff off_type;
519 typedef u32streampos pos_type;
520 typedef mbstate_t state_type;
522 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
523 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
524 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
525 {return __c1 == __c2;}
526 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
527 {return __c1 < __c2;}
529 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
530 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
531 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
532 size_t length(const char_type* __s) _NOEXCEPT;
533 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
534 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
535 _LIBCPP_INLINE_VISIBILITY
536 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
537 _LIBCPP_INLINE_VISIBILITY
538 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
539 _LIBCPP_INLINE_VISIBILITY
540 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
542 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
543 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
544 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
545 {return char_type(__c);}
546 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
547 {return int_type(__c);}
548 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
549 {return __c1 == __c2;}
550 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
551 {return int_type(0xFFFFFFFF);}
554 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
556 char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
558 for (; __n; --__n, ++__s1, ++__s2)
560 if (lt(*__s1, *__s2))
562 if (lt(*__s2, *__s1))
568 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
570 char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
573 for (; !eq(*__s, char_type(0)); ++__s)
578 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
580 char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
593 char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
595 char_type* __r = __s1;
598 for (; __n; --__n, ++__s1, ++__s2)
599 assign(*__s1, *__s2);
601 else if (__s2 < __s1)
606 assign(*--__s1, *--__s2);
613 char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
615 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
616 char_type* __r = __s1;
617 for (; __n; --__n, ++__s1, ++__s2)
618 assign(*__s1, *__s2);
624 char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
626 char_type* __r = __s;
627 for (; __n; --__n, ++__s)
632 #endif // _LIBCPP_HAS_NO_UNICODE_CHARS
634 // helper fns for basic_string and string_view
637 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
638 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
639 __str_find(const _CharT *__p, _SizeT __sz,
640 _CharT __c, _SizeT __pos) _NOEXCEPT
644 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
647 return static_cast<_SizeT>(__r - __p);
650 template <class _CharT, class _Traits>
651 inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
652 __search_substring(const _CharT *__first1, const _CharT *__last1,
653 const _CharT *__first2, const _CharT *__last2) {
654 // Take advantage of knowing source and pattern lengths.
655 // Stop short when source is smaller than pattern.
656 const ptrdiff_t __len2 = __last2 - __first2;
660 ptrdiff_t __len1 = __last1 - __first1;
664 // First element of __first2 is loop invariant.
665 _CharT __f2 = *__first2;
667 __len1 = __last1 - __first1;
668 // Check whether __first1 still has at least __len2 bytes.
672 // Find __f2 the first byte matching in __first1.
673 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
677 // It is faster to compare from the first byte of __first1 even if we
678 // already know that it matches the first byte of __first2: this is because
679 // __first2 is most likely aligned, as it is user's "pattern" string, and
680 // __first1 + 1 is most likely not aligned, as the match is in the middle of
682 if (_Traits::compare(__first1, __first2, __len2) == 0)
689 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
690 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
691 __str_find(const _CharT *__p, _SizeT __sz,
692 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
697 if (__n == 0) // There is nothing to search, just return __pos.
700 const _CharT *__r = __search_substring<_CharT, _Traits>(
701 __p + __pos, __p + __sz, __s, __s + __n);
703 if (__r == __p + __sz)
705 return static_cast<_SizeT>(__r - __p);
711 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
712 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
713 __str_rfind(const _CharT *__p, _SizeT __sz,
714 _CharT __c, _SizeT __pos) _NOEXCEPT
722 for (const _CharT* __ps = __p + __pos; __ps != __p;)
724 if (_Traits::eq(*--__ps, __c))
725 return static_cast<_SizeT>(__ps - __p);
730 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
731 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
732 __str_rfind(const _CharT *__p, _SizeT __sz,
733 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
735 __pos = _VSTD::min(__pos, __sz);
736 if (__n < __sz - __pos)
740 const _CharT* __r = _VSTD::__find_end(
741 __p, __p + __pos, __s, __s + __n, _Traits::eq,
742 random_access_iterator_tag(), random_access_iterator_tag());
743 if (__n > 0 && __r == __p + __pos)
745 return static_cast<_SizeT>(__r - __p);
748 // __str_find_first_of
749 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
750 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
751 __str_find_first_of(const _CharT *__p, _SizeT __sz,
752 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
754 if (__pos >= __sz || __n == 0)
756 const _CharT* __r = _VSTD::__find_first_of_ce
757 (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
758 if (__r == __p + __sz)
760 return static_cast<_SizeT>(__r - __p);
764 // __str_find_last_of
765 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
766 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
767 __str_find_last_of(const _CharT *__p, _SizeT __sz,
768 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
776 for (const _CharT* __ps = __p + __pos; __ps != __p;)
778 const _CharT* __r = _Traits::find(__s, __n, *--__ps);
780 return static_cast<_SizeT>(__ps - __p);
787 // __str_find_first_not_of
788 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
789 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
790 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
791 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
795 const _CharT* __pe = __p + __sz;
796 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
797 if (_Traits::find(__s, __n, *__ps) == 0)
798 return static_cast<_SizeT>(__ps - __p);
804 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
805 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
806 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
807 _CharT __c, _SizeT __pos) _NOEXCEPT
811 const _CharT* __pe = __p + __sz;
812 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
813 if (!_Traits::eq(*__ps, __c))
814 return static_cast<_SizeT>(__ps - __p);
820 // __str_find_last_not_of
821 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
822 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
823 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
824 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
830 for (const _CharT* __ps = __p + __pos; __ps != __p;)
831 if (_Traits::find(__s, __n, *--__ps) == 0)
832 return static_cast<_SizeT>(__ps - __p);
837 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
838 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
839 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
840 _CharT __c, _SizeT __pos) _NOEXCEPT
846 for (const _CharT* __ps = __p + __pos; __ps != __p;)
847 if (!_Traits::eq(*--__ps, __c))
848 return static_cast<_SizeT>(__ps - __p);
853 inline _LIBCPP_INLINE_VISIBILITY
854 size_t __do_string_hash(_Ptr __p, _Ptr __e)
856 typedef typename iterator_traits<_Ptr>::value_type value_type;
857 return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
860 template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
861 struct __quoted_output_proxy
868 __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
869 : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
870 // This would be a nice place for a string_ref
873 _LIBCPP_END_NAMESPACE_STD
877 #endif // _LIBCPP___STRING