00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
00031 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1
00032
00033 #include <bits/c++config.h>
00034 #include <cstddef>
00035 #include <bits/stl_iterator_base_types.h>
00036 #include <bits/cpp_type_traits.h>
00037
00038 namespace __gnu_debug
00039 {
00040 template<typename _Iterator, typename _Sequence>
00041 class _Safe_iterator;
00042
00043
00044 inline bool
00045 __check_singular_aux(const void*) { return false; }
00046
00047
00048
00049 template<typename _Iterator>
00050 inline bool
00051 __check_singular(_Iterator& __x)
00052 { return __check_singular_aux(&__x); }
00053
00054
00055 template<typename _Tp>
00056 inline bool
00057 __check_singular(const _Tp* __ptr)
00058 { return __ptr == 0; }
00059
00060
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
00067
00068 template<typename _Iterator>
00069 inline bool
00070 __check_dereferenceable(_Iterator&)
00071 { return true; }
00072
00073
00074 template<typename _Tp>
00075 inline bool
00076 __check_dereferenceable(const _Tp* __ptr)
00077 { return __ptr; }
00078
00079
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
00086
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
00096
00097
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
00106
00107
00108
00109 template<typename _Integral>
00110 inline bool
00111 __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
00112 { return true; }
00113
00114
00115
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
00128
00129
00130
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
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
00148
00149
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_DEBUG_ASSERT(__valid_range(__first, __last));
00158 return __first;
00159 }
00160
00161
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_DEBUG_ASSERT(__s != 0 || __n == 0);
00169 #endif
00170 return __s;
00171 }
00172
00173
00174 template<typename _CharT>
00175 inline const _CharT*
00176 __check_string(const _CharT* __s)
00177 {
00178 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00179 _GLIBCXX_DEBUG_ASSERT(__s != 0);
00180 #endif
00181 return __s;
00182 }
00183
00184
00185
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
00193
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
00211
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
00219
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
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
00245
00246 _GLIBCXX_DEBUG_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
00260
00261 _GLIBCXX_DEBUG_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
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
00329
00330
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
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 }
00382
00383 #endif