From patchwork Mon Jun 16 20:23:09 2014 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: 360236 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 97615140088 for ; Tue, 17 Jun 2014 06:23:50 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; q=dns; s=default; b=TY/WlPpV2iw18lLh+ j9K71xaL1F0Vs10xm+FiNl7kCQzEMsT2LfjpJRV86mFzb3bCCjJ+U3IEtnk7TB2E V0ntGuCraxQ06hUuRC6ILM1oCWsdKz/wsbq2c4Kg7I/H8PZVrbJyknXSCyiTeZky JS1OLga2pgaONzwqjcCZWUL3yM= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; s=default; bh=j9qe8qVlzDw1w1wgYdiuP7Y 1BQw=; b=ngM/6D92fiKd4atcE+7K/BaKTLV+l30wZYKa9vdz7vXgfgYdsfbul6a wFNAq744y0qfLdCbQ1tgzNHI2QMAvFXnqTaSr8ae+KUsrdzW1I4n8UJjxacM12fF 0p32Io+UnQBEPyaC6GNxexfu8JbjSbC7uRb1/7PaYu2HFjldZYfI= Received: (qmail 1762 invoked by alias); 16 Jun 2014 20:23:27 -0000 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 Received: (qmail 1743 invoked by uid 89); 16 Jun 2014 20:23:25 -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, T_FILL_THIS_FORM_SHORT autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-we0-f177.google.com Received: from mail-we0-f177.google.com (HELO mail-we0-f177.google.com) (74.125.82.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 16 Jun 2014 20:23:17 +0000 Received: by mail-we0-f177.google.com with SMTP id u56so6291421wes.36 for ; Mon, 16 Jun 2014 13:23:14 -0700 (PDT) X-Received: by 10.180.212.5 with SMTP id ng5mr30062022wic.33.1402950194032; Mon, 16 Jun 2014 13:23:14 -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 18sm20176394wju.15.2014.06.16.13.23.10 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 16 Jun 2014 13:23:12 -0700 (PDT) Message-ID: <539F522D.2040600@gmail.com> Date: Mon, 16 Jun 2014 22:23:09 +0200 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: Jonathan Wakely CC: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: [patch] libstdc++/29988 Rb_Tree reuse allocated nodes References: <5398028E.5020904@gmail.com> <20140611120224.GS30729@redhat.com> In-Reply-To: <20140611120224.GS30729@redhat.com> Hi Here is another proposal taking into account your remarks except the one below. In fact I had no problem with lambda, I just needed to store them in a variable, lambda do not need to be made mutable. On 11/06/2014 14:02, Jonathan Wakely wrote: > >> @@ -514,11 +651,11 @@ >> { return this->_M_impl._M_header._M_right; } >> >> _Link_type >> - _M_begin() _GLIBCXX_NOEXCEPT >> + _M_begin() const _GLIBCXX_NOEXCEPT >> { return >> static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } > > What's the purpose of this change? > Although it can be 'const' it is consistent with the usual > begin()/end() functions that the functions returning a mutable iterator > are non-const and the functions returning a constant iterator are const. > >> _Const_Link_type >> - _M_begin() const _GLIBCXX_NOEXCEPT >> + _M_cbegin() const _GLIBCXX_NOEXCEPT >> { >> return static_cast<_Const_Link_type> >> (this->_M_impl._M_header._M_parent); >> @@ -529,7 +666,7 @@ >> { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); } >> >> _Const_Link_type >> - _M_end() const _GLIBCXX_NOEXCEPT >> + _M_cend() const _GLIBCXX_NOEXCEPT >> { return >> reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); } >> >> static const_reference > > I'm not very comfortable with this renaming. > > Having consistent _M_begin() functions allows using them in template > code that doesn't care if it's using the const or non-const version. > > I try to revert this part and so remember why I did it in the first place. I needed to change _M_copy signature to: _Link_type _M_copy(_Link_type __x, _Link_type __p) because I now use this method to also move the elements of the data structure, I cannot move from a _Const_Like_type so I change first parameter to _Link_type. I see that there are some code duplications to deal with _Const_Link_type and _Link_type in 2 different part of the code but I didn't want to duplicate again here and simply made _M_copy more more flexible by taking a _Link_type rather than a _Const_Link_type. I don't really see interest of the existing code duplications so I prefer to not do the same and write the code only once. François Index: include/bits/stl_map.h =================================================================== --- include/bits/stl_map.h (revision 211713) +++ include/bits/stl_map.h (working copy) @@ -297,28 +297,9 @@ } #if __cplusplus >= 201103L - /** - * @brief %Map move assignment operator. - * @param __x A %map of identical element and allocator types. - * - * The contents of @a __x are moved into this map (without copying - * if the allocators compare equal or get moved on assignment). - * Afterwards @a __x is in a valid, but unspecified state. - */ + /// Move assignment operator. map& - operator=(map&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) - { - if (!_M_t._M_move_assign(__x._M_t)) - { - // The rvalue's allocator cannot be moved and is not equal, - // so we need to individually move each element. - clear(); - insert(std::__make_move_if_noexcept_iterator(__x.begin()), - std::__make_move_if_noexcept_iterator(__x.end())); - __x.clear(); - } - return *this; - } + operator=(map&&) = default; /** * @brief %Map list assignment operator. @@ -334,8 +315,7 @@ map& operator=(initializer_list __l) { - this->clear(); - this->insert(__l.begin(), __l.end()); + _M_t._M_assign_unique(__l.begin(), __l.end()); return *this; } #endif Index: include/bits/stl_multimap.h =================================================================== --- include/bits/stl_multimap.h (revision 211713) +++ include/bits/stl_multimap.h (working copy) @@ -292,28 +292,9 @@ } #if __cplusplus >= 201103L - /** - * @brief %Multimap move assignment operator. - * @param __x A %multimap of identical element and allocator types. - * - * The contents of @a __x are moved into this multimap (without copying - * if the allocators compare equal or get moved on assignment). - * Afterwards @a __x is in a valid, but unspecified state. - */ + /// Move assignment operator. multimap& - operator=(multimap&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) - { - if (!_M_t._M_move_assign(__x._M_t)) - { - // The rvalue's allocator cannot be moved and is not equal, - // so we need to individually move each element. - clear(); - insert(std::__make_move_if_noexcept_iterator(__x.begin()), - std::__make_move_if_noexcept_iterator(__x.end())); - __x.clear(); - } - return *this; - } + operator=(multimap&&) = default; /** * @brief %Multimap list assignment operator. @@ -329,8 +310,7 @@ multimap& operator=(initializer_list __l) { - this->clear(); - this->insert(__l.begin(), __l.end()); + _M_t._M_assign_equal(__l.begin(), __l.end()); return *this; } #endif Index: include/bits/stl_multiset.h =================================================================== --- include/bits/stl_multiset.h (revision 211713) +++ include/bits/stl_multiset.h (working copy) @@ -263,28 +263,9 @@ } #if __cplusplus >= 201103L - /** - * @brief %Multiset move assignment operator. - * @param __x A %multiset of identical element and allocator types. - * - * The contents of @a __x are moved into this %multiset (without - * copying if the allocators compare equal or get moved on assignment). - * Afterwards @a __x is in a valid, but unspecified state. - */ + /// Move assignment operator. multiset& - operator=(multiset&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) - { - if (!_M_t._M_move_assign(__x._M_t)) - { - // The rvalue's allocator cannot be moved and is not equal, - // so we need to individually move each element. - clear(); - insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()), - std::__make_move_if_noexcept_iterator(__x._M_t.end())); - __x.clear(); - } - return *this; - } + operator=(multiset&&) = default; /** * @brief %Multiset list assignment operator. @@ -300,8 +281,7 @@ multiset& operator=(initializer_list __l) { - this->clear(); - this->insert(__l.begin(), __l.end()); + _M_t._M_assign_equal(__l.begin(), __l.end()); return *this; } #endif Index: include/bits/stl_set.h =================================================================== --- include/bits/stl_set.h (revision 211713) +++ include/bits/stl_set.h (working copy) @@ -267,28 +267,9 @@ } #if __cplusplus >= 201103L - /** - * @brief %Set move assignment operator. - * @param __x A %set of identical element and allocator types. - * - * The contents of @a __x are moved into this %set (without copying - * if the allocators compare equal or get moved on assignment). - * Afterwards @a __x is in a valid, but unspecified state. - */ + /// Move assignment operator. set& - operator=(set&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) - { - if (!_M_t._M_move_assign(__x._M_t)) - { - // The rvalue's allocator cannot be moved and is not equal, - // so we need to individually move each element. - clear(); - insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()), - std::__make_move_if_noexcept_iterator(__x._M_t.end())); - __x.clear(); - } - return *this; - } + operator=(set&&) = default; /** * @brief %Set list assignment operator. @@ -304,8 +285,7 @@ set& operator=(initializer_list __l) { - this->clear(); - this->insert(__l.begin(), __l.end()); + _M_t._M_assign_unique(__l.begin(), __l.end()); return *this; } #endif Index: include/bits/stl_tree.h =================================================================== --- include/bits/stl_tree.h (revision 211713) +++ include/bits/stl_tree.h (working copy) @@ -353,7 +353,107 @@ protected: typedef _Rb_tree_node_base* _Base_ptr; typedef const _Rb_tree_node_base* _Const_Base_ptr; + typedef _Rb_tree_node<_Val>* _Link_type; + typedef const _Rb_tree_node<_Val>* _Const_Link_type; + private: + // Functor recycling a pool of nodes and using allocation once the pool is + // empty. + struct _Reuse_or_alloc_node + { + _Reuse_or_alloc_node(const _Rb_tree_node_base& __header, + _Rb_tree& __t) + : _M_root(__header._M_parent), _M_nodes(__header._M_right), _M_t(__t) + { + if (_M_root) + _M_root->_M_parent = 0; + else + _M_nodes = 0; + } + +#if __cplusplus >= 201103L + _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete; +#endif + + ~_Reuse_or_alloc_node() + { _M_t._M_erase(static_cast<_Link_type>(_M_root)); } + + template + _Link_type +#if __cplusplus < 201103L + operator()(const _Arg& __arg) +#else + operator()(_Arg&& __arg) +#endif + { + _Link_type __node = static_cast<_Link_type>(_M_extract()); + if (__node) + { + _M_t._M_destroy_node(__node); + _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg)); + return __node; + } + + return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); + } + + private: + _Base_ptr + _M_extract() + { + if (!_M_nodes) + return _M_nodes; + + _Base_ptr __node = _M_nodes; + _M_nodes = _M_nodes->_M_parent; + if (_M_nodes) + { + if (_M_nodes->_M_right == __node) + { + _M_nodes->_M_right = 0; + + if (_M_nodes->_M_left) + { + _M_nodes = _M_nodes->_M_left; + + while (_M_nodes->_M_right) + _M_nodes = _M_nodes->_M_right; + } + } + else // __node is on the left. + _M_nodes->_M_left = 0; + } + else + _M_root = 0; + + return __node; + } + + _Base_ptr _M_root; + _Base_ptr _M_nodes; + _Rb_tree& _M_t; + }; + + // Functor similar to the previous one but without any pool of node to + // recycle. + struct _Alloc_node + { + _Alloc_node(_Rb_tree& __t) + : _M_t(__t) { } + + template + _Link_type +#if __cplusplus < 201103L + operator()(const _Arg& __arg) const +#else + operator()(_Arg&& __arg) const +#endif + { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } + + private: + _Rb_tree& _M_t; + }; + public: typedef _Key key_type; typedef _Val value_type; @@ -361,8 +461,6 @@ typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; - typedef _Rb_tree_node<_Val>* _Link_type; - typedef const _Rb_tree_node<_Val>* _Const_Link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Alloc allocator_type; @@ -389,44 +487,55 @@ { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } #if __cplusplus < 201103L - _Link_type - _M_create_node(const value_type& __x) + void + _M_construct_node(_Link_type __node, const value_type& __x) { - _Link_type __tmp = _M_get_node(); __try - { get_allocator().construct(__tmp->_M_valptr(), __x); } + { get_allocator().construct(__node->_M_valptr(), __x); } __catch(...) { - _M_put_node(__tmp); + _M_put_node(__node); __throw_exception_again; } + } + + _Link_type + _M_create_node(const value_type& __x) + { + _Link_type __tmp = _M_get_node(); + _M_construct_node(__tmp, __x); return __tmp; } void _M_destroy_node(_Link_type __p) - { - get_allocator().destroy(__p->_M_valptr()); - _M_put_node(__p); - } + { get_allocator().destroy(__p->_M_valptr()); } #else template - _Link_type - _M_create_node(_Args&&... __args) + void + _M_construct_node(_Link_type __node, _Args&&... __args) { - _Link_type __tmp = _M_get_node(); __try { - ::new(__tmp) _Rb_tree_node<_Val>; + ::new(__node) _Rb_tree_node<_Val>; _Alloc_traits::construct(_M_get_Node_allocator(), - __tmp->_M_valptr(), + __node->_M_valptr(), std::forward<_Args>(__args)...); } __catch(...) { - _M_put_node(__tmp); + __node->~_Rb_tree_node<_Val>(); + _M_put_node(__node); __throw_exception_again; } + } + + template + _Link_type + _M_create_node(_Args&&... __args) + { + _Link_type __tmp = _M_get_node(); + _M_construct_node(__tmp, std::forward<_Args>(__args)...); return __tmp; } @@ -435,23 +544,29 @@ { _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); __p->~_Rb_tree_node<_Val>(); - _M_put_node(__p); } #endif - _Link_type - _M_clone_node(_Const_Link_type __x) + void + _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT { - _Link_type __tmp = _M_create_node(*__x->_M_valptr()); - __tmp->_M_color = __x->_M_color; - __tmp->_M_left = 0; - __tmp->_M_right = 0; - return __tmp; + _M_destroy_node(__p); + _M_put_node(__p); } + template + _Link_type + _M_clone_node(_Link_type __x, _NodeGen& __node_gen) + { + _Link_type __tmp = __node_gen(*__x->_M_valptr()); + __tmp->_M_color = __x->_M_color; + __tmp->_M_left = 0; + __tmp->_M_right = 0; + return __tmp; + } + protected: - template + template struct _Rb_tree_impl : public _Node_allocator { _Key_compare _M_key_compare; @@ -475,6 +590,15 @@ { _M_initialize(); } #endif + void + _M_reset() + { + this->_M_header._M_parent = 0; + this->_M_header._M_left = &this->_M_header; + this->_M_header._M_right = &this->_M_header; + this->_M_node_count = 0; + } + private: void _M_initialize() @@ -514,11 +638,11 @@ { return this->_M_impl._M_header._M_right; } _Link_type - _M_begin() _GLIBCXX_NOEXCEPT + _M_begin() const _GLIBCXX_NOEXCEPT { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } _Const_Link_type - _M_begin() const _GLIBCXX_NOEXCEPT + _M_cbegin() const _GLIBCXX_NOEXCEPT { return static_cast<_Const_Link_type> (this->_M_impl._M_header._M_parent); @@ -529,7 +653,7 @@ { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); } _Const_Link_type - _M_end() const _GLIBCXX_NOEXCEPT + _M_cend() const _GLIBCXX_NOEXCEPT { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); } static const_reference @@ -603,9 +727,9 @@ const key_type& __k); #if __cplusplus >= 201103L - template + template iterator - _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v); + _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&); iterator _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); @@ -624,9 +748,10 @@ iterator _M_insert_equal_lower_node(_Link_type __z); #else - iterator - _M_insert_(_Base_ptr __x, _Base_ptr __y, - const value_type& __v); + template + iterator + _M_insert_(_Base_ptr __x, _Base_ptr __y, + const value_type& __v, _NodeGen&); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 233. Insertion hints in associative containers. @@ -637,8 +762,16 @@ _M_insert_equal_lower(const value_type& __x); #endif + template + _Link_type + _M_copy(_Link_type __x, _Link_type __p, _NodeGen&); + _Link_type - _M_copy(_Const_Link_type __x, _Link_type __p); + _M_copy(_Link_type __x, _Link_type __p) + { + _Alloc_node __an(*this); + return _M_copy(__x, __p, __an); + } void _M_erase(_Link_type __x); @@ -688,7 +821,7 @@ _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) { - if (__x._M_root() != 0) + if (__x._M_root() != nullptr) { _M_root() = _M_copy(__x._M_begin(), _M_end()); _M_leftmost() = _S_minimum(_M_root()); @@ -792,14 +925,30 @@ iterator _M_insert_equal(_Arg&& __x); - template + template iterator - _M_insert_unique_(const_iterator __position, _Arg&& __x); + _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&); template - iterator - _M_insert_equal_(const_iterator __position, _Arg&& __x); + iterator + _M_insert_unique_(const_iterator __pos, _Arg&& __x) + { + _Alloc_node __an(*this); + return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an); + } + template + iterator + _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&); + + template + iterator + _M_insert_equal_(const_iterator __pos, _Arg&& __x) + { + _Alloc_node __an(*this); + return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); + } + template pair _M_emplace_unique(_Args&&... __args); @@ -822,11 +971,28 @@ iterator _M_insert_equal(const value_type& __x); + template + iterator + _M_insert_unique_(const_iterator __pos, const value_type& __x, + _NodeGen&); + iterator - _M_insert_unique_(const_iterator __position, const value_type& __x); + _M_insert_unique_(const_iterator __pos, const value_type& __x) + { + _Alloc_node __an(*this); + return _M_insert_unique_(__pos, __x, __an); + } + template + iterator + _M_insert_equal_(const_iterator __pos, const value_type& __x, + _NodeGen&); iterator - _M_insert_equal_(const_iterator __position, const value_type& __x); + _M_insert_equal_(const_iterator __pos, const value_type& __x) + { + _Alloc_node __an(*this); + return _M_insert_equal_(__pos, __x, __an); + } #endif template @@ -906,10 +1072,7 @@ clear() _GLIBCXX_NOEXCEPT { _M_erase(_M_begin()); - _M_leftmost() = _M_end(); - _M_root() = 0; - _M_rightmost() = _M_end(); - _M_impl._M_node_count = 0; + _M_impl._M_reset(); } // Set operations. @@ -928,7 +1091,7 @@ const_iterator lower_bound(const key_type& __k) const - { return _M_lower_bound(_M_begin(), _M_end(), __k); } + { return _M_lower_bound(_M_cbegin(), _M_cend(), __k); } iterator upper_bound(const key_type& __k) @@ -936,7 +1099,7 @@ const_iterator upper_bound(const key_type& __k) const - { return _M_upper_bound(_M_begin(), _M_end(), __k); } + { return _M_upper_bound(_M_cbegin(), _M_cend(), __k); } pair equal_range(const key_type& __k); @@ -949,9 +1112,17 @@ __rb_verify() const; #if __cplusplus >= 201103L - bool - _M_move_assign(_Rb_tree&); + _Rb_tree& + operator=(_Rb_tree&&) noexcept(_Alloc_traits::_S_nothrow_move()); + template + void + _M_assign_unique(_Iterator, _Iterator); + + template + void + _M_assign_equal(_Iterator, _Iterator); + private: // Move elements from container with equal allocator. void @@ -1027,7 +1198,7 @@ : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) { using __eq = integral_constant; - if (__x._M_root() != 0) + if (__x._M_root() != nullptr) _M_move_data(__x, __eq()); } @@ -1060,7 +1231,11 @@ _M_move_data(__x, std::true_type()); else { - _M_root() = _M_copy(__x._M_begin(), _M_end()); + _Alloc_node __an(*this); + auto __lbd = + [&__an](value_type& __val) + { return __an(std::move_if_noexcept(__val)); }; + _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); _M_leftmost() = _S_minimum(_M_root()); _M_rightmost() = _S_maximum(_M_root()); _M_impl._M_node_count = __x._M_impl._M_node_count; @@ -1069,9 +1244,10 @@ template - bool + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_move_assign(_Rb_tree& __x) + operator=(_Rb_tree&& __x) + noexcept(_Alloc_traits::_S_nothrow_move()) { _M_impl._M_key_compare = __x._M_impl._M_key_compare; if (_Alloc_traits::_S_propagate_on_move_assign() @@ -1079,14 +1255,56 @@ || _M_get_Node_allocator() == __x._M_get_Node_allocator()) { clear(); - if (__x._M_root() != 0) + if (__x._M_root() != nullptr) _M_move_data(__x, std::true_type()); std::__alloc_on_move(_M_get_Node_allocator(), __x._M_get_Node_allocator()); - return true; + return *this; } - return false; + + // Try to move each node reusing existing nodes and copying __x nodes + // structure. + _Reuse_or_alloc_node __roan(_M_impl._M_header, *this); + _M_impl._M_reset(); + if (__x._M_root() != nullptr) + { + auto __lbd = + [&__roan](value_type& __val) + { return __roan(std::move_if_noexcept(__val)); }; + _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); + _M_leftmost() = _S_minimum(_M_root()); + _M_rightmost() = _S_maximum(_M_root()); + _M_impl._M_node_count = __x._M_impl._M_node_count; + __x.clear(); + } + return *this; } + + template + template + void + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_assign_unique(_Iterator __first, _Iterator __last) + { + _Reuse_or_alloc_node __roan(this->_M_impl._M_header, *this); + _M_impl._M_reset(); + for (; __first != __last; ++__first) + _M_insert_unique_(end(), *__first, __roan); + } + + template + template + void + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_assign_equal(_Iterator __first, _Iterator __last) + { + _Reuse_or_alloc_node __roan(this->_M_impl._M_header, *this); + _M_impl._M_reset(); + for (; __first != __last; ++__first) + _M_insert_equal_(end(), *__first, __roan); + } #endif template= 201103L if (_Alloc_traits::_S_propagate_on_copy_assign()) { @@ -1107,19 +1324,26 @@ if (!_Alloc_traits::_S_always_equal() && __this_alloc != __that_alloc) { + // Replacement allocator cannot free existing storage, we need + // to erase nodes first. + clear(); std::__alloc_on_copy(__this_alloc, __that_alloc); } } #endif + + _Reuse_or_alloc_node __roan(this->_M_impl._M_header, *this); + _M_impl._M_reset(); _M_impl._M_key_compare = __x._M_impl._M_key_compare; if (__x._M_root() != 0) { - _M_root() = _M_copy(__x._M_begin(), _M_end()); + _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan); _M_leftmost() = _S_minimum(_M_root()); _M_rightmost() = _S_maximum(_M_root()); _M_impl._M_node_count = __x._M_impl._M_node_count; } } + return *this; } @@ -1126,27 +1350,31 @@ template #if __cplusplus >= 201103L - template + template +#else + template #endif - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_(_Base_ptr __x, _Base_ptr __p, #if __cplusplus >= 201103L - _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) + _Arg&& __v, #else - _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v) + const _Val& __v, #endif - { - bool __insert_left = (__x != 0 || __p == _M_end() - || _M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key(__p))); + _NodeGen& __node_gen) + { + bool __insert_left = (__x != 0 || __p == _M_end() + || _M_impl._M_key_compare(_KeyOfValue()(__v), + _S_key(__p))); - _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); + _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); - _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, - this->_M_impl._M_header); - ++_M_impl._M_node_count; - return iterator(__z); - } + _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, + this->_M_impl._M_header); + ++_M_impl._M_node_count; + return iterator(__z); + } template @@ -1198,40 +1426,41 @@ } template - typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type - _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: - _M_copy(_Const_Link_type __x, _Link_type __p) - { - // Structural copy. __x and __p must be non-null. - _Link_type __top = _M_clone_node(__x); - __top->_M_parent = __p; + typename _Compare, typename _Alloc> + template + typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type + _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: + _M_copy(_Link_type __x, _Link_type __p, _NodeGen& __node_gen) + { + // Structural copy. __x and __p must be non-null. + _Link_type __top = _M_clone_node(__x, __node_gen); + __top->_M_parent = __p; - __try - { - if (__x->_M_right) - __top->_M_right = _M_copy(_S_right(__x), __top); - __p = __top; - __x = _S_left(__x); + __try + { + if (__x->_M_right) + __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); + __p = __top; + __x = _S_left(__x); - while (__x != 0) - { - _Link_type __y = _M_clone_node(__x); - __p->_M_left = __y; - __y->_M_parent = __p; - if (__x->_M_right) - __y->_M_right = _M_copy(_S_right(__x), __y); - __p = __y; - __x = _S_left(__x); - } - } - __catch(...) - { - _M_erase(__top); - __throw_exception_again; - } - return __top; - } + while (__x != 0) + { + _Link_type __y = _M_clone_node(__x, __node_gen); + __p->_M_left = __y; + __y->_M_parent = __p; + if (__x->_M_right) + __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); + __p = __y; + __x = _S_left(__x); + } + } + __catch(...) + { + _M_erase(__top); + __throw_exception_again; + } + return __top; + } template @@ -1244,7 +1473,7 @@ { _M_erase(_S_right(__x)); _Link_type __y = _S_left(__x); - _M_destroy_node(__x); + _M_drop_node(__x); __x = __y; } } @@ -1353,8 +1582,8 @@ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: equal_range(const _Key& __k) const { - _Const_Link_type __x = _M_begin(); - _Const_Link_type __y = _M_end(); + _Const_Link_type __x = _M_cbegin(); + _Const_Link_type __y = _M_cend(); while (__x != 0) { if (_M_impl._M_key_compare(_S_key(__x), __k)) @@ -1392,10 +1621,9 @@ _M_leftmost() = __t._M_leftmost(); _M_rightmost() = __t._M_rightmost(); _M_root()->_M_parent = _M_end(); + _M_impl._M_node_count = __t._M_impl._M_node_count; - __t._M_root() = 0; - __t._M_leftmost() = __t._M_end(); - __t._M_rightmost() = __t._M_end(); + __t._M_impl._M_reset(); } } else if (__t._M_root() == 0) @@ -1404,10 +1632,9 @@ __t._M_leftmost() = _M_leftmost(); __t._M_rightmost() = _M_rightmost(); __t._M_root()->_M_parent = __t._M_end(); + __t._M_impl._M_node_count = _M_impl._M_node_count; - _M_root() = 0; - _M_leftmost() = _M_end(); - _M_rightmost() = _M_end(); + _M_impl._M_reset(); } else { @@ -1417,9 +1644,9 @@ _M_root()->_M_parent = _M_end(); __t._M_root()->_M_parent = __t._M_end(); + std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); } // No need to swap header's color as it does not change. - std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), @@ -1498,9 +1725,12 @@ = _M_get_insert_unique_pos(_KeyOfValue()(__v)); if (__res.second) - return _Res(_M_insert_(__res.first, __res.second, - _GLIBCXX_FORWARD(_Arg, __v)), - true); + { + _Alloc_node __an(*this); + return _Res(_M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v), __an), + true); + } return _Res(iterator(static_cast<_Link_type>(__res.first)), false); } @@ -1520,7 +1750,9 @@ { pair<_Base_ptr, _Base_ptr> __res = _M_get_insert_equal_pos(_KeyOfValue()(__v)); - return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v)); + _Alloc_node __an(*this); + return _M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v), __an); } template #if __cplusplus >= 201103L - template + template +#else + template #endif - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_unique_(const_iterator __position, #if __cplusplus >= 201103L - _M_insert_unique_(const_iterator __position, _Arg&& __v) + _Arg&& __v, #else - _M_insert_unique_(const_iterator __position, const _Val& __v) + const _Val& __v, #endif + _NodeGen& __node_gen) { pair<_Base_ptr, _Base_ptr> __res = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); @@ -1600,7 +1836,8 @@ if (__res.second) return _M_insert_(__res.first, __res.second, - _GLIBCXX_FORWARD(_Arg, __v)); + _GLIBCXX_FORWARD(_Arg, __v), + __node_gen); return iterator(static_cast<_Link_type>(__res.first)); } @@ -1662,25 +1899,30 @@ template #if __cplusplus >= 201103L - template + template +#else + template #endif - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_equal_(const_iterator __position, #if __cplusplus >= 201103L - _M_insert_equal_(const_iterator __position, _Arg&& __v) + _Arg&& __v, #else - _M_insert_equal_(const_iterator __position, const _Val& __v) + const _Val& __v, #endif - { - pair<_Base_ptr, _Base_ptr> __res - = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); + _NodeGen& __node_gen) + { + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); - if (__res.second) - return _M_insert_(__res.first, __res.second, - _GLIBCXX_FORWARD(_Arg, __v)); + if (__res.second) + return _M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v), + __node_gen); - return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); - } + return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); + } #if __cplusplus >= 201103L template(__res.first)), false); } __catch(...) { - _M_destroy_node(__z); + _M_drop_node(__z); __throw_exception_again; } } @@ -1775,7 +2017,7 @@ } __catch(...) { - _M_destroy_node(__z); + _M_drop_node(__z); __throw_exception_again; } } @@ -1796,12 +2038,12 @@ if (__res.second) return _M_insert_node(__res.first, __res.second, __z); - _M_destroy_node(__z); + _M_drop_node(__z); return iterator(static_cast<_Link_type>(__res.first)); } __catch(...) { - _M_destroy_node(__z); + _M_drop_node(__z); __throw_exception_again; } } @@ -1826,7 +2068,7 @@ } __catch(...) { - _M_destroy_node(__z); + _M_drop_node(__z); __throw_exception_again; } } @@ -1839,8 +2081,9 @@ _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: _M_insert_unique(_II __first, _II __last) { + _Alloc_node __an(*this); for (; __first != __last; ++__first) - _M_insert_unique_(end(), *__first); + _M_insert_unique_(end(), *__first, __an); } template:: _M_insert_equal(_II __first, _II __last) { + _Alloc_node __an(*this); for (; __first != __last; ++__first) - _M_insert_equal_(end(), *__first); + _M_insert_equal_(end(), *__first, __an); } template(_Rb_tree_rebalance_for_erase (const_cast<_Base_ptr>(__position._M_node), this->_M_impl._M_header)); - _M_destroy_node(__y); + _M_drop_node(__y); --_M_impl._M_node_count; } @@ -1923,7 +2167,7 @@ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: find(const _Key& __k) const { - const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); + const_iterator __j = _M_lower_bound(_M_cbegin(), _M_cend(), __k); return (__j == end() || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; Index: testsuite/23_containers/map/allocator/copy_assign.cc =================================================================== --- testsuite/23_containers/map/allocator/copy_assign.cc (revision 211713) +++ testsuite/23_containers/map/allocator/copy_assign.cc (working copy) @@ -59,9 +59,33 @@ VERIFY(1 == v2.get_allocator().get_personality()); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator> alloc_type; + typedef std::map, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1 = { { 0, 0 }, { 1, 1 } }; + test_type v2 = { { 2, 2 }, { 3, 3 } }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + v1 = v2; + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + int main() { test01(); test02(); + test03(); return 0; } Index: testsuite/23_containers/map/allocator/init-list.cc =================================================================== --- testsuite/23_containers/map/allocator/init-list.cc (revision 0) +++ testsuite/23_containers/map/allocator/init-list.cc (working copy) @@ -0,0 +1,55 @@ +// 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 +// . +// + +// { dg-options "-std=gnu++11" } + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator> alloc_type; + typedef std::map, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1; + v1 = { { 0, 0 }, { 1, 1 } }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + VERIFY( allocs != 0 ); + VERIFY( constructs != 0 ); + + // Check no allocation on list initialization. + v1 = { { 4, 4 }, { 5, 5 } }; + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + +int main() +{ + test01(); +} Index: testsuite/23_containers/map/allocator/move_assign.cc =================================================================== --- testsuite/23_containers/map/allocator/move_assign.cc (revision 211713) +++ testsuite/23_containers/map/allocator/move_assign.cc (working copy) @@ -43,8 +43,8 @@ v2 = { test_type::value_type{} }; v2 = std::move(v1); - VERIFY(1 == v1.get_allocator().get_personality()); - VERIFY(2 == v2.get_allocator().get_personality()); + VERIFY( 1 == v1.get_allocator().get_personality() ); + VERIFY( 2 == v2.get_allocator().get_personality() ); } void test02() @@ -60,14 +60,47 @@ v2 = { test_type::value_type{} }; v2 = std::move(v1); - VERIFY(0 == v1.get_allocator().get_personality()); - VERIFY(1 == v2.get_allocator().get_personality()); + VERIFY( 0 == v1.get_allocator().get_personality() ); + VERIFY( 1 == v2.get_allocator().get_personality() ); VERIFY( it == v2.begin() ); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef propagating_allocator, false, + tracker_allocator>> + alloc_type; + typedef std::map, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1(alloc_type(1)); + v1 = { { 0, 0 }, { 1, 1 } }; + + test_type v2(alloc_type(2)); + v2 = { { 2, 2 }, { 3, 3 } }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + // Check no allocation on move assignment with non propagating allocators. + v1 = std::move(v2); + + VERIFY( 1 == v1.get_allocator().get_personality() ); + VERIFY( 2 == v2.get_allocator().get_personality() ); + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + int main() { test01(); test02(); + test03(); return 0; } Index: testsuite/util/testsuite_allocator.h =================================================================== --- testsuite/util/testsuite_allocator.h (revision 211713) +++ testsuite/util/testsuite_allocator.h (working copy) @@ -29,6 +29,7 @@ #include #include #include +#include #include namespace __gnu_test @@ -91,87 +92,87 @@ // tracker_allocator_counter to fulfill memory requests. This class // is templated on the target object type, but tracker isn't. template - class tracker_allocator - { - private: - typedef tracker_allocator_counter counter_type; + class tracker_allocator + { + private: + typedef tracker_allocator_counter counter_type; - public: - typedef T value_type; - typedef T* pointer; - typedef const T* const_pointer; - typedef T& reference; - typedef const T& const_reference; - typedef std::size_t size_type; - typedef std::ptrdiff_t difference_type; + public: + typedef T value_type; + typedef T* pointer; + typedef const T* const_pointer; + typedef T& reference; + typedef const T& const_reference; + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; - template struct rebind { typedef tracker_allocator other; }; + template struct rebind { typedef tracker_allocator other; }; - pointer - address(reference value) const _GLIBCXX_NOEXCEPT - { return std::__addressof(value); } + pointer + address(reference value) const _GLIBCXX_NOEXCEPT + { return std::__addressof(value); } - const_pointer - address(const_reference value) const _GLIBCXX_NOEXCEPT - { return std::__addressof(value); } + const_pointer + address(const_reference value) const _GLIBCXX_NOEXCEPT + { return std::__addressof(value); } - tracker_allocator() _GLIBCXX_USE_NOEXCEPT - { } + tracker_allocator() _GLIBCXX_USE_NOEXCEPT + { } - tracker_allocator(const tracker_allocator&) _GLIBCXX_USE_NOEXCEPT - { } + tracker_allocator(const tracker_allocator&) _GLIBCXX_USE_NOEXCEPT + { } - template - tracker_allocator(const tracker_allocator&) _GLIBCXX_USE_NOEXCEPT + template + tracker_allocator(const tracker_allocator&) _GLIBCXX_USE_NOEXCEPT + { } + + ~tracker_allocator() _GLIBCXX_USE_NOEXCEPT { } - ~tracker_allocator() _GLIBCXX_USE_NOEXCEPT - { } + size_type + max_size() const _GLIBCXX_USE_NOEXCEPT + { return size_type(-1) / sizeof(T); } - size_type - max_size() const _GLIBCXX_USE_NOEXCEPT - { return size_type(-1) / sizeof(T); } + pointer + allocate(size_type n, const void* = 0) + { return static_cast(counter_type::allocate(n * sizeof(T))); } - pointer - allocate(size_type n, const void* = 0) - { return static_cast(counter_type::allocate(n * sizeof(T))); } +#if __cplusplus >= 201103L + template + void + construct(U* p, Args&&... args) + { + ::new((void *)p) U(std::forward(args)...); + counter_type::construct(); + } -#if __cplusplus >= 201103L - template + template + void + destroy(U* p) + { + p->~U(); + counter_type::destroy(); + } +#else void - construct(U* p, Args&&... args) + construct(pointer p, const T& value) { - ::new((void *)p) U(std::forward(args)...); + ::new ((void *)p) T(value); counter_type::construct(); } - template void - destroy(U* p) + destroy(pointer p) { - p->~U(); + p->~T(); counter_type::destroy(); } -#else - void - construct(pointer p, const T& value) - { - ::new ((void *)p) T(value); - counter_type::construct(); - } - - void - destroy(pointer p) - { - p->~T(); - counter_type::destroy(); - } #endif - void - deallocate(pointer p, size_type num) - { counter_type::deallocate(p, num * sizeof(T)); } - }; + void + deallocate(pointer p, size_type num) + { counter_type::deallocate(p, num * sizeof(T)); } + }; template bool @@ -219,7 +220,16 @@ throw; } + // Helper to detect inconsistency between type used to instantiate an + // allocator and the underlying allocator value_type. + template + struct check_consistent_alloc_value_type; + template + struct check_consistent_alloc_value_type + { typedef T value_type; }; + // A simple allocator which can be constructed endowed of a given // "personality" (an integer), queried in operator== to simulate the // behavior of realworld "unequal" allocators (i.e., not exploiting @@ -244,26 +254,29 @@ } }; - template + template > class uneq_allocator - : private uneq_allocator_base + : private uneq_allocator_base, + public Alloc { + typedef __gnu_cxx::__alloc_traits AllocTraits; + public: - typedef std::size_t size_type; - typedef std::ptrdiff_t difference_type; - typedef Tp* pointer; - typedef const Tp* const_pointer; - typedef Tp& reference; - typedef const Tp& const_reference; - typedef Tp value_type; + typedef typename check_consistent_alloc_value_type::value_type + value_type; + typedef typename AllocTraits::size_type size_type; + typedef typename AllocTraits::pointer pointer; #if __cplusplus >= 201103L - typedef std::true_type propagate_on_container_swap; + typedef std::true_type propagate_on_container_swap; #endif template - struct rebind - { typedef uneq_allocator other; }; + struct rebind + { + typedef uneq_allocator::other> other; + }; uneq_allocator() _GLIBCXX_USE_NOEXCEPT : personality(0) { } @@ -272,7 +285,9 @@ : personality(person) { } template - uneq_allocator(const uneq_allocator& b) _GLIBCXX_USE_NOEXCEPT + uneq_allocator(const uneq_allocator::other>& b) + _GLIBCXX_USE_NOEXCEPT : personality(b.get_personality()) { } ~uneq_allocator() _GLIBCXX_USE_NOEXCEPT @@ -281,20 +296,9 @@ int get_personality() const { return personality; } pointer - address(reference x) const _GLIBCXX_NOEXCEPT - { return std::__addressof(x); } - - const_pointer - address(const_reference x) const _GLIBCXX_NOEXCEPT - { return std::__addressof(x); } - - pointer - allocate(size_type n, const void* = 0) + allocate(size_type n, const void* hint = 0) { - if (__builtin_expect(n > this->max_size(), false)) - std::__throw_bad_alloc(); - - pointer p = static_cast(::operator new(n * sizeof(Tp))); + pointer p = Alloc::allocate(n, hint); try { get_map().insert(map_type::value_type(reinterpret_cast(p), @@ -302,7 +306,7 @@ } catch(...) { - ::operator delete(p); + Alloc::deallocate(p, n); __throw_exception_again; } return p; @@ -309,7 +313,7 @@ } void - deallocate(pointer p, size_type) + deallocate(pointer p, size_type n) { bool test __attribute__((unused)) = true; @@ -323,34 +327,14 @@ VERIFY( it->second == personality ); get_map().erase(it); - ::operator delete(p); + Alloc::deallocate(p, n); } - size_type - max_size() const _GLIBCXX_USE_NOEXCEPT - { return size_type(-1) / sizeof(Tp); } - #if __cplusplus >= 201103L - template - void - construct(U* p, Args&&... args) - { ::new((void *)p) U(std::forward(args)...); } - - template - void - destroy(U* p) { p->~U(); } - // Not copy assignable... uneq_allocator& operator=(const uneq_allocator&) = delete; #else - void - construct(pointer p, const Tp& val) - { ::new((void *)p) Tp(val); } - - void - destroy(pointer p) { p->~Tp(); } - private: // Not assignable... uneq_allocator& @@ -358,21 +342,24 @@ #endif private: - // ... yet swappable! friend inline void swap(uneq_allocator& a, uneq_allocator& b) { std::swap(a.personality, b.personality); } - + template - friend inline bool - operator==(const uneq_allocator& a, const uneq_allocator& b) - { return a.personality == b.personality; } + friend inline bool + operator==(const uneq_allocator& a, + const uneq_allocator::other>& b) + { return a.personality == b.personality; } template - friend inline bool - operator!=(const uneq_allocator& a, const uneq_allocator& b) - { return !(a == b); } + friend inline bool + operator!=(const uneq_allocator& a, + const uneq_allocator::other>& b) + { return !(a == b); } int personality; }; @@ -379,10 +366,12 @@ #if __cplusplus >= 201103L // An uneq_allocator which can be used to test allocator propagation. - template - class propagating_allocator : public uneq_allocator + template> + class propagating_allocator : public uneq_allocator { - typedef uneq_allocator base_alloc; + typedef __gnu_cxx::__alloc_traits AllocTraits; + + typedef uneq_allocator base_alloc; base_alloc& base() { return *this; } const base_alloc& base() const { return *this; } void swap_base(base_alloc& b) { swap(b, this->base()); } @@ -393,7 +382,11 @@ // default allocator_traits::rebind_alloc would select // uneq_allocator::rebind so we must define rebind here template - struct rebind { typedef propagating_allocator other; }; + struct rebind + { + typedef propagating_allocator::other> other; + }; propagating_allocator(int i) noexcept : base_alloc(i) @@ -400,8 +393,9 @@ { } template - propagating_allocator(const propagating_allocator& a) - noexcept + propagating_allocator(const propagating_allocator::other>& a) + noexcept : base_alloc(a) { } @@ -418,8 +412,8 @@ } template - propagating_allocator& - operator=(const propagating_allocator& a) noexcept + propagating_allocator& + operator=(const propagating_allocator& a) noexcept { static_assert(P2, "assigning propagating_allocator"); propagating_allocator(a).swap_base(*this); Index: testsuite/23_containers/set/allocator/copy_assign.cc =================================================================== --- testsuite/23_containers/set/allocator/copy_assign.cc (revision 211713) +++ testsuite/23_containers/set/allocator/copy_assign.cc (working copy) @@ -57,9 +57,33 @@ VERIFY(1 == v2.get_allocator().get_personality()); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator alloc_type; + typedef std::set, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1 = { 0, 1 }; + test_type v2 = { 2, 3 }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + v1 = v2; + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + int main() { test01(); test02(); + test03(); return 0; } Index: testsuite/23_containers/set/allocator/init-list.cc =================================================================== --- testsuite/23_containers/set/allocator/init-list.cc (revision 0) +++ testsuite/23_containers/set/allocator/init-list.cc (working copy) @@ -0,0 +1,55 @@ +// 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 +// . +// + +// { dg-options "-std=gnu++11" } + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator alloc_type; + typedef std::set, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1; + v1 = { 0, 1 }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + VERIFY( allocs != 0 ); + VERIFY( constructs != 0 ); + + // Check no allocation on list initialization. + v1 = { 4, 5 }; + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + +int main() +{ + test01(); +} Index: testsuite/23_containers/set/allocator/move_assign.cc =================================================================== --- testsuite/23_containers/set/allocator/move_assign.cc (revision 211713) +++ testsuite/23_containers/set/allocator/move_assign.cc (working copy) @@ -59,9 +59,40 @@ VERIFY( it == v2.begin() ); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef propagating_allocator> alloc_type; + typedef std::set, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1(alloc_type(1)); + v1 = { 0, 1 }; + + test_type v2(alloc_type(2)); + v2 = { 2, 3 }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + // Check no allocation on move assignment with non propagating allocators. + v1 = std::move(v2); + + VERIFY( 1 == v1.get_allocator().get_personality() ); + VERIFY( 2 == v2.get_allocator().get_personality() ); + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + int main() { test01(); test02(); + test03(); return 0; } Index: testsuite/23_containers/multimap/allocator/copy_assign.cc =================================================================== --- testsuite/23_containers/multimap/allocator/copy_assign.cc (revision 211713) +++ testsuite/23_containers/multimap/allocator/copy_assign.cc (working copy) @@ -59,9 +59,33 @@ VERIFY(1 == v2.get_allocator().get_personality()); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator> alloc_type; + typedef std::multimap, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1 = { { 1, 1 }, { 1, 1 } }; + test_type v2 = { { 2, 2 }, { 2, 2 } }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + v1 = v2; + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + int main() { test01(); test02(); + test03(); return 0; } Index: testsuite/23_containers/multimap/allocator/init-list.cc =================================================================== --- testsuite/23_containers/multimap/allocator/init-list.cc (revision 0) +++ testsuite/23_containers/multimap/allocator/init-list.cc (working copy) @@ -0,0 +1,55 @@ +// 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 +// . +// + +// { dg-options "-std=gnu++11" } + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator> alloc_type; + typedef std::multimap, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1; + v1 = { { 0, 0 }, { 0, 0 } }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + VERIFY( allocs != 0 ); + VERIFY( constructs != 0 ); + + // Check no allocation on list initialization. + v1 = { { 1, 1 }, { 1, 1 } }; + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + +int main() +{ + test01(); +} Index: testsuite/23_containers/multimap/allocator/move_assign.cc =================================================================== --- testsuite/23_containers/multimap/allocator/move_assign.cc (revision 211713) +++ testsuite/23_containers/multimap/allocator/move_assign.cc (working copy) @@ -61,9 +61,42 @@ VERIFY( it == v2.begin() ); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef propagating_allocator, false, + tracker_allocator>> + alloc_type; + typedef std::multimap, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1(alloc_type(1)); + v1 = { { 1, 1 }, { 1, 1 } }; + + test_type v2(alloc_type(2)); + v2 = { { 2, 2 }, { 2, 2 } }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + // Check no allocation on move assignment with non propagating allocators. + v1 = std::move(v2); + + VERIFY( 1 == v1.get_allocator().get_personality() ); + VERIFY( 2 == v2.get_allocator().get_personality() ); + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + int main() { test01(); test02(); + test03(); return 0; } Index: testsuite/23_containers/multiset/allocator/copy_assign.cc =================================================================== --- testsuite/23_containers/multiset/allocator/copy_assign.cc (revision 211713) +++ testsuite/23_containers/multiset/allocator/copy_assign.cc (working copy) @@ -57,9 +57,33 @@ VERIFY(1 == v2.get_allocator().get_personality()); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator alloc_type; + typedef std::multiset, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1 = { 0, 0 }; + test_type v2 = { 1, 1 }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + v1 = v2; + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + int main() { test01(); test02(); + test03(); return 0; } Index: testsuite/23_containers/multiset/allocator/init-list.cc =================================================================== --- testsuite/23_containers/multiset/allocator/init-list.cc (revision 0) +++ testsuite/23_containers/multiset/allocator/init-list.cc (working copy) @@ -0,0 +1,55 @@ +// 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 +// . +// + +// { dg-options "-std=gnu++11" } + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator alloc_type; + typedef std::multiset, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1; + v1 = { 0, 0 }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + VERIFY( allocs != 0 ); + VERIFY( constructs != 0 ); + + // Check no allocation on list initialization. + v1 = { 1, 1 }; + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + +int main() +{ + test01(); +} Index: testsuite/23_containers/multiset/allocator/move_assign.cc =================================================================== --- testsuite/23_containers/multiset/allocator/move_assign.cc (revision 211713) +++ testsuite/23_containers/multiset/allocator/move_assign.cc (working copy) @@ -59,9 +59,40 @@ VERIFY( it == v2.begin() ); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef propagating_allocator> alloc_type; + typedef std::multiset, alloc_type> test_type; + + tracker_allocator_counter::reset(); + + test_type v1(alloc_type(1)); + v1 = { 0, 0 }; + + test_type v2(alloc_type(2)); + v2 = { 2, 2 }; + + auto allocs = tracker_allocator_counter::get_allocation_count(); + auto constructs = tracker_allocator_counter::get_construct_count(); + + // Check no allocation on move assignment with non propagating allocators. + v1 = std::move(v2); + + VERIFY( 1 == v1.get_allocator().get_personality() ); + VERIFY( 2 == v2.get_allocator().get_personality() ); + + VERIFY( tracker_allocator_counter::get_allocation_count() == allocs ); + VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 ); +} + int main() { test01(); test02(); + test03(); return 0; }