diff options
Diffstat (limited to 'libcxx/include')
| -rw-r--r-- | libcxx/include/__algorithm/fill.h | 36 | ||||
| -rw-r--r-- | libcxx/include/__algorithm/fill_n.h | 48 | ||||
| -rw-r--r-- | libcxx/include/__algorithm/ranges_fill.h | 13 | ||||
| -rw-r--r-- | libcxx/include/__configuration/abi.h | 12 | ||||
| -rw-r--r-- | libcxx/include/__cxx03/__bit_reference | 18 | ||||
| -rw-r--r-- | libcxx/include/__cxx03/__verbose_abort | 2 | ||||
| -rw-r--r-- | libcxx/include/__cxx03/vector | 8 | ||||
| -rw-r--r-- | libcxx/include/__hash_table | 2 | ||||
| -rw-r--r-- | libcxx/include/__iterator/distance.h | 55 | ||||
| -rw-r--r-- | libcxx/include/__memory/array_cookie.h | 84 | ||||
| -rw-r--r-- | libcxx/include/__tree | 26 | ||||
| -rw-r--r-- | libcxx/include/__utility/cmp.h | 12 |
12 files changed, 242 insertions, 74 deletions
diff --git a/libcxx/include/__algorithm/fill.h b/libcxx/include/__algorithm/fill.h index 1ce3eadb..328ebb6 100644 --- a/libcxx/include/__algorithm/fill.h +++ b/libcxx/include/__algorithm/fill.h @@ -10,8 +10,11 @@ #define _LIBCPP___ALGORITHM_FILL_H #include <__algorithm/fill_n.h> +#include <__algorithm/for_each_segment.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__iterator/segmented_iterator.h> +#include <__type_traits/enable_if.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,23 +24,40 @@ _LIBCPP_BEGIN_NAMESPACE_STD // fill isn't specialized for std::memset, because the compiler already optimizes the loop to a call to std::memset. -template <class _ForwardIterator, class _Tp> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void -__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, forward_iterator_tag) { +template <class _ForwardIterator, class _Sentinel, class _Tp> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator +__fill(_ForwardIterator __first, _Sentinel __last, const _Tp& __value) { for (; __first != __last; ++__first) *__first = __value; + return __first; } -template <class _RandomAccessIterator, class _Tp> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void -__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value, random_access_iterator_tag) { - std::fill_n(__first, __last - __first, __value); +template <class _RandomAccessIterator, + class _Tp, + __enable_if_t<__has_random_access_iterator_category<_RandomAccessIterator>::value && + !__is_segmented_iterator_v<_RandomAccessIterator>, + int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator +__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value) { + return std::__fill_n(__first, __last - __first, __value); +} + +#ifndef _LIBCPP_CXX03_LANG +template <class _SegmentedIterator, class _Tp, __enable_if_t<__is_segmented_iterator_v<_SegmentedIterator>, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 +_SegmentedIterator __fill(_SegmentedIterator __first, _SegmentedIterator __last, const _Tp& __value) { + using __local_iterator_t = typename __segmented_iterator_traits<_SegmentedIterator>::__local_iterator; + std::__for_each_segment(__first, __last, [&](__local_iterator_t __lfirst, __local_iterator_t __llast) { + std::__fill(__lfirst, __llast, __value); + }); + return __last; } +#endif // !_LIBCPP_CXX03_LANG template <class _ForwardIterator, class _Tp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - std::__fill(__first, __last, __value, typename iterator_traits<_ForwardIterator>::iterator_category()); + std::__fill(__first, __last, __value); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/fill_n.h b/libcxx/include/__algorithm/fill_n.h index 0da78e1..2bfacf3 100644 --- a/libcxx/include/__algorithm/fill_n.h +++ b/libcxx/include/__algorithm/fill_n.h @@ -9,10 +9,17 @@ #ifndef _LIBCPP___ALGORITHM_FILL_N_H #define _LIBCPP___ALGORITHM_FILL_N_H +#include <__algorithm/for_each_n_segment.h> #include <__algorithm/min.h> #include <__config> #include <__fwd/bit_reference.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/segmented_iterator.h> #include <__memory/pointer_traits.h> +#include <__type_traits/conjunction.h> +#include <__type_traits/enable_if.h> +#include <__type_traits/integral_constant.h> +#include <__type_traits/negation.h> #include <__utility/convert_to_integral.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -26,9 +33,38 @@ _LIBCPP_BEGIN_NAMESPACE_STD // fill_n isn't specialized for std::memset, because the compiler already optimizes the loop to a call to std::memset. -template <class _OutputIterator, class _Size, class _Tp> +template <class _OutputIterator, + class _Size, + class _Tp +#ifndef _LIBCPP_CXX03_LANG + , + __enable_if_t<!_And<_BoolConstant<__is_segmented_iterator_v<_OutputIterator>>, + __has_random_access_local_iterator<_OutputIterator>>::value, + int> = 0 +#endif + > inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator -__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value); +__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) { + for (; __n > 0; ++__first, (void)--__n) + *__first = __value; + return __first; +} + +#ifndef _LIBCPP_CXX03_LANG +template < class _OutputIterator, + class _Size, + class _Tp, + __enable_if_t<_And<_BoolConstant<__is_segmented_iterator_v<_OutputIterator>>, + __has_random_access_local_iterator<_OutputIterator>>::value, + int> = 0> +inline _LIBCPP_HIDE_FROM_ABI +_LIBCPP_CONSTEXPR_SINCE_CXX14 _OutputIterator __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) { + using __local_iterator_t = typename __segmented_iterator_traits<_OutputIterator>::__local_iterator; + return std::__for_each_n_segment(__first, __n, [&](__local_iterator_t __lfirst, __local_iterator_t __llast) { + std::__fill_n(__lfirst, __llast - __lfirst, __value); + }); +} +#endif // !_LIBCPP_CXX03_LANG template <bool _FillVal, class _Cp> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void @@ -70,14 +106,6 @@ __fill_n(__bit_iterator<_Cp, false> __first, _Size __n, const bool& __value) { template <class _OutputIterator, class _Size, class _Tp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator -__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) { - for (; __n > 0; ++__first, (void)--__n) - *__first = __value; - return __first; -} - -template <class _OutputIterator, class _Size, class _Tp> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) { return std::__fill_n(__first, std::__convert_to_integral(__n), __value); } diff --git a/libcxx/include/__algorithm/ranges_fill.h b/libcxx/include/__algorithm/ranges_fill.h index c248009..814ae63 100644 --- a/libcxx/include/__algorithm/ranges_fill.h +++ b/libcxx/include/__algorithm/ranges_fill.h @@ -9,12 +9,14 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_FILL_H #define _LIBCPP___ALGORITHM_RANGES_FILL_H -#include <__algorithm/ranges_fill_n.h> +#include <__algorithm/fill.h> +#include <__algorithm/fill_n.h> #include <__config> #include <__iterator/concepts.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/dangling.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -31,12 +33,11 @@ namespace ranges { struct __fill { template <class _Type, output_iterator<const _Type&> _Iter, sentinel_for<_Iter> _Sent> _LIBCPP_HIDE_FROM_ABI constexpr _Iter operator()(_Iter __first, _Sent __last, const _Type& __value) const { - if constexpr (random_access_iterator<_Iter> && sized_sentinel_for<_Sent, _Iter>) { - return ranges::fill_n(__first, __last - __first, __value); + if constexpr (sized_sentinel_for<_Sent, _Iter>) { + auto __n = __last - __first; + return std::__fill_n(std::move(__first), __n, __value); } else { - for (; __first != __last; ++__first) - *__first = __value; - return __first; + return std::__fill(std::move(__first), std::move(__last), __value); } } diff --git a/libcxx/include/__configuration/abi.h b/libcxx/include/__configuration/abi.h index 2d33b9c..c9936df 100644 --- a/libcxx/include/__configuration/abi.h +++ b/libcxx/include/__configuration/abi.h @@ -30,8 +30,20 @@ #elif _LIBCPP_ABI_FORCE_MICROSOFT # define _LIBCPP_ABI_MICROSOFT #else +// Windows uses the Microsoft ABI # if defined(_WIN32) && defined(_MSC_VER) # define _LIBCPP_ABI_MICROSOFT + +// 32-bit ARM uses the Itanium ABI with a few differences (array cookies, etc), +// and so does 64-bit ARM on Apple platforms. +# elif defined(__arm__) || (defined(__APPLE__) && defined(__aarch64__)) +# define _LIBCPP_ABI_ITANIUM_WITH_ARM_DIFFERENCES + +// Non-Apple 64-bit ARM uses the vanilla Itanium ABI +# elif defined(__aarch64__) +# define _LIBCPP_ABI_ITANIUM + +// We assume that other architectures also use the vanilla Itanium ABI too # else # define _LIBCPP_ABI_ITANIUM # endif diff --git a/libcxx/include/__cxx03/__bit_reference b/libcxx/include/__cxx03/__bit_reference index 76027e2..ac0005f 100644 --- a/libcxx/include/__cxx03/__bit_reference +++ b/libcxx/include/__cxx03/__bit_reference @@ -167,7 +167,7 @@ _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned( unsigned __clz = __bits_per_word - __first.__ctz_; difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); __n -= __dn; - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); + __storage_type __m = (__storage_type(~0) << __first.__ctz_) & (__storage_type(~0) >> (__clz - __dn)); __storage_type __b = *__first.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b; @@ -185,7 +185,7 @@ _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned( // do last word if (__n > 0) { __first.__seg_ += __nw; - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); + __storage_type __m = __storage_type(~0) >> (__bits_per_word - __n); __storage_type __b = *__first.__seg_ & __m; *__result.__seg_ &= ~__m; *__result.__seg_ |= __b; @@ -210,11 +210,11 @@ _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned( unsigned __clz_f = __bits_per_word - __first.__ctz_; difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); __n -= __dn; - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); + __storage_type __m = (__storage_type(~0) << __first.__ctz_) & (__storage_type(~0) >> (__clz_f - __dn)); __storage_type __b = *__first.__seg_ & __m; unsigned __clz_r = __bits_per_word - __result.__ctz_; __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); - __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); + __m = (__storage_type(~0) << __result.__ctz_) & (__storage_type(~0) >> (__clz_r - __ddn)); *__result.__seg_ &= ~__m; if (__result.__ctz_ > __first.__ctz_) *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); @@ -224,7 +224,7 @@ _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned( __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); __dn -= __ddn; if (__dn > 0) { - __m = ~__storage_type(0) >> (__bits_per_word - __dn); + __m = __storage_type(~0) >> (__bits_per_word - __dn); *__result.__seg_ &= ~__m; *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); __result.__ctz_ = static_cast<unsigned>(__dn); @@ -235,7 +235,7 @@ _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned( // __first.__ctz_ == 0; // do middle words unsigned __clz_r = __bits_per_word - __result.__ctz_; - __storage_type __m = ~__storage_type(0) << __result.__ctz_; + __storage_type __m = __storage_type(~0) << __result.__ctz_; for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) { __storage_type __b = *__first.__seg_; *__result.__seg_ &= ~__m; @@ -246,17 +246,17 @@ _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned( } // do last word if (__n > 0) { - __m = ~__storage_type(0) >> (__bits_per_word - __n); + __m = __storage_type(~0) >> (__bits_per_word - __n); __storage_type __b = *__first.__seg_ & __m; __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r)); - __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); + __m = (__storage_type(~0) << __result.__ctz_) & (__storage_type(~0) >> (__clz_r - __dn)); *__result.__seg_ &= ~__m; *__result.__seg_ |= __b << __result.__ctz_; __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); __n -= __dn; if (__n > 0) { - __m = ~__storage_type(0) >> (__bits_per_word - __n); + __m = __storage_type(~0) >> (__bits_per_word - __n); *__result.__seg_ &= ~__m; *__result.__seg_ |= __b >> __dn; __result.__ctz_ = static_cast<unsigned>(__n); diff --git a/libcxx/include/__cxx03/__verbose_abort b/libcxx/include/__cxx03/__verbose_abort index 4fcfffa..52d1297 100644 --- a/libcxx/include/__cxx03/__verbose_abort +++ b/libcxx/include/__cxx03/__verbose_abort @@ -21,7 +21,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD // This function should never be called directly from the code -- it should only be called through // the _LIBCPP_VERBOSE_ABORT macro. _LIBCPP_NORETURN _LIBCPP_AVAILABILITY_VERBOSE_ABORT _LIBCPP_OVERRIDABLE_FUNC_VIS -_LIBCPP_ATTRIBUTE_FORMAT(__printf__, 1, 2) void __libcpp_verbose_abort(const char* __format, ...); +_LIBCPP_ATTRIBUTE_FORMAT(__printf__, 1, 2) void __libcpp_verbose_abort(const char* __format, ...) _NOEXCEPT; // _LIBCPP_VERBOSE_ABORT(format, args...) // diff --git a/libcxx/include/__cxx03/vector b/libcxx/include/__cxx03/vector index dbaa33c..43e82cd 100644 --- a/libcxx/include/__cxx03/vector +++ b/libcxx/include/__cxx03/vector @@ -1630,7 +1630,7 @@ private: return __n * __bits_per_word; } _LIBCPP_HIDE_FROM_ABI static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT { - return (__n - 1) / __bits_per_word + 1; + return __n > 0 ? (__n - 1) / __bits_per_word + 1 : size_type(0); } public: @@ -2142,11 +2142,13 @@ void vector<bool, _Allocator>::reserve(size_type __n) { template <class _Allocator> void vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT { - if (__external_cap_to_internal(size()) > __cap()) { + if (__external_cap_to_internal(size()) < __cap()) { #ifndef _LIBCPP_HAS_NO_EXCEPTIONS try { #endif // _LIBCPP_HAS_NO_EXCEPTIONS - vector(*this, allocator_type(__alloc())).swap(*this); + vector __v(*this, allocator_type(__alloc())); + if (__v.__cap() < __cap()) + __v.swap(*this); #ifndef _LIBCPP_HAS_NO_EXCEPTIONS } catch (...) { } diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table index 74923ddb..6b65e73 100644 --- a/libcxx/include/__hash_table +++ b/libcxx/include/__hash_table @@ -808,7 +808,7 @@ public: } { __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args2)...); - if (size() + 1 > __bc * max_load_factor() || __bc == 0) { + if (size() + 1 > __bc * max_load_factor()) { __rehash_unique(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor())))); __bc = bucket_count(); diff --git a/libcxx/include/__iterator/distance.h b/libcxx/include/__iterator/distance.h index 1732aa5..9be9db0 100644 --- a/libcxx/include/__iterator/distance.h +++ b/libcxx/include/__iterator/distance.h @@ -10,41 +10,71 @@ #ifndef _LIBCPP___ITERATOR_DISTANCE_H #define _LIBCPP___ITERATOR_DISTANCE_H +#include <__algorithm/for_each_segment.h> #include <__config> #include <__iterator/concepts.h> #include <__iterator/incrementable_traits.h> #include <__iterator/iterator_traits.h> +#include <__iterator/segmented_iterator.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/size.h> #include <__type_traits/decay.h> +#include <__type_traits/enable_if.h> #include <__type_traits/remove_cvref.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + _LIBCPP_BEGIN_NAMESPACE_STD -template <class _InputIter> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 typename iterator_traits<_InputIter>::difference_type -__distance(_InputIter __first, _InputIter __last, input_iterator_tag) { - typename iterator_traits<_InputIter>::difference_type __r(0); +#if _LIBCPP_STD_VER >= 20 +template <class _Iter> +using __iter_distance_t _LIBCPP_NODEBUG = std::iter_difference_t<_Iter>; +#else +template <class _Iter> +using __iter_distance_t _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::difference_type; +#endif + +template <class _InputIter, class _Sent> +inline _LIBCPP_HIDE_FROM_ABI +_LIBCPP_CONSTEXPR_SINCE_CXX17 __iter_distance_t<_InputIter> __distance(_InputIter __first, _Sent __last) { + __iter_distance_t<_InputIter> __r(0); for (; __first != __last; ++__first) ++__r; return __r; } -template <class _RandIter> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 typename iterator_traits<_RandIter>::difference_type -__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag) { +template <class _RandIter, __enable_if_t<__has_random_access_iterator_category<_RandIter>::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 __iter_distance_t<_RandIter> +__distance(_RandIter __first, _RandIter __last) { return __last - __first; } +#if _LIBCPP_STD_VER >= 20 +template <class _SegmentedIter, + __enable_if_t<!__has_random_access_iterator_category<_SegmentedIter>::value && + __is_segmented_iterator_v<_SegmentedIter>, + int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 __iter_distance_t<_SegmentedIter> +__distance(_SegmentedIter __first, _SegmentedIter __last) { + __iter_distance_t<_SegmentedIter> __r(0); + std::__for_each_segment(__first, __last, [&__r](auto __lfirst, auto __llast) { + __r += std::__distance(__lfirst, __llast); + }); + return __r; +} +#endif // _LIBCPP_STD_VER >= 20 + template <class _InputIter> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 typename iterator_traits<_InputIter>::difference_type distance(_InputIter __first, _InputIter __last) { - return std::__distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category()); + return std::__distance(__first, __last); } #if _LIBCPP_STD_VER >= 20 @@ -56,12 +86,7 @@ struct __distance { template <class _Ip, sentinel_for<_Ip> _Sp> requires(!sized_sentinel_for<_Sp, _Ip>) _LIBCPP_HIDE_FROM_ABI constexpr iter_difference_t<_Ip> operator()(_Ip __first, _Sp __last) const { - iter_difference_t<_Ip> __n = 0; - while (__first != __last) { - ++__first; - ++__n; - } - return __n; + return std::__distance(std::move(__first), std::move(__last)); } template <class _Ip, sized_sentinel_for<decay_t<_Ip>> _Sp> @@ -92,4 +117,6 @@ inline constexpr auto distance = __distance{}; _LIBCPP_END_NAMESPACE_STD +_LIBCPP_POP_MACROS + #endif // _LIBCPP___ITERATOR_DISTANCE_H diff --git a/libcxx/include/__memory/array_cookie.h b/libcxx/include/__memory/array_cookie.h index 806a9e9..be59f36 100644 --- a/libcxx/include/__memory/array_cookie.h +++ b/libcxx/include/__memory/array_cookie.h @@ -13,6 +13,7 @@ #include <__config> #include <__configuration/abi.h> #include <__cstddef/size_t.h> +#include <__memory/addressof.h> #include <__type_traits/integral_constant.h> #include <__type_traits/is_trivially_destructible.h> #include <__type_traits/negation.h> @@ -26,14 +27,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD // Trait representing whether a type requires an array cookie at the start of its allocation when // allocated as `new T[n]` and deallocated as `delete[] array`. // -// Under the Itanium C++ ABI [1], we know that an array cookie is available unless `T` is trivially -// destructible and the call to `operator delete[]` is not a sized operator delete. Under ABIs other -// than the Itanium ABI, we assume there are no array cookies. +// Under the Itanium C++ ABI [1] and the ARM ABI which derives from it, we know that an array cookie is available +// unless `T` is trivially destructible and the call to `operator delete[]` is not a sized operator delete. Under +// other ABIs, we assume there are no array cookies. // // [1]: https://itanium-cxx-abi.github.io/cxx-abi/abi.html#array-cookies -#ifdef _LIBCPP_ABI_ITANIUM +#if defined(_LIBCPP_ABI_ITANIUM) || defined(_LIBCPP_ABI_ITANIUM_WITH_ARM_DIFFERENCES) // TODO: Use a builtin instead -// TODO: We should factor in the choice of the usual deallocation function in this determination. +// TODO: We should factor in the choice of the usual deallocation function in this determination: +// a cookie may be available in more cases but we ignore those for now. template <class _Tp> struct __has_array_cookie : _Not<is_trivially_destructible<_Tp> > {}; #else @@ -41,13 +43,79 @@ template <class _Tp> struct __has_array_cookie : false_type {}; #endif +struct __itanium_array_cookie { + size_t __element_count; +}; + +template <class _Tp> +struct [[__gnu__::__aligned__(_LIBCPP_ALIGNOF(_Tp))]] __arm_array_cookie { + size_t __element_size; + size_t __element_count; +}; + +// Return the element count in the array cookie located before the given pointer. +// +// In the Itanium ABI [1] +// ---------------------- +// The element count is stored immediately before the first element of the array. If the preferred alignment +// of array elements (which is different from the ABI alignment) is more than that of size_t, additional +// padding bytes exist before the array cookie. Assuming array elements of size and alignment 16 bytes, that +// gives us the following layout: +// +// |ooooooooxxxxxxxxaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbccccccccccccccccdddddddddddddddd| +// ^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +// | ^^^^^^^^ | +// | | array elements +// padding | +// element count +// +// +// In the Itanium ABI with ARM differences [2] +// ------------------------------------------- +// The array cookie is stored at the very start of the allocation and it has the following form: +// +// struct array_cookie { +// std::size_t element_size; // element_size != 0 +// std::size_t element_count; +// }; +// +// Assuming elements of size and alignment 32 bytes, this gives us the following layout: +// +// |xxxxxxxxXXXXXXXXooooooooooooooooaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb| +// ^^^^^^^^ ^^^^^^^^^^^^^^^^ +// | ^^^^^^^^ | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +// element size | padding | +// element count array elements +// +// We must be careful to take into account the alignment of the array cookie, which may result in padding +// bytes between the element count and the first element of the array. Note that for ARM, the compiler +// aligns the array cookie using the ABI alignment, not the preferred alignment of array elements. +// +// [1]: https://itanium-cxx-abi.github.io/cxx-abi/abi.html#array-cookies +// [2]: https://developer.apple.com/documentation/xcode/writing-arm64-code-for-apple-platforms#Handle-C++-differences template <class _Tp> // Avoid failures when -fsanitize-address-poison-custom-array-cookie is enabled -_LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_SANITIZE("address") size_t __get_array_cookie(_Tp const* __ptr) { +_LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_SANITIZE("address") size_t __get_array_cookie([[__maybe_unused__]] _Tp const* __ptr) { static_assert( __has_array_cookie<_Tp>::value, "Trying to access the array cookie of a type that is not guaranteed to have one"); - size_t const* __cookie = reinterpret_cast<size_t const*>(__ptr) - 1; // TODO: Use a builtin instead - return *__cookie; + +#if defined(_LIBCPP_ABI_ITANIUM) + using _ArrayCookie = __itanium_array_cookie; +#elif defined(_LIBCPP_ABI_ITANIUM_WITH_ARM_DIFFERENCES) + using _ArrayCookie = __arm_array_cookie<_Tp>; +#else + static_assert(false, "The array cookie layout is unknown on this ABI"); + struct _ArrayCookie { // dummy definition required to make the function parse + size_t element_count; + }; +#endif + + char const* __array_cookie_start = reinterpret_cast<char const*>(__ptr) - sizeof(_ArrayCookie); + _ArrayCookie __cookie; + // This is necessary to avoid violating strict aliasing. It's valid because _ArrayCookie is an + // implicit lifetime type. + __builtin_memcpy(std::addressof(__cookie), __array_cookie_start, sizeof(_ArrayCookie)); + return __cookie.__element_count; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__tree b/libcxx/include/__tree index d7d074a0..0738c8c 100644 --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -1119,15 +1119,15 @@ public: _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&&); template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); - template <class _Tree> - _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Tree& __source); + template <class _Comp2> + _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(__tree<_Tp, _Comp2, _Allocator>& __source); template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&&); template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); - template <class _Tree> - _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Tree& __source); + template <class _Comp2> + _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(__tree<_Tp, _Comp2, _Allocator>& __source); template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const&); @@ -2020,11 +2020,10 @@ _LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_hand } template <class _Tp, class _Compare, class _Allocator> -template <class _Tree> -_LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) { - static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); - - for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) { +template <class _Comp2> +_LIBCPP_HIDE_FROM_ABI void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(__tree<_Tp, _Comp2, _Allocator>& __source) { + for (iterator __i = __source.begin(); __i != __source.end();) { __node_pointer __src_ptr = __i.__get_np(); auto [__parent, __child] = __find_equal(__src_ptr->__get_value()); ++__i; @@ -2065,11 +2064,10 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(const_iterator __h } template <class _Tp, class _Compare, class _Allocator> -template <class _Tree> -_LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) { - static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); - - for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) { +template <class _Comp2> +_LIBCPP_HIDE_FROM_ABI void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(__tree<_Tp, _Comp2, _Allocator>& __source) { + for (iterator __i = __source.begin(); __i != __source.end();) { __node_pointer __src_ptr = __i.__get_np(); __end_node_pointer __parent; __node_base_pointer& __child = __find_leaf_high(__parent, __src_ptr->__get_value()); diff --git a/libcxx/include/__utility/cmp.h b/libcxx/include/__utility/cmp.h index 14dc0c1..68864e2 100644 --- a/libcxx/include/__utility/cmp.h +++ b/libcxx/include/__utility/cmp.h @@ -26,10 +26,18 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER >= 20 +template <typename _Tp, typename _Ip> +concept __comparison_can_promote_to = + sizeof(_Tp) < sizeof(_Ip) || (sizeof(_Tp) == sizeof(_Ip) && __signed_integer<_Tp>); + template <__signed_or_unsigned_integer _Tp, __signed_or_unsigned_integer _Up> _LIBCPP_HIDE_FROM_ABI constexpr bool cmp_equal(_Tp __t, _Up __u) noexcept { if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>) return __t == __u; + else if constexpr (__comparison_can_promote_to<_Tp, int> && __comparison_can_promote_to<_Up, int>) + return static_cast<int>(__t) == static_cast<int>(__u); + else if constexpr (__comparison_can_promote_to<_Tp, long long> && __comparison_can_promote_to<_Up, long long>) + return static_cast<long long>(__t) == static_cast<long long>(__u); else if constexpr (is_signed_v<_Tp>) return __t < 0 ? false : make_unsigned_t<_Tp>(__t) == __u; else @@ -45,6 +53,10 @@ template <__signed_or_unsigned_integer _Tp, __signed_or_unsigned_integer _Up> _LIBCPP_HIDE_FROM_ABI constexpr bool cmp_less(_Tp __t, _Up __u) noexcept { if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>) return __t < __u; + else if constexpr (__comparison_can_promote_to<_Tp, int> && __comparison_can_promote_to<_Up, int>) + return static_cast<int>(__t) < static_cast<int>(__u); + else if constexpr (__comparison_can_promote_to<_Tp, long long> && __comparison_can_promote_to<_Up, long long>) + return static_cast<long long>(__t) < static_cast<long long>(__u); else if constexpr (is_signed_v<_Tp>) return __t < 0 ? true : make_unsigned_t<_Tp>(__t) < __u; else |