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