1 // Allocator traits -*- C++ -*-
2
3 // Copyright (C) 2011-2014 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 /** @file bits/alloc_traits.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{memory}
28 */
29
30 #ifndef _ALLOC_TRAITS_H
31 #define _ALLOC_TRAITS_H 1
32
33 #if __cplusplus >= 201103L
34
35 #include <bits/memoryfwd.h>
36 #include <bits/ptr_traits.h>
37 #include <ext/numeric_traits.h>
38
_GLIBCXX_VISIBILITY(default)39 namespace std _GLIBCXX_VISIBILITY(default)
40 {
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
42
43 template<typename _Alloc, typename _Tp>
44 class __alloctr_rebind_helper
45 {
46 template<typename _Alloc2, typename _Tp2>
47 static constexpr true_type
48 _S_chk(typename _Alloc2::template rebind<_Tp2>::other*);
49
50 template<typename, typename>
51 static constexpr false_type
52 _S_chk(...);
53
54 public:
55 using __type = decltype(_S_chk<_Alloc, _Tp>(nullptr));
56 };
57
58 template<typename _Alloc, typename _Tp,
59 bool = __alloctr_rebind_helper<_Alloc, _Tp>::__type::value>
60 struct __alloctr_rebind;
61
62 template<typename _Alloc, typename _Tp>
63 struct __alloctr_rebind<_Alloc, _Tp, true>
64 {
65 typedef typename _Alloc::template rebind<_Tp>::other __type;
66 };
67
68 template<template<typename, typename...> class _Alloc, typename _Tp,
69 typename _Up, typename... _Args>
70 struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false>
71 {
72 typedef _Alloc<_Tp, _Args...> __type;
73 };
74
75 /**
76 * @brief Uniform interface to all allocator types.
77 * @ingroup allocators
78 */
79 template<typename _Alloc>
80 struct allocator_traits
81 {
82 /// The allocator type
83 typedef _Alloc allocator_type;
84 /// The allocated type
85 typedef typename _Alloc::value_type value_type;
86
87 #define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \
88 private: \
89 template<typename _Tp> \
90 static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \
91 static _ALT _S_##_NTYPE##_helper(...); \
92 typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \
93 public:
94
95 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
96
97 /**
98 * @brief The allocator's pointer type.
99 *
100 * @c Alloc::pointer if that type exists, otherwise @c value_type*
101 */
102 typedef __pointer pointer;
103
104 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
105 typename pointer_traits<pointer>::template rebind<const value_type>)
106
107 /**
108 * @brief The allocator's const pointer type.
109 *
110 * @c Alloc::const_pointer if that type exists, otherwise
111 * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
112 */
113 typedef __const_pointer const_pointer;
114
115 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
116 typename pointer_traits<pointer>::template rebind<void>)
117
118 /**
119 * @brief The allocator's void pointer type.
120 *
121 * @c Alloc::void_pointer if that type exists, otherwise
122 * <tt> pointer_traits<pointer>::rebind<void> </tt>
123 */
124 typedef __void_pointer void_pointer;
125
126 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
127 typename pointer_traits<pointer>::template rebind<const void>)
128
129 /**
130 * @brief The allocator's const void pointer type.
131 *
132 * @c Alloc::const_void_pointer if that type exists, otherwise
133 * <tt> pointer_traits<pointer>::rebind<const void> </tt>
134 */
135 typedef __const_void_pointer const_void_pointer;
136
137 _GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type,
138 typename pointer_traits<pointer>::difference_type)
139
140 /**
141 * @brief The allocator's difference type
142 *
143 * @c Alloc::difference_type if that type exists, otherwise
144 * <tt> pointer_traits<pointer>::difference_type </tt>
145 */
146 typedef __difference_type difference_type;
147
148 _GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type,
149 typename make_unsigned<difference_type>::type)
150
151 /**
152 * @brief The allocator's size type
153 *
154 * @c Alloc::size_type if that type exists, otherwise
155 * <tt> make_unsigned<difference_type>::type </tt>
156 */
157 typedef __size_type size_type;
158
159 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment,
160 false_type)
161
162 /**
163 * @brief How the allocator is propagated on copy assignment
164 *
165 * @c Alloc::propagate_on_container_copy_assignment if that type exists,
166 * otherwise @c false_type
167 */
168 typedef __propagate_on_container_copy_assignment
169 propagate_on_container_copy_assignment;
170
171 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment,
172 false_type)
173
174 /**
175 * @brief How the allocator is propagated on move assignment
176 *
177 * @c Alloc::propagate_on_container_move_assignment if that type exists,
178 * otherwise @c false_type
179 */
180 typedef __propagate_on_container_move_assignment
181 propagate_on_container_move_assignment;
182
183 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
184 false_type)
185
186 /**
187 * @brief How the allocator is propagated on swap
188 *
189 * @c Alloc::propagate_on_container_swap if that type exists,
190 * otherwise @c false_type
191 */
192 typedef __propagate_on_container_swap propagate_on_container_swap;
193
194 #undef _GLIBCXX_ALLOC_TR_NESTED_TYPE
195
196 template<typename _Tp>
197 using rebind_alloc = typename __alloctr_rebind<_Alloc, _Tp>::__type;
198 template<typename _Tp>
199 using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
200
201 private:
202 template<typename _Alloc2>
203 struct __allocate_helper
204 {
205 template<typename _Alloc3,
206 typename = decltype(std::declval<_Alloc3*>()->allocate(
207 std::declval<size_type>(),
208 std::declval<const_void_pointer>()))>
209 static true_type __test(int);
210
211 template<typename>
212 static false_type __test(...);
213
214 using type = decltype(__test<_Alloc>(0));
215 };
216
217 template<typename _Alloc2>
218 using __has_allocate = typename __allocate_helper<_Alloc2>::type;
219
220 template<typename _Alloc2,
221 typename = _Require<__has_allocate<_Alloc2>>>
222 static pointer
223 _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint)
224 { return __a.allocate(__n, __hint); }
225
226 template<typename _Alloc2, typename _UnusedHint,
227 typename = _Require<__not_<__has_allocate<_Alloc2>>>>
228 static pointer
229 _S_allocate(_Alloc2& __a, size_type __n, _UnusedHint)
230 { return __a.allocate(__n); }
231
232 template<typename _Tp, typename... _Args>
233 struct __construct_helper
234 {
235 template<typename _Alloc2,
236 typename = decltype(std::declval<_Alloc2*>()->construct(
237 std::declval<_Tp*>(), std::declval<_Args>()...))>
238 static true_type __test(int);
239
240 template<typename>
241 static false_type __test(...);
242
243 using type = decltype(__test<_Alloc>(0));
244 };
245
246 template<typename _Tp, typename... _Args>
247 using __has_construct
248 = typename __construct_helper<_Tp, _Args...>::type;
249
250 template<typename _Tp, typename... _Args>
251 static _Require<__has_construct<_Tp, _Args...>>
252 _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
253 { __a.construct(__p, std::forward<_Args>(__args)...); }
254
255 template<typename _Tp, typename... _Args>
256 static
257 _Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
258 is_constructible<_Tp, _Args...>>>
259 _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
260 { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
261
262 template<typename _Tp>
263 struct __destroy_helper
264 {
265 template<typename _Alloc2,
266 typename = decltype(std::declval<_Alloc2*>()->destroy(
267 std::declval<_Tp*>()))>
268 static true_type __test(int);
269
270 template<typename>
271 static false_type __test(...);
272
273 using type = decltype(__test<_Alloc>(0));
274 };
275
276 template<typename _Tp>
277 using __has_destroy = typename __destroy_helper<_Tp>::type;
278
279 template<typename _Tp>
280 static _Require<__has_destroy<_Tp>>
281 _S_destroy(_Alloc& __a, _Tp* __p)
282 { __a.destroy(__p); }
283
284 template<typename _Tp>
285 static _Require<__not_<__has_destroy<_Tp>>>
286 _S_destroy(_Alloc&, _Tp* __p)
287 { __p->~_Tp(); }
288
289 template<typename _Alloc2>
290 struct __maxsize_helper
291 {
292 template<typename _Alloc3,
293 typename = decltype(std::declval<_Alloc3*>()->max_size())>
294 static true_type __test(int);
295
296 template<typename>
297 static false_type __test(...);
298
299 using type = decltype(__test<_Alloc2>(0));
300 };
301
302 template<typename _Alloc2>
303 using __has_max_size = typename __maxsize_helper<_Alloc2>::type;
304
305 template<typename _Alloc2,
306 typename = _Require<__has_max_size<_Alloc2>>>
307 static size_type
308 _S_max_size(_Alloc2& __a, int)
309 { return __a.max_size(); }
310
311 template<typename _Alloc2,
312 typename = _Require<__not_<__has_max_size<_Alloc2>>>>
313 static size_type
314 _S_max_size(_Alloc2&, ...)
315 { return __gnu_cxx::__numeric_traits<size_type>::__max; }
316
317 template<typename _Alloc2>
318 struct __select_helper
319 {
320 template<typename _Alloc3, typename
321 = decltype(std::declval<_Alloc3*>()
322 ->select_on_container_copy_construction())>
323 static true_type __test(int);
324
325 template<typename>
326 static false_type __test(...);
327
328 using type = decltype(__test<_Alloc2>(0));
329 };
330
331 template<typename _Alloc2>
332 using __has_soccc = typename __select_helper<_Alloc2>::type;
333
334 template<typename _Alloc2,
335 typename = _Require<__has_soccc<_Alloc2>>>
336 static _Alloc2
337 _S_select(_Alloc2& __a, int)
338 { return __a.select_on_container_copy_construction(); }
339
340 template<typename _Alloc2,
341 typename = _Require<__not_<__has_soccc<_Alloc2>>>>
342 static _Alloc2
343 _S_select(_Alloc2& __a, ...)
344 { return __a; }
345
346 public:
347
348 /**
349 * @brief Allocate memory.
350 * @param __a An allocator.
351 * @param __n The number of objects to allocate space for.
352 *
353 * Calls @c a.allocate(n)
354 */
355 static pointer
356 allocate(_Alloc& __a, size_type __n)
357 { return __a.allocate(__n); }
358
359 /**
360 * @brief Allocate memory.
361 * @param __a An allocator.
362 * @param __n The number of objects to allocate space for.
363 * @param __hint Aid to locality.
364 * @return Memory of suitable size and alignment for @a n objects
365 * of type @c value_type
366 *
367 * Returns <tt> a.allocate(n, hint) </tt> if that expression is
368 * well-formed, otherwise returns @c a.allocate(n)
369 */
370 static pointer
371 allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
372 { return _S_allocate(__a, __n, __hint); }
373
374 /**
375 * @brief Deallocate memory.
376 * @param __a An allocator.
377 * @param __p Pointer to the memory to deallocate.
378 * @param __n The number of objects space was allocated for.
379 *
380 * Calls <tt> a.deallocate(p, n) </tt>
381 */
382 static void deallocate(_Alloc& __a, pointer __p, size_type __n)
383 { __a.deallocate(__p, __n); }
384
385 /**
386 * @brief Construct an object of type @a _Tp
387 * @param __a An allocator.
388 * @param __p Pointer to memory of suitable size and alignment for Tp
389 * @param __args Constructor arguments.
390 *
391 * Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
392 * if that expression is well-formed, otherwise uses placement-new
393 * to construct an object of type @a _Tp at location @a __p from the
394 * arguments @a __args...
395 */
396 template<typename _Tp, typename... _Args>
397 static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
398 -> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
399 { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
400
401 /**
402 * @brief Destroy an object of type @a _Tp
403 * @param __a An allocator.
404 * @param __p Pointer to the object to destroy
405 *
406 * Calls @c __a.destroy(__p) if that expression is well-formed,
407 * otherwise calls @c __p->~_Tp()
408 */
409 template <class _Tp>
410 static void destroy(_Alloc& __a, _Tp* __p)
411 { _S_destroy(__a, __p); }
412
413 /**
414 * @brief The maximum supported allocation size
415 * @param __a An allocator.
416 * @return @c __a.max_size() or @c numeric_limits<size_type>::max()
417 *
418 * Returns @c __a.max_size() if that expression is well-formed,
419 * otherwise returns @c numeric_limits<size_type>::max()
420 */
421 static size_type max_size(const _Alloc& __a) noexcept
422 { return _S_max_size(__a, 0); }
423
424 /**
425 * @brief Obtain an allocator to use when copying a container.
426 * @param __rhs An allocator.
427 * @return @c __rhs.select_on_container_copy_construction() or @a __rhs
428 *
429 * Returns @c __rhs.select_on_container_copy_construction() if that
430 * expression is well-formed, otherwise returns @a __rhs
431 */
432 static _Alloc
433 select_on_container_copy_construction(const _Alloc& __rhs)
434 { return _S_select(__rhs, 0); }
435 };
436
437 template<typename _Alloc>
438 inline void
439 __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
440 { __one = __two; }
441
442 template<typename _Alloc>
443 inline void
444 __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
445 { }
446
447 template<typename _Alloc>
448 inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
449 {
450 typedef allocator_traits<_Alloc> __traits;
451 typedef typename __traits::propagate_on_container_copy_assignment __pocca;
452 __do_alloc_on_copy(__one, __two, __pocca());
453 }
454
455 template<typename _Alloc>
456 inline _Alloc __alloc_on_copy(const _Alloc& __a)
457 {
458 typedef allocator_traits<_Alloc> __traits;
459 return __traits::select_on_container_copy_construction(__a);
460 }
461
462 template<typename _Alloc>
463 inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
464 { __one = std::move(__two); }
465
466 template<typename _Alloc>
467 inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
468 { }
469
470 template<typename _Alloc>
471 inline void __alloc_on_move(_Alloc& __one, _Alloc& __two)
472 {
473 typedef allocator_traits<_Alloc> __traits;
474 typedef typename __traits::propagate_on_container_move_assignment __pocma;
475 __do_alloc_on_move(__one, __two, __pocma());
476 }
477
478 template<typename _Alloc>
479 inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
480 {
481 using std::swap;
482 swap(__one, __two);
483 }
484
485 template<typename _Alloc>
486 inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
487 { }
488
489 template<typename _Alloc>
490 inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two)
491 {
492 typedef allocator_traits<_Alloc> __traits;
493 typedef typename __traits::propagate_on_container_swap __pocs;
494 __do_alloc_on_swap(__one, __two, __pocs());
495 }
496
497 template<typename _Alloc>
498 class __is_copy_insertable_impl
499 {
500 typedef allocator_traits<_Alloc> _Traits;
501
502 template<typename _Up, typename
503 = decltype(_Traits::construct(std::declval<_Alloc&>(),
504 std::declval<_Up*>(),
505 std::declval<const _Up&>()))>
506 static true_type
507 _M_select(int);
508
509 template<typename _Up>
510 static false_type
511 _M_select(...);
512
513 public:
514 typedef decltype(_M_select<typename _Alloc::value_type>(0)) type;
515 };
516
517 // true if _Alloc::value_type is CopyInsertable into containers using _Alloc
518 template<typename _Alloc>
519 struct __is_copy_insertable
520 : __is_copy_insertable_impl<_Alloc>::type
521 { };
522
523 // std::allocator<_Tp> just requires CopyConstructible
524 template<typename _Tp>
525 struct __is_copy_insertable<allocator<_Tp>>
526 : is_copy_constructible<_Tp>
527 { };
528
529 _GLIBCXX_END_NAMESPACE_VERSION
530 } // namespace std
531
532 #endif
533 #endif
534