poolallocator.hh

Go to the documentation of this file.

// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
// $Id$
#ifndef DUNE_COMMON_POOLALLOCATOR_HH
#define DUNE_COMMON_POOLALLOCATOR_HH
 
#include "alignment.hh"
#include "static_assert.hh"
#include "lcm.hh"
#include <typeinfo>
#include <iostream>
#include <cassert>
#include <new>
 
//forward declarations.
 
// we need to know the test function to declare it friend
template<std::size_t size, typename T>
struct testPoolMain;
 
namespace Dune
{
 
  template<typename T, std::size_t s>
  class Pool;
 
  template<typename T, std::size_t s>
  class PoolAllocator;
 
}
 
namespace std
{
  /*
     template<class T, std::size_t S>
     inline ostream& operator<<(ostream& os, Dune::Pool<T,S>& pool)
     {
     os<<"pool="<<&pool<<" allocated_="<<pool.allocated_;
     return os;
     }
 
     template<class T, std::size_t S>
     inline ostream& operator<<(ostream& os, Dune::PoolAllocator<T,S>& pool)
     {
     os<<pool.memoryPool_<<std::endl;
     return os;
     }
   */
}
 
 
namespace Dune
{
  template<class T, std::size_t s>
  class Pool
  {
    // make the test function friend
    friend struct ::testPoolMain<s,T>;
 
    //friend std::ostream& std::operator<<<>(std::ostream&,Pool<T,s>&);
    template< class, std::size_t > friend class PoolAllocator;
 
  private:
 
    struct Reference
    {
      Reference *next_;
    };
 
  public:
 
    typedef T MemberType;
    enum
    {
      unionSize = ((sizeof(MemberType) < sizeof(Reference)) ?
                   sizeof(Reference) : sizeof(MemberType)),
 
      size = ((sizeof(MemberType) <= s && sizeof(Reference) <= s) ?
              s : unionSize),
 
      alignment = Lcm<AlignmentOf<MemberType>::value,AlignmentOf<Reference>::value>::value,
 
      alignedSize = ((unionSize % alignment == 0) ?
                     unionSize :
                     ((unionSize / alignment + 1) * alignment)),
 
      chunkSize = ((size % alignment == 0) ?
                   size : ((size / alignment + 1)* alignment))
                  + alignment - 1,
 
      elements = ((chunkSize - alignment + 1)/ alignedSize)
    };
 
  private:
    struct Chunk
    {
 
      //friend int testPool<s,T>();
 
      char chunk_[chunkSize];
 
      char* memory_;
 
      Chunk *next_;
 
      Chunk()
      {
        // Make sure the alignment is correct!
        // long long should be 64bit safe!
        unsigned long long lmemory = reinterpret_cast<unsigned long long>(chunk_);
        if(lmemory % alignment != 0)
          lmemory = (lmemory / alignment + 1)
                    * alignment;
 
        memory_ = reinterpret_cast<char *>(lmemory);
      }
    };
 
  public:
    inline Pool();
    inline ~Pool();
    inline void* allocate();
    inline void free(void* o);
 
    inline void print(std::ostream& os);
 
  private:
 
    // Prevent Copying!
    Pool(const Pool<MemberType,s>&);
 
    void operator=(const Pool<MemberType,s>& pool) const;
    inline void grow();
    Reference *head_;
    Chunk *chunks_;
    /* @brief The number of currently allocated elements. */
    //size_t allocated_;
 
  };
 
  template<class T, std::size_t s>
  class PoolAllocator
  {
    //friend std::ostream& std::operator<<<>(std::ostream&,PoolAllocator<T,s>&);
 
  public:
    typedef T value_type;
 
    enum
    {
      size=s*sizeof(value_type)
    };
 
    typedef T* pointer;
 
    typedef const T* const_pointer;
 
    typedef T& reference;
 
    typedef const T& const_reference;
 
    typedef std::size_t size_type;
 
    typedef std::ptrdiff_t difference_type;
 
    inline PoolAllocator();
 
    template<typename U, std::size_t u>
    inline PoolAllocator(const PoolAllocator<U,u>&)
    {
      // we allow copying but never copy the pool
      // to have a clear ownership of allocated pointers.
    }
 
    PoolAllocator(const PoolAllocator&)
    {
      // we allow copying but never copy the pool
      // to have a clear ownership of allocated pointers.
      // For this behaviour we have to implement
      // the copy constructor, because the default
      // one would copy the pool and deallocation
      // of it would break.
    }
    inline pointer allocate(std::size_t n, const_pointer hint=0);
 
    inline void deallocate(pointer p, std::size_t n);
 
    inline void construct(pointer p, const_reference value);
 
    inline void destroy(pointer p);
 
    inline pointer  address(reference x) const { return &x; }
 
 
    inline const_pointer address(const_reference x) const { return &x; }
 
    inline int max_size() const throw(){ return 1;}
 
    template<class U>
    struct rebind
    {
      typedef PoolAllocator<U,s> other;
    };
 
    typedef Pool<T,size> PoolType;
 
  private:
    PoolType memoryPool_;
  };
 
