From eb2566438402f6fe46748565e91681f84f08d272 Mon Sep 17 00:00:00 2001 From: paolo Date: Sun, 13 Jan 2008 01:34:58 +0000 Subject: [PATCH] 2008-01-12 Paolo Carlini PR libstdc++/34730 * include/debug/functions.h (__check_sorted_set, __check_sorted_set_aux): Add. (__check_sorted): Check StrictWeakOrdering. * include/debug/macros.h (__glibcxx_check_strict_weak_ordering, __glibcxx_check_strict_weak_ordering_pred): Remove. (__glibcxx_check_sorted, __glibcxx_check_sorted_pred): Adjust. (__glibcxx_check_sorted_set, __glibcxx_check_sorted_set_pred): Add. * include/debug/debug.h (__glibcxx_requires_sorted_set, __glibcxx_requires_sorted_set_pred): Add. * include/bits/stl_algo.h (merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference): Adjust, use __glibcxx_requires_sorted_set* instead. * testsuite/25_algorithms/set_intersection/34730.cc: New. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@131500 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 17 +++++ libstdc++-v3/include/bits/stl_algo.h | 58 ++++++++------- libstdc++-v3/include/debug/debug.h | 8 +- libstdc++-v3/include/debug/functions.h | 87 ++++++++++++++++++++-- libstdc++-v3/include/debug/macros.h | 34 +++++---- .../25_algorithms/set_intersection/34730.cc | 51 +++++++++++++ 6 files changed, 205 insertions(+), 50 deletions(-) create mode 100644 libstdc++-v3/testsuite/25_algorithms/set_intersection/34730.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 30d58857f83..a2b07544335 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,20 @@ +2008-01-12 Paolo Carlini + + PR libstdc++/34730 + * include/debug/functions.h (__check_sorted_set, + __check_sorted_set_aux): Add. + (__check_sorted): Check StrictWeakOrdering. + * include/debug/macros.h (__glibcxx_check_strict_weak_ordering, + __glibcxx_check_strict_weak_ordering_pred): Remove. + (__glibcxx_check_sorted, __glibcxx_check_sorted_pred): Adjust. + (__glibcxx_check_sorted_set, __glibcxx_check_sorted_set_pred): Add. + * include/debug/debug.h (__glibcxx_requires_sorted_set, + __glibcxx_requires_sorted_set_pred): Add. + * include/bits/stl_algo.h (merge, includes, set_union, + set_intersection, set_difference, set_symmetric_difference): + Adjust, use __glibcxx_requires_sorted_set* instead. + * testsuite/25_algorithms/set_intersection/34730.cc: New. + 2008-01-09 Paolo Carlini * include/parallel/multiway_merge.h: Reformat to 80 columns; diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index b81a4a354cb..4c65e1154c1 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -3034,15 +3034,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std) while (__last - __first >= __two_step) { __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size, - __first + __step_size, __first + __two_step, - __result); + __first + __step_size, + __first + __two_step, + __result); __first += __two_step; } __step_size = std::min(_Distance(__last - __first), __step_size); _GLIBCXX_STD_P::merge(__first, __first + __step_size, __first + __step_size, __last, - __result); + __result); } template) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) if (*__first2 < *__first1) @@ -3328,7 +3329,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename _Compare> bool includes(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) + _InputIterator2 __first2, _InputIterator2 __last2, + _Compare __comp) { typedef typename iterator_traits<_InputIterator1>::value_type _ValueType1; @@ -3342,8 +3344,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first2, *__first1)) @@ -5029,8 +5031,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) { @@ -5092,8 +5094,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) { @@ -5237,8 +5239,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) { @@ -5305,8 +5307,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) { @@ -5367,8 +5369,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType1>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) @@ -5425,8 +5427,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) @@ -5480,8 +5482,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType1>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) @@ -5542,8 +5544,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) @@ -5599,8 +5601,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) @@ -5667,8 +5669,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h index 32f96a37bed..97d6824ef0c 100644 --- a/libstdc++-v3/include/debug/debug.h +++ b/libstdc++-v3/include/debug/debug.h @@ -1,6 +1,6 @@ // Debugging support implementation -*- C++ -*- -// Copyright (C) 2003, 2004, 2005, 2006, 2007 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -63,6 +63,8 @@ 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_sorted_set(_First1,_Last1,_First2) +# define __glibcxx_requires_sorted_set_pred(_First1,_Last1,_First2,_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) @@ -119,6 +121,10 @@ 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_sorted_set(_First1,_Last1,_First2) \ + __glibcxx_check_sorted_set(_First1,_Last1,_First2) +# define __glibcxx_requires_sorted_set_pred(_First1,_Last1,_First2,_Pred) \ + __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred) # define __glibcxx_requires_partitioned_lower(_First,_Last,_Value) \ __glibcxx_check_partitioned_lower(_First,_Last,_Value) # define __glibcxx_requires_partitioned_upper(_First,_Last,_Value) \ diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h index 15c21541b28..7e7562a940d 100644 --- a/libstdc++-v3/include/debug/functions.h +++ b/libstdc++-v3/include/debug/functions.h @@ -1,6 +1,6 @@ // Debugging support implementation -*- C++ -*- -// Copyright (C) 2003, 2005, 2006 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -205,10 +205,9 @@ namespace __gnu_debug return true; _ForwardIterator __next = __first; - for (++__next; __next != __last; __first = __next, ++__next) { + for (++__next; __next != __last; __first = __next, ++__next) if (*__next < *__first) return false; - } return true; } @@ -232,10 +231,9 @@ namespace __gnu_debug return true; _ForwardIterator __next = __first; - for (++__next; __next != __last; __first = __next, ++__next) { + for (++__next; __next != __last; __first = __next, ++__next) if (__pred(*__next, *__first)) return false; - } return true; } @@ -247,6 +245,11 @@ namespace __gnu_debug { typedef typename std::iterator_traits<_InputIterator>::iterator_category _Category; + + // Verify that the < operator for elements in the sequence is a + // StrictWeakOrdering by checking that it is irreflexive. + _GLIBCXX_DEBUG_ASSERT(__first == __last || !(*__first < *__first)); + return __check_sorted_aux(__first, __last, _Category()); } @@ -257,10 +260,80 @@ namespace __gnu_debug { typedef typename std::iterator_traits<_InputIterator>::iterator_category _Category; - return __check_sorted_aux(__first, __last, __pred, - _Category()); + + // Verify that the predicate is StrictWeakOrdering by checking that it + // is irreflexive. + _GLIBCXX_DEBUG_ASSERT(__first == __last || !__pred(*__first, *__first)); + + return __check_sorted_aux(__first, __last, __pred, _Category()); + } + + template + inline bool + __check_sorted_set_aux(const _InputIterator1& __first, + const _InputIterator1& __last, + const _InputIterator2&, std::__true_type) + { return __check_sorted(__first, __last); } + + template + inline bool + __check_sorted_set_aux(const _InputIterator1&, + const _InputIterator1&, + const _InputIterator2&, std::__false_type) + { return true; } + + template + inline bool + __check_sorted_set_aux(const _InputIterator1& __first, + const _InputIterator1& __last, + const _InputIterator2&, _Predicate __pred, + std::__true_type) + { return __check_sorted(__first, __last, __pred); } + + template + inline bool + __check_sorted_set_aux(const _InputIterator1&, + const _InputIterator1&, + const _InputIterator2&, _Predicate, + std::__false_type) + { return true; } + + // ... special variant used in std::merge, std::includes, std::set_*. + template + inline bool + __check_sorted_set(const _InputIterator1& __first, + const _InputIterator1& __last, + const _InputIterator2&) + { + typedef typename std::iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename std::iterator_traits<_InputIterator2>::value_type + _ValueType2; + + typedef typename std::__are_same<_ValueType1, _ValueType2>::__type + _SameType; + return __check_sorted_set_aux(__first, __last, _SameType()); } + template + inline bool + __check_sorted_set(const _InputIterator1& __first, + const _InputIterator1& __last, + const _InputIterator2&, _Predicate __pred) + { + typedef typename std::iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename std::iterator_traits<_InputIterator2>::value_type + _ValueType2; + + typedef typename std::__are_same<_ValueType1, _ValueType2>::__type + _SameType; + return __check_sorted_set_aux(__first, __last, __pred, _SameType()); + } + // _GLIBCXX_RESOLVE_LIB_DEFECTS // 270. Binary search requirements overly strict // Determine if a sequence is partitioned w.r.t. this element. diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h index 4f4a0ccc9bd..6b7b2b277a8 100644 --- a/libstdc++-v3/include/debug/macros.h +++ b/libstdc++-v3/include/debug/macros.h @@ -1,6 +1,6 @@ // Debugging support implementation -*- C++ -*- -// Copyright (C) 2003, 2005, 2006 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -140,21 +140,9 @@ _GLIBCXX_DEBUG_VERIFY(! this->empty(), \ _M_message(__gnu_debug::__msg_empty) \ ._M_sequence(*this, "this")) -// Verify that the < operator for elements in the sequence is a -// StrictWeakOrdering by checking that it is irreflexive. -#define __glibcxx_check_strict_weak_ordering(_First,_Last) \ -_GLIBCXX_DEBUG_ASSERT(_First == _Last || !(*_First < *_First)) - -// Verify that the predicate is StrictWeakOrdering by checking that it -// is irreflexive. -#define __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred) \ -_GLIBCXX_DEBUG_ASSERT(_First == _Last || !_Pred(*_First, *_First)) - - // Verify that the iterator range [_First, _Last) is sorted #define __glibcxx_check_sorted(_First,_Last) \ __glibcxx_check_valid_range(_First,_Last); \ -__glibcxx_check_strict_weak_ordering(_First,_Last); \ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last), \ _M_message(__gnu_debug::__msg_unsorted) \ ._M_iterator(_First, #_First) \ @@ -164,13 +152,31 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last), \ predicate _Pred. */ #define __glibcxx_check_sorted_pred(_First,_Last,_Pred) \ __glibcxx_check_valid_range(_First,_Last); \ -__glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred); \ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last, _Pred), \ _M_message(__gnu_debug::__msg_unsorted_pred) \ ._M_iterator(_First, #_First) \ ._M_iterator(_Last, #_Last) \ ._M_string(#_Pred)) +// Special variant for std::merge, std::includes, std::set_* +#define __glibcxx_check_sorted_set(_First1,_Last1,_First2) \ +__glibcxx_check_valid_range(_First1,_Last1); \ +_GLIBCXX_DEBUG_VERIFY( \ + __gnu_debug::__check_sorted_set(_First1, _Last1, _First2), \ + _M_message(__gnu_debug::__msg_unsorted) \ + ._M_iterator(_First1, #_First1) \ + ._M_iterator(_Last1, #_Last1)) + +// Likewise with a _Pred. +#define __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred) \ +__glibcxx_check_valid_range(_First1,_Last1); \ +_GLIBCXX_DEBUG_VERIFY( \ + __gnu_debug::__check_sorted_set(_First1, _Last1, _First2, _Pred), \ + _M_message(__gnu_debug::__msg_unsorted_pred) \ + ._M_iterator(_First1, #_First1) \ + ._M_iterator(_Last1, #_Last1) \ + ._M_string(#_Pred)) + /** Verify that the iterator range [_First, _Last) is partitioned w.r.t. the value _Value. */ #define __glibcxx_check_partitioned_lower(_First,_Last,_Value) \ diff --git a/libstdc++-v3/testsuite/25_algorithms/set_intersection/34730.cc b/libstdc++-v3/testsuite/25_algorithms/set_intersection/34730.cc new file mode 100644 index 00000000000..66aef0f99df --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/set_intersection/34730.cc @@ -0,0 +1,51 @@ +// Copyright (C) 2008 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++/34730 + +#include +#include +#include + +using namespace std; + +typedef pair intstring; + +struct intstrcmp +{ + bool + operator()(const string& x, const intstring& y) const + { return x < y.second; } + + bool + operator()(const intstring& x, const string& y) const + { return x.second < y; } +}; + +void test01() +{ + vector vec1; + vector vec2; + vector vec3; + set_intersection(vec2.begin(), vec2.end(), + vec1.begin(), vec1.end(), + back_inserter(vec3), intstrcmp()); +} -- 2.11.0