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