libstdc++
pointer.h
Go to the documentation of this file.
00001 // Custom pointer adapter and sample storage policies
00002 
00003 // Copyright (C) 2008-2015 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 /**
00026  *  @file ext/pointer.h
00027  *  This file is a GNU extension to the Standard C++ Library.
00028  *
00029  *  @author Bob Walters
00030  *
00031  * Provides reusable _Pointer_adapter for assisting in the development of
00032  * custom pointer types that can be used with the standard containers via
00033  * the allocator::pointer and allocator::const_pointer typedefs.
00034  */
00035 
00036 #ifndef _POINTER_H
00037 #define _POINTER_H 1
00038 
00039 #pragma GCC system_header
00040 
00041 #include <iosfwd>
00042 #include <bits/stl_iterator_base_types.h>
00043 #include <ext/cast.h>
00044 #include <ext/type_traits.h>
00045 #if __cplusplus >= 201103L
00046 # include <bits/move.h>
00047 # include <bits/ptr_traits.h>
00048 #endif
00049 
00050 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00051 {
00052 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00053 
00054   /** 
00055    * @brief A storage policy for use with _Pointer_adapter<> which yields a
00056    *        standard pointer.
00057    * 
00058    *  A _Storage_policy is required to provide 4 things:
00059    *    1) A get() API for returning the stored pointer value.
00060    *    2) An set() API for storing a pointer value.
00061    *    3) An element_type typedef to define the type this points to.
00062    *    4) An operator<() to support pointer comparison.
00063    *    5) An operator==() to support pointer comparison.
00064    */
00065   template<typename _Tp> 
00066     class _Std_pointer_impl 
00067     {
00068     public:
00069       // the type this pointer points to.
00070       typedef _Tp element_type;
00071   
00072       // A method to fetch the pointer value as a standard T* value;
00073       inline _Tp* 
00074       get() const 
00075       { return _M_value; }
00076   
00077       // A method to set the pointer value, from a standard T* value;
00078       inline void 
00079       set(element_type* __arg) 
00080       { _M_value = __arg; }
00081   
00082       // Comparison of pointers
00083       inline bool
00084       operator<(const _Std_pointer_impl& __rarg) const
00085       { return (_M_value < __rarg._M_value); }
00086   
00087       inline bool
00088       operator==(const _Std_pointer_impl& __rarg) const
00089       { return (_M_value == __rarg._M_value); }
00090 
00091     private:
00092       element_type* _M_value;
00093     };
00094 
00095   /**
00096    * @brief A storage policy for use with _Pointer_adapter<> which stores
00097    *        the pointer's address as an offset value which is relative to
00098    *        its own address.
00099    * 
00100    * This is intended for pointers within shared memory regions which
00101    * might be mapped at different addresses by different processes.
00102    * For null pointers, a value of 1 is used.  (0 is legitimate
00103    * sometimes for nodes in circularly linked lists) This value was
00104    * chosen as the least likely to generate an incorrect null, As
00105    * there is no reason why any normal pointer would point 1 byte into
00106    * its own pointer address.
00107    */
00108   template<typename _Tp> 
00109     class _Relative_pointer_impl 
00110     {
00111     public:
00112       typedef _Tp element_type;
00113   
00114       _Tp*
00115       get() const 
00116       {
00117         if (_M_diff == 1)
00118           return 0;
00119         else
00120           return reinterpret_cast<_Tp*>(reinterpret_cast<_UIntPtrType>(this)
00121                                         + _M_diff);
00122       }
00123   
00124       void 
00125       set(_Tp* __arg)
00126       {
00127         if (!__arg)
00128           _M_diff = 1;
00129         else
00130           _M_diff = reinterpret_cast<_UIntPtrType>(__arg) 
00131                     - reinterpret_cast<_UIntPtrType>(this);
00132       }
00133   
00134       // Comparison of pointers
00135       inline bool
00136       operator<(const _Relative_pointer_impl& __rarg) const
00137       { return (reinterpret_cast<_UIntPtrType>(this->get())
00138                 < reinterpret_cast<_UIntPtrType>(__rarg.get())); }
00139 
00140       inline bool
00141       operator==(const _Relative_pointer_impl& __rarg) const
00142       { return (reinterpret_cast<_UIntPtrType>(this->get())
00143                 == reinterpret_cast<_UIntPtrType>(__rarg.get())); }
00144 
00145     private:
00146 #ifdef _GLIBCXX_USE_LONG_LONG
00147       typedef __gnu_cxx::__conditional_type<
00148          (sizeof(unsigned long) >= sizeof(void*)),
00149          unsigned long, unsigned long long>::__type _UIntPtrType;
00150 #else
00151       typedef unsigned long _UIntPtrType;
00152 #endif
00153       _UIntPtrType _M_diff;
00154     };
00155   
00156   /**
00157    * Relative_pointer_impl needs a specialization for const T because of
00158    * the casting done during pointer arithmetic.
00159    */
00160   template<typename _Tp> 
00161     class _Relative_pointer_impl<const _Tp> 
00162     {
00163     public:
00164       typedef const _Tp element_type;
00165   
00166       const _Tp*
00167       get() const
00168       {
00169         if (_M_diff == 1)
00170           return 0;
00171         else
00172           return reinterpret_cast<const _Tp*>
00173               (reinterpret_cast<_UIntPtrType>(this) + _M_diff);
00174       }
00175   
00176       void 
00177       set(const _Tp* __arg)
00178       {
00179         if (!__arg)
00180           _M_diff = 1;
00181         else
00182           _M_diff = reinterpret_cast<_UIntPtrType>(__arg) 
00183                     - reinterpret_cast<_UIntPtrType>(this);
00184       }
00185   
00186       // Comparison of pointers
00187       inline bool
00188       operator<(const _Relative_pointer_impl& __rarg) const
00189       { return (reinterpret_cast<_UIntPtrType>(this->get())
00190                 < reinterpret_cast<_UIntPtrType>(__rarg.get())); }
00191 
00192       inline bool
00193       operator==(const _Relative_pointer_impl& __rarg) const
00194       { return (reinterpret_cast<_UIntPtrType>(this->get())
00195                 == reinterpret_cast<_UIntPtrType>(__rarg.get())); }
00196   
00197     private:
00198 #ifdef _GLIBCXX_USE_LONG_LONG
00199       typedef __gnu_cxx::__conditional_type<
00200          (sizeof(unsigned long) >= sizeof(void*)),
00201          unsigned long, unsigned long long>::__type _UIntPtrType;
00202 #else
00203       typedef unsigned long _UIntPtrType;
00204 #endif
00205        _UIntPtrType _M_diff;
00206     };
00207 
00208   /**
00209    * The specialization on this type helps resolve the problem of
00210    * reference to void, and eliminates the need to specialize
00211    * _Pointer_adapter for cases of void*, const void*, and so on.
00212    */
00213   struct _Invalid_type { };
00214   
00215   template<typename _Tp>
00216     struct _Reference_type 
00217     { typedef _Tp& reference; };
00218 
00219   template<> 
00220     struct _Reference_type<void> 
00221     { typedef _Invalid_type& reference; };
00222 
00223   template<> 
00224     struct _Reference_type<const void> 
00225     { typedef const _Invalid_type& reference; };
00226 
00227   template<> 
00228     struct _Reference_type<volatile void> 
00229     { typedef volatile _Invalid_type&  reference; };
00230 
00231   template<> 
00232     struct _Reference_type<volatile const void> 
00233     { typedef const volatile _Invalid_type&  reference; };
00234 
00235   /**
00236    * This structure accommodates the way in which
00237    * std::iterator_traits<> is normally specialized for const T*, so
00238    * that value_type is still T.
00239    */
00240   template<typename _Tp> 
00241     struct _Unqualified_type 
00242     { typedef _Tp type; };
00243     
00244   template<typename _Tp> 
00245     struct _Unqualified_type<const _Tp> 
00246     { typedef _Tp type; };
00247     
00248   /**
00249    * The following provides an 'alternative pointer' that works with
00250    * the containers when specified as the pointer typedef of the
00251    * allocator.
00252    *
00253    * The pointer type used with the containers doesn't have to be this
00254    * class, but it must support the implicit conversions, pointer
00255    * arithmetic, comparison operators, etc. that are supported by this
00256    * class, and avoid raising compile-time ambiguities.  Because
00257    * creating a working pointer can be challenging, this pointer
00258    * template was designed to wrapper an easier storage policy type,
00259    * so that it becomes reusable for creating other pointer types.
00260    *
00261    * A key point of this class is also that it allows container
00262    * writers to 'assume' Allocator::pointer is a typedef for a normal
00263    * pointer.  This class supports most of the conventions of a true
00264    * pointer, and can, for instance handle implicit conversion to
00265    * const and base class pointer types.  The only impositions on
00266    * container writers to support extended pointers are: 1) use the
00267    * Allocator::pointer typedef appropriately for pointer types.  2)
00268    * if you need pointer casting, use the __pointer_cast<> functions
00269    * from ext/cast.h.  This allows pointer cast operations to be
00270    * overloaded as necessary by custom pointers.
00271    *
00272    * Note: The const qualifier works with this pointer adapter as
00273    * follows:
00274    *
00275    * _Tp*             == _Pointer_adapter<_Std_pointer_impl<_Tp> >;
00276    * const _Tp*       == _Pointer_adapter<_Std_pointer_impl<const _Tp> >;
00277    * _Tp* const       == const _Pointer_adapter<_Std_pointer_impl<_Tp> >;
00278    * const _Tp* const == const _Pointer_adapter<_Std_pointer_impl<const _Tp> >;
00279    */
00280   template<typename _Storage_policy>
00281     class _Pointer_adapter : public _Storage_policy 
00282     {
00283     public:
00284       typedef typename _Storage_policy::element_type element_type;
00285 
00286       // These are needed for iterator_traits
00287       typedef std::random_access_iterator_tag                iterator_category;
00288       typedef typename _Unqualified_type<element_type>::type value_type;
00289       typedef std::ptrdiff_t                                 difference_type;
00290       typedef _Pointer_adapter                               pointer;
00291       typedef typename _Reference_type<element_type>::reference  reference;
00292 
00293       // Reminder: 'const' methods mean that the method is valid when the 
00294       // pointer is immutable, and has nothing to do with whether the 
00295       // 'pointee' is const.
00296 
00297       // Default Constructor (Convert from element_type*)
00298       _Pointer_adapter(element_type* __arg = 0)
00299       { _Storage_policy::set(__arg); }
00300 
00301       // Copy constructor from _Pointer_adapter of same type.
00302       _Pointer_adapter(const _Pointer_adapter& __arg) 
00303       { _Storage_policy::set(__arg.get()); }
00304 
00305       // Convert from _Up* if conversion to element_type* is valid.
00306       template<typename _Up>
00307         _Pointer_adapter(_Up* __arg)
00308         { _Storage_policy::set(__arg); }
00309 
00310       // Conversion from another _Pointer_adapter if _Up if static cast is
00311       // valid.
00312       template<typename _Up>
00313         _Pointer_adapter(const _Pointer_adapter<_Up>& __arg)
00314         { _Storage_policy::set(__arg.get()); }
00315 
00316       // Destructor
00317       ~_Pointer_adapter() { }
00318   
00319       // Assignment operator
00320       _Pointer_adapter&
00321       operator=(const _Pointer_adapter& __arg) 
00322       {
00323         _Storage_policy::set(__arg.get()); 
00324         return *this; 
00325       }
00326 
00327       template<typename _Up>
00328         _Pointer_adapter&
00329         operator=(const _Pointer_adapter<_Up>& __arg)
00330         {
00331           _Storage_policy::set(__arg.get()); 
00332           return *this; 
00333         }
00334 
00335       template<typename _Up>
00336         _Pointer_adapter&
00337         operator=(_Up* __arg)
00338         {
00339           _Storage_policy::set(__arg); 
00340           return *this; 
00341         }
00342 
00343       // Operator*, returns element_type&
00344       inline reference 
00345       operator*() const 
00346       { return *(_Storage_policy::get()); }
00347 
00348       // Operator->, returns element_type*
00349       inline element_type* 
00350       operator->() const 
00351       { return _Storage_policy::get(); }
00352 
00353       // Operator[], returns a element_type& to the item at that loc.
00354       inline reference
00355       operator[](std::ptrdiff_t __index) const
00356       { return _Storage_policy::get()[__index]; }
00357 
00358       // To allow implicit conversion to "bool", for "if (ptr)..."
00359     private:
00360       typedef element_type*(_Pointer_adapter::*__unspecified_bool_type)() const;
00361 
00362     public:
00363       operator __unspecified_bool_type() const
00364       {
00365         return _Storage_policy::get() == 0 ? 0 : 
00366                          &_Pointer_adapter::operator->; 
00367       }
00368 
00369       // ! operator (for: if (!ptr)...)
00370       inline bool
00371       operator!() const 
00372       { return (_Storage_policy::get() == 0); }
00373   
00374       // Pointer differences
00375       inline friend std::ptrdiff_t 
00376       operator-(const _Pointer_adapter& __lhs, element_type* __rhs) 
00377       { return (__lhs.get() - __rhs); }
00378   
00379       inline friend std::ptrdiff_t 
00380       operator-(element_type* __lhs, const _Pointer_adapter& __rhs) 
00381       { return (__lhs - __rhs.get()); }
00382   
00383       template<typename _Up>
00384         inline friend std::ptrdiff_t 
00385         operator-(const _Pointer_adapter& __lhs, _Up* __rhs) 
00386         { return (__lhs.get() - __rhs); }
00387     
00388       template<typename _Up>
00389         inline friend std::ptrdiff_t 
00390         operator-(_Up* __lhs, const _Pointer_adapter& __rhs)
00391         { return (__lhs - __rhs.get()); }
00392 
00393       template<typename _Up>
00394         inline std::ptrdiff_t 
00395         operator-(const _Pointer_adapter<_Up>& __rhs) const 
00396         { return (_Storage_policy::get() - __rhs.get()); }
00397   
00398       // Pointer math
00399       // Note: There is a reason for all this overloading based on different
00400       // integer types.  In some libstdc++-v3 test cases, a templated
00401       // operator+ is declared which can match any types.  This operator
00402       // tends to "steal" the recognition of _Pointer_adapter's own operator+ 
00403       // unless the integer type matches perfectly.
00404 
00405 #define _CXX_POINTER_ARITH_OPERATOR_SET(INT_TYPE) \
00406       inline friend _Pointer_adapter \
00407       operator+(const _Pointer_adapter& __lhs, INT_TYPE __offset) \
00408       { return _Pointer_adapter(__lhs.get() + __offset); } \
00409 \
00410       inline friend _Pointer_adapter \
00411       operator+(INT_TYPE __offset, const _Pointer_adapter& __rhs) \
00412       { return _Pointer_adapter(__rhs.get() + __offset); } \
00413 \
00414       inline friend _Pointer_adapter \
00415       operator-(const _Pointer_adapter& __lhs, INT_TYPE __offset) \
00416       { return _Pointer_adapter(__lhs.get() - __offset); } \
00417 \
00418       inline _Pointer_adapter& \
00419       operator+=(INT_TYPE __offset) \
00420       { \
00421         _Storage_policy::set(_Storage_policy::get() + __offset); \
00422         return *this; \
00423       } \
00424 \
00425       inline _Pointer_adapter& \
00426       operator-=(INT_TYPE __offset) \
00427       { \
00428         _Storage_policy::set(_Storage_policy::get() - __offset); \
00429         return *this; \
00430       } \
00431 // END of _CXX_POINTER_ARITH_OPERATOR_SET macro
00432   
00433       // Expand into the various pointer arithmetic operators needed.
00434       _CXX_POINTER_ARITH_OPERATOR_SET(short);
00435       _CXX_POINTER_ARITH_OPERATOR_SET(unsigned short);
00436       _CXX_POINTER_ARITH_OPERATOR_SET(int);
00437       _CXX_POINTER_ARITH_OPERATOR_SET(unsigned int);
00438       _CXX_POINTER_ARITH_OPERATOR_SET(long);
00439       _CXX_POINTER_ARITH_OPERATOR_SET(unsigned long);
00440 
00441       // Mathematical Manipulators
00442       inline _Pointer_adapter& 
00443       operator++()
00444       {
00445         _Storage_policy::set(_Storage_policy::get() + 1); 
00446         return *this;
00447       }
00448   
00449       inline _Pointer_adapter 
00450       operator++(int)
00451       {
00452         _Pointer_adapter tmp(*this);
00453         _Storage_policy::set(_Storage_policy::get() + 1);
00454         return tmp;
00455       }
00456   
00457       inline _Pointer_adapter& 
00458       operator--() 
00459       {
00460         _Storage_policy::set(_Storage_policy::get() - 1); 
00461         return *this;
00462       }
00463   
00464       inline _Pointer_adapter
00465       operator--(int) 
00466       {
00467         _Pointer_adapter tmp(*this);
00468         _Storage_policy::set(_Storage_policy::get() - 1);
00469         return tmp;
00470       }
00471   
00472     }; // class _Pointer_adapter
00473 
00474 
00475 #define _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(OPERATOR) \
00476   template<typename _Tp1, typename _Tp2> \
00477     inline bool \
00478     operator OPERATOR(const _Pointer_adapter<_Tp1>& __lhs, _Tp2 __rhs) \
00479     { return __lhs.get() OPERATOR __rhs; } \
00480 \
00481   template<typename _Tp1, typename _Tp2> \
00482     inline bool \
00483     operator OPERATOR(_Tp1 __lhs, const _Pointer_adapter<_Tp2>& __rhs) \
00484     { return __lhs OPERATOR __rhs.get(); } \
00485 \
00486   template<typename _Tp1, typename _Tp2> \
00487     inline bool \
00488     operator OPERATOR(const _Pointer_adapter<_Tp1>& __lhs, \
00489                               const _Pointer_adapter<_Tp2>& __rhs) \
00490     { return __lhs.get() OPERATOR __rhs.get(); } \
00491 \
00492 // End GCC_CXX_POINTER_COMPARISON_OPERATION_SET Macro
00493   
00494   // Expand into the various comparison operators needed.
00495   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(==)
00496   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(!=)
00497   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(<)
00498   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(<=)
00499   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(>)
00500   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(>=)
00501 
00502   // These are here for expressions like "ptr == 0", "ptr != 0"
00503   template<typename _Tp>
00504     inline bool
00505     operator==(const _Pointer_adapter<_Tp>& __lhs, int __rhs)
00506     { return __lhs.get() == reinterpret_cast<void*>(__rhs); } 
00507 
00508   template<typename _Tp>
00509     inline bool
00510     operator==(int __lhs, const _Pointer_adapter<_Tp>& __rhs)
00511     { return __rhs.get() == reinterpret_cast<void*>(__lhs); } 
00512 
00513   template<typename _Tp>
00514     inline bool
00515     operator!=(const _Pointer_adapter<_Tp>& __lhs, int __rhs)
00516     { return __lhs.get() != reinterpret_cast<void*>(__rhs); } 
00517 
00518   template<typename _Tp>
00519     inline bool
00520     operator!=(int __lhs, const _Pointer_adapter<_Tp>& __rhs)
00521     { return __rhs.get() != reinterpret_cast<void*>(__lhs); } 
00522 
00523   /**
00524    * Comparison operators for _Pointer_adapter defer to the base class'
00525    * comparison operators, when possible.
00526    */
00527   template<typename _Tp>
00528     inline bool
00529     operator==(const _Pointer_adapter<_Tp>& __lhs, 
00530                const _Pointer_adapter<_Tp>& __rhs)
00531     { return __lhs._Tp::operator==(__rhs); }
00532 
00533   template<typename _Tp>
00534     inline bool
00535     operator<=(const _Pointer_adapter<_Tp>& __lhs, 
00536                const _Pointer_adapter<_Tp>& __rhs)
00537     { return __lhs._Tp::operator<(__rhs) || __lhs._Tp::operator==(__rhs); }
00538 
00539   template<typename _Tp>
00540     inline bool
00541     operator!=(const _Pointer_adapter<_Tp>& __lhs, 
00542                const _Pointer_adapter<_Tp>& __rhs)
00543     { return !(__lhs._Tp::operator==(__rhs)); }
00544 
00545   template<typename _Tp>
00546     inline bool
00547     operator>(const _Pointer_adapter<_Tp>& __lhs, 
00548               const _Pointer_adapter<_Tp>& __rhs)
00549     { return !(__lhs._Tp::operator<(__rhs) || __lhs._Tp::operator==(__rhs)); }
00550 
00551   template<typename _Tp>
00552     inline bool
00553     operator>=(const _Pointer_adapter<_Tp>& __lhs, 
00554                const _Pointer_adapter<_Tp>& __rhs)
00555     { return !(__lhs._Tp::operator<(__rhs)); }
00556 
00557   template<typename _CharT, typename _Traits, typename _StoreT>
00558     inline std::basic_ostream<_CharT, _Traits>&
00559     operator<<(std::basic_ostream<_CharT, _Traits>& __os, 
00560                const _Pointer_adapter<_StoreT>& __p)
00561     { return (__os << __p.get()); }
00562 
00563 _GLIBCXX_END_NAMESPACE_VERSION
00564 } // namespace
00565 
00566 #if __cplusplus >= 201103L
00567 namespace std _GLIBCXX_VISIBILITY(default)
00568 {
00569 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00570 
00571   template<typename _Storage_policy>
00572     struct pointer_traits<__gnu_cxx::_Pointer_adapter<_Storage_policy>>
00573     {
00574       /// The pointer type
00575       typedef __gnu_cxx::_Pointer_adapter<_Storage_policy>         pointer;
00576       /// The type pointed to
00577       typedef typename pointer::element_type            element_type;
00578       /// Type used to represent the difference between two pointers
00579       typedef typename pointer::difference_type         difference_type;
00580 
00581       template<typename _Up>
00582         using rebind = typename __gnu_cxx::_Pointer_adapter<
00583         typename pointer_traits<_Storage_policy>::template rebind<_Up>>;
00584 
00585       static pointer pointer_to(typename pointer::reference __r) noexcept
00586       { return pointer(std::addressof(__r)); }
00587     };
00588 
00589 _GLIBCXX_END_NAMESPACE_VERSION
00590 } // namespace
00591 #endif
00592 
00593 #endif // _POINTER_H