bpool.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------------------+
|
|   Supplied under applicable software license agreement.
|
|   Copyright (c) 2018 Bentley Systems, Incorporated. All rights reserved.
|
+---------------------------------------------------------------------------------------*/
#pragma once



// 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 BBOOST_POOL_HPP
#define BBOOST_POOL_HPP
#include <Bentley/BeAssert.h>
#include <type_traits>

//#include <boost/config.hpp>  // for workarounds
#ifdef _MSC_VER
    #define BBOOST_MSVC
    #pragma push_macro("max")
    #pragma push_macro("min")
    #undef max
    #undef min
#endif
#define BBOOST_NO_INCLASS_MEMBER_INITIALIZATION
#define BBOOST_ASSERT(X) BeAssert((X))

#  ifdef BBOOST_NO_INCLASS_MEMBER_INITIALIZATION
#       define BBOOST_STATIC_CONSTANT(type, assignment) enum { assignment }
#  else
#     define BBOOST_STATIC_CONSTANT(type, assignment) static const type assignment
#  endif

// 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/bpool/poolfwd.hpp>

// boost::math::static_lcm
//#include "common_factor_ct.h"
//#define BBOOST_PTR_SIZE math::static_lcm<sizeof(size_type), sizeof(void *)>::value
#define BBOOST_PTR_SIZE sizeof(void *)
//#define BBOOSTE_MIN_ALIGNMENT math::static_lcm< std::alignment_of<void *>::value, std::alignment_of<size_type>::value>::value
#define BBOOSTE_MIN_ALIGNMENT std::alignment_of<void *>::value

// boost::simple_segregated_storage
#include "simple_segregated_storage.h"
// boost::std::alignment_of
//#include <boost/type_traits/std::alignment_of.hpp>
// BBOOST_ASSERT
//#include <boost/assert.hpp>

#ifdef BBOOST_POOL_INSTRUMENT
#include <iostream>
#include<iomanip>
#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!

#ifdef BBOOST_MSVC
#pragma warning(push)
#pragma warning(disable:4127)  // Conditional expression is constant
#endif

namespace bboost
{

namespace details
{  

template <typename SizeType>
class PODptr
{ 

  public:
    typedef SizeType size_type;
    static_assert (sizeof(void*) == sizeof(size_type), "simplifying assumption");

  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() - BBOOST_PTR_SIZE);
    }

  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 static_cast<size_type>(sz - sizeof(size_type) - BBOOST_PTR_SIZE);
    }

    size_type & next_size() const
    { 
      return *(static_cast<size_type *>(static_cast<void*>((ptr_next_size()))));
    }
    char * & next_ptr() const
    {  
      return *(static_cast<char **>(static_cast<void*>(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();
    }
}; // class PODptr
} // namespace details

template <typename UserAllocator>
class bpool: 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;  
    static_assert (sizeof(void*) == sizeof(size_type), "simplifying assumption");

  private:
    BBOOST_STATIC_CONSTANT(size_type, min_alloc_size = BBOOST_PTR_SIZE );
    BBOOST_STATIC_CONSTANT(size_type, min_align = BBOOSTE_MIN_ALIGNMENT );

    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;
    size_type start_size;
    size_type max_size;

    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]
      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
    { 
      // For alignment reasons, this used to be defined to be lcm(requested_size, sizeof(void *), sizeof(size_type)),
      // but is now more parsimonious: just rounding up to the minimum required alignment of our housekeeping data
      // when required.  This works provided all alignments are powers of two.
      size_type s = std::max<size_type> (requested_size, min_alloc_size);
      size_type rem = s % min_align;
      if(rem)
         s += min_align - rem;
      BBOOST_ASSERT(s >= min_alloc_size);
      BBOOST_ASSERT(s % min_align == 0);
      return s;
    }

    static void * & nextof(void * const ptr)
    { 
      return *(static_cast<void **>(ptr));
    }

  public:
    // pre: npartition_size != 0 && nnext_size != 0
    explicit bpool(const size_type nrequested_size,
        const size_type nnext_size = 32,
        const size_type nmax_size = 0)
    :
        list(0, 0), requested_size(nrequested_size), next_size(nnext_size), start_size(nnext_size),max_size(nmax_size)
    { 
    }

    ~bpool()
    { 
      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();

    size_type get_next_size() const
    { 
      return next_size;
    }
    void set_next_size(const size_type nnext_size)
    { 
      next_size = start_size = nnext_size;
    }
    size_type get_max_size() const
    { 
      return max_size;
    }
    void set_max_size(const size_type nmax_size)
    { 
      max_size = nmax_size;
    }
    size_type get_requested_size() const
    { 
      return requested_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());
    }
};

#ifndef BBOOST_NO_INCLASS_MEMBER_INITIALIZATION
template <typename UserAllocator>
typename bpool<UserAllocator>::size_type const bpool<UserAllocator>::min_alloc_size;
template <typename UserAllocator>
typename bpool<UserAllocator>::size_type const bpool<UserAllocator>::min_align;
#endif

