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