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
17namespace std
18{
19
20template <class charT>
21struct 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
47template <> struct char_traits<char>;
48template <> 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
71template <class _CharT>
72struct _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
110template <class _CharT>
111int
112char_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
124template <class _CharT>
125inline
126size_t
127char_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
135template <class _CharT>
136inline
137const _CharT*
138char_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
149template <class _CharT>
150_CharT*
151char_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
169template <class _CharT>
170inline
171_CharT*
172char_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
181template <class _CharT>
182inline
183_CharT*
184char_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
194template <>
195struct _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
239template <>
240struct _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
285template <>
286struct _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
326inline
327int
328char_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
340inline
341size_t
342char_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
350inline
351const char16_t*
352char_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
363inline
364char16_t*
365char_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
383inline
384char16_t*
385char_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
394inline
395char16_t*
396char_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
404template <>
405struct _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
445inline
446int
447char_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
459inline
460size_t
461char_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
469inline
470const char32_t*
471char_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
482inline
483char32_t*
484char_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
502inline
503char32_t*
504char_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
513inline
514char32_t*
515char_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
528template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
529inline _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
541template <class _CharT, class _Traits>
542inline _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
580template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
581inline _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
602template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
603inline _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
621template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
622inline _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
640template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
641inline _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
656template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
657inline _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
679template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
680inline _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
695template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
696inline _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
712template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
713inline _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
728template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
729inline _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
743template<class _Ptr>
744inline _LIBCPP_INLINE_VISIBILITY
745size_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
751template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
752struct __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
767