diff options
Diffstat (limited to 'libstdc++-v3/include/debug/functions.h')
| -rw-r--r-- | libstdc++-v3/include/debug/functions.h | 276 |
1 files changed, 142 insertions, 134 deletions
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h index 3f16098185c..8e76b7f2ee5 100644 --- a/libstdc++-v3/include/debug/functions.h +++ b/libstdc++-v3/include/debug/functions.h @@ -32,7 +32,12 @@ #include <bits/c++config.h> #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and // _Iter_base -#include <bits/cpp_type_traits.h> // for __is_integer +#include <bits/cpp_type_traits.h> // for __is_integer +#include <bits/move.h> // for __addressof and addressof +#if __cplusplus >= 201103L +# include <bits/stl_function.h> // for less and greater_equal +# include <type_traits> // for is_lvalue_reference and __and_ +#endif #include <debug/formatter.h> namespace __gnu_debug @@ -40,6 +45,10 @@ namespace __gnu_debug template<typename _Iterator, typename _Sequence> class _Safe_iterator; + template<typename _Sequence> + struct _Insert_range_from_self_is_safe + { enum { __value = 0 }; }; + // An arbitrary iterator pointer is not singular. inline bool __check_singular_aux(const void*) { return false; } @@ -118,8 +127,8 @@ namespace __gnu_debug inline bool __valid_range_aux(const _InputIterator& __first, const _InputIterator& __last, std::__false_type) - { return __valid_range_aux2(__first, __last, - std::__iterator_category(__first)); } + { 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 @@ -162,6 +171,125 @@ namespace __gnu_debug return __first; } +#if __cplusplus >= 201103L + // Default implementation. + template<typename _Iterator, typename _Sequence> + inline bool + __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it, + typename _Sequence::const_pointer __begin, + typename _Sequence::const_pointer __other) + { + typedef typename _Sequence::const_pointer _PointerType; + constexpr std::less<_PointerType> __l{}; + + return (__l(__other, __begin) + || __l(std::addressof(*(__it._M_get_sequence()->_M_base().end() + - 1)), __other)); + } + + // Fallback when address type cannot be implicitely casted to sequence + // const_pointer. + template<typename _Iterator, typename _Sequence, + typename _InputIterator> + inline bool + __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, + _InputIterator, ...) + { return true; } + + template<typename _Iterator, typename _Sequence, typename _InputIterator> + inline bool + __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it, + _InputIterator __other, + std::true_type) + { + // Only containers with all elements in contiguous memory can have their + // elements passed through pointers. + // Arithmetics is here just to make sure we are not dereferencing + // past-the-end iterator. + if (__it._M_get_sequence()->_M_base().begin() + != __it._M_get_sequence()->_M_base().end()) + if (std::addressof(*(__it._M_get_sequence()->_M_base().end() - 1)) + - std::addressof(*(__it._M_get_sequence()->_M_base().begin())) + == __it._M_get_sequence()->size() - 1) + return (__foreign_iterator_aux4 + (__it, + std::addressof(*(__it._M_get_sequence()->_M_base().begin())), + std::addressof(*__other))); + return true; + } + + /* Fallback overload for which we can't say, assume it is valid. */ + template<typename _Iterator, typename _Sequence, typename _InputIterator> + inline bool + __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it, + _InputIterator __other, + std::false_type) + { return true; } +#endif + + /** Checks that iterators do not belong to the same sequence. */ + template<typename _Iterator, typename _Sequence, typename _OtherIterator> + inline bool + __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, + const _Safe_iterator<_OtherIterator, _Sequence>& __other, + std::input_iterator_tag) + { return __it._M_get_sequence() != __other._M_get_sequence(); } + +#if __cplusplus >= 201103L + /* This overload detects when passing pointers to the contained elements + rather than using iterators. + */ + template<typename _Iterator, typename _Sequence, typename _InputIterator> + inline bool + __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, + _InputIterator __other, + std::random_access_iterator_tag) + { + typedef typename _Sequence::const_iterator _ItType; + typedef typename std::iterator_traits<_ItType>::reference _Ref; + return __foreign_iterator_aux3(__it, __other, + std::is_lvalue_reference<_Ref>()); + } +#endif + + /* Fallback overload for which we can't say, assume it is valid. */ + template<typename _Iterator, typename _Sequence, typename _InputIterator> + inline bool + __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>&, + _InputIterator, + std::input_iterator_tag) + { return true; } + + template<typename _Iterator, typename _Sequence, + typename _Integral> + inline bool + __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it, + _Integral __other, + std::__true_type) + { return true; } + + template<typename _Iterator, typename _Sequence, + typename _InputIterator> + inline bool + __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it, + _InputIterator __other, + std::__false_type) + { + return (_Insert_range_from_self_is_safe<_Sequence>::__value + || __foreign_iterator_aux2(__it, __other, + std::__iterator_category(__it))); + } + + template<typename _Iterator, typename _Sequence, + typename _InputIterator> + inline bool + __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it, + _InputIterator __other) + { + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + return __foreign_iterator_aux(__it, __other, _Integral()); + } + /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ template<typename _CharT, typename _Integer> inline const _CharT* @@ -211,15 +339,6 @@ 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> @@ -246,17 +365,6 @@ 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 @@ -345,11 +453,13 @@ 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_aux(_ForwardIterator __first, - _ForwardIterator __last, const _Tp& __value, - std::forward_iterator_tag) + __check_partitioned_lower(_ForwardIterator __first, + _ForwardIterator __last, const _Tp& __value) { while (__first != __last && *__first < __value) ++__first; @@ -362,38 +472,11 @@ 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_lower(_ForwardIterator __first, + __check_partitioned_upper(_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; if (__first != __last) @@ -405,35 +488,12 @@ 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_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)); - } - + // Determine if a sequence is partitioned w.r.t. this element. template<typename _ForwardIterator, typename _Tp, typename _Pred> inline bool - __check_partitioned_lower_aux(_ForwardIterator __first, - _ForwardIterator __last, const _Tp& __value, - _Pred __pred, - std::forward_iterator_tag) + __check_partitioned_lower(_ForwardIterator __first, + _ForwardIterator __last, const _Tp& __value, + _Pred __pred) { while (__first != __last && bool(__pred(*__first, __value))) ++__first; @@ -446,39 +506,12 @@ 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_lower(_ForwardIterator __first, + __check_partitioned_upper(_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; if (__first != __last) @@ -490,31 +523,6 @@ 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_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 |