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
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
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
- = _HCBas
