From ef45724acd03ef3e1ab61a4e4f42287cba7f66c4 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 4 Jul 2018 21:15:01 +0100 Subject: [PATCH] P0646R1 Improving the Return Value of Erase-Like Algorithms I In C++2a the remove, remove_if and unique members of std::list and std::forward_list have been changed to return the number of elements removed. This is an ABI change for the remove members and the non-template unique members, so an abi-tag is used to give those symbols new mangled names in C++2a mode. For the function templates the return type is part of the mangled name so no abi-tag is needed. * include/bits/forward_list.h (__cpp_lib_list_remove_return_type): Define. (forward_list::__remove_return_type): Define typedef as size_type or void, according to __cplusplus value. (_GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG): Define macro as abi-tag or empty, according to __cplusplus value. (forward_list::remove, forward_list::unique): Use typedef and macro to change return type and add abi-tag for C++2a. (forward_list::remove_if, forward_list::unique): Use typedef to change return type for C++2a. * include/bits/forward_list.tcc (_GLIBCXX20_ONLY): Define macro. (forward_list::remove, forward_list::remove_if) (forward_list::unique): Return number of removed elements for C++2a. * include/bits/list.tcc (_GLIBCXX20_ONLY): Define macro. (list::remove, list::unique, list::remove_if) (list::unique): Return number of removed elements for C++2a. * include/bits/stl_list.h (__cpp_lib_list_remove_return_type): Define. (list::__remove_return_type): Define typedef as size_type or void, according to __cplusplus value. (_GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG): Define macro as abi-tag or empty, according to __cplusplus value. (list::remove, list::unique): Use typedef and macro to change return type and add abi-tag for C++2a. (list::remove_if, list::unique): Use typedef to change return type for C++2a. * include/std/version (__cpp_lib_list_remove_return_type): Define. * testsuite/23_containers/forward_list/operations/ remove_cxx20_return.cc: New. * testsuite/23_containers/forward_list/operations/ unique_cxx20_return.cc: New. From-SVN: r262423 --- libstdc++-v3/ChangeLog | 34 ++++++++++ libstdc++-v3/include/bits/forward_list.h | 26 ++++++-- libstdc++-v3/include/bits/forward_list.tcc | 44 ++++++++++--- libstdc++-v3/include/bits/list.tcc | 53 +++++++++++---- libstdc++-v3/include/bits/stl_list.h | 24 +++++-- libstdc++-v3/include/std/version | 1 + .../operations/remove_cxx20_return.cc | 66 +++++++++++++++++++ .../operations/unique_cxx20_return.cc | 55 ++++++++++++++++ .../list/operations/remove_cxx20_return.cc | 66 +++++++++++++++++++ .../list/operations/unique_cxx20_return.cc | 55 ++++++++++++++++ 10 files changed, 394 insertions(+), 30 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/forward_list/operations/remove_cxx20_return.cc create mode 100644 libstdc++-v3/testsuite/23_containers/forward_list/operations/unique_cxx20_return.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/operations/remove_cxx20_return.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/operations/unique_cxx20_return.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 0f46565a3eb..511a42ed9e6 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,39 @@ 2018-07-04 Jonathan Wakely + P0646R1 Improving the Return Value of Erase-Like Algorithms I + * include/bits/forward_list.h (__cpp_lib_list_remove_return_type): + Define. + (forward_list::__remove_return_type): Define typedef as size_type or + void, according to __cplusplus value. + (_GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG): Define macro as abi-tag or + empty, according to __cplusplus value. + (forward_list::remove, forward_list::unique): Use typedef and macro + to change return type and add abi-tag for C++2a. + (forward_list::remove_if, forward_list::unique): Use + typedef to change return type for C++2a. + * include/bits/forward_list.tcc (_GLIBCXX20_ONLY): Define macro. + (forward_list::remove, forward_list::remove_if) + (forward_list::unique): Return number of removed elements + for C++2a. + * include/bits/list.tcc (_GLIBCXX20_ONLY): Define macro. + (list::remove, list::unique, list::remove_if) + (list::unique): Return number of removed elements + for C++2a. + * include/bits/stl_list.h (__cpp_lib_list_remove_return_type): Define. + (list::__remove_return_type): Define typedef as size_type or + void, according to __cplusplus value. + (_GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG): Define macro as abi-tag or + empty, according to __cplusplus value. + (list::remove, list::unique): Use typedef and macro to change return + type and add abi-tag for C++2a. + (list::remove_if, list::unique): Use + typedef to change return type for C++2a. + * include/std/version (__cpp_lib_list_remove_return_type): Define. + * testsuite/23_containers/forward_list/operations/ + remove_cxx20_return.cc: New. + * testsuite/23_containers/forward_list/operations/ + unique_cxx20_return.cc: New. + P0458R2 Checking for Existence of an Element in Associative Containers * include/bits/stl_map.h (map::contains): Add for C++2a. * include/bits/stl_multimap.h (multimap::contains): Likewise. diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h index 8c4c074e454..84a4ad4d5dc 100644 --- a/libstdc++-v3/include/bits/forward_list.h +++ b/libstdc++-v3/include/bits/forward_list.h @@ -1156,6 +1156,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _M_splice_after(__pos, __before, __last); } // @} + private: +#if __cplusplus > 201703L +# define __cpp_lib_list_remove_return_type 201806L + using __remove_return_type = size_type; +# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \ + __attribute__((__abi_tag__("__cxx20"))) +#else + using __remove_return_type = void; +# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG +#endif + public: + /** * @brief Remove all elements equal to value. * @param __val The value to remove. @@ -1167,7 +1179,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * touched in any way. Managing the pointer is the user's * responsibility. */ - void + _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG + __remove_return_type remove(const _Tp& __val); /** @@ -1182,7 +1195,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * responsibility. */ template - void + __remove_return_type remove_if(_Pred __pred); /** @@ -1195,9 +1208,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * the pointed-to memory is not touched in any way. Managing * the pointer is the user's responsibility. */ - void + _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG + __remove_return_type unique() - { unique(std::equal_to<_Tp>()); } + { return unique(std::equal_to<_Tp>()); } + +#undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG /** * @brief Remove consecutive elements satisfying a predicate. @@ -1212,7 +1228,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Managing the pointer is the user's responsibility. */ template - void + __remove_return_type unique(_BinPred __binary_pred); /** diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc index b41fbbb52f2..8a62a5ee748 100644 --- a/libstdc++-v3/include/bits/forward_list.tcc +++ b/libstdc++-v3/include/bits/forward_list.tcc @@ -278,11 +278,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER return iterator(const_cast<_Node_base*>(__pos._M_node)); } +#if __cplusplus > 201703L +# define _GLIBCXX20_ONLY(__expr) __expr +#else +# define _GLIBCXX20_ONLY(__expr) +#endif + template - void + auto forward_list<_Tp, _Alloc>:: - remove(const _Tp& __val) + remove(const _Tp& __val) -> __remove_return_type { + size_type __removed __attribute__((__unused__)) = 0; _Node_base* __curr = &this->_M_impl._M_head; _Node_base* __extra = nullptr; @@ -293,6 +300,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (__tmp->_M_valptr() != std::__addressof(__val)) { this->_M_erase_after(__curr); + _GLIBCXX20_ONLY( __removed++ ); continue; } else @@ -302,46 +310,62 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } if (__extra) - this->_M_erase_after(__extra); + { + this->_M_erase_after(__extra); + _GLIBCXX20_ONLY( __removed++ ); + } + return _GLIBCXX20_ONLY( __removed ); } template template - void + auto forward_list<_Tp, _Alloc>:: - remove_if(_Pred __pred) + remove_if(_Pred __pred) -> __remove_return_type { + size_type __removed __attribute__((__unused__)) = 0; _Node_base* __curr = &this->_M_impl._M_head; while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next)) { if (__pred(*__tmp->_M_valptr())) - this->_M_erase_after(__curr); + { + this->_M_erase_after(__curr); + _GLIBCXX20_ONLY( __removed++ ); + } else __curr = __curr->_M_next; } + return _GLIBCXX20_ONLY( __removed ); } template template - void + auto forward_list<_Tp, _Alloc>:: - unique(_BinPred __binary_pred) + unique(_BinPred __binary_pred) -> __remove_return_type { iterator __first = begin(); iterator __last = end(); if (__first == __last) - return; + return _GLIBCXX20_ONLY(0); + size_type __removed __attribute__((__unused__)) = 0; iterator __next = __first; while (++__next != __last) { if (__binary_pred(*__first, *__next)) - erase_after(__first); + { + erase_after(__first); + _GLIBCXX20_ONLY( __removed++ ); + } else __first = __next; __next = __first; } + return _GLIBCXX20_ONLY( __removed ); } +#undef _GLIBCXX20_ONLY + template template void diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index e90d9574cd2..cdd95527ef5 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -320,11 +320,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER insert(__last1, __first2, __last2); } +#if __cplusplus > 201703L +# define _GLIBCXX20_ONLY(__expr) __expr +#else +# define _GLIBCXX20_ONLY(__expr) +#endif + template - void + typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>:: remove(const value_type& __value) { + size_type __removed __attribute__((__unused__)) = 0; iterator __first = begin(); iterator __last = end(); iterator __extra = __last; @@ -338,34 +345,46 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // 526. Is it undefined if a function in the standard changes // in parameters? if (std::__addressof(*__first) != std::__addressof(__value)) - _M_erase(__first); + { + _M_erase(__first); + _GLIBCXX20_ONLY( __removed++ ); + } else __extra = __first; } __first = __next; } if (__extra != __last) - _M_erase(__extra); + { + _M_erase(__extra); + _GLIBCXX20_ONLY( __removed++ ); + } + return _GLIBCXX20_ONLY( __removed ); } template - void + typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>:: unique() { iterator __first = begin(); iterator __last = end(); if (__first == __last) - return; + return _GLIBCXX20_ONLY( 0 ); + size_type __removed __attribute__((__unused__)) = 0; iterator __next = __first; while (++__next != __last) { if (*__first == *__next) - _M_erase(__next); + { + _M_erase(__next); + _GLIBCXX20_ONLY( __removed++ ); + } else __first = __next; __next = __first; } + return _GLIBCXX20_ONLY( __removed ); } template @@ -510,10 +529,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template template - void + typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>:: remove_if(_Predicate __pred) { + size_type __removed __attribute__((__unused__)) = 0; iterator __first = begin(); iterator __last = end(); while (__first != __last) @@ -521,32 +541,43 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator __next = __first; ++__next; if (__pred(*__first)) - _M_erase(__first); + { + _M_erase(__first); + _GLIBCXX20_ONLY( __removed++ ); + } __first = __next; } + return _GLIBCXX20_ONLY( __removed ); } template template - void + typename list<_Tp, _Alloc>::__remove_return_type list<_Tp, _Alloc>:: unique(_BinaryPredicate __binary_pred) { iterator __first = begin(); iterator __last = end(); if (__first == __last) - return; + return _GLIBCXX20_ONLY(0); + size_type __removed __attribute__((__unused__)) = 0; iterator __next = __first; while (++__next != __last) { if (__binary_pred(*__first, *__next)) - _M_erase(__next); + { + _M_erase(__next); + _GLIBCXX20_ONLY( __removed++ ); + } else __first = __next; __next = __first; } + return _GLIBCXX20_ONLY( __removed ); } +#undef _GLIBCXX20_ONLY + template template void diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index 59e056df604..47749142e0e 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -1673,6 +1673,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 { splice(__position, std::move(__x), __first, __last); } #endif + private: +#if __cplusplus > 201703L +# define __cpp_lib_list_remove_return_type 201806L + typedef size_type __remove_return_type; +# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \ + __attribute__((__abi_tag__("__cxx20"))) +#else + typedef void __remove_return_type; +# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG +#endif + public: + /** * @brief Remove all elements equal to value. * @param __value The value to remove. @@ -1684,7 +1696,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 * touched in any way. Managing the pointer is the user's * responsibility. */ - void + _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG + __remove_return_type remove(const _Tp& __value); /** @@ -1699,7 +1712,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 * responsibility. */ template - void + __remove_return_type remove_if(_Predicate); /** @@ -1712,7 +1725,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 * the pointed-to memory is not touched in any way. Managing * the pointer is the user's responsibility. */ - void + _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG + __remove_return_type unique(); /** @@ -1728,9 +1742,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 * Managing the pointer is the user's responsibility. */ template - void + __remove_return_type unique(_BinaryPredicate); +#undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG + /** * @brief Merge sorted lists. * @param __x Sorted list to merge. diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version index 08036ff63f2..a70c73fd12b 100644 --- a/libstdc++-v3/include/std/version +++ b/libstdc++-v3/include/std/version @@ -105,6 +105,7 @@ #define __cpp_lib_is_swappable 201603 #define __cpp_lib_launder 201606 #define __cpp_lib_lcm 201606 +#define __cpp_lib_list_remove_return_type 201806L #define __cpp_lib_logical_traits 201510 #define __cpp_lib_make_from_tuple 201606 #define __cpp_lib_map_insertion 201411 diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/remove_cxx20_return.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/remove_cxx20_return.cc new file mode 100644 index 00000000000..9b46817078e --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/remove_cxx20_return.cc @@ -0,0 +1,66 @@ +// Copyright (C) 2018 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=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +using test_type = std::forward_list; + +void +test01() +{ + test_type x{1, 2, 3, 4, 3, 2, 1}; + static_assert(std::is_same_v); + test_type::size_type r = x.remove(0); + VERIFY( r == 0 ); + r = x.remove(1); + VERIFY( r == 2 ); + r = x.remove(1); + VERIFY( r == 0 ); + r = x.remove(4); + VERIFY( r == 1 ); +} + +void +test02() +{ + int i = 0; + auto pred = [&i](int val) { return val == i; }; + test_type x{1, 2, 3, 4, 3, 2, 1}; + static_assert(std::is_same_v); + test_type::size_type r = x.remove_if(pred); + VERIFY( r == 0 ); + i = 1; + r = x.remove_if(pred); + VERIFY( r == 2 ); + r = x.remove_if(pred); + VERIFY( r == 0 ); + i = 4; + r = x.remove_if(pred); + VERIFY( r == 1 ); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/unique_cxx20_return.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/unique_cxx20_return.cc new file mode 100644 index 00000000000..066330c4148 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/unique_cxx20_return.cc @@ -0,0 +1,55 @@ +// Copyright (C) 2018 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=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +using test_type = std::forward_list; + +void +test01() +{ + test_type x{1, 2, 2, 4, 4, 2, 1}; + static_assert(std::is_same_v); + test_type::size_type r = x.unique(); + VERIFY( r == 2 ); + r = x.unique(); + VERIFY( r == 0 ); +} + +void +test02() +{ + auto pred = [](int val, int prev) { return val == prev; }; + test_type x{1, 2, 2, 4, 4, 2, 1}; + static_assert(std::is_same_v); + test_type::size_type r = x.unique(pred); + VERIFY( r == 2 ); + r = x.unique(pred); + VERIFY( r == 0 ); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/remove_cxx20_return.cc b/libstdc++-v3/testsuite/23_containers/list/operations/remove_cxx20_return.cc new file mode 100644 index 00000000000..290646106cf --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/operations/remove_cxx20_return.cc @@ -0,0 +1,66 @@ +// Copyright (C) 2018 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=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +using test_type = std::list; + +void +test01() +{ + test_type x{1, 2, 3, 4, 3, 2, 1}; + static_assert(std::is_same_v); + test_type::size_type r = x.remove(0); + VERIFY( r == 0 ); + r = x.remove(1); + VERIFY( r == 2 ); + r = x.remove(1); + VERIFY( r == 0 ); + r = x.remove(4); + VERIFY( r == 1 ); +} + +void +test02() +{ + int i = 0; + auto pred = [&i](int val) { return val == i; }; + test_type x{1, 2, 3, 4, 3, 2, 1}; + static_assert(std::is_same_v); + test_type::size_type r = x.remove_if(pred); + VERIFY( r == 0 ); + i = 1; + r = x.remove_if(pred); + VERIFY( r == 2 ); + r = x.remove_if(pred); + VERIFY( r == 0 ); + i = 4; + r = x.remove_if(pred); + VERIFY( r == 1 ); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/unique_cxx20_return.cc b/libstdc++-v3/testsuite/23_containers/list/operations/unique_cxx20_return.cc new file mode 100644 index 00000000000..90d6dd155ff --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/operations/unique_cxx20_return.cc @@ -0,0 +1,55 @@ +// Copyright (C) 2018 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=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +using test_type = std::list; + +void +test01() +{ + test_type x{1, 2, 2, 4, 4, 2, 1}; + static_assert(std::is_same_v); + test_type::size_type r = x.unique(); + VERIFY( r == 2 ); + r = x.unique(); + VERIFY( r == 0 ); +} + +void +test02() +{ + auto pred = [](int val, int prev) { return val == prev; }; + test_type x{1, 2, 2, 4, 4, 2, 1}; + static_assert(std::is_same_v); + test_type::size_type r = x.unique(pred); + VERIFY( r == 2 ); + r = x.unique(pred); + VERIFY( r == 0 ); +} + +int +main() +{ + test01(); + test02(); +} -- 2.30.2