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

Discussion in 'C++' started by Chris M. Thomasson, Nov 18, 2008.

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


    :^)
     
    Chris M. Thomasson, Nov 18, 2008
    #1
    1. Advertising

  2. "Chris M. Thomasson" <> wrote in message
    news:gfv4h3$cb5$...
    > 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();
    > }

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


    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!


    ;^(....
     
    Chris M. Thomasson, Nov 18, 2008
    #2
    1. Advertising

  3. 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.
     
    Chris M. Thomasson, Nov 19, 2008
    #3
  4. 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)?
     
    Juha Nieminen, Nov 19, 2008
    #4
  5. "Juha Nieminen" <> wrote in message
    news:xWYUk.189$...
    > 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/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...
     
    Chris M. Thomasson, Nov 19, 2008
    #5
  6. 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.
     
    Juha Nieminen, Nov 20, 2008
    #6
  7. "Juha Nieminen" <> wrote in message
    news:eek:adVk.137$...
    > 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/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.
     
    Chris M. Thomasson, Nov 20, 2008
    #7
  8. 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
     
    Chris M. Thomasson, Nov 20, 2008
    #8
  9. 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.
     
    Juha Nieminen, Nov 20, 2008
    #9
  10. "Juha Nieminen" <> wrote in message
    news:aChVk.259$...
    > 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.
     
    Chris M. Thomasson, Nov 20, 2008
    #10
    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. Michael B Allen

    Simple Memory Allocator Challenge

    Michael B Allen, Oct 22, 2003, in forum: C Programming
    Replies:
    13
    Views:
    633
    Michael B Allen
    Oct 25, 2003
  2. SAL

    #Region #End Region issue

    SAL, Aug 29, 2008, in forum: ASP .Net
    Replies:
    1
    Views:
    371
    Alexey Smirnov
    Aug 29, 2008
  3. Chris M. Thomasson

    simple region allocator...

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

    conservative static region allocator...

    Chris M. Thomasson, Mar 7, 2009, in forum: C Programming
    Replies:
    8
    Views:
    378
    Chris M. Thomasson
    Mar 12, 2009
  5. Chris M. Thomasson

    wrt my conservative static region allocator...

    Chris M. Thomasson, May 30, 2009, in forum: C Programming
    Replies:
    9
    Views:
    387
    Keith Thompson
    Jun 1, 2009
Loading...

Share This Page