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