1// Debugging support implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2005, 2006
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 2, 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// You should have received a copy of the GNU General Public License along
18// with this library; see the file COPYING.  If not, write to the Free
19// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20// USA.
21
22// As a special exception, you may use this file as part of a free software
23// library without restriction.  Specifically, if other files instantiate
24// templates or use macros or inline functions from this file, or you compile
25// this file and link it with other files to produce an executable, this
26// file does not by itself cause the resulting executable to be covered by
27// the GNU General Public License.  This exception does not however
28// invalidate any other reasons why the executable file might be covered by
29// the GNU General Public License.
30
31/** @file debug/functions.h
32 *  This file is a GNU debug extension to the Standard C++ Library.
33 */
34
35#ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
36#define _GLIBCXX_DEBUG_FUNCTIONS_H 1
37
38#include <bits/c++config.h>
39#include <stddef.h>                       // for ptrdiff_t
40#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories
41#include <bits/cpp_type_traits.h>         // for __is_integer
42
43namespace __gnu_debug
44{
45  template<typename _Iterator, typename _Sequence>
46    class _Safe_iterator;
47
48  // An arbitrary iterator pointer is not singular.
49  inline bool
50  __check_singular_aux(const void*) { return false; }
51
52  // We may have an iterator that derives from _Safe_iterator_base but isn't
53  // a _Safe_iterator.
54  template<typename _Iterator>
55    inline bool
56    __check_singular(_Iterator& __x)
57    { return __check_singular_aux(&__x); }
58
59  /** Non-NULL pointers are nonsingular. */
60  template<typename _Tp>
61    inline bool
62    __check_singular(const _Tp* __ptr)
63    { return __ptr == 0; }
64
65  /** Safe iterators know if they are singular. */
66  template<typename _Iterator, typename _Sequence>
67    inline bool
68    __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x)
69    { return __x._M_singular(); }
70
71  /** Assume that some arbitrary iterator is dereferenceable, because we
72      can't prove that it isn't. */
73  template<typename _Iterator>
74    inline bool
75    __check_dereferenceable(_Iterator&)
76    { return true; }
77
78  /** Non-NULL pointers are dereferenceable. */
79  template<typename _Tp>
80    inline bool
81    __check_dereferenceable(const _Tp* __ptr)
82    { return __ptr; }
83
84  /** Safe iterators know if they are singular. */
85  template<typename _Iterator, typename _Sequence>
86    inline bool
87    __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
88    { return __x._M_dereferenceable(); }
89
90  /** If the distance between two random access iterators is
91   *  nonnegative, assume the range is valid.
92  */
93  template<typename _RandomAccessIterator>
94    inline bool
95    __valid_range_aux2(const _RandomAccessIterator& __first,
96		       const _RandomAccessIterator& __last,
97		       std::random_access_iterator_tag)
98    { return __last - __first >= 0; }
99
100  /** Can't test for a valid range with input iterators, because
101   *  iteration may be destructive. So we just assume that the range
102   *  is valid.
103  */
104  template<typename _InputIterator>
105    inline bool
106    __valid_range_aux2(const _InputIterator&, const _InputIterator&,
107		       std::input_iterator_tag)
108    { return true; }
109
110  /** We say that integral types for a valid range, and defer to other
111   *  routines to realize what to do with integral types instead of
112   *  iterators.
113  */
114  template<typename _Integral>
115    inline bool
116    __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
117    { return true; }
118
119  /** We have iterators, so figure out what kind of iterators that are
120   *  to see if we can check the range ahead of time.
121  */
122  template<typename _InputIterator>
123    inline bool
124    __valid_range_aux(const _InputIterator& __first,
125		      const _InputIterator& __last, std::__false_type)
126  {
127    typedef typename std::iterator_traits<_InputIterator>::iterator_category
128      _Category;
129    return __valid_range_aux2(__first, __last, _Category());
130  }
131
132  /** Don't know what these iterators are, or if they are even
133   *  iterators (we may get an integral type for InputIterator), so
134   *  see if they are integral and pass them on to the next phase
135   *  otherwise.
136  */
137  template<typename _InputIterator>
138    inline bool
139    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
140    {
141      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
142      return __valid_range_aux(__first, __last, _Integral());
143    }
144
145  /** Safe 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_iterator<_Iterator, _Sequence>& __first,
149		  const _Safe_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_DEBUG_ASSERT(__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_DEBUG_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_DEBUG_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
213      return true;
214    }
215
216  // Can't check if an input iterator sequence is sorted, because we can't step
217  // through the sequence.
218  template<typename _InputIterator, typename _Predicate>
219    inline bool
220    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
221                       _Predicate, std::input_iterator_tag)
222    { return true; }
223
224  // Can verify if a forward iterator sequence is in fact sorted using
225  // std::__is_sorted
226  template<typename _ForwardIterator, typename _Predicate>
227    inline bool
228    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
229                       _Predicate __pred, std::forward_iterator_tag)
230    {
231      if (__first == __last)
232        return true;
233
234      _ForwardIterator __next = __first;
235      for (++__next; __next != __last; __first = __next, ++__next) {
236        if (__pred(*__next, *__first))
237          return false;
238      }
239
240      return true;
241    }
242
243  // Determine if a sequence is sorted.
244  template<typename _InputIterator>
245    inline bool
246    __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
247    {
248      typedef typename std::iterator_traits<_InputIterator>::iterator_category
249        _Category;
250      return __check_sorted_aux(__first, __last, _Category());
251    }
252
253  template<typename _InputIterator, typename _Predicate>
254    inline bool
255    __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
256                   _Predicate __pred)
257    {
258      typedef typename std::iterator_traits<_InputIterator>::iterator_category
259        _Category;
260      return __check_sorted_aux(__first, __last, __pred,
261					     _Category());
262    }
263
264  // _GLIBCXX_RESOLVE_LIB_DEFECTS
265  // 270. Binary search requirements overly strict
266  // Determine if a sequence is partitioned w.r.t. this element.
267  template<typename _ForwardIterator, typename _Tp>
268    inline bool
269    __check_partitioned(_ForwardIterator __first, _ForwardIterator __last,
270			const _Tp& __value)
271    {
272      while (__first != __last && *__first < __value)
273	++__first;
274      while (__first != __last && !(*__first < __value))
275	++__first;
276      return __first == __last;
277    }
278
279  // Determine if a sequence is partitioned w.r.t. this element.
280  template<typename _ForwardIterator, typename _Tp, typename _Pred>
281    inline bool
282    __check_partitioned(_ForwardIterator __first, _ForwardIterator __last,
283			const _Tp& __value, _Pred __pred)
284    {
285      while (__first != __last && __pred(*__first, __value))
286	++__first;
287      while (__first != __last && !__pred(*__first, __value))
288	++__first;
289      return __first == __last;
290    }
291} // namespace __gnu_debug
292
293#endif
294