diff --git a/libcxx/include/__algorithm/copy_backward.h b/libcxx/include/__algorithm/copy_backward.h --- a/libcxx/include/__algorithm/copy_backward.h +++ b/libcxx/include/__algorithm/copy_backward.h @@ -10,7 +10,6 @@ #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H #include <__algorithm/copy.h> -#include <__algorithm/iterator_operations.h> #include <__algorithm/unwrap_iter.h> #include <__config> #include <__iterator/iterator_traits.h> @@ -24,22 +23,21 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter2> __copy_backward_impl(_Iter1 __first, _Sent1 __last, _Iter2 __result) { - auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last); - auto __ret = std::__copy(reverse_iterator<_Iter1>(__last_iter), - reverse_iterator<_Iter1>(__first), + auto __ret = std::__copy(reverse_iterator<_Iter1>(__last), + reverse_iterator<_Sent1>(__first), reverse_iterator<_Iter2>(__result)); return pair<_Iter1, _Iter2>(__ret.first.base(), __ret.second.base()); } -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) { - auto __ret = std::__copy_backward_impl<_AlgPolicy>(std::__unwrap_iter(__first), - std::__unwrap_iter(__last), - std::__unwrap_iter(__result)); + auto __ret = std::__copy_backward_impl(std::__unwrap_iter(__first), + std::__unwrap_iter(__last), + std::__unwrap_iter(__result)); return pair<_Iter1, _Iter2>(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); } @@ -47,7 +45,7 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator2 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result).second; + return std::__copy_backward(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -59,24 +59,23 @@ _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { - using _Ops = _IterOps<_AlgPolicy>; - for (; __first1 != __last1; ++__result) { if (__first2 == __last2) { + // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `move`. _VSTD::move(__first1, __last1, __result); return; } if (__comp(*__first2, *__first1)) { - *__result = _Ops::__iter_move(__first2); + *__result = _IterOps<_AlgPolicy>::__iter_move(__first2); ++__first2; } else { - *__result = _Ops::__iter_move(__first1); + *__result = _IterOps<_AlgPolicy>::__iter_move(__first1); ++__first1; } } @@ -90,8 +89,6 @@ typename iterator_traits<_BidirectionalIterator>::difference_type __len2, typename iterator_traits<_BidirectionalIterator>::value_type* __buff) { - using _Ops = _IterOps<_AlgPolicy>; - typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; __destruct_n __d(0); unique_ptr __h2(__buff, __d); @@ -99,14 +96,14 @@ { value_type* __p = __buff; for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr(), (void) ++__i, (void) ++__p) - ::new ((void*)__p) value_type(_Ops::__iter_move(__i)); + ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i)); std::__half_inplace_merge<_AlgPolicy, _Compare>(__buff, __p, __middle, __last, __first, __comp); } else { value_type* __p = __buff; for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr(), (void) ++__i, (void) ++__p) - ::new ((void*)__p) value_type(_Ops::__iter_move(__i)); + ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator _Rv; typedef __invert<_Compare> _Inverted; @@ -182,6 +179,7 @@ difference_type __len22 = __len2 - __len21; // distance(__m2, __last) // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) // swap middle two partitions + // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`. __middle = _VSTD::rotate(__m1, __middle, __m2); // __len12 and __len21 now have swapped meanings // merge smaller range with recursive call and larger with tail recursion elimination diff --git a/libcxx/include/__algorithm/ranges_copy_backward.h b/libcxx/include/__algorithm/ranges_copy_backward.h --- a/libcxx/include/__algorithm/ranges_copy_backward.h +++ b/libcxx/include/__algorithm/ranges_copy_backward.h @@ -11,7 +11,6 @@ #include <__algorithm/copy_backward.h> #include <__algorithm/in_out_result.h> -#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/concepts.h> #include <__iterator/reverse_iterator.h> @@ -40,7 +39,7 @@ requires indirectly_copyable<_InIter1, _InIter2> _LIBCPP_HIDE_FROM_ABI constexpr copy_backward_result<_InIter1, _InIter2> operator()(_InIter1 __first, _Sent1 __last, _InIter2 __result) const { - auto __ret = std::__copy_backward<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); + auto __ret = std::__copy_backward(std::move(__first), std::move(__last), std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } @@ -48,9 +47,9 @@ requires indirectly_copyable, _Iter> _LIBCPP_HIDE_FROM_ABI constexpr copy_backward_result, _Iter> operator()(_Range&& __r, _Iter __result) const { - auto __ret = std::__copy_backward<_RangeAlgPolicy>(ranges::begin(__r), - ranges::end(__r), - std::move(__result)); + auto __ret = std::__copy_backward(ranges::begin(__r), + ranges::end(__r), + std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } }; diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -31,6 +31,53 @@ _LIBCPP_BEGIN_NAMESPACE_STD +// Wraps an algorithm policy tag and a comparator in a single struct, used to pass the policy tag around without +// changing the number of template arguments. This is only used for the "range" policy tag. +// +// To create an object of this type, use `_WrapAlgPolicy::type` -- see the specialization below for the rationale. +template +struct _WrapAlgPolicy { + using type = _WrapAlgPolicy; + + using _AlgPolicy = _PolicyT; + using _Comp = _CompT; + _Comp& __comp; + + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + _WrapAlgPolicy(_Comp& __c) : __comp(__c) {} +}; + +// Specialization for the "classic" policy tag that avoids creating a struct and simply defines an alias for the +// comparator. When unwrapping, a pristine comparator is always considered to have the "classic" tag attached. Passing +// the pristine comparator where possible allows using template instantiations from the dylib. +template +struct _WrapAlgPolicy<_PolicyT, _CompT, + typename std::enable_if::value>::type> { + using type = _CompT; +}; + +// Unwraps a pristine functor (e.g. `std::less`) as if it were wrapped using `_WrapAlgPolicy`. The policy tag is always +// set to "classic". +template +struct _UnwrapAlgPolicy { + using _AlgPolicy = _ClassicAlgPolicy; + using _Comp = _CompT; + + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 static + _Comp __get_comp(_Comp __comp) { return __comp; } +}; + +// Unwraps a `_WrapAlgPolicy` struct. +template +struct _UnwrapAlgPolicy<_Wrapped, + typename std::enable_if::value>::type> { + using _AlgPolicy = typename _Wrapped::_AlgPolicy; + using _Comp = typename _Wrapped::_Comp; + + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 static + _Comp __get_comp(_Wrapped& __w) { return __w.__comp; } +}; + // stable, 2-3 compares, 0-2 swaps template @@ -94,11 +141,16 @@ // stable, 4-10 compares, 0-9 swaps -template +template _LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, - _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { + _ForwardIterator __x4, _ForwardIterator __x5, _WrappedComp __wrapped_comp) { + using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; + using _AlgPolicy = typename _Unwrap::_AlgPolicy; using _Ops = _IterOps<_AlgPolicy>; + using _Compare = typename _Unwrap::_Comp; + _Compare __c = _Unwrap::__get_comp(__wrapped_comp); + unsigned __r = std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c); if (__c(*__x5, *__x4)) { _Ops::iter_swap(__x4, __x5); @@ -119,6 +171,16 @@ return __r; } +template +_LIBCPP_HIDDEN unsigned __sort5_wrap_policy( + _ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, + _Compare __c) { + using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type; + _WrappedComp __wrapped_comp(__c); + return std::__sort5<_WrappedComp>( + std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __wrapped_comp); +} + // The comparator being simple is a prerequisite for using the branchless optimization. template struct __is_simple_comparator : false_type {}; @@ -138,12 +200,12 @@ template ::value_type> using __use_branchless_sort = integral_constant::value && sizeof(_Tp) <= sizeof(void*) && - is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value && - is_same()), _Tp>::value>; + is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>; // Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary. template inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) { + // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`). using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; bool __r = __c(*__x, *__y); value_type __tmp = __r ? *__x : *__y; @@ -156,6 +218,7 @@ template inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _RandomAccessIterator __z, _Compare __c) { + // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`). using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; bool __r = __c(*__z, *__x); value_type __tmp = __r ? *__z : *__x; @@ -214,7 +277,7 @@ inline _LIBCPP_HIDE_FROM_ABI __enable_if_t::value, void> __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { - std::__sort5<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c); + std::__sort5_wrap_policy<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c); } // Assumes size > 0 @@ -269,10 +332,16 @@ } } -template -bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { +template +bool __insertion_sort_incomplete( + _RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) { + using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; + using _AlgPolicy = typename _Unwrap::_AlgPolicy; using _Ops = _IterOps<_AlgPolicy>; + using _Compare = typename _Unwrap::_Comp; + _Compare __comp = _Unwrap::__get_comp(__wrapped_comp); + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; switch (__last - __first) { case 0: @@ -334,10 +403,10 @@ value_type* __j2 = __last2; value_type* __i2 = __j2; if (__comp(*__first1, *--__i2)) { - ::new ((void*)__j2) value_type(_Ops::__iter_move(__i2)); + ::new ((void*)__j2) value_type(std::move(*__i2)); __d.template __incr(); for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) - *__j2 = _Ops::__iter_move(__i2); + *__j2 = std::move(*__i2); *__j2 = _Ops::__iter_move(__first1); } else { ::new ((void*)__j2) value_type(_Ops::__iter_move(__first1)); @@ -402,7 +471,8 @@ __delta = __len / 2; __m += __delta; __delta /= 2; - __n_swaps = std::__sort5<_AlgPolicy, _Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp); + __n_swaps = std::__sort5_wrap_policy<_AlgPolicy, _Compare>( + __first, __first + __delta, __m, __m + __delta, __lm1, __comp); } else { __delta = __len / 2; __m += __delta; @@ -501,8 +571,10 @@ // [__first, __i) < *__i and *__i <= [__i+1, __last) // If we were given a perfect partition, see if insertion sort is quick... if (__n_swaps == 0) { - bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp); - if (std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp)) { + using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type; + _WrappedComp __wrapped_comp(__comp); + bool __fs = std::__insertion_sort_incomplete<_WrappedComp>(__first, __i, __wrapped_comp); + if (std::__insertion_sort_incomplete<_WrappedComp>(__i + difference_type(1), __last, __wrapped_comp)) { if (__fs) return; __last = __i; @@ -544,66 +616,75 @@ return __log2; } -template -void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { +template +void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __depth_limit = 2 * __log2i(__last - __first); + + using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; + using _AlgPolicy = typename _Unwrap::_AlgPolicy; + using _Compare = typename _Unwrap::_Comp; + _Compare __comp = _Unwrap::__get_comp(__wrapped_comp); std::__introsort<_AlgPolicy, _Compare>(__first, __last, __comp, __depth_limit); } -template +template inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) { __less __comp; - std::__sort<_AlgPolicy, __less&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); + std::__sort<__less&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); } -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, char*>(char*, char*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, wchar_t*>(wchar_t*, wchar_t*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); #endif -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, signed char*>(signed char*, signed char*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned char*>(unsigned char*, unsigned char*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, short*>(short*, short*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned short*>(unsigned short*, unsigned short*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, int*>(int*, int*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned*>(unsigned*, unsigned*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, long*>(long*, long*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned long*>(unsigned long*, unsigned long*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, long long*>(long long*, long long*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, float*>(float*, float*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, double*>(double*, double*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, __less&); - -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, char*>(char*, char*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, signed char*>(signed char*, signed char*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned char*>(unsigned char*, unsigned char*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, short*>(short*, short*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned short*>(unsigned short*, unsigned short*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, int*>(int*, int*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned*>(unsigned*, unsigned*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, long*>(long*, long*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned long*>(unsigned long*, unsigned long*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, long long*>(long long*, long long*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, float*>(float*, float*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, double*>(double*, double*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<__less&, long double*>(long double*, long double*, __less&); + +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, wchar_t*>(wchar_t*, wchar_t*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); #endif -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, signed char*>(signed char*, signed char*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned char*>(unsigned char*, unsigned char*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, short*>(short*, short*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned short*>(unsigned short*, unsigned short*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, int*>(int*, int*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned*>(unsigned*, unsigned*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long*>(long*, long*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned long*>(unsigned long*, unsigned long*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long long*>(long long*, long long*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, float*>(float*, float*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, double*>(double*, double*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, __less&); - -extern template _LIBCPP_FUNC_VIS unsigned __sort5<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, signed char*>(signed char*, signed char*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned char*>(unsigned char*, unsigned char*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, short*>(short*, short*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned short*>(unsigned short*, unsigned short*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, int*>(int*, int*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned*>(unsigned*, unsigned*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, long*>(long*, long*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned long*>(unsigned long*, unsigned long*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, long long*>(long long*, long long*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, float*>(float*, float*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, double*>(double*, double*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, long double*>(long double*, long double*, __less&); + +extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { std::__debug_randomize_range(__first, __last); + using _Comp_ref = typename __comp_ref_type<_Comp>::type; if (__libcpp_is_constant_evaluated()) { std::__partial_sort<_AlgPolicy, _Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); + } else { - std::__sort<_AlgPolicy, _Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp)); + using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Comp_ref>::type; + _WrappedComp __wrapped_comp((_Comp_ref(__comp))); + std::__sort<_WrappedComp>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __wrapped_comp); } } diff --git a/libcxx/src/algorithm.cpp b/libcxx/src/algorithm.cpp --- a/libcxx/src/algorithm.cpp +++ b/libcxx/src/algorithm.cpp @@ -6,49 +6,48 @@ // //===----------------------------------------------------------------------===// -#include <__algorithm/iterator_operations.h> #include _LIBCPP_BEGIN_NAMESPACE_STD // TODO(varconst): this currently doesn't benefit `ranges::sort` because it uses `ranges::less` instead of `__less`. -template void __sort<_ClassicAlgPolicy, __less&, char*>(char*, char*, __less&); +template void __sort<__less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -template void __sort<_ClassicAlgPolicy, __less&, wchar_t*>(wchar_t*, wchar_t*, __less&); +template void __sort<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); #endif -template void __sort<_ClassicAlgPolicy, __less&, signed char*>(signed char*, signed char*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, unsigned char*>(unsigned char*, unsigned char*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, short*>(short*, short*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, unsigned short*>(unsigned short*, unsigned short*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, int*>(int*, int*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, unsigned*>(unsigned*, unsigned*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, long*>(long*, long*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, unsigned long*>(unsigned long*, unsigned long*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, long long*>(long long*, long long*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, float*>(float*, float*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, double*>(double*, double*, __less&); -template void __sort<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, __less&); +template void __sort<__less&, signed char*>(signed char*, signed char*, __less&); +template void __sort<__less&, unsigned char*>(unsigned char*, unsigned char*, __less&); +template void __sort<__less&, short*>(short*, short*, __less&); +template void __sort<__less&, unsigned short*>(unsigned short*, unsigned short*, __less&); +template void __sort<__less&, int*>(int*, int*, __less&); +template void __sort<__less&, unsigned*>(unsigned*, unsigned*, __less&); +template void __sort<__less&, long*>(long*, long*, __less&); +template void __sort<__less&, unsigned long*>(unsigned long*, unsigned long*, __less&); +template void __sort<__less&, long long*>(long long*, long long*, __less&); +template void __sort<__less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); +template void __sort<__less&, float*>(float*, float*, __less&); +template void __sort<__less&, double*>(double*, double*, __less&); +template void __sort<__less&, long double*>(long double*, long double*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, char*>(char*, char*, __less&); +template bool __insertion_sort_incomplete<__less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, wchar_t*>(wchar_t*, wchar_t*, __less&); +template bool __insertion_sort_incomplete<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); #endif -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, signed char*>(signed char*, signed char*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned char*>(unsigned char*, unsigned char*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, short*>(short*, short*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned short*>(unsigned short*, unsigned short*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, int*>(int*, int*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned*>(unsigned*, unsigned*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long*>(long*, long*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned long*>(unsigned long*, unsigned long*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long long*>(long long*, long long*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, float*>(float*, float*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, double*>(double*, double*, __less&); -template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, __less&); +template bool __insertion_sort_incomplete<__less&, signed char*>(signed char*, signed char*, __less&); +template bool __insertion_sort_incomplete<__less&, unsigned char*>(unsigned char*, unsigned char*, __less&); +template bool __insertion_sort_incomplete<__less&, short*>(short*, short*, __less&); +template bool __insertion_sort_incomplete<__less&, unsigned short*>(unsigned short*, unsigned short*, __less&); +template bool __insertion_sort_incomplete<__less&, int*>(int*, int*, __less&); +template bool __insertion_sort_incomplete<__less&, unsigned*>(unsigned*, unsigned*, __less&); +template bool __insertion_sort_incomplete<__less&, long*>(long*, long*, __less&); +template bool __insertion_sort_incomplete<__less&, unsigned long*>(unsigned long*, unsigned long*, __less&); +template bool __insertion_sort_incomplete<__less&, long long*>(long long*, long long*, __less&); +template bool __insertion_sort_incomplete<__less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); +template bool __insertion_sort_incomplete<__less&, float*>(float*, float*, __less&); +template bool __insertion_sort_incomplete<__less&, double*>(double*, double*, __less&); +template bool __insertion_sort_incomplete<__less&, long double*>(long double*, long double*, __less&); -template unsigned __sort5<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); +template unsigned __sort5<__less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp b/libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp --- a/libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp +++ b/libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp @@ -13,6 +13,7 @@ // UNSUPPORTED: c++03 // ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY +#include <__algorithm/iterator_operations.h> #include #include #include @@ -34,7 +35,7 @@ for (int i = 0; i < kSize; ++i) { v[i].value = (i % 2 ? i : kSize / 2 + i); } - std::__nth_element(v.begin(), v.begin() + kSize / 2, v.end(), std::less()); + std::__nth_element(v.begin(), v.begin() + kSize / 2, v.end(), std::less()); return v; } diff --git a/libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp b/libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp --- a/libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp +++ b/libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp @@ -13,6 +13,7 @@ // UNSUPPORTED: c++03 // ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY +#include <__algorithm/iterator_operations.h> #include #include #include @@ -34,7 +35,7 @@ for (int i = 0; i < kSize; ++i) { v[i].value = (i % 2 ? 1 : kSize / 2 + i); } - std::__partial_sort(v.begin(), v.begin() + kSize / 2, v.end(), std::less()); + std::__partial_sort(v.begin(), v.begin() + kSize / 2, v.end(), std::less()); return v; } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp rename from libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp rename to libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -27,24 +27,24 @@ #include "test_iterators.h" template -void test(Func&& func, Input& in, Args&& ...args) { +constexpr void test(Func&& func, Input& in, Args&& ...args) { func(in.begin(), in.end(), std::forward(args)...); func(in, std::forward(args)...); } -template -void test(Func&& func, Input& in1, Input& in2, Args&& ...args) { - func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward(args)...); - func(in1, in2, std::forward(args)...); +template +constexpr void test(Func&& func, Range1& r1, Range2& r2, Args&& ...args) { + func(r1.begin(), r1.end(), r2.begin(), r2.end(), std::forward(args)...); + func(r1, r2, std::forward(args)...); } template -void test_mid(Func&& func, Input& in, std::ranges::iterator_t mid, Args&& ...args) { +constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t mid, Args&& ...args) { func(in.begin(), mid, in.end(), std::forward(args)...); func(in, mid, std::forward(args)...); } -void test_all() { +constexpr bool test_all() { std::array input = {1, 2, 3}; ProxyRange in{input}; std::array input2 = {4, 5, 6}; @@ -52,7 +52,7 @@ auto mid = in.begin() + 1; - std::array output = {4, 5, 6}; + std::array output = {4, 5, 6, 7, 8, 9}; ProxyIterator out{output.begin()}; //auto out2 = output.begin() + 1; @@ -61,7 +61,7 @@ int count = 1; auto unary_pred = [](const Proxy& x) { return x.getData() > 0; }; - auto binary_pred = [](const Proxy& lhs, const Proxy& rhs) { return lhs.getData() == rhs.getData(); }; + //auto binary_pred = [](const Proxy& lhs, const Proxy& rhs) { return lhs.getData() == rhs.getData(); }; auto binary_func = [](const Proxy& lhs, const Proxy&) -> Proxy { return lhs.getData(); }; //auto gen = [] { return Proxy(42); }; //std::mt19937 rand_gen; @@ -103,9 +103,11 @@ test(std::ranges::copy, in, out); std::ranges::copy_n(in.begin(), count, out); test(std::ranges::copy_if, in, out, unary_pred); - test(std::ranges::copy_backward, in, out); + // TODO: uncomment `copy_backward` once https://reviews.llvm.org/D128864 lands. + //test(std::ranges::copy_backward, in, out); test(std::ranges::move, in, out); - test(std::ranges::move_backward, in, out); + // TODO: uncomment `move_backward` once https://reviews.llvm.org/D128864 lands. + // test(std::ranges::move_backward, in, out); test(std::ranges::fill, in, x); std::ranges::fill_n(in.begin(), count, x); test(std::ranges::transform, in, out, std::identity{}); @@ -122,9 +124,9 @@ test(std::ranges::reverse_copy, in, out); test_mid(std::ranges::rotate_copy, in, mid, out); //test(std::ranges::sample, in, out, count, rand_gen); - //test(std::ranges::unique_copy, in, out, binary_pred); + //test(std::ranges::unique_copy, in, out); //test(std::ranges::partition_copy, in, out, out2, unary_pred); - //test_mid(std::ranges::partial_sort_copy, in, in2, binary_pred); + //test_mid(std::ranges::partial_sort_copy, in, in2); test(std::ranges::merge, in, in2, out); test(std::ranges::set_difference, in, in2, out); test(std::ranges::set_intersection, in, in2, out); @@ -137,17 +139,32 @@ //test(std::ranges::shuffle, in, rand_gen); //test(std::ranges::unique, in); //test(std::ranges::partition, in, binary_pred); - //test(std::ranges::stable_partition, in, binary_pred); + //if (!std::is_constant_evaluated()) + // test(std::ranges::stable_partition, in, binary_pred); test(std::ranges::sort, in); // TODO: `stable_sort` requires `ranges::rotate` to be implemented. - //test(std::ranges::stable_sort, in); + //if (!std::is_constant_evaluated()) + // test(std::ranges::stable_sort, in); //test_mid(std::ranges::partial_sort, in, mid); test_mid(std::ranges::nth_element, in, mid); - //test_mid(std::ranges::inplace_merge, in, mid); + //if (!std::is_constant_evaluated()) + // test_mid(std::ranges::inplace_merge, in, mid); test(std::ranges::make_heap, in); - test(std::ranges::push_heap, in, binary_pred); - test(std::ranges::pop_heap, in, binary_pred); - test(std::ranges::sort_heap, in, binary_pred); - //test(std::ranges::prev_permutation, in, binary_pred); - //test(std::ranges::next_permutation, in, binary_pred); + test(std::ranges::push_heap, in); + test(std::ranges::pop_heap, in); + test(std::ranges::sort_heap, in); + //test(std::ranges::prev_permutation, in); + //test(std::ranges::next_permutation, in); + + // The algorithms that work on uninitialized memory have constraints that prevent proxy iterators from being used with + // them. + + return true; +} + +int main(int, char**) { + test_all(); + static_assert(test_all()); + + return 0; } diff --git a/libcxx/test/support/test.support/test_proxy.pass.cpp b/libcxx/test/support/test.support/test_proxy.pass.cpp --- a/libcxx/test/support/test.support/test_proxy.pass.cpp +++ b/libcxx/test/support/test.support/test_proxy.pass.cpp @@ -58,10 +58,20 @@ p4 = std::move(p3); assert(p4.data.get() == 8); - int i = 5, j = 6; + // `T` is a reference type. + int i = 5, j = 6, k = 7, x = 8; Proxy p5{i}; + // `Other` is a prvalue. p5 = Proxy{j}; assert(p5.data == 6); + // `Other` is a const lvalue. + const Proxy p_ref{k}; + p5 = p_ref; + assert(p5.data == 7); + // `Other` is an xvalue. + Proxy px{x}; + p5 = std::move(px); + assert(p5.data == 8); } // const assignment @@ -87,6 +97,18 @@ Proxy p2{6}; assert(p1 != p2); assert(p1 < p2); + + // Comparing `T` and `T&`. + int i = 5, j = 6; + Proxy p_ref{i}; + Proxy p_cref{j}; + assert(p1 == p_ref); + assert(p2 == p_cref); + assert(p_ref == p1); + assert(p_cref == p2); + assert(p_ref == p_ref); + assert(p_cref == p_cref); + assert(p_ref != p_cref); } } diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -827,12 +827,12 @@ // ====================================================================== // Proxy that can wrap a value or a reference. It simulates C++23's tuple // but simplified to just hold one argument. -// Note that unlike tuple, this class deliberately doesn't have special handling -// of swap to cause a compilation error if it's used in an algorithm that relies +// Note that unlike tuple, this class deliberately doesn't have special handling +// of swap to cause a compilation error if it's used in an algorithm that relies // on plain swap instead of ranges::iter_swap. // This class is useful for testing that if algorithms support proxy iterator // properly, i.e. calling ranges::iter_swap and ranges::iter_move instead of -// plain swap and std::move +// plain swap and std::move template struct Proxy; @@ -878,7 +878,8 @@ return *this; } - // If `T` is a reference type, the default assignment operator will be deleted. + // If `T` is a reference type, the implicitly-generated assignment operator will be deleted (and would take precedence + // over the templated `operator=` above because it's a better match). constexpr Proxy& operator=(const Proxy& rhs) { data = rhs.data; return *this;