aboutsummaryrefslogtreecommitdiff
path: root/libstdc++-v3
diff options
context:
space:
mode:
Diffstat (limited to 'libstdc++-v3')
-rw-r--r--libstdc++-v3/ChangeLog14
-rw-r--r--libstdc++-v3/include/bits/hashtable.h114
-rw-r--r--libstdc++-v3/testsuite/23_containers/unordered_map/erase/54276.cc103
-rw-r--r--libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/54276.cc101
4 files changed, 299 insertions, 33 deletions
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 <fdumont@gcc.gnu.org>
+
+ 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 <drepper@gmail.com>
* 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<typename... _Args>
@@ -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 _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_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 _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>::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
+// <http://www.gnu.org/licenses/>.
+//
+
+// { dg-options "-std=gnu++0x" }
+
+#include <set>
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+struct A
+{
+ int x;
+ static std::set<const A*> 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<const A*> 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<A, A, hasher> 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<A, A, hasher> 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
+// <http://www.gnu.org/licenses/>.
+//
+
+// { dg-options "-std=gnu++0x" }
+
+#include <set>
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+struct A
+{
+ int x;
+ static std::set<const A*> 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<const A*> 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<A, A, hasher> 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<A, A, hasher> 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;
+}
generated by cgit v1.1 at 2024-08-23 07:47:25 +0000