libstdc++-v3/include/ext/pointer.h

   1 // Custom pointer adapter and sample storage policies
   2
   3 // Copyright (C) 2008, 2009, 2010 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /**
  26  *  @file ext/pointer.h
  27  *  This file is a GNU extension to the Standard C++ Library.
  28  *
  29  *  @author Bob Walters
  30  *
  31  * Provides reusable _Pointer_adapter for assisting in the development of
  32  * custom pointer types that can be used with the standard containers via
  33  * the allocator::pointer and allocator::const_pointer typedefs.
  34  */
  35
  36 #ifndef _POINTER_H
  37 #define _POINTER_H 1
  38
  39 #pragma GCC system_header
  40
  41 #include <iosfwd>
  42 #include <bits/stl_iterator_base_types.h>
  43 #include <ext/cast.h>
  44 #include <ext/type_traits.h>
  45 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  46 # include <bits/ptr_traits.h>
  47 #endif
  48
  49 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
  50 {
  51 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  52
  53   /**
  54    * @brief A storage policy for use with _Pointer_adapter<> which yields a
  55    *        standard pointer.
  56    *
  57    *  A _Storage_policy is required to provide 4 things:
  58    *    1) A get() API for returning the stored pointer value.
  59    *    2) An set() API for storing a pointer value.
  60    *    3) An element_type typedef to define the type this points to.
  61    *    4) An operator<() to support pointer comparison.
  62    *    5) An operator==() to support pointer comparison.
  63    */
  64   template<typename _Tp>
  65     class _Std_pointer_impl
  66     {
  67     public:
  68       // the type this pointer points to.
  69       typedef _Tp element_type;
  70
  71       // A method to fetch the pointer value as a standard T* value;
  72       inline _Tp*
  73       get() const
  74       { return _M_value; }
  75
  76       // A method to set the pointer value, from a standard T* value;
  77       inline void
  78       set(element_type* __arg)
  79       { _M_value = __arg; }
  80
  81       // Comparison of pointers
  82       inline bool
  83       operator<(const _Std_pointer_impl& __rarg) const
  84       { return (_M_value < __rarg._M_value); }
  85
  86       inline bool
  87       operator==(const _Std_pointer_impl& __rarg) const
  88       { return (_M_value == __rarg._M_value); }
  89
  90     private:
  91       element_type* _M_value;
  92     };
  93
  94   /**
  95    * @brief A storage policy for use with _Pointer_adapter<> which stores
  96    *        the pointer's address as an offset value which is relative to
  97    *        its own address.
  98    *
  99    * This is intended for pointers within shared memory regions which
 100    * might be mapped at different addresses by different processes.
 101    * For null pointers, a value of 1 is used.  (0 is legitimate
 102    * sometimes for nodes in circularly linked lists) This value was
 103    * chosen as the least likely to generate an incorrect null, As
 104    * there is no reason why any normal pointer would point 1 byte into
 105    * its own pointer address.
 106    */
 107   template<typename _Tp>
 108     class _Relative_pointer_impl
 109     {
 110     public:
 111       typedef _Tp element_type;
 112
 113       _Tp*
 114       get() const
 115       {
 116         if (_M_diff == 1)
 117           return 0;
 118         else
 119           return reinterpret_cast<_Tp*>(reinterpret_cast<_UIntPtrType>(this)
 120                                         + _M_diff);
 121       }
 122
 123       void
 124       set(_Tp* __arg)
 125       {
 126         if (!__arg)
 127           _M_diff = 1;
 128         else
 129           _M_diff = reinterpret_cast<_UIntPtrType>(__arg)
 130                     - reinterpret_cast<_UIntPtrType>(this);
 131       }
 132
 133       // Comparison of pointers
 134       inline bool
 135       operator<(const _Relative_pointer_impl& __rarg) const
 136       { return (reinterpret_cast<_UIntPtrType>(this->get())
 137                 < reinterpret_cast<_UIntPtrType>(__rarg.get())); }
 138
 139       inline bool
 140       operator==(const _Relative_pointer_impl& __rarg) const
 141       { return (reinterpret_cast<_UIntPtrType>(this->get())
 142                 == reinterpret_cast<_UIntPtrType>(__rarg.get())); }
 143
 144     private:
 145 #ifdef _GLIBCXX_USE_LONG_LONG
 146       typedef __gnu_cxx::__conditional_type<
 147          (sizeof(unsigned long) >= sizeof(void*)),
 148          unsigned long, unsigned long long>::__type _UIntPtrType;
 149 #else
 150       typedef unsigned long _UIntPtrType;
 151 #endif
 152       _UIntPtrType _M_diff;
 153     };
 154
 155   /**
 156    * Relative_pointer_impl needs a specialization for const T because of
 157    * the casting done during pointer arithmetic.
 158    */
 159   template<typename _Tp>
 160     class _Relative_pointer_impl<const _Tp>
 161     {
 162     public:
 163       typedef const _Tp element_type;
 164
 165       const _Tp*
 166       get() const
 167       {
 168         if (_M_diff == 1)
 169           return 0;
 170         else
 171           return reinterpret_cast<const _Tp*>
 172               (reinterpret_cast<_UIntPtrType>(this) + _M_diff);
 173       }
 174
 175       void
 176       set(const _Tp* __arg)
 177       {
 178         if (!__arg)
 179           _M_diff = 1;
 180         else
 181           _M_diff = reinterpret_cast<_UIntPtrType>(__arg)
 182                     - reinterpret_cast<_UIntPtrType>(this);
 183       }
 184
 185       // Comparison of pointers
 186       inline bool
 187       operator<(const _Relative_pointer_impl& __rarg) const
 188       { return (reinterpret_cast<_UIntPtrType>(this->get())
 189                 < reinterpret_cast<_UIntPtrType>(__rarg.get())); }
 190
 191       inline bool
 192       operator==(const _Relative_pointer_impl& __rarg) const
 193       { return (reinterpret_cast<_UIntPtrType>(this->get())
 194                 == reinterpret_cast<_UIntPtrType>(__rarg.get())); }
 195
 196     private:
 197 #ifdef _GLIBCXX_USE_LONG_LONG
 198       typedef __gnu_cxx::__conditional_type<
 199          (sizeof(unsigned long) >= sizeof(void*)),
 200          unsigned long, unsigned long long>::__type _UIntPtrType;
 201 #else
 202       typedef unsigned long _UIntPtrType;
 203 #endif
 204        _UIntPtrType _M_diff;
 205     };
 206
 207   /**
 208    * The specialization on this type helps resolve the problem of
 209    * reference to void, and eliminates the need to specialize
 210    * _Pointer_adapter for cases of void*, const void*, and so on.
 211    */
 212   struct _Invalid_type { };
 213
 214   template<typename _Tp>
 215     struct _Reference_type
 216     { typedef _Tp& reference; };
 217
 218   template<>
 219     struct _Reference_type<void>
 220     { typedef _Invalid_type& reference; };
 221
 222   template<>
 223     struct _Reference_type<const void>
 224     { typedef const _Invalid_type& reference; };
 225
 226   template<>
 227     struct _Reference_type<volatile void>
 228     { typedef volatile _Invalid_type&  reference; };
 229
 230   template<>
 231     struct _Reference_type<volatile const void>
 232     { typedef const volatile _Invalid_type&  reference; };
 233
 234   /**
 235    * This structure accomodates the way in which
 236    * std::iterator_traits<> is normally specialized for const T*, so
 237    * that value_type is still T.
 238    */
 239   template<typename _Tp>
 240     struct _Unqualified_type
 241     { typedef _Tp type; };
 242
 243   template<typename _Tp>
 244     struct _Unqualified_type<const _Tp>
 245     { typedef _Tp type; };
 246
 247   template<typename _Tp>
 248     struct _Unqualified_type<volatile _Tp>
 249     { typedef volatile _Tp type; };
 250
 251   template<typename _Tp>
 252     struct _Unqualified_type<volatile const _Tp>
 253     { typedef volatile _Tp type; };
 254
 255   /**
 256    * The following provides an 'alternative pointer' that works with
 257    * the containers when specified as the pointer typedef of the
 258    * allocator.
 259    *
 260    * The pointer type used with the containers doesn't have to be this
 261    * class, but it must support the implicit conversions, pointer
 262    * arithmetic, comparison operators, etc. that are supported by this
 263    * class, and avoid raising compile-time ambiguities.  Because
 264    * creating a working pointer can be challenging, this pointer
 265    * template was designed to wrapper an easier storage policy type,
 266    * so that it becomes reusable for creating other pointer types.
 267    *
 268    * A key point of this class is also that it allows container
 269    * writers to 'assume' Alocator::pointer is a typedef for a normal
 270    * pointer.  This class supports most of the conventions of a true
 271    * pointer, and can, for instance handle implicit conversion to
 272    * const and base class pointer types.  The only impositions on
 273    * container writers to support extended pointers are: 1) use the
 274    * Allocator::pointer typedef appropriately for pointer types.  2)
 275    * if you need pointer casting, use the __pointer_cast<> functions
 276    * from ext/cast.h.  This allows pointer cast operations to be
 277    * overloaded is necessary by custom pointers.
 278    *
 279    * Note: The const qualifier works with this pointer adapter as
 280    * follows:
 281    *
 282    * _Tp*             == _Pointer_adapter<_Std_pointer_impl<_Tp> >;
 283    * const _Tp*       == _Pointer_adapter<_Std_pointer_impl<const _Tp> >;
 284    * _Tp* const       == const _Pointer_adapter<_Std_pointer_impl<_Tp> >;
 285    * const _Tp* const == const _Pointer_adapter<_Std_pointer_impl<const _Tp> >;
 286    */
 287   template<typename _Storage_policy>
 288     class _Pointer_adapter : public _Storage_policy
 289     {
 290     public:
 291       typedef typename _Storage_policy::element_type element_type;
 292
 293       // These are needed for iterator_traits
 294       typedef std::random_access_iterator_tag                iterator_category;
 295       typedef typename _Unqualified_type<element_type>::type value_type;
 296       typedef std::ptrdiff_t                                 difference_type;
 297       typedef _Pointer_adapter                               pointer;
 298       typedef typename _Reference_type<element_type>::reference  reference;
 299
 300       // Reminder: 'const' methods mean that the method is valid when the
 301       // pointer is immutable, and has nothing to do with whether the
 302       // 'pointee' is const.
 303
 304       // Default Constructor (Convert from element_type*)
 305       _Pointer_adapter(element_type* __arg = 0)
 306       { _Storage_policy::set(__arg); }
 307
 308       // Copy constructor from _Pointer_adapter of same type.
 309       _Pointer_adapter(const _Pointer_adapter& __arg)
 310       { _Storage_policy::set(__arg.get()); }
 311
 312       // Convert from _Up* if conversion to element_type* is valid.
 313       template<typename _Up>
 314         _Pointer_adapter(_Up* __arg)
 315         { _Storage_policy::set(__arg); }
 316
 317       // Conversion from another _Pointer_adapter if _Up if static cast is
 318       // valid.
 319       template<typename _Up>
 320         _Pointer_adapter(const _Pointer_adapter<_Up>& __arg)
 321         { _Storage_policy::set(__arg.get()); }
 322
 323       // Destructor
 324       ~_Pointer_adapter() { }
 325
 326       // Assignment operator
 327       _Pointer_adapter&
 328       operator=(const _Pointer_adapter& __arg)
 329       {
 330         _Storage_policy::set(__arg.get());
 331         return *this;
 332       }
 333
 334       template<typename _Up>
 335         _Pointer_adapter&
 336         operator=(const _Pointer_adapter<_Up>& __arg)
 337         {
 338           _Storage_policy::set(__arg.get());
 339           return *this;
 340         }
 341
 342       template<typename _Up>
 343         _Pointer_adapter&
 344         operator=(_Up* __arg)
 345         {
 346           _Storage_policy::set(__arg);
 347           return *this;
 348         }
 349
 350       // Operator*, returns element_type&
 351       inline reference
 352       operator*() const
 353       { return *(_Storage_policy::get()); }
 354
 355       // Operator->, returns element_type*
 356       inline element_type*
 357       operator->() const
 358       { return _Storage_policy::get(); }
 359
 360       // Operator[], returns a element_type& to the item at that loc.
 361       inline reference
 362       operator[](std::ptrdiff_t __index) const
 363       { return _Storage_policy::get()[__index]; }
 364
 365       // To allow implicit conversion to "bool", for "if (ptr)..."
 366     private:
 367       typedef element_type*(_Pointer_adapter::*__unspecified_bool_type)() const;
 368
 369     public:
 370       operator __unspecified_bool_type() const
 371       {
 372         return _Storage_policy::get() == 0 ? 0 :
 373                          &_Pointer_adapter::operator->;
 374       }
 375
 376       // ! operator (for: if (!ptr)...)
 377       inline bool
 378       operator!() const
 379       { return (_Storage_policy::get() == 0); }
 380
 381       // Pointer differences
 382       inline friend std::ptrdiff_t
 383       operator-(const _Pointer_adapter& __lhs, element_type* __rhs)
 384       { return (__lhs.get() - __rhs); }
 385
 386       inline friend std::ptrdiff_t
 387       operator-(element_type* __lhs, const _Pointer_adapter& __rhs)
 388       { return (__lhs - __rhs.get()); }
 389
 390       template<typename _Up>
 391         inline friend std::ptrdiff_t
 392         operator-(const _Pointer_adapter& __lhs, _Up* __rhs)
 393         { return (__lhs.get() - __rhs); }
 394
 395       template<typename _Up>
 396         inline friend std::ptrdiff_t
 397         operator-(_Up* __lhs, const _Pointer_adapter& __rhs)
 398         { return (__lhs - __rhs.get()); }
 399
 400       template<typename _Up>
 401         inline std::ptrdiff_t
 402         operator-(const _Pointer_adapter<_Up>& __rhs) const
 403         { return (_Storage_policy::get() - __rhs.get()); }
 404
 405       // Pointer math
 406       // Note: There is a reason for all this overloading based on different
 407       // integer types.  In some libstdc++-v3 test cases, a templated
 408       // operator+ is declared which can match any types.  This operator
 409       // tends to "steal" the recognition of _Pointer_adapter's own operator+
 410       // unless the integer type matches perfectly.
 411
 412 #define _CXX_POINTER_ARITH_OPERATOR_SET(INT_TYPE) \
 413       inline friend _Pointer_adapter \
 414       operator+(const _Pointer_adapter& __lhs, INT_TYPE __offset) \
 415       { return _Pointer_adapter(__lhs.get() + __offset); } \
 416 \
 417       inline friend _Pointer_adapter \
 418       operator+(INT_TYPE __offset, const _Pointer_adapter& __rhs) \
 419       { return _Pointer_adapter(__rhs.get() + __offset); } \
 420 \
 421       inline friend _Pointer_adapter \
 422       operator-(const _Pointer_adapter& __lhs, INT_TYPE __offset) \
 423       { return _Pointer_adapter(__lhs.get() - __offset); } \
 424 \
 425       inline _Pointer_adapter& \
 426       operator+=(INT_TYPE __offset) \
 427       { \
 428         _Storage_policy::set(_Storage_policy::get() + __offset); \
 429         return *this; \
 430       } \
 431 \
 432       inline _Pointer_adapter& \
 433       operator-=(INT_TYPE __offset) \
 434       { \
 435         _Storage_policy::set(_Storage_policy::get() - __offset); \
 436         return *this; \
 437       } \
 438 // END of _CXX_POINTER_ARITH_OPERATOR_SET macro
 439
 440       // Expand into the various pointer arithmatic operators needed.
 441       _CXX_POINTER_ARITH_OPERATOR_SET(short);
 442       _CXX_POINTER_ARITH_OPERATOR_SET(unsigned short);
 443       _CXX_POINTER_ARITH_OPERATOR_SET(int);
 444       _CXX_POINTER_ARITH_OPERATOR_SET(unsigned int);
 445       _CXX_POINTER_ARITH_OPERATOR_SET(long);
 446       _CXX_POINTER_ARITH_OPERATOR_SET(unsigned long);
 447
 448       // Mathematical Manipulators
 449       inline _Pointer_adapter&
 450       operator++()
 451       {
 452         _Storage_policy::set(_Storage_policy::get() + 1);
 453         return *this;
 454       }
 455
 456       inline _Pointer_adapter
 457       operator++(int)
 458       {
 459         _Pointer_adapter tmp(*this);
 460         _Storage_policy::set(_Storage_policy::get() + 1);
 461         return tmp;
 462       }
 463
 464       inline _Pointer_adapter&
 465       operator--()
 466       {
 467         _Storage_policy::set(_Storage_policy::get() - 1);
 468         return *this;
 469       }
 470
 471       inline _Pointer_adapter
 472       operator--(int)
 473       {
 474         _Pointer_adapter tmp(*this);
 475         _Storage_policy::set(_Storage_policy::get() - 1);
 476         return tmp;
 477       }
 478
 479     }; // class _Pointer_adapter
 480
 481
 482 #define _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(OPERATOR) \
 483   template<typename _Tp1, typename _Tp2> \
 484     inline bool \
 485     operator OPERATOR(const _Pointer_adapter<_Tp1>& __lhs, _Tp2 __rhs) \
 486     { return __lhs.get() OPERATOR __rhs; } \
 487 \
 488   template<typename _Tp1, typename _Tp2> \
 489     inline bool \
 490     operator OPERATOR(_Tp1 __lhs, const _Pointer_adapter<_Tp2>& __rhs) \
 491     { return __lhs OPERATOR __rhs.get(); } \
 492 \
 493   template<typename _Tp1, typename _Tp2> \
 494     inline bool \
 495     operator OPERATOR(const _Pointer_adapter<_Tp1>& __lhs, \
 496                               const _Pointer_adapter<_Tp2>& __rhs) \
 497     { return __lhs.get() OPERATOR __rhs.get(); } \
 498 \
 499 // End GCC_CXX_POINTER_COMPARISON_OPERATION_SET Macro
 500
 501   // Expand into the various comparison operators needed.
 502   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(==)
 503   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(!=)
 504   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(<)
 505   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(<=)
 506   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(>)
 507   _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(>=)
 508
 509   // These are here for expressions like "ptr == 0", "ptr != 0"
 510   template<typename _Tp>
 511     inline bool
 512     operator==(const _Pointer_adapter<_Tp>& __lhs, int __rhs)
 513     { return __lhs.get() == reinterpret_cast<void*>(__rhs); }
 514
 515   template<typename _Tp>
 516     inline bool
 517     operator==(int __lhs, const _Pointer_adapter<_Tp>& __rhs)
 518     { return __rhs.get() == reinterpret_cast<void*>(__lhs); }
 519
 520   template<typename _Tp>
 521     inline bool
 522     operator!=(const _Pointer_adapter<_Tp>& __lhs, int __rhs)
 523     { return __lhs.get() != reinterpret_cast<void*>(__rhs); }
 524
 525   template<typename _Tp>
 526     inline bool
 527     operator!=(int __lhs, const _Pointer_adapter<_Tp>& __rhs)
 528     { return __rhs.get() != reinterpret_cast<void*>(__lhs); }
 529
 530   /**
 531    * Comparison operators for _Pointer_adapter defer to the base class'es
 532    * comparison operators, when possible.
 533    */
 534   template<typename _Tp>
 535     inline bool
 536     operator==(const _Pointer_adapter<_Tp>& __lhs,
 537                const _Pointer_adapter<_Tp>& __rhs)
 538     { return __lhs._Tp::operator==(__rhs); }
 539
 540   template<typename _Tp>
 541     inline bool
 542     operator<=(const _Pointer_adapter<_Tp>& __lhs,
 543                const _Pointer_adapter<_Tp>& __rhs)
 544     { return __lhs._Tp::operator<(__rhs) || __lhs._Tp::operator==(__rhs); }
 545
 546   template<typename _Tp>
 547     inline bool
 548     operator!=(const _Pointer_adapter<_Tp>& __lhs,
 549                const _Pointer_adapter<_Tp>& __rhs)
 550     { return !(__lhs._Tp::operator==(__rhs)); }
 551
 552   template<typename _Tp>
 553     inline bool
 554     operator>(const _Pointer_adapter<_Tp>& __lhs,
 555               const _Pointer_adapter<_Tp>& __rhs)
 556     { return !(__lhs._Tp::operator<(__rhs) || __lhs._Tp::operator==(__rhs)); }
 557
 558   template<typename _Tp>
 559     inline bool
 560     operator>=(const _Pointer_adapter<_Tp>& __lhs,
 561                const _Pointer_adapter<_Tp>& __rhs)
 562     { return !(__lhs._Tp::operator<(__rhs)); }
 563
 564   template<typename _CharT, typename _Traits, typename _StoreT>
 565     inline std::basic_ostream<_CharT, _Traits>&
 566     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 567                const _Pointer_adapter<_StoreT>& __p)
 568     { return (__os << __p.get()); }
 569
 570 _GLIBCXX_END_NAMESPACE_VERSION
 571 } // namespace
 572
 573 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 574 namespace std _GLIBCXX_VISIBILITY(default)
 575 {
 576 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 577
 578   template<typename _Storage_policy>
 579     struct pointer_traits<__gnu_cxx::_Pointer_adapter<_Storage_policy>>
 580     {
 581       /// The pointer type
 582       typedef __gnu_cxx::_Pointer_adapter<_Storage_policy>         pointer;
 583       /// The type pointed to
 584       typedef typename pointer::element_type            element_type;
 585       /// Type used to represent the difference between two pointers
 586       typedef typename pointer::difference_type         difference_type;
 587
 588       /* TODO: replace __rebind<U> with alias template rebind<U> */
 589       /*
 590       template<typename _Up>
 591         using rebind<_Up> = typename __gnu_cxx::_Pointer_adapter<
 592           typename pointer_traits<_Storage_policy>::rebind<_Up>>
 593       */
 594       template<typename _Up>
 595         class __rebind
 596         {
 597           typedef pointer_traits<_Storage_policy> _Policy_traits;
 598           typedef typename _Policy_traits::template __rebind<_Up>::__type
 599             _Rebound_policy;
 600         public:
 601           typedef typename __gnu_cxx::_Pointer_adapter<_Rebound_policy> __type;
 602         };
 603     };
 604
 605 _GLIBCXX_END_NAMESPACE_VERSION
 606 } // namespace
 607 #endif
 608
 609 #endif // _POINTER_H