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 <__cstddef/ptrdiff_t.h>
  16 #include <__iterator/advance.h>
  17 #include <__iterator/distance.h>
  18 #include <__iterator/iterator_traits.h>
  19 #include <__memory/destruct_n.h>
  20 #include <__memory/unique_ptr.h>
  21 #include <__memory/unique_temporary_buffer.h>
  22 #include <__type_traits/remove_cvref.h>
  23 #include <__utility/move.h>
  24 #include <__utility/pair.h>
  25 #include <new>
  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 _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
  37 _LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition_impl(
  38     _ForwardIterator __first,
  39     _ForwardIterator __last,
  40     _Predicate __pred,
  41     _Distance __len,
  42     _Pair __p,
  43     forward_iterator_tag __fit) {
  44   using _Ops = _IterOps<_AlgPolicy>;
  45
  46   // *__first is known to be false
  47   // __len >= 1
  48   if (__len == 1)
  49     return __first;
  50   if (__len == 2) {
  51     _ForwardIterator __m = __first;
  52     if (__pred(*++__m)) {
  53       _Ops::iter_swap(__first, __m);
  54       return __m;
  55     }
  56     return __first;
  57   }
  58   if (__len <= __p.second) { // The buffer is big enough to use
  59     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
  60     __destruct_n __d(0);
  61     unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
  62     // Move the falses into the temporary buffer, and the trues to the front of the line
  63     // Update __first to always point to the end of the trues
  64     value_type* __t = __p.first;
  65     ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
  66     __d.template __incr<value_type>();
  67     ++__t;
  68     _ForwardIterator __i = __first;
  69     while (++__i != __last) {
  70       if (__pred(*__i)) {
  71         *__first = _Ops::__iter_move(__i);
  72         ++__first;
  73       } else {
  74         ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
  75         __d.template __incr<value_type>();
  76         ++__t;
  77       }
  78     }
  79     // All trues now at start of range, all falses in buffer
  80     // Move falses back into range, but don't mess up __first which points to first false
  81     __i = __first;
  82     for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
  83       *__i = _Ops::__iter_move(__t2);
  84     // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
  85     return __first;
  86   }
  87   // Else not enough buffer, do in place
  88   // __len >= 3
  89   _ForwardIterator __m = __first;
  90   _Distance __len2     = __len / 2; // __len2 >= 2
  91   _Ops::advance(__m, __len2);
  92   // recurse on [__first, __m), *__first know to be false
  93   // F?????????????????
  94   // f       m         l
  95   _ForwardIterator __first_false =
  96       std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);
  97   // TTTFFFFF??????????
  98   // f  ff   m         l
  99   // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
 100   _ForwardIterator __m1           = __m;
 101   _ForwardIterator __second_false = __last;
 102   _Distance __len_half            = __len - __len2;
 103   while (__pred(*__m1)) {
 104     if (++__m1 == __last)
 105       goto __second_half_done;
 106     --__len_half;
 107   }
 108   // TTTFFFFFTTTF??????
 109   // f  ff   m  m1     l
 110   __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);
 111 __second_half_done:
 112   // TTTFFFFFTTTTTFFFFF
 113   // f  ff   m    sf   l
 114   return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
 115   // TTTTTTTTFFFFFFFFFF
 116   //         |
 117 }
 118
 119 template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
 120 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 121 __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) {
 122   typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
 123   typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
 124
 125   const difference_type __alloc_limit = 3; // might want to make this a function of trivial assignment
 126   // Either prove all true and return __first or point to first false
 127   while (true) {
 128     if (__first == __last)
 129       return __first;
 130     if (!__pred(*__first))
 131       break;
 132     ++__first;
 133   }
 134   // We now have a reduced range [__first, __last)
 135   // *__first is known to be false
 136   difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
 137   __unique_temporary_buffer<value_type> __unique_buf;
 138   pair<value_type*, ptrdiff_t> __p(0, 0);
 139   if (__len >= __alloc_limit) {
 140     __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
 141     __p.first    = __unique_buf.get();
 142     __p.second   = __unique_buf.get_deleter().__count_;
 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   __unique_temporary_buffer<value_type> __unique_buf;
 276   pair<value_type*, ptrdiff_t> __p(0, 0);
 277   if (__len >= __alloc_limit) {
 278     __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
 279     __p.first    = __unique_buf.get();
 280     __p.second   = __unique_buf.get_deleter().__count_;
 281   }
 282   return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
 283       std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
 284 }
 285
 286 template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>
 287 _LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition(
 288     _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) {
 289   return std::__stable_partition_impl<_AlgPolicy, __remove_cvref_t<_Predicate>&>(
 290       std::move(__first), std::move(__last), __pred, __iter_category);
 291 }
 292
 293 template <class _ForwardIterator, class _Predicate>
 294 inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 295 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
 296   using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
 297   return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>(
 298       std::move(__first), std::move(__last), __pred, _IterCategory());
 299 }
 300
 301 _LIBCPP_END_NAMESPACE_STD
 302
 303 _LIBCPP_POP_MACROS
 304
 305 #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H