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?
#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};
