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