This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[v3] Fix libstdc++/19433


Hi,

tested x86/x86_64-linux, committed to mainline.

Paolo.

/////////////////
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.
diff -prN libstdc++-v3-orig/include/bits/stl_tree.h libstdc++-v3/include/bits/stl_tree.h
*** libstdc++-v3-orig/include/bits/stl_tree.h	Fri Jan 14 11:57:57 2005
--- libstdc++-v3/include/bits/stl_tree.h	Mon Jan 17 12:50:30 2005
***************
*** 1,6 ****
  // RB tree implementation -*- C++ -*-
  
! // Copyright (C) 2001, 2002, 2003, 2004 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
--- 1,6 ----
  // RB tree implementation -*- C++ -*-
  
! // 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
*************** namespace std
*** 708,714 ****
  	       const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
      {
        return __x.size() == __y.size()
! 	     && equal(__x.begin(), __x.end(), __y.begin());
      }
  
    template<typename _Key, typename _Val, typename _KeyOfValue,
--- 708,714 ----
  	       const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
      {
        return __x.size() == __y.size()
! 	     && std::equal(__x.begin(), __x.end(), __y.begin());
      }
  
    template<typename _Key, typename _Val, typename _KeyOfValue,
*************** namespace std
*** 717,724 ****
      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());
      }
  
    template<typename _Key, typename _Val, typename _KeyOfValue,
--- 717,724 ----
      operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  	      const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
      {
!       return std::lexicographical_compare(__x.begin(), __x.end(), 
! 					  __y.begin(), __y.end());
      }
  
    template<typename _Key, typename _Val, typename _KeyOfValue,
*************** namespace std
*** 892,930 ****
      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
      insert_unique(iterator __position, const _Val& __v)
      {
!       if (__position._M_node == _M_leftmost())
  	{
- 	  // 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)))
  	    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), 
  				     _KeyOfValue()(__v))
  	      && _M_impl._M_key_compare(_KeyOfValue()(__v),
! 					_S_key(__position._M_node)))
  	    {
! 	      if (_S_right(__before._M_node) == 0)
! 		return _M_insert(0, __before._M_node, __v);
  	      else
! 		return _M_insert(__position._M_node, __position._M_node, __v);
  	      // First argument just needs to be non-null.
  	    }
  	  else
--- 892,920 ----
      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
      insert_unique(iterator __position, const _Val& __v)
      {
!       if (__position._M_node == _M_end()
! 	  || __position._M_node == _M_rightmost())
  	{
  	  if (size() > 0
! 	      && _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 __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(__after._M_node)))
  	    {
! 	      if (_S_right(__position._M_node) == 0)
! 		return _M_insert(0, __position._M_node, __v);
  	      else
! 		return _M_insert(__after._M_node, __after._M_node, __v);
  	      // First argument just needs to be non-null.
  	    }
  	  else
*************** namespace std
*** 938,976 ****
      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
      insert_equal(iterator __position, const _Val& __v)
      {
!       if (__position._M_node == _M_leftmost())
  	{
- 	  // 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())))
  	    return _M_insert(0, _M_rightmost(), __v);
  	  else
  	    return insert_equal(__v);
  	}
        else
  	{
! 	  iterator __before = __position;
! 	  --__before;
  	  if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
! 				      _S_key(__before._M_node))
! 	      && !_M_impl._M_key_compare(_S_key(__position._M_node),
  					 _KeyOfValue()(__v)))
  	    {
! 	      if (_S_right(__before._M_node) == 0)
! 		return _M_insert(0, __before._M_node, __v);
  	      else
! 		return _M_insert(__position._M_node, __position._M_node, __v);
  	      // First argument just needs to be non-null.
  	    }
  	  else
--- 928,956 ----
      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
      insert_equal(iterator __position, const _Val& __v)
      {
!       if (__position._M_node == _M_end()
! 	  || __position._M_node == _M_rightmost())
  	{
  	  if (size() > 0
! 	      && !_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 __after = __position;
! 	  ++__after;
  	  if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
! 				      _S_key(__position._M_node))
! 	      && !_M_impl._M_key_compare(_S_key(__after._M_node),
  					 _KeyOfValue()(__v)))
  	    {
! 	      if (_S_right(__position._M_node) == 0)
! 		return _M_insert(0, __position._M_node, __v);
  	      else
! 		return _M_insert(__after._M_node, __after._M_node, __v);
  	      // First argument just needs to be non-null.
  	    }
  	  else
diff -prN libstdc++-v3-orig/testsuite/23_containers/multiset/insert/2.cc libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc
*** libstdc++-v3-orig/testsuite/23_containers/multiset/insert/2.cc	Thu Jan  1 01:00:00 1970
--- libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc	Sun Jan 16 14:44:02 2005
***************
*** 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 -prN libstdc++-v3-orig/testsuite/23_containers/set/insert/1.cc libstdc++-v3/testsuite/23_containers/set/insert/1.cc
*** libstdc++-v3-orig/testsuite/23_containers/set/insert/1.cc	Thu Jan  1 01:00:00 1970
--- libstdc++-v3/testsuite/23_containers/set/insert/1.cc	Sun Jan 16 14:43:04 2005
***************
*** 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 -prN libstdc++-v3-orig/testsuite/performance/23_containers/set_create_from_sorted.cc libstdc++-v3/testsuite/performance/23_containers/set_create_from_sorted.cc
*** libstdc++-v3-orig/testsuite/performance/23_containers/set_create_from_sorted.cc	Fri Jan 14 18:28:13 2005
--- libstdc++-v3/testsuite/performance/23_containers/set_create_from_sorted.cc	Sun Jan 16 11:37:25 2005
***************
*** 27,37 ****
  
  #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
--- 27,35 ----
*************** int main()
*** 45,63 ****
    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
        start_counters(time, resource);
        for (unsigned i = 0; i != iterations; ++i)
  	the_set(v.begin(), v.begin() + count);
--- 43,59 ----
    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;
  
!       // 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);
*************** int main()
*** 65,83 ****
        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);
-     }
  }
--- 61,64 ----
diff -prN libstdc++-v3-orig/testsuite/performance/23_containers/set_insert_from_sorted.cc libstdc++-v3/testsuite/performance/23_containers/set_insert_from_sorted.cc
*** libstdc++-v3-orig/testsuite/performance/23_containers/set_insert_from_sorted.cc	Thu Jan  1 01:00:00 1970
--- libstdc++-v3/testsuite/performance/23_containers/set_insert_from_sorted.cc	Sun Jan 16 14:17:22 2005
***************
*** 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);
+     }
+ }

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]