From patchwork Fri Mar 16 21:09:03 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 147267 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id C99C3B6EEC for ; Sat, 17 Mar 2012 08:09:48 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1332536990; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:References:In-Reply-To:Content-Type:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=GCeypC7Df0SQ5WkKFefdoL43wws=; b=OBzKPpyqBUbJNS5YNOtW2XMlx/8OLOl0mFz3eLdLnX8Gv0iQD/0YOKKNyvHCBi wScnWzX1g2gi1e9+wlZQCFvdHOpl9W+HJ8kVBW9h/8hxwm//x+1+M0Ewokh7qwX7 X8Zsv+9qrDC5k/bo2Cg0PmchtdWcd4Kg2P+PUR7kjIx9I= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:References:In-Reply-To:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=PmAnKrrdI5T4Sqo/tmsAGmgcCcZwSuQJbw2HU5ypE9+0TCOAOtoXSB6WZUrs2a OPUPluzfz/YTPB9D1C11NhoC2qGViwyh4pfnG8j+4J23nuLPj4qJUIZ1p08ZtfyK U5ElL8HxRJfC4P/VkWHuVXX11YwaOVi75sIvJUu0eT1Y4=; Received: (qmail 21842 invoked by alias); 16 Mar 2012 21:09:37 -0000 Received: (qmail 21828 invoked by uid 22791); 16 Mar 2012 21:09:34 -0000 X-SWARE-Spam-Status: No, hits=-2.6 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW X-Spam-Check-By: sourceware.org Received: from mail-we0-f175.google.com (HELO mail-we0-f175.google.com) (74.125.82.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 16 Mar 2012 21:09:07 +0000 Received: by wera1 with SMTP id a1so4957679wer.20 for ; Fri, 16 Mar 2012 14:09:05 -0700 (PDT) Received: by 10.180.82.136 with SMTP id i8mr1573222wiy.19.1331932145193; Fri, 16 Mar 2012 14:09:05 -0700 (PDT) Received: from localhost.localdomain (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPS id j3sm2839719wiw.1.2012.03.16.14.09.03 (version=SSLv3 cipher=OTHER); Fri, 16 Mar 2012 14:09:04 -0700 (PDT) Message-ID: <4F63ABEF.3000807@gmail.com> Date: Fri, 16 Mar 2012 22:09:03 +0100 From: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:8.0) Gecko/20111109 Thunderbird/8.0 MIME-Version: 1.0 To: Paolo Carlini CC: "libstdc++@gcc.gnu.org" , gcc-patches@gcc.gnu.org Subject: Re: [v3] fix libstdc++/52476 References: <4F5FBDE6.4010407@gmail.com> <4F609EB0.9060502@oracle.com> <4F6253E2.30001@gmail.com> <901A302D-938A-4CBF-9050-CB1AE52F0B44@oracle.com> In-Reply-To: <901A302D-938A-4CBF-9050-CB1AE52F0B44@oracle.com> Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Attached patch applied. 2012-03-16 François Dumont 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_constant()); + } + __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. + template + 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. + template + 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; + } + else + { + if (__prev_p && __prev_bkt == __bkt) { - __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; + + // 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; } else { - __p->_M_nxt = __new_buckets[__new_index]->_M_nxt; - __new_buckets[__new_index]->_M_nxt = __p; + __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; + + 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; } - __catch(...) + + if (__check_bucket && __prev_p->_M_nxt) { - // 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; + 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; } + + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + _M_bucket_count = __n; + _M_buckets = __new_buckets; } _GLIBCXX_END_NAMESPACE_VERSION Index: testsuite/23_containers/unordered_multimap/insert/52476.cc =================================================================== --- testsuite/23_containers/unordered_multimap/insert/52476.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/insert/52476.cc (revision 0) @@ -0,0 +1,59 @@ +// { dg-options "-std=gnu++0x" } +// +// 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 +// . + +#include +#include +#include +#include + +void test01() +{ + using namespace std; + bool test __attribute__((unused)) = true; + + unordered_multimap mmap; + vector values; + + size_t nb_bkts = mmap.bucket_count(); + int i = 0; + for (;; ++i) + { + mmap.insert(make_pair(0, i)); + if (mmap.bucket_count() != nb_bkts) + // Container got rehash + break; + values.clear(); + transform(mmap.begin(), mmap.end(), back_inserter(values), + [](const pair& p) { return p.second; }); + } + + vector rehash_values; + transform(mmap.begin(), mmap.end(), back_inserter(rehash_values), + [](const pair& p) { return p.second; }); + // Remove the value that result in a rehash + rehash_values.erase(remove(rehash_values.begin(), rehash_values.end(), i)); + + VERIFY( rehash_values == values ); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multiset/insert/52476.cc =================================================================== --- testsuite/23_containers/unordered_multiset/insert/52476.cc (revision 0) +++ testsuite/23_containers/unordered_multiset/insert/52476.cc (revision 0) @@ -0,0 +1,77 @@ +// { dg-options "-std=gnu++0x" } +// +// 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 +// . + +#include +#include +#include +#include + +namespace +{ + struct pair_hash + { + std::size_t + operator()(const std::pair& p) const noexcept + { return std::hash()(p.first); } + }; + + struct pair_equal_to + { + bool + operator()(const std::pair& x, + const std::pair& y) const noexcept + { return x.first == y.first; } + }; +} + +void test01() +{ + using namespace std; + bool test __attribute__((unused)) = true; + + unordered_multiset, pair_hash, pair_equal_to> mset; + vector values; + + size_t nb_bkts = mset.bucket_count(); + int i = 0; + for (;; ++i) + { + mset.insert(make_pair(0, i)); + if (mset.bucket_count() != nb_bkts) + // Container got rehash + break; + values.clear(); + transform(mset.begin(), mset.end(), back_inserter(values), + [](const pair& p) { return p.second; }); + } + + vector rehash_values; + transform(mset.begin(), mset.end(), back_inserter(rehash_values), + [](const pair& p) { return p.second; }); + // Remove the value that result in a rehash + rehash_values.erase(remove(rehash_values.begin(), rehash_values.end(), i)); + + VERIFY( rehash_values == values ); +} + +int main() +{ + test01(); + return 0; +}