497 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___CXX03___STRING_CHAR_TRAITS_H10#define _LIBCPP___CXX03___STRING_CHAR_TRAITS_H11 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_CHARACTERS31# include <__cxx03/cwchar> // for wmemcpy32#endif33 34#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)35# pragma GCC system_header36#endif37 38_LIBCPP_PUSH_MACROS39#include <__cxx03/__undef_macros>40 41_LIBCPP_BEGIN_NAMESPACE_STD42 43template <class _CharT>44struct char_traits;45/*46The Standard does not define the base template for char_traits because it is impossible to provide47a correct definition for arbitrary character types. Instead, it requires implementations to provide48specializations for predefined character types like `char`, `wchar_t` and others. We provide this as49exposition-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_ABI89 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 signed95 // type96 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_BASED99 return __builtin_memcmp(__lhs, __rhs, __count);100#else101 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_BASED113 } 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 type163 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_CHARACTERS202template <>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_CHARACTERS219 220#ifndef _LIBCPP_HAS_NO_CHAR8_T221 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 int226 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_T241 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_view307 308// __str_find309template <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 we346 // already know that it matches the first byte of __first2: this is because347 // __first2 is most likely aligned, as it is user's "pattern" string, and348 // __first1 + 1 is most likely not aligned, as the match is in the middle of349 // 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_ABI359__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_rfind374 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 else382 __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_ABI392__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 else397 __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_of405template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>406inline _SizeT _LIBCPP_HIDE_FROM_ABI407__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_of417template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>418inline _SizeT _LIBCPP_HIDE_FROM_ABI419__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 else424 __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_of435template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>436inline _SizeT _LIBCPP_HIDE_FROM_ABI437__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_ABI449__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_of460template <class _CharT, class _SizeT, class _Traits, _SizeT __npos>461inline _SizeT _LIBCPP_HIDE_FROM_ABI462__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 else466 __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_ABI475__str_find_last_not_of(const _CharT* __p, _SizeT __sz, _CharT __c, _SizeT __pos) _NOEXCEPT {476 if (__pos < __sz)477 ++__pos;478 else479 __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_STD493 494_LIBCPP_POP_MACROS495 496#endif // _LIBCPP___CXX03___STRING_CHAR_TRAITS_H497