1 // Allocator traits -*- C++ -*-
2
3 // Copyright (C) 2011-2019 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
39 #define __cpp_lib_allocator_traits_is_always_equal 201411
40
_GLIBCXX_VISIBILITY(default)41 namespace std _GLIBCXX_VISIBILITY(default)
42 {
43 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44
45 struct __allocator_traits_base
46 {
47 template<typename _Tp, typename _Up, typename = void>
48 struct __rebind : __replace_first_arg<_Tp, _Up> { };
49
50 template<typename _Tp, typename _Up>
51 struct __rebind<_Tp, _Up,
52 __void_t<typename _Tp::template rebind<_Up>::other>>
53 { using type = typename _Tp::template rebind<_Up>::other; };
54
55 protected:
56 template<typename _Tp>
57 using __pointer = typename _Tp::pointer;
58 template<typename _Tp>
59 using __c_pointer = typename _Tp::const_pointer;
60 template<typename _Tp>
61 using __v_pointer = typename _Tp::void_pointer;
62 template<typename _Tp>
63 using __cv_pointer = typename _Tp::const_void_pointer;
64 template<typename _Tp>
65 using __pocca = typename _Tp::propagate_on_container_copy_assignment;
66 template<typename _Tp>
67 using __pocma = typename _Tp::propagate_on_container_move_assignment;
68 template<typename _Tp>
69 using __pocs = typename _Tp::propagate_on_container_swap;
70 template<typename _Tp>
71 using __equal = typename _Tp::is_always_equal;
72 };
73
74 template<typename _Alloc, typename _Up>
75 using __alloc_rebind
76 = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;
77
78 /**
79 * @brief Uniform interface to all allocator types.
80 * @ingroup allocators
81 */
82 template<typename _Alloc>
83 struct allocator_traits : __allocator_traits_base
84 {
85 /// The allocator type
86 typedef _Alloc allocator_type;
87 /// The allocated type
88 typedef typename _Alloc::value_type value_type;
89
90 /**
91 * @brief The allocator's pointer type.
92 *
93 * @c Alloc::pointer if that type exists, otherwise @c value_type*
94 */
95 using pointer = __detected_or_t<value_type*, __pointer, _Alloc>;
96
97 private:
98 // Select _Func<_Alloc> or pointer_traits<pointer>::rebind<_Tp>
99 template<template<typename> class _Func, typename _Tp, typename = void>
100 struct _Ptr
101 {
102 using type = typename pointer_traits<pointer>::template rebind<_Tp>;
103 };
104
105 template<template<typename> class _Func, typename _Tp>
106 struct _Ptr<_Func, _Tp, __void_t<_Func<_Alloc>>>
107 {
108 using type = _Func<_Alloc>;
109 };
110
111 // Select _A2::difference_type or pointer_traits<_Ptr>::difference_type
112 template<typename _A2, typename _PtrT, typename = void>
113 struct _Diff
114 { using type = typename pointer_traits<_PtrT>::difference_type; };
115
116 template<typename _A2, typename _PtrT>
117 struct _Diff<_A2, _PtrT, __void_t<typename _A2::difference_type>>
118 { using type = typename _A2::difference_type; };
119
120 // Select _A2::size_type or make_unsigned<_DiffT>::type
121 template<typename _A2, typename _DiffT, typename = void>
122 struct _Size : make_unsigned<_DiffT> { };
123
124 template<typename _A2, typename _DiffT>
125 struct _Size<_A2, _DiffT, __void_t<typename _A2::size_type>>
126 { using type = typename _A2::size_type; };
127
128 public:
129 /**
130 * @brief The allocator's const pointer type.
131 *
132 * @c Alloc::const_pointer if that type exists, otherwise
133 * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
134 */
135 using const_pointer = typename _Ptr<__c_pointer, const value_type>::type;
136
137 /**
138 * @brief The allocator's void pointer type.
139 *
140 * @c Alloc::void_pointer if that type exists, otherwise
141 * <tt> pointer_traits<pointer>::rebind<void> </tt>
142 */
143 using void_pointer = typename _Ptr<__v_pointer, void>::type;
144
145 /**
146 * @brief The allocator's const void pointer type.
147 *
148 * @c Alloc::const_void_pointer if that type exists, otherwise
149 * <tt> pointer_traits<pointer>::rebind<const void> </tt>
150 */
151 using const_void_pointer = typename _Ptr<__cv_pointer, const void>::type;
152
153 /**
154 * @brief The allocator's difference type
155 *
156 * @c Alloc::difference_type if that type exists, otherwise
157 * <tt> pointer_traits<pointer>::difference_type </tt>
158 */
159 using difference_type = typename _Diff<_Alloc, pointer>::type;
160
161 /**
162 * @brief The allocator's size type
163 *
164 * @c Alloc::size_type if that type exists, otherwise
165 * <tt> make_unsigned<difference_type>::type </tt>
166 */
167 using size_type = typename _Size<_Alloc, difference_type>::type;
168
169 /**
170 * @brief How the allocator is propagated on copy assignment
171 *
172 * @c Alloc::propagate_on_container_copy_assignment if that type exists,
173 * otherwise @c false_type
174 */
175 using propagate_on_container_copy_assignment
176 = __detected_or_t<false_type, __pocca, _Alloc>;
177
178 /**
179 * @brief How the allocator is propagated on move assignment
180 *
181 * @c Alloc::propagate_on_container_move_assignment if that type exists,
182 * otherwise @c false_type
183 */
184 using propagate_on_container_move_assignment
185 = __detected_or_t<false_type, __pocma, _Alloc>;
186
187 /**
188 * @brief How the allocator is propagated on swap
189 *
190 * @c Alloc::propagate_on_container_swap if that type exists,
191 * otherwise @c false_type
192 */
193 using propagate_on_container_swap
194 = __detected_or_t<false_type, __pocs, _Alloc>;
195
196 /**
197 * @brief Whether all instances of the allocator type compare equal.
198 *
199 * @c Alloc::is_always_equal if that type exists,
200 * otherwise @c is_empty<Alloc>::type
201 */
202 using is_always_equal
203 = __detected_or_t<typename is_empty<_Alloc>::type, __equal, _Alloc>;
204
205 template<typename _Tp>
206 using rebind_alloc = __alloc_rebind<_Alloc, _Tp>;
207 template<typename _Tp>
208 using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
209
210 private:
211 template<typename _Alloc2>
212 static auto
213 _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int)
214 -> decltype(__a.allocate(__n, __hint))
215 { return __a.allocate(__n, __hint); }
216
217 template<typename _Alloc2>
218 static pointer
219 _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...)
220 { return __a.allocate(__n); }
221
222 template<typename _Tp, typename... _Args>
223 struct __construct_helper
224 {
225 template<typename _Alloc2,
226 typename = decltype(std::declval<_Alloc2*>()->construct(
227 std::declval<_Tp*>(), std::declval<_Args>()...))>
228 static true_type __test(int);
229
230 template<typename>
231 static false_type __test(...);
232
233 using type = decltype(__test<_Alloc>(0));
234 };
235
236 template<typename _Tp, typename... _Args>
237 using __has_construct
238 = typename __construct_helper<_Tp, _Args...>::type;
239
240 template<typename _Tp, typename... _Args>
241 static _Require<__has_construct<_Tp, _Args...>>
242 _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
243 noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...)))
244 { __a.construct(__p, std::forward<_Args>(__args)...); }
245
246 template<typename _Tp, typename... _Args>
247 static
248 _Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
249 is_constructible<_Tp, _Args...>>>
250 _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
251 noexcept(std::is_nothrow_constructible<_Tp, _Args...>::value)
252 { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
253
254 template<typename _Alloc2, typename _Tp>
255 static auto
256 _S_destroy(_Alloc2& __a, _Tp* __p, int)
257 noexcept(noexcept(__a.destroy(__p)))
258 -> decltype(__a.destroy(__p))
259 { __a.destroy(__p); }
260
261 template<typename _Alloc2, typename _Tp>
262 static void
263 _S_destroy(_Alloc2&, _Tp* __p, ...)
264 noexcept(std::is_nothrow_destructible<_Tp>::value)
265 { __p->~_Tp(); }
266
267 template<typename _Alloc2>
268 static auto
269 _S_max_size(_Alloc2& __a, int)
270 -> decltype(__a.max_size())
271 { return __a.max_size(); }
272
273 template<typename _Alloc2>
274 static size_type
275 _S_max_size(_Alloc2&, ...)
276 {
277 // _GLIBCXX_RESOLVE_LIB_DEFECTS
278 // 2466. allocator_traits::max_size() default behavior is incorrect
279 return __gnu_cxx::__numeric_traits<size_type>::__max
280 / sizeof(value_type);
281 }
282
283 template<typename _Alloc2>
284 static auto
285 _S_select(_Alloc2& __a, int)
286 -> decltype(__a.select_on_container_copy_construction())
287 { return __a.select_on_container_copy_construction(); }
288
289 template<typename _Alloc2>
290 static _Alloc2
291 _S_select(_Alloc2& __a, ...)
292 { return __a; }
293
294 public:
295
296 /**
297 * @brief Allocate memory.
298 * @param __a An allocator.
299 * @param __n The number of objects to allocate space for.
300 *
301 * Calls @c a.allocate(n)
302 */
303 _GLIBCXX_NODISCARD static pointer
304 allocate(_Alloc& __a, size_type __n)
305 { return __a.allocate(__n); }
306
307 /**
308 * @brief Allocate memory.
309 * @param __a An allocator.
310 * @param __n The number of objects to allocate space for.
311 * @param __hint Aid to locality.
312 * @return Memory of suitable size and alignment for @a n objects
313 * of type @c value_type
314 *
315 * Returns <tt> a.allocate(n, hint) </tt> if that expression is
316 * well-formed, otherwise returns @c a.allocate(n)
317 */
318 _GLIBCXX_NODISCARD static pointer
319 allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
320 { return _S_allocate(__a, __n, __hint, 0); }
321
322 /**
323 * @brief Deallocate memory.
324 * @param __a An allocator.
325 * @param __p Pointer to the memory to deallocate.
326 * @param __n The number of objects space was allocated for.
327 *
328 * Calls <tt> a.deallocate(p, n) </tt>
329 */
330 static void
331 deallocate(_Alloc& __a, pointer __p, size_type __n)
332 { __a.deallocate(__p, __n); }
333
334 /**
335 * @brief Construct an object of type `_Tp`
336 * @param __a An allocator.
337 * @param __p Pointer to memory of suitable size and alignment for Tp
338 * @param __args Constructor arguments.
339 *
340 * Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
341 * if that expression is well-formed, otherwise uses placement-new
342 * to construct an object of type @a _Tp at location @a __p from the
343 * arguments @a __args...
344 */
345 template<typename _Tp, typename... _Args>
346 static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
347 noexcept(noexcept(_S_construct(__a, __p,
348 std::forward<_Args>(__args)...)))
349 -> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
350 { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
351
352 /**
353 * @brief Destroy an object of type @a _Tp
354 * @param __a An allocator.
355 * @param __p Pointer to the object to destroy
356 *
357 * Calls @c __a.destroy(__p) if that expression is well-formed,
358 * otherwise calls @c __p->~_Tp()
359 */
360 template<typename _Tp>
361 static void destroy(_Alloc& __a, _Tp* __p)
362 noexcept(noexcept(_S_destroy(__a, __p, 0)))
363 { _S_destroy(__a, __p, 0); }
364
365 /**
366 * @brief The maximum supported allocation size
367 * @param __a An allocator.
368 * @return @c __a.max_size() or @c numeric_limits<size_type>::max()
369 *
370 * Returns @c __a.max_size() if that expression is well-formed,
371 * otherwise returns @c numeric_limits<size_type>::max()
372 */
373 static size_type max_size(const _Alloc& __a) noexcept
374 { return _S_max_size(__a, 0); }
375
376 /**
377 * @brief Obtain an allocator to use when copying a container.
378 * @param __rhs An allocator.
379 * @return @c __rhs.select_on_container_copy_construction() or @a __rhs
380 *
381 * Returns @c __rhs.select_on_container_copy_construction() if that
382 * expression is well-formed, otherwise returns @a __rhs
383 */
384 static _Alloc
385 select_on_container_copy_construction(const _Alloc& __rhs)
386 { return _S_select(__rhs, 0); }
387 };
388
389 /// Partial specialization for std::allocator.
390 template<typename _Tp>
391 struct allocator_traits<allocator<_Tp>>
392 {
393 /// The allocator type
394 using allocator_type = allocator<_Tp>;
395 /// The allocated type
396 using value_type = _Tp;
397
398 /// The allocator's pointer type.
399 using pointer = _Tp*;
400
401 /// The allocator's const pointer type.
402 using const_pointer = const _Tp*;
403
404 /// The allocator's void pointer type.
405 using void_pointer = void*;
406
407 /// The allocator's const void pointer type.
408 using const_void_pointer = const void*;
409
410 /// The allocator's difference type
411 using difference_type = std::ptrdiff_t;
412
413 /// The allocator's size type
414 using size_type = std::size_t;
415
416 /// How the allocator is propagated on copy assignment
417 using propagate_on_container_copy_assignment = false_type;
418
419 /// How the allocator is propagated on move assignment
420 using propagate_on_container_move_assignment = true_type;
421
422 /// How the allocator is propagated on swap
423 using propagate_on_container_swap = false_type;
424
425 /// Whether all instances of the allocator type compare equal.
426 using is_always_equal = true_type;
427
428 template<typename _Up>
429 using rebind_alloc = allocator<_Up>;
430
431 template<typename _Up>
432 using rebind_traits = allocator_traits<allocator<_Up>>;
433
434 /**
435 * @brief Allocate memory.
436 * @param __a An allocator.
437 * @param __n The number of objects to allocate space for.
438 *
439 * Calls @c a.allocate(n)
440 */
441 _GLIBCXX_NODISCARD static pointer
442 allocate(allocator_type& __a, size_type __n)
443 { return __a.allocate(__n); }
444
445 /**
446 * @brief Allocate memory.
447 * @param __a An allocator.
448 * @param __n The number of objects to allocate space for.
449 * @param __hint Aid to locality.
450 * @return Memory of suitable size and alignment for @a n objects
451 * of type @c value_type
452 *
453 * Returns <tt> a.allocate(n, hint) </tt>
454 */
455 _GLIBCXX_NODISCARD static pointer
456 allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)
457 { return __a.allocate(__n, __hint); }
458
459 /**
460 * @brief Deallocate memory.
461 * @param __a An allocator.
462 * @param __p Pointer to the memory to deallocate.
463 * @param __n The number of objects space was allocated for.
464 *
465 * Calls <tt> a.deallocate(p, n) </tt>
466 */
467 static void
468 deallocate(allocator_type& __a, pointer __p, size_type __n)
469 { __a.deallocate(__p, __n); }
470
471 /**
472 * @brief Construct an object of type @a _Up
473 * @param __a An allocator.
474 * @param __p Pointer to memory of suitable size and alignment for Tp
475 * @param __args Constructor arguments.
476 *
477 * Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
478 */
479 template<typename _Up, typename... _Args>
480 static void
481 construct(allocator_type& __a, _Up* __p, _Args&&... __args)
482 noexcept(std::is_nothrow_constructible<_Up, _Args...>::value)
483 { __a.construct(__p, std::forward<_Args>(__args)...); }
484
485 /**
486 * @brief Destroy an object of type @a _Up
487 * @param __a An allocator.
488 * @param __p Pointer to the object to destroy
489 *
490 * Calls @c __a.destroy(__p).
491 */
492 template<typename _Up>
493 static void
494 destroy(allocator_type& __a, _Up* __p)
495 noexcept(noexcept(__a.destroy(__p)))
496 { __a.destroy(__p); }
497
498 /**
499 * @brief The maximum supported allocation size
500 * @param __a An allocator.
501 * @return @c __a.max_size()
502 */
503 static size_type
504 max_size(const allocator_type& __a) noexcept
505 { return __a.max_size(); }
506
507 /**
508 * @brief Obtain an allocator to use when copying a container.
509 * @param __rhs An allocator.
510 * @return @c __rhs
511 */
512 static allocator_type
513 select_on_container_copy_construction(const allocator_type& __rhs)
514 { return __rhs; }
515 };
516
517
518 template<typename _Alloc>
519 inline void
520 __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
521 { __one = __two; }
522
523 template<typename _Alloc>
524 inline void
525 __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
526 { }
527
528 template<typename _Alloc>
529 inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
530 {
531 typedef allocator_traits<_Alloc> __traits;
532 typedef typename __traits::propagate_on_container_copy_assignment __pocca;
533 __do_alloc_on_copy(__one, __two, __pocca());
534 }
535
536 template<typename _Alloc>
537 inline _Alloc __alloc_on_copy(const _Alloc& __a)
538 {
539 typedef allocator_traits<_Alloc> __traits;
540 return __traits::select_on_container_copy_construction(__a);
541 }
542
543 template<typename _Alloc>
544 inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
545 { __one = std::move(__two); }
546
547 template<typename _Alloc>
548 inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
549 { }
550
551 template<typename _Alloc>
552 inline void __alloc_on_move(_Alloc& __one, _Alloc& __two)
553 {
554 typedef allocator_traits<_Alloc> __traits;
555 typedef typename __traits::propagate_on_container_move_assignment __pocma;
556 __do_alloc_on_move(__one, __two, __pocma());
557 }
558
559 template<typename _Alloc>
560 inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
561 {
562 using std::swap;
563 swap(__one, __two);
564 }
565
566 template<typename _Alloc>
567 inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
568 { }
569
570 template<typename _Alloc>
571 inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two)
572 {
573 typedef allocator_traits<_Alloc> __traits;
574 typedef typename __traits::propagate_on_container_swap __pocs;
575 __do_alloc_on_swap(__one, __two, __pocs());
576 }
577
578 template<typename _Alloc, typename _Tp,
579 typename _ValueT = __remove_cvref_t<typename _Alloc::value_type>,
580 typename = void>
581 struct __is_alloc_insertable_impl
582 : false_type
583 { };
584
585 template<typename _Alloc, typename _Tp, typename _ValueT>
586 struct __is_alloc_insertable_impl<_Alloc, _Tp, _ValueT,
587 __void_t<decltype(allocator_traits<_Alloc>::construct(
588 std::declval<_Alloc&>(), std::declval<_ValueT*>(),
589 std::declval<_Tp>()))>>
590 : true_type
591 { };
592
593 // true if _Alloc::value_type is CopyInsertable into containers using _Alloc
594 // (might be wrong if _Alloc::construct exists but is not constrained,
595 // i.e. actually trying to use it would still be invalid. Use with caution.)
596 template<typename _Alloc>
597 struct __is_copy_insertable
598 : __is_alloc_insertable_impl<_Alloc,
599 typename _Alloc::value_type const&>::type
600 { };
601
602 // std::allocator<_Tp> just requires CopyConstructible
603 template<typename _Tp>
604 struct __is_copy_insertable<allocator<_Tp>>
605 : is_copy_constructible<_Tp>
606 { };
607
608 // true if _Alloc::value_type is MoveInsertable into containers using _Alloc
609 // (might be wrong if _Alloc::construct exists but is not constrained,
610 // i.e. actually trying to use it would still be invalid. Use with caution.)
611 template<typename _Alloc>
612 struct __is_move_insertable
613 : __is_alloc_insertable_impl<_Alloc, typename _Alloc::value_type>::type
614 { };
615
616 // std::allocator<_Tp> just requires MoveConstructible
617 template<typename _Tp>
618 struct __is_move_insertable<allocator<_Tp>>
619 : is_move_constructible<_Tp>
620 { };
621
622 // Trait to detect Allocator-like types.
623 template<typename _Alloc, typename = void>
624 struct __is_allocator : false_type { };
625
626 template<typename _Alloc>
627 struct __is_allocator<_Alloc,
628 __void_t<typename _Alloc::value_type,
629 decltype(std::declval<_Alloc&>().allocate(size_t{}))>>
630 : true_type { };
631
632 template<typename _Alloc>
633 using _RequireAllocator
634 = typename enable_if<__is_allocator<_Alloc>::value, _Alloc>::type;
635
636 template<typename _Alloc>
637 using _RequireNotAllocator
638 = typename enable_if<!__is_allocator<_Alloc>::value, _Alloc>::type;
639
640 _GLIBCXX_END_NAMESPACE_VERSION
641 } // namespace std
642 #endif // C++11
643 #endif // _ALLOC_TRAITS_H
644