From 24167c42e62564c28c3e1e1159ee78ee6a52a86f Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Mon, 29 Jun 2015 20:17:56 +0000 Subject: [PATCH] stl_iterator_base_types.h (_Iter_base): Limit definition to pre-C++11 mode. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2015-06-29 François Dumont * include/bits/stl_iterator_base_types.h (_Iter_base): Limit definition to pre-C++11 mode. * include/debug/functions.h (__gnu_debug::__valid_range, __gnu_debug::__base): Move... * include/debug/safe_iterator.h (__gnu_debug::_Sequence_traits): New. (__gnu_debug::__get_distance_from_begin): New. (__gnu_debug::__get_distance_to_end): New. (__gnu_debug::_Safe_iterator<>::_M_valid_range): Expose iterator range distance information. Add optional check_dereferenceable parameter, default true. (__gnu_debug::_Distance_precision, __gnu_debug::__get_distance): Move default definition... (__gnu_debug::__get_distance): New overload for _Safe_iterator. (__gnu_debug::__unsafe): Likewise. * include/debug/helper_functions.h: ...here. New. (__gnu_debug::__unsafe): New helper function to remove safe iterator layer. * include/debug/stl_iterator.h: New. Include latter. * include/bits/stl_iterator.h: Include latter in debug mode. * include/debug/stl_iterator.tcc: Adapt. * include/debug/safe_local_iterator.h (__gnu_debug::__get_distance): Add overload for _Safe_local_iterator. (__gnu_debug::__unsafe): Likewise. * include/debug/safe_local_iterator.tcc: Adapt. * include/debug/macros.h (__glibcxx_check_valid_range2): New. (__glibcxx_check_insert_range): Add _Dist parameter. (__glibcxx_check_insert_range_after): Likewise. (__glibcxx_check_string, __glibcxx_check_string_len): Implement using _GLIBCXX_DEBUG_PEDASSERT. * include/debug/deque (deque<>::assign): Remove iterator debug layer when possible. (deque<>::insert): Likewise. * include/debug/forward_list (__glibcxx_check_valid_fl_range): New. (forward_list<>::splice_after): Use latter. (forward_list<>::assign): Remove iterator debug layer when possible. (forward_list<>::insert_after): Likewise. (__gnu_debug::_Sequence_traits<>): Partial specialization. * include/debug/list (list<>::assign): Remove iterator debug layer when possible. (list<>::insert): Likewise. [__gnu_debug::_Sequence_traits<>]: Partial specialization pre C++11 ABI. * include/debug/map.h (map<>::insert): Remove iterator debug layer when possible. * include/debug/multimap.h (multimap<>::insert): Likewise. * include/debug/set.h (set<>::insert): Likewise. * include/debug/multiset.h (multiset<>::insert): Likewise. * include/debug/string (basic_string<>::append, basic_string<>::assign, basic_string<>::insert, basic_string<>::replace): Likewise. * include/debug/unordered_map (unordered_map<>::insert, unordered_multimap<>::insert): Likewise. * include/debug/unordered_set (unordered_set<>::insert, unordered_multiset<>insert): Likewise. * include/debug/vector (vector<>::assign, vector<>::insert): Likewise. * include/Makefile.am: Add new debug headers. * include/Makefile.in: Regenerate. From-SVN: r225143 --- libstdc++-v3/ChangeLog | 60 +++++ libstdc++-v3/include/Makefile.am | 2 + libstdc++-v3/include/Makefile.in | 2 + libstdc++-v3/include/bits/stl_iterator.h | 4 + .../include/bits/stl_iterator_base_types.h | 2 + libstdc++-v3/include/debug/deque | 38 +++- libstdc++-v3/include/debug/forward_list | 55 ++++- libstdc++-v3/include/debug/functions.h | 81 +------ libstdc++-v3/include/debug/helper_functions.h | 210 ++++++++++++++++++ libstdc++-v3/include/debug/list | 60 +++-- libstdc++-v3/include/debug/macros.h | 25 ++- libstdc++-v3/include/debug/map.h | 11 +- libstdc++-v3/include/debug/multimap.h | 11 +- libstdc++-v3/include/debug/multiset.h | 11 +- libstdc++-v3/include/debug/safe_iterator.h | 190 +++++++++++++--- libstdc++-v3/include/debug/safe_iterator.tcc | 50 ++--- .../include/debug/safe_local_iterator.h | 66 +++++- .../include/debug/safe_local_iterator.tcc | 16 +- libstdc++-v3/include/debug/set.h | 11 +- libstdc++-v3/include/debug/stl_iterator.h | 113 ++++++++++ libstdc++-v3/include/debug/string | 49 +++- libstdc++-v3/include/debug/unordered_map | 24 +- libstdc++-v3/include/debug/unordered_set | 24 +- libstdc++-v3/include/debug/vector | 35 ++- 24 files changed, 904 insertions(+), 246 deletions(-) create mode 100644 libstdc++-v3/include/debug/helper_functions.h create mode 100644 libstdc++-v3/include/debug/stl_iterator.h diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 9e76cc4d27e..90a6e9a877c 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,63 @@ +2015-06-29 François Dumont + + * include/bits/stl_iterator_base_types.h (_Iter_base): Limit definition + to pre-C++11 mode. + * include/debug/functions.h + (__gnu_debug::__valid_range, __gnu_debug::__base): Move... + * include/debug/safe_iterator.h + (__gnu_debug::_Sequence_traits): New. + (__gnu_debug::__get_distance_from_begin): New. + (__gnu_debug::__get_distance_to_end): New. + (__gnu_debug::_Safe_iterator<>::_M_valid_range): Expose iterator range + distance information. Add optional check_dereferenceable parameter, + default true. + (__gnu_debug::_Distance_precision, __gnu_debug::__get_distance): Move + default definition... + (__gnu_debug::__get_distance): New overload for _Safe_iterator. + (__gnu_debug::__unsafe): Likewise. + * include/debug/helper_functions.h: ...here. New. + (__gnu_debug::__unsafe): New helper function to remove safe iterator + layer. + * include/debug/stl_iterator.h: New. Include latter. + * include/bits/stl_iterator.h: Include latter in debug mode. + * include/debug/stl_iterator.tcc: Adapt. + * include/debug/safe_local_iterator.h (__gnu_debug::__get_distance): Add + overload for _Safe_local_iterator. + (__gnu_debug::__unsafe): Likewise. + * include/debug/safe_local_iterator.tcc: Adapt. + * include/debug/macros.h (__glibcxx_check_valid_range2): New. + (__glibcxx_check_insert_range): Add _Dist parameter. + (__glibcxx_check_insert_range_after): Likewise. + (__glibcxx_check_string, __glibcxx_check_string_len): Implement using + _GLIBCXX_DEBUG_PEDASSERT. + * include/debug/deque (deque<>::assign): Remove iterator debug layer + when possible. + (deque<>::insert): Likewise. + * include/debug/forward_list (__glibcxx_check_valid_fl_range): New. + (forward_list<>::splice_after): Use latter. + (forward_list<>::assign): Remove iterator debug layer when possible. + (forward_list<>::insert_after): Likewise. + (__gnu_debug::_Sequence_traits<>): Partial specialization. + * include/debug/list (list<>::assign): Remove iterator debug layer when + possible. + (list<>::insert): Likewise. + [__gnu_debug::_Sequence_traits<>]: Partial specialization pre C++11 ABI. + * include/debug/map.h (map<>::insert): Remove iterator debug layer when + possible. + * include/debug/multimap.h (multimap<>::insert): Likewise. + * include/debug/set.h (set<>::insert): Likewise. + * include/debug/multiset.h (multiset<>::insert): Likewise. + * include/debug/string (basic_string<>::append, basic_string<>::assign, + basic_string<>::insert, basic_string<>::replace): Likewise. + * include/debug/unordered_map + (unordered_map<>::insert, unordered_multimap<>::insert): Likewise. + * include/debug/unordered_set + (unordered_set<>::insert, unordered_multiset<>insert): Likewise. + * include/debug/vector + (vector<>::assign, vector<>::insert): Likewise. + * include/Makefile.am: Add new debug headers. + * include/Makefile.in: Regenerate. + 2015-06-26 Jonathan Wakely * doc/xml/manual/intro.xml: Document LWG 2108 status. diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 927418ed8b0..05be8ad1b84 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -766,6 +766,7 @@ debug_headers = \ ${debug_srcdir}/formatter.h \ ${debug_srcdir}/forward_list \ ${debug_srcdir}/functions.h \ + ${debug_srcdir}/helper_functions.h \ ${debug_srcdir}/list \ ${debug_srcdir}/map \ ${debug_srcdir}/macros.h \ @@ -785,6 +786,7 @@ debug_headers = \ ${debug_srcdir}/safe_unordered_container.tcc \ ${debug_srcdir}/set \ ${debug_srcdir}/set.h \ + ${debug_srcdir}/stl_iterator.h \ ${debug_srcdir}/string \ ${debug_srcdir}/unordered_map \ ${debug_srcdir}/unordered_set \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 0674d8ca976..bab83b40018 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -1047,6 +1047,7 @@ debug_headers = \ ${debug_srcdir}/formatter.h \ ${debug_srcdir}/forward_list \ ${debug_srcdir}/functions.h \ + ${debug_srcdir}/helper_functions.h \ ${debug_srcdir}/list \ ${debug_srcdir}/map \ ${debug_srcdir}/macros.h \ @@ -1066,6 +1067,7 @@ debug_headers = \ ${debug_srcdir}/safe_unordered_container.tcc \ ${debug_srcdir}/set \ ${debug_srcdir}/set.h \ + ${debug_srcdir}/stl_iterator.h \ ${debug_srcdir}/string \ ${debug_srcdir}/unordered_map \ ${debug_srcdir}/unordered_set \ diff --git a/libstdc++-v3/include/bits/stl_iterator.h b/libstdc++-v3/include/bits/stl_iterator.h index 58b9aabf2e6..1060433d0bd 100644 --- a/libstdc++-v3/include/bits/stl_iterator.h +++ b/libstdc++-v3/include/bits/stl_iterator.h @@ -1246,4 +1246,8 @@ _GLIBCXX_END_NAMESPACE_VERSION #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) #endif // C++11 +#ifdef _GLIBCXX_DEBUG +# include +#endif + #endif diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h b/libstdc++-v3/include/bits/stl_iterator_base_types.h index 83e6444ab1c..eba9e398be7 100644 --- a/libstdc++-v3/include/bits/stl_iterator_base_types.h +++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h @@ -206,6 +206,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION //@} +#if __cplusplus < 201103L // If _Iterator has a base returns it otherwise _Iterator is returned // untouched template @@ -223,6 +224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION static iterator_type _S_base(_Iterator __it) { return __it.base(); } }; +#endif #if __cplusplus >= 201103L template diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque index fffc5e4ab63..7d15e33606b 100644 --- a/libstdc++-v3/include/debug/deque +++ b/libstdc++-v3/include/debug/deque @@ -169,9 +169,14 @@ namespace __debug void assign(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::assign(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::assign(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::assign(__first, __last); + this->_M_invalidate_all(); } @@ -460,10 +465,16 @@ namespace __debug insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { - __glibcxx_check_insert_range(__position, __first, __last); - _Base_iterator __res = _Base::insert(__position.base(), - __gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_insert_range(__position, __first, __last, __dist); + _Base_iterator __res; + if (__dist.second >= __gnu_debug::__dp_sign) + __res = _Base::insert(__position.base(), + __gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + __res = _Base::insert(__position.base(), __first, __last); + this->_M_invalidate_all(); return iterator(__res, this); } @@ -473,9 +484,16 @@ namespace __debug insert(iterator __position, _InputIterator __first, _InputIterator __last) { - __glibcxx_check_insert_range(__position, __first, __last); - _Base::insert(__position.base(), __gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_insert_range(__position, __first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__position.base(), + __gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__position.base(), __first, __last); + this->_M_invalidate_all(); } #endif diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list index 2b42a3f8d29..df35bc29cf5 100644 --- a/libstdc++-v3/include/debug/forward_list +++ b/libstdc++-v3/include/debug/forward_list @@ -36,6 +36,13 @@ #include #include +// Special validity check for forward_list ranges. +#define __glibcxx_check_valid_fl_range(_First,_Last,_Dist) \ +_GLIBCXX_DEBUG_VERIFY(_First._M_valid_range(_Last, _Dist, false), \ + _M_message(__gnu_debug::__msg_valid_range) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last)) + namespace __gnu_debug { /// Special iterators swap and invalidation for forward_list because of the @@ -269,9 +276,15 @@ namespace __debug void assign(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::assign(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::assign(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::assign(__first, __last); + this->_M_invalidate_all(); } @@ -401,11 +414,19 @@ namespace __debug insert_after(const_iterator __pos, _InputIterator __first, _InputIterator __last) { - __glibcxx_check_insert_range_after(__pos, __first, __last); - return iterator(_Base::insert_after(__pos.base(), - __gnu_debug::__base(__first), - __gnu_debug::__base(__last)), - this); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_insert_range_after(__pos, __first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + return + { + _Base::insert_after(__pos.base(), + __gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)), + this + }; + else + return { _Base::insert_after(__pos.base(), __first, __last), this }; } iterator @@ -580,9 +601,10 @@ namespace __debug splice_after(const_iterator __pos, forward_list&& __list, const_iterator __before, const_iterator __last) { + typename __gnu_debug::_Distance_traits::__type __dist; auto __listptr = std::__addressof(__list); __glibcxx_check_insert_after(__pos); - __glibcxx_check_valid_range(__before, __last); + __glibcxx_check_valid_fl_range(__before, __last, __dist); _GLIBCXX_DEBUG_VERIFY(__before._M_attached_to(__listptr), _M_message(__gnu_debug::__msg_splice_other) ._M_sequence(__list, "list") @@ -801,7 +823,7 @@ namespace __debug namespace __gnu_debug { - template + template struct _BeforeBeginHelper > { typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence; @@ -820,6 +842,19 @@ namespace __gnu_debug { return _S_Is(__it); } }; + template + struct _Sequence_traits > + { + typedef typename std::__debug::forward_list<_Tp, _Alloc>::iterator _It; + + static typename _Distance_traits<_It>::__type + _S_size(const std::__debug::forward_list<_Tp, _Alloc>& __seq) + { + return __seq.empty() + ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality); + } + }; + #ifndef _GLIBCXX_DEBUG_PEDANTIC template struct _Insert_range_from_self_is_safe< diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h index bf60ccc23c6..7f0659f5b25 100644 --- a/libstdc++-v3/include/debug/functions.h +++ b/libstdc++-v3/include/debug/functions.h @@ -29,11 +29,6 @@ #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H #define _GLIBCXX_DEBUG_FUNCTIONS_H 1 -#include -#include // for iterator_traits, - // categories and _Iter_base -#include // for __is_integer - #include // for __addressof #include // for less #if __cplusplus >= 201103L @@ -41,6 +36,7 @@ // conditional. #endif +#include #include namespace __gnu_debug @@ -85,58 +81,6 @@ namespace __gnu_debug __check_dereferenceable(const _Tp* __ptr) { return __ptr; } - /** If the distance between two random access iterators is - * nonnegative, assume the range is valid. - */ - template - inline bool - __valid_range_aux2(const _RandomAccessIterator& __first, - const _RandomAccessIterator& __last, - std::random_access_iterator_tag) - { return __last - __first >= 0; } - - /** Can't test for a valid range with input iterators, because - * iteration may be destructive. So we just assume that the range - * is valid. - */ - template - inline bool - __valid_range_aux2(const _InputIterator&, const _InputIterator&, - std::input_iterator_tag) - { return true; } - - /** We say that integral types for a valid range, and defer to other - * routines to realize what to do with integral types instead of - * iterators. - */ - template - inline bool - __valid_range_aux(const _Integral&, const _Integral&, std::__true_type) - { return true; } - - /** We have iterators, so figure out what kind of iterators that are - * to see if we can check the range ahead of time. - */ - template - inline bool - __valid_range_aux(const _InputIterator& __first, - const _InputIterator& __last, std::__false_type) - { 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 - * see if they are integral and pass them on to the next phase - * otherwise. - */ - template - inline bool - __valid_range(const _InputIterator& __first, const _InputIterator& __last) - { - typedef typename std::__is_integer<_InputIterator>::__type _Integral; - return __valid_range_aux(__first, __last, _Integral()); - } - /* Checks that [first, last) is a valid range, and then returns * __first. This routine is useful when we can't use a separate * assertion statement because, e.g., we are in a constructor. @@ -500,29 +444,6 @@ namespace __gnu_debug return __first == __last; } - // Helper struct to detect random access safe iterators. - template - struct __is_safe_random_iterator - { - enum { __value = 0 }; - typedef std::__false_type __type; - }; - - template - 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 - 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/helper_functions.h b/libstdc++-v3/include/debug/helper_functions.h new file mode 100644 index 00000000000..a2db00d29cc --- /dev/null +++ b/libstdc++-v3/include/debug/helper_functions.h @@ -0,0 +1,210 @@ +// Debugging support implementation -*- C++ -*- + +// Copyright (C) 2003-2015 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file debug/helper_functions.h + * This file is a GNU debug extension to the Standard C++ Library. + */ + +#ifndef _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H +#define _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H 1 + +#include // for iterator_traits, + // categories and _Iter_base +#include // for __is_integer + +#include // for pair + +namespace __gnu_debug +{ + /** The precision to which we can calculate the distance between + * two iterators. + */ + enum _Distance_precision + { + __dp_none, // Not even an iterator type + __dp_equality, //< Can compare iterator equality, only + __dp_sign, //< Can determine equality and ordering + __dp_exact //< Can determine distance precisely + }; + + template::__type> + struct _Distance_traits + { + private: + typedef + typename std::iterator_traits<_Iterator>::difference_type _ItDiffType; + + template::__type> + struct _DiffTraits + { typedef _DiffType __type; }; + + template + struct _DiffTraits<_DiffType, std::__true_type> + { typedef std::ptrdiff_t __type; }; + + typedef typename _DiffTraits<_ItDiffType>::__type _DiffType; + + public: + typedef std::pair<_DiffType, _Distance_precision> __type; + }; + + template + struct _Distance_traits<_Integral, std::__true_type> + { typedef std::pair __type; }; + + /** Determine the distance between two iterators with some known + * precision. + */ + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance(const _Iterator& __lhs, const _Iterator& __rhs, + std::random_access_iterator_tag) + { return std::make_pair(__rhs - __lhs, __dp_exact); } + + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance(const _Iterator& __lhs, const _Iterator& __rhs, + std::input_iterator_tag) + { + if (__lhs == __rhs) + return std::make_pair(0, __dp_exact); + + return std::make_pair(1, __dp_equality); + } + + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance(const _Iterator& __lhs, const _Iterator& __rhs) + { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); } + + /** We say that integral types for a valid range, and defer to other + * routines to realize what to do with integral types instead of + * iterators. + */ + template + inline bool + __valid_range_aux(const _Integral&, const _Integral&, + typename _Distance_traits<_Integral>::__type& __dist, + std::__true_type) + { + __dist = std::make_pair(0, __dp_none); + return true; + } + + /** We have iterators, so figure out what kind of iterators that are + * to see if we can check the range ahead of time. + */ + template + inline bool + __valid_range_aux(const _InputIterator& __first, + const _InputIterator& __last, + typename _Distance_traits<_InputIterator>::__type& __dist, + std::__false_type) + { + __dist = __get_distance(__first, __last); + switch (__dist.second) + { + case __dp_none: + break; + case __dp_equality: + if (__dist.first == 0) + return true; + break; + case __dp_sign: + case __dp_exact: + return __dist.first >= 0; + } + + return true; + } + + /** Don't know what these iterators are, or if they are even + * iterators (we may get an integral type for InputIterator), so + * see if they are integral and pass them on to the next phase + * otherwise. + */ + template + inline bool + __valid_range(const _InputIterator& __first, const _InputIterator& __last, + typename _Distance_traits<_InputIterator>::__type& __dist) + { + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + return __valid_range_aux(__first, __last, __dist, _Integral()); + } + + template + inline bool + __valid_range(const _InputIterator& __first, const _InputIterator& __last) + { + typename _Distance_traits<_InputIterator>::__type __dist; + return __valid_range(__first, __last, __dist); + } + +#if __cplusplus < 201103L + // Helper struct to detect random access safe iterators. + template + struct __is_safe_random_iterator + { + enum { __value = 0 }; + typedef std::__false_type __type; + }; + + template + 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 + inline typename _Siter_base<_Iterator>::iterator_type + __base(_Iterator __it) + { return _Siter_base<_Iterator>::_S_base(__it); } +#else + template + inline _Iterator + __base(_Iterator __it) + { return __it; } +#endif + +#if __cplusplus < 201103L + template + struct _Unsafe_type + { typedef _Iterator _Type; }; +#endif + + /* Remove debug mode safe iterator layer, if any. */ + template + inline _Iterator + __unsafe(_Iterator __it) + { return __it; } +} + +#endif diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list index 12ac53c4675..0f3f1a0e241 100644 --- a/libstdc++-v3/include/debug/list +++ b/libstdc++-v3/include/debug/list @@ -177,9 +177,15 @@ namespace __debug void assign(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::assign(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::assign(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::assign(__first, __last); + this->_M_invalidate_all(); } @@ -441,11 +447,18 @@ namespace __debug insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { - __glibcxx_check_insert_range(__position, __first, __last); - return iterator(_Base::insert(__position.base(), - __gnu_debug::__base(__first), - __gnu_debug::__base(__last)), - this); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_insert_range(__position, __first, __last, __dist); + if (__dist.second >= __gnu_debug::__dp_sign) + return + { + _Base::insert(__position.base(), + __gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)), + this + }; + else + return { _Base::insert(__position.base(), __first, __last), this }; } #else template @@ -453,9 +466,14 @@ namespace __debug insert(iterator __position, _InputIterator __first, _InputIterator __last) { - __glibcxx_check_insert_range(__position, __first, __last); - _Base::insert(__position.base(), __gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_insert_range(__position, __first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__position.base(), __gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__position.base(), __first, __last); } #endif @@ -795,13 +813,29 @@ namespace __debug } // namespace __debug } // namespace std -#ifndef _GLIBCXX_DEBUG_PEDANTIC namespace __gnu_debug { +#ifndef _GLIBCXX_USE_CXX11_ABI + // If not using C++11 list::size() is not in O(1) so we do not use it. + template + struct _Sequence_traits > + { + typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It; + + static typename _Distance_traits<_It>::__type + _S_size(const std::__debug::list<_Tp, _Alloc>& __seq) + { + return __seq.empty() + ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality); + } + }; +#endif + +#ifndef _GLIBCXX_DEBUG_PEDANTIC template struct _Insert_range_from_self_is_safe > { enum { __value = 1 }; }; -} #endif +} #endif diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h index f796e718770..a4c2649c843 100644 --- a/libstdc++-v3/include/debug/macros.h +++ b/libstdc++-v3/include/debug/macros.h @@ -56,6 +56,12 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__valid_range(_First, _Last), \ ._M_iterator(_First, #_First) \ ._M_iterator(_Last, #_Last)) +#define __glibcxx_check_valid_range2(_First,_Last,_Dist) \ +_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__valid_range(_First, _Last, _Dist), \ + _M_message(__gnu_debug::__msg_valid_range) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last)) + // Verify that [_First, _Last) forms a non-empty iterator range. #define __glibcxx_check_non_empty_range(_First,_Last) \ _GLIBCXX_DEBUG_VERIFY(_First != _Last, \ @@ -104,8 +110,8 @@ _GLIBCXX_DEBUG_VERIFY(!_Position._M_is_end(), \ * Note that this macro is only valid when the container is a * _Safe_sequence and the _Position iterator is a _Safe_iterator. */ -#define __glibcxx_check_insert_range(_Position,_First,_Last) \ -__glibcxx_check_valid_range(_First,_Last); \ +#define __glibcxx_check_insert_range(_Position,_First,_Last,_Dist) \ +__glibcxx_check_valid_range2(_First,_Last,_Dist); \ __glibcxx_check_insert(_Position); \ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First,_Last),\ _M_message(__gnu_debug::__msg_insert_range_from_self)\ @@ -123,8 +129,8 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First,_Last),\ * Note that this macro is only valid when the container is a * _Safe_sequence and the _Position iterator is a _Safe_iterator. */ -#define __glibcxx_check_insert_range_after(_Position,_First,_Last) \ -__glibcxx_check_valid_range(_First,_Last); \ +#define __glibcxx_check_insert_range_after(_Position,_First,_Last,_Dist)\ + __glibcxx_check_valid_range2(_First,_Last,_Dist); \ __glibcxx_check_insert_after(_Position); \ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First,_Last),\ _M_message(__gnu_debug::__msg_insert_range_from_self)\ @@ -352,13 +358,8 @@ _GLIBCXX_DEBUG_VERIFY(_This.get_allocator() == _Other.get_allocator(), \ _M_message(__gnu_debug::__msg_equal_allocs) \ ._M_sequence(_This, "this")) -#ifdef _GLIBCXX_DEBUG_PEDANTIC -# define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_ASSERT(_String != 0) -# define __glibcxx_check_string_len(_String,_Len) \ - _GLIBCXX_DEBUG_ASSERT(_String != 0 || _Len == 0) -#else -# define __glibcxx_check_string(_String) -# define __glibcxx_check_string_len(_String,_Len) -#endif +#define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_PEDASSERT(_String != 0) +#define __glibcxx_check_string_len(_String,_Len) \ + _GLIBCXX_DEBUG_PEDASSERT(_String != 0 || _Len == 0) #endif diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h index 688fb99d499..9bda8eba1da 100644 --- a/libstdc++-v3/include/debug/map.h +++ b/libstdc++-v3/include/debug/map.h @@ -307,9 +307,14 @@ namespace __debug void insert(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::insert(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__first, __last); } #if __cplusplus >= 201103L diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h index e2c806131f0..b9b0a74c94e 100644 --- a/libstdc++-v3/include/debug/multimap.h +++ b/libstdc++-v3/include/debug/multimap.h @@ -286,9 +286,14 @@ namespace __debug void insert(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::insert(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__first, __last); } #if __cplusplus >= 201103L diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h index b4d738f4bec..f1f6e2c576a 100644 --- a/libstdc++-v3/include/debug/multiset.h +++ b/libstdc++-v3/include/debug/multiset.h @@ -271,9 +271,14 @@ namespace __debug void insert(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::insert(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__first, __last); } #if __cplusplus >= 201103L diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index 9f2dcd1e238..a8bee214e36 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -41,7 +41,7 @@ namespace __gnu_debug /** Helper struct to deal with sequence offering a before_begin * iterator. **/ - template + template struct _BeforeBeginHelper { template @@ -55,38 +55,16 @@ namespace __gnu_debug { return __it.base() == __it._M_get_sequence()->_M_base().begin(); } }; - /** The precision to which we can calculate the distance between - * two iterators. - */ - enum _Distance_precision + /** Sequence traits giving the size of a container if possible. */ + template + struct _Sequence_traits { - __dp_equality, //< Can compare iterator equality, only - __dp_sign, //< Can determine equality and ordering - __dp_exact //< Can determine distance precisely - }; - - /** Determine the distance between two iterators with some known - * precision. - */ - template - inline std::pair::difference_type, - _Distance_precision> - __get_distance(const _Iterator& __lhs, const _Iterator& __rhs, - std::random_access_iterator_tag) - { return std::make_pair(__rhs - __lhs, __dp_exact); } + typedef _Distance_traits _DistTraits; - template - inline std::pair::difference_type, - _Distance_precision> - __get_distance(const _Iterator& __lhs, const _Iterator& __rhs, - std::forward_iterator_tag) - { return std::make_pair(__lhs == __rhs? 0 : 1, __dp_equality); } - - template - inline std::pair::difference_type, - _Distance_precision> - __get_distance(const _Iterator& __lhs, const _Iterator& __rhs) - { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); } + static typename _DistTraits::__type + _S_size(const _Sequence& __seq) + { return std::make_pair(__seq.size(), __dp_exact); } + }; /** \brief Safe iterator wrapper. * @@ -476,7 +454,9 @@ namespace __gnu_debug // Is the iterator range [*this, __rhs) valid? bool - _M_valid_range(const _Safe_iterator& __rhs) const; + _M_valid_range(const _Safe_iterator& __rhs, + std::pair& __dist, + bool __check_dereferenceable = true) const; // The sequence this iterator references. typename @@ -768,15 +748,157 @@ namespace __gnu_debug template inline bool __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, - const _Safe_iterator<_Iterator, _Sequence>& __last) - { return __first._M_valid_range(__last); } + const _Safe_iterator<_Iterator, _Sequence>& __last, + typename _Distance_traits<_Iterator>::__type& __dist) + { return __first._M_valid_range(__last, __dist); } + + /** Safe iterators can help to get better distance knowledge. */ + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last, + std::random_access_iterator_tag) + { return std::make_pair(__last.base() - __first.base(), __dp_exact); } + + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last, + std::input_iterator_tag) + { + typedef typename _Distance_traits<_Iterator>::__type _Diff; + typedef _Sequence_traits<_Sequence> _SeqTraits; + + if (__first.base() == __last.base()) + return std::make_pair(0, __dp_exact); + + if (__first._M_is_before_begin()) + { + if (__last._M_is_begin()) + return std::make_pair(1, __dp_exact); + + return std::make_pair(1, __dp_sign); + } + + if (__first._M_is_begin()) + { + if (__last._M_is_before_begin()) + return std::make_pair(-1, __dp_exact); + + if (__last._M_is_end()) + return _SeqTraits::_S_size(*__first._M_get_sequence()); + + return std::make_pair(1, __dp_sign); + } + + if (__first._M_is_end()) + { + if (__last._M_is_before_begin()) + return std::make_pair(-1, __dp_exact); + + if (__last._M_is_begin()) + { + _Diff __diff = _SeqTraits::_S_size(*__first._M_get_sequence()); + return std::make_pair(-__diff.first, __diff.second); + } + + return std::make_pair(-1, __dp_sign); + } + + if (__last._M_is_before_begin() || __last._M_is_begin()) + return std::make_pair(-1, __dp_sign); + + if (__last._M_is_end()) + return std::make_pair(1, __dp_sign); + + return std::make_pair(1, __dp_equality); + } + + // Get distance from sequence begin to specified iterator. + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance_from_begin(const _Safe_iterator<_Iterator, _Sequence>& __it) + { + typedef _Sequence_traits<_Sequence> _SeqTraits; + + // No need to consider before_begin as this function is only used in + // _M_can_advance which won't be used for forward_list iterators. + if (__it._M_is_begin()) + return std::make_pair(0, __dp_exact); + + if (__it._M_is_end()) + return _SeqTraits::_S_size(*__it._M_get_sequence()); + + typename _Distance_traits<_Iterator>::__type __res + = __get_distance(__it._M_get_sequence()->_M_base().begin(), __it.base()); + + if (__res.second == __dp_equality) + return std::make_pair(1, __dp_sign); + + return __res; + } + + // Get distance from specified iterator to sequence end. + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance_to_end(const _Safe_iterator<_Iterator, _Sequence>& __it) + { + typedef _Sequence_traits<_Sequence> _SeqTraits; + + // No need to consider before_begin as this function is only used in + // _M_can_advance which won't be used for forward_list iterators. + if (__it._M_is_begin()) + return _SeqTraits::_S_size(*__it._M_get_sequence()); + + if (__it._M_is_end()) + return std::make_pair(0, __dp_exact); + typename _Distance_traits<_Iterator>::__type __res + = __get_distance(__it.base(), __it._M_get_sequence()->_M_base().end()); + + if (__res.second == __dp_equality) + return std::make_pair(1, __dp_sign); + + return __res; + } + +#if __cplusplus < 201103L template struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > : std::__are_same:: iterator_category> { }; +#else + template + _Iterator + __base(const _Safe_iterator<_Iterator, _Sequence>& __it, + std::random_access_iterator_tag) + { return __it.base(); } + + template + const _Safe_iterator<_Iterator, _Sequence>& + __base(const _Safe_iterator<_Iterator, _Sequence>& __it, + std::input_iterator_tag) + { return __it; } + + template + auto + __base(const _Safe_iterator<_Iterator, _Sequence>& __it) + -> decltype(__base(__it, std::__iterator_category(__it))) + { return __base(__it, std::__iterator_category(__it)); } +#endif + +#if __cplusplus < 201103L + template + struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> > + { typedef _Iterator _Type; }; +#endif + + template + inline _Iterator + __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it) + { return __it.base(); } } // namespace __gnu_debug diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc index 47b6f2f1dd3..1ad26e3e07b 100644 --- a/libstdc++-v3/include/debug/safe_iterator.tcc +++ b/libstdc++-v3/include/debug/safe_iterator.tcc @@ -38,12 +38,14 @@ namespace __gnu_debug { if (this->_M_singular()) return false; + if (__n == 0) return true; + if (__n < 0) { std::pair __dist = - __get_distance(_M_get_sequence()->_M_base().begin(), base()); + __get_distance_from_begin(*this); bool __ok = ((__dist.second == __dp_exact && __dist.first >= -__n) || (__dist.second != __dp_exact && __dist.first > 0)); return __ok; @@ -51,7 +53,7 @@ namespace __gnu_debug else { std::pair __dist = - __get_distance(base(), _M_get_sequence()->_M_base().end()); + __get_distance_to_end(*this); bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n) || (__dist.second != __dp_exact && __dist.first > 0)); return __ok; @@ -61,37 +63,31 @@ namespace __gnu_debug template bool _Safe_iterator<_Iterator, _Sequence>:: - _M_valid_range(const _Safe_iterator& __rhs) const + _M_valid_range(const _Safe_iterator& __rhs, + std::pair& __dist, + bool __check_dereferenceable) const { if (!_M_can_compare(__rhs)) return false; - /* Determine if we can order the iterators without the help of - the container */ - std::pair __dist = - __get_distance(base(), __rhs.base()); - switch (__dist.second) { - case __dp_equality: - if (__dist.first == 0) - return true; - break; - - case __dp_sign: - case __dp_exact: - return __dist.first >= 0; - } + /* Determine iterators order */ + __dist = __get_distance(*this, __rhs); + switch (__dist.second) + { + case __dp_equality: + if (__dist.first == 0) + return true; + break; - /* We can only test for equality, but check if one of the - iterators is at an extreme. */ - /* Optim for classic [begin, it) or [it, end) ranges, limit checks - * when code is valid. Note, for the special case of forward_list, - * before_begin replaces the role of begin. */ - if (_M_is_beginnest() || __rhs._M_is_end()) - return true; - if (_M_is_end() || __rhs._M_is_beginnest()) - return false; + case __dp_sign: + case __dp_exact: + // If range is not empty first iterator must be dereferenceable. + if (__dist.first > 0) + return !__check_dereferenceable || _M_dereferenceable(); + return __dist.first == 0; + } - // Assume that this is a valid range; we can't check anything else + // Assume that this is a valid range; we can't check anything else. return true; } } // namespace __gnu_debug diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h index dcbe4400cac..350a1d249ed 100644 --- a/libstdc++-v3/include/debug/safe_local_iterator.h +++ b/libstdc++-v3/include/debug/safe_local_iterator.h @@ -322,7 +322,9 @@ namespace __gnu_debug // Is the iterator range [*this, __rhs) valid? bool - _M_valid_range(const _Safe_local_iterator& __rhs) const; + _M_valid_range(const _Safe_local_iterator& __rhs, + std::pair& __dist_info) const; // The sequence this iterator references. typename @@ -440,8 +442,66 @@ namespace __gnu_debug template inline bool __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, - const _Safe_local_iterator<_Iterator, _Sequence>& __last) - { return __first._M_valid_range(__last); } + const _Safe_local_iterator<_Iterator, _Sequence>& __last, + typename _Distance_traits<_Iterator>::__type& __dist_info) + { return __first._M_valid_range(__last, __dist_info); } + + /** Safe local iterators need a special method to get distance between each + other. */ + template + inline std::pair::difference_type, + _Distance_precision> + __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first, + const _Safe_local_iterator<_Iterator, _Sequence>& __last, + std::input_iterator_tag) + { + if (__first.base() == __last.base()) + return { 0, __dp_exact }; + + if (__first._M_is_begin()) + { + if (__last._M_is_end()) + return + { + __first._M_get_sequence()->bucket_size(__first.bucket()), + __dp_exact + }; + + return { 1, __dp_sign }; + } + + if (__first._M_is_end()) + { + if (__last._M_is_begin()) + return + { + -__first._M_get_sequence()->bucket_size(__first.bucket()), + __dp_exact + }; + + return { -1, __dp_sign }; + } + + if (__last._M_is_begin()) + return { -1, __dp_sign }; + + if (__last._M_is_end()) + return { 1, __dp_sign }; + + return { 1, __dp_equality }; + } + +#if __cplusplus < 201103L + template + struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> > + { typedef _Iterator _Type; }; +#endif + + template + inline _Iterator + __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it) + { return __it.base(); } + } // namespace __gnu_debug #include diff --git a/libstdc++-v3/include/debug/safe_local_iterator.tcc b/libstdc++-v3/include/debug/safe_local_iterator.tcc index 455e4cd5dd7..f846bf78307 100644 --- a/libstdc++-v3/include/debug/safe_local_iterator.tcc +++ b/libstdc++-v3/include/debug/safe_local_iterator.tcc @@ -34,17 +34,18 @@ namespace __gnu_debug template bool _Safe_local_iterator<_Iterator, _Sequence>:: - _M_valid_range(const _Safe_local_iterator& __rhs) const + _M_valid_range(const _Safe_local_iterator& __rhs, + std::pair& __dist) const { if (!_M_can_compare(__rhs)) return false; + if (bucket() != __rhs.bucket()) return false; /* Determine if we can order the iterators without the help of the container */ - std::pair __dist = - __get_distance(base(), __rhs.base()); + __dist = __get_distance(*this, __rhs); switch (__dist.second) { case __dp_equality: @@ -57,15 +58,6 @@ namespace __gnu_debug return __dist.first >= 0; } - /* We can only test for equality, but check if one of the - iterators is at an extreme. */ - /* Optim for classic [begin, it) or [it, end) ranges, limit checks - * when code is valid. */ - if (_M_is_begin() || __rhs._M_is_end()) - return true; - if (_M_is_end() || __rhs._M_is_begin()) - return false; - // Assume that this is a valid range; we can't check anything else return true; } diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h index c13ee811aaa..1ca6dda9c0e 100644 --- a/libstdc++-v3/include/debug/set.h +++ b/libstdc++-v3/include/debug/set.h @@ -280,9 +280,14 @@ namespace __debug void insert(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::insert(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__first, __last); } #if __cplusplus >= 201103L diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h new file mode 100644 index 00000000000..d1e57ea75a0 --- /dev/null +++ b/libstdc++-v3/include/debug/stl_iterator.h @@ -0,0 +1,113 @@ +// Debugging support implementation -*- C++ -*- + +// Copyright (C) 2015 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file debug/stl_iterator.h + * This file is a GNU debug extension to the Standard C++ Library. + */ + +#ifndef _GLIBCXX_DEBUG_STL_ITERATOR_H +#define _GLIBCXX_DEBUG_STL_ITERATOR_H 1 + +#include + +namespace __gnu_debug +{ + // Help Debug mode to see through reverse_iterator. + template + inline bool + __valid_range(const std::reverse_iterator<_Iterator>& __first, + const std::reverse_iterator<_Iterator>& __last, + typename _Distance_traits<_Iterator>::__type& __dist) + { return __valid_range(__last.base(), __first.base(), __dist); } + + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance(const std::reverse_iterator<_Iterator>& __first, + const std::reverse_iterator<_Iterator>& __last) + { return __get_distance(__last.base(), __first.base()); } + +#if __cplusplus < 201103L + template + struct __is_safe_random_iterator > + : __is_safe_random_iterator<_Iterator> + { }; + + template + struct _Unsafe_type > + { + typedef typename _Unsafe_type<_Iterator>::_Type _UnsafeType; + typedef std::reverse_iterator<_UnsafeType> _Type; + }; + + template + inline std::reverse_iterator::_Type> + __unsafe(const std::reverse_iterator<_Iterator>& __it) + { + typedef typename _Unsafe_type<_Iterator>::_Type _UnsafeType; + return std::reverse_iterator<_UnsafeType>(__unsafe(__it.base())); + } +#else + template + inline auto + __base(const std::reverse_iterator<_Iterator>& __it) + -> decltype(std::__make_reverse_iterator(__base(__it.base()))) + { return std::__make_reverse_iterator(__base(__it.base())); } + + template + inline auto + __unsafe(const std::reverse_iterator<_Iterator>& __it) + -> decltype(std::__make_reverse_iterator(__unsafe(__it.base()))) + { return std::__make_reverse_iterator(__unsafe(__it.base())); } +#endif + +#if __cplusplus >= 201103L + // Help Debug mode to see through move_iterator. + template + inline bool + __valid_range(const std::move_iterator<_Iterator>& __first, + const std::move_iterator<_Iterator>& __last, + typename _Distance_traits<_Iterator>::__type& __dist) + { return __valid_range(__first.base(), __last.base(), __dist); } + + template + inline typename _Distance_traits<_Iterator>::__type + __get_distance(const std::move_iterator<_Iterator>& __first, + const std::move_iterator<_Iterator>& __last) + { return __get_distance(__first.base(), __last.base()); } + + template + inline auto + __unsafe(const std::move_iterator<_Iterator>& __it) + -> decltype(std::make_move_iterator(__unsafe(__it.base()))) + { return std::make_move_iterator(__unsafe(__it.base())); } + + template + inline auto + __base(const std::move_iterator<_Iterator>& __it) + -> decltype(std::make_move_iterator(__base(__it.base()))) + { return std::make_move_iterator(__base(__it.base())); } +#endif +} + +#endif diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string index f068ef04fe8..72ae88e5495 100644 --- a/libstdc++-v3/include/debug/string +++ b/libstdc++-v3/include/debug/string @@ -380,9 +380,15 @@ namespace __gnu_debug basic_string& append(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::append(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __dp_sign) + _Base::append(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::append(__first, __last); + this->_M_invalidate_all(); return *this; } @@ -452,9 +458,15 @@ namespace __gnu_debug basic_string& assign(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::assign(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __dp_sign) + _Base::assign(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::assign(__first, __last); + this->_M_invalidate_all(); return *this; } @@ -533,9 +545,15 @@ namespace __gnu_debug void insert(iterator __p, _InputIterator __first, _InputIterator __last) { - __glibcxx_check_insert_range(__p, __first, __last); - _Base::insert(__p.base(), __gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_insert_range2(__p, __first, __last, __dist); + + if (__dist.second >= __dp_sign) + _Base::insert(__p.base(), __gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__p.base(), __first, __last); + this->_M_invalidate_all(); } @@ -676,8 +694,17 @@ namespace __gnu_debug _InputIterator __j1, _InputIterator __j2) { __glibcxx_check_erase_range(__i1, __i2); - __glibcxx_check_valid_range(__j1, __j2); - _Base::replace(__i1.base(), __i2.base(), __j1, __j2); + + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__j1, __j2, __dist); + + if (__dist.second >= __dp_sign) + _Base::replace(__i1.base(), __i2.base(), + __gnu_debug::__unsafe(__j1), + __gnu_debug::__unsafe(__j2)); + else + _Base::replace(__i1.base(), __i2.base(), __j1, __j2); + this->_M_invalidate_all(); return *this; } diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index 3f46641d678..41e20d7f203 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -364,10 +364,16 @@ namespace __debug void insert(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); size_type __bucket_count = this->bucket_count(); - _Base::insert(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__first, __last); + _M_check_rehashed(__bucket_count); } @@ -809,10 +815,16 @@ namespace __debug void insert(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); size_type __bucket_count = this->bucket_count(); - _Base::insert(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__first, __last); + _M_check_rehashed(__bucket_count); } diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index 10a9c270ed0..1e6846140ab 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -355,10 +355,16 @@ namespace __debug void insert(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); size_type __bucket_count = this->bucket_count(); - _Base::insert(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__first, __last); + _M_check_rehashed(__bucket_count); } @@ -799,10 +805,16 @@ namespace __debug void insert(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); size_type __bucket_count = this->bucket_count(); - _Base::insert(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__first, __last); + _M_check_rehashed(__bucket_count); } diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector index be679920949..310009756c0 100644 --- a/libstdc++-v3/include/debug/vector +++ b/libstdc++-v3/include/debug/vector @@ -244,9 +244,15 @@ namespace __debug void assign(_InputIterator __first, _InputIterator __last) { - __glibcxx_check_valid_range(__first, __last); - _Base::assign(__gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::assign(__gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::assign(__first, __last); + this->_M_invalidate_all(); this->_M_update_guaranteed_capacity(); } @@ -574,16 +580,21 @@ namespace __debug insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { - __glibcxx_check_insert_range(__position, __first, __last); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_insert_range(__position, __first, __last, __dist); /* Hard to guess if invalidation will occur, because __last - __first can't be calculated in all cases, so we just punt here by checking if it did occur. */ _Base_iterator __old_begin = _M_base().begin(); difference_type __offset = __position.base() - _Base::cbegin(); - _Base_iterator __res = _Base::insert(__position.base(), - __gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + _Base_iterator __res; + if (__dist.second >= __gnu_debug::__dp_sign) + __res = _Base::insert(__position.base(), + __gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + __res = _Base::insert(__position.base(), __first, __last); if (_M_base().begin() != __old_begin) this->_M_invalidate_all(); @@ -598,15 +609,19 @@ namespace __debug insert(iterator __position, _InputIterator __first, _InputIterator __last) { - __glibcxx_check_insert_range(__position, __first, __last); + typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; + __glibcxx_check_insert_range(__position, __first, __last, __dist); /* Hard to guess if invalidation will occur, because __last - __first can't be calculated in all cases, so we just punt here by checking if it did occur. */ _Base_iterator __old_begin = _M_base().begin(); difference_type __offset = __position.base() - _Base::begin(); - _Base::insert(__position.base(), __gnu_debug::__base(__first), - __gnu_debug::__base(__last)); + if (__dist.second >= __gnu_debug::__dp_sign) + _Base::insert(__position.base(), __gnu_debug::__unsafe(__first), + __gnu_debug::__unsafe(__last)); + else + _Base::insert(__position.base(), __first, __last); if (_M_base().begin() != __old_begin) this->_M_invalidate_all(); -- 2.30.2