This is a fairly straightforward object allocator/factory, which sets up a stack of freed nodes as a linked list in the unused part of the storage. I would appreciate any and all feedback you may have.
A few things of note:
- This is not intended to be a
std::allocatordrop-in replacement. - I'm kind of iffy on the
ALLOC_Ttemplate parameter. It feels like it could be become annoying to use, but I need to add a trait type to manageentry_totherwise (because of the default template parameter value). I'm definitely up for suggestions on that front. - My code does not currently actively use the move constructor/assignment beyond unit tests, and I'm on the fence about them. They subjectively feel like a potential minefield if misused, but potentially usefull during initialization. I'd like opinions on that.
- I am mildly worried about strict aliasing violations since I'm being kinda cute with the
entry_tunion, recycling unused objects to maintain the free list. I'm pretty sure everything is fine, but I'd like a sanity check on that specific front. - If this code is bug-free, there should be no usage of the public interface of this class that could cause any of the asserts to fire.
- Allocating and freeing is currently a hard O(1) and I like it this way.
- I didn't bother with
noexcept, should I have?
Here's the code:
#include <cassert>
#include <utility>
#include <vector>
template<typename T, template<typename> typename ALLOC_T=std::allocator>
class Arena {
public:
using allocator_t = ALLOC_T<T>;
using storage_t = std::aligned_storage<sizeof(T), alignof(T)>;
union entry_t {
storage_t storage;
size_t next_free;
};
Arena(std::size_t count, const allocator_t& alloc=allocator_t())
: storage_(count, alloc) {}
Arena(Arena const&) = delete;
Arena& operator=(Arena const&) = delete;
Arena(Arena&& rhs)
: storage_(std::move(rhs.storage_)),
alloc_count_(rhs.alloc_count_),
free_stack_top_(rhs.free_stack_top_) {
rhs.alloc_count_ = 0;
rhs.free_stack_top_ = npos;
}
Arena& operator=(Arena&& rhs) {
storage_ = std::move(rhs.storage_);
alloc_count_ = rhs.alloc_count_;
free_stack_top_ = rhs.free_stack_top_;
rhs.alloc_count_ = 0;
rhs.free_stack_top_ = npos;
}
template<typename... ARGS>
T* create(ARGS&&... args) {
// Find the slot we will allocate from.
entry_t* selected_entry = nullptr;
if (free_stack_top_ != npos) {
// If the free list is not empty, pick from it.
assert(free_stack_top_ < storage_.size());
selected_entry = &storage_[free_stack_top_];
// Update the free list
free_stack_top_ = selected_entry->next_free;
assert(free_stack_top_ < storage_.size() || free_stack_top_ == npos);
}
else {
// Pick from the end of the currently allocated block, which is currently contiguous.
if (alloc_count_ == storage_.size()) {
throw std::bad_alloc();
}
assert(alloc_count_ < storage_.size());
selected_entry = &storage_[alloc_count_];
}
try {
selected_entry->storage = storage_t();
T* result = new(&selected_entry->storage) T(std::forward<ARGS>(args)...);
++alloc_count_;
return result;
}
catch(...) {
// If T's constructor throws, cancel the allocation
selected_entry->next_free = free_stack_top_;
free_stack_top_ = getId_(selected_entry);
throw;
}
}
void destroy(T* what) {
what->~T();
auto as_storage = reinterpret_cast<storage_t*>(what);
auto as_entry = reinterpret_cast<entry_t*>(as_storage);
auto index = getId_(as_entry);
// Insert the freed node on the free stack
storage_[index].next_free = free_stack_top_;
free_stack_top_ = index;
--alloc_count_;
}
size_t capacity() const {
return storage_.size();
}
bool full() const {
return alloc_count_ == capacity();
}
private:
// returns the index of a given storage entry.
size_t getId_(entry_t* storage_entry) {
assert(storage_entry >= &storage_.front() && storage_entry <= &storage_.back());
return storage_entry - &storage_[0];
}
static const size_t npos = -1;
std::vector<entry_t, allocator_t> storage_;
size_t alloc_count_ = 0;
size_t free_stack_top_ = npos;
};
Example usage:
#include <iostream>
struct test {
int i_;
test(int i) : i_(i) {
std::cout << i << " created at: " << this << std::endl;
}
~test() {
std::cout << i_ << " destroyed" << std::endl;
}
};
int main() {
simpleobj::Arena<test> arena(12);
int i = 0;
auto a = arena.create(i++);
auto b = arena.create(i++);
auto c = arena.create(i++);
auto d = arena.create(i++);
arena.destroy(b);
arena.destroy(c);
auto e = arena.create(i++);
arena.destroy(a);
auto f = arena.create(i++);
auto g = arena.create(i++);
try {
for (int i = 0; i < 100; ++i) {
arena.create(i++);
}
}
catch (std::exception& e) {
std::cout << e.what() << std::endl;
}
return 0;
}