libstdc++-v3/include/bits/alloc_traits.h

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