From 90fc7b3ce0ee24c08b1edd40c528467939ef9d4f Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Wed, 12 Feb 2020 12:30:57 -0500 Subject: [PATCH] libstdc++: Move some ranges algos to a new header This roughly mirrors the existing split between and . The ranges [specialized.algorithms] will use this new header to avoid including all of of . libstdc++-v3/ChangeLog: * include/Makefile.am: Add bits/ranges_algobase.h * include/Makefile.in: Regenerate. * bits/ranges_algo.h: Include and refactor existing #includes. (__detail::__is_normal_iterator, __detail::is_reverse_iterator, __detail::__is_move_iterator, copy_result, move_result, __equal, equal, copy_result, move_result, move_backward_result, copy_backward_result, __copy_or_move_backward, __copy_or_move, copy, move, copy_backward, move_backward, copy_n_result, copy_n, fill_n, fill): Split out into ... * bits/range_algobase.h: ... this new header. --- libstdc++-v3/ChangeLog | 14 + libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/ranges_algo.h | 508 +----------------- libstdc++-v3/include/bits/ranges_algobase.h | 556 ++++++++++++++++++++ 5 files changed, 573 insertions(+), 507 deletions(-) create mode 100644 libstdc++-v3/include/bits/ranges_algobase.h diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index cc4cfb7da0f..8715e50daba 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,17 @@ +2020-02-13 Patrick Palka + + * include/Makefile.am: Add bits/ranges_algobase.h + * include/Makefile.in: Regenerate. + * bits/ranges_algo.h: Include and refactor + existing #includes. + (__detail::__is_normal_iterator, __detail::is_reverse_iterator, + __detail::__is_move_iterator, copy_result, move_result, + __equal, equal, copy_result, move_result, move_backward_result, + copy_backward_result, __copy_or_move_backward, __copy_or_move, copy, + move, copy_backward, move_backward, copy_n_result, copy_n, fill_n, + fill): Split out into ... + * bits/range_algobase.h: ... this new header. + 2020-02-12 Patrick Palka LWG 3389 and LWG 3390 diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 1d342cecbcc..614222db400 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -157,6 +157,7 @@ bits_headers = \ ${bits_srcdir}/random.tcc \ ${bits_srcdir}/range_access.h \ ${bits_srcdir}/range_cmp.h \ + ${bits_srcdir}/ranges_algobase.h \ ${bits_srcdir}/ranges_algo.h \ ${bits_srcdir}/refwrap.h \ ${bits_srcdir}/regex.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index c735d67a5d3..7ee6a1e3f61 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -502,6 +502,7 @@ bits_headers = \ ${bits_srcdir}/random.tcc \ ${bits_srcdir}/range_access.h \ ${bits_srcdir}/range_cmp.h \ + ${bits_srcdir}/ranges_algobase.h \ ${bits_srcdir}/ranges_algo.h \ ${bits_srcdir}/refwrap.h \ ${bits_srcdir}/regex.h \ diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index e065ff2a974..84a02cabb80 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -32,13 +32,7 @@ #if __cplusplus > 201703L -#include -#include -#include -// #include -#include -#include -#include // __is_byte +#include #include // concept uniform_random_bit_generator #if __cpp_lib_concepts @@ -49,28 +43,6 @@ namespace ranges { namespace __detail { - template - constexpr inline bool __is_normal_iterator = false; - - template - constexpr inline bool - __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator, - _Container>> = true; - - template - constexpr inline bool __is_reverse_iterator = false; - - template - constexpr inline bool - __is_reverse_iterator> = true; - - template - constexpr inline bool __is_move_iterator = false; - - template - constexpr inline bool - __is_move_iterator> = true; - template constexpr auto __make_comp_proj(_Comp& __comp, _Proj& __proj) @@ -741,420 +713,6 @@ namespace ranges std::move(__proj1), std::move(__proj2)); } - template _Sent1, - input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Pred, typename _Proj1, typename _Proj2> - requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - constexpr bool - __equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, - _Pred __pred, _Proj1 __proj1, _Proj2 __proj2) - { - // TODO: implement more specializations to at least have parity with - // std::equal. - constexpr bool __sized_iters - = (sized_sentinel_for<_Sent1, _Iter1> - && sized_sentinel_for<_Sent2, _Iter2>); - if constexpr (__sized_iters) - { - auto __d1 = ranges::distance(__first1, __last1); - auto __d2 = ranges::distance(__first2, __last2); - if (__d1 != __d2) - 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> - && is_same_v<_Pred, ranges::equal_to> - && is_same_v<_Proj1, identity> - && is_same_v<_Proj2, identity>); - if constexpr (__use_memcmp) - { - if (const size_t __len = (__last1 - __first1)) - return !std::__memcmp(__first1, __first2, __len); - return true; - } - else - { - for (; __first1 != __last1; ++__first1, (void)++__first2) - if (!(bool)std::__invoke(__pred, - std::__invoke(__proj1, *__first1), - std::__invoke(__proj2, *__first2))) - return false; - return true; - } - } - else - { - for (; __first1 != __last1 && __first2 != __last2; - ++__first1, (void)++__first2) - if (!(bool)std::__invoke(__pred, - std::__invoke(__proj1, *__first1), - std::__invoke(__proj2, *__first2))) - return false; - return __first1 == __last1 && __first2 == __last2; - } - } - - template _Sent1, - input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Pred = ranges::equal_to, - typename _Proj1 = identity, typename _Proj2 = identity> - requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - constexpr bool - equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, - _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) - { - return ranges::__equal(std::__niter_base(std::move(__first1)), - std::__niter_base(std::move(__last1)), - std::__niter_base(std::move(__first2)), - std::__niter_base(std::move(__last2)), - std::move(__pred), - std::move(__proj1), std::move(__proj2)); - } - - template - requires indirectly_comparable, iterator_t<_Range2>, - _Pred, _Proj1, _Proj2> - constexpr bool - equal(_Range1&& __r1, _Range2&& __r2, - _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) - { - return ranges::equal(ranges::begin(__r1), ranges::end(__r1), - ranges::begin(__r2), ranges::end(__r2), - std::move(__pred), - std::move(__proj1), std::move(__proj2)); - } - - template - struct copy_result - { - [[no_unique_address]] _Iter in; - [[no_unique_address]] _Out out; - - template - requires convertible_to - && convertible_to - operator copy_result<_Iter2, _Out2>() const & - { return {in, out}; } - - template - requires convertible_to<_Iter, _Iter2> - && convertible_to<_Out, _Out2> - operator copy_result<_Iter2, _Out2>() && - { return {std::move(in), std::move(out)}; } - }; - - template - using move_result = copy_result<_Iter, _Out>; - - template - using move_backward_result = copy_result<_Iter1, _Iter2>; - - template - using copy_backward_result = copy_result<_Iter1, _Iter2>; - - template _Sent, - bidirectional_iterator _Out> - requires (_IsMove - ? indirectly_movable<_Iter, _Out> - : indirectly_copyable<_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 _Sent, - weakly_incrementable _Out> - requires (_IsMove - ? indirectly_movable<_Iter, _Out> - : indirectly_copyable<_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) - { - auto [__in, __out] - = ranges::__copy_or_move(std::move(__first).base(), - std::move(__last).base(), - std::move(__result)); - return {move_iterator{std::move(__in)}, std::move(__out)}; - } - else if constexpr (__reverse_p) - { - auto [__in,__out] - = ranges::__copy_or_move_backward<_IsMove>(__last.base(), - __first.base(), - __result.base()); - return {reverse_iterator{std::move(__in)}, - reverse_iterator{std::move(__out)}}; - } - else if constexpr (__normal_iterator_p) - { - 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))}; - } - 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 - { - 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 - { - while (__first != __last) - { - if constexpr (_IsMove) - *__result = std::move(*__first); - else - *__result = *__first; - ++__first; - ++__result; - } - return {std::move(__first), std::move(__result)}; - } - } - - template _Sent, - weakly_incrementable _Out> - requires indirectly_copyable<_Iter, _Out> - constexpr copy_result<_Iter, _Out> - copy(_Iter __first, _Sent __last, _Out __result) - { - return ranges::__copy_or_move(std::move(__first), - std::move(__last), - std::move(__result)); - } - - template - requires indirectly_copyable, _Out> - constexpr copy_result, _Out> - copy(_Range&& __r, _Out __result) - { - return ranges::copy(ranges::begin(__r), ranges::end(__r), - std::move(__result)); - } - - template _Sent, - weakly_incrementable _Out> - requires indirectly_movable<_Iter, _Out> - constexpr move_result<_Iter, _Out> - move(_Iter __first, _Sent __last, _Out __result) - { - return ranges::__copy_or_move(std::move(__first), - std::move(__last), - std::move(__result)); - } - - template - requires indirectly_movable, _Out> - constexpr move_result, _Out> - move(_Range&& __r, _Out __result) - { - return ranges::move(ranges::begin(__r), ranges::end(__r), - std::move(__result)); - } - - template _Sent, - bidirectional_iterator _Out> - requires (_IsMove - ? indirectly_movable<_Iter, _Out> - : indirectly_copyable<_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) - { - auto [__in,__out] - = ranges::__copy_or_move<_IsMove>(__last.base(), - __first.base(), - __result.base()); - return {reverse_iterator{std::move(__in)}, - reverse_iterator{std::move(__out)}}; - } - else if constexpr (__normal_iterator_p) - { - 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))}; - } - 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 - { - 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 - { - auto __lasti = ranges::next(__first, __last); - auto __tail = __lasti; - - while (__first != __tail) - { - --__tail; - --__result; - if constexpr (_IsMove) - *__result = std::move(*__tail); - else - *__result = *__tail; - } - return {std::move(__lasti), std::move(__result)}; - } - } - - template _Sent1, - bidirectional_iterator _Iter2> - requires indirectly_copyable<_Iter1, _Iter2> - constexpr copy_backward_result<_Iter1, _Iter2> - copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) - { - return ranges::__copy_or_move_backward(std::move(__first), - std::move(__last), - std::move(__result)); - } - - template - requires indirectly_copyable, _Iter> - constexpr copy_backward_result, _Iter> - copy_backward(_Range&& __r, _Iter __result) - { - return ranges::copy_backward(ranges::begin(__r), ranges::end(__r), - std::move(__result)); - } - - template _Sent1, - bidirectional_iterator _Iter2> - requires indirectly_movable<_Iter1, _Iter2> - constexpr move_backward_result<_Iter1, _Iter2> - move_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) - { - return ranges::__copy_or_move_backward(std::move(__first), - std::move(__last), - std::move(__result)); - } - - template - requires indirectly_movable, _Iter> - constexpr move_backward_result, _Iter> - move_backward(_Range&& __r, _Iter __result) - { - return ranges::move_backward(ranges::begin(__r), ranges::end(__r), - std::move(__result)); - } - - template - using copy_n_result = copy_result<_Iter, _Out>; - - template - requires indirectly_copyable<_Iter, _Out> - constexpr copy_n_result<_Iter, _Out> - copy_n(_Iter __first, iter_difference_t<_Iter> __n, _Out __result) - { - if constexpr (random_access_iterator<_Iter>) - 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)}; - } - } - template using copy_if_result = copy_result<_Iter, _Out>; @@ -1434,70 +992,6 @@ namespace ranges __new_value, std::move(__proj)); } - template _Out> - constexpr _Out - fill_n(_Out __first, iter_difference_t<_Out> __n, const _Tp& __value) - { - // TODO: implement more specializations to be at least on par with - // std::fill_n - 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(__value), __n); - return __first + __n; - } - else if constexpr (is_scalar_v<_Tp>) - { - const auto __tmp = __value; - for (; __n > 0; --__n, (void)++__first) - *__first = __tmp; - return __first; - } - else - { - for (; __n > 0; --__n, (void)++__first) - *__first = __value; - return __first; - } - } - - template _Out, sentinel_for<_Out> _Sent> - constexpr _Out - fill(_Out __first, _Sent __last, const _Tp& __value) - { - // TODO: implement more specializations to be at least on par with - // std::fill - if constexpr (sized_sentinel_for<_Sent, _Out>) - { - const auto __len = __last - __first; - return ranges::fill_n(__first, __len, __value); - } - else if constexpr (is_scalar_v<_Tp>) - { - const auto __tmp = __value; - for (; __first != __last; ++__first) - *__first = __tmp; - return __first; - } - else - { - for (; __first != __last; ++__first) - *__first = __value; - return __first; - } - } - - template _Range> - constexpr safe_iterator_t<_Range> - fill(_Range&& __r, const _Tp& __value) - { - return ranges::fill(ranges::begin(__r), ranges::end(__r), __value); - } - template requires invocable<_Fp&> && indirectly_writable<_Out, invoke_result_t<_Fp&>> diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h new file mode 100644 index 00000000000..f63c032cf0b --- /dev/null +++ b/libstdc++-v3/include/bits/ranges_algobase.h @@ -0,0 +1,556 @@ +// Core algorithmic facilities -*- C++ -*- + +// Copyright (C) 2020 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 +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file bits/ranges_algobase.h + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{algorithm} + */ + +#ifndef _RANGES_ALGOBASE_H +#define _RANGES_ALGOBASE_H 1 + +#if __cplusplus > 201703L + +#include +#include +#include +// #include +#include +#include +#include // __is_byte + +#if __cpp_lib_concepts +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION +namespace ranges +{ + namespace __detail + { + template + constexpr inline bool __is_normal_iterator = false; + + template + constexpr inline bool + __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator, + _Container>> = true; + + template + constexpr inline bool __is_reverse_iterator = false; + + template + constexpr inline bool + __is_reverse_iterator> = true; + + template + constexpr inline bool __is_move_iterator = false; + + template + constexpr inline bool + __is_move_iterator> = true; + } // namespace __detail + + template _Sent1, + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + typename _Pred, typename _Proj1, typename _Proj2> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + constexpr bool + __equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred __pred, _Proj1 __proj1, _Proj2 __proj2) + { + // TODO: implement more specializations to at least have parity with + // std::equal. + constexpr bool __sized_iters + = (sized_sentinel_for<_Sent1, _Iter1> + && sized_sentinel_for<_Sent2, _Iter2>); + if constexpr (__sized_iters) + { + auto __d1 = ranges::distance(__first1, __last1); + auto __d2 = ranges::distance(__first2, __last2); + if (__d1 != __d2) + 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> + && is_same_v<_Pred, ranges::equal_to> + && is_same_v<_Proj1, identity> + && is_same_v<_Proj2, identity>); + if constexpr (__use_memcmp) + { + if (const size_t __len = (__last1 - __first1)) + return !std::__memcmp(__first1, __first2, __len); + return true; + } + else + { + for (; __first1 != __last1; ++__first1, (void)++__first2) + if (!(bool)std::__invoke(__pred, + std::__invoke(__proj1, *__first1), + std::__invoke(__proj2, *__first2))) + return false; + return true; + } + } + else + { + for (; __first1 != __last1 && __first2 != __last2; + ++__first1, (void)++__first2) + if (!(bool)std::__invoke(__pred, + std::__invoke(__proj1, *__first1), + std::__invoke(__proj2, *__first2))) + return false; + return __first1 == __last1 && __first2 == __last2; + } + } + + template _Sent1, + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + constexpr bool + equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) + { + return ranges::__equal(std::__niter_base(std::move(__first1)), + std::__niter_base(std::move(__last1)), + std::__niter_base(std::move(__first2)), + std::__niter_base(std::move(__last2)), + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + + template + requires indirectly_comparable, iterator_t<_Range2>, + _Pred, _Proj1, _Proj2> + constexpr bool + equal(_Range1&& __r1, _Range2&& __r2, + _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) + { + return ranges::equal(ranges::begin(__r1), ranges::end(__r1), + ranges::begin(__r2), ranges::end(__r2), + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + + template + struct copy_result + { + [[no_unique_address]] _Iter in; + [[no_unique_address]] _Out out; + + template + requires convertible_to + && convertible_to + operator copy_result<_Iter2, _Out2>() const & + { return {in, out}; } + + template + requires convertible_to<_Iter, _Iter2> + && convertible_to<_Out, _Out2> + operator copy_result<_Iter2, _Out2>() && + { return {std::move(in), std::move(out)}; } + }; + + template + using move_result = copy_result<_Iter, _Out>; + + template + using move_backward_result = copy_result<_Iter1, _Iter2>; + + template + using copy_backward_result = copy_result<_Iter1, _Iter2>; + + template _Sent, + bidirectional_iterator _Out> + requires (_IsMove + ? indirectly_movable<_Iter, _Out> + : indirectly_copyable<_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 _Sent, + weakly_incrementable _Out> + requires (_IsMove + ? indirectly_movable<_Iter, _Out> + : indirectly_copyable<_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) + { + auto [__in, __out] + = ranges::__copy_or_move(std::move(__first).base(), + std::move(__last).base(), + std::move(__result)); + return {move_iterator{std::move(__in)}, std::move(__out)}; + } + else if constexpr (__reverse_p) + { + auto [__in,__out] + = ranges::__copy_or_move_backward<_IsMove>(__last.base(), + __first.base(), + __result.base()); + return {reverse_iterator{std::move(__in)}, + reverse_iterator{std::move(__out)}}; + } + else if constexpr (__normal_iterator_p) + { + 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))}; + } + 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 + { + 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 + { + while (__first != __last) + { + if constexpr (_IsMove) + *__result = std::move(*__first); + else + *__result = *__first; + ++__first; + ++__result; + } + return {std::move(__first), std::move(__result)}; + } + } + + template _Sent, + weakly_incrementable _Out> + requires indirectly_copyable<_Iter, _Out> + constexpr copy_result<_Iter, _Out> + copy(_Iter __first, _Sent __last, _Out __result) + { + return ranges::__copy_or_move(std::move(__first), + std::move(__last), + std::move(__result)); + } + + template + requires indirectly_copyable, _Out> + constexpr copy_result, _Out> + copy(_Range&& __r, _Out __result) + { + return ranges::copy(ranges::begin(__r), ranges::end(__r), + std::move(__result)); + } + + template _Sent, + weakly_incrementable _Out> + requires indirectly_movable<_Iter, _Out> + constexpr move_result<_Iter, _Out> + move(_Iter __first, _Sent __last, _Out __result) + { + return ranges::__copy_or_move(std::move(__first), + std::move(__last), + std::move(__result)); + } + + template + requires indirectly_movable, _Out> + constexpr move_result, _Out> + move(_Range&& __r, _Out __result) + { + return ranges::move(ranges::begin(__r), ranges::end(__r), + std::move(__result)); + } + + template _Sent, + bidirectional_iterator _Out> + requires (_IsMove + ? indirectly_movable<_Iter, _Out> + : indirectly_copyable<_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) + { + auto [__in,__out] + = ranges::__copy_or_move<_IsMove>(__last.base(), + __first.base(), + __result.base()); + return {reverse_iterator{std::move(__in)}, + reverse_iterator{std::move(__out)}}; + } + else if constexpr (__normal_iterator_p) + { + 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))}; + } + 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 + { + 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 + { + auto __lasti = ranges::next(__first, __last); + auto __tail = __lasti; + + while (__first != __tail) + { + --__tail; + --__result; + if constexpr (_IsMove) + *__result = std::move(*__tail); + else + *__result = *__tail; + } + return {std::move(__lasti), std::move(__result)}; + } + } + + template _Sent1, + bidirectional_iterator _Iter2> + requires indirectly_copyable<_Iter1, _Iter2> + constexpr copy_backward_result<_Iter1, _Iter2> + copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) + { + return ranges::__copy_or_move_backward(std::move(__first), + std::move(__last), + std::move(__result)); + } + + template + requires indirectly_copyable, _Iter> + constexpr copy_backward_result, _Iter> + copy_backward(_Range&& __r, _Iter __result) + { + return ranges::copy_backward(ranges::begin(__r), ranges::end(__r), + std::move(__result)); + } + + template _Sent1, + bidirectional_iterator _Iter2> + requires indirectly_movable<_Iter1, _Iter2> + constexpr move_backward_result<_Iter1, _Iter2> + move_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) + { + return ranges::__copy_or_move_backward(std::move(__first), + std::move(__last), + std::move(__result)); + } + + template + requires indirectly_movable, _Iter> + constexpr move_backward_result, _Iter> + move_backward(_Range&& __r, _Iter __result) + { + return ranges::move_backward(ranges::begin(__r), ranges::end(__r), + std::move(__result)); + } + + template + using copy_n_result = copy_result<_Iter, _Out>; + + template + requires indirectly_copyable<_Iter, _Out> + constexpr copy_n_result<_Iter, _Out> + copy_n(_Iter __first, iter_difference_t<_Iter> __n, _Out __result) + { + if constexpr (random_access_iterator<_Iter>) + 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)}; + } + } + + template _Out> + constexpr _Out + fill_n(_Out __first, iter_difference_t<_Out> __n, const _Tp& __value) + { + // TODO: implement more specializations to be at least on par with + // std::fill_n + 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(__value), __n); + return __first + __n; + } + else if constexpr (is_scalar_v<_Tp>) + { + const auto __tmp = __value; + for (; __n > 0; --__n, (void)++__first) + *__first = __tmp; + return __first; + } + else + { + for (; __n > 0; --__n, (void)++__first) + *__first = __value; + return __first; + } + } + + template _Out, sentinel_for<_Out> _Sent> + constexpr _Out + fill(_Out __first, _Sent __last, const _Tp& __value) + { + // TODO: implement more specializations to be at least on par with + // std::fill + if constexpr (sized_sentinel_for<_Sent, _Out>) + { + const auto __len = __last - __first; + return ranges::fill_n(__first, __len, __value); + } + else if constexpr (is_scalar_v<_Tp>) + { + const auto __tmp = __value; + for (; __first != __last; ++__first) + *__first = __tmp; + return __first; + } + else + { + for (; __first != __last; ++__first) + *__first = __value; + return __first; + } + } + + template _Range> + constexpr safe_iterator_t<_Range> + fill(_Range&& __r, const _Tp& __value) + { + return ranges::fill(ranges::begin(__r), ranges::end(__r), __value); + } +} +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std +#endif // concepts +#endif // C++20 +#endif // _RANGES_ALGOBASE_H -- 2.30.2