Patch committed: Fix erasing with reference in old hashtable code

Patch committed: Fix erasing with reference in old hashtable code

[Ian Lance Taylor]

[-- Attachment #1: Type: text/plain, Size: 655 bytes --]

This patch fixes a problem with the old hashtable::erase code when the
caller passes a reference to an element in the table, the element is not
the first in the bucket, but it is equal to the first in the bucket.
This is PR 49060, and the patch and test case are from that PR with
minor tweaks.  Bootstrapped and ran libstdc++ testsuite on
x86_64-unknown-linux-gnu.  Committed to mainline.

Ian


2011-05-25  David Tardon  <dtardon@redhat.com>

	PR libstdc++/49060
	* include/backward/hashtable.h (hashtable::erase): Don't crash if
	erasing first and another element with a reference to the other
	element.
	* testsuite/backward/hash_set/49060.cc: New.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: patc --]
[-- Type: text/x-diff, Size: 1996 bytes --]

Index: include/backward/hashtable.h
===================================================================
--- include/backward/hashtable.h	(revision 173685)
+++ include/backward/hashtable.h	(working copy)
@@ -898,13 +898,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  __next = __cur->_M_next;
 		}
 	    }
-	  if (_M_equals(_M_get_key(__first->_M_val), __key))
-	    {
-	      _M_buckets[__n] = __first->_M_next;
-	      _M_delete_node(__first);
-	      ++__erased;
-	      --_M_num_elements;
-	    }
+	  bool __delete_first = _M_equals(_M_get_key(__first->_M_val), __key);
 	  if (__saved_slot)
 	    {
 	      __next = __saved_slot->_M_next;
@@ -913,6 +907,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      ++__erased;
 	      --_M_num_elements;
 	    }
+	  if (__delete_first)
+	    {
+	      _M_buckets[__n] = __first->_M_next;
+	      _M_delete_node(__first);
+	      ++__erased;
+	      --_M_num_elements;
+	    }
 	}
       return __erased;
     }
Index: testsuite/backward/hash_set/49060.cc
===================================================================
--- testsuite/backward/hash_set/49060.cc	(revision 0)
+++ testsuite/backward/hash_set/49060.cc	(revision 0)
@@ -0,0 +1,35 @@
+// { dg-options "-Wno-deprecated" }
+
+#include <backward/hashtable.h>
+#include <utility>
+
+struct modulo2_hash
+{
+  size_t operator()(int const key) const
+  {
+    return key % 2;
+  }
+};
+
+struct modulo2_eq
+{
+  bool operator()(int const left, int const right) const
+  {
+    return left % 2 == right % 2;
+  }
+};
+
+int main()
+{
+  typedef std::_Select1st<std::pair<int const, int> > extract_type;
+  typedef
+    __gnu_cxx::hashtable<std::pair<int const, int>, int, modulo2_hash,
+			 extract_type, modulo2_eq, std::allocator<int> >
+      table_type;
+  table_type table(4, modulo2_hash(), modulo2_eq(), extract_type(),
+		   std::allocator<int>());
+
+  table.insert_equal(std::make_pair(2, 1));
+  table_type::iterator it(table.insert_equal(std::make_pair(4, 2)));
+  table.erase(it->first);
+}

Re: Patch committed: Fix erasing with reference in old hashtable code

[Paolo Carlini]

On 05/26/2011 01:09 AM, Ian Lance Taylor wrote:
> This patch fixes a problem with the old hashtable::erase code when the
> caller passes a reference to an element in the table, the element is not
> the first in the bucket, but it is equal to the first in the bucket.
> This is PR 49060, and the patch and test case are from that PR with
> minor tweaks.  Bootstrapped and ran libstdc++ testsuite on
> x86_64-unknown-linux-gnu.  Committed to mainline.
Thanks Ian.

Paolo.