re PR libstdc++/54296 (using the object in the map to erase element from the map crashes)

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.

From-SVN: r190991

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;
+}