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
00031
00032
00033
00034
00035 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
00036 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1
00037
00038 #include <bits/c++config.h>
00039 #include <cstddef>
00040 #include <bits/stl_iterator_base_types.h>
00041 #include <bits/cpp_type_traits.h>
00042
00043 namespace __gnu_debug
00044 {
00045 template<typename _Iterator, typename _Sequence>
00046 class _Safe_iterator;
00047
00048
00049 inline bool
00050 __check_singular_aux(const void*) { return false; }
00051
00052
00053
00054 template<typename _Iterator>
00055 inline bool
00056 __check_singular(_Iterator& __x)
00057 { return __check_singular_aux(&__x); }
00058
00059
00060 template<typename _Tp>
00061 inline bool
00062 __check_singular(const _Tp* __ptr)
00063 { return __ptr == 0; }
00064
00065
00066 template<typename _Iterator, typename _Sequence>
00067 inline bool
00068 __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x)
00069 { return __x._M_singular(); }
00070
00071
00072
00073 template<typename _Iterator>
00074 inline bool
00075 __check_dereferenceable(_Iterator&)
00076 { return true; }
00077
00078
00079 template<typename _Tp>
00080 inline bool
00081 __check_dereferenceable(const _Tp* __ptr)
00082 { return __ptr; }
00083
00084
00085 template<typename _Iterator, typename _Sequence>
00086 inline bool
00087 __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
00088 { return __x._M_dereferenceable(); }
00089
00090
00091
00092
00093 template<typename _RandomAccessIterator>
00094 inline bool
00095 __valid_range_aux2(const _RandomAccessIterator& __first,
00096 const _RandomAccessIterator& __last,
00097 std::random_access_iterator_tag)
00098 { return __last - __first >= 0; }
00099
00100
00101
00102
00103
00104 template<typename _InputIterator>
00105 inline bool
00106 __valid_range_aux2(const _InputIterator&, const _InputIterator&,
00107 std::input_iterator_tag)
00108 { return true; }
00109
00110
00111
00112
00113
00114 template<typename _Integral>
00115 inline bool
00116 __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
00117 { return true; }
00118
00119
00120
00121
00122 template<typename _InputIterator>
00123 inline bool
00124 __valid_range_aux(const _InputIterator& __first,
00125 const _InputIterator& __last, std::__false_type)
00126 {
00127 typedef typename std::iterator_traits<_InputIterator>::iterator_category
00128 _Category;
00129 return __valid_range_aux2(__first, __last, _Category());
00130 }
00131
00132
00133
00134
00135
00136
00137 template<typename _InputIterator>
00138 inline bool
00139 __valid_range(const _InputIterator& __first, const _InputIterator& __last)
00140 {
00141 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00142 return __valid_range_aux(__first, __last, _Integral());
00143 }
00144
00145
00146 template<typename _Iterator, typename _Sequence>
00147 inline bool
00148 __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
00149 const _Safe_iterator<_Iterator, _Sequence>& __last)
00150 { return __first._M_valid_range(__last); }
00151
00152
00153
00154
00155
00156 template<typename _InputIterator>
00157 inline _InputIterator
00158 __check_valid_range(const _InputIterator& __first,
00159 const _InputIterator& __last
00160 __attribute__((__unused__)))
00161 {
00162 _GLIBCXX_DEBUG_ASSERT(__valid_range(__first, __last));
00163 return __first;
00164 }
00165
00166
00167 template<typename _CharT, typename _Integer>
00168 inline const _CharT*
00169 __check_string(const _CharT* __s,
00170 const _Integer& __n __attribute__((__unused__)))
00171 {
00172 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00173 _GLIBCXX_DEBUG_ASSERT(__s != 0 || __n == 0);
00174 #endif
00175 return __s;
00176 }
00177
00178
00179 template<typename _CharT>
00180 inline const _CharT*
00181 __check_string(const _CharT* __s)
00182 {
00183 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00184 _GLIBCXX_DEBUG_ASSERT(__s != 0);
00185 #endif
00186 return __s;
00187 }
00188
00189
00190
00191 template<typename _InputIterator>
00192 inline bool
00193 __check_sorted_aux(const _InputIterator&, const _InputIterator&,
00194 std::input_iterator_tag)
00195 { return true; }
00196
00197
00198
00199 template<typename _ForwardIterator>
00200 inline bool
00201 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
00202 std::forward_iterator_tag)
00203 {
00204 if (__first == __last)
00205 return true;
00206
00207 _ForwardIterator __next = __first;
00208 for (++__next; __next != __last; __first = __next, ++__next)
00209 if (*__next < *__first)
00210 return false;
00211
00212 return true;
00213 }
00214
00215
00216
00217 template<typename _InputIterator, typename _Predicate>
00218 inline bool
00219 __check_sorted_aux(const _InputIterator&, const _InputIterator&,
00220 _Predicate, std::input_iterator_tag)
00221 { return true; }
00222
00223
00224
00225 template<typename _ForwardIterator, typename _Predicate>
00226 inline bool
00227 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
00228 _Predicate __pred, std::forward_iterator_tag)
00229 {
00230 if (__first == __last)
00231 return true;
00232
00233 _ForwardIterator __next = __first;
00234 for (++__next; __next != __last; __first = __next, ++__next)
00235 if (__pred(*__next, *__first))
00236 return false;
00237
00238 return true;
00239 }
00240
00241
00242 template<typename _InputIterator>
00243 inline bool
00244 __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
00245 {
00246 typedef typename std::iterator_traits<_InputIterator>::iterator_category
00247 _Category;
00248
00249
00250
00251 _GLIBCXX_DEBUG_ASSERT(__first == __last || !(*__first < *__first));
00252
00253 return __check_sorted_aux(__first, __last, _Category());
00254 }
00255
00256 template<typename _InputIterator, typename _Predicate>
00257 inline bool
00258 __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
00259 _Predicate __pred)
00260 {
00261 typedef typename std::iterator_traits<_InputIterator>::iterator_category
00262 _Category;
00263
00264
00265
00266 _GLIBCXX_DEBUG_ASSERT(__first == __last || !__pred(*__first, *__first));
00267
00268 return __check_sorted_aux(__first, __last, __pred, _Category());
00269 }
00270
00271 template<typename _InputIterator>
00272 inline bool
00273 __check_sorted_set_aux(const _InputIterator& __first,
00274 const _InputIterator& __last,
00275 std::__true_type)
00276 { return __check_sorted(__first, __last); }
00277
00278 template<typename _InputIterator>
00279 inline bool
00280 __check_sorted_set_aux(const _InputIterator&,
00281 const _InputIterator&,
00282 std::__false_type)
00283 { return true; }
00284
00285 template<typename _InputIterator, typename _Predicate>
00286 inline bool
00287 __check_sorted_set_aux(const _InputIterator& __first,
00288 const _InputIterator& __last,
00289 _Predicate __pred, std::__true_type)
00290 { return __check_sorted(__first, __last, __pred); }
00291
00292 template<typename _InputIterator, typename _Predicate>
00293 inline bool
00294 __check_sorted_set_aux(const _InputIterator&,
00295 const _InputIterator&, _Predicate,
00296 std::__false_type)
00297 { return true; }
00298
00299
00300 template<typename _InputIterator1, typename _InputIterator2>
00301 inline bool
00302 __check_sorted_set(const _InputIterator1& __first,
00303 const _InputIterator1& __last,
00304 const _InputIterator2&)
00305 {
00306 typedef typename std::iterator_traits<_InputIterator1>::value_type
00307 _ValueType1;
00308 typedef typename std::iterator_traits<_InputIterator2>::value_type
00309 _ValueType2;
00310
00311 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
00312 _SameType;
00313 return __check_sorted_set_aux(__first, __last, _SameType());
00314 }
00315
00316 template<typename _InputIterator1, typename _InputIterator2,
00317 typename _Predicate>
00318 inline bool
00319 __check_sorted_set(const _InputIterator1& __first,
00320 const _InputIterator1& __last,
00321 const _InputIterator2&, _Predicate __pred)
00322 {
00323 typedef typename std::iterator_traits<_InputIterator1>::value_type
00324 _ValueType1;
00325 typedef typename std::iterator_traits<_InputIterator2>::value_type
00326 _ValueType2;
00327
00328 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
00329 _SameType;
00330 return __check_sorted_set_aux(__first, __last, __pred, _SameType());
00331 }
00332
00333
00334
00335
00336 template<typename _ForwardIterator, typename _Tp>
00337 inline bool
00338 __check_partitioned_lower(_ForwardIterator __first,
00339 _ForwardIterator __last, const _Tp& __value)
00340 {
00341 while (__first != __last && *__first < __value)
00342 ++__first;
00343 while (__first != __last && !(*__first < __value))
00344 ++__first;
00345 return __first == __last;
00346 }
00347
00348 template<typename _ForwardIterator, typename _Tp>
00349 inline bool
00350 __check_partitioned_upper(_ForwardIterator __first,
00351 _ForwardIterator __last, const _Tp& __value)
00352 {
00353 while (__first != __last && !(__value < *__first))
00354 ++__first;
00355 while (__first != __last && __value < *__first)
00356 ++__first;
00357 return __first == __last;
00358 }
00359
00360
00361 template<typename _ForwardIterator, typename _Tp, typename _Pred>
00362 inline bool
00363 __check_partitioned_lower(_ForwardIterator __first,
00364 _ForwardIterator __last, const _Tp& __value,
00365 _Pred __pred)
00366 {
00367 while (__first != __last && bool(__pred(*__first, __value)))
00368 ++__first;
00369 while (__first != __last && !bool(__pred(*__first, __value)))
00370 ++__first;
00371 return __first == __last;
00372 }
00373
00374 template<typename _ForwardIterator, typename _Tp, typename _Pred>
00375 inline bool
00376 __check_partitioned_upper(_ForwardIterator __first,
00377 _ForwardIterator __last, const _Tp& __value,
00378 _Pred __pred)
00379 {
00380 while (__first != __last && !bool(__pred(__value, *__first)))
00381 ++__first;
00382 while (__first != __last && bool(__pred(__value, *__first)))
00383 ++__first;
00384 return __first == __last;
00385 }
00386 }
00387
00388 #endif