1// -*- C++ -*- 2//===-------------------------- __string ----------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP___STRING 11#define _LIBCPP___STRING 12 13#include <__config> 14#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 26#include <cwchar> // for wmemcpy 27#include <type_traits> // for __libcpp_is_constant_evaluated 28 29#include <__debug> 30 31#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 32#pragma GCC system_header 33#endif 34 35_LIBCPP_PUSH_MACROS 36#include <__undef_macros> 37 38 39_LIBCPP_BEGIN_NAMESPACE_STD 40 41// The the extern template ABI lists are kept outside of <string> to improve the 42// readability of that header. 43 44// The extern template ABI lists are kept outside of <string> to improve the 45// readability of that header. We maintain 2 ABI lists: 46// - _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST 47// - _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST 48// As the name implies, the ABI lists define the V1 (Stable) and unstable ABI. 49// 50// For unstable, we may explicitly remove function that are external in V1, 51// and add (new) external functions to better control inlining and compiler 52// optimization opportunities. 53// 54// For stable, the ABI list should rarely change, except for adding new 55// functions supporting new c++ version / API changes. Typically entries 56// must never be removed from the stable list. 57#define _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST(_Func, _CharType) \ 58 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*, size_type)) \ 59 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type const*, size_type, size_type) const) \ 60 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type, size_type)) \ 61 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&)) \ 62 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*)) \ 63 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, allocator<_CharType> const&)) \ 64 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_not_of(value_type const*, size_type, size_type) const) \ 65 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::~basic_string()) \ 66 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_not_of(value_type const*, size_type, size_type) const) \ 67 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, size_type, value_type)) \ 68 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(value_type)) \ 69 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type)) \ 70 _Func(_LIBCPP_FUNC_VIS const _CharType& basic_string<_CharType>::at(size_type) const) \ 71 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*, size_type)) \ 72 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_of(value_type const*, size_type, size_type) const) \ 73 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, size_type, value_type)) \ 74 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*, size_type)) \ 75 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::reserve(size_type)) \ 76 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*, size_type)) \ 77 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(basic_string const&, size_type, size_type)) \ 78 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::copy(value_type*, size_type, size_type) const) \ 79 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, size_type, size_type, allocator<_CharType> const&)) \ 80 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type, size_type) const) \ 81 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(size_type, value_type)) \ 82 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*)) \ 83 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_of(value_type const*, size_type, size_type) const) \ 84 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \ 85 _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*)) \ 86 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::push_back(value_type)) \ 87 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(size_type, value_type)) \ 88 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type, size_type) const) \ 89 _Func(_LIBCPP_FUNC_VIS const basic_string<_CharType>::size_type basic_string<_CharType>::npos) \ 90 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(size_type, value_type)) \ 91 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::erase(size_type, size_type)) \ 92 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(basic_string const&, size_type, size_type)) \ 93 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(value_type const*) const) \ 94 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*) const) \ 95 _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \ 96 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*)) \ 97 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type const*, size_type, size_type) const) \ 98 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, basic_string const&, size_type, size_type) const) \ 99 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \ 100 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(basic_string const&)) \ 101 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \ 102 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \ 103 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \ 104 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \ 105 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type)) 106 107#define _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(_Func, _CharType) \ 108 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*, size_type)) \ 109 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type const*, size_type, size_type) const) \ 110 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type, size_type)) \ 111 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, value_type const*)) \ 112 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_not_of(value_type const*, size_type, size_type) const) \ 113 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::~basic_string()) \ 114 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_not_of(value_type const*, size_type, size_type) const) \ 115 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, size_type, value_type)) \ 116 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(value_type)) \ 117 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(value_type const*, size_type)) \ 118 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init_copy_ctor_external(value_type const*, size_type)) \ 119 _Func(_LIBCPP_FUNC_VIS const _CharType& basic_string<_CharType>::at(size_type) const) \ 120 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*, size_type)) \ 121 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_of(value_type const*, size_type, size_type) const) \ 122 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, size_type, value_type)) \ 123 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_external(value_type const*, size_type)) \ 124 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_external(value_type const*)) \ 125 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::reserve(size_type)) \ 126 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*, size_type)) \ 127 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(basic_string const&, size_type, size_type)) \ 128 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::copy(value_type*, size_type, size_type) const) \ 129 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, size_type, size_type, allocator<_CharType> const&)) \ 130 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type, size_type) const) \ 131 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(size_type, value_type)) \ 132 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*)) \ 133 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_of(value_type const*, size_type, size_type) const) \ 134 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \ 135 _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*)) \ 136 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_no_alias<false>(value_type const*, size_type)) \ 137 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_no_alias<true>(value_type const*, size_type)) \ 138 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::push_back(value_type)) \ 139 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(size_type, value_type)) \ 140 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type, size_type) const) \ 141 _Func(_LIBCPP_FUNC_VIS const basic_string<_CharType>::size_type basic_string<_CharType>::npos) \ 142 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(size_type, value_type)) \ 143 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__erase_external_with_move(size_type, size_type)) \ 144 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(basic_string const&, size_type, size_type)) \ 145 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(value_type const*) const) \ 146 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*) const) \ 147 _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \ 148 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type const*, size_type, size_type) const) \ 149 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, basic_string const&, size_type, size_type) const) \ 150 _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \ 151 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \ 152 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \ 153 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \ 154 _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \ 155 _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type)) 156 157 158// char_traits 159 160template <class _CharT> 161struct _LIBCPP_TEMPLATE_VIS char_traits 162{ 163 typedef _CharT char_type; 164 typedef int int_type; 165 typedef streamoff off_type; 166 typedef streampos pos_type; 167 typedef mbstate_t state_type; 168 169 static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14 170 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 171 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 172 {return __c1 == __c2;} 173 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 174 {return __c1 < __c2;} 175 176 static _LIBCPP_CONSTEXPR_AFTER_CXX14 177 int compare(const char_type* __s1, const char_type* __s2, size_t __n); 178 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 179 size_t length(const char_type* __s); 180 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 181 const char_type* find(const char_type* __s, size_t __n, const char_type& __a); 182 static _LIBCPP_CONSTEXPR_AFTER_CXX17 183 char_type* move(char_type* __s1, const char_type* __s2, size_t __n); 184 _LIBCPP_INLINE_VISIBILITY 185 static _LIBCPP_CONSTEXPR_AFTER_CXX17 186 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n); 187 _LIBCPP_INLINE_VISIBILITY 188 static _LIBCPP_CONSTEXPR_AFTER_CXX17 189 char_type* assign(char_type* __s, size_t __n, char_type __a); 190 191 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 192 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 193 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 194 {return char_type(__c);} 195 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 196 {return int_type(__c);} 197 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 198 {return __c1 == __c2;} 199 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 200 {return int_type(EOF);} 201}; 202 203template <class _CharT> 204_LIBCPP_CONSTEXPR_AFTER_CXX14 int 205char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n) 206{ 207 for (; __n; --__n, ++__s1, ++__s2) 208 { 209 if (lt(*__s1, *__s2)) 210 return -1; 211 if (lt(*__s2, *__s1)) 212 return 1; 213 } 214 return 0; 215} 216 217template <class _CharT> 218inline 219_LIBCPP_CONSTEXPR_AFTER_CXX14 size_t 220char_traits<_CharT>::length(const char_type* __s) 221{ 222 size_t __len = 0; 223 for (; !eq(*__s, char_type(0)); ++__s) 224 ++__len; 225 return __len; 226} 227 228template <class _CharT> 229inline 230_LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT* 231char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a) 232{ 233 for (; __n; --__n) 234 { 235 if (eq(*__s, __a)) 236 return __s; 237 ++__s; 238 } 239 return nullptr; 240} 241 242template <class _CharT> 243_LIBCPP_CONSTEXPR_AFTER_CXX17 _CharT* 244char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n) 245{ 246 if (__n == 0) return __s1; 247 char_type* __r = __s1; 248 if (__s1 < __s2) 249 { 250 for (; __n; --__n, ++__s1, ++__s2) 251 assign(*__s1, *__s2); 252 } 253 else if (__s2 < __s1) 254 { 255 __s1 += __n; 256 __s2 += __n; 257 for (; __n; --__n) 258 assign(*--__s1, *--__s2); 259 } 260 return __r; 261} 262 263template <class _CharT> 264inline _LIBCPP_CONSTEXPR_AFTER_CXX17 265_CharT* 266char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n) 267{ 268 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 269 char_type* __r = __s1; 270 for (; __n; --__n, ++__s1, ++__s2) 271 assign(*__s1, *__s2); 272 return __r; 273} 274 275template <class _CharT> 276inline _LIBCPP_CONSTEXPR_AFTER_CXX17 277_CharT* 278char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a) 279{ 280 char_type* __r = __s; 281 for (; __n; --__n, ++__s) 282 assign(*__s, __a); 283 return __r; 284} 285 286// constexpr versions of move/copy/assign. 287 288template <class _CharT> 289static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 290_CharT* __move_constexpr(_CharT* __s1, const _CharT* __s2, size_t __n) _NOEXCEPT 291{ 292 if (__n == 0) return __s1; 293 if (__s1 < __s2) { 294 _VSTD::copy(__s2, __s2 + __n, __s1); 295 } else if (__s2 < __s1) { 296 _VSTD::copy_backward(__s2, __s2 + __n, __s1 + __n); 297 } 298 return __s1; 299} 300 301template <class _CharT> 302static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 303_CharT* __copy_constexpr(_CharT* __s1, const _CharT* __s2, size_t __n) _NOEXCEPT 304{ 305 _VSTD::copy_n(__s2, __n, __s1); 306 return __s1; 307} 308 309template <class _CharT> 310static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 311_CharT* __assign_constexpr(_CharT* __s, size_t __n, _CharT __a) _NOEXCEPT 312{ 313 _VSTD::fill_n(__s, __n, __a); 314 return __s; 315} 316 317// char_traits<char> 318 319template <> 320struct _LIBCPP_TEMPLATE_VIS char_traits<char> 321{ 322 typedef char char_type; 323 typedef int int_type; 324 typedef streamoff off_type; 325 typedef streampos pos_type; 326 typedef mbstate_t state_type; 327 328 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 329 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 330 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 331 {return __c1 == __c2;} 332 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 333 {return (unsigned char)__c1 < (unsigned char)__c2;} 334 335 static _LIBCPP_CONSTEXPR_AFTER_CXX14 336 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 337 static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14 338 length(const char_type* __s) _NOEXCEPT {return __builtin_strlen(__s);} 339 static _LIBCPP_CONSTEXPR_AFTER_CXX14 340 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 341 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 342 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 343 { 344 return __libcpp_is_constant_evaluated() 345 ? _VSTD::__move_constexpr(__s1, __s2, __n) 346 : __n == 0 ? __s1 : (char_type*)_VSTD::memmove(__s1, __s2, __n); 347 } 348 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 349 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 350 { 351 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 352 return __libcpp_is_constant_evaluated() 353 ? _VSTD::__copy_constexpr(__s1, __s2, __n) 354 : __n == 0 ? __s1 : (char_type*)_VSTD::memcpy(__s1, __s2, __n); 355 } 356 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 357 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 358 { 359 return __libcpp_is_constant_evaluated() 360 ? _VSTD::__assign_constexpr(__s, __n, __a) 361 : __n == 0 ? __s : (char_type*)_VSTD::memset(__s, to_int_type(__a), __n); 362 } 363 364 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 365 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 366 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 367 {return char_type(__c);} 368 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 369 {return int_type((unsigned char)__c);} 370 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 371 {return __c1 == __c2;} 372 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 373 {return int_type(EOF);} 374}; 375 376inline _LIBCPP_CONSTEXPR_AFTER_CXX14 377int 378char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 379{ 380 if (__n == 0) 381 return 0; 382#if __has_feature(cxx_constexpr_string_builtins) 383 return __builtin_memcmp(__s1, __s2, __n); 384#elif _LIBCPP_STD_VER <= 14 385 return _VSTD::memcmp(__s1, __s2, __n); 386#else 387 for (; __n; --__n, ++__s1, ++__s2) 388 { 389 if (lt(*__s1, *__s2)) 390 return -1; 391 if (lt(*__s2, *__s1)) 392 return 1; 393 } 394 return 0; 395#endif 396} 397 398inline _LIBCPP_CONSTEXPR_AFTER_CXX14 399const char* 400char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 401{ 402 if (__n == 0) 403 return nullptr; 404#if __has_feature(cxx_constexpr_string_builtins) 405 return __builtin_char_memchr(__s, to_int_type(__a), __n); 406#elif _LIBCPP_STD_VER <= 14 407 return (const char_type*) _VSTD::memchr(__s, to_int_type(__a), __n); 408#else 409 for (; __n; --__n) 410 { 411 if (eq(*__s, __a)) 412 return __s; 413 ++__s; 414 } 415 return nullptr; 416#endif 417} 418 419 420// char_traits<wchar_t> 421 422template <> 423struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t> 424{ 425 typedef wchar_t char_type; 426 typedef wint_t int_type; 427 typedef streamoff off_type; 428 typedef streampos pos_type; 429 typedef mbstate_t state_type; 430 431 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 432 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 433 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 434 {return __c1 == __c2;} 435 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 436 {return __c1 < __c2;} 437 438 static _LIBCPP_CONSTEXPR_AFTER_CXX14 439 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 440 static _LIBCPP_CONSTEXPR_AFTER_CXX14 441 size_t length(const char_type* __s) _NOEXCEPT; 442 static _LIBCPP_CONSTEXPR_AFTER_CXX14 443 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 444 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 445 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 446 { 447 return __libcpp_is_constant_evaluated() 448 ? _VSTD::__move_constexpr(__s1, __s2, __n) 449 : __n == 0 ? __s1 : _VSTD::wmemmove(__s1, __s2, __n); 450 } 451 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 452 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 453 { 454 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 455 return __libcpp_is_constant_evaluated() 456 ? _VSTD::__copy_constexpr(__s1, __s2, __n) 457 : __n == 0 ? __s1 : _VSTD::wmemcpy(__s1, __s2, __n); 458 } 459 static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 460 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 461 { 462 return __libcpp_is_constant_evaluated() 463 ? _VSTD::__assign_constexpr(__s, __n, __a) 464 : __n == 0 ? __s : _VSTD::wmemset(__s, __a, __n); 465 } 466 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 467 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 468 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 469 {return char_type(__c);} 470 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 471 {return int_type(__c);} 472 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 473 {return __c1 == __c2;} 474 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 475 {return int_type(WEOF);} 476}; 477 478inline _LIBCPP_CONSTEXPR_AFTER_CXX14 479int 480char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 481{ 482 if (__n == 0) 483 return 0; 484#if __has_feature(cxx_constexpr_string_builtins) 485 return __builtin_wmemcmp(__s1, __s2, __n); 486#elif _LIBCPP_STD_VER <= 14 487 return _VSTD::wmemcmp(__s1, __s2, __n); 488#else 489 for (; __n; --__n, ++__s1, ++__s2) 490 { 491 if (lt(*__s1, *__s2)) 492 return -1; 493 if (lt(*__s2, *__s1)) 494 return 1; 495 } 496 return 0; 497#endif 498} 499 500 501template <class _Traits> 502_LIBCPP_INLINE_VISIBILITY 503_LIBCPP_CONSTEXPR 504inline size_t __char_traits_length_checked(const typename _Traits::char_type* __s) _NOEXCEPT { 505#if _LIBCPP_DEBUG_LEVEL >= 1 506 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); 507#else 508 return _Traits::length(__s); 509#endif 510} 511 512inline _LIBCPP_CONSTEXPR_AFTER_CXX14 513size_t 514char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT 515{ 516#if __has_feature(cxx_constexpr_string_builtins) 517 return __builtin_wcslen(__s); 518#elif _LIBCPP_STD_VER <= 14 519 return _VSTD::wcslen(__s); 520#else 521 size_t __len = 0; 522 for (; !eq(*__s, char_type(0)); ++__s) 523 ++__len; 524 return __len; 525#endif 526} 527 528inline _LIBCPP_CONSTEXPR_AFTER_CXX14 529const wchar_t* 530char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 531{ 532 if (__n == 0) 533 return nullptr; 534#if __has_feature(cxx_constexpr_string_builtins) 535 return __builtin_wmemchr(__s, __a, __n); 536#elif _LIBCPP_STD_VER <= 14 537 return _VSTD::wmemchr(__s, __a, __n); 538#else 539 for (; __n; --__n) 540 { 541 if (eq(*__s, __a)) 542 return __s; 543 ++__s; 544 } 545 return nullptr; 546#endif 547} 548 549 550#ifndef _LIBCPP_HAS_NO_CHAR8_T 551 552template <> 553struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t> 554{ 555 typedef char8_t char_type; 556 typedef unsigned int int_type; 557 typedef streamoff off_type; 558 typedef u8streampos pos_type; 559 typedef mbstate_t state_type; 560 561 static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept 562 {__c1 = __c2;} 563 static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept 564 {return __c1 == __c2;} 565 static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept 566 {return __c1 < __c2;} 567 568 static constexpr 569 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 570 571 static constexpr 572 size_t length(const char_type* __s) _NOEXCEPT; 573 574 _LIBCPP_INLINE_VISIBILITY static constexpr 575 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 576 577 static _LIBCPP_CONSTEXPR_AFTER_CXX17 578 char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 579 { 580 return __libcpp_is_constant_evaluated() 581 ? _VSTD::__move_constexpr(__s1, __s2, __n) 582 : __n == 0 ? __s1 : (char_type*)_VSTD::memmove(__s1, __s2, __n); 583 } 584 585 static _LIBCPP_CONSTEXPR_AFTER_CXX17 586 char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 587 { 588 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 589 return __libcpp_is_constant_evaluated() 590 ? _VSTD::__copy_constexpr(__s1, __s2, __n) 591 : __n == 0 ? __s1 : (char_type*)_VSTD::memcpy(__s1, __s2, __n); 592 } 593 594 static _LIBCPP_CONSTEXPR_AFTER_CXX17 595 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 596 { 597 return __libcpp_is_constant_evaluated() 598 ? _VSTD::__assign_constexpr(__s, __n, __a) 599 : __n == 0 ? __s : (char_type*)_VSTD::memset(__s, to_int_type(__a), __n); 600 } 601 602 static inline constexpr int_type not_eof(int_type __c) noexcept 603 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 604 static inline constexpr char_type to_char_type(int_type __c) noexcept 605 {return char_type(__c);} 606 static inline constexpr int_type to_int_type(char_type __c) noexcept 607 {return int_type(__c);} 608 static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept 609 {return __c1 == __c2;} 610 static inline constexpr int_type eof() noexcept 611 {return int_type(EOF);} 612}; 613 614// TODO use '__builtin_strlen' if it ever supports char8_t ?? 615inline constexpr 616size_t 617char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT 618{ 619 size_t __len = 0; 620 for (; !eq(*__s, char_type(0)); ++__s) 621 ++__len; 622 return __len; 623} 624 625inline constexpr 626int 627char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 628{ 629#if __has_feature(cxx_constexpr_string_builtins) 630 return __builtin_memcmp(__s1, __s2, __n); 631#else 632 for (; __n; --__n, ++__s1, ++__s2) 633 { 634 if (lt(*__s1, *__s2)) 635 return -1; 636 if (lt(*__s2, *__s1)) 637 return 1; 638 } 639 return 0; 640#endif 641} 642 643// TODO use '__builtin_char_memchr' if it ever supports char8_t ?? 644inline constexpr 645const char8_t* 646char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 647{ 648 for (; __n; --__n) 649 { 650 if (eq(*__s, __a)) 651 return __s; 652 ++__s; 653 } 654 return nullptr; 655} 656 657#endif // #_LIBCPP_HAS_NO_CHAR8_T 658 659#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS 660 661template <> 662struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t> 663{ 664 typedef char16_t char_type; 665 typedef uint_least16_t int_type; 666 typedef streamoff off_type; 667 typedef u16streampos pos_type; 668 typedef mbstate_t state_type; 669 670 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 671 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 672 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 673 {return __c1 == __c2;} 674 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 675 {return __c1 < __c2;} 676 677 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 678 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 679 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 680 size_t length(const char_type* __s) _NOEXCEPT; 681 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 682 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 683 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 684 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 685 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 686 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 687 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 688 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT; 689 690 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 691 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 692 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 693 {return char_type(__c);} 694 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 695 {return int_type(__c);} 696 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 697 {return __c1 == __c2;} 698 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 699 {return int_type(0xFFFF);} 700}; 701 702inline _LIBCPP_CONSTEXPR_AFTER_CXX14 703int 704char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 705{ 706 for (; __n; --__n, ++__s1, ++__s2) 707 { 708 if (lt(*__s1, *__s2)) 709 return -1; 710 if (lt(*__s2, *__s1)) 711 return 1; 712 } 713 return 0; 714} 715 716inline _LIBCPP_CONSTEXPR_AFTER_CXX14 717size_t 718char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT 719{ 720 size_t __len = 0; 721 for (; !eq(*__s, char_type(0)); ++__s) 722 ++__len; 723 return __len; 724} 725 726inline _LIBCPP_CONSTEXPR_AFTER_CXX14 727const char16_t* 728char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 729{ 730 for (; __n; --__n) 731 { 732 if (eq(*__s, __a)) 733 return __s; 734 ++__s; 735 } 736 return nullptr; 737} 738 739inline _LIBCPP_CONSTEXPR_AFTER_CXX17 740char16_t* 741char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 742{ 743 if (__n == 0) return __s1; 744 char_type* __r = __s1; 745 if (__s1 < __s2) 746 { 747 for (; __n; --__n, ++__s1, ++__s2) 748 assign(*__s1, *__s2); 749 } 750 else if (__s2 < __s1) 751 { 752 __s1 += __n; 753 __s2 += __n; 754 for (; __n; --__n) 755 assign(*--__s1, *--__s2); 756 } 757 return __r; 758} 759 760inline _LIBCPP_CONSTEXPR_AFTER_CXX17 761char16_t* 762char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 763{ 764 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 765 char_type* __r = __s1; 766 for (; __n; --__n, ++__s1, ++__s2) 767 assign(*__s1, *__s2); 768 return __r; 769} 770 771inline _LIBCPP_CONSTEXPR_AFTER_CXX17 772char16_t* 773char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 774{ 775 char_type* __r = __s; 776 for (; __n; --__n, ++__s) 777 assign(*__s, __a); 778 return __r; 779} 780 781template <> 782struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t> 783{ 784 typedef char32_t char_type; 785 typedef uint_least32_t int_type; 786 typedef streamoff off_type; 787 typedef u32streampos pos_type; 788 typedef mbstate_t state_type; 789 790 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 791 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} 792 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT 793 {return __c1 == __c2;} 794 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT 795 {return __c1 < __c2;} 796 797 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 798 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 799 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 800 size_t length(const char_type* __s) _NOEXCEPT; 801 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 802 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; 803 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 804 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 805 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 806 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; 807 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 808 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT; 809 810 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT 811 {return eq_int_type(__c, eof()) ? ~eof() : __c;} 812 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT 813 {return char_type(__c);} 814 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT 815 {return int_type(__c);} 816 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT 817 {return __c1 == __c2;} 818 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT 819 {return int_type(0xFFFFFFFF);} 820}; 821 822inline _LIBCPP_CONSTEXPR_AFTER_CXX14 823int 824char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 825{ 826 for (; __n; --__n, ++__s1, ++__s2) 827 { 828 if (lt(*__s1, *__s2)) 829 return -1; 830 if (lt(*__s2, *__s1)) 831 return 1; 832 } 833 return 0; 834} 835 836inline _LIBCPP_CONSTEXPR_AFTER_CXX14 837size_t 838char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT 839{ 840 size_t __len = 0; 841 for (; !eq(*__s, char_type(0)); ++__s) 842 ++__len; 843 return __len; 844} 845 846inline _LIBCPP_CONSTEXPR_AFTER_CXX14 847const char32_t* 848char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT 849{ 850 for (; __n; --__n) 851 { 852 if (eq(*__s, __a)) 853 return __s; 854 ++__s; 855 } 856 return nullptr; 857} 858 859inline _LIBCPP_CONSTEXPR_AFTER_CXX17 860char32_t* 861char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 862{ 863 if (__n == 0) return __s1; 864 char_type* __r = __s1; 865 if (__s1 < __s2) 866 { 867 for (; __n; --__n, ++__s1, ++__s2) 868 assign(*__s1, *__s2); 869 } 870 else if (__s2 < __s1) 871 { 872 __s1 += __n; 873 __s2 += __n; 874 for (; __n; --__n) 875 assign(*--__s1, *--__s2); 876 } 877 return __r; 878} 879 880inline _LIBCPP_CONSTEXPR_AFTER_CXX17 881char32_t* 882char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT 883{ 884 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); 885 char_type* __r = __s1; 886 for (; __n; --__n, ++__s1, ++__s2) 887 assign(*__s1, *__s2); 888 return __r; 889} 890 891inline _LIBCPP_CONSTEXPR_AFTER_CXX17 892char32_t* 893char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT 894{ 895 char_type* __r = __s; 896 for (; __n; --__n, ++__s) 897 assign(*__s, __a); 898 return __r; 899} 900 901#endif // _LIBCPP_HAS_NO_UNICODE_CHARS 902 903// helper fns for basic_string and string_view 904 905// __str_find 906template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 907inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 908__str_find(const _CharT *__p, _SizeT __sz, 909 _CharT __c, _SizeT __pos) _NOEXCEPT 910{ 911 if (__pos >= __sz) 912 return __npos; 913 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c); 914 if (__r == nullptr) 915 return __npos; 916 return static_cast<_SizeT>(__r - __p); 917} 918 919template <class _CharT, class _Traits> 920inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT * 921__search_substring(const _CharT *__first1, const _CharT *__last1, 922 const _CharT *__first2, const _CharT *__last2) _NOEXCEPT { 923 // Take advantage of knowing source and pattern lengths. 924 // Stop short when source is smaller than pattern. 925 const ptrdiff_t __len2 = __last2 - __first2; 926 if (__len2 == 0) 927 return __first1; 928 929 ptrdiff_t __len1 = __last1 - __first1; 930 if (__len1 < __len2) 931 return __last1; 932 933 // First element of __first2 is loop invariant. 934 _CharT __f2 = *__first2; 935 while (true) { 936 __len1 = __last1 - __first1; 937 // Check whether __first1 still has at least __len2 bytes. 938 if (__len1 < __len2) 939 return __last1; 940 941 // Find __f2 the first byte matching in __first1. 942 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2); 943 if (__first1 == nullptr) 944 return __last1; 945 946 // It is faster to compare from the first byte of __first1 even if we 947 // already know that it matches the first byte of __first2: this is because 948 // __first2 is most likely aligned, as it is user's "pattern" string, and 949 // __first1 + 1 is most likely not aligned, as the match is in the middle of 950 // the string. 951 if (_Traits::compare(__first1, __first2, __len2) == 0) 952 return __first1; 953 954 ++__first1; 955 } 956} 957 958template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 959inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 960__str_find(const _CharT *__p, _SizeT __sz, 961 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 962{ 963 if (__pos > __sz) 964 return __npos; 965 966 if (__n == 0) // There is nothing to search, just return __pos. 967 return __pos; 968 969 const _CharT *__r = __search_substring<_CharT, _Traits>( 970 __p + __pos, __p + __sz, __s, __s + __n); 971 972 if (__r == __p + __sz) 973 return __npos; 974 return static_cast<_SizeT>(__r - __p); 975} 976 977 978// __str_rfind 979 980template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 981inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 982__str_rfind(const _CharT *__p, _SizeT __sz, 983 _CharT __c, _SizeT __pos) _NOEXCEPT 984{ 985 if (__sz < 1) 986 return __npos; 987 if (__pos < __sz) 988 ++__pos; 989 else 990 __pos = __sz; 991 for (const _CharT* __ps = __p + __pos; __ps != __p;) 992 { 993 if (_Traits::eq(*--__ps, __c)) 994 return static_cast<_SizeT>(__ps - __p); 995 } 996 return __npos; 997} 998 999template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 1000inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 1001__str_rfind(const _CharT *__p, _SizeT __sz, 1002 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 1003{ 1004 __pos = _VSTD::min(__pos, __sz); 1005 if (__n < __sz - __pos) 1006 __pos += __n; 1007 else 1008 __pos = __sz; 1009 const _CharT* __r = _VSTD::__find_end( 1010 __p, __p + __pos, __s, __s + __n, _Traits::eq, 1011 random_access_iterator_tag(), random_access_iterator_tag()); 1012 if (__n > 0 && __r == __p + __pos) 1013 return __npos; 1014 return static_cast<_SizeT>(__r - __p); 1015} 1016 1017// __str_find_first_of 1018template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 1019inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 1020__str_find_first_of(const _CharT *__p, _SizeT __sz, 1021 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 1022{ 1023 if (__pos >= __sz || __n == 0) 1024 return __npos; 1025 const _CharT* __r = _VSTD::__find_first_of_ce 1026 (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq ); 1027 if (__r == __p + __sz) 1028 return __npos; 1029 return static_cast<_SizeT>(__r - __p); 1030} 1031 1032 1033// __str_find_last_of 1034template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 1035inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 1036__str_find_last_of(const _CharT *__p, _SizeT __sz, 1037 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 1038 { 1039 if (__n != 0) 1040 { 1041 if (__pos < __sz) 1042 ++__pos; 1043 else 1044 __pos = __sz; 1045 for (const _CharT* __ps = __p + __pos; __ps != __p;) 1046 { 1047 const _CharT* __r = _Traits::find(__s, __n, *--__ps); 1048 if (__r) 1049 return static_cast<_SizeT>(__ps - __p); 1050 } 1051 } 1052 return __npos; 1053} 1054 1055 1056// __str_find_first_not_of 1057template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 1058inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 1059__str_find_first_not_of(const _CharT *__p, _SizeT __sz, 1060 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 1061{ 1062 if (__pos < __sz) 1063 { 1064 const _CharT* __pe = __p + __sz; 1065 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) 1066 if (_Traits::find(__s, __n, *__ps) == nullptr) 1067 return static_cast<_SizeT>(__ps - __p); 1068 } 1069 return __npos; 1070} 1071 1072 1073template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 1074inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 1075__str_find_first_not_of(const _CharT *__p, _SizeT __sz, 1076 _CharT __c, _SizeT __pos) _NOEXCEPT 1077{ 1078 if (__pos < __sz) 1079 { 1080 const _CharT* __pe = __p + __sz; 1081 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) 1082 if (!_Traits::eq(*__ps, __c)) 1083 return static_cast<_SizeT>(__ps - __p); 1084 } 1085 return __npos; 1086} 1087 1088 1089// __str_find_last_not_of 1090template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 1091inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 1092__str_find_last_not_of(const _CharT *__p, _SizeT __sz, 1093 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT 1094{ 1095 if (__pos < __sz) 1096 ++__pos; 1097 else 1098 __pos = __sz; 1099 for (const _CharT* __ps = __p + __pos; __ps != __p;) 1100 if (_Traits::find(__s, __n, *--__ps) == nullptr) 1101 return static_cast<_SizeT>(__ps - __p); 1102 return __npos; 1103} 1104 1105 1106template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> 1107inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 1108__str_find_last_not_of(const _CharT *__p, _SizeT __sz, 1109 _CharT __c, _SizeT __pos) _NOEXCEPT 1110{ 1111 if (__pos < __sz) 1112 ++__pos; 1113 else 1114 __pos = __sz; 1115 for (const _CharT* __ps = __p + __pos; __ps != __p;) 1116 if (!_Traits::eq(*--__ps, __c)) 1117 return static_cast<_SizeT>(__ps - __p); 1118 return __npos; 1119} 1120 1121template<class _Ptr> 1122inline _LIBCPP_INLINE_VISIBILITY 1123size_t __do_string_hash(_Ptr __p, _Ptr __e) 1124{ 1125 typedef typename iterator_traits<_Ptr>::value_type value_type; 1126 return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type)); 1127} 1128 1129template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> > 1130struct __quoted_output_proxy 1131{ 1132 _Iter __first; 1133 _Iter __last; 1134 _CharT __delim; 1135 _CharT __escape; 1136 1137 __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e) 1138 : __first(__f), __last(__l), __delim(__d), __escape(__e) {} 1139 // This would be a nice place for a string_ref 1140}; 1141 1142_LIBCPP_END_NAMESPACE_STD 1143 1144_LIBCPP_POP_MACROS 1145 1146#endif // _LIBCPP___STRING 1147