This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] libstdc++/19433
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Sun, 16 Jan 2005 15:12:38 +0100
- Subject: [Patch] libstdc++/19433
Hi,
this is what I have tested and performance tested on x86/x86_64-linux,
includes a few basic correctness tests for insert with hint.
All in all, the fix is rather straightforward: begin() is not a special
case anymore, whereas "rightmost" is dealt with the same way of end().
Will wait 'til tomorrow, in case of comments...
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.
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 Sun Jan 16 11:57:04 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
*** 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);
+ }
+ }