1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef _LIBCPP___ALGORITHM_STABLE_SORT_H
10 #define _LIBCPP___ALGORITHM_STABLE_SORT_H
11 
12 #include <__algorithm/comp.h>
13 #include <__algorithm/comp_ref_type.h>
14 #include <__algorithm/inplace_merge.h>
15 #include <__algorithm/iterator_operations.h>
16 #include <__algorithm/sort.h>
17 #include <__config>
18 #include <__iterator/iterator_traits.h>
19 #include <__utility/move.h>
20 #include <memory>
21 #include <type_traits>
22 
23 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
24 #  pragma GCC system_header
25 #endif
26 
27 _LIBCPP_BEGIN_NAMESPACE_STD
28 
29 template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2>
30 void
__merge_move_construct(_InputIterator1 __first1,_InputIterator1 __last1,_InputIterator2 __first2,_InputIterator2 __last2,typename iterator_traits<_InputIterator1>::value_type * __result,_Compare __comp)31 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
32         _InputIterator2 __first2, _InputIterator2 __last2,
33         typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
34 {
35     using _Ops = _IterOps<_AlgPolicy>;
36 
37     typedef typename iterator_traits<_InputIterator1>::value_type value_type;
38     __destruct_n __d(0);
39     unique_ptr<value_type, __destruct_n&> __h(__result, __d);
40     for (; true; ++__result)
41     {
42         if (__first1 == __last1)
43         {
44             for (; __first2 != __last2; ++__first2, (void) ++__result, __d.template __incr<value_type>())
45                 ::new ((void*)__result) value_type(_Ops::__iter_move(__first2));
46             __h.release();
47             return;
48         }
49         if (__first2 == __last2)
50         {
51             for (; __first1 != __last1; ++__first1, (void) ++__result, __d.template __incr<value_type>())
52                 ::new ((void*)__result) value_type(_Ops::__iter_move(__first1));
53             __h.release();
54             return;
55         }
56         if (__comp(*__first2, *__first1))
57         {
58             ::new ((void*)__result) value_type(_Ops::__iter_move(__first2));
59             __d.template __incr<value_type>();
60             ++__first2;
61         }
62         else
63         {
64             ::new ((void*)__result) value_type(_Ops::__iter_move(__first1));
65             __d.template __incr<value_type>();
66             ++__first1;
67         }
68     }
69 }
70 
71 template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
72 void
__merge_move_assign(_InputIterator1 __first1,_InputIterator1 __last1,_InputIterator2 __first2,_InputIterator2 __last2,_OutputIterator __result,_Compare __comp)73 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
74         _InputIterator2 __first2, _InputIterator2 __last2,
75         _OutputIterator __result, _Compare __comp)
76 {
77     using _Ops = _IterOps<_AlgPolicy>;
78 
79     for (; __first1 != __last1; ++__result)
80     {
81         if (__first2 == __last2)
82         {
83             for (; __first1 != __last1; ++__first1, (void) ++__result)
84                 *__result = _Ops::__iter_move(__first1);
85             return;
86         }
87         if (__comp(*__first2, *__first1))
88         {
89             *__result = _Ops::__iter_move(__first2);
90             ++__first2;
91         }
92         else
93         {
94             *__result = _Ops::__iter_move(__first1);
95             ++__first1;
96         }
97     }
98     for (; __first2 != __last2; ++__first2, (void) ++__result)
99         *__result = _Ops::__iter_move(__first2);
100 }
101 
102 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
103 void
104 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
105               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
106               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
107 
108 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
109 void
__stable_sort_move(_RandomAccessIterator __first1,_RandomAccessIterator __last1,_Compare __comp,typename iterator_traits<_RandomAccessIterator>::difference_type __len,typename iterator_traits<_RandomAccessIterator>::value_type * __first2)110 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
111                    typename iterator_traits<_RandomAccessIterator>::difference_type __len,
112                    typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
113 {
114     using _Ops = _IterOps<_AlgPolicy>;
115 
116     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
117     switch (__len)
118     {
119     case 0:
120         return;
121     case 1:
122         ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
123         return;
124     case 2:
125         __destruct_n __d(0);
126         unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
127         if (__comp(*--__last1, *__first1))
128         {
129             ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1));
130             __d.template __incr<value_type>();
131             ++__first2;
132             ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
133         }
134         else
135         {
136             ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
137             __d.template __incr<value_type>();
138             ++__first2;
139             ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1));
140         }
141         __h2.release();
142         return;
143     }
144     if (__len <= 8)
145     {
146         std::__insertion_sort_move<_AlgPolicy, _Compare>(__first1, __last1, __first2, __comp);
147         return;
148     }
149     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
150     _RandomAccessIterator __m = __first1 + __l2;
151     std::__stable_sort<_AlgPolicy, _Compare>(__first1, __m, __comp, __l2, __first2, __l2);
152     std::__stable_sort<_AlgPolicy, _Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
153     std::__merge_move_construct<_AlgPolicy, _Compare>(__first1, __m, __m, __last1, __first2, __comp);
154 }
155 
156 template <class _Tp>
157 struct __stable_sort_switch
158 {
159     static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
160 };
161 
162 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
163 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)164 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
165               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
166               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
167 {
168     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
169     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
170     switch (__len)
171     {
172     case 0:
173     case 1:
174         return;
175     case 2:
176         if (__comp(*--__last, *__first))
177             _IterOps<_AlgPolicy>::iter_swap(__first, __last);
178         return;
179     }
180     if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
181     {
182         std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
183         return;
184     }
185     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
186     _RandomAccessIterator __m = __first + __l2;
187     if (__len <= __buff_size)
188     {
189         __destruct_n __d(0);
190         unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
191         std::__stable_sort_move<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff);
192         __d.__set(__l2, (value_type*)nullptr);
193         std::__stable_sort_move<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
194         __d.__set(__len, (value_type*)nullptr);
195         std::__merge_move_assign<_AlgPolicy, _Compare>(
196             __buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
197 //         _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff),
198 //                                  move_iterator<value_type*>(__buff + __l2),
199 //                                  move_iterator<_RandomAccessIterator>(__buff + __l2),
200 //                                  move_iterator<_RandomAccessIterator>(__buff + __len),
201 //                                  __first, __comp);
202         return;
203     }
204     std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
205     std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
206     std::__inplace_merge<_AlgPolicy>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
207 }
208 
209 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
210 inline _LIBCPP_HIDE_FROM_ABI
__stable_sort_impl(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare & __comp)211 void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
212   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
213   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
214 
215   difference_type __len = __last - __first;
216   pair<value_type*, ptrdiff_t> __buf(0, 0);
217   unique_ptr<value_type, __return_temporary_buffer> __h;
218   if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {
219 // TODO: Remove the use of std::get_temporary_buffer
220 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
221       __buf = std::get_temporary_buffer<value_type>(__len);
222 _LIBCPP_SUPPRESS_DEPRECATED_POP
223       __h.reset(__buf.first);
224   }
225 
226   using _Comp_ref = typename __comp_ref_type<_Compare>::type;
227   std::__stable_sort<_AlgPolicy, _Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
228 }
229 
230 template <class _RandomAccessIterator, class _Compare>
231 inline _LIBCPP_HIDE_FROM_ABI
stable_sort(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)232 void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
233   std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
234 }
235 
236 template <class _RandomAccessIterator>
237 inline _LIBCPP_HIDE_FROM_ABI
stable_sort(_RandomAccessIterator __first,_RandomAccessIterator __last)238 void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
239   std::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
240 }
241 
242 _LIBCPP_END_NAMESPACE_STD
243 
244 #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H
245