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