This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: PR 53115
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Paolo Carlini <paolo dot carlini at oracle dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Tue, 01 May 2012 22:23:40 +0200
- Subject: Re: PR 53115
- References: <4F9D1625.2050308@gmail.com> <4F9D1B27.8040209@oracle.com>
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.
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;
+}