template <typename UserAllocator>
bool bpool<UserAllocator>::release_memory()
{ 

  // ret 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_p = this->first;
  void * prev_free_p = 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_p points to either:
    //    0 if there are no more free chunks
    //    the first free chunk in this or some next memory block
    //  prev_free_p 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_p == 0)
      break;

    // 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_p;
    for (char * i = ptr.begin(); i != ptr.end(); i += partition_size)
    {
      // If this chunk is not free
      if (i != free_p)
      {
        // We won't be able to free this block
        all_chunks_free = false;

        // free_p might have travelled outside ptr
        free_p = 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_p because we are in the same block
      free_p = nextof(free_p);
    }

    // post: if the memory block has any chunks, free_p 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_p, ptr.begin(), ptr.element_size()))
      {
        std::less<void *> lt;
        void * const end = ptr.end();
        do
        {
          prev_free_p = free_p;
          free_p = nextof(free_p);
        } while (free_p && lt(free_p, end));
      }
      // This invariant is now restored:
      //     free_p points to the first free chunk in some next memory block, or
      //       0 if there is no such chunk.
      //     prev_free_p 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_p != 0)
        nextof(prev_free_p) = free_p;
      else
        this->first = free_p;

      // And release memory
      (UserAllocator::free)(ptr.begin());
      ret = true;
    }

    // Increment ptr
    ptr = next;
  }

  next_size = start_size;
  return ret;
}

template <typename UserAllocator>
bool bpool<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;
  next_size = start_size;

  return true;
}

template <typename UserAllocator>
void * bpool<UserAllocator>::malloc_need_resize()
{ 
  size_type partition_size = alloc_size();
  size_type POD_size = static_cast<size_type>(next_size * partition_size + BBOOST_PTR_SIZE + sizeof(size_type));
  char * ptr = (UserAllocator::malloc)(POD_size);
  if (ptr == 0)
  {
     if(next_size > 4)
     {
        next_size >>= 1;
        partition_size = alloc_size();
        POD_size = static_cast<size_type>(next_size * partition_size + BBOOST_PTR_SIZE + sizeof(size_type));
        ptr = (UserAllocator::malloc)(POD_size);
     }
     if(ptr == 0)
        return 0;
  }
  const details::PODptr<size_type> node(ptr, POD_size);

  if(!max_size)
    next_size <<= 1;
  else if( next_size*partition_size/requested_size < max_size)
    next_size = std::min (next_size << 1, max_size*requested_size/ partition_size);

  //  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 * bpool<UserAllocator>::ordered_malloc_need_resize()
{ 
  size_type partition_size = alloc_size();
  size_type POD_size = static_cast<size_type>(next_size * partition_size + BBOOST_PTR_SIZE + sizeof(size_type));
  char * ptr = (UserAllocator::malloc)(POD_size);
  if (ptr == 0)
  {
     if(next_size > 4)
     {
       next_size >>= 1;
       partition_size = alloc_size();
       POD_size = static_cast<size_type>(next_size * partition_size + BBOOST_PTR_SIZE + sizeof(size_type));
       ptr = (UserAllocator::malloc)(POD_size);
     }
     if(ptr == 0)
       return 0;
  }
  const details::PODptr<size_type> node(ptr, POD_size);

  if(!max_size)
    next_size <<= 1;
  else if( next_size*partition_size/requested_size < max_size)
    next_size = std::min (next_size << 1, max_size*requested_size/ partition_size);

  //  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_ordered_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 * bpool<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);

#ifdef BBOOST_POOL_INSTRUMENT
  std::cout << "Allocating " << n << " chunks from bpool of size " << partition_size << std::endl;
#endif
  if ((ret != 0) || (n == 0))
    return ret;

#ifdef BBOOST_POOL_INSTRUMENT
  std::cout << "Cache miss, allocating another chunk...\n";
#endif

  // Not enough memory in our storages; make a new storage,
  next_size = std::max (next_size, num_chunks);
  size_type POD_size = static_cast<size_type>(next_size * partition_size + BBOOST_PTR_SIZE + sizeof(size_type));
  char * ptr = (UserAllocator::malloc)(POD_size);

  if (ptr == 0)
  {
     if(num_chunks < next_size)
     {
        // Try again with just enough memory to do the job, or at least whatever we
        // allocated last time:
        next_size >>= 1;
        next_size = std::max (next_size, num_chunks);
        POD_size = static_cast<size_type>(next_size * partition_size + BBOOST_PTR_SIZE + sizeof(size_type));
        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.
  if (next_size > num_chunks)
    store().add_ordered_block(node.begin() + num_chunks * partition_size,
        node.element_size() - num_chunks * partition_size, partition_size);

  if(!max_size)
    next_size <<= 1;
  else if( next_size*partition_size/requested_size < max_size)
    next_size = std::min (next_size << 1, max_size*requested_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 it.
  return node.begin();
}

template <typename UserAllocator>
details::PODptr<typename bpool<UserAllocator>::size_type>
bpool<UserAllocator>::find_POD(void * const chunk) const
{ 
  // Iterate down list to find which storage this chunk is from.
  details::PODptr<size_type> iter = list;
  while (iter.valid())
  {
    if (is_from(chunk, iter.begin(), iter.element_size()))
      return iter;
    iter = iter.next();
  }

  return iter;
}


} // namespace boost

#ifdef BBOOST_MSVC
#pragma warning(pop)
#pragma pop_macro("max")
#pragma pop_macro("min")
#endif

#endif // #ifdef BBOOST_POOL_HPP