Warning: This file is not a C or C++ file. It does not have highlighting.

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___CXX03___STRING_CHAR_TRAITS_H
10#define _LIBCPP___CXX03___STRING_CHAR_TRAITS_H
11
12#include <__cxx03/__algorithm/fill_n.h>
13#include <__cxx03/__algorithm/find.h>
14#include <__cxx03/__algorithm/find_end.h>
15#include <__cxx03/__algorithm/find_first_of.h>
16#include <__cxx03/__algorithm/min.h>
17#include <__cxx03/__assert>
18#include <__cxx03/__config>
19#include <__cxx03/__functional/hash.h>
20#include <__cxx03/__functional/identity.h>
21#include <__cxx03/__iterator/iterator_traits.h>
22#include <__cxx03/__string/constexpr_c_functions.h>
23#include <__cxx03/__type_traits/is_constant_evaluated.h>
24#include <__cxx03/__utility/is_pointer_in_range.h>
25#include <__cxx03/cstddef>
26#include <__cxx03/cstdint>
27#include <__cxx03/cstdio>
28#include <__cxx03/iosfwd>
29
30#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
31# include <__cxx03/cwchar> // for wmemcpy
32#endif
33
34#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
35# pragma GCC system_header
36#endif
37
38_LIBCPP_PUSH_MACROS
39#include <__cxx03/__undef_macros>
40
41_LIBCPP_BEGIN_NAMESPACE_STD
42
43template <class _CharT>
44struct char_traits;
45/*
46The Standard does not define the base template for char_traits because it is impossible to provide
47a correct definition for arbitrary character types. Instead, it requires implementations to provide
48specializations for predefined character types like `char`, `wchar_t` and others. We provide this as
49exposition-only to document what members a char_traits specialization should provide:
50{
51 using char_type = _CharT;
52 using int_type = ...;
53 using off_type = ...;
54 using pos_type = ...;
55 using state_type = ...;
56
57 static void assign(char_type&, const char_type&);
58 static bool eq(char_type, char_type);
59 static bool lt(char_type, char_type);
60
61 static int compare(const char_type*, const char_type*, size_t);
62 static size_t length(const char_type*);
63 static const char_type* find(const char_type*, size_t, const char_type&);
64 static char_type* move(char_type*, const char_type*, size_t);
65 static char_type* copy(char_type*, const char_type*, size_t);
66 static char_type* assign(char_type*, size_t, char_type);
67
68 static int_type not_eof(int_type);
69 static char_type to_char_type(int_type);
70 static int_type to_int_type(char_type);
71 static bool eq_int_type(int_type, int_type);
72 static int_type eof();
73};
74*/
75
76// char_traits<char>
77
78template <>
79struct _LIBCPP_TEMPLATE_VIS char_traits<char> {
80 using char_type = char;
81 using int_type = int;
82 using off_type = streamoff;
83 using pos_type = streampos;
84 using state_type = mbstate_t;
85
86 static inline _LIBCPP_HIDE_FROM_ABI void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT { __c1 = __c2; }
87
88 // TODO: Make this _LIBCPP_HIDE_FROM_ABI
89 static inline _LIBCPP_HIDDEN bool eq(char_type __c1, char_type __c2) _NOEXCEPT { return __c1 == __c2; }
90 static inline _LIBCPP_HIDE_FROM_ABI bool lt(char_type __c1, char_type __c2) _NOEXCEPT {
91 return (unsigned char)__c1 < (unsigned char)__c2;
92 }
93
94 // __constexpr_memcmp requires a trivially lexicographically comparable type, but char is not when char is a signed
95 // type
96 static _LIBCPP_HIDE_FROM_ABI int compare(const char_type* __lhs, const char_type* __rhs, size_t __count) _NOEXCEPT {
97 if (__libcpp_is_constant_evaluated()) {
98#ifdef _LIBCPP_COMPILER_CLANG_BASED
99 return __builtin_memcmp(__lhs, __rhs, __count);
100#else
101 while (__count != 0) {
102 if (lt(*__lhs, *__rhs))
103 return -1;
104 if (lt(*__rhs, *__lhs))
105 return 1;
106
107 __count -= sizeof(char_type);
108 ++__lhs;
109 ++__rhs;
110 }
111 return 0;
112#endif // _LIBCPP_COMPILER_CLANG_BASED
113 } else {
114 return __builtin_memcmp(__lhs, __rhs, __count);
115 }
116 }
117
118 static inline _LIBCPP_HIDE_FROM_ABI size_t length(const char_type* __s) _NOEXCEPT {
119 return std::__constexpr_strlen(__s);
120 }
121
122 static _LIBCPP_HIDE_FROM_ABI const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
123 if (__n == 0)
124 return nullptr;
125 return std::__constexpr_memchr(__s, __a, __n);
126 }
127
128 static inline _LIBCPP_HIDE_FROM_ABI char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
129 return std::__constexpr_memmove(__s1, __s2, __element_count(__n));
130 }
131
132 static inline _LIBCPP_HIDE_FROM_ABI char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
133 _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__s1, __s1 + __n, __s2),
134 "char_traits::copy: source and destination ranges overlap");
135 std::__constexpr_memmove(__s1, __s2, __element_count(__n));
136 return __s1;
137 }
138
139 static inline _LIBCPP_HIDE_FROM_ABI char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT {
140 std::fill_n(__s, __n, __a);
141 return __s;
142 }
143
144 static inline _LIBCPP_HIDE_FROM_ABI int_type not_eof(int_type __c) _NOEXCEPT {
145 return eq_int_type(__c, eof()) ? ~eof() : __c;
146 }
147 static inline _LIBCPP_HIDE_FROM_ABI char_type to_char_type(int_type __c) _NOEXCEPT { return char_type(__c); }
148 static inline _LIBCPP_HIDE_FROM_ABI int_type to_int_type(char_type __c) _NOEXCEPT {
149 return int_type((unsigned char)__c);
150 }
151 static inline _LIBCPP_HIDE_FROM_ABI bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT { return __c1 == __c2; }
152 static inline _LIBCPP_HIDE_FROM_ABI int_type eof() _NOEXCEPT { return int_type(EOF); }
153};
154
155template <class _CharT, class _IntT, _IntT _EOFVal>
156struct __char_traits_base {
157 using char_type = _CharT;
158 using int_type = _IntT;
159 using off_type = streamoff;
160 using state_type = mbstate_t;
161
162 // There are different aliases for the different char types, but they are all aliases to this type
163 using pos_type = fpos<mbstate_t>;
164
165 _LIBCPP_HIDE_FROM_ABI static inline void assign(char_type& __lhs, const char_type& __rhs) _NOEXCEPT { __lhs = __rhs; }
166
167 _LIBCPP_HIDE_FROM_ABI static bool eq(char_type __lhs, char_type __rhs) _NOEXCEPT { return __lhs == __rhs; }
168
169 _LIBCPP_HIDE_FROM_ABI static bool lt(char_type __lhs, char_type __rhs) _NOEXCEPT { return __lhs < __rhs; }
170
171 _LIBCPP_HIDE_FROM_ABI static char_type* move(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT {
172 return std::__constexpr_memmove(__dest, __src, __element_count(__n));
173 }
174
175 _LIBCPP_HIDE_FROM_ABI static char_type* copy(char_type* __dest, const char_type* __src, size_t __n) _NOEXCEPT {
176 _LIBCPP_ASSERT_NON_OVERLAPPING_RANGES(!std::__is_pointer_in_range(__dest, __dest + __n, __src),
177 "char_traits::copy: source and destination ranges overlap");
178 return std::__constexpr_memmove(__dest, __src, __element_count(__n));
179 }
180
181 _LIBCPP_HIDE_FROM_ABI static char_type* assign(char_type* __str, size_t __n, char_type __fill_char) _NOEXCEPT {
182 std::fill_n(__str, __n, __fill_char);
183 return __str;
184 }
185
186 _LIBCPP_HIDE_FROM_ABI static char_type to_char_type(int_type __c) _NOEXCEPT { return char_type(__c); }
187
188 _LIBCPP_HIDE_FROM_ABI static int_type to_int_type(char_type __c) _NOEXCEPT { return int_type(__c); }
189
190 _LIBCPP_HIDE_FROM_ABI static bool eq_int_type(int_type __lhs, int_type __rhs) _NOEXCEPT { return __lhs == __rhs; }
191
192 _LIBCPP_HIDE_FROM_ABI static int_type eof() _NOEXCEPT { return _EOFVal; }
193
194 _LIBCPP_HIDE_FROM_ABI static int_type not_eof(int_type __c) _NOEXCEPT {
195 return eq_int_type(__c, eof()) ? static_cast<int_type>(~eof()) : __c;
196 }
197};
198
199// char_traits<wchar_t>
200
201#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
202template <>
203struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t> : __char_traits_base<wchar_t, wint_t, static_cast<wint_t>(WEOF)> {
204 static _LIBCPP_HIDE_FROM_ABI int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
205 if (__n == 0)
206 return 0;
207 return std::__constexpr_wmemcmp(__s1, __s2, __n);
208 }
209
210 static _LIBCPP_HIDE_FROM_ABI size_t length(const char_type* __s) _NOEXCEPT { return std::__constexpr_wcslen(__s); }
211
212 static _LIBCPP_HIDE_FROM_ABI const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
213 if (__n == 0)
214 return nullptr;
215 return std::__constexpr_wmemchr(__s, __a, __n);
216 }
217};
218#endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS
219
220#ifndef _LIBCPP_HAS_NO_CHAR8_T
221
222template <>
223struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
224 : __char_traits_base<char8_t, unsigned int, static_cast<unsigned int>(EOF)> {
225 static _LIBCPP_HIDE_FROM_ABI constexpr int
226 compare(const char_type* __s1, const char_type* __s2, size_t __n) noexcept {
227 return std::__constexpr_memcmp(__s1, __s2, __element_count(__n));
228 }
229
230 static _LIBCPP_HIDE_FROM_ABI constexpr size_t length(const char_type* __str) noexcept {
231 return std::__constexpr_strlen(__str);
232 }
233
234 _LIBCPP_HIDE_FROM_ABI static constexpr const char_type*
235 find(const char_type* __s, size_t __n, const char_type& __a) noexcept {
236 return std::__constexpr_memchr(__s, __a, __n);
237 }
238};
239
240#endif // _LIBCPP_HAS_NO_CHAR8_T
241
242template <>
243struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
244 : __char_traits_base<char16_t, uint_least16_t, static_cast<uint_least16_t>(0xFFFF)> {
245 _LIBCPP_HIDE_FROM_ABI static int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
246 _LIBCPP_HIDE_FROM_ABI static size_t length(const char_type* __s) _NOEXCEPT;
247
248 _LIBCPP_HIDE_FROM_ABI static const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
249 __identity __proj;
250 const char_type* __match = std::__find(__s, __s + __n, __a, __proj);
251 if (__match == __s + __n)
252 return nullptr;
253 return __match;
254 }
255};
256
257inline int char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
258 for (; __n; --__n, ++__s1, ++__s2) {
259 if (lt(*__s1, *__s2))
260 return -1;
261 if (lt(*__s2, *__s1))
262 return 1;
263 }
264 return 0;
265}
266
267inline size_t char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT {
268 size_t __len = 0;
269 for (; !eq(*__s, char_type(0)); ++__s)
270 ++__len;
271 return __len;
272}
273
274template <>
275struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
276 : __char_traits_base<char32_t, uint_least32_t, static_cast<uint_least32_t>(0xFFFFFFFF)> {
277 _LIBCPP_HIDE_FROM_ABI static int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
278 _LIBCPP_HIDE_FROM_ABI static size_t length(const char_type* __s) _NOEXCEPT;
279
280 _LIBCPP_HIDE_FROM_ABI static const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
281 __identity __proj;
282 const char_type* __match = std::__find(__s, __s + __n, __a, __proj);
283 if (__match == __s + __n)
284 return nullptr;
285 return __match;
286 }
287};
288
289inline int char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
290 for (; __n; --__n, ++__s1, ++__s2) {
291 if (lt(*__s1, *__s2))
292 return -1;
293 if (lt(*__s2, *__s1))
294 return 1;
295 }
296 return 0;
297}
298
299inline size_t char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT {
300 size_t __len = 0;
301 for (; !eq(*__s, char_type(0)); ++__s)
302 ++__len;
303 return __len;
304}
305
306// helper fns for basic_string and string_view
307
308// __str_find
309template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
310inline _SizeT _LIBCPP_HIDE_FROM_ABI __str_find(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
311 if (__pos >= __sz)
312 return __npos;
313 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
314 if (__r == nullptr)
315 return __npos;
316 return static_cast<_SizeT>(__r - __p);
317}
318
319template <class _CharT, class _Traits>
320_LIBCPP_HIDE_FROM_ABI inline const _CharT* __search_substring(
321 const _CharT* __first1, const _CharT* __last1, const _CharT* __first2, const _CharT* __last2) _NOEXCEPT {
322 // Take advantage of knowing source and pattern lengths.
323 // Stop short when source is smaller than pattern.
324 const ptrdiff_t __len2 = __last2 - __first2;
325 if (__len2 == 0)
326 return __first1;
327
328 ptrdiff_t __len1 = __last1 - __first1;
329 if (__len1 < __len2)
330 return __last1;
331
332 // First element of __first2 is loop invariant.
333 _CharT __f2 = *__first2;
334 while (true) {
335 __len1 = __last1 - __first1;
336 // Check whether __first1 still has at least __len2 bytes.
337 if (__len1 < __len2)
338 return __last1;
339
340 // Find __f2 the first byte matching in __first1.
341 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
342 if (__first1 == nullptr)
343 return __last1;
344
345 // It is faster to compare from the first byte of __first1 even if we
346 // already know that it matches the first byte of __first2: this is because
347 // __first2 is most likely aligned, as it is user's "pattern" string, and
348 // __first1 + 1 is most likely not aligned, as the match is in the middle of
349 // the string.
350 if (_Traits::compare(__first1, __first2, __len2) == 0)
351 return __first1;
352
353 ++__first1;
354 }
355}
356
357template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
358inline _SizeT _LIBCPP_HIDE_FROM_ABI
359__str_find(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
360 if (__pos > __sz)
361 return __npos;
362
363 if (__n == 0) // There is nothing to search, just return __pos.
364 return __pos;
365
366 const _CharT* __r = std::__search_substring<_CharT, _Traits>(__p + __pos, __p + __sz, __s, __s + __n);
367
368 if (__r == __p + __sz)
369 return __npos;
370 return static_cast<_SizeT>(__r - __p);
371}
372
373// __str_rfind
374
375template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
376inline _SizeT _LIBCPP_HIDE_FROM_ABI __str_rfind(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
377 if (__sz < 1)
378 return __npos;
379 if (__pos < __sz)
380 ++__pos;
381 else
382 __pos = __sz;
383 for (const _CharT* __ps = __p + __pos; __ps != __p;) {
384 if (_Traits::eq(*--__ps, __c))
385 return static_cast<_SizeT>(__ps - __p);
386 }
387 return __npos;
388}
389
390template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
391inline _SizeT _LIBCPP_HIDE_FROM_ABI
392__str_rfind(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
393 __pos = std::min(__pos, __sz);
394 if (__n < __sz - __pos)
395 __pos += __n;
396 else
397 __pos = __sz;
398 const _CharT* __r = std::__find_end_classic(__p, __p + __pos, __s, __s + __n, _Traits::eq);
399 if (__n > 0 && __r == __p + __pos)
400 return __npos;
401 return static_cast<_SizeT>(__r - __p);
402}
403
404// __str_find_first_of
405template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
406inline _SizeT _LIBCPP_HIDE_FROM_ABI
407__str_find_first_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
408 if (__pos >= __sz || __n == 0)
409 return __npos;
410 const _CharT* __r = std::__find_first_of_ce(__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq);
411 if (__r == __p + __sz)
412 return __npos;
413 return static_cast<_SizeT>(__r - __p);
414}
415
416// __str_find_last_of
417template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
418inline _SizeT _LIBCPP_HIDE_FROM_ABI
419__str_find_last_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
420 if (__n != 0) {
421 if (__pos < __sz)
422 ++__pos;
423 else
424 __pos = __sz;
425 for (const _CharT* __ps = __p + __pos; __ps != __p;) {
426 const _CharT* __r = _Traits::find(__s, __n, *--__ps);
427 if (__r)
428 return static_cast<_SizeT>(__ps - __p);
429 }
430 }
431 return __npos;
432}
433
434// __str_find_first_not_of
435template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
436inline _SizeT _LIBCPP_HIDE_FROM_ABI
437__str_find_first_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
438 if (__pos < __sz) {
439 const _CharT* __pe = __p + __sz;
440 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
441 if (_Traits::find(__s, __n, *__ps) == nullptr)
442 return static_cast<_SizeT>(__ps - __p);
443 }
444 return __npos;
445}
446
447template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
448inline _SizeT _LIBCPP_HIDE_FROM_ABI
449__str_find_first_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
450 if (__pos < __sz) {
451 const _CharT* __pe = __p + __sz;
452 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
453 if (!_Traits::eq(*__ps, __c))
454 return static_cast<_SizeT>(__ps - __p);
455 }
456 return __npos;
457}
458
459// __str_find_last_not_of
460template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
461inline _SizeT _LIBCPP_HIDE_FROM_ABI
462__str_find_last_not_of(const _CharT* __p, _SizeT __sz, const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT {
463 if (__pos < __sz)
464 ++__pos;
465 else
466 __pos = __sz;
467 for (const _CharT* __ps = __p + __pos; __ps != __p;)
468 if (_Traits::find(__s, __n, *--__ps) == nullptr)
469 return static_cast<_SizeT>(__ps - __p);
470 return __npos;
471}
472
473template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>
474inline _SizeT _LIBCPP_HIDE_FROM_ABI
475__str_find_last_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {
476 if (__pos < __sz)
477 ++__pos;
478 else
479 __pos = __sz;
480 for (const _CharT* __ps = __p + __pos; __ps != __p;)
481 if (!_Traits::eq(*--__ps, __c))
482 return static_cast<_SizeT>(__ps - __p);
483 return __npos;
484}
485
486template <class _Ptr>
487inline _LIBCPP_HIDE_FROM_ABI size_t __do_string_hash(_Ptr __p, _Ptr __e) {
488 typedef typename iterator_traits<_Ptr>::value_type value_type;
489 return __murmur2_or_cityhash<size_t>()(__p, (__e - __p) * sizeof(value_type));
490}
491
492_LIBCPP_END_NAMESPACE_STD
493
494_LIBCPP_POP_MACROS
495
496#endif // _LIBCPP___CXX03___STRING_CHAR_TRAITS_H
497

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__cxx03/__string/char_traits.h