Re: [v3] libstdc++/54296

[François Dumont <frs dot dumont at gmail dot com>]

On 09/05/2012 11:58 AM, Paolo Carlini wrote:
> Hi,
>
> On 09/04/2012 10:08 PM, François Dumont wrote:
> > Hi
> >
> >     I managed to do the test with Valgrind and so confirm the fix 
> > with the attached patch (unmodified since last proposal).
> Patch is Ok, thanks for your patience and thanks again for all your 
> great work on the unordered containers!
>
> Paolo.

    Attached patch applied. No problem Paolo, this is your job as 
maintainers to challenge the patches, no big deal. And being now able to 
run programs through Valgrind or Gdb is definitely more comfortable for me.

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.

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 190990)
+++ include/bits/hashtable.h	(working copy)
@@ -612,6 +612,15 @@
 	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 @@
       { 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 @@
       // 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,7 @@
 			_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);
@@ -1466,43 +1490,67 @@
       __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);
-      bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
+      _M_erase(__bkt, __prev_n, __n);
+      return 1;
+    }
 
-      // We found a matching node, start deallocation loop from it
-      std::size_t __next_bkt = __bkt;
-      __node_type* __next_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>::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);
+
+      // 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;
+
+      // _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);
+      __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));
+
+      // 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;
+	  __node_type* __p = __n->_M_next();
+	  _M_deallocate_node(__n);
+	  __n = __p;
+	  ++__result;
 	  --_M_element_count;
-	  ++__result;
-	  if (!__next_n)
-	    break;
-	  __next_bkt = _M_bucket_index(__next_n);
 	}
-      while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
+      while (__n != __n_last);
 
-      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;
+      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;
     }
 
Index: testsuite/23_containers/unordered_map/erase/54276.cc
===================================================================
--- testsuite/23_containers/unordered_map/erase/54276.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/erase/54276.cc	(revision 0)
@@ -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;
+}
Index: testsuite/23_containers/unordered_multimap/erase/54276.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/erase/54276.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/erase/54276.cc	(revision 0)
@@ -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;
+}