From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 92B803857C60 for ; Fri, 1 Oct 2021 19:44:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 92B803857C60 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-238-CalR1yAsOTGpgheYOgkk_w-1; Fri, 01 Oct 2021 15:44:01 -0400 X-MC-Unique: CalR1yAsOTGpgheYOgkk_w-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 46C28362F9; Fri, 1 Oct 2021 19:44:00 +0000 (UTC) Received: from localhost (unknown [10.33.36.47]) by smtp.corp.redhat.com (Postfix) with ESMTP id C131D5DF26; Fri, 1 Oct 2021 19:43:59 +0000 (UTC) Date: Fri, 1 Oct 2021 20:43:58 +0100 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Allow stateful allocators in std::list::sort [PR 66742] Message-ID: MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="c06OEOIGgWbOhHgo" Content-Disposition: inline X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 01 Oct 2021 19:44:04 -0000 --c06OEOIGgWbOhHgo Content-Type: text/plain; charset=us-ascii Content-Disposition: inline The temporary lists used by std::list::sort are default constructed, which means they use default constructed allocators. The sort operation is defined in terms of merge and splice operations, which have undefined behaviour (and abort) if the allocators do not compare equal. This means it is not possible to sort a list that uses an allocator that compares unequal to an default constructed allocator. The solution is to avoid using temporary std::list objects at all. We do not need to be able to allocate memory because no nodes are allocated, only spliced from one list to another. That means the temporary lists don't need an allocator at all, so whether it would compare equal doesn't matter. Instead of temporary std::list objects, we can just use a collection of _List_node_base objects that nodes can be spliced onto as needed. Those objects are wrapped in a _Scratch_list type that implements the splicing and merging operations used by list::sort. We also don't need to update the list size during the sort, because sorting doesn't alter the number of nodes. Although we move nodes in and out of the scratch lists, at the end of the function all nodes are back in the original std::list and the scratch lists are empty. So for the cxx11 ABI we can avoid the _M_size modifications usually done when splicing nodes. Signed-off-by: Jonathan Wakely libstdc++-v3/ChangeLog: PR libstdc++/66742 * include/bits/list.tcc (list::sort()): Use _Scratch_list objects for splicing and merging. (list::sort(StrictWeakOrdering)): Likewise. * include/bits/stl_list.h (__detail::_Scratch_list): New type. * src/c++98/list.cc (_List_node_base::_M_transfer): Add assertion for --enable-libstdcxx-debug library. * testsuite/23_containers/list/operations/66742.cc: New test. Tested powerpc64le-linux. Committed to trunk. --c06OEOIGgWbOhHgo Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="patch.txt" commit ff7793bea465019683b3a07d7ffceb6eae22def5 Author: Jonathan Wakely Date: Tue May 25 14:33:15 2021 libstdc++: Allow stateful allocators in std::list::sort [PR 66742] The temporary lists used by std::list::sort are default constructed, which means they use default constructed allocators. The sort operation is defined in terms of merge and splice operations, which have undefined behaviour (and abort) if the allocators do not compare equal. This means it is not possible to sort a list that uses an allocator that compares unequal to an default constructed allocator. The solution is to avoid using temporary std::list objects at all. We do not need to be able to allocate memory because no nodes are allocated, only spliced from one list to another. That means the temporary lists don't need an allocator at all, so whether it would compare equal doesn't matter. Instead of temporary std::list objects, we can just use a collection of _List_node_base objects that nodes can be spliced onto as needed. Those objects are wrapped in a _Scratch_list type that implements the splicing and merging operations used by list::sort. We also don't need to update the list size during the sort, because sorting doesn't alter the number of nodes. Although we move nodes in and out of the scratch lists, at the end of the function all nodes are back in the original std::list and the scratch lists are empty. So for the cxx11 ABI we can avoid the _M_size modifications usually done when splicing nodes. Signed-off-by: Jonathan Wakely libstdc++-v3/ChangeLog: PR libstdc++/66742 * include/bits/list.tcc (list::sort()): Use _Scratch_list objects for splicing and merging. (list::sort(StrictWeakOrdering)): Likewise. * include/bits/stl_list.h (__detail::_Scratch_list): New type. * src/c++98/list.cc (_List_node_base::_M_transfer): Add assertion for --enable-libstdcxx-debug library. * testsuite/23_containers/list/operations/66742.cc: New test. diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 62b0ba1063a..7f4e1569ab1 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -485,21 +485,34 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) { - list __carry; - list __tmp[64]; - list * __fill = __tmp; - list * __counter; + using __detail::_Scratch_list; + // The algorithm used here is largely unchanged from the SGI STL + // and is described in The C++ Standard Template Library by Plauger, + // Stepanov, Lee, Musser. + // Each element of *this is spliced out and merged into one of the + // sorted lists in __tmp, then all the lists in __tmp are merged + // together and then swapped back into *this. + // Because all nodes end up back in *this we do not need to update + // this->size() while nodes are temporarily moved out. + _Scratch_list __carry; + _Scratch_list __tmp[64]; + _Scratch_list* __fill = __tmp; + _Scratch_list* __counter; + + _Scratch_list::_Ptr_cmp __ptr_comp; + __try { do { - __carry.splice(__carry.begin(), *this, begin()); + __carry._M_take_one(begin()._M_node); for(__counter = __tmp; __counter != __fill && !__counter->empty(); ++__counter) { - __counter->merge(__carry); + + __counter->merge(__carry, __ptr_comp); __carry.swap(*__counter); } __carry.swap(*__counter); @@ -509,14 +522,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER while ( !empty() ); for (__counter = __tmp + 1; __counter != __fill; ++__counter) - __counter->merge(*(__counter - 1)); - swap( *(__fill - 1) ); + __counter->merge(__counter[-1], __ptr_comp); + __fill[-1].swap(this->_M_impl._M_node); } __catch(...) { - this->splice(this->end(), __carry); + // Move all nodes back into *this. + __carry._M_put_all(end()._M_node); for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) - this->splice(this->end(), __tmp[__i]); + __tmp[__i]._M_put_all(end()._M_node); __throw_exception_again; } } @@ -602,42 +616,49 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Do nothing if the list has length 0 or 1. if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) - { - list __carry; - list __tmp[64]; - list * __fill = __tmp; - list * __counter; - __try - { - do - { - __carry.splice(__carry.begin(), *this, begin()); + { + using __detail::_Scratch_list; + _Scratch_list __carry; + _Scratch_list __tmp[64]; + _Scratch_list* __fill = __tmp; + _Scratch_list* __counter; - for(__counter = __tmp; - __counter != __fill && !__counter->empty(); - ++__counter) - { - __counter->merge(__carry, __comp); - __carry.swap(*__counter); - } - __carry.swap(*__counter); - if (__counter == __fill) - ++__fill; - } - while ( !empty() ); + _Scratch_list::_Ptr_cmp __ptr_comp + = { __comp }; - for (__counter = __tmp + 1; __counter != __fill; ++__counter) - __counter->merge(*(__counter - 1), __comp); - swap(*(__fill - 1)); - } - __catch(...) - { - this->splice(this->end(), __carry); - for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) - this->splice(this->end(), __tmp[__i]); - __throw_exception_again; - } - } + __try + { + do + { + __carry._M_take_one(begin()._M_node); + + for(__counter = __tmp; + __counter != __fill && !__counter->empty(); + ++__counter) + { + + __counter->merge(__carry, __ptr_comp); + __carry.swap(*__counter); + } + __carry.swap(*__counter); + if (__counter == __fill) + ++__fill; + } + while ( !empty() ); + + for (__counter = __tmp + 1; __counter != __fill; ++__counter) + __counter->merge(__counter[-1], __ptr_comp); + __fill[-1].swap(this->_M_impl._M_node); + } + __catch(...) + { + // Move all nodes back into *this. + __carry._M_put_all(end()._M_node); + for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) + __tmp[__i]._M_put_all(end()._M_node); + __throw_exception_again; + } + } } _GLIBCXX_END_NAMESPACE_CONTAINER diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index e11603c0157..81361dfa4d5 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -158,6 +158,73 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: _List_node_base* _M_base() { return this; } }; + + // Used by list::sort to hold nodes being sorted. + struct _Scratch_list : _List_node_base + { + _Scratch_list() { _M_next = _M_prev = this; } + + bool empty() const { return _M_next == this; } + + void swap(_List_node_base& __l) { _List_node_base::swap(*this, __l); } + + template + struct _Ptr_cmp + { + _Cmp _M_cmp; + + bool + operator()(const __detail::_List_node_base* __lhs, + const __detail::_List_node_base* __rhs) /* not const */ + { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); } + }; + + template + struct _Ptr_cmp<_Iter, void> + { + bool + operator()(const __detail::_List_node_base* __lhs, + const __detail::_List_node_base* __rhs) const + { return *_Iter(__lhs) < *_Iter(__rhs); } + }; + + // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp. + template + void + merge(_List_node_base& __x, _Cmp __comp) + { + _List_node_base* __first1 = _M_next; + _List_node_base* const __last1 = this; + _List_node_base* __first2 = __x._M_next; + _List_node_base* const __last2 = std::__addressof(__x); + + while (__first1 != __last1 && __first2 != __last2) + { + if (__comp(__first2, __first1)) + { + _List_node_base* __next = __first2->_M_next; + __first1->_M_transfer(__first2, __next); + __first2 = __next; + } + else + __first1 = __first1->_M_next; + } + if (__first2 != __last2) + this->_M_transfer(__first2, __last2); + } + + // Splice the node at __i into *this. + void _M_take_one(_List_node_base* __i) + { this->_M_transfer(__i, __i->_M_next); } + + // Splice all nodes from *this after __i. + void _M_put_all(_List_node_base* __i) + { + if (!empty()) + __i->_M_transfer(_M_next, this); + } + }; + } // namespace detail _GLIBCXX_BEGIN_NAMESPACE_CONTAINER diff --git a/libstdc++-v3/src/c++98/list.cc b/libstdc++-v3/src/c++98/list.cc index 18f0e136c47..c2f5c43622e 100644 --- a/libstdc++-v3/src/c++98/list.cc +++ b/libstdc++-v3/src/c++98/list.cc @@ -94,6 +94,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_transfer(_List_node_base * const __first, _List_node_base * const __last) _GLIBCXX_USE_NOEXCEPT { + __glibcxx_assert(__first != __last); + if (this != __last) { // Remove [first, last) from its old position. diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc new file mode 100644 index 00000000000..24bda3920d8 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc @@ -0,0 +1,55 @@ +// { dg-do run { target c++11 } } + +#include +#include +#include + +// PR libstdc++/66742 +// abort on sorting list with custom allocator that is not stateless + +template> +bool is_sorted(const List& l, Cmp cmp = {}) +{ + auto it = l.begin(); + auto next = it; + const auto end = l.end(); + if (it == end) + return true; + while (++next != end) + if (cmp(*next, *it)) + return false; + else + it = next; + return true; +} + +void +test01() +{ + using Alloc = __gnu_test::uneq_allocator; + Alloc a1(1); + std::list l(a1); + for (int i = 0; i < 1000; ++i) + { + l.push_front(i); + l.push_back(i + (i % 3)); + } + const auto orig = l; + + l.sort(); + VERIFY( is_sorted(l) ); + l.sort(); + VERIFY( is_sorted(l) ); + + l = orig; + l.sort(std::less()); + VERIFY( is_sorted(l) ); + l.sort(std::greater()); + VERIFY( is_sorted(l, std::greater()) ); +} + +int +main() +{ + test01(); +} --c06OEOIGgWbOhHgo--