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