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