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