diff options
author | François Dumont <fdumont@gcc.gnu.org> | 2012-05-11 19:21:31 +0000 |
---|---|---|
committer | François Dumont <fdumont@gcc.gnu.org> | 2012-05-11 19:21:31 +0000 |
commit | 0545ebf2dc7578cbc23eaf2546794548d02bca62 (patch) | |
tree | c3a1f6beee1db89e2e98320de952fc89e37b7a6c /libstdc++-v3 | |
parent | 06118b14d6a75fc6d6c949ef66c6696430d7724d (diff) | |
download | gcc-0545ebf2dc7578cbc23eaf2546794548d02bca62.zip gcc-0545ebf2dc7578cbc23eaf2546794548d02bca62.tar.gz gcc-0545ebf2dc7578cbc23eaf2546794548d02bca62.tar.bz2 |
re PR libstdc++/53263 (priority_queue is very slow if -D_GLIBCXX_DEBUG is used)
2012-05-11 François Dumont <fdumont@gcc.gnu.org>
PR libstdc++/53263
* include/debug/safe_iterator.h (__gnu_debug::__base): Move...
* include/debug/functions.h: ... Here. Add debug function
overloads to perform checks on normal iterators when possible.
* include/debug/macros.h (__glibcxx_check_heap)
(__glibcxx_check_heap_pred): Use __gnu_debug::__base on iterator range.
From-SVN: r187414
Diffstat (limited to 'libstdc++-v3')
-rw-r--r-- | libstdc++-v3/ChangeLog | 9 | ||||
-rw-r--r-- | libstdc++-v3/include/debug/functions.h | 179 | ||||
-rw-r--r-- | libstdc++-v3/include/debug/macros.h | 7 | ||||
-rw-r--r-- | libstdc++-v3/include/debug/safe_iterator.h | 32 |
4 files changed, 168 insertions, 59 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index ea30cc9..f1dab1a 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,12 @@ +2012-05-11 François Dumont <fdumont@gcc.gnu.org> + + PR libstdc++/53263 + * include/debug/safe_iterator.h (__gnu_debug::__base): Move... + * include/debug/functions.h: ... Here. Add debug function + overloads to perform checks on normal iterators when possible. + * include/debug/macros.h (__glibcxx_check_heap) + (__glibcxx_check_heap_pred): Use __gnu_debug::__base on iterator range. + 2012-05-10 DJ Delorie <dj@redhat.com> * include/bits/random.tcc (seed_seq::generate): Cast max() diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h index ea12589..b2817d5 100644 --- a/libstdc++-v3/include/debug/functions.h +++ b/libstdc++-v3/include/debug/functions.h @@ -31,7 +31,8 @@ #define _GLIBCXX_DEBUG_FUNCTIONS_H 1 #include <bits/c++config.h> -#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories +#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and + // _Iter_base #include <bits/cpp_type_traits.h> // for __is_integer #include <debug/formatter.h> @@ -118,11 +119,8 @@ namespace __gnu_debug inline bool __valid_range_aux(const _InputIterator& __first, const _InputIterator& __last, std::__false_type) - { - typedef typename std::iterator_traits<_InputIterator>::iterator_category - _Category; - return __valid_range_aux2(__first, __last, _Category()); - } + { return __valid_range_aux2(__first, __last, + std::__iterator_category(__first)); } /** Don't know what these iterators are, or if they are even * iterators (we may get an integral type for InputIterator), so @@ -214,6 +212,15 @@ namespace __gnu_debug return true; } + // For performance reason, as the iterator range has been validated, check on + // random access safe iterators is done using the base iterator. + template<typename _Iterator, typename _Sequence> + inline bool + __check_sorted_aux(const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last, + std::random_access_iterator_tag __tag) + { return __check_sorted_aux(__first.base(), __last.base(), __tag); } + // Can't check if an input iterator sequence is sorted, because we can't step // through the sequence. template<typename _InputIterator, typename _Predicate> @@ -240,19 +247,28 @@ namespace __gnu_debug return true; } + // For performance reason, as the iterator range has been validated, check on + // random access safe iterators is done using the base iterator. + template<typename _Iterator, typename _Sequence, + typename _Predicate> + inline bool + __check_sorted_aux(const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last, + _Predicate __pred, + std::random_access_iterator_tag __tag) + { return __check_sorted_aux(__first.base(), __last.base(), __pred, __tag); } + // Determine if a sequence is sorted. template<typename _InputIterator> inline bool __check_sorted(const _InputIterator& __first, const _InputIterator& __last) { - 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_assert(__first == __last || !(*__first < *__first)); - return __check_sorted_aux(__first, __last, _Category()); + return __check_sorted_aux(__first, __last, + std::__iterator_category(__first)); } template<typename _InputIterator, typename _Predicate> @@ -260,14 +276,12 @@ namespace __gnu_debug __check_sorted(const _InputIterator& __first, const _InputIterator& __last, _Predicate __pred) { - typedef typename std::iterator_traits<_InputIterator>::iterator_category - _Category; - // Verify that the predicate is StrictWeakOrdering by checking that it // is irreflexive. __glibcxx_assert(__first == __last || !__pred(*__first, *__first)); - return __check_sorted_aux(__first, __last, __pred, _Category()); + return __check_sorted_aux(__first, __last, __pred, + std::__iterator_category(__first)); } template<typename _InputIterator> @@ -332,13 +346,11 @@ namespace __gnu_debug 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. template<typename _ForwardIterator, typename _Tp> inline bool - __check_partitioned_lower(_ForwardIterator __first, - _ForwardIterator __last, const _Tp& __value) + __check_partitioned_lower_aux(_ForwardIterator __first, + _ForwardIterator __last, const _Tp& __value, + std::forward_iterator_tag) { while (__first != __last && *__first < __value) ++__first; @@ -347,10 +359,33 @@ namespace __gnu_debug return __first == __last; } + // For performance reason, as the iterator range has been validated, check on + // random access safe iterators is done using the base iterator. + template<typename _Iterator, typename _Sequence, typename _Tp> + inline bool + __check_partitioned_lower_aux( + const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last, + const _Tp& __value, + std::random_access_iterator_tag __tag) + { return __check_partitioned_lower_aux(__first.base(), __last.base(), + __value, __tag); } + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 270. Binary search requirements overly strict + // Determine if a sequence is partitioned w.r.t. this element. template<typename _ForwardIterator, typename _Tp> inline bool - __check_partitioned_upper(_ForwardIterator __first, + __check_partitioned_lower(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) + { return __check_partitioned_lower_aux(__first, __last, __value, + std::__iterator_category(__first)); } + + template<typename _ForwardIterator, typename _Tp> + inline bool + __check_partitioned_upper_aux(_ForwardIterator __first, + _ForwardIterator __last, const _Tp& __value, + std::forward_iterator_tag) { while (__first != __last && !(__value < *__first)) ++__first; @@ -359,12 +394,31 @@ namespace __gnu_debug return __first == __last; } - // Determine if a sequence is partitioned w.r.t. this element. + // For performance reason, as the iterator range has been validated, check on + // random access safe iterators is done using the base iterator. + template<typename _Iterator, typename _Sequence, typename _Tp> + inline bool + __check_partitioned_upper_aux( + const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last, + const _Tp& __value, + std::random_access_iterator_tag __tag) + { return __check_partitioned_upper_aux(__first.base(), __last.base(), + __value, __tag); } + + template<typename _ForwardIterator, typename _Tp> + inline bool + __check_partitioned_upper(_ForwardIterator __first, + _ForwardIterator __last, const _Tp& __value) + { return __check_partitioned_upper_aux(__first, __last, __value, + std::__iterator_category(__first)); } + template<typename _ForwardIterator, typename _Tp, typename _Pred> inline bool - __check_partitioned_lower(_ForwardIterator __first, - _ForwardIterator __last, const _Tp& __value, - _Pred __pred) + __check_partitioned_lower_aux(_ForwardIterator __first, + _ForwardIterator __last, const _Tp& __value, + _Pred __pred, + std::forward_iterator_tag) { while (__first != __last && bool(__pred(*__first, __value))) ++__first; @@ -373,11 +427,34 @@ namespace __gnu_debug return __first == __last; } + // For performance reason, as the iterator range has been validated, check on + // random access safe iterators is done using the base iterator. + template<typename _Iterator, typename _Sequence, + typename _Tp, typename _Pred> + inline bool + __check_partitioned_lower_aux( + const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last, + const _Tp& __value, _Pred __pred, + std::random_access_iterator_tag __tag) + { return __check_partitioned_lower_aux(__first.base(), __last.base(), + __value, __pred, __tag); } + + // Determine if a sequence is partitioned w.r.t. this element. template<typename _ForwardIterator, typename _Tp, typename _Pred> inline bool - __check_partitioned_upper(_ForwardIterator __first, + __check_partitioned_lower(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Pred __pred) + { return __check_partitioned_lower_aux(__first, __last, __value, __pred, + std::__iterator_category(__first)); } + + template<typename _ForwardIterator, typename _Tp, typename _Pred> + inline bool + __check_partitioned_upper_aux(_ForwardIterator __first, + _ForwardIterator __last, const _Tp& __value, + _Pred __pred, + std::forward_iterator_tag) { while (__first != __last && !bool(__pred(__value, *__first))) ++__first; @@ -385,6 +462,58 @@ namespace __gnu_debug ++__first; return __first == __last; } + + // For performance reason, as the iterator range has been validated, check on + // random access safe iterators is done using the base iterator. + template<typename _Iterator, typename _Sequence, + typename _Tp, typename _Pred> + inline bool + __check_partitioned_upper_aux( + const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last, + const _Tp& __value, _Pred __pred, + std::random_access_iterator_tag __tag) + { return __check_partitioned_upper_aux(__first.base(), __last.base(), + __value, __pred, __tag); } + + template<typename _ForwardIterator, typename _Tp, typename _Pred> + inline bool + __check_partitioned_upper(_ForwardIterator __first, + _ForwardIterator __last, const _Tp& __value, + _Pred __pred) + { return __check_partitioned_upper_aux(__first, __last, __value, __pred, + std::__iterator_category(__first)); } + + // Helper struct to detect random access safe iterators. + template<typename _Iterator> + struct __is_safe_random_iterator + { + enum { __value = 0 }; + typedef std::__false_type __type; + }; + + template<typename _Iterator, typename _Sequence> + struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > + : std::__are_same<std::random_access_iterator_tag, + typename std::iterator_traits<_Iterator>:: + iterator_category> + { }; + + template<typename _Iterator> + struct _Siter_base + : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value> + { }; + + /** Helper function to extract base iterator of random access safe iterator + in order to reduce performance impact of debug mode. Limited to random + access iterator because it is the only category for which it is possible + to check for correct iterators order in the __valid_range function + thanks to the < operator. + */ + template<typename _Iterator> + inline typename _Siter_base<_Iterator>::iterator_type + __base(_Iterator __it) + { return _Siter_base<_Iterator>::_S_base(__it); } } // namespace __gnu_debug #endif diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h index aac5634..1b78719 100644 --- a/libstdc++-v3/include/debug/macros.h +++ b/libstdc++-v3/include/debug/macros.h @@ -296,7 +296,8 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned_upper(_First, _Last, \ // Verify that the iterator range [_First, _Last) is a heap #define __glibcxx_check_heap(_First,_Last) \ -_GLIBCXX_DEBUG_VERIFY(std::__is_heap(_First, _Last), \ + _GLIBCXX_DEBUG_VERIFY(std::__is_heap(__gnu_debug::__base(_First), \ + __gnu_debug::__base(_Last)), \ _M_message(__gnu_debug::__msg_not_heap) \ ._M_iterator(_First, #_First) \ ._M_iterator(_Last, #_Last)) @@ -304,7 +305,9 @@ _GLIBCXX_DEBUG_VERIFY(std::__is_heap(_First, _Last), \ /** Verify that the iterator range [_First, _Last) is a heap w.r.t. the predicate _Pred. */ #define __glibcxx_check_heap_pred(_First,_Last,_Pred) \ -_GLIBCXX_DEBUG_VERIFY(std::__is_heap(_First, _Last, _Pred), \ + _GLIBCXX_DEBUG_VERIFY(std::__is_heap(__gnu_debug::__base(_First), \ + __gnu_debug::__base(_Last), \ + _Pred), \ _M_message(__gnu_debug::__msg_not_heap_pred) \ ._M_iterator(_First, #_First) \ ._M_iterator(_Last, #_Last) \ diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index 3cab2d7..68f55cd 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -35,7 +35,6 @@ #include <debug/functions.h> #include <debug/safe_base.h> #include <bits/stl_pair.h> -#include <bits/stl_iterator_base_types.h> // for _Iter_base #include <ext/type_traits.h> namespace __gnu_debug @@ -714,37 +713,6 @@ namespace __gnu_debug operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n, const _Safe_iterator<_Iterator, _Sequence>& __i) { return __i + __n; } - - // Helper struct to detect random access safe iterators. - template<typename _Iterator> - struct __is_safe_random_iterator - { - enum { __value = 0 }; - typedef std::__false_type __type; - }; - - template<typename _Iterator, typename _Sequence> - struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > - : std::__are_same<std::random_access_iterator_tag, - typename std::iterator_traits<_Iterator>:: - iterator_category> - { }; - - template<typename _Iterator> - struct _Siter_base - : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value> - { }; - - /** Helper function to extract base iterator of random access safe iterator - in order to reduce performance impact of debug mode. Limited to random - access iterator because it is the only category for which it is possible - to check for correct iterators order in the __valid_range function - thanks to the < operator. - */ - template<typename _Iterator> - inline typename _Siter_base<_Iterator>::iterator_type - __base(_Iterator __it) - { return _Siter_base<_Iterator>::_S_base(__it); } } // namespace __gnu_debug #include <debug/safe_iterator.tcc> |