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