pool.hpp

CGAL is a collaborative effort of several sites in Europe and Israel. The goal is to make the most i

// 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_POOL_HPP
#define BOOST_POOL_HPP

#include <boost/config.hpp>  // for workarounds

// std::less, std::less_equal, std::greater
#include <functional>
// new[], delete[], std::nothrow
#include <new>
// std::size_t, std::ptrdiff_t
#include <cstddef>
// std::malloc, std::free
#include <cstdlib>
// std::invalid_argument
#include <exception>
// std::max
#include <algorithm>

#include <boost/pool/poolfwd.hpp>

// boost::details::pool::ct_lcm
#include <boost/pool/detail/ct_gcd_lcm.hpp>
// boost::details::pool::lcm
#include <boost/pool/detail/gcd_lcm.hpp>
// boost::simple_segregated_storage
#include <boost/pool/simple_segregated_storage.hpp>

#ifdef BOOST_NO_STDC_NAMESPACE
 namespace std { using ::malloc; using ::free; }
#endif

// There are a few places in this file where the expression "this->m" is used.
// This expression is used to force instantiation-time name lookup, which I am
//   informed is required for strict Standard compliance.  It's only necessary
//   if "m" is a member of a base class that is dependent on a template
//   parameter.
// Thanks to Jens Maurer for pointing this out!

namespace boost {

struct default_user_allocator_new_delete
{
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;

  static char * malloc(const size_type bytes)
  { return new (std::nothrow) char[bytes]; }
  static void free(char * const block)
  { delete [] block; }
};

struct default_user_allocator_malloc_free
{
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;

  static char * malloc(const size_type bytes)
  { return reinterpret_cast<char *>(std::malloc(bytes)); }
  static void free(char * const block)
  { std::free(block); }
};

namespace details {

// PODptr is a class that pretends to be a "pointer" to different class types
//  that don't really exist.  It provides member functions to access the "data"
//  of the "object" it points to.  Since these "class" types are of variable
//  size, and contains some information at the *end* of its memory (for
//  alignment reasons), PODptr must contain the size of this "class" as well as
//  the pointer to this "object".
template <typename SizeType>
class PODptr
{
  public:
    typedef SizeType size_type;

  private:
    char * ptr;
    size_type sz;

    char * ptr_next_size() const
    { return (ptr + sz - sizeof(size_type)); }
    char * ptr_next_ptr() const
    {
      return (ptr_next_size() -
          pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value);
    }

  public:
    PODptr(char * const nptr, const size_type nsize)
    :ptr(nptr), sz(nsize) { }
    PODptr()
    :ptr(0), sz(0) { }

    bool valid() const { return (begin() != 0); }
    void invalidate() { begin() = 0; }
    char * & begin() { return ptr; }
    char * begin() const { return ptr; }
    char * end() const { return ptr_next_ptr(); }
    size_type total_size() const { return sz; }
    size_type element_size() const
    {
      return (sz - sizeof(size_type) -
          pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value);
    }

    size_type & next_size() const
    { return *(reinterpret_cast<size_type *>(ptr_next_size())); }
    char * & next_ptr() const
    { return *(reinterpret_cast<char **>(ptr_next_ptr())); }

