re PR libstdc++/33613 (compilation inconsistency upper_bound vs lower_bound with -D_GLIBCXX_DEBUG)

2007-10-03  Paolo Carlini  <pcarlini@suse.de>

	PR libstdc++/33613
	* include/debug/functions.h (__check_partitioned): Rename to...
	(__check_partioned_lower): ... this.
	(__check_partioned_upper): Add.
	* include/debug/macros.h (__glibcxx_check_partitioned): Rename to...
	(__glibcxx_check_partitioned_lower): ... this, adjust.
	(__glibcxx_check_partitioned_upper): Add.
	* include/debug/debug.h (__glibcxx_requires_partitioned): Rename to...
	(__glibcxx_requires_partitioned_lower): ... this, adjust.
	(__glibcxx_requires_partitioned_upper): Add.
	* include/bits/stl_algo.h (lower_bound, upper_bound, equal_range,
	binary search): Use the above.
	* testsuite/25_algorithms/lower_bound/33613.cc: New.
	* testsuite/25_algorithms/upper_bound/33613.cc: Likewise.

From-SVN: r128974

7 files changed, 176 insertions, 24 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 8350df8..275739f 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,20 @@
+2007-10-03  Paolo Carlini  <pcarlini@suse.de>
+
+	PR libstdc++/33613
+	* include/debug/functions.h (__check_partitioned): Rename to...
+	(__check_partioned_lower): ... this.
+	(__check_partioned_upper): Add.
+	* include/debug/macros.h (__glibcxx_check_partitioned): Rename to...
+	(__glibcxx_check_partitioned_lower): ... this, adjust.
+	(__glibcxx_check_partitioned_upper): Add.
+	* include/debug/debug.h (__glibcxx_requires_partitioned): Rename to...
+	(__glibcxx_requires_partitioned_lower): ... this, adjust.
+	(__glibcxx_requires_partitioned_upper): Add.
+	* include/bits/stl_algo.h (lower_bound, upper_bound, equal_range,
+	binary search): Use the above.
+	* testsuite/25_algorithms/lower_bound/33613.cc: New.
+	* testsuite/25_algorithms/upper_bound/33613.cc: Likewise.
+
 2007-10-03  Kazu Hirata  <kazu@codesourcery.com>
 
 	Revert:
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 561609d..cd14190 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2186,7 +2186,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
-      __glibcxx_requires_partitioned(__first, __last, __val);
+      __glibcxx_requires_partitioned_lower(__first, __last, __val);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2237,7 +2237,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _ValueType, _Tp>)
-      __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
+      __glibcxx_requires_partitioned_lower_pred(__first, __last,
+						__val, __comp);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2283,7 +2284,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
-      __glibcxx_requires_partitioned(__first, __last, __val);
+      __glibcxx_requires_partitioned_upper(__first, __last, __val);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2334,7 +2335,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _Tp, _ValueType>)
-      __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
+      __glibcxx_requires_partitioned_upper_pred(__first, __last,
+						__val, __comp);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2387,7 +2389,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)	
-      __glibcxx_requires_partitioned(__first, __last, __val);
+      __glibcxx_requires_partitioned_lower(__first, __last, __val);
+      __glibcxx_requires_partitioned_upper(__first, __last, __val);      
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2451,7 +2454,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 				  _ValueType, _Tp>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _Tp, _ValueType>)
-      __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
+      __glibcxx_requires_partitioned_lower_pred(__first, __last,
+						__val, __comp);
+      __glibcxx_requires_partitioned_upper_pred(__first, __last,
+						__val, __comp);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2503,7 +2509,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
-      __glibcxx_requires_partitioned(__first, __last, __val);
+      __glibcxx_requires_partitioned_lower(__first, __last, __val);
+      __glibcxx_requires_partitioned_upper(__first, __last, __val);
 
       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
       return __i != __last && !(__val < *__i);
@@ -2536,7 +2543,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _Tp, _ValueType>)
-      __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
+      __glibcxx_requires_partitioned_lower_pred(__first, __last,
+						__val, __comp);
+      __glibcxx_requires_partitioned_upper_pred(__first, __last,
+						__val, __comp);
 
       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
       return __i != __last && !bool(__comp(__val, *__i));
diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
index d488f15..46e4b6bf 100644
--- a/libstdc++-v3/include/debug/debug.h
+++ b/libstdc++-v3/include/debug/debug.h
@@ -69,8 +69,10 @@ namespace __gnu_debug
 # define __glibcxx_requires_valid_range(_First,_Last)
 # define __glibcxx_requires_sorted(_First,_Last)
 # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred)
-# define __glibcxx_requires_partitioned(_First,_Last,_Value)
-# define __glibcxx_requires_partitioned_pred(_First,_Last,_Value,_Pred)
+# define __glibcxx_requires_partitioned_lower(_First,_Last,_Value)
+# define __glibcxx_requires_partitioned_upper(_First,_Last,_Value)
+# define __glibcxx_requires_partitioned_lower_pred(_First,_Last,_Value,_Pred)
+# define __glibcxx_requires_partitioned_upper_pred(_First,_Last,_Value,_Pred)
 # define __glibcxx_requires_heap(_First,_Last)
 # define __glibcxx_requires_heap_pred(_First,_Last,_Pred)
 # define __glibcxx_requires_nonempty()
@@ -123,10 +125,14 @@ namespace std
      __glibcxx_check_sorted(_First,_Last)
 # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \
      __glibcxx_check_sorted_pred(_First,_Last,_Pred)
-# define __glibcxx_requires_partitioned(_First,_Last,_Value)	\
-     __glibcxx_check_partitioned(_First,_Last,_Value)
-# define __glibcxx_requires_partitioned_pred(_First,_Last,_Value,_Pred) \
-     __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred)
+# define __glibcxx_requires_partitioned_lower(_First,_Last,_Value)	\
+     __glibcxx_check_partitioned_lower(_First,_Last,_Value)
+# define __glibcxx_requires_partitioned_upper(_First,_Last,_Value)	\
+     __glibcxx_check_partitioned_upper(_First,_Last,_Value)
+# define __glibcxx_requires_partitioned_lower_pred(_First,_Last,_Value,_Pred) \
+     __glibcxx_check_partitioned_lower_pred(_First,_Last,_Value,_Pred)
+# define __glibcxx_requires_partitioned_upper_pred(_First,_Last,_Value,_Pred) \
+     __glibcxx_check_partitioned_upper_pred(_First,_Last,_Value,_Pred)
 # define __glibcxx_requires_heap(_First,_Last) \
      __glibcxx_check_heap(_First,_Last)
 # define __glibcxx_requires_heap_pred(_First,_Last,_Pred) \
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h
index ee7037f..15c2154 100644
--- a/libstdc++-v3/include/debug/functions.h
+++ b/libstdc++-v3/include/debug/functions.h
@@ -266,8 +266,8 @@ namespace __gnu_debug
   // Determine if a sequence is partitioned w.r.t. this element.
   template<typename _ForwardIterator, typename _Tp>
     inline bool
-    __check_partitioned(_ForwardIterator __first, _ForwardIterator __last,
-			const _Tp& __value)
+    __check_partitioned_lower(_ForwardIterator __first,
+			      _ForwardIterator __last, const _Tp& __value)
     {
       while (__first != __last && *__first < __value)
 	++__first;
@@ -276,15 +276,41 @@ namespace __gnu_debug
       return __first == __last;
     }
 
+  template<typename _ForwardIterator, typename _Tp>
+    inline bool
+    __check_partitioned_upper(_ForwardIterator __first,
+			      _ForwardIterator __last, const _Tp& __value)
+    {
+      while (__first != __last && !(__value < *__first))
+	++__first;
+      while (__first != __last && __value < *__first)
+	++__first;
+      return __first == __last;
+    }
+
   // Determine if a sequence is partitioned w.r.t. this element.
   template<typename _ForwardIterator, typename _Tp, typename _Pred>
     inline bool
