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