blob: 86c92477cbfeb174f93d6d8d437f9df1806d3476 [file] [log] [blame]
Louis Dionneeb8650a2021-11-17 16:25:01 -05001//===----------------------------------------------------------------------===//
Marshall Clow053d81c2016-07-21 05:31:24 +00002//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Marshall Clow053d81c2016-07-21 05:31:24 +00006//
7//===----------------------------------------------------------------------===//
8
Nikolas Klauser976f3702022-06-06 23:35:24 +02009#ifndef _LIBCPP___STRING_CHAR_TRAITS_H
10#define _LIBCPP___STRING_CHAR_TRAITS_H
Marshall Clow053d81c2016-07-21 05:31:24 +000011
Christopher Di Bella050b0642021-07-01 09:25:35 -040012#include <__algorithm/fill_n.h>
Nikolas Klauser29312d32024-04-20 11:40:18 +020013#include <__algorithm/find.h>
Christopher Di Bella050b0642021-07-01 09:25:35 -040014#include <__algorithm/find_end.h>
Arthur O'Dwyer4d81a462022-01-07 09:45:05 -050015#include <__algorithm/find_first_of.h>
Christopher Di Bella050b0642021-07-01 09:25:35 -040016#include <__algorithm/min.h>
Louis Dionne37dca602024-02-29 10:12:22 -050017#include <__assert>
Nikolas Klauser7afa1592022-09-17 14:30:29 +020018#include <__compare/ordering.h>
Arthur O'Dwyer4d81a462022-01-07 09:45:05 -050019#include <__config>
Louis Dionne88f89932024-11-01 08:48:32 -040020#include <__cstddef/ptrdiff_t.h>
Nikolas Klauser976f3702022-06-06 23:35:24 +020021#include <__functional/hash.h>
Nikolas Klauser29312d32024-04-20 11:40:18 +020022#include <__functional/identity.h>
Christopher Di Bella050b0642021-07-01 09:25:35 -040023#include <__iterator/iterator_traits.h>
Louis Dionne09e3a362024-09-16 15:06:20 -040024#include <__std_mbstate_t.h>
Nikolas Klausere8cb3552023-02-05 00:21:11 +010025#include <__string/constexpr_c_functions.h>
Nikolas Klauser7afa1592022-09-17 14:30:29 +020026#include <__type_traits/is_constant_evaluated.h>
philnik7775a305cea2023-11-19 16:49:40 +010027#include <__utility/is_pointer_in_range.h>
Nikolas Klauser976f3702022-06-06 23:35:24 +020028#include <cstdint>
29#include <cstdio>
Nikolas Klauser976f3702022-06-06 23:35:24 +020030#include <iosfwd>
Louis Dionnef4c12582021-08-23 15:32:36 -040031
Nikolas Klauserc6f3b7b2024-11-06 10:39:19 +010032#if _LIBCPP_HAS_WIDE_CHARACTERS
Louis Dionne9783f282023-12-18 14:01:33 -050033# include <cwchar> // for wmemcpy
Louis Dionnef4c12582021-08-23 15:32:36 -040034#endif
Marshall Clow053d81c2016-07-21 05:31:24 +000035
Marshall Clow053d81c2016-07-21 05:31:24 +000036#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Arthur O'Dwyerfa6b9e42022-02-01 20:16:40 -050037# pragma GCC system_header
Marshall Clow053d81c2016-07-21 05:31:24 +000038#endif
39
Eric Fiseliera016efb2017-05-31 22:07:49 +000040_LIBCPP_PUSH_MACROS
41#include <__undef_macros>
42
Marshall Clow053d81c2016-07-21 05:31:24 +000043_LIBCPP_BEGIN_NAMESPACE_STD
44
Marshall Clow053d81c2016-07-21 05:31:24 +000045template <class _CharT>
Louis Dionneaeecef02022-11-17 10:47:18 -050046struct char_traits;
47/*
48The Standard does not define the base template for char_traits because it is impossible to provide
49a correct definition for arbitrary character types. Instead, it requires implementations to provide
50specializations for predefined character types like `char`, `wchar_t` and others. We provide this as
51exposition-only to document what members a char_traits specialization should provide:
Marshall Clow053d81c2016-07-21 05:31:24 +000052{
Mark de Wever2928b232022-08-04 19:44:21 +020053 using char_type = _CharT;
Louis Dionneaeecef02022-11-17 10:47:18 -050054 using int_type = ...;
55 using off_type = ...;
56 using pos_type = ...;
57 using state_type = ...;
Marshall Clow053d81c2016-07-21 05:31:24 +000058
Louis Dionneaeecef02022-11-17 10:47:18 -050059 static void assign(char_type&, const char_type&);
60 static bool eq(char_type, char_type);
61 static bool lt(char_type, char_type);
Marshall Clow053d81c2016-07-21 05:31:24 +000062
Louis Dionneaeecef02022-11-17 10:47:18 -050063 static int compare(const char_type*, const char_type*, size_t);
64 static size_t length(const char_type*);
65 static const char_type* find(const char_type*, size_t, const char_type&);
66 static char_type* move(char_type*, const char_type*, size_t);
Louis Dionne08a0faf2022-11-23 14:06:14 -050067 static char_type* copy(char_type*, const char_type*, size_t);
Louis Dionneaeecef02022-11-17 10:47:18 -050068 static char_type* assign(char_type*, size_t, char_type);
Marshall Clow053d81c2016-07-21 05:31:24 +000069
Louis Dionneaeecef02022-11-17 10:47:18 -050070 static int_type not_eof(int_type);
71 static char_type to_char_type(int_type);
72 static int_type to_int_type(char_type);
73 static bool eq_int_type(int_type, int_type);
74 static int_type eof();
Marshall Clow053d81c2016-07-21 05:31:24 +000075};
Louis Dionneaeecef02022-11-17 10:47:18 -050076*/
Marshall Clow053d81c2016-07-21 05:31:24 +000077
Marshall Clow053d81c2016-07-21 05:31:24 +000078// char_traits<char>
79
80template <>
Nikolas Klauseraf9c04f2025-04-09 23:47:57 +020081struct char_traits<char> {
Louis Dionne9783f282023-12-18 14:01:33 -050082 using char_type = char;
83 using int_type = int;
84 using off_type = streamoff;
85 using pos_type = streampos;
86 using state_type = mbstate_t;
Nikolas Klauser4f152672023-02-14 00:56:09 +010087#if _LIBCPP_STD_VER >= 20
Louis Dionne9783f282023-12-18 14:01:33 -050088 using comparison_category = strong_ordering;
Mark de Wever3818b4d2022-07-19 07:56:23 +020089#endif
Marshall Clow053d81c2016-07-21 05:31:24 +000090
Louis Dionne9783f282023-12-18 14:01:33 -050091 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void
92 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {
93 __c1 = __c2;
94 }
Nikolas Klauser83ce1392023-01-23 10:27:14 +010095
Louis Dionne9783f282023-12-18 14:01:33 -050096 // TODO: Make this _LIBCPP_HIDE_FROM_ABI
97 static inline _LIBCPP_HIDDEN _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT {
98 return __c1 == __c2;
99 }
100 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT {
101 return (unsigned char)__c1 < (unsigned char)__c2;
102 }
Marshall Clow053d81c2016-07-21 05:31:24 +0000103
Louis Dionne9783f282023-12-18 14:01:33 -0500104 // __constexpr_memcmp requires a trivially lexicographically comparable type, but char is not when char is a signed
105 // type
106 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int
107 compare(const char_type* __lhs, const char_type* __rhs, size_t __count) _NOEXCEPT {
108 if (__libcpp_is_constant_evaluated()) {
Nikolas Klauser746cf7e2023-05-07 11:18:32 -0700109#ifdef _LIBCPP_COMPILER_CLANG_BASED
Louis Dionne9783f282023-12-18 14:01:33 -0500110 return __builtin_memcmp(__lhs, __rhs, __count);
Nikolas Klauser746cf7e2023-05-07 11:18:32 -0700111#else
Louis Dionne9783f282023-12-18 14:01:33 -0500112 while (__count != 0) {
113 if (lt(*__lhs, *__rhs))
114 return -1;
115 if (lt(*__rhs, *__lhs))
116 return 1;
Nikolas Klauser148ef802021-12-15 21:12:24 +0100117
Louis Dionne9783f282023-12-18 14:01:33 -0500118 __count -= sizeof(char_type);
119 ++__lhs;
120 ++__rhs;
Nikolas Klauser746cf7e2023-05-07 11:18:32 -0700121 }
Louis Dionne9783f282023-12-18 14:01:33 -0500122 return 0;
123#endif // _LIBCPP_COMPILER_CLANG_BASED
124 } else {
125 return __builtin_memcmp(__lhs, __rhs, __count);
Nikolas Klauser746cf7e2023-05-07 11:18:32 -0700126 }
Louis Dionne9783f282023-12-18 14:01:33 -0500127 }
Nikolas Klauser148ef802021-12-15 21:12:24 +0100128
Louis Dionne9783f282023-12-18 14:01:33 -0500129 static inline _LIBCPP_HIDE_FROM_ABI size_t _LIBCPP_CONSTEXPR_SINCE_CXX17 length(const char_type* __s) _NOEXCEPT {
130 return std::__constexpr_strlen(__s);
131 }
Nikolas Klauser746cf7e2023-05-07 11:18:32 -0700132
Louis Dionne9783f282023-12-18 14:01:33 -0500133 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type*
134 find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
Louis Dionne9783f282023-12-18 14:01:33 -0500135 return std::__constexpr_memchr(__s, __a, __n);
136 }
Nikolas Klauser993a22e2022-06-13 17:54:20 +0200137
Louis Dionne9783f282023-12-18 14:01:33 -0500138 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
139 move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
140 return std::__constexpr_memmove(__s1, __s2, __element_count(__n));
141 }
Nikolas Klauser993a22e2022-06-13 17:54:20 +0200142
Louis Dionne9783f282023-12-18 14:01:33 -0500143 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
144 copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
145 _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__s1, __s1 + __n, __s2),
146 "char_traits::copy: source and destination ranges overlap");
Nikolas Klauser2096f372024-03-21 11:57:07 +0100147 std::__constexpr_memmove(__s1, __s2, __element_count(__n));
Louis Dionne9783f282023-12-18 14:01:33 -0500148 return __s1;
149 }
Nikolas Klauser993a22e2022-06-13 17:54:20 +0200150
Louis Dionne9783f282023-12-18 14:01:33 -0500151 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
152 assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT {
153 std::fill_n(__s, __n, __a);
154 return __s;
155 }
Marshall Clow053d81c2016-07-21 05:31:24 +0000156
Louis Dionne9783f282023-12-18 14:01:33 -0500157 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT {
158 return eq_int_type(__c, eof()) ? ~eof() : __c;
159 }
160 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT {
161 return char_type(__c);
162 }
163 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT {
164 return int_type((unsigned char)__c);
165 }
166 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT {
167 return __c1 == __c2;
168 }
169 static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT { return int_type(EOF); }
Marshall Clow053d81c2016-07-21 05:31:24 +0000170};
171
Nikolas Klauser2da00552024-07-06 15:35:13 +0200172template <class _CharT, class _IntT, _IntT _EOFVal>
173struct __char_traits_base {
174 using char_type = _CharT;
175 using int_type = _IntT;
176 using off_type = streamoff;
177 using state_type = mbstate_t;
178#if _LIBCPP_STD_VER >= 20
179 using comparison_category = strong_ordering;
180#endif
181
182 // There are different aliases for the different char types, but they are all aliases to this type
183 using pos_type = fpos<mbstate_t>;
184
185 _LIBCPP_HIDE_FROM_ABI static inline _LIBCPP_CONSTEXPR_SINCE_CXX17 void
186 assign(char_type& __lhs, const char_type& __rhs) _NOEXCEPT {
187 __lhs = __rhs;
188 }
189
190 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool eq(char_type __lhs, char_type __rhs) _NOEXCEPT {
191 return __lhs == __rhs;
192 }
193
194 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool lt(char_type __lhs, char_type __rhs) _NOEXCEPT {
195 return __lhs < __rhs;
196 }
197
198 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
199 move(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT {
200 return std::__constexpr_memmove(__dest, __src, __element_count(__n));
201 }
202
203 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
204 copy(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT {
205 _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__dest, __dest + __n, __src),
206 "char_traits::copy: source and destination ranges overlap");
207 return std::__constexpr_memmove(__dest, __src, __element_count(__n));
208 }
209
210 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX20 char_type*
211 assign(char_type* __str, size_t __n, char_type __fill_char) _NOEXCEPT {
212 std::fill_n(__str, __n, __fill_char);
213 return __str;
214 }
215
216 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT {
217 return char_type(__c);
218 }
219
220 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT { return int_type(__c); }
221
222 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR bool eq_int_type(int_type __lhs, int_type __rhs) _NOEXCEPT {
223 return __lhs == __rhs;
224 }
225
226 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT { return _EOFVal; }
227
228 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT {
229 return eq_int_type(__c, eof()) ? static_cast<int_type>(~eof()) : __c;
230 }
231};
232
Marshall Clow053d81c2016-07-21 05:31:24 +0000233// char_traits<wchar_t>
234
Nikolas Klauserc6f3b7b2024-11-06 10:39:19 +0100235#if _LIBCPP_HAS_WIDE_CHARACTERS
Marshall Clow053d81c2016-07-21 05:31:24 +0000236template <>
Nikolas Klauseraf9c04f2025-04-09 23:47:57 +0200237struct char_traits<wchar_t> : __char_traits_base<wchar_t, wint_t, static_cast<wint_t>(WEOF)> {
Nikolas Klauser83ce1392023-01-23 10:27:14 +0100238 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int
239 compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
Nikolas Klauser72173462022-12-07 18:31:14 +0100240 if (__n == 0)
Nikolas Klauser83ce1392023-01-23 10:27:14 +0100241 return 0;
Nikolas Klauser72173462022-12-07 18:31:14 +0100242 return std::__constexpr_wmemcmp(__s1, __s2, __n);
243 }
244
Nikolas Klauser83ce1392023-01-23 10:27:14 +0100245 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT {
Nikolas Klauser72173462022-12-07 18:31:14 +0100246 return std::__constexpr_wcslen(__s);
247 }
248
Louis Dionne9783f282023-12-18 14:01:33 -0500249 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type*
250 find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
Nikolas Klauser72173462022-12-07 18:31:14 +0100251 return std::__constexpr_wmemchr(__s, __a, __n);
252 }
Marshall Clow053d81c2016-07-21 05:31:24 +0000253};
Nikolas Klauserc6f3b7b2024-11-06 10:39:19 +0100254#endif // _LIBCPP_HAS_WIDE_CHARACTERS
Marshall Clow05d57fa2017-01-12 04:37:14 +0000255
Nikolas Klauserba875152024-10-12 09:49:52 +0200256#if _LIBCPP_HAS_CHAR8_T
Marshall Clow7dad0bd2018-12-11 04:35:44 +0000257
258template <>
Nikolas Klauseraf9c04f2025-04-09 23:47:57 +0200259struct char_traits<char8_t> : __char_traits_base<char8_t, unsigned int, static_cast<unsigned int>(EOF)> {
Nikolas Klauser72173462022-12-07 18:31:14 +0100260 static _LIBCPP_HIDE_FROM_ABI constexpr int
Nikolas Klauser1f98ac02024-06-23 22:03:41 +0200261 compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept {
Louis Dionne9783f282023-12-18 14:01:33 -0500262 return std::__constexpr_memcmp(__s1, __s2, __element_count(__n));
Nikolas Klauser72173462022-12-07 18:31:14 +0100263 }
Marshall Clow7dad0bd2018-12-11 04:35:44 +0000264
Nikolas Klauser1f98ac02024-06-23 22:03:41 +0200265 static _LIBCPP_HIDE_FROM_ABI constexpr size_t length(const char_type* __str) noexcept {
Nikolas Klauser29312d32024-04-20 11:40:18 +0200266 return std::__constexpr_strlen(__str);
267 }
Louis Dionne6b77ebd2019-10-23 10:40:15 -0700268
Louis Dionne9783f282023-12-18 14:01:33 -0500269 _LIBCPP_HIDE_FROM_ABI static constexpr const char_type*
Nikolas Klauser1f98ac02024-06-23 22:03:41 +0200270 find(const char_type* __s, size_t __n, const char_type& __a) noexcept {
Nikolas Klauser29312d32024-04-20 11:40:18 +0200271 return std::__constexpr_memchr(__s, __a, __n);
272 }
Marshall Clow7dad0bd2018-12-11 04:35:44 +0000273};
274
Nikolas Klauserba875152024-10-12 09:49:52 +0200275#endif // _LIBCPP_HAS_CHAR8_T
Marshall Clow7dad0bd2018-12-11 04:35:44 +0000276
Marshall Clow053d81c2016-07-21 05:31:24 +0000277template <>
Nikolas Klauseraf9c04f2025-04-09 23:47:57 +0200278struct char_traits<char16_t> : __char_traits_base<char16_t, uint_least16_t, static_cast<uint_least16_t>(0xFFFF)> {
Louis Dionne9783f282023-12-18 14:01:33 -0500279 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 int
280 compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
281 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT;
Nikolas Klauser993a22e2022-06-13 17:54:20 +0200282
Nikolas Klauser29312d32024-04-20 11:40:18 +0200283 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type*
284 find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
285 __identity __proj;
Nikolas Klauser84003242024-04-27 09:51:59 +0200286 const char_type* __match = std::__find(__s, __s + __n, __a, __proj);
Nikolas Klauser29312d32024-04-20 11:40:18 +0200287 if (__match == __s + __n)
288 return nullptr;
289 return __match;
290 }
Marshall Clow053d81c2016-07-21 05:31:24 +0000291};
292
Louis Dionne9783f282023-12-18 14:01:33 -0500293inline _LIBCPP_CONSTEXPR_SINCE_CXX17 int
294char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
295 for (; __n; --__n, ++__s1, ++__s2) {
296 if (lt(*__s1, *__s2))
297 return -1;
298 if (lt(*__s2, *__s1))
299 return 1;
300 }
301 return 0;
Marshall Clow053d81c2016-07-21 05:31:24 +0000302}
303
Louis Dionne9783f282023-12-18 14:01:33 -0500304inline _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT {
305 size_t __len = 0;
306 for (; !eq(*__s, char_type(0)); ++__s)
307 ++__len;
308 return __len;
Marshall Clow053d81c2016-07-21 05:31:24 +0000309}
310
Marshall Clow053d81c2016-07-21 05:31:24 +0000311template <>
Nikolas Klauseraf9c04f2025-04-09 23:47:57 +0200312struct char_traits<char32_t> : __char_traits_base<char32_t, uint_least32_t, static_cast<uint_least32_t>(0xFFFFFFFF)> {
Louis Dionne9783f282023-12-18 14:01:33 -0500313 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 int
314 compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
315 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t length(const char_type* __s) _NOEXCEPT;
Nikolas Klauser29312d32024-04-20 11:40:18 +0200316
Louis Dionne9783f282023-12-18 14:01:33 -0500317 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX17 const char_type*
Nikolas Klauser29312d32024-04-20 11:40:18 +0200318 find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
319 __identity __proj;
Nikolas Klauser84003242024-04-27 09:51:59 +0200320 const char_type* __match = std::__find(__s, __s + __n, __a, __proj);
Nikolas Klauser29312d32024-04-20 11:40:18 +0200321 if (__match == __s + __n)
322 return nullptr;
323 return __match;
324 }
Marshall Clow053d81c2016-07-21 05:31:24 +0000325};
326
Louis Dionne9783f282023-12-18 14:01:33 -0500327inline _LIBCPP_CONSTEXPR_SINCE_CXX17 int
328char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
329 for (; __n; --__n, ++__s1, ++__s2) {
330 if (lt(*__s1, *__s2))
331 return -1;
332 if (lt(*__s2, *__s1))
333 return 1;
334 }
335 return 0;
Marshall Clow053d81c2016-07-21 05:31:24 +0000336}
337
Louis Dionne9783f282023-12-18 14:01:33 -0500338inline _LIBCPP_CONSTEXPR_SINCE_CXX17 size_t char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT {
339 size_t __len = 0;
340 for (; !eq(*__s, char_type(0)); ++__s)
341 ++__len;
342 return __len;
Marshall Clow053d81c2016-07-21 05:31:24 +0000343}
344
Marshall Clow053d81c2016-07-21 05:31:24 +0000345// helper fns for basic_string and string_view
346
347// __str_find
Louis Dionne9783f282023-12-18 14:01:33 -0500348template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500349inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500350__str_find(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
Nikolas Klauser38595fb2025-05-07 16:54:34 +0200351 if (__pos > __sz)
Louis Dionne9783f282023-12-18 14:01:33 -0500352 return __npos;
353 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
354 if (__r == nullptr)
355 return __npos;
356 return static_cast<_SizeT>(__r - __p);
Marshall Clow053d81c2016-07-21 05:31:24 +0000357}
358
Sebastian Pop90705002016-12-30 18:01:36 +0000359template <class _CharT, class _Traits>
Louis Dionne9783f282023-12-18 14:01:33 -0500360_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX14 const _CharT* __search_substring(
361 const _CharT* __first1, const _CharT* __last1, const _CharT* __first2, const _CharT* __last2) _NOEXCEPT {
Sebastian Pop90705002016-12-30 18:01:36 +0000362 // Take advantage of knowing source and pattern lengths.
363 // Stop short when source is smaller than pattern.
364 const ptrdiff_t __len2 = __last2 - __first2;
365 if (__len2 == 0)
366 return __first1;
367
368 ptrdiff_t __len1 = __last1 - __first1;
369 if (__len1 < __len2)
370 return __last1;
371
372 // First element of __first2 is loop invariant.
373 _CharT __f2 = *__first2;
374 while (true) {
375 __len1 = __last1 - __first1;
376 // Check whether __first1 still has at least __len2 bytes.
377 if (__len1 < __len2)
378 return __last1;
379
380 // Find __f2 the first byte matching in __first1.
381 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
Bruce Mitchener527a7fd2020-11-24 12:53:53 -0500382 if (__first1 == nullptr)
Sebastian Pop90705002016-12-30 18:01:36 +0000383 return __last1;
384
385 // It is faster to compare from the first byte of __first1 even if we
386 // already know that it matches the first byte of __first2: this is because
387 // __first2 is most likely aligned, as it is user's "pattern" string, and
388 // __first1 + 1 is most likely not aligned, as the match is in the middle of
389 // the string.
390 if (_Traits::compare(__first1, __first2, __len2) == 0)
391 return __first1;
392
393 ++__first1;
394 }
395}
396
Louis Dionne9783f282023-12-18 14:01:33 -0500397template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500398inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500399__str_find(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
400 if (__pos > __sz)
401 return __npos;
Sebastian Pop90705002016-12-30 18:01:36 +0000402
Louis Dionne9783f282023-12-18 14:01:33 -0500403 if (__n == 0) // There is nothing to search, just return __pos.
404 return __pos;
Sebastian Pop90705002016-12-30 18:01:36 +0000405
Louis Dionne9783f282023-12-18 14:01:33 -0500406 const _CharT* __r = std::__search_substring<_CharT, _Traits>(__p + __pos, __p + __sz, __s, __s + __n);
Sebastian Pop90705002016-12-30 18:01:36 +0000407
Louis Dionne9783f282023-12-18 14:01:33 -0500408 if (__r == __p + __sz)
409 return __npos;
410 return static_cast<_SizeT>(__r - __p);
Marshall Clow053d81c2016-07-21 05:31:24 +0000411}
412
Marshall Clow053d81c2016-07-21 05:31:24 +0000413// __str_rfind
414
Louis Dionne9783f282023-12-18 14:01:33 -0500415template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500416inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500417__str_rfind(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
418 if (__sz < 1)
Marshall Clow053d81c2016-07-21 05:31:24 +0000419 return __npos;
Louis Dionne9783f282023-12-18 14:01:33 -0500420 if (__pos < __sz)
421 ++__pos;
422 else
423 __pos = __sz;
424 for (const _CharT* __ps = __p + __pos; __ps != __p;) {
425 if (_Traits::eq(*--__ps, __c))
426 return static_cast<_SizeT>(__ps - __p);
427 }
428 return __npos;
Marshall Clow053d81c2016-07-21 05:31:24 +0000429}
430
Louis Dionne9783f282023-12-18 14:01:33 -0500431template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500432inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500433__str_rfind(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
434 __pos = std::min(__pos, __sz);
435 if (__n < __sz - __pos)
436 __pos += __n;
437 else
438 __pos = __sz;
439 const _CharT* __r = std::__find_end_classic(__p, __p + __pos, __s, __s + __n, _Traits::eq);
440 if (__n > 0 && __r == __p + __pos)
441 return __npos;
442 return static_cast<_SizeT>(__r - __p);
Marshall Clow053d81c2016-07-21 05:31:24 +0000443}
444
445// __str_find_first_of
Louis Dionne9783f282023-12-18 14:01:33 -0500446template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500447inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500448__str_find_first_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
449 if (__pos >= __sz || __n == 0)
450 return __npos;
451 const _CharT* __r = std::__find_first_of_ce(__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq);
452 if (__r == __p + __sz)
453 return __npos;
454 return static_cast<_SizeT>(__r - __p);
Marshall Clow053d81c2016-07-21 05:31:24 +0000455}
456
Marshall Clow053d81c2016-07-21 05:31:24 +0000457// __str_find_last_of
Louis Dionne9783f282023-12-18 14:01:33 -0500458template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500459inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500460__str_find_last_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
461 if (__n != 0) {
462 if (__pos < __sz)
463 ++__pos;
464 else
465 __pos = __sz;
466 for (const _CharT* __ps = __p + __pos; __ps != __p;) {
467 const _CharT* __r = _Traits::find(__s, __n, *--__ps);
468 if (__r)
469 return static_cast<_SizeT>(__ps - __p);
Marshall Clow053d81c2016-07-21 05:31:24 +0000470 }
Louis Dionne9783f282023-12-18 14:01:33 -0500471 }
472 return __npos;
Marshall Clow053d81c2016-07-21 05:31:24 +0000473}
474
Marshall Clow053d81c2016-07-21 05:31:24 +0000475// __str_find_first_not_of
Louis Dionne9783f282023-12-18 14:01:33 -0500476template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500477inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500478__str_find_first_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
479 if (__pos < __sz) {
480 const _CharT* __pe = __p + __sz;
481 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
482 if (_Traits::find(__s, __n, *__ps) == nullptr)
483 return static_cast<_SizeT>(__ps - __p);
484 }
485 return __npos;
Marshall Clow053d81c2016-07-21 05:31:24 +0000486}
487
Louis Dionne9783f282023-12-18 14:01:33 -0500488template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500489inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500490__str_find_first_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
491 if (__pos < __sz) {
492 const _CharT* __pe = __p + __sz;
493 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
494 if (!_Traits::eq(*__ps, __c))
495 return static_cast<_SizeT>(__ps - __p);
496 }
497 return __npos;
Marshall Clow053d81c2016-07-21 05:31:24 +0000498}
499
Marshall Clow053d81c2016-07-21 05:31:24 +0000500// __str_find_last_not_of
Louis Dionne9783f282023-12-18 14:01:33 -0500501template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500502inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500503__str_find_last_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
504 if (__pos < __sz)
505 ++__pos;
506 else
507 __pos = __sz;
508 for (const _CharT* __ps = __p + __pos; __ps != __p;)
509 if (_Traits::find(__s, __n, *--__ps) == nullptr)
510 return static_cast<_SizeT>(__ps - __p);
511 return __npos;
Marshall Clow053d81c2016-07-21 05:31:24 +0000512}
513
Louis Dionne9783f282023-12-18 14:01:33 -0500514template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
Louis Dionne4c198542023-12-04 10:25:14 -0500515inline _SizeT _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI
Louis Dionne9783f282023-12-18 14:01:33 -0500516__str_find_last_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
517 if (__pos < __sz)
518 ++__pos;
519 else
520 __pos = __sz;
521 for (const _CharT* __ps = __p + __pos; __ps != __p;)
522 if (!_Traits::eq(*--__ps, __c))
523 return static_cast<_SizeT>(__ps - __p);
524 return __npos;
Marshall Clow053d81c2016-07-21 05:31:24 +0000525}
526
Louis Dionne9783f282023-12-18 14:01:33 -0500527template <class _Ptr>
528inline _LIBCPP_HIDE_FROM_ABI size_t __do_string_hash(_Ptr __p, _Ptr __e) {
529 typedef typename iterator_traits<_Ptr>::value_type value_type;
Nikolas Klauser17d05692025-03-27 13:19:59 +0100530 return std::__hash_memory(__p, (__e - __p) * sizeof(value_type));
Marshall Clow053d81c2016-07-21 05:31:24 +0000531}
532
Marshall Clow053d81c2016-07-21 05:31:24 +0000533_LIBCPP_END_NAMESPACE_STD
534
Eric Fiseliera016efb2017-05-31 22:07:49 +0000535_LIBCPP_POP_MACROS
536
Nikolas Klauser976f3702022-06-06 23:35:24 +0200537#endif // _LIBCPP___STRING_CHAR_TRAITS_H