libstdc++
functions.h
Go to the documentation of this file.
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