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