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_INPLACE_MERGE_H
10#define _LIBCPP___ALGORITHM_INPLACE_MERGE_H
11
12#include <__algorithm/comp.h>
13#include <__algorithm/comp_ref_type.h>
14#include <__algorithm/iterator_operations.h>
15#include <__algorithm/lower_bound.h>
16#include <__algorithm/min.h>
17#include <__algorithm/move.h>
18#include <__algorithm/rotate.h>
19#include <__algorithm/upper_bound.h>
20#include <__config>
21#include <__functional/identity.h>
22#include <__iterator/advance.h>
23#include <__iterator/distance.h>
24#include <__iterator/iterator_traits.h>
25#include <__iterator/reverse_iterator.h>
26#include <__memory/destruct_n.h>
27#include <__memory/temporary_buffer.h>
28#include <__memory/unique_ptr.h>
29#include <__utility/pair.h>
30#include <new>
31
32#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
33#  pragma GCC system_header
34#endif
35
36_LIBCPP_PUSH_MACROS
37#include <__undef_macros>
38
39_LIBCPP_BEGIN_NAMESPACE_STD
40
41template <class _Predicate>
42class __invert // invert the sense of a comparison
43{
44private:
45    _Predicate __p_;
46public:
47    _LIBCPP_INLINE_VISIBILITY __invert() {}
48
49    _LIBCPP_INLINE_VISIBILITY
50    explicit __invert(_Predicate __p) : __p_(__p) {}
51
52    template <class _T1>
53    _LIBCPP_INLINE_VISIBILITY
54    bool operator()(const _T1& __x) {return !__p_(__x);}
55
56    template <class _T1, class _T2>
57    _LIBCPP_INLINE_VISIBILITY
58    bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
59};
60
61template <class _AlgPolicy, class _Compare, class _InputIterator1, class _Sent1,
62          class _InputIterator2, class _Sent2, class _OutputIterator>
63_LIBCPP_HIDE_FROM_ABI
64void __half_inplace_merge(_InputIterator1 __first1, _Sent1 __last1,
65                          _InputIterator2 __first2, _Sent2 __last2,
66                          _OutputIterator __result, _Compare&& __comp)
67{
68    for (; __first1 != __last1; ++__result)
69    {
70        if (__first2 == __last2)
71        {
72            std::__move<_AlgPolicy>(__first1, __last1, __result);
73            return;
74        }
75
76        if (__comp(*__first2, *__first1))
77        {
78            *__result = _IterOps<_AlgPolicy>::__iter_move(__first2);
79            ++__first2;
80        }
81        else
82        {
83            *__result = _IterOps<_AlgPolicy>::__iter_move(__first1);
84            ++__first1;
85        }
86    }
87    // __first2 through __last2 are already in the right spot.
88}
89
90template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
91_LIBCPP_HIDE_FROM_ABI
92void __buffered_inplace_merge(
93    _BidirectionalIterator __first,
94    _BidirectionalIterator __middle,
95    _BidirectionalIterator __last,
96    _Compare&& __comp,
97    typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
98    typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
99    typename iterator_traits<_BidirectionalIterator>::value_type* __buff) {
100  typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
101    __destruct_n __d(0);
102    unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
103    if (__len1 <= __len2)
104    {
105        value_type* __p = __buff;
106        for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
107            ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
108        std::__half_inplace_merge<_AlgPolicy>(__buff, __p, __middle, __last, __first, __comp);
109    }
110    else
111    {
112        value_type* __p = __buff;
113        for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
114            ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
115        typedef __unconstrained_reverse_iterator<_BidirectionalIterator> _RBi;
116        typedef __unconstrained_reverse_iterator<value_type*> _Rv;
117        typedef __invert<_Compare> _Inverted;
118        std::__half_inplace_merge<_AlgPolicy>(_Rv(__p), _Rv(__buff),
119                                    _RBi(__middle), _RBi(__first),
120                                    _RBi(__last), _Inverted(__comp));
121    }
122}
123
124template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
125void __inplace_merge(
126    _BidirectionalIterator __first,
127    _BidirectionalIterator __middle,
128    _BidirectionalIterator __last,
129    _Compare&& __comp,
130    typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
131    typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
132    typename iterator_traits<_BidirectionalIterator>::value_type* __buff,
133    ptrdiff_t __buff_size) {
134    using _Ops = _IterOps<_AlgPolicy>;
135
136    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
137    while (true)
138    {
139        // if __middle == __last, we're done
140        if (__len2 == 0)
141            return;
142        if (__len1 <= __buff_size || __len2 <= __buff_size)
143            return std::__buffered_inplace_merge<_AlgPolicy>
144                   (__first, __middle, __last, __comp, __len1, __len2, __buff);
145        // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
146        for (; true; ++__first, (void) --__len1)
147        {
148            if (__len1 == 0)
149                return;
150            if (__comp(*__middle, *__first))
151                break;
152        }
153        // __first < __middle < __last
154        // *__first > *__middle
155        // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
156        //     all elements in:
157        //         [__first, __m1)  <= [__middle, __m2)
158        //         [__middle, __m2) <  [__m1, __middle)
159        //         [__m1, __middle) <= [__m2, __last)
160        //     and __m1 or __m2 is in the middle of its range
161        _BidirectionalIterator __m1;  // "median" of [__first, __middle)
162        _BidirectionalIterator __m2;  // "median" of [__middle, __last)
163        difference_type __len11;      // distance(__first, __m1)
164        difference_type __len21;      // distance(__middle, __m2)
165        // binary search smaller range
166        if (__len1 < __len2)
167        {   // __len >= 1, __len2 >= 2
168            __len21 = __len2 / 2;
169            __m2 = __middle;
170            _Ops::advance(__m2, __len21);
171            __m1 = std::__upper_bound<_AlgPolicy>(__first, __middle, *__m2, __comp, std::__identity());
172            __len11 = _Ops::distance(__first, __m1);
173        }
174        else
175        {
176            if (__len1 == 1)
177            {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
178                // It is known *__first > *__middle
179              _Ops::iter_swap(__first, __middle);
180                return;
181            }
182            // __len1 >= 2, __len2 >= 1
183            __len11 = __len1 / 2;
184            __m1 = __first;
185            _Ops::advance(__m1, __len11);
186            __m2 = std::lower_bound(__middle, __last, *__m1, __comp);
187            __len21 = _Ops::distance(__middle, __m2);
188        }
189        difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
190        difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
191        // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
192        // swap middle two partitions
193        __middle = std::__rotate<_AlgPolicy>(__m1, __middle, __m2).first;
194        // __len12 and __len21 now have swapped meanings
195        // merge smaller range with recursive call and larger with tail recursion elimination
196        if (__len11 + __len21 < __len12 + __len22)
197        {
198            std::__inplace_merge<_AlgPolicy>(
199                __first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
200            __first = __middle;
201            __middle = __m2;
202            __len1 = __len12;
203            __len2 = __len22;
204        }
205        else
206        {
207            std::__inplace_merge<_AlgPolicy>(
208                __middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
209            __last = __middle;
210            __middle = __m1;
211            __len1 = __len11;
212            __len2 = __len21;
213        }
214    }
215}
216
217template <class _AlgPolicy, class _BidirectionalIterator, class _Compare>
218_LIBCPP_HIDE_FROM_ABI
219void
220__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
221              _Compare&& __comp)
222{
223    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
224    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
225    difference_type __len1 = _IterOps<_AlgPolicy>::distance(__first, __middle);
226    difference_type __len2 = _IterOps<_AlgPolicy>::distance(__middle, __last);
227    difference_type __buf_size = _VSTD::min(__len1, __len2);
228// TODO: Remove the use of std::get_temporary_buffer
229_LIBCPP_SUPPRESS_DEPRECATED_PUSH
230    pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
231_LIBCPP_SUPPRESS_DEPRECATED_POP
232    unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
233    return std::__inplace_merge<_AlgPolicy>(
234        std::move(__first), std::move(__middle), std::move(__last), __comp, __len1, __len2, __buf.first, __buf.second);
235}
236
237template <class _BidirectionalIterator, class _Compare>
238inline _LIBCPP_HIDE_FROM_ABI void inplace_merge(
239    _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) {
240  std::__inplace_merge<_ClassicAlgPolicy>(
241      std::move(__first), std::move(__middle), std::move(__last), static_cast<__comp_ref_type<_Compare> >(__comp));
242}
243
244template <class _BidirectionalIterator>
245inline _LIBCPP_HIDE_FROM_ABI
246void
247inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
248{
249    std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last),
250                        __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
251}
252
253_LIBCPP_END_NAMESPACE_STD
254
255_LIBCPP_POP_MACROS
256
257#endif // _LIBCPP___ALGORITHM_INPLACE_MERGE_H
258