diff options
Diffstat (limited to 'libcxx/include/__algorithm/sort.h')
| -rw-r--r-- | libcxx/include/__algorithm/sort.h | 428 |
1 files changed, 196 insertions, 232 deletions
diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h index a7d2d55a06f8..3b594fa4d2a8 100644 --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -21,15 +21,15 @@ #include <__bit/countl.h> #include <__bit/countr.h> #include <__config> -#include <__debug> #include <__debug_utils/randomize_range.h> +#include <__debug_utils/strict_weak_ordering_check.h> #include <__functional/operations.h> #include <__functional/ranges_operations.h> #include <__iterator/iterator_traits.h> -#include <__memory/destruct_n.h> -#include <__memory/unique_ptr.h> #include <__type_traits/conditional.h> +#include <__type_traits/disjunction.h> #include <__type_traits/is_arithmetic.h> +#include <__type_traits/is_constant_evaluated.h> #include <__utility/move.h> #include <__utility/pair.h> #include <climits> @@ -41,52 +41,6 @@ _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 (to keep the ABI stable). This is only used for the "range" policy tag. -// -// To create an object of this type, use `_WrapAlgPolicy<T, C>::type` -- see the specialization below for the rationale. -template <class _PolicyT, class _CompT, class = void> -struct _WrapAlgPolicy { - using type = _WrapAlgPolicy; - - using _AlgPolicy = _PolicyT; - using _Comp = _CompT; - _Comp& __comp; - - _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 - _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 <class _PolicyT, class _CompT> -struct _WrapAlgPolicy<_PolicyT, _CompT, __enable_if_t<std::is_same<_PolicyT, _ClassicAlgPolicy>::value> > { - 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 <class _CompT> -struct _UnwrapAlgPolicy { - using _AlgPolicy = _ClassicAlgPolicy; - using _Comp = _CompT; - - _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static - _Comp __get_comp(_Comp __comp) { return __comp; } -}; - -// Unwraps a `_WrapAlgPolicy` struct. -template <class... _Ts> -struct _UnwrapAlgPolicy<_WrapAlgPolicy<_Ts...> > { - using _Wrapped = _WrapAlgPolicy<_Ts...>; - using _AlgPolicy = typename _Wrapped::_AlgPolicy; - using _Comp = typename _Wrapped::_Comp; - - _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static - _Comp __get_comp(_Wrapped& __w) { return __w.__comp; } -}; - // stable, 2-3 compares, 0-2 swaps template <class _AlgPolicy, class _Compare, class _ForwardIterator> @@ -130,77 +84,53 @@ _LIBCPP_CONSTEXPR_SINCE_CXX14 unsigned __sort3(_ForwardIterator __x, _ForwardIte template <class _AlgPolicy, class _Compare, class _ForwardIterator> _LIBCPP_HIDE_FROM_ABI -unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, +void __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) { using _Ops = _IterOps<_AlgPolicy>; - unsigned __r = std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c); + std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c); if (__c(*__x4, *__x3)) { _Ops::iter_swap(__x3, __x4); - ++__r; if (__c(*__x3, *__x2)) { _Ops::iter_swap(__x2, __x3); - ++__r; if (__c(*__x2, *__x1)) { _Ops::iter_swap(__x1, __x2); - ++__r; } } } - return __r; } // stable, 4-10 compares, 0-9 swaps -template <class _WrappedComp, class _ForwardIterator> -_LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, - _ForwardIterator __x4, _ForwardIterator __x5, _WrappedComp __wrapped_comp) { - using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; - using _AlgPolicy = typename _Unwrap::_AlgPolicy; +template <class _AlgPolicy, class _Comp, class _ForwardIterator> +_LIBCPP_HIDE_FROM_ABI void __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, + _ForwardIterator __x4, _ForwardIterator __x5, _Comp __comp) { 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)) { + std::__sort4<_AlgPolicy, _Comp>(__x1, __x2, __x3, __x4, __comp); + if (__comp(*__x5, *__x4)) { _Ops::iter_swap(__x4, __x5); - ++__r; - if (__c(*__x4, *__x3)) { + if (__comp(*__x4, *__x3)) { _Ops::iter_swap(__x3, __x4); - ++__r; - if (__c(*__x3, *__x2)) { + if (__comp(*__x3, *__x2)) { _Ops::iter_swap(__x2, __x3); - ++__r; - if (__c(*__x2, *__x1)) { + if (__comp(*__x2, *__x1)) { _Ops::iter_swap(__x1, __x2); - ++__r; } } } } - return __r; -} - -template <class _AlgPolicy, class _Compare, class _ForwardIterator> -_LIBCPP_HIDE_FROM_ABI 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, _ForwardIterator>( - 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 <class _Tp> struct __is_simple_comparator : false_type {}; -template <class _Tp> -struct __is_simple_comparator<__less<_Tp>&> : true_type {}; +template <> +struct __is_simple_comparator<__less<>&> : true_type {}; template <class _Tp> struct __is_simple_comparator<less<_Tp>&> : true_type {}; template <class _Tp> struct __is_simple_comparator<greater<_Tp>&> : true_type {}; -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <> struct __is_simple_comparator<ranges::less&> : true_type {}; template <> @@ -209,7 +139,7 @@ struct __is_simple_comparator<ranges::greater&> : true_type {}; template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type> using __use_branchless_sort = - integral_constant<bool, __is_cpp17_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) && + integral_constant<bool, __libcpp_is_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) && is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>; namespace __detail { @@ -299,7 +229,8 @@ template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { - std::__sort5_wrap_policy<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c); + std::__sort5<_AlgPolicy, _Compare, _RandomAccessIterator>( + std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __c); } // Assumes size > 0 @@ -344,17 +275,18 @@ void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __l // Sort the iterator range [__first, __last) using the comparator __comp using // the insertion sort algorithm. Insertion sort has two loops, outer and inner. -// The implementation below has not bounds check (unguarded) for the inner loop. +// The implementation below has no bounds check (unguarded) for the inner loop. // Assumes that there is an element in the position (__first - 1) and that each // element in the input range is greater or equal to the element at __first - 1. template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> _LIBCPP_HIDE_FROM_ABI void -__insertion_sort_unguarded(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { +__insertion_sort_unguarded(_RandomAccessIterator const __first, _RandomAccessIterator __last, _Compare __comp) { using _Ops = _IterOps<_AlgPolicy>; typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; if (__first == __last) return; + const _RandomAccessIterator __leftmost = __first - difference_type(1); (void)__leftmost; // can be unused when assertions are disabled for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) { _RandomAccessIterator __j = __i - difference_type(1); if (__comp(*__i, *__j)) { @@ -364,22 +296,20 @@ __insertion_sort_unguarded(_RandomAccessIterator __first, _RandomAccessIterator do { *__j = _Ops::__iter_move(__k); __j = __k; + _LIBCPP_ASSERT_UNCATEGORIZED( + __k != __leftmost, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above. *__j = std::move(__t); } } } -template <class _WrappedComp, class _RandomAccessIterator> -_LIBCPP_HIDDEN bool __insertion_sort_incomplete( - _RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) { - using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; - using _AlgPolicy = typename _Unwrap::_AlgPolicy; +template <class _AlgPolicy, class _Comp, class _RandomAccessIterator> +_LIBCPP_HIDE_FROM_ABI bool __insertion_sort_incomplete( + _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { 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: @@ -390,21 +320,21 @@ _LIBCPP_HIDDEN bool __insertion_sort_incomplete( _Ops::iter_swap(__first, __last); return true; case 3: - std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp); + std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), --__last, __comp); return true; case 4: - std::__sort4_maybe_branchless<_AlgPolicy, _Compare>( + std::__sort4_maybe_branchless<_AlgPolicy, _Comp>( __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp); return true; case 5: - std::__sort5_maybe_branchless<_AlgPolicy, _Compare>( + std::__sort5_maybe_branchless<_AlgPolicy, _Comp>( __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3), --__last, __comp); return true; } typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first + difference_type(2); - std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp); + std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), __j, __comp); const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { @@ -425,37 +355,6 @@ _LIBCPP_HIDDEN bool __insertion_sort_incomplete( return true; } -template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> -_LIBCPP_HIDE_FROM_ABI -void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, - typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) { - using _Ops = _IterOps<_AlgPolicy>; - - typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; - if (__first1 != __last1) { - __destruct_n __d(0); - unique_ptr<value_type, __destruct_n&> __h(__first2, __d); - value_type* __last2 = __first2; - ::new ((void*)__last2) value_type(_Ops::__iter_move(__first1)); - __d.template __incr<value_type>(); - for (++__last2; ++__first1 != __last1; ++__last2) { - value_type* __j2 = __last2; - value_type* __i2 = __j2; - if (__comp(*__first1, *--__i2)) { - ::new ((void*)__j2) value_type(std::move(*__i2)); - __d.template __incr<value_type>(); - for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) - *__j2 = std::move(*__i2); - *__j2 = _Ops::__iter_move(__first1); - } else { - ::new ((void*)__j2) value_type(_Ops::__iter_move(__first1)); - __d.template __incr<value_type>(); - } - } - __h.release(); - } -} - template <class _AlgPolicy, class _RandomAccessIterator> inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos( _RandomAccessIterator __first, _RandomAccessIterator __last, uint64_t& __left_bitset, uint64_t& __right_bitset) { @@ -464,11 +363,11 @@ inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos( // Swap one pair on each iteration as long as both bitsets have at least one // element for swapping. while (__left_bitset != 0 && __right_bitset != 0) { - difference_type tz_left = __libcpp_ctz(__left_bitset); - __left_bitset = __libcpp_blsr(__left_bitset); - difference_type tz_right = __libcpp_ctz(__right_bitset); - __right_bitset = __libcpp_blsr(__right_bitset); - _Ops::iter_swap(__first + tz_left, __last - tz_right); + difference_type __tz_left = __libcpp_ctz(__left_bitset); + __left_bitset = __libcpp_blsr(__left_bitset); + difference_type __tz_right = __libcpp_ctz(__right_bitset); + __right_bitset = __libcpp_blsr(__right_bitset); + _Ops::iter_swap(__first + __tz_left, __last - __tz_right); } } @@ -533,9 +432,9 @@ inline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks( // Record the comparison outcomes for the elements currently on the left side. if (__left_bitset == 0) { _RandomAccessIterator __iter = __first; - for (int j = 0; j < __l_size; j++) { + for (int __j = 0; __j < __l_size; __j++) { bool __comp_result = !__comp(*__iter, __pivot); - __left_bitset |= (static_cast<uint64_t>(__comp_result) << j); + __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j); ++__iter; } } @@ -543,9 +442,9 @@ inline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks( // side. if (__right_bitset == 0) { _RandomAccessIterator __iter = __lm1; - for (int j = 0; j < __r_size; j++) { + for (int __j = 0; __j < __r_size; __j++) { bool __comp_result = __comp(*__iter, __pivot); - __right_bitset |= (static_cast<uint64_t>(__comp_result) << j); + __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j); --__iter; } } @@ -565,9 +464,9 @@ inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within( while (__left_bitset != 0) { difference_type __tz_left = __detail::__block_size - 1 - __libcpp_clz(__left_bitset); __left_bitset &= (static_cast<uint64_t>(1) << __tz_left) - 1; - _RandomAccessIterator it = __first + __tz_left; - if (it != __lm1) { - _Ops::iter_swap(it, __lm1); + _RandomAccessIterator __it = __first + __tz_left; + if (__it != __lm1) { + _Ops::iter_swap(__it, __lm1); } --__lm1; } @@ -578,9 +477,9 @@ inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within( while (__right_bitset != 0) { difference_type __tz_right = __detail::__block_size - 1 - __libcpp_clz(__right_bitset); __right_bitset &= (static_cast<uint64_t>(1) << __tz_right) - 1; - _RandomAccessIterator it = __lm1 - __tz_right; - if (it != __first) { - _Ops::iter_swap(it, __first); + _RandomAccessIterator __it = __lm1 - __tz_right; + if (__it != __first) { + _Ops::iter_swap(__it, __first); } ++__first; } @@ -601,15 +500,20 @@ __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, using _Ops = _IterOps<_AlgPolicy>; typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type; - _LIBCPP_ASSERT(__last - __first >= difference_type(3), ""); + _LIBCPP_ASSERT_UNCATEGORIZED(__last - __first >= difference_type(3), ""); + const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around + const _RandomAccessIterator __end = __last; (void)__end; // - _RandomAccessIterator __begin = __first; value_type __pivot(_Ops::__iter_move(__first)); // Find the first element greater than the pivot. if (__comp(__pivot, *(__last - difference_type(1)))) { // Not guarded since we know the last element is greater than the pivot. - while (!__comp(__pivot, *++__first)) { - } + do { + ++__first; + _LIBCPP_ASSERT_UNCATEGORIZED( + __first != __end, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + } while (!__comp(__pivot, *__first)); } else { while (++__first < __last && !__comp(__pivot, *__first)) { } @@ -618,8 +522,12 @@ __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, if (__first < __last) { // It will be always guarded because __introsort will do the median-of-three // before calling this. - while (__comp(__pivot, *--__last)) { - } + do { + _LIBCPP_ASSERT_UNCATEGORIZED( + __last != __begin, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + --__last; + } while (__comp(__pivot, *__last)); } // If the first element greater than the pivot is at or after the // last element less than or equal to the pivot, then we have covered the @@ -683,14 +591,19 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte using _Ops = _IterOps<_AlgPolicy>; typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; - _LIBCPP_ASSERT(__last - __first >= difference_type(3), ""); - _RandomAccessIterator __begin = __first; + _LIBCPP_ASSERT_UNCATEGORIZED(__last - __first >= difference_type(3), ""); + const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around + const _RandomAccessIterator __end = __last; (void)__end; // value_type __pivot(_Ops::__iter_move(__first)); // Find the first element greater or equal to the pivot. It will be always // guarded because __introsort will do the median-of-three before calling // this. - while (__comp(*++__first, __pivot)) - ; + do { + ++__first; + _LIBCPP_ASSERT_UNCATEGORIZED( + __first != __end, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + } while (__comp(*__first, __pivot)); // Find the last element less than the pivot. if (__begin == __first - difference_type(1)) { @@ -698,8 +611,12 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte ; } else { // Guarded. - while (!__comp(*--__last, __pivot)) - ; + do { + _LIBCPP_ASSERT_UNCATEGORIZED( + __last != __begin, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + --__last; + } while (!__comp(*__last, __pivot)); } // If the first element greater than or equal to the pivot is at or after the @@ -711,10 +628,18 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte // correct side of the pivot. while (__first < __last) { _Ops::iter_swap(__first, __last); - while (__comp(*++__first, __pivot)) - ; - while (!__comp(*--__last, __pivot)) - ; + do { + ++__first; + _LIBCPP_ASSERT_UNCATEGORIZED( + __first != __end, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + } while (__comp(*__first, __pivot)); + do { + _LIBCPP_ASSERT_UNCATEGORIZED( + __last != __begin, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + --__last; + } while (!__comp(*__last, __pivot)); } // Move the pivot to its correct position. _RandomAccessIterator __pivot_pos = __first - difference_type(1); @@ -733,12 +658,18 @@ __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIter using _Ops = _IterOps<_AlgPolicy>; typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; - _RandomAccessIterator __begin = __first; + // TODO(LLVM18): Make __begin const, see https://reviews.llvm.org/D147089#4349748 + _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around + const _RandomAccessIterator __end = __last; (void)__end; // value_type __pivot(_Ops::__iter_move(__first)); if (__comp(__pivot, *(__last - difference_type(1)))) { // Guarded. - while (!__comp(__pivot, *++__first)) { - } + do { + ++__first; + _LIBCPP_ASSERT_UNCATEGORIZED( + __first != __end, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + } while (!__comp(__pivot, *__first)); } else { while (++__first < __last && !__comp(__pivot, *__first)) { } @@ -747,15 +678,27 @@ __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIter if (__first < __last) { // It will be always guarded because __introsort will do the // median-of-three before calling this. - while (__comp(__pivot, *--__last)) { - } + do { + _LIBCPP_ASSERT_UNCATEGORIZED( + __last != __begin, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + --__last; + } while (__comp(__pivot, *__last)); } while (__first < __last) { _Ops::iter_swap(__first, __last); - while (!__comp(__pivot, *++__first)) - ; - while (__comp(__pivot, *--__last)) - ; + do { + ++__first; + _LIBCPP_ASSERT_UNCATEGORIZED( + __first != __end, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + } while (!__comp(__pivot, *__first)); + do { + _LIBCPP_ASSERT_UNCATEGORIZED( + __last != __begin, + "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); + --__last; + } while (__comp(__pivot, *__last)); } _RandomAccessIterator __pivot_pos = __first - difference_type(1); if (__begin != __pivot_pos) { @@ -862,10 +805,8 @@ void __introsort(_RandomAccessIterator __first, // [__first, __i) < *__i and *__i <= [__i+1, __last) // If we were given a perfect partition, see if insertion sort is quick... if (__ret.second) { - 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)) { + bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp); + if (std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp)) { if (__fs) return; __last = __i; @@ -904,84 +845,107 @@ inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { return __log2; } -template <class _WrappedComp, class _RandomAccessIterator> -_LIBCPP_HIDDEN void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) { +template <class _Comp, class _RandomAccessIterator> +void __sort(_RandomAccessIterator, _RandomAccessIterator, _Comp); + +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<char>&, char*>(char*, char*, __less<char>&); +#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); +#endif +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<short>&, short*>(short*, short*, __less<short>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<int>&, int*>(int*, int*, __less<int>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long>&, long*>(long*, long*, __less<long>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<float>&, float*>(float*, float*, __less<float>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<double>&, double*>(double*, double*, __less<double>&); +extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); + +template <class _AlgPolicy, class _RandomAccessIterator, class _Comp> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void +__sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __depth_limit = 2 * std::__log2i(__last - __first); - using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; - using _AlgPolicy = typename _Unwrap::_AlgPolicy; - using _Compare = typename _Unwrap::_Comp; - _Compare __comp = _Unwrap::__get_comp(__wrapped_comp); // Only use bitset partitioning for arithmetic types. We should also check // that the default comparator is in use so that we are sure that there are no // branches in the comparator. std::__introsort<_AlgPolicy, - _Compare, + _Comp&, _RandomAccessIterator, - __use_branchless_sort<_Compare, _RandomAccessIterator>::value>( + __use_branchless_sort<_Comp, _RandomAccessIterator>::value>( __first, __last, __comp, __depth_limit); } -template <class _Compare, class _Tp> -inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) { - __less<uintptr_t> __comp; - std::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); -} +template <class _Type, class... _Options> +using __is_any_of = _Or<is_same<_Type, _Options>...>; -extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&); +template <class _Type> +using __sort_is_specialized_in_library = __is_any_of< + _Type, + char, #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -extern template _LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); + wchar_t, #endif -extern template _LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&); -extern template _LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); - -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&); -#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); + signed char, + unsigned char, + short, + unsigned short, + int, + unsigned int, + long, + unsigned long, + long long, + unsigned long long, + float, + double, + long double>; + +template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<>&) { + __less<_Type> __comp; + std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); +} + +template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<_Type>&) { + __less<_Type> __comp; + std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); +} + +#if _LIBCPP_STD_VER >= 14 +template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<>&) { + __less<_Type> __comp; + std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); +} +#endif + +#if _LIBCPP_STD_VER >= 20 +template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, ranges::less&) { + __less<_Type> __comp; + std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); +} #endif -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); - -extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&); template <class _AlgPolicy, class _RandomAccessIterator, class _Comp> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { std::__debug_randomize_range<_AlgPolicy>(__first, __last); - using _Comp_ref = __comp_ref_type<_Comp>; if (__libcpp_is_constant_evaluated()) { - std::__partial_sort<_AlgPolicy>(__first, __last, __last, __comp); - + std::__partial_sort<_AlgPolicy>( + std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__last), __comp); } else { - using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Comp_ref>::type; - _Comp_ref __comp_ref(__comp); - _WrappedComp __wrapped_comp(__comp_ref); - std::__sort<_WrappedComp>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __wrapped_comp); + std::__sort_dispatch<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp); } + std::__check_strict_weak_ordering_sorted(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp); } template <class _RandomAccessIterator, class _Comp> @@ -993,7 +957,7 @@ void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __c template <class _RandomAccessIterator> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); + std::sort(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD |