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