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/radix_sort.h> 17 #include <__algorithm/sort.h> 18 #include <__config> 19 #include <__cstddef/ptrdiff_t.h> 20 #include <__debug_utils/strict_weak_ordering_check.h> 21 #include <__iterator/iterator_traits.h> 22 #include <__memory/destruct_n.h> 23 #include <__memory/unique_ptr.h> 24 #include <__memory/unique_temporary_buffer.h> 25 #include <__type_traits/desugars_to.h> 26 #include <__type_traits/enable_if.h> 27 #include <__type_traits/is_integral.h> 28 #include <__type_traits/is_same.h> 29 #include <__type_traits/is_trivially_assignable.h> 30 #include <__type_traits/remove_cvref.h> 31 #include <__utility/move.h> 32 #include <__utility/pair.h> 33 34 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 35 # pragma GCC system_header 36 #endif 37 38 _LIBCPP_PUSH_MACROS 39 #include <__undef_macros> 40 41 _LIBCPP_BEGIN_NAMESPACE_STD 42 43 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> 44 _LIBCPP_HIDE_FROM_ABI void __insertion_sort_move( 45 _BidirectionalIterator __first1, 46 _BidirectionalIterator __last1, 47 typename iterator_traits<_BidirectionalIterator>::value_type* __first2, 48 _Compare __comp) { 49 using _Ops = _IterOps<_AlgPolicy>; 50 51 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 52 if (__first1 != __last1) { 53 __destruct_n __d(0); 54 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 55 value_type* __last2 = __first2; 56 ::new ((void*)__last2) value_type(_Ops::__iter_move(__first1)); 57 __d.template __incr<value_type>(); 58 for (++__last2; ++__first1 != __last1; ++__last2) { 59 value_type* __j2 = __last2; 60 value_type* __i2 = __j2; 61 if (__comp(*__first1, *--__i2)) { 62 ::new ((void*)__j2) value_type(std::move(*__i2)); 63 __d.template __incr<value_type>(); 64 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 65 *__j2 = std::move(*__i2); 66 *__j2 = _Ops::__iter_move(__first1); 67 } else { 68 ::new ((void*)__j2) value_type(_Ops::__iter_move(__first1)); 69 __d.template __incr<value_type>(); 70 } 71 } 72 __h.release(); 73 } 74 } 75 76 template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2> 77 _LIBCPP_HIDE_FROM_ABI void __merge_move_construct( 78 _InputIterator1 __first1, 79 _InputIterator1 __last1, 80 _InputIterator2 __first2, 81 _InputIterator2 __last2, 82 typename iterator_traits<_InputIterator1>::value_type* __result, 83 _Compare __comp) { 84 using _Ops = _IterOps<_AlgPolicy>; 85 86 typedef typename iterator_traits<_InputIterator1>::value_type value_type; 87 __destruct_n __d(0); 88 unique_ptr<value_type, __destruct_n&> __h(__result, __d); 89 for (; true; ++__result) { 90 if (__first1 == __last1) { 91 for (; __first2 != __last2; ++__first2, (void)++__result, __d.template __incr<value_type>()) 92 ::new ((void*)__result) value_type(_Ops::__iter_move(__first2)); 93 __h.release(); 94 return; 95 } 96 if (__first2 == __last2) { 97 for (; __first1 != __last1; ++__first1, (void)++__result, __d.template __incr<value_type>()) 98 ::new ((void*)__result) value_type(_Ops::__iter_move(__first1)); 99 __h.release(); 100 return; 101 } 102 if (__comp(*__first2, *__first1)) { 103 ::new ((void*)__result) value_type(_Ops::__iter_move(__first2)); 104 __d.template __incr<value_type>(); 105 ++__first2; 106 } else { 107 ::new ((void*)__result) value_type(_Ops::__iter_move(__first1)); 108 __d.template __incr<value_type>(); 109 ++__first1; 110 } 111 } 112 } 113 114 template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 115 _LIBCPP_HIDE_FROM_ABI void __merge_move_assign( 116 _InputIterator1 __first1, 117 _InputIterator1 __last1, 118 _InputIterator2 __first2, 119 _InputIterator2 __last2, 120 _OutputIterator __result, 121 _Compare __comp) { 122 using _Ops = _IterOps<_AlgPolicy>; 123 124 for (; __first1 != __last1; ++__result) { 125 if (__first2 == __last2) { 126 for (; __first1 != __last1; ++__first1, (void)++__result) 127 *__result = _Ops::__iter_move(__first1); 128 return; 129 } 130 if (__comp(*__first2, *__first1)) { 131 *__result = _Ops::__iter_move(__first2); 132 ++__first2; 133 } else { 134 *__result = _Ops::__iter_move(__first1); 135 ++__first1; 136 } 137 } 138 for (; __first2 != __last2; ++__first2, (void)++__result) 139 *__result = _Ops::__iter_move(__first2); 140 } 141 142 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 143 void __stable_sort(_RandomAccessIterator __first, 144 _RandomAccessIterator __last, 145 _Compare __comp, 146 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 147 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, 148 ptrdiff_t __buff_size); 149 150 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 151 void __stable_sort_move(_RandomAccessIterator __first1, 152 _RandomAccessIterator __last1, 153 _Compare __comp, 154 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 155 typename iterator_traits<_RandomAccessIterator>::value_type* __first2) { 156 using _Ops = _IterOps<_AlgPolicy>; 157 158 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 159 switch (__len) { 160 case 0: 161 return; 162 case 1: 163 ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); 164 return; 165 case 2: 166 __destruct_n __d(0); 167 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); 168 if (__comp(*--__last1, *__first1)) { 169 ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1)); 170 __d.template __incr<value_type>(); 171 ++__first2; 172 ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); 173 } else { 174 ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); 175 __d.template __incr<value_type>(); 176 ++__first2; 177 ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1)); 178 } 179 __h2.release(); 180 return; 181 } 182 if (__len <= 8) { 183 std::__insertion_sort_move<_AlgPolicy, _Compare>(__first1, __last1, __first2, __comp); 184 return; 185 } 186 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 187 _RandomAccessIterator __m = __first1 + __l2; 188 std::__stable_sort<_AlgPolicy, _Compare>(__first1, __m, __comp, __l2, __first2, __l2); 189 std::__stable_sort<_AlgPolicy, _Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); 190 std::__merge_move_construct<_AlgPolicy, _Compare>(__first1, __m, __m, __last1, __first2, __comp); 191 } 192 193 template <class _Tp> 194 struct __stable_sort_switch { 195 static const unsigned value = 128 * is_trivially_copy_assignable<_Tp>::value; 196 }; 197 198 #if _LIBCPP_STD_VER >= 17 199 template <class _Tp> 200 _LIBCPP_HIDE_FROM_ABI constexpr unsigned __radix_sort_min_bound() { 201 static_assert(is_integral<_Tp>::value); 202 if constexpr (sizeof(_Tp) == 1) { 203 return 1 << 8; 204 } 205 206 return 1 << 10; 207 } 208 209 template <class _Tp> 210 _LIBCPP_HIDE_FROM_ABI constexpr unsigned __radix_sort_max_bound() { 211 static_assert(is_integral<_Tp>::value); 212 if constexpr (sizeof(_Tp) >= 8) { 213 return 1 << 15; 214 } 215 216 return 1 << 16; 217 } 218 #endif // _LIBCPP_STD_VER >= 17 219 220 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 221 void __stable_sort(_RandomAccessIterator __first, 222 _RandomAccessIterator __last, 223 _Compare __comp, 224 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 225 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, 226 ptrdiff_t __buff_size) { 227 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 228 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 229 switch (__len) { 230 case 0: 231 case 1: 232 return; 233 case 2: 234 if (__comp(*--__last, *__first)) 235 _IterOps<_AlgPolicy>::iter_swap(__first, __last); 236 return; 237 } 238 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) { 239 std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp); 240 return; 241 } 242 243 #if _LIBCPP_STD_VER >= 17 244 constexpr auto __default_comp = 245 __desugars_to_v<__totally_ordered_less_tag, __remove_cvref_t<_Compare>, value_type, value_type >; 246 constexpr auto __integral_value = 247 is_integral_v<value_type > && is_same_v< value_type&, __iter_reference<_RandomAccessIterator>>; 248 constexpr auto __allowed_radix_sort = __default_comp && __integral_value; 249 if constexpr (__allowed_radix_sort) { 250 if (__len <= __buff_size && __len >= static_cast<difference_type>(__radix_sort_min_bound<value_type>()) && 251 __len <= static_cast<difference_type>(__radix_sort_max_bound<value_type>())) { 252 std::__radix_sort(__first, __last, __buff); 253 return; 254 } 255 } 256 #endif // _LIBCPP_STD_VER >= 17 257 258 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 259 _RandomAccessIterator __m = __first + __l2; 260 if (__len <= __buff_size) { 261 __destruct_n __d(0); 262 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 263 std::__stable_sort_move<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff); 264 __d.__set(__l2, (value_type*)nullptr); 265 std::__stable_sort_move<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); 266 __d.__set(__len, (value_type*)nullptr); 267 std::__merge_move_assign<_AlgPolicy, _Compare>( 268 __buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); 269 // std::__merge<_Compare>(move_iterator<value_type*>(__buff), 270 // move_iterator<value_type*>(__buff + __l2), 271 // move_iterator<_RandomAccessIterator>(__buff + __l2), 272 // move_iterator<_RandomAccessIterator>(__buff + __len), 273 // __first, __comp); 274 return; 275 } 276 std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size); 277 std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); 278 std::__inplace_merge<_AlgPolicy>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); 279 } 280 281 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare> 282 inline _LIBCPP_HIDE_FROM_ABI void 283 __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { 284 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; 285 using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; 286 287 difference_type __len = __last - __first; 288 __unique_temporary_buffer<value_type> __unique_buf; 289 pair<value_type*, ptrdiff_t> __buf(0, 0); 290 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) { 291 __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len); 292 __buf.first = __unique_buf.get(); 293 __buf.second = __unique_buf.get_deleter().__count_; 294 } 295 296 std::__stable_sort<_AlgPolicy, __comp_ref_type<_Compare> >(__first, __last, __comp, __len, __buf.first, __buf.second); 297 std::__check_strict_weak_ordering_sorted(__first, __last, __comp); 298 } 299 300 template <class _RandomAccessIterator, class _Compare> 301 inline _LIBCPP_HIDE_FROM_ABI void 302 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 303 std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); 304 } 305 306 template <class _RandomAccessIterator> 307 inline _LIBCPP_HIDE_FROM_ABI void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { 308 std::stable_sort(__first, __last, __less<>()); 309 } 310 311 _LIBCPP_END_NAMESPACE_STD 312 313 _LIBCPP_POP_MACROS 314 315 #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H 316