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 template<typename _ForwardIterator, typename _Tp> 00349 inline bool 00350 __check_partitioned_lower_aux(_ForwardIterator __first, 00351 _ForwardIterator __last, const _Tp& __value, 00352 std::forward_iterator_tag) 00353 { 00354 while (__first != __last && *__first < __value) 00355 ++__first; 00356 if (__first != __last) 00357 { 00358 ++__first; 00359 while (__first != __last && !(*__first < __value)) 00360 ++__first; 00361 } 00362 return __first == __last; 00363 } 00364 00365 // For performance reason, as the iterator range has been validated, check on 00366 // random access safe iterators is done using the base iterator. 00367 template<typename _Iterator, typename _Sequence, typename _Tp> 00368 inline bool 00369 __check_partitioned_lower_aux( 00370 const _Safe_iterator<_Iterator, _Sequence>& __first, 00371 const _Safe_iterator<_Iterator, _Sequence>& __last, 00372 const _Tp& __value, 00373 std::random_access_iterator_tag __tag) 00374 { 00375 return __check_partitioned_lower_aux(__first.base(), __last.base(), 00376 __value, __tag); 00377 } 00378 00379 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00380 // 270. Binary search requirements overly strict 00381 // Determine if a sequence is partitioned w.r.t. this element. 00382 template<typename _ForwardIterator, typename _Tp> 00383 inline bool 00384 __check_partitioned_lower(_ForwardIterator __first, 00385 _ForwardIterator __last, const _Tp& __value) 00386 { 00387 return __check_partitioned_lower_aux(__first, __last, __value, 00388 std::__iterator_category(__first)); 00389 } 00390 00391 template<typename _ForwardIterator, typename _Tp> 00392 inline bool 00393 __check_partitioned_upper_aux(_ForwardIterator __first, 00394 _ForwardIterator __last, const _Tp& __value, 00395 std::forward_iterator_tag) 00396 { 00397 while (__first != __last && !(__value < *__first)) 00398 ++__first; 00399 if (__first != __last) 00400 { 00401 ++__first; 00402 while (__first != __last && __value < *__first) 00403 ++__first; 00404 } 00405 return __first == __last; 00406 } 00407 00408 // For performance reason, as the iterator range has been validated, check on 00409 // random access safe iterators is done using the base iterator. 00410 template<typename _Iterator, typename _Sequence, typename _Tp> 00411 inline bool 00412 __check_partitioned_upper_aux( 00413 const _Safe_iterator<_Iterator, _Sequence>& __first, 00414 const _Safe_iterator<_Iterator, _Sequence>& __last, 00415 const _Tp& __value, 00416 std::random_access_iterator_tag __tag) 00417 { 00418 return __check_partitioned_upper_aux(__first.base(), __last.base(), 00419 __value, __tag); 00420 } 00421 00422 template<typename _ForwardIterator, typename _Tp> 00423 inline bool 00424 __check_partitioned_upper(_ForwardIterator __first, 00425 _ForwardIterator __last, const _Tp& __value) 00426 { 00427 return __check_partitioned_upper_aux(__first, __last, __value, 00428 std::__iterator_category(__first)); 00429 } 00430 00431 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00432 inline bool 00433 __check_partitioned_lower_aux(_ForwardIterator __first, 00434 _ForwardIterator __last, const _Tp& __value, 00435 _Pred __pred, 00436 std::forward_iterator_tag) 00437 { 00438 while (__first != __last && bool(__pred(*__first, __value))) 00439 ++__first; 00440 if (__first != __last) 00441 { 00442 ++__first; 00443 while (__first != __last && !bool(__pred(*__first, __value))) 00444 ++__first; 00445 } 00446 return __first == __last; 00447 } 00448 00449 // For performance reason, as the iterator range has been validated, check on 00450 // random access safe iterators is done using the base iterator. 00451 template<typename _Iterator, typename _Sequence, 00452 typename _Tp, typename _Pred> 00453 inline bool 00454 __check_partitioned_lower_aux( 00455 const _Safe_iterator<_Iterator, _Sequence>& __first, 00456 const _Safe_iterator<_Iterator, _Sequence>& __last, 00457 const _Tp& __value, _Pred __pred, 00458 std::random_access_iterator_tag __tag) 00459 { 00460 return __check_partitioned_lower_aux(__first.base(), __last.base(), 00461 __value, __pred, __tag); 00462 } 00463 00464 // Determine if a sequence is partitioned w.r.t. this element. 00465 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00466 inline bool 00467 __check_partitioned_lower(_ForwardIterator __first, 00468 _ForwardIterator __last, const _Tp& __value, 00469 _Pred __pred) 00470 { 00471 return __check_partitioned_lower_aux(__first, __last, __value, __pred, 00472 std::__iterator_category(__first)); 00473 } 00474 00475 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00476 inline bool 00477 __check_partitioned_upper_aux(_ForwardIterator __first, 00478 _ForwardIterator __last, const _Tp& __value, 00479 _Pred __pred, 00480 std::forward_iterator_tag) 00481 { 00482 while (__first != __last && !bool(__pred(__value, *__first))) 00483 ++__first; 00484 if (__first != __last) 00485 { 00486 ++__first; 00487 while (__first != __last && bool(__pred(__value, *__first))) 00488 ++__first; 00489 } 00490 return __first == __last; 00491 } 00492 00493 // For performance reason, as the iterator range has been validated, check on 00494 // random access safe iterators is done using the base iterator. 00495 template<typename _Iterator, typename _Sequence, 00496 typename _Tp, typename _Pred> 00497 inline bool 00498 __check_partitioned_upper_aux( 00499 const _Safe_iterator<_Iterator, _Sequence>& __first, 00500 const _Safe_iterator<_Iterator, _Sequence>& __last, 00501 const _Tp& __value, _Pred __pred, 00502 std::random_access_iterator_tag __tag) 00503 { 00504 return __check_partitioned_upper_aux(__first.base(), __last.base(), 00505 __value, __pred, __tag); 00506 } 00507 00508 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00509 inline bool 00510 __check_partitioned_upper(_ForwardIterator __first, 00511 _ForwardIterator __last, const _Tp& __value, 00512 _Pred __pred) 00513 { 00514 return __check_partitioned_upper_aux(__first, __last, __value, __pred, 00515 std::__iterator_category(__first)); 00516 } 00517 00518 // Helper struct to detect random access safe iterators. 00519 template<typename _Iterator> 00520 struct __is_safe_random_iterator 00521 { 00522 enum { __value = 0 }; 00523 typedef std::__false_type __type; 00524 }; 00525 00526 template<typename _Iterator, typename _Sequence> 00527 struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > 00528 : std::__are_same<std::random_access_iterator_tag, 00529 typename std::iterator_traits<_Iterator>:: 00530 iterator_category> 00531 { }; 00532 00533 template<typename _Iterator> 00534 struct _Siter_base 00535 : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value> 00536 { }; 00537 00538 /** Helper function to extract base iterator of random access safe iterator 00539 in order to reduce performance impact of debug mode. Limited to random 00540 access iterator because it is the only category for which it is possible 00541 to check for correct iterators order in the __valid_range function 00542 thanks to the < operator. 00543 */ 00544 template<typename _Iterator> 00545 inline typename _Siter_base<_Iterator>::iterator_type 00546 __base(_Iterator __it) 00547 { return _Siter_base<_Iterator>::_S_base(__it); } 00548 } // namespace __gnu_debug 00549 00550 #endif