I'm working on a C++ custom memory allocator, that would be kind of a replacement for the C flexible array syntax, you know, the stuff like that:
struct C_Arena
{
struct Header header;
size_t size;
size_t used;
char* data[];
};
...
struct C_Arena *arena = malloc(1000);
arena->size = 1000 - sizeof(struct C_flexible_array_struct));
arena->used = 0;
struct Header *header = &arena->header;
...
I want to have this in C++ like this:
auto arena = Chunk<Header>(new char[1000], 1000);
Header *header = arena.Get<Header>();
...
I'm not an expert C++ programmer. I had to learn a lot while I've been working on this problem. I probably made some mistakes. In particular I didn't think ahead about exception safety of my code. I'd like to get an advice on how to amend this problem. And any other suggestions on improving my code are welcome.
Please note that this is a low level allocator. Its interface is not compatible with libc++ requirements. I am going to add a libc++-compatible wrapper for this one as a separate class.
So far I have the following:
// Round down to a power of two multiple.
constexpr std::size_t Align(std::size_t n, std::size_t a) {
return n & ~(a - 1);
}
// Round up to a power of two multiple.
constexpr std::size_t AlignUp(std::size_t n, std::size_t a) {
return Align(n + a - 1, a);
}
namespace memory {
namespace detail {
// Calculate a data item alignment according to its size.
constexpr std::size_t Align(std::size_t size, std::size_t offset) {
return size < 0x08 ? ::AlignUp(offset, 0x04)
: size < 0x10 ? ::AlignUp(offset, 0x08)
: ::AlignUp(offset, 0x10);
}
// Services for placement of a given type instance within a memory chunk
// at the specified offset.
template <typename T, std::size_t S> class EntryLayout {
public:
using Type = T;
using Pointer = T *;
static constexpr std::size_t Size = sizeof(Type);
static constexpr std::size_t Offset = Align(Size, S);
static constexpr std::size_t EndOffset = Offset + Size;
static Pointer Instance(char *ptr) {
return reinterpret_cast<Pointer>(RawData(ptr));
}
template <typename... Args>
static Pointer Construct(char *ptr, Args &&... args) {
return new (RawData(ptr)) Type(std::forward<Args>(args)...);
}
static void Destruct(char *ptr) { Instance(ptr)->~Type(); }
private:
static char *RawData(char *ptr) { return ptr + Offset; }
};
// Services for placement of a number of types within a memory
// chunk at the specified offset.
template <std::size_t S, typename... Tail> class ChunkLayout {
public:
static constexpr std::size_t StartOffset = S;
static constexpr std::size_t EndOffset = S;
template <typename... Args> static void Construct(char *, Args...) {}
static void Destruct(char *) {}
};
// Recursive template specialization of the above.
template <std::size_t S, typename Head, typename... Tail>
class ChunkLayout<S, Head, Tail...>
: public ChunkLayout<EntryLayout<Head, S>::EndOffset, Tail...> {
public:
using EntryType = Head;
using HeadLayout = EntryLayout<Head, S>;
using TailLayout = ChunkLayout<HeadLayout::EndOffset, Tail...>;
static constexpr std::size_t StartOffset = S;
static constexpr std::size_t EndOffset = TailLayout::EndOffset;
static typename HeadLayout::Pointer Instance(char *ptr) {
return HeadLayout::Instance(ptr);
}
template <typename... Args> void Construct(char *ptr, Args... args) {
HeadLayout::Construct(ptr, args...);
TailLayout::Construct(ptr, args...);
}
void Destruct(char *ptr) {
TailLayout::Destruct(ptr);
HeadLayout::Destruct(ptr);
}
};
} // namespace detail
// Control of memory chunk free and used space.
class ChunkSpace {
public:
ChunkSpace(std::size_t size) noexcept : free_{size}, used_(0) {}
std::size_t Used() const { return used_; }
std::size_t Free() const { return free_; }
std::size_t Size() const { return free_ + used_; }
bool Alloc(std::size_t size) {
if (size > free_)
return false;
free_ -= size;
used_ += size;
return true;
}
void Reset(std::size_t size = 0) {
assert(size <= used_);
free_ = free_ + used_ - size;
used_ = size;
}
private:
std::size_t free_;
std::size_t used_;
};
template <typename... EntryType>
class Chunk : public detail::ChunkLayout<0, ChunkSpace, EntryType...> {
using Layout = detail::ChunkLayout<0, ChunkSpace, EntryType...>;
public:
Chunk(char *data, std::size_t size) : data_{data} {
assert(size > Layout::EndOffset);
// Construct ChunkSpace instance to bootstrap allocation.
Layout::HeadLayout::Construct(data_, size);
// Allocate space required for all the chunk data.
Alloc(Layout::EndOffset);
// Construct the rest of the chunk data.
Layout::TailLayout::Construct(data_);
}
~Chunk() {
Layout::Destruct(data_);
}
template <typename T>
T* Get() {
return decltype(Upcast<T>(this))::Instance(data_);
}
template <typename T>
const T* Get() const {
return decltype(Upcast<T>(this))::Instance(data_);
}
std::size_t Used() const { return Get<ChunkSpace>()->Used(); }
std::size_t Free() const { return Get<ChunkSpace>()->Free(); }
std::size_t Size() const { return Get<ChunkSpace>()->Size(); }
void *Allocate(std::size_t size) {
std::size_t offset = Used();
std::size_t aligned_offset = detail::Align(size, offset);
std::size_t offset_padding = aligned_offset - offset;
if (!Alloc(size + offset_padding))
return nullptr;
return data_ + aligned_offset;
}
private:
bool Alloc(std::size_t size) {
return Get<ChunkSpace>()->Alloc(size);
}
// Some C++ magic to upcast to the base class that contains layout info
// for a given entry type.
template <typename Head, std::size_t S, typename... Tail>
static typename detail::ChunkLayout<S, Head, Tail...>::HeadLayout
Upcast(const detail::ChunkLayout<S, Head, Tail...> *);
char *data_;
};
} // namespace memory
To make clear how this code is going to be used, here is a more elaborated example:
#include "chunk.h"
#include "iostream"
struct A {
int value = 0xa;
};
struct B {
int value = 0xb;
};
int main() {
char buffer[1024];
// Create a memory chunk with 2 embedded structs.
memory::Chunk<A, B> chunk(buffer, sizeof buffer);
// Get and use the embedded structs.
A *a = chunk.Get<A>();
B *b = chunk.Get<B>();
std::cout << std::hex;
std::cout << "a: " << a->value << " b: " << b->value << std::endl;
std::cout << std::dec;
// Allocate a memory block within the chunk.
void *p = chunk.Allocate(200);
// Do whatever you like with the block.
memset(p, 0, 200);
// ...
return 0;
}
