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