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