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 __p = _VSTD::get_temporary_buffer<value_type>(__len); 136 __h.reset(__p.first); 137 } 138 return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, forward_iterator_tag()); 139 } 140 141 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> 142 _BidirectionalIterator 143 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 144 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit) 145 { 146 // *__first is known to be false 147 // *__last is known to be true 148 // __len >= 2 149 if (__len == 2) 150 { 151 swap(*__first, *__last); 152 return __last; 153 } 154 if (__len == 3) 155 { 156 _BidirectionalIterator __m = __first; 157 if (__pred(*++__m)) 158 { 159 swap(*__first, *__m); 160 swap(*__m, *__last); 161 return __last; 162 } 163 swap(*__m, *__last); 164 swap(*__first, *__m); 165 return __m; 166 } 167 if (__len <= __p.second) 168 { // The buffer is big enough to use 169 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 170 __destruct_n __d(0); 171 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 172 // Move the falses into the temporary buffer, and the trues to the front of the line 173 // Update __first to always point to the end of the trues 174 value_type* __t = __p.first; 175 ::new ((void*)__t) value_type(_VSTD::move(*__first)); 176 __d.template __incr<value_type>(); 177 ++__t; 178 _BidirectionalIterator __i = __first; 179 while (++__i != __last) 180 { 181 if (__pred(*__i)) 182 { 183 *__first = _VSTD::move(*__i); 184 ++__first; 185 } 186 else 187 { 188 ::new ((void*)__t) value_type(_VSTD::move(*__i)); 189 __d.template __incr<value_type>(); 190 ++__t; 191 } 192 } 193 // move *__last, known to be true 194 *__first = _VSTD::move(*__i); 195 __i = ++__first; 196 // All trues now at start of range, all falses in buffer 197 // Move falses back into range, but don't mess up __first which points to first false 198 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) 199 *__i = _VSTD::move(*__t2); 200 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 201 return __first; 202 } 203 // Else not enough buffer, do in place 204 // __len >= 4 205 _BidirectionalIterator __m = __first; 206 _Distance __len2 = __len / 2; // __len2 >= 2 207 _VSTD::advance(__m, __len2); 208 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false 209 // F????????????????T 210 // f m l 211 _BidirectionalIterator __m1 = __m; 212 _BidirectionalIterator __first_false = __first; 213 _Distance __len_half = __len2; 214 while (!__pred(*--__m1)) 215 { 216 if (__m1 == __first) 217 goto __first_half_done; 218 --__len_half; 219 } 220 // F???TFFF?????????T 221 // f m1 m l 222 __first_false = _VSTD::__stable_partition<_Predicate&>(__first, __m1, __pred, __len_half, __p, __bit); 223 __first_half_done: 224 // TTTFFFFF?????????T 225 // f ff m l 226 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 227 __m1 = __m; 228 _BidirectionalIterator __second_false = __last; 229 ++__second_false; 230 __len_half = __len - __len2; 231 while (__pred(*__m1)) 232 { 233 if (++__m1 == __last) 234 goto __second_half_done; 235 --__len_half; 236 } 237 // TTTFFFFFTTTF?????T 238 // f ff m m1 l 239 __second_false = _VSTD::__stable_partition<_Predicate&>(__m1, __last, __pred, __len_half, __p, __bit); 240 __second_half_done: 241 // TTTFFFFFTTTTTFFFFF 242 // f ff m sf l 243 return _VSTD::rotate(__first_false, __m, __second_false); 244 // TTTTTTTTFFFFFFFFFF 245 // | 246 } 247 248 template <class _Predicate, class _BidirectionalIterator> 249 _BidirectionalIterator 250 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 251 bidirectional_iterator_tag) 252 { 253 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 254 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 255 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment 256 // Either prove all true and return __first or point to first false 257 while (true) 258 { 259 if (__first == __last) 260 return __first; 261 if (!__pred(*__first)) 262 break; 263 ++__first; 264 } 265 // __first points to first false, everything prior to __first is already set. 266 // Either prove [__first, __last) is all false and return __first, or point __last to last true 267 do 268 { 269 if (__first == --__last) 270 return __first; 271 } while (!__pred(*__last)); 272 // We now have a reduced range [__first, __last] 273 // *__first is known to be false 274 // *__last is known to be true 275 // __len >= 2 276 difference_type __len = _VSTD::distance(__first, __last) + 1; 277 pair<value_type*, ptrdiff_t> __p(0, 0); 278 unique_ptr<value_type, __return_temporary_buffer> __h; 279 if (__len >= __alloc_limit) 280 { 281 __p = _VSTD::get_temporary_buffer<value_type>(__len); 282 __h.reset(__p.first); 283 } 284 return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); 285 } 286 287 template <class _ForwardIterator, class _Predicate> 288 inline _LIBCPP_INLINE_VISIBILITY 289 _ForwardIterator 290 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 291 { 292 return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 293 } 294 295 _LIBCPP_END_NAMESPACE_STD 296 297 #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H 298