aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm-project/libcxx/include/__algorithm/stable_partition.h
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/libcxx/include/__algorithm/stable_partition.h')
-rw-r--r--contrib/llvm-project/libcxx/include/__algorithm/stable_partition.h487
1 files changed, 230 insertions, 257 deletions
diff --git a/contrib/llvm-project/libcxx/include/__algorithm/stable_partition.h b/contrib/llvm-project/libcxx/include/__algorithm/stable_partition.h
index 0e92a0a5f73d..8762abcf18e1 100644
--- a/contrib/llvm-project/libcxx/include/__algorithm/stable_partition.h
+++ b/contrib/llvm-project/libcxx/include/__algorithm/stable_partition.h
@@ -29,296 +29,269 @@
_LIBCPP_BEGIN_NAMESPACE_STD
template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
-_LIBCPP_HIDE_FROM_ABI _ForwardIterator
-__stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
- _Distance __len, _Pair __p, forward_iterator_tag __fit)
-{
- using _Ops = _IterOps<_AlgPolicy>;
+_LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition_impl(
+ _ForwardIterator __first,
+ _ForwardIterator __last,
+ _Predicate __pred,
+ _Distance __len,
+ _Pair __p,
+ forward_iterator_tag __fit) {
+ using _Ops = _IterOps<_AlgPolicy>;
- // *__first is known to be false
- // __len >= 1
- if (__len == 1)
- return __first;
- if (__len == 2)
- {
- _ForwardIterator __m = __first;
- if (__pred(*++__m))
- {
- _Ops::iter_swap(__first, __m);
- return __m;
- }
- return __first;
+ // *__first is known to be false
+ // __len >= 1
+ if (__len == 1)
+ return __first;
+ if (__len == 2) {
+ _ForwardIterator __m = __first;
+ if (__pred(*++__m)) {
+ _Ops::iter_swap(__first, __m);
+ return __m;
}
- if (__len <= __p.second)
- { // The buffer is big enough to use
- typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
- __destruct_n __d(0);
- unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
- // Move the falses into the temporary buffer, and the trues to the front of the line
- // Update __first to always point to the end of the trues
- value_type* __t = __p.first;
- ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
+ return __first;
+ }
+ if (__len <= __p.second) { // The buffer is big enough to use
+ typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
+ __destruct_n __d(0);
+ unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
+ // Move the falses into the temporary buffer, and the trues to the front of the line
+ // Update __first to always point to the end of the trues
+ value_type* __t = __p.first;
+ ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
+ __d.template __incr<value_type>();
+ ++__t;
+ _ForwardIterator __i = __first;
+ while (++__i != __last) {
+ if (__pred(*__i)) {
+ *__first = _Ops::__iter_move(__i);
+ ++__first;
+ } else {
+ ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
__d.template __incr<value_type>();
++__t;
- _ForwardIterator __i = __first;
- while (++__i != __last)
- {
- if (__pred(*__i))
- {
- *__first = _Ops::__iter_move(__i);
- ++__first;
- }
- else
- {
- ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
- __d.template __incr<value_type>();
- ++__t;
- }
- }
- // All trues now at start of range, all falses in buffer
- // Move falses back into range, but don't mess up __first which points to first false
- __i = __first;
- for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
- *__i = _Ops::__iter_move(__t2);
- // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
- return __first;
- }
- // Else not enough buffer, do in place
- // __len >= 3
- _ForwardIterator __m = __first;
- _Distance __len2 = __len / 2; // __len2 >= 2
- _Ops::advance(__m, __len2);
- // recurse on [__first, __m), *__first know to be false
- // F?????????????????
- // f m l
- _ForwardIterator __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
- __first, __m, __pred, __len2, __p, __fit);
- // TTTFFFFF??????????
- // f ff m l
- // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
- _ForwardIterator __m1 = __m;
- _ForwardIterator __second_false = __last;
- _Distance __len_half = __len - __len2;
- while (__pred(*__m1))
- {
- if (++__m1 == __last)
- goto __second_half_done;
- --__len_half;
+ }
}
- // TTTFFFFFTTTF??????
- // f ff m m1 l
- __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
- __m1, __last, __pred, __len_half, __p, __fit);
+ // All trues now at start of range, all falses in buffer
+ // Move falses back into range, but don't mess up __first which points to first false
+ __i = __first;
+ for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
+ *__i = _Ops::__iter_move(__t2);
+ // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
+ return __first;
+ }
+ // Else not enough buffer, do in place
+ // __len >= 3
+ _ForwardIterator __m = __first;
+ _Distance __len2 = __len / 2; // __len2 >= 2
+ _Ops::advance(__m, __len2);
+ // recurse on [__first, __m), *__first know to be false
+ // F?????????????????
+ // f m l
+ _ForwardIterator __first_false =
+ std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);
+ // TTTFFFFF??????????
+ // f ff m l
+ // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
+ _ForwardIterator __m1 = __m;
+ _ForwardIterator __second_false = __last;
+ _Distance __len_half = __len - __len2;
+ while (__pred(*__m1)) {
+ if (++__m1 == __last)
+ goto __second_half_done;
+ --__len_half;
+ }
+ // TTTFFFFFTTTF??????
+ // f ff m m1 l
+ __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);
__second_half_done:
- // TTTFFFFFTTTTTFFFFF
- // f ff m sf l
- return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
- // TTTTTTTTFFFFFFFFFF
- // |
+ // TTTFFFFFTTTTTFFFFF
+ // f ff m sf l
+ return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
+ // TTTTTTTTFFFFFFFFFF
+ // |
}
template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
_LIBCPP_HIDE_FROM_ABI _ForwardIterator
-__stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
- forward_iterator_tag)
-{
- typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
- typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
+__stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) {
+ typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
+ typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
- const difference_type __alloc_limit = 3; // might want to make this a function of trivial assignment
- // Either prove all true and return __first or point to first false
- while (true)
- {
- if (__first == __last)
- return __first;
- if (!__pred(*__first))
- break;
- ++__first;
- }
- // We now have a reduced range [__first, __last)
- // *__first is known to be false
- difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
- pair<value_type*, ptrdiff_t> __p(0, 0);
- unique_ptr<value_type, __return_temporary_buffer> __h;
- if (__len >= __alloc_limit)
- {
-// TODO: Remove the use of std::get_temporary_buffer
-_LIBCPP_SUPPRESS_DEPRECATED_PUSH
- __p = std::get_temporary_buffer<value_type>(__len);
-_LIBCPP_SUPPRESS_DEPRECATED_POP
- __h.reset(__p.first);
- }
- return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
- std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag());
+ const difference_type __alloc_limit = 3; // might want to make this a function of trivial assignment
+ // Either prove all true and return __first or point to first false
+ while (true) {
+ if (__first == __last)
+ return __first;
+ if (!__pred(*__first))
+ break;
+ ++__first;
+ }
+ // We now have a reduced range [__first, __last)
+ // *__first is known to be false
+ difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
+ pair<value_type*, ptrdiff_t> __p(0, 0);
+ unique_ptr<value_type, __return_temporary_buffer> __h;
+ if (__len >= __alloc_limit) {
+ // TODO: Remove the use of std::get_temporary_buffer
+ _LIBCPP_SUPPRESS_DEPRECATED_PUSH
+ __p = std::get_temporary_buffer<value_type>(__len);
+ _LIBCPP_SUPPRESS_DEPRECATED_POP
+ __h.reset(__p.first);
+ }
+ return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
+ std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag());
}
template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
-_BidirectionalIterator
-__stable_partition_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
- _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
-{
- using _Ops = _IterOps<_AlgPolicy>;
+_BidirectionalIterator __stable_partition_impl(
+ _BidirectionalIterator __first,
+ _BidirectionalIterator __last,
+ _Predicate __pred,
+ _Distance __len,
+ _Pair __p,
+ bidirectional_iterator_tag __bit) {
+ using _Ops = _IterOps<_AlgPolicy>;
- // *__first is known to be false
- // *__last is known to be true
- // __len >= 2
- if (__len == 2)
- {
- _Ops::iter_swap(__first, __last);
- return __last;
- }
- if (__len == 3)
- {
- _BidirectionalIterator __m = __first;
- if (__pred(*++__m))
- {
- _Ops::iter_swap(__first, __m);
- _Ops::iter_swap(__m, __last);
- return __last;
- }
- _Ops::iter_swap(__m, __last);
- _Ops::iter_swap(__first, __m);
- return __m;
+ // *__first is known to be false
+ // *__last is known to be true
+ // __len >= 2
+ if (__len == 2) {
+ _Ops::iter_swap(__first, __last);
+ return __last;
+ }
+ if (__len == 3) {
+ _BidirectionalIterator __m = __first;
+ if (__pred(*++__m)) {
+ _Ops::iter_swap(__first, __m);
+ _Ops::iter_swap(__m, __last);
+ return __last;
}
- if (__len <= __p.second)
- { // The buffer is big enough to use
- typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
- __destruct_n __d(0);
- unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
- // Move the falses into the temporary buffer, and the trues to the front of the line
- // Update __first to always point to the end of the trues
- value_type* __t = __p.first;
- ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
+ _Ops::iter_swap(__m, __last);
+ _Ops::iter_swap(__first, __m);
+ return __m;
+ }
+ if (__len <= __p.second) { // The buffer is big enough to use
+ typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+ __destruct_n __d(0);
+ unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
+ // Move the falses into the temporary buffer, and the trues to the front of the line
+ // Update __first to always point to the end of the trues
+ value_type* __t = __p.first;
+ ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
+ __d.template __incr<value_type>();
+ ++__t;
+ _BidirectionalIterator __i = __first;
+ while (++__i != __last) {
+ if (__pred(*__i)) {
+ *__first = _Ops::__iter_move(__i);
+ ++__first;
+ } else {
+ ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
__d.template __incr<value_type>();
++__t;
- _BidirectionalIterator __i = __first;
- while (++__i != __last)
- {
- if (__pred(*__i))
- {
- *__first = _Ops::__iter_move(__i);
- ++__first;
- }
- else
- {
- ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
- __d.template __incr<value_type>();
- ++__t;
- }
- }
- // move *__last, known to be true
- *__first = _Ops::__iter_move(__i);
- __i = ++__first;
- // All trues now at start of range, all falses in buffer
- // Move falses back into range, but don't mess up __first which points to first false
- for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
- *__i = _Ops::__iter_move(__t2);
- // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
- return __first;
- }
- // Else not enough buffer, do in place
- // __len >= 4
- _BidirectionalIterator __m = __first;
- _Distance __len2 = __len / 2; // __len2 >= 2
- _Ops::advance(__m, __len2);
- // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
- // F????????????????T
- // f m l
- _BidirectionalIterator __m1 = __m;
- _BidirectionalIterator __first_false = __first;
- _Distance __len_half = __len2;
- while (!__pred(*--__m1))
- {
- if (__m1 == __first)
- goto __first_half_done;
- --__len_half;
+ }
}
- // F???TFFF?????????T
- // f m1 m l
- __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
- __first, __m1, __pred, __len_half, __p, __bit);
+ // move *__last, known to be true
+ *__first = _Ops::__iter_move(__i);
+ __i = ++__first;
+ // All trues now at start of range, all falses in buffer
+ // Move falses back into range, but don't mess up __first which points to first false
+ for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
+ *__i = _Ops::__iter_move(__t2);
+ // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
+ return __first;
+ }
+ // Else not enough buffer, do in place
+ // __len >= 4
+ _BidirectionalIterator __m = __first;
+ _Distance __len2 = __len / 2; // __len2 >= 2
+ _Ops::advance(__m, __len2);
+ // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
+ // F????????????????T
+ // f m l
+ _BidirectionalIterator __m1 = __m;
+ _BidirectionalIterator __first_false = __first;
+ _Distance __len_half = __len2;
+ while (!__pred(*--__m1)) {
+ if (__m1 == __first)
+ goto __first_half_done;
+ --__len_half;
+ }
+ // F???TFFF?????????T
+ // f m1 m l
+ __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m1, __pred, __len_half, __p, __bit);
__first_half_done:
- // TTTFFFFF?????????T
- // f ff m l
- // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
- __m1 = __m;
- _BidirectionalIterator __second_false = __last;
- ++__second_false;
- __len_half = __len - __len2;
- while (__pred(*__m1))
- {
- if (++__m1 == __last)
- goto __second_half_done;
- --__len_half;
- }
- // TTTFFFFFTTTF?????T
- // f ff m m1 l
- __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
- __m1, __last, __pred, __len_half, __p, __bit);
+ // TTTFFFFF?????????T
+ // f ff m l
+ // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
+ __m1 = __m;
+ _BidirectionalIterator __second_false = __last;
+ ++__second_false;
+ __len_half = __len - __len2;
+ while (__pred(*__m1)) {
+ if (++__m1 == __last)
+ goto __second_half_done;
+ --__len_half;
+ }
+ // TTTFFFFFTTTF?????T
+ // f ff m m1 l
+ __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __bit);
__second_half_done:
- // TTTFFFFFTTTTTFFFFF
- // f ff m sf l
- return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
- // TTTTTTTTFFFFFFFFFF
- // |
+ // TTTFFFFFTTTTTFFFFF
+ // f ff m sf l
+ return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
+ // TTTTTTTTFFFFFFFFFF
+ // |
}
template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>
-_LIBCPP_HIDE_FROM_ABI _BidirectionalIterator
-__stable_partition_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
- bidirectional_iterator_tag)
-{
- typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
- typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
- const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
- // Either prove all true and return __first or point to first false
- while (true)
- {
- if (__first == __last)
- return __first;
- if (!__pred(*__first))
- break;
- ++__first;
- }
- // __first points to first false, everything prior to __first is already set.
- // Either prove [__first, __last) is all false and return __first, or point __last to last true
- do
- {
- if (__first == --__last)
- return __first;
- } while (!__pred(*__last));
- // We now have a reduced range [__first, __last]
- // *__first is known to be false
- // *__last is known to be true
- // __len >= 2
- difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1;
- pair<value_type*, ptrdiff_t> __p(0, 0);
- unique_ptr<value_type, __return_temporary_buffer> __h;
- if (__len >= __alloc_limit)
- {
-// TODO: Remove the use of std::get_temporary_buffer
-_LIBCPP_SUPPRESS_DEPRECATED_PUSH
- __p = std::get_temporary_buffer<value_type>(__len);
-_LIBCPP_SUPPRESS_DEPRECATED_POP
- __h.reset(__p.first);
- }
- return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
- std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
+_LIBCPP_HIDE_FROM_ABI _BidirectionalIterator __stable_partition_impl(
+ _BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag) {
+ typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
+ typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+ const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
+ // Either prove all true and return __first or point to first false
+ while (true) {
+ if (__first == __last)
+ return __first;
+ if (!__pred(*__first))
+ break;
+ ++__first;
+ }
+ // __first points to first false, everything prior to __first is already set.
+ // Either prove [__first, __last) is all false and return __first, or point __last to last true
+ do {
+ if (__first == --__last)
+ return __first;
+ } while (!__pred(*__last));
+ // We now have a reduced range [__first, __last]
+ // *__first is known to be false
+ // *__last is known to be true
+ // __len >= 2
+ difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1;
+ pair<value_type*, ptrdiff_t> __p(0, 0);
+ unique_ptr<value_type, __return_temporary_buffer> __h;
+ if (__len >= __alloc_limit) {
+ // TODO: Remove the use of std::get_temporary_buffer
+ _LIBCPP_SUPPRESS_DEPRECATED_PUSH
+ __p = std::get_temporary_buffer<value_type>(__len);
+ _LIBCPP_SUPPRESS_DEPRECATED_POP
+ __h.reset(__p.first);
+ }
+ return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
+ std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
}
template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>
-_LIBCPP_HIDE_FROM_ABI
-_ForwardIterator __stable_partition(
+_LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition(
_ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) {
return std::__stable_partition_impl<_AlgPolicy, __remove_cvref_t<_Predicate>&>(
std::move(__first), std::move(__last), __pred, __iter_category);
}
template <class _ForwardIterator, class _Predicate>
-inline _LIBCPP_HIDE_FROM_ABI
-_ForwardIterator
-stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
-{
+inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator
+stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>(
std::move(__first), std::move(__last), __pred, _IterCategory());
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-07 10:58:58 +0000