libstdc++
|
00001 // Debugging support implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2013 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file debug/functions.h 00026 * This file is a GNU debug extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H 00030 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1 00031 00032 #include <bits/c++config.h> 00033 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and 00034 // _Iter_base 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 { return __valid_range_aux2(__first, __last, 00122 std::__iterator_category(__first)); } 00123 00124 /** Don't know what these iterators are, or if they are even 00125 * iterators (we may get an integral type for InputIterator), so 00126 * see if they are integral and pass them on to the next phase 00127 * otherwise. 00128 */ 00129 template<typename _InputIterator> 00130 inline bool 00131 __valid_range(const _InputIterator& __first, const _InputIterator& __last) 00132 { 00133 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00134 return __valid_range_aux(__first, __last, _Integral()); 00135 } 00136 00137 /** Safe iterators know how to check if they form a valid range. */ 00138 template<typename _Iterator, typename _Sequence> 00139 inline bool 00140 __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, 00141 const _Safe_iterator<_Iterator, _Sequence>& __last) 00142 { return __first._M_valid_range(__last); } 00143 00144 /** Safe local iterators know how to check if they form a valid range. */ 00145 template<typename _Iterator, typename _Sequence> 00146 inline bool 00147 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 00148 const _Safe_local_iterator<_Iterator, _Sequence>& __last) 00149 { return __first._M_valid_range(__last); } 00150 00151 /* Checks that [first, last) is a valid range, and then returns 00152 * __first. This routine is useful when we can't use a separate 00153 * assertion statement because, e.g., we are in a constructor. 00154 */ 00155 template<typename _InputIterator> 00156 inline _InputIterator 00157 __check_valid_range(const _InputIterator& __first, 00158 const _InputIterator& __last 00159 __attribute__((__unused__))) 00160 { 00161 __glibcxx_check_valid_range(__first, __last); 00162 return __first; 00163 } 00164 00165 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ 00166 template<typename _CharT, typename _Integer> 00167 inline const _CharT* 00168 __check_string(const _CharT* __s, 00169 const _Integer& __n __attribute__((__unused__))) 00170 { 00171 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00172 __glibcxx_assert(__s != 0 || __n == 0); 00173 #endif 00174 return __s; 00175 } 00176 00177 /** Checks that __s is non-NULL and then returns __s. */ 00178 template<typename _CharT> 00179 inline const _CharT* 00180 __check_string(const _CharT* __s) 00181 { 00182 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00183 __glibcxx_assert(__s != 0); 00184 #endif 00185 return __s; 00186 } 00187 00188 // Can't check if an input iterator sequence is sorted, because we 00189 // can't step through the sequence. 00190 template<typename _InputIterator> 00191 inline bool 00192 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00193 std::input_iterator_tag) 00194 { return true; } 00195 00196 // Can verify if a forward iterator sequence is in fact sorted using 00197 // std::__is_sorted 00198 template<typename _ForwardIterator> 00199 inline bool 00200 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00201 std::forward_iterator_tag) 00202 { 00203 if (__first == __last) 00204 return true; 00205 00206 _ForwardIterator __next = __first; 00207 for (++__next; __next != __last; __first = __next, ++__next) 00208 if (*__next < *__first) 00209 return false; 00210 00211 return true; 00212 } 00213 00214 // For performance reason, as the iterator range has been validated, check on 00215 // random access safe iterators is done using the base iterator. 00216 template<typename _Iterator, typename _Sequence> 00217 inline bool 00218 __check_sorted_aux(const _Safe_iterator<_Iterator, _Sequence>& __first, 00219 const _Safe_iterator<_Iterator, _Sequence>& __last, 00220 std::random_access_iterator_tag __tag) 00221 { return __check_sorted_aux(__first.base(), __last.base(), __tag); } 00222 00223 // Can't check if an input iterator sequence is sorted, because we can't step 00224 // through the sequence. 00225 template<typename _InputIterator, typename _Predicate> 00226 inline bool 00227 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00228 _Predicate, std::input_iterator_tag) 00229 { return true; } 00230 00231 // Can verify if a forward iterator sequence is in fact sorted using 00232 // std::__is_sorted 00233 template<typename _ForwardIterator, typename _Predicate> 00234 inline bool 00235 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00236 _Predicate __pred, std::forward_iterator_tag) 00237 { 00238 if (__first == __last) 00239 return true; 00240 00241 _ForwardIterator __next = __first; 00242 for (++__next; __next != __last; __first = __next, ++__next) 00243 if (__pred(*__next, *__first)) 00244 return false; 00245 00246 return true; 00247 } 00248 00249 // For performance reason, as the iterator range has been validated, check on 00250 // random access safe iterators is done using the base iterator. 00251 template<typename _Iterator, typename _Sequence, 00252 typename _Predicate> 00253 inline bool 00254 __check_sorted_aux(const _Safe_iterator<_Iterator, _Sequence>& __first, 00255 const _Safe_iterator<_Iterator, _Sequence>& __last, 00256 _Predicate __pred, 00257 std::random_access_iterator_tag __tag) 00258 { return __check_sorted_aux(__first.base(), __last.base(), __pred, __tag); } 00259 00260 // Determine if a sequence is sorted. 00261 template<typename _InputIterator> 00262 inline bool 00263 __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 00264 { 00265 // Verify that the < operator for elements in the sequence is a 00266 // StrictWeakOrdering by checking that it is irreflexive. 00267 __glibcxx_assert(__first == __last || !(*__first < *__first)); 00268 00269 return __check_sorted_aux(__first, __last, 00270 std::__iterator_category(__first)); 00271 } 00272 00273 template<typename _InputIterator, typename _Predicate> 00274 inline bool 00275 __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 00276 _Predicate __pred) 00277 { 00278 // Verify that the predicate is StrictWeakOrdering by checking that it 00279 // is irreflexive. 00280 __glibcxx_assert(__first == __last || !__pred(*__first, *__first)); 00281 00282 return __check_sorted_aux(__first, __last, __pred, 00283 std::__iterator_category(__first)); 00284 } 00285 00286 template<typename _InputIterator> 00287 inline bool 00288 __check_sorted_set_aux(const _InputIterator& __first, 00289 const _InputIterator& __last, 00290 std::__true_type) 00291 { return __check_sorted(__first, __last); } 00292 00293 template<typename _InputIterator> 00294 inline bool 00295 __check_sorted_set_aux(const _InputIterator&, 00296 const _InputIterator&, 00297 std::__false_type) 00298 { return true; } 00299 00300 template<typename _InputIterator, typename _Predicate> 00301 inline bool 00302 __check_sorted_set_aux(const _InputIterator& __first, 00303 const _InputIterator& __last, 00304 _Predicate __pred, std::__true_type) 00305 { return __check_sorted(__first, __last, __pred); } 00306 00307 template<typename _InputIterator, typename _Predicate> 00308 inline bool 00309 __check_sorted_set_aux(const _InputIterator&, 00310 const _InputIterator&, _Predicate, 00311 std::__false_type) 00312 { return true; } 00313 00314 // ... special variant used in std::merge, std::includes, std::set_*. 00315 template<typename _InputIterator1, typename _InputIterator2> 00316 inline bool 00317 __check_sorted_set(const _InputIterator1& __first, 00318 const _InputIterator1& __last, 00319 const _InputIterator2&) 00320 { 00321 typedef typename std::iterator_traits<_InputIterator1>::value_type 00322 _ValueType1; 00323 typedef typename std::iterator_traits<_InputIterator2>::value_type 00324 _ValueType2; 00325 00326 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00327 _SameType; 00328 return __check_sorted_set_aux(__first, __last, _SameType()); 00329 } 00330 00331 template<typename _InputIterator1, typename _InputIterator2, 00332 typename _Predicate> 00333 inline bool 00334 __check_sorted_set(const _InputIterator1& __first, 00335 const _InputIterator1& __last, 00336 const _InputIterator2&, _Predicate __pred) 00337 { 00338 typedef typename std::iterator_traits<_InputIterator1>::value_type 00339 _ValueType1; 00340 typedef typename std::iterator_traits<_InputIterator2>::value_type 00341 _ValueType2; 00342 00343 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00344 _SameType; 00345 return __check_sorted_set_aux(__first, __last, __pred, _SameType()); 00346 } 00347 00348 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00349 // 270. Binary search requirements overly strict 00350 // Determine if a sequence is partitioned w.r.t. this element. 00351 template<typename _ForwardIterator, typename _Tp> 00352 inline bool 00353 __check_partitioned_lower(_ForwardIterator __first, 00354 _ForwardIterator __last, const _Tp& __value) 00355 { 00356 while (__first != __last && *__first < __value) 00357 ++__first; 00358 if (__first != __last) 00359 { 00360 ++__first; 00361 while (__first != __last && !(*__first < __value)) 00362 ++__first; 00363 } 00364 return __first == __last; 00365 } 00366 00367 template<typename _ForwardIterator, typename _Tp> 00368 inline bool 00369 __check_partitioned_upper(_ForwardIterator __first, 00370 _ForwardIterator __last, const _Tp& __value) 00371 { 00372 while (__first != __last && !(__value < *__first)) 00373 ++__first; 00374 if (__first != __last) 00375 { 00376 ++__first; 00377 while (__first != __last && __value < *__first) 00378 ++__first; 00379 } 00380 return __first == __last; 00381 } 00382 00383 // Determine if a sequence is partitioned w.r.t. this element. 00384 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00385 inline bool 00386 __check_partitioned_lower(_ForwardIterator __first, 00387 _ForwardIterator __last, const _Tp& __value, 00388 _Pred __pred) 00389 { 00390 while (__first != __last && bool(__pred(*__first, __value))) 00391 ++__first; 00392 if (__first != __last) 00393 { 00394 ++__first; 00395 while (__first != __last && !bool(__pred(*__first, __value))) 00396 ++__first; 00397 } 00398 return __first == __last; 00399 } 00400 00401 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00402 inline bool 00403 __check_partitioned_upper(_ForwardIterator __first, 00404 _ForwardIterator __last, const _Tp& __value, 00405 _Pred __pred) 00406 { 00407 while (__first != __last && !bool(__pred(__value, *__first))) 00408 ++__first; 00409 if (__first != __last) 00410 { 00411 ++__first; 00412 while (__first != __last && bool(__pred(__value, *__first))) 00413 ++__first; 00414 } 00415 return __first == __last; 00416 } 00417 00418 // Helper struct to detect random access safe iterators. 00419 template<typename _Iterator> 00420 struct __is_safe_random_iterator 00421 { 00422 enum { __value = 0 }; 00423 typedef std::__false_type __type; 00424 }; 00425 00426 template<typename _Iterator, typename _Sequence> 00427 struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > 00428 : std::__are_same<std::random_access_iterator_tag, 00429 typename std::iterator_traits<_Iterator>:: 00430 iterator_category> 00431 { }; 00432 00433 template<typename _Iterator> 00434 struct _Siter_base 00435 : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value> 00436 { }; 00437 00438 /** Helper function to extract base iterator of random access safe iterator 00439 in order to reduce performance impact of debug mode. Limited to random 00440 access iterator because it is the only category for which it is possible 00441 to check for correct iterators order in the __valid_range function 00442 thanks to the < operator. 00443 */ 00444 template<typename _Iterator> 00445 inline typename _Siter_base<_Iterator>::iterator_type 00446 __base(_Iterator __it) 00447 { return _Siter_base<_Iterator>::_S_base(__it); } 00448 } // namespace __gnu_debug 00449 00450 #endif