  // specialization for void
  template <std::size_t s>
  class PoolAllocator<void,s>
  {
  public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    // reference to void members are impossible.
    typedef void value_type;
    template <class U> struct rebind
    {
      typedef PoolAllocator<U,s> other;
    };
  };
 
 
  template<typename T1, std::size_t t1, typename T2, std::size_t t2>
  bool operator==(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
  {
    return false;
  }
 
 
  template<typename T1, std::size_t t1, typename T2, std::size_t t2>
  bool operator!=(const PoolAllocator<T1,t1>&, const PoolAllocator<T2,t2>&)
  {
    return true;
  }
 
  template<typename T, std::size_t t1, std::size_t t2>
  bool operator==(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
  {
    return &p1==&p2;
  }
 
 
  template<typename T, std::size_t t1, std::size_t t2>
  bool operator!=(const PoolAllocator<T,t1>& p1, const PoolAllocator<T,t2>& p2)
  {
    return &p1 != &p2;
  }
 
  template<typename T, std::size_t t1, std::size_t t2>
  bool operator==(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
  {
    return false;
  }
 
 
  template<typename T, std::size_t t1, std::size_t t2>
  bool operator!=(const PoolAllocator<void,t1>&, const PoolAllocator<T,t2>&)
  {
    return true;
  }
 
  template<std::size_t t1, std::size_t t2>
  bool operator==(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
  {
    return &p1==&p2;
  }
 
  template<std::size_t t1, std::size_t t2>
  bool operator!=(const PoolAllocator<void,t1>& p1, const PoolAllocator<void,t2>& p2)
  {
    return &p1!=&p2;
  }
 
  template<class T, std::size_t S>
  inline Pool<T,S>::Pool()
    : head_(0), chunks_(0) //, allocated_(0)
  {
    dune_static_assert(sizeof(T)<=unionSize, "Library Error: type T is too big");
    dune_static_assert(sizeof(Reference)<=unionSize, "Library Error: type of referene is too big");
    dune_static_assert(unionSize<=alignedSize, "Library Error: alignedSize too small");
    dune_static_assert(sizeof(T)<=chunkSize, "Library Error: chunkSize must be able to hold at least one value");
    dune_static_assert(sizeof(Reference)<=chunkSize, "Library Error: chunkSize must be able to hold at least one reference");
    dune_static_assert((chunkSize - (alignment - 1)) % alignment == 0, "Library Error: compiler cannot calculate!");
    dune_static_assert(elements>=1, "Library Error: we need to hold at least one element!");
    dune_static_assert(elements*alignedSize<=chunkSize, "Library Error: aligned elements must fit into chuck!");
  }
 
  template<class T, std::size_t S>
  inline Pool<T,S>::~Pool()
  {
    /*
       if(allocated_!=0)
       std::cerr<<"There are still "<<allocated_<<" allocated elements by the Pool<"<<typeid(T).name()<<","<<S<<"> "
               <<static_cast<void*>(this)<<"! This is a memory leak and might result in segfaults"
               <<std::endl;
     */
    // delete the allocated chunks.
    Chunk *current=chunks_;
 
    while(current!=0)
    {
      Chunk *tmp = current;
      current = current->next_;
      delete tmp;
    }
  }
 
  template<class T, std::size_t S>
  inline void Pool<T,S>::print(std::ostream& os)
  {
    Chunk* current=chunks_;
    while(current) {
      os<<current<<" ";
      current=current->next_;
    }
    os<<current<<" ";
  }
 
  template<class T, std::size_t S>
  inline void Pool<T,S>::grow()
  {
    Chunk *newChunk = new Chunk;
    newChunk->next_ = chunks_;
    chunks_ = newChunk;
 
    char* start = chunks_->memory_;
    char* last  = &start[elements*alignedSize];
    Reference* ref = new (start) (Reference);
 
    // grow is only called if head==0,
    assert(!head_);
 
    head_ = ref;
 
    for(char* element=start+alignedSize; element<last; element=element+alignedSize) {
      Reference* next = new (element) (Reference);
      ref->next_ = next;
      ref = next;
    }
    ref->next_=0;
  }
 
  template<class T, std::size_t S>
  inline void Pool<T,S>::free(void* b)
  {
    if(b) {
#ifndef NDEBUG
      Chunk* current=chunks_;
      while(current) {
        if(static_cast<void*>(&current->chunk_)<=b &&
           static_cast<void*>((&current->chunk_)+chunkSize)>b)
          break;
        current=current->next_;
      }
      if(!current)
        throw std::bad_alloc();
#endif
      Reference* freed = static_cast<Reference*>(b);
      freed->next_ = head_;
      head_ = freed;
      //--allocated_;
    }
    else
    {
      std::cerr<< "Tried to free null pointer! "<<b<<std::endl;
      throw std::bad_alloc();
    }
  }
 
  template<class T, std::size_t S>
  inline void* Pool<T,S>::allocate()
  {
    if(!head_)
      grow();
 
    Reference* p = head_;
    head_ = p->next_;
    //++allocated_;
    return p;
  }
 
  template<class T, std::size_t s>
  inline PoolAllocator<T,s>::PoolAllocator()
  { }
 
  template<class T, std::size_t s>
  inline typename PoolAllocator<T,s>::pointer
  PoolAllocator<T,s>::allocate(std::size_t n, const_pointer hint)
  {
    if(n==1)
      return static_cast<T*>(memoryPool_.allocate());
    else
      throw std::bad_alloc();
  }
 
  template<class T, std::size_t s>
  inline void PoolAllocator<T,s>::deallocate(pointer p, std::size_t n)
  {
    for(size_t i=0; i<n; i++)
      memoryPool_.free(p++);
  }
 
  template<class T, std::size_t s>
  inline void PoolAllocator<T,s>::construct(pointer p, const_reference value)
  {
    ::new (static_cast<void*>(p))T(value);
  }
 
  template<class T, std::size_t s>
  inline void PoolAllocator<T,s>::destroy(pointer p)
  {
    p->~T();
  }
 
}
#endif