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