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

	PR libstdc++/22102 (insert as close to hint as possible)
	* include/bits/stl_tree.h (_Rb_tree<>::_M_insert_lower,
	_M_insert_equal_lower): New.
	(_M_insert_equal(iterator, const _Val&),
	_M_insert_equal(const_iterator, const _Val&)): Use the above.
	* docs/html/ext/howto.html: Add an entry for DR 233.
	* testsuite/23_containers/multiset/modifiers/insert/22102.cc: New.
	* testsuite/23_containers/multimap/modifiers/insert/22102.cc: New.

	* testsuite/23_containers/set/insert/: Move...
	* testsuite/23_containers/set/modifiers/insert/: ...here.
	* testsuite/23_containers/map/insert/: Move...
	* testsuite/23_containers/map/modifiers/insert/: ...here.
	* testsuite/23_containers/multiset/insert/: Move...
	* testsuite/23_containers/multiset/modifiers/insert/: ...here.


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

10 files changed, 354 insertions, 2 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 820d7c15833..5e5e1b86ffd 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,21 @@
+2006-01-08  Paolo Carlini  <pcarlini@suse.de>
+
+	PR libstdc++/22102 (insert as close to hint as possible)
+	* include/bits/stl_tree.h (_Rb_tree<>::_M_insert_lower,
+	_M_insert_equal_lower): New.
+	(_M_insert_equal(iterator, const _Val&),
+	_M_insert_equal(const_iterator, const _Val&)): Use the above.
+	* docs/html/ext/howto.html: Add an entry for DR 233.
+	* testsuite/23_containers/multiset/modifiers/insert/22102.cc: New.
+	* testsuite/23_containers/multimap/modifiers/insert/22102.cc: New.
+
+	* testsuite/23_containers/set/insert/: Move...
+	* testsuite/23_containers/set/modifiers/insert/: ...here.
+	* testsuite/23_containers/map/insert/: Move...
+	* testsuite/23_containers/map/modifiers/insert/: ...here.
+	* testsuite/23_containers/multiset/insert/: Move...
+	* testsuite/23_containers/multiset/modifiers/insert/: ...here.
+
 2006-01-06  Paolo Carlini  <pcarlini@suse.de>
 
 	* include/bits/stl_tree.h (_Rb_tree<>::insert_unique): Rename
diff --git a/libstdc++-v3/docs/html/ext/howto.html b/libstdc++-v3/docs/html/ext/howto.html
index 9d86bc04162..bc0b358b9f3 100644
--- a/libstdc++-v3/docs/html/ext/howto.html
+++ b/libstdc++-v3/docs/html/ext/howto.html
@@ -399,6 +399,13 @@
         is specified in the conversion specification.
     </dd>
 
+    <dt><a href="lwg-active.html#233">233</a>:
+        <em>Insertion hints in associative containers</em>
+    </dt>
+    <dd>Implement N1780, first check before then check after, insert as close
+        to hint as possible.
+    </dd>
+
     <dt><a href="lwg-defects.html#235">235</a>:
         <em>No specification of default ctor for reverse_iterator</em>
     </dt>
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 031e37f44fb..ecea171c457 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -548,6 +548,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       iterator
       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 233. Insertion hints in associative containers.
+      iterator
+      _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
+
       const_iterator
       _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
 		const value_type& __v);
@@ -657,6 +662,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       iterator
       _M_insert_equal(const value_type& __x);
 
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 233. Insertion hints in associative containers.
+      iterator
+      _M_insert_equal_lower(const value_type& __x);
+
       iterator
       _M_insert_unique(iterator __position, const value_type& __x);
 
@@ -835,6 +845,24 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
+    {
+      bool __insert_left = (__x != 0 || __p == _M_end()
+			    || !_M_impl._M_key_compare(_S_key(__p),
+						       _KeyOfValue()(__v)));
+
+      _Link_type __z = _M_create_node(__v);
+
+      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
+				    this->_M_impl._M_header);
+      ++_M_impl._M_node_count;
+      return iterator(__z);
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
@@ -871,6 +899,23 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_insert_equal_lower(const _Val& __v)
+    {
+      _Link_type __x = _M_begin();
+      _Link_type __y = _M_end();
+      while (__x != 0)
+	{
+	  __y = __x;
+	  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
+	        _S_left(__x) : _S_right(__x);
+	}
+      return _M_insert_lower(__x, __y, __v);
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
     void
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
@@ -1110,7 +1155,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 		return _M_insert(__after._M_node, __after._M_node, __v);
 	    }
 	  else
-	    return _M_insert_equal(__v);
+	    return _M_insert_equal_lower(__v);
 	}
     }
 
@@ -1164,7 +1209,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 		return _M_insert(__after._M_node, __after._M_node, __v);
 	    }
 	  else
-	    return const_iterator(_M_insert_equal(__v));
+	    return const_iterator(_M_insert_equal_lower(__v));
 	}
     }
 
