diff options
Diffstat (limited to 'libcxx')
19 files changed, 184 insertions, 108 deletions
diff --git a/libcxx/docs/ReleaseNotes/22.rst b/libcxx/docs/ReleaseNotes/22.rst index ada8b41..25d33a9 100644 --- a/libcxx/docs/ReleaseNotes/22.rst +++ b/libcxx/docs/ReleaseNotes/22.rst @@ -62,6 +62,7 @@ Improvements and New Features has been improved by up to 3x - The performance of ``insert(iterator, iterator)`` of ``map``, ``set``, ``multimap`` and ``multiset`` has been improved by up to 2.5x +- The performance of ``erase(iterator, iterator)`` in the unordered containers has been improved by up to 1.9x - The performance of ``map::insert_or_assign`` has been improved by up to 2x - ``ofstream::write`` has been optimized to pass through large strings to system calls directly instead of copying them in chunks into a buffer. @@ -75,8 +76,8 @@ Improvements and New Features - 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. -- The ``std::generate`` algorithm has been optimized for segmented iterators, resulting in a performance improvement for - ``std::deque<short>`` and ``std::join_view<vector<vector<short>>>`` iterators. +- The ``std::generate`` and ``std::generate_n`` algorithms have been optimized for segmented iterators, resulting in a + performance improvement for ``std::deque<short>`` and ``std::join_view<vector<vector<short>>>`` iterators. Deprecations and Removals ------------------------- diff --git a/libcxx/include/__algorithm/for_each.h b/libcxx/include/__algorithm/for_each.h index e31fcae..6fb66d2 100644 --- a/libcxx/include/__algorithm/for_each.h +++ b/libcxx/include/__algorithm/for_each.h @@ -16,15 +16,11 @@ #include <__iterator/segmented_iterator.h> #include <__type_traits/enable_if.h> #include <__type_traits/invoke.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 _InputIterator, class _Sent, class _Func, class _Proj> @@ -60,6 +56,4 @@ for_each(_InputIterator __first, _InputIterator __last, _Func __f) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FOR_EACH_H diff --git a/libcxx/include/__algorithm/generate_n.h b/libcxx/include/__algorithm/generate_n.h index f36403f..e9da133 100644 --- a/libcxx/include/__algorithm/generate_n.h +++ b/libcxx/include/__algorithm/generate_n.h @@ -9,8 +9,10 @@ #ifndef _LIBCPP___ALGORITHM_GENERATE_N_H #define _LIBCPP___ALGORITHM_GENERATE_N_H +#include <__algorithm/for_each_n.h> #include <__config> -#include <__utility/convert_to_integral.h> +#include <__functional/identity.h> +#include <__utility/forward.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,11 +23,10 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _OutputIterator, class _Size, class _Generator> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen) { - typedef decltype(std::__convert_to_integral(__orig_n)) _IntegralSize; - _IntegralSize __n = __orig_n; - for (; __n > 0; ++__first, (void)--__n) - *__first = __gen(); - return __first; + using __iter_ref = decltype(*__first); + __identity __proj; + auto __f = [&](__iter_ref __element) { std::forward<__iter_ref>(__element) = __gen(); }; + return std::__for_each_n(__first, __orig_n, __f, __proj); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__compare/strong_order.h b/libcxx/include/__compare/strong_order.h index 8c363b5..ba6de44 100644 --- a/libcxx/include/__compare/strong_order.h +++ b/libcxx/include/__compare/strong_order.h @@ -13,7 +13,6 @@ #include <__compare/compare_three_way.h> #include <__compare/ordering.h> #include <__config> -#include <__math/exponential_functions.h> #include <__math/traits.h> #include <__type_traits/conditional.h> #include <__type_traits/decay.h> @@ -53,38 +52,21 @@ struct __fn { template <class _Tp, class _Up, class _Dp = decay_t<_Tp>> requires is_same_v<_Dp, decay_t<_Up>> && is_floating_point_v<_Dp> _LIBCPP_HIDE_FROM_ABI static constexpr strong_ordering __go(_Tp&& __t, _Up&& __u, __priority_tag<1>) noexcept { - if constexpr (numeric_limits<_Dp>::is_iec559 && sizeof(_Dp) == sizeof(int32_t)) { - int32_t __rx = std::bit_cast<int32_t>(__t); - int32_t __ry = std::bit_cast<int32_t>(__u); - __rx = (__rx < 0) ? (numeric_limits<int32_t>::min() - __rx - 1) : __rx; - __ry = (__ry < 0) ? (numeric_limits<int32_t>::min() - __ry - 1) : __ry; - return (__rx <=> __ry); - } else if constexpr (numeric_limits<_Dp>::is_iec559 && sizeof(_Dp) == sizeof(int64_t)) { - int64_t __rx = std::bit_cast<int64_t>(__t); - int64_t __ry = std::bit_cast<int64_t>(__u); - __rx = (__rx < 0) ? (numeric_limits<int64_t>::min() - __rx - 1) : __rx; - __ry = (__ry < 0) ? (numeric_limits<int64_t>::min() - __ry - 1) : __ry; + if constexpr (numeric_limits<_Dp>::is_iec559 && + (sizeof(_Dp) == sizeof(int32_t) || sizeof(_Dp) == sizeof(int64_t))) { + using _IntT = conditional_t<sizeof(_Dp) == sizeof(int32_t), int32_t, int64_t>; + _IntT __rx = std::bit_cast<_IntT>(__t); + _IntT __ry = std::bit_cast<_IntT>(__u); + __rx = (__rx < 0) ? (numeric_limits<_IntT>::min() - __rx - 1) : __rx; + __ry = (__ry < 0) ? (numeric_limits<_IntT>::min() - __ry - 1) : __ry; return (__rx <=> __ry); } else if (__t < __u) { return strong_ordering::less; } else if (__t > __u) { return strong_ordering::greater; } else if (__t == __u) { - if constexpr (numeric_limits<_Dp>::radix == 2) { - return __math::signbit(__u) <=> __math::signbit(__t); - } else { - // This is bullet 3 of the IEEE754 algorithm, relevant - // only for decimal floating-point; - // see https://stackoverflow.com/questions/69068075/ - if (__t == 0 || __math::isinf(__t)) { - return __math::signbit(__u) <=> __math::signbit(__t); - } else { - int __texp, __uexp; - (void)__math::frexp(__t, &__texp); - (void)__math::frexp(__u, &__uexp); - return (__t < 0) ? (__texp <=> __uexp) : (__uexp <=> __texp); - } - } + static_assert(numeric_limits<_Dp>::radix == 2, "floating point type with a radix other than 2?"); + return __math::signbit(__u) <=> __math::signbit(__t); } else { // They're unordered, so one of them must be a NAN. // The order is -QNAN, -SNAN, numbers, +SNAN, +QNAN. @@ -93,9 +75,9 @@ struct __fn { bool __t_is_negative = __math::signbit(__t); bool __u_is_negative = __math::signbit(__u); using _IntType = - conditional_t< sizeof(__t) == sizeof(int32_t), - int32_t, - conditional_t< sizeof(__t) == sizeof(int64_t), int64_t, void> >; + conditional_t<sizeof(__t) == sizeof(int32_t), + int32_t, + conditional_t<sizeof(__t) == sizeof(int64_t), int64_t, void>>; if constexpr (is_same_v<_IntType, void>) { static_assert(sizeof(_Dp) == 0, "std::strong_order is unimplemented for this floating-point type"); } else if (__t_is_nan && __u_is_nan) { diff --git a/libcxx/include/__cxx03/__algorithm/count.h b/libcxx/include/__cxx03/__algorithm/count.h index 5440fd0..5b05b4b 100644 --- a/libcxx/include/__cxx03/__algorithm/count.h +++ b/libcxx/include/__cxx03/__algorithm/count.h @@ -54,18 +54,18 @@ __count_bool(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) if (__first.__ctz_ != 0) { __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); __storage_type __dn = std::min(__clz_f, __n); - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __r = std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_) & __m); + __storage_type __m = (__storage_type(~0) << __first.__ctz_) & (__storage_type(~0) >> (__clz_f - __dn)); + __r = std::__libcpp_popcount<__storage_type>(std::__invert_if<!_ToCount>(*__first.__seg_) & __m); __n -= __dn; ++__first.__seg_; } // do middle whole words for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) - __r += std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_)); + __r += std::__libcpp_popcount<__storage_type>(std::__invert_if<!_ToCount>(*__first.__seg_)); // do last partial word if (__n > 0) { - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __r += std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_) & __m); + __storage_type __m = __storage_type(~0) >> (__bits_per_word - __n); + __r += std::__libcpp_popcount<__storage_type>(std::__invert_if<!_ToCount>(*__first.__seg_) & __m); } return __r; } diff --git a/libcxx/include/__cxx03/__algorithm/for_each.h b/libcxx/include/__cxx03/__algorithm/for_each.h index d160a9e..1ffb013 100644 --- a/libcxx/include/__cxx03/__algorithm/for_each.h +++ b/libcxx/include/__cxx03/__algorithm/for_each.h @@ -14,15 +14,11 @@ #include <__cxx03/__config> #include <__cxx03/__iterator/segmented_iterator.h> #include <__cxx03/__type_traits/enable_if.h> -#include <__cxx03/__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__cxx03/__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Function> @@ -34,6 +30,4 @@ _LIBCPP_HIDE_FROM_ABI _Function for_each(_InputIterator __first, _InputIterator _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___CXX03___ALGORITHM_FOR_EACH_H diff --git a/libcxx/include/__cxx03/__bit/popcount.h b/libcxx/include/__cxx03/__bit/popcount.h index 64404d2..a61a921 100644 --- a/libcxx/include/__cxx03/__bit/popcount.h +++ b/libcxx/include/__cxx03/__bit/popcount.h @@ -6,9 +6,6 @@ // //===----------------------------------------------------------------------===// -// TODO: __builtin_popcountg is available since Clang 19 and GCC 14. When support for older versions is dropped, we can -// refactor this code to exclusively use __builtin_popcountg. - #ifndef _LIBCPP___CXX03___BIT_POPCOUNT_H #define _LIBCPP___CXX03___BIT_POPCOUNT_H @@ -25,12 +22,9 @@ _LIBCPP_PUSH_MACROS _LIBCPP_BEGIN_NAMESPACE_STD -inline _LIBCPP_HIDE_FROM_ABI int __libcpp_popcount(unsigned __x) _NOEXCEPT { return __builtin_popcount(__x); } - -inline _LIBCPP_HIDE_FROM_ABI int __libcpp_popcount(unsigned long __x) _NOEXCEPT { return __builtin_popcountl(__x); } - -inline _LIBCPP_HIDE_FROM_ABI int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { - return __builtin_popcountll(__x); +template <class _Tp> +_LIBCPP_HIDE_FROM_ABI int __libcpp_popcount(_Tp __v) { + return __builtin_popcountg(__v); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table index 6b65e73..5432abb 100644 --- a/libcxx/include/__hash_table +++ b/libcxx/include/__hash_table @@ -1037,7 +1037,21 @@ private: } _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} - _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT; + _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__node_pointer __nd) _NOEXCEPT { + auto& __alloc = __node_alloc(); + __node_traits::destroy(__alloc, std::addressof(__nd->__get_value())); + std::__destroy_at(std::__to_address(__nd)); + __node_traits::deallocate(__alloc, __nd, 1); + } + + _LIBCPP_HIDE_FROM_ABI void __deallocate_node_list(__next_pointer __np) _NOEXCEPT { + while (__np != nullptr) { + __next_pointer __next = __np->__next_; + __deallocate_node(__np->__upcast()); + __np = __next; + } + } + _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT; template <class _From, class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0> @@ -1175,7 +1189,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() { static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible."); #endif - __deallocate_node(__first_node_.__next_); + __deallocate_node_list(__first_node_.__next_); } template <class _Tp, class _Hash, class _Equal, class _Alloc> @@ -1251,7 +1265,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __other) // At this point we either have consumed the whole incoming hash table, or we don't have any more nodes to reuse in // the destination. Either continue with constructing new nodes, or deallocate the left over nodes. if (__own_iter->__next_) { - __deallocate_node(__own_iter->__next_); + __deallocate_node_list(__own_iter->__next_); __own_iter->__next_ = nullptr; } else { __copy_construct(__other_iter, __own_iter, __current_chash); @@ -1263,19 +1277,6 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __other) } template <class _Tp, class _Hash, class _Equal, class _Alloc> -void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) _NOEXCEPT { - __node_allocator& __na = __node_alloc(); - while (__np != nullptr) { - __next_pointer __next = __np->__next_; - __node_pointer __real_np = __np->__upcast(); - __node_traits::destroy(__na, std::addressof(__real_np->__get_value())); - std::__destroy_at(std::addressof(*__real_np)); - __node_traits::deallocate(__na, __real_np, 1); - __np = __next; - } -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT { size_type __bc = bucket_count(); @@ -1318,7 +1319,7 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, max_load_factor() = __u.max_load_factor(); if (bucket_count() != 0) { __next_pointer __cache = __detach(); - auto __guard = std::__make_scope_guard([&] { __deallocate_node(__cache); }); + auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); }); const_iterator __i = __u.begin(); while (__cache != nullptr && __u.size() != 0) { __assign_value(__cache->__upcast()->__get_value(), std::move(__u.remove(__i++)->__get_value())); @@ -1353,7 +1354,7 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __ if (bucket_count() != 0) { __next_pointer __cache = __detach(); - auto __guard = std::__make_scope_guard([&] { __deallocate_node(__cache); }); + auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); }); for (; __cache != nullptr && __first != __last; ++__first) { __assign_value(__cache->__upcast()->__get_value(), *__first); __next_pointer __next = __cache->__next_; @@ -1374,7 +1375,7 @@ void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __f "__assign_multi may only be called with the containers value type or the nodes value type"); if (bucket_count() != 0) { __next_pointer __cache = __detach(); - auto __guard = std::__make_scope_guard([&] { __deallocate_node(__cache); }); + auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); }); for (; __cache != nullptr && __first != __last; ++__first) { __assign_value(__cache->__upcast()->__get_value(), *__first); __next_pointer __next = __cache->__next_; @@ -1413,7 +1414,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT { template <class _Tp, class _Hash, class _Equal, class _Alloc> void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT { if (size() > 0) { - __deallocate_node(__first_node_.__next_); + __deallocate_node_list(__first_node_.__next_); __first_node_.__next_ = nullptr; size_type __bc = bucket_count(); for (size_type __i = 0; __i < __bc; ++__i) @@ -1873,12 +1874,61 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) { template <class _Tp, class _Hash, class _Equal, class _Alloc> typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) { - for (const_iterator __p = __first; __first != __last; __p = __first) { - ++__first; - erase(__p); + if (__first == __last) + return iterator(__last.__node_); + + // current node + __next_pointer __current = __first.__node_; + size_type __bucket_count = bucket_count(); + size_t __chash = std::__constrain_hash(__current->__hash(), __bucket_count); + // find previous node + __next_pointer __before_first = __bucket_list_[__chash]; + for (; __before_first->__next_ != __current; __before_first = __before_first->__next_) + ; + + __next_pointer __last_node = __last.__node_; + + // If __before_first is in the same bucket (i.e. the first element we erase is not the first in the bucket), clear + // this bucket first without re-linking it + if (__before_first != __first_node_.__ptr() && + std::__constrain_hash(__before_first->__hash(), __bucket_count) == __chash) { + while (__current != __last_node) { + auto __next = __current->__next_; + __deallocate_node(__current->__upcast()); + __current = __next; + --__size_; + + if (__next) { + if (auto __next_chash = std::__constrain_hash(__next->__hash(), __bucket_count); __next_chash != __chash) { + __bucket_list_[__next_chash] = __before_first; + __chash = __next_chash; + break; + } + } + } + } + + while (__current != __last_node) { + auto __next = __current->__next_; + __deallocate_node(__current->__upcast()); + __current = __next; + --__size_; + + // When switching buckets, set the old bucket to be empty and update the next bucket to have __before_first as its + // before-first element + if (__next) { + if (auto __next_chash = std::__constrain_hash(__next->__hash(), __bucket_count); __next_chash != __chash) { + __bucket_list_[__chash] = nullptr; + __bucket_list_[__next_chash] = __before_first; + __chash = __next_chash; + } + } } - __next_pointer __np = __last.__node_; - return iterator(__np); + + // re-link __before_first with __last + __before_first->__next_ = __current; + + return iterator(__last.__node_); } template <class _Tp, class _Hash, class _Equal, class _Alloc> diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/generate_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/generate_n.pass.cpp index 13fd1cb..525737c 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/generate_n.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/generate_n.pass.cpp @@ -16,6 +16,7 @@ #include <algorithm> #include <cassert> +#include <deque> #include "test_iterators.h" #include "test_macros.h" @@ -71,12 +72,22 @@ test() test2<Iter, long double>(); } +void deque_test() { + int sizes[] = {0, 1, 2, 1023, 1024, 1025, 2047, 2048, 2049}; + for (const int size : sizes) { + std::deque<int> d(size); + std::generate_n(d.begin(), size, gen_test()); + assert(std::all_of(d.begin(), d.end(), [](int x) { return x == 2; })); + } +} + int main(int, char**) { test<forward_iterator<int*> >(); test<bidirectional_iterator<int*> >(); test<random_access_iterator<int*> >(); test<int*>(); + deque_test(); #if TEST_STD_VER > 17 static_assert(test_constexpr()); diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/count.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/count.pass.cpp index e696dcd..ffe3e0e 100644 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/count.pass.cpp +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.count/count.pass.cpp @@ -15,7 +15,6 @@ // ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=20000000 // ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=80000000 -// XFAIL: FROZEN-CXX03-HEADERS-FIXME #include <algorithm> #include <cassert> diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.cnstr/assign_copy.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.cnstr/assign_copy.pass.cpp index 3e4c5b1..c9a0fa1 100644 --- a/libcxx/test/std/containers/unord/unord.map/unord.map.cnstr/assign_copy.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.map/unord.map.cnstr/assign_copy.pass.cpp @@ -14,8 +14,6 @@ // unordered_map& operator=(const unordered_map& u); -// XFAIL: FROZEN-CXX03-HEADERS-FIXME - #include <algorithm> #include <cassert> #include <cfloat> @@ -270,7 +268,7 @@ void test_alloc(const Alloc& lhs_alloc = Alloc(), V rhs_arr[] = {V(10, 4), V(13, 5), V(12, 324), V(0, 54), V(50, 5), V(2, 5)}; Map copy(begin(rhs_arr), end(rhs_arr), 0, std::hash<int>(), std::equal_to<int>(), rhs_alloc); copy = orig; - LIBCPP_ASSERT(copy.bucket_count() == 5); + LIBCPP_NON_FROZEN_ASSERT(copy.bucket_count() == 5); assert(copy.size() == 4); assert(copy.at(1) == 1); assert(copy.at(2) == 3); diff --git a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.cnstr/assign_copy.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.cnstr/assign_copy.pass.cpp index 938b6be..beb67d8 100644 --- a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.cnstr/assign_copy.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.cnstr/assign_copy.pass.cpp @@ -14,8 +14,6 @@ // unordered_multimap& operator=(const unordered_multimap& u); -// XFAIL: FROZEN-CXX03-HEADERS-FIXME - #include <algorithm> #include <cassert> #include <cfloat> @@ -289,7 +287,7 @@ void test_alloc(const Alloc& lhs_alloc = Alloc(), V rhs_arr[] = {V(10, 4), V(13, 5), V(12, 324), V(0, 54), V(50, 5), V(2, 5)}; Map copy(begin(rhs_arr), end(rhs_arr), 0, std::hash<int>(), std::equal_to<int>(), rhs_alloc); copy = orig; - LIBCPP_ASSERT(copy.bucket_count() == 5); + LIBCPP_NON_FROZEN_ASSERT(copy.bucket_count() == 5); assert(copy.size() == 4); assert(copy.find(1)->second == 1); assert(copy.find(2)->second == 3); diff --git a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/erase_range.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/erase_range.pass.cpp index f8a2bdd..38b75c0 100644 --- a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/erase_range.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/erase_range.pass.cpp @@ -91,6 +91,37 @@ int main(int, char**) { assert(c.size() == 0); assert(k == c.end()); } + { // Make sure we're properly destroying the elements when erasing + { // When erasing part of a bucket + std::unordered_multimap<int, std::string> map; + map.insert(std::make_pair(1, "This is a long string to make sure ASan can detect a memory leak")); + map.insert(std::make_pair(1, "This is another long string to make sure ASan can detect a memory leak")); + map.erase(++map.begin(), map.end()); + } + { // When erasing the whole bucket + std::unordered_multimap<int, std::string> map; + map.insert(std::make_pair(1, "This is a long string to make sure ASan can detect a memory leak")); + map.insert(std::make_pair(1, "This is another long string to make sure ASan can detect a memory leak")); + map.erase(map.begin(), map.end()); + } + } + { // Make sure that we're properly updating the bucket list when starting within a bucket + struct MyHash { + size_t operator()(size_t v) const { return v; } + }; + std::unordered_multimap<size_t, size_t, MyHash> map; + size_t collision_val = 2 + map.bucket_count(); // try to get a bucket collision + map.rehash(3); + map.insert(std::pair<size_t, size_t>(1, 1)); + map.insert(std::pair<size_t, size_t>(collision_val, 1)); + map.insert(std::pair<size_t, size_t>(2, 1)); + LIBCPP_ASSERT(map.bucket(2) == map.bucket(collision_val)); + + auto erase = map.equal_range(2); + map.erase(erase.first, erase.second); + for (const auto& v : map) + assert(v.first == 1 || v.first == collision_val); + } #if TEST_STD_VER >= 11 { typedef std::unordered_multimap<int, diff --git a/libcxx/test/std/containers/unord/unord.multiset/erase_range.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/erase_range.pass.cpp index 62724fd..3bc686e 100644 --- a/libcxx/test/std/containers/unord/unord.multiset/erase_range.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.multiset/erase_range.pass.cpp @@ -47,6 +47,23 @@ int main(int, char**) { assert(c.size() == 0); assert(k == c.end()); } + { // Make sure that we're properly updating the bucket list when starting within a bucket + struct MyHash { + size_t operator()(size_t v) const { return v; } + }; + std::unordered_multiset<size_t, MyHash> map; + size_t collision_val = 2 + map.bucket_count(); // try to get a bucket collision + map.rehash(3); + map.insert(1); + map.insert(collision_val); + map.insert(2); + LIBCPP_ASSERT(map.bucket(2) == map.bucket(collision_val)); + + auto erase = map.equal_range(2); + map.erase(erase.first, erase.second); + for (const auto& v : map) + assert(v == 1 || v == collision_val); + } #if TEST_STD_VER >= 11 { typedef std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> C; diff --git a/libcxx/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_copy.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_copy.pass.cpp index e415253..5c85676 100644 --- a/libcxx/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_copy.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_copy.pass.cpp @@ -14,8 +14,6 @@ // unordered_multiset& operator=(const unordered_multiset& u); -// XFAIL: FROZEN-CXX03-HEADERS-FIXME - #include <algorithm> #include <cassert> #include <cfloat> @@ -259,7 +257,7 @@ void test_alloc(const Alloc& lhs_alloc = Alloc(), int rhs_arr[] = {10, 13, 12, 0, 50, 2}; Set copy(std::begin(rhs_arr), std::end(rhs_arr), 0, std::hash<int>(), std::equal_to<int>(), rhs_alloc); copy = orig; - LIBCPP_ASSERT(copy.bucket_count() == 5); + LIBCPP_NON_FROZEN_ASSERT(copy.bucket_count() == 5); assert(copy.size() == 4); assert(copy.count(1) == 1); assert(copy.count(2) == 1); diff --git a/libcxx/test/std/containers/unord/unord.set/unord.set.cnstr/assign_copy.pass.cpp b/libcxx/test/std/containers/unord/unord.set/unord.set.cnstr/assign_copy.pass.cpp index 9828b8b..30e12e2 100644 --- a/libcxx/test/std/containers/unord/unord.set/unord.set.cnstr/assign_copy.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.set/unord.set.cnstr/assign_copy.pass.cpp @@ -14,8 +14,6 @@ // unordered_set& operator=(const unordered_set& u); -// XFAIL: FROZEN-CXX03-HEADERS-FIXME - #include <algorithm> #include <cassert> #include <cfloat> @@ -262,7 +260,7 @@ void test_alloc(const Alloc& lhs_alloc = Alloc(), int rhs_arr[] = {10, 13, 12, 0, 50, 2}; Set copy(std::begin(rhs_arr), std::end(rhs_arr), 0, std::hash<int>(), std::equal_to<int>(), rhs_alloc); copy = orig; - LIBCPP_ASSERT(copy.bucket_count() == 5); + LIBCPP_NON_FROZEN_ASSERT(copy.bucket_count() == 5); assert(copy.size() == 4); assert(copy.count(1) == 1); assert(copy.count(2) == 1); diff --git a/libcxx/test/std/localization/locale.categories/category.numeric/locale.nm.put/facet.num.put.members/put_pointer.pass.cpp b/libcxx/test/std/localization/locale.categories/category.numeric/locale.nm.put/facet.num.put.members/put_pointer.pass.cpp index 572a14e..fed5b4a 100644 --- a/libcxx/test/std/localization/locale.categories/category.numeric/locale.nm.put/facet.num.put.members/put_pointer.pass.cpp +++ b/libcxx/test/std/localization/locale.categories/category.numeric/locale.nm.put/facet.num.put.members/put_pointer.pass.cpp @@ -12,8 +12,6 @@ // iter_type put(iter_type s, ios_base& iob, char_type fill, void* v) const; -// XFAIL: FROZEN-CXX03-HEADERS-FIXME - #include <cassert> #include <ios> #include <locale> @@ -36,7 +34,7 @@ int main(int, char**) { cpp17_output_iterator<char*> iter = f.put(cpp17_output_iterator<char*>(str), ios, '*', v); std::string ex(str, base(iter)); assert(!ex.empty()); - LIBCPP_ASSERT(ex == "0"); + LIBCPP_NON_FROZEN_ASSERT(ex == "0"); } return 0; diff --git a/libcxx/test/support/test_macros.h b/libcxx/test/support/test_macros.h index 2fc25fc..c4e1600 100644 --- a/libcxx/test/support/test_macros.h +++ b/libcxx/test/support/test_macros.h @@ -264,6 +264,12 @@ #define LIBCPP_ONLY(...) static_assert(true, "") #endif +#ifdef _LIBCPP_USE_FROZEN_CXX03_HEADERS +# define LIBCPP_NON_FROZEN_ASSERT(...) static_assert(true, "") +#else +# define LIBCPP_NON_FROZEN_ASSERT(...) LIBCPP_ASSERT(__VA_ARGS__) +#endif + #if __has_cpp_attribute(nodiscard) # define TEST_NODISCARD [[nodiscard]] #else diff --git a/libcxx/utils/visualize-historical b/libcxx/utils/visualize-historical index 114c7e8..0a94b15 100755 --- a/libcxx/utils/visualize-historical +++ b/libcxx/utils/visualize-historical @@ -112,7 +112,7 @@ def truncate_lines(string, n, marker=None): assert len(truncated) <= n, "broken post-condition" return '\n'.join(truncated) -def create_plot(data, metric, subtitle=None): +def create_plot(data, metric, trendline=None, subtitle=None): """ Create a plot object showing the evolution of each benchmark throughout the given commits for the given metric. @@ -126,7 +126,7 @@ def create_plot(data, metric, subtitle=None): symbol='benchmark', color='benchmark', hover_name=[hover_info[c] for c in data['commit']], - trendline="lowess") + trendline=trendline) return figure def directory_path(string): @@ -221,6 +221,10 @@ def main(argv): parser.add_argument('--open', action='store_true', help='Whether to automatically open the generated HTML file when finished. If no output file is provided, ' 'the resulting benchmark is opened automatically by default.') + parser.add_argument('--trendline', type=str, required=False, default=None, choices=('ols', 'lowess', 'expanding'), + help='Optional trendline to add on each series in the chart. See the documentation in ' + 'https://plotly.com/python-api-reference/generated/plotly.express.trendline_functions.html ' + 'details on each option.') args = parser.parse_args(argv) # Extract benchmark data from the directory. @@ -250,9 +254,11 @@ def main(argv): if args.filter is not None: keeplist = [b for b in data['benchmark'] if re.search(args.filter, b) is not None] data = data[data['benchmark'].isin(keeplist)] + if len(data) == 0: + raise RuntimeError(f'Filter "{args.filter}" resulted in empty data set -- nothing to plot') # Plot the data for all the required benchmarks. - figure = create_plot(data, args.metric, subtitle=args.subtitle) + figure = create_plot(data, args.metric, trendline=args.trendline, subtitle=args.subtitle) do_open = args.output is None or args.open output = args.output if args.output is not None else tempfile.NamedTemporaryFile(suffix='.html').name plotly.io.write_html(figure, file=output, auto_open=do_open) |