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