-    __check_partitioned(_ForwardIterator __first, _ForwardIterator __last,
-			const _Tp& __value, _Pred __pred)
+    __check_partitioned_lower(_ForwardIterator __first,
+			      _ForwardIterator __last, const _Tp& __value,
+			      _Pred __pred)
+    {
+      while (__first != __last && bool(__pred(*__first, __value)))
+	++__first;
+      while (__first != __last && !bool(__pred(*__first, __value)))
+	++__first;
+      return __first == __last;
+    }
+
+  template<typename _ForwardIterator, typename _Tp, typename _Pred>
+    inline bool
+    __check_partitioned_upper(_ForwardIterator __first,
+			      _ForwardIterator __last, const _Tp& __value,
+			      _Pred __pred)
     {
-      while (__first != __last && __pred(*__first, __value))
+      while (__first != __last && !bool(__pred(__value, *__first)))
 	++__first;
-      while (__first != __last && !__pred(*__first, __value))
+      while (__first != __last && bool(__pred(__value, *__first)))
 	++__first;
       return __first == __last;
     }
diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
index ce40919..4f4a0cc 100644
--- a/libstdc++-v3/include/debug/macros.h
+++ b/libstdc++-v3/include/debug/macros.h
@@ -173,20 +173,41 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last, _Pred), \
 
 /** Verify that the iterator range [_First, _Last) is partitioned
     w.r.t. the value _Value. */
-#define __glibcxx_check_partitioned(_First,_Last,_Value)		\
+#define __glibcxx_check_partitioned_lower(_First,_Last,_Value)		\
 __glibcxx_check_valid_range(_First,_Last);				\
-_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned(_First, _Last,   \
+_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned_lower(_First, _Last, \
 							    _Value),	\
 		      _M_message(__gnu_debug::__msg_unpartitioned)      \
 		      ._M_iterator(_First, #_First)			\
 		      ._M_iterator(_Last, #_Last)			\
 		      ._M_string(#_Value))
 
+#define __glibcxx_check_partitioned_upper(_First,_Last,_Value)		\
+__glibcxx_check_valid_range(_First,_Last);				\
+_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned_upper(_First, _Last, \
+							    _Value),	\
+		      _M_message(__gnu_debug::__msg_unpartitioned)      \
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last)			\
+		      ._M_string(#_Value))
+
+/** Verify that the iterator range [_First, _Last) is partitioned
+    w.r.t. the value _Value and predicate _Pred. */
+#define __glibcxx_check_partitioned_lower_pred(_First,_Last,_Value,_Pred) \
+__glibcxx_check_valid_range(_First,_Last);				\
+_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned_lower(_First, _Last, \
+							 _Value, _Pred), \
+		      _M_message(__gnu_debug::__msg_unpartitioned_pred) \
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last)			\
+		      ._M_string(#_Pred)				\
+                      ._M_string(#_Value))
+
 /** Verify that the iterator range [_First, _Last) is partitioned
     w.r.t. the value _Value and predicate _Pred. */
-#define __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred)	\
+#define __glibcxx_check_partitioned_upper_pred(_First,_Last,_Value,_Pred) \
 __glibcxx_check_valid_range(_First,_Last);				\
-_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned(_First, _Last,   \
+_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned_upper(_First, _Last, \
 							 _Value, _Pred), \
 		      _M_message(__gnu_debug::__msg_unpartitioned_pred) \
 		      ._M_iterator(_First, #_First)			\
diff --git a/libstdc++-v3/testsuite/25_algorithms/lower_bound/33613.cc b/libstdc++-v3/testsuite/25_algorithms/lower_bound/33613.cc
new file mode 100644
index 0000000..189464c
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lower_bound/33613.cc
@@ -0,0 +1,36 @@
+// 2007-10-02  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2007 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.
+
+// { dg-options "-D_GLIBCXX_DEBUG" }
+// { dg-do compile }
+
+// libstdc++/33613
+
+#include <algorithm>
+
+struct A { };
+struct B { };
+
+bool ab(A, B);
+
+void test01(A* a, B b)
+{
+  std::lower_bound(a, a, b, ab);
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/upper_bound/33613.cc b/libstdc++-v3/testsuite/25_algorithms/upper_bound/33613.cc
new file mode 100644
index 0000000..a178428
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/upper_bound/33613.cc
@@ -0,0 +1,36 @@
+// 2007-10-02  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2007 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.
+
+// { dg-options "-D_GLIBCXX_DEBUG" }
+// { dg-do compile }
+
+// libstdc++/33613
+
+#include <algorithm>
+
+struct A { };
+struct B { };
+
+bool ba(B, A);
+
+void test01(A* a, B b)
+{
+  std::upper_bound(a, a, b, ba);
+}