simple reap allocator...

Discussion in 'C++' started by Chris M. Thomasson, Dec 11, 2008.

  1. 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.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-oopsla2002.pdf

    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.
    Chris M. Thomasson, Dec 11, 2008
    #1
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dan
    Replies:
    0
    Views:
    455
  2. Fraser Ross

    allocator size_type

    Fraser Ross, Jul 31, 2003, in forum: C++
    Replies:
    1
    Views:
    426
    John Harrison
    Jul 31, 2003
  3. Michael B Allen

    Simple Memory Allocator Challenge

    Michael B Allen, Oct 22, 2003, in forum: C Programming
    Replies:
    13
    Views:
    613
    Michael B Allen
    Oct 25, 2003
  4. Chris M. Thomasson

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

    Chris M. Thomasson, Nov 18, 2008, in forum: C++
    Replies:
    9
    Views:
    361
    Chris M. Thomasson
    Nov 20, 2008
  5. Chris M. Thomasson

    simple region allocator...

    Chris M. Thomasson, Nov 24, 2008, in forum: C Programming
    Replies:
    2
    Views:
    333
    Chris M. Thomasson
    Feb 8, 2009
Loading...

Share This Page