/* -*- c++ -*-
C++ Indexable objects pool
This file is part of the dpp library of C++ template classes
doc: http://diaxen.ssji.net/dpp/index.html
repo: https://www.ssji.net/svn/projets/trunk/libdpp
This program is free software: you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public License
as published by the Free Software Foundation, either version 3 of
the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this program. If not, see
.
(c) 2010 Alexandre Becoulet
*/
#ifndef DPP_VECTOR_POOL_HH_
#define DPP_VECTOR_POOL_HH_
#include
#include
#include
/** @file @module{Vector pool} */
namespace dpp {
template ,
class PtrAllocator = std::allocator >
class vector_pool;
/** @short Vector pool iterator class
@module {Vector pool}
@header dpp/vector_pool
@internal
@This contains the iterator implementation for the @ref
vector_pool class.
*/
template /* FIXME rework iterator (more ops, copy, const, ...) */
class vector_pool_iterator
{
template friend class vector_pool;
template friend class vector_pool_iterator;
P *_pool;
unsigned int _i;
vector_pool_iterator (P *pool, unsigned int i)
: _pool(pool),
_i(i)
{
}
public:
typedef typename P::value_type value_type;
typedef typename P::reference reference;
typedef typename P::const_reference const_reference;
typedef typename P::pointer pointer;
typedef typename P::const_pointer const_pointer;
typedef unsigned int size_type;
typedef int difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
vector_pool_iterator()
{
}
template
vector_pool_iterator(const vector_pool_iterator &i)
: _pool(i._pool),
_i(i._i)
{
}
inline E & operator*()
{
return (*_pool)[_i];
}
inline E * operator->()
{
return &(*_pool)[_i];
}
inline vector_pool_iterator & operator++()
{
_i += direction;
return *this;
}
inline vector_pool_iterator operator++(int)
{
vector_pool_iterator tmp(*this);
_i += direction;
return tmp;
}
inline vector_pool_iterator & operator--()
{
_i -= direction;
return *this;
}
inline vector_pool_iterator operator--(int)
{
vector_pool_iterator tmp(*this);
_i -= direction;
return tmp;
}
vector_pool_iterator operator-(int x) const
{
return vector_pool_iterator(_pool, _i - x * direction);
}
vector_pool_iterator operator+(int x) const
{
return vector_pool_iterator(_pool, _i + x * direction);
}
difference_type operator-(const vector_pool_iterator & i) const
{
return (_i - i._i) * direction;
}
inline bool operator<(const vector_pool_iterator &i) const
{
return _i < i._i;
}
inline bool operator==(const vector_pool_iterator &i) const
{
return _i == i._i;
}
inline bool operator!=(const vector_pool_iterator &i) const
{
return _i != i._i;
}
};
/** @short Indexable allocation pool
@module {Vector pool}
@header dpp/vector_pool
@main
@showvalue
This class provides an indexable object allocation pool. The
pool can be accessed and traversed like a @ref std::vector.
Only the last or all objects in pool can be removed at once.
The @ref create functions must be used to allocate and construct
objects in pool. Unlike @ref std::vector this class does not
require assignment operator to be available in the object class.
The pool allocates storage blocks for multiple objects at once.
The number of objects in a storage block can be specified as
template parameter. Moreover a static storage space can be
provided for first storage blocks when creating the pool.
Unlike @ref std::vector, iterators and pointers to objects in
the pool are not invalidated by allocation and elements in the
pool are not stored at contiguous locations when crossing the @tt
block_size boundary.
The @tt Allocator and @tt PtrAllocator standard allocators
parameters are used to allocate objects and manage vector of
storage blocks respectively.
*/
template
class vector_pool
{
vector_pool(const vector_pool &);
const vector_pool & operator= (const vector_pool &);
typedef std::vector block_list_t;
block_list_t _blocks;
size_t _free_count;
size_t _static_size;
Allocator _allocator;
X * get_ptr(unsigned int i) const
{
return _blocks[i / block_size] + i % block_size;
}
X *alloc(size_t count = 1)
{
while (_free_count < count)
add_block();
unsigned int id = _blocks.size() * block_size - _free_count;
_free_count -= count;
return get_ptr(id);
}
void add_block()
{
const void *hint = _blocks.empty() ? 0 : (const void*)_blocks.front();
X *b = (X*)_allocator.allocate(block_size, hint);
_free_count += block_size;
_blocks.push_back(b);
}
public:
typedef X value_type;
typedef X & reference;
typedef const X & const_reference;
typedef X * pointer;
typedef const X * const_pointer;
typedef unsigned int size_type;
typedef int difference_type;
typedef Allocator allocator_type;
typedef vector_pool_iterator, X, 1 > iterator;
typedef vector_pool_iterator, const X, 1 > const_iterator;
typedef vector_pool_iterator, X, -1 > reverse_iterator;
typedef vector_pool_iterator, const X, -1 > const_reverse_iterator;
/** Storage space for a single block of objects in pool */
typedef unsigned char block_type[sizeof(X) * block_size];
/** @This creates a new pool with empty storage. */
vector_pool(const Allocator &a = Allocator(),
const PtrAllocator &pa = PtrAllocator())
: _blocks(pa),
_free_count(0),
_static_size(0),
_allocator(a)
{
}
/** @This creates a new pool and provide static storage space for
the first block. */
vector_pool(block_type &first,
const Allocator &a = Allocator(),
const PtrAllocator &pa = PtrAllocator())
: _blocks(pa),
_free_count(block_size),
_static_size(1),
_allocator(a)
{
_blocks.push_back((X*)first);
}
/** @This creates a new pool and provide static storage space for
multiple blocks. */
vector_pool(block_type block[], size_t count,
const Allocator &a = Allocator(),
const PtrAllocator &pa = PtrAllocator())
: _blocks(pa),
_free_count(block_size * count),
_static_size(count),
_allocator(a)
{
for (unsigned int i = 0; i < count; i++)
_blocks.push_back((X*)block[i]);
}
/** @This destroy pool along with contained objects */
~vector_pool()
{
clear();
shrink();
}
/** @This returns reference to object at given position in pool */
const X & operator[](unsigned int i) const
{
return *get_ptr(i);
}
/** @This returns reference to object at given position in pool */
X & operator[](unsigned int i)
{
return *get_ptr(i);
}
/** @This returns reference to object at given position in pool
with bound checking */
const X & at(unsigned int i) const throw (std::out_of_range)
{
if (i >= size())
throw std::out_of_range("vector_pool access out of bounds");
return *get_ptr(i);
}
/** @This returns reference to object at given position in pool
with bound checking */
X & at(unsigned int i) throw (std::out_of_range)
{
if (i >= size())
throw std::out_of_range("vector_pool access out of bounds");
return *get_ptr(i);
}
/** @This allocates and construct a new object in pool */
X &create()
{
return *new(alloc())X();
}
X * create_array(size_t count)
{
X *t = alloc(count);
for (unsigned int i = 0; i < count; i++)
new(t + i)X();
return t;
}
#define _DPP_VECTOR_POOL_CREATE(a, b, ...) \
template <__VA_ARGS__> \
inline X &create a \
{ \
return *new(alloc())X b; \
}
#define _DPP_VECTOR_POOL_CREATE_ARRAY(a, b, ...) \
template <__VA_ARGS__> \
inline X * create_array a \
{ \
X *t = alloc(count); \
for (unsigned int i = 0; i < count; i++) \
new(t + i)X b; \
return t; \
}
/** @multiple
@This allocates and construct a new object in pool. Parameters
are passed to constructor. */
_DPP_VECTOR_POOL_CREATE((const P1 &p1), (p1), typename P1);
_DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2), (p1, p2), typename P1, typename P2);
_DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2, const P3 &p3), (p1, p2, p3),
typename P1, typename P2, typename P3);
_DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2, const P3 &p3,
const P4 &p4),
(p1, p2, p3, p4),
typename P1, typename P2, typename P3,
typename P4);
_DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2, const P3 &p3,
const P4 &p4, const P5 &p5),
(p1, p2, p3, p4, p5),
typename P1, typename P2, typename P3,
typename P4, typename P5);
_DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2, const P3 &p3,
const P4 &p4, const P5 &p5, const P6 &p6),
(p1, p2, p3, p4, p5, p6),
typename P1, typename P2, typename P3,
typename P4, typename P5, typename P6);
/** @multiple
@This allocates and construct multiple objects in pool. Parameters
are passed to constructor. */
_DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1), (p1), typename P1);
_DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2), (p1, p2), typename P1, typename P2);
_DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2, const P3 &p3), (p1, p2, p3),
typename P1, typename P2, typename P3);
_DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2, const P3 &p3,
const P4 &p4),
(p1, p2, p3, p4),
typename P1, typename P2, typename P3,
typename P4);
_DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2, const P3 &p3,
const P4 &p4, const P5 &p5),
(p1, p2, p3, p4, p5),
typename P1, typename P2, typename P3,
typename P4, typename P5);
_DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2, const P3 &p3,
const P4 &p4, const P5 &p5, const P6 &p6),
(p1, p2, p3, p4, p5, p6),
typename P1, typename P2, typename P3,
typename P4, typename P5, typename P6);
/** @This removes last entry. It does not reduce
allocated blocks count. @see shrink */
void pop_back()
{
unsigned int id = _blocks.size() * block_size - ++_free_count;
get_ptr(id)->~X();
}
/** @This destroys all objects in pool. It does not reduce
allocated blocks count. @see shrink */
void clear()
{
int i;
unsigned int j;
for (i = _blocks.size() - 1; i >= 0; i--)
{
for (j = 0; j < block_size - _free_count % block_size; j++)
_blocks[i][j].~X();
_free_count += j;
}
}
/** @This frees unused storage blocks at end of pool. */
void shrink()
{
while (_blocks.size() > _static_size)
{
_allocator.deallocate(_blocks.back(), block_size);
_blocks.pop_back();
_free_count -= block_size;
}
}
/** @This allocates enough storage blocks to hold at least @tt
count objects */
void reserve(size_t count)
{
while (capacity() < count)
add_block();
}
/** @This returns current live objects count in pool */
inline size_t size() const
{
return _blocks.size() * block_size - _free_count;
}
/** @This returns current allocated storage space in objects count unit */
inline size_t capacity() const
{
return _blocks.size() * block_size;
}
/** @This tests pool empty state */
inline bool empty() const
{
return size() == 0;
}
/** @This returns first object in pool */
inline const X & front() const
{
return *_blocks.front();
}
/** @This returns first object in pool */
inline X & front()
{
return *_blocks.front();
}
/** @This returns last object in pool */
inline const X & back() const
{
return *get_ptr(size() - 1);
}
/** @This returns last object in pool */
inline X & back()
{
return *get_ptr(size() - 1);
}
/** @This returns @ref iterator to first object in pool */
inline iterator begin()
{
return iterator(this, 0);
}
/** @This returns end @ref iterator */
inline iterator end()
{
return iterator(this, size());
}
/** @This returns @ref const_iterator to first object in pool */
inline const_iterator begin() const
{
return const_iterator(this, 0);
}
/** @This returns end @ref const_iterator */
inline const_iterator end() const
{
return const_iterator(this, size());
}
/** @This returns @ref reverse_iterator to last object in pool */
inline reverse_iterator rbegin()
{
return reverse_iterator(this, size() - 1);
}
/** @This returns end @ref reverse_iterator */
inline reverse_iterator rend()
{
return reverse_iterator(this, -1);
}
/** @This returns @ref const_reverse_iterator to first object in pool */
inline const_reverse_iterator rbegin() const
{
return const_reverse_iterator(this, size() - 1);
}
/** @This returns end @ref const_reverse_iterator */
inline const_reverse_iterator rend() const
{
return const_reverse_iterator(this, -1);
}
/** @This returns pool object allocator */
const allocator_type & get_allocator() const
{
return _allocator;
}
};
}
#endif