URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [debug/] [functions.h] - Blame information for rev 35

Details | Compare with Previous | View Log


// Debugging support implementation -*- C++ -*-
 
// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
// 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/functions.h
 *  This file is a GNU debug extension to the Standard C++ Library.
 */
 
#ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
#define _GLIBCXX_DEBUG_FUNCTIONS_H 1
 
#include <bits/c++config.h>
#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and
                                          // _Iter_base
#include <bits/cpp_type_traits.h>         // for __is_integer
#include <debug/formatter.h>
 
namespace __gnu_debug
{
  template<typename _Iterator, typename _Sequence>
    class _Safe_iterator;
 
  // An arbitrary iterator pointer is not singular.
  inline bool
  __check_singular_aux(const void*) { return false; }
 
  // We may have an iterator that derives from _Safe_iterator_base but isn't
  // a _Safe_iterator.
  template<typename _Iterator>
    inline bool
    __check_singular(_Iterator& __x)
    { return __check_singular_aux(&__x); }
 
  /** Non-NULL pointers are nonsingular. */
  template<typename _Tp>
    inline bool
    __check_singular(const _Tp* __ptr)
    { return __ptr == 0; }
 
  /** Safe iterators know if they are singular. */
  template<typename _Iterator, typename _Sequence>
    inline bool
    __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x)
    { return __x._M_singular(); }
 
  /** Assume that some arbitrary iterator is dereferenceable, because we
      can't prove that it isn't. */
  template<typename _Iterator>
    inline bool
    __check_dereferenceable(_Iterator&)
    { return true; }
 
  /** Non-NULL pointers are dereferenceable. */
  template<typename _Tp>
    inline bool
    __check_dereferenceable(const _Tp* __ptr)
    { return __ptr; }
 
  /** Safe iterators know if they are singular. */
  template<typename _Iterator, typename _Sequence>
    inline bool
    __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
    { return __x._M_dereferenceable(); }
 
  /** If the distance between two random access iterators is
   *  nonnegative, assume the range is valid.
  */
  template<typename _RandomAccessIterator>
    inline bool
    __valid_range_aux2(const _RandomAccessIterator& __first,
                       const _RandomAccessIterator& __last,
                       std::random_access_iterator_tag)
    { return __last - __first >= 0; }
 
  /** Can't test for a valid range with input iterators, because
   *  iteration may be destructive. So we just assume that the range
   *  is valid.
  */
  template<typename _InputIterator>
    inline bool
    __valid_range_aux2(const _InputIterator&, const _InputIterator&,
                       std::input_iterator_tag)
    { return true; }
 
  /** We say that integral types for a valid range, and defer to other
   *  routines to realize what to do with integral types instead of
   *  iterators.
  */
  template<typename _Integral>
    inline bool
    __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
    { return true; }
 
  /** We have iterators, so figure out what kind of iterators that are
   *  to see if we can check the range ahead of time.
  */
  template<typename _InputIterator>
    inline bool
    __valid_range_aux(const _InputIterator& __first,
                      const _InputIterator& __last, std::__false_type)
  { return __valid_range_aux2(__first, __last,
                              std::__iterator_category(__first)); }
 
  /** Don't know what these iterators are, or if they are even
   *  iterators (we may get an integral type for InputIterator), so
   *  see if they are integral and pass them on to the next phase
   *  otherwise.
  */
  template<typename _InputIterator>
    inline bool
    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
    {
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      return __valid_range_aux(__first, __last, _Integral());
    }
 
  /** Safe iterators know how to check if they form a valid range. */
  template<typename _Iterator, typename _Sequence>
    inline bool
    __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
                  const _Safe_iterator<_Iterator, _Sequence>& __last)
    { return __first._M_valid_range(__last); }
 
  /** Safe local iterators know how to check if they form a valid range. */
  template<typename _Iterator, typename _Sequence>
    inline bool
    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
                  const _Safe_local_iterator<_Iterator, _Sequence>& __last)
    { return __first._M_valid_range(__last); }
 
  /* Checks that [first, last) is a valid range, and then returns
   * __first. This routine is useful when we can't use a separate
   * assertion statement because, e.g., we are in a constructor.
  */
  template<typename _InputIterator>
    inline _InputIterator
    __check_valid_range(const _InputIterator& __first,
                        const _InputIterator& __last
                        __attribute__((__unused__)))
    {
      __glibcxx_check_valid_range(__first, __last);
      return __first;
    }
 
  /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
  template<typename _CharT, typename _Integer>
    inline const _CharT*
    __check_string(const _CharT* __s,
                   const _Integer& __n __attribute__((__unused__)))
    {
#ifdef _GLIBCXX_DEBUG_PEDANTIC
      __glibcxx_assert(__s != 0 || __n == 0);
#endif
      return __s;
    }
 
  /** Checks that __s is non-NULL and then returns __s. */
  template<typename _CharT>
    inline const _CharT*
    __check_string(const _CharT* __s)
    {
#ifdef _GLIBCXX_DEBUG_PEDANTIC
      __glibcxx_assert(__s != 0);
#endif
      return __s;
    }
 
  // Can't check if an input iterator sequence is sorted, because we
  // can't step through the sequence.
  template<typename _InputIterator>
    inline bool
    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
                       std::input_iterator_tag)
    { return true; }
 
  // Can verify if a forward iterator sequence is in fact sorted using
  // std::__is_sorted
  template<typename _ForwardIterator>
    inline bool
    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
                       std::forward_iterator_tag)
    {
      if (__first == __last)
        return true;
 
      _ForwardIterator __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next)
        if (*__next < *__first)
          return false;
 
      return true;
    }
 
  // For performance reason, as the iterator range has been validated, check on
  // random access safe iterators is done using the base iterator.
  template<typename _Iterator, typename _Sequence>
    inline bool
    __check_sorted_aux(const _Safe_iterator<_Iterator, _Sequence>& __first,
                       const _Safe_iterator<_Iterator, _Sequence>& __last,
                       std::random_access_iterator_tag __tag)
  { return __check_sorted_aux(__first.base(), __last.base(), __tag); }
 
  // Can't check if an input iterator sequence is sorted, because we can't step
  // through the sequence.
  template<typename _InputIterator, typename _Predicate>
    inline bool
    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
                       _Predicate, std::input_iterator_tag)
    { return true; }
 
  // Can verify if a forward iterator sequence is in fact sorted using
  // std::__is_sorted
  template<typename _ForwardIterator, typename _Predicate>
    inline bool
    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
                       _Predicate __pred, std::forward_iterator_tag)
    {
      if (__first == __last)
        return true;
 
      _ForwardIterator __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next)
        if (__pred(*__next, *__first))
          return false;
 
      return true;
    }
 
  // For performance reason, as the iterator range has been validated, check on
  // random access safe iterators is done using the base iterator.
  template<typename _Iterator, typename _Sequence,
           typename _Predicate>
    inline bool
    __check_sorted_aux(const _Safe_iterator<_Iterator, _Sequence>& __first,
                       const _Safe_iterator<_Iterator, _Sequence>& __last,
                       _Predicate __pred,
                       std::random_access_iterator_tag __tag)
  { return __check_sorted_aux(__first.base(), __last.base(), __pred, __tag); }
 
  // Determine if a sequence is sorted.
  template<typename _InputIterator>
    inline bool
    __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
    {
      // Verify that the < operator for elements in the sequence is a
      // StrictWeakOrdering by checking that it is irreflexive.
      __glibcxx_assert(__first == __last || !(*__first < *__first));
 
      return __check_sorted_aux(__first, __last,
                                std::__iterator_category(__first));
    }
 
  template<typename _InputIterator, typename _Predicate>
    inline bool
    __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
                   _Predicate __pred)
    {
      // Verify that the predicate is StrictWeakOrdering by checking that it
      // is irreflexive.
      __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
 
      return __check_sorted_aux(__first, __last, __pred,
                                std::__iterator_category(__first));
    }
 
  template<typename _InputIterator>
    inline bool
    __check_sorted_set_aux(const _InputIterator& __first,
                           const _InputIterator& __last,
                           std::__true_type)
    { return __check_sorted(__first, __last); }
 
  template<typename _InputIterator>
    inline bool
    __check_sorted_set_aux(const _InputIterator&,
                           const _InputIterator&,
                           std::__false_type)
    { return true; }
 
  template<typename _InputIterator, typename _Predicate>
    inline bool
    __check_sorted_set_aux(const _InputIterator& __first,
                           const _InputIterator& __last,
                           _Predicate __pred, std::__true_type)
    { return __check_sorted(__first, __last, __pred); }
 
  template<typename _InputIterator, typename _Predicate>
    inline bool
    __check_sorted_set_aux(const _InputIterator&,
                           const _InputIterator&, _Predicate,
                           std::__false_type)
    { return true; }
 
  // ... special variant used in std::merge, std::includes, std::set_*.
  template<typename _InputIterator1, typename _InputIterator2>
    inline bool
    __check_sorted_set(const _InputIterator1& __first,
                       const _InputIterator1& __last,
                       const _InputIterator2&)
    {
      typedef typename std::iterator_traits<_InputIterator1>::value_type
        _ValueType1;
      typedef typename std::iterator_traits<_InputIterator2>::value_type
        _ValueType2;
 
      typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
        _SameType;
      return __check_sorted_set_aux(__first, __last, _SameType());
    }
 
  template<typename _InputIterator1, typename _InputIterator2,
           typename _Predicate>
    inline bool
    __check_sorted_set(const _InputIterator1& __first,
                       const _InputIterator1& __last,
                       const _InputIterator2&, _Predicate __pred)
    {
      typedef typename std::iterator_traits<_InputIterator1>::value_type
        _ValueType1;
      typedef typename std::iterator_traits<_InputIterator2>::value_type
        _ValueType2;
 
      typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
        _SameType;
      return __check_sorted_set_aux(__first, __last, __pred, _SameType());
   }
 
  template<typename _ForwardIterator, typename _Tp>
    inline bool
  __check_partitioned_lower_aux(_ForwardIterator __first,
                                _ForwardIterator __last, const _Tp& __value,
                                std::forward_iterator_tag)
    {
      while (__first != __last && *__first < __value)
        ++__first;
      if (__first != __last)
        {
          ++__first;
          while (__first != __last && !(*__first < __value))
            ++__first;
        }
      return __first == __last;
    }
 
  // For performance reason, as the iterator range has been validated, check on
  // random access safe iterators is done using the base iterator.
  template<typename _Iterator, typename _Sequence, typename _Tp>
    inline bool
    __check_partitioned_lower_aux(
                        const _Safe_iterator<_Iterator, _Sequence>& __first,
                        const _Safe_iterator<_Iterator, _Sequence>& __last,
                        const _Tp& __value,
                        std::random_access_iterator_tag __tag)
    {
      return __check_partitioned_lower_aux(__first.base(), __last.base(),
                                           __value, __tag);
    }
 
  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 270. Binary search requirements overly strict
  // Determine if a sequence is partitioned w.r.t. this element.
  template<typename _ForwardIterator, typename _Tp>
    inline bool
    __check_partitioned_lower(_ForwardIterator __first,
                              _ForwardIterator __last, const _Tp& __value)
    {
      return __check_partitioned_lower_aux(__first, __last, __value,
                                           std::__iterator_category(__first));
    }
 
  template<typename _ForwardIterator, typename _Tp>
    inline bool
    __check_partitioned_upper_aux(_ForwardIterator __first,
                                  _ForwardIterator __last, const _Tp& __value,
                                  std::forward_iterator_tag)
    {
      while (__first != __last && !(__value < *__first))
        ++__first;
      if (__first != __last)
        {
          ++__first;
          while (__first != __last && __value < *__first)
            ++__first;
        }
      return __first == __last;
    }
 
  // For performance reason, as the iterator range has been validated, check on
  // random access safe iterators is done using the base iterator.
  template<typename _Iterator, typename _Sequence, typename _Tp>
    inline bool
    __check_partitioned_upper_aux(
                        const _Safe_iterator<_Iterator, _Sequence>& __first,
                        const _Safe_iterator<_Iterator, _Sequence>& __last,
                        const _Tp& __value,
                        std::random_access_iterator_tag __tag)
    {
      return __check_partitioned_upper_aux(__first.base(), __last.base(),
                                           __value, __tag);
    }
 
  template<typename _ForwardIterator, typename _Tp>
    inline bool
    __check_partitioned_upper(_ForwardIterator __first,
                              _ForwardIterator __last, const _Tp& __value)
    {
      return __check_partitioned_upper_aux(__first, __last, __value,
                                           std::__iterator_category(__first));
    }
 
  template<typename _ForwardIterator, typename _Tp, typename _Pred>
    inline bool
    __check_partitioned_lower_aux(_ForwardIterator __first,
                                  _ForwardIterator __last, const _Tp& __value,
                                  _Pred __pred,
                                  std::forward_iterator_tag)
    {
      while (__first != __last && bool(__pred(*__first, __value)))
        ++__first;
      if (__first != __last)
        {
          ++__first;
          while (__first != __last && !bool(__pred(*__first, __value)))
            ++__first;
        }
      return __first == __last;
    }
 
  // For performance reason, as the iterator range has been validated, check on
  // random access safe iterators is done using the base iterator.
  template<typename _Iterator, typename _Sequence,
           typename _Tp, typename _Pred>
    inline bool
    __check_partitioned_lower_aux(
                        const _Safe_iterator<_Iterator, _Sequence>& __first,
                        const _Safe_iterator<_Iterator, _Sequence>& __last,
                        const _Tp& __value, _Pred __pred,
                        std::random_access_iterator_tag __tag)
    {
      return __check_partitioned_lower_aux(__first.base(), __last.base(),
                                           __value, __pred, __tag);
    }
 
  // Determine if a sequence is partitioned w.r.t. this element.
  template<typename _ForwardIterator, typename _Tp, typename _Pred>
    inline bool
    __check_partitioned_lower(_ForwardIterator __first,
                              _ForwardIterator __last, const _Tp& __value,
                              _Pred __pred)
    {
      return __check_partitioned_lower_aux(__first, __last, __value, __pred,
                                           std::__iterator_category(__first));
    }
 
  template<typename _ForwardIterator, typename _Tp, typename _Pred>
    inline bool
    __check_partitioned_upper_aux(_ForwardIterator __first,
                                  _ForwardIterator __last, const _Tp& __value,
                                  _Pred __pred,
                                  std::forward_iterator_tag)
    {
      while (__first != __last && !bool(__pred(__value, *__first)))
        ++__first;
      if (__first != __last)
        {
          ++__first;
          while (__first != __last && bool(__pred(__value, *__first)))
            ++__first;
        }
      return __first == __last;
    }
 
  // For performance reason, as the iterator range has been validated, check on
  // random access safe iterators is done using the base iterator.
  template<typename _Iterator, typename _Sequence,
           typename _Tp, typename _Pred>
    inline bool
    __check_partitioned_upper_aux(
                        const _Safe_iterator<_Iterator, _Sequence>& __first,
                        const _Safe_iterator<_Iterator, _Sequence>& __last,
                        const _Tp& __value, _Pred __pred,
                        std::random_access_iterator_tag __tag)
    {
      return __check_partitioned_upper_aux(__first.base(), __last.base(),
                                           __value, __pred, __tag);
    }
 
  template<typename _ForwardIterator, typename _Tp, typename _Pred>
    inline bool
    __check_partitioned_upper(_ForwardIterator __first,
                              _ForwardIterator __last, const _Tp& __value,
                              _Pred __pred)
    {
      return __check_partitioned_upper_aux(__first, __last, __value, __pred,
                                           std::__iterator_category(__first));
    }
 
  // Helper struct to detect random access safe iterators.
  template<typename _Iterator>
    struct __is_safe_random_iterator
    {
      enum { __value = 0 };
      typedef std::__false_type __type;
    };
 
  template<typename _Iterator, typename _Sequence>
    struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
    : std::__are_same<std::random_access_iterator_tag,
                      typename std::iterator_traits<_Iterator>::
                      iterator_category>
    { };
 
  template<typename _Iterator>
    struct _Siter_base
    : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
    { };
 
  /** Helper function to extract base iterator of random access safe iterator
      in order to reduce performance impact of debug mode.  Limited to random
      access iterator because it is the only category for which it is possible
      to check for correct iterators order in the __valid_range function
      thanks to the < operator.
  */
  template<typename _Iterator>
    inline typename _Siter_base<_Iterator>::iterator_type
    __base(_Iterator __it)
    { return _Siter_base<_Iterator>::_S_base(__it); }
} // namespace __gnu_debug
 
