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