functions.h

Go to the documentation of this file.
00001 // Debugging support implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 2, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /** @file debug/functions.h
00032  *  This file is a GNU debug extension to the Standard C++ Library.
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>                       // for ptrdiff_t
00040 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories
00041 #include <bits/cpp_type_traits.h>         // for __is_integer
00042 
00043 namespace __gnu_debug
00044 {
00045   template<typename _Iterator, typename _Sequence>
00046     class _Safe_iterator;
00047 
00048   // An arbitrary iterator pointer is not singular.
00049   inline bool
00050   __check_singular_aux(const void*) { return false; }
00051 
00052   // We may have an iterator that derives from _Safe_iterator_base but isn't
00053   // a _Safe_iterator.
00054   template<typename _Iterator>
00055     inline bool
00056     __check_singular(_Iterator& __x)
00057     { return __check_singular_aux(&__x); }
00058 
00059   /** Non-NULL pointers are nonsingular. */
00060   template<typename _Tp>
00061     inline bool
00062     __check_singular(const _Tp* __ptr)
00063     { return __ptr == 0; }
00064 
00065   /** Safe iterators know if they are singular. */
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   /** Assume that some arbitrary iterator is dereferenceable, because we
00072       can't prove that it isn't. */
00073   template<typename _Iterator>
00074     inline bool
00075     __check_dereferenceable(_Iterator&)
00076     { return true; }
00077 
00078   /** Non-NULL pointers are dereferenceable. */
00079   template<typename _Tp>
00080     inline bool
00081     __check_dereferenceable(const _Tp* __ptr)
00082     { return __ptr; }
00083 
00084   /** Safe iterators know if they are singular. */
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   /** If the distance between two random access iterators is
00091    *  nonnegative, assume the range is valid.
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   /** Can't test for a valid range with input iterators, because
00101    *  iteration may be destructive. So we just assume that the range
00102    *  is valid.
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   /** We say that integral types for a valid range, and defer to other
00111    *  routines to realize what to do with integral types instead of
00112    *  iterators.
00113   */
00114   template<typename _Integral>
00115     inline bool
00116     __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
00117     { return true; }
00118 
00119   /** We have iterators, so figure out what kind of iterators that are
00120    *  to see if we can check the range ahead of time.
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   /** Don't know what these iterators are, or if they are even
00133    *  iterators (we may get an integral type for InputIterator), so
00134    *  see if they are integral and pass them on to the next phase
00135    *  otherwise.
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   /** Safe iterators know how to check if they form a valid range. */
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   /* Checks that [first, last) is a valid range, and then returns
00153    * __first. This routine is useful when we can't use a separate
00154    * assertion statement because, e.g., we are in a constructor.
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   /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
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   /** Checks that __s is non-NULL and then returns __s. */
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   // Can't check if an input iterator sequence is sorted, because we
00190   // can't step through the sequence.
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   // Can verify if a forward iterator sequence is in fact sorted using
00198   // std::__is_sorted
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   // Can't check if an input iterator sequence is sorted, because we can't step
00216   // through the sequence.
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   // Can verify if a forward iterator sequence is in fact sorted using
00224   // std::__is_sorted
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   // Determine if a sequence is sorted.
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       // Verify that the < operator for elements in the sequence is a
00250       // StrictWeakOrdering by checking that it is irreflexive.
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       // Verify that the predicate is StrictWeakOrdering by checking that it
00265       // is irreflexive.
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   // ... special variant used in std::merge, std::includes, std::set_*.
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   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00334   // 270. Binary search requirements overly strict
00335   // Determine if a sequence is partitioned w.r.t. this element.
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   // Determine if a sequence is partitioned w.r.t. this element.
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 } // namespace __gnu_debug
00387 
00388 #endif

Generated on Wed Dec 31 12:48:55 2008 for libstdc++ by  doxygen 1.5.6