[v3] fix libstdc++/52476
François Dumont
frs.dumont@gmail.com
Fri Mar 16 00:29:00 GMT 2012
Compiling your feedbacks here is what I came to:
2012-03-15 François Dumont <fdumont@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.
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.
Tested under Linux x86_64.
Ok for mainline ?
François
On 03/14/2012 02:35 PM, Paolo Carlini wrote:
> Hi,
>>
>> Here a patch proposition to fix PR 52446.
>>
>> I have introduce 2 version of the _M_rehash method. One used when
>> keys are unique which is very close to the existing one. The second
>> that take care of keeping equivalent keys relative order on rehash.
>> The second one might seem complicated but I wanted to avoid to
>> recompute a bucket index each time we find an equivalent element. If
>> the hash code is cached it is ok but if it is not I prefer to limit
>> the number of time it is recalculated.
>>
>> 2012-03-13 François Dumont <fdumont@gcc.gnu.org>
>>
>> PR libstdc++/52446
>> * include/bits/hashtable.h (_Hashtable<>::_M_rehash): Split into 2
>> methods, the first, copy of the existing one, is used when keys
>> are unique, the second purpose is to keep equivalent keys relative
>> orders.
> The "purpose of the second", maybe? Can we use a new name for the new
> functions, instead of overloading? A descriptive name or suffix would
> add clarity to the code.
>
>> * testsuite/23_containers/unordered_multimap/insert/52446.cc: New.
>>
>> Tested under linux x86_64.
>>
>> If ok tell me if I must also apply it to 4.7 branch.
> We are going to fix this in mainline and, then, if everything goes
> well, in 4.7.1.
>
> Minor nits:
>>
>> François
>>
>>
>> 52446.patch
>>
>>
>> Index: include/bits/hashtable.h
>> ===================================================================
>> --- include/bits/hashtable.h (revision 185352)
>> +++ include/bits/hashtable.h (working copy)
>> @@ -596,6 +596,11 @@
>> // reserve, if present, comes from _Rehash_base.
>>
>> private:
>> + // Rehash method when keys are unique
>> + void _M_rehash(size_type __n, std::true_type);
> A blank line here.
>> + // Rehash method when there might be equivalent keys.
>> + void _M_rehash(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 +1597,141 @@
>> {
>> __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(__n, integral_constant<bool, __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;
>> + }
>> + }
>> +
>> + template<typename _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(size_type __n, std::true_type)
>> + {
>> + // This version of rehash do not have to care about equivalent
>> elements
>> + // relative order.
>> + _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)
>> + {
>> + _Node* __next = __p->_M_next();
>> + std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
>> + if (!__new_buckets[__new_index])
>> {
>> - _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[__new_index] =&_M_before_begin;
>> + if (__p->_M_nxt)
>> + __new_buckets[__cur_bbegin_bkt] = __p;
>> + __cur_bbegin_bkt = __new_index;
>> + }
>> + else
>> + {
>> + __p->_M_nxt = __new_buckets[__new_index]->_M_nxt;
>> + __new_buckets[__new_index]->_M_nxt = __p;
>> + }
>> + __p = __next;
>> + }
>> + _M_deallocate_buckets(_M_buckets, _M_bucket_count);
>> + _M_bucket_count = __n;
>> + _M_buckets = __new_buckets;
>> + }
>> +
>> + template<typename _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(size_type __n, std::false_type)
>> + {
>> + // This version of rehash must guaranty that equivalent
>> elements relative
>> + // order is preserve.
>> + _Bucket* __new_buckets = _M_allocate_buckets(__n);
>> + _Node* __p = _M_begin();
>> + _M_before_begin._M_nxt = nullptr;
>> + std::size_t __cur_bbegin_bkt;
>> + std::size_t __prev_index;
>> + _Node* __prev_p = nullptr;
>> + bool __check_next_bucket = false;
>> + while (__p)
>> + {
>> + bool __check_now = true;
>> + _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[__new_index] =&_M_before_begin;
>> + if (__p->_M_nxt)
>> + __new_buckets[__cur_bbegin_bkt] = __p;
>> + __cur_bbegin_bkt = __new_index;
>> + }
>> + else
>> + {
>> + if (__prev_p&& __prev_index == __new_index)
>> {
>> - __p->_M_nxt = _M_before_begin._M_nxt;
>> - _M_before_begin._M_nxt = __p;
>> - __new_buckets[__new_index] =&_M_before_begin;
>> - if (__p->_M_nxt)
>> - __new_buckets[__cur_bbegin_bkt] = __p;
>> - __cur_bbegin_bkt = __new_index;
>> + // 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;
> And here. As a general style, I would say always when the comment
> itself is preceded by code != open curly bracket.
>> + // Request a check as soon as we move out of the sequence of
>> + // equivalent nodes.
>> + __check_next_bucket = true;
>> + __check_now = false;
> In terms of testcases, I would also add something more
> straightforward, close to what we have in the PR, and duplicated for
> map and set. But I'm not going to insist ;)
>
> Thanks!
> Paolo.
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 52476.patch
Type: text/x-patch
Size: 10791 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20120316/f803445b/attachment.bin>
More information about the Libstdc++
mailing list