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