1// -*- C++ -*-
2//===-------------------------- __string ----------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___STRING
11#define _LIBCPP___STRING
12
13/*
14    string synopsis
15
16namespace std
17{
18
19template <class charT>
20struct char_traits
21{
22    typedef charT     char_type;
23    typedef ...       int_type;
24    typedef streamoff off_type;
25    typedef streampos pos_type;
26    typedef mbstate_t state_type;
27
28    static constexpr void assign(char_type& c1, const char_type& c2) noexcept;
29    static constexpr bool eq(char_type c1, char_type c2) noexcept;
30    static constexpr bool lt(char_type c1, char_type c2) noexcept;
31
32    static constexpr int    compare(const char_type* s1, const char_type* s2, size_t n);
33    static constexpr size_t length(const char_type* s);
34    static constexpr const char_type*
35                            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>;
49template <> struct char_traits<char8_t>;  // c++20
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 <__debug>
61
62#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
63#pragma GCC system_header
64#endif
65
66_LIBCPP_PUSH_MACROS
67#include <__undef_macros>
68
69
70_LIBCPP_BEGIN_NAMESPACE_STD
71
72// char_traits
73
74template <class _CharT>
75struct _LIBCPP_TEMPLATE_VIS char_traits
76{
77    typedef _CharT    char_type;
78    typedef int       int_type;
79    typedef streamoff off_type;
80    typedef streampos pos_type;
81    typedef mbstate_t state_type;
82
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
88        {return __c1 < __c2;}
89
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);
101
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);}
112};
113
114template <class _CharT>
115_LIBCPP_CONSTEXPR_AFTER_CXX14 int
116char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
117{
118    for (; __n; --__n, ++__s1, ++__s2)
119    {
120        if (lt(*__s1, *__s2))
121            return -1;
122        if (lt(*__s2, *__s1))
123            return 1;
124    }
125    return 0;
126}
127
128template <class _CharT>
129inline
130_LIBCPP_CONSTEXPR_AFTER_CXX14 size_t
131char_traits<_CharT>::length(const char_type* __s)
132{
133    size_t __len = 0;
134    for (; !eq(*__s, char_type(0)); ++__s)
135        ++__len;
136    return __len;
137}
138
139template <class _CharT>
140inline
141_LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT*
142char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
143{
144    for (; __n; --__n)
145    {
146        if (eq(*__s, __a))
147            return __s;
148        ++__s;
149    }
150    return 0;
151}
152
153template <class _CharT>
154_CharT*
155char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
156{
157    char_type* __r = __s1;
158    if (__s1 < __s2)
159    {
160        for (; __n; --__n, ++__s1, ++__s2)
161            assign(*__s1, *__s2);
162    }
163    else if (__s2 < __s1)
164    {
165        __s1 += __n;
166        __s2 += __n;
167        for (; __n; --__n)
168            assign(*--__s1, *--__s2);
169    }
170    return __r;
171}
172
173template <class _CharT>
174inline
175_CharT*
176char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
177{
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);
182    return __r;
183}
184
185template <class _CharT>
186inline
187_CharT*
188char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
189{
190    char_type* __r = __s;
191    for (; __n; --__n, ++__s)
192        assign(*__s, __a);
193    return __r;
194}
195
196// char_traits<char>
197
198template <>
199struct _LIBCPP_TEMPLATE_VIS char_traits<char>
200{
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;
206
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;}
213
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
223        {
224            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
225            return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
226        }
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);}
229
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);}
240};
241
242inline _LIBCPP_CONSTEXPR_AFTER_CXX14
243int
244char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
245{
246    if (__n == 0)
247        return 0;
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);
252#else
253    for (; __n; --__n, ++__s1, ++__s2)
254    {
255        if (lt(*__s1, *__s2))
256            return -1;
257        if (lt(*__s2, *__s1))
258            return 1;
259    }
260    return 0;
261#endif
262}
263
264inline _LIBCPP_CONSTEXPR_AFTER_CXX14
265const char*
266char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
267{
268    if (__n == 0)
269        return nullptr;
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);
274#else
275    for (; __n; --__n)
276    {
277        if (eq(*__s, __a))
278            return __s;
279        ++__s;
280    }
281    return nullptr;
282#endif
283}
284
285
286// char_traits<wchar_t>
287
288template <>
289struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
290{
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;
296
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;}
303
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
313        {
314            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
315            return __n == 0 ? __s1 : (char_type*)wmemcpy(__s1, __s2, __n);
316        }
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);}
319
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);}
330};
331
332inline _LIBCPP_CONSTEXPR_AFTER_CXX14
333int
334char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
335{
336    if (__n == 0)
337        return 0;
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);
342#else
343    for (; __n; --__n, ++__s1, ++__s2)
344    {
345        if (lt(*__s1, *__s2))
346            return -1;
347        if (lt(*__s2, *__s1))
348            return 1;
349    }
350    return 0;
351#endif
352}
353
354inline _LIBCPP_CONSTEXPR_AFTER_CXX14
355size_t
356char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
357{
358#if __has_feature(cxx_constexpr_string_builtins)
359    return __builtin_wcslen(__s);
360#elif _LIBCPP_STD_VER <= 14
361    return wcslen(__s);
362#else
363    size_t __len = 0;
364    for (; !eq(*__s, char_type(0)); ++__s)
365        ++__len;
366    return __len;
367#endif
368}
369
370inline _LIBCPP_CONSTEXPR_AFTER_CXX14
371const wchar_t*
372char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
373{
374    if (__n == 0)
375        return nullptr;
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);
380#else
381    for (; __n; --__n)
382    {
383        if (eq(*__s, __a))
384            return __s;
385        ++__s;
386    }
387    return nullptr;
388#endif
389}
390
391
392#ifndef _LIBCPP_NO_HAS_CHAR8_T
393
394template <>
395struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
396{
397    typedef char8_t        char_type;
398    typedef unsigned int   int_type;
399    typedef streamoff      off_type;
400    typedef u8streampos    pos_type;
401    typedef mbstate_t      state_type;
402
403    static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
404        {__c1 = __c2;}
405    static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept
406        {return __c1 == __c2;}
407    static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept
408        {return __c1 < __c2;}
409
410    static constexpr
411    int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
412
413    static constexpr
414    size_t           length(const char_type* __s) _NOEXCEPT;
415
416    _LIBCPP_INLINE_VISIBILITY static constexpr
417    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
418
419    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
420        {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}
421
422    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
423       {
424            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
425            return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
426       }
427
428    static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
429        {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);}
430
431    static inline constexpr int_type  not_eof(int_type __c) noexcept
432        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
433    static inline constexpr char_type to_char_type(int_type __c) noexcept
434        {return char_type(__c);}
435    static inline constexpr int_type to_int_type(char_type __c) noexcept
436        {return int_type(__c);}
437    static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
438        {return __c1 == __c2;}
439    static inline constexpr int_type eof() noexcept
440        {return int_type(EOF);}
441};
442
443// TODO use '__builtin_strlen' if it ever supports char8_t ??
444inline constexpr
445size_t
446char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT
447{
448    size_t __len = 0;
449    for (; !eq(*__s, char_type(0)); ++__s)
450        ++__len;
451    return __len;
452}
453
454inline constexpr
455int
456char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
457{
458#if __has_feature(cxx_constexpr_string_builtins)
459    return __builtin_memcmp(__s1, __s2, __n);
460#else
461    for (; __n; --__n, ++__s1, ++__s2)
462    {
463        if (lt(*__s1, *__s2))
464            return -1;
465        if (lt(*__s2, *__s1))
466            return 1;
467    }
468    return 0;
469#endif
470}
471
472// TODO use '__builtin_char_memchr' if it ever supports char8_t ??
473inline constexpr
474const char8_t*
475char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
476{
477    for (; __n; --__n)
478    {
479        if (eq(*__s, __a))
480            return __s;
481        ++__s;
482    }
483    return 0;
484}
485
486#endif // #_LIBCPP_NO_HAS_CHAR8_T
487
488#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
489
490template <>
491struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
492{
493    typedef char16_t       char_type;
494    typedef uint_least16_t int_type;
495    typedef streamoff      off_type;
496    typedef u16streampos   pos_type;
497    typedef mbstate_t      state_type;
498
499    static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
500    void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
501    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
502        {return __c1 == __c2;}
503    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
504        {return __c1 < __c2;}
505
506    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
507    int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
508    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
509    size_t           length(const char_type* __s) _NOEXCEPT;
510    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
511    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
512    _LIBCPP_INLINE_VISIBILITY
513    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
514    _LIBCPP_INLINE_VISIBILITY
515    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
516    _LIBCPP_INLINE_VISIBILITY
517    static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
518
519    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
520        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
521    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
522        {return char_type(__c);}
523    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
524        {return int_type(__c);}
525    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
526        {return __c1 == __c2;}
527    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
528        {return int_type(0xFFFF);}
529};
530
531inline _LIBCPP_CONSTEXPR_AFTER_CXX14
532int
533char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
534{
535    for (; __n; --__n, ++__s1, ++__s2)
536    {
537        if (lt(*__s1, *__s2))
538            return -1;
539        if (lt(*__s2, *__s1))
540            return 1;
541    }
542    return 0;
543}
544
545inline _LIBCPP_CONSTEXPR_AFTER_CXX14
546size_t
547char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
548{
549    size_t __len = 0;
550    for (; !eq(*__s, char_type(0)); ++__s)
551        ++__len;
552    return __len;
553}
554
555inline _LIBCPP_CONSTEXPR_AFTER_CXX14
556const char16_t*
557char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
558{
559    for (; __n; --__n)
560    {
561        if (eq(*__s, __a))
562            return __s;
563        ++__s;
564    }
565    return 0;
566}
567
568inline
569char16_t*
570char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
571{
572    char_type* __r = __s1;
573    if (__s1 < __s2)
574    {
575        for (; __n; --__n, ++__s1, ++__s2)
576            assign(*__s1, *__s2);
577    }
578    else if (__s2 < __s1)
579    {
580        __s1 += __n;
581        __s2 += __n;
582        for (; __n; --__n)
583            assign(*--__s1, *--__s2);
584    }
585    return __r;
586}
587
588inline
589char16_t*
590char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
591{
592    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
593    char_type* __r = __s1;
594    for (; __n; --__n, ++__s1, ++__s2)
595        assign(*__s1, *__s2);
596    return __r;
597}
598
599inline
600char16_t*
601char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
602{
603    char_type* __r = __s;
604    for (; __n; --__n, ++__s)
605        assign(*__s, __a);
606    return __r;
607}
608
609template <>
610struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
611{
612    typedef char32_t       char_type;
613    typedef uint_least32_t int_type;
614    typedef streamoff      off_type;
615    typedef u32streampos   pos_type;
616    typedef mbstate_t      state_type;
617
618    static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
619    void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
620    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
621        {return __c1 == __c2;}
622    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
623        {return __c1 < __c2;}
624
625    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
626    int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
627    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
628    size_t           length(const char_type* __s) _NOEXCEPT;
629    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
630    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
631    _LIBCPP_INLINE_VISIBILITY
632    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
633    _LIBCPP_INLINE_VISIBILITY
634    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
635    _LIBCPP_INLINE_VISIBILITY
636    static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
637
638    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
639        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
640    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
641        {return char_type(__c);}
642    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
643        {return int_type(__c);}
644    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
645        {return __c1 == __c2;}
646    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
647        {return int_type(0xFFFFFFFF);}
648};
649
650inline _LIBCPP_CONSTEXPR_AFTER_CXX14
651int
652char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
653{
654    for (; __n; --__n, ++__s1, ++__s2)
655    {
656        if (lt(*__s1, *__s2))
657            return -1;
658        if (lt(*__s2, *__s1))
659            return 1;
660    }
661    return 0;
662}
663
664inline _LIBCPP_CONSTEXPR_AFTER_CXX14
665size_t
666char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
667{
668    size_t __len = 0;
669    for (; !eq(*__s, char_type(0)); ++__s)
670        ++__len;
671    return __len;
672}
673
674inline _LIBCPP_CONSTEXPR_AFTER_CXX14
675const char32_t*
676char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
677{
678    for (; __n; --__n)
679    {
680        if (eq(*__s, __a))
681            return __s;
682        ++__s;
683    }
684    return 0;
685}
686
687inline
688char32_t*
689char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
690{
691    char_type* __r = __s1;
692    if (__s1 < __s2)
693    {
694        for (; __n; --__n, ++__s1, ++__s2)
695            assign(*__s1, *__s2);
696    }
697    else if (__s2 < __s1)
698    {
699        __s1 += __n;
700        __s2 += __n;
701        for (; __n; --__n)
702            assign(*--__s1, *--__s2);
703    }
704    return __r;
705}
706
707inline
708char32_t*
709char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
710{
711    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
712    char_type* __r = __s1;
713    for (; __n; --__n, ++__s1, ++__s2)
714        assign(*__s1, *__s2);
715    return __r;
716}
717
718inline
719char32_t*
720char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
721{
722    char_type* __r = __s;
723    for (; __n; --__n, ++__s)
724        assign(*__s, __a);
725    return __r;
726}
727
728#endif  // _LIBCPP_HAS_NO_UNICODE_CHARS
729
730// helper fns for basic_string and string_view
731
732// __str_find
733template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
734inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
735__str_find(const _CharT *__p, _SizeT __sz,
736             _CharT __c, _SizeT __pos) _NOEXCEPT
737{
738    if (__pos >= __sz)
739        return __npos;
740    const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
741    if (__r == 0)
742        return __npos;
743    return static_cast<_SizeT>(__r - __p);
744}
745
746template <class _CharT, class _Traits>
747inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
748__search_substring(const _CharT *__first1, const _CharT *__last1,
749                   const _CharT *__first2, const _CharT *__last2) {
750  // Take advantage of knowing source and pattern lengths.
751  // Stop short when source is smaller than pattern.
752  const ptrdiff_t __len2 = __last2 - __first2;
753  if (__len2 == 0)
754    return __first1;
755
756  ptrdiff_t __len1 = __last1 - __first1;
757  if (__len1 < __len2)
758    return __last1;
759
760  // First element of __first2 is loop invariant.
761  _CharT __f2 = *__first2;
762  while (true) {
763    __len1 = __last1 - __first1;
764    // Check whether __first1 still has at least __len2 bytes.
765    if (__len1 < __len2)
766      return __last1;
767
768    // Find __f2 the first byte matching in __first1.
769    __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
770    if (__first1 == 0)
771      return __last1;
772
773    // It is faster to compare from the first byte of __first1 even if we
774    // already know that it matches the first byte of __first2: this is because
775    // __first2 is most likely aligned, as it is user's "pattern" string, and
776    // __first1 + 1 is most likely not aligned, as the match is in the middle of
777    // the string.
778    if (_Traits::compare(__first1, __first2, __len2) == 0)
779      return __first1;
780
781    ++__first1;
782  }
783}
784
785template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
786inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
787__str_find(const _CharT *__p, _SizeT __sz,
788       const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
789{
790    if (__pos > __sz)
791        return __npos;
792
793    if (__n == 0) // There is nothing to search, just return __pos.
794        return __pos;
795
796    const _CharT *__r = __search_substring<_CharT, _Traits>(
797        __p + __pos, __p + __sz, __s, __s + __n);
798
799    if (__r == __p + __sz)
800        return __npos;
801    return static_cast<_SizeT>(__r - __p);
802}
803
804
805// __str_rfind
806
807template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
808inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
809__str_rfind(const _CharT *__p, _SizeT __sz,
810              _CharT __c, _SizeT __pos) _NOEXCEPT
811{
812    if (__sz < 1)
813        return __npos;
814    if (__pos < __sz)
815        ++__pos;
816    else
817        __pos = __sz;
818    for (const _CharT* __ps = __p + __pos; __ps != __p;)
819    {
820        if (_Traits::eq(*--__ps, __c))
821            return static_cast<_SizeT>(__ps - __p);
822    }
823    return __npos;
824}
825
826template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
827inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
828__str_rfind(const _CharT *__p, _SizeT __sz,
829        const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
830{
831    __pos = _VSTD::min(__pos, __sz);
832    if (__n < __sz - __pos)
833        __pos += __n;
834    else
835        __pos = __sz;
836    const _CharT* __r = _VSTD::__find_end(
837                  __p, __p + __pos, __s, __s + __n, _Traits::eq,
838                        random_access_iterator_tag(), random_access_iterator_tag());
839    if (__n > 0 && __r == __p + __pos)
840        return __npos;
841    return static_cast<_SizeT>(__r - __p);
842}
843
844// __str_find_first_of
845template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
846inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
847__str_find_first_of(const _CharT *__p, _SizeT __sz,
848                const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
849{
850    if (__pos >= __sz || __n == 0)
851        return __npos;
852    const _CharT* __r = _VSTD::__find_first_of_ce
853        (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
854    if (__r == __p + __sz)
855        return __npos;
856    return static_cast<_SizeT>(__r - __p);
857}
858
859
860// __str_find_last_of
861template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
862inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
863__str_find_last_of(const _CharT *__p, _SizeT __sz,
864               const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
865    {
866    if (__n != 0)
867    {
868        if (__pos < __sz)
869            ++__pos;
870        else
871            __pos = __sz;
872        for (const _CharT* __ps = __p + __pos; __ps != __p;)
873        {
874            const _CharT* __r = _Traits::find(__s, __n, *--__ps);
875            if (__r)
876                return static_cast<_SizeT>(__ps - __p);
877        }
878    }
879    return __npos;
880}
881
882
883// __str_find_first_not_of
884template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
885inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
886__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
887                    const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
888{
889    if (__pos < __sz)
890    {
891        const _CharT* __pe = __p + __sz;
892        for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
893            if (_Traits::find(__s, __n, *__ps) == 0)
894                return static_cast<_SizeT>(__ps - __p);
895    }
896    return __npos;
897}
898
899
900template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
901inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
902__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
903                          _CharT __c, _SizeT __pos) _NOEXCEPT
904{
905    if (__pos < __sz)
906    {
907        const _CharT* __pe = __p + __sz;
908        for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
909            if (!_Traits::eq(*__ps, __c))
910                return static_cast<_SizeT>(__ps - __p);
911    }
912    return __npos;
913}
914
915
916// __str_find_last_not_of
917template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
918inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
919__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
920                   const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
921{
922    if (__pos < __sz)
923        ++__pos;
924    else
925        __pos = __sz;
926    for (const _CharT* __ps = __p + __pos; __ps != __p;)
927        if (_Traits::find(__s, __n, *--__ps) == 0)
928            return static_cast<_SizeT>(__ps - __p);
929    return __npos;
930}
931
932
933template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
934inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
935__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
936                         _CharT __c, _SizeT __pos) _NOEXCEPT
937{
938    if (__pos < __sz)
939        ++__pos;
940    else
941        __pos = __sz;
942    for (const _CharT* __ps = __p + __pos; __ps != __p;)
943        if (!_Traits::eq(*--__ps, __c))
944            return static_cast<_SizeT>(__ps - __p);
945    return __npos;
946}
947
948template<class _Ptr>
949inline _LIBCPP_INLINE_VISIBILITY
950size_t __do_string_hash(_Ptr __p, _Ptr __e)
951{
952    typedef typename iterator_traits<_Ptr>::value_type value_type;
953    return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
954}
955
956template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
957struct __quoted_output_proxy
958{
959    _Iter  __first;
960    _Iter  __last;
961    _CharT  __delim;
962    _CharT  __escape;
963
964    __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
965    : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
966    //  This would be a nice place for a string_ref
967};
968
969_LIBCPP_END_NAMESPACE_STD
970
971_LIBCPP_POP_MACROS
972
973#endif  // _LIBCPP___STRING
974