From patchwork Thu Nov 1 01:32:48 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 196070 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 978F92C00E1 for ; Thu, 1 Nov 2012 12:33:02 +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=1352338383; h=Comment: DomainKey-Signature:Received:Received:Received:Received: MIME-Version:Received:Received:Date:Message-ID:Subject:From:To: Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=zfCNd81 3LyDuroA/scUJooNkcP0=; b=XZIGJc+4WeBlmoNYhFK0l073uJXjAPJPtWqcXJ7 4rbEV6Yzv1rmb8AP5cqEfAsUEY1ZJf/vMZOTQ8pBCepkGq/nP+WZj2+wIEX98iSU D0JIpkAmXmaceMeH7xDt1O6NWuuVnOmO31Mt4CS4Pmc4bJVTcfJk52SBaI63VOfl 6n/U= 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:MIME-Version:Received:Received:Date:Message-ID:Subject:From:To:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=y4isG6tV4IgR8/FHVXC8J3MZlSHEot+jxP03nEO+iF5JSruktKkLJTKCBNXJb2 icCksCgMM4580KaT6QD0buQg1ZBOPdq50SLOp86YP5JL0uF2S7ja+aOKBj0DWh6R cgZz11EQtv490H7zPjyT+B74Z5qoW31vwe6K0r/wW0MQo=; Received: (qmail 4869 invoked by alias); 1 Nov 2012 01:32:55 -0000 Received: (qmail 4853 invoked by uid 22791); 1 Nov 2012 01:32:54 -0000 X-SWARE-Spam-Status: No, hits=-4.5 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, KHOP_RCVD_TRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE X-Spam-Check-By: sourceware.org Received: from mail-ie0-f175.google.com (HELO mail-ie0-f175.google.com) (209.85.223.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 01 Nov 2012 01:32:48 +0000 Received: by mail-ie0-f175.google.com with SMTP id c13so3311227ieb.20 for ; Wed, 31 Oct 2012 18:32:48 -0700 (PDT) MIME-Version: 1.0 Received: by 10.50.15.132 with SMTP id x4mr3440907igc.58.1351733568092; Wed, 31 Oct 2012 18:32:48 -0700 (PDT) Received: by 10.42.158.202 with HTTP; Wed, 31 Oct 2012 18:32:48 -0700 (PDT) Date: Thu, 1 Nov 2012 01:32:48 +0000 Message-ID: Subject: [v3] Reuse existing elements in forward_list::assign() From: Jonathan Wakely To: "libstdc++" , gcc-patches 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 This changes the forward_list::assign() members to assign to existing elements instead of destroying them and reallocating new ones, as allowed by the Sequence Container requirements. The copy assignment operator already did that, so now it uses assign(). For QoI we still support non-assignable types by dispatching to different functions. I've also added a test for the memory leak I fixed yesterday. I'll have one more forward_list patch tomorrow to finish the allocator support and I'll leave forward_list alone for 4.8 Tested x86_64-linux, committed to trunk. commit 679c6e478bba98781554a5170eaef975c708a487 Author: Jonathan Wakely Date: Wed Oct 31 23:17:11 2012 +0000 * include/bits/forward_list.h (forward_list::assign): Dispatch to new functions based on assignability of elements. (forward_list::_M_assign): Add overloaded functions for assigning via assignment or via clearing and insertion. (forward_list::_M_assign_val): Likewise. (forward_list::_M_move_assign(forward_list&&, false_type)): Do not erase elements that are not moved. * include/bits/forward_list.tcc (forward_list::operator=): Call assign() to copy elements. * testsuite/23_containers/forward_list/cons/10.cc: New. * testsuite/23_containers/forward_list/cons/11.cc: New. * testsuite/23_containers/forward_list/cons/12.cc: New. diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h index 8d4915d..b40fe9b 100644 --- a/libstdc++-v3/include/bits/forward_list.h +++ b/libstdc++-v3/include/bits/forward_list.h @@ -589,7 +589,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * in the range [@a __first,@a __last). * * Note that the assignment completely changes the %forward_list and - * that the number of elements of the resulting %forward_list's is the + * that the number of elements of the resulting %forward_list is the * same as the number of elements assigned. Old data is lost. */ template __assignable; + _M_assign(__first, __last, __assignable()); + } /** * @brief Assigns a given value to a %forward_list. @@ -613,10 +613,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void assign(size_type __n, const _Tp& __val) - { - clear(); - insert_after(cbefore_begin(), __n, __val); - } + { _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); } /** * @brief Assigns an initializer_list to a %forward_list. @@ -628,10 +625,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void assign(std::initializer_list<_Tp> __il) - { - clear(); - insert_after(cbefore_begin(), __il); - } + { assign(__il.begin(), __il.end()); } /// Get a copy of the memory allocation object. allocator_type @@ -1255,13 +1249,70 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator()) _M_move_assign(std::move(__list), std::true_type()); else - { - // The rvalue's allocator cannot be moved, or is not equal, - // so we need to individually move each element. - this->assign(std::__make_move_if_noexcept_iterator(__list.begin()), - std::__make_move_if_noexcept_iterator(__list.end())); - __list.clear(); - } + // The rvalue's allocator cannot be moved, or is not equal, + // so we need to individually move each element. + this->assign(std::__make_move_if_noexcept_iterator(__list.begin()), + std::__make_move_if_noexcept_iterator(__list.end())); + } + + // Called by assign(_InputIterator, _InputIterator) if _Tp is + // CopyAssignable. + template + void + _M_assign(_InputIterator __first, _InputIterator __last, true_type) + { + auto __prev = before_begin(); + auto __curr = begin(); + auto __end = end(); + while (__curr != __end && __first != __last) + { + *__curr = *__first; + ++__prev; + ++__curr; + ++__first; + } + if (__first != __last) + insert_after(__prev, __first, __last); + else if (__curr != __end) + erase_after(__prev, __end); + } + + // Called by assign(_InputIterator, _InputIterator) if _Tp is not + // CopyAssignable. + template + void + _M_assign(_InputIterator __first, _InputIterator __last, false_type) + { + clear(); + insert_after(cbefore_begin(), __first, __last); + } + + // Called by assign(size_type, const _Tp&) if Tp is CopyAssignable + void + _M_assign_n(size_type __n, const _Tp& __val, true_type) + { + auto __prev = before_begin(); + auto __curr = begin(); + auto __end = end(); + while (__curr != __end && __n > 0) + { + *__curr = __val; + ++__prev; + ++__curr; + --__n; + } + if (__n > 0) + insert_after(__prev, __n, __val); + else if (__curr != __end) + erase_after(__prev, __end); + } + + // Called by assign(size_type, const _Tp&) if Tp is non-CopyAssignable + void + _M_assign_n(size_type __n, const _Tp& __val, false_type) + { + clear(); + insert_after(cbefore_begin(), __n, __val); } }; diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc index 4f9a7fa..7395b20 100644 --- a/libstdc++-v3/include/bits/forward_list.tcc +++ b/libstdc++-v3/include/bits/forward_list.tcc @@ -165,22 +165,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } std::__alloc_on_copy(__this_alloc, __that_alloc); } - iterator __prev1 = before_begin(); - iterator __curr1 = begin(); - iterator __last1 = end(); - const_iterator __first2 = __list.cbegin(); - const_iterator __last2 = __list.cend(); - while (__curr1 != __last1 && __first2 != __last2) - { - *__curr1 = *__first2; - ++__prev1; - ++__curr1; - ++__first2; - } - if (__first2 == __last2) - erase_after(__prev1, __last1); - else - insert_after(__prev1, __first2, __last2); + assign(__list.cbegin(), __list.cend()); } return *this; } diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/cons/10.cc b/libstdc++-v3/testsuite/23_containers/forward_list/cons/10.cc new file mode 100644 index 0000000..8c64ed4 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/cons/10.cc @@ -0,0 +1,58 @@ +// { dg-options "-std=gnu++11" } + +// 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 Pred 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 +// . + +// 23.3.4.2 forward_list construction [forwardlist.cons] + +#include +#include +#include + +struct Counter +{ + Counter() { ++create; } + Counter(const Counter&) { ++create; } + ~Counter() { ++destroy; } + + static int create; + static int destroy; +}; + +int Counter::create = 0; +int Counter::destroy = 0; + +void test01() +{ + typedef __gnu_test::uneq_allocator alloc; + typedef std::forward_list list; + + { + Counter c; + + list l( list(10, c, alloc(1)), alloc(2) ); + + VERIFY( Counter::create == 21 ); + VERIFY( Counter::destroy == 10 ); + } + VERIFY( Counter::destroy == 21 ); +} + +int main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/cons/11.cc b/libstdc++-v3/testsuite/23_containers/forward_list/cons/11.cc new file mode 100644 index 0000000..4c99305 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/cons/11.cc @@ -0,0 +1,50 @@ +// { dg-options "-std=gnu++11" } + +// 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 Pred 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 +// . + +// 23.3.4.2 forward_list construction [forwardlist.cons] + +#include +#include +#include + +bool fail = false; + +struct A +{ + A() = default; + A(const A&) { if (fail) throw fail; } +}; + +void test01() +{ + typedef std::forward_list list; + + list l(2); + A from[2]; + fail = true; + // Check existing elements are assigned to, instead of creating new ones. + // This is QoI, not required by the standard. + l.assign(from, from+2); + l.assign(2, from[0]); +} + +int main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/cons/12.cc b/libstdc++-v3/testsuite/23_containers/forward_list/cons/12.cc new file mode 100644 index 0000000..a1fc3c3 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/cons/12.cc @@ -0,0 +1,61 @@ +// { dg-do compile } +// { dg-options "-std=gnu++11" } + +// 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 Pred 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 +// . + +// 23.3.4.2 forward_list construction [forwardlist.cons] + +#include +#include +#include + +bool fail = false; + +struct NonCopyAssignable +{ + NonCopyAssignable() = default; + NonCopyAssignable(const NonCopyAssignable&) = default; + NonCopyAssignable(int) { } + + NonCopyAssignable& operator=(const NonCopyAssignable&) = delete; + NonCopyAssignable& operator=(int) = delete; +}; + +void test01() +{ + typedef std::forward_list list; + + list l(2); + NonCopyAssignable from[2]; + int from2[2]; + + // Assigning non-Assignable elements is QoI, not required by the standard. + + l = l; + + l.assign(from, from+2); + l.assign(2, from[0]); + + l.assign(from2, from2+2); + l.assign(2, from2[0]); +} + +int main() +{ + test01(); +}