diff mbox

PR 53115

Message ID 4FA0464C.5030605@gmail.com
State New
Headers show

Commit Message

François Dumont May 1, 2012, 8:23 p.m. UTC 
unordered_multilmap test added, attached patch applied to 4.7 branch and 
trunk.

This bug was not so difficult to fix. It would even have been quite easy 
to detect with a good test coverage tool showing that not all possible 
path had been tested in this method. I hope to be able to make some 
progress on this subject in the future. However I will have a try with 
Valgrind.

I can only add comment in bugzilla so I let you set this issue as resolved.

François


I will have a run with Valgrind

2012-05-01  François Dumont <fdumont@gcc.gnu.org>

         PR libstdc++/53115
         * include/bits/hashtable.h
         (_Hashtable<>::_M_rehash_aux(size_type, false_type)): Fix buckets
         after insertion of several equivalent elements.
         * testsuite/23_containers/unordered_multiset/insert/53115.cc: New.
         * testsuite/23_containers/unordered_multimap/insert/53115.cc: New.
On 04/29/2012 12:42 PM, Paolo Carlini wrote:
> On 04/29/2012 12:21 PM, François Dumont wrote:
>> Hi
>>
>>     Here is the patch for this PR. We were using buckets before 
>> updating them after having inserted equivalents elements one after 
>> the another.
>>
>> 2012-04-29  François Dumont <fdumont@gcc.gnu.org>
>>
>>     PR libstdc++/53115
>>     * include/bits/hashtable.h
>>     (_Hashtable<>::_M_rehash_aux(size_type, false_type)): Fix buckets
>>     after insertion of several equivalent elements.
>>     * testsuite/23_containers/unordered_multiset/insert/53115.cc: New.
>>
>>     Tested undex linux x86_64 in the 4.7 branch, normal and debug mode.
>>
>>     Ok to commit ?
> Ok, but please also add a similar testcase for unordered_multimap. 
> Also - just in case isn't obvious enough - please run such testcases 
> through valgrind.
>
> Thanks!
> Paolo.
>
>

Comments

Paolo Carlini May 1, 2012, 8:28 p.m. UTC | #1 
On 05/01/2012 10:23 PM, François Dumont wrote:
> unordered_multilmap test added, attached patch applied to 4.7 branch 
> and trunk.
>
> This bug was not so difficult to fix. It would even have been quite 
> easy to detect with a good test coverage tool showing that not all 
> possible path had been tested in this method. I hope to be able to 
> make some progress on this subject in the future. However I will have 
> a try with Valgrind.
If you are on Linux, or any of the supported targets, *always* use 
valgrind when handling this kind of issue. If you are not, just let me 
know, and I will for you.

Paolo.
H.J. Lu May 2, 2012, 4:23 p.m. UTC | #2 
On Tue, May 1, 2012 at 1:23 PM, François Dumont <frs.dumont@gmail.com> wrote:
> unordered_multilmap test added, attached patch applied to 4.7 branch and
> trunk.
>
> This bug was not so difficult to fix. It would even have been quite easy to
> detect with a good test coverage tool showing that not all possible path had
> been tested in this method. I hope to be able to make some progress on this
> subject in the future. However I will have a try with Valgrind.
>
> I can only add comment in bugzilla so I let you set this issue as resolved.
>
> François
>
>
> I will have a run with Valgrind
>
> 2012-05-01  François Dumont <fdumont@gcc.gnu.org>
>
>        PR libstdc++/53115
>        * include/bits/hashtable.h
>        (_Hashtable<>::_M_rehash_aux(size_type, false_type)): Fix buckets
>        after insertion of several equivalent elements.
>        * testsuite/23_containers/unordered_multiset/insert/53115.cc: New.
>        * testsuite/23_containers/unordered_multimap/insert/53115.cc: New.

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53193

It may need other fixes from trunk.
François Dumont May 2, 2012, 7:08 p.m. UTC | #3 
On 05/02/2012 06:23 PM, H.J. Lu wrote:
> On Tue, May 1, 2012 at 1:23 PM, François Dumont<frs.dumont@gmail.com>  wrote:
>> unordered_multilmap test added, attached patch applied to 4.7 branch and
>> trunk.
>>
>> This bug was not so difficult to fix. It would even have been quite easy to
>> detect with a good test coverage tool showing that not all possible path had
>> been tested in this method. I hope to be able to make some progress on this
>> subject in the future. However I will have a try with Valgrind.
>>
>> I can only add comment in bugzilla so I let you set this issue as resolved.
>>
>> François
>>
>>
>> I will have a run with Valgrind
>>
>> 2012-05-01  François Dumont<fdumont@gcc.gnu.org>
>>
>>         PR libstdc++/53115
>>         * include/bits/hashtable.h
>>         (_Hashtable<>::_M_rehash_aux(size_type, false_type)): Fix buckets
>>         after insertion of several equivalent elements.
>>         * testsuite/23_containers/unordered_multiset/insert/53115.cc: New.
>>         * testsuite/23_containers/unordered_multimap/insert/53115.cc: New.
> This caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53193
>
> It may need other fixes from trunk.
>
I run tests before updating FSF copyright year.

Sorry
diff mbox

Patch

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 187022)
+++ include/bits/hashtable.h	(working copy)
@@ -1,6 +1,7 @@ 
 // hashtable.h header -*- C++ -*-
 
-// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010, 2011, 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
@@ -1670,57 +1671,55 @@ 
 
       while (__p)
 	{
-	  bool __check_now = true;
 	  _Node* __next = __p->_M_next();
 	  std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
 
-	  if (!__new_buckets[__bkt])
+	  if (__prev_p && __prev_bkt == __bkt)
 	    {
-	      __p->_M_nxt = _M_before_begin._M_nxt;
-	      _M_before_begin._M_nxt = __p;
-	      __new_buckets[__bkt] = &_M_before_begin;
-	      if (__p->_M_nxt)
-		__new_buckets[__bbegin_bkt] = __p;
-	      __bbegin_bkt = __bkt;
+	      // Previous insert was already in this bucket, we insert after
+	      // the previously inserted one to preserve equivalent elements
+	      // relative order.
+	      __p->_M_nxt = __prev_p->_M_nxt;
+	      __prev_p->_M_nxt = __p;
+	      
+	      // Inserting after a node in a bucket require to check that we
+	      // haven't change the bucket last node, in this case next
+	      // bucket containing its before begin node must be updated. We
+	      // schedule a check as soon as we move out of the sequence of
+	      // equivalent nodes to limit the number of checks.
+	      __check_bucket = true;
 	    }
 	  else
 	    {
-	      if (__prev_p && __prev_bkt == __bkt)
+	      if (__check_bucket)
 		{
-		  // Previous insert was already in this bucket, we insert after
-		  // the previously inserted one to preserve equivalent elements
-		  // relative order.
-		  __p->_M_nxt = __prev_p->_M_nxt;
-		  __prev_p->_M_nxt = __p;
-
-		  // Inserting after a node in a bucket require to check that we
-		  // haven't change the bucket last node, in this case next
-		  // bucket containing its before begin node must be updated. We
-		  // schedule a check as soon as we move out of the sequence of
-		  // equivalent nodes to limit the number of checks.
-		  __check_bucket = true;
-		  __check_now = false;
+		  // Check if we shall update the next bucket because of insertions
+		  // into __prev_bkt bucket.
+		  if (__prev_p->_M_nxt)
+		    {
+		      std::size_t __next_bkt
+			= _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
+		      if (__next_bkt != __prev_bkt)
+			__new_buckets[__next_bkt] = __prev_p;
+		    }
+		  __check_bucket = false;
 		}
+	      if (!__new_buckets[__bkt])
+		{
+		  __p->_M_nxt = _M_before_begin._M_nxt;
+		  _M_before_begin._M_nxt = __p;
+		  __new_buckets[__bkt] = &_M_before_begin;
+		  if (__p->_M_nxt)
+		    __new_buckets[__bbegin_bkt] = __p;
+		  __bbegin_bkt = __bkt;
+		}
 	      else
 		{
 		  __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
 		  __new_buckets[__bkt]->_M_nxt = __p;
 		}
 	    }
-	  
-	  if (__check_now && __check_bucket)
-	    {
-	      // Check if we shall update the next bucket because of insertions
-	      // into __prev_bkt bucket.
-	      if (__prev_p->_M_nxt)
-		{
-		  std::size_t __next_bkt
-		    = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
-		  if (__next_bkt != __prev_bkt)
-		    __new_buckets[__next_bkt] = __prev_p;
-		}
-	      __check_bucket = false;
-	    }
+
 	  __prev_p = __p;
 	  __prev_bkt = __bkt;
 	  __p = __next;
Index: testsuite/23_containers/unordered_multimap/insert/53115.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/insert/53115.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/insert/53115.cc	(revision 0)
@@ -0,0 +1,101 @@ 
+// { dg-options "-std=gnu++11" }
+//
+// 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/>.
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+namespace
+{
+  std::size_t
+  get_nb_bucket_elems(const std::unordered_multimap<int, int>& us)
+  {
+    std::size_t nb = 0;
+    for (std::size_t b = 0; b != us.bucket_count(); ++b)
+      nb += us.bucket_size(b);
+    return nb;
+  }
+}
+
+void test01()
+{
+  using namespace std;
+  bool test __attribute__((unused)) = true;
+
+  std::unordered_multimap<int, int> umm;
+  umm.insert(make_pair(10, 1));
+  VERIFY( umm.size() == 1 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 2)); 
+  VERIFY( umm.size() == 2 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 3));
+  VERIFY( umm.size() == 3 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 4));
+  VERIFY( umm.size() == 4 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 5));
+  VERIFY( umm.size() == 5 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(24, 6));
+  VERIFY( umm.size() == 6 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(25, 7));
+  VERIFY( umm.size() == 7 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(2, 8));
+  VERIFY( umm.size() == 8 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(2, 9));
+  VERIFY( umm.size() == 9 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(1, 10));
+  VERIFY( umm.size() == 10 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 11));
+  VERIFY( umm.size() == 11 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multiset/insert/53115.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/insert/53115.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/insert/53115.cc	(revision 0)
@@ -0,0 +1,101 @@ 
+// { dg-options "-std=gnu++11" }
+//
+// 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/>.
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+
+namespace
+{
+  std::size_t
+  get_nb_bucket_elems(const std::unordered_multiset<int>& us)
+  {
+    std::size_t nb = 0;
+    for (std::size_t b = 0; b != us.bucket_count(); ++b)
+      nb += us.bucket_size(b);
+    return nb;
+  }
+}
+
+void test01()
+{
+  using namespace std;
+  bool test __attribute__((unused)) = true;
+
+  std::unordered_multiset<int> mms;
+  mms.insert(10);
+  VERIFY( mms.size() == 1 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10); 
+  VERIFY( mms.size() == 2 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10);
+  VERIFY( mms.size() == 3 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10);
+  VERIFY( mms.size() == 4 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10);
+  VERIFY( mms.size() == 5 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(24);
+  VERIFY( mms.size() == 6 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(25);
+  VERIFY( mms.size() == 7 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(2);
+  VERIFY( mms.size() == 8 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(2);
+  VERIFY( mms.size() == 9 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(1);
+  VERIFY( mms.size() == 10 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10);
+  VERIFY( mms.size() == 11 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}