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