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 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 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 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 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 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 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 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