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