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

   1 // Allocator traits -*- C++ -*-
   2
   3 // Copyright (C) 2011-2018 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 #if __cplusplus >= 201103L
  34
  35 #include <bits/memoryfwd.h>
  36 #include <bits/ptr_traits.h>
  37 #include <ext/numeric_traits.h>
  38
  39 #define __cpp_lib_allocator_traits_is_always_equal 201411
  40
  41 namespace std _GLIBCXX_VISIBILITY(default)
  42 {
  43 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  44
  45   struct __allocator_traits_base
  46   {
  47     template<typename _Tp, typename _Up, typename = void>
  48       struct __rebind : __replace_first_arg<_Tp, _Up> { };
  49
  50     template<typename _Tp, typename _Up>
  51       struct __rebind<_Tp, _Up,
  52                       __void_t<typename _Tp::template rebind<_Up>::other>>
  53       { using type = typename _Tp::template rebind<_Up>::other; };
  54
  55   protected:
  56     template<typename _Tp>
  57       using __pointer = typename _Tp::pointer;
  58     template<typename _Tp>
  59       using __c_pointer = typename _Tp::const_pointer;
  60     template<typename _Tp>
  61       using __v_pointer = typename _Tp::void_pointer;
  62     template<typename _Tp>
  63       using __cv_pointer = typename _Tp::const_void_pointer;
  64     template<typename _Tp>
  65       using __pocca = typename _Tp::propagate_on_container_copy_assignment;
  66     template<typename _Tp>
  67       using __pocma = typename _Tp::propagate_on_container_move_assignment;
  68     template<typename _Tp>
  69       using __pocs = typename _Tp::propagate_on_container_swap;
  70     template<typename _Tp>
  71       using __equal = typename _Tp::is_always_equal;
  72   };
  73
  74   template<typename _Alloc, typename _Up>
  75     using __alloc_rebind
  76       = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;
  77
  78   /**
  79    * @brief  Uniform interface to all allocator types.
  80    * @ingroup allocators
  81   */
  82   template<typename _Alloc>
  83     struct allocator_traits : __allocator_traits_base
  84     {
  85       /// The allocator type
  86       typedef _Alloc allocator_type;
  87       /// The allocated type
  88       typedef typename _Alloc::value_type value_type;
  89
  90       /**
  91        * @brief   The allocator's pointer type.
  92        *
  93        * @c Alloc::pointer if that type exists, otherwise @c value_type*
  94       */
  95       using pointer = __detected_or_t<value_type*, __pointer, _Alloc>;
  96
  97     private:
  98       // Select _Func<_Alloc> or pointer_traits<pointer>::rebind<_Tp>
  99       template<template<typename> class _Func, typename _Tp, typename = void>
 100         struct _Ptr
 101         {
 102           using type = typename pointer_traits<pointer>::template rebind<_Tp>;
 103         };
 104
 105       template<template<typename> class _Func, typename _Tp>
 106         struct _Ptr<_Func, _Tp, __void_t<_Func<_Alloc>>>
 107         {
 108           using type = _Func<_Alloc>;
 109         };
 110
 111       // Select _A2::difference_type or pointer_traits<_Ptr>::difference_type
 112       template<typename _A2, typename _PtrT, typename = void>
 113         struct _Diff
 114         { using type = typename pointer_traits<_PtrT>::difference_type; };
 115
 116       template<typename _A2, typename _PtrT>
 117         struct _Diff<_A2, _PtrT, __void_t<typename _A2::difference_type>>
 118         { using type = typename _A2::difference_type; };
 119
 120       // Select _A2::size_type or make_unsigned<_DiffT>::type
 121       template<typename _A2, typename _DiffT, typename = void>
 122         struct _Size : make_unsigned<_DiffT> { };
 123
 124       template<typename _A2, typename _DiffT>
 125         struct _Size<_A2, _DiffT, __void_t<typename _A2::size_type>>
 126         { using type = typename _A2::size_type; };
 127
 128     public:
 129       /**
 130        * @brief   The allocator's const pointer type.
 131        *
 132        * @c Alloc::const_pointer if that type exists, otherwise
 133        * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
 134       */
 135       using const_pointer = typename _Ptr<__c_pointer, const value_type>::type;
 136
 137       /**
 138        * @brief   The allocator's void pointer type.
 139        *
 140        * @c Alloc::void_pointer if that type exists, otherwise
 141        * <tt> pointer_traits<pointer>::rebind<void> </tt>
 142       */
 143       using void_pointer = typename _Ptr<__v_pointer, void>::type;
 144
 145       /**
 146        * @brief   The allocator's const void pointer type.
 147        *
 148        * @c Alloc::const_void_pointer if that type exists, otherwise
 149        * <tt> pointer_traits<pointer>::rebind<const void> </tt>
 150       */
 151       using const_void_pointer = typename _Ptr<__cv_pointer, const void>::type;
 152
 153       /**
 154        * @brief   The allocator's difference type
 155        *
 156        * @c Alloc::difference_type if that type exists, otherwise
 157        * <tt> pointer_traits<pointer>::difference_type </tt>
 158       */
 159       using difference_type = typename _Diff<_Alloc, pointer>::type;
 160
 161       /**
 162        * @brief   The allocator's size type
 163        *
 164        * @c Alloc::size_type if that type exists, otherwise
 165        * <tt> make_unsigned<difference_type>::type </tt>
 166       */
 167       using size_type = typename _Size<_Alloc, difference_type>::type;
 168
 169       /**
 170        * @brief   How the allocator is propagated on copy assignment
 171        *
 172        * @c Alloc::propagate_on_container_copy_assignment if that type exists,
 173        * otherwise @c false_type
 174       */
 175       using propagate_on_container_copy_assignment
 176         = __detected_or_t<false_type, __pocca, _Alloc>;
 177
 178       /**
 179        * @brief   How the allocator is propagated on move assignment
 180        *
 181        * @c Alloc::propagate_on_container_move_assignment if that type exists,
 182        * otherwise @c false_type
 183       */
 184       using propagate_on_container_move_assignment
 185         = __detected_or_t<false_type, __pocma, _Alloc>;
 186
 187       /**
 188        * @brief   How the allocator is propagated on swap
 189        *
 190        * @c Alloc::propagate_on_container_swap if that type exists,
 191        * otherwise @c false_type
 192       */
 193       using propagate_on_container_swap
 194         = __detected_or_t<false_type, __pocs, _Alloc>;
 195
 196       /**
 197        * @brief   Whether all instances of the allocator type compare equal.
 198        *
 199        * @c Alloc::is_always_equal if that type exists,
 200        * otherwise @c is_empty<Alloc>::type
 201       */
 202       using is_always_equal
 203         = __detected_or_t<typename is_empty<_Alloc>::type, __equal, _Alloc>;
 204
 205       template<typename _Tp>
 206         using rebind_alloc = __alloc_rebind<_Alloc, _Tp>;
 207       template<typename _Tp>
 208         using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
 209
 210     private:
 211       template<typename _Alloc2>
 212         static auto
 213         _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int)
 214         -> decltype(__a.allocate(__n, __hint))
 215         { return __a.allocate(__n, __hint); }
 216
 217       template<typename _Alloc2>
 218         static pointer
 219         _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...)
 220         { return __a.allocate(__n); }
 221
 222       template<typename _Tp, typename... _Args>
 223         struct __construct_helper
 224         {
 225           template<typename _Alloc2,
 226             typename = decltype(std::declval<_Alloc2*>()->construct(
 227                   std::declval<_Tp*>(), std::declval<_Args>()...))>
 228             static true_type __test(int);
 229
 230           template<typename>
 231             static false_type __test(...);
 232
 233           using type = decltype(__test<_Alloc>(0));
 234         };
 235
 236       template<typename _Tp, typename... _Args>
 237         using __has_construct
 238           = typename __construct_helper<_Tp, _Args...>::type;
 239
 240       template<typename _Tp, typename... _Args>
 241         static _Require<__has_construct<_Tp, _Args...>>
 242         _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
 243         { __a.construct(__p, std::forward<_Args>(__args)...); }
 244
 245       template<typename _Tp, typename... _Args>
 246         static
 247         _Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
 248                                is_constructible<_Tp, _Args...>>>
 249         _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
 250         { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
 251
 252       template<typename _Alloc2, typename _Tp>
 253         static auto
 254         _S_destroy(_Alloc2& __a, _Tp* __p, int)
 255         -> decltype(__a.destroy(__p))
 256         { __a.destroy(__p); }
 257
 258       template<typename _Alloc2, typename _Tp>
 259         static void
 260         _S_destroy(_Alloc2&, _Tp* __p, ...)
 261         { __p->~_Tp(); }
 262
 263       template<typename _Alloc2>
 264         static auto
 265         _S_max_size(_Alloc2& __a, int)
 266         -> decltype(__a.max_size())
 267         { return __a.max_size(); }
 268
 269       template<typename _Alloc2>
 270         static size_type
 271         _S_max_size(_Alloc2&, ...)
 272         {
 273           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 274           // 2466. allocator_traits::max_size() default behavior is incorrect
 275           return __gnu_cxx::__numeric_traits<size_type>::__max
 276             / sizeof(value_type);
 277         }
 278
 279       template<typename _Alloc2>
 280         static auto
 281         _S_select(_Alloc2& __a, int)
 282         -> decltype(__a.select_on_container_copy_construction())
 283         { return __a.select_on_container_copy_construction(); }
 284
 285       template<typename _Alloc2>
 286         static _Alloc2
 287         _S_select(_Alloc2& __a, ...)
 288         { return __a; }
 289
 290     public:
 291
 292       /**
 293        *  @brief  Allocate memory.
 294        *  @param  __a  An allocator.
 295        *  @param  __n  The number of objects to allocate space for.
 296        *
 297        *  Calls @c a.allocate(n)
 298       */
 299       static pointer
 300       allocate(_Alloc& __a, size_type __n)
 301       { return __a.allocate(__n); }
 302
 303       /**
 304        *  @brief  Allocate memory.
 305        *  @param  __a  An allocator.
 306        *  @param  __n  The number of objects to allocate space for.
 307        *  @param  __hint Aid to locality.
 308        *  @return Memory of suitable size and alignment for @a n objects
 309        *          of type @c value_type
 310        *
 311        *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
 312        *  well-formed, otherwise returns @c a.allocate(n)
 313       */
 314       static pointer
 315       allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
 316       { return _S_allocate(__a, __n, __hint, 0); }
 317
 318       /**
 319        *  @brief  Deallocate memory.
 320        *  @param  __a  An allocator.
 321        *  @param  __p  Pointer to the memory to deallocate.
 322        *  @param  __n  The number of objects space was allocated for.
 323        *
 324        *  Calls <tt> a.deallocate(p, n) </tt>
 325       */
 326       static void
 327       deallocate(_Alloc& __a, pointer __p, size_type __n)
 328       { __a.deallocate(__p, __n); }
 329
 330       /**
 331        *  @brief  Construct an object of type @a _Tp
 332        *  @param  __a  An allocator.
 333        *  @param  __p  Pointer to memory of suitable size and alignment for Tp
 334        *  @param  __args Constructor arguments.
 335        *
 336        *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
 337        *  if that expression is well-formed, otherwise uses placement-new
 338        *  to construct an object of type @a _Tp at location @a __p from the
 339        *  arguments @a __args...
 340       */
 341       template<typename _Tp, typename... _Args>
 342         static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
 343         -> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
 344         { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
 345
 346       /**
 347        *  @brief  Destroy an object of type @a _Tp
 348        *  @param  __a  An allocator.
 349        *  @param  __p  Pointer to the object to destroy
 350        *
 351        *  Calls @c __a.destroy(__p) if that expression is well-formed,
 352        *  otherwise calls @c __p->~_Tp()
 353       */
 354       template<typename _Tp>
 355         static void destroy(_Alloc& __a, _Tp* __p)
 356         { _S_destroy(__a, __p, 0); }
 357
 358       /**
 359        *  @brief  The maximum supported allocation size
 360        *  @param  __a  An allocator.
 361        *  @return @c __a.max_size() or @c numeric_limits<size_type>::max()
 362        *
 363        *  Returns @c __a.max_size() if that expression is well-formed,
 364        *  otherwise returns @c numeric_limits<size_type>::max()
 365       */
 366       static size_type max_size(const _Alloc& __a) noexcept
 367       { return _S_max_size(__a, 0); }
 368
 369       /**
 370        *  @brief  Obtain an allocator to use when copying a container.
 371        *  @param  __rhs  An allocator.
 372        *  @return @c __rhs.select_on_container_copy_construction() or @a __rhs
 373        *
 374        *  Returns @c __rhs.select_on_container_copy_construction() if that
 375        *  expression is well-formed, otherwise returns @a __rhs
 376       */
 377       static _Alloc
 378       select_on_container_copy_construction(const _Alloc& __rhs)
 379       { return _S_select(__rhs, 0); }
 380     };
 381
 382   /// Partial specialization for std::allocator.
 383   template<typename _Tp>
 384     struct allocator_traits<allocator<_Tp>>
 385     {
 386       /// The allocator type
 387       using allocator_type = allocator<_Tp>;
 388       /// The allocated type
 389       using value_type = _Tp;
 390
 391       /// The allocator's pointer type.
 392       using pointer = _Tp*;
 393
 394       /// The allocator's const pointer type.
 395       using const_pointer = const _Tp*;
 396
 397       /// The allocator's void pointer type.
 398       using void_pointer = void*;
 399
 400       /// The allocator's const void pointer type.
 401       using const_void_pointer = const void*;
 402
 403       /// The allocator's difference type
 404       using difference_type = std::ptrdiff_t;
 405
 406       /// The allocator's size type
 407       using size_type = std::size_t;
 408
 409       /// How the allocator is propagated on copy assignment
 410       using propagate_on_container_copy_assignment = false_type;
 411
 412       /// How the allocator is propagated on move assignment
 413       using propagate_on_container_move_assignment = true_type;
 414
 415       /// How the allocator is propagated on swap
 416       using propagate_on_container_swap = false_type;
 417
 418       /// Whether all instances of the allocator type compare equal.
 419       using is_always_equal = true_type;
 420
 421       template<typename _Up>
 422         using rebind_alloc = allocator<_Up>;
 423
 424       template<typename _Up>
 425         using rebind_traits = allocator_traits<allocator<_Up>>;
 426
 427       /**
 428        *  @brief  Allocate memory.
 429        *  @param  __a  An allocator.
 430        *  @param  __n  The number of objects to allocate space for.
 431        *
 432        *  Calls @c a.allocate(n)
 433       */
 434       static pointer
 435       allocate(allocator_type& __a, size_type __n)
 436       { return __a.allocate(__n); }
 437
 438       /**
 439        *  @brief  Allocate memory.
 440        *  @param  __a  An allocator.
 441        *  @param  __n  The number of objects to allocate space for.
 442        *  @param  __hint Aid to locality.
 443        *  @return Memory of suitable size and alignment for @a n objects
 444        *          of type @c value_type
 445        *
 446        *  Returns <tt> a.allocate(n, hint) </tt>
 447       */
 448       static pointer
 449       allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)
 450       { return __a.allocate(__n, __hint); }
 451
 452       /**
 453        *  @brief  Deallocate memory.
 454        *  @param  __a  An allocator.
 455        *  @param  __p  Pointer to the memory to deallocate.
 456        *  @param  __n  The number of objects space was allocated for.
 457        *
 458        *  Calls <tt> a.deallocate(p, n) </tt>
 459       */
 460       static void
 461       deallocate(allocator_type& __a, pointer __p, size_type __n)
 462       { __a.deallocate(__p, __n); }
 463
 464       /**
 465        *  @brief  Construct an object of type @a _Up
 466        *  @param  __a  An allocator.
 467        *  @param  __p  Pointer to memory of suitable size and alignment for Tp
 468        *  @param  __args Constructor arguments.
 469        *
 470        *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
 471       */
 472       template<typename _Up, typename... _Args>
 473         static void
 474         construct(allocator_type& __a, _Up* __p, _Args&&... __args)
 475         { __a.construct(__p, std::forward<_Args>(__args)...); }
 476
 477       /**
 478        *  @brief  Destroy an object of type @a _Up
 479        *  @param  __a  An allocator.
 480        *  @param  __p  Pointer to the object to destroy
 481        *
 482        *  Calls @c __a.destroy(__p).
 483       */
 484       template<typename _Up>
 485         static void
 486         destroy(allocator_type& __a, _Up* __p)
 487         { __a.destroy(__p); }
 488
 489       /**
 490        *  @brief  The maximum supported allocation size
 491        *  @param  __a  An allocator.
 492        *  @return @c __a.max_size()
 493       */
 494       static size_type
 495       max_size(const allocator_type& __a) noexcept
 496       { return __a.max_size(); }
 497
 498       /**
 499        *  @brief  Obtain an allocator to use when copying a container.
 500        *  @param  __rhs  An allocator.
 501        *  @return @c __rhs
 502       */
 503       static allocator_type
 504       select_on_container_copy_construction(const allocator_type& __rhs)
 505       { return __rhs; }
 506     };
 507
 508
 509   template<typename _Alloc>
 510     inline void
 511     __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
 512     { __one = __two; }
 513
 514   template<typename _Alloc>
 515     inline void
 516     __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
 517     { }
 518
 519   template<typename _Alloc>
 520     inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
 521     {
 522       typedef allocator_traits<_Alloc> __traits;
 523       typedef typename __traits::propagate_on_container_copy_assignment __pocca;
 524       __do_alloc_on_copy(__one, __two, __pocca());
 525     }
 526
 527   template<typename _Alloc>
 528     inline _Alloc __alloc_on_copy(const _Alloc& __a)
 529     {
 530       typedef allocator_traits<_Alloc> __traits;
 531       return __traits::select_on_container_copy_construction(__a);
 532     }
 533
 534   template<typename _Alloc>
 535     inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
 536     { __one = std::move(__two); }
 537
 538   template<typename _Alloc>
 539     inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
 540     { }
 541
 542   template<typename _Alloc>
 543     inline void __alloc_on_move(_Alloc& __one, _Alloc& __two)
 544     {
 545       typedef allocator_traits<_Alloc> __traits;
 546       typedef typename __traits::propagate_on_container_move_assignment __pocma;
 547       __do_alloc_on_move(__one, __two, __pocma());
 548     }
 549
 550   template<typename _Alloc>
 551     inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
 552     {
 553       using std::swap;
 554       swap(__one, __two);
 555     }
 556
 557   template<typename _Alloc>
 558     inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
 559     { }
 560
 561   template<typename _Alloc>
 562     inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two)
 563     {
 564       typedef allocator_traits<_Alloc> __traits;
 565       typedef typename __traits::propagate_on_container_swap __pocs;
 566       __do_alloc_on_swap(__one, __two, __pocs());
 567     }
 568
 569   template<typename _Alloc>
 570     class __is_copy_insertable_impl
 571     {
 572       typedef allocator_traits<_Alloc> _Traits;
 573
 574       template<typename _Up, typename
 575                = decltype(_Traits::construct(std::declval<_Alloc&>(),
 576                                              std::declval<_Up*>(),
 577                                              std::declval<const _Up&>()))>
 578         static true_type
 579         _M_select(int);
 580
 581       template<typename _Up>
 582         static false_type
 583         _M_select(...);
 584
 585     public:
 586       typedef decltype(_M_select<typename _Alloc::value_type>(0)) type;
 587     };
 588
 589   // true if _Alloc::value_type is CopyInsertable into containers using _Alloc
 590   template<typename _Alloc>
 591     struct __is_copy_insertable
 592     : __is_copy_insertable_impl<_Alloc>::type
 593     { };
 594
 595   // std::allocator<_Tp> just requires CopyConstructible
 596   template<typename _Tp>
 597     struct __is_copy_insertable<allocator<_Tp>>
 598     : is_copy_constructible<_Tp>
 599     { };
 600
 601 #if __cplusplus >= 201103L
 602   // Trait to detect Allocator-like types.
 603   template<typename _Alloc, typename = void>
 604     struct __is_allocator : false_type { };
 605
 606   template<typename _Alloc>
 607     struct __is_allocator<_Alloc,
 608       __void_t<typename _Alloc::value_type,
 609                decltype(std::declval<_Alloc&>().allocate(size_t{}))>>
 610     : true_type { };
 611
 612   template<typename _Alloc>
 613     using _RequireAllocator
 614       = typename enable_if<__is_allocator<_Alloc>::value, _Alloc>::type;
 615 #endif
 616
 617 _GLIBCXX_END_NAMESPACE_VERSION
 618 } // namespace std
 619
 620 #endif
 621 #endif