sl@0: // Copyright (C) 2000, 2001 Stephen Cleary sl@0: // sl@0: // Distributed under the Boost Software License, Version 1.0. (See sl@0: // accompanying file LICENSE_1_0.txt or copy at sl@0: // http://www.boost.org/LICENSE_1_0.txt) sl@0: // sl@0: // See http://www.boost.org for updates, documentation, and revision history. sl@0: sl@0: #ifndef BOOST_POOL_HPP sl@0: #define BOOST_POOL_HPP sl@0: sl@0: #include <boost/config.hpp> // for workarounds sl@0: sl@0: // std::less, std::less_equal, std::greater sl@0: #include <functional> sl@0: // new[], delete[], std::nothrow sl@0: #include <new> sl@0: // std::size_t, std::ptrdiff_t sl@0: #include <cstddef> sl@0: // std::malloc, std::free sl@0: #include <cstdlib> sl@0: // std::invalid_argument sl@0: #include <exception> sl@0: // std::max sl@0: #include <algorithm> sl@0: sl@0: #include <boost/pool/poolfwd.hpp> sl@0: sl@0: // boost::details::pool::ct_lcm sl@0: #include <boost/pool/detail/ct_gcd_lcm.hpp> sl@0: // boost::details::pool::lcm sl@0: #include <boost/pool/detail/gcd_lcm.hpp> sl@0: // boost::simple_segregated_storage sl@0: #include <boost/pool/simple_segregated_storage.hpp> sl@0: sl@0: #ifdef BOOST_NO_STDC_NAMESPACE sl@0: namespace std { using ::malloc; using ::free; } sl@0: #endif sl@0: sl@0: // There are a few places in this file where the expression "this->m" is used. sl@0: // This expression is used to force instantiation-time name lookup, which I am sl@0: // informed is required for strict Standard compliance. It's only necessary sl@0: // if "m" is a member of a base class that is dependent on a template sl@0: // parameter. sl@0: // Thanks to Jens Maurer for pointing this out! sl@0: sl@0: namespace boost { sl@0: sl@0: struct default_user_allocator_new_delete sl@0: { sl@0: typedef std::size_t size_type; sl@0: typedef std::ptrdiff_t difference_type; sl@0: sl@0: static char * malloc(const size_type bytes) sl@0: { return new (std::nothrow) char[bytes]; } sl@0: static void free(char * const block) sl@0: { delete [] block; } sl@0: }; sl@0: sl@0: struct default_user_allocator_malloc_free sl@0: { sl@0: typedef std::size_t size_type; sl@0: typedef std::ptrdiff_t difference_type; sl@0: sl@0: static char * malloc(const size_type bytes) sl@0: { return reinterpret_cast<char *>(std::malloc(bytes)); } sl@0: static void free(char * const block) sl@0: { std::free(block); } sl@0: }; sl@0: sl@0: namespace details { sl@0: sl@0: // PODptr is a class that pretends to be a "pointer" to different class types sl@0: // that don't really exist. It provides member functions to access the "data" sl@0: // of the "object" it points to. Since these "class" types are of variable sl@0: // size, and contains some information at the *end* of its memory (for sl@0: // alignment reasons), PODptr must contain the size of this "class" as well as sl@0: // the pointer to this "object". sl@0: template <typename SizeType> sl@0: class PODptr sl@0: { sl@0: public: sl@0: typedef SizeType size_type; sl@0: sl@0: private: sl@0: char * ptr; sl@0: size_type sz; sl@0: sl@0: char * ptr_next_size() const sl@0: { return (ptr + sz - sizeof(size_type)); } sl@0: char * ptr_next_ptr() const sl@0: { sl@0: return (ptr_next_size() - sl@0: pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value); sl@0: } sl@0: sl@0: public: sl@0: PODptr(char * const nptr, const size_type nsize) sl@0: :ptr(nptr), sz(nsize) { } sl@0: PODptr() sl@0: :ptr(0), sz(0) { } sl@0: sl@0: bool valid() const { return (begin() != 0); } sl@0: void invalidate() { begin() = 0; } sl@0: char * & begin() { return ptr; } sl@0: char * begin() const { return ptr; } sl@0: char * end() const { return ptr_next_ptr(); } sl@0: size_type total_size() const { return sz; } sl@0: size_type element_size() const sl@0: { sl@0: return (sz - sizeof(size_type) - sl@0: pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value); sl@0: } sl@0: sl@0: size_type & next_size() const sl@0: { return *(reinterpret_cast<size_type *>(ptr_next_size())); } sl@0: char * & next_ptr() const sl@0: { return *(reinterpret_cast<char **>(ptr_next_ptr())); } sl@0: sl@0: PODptr next() const sl@0: { return PODptr<size_type>(next_ptr(), next_size()); } sl@0: void next(const PODptr & arg) const sl@0: { sl@0: next_ptr() = arg.begin(); sl@0: next_size() = arg.total_size(); sl@0: } sl@0: }; sl@0: sl@0: } // namespace details sl@0: sl@0: template <typename UserAllocator> sl@0: class pool: protected simple_segregated_storage< sl@0: typename UserAllocator::size_type> sl@0: { sl@0: public: sl@0: typedef UserAllocator user_allocator; sl@0: typedef typename UserAllocator::size_type size_type; sl@0: typedef typename UserAllocator::difference_type difference_type; sl@0: sl@0: private: sl@0: BOOST_STATIC_CONSTANT(unsigned, min_alloc_size = sl@0: (::boost::details::pool::ct_lcm<sizeof(void *), sizeof(size_type)>::value) ); sl@0: sl@0: // Returns 0 if out-of-memory sl@0: // Called if malloc/ordered_malloc needs to resize the free list sl@0: void * malloc_need_resize(); sl@0: void * ordered_malloc_need_resize(); sl@0: sl@0: protected: sl@0: details::PODptr<size_type> list; sl@0: sl@0: simple_segregated_storage<size_type> & store() { return *this; } sl@0: const simple_segregated_storage<size_type> & store() const { return *this; } sl@0: const size_type requested_size; sl@0: size_type next_size; sl@0: sl@0: // finds which POD in the list 'chunk' was allocated from sl@0: details::PODptr<size_type> find_POD(void * const chunk) const; sl@0: sl@0: // is_from() tests a chunk to determine if it belongs in a block sl@0: static bool is_from(void * const chunk, char * const i, sl@0: const size_type sizeof_i) sl@0: { sl@0: // We use std::less_equal and std::less to test 'chunk' sl@0: // against the array bounds because standard operators sl@0: // may return unspecified results. sl@0: // This is to ensure portability. The operators < <= > >= are only sl@0: // defined for pointers to objects that are 1) in the same array, or sl@0: // 2) subobjects of the same object [5.9/2]. sl@0: // The functor objects guarantee a total order for any pointer [20.3.3/8] sl@0: //WAS: sl@0: // return (std::less_equal<void *>()(static_cast<void *>(i), chunk) sl@0: // && std::less<void *>()(chunk, sl@0: // static_cast<void *>(i + sizeof_i))); sl@0: std::less_equal<void *> lt_eq; sl@0: std::less<void *> lt; sl@0: return (lt_eq(i, chunk) && lt(chunk, i + sizeof_i)); sl@0: } sl@0: sl@0: size_type alloc_size() const sl@0: { sl@0: const unsigned min_size = min_alloc_size; sl@0: return details::pool::lcm<size_type>(requested_size, min_size); sl@0: } sl@0: sl@0: // for the sake of code readability :) sl@0: static void * & nextof(void * const ptr) sl@0: { return *(static_cast<void **>(ptr)); } sl@0: sl@0: public: sl@0: // The second parameter here is an extension! sl@0: // pre: npartition_size != 0 && nnext_size != 0 sl@0: explicit pool(const size_type nrequested_size, sl@0: const size_type nnext_size = 32) sl@0: :list(0, 0), requested_size(nrequested_size), next_size(nnext_size) sl@0: { } sl@0: sl@0: ~pool() { purge_memory(); } sl@0: sl@0: // Releases memory blocks that don't have chunks allocated sl@0: // pre: lists are ordered sl@0: // Returns true if memory was actually deallocated sl@0: bool release_memory(); sl@0: sl@0: // Releases *all* memory blocks, even if chunks are still allocated sl@0: // Returns true if memory was actually deallocated sl@0: bool purge_memory(); sl@0: sl@0: // These functions are extensions! sl@0: size_type get_next_size() const { return next_size; } sl@0: void set_next_size(const size_type nnext_size) { next_size = nnext_size; } sl@0: sl@0: // Both malloc and ordered_malloc do a quick inlined check first for any sl@0: // free chunks. Only if we need to get another memory block do we call sl@0: // the non-inlined *_need_resize() functions. sl@0: // Returns 0 if out-of-memory sl@0: void * malloc() sl@0: { sl@0: // Look for a non-empty storage sl@0: if (!store().empty()) sl@0: return store().malloc(); sl@0: return malloc_need_resize(); sl@0: } sl@0: sl@0: void * ordered_malloc() sl@0: { sl@0: // Look for a non-empty storage sl@0: if (!store().empty()) sl@0: return store().malloc(); sl@0: return ordered_malloc_need_resize(); sl@0: } sl@0: sl@0: // Returns 0 if out-of-memory sl@0: // Allocate a contiguous section of n chunks sl@0: void * ordered_malloc(size_type n); sl@0: sl@0: // pre: 'chunk' must have been previously sl@0: // returned by *this.malloc(). sl@0: void free(void * const chunk) sl@0: { store().free(chunk); } sl@0: sl@0: // pre: 'chunk' must have been previously sl@0: // returned by *this.malloc(). sl@0: void ordered_free(void * const chunk) sl@0: { store().ordered_free(chunk); } sl@0: sl@0: // pre: 'chunk' must have been previously sl@0: // returned by *this.malloc(n). sl@0: void free(void * const chunks, const size_type n) sl@0: { sl@0: const size_type partition_size = alloc_size(); sl@0: const size_type total_req_size = n * requested_size; sl@0: const size_type num_chunks = total_req_size / partition_size + sl@0: ((total_req_size % partition_size) ? true : false); sl@0: sl@0: store().free_n(chunks, num_chunks, partition_size); sl@0: } sl@0: sl@0: // pre: 'chunk' must have been previously sl@0: // returned by *this.malloc(n). sl@0: void ordered_free(void * const chunks, const size_type n) sl@0: { sl@0: const size_type partition_size = alloc_size(); sl@0: const size_type total_req_size = n * requested_size; sl@0: const size_type num_chunks = total_req_size / partition_size + sl@0: ((total_req_size % partition_size) ? true : false); sl@0: sl@0: store().ordered_free_n(chunks, num_chunks, partition_size); sl@0: } sl@0: sl@0: // is_from() tests a chunk to determine if it was allocated from *this sl@0: bool is_from(void * const chunk) const sl@0: { sl@0: return (find_POD(chunk).valid()); sl@0: } sl@0: }; sl@0: sl@0: template <typename UserAllocator> sl@0: bool pool<UserAllocator>::release_memory() sl@0: { sl@0: // This is the return value: it will be set to true when we actually call sl@0: // UserAllocator::free(..) sl@0: bool ret = false; sl@0: sl@0: // This is a current & previous iterator pair over the memory block list sl@0: details::PODptr<size_type> ptr = list; sl@0: details::PODptr<size_type> prev; sl@0: sl@0: // This is a current & previous iterator pair over the free memory chunk list sl@0: // Note that "prev_free" in this case does NOT point to the previous memory sl@0: // chunk in the free list, but rather the last free memory chunk before the sl@0: // current block. sl@0: void * free = this->first; sl@0: void * prev_free = 0; sl@0: sl@0: const size_type partition_size = alloc_size(); sl@0: sl@0: // Search through all the all the allocated memory blocks sl@0: while (ptr.valid()) sl@0: { sl@0: // At this point: sl@0: // ptr points to a valid memory block sl@0: // free points to either: sl@0: // 0 if there are no more free chunks sl@0: // the first free chunk in this or some next memory block sl@0: // prev_free points to either: sl@0: // the last free chunk in some previous memory block sl@0: // 0 if there is no such free chunk sl@0: // prev is either: sl@0: // the PODptr whose next() is ptr sl@0: // !valid() if there is no such PODptr sl@0: sl@0: // If there are no more free memory chunks, then every remaining sl@0: // block is allocated out to its fullest capacity, and we can't sl@0: // release any more memory sl@0: if (free == 0) sl@0: return ret; sl@0: sl@0: // We have to check all the chunks. If they are *all* free (i.e., present sl@0: // in the free list), then we can free the block. sl@0: bool all_chunks_free = true; sl@0: sl@0: // Iterate 'i' through all chunks in the memory block sl@0: // if free starts in the memory block, be careful to keep it there sl@0: void * saved_free = free; sl@0: for (char * i = ptr.begin(); i != ptr.end(); i += partition_size) sl@0: { sl@0: // If this chunk is not free sl@0: if (i != free) sl@0: { sl@0: // We won't be able to free this block sl@0: all_chunks_free = false; sl@0: sl@0: // free might have travelled outside ptr sl@0: free = saved_free; sl@0: // Abort searching the chunks; we won't be able to free this sl@0: // block because a chunk is not free. sl@0: break; sl@0: } sl@0: sl@0: // We do not increment prev_free because we are in the same block sl@0: free = nextof(free); sl@0: } sl@0: sl@0: // post: if the memory block has any chunks, free points to one of them sl@0: // otherwise, our assertions above are still valid sl@0: sl@0: const details::PODptr<size_type> next = ptr.next(); sl@0: sl@0: if (!all_chunks_free) sl@0: { sl@0: if (is_from(free, ptr.begin(), ptr.element_size())) sl@0: { sl@0: std::less<void *> lt; sl@0: void * const end = ptr.end(); sl@0: do sl@0: { sl@0: prev_free = free; sl@0: free = nextof(free); sl@0: } while (free && lt(free, end)); sl@0: } sl@0: // This invariant is now restored: sl@0: // free points to the first free chunk in some next memory block, or sl@0: // 0 if there is no such chunk. sl@0: // prev_free points to the last free chunk in this memory block. sl@0: sl@0: // We are just about to advance ptr. Maintain the invariant: sl@0: // prev is the PODptr whose next() is ptr, or !valid() sl@0: // if there is no such PODptr sl@0: prev = ptr; sl@0: } sl@0: else sl@0: { sl@0: // All chunks from this block are free sl@0: sl@0: // Remove block from list sl@0: if (prev.valid()) sl@0: prev.next(next); sl@0: else sl@0: list = next; sl@0: sl@0: // Remove all entries in the free list from this block sl@0: if (prev_free != 0) sl@0: nextof(prev_free) = free; sl@0: else sl@0: this->first = free; sl@0: sl@0: // And release memory sl@0: UserAllocator::free(ptr.begin()); sl@0: ret = true; sl@0: } sl@0: sl@0: // Increment ptr sl@0: ptr = next; sl@0: } sl@0: sl@0: return ret; sl@0: } sl@0: sl@0: template <typename UserAllocator> sl@0: bool pool<UserAllocator>::purge_memory() sl@0: { sl@0: details::PODptr<size_type> iter = list; sl@0: sl@0: if (!iter.valid()) sl@0: return false; sl@0: sl@0: do sl@0: { sl@0: // hold "next" pointer sl@0: const details::PODptr<size_type> next = iter.next(); sl@0: sl@0: // delete the storage sl@0: UserAllocator::free(iter.begin()); sl@0: sl@0: // increment iter sl@0: iter = next; sl@0: } while (iter.valid()); sl@0: sl@0: list.invalidate(); sl@0: this->first = 0; sl@0: sl@0: return true; sl@0: } sl@0: sl@0: template <typename UserAllocator> sl@0: void * pool<UserAllocator>::malloc_need_resize() sl@0: { sl@0: // No memory in any of our storages; make a new storage, sl@0: const size_type partition_size = alloc_size(); sl@0: const size_type POD_size = next_size * partition_size + sl@0: details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type); sl@0: char * const ptr = UserAllocator::malloc(POD_size); sl@0: if (ptr == 0) sl@0: return 0; sl@0: const details::PODptr<size_type> node(ptr, POD_size); sl@0: next_size <<= 1; sl@0: sl@0: // initialize it, sl@0: store().add_block(node.begin(), node.element_size(), partition_size); sl@0: sl@0: // insert it into the list, sl@0: node.next(list); sl@0: list = node; sl@0: sl@0: // and return a chunk from it. sl@0: return store().malloc(); sl@0: } sl@0: sl@0: template <typename UserAllocator> sl@0: void * pool<UserAllocator>::ordered_malloc_need_resize() sl@0: { sl@0: // No memory in any of our storages; make a new storage, sl@0: const size_type partition_size = alloc_size(); sl@0: const size_type POD_size = next_size * partition_size + sl@0: details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type); sl@0: char * const ptr = UserAllocator::malloc(POD_size); sl@0: if (ptr == 0) sl@0: return 0; sl@0: const details::PODptr<size_type> node(ptr, POD_size); sl@0: next_size <<= 1; sl@0: sl@0: // initialize it, sl@0: // (we can use "add_block" here because we know that sl@0: // the free list is empty, so we don't have to use sl@0: // the slower ordered version) sl@0: store().add_block(node.begin(), node.element_size(), partition_size); sl@0: sl@0: // insert it into the list, sl@0: // handle border case sl@0: if (!list.valid() || std::greater<void *>()(list.begin(), node.begin())) sl@0: { sl@0: node.next(list); sl@0: list = node; sl@0: } sl@0: else sl@0: { sl@0: details::PODptr<size_type> prev = list; sl@0: sl@0: while (true) sl@0: { sl@0: // if we're about to hit the end or sl@0: // if we've found where "node" goes sl@0: if (prev.next_ptr() == 0 sl@0: || std::greater<void *>()(prev.next_ptr(), node.begin())) sl@0: break; sl@0: sl@0: prev = prev.next(); sl@0: } sl@0: sl@0: node.next(prev.next()); sl@0: prev.next(node); sl@0: } sl@0: sl@0: // and return a chunk from it. sl@0: return store().malloc(); sl@0: } sl@0: sl@0: template <typename UserAllocator> sl@0: void * pool<UserAllocator>::ordered_malloc(const size_type n) sl@0: { sl@0: const size_type partition_size = alloc_size(); sl@0: const size_type total_req_size = n * requested_size; sl@0: const size_type num_chunks = total_req_size / partition_size + sl@0: ((total_req_size % partition_size) ? true : false); sl@0: sl@0: void * ret = store().malloc_n(num_chunks, partition_size); sl@0: sl@0: if (ret != 0) sl@0: return ret; sl@0: sl@0: // Not enougn memory in our storages; make a new storage, sl@0: BOOST_USING_STD_MAX(); sl@0: next_size = max BOOST_PREVENT_MACRO_SUBSTITUTION(next_size, num_chunks); sl@0: const size_type POD_size = next_size * partition_size + sl@0: details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type); sl@0: char * const ptr = UserAllocator::malloc(POD_size); sl@0: if (ptr == 0) sl@0: return 0; sl@0: const details::PODptr<size_type> node(ptr, POD_size); sl@0: sl@0: // Split up block so we can use what wasn't requested sl@0: // (we can use "add_block" here because we know that sl@0: // the free list is empty, so we don't have to use sl@0: // the slower ordered version) sl@0: if (next_size > num_chunks) sl@0: store().add_block(node.begin() + num_chunks * partition_size, sl@0: node.element_size() - num_chunks * partition_size, partition_size); sl@0: sl@0: next_size <<= 1; sl@0: sl@0: // insert it into the list, sl@0: // handle border case sl@0: if (!list.valid() || std::greater<void *>()(list.begin(), node.begin())) sl@0: { sl@0: node.next(list); sl@0: list = node; sl@0: } sl@0: else sl@0: { sl@0: details::PODptr<size_type> prev = list; sl@0: sl@0: while (true) sl@0: { sl@0: // if we're about to hit the end or sl@0: // if we've found where "node" goes sl@0: if (prev.next_ptr() == 0 sl@0: || std::greater<void *>()(prev.next_ptr(), node.begin())) sl@0: break; sl@0: sl@0: prev = prev.next(); sl@0: } sl@0: sl@0: node.next(prev.next()); sl@0: prev.next(node); sl@0: } sl@0: sl@0: // and return it. sl@0: return node.begin(); sl@0: } sl@0: sl@0: template <typename UserAllocator> sl@0: details::PODptr<typename pool<UserAllocator>::size_type> sl@0: pool<UserAllocator>::find_POD(void * const chunk) const sl@0: { sl@0: // We have to find which storage this chunk is from. sl@0: details::PODptr<size_type> iter = list; sl@0: while (iter.valid()) sl@0: { sl@0: if (is_from(chunk, iter.begin(), iter.element_size())) sl@0: return iter; sl@0: iter = iter.next(); sl@0: } sl@0: sl@0: return iter; sl@0: } sl@0: sl@0: } // namespace boost sl@0: sl@0: #endif