Loading...
Searching...
No Matches
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:
// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
#ifndef DUNE_COMMON_POOLALLOCATOR_HH
#define DUNE_COMMON_POOLALLOCATOR_HH
#include <numeric>
#include <typeinfo>
#include <iostream>
#include <cassert>
#include <new>
#ifndef DOXYGEN
// forward declarations.
// we need to know the test function to declare it friend
template<std::size_t size, typename T>
struct testPoolMain;
#endif
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;
constexpr static int unionSize = (sizeof(MemberType) < sizeof(Reference)) ?
sizeof(Reference) : sizeof(MemberType);
constexpr static int size = (sizeof(MemberType) <= s && sizeof(Reference) <= s) ?
s : unionSize;
constexpr static int alignment = std::lcm(alignof(MemberType), alignof(Reference));
constexpr static int alignedSize = (unionSize % alignment == 0) ?
unionSize :
((unionSize / alignment + 1) * alignment);
constexpr static int chunkSize = (size % alignment == 0) ?
size : ((size / alignment + 1)* alignment);
constexpr static int elements = (chunkSize / alignedSize);
private:
struct Chunk
{
//friend int testPool<s,T>();
alignas(alignment) char chunk_[chunkSize];
Chunk *next_;
};
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;
constexpr static int 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 noexcept { 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)
{
static_assert(sizeof(T)<=unionSize, "Library Error: type T is too big");
static_assert(sizeof(Reference)<=unionSize, "Library Error: type of reference is too big");
static_assert(unionSize<=alignedSize, "Library Error: alignedSize too small");
static_assert(sizeof(T)<=chunkSize, "Library Error: chunkSize must be able to hold at least one value");
static_assert(sizeof(Reference)<=chunkSize, "Library Error: chunkSize must be able to hold at least one reference");
static_assert(chunkSize % alignment == 0, "Library Error: compiler cannot calculate!");
static_assert(elements>=1, "Library Error: we need to hold at least one element!");
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_->chunk_;
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)
{
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
Dune::PoolAllocator::construct
void construct(pointer p, const_reference value)
Construct an object.
Definition poolallocator.hh:555
Dune::Pool::free
void free(void *o)
Free an object.
Definition poolallocator.hh:495
Dune::Pool::~Pool
~Pool()
Destructor.
Definition poolallocator.hh:440
Dune::Pool::allocate
void * allocate()
Get a new or recycled object.
Definition poolallocator.hh:522
Dune::Pool::print
void print(std::ostream &os)
Print elements in pool for debugging.
Definition poolallocator.hh:460
Dune::PoolAllocator::allocate
pointer allocate(std::size_t n, const_pointer hint=0)
Allocates objects.
Definition poolallocator.hh:539
Dune::Pool::Pool
Pool()
Constructor.
Definition poolallocator.hh:426
Dune::PoolAllocator::deallocate
void deallocate(pointer p, std::size_t n)
Free objects.
Definition poolallocator.hh:548
Dune::PoolAllocator::destroy
void destroy(pointer p)
Destroy an object without freeing memory.
Definition poolallocator.hh:561
Dune::PoolAllocator::PoolAllocator
PoolAllocator()
Constructor.
Definition poolallocator.hh:534
std
STL namespace.
Dune
Dune namespace
Definition alignedallocator.hh:13
Dune::operator!=
constexpr auto operator!=(const HybridMultiIndex< S... > &lhs, const HybridMultiIndex< T... > &rhs)
Compare two HybridMultiIndexs for inequality.
Definition hybridmultiindex.hh:441
Dune::operator==
constexpr bool operator==(const HybridMultiIndex< S... > &lhs, const HybridMultiIndex< T... > &rhs)
Compare two HybridMultiIndexs for value equality.
Definition hybridmultiindex.hh:404
Dune::Pool
A memory pool of objects.
Definition poolallocator.hh:90
Dune::Pool< T, size >::alignment
static constexpr int alignment
Definition poolallocator.hh:127
Dune::Pool< T, size >::alignedSize
static constexpr int alignedSize
Definition poolallocator.hh:135
Dune::Pool< T, size >::chunkSize
static constexpr int chunkSize
Definition poolallocator.hh:144
Dune::Pool< T, size >::size
static constexpr int size
Definition poolallocator.hh:120
Dune::Pool< T, size >::unionSize
static constexpr int unionSize
Definition poolallocator.hh:113
Dune::Pool< T, size >::PoolAllocator
friend class PoolAllocator
Definition poolallocator.hh:95
Dune::Pool::MemberType
T MemberType
The type of object we allocate memory for.
Definition poolallocator.hh:108
Dune::Pool< T, size >::elements
static constexpr int elements
Definition poolallocator.hh:150
Dune::PoolAllocator
An allocator managing a pool of objects for reuse.
Definition poolallocator.hh:223
Dune::PoolAllocator< U, s >::PoolType
Pool< U, size > PoolType
Definition poolallocator.hh:349
Dune::PoolAllocator::address
const_pointer address(const_reference x) const
Convert a reference to a pointer.
Definition poolallocator.hh:332
Dune::PoolAllocator::const_reference
const T & const_reference
The constant reference type.
Definition poolallocator.hh:256
Dune::PoolAllocator::size_type
std::size_t size_type
The size type.
Definition poolallocator.hh:261
Dune::PoolAllocator::value_type
T value_type
Type of the values we construct and allocate.
Definition poolallocator.hh:230
Dune::PoolAllocator::reference
T & reference
The reference type.
Definition poolallocator.hh:251
Dune::PoolAllocator::PoolAllocator
PoolAllocator(const PoolAllocator &)
Copy constructor that does not copy the memory pool.
Definition poolallocator.hh:284
Dune::PoolAllocator::const_pointer
const T * const_pointer
The constant pointer type.
Definition poolallocator.hh:246
Dune::PoolAllocator::address
pointer address(reference x) const
Convert a reference to a pointer.
Definition poolallocator.hh:326
Dune::PoolAllocator::pointer
T * pointer
The pointer type.
Definition poolallocator.hh:241
Dune::PoolAllocator::PoolAllocator
PoolAllocator(const PoolAllocator< U, u > &)
Copy Constructor that does not copy the memory pool.
Definition poolallocator.hh:277
Dune::PoolAllocator::difference_type
std::ptrdiff_t difference_type
The difference_type.
Definition poolallocator.hh:266
Dune::PoolAllocator::max_size
int max_size() const noexcept
Not correctly implemented, yet!
Definition poolallocator.hh:337
Dune::PoolAllocator< U, s >::size
static constexpr int size
Definition poolallocator.hh:236
Dune::PoolAllocator::rebind
Rebind the allocator to another type.
Definition poolallocator.hh:344
Dune::PoolAllocator::rebind::other
PoolAllocator< U, s > other
Definition poolallocator.hh:345
Dune::PoolAllocator< void, s >::value_type
void value_type
Definition poolallocator.hh:366
Dune::PoolAllocator< void, s >::pointer
void * pointer
Definition poolallocator.hh:363
Dune::PoolAllocator< void, s >::const_pointer
const void * const_pointer
Definition poolallocator.hh:364
Dune::PoolAllocator< void, s >::rebind
Definition poolallocator.hh:368
Dune::PoolAllocator< void, s >::rebind::other
PoolAllocator< U, s > other
Definition poolallocator.hh:369