libstdc++
helper_functions.h
Go to the documentation of this file.
00001 // Debugging support implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2019 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/helper_functions.h
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H
00030 #define _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H 1
00031 
00032 #include <bits/stl_iterator_base_types.h>       // for iterator_traits,
00033                                                 // categories and _Iter_base
00034 #include <bits/cpp_type_traits.h>               // for __is_integer
00035 
00036 #include <bits/stl_pair.h>                      // for pair
00037 
00038 namespace __gnu_debug
00039 {
00040   template<typename _Iterator, typename _Sequence, typename _Category>
00041     class _Safe_iterator;
00042 
00043 #if __cplusplus >= 201103L
00044   template<typename _Iterator, typename _Sequence>
00045     class _Safe_local_iterator;
00046 #endif
00047 
00048   /** The precision to which we can calculate the distance between
00049    *  two iterators.
00050    */
00051   enum _Distance_precision
00052     {
00053       __dp_none,        // Not even an iterator type
00054       __dp_equality,    //< Can compare iterator equality, only
00055       __dp_sign,        //< Can determine equality and ordering
00056       __dp_exact        //< Can determine distance precisely
00057     };
00058 
00059   template<typename _Iterator,
00060            typename = typename std::__is_integer<_Iterator>::__type>
00061     struct _Distance_traits
00062     {
00063     private:
00064       typedef
00065       typename std::iterator_traits<_Iterator>::difference_type _ItDiffType;
00066 
00067       template<typename _DiffType,
00068                typename = typename std::__is_void<_DiffType>::__type>
00069         struct _DiffTraits
00070         { typedef _DiffType __type; };
00071 
00072       template<typename _DiffType>
00073         struct _DiffTraits<_DiffType, std::__true_type>
00074         { typedef std::ptrdiff_t __type; };
00075 
00076       typedef typename _DiffTraits<_ItDiffType>::__type _DiffType;
00077 
00078     public:
00079       typedef std::pair<_DiffType, _Distance_precision> __type;
00080     };
00081 
00082   template<typename _Integral>
00083     struct _Distance_traits<_Integral, std::__true_type>
00084     { typedef std::pair<std::ptrdiff_t, _Distance_precision> __type; };
00085 
00086   /** Determine the distance between two iterators with some known
00087    *    precision.
00088   */
00089   template<typename _Iterator>
00090     inline typename _Distance_traits<_Iterator>::__type
00091     __get_distance(_Iterator __lhs, _Iterator __rhs,
00092                    std::random_access_iterator_tag)
00093     { return std::make_pair(__rhs - __lhs, __dp_exact); }
00094 
00095   template<typename _Iterator>
00096     inline typename _Distance_traits<_Iterator>::__type
00097     __get_distance(_Iterator __lhs, _Iterator __rhs,
00098                    std::input_iterator_tag)
00099     {
00100       if (__lhs == __rhs)
00101         return std::make_pair(0, __dp_exact);
00102 
00103       return std::make_pair(1, __dp_equality);
00104     }
00105 
00106   template<typename _Iterator>
00107     inline typename _Distance_traits<_Iterator>::__type
00108     __get_distance(_Iterator __lhs, _Iterator __rhs)
00109     { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); }
00110 
00111   /** We say that integral types for a valid range, and defer to other
00112    *  routines to realize what to do with integral types instead of
00113    *  iterators.
00114   */
00115   template<typename _Integral>
00116     inline bool
00117     __valid_range_aux(_Integral, _Integral,
00118                       typename _Distance_traits<_Integral>::__type& __dist,
00119                       std::__true_type)
00120     {
00121       __dist = std::make_pair(0, __dp_none);
00122       return true;
00123     }
00124 
00125   /** We have iterators, so figure out what kind of iterators they are
00126    *  to see if we can check the range ahead of time.
00127   */
00128   template<typename _InputIterator>
00129     inline bool
00130     __valid_range_aux(_InputIterator __first, _InputIterator __last,
00131                       typename _Distance_traits<_InputIterator>::__type& __dist,
00132                       std::__false_type)
00133     {
00134       __dist = __get_distance(__first, __last);
00135       switch (__dist.second)
00136         {
00137         case __dp_none:
00138           break;
00139         case __dp_equality:
00140           if (__dist.first == 0)
00141             return true;
00142           break;
00143         case __dp_sign:
00144         case __dp_exact:
00145           return __dist.first >= 0;
00146         }
00147 
00148       // Can't tell so assume it is fine.
00149       return true;
00150     }
00151 
00152   /** Don't know what these iterators are, or if they are even
00153    *  iterators (we may get an integral type for InputIterator), so
00154    *  see if they are integral and pass them on to the next phase
00155    *  otherwise.
00156   */
00157   template<typename _InputIterator>
00158     inline bool
00159     __valid_range(_InputIterator __first, _InputIterator __last,
00160                   typename _Distance_traits<_InputIterator>::__type& __dist)
00161     {
00162       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00163       return __valid_range_aux(__first, __last, __dist, _Integral());
00164     }
00165 
00166   template<typename _Iterator, typename _Sequence, typename _Category>
00167     bool
00168     __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
00169                   const _Safe_iterator<_Iterator, _Sequence, _Category>&,
00170                   typename _Distance_traits<_Iterator>::__type&);
00171 
00172 #if __cplusplus >= 201103L
00173   template<typename _Iterator,typename _Sequence>
00174     bool
00175     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
00176                   const _Safe_local_iterator<_Iterator, _Sequence>&,
00177                   typename _Distance_traits<_Iterator>::__type&);
00178 #endif
00179 
00180   template<typename _InputIterator>
00181     inline bool
00182     __valid_range(_InputIterator __first, _InputIterator __last)
00183     {
00184       typename _Distance_traits<_InputIterator>::__type __dist;
00185       return __valid_range(__first, __last, __dist);
00186     }
00187 
00188   template<typename _Iterator, typename _Sequence, typename _Category>
00189     bool
00190     __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
00191                   const _Safe_iterator<_Iterator, _Sequence, _Category>&);
00192 
00193 #if __cplusplus >= 201103L
00194   template<typename _Iterator, typename _Sequence>
00195     bool
00196     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
00197                   const _Safe_local_iterator<_Iterator, _Sequence>&);
00198 #endif
00199 
00200   // Fallback method, always ok.
00201   template<typename _InputIterator, typename _Size>
00202     inline bool
00203     __can_advance(_InputIterator, _Size)
00204     { return true; }
00205 
00206   template<typename _Iterator, typename _Sequence, typename _Category,
00207            typename _Size>
00208     bool
00209     __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
00210                   _Size);
00211 
00212   /** Helper function to extract base iterator of random access safe iterator
00213    *  in order to reduce performance impact of debug mode.  Limited to random
00214    *  access iterator because it is the only category for which it is possible
00215    *  to check for correct iterators order in the __valid_range function
00216    *  thanks to the < operator.
00217    */
00218   template<typename _Iterator>
00219     inline _Iterator
00220     __base(_Iterator __it)
00221     { return __it; }
00222 
00223 #if __cplusplus < 201103L
00224   template<typename _Iterator>
00225     struct _Unsafe_type
00226     { typedef _Iterator _Type; };
00227 #endif
00228 
00229   /* Remove debug mode safe iterator layer, if any. */
00230   template<typename _Iterator>
00231     inline _Iterator
00232     __unsafe(_Iterator __it)
00233     { return __it; }
00234 }
00235 
00236 #endif