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