2 //===-------------------------- __string ----------------------------------===//
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
8 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP___STRING
11 #define _LIBCPP___STRING
19 template <class charT>
22 typedef charT char_type;
24 typedef streamoff off_type;
25 typedef streampos pos_type;
26 typedef mbstate_t state_type;
28 static constexpr void assign(char_type& c1, const char_type& c2) noexcept;
29 static constexpr bool eq(char_type c1, char_type c2) noexcept;
30 static constexpr bool lt(char_type c1, char_type c2) noexcept;
32 static constexpr int compare(const char_type* s1, const char_type* s2, size_t n);
33 static constexpr size_t length(const char_type* s);
34 static constexpr const char_type*
35 find(const char_type* s, size_t n, const char_type& a);
37 static constexpr char_type* move(char_type* s1, const char_type* s2, size_t n); // constexpr in C++20
38 static constexpr char_type* copy(char_type* s1, const char_type* s2, size_t n); // constexpr in C++20
39 static constexpr char_type* assign(char_type* s, size_t n, char_type a); // constexpr in C++20
41 static constexpr int_type not_eof(int_type c) noexcept;
42 static constexpr char_type to_char_type(int_type c) noexcept;
43 static constexpr int_type to_int_type(char_type c) noexcept;
44 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept;
45 static constexpr int_type eof() noexcept;
48 template <> struct char_traits<char>;
49 template <> struct char_traits<wchar_t>;
50 template <> struct char_traits<char8_t>; // c++20
57 #include <algorithm> // for search and min
58 #include <cstdio> // For EOF.
59 #include <memory> // for __murmur2_or_cityhash
63 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
64 #pragma GCC system_header
68 #include <__undef_macros>
71 _LIBCPP_BEGIN_NAMESPACE_STD
75 template <class _CharT>
76 struct _LIBCPP_TEMPLATE_VIS char_traits
78 typedef _CharT char_type;
80 typedef streamoff off_type;
81 typedef streampos pos_type;
82 typedef mbstate_t state_type;
84 static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14
85 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
86 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
87 {return __c1 == __c2;}
88 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
91 static _LIBCPP_CONSTEXPR_AFTER_CXX14
92 int compare(const char_type* __s1, const char_type* __s2, size_t __n);
93 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
94 size_t length(const char_type* __s);
95 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
96 const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
97 static _LIBCPP_CONSTEXPR_AFTER_CXX17
98 char_type* move(char_type* __s1, const char_type* __s2, size_t __n);
99 _LIBCPP_INLINE_VISIBILITY
100 static _LIBCPP_CONSTEXPR_AFTER_CXX17
101 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n);
102 _LIBCPP_INLINE_VISIBILITY
103 static _LIBCPP_CONSTEXPR_AFTER_CXX17
104 char_type* assign(char_type* __s, size_t __n, char_type __a);
106 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
107 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
108 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
109 {return char_type(__c);}
110 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
111 {return int_type(__c);}
112 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
113 {return __c1 == __c2;}
114 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
115 {return int_type(EOF);}
118 template <class _CharT>
119 _LIBCPP_CONSTEXPR_AFTER_CXX14 int
120 char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
122 for (; __n; --__n, ++__s1, ++__s2)
124 if (lt(*__s1, *__s2))
126 if (lt(*__s2, *__s1))
132 template <class _CharT>
134 _LIBCPP_CONSTEXPR_AFTER_CXX14 size_t
135 char_traits<_CharT>::length(const char_type* __s)
138 for (; !eq(*__s, char_type(0)); ++__s)
143 template <class _CharT>
145 _LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT*
146 char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
157 template <class _CharT>
158 _LIBCPP_CONSTEXPR_AFTER_CXX17 _CharT*
159 char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
161 if (__n == 0) return __s1;
162 char_type* __r = __s1;
165 for (; __n; --__n, ++__s1, ++__s2)
166 assign(*__s1, *__s2);
168 else if (__s2 < __s1)
173 assign(*--__s1, *--__s2);
178 template <class _CharT>
179 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
181 char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
183 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
184 char_type* __r = __s1;
185 for (; __n; --__n, ++__s1, ++__s2)
186 assign(*__s1, *__s2);
190 template <class _CharT>
191 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
193 char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
195 char_type* __r = __s;
196 for (; __n; --__n, ++__s)
201 // constexpr versions of move/copy/assign.
203 template <class _CharT>
204 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
205 _CharT* __move_constexpr(_CharT* __s1, const _CharT* __s2, size_t __n) _NOEXCEPT
207 if (__n == 0) return __s1;
209 _VSTD::copy(__s2, __s2 + __n, __s1);
210 } else if (__s2 < __s1) {
211 _VSTD::copy_backward(__s2, __s2 + __n, __s1 + __n);
216 template <class _CharT>
217 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
218 _CharT* __copy_constexpr(_CharT* __s1, const _CharT* __s2, size_t __n) _NOEXCEPT
220 _VSTD::copy_n(__s2, __n, __s1);
224 template <class _CharT>
225 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
226 _CharT* __assign_constexpr(_CharT* __s, size_t __n, _CharT __a) _NOEXCEPT
228 _VSTD::fill_n(__s, __n, __a);
235 struct _LIBCPP_TEMPLATE_VIS char_traits<char>
237 typedef char char_type;
238 typedef int int_type;
239 typedef streamoff off_type;
240 typedef streampos pos_type;
241 typedef mbstate_t state_type;
243 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
244 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
245 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
246 {return __c1 == __c2;}
247 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
248 {return (unsigned char)__c1 < (unsigned char)__c2;}
250 static _LIBCPP_CONSTEXPR_AFTER_CXX14
251 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
252 static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14
253 length(const char_type* __s) _NOEXCEPT {return __builtin_strlen(__s);}
254 static _LIBCPP_CONSTEXPR_AFTER_CXX14
255 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
256 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
257 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
259 return __libcpp_is_constant_evaluated()
260 ? __move_constexpr(__s1, __s2, __n)
261 : __n == 0 ? __s1 : (char_type*)memmove(__s1, __s2, __n);
263 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
264 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
266 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
267 return __libcpp_is_constant_evaluated()
268 ? __copy_constexpr(__s1, __s2, __n)
269 : __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
271 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
272 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
274 return __libcpp_is_constant_evaluated()
275 ? __assign_constexpr(__s, __n, __a)
276 : __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);
279 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
280 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
281 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
282 {return char_type(__c);}
283 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
284 {return int_type((unsigned char)__c);}
285 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
286 {return __c1 == __c2;}
287 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
288 {return int_type(EOF);}
291 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
293 char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
297 #if __has_feature(cxx_constexpr_string_builtins)
298 return __builtin_memcmp(__s1, __s2, __n);
299 #elif _LIBCPP_STD_VER <= 14
300 return memcmp(__s1, __s2, __n);
302 for (; __n; --__n, ++__s1, ++__s2)
304 if (lt(*__s1, *__s2))
306 if (lt(*__s2, *__s1))
313 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
315 char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
319 #if __has_feature(cxx_constexpr_string_builtins)
320 return __builtin_char_memchr(__s, to_int_type(__a), __n);
321 #elif _LIBCPP_STD_VER <= 14
322 return (const char_type*) memchr(__s, to_int_type(__a), __n);
335 // char_traits<wchar_t>
338 struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
340 typedef wchar_t char_type;
341 typedef wint_t int_type;
342 typedef streamoff off_type;
343 typedef streampos pos_type;
344 typedef mbstate_t state_type;
346 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
347 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
348 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
349 {return __c1 == __c2;}
350 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
351 {return __c1 < __c2;}
353 static _LIBCPP_CONSTEXPR_AFTER_CXX14
354 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
355 static _LIBCPP_CONSTEXPR_AFTER_CXX14
356 size_t length(const char_type* __s) _NOEXCEPT;
357 static _LIBCPP_CONSTEXPR_AFTER_CXX14
358 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
359 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
360 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
362 return __libcpp_is_constant_evaluated()
363 ? __move_constexpr(__s1, __s2, __n)
364 : __n == 0 ? __s1 : wmemmove(__s1, __s2, __n);
366 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
367 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
369 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
370 return __libcpp_is_constant_evaluated()
371 ? __copy_constexpr(__s1, __s2, __n)
372 : __n == 0 ? __s1 : wmemcpy(__s1, __s2, __n);
374 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
375 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
377 return __libcpp_is_constant_evaluated()
378 ? __assign_constexpr(__s, __n, __a)
379 : __n == 0 ? __s : wmemset(__s, __a, __n);
381 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
382 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
383 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
384 {return char_type(__c);}
385 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
386 {return int_type(__c);}
387 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
388 {return __c1 == __c2;}
389 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
390 {return int_type(WEOF);}
393 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
395 char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
399 #if __has_feature(cxx_constexpr_string_builtins)
400 return __builtin_wmemcmp(__s1, __s2, __n);
401 #elif _LIBCPP_STD_VER <= 14
402 return wmemcmp(__s1, __s2, __n);
404 for (; __n; --__n, ++__s1, ++__s2)
406 if (lt(*__s1, *__s2))
408 if (lt(*__s2, *__s1))
416 template <class _Traits>
417 _LIBCPP_INLINE_VISIBILITY
419 inline size_t __char_traits_length_checked(const typename _Traits::char_type* __s) _NOEXCEPT {
420 #if _LIBCPP_DEBUG_LEVEL >= 1
421 return __s ? _Traits::length(__s) : (_VSTD::__libcpp_debug_function(_VSTD::__libcpp_debug_info(__FILE__, __LINE__, "p == nullptr", "null pointer pass to non-null argument of char_traits<...>::length")), 0);
423 return _Traits::length(__s);
427 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
429 char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
431 #if __has_feature(cxx_constexpr_string_builtins)
432 return __builtin_wcslen(__s);
433 #elif _LIBCPP_STD_VER <= 14
437 for (; !eq(*__s, char_type(0)); ++__s)
443 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
445 char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
449 #if __has_feature(cxx_constexpr_string_builtins)
450 return __builtin_wmemchr(__s, __a, __n);
451 #elif _LIBCPP_STD_VER <= 14
452 return wmemchr(__s, __a, __n);
465 #ifndef _LIBCPP_NO_HAS_CHAR8_T
468 struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
470 typedef char8_t char_type;
471 typedef unsigned int int_type;
472 typedef streamoff off_type;
473 typedef u8streampos pos_type;
474 typedef mbstate_t state_type;
476 static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
478 static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept
479 {return __c1 == __c2;}
480 static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept
481 {return __c1 < __c2;}
484 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
487 size_t length(const char_type* __s) _NOEXCEPT;
489 _LIBCPP_INLINE_VISIBILITY static constexpr
490 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
492 static _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
493 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
495 return __libcpp_is_constant_evaluated()
496 ? __move_constexpr(__s1, __s2, __n)
497 : __n == 0 ? __s1 : (char_type*)memmove(__s1, __s2, __n);
500 static _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
501 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
503 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
504 return __libcpp_is_constant_evaluated()
505 ? __copy_constexpr(__s1, __s2, __n)
506 : __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
509 static _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
510 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
512 return __libcpp_is_constant_evaluated()
513 ? __assign_constexpr(__s, __n, __a)
514 : __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);
517 static inline constexpr int_type not_eof(int_type __c) noexcept
518 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
519 static inline constexpr char_type to_char_type(int_type __c) noexcept
520 {return char_type(__c);}
521 static inline constexpr int_type to_int_type(char_type __c) noexcept
522 {return int_type(__c);}
523 static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
524 {return __c1 == __c2;}
525 static inline constexpr int_type eof() noexcept
526 {return int_type(EOF);}
529 // TODO use '__builtin_strlen' if it ever supports char8_t ??
532 char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT
535 for (; !eq(*__s, char_type(0)); ++__s)
542 char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
544 #if __has_feature(cxx_constexpr_string_builtins)
545 return __builtin_memcmp(__s1, __s2, __n);
547 for (; __n; --__n, ++__s1, ++__s2)
549 if (lt(*__s1, *__s2))
551 if (lt(*__s2, *__s1))
558 // TODO use '__builtin_char_memchr' if it ever supports char8_t ??
561 char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
572 #endif // #_LIBCPP_NO_HAS_CHAR8_T
574 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
577 struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
579 typedef char16_t char_type;
580 typedef uint_least16_t int_type;
581 typedef streamoff off_type;
582 typedef u16streampos pos_type;
583 typedef mbstate_t state_type;
585 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
586 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
587 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
588 {return __c1 == __c2;}
589 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
590 {return __c1 < __c2;}
592 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
593 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
594 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
595 size_t length(const char_type* __s) _NOEXCEPT;
596 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
597 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
598 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
599 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
600 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
601 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
602 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
603 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
605 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
606 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
607 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
608 {return char_type(__c);}
609 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
610 {return int_type(__c);}
611 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
612 {return __c1 == __c2;}
613 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
614 {return int_type(0xFFFF);}
617 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
619 char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
621 for (; __n; --__n, ++__s1, ++__s2)
623 if (lt(*__s1, *__s2))
625 if (lt(*__s2, *__s1))
631 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
633 char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
636 for (; !eq(*__s, char_type(0)); ++__s)
641 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
643 char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
654 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
656 char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
658 if (__n == 0) return __s1;
659 char_type* __r = __s1;
662 for (; __n; --__n, ++__s1, ++__s2)
663 assign(*__s1, *__s2);
665 else if (__s2 < __s1)
670 assign(*--__s1, *--__s2);
675 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
677 char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
679 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
680 char_type* __r = __s1;
681 for (; __n; --__n, ++__s1, ++__s2)
682 assign(*__s1, *__s2);
686 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
688 char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
690 char_type* __r = __s;
691 for (; __n; --__n, ++__s)
697 struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
699 typedef char32_t char_type;
700 typedef uint_least32_t int_type;
701 typedef streamoff off_type;
702 typedef u32streampos pos_type;
703 typedef mbstate_t state_type;
705 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
706 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
707 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
708 {return __c1 == __c2;}
709 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
710 {return __c1 < __c2;}
712 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
713 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
714 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
715 size_t length(const char_type* __s) _NOEXCEPT;
716 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
717 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
718 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
719 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
720 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
721 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
722 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
723 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
725 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
726 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
727 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
728 {return char_type(__c);}
729 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
730 {return int_type(__c);}
731 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
732 {return __c1 == __c2;}
733 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
734 {return int_type(0xFFFFFFFF);}
737 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
739 char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
741 for (; __n; --__n, ++__s1, ++__s2)
743 if (lt(*__s1, *__s2))
745 if (lt(*__s2, *__s1))
751 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
753 char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
756 for (; !eq(*__s, char_type(0)); ++__s)
761 inline _LIBCPP_CONSTEXPR_AFTER_CXX14
763 char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
774 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
776 char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
778 if (__n == 0) return __s1;
779 char_type* __r = __s1;
782 for (; __n; --__n, ++__s1, ++__s2)
783 assign(*__s1, *__s2);
785 else if (__s2 < __s1)
790 assign(*--__s1, *--__s2);
795 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
797 char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
799 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
800 char_type* __r = __s1;
801 for (; __n; --__n, ++__s1, ++__s2)
802 assign(*__s1, *__s2);
806 inline _LIBCPP_CONSTEXPR_AFTER_CXX17
808 char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
810 char_type* __r = __s;
811 for (; __n; --__n, ++__s)
816 #endif // _LIBCPP_HAS_NO_UNICODE_CHARS
818 // helper fns for basic_string and string_view
821 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
822 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
823 __str_find(const _CharT *__p, _SizeT __sz,
824 _CharT __c, _SizeT __pos) _NOEXCEPT
828 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
831 return static_cast<_SizeT>(__r - __p);
834 template <class _CharT, class _Traits>
835 inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
836 __search_substring(const _CharT *__first1, const _CharT *__last1,
837 const _CharT *__first2, const _CharT *__last2) {
838 // Take advantage of knowing source and pattern lengths.
839 // Stop short when source is smaller than pattern.
840 const ptrdiff_t __len2 = __last2 - __first2;
844 ptrdiff_t __len1 = __last1 - __first1;
848 // First element of __first2 is loop invariant.
849 _CharT __f2 = *__first2;
851 __len1 = __last1 - __first1;
852 // Check whether __first1 still has at least __len2 bytes.
856 // Find __f2 the first byte matching in __first1.
857 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
861 // It is faster to compare from the first byte of __first1 even if we
862 // already know that it matches the first byte of __first2: this is because
863 // __first2 is most likely aligned, as it is user's "pattern" string, and
864 // __first1 + 1 is most likely not aligned, as the match is in the middle of
866 if (_Traits::compare(__first1, __first2, __len2) == 0)
873 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
874 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
875 __str_find(const _CharT *__p, _SizeT __sz,
876 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
881 if (__n == 0) // There is nothing to search, just return __pos.
884 const _CharT *__r = __search_substring<_CharT, _Traits>(
885 __p + __pos, __p + __sz, __s, __s + __n);
887 if (__r == __p + __sz)
889 return static_cast<_SizeT>(__r - __p);
895 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
896 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
897 __str_rfind(const _CharT *__p, _SizeT __sz,
898 _CharT __c, _SizeT __pos) _NOEXCEPT
906 for (const _CharT* __ps = __p + __pos; __ps != __p;)
908 if (_Traits::eq(*--__ps, __c))
909 return static_cast<_SizeT>(__ps - __p);
914 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
915 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
916 __str_rfind(const _CharT *__p, _SizeT __sz,
917 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
919 __pos = _VSTD::min(__pos, __sz);
920 if (__n < __sz - __pos)
924 const _CharT* __r = _VSTD::__find_end(
925 __p, __p + __pos, __s, __s + __n, _Traits::eq,
926 random_access_iterator_tag(), random_access_iterator_tag());
927 if (__n > 0 && __r == __p + __pos)
929 return static_cast<_SizeT>(__r - __p);
932 // __str_find_first_of
933 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
934 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
935 __str_find_first_of(const _CharT *__p, _SizeT __sz,
936 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
938 if (__pos >= __sz || __n == 0)
940 const _CharT* __r = _VSTD::__find_first_of_ce
941 (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
942 if (__r == __p + __sz)
944 return static_cast<_SizeT>(__r - __p);
948 // __str_find_last_of
949 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
950 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
951 __str_find_last_of(const _CharT *__p, _SizeT __sz,
952 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
960 for (const _CharT* __ps = __p + __pos; __ps != __p;)
962 const _CharT* __r = _Traits::find(__s, __n, *--__ps);
964 return static_cast<_SizeT>(__ps - __p);
971 // __str_find_first_not_of
972 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
973 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
974 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
975 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
979 const _CharT* __pe = __p + __sz;
980 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
981 if (_Traits::find(__s, __n, *__ps) == 0)
982 return static_cast<_SizeT>(__ps - __p);
988 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
989 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
990 __str_find_first_not_of(const _CharT *__p, _SizeT __sz,
991 _CharT __c, _SizeT __pos) _NOEXCEPT
995 const _CharT* __pe = __p + __sz;
996 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
997 if (!_Traits::eq(*__ps, __c))
998 return static_cast<_SizeT>(__ps - __p);
1004 // __str_find_last_not_of
1005 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1006 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1007 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
1008 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1014 for (const _CharT* __ps = __p + __pos; __ps != __p;)
1015 if (_Traits::find(__s, __n, *--__ps) == 0)
1016 return static_cast<_SizeT>(__ps - __p);
1021 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1022 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1023 __str_find_last_not_of(const _CharT *__p, _SizeT __sz,
1024 _CharT __c, _SizeT __pos) _NOEXCEPT
1030 for (const _CharT* __ps = __p + __pos; __ps != __p;)
1031 if (!_Traits::eq(*--__ps, __c))
1032 return static_cast<_SizeT>(__ps - __p);
1036 template<class _Ptr>
1037 inline _LIBCPP_INLINE_VISIBILITY
1038 size_t __do_string_hash(_Ptr __p, _Ptr __e)
1040 typedef typename iterator_traits<_Ptr>::value_type value_type;
1041 return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
1044 template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
1045 struct __quoted_output_proxy
1052 __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
1053 : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
1054 // This would be a nice place for a string_ref
1057 _LIBCPP_END_NAMESPACE_STD
1061 #endif // _LIBCPP___STRING