// Core algorithmic facilities -*- C++ -*-
-// Copyright (C) 2020 Free Software Foundation, Inc.
+// Copyright (C) 2020-2024 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
#if __cplusplus > 201703L
-#include <cmath>
#include <compare>
-#include <iterator>
-// #include <bits/range_concepts.h>
-#include <ranges>
-#include <bits/invoke.h>
+#include <bits/stl_iterator_base_funcs.h>
+#include <bits/stl_iterator.h>
+#include <bits/ranges_base.h> // ranges::begin, ranges::range etc.
+#include <bits/invoke.h> // __invoke
#include <bits/cpp_type_traits.h> // __is_byte
#if __cpp_lib_concepts
// TODO: implement more specializations to at least have parity with
// std::equal.
if constexpr (__detail::__is_normal_iterator<_Iter1>
- || __detail::__is_normal_iterator<_Iter2>)
- return (*this)(std::__niter_base(std::move(__first1)),
- std::__niter_base(std::move(__last1)),
- std::__niter_base(std::move(__first2)),
- std::__niter_base(std::move(__last2)),
+ && same_as<_Iter1, _Sent1>)
+ return (*this)(__first1.base(), __last1.base(),
+ std::move(__first2), std::move(__last2),
std::move(__pred),
std::move(__proj1), std::move(__proj2));
-
- constexpr bool __sized_iters
- = (sized_sentinel_for<_Sent1, _Iter1>
- && sized_sentinel_for<_Sent2, _Iter2>);
- if constexpr (__sized_iters)
+ else if constexpr (__detail::__is_normal_iterator<_Iter2>
+ && same_as<_Iter2, _Sent2>)
+ return (*this)(std::move(__first1), std::move(__last1),
+ __first2.base(), __last2.base(),
+ std::move(__pred),
+ std::move(__proj1), std::move(__proj2));
+ else if constexpr (sized_sentinel_for<_Sent1, _Iter1>
+ && sized_sentinel_for<_Sent2, _Iter2>)
{
auto __d1 = ranges::distance(__first1, __last1);
auto __d2 = ranges::distance(__first2, __last2);
return false;
using _ValueType1 = iter_value_t<_Iter1>;
- using _ValueType2 = iter_value_t<_Iter2>;
constexpr bool __use_memcmp
= ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
- && is_same_v<_ValueType1, _ValueType2>
- && is_pointer_v<_Iter1>
- && is_pointer_v<_Iter2>
+ && __memcmpable<_Iter1, _Iter2>::__value
&& is_same_v<_Pred, ranges::equal_to>
&& is_same_v<_Proj1, identity>
&& is_same_v<_Proj2, identity>);
inline constexpr __equal_fn equal{};
template<typename _Iter, typename _Out>
- struct copy_result
+ struct in_out_result
{
[[no_unique_address]] _Iter in;
[[no_unique_address]] _Out out;
template<typename _Iter2, typename _Out2>
requires convertible_to<const _Iter&, _Iter2>
&& convertible_to<const _Out&, _Out2>
- operator copy_result<_Iter2, _Out2>() const &
+ constexpr
+ operator in_out_result<_Iter2, _Out2>() const &
{ return {in, out}; }
template<typename _Iter2, typename _Out2>
requires convertible_to<_Iter, _Iter2>
&& convertible_to<_Out, _Out2>
- operator copy_result<_Iter2, _Out2>() &&
+ constexpr
+ operator in_out_result<_Iter2, _Out2>() &&
{ return {std::move(in), std::move(out)}; }
};
template<typename _Iter, typename _Out>
- using move_result = copy_result<_Iter, _Out>;
+ using copy_result = in_out_result<_Iter, _Out>;
+
+ template<typename _Iter, typename _Out>
+ using move_result = in_out_result<_Iter, _Out>;
template<typename _Iter1, typename _Iter2>
- using move_backward_result = copy_result<_Iter1, _Iter2>;
+ using move_backward_result = in_out_result<_Iter1, _Iter2>;
template<typename _Iter1, typename _Iter2>
- using copy_backward_result = copy_result<_Iter1, _Iter2>;
+ using copy_backward_result = in_out_result<_Iter1, _Iter2>;
template<bool _IsMove,
bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
requires (_IsMove
? indirectly_movable<_Iter, _Out>
: indirectly_copyable<_Iter, _Out>)
- constexpr conditional_t<_IsMove,
- move_backward_result<_Iter, _Out>,
- copy_backward_result<_Iter, _Out>>
+ constexpr __conditional_t<_IsMove,
+ move_backward_result<_Iter, _Out>,
+ copy_backward_result<_Iter, _Out>>
__copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
template<bool _IsMove,
requires (_IsMove
? indirectly_movable<_Iter, _Out>
: indirectly_copyable<_Iter, _Out>)
- constexpr conditional_t<_IsMove,
- move_result<_Iter, _Out>,
- copy_result<_Iter, _Out>>
+ constexpr __conditional_t<_IsMove,
+ move_result<_Iter, _Out>,
+ copy_result<_Iter, _Out>>
__copy_or_move(_Iter __first, _Sent __last, _Out __result)
{
// TODO: implement more specializations to be at least on par with
// std::copy/std::move.
- constexpr bool __normal_iterator_p
- = (__detail::__is_normal_iterator<_Iter>
- || __detail::__is_normal_iterator<_Out>);
- constexpr bool __reverse_p
- = (__detail::__is_reverse_iterator<_Iter>
- && __detail::__is_reverse_iterator<_Out>);
- constexpr bool __move_iterator_p = __detail::__is_move_iterator<_Iter>;
- if constexpr (__move_iterator_p)
+ using __detail::__is_move_iterator;
+ using __detail::__is_reverse_iterator;
+ using __detail::__is_normal_iterator;
+ if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>)
{
auto [__in, __out]
= ranges::__copy_or_move<true>(std::move(__first).base(),
std::move(__result));
return {move_iterator{std::move(__in)}, std::move(__out)};
}
- else if constexpr (__reverse_p)
+ else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
+ && __is_reverse_iterator<_Out>)
{
auto [__in,__out]
- = ranges::__copy_or_move_backward<_IsMove>(__last.base(),
- __first.base(),
- __result.base());
+ = ranges::__copy_or_move_backward<_IsMove>(std::move(__last).base(),
+ std::move(__first).base(),
+ std::move(__result).base());
return {reverse_iterator{std::move(__in)},
reverse_iterator{std::move(__out)}};
}
- else if constexpr (__normal_iterator_p)
+ else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
{
auto [__in,__out]
- = ranges::__copy_or_move<_IsMove>(std::__niter_base(__first),
- std::__niter_base(__last),
- std::__niter_base(__result));
- return {std::__niter_wrap(__first, std::move(__in)),
- std::__niter_wrap(__result, std::move(__out))};
+ = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(),
+ std::move(__result));
+ return {decltype(__first){__in}, std::move(__out)};
+ }
+ else if constexpr (__is_normal_iterator<_Out>)
+ {
+ auto [__in,__out]
+ = ranges::__copy_or_move<_IsMove>(std::move(__first), __last, __result.base());
+ return {std::move(__in), decltype(__result){__out}};
}
else if constexpr (sized_sentinel_for<_Sent, _Iter>)
{
- using _ValueTypeI = iter_value_t<_Iter>;
- using _ValueTypeO = iter_value_t<_Out>;
- constexpr bool __use_memmove
- = (is_trivially_copyable_v<_ValueTypeI>
- && is_same_v<_ValueTypeI, _ValueTypeO>
- && is_pointer_v<_Iter>
- && is_pointer_v<_Out>);
-
- if constexpr (__use_memmove)
- {
- static_assert(_IsMove
- ? is_move_assignable_v<_ValueTypeI>
- : is_copy_assignable_v<_ValueTypeI>);
- auto __num = __last - __first;
- if (__num)
- std::__memmove<_IsMove>(__result, __first, __num);
- return {__first + __num, __result + __num};
- }
- else
+ if (!std::__is_constant_evaluated())
{
- for (auto __n = __last - __first; __n > 0; --__n)
+ if constexpr (__memcpyable<_Iter, _Out>::__value)
{
- if constexpr (_IsMove)
- *__result = std::move(*__first);
- else
- *__result = *__first;
- ++__first;
- ++__result;
+ using _ValueTypeI = iter_value_t<_Iter>;
+ static_assert(_IsMove
+ ? is_move_assignable_v<_ValueTypeI>
+ : is_copy_assignable_v<_ValueTypeI>);
+ auto __num = __last - __first;
+ if (__num)
+ __builtin_memmove(__result, __first,
+ sizeof(_ValueTypeI) * __num);
+ return {__first + __num, __result + __num};
}
- return {std::move(__first), std::move(__result)};
}
+
+ for (auto __n = __last - __first; __n > 0; --__n)
+ {
+ if constexpr (_IsMove)
+ *__result = std::move(*__first);
+ else
+ *__result = *__first;
+ ++__first;
+ ++__result;
+ }
+ return {std::move(__first), std::move(__result)};
}
else
{
template<input_range _Range, weakly_incrementable _Out>
requires indirectly_copyable<iterator_t<_Range>, _Out>
- constexpr copy_result<safe_iterator_t<_Range>, _Out>
+ constexpr copy_result<borrowed_iterator_t<_Range>, _Out>
operator()(_Range&& __r, _Out __result) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
template<input_range _Range, weakly_incrementable _Out>
requires indirectly_movable<iterator_t<_Range>, _Out>
- constexpr move_result<safe_iterator_t<_Range>, _Out>
+ constexpr move_result<borrowed_iterator_t<_Range>, _Out>
operator()(_Range&& __r, _Out __result) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
requires (_IsMove
? indirectly_movable<_Iter, _Out>
: indirectly_copyable<_Iter, _Out>)
- constexpr conditional_t<_IsMove,
- move_backward_result<_Iter, _Out>,
- copy_backward_result<_Iter, _Out>>
+ constexpr __conditional_t<_IsMove,
+ move_backward_result<_Iter, _Out>,
+ copy_backward_result<_Iter, _Out>>
__copy_or_move_backward(_Iter __first, _Sent __last, _Out __result)
{
// TODO: implement more specializations to be at least on par with
// std::copy_backward/std::move_backward.
- constexpr bool __normal_iterator_p
- = (__detail::__is_normal_iterator<_Iter>
- || __detail::__is_normal_iterator<_Out>);
- constexpr bool __reverse_p
- = (__detail::__is_reverse_iterator<_Iter>
- && __detail::__is_reverse_iterator<_Out>);
- if constexpr (__reverse_p)
+ using __detail::__is_reverse_iterator;
+ using __detail::__is_normal_iterator;
+ if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
+ && __is_reverse_iterator<_Out>)
{
auto [__in,__out]
- = ranges::__copy_or_move<_IsMove>(__last.base(),
- __first.base(),
- __result.base());
+ = ranges::__copy_or_move<_IsMove>(std::move(__last).base(),
+ std::move(__first).base(),
+ std::move(__result).base());
return {reverse_iterator{std::move(__in)},
reverse_iterator{std::move(__out)}};
}
- else if constexpr (__normal_iterator_p)
+ else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
+ {
+ auto [__in,__out]
+ = ranges::__copy_or_move_backward<_IsMove>(__first.base(),
+ __last.base(),
+ std::move(__result));
+ return {decltype(__first){__in}, std::move(__out)};
+ }
+ else if constexpr (__is_normal_iterator<_Out>)
{
auto [__in,__out]
- = ranges::__copy_or_move_backward<_IsMove>
- (std::__niter_base(__first),
- std::__niter_base(__last),
- std::__niter_base(__result));
- return {std::__niter_wrap(__first, std::move(__in)),
- std::__niter_wrap(__result, std::move(__out))};
+ = ranges::__copy_or_move_backward<_IsMove>(std::move(__first),
+ std::move(__last),
+ __result.base());
+ return {std::move(__in), decltype(__result){__out}};
}
else if constexpr (sized_sentinel_for<_Sent, _Iter>)
{
- using _ValueTypeI = iter_value_t<_Iter>;
- using _ValueTypeO = iter_value_t<_Out>;
- constexpr bool __use_memmove
- = (is_trivially_copyable_v<_ValueTypeI>
- && is_same_v<_ValueTypeI, _ValueTypeO>
- && is_pointer_v<_Iter>
- && is_pointer_v<_Out>);
- if constexpr (__use_memmove)
+ if (!std::__is_constant_evaluated())
{
- static_assert(_IsMove
- ? is_move_assignable_v<_ValueTypeI>
- : is_copy_assignable_v<_ValueTypeI>);
- auto __num = __last - __first;
- if (__num)
- std::__memmove<_IsMove>(__result - __num, __first, __num);
- return {__first + __num, __result - __num};
- }
- else
- {
- auto __lasti = ranges::next(__first, __last);
- auto __tail = __lasti;
-
- for (auto __n = __last - __first; __n > 0; --__n)
+ if constexpr (__memcpyable<_Out, _Iter>::__value)
{
- --__tail;
- --__result;
- if constexpr (_IsMove)
- *__result = std::move(*__tail);
- else
- *__result = *__tail;
+ using _ValueTypeI = iter_value_t<_Iter>;
+ static_assert(_IsMove
+ ? is_move_assignable_v<_ValueTypeI>
+ : is_copy_assignable_v<_ValueTypeI>);
+ auto __num = __last - __first;
+ if (__num)
+ __builtin_memmove(__result - __num, __first,
+ sizeof(_ValueTypeI) * __num);
+ return {__first + __num, __result - __num};
}
- return {std::move(__lasti), std::move(__result)};
}
+
+ auto __lasti = ranges::next(__first, __last);
+ auto __tail = __lasti;
+
+ for (auto __n = __last - __first; __n > 0; --__n)
+ {
+ --__tail;
+ --__result;
+ if constexpr (_IsMove)
+ *__result = std::move(*__tail);
+ else
+ *__result = *__tail;
+ }
+ return {std::move(__lasti), std::move(__result)};
}
else
{
template<bidirectional_range _Range, bidirectional_iterator _Iter>
requires indirectly_copyable<iterator_t<_Range>, _Iter>
- constexpr copy_backward_result<safe_iterator_t<_Range>, _Iter>
+ constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter>
operator()(_Range&& __r, _Iter __result) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
template<bidirectional_range _Range, bidirectional_iterator _Iter>
requires indirectly_movable<iterator_t<_Range>, _Iter>
- constexpr move_backward_result<safe_iterator_t<_Range>, _Iter>
+ constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter>
operator()(_Range&& __r, _Iter __result) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
inline constexpr __move_backward_fn move_backward{};
template<typename _Iter, typename _Out>
- using copy_n_result = copy_result<_Iter, _Out>;
+ using copy_n_result = in_out_result<_Iter, _Out>;
struct __copy_n_fn
{
_Out __result) const
{
if constexpr (random_access_iterator<_Iter>)
- return ranges::copy(__first, __first + __n, std::move(__result));
+ {
+ if (__n > 0)
+ return ranges::copy(__first, __first + __n, std::move(__result));
+ }
else
{
for (; __n > 0; --__n, (void)++__result, (void)++__first)
*__result = *__first;
- return {std::move(__first), std::move(__result)};
}
+ return {std::move(__first), std::move(__result)};
}
};
if (__n <= 0)
return __first;
- // TODO: is __is_byte the best condition?
- if constexpr (is_pointer_v<_Out> && __is_byte<_Tp>::__value)
- {
- __builtin_memset(__first, static_cast<unsigned char>(__value), __n);
- return __first + __n;
- }
- else if constexpr (is_scalar_v<_Tp>)
+ if constexpr (is_scalar_v<_Tp>)
{
+ // TODO: Generalize this optimization to contiguous iterators.
+ if constexpr (is_pointer_v<_Out>
+ // Note that __is_byte already implies !is_volatile.
+ && __is_byte<remove_pointer_t<_Out>>::__value
+ && integral<_Tp>)
+ {
+ if (!std::__is_constant_evaluated())
+ {
+ __builtin_memset(__first,
+ static_cast<unsigned char>(__value),
+ __n);
+ return __first + __n;
+ }
+ }
+
const auto __tmp = __value;
for (; __n > 0; --__n, (void)++__first)
*__first = __tmp;
}
template<typename _Tp, output_range<const _Tp&> _Range>
- constexpr safe_iterator_t<_Range>
+ constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, const _Tp& __value) const
{
return (*this)(ranges::begin(__r), ranges::end(__r), __value);
projects / thirdparty / gcc.git / blobdiff