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