[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

simple reap allocator...

Chris M. Thomasson

12/11/2008 4:17:00 AM

Here is the crude code:
_____________________________________________________________________________
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <climits>
#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_head() throw() {
return m_next->get();
}


inline T* get_tail() throw() {
return m_prev->get();
}


inline T* get() throw() {
return (T*)this;
}
};


#define BITSIZE (sizeof(unsigned) * CHAR_BIT)


template<typename T, std::size_t DEPTH = 1024 * 4, std::size_t THRESHOLD =
2>
class reap_allocator {

struct reap : public dlink<reap> {
union block {
block* m_next;
double m_align;
unsigned char m_buf[sizeof(T)];
};


struct allocation {
reap* m_reap;
block* m_block;
block* m_next;
bool m_flist;
};


struct map_node {
std::size_t m_offset;
std::size_t m_bit;
};


block m_blocks[DEPTH];
block* m_flist;
std::size_t m_offset;
std::size_t m_count;
unsigned m_map[DEPTH / BITSIZE];


static reap* create() {
reap* const r = (reap*)std::calloc(1, sizeof(*r));
if (! r) { throw std::bad_alloc(); }
return r;
}

void destroy() {
flush();
std::free(this);
}

void get_map_node(void* const mem_, map_node& mn) {
unsigned char* const mem = (unsigned char*)mem_;
mn.m_offset = (size_t)((mem - (unsigned char*)m_blocks) / sizeof(T));
mn.m_bit = 1 << (mn.m_offset & (BITSIZE - 1));
mn.m_offset /= BITSIZE;
}

void set_bit(map_node& mn) {
m_map[mn.m_offset] |= mn.m_bit;
}

void clear_bit(map_node& mn) {
m_map[mn.m_offset] &= ~mn.m_bit;
}

bool is_bit(map_node& mn) {
return m_map[mn.m_offset] & mn.m_bit ? true : false;
}

bool allocate(allocation& a) {
a.m_reap = this;
a.m_block = m_flist;
if (a.m_block) {
a.m_next = a.m_block->m_next;
a.m_flist = true;
return true;
} else {
size_t const offset = m_offset;
if (offset + 1 <= DEPTH) {
a.m_block = m_blocks + offset;
a.m_flist = false;
return true;
}
}
a.m_block = NULL;
return false;
}

void allocate_commit(allocation& a) {
map_node mn;
get_map_node(a.m_block, mn);
set_bit(mn);
++m_count;
if (a.m_flist) {
m_flist = a.m_next;
} else {
++m_offset;
}
}

std::size_t deallocate(void* const mem) {
block* const b = (block*)mem;
map_node mn;
get_map_node(b, mn);
clear_bit(mn);
b->m_next = m_flist;
m_flist = b;
--m_count;
return m_count;
}

void flush() {
map_node mn;
for (unsigned i = 0; i < m_offset && m_count; ++i) {
get_map_node(m_blocks + i, mn);
if (is_bit(mn)) {
try { ((T*)m_blocks[i].m_buf)->~T(); } catch (...) {}
clear_bit(mn);
--m_count;
}
}
assert(! m_count);
m_offset = 0;
m_flist = NULL;
}

bool is_block(void* const mem) {
unsigned char* const b = (unsigned char*)mem;
unsigned char* const s = (unsigned char*)m_blocks;
unsigned char* const e = (unsigned char*)(m_blocks + DEPTH);
return (b >= s && b < e);
}
};


dlink<reap> m_reaps;
std::size_t m_count;


reap* prv_expand() {
reap* const r = reap::create();
m_reaps.push_head(r);
++m_count;
return r;
}


void prv_shrink(reap* const r) {
r->pop();
r->destroy();
--m_count;
}


reap* prv_find(void* const mem) {
reap* r = m_reaps.get_head();
while (r != &m_reaps) {
if (r->is_block(mem)) {
return r;
}
r = r->m_next->get();
}
assert(false);
std::unexpected();
return NULL;
}


typedef typename reap::allocation allocation;


void prv_allocate(allocation& a) {
reap* r = m_reaps.get_head();
while (r != &m_reaps) {
if (r->allocate(a)) {
return;
}
r = r->m_next->get();
}
prv_expand()->allocate(a);
}


#define REAP_SYS_ALLOCATE_X(mp_params) allocation a; prv_allocate(a); T* const obj = new (a.m_block) T mp_params; a.m_reap->allocate_commit(a); return obj

#define REAP_SYS_ALLOCATE(mp_params) REAP_SYS_ALLOCATE_X(mp_params)


public:
class fguard { // flush RAII guard
reap_allocator& m_handle;
public:
fguard(reap_allocator& handle) : m_handle(handle) {}
~fguard() { m_handle.flush(); }
};


reap_allocator() : m_count(0) {
m_reaps.ctor();
prv_expand();
}


~reap_allocator() {
flush();
prv_shrink(m_reaps.get_head());
}


void flush() {
reap* r = m_reaps.get_head();
while (r != &m_reaps) {
reap* const next = r->m_next->get();
if (m_count > 1) {
prv_shrink(r);
} else {
r->flush();
}
r = next;
}
}


void deallocate(T* const obj) {
try { obj->~T(); } catch (...) {}
// TODO: make `deallocate()' an `O(1)' procedure!
// (e.g., remove `prv_find()'); use alignment mask instead...
reap* const r = prv_find(obj);
if (! r->deallocate(obj) && m_count > THRESHOLD) {
prv_shrink(r);
}
}


T* allocate() {
REAP_SYS_ALLOCATE(());
}


template<typename P1>
T* allocate(P1 p1) {
REAP_SYS_ALLOCATE((p1));
}
};




