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