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 <bits/uses_allocator.h>
  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   template<typename _Alloc, typename _Tp>
 211     class __alloctr_rebind_helper
 212     {
 213       template<typename _Alloc2, typename _Tp2>
 214         static constexpr bool
 215         _S_chk(typename _Alloc2::template rebind<_Tp2>::other*)
 216         { return true; }
 217
 218       template<typename, typename>
 219         static constexpr bool
 220         _S_chk(...)
 221         { return false; }
 222
 223     public:
 224       static const bool __value = _S_chk<_Alloc, _Tp>(nullptr);
 225     };
 226
 227   template<typename _Alloc, typename _Tp,
 228            bool = __alloctr_rebind_helper<_Alloc, _Tp>::__value>
 229     struct __alloctr_rebind;
 230
 231   template<typename _Alloc, typename _Tp>
 232     struct __alloctr_rebind<_Alloc, _Tp, true>
 233     {
 234       typedef typename _Alloc::template rebind<_Tp>::other __type;
 235     };
 236
 237   template<template<typename, typename...> class _Alloc, typename _Tp,
 238             typename _Up, typename... _Args>
 239     struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false>
 240     {
 241       typedef _Alloc<_Tp, _Args...> __type;
 242     };
 243
 244   /**
 245    * @brief  Uniform interface to all allocator types.
 246    * @ingroup allocators
 247   */
 248   template<typename _Alloc>
 249     struct allocator_traits
 250     {
 251       /// The allocator type
 252       typedef _Alloc allocator_type;
 253       /// The allocated type
 254       typedef typename _Alloc::value_type value_type;
 255
 256 #define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \
 257   private: \
 258   template<typename _Tp> \
 259     static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \
 260   static _ALT _S_##_NTYPE##_helper(...); \
 261     typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \
 262   public:
 263
 264 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
 265
 266       /**
 267        * @brief   The allocator's pointer type.
 268        *
 269        * @c Alloc::pointer if that type exists, otherwise @c value_type*
 270       */
 271       typedef __pointer pointer;
 272
 273 // TODO: Use pointer_traits::rebind alias template.
 274
 275 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
 276   typename pointer_traits<pointer>::template __rebind<const value_type>::__type)
 277
 278       /**
 279        * @brief   The allocator's const pointer type.
 280        *
 281        * @c Alloc::const_pointer if that type exists, otherwise
 282        * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
 283       */
 284       typedef __const_pointer const_pointer;
 285
 286 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
 287   typename pointer_traits<pointer>::template __rebind<void>::__type)
 288
 289       /**
 290        * @brief   The allocator's void pointer type.
 291        *
 292        * @c Alloc::void_pointer if that type exists, otherwise
 293        * <tt> pointer_traits<pointer>::rebind<void> </tt>
 294       */
 295       typedef __void_pointer void_pointer;
 296
 297 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
 298   typename pointer_traits<pointer>::template __rebind<const void>::__type)
 299
 300       /**
 301        * @brief   The allocator's const void pointer type.
 302        *
 303        * @c Alloc::const_void_pointer if that type exists, otherwise
 304        * <tt> pointer_traits<pointer>::rebind<const void> </tt>
 305       */
 306       typedef __const_void_pointer const_void_pointer;
 307
 308 _GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type,
 309                               typename pointer_traits<pointer>::difference_type)
 310
 311       /**
 312        * @brief   The allocator's difference type
 313        *
 314        * @c Alloc::difference_type if that type exists, otherwise
 315        * <tt> pointer_traits<pointer>::difference_type </tt>
 316       */
 317       typedef __difference_type difference_type;
 318
 319 _GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type,
 320                               typename make_unsigned<difference_type>::type)
 321
 322       /**
 323        * @brief   The allocator's size type
 324        *
 325        * @c Alloc::size_type if that type exists, otherwise
 326        * <tt> make_unsigned<difference_type>::type </tt>
 327       */
 328       typedef __size_type size_type;
 329
 330 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment,
 331                               false_type)
 332
 333       /**
 334        * @brief   How the allocator is propagated on copy assignment
 335        *
 336        * @c Alloc::propagate_on_container_copy_assignment if that type exists,
 337        * otherwise @c false_type
 338       */
 339       typedef __propagate_on_container_copy_assignment
 340         propagate_on_container_copy_assignment;
 341
 342 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment,
 343                               false_type)
 344
 345       /**
 346        * @brief   How the allocator is propagated on move assignment
 347        *
 348        * @c Alloc::propagate_on_container_move_assignment if that type exists,
 349        * otherwise @c false_type
 350       */
 351       typedef __propagate_on_container_move_assignment
 352         propagate_on_container_move_assignment;
 353
 354 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
 355                               false_type)
 356
 357       /**
 358        * @brief   How the allocator is propagated on swap
 359        *
 360        * @c Alloc::propagate_on_container_swap if that type exists,
 361        * otherwise @c false_type
 362       */
 363       typedef __propagate_on_container_swap propagate_on_container_swap;
 364
 365 #undef _GLIBCXX_ALLOC_TR_NESTED_TYPE
 366
 367       /* TODO: use template alias
 368       template<typename _Tp>
 369         using rebind_alloc = __alloctr_rebind<_Alloc, _Tp>::__type;
 370       template<typename _Tp>
 371         using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
 372       */
 373       template<typename _Tp>
 374         struct __rebind_alloc
 375         {
 376           typedef typename __alloctr_rebind<_Alloc, _Tp>::__type __type;
 377         };
 378
 379       template<typename _Tp>
 380         struct __rebind_traits
 381         {
 382           typedef allocator_traits<typename __rebind_alloc<_Tp>::__type> __type;
 383         };
 384
 385     private:
 386       template<typename _Alloc2>
 387         struct __allocate_helper
 388         {
 389           template<typename _Alloc3,
 390             typename = decltype(std::declval<_Alloc3*>()->allocate(
 391                   std::declval<size_type>(),
 392                   std::declval<const_void_pointer>()))>
 393             static true_type __test(int);
 394
 395           template<typename>
 396             static false_type __test(...);
 397
 398           typedef decltype(__test<_Alloc>(0)) type;
 399           static const bool value = type::value;
 400         };
 401
 402       template<typename _Alloc2>
 403         static typename
 404         enable_if<__allocate_helper<_Alloc2>::value, pointer>::type
 405         _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint)
 406         { return __a.allocate(__n, __hint); }
 407
 408       template<typename _Alloc2>
 409         static typename
 410         enable_if<!__allocate_helper<_Alloc2>::value, pointer>::type
 411         _S_allocate(_Alloc2& __a, size_type __n, ...)
 412         { return __a.allocate(__n); }
 413
 414       template<typename _Tp, typename... _Args>
 415         struct __construct_helper
 416         {
 417           template<typename _Alloc2,
 418             typename = decltype(std::declval<_Alloc2*>()->construct(
 419                   std::declval<_Tp*>(), std::declval<_Args>()...))>
 420             static true_type __test(int);
 421
 422           template<typename>
 423             static false_type __test(...);
 424
 425           typedef decltype(__test<_Alloc>(0)) type;
 426           static const bool value = type::value;
 427         };
 428
 429       template<typename _Tp, typename... _Args>
 430         static typename
 431         enable_if<__construct_helper<_Tp, _Args...>::value, void>::type
 432         _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
 433         { __a.construct(__p, std::forward<_Args>(__args)...); }
 434
 435       template<typename _Tp, typename... _Args>
 436         static typename
 437         enable_if<!__construct_helper<_Tp, _Args...>::value, void>::type
 438         _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
 439         { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
 440
 441       template<typename _Tp>
 442         struct __destroy_helper
 443         {
 444           template<typename _Alloc2,
 445             typename = decltype(std::declval<_Alloc2*>()->destroy(
 446                   std::declval<_Tp*>()))>
 447             static true_type __test(int);
 448
 449           template<typename>
 450             static false_type __test(...);
 451
 452           typedef decltype(__test<_Alloc>(0)) type;
 453           static const bool value = type::value;
 454         };
 455
 456       template<typename _Tp>
 457         static typename enable_if<__destroy_helper<_Tp>::value, void>::type
 458         _S_destroy(_Alloc& __a, _Tp* __p)
 459         { __a.destroy(__p); }
 460
 461       template<typename _Tp>
 462         static typename enable_if<!__destroy_helper<_Tp>::value, void>::type
 463         _S_destroy(_Alloc&, _Tp* __p)
 464         { __p->~_Tp(); }
 465
 466       template<typename _Alloc2>
 467         struct __maxsize_helper
 468         {
 469           template<typename _Alloc3,
 470             typename = decltype(std::declval<_Alloc3*>()->max_size())>
 471             static true_type __test(int);
 472
 473           template<typename>
 474             static false_type __test(...);
 475
 476           typedef decltype(__test<_Alloc2>(0)) type;
 477           static const bool value = type::value;
 478         };
 479
 480       template<typename _Alloc2>
 481         static typename
 482         enable_if<__maxsize_helper<_Alloc2>::value, size_type>::type
 483         _S_max_size(_Alloc2& __a)
 484         { return __a.max_size(); }
 485
 486       template<typename _Alloc2>
 487         static typename
 488         enable_if<!__maxsize_helper<_Alloc2>::value, size_type>::type
 489         _S_max_size(_Alloc2&)
 490         { return numeric_limits<size_type>::max(); }
 491
 492       template<typename _Alloc2>
 493         struct __select_helper
 494         {
 495           template<typename _Alloc3, typename
 496             = decltype(std::declval<_Alloc3*>()
 497                 ->select_on_container_copy_construction())>
 498             static true_type __test(int);
 499
 500           template<typename>
 501             static false_type __test(...);
 502
 503           typedef decltype(__test<_Alloc2>(0)) type;
 504           static const bool value = type::value;
 505         };
 506       template<typename _Alloc2>
 507         static typename
 508         enable_if<__select_helper<_Alloc2>::value, _Alloc2>::type
 509         _S_select(_Alloc2& __a)
 510         { return __a.select_on_container_copy_construction(); }
 511
 512       template<typename _Alloc2>
 513         static typename
 514         enable_if<!__select_helper<_Alloc2>::value, _Alloc2>::type
 515         _S_select(_Alloc2& __a)
 516         { return __a; }
 517
 518     public:
 519
 520       /**
 521        *  @brief  Allocate memory.
 522        *  @param  a  An allocator.
 523        *  @param  n  The number of objects to allocate space for.
 524        *
 525        *  Calls @c a.allocate(n)
 526       */
 527       static pointer
 528       allocate(_Alloc& __a, size_type __n)
 529       { return __a.allocate(__n); }
 530
 531       /**
 532        *  @brief  Allocate memory.
 533        *  @param  a  An allocator.
 534        *  @param  n  The number of objects to allocate space for.
 535        *  @param  hint Aid to locality.
 536        *  @return Memory of suitable size and alignment for @a n objects
 537        *          of type @c value_type
 538        *
 539        *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
 540        *  well-formed, otherwise returns @c a.allocate(n)
 541       */
 542       static pointer
 543       allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
 544       { return _S_allocate(__a, __n, __hint); }
 545
 546       /**
 547        *  @brief  Deallocate memory.
 548        *  @param  a  An allocator.
 549        *  @param  p  Pointer to the memory to deallocate.
 550        *  @param  n  The number of objects space was allocated for.
 551        *
 552        *  Calls <tt> a.deallocate(p, n) </tt>
 553       */
 554       static void deallocate(_Alloc& __a, pointer __p, size_type __n)
 555       { __a.deallocate(__p, __n); }
 556
 557       /**
 558        *  @brief  Construct an object of type @a Tp
 559        *  @param  a  An allocator.
 560        *  @param  p  Pointer to memory of suitable size and alignment for Tp
 561        *  @param  args Constructor arguments.
 562        *
 563        *  Calls <tt> a.construct(p, std::forward<Args>(args)...) </tt>
 564        *  if that expression is well-formed, otherwise uses placement-new
 565        *  to construct an object of type @a Tp at location @a p from the
 566        *  arguments @a args...
 567       */
 568       template<typename _Tp, typename... _Args>
 569         static void construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
 570         { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
 571
 572       /**
 573        *  @brief  Destroy an object of type @a Tp
 574        *  @param  a  An allocator.
 575        *  @param  p  Pointer to the object to destroy
 576        *
 577        *  Calls @c a.destroy(p) if that expression is well-formed,
 578        *  otherwise calls @c p->~Tp()
 579       */
 580       template <class _Tp>
 581         static void destroy(_Alloc& __a, _Tp* __p)
 582         { _S_destroy(__a, __p); }
 583
 584       /**
 585        *  @brief  The maximum supported allocation size
 586        *  @param  a  An allocator.
 587        *  @return @c a.max_size() or @c %numeric_limits<size_type>::max()
 588        *
 589        *  Returns @c a.max_size() if that expression is well-formed,
 590        *  otherwise returns @c %numeric_limits<size_type>::max()
 591       */
 592       static size_type max_size(const _Alloc& __a)
 593       { return _S_max_size(__a); }
 594
 595       /**
 596        *  @brief  Obtain an allocator to use when copying a container.
 597        *  @param  rhs  An allocator.
 598        *  @return @c rhs.select_on_container_copy_construction() or @a rhs
 599        *
 600        *  Returns @c rhs.select_on_container_copy_construction() if that
 601        *  expression is well-formed, otherwise returns @a rhs
 602       */
 603       static _Alloc
 604       select_on_container_copy_construction(const _Alloc& __rhs)
 605       { return _S_select(__rhs); }
 606     };
 607
 608 #endif
 609
 610 _GLIBCXX_END_NAMESPACE_VERSION
 611 } // namespace std
 612
 613 #endif