2006-01-19 Paolo Carlini <pcarlini@suse.de>

	Implement list::splice (and merge) bits of N1599
	* include/bits/stl_list.h (list<>::_M_check_equal_allocators): New.
	(list<>::splice(iterator, list&), splice(iterator, list&, iterator),
	splice(iterator, list&, iterator, iterator)): Use it.
	* include/bits/stl_list.h (list<>::merge(list&), merge(list&,
	_StrictWeakOrdering)): Likewise.
	* testsuite/23_containers/list/operators/5.cc: New.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@110011 138bc75d-0d04-0410-961f-82ee72b054a4

4 files changed, 214 insertions, 35 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 2ee8841e134..d699d6f16d7 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,13 @@
+2006-01-19  Paolo Carlini  <pcarlini@suse.de>
+
+	Implement list::splice (and merge) bits of N1599
+	* include/bits/stl_list.h (list<>::_M_check_equal_allocators): New.
+	(list<>::splice(iterator, list&), splice(iterator, list&, iterator),
+	splice(iterator, list&, iterator, iterator)): Use it.
+	* include/bits/stl_list.h (list<>::merge(list&), merge(list&,
+	_StrictWeakOrdering)): Likewise.
+	* testsuite/23_containers/list/operators/5.cc: New.
+
 2006-01-19  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR libstdc++/25797
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index 355ec75ba95..f2849fb6e52 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -1,6 +1,7 @@
 // List implementation (out of line) -*- C++ -*-
 
-// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
+// 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
@@ -214,6 +215,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
       // 300. list::merge() specification incomplete
       if (this != &__x)
 	{
+	  _M_check_equal_allocators(__x); 
+
 	  iterator __first1 = begin();
 	  iterator __last1 = end();
 	  iterator __first2 = __x.begin();
@@ -233,6 +236,36 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
     }
 
   template<typename _Tp, typename _Alloc>
+    template <typename _StrictWeakOrdering>
+      void
+      list<_Tp, _Alloc>::
+      merge(list& __x, _StrictWeakOrdering __comp)
+      {
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 300. list::merge() specification incomplete
+	if (this != &__x)
+	  {
+	    _M_check_equal_allocators(__x);
+
+	    iterator __first1 = begin();
+	    iterator __last1 = end();
+	    iterator __first2 = __x.begin();
+	    iterator __last2 = __x.end();
+	    while (__first1 != __last1 && __first2 != __last2)
+	      if (__comp(*__first2, *__first1))
+		{
+		  iterator __next = __first2;
+		  _M_transfer(__first1, __first2, ++__next);
+		  __first2 = __next;
+		}
+	      else
+		++__first1;
+	    if (__first2 != __last2)
+	      _M_transfer(__last1, __first2, __last2);
+	  }
+      }
+
+  template<typename _Tp, typename _Alloc>
     void
     list<_Tp, _Alloc>::
     sort()
@@ -312,34 +345,6 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
     template <typename _StrictWeakOrdering>
       void
       list<_Tp, _Alloc>::
