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   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