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