2005-01-17 Paolo Carlini <pcarlini@suse.de>

	PR libstdc++/19433
	* include/bits/stl_tree.h (_Rb_tree<>::insert_unique(iterator,
	const _Val&), _Rb_tree<>::insert_equal(iterator, const _Val&)):
	Obtain amortized constant complexity if t is inserted right after
	p - not before p - as per Table 69.
	* testsuite/performance/23_containers/set_insert_from_sorted.cc: New.

	* testsuite/23_containers/multiset/insert/2.cc: New.
	* testsuite/23_containers/set/insert/1.cc: Likewise.

	* testsuite/performance/23_containers/set_create_from_sorted.cc:
	Simplify.

	* include/bits/stl_tree.h: Add a few missing std:: qualifications.


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

6 files changed, 308 insertions, 66 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 680a2d8140b..8bd52a5d5d4 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,20 @@
+2005-01-17  Paolo Carlini  <pcarlini@suse.de>
+
+	PR libstdc++/19433
+	* include/bits/stl_tree.h (_Rb_tree<>::insert_unique(iterator,
+	const _Val&), _Rb_tree<>::insert_equal(iterator, const _Val&)):
+	Obtain amortized constant complexity if t is inserted right after
+	p - not before p - as per Table 69.
+	* testsuite/performance/23_containers/set_insert_from_sorted.cc: New.
+	
+	* testsuite/23_containers/multiset/insert/2.cc: New.
+	* testsuite/23_containers/set/insert/1.cc: Likewise.
+	
+	* testsuite/performance/23_containers/set_create_from_sorted.cc:
+	Simplify.
+
+	* include/bits/stl_tree.h: Add a few missing std:: qualifications.
+
 2005-01-16  Jonathan Wakely  <redi@gcc.gnu.org>
 
 	* include/ext/rope: Qualify calls to std::copy() by sequence_buffer.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index a49b898e16b..197d52a2a08 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1,6 +1,6 @@
 // RB tree implementation -*- C++ -*-
 
-// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002, 2003, 2004, 2005 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
@@ -708,7 +708,7 @@ namespace std
 	       const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
     {
       return __x.size() == __y.size()
-	     && equal(__x.begin(), __x.end(), __y.begin());
+	     && std::equal(__x.begin(), __x.end(), __y.begin());
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -717,8 +717,8 @@ namespace std
     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 	      const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
     {
-      return lexicographical_compare(__x.begin(), __x.end(), 
-				     __y.begin(), __y.end());
+      return std::lexicographical_compare(__x.begin(), __x.end(), 
+					  __y.begin(), __y.end());
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -892,39 +892,29 @@ namespace std
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     insert_unique(iterator __position, const _Val& __v)
     {
-      if (__position._M_node == _M_leftmost())
+      if (__position._M_node == _M_end()
+	  || __position._M_node == _M_rightmost())
 	{
-	  // begin()
 	  if (size() > 0
-	      && _M_impl._M_key_compare(_KeyOfValue()(__v), 
-					_S_key(__position._M_node)))
-	    return _M_insert(__position._M_node, __position._M_node, __v);
-	  // First argument just needs to be non-null.
-	  else
-	    return insert_unique(__v).first;
-	}
-      else if (__position._M_node == _M_end())
-	{
-	  // end()
-	  if (_M_impl._M_key_compare(_S_key(_M_rightmost()), 
-				     _KeyOfValue()(__v)))
+	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
+					_KeyOfValue()(__v)))
 	    return _M_insert(0, _M_rightmost(), __v);
 	  else
 	    return insert_unique(__v).first;
 	}
       else
 	{
-	  iterator __before = __position;
-	  --__before;
-	  if (_M_impl._M_key_compare(_S_key(__before._M_node), 
+	  iterator __after = __position;
+	  ++__after;
+	  if (_M_impl._M_key_compare(_S_key(__position._M_node), 
 				     _KeyOfValue()(__v))
 	      && _M_impl._M_key_compare(_KeyOfValue()(__v),
-					_S_key(__position._M_node)))
+					_S_key(__after._M_node)))
 	    {
-	      if (_S_right(__before._M_node) == 0)
-		return _M_insert(0, __before._M_node, __v);
+	      if (_S_right(__position._M_node) == 0)
+		return _M_insert(0, __position._M_node, __v);
 	      else
-		return _M_insert(__position._M_node, __position._M_node, __v);
+		return _M_insert(__after._M_node, __after._M_node, __v);
 	      // First argument just needs to be non-null.
 	    }
 	  else
@@ -938,39 +928,29 @@ namespace std
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     insert_equal(iterator __position, const _Val& __v)
     {
-      if (__position._M_node == _M_leftmost())
+      if (__position._M_node == _M_end()
+	  || __position._M_node == _M_rightmost())
 	{
-	  // begin()
 	  if (size() > 0
-	      && !_M_impl._M_key_compare(_S_key(__position._M_node),
-					 _KeyOfValue()(__v)))
-	    return _M_insert(__position._M_node, __position._M_node, __v);
-	  // first argument just needs to be non-null
-	  else
-	    return insert_equal(__v);
-	}
-      else if (__position._M_node == _M_end())
-	{
-	  // end()
-	  if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
-				      _S_key(_M_rightmost())))
+	      && !_M_impl._M_key_compare(_KeyOfValue()(__v), 
+					 _S_key(_M_rightmost())))
 	    return _M_insert(0, _M_rightmost(), __v);
 	  else
 	    return insert_equal(__v);
 	}
       else
 	{
-	  iterator __before = __position;
-	  --__before;
+	  iterator __after = __position;
+	  ++__after;
 	  if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
-				      _S_key(__before._M_node))
-	      && !_M_impl._M_key_compare(_S_key(__position._M_node),
+				      _S_key(__position._M_node))
+	      && !_M_impl._M_key_compare(_S_key(__after._M_node),
 					 _KeyOfValue()(__v)))
 	    {
-	      if (_S_right(__before._M_node) == 0)
-		return _M_insert(0, __before._M_node, __v);
+	      if (_S_right(__position._M_node) == 0)
+		return _M_insert(0, __position._M_node, __v);
 	      else
-		return _M_insert(__position._M_node, __position._M_node, __v);
+		return _M_insert(__after._M_node, __after._M_node, __v);
 	      // First argument just needs to be non-null.
 	    }
 	  else
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc b/libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc
new file mode 100644
index 00000000000..6f586e4eac1
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc
@@ -0,0 +1,97 @@
+// 2005-01-17  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2005 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 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <set>
+#include <testsuite_hooks.h>
+
+// A few tests for insert with hint, in the occasion of libstdc++/19422
+// and libstdc++/19433.
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  using namespace std;
+
+  multiset<int> ms0, ms1;
+  multiset<int>::iterator iter1;
+  
+  ms0.insert(1);
+  ms1.insert(ms1.end(), 1);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(3);
+  ms1.insert(ms1.begin(), 3);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(4);
+  iter1 = ms1.insert(ms1.end(), 4);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(6);
+  ms1.insert(iter1, 6);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(2);
+  ms1.insert(ms1.begin(), 2);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(7);
+  ms1.insert(ms1.end(), 7);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(5);
+  ms1.insert(ms1.find(4), 5);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(0);
+  ms1.insert(ms1.end(), 0);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(8);
+  ms1.insert(ms1.find(3), 8);
+  VERIFY( ms0 == ms1 );
+  
+  ms0.insert(9);
+  ms1.insert(ms1.end(), 9);
+  VERIFY( ms0 == ms1 );
+
+  ms0.insert(10);
+  ms1.insert(ms1.begin(), 10);
+  VERIFY( ms0 == ms1 );
+}
+
+#if !__GXX_WEAK__ && _MT_ALLOCATOR_H
+// Explicitly instantiate for systems with no COMDAT or weak support.
+template class __gnu_cxx::__mt_alloc<std::_Rb_tree_node<int> >;
+#endif
+
+int main ()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/insert/1.cc b/libstdc++-v3/testsuite/23_containers/set/insert/1.cc
new file mode 100644
index 00000000000..7d1ef2f9d34
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/insert/1.cc
@@ -0,0 +1,97 @@
+// 2005-01-17  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2005 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 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <set>
+#include <testsuite_hooks.h>
+
+// A few tests for insert with hint, in the occasion of libstdc++/19422
+// and libstdc++/19433.
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  using namespace std;
+
+  set<int> s0, s1;
+  set<int>::iterator iter1;
+  
+  s0.insert(1);
+  s1.insert(s1.end(), 1);
+  VERIFY( s0 == s1 );
+
+  s0.insert(3);
+  s1.insert(s1.begin(), 3);
+  VERIFY( s0 == s1 );
+
+  s0.insert(4);
+  iter1 = s1.insert(s1.end(), 4);
+  VERIFY( s0 == s1 );
+
+  s0.insert(6);
+  s1.insert(iter1, 6);
+  VERIFY( s0 == s1 );
+
+  s0.insert(2);
+  s1.insert(s1.begin(), 2);
+  VERIFY( s0 == s1 );
+
+  s0.insert(7);
+  s1.insert(s1.end(), 7);
+  VERIFY( s0 == s1 );
+
+  s0.insert(5);
+  s1.insert(s1.find(4), 5);
+  VERIFY( s0 == s1 );
+
+  s0.insert(0);
+  s1.insert(s1.end(), 0);
+  VERIFY( s0 == s1 );
+
+  s0.insert(8);
+  s1.insert(s1.find(3), 8);
+  VERIFY( s0 == s1 );
+  
+  s0.insert(9);
+  s1.insert(s1.end(), 9);
+  VERIFY( s0 == s1 );
+
+  s0.insert(10);
+  s1.insert(s1.begin(), 10);
+  VERIFY( s0 == s1 );
+}
+
+#if !__GXX_WEAK__ && _MT_ALLOCATOR_H
+// Explicitly instantiate for systems with no COMDAT or weak support.
+template class __gnu_cxx::__mt_alloc<std::_Rb_tree_node<int> >;
+#endif
+
+int main ()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/performance/23_containers/set_create_from_sorted.cc b/libstdc++-v3/testsuite/performance/23_containers/set_create_from_sorted.cc
index a1b1b0d6804..17eaadd0b78 100644
--- a/libstdc++-v3/testsuite/performance/23_containers/set_create_from_sorted.cc
+++ b/libstdc++-v3/testsuite/performance/23_containers/set_create_from_sorted.cc
@@ -27,11 +27,9 @@
 
 #include <vector>
 #include <set>
