1169691Skan// Debugging support implementation -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2003, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 5169691Skan// 6169691Skan// This file is part of the GNU ISO C++ Library. This library is free 7169691Skan// software; you can redistribute it and/or modify it under the 8169691Skan// terms of the GNU General Public License as published by the 9169691Skan// Free Software Foundation; either version 2, or (at your option) 10169691Skan// any later version. 11169691Skan 12169691Skan// This library is distributed in the hope that it will be useful, 13169691Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 14169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169691Skan// GNU General Public License for more details. 16169691Skan 17169691Skan// You should have received a copy of the GNU General Public License along 18169691Skan// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20169691Skan// USA. 21169691Skan 22169691Skan// As a special exception, you may use this file as part of a free software 23169691Skan// library without restriction. Specifically, if other files instantiate 24169691Skan// templates or use macros or inline functions from this file, or you compile 25169691Skan// this file and link it with other files to produce an executable, this 26169691Skan// file does not by itself cause the resulting executable to be covered by 27169691Skan// the GNU General Public License. This exception does not however 28169691Skan// invalidate any other reasons why the executable file might be covered by 29169691Skan// the GNU General Public License. 30169691Skan 31169691Skan/** @file debug/functions.h 32169691Skan * This file is a GNU debug extension to the Standard C++ Library. 33169691Skan */ 34169691Skan 35169691Skan#ifndef _GLIBCXX_DEBUG_FUNCTIONS_H 36169691Skan#define _GLIBCXX_DEBUG_FUNCTIONS_H 1 37169691Skan 38169691Skan#include <bits/c++config.h> 39169691Skan#include <stddef.h> // for ptrdiff_t 40169691Skan#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories 41169691Skan#include <bits/cpp_type_traits.h> // for __is_integer 42169691Skan 43169691Skannamespace __gnu_debug 44169691Skan{ 45169691Skan template<typename _Iterator, typename _Sequence> 46169691Skan class _Safe_iterator; 47169691Skan 48169691Skan // An arbitrary iterator pointer is not singular. 49169691Skan inline bool 50169691Skan __check_singular_aux(const void*) { return false; } 51169691Skan 52169691Skan // We may have an iterator that derives from _Safe_iterator_base but isn't 53169691Skan // a _Safe_iterator. 54169691Skan template<typename _Iterator> 55169691Skan inline bool 56169691Skan __check_singular(_Iterator& __x) 57169691Skan { return __check_singular_aux(&__x); } 58169691Skan 59169691Skan /** Non-NULL pointers are nonsingular. */ 60169691Skan template<typename _Tp> 61169691Skan inline bool 62169691Skan __check_singular(const _Tp* __ptr) 63169691Skan { return __ptr == 0; } 64169691Skan 65169691Skan /** Safe iterators know if they are singular. */ 66169691Skan template<typename _Iterator, typename _Sequence> 67169691Skan inline bool 68169691Skan __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x) 69169691Skan { return __x._M_singular(); } 70169691Skan 71169691Skan /** Assume that some arbitrary iterator is dereferenceable, because we 72169691Skan can't prove that it isn't. */ 73169691Skan template<typename _Iterator> 74169691Skan inline bool 75169691Skan __check_dereferenceable(_Iterator&) 76169691Skan { return true; } 77169691Skan 78169691Skan /** Non-NULL pointers are dereferenceable. */ 79169691Skan template<typename _Tp> 80169691Skan inline bool 81169691Skan __check_dereferenceable(const _Tp* __ptr) 82169691Skan { return __ptr; } 83169691Skan 84169691Skan /** Safe iterators know if they are singular. */ 85169691Skan template<typename _Iterator, typename _Sequence> 86169691Skan inline bool 87169691Skan __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x) 88169691Skan { return __x._M_dereferenceable(); } 89169691Skan 90169691Skan /** If the distance between two random access iterators is 91169691Skan * nonnegative, assume the range is valid. 92169691Skan */ 93169691Skan template<typename _RandomAccessIterator> 94169691Skan inline bool 95169691Skan __valid_range_aux2(const _RandomAccessIterator& __first, 96169691Skan const _RandomAccessIterator& __last, 97169691Skan std::random_access_iterator_tag) 98169691Skan { return __last - __first >= 0; } 99169691Skan 100169691Skan /** Can't test for a valid range with input iterators, because 101169691Skan * iteration may be destructive. So we just assume that the range 102169691Skan * is valid. 103169691Skan */ 104169691Skan template<typename _InputIterator> 105169691Skan inline bool 106169691Skan __valid_range_aux2(const _InputIterator&, const _InputIterator&, 107169691Skan std::input_iterator_tag) 108169691Skan { return true; } 109169691Skan 110169691Skan /** We say that integral types for a valid range, and defer to other 111169691Skan * routines to realize what to do with integral types instead of 112169691Skan * iterators. 113169691Skan */ 114169691Skan template<typename _Integral> 115169691Skan inline bool 116169691Skan __valid_range_aux(const _Integral&, const _Integral&, std::__true_type) 117169691Skan { return true; } 118169691Skan 119169691Skan /** We have iterators, so figure out what kind of iterators that are 120169691Skan * to see if we can check the range ahead of time. 121169691Skan */ 122169691Skan template<typename _InputIterator> 123169691Skan inline bool 124169691Skan __valid_range_aux(const _InputIterator& __first, 125169691Skan const _InputIterator& __last, std::__false_type) 126169691Skan { 127169691Skan typedef typename std::iterator_traits<_InputIterator>::iterator_category 128169691Skan _Category; 129169691Skan return __valid_range_aux2(__first, __last, _Category()); 130169691Skan } 131169691Skan 132169691Skan /** Don't know what these iterators are, or if they are even 133169691Skan * iterators (we may get an integral type for InputIterator), so 134169691Skan * see if they are integral and pass them on to the next phase 135169691Skan * otherwise. 136169691Skan */ 137169691Skan template<typename _InputIterator> 138169691Skan inline bool 139169691Skan __valid_range(const _InputIterator& __first, const _InputIterator& __last) 140169691Skan { 141169691Skan typedef typename std::__is_integer<_InputIterator>::__type _Integral; 142169691Skan return __valid_range_aux(__first, __last, _Integral()); 143169691Skan } 144169691Skan 145169691Skan /** Safe iterators know how to check if they form a valid range. */ 146169691Skan template<typename _Iterator, typename _Sequence> 147169691Skan inline bool 148169691Skan __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, 149169691Skan const _Safe_iterator<_Iterator, _Sequence>& __last) 150169691Skan { return __first._M_valid_range(__last); } 151169691Skan 152169691Skan /* Checks that [first, last) is a valid range, and then returns 153169691Skan * __first. This routine is useful when we can't use a separate 154169691Skan * assertion statement because, e.g., we are in a constructor. 155169691Skan */ 156169691Skan template<typename _InputIterator> 157169691Skan inline _InputIterator 158169691Skan __check_valid_range(const _InputIterator& __first, 159169691Skan const _InputIterator& __last 160169691Skan __attribute__((__unused__))) 161169691Skan { 162169691Skan _GLIBCXX_DEBUG_ASSERT(__valid_range(__first, __last)); 163169691Skan return __first; 164169691Skan } 165169691Skan 166169691Skan /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ 167169691Skan template<typename _CharT, typename _Integer> 168169691Skan inline const _CharT* 169169691Skan __check_string(const _CharT* __s, 170169691Skan const _Integer& __n __attribute__((__unused__))) 171169691Skan { 172169691Skan#ifdef _GLIBCXX_DEBUG_PEDANTIC 173169691Skan _GLIBCXX_DEBUG_ASSERT(__s != 0 || __n == 0); 174169691Skan#endif 175169691Skan return __s; 176169691Skan } 177169691Skan 178169691Skan /** Checks that __s is non-NULL and then returns __s. */ 179169691Skan template<typename _CharT> 180169691Skan inline const _CharT* 181169691Skan __check_string(const _CharT* __s) 182169691Skan { 183169691Skan#ifdef _GLIBCXX_DEBUG_PEDANTIC 184169691Skan _GLIBCXX_DEBUG_ASSERT(__s != 0); 185169691Skan#endif 186169691Skan return __s; 187169691Skan } 188169691Skan 189169691Skan // Can't check if an input iterator sequence is sorted, because we 190169691Skan // can't step through the sequence. 191169691Skan template<typename _InputIterator> 192169691Skan inline bool 193169691Skan __check_sorted_aux(const _InputIterator&, const _InputIterator&, 194169691Skan std::input_iterator_tag) 195169691Skan { return true; } 196169691Skan 197169691Skan // Can verify if a forward iterator sequence is in fact sorted using 198169691Skan // std::__is_sorted 199169691Skan template<typename _ForwardIterator> 200169691Skan inline bool 201169691Skan __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 202169691Skan std::forward_iterator_tag) 203169691Skan { 204169691Skan if (__first == __last) 205169691Skan return true; 206169691Skan 207169691Skan _ForwardIterator __next = __first; 208169691Skan for (++__next; __next != __last; __first = __next, ++__next) { 209169691Skan if (*__next < *__first) 210169691Skan return false; 211169691Skan } 212169691Skan 213169691Skan return true; 214169691Skan } 215169691Skan 216169691Skan // Can't check if an input iterator sequence is sorted, because we can't step 217169691Skan // through the sequence. 218169691Skan template<typename _InputIterator, typename _Predicate> 219169691Skan inline bool 220169691Skan __check_sorted_aux(const _InputIterator&, const _InputIterator&, 221169691Skan _Predicate, std::input_iterator_tag) 222169691Skan { return true; } 223169691Skan 224169691Skan // Can verify if a forward iterator sequence is in fact sorted using 225169691Skan // std::__is_sorted 226169691Skan template<typename _ForwardIterator, typename _Predicate> 227169691Skan inline bool 228169691Skan __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 229169691Skan _Predicate __pred, std::forward_iterator_tag) 230169691Skan { 231169691Skan if (__first == __last) 232169691Skan return true; 233169691Skan 234169691Skan _ForwardIterator __next = __first; 235169691Skan for (++__next; __next != __last; __first = __next, ++__next) { 236169691Skan if (__pred(*__next, *__first)) 237169691Skan return false; 238169691Skan } 239169691Skan 240169691Skan return true; 241169691Skan } 242169691Skan 243169691Skan // Determine if a sequence is sorted. 244169691Skan template<typename _InputIterator> 245169691Skan inline bool 246169691Skan __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 247169691Skan { 248169691Skan typedef typename std::iterator_traits<_InputIterator>::iterator_category 249169691Skan _Category; 250169691Skan return __check_sorted_aux(__first, __last, _Category()); 251169691Skan } 252169691Skan 253169691Skan template<typename _InputIterator, typename _Predicate> 254169691Skan inline bool 255169691Skan __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 256169691Skan _Predicate __pred) 257169691Skan { 258169691Skan typedef typename std::iterator_traits<_InputIterator>::iterator_category 259169691Skan _Category; 260169691Skan return __check_sorted_aux(__first, __last, __pred, 261169691Skan _Category()); 262169691Skan } 263169691Skan 264169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 265169691Skan // 270. Binary search requirements overly strict 266169691Skan // Determine if a sequence is partitioned w.r.t. this element. 267169691Skan template<typename _ForwardIterator, typename _Tp> 268169691Skan inline bool 269169691Skan __check_partitioned(_ForwardIterator __first, _ForwardIterator __last, 270169691Skan const _Tp& __value) 271169691Skan { 272169691Skan while (__first != __last && *__first < __value) 273169691Skan ++__first; 274169691Skan while (__first != __last && !(*__first < __value)) 275169691Skan ++__first; 276169691Skan return __first == __last; 277169691Skan } 278169691Skan 279169691Skan // Determine if a sequence is partitioned w.r.t. this element. 280169691Skan template<typename _ForwardIterator, typename _Tp, typename _Pred> 281169691Skan inline bool 282169691Skan __check_partitioned(_ForwardIterator __first, _ForwardIterator __last, 283169691Skan const _Tp& __value, _Pred __pred) 284169691Skan { 285169691Skan while (__first != __last && __pred(*__first, __value)) 286169691Skan ++__first; 287169691Skan while (__first != __last && !__pred(*__first, __value)) 288169691Skan ++__first; 289169691Skan return __first == __last; 290169691Skan } 291169691Skan} // namespace __gnu_debug 292169691Skan 293169691Skan#endif 294