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