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