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_PARTITION_H 10 #define _LIBCPP___ALGORITHM_STABLE_PARTITION_H 11 12 #include <__algorithm/iterator_operations.h> 13 #include <__algorithm/rotate.h> 14 #include <__config> 15 #include <__iterator/advance.h> 16 #include <__iterator/distance.h> 17 #include <__iterator/iterator_traits.h> 18 #include <__memory/destruct_n.h> 19 #include <__memory/temporary_buffer.h> 20 #include <__memory/unique_ptr.h> 21 #include <__utility/pair.h> 22 #include <new> 23 #include <type_traits> 24 25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26 # pragma GCC system_header 27 #endif 28 29 _LIBCPP_BEGIN_NAMESPACE_STD 30 31 template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair> 32 _LIBCPP_HIDE_FROM_ABI _ForwardIterator 33 __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 34 _Distance __len, _Pair __p, forward_iterator_tag __fit) 35 { 36 using _Ops = _IterOps<_AlgPolicy>; 37 38 // *__first is known to be false 39 // __len >= 1 40 if (__len == 1) 41 return __first; 42 if (__len == 2) 43 { 44 _ForwardIterator __m = __first; 45 if (__pred(*++__m)) 46 { 47 _Ops::iter_swap(__first, __m); 48 return __m; 49 } 50 return __first; 51 } 52 if (__len <= __p.second) 53 { // The buffer is big enough to use 54 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 55 __destruct_n __d(0); 56 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 57 // Move the falses into the temporary buffer, and the trues to the front of the line 58 // Update __first to always point to the end of the trues 59 value_type* __t = __p.first; 60 ::new ((void*)__t) value_type(_Ops::__iter_move(__first)); 61 __d.template __incr<value_type>(); 62 ++__t; 63 _ForwardIterator __i = __first; 64 while (++__i != __last) 65 { 66 if (__pred(*__i)) 67 { 68 *__first = _Ops::__iter_move(__i); 69 ++__first; 70 } 71 else 72 { 73 ::new ((void*)__t) value_type(_Ops::__iter_move(__i)); 74 __d.template __incr<value_type>(); 75 ++__t; 76 } 77 } 78 // All trues now at start of range, all falses in buffer 79 // Move falses back into range, but don't mess up __first which points to first false 80 __i = __first; 81 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) 82 *__i = _Ops::__iter_move(__t2); 83 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 84 return __first; 85 } 86 // Else not enough buffer, do in place 87 // __len >= 3 88 _ForwardIterator __m = __first; 89 _Distance __len2 = __len / 2; // __len2 >= 2 90 _Ops::advance(__m, __len2); 91 // recurse on [__first, __m), *__first know to be false 92 // F????????????????? 93 // f m l 94 _ForwardIterator __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>( 95 __first, __m, __pred, __len2, __p, __fit); 96 // TTTFFFFF?????????? 97 // f ff m l 98 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 99 _ForwardIterator __m1 = __m; 100 _ForwardIterator __second_false = __last; 101 _Distance __len_half = __len - __len2; 102 while (__pred(*__m1)) 103 { 104 if (++__m1 == __last) 105 goto __second_half_done; 106 --__len_half; 107 } 108 // TTTFFFFFTTTF?????? 109 // f ff m m1 l 110 __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>( 111 __m1, __last, __pred, __len_half, __p, __fit); 112 __second_half_done: 113 // TTTFFFFFTTTTTFFFFF 114 // f ff m sf l 115 return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first; 116 // TTTTTTTTFFFFFFFFFF 117 // | 118 } 119 120 template <class _AlgPolicy, class _Predicate, class _ForwardIterator> 121 _LIBCPP_HIDE_FROM_ABI _ForwardIterator 122 __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 123 forward_iterator_tag) 124 { 125 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment 126 // Either prove all true and return __first or point to first false 127 while (true) 128 { 129 if (__first == __last) 130 return __first; 131 if (!__pred(*__first)) 132 break; 133 ++__first; 134 } 135 // We now have a reduced range [__first, __last) 136 // *__first is known to be false 137 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 138 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 139 difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last); 140 pair<value_type*, ptrdiff_t> __p(0, 0); 141 unique_ptr<value_type, __return_temporary_buffer> __h; 142 if (__len >= __alloc_limit) 143 { 144 // TODO: Remove the use of std::get_temporary_buffer 145 _LIBCPP_SUPPRESS_DEPRECATED_PUSH 146 __p = _VSTD::get_temporary_buffer<value_type>(__len); 147 _LIBCPP_SUPPRESS_DEPRECATED_POP 148 __h.reset(__p.first); 149 } 150 return std::__stable_partition_impl<_AlgPolicy, _Predicate&>( 151 std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag()); 152 } 153 154 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> 155 _BidirectionalIterator 156 __stable_partition_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 157 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit) 158 { 159 using _Ops = _IterOps<_AlgPolicy>; 160 161 // *__first is known to be false 162 // *__last is known to be true 163 // __len >= 2 164 if (__len == 2) 165 { 166 _Ops::iter_swap(__first, __last); 167 return __last; 168 } 169 if (__len == 3) 170 { 171 _BidirectionalIterator __m = __first; 172 if (__pred(*++__m)) 173 { 174 _Ops::iter_swap(__first, __m); 175 _Ops::iter_swap(__m, __last); 176 return __last; 177 } 178 _Ops::iter_swap(__m, __last); 179 _Ops::iter_swap(__first, __m); 180 return __m; 181 } 182 if (__len <= __p.second) 183 { // The buffer is big enough to use 184 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 185 __destruct_n __d(0); 186 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 187 // Move the falses into the temporary buffer, and the trues to the front of the line 188 // Update __first to always point to the end of the trues 189 value_type* __t = __p.first; 190 ::new ((void*)__t) value_type(_Ops::__iter_move(__first)); 191 __d.template __incr<value_type>(); 192 ++__t; 193 _BidirectionalIterator __i = __first; 194 while (++__i != __last) 195 { 196 if (__pred(*__i)) 197 { 198 *__first = _Ops::__iter_move(__i); 199 ++__first; 200 } 201 else 202 { 203 ::new ((void*)__t) value_type(_Ops::__iter_move(__i)); 204 __d.template __incr<value_type>(); 205 ++__t; 206 } 207 } 208 // move *__last, known to be true 209 *__first = _Ops::__iter_move(__i); 210 __i = ++__first; 211 // All trues now at start of range, all falses in buffer 212 // Move falses back into range, but don't mess up __first which points to first false 213 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) 214 *__i = _Ops::__iter_move(__t2); 215 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 216 return __first; 217 } 218 // Else not enough buffer, do in place 219 // __len >= 4 220 _BidirectionalIterator __m = __first; 221 _Distance __len2 = __len / 2; // __len2 >= 2 222 _Ops::advance(__m, __len2); 223 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false 224 // F????????????????T 225 // f m l 226 _BidirectionalIterator __m1 = __m; 227 _BidirectionalIterator __first_false = __first; 228 _Distance __len_half = __len2; 229 while (!__pred(*--__m1)) 230 { 231 if (__m1 == __first) 232 goto __first_half_done; 233 --__len_half; 234 } 235 // F???TFFF?????????T 236 // f m1 m l 237 __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>( 238 __first, __m1, __pred, __len_half, __p, __bit); 239 __first_half_done: 240 // TTTFFFFF?????????T 241 // f ff m l 242 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 243 __m1 = __m; 244 _BidirectionalIterator __second_false = __last; 245 ++__second_false; 246 __len_half = __len - __len2; 247 while (__pred(*__m1)) 248 { 249 if (++__m1 == __last) 250 goto __second_half_done; 251 --__len_half; 252 } 253 // TTTFFFFFTTTF?????T 254 // f ff m m1 l 255 __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>( 256 __m1, __last, __pred, __len_half, __p, __bit); 257 __second_half_done: 258 // TTTFFFFFTTTTTFFFFF 259 // f ff m sf l 260 return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first; 261 // TTTTTTTTFFFFFFFFFF 262 // | 263 } 264 265 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator> 266 _LIBCPP_HIDE_FROM_ABI _BidirectionalIterator 267 __stable_partition_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 268 bidirectional_iterator_tag) 269 { 270 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 271 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 272 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment 273 // Either prove all true and return __first or point to first false 274 while (true) 275 { 276 if (__first == __last) 277 return __first; 278 if (!__pred(*__first)) 279 break; 280 ++__first; 281 } 282 // __first points to first false, everything prior to __first is already set. 283 // Either prove [__first, __last) is all false and return __first, or point __last to last true 284 do 285 { 286 if (__first == --__last) 287 return __first; 288 } while (!__pred(*__last)); 289 // We now have a reduced range [__first, __last] 290 // *__first is known to be false 291 // *__last is known to be true 292 // __len >= 2 293 difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1; 294 pair<value_type*, ptrdiff_t> __p(0, 0); 295 unique_ptr<value_type, __return_temporary_buffer> __h; 296 if (__len >= __alloc_limit) 297 { 298 // TODO: Remove the use of std::get_temporary_buffer 299 _LIBCPP_SUPPRESS_DEPRECATED_PUSH 300 __p = _VSTD::get_temporary_buffer<value_type>(__len); 301 _LIBCPP_SUPPRESS_DEPRECATED_POP 302 __h.reset(__p.first); 303 } 304 return std::__stable_partition_impl<_AlgPolicy, _Predicate&>( 305 std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag()); 306 } 307 308 template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory> 309 _LIBCPP_HIDE_FROM_ABI 310 _ForwardIterator __stable_partition( 311 _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) { 312 return std::__stable_partition_impl<_AlgPolicy, __uncvref_t<_Predicate>&>( 313 std::move(__first), std::move(__last), __pred, __iter_category); 314 } 315 316 template <class _ForwardIterator, class _Predicate> 317 inline _LIBCPP_INLINE_VISIBILITY 318 _ForwardIterator 319 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 320 { 321 using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category; 322 return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>( 323 std::move(__first), std::move(__last), __pred, _IterCategory()); 324 } 325 326 _LIBCPP_END_NAMESPACE_STD 327 328 #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H 329