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