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