Hi
Bug confirmed, limited to range insertion on unordered_set and
unordered_map.
I had to specialize _M_insert_range for those containers. Now this
method maintains the theoretical number of elements to insert which is
used only if an insertion takes place.
I also took this oportunity to introduce a small change in
__distance_fw to report 0 only if __first == __last and do nothing in
this case.
* include/bits/hashtable_policy.h
(__distance_fwd(_Iterator, _Iterator, input_iterator_tag)): Return 1 if
__first != __last.
(_Insert_base::_M_insert_range(_Ite, _Ite, _NodeGetter,
true_type)): New.
(_Insert_base::_M_insert_range(_Ite, _Ite, _NodeGetter, false_type)):
Add false_type parameter.
(_Insert_base::insert): Adapt.
* include/bits/hashtable.h (_Hashtable::operator=(initializzr_list<>)):
Adapt.
(_Hashtable::_M_insert_unique_node): Add __n_elt parameter, defaulted
to 1.
(_Hashtable::_M_insert(_Arg&&, const _NodeGen&, true_type, size_t)):
Likewise.
(_Hashtable::_M_merge_unique): Pass target number of elements to add to
produce only 1 rehash if necessary.
* testsuite/23_containers/unordered_map/insert/83709.cc: New.
* testsuite/23_containers/unordered_set/insert/83709.cc: New.
Tested under Linux x86_64 normal and debug modes.
Ok to commit ?
François
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index e6108a6..1245d79 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -490,7 +490,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__reuse_or_alloc_node_type __roan(_M_begin(), *this);
_M_before_begin._M_nxt = nullptr;
clear();
- this->_M_insert_range(__l.begin(), __l.end(), __roan);
+ this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
return *this;
}
@@ -678,7 +678,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// deallocate it on exception.
iterator
_M_insert_unique_node(size_type __bkt, __hash_code __code,
- __node_type* __n);
+ __node_type* __n, size_type __n_elt = 1);
// Insert node with hash code __code. Take ownership of the node,
// deallocate it on exception.
@@ -707,12 +707,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert(_Arg&&, const _NodeGenerator&, std::true_type);
+ _M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1);
template<typename _Arg, typename _NodeGenerator>
iterator
_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
- std::false_type __uk)
+ false_type __uk)
{
return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
__uk);
@@ -722,7 +722,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
iterator
_M_insert(const_iterator, _Arg&& __arg,
- const _NodeGenerator& __node_gen, std::true_type __uk)
+ const _NodeGenerator& __node_gen, true_type __uk)
{
return
_M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first;
@@ -732,7 +732,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
iterator
_M_insert(const_iterator, _Arg&&,
- const _NodeGenerator&, std::false_type);
+ const _NodeGenerator&, false_type);
size_type
_M_erase(std::true_type, const key_type&);
@@ -884,6 +884,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
+ auto __n_elt = __src.size();
for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
{
auto __pos = __i++;
@@ -893,9 +894,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (_M_find_node(__bkt, __k, __code) == nullptr)
{
auto __nh = __src.extract(__pos);
- _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+ _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
__nh._M_ptr = nullptr;
+ __n_elt = 1;
}
+ else if (__n_elt != 1)
+ --__n_elt;
}
}
@@ -1721,12 +1725,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_insert_unique_node(size_type __bkt, __hash_code __code,
- __node_type* __node)
+ __node_type* __node, size_type __n_elt)
-> iterator
{
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);
+ = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
+ __n_elt);
__try
{
@@ -1824,7 +1829,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, std::true_type)
+ _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type,
+ size_type __n_elt)
-> pair<iterator, bool>
{
const key_type& __k = this->_M_extract()(__v);
@@ -1836,7 +1842,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return std::make_pair(iterator(__n), false);
__n = __node_gen(std::forward<_Arg>(__v));
- return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true);
+ return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true };
}
// Insert v unconditionally.
@@ -1849,7 +1855,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_insert(const_iterator __hint, _Arg&& __v,
- const _NodeGenerator& __node_gen, std::false_type)
+ const _NodeGenerator& __node_gen, false_type)
-> iterator
{
// First compute the hash code so that we don't do anything if it
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index ab59b61..df6a0eb 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -58,12 +58,12 @@ namespace __detail
struct _Hashtable_base;
// Helper function: return distance(first, last) for forward
- // iterators, or 0 for input iterators.
+ // iterators, or 0/1 for input iterators.
template<class _Iterator>
inline typename std::iterator_traits<_Iterator>::difference_type
__distance_fw(_Iterator __first, _Iterator __last,
std::input_iterator_tag)
- { return 0; }
+ { return __first != __last ? 1 : 0; }
template<class _Iterator>
inline typename std::iterator_traits<_Iterator>::difference_type
@@ -74,10 +74,8 @@ namespace __detail
template<class _Iterator>
inline typename std::iterator_traits<_Iterator>::difference_type
__distance_fw(_Iterator __first, _Iterator __last)
- {
- typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
- return __distance_fw(__first, __last, _Tag());
- }
+ { return __distance_fw(__first, __last,
+ std::__iterator_category(__first)); }
struct _Identity
{
@@ -820,7 +818,12 @@ namespace __detail
template<typename _InputIterator, typename _NodeGetter>
void
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter&);
+ const _NodeGetter&, true_type);
+
+ template<typename _InputIterator, typename _NodeGetter>
+ void
+ _M_insert_range(_InputIterator __first, _InputIterator __last,
+ const _NodeGetter&, false_type);
public:
__ireturn_type
@@ -849,7 +852,7 @@ namespace __detail
{
__hashtable& __h = _M_conjure_hashtable();
__node_gen_type __node_gen(__h);
- return _M_insert_range(__first, __last, __node_gen);
+ return _M_insert_range(__first, __last, __node_gen, __unique_keys());
}
};
@@ -862,13 +865,41 @@ namespace __detail
_Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
_RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter& __node_gen)
+ const _NodeGetter& __node_gen, true_type)
+ {
+ size_type __n_elt = __detail::__distance_fw(__first, __last);
+ if (__n_elt == 0)
+ return;
+
+ __hashtable& __h = _M_conjure_hashtable();
+ for (; __first != __last; ++__first)
+ {
+ if (__h._M_insert(*__first, __node_gen, __unique_keys(),
+ __n_elt).second)
+ __n_elt = 1;
+ else if (__n_elt != 1)
+ --__n_elt;
+ }
+ }
+
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ template<typename _InputIterator, typename _NodeGetter>
+ void
+ _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>::
+ _M_insert_range(_InputIterator __first, _InputIterator __last,
+ const _NodeGetter& __node_gen, false_type)
{
using __rehash_type = typename __hashtable::__rehash_type;
using __rehash_state = typename __hashtable::__rehash_state;
using pair_type = std::pair<bool, std::size_t>;
size_type __n_elt = __detail::__distance_fw(__first, __last);
+ if (__n_elt == 0)
+ return;
__hashtable& __h = _M_conjure_hashtable();
__rehash_type& __rehash = __h._M_rehash_policy;
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/insert/83709.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/83709.cc
new file mode 100644
index 0000000..16e4f03
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/83709.cc
@@ -0,0 +1,43 @@
+// { dg-do run { target c++11 } }
+//
+// Copyright (C) 2018 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/>.
+
+#include <unordered_map>
+#include <string>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::unordered_map<std::string, std::string> m
+ { {"E", "E" }, { "T", "T" } };
+
+ VERIFY( m.size() == 2 );
+
+ auto bcount = m.bucket_count();
+
+ m.insert({ {"E", "E" }, { "T", "T" } });
+
+ VERIFY( m.size() == 2 );
+ VERIFY( m.bucket_count() == bcount );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/83709.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/83709.cc
new file mode 100644
index 0000000..0a5a520
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/83709.cc
@@ -0,0 +1,42 @@
+// { dg-do run { target c++11 } }
+//
+// Copyright (C) 2018 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/>.
+
+#include <unordered_set>
+#include <string>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::unordered_set<std::string> s { "E", "T" };
+
+ VERIFY( s.size() == 2 );
+
+ auto bcount = s.bucket_count();
+
+ s.insert({"E", "T" });
+
+ VERIFY( s.size() == 2 );
+ VERIFY( s.bucket_count() == bcount );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