-      merge(list& __x, _StrictWeakOrdering __comp)
-      {
-	// _GLIBCXX_RESOLVE_LIB_DEFECTS
-	// 300. list::merge() specification incomplete
-	if (this != &__x)
-	  {
-	    iterator __first1 = begin();
-	    iterator __last1 = end();
-	    iterator __first2 = __x.begin();
-	    iterator __last2 = __x.end();
-	    while (__first1 != __last1 && __first2 != __last2)
-	      if (__comp(*__first2, *__first1))
-		{
-		  iterator __next = __first2;
-		  _M_transfer(__first1, __first2, ++__next);
-		  __first2 = __next;
-		}
-	      else
-		++__first1;
-	    if (__first2 != __last2)
-	      _M_transfer(__last1, __first2, __last2);
-	  }
-      }
-
-  template<typename _Tp, typename _Alloc>
-    template <typename _StrictWeakOrdering>
-      void
-      list<_Tp, _Alloc>::
       sort(_StrictWeakOrdering __comp)
       {
 	// Do nothing if the list has length 0 or 1.
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index 513833c71ef..5ae400f6f0f 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -919,12 +919,18 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
        *  The elements of @a x are inserted in constant time in front of
        *  the element referenced by @a position.  @a x becomes an empty
        *  list.
+       *
+       *  Requires this != @a x.
        */
       void
       splice(iterator __position, list& __x)
       {
 	if (!__x.empty())
-	  this->_M_transfer(__position, __x.begin(), __x.end());
+	  {
+	    _M_check_equal_allocators(__x);
+
+	    this->_M_transfer(__position, __x.begin(), __x.end());
+	  }
       }
 
       /**
@@ -937,12 +943,16 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
        *  inserts it into the current list before @a position.
        */
       void
-      splice(iterator __position, list&, iterator __i)
+      splice(iterator __position, list& __x, iterator __i)
       {
 	iterator __j = __i;
 	++__j;
 	if (__position == __i || __position == __j)
 	  return;
+
+	if (this != &__x)
+	  _M_check_equal_allocators(__x);
+
 	this->_M_transfer(__position, __i, __j);
       }
 
@@ -959,10 +969,15 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
        *  Undefined if @a position is in [first,last).
        */
       void
-      splice(iterator __position, list&, iterator __first, iterator __last)
+      splice(iterator __position, list& __x, iterator __first, iterator __last)
       {
 	if (__first != __last)
-	  this->_M_transfer(__position, __first, __last);
+	  {
+	    if (this != &__x)
+	      _M_check_equal_allocators(__x);
+
+	    this->_M_transfer(__position, __first, __last);
+	  }
       }
 
       /**
@@ -991,8 +1006,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
        *  responsibilty.
        */
       template<typename _Predicate>
-      void
-      remove_if(_Predicate);
+        void
+        remove_if(_Predicate);
 
       /**
        *  @brief  Remove consecutive duplicate elements.
@@ -1156,6 +1171,14 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
         _M_get_Tp_allocator().destroy(&__n->_M_data);
         _M_put_node(__n);
       }
+
+      // To implement the splice (and merge) bits of N1599.
+      void
+      _M_check_equal_allocators(list& __x)
+      {
+	if (_M_get_Node_allocator() != __x._M_get_Node_allocator())
+	  __throw_runtime_error(__N("list::_M_check_equal_allocators"));
+      }
     };
 
   /**
diff --git a/libstdc++-v3/testsuite/23_containers/list/operators/5.cc b/libstdc++-v3/testsuite/23_containers/list/operators/5.cc
new file mode 100644
index 00000000000..22f504691d9
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/operators/5.cc
@@ -0,0 +1,141 @@
+// 2006-01-19  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2006 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// 23.2.2.4 list operations [lib.list.ops]
+
+#include <list>
+#include <stdexcept>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+// Check the splice (and merge) bits of N1599.
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+  
+  typedef __gnu_test::uneq_allocator<int> my_alloc;
+  typedef std::list<int, my_alloc> my_list;
+
+  const int data1[] = {1, 2, 3, 4, 5};
+  const int data2[] = {6, 7, 8, 9, 10};
+  const size_t N1 = sizeof(data1) / sizeof(int);
+  const size_t N2 = sizeof(data2) / sizeof(int);
+  
+  my_alloc alloc01(1), alloc02(2);
+
+  my_list l01(data1, data1 + N1, alloc01);
+  const my_list l01_ref = l01;
+
+  my_list l02(data2, data2 + N2, alloc02);
+  const my_list l02_ref = l02;
+
+  bool catched = false;
+
+  try
+    {
+      l01.splice(l01.begin(), l02);
+    }
+  catch(std::runtime_error&)
+    {
+      catched = true;
+    }
+  catch(...)
+    {
+      VERIFY( false );
+    }
+  VERIFY( catched );
+  VERIFY( l01 == l01_ref );
+  VERIFY( l02 == l02_ref );
+  
+  catched = false;
+  try
+    {
+      l01.splice(l01.begin(), l02, l02.begin());
+    }
+  catch(std::runtime_error&)
+    {
+      catched = true;
+    }
+  catch(...)
+    {
+      VERIFY( false );
+    }
+  VERIFY( catched );
+  VERIFY( l01 == l01_ref );
+  VERIFY( l02 == l02_ref );
+
+  catched = false;
+  try
+    {
+      l01.splice(l01.begin(), l02, l02.begin(), l02.end());
+    }
+  catch(std::runtime_error&)
+    {
+      catched = true;
+    }
+  catch(...)
+    {
+      VERIFY( false );
+    }
+  VERIFY( catched );
+  VERIFY( l01 == l01_ref );
+  VERIFY( l02 == l02_ref );
+
+  catched = false;
+  try
+    {
+      l01.merge(l02);
+    }
+  catch(std::runtime_error&)
+    {
+      catched = true;
+    }
+  catch(...)
+    {
+      VERIFY( false );
+    }
+  VERIFY( catched );
+  VERIFY( l01 == l01_ref );
+  VERIFY( l02 == l02_ref );
+
+  catched = false;
+  try
+    {
+      l01.merge(l02, std::less<int>());
+    }
+  catch(std::runtime_error&)
+    {
+      catched = true;
+    }
+  catch(...)
+    {
+      VERIFY( false );
+    }
+  VERIFY( catched );
+  VERIFY( l01 == l01_ref );
+  VERIFY( l02 == l02_ref );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}