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