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