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
assignchar_traits49 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
eqchar_traits50 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
51 {return __c1 == __c2;}
ltchar_traits52 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
not_eofchar_traits70 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
71 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
to_char_typechar_traits72 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
73 {return char_type(__c);}
to_int_typechar_traits74 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
75 {return int_type(__c);}
eq_int_typechar_traits76 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
77 {return __c1 == __c2;}
eofchar_traits78 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
compare(const char_type * __s1,const char_type * __s2,size_t __n)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
length(const char_type * __s)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*
find(const char_type * __s,size_t __n,const char_type & __a)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*
move(char_type * __s1,const char_type * __s2,size_t __n)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*
copy(char_type * __s1,const char_type * __s2,size_t __n)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*
assign(char_type * __s,size_t __n,char_type __a)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
__char_traits_move(_CharT * __dest,const _CharT * __source,size_t __n)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