I wrote this memory pool as a code sample for a job interview. It provides a per-class memory pool that can offer faster runtime performance for classes that need to be traversable and (de)allocatable during runtime.
Specifically, it provides in-order traversal of the allocated data blocks, to improve cache effectiveness. Both allocation and deallocation are O(1) operations. Traversal of the allocated blocks is linear in the number of allocated blocks, with a one-time potentially full traversal of the pool upon the first call to begin() after (de)allocation.
The pool stores metadata about the (un)allocated data in two structures both store in a singly linked list. The list of free blocks behaves like a stack: upon an allocation request a single block is popped off the front and upon deallocation a single block is pushed onto it. The list of allocated blocks functions as a singly linked list, and is mainly used for efficient traversal.
Any suggestions? Obvious issues? Glaring mistakes? I'd love to hear them :)
#pragma once
#include <iostream>
#include <iterator>
#include <cassert>
template<class T>
class Pool {
friend class iterator;
private:
struct Node {
T* data;
Node* next;
bool alloc;
};
unsigned int size; ///< The total number of instances that fit in the pool
unsigned int nrOfAllocs; ///< How many instances have been allocated
T* pool; ///< Starting address of the data block
Node* metadata; ///< Storage for the free and allocated block list
Node* firstFree, *firstAlloc; ///< Pointers to the first blocks of both lists
bool dirty; ///< Flag that is set upon (de)allocation, indicates that cleanup() should be called
static Node EndNode; ///< Used by the iterator
public:
class iterator : public std::iterator<std::forward_iterator_tag, T> {
friend class Pool;
public:
bool operator == (iterator const& rhs) const {return node->data == (*rhs);}
bool operator != (iterator const& rhs) const {return node->data != (*rhs);}
bool operator < (iterator const& rhs) const {return node->data < (*rhs);}
bool operator <= (iterator const& rhs) const {return node->data <= (*rhs);}
bool operator > (iterator const& rhs) const {return node->data > (*rhs);}
bool operator >= (iterator const& rhs) const {return node->data >= (*rhs);}
iterator operator ++ () {
node = node->next == nullptr ? &Pool::EndNode : node->next;
return (*this);
}
iterator operator ++ (int){
iterator original(*this);
node = node->next == nullptr ? &Pool::EndNode : node->next;
return original;
}
T* operator * () const {
return node->data;
}
private:
iterator(Pool::Node* node):node(node){}
Pool::Node* node;
};
class const_iterator : public std::iterator<std::forward_iterator_tag, const T> {
friend class Pool;
public:
bool operator == (const_iterator const& rhs) const {return node->data == (*rhs);}
bool operator != (const_iterator const& rhs) const {return node->data != (*rhs);}
bool operator < (const_iterator const& rhs) const {return node->data < (*rhs);}
bool operator <= (const_iterator const& rhs) const {return node->data <= (*rhs);}
bool operator > (const_iterator const& rhs) const {return node->data > (*rhs);}
bool operator >= (const_iterator const& rhs) const {return node->data >= (*rhs);}
const_iterator operator ++ () {
node = node->next == nullptr ? &Pool::EndNode : node->next;
return (*this);
}
const_iterator operator ++ (int){
const_iterator original(*this);
node = node->next == nullptr ? &Pool::EndNode : node->next;
return original;
}
const T* operator * () const {
return node->data;
}
private:
const_iterator(Pool::Node* node):node(node){}
Pool::Node* node;
};
/** \note Calling begin() triggers a potentially full traversal of the pool after a (de)allocation. */
iterator begin() {
cleanup();
if ( firstAlloc == nullptr )
return iterator(&Pool<T>::EndNode);
return iterator(firstAlloc);
}
iterator end() const {
return iterator(&Pool<T>::EndNode);
}
/** \param size Integer representing the number of instances that should be able to fit in the pool. */
Pool(unsigned int size = 1024):size(size),nrOfAllocs(0),dirty(false),firstAlloc(nullptr) {
// Allocate pool and metadata
pool = static_cast<T*>(malloc(size * sizeof(T)));
metadata = new Node[size];
firstFree = &metadata[0];
assert(firstFree != nullptr);
// Initialise nodes
for ( int i = 0; i < size; ++i ) {
metadata[i].data = pool + i;
metadata[i].next = &metadata[i+1];
assert(metadata[i].next != nullptr);
metadata[i].alloc = false;
}
metadata[size-1].next = nullptr;
// Setup end node
Pool::EndNode.data = pool + size;
}
~Pool() {
free(pool);
delete[] metadata;
}
/// Called by new. Pops a free block, marks it and returns the associated pool address
T* alloc() {
// Check if we have free blocks left
if ( firstFree == nullptr ) {
std::cout << "Pool out of memory!" << std::endl;
abort();
}
// Pop front free node
Node* n = firstFree;
firstFree = n->next;
// Set metadata
n->alloc = true;
++nrOfAllocs;
dirty = true;
// Fix head
if ( firstAlloc == nullptr || firstAlloc->data > n->data )
firstAlloc = n;
return n->data;
}
/// Called by delete. Marks the block as unused, and pushes it on the free list.
void free(void* block) {
// Get node
T* data = static_cast<T*>(block);
int i = data - pool;
assert(i >= 0 && i < size);
Node* n = &metadata[i];
assert(n->data == block);
// Fix head
if ( firstAlloc == n )
firstAlloc = n->next;
// Return node to free list
n->next = firstFree;
firstFree = n;
// Set metadata
n->alloc = false;
--nrOfAllocs;
dirty = true;
}
/// Called by begin if the pool is marked as dirty. Recreates the linked list for allocated blocks for efficient traversal.
void cleanup() {
if ( dirty && nrOfAllocs > 0 ) {
int allocsFound = 0;
int i = firstAlloc->data - pool;
Node* n = firstAlloc;
// Only search within the range we know has allocated blocks
while ( allocsFound < nrOfAllocs && (i+1) < size ) {
if ( metadata[i+1].alloc ) {
++allocsFound;
n->next = &metadata[i+1];
assert(n->next != nullptr);
n = &metadata[i+1];
}
++i;
}
n->next = nullptr;
dirty = false;
}
}
};
template <class T>
typename Pool<T>::Node Pool<T>::EndNode = {nullptr, nullptr, false};
