libcxx/include/__algorithm/stable_partition.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_STABLE_PARTITION_H
  10 #define _LIBCPP___ALGORITHM_STABLE_PARTITION_H
  11
  12 #include <__algorithm/iterator_operations.h>
  13 #include <__algorithm/rotate.h>
  14 #include <__config>
  15 #include <__iterator/advance.h>
  16 #include <__iterator/distance.h>
  17 #include <__iterator/iterator_traits.h>
  18 #include <__memory/destruct_n.h>
  19 #include <__memory/temporary_buffer.h>
  20 #include <__memory/unique_ptr.h>
  21 #include <__utility/move.h>
  22 #include <__utility/pair.h>
  23 #include <new>
  24
  25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  26 #  pragma GCC system_header
  27 #endif
  28
  29 _LIBCPP_PUSH_MACROS
  30 #include <__undef_macros>
  31
  32 _LIBCPP_BEGIN_NAMESPACE_STD
  33
  34 template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
  35 _LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition_impl(
  36     _ForwardIterator __first,
  37     _ForwardIterator __last,
  38     _Predicate __pred,
  39     _Distance __len,
  40     _Pair __p,
  41     forward_iterator_tag __fit) {
  42   using _Ops = _IterOps<_AlgPolicy>;
  43
  44   // *__first is known to be false
  45   // __len >= 1
  46   if (__len == 1)
  47     return __first;
  48   if (__len == 2) {
  49     _ForwardIterator __m = __first;
  50     if (__pred(*++__m)) {
  51       _Ops::iter_swap(__first, __m);
  52       return __m;
  53     }
  54     return __first;
  55   }
  56   if (__len <= __p.second) { // The buffer is big enough to use
  57     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
  58     __destruct_n __d(0);
  59     unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
  60     // Move the falses into the temporary buffer, and the trues to the front of the line
  61     // Update __first to always point to the end of the trues
  62     value_type* __t = __p.first;
  63     ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
  64     __d.template __incr<value_type>();
  65     ++__t;
  66     _ForwardIterator __i = __first;
  67     while (++__i != __last) {
  68       if (__pred(*__i)) {
  69         *__first = _Ops::__iter_move(__i);
  70         ++__first;
  71       } else {
  72         ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
  73         __d.template __incr<value_type>();
  74         ++__t;
  75       }
  76     }
  77     // All trues now at start of range, all falses in buffer
  78     // Move falses back into range, but don't mess up __first which points to first false
  79     __i = __first;
  80     for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
  81       *__i = _Ops::__iter_move(__t2);
  82     // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
  83     return __first;
  84   }
  85   // Else not enough buffer, do in place
  86   // __len >= 3
  87   _ForwardIterator __m = __first;
  88   _Distance __len2     = __len / 2; // __len2 >= 2
  89   _Ops::advance(__m, __len2);
  90   // recurse on [__first, __m), *__first know to be false
  91   // F?????????????????
  92   // f       m         l
  93   _ForwardIterator __first_false =
  94       std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);
  95   // TTTFFFFF??????????
  96   // f  ff   m         l
  97   // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
  98   _ForwardIterator __m1           = __m;
  99   _ForwardIterator __second_false = __last;
 100   _Distance __len_half            = __len - __len2;
 101   while (__pred(*__m1)) {
 102     if (++__m1 == __last)
 103       goto __second_half_done;
 104     --__len_half;
 105   }
 106   // TTTFFFFFTTTF??????
 107   // f  ff   m  m1     l
 108   __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);
 109 __second_half_done:
 110   // TTTFFFFFTTTTTFFFFF
 111   // f  ff   m    sf   l
 112   return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
 113   // TTTTTTTTFFFFFFFFFF
 114   //         |
 115 }
 116
 117 template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
 118 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 119 __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) {
 120   typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
 121   typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
 122
 123   const difference_type __alloc_limit = 3; // might want to make this a function of trivial assignment
 124   // Either prove all true and return __first or point to first false
 125   while (true) {
 126     if (__first == __last)
 127       return __first;
 128     if (!__pred(*__first))
 129       break;
 130     ++__first;
 131   }
 132   // We now have a reduced range [__first, __last)
 133   // *__first is known to be false
 134   difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
 135   pair<value_type*, ptrdiff_t> __p(0, 0);
 136   unique_ptr<value_type, __return_temporary_buffer> __h;
 137   if (__len >= __alloc_limit) {
 138     // TODO: Remove the use of std::get_temporary_buffer
 139     _LIBCPP_SUPPRESS_DEPRECATED_PUSH
 140     __p = std::get_temporary_buffer<value_type>(__len);
 141     _LIBCPP_SUPPRESS_DEPRECATED_POP
 142     __h.reset(__p.first);
 143   }
 144   return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
 145       std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag());
 146 }
 147
 148 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
 149 _BidirectionalIterator __stable_partition_impl(
 150     _BidirectionalIterator __first,
 151     _BidirectionalIterator __last,
 152     _Predicate __pred,
 153     _Distance __len,
 154     _Pair __p,
 155     bidirectional_iterator_tag __bit) {
 156   using _Ops = _IterOps<_AlgPolicy>;
 157
 158   // *__first is known to be false
 159   // *__last is known to be true
 160   // __len >= 2
 161   if (__len == 2) {
 162     _Ops::iter_swap(__first, __last);
 163     return __last;
 164   }
 165   if (__len == 3) {
 166     _BidirectionalIterator __m = __first;
 167     if (__pred(*++__m)) {
 168       _Ops::iter_swap(__first, __m);
 169       _Ops::iter_swap(__m, __last);
 170       return __last;
 171     }
 172     _Ops::iter_swap(__m, __last);
 173     _Ops::iter_swap(__first, __m);
 174     return __m;
 175   }
 176   if (__len <= __p.second) { // The buffer is big enough to use
 177     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
 178     __destruct_n __d(0);
 179     unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
 180     // Move the falses into the temporary buffer, and the trues to the front of the line
 181     // Update __first to always point to the end of the trues
 182     value_type* __t = __p.first;
 183     ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
 184     __d.template __incr<value_type>();
 185     ++__t;
 186     _BidirectionalIterator __i = __first;
 187     while (++__i != __last) {
 188       if (__pred(*__i)) {
 189         *__first = _Ops::__iter_move(__i);
 190         ++__first;
 191       } else {
 192         ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
 193         __d.template __incr<value_type>();
 194         ++__t;
 195       }
 196     }
 197     // move *__last, known to be true
 198     *__first = _Ops::__iter_move(__i);
 199     __i      = ++__first;
 200     // All trues now at start of range, all falses in buffer
 201     // Move falses back into range, but don't mess up __first which points to first false
 202     for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
 203       *__i = _Ops::__iter_move(__t2);
 204     // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
 205     return __first;
 206   }
 207   // Else not enough buffer, do in place
 208   // __len >= 4
 209   _BidirectionalIterator __m = __first;
 210   _Distance __len2           = __len / 2; // __len2 >= 2
 211   _Ops::advance(__m, __len2);
 212   // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
 213   // F????????????????T
 214   // f       m        l
 215   _BidirectionalIterator __m1          = __m;
 216   _BidirectionalIterator __first_false = __first;
 217   _Distance __len_half                 = __len2;
 218   while (!__pred(*--__m1)) {
 219     if (__m1 == __first)
 220       goto __first_half_done;
 221     --__len_half;
 222   }
 223   // F???TFFF?????????T
 224   // f   m1  m        l
 225   __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m1, __pred, __len_half, __p, __bit);
 226 __first_half_done:
 227   // TTTFFFFF?????????T
 228   // f  ff   m        l
 229   // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
 230   __m1                                  = __m;
 231   _BidirectionalIterator __second_false = __last;
 232   ++__second_false;
 233   __len_half = __len - __len2;
 234   while (__pred(*__m1)) {
 235     if (++__m1 == __last)
 236       goto __second_half_done;
 237     --__len_half;
 238   }
 239   // TTTFFFFFTTTF?????T
 240   // f  ff   m  m1    l
 241   __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __bit);
 242 __second_half_done:
 243   // TTTFFFFFTTTTTFFFFF
 244   // f  ff   m    sf  l
 245   return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
 246   // TTTTTTTTFFFFFFFFFF
 247   //         |
 248 }
 249
 250 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>
 251 _LIBCPP_HIDE_FROM_ABI _BidirectionalIterator __stable_partition_impl(
 252     _BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag) {
 253   typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
 254   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
 255   const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
 256   // Either prove all true and return __first or point to first false
 257   while (true) {
 258     if (__first == __last)
 259       return __first;
 260     if (!__pred(*__first))
 261       break;
 262     ++__first;
 263   }
 264   // __first points to first false, everything prior to __first is already set.
 265   // Either prove [__first, __last) is all false and return __first, or point __last to last true
 266   do {
 267     if (__first == --__last)
 268       return __first;
 269   } while (!__pred(*__last));
 270   // We now have a reduced range [__first, __last]
 271   // *__first is known to be false
 272   // *__last is known to be true
 273   // __len >= 2
 274   difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1;
 275   pair<value_type*, ptrdiff_t> __p(0, 0);
 276   unique_ptr<value_type, __return_temporary_buffer> __h;
 277   if (__len >= __alloc_limit) {
 278     // TODO: Remove the use of std::get_temporary_buffer
 279     _LIBCPP_SUPPRESS_DEPRECATED_PUSH
 280     __p = std::get_temporary_buffer<value_type>(__len);
 281     _LIBCPP_SUPPRESS_DEPRECATED_POP
 282     __h.reset(__p.first);
 283   }
 284   return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
 285       std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
 286 }
 287
 288 template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>
 289 _LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition(
 290     _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) {
 291   return std::__stable_partition_impl<_AlgPolicy, __remove_cvref_t<_Predicate>&>(
 292       std::move(__first), std::move(__last), __pred, __iter_category);
 293 }
 294
 295 template <class _ForwardIterator, class _Predicate>
 296 inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 297 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
 298   using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
 299   return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>(
 300       std::move(__first), std::move(__last), __pred, _IterCategory());
 301 }
 302
 303 _LIBCPP_END_NAMESPACE_STD
 304
 305 _LIBCPP_POP_MACROS
 306
 307 #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H