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