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
__merge_move_construct(_InputIterator1 __first1,_InputIterator1 __last1,_InputIterator2 __first2,_InputIterator2 __last2,typename iterator_traits<_InputIterator1>::value_type * __result,_Compare __comp)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
__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 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
__stable_sort_move(_RandomAccessIterator __first1,_RandomAccessIterator __last1,_Compare __comp,typename iterator_traits<_RandomAccessIterator>::difference_type __len,typename iterator_traits<_RandomAccessIterator>::value_type * __first2)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
__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)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
stable_sort(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)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
stable_sort(_RandomAccessIterator __first,_RandomAccessIterator __last)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