From 439cd9b7c2a753a387db542125e4e568d89d9e9e Mon Sep 17 00:00:00 2001 From: fdumont Date: Wed, 5 Sep 2012 19:41:16 +0000 Subject: [PATCH] =?utf8?q?2012-09-05=20=20Fran=C3=A7ois=20Dumont=20=20?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit PR libstdc++/54296 * include/bits/hashtable.h (_M_erase(size_type, __node_base*, __node_type*)): New. (erase(const_iterator)): Use latter. (_M_erase(std::true_type, const key_type&)): New, likewise. (_M_erase(std::false_type, const key_type&)): New. Find all nodes matching the key before deallocating them so that the key doesn't get invalidated. (erase(const key_type&)): Use the new member functions. * testsuite/23_containers/unordered_map/erase/54296.cc: New. * testsuite/23_containers/unordered_multimap/erase/54296.cc: New. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@190991 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 14 +++ libstdc++-v3/include/bits/hashtable.h | 114 +++++++++++++++------ .../23_containers/unordered_map/erase/54276.cc | 103 +++++++++++++++++++ .../unordered_multimap/erase/54276.cc | 101 ++++++++++++++++++ 4 files changed, 299 insertions(+), 33 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/erase/54276.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/54276.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index fa11b34..707e474 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,17 @@ +2012-09-05 François Dumont + + PR libstdc++/54296 + * include/bits/hashtable.h (_M_erase(size_type, __node_base*, + __node_type*)): New. + (erase(const_iterator)): Use latter. + (_M_erase(std::true_type, const key_type&)): New, likewise. + (_M_erase(std::false_type, const key_type&)): New. Find all nodes + matching the key before deallocating them so that the key doesn't + get invalidated. + (erase(const key_type&)): Use the new member functions. + * testsuite/23_containers/unordered_map/erase/54296.cc: New. + * testsuite/23_containers/unordered_multimap/erase/54296.cc: New. + 2012-09-05 Ulrich Drepper * src/c++11/random.cc (random_device::_M_init): Check whether cpuid diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 2018575..44badc0 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -612,6 +612,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_insert(_Arg&&, std::false_type); + size_type + _M_erase(std::true_type, const key_type&); + + size_type + _M_erase(std::false_type, const key_type&); + + iterator + _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n); + public: // Emplace template @@ -636,7 +645,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return erase(const_iterator(__it)); } size_type - erase(const key_type&); + erase(const key_type& __k) + { return _M_erase(__unique_keys(), __k); } iterator erase(const_iterator, const_iterator); @@ -1430,7 +1440,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // is why we need buckets to contain the before begin to make // this research fast. __node_base* __prev_n = _M_get_previous_node(__bkt, __n); - if (__n == _M_bucket_begin(__bkt)) + return _M_erase(__bkt, __prev_n, __n); + } + + template + 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_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) + { + if (__prev_n == _M_buckets[__bkt]) _M_remove_bucket_begin(__bkt, __n->_M_next(), __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); else if (__n->_M_nxt) @@ -1457,7 +1481,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Traits>::size_type _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - erase(const key_type& __k) + _M_erase(std::true_type, const key_type& __k) + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__k, __code); + + // Look for the node before the first matching node. + __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); + if (!__prev_n) + return 0; + + // We found a matching node, erase it. + __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); + _M_erase(__bkt, __prev_n, __n); + return 1; + } + + template + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + _Traits>::size_type + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_erase(std::false_type, const key_type& __k) { __hash_code __code = this->_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__k, __code); @@ -1466,43 +1515,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); if (!__prev_n) return 0; + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 526. Is it undefined if a function in the standard changes + // in parameters? + // We use one loop to find all matching nodes and another to deallocate + // them so that the key stays valid during the first loop. It might be + // invalidated indirectly when destroying nodes. __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); - bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n; + __node_type* __n_last = __n; + std::size_t __n_last_bkt = __bkt; + do + { + __n_last = __n_last->_M_next(); + if (!__n_last) + break; + __n_last_bkt = _M_bucket_index(__n_last); + } + while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); - // We found a matching node, start deallocation loop from it - std::size_t __next_bkt = __bkt; - __node_type* __next_n = __n; + // Deallocate nodes. size_type __result = 0; - __node_type* __saved_n = nullptr; do { - __node_type* __p = __next_n; - __next_n = __p->_M_next(); - - // _GLIBCXX_RESOLVE_LIB_DEFECTS - // 526. Is it undefined if a function in the standard changes - // in parameters? - if (std::__addressof(this->_M_extract()(__p->_M_v)) - != std::__addressof(__k)) - _M_deallocate_node(__p); - else - __saved_n = __p; - --_M_element_count; + __node_type* __p = __n->_M_next(); + _M_deallocate_node(__n); + __n = __p; ++__result; - if (!__next_n) - break; - __next_bkt = _M_bucket_index(__next_n); + --_M_element_count; } - while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n)); - - if (__saved_n) - _M_deallocate_node(__saved_n); - if (__is_bucket_begin) - _M_remove_bucket_begin(__bkt, __next_n, __next_bkt); - else if (__next_n && __next_bkt != __bkt) - _M_buckets[__next_bkt] = __prev_n; - if (__prev_n) - __prev_n->_M_nxt = __next_n; + while (__n != __n_last); + + if (__prev_n == _M_buckets[__bkt]) + _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); + else if (__n_last && __n_last_bkt != __bkt) + _M_buckets[__n_last_bkt] = __prev_n; + __prev_n->_M_nxt = __n_last; return __result; } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/erase/54276.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/erase/54276.cc new file mode 100644 index 0000000..40a5486 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/erase/54276.cc @@ -0,0 +1,103 @@ +// 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 +// . +// + +// { dg-options "-std=gnu++0x" } + +#include +#include +#include + +bool test __attribute__((unused)) = true; + +struct A +{ + int x; + static std::set destroyed; + + A() + { destroyed.erase(this); } + + A(const A& a) + : x(a.x) + { destroyed.erase(this); } + + ~A() + { destroyed.insert(this); } + + bool + operator==(const A& other) const + { + VERIFY( destroyed.find(this) == destroyed.end() ); + VERIFY( destroyed.find(&other) == destroyed.end() ); + return x == other.x; + } +}; + +std::set A::destroyed; + +struct hasher +{ + std::size_t operator()(const A& a) const + { + VERIFY( A::destroyed.find(&a) == A::destroyed.end() ); + return a.x / 10; + } +}; + +void test01() +{ + typedef std::unordered_map UMap; + UMap map; + + A::destroyed.clear(); + A a; + a.x = 0; + map.insert({a, a}); + a.x = 1; + map.insert({a, a}); + VERIFY( map.size() == 2 ); + std::size_t bkt = map.bucket(a); + VERIFY( map.bucket_size(bkt) == 2 ); + + VERIFY( map.erase( map.begin(bkt)->first ) == 1 ); +} + +void test02() +{ + typedef std::unordered_map UMap; + UMap map; + + A::destroyed.clear(); + A a; + a.x = 0; + map.insert({a, a}); + a.x = 1; + map.insert({a, a}); + VERIFY( map.size() == 2 ); + std::size_t bkt = map.bucket(a); + VERIFY( map.bucket_size(bkt) == 2 ); + + VERIFY( map.erase( map.begin(bkt)->second ) == 1 ); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/54276.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/54276.cc new file mode 100644 index 0000000..1cfb734 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/54276.cc @@ -0,0 +1,101 @@ +// 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 +// . +// + +// { dg-options "-std=gnu++0x" } + +#include +#include +#include + +bool test __attribute__((unused)) = true; + +struct A +{ + int x; + static std::set destroyed; + + A() + { destroyed.erase(this); } + + A(const A& a) + : x(a.x) + { destroyed.erase(this); } + + ~A() + { destroyed.insert(this); } + + bool + operator==(const A& other) const + { + VERIFY( destroyed.find(this) == destroyed.end() ); + VERIFY( destroyed.find(&other) == destroyed.end() ); + return x == other.x; + } +}; + +std::set A::destroyed; + +struct hasher +{ + std::size_t operator()(const A& a) const + { + VERIFY( A::destroyed.find(&a) == A::destroyed.end() ); + return a.x / 10; + } +}; + +void test01() +{ + typedef std::unordered_multimap UMMap; + UMMap map; + + A::destroyed.clear(); + A a; + a.x = 0; + map.insert({a, a}); + map.insert({a, a}); + VERIFY( map.size() == 2 ); + std::size_t bkt = map.bucket(a); + VERIFY( map.bucket_size(bkt) == 2 ); + + VERIFY( map.erase( map.begin(bkt)->first ) == 2 ); +} + +void test02() +{ + typedef std::unordered_multimap UMMap; + UMMap map; + + A::destroyed.clear(); + A a; + a.x = 0; + map.insert({a, a}); + map.insert({a, a}); + VERIFY( map.size() == 2 ); + std::size_t bkt = map.bucket(a); + VERIFY( map.bucket_size(bkt) == 2 ); + + VERIFY( map.erase( map.begin(bkt)->second ) == 2 ); +} + +int main() +{ + test01(); + test02(); + return 0; +} -- 2.7.4