xref: /freebsd/contrib/llvm-project/libcxx/include/__algorithm/stable_partition.h (revision 4d3fc8b0570b29fb0d6ee9525f104d52176ff0d4)
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
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
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
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
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
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
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