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