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