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