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 #ifdef BOOST_POOL_INSTRUMENT 83 #include <iostream> 84 #include <iomanip> 85 #endif 86 87 // The following code will be put into Boost.Config in a later revision 88 #if defined(_RWSTD_VER) || defined(__SGI_STL_PORT) || \ 89 BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x582)) 90 #define BOOST_NO_PROPER_STL_DEALLOCATE 91 #endif 92 93 namespace boost { 94 95 #ifdef BOOST_POOL_INSTRUMENT 96 97 template <bool b> 98 struct debug_info 99 { 100 static unsigned allocated; 101 }; 102 103 template <bool b> 104 unsigned debug_info<b>::allocated = 0; 105 106 #endif 107 108 //! Simple tag type used by pool_allocator as an argument to the 109 //! underlying singleton_pool. 110 struct pool_allocator_tag 111 { 112 }; 113 114 /*! \brief A C++ Standard Library conforming allocator, based on an underlying pool. 115 116 Template parameters for pool_allocator are defined as follows: 117 118 <b>T</b> Type of object to allocate/deallocate. 119 120 <b>UserAllocator</B>. Defines the method that the underlying Pool will use to allocate memory from the system. See 121 <a href="boost_pool/pool/pooling.html#boost_pool.pool.pooling.user_allocator">User Allocators</a> for details. 122 123 <b>Mutex</b> Allows the user to determine the type of synchronization to be used on the underlying singleton_pool. 124 125 <b>NextSize</b> The value of this parameter is passed to the underlying singleton_pool when it is created. 126 127 <b>MaxSize</b> Limit on the maximum size used. 128 129 \attention 130 The underlying singleton_pool used by the this allocator 131 constructs a pool instance that 132 <b>is never freed</b>. This means that memory allocated 133 by the allocator can be still used after main() has 134 completed, but may mean that some memory checking programs 135 will complain about leaks. 136 137 138 */ 139 template <typename T, 140 typename UserAllocator, 141 typename Mutex, 142 unsigned NextSize, 143 unsigned MaxSize > 144 class pool_allocator 145 { 146 public: 147 typedef T value_type; //!< value_type of template parameter T. 148 typedef UserAllocator user_allocator; //!< allocator that defines the method that the underlying Pool will use to allocate memory from the system. 149 typedef Mutex mutex; //!< typedef mutex publishes the value of the template parameter Mutex. 150 BOOST_STATIC_CONSTANT(unsigned, next_size = NextSize); //!< next_size publishes the values of the template parameter NextSize. 151 152 typedef value_type * pointer; //!< 153 typedef const value_type * const_pointer; 154 typedef value_type & reference; 155 typedef const value_type & const_reference; 156 typedef typename pool<UserAllocator>::size_type size_type; 157 typedef typename pool<UserAllocator>::difference_type difference_type; 158 159 //! \brief Nested class rebind allows for transformation from 160 //! pool_allocator<T> to pool_allocator<U>. 161 //! 162 //! Nested class rebind allows for transformation from 163 //! pool_allocator<T> to pool_allocator<U> via the member 164 //! typedef other. 165 template <typename U> 166 struct rebind 167 { // 168 typedef pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other; 169 }; 170 171 public: pool_allocator()172 pool_allocator() 173 { /*! Results in default construction of the underlying singleton_pool IFF an 174 instance of this allocator is constructed during global initialization ( 175 required to ensure construction of singleton_pool IFF an 176 instance of this allocator is constructed during global 177 initialization. See ticket #2359 for a complete explanation at 178 http://svn.boost.org/trac/boost/ticket/2359) . 179 */ 180 singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex, 181 NextSize, MaxSize>::is_from(0); 182 } 183 184 // default copy constructor. 185 186 // default assignment operator. 187 188 // not explicit, mimicking std::allocator [20.4.1] 189 template <typename U> pool_allocator(const pool_allocator<U,UserAllocator,Mutex,NextSize,MaxSize> &)190 pool_allocator(const pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> &) 191 { /*! Results in the default construction of the underlying singleton_pool, this 192 is required to ensure construction of singleton_pool IFF an 193 instance of this allocator is constructed during global 194 initialization. See ticket #2359 for a complete explanation 195 at http://svn.boost.org/trac/boost/ticket/2359 . 196 */ 197 singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex, 198 NextSize, MaxSize>::is_from(0); 199 } 200 201 // default destructor 202 address(reference r)203 static pointer address(reference r) 204 { return &r; } address(const_reference s)205 static const_pointer address(const_reference s) 206 { return &s; } max_size()207 static size_type max_size() 208 { return (std::numeric_limits<size_type>::max)(); } construct(const pointer ptr,const value_type & t)209 static void construct(const pointer ptr, const value_type & t) 210 { new (ptr) T(t); } destroy(const pointer ptr)211 static void destroy(const pointer ptr) 212 { 213 ptr->~T(); 214 (void) ptr; // avoid unused variable warning. 215 } 216 operator ==(const pool_allocator &) const217 bool operator==(const pool_allocator &) const 218 { return true; } operator !=(const pool_allocator &) const219 bool operator!=(const pool_allocator &) const 220 { return false; } 221 allocate(const size_type n)222 static pointer allocate(const size_type n) 223 { 224 #ifdef BOOST_POOL_INSTRUMENT 225 debug_info<true>::allocated += n * sizeof(T); 226 std::cout << "Allocating " << n << " * " << sizeof(T) << " bytes...\n" 227 "Total allocated is now " << debug_info<true>::allocated << std::endl; 228 #endif 229 const pointer ret = static_cast<pointer>( 230 singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex, 231 NextSize, MaxSize>::ordered_malloc(n) ); 232 if ((ret == 0) && n) 233 boost::throw_exception(std::bad_alloc()); 234 return ret; 235 } allocate(const size_type n,const void * const)236 static pointer allocate(const size_type n, const void * const) 237 { //! allocate n bytes 238 //! \param n bytes to allocate. 239 //! \param unused. 240 return allocate(n); 241 } deallocate(const pointer ptr,const size_type n)242 static void deallocate(const pointer ptr, const size_type n) 243 { //! Deallocate n bytes from ptr 244 //! \param ptr location to deallocate from. 245 //! \param n number of bytes to deallocate. 246 #ifdef BOOST_POOL_INSTRUMENT 247 debug_info<true>::allocated -= n * sizeof(T); 248 std::cout << "Deallocating " << n << " * " << sizeof(T) << " bytes...\n" 249 "Total allocated is now " << debug_info<true>::allocated << std::endl; 250 #endif 251 #ifdef BOOST_NO_PROPER_STL_DEALLOCATE 252 if (ptr == 0 || n == 0) 253 return; 254 #endif 255 singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex, 256 NextSize, MaxSize>::ordered_free(ptr, n); 257 } 258 }; 259 260 /*! \brief Specialization of pool_allocator<void>. 261 262 Specialization of pool_allocator for type void: required by the standard to make this a conforming allocator type. 263 */ 264 template< 265 typename UserAllocator, 266 typename Mutex, 267 unsigned NextSize, 268 unsigned MaxSize> 269 class pool_allocator<void, UserAllocator, Mutex, NextSize, MaxSize> 270 { 271 public: 272 typedef void* pointer; 273 typedef const void* const_pointer; 274 typedef void value_type; 275 //! \brief Nested class rebind allows for transformation from 276 //! pool_allocator<T> to pool_allocator<U>. 277 //! 278 //! Nested class rebind allows for transformation from 279 //! pool_allocator<T> to pool_allocator<U> via the member 280 //! typedef other. 281 template <class U> 282 struct rebind 283 { 284 typedef pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other; 285 }; 286 }; 287 288 //! Simple tag type used by fast_pool_allocator as a template parameter to the underlying singleton_pool. 289 struct fast_pool_allocator_tag 290 { 291 }; 292 293 /*! \brief A C++ Standard Library conforming allocator geared towards allocating single chunks. 294 295 While class template <tt>pool_allocator</tt> is a more general-purpose solution geared towards 296 efficiently servicing requests for any number of contiguous chunks, 297 <tt>fast_pool_allocator</tt> is also a general-purpose solution, 298 but is geared towards efficiently servicing requests for one chunk at a time; 299 it will work for contiguous chunks, but not as well as <tt>pool_allocator</tt>. 300 301 If you are seriously concerned about performance, 302 use <tt>fast_pool_allocator</tt> when dealing with containers such as <tt>std::list</tt>, 303 and use <tt>pool_allocator</tt> when dealing with containers such as <tt>std::vector</tt>. 304 305 The template parameters are defined as follows: 306 307 <b>T</b> Type of object to allocate/deallocate. 308 309 <b>UserAllocator</b>. Defines the method that the underlying Pool will use to allocate memory from the system. 310 See <a href="boost_pool/pool/pooling.html#boost_pool.pool.pooling.user_allocator">User Allocators</a> for details. 311 312 <b>Mutex</b> Allows the user to determine the type of synchronization to be used on the underlying <tt>singleton_pool</tt>. 313 314 <b>NextSize</b> The value of this parameter is passed to the underlying Pool when it is created. 315 316 <b>MaxSize</b> Limit on the maximum size used. 317 318 \attention 319 The underlying singleton_pool used by the this allocator 320 constructs a pool instance that 321 <b>is never freed</b>. This means that memory allocated 322 by the allocator can be still used after main() has 323 completed, but may mean that some memory checking programs 324 will complain about leaks. 325 326 */ 327 328 template <typename T, 329 typename UserAllocator, 330 typename Mutex, 331 unsigned NextSize, 332 unsigned MaxSize > 333 class fast_pool_allocator 334 { 335 public: 336 typedef T value_type; 337 typedef UserAllocator user_allocator; 338 typedef Mutex mutex; 339 BOOST_STATIC_CONSTANT(unsigned, next_size = NextSize); 340 341 typedef value_type * pointer; 342 typedef const value_type * const_pointer; 343 typedef value_type & reference; 344 typedef const value_type & const_reference; 345 typedef typename pool<UserAllocator>::size_type size_type; 346 typedef typename pool<UserAllocator>::difference_type difference_type; 347 348 //! \brief Nested class rebind allows for transformation from 349 //! fast_pool_allocator<T> to fast_pool_allocator<U>. 350 //! 351 //! Nested class rebind allows for transformation from 352 //! fast_pool_allocator<T> to fast_pool_allocator<U> via the member 353 //! typedef other. 354 template <typename U> 355 struct rebind 356 { 357 typedef fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other; 358 }; 359 360 public: fast_pool_allocator()361 fast_pool_allocator() 362 { 363 //! Ensures construction of the underlying singleton_pool IFF an 364 //! instance of this allocator is constructed during global 365 //! initialization. See ticket #2359 for a complete explanation 366 //! at http://svn.boost.org/trac/boost/ticket/2359 . 367 singleton_pool<fast_pool_allocator_tag, sizeof(T), 368 UserAllocator, Mutex, NextSize, MaxSize>::is_from(0); 369 } 370 371 // Default copy constructor used. 372 373 // Default assignment operator used. 374 375 // Not explicit, mimicking std::allocator [20.4.1] 376 template <typename U> fast_pool_allocator(const fast_pool_allocator<U,UserAllocator,Mutex,NextSize,MaxSize> &)377 fast_pool_allocator( 378 const fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> &) 379 { 380 //! Ensures construction of the underlying singleton_pool IFF an 381 //! instance of this allocator is constructed during global 382 //! initialization. See ticket #2359 for a complete explanation 383 //! at http://svn.boost.org/trac/boost/ticket/2359 . 384 singleton_pool<fast_pool_allocator_tag, sizeof(T), 385 UserAllocator, Mutex, NextSize, MaxSize>::is_from(0); 386 } 387 388 // Default destructor used. 389 address(reference r)390 static pointer address(reference r) 391 { 392 return &r; 393 } address(const_reference s)394 static const_pointer address(const_reference s) 395 { return &s; } max_size()396 static size_type max_size() 397 { return (std::numeric_limits<size_type>::max)(); } construct(const pointer ptr,const value_type & t)398 void construct(const pointer ptr, const value_type & t) 399 { new (ptr) T(t); } destroy(const pointer ptr)400 void destroy(const pointer ptr) 401 { //! Destroy ptr using destructor. 402 ptr->~T(); 403 (void) ptr; // Avoid unused variable warning. 404 } 405 operator ==(const fast_pool_allocator &) const406 bool operator==(const fast_pool_allocator &) const 407 { return true; } operator !=(const fast_pool_allocator &) const408 bool operator!=(const fast_pool_allocator &) const 409 { return false; } 410 allocate(const size_type n)411 static pointer allocate(const size_type n) 412 { 413 const pointer ret = (n == 1) ? 414 static_cast<pointer>( 415 (singleton_pool<fast_pool_allocator_tag, sizeof(T), 416 UserAllocator, Mutex, NextSize, MaxSize>::malloc)() ) : 417 static_cast<pointer>( 418 singleton_pool<fast_pool_allocator_tag, sizeof(T), 419 UserAllocator, Mutex, NextSize, MaxSize>::ordered_malloc(n) ); 420 if (ret == 0) 421 boost::throw_exception(std::bad_alloc()); 422 return ret; 423 } allocate(const size_type n,const void * const)424 static pointer allocate(const size_type n, const void * const) 425 { //! Allocate memory . 426 return allocate(n); 427 } allocate()428 static pointer allocate() 429 { //! Allocate memory. 430 const pointer ret = static_cast<pointer>( 431 (singleton_pool<fast_pool_allocator_tag, sizeof(T), 432 UserAllocator, Mutex, NextSize, MaxSize>::malloc)() ); 433 if (ret == 0) 434 boost::throw_exception(std::bad_alloc()); 435 return ret; 436 } deallocate(const pointer ptr,const size_type n)437 static void deallocate(const pointer ptr, const size_type n) 438 { //! Deallocate memory. 439 440 #ifdef BOOST_NO_PROPER_STL_DEALLOCATE 441 if (ptr == 0 || n == 0) 442 return; 443 #endif 444 if (n == 1) 445 (singleton_pool<fast_pool_allocator_tag, sizeof(T), 446 UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr); 447 else 448 (singleton_pool<fast_pool_allocator_tag, sizeof(T), 449 UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr, n); 450 } deallocate(const pointer ptr)451 static void deallocate(const pointer ptr) 452 { //! deallocate/free 453 (singleton_pool<fast_pool_allocator_tag, sizeof(T), 454 UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr); 455 } 456 }; 457 458 /*! \brief Specialization of fast_pool_allocator<void>. 459 460 Specialization of fast_pool_allocator<void> required to make the allocator standard-conforming. 461 */ 462 template< 463 typename UserAllocator, 464 typename Mutex, 465 unsigned NextSize, 466 unsigned MaxSize > 467 class fast_pool_allocator<void, UserAllocator, Mutex, NextSize, MaxSize> 468 { 469 public: 470 typedef void* pointer; 471 typedef const void* const_pointer; 472 typedef void value_type; 473 474 //! \brief Nested class rebind allows for transformation from 475 //! fast_pool_allocator<T> to fast_pool_allocator<U>. 476 //! 477 //! Nested class rebind allows for transformation from 478 //! fast_pool_allocator<T> to fast_pool_allocator<U> via the member 479 //! typedef other. 480 template <class U> struct rebind 481 { 482 typedef fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other; 483 }; 484 }; 485 486 } // namespace boost 487 488 #endif 489