This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Value type of map need not be default copyable
Here is an other attempt. I took the time to refactor the hashtable
implementation. I prefer to rename _M_insert_node into
_M_insert_unique_node and use it also into _M_emplace implementation. I
introduce _M_insert_multi_node that is used in _M_insert and _M_emplace
when keys are not unique.
Your remark on using std::move rather than std::forward Marc made
sens but didn't work. I don't understand why but the new test is showing
that std::forward works. If anyone can explain why std::move doesn't
work I am interested.
For your question regarding how to include headers I just follow
current method. Normally it is done so to make headers more reusable but
in this case I agree that hashtable_policy.h can't be included without
<tuple> before. Should I put <tuple> include into hashtable_policy.h ?
Adding a declaration of std::tuple in hashtable_policy.h could make this
header less dependent on <tuple>, should I do so ?
2012-08-09 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.
Tested under linux x86_64, normal and debug mode.
Ok for trunk ?
François
On 08/10/2012 01:26 AM, Paolo Carlini wrote:
On 08/09/2012 11:22 PM, Marc Glisse wrote:
I don't know if std:: is needed, but it looks strange to have it only
on some functions:
std::forward_as_tuple(forward<key_type>(__k)),
Looking at this line again, you seem to be using std::forward on
something that is not a deduced parameter type. I guess it is
equivalent to std::move in this case, it just confuses me a bit.
Wanted to point out that yesterday. Please double check std::move.
I realize now that nobody is interested in std::cref, good ;)
Thanks!
Paolo.
Index: include/std/unordered_map
===================================================================
--- include/std/unordered_map (revision 190209)
+++ include/std/unordered_map (working copy)
@@ -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
Index: include/std/unordered_set
===================================================================
--- include/std/unordered_set (revision 190209)
+++ include/std/unordered_set (working copy)
@@ -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
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 190209)
+++ include/bits/hashtable.h (working copy)
@@ -584,10 +584,17 @@
__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 @@
{
// 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,98 +1258,111 @@
_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);
+ 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);
- if (__do_rehash.first)
- {
- const key_type& __k = this->_M_extract()(__v);
- __n = __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)
+ __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,
typename _Alloc, typename _ExtractKey, typename _Equal,
@@ -1372,12 +1379,14 @@
{
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,55 +1402,16 @@
_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);
+ // Second allocate new node so that we don't rehash if it throws.
+ __node_type* __node = _M_allocate_node(std::forward<_Arg>(__v));
- // 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;
- }
+ return _M_insert_multi_node(__code, __node);
}
-
template<typename _Key, typename _Value,
typename _Alloc, typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 190209)
+++ include/bits/hashtable_policy.h (working copy)
@@ -577,8 +577,13 @@
__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 @@
__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::forward<key_type>(__k)),
+ std::tuple<>());
+ return __h->_M_insert_unique_node(__n, __code, __p)->second;
+ }
+
return (__p->_M_v).second;
}
Index: testsuite/23_containers/unordered_map/operators/2.cc
===================================================================
--- testsuite/23_containers/unordered_map/operators/2.cc (revision 0)
+++ testsuite/23_containers/unordered_map/operators/2.cc (revision 0)
@@ -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;
+}
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
+// <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
+
Property changes on: testsuite/util/testsuite_counter_type.h
___________________________________________________________________
Added: svn:eol-style
+ native