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