diff options
| -rw-r--r-- | libstdc++-v3/ChangeLog | 19 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/hashtable.h | 276 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/hashtable_policy.h | 19 | ||||
| -rw-r--r-- | libstdc++-v3/include/std/unordered_map | 1 | ||||
| -rw-r--r-- | libstdc++-v3/include/std/unordered_set | 1 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/23_containers/unordered_map/operators/2.cc | 91 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/util/testsuite_counter_type.h | 122 |
7 files changed, 371 insertions, 158 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 250c8be..69a77c5 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,22 @@ +2012-08-13 François Dumont <fdumont@gcc.gnu.org> + Ollie Wild <aaw@google.com> + + * include/bits/hashtable.h + (_Hashtable<>_M_insert_multi_node(hash_code, node_type*)): New. + (_Hashtable<>_M_insert(_Args&&, false_type)): Use latter. + (_Hashtable<>::_M_emplace(false_type, _Args&&...)): Likewise. + (_Hashtable<>::_M_insert_bucket): Replace by ... + (_Hashtable<>::_M_insert_unique_node(size_type, hash_code, node_type*)): + ... this, new. + (_Hashtable<>::_M_insert(_Args&&, true_type)): Use latter. + (_Hashtable<>::_M_emplace(true_type, _Args&&...)): Likewise. + * 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. + 2012-08-13 Marc Glisse <marc.glisse@inria.fr> PR libstdc++/54112 diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 2faf0b3..2018575 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -584,10 +584,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base* _M_get_previous_node(size_type __bkt, __node_base* __n); - template<typename _Arg> - iterator - _M_insert_bucket(_Arg&&, size_type, __hash_code); + // Insert node with hash code __code, in bucket bkt if no rehash (assumes + // no element with its key already present). Take ownership of the node, + // deallocate it on exception. + iterator + _M_insert_unique_node(size_type __bkt, __hash_code __code, + __node_type* __n); + // Insert node with hash code __code. Take ownership of the node, + // deallocate it on exception. + iterator + _M_insert_multi_node(__hash_code __code, __node_type* __n); template<typename... _Args> std::pair<iterator, bool> @@ -1214,42 +1221,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { // First build the node to get access to the hash code __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...); + const key_type& __k = this->_M_extract()(__node->_M_v); + __hash_code __code; __try { - const key_type& __k = this->_M_extract()(__node->_M_v); - __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__k, __code); - - if (__node_type* __p = _M_find_node(__bkt, __k, __code)) - { - // There is already an equivalent node, no insertion - _M_deallocate_node(__node); - return std::make_pair(iterator(__p), false); - } - - // We are going to insert this node - this->_M_store_code(__node, __code); - const __rehash_state& __saved_state - = _M_rehash_policy._M_state(); - std::pair<bool, std::size_t> __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, - _M_element_count, 1); - - if (__do_rehash.first) - { - _M_rehash(__do_rehash.second, __saved_state); - __bkt = _M_bucket_index(__k, __code); - } - - _M_insert_bucket_begin(__bkt, __node); - ++_M_element_count; - return std::make_pair(iterator(__node), true); + __code = this->_M_hash_code(__k); } __catch(...) { _M_deallocate_node(__node); __throw_exception_again; } + + size_type __bkt = _M_bucket_index(__k, __code); + if (__node_type* __p = _M_find_node(__bkt, __k, __code)) + { + // There is already an equivalent node, no insertion + _M_deallocate_node(__node); + return std::make_pair(iterator(__p), false); + } + + // Insert the node + return std::make_pair(_M_insert_unique_node(__bkt, __code, __node), + true); } template<typename _Key, typename _Value, @@ -1264,97 +1258,110 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_emplace(std::false_type, _Args&&... __args) { - const __rehash_state& __saved_state = _M_rehash_policy._M_state(); - std::pair<bool, std::size_t> __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, - _M_element_count, 1); - // First build the node to get its hash code. __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...); + + __hash_code __code; __try { - const key_type& __k = this->_M_extract()(__node->_M_v); - __hash_code __code = this->_M_hash_code(__k); - this->_M_store_code(__node, __code); - - // Second, do rehash if necessary. - if (__do_rehash.first) - _M_rehash(__do_rehash.second, __saved_state); - - // Third, find the node before an equivalent one. - size_type __bkt = _M_bucket_index(__k, __code); - __node_base* __prev = _M_find_before_node(__bkt, __k, __code); - - if (__prev) - { - // Insert after the node before the equivalent one. - __node->_M_nxt = __prev->_M_nxt; - __prev->_M_nxt = __node; - } - else - // The inserted node has no equivalent in the - // hashtable. We must insert the new node at the - // beginning of the bucket to preserve equivalent - // elements relative positions. - _M_insert_bucket_begin(__bkt, __node); - ++_M_element_count; - return iterator(__node); + __code = this->_M_hash_code(this->_M_extract()(__node->_M_v)); } __catch(...) { _M_deallocate_node(__node); __throw_exception_again; } + + return _M_insert_multi_node(__code, __node); } - // Insert v in bucket n (assumes no element with its key already present). template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, typename _Traits> - template<typename _Arg> - 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<bool, std::size_t> __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, - __do_rehash.second); - } + 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_unique_node(size_type __bkt, __hash_code __code, + __node_type* __node) + { + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); + std::pair<bool, std::size_t> __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); - __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) + __try + { + if (__do_rehash.first) + { _M_rehash(__do_rehash.second, __saved_state); + __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v), __code); + } - _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; - } - } + this->_M_store_code(__node, __code); + + // Always insert at the begining of the bucket. + _M_insert_bucket_begin(__bkt, __node); + ++_M_element_count; + return iterator(__node); + } + __catch(...) + { + _M_deallocate_node(__node); + __throw_exception_again; + } + } + + // Insert node, in bucket bkt if no rehash (assumes no element with its key + // already present). Take ownership of the node, deallocate it on exception. + template<typename _Key, typename _Value, + typename _Alloc, typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, + typename _Traits> + 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_multi_node(__hash_code __code, __node_type* __node) + { + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); + std::pair<bool, std::size_t> __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); + + __try + { + if (__do_rehash.first) + _M_rehash(__do_rehash.second, __saved_state); + + this->_M_store_code(__node, __code); + const key_type& __k = this->_M_extract()(__node->_M_v); + size_type __bkt = _M_bucket_index(__k, __code); + + // Find the node before an equivalent one. + __node_base* __prev = _M_find_before_node(__bkt, __k, __code); + if (__prev) + { + // Insert after the node before the equivalent one. + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; + } + else + // The inserted node has no equivalent in the + // hashtable. We must insert the new node at the + // beginning of the bucket to preserve equivalent + // elements relative positions. + _M_insert_bucket_begin(__bkt, __node); + ++_M_element_count; + return iterator(__node); + } + __catch(...) + { + _M_deallocate_node(__node); + __throw_exception_again; + } + } // Insert v if no element with its key is already present. template<typename _Key, typename _Value, @@ -1372,12 +1379,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { const key_type& __k = this->_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)); + return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true); } // Insert v unconditionally. @@ -1393,54 +1402,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_insert(_Arg&& __v, std::false_type) { - const __rehash_state& __saved_state = _M_rehash_policy._M_state(); - std::pair<bool, std::size_t> __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, - _M_element_count, 1); - - // First compute the hash code so that we don't do anything if - // it throws. + // First compute the hash code so that we don't do anything if it + // throws. __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); - __node_type* __node = nullptr; - __try - { - // Second allocate new node so that we don't rehash if it 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); - - // Third, find the node before an equivalent one. - size_type __bkt = _M_bucket_index(__node); - __node_base* __prev - = _M_find_before_node(__bkt, this->_M_extract()(__node->_M_v), - __code); - if (__prev) - { - // Insert after the node before the equivalent one. - __node->_M_nxt = __prev->_M_nxt; - __prev->_M_nxt = __node; - } - else - // The inserted node has no equivalent in the - // hashtable. We must insert the new node at the - // beginning of the bucket to preserve equivalent - // elements relative positions. - _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; - } - } + // Second allocate new node so that we don't rehash if it throws. + __node_type* __node = _M_allocate_node(std::forward<_Arg>(__v)); + return _M_insert_multi_node(__code, __node); + } template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 27790f2..6350ae6 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -577,8 +577,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __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<const key_type&>(__k), + std::tuple<>()); + return __h->_M_insert_unique_node(__n, __code, __p)->second; + } + return (__p->_M_v).second; } @@ -598,9 +603,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __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(std::move(__k)), + std::tuple<>()); + return __h->_M_insert_unique_node(__n, __code, __p)->second; + } + return (__p->_M_v).second; } diff --git a/libstdc++-v3/include/std/unordered_map b/libstdc++-v3/include/std/unordered_map index e77a297..9241f30 100644 --- a/libstdc++-v3/include/std/unordered_map +++ b/libstdc++-v3/include/std/unordered_map @@ -38,6 +38,7 @@ #include <utility> #include <type_traits> #include <initializer_list> +#include <tuple> #include <bits/stl_algobase.h> #include <bits/allocator.h> #include <bits/stl_function.h> // equal_to, _Identity, _Select1st diff --git a/libstdc++-v3/include/std/unordered_set b/libstdc++-v3/include/std/unordered_set index 739e0a4..4d4517b 100644 --- a/libstdc++-v3/include/std/unordered_set +++ b/libstdc++-v3/include/std/unordered_set @@ -38,6 +38,7 @@ #include <utility> #include <type_traits> #include <initializer_list> +#include <tuple> #include <bits/stl_algobase.h> #include <bits/allocator.h> #include <bits/stl_function.h> // equal_to, _Identity, _Select1st diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/operators/2.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/operators/2.cc new file mode 100644 index 0000000..8c32824 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/operators/2.cc @@ -0,0 +1,91 @@ +// 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 +// <http://www.gnu.org/licenses/>. + +// 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 <unordered_map> +#include <testsuite_hooks.h> +#include <testsuite_rvalref.h> +#include <testsuite_counter_type.h> + +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<int, Mapped> m1; + m1[0] = Mapped(); + + std::unordered_map<int, rvalstruct> m2; + m2[0] = rvalstruct(13); + + std::unordered_map<int, DefaultConstructibleType> m3; + VERIFY( m3[0].val == 123 ); + VERIFY( m3.size() == 1 ); + m3[0] = 2; + VERIFY( m3[0].val == 2 ); + + std::unordered_map<counter_type, int, + __gnu_test::counter_type_hasher> 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; +} diff --git a/libstdc++-v3/testsuite/util/testsuite_counter_type.h b/libstdc++-v3/testsuite/util/testsuite_counter_type.h new file mode 100644 index 0000000..2b7063d --- /dev/null +++ b/libstdc++-v3/testsuite/util/testsuite_counter_type.h @@ -0,0 +1,122 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. +// + +#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 |