libstdc++
|
00001 // Debugging support implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /** @file debug/functions.h 00027 * This file is a GNU debug extension to the Standard C++ Library. 00028 */ 00029 00030 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H 00031 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1 00032 00033 #include <bits/c++config.h> 00034 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories 00035 #include <bits/cpp_type_traits.h> // for __is_integer 00036 #include <debug/formatter.h> 00037 00038 namespace __gnu_debug 00039 { 00040 template<typename _Iterator, typename _Sequence> 00041 class _Safe_iterator; 00042 00043 // An arbitrary iterator pointer is not singular. 00044 inline bool 00045 __check_singular_aux(const void*) { return false; } 00046 00047 // We may have an iterator that derives from _Safe_iterator_base but isn't 00048 // a _Safe_iterator. 00049 template<typename _Iterator> 00050 inline bool 00051 __check_singular(_Iterator& __x) 00052 { return __check_singular_aux(&__x); } 00053 00054 /** Non-NULL pointers are nonsingular. */ 00055 template<typename _Tp> 00056 inline bool 00057 __check_singular(const _Tp* __ptr) 00058 { return __ptr == 0; } 00059 00060 /** Safe iterators know if they are singular. */ 00061 template<typename _Iterator, typename _Sequence> 00062 inline bool 00063 __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x) 00064 { return __x._M_singular(); } 00065 00066 /** Assume that some arbitrary iterator is dereferenceable, because we 00067 can't prove that it isn't. */ 00068 template<typename _Iterator> 00069 inline bool 00070 __check_dereferenceable(_Iterator&) 00071 { return true; } 00072 00073 /** Non-NULL pointers are dereferenceable. */ 00074 template<typename _Tp> 00075 inline bool 00076 __check_dereferenceable(const _Tp* __ptr) 00077 { return __ptr; } 00078 00079 /** Safe iterators know if they are singular. */ 00080 template<typename _Iterator, typename _Sequence> 00081 inline bool 00082 __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x) 00083 { return __x._M_dereferenceable(); } 00084 00085 /** If the distance between two random access iterators is 00086 * nonnegative, assume the range is valid. 00087 */ 00088 template<typename _RandomAccessIterator> 00089 inline bool 00090 __valid_range_aux2(const _RandomAccessIterator& __first, 00091 const _RandomAccessIterator& __last, 00092 std::random_access_iterator_tag) 00093 { return __last - __first >= 0; } 00094 00095 /** Can't test for a valid range with input iterators, because 00096 * iteration may be destructive. So we just assume that the range 00097 * is valid. 00098 */ 00099 template<typename _InputIterator> 00100 inline bool 00101 __valid_range_aux2(const _InputIterator&, const _InputIterator&, 00102 std::input_iterator_tag) 00103 { return true; } 00104 00105 /** We say that integral types for a valid range, and defer to other 00106 * routines to realize what to do with integral types instead of 00107 * iterators. 00108 */ 00109 template<typename _Integral> 00110 inline bool 00111 __valid_range_aux(const _Integral&, const _Integral&, std::__true_type) 00112 { return true; } 00113 00114 /** We have iterators, so figure out what kind of iterators that are 00115 * to see if we can check the range ahead of time. 00116 */ 00117 template<typename _InputIterator> 00118 inline bool 00119 __valid_range_aux(const _InputIterator& __first, 00120 const _InputIterator& __last, std::__false_type) 00121 { 00122 typedef typename std::iterator_traits<_InputIterator>::iterator_category 00123 _Category; 00124 return __valid_range_aux2(__first, __last, _Category()); 00125 } 00126 00127 /** Don't know what these iterators are, or if they are even 00128 * iterators (we may get an integral type for InputIterator), so 00129 * see if they are integral and pass them on to the next phase 00130 * otherwise. 00131 */ 00132 template<typename _InputIterator> 00133 inline bool 00134 __valid_range(const _InputIterator& __first, const _InputIterator& __last) 00135 { 00136 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00137 return __valid_range_aux(__first, __last, _Integral()); 00138 } 00139 00140 /** Safe iterators know how to check if they form a valid range. */ 00141 template<typename _Iterator, typename _Sequence> 00142 inline bool 00143 __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, 00144 const _Safe_iterator<_Iterator, _Sequence>& __last) 00145 { return __first._M_valid_range(__last); } 00146 00147 /* Checks that [first, last) is a valid range, and then returns 00148 * __first. This routine is useful when we can't use a separate 00149 * assertion statement because, e.g., we are in a constructor. 00150 */ 00151 template<typename _InputIterator> 00152 inline _InputIterator 00153 __check_valid_range(const _InputIterator& __first, 00154 const _InputIterator& __last 00155 __attribute__((__unused__))) 00156 { 00157 __glibcxx_check_valid_range(__first, __last); 00158 return __first; 00159 } 00160 00161 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ 00162 template<typename _CharT, typename _Integer> 00163 inline const _CharT* 00164 __check_string(const _CharT* __s, 00165 const _Integer& __n __attribute__((__unused__))) 00166 { 00167 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00168 __glibcxx_assert(__s != 0 || __n == 0); 00169 #endif 00170 return __s; 00171 } 00172 00173 /** Checks that __s is non-NULL and then returns __s. */ 00174 template<typename _CharT> 00175 inline const _CharT* 00176 __check_string(const _CharT* __s) 00177 { 00178 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00179 __glibcxx_assert(__s != 0); 00180 #endif 00181 return __s; 00182 } 00183 00184 // Can't check if an input iterator sequence is sorted, because we 00185 // can't step through the sequence. 00186 template<typename _InputIterator> 00187 inline bool 00188 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00189 std::input_iterator_tag) 00190 { return true; } 00191 00192 // Can verify if a forward iterator sequence is in fact sorted using 00193 // std::__is_sorted 00194 template<typename _ForwardIterator> 00195 inline bool 00196 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00197 std::forward_iterator_tag) 00198 { 00199 if (__first == __last) 00200 return true; 00201 00202 _ForwardIterator __next = __first; 00203 for (++__next; __next != __last; __first = __next, ++__next) 00204 if (*__next < *__first) 00205 return false; 00206 00207 return true; 00208 } 00209 00210 // Can't check if an input iterator sequence is sorted, because we can't step 00211 // through the sequence. 00212 template<typename _InputIterator, typename _Predicate> 00213 inline bool 00214 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00215 _Predicate, std::input_iterator_tag) 00216 { return true; } 00217 00218 // Can verify if a forward iterator sequence is in fact sorted using 00219 // std::__is_sorted 00220 template<typename _ForwardIterator, typename _Predicate> 00221 inline bool 00222 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00223 _Predicate __pred, std::forward_iterator_tag) 00224 { 00225 if (__first == __last) 00226 return true; 00227 00228 _ForwardIterator __next = __first; 00229 for (++__next; __next != __last; __first = __next, ++__next) 00230 if (__pred(*__next, *__first)) 00231 return false; 00232 00233 return true; 00234 } 00235 00236 // Determine if a sequence is sorted. 00237 template<typename _InputIterator> 00238 inline bool 00239 __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 00240 { 00241 typedef typename std::iterator_traits<_InputIterator>::iterator_category 00242 _Category; 00243 00244 // Verify that the < operator for elements in the sequence is a 00245 // StrictWeakOrdering by checking that it is irreflexive. 00246 __glibcxx_assert(__first == __last || !(*__first < *__first)); 00247 00248 return __check_sorted_aux(__first, __last, _Category()); 00249 } 00250 00251 template<typename _InputIterator, typename _Predicate> 00252 inline bool 00253 __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 00254 _Predicate __pred) 00255 { 00256 typedef typename std::iterator_traits<_InputIterator>::iterator_category 00257 _Category; 00258 00259 // Verify that the predicate is StrictWeakOrdering by checking that it 00260 // is irreflexive. 00261 __glibcxx_assert(__first == __last || !__pred(*__first, *__first)); 00262 00263 return __check_sorted_aux(__first, __last, __pred, _Category()); 00264 } 00265 00266 template<typename _InputIterator> 00267 inline bool 00268 __check_sorted_set_aux(const _InputIterator& __first, 00269 const _InputIterator& __last, 00270 std::__true_type) 00271 { return __check_sorted(__first, __last); } 00272 00273 template<typename _InputIterator> 00274 inline bool 00275 __check_sorted_set_aux(const _InputIterator&, 00276 const _InputIterator&, 00277 std::__false_type) 00278 { return true; } 00279 00280 template<typename _InputIterator, typename _Predicate> 00281 inline bool 00282 __check_sorted_set_aux(const _InputIterator& __first, 00283 const _InputIterator& __last, 00284 _Predicate __pred, std::__true_type) 00285 { return __check_sorted(__first, __last, __pred); } 00286 00287 template<typename _InputIterator, typename _Predicate> 00288 inline bool 00289 __check_sorted_set_aux(const _InputIterator&, 00290 const _InputIterator&, _Predicate, 00291 std::__false_type) 00292 { return true; } 00293 00294 // ... special variant used in std::merge, std::includes, std::set_*. 00295 template<typename _InputIterator1, typename _InputIterator2> 00296 inline bool 00297 __check_sorted_set(const _InputIterator1& __first, 00298 const _InputIterator1& __last, 00299 const _InputIterator2&) 00300 { 00301 typedef typename std::iterator_traits<_InputIterator1>::value_type 00302 _ValueType1; 00303 typedef typename std::iterator_traits<_InputIterator2>::value_type 00304 _ValueType2; 00305 00306 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00307 _SameType; 00308 return __check_sorted_set_aux(__first, __last, _SameType()); 00309 } 00310 00311 template<typename _InputIterator1, typename _InputIterator2, 00312 typename _Predicate> 00313 inline bool 00314 __check_sorted_set(const _InputIterator1& __first, 00315 const _InputIterator1& __last, 00316 const _InputIterator2&, _Predicate __pred) 00317 { 00318 typedef typename std::iterator_traits<_InputIterator1>::value_type 00319 _ValueType1; 00320 typedef typename std::iterator_traits<_InputIterator2>::value_type 00321 _ValueType2; 00322 00323 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00324 _SameType; 00325 return __check_sorted_set_aux(__first, __last, __pred, _SameType()); 00326 } 00327 00328 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00329 // 270. Binary search requirements overly strict 00330 // Determine if a sequence is partitioned w.r.t. this element. 00331 template<typename _ForwardIterator, typename _Tp> 00332 inline bool 00333 __check_partitioned_lower(_ForwardIterator __first, 00334 _ForwardIterator __last, const _Tp& __value) 00335 { 00336 while (__first != __last && *__first < __value) 00337 ++__first; 00338 while (__first != __last && !(*__first < __value)) 00339 ++__first; 00340 return __first == __last; 00341 } 00342 00343 template<typename _ForwardIterator, typename _Tp> 00344 inline bool 00345 __check_partitioned_upper(_ForwardIterator __first, 00346 _ForwardIterator __last, const _Tp& __value) 00347 { 00348 while (__first != __last && !(__value < *__first)) 00349 ++__first; 00350 while (__first != __last && __value < *__first) 00351 ++__first; 00352 return __first == __last; 00353 } 00354 00355 // Determine if a sequence is partitioned w.r.t. this element. 00356 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00357 inline bool 00358 __check_partitioned_lower(_ForwardIterator __first, 00359 _ForwardIterator __last, const _Tp& __value, 00360 _Pred __pred) 00361 { 00362 while (__first != __last && bool(__pred(*__first, __value))) 00363 ++__first; 00364 while (__first != __last && !bool(__pred(*__first, __value))) 00365 ++__first; 00366 return __first == __last; 00367 } 00368 00369 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00370 inline bool 00371 __check_partitioned_upper(_ForwardIterator __first, 00372 _ForwardIterator __last, const _Tp& __value, 00373 _Pred __pred) 00374 { 00375 while (__first != __last && !bool(__pred(__value, *__first))) 00376 ++__first; 00377 while (__first != __last && bool(__pred(__value, *__first))) 00378 ++__first; 00379 return __first == __last; 00380 } 00381 } // namespace __gnu_debug 00382 00383 #endif