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/rotate.h> 13 #include <__config> 14 #include <__iterator/advance.h> 15 #include <__iterator/distance.h> 16 #include <__iterator/iterator_traits.h> 17 #include <__utility/swap.h> 18 #include <memory> 19 20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21 # pragma GCC system_header 22 #endif 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 _ForwardIterator __first_false = _VSTD::__stable_partition<_Predicate&>(__first, __m, __pred, __len2, __p, __fit); 88 // TTTFFFFF?????????? 89 // f ff m l 90 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 91 _ForwardIterator __m1 = __m; 92 _ForwardIterator __second_false = __last; 93 _Distance __len_half = __len - __len2; 94 while (__pred(*__m1)) 95 { 96 if (++__m1 == __last) 97 goto __second_half_done; 98 --__len_half; 99 } 100 // TTTFFFFFTTTF?????? 101 // f ff m m1 l 102 __second_false = _VSTD::__stable_partition<_Predicate&>(__m1, __last, __pred, __len_half, __p, __fit); 103 __second_half_done: 104 // TTTFFFFFTTTTTFFFFF 105 // f ff m sf l 106 return _VSTD::rotate(__first_false, __m, __second_false); 107 // TTTTTTTTFFFFFFFFFF 108 // | 109 } 110 111 template <class _Predicate, class _ForwardIterator> 112 _ForwardIterator 113 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 114 forward_iterator_tag) 115 { 116 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment 117 // Either prove all true and return __first or point to first false 118 while (true) 119 { 120 if (__first == __last) 121 return __first; 122 if (!__pred(*__first)) 123 break; 124 ++__first; 125 } 126 // We now have a reduced range [__first, __last) 127 // *__first is known to be false 128 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 129 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 130 difference_type __len = _VSTD::distance(__first, __last); 131 pair<value_type*, ptrdiff_t> __p(0, 0); 132 unique_ptr<value_type, __return_temporary_buffer> __h; 133 if (__len >= __alloc_limit) 134 { 135 // TODO: Remove the use of std::get_temporary_buffer 136 _LIBCPP_SUPPRESS_DEPRECATED_PUSH 137 __p = _VSTD::get_temporary_buffer<value_type>(__len); 138 _LIBCPP_SUPPRESS_DEPRECATED_POP 139 __h.reset(__p.first); 140 } 141 return _VSTD::__stable_partition<_Predicate&>(__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 __first_false = _VSTD::__stable_partition<_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 { 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<_Predicate&>(__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 // TODO: Remove the use of std::get_temporary_buffer 285 _LIBCPP_SUPPRESS_DEPRECATED_PUSH 286 __p = _VSTD::get_temporary_buffer<value_type>(__len); 287 _LIBCPP_SUPPRESS_DEPRECATED_POP 288 __h.reset(__p.first); 289 } 290 return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); 291 } 292 293 template <class _ForwardIterator, class _Predicate> 294 inline _LIBCPP_INLINE_VISIBILITY 295 _ForwardIterator 296 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 297 { 298 return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 299 } 300 301 _LIBCPP_END_NAMESPACE_STD 302 303 #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H 304