struct foo {
foo* m_next;

foo(foo* next = NULL) : m_next(next) {
std::printf("(%p)->foo::foo(%p)\n", (void*)this, (void*)next);
}

~foo() {
std::printf("(%p)->foo::~foo() - %p\n", (void*)this, (void*)m_next);
}
};


int main() {

{
reap_allocator<foo> a;
foo* head = NULL;

for (unsigned r = 0; r < 25; ++r) {
reap_allocator<foo>::fguard fg(a);

for (unsigned i = 0; i < (r + 1) * 10; ++i) {
head = a.allocate(head);
}

foo* h = head->m_next->m_next->m_next->m_next;
while (h) {
foo* n = h->m_next;
a.deallocate(h);
h = n;
}

a.allocate();
a.allocate();
a.allocate();
a.allocate();
a.allocate();
a.allocate();
a.deallocate(a.allocate());

head = NULL;
}
}

return 0;
}
_____________________________________________________________________________




As you can see, the reap allocator uses a very simple, fine-grain bitmap
algorithm to ensure that calls to `reap_allocator<T>::flush()' do not call
the dtor of a free object. This algorithm acts as both region and heap
allocation schemes. There is a paper on the idea of merging regions/heaps:

http://www.cs.umass.edu/~emery/pubs/berger-oops...

IMVHO, its fairly useful. Its also completely exception-safe; the following
code is not a memory leak:


reap_allocator<foo> ralloc;
for (;;) {
reap_allocator<foo>::fguard fg(ralloc);
ralloc.allocate(); ralloc.allocate();
ralloc.allocate(); ralloc.allocate();
ralloc.allocate(); ralloc.allocate();
}


`reap_allocator<T>::allocate()' can potentially throw because it invokes
ctor of object `T'. Luckily, this does not adversely effect state of the
allocator `ralloc' and/or the application as no memory leaks occur. The RAII
object `fg' will automatically flush the local instance of the reap object
`ralloc' before the next iteration of the naked `for (;;)' loop.
2 Answers

Yoorghis

2/1/2012 3:46:00 AM

0

On Tue, 31 Jan 2012 17:05:41 -0800 (PST), Richard Steel
<rsteel2525@aol.com> wrote:

>How would you know? You only pretend to be vet, remember?

You pretend to be educated, SteelLoon

Your ignorance is one of your most endearing characteristics.

Richard Steel

2/1/2012 5:08:00 AM

0


> >> >> >And yet you insist that these men would allow a pale skinned, slack
> >> >> >jacked nobody to simply steal their reputations and honor without a
> >> >> >word of protest?
>
> >> >>     Where was this done?

> >> >When you claimed to be a Navy Seal.

> >>    So you have seen my records?

> >You once told me that you hadn't ever earned a military honor.  You
> >then claimed to have been a Navy Seal.

>   You ever think maybe you misunderstood.

Quite certain that I didn't. I asked you several times, and gave you
every chance to back off from the lies. You chose to double down. Of
course, you never settled down on a single story - you alternated
between cop and Navy Seal - and you've never straighten out idea you
were retired/active duty/retured but you took monthly meetings
nonsense.

>   Some people don't like to
> tell such things on a public NG.

And yet you did exactly that several times. Nobody held a gun to your
head.

> You do not have a right to peoples
> personal information.

Big talk from a pathological liar who demanded I prove that my father
served in the Marines.

> >You might as well have written that you're President of the United
> >States, but you've never run for office.  I suppose there are some
> >people who manage to get an Honorable Discharge without ever winning
> >some sort of military honor....but I've never met one.  Certainly,
> >without question, no one has ever been raised to the heights of Seal
> >without earning many honors.  It's the bare minimum requirement.

> Well maybe you need to think a little.  If everyone has one is it a
> honor or just part of he job.

You didn't say that it didn't matter - you said in never happened.

And you said this multiple times.

Never mind never having served - you've never even seen a movie about
the military.


> >> >They're Tea Party members - the one you repeated said sucked
> >> >testicles, were traitors, and settled on "Tea Billies".  They're also
> >> >actual Veterns ... not a lying sack of shit your yourself.

> >>   Well being a vet doesn't make one perfect.

> >How would you know?  You only pretend to be vet, remember?

>    Again where is your evidence?

1. Your story isn't consistant.
2. You don't know the first thing about the military.

> >>  Then living where you do.

> >Now that you've been utterly humiliated and discredited, you start
> >with the thinly veiled creepy threats.  Hinting that you have my home
> >address, are you?  If so, you know that we have Castle laws in my neck
> >of the woods - and I'm heavily armed.  I have guns, and I love
> >shooting them.

>   LOL   You are crazy.   Do you really think your so important I'd
> make a public threat.  ROFL.

It's not that I'm important - I'm sure you creepily threaten anyone
who calls you on your lies.

>  You have no proof of your accusations as there can't be any.  You
> have no credibility on this NG and have no way to effect my life at
> all.

>  Being a X-seal does not make my opinion any better than anyone else.

Just when I believe that you've hit bottom, you sink lower.

There is no such thing as a "X-Seal". I ONCE made the mistake of
telling my father that he "used to be a Marine". I was told, in no
uncertain terms, that he IS a Marine. Once a man is a Seal, he's one
for life.