306 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_STABLE_PARTITION_H10#define _LIBCPP___ALGORITHM_STABLE_PARTITION_H11 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/construct_at.h>20#include <__memory/destruct_n.h>21#include <__memory/unique_ptr.h>22#include <__memory/unique_temporary_buffer.h>23#include <__type_traits/remove_cvref.h>24#include <__utility/move.h>25#include <__utility/pair.h>26 27#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)28# pragma GCC system_header29#endif30 31_LIBCPP_PUSH_MACROS32#include <__undef_macros>33 34_LIBCPP_BEGIN_NAMESPACE_STD35 36template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>37_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _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 false47 // __len >= 148 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 use59 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 line63 // Update __first to always point to the end of the trues64 value_type* __t = __p.first;65 std::__construct_at(__t, _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 std::__construct_at(__t, _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 buffer80 // Move falses back into range, but don't mess up __first which points to first false81 __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 buffer85 return __first;86 }87 // Else not enough buffer, do in place88 // __len >= 389 _ForwardIterator __m = __first;90 _Distance __len2 = __len / 2; // __len2 >= 291 _Ops::advance(__m, __len2);92 // recurse on [__first, __m), *__first know to be false93 // F?????????????????94 // f m l95 _ForwardIterator __first_false =96 std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);97 // TTTFFFFF??????????98 // f ff m l99 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true100 _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 l110 __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);111__second_half_done:112 // TTTFFFFFTTTTTFFFFF113 // f ff m sf l114 return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;115 // TTTTTTTTFFFFFFFFFF116 // |117}118 119template <class _AlgPolicy, class _Predicate, class _ForwardIterator>120_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator121__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 assignment126 // Either prove all true and return __first or point to first false127 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 false136 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 148template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>149_LIBCPP_CONSTEXPR_SINCE_CXX26 _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 false159 // *__last is known to be true160 // __len >= 2161 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 use177 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 line181 // Update __first to always point to the end of the trues182 value_type* __t = __p.first;183 std::__construct_at(__t, _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 std::__construct_at(__t, _Ops::__iter_move(__i));193 __d.template __incr<value_type>();194 ++__t;195 }196 }197 // move *__last, known to be true198 *__first = _Ops::__iter_move(__i);199 __i = ++__first;200 // All trues now at start of range, all falses in buffer201 // Move falses back into range, but don't mess up __first which points to first false202 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 buffer205 return __first;206 }207 // Else not enough buffer, do in place208 // __len >= 4209 _BidirectionalIterator __m = __first;210 _Distance __len2 = __len / 2; // __len2 >= 2211 _Ops::advance(__m, __len2);212 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false213 // F????????????????T214 // f m l215 _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?????????T224 // f m1 m l225 __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m1, __pred, __len_half, __p, __bit);226__first_half_done:227 // TTTFFFFF?????????T228 // f ff m l229 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true230 __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?????T240 // f ff m m1 l241 __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __bit);242__second_half_done:243 // TTTFFFFFTTTTTFFFFF244 // f ff m sf l245 return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;246 // TTTTTTTTFFFFFFFFFF247 // |248}249 250template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>251_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _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 assignment256 // Either prove all true and return __first or point to first false257 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 true266 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 false272 // *__last is known to be true273 // __len >= 2274 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 286template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>287_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _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 293template <class _ForwardIterator, class _Predicate>294_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator295stable_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_STD302 303_LIBCPP_POP_MACROS304 305#endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H306