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