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 @@ -123,6 +123,86 @@ return __r; } +// Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary. +template +inline _LIBCPP_HIDDEN void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + bool __r = __c(*__x, *__y); + value_type __tmp = __r ? *__x : *__y; + *__y = __r ? *__y : *__x; + *__x = __tmp; +} + +// Ensures that *__x, *__y and *__z are ordered according to the comparator __c, +// under the assumption that *__y and *__z are already ordered. +template +inline _LIBCPP_HIDDEN void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, + _RandomAccessIterator __z, _Compare __c) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + bool __r = __c(*__z, *__x); + value_type __tmp = __r ? *__z : *__x; + *__z = __r ? *__x : *__z; + __r = __c(__tmp, *__y); + *__x = __r ? *__x : *__y; + *__y = __r ? *__y : __tmp; +} + +template +inline _LIBCPP_HIDDEN + __enable_if_t<_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void> + __sort3_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) { + _VSTD::__cond_swap(__x2, __x3, __c); + _VSTD::__partially_sorted_swap(__x1, __x2, __x3, __c); +} + +template +inline _LIBCPP_HIDDEN + __enable_if_t::value_type>::value, void> + __sort3_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) { + _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); +} + +template +inline _LIBCPP_HIDDEN + __enable_if_t<_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void> + __sort4_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _RandomAccessIterator __x4, _Compare __c) { + _VSTD::__cond_swap(__x1, __x3, __c); + _VSTD::__cond_swap(__x2, __x4, __c); + _VSTD::__cond_swap(__x1, __x2, __c); + _VSTD::__cond_swap(__x3, __x4, __c); + _VSTD::__cond_swap(__x2, __x3, __c); +} + +template +inline _LIBCPP_HIDDEN + __enable_if_t::value_type>::value, void> + __sort4_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _RandomAccessIterator __x4, _Compare __c) { + _VSTD::__sort4(__x1, __x2, __x3, __x4, __c); +} + +template +inline _LIBCPP_HIDDEN + __enable_if_t<_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void> + __sort5_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { + _VSTD::__cond_swap(__x1, __x2, __c); + _VSTD::__cond_swap(__x4, __x5, __c); + _VSTD::__partially_sorted_swap(__x3, __x4, __x5, __c); + _VSTD::__cond_swap(__x2, __x5, __c); + _VSTD::__partially_sorted_swap(__x1, __x3, __x4, __c); + _VSTD::__partially_sorted_swap(__x2, __x3, __x4, __c); +} + +template +inline _LIBCPP_HIDDEN + __enable_if_t::value_type>::value, void> + __sort5_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { + _VSTD::__sort5(__x1, __x2, __x3, __x4, __x5, __c); +} + // Assumes size > 0 template _LIBCPP_CONSTEXPR_AFTER_CXX11 void @@ -163,7 +243,7 @@ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+difference_type(2); - _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp); + _VSTD::__sort3_internal<_Compare>(__first, __first + difference_type(1), __j, __comp); for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i) { if (__comp(*__i, *__j)) @@ -197,18 +277,20 @@ swap(*__first, *__last); return true; case 3: - _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp); - return true; + _VSTD::__sort3_internal<_Compare>(__first, __first + difference_type(1), --__last, __comp); + return true; case 4: - _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp); - return true; + _VSTD::__sort4_internal<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), --__last, + __comp); + return true; case 5: - _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp); - return true; + _VSTD::__sort5_internal<_Compare>(__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); - _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp); + _VSTD::__sort3_internal<_Compare>(__first, __first + difference_type(1), __j, __comp); const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i) @@ -290,14 +372,16 @@ swap(*__first, *__last); return; case 3: - _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp); - return; + _VSTD::__sort3_internal<_Compare>(__first, __first + difference_type(1), --__last, __comp); + return; case 4: - _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp); - return; + _VSTD::__sort4_internal<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), + --__last, __comp); + return; case 5: - _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp); - return; + _VSTD::__sort5_internal<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), + __first + difference_type(3), --__last, __comp); + return; } if (__len <= __limit) {