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