| // Copyright (C) 2000, 2001 Stephen Cleary |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // See http://www.boost.org for updates, documentation, and revision history. |
| |
| #ifndef BOOST_SIMPLE_SEGREGATED_STORAGE_HPP |
| #define BOOST_SIMPLE_SEGREGATED_STORAGE_HPP |
| |
| /*! |
| \file |
| \brief Simple Segregated Storage. |
| \details A simple segregated storage implementation: |
| simple segregated storage is the basic idea behind the Boost Pool library. |
| Simple segregated storage is the simplest, and probably the fastest, |
| memory allocation/deallocation algorithm. |
| It begins by partitioning a memory block into fixed-size chunks. |
| Where the block comes from is not important until implementation time. |
| A Pool is some object that uses Simple Segregated Storage in this fashion. |
| */ |
| |
| // std::greater |
| #include <functional> |
| |
| #include <boost/pool/poolfwd.hpp> |
| |
| #ifdef BOOST_MSVC |
| #pragma warning(push) |
| #pragma warning(disable:4127) // Conditional expression is constant |
| #endif |
| |
| #ifdef BOOST_POOL_VALIDATE |
| # define BOOST_POOL_VALIDATE_INTERNALS validate(); |
| #else |
| # define BOOST_POOL_VALIDATE_INTERNALS |
| #endif |
| |
| namespace boost { |
| |
| /*! |
| |
| \brief Simple Segregated Storage is the simplest, and probably the fastest, |
| memory allocation/deallocation algorithm. It is responsible for |
| partitioning a memory block into fixed-size chunks: where the block comes from |
| is determined by the client of the class. |
| |
| \details Template class simple_segregated_storage controls access to a free list of memory chunks. |
| Please note that this is a very simple class, with preconditions on almost all its functions. It is intended to |
| be the fastest and smallest possible quick memory allocator - e.g., something to use in embedded systems. |
| This class delegates many difficult preconditions to the user (i.e., alignment issues). |
| |
| An object of type simple_segregated_storage<SizeType> is empty if its free list is empty. |
| If it is not empty, then it is ordered if its free list is ordered. A free list is ordered if repeated calls |
| to <tt>malloc()</tt> will result in a constantly-increasing sequence of values, as determined by <tt>std::less<void *></tt>. |
| A member function is <i>order-preserving</i> if the free list maintains its order orientation (that is, an |
| ordered free list is still ordered after the member function call). |
| |
| */ |
| template <typename SizeType> |
| class simple_segregated_storage |
| { |
| public: |
| typedef SizeType size_type; |
| |
| private: |
| simple_segregated_storage(const simple_segregated_storage &); |
| void operator=(const simple_segregated_storage &); |
| |
| static void * try_malloc_n(void * & start, size_type n, |
| size_type partition_size); |
| |
| protected: |
| void * first; /*!< This data member is the free list. |
| It points to the first chunk in the free list, |
| or is equal to 0 if the free list is empty. |
| */ |
| |
| void * find_prev(void * ptr); |
| |
| // for the sake of code readability :) |
| static void * & nextof(void * const ptr) |
| { //! The return value is just *ptr cast to the appropriate type. ptr must not be 0. (For the sake of code readability :) |
| //! As an example, let us assume that we want to truncate the free list after the first chunk. |
| //! That is, we want to set *first to 0; this will result in a free list with only one entry. |
| //! The normal way to do this is to first cast first to a pointer to a pointer to void, |
| //! and then dereference and assign (*static_cast<void **>(first) = 0;). |
| //! This can be done more easily through the use of this convenience function (nextof(first) = 0;). |
| //! \returns dereferenced pointer. |
| return *(static_cast<void **>(ptr)); |
| } |
| |
| public: |
| // Post: empty() |
| simple_segregated_storage() |
| :first(0) |
| { //! Construct empty storage area. |
| //! \post empty() |
| } |
| |
| static void * segregate(void * block, |
| size_type nsz, size_type npartition_sz, |
| void * end = 0); |
| |
| // Same preconditions as 'segregate' |
| // Post: !empty() |
| void add_block(void * const block, |
| const size_type nsz, const size_type npartition_sz) |
| { //! Add block |
| //! Segregate this block and merge its free list into the |
| //! free list referred to by "first". |
| //! \pre Same as segregate. |
| //! \post !empty() |
| BOOST_POOL_VALIDATE_INTERNALS |
| first = segregate(block, nsz, npartition_sz, first); |
| BOOST_POOL_VALIDATE_INTERNALS |
| } |
| |
| // Same preconditions as 'segregate' |
| // Post: !empty() |
| void add_ordered_block(void * const block, |
| const size_type nsz, const size_type npartition_sz) |
| { //! add block (ordered into list) |
| //! This (slower) version of add_block segregates the |
| //! block and merges its free list into our free list |
| //! in the proper order. |
| BOOST_POOL_VALIDATE_INTERNALS |
| // Find where "block" would go in the free list |
| void * const loc = find_prev(block); |
| |
| // Place either at beginning or in middle/end |
| if (loc == 0) |
| add_block(block, nsz, npartition_sz); |
| else |
| nextof(loc) = segregate(block, nsz, npartition_sz, nextof(loc)); |
| BOOST_POOL_VALIDATE_INTERNALS |
| } |
| |
| // default destructor. |
| |
| bool empty() const |
| { //! \returns true only if simple_segregated_storage is empty. |
| return (first == 0); |
| } |
| |
| void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION() |
| { //! Create a chunk. |
| //! \pre !empty() |
| //! Increment the "first" pointer to point to the next chunk. |
| BOOST_POOL_VALIDATE_INTERNALS |
| void * const ret = first; |
| |
| // Increment the "first" pointer to point to the next chunk. |
| first = nextof(first); |
| BOOST_POOL_VALIDATE_INTERNALS |
| return ret; |
| } |
| |
| void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk) |
| { //! Free a chunk. |
| //! \pre chunk was previously returned from a malloc() referring to the same free list. |
| //! \post !empty() |
| BOOST_POOL_VALIDATE_INTERNALS |
| nextof(chunk) = first; |
| first = chunk; |
| BOOST_POOL_VALIDATE_INTERNALS |
| } |
| |
| void ordered_free(void * const chunk) |
| { //! This (slower) implementation of 'free' places the memory |
| //! back in the list in its proper order. |
| //! \pre chunk was previously returned from a malloc() referring to the same free list |
| //! \post !empty(). |
| |
| // Find where "chunk" goes in the free list |
| BOOST_POOL_VALIDATE_INTERNALS |
| void * const loc = find_prev(chunk); |
| |
| // Place either at beginning or in middle/end. |
| if (loc == 0) |
| (free)(chunk); |
| else |
| { |
| nextof(chunk) = nextof(loc); |
| nextof(loc) = chunk; |
| } |
| BOOST_POOL_VALIDATE_INTERNALS |
| } |
| |
| void * malloc_n(size_type n, size_type partition_size); |
| |
| //! \pre chunks was previously allocated from *this with the same |
| //! values for n and partition_size. |
| //! \post !empty() |
| //! \note If you're allocating/deallocating n a lot, you should |
| //! be using an ordered pool. |
| void free_n(void * const chunks, const size_type n, |
| const size_type partition_size) |
| { |
| BOOST_POOL_VALIDATE_INTERNALS |
| if(n != 0) |
| add_block(chunks, n * partition_size, partition_size); |
| BOOST_POOL_VALIDATE_INTERNALS |
| } |
| |
| // pre: chunks was previously allocated from *this with the same |
| // values for n and partition_size. |
| // post: !empty() |
| void ordered_free_n(void * const chunks, const size_type n, |
| const size_type partition_size) |
| { //! Free n chunks from order list. |
| //! \pre chunks was previously allocated from *this with the same |
| //! values for n and partition_size. |
| |
| //! \pre n should not be zero (n == 0 has no effect). |
| BOOST_POOL_VALIDATE_INTERNALS |
| if(n != 0) |
| add_ordered_block(chunks, n * partition_size, partition_size); |
| BOOST_POOL_VALIDATE_INTERNALS |
| } |
| #ifdef BOOST_POOL_VALIDATE |
| void validate() |
| { |
| int index = 0; |
| void* old = 0; |
| void* ptr = first; |
| while(ptr) |
| { |
| void* pt = nextof(ptr); // trigger possible segfault *before* we update variables |
| ++index; |
| old = ptr; |
| ptr = nextof(ptr); |
| } |
| } |
| #endif |
| }; |
| |
| //! Traverses the free list referred to by "first", |
| //! and returns the iterator previous to where |
| //! "ptr" would go if it was in the free list. |
| //! Returns 0 if "ptr" would go at the beginning |
| //! of the free list (i.e., before "first"). |
| |
| //! \note Note that this function finds the location previous to where ptr would go |
| //! if it was in the free list. |
| //! It does not find the entry in the free list before ptr |
| //! (unless ptr is already in the free list). |
| //! Specifically, find_prev(0) will return 0, |
| //! not the last entry in the free list. |
| //! \returns location previous to where ptr would go if it was in the free list. |
| template <typename SizeType> |
| void * simple_segregated_storage<SizeType>::find_prev(void * const ptr) |
| { |
| // Handle border case. |
| if (first == 0 || std::greater<void *>()(first, ptr)) |
| return 0; |
| |
| void * iter = first; |
| while (true) |
| { |
| // if we're about to hit the end, or if we've found where "ptr" goes. |
| if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr)) |
| return iter; |
| |
| iter = nextof(iter); |
| } |
| } |
| |
| //! Segregate block into chunks. |
| //! \pre npartition_sz >= sizeof(void *) |
| //! \pre npartition_sz = sizeof(void *) * i, for some integer i |
| //! \pre nsz >= npartition_sz |
| //! \pre Block is properly aligned for an array of object of |
| //! size npartition_sz and array of void *. |
| //! The requirements above guarantee that any pointer to a chunk |
| //! (which is a pointer to an element in an array of npartition_sz) |
| //! may be cast to void **. |
| template <typename SizeType> |
| void * simple_segregated_storage<SizeType>::segregate( |
| void * const block, |
| const size_type sz, |
| const size_type partition_sz, |
| void * const end) |
| { |
| // Get pointer to last valid chunk, preventing overflow on size calculations |
| // The division followed by the multiplication just makes sure that |
| // old == block + partition_sz * i, for some integer i, even if the |
| // block size (sz) is not a multiple of the partition size. |
| char * old = static_cast<char *>(block) |
| + ((sz - partition_sz) / partition_sz) * partition_sz; |
| |
| // Set it to point to the end |
| nextof(old) = end; |
| |
| // Handle border case where sz == partition_sz (i.e., we're handling an array |
| // of 1 element) |
| if (old == block) |
| return block; |
| |
| // Iterate backwards, building a singly-linked list of pointers |
| for (char * iter = old - partition_sz; iter != block; |
| old = iter, iter -= partition_sz) |
| nextof(iter) = old; |
| |
| // Point the first pointer, too |
| nextof(block) = old; |
| |
| return block; |
| } |
| |
| //! \pre (n > 0), (start != 0), (nextof(start) != 0) |
| //! \post (start != 0) |
| //! The function attempts to find n contiguous chunks |
| //! of size partition_size in the free list, starting at start. |
| //! If it succeds, it returns the last chunk in that contiguous |
| //! sequence, so that the sequence is known by [start, {retval}] |
| //! If it fails, it does do either because it's at the end of the |
| //! free list or hits a non-contiguous chunk. In either case, |
| //! it will return 0, and set start to the last considered |
| //! chunk. You are at the end of the free list if |
| //! nextof(start) == 0. Otherwise, start points to the last |
| //! chunk in the contiguous sequence, and nextof(start) points |
| //! to the first chunk in the next contiguous sequence (assuming |
| //! an ordered free list). |
| template <typename SizeType> |
| void * simple_segregated_storage<SizeType>::try_malloc_n( |
| void * & start, size_type n, const size_type partition_size) |
| { |
| void * iter = nextof(start); |
| while (--n != 0) |
| { |
| void * next = nextof(iter); |
| if (next != static_cast<char *>(iter) + partition_size) |
| { |
| // next == 0 (end-of-list) or non-contiguous chunk found |
| start = iter; |
| return 0; |
| } |
| iter = next; |
| } |
| return iter; |
| } |
| |
| //! Attempts to find a contiguous sequence of n partition_sz-sized chunks. If found, removes them |
| //! all from the free list and returns a pointer to the first. If not found, returns 0. It is strongly |
| //! recommended (but not required) that the free list be ordered, as this algorithm will fail to find |
| //! a contiguous sequence unless it is contiguous in the free list as well. Order-preserving. |
| //! O(N) with respect to the size of the free list. |
| template <typename SizeType> |
| void * simple_segregated_storage<SizeType>::malloc_n(const size_type n, |
| const size_type partition_size) |
| { |
| BOOST_POOL_VALIDATE_INTERNALS |
| if(n == 0) |
| return 0; |
| void * start = &first; |
| void * iter; |
| do |
| { |
| if (nextof(start) == 0) |
| return 0; |
| iter = try_malloc_n(start, n, partition_size); |
| } while (iter == 0); |
| void * const ret = nextof(start); |
| nextof(start) = nextof(iter); |
| BOOST_POOL_VALIDATE_INTERNALS |
| return ret; |
| } |
| |
| } // namespace boost |
| |
| #ifdef BOOST_MSVC |
| #pragma warning(pop) |
| #endif |
| |
| #endif |