From 0f1462579e348656b9a5549721f926d6f5894e1c Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Tue, 9 Jan 2018 21:05:10 +0000 Subject: [PATCH] re PR libstdc++/83709 (Inserting duplicates into an unordered associative containers causes the container to invalidate iterators) MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2018-01-09 François Dumont PR libstdc++/83709 * 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(_Arg&&, const _NodeGen&, true_type, size_t)): Add __n_elt parameter, defaulted to 1. (_Hashtable::_M_insert_unique_node): Likewise. Use it to call rehash policy _M_need_rehash. (_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. From-SVN: r256396 --- libstdc++-v3/ChangeLog | 21 ++++++++ libstdc++-v3/include/bits/hashtable.h | 30 +++++++----- libstdc++-v3/include/bits/hashtable_policy.h | 49 +++++++++++++++---- .../unordered_map/insert/83709.cc | 43 ++++++++++++++++ .../unordered_set/insert/83709.cc | 42 ++++++++++++++++ 5 files changed, 164 insertions(+), 21 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/insert/83709.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/insert/83709.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index df96fcb3944..07dbb5faf46 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,24 @@ +2018-01-09 François Dumont + + PR libstdc++/83709 + * 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(_Arg&&, const _NodeGen&, true_type, size_t)): + Add __n_elt parameter, defaulted to 1. + (_Hashtable::_M_insert_unique_node): Likewise. Use it to call rehash + policy _M_need_rehash. + (_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. + 2018-01-09 Jonathan Wakely PR libstdc++/59253 (partial) diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 6cdcbc12aa6..af16e2c03cb 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -487,7 +487,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; } @@ -675,7 +675,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. @@ -704,12 +704,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert(_Arg&&, const _NodeGenerator&, std::true_type); + _M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1); template 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); @@ -719,7 +719,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template 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; @@ -729,7 +729,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template 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&); @@ -881,6 +881,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++; @@ -890,9 +891,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; } } @@ -1713,12 +1717,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 __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 { @@ -1816,7 +1821,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 { const key_type& __k = this->_M_extract()(__v); @@ -1828,7 +1834,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. @@ -1841,7 +1847,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 ab59b612441..3ff6b14a90f 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 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 inline typename std::iterator_traits<_Iterator>::difference_type @@ -74,10 +74,8 @@ namespace __detail template 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 void _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter&); + const _NodeGetter&, true_type); + + template + 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 + template + 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; 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 00000000000..16e4f033a48 --- /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 +// . + +#include +#include +#include + +void test01() +{ + std::unordered_map 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 00000000000..0a5a520122f --- /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 +// . + +#include +#include +#include + +void test01() +{ + std::unordered_set 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; +} -- 2.30.2