From patchwork Wed Feb 12 20:41:06 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1237078 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-519433-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha1 header.s=default header.b=fyTkjn5H; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=UKmwzz9k; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 48Hs5L5LGwz9sPK for ; Thu, 13 Feb 2020 07:42:13 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:mime-version:content-type :content-transfer-encoding; q=dns; s=default; b=X+W2X5TDk2YAPEsX Aa9gpjLVSoU5lBNEgD/CpW+APhBhlUb8WIU1U1ubsvg8BavzSc17RcJ8xw/Z3KNV idQimDKStag231F/PkEiGsVpm3ZPQpSCkDp9bnqvgu2NOQwJ6qOo6O8HGPm0o0ob aZJ6eS2DwRRW9DHe0wYjBNx9/TY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:mime-version:content-type :content-transfer-encoding; s=default; bh=TXUy+r4Ic1up0HyHylHO6g SJlWo=; b=fyTkjn5HmY5EVsjbSUARe4QKI0a6Z7AaZcdbefgRjWQGyTxOnymoxu r0cjFNdoIqvJFeYU9nw+M0ArrXG/c3MmhdOR0gVCMtW8XgPPpW691JRSTReoBWx1 JBoZ2NHKe2DQyJPsAqbdbEZs1cyNazg10DqK02KNVO/0vwsQ6fxFQ= Received: (qmail 101781 invoked by alias); 12 Feb 2020 20:42:02 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 101767 invoked by uid 89); 12 Feb 2020 20:42:01 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-24.2 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 spammy= X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-2.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (205.139.110.61) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 12 Feb 2020 20:41:56 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1581540114; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=yARbDoNmLsIjUPvwxoU/Y0LXWk0u53dBmrj729RKFvk=; b=UKmwzz9k4E+Woil5R11Kq0R8eGGEPuKWlh5YfsfDrvU1KVJbxb1r8bxSXulTcCN9lmf/Rp VEUgBVNhuzzYv0GNIWCGmlgyo8z7qjFpiQ1Kc085W5I7QoVIlSi4LewQlPhiZjFJQXwqIF M83X6/IymF9Su7UrK0wKutnUWMLP1uM= Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-164-XDQ1wP0ROBuKtlGCRWrqdw-1; Wed, 12 Feb 2020 15:41:49 -0500 Received: by mail-qk1-f200.google.com with SMTP id d134so2214466qkc.0 for ; Wed, 12 Feb 2020 12:41:49 -0800 (PST) Received: from localhost.localdomain (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id n32sm161397qtk.66.2020.02.12.12.41.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 12 Feb 2020 12:41:46 -0800 (PST) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, jwakely@redhat.com, Patrick Palka Subject: [PATCH 1/2] libstdc++: Move some ranges algos to a new header Date: Wed, 12 Feb 2020 15:41:06 -0500 Message-Id: <20200212204107.4124217-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-IsSubscribed: yes 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/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 ++++++++++++++++++++ 4 files changed, 559 insertions(+), 507 deletions(-) create mode 100644 libstdc++-v3/include/bits/ranges_algobase.h 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