1 // Custom pointer adapter and sample storage policies
2
3 // Copyright (C) 2008-2020 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 #if __cplusplus >= 201103L
46 # include <bits/move.h>
47 # include <bits/ptr_traits.h>
48 #endif
49 #if __cplusplus > 201703L
50 # include <iterator> // for indirectly_readable_traits
51 #endif
52
_GLIBCXX_VISIBILITY(default)53 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
54 {
55 _GLIBCXX_BEGIN_NAMESPACE_VERSION
56
57 /**
58 * @brief A storage policy for use with _Pointer_adapter<> which yields a
59 * standard pointer.
60 *
61 * A _Storage_policy is required to provide 4 things:
62 * 1) A get() API for returning the stored pointer value.
63 * 2) An set() API for storing a pointer value.
64 * 3) An element_type typedef to define the type this points to.
65 * 4) An operator<() to support pointer comparison.
66 * 5) An operator==() to support pointer comparison.
67 */
68 template<typename _Tp>
69 class _Std_pointer_impl
70 {
71 public:
72 // the type this pointer points to.
73 typedef _Tp element_type;
74
75 // A method to fetch the pointer value as a standard T* value;
76 inline _Tp*
77 get() const
78 { return _M_value; }
79
80 // A method to set the pointer value, from a standard T* value;
81 inline void
82 set(element_type* __arg)
83 { _M_value = __arg; }
84
85 // Comparison of pointers
86 inline bool
87 operator<(const _Std_pointer_impl& __rarg) const
88 { return (_M_value < __rarg._M_value); }
89
90 inline bool
91 operator==(const _Std_pointer_impl& __rarg) const
92 { return (_M_value == __rarg._M_value); }
93
94 private:
95 element_type* _M_value;
96 };
97
98 /**
99 * @brief A storage policy for use with _Pointer_adapter<> which stores
100 * the pointer's address as an offset value which is relative to
101 * its own address.
102 *
103 * This is intended for pointers within shared memory regions which
104 * might be mapped at different addresses by different processes.
105 * For null pointers, a value of 1 is used. (0 is legitimate
106 * sometimes for nodes in circularly linked lists) This value was
107 * chosen as the least likely to generate an incorrect null, As
108 * there is no reason why any normal pointer would point 1 byte into
109 * its own pointer address.
110 */
111 template<typename _Tp>
112 class _Relative_pointer_impl
113 {
114 public:
115 typedef _Tp element_type;
116
117 _Tp*
118 get() const
119 {
120 if (_M_diff == 1)
121 return 0;
122 else
123 return reinterpret_cast<_Tp*>(reinterpret_cast<_UIntPtrType>(this)
124 + _M_diff);
125 }
126
127 void
128 set(_Tp* __arg)
129 {
130 if (!__arg)
131 _M_diff = 1;
132 else
133 _M_diff = reinterpret_cast<_UIntPtrType>(__arg)
134 - reinterpret_cast<_UIntPtrType>(this);
135 }
136
137 // Comparison of pointers
138 inline bool
139 operator<(const _Relative_pointer_impl& __rarg) const
140 { return (reinterpret_cast<_UIntPtrType>(this->get())
141 < reinterpret_cast<_UIntPtrType>(__rarg.get())); }
142
143 inline bool
144 operator==(const _Relative_pointer_impl& __rarg) const
145 { return (reinterpret_cast<_UIntPtrType>(this->get())
146 == reinterpret_cast<_UIntPtrType>(__rarg.get())); }
147
148 private:
149 #ifdef _GLIBCXX_USE_LONG_LONG
150 typedef __gnu_cxx::__conditional_type<
151 (sizeof(unsigned long) >= sizeof(void*)),
152 unsigned long, unsigned long long>::__type _UIntPtrType;
153 #else
154 typedef unsigned long _UIntPtrType;
155 #endif
156 _UIntPtrType _M_diff;
157 };
158
159 /**
160 * Relative_pointer_impl needs a specialization for const T because of
161 * the casting done during pointer arithmetic.
162 */
163 template<typename _Tp>
164 class _Relative_pointer_impl<const _Tp>
165 {
166 public:
167 typedef const _Tp element_type;
168
169 const _Tp*
170 get() const
171 {
172 if (_M_diff == 1)
173 return 0;
174 else
175 return reinterpret_cast<const _Tp*>
176 (reinterpret_cast<_UIntPtrType>(this) + _M_diff);
177 }
178
179 void
180 set(const _Tp* __arg)
181 {
182 if (!__arg)
183 _M_diff = 1;
184 else
185 _M_diff = reinterpret_cast<_UIntPtrType>(__arg)
186 - reinterpret_cast<_UIntPtrType>(this);
187 }
188
189 // Comparison of pointers
190 inline bool
191 operator<(const _Relative_pointer_impl& __rarg) const
192 { return (reinterpret_cast<_UIntPtrType>(this->get())
193 < reinterpret_cast<_UIntPtrType>(__rarg.get())); }
194
195 inline bool
196 operator==(const _Relative_pointer_impl& __rarg) const
197 { return (reinterpret_cast<_UIntPtrType>(this->get())
198 == reinterpret_cast<_UIntPtrType>(__rarg.get())); }
199
200 private:
201 #ifdef _GLIBCXX_USE_LONG_LONG
202 typedef __gnu_cxx::__conditional_type<
203 (sizeof(unsigned long) >= sizeof(void*)),
204 unsigned long, unsigned long long>::__type _UIntPtrType;
205 #else
206 typedef unsigned long _UIntPtrType;
207 #endif
208 _UIntPtrType _M_diff;
209 };
210
211 /**
212 * The specialization on this type helps resolve the problem of
213 * reference to void, and eliminates the need to specialize
214 * _Pointer_adapter for cases of void*, const void*, and so on.
215 */
216 struct _Invalid_type { };
217
218 template<typename _Tp>
219 struct _Reference_type
220 { typedef _Tp& reference; };
221
222 template<>
223 struct _Reference_type<void>
224 { typedef _Invalid_type& reference; };
225
226 template<>
227 struct _Reference_type<const void>
228 { typedef const _Invalid_type& reference; };
229
230 template<>
231 struct _Reference_type<volatile void>
232 { typedef volatile _Invalid_type& reference; };
233
234 template<>
235 struct _Reference_type<volatile const void>
236 { typedef const volatile _Invalid_type& reference; };
237
238 /**
239 * This structure accommodates the way in which
240 * std::iterator_traits<> is normally specialized for const T*, so
241 * that value_type is still T.
242 */
243 template<typename _Tp>
244 struct _Unqualified_type
245 { typedef _Tp type; };
246
247 template<typename _Tp>
248 struct _Unqualified_type<const _Tp>
249 { typedef _Tp type; };
250
251 /**
252 * The following provides an 'alternative pointer' that works with
253 * the containers when specified as the pointer typedef of the
254 * allocator.
255 *
256 * The pointer type used with the containers doesn't have to be this
257 * class, but it must support the implicit conversions, pointer
258 * arithmetic, comparison operators, etc. that are supported by this
259 * class, and avoid raising compile-time ambiguities. Because
260 * creating a working pointer can be challenging, this pointer
261 * template was designed to wrapper an easier storage policy type,
262 * so that it becomes reusable for creating other pointer types.
263 *
264 * A key point of this class is also that it allows container
265 * writers to 'assume' Allocator::pointer is a typedef for a normal
266 * pointer. This class supports most of the conventions of a true
267 * pointer, and can, for instance handle implicit conversion to
268 * const and base class pointer types. The only impositions on
269 * container writers to support extended pointers are: 1) use the
270 * Allocator::pointer typedef appropriately for pointer types. 2)
271 * if you need pointer casting, use the __pointer_cast<> functions
272 * from ext/cast.h. This allows pointer cast operations to be
273 * overloaded as necessary by custom pointers.
274 *
275 * Note: The const qualifier works with this pointer adapter as
276 * follows:
277 *
278 * _Tp* == _Pointer_adapter<_Std_pointer_impl<_Tp> >;
279 * const _Tp* == _Pointer_adapter<_Std_pointer_impl<const _Tp> >;
280 * _Tp* const == const _Pointer_adapter<_Std_pointer_impl<_Tp> >;
281 * const _Tp* const == const _Pointer_adapter<_Std_pointer_impl<const _Tp> >;
282 */
283 template<typename _Storage_policy>
284 class _Pointer_adapter : public _Storage_policy
285 {
286 public:
287 typedef typename _Storage_policy::element_type element_type;
288
289 // These are needed for iterator_traits
290 typedef std::random_access_iterator_tag iterator_category;
291 typedef typename _Unqualified_type<element_type>::type value_type;
292 typedef std::ptrdiff_t difference_type;
293 typedef _Pointer_adapter pointer;
294 typedef typename _Reference_type<element_type>::reference reference;
295
296 // Reminder: 'const' methods mean that the method is valid when the
297 // pointer is immutable, and has nothing to do with whether the
298 // 'pointee' is const.
299
300 // Default Constructor (Convert from element_type*)
301 _Pointer_adapter(element_type* __arg = 0)
302 { _Storage_policy::set(__arg); }
303
304 // Copy constructor from _Pointer_adapter of same type.
305 _Pointer_adapter(const _Pointer_adapter& __arg)
306 { _Storage_policy::set(__arg.get()); }
307
308 // Convert from _Up* if conversion to element_type* is valid.
309 template<typename _Up>
310 _Pointer_adapter(_Up* __arg)
311 { _Storage_policy::set(__arg); }
312
313 // Conversion from another _Pointer_adapter if _Up if static cast is
314 // valid.
315 template<typename _Up>
316 _Pointer_adapter(const _Pointer_adapter<_Up>& __arg)
317 { _Storage_policy::set(__arg.get()); }
318
319 // Destructor
320 ~_Pointer_adapter() { }
321
322 // Assignment operator
323 _Pointer_adapter&
324 operator=(const _Pointer_adapter& __arg)
325 {
326 _Storage_policy::set(__arg.get());
327 return *this;
328 }
329
330 template<typename _Up>
331 _Pointer_adapter&
332 operator=(const _Pointer_adapter<_Up>& __arg)
333 {
334 _Storage_policy::set(__arg.get());
335 return *this;
336 }
337
338 template<typename _Up>
339 _Pointer_adapter&
340 operator=(_Up* __arg)
341 {
342 _Storage_policy::set(__arg);
343 return *this;
344 }
345
346 // Operator*, returns element_type&
347 inline reference
348 operator*() const
349 { return *(_Storage_policy::get()); }
350
351 // Operator->, returns element_type*
352 inline element_type*
353 operator->() const
354 { return _Storage_policy::get(); }
355
356 // Operator[], returns a element_type& to the item at that loc.
357 inline reference
358 operator[](std::ptrdiff_t __index) const
359 { return _Storage_policy::get()[__index]; }
360
361 // To allow implicit conversion to "bool", for "if (ptr)..."
362 #if __cplusplus >= 201103L
363 explicit operator bool() const { return _Storage_policy::get() != 0; }
364 #else
365 private:
366 typedef element_type*(_Pointer_adapter::*__unspecified_bool_type)() const;
367
368 public:
369 operator __unspecified_bool_type() const
370 {
371 return _Storage_policy::get() == 0 ? 0 :
372 &_Pointer_adapter::operator->;
373 }
374
375 // ! operator (for: if (!ptr)...)
376 inline bool
377 operator!() const
378 { return (_Storage_policy::get() == 0); }
379 #endif
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 arithmetic 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 #ifdef _GLIBCXX_USE_LONG_LONG
448 _CXX_POINTER_ARITH_OPERATOR_SET(long long);
449 _CXX_POINTER_ARITH_OPERATOR_SET(unsigned long long);
450 #endif
451
452 // Mathematical Manipulators
453 inline _Pointer_adapter&
454 operator++()
455 {
456 _Storage_policy::set(_Storage_policy::get() + 1);
457 return *this;
458 }
459
460 inline _Pointer_adapter
461 operator++(int)
462 {
463 _Pointer_adapter __tmp(*this);
464 _Storage_policy::set(_Storage_policy::get() + 1);
465 return __tmp;
466 }
467
468 inline _Pointer_adapter&
469 operator--()
470 {
471 _Storage_policy::set(_Storage_policy::get() - 1);
472 return *this;
473 }
474
475 inline _Pointer_adapter
476 operator--(int)
477 {
478 _Pointer_adapter __tmp(*this);
479 _Storage_policy::set(_Storage_policy::get() - 1);
480 return __tmp;
481 }
482
483 #if __cpp_lib_three_way_comparison
484 friend std::strong_ordering
485 operator<=>(const _Pointer_adapter& __lhs, const _Pointer_adapter& __rhs)
486 noexcept
487 { return __lhs.get() <=> __rhs.get(); }
488 #endif
489 }; // class _Pointer_adapter
490
491
492 #define _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(OPERATOR) \
493 template<typename _Tp1, typename _Tp2> \
494 inline bool \
495 operator OPERATOR(const _Pointer_adapter<_Tp1>& __lhs, _Tp2 __rhs) \
496 { return __lhs.get() OPERATOR __rhs; } \
497 \
498 template<typename _Tp1, typename _Tp2> \
499 inline bool \
500 operator OPERATOR(_Tp1 __lhs, const _Pointer_adapter<_Tp2>& __rhs) \
501 { return __lhs OPERATOR __rhs.get(); } \
502 \
503 template<typename _Tp1, typename _Tp2> \
504 inline bool \
505 operator OPERATOR(const _Pointer_adapter<_Tp1>& __lhs, \
506 const _Pointer_adapter<_Tp2>& __rhs) \
507 { return __lhs.get() OPERATOR __rhs.get(); } \
508 \
509 // End GCC_CXX_POINTER_COMPARISON_OPERATION_SET Macro
510
511 // Expand into the various comparison operators needed.
512 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(==)
513 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(!=)
514 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(<)
515 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(<=)
516 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(>)
517 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(>=)
518
519 // These are here for expressions like "ptr == 0", "ptr != 0"
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 template<typename _Tp>
531 inline bool
532 operator!=(const _Pointer_adapter<_Tp>& __lhs, int __rhs)
533 { return __lhs.get() != reinterpret_cast<void*>(__rhs); }
534
535 template<typename _Tp>
536 inline bool
537 operator!=(int __lhs, const _Pointer_adapter<_Tp>& __rhs)
538 { return __rhs.get() != reinterpret_cast<void*>(__lhs); }
539
540 /**
541 * Comparison operators for _Pointer_adapter defer to the base class'
542 * comparison operators, when possible.
543 */
544 template<typename _Tp>
545 inline bool
546 operator==(const _Pointer_adapter<_Tp>& __lhs,
547 const _Pointer_adapter<_Tp>& __rhs)
548 { return __lhs._Tp::operator==(__rhs); }
549
550 template<typename _Tp>
551 inline bool
552 operator<=(const _Pointer_adapter<_Tp>& __lhs,
553 const _Pointer_adapter<_Tp>& __rhs)
554 { return __lhs._Tp::operator<(__rhs) || __lhs._Tp::operator==(__rhs); }
555
556 template<typename _Tp>
557 inline bool
558 operator!=(const _Pointer_adapter<_Tp>& __lhs,
559 const _Pointer_adapter<_Tp>& __rhs)
560 { return !(__lhs._Tp::operator==(__rhs)); }
561
562 template<typename _Tp>
563 inline bool
564 operator>(const _Pointer_adapter<_Tp>& __lhs,
565 const _Pointer_adapter<_Tp>& __rhs)
566 { return !(__lhs._Tp::operator<(__rhs) || __lhs._Tp::operator==(__rhs)); }
567
568 template<typename _Tp>
569 inline bool
570 operator>=(const _Pointer_adapter<_Tp>& __lhs,
571 const _Pointer_adapter<_Tp>& __rhs)
572 { return !(__lhs._Tp::operator<(__rhs)); }
573
574 template<typename _CharT, typename _Traits, typename _StoreT>
575 inline std::basic_ostream<_CharT, _Traits>&
576 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
577 const _Pointer_adapter<_StoreT>& __p)
578 { return (__os << __p.get()); }
579
580 _GLIBCXX_END_NAMESPACE_VERSION
581 } // namespace
582
583 #if __cplusplus >= 201103L
584 namespace std _GLIBCXX_VISIBILITY(default)
585 {
586 _GLIBCXX_BEGIN_NAMESPACE_VERSION
587
588 template<typename _Storage_policy>
589 struct pointer_traits<__gnu_cxx::_Pointer_adapter<_Storage_policy>>
590 {
591 /// The pointer type
592 typedef __gnu_cxx::_Pointer_adapter<_Storage_policy> pointer;
593 /// The type pointed to
594 typedef typename pointer::element_type element_type;
595 /// Type used to represent the difference between two pointers
596 typedef typename pointer::difference_type difference_type;
597
598 template<typename _Up>
599 using rebind = typename __gnu_cxx::_Pointer_adapter<
600 typename pointer_traits<_Storage_policy>::template rebind<_Up>>;
601
602 static pointer pointer_to(typename pointer::reference __r) noexcept
603 { return pointer(std::addressof(__r)); }
604 };
605
606 #if __cpp_lib_concepts
607 template<typename _Policy>
608 struct indirectly_readable_traits<__gnu_cxx::_Pointer_adapter<_Policy>>
609 {
610 using value_type
611 = typename __gnu_cxx::_Pointer_adapter<_Policy>::value_type;
612 };
613 #endif
614 _GLIBCXX_END_NAMESPACE_VERSION
615 } // namespace
616 #endif
617
618 #endif // _POINTER_H
619