Line data Source code
1 : // Copyright (C) 2000, 2001 Stephen Cleary
2 : //
3 : // Distributed under the Boost Software License, Version 1.0. (See
4 : // accompanying file LICENSE_1_0.txt or copy at
5 : // http://www.boost.org/LICENSE_1_0.txt)
6 : //
7 : // See http://www.boost.org for updates, documentation, and revision history.
8 :
9 : #ifndef BOOST_POOL_HPP
10 : #define BOOST_POOL_HPP
11 :
12 : #include <boost/config.hpp> // for workarounds
13 :
14 : // std::less, std::less_equal, std::greater
15 : #include <functional>
16 : // new[], delete[], std::nothrow
17 : #include <new>
18 : // std::size_t, std::ptrdiff_t
19 : #include <cstddef>
20 : // std::malloc, std::free
21 : #include <cstdlib>
22 : // std::invalid_argument
23 : #include <exception>
24 : // std::max
25 : #include <algorithm>
26 :
27 : #include <boost/pool/poolfwd.hpp>
28 :
29 : // std::numeric_limits
30 : #include <boost/limits.hpp>
31 : // boost::integer::static_lcm
32 : #include <boost/integer/common_factor_ct.hpp>
33 : // boost::simple_segregated_storage
34 : #include <boost/pool/simple_segregated_storage.hpp>
35 : // boost::alignment_of
36 : #include <boost/type_traits/alignment_of.hpp>
37 : // BOOST_ASSERT
38 : #include <boost/assert.hpp>
39 :
40 : #ifdef BOOST_POOL_INSTRUMENT
41 : #include <iostream>
42 : #include <iomanip>
43 : #endif
44 : #ifdef BOOST_POOL_VALGRIND
45 : #include <set>
46 : #include <valgrind/memcheck.h>
47 : #endif
48 :
49 : #ifdef BOOST_NO_STDC_NAMESPACE
50 : namespace std { using ::malloc; using ::free; }
51 : #endif
52 :
53 : // There are a few places in this file where the expression "this->m" is used.
54 : // This expression is used to force instantiation-time name lookup, which I am
55 : // informed is required for strict Standard compliance. It's only necessary
56 : // if "m" is a member of a base class that is dependent on a template
57 : // parameter.
58 : // Thanks to Jens Maurer for pointing this out!
59 :
60 : /*!
61 : \file
62 : \brief Provides class \ref pool: a fast memory allocator that guarantees proper alignment of all allocated chunks,
63 : and which extends and generalizes the framework provided by the simple segregated storage solution.
64 : Also provides two UserAllocator classes which can be used in conjuction with \ref pool.
65 : */
66 :
67 : /*!
68 : \mainpage Boost.Pool Memory Allocation Scheme
69 :
70 : \section intro_sec Introduction
71 :
72 : Pool allocation is a memory allocation scheme that is very fast, but limited in its usage.
73 :
74 : This Doxygen-style documentation is complementary to the
75 : full Quickbook-generated html and pdf documentation at www.boost.org.
76 :
77 : This page generated from file pool.hpp.
78 :
79 : */
80 :
81 : #ifdef BOOST_MSVC
82 : #pragma warning(push)
83 : #pragma warning(disable:4127) // Conditional expression is constant
84 : #endif
85 :
86 : namespace boost
87 : {
88 :
89 : //! \brief Allocator used as the default template parameter for
90 : //! a <a href="boost_pool/pool/pooling.html#boost_pool.pool.pooling.user_allocator">UserAllocator</a>
91 : //! template parameter. Uses new and delete.
92 : struct default_user_allocator_new_delete
93 : {
94 : typedef std::size_t size_type; //!< An unsigned integral type that can represent the size of the largest object to be allocated.
95 : typedef std::ptrdiff_t difference_type; //!< A signed integral type that can represent the difference of any two pointers.
96 :
97 : static char * malloc BOOST_PREVENT_MACRO_SUBSTITUTION(const size_type bytes)
98 : { //! Attempts to allocate n bytes from the system. Returns 0 if out-of-memory
99 : return new (std::nothrow) char[bytes];
100 : }
101 : static void free BOOST_PREVENT_MACRO_SUBSTITUTION(char * const block)
102 : { //! Attempts to de-allocate block.
103 : //! \pre Block must have been previously returned from a call to UserAllocator::malloc.
104 : delete [] block;
105 : }
106 : };
107 :
108 : //! \brief <a href="boost_pool/pool/pooling.html#boost_pool.pool.pooling.user_allocator">UserAllocator</a>
109 : //! used as template parameter for \ref pool and \ref object_pool.
110 : //! Uses malloc and free internally.
111 : struct default_user_allocator_malloc_free
112 : {
113 : typedef std::size_t size_type; //!< An unsigned integral type that can represent the size of the largest object to be allocated.
114 : typedef std::ptrdiff_t difference_type; //!< A signed integral type that can represent the difference of any two pointers.
115 :
116 : static char * malloc BOOST_PREVENT_MACRO_SUBSTITUTION(const size_type bytes)
117 : { return static_cast<char *>((std::malloc)(bytes)); }
118 : static void free BOOST_PREVENT_MACRO_SUBSTITUTION(char * const block)
119 : { (std::free)(block); }
120 : };
121 :
122 : namespace details
123 : { //! Implemention only.
124 :
125 : template <typename SizeType>
126 : class PODptr
127 : { //! PODptr is a class that pretends to be a "pointer" to different class types
128 : //! that don't really exist. It provides member functions to access the "data"
129 : //! of the "object" it points to. Since these "class" types are of variable
130 : //! size, and contains some information at the *end* of its memory
131 : //! (for alignment reasons),
132 : //! PODptr must contain the size of this "class" as well as the pointer to this "object".
133 :
134 : /*! \details A PODptr holds the location and size of a memory block allocated from the system.
135 : Each memory block is split logically into three sections:
136 :
137 : <b>Chunk area</b>. This section may be different sizes. PODptr does not care what the size of the chunks is,
138 : but it does care (and keep track of) the total size of the chunk area.
139 :
140 : <b>Next pointer</b>. This section is always the same size for a given SizeType. It holds a pointer
141 : to the location of the next memory block in the memory block list, or 0 if there is no such block.
142 :
143 : <b>Next size</b>. This section is always the same size for a given SizeType. It holds the size of the
144 : next memory block in the memory block list.
145 :
146 : The PODptr class just provides cleaner ways of dealing with raw memory blocks.
147 :
148 : A PODptr object is either valid or invalid. An invalid PODptr is analogous to a null pointer.
149 : The default constructor for PODptr will result in an invalid object.
150 : Calling the member function invalidate will result in that object becoming invalid.
151 : The member function valid can be used to test for validity.
152 : */
153 : public:
154 : typedef SizeType size_type;
155 :
156 : private:
157 : char * ptr;
158 : size_type sz;
159 :
160 40 : char * ptr_next_size() const
161 : {
162 40 : return (ptr + sz - sizeof(size_type));
163 : }
164 20 : char * ptr_next_ptr() const
165 : {
166 20 : return (ptr_next_size() -
167 : integer::static_lcm<sizeof(size_type), sizeof(void *)>::value);
168 : }
169 :
170 : public:
171 330 : PODptr(char * const nptr, const size_type nsize)
172 165 : :ptr(nptr), sz(nsize)
173 165 : {
174 : //! A PODptr may be created to point to a memory block by passing
175 : //! the address and size of that memory block into the constructor.
176 : //! A PODptr constructed in this way is valid.
177 330 : }
178 : PODptr()
179 : : ptr(0), sz(0)
180 : { //! default constructor for PODptr will result in an invalid object.
181 : }
182 :
183 165 : bool valid() const
184 : { //! A PODptr object is either valid or invalid.
185 : //! An invalid PODptr is analogous to a null pointer.
186 : //! \returns true if PODptr is valid, false if invalid.
187 165 : return (begin() != 0);
188 : }
189 10 : void invalidate()
190 : { //! Make object invalid.
191 10 : begin() = 0;
192 10 : }
193 20 : char * & begin()
194 : { //! Each PODptr keeps the address and size of its memory block.
195 : //! \returns The address of its memory block.
196 20 : return ptr;
197 : }
198 195 : char * begin() const
199 : { //! Each PODptr keeps the address and size of its memory block.
200 : //! \return The address of its memory block.
201 195 : return ptr;
202 : }
203 : char * end() const
204 : { //! \returns begin() plus element_size (a 'past the end' value).
205 : return ptr_next_ptr();
206 : }
207 10 : size_type total_size() const
208 : { //! Each PODptr keeps the address and size of its memory block.
209 : //! The address may be read or written by the member functions begin.
210 : //! The size of the memory block may only be read,
211 : //! \returns size of the memory block.
212 10 : return sz;
213 : }
214 10 : size_type element_size() const
215 : { //! \returns size of element pointer area.
216 10 : return static_cast<size_type>(sz - sizeof(size_type) -
217 : integer::static_lcm<sizeof(size_type), sizeof(void *)>::value);
218 : }
219 :
220 20 : size_type & next_size() const
221 : { //!
222 : //! \returns next_size.
223 20 : return *(static_cast<size_type *>(static_cast<void*>((ptr_next_size()))));
224 : }
225 20 : char * & next_ptr() const
226 : { //! \returns pointer to next pointer area.
227 20 : return *(static_cast<char **>(static_cast<void*>(ptr_next_ptr())));
228 : }
229 :
230 10 : PODptr next() const
231 : { //! \returns next PODptr.
232 10 : return PODptr<size_type>(next_ptr(), next_size());
233 : }
234 10 : void next(const PODptr & arg) const
235 : { //! Sets next PODptr.
236 10 : next_ptr() = arg.begin();
237 10 : next_size() = arg.total_size();
238 10 : }
239 : }; // class PODptr
240 : } // namespace details
241 :
242 : #ifndef BOOST_POOL_VALGRIND
243 : /*!
244 : \brief A fast memory allocator that guarantees proper alignment of all allocated chunks.
245 :
246 : \details Whenever an object of type pool needs memory from the system,
247 : it will request it from its UserAllocator template parameter.
248 : The amount requested is determined using a doubling algorithm;
249 : that is, each time more system memory is allocated,
250 : the amount of system memory requested is doubled.
251 :
252 : Users may control the doubling algorithm by using the following extensions:
253 :
254 : Users may pass an additional constructor parameter to pool.
255 : This parameter is of type size_type,
256 : and is the number of chunks to request from the system
257 : the first time that object needs to allocate system memory.
258 : The default is 32. This parameter may not be 0.
259 :
260 : Users may also pass an optional third parameter to pool's
261 : constructor. This parameter is of type size_type,
262 : and sets a maximum size for allocated chunks. When this
263 : parameter takes the default value of 0, then there is no upper
264 : limit on chunk size.
265 :
266 : Finally, if the doubling algorithm results in no memory
267 : being allocated, the pool will backtrack just once, halving
268 : the chunk size and trying again.
269 :
270 : <b>UserAllocator type</b> - the method that the Pool will use to allocate memory from the system.
271 :
272 : There are essentially two ways to use class pool: the client can call \ref malloc() and \ref free() to allocate
273 : and free single chunks of memory, this is the most efficient way to use a pool, but does not allow for
274 : the efficient allocation of arrays of chunks. Alternatively, the client may call \ref ordered_malloc() and \ref
275 : ordered_free(), in which case the free list is maintained in an ordered state, and efficient allocation of arrays
276 : of chunks are possible. However, this latter option can suffer from poor performance when large numbers of
277 : allocations are performed.
278 :
279 : */
280 : template <typename UserAllocator>
281 : class pool: protected simple_segregated_storage < typename UserAllocator::size_type >
282 : {
283 : public:
284 : typedef UserAllocator user_allocator; //!< User allocator.
285 : typedef typename UserAllocator::size_type size_type; //!< An unsigned integral type that can represent the size of the largest object to be allocated.
286 : typedef typename UserAllocator::difference_type difference_type; //!< A signed integral type that can represent the difference of any two pointers.
287 :
288 : private:
289 : BOOST_STATIC_CONSTANT(size_type, min_alloc_size =
290 : (::boost::integer::static_lcm<sizeof(void *), sizeof(size_type)>::value) );
291 : BOOST_STATIC_CONSTANT(size_type, min_align =
292 : (::boost::integer::static_lcm< ::boost::alignment_of<void *>::value, ::boost::alignment_of<size_type>::value>::value) );
293 :
294 : //! \returns 0 if out-of-memory.
295 : //! Called if malloc/ordered_malloc needs to resize the free list.
296 : void * malloc_need_resize(); //! Called if malloc needs to resize the free list.
297 : void * ordered_malloc_need_resize(); //! Called if ordered_malloc needs to resize the free list.
298 :
299 : protected:
300 : details::PODptr<size_type> list; //!< List structure holding ordered blocks.
301 :
302 1278 : simple_segregated_storage<size_type> & store()
303 : { //! \returns pointer to store.
304 1278 : return *this;
305 : }
306 : const simple_segregated_storage<size_type> & store() const
307 : { //! \returns pointer to store.
308 : return *this;
309 : }
310 : const size_type requested_size;
311 : size_type next_size;
312 : size_type start_size;
313 : size_type max_size;
314 :
315 : //! finds which POD in the list 'chunk' was allocated from.
316 : details::PODptr<size_type> find_POD(void * const chunk) const;
317 :
318 : // is_from() tests a chunk to determine if it belongs in a block.
319 : static bool is_from(void * const chunk, char * const i,
320 : const size_type sizeof_i)
321 : { //! \param chunk chunk to check if is from this pool.
322 : //! \param i memory chunk at i with element sizeof_i.
323 : //! \param sizeof_i element size (size of the chunk area of that block, not the total size of that block).
324 : //! \returns true if chunk was allocated or may be returned.
325 : //! as the result of a future allocation.
326 : //!
327 : //! Returns false if chunk was allocated from some other pool,
328 : //! or may be returned as the result of a future allocation from some other pool.
329 : //! Otherwise, the return value is meaningless.
330 : //!
331 : //! Note that this function may not be used to reliably test random pointer values.
332 :
333 : // We use std::less_equal and std::less to test 'chunk'
334 : // against the array bounds because standard operators
335 : // may return unspecified results.
336 : // This is to ensure portability. The operators < <= > >= are only
337 : // defined for pointers to objects that are 1) in the same array, or
338 : // 2) subobjects of the same object [5.9/2].
339 : // The functor objects guarantee a total order for any pointer [20.3.3/8]
340 : std::less_equal<void *> lt_eq;
341 : std::less<void *> lt;
342 : return (lt_eq(i, chunk) && lt(chunk, i + sizeof_i));
343 : }
344 :
345 2202 : size_type alloc_size() const
346 : { //! Calculated size of the memory chunks that will be allocated by this Pool.
347 : //! \returns allocated size.
348 : // For alignment reasons, this used to be defined to be lcm(requested_size, sizeof(void *), sizeof(size_type)),
349 : // but is now more parsimonious: just rounding up to the minimum required alignment of our housekeeping data
350 : // when required. This works provided all alignments are powers of two.
351 2202 : size_type s = (std::max)(requested_size, min_alloc_size);
352 2202 : size_type rem = s % min_align;
353 2202 : if(rem)
354 0 : s += min_align - rem;
355 2202 : BOOST_ASSERT(s >= min_alloc_size);
356 2202 : BOOST_ASSERT(s % min_align == 0);
357 2202 : return s;
358 : }
359 :
360 934 : size_type max_chunks() const
361 : { //! Calculated maximum number of memory chunks that can be allocated in a single call by this Pool.
362 934 : size_type POD_size = integer::static_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);
363 934 : return ((std::numeric_limits<size_type>::max)() - POD_size) / alloc_size();
364 : }
365 :
366 : static void * & nextof(void * const ptr)
367 : { //! \returns Pointer dereferenced.
368 : //! (Provided and used for the sake of code readability :)
369 : return *(static_cast<void **>(ptr));
370 : }
371 :
372 : public:
373 : // pre: npartition_size != 0 && nnext_size != 0
374 290 : explicit pool(const size_type nrequested_size,
375 : const size_type nnext_size = 32,
376 : const size_type nmax_size = 0)
377 : :
378 145 : list(0, 0), requested_size(nrequested_size), next_size(nnext_size), start_size(nnext_size),max_size(nmax_size)
379 145 : { //! Constructs a new empty Pool that can be used to allocate chunks of size RequestedSize.
380 : //! \param nrequested_size Requested chunk size
381 : //! \param nnext_size parameter is of type size_type,
382 : //! is the number of chunks to request from the system
383 : //! the first time that object needs to allocate system memory.
384 : //! The default is 32. This parameter may not be 0.
385 : //! \param nmax_size is the maximum number of chunks to allocate in one block.
386 145 : set_next_size(nnext_size);
387 145 : set_max_size(nmax_size);
388 290 : }
389 :
390 290 : ~pool()
391 145 : { //! Destructs the Pool, freeing its list of memory blocks.
392 145 : purge_memory();
393 290 : }
394 :
395 : // Releases memory blocks that don't have chunks allocated
396 : // pre: lists are ordered
397 : // Returns true if memory was actually deallocated
398 : bool release_memory();
399 :
400 : // Releases *all* memory blocks, even if chunks are still allocated
401 : // Returns true if memory was actually deallocated
402 : bool purge_memory();
403 :
404 : size_type get_next_size() const
405 : { //! Number of chunks to request from the system the next time that object needs to allocate system memory. This value should never be 0.
406 : //! \returns next_size;
407 : return next_size;
408 : }
409 155 : void set_next_size(const size_type nnext_size)
410 : { //! Set number of chunks to request from the system the next time that object needs to allocate system memory. This value should never be set to 0.
411 : BOOST_USING_STD_MIN();
412 155 : next_size = start_size = min BOOST_PREVENT_MACRO_SUBSTITUTION(nnext_size, max_chunks());
413 155 : }
414 : size_type get_max_size() const
415 : { //! \returns max_size.
416 : return max_size;
417 : }
418 145 : void set_max_size(const size_type nmax_size)
419 : { //! Set max_size.
420 : BOOST_USING_STD_MIN();
421 145 : max_size = min BOOST_PREVENT_MACRO_SUBSTITUTION(nmax_size, max_chunks());
422 145 : }
423 3170 : size_type get_requested_size() const
424 : { //! \returns the requested size passed into the constructor.
425 : //! (This value will not change during the lifetime of a Pool object).
426 3170 : return requested_size;
427 : }
428 :
429 : // Both malloc and ordered_malloc do a quick inlined check first for any
430 : // free chunks. Only if we need to get another memory block do we call
431 : // the non-inlined *_need_resize() functions.
432 : // Returns 0 if out-of-memory
433 : void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION()
434 : { //! Allocates a chunk of memory. Searches in the list of memory blocks
435 : //! for a block that has a free chunk, and returns that free chunk if found.
436 : //! Otherwise, creates a new memory block, adds its free list to pool's free list,
437 : //! \returns a free chunk from that block.
438 : //! If a new memory block cannot be allocated, returns 0. Amortized O(1).
439 : // Look for a non-empty storage
440 : if (!store().empty())
441 : return (store().malloc)();
442 : return malloc_need_resize();
443 : }
444 :
445 : void * ordered_malloc()
446 : { //! Same as malloc, only merges the free lists, to preserve order. Amortized O(1).
447 : //! \returns a free chunk from that block.
448 : //! If a new memory block cannot be allocated, returns 0. Amortized O(1).
449 : // Look for a non-empty storage
450 : if (!store().empty())
451 : return (store().malloc)();
452 : return ordered_malloc_need_resize();
453 : }
454 :
455 : // Returns 0 if out-of-memory
456 : // Allocate a contiguous section of n chunks
457 : void * ordered_malloc(size_type n);
458 : //! Same as malloc, only allocates enough contiguous chunks to cover n * requested_size bytes. Amortized O(n).
459 : //! \returns a free chunk from that block.
460 : //! If a new memory block cannot be allocated, returns 0. Amortized O(1).
461 :
462 : // pre: 'chunk' must have been previously
463 : // returned by *this.malloc().
464 : void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk)
465 : { //! Deallocates a chunk of memory. Note that chunk may not be 0. O(1).
466 : //!
467 : //! Chunk must have been previously returned by t.malloc() or t.ordered_malloc().
468 : //! Assumes that chunk actually refers to a block of chunks
469 : //! spanning n * partition_sz bytes.
470 : //! deallocates each chunk in that block.
471 : //! Note that chunk may not be 0. O(n).
472 : (store().free)(chunk);
473 : }
474 :
475 : // pre: 'chunk' must have been previously
476 : // returned by *this.malloc().
477 : void ordered_free(void * const chunk)
478 : { //! Same as above, but is order-preserving.
479 : //!
480 : //! Note that chunk may not be 0. O(N) with respect to the size of the free list.
481 : //! chunk must have been previously returned by t.malloc() or t.ordered_malloc().
482 : store().ordered_free(chunk);
483 : }
484 :
485 : // pre: 'chunk' must have been previously
486 : // returned by *this.malloc(n).
487 : void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunks, const size_type n)
488 : { //! Assumes that chunk actually refers to a block of chunks.
489 : //!
490 : //! chunk must have been previously returned by t.ordered_malloc(n)
491 : //! spanning n * partition_sz bytes.
492 : //! Deallocates each chunk in that block.
493 : //! Note that chunk may not be 0. O(n).
494 : const size_type partition_size = alloc_size();
495 : const size_type total_req_size = n * requested_size;
496 : const size_type num_chunks = total_req_size / partition_size +
497 : ((total_req_size % partition_size) ? true : false);
498 :
499 : store().free_n(chunks, num_chunks, partition_size);
500 : }
501 :
502 : // pre: 'chunk' must have been previously
503 : // returned by *this.malloc(n).
504 634 : void ordered_free(void * const chunks, const size_type n)
505 : { //! Assumes that chunk actually refers to a block of chunks spanning n * partition_sz bytes;
506 : //! deallocates each chunk in that block.
507 : //!
508 : //! Note that chunk may not be 0. Order-preserving. O(N + n) where N is the size of the free list.
509 : //! chunk must have been previously returned by t.malloc() or t.ordered_malloc().
510 :
511 634 : const size_type partition_size = alloc_size();
512 634 : const size_type total_req_size = n * requested_size;
513 1268 : const size_type num_chunks = total_req_size / partition_size +
514 634 : ((total_req_size % partition_size) ? true : false);
515 :
516 634 : store().ordered_free_n(chunks, num_chunks, partition_size);
517 634 : }
518 :
519 : // is_from() tests a chunk to determine if it was allocated from *this
520 : bool is_from(void * const chunk) const
521 : { //! \returns Returns true if chunk was allocated from u or
522 : //! may be returned as the result of a future allocation from u.
523 : //! Returns false if chunk was allocated from some other pool or
524 : //! may be returned as the result of a future allocation from some other pool.
525 : //! Otherwise, the return value is meaningless.
526 : //! Note that this function may not be used to reliably test random pointer values.
527 : return (find_POD(chunk).valid());
528 : }
529 : };
530 :
531 : #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
532 : template <typename UserAllocator>
533 : typename pool<UserAllocator>::size_type const pool<UserAllocator>::min_alloc_size;
534 : template <typename UserAllocator>
535 : typename pool<UserAllocator>::size_type const pool<UserAllocator>::min_align;
536 : #endif
537 :
538 : template <typename UserAllocator>
539 : bool pool<UserAllocator>::release_memory()
540 : { //! pool must be ordered. Frees every memory block that doesn't have any allocated chunks.
541 : //! \returns true if at least one memory block was freed.
542 :
543 : // ret is the return value: it will be set to true when we actually call
544 : // UserAllocator::free(..)
545 : bool ret = false;
546 :
547 : // This is a current & previous iterator pair over the memory block list
548 : details::PODptr<size_type> ptr = list;
549 : details::PODptr<size_type> prev;
550 :
551 : // This is a current & previous iterator pair over the free memory chunk list
552 : // Note that "prev_free" in this case does NOT point to the previous memory
553 : // chunk in the free list, but rather the last free memory chunk before the
554 : // current block.
555 : void * free_p = this->first;
556 : void * prev_free_p = 0;
557 :
558 : const size_type partition_size = alloc_size();
559 :
560 : // Search through all the all the allocated memory blocks
561 : while (ptr.valid())
562 : {
563 : // At this point:
564 : // ptr points to a valid memory block
565 : // free_p points to either:
566 : // 0 if there are no more free chunks
567 : // the first free chunk in this or some next memory block
568 : // prev_free_p points to either:
569 : // the last free chunk in some previous memory block
570 : // 0 if there is no such free chunk
571 : // prev is either:
572 : // the PODptr whose next() is ptr
573 : // !valid() if there is no such PODptr
574 :
575 : // If there are no more free memory chunks, then every remaining
576 : // block is allocated out to its fullest capacity, and we can't
577 : // release any more memory
578 : if (free_p == 0)
579 : break;
580 :
581 : // We have to check all the chunks. If they are *all* free (i.e., present
582 : // in the free list), then we can free the block.
583 : bool all_chunks_free = true;
584 :
585 : // Iterate 'i' through all chunks in the memory block
586 : // if free starts in the memory block, be careful to keep it there
587 : void * saved_free = free_p;
588 : for (char * i = ptr.begin(); i != ptr.end(); i += partition_size)
589 : {
590 : // If this chunk is not free
591 : if (i != free_p)
592 : {
593 : // We won't be able to free this block
594 : all_chunks_free = false;
595 :
596 : // free_p might have travelled outside ptr
597 : free_p = saved_free;
598 : // Abort searching the chunks; we won't be able to free this
599 : // block because a chunk is not free.
600 : break;
601 : }
602 :
603 : // We do not increment prev_free_p because we are in the same block
604 : free_p = nextof(free_p);
605 : }
606 :
607 : // post: if the memory block has any chunks, free_p points to one of them
608 : // otherwise, our assertions above are still valid
609 :
610 : const details::PODptr<size_type> next = ptr.next();
611 :
612 : if (!all_chunks_free)
613 : {
614 : if (is_from(free_p, ptr.begin(), ptr.element_size()))
615 : {
616 : std::less<void *> lt;
617 : void * const end = ptr.end();
618 : do
619 : {
620 : prev_free_p = free_p;
621 : free_p = nextof(free_p);
622 : } while (free_p && lt(free_p, end));
623 : }
624 : // This invariant is now restored:
625 : // free_p points to the first free chunk in some next memory block, or
626 : // 0 if there is no such chunk.
627 : // prev_free_p points to the last free chunk in this memory block.
628 :
629 : // We are just about to advance ptr. Maintain the invariant:
630 : // prev is the PODptr whose next() is ptr, or !valid()
631 : // if there is no such PODptr
632 : prev = ptr;
633 : }
634 : else
635 : {
636 : // All chunks from this block are free
637 :
638 : // Remove block from list
639 : if (prev.valid())
640 : prev.next(next);
641 : else
642 : list = next;
643 :
644 : // Remove all entries in the free list from this block
645 : if (prev_free_p != 0)
646 : nextof(prev_free_p) = free_p;
647 : else
648 : this->first = free_p;
649 :
650 : // And release memory
651 : (UserAllocator::free)(ptr.begin());
652 : ret = true;
653 : }
654 :
655 : // Increment ptr
656 : ptr = next;
657 : }
658 :
659 : next_size = start_size;
660 : return ret;
661 : }
662 :
663 : template <typename UserAllocator>
664 145 : bool pool<UserAllocator>::purge_memory()
665 : { //! pool must be ordered.
666 : //! Frees every memory block.
667 : //!
668 : //! This function invalidates any pointers previously returned
669 : //! by allocation functions of t.
670 : //! \returns true if at least one memory block was freed.
671 :
672 145 : details::PODptr<size_type> iter = list;
673 :
674 145 : if (!iter.valid())
675 135 : return false;
676 :
677 10 : do
678 : {
679 : // hold "next" pointer
680 10 : const details::PODptr<size_type> next = iter.next();
681 :
682 : // delete the storage
683 10 : (UserAllocator::free)(iter.begin());
684 :
685 : // increment iter
686 10 : iter = next;
687 10 : } while (iter.valid());
688 :
689 10 : list.invalidate();
690 10 : this->first = 0;
691 10 : next_size = start_size;
692 :
693 10 : return true;
694 145 : }
695 :
696 : template <typename UserAllocator>
697 : void * pool<UserAllocator>::malloc_need_resize()
698 : { //! No memory in any of our storages; make a new storage,
699 : //! Allocates chunk in newly malloc aftert resize.
700 : //! \returns pointer to chunk.
701 : size_type partition_size = alloc_size();
702 : size_type POD_size = static_cast<size_type>(next_size * partition_size +
703 : integer::static_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type));
704 : char * ptr = (UserAllocator::malloc)(POD_size);
705 : if (ptr == 0)
706 : {
707 : if(next_size > 4)
708 : {
709 : next_size >>= 1;
710 : partition_size = alloc_size();
711 : POD_size = static_cast<size_type>(next_size * partition_size +
712 : integer::static_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type));
713 : ptr = (UserAllocator::malloc)(POD_size);
714 : }
715 : if(ptr == 0)
716 : return 0;
717 : }
718 : const details::PODptr<size_type> node(ptr, POD_size);
719 :
720 : BOOST_USING_STD_MIN();
721 : if(!max_size)
722 : set_next_size(next_size << 1);
723 : else if( next_size*partition_size/requested_size < max_size)
724 : set_next_size(min BOOST_PREVENT_MACRO_SUBSTITUTION(next_size << 1, max_size * requested_size / partition_size));
725 :
726 : // initialize it,
727 : store().add_block(node.begin(), node.element_size(), partition_size);
728 :
729 : // insert it into the list,
730 : node.next(list);
731 : list = node;
732 :
733 : // and return a chunk from it.
734 : return (store().malloc)();
735 : }
736 :
737 : template <typename UserAllocator>
738 : void * pool<UserAllocator>::ordered_malloc_need_resize()
739 : { //! No memory in any of our storages; make a new storage,
740 : //! \returns pointer to new chunk.
741 : size_type partition_size = alloc_size();
742 : size_type POD_size = static_cast<size_type>(next_size * partition_size +
743 : integer::static_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type));
744 : char * ptr = (UserAllocator::malloc)(POD_size);
745 : if (ptr == 0)
746 : {
747 : if(next_size > 4)
748 : {
749 : next_size >>= 1;
750 : partition_size = alloc_size();
751 : POD_size = static_cast<size_type>(next_size * partition_size +
752 : integer::static_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type));
753 : ptr = (UserAllocator::malloc)(POD_size);
754 : }
755 : if(ptr == 0)
756 : return 0;
757 : }
758 : const details::PODptr<size_type> node(ptr, POD_size);
759 :
760 : BOOST_USING_STD_MIN();
761 : if(!max_size)
762 : set_next_size(next_size << 1);
763 : else if( next_size*partition_size/requested_size < max_size)
764 : set_next_size(min BOOST_PREVENT_MACRO_SUBSTITUTION(next_size << 1, max_size * requested_size / partition_size));
765 :
766 : // initialize it,
767 : // (we can use "add_block" here because we know that
768 : // the free list is empty, so we don't have to use
769 : // the slower ordered version)
770 : store().add_ordered_block(node.begin(), node.element_size(), partition_size);
771 :
772 : // insert it into the list,
773 : // handle border case
774 : if (!list.valid() || std::greater<void *>()(list.begin(), node.begin()))
775 : {
776 : node.next(list);
777 : list = node;
778 : }
779 : else
780 : {
781 : details::PODptr<size_type> prev = list;
782 :
783 : while (true)
784 : {
785 : // if we're about to hit the end or
786 : // if we've found where "node" goes
787 : if (prev.next_ptr() == 0
788 : || std::greater<void *>()(prev.next_ptr(), node.begin()))
789 : break;
790 :
791 : prev = prev.next();
792 : }
793 :
794 : node.next(prev.next());
795 : prev.next(node);
796 : }
797 : // and return a chunk from it.
798 : return (store().malloc)();
799 : }
800 :
801 : template <typename UserAllocator>
802 634 : void * pool<UserAllocator>::ordered_malloc(const size_type n)
803 : { //! Gets address of a chunk n, allocating new memory if not already available.
804 : //! \returns Address of chunk n if allocated ok.
805 : //! \returns 0 if not enough memory for n chunks.
806 634 : if (n > max_chunks())
807 0 : return 0;
808 :
809 634 : const size_type partition_size = alloc_size();
810 634 : const size_type total_req_size = n * requested_size;
811 1268 : const size_type num_chunks = total_req_size / partition_size +
812 634 : ((total_req_size % partition_size) ? true : false);
813 :
814 634 : void * ret = store().malloc_n(num_chunks, partition_size);
815 :
816 : #ifdef BOOST_POOL_INSTRUMENT
817 : std::cout << "Allocating " << n << " chunks from pool of size " << partition_size << std::endl;
818 : #endif
819 634 : if ((ret != 0) || (n == 0))
820 624 : return ret;
821 :
822 : #ifdef BOOST_POOL_INSTRUMENT
823 : std::cout << "Cache miss, allocating another chunk...\n";
824 : #endif
825 :
826 : // Not enough memory in our storages; make a new storage,
827 : BOOST_USING_STD_MAX();
828 10 : next_size = max BOOST_PREVENT_MACRO_SUBSTITUTION(next_size, num_chunks);
829 20 : size_type POD_size = static_cast<size_type>(next_size * partition_size +
830 10 : integer::static_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type));
831 10 : char * ptr = (UserAllocator::malloc)(POD_size);
832 10 : if (ptr == 0)
833 : {
834 0 : if(num_chunks < next_size)
835 : {
836 : // Try again with just enough memory to do the job, or at least whatever we
837 : // allocated last time:
838 0 : next_size >>= 1;
839 0 : next_size = max BOOST_PREVENT_MACRO_SUBSTITUTION(next_size, num_chunks);
840 0 : POD_size = static_cast<size_type>(next_size * partition_size +
841 0 : integer::static_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type));
842 0 : ptr = (UserAllocator::malloc)(POD_size);
843 0 : }
844 0 : if(ptr == 0)
845 0 : return 0;
846 0 : }
847 10 : const details::PODptr<size_type> node(ptr, POD_size);
848 :
849 : // Split up block so we can use what wasn't requested.
850 10 : if (next_size > num_chunks)
851 20 : store().add_ordered_block(node.begin() + num_chunks * partition_size,
852 10 : node.element_size() - num_chunks * partition_size, partition_size);
853 :
854 : BOOST_USING_STD_MIN();
855 10 : if(!max_size)
856 10 : set_next_size(next_size << 1);
857 0 : else if( next_size*partition_size/requested_size < max_size)
858 0 : set_next_size(min BOOST_PREVENT_MACRO_SUBSTITUTION(next_size << 1, max_size * requested_size / partition_size));
859 :
860 : // insert it into the list,
861 : // handle border case.
862 10 : if (!list.valid() || std::greater<void *>()(list.begin(), node.begin()))
863 : {
864 10 : node.next(list);
865 10 : list = node;
866 10 : }
867 : else
868 : {
869 0 : details::PODptr<size_type> prev = list;
870 :
871 0 : while (true)
872 : {
873 : // if we're about to hit the end, or if we've found where "node" goes.
874 0 : if (prev.next_ptr() == 0
875 0 : || std::greater<void *>()(prev.next_ptr(), node.begin()))
876 0 : break;
877 :
878 0 : prev = prev.next();
879 : }
880 :
881 0 : node.next(prev.next());
882 0 : prev.next(node);
883 : }
884 :
885 : // and return it.
886 10 : return node.begin();
887 634 : }
888 :
889 : template <typename UserAllocator>
890 : details::PODptr<typename pool<UserAllocator>::size_type>
891 : pool<UserAllocator>::find_POD(void * const chunk) const
892 : { //! find which PODptr storage memory that this chunk is from.
893 : //! \returns the PODptr that holds this chunk.
894 : // Iterate down list to find which storage this chunk is from.
895 : details::PODptr<size_type> iter = list;
896 : while (iter.valid())
897 : {
898 : if (is_from(chunk, iter.begin(), iter.element_size()))
899 : return iter;
900 : iter = iter.next();
901 : }
902 :
903 : return iter;
904 : }
905 :
906 : #else // BOOST_POOL_VALGRIND
907 :
908 : template<typename UserAllocator>
909 : class pool
910 : {
911 : public:
912 : // types
913 : typedef UserAllocator user_allocator; // User allocator.
914 : typedef typename UserAllocator::size_type size_type; // An unsigned integral type that can represent the size of the largest object to be allocated.
915 : typedef typename UserAllocator::difference_type difference_type; // A signed integral type that can represent the difference of any two pointers.
916 :
917 : // construct/copy/destruct
918 : explicit pool(const size_type s, const size_type = 32, const size_type m = 0) : chunk_size(s), max_alloc_size(m) {}
919 : ~pool()
920 : {
921 : purge_memory();
922 : }
923 :
924 : bool release_memory()
925 : {
926 : bool ret = free_list.empty() ? false : true;
927 : for(std::set<void*>::iterator pos = free_list.begin(); pos != free_list.end(); ++pos)
928 : {
929 : (user_allocator::free)(static_cast<char*>(*pos));
930 : }
931 : free_list.clear();
932 : return ret;
933 : }
934 : bool purge_memory()
935 : {
936 : bool ret = free_list.empty() && used_list.empty() ? false : true;
937 : for(std::set<void*>::iterator pos = free_list.begin(); pos != free_list.end(); ++pos)
938 : {
939 : (user_allocator::free)(static_cast<char*>(*pos));
940 : }
941 : free_list.clear();
942 : for(std::set<void*>::iterator pos = used_list.begin(); pos != used_list.end(); ++pos)
943 : {
944 : (user_allocator::free)(static_cast<char*>(*pos));
945 : }
946 : used_list.clear();
947 : return ret;
948 : }
949 : size_type get_next_size() const
950 : {
951 : return 1;
952 : }
953 : void set_next_size(const size_type){}
954 : size_type get_max_size() const
955 : {
956 : return max_alloc_size;
957 : }
958 : void set_max_size(const size_type s)
959 : {
960 : max_alloc_size = s;
961 : }
962 : size_type get_requested_size() const
963 : {
964 : return chunk_size;
965 : }
966 : void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION()
967 : {
968 : void* ret;
969 : if(free_list.empty())
970 : {
971 : ret = (user_allocator::malloc)(chunk_size);
972 : VALGRIND_MAKE_MEM_UNDEFINED(ret, chunk_size);
973 : }
974 : else
975 : {
976 : ret = *free_list.begin();
977 : free_list.erase(free_list.begin());
978 : VALGRIND_MAKE_MEM_UNDEFINED(ret, chunk_size);
979 : }
980 : used_list.insert(ret);
981 : return ret;
982 : }
983 : void * ordered_malloc()
984 : {
985 : return (this->malloc)();
986 : }
987 : void * ordered_malloc(size_type n)
988 : {
989 : if(max_alloc_size && (n > max_alloc_size))
990 : return 0;
991 : void* ret = (user_allocator::malloc)(chunk_size * n);
992 : used_list.insert(ret);
993 : return ret;
994 : }
995 : void free BOOST_PREVENT_MACRO_SUBSTITUTION(void *const chunk)
996 : {
997 : BOOST_ASSERT(used_list.count(chunk) == 1);
998 : BOOST_ASSERT(free_list.count(chunk) == 0);
999 : used_list.erase(chunk);
1000 : free_list.insert(chunk);
1001 : VALGRIND_MAKE_MEM_NOACCESS(chunk, chunk_size);
1002 : }
1003 : void ordered_free(void *const chunk)
1004 : {
1005 : return (this->free)(chunk);
1006 : }
1007 : void free BOOST_PREVENT_MACRO_SUBSTITUTION(void *const chunk, const size_type)
1008 : {
1009 : BOOST_ASSERT(used_list.count(chunk) == 1);
1010 : BOOST_ASSERT(free_list.count(chunk) == 0);
1011 : used_list.erase(chunk);
1012 : (user_allocator::free)(static_cast<char*>(chunk));
1013 : }
1014 : void ordered_free(void *const chunk, const size_type n)
1015 : {
1016 : (this->free)(chunk, n);
1017 : }
1018 : bool is_from(void *const chunk) const
1019 : {
1020 : return used_list.count(chunk) || free_list.count(chunk);
1021 : }
1022 :
1023 : protected:
1024 : size_type chunk_size, max_alloc_size;
1025 : std::set<void*> free_list, used_list;
1026 : };
1027 :
1028 : #endif
1029 :
1030 : } // namespace boost
1031 :
1032 : #ifdef BOOST_MSVC
1033 : #pragma warning(pop)
1034 : #endif
1035 :
1036 : #endif // #ifdef BOOST_POOL_HPP
1037 :
|
