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