| // -*- C++ -*- | |
| //===-------------------------- __string ----------------------------------===// | |
| // | |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
| // See https://llvm.org/LICENSE.txt for license information. | |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
| // | |
| //===----------------------------------------------------------------------===// | |
| #ifndef _LIBCPP___STRING | |
| #define _LIBCPP___STRING | |
| /* | |
| string synopsis | |
| namespace std | |
| { | |
| template <class charT> | |
| struct char_traits | |
| { | |
| typedef charT char_type; | |
| typedef ... int_type; | |
| typedef streamoff off_type; | |
| typedef streampos pos_type; | |
| typedef mbstate_t state_type; | |
| static constexpr void assign(char_type& c1, const char_type& c2) noexcept; | |
| static constexpr bool eq(char_type c1, char_type c2) noexcept; | |
| static constexpr bool lt(char_type c1, char_type c2) noexcept; | |
| static constexpr int compare(const char_type* s1, const char_type* s2, size_t n); | |
| static constexpr size_t length(const char_type* s); | |
| static constexpr const char_type* | |
| find(const char_type* s, size_t n, const char_type& a); | |
| static char_type* move(char_type* s1, const char_type* s2, size_t n); | |
| static char_type* copy(char_type* s1, const char_type* s2, size_t n); | |
| static char_type* assign(char_type* s, size_t n, char_type a); | |
| static constexpr int_type not_eof(int_type c) noexcept; | |
| static constexpr char_type to_char_type(int_type c) noexcept; | |
| static constexpr int_type to_int_type(char_type c) noexcept; | |
| static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept; | |
| static constexpr int_type eof() noexcept; | |
| }; | |
| template <> struct char_traits<char>; | |
| template <> struct char_traits<wchar_t>; | |
| template <> struct char_traits<char8_t>; // c++20 | |
| } // std | |
| */ | |
| #include <__config> | |
| #include <algorithm> // for search and min | |
| #include <cstdio> // For EOF. | |
| #include <memory> // for __murmur2_or_cityhash | |
| #include <__debug> | |
| #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) | |
| #pragma GCC system_header | |
| #endif | |
| _LIBCPP_PUSH_MACROS | |
| #include <__undef_macros> | |
| _LIBCPP_BEGIN_NAMESPACE_STD | |
| // char_traits | |
| template <class _CharT> | |
| struct _LIBCPP_TEMPLATE_VIS char_traits | |
| { | |
| typedef _CharT char_type; | |
| typedef int int_type; | |
| typedef streamoff off_type; | |
| typedef streampos pos_type; | |
| typedef mbstate_t state_type; | |
| static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 < __c2;} | |
| static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int compare(const char_type* __s1, const char_type* __s2, size_t __n); | |
| _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| size_t length(const char_type* __s); | |
| _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const char_type* find(const char_type* __s, size_t __n, const char_type& __a); | |
| static char_type* move(char_type* __s1, const char_type* __s2, size_t __n); | |
| _LIBCPP_INLINE_VISIBILITY | |
| static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n); | |
| _LIBCPP_INLINE_VISIBILITY | |
| static char_type* assign(char_type* __s, size_t __n, char_type __a); | |
| static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT | |
| {return eq_int_type(__c, eof()) ? ~eof() : __c;} | |
| static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT | |
| {return char_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT | |
| {return int_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT | |
| {return int_type(EOF);} | |
| }; | |
| template <class _CharT> | |
| _LIBCPP_CONSTEXPR_AFTER_CXX14 int | |
| char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n) | |
| { | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| { | |
| if (lt(*__s1, *__s2)) | |
| return -1; | |
| if (lt(*__s2, *__s1)) | |
| return 1; | |
| } | |
| return 0; | |
| } | |
| template <class _CharT> | |
| inline | |
| _LIBCPP_CONSTEXPR_AFTER_CXX14 size_t | |
| char_traits<_CharT>::length(const char_type* __s) | |
| { | |
| size_t __len = 0; | |
| for (; !eq(*__s, char_type(0)); ++__s) | |
| ++__len; | |
| return __len; | |
| } | |
| template <class _CharT> | |
| inline | |
| _LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT* | |
| char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a) | |
| { | |
| for (; __n; --__n) | |
| { | |
| if (eq(*__s, __a)) | |
| return __s; | |
| ++__s; | |
| } | |
| return 0; | |
| } | |
| template <class _CharT> | |
| _CharT* | |
| char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n) | |
| { | |
| char_type* __r = __s1; | |
| if (__s1 < __s2) | |
| { | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| assign(*__s1, *__s2); | |
| } | |
| else if (__s2 < __s1) | |
| { | |
| __s1 += __n; | |
| __s2 += __n; | |
| for (; __n; --__n) | |
| assign(*--__s1, *--__s2); | |
| } | |
| return __r; | |
| } | |
| template <class _CharT> | |
| inline | |
| _CharT* | |
| char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n) | |
| { | |
| _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); | |
| char_type* __r = __s1; | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| assign(*__s1, *__s2); | |
| return __r; | |
| } | |
| template <class _CharT> | |
| inline | |
| _CharT* | |
| char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a) | |
| { | |
| char_type* __r = __s; | |
| for (; __n; --__n, ++__s) | |
| assign(*__s, __a); | |
| return __r; | |
| } | |
| // char_traits<char> | |
| template <> | |
| struct _LIBCPP_TEMPLATE_VIS char_traits<char> | |
| { | |
| typedef char char_type; | |
| typedef int int_type; | |
| typedef streamoff off_type; | |
| typedef streampos pos_type; | |
| typedef mbstate_t state_type; | |
| static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return (unsigned char)__c1 < (unsigned char)__c2;} | |
| static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| length(const char_type* __s) _NOEXCEPT {return __builtin_strlen(__s);} | |
| static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; | |
| static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);} | |
| static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); | |
| return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n); | |
| } | |
| static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT | |
| {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);} | |
| static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT | |
| {return eq_int_type(__c, eof()) ? ~eof() : __c;} | |
| static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT | |
| {return char_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT | |
| {return int_type((unsigned char)__c);} | |
| static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT | |
| {return int_type(EOF);} | |
| }; | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int | |
| char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| if (__n == 0) | |
| return 0; | |
| #if __has_feature(cxx_constexpr_string_builtins) | |
| return __builtin_memcmp(__s1, __s2, __n); | |
| #elif _LIBCPP_STD_VER <= 14 | |
| return memcmp(__s1, __s2, __n); | |
| #else | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| { | |
| if (lt(*__s1, *__s2)) | |
| return -1; | |
| if (lt(*__s2, *__s1)) | |
| return 1; | |
| } | |
| return 0; | |
| #endif | |
| } | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const char* | |
| char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT | |
| { | |
| if (__n == 0) | |
| return nullptr; | |
| #if __has_feature(cxx_constexpr_string_builtins) | |
| return __builtin_char_memchr(__s, to_int_type(__a), __n); | |
| #elif _LIBCPP_STD_VER <= 14 | |
| return (const char_type*) memchr(__s, to_int_type(__a), __n); | |
| #else | |
| for (; __n; --__n) | |
| { | |
| if (eq(*__s, __a)) | |
| return __s; | |
| ++__s; | |
| } | |
| return nullptr; | |
| #endif | |
| } | |
| // char_traits<wchar_t> | |
| template <> | |
| struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t> | |
| { | |
| typedef wchar_t char_type; | |
| typedef wint_t int_type; | |
| typedef streamoff off_type; | |
| typedef streampos pos_type; | |
| typedef mbstate_t state_type; | |
| static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 < __c2;} | |
| static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| size_t length(const char_type* __s) _NOEXCEPT; | |
| static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; | |
| static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| {return __n == 0 ? __s1 : (char_type*)wmemmove(__s1, __s2, __n);} | |
| static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); | |
| return __n == 0 ? __s1 : (char_type*)wmemcpy(__s1, __s2, __n); | |
| } | |
| static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT | |
| {return __n == 0 ? __s : (char_type*)wmemset(__s, __a, __n);} | |
| static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT | |
| {return eq_int_type(__c, eof()) ? ~eof() : __c;} | |
| static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT | |
| {return char_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT | |
| {return int_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT | |
| {return int_type(WEOF);} | |
| }; | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int | |
| char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| if (__n == 0) | |
| return 0; | |
| #if __has_feature(cxx_constexpr_string_builtins) | |
| return __builtin_wmemcmp(__s1, __s2, __n); | |
| #elif _LIBCPP_STD_VER <= 14 | |
| return wmemcmp(__s1, __s2, __n); | |
| #else | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| { | |
| if (lt(*__s1, *__s2)) | |
| return -1; | |
| if (lt(*__s2, *__s1)) | |
| return 1; | |
| } | |
| return 0; | |
| #endif | |
| } | |
| template <class _Traits> | |
| _LIBCPP_INLINE_VISIBILITY | |
| _LIBCPP_CONSTEXPR | |
| inline size_t __char_traits_length_checked(const typename _Traits::char_type* __s) _NOEXCEPT { | |
| #if _LIBCPP_DEBUG_LEVEL >= 1 | |
| 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); | |
| #else | |
| return _Traits::length(__s); | |
| #endif | |
| } | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| size_t | |
| char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT | |
| { | |
| #if __has_feature(cxx_constexpr_string_builtins) | |
| return __builtin_wcslen(__s); | |
| #elif _LIBCPP_STD_VER <= 14 | |
| return wcslen(__s); | |
| #else | |
| size_t __len = 0; | |
| for (; !eq(*__s, char_type(0)); ++__s) | |
| ++__len; | |
| return __len; | |
| #endif | |
| } | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const wchar_t* | |
| char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT | |
| { | |
| if (__n == 0) | |
| return nullptr; | |
| #if __has_feature(cxx_constexpr_string_builtins) | |
| return __builtin_wmemchr(__s, __a, __n); | |
| #elif _LIBCPP_STD_VER <= 14 | |
| return wmemchr(__s, __a, __n); | |
| #else | |
| for (; __n; --__n) | |
| { | |
| if (eq(*__s, __a)) | |
| return __s; | |
| ++__s; | |
| } | |
| return nullptr; | |
| #endif | |
| } | |
| #ifndef _LIBCPP_NO_HAS_CHAR8_T | |
| template <> | |
| struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t> | |
| { | |
| typedef char8_t char_type; | |
| typedef unsigned int int_type; | |
| typedef streamoff off_type; | |
| typedef u8streampos pos_type; | |
| typedef mbstate_t state_type; | |
| static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept | |
| {__c1 = __c2;} | |
| static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept | |
| {return __c1 == __c2;} | |
| static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept | |
| {return __c1 < __c2;} | |
| static constexpr | |
| int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| static constexpr | |
| size_t length(const char_type* __s) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY static constexpr | |
| const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; | |
| static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);} | |
| static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); | |
| return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n); | |
| } | |
| static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT | |
| {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);} | |
| static inline constexpr int_type not_eof(int_type __c) noexcept | |
| {return eq_int_type(__c, eof()) ? ~eof() : __c;} | |
| static inline constexpr char_type to_char_type(int_type __c) noexcept | |
| {return char_type(__c);} | |
| static inline constexpr int_type to_int_type(char_type __c) noexcept | |
| {return int_type(__c);} | |
| static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept | |
| {return __c1 == __c2;} | |
| static inline constexpr int_type eof() noexcept | |
| {return int_type(EOF);} | |
| }; | |
| // TODO use '__builtin_strlen' if it ever supports char8_t ?? | |
| inline constexpr | |
| size_t | |
| char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT | |
| { | |
| size_t __len = 0; | |
| for (; !eq(*__s, char_type(0)); ++__s) | |
| ++__len; | |
| return __len; | |
| } | |
| inline constexpr | |
| int | |
| char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| #if __has_feature(cxx_constexpr_string_builtins) | |
| return __builtin_memcmp(__s1, __s2, __n); | |
| #else | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| { | |
| if (lt(*__s1, *__s2)) | |
| return -1; | |
| if (lt(*__s2, *__s1)) | |
| return 1; | |
| } | |
| return 0; | |
| #endif | |
| } | |
| // TODO use '__builtin_char_memchr' if it ever supports char8_t ?? | |
| inline constexpr | |
| const char8_t* | |
| char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT | |
| { | |
| for (; __n; --__n) | |
| { | |
| if (eq(*__s, __a)) | |
| return __s; | |
| ++__s; | |
| } | |
| return 0; | |
| } | |
| #endif // #_LIBCPP_NO_HAS_CHAR8_T | |
| #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS | |
| template <> | |
| struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t> | |
| { | |
| typedef char16_t char_type; | |
| typedef uint_least16_t int_type; | |
| typedef streamoff off_type; | |
| typedef u16streampos pos_type; | |
| typedef mbstate_t state_type; | |
| static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 < __c2;} | |
| _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| size_t length(const char_type* __s) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY | |
| static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY | |
| static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY | |
| static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT; | |
| static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT | |
| {return eq_int_type(__c, eof()) ? ~eof() : __c;} | |
| static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT | |
| {return char_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT | |
| {return int_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT | |
| {return int_type(0xFFFF);} | |
| }; | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int | |
| char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| { | |
| if (lt(*__s1, *__s2)) | |
| return -1; | |
| if (lt(*__s2, *__s1)) | |
| return 1; | |
| } | |
| return 0; | |
| } | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| size_t | |
| char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT | |
| { | |
| size_t __len = 0; | |
| for (; !eq(*__s, char_type(0)); ++__s) | |
| ++__len; | |
| return __len; | |
| } | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const char16_t* | |
| char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT | |
| { | |
| for (; __n; --__n) | |
| { | |
| if (eq(*__s, __a)) | |
| return __s; | |
| ++__s; | |
| } | |
| return 0; | |
| } | |
| inline | |
| char16_t* | |
| char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| char_type* __r = __s1; | |
| if (__s1 < __s2) | |
| { | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| assign(*__s1, *__s2); | |
| } | |
| else if (__s2 < __s1) | |
| { | |
| __s1 += __n; | |
| __s2 += __n; | |
| for (; __n; --__n) | |
| assign(*--__s1, *--__s2); | |
| } | |
| return __r; | |
| } | |
| inline | |
| char16_t* | |
| char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); | |
| char_type* __r = __s1; | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| assign(*__s1, *__s2); | |
| return __r; | |
| } | |
| inline | |
| char16_t* | |
| char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT | |
| { | |
| char_type* __r = __s; | |
| for (; __n; --__n, ++__s) | |
| assign(*__s, __a); | |
| return __r; | |
| } | |
| template <> | |
| struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t> | |
| { | |
| typedef char32_t char_type; | |
| typedef uint_least32_t int_type; | |
| typedef streamoff off_type; | |
| typedef u32streampos pos_type; | |
| typedef mbstate_t state_type; | |
| static inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT | |
| {return __c1 < __c2;} | |
| _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| size_t length(const char_type* __s) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY | |
| static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY | |
| static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; | |
| _LIBCPP_INLINE_VISIBILITY | |
| static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT; | |
| static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT | |
| {return eq_int_type(__c, eof()) ? ~eof() : __c;} | |
| static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT | |
| {return char_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT | |
| {return int_type(__c);} | |
| static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT | |
| {return __c1 == __c2;} | |
| static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT | |
| {return int_type(0xFFFFFFFF);} | |
| }; | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| int | |
| char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| { | |
| if (lt(*__s1, *__s2)) | |
| return -1; | |
| if (lt(*__s2, *__s1)) | |
| return 1; | |
| } | |
| return 0; | |
| } | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| size_t | |
| char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT | |
| { | |
| size_t __len = 0; | |
| for (; !eq(*__s, char_type(0)); ++__s) | |
| ++__len; | |
| return __len; | |
| } | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX14 | |
| const char32_t* | |
| char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT | |
| { | |
| for (; __n; --__n) | |
| { | |
| if (eq(*__s, __a)) | |
| return __s; | |
| ++__s; | |
| } | |
| return 0; | |
| } | |
| inline | |
| char32_t* | |
| char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| char_type* __r = __s1; | |
| if (__s1 < __s2) | |
| { | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| assign(*__s1, *__s2); | |
| } | |
| else if (__s2 < __s1) | |
| { | |
| __s1 += __n; | |
| __s2 += __n; | |
| for (; __n; --__n) | |
| assign(*--__s1, *--__s2); | |
| } | |
| return __r; | |
| } | |
| inline | |
| char32_t* | |
| char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT | |
| { | |
| _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); | |
| char_type* __r = __s1; | |
| for (; __n; --__n, ++__s1, ++__s2) | |
| assign(*__s1, *__s2); | |
| return __r; | |
| } | |
| inline | |
| char32_t* | |
| char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT | |
| { | |
| char_type* __r = __s; | |
| for (; __n; --__n, ++__s) | |
| assign(*__s, __a); | |
| return __r; | |
| } | |
| #endif // _LIBCPP_HAS_NO_UNICODE_CHARS | |
| // helper fns for basic_string and string_view | |
| // __str_find | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_find(const _CharT *__p, _SizeT __sz, | |
| _CharT __c, _SizeT __pos) _NOEXCEPT | |
| { | |
| if (__pos >= __sz) | |
| return __npos; | |
| const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c); | |
| if (__r == 0) | |
| return __npos; | |
| return static_cast<_SizeT>(__r - __p); | |
| } | |
| template <class _CharT, class _Traits> | |
| inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT * | |
| __search_substring(const _CharT *__first1, const _CharT *__last1, | |
| const _CharT *__first2, const _CharT *__last2) { | |
| // Take advantage of knowing source and pattern lengths. | |
| // Stop short when source is smaller than pattern. | |
| const ptrdiff_t __len2 = __last2 - __first2; | |
| if (__len2 == 0) | |
| return __first1; | |
| ptrdiff_t __len1 = __last1 - __first1; | |
| if (__len1 < __len2) | |
| return __last1; | |
| // First element of __first2 is loop invariant. | |
| _CharT __f2 = *__first2; | |
| while (true) { | |
| __len1 = __last1 - __first1; | |
| // Check whether __first1 still has at least __len2 bytes. | |
| if (__len1 < __len2) | |
| return __last1; | |
| // Find __f2 the first byte matching in __first1. | |
| __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2); | |
| if (__first1 == 0) | |
| return __last1; | |
| // It is faster to compare from the first byte of __first1 even if we | |
| // already know that it matches the first byte of __first2: this is because | |
| // __first2 is most likely aligned, as it is user's "pattern" string, and | |
| // __first1 + 1 is most likely not aligned, as the match is in the middle of | |
| // the string. | |
| if (_Traits::compare(__first1, __first2, __len2) == 0) | |
| return __first1; | |
| ++__first1; | |
| } | |
| } | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_find(const _CharT *__p, _SizeT __sz, | |
| const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT | |
| { | |
| if (__pos > __sz) | |
| return __npos; | |
| if (__n == 0) // There is nothing to search, just return __pos. | |
| return __pos; | |
| const _CharT *__r = __search_substring<_CharT, _Traits>( | |
| __p + __pos, __p + __sz, __s, __s + __n); | |
| if (__r == __p + __sz) | |
| return __npos; | |
| return static_cast<_SizeT>(__r - __p); | |
| } | |
| // __str_rfind | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_rfind(const _CharT *__p, _SizeT __sz, | |
| _CharT __c, _SizeT __pos) _NOEXCEPT | |
| { | |
| if (__sz < 1) | |
| return __npos; | |
| if (__pos < __sz) | |
| ++__pos; | |
| else | |
| __pos = __sz; | |
| for (const _CharT* __ps = __p + __pos; __ps != __p;) | |
| { | |
| if (_Traits::eq(*--__ps, __c)) | |
| return static_cast<_SizeT>(__ps - __p); | |
| } | |
| return __npos; | |
| } | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_rfind(const _CharT *__p, _SizeT __sz, | |
| const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT | |
| { | |
| __pos = _VSTD::min(__pos, __sz); | |
| if (__n < __sz - __pos) | |
| __pos += __n; | |
| else | |
| __pos = __sz; | |
| const _CharT* __r = _VSTD::__find_end( | |
| __p, __p + __pos, __s, __s + __n, _Traits::eq, | |
| random_access_iterator_tag(), random_access_iterator_tag()); | |
| if (__n > 0 && __r == __p + __pos) | |
| return __npos; | |
| return static_cast<_SizeT>(__r - __p); | |
| } | |
| // __str_find_first_of | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_find_first_of(const _CharT *__p, _SizeT __sz, | |
| const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT | |
| { | |
| if (__pos >= __sz || __n == 0) | |
| return __npos; | |
| const _CharT* __r = _VSTD::__find_first_of_ce | |
| (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq ); | |
| if (__r == __p + __sz) | |
| return __npos; | |
| return static_cast<_SizeT>(__r - __p); | |
| } | |
| // __str_find_last_of | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_find_last_of(const _CharT *__p, _SizeT __sz, | |
| const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT | |
| { | |
| if (__n != 0) | |
| { | |
| if (__pos < __sz) | |
| ++__pos; | |
| else | |
| __pos = __sz; | |
| for (const _CharT* __ps = __p + __pos; __ps != __p;) | |
| { | |
| const _CharT* __r = _Traits::find(__s, __n, *--__ps); | |
| if (__r) | |
| return static_cast<_SizeT>(__ps - __p); | |
| } | |
| } | |
| return __npos; | |
| } | |
| // __str_find_first_not_of | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_find_first_not_of(const _CharT *__p, _SizeT __sz, | |
| const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT | |
| { | |
| if (__pos < __sz) | |
| { | |
| const _CharT* __pe = __p + __sz; | |
| for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) | |
| if (_Traits::find(__s, __n, *__ps) == 0) | |
| return static_cast<_SizeT>(__ps - __p); | |
| } | |
| return __npos; | |
| } | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_find_first_not_of(const _CharT *__p, _SizeT __sz, | |
| _CharT __c, _SizeT __pos) _NOEXCEPT | |
| { | |
| if (__pos < __sz) | |
| { | |
| const _CharT* __pe = __p + __sz; | |
| for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps) | |
| if (!_Traits::eq(*__ps, __c)) | |
| return static_cast<_SizeT>(__ps - __p); | |
| } | |
| return __npos; | |
| } | |
| // __str_find_last_not_of | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_find_last_not_of(const _CharT *__p, _SizeT __sz, | |
| const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT | |
| { | |
| if (__pos < __sz) | |
| ++__pos; | |
| else | |
| __pos = __sz; | |
| for (const _CharT* __ps = __p + __pos; __ps != __p;) | |
| if (_Traits::find(__s, __n, *--__ps) == 0) | |
| return static_cast<_SizeT>(__ps - __p); | |
| return __npos; | |
| } | |
| template<class _CharT, class _SizeT, class _Traits, _SizeT __npos> | |
| inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY | |
| __str_find_last_not_of(const _CharT *__p, _SizeT __sz, | |
| _CharT __c, _SizeT __pos) _NOEXCEPT | |
| { | |
| if (__pos < __sz) | |
| ++__pos; | |
| else | |
| __pos = __sz; | |
| for (const _CharT* __ps = __p + __pos; __ps != __p;) | |
| if (!_Traits::eq(*--__ps, __c)) | |
| return static_cast<_SizeT>(__ps - __p); | |
| return __npos; | |
| } | |
| template<class _Ptr> | |
| inline _LIBCPP_INLINE_VISIBILITY | |
| size_t __do_string_hash(_Ptr __p, _Ptr __e) | |
| { | |
| typedef typename iterator_traits<_Ptr>::value_type value_type; | |
| return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type)); | |
| } | |
| template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> > | |
| struct __quoted_output_proxy | |
| { | |
| _Iter __first; | |
| _Iter __last; | |
| _CharT __delim; | |
| _CharT __escape; | |
| __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e) | |
| : __first(__f), __last(__l), __delim(__d), __escape(__e) {} | |
| // This would be a nice place for a string_ref | |
| }; | |
| _LIBCPP_END_NAMESPACE_STD | |
| _LIBCPP_POP_MACROS | |
| #endif // _LIBCPP___STRING |