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