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/vector | 8 | ||||
| -rw-r--r-- | libcxx/include/__memory/array_cookie.h | 84 | ||||
| -rw-r--r-- | libcxx/include/__tree | 26 |
7 files changed, 178 insertions, 49 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/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/__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()); |