blob: 13ff7b35e47dbb4afbd7f4eee6b6805df1cfa492 [file] [log] [blame]
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001// -*- C++ -*-
Louis Dionne9bd93882021-11-17 16:25:01 -05002//===----------------------------------------------------------------------===//
Marshall Clowdf63a6d2016-07-21 05:31:24 +00003//
Chandler Carruth7642bb12019-01-19 08:50:56 +00004// 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
Marshall Clowdf63a6d2016-07-21 05:31:24 +00007//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___STRING
11#define _LIBCPP___STRING
12
Marshall Clowdf63a6d2016-07-21 05:31:24 +000013#include <__config>
Christopher Di Bella55d7a822021-07-01 09:25:35 -040014#include <__algorithm/copy.h>
15#include <__algorithm/copy_backward.h>
16#include <__algorithm/copy_n.h>
17#include <__algorithm/fill_n.h>
18#include <__algorithm/find_first_of.h>
19#include <__algorithm/find_end.h>
20#include <__algorithm/min.h>
21#include <__functional/hash.h> // for __murmur2_or_cityhash
22#include <__iterator/iterator_traits.h>
23#include <cstdio> // for EOF
24#include <cstdint> // for uint_least16_t
25#include <cstring> // for memcpy
Christopher Di Bella55d7a822021-07-01 09:25:35 -040026#include <type_traits> // for __libcpp_is_constant_evaluated
Louis Dionne89258142021-08-23 15:32:36 -040027#include <iosfwd> // for streampos & friends
28
29#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
30# include <cwchar> // for wmemcpy
31#endif
Marshall Clowdf63a6d2016-07-21 05:31:24 +000032
Marshall Clowdf63a6d2016-07-21 05:31:24 +000033#include <__debug>
34
35#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
36#pragma GCC system_header
37#endif
38
Eric Fiselierf4433a32017-05-31 22:07:49 +000039_LIBCPP_PUSH_MACROS
40#include <__undef_macros>
41
42
Marshall Clowdf63a6d2016-07-21 05:31:24 +000043_LIBCPP_BEGIN_NAMESPACE_STD
44
Martijn Vels1e63ba02020-02-19 16:27:50 -050045// The extern template ABI lists are kept outside of <string> to improve the
46// readability of that header. We maintain 2 ABI lists:
47// - _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST
48// - _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST
49// As the name implies, the ABI lists define the V1 (Stable) and unstable ABI.
50//
51// For unstable, we may explicitly remove function that are external in V1,
52// and add (new) external functions to better control inlining and compiler
53// optimization opportunities.
54//
55// For stable, the ABI list should rarely change, except for adding new
56// functions supporting new c++ version / API changes. Typically entries
57// must never be removed from the stable list.
58#define _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
59 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*, size_type)) \
60 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type const*, size_type, size_type) const) \
61 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type, size_type)) \
62 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&)) \
63 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*)) \
Arthur O'Dwyer07b22492020-11-27 11:02:06 -050064 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, allocator<_CharType> const&)) \
Martijn Vels1e63ba02020-02-19 16:27:50 -050065 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_not_of(value_type const*, size_type, size_type) const) \
66 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::~basic_string()) \
67 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_not_of(value_type const*, size_type, size_type) const) \
68 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, size_type, value_type)) \
69 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(value_type)) \
70 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type)) \
71 _Func(_LIBCPP_FUNC_VIS const _CharType& basic_string<_CharType>::at(size_type) const) \
72 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*, size_type)) \
73 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_of(value_type const*, size_type, size_type) const) \
74 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, size_type, value_type)) \
75 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*, size_type)) \
76 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::reserve(size_type)) \
77 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*, size_type)) \
78 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(basic_string const&, size_type, size_type)) \
79 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::copy(value_type*, size_type, size_type) const) \
Arthur O'Dwyer07b22492020-11-27 11:02:06 -050080 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, size_type, size_type, allocator<_CharType> const&)) \
Martijn Vels1e63ba02020-02-19 16:27:50 -050081 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type, size_type) const) \
82 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(size_type, value_type)) \
83 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*)) \
84 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_of(value_type const*, size_type, size_type) const) \
85 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \
86 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by_and_replace(size_type, size_type, size_type, size_type, size_type, size_type, value_type const*)) \
87 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::push_back(value_type)) \
88 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(size_type, value_type)) \
89 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type, size_type) const) \
90 _Func(_LIBCPP_FUNC_VIS const basic_string<_CharType>::size_type basic_string<_CharType>::npos) \
91 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(size_type, value_type)) \
92 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::erase(size_type, size_type)) \
93 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(basic_string const&, size_type, size_type)) \
94 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(value_type const*) const) \
95 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*) const) \
96 _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \
97 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*)) \
98 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type const*, size_type, size_type) const) \
99 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, basic_string const&, size_type, size_type) const) \
100 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \
101 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(basic_string const&)) \
102 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \
103 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \
104 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \
105 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \
106 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type))
107
108#define _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500109 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*, size_type)) \
110 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type const*, size_type, size_type) const) \
111 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type, size_type)) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500112 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*)) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500113 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_not_of(value_type const*, size_type, size_type) const) \
114 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::~basic_string()) \
115 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_not_of(value_type const*, size_type, size_type) const) \
116 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, size_type, value_type)) \
117 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(value_type)) \
118 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type)) \
Martijn Vels5e7c9752020-03-04 17:52:46 -0500119 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init_copy_ctor_external(value_type const*, size_type)) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500120 _Func(_LIBCPP_FUNC_VIS const _CharType& basic_string<_CharType>::at(size_type) const) \
121 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*, size_type)) \
122 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_of(value_type const*, size_type, size_type) const) \
123 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, size_type, value_type)) \
Martijn Velsda7d94f2020-06-19 14:24:03 -0400124 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_external(value_type const*, size_type)) \
125 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_external(value_type const*)) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500126 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::reserve(size_type)) \
127 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*, size_type)) \
128 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(basic_string const&, size_type, size_type)) \
129 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::copy(value_type*, size_type, size_type) const) \
Arthur O'Dwyer07b22492020-11-27 11:02:06 -0500130 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, size_type, size_type, allocator<_CharType> const&)) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500131 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type, size_type) const) \
132 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(size_type, value_type)) \
133 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*)) \
134 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_of(value_type const*, size_type, size_type) const) \
135 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \
136 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by_and_replace(size_type, size_type, size_type, size_type, size_type, size_type, value_type const*)) \
Martijn Velsb6a08b62020-04-10 18:36:31 -0400137 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_no_alias<false>(value_type const*, size_type)) \
138 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_no_alias<true>(value_type const*, size_type)) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500139 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::push_back(value_type)) \
140 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(size_type, value_type)) \
141 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type, size_type) const) \
142 _Func(_LIBCPP_FUNC_VIS const basic_string<_CharType>::size_type basic_string<_CharType>::npos) \
143 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(size_type, value_type)) \
Martijn Velsa81fc792020-02-26 13:25:43 -0500144 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__erase_external_with_move(size_type, size_type)) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500145 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(basic_string const&, size_type, size_type)) \
146 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(value_type const*) const) \
147 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*) const) \
148 _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500149 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type const*, size_type, size_type) const) \
150 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, basic_string const&, size_type, size_type) const) \
151 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \
Eric Fiselier5dcce5c2020-01-15 17:12:09 -0500152 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \
153 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \
154 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \
155 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \
156 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type))
157
158
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000159// char_traits
160
161template <class _CharT>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000162struct _LIBCPP_TEMPLATE_VIS char_traits
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000163{
164 typedef _CharT char_type;
165 typedef int int_type;
166 typedef streamoff off_type;
167 typedef streampos pos_type;
168 typedef mbstate_t state_type;
169
Marshall Clow951035b2017-01-12 04:37:14 +0000170 static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14
171 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000172 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
173 {return __c1 == __c2;}
174 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
175 {return __c1 < __c2;}
176
Marshall Clow951035b2017-01-12 04:37:14 +0000177 static _LIBCPP_CONSTEXPR_AFTER_CXX14
178 int compare(const char_type* __s1, const char_type* __s2, size_t __n);
179 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
180 size_t length(const char_type* __s);
181 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
182 const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
Michael Parkb5f44472019-11-08 13:42:26 +0000183 static _LIBCPP_CONSTEXPR_AFTER_CXX17
184 char_type* move(char_type* __s1, const char_type* __s2, size_t __n);
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000185 _LIBCPP_INLINE_VISIBILITY
Michael Parkb5f44472019-11-08 13:42:26 +0000186 static _LIBCPP_CONSTEXPR_AFTER_CXX17
187 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n);
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000188 _LIBCPP_INLINE_VISIBILITY
Michael Parkb5f44472019-11-08 13:42:26 +0000189 static _LIBCPP_CONSTEXPR_AFTER_CXX17
190 char_type* assign(char_type* __s, size_t __n, char_type __a);
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000191
192 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
193 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
194 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
195 {return char_type(__c);}
196 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
197 {return int_type(__c);}
198 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
199 {return __c1 == __c2;}
200 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
201 {return int_type(EOF);}
202};
203
204template <class _CharT>
Marshall Clow951035b2017-01-12 04:37:14 +0000205_LIBCPP_CONSTEXPR_AFTER_CXX14 int
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000206char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
207{
208 for (; __n; --__n, ++__s1, ++__s2)
209 {
210 if (lt(*__s1, *__s2))
211 return -1;
212 if (lt(*__s2, *__s1))
213 return 1;
214 }
215 return 0;
216}
217
218template <class _CharT>
219inline
Marshall Clow951035b2017-01-12 04:37:14 +0000220_LIBCPP_CONSTEXPR_AFTER_CXX14 size_t
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000221char_traits<_CharT>::length(const char_type* __s)
222{
223 size_t __len = 0;
224 for (; !eq(*__s, char_type(0)); ++__s)
225 ++__len;
226 return __len;
227}
228
229template <class _CharT>
230inline
Marshall Clow951035b2017-01-12 04:37:14 +0000231_LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT*
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000232char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
233{
234 for (; __n; --__n)
235 {
236 if (eq(*__s, __a))
237 return __s;
238 ++__s;
239 }
Bruce Mitchener170d8972020-11-24 12:53:53 -0500240 return nullptr;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000241}
242
243template <class _CharT>
Michael Parkb5f44472019-11-08 13:42:26 +0000244_LIBCPP_CONSTEXPR_AFTER_CXX17 _CharT*
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000245char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
246{
Michael Parkb5f44472019-11-08 13:42:26 +0000247 if (__n == 0) return __s1;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000248 char_type* __r = __s1;
249 if (__s1 < __s2)
250 {
251 for (; __n; --__n, ++__s1, ++__s2)
252 assign(*__s1, *__s2);
253 }
254 else if (__s2 < __s1)
255 {
256 __s1 += __n;
257 __s2 += __n;
258 for (; __n; --__n)
259 assign(*--__s1, *--__s2);
260 }
261 return __r;
262}
263
264template <class _CharT>
Michael Parkb5f44472019-11-08 13:42:26 +0000265inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000266_CharT*
267char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
268{
Arthur O'Dwyere9a55122021-04-20 22:24:24 -0400269 if (!__libcpp_is_constant_evaluated()) {
270 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
271 }
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000272 char_type* __r = __s1;
273 for (; __n; --__n, ++__s1, ++__s2)
274 assign(*__s1, *__s2);
275 return __r;
276}
277
278template <class _CharT>
Michael Parkb5f44472019-11-08 13:42:26 +0000279inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000280_CharT*
281char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
282{
283 char_type* __r = __s;
284 for (; __n; --__n, ++__s)
285 assign(*__s, __a);
286 return __r;
287}
288
Michael Parkb5f44472019-11-08 13:42:26 +0000289// constexpr versions of move/copy/assign.
290
291template <class _CharT>
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500292static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Arthur O'Dwyer0eedd172021-12-21 08:33:30 -0500293_CharT* __copy_constexpr(_CharT* __dest, const _CharT* __source, size_t __n) _NOEXCEPT
Michael Parkb5f44472019-11-08 13:42:26 +0000294{
Nikolas Klauserf87ca902021-12-21 11:22:50 +0100295 _LIBCPP_ASSERT(__libcpp_is_constant_evaluated(), "__copy_constexpr() should always be constant evaluated");
Arthur O'Dwyer0eedd172021-12-21 08:33:30 -0500296 _VSTD::copy_n(__source, __n, __dest);
297 return __dest;
Michael Parkb5f44472019-11-08 13:42:26 +0000298}
299
300template <class _CharT>
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500301static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Nikolas Klauserf87ca902021-12-21 11:22:50 +0100302_CharT* __move_constexpr(_CharT* __dest, const _CharT* __source, size_t __n) _NOEXCEPT
Michael Parkb5f44472019-11-08 13:42:26 +0000303{
Nikolas Klauserf87ca902021-12-21 11:22:50 +0100304 _LIBCPP_ASSERT(__libcpp_is_constant_evaluated(), "__move_constexpr() should always be constant evaluated");
305 if (__n == 0)
306 return __dest;
307 _CharT* __allocation = new _CharT[__n];
308 _VSTD::__copy_constexpr(__allocation, __source, __n);
309 _VSTD::__copy_constexpr(__dest, static_cast<const _CharT*>(__allocation), __n);
310 delete[] __allocation;
311 return __dest;
Michael Parkb5f44472019-11-08 13:42:26 +0000312}
313
314template <class _CharT>
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500315static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000316_CharT* __assign_constexpr(_CharT* __s, size_t __n, _CharT __a) _NOEXCEPT
317{
Nikolas Klauserf87ca902021-12-21 11:22:50 +0100318 _LIBCPP_ASSERT(__libcpp_is_constant_evaluated(), "__assign_constexpr() should always be constant evaluated");
319 _VSTD::fill_n(__s, __n, __a);
320 return __s;
Michael Parkb5f44472019-11-08 13:42:26 +0000321}
322
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000323// char_traits<char>
324
325template <>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000326struct _LIBCPP_TEMPLATE_VIS char_traits<char>
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000327{
328 typedef char char_type;
329 typedef int int_type;
330 typedef streamoff off_type;
331 typedef streampos pos_type;
332 typedef mbstate_t state_type;
333
Marshall Clow951035b2017-01-12 04:37:14 +0000334 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
335 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000336 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
337 {return __c1 == __c2;}
338 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
339 {return (unsigned char)__c1 < (unsigned char)__c2;}
340
Marshall Clowaa32f162017-01-12 05:40:58 +0000341 static _LIBCPP_CONSTEXPR_AFTER_CXX14
342 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Nikolas Klauserce79c5d2021-12-15 21:12:24 +0100343
344 static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14 length(const char_type* __s) _NOEXCEPT {
345 // GCC currently does not support __builtin_strlen during constant evaluation.
346 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70816
347#ifdef _LIBCPP_COMPILER_GCC
348 if (__libcpp_is_constant_evaluated()) {
349 size_t __i = 0;
350 for (; __s[__i] != char_type('\0'); ++__i)
351 ;
352 return __i;
353 }
354#endif
355 return __builtin_strlen(__s);
356 }
357
Marshall Clow951035b2017-01-12 04:37:14 +0000358 static _LIBCPP_CONSTEXPR_AFTER_CXX14
359 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500360 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000361 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
362 {
363 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500364 ? _VSTD::__move_constexpr(__s1, __s2, __n)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500365 : __n == 0 ? __s1 : (char_type*)_VSTD::memmove(__s1, __s2, __n);
Michael Parkb5f44472019-11-08 13:42:26 +0000366 }
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500367 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000368 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000369 {
Arthur O'Dwyere9a55122021-04-20 22:24:24 -0400370 if (!__libcpp_is_constant_evaluated()) {
371 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
372 }
Michael Parkb5f44472019-11-08 13:42:26 +0000373 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500374 ? _VSTD::__copy_constexpr(__s1, __s2, __n)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500375 : __n == 0 ? __s1 : (char_type*)_VSTD::memcpy(__s1, __s2, __n);
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000376 }
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500377 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000378 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
379 {
380 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500381 ? _VSTD::__assign_constexpr(__s, __n, __a)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500382 : __n == 0 ? __s : (char_type*)_VSTD::memset(__s, to_int_type(__a), __n);
Michael Parkb5f44472019-11-08 13:42:26 +0000383 }
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000384
385 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
386 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
387 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
388 {return char_type(__c);}
389 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
390 {return int_type((unsigned char)__c);}
391 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
392 {return __c1 == __c2;}
393 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
394 {return int_type(EOF);}
395};
396
Marshall Clow951035b2017-01-12 04:37:14 +0000397inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowaa32f162017-01-12 05:40:58 +0000398int
399char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
400{
401 if (__n == 0)
402 return 0;
Marshall Clowb344c362017-01-26 06:58:29 +0000403#if __has_feature(cxx_constexpr_string_builtins)
Marshall Clowaa32f162017-01-12 05:40:58 +0000404 return __builtin_memcmp(__s1, __s2, __n);
405#elif _LIBCPP_STD_VER <= 14
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500406 return _VSTD::memcmp(__s1, __s2, __n);
Marshall Clowaa32f162017-01-12 05:40:58 +0000407#else
408 for (; __n; --__n, ++__s1, ++__s2)
409 {
410 if (lt(*__s1, *__s2))
411 return -1;
412 if (lt(*__s2, *__s1))
413 return 1;
414 }
415 return 0;
416#endif
417}
418
419inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow951035b2017-01-12 04:37:14 +0000420const char*
421char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
422{
423 if (__n == 0)
Marshall Clow32043ac2018-02-06 18:58:05 +0000424 return nullptr;
Marshall Clowb344c362017-01-26 06:58:29 +0000425#if __has_feature(cxx_constexpr_string_builtins)
426 return __builtin_char_memchr(__s, to_int_type(__a), __n);
427#elif _LIBCPP_STD_VER <= 14
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500428 return (const char_type*) _VSTD::memchr(__s, to_int_type(__a), __n);
Marshall Clow951035b2017-01-12 04:37:14 +0000429#else
430 for (; __n; --__n)
431 {
432 if (eq(*__s, __a))
433 return __s;
434 ++__s;
435 }
Marshall Clow32043ac2018-02-06 18:58:05 +0000436 return nullptr;
Marshall Clow951035b2017-01-12 04:37:14 +0000437#endif
438}
439
440
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000441// char_traits<wchar_t>
442
Louis Dionne89258142021-08-23 15:32:36 -0400443#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000444template <>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000445struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000446{
447 typedef wchar_t char_type;
448 typedef wint_t int_type;
449 typedef streamoff off_type;
450 typedef streampos pos_type;
451 typedef mbstate_t state_type;
452
Marshall Clow951035b2017-01-12 04:37:14 +0000453 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
454 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000455 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
456 {return __c1 == __c2;}
457 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
458 {return __c1 < __c2;}
459
Marshall Clow951035b2017-01-12 04:37:14 +0000460 static _LIBCPP_CONSTEXPR_AFTER_CXX14
461 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
462 static _LIBCPP_CONSTEXPR_AFTER_CXX14
463 size_t length(const char_type* __s) _NOEXCEPT;
464 static _LIBCPP_CONSTEXPR_AFTER_CXX14
465 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500466 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000467 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
468 {
469 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500470 ? _VSTD::__move_constexpr(__s1, __s2, __n)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500471 : __n == 0 ? __s1 : _VSTD::wmemmove(__s1, __s2, __n);
Michael Parkb5f44472019-11-08 13:42:26 +0000472 }
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500473 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000474 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000475 {
Arthur O'Dwyere9a55122021-04-20 22:24:24 -0400476 if (!__libcpp_is_constant_evaluated()) {
477 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
478 }
Michael Parkb5f44472019-11-08 13:42:26 +0000479 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500480 ? _VSTD::__copy_constexpr(__s1, __s2, __n)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500481 : __n == 0 ? __s1 : _VSTD::wmemcpy(__s1, __s2, __n);
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000482 }
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500483 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000484 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
485 {
486 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500487 ? _VSTD::__assign_constexpr(__s, __n, __a)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500488 : __n == 0 ? __s : _VSTD::wmemset(__s, __a, __n);
Michael Parkb5f44472019-11-08 13:42:26 +0000489 }
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000490 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
491 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
492 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
493 {return char_type(__c);}
494 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
495 {return int_type(__c);}
496 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
497 {return __c1 == __c2;}
498 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
499 {return int_type(WEOF);}
500};
501
Marshall Clow951035b2017-01-12 04:37:14 +0000502inline _LIBCPP_CONSTEXPR_AFTER_CXX14
503int
504char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
505{
506 if (__n == 0)
507 return 0;
Marshall Clowb344c362017-01-26 06:58:29 +0000508#if __has_feature(cxx_constexpr_string_builtins)
Marshall Clow951035b2017-01-12 04:37:14 +0000509 return __builtin_wmemcmp(__s1, __s2, __n);
510#elif _LIBCPP_STD_VER <= 14
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500511 return _VSTD::wmemcmp(__s1, __s2, __n);
Marshall Clow951035b2017-01-12 04:37:14 +0000512#else
513 for (; __n; --__n, ++__s1, ++__s2)
514 {
515 if (lt(*__s1, *__s2))
516 return -1;
517 if (lt(*__s2, *__s1))
518 return 1;
519 }
520 return 0;
521#endif
522}
523
524inline _LIBCPP_CONSTEXPR_AFTER_CXX14
525size_t
526char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
527{
Marshall Clowb344c362017-01-26 06:58:29 +0000528#if __has_feature(cxx_constexpr_string_builtins)
Marshall Clow951035b2017-01-12 04:37:14 +0000529 return __builtin_wcslen(__s);
530#elif _LIBCPP_STD_VER <= 14
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500531 return _VSTD::wcslen(__s);
Marshall Clow951035b2017-01-12 04:37:14 +0000532#else
533 size_t __len = 0;
534 for (; !eq(*__s, char_type(0)); ++__s)
535 ++__len;
536 return __len;
537#endif
538}
539
540inline _LIBCPP_CONSTEXPR_AFTER_CXX14
541const wchar_t*
542char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
543{
544 if (__n == 0)
Marshall Clow32043ac2018-02-06 18:58:05 +0000545 return nullptr;
Marshall Clowb344c362017-01-26 06:58:29 +0000546#if __has_feature(cxx_constexpr_string_builtins)
Marshall Clow32043ac2018-02-06 18:58:05 +0000547 return __builtin_wmemchr(__s, __a, __n);
Marshall Clow951035b2017-01-12 04:37:14 +0000548#elif _LIBCPP_STD_VER <= 14
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500549 return _VSTD::wmemchr(__s, __a, __n);
Marshall Clow951035b2017-01-12 04:37:14 +0000550#else
551 for (; __n; --__n)
552 {
553 if (eq(*__s, __a))
554 return __s;
555 ++__s;
556 }
Marshall Clow32043ac2018-02-06 18:58:05 +0000557 return nullptr;
Marshall Clow951035b2017-01-12 04:37:14 +0000558#endif
559}
Louis Dionne89258142021-08-23 15:32:36 -0400560#endif // _LIBCPP_HAS_NO_WIDE_CHARACTERS
Marshall Clow951035b2017-01-12 04:37:14 +0000561
Louis Dionne76f4e0b2021-09-09 13:23:26 -0400562template <class _Traits>
563_LIBCPP_INLINE_VISIBILITY
564_LIBCPP_CONSTEXPR
565inline size_t __char_traits_length_checked(const typename _Traits::char_type* __s) _NOEXCEPT {
566#if _LIBCPP_DEBUG_LEVEL >= 1
567 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);
568#else
569 return _Traits::length(__s);
570#endif
571}
Marshall Clow951035b2017-01-12 04:37:14 +0000572
Arthur O'Dwyerafa5d5f2021-04-18 21:47:08 -0400573#ifndef _LIBCPP_HAS_NO_CHAR8_T
Marshall Clow8732fed2018-12-11 04:35:44 +0000574
575template <>
576struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
577{
578 typedef char8_t char_type;
579 typedef unsigned int int_type;
580 typedef streamoff off_type;
581 typedef u8streampos pos_type;
582 typedef mbstate_t state_type;
583
584 static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
585 {__c1 = __c2;}
586 static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept
587 {return __c1 == __c2;}
588 static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept
589 {return __c1 < __c2;}
590
591 static constexpr
592 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
593
594 static constexpr
595 size_t length(const char_type* __s) _NOEXCEPT;
Louis Dionnefd77e4f2019-10-23 10:40:15 -0700596
Marshall Clow8732fed2018-12-11 04:35:44 +0000597 _LIBCPP_INLINE_VISIBILITY static constexpr
598 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
Louis Dionnefd77e4f2019-10-23 10:40:15 -0700599
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500600 static _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000601 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
602 {
603 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500604 ? _VSTD::__move_constexpr(__s1, __s2, __n)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500605 : __n == 0 ? __s1 : (char_type*)_VSTD::memmove(__s1, __s2, __n);
Michael Parkb5f44472019-11-08 13:42:26 +0000606 }
Louis Dionnefd77e4f2019-10-23 10:40:15 -0700607
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500608 static _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000609 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Arthur O'Dwyere9a55122021-04-20 22:24:24 -0400610 {
611 if (!__libcpp_is_constant_evaluated()) {
612 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
613 }
Michael Parkb5f44472019-11-08 13:42:26 +0000614 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500615 ? _VSTD::__copy_constexpr(__s1, __s2, __n)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500616 : __n == 0 ? __s1 : (char_type*)_VSTD::memcpy(__s1, __s2, __n);
Michael Parkb5f44472019-11-08 13:42:26 +0000617 }
Louis Dionnefd77e4f2019-10-23 10:40:15 -0700618
Arthur O'Dwyer14606d12020-11-23 12:44:41 -0500619 static _LIBCPP_CONSTEXPR_AFTER_CXX17
Michael Parkb5f44472019-11-08 13:42:26 +0000620 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
621 {
622 return __libcpp_is_constant_evaluated()
Arthur O'Dwyere75dcfa2020-11-22 13:21:11 -0500623 ? _VSTD::__assign_constexpr(__s, __n, __a)
Arthur O'Dwyer22236632020-12-07 21:50:15 -0500624 : __n == 0 ? __s : (char_type*)_VSTD::memset(__s, to_int_type(__a), __n);
Michael Parkb5f44472019-11-08 13:42:26 +0000625 }
Marshall Clow8732fed2018-12-11 04:35:44 +0000626
627 static inline constexpr int_type not_eof(int_type __c) noexcept
628 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
629 static inline constexpr char_type to_char_type(int_type __c) noexcept
630 {return char_type(__c);}
631 static inline constexpr int_type to_int_type(char_type __c) noexcept
632 {return int_type(__c);}
633 static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
634 {return __c1 == __c2;}
635 static inline constexpr int_type eof() noexcept
636 {return int_type(EOF);}
637};
638
639// TODO use '__builtin_strlen' if it ever supports char8_t ??
640inline constexpr
641size_t
642char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT
643{
644 size_t __len = 0;
645 for (; !eq(*__s, char_type(0)); ++__s)
646 ++__len;
647 return __len;
648}
649
650inline constexpr
651int
652char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
653{
654#if __has_feature(cxx_constexpr_string_builtins)
655 return __builtin_memcmp(__s1, __s2, __n);
656#else
657 for (; __n; --__n, ++__s1, ++__s2)
658 {
659 if (lt(*__s1, *__s2))
660 return -1;
661 if (lt(*__s2, *__s1))
662 return 1;
663 }
664 return 0;
665#endif
666}
667
668// TODO use '__builtin_char_memchr' if it ever supports char8_t ??
669inline constexpr
670const char8_t*
671char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
672{
673 for (; __n; --__n)
674 {
675 if (eq(*__s, __a))
676 return __s;
677 ++__s;
678 }
Bruce Mitchener170d8972020-11-24 12:53:53 -0500679 return nullptr;
Marshall Clow8732fed2018-12-11 04:35:44 +0000680}
681
Arthur O'Dwyerafa5d5f2021-04-18 21:47:08 -0400682#endif // #_LIBCPP_HAS_NO_CHAR8_T
Marshall Clow8732fed2018-12-11 04:35:44 +0000683
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000684#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
685
686template <>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000687struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000688{
689 typedef char16_t char_type;
690 typedef uint_least16_t int_type;
691 typedef streamoff off_type;
692 typedef u16streampos pos_type;
693 typedef mbstate_t state_type;
694
Marshall Clow951035b2017-01-12 04:37:14 +0000695 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
696 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000697 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
698 {return __c1 == __c2;}
699 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
700 {return __c1 < __c2;}
701
Marshall Clow951035b2017-01-12 04:37:14 +0000702 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
703 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
704 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
705 size_t length(const char_type* __s) _NOEXCEPT;
706 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
707 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
Michael Parkb5f44472019-11-08 13:42:26 +0000708 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clow36097db2016-07-28 04:52:02 +0000709 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Michael Parkb5f44472019-11-08 13:42:26 +0000710 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clow36097db2016-07-28 04:52:02 +0000711 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Michael Parkb5f44472019-11-08 13:42:26 +0000712 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clow36097db2016-07-28 04:52:02 +0000713 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000714
715 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
716 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
717 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
718 {return char_type(__c);}
719 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
720 {return int_type(__c);}
721 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
722 {return __c1 == __c2;}
723 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
724 {return int_type(0xFFFF);}
725};
726
Marshall Clow951035b2017-01-12 04:37:14 +0000727inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000728int
Marshall Clow36097db2016-07-28 04:52:02 +0000729char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000730{
731 for (; __n; --__n, ++__s1, ++__s2)
732 {
733 if (lt(*__s1, *__s2))
734 return -1;
735 if (lt(*__s2, *__s1))
736 return 1;
737 }
738 return 0;
739}
740
Marshall Clow951035b2017-01-12 04:37:14 +0000741inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000742size_t
Marshall Clow36097db2016-07-28 04:52:02 +0000743char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000744{
745 size_t __len = 0;
746 for (; !eq(*__s, char_type(0)); ++__s)
747 ++__len;
748 return __len;
749}
750
Marshall Clow951035b2017-01-12 04:37:14 +0000751inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000752const char16_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000753char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000754{
755 for (; __n; --__n)
756 {
757 if (eq(*__s, __a))
758 return __s;
759 ++__s;
760 }
Bruce Mitchener170d8972020-11-24 12:53:53 -0500761 return nullptr;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000762}
763
Michael Parkb5f44472019-11-08 13:42:26 +0000764inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000765char16_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000766char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000767{
Michael Parkb5f44472019-11-08 13:42:26 +0000768 if (__n == 0) return __s1;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000769 char_type* __r = __s1;
770 if (__s1 < __s2)
771 {
772 for (; __n; --__n, ++__s1, ++__s2)
773 assign(*__s1, *__s2);
774 }
775 else if (__s2 < __s1)
776 {
777 __s1 += __n;
778 __s2 += __n;
779 for (; __n; --__n)
780 assign(*--__s1, *--__s2);
781 }
782 return __r;
783}
784
Michael Parkb5f44472019-11-08 13:42:26 +0000785inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000786char16_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000787char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000788{
Arthur O'Dwyere9a55122021-04-20 22:24:24 -0400789 if (!__libcpp_is_constant_evaluated()) {
790 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
791 }
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000792 char_type* __r = __s1;
793 for (; __n; --__n, ++__s1, ++__s2)
794 assign(*__s1, *__s2);
795 return __r;
796}
797
Michael Parkb5f44472019-11-08 13:42:26 +0000798inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000799char16_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000800char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000801{
802 char_type* __r = __s;
803 for (; __n; --__n, ++__s)
804 assign(*__s, __a);
805 return __r;
806}
807
808template <>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000809struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000810{
811 typedef char32_t char_type;
812 typedef uint_least32_t int_type;
813 typedef streamoff off_type;
814 typedef u32streampos pos_type;
815 typedef mbstate_t state_type;
816
Marshall Clow951035b2017-01-12 04:37:14 +0000817 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
818 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000819 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
820 {return __c1 == __c2;}
821 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
822 {return __c1 < __c2;}
823
Marshall Clow951035b2017-01-12 04:37:14 +0000824 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
825 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
826 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
827 size_t length(const char_type* __s) _NOEXCEPT;
828 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
829 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
Michael Parkb5f44472019-11-08 13:42:26 +0000830 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clow36097db2016-07-28 04:52:02 +0000831 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Michael Parkb5f44472019-11-08 13:42:26 +0000832 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clow36097db2016-07-28 04:52:02 +0000833 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Michael Parkb5f44472019-11-08 13:42:26 +0000834 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clow36097db2016-07-28 04:52:02 +0000835 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000836
837 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
838 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
839 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
840 {return char_type(__c);}
841 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
842 {return int_type(__c);}
843 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
844 {return __c1 == __c2;}
845 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
846 {return int_type(0xFFFFFFFF);}
847};
848
Marshall Clow951035b2017-01-12 04:37:14 +0000849inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000850int
Marshall Clow36097db2016-07-28 04:52:02 +0000851char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000852{
853 for (; __n; --__n, ++__s1, ++__s2)
854 {
855 if (lt(*__s1, *__s2))
856 return -1;
857 if (lt(*__s2, *__s1))
858 return 1;
859 }
860 return 0;
861}
862
Marshall Clow951035b2017-01-12 04:37:14 +0000863inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000864size_t
Marshall Clow36097db2016-07-28 04:52:02 +0000865char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000866{
867 size_t __len = 0;
868 for (; !eq(*__s, char_type(0)); ++__s)
869 ++__len;
870 return __len;
871}
872
Marshall Clow951035b2017-01-12 04:37:14 +0000873inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000874const char32_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000875char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000876{
877 for (; __n; --__n)
878 {
879 if (eq(*__s, __a))
880 return __s;
881 ++__s;
882 }
Bruce Mitchener170d8972020-11-24 12:53:53 -0500883 return nullptr;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000884}
885
Michael Parkb5f44472019-11-08 13:42:26 +0000886inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000887char32_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000888char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000889{
Michael Parkb5f44472019-11-08 13:42:26 +0000890 if (__n == 0) return __s1;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000891 char_type* __r = __s1;
892 if (__s1 < __s2)
893 {
894 for (; __n; --__n, ++__s1, ++__s2)
895 assign(*__s1, *__s2);
896 }
897 else if (__s2 < __s1)
898 {
899 __s1 += __n;
900 __s2 += __n;
901 for (; __n; --__n)
902 assign(*--__s1, *--__s2);
903 }
904 return __r;
905}
906
Michael Parkb5f44472019-11-08 13:42:26 +0000907inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000908char32_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000909char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000910{
Arthur O'Dwyere9a55122021-04-20 22:24:24 -0400911 if (!__libcpp_is_constant_evaluated()) {
912 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
913 }
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000914 char_type* __r = __s1;
915 for (; __n; --__n, ++__s1, ++__s2)
916 assign(*__s1, *__s2);
917 return __r;
918}
919
Michael Parkb5f44472019-11-08 13:42:26 +0000920inline _LIBCPP_CONSTEXPR_AFTER_CXX17
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000921char32_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000922char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000923{
924 char_type* __r = __s;
925 for (; __n; --__n, ++__s)
926 assign(*__s, __a);
927 return __r;
928}
929
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400930#endif // _LIBCPP_HAS_NO_UNICODE_CHARS
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000931
932// helper fns for basic_string and string_view
933
934// __str_find
935template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
936inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
Louis Dionnefd77e4f2019-10-23 10:40:15 -0700937__str_find(const _CharT *__p, _SizeT __sz,
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000938 _CharT __c, _SizeT __pos) _NOEXCEPT
939{
940 if (__pos >= __sz)
941 return __npos;
942 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
Bruce Mitchener170d8972020-11-24 12:53:53 -0500943 if (__r == nullptr)
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000944 return __npos;
945 return static_cast<_SizeT>(__r - __p);
946}
947
Sebastian Pop65115202016-12-30 18:01:36 +0000948template <class _CharT, class _Traits>
949inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
950__search_substring(const _CharT *__first1, const _CharT *__last1,
zoecarver1997e0a2021-02-05 11:54:47 -0800951 const _CharT *__first2, const _CharT *__last2) _NOEXCEPT {
Sebastian Pop65115202016-12-30 18:01:36 +0000952 // Take advantage of knowing source and pattern lengths.
953 // Stop short when source is smaller than pattern.
954 const ptrdiff_t __len2 = __last2 - __first2;
955 if (__len2 == 0)
956 return __first1;
957
958 ptrdiff_t __len1 = __last1 - __first1;
959 if (__len1 < __len2)
960 return __last1;
961
962 // First element of __first2 is loop invariant.
963 _CharT __f2 = *__first2;
964 while (true) {
965 __len1 = __last1 - __first1;
966 // Check whether __first1 still has at least __len2 bytes.
967 if (__len1 < __len2)
968 return __last1;
969
970 // Find __f2 the first byte matching in __first1.
971 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
Bruce Mitchener170d8972020-11-24 12:53:53 -0500972 if (__first1 == nullptr)
Sebastian Pop65115202016-12-30 18:01:36 +0000973 return __last1;
974
975 // It is faster to compare from the first byte of __first1 even if we
976 // already know that it matches the first byte of __first2: this is because
977 // __first2 is most likely aligned, as it is user's "pattern" string, and
978 // __first1 + 1 is most likely not aligned, as the match is in the middle of
979 // the string.
980 if (_Traits::compare(__first1, __first2, __len2) == 0)
981 return __first1;
982
983 ++__first1;
984 }
985}
986
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000987template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
988inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
Louis Dionnefd77e4f2019-10-23 10:40:15 -0700989__str_find(const _CharT *__p, _SizeT __sz,
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000990 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
991{
Sebastian Pop65115202016-12-30 18:01:36 +0000992 if (__pos > __sz)
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000993 return __npos;
Sebastian Pop65115202016-12-30 18:01:36 +0000994
995 if (__n == 0) // There is nothing to search, just return __pos.
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000996 return __pos;
Sebastian Pop65115202016-12-30 18:01:36 +0000997
998 const _CharT *__r = __search_substring<_CharT, _Traits>(
999 __p + __pos, __p + __sz, __s, __s + __n);
1000
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001001 if (__r == __p + __sz)
1002 return __npos;
1003 return static_cast<_SizeT>(__r - __p);
1004}
1005
1006
1007// __str_rfind
1008
1009template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1010inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
Louis Dionnefd77e4f2019-10-23 10:40:15 -07001011__str_rfind(const _CharT *__p, _SizeT __sz,
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001012 _CharT __c, _SizeT __pos) _NOEXCEPT
1013{
1014 if (__sz < 1)
1015 return __npos;
1016 if (__pos < __sz)
1017 ++__pos;
1018 else
1019 __pos = __sz;
1020 for (const _CharT* __ps = __p + __pos; __ps != __p;)
1021 {
1022 if (_Traits::eq(*--__ps, __c))
1023 return static_cast<_SizeT>(__ps - __p);
1024 }
1025 return __npos;
1026}
1027
1028template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1029inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
Louis Dionnefd77e4f2019-10-23 10:40:15 -07001030__str_rfind(const _CharT *__p, _SizeT __sz,
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001031 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1032{
1033 __pos = _VSTD::min(__pos, __sz);
1034 if (__n < __sz - __pos)
1035 __pos += __n;
1036 else
1037 __pos = __sz;
1038 const _CharT* __r = _VSTD::__find_end(
Louis Dionnefd77e4f2019-10-23 10:40:15 -07001039 __p, __p + __pos, __s, __s + __n, _Traits::eq,
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001040 random_access_iterator_tag(), random_access_iterator_tag());
1041 if (__n > 0 && __r == __p + __pos)
1042 return __npos;
1043 return static_cast<_SizeT>(__r - __p);
1044}
1045
1046// __str_find_first_of
1047template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1048inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1049__str_find_first_of(const _CharT *__p, _SizeT __sz,
1050 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1051{
1052 if (__pos >= __sz || __n == 0)
1053 return __npos;
1054 const _CharT* __r = _VSTD::__find_first_of_ce
1055 (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
1056 if (__r == __p + __sz)
1057 return __npos;
1058 return static_cast<_SizeT>(__r - __p);
1059}
1060
1061
1062// __str_find_last_of
1063template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1064inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1065__str_find_last_of(const _CharT *__p, _SizeT __sz,
1066 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1067 {
1068 if (__n != 0)
1069 {
1070 if (__pos < __sz)
1071 ++__pos;
1072 else
1073 __pos = __sz;
1074 for (const _CharT* __ps = __p + __pos; __ps != __p;)
1075 {
1076 const _CharT* __r = _Traits::find(__s, __n, *--__ps);
1077 if (__r)
1078 return static_cast<_SizeT>(__ps - __p);
1079 }
1080 }
1081 return __npos;
1082}
1083
1084
1085// __str_find_first_not_of
1086template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1087inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1088__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
1089 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1090{
1091 if (__pos < __sz)
1092 {
1093 const _CharT* __pe = __p + __sz;
1094 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
Bruce Mitchener170d8972020-11-24 12:53:53 -05001095 if (_Traits::find(__s, __n, *__ps) == nullptr)
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001096 return static_cast<_SizeT>(__ps - __p);
1097 }
1098 return __npos;
1099}
1100
1101
1102template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1103inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1104__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
1105 _CharT __c, _SizeT __pos) _NOEXCEPT
1106{
1107 if (__pos < __sz)
1108 {
1109 const _CharT* __pe = __p + __sz;
1110 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
1111 if (!_Traits::eq(*__ps, __c))
1112 return static_cast<_SizeT>(__ps - __p);
1113 }
1114 return __npos;
1115}
1116
1117
1118// __str_find_last_not_of
1119template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1120inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1121__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
1122 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
1123{
1124 if (__pos < __sz)
1125 ++__pos;
1126 else
1127 __pos = __sz;
1128 for (const _CharT* __ps = __p + __pos; __ps != __p;)
Bruce Mitchener170d8972020-11-24 12:53:53 -05001129 if (_Traits::find(__s, __n, *--__ps) == nullptr)
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001130 return static_cast<_SizeT>(__ps - __p);
1131 return __npos;
1132}
1133
1134
1135template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
1136inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1137__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
1138 _CharT __c, _SizeT __pos) _NOEXCEPT
1139{
1140 if (__pos < __sz)
1141 ++__pos;
1142 else
1143 __pos = __sz;
1144 for (const _CharT* __ps = __p + __pos; __ps != __p;)
1145 if (!_Traits::eq(*--__ps, __c))
1146 return static_cast<_SizeT>(__ps - __p);
1147 return __npos;
1148}
1149
1150template<class _Ptr>
Eric Fiselier1b57fa82016-09-15 22:27:07 +00001151inline _LIBCPP_INLINE_VISIBILITY
1152size_t __do_string_hash(_Ptr __p, _Ptr __e)
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001153{
1154 typedef typename iterator_traits<_Ptr>::value_type value_type;
1155 return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
1156}
1157
1158template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
1159struct __quoted_output_proxy
1160{
1161 _Iter __first;
1162 _Iter __last;
1163 _CharT __delim;
1164 _CharT __escape;
1165
1166 __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
1167 : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
Louis Dionnefd77e4f2019-10-23 10:40:15 -07001168 // This would be a nice place for a string_ref
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001169};
1170
1171_LIBCPP_END_NAMESPACE_STD
1172
Eric Fiselierf4433a32017-05-31 22:07:49 +00001173_LIBCPP_POP_MACROS
1174
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001175#endif // _LIBCPP___STRING