Re: [v3] libstdc++/54296
On 09/05/2012 11:58 AM, Paolo Carlini wrote:
Hi,
On 09/04/2012 10:08 PM, François Dumont wrote:
Hi
I managed to do the test with Valgrind and so confirm the fix
with the attached patch (unmodified since last proposal).
Patch is Ok, thanks for your patience and thanks again for all your
great work on the unordered containers!
Paolo.
Attached patch applied. No problem Paolo, this is your job as
maintainers to challenge the patches, no big deal. And being now able to
run programs through Valgrind or Gdb is definitely more comfortable for me.
2012-09-05 François Dumont fdum...@gcc.gnu.org
PR libstdc++/54296
* include/bits/hashtable.h (_M_erase(size_type, __node_base*,
__node_type*)): New.
(erase(const_iterator)): Use latter.
(_M_erase(std::true_type, const key_type)): New, likewise.
(_M_erase(std::false_type, const key_type)): New. Find all nodes
matching the key before deallocating them so that the key doesn't
get invalidated.
(erase(const key_type)): Use the new member functions.
* testsuite/23_containers/unordered_map/erase/54296.cc: New.
* testsuite/23_containers/unordered_multimap/erase/54296.cc: New.
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 190990)
+++ include/bits/hashtable.h (working copy)
@@ -612,6 +612,15 @@
iterator
_M_insert(_Arg, std::false_type);
+ size_type
+ _M_erase(std::true_type, const key_type);
+
+ size_type
+ _M_erase(std::false_type, const key_type);
+
+ iterator
+ _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
+
public:
// Emplace
templatetypename... _Args
@@ -636,7 +645,8 @@
{ return erase(const_iterator(__it)); }
size_type
- erase(const key_type);
+ erase(const key_type __k)
+ { return _M_erase(__unique_keys(), __k); }
iterator
erase(const_iterator, const_iterator);
@@ -1430,7 +1440,21 @@
// is why we need buckets to contain the before begin to make
// this research fast.
__node_base* __prev_n = _M_get_previous_node(__bkt, __n);
- if (__n == _M_bucket_begin(__bkt))
+ return _M_erase(__bkt, __prev_n, __n);
+}
+
+ templatetypename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits
+typename _Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy,
+ _Traits::iterator
+_Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits::
+_M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
+{
+ if (__prev_n == _M_buckets[__bkt])
_M_remove_bucket_begin(__bkt, __n-_M_next(),
__n-_M_nxt ? _M_bucket_index(__n-_M_next()) : 0);
else if (__n-_M_nxt)
@@ -1457,7 +1481,7 @@
_Traits::size_type
_Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits::
-erase(const key_type __k)
+_M_erase(std::true_type, const key_type __k)
{
__hash_code __code = this-_M_hash_code(__k);
std::size_t __bkt = _M_bucket_index(__k, __code);
@@ -1466,43 +1490,67 @@
__node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
if (!__prev_n)
return 0;
+
+ // We found a matching node, erase it.
__node_type* __n = static_cast__node_type*(__prev_n-_M_nxt);
- bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
+ _M_erase(__bkt, __prev_n, __n);
+ return 1;
+}
- // We found a matching node, start deallocation loop from it
- std::size_t __next_bkt = __bkt;
- __node_type* __next_n = __n;
+ templatetypename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits
+typename _Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy,
+ _Traits::size_type
+_Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits::
+_M_erase(std::false_type, const key_type __k)
+{
+ __hash_code __code = this-_M_hash_code(__k);
+ std::size_t __bkt = _M_bucket_index(__k, __code);
+
+ // Look for the node before the first matching node.
+ __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
+ if (!__prev_n)
+ return 0;
+
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 526. Is it undefined if a function in the standard changes
+ // in parameters?
+ // We use one loop to find all matching nodes and another to deallocate
+ // them so that the key stays valid during the first loop. It might be
+ // invalidated indirectly when destroying nodes.
+ __node_type* __n =
[v3] libstdc++/54296
Hi
Here is the patch for this issue. I introduced 2 distinct methods
to erase elements from a key. The one when keys are unique is rather
simple and now use the same underlying code that the erase method from
iterator. The other one when keys are not unique first look for nodes
matching the key and deallocate those in a second loop so that it
doesn't invalidate the key while looking for nodes. I considered
checking if the key instance address was inside the node address space
but the key instance might also be referenced as a pointer in the value
type free when the value instance is destroyed. Separating is the only
way to be sure that the key won't be broken while looking for matching
nodes.
I check that _Rb_tree is not impacted by this issue as it is using
a call to equal_range first and erase the range after. I considered
doing the same in _Hashtable implementation but finally preferred not to
do so because it would imply re-computing hash code and add useless checks.
2012-08-28 François Dumont fdum...@gcc.gnu.org
PR libstdc++/54296
* include/bits/hashtable.h (_M_erase(size_type, __node_base*,
__node_type*)): New.
(erase(const_iterator)): Use latter.
(_M_erase(std::true_type, const key_type)): New, likewise.
(_M_erase(std::false_type, const key_type)): New. Find all nodes
matching the key before deallocating them so that the key doesn't
get invalidated.
(erase(const key_type)): Use latters.
* testsuite/23_containers/unordered_map/erase/54296.cc: New.
* testsuite/23_containers/unordered_multimap/erase/54296.cc: New.
Tested under linux x86_64.
Ok for trunk ? As it is an old issue I don't think it needs to be apply
to any branch, tell me otherwise.
François
Index: include/bits/hashtable.h
===
--- include/bits/hashtable.h (revision 190703)
+++ include/bits/hashtable.h (working copy)
@@ -612,6 +612,15 @@
iterator
_M_insert(_Arg, std::false_type);
+ size_type
+ _M_erase(std::true_type, const key_type);
+
+ size_type
+ _M_erase(std::false_type, const key_type);
+
+ iterator
+ _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
+
public:
// Emplace
templatetypename... _Args
@@ -636,7 +645,8 @@
{ return erase(const_iterator(__it)); }
size_type
- erase(const key_type);
+ erase(const key_type __k)
+ { return _M_erase(__unique_keys(), __k); }
iterator
erase(const_iterator, const_iterator);
@@ -1430,7 +1440,21 @@
// is why we need buckets to contain the before begin to make
// this research fast.
__node_base* __prev_n = _M_get_previous_node(__bkt, __n);
- if (__n == _M_bucket_begin(__bkt))
+ return _M_erase(__bkt, __prev_n, __n);
+}
+
+ templatetypename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits
+typename _Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy,
+ _Traits::iterator
+_Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits::
+_M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
+{
+ if (__prev_n == _M_buckets[__bkt])
_M_remove_bucket_begin(__bkt, __n-_M_next(),
__n-_M_nxt ? _M_bucket_index(__n-_M_next()) : 0);
else if (__n-_M_nxt)
@@ -1457,7 +1481,7 @@
_Traits::size_type
_Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits::
-erase(const key_type __k)
+_M_erase(std::true_type, const key_type __k)
{
__hash_code __code = this-_M_hash_code(__k);
std::size_t __bkt = _M_bucket_index(__k, __code);
@@ -1466,43 +1490,67 @@
__node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
if (!__prev_n)
return 0;
+
+ // We found a matching node, erase it.
__node_type* __n = static_cast__node_type*(__prev_n-_M_nxt);
- bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
+ _M_erase(__bkt, __prev_n, __n);
+ return 1;
+}
- // We found a matching node, start deallocation loop from it
- std::size_t __next_bkt = __bkt;
- __node_type* __next_n = __n;
+ templatetypename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits
+typename _Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy,
+ _Traits::size_type
+_Hashtable_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits::
+_M_erase(std::false_type, const key_type __k)
+{
+ __hash_code __code = this-_M_hash_code(__k);
+ std::size_t __bkt =
Re: [v3] libstdc++/54296
On 28 August 2012 11:08, François Dumont wrote: (erase(const key_type)): Use latters. Let's put Use the new member functions here in the ChangeLog, I don't think you can make a plural out of latter :-) * testsuite/23_containers/unordered_map/erase/54296.cc: New. * testsuite/23_containers/unordered_multimap/erase/54296.cc: New. Tested under linux x86_64. Thanks for the fix. Did you manage to test it with valgrind?
