From patchwork Wed Aug 8 13:15:43 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: 175928 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 B41D42C0098 for ; Wed, 8 Aug 2012 23:16:35 +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=1345036597; 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=qeEuUeP1F4507y7mGOGwyZbMCoE=; b=UqNFXcTudeRQi9gQ/SJZ/laxhBP2T16yqXoVoaNK9jY2FpYi3SGe+xqTJULLZB a3QfOOGBbC10VfsoBwqittiokO4N9CWZSXShjIEupplybrkoTppjfZRGllqQjESf JYE7tTT59DiH5JUoJ8N/fxiUOOIPsxMKM4CHnNnnOOYLU= 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=Ub5ZOfd1OATbVrOKH0spk0kEvITHkThI5Iaa4EV9DOgXBiI6Ox9qEFrk70T6cS mWEYw58CmqQp4u3gt3WBueqzLmFTh+sRRoUNbx8gNQFfhu0C4YZjRIeCyDXOsEqH XD5r3TlqvS+SUnuH8qAL68v0GEGMOieBPl2DA85wKSgb4=; Received: (qmail 3974 invoked by alias); 8 Aug 2012 13:16:13 -0000 Received: (qmail 3694 invoked by uid 22791); 8 Aug 2012 13:16:07 -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; Wed, 08 Aug 2012 13:15:48 +0000 Received: by eaad12 with SMTP id d12so248672eaa.20 for ; Wed, 08 Aug 2012 06:15:46 -0700 (PDT) Received: by 10.14.215.129 with SMTP id e1mr22024105eep.46.1344431746535; Wed, 08 Aug 2012 06:15:46 -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 d48sm64625498eeo.10.2012.08.08.06.15.44 (version=SSLv3 cipher=OTHER); Wed, 08 Aug 2012 06:15:45 -0700 (PDT) Message-ID: <5022667F.404@gmail.com> Date: Wed, 08 Aug 2012 15:15:43 +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: Marc Glisse CC: Richard Smith , Ollie Wild , Paolo Carlini , 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> In-Reply-To: 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/08/2012 09:34 AM, Marc Glisse wrote: > On Tue, 7 Aug 2012, Richard Smith wrote: > >>> I've attached a patch for unordered_map which solves the rvalue >>> reference problem. For efficiency, I've created a new >>> _M_emplace_bucket method rather than call emplace directly. >>> >>> I've verified all libstdc++ tests pass (sorry for the previous >>> oversight) and am running the full GCC test suite now. However, I'd >>> appreciate any feedback on whether this is a reasonable approach. STL >>> hacking is way outside my comfort zone. ;-) >>> >>> If this looks good, I'll take a stab at std::map. >> >> I think you should remove the mapped_type() argument from the call to >> _M_emplace_bucket. In C++11, the mapped_type is not required to be >> copyable >> at all, just to be DefaultInsertable. > > Indeed. The reason I was talking about emplace is that you want an > object to be created only at the time the node is created. That might > mean passing piecewise_construct_t and an empty tuple to emplace > (otherwise it is too similar to insert). Or for unordered_map where > the node functions are "exposed", you could just create the node > directly without passing through emplace. > This is what I try to do in the attached patch. I replace _M_insert_bucket with _M_insert_node and use it for operator[] implementation. 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. However one test is failing: /home/fdt/dev/gcc/libstdc++-v3/testsuite/23_containers/unordered_map/insert/array_syntax_move.cc:39:18: required from here /home/fdt/dev/gcc-build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/stl_pair.h:175:42: error: use of deleted function '__gnu_test::rvalstruct::rvalstruct(const __gnu_test::rvalstruct&)' : first(std::forward<_T1>(__x)), second() { } I don't understand why it doesn't use the move constructor. I can't see any std::forward call missing. Anyone ? François Index: include/bits/hashtable.h =================================================================== --- include/bits/hashtable.h (revision 190209) +++ include/bits/hashtable.h (working copy) @@ -584,11 +584,10 @@ __node_base* _M_get_previous_node(size_type __bkt, __node_base* __n); - template - iterator - _M_insert_bucket(_Arg&&, size_type, __hash_code); + // Insert the node n. Assumes key doesn't exist + 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 +1306,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 passed 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 +1438,6 @@ } } - template_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::__detail::container_construct, __k); + __h->_M_store_code(__p, __code); + return __h->_M_insert_node(__n, __code, __p)->second; + } + return (__p->_M_v).second; } @@ -598,9 +602,13 @@ __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::__detail::container_construct, + std::forward(__k)); + __h->_M_store_code(__p, __code); + return __h->_M_insert_node(__n, __code, __p)->second; + } + return (__p->_M_v).second; } Index: include/bits/stl_pair.h =================================================================== --- include/bits/stl_pair.h (revision 190209) +++ include/bits/stl_pair.h (working copy) @@ -81,6 +81,23 @@ template struct _Index_tuple; + +_GLIBCXX_END_NAMESPACE_VERSION + +namespace __detail +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + /// container_construct_t for associative container usage only. + struct container_construct_t { }; + + /// container_construct + constexpr container_construct_t container_construct = container_construct_t(); + +_GLIBCXX_END_NAMESPACE_VERSION +} + +_GLIBCXX_BEGIN_NAMESPACE_VERSION #endif /** @@ -151,6 +168,12 @@ template pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>); + pair(std::__detail::container_construct_t, const _T1& __x) + : first(__x), second() { } + + pair(std::__detail::container_construct_t, _T1&& __x) + : first(std::forward<_T1>(__x)), second() { } + pair& operator=(const pair& __p) {