diff options
Diffstat (limited to 'libcxx')
18 files changed, 334 insertions, 59 deletions
diff --git a/libcxx/docs/ReleaseNotes/21.rst b/libcxx/docs/ReleaseNotes/21.rst index 642bf7d..2b1aa28 100644 --- a/libcxx/docs/ReleaseNotes/21.rst +++ b/libcxx/docs/ReleaseNotes/21.rst @@ -53,8 +53,7 @@ Implemented Papers - P2711R1: Making multi-param constructors of ``views`` ``explicit`` (`Github <https://github.com/llvm/llvm-project/issues/105252>`__) - P2770R0: Stashing stashing ``iterators`` for proper flattening (`Github <https://github.com/llvm/llvm-project/issues/105250>`__) - P2655R3: ``common_reference_t`` of ``reference_wrapper`` Should Be a Reference Type (`Github <https://github.com/llvm/llvm-project/issues/105260>`__) -- P2944R3: Comparisons for ``reference_wrapper`` (`Github <https://github.com/llvm/llvm-project/issues/105424>`__) -- P3379R0: Constrain ``std::expected equality`` operators (`Github <https://github.com/llvm/llvm-project/issues/118135>`__) +- P3379R0: Constrain ``std::expected`` equality operators (`Github <https://github.com/llvm/llvm-project/issues/118135>`__) Improvements and New Features ----------------------------- diff --git a/libcxx/docs/ReleaseNotes/22.rst b/libcxx/docs/ReleaseNotes/22.rst index 5e8fe2e..1a7a2c7 100644 --- a/libcxx/docs/ReleaseNotes/22.rst +++ b/libcxx/docs/ReleaseNotes/22.rst @@ -44,6 +44,7 @@ Implemented Papers - P3223R2: Making ``std::istream::ignore`` less surprising (`Github <https://llvm.org/PR148178>`__) - P3060R3: Add ``std::views::indices(n)`` (`Github <https://llvm.org/PR148175>`__) - P2835R7: Expose ``std::atomic_ref``'s object address (`Github <https://llvm.org/PR118377>`__) +- P2944R3: Comparisons for ``reference_wrapper`` (`Github <https://llvm.org/PR105424>`__) - P3168R2: Give ``std::optional`` Range Support (`Github <https://llvm.org/PR105430>`__) Improvements and New Features @@ -71,6 +72,9 @@ Improvements and New Features - The ``std::distance`` and ``std::ranges::distance`` algorithms have been optimized for segmented iterators (e.g., ``std::join_view`` iterators), reducing the complexity from ``O(n)`` to ``O(n / segment_size)``. Benchmarks show performance improvements of over 1600x in favorable cases with large segment sizes (e.g., 1024). +- The ``std::{fill, fill_n}`` and ``std::ranges::{fill, fill_n}`` algorithms have been optimized for segmented iterators, + resulting in a performance improvement of at least 10x for ``std::deque<int>`` iterators and + ``std::join_view<std::vector<std::vector<int>>>`` iterators. Deprecations and Removals ------------------------- diff --git a/libcxx/docs/Status/Cxx2cIssues.csv b/libcxx/docs/Status/Cxx2cIssues.csv index 7bf7bc9..237217a 100644 --- a/libcxx/docs/Status/Cxx2cIssues.csv +++ b/libcxx/docs/Status/Cxx2cIssues.csv @@ -149,5 +149,5 @@ "`LWG3343 <https://wg21.link/LWG3343>`__","Ordering of calls to ``unlock()`` and ``notify_all()`` in Effects element of ``notify_all_at_thread_exit()`` should be reversed","Not Adopted Yet","|Complete|","16","`#105356 <https://github.com/llvm/llvm-project/issues/105356>`__","" "`LWG4139 <https://wg21.link/LWG4139>`__","ยง[time.zone.leap] recursive constraint in ``<=>``","Not Adopted Yet","|Complete|","20","`#118369 <https://github.com/llvm/llvm-project/issues/118369>`__","" "`LWG3456 <https://wg21.link/LWG3456>`__","Pattern used by ``std::from_chars`` is underspecified (option B)","Not Adopted Yet","|Complete|","20","`#118370 <https://github.com/llvm/llvm-project/issues/118370>`__","" -"`LWG3882 <https://wg21.link/LWG3882>`__","``tuple`` relational operators have confused friendships","Not Adopted Yet","|Complete|","21","The comparsion operators are constrained harder than the proposed resolution. libstdc++ and MSVC STL do the same.","" +"`LWG3882 <https://wg21.link/LWG3882>`__","``tuple`` relational operators have confused friendships","Not Adopted Yet","|Complete|","22","The comparsion operators are constrained harder than the proposed resolution. libstdc++ and MSVC STL do the same.","" "","","","","","" diff --git a/libcxx/docs/Status/Cxx2cPapers.csv b/libcxx/docs/Status/Cxx2cPapers.csv index 9b83047..0eedc82 100644 --- a/libcxx/docs/Status/Cxx2cPapers.csv +++ b/libcxx/docs/Status/Cxx2cPapers.csv @@ -59,7 +59,7 @@ "`P2248R8 <https://wg21.link/P2248R8>`__","Enabling list-initialization for algorithms","2024-03 (Tokyo)","","","`#105421 <https://github.com/llvm/llvm-project/issues/105421>`__","" "`P2810R4 <https://wg21.link/P2810R4>`__","``is_debugger_present`` ``is_replaceable``","2024-03 (Tokyo)","","","`#105422 <https://github.com/llvm/llvm-project/issues/105422>`__","" "`P1068R11 <https://wg21.link/P1068R11>`__","Vector API for random number generation","2024-03 (Tokyo)","","","`#105423 <https://github.com/llvm/llvm-project/issues/105423>`__","" -"`P2944R3 <https://wg21.link/P2944R3>`__","Comparisons for ``reference_wrapper``","2024-03 (Tokyo)","|Complete|","21","`#105424 <https://github.com/llvm/llvm-project/issues/105424>`__","The changes to ``tuple``'s equality overload from P2165R4 are not yet implemented." +"`P2944R3 <https://wg21.link/P2944R3>`__","Comparisons for ``reference_wrapper``","2024-03 (Tokyo)","|Complete|","22","`#105424 <https://github.com/llvm/llvm-project/issues/105424>`__","The changes to ``tuple``'s equality overload from P2165R4 are not yet implemented." "`P2642R6 <https://wg21.link/P2642R6>`__","Padded ``mdspan`` layouts","2024-03 (Tokyo)","","","`#105425 <https://github.com/llvm/llvm-project/issues/105425>`__","" "`P3029R1 <https://wg21.link/P3029R1>`__","Better ``mdspan``'s CTAD","2024-03 (Tokyo)","|Complete|","19","`#105426 <https://github.com/llvm/llvm-project/issues/105426>`__","" "","","","","","" 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()); diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp index 9b403db..b0a74b8 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp @@ -17,6 +17,8 @@ #include <array> #include <cassert> #include <cstddef> +#include <deque> +#include <ranges> #include <vector> #include "sized_allocator.h" @@ -93,6 +95,13 @@ TEST_CONSTEXPR_CXX20 bool test_vector_bool(std::size_t N) { return true; } +/*TEST_CONSTEXPR_CXX26*/ void test_deque() { // TODO: Mark as TEST_CONSTEXPR_CXX26 once std::deque is constexpr + std::deque<int> in(20); + std::deque<int> expected(in.size(), 42); + std::fill(in.begin(), in.end(), 42); + assert(in == expected); +} + TEST_CONSTEXPR_CXX20 bool test() { types::for_each(types::forward_iterator_list<char*>(), Test<char>()); types::for_each(types::forward_iterator_list<int*>(), Test<int>()); @@ -138,6 +147,20 @@ TEST_CONSTEXPR_CXX20 bool test() { } } + if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED when std::deque is made constexpr + test_deque(); + +#if TEST_STD_VER >= 20 + { // Verify that join_view of vectors work properly. + std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}}; + auto jv = std::ranges::join_view(v); + std::fill(jv.begin(), jv.end(), 42); + for (const auto& vec : v) + for (auto n : vec) + assert(n == 42); + } +#endif + return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp index e42172c..5dc9b90 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp @@ -17,6 +17,8 @@ #include <array> #include <cassert> #include <cstddef> +#include <deque> +#include <ranges> #include <vector> #include "sized_allocator.h" @@ -126,6 +128,13 @@ TEST_CONSTEXPR_CXX20 bool test_vector_bool(std::size_t N) { return true; } +/*TEST_CONSTEXPR_CXX26*/ void test_deque() { // TODO: Mark as TEST_CONSTEXPR_CXX26 once std::deque is constexpr + std::deque<int> in(20); + std::deque<int> expected(in.size(), 42); + std::fill_n(in.begin(), in.size(), 42); + assert(in == expected); +} + TEST_CONSTEXPR_CXX20 bool test() { types::for_each(types::forward_iterator_list<char*>(), Test<char>()); types::for_each(types::forward_iterator_list<int*>(), Test<int>()); @@ -221,6 +230,20 @@ TEST_CONSTEXPR_CXX20 bool test() { } } + if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED when std::deque is made constexpr + test_deque(); + +#if TEST_STD_VER >= 20 + { + std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}}; + auto jv = std::ranges::join_view(v); + std::fill_n(jv.begin(), std::distance(jv.begin(), jv.end()), 42); + for (const auto& vec : v) + for (auto n : vec) + assert(n == 42); + } +#endif + return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp index 61a659f..7ae0a06 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp @@ -18,6 +18,7 @@ #include <algorithm> #include <array> #include <cassert> +#include <deque> #include <ranges> #include <string> #include <vector> @@ -128,6 +129,13 @@ constexpr bool test_vector_bool(std::size_t N) { } #endif +/*TEST_CONSTEXPR_CXX26*/ void test_deque() { // TODO: Mark as TEST_CONSTEXPR_CXX26 once std::deque is constexpr + std::deque<int> in(20); + std::deque<int> expected(in.size(), 42); + std::ranges::fill(in, 42); + assert(in == expected); +} + constexpr bool test() { test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>(); test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>(); @@ -227,6 +235,20 @@ constexpr bool test() { } #endif + if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED when std::deque is made constexpr + test_deque(); + +#if TEST_STD_VER >= 20 + { + std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}}; + auto jv = std::ranges::join_view(v); + std::ranges::fill(jv, 42); + for (const auto& vec : v) + for (auto n : vec) + assert(n == 42); + } +#endif + return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp index 2d6e24a..25db892 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp @@ -16,6 +16,7 @@ #include <algorithm> #include <array> #include <cassert> +#include <deque> #include <ranges> #include <string> #include <vector> @@ -101,6 +102,13 @@ constexpr bool test_vector_bool(std::size_t N) { } #endif +/*TEST_CONSTEXPR_CXX26*/ void test_deque() { // TODO: Mark as TEST_CONSTEXPR_CXX26 once std::deque is constexpr + std::deque<int> in(20); + std::deque<int> expected(in.size(), 42); + std::ranges::fill_n(std::ranges::begin(in), std::ranges::size(in), 42); + assert(in == expected); +} + constexpr bool test() { test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>(); test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>(); @@ -175,6 +183,20 @@ constexpr bool test() { } #endif + if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED when std::deque is made constexpr + test_deque(); + +#if TEST_STD_VER >= 20 + { + std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}}; + auto jv = std::ranges::join_view(v); + std::ranges::fill_n(std::ranges::begin(jv), std::ranges::distance(jv), 42); + for (const auto& vec : v) + for (auto n : vec) + assert(n == 42); + } +#endif + return true; } diff --git a/libcxx/test/std/containers/sequences/vector.bool/shrink_to_fit.pass.cpp b/libcxx/test/std/containers/sequences/vector.bool/shrink_to_fit.pass.cpp index 665867a..bf17733 100644 --- a/libcxx/test/std/containers/sequences/vector.bool/shrink_to_fit.pass.cpp +++ b/libcxx/test/std/containers/sequences/vector.bool/shrink_to_fit.pass.cpp @@ -11,8 +11,6 @@ // void shrink_to_fit(); -// XFAIL: FROZEN-CXX03-HEADERS-FIXME - #include <cassert> #include <climits> #include <vector> diff --git a/libcxx/test/std/utilities/smartptr/unique.ptr/unique.ptr.class/unique.ptr.observers/assert.subscript.pass.cpp b/libcxx/test/std/utilities/smartptr/unique.ptr/unique.ptr.class/unique.ptr.observers/assert.subscript.pass.cpp index b7cc123..f7390ef 100644 --- a/libcxx/test/std/utilities/smartptr/unique.ptr/unique.ptr.class/unique.ptr.observers/assert.subscript.pass.cpp +++ b/libcxx/test/std/utilities/smartptr/unique.ptr/unique.ptr.class/unique.ptr.observers/assert.subscript.pass.cpp @@ -58,15 +58,18 @@ void test() { { { std::unique_ptr<WithCookie[]> ptr(new WithCookie[5]); + assert(&ptr[1] == ptr.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(ptr[6], "unique_ptr<T[]>::operator[](index): index out of range"); } { std::unique_ptr<WithCookie[]> ptr = std::make_unique<WithCookie[]>(5); + assert(&ptr[1] == ptr.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(ptr[6], "unique_ptr<T[]>::operator[](index): index out of range"); } #if TEST_STD_VER >= 20 { std::unique_ptr<WithCookie[]> ptr = std::make_unique_for_overwrite<WithCookie[]>(5); + assert(&ptr[1] == ptr.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(ptr[6] = WithCookie(), "unique_ptr<T[]>::operator[](index): index out of range"); } #endif @@ -82,11 +85,13 @@ void test() { { { std::unique_ptr<NoCookie[]> ptr = std::make_unique<NoCookie[]>(5); + assert(&ptr[1] == ptr.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(ptr[6], "unique_ptr<T[]>::operator[](index): index out of range"); } # if TEST_STD_VER >= 20 { std::unique_ptr<NoCookie[]> ptr = std::make_unique_for_overwrite<NoCookie[]>(5); + assert(&ptr[1] == ptr.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(ptr[6] = NoCookie(), "unique_ptr<T[]>::operator[](index): index out of range"); } # endif @@ -101,6 +106,7 @@ void test() { { std::unique_ptr<T[]> ptr = std::make_unique<T[]>(5); std::unique_ptr<T[]> other(std::move(ptr)); + assert(&other[1] == other.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(other[6], "unique_ptr<T[]>::operator[](index): index out of range"); } @@ -109,6 +115,7 @@ void test() { std::unique_ptr<T[]> ptr = std::make_unique<T[]>(5); std::unique_ptr<T[]> other; other = std::move(ptr); + assert(&other[1] == other.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(other[6], "unique_ptr<T[]>::operator[](index): index out of range"); } @@ -116,6 +123,7 @@ void test() { { std::unique_ptr<T[]> ptr = std::make_unique<T[]>(5); std::unique_ptr<T[], MyDeleter> other(std::move(ptr)); + assert(&other[1] == other.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(other[6], "unique_ptr<T[]>::operator[](index): index out of range"); } @@ -124,6 +132,7 @@ void test() { std::unique_ptr<T[]> ptr = std::make_unique<T[]>(5); std::unique_ptr<T[], MyDeleter> other; other = std::move(ptr); + assert(&other[1] == other.get() + 1); // ensure no assertion TEST_LIBCPP_ASSERT_FAILURE(other[6], "unique_ptr<T[]>::operator[](index): index out of range"); } }); @@ -144,6 +153,34 @@ struct WithCookie { char padding[Size]; }; +template <std::size_t Size> +struct alignas(128) OveralignedNoCookie { + char padding[Size]; +}; + +template <std::size_t Size> +struct alignas(128) OveralignedWithCookie { + OveralignedWithCookie() = default; + OveralignedWithCookie(OveralignedWithCookie const&) {} + OveralignedWithCookie& operator=(OveralignedWithCookie const&) { return *this; } + ~OveralignedWithCookie() {} + char padding[Size]; +}; + +// These types have a different ABI alignment (alignof) and preferred alignment (__alignof) on some platforms. +// Make sure things work with these types because array cookies can be sensitive to preferred alignment on some +// platforms. +struct WithCookiePreferredAlignment { + WithCookiePreferredAlignment() = default; + WithCookiePreferredAlignment(WithCookiePreferredAlignment const&) {} + WithCookiePreferredAlignment& operator=(WithCookiePreferredAlignment const&) { return *this; } + ~WithCookiePreferredAlignment() {} + long double data; +}; +struct NoCookiePreferredAlignment { + long double data; +}; + int main(int, char**) { test<WithCookie<1>, NoCookie<1>>(); test<WithCookie<2>, NoCookie<2>>(); @@ -153,7 +190,18 @@ int main(int, char**) { test<WithCookie<16>, NoCookie<16>>(); test<WithCookie<32>, NoCookie<32>>(); test<WithCookie<256>, NoCookie<256>>(); + + test<OveralignedWithCookie<1>, OveralignedNoCookie<1>>(); + test<OveralignedWithCookie<2>, OveralignedNoCookie<2>>(); + test<OveralignedWithCookie<3>, OveralignedNoCookie<3>>(); + test<OveralignedWithCookie<4>, OveralignedNoCookie<4>>(); + test<OveralignedWithCookie<8>, OveralignedNoCookie<8>>(); + test<OveralignedWithCookie<16>, OveralignedNoCookie<16>>(); + test<OveralignedWithCookie<32>, OveralignedNoCookie<32>>(); + test<OveralignedWithCookie<256>, OveralignedNoCookie<256>>(); + test<std::string, int>(); + test<WithCookiePreferredAlignment, NoCookiePreferredAlignment>(); return 0; } diff --git a/libcxx/utils/compare-benchmarks b/libcxx/utils/compare-benchmarks index 988e243..d165c73 100755 --- a/libcxx/utils/compare-benchmarks +++ b/libcxx/utils/compare-benchmarks @@ -65,9 +65,16 @@ def plain_text_comparison(data, metric, baseline_name=None, candidate_name=None) """ data = data.replace(numpy.nan, None) # avoid NaNs in tabulate output headers = ['Benchmark', baseline_name, candidate_name, 'Difference', '% Difference'] - fmt = (None, '.2f', '.2f', '.2f', '.2f') - table = data[['benchmark', f'{metric}_0', f'{metric}_1', 'difference', 'percent']].set_index('benchmark') - return tabulate.tabulate(table, headers=headers, floatfmt=fmt, numalign='right') + fmt = (None, '.2f', '.2f', '.2f', '.2%') + table = data[['benchmark', f'{metric}_0', f'{metric}_1', 'difference', 'percent']] + + # Compute the geomean and report on their difference + geomean_0 = statistics.geometric_mean(data[f'{metric}_0'].dropna()) + geomean_1 = statistics.geometric_mean(data[f'{metric}_1'].dropna()) + geomean_row = ['Geomean', geomean_0, geomean_1, (geomean_1 - geomean_0), (geomean_1 - geomean_0) / geomean_0] + table.loc[table.index.max()] = geomean_row + + return tabulate.tabulate(table.set_index('benchmark'), headers=headers, floatfmt=fmt, numalign='right') def create_chart(data, metric, subtitle=None, series_names=None): """ @@ -154,7 +161,7 @@ def main(argv): # If we have exactly two data sets, compute additional info in new columns if len(lnt_inputs) == 2: data['difference'] = data[f'{args.metric}_1'] - data[f'{args.metric}_0'] - data['percent'] = 100 * (data['difference'] / data[f'{args.metric}_0']) + data['percent'] = data['difference'] / data[f'{args.metric}_0'] if args.filter is not None: keeplist = [b for b in data['benchmark'] if re.search(args.filter, b) is not None] |