    PODptr next() const
    { return PODptr<size_type>(next_ptr(), next_size()); }
    void next(const PODptr & arg) const
    {
      next_ptr() = arg.begin();
      next_size() = arg.total_size();
    }
};

} // namespace details

template <typename UserAllocator>
class pool: protected simple_segregated_storage<
    typename UserAllocator::size_type>
{
  public:
    typedef UserAllocator user_allocator;
    typedef typename UserAllocator::size_type size_type;
    typedef typename UserAllocator::difference_type difference_type;

  private:
    BOOST_STATIC_CONSTANT(unsigned, min_alloc_size =
        (::boost::details::pool::ct_lcm<sizeof(void *), sizeof(size_type)>::value) );

    // Returns 0 if out-of-memory
    // Called if malloc/ordered_malloc needs to resize the free list
    void * malloc_need_resize();
    void * ordered_malloc_need_resize();

  protected:
    details::PODptr<size_type> list;

    simple_segregated_storage<size_type> & store() { return *this; }
    const simple_segregated_storage<size_type> & store() const { return *this; }
    const size_type requested_size;
    size_type next_size;

    // finds which POD in the list 'chunk' was allocated from
    details::PODptr<size_type> find_POD(void * const chunk) const;

    // is_from() tests a chunk to determine if it belongs in a block
    static bool is_from(void * const chunk, char * const i,
        const size_type sizeof_i)
    {
      // We use std::less_equal and std::less to test 'chunk'
      //  against the array bounds because standard operators
      //  may return unspecified results.
      // This is to ensure portability.  The operators < <= > >= are only
      //  defined for pointers to objects that are 1) in the same array, or
      //  2) subobjects of the same object [5.9/2].
      // The functor objects guarantee a total order for any pointer [20.3.3/8]
//WAS:
//      return (std::less_equal<void *>()(static_cast<void *>(i), chunk)
//          && std::less<void *>()(chunk,
//              static_cast<void *>(i + sizeof_i)));
      std::less_equal<void *> lt_eq;
      std::less<void *> lt;
      return (lt_eq(i, chunk) && lt(chunk, i + sizeof_i));
    }

    size_type alloc_size() const
    {
      const unsigned min_size = min_alloc_size;
      return details::pool::lcm<size_type>(requested_size, min_size);
    }

    // for the sake of code readability :)
    static void * & nextof(void * const ptr)
    { return *(static_cast<void **>(ptr)); }

  public:
    // The second parameter here is an extension!
    // pre: npartition_size != 0 && nnext_size != 0
    explicit pool(const size_type nrequested_size,
        const size_type nnext_size = 32)
    :list(0, 0), requested_size(nrequested_size), next_size(nnext_size)
    { }

    ~pool() { purge_memory(); }

    // Releases memory blocks that don't have chunks allocated
    // pre: lists are ordered
    //  Returns true if memory was actually deallocated
    bool release_memory();

    // Releases *all* memory blocks, even if chunks are still allocated
    //  Returns true if memory was actually deallocated
    bool purge_memory();

    // These functions are extensions!
    size_type get_next_size() const { return next_size; }
    void set_next_size(const size_type nnext_size) { next_size = nnext_size; }

    // Both malloc and ordered_malloc do a quick inlined check first for any
    //  free chunks.  Only if we need to get another memory block do we call
    //  the non-inlined *_need_resize() functions.
    // Returns 0 if out-of-memory
    void * malloc()
    {
      // Look for a non-empty storage
      if (!store().empty())
        return store().malloc();
      return malloc_need_resize();
    }

    void * ordered_malloc()
    {
      // Look for a non-empty storage
      if (!store().empty())
        return store().malloc();
      return ordered_malloc_need_resize();
    }

    // Returns 0 if out-of-memory
    // Allocate a contiguous section of n chunks
    void * ordered_malloc(size_type n);

    // pre: 'chunk' must have been previously
    //        returned by *this.malloc().
    void free(void * const chunk)
    { store().free(chunk); }

    // pre: 'chunk' must have been previously
    //        returned by *this.malloc().
    void ordered_free(void * const chunk)
    { store().ordered_free(chunk); }

    // pre: 'chunk' must have been previously
    //        returned by *this.malloc(n).
    void free(void * const chunks, const size_type n)
    {
      const size_type partition_size = alloc_size();
      const size_type total_req_size = n * requested_size;
      const size_type num_chunks = total_req_size / partition_size +
          static_cast<bool>(total_req_size % partition_size);

      store().free_n(chunks, num_chunks, partition_size);
    }

    // pre: 'chunk' must have been previously
    //        returned by *this.malloc(n).
    void ordered_free(void * const chunks, const size_type n)
    {
      const size_type partition_size = alloc_size();
      const size_type total_req_size = n * requested_size;
      const size_type num_chunks = total_req_size / partition_size +
          static_cast<bool>(total_req_size % partition_size);

      store().ordered_free_n(chunks, num_chunks, partition_size);
    }

    // is_from() tests a chunk to determine if it was allocated from *this
    bool is_from(void * const chunk) const
    {
      return (find_POD(chunk).valid());
    }
};

template <typename UserAllocator>
bool pool<UserAllocator>::release_memory()
{
  // This is the return value: it will be set to true when we actually call
  //  UserAllocator::free(..)
  bool ret = false;