From patchwork Thu Nov 1 01:32:48 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [v3] Reuse existing elements in forward_list::assign() Date: Wed, 31 Oct 2012 15:32:48 -0000 From: Jonathan Wakely X-Patchwork-Id: 196070 Message-Id: To: "libstdc++" , gcc-patches 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(); +}