Chris M. Thomasson
11/19/2008 4:39:00 PM
I fix some nasty exception safety issues that exist in the initial version
by removing dependence on `std::list'. I implement a trivial intrusive
circular doubly linked-list instead. Every operation is guaranteed not to
throw. Also, it improves efficiency because regions are now nodes.
Therefore, nodes do not need to be separately allocated. This is one
advantage intrusive containers have over the STL. Anyway, here is the code:
______________________________________________________________________
#include <cassert>
#include <cstdlib>
#include <new>
template<typename T>
struct dlink {
dlink* m_next;
dlink* m_prev;
void ctor() {
m_next = m_prev = this;
}
private:
inline static void prv_insert(
dlink* n,
dlink* prev,
dlink* next
) throw() {
next->m_prev = n;
n->m_next = next;
n->m_prev = prev;
prev->m_next = n;
}
inline static void prv_remove(
dlink* prev,
dlink* next
) throw() {
next->m_prev = prev;
prev->m_next = next;
}
public:
inline void push_head(dlink* n) throw() {
prv_insert(n, this, m_next);
}
inline void push_tail(dlink* n) throw() {
prv_insert(n, m_prev, this);
}
inline void pop() throw() {
prv_remove(m_prev, m_next);
}
inline T* get() throw() {
return (T*)this;
}
};
template<typename T, std::size_t BUFDEPTH = 1024>
class region_allocator {
struct region : dlink<region> {
T m_buf[BUFDEPTH];
std::size_t m_idx;
void ctor() {
m_idx = 0;
}
void dtor() {
for (std::size_t i = 0; i < m_idx; ++i) {
m_buf[i].~T();
}
}
void* allocate() {
std::size_t const idx = m_idx;
if (idx + 1 > BUFDEPTH) {
return NULL;
}
return (void*)&m_buf[idx];
}
void commit() {
++m_idx;
}
void flush() {
dtor();
ctor();
}
};
dlink<region> m_regions;
struct allocation {
region* m_region;
void* m_mem;
};
region* prv_expand(){
region* r = (region*)std::malloc(sizeof(*r));
if (! r) {
throw std::bad_alloc();
};
r->ctor();
m_regions.push_head(r);
return r;
}
inline void prv_allocate(allocation& a) {
region* r = m_regions.m_next->get();
while (r != &m_regions) {
a.m_mem = r->allocate();
if (a.m_mem) {
a.m_region = r;
return;
}
r = r->m_next->get();
}
a.m_region = prv_expand();
a.m_mem = a.m_region->allocate();
}
#define REGION_PRV_ALLOCATE(mp_params) allocation a; prv_allocate(a); T* const obj = new (a.m_mem) T mp_params; a.m_region->commit(); return obj
public:
struct flush_guard {
region_allocator& m_ralloc;
public:
flush_guard(region_allocator& ralloc) : m_ralloc(ralloc) {
}
~flush_guard() {
m_ralloc.flush();
}
};
region_allocator() {
m_regions.ctor();
prv_expand();
}
~region_allocator() {
flush();
std::free(m_regions.m_next->get());
}
void flush() {
region* r = m_regions.m_next->get();
if (r->m_next != &m_regions) {
r = r->m_next->get();
while (r != &m_regions) {
region* rn = r->m_next->get();
r->pop();
r->dtor();
std::free(r);
r = rn;
}
}
m_regions.m_next->get()->flush();
}
inline T* allocate() {
REGION_PRV_ALLOCATE(());
}
template<typename P1>
inline T* allocate(P1 p1) {
REGION_PRV_ALLOCATE((p1));
}
template<typename P1, typename P2>
inline T* allocate(P1 p1, P2 p2) {
REGION_PRV_ALLOCATE((p1, p2));
}
template<typename P1, typename P2, typename P3>
inline T* allocate(P1 p1, P2 p2, P3 p3) {
REGION_PRV_ALLOCATE((p1, p2, p3));
}
// [and on and on for more params...];
};
/* Usage Example
______________________________________________________________*/
#include <cstdio>
#include <string>
class foo {
unsigned const m_id;
public:
foo(unsigned const id) : m_id(id) {
std::printf("(%p)->foo::foo(%u)\n", (void*)this, id);
}
~foo() {
std::printf("(%p)->foo::~foo() - %u\n", (void*)this, m_id);
}
};
class foo2 {
unsigned const m_id;
std::string const m_name;
public:
foo2(unsigned const id, std::string const name)
: m_id(id), m_name(name) {
std::printf("(%p)->foo2::foo2(%u, %s)\n",
(void*)this, id, name.c_str());
}
~foo2() {
std::printf("(%p)->foo2::~foo2() - %u, %s\n",
(void*)this, m_id, m_name.c_str());
}
};
struct node {
node* m_next;
node(node* next) : m_next(next) {
std::printf("(%p)->node::node(%p)\n",
(void*)this, (void*)next);
}
~node() {
std::printf("(%p)->node::~node(%p)\n",
(void*)this, (void*)m_next);
}
};
int main() {
{
region_allocator<foo, 2> foo_alloc;
{
region_allocator<foo, 2>::flush_guard fguard(foo_alloc);
foo* f1 = foo_alloc.allocate(1);
foo* f2 = foo_alloc.allocate(2);
foo* f3 = foo_alloc.allocate(3);
foo* f4 = foo_alloc.allocate(4);
foo* f5 = foo_alloc.allocate(5);
foo* f6 = foo_alloc.allocate(6);
}
foo* f1 = foo_alloc.allocate(5);
foo* f2 = foo_alloc.allocate(6);
foo* f3 = foo_alloc.allocate(7);
foo* f4 = foo_alloc.allocate(8);
{
region_allocator<foo2> foo2_alloc;
foo2* f2_1 = foo2_alloc.allocate(123, "Chris");
foo2* f2_2 = foo2_alloc.allocate(456, "John");
foo2* f2_3 = foo2_alloc.allocate(789, "Amy");
foo2* f2_4 = foo2_alloc.allocate(777, "Kim");
foo2* f2_5 = foo2_alloc.allocate(999, "Jane");
}
{
region_allocator<unsigned, 64> int_alloc;
unsigned* a1 = int_alloc.allocate(1);
unsigned* a2 = int_alloc.allocate(2);
unsigned* a3 = int_alloc.allocate(3);
unsigned* a4 = int_alloc.allocate();
*a4 = 123456789;
std::printf("%u - %u - %u - %u\n", *a1, *a2, *a3, *a4);
}
}
{
region_allocator<node, 10> node_alloc;
node* head = NULL; // linked-list
// fill
for (unsigned i = 0; i < 14; ++i) {
node* n = node_alloc.allocate(head);
head = n;
}
// empty list
head = NULL;
node_alloc.flush();
// refill
for (unsigned i = 0; i < 15; ++i) {
node* n = node_alloc.allocate(head);
head = n;
}
}
return 0;
}
______________________________________________________________________
Well, what do you think of it? IMVHO, I think it can be a fairly useful tool
indeed. How can I make any further improvements?
Thanks.