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

   1 // Allocators -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
   4 // 2011 Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  * Copyright (c) 1996-1997
  28  * Silicon Graphics Computer Systems, Inc.
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Silicon Graphics makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  */
  38
  39 /** @file bits/allocator.h
  40  *  This is an internal header file, included by other library headers.
  41  *  Do not attempt to use it directly. @headername{memory}
  42  */
  43
  44 #ifndef _ALLOCATOR_H
  45 #define _ALLOCATOR_H 1
  46
  47 // Define the base class to std::allocator.
  48 #include <bits/c++allocator.h>
  49
  50 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  51 #include <bits/ptr_traits.h>
  52 #include <type_traits> // For _GLIBCXX_HAS_NESTED_TYPE
  53 #include <limits>
  54 #endif
  55
  56 namespace std _GLIBCXX_VISIBILITY(default)
  57 {
  58 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  59
  60   /**
  61    * @defgroup allocators Allocators
  62    * @ingroup memory
  63    *
  64    * Classes encapsulating memory operations.
  65    */
  66
  67   template<typename _Tp>
  68     class allocator;
  69
  70   /// allocator<void> specialization.
  71   template<>
  72     class allocator<void>
  73     {
  74     public:
  75       typedef size_t      size_type;
  76       typedef ptrdiff_t   difference_type;
  77       typedef void*       pointer;
  78       typedef const void* const_pointer;
  79       typedef void        value_type;
  80
  81       template<typename _Tp1>
  82         struct rebind
  83         { typedef allocator<_Tp1> other; };
  84     };
  85
  86   /**
  87    * @brief  The @a standard allocator, as per [20.4].
  88    * @ingroup allocators
  89    *
  90    *  See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt04ch11.html
  91    *  for further details.
  92    */
  93   template<typename _Tp>
  94     class allocator: public __glibcxx_base_allocator<_Tp>
  95     {
  96    public:
  97       typedef size_t     size_type;
  98       typedef ptrdiff_t  difference_type;
  99       typedef _Tp*       pointer;
 100       typedef const _Tp* const_pointer;
 101       typedef _Tp&       reference;
 102       typedef const _Tp& const_reference;
 103       typedef _Tp        value_type;
 104
 105       template<typename _Tp1>
 106         struct rebind
 107         { typedef allocator<_Tp1> other; };
 108
 109       allocator() throw() { }
 110
 111       allocator(const allocator& __a) throw()
 112       : __glibcxx_base_allocator<_Tp>(__a) { }
 113
 114       template<typename _Tp1>
 115         allocator(const allocator<_Tp1>&) throw() { }
 116
 117       ~allocator() throw() { }
 118
 119       // Inherit everything else.
 120     };
 121
 122   template<typename _T1, typename _T2>
 123     inline bool
 124     operator==(const allocator<_T1>&, const allocator<_T2>&)
 125     { return true; }
 126
 127   template<typename _Tp>
 128     inline bool
 129     operator==(const allocator<_Tp>&, const allocator<_Tp>&)
 130     { return true; }
 131
 132   template<typename _T1, typename _T2>
 133     inline bool
 134     operator!=(const allocator<_T1>&, const allocator<_T2>&)
 135     { return false; }
 136
 137   template<typename _Tp>
 138     inline bool
 139     operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
 140     { return false; }
 141
 142   // Inhibit implicit instantiations for required instantiations,
 143   // which are defined via explicit instantiations elsewhere.
 144 #if _GLIBCXX_EXTERN_TEMPLATE
 145   extern template class allocator<char>;
 146   extern template class allocator<wchar_t>;
 147 #endif
 148
 149   // Undefine.
 150 #undef __glibcxx_base_allocator
 151
 152   // To implement Option 3 of DR 431.
 153   template<typename _Alloc, bool = __is_empty(_Alloc)>
 154     struct __alloc_swap
 155     { static void _S_do_it(_Alloc&, _Alloc&) { } };
 156
 157   template<typename _Alloc>
 158     struct __alloc_swap<_Alloc, false>
 159     {
 160       static void
 161       _S_do_it(_Alloc& __one, _Alloc& __two)
 162       {
 163         // Precondition: swappable allocators.
 164         if (__one != __two)
 165           swap(__one, __two);
 166       }
 167     };
 168
 169   // Optimize for stateless allocators.
 170   template<typename _Alloc, bool = __is_empty(_Alloc)>
 171     struct __alloc_neq
 172     {
 173       static bool
 174       _S_do_it(const _Alloc&, const _Alloc&)
 175       { return false; }
 176     };
 177
 178   template<typename _Alloc>
 179     struct __alloc_neq<_Alloc, false>
 180     {
 181       static bool
 182       _S_do_it(const _Alloc& __one, const _Alloc& __two)
 183       { return __one != __two; }
 184     };
 185
 186 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 187   // A very basic implementation for now.  In general we have to wait for
 188   // the availability of the infrastructure described in N2983:  we should
 189   // try when either T has a move constructor which cannot throw or T is
 190   // CopyConstructible.
 191   // NB: This code doesn't properly belong here, we should find a more
 192   // suited place common to std::vector and std::deque.
 193   template<typename _Tp,
 194            bool = __has_trivial_copy(typename _Tp::value_type)>
 195     struct __shrink_to_fit
 196     { static void _S_do_it(_Tp&) { } };
 197
 198   template<typename _Tp>
 199     struct __shrink_to_fit<_Tp, true>
 200     {
 201       static void
 202       _S_do_it(_Tp& __v)
 203       {
 204         __try
 205           { _Tp(__v).swap(__v); }
 206         __catch(...) { }
 207       }
 208     };
 209
 210
 211   /// [allocator.tag]
 212   struct allocator_arg_t { };
 213
 214   constexpr allocator_arg_t allocator_arg = allocator_arg_t();
 215
 216 _GLIBCXX_HAS_NESTED_TYPE(allocator_type)
 217
 218   template<typename _Tp, typename _Alloc,
 219            bool = __has_allocator_type<_Tp>::value>
 220     struct __uses_allocator_helper
 221     : public false_type { };
 222
 223   template<typename _Tp, typename _Alloc>
 224     struct __uses_allocator_helper<_Tp, _Alloc, true>
 225     : public integral_constant<bool, is_convertible<_Alloc,
 226                                      typename _Tp::allocator_type>::value>
 227     { };
 228
 229   /// [allocator.uses.trait]
 230   template<typename _Tp, typename _Alloc>
 231     struct uses_allocator
 232     : public integral_constant<bool,
 233                                __uses_allocator_helper<_Tp, _Alloc>::value>
 234     { };
 235
 236   template<typename _Alloc, typename _Tp>
 237     class __alloctr_rebind_helper
 238     {
 239       template<typename _Alloc2, typename _Tp2>
 240         static constexpr bool
 241         _S_chk(typename _Alloc2::template rebind<_Tp2>::other*)
 242         { return true; }
 243
 244       template<typename, typename>
 245         static constexpr bool
 246         _S_chk(...)
 247         { return false; }
 248
 249     public:
 250       static const bool __value = _S_chk<_Alloc, _Tp>(nullptr);
 251     };
 252
 253   template<typename _Alloc, typename _Tp,
 254            bool = __alloctr_rebind_helper<_Alloc, _Tp>::__value>
 255     struct __alloctr_rebind;
 256
 257   template<typename _Alloc, typename _Tp>
 258     struct __alloctr_rebind<_Alloc, _Tp, true>
 259     {
 260       typedef typename _Alloc::template rebind<_Tp>::other __type;
 261     };
 262
 263   template<template<typename, typename...> class _Alloc, typename _Tp,
 264             typename _Up, typename... _Args>
 265     struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false>
 266     {
 267       typedef _Alloc<_Tp, _Args...> __type;
 268     };
 269
 270   /**
 271    * @brief  Uniform interface to all allocator types.
 272    * @ingroup allocators
 273   */
 274   template<typename _Alloc>
 275     struct allocator_traits
 276     {
 277       /// The allocator type
 278       typedef _Alloc allocator_type;
 279       /// The allocated type
 280       typedef typename _Alloc::value_type value_type;
 281
 282 #define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \
 283   private: \
 284   template<typename _Tp> \
 285     static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \
 286   static _ALT _S_##_NTYPE##_helper(...); \
 287     typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \
 288   public:
 289
 290 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
 291
 292       /**
 293        * @brief   The allocator's pointer type.
 294        *
 295        * @c Alloc::pointer if that type exists, otherwise @c value_type*
 296       */
 297       typedef __pointer pointer;
 298
 299 // TODO: Use pointer_traits::rebind alias template.
 300
 301 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
 302   typename pointer_traits<pointer>::template __rebind<const value_type>::__type)
 303
 304       /**
 305        * @brief   The allocator's const pointer type.
 306        *
 307        * @c Alloc::const_pointer if that type exists, otherwise
 308        * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
 309       */
 310       typedef __const_pointer const_pointer;
 311
 312 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
 313   typename pointer_traits<pointer>::template __rebind<void>::__type)
 314
 315       /**
 316        * @brief   The allocator's void pointer type.
 317        *
 318        * @c Alloc::void_pointer if that type exists, otherwise
 319        * <tt> pointer_traits<pointer>::rebind<void> </tt>
 320       */
 321       typedef __void_pointer void_pointer;
 322
 323 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
 324   typename pointer_traits<pointer>::template __rebind<const void>::__type)
 325
 326       /**
 327        * @brief   The allocator's const void pointer type.
 328        *
 329        * @c Alloc::const_void_pointer if that type exists, otherwise
 330        * <tt> pointer_traits<pointer>::rebind<const void> </tt>
 331       */
 332       typedef __const_void_pointer const_void_pointer;
 333
 334 _GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type,
 335                               typename pointer_traits<pointer>::difference_type)
 336
 337       /**
 338        * @brief   The allocator's difference type
 339        *
 340        * @c Alloc::difference_type if that type exists, otherwise
 341        * <tt> pointer_traits<pointer>::difference_type </tt>
 342       */
 343       typedef __difference_type difference_type;
 344
 345 _GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type,
 346                               typename make_unsigned<difference_type>::type)
 347
 348       /**
 349        * @brief   The allocator's size type
 350        *
 351        * @c Alloc::size_type if that type exists, otherwise
 352        * <tt> make_unsigned<difference_type>::type </tt>
 353       */
 354       typedef __size_type size_type;
 355
 356 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment,
 357                               false_type)
 358
 359       /**
 360        * @brief   How the allocator is propagated on copy assignment
 361        *
 362        * @c Alloc::propagate_on_container_copy_assignment if that type exists,
 363        * otherwise @c false_type
 364       */
 365       typedef __propagate_on_container_copy_assignment
 366         propagate_on_container_copy_assignment;
 367
 368 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment,
 369                               false_type)
 370
 371       /**
 372        * @brief   How the allocator is propagated on move assignment
 373        *
 374        * @c Alloc::propagate_on_container_move_assignment if that type exists,
 375        * otherwise @c false_type
 376       */
 377       typedef __propagate_on_container_move_assignment
 378         propagate_on_container_move_assignment;
 379
 380 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
 381                               false_type)
 382
 383       /**
 384        * @brief   How the allocator is propagated on swap
 385        *
 386        * @c Alloc::propagate_on_container_swap if that type exists,
 387        * otherwise @c false_type
 388       */
 389       typedef __propagate_on_container_swap propagate_on_container_swap;
 390
 391 #undef _GLIBCXX_ALLOC_TR_NESTED_TYPE
 392
 393       /* TODO: use template alias
 394       template<typename _Tp>
 395         using rebind_alloc = __alloctr_rebind<_Alloc, _Tp>::__type;
 396       template<typename _Tp>
 397         using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
 398       */
 399       template<typename _Tp>
 400         struct __rebind_alloc
 401         {
 402           typedef typename __alloctr_rebind<_Alloc, _Tp>::__type __type;
 403         };
 404
 405       template<typename _Tp>
 406         struct __rebind_traits
 407         {
 408           typedef allocator_traits<typename __rebind_alloc<_Tp>::__type> __type;
 409         };
 410
 411     private:
 412       template<typename _Alloc2>
 413         struct __allocate_helper
 414         {
 415           template<typename _Alloc3,
 416             typename = decltype(std::declval<_Alloc3*>()->allocate(
 417                   std::declval<size_type>(),
 418                   std::declval<const_void_pointer>()))>
 419             static true_type __test(int);
 420
 421           template<typename>
 422             static false_type __test(...);
 423
 424           typedef decltype(__test<_Alloc>(0)) type;
 425           static const bool value = type::value;
 426         };
 427
 428       template<typename _Alloc2>
 429         static typename
 430         enable_if<__allocate_helper<_Alloc2>::value, pointer>::type
 431         _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint)
 432         { return __a.allocate(__n, __hint); }
 433
 434       template<typename _Alloc2>
 435         static typename
 436         enable_if<!__allocate_helper<_Alloc2>::value, pointer>::type
 437         _S_allocate(_Alloc2& __a, size_type __n, ...)
 438         { return __a.allocate(__n); }
 439
 440       template<typename _Tp, typename... _Args>
 441         struct __construct_helper
 442         {
 443           template<typename _Alloc2,
 444             typename = decltype(std::declval<_Alloc2*>()->construct(
 445                   std::declval<_Tp*>(), std::declval<_Args>()...))>
 446             static true_type __test(int);
 447
 448           template<typename>
 449             static false_type __test(...);
 450
 451           typedef decltype(__test<_Alloc>(0)) type;
 452           static const bool value = type::value;
 453         };
 454
 455       template<typename _Tp, typename... _Args>
 456         static typename
 457         enable_if<__construct_helper<_Tp, _Args...>::value, void>::type
 458         _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
 459         { __a.construct(__p, std::forward<_Args>(__args)...); }
 460
 461       template<typename _Tp, typename... _Args>
 462         static typename
 463         enable_if<!__construct_helper<_Tp, _Args...>::value, void>::type
 464         _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
 465         { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
 466
 467       template<typename _Tp>
 468         struct __destroy_helper
 469         {
 470           template<typename _Alloc2,
 471             typename = decltype(std::declval<_Alloc2*>()->destroy(
 472                   std::declval<_Tp*>()))>
 473             static true_type __test(int);
 474
 475           template<typename>
 476             static false_type __test(...);
 477
 478           typedef decltype(__test<_Alloc>(0)) type;
 479           static const bool value = type::value;
 480         };
 481
 482       template<typename _Tp>
 483         static typename enable_if<__destroy_helper<_Tp>::value, void>::type
 484         _S_destroy(_Alloc& __a, _Tp* __p)
 485         { __a.destroy(__p); }
 486
 487       template<typename _Tp>
 488         static typename enable_if<!__destroy_helper<_Tp>::value, void>::type
 489         _S_destroy(_Alloc&, _Tp* __p)
 490         { __p->~_Tp(); }
 491
 492       template<typename _Alloc2>
 493         struct __maxsize_helper
 494         {
 495           template<typename _Alloc3,
 496             typename = decltype(std::declval<_Alloc3*>()->max_size())>
 497             static true_type __test(int);
 498
 499           template<typename>
 500             static false_type __test(...);
 501
 502           typedef decltype(__test<_Alloc2>(0)) type;
 503           static const bool value = type::value;
 504         };
 505
 506       template<typename _Alloc2>
 507         static typename
 508         enable_if<__maxsize_helper<_Alloc2>::value, size_type>::type
 509         _S_max_size(_Alloc2& __a)
 510         { return __a.max_size(); }
 511
 512       template<typename _Alloc2>
 513         static typename
 514         enable_if<!__maxsize_helper<_Alloc2>::value, size_type>::type
 515         _S_max_size(_Alloc2&)
 516         { return numeric_limits<size_type>::max(); }
 517
 518       template<typename _Alloc2>
 519         struct __select_helper
 520         {
 521           template<typename _Alloc3, typename
 522             = decltype(std::declval<_Alloc3*>()
 523                 ->select_on_container_copy_construction())>
 524             static true_type __test(int);
 525
 526           template<typename>
 527             static false_type __test(...);
 528
 529           typedef decltype(__test<_Alloc2>(0)) type;
 530           static const bool value = type::value;
 531         };
 532       template<typename _Alloc2>
 533         static typename
 534         enable_if<__select_helper<_Alloc2>::value, _Alloc2>::type
 535         _S_select(_Alloc2& __a)
 536         { return __a.select_on_container_copy_construction(); }
 537
 538       template<typename _Alloc2>
 539         static typename
 540         enable_if<!__select_helper<_Alloc2>::value, _Alloc2>::type
 541         _S_select(_Alloc2& __a)
 542         { return __a; }
 543
 544     public:
 545
 546       /**
 547        *  @brief  Allocate memory.
 548        *  @param  a  An allocator.
 549        *  @param  n  The number of objects to allocate space for.
 550        *
 551        *  Calls @c a.allocate(n)
 552       */
 553       static pointer
 554       allocate(_Alloc& __a, size_type __n)
 555       { return __a.allocate(__n); }
 556
 557       /**
 558        *  @brief  Allocate memory.
 559        *  @param  a  An allocator.
 560        *  @param  n  The number of objects to allocate space for.
 561        *  @param  hint Aid to locality.
 562        *  @return Memory of suitable size and alignment for @a n objects
 563        *          of type @c value_type
 564        *
 565        *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
 566        *  well-formed, otherwise returns @c a.allocate(n)
 567       */
 568       static pointer
 569       allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
 570       { return _S_allocate(__a, __n, __hint); }
 571
 572       /**
 573        *  @brief  Deallocate memory.
 574        *  @param  a  An allocator.
 575        *  @param  p  Pointer to the memory to deallocate.
 576        *  @param  n  The number of objects space was allocated for.
 577        *
 578        *  Calls <tt> a.deallocate(p, n) </tt>
 579       */
 580       static void deallocate(_Alloc& __a, pointer __p, size_type __n)
 581       { __a.deallocate(__p, __n); }
 582
 583       /**
 584        *  @brief  Construct an object of type @a Tp
 585        *  @param  a  An allocator.
 586        *  @param  p  Pointer to memory of suitable size and alignment for Tp
 587        *  @param  args Constructor arguments.
 588        *
 589        *  Calls <tt> a.construct(p, std::forward<Args>(args)...) </tt>
 590        *  if that expression is well-formed, otherwise uses placement-new
 591        *  to construct an object of type @a Tp at location @a p from the
 592        *  arguments @a args...
 593       */
 594       template<typename _Tp, typename... _Args>
 595         static void construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
 596         { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
 597
 598       /**
 599        *  @brief  Destroy an object of type @a Tp
 600        *  @param  a  An allocator.
 601        *  @param  p  Pointer to the object to destroy
 602        *
 603        *  Calls @c a.destroy(p) if that expression is well-formed,
 604        *  otherwise calls @c p->~Tp()
 605       */
 606       template <class _Tp>
 607         static void destroy(_Alloc& __a, _Tp* __p)
 608         { _S_destroy(__a, __p); }
 609
 610       /**
 611        *  @brief  The maximum supported allocation size
 612        *  @param  a  An allocator.
 613        *  @return @c a.max_size() or @c %numeric_limits<size_type>::max()
 614        *
 615        *  Returns @c a.max_size() if that expression is well-formed,
 616        *  otherwise returns @c %numeric_limits<size_type>::max()
 617       */
 618       static size_type max_size(const _Alloc& __a)
 619       { return _S_max_size(__a); }
 620
 621       /**
 622        *  @brief  Obtain an allocator to use when copying a container.
 623        *  @param  rhs  An allocator.
 624        *  @return @c rhs.select_on_container_copy_construction() or @a rhs
 625        *
 626        *  Returns @c rhs.select_on_container_copy_construction() if that
 627        *  expression is well-formed, otherwise returns @a rhs
 628       */
 629       static _Alloc
 630       select_on_container_copy_construction(const _Alloc& __rhs)
 631       { return _S_select(__rhs); }
 632     };
 633
 634 #endif
 635
 636 _GLIBCXX_END_NAMESPACE_VERSION
 637 } // namespace std
 638
 639 #endif