v1/__algorithm/stable_sort.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_STABLE_SORT_H
0010 #define _LIBCPP___ALGORITHM_STABLE_SORT_H
0011
0012 #include <__algorithm/comp.h>
0013 #include <__algorithm/comp_ref_type.h>
0014 #include <__algorithm/inplace_merge.h>
0015 #include <__algorithm/iterator_operations.h>
0016 #include <__algorithm/radix_sort.h>
0017 #include <__algorithm/sort.h>
0018 #include <__config>
0019 #include <__cstddef/ptrdiff_t.h>
0020 #include <__debug_utils/strict_weak_ordering_check.h>
0021 #include <__iterator/iterator_traits.h>
0022 #include <__memory/construct_at.h>
0023 #include <__memory/destruct_n.h>
0024 #include <__memory/unique_ptr.h>
0025 #include <__memory/unique_temporary_buffer.h>
0026 #include <__type_traits/desugars_to.h>
0027 #include <__type_traits/enable_if.h>
0028 #include <__type_traits/is_integral.h>
0029 #include <__type_traits/is_same.h>
0030 #include <__type_traits/is_trivially_assignable.h>
0031 #include <__type_traits/remove_cvref.h>
0032 #include <__utility/move.h>
0033 #include <__utility/pair.h>
0034
0035 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0036 #  pragma GCC system_header
0037 #endif
0038
0039 _LIBCPP_PUSH_MACROS
0040 #include <__undef_macros>
0041
0042 _LIBCPP_BEGIN_NAMESPACE_STD
0043
0044 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
0045 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __insertion_sort_move(
0046     _BidirectionalIterator __first1,
0047     _BidirectionalIterator __last1,
0048     typename iterator_traits<_BidirectionalIterator>::value_type* __first2,
0049     _Compare __comp) {
0050   using _Ops = _IterOps<_AlgPolicy>;
0051
0052   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
0053   if (__first1 != __last1) {
0054     __destruct_n __d(0);
0055     unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
0056     value_type* __last2 = __first2;
0057     std::__construct_at(__last2, _Ops::__iter_move(__first1));
0058     __d.template __incr<value_type>();
0059     for (++__last2; ++__first1 != __last1; ++__last2) {
0060       value_type* __j2 = __last2;
0061       value_type* __i2 = __j2;
0062       if (__comp(*__first1, *--__i2)) {
0063         std::__construct_at(__j2, std::move(*__i2));
0064         __d.template __incr<value_type>();
0065         for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
0066           *__j2 = std::move(*__i2);
0067         *__j2 = _Ops::__iter_move(__first1);
0068       } else {
0069         std::__construct_at(__j2, _Ops::__iter_move(__first1));
0070         __d.template __incr<value_type>();
0071       }
0072     }
0073     __h.release();
0074   }
0075 }
0076
0077 template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2>
0078 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __merge_move_construct(
0079     _InputIterator1 __first1,
0080     _InputIterator1 __last1,
0081     _InputIterator2 __first2,
0082     _InputIterator2 __last2,
0083     typename iterator_traits<_InputIterator1>::value_type* __result,
0084     _Compare __comp) {
0085   using _Ops = _IterOps<_AlgPolicy>;
0086
0087   typedef typename iterator_traits<_InputIterator1>::value_type value_type;
0088   __destruct_n __d(0);
0089   unique_ptr<value_type, __destruct_n&> __h(__result, __d);
0090   for (; true; ++__result) {
0091     if (__first1 == __last1) {
0092       for (; __first2 != __last2; ++__first2, (void)++__result, __d.template __incr<value_type>())
0093         std::__construct_at(__result, _Ops::__iter_move(__first2));
0094       __h.release();
0095       return;
0096     }
0097     if (__first2 == __last2) {
0098       for (; __first1 != __last1; ++__first1, (void)++__result, __d.template __incr<value_type>())
0099         std::__construct_at(__result, _Ops::__iter_move(__first1));
0100       __h.release();
0101       return;
0102     }
0103     if (__comp(*__first2, *__first1)) {
0104       std::__construct_at(__result, _Ops::__iter_move(__first2));
0105       __d.template __incr<value_type>();
0106       ++__first2;
0107     } else {
0108       std::__construct_at(__result, _Ops::__iter_move(__first1));
0109       __d.template __incr<value_type>();
0110       ++__first1;
0111     }
0112   }
0113 }
0114
0115 template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
0116 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __merge_move_assign(
0117     _InputIterator1 __first1,
0118     _InputIterator1 __last1,
0119     _InputIterator2 __first2,
0120     _InputIterator2 __last2,
0121     _OutputIterator __result,
0122     _Compare __comp) {
0123   using _Ops = _IterOps<_AlgPolicy>;
0124
0125   for (; __first1 != __last1; ++__result) {
0126     if (__first2 == __last2) {
0127       for (; __first1 != __last1; ++__first1, (void)++__result)
0128         *__result = _Ops::__iter_move(__first1);
0129       return;
0130     }
0131     if (__comp(*__first2, *__first1)) {
0132       *__result = _Ops::__iter_move(__first2);
0133       ++__first2;
0134     } else {
0135       *__result = _Ops::__iter_move(__first1);
0136       ++__first1;
0137     }
0138   }
0139   for (; __first2 != __last2; ++__first2, (void)++__result)
0140     *__result = _Ops::__iter_move(__first2);
0141 }
0142
0143 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
0144 _LIBCPP_CONSTEXPR_SINCE_CXX26 void __stable_sort(
0145     _RandomAccessIterator __first,
0146     _RandomAccessIterator __last,
0147     _Compare __comp,
0148     typename iterator_traits<_RandomAccessIterator>::difference_type __len,
0149     typename iterator_traits<_RandomAccessIterator>::value_type* __buff,
0150     ptrdiff_t __buff_size);
0151
0152 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
0153 _LIBCPP_CONSTEXPR_SINCE_CXX26 void __stable_sort_move(
0154     _RandomAccessIterator __first1,
0155     _RandomAccessIterator __last1,
0156     _Compare __comp,
0157     typename iterator_traits<_RandomAccessIterator>::difference_type __len,
0158     typename iterator_traits<_RandomAccessIterator>::value_type* __first2) {
0159   using _Ops = _IterOps<_AlgPolicy>;
0160
0161   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
0162   switch (__len) {
0163   case 0:
0164     return;
0165   case 1:
0166     std::__construct_at(__first2, _Ops::__iter_move(__first1));
0167     return;
0168   case 2:
0169     __destruct_n __d(0);
0170     unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
0171     if (__comp(*--__last1, *__first1)) {
0172       std::__construct_at(__first2, _Ops::__iter_move(__last1));
0173       __d.template __incr<value_type>();
0174       ++__first2;
0175       std::__construct_at(__first2, _Ops::__iter_move(__first1));
0176     } else {
0177       std::__construct_at(__first2, _Ops::__iter_move(__first1));
0178       __d.template __incr<value_type>();
0179       ++__first2;
0180       std::__construct_at(__first2, _Ops::__iter_move(__last1));
0181     }
0182     __h2.release();
0183     return;
0184   }
0185   if (__len <= 8) {
0186     std::__insertion_sort_move<_AlgPolicy, _Compare>(__first1, __last1, __first2, __comp);
0187     return;
0188   }
0189   typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
0190   _RandomAccessIterator __m                                             = __first1 + __l2;
0191   std::__stable_sort<_AlgPolicy, _Compare>(__first1, __m, __comp, __l2, __first2, __l2);
0192   std::__stable_sort<_AlgPolicy, _Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
0193   std::__merge_move_construct<_AlgPolicy, _Compare>(__first1, __m, __m, __last1, __first2, __comp);
0194 }
0195
0196 template <class _Tp>
0197 struct __stable_sort_switch {
0198   static const unsigned value = 128 * is_trivially_copy_assignable<_Tp>::value;
0199 };
0200
0201 #if _LIBCPP_STD_VER >= 17
0202 template <class _Tp>
0203 _LIBCPP_HIDE_FROM_ABI constexpr unsigned __radix_sort_min_bound() {
0204   static_assert(is_integral<_Tp>::value);
0205   if constexpr (sizeof(_Tp) == 1) {
0206     return 1 << 8;
0207   }
0208
0209   return 1 << 10;
0210 }
0211
0212 template <class _Tp>
0213 _LIBCPP_HIDE_FROM_ABI constexpr unsigned __radix_sort_max_bound() {
0214   static_assert(is_integral<_Tp>::value);
0215   if constexpr (sizeof(_Tp) >= 8) {
0216     return 1 << 15;
0217   }
0218
0219   return 1 << 16;
0220 }
0221 #endif // _LIBCPP_STD_VER >= 17
0222
0223 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
0224 _LIBCPP_CONSTEXPR_SINCE_CXX26 void __stable_sort(
0225     _RandomAccessIterator __first,
0226     _RandomAccessIterator __last,
0227     _Compare __comp,
0228     typename iterator_traits<_RandomAccessIterator>::difference_type __len,
0229     typename iterator_traits<_RandomAccessIterator>::value_type* __buff,
0230     ptrdiff_t __buff_size) {
0231   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
0232   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
0233   switch (__len) {
0234   case 0:
0235   case 1:
0236     return;
0237   case 2:
0238     if (__comp(*--__last, *__first))
0239       _IterOps<_AlgPolicy>::iter_swap(__first, __last);
0240     return;
0241   }
0242   if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {
0243     std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
0244     return;
0245   }
0246
0247 #if _LIBCPP_STD_VER >= 17
0248   constexpr auto __default_comp =
0249       __desugars_to_v<__totally_ordered_less_tag, __remove_cvref_t<_Compare>, value_type, value_type >;
0250   constexpr auto __integral_value =
0251       is_integral_v<value_type > && is_same_v< value_type&, __iter_reference<_RandomAccessIterator>>;
0252   constexpr auto __allowed_radix_sort = __default_comp && __integral_value;
0253   if constexpr (__allowed_radix_sort) {
0254     if (__len <= __buff_size && __len >= static_cast<difference_type>(__radix_sort_min_bound<value_type>()) &&
0255         __len <= static_cast<difference_type>(__radix_sort_max_bound<value_type>())) {
0256       std::__radix_sort(__first, __last, __buff);
0257       return;
0258     }
0259   }
0260 #endif // _LIBCPP_STD_VER >= 17
0261
0262   typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
0263   _RandomAccessIterator __m                                             = __first + __l2;
0264   if (__len <= __buff_size) {
0265     __destruct_n __d(0);
0266     unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
0267     std::__stable_sort_move<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff);
0268     __d.__set(__l2, (value_type*)nullptr);
0269     std::__stable_sort_move<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
0270     __d.__set(__len, (value_type*)nullptr);
0271     std::__merge_move_assign<_AlgPolicy, _Compare>(
0272         __buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
0273     //         std::__merge<_Compare>(move_iterator<value_type*>(__buff),
0274     //                                  move_iterator<value_type*>(__buff + __l2),
0275     //                                  move_iterator<_RandomAccessIterator>(__buff + __l2),
0276     //                                  move_iterator<_RandomAccessIterator>(__buff + __len),
0277     //                                  __first, __comp);
0278     return;
0279   }
0280   std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
0281   std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
0282   std::__inplace_merge<_AlgPolicy>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
0283 }
0284
0285 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
0286 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
0287 __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
0288   using value_type      = typename iterator_traits<_RandomAccessIterator>::value_type;
0289   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
0290
0291   difference_type __len = __last - __first;
0292   __unique_temporary_buffer<value_type> __unique_buf;
0293   pair<value_type*, ptrdiff_t> __buf(0, 0);
0294   if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {
0295     __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
0296     __buf.first  = __unique_buf.get();
0297     __buf.second = __unique_buf.get_deleter().__count_;
0298   }
0299
0300   std::__stable_sort<_AlgPolicy, __comp_ref_type<_Compare> >(__first, __last, __comp, __len, __buf.first, __buf.second);
0301   std::__check_strict_weak_ordering_sorted(__first, __last, __comp);
0302 }
0303
0304 template <class _RandomAccessIterator, class _Compare>
0305 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
0306 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
0307   std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
0308 }
0309
0310 template <class _RandomAccessIterator>
0311 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
0312 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
0313   std::stable_sort(__first, __last, __less<>());
0314 }
0315
0316 _LIBCPP_END_NAMESPACE_STD
0317 _LIBCPP_POP_MACROS
0318
0319 #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H