Patchwork [v3] Reuse existing elements in forward_list::assign()

login
register
mail settings
Submitter Jonathan Wakely
Date Nov. 1, 2012, 1:32 a.m.
Message ID <CAH6eHdR-DD9g+nSpE5BiAxY_Q12J=TQ9nCiyv+mFjgt4NUR40g@mail.gmail.com>
Download mbox | patch
Permalink /patch/196070/
State New
Headers show

Comments

Jonathan Wakely - Nov. 1, 2012, 1:32 a.m.
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 <jwakely.gcc@gmail.com>
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.

Patch

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<typename _InputIterator,
@@ -597,9 +597,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	void
         assign(_InputIterator __first, _InputIterator __last)
         {
-          clear();
-          insert_after(cbefore_begin(), __first, __last);
-        }
+	  typedef is_assignable<_Tp, decltype(*__first)> __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<typename _InputIterator>
+	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<typename _InputIterator>
+	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
+// <http://www.gnu.org/licenses/>.
+
+// 23.3.4.2 forward_list construction [forwardlist.cons]
+
+#include <forward_list>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+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<Counter> alloc;
+  typedef std::forward_list<Counter, alloc> 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
+// <http://www.gnu.org/licenses/>.
+
+// 23.3.4.2 forward_list construction [forwardlist.cons]
+
+#include <forward_list>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+bool fail = false;
+
+struct A
+{
+  A() = default;
+  A(const A&) { if (fail) throw fail; }
+};
+
+void test01()
+{
+  typedef std::forward_list<A> 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
+// <http://www.gnu.org/licenses/>.
+
+// 23.3.4.2 forward_list construction [forwardlist.cons]
+
+#include <forward_list>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+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<NonCopyAssignable> 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();
+}