#endif

Browse

Tools

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [debug/] [functions.h] - Blame information for rev 35

Line No.	Rev	Author	Line
1	35	ultra_embe	`// Debugging support implementation -- C++ --`
2
3			`// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011`
4			`// Free Software Foundation, Inc.`
5			`//`
6			`// This file is part of the GNU ISO C++ Library. This library is free`
7			`// software; you can redistribute it and/or modify it under the`
8			`// terms of the GNU General Public License as published by the`
9			`// Free Software Foundation; either version 3, or (at your option)`
10			`// any later version.`
11
12			`// This library is distributed in the hope that it will be useful,`
13			`// but WITHOUT ANY WARRANTY; without even the implied warranty of`
14			`// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the`
15			`// GNU General Public License for more details.`
16
17			`// Under Section 7 of GPL version 3, you are granted additional`
18			`// permissions described in the GCC Runtime Library Exception, version`
19			`// 3.1, as published by the Free Software Foundation.`
20
21			`// You should have received a copy of the GNU General Public License and`
22			`// a copy of the GCC Runtime Library Exception along with this program;`
23			`// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see`
24			`// <http://www.gnu.org/licenses/>.`
25
26			`/** @file debug/functions.h`
27			`* This file is a GNU debug extension to the Standard C++ Library.`
28			`*/`
29
30			`#ifndef _GLIBCXX_DEBUG_FUNCTIONS_H`
31			`#define _GLIBCXX_DEBUG_FUNCTIONS_H 1`
32
33			`#include <bits/c++config.h>`
34			`#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and`
35			`// _Iter_base`
36			`#include <bits/cpp_type_traits.h> // for __is_integer`
37			`#include <debug/formatter.h>`
38
39			`namespace __gnu_debug`
40			`{`
41			`template<typename _Iterator, typename _Sequence>`
42			`class _Safe_iterator;`
43
44			`// An arbitrary iterator pointer is not singular.`
45			`inline bool`
46			`__check_singular_aux(const void*) { return false; }`
47
48			`// We may have an iterator that derives from _Safe_iterator_base but isn't`
49			`// a _Safe_iterator.`
50			`template<typename _Iterator>`
51			`inline bool`
52			`__check_singular(_Iterator& __x)`
53			`{ return __check_singular_aux(&__x); }`
54
55			`/** Non-NULL pointers are nonsingular. */`
56			`template<typename _Tp>`
57			`inline bool`
58			`__check_singular(const _Tp* __ptr)`
59			`{ return __ptr == 0; }`
60
61			`/** Safe iterators know if they are singular. */`
62			`template<typename _Iterator, typename _Sequence>`
63			`inline bool`
64			`__check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x)`
65			`{ return __x._M_singular(); }`
66
67			`/** Assume that some arbitrary iterator is dereferenceable, because we`
68			`can't prove that it isn't. */`
69			`template<typename _Iterator>`
70			`inline bool`
71			`__check_dereferenceable(_Iterator&)`
72			`{ return true; }`
73
74			`/** Non-NULL pointers are dereferenceable. */`
75			`template<typename _Tp>`
76			`inline bool`
77			`__check_dereferenceable(const _Tp* __ptr)`
78			`{ return __ptr; }`
79
80			`/** Safe iterators know if they are singular. */`
81			`template<typename _Iterator, typename _Sequence>`
82			`inline bool`
83			`__check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)`
84			`{ return __x._M_dereferenceable(); }`
85
86			`/** If the distance between two random access iterators is`
87			`* nonnegative, assume the range is valid.`
88			`*/`
89			`template<typename _RandomAccessIterator>`
90			`inline bool`
91			`__valid_range_aux2(const _RandomAccessIterator& __first,`
92			`const _RandomAccessIterator& __last,`
93			`std::random_access_iterator_tag)`
94			`{ return __last - __first >= 0; }`
95
96			`/** Can't test for a valid range with input iterators, because`
97			`* iteration may be destructive. So we just assume that the range`
98			`* is valid.`
99			`*/`
100			`template<typename _InputIterator>`
101			`inline bool`
102			`__valid_range_aux2(const _InputIterator&, const _InputIterator&,`
103			`std::input_iterator_tag)`
104			`{ return true; }`
105
106			`/** We say that integral types for a valid range, and defer to other`
107			`* routines to realize what to do with integral types instead of`
108			`* iterators.`
109			`*/`
110			`template<typename _Integral>`
111			`inline bool`
112			`__valid_range_aux(const _Integral&, const _Integral&, std::__true_type)`
113			`{ return true; }`
114
115			`/** We have iterators, so figure out what kind of iterators that are`
116			`* to see if we can check the range ahead of time.`
117			`*/`
118			`template<typename _InputIterator>`
119			`inline bool`
120			`__valid_range_aux(const _InputIterator& __first,`
121			`const _InputIterator& __last, std::__false_type)`
122			`{ return __valid_range_aux2(__first, __last,`
123			`std::__iterator_category(__first)); }`
124
125			`/** Don't know what these iterators are, or if they are even`
126			`* iterators (we may get an integral type for InputIterator), so`
127			`* see if they are integral and pass them on to the next phase`
128			`* otherwise.`
129			`*/`
130			`template<typename _InputIterator>`
131			`inline bool`
132			`__valid_range(const _InputIterator& __first, const _InputIterator& __last)`
133			`{`
134			`typedef typename std::__is_integer<_InputIterator>::__type _Integral;`
135			`return __valid_range_aux(__first, __last, _Integral());`
136			`}`
137
138			`/** Safe iterators know how to check if they form a valid range. */`
139			`template<typename _Iterator, typename _Sequence>`
140			`inline bool`
141			`__valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,`
142			`const _Safe_iterator<_Iterator, _Sequence>& __last)`
143			`{ return __first._M_valid_range(__last); }`
144
145			`/** Safe local iterators know how to check if they form a valid range. */`
146			`template<typename _Iterator, typename _Sequence>`
147			`inline bool`
148			`__valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,`
149			`const _Safe_local_iterator<_Iterator, _Sequence>& __last)`
150			`{ return __first._M_valid_range(__last); }`
151
152			`/* Checks that [first, last) is a valid range, and then returns`
153			`* __first. This routine is useful when we can't use a separate`
154			`* assertion statement because, e.g., we are in a constructor.`
155			`*/`
156			`template<typename _InputIterator>`
157			`inline _InputIterator`
158			`__check_valid_range(const _InputIterator& __first,`
159			`const _InputIterator& __last`
160			`__attribute__((__unused__)))`
161			`{`
162			`__glibcxx_check_valid_range(__first, __last);`
163			`return __first;`
164			`}`
165
166			`/** Checks that __s is non-NULL or __n == 0, and then returns __s. */`
167			`template<typename _CharT, typename _Integer>`
168			`inline const _CharT*`
169			`__check_string(const _CharT* __s,`
170			`const _Integer& __n __attribute__((__unused__)))`
171			`{`
172			`#ifdef _GLIBCXX_DEBUG_PEDANTIC`
173			`__glibcxx_assert(__s != 0 \|\| __n == 0);`
174			`#endif`
175			`return __s;`
176			`}`
177
178			`/** Checks that __s is non-NULL and then returns __s. */`
179			`template<typename _CharT>`
180			`inline const _CharT*`
181			`__check_string(const _CharT* __s)`
182			`{`
183			`#ifdef _GLIBCXX_DEBUG_PEDANTIC`
184			`__glibcxx_assert(__s != 0);`
185			`#endif`
186			`return __s;`
187			`}`
188
189			`// Can't check if an input iterator sequence is sorted, because we`
190			`// can't step through the sequence.`
191			`template<typename _InputIterator>`
192			`inline bool`
193			`__check_sorted_aux(const _InputIterator&, const _InputIterator&,`
194			`std::input_iterator_tag)`
195			`{ return true; }`
196
197			`// Can verify if a forward iterator sequence is in fact sorted using`
198			`// std::__is_sorted`
199			`template<typename _ForwardIterator>`
200			`inline bool`
201			`__check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,`
202			`std::forward_iterator_tag)`
203			`{`
204			`if (__first == __last)`
205			`return true;`
206
207			`_ForwardIterator __next = __first;`
208			`for (++__next; __next != __last; __first = __next, ++__next)`
209			`if (__next < __first)`
210			`return false;`
211
212			`return true;`
213			`}`
214
215			`// For performance reason, as the iterator range has been validated, check on`
216			`// random access safe iterators is done using the base iterator.`
217			`template<typename _Iterator, typename _Sequence>`
218			`inline bool`
219			`__check_sorted_aux(const _Safe_iterator<_Iterator, _Sequence>& __first,`
220			`const _Safe_iterator<_Iterator, _Sequence>& __last,`
221			`std::random_access_iterator_tag __tag)`
222			`{ return __check_sorted_aux(__first.base(), __last.base(), __tag); }`
223
224			`// Can't check if an input iterator sequence is sorted, because we can't step`
225			`// through the sequence.`
226			`template<typename _InputIterator, typename _Predicate>`
227			`inline bool`
228			`__check_sorted_aux(const _InputIterator&, const _InputIterator&,`
229			`_Predicate, std::input_iterator_tag)`
230			`{ return true; }`
231
232			`// Can verify if a forward iterator sequence is in fact sorted using`
233			`// std::__is_sorted`
234			`template<typename _ForwardIterator, typename _Predicate>`
235			`inline bool`
236			`__check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,`
237			`_Predicate __pred, std::forward_iterator_tag)`
238			`{`
239			`if (__first == __last)`
240			`return true;`
241
242			`_ForwardIterator __next = __first;`
243			`for (++__next; __next != __last; __first = __next, ++__next)`
244			`if (__pred(__next, __first))`
245			`return false;`
246
247			`return true;`
248			`}`
249
250			`// For performance reason, as the iterator range has been validated, check on`
251			`// random access safe iterators is done using the base iterator.`
252			`template<typename _Iterator, typename _Sequence,`
253			`typename _Predicate>`
254			`inline bool`
255			`__check_sorted_aux(const _Safe_iterator<_Iterator, _Sequence>& __first,`
256			`const _Safe_iterator<_Iterator, _Sequence>& __last,`
257			`_Predicate __pred,`
258			`std::random_access_iterator_tag __tag)`
259			`{ return __check_sorted_aux(__first.base(), __last.base(), __pred, __tag); }`
260
261			`// Determine if a sequence is sorted.`
262			`template<typename _InputIterator>`
263			`inline bool`
264			`__check_sorted(const _InputIterator& __first, const _InputIterator& __last)`
265			`{`
266			`// Verify that the < operator for elements in the sequence is a`
267			`// StrictWeakOrdering by checking that it is irreflexive.`
268			`__glibcxx_assert(__first == __last \|\| !(__first < __first));`
269
270			`return __check_sorted_aux(__first, __last,`
271			`std::__iterator_category(__first));`
272			`}`
273
274			`template<typename _InputIterator, typename _Predicate>`
275			`inline bool`
276			`__check_sorted(const _InputIterator& __first, const _InputIterator& __last,`
277			`_Predicate __pred)`
278			`{`
279			`// Verify that the predicate is StrictWeakOrdering by checking that it`
280			`// is irreflexive.`
281			`__glibcxx_assert(__first == __last \|\| !__pred(__first, __first));`
282
283			`return __check_sorted_aux(__first, __last, __pred,`
284			`std::__iterator_category(__first));`
285			`}`
286
287			`template<typename _InputIterator>`
288			`inline bool`
289			`__check_sorted_set_aux(const _InputIterator& __first,`
290			`const _InputIterator& __last,`
291			`std::__true_type)`
292			`{ return __check_sorted(__first, __last); }`
293
294			`template<typename _InputIterator>`
295			`inline bool`
296			`__check_sorted_set_aux(const _InputIterator&,`
297			`const _InputIterator&,`
298			`std::__false_type)`
299			`{ return true; }`
300
301			`template<typename _InputIterator, typename _Predicate>`
302			`inline bool`
303			`__check_sorted_set_aux(const _InputIterator& __first,`
304			`const _InputIterator& __last,`
305			`_Predicate __pred, std::__true_type)`
306			`{ return __check_sorted(__first, __last, __pred); }`
307
308			`template<typename _InputIterator, typename _Predicate>`
309			`inline bool`
310			`__check_sorted_set_aux(const _InputIterator&,`
311			`const _InputIterator&, _Predicate,`
312			`std::__false_type)`
313			`{ return true; }`
314
315			`// ... special variant used in std::merge, std::includes, std::set_*.`
316			`template<typename _InputIterator1, typename _InputIterator2>`
317			`inline bool`
318			`__check_sorted_set(const _InputIterator1& __first,`
319			`const _InputIterator1& __last,`
320			`const _InputIterator2&)`
321			`{`
322			`typedef typename std::iterator_traits<_InputIterator1>::value_type`
323			`_ValueType1;`
324			`typedef typename std::iterator_traits<_InputIterator2>::value_type`
325			`_ValueType2;`
326
327			`typedef typename std::__are_same<_ValueType1, _ValueType2>::__type`
328			`_SameType;`
329			`return __check_sorted_set_aux(__first, __last, _SameType());`
330			`}`
331
332			`template<typename _InputIterator1, typename _InputIterator2,`
333			`typename _Predicate>`
334			`inline bool`
335			`__check_sorted_set(const _InputIterator1& __first,`
336			`const _InputIterator1& __last,`
337			`const _InputIterator2&, _Predicate __pred)`
338			`{`
339			`typedef typename std::iterator_traits<_InputIterator1>::value_type`
340			`_ValueType1;`
341			`typedef typename std::iterator_traits<_InputIterator2>::value_type`
342			`_ValueType2;`
343
344			`typedef typename std::__are_same<_ValueType1, _ValueType2>::__type`
345			`_SameType;`
346			`return __check_sorted_set_aux(__first, __last, __pred, _SameType());`
347			`}`
348
349			`template<typename _ForwardIterator, typename _Tp>`
350			`inline bool`
351			`__check_partitioned_lower_aux(_ForwardIterator __first,`
352			`_ForwardIterator __last, const _Tp& __value,`
353			`std::forward_iterator_tag)`
354			`{`
355			`while (__first != __last && *__first < __value)`
356			`++__first;`
357			`if (__first != __last)`
358			`{`
359			`++__first;`
360			`while (__first != __last && !(*__first < __value))`
361			`++__first;`
362			`}`
363			`return __first == __last;`
364			`}`
365
366			`// For performance reason, as the iterator range has been validated, check on`
367			`// random access safe iterators is done using the base iterator.`
368			`template<typename _Iterator, typename _Sequence, typename _Tp>`
369			`inline bool`
370			`__check_partitioned_lower_aux(`
371			`const _Safe_iterator<_Iterator, _Sequence>& __first,`
372			`const _Safe_iterator<_Iterator, _Sequence>& __last,`
373			`const _Tp& __value,`
374			`std::random_access_iterator_tag __tag)`
375			`{`
376			`return __check_partitioned_lower_aux(__first.base(), __last.base(),`
377			`__value, __tag);`
378			`}`
379
380			`// _GLIBCXX_RESOLVE_LIB_DEFECTS`
381			`// 270. Binary search requirements overly strict`
382			`// Determine if a sequence is partitioned w.r.t. this element.`
383			`template<typename _ForwardIterator, typename _Tp>`
384			`inline bool`
385			`__check_partitioned_lower(_ForwardIterator __first,`
386			`_ForwardIterator __last, const _Tp& __value)`
387			`{`
388			`return __check_partitioned_lower_aux(__first, __last, __value,`
389			`std::__iterator_category(__first));`
390			`}`
391
392			`template<typename _ForwardIterator, typename _Tp>`
393			`inline bool`
394			`__check_partitioned_upper_aux(_ForwardIterator __first,`
395			`_ForwardIterator __last, const _Tp& __value,`
396			`std::forward_iterator_tag)`
397			`{`
398			`while (__first != __last && !(__value < *__first))`
399			`++__first;`
400			`if (__first != __last)`
401			`{`
402			`++__first;`
403			`while (__first != __last && __value < *__first)`
404			`++__first;`
405			`}`
406			`return __first == __last;`
407			`}`
408
409			`// For performance reason, as the iterator range has been validated, check on`
410			`// random access safe iterators is done using the base iterator.`
411			`template<typename _Iterator, typename _Sequence, typename _Tp>`
412			`inline bool`
413			`__check_partitioned_upper_aux(`
414			`const _Safe_iterator<_Iterator, _Sequence>& __first,`
415			`const _Safe_iterator<_Iterator, _Sequence>& __last,`
416			`const _Tp& __value,`
417			`std::random_access_iterator_tag __tag)`
418			`{`
419			`return __check_partitioned_upper_aux(__first.base(), __last.base(),`
420			`__value, __tag);`
421			`}`
422
423			`template<typename _ForwardIterator, typename _Tp>`
424			`inline bool`
425			`__check_partitioned_upper(_ForwardIterator __first,`
426			`_ForwardIterator __last, const _Tp& __value)`
427			`{`
428			`return __check_partitioned_upper_aux(__first, __last, __value,`
429			`std::__iterator_category(__first));`
430			`}`
431
432			`template<typename _ForwardIterator, typename _Tp, typename _Pred>`
433			`inline bool`
434			`__check_partitioned_lower_aux(_ForwardIterator __first,`
435			`_ForwardIterator __last, const _Tp& __value,`
436			`_Pred __pred,`
437			`std::forward_iterator_tag)`
438			`{`
439			`while (__first != __last && bool(__pred(*__first, __value)))`
440			`++__first;`
441			`if (__first != __last)`
442			`{`
443			`++__first;`
444			`while (__first != __last && !bool(__pred(*__first, __value)))`
445			`++__first;`
446			`}`
447			`return __first == __last;`
448			`}`
449
450			`// For performance reason, as the iterator range has been validated, check on`
451			`// random access safe iterators is done using the base iterator.`
452			`template<typename _Iterator, typename _Sequence,`
453			`typename _Tp, typename _Pred>`
454			`inline bool`
455			`__check_partitioned_lower_aux(`
456			`const _Safe_iterator<_Iterator, _Sequence>& __first,`
457			`const _Safe_iterator<_Iterator, _Sequence>& __last,`
458			`const _Tp& __value, _Pred __pred,`
459			`std::random_access_iterator_tag __tag)`
460			`{`
461			`return __check_partitioned_lower_aux(__first.base(), __last.base(),`
462			`__value, __pred, __tag);`
463			`}`
464
465			`// Determine if a sequence is partitioned w.r.t. this element.`
466			`template<typename _ForwardIterator, typename _Tp, typename _Pred>`
467			`inline bool`
468			`__check_partitioned_lower(_ForwardIterator __first,`
469			`_ForwardIterator __last, const _Tp& __value,`
470			`_Pred __pred)`
471			`{`
472			`return __check_partitioned_lower_aux(__first, __last, __value, __pred,`
473			`std::__iterator_category(__first));`
474			`}`
475
476			`template<typename _ForwardIterator, typename _Tp, typename _Pred>`
477			`inline bool`
478			`__check_partitioned_upper_aux(_ForwardIterator __first,`
479			`_ForwardIterator __last, const _Tp& __value,`
480			`_Pred __pred,`
481			`std::forward_iterator_tag)`
482			`{`
483			`while (__first != __last && !bool(__pred(__value, *__first)))`
484			`++__first;`
485			`if (__first != __last)`
486			`{`
487			`++__first;`
488			`while (__first != __last && bool(__pred(__value, *__first)))`
489			`++__first;`
490			`}`
491			`return __first == __last;`
492			`}`
493
494			`// For performance reason, as the iterator range has been validated, check on`
495			`// random access safe iterators is done using the base iterator.`
496			`template<typename _Iterator, typename _Sequence,`
497			`typename _Tp, typename _Pred>`
498			`inline bool`
499			`__check_partitioned_upper_aux(`
500			`const _Safe_iterator<_Iterator, _Sequence>& __first,`
501			`const _Safe_iterator<_Iterator, _Sequence>& __last,`
502			`const _Tp& __value, _Pred __pred,`
503			`std::random_access_iterator_tag __tag)`
504			`{`
505			`return __check_partitioned_upper_aux(__first.base(), __last.base(),`
506			`__value, __pred, __tag);`
507			`}`
508
509			`template<typename _ForwardIterator, typename _Tp, typename _Pred>`
510			`inline bool`
511			`__check_partitioned_upper(_ForwardIterator __first,`
512			`_ForwardIterator __last, const _Tp& __value,`
513			`_Pred __pred)`
514			`{`
515			`return __check_partitioned_upper_aux(__first, __last, __value, __pred,`
516			`std::__iterator_category(__first));`
517			`}`
518
519			`// Helper struct to detect random access safe iterators.`
520			`template<typename _Iterator>`
521			`struct __is_safe_random_iterator`
522			`{`
523			`enum { __value = 0 };`
524			`typedef std::__false_type __type;`
525			`};`
526
527			`template<typename _Iterator, typename _Sequence>`
528			`struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >`
529			`: std::__are_same<std::random_access_iterator_tag,`
530			`typename std::iterator_traits<_Iterator>::`
531			`iterator_category>`
532			`{ };`
533
534			`template<typename _Iterator>`
535			`struct _Siter_base`
536			`: std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>`
537			`{ };`
538
539			`/** Helper function to extract base iterator of random access safe iterator`
540			`in order to reduce performance impact of debug mode. Limited to random`
541			`access iterator because it is the only category for which it is possible`
542			`to check for correct iterators order in the __valid_range function`
543			`thanks to the < operator.`
544			`*/`
545			`template<typename _Iterator>`
546			`inline typename _Siter_base<_Iterator>::iterator_type`
547			`__base(_Iterator __it)`
548			`{ return _Siter_base<_Iterator>::_S_base(__it); }`
549			`} // namespace __gnu_debug`
550
551			`#endif`