From patchwork Thu Aug 9 20:22:09 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 176251 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id A905F2C0091 for ; Fri, 10 Aug 2012 06:22:59 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1345148580; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:References:In-Reply-To:Content-Type:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=BgyjN01NvaVqvP3p8IumSy8eFVw=; b=VugjtlFsPYw2zn/87vzT32S1GGrR70CjTeADJIIp/kYAT0XXJmtjBf5v1zGfxW AhOGjdsuHtihIPommcVGyoKmxAxzdvdJIReS5hg2oGht8QbPI2f1t/NdJVYu3hWQ 1Ql38dLr2i75nxwfwZN009L5x1pEBL1l1aefYBWQLlrL8= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:References:In-Reply-To:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=jTNCDMIjT8Kh1Q8/bixrPwOabGSuwvLHwrLl5AdyL6v75g7vttEMqY4oE2orls DCgeoLX8HbD/moyTzqkE6vGO4uCBEYfDsG9uYVr204Qvgd6dumZ4eNGddKdiOYdA uVhp5zetXy95gZT3OSf7gxOJOy3b2cMP0UNJXbAW+YAiM=; Received: (qmail 23001 invoked by alias); 9 Aug 2012 20:22:38 -0000 Received: (qmail 22970 invoked by uid 22791); 9 Aug 2012 20:22:31 -0000 X-SWARE-Spam-Status: No, hits=-5.1 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, KHOP_RCVD_TRUST, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE X-Spam-Check-By: sourceware.org Received: from mail-ey0-f175.google.com (HELO mail-ey0-f175.google.com) (209.85.215.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 09 Aug 2012 20:22:16 +0000 Received: by eaad12 with SMTP id d12so290862eaa.20 for ; Thu, 09 Aug 2012 13:22:14 -0700 (PDT) Received: by 10.14.216.198 with SMTP id g46mr722074eep.32.1344543734593; Thu, 09 Aug 2012 13:22:14 -0700 (PDT) Received: from localhost.localdomain (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPS id e7sm6024806eep.2.2012.08.09.13.22.11 (version=SSLv3 cipher=OTHER); Thu, 09 Aug 2012 13:22:13 -0700 (PDT) Message-ID: <50241BF1.3060404@gmail.com> Date: Thu, 09 Aug 2012 22:22:09 +0200 From: =?UTF-8?B?RnJhbsOnb2lzIER1bW9udA==?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120723 Thunderbird/14.0 MIME-Version: 1.0 To: Paolo Carlini CC: Marc Glisse , Richard Smith , Ollie Wild , gcc-patches , Diego Novillo , Paul Pluzhnikov , libstdc++ Subject: Re: Value type of map need not be default copyable References: <501B9C45.7010409@oracle.com> <501D0635.8050006@oracle.com> <501D0D6A.3090407@oracle.com> <501D3AD7.8060503@oracle.com> <501D3D89.7010505@oracle.com> <501D40ED.8090909@oracle.com> <5022667F.404@gmail.com> <50226BF4.7070904@oracle.com> <5022D02C.4070108@gmail.com> <50237639.3030103@oracle.com> In-Reply-To: <50237639.3030103@oracle.com> 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 On 08/09/2012 10:35 AM, Paolo Carlini wrote: > Hi, > > On 08/09/2012 09:14 AM, Marc Glisse wrote: >> On Wed, 8 Aug 2012, François Dumont wrote: >> >>> On 08/08/2012 03:39 PM, Paolo Carlini wrote: >>>> On 08/08/2012 03:15 PM, François Dumont wrote: >>>>> I have also introduce a special std::pair constructor for >>>>> container usage so that we do not have to include the whole tuple >>>>> stuff just for associative container implementations. >>>> To be clear: sorry, this is not an option. >>>> >>>> Paolo. >>>> >>> Then I can only imagine the attached patch which require to >>> include tuple when including unordered_map or unordered_set. The >>> std::pair(piecewise_construct_t, tuple<>, tuple<>) is the only >>> constructor that allow to build a pair using the default constructor >>> for the second member. >> >> I agree that the extra constructor would be convenient (I probably >> would have gone with pair(T&&,__default_construct_t), the symmetric >> version, and enough extra constructors to resolve all ambiguities). >> Maybe LWG would consider doing something. > When it does, and the corresponding PR will be *ready* we'll > reconsider the issue. After all the *months and months and months* > spent by the LWG adding and removing members from pair and tweaking > everything wrt the containers and issues *still* popping up (like that > with the defaulted copy constructor vs insert constraining), and with > the support for scoped allocators still missing from our > implementation, we are not adding members to std::pair such easily. > Sorry, but personally I'm not available now to further discuss this > specific point. > > I was still hoping that for something as simple as mapped_type() we > wouldn't need the full machinery, and I encourage everybody to > have another look (while making sure anything we figure out adapts > smoothly an consistently to std::map), then in a few days we'll take a > final decision. We'll still have chances to further improve the code > in time for 4.8.0. > >> + __p = __h->_M_allocate_node(std::piecewise_construct, >> + std::make_tuple(__k), >> + std::make_tuple()); >> >> Don't you want cref(__k)? It might save a move at some point. > Are we already doing that elsewhere? I think we should aim for > something simple first, then carefully evaluate if the additional > complexity is worth the cost and in case deploy the superior solution > consistently everywhere it may apply. > > Thanks! > Paolo. > Here is an updated version considering the good catch from Marc. However I prefer to use an explicit instantiation of tuple rather than using cref that would have imply inclusion of in addition to . I have also updated the test case to use a type without copy and move constructors. 2012-08-09 François Dumont Ollie Wild * include/bits/hashtable.h (_Hashtable<>::_M_insert_bucket): Replace by ... (_Hashtable<>::_M_insert_node): ... this, new. (_Hashtable<>::_M_insert(_Args&&, true_type)): Use latter. * include/bits/hashtable_policy.h (_Map_base<>::operator[]): Use latter, emplace the value_type rather than insert. * include/std/unordered_map: Include tuple. * include/std/unordered_set: Likewise. * testsuite/util/testsuite_counter_type.h: New. * testsuite/23_containers/unordered_map/operators/2.cc: New. François Index: include/std/unordered_map =================================================================== --- include/std/unordered_map (revision 190209) +++ include/std/unordered_map (working copy) @@ -38,6 +38,7 @@ #include #include #include +#include #include #include #include // equal_to, _Identity, _Select1st Index: include/std/unordered_set =================================================================== --- include/std/unordered_set (revision 190209) +++ include/std/unordered_set (working copy) @@ -38,6 +38,7 @@ #include #include #include +#include #include #include #include // equal_to, _Identity, _Select1st Index: include/bits/hashtable_policy.h =================================================================== --- include/bits/hashtable_policy.h (revision 190209) +++ include/bits/hashtable_policy.h (working copy) @@ -577,8 +577,14 @@ __node_type* __p = __h->_M_find_node(__n, __k, __code); if (!__p) - return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), - __n, __code)->second; + { + __p = __h->_M_allocate_node(std::piecewise_construct, + std::tuple(__k), + std::make_tuple()); + __h->_M_store_code(__p, __code); + return __h->_M_insert_node(__n, __code, __p)->second; + } + return (__p->_M_v).second; } @@ -598,9 +604,14 @@ __node_type* __p = __h->_M_find_node(__n, __k, __code); if (!__p) - return __h->_M_insert_bucket(std::make_pair(std::move(__k), - mapped_type()), - __n, __code)->second; + { + __p = __h->_M_allocate_node(std::piecewise_construct, + std::forward_as_tuple(forward(__k)), + std::make_tuple()); + __h->_M_store_code(__p, __code); + return __h->_M_insert_node(__n, __code, __p)->second; + } + return (__p->_M_v).second; } Index: include/bits/hashtable.h =================================================================== --- include/bits/hashtable.h (revision 190209) +++ include/bits/hashtable.h (working copy) @@ -584,11 +584,11 @@ __node_base* _M_get_previous_node(size_type __bkt, __node_base* __n); - template - iterator - _M_insert_bucket(_Arg&&, size_type, __hash_code); + // Insert node in bucket bkt (assumes no element with its key already + // present). Take ownership of the node, deallocate it on exception. + iterator + _M_insert_node(size_type __bkt, __hash_code __code, __node_type* __n); - template std::pair _M_emplace(std::true_type, _Args&&... __args); @@ -1307,54 +1307,49 @@ } } - // Insert v in bucket n (assumes no element with its key already present). + // Insert node in bucket bkt (assumes no element with its key already + // present). Take ownership of the node, deallocate it on exception. template - template - typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, - _Traits>::iterator - _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_insert_bucket(_Arg&& __v, size_type __n, __hash_code __code) - { - const __rehash_state& __saved_state = _M_rehash_policy._M_state(); - std::pair __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, - _M_element_count, 1); + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_insert_node(size_type __bkt, __hash_code __code, __node_type* __node) + { + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); - if (__do_rehash.first) - { - const key_type& __k = this->_M_extract()(__v); - __n = __hash_code_base::_M_bucket_index(__k, __code, + if (__do_rehash.first) + { + const key_type& __k = this->_M_extract()(__node->_M_v); + __bkt = __hash_code_base::_M_bucket_index(__k, __code, __do_rehash.second); - } + } - __node_type* __node = nullptr; - __try - { - // Allocate the new node before doing the rehash so that we - // don't do a rehash if the allocation throws. - __node = _M_allocate_node(std::forward<_Arg>(__v)); - this->_M_store_code(__node, __code); - if (__do_rehash.first) - _M_rehash(__do_rehash.second, __saved_state); + __try + { + if (__do_rehash.first) + _M_rehash(__do_rehash.second, __saved_state); - _M_insert_bucket_begin(__n, __node); - ++_M_element_count; - return iterator(__node); - } - __catch(...) - { - if (!__node) - _M_rehash_policy._M_reset(__saved_state); - else - _M_deallocate_node(__node); - __throw_exception_again; - } - } + _M_insert_bucket_begin(__bkt, __node); + ++_M_element_count; + return iterator(__node); + } + __catch(...) + { + if (!__node) + _M_rehash_policy._M_reset(__saved_state); + else + _M_deallocate_node(__node); + __throw_exception_again; + } + } // Insert v if no element with its key is already present. template_M_extract()(__v); __hash_code __code = this->_M_hash_code(__k); - size_type __n = _M_bucket_index(__k, __code); + size_type __bkt = _M_bucket_index(__k, __code); - if (__node_type* __p = _M_find_node(__n, __k, __code)) - return std::make_pair(iterator(__p), false); - return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v), - __n, __code), true); + __node_type* __n = _M_find_node(__bkt, __k, __code); + if (__n) + return std::make_pair(iterator(__n), false); + + __n = _M_allocate_node(std::forward<_Arg>(__v)); + this->_M_store_code(__n, __code); + return std::make_pair(_M_insert_node(__bkt, __code, __n), true); } // Insert v unconditionally. @@ -1441,7 +1439,6 @@ } } - template. + +// 23.5.4 template class unordered_map + +// This test verifies that the value type of a unordered_map need not be +// default copyable. + +// { dg-options "-std=gnu++11" } + +#include +#include +#include +#include + +struct Mapped +{ + Mapped() = default; + explicit Mapped(const Mapped&) = default; +}; + +struct DefaultConstructibleType +{ + int val; + + DefaultConstructibleType() : val(123) + {} + + DefaultConstructibleType(const DefaultConstructibleType&) = delete; + DefaultConstructibleType(DefaultConstructibleType&&) = delete; + + DefaultConstructibleType& operator=(int x) + { + val = x; + return *this; + } +}; + +void test01() +{ + bool test __attribute__((unused)) = true; + + using __gnu_test::rvalstruct; + using __gnu_test::counter_type; + + std::unordered_map m1; + m1[0] = Mapped(); + + std::unordered_map m2; + m2[0] = rvalstruct(13); + + std::unordered_map m3; + VERIFY( m3[0].val == 123 ); + VERIFY( m3.size() == 1 ); + m3[0] = 2; + VERIFY( m3[0].val == 2 ); + + std::unordered_map m4; + VERIFY( m4[counter_type(1)] == 0 ); + VERIFY( counter_type::specialize_count == 1 ); + VERIFY( counter_type::copy_count == 0 ); + VERIFY( counter_type::move_count == 1 ); + + counter_type k(2); + counter_type::reset(); + + VERIFY( m4[k] == 0 ); + VERIFY( counter_type::copy_count == 1 ); + VERIFY( counter_type::move_count == 0 ); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/util/testsuite_counter_type.h =================================================================== --- testsuite/util/testsuite_counter_type.h (revision 0) +++ testsuite/util/testsuite_counter_type.h (revision 0) @@ -0,0 +1,123 @@ +// -*- C++ -*- +// +// Copyright (C) 2012 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 +// . +// + +#ifndef _TESTSUITE_COUNTER_TYPE_H +#define _TESTSUITE_COUNTER_TYPE_H 1 + +namespace __gnu_test +{ + // Type counting how many constructors or assign operators are invoked. + struct counter_type + { + // Constructor counters: + static int default_count; + static int specialize_count; + static int copy_count; + static int copy_assign_count; + static int less_compare_count; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + static int move_count; + static int move_assign_count; +#endif + + int val; + + counter_type() : val(0) + { + ++default_count; + } + + counter_type(int inval) : val(inval) + { + ++specialize_count; + } + + counter_type(const counter_type& in) : val(in.val) + { + ++copy_count; + } + + counter_type& + operator=(const counter_type& in) + { + val = in.val; + ++copy_assign_count; + return *this; + } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + counter_type(counter_type&& in) noexcept + { + val = in.val; + ++move_count; + } + + counter_type& + operator=(counter_type&& rhs) + { + val = rhs.val; + ++move_assign_count; + return *this; + } +#endif + + static void + reset() + { + default_count = 0; + specialize_count = 0; + copy_count = 0; + copy_assign_count = 0; + less_compare_count = 0; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + move_count = 0; + move_assign_count = 0; +#endif + } + + bool operator==(const counter_type& rhs) const + { return val == rhs.val; } + + bool operator<(const counter_type& rhs) const + { return val < rhs.val; } + }; + + int counter_type::default_count = 0; + int counter_type::specialize_count = 0; + int counter_type::copy_count = 0; + int counter_type::copy_assign_count = 0; + int counter_type::less_compare_count = 0; + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + int counter_type::move_count = 0; + int counter_type::move_assign_count = 0; +#endif + + struct counter_type_hasher + { + std::size_t operator()(const counter_type& c) const + { + return c.val; + } + }; + +} // namespace __gnu_test +#endif + Property changes on: testsuite/util/testsuite_counter_type.h ___________________________________________________________________ Added: svn:eol-style + native