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