244 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_INPLACE_MERGE_H10#define _LIBCPP___ALGORITHM_INPLACE_MERGE_H11 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 <__cstddef/ptrdiff_t.h>22#include <__functional/identity.h>23#include <__iterator/iterator_traits.h>24#include <__iterator/reverse_iterator.h>25#include <__memory/construct_at.h>26#include <__memory/destruct_n.h>27#include <__memory/unique_ptr.h>28#include <__memory/unique_temporary_buffer.h>29#include <__utility/move.h>30#include <__utility/pair.h>31 32#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)33# pragma GCC system_header34#endif35 36_LIBCPP_PUSH_MACROS37#include <__undef_macros>38 39_LIBCPP_BEGIN_NAMESPACE_STD40 41template <class _Predicate>42class __invert // invert the sense of a comparison43{44private:45 _Predicate __p_;46 47public:48 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __invert() {}49 50 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit __invert(_Predicate __p) : __p_(__p) {}51 52 template <class _T1>53 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator()(const _T1& __x) {54 return !__p_(__x);55 }56 57 template <class _T1, class _T2>58 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator()(const _T1& __x, const _T2& __y) {59 return __p_(__y, __x);60 }61};62 63template <class _AlgPolicy,64 class _Compare,65 class _InputIterator1,66 class _Sent1,67 class _InputIterator2,68 class _Sent2,69 class _OutputIterator>70_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __half_inplace_merge(71 _InputIterator1 __first1,72 _Sent1 __last1,73 _InputIterator2 __first2,74 _Sent2 __last2,75 _OutputIterator __result,76 _Compare&& __comp) {77 for (; __first1 != __last1; ++__result) {78 if (__first2 == __last2) {79 std::__move<_AlgPolicy>(__first1, __last1, __result);80 return;81 }82 83 if (__comp(*__first2, *__first1)) {84 *__result = _IterOps<_AlgPolicy>::__iter_move(__first2);85 ++__first2;86 } else {87 *__result = _IterOps<_AlgPolicy>::__iter_move(__first1);88 ++__first1;89 }90 }91 // __first2 through __last2 are already in the right spot.92}93 94template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>95_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __buffered_inplace_merge(96 _BidirectionalIterator __first,97 _BidirectionalIterator __middle,98 _BidirectionalIterator __last,99 _Compare&& __comp,100 typename iterator_traits<_BidirectionalIterator>::difference_type __len1,101 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,102 typename iterator_traits<_BidirectionalIterator>::value_type* __buff) {103 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;104 __destruct_n __d(0);105 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);106 if (__len1 <= __len2) {107 value_type* __p = __buff;108 for (_BidirectionalIterator __i = __first; __i != __middle;109 __d.template __incr<value_type>(), (void)++__i, (void)++__p)110 std::__construct_at(__p, _IterOps<_AlgPolicy>::__iter_move(__i));111 std::__half_inplace_merge<_AlgPolicy>(__buff, __p, __middle, __last, __first, __comp);112 } else {113 value_type* __p = __buff;114 for (_BidirectionalIterator __i = __middle; __i != __last;115 __d.template __incr<value_type>(), (void)++__i, (void)++__p)116 std::__construct_at(__p, _IterOps<_AlgPolicy>::__iter_move(__i));117 typedef reverse_iterator<_BidirectionalIterator> _RBi;118 typedef reverse_iterator<value_type*> _Rv;119 typedef __invert<_Compare> _Inverted;120 std::__half_inplace_merge<_AlgPolicy>(121 _Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), _RBi(__last), _Inverted(__comp));122 }123}124 125template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>126_LIBCPP_CONSTEXPR_SINCE_CXX26 void __inplace_merge(127 _BidirectionalIterator __first,128 _BidirectionalIterator __middle,129 _BidirectionalIterator __last,130 _Compare&& __comp,131 typename iterator_traits<_BidirectionalIterator>::difference_type __len1,132 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,133 typename iterator_traits<_BidirectionalIterator>::value_type* __buff,134 ptrdiff_t __buff_size) {135 using _Ops = _IterOps<_AlgPolicy>;136 137 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;138 while (true) {139 // if __middle == __last, we're done140 if (__len2 == 0)141 return;142 if (__len1 <= __buff_size || __len2 <= __buff_size)143 return std::__buffered_inplace_merge<_AlgPolicy>(__first, __middle, __last, __comp, __len1, __len2, __buff);144 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0145 for (; true; ++__first, (void)--__len1) {146 if (__len1 == 0)147 return;148 if (__comp(*__middle, *__first))149 break;150 }151 // __first < __middle < __last152 // *__first > *__middle153 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that154 // all elements in:155 // [__first, __m1) <= [__middle, __m2)156 // [__middle, __m2) < [__m1, __middle)157 // [__m1, __middle) <= [__m2, __last)158 // and __m1 or __m2 is in the middle of its range159 _BidirectionalIterator __m1; // "median" of [__first, __middle)160 _BidirectionalIterator __m2; // "median" of [__middle, __last)161 difference_type __len11; // distance(__first, __m1)162 difference_type __len21; // distance(__middle, __m2)163 // binary search smaller range164 if (__len1 < __len2) { // __len >= 1, __len2 >= 2165 __len21 = __len2 / 2;166 __m2 = __middle;167 _Ops::advance(__m2, __len21);168 __m1 = std::__upper_bound<_AlgPolicy>(__first, __middle, *__m2, __comp, std::__identity());169 __len11 = _Ops::distance(__first, __m1);170 } else {171 if (__len1 == 1) { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1172 // It is known *__first > *__middle173 _Ops::iter_swap(__first, __middle);174 return;175 }176 // __len1 >= 2, __len2 >= 1177 __len11 = __len1 / 2;178 __m1 = __first;179 _Ops::advance(__m1, __len11);180 __m2 = std::lower_bound(__middle, __last, *__m1, __comp);181 __len21 = _Ops::distance(__middle, __m2);182 }183 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)184 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)185 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)186 // swap middle two partitions187 __middle = std::__rotate<_AlgPolicy>(__m1, __middle, __m2).first;188 // __len12 and __len21 now have swapped meanings189 // merge smaller range with recursive call and larger with tail recursion elimination190 if (__len11 + __len21 < __len12 + __len22) {191 std::__inplace_merge<_AlgPolicy>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);192 __first = __middle;193 __middle = __m2;194 __len1 = __len12;195 __len2 = __len22;196 } else {197 std::__inplace_merge<_AlgPolicy>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);198 __last = __middle;199 __middle = __m1;200 __len1 = __len11;201 __len2 = __len21;202 }203 }204}205 206template <class _AlgPolicy, class _BidirectionalIterator, class _Compare>207_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __inplace_merge(208 _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare&& __comp) {209 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;210 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;211 difference_type __len1 = _IterOps<_AlgPolicy>::distance(__first, __middle);212 difference_type __len2 = _IterOps<_AlgPolicy>::distance(__middle, __last);213 difference_type __buf_size = std::min(__len1, __len2);214 __unique_temporary_buffer<value_type> __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__buf_size);215 return std::__inplace_merge<_AlgPolicy>(216 std::move(__first),217 std::move(__middle),218 std::move(__last),219 __comp,220 __len1,221 __len2,222 __unique_buf.get(),223 __unique_buf.get_deleter().__count_);224}225 226template <class _BidirectionalIterator, class _Compare>227inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void inplace_merge(228 _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) {229 std::__inplace_merge<_ClassicAlgPolicy>(230 std::move(__first), std::move(__middle), std::move(__last), static_cast<__comp_ref_type<_Compare> >(__comp));231}232 233template <class _BidirectionalIterator>234inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void235inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) {236 std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), __less<>());237}238 239_LIBCPP_END_NAMESPACE_STD240 241_LIBCPP_POP_MACROS242 243#endif // _LIBCPP___ALGORITHM_INPLACE_MERGE_H244