This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Debug algos evolution
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Thu, 14 Nov 2013 22:03:28 +0100
- Subject: Debug algos evolution
- Authentication-results: sourceware.org; auth=none
Hi
Here is a proposal for an evolution of debug algos. It is far from
being complete but I would like to know first if you find it interesting.
The new approach is to expose real debug algos rather than to have
debug macros in normal algos. To do so I had to introduce a dedicated
namespace __cxx1998_a different of the one used for debug containers
otherwise, because of ADL, the compiler do not know what version of the
algo to use when it is called with an iterator of a debug container.
The advantage of this approach is that:
- we can implement any debug checks without polluting normal algos
- debug algos are now aware about debug iterators and can remove debug
layer before invoking normal algos. This will reduce perfomance hint of
debug mode. For instance this code:
std::vector<int> v1, v2;
//....
std::copy(v1.begin(), v1.end(), v2.begin());
will continue to rely on memmove with or without debug mode.
Note that I have also started implementing new checks to try and
detect overlapping when invoking swap_ranges or copy or move. Paolo, you
said that we needed to use std::less to do some comparison, is it also
true for a random access iterator ?
Some checks are even on only potential issues like in std::equal.
For the moment debug mode will detect an issue in this algo only if all
compared values are equals until we reach a past-the-end iterator. With
this evolution we will notify an issue even if the first values are not
equal. IMO it simply means that the code is wrong and will crash one day
sooner or later.
What do you think about it ?
François
Index: src/c++11/debug.cc
===================================================================
--- src/c++11/debug.cc (revision 204819)
+++ src/c++11/debug.cc (working copy)
@@ -182,7 +182,14 @@
" container only holds %3; buckets",
"load factor shall be positive",
"allocators must be equal",
- "attempt to insert with an iterator range [%1.name;, %2.name;) from this container"
+ "attempt to insert with an iterator range [%1.name;, %2.name;) from this"
+ " container",
+ "completing the operation might result in accessing unaccessible memory",
+ "range starting at %3.name; overlap [%1.name;, %2.name;)",
+ "copying [%1.name;, %2.name;) to [%3.name;, %3.name; + (%2.name; -"
+ " %1.name;)) won't have the expected result, ranges overlap",
+ "copying (%1.name;, %2.name;] to (%3.name; - (%2.name; - %1.name;),"
+ " %3.name;] won't have the expected result, ranges overlap"
};
void
Index: include/Makefile.in
===================================================================
--- include/Makefile.in (revision 204819)
+++ include/Makefile.in (working copy)
@@ -978,6 +978,10 @@
debug_srcdir = ${glibcxx_srcdir}/include/debug
debug_builddir = ./debug
debug_headers = \
+ ${debug_srcdir}/algo.h \
+ ${debug_srcdir}/algobase.h \
+ ${debug_srcdir}/algorithm \
+ ${debug_srcdir}/algorithmfwd.h \
${debug_srcdir}/array \
${debug_srcdir}/bitset \
${debug_srcdir}/debug.h \
@@ -991,6 +995,7 @@
${debug_srcdir}/map.h \
${debug_srcdir}/multimap.h \
${debug_srcdir}/multiset.h \
+ ${debug_srcdir}/numeric \
${debug_srcdir}/safe_base.h \
${debug_srcdir}/safe_iterator.h \
${debug_srcdir}/safe_iterator.tcc \
Index: include/debug/numeric
===================================================================
--- include/debug/numeric (revision 0)
+++ include/debug/numeric (revision 0)
@@ -0,0 +1,95 @@
+// -*- C++ -*-
+
+// Copyright (C) 2013 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
+// <http://www.gnu.org/licenses/>.
+
+/**
+ * @file debug/numeric
+*
+ * This file is a GNU debug extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_DEBUG_NUMERIC_H
+#define _GLIBCXX_DEBUG_NUMERIC_H 1
+
+#include <numeric>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+namespace __debug
+{
+ template<typename _IIter, typename _Tp>
+ inline _Tp
+ accumulate(_IIter __begin, _IIter __end, _Tp __init)
+ { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); }
+
+ template<typename _IIter, typename _Tp, typename _BinaryOperation>
+ inline _Tp
+ accumulate(_IIter __begin, _IIter __end, _Tp __init,
+ _BinaryOperation __binary_op)
+ { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init, __binary_op); }
+
+ template<typename _IIter1, typename _IIter2, typename _Tp>
+ inline _Tp
+ inner_product(_IIter1 __first1, _IIter1 __last1,
+ _IIter2 __first2, _Tp __init)
+ { return _GLIBCXX_STD_A::inner_product(
+ __first1, __last1, __first2, __init); }
+
+ template<typename _IIter1, typename _IIter2, typename _Tp,
+ typename _BinaryFunction1, typename _BinaryFunction2>
+ inline _Tp
+ inner_product(_IIter1 __first1, _IIter1 __last1,
+ _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
+ _BinaryFunction2 __binary_op2)
+ { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init,
+ __binary_op1, __binary_op2); }
+
+ template<typename _IIter, typename _OutputIterator>
+ inline _OutputIterator
+ partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
+ { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }
+
+ template<typename _IIter, typename _OutputIterator,
+ typename _BinaryOperation>
+ inline _OutputIterator
+ partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
+ _BinaryOperation __bin_op)
+ { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
+
+
+ template<typename _IIter, typename _OutputIterator>
+ inline _OutputIterator
+ adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result)
+ { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }
+
+ template<typename _IIter, typename _OutputIterator,
+ typename _BinaryOperation>
+ inline _OutputIterator
+ adjacent_difference(_IIter __begin, _IIter __end,
+ _OutputIterator __result, _BinaryOperation __bin_op)
+ { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end,
+ __result, __bin_op); }
+} // end namespace
+} // end namespace
+
+#endif /* _GLIBCXX_NUMERIC_H */
Index: include/debug/list
===================================================================
--- include/debug/list (revision 204819)
+++ include/debug/list (working copy)
@@ -797,6 +797,24 @@
template<class _Tp, class _Alloc>
struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
{ enum { __value = 1 }; };
+
+ template<class _Tp, class _Alloc>
+ struct _Size_helper<std::__debug::list<_Tp, _Alloc> >
+ {
+ typedef std::__debug::list<_Tp, _Alloc> _Sequence;
+
+ template<typename _Iterator>
+ static std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ _S_size(const _Safe_iterator<_Iterator, _Sequence>& __it)
+ {
+ typedef typename _Diff_type_helper<_Iterator>::_Type _DiffType;
+ if (__it._M_get_sequence()->empty())
+ return std::make_pair(_DiffType(0), __dp_exact);
+ else
+ return std::make_pair(_DiffType(1), __dp_sign);
+ }
+ };
}
#endif
Index: include/debug/algorithmfwd.h
===================================================================
--- include/debug/algorithmfwd.h (revision 0)
+++ include/debug/algorithmfwd.h (revision 0)
@@ -0,0 +1,293 @@
+// <debug/algorithm> Forward declarations -*- C++ -*-
+
+// Copyright (C) 2013 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
+// <http://www.gnu.org/licenses/>.
+
+/** @file debug/algorithmfwd.h
+ * This file is a GNU debug extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_DEBUG_ALGORITHMFWD_H
+#define _GLIBCXX_DEBUG_ALGORITHMFWD_H 1
+
+#pragma GCC system_header
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+namespace __debug
+{
+ template<typename _FIter>
+ _FIter
+ adjacent_find(_FIter, _FIter);
+
+ template<typename _FIter, typename _BiPredicate>
+ _FIter
+ adjacent_find(_FIter, _FIter, _BiPredicate);
+
+ template<typename _IIter, typename _Tp>
+ typename iterator_traits<_IIter>::difference_type
+ count(_IIter, _IIter, const _Tp&);
+
+ template<typename _IIter, typename _Predicate>
+ typename iterator_traits<_IIter>::difference_type
+ count_if(_IIter, _IIter, _Predicate);
+
+ // algobase.h
+ template<typename _IIter1, typename _IIter2>
+ _IIter2
+ swap_ranges(_IIter1, _IIter1, _IIter2);
+
+ template<typename _II, typename _OI>
+ _OI
+ copy(_II, _II, _OI);
+
+ template<typename _BI1, typename _BI2>
+ _BI2
+ copy_backward(_BI1, _BI1, _BI2);
+
+#if __cplusplus >= 201103L
+ template<typename _II, typename _OI>
+ _OI
+ move(_II, _II, _OI);
+
+ template<typename _BI1, typename _BI2>
+ _BI2
+ move_backward(_BI1, _BI1, _BI2);
+#endif
+
+ template<typename _FI, typename _Tp>
+ void
+ fill(_FI, _FI, const _Tp&);
+
+ template<typename _OI, typename _Size, typename _Tp>
+ _OI
+ fill_n(_OI, _Size, const _Tp&);
+
+ template<typename _IIter1, typename _IIter2>
+ bool
+ equal(_IIter1, _IIter1, _IIter2);
+
+ template<typename _IIter1, typename _IIter2, typename _Predicate>
+ bool
+ equal(_IIter1, _IIter1, _IIter2, _Predicate);
+
+ template<typename _IIter, typename _Tp>
+ _IIter
+ find(_IIter, _IIter, const _Tp& __val);
+
+ template<typename _IIter, typename _Predicate>
+ _IIter
+ find_if(_IIter, _IIter, _Predicate);
+
+ template<typename _IIter, typename _FIter, typename _BiPredicate>
+ _IIter
+ find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate);
+
+ template<typename _IIter, typename _FIter>
+ _IIter
+ find_first_of(_IIter, _IIter, _FIter, _FIter);
+
+ template<typename _IIter, typename _Function>
+ _Function
+ for_each(_IIter, _IIter, _Function);
+
+ template<typename _FIter, typename _Generator>
+ void
+ generate(_FIter, _FIter, _Generator);
+
+ template<typename _OIter, typename _Size, typename _Generator>
+ _OIter
+ generate_n(_OIter, _Size, _Generator);
+
+ template<typename _IIter1, typename _IIter2>
+ bool
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
+
+ template<typename _IIter1, typename _IIter2, typename _Predicate>
+ bool
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Predicate);
+
+ // algo.h
+ template<typename _IIter1, typename _IIter2>
+ pair<_IIter1, _IIter2>
+ mismatch(_IIter1, _IIter1, _IIter2);
+
+ template<typename _IIter1, typename _IIter2, typename _Predicate>
+ pair<_IIter1, _IIter2>
+ mismatch(_IIter1, _IIter1, _IIter2, _Predicate);
+
+ template<typename _FIter1, typename _FIter2>
+ _FIter1
+ search(_FIter1, _FIter1, _FIter2, _FIter2);
+
+ template<typename _FIter1, typename _FIter2, typename _BiPredicate>
+ _FIter1
+ search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate);
+
+ template<typename _FIter, typename _Integer, typename _Tp>
+ _FIter
+ search_n(_FIter, _FIter, _Integer, const _Tp&);
+
+ template<typename _FIter, typename _Integer, typename _Tp,
+ typename _BiPredicate>
+ _FIter
+ search_n(_FIter, _FIter, _Integer, const _Tp&, _BiPredicate);
+
+ template<typename _IIter, typename _OIter, typename _UnaryOperation>
+ _OIter
+ transform(_IIter, _IIter, _OIter, _UnaryOperation);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
+ _OIter
+ transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation);
+
+ template<typename _FIter, typename _Tp>
+ void
+ replace(_FIter, _FIter, const _Tp&, const _Tp&);
+
+ template<typename _FIter, typename _Predicate, typename _Tp>
+ void
+ replace_if(_FIter, _FIter, _Predicate, const _Tp&);
+
+ template<typename _FIter>
+ _FIter
+ max_element(_FIter, _FIter);
+
+ template<typename _FIter, typename _Compare>
+ _FIter
+ max_element(_FIter, _FIter, _Compare);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
+ _OIter
+ merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter>
+ _OIter
+ merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+
+ template<typename _FIter>
+ _FIter
+ min_element(_FIter, _FIter);
+
+ template<typename _FIter, typename _Compare>
+ _FIter
+ min_element(_FIter, _FIter, _Compare);
+
+ template<typename _RAIter, typename _Compare>
+ void
+ nth_element(_RAIter, _RAIter, _RAIter, _Compare);
+
+ template<typename _RAIter>
+ void
+ nth_element(_RAIter, _RAIter, _RAIter);
+
+ template<typename _RAIter, typename _Compare>
+ void
+ partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
+
+ template<typename _RAIter>
+ void
+ partial_sort(_RAIter, _RAIter, _RAIter);
+
+ template<typename _FIter, typename _Predicate>
+ _FIter
+ partition(_FIter, _FIter, _Predicate);
+
+ template<typename _RAIter>
+ void
+ random_shuffle(_RAIter, _RAIter);
+
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ void
+ random_shuffle(_RAIter, _RAIter,
+#if __cplusplus >= 201103L
+ _RandomNumberGenerator&&);
+#else
+ _RandomNumberGenerator&);
+#endif
+
+ template<typename _IIter1, typename _IIter2, typename _OIter>
+ _OIter
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter>
+ _OIter
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter>
+ _OIter
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ _Predicate);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter>
+ _OIter
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
+
+ template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Predicate>
+ _OIter
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate);
+
+ template<typename _RAIter>
+ void
+ sort(_RAIter, _RAIter);
+
+ template<typename _RAIter, typename _Compare>
+ void
+ sort(_RAIter, _RAIter, _Compare);
+
+ template<typename _RAIter>
+ void
+ stable_sort(_RAIter, _RAIter);
+
+ template<typename _RAIter, typename _Compare>
+ void
+ stable_sort(_RAIter, _RAIter, _Compare);
+
+ template<typename _IIter, typename _OIter>
+ _OIter
+ unique_copy(_IIter, _IIter, _OIter);
+
+ template<typename _IIter, typename _OIter, typename _Predicate>
+ _OIter
+ unique_copy(_IIter, _IIter, _OIter, _Predicate);
+} // end namespace __parallel
+} // end namespace std
+
+#endif /* _GLIBCXX_DEBUG_ALGORITHMFWD_H */
Property changes on: include/debug/algorithmfwd.h
___________________________________________________________________
Added: svn:eol-style
+ native
Index: include/debug/safe_iterator.tcc
===================================================================
--- include/debug/safe_iterator.tcc (revision 204819)
+++ include/debug/safe_iterator.tcc (working copy)
@@ -43,7 +43,7 @@
if (__n < 0)
{
std::pair<difference_type, _Distance_precision> __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 +51,7 @@
else
{
std::pair<difference_type, _Distance_precision> __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;
@@ -69,7 +69,7 @@
/* Determine if we can order the iterators without the help of
the container */
std::pair<difference_type, _Distance_precision> __dist =
- __get_distance(base(), __rhs.base());
+ __get_distance(*this, __rhs);
switch (__dist.second) {
case __dp_equality:
if (__dist.first == 0)
@@ -81,19 +81,53 @@
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. 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;
-
// Assume that this is a valid range; we can't check anything else
return true;
}
+
+ template<typename _Iterator, typename _Sequence>
+ std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ __get_distance_aux(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
+ const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+ {
+ typedef std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision> _Pair;
+ if (__lhs.base() == __rhs.base())
+ return _Pair(0, __dp_exact);
+
+ if (__lhs._M_is_beginnest())
+ if (__rhs._M_is_end())
+ // For forward_list we could return size() + 1 but forward_list has
+ // no size() so we do not have to care about being more accurate.
+ return _Size_helper<_Sequence>::_S_size(__lhs);
+ else if (__rhs._M_is_begin())
+ return _Pair(1, __dp_exact);
+ else
+ return _Pair(1, __dp_sign);
+ else if (__lhs._M_is_begin())
+ if (__rhs._M_is_beginnest())
+ return _Pair(-1, __dp_exact);
+ else if (__rhs._M_is_end())
+ return _Size_helper<_Sequence>::_S_size(__lhs);
+ else
+ return _Pair(1, __dp_sign);
+ else if (__lhs._M_is_end())
+ if (__rhs._M_is_beginnest() || __rhs._M_is_begin())
+ {
+ _Pair __cont_size =
+ _Size_helper<_Sequence>::_S_size(__lhs);
+ return _Pair(-__cont_size.first, __cont_size.second);
+ }
+ else
+ return _Pair(-1, __dp_sign);
+ else if (__rhs._M_is_beginnest() || __rhs._M_is_begin())
+ return _Pair(-1, __dp_sign);
+ else if (__rhs._M_is_end())
+ return _Pair(1, __dp_sign);
+ else
+ return _Pair(1, __dp_equality);
+ }
} // namespace __gnu_debug
#endif
Index: include/debug/algobase.h
===================================================================
--- include/debug/algobase.h (revision 0)
+++ include/debug/algobase.h (revision 0)
@@ -0,0 +1,709 @@
+// Debugging support implementation -*- C++ -*-
+
+// Copyright (C) 2013 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
+// <http://www.gnu.org/licenses/>.
+
+/** @file debug/algobase.h
+ * This file is a GNU debug extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_DEBUG_ALGOBASE_H
+#define _GLIBCXX_DEBUG_ALGOBASE_H 1
+
+#include <debug/safe_iterator.h>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+namespace __debug
+{
+ template<typename _II1, typename _II2>
+ _II2
+ swap_ranges(_II1 __first1, _II1 __last1, _II2 __first2)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+ __glibcxx_check_overlap(__first1, __last1, __first2);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance_to_end(__first2);
+
+ // For first range we just need to know that it is correctly ordered to
+ // bypass the safe layer.
+ if (__dist1.second != __dp_equality)
+ // For second range there is a risk to move out of it unless we know
+ // exactly its number of elements.
+ if (__dist2.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__dist2.first >= __dist1.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__first2));
+ return __safe(__first2,
+ _GLIBCXX_STD_A::swap_ranges(__unsafe(__first1),
+ __unsafe(__last1),
+ __unsafe(__first2)));
+ }
+ else
+ return _GLIBCXX_STD_A::swap_ranges(__unsafe(__first1),
+ __unsafe(__last1),
+ __first2);
+ else
+ return _GLIBCXX_STD_A::swap_ranges(__first1, __last1, __first2);
+ }
+
+ template<typename _II, typename _OI>
+ inline _OI
+ copy(_II __first, _II __last, _OI __result)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first, __last);
+
+ typedef typename _Diff_type_helper<_II>::_Type _IDiffType;
+ std::pair<_IDiffType, _Distance_precision> __idist =
+ __get_distance(__first, __last);
+
+ __glibcxx_check_range_from_dist(__first, __last, __idist);
+ __glibcxx_check_copy(__first, __last, __result);
+
+ typedef typename _Diff_type_helper<_OI>::_Type _ODiffType;
+ std::pair<_ODiffType, _Distance_precision> __odist =
+ __get_distance_to_end(__result);
+
+ if (__idist.second != __dp_equality)
+ if (__odist.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__odist.first >= __idist.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__result));
+ return __safe(__result, _GLIBCXX_STD_A::copy(__unsafe(__first),
+ __unsafe(__last),
+ __unsafe(__result)));
+ }
+ else
+ return _GLIBCXX_STD_A::copy(__unsafe(__first), __unsafe(__last),
+ __result);
+ else
+ return _GLIBCXX_STD_A::copy(__first, __last, __result);
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _II, typename _OI>
+ inline _OI
+ move(_II __first, _II __last, _OI __result)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first, __last);
+
+ typedef typename _Diff_type_helper<_II>::_Type _IDiffType;
+ std::pair<_IDiffType, _Distance_precision> __idist =
+ __get_distance(__first, __last);
+
+ __glibcxx_check_range_from_dist(__first, __last, __idist);
+ __glibcxx_check_copy(__first, __last, __result);
+
+ typedef typename _Diff_type_helper<_OI>::_Type _ODiffType;
+ std::pair<_ODiffType, _Distance_precision> __odist =
+ __get_distance_to_end(__result);
+
+ if (__idist.second != __dp_equality)
+ if (__odist.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__odist.first >= __idist.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__result));
+ return __safe(__result, _GLIBCXX_STD_A::move(__unsafe(__first),
+ __unsafe(__last),
+ __unsafe(__result)));
+ }
+ else
+ return _GLIBCXX_STD_A::move(__unsafe(__first), __unsafe(__last),
+ __result);
+ else
+ return _GLIBCXX_STD_A::move(__first, __last, __result);
+ }
+#endif
+
+ template<typename _BI1, typename _BI2>
+ inline _BI2
+ copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first, __last);
+
+ typedef typename _Diff_type_helper<_BI1>::_Type _BIDiffType1;
+ std::pair<_BIDiffType1, _Distance_precision> __bidist1 =
+ __get_distance(__first, __last);
+
+ __glibcxx_check_range_from_dist(__first, __last, __bidist1);
+ __glibcxx_check_copy_backward(__first, __last, __result);
+
+ typedef typename _Diff_type_helper<_BI2>::_Type _BIDiffType2;
+ std::pair<_BIDiffType2, _Distance_precision> __bidist2 =
+ __get_distance_from_begin(__result);
+
+ if (__bidist1.second != __dp_equality)
+ if (__bidist2.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__bidist2.first >= __bidist1.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__result));
+ return __safe(__result,
+ _GLIBCXX_STD_A::copy_backward(__unsafe(__first),
+ __unsafe(__last),
+ __unsafe(__result)));
+ }
+ else
+ return _GLIBCXX_STD_A::copy_backward(__unsafe(__first),
+ __unsafe(__last),
+ __result);
+ else
+ return _GLIBCXX_STD_A::copy_backward(__first, __last, __result);
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _BI1, typename _BI2>
+ inline _BI2
+ move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first, __last);
+
+ typedef typename _Diff_type_helper<_BI1>::_Type _BIDiffType1;
+ std::pair<_BIDiffType1, _Distance_precision> __bidist1 =
+ __get_distance(__first, __last);
+
+ __glibcxx_check_range_from_dist(__first, __last, __bidist1);
+ __glibcxx_check_copy_backward(__first, __last, __result);
+
+ typedef typename _Diff_type_helper<_BI2>::_Type _BIDiffType2;
+ std::pair<_BIDiffType2, _Distance_precision> __bidist2 =
+ __get_distance_from_begin(__result);
+
+ if (__bidist1.second != __dp_equality)
+ if (__bidist1.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__bidist2.first >= __bidist1.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__result));
+ return __safe(__result,
+ _GLIBCXX_STD_A::move_backward(__unsafe(__first),
+ __unsafe(__last),
+ __unsafe(__result)));
+ }
+ else
+ return _GLIBCXX_STD_A::move_backward(__unsafe(__first),
+ __unsafe(__last),
+ __result);
+ else
+ return _GLIBCXX_STD_A::move_backward(__first, __last, __result);
+ }
+#endif
+
+ template<typename _FI, typename _Tp>
+ inline void
+ fill(_FI __first, _FI __last, const _Tp& __value)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first, __last);
+
+ typedef typename _Diff_type_helper<_FI>::_Type _FIDiffType;
+ std::pair<_FIDiffType, _Distance_precision> __dist =
+ __get_distance(__first, __last);
+
+ __glibcxx_check_range_from_dist(__first, __last, __dist);
+
+ if (__dist.second != __dp_equality)
+ _GLIBCXX_STD_A::fill(__unsafe(__first), __unsafe(__last), __value);
+ else
+ _GLIBCXX_STD_A::fill(__first, __last, __value);
+ }
+
+ template<typename _OI, typename _Size, typename _Tp>
+ inline _OI
+ fill_n(_OI __first, _Size __n, const _Tp& __value)
+ {
+ using namespace __gnu_debug;
+
+ typedef typename _Diff_type_helper<_OI>::_Type _OIDiffType;
+ std::pair<_OIDiffType, _Distance_precision> __dist =
+ __get_distance_to_end(__first);
+
+ if (__dist.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__dist.first >= __n,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__first));
+ return __safe(__first,
+ _GLIBCXX_STD_A::fill_n(__unsafe(__first),
+ __n, __value));
+ }
+ else
+ return _GLIBCXX_STD_A::fill_n(__first, __n, __value);
+ }
+
+ template<typename _II1, typename _II2>
+ inline bool
+ equal(_II1 __first1, _II1 __last1, _II2 __first2)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance_to_end(__first2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__dist2.first >= __dist1.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__first2));
+ return _GLIBCXX_STD_A::equal(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2));
+ }
+ else
+ return _GLIBCXX_STD_A::equal(__unsafe(__first1), __unsafe(__last1),
+ __first2);
+ else
+ return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
+ }
+
+ template<typename _II1, typename _II2, typename _BinaryPredicate>
+ inline bool
+ equal(_II1 __first1, _II1 __last1,
+ _II2 __first2, _BinaryPredicate __binary_pred)
+ {
+ using namespace __gnu_debug;;
+ __glibcxx_check_can_compare(__first1, __last1);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance_to_end(__first2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__dist2.first >= __dist1.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__first2));
+ return _GLIBCXX_STD_A::equal(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2), __binary_pred);
+ }
+ else
+ return _GLIBCXX_STD_A::equal(__unsafe(__first1), __unsafe(__last1),
+ __first2, __binary_pred);
+ else
+ return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
+ __binary_pred);
+ }
+
+#if __cplusplus > 201103L
+ template<typename _II1, typename _II2>
+ inline bool
+ equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+ __glibcxx_check_can_compare(__first2, __last2);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance(__first2, __last2);
+
+ __glibcxx_check_range_from_dist(__first2, __last2, __dist2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second != __dp_equality)
+ return _GLIBCXX_STD_A::equal(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2), __unsafe(__last2));
+ else
+ return _GLIBCXX_STD_A::equal(__unsafe(__first1), __unsafe(__last1),
+ __first2, __last2);
+ else
+ if (__dist2.second != __dp_equality)
+ return _GLIBCXX_STD_A::equal(__first1, __last1,
+ __unsafe(__first2), __unsafe(__last2));
+ else
+ return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, __last2);
+ }
+
+ template<typename _II1, typename _II2, typename _BinaryPredicate>
+ inline bool
+ equal(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2, _BinaryPredicate __binary_pred)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+ __glibcxx_check_can_compare(__first2, __last2);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance(__first2, __last2);
+
+ __glibcxx_check_range_from_dist(__first2, __last2, __dist2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second != __dp_equality)
+ return _GLIBCXX_STD_A::equal(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2), __unsafe(__last2),
+ __binary_pred);
+ else
+ return _GLIBCXX_STD_A::equal(__unsafe(__first1), __unsafe(__last1),
+ __first2, __last2, __binary_pred);
+ else
+ if (__dist2.second != __dp_equality)
+ return _GLIBCXX_STD_A::equal(__first1, __last1,
+ __unsafe(__first2), __unsafe(__last2),
+ __binary_pred);
+ else
+ return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, __last2,
+ __binary_pred);
+ }
+#endif
+
+ template<typename _II1, typename _II2>
+ inline bool
+ lexicographical_compare(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+ __glibcxx_check_can_compare(__first2, __last2);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance(__first2, __last2);
+
+ __glibcxx_check_range_from_dist(__first2, __last2, __dist2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second != __dp_equality)
+ return _GLIBCXX_STD_A::lexicographical_compare(__unsafe(__first1),
+ __unsafe(__last1),
+ __unsafe(__first2),
+ __unsafe(__last2));
+ else
+ return _GLIBCXX_STD_A::lexicographical_compare(__unsafe(__first1),
+ __unsafe(__last1),
+ __first2, __last2);
+ else
+ if (__dist2.second != __dp_equality)
+ return _GLIBCXX_STD_A::lexicographical_compare(__first1, __last1,
+ __unsafe(__first2),
+ __unsafe(__last2));
+ else
+ return _GLIBCXX_STD_A::lexicographical_compare(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _II1, typename _II2, typename _Compare>
+ inline bool
+ lexicographical_compare(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2, _Compare __comp)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+ __glibcxx_check_can_compare(__first2, __last2);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance(__first2, __last2);
+
+ __glibcxx_check_range_from_dist(__first2, __last2, __dist2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second != __dp_equality)
+ return _GLIBCXX_STD_A::lexicographical_compare(__unsafe(__first1),
+ __unsafe(__last1),
+ __unsafe(__first2),
+ __unsafe(__last2),
+ __comp);
+ else
+ return _GLIBCXX_STD_A::lexicographical_compare(__unsafe(__first1),
+ __unsafe(__last1),
+ __first2, __last2,
+ __comp);
+ else
+ if (__dist2.second != __dp_exact)
+ return _GLIBCXX_STD_A::lexicographical_compare(__first1, __last1,
+ __unsafe(__first2),
+ __unsafe(__last2),
+ __comp);
+ else
+ return _GLIBCXX_STD_A::lexicographical_compare(__first1, __last1,
+ __first2, __last2,
+ __comp);
+ }
+
+ template<typename _II1, typename _II2>
+ inline std::pair<_II1, _II2>
+ mismatch(_II1 __first1, _II1 __last1, _II2 __first2)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance_to_end(__first2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__dist2.first >= __dist1.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__first2));
+ std::pair<__decltype(__unsafe(__first1)),
+ __decltype(__unsafe(__first2))> __ret =
+ _GLIBCXX_STD_A::mismatch(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2));
+ return std::make_pair(__safe(__first1, __ret.first),
+ __safe(__first2, __ret.second));
+ }
+ else
+ {
+ std::pair<__decltype(__unsafe(__first1)), _II2> __ret =
+ _GLIBCXX_STD_A::mismatch(__unsafe(__first1), __unsafe(__last1),
+ __first2);
+ return std::make_pair(__safe(__first1, __ret.first), __ret.second);
+ }
+ else
+ return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2);
+ }
+
+ template<typename _II1, typename _II2,
+ typename _BinaryPredicate>
+ inline std::pair<_II1, _II2>
+ mismatch(_II1 __first1, _II1 __last1,
+ _II2 __first2, _BinaryPredicate __binary_pred)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance_to_end(__first2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second == __dp_exact)
+ {
+ _GLIBCXX_DEBUG_VERIFY(__dist2.first >= __dist1.first,
+ _M_message(__msg_forbidden_mem)
+ ._M_iterator(__first2));
+ std::pair<__decltype(__unsafe(__first1)),
+ __decltype(__unsafe(__first2))> __ret =
+ _GLIBCXX_STD_A::mismatch(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2), __binary_pred);
+ return std::make_pair(__safe(__first1, __ret.first),
+ __safe(__first2, __ret.second));
+ }
+ else
+ {
+ std::pair<__decltype(__unsafe(__first1)), _II2> __ret =
+ _GLIBCXX_STD_A::mismatch(__unsafe(__first1), __unsafe(__last1),
+ __first2, __binary_pred);
+ return std::make_pair(__safe(__first1, __ret.first), __ret.second);
+ }
+ else
+ return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2,
+ __binary_pred);
+ }
+
+#if __cplusplus > 201103L
+ template<typename _II1, typename _II2>
+ inline std::pair<_II1, _II2>
+ mismatch(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+ __glibcxx_check_can_compare(__first2, __last2);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance(__first2, __last2);
+
+ __glibcxx_check_range_from_dist(__first2, __last2, __dist2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second != __dp_equality)
+ {
+ std::pair<__decltype(__unsafe(__first1)),
+ __decltype(__unsafe(__first2))> __ret =
+ _GLIBCXX_STD_A::mismatch(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2), __unsafe(__last2));
+ return std::make_pair(__safe(__first1, __ret.first),
+ __safe(__first2, __ret.second));
+ }
+ else
+ {
+ std::pair<__decltype(__unsafe(__first1)), _II2> __ret =
+ _GLIBCXX_STD_A::mismatch(__unsafe(__first1), __unsafe(__last1),
+ __first2, __last2);
+ return std::make_pair(__safe(__first1, __ret.first), __ret.second);
+ }
+ else
+ if (__dist2.second != __dp_equality)
+ {
+ std::pair<_II1, __decltype(__unsafe(__first2))> __ret =
+ _GLIBCXX_STD_A::mismatch(__first1, __last1,
+ __unsafe(__first2), __unsafe(__last2));
+ return std::make_pair(__ret.first, __safe(__first2, __ret.second));
+ }
+ else
+ return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2);
+ }
+
+ template<typename _II1, typename _II2,
+ typename _BinaryPredicate>
+ inline pair<_II1, _II2>
+ mismatch(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2,
+ _BinaryPredicate __binary_pred)
+ {
+ using namespace __gnu_debug;
+
+ __glibcxx_check_can_compare(__first1, __last1);
+ __glibcxx_check_can_compare(__first2, __last2);
+
+ typedef typename _Diff_type_helper<_II1>::_Type _DiffType1;
+ std::pair<_DiffType1, _Distance_precision> __dist1 =
+ __get_distance(__first1, __last1);
+
+ __glibcxx_check_range_from_dist(__first1, __last1, __dist1);
+
+ typedef typename _Diff_type_helper<_II2>::_Type _DiffType2;
+ std::pair<_DiffType2, _Distance_precision> __dist2 =
+ __get_distance(__first2, __last2);
+
+ __glibcxx_check_range_from_dist(__first2, __last2, __dist2);
+
+ if (__dist1.second != __dp_equality)
+ if (__dist2.second != __dp_equality)
+ {
+ std::pair<__decltype(__unsafe(__first1)),
+ __decltype(__unsafe(__first2))> __ret =
+ _GLIBCXX_STD_A::mismatch(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2), __unsafe(__last2),
+ __binary_pred);
+ return std::make_pair(__safe(__first1, __ret.first),
+ __safe(__first2, __ret.second));
+ }
+ else
+ {
+ std::pair<__decltype(__unsafe(__first1)), _II2> __ret =
+ _GLIBCXX_STD_A::mismatch(__unsafe(__first1), __unsafe(__last1),
+ __first2, __last2, __binary_pred);
+ return std::make_pair(__safe(__first1, __ret.first), __ret.second);
+ }
+ else
+ if (__dist2.second != __dp_equality)
+ {
+ std::pair<_II1, __decltype(__unsafe(__first2))> __ret =
+ _GLIBCXX_STD_A::mismatch(__first1, __last1,
+ __unsafe(__first2), __unsafe(__last2),
+ __binary_pred);
+ return std::make_pair(__ret.first, __safe(__first2, __ret.second));
+ }
+ else
+ return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2,
+ __binary_pred);
+ }
+#endif
+
+} // end namespace
+} // end namespace
+
+#endif /* _GLIBCXX_DEBUG_ALGOBASE_H */
Property changes on: include/debug/algobase.h
___________________________________________________________________
Added: svn:eol-style
+ native
Index: include/debug/algo.h
===================================================================
--- include/debug/algo.h (revision 0)
+++ include/debug/algo.h (revision 0)
@@ -0,0 +1,377 @@
+// -*- C++ -*-
+
+// Copyright (C) 2013 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
+// <http://www.gnu.org/licenses/>.
+
+/** @file debug/algo.h
+ * This file is a GNU debug extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_DEBUG_ALGO_H
+#define _GLIBCXX_DEBUG_ALGO_H 1
+
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+namespace __debug
+{
+ template<typename _IIter, typename _Function>
+ inline _Function
+ for_each(_IIter __begin, _IIter __end, _Function __f)
+ { return _GLIBCXX_STD_A::for_each(__begin, __end, __f); }
+
+ template<typename _IIter, typename _Tp>
+ inline _IIter
+ find(_IIter __begin, _IIter __end, const _Tp& __val)
+ { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
+
+ template<typename _IIter, typename _Predicate>
+ inline _IIter
+ find_if(_IIter __begin, _IIter __end, _Predicate __pred)
+ { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
+
+ template<typename _IIter, typename _FIterator>
+ inline _IIter
+ find_first_of(_IIter __begin1, _IIter __end1,
+ _FIterator __begin2, _FIterator __end2)
+ {
+ return _GLIBCXX_STD_A::find_first_of(__begin1, __end1, __begin2, __end2);
+ }
+
+ template<typename _IIter, typename _FIterator,
+ typename _BinaryPredicate>
+ inline _IIter
+ find_first_of(_IIter __begin1, _IIter __end1,
+ _FIterator __begin2, _FIterator __end2,
+ _BinaryPredicate __comp)
+ {
+ return _GLIBCXX_STD_A::find_first_of(__begin1, __end1,
+ __begin2, __end2, __comp);
+ }
+
+ template<typename _IIter, typename _OutputIterator>
+ inline _OutputIterator
+ unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out)
+ { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out); }
+
+ template<typename _IIter, typename _OutputIterator,
+ typename _Predicate>
+ inline _OutputIterator
+ unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
+ _Predicate __pred)
+ { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out, __pred); }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator>
+ inline _OutputIterator
+ set_union(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2,
+ _OutputIterator __out)
+ {
+ return _GLIBCXX_STD_A::set_union(__begin1, __end1,
+ __begin2, __end2, __out);
+ }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator, typename _Predicate>
+ inline _OutputIterator
+ set_union(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2,
+ _OutputIterator __out, _Predicate __pred)
+ {
+ return _GLIBCXX_STD_A::set_union(__begin1, __end1,
+ __begin2, __end2, __out, __pred);
+ }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator>
+ inline _OutputIterator
+ set_intersection(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2,
+ _OutputIterator __out)
+ {
+ return _GLIBCXX_STD_A::set_intersection(__begin1, __end1,
+ __begin2, __end2, __out);
+ }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator, typename _Predicate>
+ inline _OutputIterator
+ set_intersection(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2,
+ _OutputIterator __out, _Predicate __pred)
+ {
+ return _GLIBCXX_STD_A::set_intersection(__begin1, __end1,
+ __begin2, __end2, __out, __pred);
+ }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator>
+ inline _OutputIterator
+ set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2,
+ _OutputIterator __out)
+ {
+ return _GLIBCXX_STD_A::set_symmetric_difference(__begin1, __end1,
+ __begin2, __end2, __out);
+ }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator, typename _Predicate>
+ inline _OutputIterator
+ set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2,
+ _OutputIterator __out, _Predicate __pred)
+ {
+ return _GLIBCXX_STD_A::set_symmetric_difference(__begin1, __end1,
+ __begin2, __end2, __out,
+ __pred);
+ }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator>
+ inline _OutputIterator
+ set_difference(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2,
+ _OutputIterator __out)
+ {
+ return _GLIBCXX_STD_A::set_difference(__begin1,__end1,
+ __begin2, __end2, __out);
+ }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator, typename _Predicate>
+ inline _OutputIterator
+ set_difference(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2,
+ _OutputIterator __out, _Predicate __pred)
+ {
+ return _GLIBCXX_STD_A::set_difference(__begin1, __end1,
+ __begin2, __end2, __out, __pred);
+ }
+
+ template<typename _FIterator>
+ inline _FIterator
+ adjacent_find(_FIterator __begin, _FIterator __end)
+ { return _GLIBCXX_STD_A::adjacent_find(__begin, __end); }
+
+ template<typename _FIterator, typename _BinaryPredicate>
+ inline _FIterator
+ adjacent_find(_FIterator __begin, _FIterator __end,
+ _BinaryPredicate __binary_pred)
+ { return _GLIBCXX_STD_A::adjacent_find(__begin, __end, __binary_pred); }
+
+ // Sequential fallback
+ template<typename _IIter, typename _Tp>
+ inline typename iterator_traits<_IIter>::difference_type
+ count(_IIter __begin, _IIter __end, const _Tp& __value)
+ { return _GLIBCXX_STD_A::count(__begin, __end, __value); }
+
+ template<typename _IIter, typename _Predicate>
+ inline typename iterator_traits<_IIter>::difference_type
+ count_if(_IIter __begin, _IIter __end, _Predicate __pred)
+ { return _GLIBCXX_STD_A::count_if(__begin, __end, __pred); }
+
+ template<typename _FIterator1, typename _FIterator2>
+ inline _FIterator1
+ search(_FIterator1 __begin1, _FIterator1 __end1,
+ _FIterator2 __begin2, _FIterator2 __end2)
+ { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); }
+
+ template<typename _FIterator1, typename _FIterator2,
+ typename _BinaryPredicate>
+ inline _FIterator1
+ search(_FIterator1 __begin1, _FIterator1 __end1,
+ _FIterator2 __begin2, _FIterator2 __end2,
+ _BinaryPredicate __pred)
+ {
+ return _GLIBCXX_STD_A::search(__begin1, __end1,
+ __begin2, __end2, __pred);
+ }
+
+ template<typename _FIterator, typename _Integer, typename _Tp>
+ inline _FIterator
+ search_n(_FIterator __begin, _FIterator __end, _Integer __count,
+ const _Tp& __val)
+ { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); }
+
+ template<typename _FIterator, typename _Integer, typename _Tp,
+ typename _BinaryPredicate>
+ inline _FIterator
+ search_n(_FIterator __begin, _FIterator __end, _Integer __count,
+ const _Tp& __val, _BinaryPredicate __binary_pred)
+ {
+ return _GLIBCXX_STD_A::search_n(__begin, __end,
+ __count, __val, __binary_pred);
+ }
+
+ template<typename _IIter, typename _OutputIterator,
+ typename _UnaryOperation>
+ inline _OutputIterator
+ transform(_IIter __begin, _IIter __end, _OutputIterator __result,
+ _UnaryOperation __unary_op)
+ { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator, typename _BinaryOperation>
+ inline _OutputIterator
+ transform(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _OutputIterator __result,
+ _BinaryOperation __binary_op)
+ {
+ return _GLIBCXX_STD_A::transform(__begin1, __end1,
+ __begin2, __result, __binary_op);
+ }
+
+ template<typename _FIterator, typename _Tp>
+ inline void
+ replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
+ const _Tp& __new_value)
+ { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); }
+
+ template<typename _FIterator, typename _Predicate, typename _Tp>
+ inline void
+ replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred,
+ const _Tp& __new_value)
+ { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); }
+
+ template<typename _FIterator, typename _Generator>
+ inline void
+ generate(_FIterator __begin, _FIterator __end, _Generator __gen)
+ { _GLIBCXX_STD_A::generate(__begin, __end, __gen); }
+
+ template<typename _OutputIterator, typename _Size, typename _Generator>
+ inline _OutputIterator
+ generate_n(_OutputIterator __begin, _Size __n, _Generator __gen)
+ { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); }
+
+ template<typename _RAIter>
+ inline void
+ random_shuffle(_RAIter __begin, _RAIter __end)
+ { _GLIBCXX_STD_A::random_shuffle(__begin, __end); }
+
+ // Parallel algorithm for random access iterators.
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ void
+ random_shuffle(_RAIter __begin, _RAIter __end,
+#if __cplusplus >= 201103L
+ _RandomNumberGenerator&& __rand)
+#else
+ _RandomNumberGenerator& __rand)
+#endif
+ { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); }
+
+ template<typename _FIterator, typename _Predicate>
+ inline _FIterator
+ partition(_FIterator __begin, _FIterator __end,
+ _Predicate __pred)
+ { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); }
+
+ template<typename _RAIter>
+ inline void
+ sort(_RAIter __begin, _RAIter __end)
+ { _GLIBCXX_STD_A::sort(__begin, __end); }
+
+ template<typename _RAIter, typename _Compare>
+ inline void
+ sort(_RAIter __begin, _RAIter __end, _Compare __comp)
+ { _GLIBCXX_STD_A::sort(__begin, __end, __comp); }
+
+ template<typename _RAIter>
+ inline void
+ stable_sort(_RAIter __begin, _RAIter __end)
+ { _GLIBCXX_STD_A::stable_sort(__begin, __end); }
+
+ template<typename _RAIter, typename _Compare>
+ inline void
+ stable_sort(_RAIter __begin, _RAIter __end,
+ _Compare __comp)
+ { _GLIBCXX_STD_A::stable_sort(__begin, __end, __comp); }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator>
+ inline _OutputIterator
+ merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
+ _IIter2 __end2, _OutputIterator __result)
+ {
+ return _GLIBCXX_STD_A::merge(__begin1, __end1,
+ __begin2, __end2, __result);
+ }
+
+ template<typename _IIter1, typename _IIter2,
+ typename _OutputIterator, typename _Compare>
+ inline _OutputIterator
+ merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
+ _IIter2 __end2, _OutputIterator __result, _Compare __comp)
+ {
+ return _GLIBCXX_STD_A::merge(__begin1, __end1,
+ __begin2, __end2, __result, __comp);
+ }
+
+ template<typename _RAIter>
+ inline void
+ nth_element(_RAIter __begin, _RAIter __nth, _RAIter __end)
+ { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); }
+
+ // Sequential fallback
+ template<typename _RAIter, typename _Compare>
+ inline void
+ nth_element(_RAIter __begin, _RAIter __nth,
+ _RAIter __end, _Compare __comp)
+ { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); }
+
+ template<typename _RAIter, typename _Compare>
+ inline void
+ partial_sort(_RAIter __begin, _RAIter __middle,
+ _RAIter __end, _Compare __comp)
+ { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); }
+
+ // Public interface, insert default comparator
+ template<typename _RAIter>
+ inline void
+ partial_sort(_RAIter __begin, _RAIter __middle,
+ _RAIter __end)
+ { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); }
+
+ template<typename _FIterator>
+ inline _FIterator
+ max_element(_FIterator __begin, _FIterator __end)
+ { return _GLIBCXX_STD_A::max_element(__begin, __end); }
+
+ template<typename _FIterator, typename _Compare>
+ inline _FIterator
+ max_element(_FIterator __begin, _FIterator __end, _Compare __comp)
+ { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); }
+
+ template<typename _FIterator>
+ inline _FIterator
+ min_element(_FIterator __begin, _FIterator __end)
+ { return _GLIBCXX_STD_A::min_element(__begin, __end); }
+
+ template<typename _FIterator, typename _Compare>
+ inline _FIterator
+ min_element(_FIterator __begin, _FIterator __end, _Compare __comp)
+ { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); }
+} // end namespace
+} // end namespace
+
+#endif /* _GLIBCXX_DEBUG_ALGO_H */
Property changes on: include/debug/algo.h
___________________________________________________________________
Added: svn:eol-style
+ native
Index: include/debug/safe_local_iterator.tcc
===================================================================
--- include/debug/safe_local_iterator.tcc (revision 204819)
+++ include/debug/safe_local_iterator.tcc (working copy)
@@ -32,6 +32,29 @@
namespace __gnu_debug
{
template<typename _Iterator, typename _Sequence>
+ std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ __get_distance_aux(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
+ const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
+ {
+ typedef std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision> _Pair;
+ if (__lhs.base() == __rhs.base())
+ return _Pair(0, __dp_exact);
+
+ if (__lhs._M_is_begin())
+ return _Pair(1, __dp_sign);
+ else if (__lhs._M_is_end())
+ return _Pair(-1, __dp_sign);
+ else if (__rhs._M_is_begin())
+ return _Pair(-1, __dp_sign);
+ else if (__rhs._M_is_end())
+ return _Pair(1, __dp_sign);
+ else
+ return _Pair(1, __dp_equality);
+ }
+
+ template<typename _Iterator, typename _Sequence>
bool
_Safe_local_iterator<_Iterator, _Sequence>::
_M_valid_range(const _Safe_local_iterator& __rhs) const
@@ -44,7 +67,7 @@
/* Determine if we can order the iterators without the help of
the container */
std::pair<difference_type, _Distance_precision> __dist =
- __get_distance(base(), __rhs.base());
+ __get_distance(*this, __rhs);
switch (__dist.second)
{
case __dp_equality:
@@ -57,15 +80,6 @@
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;
}
Index: include/debug/macros.h
===================================================================
--- include/debug/macros.h (revision 204819)
+++ include/debug/macros.h (working copy)
@@ -49,6 +49,29 @@
#define _GLIBCXX_DEBUG_VERIFY(_Condition,_ErrorMessage) \
_GLIBCXX_DEBUG_VERIFY_AT(_Condition,_ErrorMessage,__FILE__,__LINE__)
+// Verify that [_First, _Last) can be a range
+#define __glibcxx_check_can_compare(_First, _Last) \
+ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__can_compare(_First, _Last), \
+ _M_message(__gnu_debug::__msg_valid_range) \
+ ._M_iterator(_First, #_First) \
+ ._M_iterator(_Last, #_Last)); \
+ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__same_bucket(_First, _Last), \
+ _M_message(__gnu_debug::__msg_local_iter_compare_bad) \
+ ._M_iterator(_First, #_First) \
+ ._M_iterator(_Last, #_Last))
+
+/** Verify that [First, _Last) forms a valid range given its computed distance
+ * information.
+ */
+#define __glibcxx_check_range_from_dist(_First, _Last, _Dist) \
+ _GLIBCXX_DEBUG_VERIFY((_Dist.second == __gnu_debug::__dp_equality || \
+ _Dist.first >= 0) && \
+ (_Dist.first == 0 || \
+ __gnu_debug::__check_dereferenceable(_First)), \
+ _M_message(__gnu_debug::__msg_valid_range) \
+ ._M_iterator(_First, #_First) \
+ ._M_iterator(_Last, #_Last))
+
// Verify that [_First, _Last) forms a valid iterator range.
#define __glibcxx_check_valid_range(_First,_Last) \
_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__valid_range(_First, _Last), \
@@ -63,6 +86,33 @@
._M_iterator(_First, #_First) \
._M_iterator(_Last, #_Last))
+/** Verify that range [_Pos, _Pos + (_Last - _First)) doesn't overlap range
+ * [_First, _Last).
+ */
+#define __glibcxx_check_overlap(_First,_Last,_Pos) \
+ _GLIBCXX_DEBUG_VERIFY(!__gnu_debug::__overlap(_First, _Last, _Pos), \
+ _M_message(__gnu_debug::__msg_ranges_overlap) \
+ ._M_iterator(_First, #_First) \
+ ._M_iterator(_Last, #_Last) \
+ ._M_iterator(_Pos, #_Pos))
+
+/** Verify that it is safe to copy [_First, _Last) to _Result */
+#define __glibcxx_check_copy(_First,_Last,_Result) \
+ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_copy(_First, _Last, _Result),\
+ _M_message(__gnu_debug::__msg_copy_bad) \
+ ._M_iterator(_First, #_First) \
+ ._M_iterator(_Last, #_Last) \
+ ._M_iterator(_Result, #_Result))
+
+/** Verify that it is safe to copy (_First, _Last] to _Result backward */
+#define __glibcxx_check_copy_backward(_First,_Last,_Result) \
+ _GLIBCXX_DEBUG_VERIFY( \
+ __gnu_debug::__check_copy_backward(_First, _Last, _Result), \
+ _M_message(__gnu_debug::__msg_copy_backward_bad)\
+ ._M_iterator(_First, #_First) \
+ ._M_iterator(_Last, #_Last) \
+ ._M_iterator(_Result, #_Result))
+
/** Verify that we can insert into *this with the iterator _Position.
* Insertion into a container at a specific position requires that
* the iterator be nonsingular, either dereferenceable or past-the-end,
Index: include/debug/safe_iterator.h
===================================================================
--- include/debug/safe_iterator.h (revision 204819)
+++ include/debug/safe_iterator.h (working copy)
@@ -35,13 +35,14 @@
#include <debug/safe_base.h>
#include <bits/stl_pair.h>
#include <ext/type_traits.h>
+#include <ext/numeric_traits.h>
namespace __gnu_debug
{
/** Helper struct to deal with sequence offering a before_begin
* iterator.
**/
- template <typename _Sequence>
+ template<typename _Sequence>
struct _BeforeBeginHelper
{
template<typename _Iterator>
@@ -62,6 +63,17 @@
__check_singular_aux(const _Safe_iterator_base* __x)
{ return __x->_M_singular(); }
+ /** Iterators that derives from _Safe_iterator_base know if they are
+ * comparable or not.
+ **/
+ inline bool
+ __can_compare_aux(const _Safe_iterator_base* __first,
+ const _Safe_iterator_base* __last)
+ { return __first->_M_can_compare(*__last); }
+
+ template<typename _Iterator, typename _Sequence>
+ class _Safe_iterator;
+
/** The precision to which we can calculate the distance between
* two iterators.
*/
@@ -72,31 +84,131 @@
__dp_exact //< Can determine distance precisely
};
+ /** Helper struct to get a non-void difference type; workaround for output
+ * iterators that might have a void one.
+ */
+ template<typename _Iterator,
+ typename _DiffType
+ = typename std::iterator_traits<_Iterator>::difference_type>
+ struct _Diff_type_helper
+ { typedef _DiffType _Type; };
+
+ template<typename _Iterator>
+ struct _Diff_type_helper<_Iterator, void>
+ { typedef std::ptrdiff_t _Type; };
+
+ /** Helper struct giving sequence size() if available and if O(1) **/
+ template<typename _Sequence>
+ struct _Size_helper
+ {
+ template<typename _Iterator>
+ static std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ _S_size(const _Safe_iterator<_Iterator, _Sequence>& __it)
+ {
+ typedef typename _Diff_type_helper<_Iterator>::_Type _DiffType;
+
+ // Potential conversion from unsigned to signed
+ if (__it._M_get_sequence()->size()
+ > __gnu_cxx::__numeric_traits<_DiffType>::__max)
+ return std::make_pair(__gnu_cxx::__numeric_traits<_DiffType>::__max,
+ __dp_sign);
+ return std::make_pair
+ (static_cast<_DiffType>(__it._M_get_sequence()->size()), __dp_exact);
+ }
+ };
+
/** Determine the distance between two iterators with some known
- * precision.
+ * precision.
*/
template<typename _Iterator>
- inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
+ inline std::pair<typename _Diff_type_helper<_Iterator>::_Type,
_Distance_precision>
+ __get_distance_aux(const _Iterator& __lhs, const _Iterator& __rhs)
+ {
+ typedef std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision> _Pair;
+ if (__lhs == __rhs)
+ return _Pair(0, __dp_exact);
+
+ return _Pair(1, __dp_equality);
+ }
+
+ template<typename _Iterator, typename _Sequence>
+ std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ __get_distance_aux(const _Safe_iterator<_Iterator, _Sequence>&,
+ const _Safe_iterator<_Iterator, _Sequence>&);
+
+ template<typename _Iterator, typename _Sequence>
+ std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ __get_distance_aux(const _Safe_local_iterator<_Iterator, _Sequence>&,
+ const _Safe_local_iterator<_Iterator, _Sequence>&);
+
+ template<typename _Iterator>
+ inline std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
__get_distance(const _Iterator& __lhs, const _Iterator& __rhs,
std::random_access_iterator_tag)
{ return std::make_pair(__rhs - __lhs, __dp_exact); }
template<typename _Iterator>
- inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
+ inline std::pair<typename _Diff_type_helper<_Iterator>::_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); }
+ std::input_iterator_tag)
+ { return __get_distance_aux(__lhs, __rhs); }
template<typename _Iterator>
- inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
+ inline std::pair<typename _Diff_type_helper<_Iterator>::_Type,
_Distance_precision>
__get_distance(const _Iterator& __lhs, const _Iterator& __rhs)
+ { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); }
+
+ // Get distance from beginning of iterator sequence if we are able to access
+ // it.
+ template<typename _Iterator>
+ inline std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ __get_distance_from_begin(const _Iterator&)
+ { return std::make_pair(0, __dp_equality); }
+
+ template<typename _Iterator, typename _Sequence>
+ inline std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ __get_distance_from_begin(const _Safe_iterator<_Iterator, _Sequence>& __to)
+ {
+ if (__to._M_is_beginnest() || __to._M_is_begin())
+ return std::make_pair(0, __dp_exact);
+
+ if (__to._M_is_end())
+ return _Size_helper<_Sequence>::_S_size(__to);
+
+ return __get_distance(__to._M_get_sequence()->_M_base().begin(),
+ __to.base());
+ }
+
+ // Get distance to the end of iterator's sequence if we are able to access it.
+ template<typename _Iterator>
+ inline std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ __get_distance_to_end(const _Iterator&)
+ { return std::make_pair(0, __dp_equality); }
+
+ template<typename _Iterator, typename _Sequence>
+ inline std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ __get_distance_to_end(const _Safe_iterator<_Iterator, _Sequence>& __from)
{
- typedef typename std::iterator_traits<_Iterator>::iterator_category
- _Category;
- return __get_distance(__lhs, __rhs, _Category());
+ if (__from._M_is_beginnest() || __from._M_is_begin())
+ return _Size_helper<_Sequence>::_S_size(__from);
+
+ if (__from._M_is_end())
+ return std::make_pair(0, __dp_exact);
+
+ return __get_distance(__from.base(),
+ __from._M_get_sequence()->_M_base().end());
}
/** \brief Safe iterator wrapper.
@@ -445,7 +557,10 @@
bool
_M_valid_range(const _Safe_iterator& __rhs) const;
- // The sequence this iterator references.
+ // The sequence this iterator references. Need a pointer to const when
+ // const_iterator so that accessing another iterator from it gives a
+ // result consistent with *this iterator, a const_iterator if called from
+ // a const_iterator and an iterator from an iterator.
typename
__gnu_cxx::__conditional_type<std::__are_same<_Const_iterator,
_Safe_iterator>::__value,
Index: include/debug/algorithm
===================================================================
--- include/debug/algorithm (revision 0)
+++ include/debug/algorithm (revision 0)
@@ -0,0 +1,38 @@
+// Algorithm extensions -*- C++ -*-
+
+// Copyright (C) 2013 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
+// <http://www.gnu.org/licenses/>.
+
+/** @file debug/algorithm
+ * This file is a GNU extension to the Standard C++ Library.
+ */
+
+#ifndef _DEBUG_ALGORITHM
+#define _DEBUG_ALGORITHM 1
+
+#pragma GCC system_header
+
+#include <algorithm>
+#include <debug/algobase.h>
+#include <debug/algo.h>
+
+#endif
Index: include/debug/safe_local_iterator.h
===================================================================
--- include/debug/safe_local_iterator.h (revision 204819)
+++ include/debug/safe_local_iterator.h (working copy)
@@ -266,18 +266,19 @@
_M_get_sequence() const
{ return static_cast<_Sequence*>(_M_sequence); }
- /// Is this iterator equal to the sequence's begin() iterator?
+ /// Is this iterator equal to the sequence's begin() iterator ?
bool _M_is_begin() const
{ return base() == _M_get_sequence()->_M_base().begin(_M_bucket); }
- /// Is this iterator equal to the sequence's end() iterator?
+ /// Is this iterator equal to the sequence's end() iterator ?
bool _M_is_end() const
{ return base() == _M_get_sequence()->_M_base().end(_M_bucket); }
- /// Is this iterator part of the same bucket as the other one?
- template <typename _Other>
- bool _M_in_same_bucket(const _Safe_local_iterator<_Other,
- _Sequence>& __other) const
+ /// Is this iterator part of the same bucket as the other one ?
+ template<typename _Other>
+ bool
+ _M_in_same_bucket(const _Safe_local_iterator<_Other,
+ _Sequence>& __other) const
{ return _M_bucket == __other.bucket(); }
};
@@ -286,7 +287,7 @@
operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
{
- _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+ _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
_M_message(__msg_iter_compare_bad)
._M_iterator(__lhs, "lhs")
._M_iterator(__rhs, "rhs"));
@@ -294,10 +295,6 @@
_M_message(__msg_compare_different)
._M_iterator(__lhs, "lhs")
._M_iterator(__rhs, "rhs"));
- _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
- _M_message(__msg_compare_different)
- ._M_iterator(__lhs, "lhs")
- ._M_iterator(__rhs, "rhs"));
_GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
_M_message(__msg_local_iter_compare_bad)
._M_iterator(__lhs, "lhs")
@@ -310,7 +307,7 @@
operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
{
- _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+ _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
_M_message(__msg_iter_compare_bad)
._M_iterator(__lhs, "lhs")
._M_iterator(__rhs, "rhs"));
@@ -350,7 +347,7 @@
operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
{
- _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+ _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
_M_message(__msg_iter_compare_bad)
._M_iterator(__lhs, "lhs")
._M_iterator(__rhs, "rhs"));
Index: include/debug/formatter.h
===================================================================
--- include/debug/formatter.h (revision 204819)
+++ include/debug/formatter.h (working copy)
@@ -116,7 +116,12 @@
__msg_valid_load_factor,
// others
__msg_equal_allocs,
- __msg_insert_range_from_self
+ __msg_insert_range_from_self,
+ // algos checks
+ __msg_forbidden_mem,
+ __msg_ranges_overlap,
+ __msg_copy_bad,
+ __msg_copy_backward_bad
};
class _Error_formatter
Index: include/debug/functions.h
===================================================================
--- include/debug/functions.h (revision 204819)
+++ include/debug/functions.h (working copy)
@@ -175,6 +175,34 @@
return __first;
}
+ /* Arbitrary pointer type, assume they can compare */
+ inline bool
+ __can_compare_aux(const void*, const void*)
+ { return true; }
+
+ /* Try to find out if iterators can be compared each other. */
+ template<typename _InputIterator>
+ inline bool
+ __can_compare(const _InputIterator& __first, const _InputIterator& __last)
+ { return __can_compare_aux(&__first, &__last); }
+
+ /** Check if iterators are pointing to the same bucket when using unordered
+ * containers local iterators.
+ * Assume it is correct for arbitrary iterators because we can't say
+ * otherwise.
+ **/
+ template<typename _InputIterator>
+ inline bool
+ __same_bucket(const _InputIterator&, const _InputIterator&)
+ { return true; }
+
+ /* Safe local iterators know their bucket. */
+ template<typename _Iterator, typename _Sequence>
+ inline bool
+ __same_bucket(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
+ const _Safe_local_iterator<_Iterator, _Sequence>& __last)
+ { return __first._M_in_same_bucket(__last); }
+
#if __cplusplus >= 201103L
// Default implementation.
template<typename _Iterator, typename _Sequence>
@@ -294,6 +322,119 @@
return __foreign_iterator_aux(__it, __other, _Integral());
}
+ /* Gets the underlying unsafe iterator if any */
+ template<typename _Iterator>
+ inline _Iterator
+ __unsafe(_Iterator __it)
+ { return __it; }
+
+ template<typename _Iterator, typename _Sequence>
+ inline _Iterator
+ __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
+ { return __it.base(); }
+
+ template<typename _Iterator, typename _Sequence>
+ inline _Iterator
+ __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
+ { return __it.base(); }
+
+ /* Fallback assume that ranges doesn't overlap. */
+ template<typename _IIte1, typename _IIte2>
+ inline bool
+ __overlap(_IIte1, _IIte1, _IIte2)
+ { return false; }
+
+ template<typename _Ite>
+ inline bool
+ __overlap_aux(const _Ite&, const _Ite&, const _Ite&,
+ std::input_iterator_tag)
+ { return false; }
+
+ template<typename _Ite>
+ inline bool
+ __overlap_aux(const _Ite& __first1, const _Ite& __last1,
+ const _Ite& __first2,
+ std::random_access_iterator_tag)
+ {
+ return __first2 < __last1
+ && (__first2 + (__last1 - __first1) >= __first1);
+ }
+
+ /* Overload when all iterators are of the same type. */
+ template<typename _Ite>
+ inline bool
+ __overlap(const _Ite& __first1, const _Ite& __last1,
+ const _Ite& __first2)
+ {
+ return __overlap_aux(__unsafe(__first1), __unsafe(__last1),
+ __unsafe(__first2),
+ std::__iterator_category(__first1));
+ }
+
+ /* Check that it is safe to copy [first, last) to result. */
+ // Fallback overload, assume it is safe.
+ template<typename _IIte, typename _OIte>
+ inline bool
+ __check_copy(_IIte, _IIte, _OIte)
+ { return true; }
+
+ // Check is done only if all iterators are of the same type and are random
+ // ones.
+ template<typename _Ite>
+ inline bool
+ __check_copy_aux(_Ite __first, _Ite __last, _Ite __result,
+ std::random_access_iterator_tag)
+ { return __result < __first || __last <= __result; }
+
+ // Can't say.
+ template<typename _Ite>
+ inline bool
+ __check_copy_aux(_Ite, _Ite, _Ite,
+ std::input_iterator_tag)
+ { return true; }
+
+ // Overload when all iterators are of the same type.
+ template<typename _Ite>
+ inline bool
+ __check_copy(_Ite __first, _Ite __last, _Ite __result)
+ {
+ return __check_copy_aux(__unsafe(__first), __unsafe(__last),
+ __unsafe(__result),
+ std::__iterator_category(__first));
+ }
+
+ /* Check that it is safe to copy (first, last] to result backward. */
+ // Fallback overload, assume it is safe.
+ template<typename _IIte, typename _OIte>
+ inline bool
+ __check_copy_backward(_IIte, _IIte, _OIte)
+ { return true; }
+
+ // Check is done only if all iterators are of the same type and are random
+ // ones.
+ template<typename _Ite>
+ inline bool
+ __check_copy_backward_aux(_Ite __first, _Ite __last, _Ite __result,
+ std::random_access_iterator_tag)
+ { return __result <= __first || __last < __result; }
+
+ // Can't say.
+ template<typename _Ite>
+ inline bool
+ __check_copy_backward_aux(_Ite, _Ite, _Ite,
+ std::input_iterator_tag)
+ { return true; }
+
+ // Overload when all iterators are of the same type.
+ template<typename _Ite>
+ inline bool
+ __check_copy_backward(_Ite __first, _Ite __last, _Ite __result)
+ {
+ return __check_copy_backward_aux(__unsafe(__first), __unsafe(__last),
+ __unsafe(__result),
+ std::__iterator_category(__first));
+ }
+
/** Checks that __s is non-NULL or __n == 0, and then returns __s. */
template<typename _CharT, typename _Integer>
inline const _CharT*
@@ -557,6 +698,29 @@
inline typename _Siter_base<_Iterator>::iterator_type
__base(_Iterator __it)
{ return _Siter_base<_Iterator>::_S_base(__it); }
+
+ template<typename _Iterator>
+ inline _Iterator
+ __safe(_Iterator, _Iterator __it)
+ { return __it; }
+
+ template<typename _Iterator, typename _Sequence>
+ inline _Safe_iterator<_Iterator, _Sequence>
+ __safe(const _Safe_iterator<_Iterator, _Sequence>& __safe_it,
+ _Iterator __it)
+ {
+ return _Safe_iterator<_Iterator, _Sequence>(__it,
+ __safe_it._M_get_sequence());
+ }
+
+ template<typename _Iterator, typename _Sequence>
+ inline _Safe_local_iterator<_Iterator, _Sequence>
+ __safe(const _Safe_local_iterator<_Iterator, _Sequence>& __safe_it,
+ _Iterator __it)
+ {
+ return _Safe_local_iterator<_Iterator, _Sequence>(__it,
+ __safe_it._M_get_sequence());
+ }
} // namespace __gnu_debug
#endif
Index: include/debug/forward_list
===================================================================
--- include/debug/forward_list (revision 204819)
+++ include/debug/forward_list (working copy)
@@ -806,6 +806,24 @@
std::__debug::forward_list<_Tp, _Alloc> >
{ enum { __value = 1 }; };
#endif
+
+ template<class _Tp, class _Alloc>
+ struct _Size_helper<std::__debug::forward_list<_Tp, _Alloc> >
+ {
+ typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence;
+
+ template<typename _Iterator>
+ static std::pair<typename _Diff_type_helper<_Iterator>::_Type,
+ _Distance_precision>
+ _S_size(const _Safe_iterator<_Iterator, _Sequence>& __it)
+ {
+ typedef typename _Diff_type_helper<_Iterator>::_Type _DiffType;
+ if (__it._M_get_sequence()->empty())
+ return std::make_pair(_DiffType(0), __dp_exact);
+ else
+ return std::make_pair(_DiffType(1), __dp_sign);
+ }
+ };
}
#endif
Index: include/std/algorithm
===================================================================
--- include/std/algorithm (revision 204819)
+++ include/std/algorithm (working copy)
@@ -61,6 +61,10 @@
#include <bits/stl_algobase.h>
#include <bits/stl_algo.h>
+#ifdef _GLIBCXX_DEBUG
+# include <debug/algorithm>
+#endif
+
#ifdef _GLIBCXX_PARALLEL
# include <parallel/algorithm>
#endif
Index: include/std/numeric
===================================================================
--- include/std/numeric (revision 204819)
+++ include/std/numeric (working copy)
@@ -61,6 +61,10 @@
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_numeric.h>
+#ifdef _GLIBCXX_DEBUG
+# include <debug/numeric>
+#endif
+
#ifdef _GLIBCXX_PARALLEL
# include <parallel/numeric>
#endif
Index: include/parallel/algorithmfwd.h
===================================================================
--- include/parallel/algorithmfwd.h (revision 204819)
+++ include/parallel/algorithmfwd.h (working copy)
@@ -121,6 +121,36 @@
// algobase.h
template<typename _IIter1, typename _IIter2>
+ _IIter2
+ swap_ranges(_IIter1, _IIter1, _IIter2);
+
+ template<typename _II, typename _OI>
+ _OI
+ copy(_II, _II, _OI);
+
+ template<typename _BI1, typename _BI2>
+ _BI2
+ copy_backward(_BI1, _BI1, _BI2)
+
+#if __cplusplus >= 201103L
+ template<typename _II, typename _OI>
+ _OI
+ move(_II, _II, _OI);
+
+ template<typename _BI1, typename _BI2>
+ _BI2
+ move_backward(_BI1, _BI1, _BI2)
+#endif
+
+ template<typename _FI, typename _Tp>
+ void
+ fill(_FI, _FI, const _Tp&);
+
+ template<typename _OI, typename _Size, typename _Tp>
+ _OI
+ fill_n(_OI, _Size, const _Tp&);
+
+ template<typename _IIter1, typename _IIter2>
bool
equal(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
Index: include/parallel/algobase.h
===================================================================
--- include/parallel/algobase.h (revision 204819)
+++ include/parallel/algobase.h (working copy)
@@ -46,6 +46,46 @@
{
namespace __parallel
{
+ // No parallel version for those algos.
+ template<typename _IIter1, typename _IIter2>
+ _IIter2
+ swap_ranges(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2)
+ { return _GLIBCXX_STD_A::swap_ranges(__first1, __last1, __first2); }
+
+ template<typename _II, typename _OI>
+ inline _OI
+ copy(_II __first, _II __last, _OI __result)
+ { return _GLIBCXX_STD_A::copy(__first, __last, __result); }
+
+#if __cplusplus >= 201103L
+ template<typename _II, typename _OI>
+ inline _OI
+ move(_II __first, _II __last, _OI __result)
+ { return _GLIBCXX_STD_A::move(__first, __last, __result); }
+#endif
+
+ template<typename _BI1, typename _BI2>
+ inline _BI2
+ copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
+ { return _GLIBCXX_STD_A::copy_backward(__first, __last, __result); }
+
+#if __cplusplus >= 201103L
+ template<typename _BI1, typename _BI2>
+ inline _BI2
+ move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
+ { return _GLIBCXX_STD_A::move_backward(__first, __last, __result); }
+#endif
+
+ template<typename _FI, typename _Tp>
+ inline void
+ fill(_FI __first, _FI __last, const _Tp& __value)
+ { _GLIBCXX_STD_A::fill(__first, __last, __value); }
+
+ template<typename _OI, typename _Size, typename _Tp>
+ inline _OI
+ fill_n(_OI __first, _Size __n, const _Tp& __value)
+ { return _GLIBCXX_STD_A::fill_n(__first, __n, __value); }
+
// NB: equal and lexicographical_compare require mismatch.
// Sequential fallback
Index: include/bits/c++config
===================================================================
--- include/bits/c++config (revision 204819)
+++ include/bits/c++config (working copy)
@@ -149,6 +149,7 @@
namespace __parallel { }
namespace __profile { }
namespace __cxx1998 { }
+ namespace __cxx1998_a { }
namespace __detail { }
@@ -251,6 +252,13 @@
#endif
}
+ namespace __cxx1998_a
+ {
+#if _GLIBCXX_INLINE_VERSION
+ inline namespace __7 { }
+#endif
+ }
+
// Inline namespace for debug mode.
# ifdef _GLIBCXX_DEBUG
inline namespace __debug { }
@@ -305,8 +313,8 @@
# define _GLIBCXX_EXTERN_TEMPLATE -1
#endif
-#ifdef _GLIBCXX_PARALLEL
-# define _GLIBCXX_STD_A __cxx1998
+#if defined(_GLIBCXX_DEBUG) || defined(_GLIBCXX_PARALLEL)
+# define _GLIBCXX_STD_A __cxx1998_a
# define _GLIBCXX_BEGIN_NAMESPACE_ALGO \
namespace _GLIBCXX_STD_A { _GLIBCXX_BEGIN_NAMESPACE_VERSION
# define _GLIBCXX_END_NAMESPACE_ALGO \
Index: include/bits/algorithmfwd.h
===================================================================
--- include/bits/algorithmfwd.h (revision 204819)
+++ include/bits/algorithmfwd.h (working copy)
@@ -208,6 +208,10 @@
bool
binary_search(_FIter, _FIter, const _Tp&, _Compare);
+_GLIBCXX_END_NAMESPACE_VERSION
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
template<typename _IIter, typename _OIter>
_OIter
copy(_IIter, _IIter, _OIter);
@@ -216,6 +220,10 @@
_BIter2
copy_backward(_BIter1, _BIter1, _BIter2);
+_GLIBCXX_END_NAMESPACE_ALGO
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
#if __cplusplus >= 201103L
template<typename _IIter, typename _OIter, typename _Predicate>
_OIter
@@ -237,6 +245,10 @@
pair<_FIter, _FIter>
equal_range(_FIter, _FIter, const _Tp&, _Compare);
+_GLIBCXX_END_NAMESPACE_VERSION
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
template<typename _FIter, typename _Tp>
void
fill(_FIter, _FIter, const _Tp&);
@@ -245,6 +257,10 @@
_OIter
fill_n(_OIter, _Size, const _Tp&);
+_GLIBCXX_END_NAMESPACE_ALGO
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
// find
template<typename _FIter1, typename _FIter2>
@@ -566,10 +582,18 @@
#endif
;
+_GLIBCXX_END_NAMESPACE_VERSION
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
template<typename _FIter1, typename _FIter2>
_FIter2
swap_ranges(_FIter1, _FIter1, _FIter2);
+_GLIBCXX_END_NAMESPACE_ALGO
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
// transform
template<typename _FIter>
@@ -818,6 +842,10 @@
_GLIBCXX_END_NAMESPACE_ALGO
} // namespace std
+#ifdef _GLIBCXX_DEBUG
+# include <debug/algorithmfwd.h>
+#endif
+
#ifdef _GLIBCXX_PARALLEL
# include <parallel/algorithmfwd.h>
#endif
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h (revision 204819)
+++ include/bits/stl_algobase.h (working copy)
@@ -66,7 +66,6 @@
#include <bits/stl_iterator_base_funcs.h>
#include <bits/stl_iterator.h>
#include <bits/concept_check.h>
-#include <debug/debug.h>
#include <bits/move.h> // For std::swap and _GLIBCXX_MOVE
#include <bits/predefined_ops.h>
@@ -149,6 +148,10 @@
#endif
}
+_GLIBCXX_END_NAMESPACE_VERSION
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
/**
* @brief Swap the elements of two sequences.
* @ingroup mutating_algorithms
@@ -171,13 +174,16 @@
_ForwardIterator1>)
__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
_ForwardIterator2>)
- __glibcxx_requires_valid_range(__first1, __last1);
for (; __first1 != __last1; ++__first1, ++__first2)
std::iter_swap(__first1, __first2);
return __first2;
}
+_GLIBCXX_END_NAMESPACE_ALGO
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
/**
* @brief This does what you think it does.
* @ingroup sorting_algorithms
@@ -434,6 +440,10 @@
std::__niter_base(__result)));
}
+_GLIBCXX_END_NAMESPACE_VERSION
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
/**
* @brief Copies the range [first,last) into result.
* @ingroup mutating_algorithms
@@ -459,7 +469,6 @@
__glibcxx_function_requires(_InputIteratorConcept<_II>)
__glibcxx_function_requires(_OutputIteratorConcept<_OI,
typename iterator_traits<_II>::value_type>)
- __glibcxx_requires_valid_range(__first, __last);
return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
(std::__miter_base(__first), std::__miter_base(__last),
@@ -492,7 +501,6 @@
__glibcxx_function_requires(_InputIteratorConcept<_II>)
__glibcxx_function_requires(_OutputIteratorConcept<_OI,
typename iterator_traits<_II>::value_type>)
- __glibcxx_requires_valid_range(__first, __last);
return std::__copy_move_a2<true>(std::__miter_base(__first),
std::__miter_base(__last), __result);
@@ -503,6 +511,10 @@
#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
#endif
+_GLIBCXX_END_NAMESPACE_ALGO
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
template<bool, bool, typename>
struct __copy_move_backward
{
@@ -607,6 +619,10 @@
std::__niter_base(__result)));
}
+_GLIBCXX_END_NAMESPACE_VERSION
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
/**
* @brief Copies the range [first,last) into result.
* @ingroup mutating_algorithms
@@ -635,7 +651,6 @@
__glibcxx_function_requires(_ConvertibleConcept<
typename iterator_traits<_BI1>::value_type,
typename iterator_traits<_BI2>::value_type>)
- __glibcxx_requires_valid_range(__first, __last);
return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
(std::__miter_base(__first), std::__miter_base(__last),
@@ -671,7 +686,6 @@
__glibcxx_function_requires(_ConvertibleConcept<
typename iterator_traits<_BI1>::value_type,
typename iterator_traits<_BI2>::value_type>)
- __glibcxx_requires_valid_range(__first, __last);
return std::__copy_move_backward_a2<true>(std::__miter_base(__first),
std::__miter_base(__last),
@@ -683,6 +697,10 @@
#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
#endif
+_GLIBCXX_END_NAMESPACE_ALGO
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
template<typename _ForwardIterator, typename _Tp>
inline typename
__gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
@@ -715,6 +733,10 @@
__last - __first);
}
+_GLIBCXX_END_NAMESPACE_VERSION
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
/**
* @brief Fills the range [first,last) with copies of value.
* @ingroup mutating_algorithms
@@ -734,12 +756,15 @@
// concept requirements
__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
_ForwardIterator>)
- __glibcxx_requires_valid_range(__first, __last);
std::__fill_a(std::__niter_base(__first), std::__niter_base(__last),
__value);
}
+_GLIBCXX_END_NAMESPACE_ALGO
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
template<typename _OutputIterator, typename _Size, typename _Tp>
inline typename
__gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
@@ -772,6 +797,10 @@
return __first + __n;
}
+_GLIBCXX_END_NAMESPACE_VERSION
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
/**
* @brief Fills the range [first,first+n) with copies of value.
* @ingroup mutating_algorithms
@@ -797,6 +826,10 @@
return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
}
+_GLIBCXX_END_NAMESPACE_ALGO
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
template<bool _BoolType>
struct __equal
{
@@ -1052,7 +1085,6 @@
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_II1>::value_type,
typename iterator_traits<_II2>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
return std::__equal_aux(std::__niter_base(__first1),
std::__niter_base(__last1),
@@ -1082,7 +1114,6 @@
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
__glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
- __glibcxx_requires_valid_range(__first1, __last1);
for (; __first1 != __last1; ++__first1, ++__first2)
if (!bool(__binary_pred(*__first1, *__first2)))
@@ -1114,8 +1145,6 @@
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_II1>::value_type,
typename iterator_traits<_II2>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_valid_range(__first2, __last2);
using _RATag = random_access_iterator_tag;
using _Cat1 = typename iterator_traits<_II1>::iterator_category;
@@ -1160,8 +1189,6 @@
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
__glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
- __glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_valid_range(__first2, __last2);
using _RATag = random_access_iterator_tag;
using _Cat1 = typename iterator_traits<_IIter1>::iterator_category;
@@ -1213,8 +1240,6 @@
__glibcxx_function_requires(_InputIteratorConcept<_II2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
- __glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_valid_range(__first2, __last2);
return std::__lexicographical_compare_aux(std::__niter_base(__first1),
std::__niter_base(__last1),
@@ -1243,8 +1268,6 @@
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_II1>)
__glibcxx_function_requires(_InputIteratorConcept<_II2>)
- __glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_valid_range(__first2, __last2);
return std::__lexicographical_compare_impl
(__first1, __last1, __first2, __last2,
@@ -1289,7 +1312,6 @@
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator1>::value_type,
typename iterator_traits<_InputIterator2>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
__gnu_cxx::__ops::__iter_equal_to_iter());
@@ -1320,7 +1342,6 @@
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
- __glibcxx_requires_valid_range(__first1, __last1);
return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
@@ -1369,8 +1390,6 @@
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator1>::value_type,
typename iterator_traits<_InputIterator2>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_valid_range(__first2, __last2);
return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
__gnu_cxx::__ops::__iter_equal_to_iter());
@@ -1403,8 +1422,6 @@
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
- __glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_valid_range(__first2, __last2);
return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
@@ -1421,4 +1438,8 @@
# include <parallel/algobase.h>
#endif
+#ifdef _GLIBCXX_DEBUG
+# include <debug/algobase.h>
#endif
+
+#endif
Index: include/Makefile.am
===================================================================
--- include/Makefile.am (revision 204819)
+++ include/Makefile.am (working copy)
@@ -717,6 +717,10 @@
debug_srcdir = ${glibcxx_srcdir}/include/debug
debug_builddir = ./debug
debug_headers = \
+ ${debug_srcdir}/algo.h \
+ ${debug_srcdir}/algobase.h \
+ ${debug_srcdir}/algorithm \
+ ${debug_srcdir}/algorithmfwd.h \
${debug_srcdir}/array \
${debug_srcdir}/bitset \
${debug_srcdir}/debug.h \
@@ -730,6 +734,7 @@
${debug_srcdir}/map.h \
${debug_srcdir}/multimap.h \
${debug_srcdir}/multiset.h \
+ ${debug_srcdir}/numeric \
${debug_srcdir}/safe_base.h \
${debug_srcdir}/safe_iterator.h \
${debug_srcdir}/safe_iterator.tcc \