]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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: | |
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> | |
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 | ||
203 | static pointer address(reference r) | |
204 | { return &r; } | |
205 | static const_pointer address(const_reference s) | |
206 | { return &s; } | |
207 | static size_type max_size() | |
208 | { return (std::numeric_limits<size_type>::max)(); } | |
209 | static void construct(const pointer ptr, const value_type & t) | |
210 | { new (ptr) T(t); } | |
211 | static void destroy(const pointer ptr) | |
212 | { | |
213 | ptr->~T(); | |
214 | (void) ptr; // avoid unused variable warning. | |
215 | } | |
216 | ||
217 | bool operator==(const pool_allocator &) const | |
218 | { return true; } | |
219 | bool operator!=(const pool_allocator &) const | |
220 | { return false; } | |
221 | ||
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 | } | |
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 | } | |
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: | |
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> | |
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 | ||
390 | static pointer address(reference r) | |
391 | { | |
392 | return &r; | |
393 | } | |
394 | static const_pointer address(const_reference s) | |
395 | { return &s; } | |
396 | static size_type max_size() | |
397 | { return (std::numeric_limits<size_type>::max)(); } | |
398 | void construct(const pointer ptr, const value_type & t) | |
399 | { new (ptr) T(t); } | |
400 | void destroy(const pointer ptr) | |
401 | { //! Destroy ptr using destructor. | |
402 | ptr->~T(); | |
403 | (void) ptr; // Avoid unused variable warning. | |
404 | } | |
405 | ||
406 | bool operator==(const fast_pool_allocator &) const | |
407 | { return true; } | |
408 | bool operator!=(const fast_pool_allocator &) const | |
409 | { return false; } | |
410 | ||
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 | } | |
424 | static pointer allocate(const size_type n, const void * const) | |
425 | { //! Allocate memory . | |
426 | return allocate(n); | |
427 | } | |
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 | } | |
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 | } | |
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 |