libcxx/include/__algorithm/inplace_merge.h

   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
  41 template <class _Predicate>
  42 class __invert // invert the sense of a comparison
  43 {
  44 private:
  45     _Predicate __p_;
  46 public:
  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
  61 template <class _AlgPolicy, class _Compare, class _InputIterator1, class _Sent1,
  62           class _InputIterator2, class _Sent2, class _OutputIterator>
  63 _LIBCPP_HIDE_FROM_ABI
  64 void __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
  90 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
  91 _LIBCPP_HIDE_FROM_ABI
  92 void __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
 124 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 125 void __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
 217 template <class _AlgPolicy, class _BidirectionalIterator, class _Compare>
 218 _LIBCPP_HIDE_FROM_ABI
 219 void
 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
 237 template <class _BidirectionalIterator, class _Compare>
 238 inline _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
 244 template <class _BidirectionalIterator>
 245 inline _LIBCPP_HIDE_FROM_ABI
 246 void
 247 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
 248 {
 249     std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), __less<>());
 250 }
 251
 252 _LIBCPP_END_NAMESPACE_STD
 253
 254 _LIBCPP_POP_MACROS
 255
 256 #endif // _LIBCPP___ALGORITHM_INPLACE_MERGE_H