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