diff options
Diffstat (limited to 'contrib/llvm-project/libcxx/include/__algorithm/stable_sort.h')
| -rw-r--r-- | contrib/llvm-project/libcxx/include/__algorithm/stable_sort.h | 75 |
1 files changed, 41 insertions, 34 deletions
diff --git a/contrib/llvm-project/libcxx/include/__algorithm/stable_sort.h b/contrib/llvm-project/libcxx/include/__algorithm/stable_sort.h index e3479aad62e6..6122758bdefe 100644 --- a/contrib/llvm-project/libcxx/include/__algorithm/stable_sort.h +++ b/contrib/llvm-project/libcxx/include/__algorithm/stable_sort.h @@ -12,11 +12,11 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/inplace_merge.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/sort.h> #include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> -#include <__utility/swap.h> #include <memory> #include <type_traits> @@ -26,12 +26,14 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Compare, class _InputIterator1, class _InputIterator2> +template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2> void __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_InputIterator1>::value_type value_type; __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h(__result, __d); @@ -40,111 +42,115 @@ __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, if (__first1 == __last1) { for (; __first2 != __last2; ++__first2, (void) ++__result, __d.template __incr<value_type>()) - ::new ((void*)__result) value_type(_VSTD::move(*__first2)); + ::new ((void*)__result) value_type(_Ops::__iter_move(__first2)); __h.release(); return; } if (__first2 == __last2) { for (; __first1 != __last1; ++__first1, (void) ++__result, __d.template __incr<value_type>()) - ::new ((void*)__result) value_type(_VSTD::move(*__first1)); + ::new ((void*)__result) value_type(_Ops::__iter_move(__first1)); __h.release(); return; } if (__comp(*__first2, *__first1)) { - ::new ((void*)__result) value_type(_VSTD::move(*__first2)); + ::new ((void*)__result) value_type(_Ops::__iter_move(__first2)); __d.template __incr<value_type>(); ++__first2; } else { - ::new ((void*)__result) value_type(_VSTD::move(*__first1)); + ::new ((void*)__result) value_type(_Ops::__iter_move(__first1)); __d.template __incr<value_type>(); ++__first1; } } } -template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> +template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> void __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + for (; __first1 != __last1; ++__result) { if (__first2 == __last2) { for (; __first1 != __last1; ++__first1, (void) ++__result) - *__result = _VSTD::move(*__first1); + *__result = _Ops::__iter_move(__first1); return; } if (__comp(*__first2, *__first1)) { - *__result = _VSTD::move(*__first2); + *__result = _Ops::__iter_move(__first2); ++__first2; } else { - *__result = _VSTD::move(*__first1); + *__result = _Ops::__iter_move(__first1); ++__first1; } } for (; __first2 != __last2; ++__first2, (void) ++__result) - *__result = _VSTD::move(*__first2); + *__result = _Ops::__iter_move(__first2); } -template <class _Compare, class _RandomAccessIterator> +template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> void __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size); -template <class _Compare, class _RandomAccessIterator> +template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> void __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, typename iterator_traits<_RandomAccessIterator>::value_type* __first2) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; switch (__len) { case 0: return; case 1: - ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); return; case 2: __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); if (__comp(*--__last1, *__first1)) { - ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1)); __d.template __incr<value_type>(); ++__first2; - ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); } else { - ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); __d.template __incr<value_type>(); ++__first2; - ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1)); } __h2.release(); return; } if (__len <= 8) { - _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); + std::__insertion_sort_move<_AlgPolicy, _Compare>(__first1, __last1, __first2, __comp); return; } typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; _RandomAccessIterator __m = __first1 + __l2; - _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); - _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); - _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); + std::__stable_sort<_AlgPolicy, _Compare>(__first1, __m, __comp, __l2, __first2, __l2); + std::__stable_sort<_AlgPolicy, _Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); + std::__merge_move_construct<_AlgPolicy, _Compare>(__first1, __m, __m, __last1, __first2, __comp); } template <class _Tp> @@ -153,7 +159,7 @@ struct __stable_sort_switch static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value; }; -template <class _Compare, class _RandomAccessIterator> +template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> void __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, @@ -168,12 +174,12 @@ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp return; case 2: if (__comp(*--__last, *__first)) - swap(*__first, *__last); + _IterOps<_AlgPolicy>::iter_swap(__first, __last); return; } if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) { - _VSTD::__insertion_sort<_Compare>(__first, __last, __comp); + std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp); return; } typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; @@ -182,11 +188,12 @@ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp { __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); - _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); + std::__stable_sort_move<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff); __d.__set(__l2, (value_type*)nullptr); - _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); + std::__stable_sort_move<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); __d.__set(__len, (value_type*)nullptr); - _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); + std::__merge_move_assign<_AlgPolicy, _Compare>( + __buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); // _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff), // move_iterator<value_type*>(__buff + __l2), // move_iterator<_RandomAccessIterator>(__buff + __l2), @@ -194,12 +201,12 @@ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp // __first, __comp); return; } - _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); - _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); - _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); + std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size); + std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); + std::__inplace_merge<_AlgPolicy, _Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); } -template <class _RandomAccessIterator, class _Compare> +template <class _AlgPolicy, class _RandomAccessIterator, class _Compare> inline _LIBCPP_HIDE_FROM_ABI void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; @@ -217,13 +224,13 @@ _LIBCPP_SUPPRESS_DEPRECATED_POP } using _Comp_ref = typename __comp_ref_type<_Compare>::type; - std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); + std::__stable_sort<_AlgPolicy, _Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); } template <class _RandomAccessIterator, class _Compare> inline _LIBCPP_HIDE_FROM_ABI void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - std::__stable_sort_impl(std::move(__first), std::move(__last), __comp); + std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> |