Re: [v3] fix libstdc++/52476
Attached patch applied to 4_7-branch.
2012-04-09 François Dumont fdum...@gcc.gnu.org
PR libstdc++/52476
* include/bits/hashtable.h (_Hashtable::_M_rehash_aux): Add.
(_Hashtable::_M_rehash): Use the latter.
* testsuite/23_containers/unordered_multimap/insert/52476.cc: New.
* testsuite/23_containers/unordered_multiset/insert/52476.cc: New.
Tested under linux x86_64.
I don't think I have the necessary rights to close the PR on bugzilla, I
haven't been able to do so.
François
On 04/02/2012 12:12 AM, Paolo Carlini wrote:
Hi,
Attached patch applied.
2012-03-16 François Dumont fdum...@gcc.gnu.org
PR libstdc++/52476
* include/bits/hashtable.h (_Hashtable::_M_rehash_aux): Add.
(_Hashtable::_M_rehash): Use the latter.
* testsuite/23_containers/unordered_multimap/insert/52476.cc:
New.
* testsuite/23_containers/unordered_multiset/insert/52476.cc:
New.
Francois, at your ease, I think it's time to apply the fix to
4_7-branch too and resolve the PR. By the way, Daniel confirmed in
private email that mainline works just fine now.
Thanks,
Paolo.
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 186244)
+++ include/bits/hashtable.h (working copy)
@@ -596,6 +596,12 @@
// reserve, if present, comes from _Rehash_base.
private:
+ // Helper rehash method used when keys are unique.
+ void _M_rehash_aux(size_type __n, std::true_type);
+
+ // Helper rehash method used when keys can be non-unique.
+ void _M_rehash_aux(size_type __n, std::false_type);
+
// Unconditionally change size of bucket array to n, restore hash policy
// state to __state on exception.
void _M_rehash(size_type __n, const _RehashPolicyState __state);
@@ -1592,41 +1598,145 @@
{
__try
{
- _Bucket* __new_buckets = _M_allocate_buckets(__n);
- _Node* __p = _M_begin();
- _M_before_begin._M_nxt = nullptr;
- std::size_t __cur_bbegin_bkt;
- while (__p)
+ _M_rehash_aux(__n, integral_constantbool, __uk());
+ }
+ __catch(...)
+ {
+ // A failure here means that buckets allocation failed. We only
+ // have to restore hash policy previous state.
+ _M_rehash_policy._M_reset(__state);
+ __throw_exception_again;
+ }
+}
+
+ // Rehash when there is no equivalent elements.
+ templatetypename _Key, typename _Value,
+ typename _Allocator, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ bool __chc, bool __cit, bool __uk
+void
+_Hashtable_Key, _Value, _Allocator, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk::
+_M_rehash_aux(size_type __n, std::true_type)
+{
+ _Bucket* __new_buckets = _M_allocate_buckets(__n);
+ _Node* __p = _M_begin();
+ _M_before_begin._M_nxt = nullptr;
+ std::size_t __bbegin_bkt;
+ while (__p)
+ {
+ _Node* __next = __p-_M_next();
+ std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
+ if (!__new_buckets[__bkt])
{
- _Node* __next = __p-_M_next();
- std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
- if (!__new_buckets[__new_index])
+ __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;
+ }
+ __p = __next;
+ }
+ _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+ _M_bucket_count = __n;
+ _M_buckets = __new_buckets;
+}
+
+ // Rehash when there can be equivalent elements, preserve their relative
+ // order.
+ templatetypename _Key, typename _Value,
+ typename _Allocator, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ bool __chc, bool __cit, bool __uk
+void
+_Hashtable_Key, _Value, _Allocator, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk::
+_M_rehash_aux(size_type __n, std::false_type)
+{
+ _Bucket* __new_buckets = _M_allocate_buckets(__n);
+
+ _Node* __p = _M_begin();
+ _M_before_begin._M_nxt = nullptr;
+ std::size_t __bbegin_bkt;
+ std::size_t __prev_bkt;
+ _Node* __prev_p = nullptr;
+ bool __check_bucket = false;
+
+ 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])
+ {
+ __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;
+
Re: [v3] fix libstdc++/52476
On 9 April 2012 20:25, François Dumont wrote: I don't think I have the necessary rights to close the PR on bugzilla, I haven't been able to do so. You should be able to using your @gcc.gnu.org account. What if you assign it to yourself first?
Re: [v3] fix libstdc++/52476
Hi, Attached patch applied. 2012-03-16 François Dumont fdum...@gcc.gnu.org PR libstdc++/52476 * include/bits/hashtable.h (_Hashtable::_M_rehash_aux): Add. (_Hashtable::_M_rehash): Use the latter. * testsuite/23_containers/unordered_multimap/insert/52476.cc: New. * testsuite/23_containers/unordered_multiset/insert/52476.cc: New. Francois, at your ease, I think it's time to apply the fix to 4_7-branch too and resolve the PR. By the way, Daniel confirmed in private email that mainline works just fine now. Thanks, Paolo.
Re: [v3] fix libstdc++/52476
this removes the pb_ds fails exposed by this patch.
-benjamin2012-03-19 Benjamin Kosnik b...@redhat.com
* include/ext/pb_ds/detail/pat_trie_/
constructors_destructor_fn_imps.hpp: Increment after recursion.
* include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp: Convert
node_type markup from brief.
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp
index 8370a2e..c5748ec 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
+// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
@@ -188,7 +188,11 @@ recursive_copy_node(node_const_pointer p_ncp)
__try
{
while (child_it != p_icp-end())
- a_p_children[child_i++] = recursive_copy_node(*(child_it++));
+ {
+ a_p_children[child_i] = recursive_copy_node(*(child_it));
+ child_i++;
+ child_it++;
+ }
p_ret = s_inode_allocator.allocate(1);
}
__catch(...)
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
index b7eb024..0a763b5 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
@@ -1,6 +1,6 @@
// -*- C++ -*-
-// Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 2009, 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 terms
@@ -50,7 +50,11 @@ namespace __gnu_pbds
/// Base type for PATRICIA trees.
struct pat_trie_base
{
- /// Three types of nodes.
+ /**
+ * @brief Three types of nodes.
+ *
+ * i_node is used by _Inode, leaf_node by _Leaf, and head_node by _Head.
+ */
enum node_type
{
i_node,
Re: [v3] fix libstdc++/52476
Attached patch applied.
2012-03-16 François Dumont fdum...@gcc.gnu.org
PR libstdc++/52476
* include/bits/hashtable.h (_Hashtable::_M_rehash_aux): Add.
(_Hashtable::_M_rehash): Use the latter.
* testsuite/23_containers/unordered_multimap/insert/52476.cc: New.
* testsuite/23_containers/unordered_multiset/insert/52476.cc: New.
Regards
On 03/16/2012 10:19 AM, Paolo Carlini wrote:
Hi,
Regarding the testcase, the code in the ticket is showing the problem but
is not a test. The test might seem a little bit complicated but I try to make
it independent to how elements are inserted into the container which is not
defined by the Standard. Even if we change implementation and store
0-3,0-2,0-1,0-0 rather than 0-0,0-1,0-2,0-3 the test will still work and only
check the Standard point which is that the order of those elements should be
preserve on rehash.
Understood, thanks for adding a second testcase for multiset.
Tested under Linux x86_64.
Ok for mainline ?
Yes, thanks a lot. Please keep in mind that barring special issues we want the
fix for 4.7.1 too.
Thanks
Paolo
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 185475)
+++ include/bits/hashtable.h (working copy)
@@ -596,6 +596,12 @@
// reserve, if present, comes from _Rehash_base.
private:
+ // Helper rehash method used when keys are unique.
+ void _M_rehash_aux(size_type __n, std::true_type);
+
+ // Helper rehash method used when keys can be non-unique.
+ void _M_rehash_aux(size_type __n, std::false_type);
+
// Unconditionally change size of bucket array to n, restore hash policy
// state to __state on exception.
void _M_rehash(size_type __n, const _RehashPolicyState __state);
@@ -1592,41 +1598,145 @@
{
__try
{
- _Bucket* __new_buckets = _M_allocate_buckets(__n);
- _Node* __p = _M_begin();
- _M_before_begin._M_nxt = nullptr;
- std::size_t __cur_bbegin_bkt;
- while (__p)
+ _M_rehash_aux(__n, integral_constantbool, __uk());
+ }
+ __catch(...)
+ {
+ // A failure here means that buckets allocation failed. We only
+ // have to restore hash policy previous state.
+ _M_rehash_policy._M_reset(__state);
+ __throw_exception_again;
+ }
+}
+
+ // Rehash when there is no equivalent elements.
+ templatetypename _Key, typename _Value,
+ typename _Allocator, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ bool __chc, bool __cit, bool __uk
+void
+_Hashtable_Key, _Value, _Allocator, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk::
+_M_rehash_aux(size_type __n, std::true_type)
+{
+ _Bucket* __new_buckets = _M_allocate_buckets(__n);
+ _Node* __p = _M_begin();
+ _M_before_begin._M_nxt = nullptr;
+ std::size_t __bbegin_bkt;
+ while (__p)
+ {
+ _Node* __next = __p-_M_next();
+ std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
+ if (!__new_buckets[__bkt])
{
- _Node* __next = __p-_M_next();
- std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
- if (!__new_buckets[__new_index])
+ __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;
+ }
+ __p = __next;
+ }
+ _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+ _M_bucket_count = __n;
+ _M_buckets = __new_buckets;
+}
+
+ // Rehash when there can be equivalent elements, preserve their relative
+ // order.
+ templatetypename _Key, typename _Value,
+ typename _Allocator, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ bool __chc, bool __cit, bool __uk
+void
+_Hashtable_Key, _Value, _Allocator, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk::
+_M_rehash_aux(size_type __n, std::false_type)
+{
+ _Bucket* __new_buckets = _M_allocate_buckets(__n);
+
+ _Node* __p = _M_begin();
+ _M_before_begin._M_nxt = nullptr;
+ std::size_t __bbegin_bkt;
+ std::size_t __prev_bkt;
+ _Node* __prev_p = nullptr;
+ bool __check_bucket = false;
+
+ 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])
+ {
+ __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;
+ }
+
