template<typename T, std::size_t BUFDEPTH = 1024>
class region_allocator {
struct 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();
}
};
std::list<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_front(r);
return r;
}
inline void prv_allocate(allocation* const a) {
typename std::list<region*>::iterator i;
for (i = m_regions.begin(); i != m_regions.end(); ++i) {
a->m_mem = (*i)->allocate();
if (a->m_mem) {
a->m_region = (*i);
return;
}
}
a->m_region = prv_expand();
a->m_mem = a->m_region->allocate();
assert(a->m_mem);
}
#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) {
m_ralloc.flush();
}
~flush_guard() {
m_ralloc.flush();
}
};
region_allocator() {
prv_expand();
}
~region_allocator() {
flush();
std::free(m_regions.front());
m_regions.pop_front();
}
void flush() {
std::size_t const depth = m_regions.size();
for (std::size_t i = 1; i < depth; ++i) {
region* const r = m_regions.back();
r->dtor();
std::free(r);
m_regions.pop_back();
}
m_regions.front()->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(void) {
{
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* 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> node_alloc;
node* head = NULL; // linked-list
// fill
for (unsigned i = 0; i < 512; ++i) {
node* n = node_alloc.allocate(head);
head = n;
}
// empty list
head = NULL;
node_alloc.flush();
// refill
for (unsigned i = 0; i < 2048; ++i) {
node* n = node_alloc.allocate(head);
head = n;
}
}
return 0;
}
___________________________________________________________________
Notice how there are no explicit calls to a per-object deallocation
function? The `region_allocator<T, ...>::flush_guard' object uses RAII to
automatically invoke the `region_allocator<T, ...>::flush()' procedure which
calls the dtor of all contained objects and automatically frees excess
region memory. One nice thing is that it allows one to pass variable number
of arguments to the objects ctor.
Also, please take notice of how I can create a linked-list, and simple call
`flush()' to automatically destroy all of its nodes _without_ explicitly
traversing it. IMVHO, that ability can come in handy.
Well, what do you think of the initial design? Is it crap? How would you
improve it?
Thanks for all of your time! I really do appreciate it.
:^)
ARGHH23$#@$@#!!!!
DAMNIT!!!!
Okay, I make error here... The call to flush should NOT be in the darn ctor
of the `flush_guard' object!
Sorry about that non-sense!
[...]
Here is full fixed code:
______________________________________________________________________
void commit() {
++m_idx;
}
void flush() {
dtor();
ctor();
}
};
std::list<region*> m_regions;
public:
flush_guard(region_allocator& ralloc) : m_ralloc(ralloc) {
}
~flush_guard() {
m_ralloc.flush();
}
};
region_allocator() {
prv_expand();
}
inline T* allocate() {
REGION_PRV_ALLOCATE(());
}
struct node {
node* m_next;
{
region_allocator<unsigned, 64> int_alloc;
*a4 = 123456789;
return 0;
}
______________________________________________________________________
Sorry about that stupid non-sense!
;^(....
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(());
}
struct node {
node* 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.
How do you deallocate (so that deallocated elements can be reused by
further allocations)?
Region allocation forbids one from deallocating individual objects; you can
only deallocate all previously allocated objects. The
`region_allocator<...>::flush()' procedure does just that. This is a major
limitation inherent in basically any region-based allocators. However, Emery
Berger has created a workaround which combines region and heap allocation
and named the algorithm "Reaps":
http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf
You can free individual objects back to a reap. You can also free all
previously allocated objects in a reap in one shot.
IMVHO, region allocation has its place. It can help get rid of memory leaks,
and provides certain conveniences. For instance, you don't need to traverse
a custom collection just to delete all objects therein. Instead, you can set
the collection to an empty state, and flush its region and all of the dtors
for its previously contained objects will fire. Take the following into
account:
http://groups.google.com/group/comp.lang.c++/msg/e8419704ab8c471d
http://groups.google.com/group/comp.lang.c++/msg/d23c3b7d353bd3d9
Here is how one could implement partitioned region allocation as shown in
the C pseudo-code contained within the latter link:
_______________________________________________________________________
// [snip region allocator code]
/* Region Partition Usage Example
______________________________________________________________*/
#include <cstdio>
template<typename T, std::size_t BUFDEPTH = 1024>
class partition_allocator {
public:
typedef region_allocator<T, BUFDEPTH> partition;
private:
struct node {
node* m_next;
partition m_partition;
};
region_allocator<node, 1> m_palloc;
node* m_partitions;
public:
partition_allocator() : m_partitions(NULL) {}
partition* allocate() {
node* const n = m_palloc.allocate();
n->m_next = m_partitions;
m_partitions = n;
return &n->m_partition;
}
void flush() {
node* n = m_partitions;
while (n) {
n->m_partition.flush();
n = n->m_next;
}
}
};
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(void) {
{
unsigned i, r;
partition_allocator<node> npalloc;
partition_allocator<node>::partition& l1alloc = *npalloc.allocate();
partition_allocator<node>::partition& l2alloc = *npalloc.allocate();
partition_allocator<node>::partition& l3alloc = *npalloc.allocate();
node* list1 = NULL;
node* list2 = NULL;
node* list3 = NULL;
for (r = 0; r < 3; ++r) {
// fill list 1
std::puts("filling list 1...");
for (i = 0; i < 10; ++i) {
node* n = l1alloc.allocate(list1);
list1 = n;
}
// fill list 2
std::puts("\n\nfilling list 2...");
for (i = 0; i < 10; ++i) {
node* n = l2alloc.allocate(list2);
list2 = n;
}
// fill list 3
std::puts("\n\nfilling list 3...");
for (i = 0; i < 10; ++i) {
node* n = l3alloc.allocate(list3);
list3 = n;
}
// destroy list 1 in a single shot
list1 = NULL;
std::puts("\n\ndestroy list 1 in one call...");
l1alloc.flush();
// refill list 1
std::puts("\n\nrefilling list 1...");
for (i = 0; i < 10; ++i) {
node* n = l1alloc.allocate(list1);
list1 = n;
}
// destroy lists 1, 2 and 3 in a single shot
list1 = list2 = list3 = NULL;
std::puts("\n\ndestroy list 1, 2 and 3 in one call...");
npalloc.flush();
}
}
return 0;
}
_______________________________________________________________________
As you can see, each list has its own "slave" region_allocator derived from
the "master" partition_allocator. You can destroy all the nodes for a given
list by simply flushing its region_allocator. Or, you can destroy all the
nodes from all the lists by flushing the "master" partition_allocator. Do
you think this is useful at all? Humm...
Then what's the point? You can't substitute new/malloc with such a
thing. The whole idea is that you should be able to destroy and
deallocate objects.
If you never deallocate anything, you may as well just use a
deque-style data container as your allocator, always appending newly
allocated memory blocks at the end.
Did you read the paper I linked to? It explains the benefits and caveats of
region allocation. Surely you must be familiar with this type of allocation
scheme. Its been around for a long time.
> You can't substitute new/malloc with such a thing.
You can substitute new/malloc, however, you "generally" cannot substitute
delete/free. Region allocation API would look like:
new/malloc
delete_all/free_all
Here is a multi-threaded region allocator I did which is used by overloaded
global new/delete operators:
http://webpages.charter.net/appcore/vzoom/malloc/sergey_vzmem_thread.html
I did this for fun. It still suffers from the same caveats. If you notice, a
call to delete simply decrements a counter, and destroys the owning region
when it hits zero.
> The whole idea is that you should be able to destroy and
> deallocate objects.
You can deallocate objects. Just all the objects at once.
> If you never deallocate anything,
You can deallocate all objects in one shot. That's the point of region
allocation. Have you looked at my code and some of the example uses?
> you may as well just use a
> deque-style data container as your allocator, always appending newly
> allocated memory blocks at the end.
I don't want to explicitly allocate memory for each individual object. I
want a slab of memory which can hold multiple objects. Have you looked at my
code yet? Please examine it. I build a region of raw memory which can hold a
number of objects. I call there ctors on demand, and only call the dtors of
all previously allocated objects when the user flushes the region.
#include <cstdio>
class foo {
foo* const m_other;
public:
foo() : m_other(NULL) {
std::printf("(%p)->foo::foo()\n", (void*)this, NULL);
}
foo(foo* const f) : m_other(f) {
std::printf("(%p)->foo::foo(%p)\n", (void*)this, (void*)f);
}
~foo() {
if (m_other) {
m_other->oops();
}
std::printf("(%p)->foo::~foo() - %p\n",
(void*)this, (void*)m_other);
}
void oops() {
std::printf("(%p)->foo::oops() - %p\n",
(void*)this, (void*)m_other);
}
};
int main() {
{
region_allocator<foo> foo_alloc;
foo* f1 = foo_alloc.allocate();
foo* f2 = foo_alloc.allocate(f1);
foo_alloc.flush();
std::puts("_________________________________________");
region_allocator<foo> foo_alloc_other;
f1 = foo_alloc_other.allocate();
f2 = foo_alloc.allocate(f1);
foo_alloc.flush();
foo_alloc_other.flush();
}
return 0;
}
______________________________________________________________________
Here is the output I get:
(003E4B98)->foo::foo()
(003E4B9C)->foo::foo(003E4B98)
(003E4B98)->foo::~foo() - 00000000
(003E4B98)->foo::oops() - 00000000
(003E4B9C)->foo::~foo() - 003E4B98
_________________________________________
(003E6BB8)->foo::foo()
(003E4B98)->foo::foo(003E6BB8)
(003E6BB8)->foo::oops() - 00000000
(003E4B98)->foo::~foo() - 003E6BB8
(003E6BB8)->foo::~foo() - 00000000
YIKES! Take note of the first section: Notice how foo(003E4B98) gets dtor'd
in line 3, but its member function `foo::oops()' get invoked from
foo(003E4B9C) in line 4? This is bad. It can cause undefined behavior, or it
can simply seg-fault if the region that foo(003E4B98) belonged to was
already freed.
Now take not of the second section: Notice how the member function
`foo::oops()' gets invoked on a valid object? This is because both objects
belong to different regions, and they get destroyed in the proper order.
I am very sorry for not mentioning the massive caveat earlier. Although, one
can most certainly make this exact same mistake with new/delete; example:
______________________________________________________________________
#include <cstdio>
class foo {
foo* const m_other;
public:
foo() : m_other(NULL) {
std::printf("(%p)->foo::foo()\n", (void*)this, NULL);
}
foo(foo* const f) : m_other(f) {
std::printf("(%p)->foo::foo(%p)\n", (void*)this, (void*)f);
}
~foo() {
if (m_other) {
m_other->oops();
}
std::printf("(%p)->foo::~foo() - %p\n",
(void*)this, (void*)m_other);
}
void oops() {
std::printf("(%p)->foo::oops() - %p\n",
(void*)this, (void*)m_other);
}
};
int main() {
{
foo* f1 = new foo();
foo* f2 = new foo(f1);
delete f1;
delete f2;
}
return 0;
}
______________________________________________________________________
output:
(003E4B10)->foo::foo()
(003E2BB0)->foo::foo(003E4B10)
(003E4B10)->foo::~foo() - 00000000
(003E4B10)->foo::oops() - 00000000
(003E2BB0)->foo::~foo() - 003E4B10
You have just got to be very careful!
:^o
Which is precisely the reason why you can't substitute new/malloc with
such a thing: You can never free any object, unless you free all objects.
>> you may as well just use a
>> deque-style data container as your allocator, always appending newly
>> allocated memory blocks at the end.
>
> I don't want to explicitly allocate memory for each individual object. I
> want a slab of memory which can hold multiple objects.
Which is exactly what I suggested above.
Sorry for being so retarded, but how would a deque improve on my existing
design? Can you give me some examples? Thanks Juha.