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