-#include <list>
 #include <sstream>
 #include <testsuite_performance.h>
 
-// adjust for your setup
 static const unsigned max_size = 1000000; // avoid excessive swap file use!
 static const unsigned iterations = 10;    // make results less random while
 static const unsigned step = 50000;       // keeping the total time reasonable
@@ -45,19 +43,17 @@ int main()
   resource_counter resource;
 
   typedef set<unsigned>  the_set;
-  typedef list<unsigned> the_list;
 
   vector<unsigned> v(max_size, 0);
   for (unsigned i = 0; i != max_size; ++i)
     v[i] = i; // initialize sorted array
 
-  report_header(__FILE__, "set:");
   for (unsigned count = step; count <= max_size; count += step)
     {
       ostringstream oss;
       oss << count;
 
-      // measure set construction time
+      // measure set construction time (linear in count (Table 69))
       start_counters(time, resource);
       for (unsigned i = 0; i != iterations; ++i)
 	the_set(v.begin(), v.begin() + count);
@@ -65,19 +61,4 @@ int main()
       report_performance(__FILE__, oss.str(), time, resource);
       clear_counters(time, resource);
     }
-
-  report_header(__FILE__, "list:");
-  for (unsigned count = step; count <= max_size; count += step)
-    {
-      ostringstream oss;
-      oss << count;
-
-      // measure list construction time (surely linear in count)
-      start_counters(time, resource);
-      for (unsigned i = 0; i != iterations; ++i)
-	the_list(v.begin(), v.begin() + count);
-      stop_counters(time, resource);
-      report_performance(__FILE__, oss.str(), time, resource);
-      clear_counters(time, resource);
-    }
 }
diff --git a/libstdc++-v3/testsuite/performance/23_containers/set_insert_from_sorted.cc b/libstdc++-v3/testsuite/performance/23_containers/set_insert_from_sorted.cc
new file mode 100644
index 00000000000..48cb952a537
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/set_insert_from_sorted.cc
@@ -0,0 +1,70 @@
+// Copyright (C) 2005 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 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <vector>
+#include <set>
+#include <sstream>
+#include <testsuite_performance.h>
+
+static const unsigned max_size = 1000000; // avoid excessive swap file use!
+static const unsigned iterations = 10;    // make results less random while
+static const unsigned step = 50000;       // keeping the total time reasonable
+
+// libstdc++/19433
+int main()
+{
+  using namespace std;
+  using namespace __gnu_test;
+  time_counter time;
+  resource_counter resource;
+
+  typedef set<unsigned>  the_set;
+
+  vector<unsigned> v(max_size, 0);
+  for (unsigned i = 0; i != max_size; ++i)
+    v[i] = i; // initialize sorted array
+
+  for (unsigned count = step; count <= max_size; count += step)
+    {
+      ostringstream oss;
+      oss << count;
+
+      start_counters(time, resource);
+      for (unsigned i = 0; i != iterations; ++i)
+	{
+	  the_set test_set;
+	  the_set::iterator iter = test_set.end();
+
+	  // each insert in amortized constant time (Table 69)
+	  for (unsigned j = 0; j != count; ++j)
+	    iter = test_set.insert(iter, v[j]);
+	}
+      stop_counters(time, resource);
+      report_performance(__FILE__, oss.str(), time, resource);
+      clear_counters(time, resource);
+    }
+}