308 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___CXX03___ALGORITHM_STABLE_PARTITION_H10#define _LIBCPP___CXX03___ALGORITHM_STABLE_PARTITION_H11 12#include <__cxx03/__algorithm/iterator_operations.h>13#include <__cxx03/__algorithm/rotate.h>14#include <__cxx03/__config>15#include <__cxx03/__iterator/advance.h>16#include <__cxx03/__iterator/distance.h>17#include <__cxx03/__iterator/iterator_traits.h>18#include <__cxx03/__memory/destruct_n.h>19#include <__cxx03/__memory/temporary_buffer.h>20#include <__cxx03/__memory/unique_ptr.h>21#include <__cxx03/__utility/move.h>22#include <__cxx03/__utility/pair.h>23#include <__cxx03/new>24 25#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)26# pragma GCC system_header27#endif28 29_LIBCPP_PUSH_MACROS30#include <__cxx03/__undef_macros>31 32_LIBCPP_BEGIN_NAMESPACE_STD33 34template <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 false45 // __len >= 146 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 use57 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 line61 // Update __first to always point to the end of the trues62 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 buffer78 // Move falses back into range, but don't mess up __first which points to first false79 __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 buffer83 return __first;84 }85 // Else not enough buffer, do in place86 // __len >= 387 _ForwardIterator __m = __first;88 _Distance __len2 = __len / 2; // __len2 >= 289 _Ops::advance(__m, __len2);90 // recurse on [__first, __m), *__first know to be false91 // F?????????????????92 // f m l93 _ForwardIterator __first_false =94 std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);95 // TTTFFFFF??????????96 // f ff m l97 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true98 _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 l108 __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);109__second_half_done:110 // TTTFFFFFTTTTTFFFFF111 // f ff m sf l112 return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;113 // TTTTTTTTFFFFFFFFFF114 // |115}116 117template <class _AlgPolicy, class _Predicate, class _ForwardIterator>118_LIBCPP_HIDE_FROM_ABI _ForwardIterator119__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 assignment124 // Either prove all true and return __first or point to first false125 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 false134 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_buffer139 _LIBCPP_SUPPRESS_DEPRECATED_PUSH140 __p = std::get_temporary_buffer<value_type>(__len);141 _LIBCPP_SUPPRESS_DEPRECATED_POP142 __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 148template <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 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 ::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 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 _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 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_buffer279 _LIBCPP_SUPPRESS_DEPRECATED_PUSH280 __p = std::get_temporary_buffer<value_type>(__len);281 _LIBCPP_SUPPRESS_DEPRECATED_POP282 __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 288template <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 295template <class _ForwardIterator, class _Predicate>296inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator297stable_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_STD304 305_LIBCPP_POP_MACROS306 307#endif // _LIBCPP___CXX03___ALGORITHM_STABLE_PARTITION_H308