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