Here is an attempt at implementing a fixed size Memory Pool1:
pool.h
#ifndef Pool_h
#define Pool_h
template <typename T, size_t N> // memory type, number of blocks
class Pool
{
protected:
typedef T* pointer_type;
typedef const T* const_pointer_type;
typedef size_t size_type;
public:
Pool(); // default constructor
~Pool(); // destructor
pointer_type AddrFromIndex(size_type i) const; // address of i-th block
size_type IndexFromAddr(const_pointer_type ptr) const; // subscript operator [ ]
pointer_type get(); // get a memory block
void free(pointer_type ptr, size_type size = 0); // free a memory block
private:
size_type num_of_blocks; // number of identical memory blocks
size_type size_of_each_block; // size of each(every) memory block
size_type num_of_free_blocks; // number of free blocks
size_type num_of_init_blocks; // number of blocks been allocated
pointer_type data; // base(start) address of memory
pointer_type next; // next free memory block
};
#include "pool_def.cpp"
#endif
pool_def.cpp
//----------------------------------------------------------------------
template <typename T, size_t N>
Pool<T, N>::Pool()
: num_of_blocks(N), size_of_each_block(sizeof(T)),
num_of_free_blocks(N), num_of_init_blocks(0),
data (new T[N]), next(data)
{
}
//----------------------------------------------------------------------
template <typename T, size_t N>
Pool<T, N>::~Pool()
{
delete [] data;
data = nullptr;
}
//----------------------------------------------------------------------
template <typename T, size_t N>
typename Pool<T, N>::pointer_type Pool<T, N>::AddrFromIndex(size_type i) const
{
return data + (i * size_of_each_block);
}
//----------------------------------------------------------------------
template <typename T, size_t N>
typename Pool<T, N>::size_type Pool<T, N>::IndexFromAddr(const_pointer_type ptr) const
{
return ((size_type)(ptr - data)) / size_of_each_block;
}
//----------------------------------------------------------------------
template <typename T, size_t N>
typename Pool<T, N>::pointer_type Pool<T, N>::get()
{
if (num_of_init_blocks < num_of_blocks)
{
pointer_type p = (pointer_type) AddrFromIndex(num_of_init_blocks);
*p = num_of_init_blocks + 1;
++num_of_init_blocks;
}
pointer_type ptr = nullptr;
if (num_of_free_blocks > 0)
{
ptr = next;
--num_of_free_blocks;
if (num_of_free_blocks != 0)
{
next = AddrFromIndex(*((pointer_type)next) );
}
else
{
next = nullptr;
}
}
return ptr;
}
//----------------------------------------------------------------------
template <typename T, size_t N>
void Pool<T, N>::free(pointer_type ptr, size_type size = 0)
{
if (next != nullptr)
{
(*(size_type*)ptr) = IndexFromAddr( next );
next = (pointer_type)ptr;
}
else
{
*((size_type*)ptr) = num_of_blocks;
next = (pointer_type)ptr;
}
++num_of_free_blocks;
}
//----------------------------------------------------------------------
Any remarks and corrections are welcome.
Questions:
If I want to implement a data structure2 based on dynamic array: When I allocate an array of type
T
, of let sayN
elements, I'm able to do it by callingget()
only once. Then by using simple pointer arithmetic (or subscriptoperator[]
) I can access all the elements without the use ofget()
:#include <iostream> #include "Pool.h" int main() { Pool<int, 100> p2; int* ptr2 = p2.get(); for (size_t i = 0; i < 100; i++) { // ptr2[i] = p2.get(); <-----------------? ptr2[i] = i; } for (size_t i = 0; i < 100; i++) { std::cout << ptr2[i] <<" "; } // for loop on every element of the array or just as it is? p2.free(ptr2); }
Is the above a correct/valid use of Pool
or should I call get()
on every next, ptr2[i]
, element before I assign it a value?
- I use
Pool::free()
to deallocate the chunk of100 int
s, is it a valid use or should I apply it on every single element of the array?
Note: The Pool
is meant to be used, in the context of embedded systems programming, as an alternative of system functions/operators like malloc()
or new
/ new []
related to free store - fragmentation, speed, predictability.
1. Based on: "Fast Efficient Fixed-Size Memory Pool - no loops and no overhead." B. Kenwright
2. Let say a simple vector
.
Note: The original code uses the first four bytes (unsigned int
) of every free memory block to store the address of the following free block of memory. This address is used to update the variable next
which is a pointer to the next free memory block. The stored value is not actually an address but the variable num_of_init_blocks
, which, additionally, is used as an index of the sequence of allocation of free memory blocks. num_of_init_blocks
is used as an offset from the data
, which is the base address.
typedef
s protected? \$\endgroup\$public
. \$\endgroup\$Allocator
based onPool
. I've read it (upvote it) in the past few days. The use ofstd::vector
as a member (which implicitly uses the operatorsPool
is created as an alternative to) confused me. \$\endgroup\$