From patchwork Wed Sep 5 19:51:48 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: 181933 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 361C62C0094 for ; Thu, 6 Sep 2012 05:52:19 +1000 (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=1347479540; 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=AfFts3w8JDBmqLKz2wUl+IBsiHc=; b=GVNSAUlChCv+YB/BYGU2pf1eyrg3f1uW8JtG13GCcvwiVSbzimINb8/NtXOBkW 1Hy7pHEgwrqCL/1txJEJJQBtjdOXSMc83VoDqQyEaBcrlfBuDgBThAxtHWla8w2W uup+KKsfT9wQTV1C1MCKauHW8yLUe/LEM4KQAonxcKsps= 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=O/qsyDORlVTjmwl2UceZsT09Ogl8h62e7rVOafs8YOP7FGZWsiTyLSXOrWnN5F zkD6Dp/chLAdqd4xlNe21Dz3PlDUlzWmDCO/XNLI71JyUv+aKrjGVeWRLup+Gt4F 6V1dTLbjic383jlOSublyjFY8sC05wduatrX2x+ElaQAg=; Received: (qmail 21261 invoked by alias); 5 Sep 2012 19:52:15 -0000 Received: (qmail 21236 invoked by uid 22791); 5 Sep 2012 19:52:12 -0000 X-SWARE-Spam-Status: No, hits=-5.2 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, KHOP_RCVD_TRUST, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE X-Spam-Check-By: sourceware.org Received: from mail-ee0-f47.google.com (HELO mail-ee0-f47.google.com) (74.125.83.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 05 Sep 2012 19:51:57 +0000 Received: by eekb57 with SMTP id b57so424329eek.20 for ; Wed, 05 Sep 2012 12:51:55 -0700 (PDT) Received: by 10.14.173.9 with SMTP id u9mr32282875eel.8.1346874715859; Wed, 05 Sep 2012 12:51:55 -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 i41sm6973237eem.7.2012.09.05.12.51.53 (version=SSLv3 cipher=OTHER); Wed, 05 Sep 2012 12:51:54 -0700 (PDT) Message-ID: <5047AD54.6000806@gmail.com> Date: Wed, 05 Sep 2012 21:51:48 +0200 From: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120829 Thunderbird/15.0 MIME-Version: 1.0 To: Paolo Carlini CC: Paolo Carlini , libstdc++@gcc.gnu.org, Jonathan Wakely , gcc-patches Subject: Re: [v3] libstdc++/54296 References: <503C9881.3080404@gmail.com> <503E7AFD.7090000@gmail.com> <503F2B93.2050801@gmail.com> <50465FB2.803@gmail.com> <50472258.50005@oracle.com> In-Reply-To: <50472258.50005@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 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 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 template @@ -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); + } + + template + 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; + template + 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 = static_cast<__node_type*>(__prev_n->_M_nxt); + __node_type* __n_last = __n; + std::size_t __n_last_bkt = __bkt; + do + { + __n_last = __n_last->_M_next(); + if (!__n_last) + break; + __n_last_bkt = _M_bucket_index(__n_last); + } + while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); + + // Deallocate nodes. size_type __result = 0; - __node_type* __saved_n = nullptr; do { - __node_type* __p = __next_n; - __next_n = __p->_M_next(); - - // _GLIBCXX_RESOLVE_LIB_DEFECTS - // 526. Is it undefined if a function in the standard changes - // in parameters? - if (std::__addressof(this->_M_extract()(__p->_M_v)) - != std::__addressof(__k)) - _M_deallocate_node(__p); - else - __saved_n = __p; + __node_type* __p = __n->_M_next(); + _M_deallocate_node(__n); + __n = __p; + ++__result; --_M_element_count; - ++__result; - if (!__next_n) - break; - __next_bkt = _M_bucket_index(__next_n); } - while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n)); + while (__n != __n_last); - if (__saved_n) - _M_deallocate_node(__saved_n); - if (__is_bucket_begin) - _M_remove_bucket_begin(__bkt, __next_n, __next_bkt); - else if (__next_n && __next_bkt != __bkt) - _M_buckets[__next_bkt] = __prev_n; - if (__prev_n) - __prev_n->_M_nxt = __next_n; + if (__prev_n == _M_buckets[__bkt]) + _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); + else if (__n_last && __n_last_bkt != __bkt) + _M_buckets[__n_last_bkt] = __prev_n; + __prev_n->_M_nxt = __n_last; return __result; } Index: testsuite/23_containers/unordered_map/erase/54276.cc =================================================================== --- testsuite/23_containers/unordered_map/erase/54276.cc (revision 0) +++ testsuite/23_containers/unordered_map/erase/54276.cc (revision 0) @@ -0,0 +1,103 @@ +// 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 +// . +// + +// { dg-options "-std=gnu++0x" } + +#include +#include +#include + +bool test __attribute__((unused)) = true; + +struct A +{ + int x; + static std::set destroyed; + + A() + { destroyed.erase(this); } + + A(const A& a) + : x(a.x) + { destroyed.erase(this); } + + ~A() + { destroyed.insert(this); } + + bool + operator==(const A& other) const + { + VERIFY( destroyed.find(this) == destroyed.end() ); + VERIFY( destroyed.find(&other) == destroyed.end() ); + return x == other.x; + } +}; + +std::set A::destroyed; + +struct hasher +{ + std::size_t operator()(const A& a) const + { + VERIFY( A::destroyed.find(&a) == A::destroyed.end() ); + return a.x / 10; + } +}; + +void test01() +{ + typedef std::unordered_map UMap; + UMap map; + + A::destroyed.clear(); + A a; + a.x = 0; + map.insert({a, a}); + a.x = 1; + map.insert({a, a}); + VERIFY( map.size() == 2 ); + std::size_t bkt = map.bucket(a); + VERIFY( map.bucket_size(bkt) == 2 ); + + VERIFY( map.erase( map.begin(bkt)->first ) == 1 ); +} + +void test02() +{ + typedef std::unordered_map UMap; + UMap map; + + A::destroyed.clear(); + A a; + a.x = 0; + map.insert({a, a}); + a.x = 1; + map.insert({a, a}); + VERIFY( map.size() == 2 ); + std::size_t bkt = map.bucket(a); + VERIFY( map.bucket_size(bkt) == 2 ); + + VERIFY( map.erase( map.begin(bkt)->second ) == 1 ); +} + +int main() +{ + test01(); + test02(); + return 0; +} Index: testsuite/23_containers/unordered_multimap/erase/54276.cc =================================================================== --- testsuite/23_containers/unordered_multimap/erase/54276.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/erase/54276.cc (revision 0) @@ -0,0 +1,101 @@ +// 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 +// . +// + +// { dg-options "-std=gnu++0x" } + +#include +#include +#include + +bool test __attribute__((unused)) = true; + +struct A +{ + int x; + static std::set destroyed; + + A() + { destroyed.erase(this); } + + A(const A& a) + : x(a.x) + { destroyed.erase(this); } + + ~A() + { destroyed.insert(this); } + + bool + operator==(const A& other) const + { + VERIFY( destroyed.find(this) == destroyed.end() ); + VERIFY( destroyed.find(&other) == destroyed.end() ); + return x == other.x; + } +}; + +std::set A::destroyed; + +struct hasher +{ + std::size_t operator()(const A& a) const + { + VERIFY( A::destroyed.find(&a) == A::destroyed.end() ); + return a.x / 10; + } +}; + +void test01() +{ + typedef std::unordered_multimap UMMap; + UMMap map; + + A::destroyed.clear(); + A a; + a.x = 0; + map.insert({a, a}); + map.insert({a, a}); + VERIFY( map.size() == 2 ); + std::size_t bkt = map.bucket(a); + VERIFY( map.bucket_size(bkt) == 2 ); + + VERIFY( map.erase( map.begin(bkt)->first ) == 2 ); +} + +void test02() +{ + typedef std::unordered_multimap UMMap; + UMMap map; + + A::destroyed.clear(); + A a; + a.x = 0; + map.insert({a, a}); + map.insert({a, a}); + VERIFY( map.size() == 2 ); + std::size_t bkt = map.bucket(a); + VERIFY( map.bucket_size(bkt) == 2 ); + + VERIFY( map.erase( map.begin(bkt)->second ) == 2 ); +} + +int main() +{ + test01(); + test02(); + return 0; +}