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