// 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 +

          ((total_req_size % partition_size) ? true : false);

      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 +

          ((total_req_size % partition_size) ? true : false);

      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;

  // This is a current & previous iterator pair over the memory block list

  details::PODptr<size_type> ptr = list;

  details::PODptr<size_type> prev;

  // This is a current & previous iterator pair over the free memory chunk list

  //  Note that "prev_free" in this case does NOT point to the previous memory

  //  chunk in the free list, but rather the last free memory chunk before the

  //  current block.

  void * free = this->first;

  void * prev_free = 0;

  const size_type partition_size = alloc_size();

  // Search through all the all the allocated memory blocks

  while (ptr.valid())

  {

    // At this point:

    //  ptr points to a valid memory block

    //  free points to either:

    //    0 if there are no more free chunks

    //    the first free chunk in this or some next memory block

    //  prev_free points to either:

    //    the last free chunk in some previous memory block

    //    0 if there is no such free chunk

    //  prev is either:

    //    the PODptr whose next() is ptr

    //    !valid() if there is no such PODptr

    // If there are no more free memory chunks, then every remaining

    //  block is allocated out to its fullest capacity, and we can't

    //  release any more memory

    if (free == 0)

      return ret;

    // We have to check all the chunks.  If they are *all* free (i.e., present

    //  in the free list), then we can free the block.

    bool all_chunks_free = true;

    // Iterate 'i' through all chunks in the memory block

    // if free starts in the memory block, be careful to keep it there

    void * saved_free = free;

    for (char * i = ptr.begin(); i != ptr.end(); i += partition_size)

    {

      // If this chunk is not free

      if (i != free)

      {

        // We won't be able to free this block

        all_chunks_free = false;

        // free might have travelled outside ptr

        free = saved_free;

        // Abort searching the chunks; we won't be able to free this

        //  block because a chunk is not free.

        break;

      }

      // We do not increment prev_free because we are in the same block

      free = nextof(free);

    }

    // post: if the memory block has any chunks, free points to one of them

    // otherwise, our assertions above are still valid

    const details::PODptr<size_type> next = ptr.next();

    if (!all_chunks_free)

    {

      if (is_from(free, ptr.begin(), ptr.element_size()))

      {

        std::less<void *> lt;

        void * const end = ptr.end();

        do

        {

          prev_free = free;

          free = nextof(free);

        } while (free && lt(free, end));

      }

      // This invariant is now restored:

      //     free points to the first free chunk in some next memory block, or

      //       0 if there is no such chunk.

      //     prev_free points to the last free chunk in this memory block.

      // We are just about to advance ptr.  Maintain the invariant:

      // prev is the PODptr whose next() is ptr, or !valid()

      // if there is no such PODptr

      prev = ptr;

    }

    else

    {

      // All chunks from this block are free

      // Remove block from list

      if (prev.valid())

        prev.next(next);

      else

        list = next;

      // Remove all entries in the free list from this block

      if (prev_free != 0)

        nextof(prev_free) = free;

      else

        this->first = free;

      // And release memory

      UserAllocator::free(ptr.begin());

      ret = true;

    }

    // Increment ptr

    ptr = next;

  }

  return ret;

}

template <typename UserAllocator>

bool pool<UserAllocator>::purge_memory()

{

  details::PODptr<size_type> iter = list;

  if (!iter.valid())

    return false;

  do

  {

    // hold "next" pointer

    const details::PODptr<size_type> next = iter.next();

    // delete the storage

    UserAllocator::free(iter.begin());

    // increment iter

    iter = next;

  } while (iter.valid());

  list.invalidate();

  this->first = 0;

  return true;

}

template <typename UserAllocator>

void * pool<UserAllocator>::malloc_need_resize()

{

  // No memory in any of our storages; make a new storage,

  const size_type partition_size = alloc_size();

  const size_type POD_size = next_size * partition_size +

      details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);

  char * const ptr = UserAllocator::malloc(POD_size);

  if (ptr == 0)

    return 0;

  const details::PODptr<size_type> node(ptr, POD_size);

  next_size <<= 1;

  //  initialize it,

  store().add_block(node.begin(), node.element_size(), partition_size);

  //  insert it into the list,

  node.next(list);

  list = node;

  //  and return a chunk from it.

  return store().malloc();

}

template <typename UserAllocator>

void * pool<UserAllocator>::ordered_malloc_need_resize()

{

  // No memory in any of our storages; make a new storage,

  const size_type partition_size = alloc_size();

  const size_type POD_size = next_size * partition_size +

      details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);

  char * const ptr = UserAllocator::malloc(POD_size);

  if (ptr == 0)

    return 0;

  const details::PODptr<size_type> node(ptr, POD_size);

  next_size <<= 1;

  //  initialize it,

  //  (we can use "add_block" here because we know that

  //  the free list is empty, so we don't have to use

  //  the slower ordered version)

  store().add_block(node.begin(), node.element_size(), partition_size);

  //  insert it into the list,

  //   handle border case

  if (!list.valid() || std::greater<void *>()(list.begin(), node.begin()))

  {

    node.next(list);

    list = node;

  }

  else

  {

    details::PODptr<size_type> prev = list;

    while (true)

    {

      // if we're about to hit the end or

      //  if we've found where "node" goes

      if (prev.next_ptr() == 0

          || std::greater<void *>()(prev.next_ptr(), node.begin()))

        break;

      prev = prev.next();

    }

    node.next(prev.next());

    prev.next(node);

  }

  //  and return a chunk from it.

  return store().malloc();

}

template <typename UserAllocator>

void * pool<UserAllocator>::ordered_malloc(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 +

      ((total_req_size % partition_size) ? true : false);

  void * ret = store().malloc_n(num_chunks, partition_size);

  if (ret != 0)

    return ret;

  // Not enougn memory in our storages; make a new storage,

  BOOST_USING_STD_MAX();

  next_size = max BOOST_PREVENT_MACRO_SUBSTITUTION(next_size, num_chunks);

  const size_type POD_size = next_size * partition_size +

      details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);

  char * const ptr = UserAllocator::malloc(POD_size);

  if (ptr == 0)

    return 0;

  const details::PODptr<size_type> node(ptr, POD_size);

  // Split up block so we can use what wasn't requested

  //  (we can use "add_block" here because we know that

  //  the free list is empty, so we don't have to use

  //  the slower ordered version)

  if (next_size > num_chunks)

    store().add_block(node.begin() + num_chunks * partition_size,

        node.element_size() - num_chunks * partition_size, partition_size);