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