By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,503 Members | 1,608 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,503 IT Pros & Developers. It's quick & easy.

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

P: n/a
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[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, 2foo_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<foo2foo2_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, 64int_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<nodenode_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.
:^)
Nov 18 '08 #1
Share this Question
Share on Google+
8 Replies


P: n/a

"Chris M. Thomasson" <no@spam.invalidwrote in message
news:gf**********@aioe.org...
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[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();
}
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^
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[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) {

}

~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, 2foo_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<foo2foo2_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, 64int_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<nodenode_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!
;^(....

Nov 18 '08 #2

P: n/a
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<regionm_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, 2foo_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<foo2foo2_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, 64int_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, 10node_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.

Nov 19 '08 #3

P: n/a
Chris M. Thomasson wrote:
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?
How do you deallocate (so that deallocated elements can be reused by
further allocations)?
Nov 19 '08 #4

P: n/a
"Juha Nieminen" <no****@thanks.invalidwrote in message
news:xW**************@read4.inet.fi...
Chris M. Thomasson wrote:
>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?

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/...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....419704ab8c471d

http://groups.google.com/group/comp....3c3b7d353bd3d9
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, BUFDEPTHpartition;
private:
struct node {
node* m_next;
partition m_partition;
};

region_allocator<node, 1m_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<nodenpalloc;
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...

Nov 19 '08 #5

P: n/a
Chris M. Thomasson wrote:
Region allocation forbids one from deallocating individual objects; you
can only deallocate all previously allocated objects.
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.
Nov 20 '08 #6

P: n/a
"Juha Nieminen" <no****@thanks.invalidwrote in message
news:oa**************@read4.inet.fi...
Chris M. Thomasson wrote:
>Region allocation forbids one from deallocating individual objects; you
can only deallocate all previously allocated objects.

Then what's the point?
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/...em_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.

Nov 20 '08 #7

P: n/a
Chris M. Thomasson wrote:
>You can't substitute new/malloc with such a thing.

You can substitute new/malloc, however, you "generally" cannot
substitute delete/free.
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.
Nov 20 '08 #8

P: n/a
"Juha Nieminen" <no****@thanks.invalidwrote in message
news:aC***************@read4.inet.fi...
Chris M. Thomasson wrote:
>>You can't substitute new/malloc with such a thing.

You can substitute new/malloc, however, you "generally" cannot
substitute delete/free.

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.

Nov 20 '08 #9

This discussion thread is closed

Replies have been disabled for this discussion.