boost/pool/pool_alloc.hpp

   1 // Copyright (C) 2000, 2001 Stephen Cleary
   2 // Copyright (C) 2010 Paul A. Bristow added Doxygen comments.
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See
   5 // accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //
   8 // See http://www.boost.org for updates, documentation, and revision history.
   9
  10 #ifndef BOOST_POOL_ALLOC_HPP
  11 #define BOOST_POOL_ALLOC_HPP
  12
  13 /*!
  14   \file
  15   \brief C++ Standard Library compatible pool-based allocators.
  16   \details  This header provides two template types -
  17   \ref pool_allocator and \ref fast_pool_allocator -
  18   that can be used for fast and efficient memory allocation
  19   in conjunction with the C++ Standard Library containers.
  20
  21   These types both satisfy the Standard Allocator requirements [20.1.5]
  22   and the additional requirements in [20.1.5/4],
  23   so they can be used with either Standard or user-supplied containers.
  24
  25   In addition, the fast_pool_allocator also provides an additional allocation
  26   and an additional deallocation function:
  27
  28 <table>
  29 <tr><th>Expression</th><th>Return Type</th><th>Semantic Equivalence<th></tr>
  30 <tr><td><tt>PoolAlloc::allocate()</tt></td><td><tt>T *</tt></td><td><tt>PoolAlloc::allocate(1)</tt></tr>
  31 <tr><td><tt>PoolAlloc::deallocate(p)</tt></td><td>void</tt></td><td><tt>PoolAlloc::deallocate(p, 1)</tt></tr>
  32 </table>
  33
  34 The typedef user_allocator publishes the value of the UserAllocator template parameter.
  35
  36 <b>Notes</b>
  37
  38 If the allocation functions run out of memory, they will throw <tt>std::bad_alloc</tt>.
  39
  40 The underlying Pool type used by the allocators is accessible through the Singleton Pool Interface.
  41 The identifying tag used for pool_allocator is pool_allocator_tag,
  42 and the tag used for fast_pool_allocator is fast_pool_allocator_tag.
  43 All template parameters of the allocators (including implementation-specific ones)
  44 determine the type of the underlying Pool,
  45 with the exception of the first parameter T, whose size is used instead.
  46
  47 Since the size of T is used to determine the type of the underlying Pool,
  48 each allocator for different types of the same size will share the same underlying pool.
  49 The tag class prevents pools from being shared between pool_allocator and fast_pool_allocator.
  50 For example, on a system where
  51 <tt>sizeof(int) == sizeof(void *)</tt>, <tt>pool_allocator<int></tt> and <tt>pool_allocator<void *></tt>
  52 will both allocate/deallocate from/to the same pool.
  53
  54 If there is only one thread running before main() starts and after main() ends,
  55 then both allocators are completely thread-safe.
  56
  57 <b>Compiler and STL Notes</b>
  58
  59 A number of common STL libraries contain bugs in their using of allocators.
  60 Specifically, they pass null pointers to the deallocate function,
  61 which is explicitly forbidden by the Standard [20.1.5 Table 32].
  62 PoolAlloc will work around these libraries if it detects them;
  63 currently, workarounds are in place for:
  64 Borland C++ (Builder and command-line compiler)
  65 with default (RogueWave) library, ver. 5 and earlier,
  66 STLport (with any compiler), ver. 4.0 and earlier.
  67 */
  68
  69 // std::numeric_limits
  70 #include <boost/limits.hpp>
  71 // new, std::bad_alloc
  72 #include <new>
  73
  74 #include <boost/throw_exception.hpp>
  75 #include <boost/pool/poolfwd.hpp>
  76
  77 // boost::singleton_pool
  78 #include <boost/pool/singleton_pool.hpp>
  79
  80 #include <boost/detail/workaround.hpp>
  81
  82 // C++11 features detection
  83 #include <boost/config.hpp>
  84
  85 // std::forward
  86 #ifdef BOOST_HAS_VARIADIC_TMPL
  87 #include <utility>
  88 #endif
  89
  90 #ifdef BOOST_POOL_INSTRUMENT
  91 #include <iostream>
  92 #include <iomanip>
  93 #endif
  94
  95 // The following code will be put into Boost.Config in a later revision
  96 #if defined(_RWSTD_VER) || defined(__SGI_STL_PORT) || \
  97     BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x582))
  98  #define BOOST_NO_PROPER_STL_DEALLOCATE
  99 #endif
 100
 101 namespace boost {
 102
 103 #ifdef BOOST_POOL_INSTRUMENT
 104
 105 template <bool b>
 106 struct debug_info
 107 {
 108    static unsigned allocated;
 109 };
 110
 111 template <bool b>
 112 unsigned debug_info<b>::allocated = 0;
 113
 114 #endif
 115
 116  //! Simple tag type used by pool_allocator as an argument to the
 117  //! underlying singleton_pool.
 118  struct pool_allocator_tag
 119 {
 120 };
 121
 122 /*!  \brief A C++ Standard Library conforming allocator, based on an underlying pool.
 123
 124   Template parameters for pool_allocator are defined as follows:
 125
 126   <b>T</b> Type of object to allocate/deallocate.
 127
 128   <b>UserAllocator</B>. Defines the method that the underlying Pool will use to allocate memory from the system. See
 129   <a href="boost_pool/pool/pooling.html#boost_pool.pool.pooling.user_allocator">User Allocators</a> for details.
 130
 131   <b>Mutex</b> Allows the user to determine the type of synchronization to be used on the underlying singleton_pool.
 132
 133   <b>NextSize</b> The value of this parameter is passed to the underlying singleton_pool when it is created.
 134
 135   <b>MaxSize</b> Limit on the maximum size used.
 136
 137   \attention
 138   The underlying singleton_pool used by the this allocator
 139   constructs a pool instance that
 140   <b>is never freed</b>.  This means that memory allocated
 141   by the allocator can be still used after main() has
 142   completed, but may mean that some memory checking programs
 143   will complain about leaks.
 144
 145
 146   */
 147 template <typename T,
 148     typename UserAllocator,
 149     typename Mutex,
 150     unsigned NextSize,
 151     unsigned MaxSize >
 152 class pool_allocator
 153 {
 154   public:
 155     typedef T value_type;  //!< value_type of template parameter T.
 156     typedef UserAllocator user_allocator;  //!< allocator that defines the method that the underlying Pool will use to allocate memory from the system.
 157     typedef Mutex mutex; //!< typedef mutex publishes the value of the template parameter Mutex.
 158     BOOST_STATIC_CONSTANT(unsigned, next_size = NextSize); //!< next_size publishes the values of the template parameter NextSize.
 159
 160     typedef value_type * pointer; //!<
 161     typedef const value_type * const_pointer;
 162     typedef value_type & reference;
 163     typedef const value_type & const_reference;
 164     typedef typename pool<UserAllocator>::size_type size_type;
 165     typedef typename pool<UserAllocator>::difference_type difference_type;
 166
 167     //! \brief Nested class rebind allows for transformation from
 168     //! pool_allocator<T> to pool_allocator<U>.
 169     //!
 170     //! Nested class rebind allows for transformation from
 171     //! pool_allocator<T> to pool_allocator<U> via the member
 172     //! typedef other.
 173     template <typename U>
 174     struct rebind
 175     { //
 176       typedef pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other;
 177     };
 178
 179   public:
 180     pool_allocator()
 181     { /*! Results in default construction of the underlying singleton_pool IFF an
 182        instance of this allocator is constructed during global initialization (
 183          required to ensure construction of singleton_pool IFF an
 184          instance of this allocator is constructed during global
 185          initialization. See ticket #2359 for a complete explanation at
 186          http://svn.boost.org/trac/boost/ticket/2359) .
 187        */
 188       singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex,
 189                      NextSize, MaxSize>::is_from(0);
 190     }
 191
 192     // default copy constructor.
 193
 194     // default assignment operator.
 195
 196     // not explicit, mimicking std::allocator [20.4.1]
 197     template <typename U>
 198     pool_allocator(const pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> &)
 199     { /*! Results in the default construction of the underlying singleton_pool, this
 200          is required to ensure construction of singleton_pool IFF an
 201          instance of this allocator is constructed during global
 202          initialization. See ticket #2359 for a complete explanation
 203          at http://svn.boost.org/trac/boost/ticket/2359 .
 204        */
 205       singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex,
 206                      NextSize, MaxSize>::is_from(0);
 207     }
 208
 209     // default destructor
 210
 211     static pointer address(reference r)
 212     { return &r; }
 213     static const_pointer address(const_reference s)
 214     { return &s; }
 215     static size_type max_size()
 216     { return (std::numeric_limits<size_type>::max)(); }
 217
 218 #if defined(BOOST_HAS_VARIADIC_TMPL) && defined(BOOST_HAS_RVALUE_REFS)
 219     template <typename U, typename... Args>
 220     static void construct(U* ptr, Args&&... args)
 221     { new (ptr) U(std::forward<Args>(args)...); }
 222 #else
 223     static void construct(const pointer ptr, const value_type & t)
 224     { new (ptr) T(t); }
 225 #endif
 226
 227     static void destroy(const pointer ptr)
 228     {
 229       ptr->~T();
 230       (void) ptr; // avoid unused variable warning.
 231     }
 232
 233     bool operator==(const pool_allocator &) const
 234     { return true; }
 235     bool operator!=(const pool_allocator &) const
 236     { return false; }
 237
 238     static pointer allocate(const size_type n)
 239     {
 240 #ifdef BOOST_POOL_INSTRUMENT
 241        debug_info<true>::allocated += n * sizeof(T);
 242        std::cout << "Allocating " << n << " * " << sizeof(T) << " bytes...\n"
 243           "Total allocated is now " << debug_info<true>::allocated << std::endl;
 244 #endif
 245       const pointer ret = static_cast<pointer>(
 246           singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex,
 247               NextSize, MaxSize>::ordered_malloc(n) );
 248       if ((ret == 0) && n)
 249         boost::throw_exception(std::bad_alloc());
 250       return ret;
 251     }
 252     static pointer allocate(const size_type n, const void * const)
 253     { //! allocate n bytes
 254     //! \param n bytes to allocate.
 255     //! \param unused.
 256       return allocate(n);
 257     }
 258     static void deallocate(const pointer ptr, const size_type n)
 259     {  //! Deallocate n bytes from ptr
 260        //! \param ptr location to deallocate from.
 261        //! \param n number of bytes to deallocate.
 262 #ifdef BOOST_POOL_INSTRUMENT
 263        debug_info<true>::allocated -= n * sizeof(T);
 264        std::cout << "Deallocating " << n << " * " << sizeof(T) << " bytes...\n"
 265           "Total allocated is now " << debug_info<true>::allocated << std::endl;
 266 #endif
 267 #ifdef BOOST_NO_PROPER_STL_DEALLOCATE
 268       if (ptr == 0 || n == 0)
 269         return;
 270 #endif
 271       singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex,
 272           NextSize, MaxSize>::ordered_free(ptr, n);
 273     }
 274 };
 275
 276 /*! \brief Specialization of pool_allocator<void>.
 277
 278 Specialization of pool_allocator for type void: required by the standard to make this a conforming allocator type.
 279 */
 280 template<
 281     typename UserAllocator,
 282     typename Mutex,
 283     unsigned NextSize,
 284     unsigned MaxSize>
 285 class pool_allocator<void, UserAllocator, Mutex, NextSize, MaxSize>
 286 {
 287 public:
 288     typedef void*       pointer;
 289     typedef const void* const_pointer;
 290     typedef void        value_type;
 291     //! \brief Nested class rebind allows for transformation from
 292     //! pool_allocator<T> to pool_allocator<U>.
 293     //!
 294     //! Nested class rebind allows for transformation from
 295     //! pool_allocator<T> to pool_allocator<U> via the member
 296     //! typedef other.
 297     template <class U>
 298     struct rebind
 299     {
 300        typedef pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other;
 301     };
 302 };
 303
 304 //! Simple tag type used by fast_pool_allocator as a template parameter to the underlying singleton_pool.
 305 struct fast_pool_allocator_tag
 306 {
 307 };
 308
 309  /*! \brief A C++ Standard Library conforming allocator geared towards allocating single chunks.
 310
 311   While class template <tt>pool_allocator</tt> is a more general-purpose solution geared towards
 312   efficiently servicing requests for any number of contiguous chunks,
 313   <tt>fast_pool_allocator</tt> is also a general-purpose solution,
 314   but is geared towards efficiently servicing requests for one chunk at a time;
 315   it will work for contiguous chunks, but not as well as <tt>pool_allocator</tt>.
 316
 317   If you are seriously concerned about performance,
 318   use <tt>fast_pool_allocator</tt> when dealing with containers such as <tt>std::list</tt>,
 319   and use <tt>pool_allocator</tt> when dealing with containers such as <tt>std::vector</tt>.
 320
 321   The template parameters are defined as follows:
 322
 323   <b>T</b> Type of object to allocate/deallocate.
 324
 325   <b>UserAllocator</b>. Defines the method that the underlying Pool will use to allocate memory from the system.
 326   See <a href="boost_pool/pool/pooling.html#boost_pool.pool.pooling.user_allocator">User Allocators</a> for details.
 327
 328   <b>Mutex</b> Allows the user to determine the type of synchronization to be used on the underlying <tt>singleton_pool</tt>.
 329
 330   <b>NextSize</b> The value of this parameter is passed to the underlying Pool when it is created.
 331
 332   <b>MaxSize</b> Limit on the maximum size used.
 333
 334    \attention
 335   The underlying singleton_pool used by the this allocator
 336   constructs a pool instance that
 337   <b>is never freed</b>.  This means that memory allocated
 338   by the allocator can be still used after main() has
 339   completed, but may mean that some memory checking programs
 340   will complain about leaks.
 341
 342  */
 343
 344 template <typename T,
 345     typename UserAllocator,
 346     typename Mutex,
 347     unsigned NextSize,
 348     unsigned MaxSize >
 349 class fast_pool_allocator
 350 {
 351   public:
 352     typedef T value_type;
 353     typedef UserAllocator user_allocator;
 354     typedef Mutex mutex;
 355     BOOST_STATIC_CONSTANT(unsigned, next_size = NextSize);
 356
 357     typedef value_type * pointer;
 358     typedef const value_type * const_pointer;
 359     typedef value_type & reference;
 360     typedef const value_type & const_reference;
 361     typedef typename pool<UserAllocator>::size_type size_type;
 362     typedef typename pool<UserAllocator>::difference_type difference_type;
 363
 364     //! \brief Nested class rebind allows for transformation from
 365     //! fast_pool_allocator<T> to fast_pool_allocator<U>.
 366     //!
 367     //! Nested class rebind allows for transformation from
 368     //! fast_pool_allocator<T> to fast_pool_allocator<U> via the member
 369     //! typedef other.
 370     template <typename U>
 371     struct rebind
 372     {
 373       typedef fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other;
 374     };
 375
 376   public:
 377     fast_pool_allocator()
 378     {
 379       //! Ensures construction of the underlying singleton_pool IFF an
 380       //! instance of this allocator is constructed during global
 381       //! initialization. See ticket #2359 for a complete explanation
 382       //! at http://svn.boost.org/trac/boost/ticket/2359 .
 383       singleton_pool<fast_pool_allocator_tag, sizeof(T),
 384                      UserAllocator, Mutex, NextSize, MaxSize>::is_from(0);
 385     }
 386
 387     // Default copy constructor used.
 388
 389     // Default assignment operator used.
 390
 391     // Not explicit, mimicking std::allocator [20.4.1]
 392     template <typename U>
 393     fast_pool_allocator(
 394         const fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> &)
 395     {
 396       //! Ensures construction of the underlying singleton_pool IFF an
 397       //! instance of this allocator is constructed during global
 398       //! initialization. See ticket #2359 for a complete explanation
 399       //! at http://svn.boost.org/trac/boost/ticket/2359 .
 400       singleton_pool<fast_pool_allocator_tag, sizeof(T),
 401                      UserAllocator, Mutex, NextSize, MaxSize>::is_from(0);
 402     }
 403
 404     // Default destructor used.
 405
 406     static pointer address(reference r)
 407     {
 408       return &r;
 409     }
 410     static const_pointer address(const_reference s)
 411     { return &s; }
 412     static size_type max_size()
 413     { return (std::numeric_limits<size_type>::max)(); }
 414
 415 #if defined(BOOST_HAS_VARIADIC_TMPL) && defined(BOOST_HAS_RVALUE_REFS)
 416     template <typename U, typename... Args>
 417     void construct(U* ptr, Args&&... args)
 418     { new (ptr) U(std::forward<Args>(args)...); }
 419 #else
 420     void construct(const pointer ptr, const value_type & t)
 421     { new (ptr) T(t); }
 422 #endif
 423
 424     void destroy(const pointer ptr)
 425     { //! Destroy ptr using destructor.
 426       ptr->~T();
 427       (void) ptr; // Avoid unused variable warning.
 428     }
 429
 430     bool operator==(const fast_pool_allocator &) const
 431     { return true; }
 432     bool operator!=(const fast_pool_allocator &) const
 433     { return false; }
 434
 435     static pointer allocate(const size_type n)
 436     {
 437       const pointer ret = (n == 1) ?
 438           static_cast<pointer>(
 439               (singleton_pool<fast_pool_allocator_tag, sizeof(T),
 440                   UserAllocator, Mutex, NextSize, MaxSize>::malloc)() ) :
 441           static_cast<pointer>(
 442               singleton_pool<fast_pool_allocator_tag, sizeof(T),
 443                   UserAllocator, Mutex, NextSize, MaxSize>::ordered_malloc(n) );
 444       if (ret == 0)
 445         boost::throw_exception(std::bad_alloc());
 446       return ret;
 447     }
 448     static pointer allocate(const size_type n, const void * const)
 449     { //! Allocate memory .
 450       return allocate(n);
 451     }
 452     static pointer allocate()
 453     { //! Allocate memory.
 454       const pointer ret = static_cast<pointer>(
 455           (singleton_pool<fast_pool_allocator_tag, sizeof(T),
 456               UserAllocator, Mutex, NextSize, MaxSize>::malloc)() );
 457       if (ret == 0)
 458         boost::throw_exception(std::bad_alloc());
 459       return ret;
 460     }
 461     static void deallocate(const pointer ptr, const size_type n)
 462     { //! Deallocate memory.
 463
 464 #ifdef BOOST_NO_PROPER_STL_DEALLOCATE
 465       if (ptr == 0 || n == 0)
 466         return;
 467 #endif
 468       if (n == 1)
 469         (singleton_pool<fast_pool_allocator_tag, sizeof(T),
 470             UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr);
 471       else
 472         (singleton_pool<fast_pool_allocator_tag, sizeof(T),
 473             UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr, n);
 474     }
 475     static void deallocate(const pointer ptr)
 476     { //! deallocate/free
 477       (singleton_pool<fast_pool_allocator_tag, sizeof(T),
 478           UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr);
 479     }
 480 };
 481
 482 /*!  \brief Specialization of fast_pool_allocator<void>.
 483
 484 Specialization of fast_pool_allocator<void> required to make the allocator standard-conforming.
 485 */
 486 template<
 487     typename UserAllocator,
 488     typename Mutex,
 489     unsigned NextSize,
 490     unsigned MaxSize >
 491 class fast_pool_allocator<void, UserAllocator, Mutex, NextSize, MaxSize>
 492 {
 493 public:
 494     typedef void*       pointer;
 495     typedef const void* const_pointer;
 496     typedef void        value_type;
 497
 498     //! \brief Nested class rebind allows for transformation from
 499     //! fast_pool_allocator<T> to fast_pool_allocator<U>.
 500     //!
 501     //! Nested class rebind allows for transformation from
 502     //! fast_pool_allocator<T> to fast_pool_allocator<U> via the member
 503     //! typedef other.
 504     template <class U> struct rebind
 505     {
 506         typedef fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other;
 507     };
 508 };
 509
 510 } // namespace boost
 511
 512 #endif