From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 31688 invoked by alias); 15 May 2014 20:20:52 -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 31662 invoked by uid 89); 15 May 2014 20:20:51 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-we0-f171.google.com Received: from mail-we0-f171.google.com (HELO mail-we0-f171.google.com) (74.125.82.171) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Thu, 15 May 2014 20:20:46 +0000 Received: by mail-we0-f171.google.com with SMTP id w62so1633141wes.30 for ; Thu, 15 May 2014 13:20:42 -0700 (PDT) X-Received: by 10.180.13.208 with SMTP id j16mr32600105wic.58.1400185242839; Thu, 15 May 2014 13:20:42 -0700 (PDT) Received: from [192.168.0.22] (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPSA id h19sm11641546wiw.17.2014.05.15.13.20.41 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 15 May 2014 13:20:41 -0700 (PDT) Message-ID: <53752198.1030705@gmail.com> Date: Thu, 15 May 2014 20:20:00 -0000 From: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 MIME-Version: 1.0 To: "libstdc++@gcc.gnu.org" , gcc-patches Subject: [patch] libstdc++/61143 make unordered containers usable after move Content-Type: multipart/mixed; boundary="------------000700090404070101070201" X-SW-Source: 2014-05/txt/msg01225.txt.bz2 This is a multi-part message in MIME format. --------------000700090404070101070201 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Content-length: 786 Hi Here is a proposal to fix PR 61143. As explained in the PR I finally prefer to leave the container in a valid state that is to say with a non zero number of bucket, that is to say 1, after a move. This bucket is stored directly in the container so not allocated to leave the move operations noexcept qualified. With this evolution we could even make the default constructor noexcept but I don't think it has any interest. 2014-05-15 François Dumont PR libstdc++/61143 * include/bits/hashtable.h: Fix move semantic to leave hashtable in a usable state. * testsuite/23_containers/unordered_set/61143.cc: New. I run unordered containers test for the moment with no error. I will run the others before to commit. François --------------000700090404070101070201 Content-Type: text/x-patch; name="hashtable.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="hashtable.patch" Content-length: 16444 Index: include/bits/hashtable.h =================================================================== --- include/bits/hashtable.h (revision 210479) +++ include/bits/hashtable.h (working copy) @@ -316,14 +316,37 @@ size_type _M_element_count; _RehashPolicy _M_rehash_policy; + // A single bucket used when only need 1 bucket. After move the hashtable + // is left with only 1 bucket which is not allocated so that we can have a + // noexcept move constructor. + // Note that we can't leave hashtable with 0 bucket without adding + // numerous checks in the code to avoid 0 modulus. + __bucket_type _M_single_bucket; + __hashtable_alloc& _M_base_alloc() { return *this; } - using __hashtable_alloc::_M_deallocate_buckets; + __bucket_type* + _M_allocate_buckets(size_type __n) + { + if (__builtin_expect(__n == 1, false)) + return &_M_single_bucket; + return __hashtable_alloc::_M_allocate_buckets(__n); + } + void + _M_deallocate_buckets(__bucket_type* __bkts, size_type __n) + { + if (__builtin_expect(__bkts == &_M_single_bucket, false)) + return; + + __hashtable_alloc::_M_deallocate_buckets(__bkts, __n); + } + + void _M_deallocate_buckets() - { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); } + { _M_deallocate_buckets(_M_buckets, _M_bucket_count); } // Gets bucket begin, deals with the fact that non-empty buckets contain // their before begin node. @@ -703,11 +726,7 @@ size_type erase(const key_type& __k) - { - if (__builtin_expect(_M_bucket_count == 0, false)) - return 0; - return _M_erase(__unique_keys(), __k); - } + { return _M_erase(__unique_keys(), __k); } iterator erase(const_iterator, const_iterator); @@ -768,7 +787,7 @@ _M_rehash_policy() { _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); - _M_buckets = this->_M_allocate_buckets(_M_bucket_count); + _M_buckets = _M_allocate_buckets(_M_bucket_count); } template_M_allocate_buckets(_M_bucket_count); + _M_buckets = _M_allocate_buckets(_M_bucket_count); __try { for (; __f != __l; ++__f) @@ -833,9 +852,9 @@ { // Replacement allocator cannot free existing storage. this->_M_deallocate_nodes(_M_begin()); - if (__builtin_expect(_M_bucket_count != 0, true)) - _M_deallocate_buckets(); - _M_reset(); + _M_before_begin._M_nxt = nullptr; + _M_deallocate_buckets(); + _M_buckets = nullptr; std::__alloc_on_copy(__this_alloc, __that_alloc); __hashtable_base::operator=(__ht); _M_bucket_count = __ht._M_bucket_count; @@ -867,7 +886,7 @@ if (_M_bucket_count != __ht._M_bucket_count) { __former_buckets = _M_buckets; - _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count); + _M_buckets = _M_allocate_buckets(__ht._M_bucket_count); _M_bucket_count = __ht._M_bucket_count; } else @@ -885,8 +904,7 @@ [&__roan](const __node_type* __n) { return __roan(__n->_M_v()); }); if (__former_buckets) - this->_M_deallocate_buckets(__former_buckets, - __former_bucket_count); + _M_deallocate_buckets(__former_buckets, __former_bucket_count); } __catch(...) { @@ -917,7 +935,7 @@ { __bucket_type* __buckets = nullptr; if (!_M_buckets) - _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count); + _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count); __try { @@ -964,8 +982,9 @@ _M_reset() noexcept { _M_rehash_policy._M_reset(); - _M_bucket_count = 0; - _M_buckets = nullptr; + _M_bucket_count = 1; + _M_buckets = &_M_single_bucket; + _M_single_bucket = nullptr; _M_before_begin._M_nxt = nullptr; _M_element_count = 0; } @@ -980,12 +999,16 @@ _M_move_assign(_Hashtable&& __ht, std::true_type) { this->_M_deallocate_nodes(_M_begin()); - if (__builtin_expect(_M_bucket_count != 0, true)) - _M_deallocate_buckets(); - + _M_deallocate_buckets(); __hashtable_base::operator=(std::move(__ht)); _M_rehash_policy = __ht._M_rehash_policy; - _M_buckets = __ht._M_buckets; + if (__builtin_expect(__ht._M_buckets != &__ht._M_single_bucket, true)) + _M_buckets = __ht._M_buckets; + else + { + _M_buckets = &_M_single_bucket; + _M_single_bucket = __ht._M_single_bucket; + } _M_bucket_count = __ht._M_bucket_count; _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; _M_element_count = __ht._M_element_count; @@ -1019,7 +1042,7 @@ if (_M_bucket_count != __ht._M_bucket_count) { __former_buckets = _M_buckets; - _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count); + _M_buckets = _M_allocate_buckets(__ht._M_bucket_count); _M_bucket_count = __ht._M_bucket_count; } else @@ -1093,10 +1116,18 @@ _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) { + // Update, if necessary, buckets if __ht is using its single bucket. + if (__builtin_expect(__ht._M_buckets == &__ht._M_single_bucket, false)) + { + _M_buckets = &_M_single_bucket; + _M_single_bucket = __ht._M_single_bucket; + } + // Update, if necessary, bucket pointing to before begin that hasn't // moved. if (_M_begin()) _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + __ht._M_reset(); } @@ -1139,7 +1170,14 @@ { if (__ht._M_node_allocator() == this->_M_node_allocator()) { - _M_buckets = __ht._M_buckets; + if (__builtin_expect(__ht._M_buckets == &__ht._M_single_bucket, false)) + { + _M_buckets = &_M_single_bucket; + _M_single_bucket = __ht._M_single_bucket; + } + else + _M_buckets = __ht._M_buckets; + _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; // Update, if necessary, bucket pointing to before begin that hasn't // moved. @@ -1193,11 +1231,21 @@ std::swap(_M_bucket_count, __x._M_bucket_count); std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); std::swap(_M_element_count, __x._M_element_count); + std::swap(_M_single_bucket, __x._M_single_bucket); + // Fix buckets if any is pointing to its single bucket that can't be + // swapped. + if (_M_buckets == &__x._M_single_bucket) + _M_buckets = &_M_single_bucket; + + if (__x._M_buckets == &_M_single_bucket) + __x._M_buckets = &__x._M_single_bucket; + // Fix buckets containing the _M_before_begin pointers that can't be // swapped. if (_M_begin()) _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + if (__x._M_begin()) __x._M_buckets[__x._M_bucket_index(__x._M_begin())] = &__x._M_before_begin; @@ -1230,9 +1278,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: find(const key_type& __k) { - if (__builtin_expect(_M_bucket_count == 0, false)) - return end(); - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_find_node(__n, __k, __code); @@ -1250,9 +1295,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: find(const key_type& __k) const { - if (__builtin_expect(_M_bucket_count == 0, false)) - return end(); - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_find_node(__n, __k, __code); @@ -1270,9 +1312,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: count(const key_type& __k) const { - if (__builtin_expect(_M_bucket_count == 0, false)) - return 0; - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_bucket_begin(__n); @@ -1311,9 +1350,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) { - if (__builtin_expect(_M_bucket_count == 0, false)) - return std::make_pair(end(), end()); - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_find_node(__n, __k, __code); @@ -1347,9 +1383,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) const { - if (__builtin_expect(_M_bucket_count == 0, false)) - return std::make_pair(end(), end()); - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_find_node(__n, __k, __code); @@ -1944,7 +1977,7 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __n, std::true_type) { - __bucket_type* __new_buckets = this->_M_allocate_buckets(__n); + __bucket_type* __new_buckets = _M_allocate_buckets(__n); __node_type* __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt = 0; @@ -1969,8 +2002,7 @@ __p = __next; } - if (__builtin_expect(_M_bucket_count != 0, true)) - _M_deallocate_buckets(); + _M_deallocate_buckets(); _M_bucket_count = __n; _M_buckets = __new_buckets; } @@ -1986,7 +2018,7 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __n, std::false_type) { - __bucket_type* __new_buckets = this->_M_allocate_buckets(__n); + __bucket_type* __new_buckets = _M_allocate_buckets(__n); __node_type* __p = _M_begin(); _M_before_begin._M_nxt = nullptr; @@ -2060,8 +2092,7 @@ __new_buckets[__next_bkt] = __prev_p; } - if (__builtin_expect(_M_bucket_count != 0, true)) - _M_deallocate_buckets(); + _M_deallocate_buckets(); _M_bucket_count = __n; _M_buckets = __new_buckets; } Index: testsuite/23_containers/unordered_map/allocator/copy_assign.cc =================================================================== --- testsuite/23_containers/unordered_map/allocator/copy_assign.cc (revision 210479) +++ testsuite/23_containers/unordered_map/allocator/copy_assign.cc (working copy) @@ -17,6 +17,7 @@ // { dg-options "-std=c++11" } +#include #include #include #include @@ -56,22 +57,37 @@ void test02() { bool test __attribute__((unused)) = true; - typedef propagating_allocator alloc_type; - typedef std::unordered_map test_type; - test_type v1(alloc_type(1)); - v1.emplace(std::piecewise_construct, - std::make_tuple(T()), std::make_tuple(T())); - test_type v2(alloc_type(2)); - v2.emplace(std::piecewise_construct, - std::make_tuple(T()), std::make_tuple(T())); - v2 = v1; - VERIFY(1 == v1.get_allocator().get_personality()); - VERIFY(1 == v2.get_allocator().get_personality()); + { + typedef propagating_allocator alloc_type; + typedef std::unordered_map test_type; + std::cout << "Instantiate v1" << std::endl; + test_type v1(alloc_type(1)); + std::cout << "Emplace in v1" << std::endl; + v1.emplace(std::piecewise_construct, + std::make_tuple(T()), std::make_tuple(T())); + { + std::cout << "Instantiate v2" << std::endl; + test_type v2(alloc_type(2)); + std::cout << "Emplace in v2" << std::endl; + v2.emplace(std::piecewise_construct, + std::make_tuple(T()), std::make_tuple(T())); + std::cout << "v2 = v1" << std::endl; + v2 = v1; + std::cout << "Done" << std::endl; + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(1 == v2.get_allocator().get_personality()); + } + std::cout << "v2 destroyed" << std::endl; + } + std::cout << "v1 destroyed" << std::endl; } int main() { + std::cout << "Running test01" << std::endl; test01(); + std::cout << "Running test02" << std::endl; test02(); + std::cout << "Done" << std::endl; return 0; } Index: testsuite/23_containers/unordered_set/61143.cc =================================================================== --- testsuite/23_containers/unordered_set/61143.cc (revision 0) +++ testsuite/23_containers/unordered_set/61143.cc (working copy) @@ -0,0 +1,38 @@ +// { dg-options "-std=gnu++11" } + +// Copyright (C) 2014 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 +// . + +// libstdc++/61143 + +#include + +void test01() +{ + std::unordered_set us1, us2; + us1.insert(1); + + us2 = std::move(us1); + + us1.insert(1); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/Makefile.in =================================================================== --- testsuite/Makefile.in (revision 210479) +++ testsuite/Makefile.in (working copy) @@ -1,9 +1,9 @@ -# Makefile.in generated by automake 1.11.1 from Makefile.am. +# Makefile.in generated by automake 1.11.6 from Makefile.am. # @configure_input@ # Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, -# 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation, -# Inc. +# 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software +# Foundation, Inc. # This Makefile.in is free software; the Free Software Foundation # gives unlimited permission to copy and/or distribute it, # with or without modifications, as long as this notice is preserved. @@ -15,6 +15,23 @@ @SET_MAKE@ VPATH = @srcdir@ +am__make_dryrun = \ + { \ + am__dry=no; \ + case $$MAKEFLAGS in \ + *\\[\ \ ]*) \ + echo 'am--echo: ; @echo "AM" OK' | $(MAKE) -f - 2>/dev/null \ + | grep '^AM OK$$' >/dev/null || am__dry=yes;; \ + *) \ + for am__flg in $$MAKEFLAGS; do \ + case $$am__flg in \ + *=*|--*) ;; \ + *n*) am__dry=yes; break;; \ + esac; \ + done;; \ + esac; \ + test $$am__dry = yes; \ + } pkgdatadir = $(datadir)/@PACKAGE@ pkgincludedir = $(includedir)/@PACKAGE@ pkglibdir = $(libdir)/@PACKAGE@ @@ -67,6 +84,11 @@ depcomp = am__depfiles_maybe = SOURCES = +am__can_run_installinfo = \ + case $$AM_UPDATE_INFO_DIR in \ + n|no|NO) false;; \ + *) (install-info --version) >/dev/null 2>&1;; \ + esac ABI_TWEAKS_SRCDIR = @ABI_TWEAKS_SRCDIR@ ACLOCAL = @ACLOCAL@ ALLOCATOR_H = @ALLOCATOR_H@ @@ -360,6 +382,7 @@ echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \ cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \ esac; +$(top_srcdir)/fragment.am: $(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh @@ -395,10 +418,15 @@ installcheck: installcheck-am install-strip: - $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ - install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ - `test -z '$(STRIP)' || \ - echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install + if test -z '$(STRIP)'; then \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + install; \ + else \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \ + fi mostlyclean-generic: clean-generic: --------------000700090404070101070201--