From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 113866 invoked by alias); 25 Feb 2020 02:20:36 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 113849 invoked by uid 89); 25 Feb 2020 02:20:35 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.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) (207.211.31.81) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 25 Feb 2020 02:20:29 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1582597228; 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: in-reply-to:in-reply-to:references:references; bh=vqn3013Vkhh7JDnzAq2ZRdANgMNiCy0bubJjcYrMEBI=; b=DKdsrL1Sdw2oXCvUjYLuRc8R6pDYS7tiof6gHnYQa1RWmY3nyJ3LdR0vblL+XPvznQWS1r K1PliYSWsArs+1QMfe413M+zv9Hvr79+Y+6eg+UxF1otAcnJHfkolunYKyuMWjAT3PBbT4 uZL1Mxi50fTFZBK+za1a8TKtWH5pYE0= Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-273---lZuiPFPz-pB5ltMlWqug-1; Mon, 24 Feb 2020 21:20:22 -0500 Received: by mail-qk1-f197.google.com with SMTP id h6so13038532qkj.14 for ; Mon, 24 Feb 2020 18:20:22 -0800 (PST) Return-Path: Received: from [192.168.1.130] (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id b22sm6718715qkk.20.2020.02.24.18.20.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 24 Feb 2020 18:20:19 -0800 (PST) From: Patrick Palka Date: Tue, 25 Feb 2020 02:20:00 -0000 To: Patrick Palka cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org, jwakely@redhat.com Subject: Re: [PATCH] libstdc++: Implement integer-class types as defined in [iterator.concept.winc] In-Reply-To: <20200224201623.765972-1-ppalka@redhat.com> Message-ID: References: <20200224201623.765972-1-ppalka@redhat.com> User-Agent: Alpine 2.22 (DEB 395 2020-01-19) MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2020-02/txt/msg01358.txt.bz2 On Mon, 24 Feb 2020, Patrick Palka wrote: > This implements signed and unsigned integer-class types, whose width is o= ne bit > larger than the widest native signed and unsigned integral type respectiv= ely. > In our case this is either __int128 and unsigned __int128, or long long a= nd > unsigned long long. >=20 > Internally, the two integer-class types are represented as a largest nati= ve > unsigned integral type plus one extra bit. The signed integer-class type= is > represented in two's complement form with the extra bit acting as the sig= n bit. >=20 > libstdc++-v3/ChangeLog: >=20 > * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): > Remove definition, replace with forward declaration of class > __max_diff_type. > (ranges::__detail::__max_size_type): Remove definition, replace with > forward declaration of class __max_size_type. > (__detail::__is_integer_like): Accept __int128 and unsigned __int128. > (__detail::__is_signed_integer_like): Accept __int128. > * include/bits/range_access.h (__detail::__max_size_type): New class. > (__detail::__max_diff_type): New class. > (__detail::__max_size_type::__max_size_type): Define this constructor > out-of-line to break the cycle. > (__detail::__to_unsigned_like): New function. > (numeric_limits<__detail::__max_size_type>): New explicit specialization. > (numeric_limits<__detail::__max_diff_type>): New explicit specialization. > * testsuite/std/ranges/iota/differenc_type.cc: New test. Here's v2 of the patch that splits out __max_size_type and __max_diff_type into a dedicated header, along with other misc improvements and fixes. -- >8 -- Subject: [PATCH] libstdc++: Implement integer-class types as defined in [iterator.concept.winc] This implements signed and unsigned integer-class types, whose width is one= bit larger than the widest native signed and unsigned integral type respectivel= y. In our case this is either __int128 and unsigned __int128, or long long and unsigned long long. Internally, the two integer-class types are represented as a largest native unsigned integral type plus one extra bit. The signed integer-class type is represented in two's complement form with the extra bit acting as the sign = bit. libstdc++-v3/ChangeLog: * include/Makefile.am (bits_headers): Add new header . * include/Makefile.in: Regenerate. * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): Remove definition, replace with forward declaration of class __max_diff_type. (ranges::__detail::__max_size_type): Remove definition, replace with forward declaration of class __max_size_type. (__detail::__is_integer_like): Accept __int128 and unsigned __int128. (__detail::__is_signed_integer_like): Accept __int128. * include/bits/max_size_type.h: New header. * include/bits/range_access.h: Include . (__detail::__to_unsigned_like): Two new overloads. * testsuite/std/ranges/iota/difference_type.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/iterator_concepts.h | 15 +- libstdc++-v3/include/bits/max_size_type.h | 736 ++++++++++++++++++ libstdc++-v3/include/bits/range_access.h | 11 + .../std/ranges/iota/difference_type.cc | 379 +++++++++ 6 files changed, 1136 insertions(+), 7 deletions(-) create mode 100644 libstdc++-v3/include/bits/max_size_type.h create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/difference_type.= cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefi= le.am index 80aeb3f8959..a1460b98247 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -144,6 +144,7 @@ bits_headers =3D \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefi= le.in index eb437ad8d8d..dd317fa0178 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -489,6 +489,7 @@ bits_headers =3D \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/i= nclude/bits/iterator_concepts.h index 08e622259b4..6eff0b82feb 100644 --- a/libstdc++-v3/include/bits/iterator_concepts.h +++ b/libstdc++-v3/include/bits/iterator_concepts.h @@ -482,20 +482,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION =20 namespace ranges::__detail { -#if __SIZEOF_INT128__ - using __max_diff_type =3D __int128; - using __max_size_type =3D unsigned __int128; -#else - using __max_diff_type =3D long long; - using __max_size_type =3D unsigned long long; -#endif + class __max_diff_type; + class __max_size_type; =20 template concept __is_integer_like =3D integral<_Tp> +#if __SIZEOF_INT128__ + || same_as<_Tp, __int128> || same_as<_Tp, unsigned __int128> +#endif || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; =20 template concept __is_signed_integer_like =3D signed_integral<_Tp> +#if __SIZEOF_INT128__ + || same_as<_Tp, __int128> +#endif || same_as<_Tp, __max_diff_type>; =20 } // namespace ranges::__detail diff --git a/libstdc++-v3/include/bits/max_size_type.h b/libstdc++-v3/inclu= de/bits/max_size_type.h new file mode 100644 index 00000000000..8797645c70d --- /dev/null +++ b/libstdc++-v3/include/bits/max_size_type.h @@ -0,0 +1,736 @@ +// -*- C++ -*- + +// Copyright (C) 2019-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/max_size_type.h. + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{iterator} + */ + +#ifndef _GLIBCXX_MAX_SIZE_TYPE_H +#define _GLIBCXX_MAX_SIZE_TYPE_H 1 + +#pragma GCC system_header + +#if __cplusplus > 201703L && __cpp_lib_concepts +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + +template + struct numeric_limits; + +// Unsigned and signed integer-class types (as per [iterator.concept.winc]= ) that +// are one bit wider than the largest native integer type. + +namespace ranges +{ + namespace __detail + { + class __max_size_type + { + public: + __max_size_type() =3D default; + + template + constexpr + __max_size_type(_Tp __i) noexcept + : _M_val(__i), _M_msb(__i < 0) + { } + + constexpr explicit + __max_size_type(const __max_diff_type& __d) noexcept; + + template + constexpr explicit operator _Tp() const noexcept + { return _M_val; } + + constexpr explicit + operator bool() const noexcept + { return _M_val !=3D 0 || _M_msb !=3D 0; } + + constexpr __max_size_type + operator+() const noexcept + { return *this; } + + constexpr __max_size_type + operator~() const noexcept + { return __max_size_type{~_M_val, !_M_msb}; } + + constexpr __max_size_type + operator-() const noexcept + { return operator~() + 1; } + + constexpr __max_size_type& + operator+=3D(const __max_size_type& __r) noexcept + { + const auto __sum =3D _M_val + __r._M_val; + const bool __overflow =3D (__sum < _M_val); + _M_msb =3D _M_msb ^ __r._M_msb ^ __overflow; + _M_val =3D __sum; + return *this; + } + + constexpr __max_size_type& + operator-=3D(const __max_size_type& __r) noexcept + { return *this +=3D -__r; } + + constexpr __max_size_type& + operator*=3D(__max_size_type __r) noexcept + { + const bool __lsb =3D _M_val & 1; + const bool __rlsb =3D __r._M_val & 1; + + constexpr auto __threshold =3D __rep(1) << (__rep_bits / 2 - 1); + if (!_M_msb && !__r._M_msb + && _M_val < __threshold && __r._M_val < __threshold) [[likely]] + _M_val =3D _M_val * __r._M_val; + else + { + *this >>=3D 1; + __r >>=3D 1; + _M_val =3D (2 * _M_val * __r._M_val + + _M_val * __rlsb + __r._M_val * __lsb); + *this <<=3D 1; + *this +=3D __rlsb * __lsb; + } + + return *this; + } + + constexpr __max_size_type& + operator/=3D(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r !=3D 0); + + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val /=3D __r._M_val; + else if (_M_msb && __r._M_msb) + { + _M_val =3D (_M_val >=3D __r._M_val); + _M_msb =3D 0; + } + else if (!_M_msb && __r._M_msb) + _M_val =3D 0; + else if (_M_msb && !__r._M_msb) + { + const auto __orig =3D *this; + *this >>=3D 1; + _M_val /=3D __r._M_val; + *this <<=3D 1; + if (__orig - *this * __r >=3D __r) + ++_M_val; + } + return *this; + } + + constexpr __max_size_type& + operator%=3D(const __max_size_type& __r) noexcept + { + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val %=3D __r._M_val; + else + *this -=3D (*this / __r) * __r; + return *this; + } + + constexpr __max_size_type& + operator<<=3D(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <=3D __rep_bits); + if (__r =3D=3D 0) + return *this; + if (_M_val & (__rep(1) << (__rep_bits - __r._M_val))) + _M_msb =3D 1; + else + _M_msb =3D 0; + if (__r._M_val =3D=3D __rep_bits) [[unlikely]] + _M_val =3D 0; + else + _M_val <<=3D __r._M_val; + return *this; + } + + constexpr __max_size_type& + operator>>=3D(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <=3D __rep_bits); + if (__r =3D=3D 0) + return *this; + if (__r._M_val =3D=3D __rep_bits) [[unlikely]] + _M_val =3D 0; + else + _M_val >>=3D __r._M_val; + if (_M_msb) [[unlikely]] + { + _M_val |=3D __rep(1) << (__rep_bits - __r._M_val); + _M_msb =3D 0; + } + return *this; + } + + constexpr __max_size_type& + operator&=3D(const __max_size_type& __r) noexcept + { + _M_val &=3D __r._M_val; + _M_msb &=3D __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator|=3D(const __max_size_type& __r) noexcept + { + _M_val |=3D __r._M_val; + _M_msb |=3D __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator^=3D(const __max_size_type& __r) noexcept + { + _M_val ^=3D __r._M_val; + _M_msb ^=3D __r._M_msb; + return *this; + } + + template + friend constexpr _Tp& + operator+=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a + b)); } + + template + friend constexpr _Tp& + operator-=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a - b)); } + + template + friend constexpr _Tp& + operator*=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a * b)); } + + template + friend constexpr _Tp& + operator/=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a / b)); } + + template + friend constexpr _Tp& + operator%=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a % b)); } + + template + friend constexpr _Tp& + operator&=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a & b)); } + + template + friend constexpr _Tp& + operator|=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a | b)); } + + template + friend constexpr _Tp& + operator^=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a ^ b)); } + + template + friend constexpr _Tp& + operator<<=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a << b)); } + + template + friend constexpr _Tp& + operator>>=3D(_Tp& a, const __max_size_type& b) noexcept + { return (a =3D static_cast<_Tp>(a >> b)); } + + friend constexpr __max_size_type + operator+(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l +=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator-(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l -=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator*(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l *=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator/(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l /=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator%(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l %=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator<<(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l <<=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator>>(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l >>=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator&(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l &=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator|(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l |=3D __r; + return __l; + } + + friend constexpr __max_size_type + operator^(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l ^=3D __r; + return __l; + } + + friend constexpr bool + operator=3D=3D(const __max_size_type& __l, const __max_size_type& __= r) noexcept + { return __l._M_val =3D=3D __r._M_val && __l._M_msb =3D=3D __r._M_ms= b; } + + friend constexpr bool + operator!=3D(const __max_size_type& __l, const __max_size_type& __r)= noexcept + { return !(__l =3D=3D __r); } + + friend constexpr bool + operator<(const __max_size_type& __l, const __max_size_type& __r) no= except + { + if (__l._M_msb =3D=3D __r._M_msb) + return __l._M_val < __r._M_val; + else + return __r._M_msb; + } + + friend constexpr bool + operator>(const __max_size_type& __l, const __max_size_type& __r) no= except + { return __r < __l; } + + friend constexpr bool + operator<=3D(const __max_size_type& __l, const __max_size_type& __r)= noexcept + { return !(__l > __r); } + + friend constexpr bool + operator>=3D(const __max_size_type& __l, const __max_size_type& __r)= noexcept + { return __r <=3D __l; } + +#if __SIZEOF_INT128__ + using __rep =3D unsigned __int128; +#else + using __rep =3D unsigned long long; +#endif + static constexpr size_t __rep_bits =3D sizeof(__rep) * __CHAR_BIT__; + private: + __rep _M_val =3D 0; + unsigned _M_msb:1 =3D 0; + + constexpr explicit + __max_size_type(__rep __val, int __msb) noexcept + : _M_val(__val), _M_msb(__msb) + { } + + friend __max_diff_type; + friend std::numeric_limits<__max_size_type>; + friend std::numeric_limits<__max_diff_type>; + }; + + // A signed integer-class type as per [iterator.concept.winc]. + class __max_diff_type + { + public: + __max_diff_type() =3D default; + + template + constexpr + __max_diff_type(_Tp __i) noexcept + : _M_rep(__i) + { } + + constexpr explicit + __max_diff_type(const __max_size_type& __d) noexcept + : _M_rep(__d) + { } + + template + constexpr explicit operator _Tp() const noexcept + { return static_cast<_Tp>(_M_rep); } + + constexpr explicit + operator bool() const noexcept + { return _M_rep !=3D 0; } + + constexpr __max_diff_type + operator+() const noexcept + { return *this; } + + constexpr __max_diff_type + operator-() const noexcept + { return __max_diff_type(-_M_rep); } + + constexpr __max_diff_type + operator~() const noexcept + { return __max_diff_type(~_M_rep); } + + constexpr __max_diff_type& + operator+=3D(const __max_diff_type& __r) noexcept + { + _M_rep +=3D __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator-=3D(const __max_diff_type& __r) noexcept + { + _M_rep -=3D __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator*=3D(const __max_diff_type& __r) noexcept + { + _M_rep *=3D __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator/=3D(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r !=3D 0); + const bool __neg =3D *this < 0; + const bool __rneg =3D __r < 0; + if (!__neg && !__rneg) + _M_rep =3D _M_rep / __r._M_rep; + else if (__neg && __rneg) + _M_rep =3D -_M_rep / -__r._M_rep; + else + _M_rep =3D -((__neg ? -_M_rep : _M_rep) + / (__rneg ? -__r._M_rep : __r._M_rep)); + return *this ; + } + + constexpr __max_diff_type& + operator%=3D(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r !=3D 0); + if (*this >=3D 0 && __r > 0) + _M_rep %=3D __r._M_rep; + else + *this -=3D (*this / __r) * __r; + return *this; + } + + constexpr __max_diff_type& + operator<<=3D(const __max_diff_type& __r) noexcept + { + _M_rep.operator<<=3D(__r._M_rep); + return *this; + } + + constexpr __max_diff_type& + operator>>=3D(const __max_diff_type& __r) noexcept + { + const auto __msb =3D _M_rep._M_msb; + _M_rep >>=3D __r._M_rep; + _M_rep._M_msb |=3D __msb; + return *this; + } + + constexpr __max_diff_type& + operator&=3D(const __max_diff_type& __r) noexcept + { + _M_rep &=3D __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator|=3D(const __max_diff_type& __r) noexcept + { + _M_rep |=3D __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator^=3D(const __max_diff_type& __r) noexcept + { + _M_rep ^=3D __r._M_rep; + return *this; + } + + template + friend constexpr _Tp& + operator+=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a + b)); } + + template + friend constexpr _Tp& + operator-=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a - b)); } + + template + friend constexpr _Tp& + operator*=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a * b)); } + + template + friend constexpr _Tp& + operator/=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a / b)); } + + template + friend constexpr _Tp& + operator%=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a % b)); } + + template + friend constexpr _Tp& + operator&=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a & b)); } + + template + friend constexpr _Tp& + operator|=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a | b)); } + + template + friend constexpr _Tp& + operator^=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a ^ b)); } + + template + friend constexpr _Tp& + operator<<=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a << b)); } + + template + friend constexpr _Tp& + operator>>=3D(_Tp& a, const __max_diff_type& b) noexcept + { return (a =3D static_cast<_Tp>(a >> b)); } + + friend constexpr __max_diff_type + operator+(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l +=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator-(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l -=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator*(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l *=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator/(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l /=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator%(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l %=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator<<(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l <<=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator>>(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l >>=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator&(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l &=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator|(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l |=3D __r; + return __l; + } + + friend constexpr __max_diff_type + operator^(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l ^=3D __r; + return __l; + } + + friend constexpr bool + operator=3D=3D(const __max_diff_type& __l, const __max_diff_type& __= r) noexcept + { return __l._M_rep =3D=3D __r._M_rep; } + + friend constexpr bool + operator!=3D(const __max_diff_type& __l, const __max_diff_type& __r)= noexcept + { return !(__l =3D=3D __r); } + + constexpr bool + operator<(const __max_diff_type& __r) const noexcept + { + const auto __lsign =3D _M_rep._M_msb; + const auto __rsign =3D __r._M_rep._M_msb; + if (__lsign ^ __rsign) + return __lsign; + else + return _M_rep < __r._M_rep; + } + + friend constexpr bool + operator>(const __max_diff_type& __l, const __max_diff_type& __r) no= except + { return __r < __l; } + + friend constexpr bool + operator<=3D(const __max_diff_type& __l, const __max_diff_type& __r)= noexcept + { return !(__r < __l); } + + friend constexpr bool + operator>=3D(const __max_diff_type& __l, const __max_diff_type& __r)= noexcept + { return !(__l < __r); } + + private: + __max_size_type _M_rep =3D 0; + + friend class __max_size_type; + }; + + constexpr + __max_size_type::__max_size_type(const __max_diff_type& __d) noexcept + : __max_size_type(__d._M_rep) + { } + + } // namespace __detail +} // namespace ranges + + template<> + struct numeric_limits + { + using _Sp =3D ranges::__detail::__max_size_type; + static constexpr bool is_specialized =3D true; + static constexpr bool is_signed =3D false; + static constexpr bool is_integer =3D true; + static constexpr bool is_exact =3D true; +#if __SIZEOF_INT128__ + static_assert(same_as<_Sp::__rep, unsigned __int128>); + static constexpr int digits =3D 129; +#else + static_assert(same_as<_Sp::__rep, unsigned long long>); + static constexpr int digits + =3D __detail::__int_limits::digits + 1; +#endif + static constexpr int digits10 + =3D static_cast(digits * 0.30102); + // =3D static_cast(digits * log10(2)) + + static constexpr _Sp + min() noexcept + { return 0; } + + static constexpr _Sp + max() noexcept + { return _Sp(static_cast<_Sp::__rep>(-1), 1); } + + static constexpr _Sp + lowest() noexcept + { return min(); } + }; + + template<> + struct numeric_limits + { + using _Dp =3D ranges::__detail::__max_diff_type; + using _Sp =3D ranges::__detail::__max_size_type; + static constexpr bool is_specialized =3D true; + static constexpr bool is_signed =3D true; + static constexpr bool is_integer =3D true; + static constexpr bool is_exact =3D true; + static constexpr int digits =3D numeric_limits<_Sp>::digits - 1; + static constexpr int digits10 =3D static_cast(digits * 0.301); + + static constexpr _Dp + min() noexcept + { return _Dp(_Sp(0, 1)); } + + static constexpr _Dp + max() noexcept + { return _Dp(_Sp(static_cast<_Sp::__rep>(-1), 0)); } + + static constexpr _Dp + lowest() noexcept + { return min(); } + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif // C++20 && library concepts +#endif // _GLIBCXX_MAX_SIZE_TYPE_H diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/includ= e/bits/range_access.h index 8b276fd6625..c814694623c 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -36,6 +36,9 @@ #include #include #include +#if __cplusplus > 201703L +#include +#endif =20 namespace std _GLIBCXX_VISIBILITY(default) { @@ -351,6 +354,14 @@ namespace ranges =20 namespace __detail { + constexpr __max_size_type + __to_unsigned_like(__max_size_type __t) noexcept + { return __t; } + + constexpr __max_size_type + __to_unsigned_like(__max_diff_type __t) noexcept + { return __max_size_type(__t); } + template constexpr make_unsigned_t<_Tp> __to_unsigned_like(_Tp __t) noexcept diff --git a/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc b/li= bstdc++-v3/testsuite/std/ranges/iota/difference_type.cc new file mode 100644 index 00000000000..c37c88467bb --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc @@ -0,0 +1,379 @@ +// 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. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=3Dgnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include +#include + +void +test01() +{ + using I =3D unsigned long long; + auto imax =3D std::numeric_limits::max(); + std::ranges::iota_view i(0, imax); + auto begin =3D i.begin(); + static_assert( std::input_or_output_iterator ); + auto size =3D std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size =3D=3D imax ); +} + +void +test02() +{ +#if __SIZEOF_INT128__ + using I =3D unsigned __int128; + auto imax =3D std::numeric_limits::max(); + std::ranges::iota_view i(0, imax); + auto begin =3D i.begin(); + static_assert( std::input_or_output_iterator ); + auto size =3D std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size =3D=3D imax ); +#endif +} + +// The following are correctness tests for the arithmetic operations on +// __max_size_type and __max_diff_type. + +using max_size_t =3D std::ranges::__detail::__max_size_type; +using max_diff_t =3D std::ranges::__detail::__max_diff_type; +using rep_t =3D max_size_t::__rep; + +static_assert(sizeof(max_size_t) =3D=3D sizeof(max_diff_t)); + +static_assert(std::regular); +static_assert(std::totally_ordered); + +static_assert(std::regular); +static_assert(std::totally_ordered); + +void +test03() +{ + static_assert(max_size_t(7) % 3 =3D=3D 1); + static_assert(max_size_t(7) % 4 =3D=3D 3); + + static_assert(-max_diff_t(1) =3D=3D max_diff_t(-1)); + static_assert(max_diff_t(3) % 2 =3D=3D 1); + static_assert(max_diff_t(-3) / 2 =3D=3D -1); + static_assert(max_diff_t(-3) % 2 =3D=3D -1); + static_assert(max_diff_t(3) % -2 =3D=3D 1); + static_assert(max_diff_t(-3) << 1 =3D=3D -6); + static_assert(max_diff_t(-3) >> 1 =3D=3D -2); + static_assert(max_diff_t(3) >> 1 =3D=3D 1); + static_assert(max_diff_t(3) >> 2 =3D=3D 0); + + static_assert(max_diff_t(-5) / 3 =3D=3D -1); + static_assert(max_diff_t(5) / -3 =3D=3D -1); + static_assert(max_diff_t(-5) / -3 =3D=3D 1); + static_assert(max_diff_t(5) / 3 =3D=3D 1); + + static_assert(max_diff_t(-6) / 3 =3D=3D -2); + static_assert(max_diff_t(6) / -3 =3D=3D -2); + static_assert(max_diff_t(-6) / -3 =3D=3D 2); + static_assert(max_diff_t(6) / 3 =3D=3D 2); + + static_assert(~max_size_t(-3) =3D=3D 2); + static_assert(~max_diff_t(-3) =3D=3D 2); + + static_assert(max_diff_t(1) < max_diff_t(3)); + static_assert(max_diff_t(-1) < max_diff_t(3)); + static_assert(max_diff_t(1) > max_diff_t(-3)); + static_assert(max_diff_t(-1) > max_diff_t(-3)); + + constexpr max_size_t mu =3D std::numeric_limits::max(); + + static_assert(max_diff_t(mu)/-1 =3D=3D -max_diff_t(mu)); + static_assert(-max_diff_t(mu)/1 =3D=3D -max_diff_t(mu)); + static_assert(max_diff_t(mu)>>1 =3D=3D max_diff_t(mu)/2); + static_assert(-max_diff_t(mu+1) =3D=3D max_diff_t(mu+1)); + static_assert(-(mu+1) =3D=3D mu+1); + static_assert((mu+1)<<1 =3D=3D 0); + static_assert(max_diff_t(mu+1)<<1 =3D=3D 0); + static_assert(max_diff_t(mu+1)>>1 < 0); + + static_assert(int(max_diff_t(mu+1)) =3D=3D 0); + static_assert(rep_t(max_diff_t(mu+1)) =3D=3D 0); + static_assert(int(max_diff_t(mu)) =3D=3D -1); + static_assert(rep_t(max_diff_t(mu)) =3D=3D rep_t(-1)); + + static_assert(2*mu+1 > 2*mu); + static_assert(~(2*mu+1) =3D=3D 0); + static_assert(mu/mu =3D=3D 1); + static_assert(2*mu > mu); + static_assert(2*mu-mu =3D=3D mu); + static_assert((2*mu)/mu =3D=3D 2); + static_assert((2*mu+1)/mu =3D=3D 2); + static_assert((2*mu-1)/(mu-1) =3D=3D 2); + static_assert((2*mu-1)/mu =3D=3D 1); + static_assert((2*mu+-1)/mu =3D=3D 1); + static_assert(2*mu-1 < 2*mu); + static_assert(2*mu-1 <=3D 2*mu); + static_assert(2*mu+1 > 2*mu); + static_assert(2*mu+1 >=3D 2*mu); + static_assert((2*mu)/1 =3D=3D 2*mu); + static_assert(mu/mu-1 =3D=3D 0); + static_assert(mu*0 =3D=3D 0); + static_assert((2*mu-1)*0 =3D=3D 0); + static_assert((2*mu-1)>>1 =3D=3D mu-1); + static_assert(mu+-1+1 =3D=3D mu); + static_assert(mu+1+-1 =3D=3D mu); + static_assert(mu+1); + static_assert((2*mu)/2 =3D=3D mu); + static_assert((2*mu)>>1 =3D=3D mu); + static_assert((mu<<1)>>1 =3D=3D mu); + static_assert(1/mu =3D=3D 0); + static_assert(mu/1 =3D=3D mu); + static_assert(((mu+1)|mu) =3D=3D -1); + static_assert((mu+1)+(mu+1) < mu+1); + + constexpr max_size_t ou =3D 1; + constexpr max_diff_t ns =3D -1; + + static_assert(max_size_t(ns) =3D=3D -1); + static_assert(-max_diff_t(ou) =3D=3D -1); + static_assert(-max_diff_t(-ou) =3D=3D 1); + static_assert(max_size_t(-max_diff_t(-ou)) =3D=3D 1); + static_assert(ns*ns =3D=3D max_diff_t(ou)); + static_assert(max_size_t(ns)*max_size_t(ns) =3D=3D ou); + static_assert(-max_diff_t(0) =3D=3D max_diff_t(0)); + static_assert(-ou-ou =3D=3D -2*ou); + + static_assert(int(ns) =3D=3D -1); + static_assert(rep_t(ns) =3D=3D rep_t(-1)); + + static_assert(max_size_t() =3D=3D 0); + static_assert(max_diff_t() =3D=3D 0); + + auto f =3D [] (auto a) { a /=3D a; return a; }; + static_assert(f(max_size_t(5)) =3D=3D 1); + static_assert(f(max_size_t(-5)) =3D=3D 1); + static_assert(f(max_diff_t(5)) =3D=3D 1); + + auto g =3D [] (auto a) { a >>=3D a; return a; }; + static_assert(g(max_size_t(5)) =3D=3D 0); + static_assert(g(max_diff_t(5)) =3D=3D 0); + + auto h =3D [] (auto a) { a <<=3D a; return a; }; + static_assert(h(max_size_t(3)) =3D=3D 24); + static_assert(h(max_diff_t(3)) =3D=3D 24); +} + +template +void +test04() +{ + using hw_type =3D std::conditional_t; + using max_type =3D std::conditional_t; + using shorten_type =3D std::conditional_t; + const int hw_type_bit_size =3D sizeof(hw_type) * __CHAR_BIT__; + const int limit =3D 1000; + const int log2_limit =3D 10; + static_assert((1 << log2_limit) >=3D limit); + const int min =3D (signed_p ? -limit : 0); + const int max =3D limit; + for (hw_type i =3D min; i <=3D max; i++) + { + bool ok =3D true; + if (signed_p || shorten_p) + { + ok &=3D (~i =3D=3D shorten_type(~max_type(i))); + ok &=3D (-i =3D=3D shorten_type(-max_type(i))); + } + for (hw_type j =3D min; j <=3D max; j++) + { + ok &=3D (i*j =3D=3D shorten_type(max_type(i)*j)); + ok &=3D (i+j =3D=3D shorten_type(max_type(i)+j)); + if (j !=3D 0) + { + ok &=3D (i/j =3D=3D shorten_type(max_type(i)/j)); + ok &=3D (i%j =3D=3D shorten_type(max_type(i)%j)); + } + if (signed_p || shorten_p) + ok &=3D (i-j =3D=3D shorten_type(max_type(i)-j)); + ok &=3D ((i&j) =3D=3D shorten_type(max_type(i)&j)); + ok &=3D ((i|j) =3D=3D shorten_type(max_type(i)|j)); + ok &=3D ((i^j) =3D=3D shorten_type(max_type(i)^j)); + if (j >=3D 0 && j < hw_type(hw_type_bit_size) + && (shorten_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + ok &=3D ((i>>j) =3D=3D shorten_type(max_type(i)>>j)); + ok &=3D ((i<j) =3D=3D (max_type(i) > j); + ok &=3D (i=3Dj) =3D=3D (max_type(i) >=3D j); + ok &=3D (i<=3Dj) =3D=3D (max_type(i) <=3D j); + ok &=3D (i=3D=3Dj) =3D=3D (max_type(i) =3D=3D j); + ok &=3D (i!=3Dj) =3D=3D (max_type(i) !=3D j); + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, shorten_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +template +void +test05() +{ + using hw_type =3D std::conditional_t; + using max_type =3D std::conditional_t; + using base_type =3D std::conditional_t; + constexpr int hw_type_bit_size =3D sizeof(hw_type) * __CHAR_BIT__; + constexpr int limit =3D 1000; + constexpr int log2_limit =3D 10; + static_assert((1 << log2_limit) >=3D limit); + const int min =3D (signed_p ? -limit : 0); + const int max =3D limit; + for (hw_type i =3D min; i <=3D max; i++) + { + bool ok =3D true; + base_type k; + for (hw_type j =3D min; j <=3D max; j++) + { + k =3D i; k *=3D j; + ok &=3D (k =3D=3D (max_type(i)*j)); + k =3D i; k +=3D j; + ok &=3D (k =3D=3D (max_type(i)+j)); + if (j !=3D 0) + { + k =3D i; k /=3D j; + ok &=3D (k =3D=3D (max_type(i)/j)); + k =3D i; k %=3D j; + ok &=3D (k =3D=3D (max_type(i)%j)); + } + if (signed_p) + { + k =3D i; k -=3D j; + ok &=3D (k =3D=3D (max_type(i)-j)); + } + k =3D i; k &=3D j; + ok &=3D (k =3D=3D (max_type(i)&j)); + k =3D i; k |=3D j; + ok &=3D (k =3D=3D (max_type(i)|j)); + k =3D i; k ^=3D j; + ok &=3D (k =3D=3D (max_type(i)^j)); + if (j >=3D 0 && j < hw_type(hw_type_bit_size) + && (!toggle_base_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + k =3D i; k >>=3D j; + ok &=3D (k =3D=3D (max_type(i)>>j)); + k =3D i; k <<=3D j; + ok &=3D (k =3D=3D (max_type(i)<::max(); + const int limit =3D 1000; + for (int i =3D -limit; i <=3D limit; i++) + { + VERIFY( -max_size_t(-i) =3D=3D i ); + for (int j =3D i; j <=3D limit; j++) + { + VERIFY( max_size_t(-i) * max_size_t(-j) =3D=3D i*j ); + VERIFY( max_size_t(-j) * max_size_t(-i) =3D=3D j*i ); + VERIFY( rep_t(((mu+1)+i)*((mu+1)+j)) =3D=3D rep_t(i*j) ); + VERIFY( rep_t(((mu+1)+j)*((mu+1)+i)) =3D=3D rep_t(j*i) ); + if (i >=3D 0 && j > 0) + { + auto r =3D (mu+i)-((mu+i)/j)*j; + VERIFY( r >=3D 0 && r < j ); + VERIFY( r =3D=3D (mu+i)%j ); + } + } + } +} + +using std::numeric_limits; + +static_assert(numeric_limits::is_specialized); +static_assert(!numeric_limits::is_signed); +static_assert(numeric_limits::is_integer); +static_assert(numeric_limits::is_exact); +static_assert(numeric_limits::digits + =3D=3D numeric_limits::digits + 1); +// XXX: not quite.. +static_assert(numeric_limits::digits10 + =3D=3D numeric_limits::digits10); +static_assert(numeric_limits::min() =3D=3D 0); +static_assert(numeric_limits::max() + =3D=3D max_size_t(-1)); +static_assert(numeric_limits::max() + =3D=3D 2*max_size_t(numeric_limits::max())+1); +static_assert((numeric_limits::max() + >> (numeric_limits::digits-1)) =3D=3D 1); +static_assert(numeric_limits::lowest() + =3D=3D numeric_limits::min()); + +static_assert(numeric_limits::is_specialized); +static_assert(numeric_limits::is_signed); +static_assert(numeric_limits::is_integer); +static_assert(numeric_limits::is_exact); +static_assert(numeric_limits::digits + =3D=3D numeric_limits::digits); +static_assert(numeric_limits::digits10 + =3D=3D numeric_limits::digits10); +static_assert(numeric_limits::min() + =3D=3D -max_diff_t(numeric_limits::max())-1); +static_assert(numeric_limits::max() + =3D=3D numeric_limits::max()); +static_assert(numeric_limits::lowest() + =3D=3D numeric_limits::min()); +static_assert(max_diff_t(max_size_t(1) + << (numeric_limits::digits-1)) + =3D=3D numeric_limits::min()); + +int +main() +{ + test01(); + test02(); + test03(); + + test04(); + test04(); + test04(); + test04(); + + test05(); + test05(); + test05(); + test05(); + + test06(); +} --=20 2.25.1.291.ge68e29171c