a simple type-based C++ region allocator...

C

Chris M. Thomasson

Here is the initial crude implmentation which compiles under Comeau with no
warnings:
___________________________________________________________________
#include <cassert>
#include <cstdlib>
#include <new>
#include <list>


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.~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.


:^)
 
C

Chris M. Thomasson

Chris M. Thomasson said:
Here is the initial crude implmentation which compiles under Comeau with
no
warnings:
___________________________________________________________________
#include <cassert>
#include <cstdlib>
#include <new>
#include <list>


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.~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();
}
Click to expand...

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^


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:
______________________________________________________________________
#include <cassert>
#include <cstdlib>
#include <new>
#include <list>


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.~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) {

}

~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;
}
______________________________________________________________________





Sorry about that stupid non-sense!


;^(....
 
C

Chris M. Thomasson

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.~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.
 
J

Juha Nieminen

Chris said:
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?
Click to expand...

How do you deallocate (so that deallocated elements can be reused by
further allocations)?
 
C

Chris M. Thomasson

Juha Nieminen said:
How do you deallocate (so that deallocated elements can be reused by
further allocations)?
Click to expand...

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...
 
J

Juha Nieminen

Chris said:
Region allocation forbids one from deallocating individual objects; you
can only deallocate all previously allocated objects.
Click to expand...

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.
 
C

Chris M. Thomasson

Juha Nieminen said:
Then what's the point?
Click to expand...

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.
Click to expand...

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.
Click to expand...

You can deallocate objects. Just all the objects at once.



If you never deallocate anything,
Click to expand...

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.
Click to expand...

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.
 
C

Chris M. Thomasson

I forget to mention a major caveat. This is not the fault of region
allocation, but is related to C++ dtors. C-based regions do not have the
following problem: You should not access an object A which belongs to the
same allocator in the dtor of object B. Example of the problem, and a fix:
______________________________________________________________________
// snip region allocator code

#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::eek:ops() - %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::eek:ops() - 00000000
(003E4B9C)->foo::~foo() - 003E4B98
_________________________________________
(003E6BB8)->foo::foo()
(003E4B98)->foo::foo(003E6BB8)
(003E6BB8)->foo::eek:ops() - 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::eek:ops()' 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::eek:ops()' 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::eek:ops() - %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::eek:ops() - 00000000
(003E2BB0)->foo::~foo() - 003E4B10



You have just got to be very careful!



:^o
 
J

Juha Nieminen

Chris said:
You can substitute new/malloc, however, you "generally" cannot
substitute delete/free.
Click to expand...

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.
I don't want to explicitly allocate memory for each individual object. I
want a slab of memory which can hold multiple objects.
Click to expand...

Which is exactly what I suggested above.
 
C

Chris M. Thomasson

Juha Nieminen said:
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.


Which is exactly what I suggested above.
Click to expand...

Sorry for being so retarded, but how would a deque improve on my existing
design? Can you give me some examples? Thanks Juha.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

simple reap allocator... 0
simple region allocator... 2
how to define my allocator 1
a really simple C++ abstraction around pthread_t... 19
Drawing missing in bitmap in a pure C win32 program 4
using nested types for custom allocator of incomplete type 5
General Allocator Regarding type definitions and void * specializedproblem 16
Custom Pool Allocator Question 0

Members online

No members online now.
Total: 29 (members: 0, guests: 29)
Robots: 318

Forum statistics

Threads
473,755
Messages
2,569,536
Members
45,007
Latest member
obedient dusk

Latest Threads

Top