Line data Source code
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 0 : 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 0 : 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 0 : 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 0 : 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 0 : static pointer allocate(const size_type n)
436 : {
437 0 : const pointer ret = (n == 1) ?
438 : static_cast<pointer>(
439 : (singleton_pool<fast_pool_allocator_tag, sizeof(T),
440 0 : UserAllocator, Mutex, NextSize, MaxSize>::malloc)() ) :
441 : static_cast<pointer>(
442 : singleton_pool<fast_pool_allocator_tag, sizeof(T),
443 0 : UserAllocator, Mutex, NextSize, MaxSize>::ordered_malloc(n) );
444 0 : if (ret == 0)
445 0 : boost::throw_exception(std::bad_alloc());
446 0 : 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 0 : 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 0 : 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
|