1 // Allocator traits -*- C++ -*-
2
3 // Copyright (C) 2011-2023 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 #include <bits/stl_construct.h>
34 #include <bits/memoryfwd.h>
35 #if __cplusplus >= 201103L
36 # include <bits/ptr_traits.h>
37 # include <ext/numeric_traits.h>
38 # if _GLIBCXX_HOSTED
39 # include <bits/allocator.h>
40 # endif
41 #endif
42
43 namespace std _GLIBCXX_VISIBILITY(default)
44 {
45 _GLIBCXX_BEGIN_NAMESPACE_VERSION
46
47 #if __cplusplus >= 201103L
48 #define __cpp_lib_allocator_traits_is_always_equal 201411L
49
50 /// @cond undocumented
51 struct __allocator_traits_base
52 {
53 template<typename _Tp, typename _Up, typename = void>
54 struct __rebind : __replace_first_arg<_Tp, _Up>
55 {
56 static_assert(is_same<
57 typename __replace_first_arg<_Tp, typename _Tp::value_type>::type,
58 _Tp>::value,
59 "allocator_traits<A>::rebind_alloc<A::value_type> must be A");
60 };
61
62 template<typename _Tp, typename _Up>
63 struct __rebind<_Tp, _Up,
64 __void_t<typename _Tp::template rebind<_Up>::other>>
65 {
66 using type = typename _Tp::template rebind<_Up>::other;
67
68 static_assert(is_same<
69 typename _Tp::template rebind<typename _Tp::value_type>::other,
70 _Tp>::value,
71 "allocator_traits<A>::rebind_alloc<A::value_type> must be A");
72 };
73
74 protected:
75 template<typename _Tp>
76 using __pointer = typename _Tp::pointer;
77 template<typename _Tp>
78 using __c_pointer = typename _Tp::const_pointer;
79 template<typename _Tp>
80 using __v_pointer = typename _Tp::void_pointer;
81 template<typename _Tp>
82 using __cv_pointer = typename _Tp::const_void_pointer;
83 template<typename _Tp>
84 using __pocca = typename _Tp::propagate_on_container_copy_assignment;
85 template<typename _Tp>
86 using __pocma = typename _Tp::propagate_on_container_move_assignment;
87 template<typename _Tp>
88 using __pocs = typename _Tp::propagate_on_container_swap;
89 template<typename _Tp>
90 using __equal = __type_identity<typename _Tp::is_always_equal>;
91 };
92
93 template<typename _Alloc, typename _Up>
94 using __alloc_rebind
95 = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;
96 /// @endcond
97
98 /**
99 * @brief Uniform interface to all allocator types.
100 * @headerfile memory
101 * @ingroup allocators
102 * @since C++11
103 */
104 template<typename _Alloc>
105 struct allocator_traits : __allocator_traits_base
106 {
107 /// The allocator type
108 typedef _Alloc allocator_type;
109 /// The allocated type
110 typedef typename _Alloc::value_type value_type;
111
112 /**
113 * @brief The allocator's pointer type.
114 *
115 * @c Alloc::pointer if that type exists, otherwise @c value_type*
116 */
117 using pointer = __detected_or_t<value_type*, __pointer, _Alloc>;
118
119 private:
120 // Select _Func<_Alloc> or pointer_traits<pointer>::rebind<_Tp>
121 template<template<typename> class _Func, typename _Tp, typename = void>
122 struct _Ptr
123 {
124 using type = typename pointer_traits<pointer>::template rebind<_Tp>;
125 };
126
127 template<template<typename> class _Func, typename _Tp>
128 struct _Ptr<_Func, _Tp, __void_t<_Func<_Alloc>>>
129 {
130 using type = _Func<_Alloc>;
131 };
132
133 // Select _A2::difference_type or pointer_traits<_Ptr>::difference_type
134 template<typename _A2, typename _PtrT, typename = void>
135 struct _Diff
136 { using type = typename pointer_traits<_PtrT>::difference_type; };
137
138 template<typename _A2, typename _PtrT>
139 struct _Diff<_A2, _PtrT, __void_t<typename _A2::difference_type>>
140 { using type = typename _A2::difference_type; };
141
142 // Select _A2::size_type or make_unsigned<_DiffT>::type
143 template<typename _A2, typename _DiffT, typename = void>
144 struct _Size : make_unsigned<_DiffT> { };
145
146 template<typename _A2, typename _DiffT>
147 struct _Size<_A2, _DiffT, __void_t<typename _A2::size_type>>
148 { using type = typename _A2::size_type; };
149
150 public:
151 /**
152 * @brief The allocator's const pointer type.
153 *
154 * @c Alloc::const_pointer if that type exists, otherwise
155 * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
156 */
157 using const_pointer = typename _Ptr<__c_pointer, const value_type>::type;
158
159 /**
160 * @brief The allocator's void pointer type.
161 *
162 * @c Alloc::void_pointer if that type exists, otherwise
163 * <tt> pointer_traits<pointer>::rebind<void> </tt>
164 */
165 using void_pointer = typename _Ptr<__v_pointer, void>::type;
166
167 /**
168 * @brief The allocator's const void pointer type.
169 *
170 * @c Alloc::const_void_pointer if that type exists, otherwise
171 * <tt> pointer_traits<pointer>::rebind<const void> </tt>
172 */
173 using const_void_pointer = typename _Ptr<__cv_pointer, const void>::type;
174
175 /**
176 * @brief The allocator's difference type
177 *
178 * @c Alloc::difference_type if that type exists, otherwise
179 * <tt> pointer_traits<pointer>::difference_type </tt>
180 */
181 using difference_type = typename _Diff<_Alloc, pointer>::type;
182
183 /**
184 * @brief The allocator's size type
185 *
186 * @c Alloc::size_type if that type exists, otherwise
187 * <tt> make_unsigned<difference_type>::type </tt>
188 */
189 using size_type = typename _Size<_Alloc, difference_type>::type;
190
191 /**
192 * @brief How the allocator is propagated on copy assignment
193 *
194 * @c Alloc::propagate_on_container_copy_assignment if that type exists,
195 * otherwise @c false_type
196 */
197 using propagate_on_container_copy_assignment
198 = __detected_or_t<false_type, __pocca, _Alloc>;
199
200 /**
201 * @brief How the allocator is propagated on move assignment
202 *
203 * @c Alloc::propagate_on_container_move_assignment if that type exists,
204 * otherwise @c false_type
205 */
206 using propagate_on_container_move_assignment
207 = __detected_or_t<false_type, __pocma, _Alloc>;
208
209 /**
210 * @brief How the allocator is propagated on swap
211 *
212 * @c Alloc::propagate_on_container_swap if that type exists,
213 * otherwise @c false_type
214 */
215 using propagate_on_container_swap
216 = __detected_or_t<false_type, __pocs, _Alloc>;
217
218 /**
219 * @brief Whether all instances of the allocator type compare equal.
220 *
221 * @c Alloc::is_always_equal if that type exists,
222 * otherwise @c is_empty<Alloc>::type
223 */
224 using is_always_equal
225 = typename __detected_or_t<is_empty<_Alloc>, __equal, _Alloc>::type;
226
227 template<typename _Tp>
228 using rebind_alloc = __alloc_rebind<_Alloc, _Tp>;
229 template<typename _Tp>
230 using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
231
232 private:
233 template<typename _Alloc2>
234 static constexpr auto
235 _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int)
236 -> decltype(__a.allocate(__n, __hint))
237 { return __a.allocate(__n, __hint); }
238
239 template<typename _Alloc2>
240 static constexpr pointer
241 _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...)
242 { return __a.allocate(__n); }
243
244 template<typename _Tp, typename... _Args>
245 struct __construct_helper
246 {
247 template<typename _Alloc2,
248 typename = decltype(std::declval<_Alloc2*>()->construct(
249 std::declval<_Tp*>(), std::declval<_Args>()...))>
250 static true_type __test(int);
251
252 template<typename>
253 static false_type __test(...);
254
255 using type = decltype(__test<_Alloc>(0));
256 };
257
258 template<typename _Tp, typename... _Args>
259 using __has_construct
260 = typename __construct_helper<_Tp, _Args...>::type;
261
262 template<typename _Tp, typename... _Args>
263 static _GLIBCXX14_CONSTEXPR _Require<__has_construct<_Tp, _Args...>>
264 _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
265 noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...)))
266 { __a.construct(__p, std::forward<_Args>(__args)...); }
267
268 template<typename _Tp, typename... _Args>
269 static _GLIBCXX14_CONSTEXPR
270 _Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
271 is_constructible<_Tp, _Args...>>>
272 _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
273 noexcept(std::is_nothrow_constructible<_Tp, _Args...>::value)
274 {
275 #if __cplusplus <= 201703L
276 ::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
277 #else
278 std::construct_at(__p, std::forward<_Args>(__args)...);
279 #endif
280 }
281
282 template<typename _Alloc2, typename _Tp>
283 static _GLIBCXX14_CONSTEXPR auto
284 _S_destroy(_Alloc2& __a, _Tp* __p, int)
285 noexcept(noexcept(__a.destroy(__p)))
286 -> decltype(__a.destroy(__p))
287 { __a.destroy(__p); }
288
289 template<typename _Alloc2, typename _Tp>
290 static _GLIBCXX14_CONSTEXPR void
291 _S_destroy(_Alloc2&, _Tp* __p, ...)
292 noexcept(std::is_nothrow_destructible<_Tp>::value)
293 { std::_Destroy(__p); }
294
295 template<typename _Alloc2>
296 static constexpr auto
297 _S_max_size(_Alloc2& __a, int)
298 -> decltype(__a.max_size())
299 { return __a.max_size(); }
300
301 template<typename _Alloc2>
302 static constexpr size_type
303 _S_max_size(_Alloc2&, ...)
304 {
305 // _GLIBCXX_RESOLVE_LIB_DEFECTS
306 // 2466. allocator_traits::max_size() default behavior is incorrect
307 return __gnu_cxx::__numeric_traits<size_type>::__max
308 / sizeof(value_type);
309 }
310
311 template<typename _Alloc2>
312 static constexpr auto
313 _S_select(_Alloc2& __a, int)
314 -> decltype(__a.select_on_container_copy_construction())
315 { return __a.select_on_container_copy_construction(); }
316
317 template<typename _Alloc2>
318 static constexpr _Alloc2
319 _S_select(_Alloc2& __a, ...)
320 { return __a; }
321
322 public:
323
324 /**
325 * @brief Allocate memory.
326 * @param __a An allocator.
327 * @param __n The number of objects to allocate space for.
328 *
329 * Calls @c a.allocate(n)
330 */
331 _GLIBCXX_NODISCARD static _GLIBCXX20_CONSTEXPR pointer
332 allocate(_Alloc& __a, size_type __n)
333 { return __a.allocate(__n); }
334
335 /**
336 * @brief Allocate memory.
337 * @param __a An allocator.
338 * @param __n The number of objects to allocate space for.
339 * @param __hint Aid to locality.
340 * @return Memory of suitable size and alignment for @a n objects
341 * of type @c value_type
342 *
343 * Returns <tt> a.allocate(n, hint) </tt> if that expression is
344 * well-formed, otherwise returns @c a.allocate(n)
345 */
346 _GLIBCXX_NODISCARD static _GLIBCXX20_CONSTEXPR pointer
347 allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
348 { return _S_allocate(__a, __n, __hint, 0); }
349
350 /**
351 * @brief Deallocate memory.
352 * @param __a An allocator.
353 * @param __p Pointer to the memory to deallocate.
354 * @param __n The number of objects space was allocated for.
355 *
356 * Calls <tt> a.deallocate(p, n) </tt>
357 */
358 static _GLIBCXX20_CONSTEXPR void
359 deallocate(_Alloc& __a, pointer __p, size_type __n)
360 { __a.deallocate(__p, __n); }
361
362 /**
363 * @brief Construct an object of type `_Tp`
364 * @param __a An allocator.
365 * @param __p Pointer to memory of suitable size and alignment for Tp
366 * @param __args Constructor arguments.
367 *
368 * Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
369 * if that expression is well-formed, otherwise uses placement-new
370 * to construct an object of type @a _Tp at location @a __p from the
371 * arguments @a __args...
372 */
373 template<typename _Tp, typename... _Args>
374 static _GLIBCXX20_CONSTEXPR auto
375 construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
376 noexcept(noexcept(_S_construct(__a, __p,
377 std::forward<_Args>(__args)...)))
378 -> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
379 { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
380
381 /**
382 * @brief Destroy an object of type @a _Tp
383 * @param __a An allocator.
384 * @param __p Pointer to the object to destroy
385 *
386 * Calls @c __a.destroy(__p) if that expression is well-formed,
387 * otherwise calls @c __p->~_Tp()
388 */
389 template<typename _Tp>
390 static _GLIBCXX20_CONSTEXPR void
391 destroy(_Alloc& __a, _Tp* __p)
392 noexcept(noexcept(_S_destroy(__a, __p, 0)))
393 { _S_destroy(__a, __p, 0); }
394
395 /**
396 * @brief The maximum supported allocation size
397 * @param __a An allocator.
398 * @return @c __a.max_size() or @c numeric_limits<size_type>::max()
399 *
400 * Returns @c __a.max_size() if that expression is well-formed,
401 * otherwise returns @c numeric_limits<size_type>::max()
402 */
403 static _GLIBCXX20_CONSTEXPR size_type
404 max_size(const _Alloc& __a) noexcept
405 { return _S_max_size(__a, 0); }
406
407 /**
408 * @brief Obtain an allocator to use when copying a container.
409 * @param __rhs An allocator.
410 * @return @c __rhs.select_on_container_copy_construction() or @a __rhs
411 *
412 * Returns @c __rhs.select_on_container_copy_construction() if that
413 * expression is well-formed, otherwise returns @a __rhs
414 */
415 static _GLIBCXX20_CONSTEXPR _Alloc
416 select_on_container_copy_construction(const _Alloc& __rhs)
417 { return _S_select(__rhs, 0); }
418 };
419
420 #if _GLIBCXX_HOSTED
421
422 #if __cplusplus > 201703L
423 # define __cpp_lib_constexpr_dynamic_alloc 201907L
424 #endif
425
426 /// Partial specialization for std::allocator.
427 template<typename _Tp>
428 struct allocator_traits<allocator<_Tp>>
429 {
430 /// The allocator type
431 using allocator_type = allocator<_Tp>;
432
433 /// The allocated type
434 using value_type = _Tp;
435
436 /// The allocator's pointer type.
437 using pointer = _Tp*;
438
439 /// The allocator's const pointer type.
440 using const_pointer = const _Tp*;
441
442 /// The allocator's void pointer type.
443 using void_pointer = void*;
444
445 /// The allocator's const void pointer type.
446 using const_void_pointer = const void*;
447
448 /// The allocator's difference type
449 using difference_type = std::ptrdiff_t;
450
451 /// The allocator's size type
452 using size_type = std::size_t;
453
454 /// How the allocator is propagated on copy assignment
455 using propagate_on_container_copy_assignment = false_type;
456
457 /// How the allocator is propagated on move assignment
458 using propagate_on_container_move_assignment = true_type;
459
460 /// How the allocator is propagated on swap
461 using propagate_on_container_swap = false_type;
462
463 /// Whether all instances of the allocator type compare equal.
464 using is_always_equal = true_type;
465
466 template<typename _Up>
467 using rebind_alloc = allocator<_Up>;
468
469 template<typename _Up>
470 using rebind_traits = allocator_traits<allocator<_Up>>;
471
472 /**
473 * @brief Allocate memory.
474 * @param __a An allocator.
475 * @param __n The number of objects to allocate space for.
476 *
477 * Calls @c a.allocate(n)
478 */
479 [[__nodiscard__,__gnu__::__always_inline__]]
480 static _GLIBCXX20_CONSTEXPR pointer
481 allocate(allocator_type& __a, size_type __n)
482 { return __a.allocate(__n); }
483
484 /**
485 * @brief Allocate memory.
486 * @param __a An allocator.
487 * @param __n The number of objects to allocate space for.
488 * @param __hint Aid to locality.
489 * @return Memory of suitable size and alignment for @a n objects
490 * of type @c value_type
491 *
492 * Returns <tt> a.allocate(n, hint) </tt>
493 */
494 [[__nodiscard__,__gnu__::__always_inline__]]
495 static _GLIBCXX20_CONSTEXPR pointer
496 allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)
497 {
498 #if __cplusplus <= 201703L
499 return __a.allocate(__n, __hint);
500 #else
501 return __a.allocate(__n);
502 #endif
503 }
504
505 /**
506 * @brief Deallocate memory.
507 * @param __a An allocator.
508 * @param __p Pointer to the memory to deallocate.
509 * @param __n The number of objects space was allocated for.
510 *
511 * Calls <tt> a.deallocate(p, n) </tt>
512 */
513 [[__gnu__::__always_inline__]]
514 static _GLIBCXX20_CONSTEXPR void
515 deallocate(allocator_type& __a, pointer __p, size_type __n)
516 { __a.deallocate(__p, __n); }
517
518 /**
519 * @brief Construct an object of type `_Up`
520 * @param __a An allocator.
521 * @param __p Pointer to memory of suitable size and alignment for
522 * an object of type `_Up`.
523 * @param __args Constructor arguments.
524 *
525 * Calls `__a.construct(__p, std::forward<_Args>(__args)...)`
526 * in C++11, C++14 and C++17. Changed in C++20 to call
527 * `std::construct_at(__p, std::forward<_Args>(__args)...)` instead.
528 */
529 template<typename _Up, typename... _Args>
530 [[__gnu__::__always_inline__]]
531 static _GLIBCXX20_CONSTEXPR void
532 construct(allocator_type& __a __attribute__((__unused__)), _Up* __p,
533 _Args&&... __args)
534 noexcept(std::is_nothrow_constructible<_Up, _Args...>::value)
535 {
536 #if __cplusplus <= 201703L
537 __a.construct(__p, std::forward<_Args>(__args)...);
538 #else
539 std::construct_at(__p, std::forward<_Args>(__args)...);
540 #endif
541 }
542
543 /**
544 * @brief Destroy an object of type @a _Up
545 * @param __a An allocator.
546 * @param __p Pointer to the object to destroy
547 *
548 * Calls @c __a.destroy(__p).
549 */
550 template<typename _Up>
551 [[__gnu__::__always_inline__]]
552 static _GLIBCXX20_CONSTEXPR void
553 destroy(allocator_type& __a __attribute__((__unused__)), _Up* __p)
554 noexcept(is_nothrow_destructible<_Up>::value)
555 {
556 #if __cplusplus <= 201703L
557 __a.destroy(__p);
558 #else
559 std::destroy_at(__p);
560 #endif
561 }
562
563 /**
564 * @brief The maximum supported allocation size
565 * @param __a An allocator.
566 * @return @c __a.max_size()
567 */
568 [[__gnu__::__always_inline__]]
569 static _GLIBCXX20_CONSTEXPR size_type
570 max_size(const allocator_type& __a __attribute__((__unused__))) noexcept
571 {
572 #if __cplusplus <= 201703L
573 return __a.max_size();
574 #else
575 return size_t(-1) / sizeof(value_type);
576 #endif
577 }
578
579 /**
580 * @brief Obtain an allocator to use when copying a container.
581 * @param __rhs An allocator.
582 * @return @c __rhs
583 */
584 [[__gnu__::__always_inline__]]
585 static _GLIBCXX20_CONSTEXPR allocator_type
586 select_on_container_copy_construction(const allocator_type& __rhs)
587 { return __rhs; }
588 };
589
590 /// Explicit specialization for std::allocator<void>.
591 template<>
592 struct allocator_traits<allocator<void>>
593 {
594 /// The allocator type
595 using allocator_type = allocator<void>;
596
597 /// The allocated type
598 using value_type = void;
599
600 /// The allocator's pointer type.
601 using pointer = void*;
602
603 /// The allocator's const pointer type.
604 using const_pointer = const void*;
605
606 /// The allocator's void pointer type.
607 using void_pointer = void*;
608
609 /// The allocator's const void pointer type.
610 using const_void_pointer = const void*;
611
612 /// The allocator's difference type
613 using difference_type = std::ptrdiff_t;
614
615 /// The allocator's size type
616 using size_type = std::size_t;
617
618 /// How the allocator is propagated on copy assignment
619 using propagate_on_container_copy_assignment = false_type;
620
621 /// How the allocator is propagated on move assignment
622 using propagate_on_container_move_assignment = true_type;
623
624 /// How the allocator is propagated on swap
625 using propagate_on_container_swap = false_type;
626
627 /// Whether all instances of the allocator type compare equal.
628 using is_always_equal = true_type;
629
630 template<typename _Up>
631 using rebind_alloc = allocator<_Up>;
632
633 template<typename _Up>
634 using rebind_traits = allocator_traits<allocator<_Up>>;
635
636 /// allocate is ill-formed for allocator<void>
637 static void*
638 allocate(allocator_type&, size_type, const void* = nullptr) = delete;
639
640 /// deallocate is ill-formed for allocator<void>
641 static void
642 deallocate(allocator_type&, void*, size_type) = delete;
643
644 /**
645 * @brief Construct an object of type `_Up`
646 * @param __a An allocator.
647 * @param __p Pointer to memory of suitable size and alignment for
648 * an object of type `_Up`.
649 * @param __args Constructor arguments.
650 *
651 * Calls `__a.construct(__p, std::forward<_Args>(__args)...)`
652 * in C++11, C++14 and C++17. Changed in C++20 to call
653 * `std::construct_at(__p, std::forward<_Args>(__args)...)` instead.
654 */
655 template<typename _Up, typename... _Args>
656 [[__gnu__::__always_inline__]]
657 static _GLIBCXX20_CONSTEXPR void
658 construct(allocator_type&, _Up* __p, _Args&&... __args)
659 noexcept(std::is_nothrow_constructible<_Up, _Args...>::value)
660 { std::_Construct(__p, std::forward<_Args>(__args)...); }
661
662 /**
663 * @brief Destroy an object of type `_Up`
664 * @param __a An allocator.
665 * @param __p Pointer to the object to destroy
666 *
667 * Invokes the destructor for `*__p`.
668 */
669 template<typename _Up>
670 [[__gnu__::__always_inline__]]
671 static _GLIBCXX20_CONSTEXPR void
672 destroy(allocator_type&, _Up* __p)
673 noexcept(is_nothrow_destructible<_Up>::value)
674 { std::_Destroy(__p); }
675
676 /// max_size is ill-formed for allocator<void>
677 static size_type
678 max_size(const allocator_type&) = delete;
679
680 /**
681 * @brief Obtain an allocator to use when copying a container.
682 * @param __rhs An allocator.
683 * @return `__rhs`
684 */
685 [[__gnu__::__always_inline__]]
686 static _GLIBCXX20_CONSTEXPR allocator_type
687 select_on_container_copy_construction(const allocator_type& __rhs)
688 { return __rhs; }
689 };
690 #endif
691
692 /// @cond undocumented
693 #if __cplusplus < 201703L
694 template<typename _Alloc>
695 [[__gnu__::__always_inline__]]
696 inline void
697 __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
698 { __one = __two; }
699
700 template<typename _Alloc>
701 [[__gnu__::__always_inline__]]
702 inline void
703 __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
704 { }
705 #endif
706
707 template<typename _Alloc>
708 [[__gnu__::__always_inline__]]
709 _GLIBCXX14_CONSTEXPR inline void
710 __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
711 {
712 using __traits = allocator_traits<_Alloc>;
713 using __pocca =
714 typename __traits::propagate_on_container_copy_assignment::type;
715 #if __cplusplus >= 201703L
716 if constexpr (__pocca::value)
717 __one = __two;
718 #else
719 __do_alloc_on_copy(__one, __two, __pocca());
720 #endif
721 }
722
723 template<typename _Alloc>
724 [[__gnu__::__always_inline__]]
725 constexpr _Alloc
726 __alloc_on_copy(const _Alloc& __a)
727 {
728 typedef allocator_traits<_Alloc> __traits;
729 return __traits::select_on_container_copy_construction(__a);
730 }
731
732 #if __cplusplus < 201703L
733 template<typename _Alloc>
734 [[__gnu__::__always_inline__]]
735 inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
736 { __one = std::move(__two); }
737
738 template<typename _Alloc>
739 [[__gnu__::__always_inline__]]
740 inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
741 { }
742 #endif
743
744 template<typename _Alloc>
745 [[__gnu__::__always_inline__]]
746 _GLIBCXX14_CONSTEXPR inline void
747 __alloc_on_move(_Alloc& __one, _Alloc& __two)
748 {
749 using __traits = allocator_traits<_Alloc>;
750 using __pocma
751 = typename __traits::propagate_on_container_move_assignment::type;
752 #if __cplusplus >= 201703L
753 if constexpr (__pocma::value)
754 __one = std::move(__two);
755 #else
756 __do_alloc_on_move(__one, __two, __pocma());
757 #endif
758 }
759
760 #if __cplusplus < 201703L
761 template<typename _Alloc>
762 [[__gnu__::__always_inline__]]
763 inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
764 {
765 using std::swap;
766 swap(__one, __two);
767 }
768
769 template<typename _Alloc>
770 [[__gnu__::__always_inline__]]
771 inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
772 { }
773 #endif
774
775 template<typename _Alloc>
776 [[__gnu__::__always_inline__]]
777 _GLIBCXX14_CONSTEXPR inline void
778 __alloc_on_swap(_Alloc& __one, _Alloc& __two)
779 {
780 using __traits = allocator_traits<_Alloc>;
781 using __pocs = typename __traits::propagate_on_container_swap::type;
782 #if __cplusplus >= 201703L
783 if constexpr (__pocs::value)
784 {
785 using std::swap;
786 swap(__one, __two);
787 }
788 #else
789 __do_alloc_on_swap(__one, __two, __pocs());
790 #endif
791 }
792
793 template<typename _Alloc, typename _Tp,
794 typename _ValueT = __remove_cvref_t<typename _Alloc::value_type>,
795 typename = void>
796 struct __is_alloc_insertable_impl
797 : false_type
798 { };
799
800 template<typename _Alloc, typename _Tp, typename _ValueT>
801 struct __is_alloc_insertable_impl<_Alloc, _Tp, _ValueT,
802 __void_t<decltype(allocator_traits<_Alloc>::construct(
803 std::declval<_Alloc&>(), std::declval<_ValueT*>(),
804 std::declval<_Tp>()))>>
805 : true_type
806 { };
807
808 // true if _Alloc::value_type is CopyInsertable into containers using _Alloc
809 // (might be wrong if _Alloc::construct exists but is not constrained,
810 // i.e. actually trying to use it would still be invalid. Use with caution.)
811 template<typename _Alloc>
812 struct __is_copy_insertable
813 : __is_alloc_insertable_impl<_Alloc,
814 typename _Alloc::value_type const&>::type
815 { };
816
817 #if _GLIBCXX_HOSTED
818 // std::allocator<_Tp> just requires CopyConstructible
819 template<typename _Tp>
820 struct __is_copy_insertable<allocator<_Tp>>
821 : is_copy_constructible<_Tp>
822 { };
823 #endif
824
825 // true if _Alloc::value_type is MoveInsertable into containers using _Alloc
826 // (might be wrong if _Alloc::construct exists but is not constrained,
827 // i.e. actually trying to use it would still be invalid. Use with caution.)
828 template<typename _Alloc>
829 struct __is_move_insertable
830 : __is_alloc_insertable_impl<_Alloc, typename _Alloc::value_type>::type
831 { };
832
833 #if _GLIBCXX_HOSTED
834 // std::allocator<_Tp> just requires MoveConstructible
835 template<typename _Tp>
836 struct __is_move_insertable<allocator<_Tp>>
837 : is_move_constructible<_Tp>
838 { };
839 #endif
840
841 // Trait to detect Allocator-like types.
842 template<typename _Alloc, typename = void>
843 struct __is_allocator : false_type { };
844
845 template<typename _Alloc>
846 struct __is_allocator<_Alloc,
847 __void_t<typename _Alloc::value_type,
848 decltype(std::declval<_Alloc&>().allocate(size_t{}))>>
849 : true_type { };
850
851 template<typename _Alloc>
852 using _RequireAllocator
853 = typename enable_if<__is_allocator<_Alloc>::value, _Alloc>::type;
854
855 template<typename _Alloc>
856 using _RequireNotAllocator
857 = typename enable_if<!__is_allocator<_Alloc>::value, _Alloc>::type;
858
859 #if __cpp_concepts >= 201907L
860 template<typename _Alloc>
861 concept __allocator_like = requires (_Alloc& __a) {
862 typename _Alloc::value_type;
863 __a.deallocate(__a.allocate(1u), 1u);
864 };
865 #endif
866 /// @endcond
867 #endif // C++11
868
869 /// @cond undocumented
870
871 // To implement Option 3 of DR 431.
872 template<typename _Alloc, bool = __is_empty(_Alloc)>
873 struct __alloc_swap
874 { static void _S_do_it(_Alloc&, _Alloc&) _GLIBCXX_NOEXCEPT { } };
875
876 template<typename _Alloc>
877 struct __alloc_swap<_Alloc, false>
878 {
879 static void
880 _S_do_it(_Alloc& __one, _Alloc& __two) _GLIBCXX_NOEXCEPT
881 {
882 // Precondition: swappable allocators.
883 if (__one != __two)
884 swap(__one, __two);
885 }
886 };
887
888 #if __cplusplus >= 201103L
889 template<typename _Tp, bool
890 = __or_<is_copy_constructible<typename _Tp::value_type>,
891 is_nothrow_move_constructible<typename _Tp::value_type>>::value>
892 struct __shrink_to_fit_aux
893 { static bool _S_do_it(_Tp&) noexcept { return false; } };
894
895 template<typename _Tp>
896 struct __shrink_to_fit_aux<_Tp, true>
897 {
898 _GLIBCXX20_CONSTEXPR
899 static bool
900 _S_do_it(_Tp& __c) noexcept
901 {
902 #if __cpp_exceptions
903 try
904 {
905 _Tp(__make_move_if_noexcept_iterator(__c.begin()),
906 __make_move_if_noexcept_iterator(__c.end()),
907 __c.get_allocator()).swap(__c);
908 return true;
909 }
910 catch(...)
911 { return false; }
912 #else
913 return false;
914 #endif
915 }
916 };
917 #endif
918
919 /**
920 * Destroy a range of objects using the supplied allocator. For
921 * non-default allocators we do not optimize away invocation of
922 * destroy() even if _Tp has a trivial destructor.
923 */
924
925 template<typename _ForwardIterator, typename _Allocator>
926 _GLIBCXX20_CONSTEXPR
927 void
928 _Destroy(_ForwardIterator __first, _ForwardIterator __last,
929 _Allocator& __alloc)
930 {
931 for (; __first != __last; ++__first)
932 #if __cplusplus < 201103L
933 __alloc.destroy(std::__addressof(*__first));
934 #else
935 allocator_traits<_Allocator>::destroy(__alloc,
936 std::__addressof(*__first));
937 #endif
938 }
939
940 #if _GLIBCXX_HOSTED
941 template<typename _ForwardIterator, typename _Tp>
942 __attribute__((__always_inline__)) _GLIBCXX20_CONSTEXPR
943 inline void
944 _Destroy(_ForwardIterator __first, _ForwardIterator __last,
945 allocator<_Tp>&)
946 {
947 std::_Destroy(__first, __last);
948 }
949 #endif
950 /// @endcond
951
952 _GLIBCXX_END_NAMESPACE_VERSION
953 } // namespace std
954 #endif // _ALLOC_TRAITS_H