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 <__cstddef/ptrdiff_t.h>
16#include <__iterator/advance.h>
17#include <__iterator/distance.h>
18#include <__iterator/iterator_traits.h>
19#include <__memory/construct_at.h>
20#include <__memory/destruct_n.h>
21#include <__memory/unique_ptr.h>
22#include <__memory/unique_temporary_buffer.h>
23#include <__type_traits/remove_cvref.h>
24#include <__utility/move.h>
25#include <__utility/pair.h>
26
27#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
28# pragma GCC system_header
29#endif
30
31_LIBCPP_PUSH_MACROS
32#include <__undef_macros>
33
34_LIBCPP_BEGIN_NAMESPACE_STD
35
36template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
37_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator __stable_partition_impl(
38 _ForwardIterator __first,
39 _ForwardIterator __last,
40 _Predicate __pred,
41 _Distance __len,
42 _Pair __p,
43 forward_iterator_tag __fit) {
44 using _Ops = _IterOps<_AlgPolicy>;
45
46 // *__first is known to be false
47 // __len >= 1
48 if (__len == 1)
49 return __first;
50 if (__len == 2) {
51 _ForwardIterator __m = __first;
52 if (__pred(*++__m)) {
53 _Ops::iter_swap(__first, __m);
54 return __m;
55 }
56 return __first;
57 }
58 if (__len <= __p.second) { // The buffer is big enough to use
59 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
60 __destruct_n __d(0);
61 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
62 // Move the falses into the temporary buffer, and the trues to the front of the line
63 // Update __first to always point to the end of the trues
64 value_type* __t = __p.first;
65 std::__construct_at(__t, _Ops::__iter_move(__first));
66 __d.template __incr<value_type>();
67 ++__t;
68 _ForwardIterator __i = __first;
69 while (++__i != __last) {
70 if (__pred(*__i)) {
71 *__first = _Ops::__iter_move(__i);
72 ++__first;
73 } else {
74 std::__construct_at(__t, _Ops::__iter_move(__i));
75 __d.template __incr<value_type>();
76 ++__t;
77 }
78 }
79 // All trues now at start of range, all falses in buffer
80 // Move falses back into range, but don't mess up __first which points to first false
81 __i = __first;
82 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
83 *__i = _Ops::__iter_move(__t2);
84 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
85 return __first;
86 }
87 // Else not enough buffer, do in place
88 // __len >= 3
89 _ForwardIterator __m = __first;
90 _Distance __len2 = __len / 2; // __len2 >= 2
91 _Ops::advance(__m, __len2);
92 // recurse on [__first, __m), *__first know to be false
93 // F?????????????????
94 // f m l
95 _ForwardIterator __first_false =
96 std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);
97 // TTTFFFFF??????????
98 // f ff m l
99 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
100 _ForwardIterator __m1 = __m;
101 _ForwardIterator __second_false = __last;
102 _Distance __len_half = __len - __len2;
103 while (__pred(*__m1)) {
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&>(__m1, __last, __pred, __len_half, __p, __fit);
111__second_half_done:
112 // TTTFFFFFTTTTTFFFFF
113 // f ff m sf l
114 return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
115 // TTTTTTTTFFFFFFFFFF
116 // |
117}
118
119template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
120_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
121__stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) {
122 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
123 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
124
125 const difference_type __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 if (__first == __last)
129 return __first;
130 if (!__pred(*__first))
131 break;
132 ++__first;
133 }
134 // We now have a reduced range [__first, __last)
135 // *__first is known to be false
136 difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
137 __unique_temporary_buffer<value_type> __unique_buf;
138 pair<value_type*, ptrdiff_t> __p(0, 0);
139 if (__len >= __alloc_limit) {
140 __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
141 __p.first = __unique_buf.get();
142 __p.second = __unique_buf.get_deleter().__count_;
143 }
144 return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
145 std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag());
146}
147
148template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
149_LIBCPP_CONSTEXPR_SINCE_CXX26 _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 std::__construct_at(__t, _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 std::__construct_at(__t, _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
250template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>
251_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _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 __unique_temporary_buffer<value_type> __unique_buf;
276 pair<value_type*, ptrdiff_t> __p(0, 0);
277 if (__len >= __alloc_limit) {
278 __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
279 __p.first = __unique_buf.get();
280 __p.second = __unique_buf.get_deleter().__count_;
281 }
282 return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
283 std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
284}
285
286template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>
287_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator __stable_partition(
288 _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) {
289 return std::__stable_partition_impl<_AlgPolicy, __remove_cvref_t<_Predicate>&>(
290 std::move(__first), std::move(__last), __pred, __iter_category);
291}
292
293template <class _ForwardIterator, class _Predicate>
294_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
295stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
296 using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
297 return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>(
298 std::move(__first), std::move(__last), __pred, _IterCategory());
299}
300
301_LIBCPP_END_NAMESPACE_STD
302
303_LIBCPP_POP_MACROS
304
305#endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H
306