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 accommodates 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 /** 248 * The following provides an 'alternative pointer' that works with 249 * the containers when specified as the pointer typedef of the 250 * allocator. 251 * 252 * The pointer type used with the containers doesn't have to be this 253 * class, but it must support the implicit conversions, pointer 254 * arithmetic, comparison operators, etc. that are supported by this 255 * class, and avoid raising compile-time ambiguities. Because 256 * creating a working pointer can be challenging, this pointer 257 * template was designed to wrapper an easier storage policy type, 258 * so that it becomes reusable for creating other pointer types. 259 * 260 * A key point of this class is also that it allows container 261 * writers to 'assume' Allocator::pointer is a typedef for a normal 262 * pointer. This class supports most of the conventions of a true 263 * pointer, and can, for instance handle implicit conversion to 264 * const and base class pointer types. The only impositions on 265 * container writers to support extended pointers are: 1) use the 266 * Allocator::pointer typedef appropriately for pointer types. 2) 267 * if you need pointer casting, use the __pointer_cast<> functions 268 * from ext/cast.h. This allows pointer cast operations to be 269 * overloaded as necessary by custom pointers. 270 * 271 * Note: The const qualifier works with this pointer adapter as 272 * follows: 273 * 274 * _Tp* == _Pointer_adapter<_Std_pointer_impl<_Tp> >; 275 * const _Tp* == _Pointer_adapter<_Std_pointer_impl<const _Tp> >; 276 * _Tp* const == const _Pointer_adapter<_Std_pointer_impl<_Tp> >; 277 * const _Tp* const == const _Pointer_adapter<_Std_pointer_impl<const _Tp> >; 278 */ 279 template<typename _Storage_policy> 280 class _Pointer_adapter : public _Storage_policy 281 { 282 public: 283 typedef typename _Storage_policy::element_type element_type; 284 285 // These are needed for iterator_traits 286 typedef std::random_access_iterator_tag iterator_category; 287 typedef typename _Unqualified_type<element_type>::type value_type; 288 typedef std::ptrdiff_t difference_type; 289 typedef _Pointer_adapter pointer; 290 typedef typename _Reference_type<element_type>::reference reference; 291 292 // Reminder: 'const' methods mean that the method is valid when the 293 // pointer is immutable, and has nothing to do with whether the 294 // 'pointee' is const. 295 296 // Default Constructor (Convert from element_type*) 297 _Pointer_adapter(element_type* __arg = 0) 298 { _Storage_policy::set(__arg); } 299 300 // Copy constructor from _Pointer_adapter of same type. 301 _Pointer_adapter(const _Pointer_adapter& __arg) 302 { _Storage_policy::set(__arg.get()); } 303 304 // Convert from _Up* if conversion to element_type* is valid. 305 template<typename _Up> 306 _Pointer_adapter(_Up* __arg) 307 { _Storage_policy::set(__arg); } 308 309 // Conversion from another _Pointer_adapter if _Up if static cast is 310 // valid. 311 template<typename _Up> 312 _Pointer_adapter(const _Pointer_adapter<_Up>& __arg) 313 { _Storage_policy::set(__arg.get()); } 314 315 // Destructor 316 ~_Pointer_adapter() { } 317 318 // Assignment operator 319 _Pointer_adapter& 320 operator=(const _Pointer_adapter& __arg) 321 { 322 _Storage_policy::set(__arg.get()); 323 return *this; 324 } 325 326 template<typename _Up> 327 _Pointer_adapter& 328 operator=(const _Pointer_adapter<_Up>& __arg) 329 { 330 _Storage_policy::set(__arg.get()); 331 return *this; 332 } 333 334 template<typename _Up> 335 _Pointer_adapter& 336 operator=(_Up* __arg) 337 { 338 _Storage_policy::set(__arg); 339 return *this; 340 } 341 342 // Operator*, returns element_type& 343 inline reference 344 operator*() const 345 { return *(_Storage_policy::get()); } 346 347 // Operator->, returns element_type* 348 inline element_type* 349 operator->() const 350 { return _Storage_policy::get(); } 351 352 // Operator[], returns a element_type& to the item at that loc. 353 inline reference 354 operator[](std::ptrdiff_t __index) const 355 { return _Storage_policy::get()[__index]; } 356 357 // To allow implicit conversion to "bool", for "if (ptr)..." 358 private: 359 typedef element_type*(_Pointer_adapter::*__unspecified_bool_type)() const; 360 361 public: 362 operator __unspecified_bool_type() const 363 { 364 return _Storage_policy::get() == 0 ? 0 : 365 &_Pointer_adapter::operator->; 366 } 367 368 // ! operator (for: if (!ptr)...) 369 inline bool 370 operator!() const 371 { return (_Storage_policy::get() == 0); } 372 373 // Pointer differences 374 inline friend std::ptrdiff_t 375 operator-(const _Pointer_adapter& __lhs, element_type* __rhs) 376 { return (__lhs.get() - __rhs); } 377 378 inline friend std::ptrdiff_t 379 operator-(element_type* __lhs, const _Pointer_adapter& __rhs) 380 { return (__lhs - __rhs.get()); } 381 382 template<typename _Up> 383 inline friend std::ptrdiff_t 384 operator-(const _Pointer_adapter& __lhs, _Up* __rhs) 385 { return (__lhs.get() - __rhs); } 386 387 template<typename _Up> 388 inline friend std::ptrdiff_t 389 operator-(_Up* __lhs, const _Pointer_adapter& __rhs) 390 { return (__lhs - __rhs.get()); } 391 392 template<typename _Up> 393 inline std::ptrdiff_t 394 operator-(const _Pointer_adapter<_Up>& __rhs) const 395 { return (_Storage_policy::get() - __rhs.get()); } 396 397 // Pointer math 398 // Note: There is a reason for all this overloading based on different 399 // integer types. In some libstdc++-v3 test cases, a templated 400 // operator+ is declared which can match any types. This operator 401 // tends to "steal" the recognition of _Pointer_adapter's own operator+ 402 // unless the integer type matches perfectly. 403 404 #define _CXX_POINTER_ARITH_OPERATOR_SET(INT_TYPE) \ 405 inline friend _Pointer_adapter \ 406 operator+(const _Pointer_adapter& __lhs, INT_TYPE __offset) \ 407 { return _Pointer_adapter(__lhs.get() + __offset); } \ 408 \ 409 inline friend _Pointer_adapter \ 410 operator+(INT_TYPE __offset, const _Pointer_adapter& __rhs) \ 411 { return _Pointer_adapter(__rhs.get() + __offset); } \ 412 \ 413 inline friend _Pointer_adapter \ 414 operator-(const _Pointer_adapter& __lhs, INT_TYPE __offset) \ 415 { return _Pointer_adapter(__lhs.get() - __offset); } \ 416 \ 417 inline _Pointer_adapter& \ 418 operator+=(INT_TYPE __offset) \ 419 { \ 420 _Storage_policy::set(_Storage_policy::get() + __offset); \ 421 return *this; \ 422 } \ 423 \ 424 inline _Pointer_adapter& \ 425 operator-=(INT_TYPE __offset) \ 426 { \ 427 _Storage_policy::set(_Storage_policy::get() - __offset); \ 428 return *this; \ 429 } \ 430 // END of _CXX_POINTER_ARITH_OPERATOR_SET macro 431 432 // Expand into the various pointer arithmetic operators needed. 433 _CXX_POINTER_ARITH_OPERATOR_SET(short); 434 _CXX_POINTER_ARITH_OPERATOR_SET(unsigned short); 435 _CXX_POINTER_ARITH_OPERATOR_SET(int); 436 _CXX_POINTER_ARITH_OPERATOR_SET(unsigned int); 437 _CXX_POINTER_ARITH_OPERATOR_SET(long); 438 _CXX_POINTER_ARITH_OPERATOR_SET(unsigned long); 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 }; // class _Pointer_adapter 472 473 474 #define _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(OPERATOR) \ 475 template<typename _Tp1, typename _Tp2> \ 476 inline bool \ 477 operator OPERATOR(const _Pointer_adapter<_Tp1>& __lhs, _Tp2 __rhs) \ 478 { return __lhs.get() OPERATOR __rhs; } \ 479 \ 480 template<typename _Tp1, typename _Tp2> \ 481 inline bool \ 482 operator OPERATOR(_Tp1 __lhs, const _Pointer_adapter<_Tp2>& __rhs) \ 483 { return __lhs OPERATOR __rhs.get(); } \ 484 \ 485 template<typename _Tp1, typename _Tp2> \ 486 inline bool \ 487 operator OPERATOR(const _Pointer_adapter<_Tp1>& __lhs, \ 488 const _Pointer_adapter<_Tp2>& __rhs) \ 489 { return __lhs.get() OPERATOR __rhs.get(); } \ 490 \ 491 // End GCC_CXX_POINTER_COMPARISON_OPERATION_SET Macro 492 493 // Expand into the various comparison operators needed. 494 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(==) 495 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(!=) 496 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(<) 497 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(<=) 498 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(>) 499 _GCC_CXX_POINTER_COMPARISON_OPERATION_SET(>=) 500 501 // These are here for expressions like "ptr == 0", "ptr != 0" 502 template<typename _Tp> 503 inline bool 504 operator==(const _Pointer_adapter<_Tp>& __lhs, int __rhs) 505 { return __lhs.get() == reinterpret_cast<void*>(__rhs); } 506 507 template<typename _Tp> 508 inline bool 509 operator==(int __lhs, const _Pointer_adapter<_Tp>& __rhs) 510 { return __rhs.get() == reinterpret_cast<void*>(__lhs); } 511 512 template<typename _Tp> 513 inline bool 514 operator!=(const _Pointer_adapter<_Tp>& __lhs, int __rhs) 515 { return __lhs.get() != reinterpret_cast<void*>(__rhs); } 516 517 template<typename _Tp> 518 inline bool 519 operator!=(int __lhs, const _Pointer_adapter<_Tp>& __rhs) 520 { return __rhs.get() != reinterpret_cast<void*>(__lhs); } 521 522 /** 523 * Comparison operators for _Pointer_adapter defer to the base class' 524 * comparison operators, when possible. 525 */ 526 template<typename _Tp> 527 inline bool 528 operator==(const _Pointer_adapter<_Tp>& __lhs, 529 const _Pointer_adapter<_Tp>& __rhs) 530 { return __lhs._Tp::operator==(__rhs); } 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) || __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)); } 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) || __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)); } 555 556 template<typename _CharT, typename _Traits, typename _StoreT> 557 inline std::basic_ostream<_CharT, _Traits>& 558 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 559 const _Pointer_adapter<_StoreT>& __p) 560 { return (__os << __p.get()); } 561 562 _GLIBCXX_END_NAMESPACE_VERSION 563 } // namespace 564 565 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 566 namespace std _GLIBCXX_VISIBILITY(default) 567 { 568 _GLIBCXX_BEGIN_NAMESPACE_VERSION 569 570 template<typename _Storage_policy> 571 struct pointer_traits<__gnu_cxx::_Pointer_adapter<_Storage_policy>> 572 { 573 /// The pointer type 574 typedef __gnu_cxx::_Pointer_adapter<_Storage_policy> pointer; 575 /// The type pointed to 576 typedef typename pointer::element_type element_type; 577 /// Type used to represent the difference between two pointers 578 typedef typename pointer::difference_type difference_type; 579 580 template<typename _Up> 581 using rebind = typename __gnu_cxx::_Pointer_adapter< 582 typename pointer_traits<_Storage_policy>::rebind<_Up>>; 583 584 static pointer pointer_to(typename pointer::reference __r) noexcept 585 { return pointer(std::addressof(__r)); } 586 }; 587 588 _GLIBCXX_END_NAMESPACE_VERSION 589 } // namespace 590 #endif 591 592 #endif // _POINTER_H 593