libstdc++
alloc_traits.h
Go to the documentation of this file.
00001 // Allocator traits -*- C++ -*-
00002 
00003 // Copyright (C) 2011-2014 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/alloc_traits.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{memory}
00028  */
00029 
00030 #ifndef _ALLOC_TRAITS_H
00031 #define _ALLOC_TRAITS_H 1
00032 
00033 #if __cplusplus >= 201103L
00034 
00035 #include <bits/memoryfwd.h>
00036 #include <bits/ptr_traits.h>
00037 #include <ext/numeric_traits.h>
00038 
00039 namespace std _GLIBCXX_VISIBILITY(default)
00040 {
00041 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00042 
00043   template<typename _Alloc, typename _Tp>
00044     class __alloctr_rebind_helper
00045     {
00046       template<typename _Alloc2, typename _Tp2>
00047     static constexpr true_type
00048     _S_chk(typename _Alloc2::template rebind<_Tp2>::other*);
00049 
00050       template<typename, typename>
00051     static constexpr false_type
00052     _S_chk(...);
00053 
00054     public:
00055       using __type = decltype(_S_chk<_Alloc, _Tp>(nullptr));
00056     };
00057 
00058   template<typename _Alloc, typename _Tp,
00059        bool = __alloctr_rebind_helper<_Alloc, _Tp>::__type::value>
00060     struct __alloctr_rebind;
00061 
00062   template<typename _Alloc, typename _Tp>
00063     struct __alloctr_rebind<_Alloc, _Tp, true>
00064     {
00065       typedef typename _Alloc::template rebind<_Tp>::other __type;
00066     };
00067 
00068   template<template<typename, typename...> class _Alloc, typename _Tp,
00069        typename _Up, typename... _Args>
00070     struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false>
00071     {
00072       typedef _Alloc<_Tp, _Args...> __type;
00073     };
00074 
00075   /**
00076    * @brief  Uniform interface to all allocator types.
00077    * @ingroup allocators
00078   */
00079   template<typename _Alloc>
00080     struct allocator_traits
00081     {
00082       /// The allocator type
00083       typedef _Alloc allocator_type;
00084       /// The allocated type
00085       typedef typename _Alloc::value_type value_type;
00086 
00087 #define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \
00088   private: \
00089   template<typename _Tp> \
00090     static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \
00091   static _ALT _S_##_NTYPE##_helper(...); \
00092     typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \
00093   public:
00094 
00095 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
00096 
00097       /**
00098        * @brief   The allocator's pointer type.
00099        *
00100        * @c Alloc::pointer if that type exists, otherwise @c value_type*
00101       */
00102       typedef __pointer pointer;
00103 
00104 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
00105   typename pointer_traits<pointer>::template rebind<const value_type>)
00106 
00107       /**
00108        * @brief   The allocator's const pointer type.
00109        *
00110        * @c Alloc::const_pointer if that type exists, otherwise
00111        * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
00112       */
00113       typedef __const_pointer const_pointer;
00114 
00115 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
00116   typename pointer_traits<pointer>::template rebind<void>)
00117 
00118       /**
00119        * @brief   The allocator's void pointer type.
00120        *
00121        * @c Alloc::void_pointer if that type exists, otherwise
00122        * <tt> pointer_traits<pointer>::rebind<void> </tt>
00123       */
00124       typedef __void_pointer void_pointer;
00125 
00126 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
00127   typename pointer_traits<pointer>::template rebind<const void>)
00128 
00129       /**
00130        * @brief   The allocator's const void pointer type.
00131        *
00132        * @c Alloc::const_void_pointer if that type exists, otherwise
00133        * <tt> pointer_traits<pointer>::rebind<const void> </tt>
00134       */
00135       typedef __const_void_pointer const_void_pointer;
00136 
00137 _GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type,
00138                   typename pointer_traits<pointer>::difference_type)
00139 
00140       /**
00141        * @brief   The allocator's difference type
00142        *
00143        * @c Alloc::difference_type if that type exists, otherwise
00144        * <tt> pointer_traits<pointer>::difference_type </tt>
00145       */
00146       typedef __difference_type difference_type;
00147 
00148 _GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type,
00149                   typename make_unsigned<difference_type>::type)
00150 
00151       /**
00152        * @brief   The allocator's size type
00153        *
00154        * @c Alloc::size_type if that type exists, otherwise
00155        * <tt> make_unsigned<difference_type>::type </tt>
00156       */
00157       typedef __size_type size_type;
00158 
00159 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment,
00160                   false_type)
00161 
00162       /**
00163        * @brief   How the allocator is propagated on copy assignment
00164        *
00165        * @c Alloc::propagate_on_container_copy_assignment if that type exists,
00166        * otherwise @c false_type
00167       */
00168       typedef __propagate_on_container_copy_assignment
00169     propagate_on_container_copy_assignment;
00170 
00171 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment,
00172                   false_type)
00173 
00174       /**
00175        * @brief   How the allocator is propagated on move assignment
00176        *
00177        * @c Alloc::propagate_on_container_move_assignment if that type exists,
00178        * otherwise @c false_type
00179       */
00180       typedef __propagate_on_container_move_assignment
00181     propagate_on_container_move_assignment;
00182 
00183 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
00184                   false_type)
00185 
00186       /**
00187        * @brief   How the allocator is propagated on swap
00188        *
00189        * @c Alloc::propagate_on_container_swap if that type exists,
00190        * otherwise @c false_type
00191       */
00192       typedef __propagate_on_container_swap propagate_on_container_swap;
00193 
00194 #undef _GLIBCXX_ALLOC_TR_NESTED_TYPE
00195 
00196       template<typename _Tp>
00197     using rebind_alloc = typename __alloctr_rebind<_Alloc, _Tp>::__type;
00198       template<typename _Tp>
00199     using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
00200 
00201     private:
00202       template<typename _Alloc2>
00203     struct __allocate_helper
00204     {
00205       template<typename _Alloc3,
00206         typename = decltype(std::declval<_Alloc3*>()->allocate(
00207           std::declval<size_type>(),
00208           std::declval<const_void_pointer>()))>
00209         static true_type __test(int);
00210 
00211       template<typename>
00212         static false_type __test(...);
00213 
00214       using type = decltype(__test<_Alloc>(0));
00215     };
00216 
00217       template<typename _Alloc2>
00218     using __has_allocate = typename __allocate_helper<_Alloc2>::type;
00219 
00220       template<typename _Alloc2,
00221            typename = _Require<__has_allocate<_Alloc2>>>
00222     static pointer
00223     _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint)
00224     { return __a.allocate(__n, __hint); }
00225 
00226       template<typename _Alloc2, typename _UnusedHint,
00227            typename = _Require<__not_<__has_allocate<_Alloc2>>>>
00228     static pointer
00229     _S_allocate(_Alloc2& __a, size_type __n, _UnusedHint)
00230     { return __a.allocate(__n); }
00231 
00232       template<typename _Tp, typename... _Args>
00233     struct __construct_helper
00234     {
00235       template<typename _Alloc2,
00236         typename = decltype(std::declval<_Alloc2*>()->construct(
00237           std::declval<_Tp*>(), std::declval<_Args>()...))>
00238         static true_type __test(int);
00239 
00240       template<typename>
00241         static false_type __test(...);
00242 
00243       using type = decltype(__test<_Alloc>(0));
00244     };
00245 
00246       template<typename _Tp, typename... _Args>
00247     using __has_construct
00248       = typename __construct_helper<_Tp, _Args...>::type;
00249 
00250       template<typename _Tp, typename... _Args>
00251     static _Require<__has_construct<_Tp, _Args...>>
00252     _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
00253     { __a.construct(__p, std::forward<_Args>(__args)...); }
00254 
00255       template<typename _Tp, typename... _Args>
00256     static
00257     _Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
00258                    is_constructible<_Tp, _Args...>>>
00259     _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
00260     { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
00261 
00262       template<typename _Tp>
00263     struct __destroy_helper
00264     {
00265       template<typename _Alloc2,
00266         typename = decltype(std::declval<_Alloc2*>()->destroy(
00267           std::declval<_Tp*>()))>
00268         static true_type __test(int);
00269 
00270       template<typename>
00271         static false_type __test(...);
00272 
00273       using type = decltype(__test<_Alloc>(0));
00274     };
00275 
00276       template<typename _Tp>
00277     using __has_destroy = typename __destroy_helper<_Tp>::type;
00278 
00279       template<typename _Tp>
00280     static _Require<__has_destroy<_Tp>>
00281     _S_destroy(_Alloc& __a, _Tp* __p)
00282     { __a.destroy(__p); }
00283 
00284       template<typename _Tp>
00285     static _Require<__not_<__has_destroy<_Tp>>>
00286     _S_destroy(_Alloc&, _Tp* __p)
00287     { __p->~_Tp(); }
00288 
00289       template<typename _Alloc2>
00290     struct __maxsize_helper
00291     {
00292       template<typename _Alloc3,
00293         typename = decltype(std::declval<_Alloc3*>()->max_size())>
00294         static true_type __test(int);
00295 
00296       template<typename>
00297         static false_type __test(...);
00298 
00299       using type = decltype(__test<_Alloc2>(0));
00300     };
00301 
00302       template<typename _Alloc2>
00303     using __has_max_size = typename __maxsize_helper<_Alloc2>::type;
00304 
00305       template<typename _Alloc2,
00306            typename = _Require<__has_max_size<_Alloc2>>>
00307     static size_type
00308     _S_max_size(_Alloc2& __a, int)
00309     { return __a.max_size(); }
00310 
00311       template<typename _Alloc2,
00312            typename = _Require<__not_<__has_max_size<_Alloc2>>>>
00313     static size_type
00314     _S_max_size(_Alloc2&, ...)
00315     { return __gnu_cxx::__numeric_traits<size_type>::__max; }
00316 
00317       template<typename _Alloc2>
00318     struct __select_helper
00319     {
00320       template<typename _Alloc3, typename
00321         = decltype(std::declval<_Alloc3*>()
00322         ->select_on_container_copy_construction())>
00323         static true_type __test(int);
00324 
00325       template<typename>
00326         static false_type __test(...);
00327 
00328       using type = decltype(__test<_Alloc2>(0));
00329     };
00330 
00331       template<typename _Alloc2>
00332     using __has_soccc = typename __select_helper<_Alloc2>::type;
00333 
00334       template<typename _Alloc2,
00335            typename = _Require<__has_soccc<_Alloc2>>>
00336     static _Alloc2
00337     _S_select(_Alloc2& __a, int)
00338     { return __a.select_on_container_copy_construction(); }
00339 
00340       template<typename _Alloc2,
00341            typename = _Require<__not_<__has_soccc<_Alloc2>>>>
00342     static _Alloc2
00343     _S_select(_Alloc2& __a, ...)
00344     { return __a; }
00345 
00346     public:
00347 
00348       /**
00349        *  @brief  Allocate memory.
00350        *  @param  __a  An allocator.
00351        *  @param  __n  The number of objects to allocate space for.
00352        *
00353        *  Calls @c a.allocate(n)
00354       */
00355       static pointer
00356       allocate(_Alloc& __a, size_type __n)
00357       { return __a.allocate(__n); }
00358 
00359       /**
00360        *  @brief  Allocate memory.
00361        *  @param  __a  An allocator.
00362        *  @param  __n  The number of objects to allocate space for.
00363        *  @param  __hint Aid to locality.
00364        *  @return Memory of suitable size and alignment for @a n objects
00365        *          of type @c value_type
00366        *
00367        *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
00368        *  well-formed, otherwise returns @c a.allocate(n)
00369       */
00370       static pointer
00371       allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
00372       { return _S_allocate(__a, __n, __hint); }
00373 
00374       /**
00375        *  @brief  Deallocate memory.
00376        *  @param  __a  An allocator.
00377        *  @param  __p  Pointer to the memory to deallocate.
00378        *  @param  __n  The number of objects space was allocated for.
00379        *
00380        *  Calls <tt> a.deallocate(p, n) </tt>
00381       */
00382       static void deallocate(_Alloc& __a, pointer __p, size_type __n)
00383       { __a.deallocate(__p, __n); }
00384 
00385       /**
00386        *  @brief  Construct an object of type @a _Tp
00387        *  @param  __a  An allocator.
00388        *  @param  __p  Pointer to memory of suitable size and alignment for Tp
00389        *  @param  __args Constructor arguments.
00390        *
00391        *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
00392        *  if that expression is well-formed, otherwise uses placement-new
00393        *  to construct an object of type @a _Tp at location @a __p from the
00394        *  arguments @a __args...
00395       */
00396       template<typename _Tp, typename... _Args>
00397     static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
00398     -> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
00399     { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
00400 
00401       /**
00402        *  @brief  Destroy an object of type @a _Tp
00403        *  @param  __a  An allocator.
00404        *  @param  __p  Pointer to the object to destroy
00405        *
00406        *  Calls @c __a.destroy(__p) if that expression is well-formed,
00407        *  otherwise calls @c __p->~_Tp()
00408       */
00409       template <class _Tp>
00410     static void destroy(_Alloc& __a, _Tp* __p)
00411     { _S_destroy(__a, __p); }
00412 
00413       /**
00414        *  @brief  The maximum supported allocation size
00415        *  @param  __a  An allocator.
00416        *  @return @c __a.max_size() or @c numeric_limits<size_type>::max()
00417        *
00418        *  Returns @c __a.max_size() if that expression is well-formed,
00419        *  otherwise returns @c numeric_limits<size_type>::max()
00420       */
00421       static size_type max_size(const _Alloc& __a) noexcept
00422       { return _S_max_size(__a, 0); }
00423 
00424       /**
00425        *  @brief  Obtain an allocator to use when copying a container.
00426        *  @param  __rhs  An allocator.
00427        *  @return @c __rhs.select_on_container_copy_construction() or @a __rhs
00428        *
00429        *  Returns @c __rhs.select_on_container_copy_construction() if that
00430        *  expression is well-formed, otherwise returns @a __rhs
00431       */
00432       static _Alloc
00433       select_on_container_copy_construction(const _Alloc& __rhs)
00434       { return _S_select(__rhs, 0); }
00435     };
00436 
00437   template<typename _Alloc>
00438     inline void
00439     __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
00440     { __one = __two; }
00441 
00442   template<typename _Alloc>
00443     inline void
00444     __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
00445     { }
00446 
00447   template<typename _Alloc>
00448     inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
00449     {
00450       typedef allocator_traits<_Alloc> __traits;
00451       typedef typename __traits::propagate_on_container_copy_assignment __pocca;
00452       __do_alloc_on_copy(__one, __two, __pocca());
00453     }
00454 
00455   template<typename _Alloc>
00456     inline _Alloc __alloc_on_copy(const _Alloc& __a)
00457     {
00458       typedef allocator_traits<_Alloc> __traits;
00459       return __traits::select_on_container_copy_construction(__a);
00460     }
00461 
00462   template<typename _Alloc>
00463     inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
00464     { __one = std::move(__two); }
00465 
00466   template<typename _Alloc>
00467     inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
00468     { }
00469 
00470   template<typename _Alloc>
00471     inline void __alloc_on_move(_Alloc& __one, _Alloc& __two)
00472     {
00473       typedef allocator_traits<_Alloc> __traits;
00474       typedef typename __traits::propagate_on_container_move_assignment __pocma;
00475       __do_alloc_on_move(__one, __two, __pocma());
00476     }
00477 
00478   template<typename _Alloc>
00479     inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
00480     {
00481       using std::swap;
00482       swap(__one, __two);
00483     }
00484 
00485   template<typename _Alloc>
00486     inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
00487     { }
00488 
00489   template<typename _Alloc>
00490     inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two)
00491     {
00492       typedef allocator_traits<_Alloc> __traits;
00493       typedef typename __traits::propagate_on_container_swap __pocs;
00494       __do_alloc_on_swap(__one, __two, __pocs());
00495     }
00496 
00497   template<typename _Alloc>
00498     class __is_copy_insertable_impl
00499     {
00500       typedef allocator_traits<_Alloc> _Traits;
00501 
00502       template<typename _Up, typename
00503            = decltype(_Traits::construct(std::declval<_Alloc&>(),
00504                          std::declval<_Up*>(),
00505                          std::declval<const _Up&>()))>
00506     static true_type
00507     _M_select(int);
00508 
00509       template<typename _Up>
00510     static false_type
00511     _M_select(...);
00512 
00513     public:
00514       typedef decltype(_M_select<typename _Alloc::value_type>(0)) type;
00515     };
00516 
00517   // true if _Alloc::value_type is CopyInsertable into containers using _Alloc
00518   template<typename _Alloc>
00519     struct __is_copy_insertable
00520     : __is_copy_insertable_impl<_Alloc>::type
00521     { };
00522 
00523   // std::allocator<_Tp> just requires CopyConstructible
00524   template<typename _Tp>
00525     struct __is_copy_insertable<allocator<_Tp>>
00526     : is_copy_constructible<_Tp>
00527     { };
00528 
00529 _GLIBCXX_END_NAMESPACE_VERSION
00530 } // namespace std
00531 
00532 #endif
00533 #endif