// 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 <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));
+ 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>
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>);
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>(__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::__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>(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)
+ 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, __first, __num);
- return {__first + __num, __result + __num};
- }
- else
- {
- 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
{
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>
- (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>(__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::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)
- {
- 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
+ if (!std::__is_constant_evaluated())
{
- 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
{
_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;
projects / thirdparty / gcc.git / blobdiff