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