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