diff --git a/libstdc++-v3/testsuite/23_containers/map/insert/1.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/1.cc
index 7bf7a6cb96a..7bf7a6cb96a 100644
--- a/libstdc++-v3/testsuite/23_containers/map/insert/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/map/insert/16813.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/16813.cc
index 1132aad7748..1132aad7748 100644
--- a/libstdc++-v3/testsuite/23_containers/map/insert/16813.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/16813.cc
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/modifiers/insert/22102.cc b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/insert/22102.cc
new file mode 100644
index 00000000000..dfaf4c252d7
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/insert/22102.cc
@@ -0,0 +1,141 @@
+// 2006-01-07  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 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// 23.3.2  Class template multimap
+
+#include <map>
+#include <testsuite_hooks.h>
+
+// libstdc++/22102
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef std::multimap<int, int>   Mmap;
+  typedef Mmap::value_type          value_type;
+  typedef Mmap::iterator            iterator;
+  
+  Mmap mm1;
+  
+  const iterator it1 = mm1.insert(value_type(0, 0));
+  const iterator it2 = mm1.insert(value_type(1, 1));  
+  const iterator it3 = mm1.insert(value_type(2, 2));
+
+  const value_type vt1(2, 1);
+  const iterator it4 = mm1.insert(it1, vt1);
+  iterator it5 = it4;
+  iterator it6 = it4;
+  VERIFY( mm1.size() == 4 );
+  VERIFY( *it4 == vt1 );
+  VERIFY( ++it5 == it3 );
+  VERIFY( --it6 == it2 );
+  VERIFY( *it5 == *it3 );
+  VERIFY( *it6 == *it2 );
+
+  const value_type vt2(2, 0);
+  const iterator it7 = mm1.insert(mm1.begin(), vt2);
+  iterator it8 = it7;
+  iterator it9 = it7;
+  VERIFY( mm1.size() == 5 );
+  VERIFY( *it7 == vt2 );
+  VERIFY( ++it8 == it4 );
+  VERIFY( --it9 == it2 );
+  VERIFY( *it8 == *it4 );
+  VERIFY( *it9 == *it2 );
+
+  const value_type vt3(2, -1);
+  const iterator it10 = mm1.insert(it1, vt3);
+  iterator it11 = it10;
+  iterator it12 = it10;
+  VERIFY( mm1.size() == 6 );
+  VERIFY( *it10 == vt3 );
+  VERIFY( ++it11 == it7 );
+  VERIFY( --it12 == it2 );
+  VERIFY( *it11 == *it7 );
+  VERIFY( *it12 == *it2 );
+
+  const value_type vt4(0, 1);
+  const iterator it13 = mm1.insert(it10, vt4);
+  iterator it14 = it13;
+  iterator it15 = it13;
+  VERIFY( mm1.size() == 7 );
+  VERIFY( *it13 == vt4 );
+  VERIFY( ++it14 == it2 );
+  VERIFY( --it15 == it1 );
+  VERIFY( *it14 == *it2 );
+  VERIFY( *it15 == *it1 );
+
+  const value_type vt5(1, 0);
+  const iterator it16 = mm1.insert(it13, vt5);
+  iterator it17 = it16;
+  iterator it18 = it16;
+  VERIFY( mm1.size() == 8 );
+  VERIFY( *it16 == vt5 );
+  VERIFY( ++it17 == it2 );
+  VERIFY( --it18 == it13 );
+  VERIFY( *it17 == *it2 );
+  VERIFY( *it18 == *it13 );
+
+  const value_type vt6(0, -1);
+  const iterator it19 = mm1.insert(it1, vt6);
+  iterator it20 = it19;
+  VERIFY( mm1.size() == 9 );
+  VERIFY( *it19 == vt6 );
+  VERIFY( it19 == mm1.begin() );
+  VERIFY( ++it20 == it1 );
+  VERIFY( *it20 == *it1 );
+
+  const value_type vt7(3, 3);
+  const iterator it21 = mm1.insert(it19, vt7);
+  iterator it22 = it21;
+  iterator it23 = it21;
+  VERIFY( mm1.size() == 10 );
+  VERIFY( *it21 == vt7 );
+  VERIFY( ++it22 == mm1.end() );
+  VERIFY( --it23 == it3 );
+  VERIFY( *it23 == *it3 );
+
+  const value_type vt8(2, 3);
+  const iterator it24 = mm1.insert(mm1.end(), vt8);
+  iterator it25 = it24;
+  iterator it26 = it24;
+  VERIFY( mm1.size() == 11 );
+  VERIFY( *it24 == vt8 );
+  VERIFY( ++it25 == it21 );
+  VERIFY( --it26 == it3 );
+  VERIFY( *it25 == *it21 );
+  VERIFY( *it26 == *it3 );   
+    
+  const value_type vt9(3, 2);
+  const iterator it27 = mm1.insert(it3, vt9);
+  iterator it28 = it27;
+  iterator it29 = it27;
+  VERIFY( mm1.size() == 12 );
+  VERIFY( *it27 == vt9 );
+  VERIFY( ++it28 == it21 );
+  VERIFY( --it29 == it24 );
+  VERIFY( *it28 == *it21 );
+  VERIFY( *it29 == *it24 ); 
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/insert/1.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/1.cc
index c1a5de3dc74..c1a5de3dc74 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/insert/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/2.cc
index 0f654cb0500..0f654cb0500 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/2.cc
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/22102.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/22102.cc
new file mode 100644
index 00000000000..99b808f1b33
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/22102.cc
@@ -0,0 +1,141 @@
+// 2006-01-07  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 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// 23.3.4  Class template multiset
+
+#include <set>
+#include <testsuite_hooks.h>
+
+// libstdc++/22102
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef std::multiset<int>        Mset;
+  typedef Mset::value_type          value_type;
+  typedef Mset::iterator            iterator;
+  
+  Mset ms1;
+  
+  const iterator it1 = ms1.insert(value_type(0));
+  const iterator it2 = ms1.insert(value_type(1));  
+  const iterator it3 = ms1.insert(value_type(2));
+
+  const value_type vt1(2);
+  const iterator it4 = ms1.insert(it1, vt1);
+  iterator it5 = it4;
+  iterator it6 = it4;
+  VERIFY( ms1.size() == 4 );
+  VERIFY( *it4 == vt1 );
+  VERIFY( ++it5 == it3 );
+  VERIFY( --it6 == it2 );
+  VERIFY( *it5 == *it3 );
+  VERIFY( *it6 == *it2 );
+
+  const value_type vt2(2);
+  const iterator it7 = ms1.insert(ms1.begin(), vt2);
+  iterator it8 = it7;
+  iterator it9 = it7;
+  VERIFY( ms1.size() == 5 );
+  VERIFY( *it7 == vt2 );
+  VERIFY( ++it8 == it4 );
+  VERIFY( --it9 == it2 );
+  VERIFY( *it8 == *it4 );
+  VERIFY( *it9 == *it2 );
+
+  const value_type vt3(2);
+  const iterator it10 = ms1.insert(it1, vt3);
+  iterator it11 = it10;
+  iterator it12 = it10;
+  VERIFY( ms1.size() == 6 );
+  VERIFY( *it10 == vt3 );
+  VERIFY( ++it11 == it7 );
+  VERIFY( --it12 == it2 );
+  VERIFY( *it11 == *it7 );
+  VERIFY( *it12 == *it2 );
+
+  const value_type vt4(0);
+  const iterator it13 = ms1.insert(it10, vt4);
+  iterator it14 = it13;
+  iterator it15 = it13;
+  VERIFY( ms1.size() == 7 );
+  VERIFY( *it13 == vt4 );
+  VERIFY( ++it14 == it2 );
+  VERIFY( --it15 == it1 );
+  VERIFY( *it14 == *it2 );
+  VERIFY( *it15 == *it1 );
+
+  const value_type vt5(1);
+  const iterator it16 = ms1.insert(it13, vt5);
+  iterator it17 = it16;
+  iterator it18 = it16;
+  VERIFY( ms1.size() == 8 );
+  VERIFY( *it16 == vt5 );
+  VERIFY( ++it17 == it2 );
+  VERIFY( --it18 == it13 );
+  VERIFY( *it17 == *it2 );
+  VERIFY( *it18 == *it13 );
+
+  const value_type vt6(0);
+  const iterator it19 = ms1.insert(it1, vt6);
+  iterator it20 = it19;
+  VERIFY( ms1.size() == 9 );
+  VERIFY( *it19 == vt6 );
+  VERIFY( it19 == ms1.begin() );
+  VERIFY( ++it20 == it1 );
+  VERIFY( *it20 == *it1 );
+
+  const value_type vt7(3);
+  const iterator it21 = ms1.insert(it19, vt7);
+  iterator it22 = it21;
+  iterator it23 = it21;
+  VERIFY( ms1.size() == 10 );
+  VERIFY( *it21 == vt7 );
+  VERIFY( ++it22 == ms1.end() );
+  VERIFY( --it23 == it3 );
+  VERIFY( *it23 == *it3 );
+
+  const value_type vt8(2);
+  const iterator it24 = ms1.insert(ms1.end(), vt8);
+  iterator it25 = it24;
+  iterator it26 = it24;
+  VERIFY( ms1.size() == 11 );
+  VERIFY( *it24 == vt8 );
+  VERIFY( ++it25 == it21 );
+  VERIFY( --it26 == it3 );
+  VERIFY( *it25 == *it21 );
+  VERIFY( *it26 == *it3 );   
+    
+  const value_type vt9(3);
+  const iterator it27 = ms1.insert(it3, vt9);
+  iterator it28 = it27;
+  iterator it29 = it27;
+  VERIFY( ms1.size() == 12 );
+  VERIFY( *it27 == vt9 );
+  VERIFY( ++it28 == it21 );
+  VERIFY( --it29 == it24 );
+  VERIFY( *it28 == *it21 );
+  VERIFY( *it29 == *it24 ); 
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/insert/1.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/insert/1.cc
index 22fdf0debbb..22fdf0debbb 100644
--- a/libstdc++-v3/testsuite/23_containers/set/insert/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/insert/1.cc