Boost logo

Boost :

From: Philippe A. Bouchard (philippe_at_[hidden])
Date: 2003-06-04 09:22:18

Greetings Boost,

    I am not that much familiar with garbage collection techniques so please
excuse me if the technique I am thinking of is already used somewhere.

Let's say:
- you can easily detect weither an object was allocated on the stack or on
the heap;
- a smart pointer contained within an object can somehow access it's "object
header" when the object was allocated on the heap with a placement operator

Node = element of a possible cyclic graph allocated on the heap.
Entity = possible cyclic graph in its entirety allocated on the heap.

struct entity_header
    int count;

struct node_header
    int count;
    entity_header * p_entity;

// Erroneous but simple allocation example:
inline void * operator new (size_t s, gc const &)
    return malloc(s + sizeof(node_header)) + sizeof(node_header);

template <typename T>
    struct smart_pointer
        template <typename U>
            smart_pointer(U * p) : m_p(p)
                if (is_on_the_stack(this))
                    // Allocate an entity_header and affect its address to
m_p's header->p_entity. *
                    // Initialize m_p's header->p_entity->count to 1.
                // 'this' is part of a node with a header on the heap.
                    // Copy the this's header->p_entity to m_p's
header->p_entity. **

        template <typename U>
            smart_pointer(smart_pointer<U> const & p) : m_p(p.m_p)
                // Possible merge / fragmentation of two entities. ***
                // Possible incrementation / decrementation of this's
header->p_entity->count and m_p's header->p_entity->count. ****

            if (m_p && m_p's header->p_entity->count == 1)
                // Force an entity's destruction. *****


        T * m_p;

An entity_header will be allocated each time a pointer on the stack refers
to a new node on the heap (*) and every other node derived from this root
node will refer to the same entity_header with node_header::p_entity. If a
new pointer on the stack refers to the entity, its entity_header::count will
be incremented. If the last pointer on the stack refers to the entity then
the entire entity will be destructed (no more possible cyclic graph).

template <typename T> struct rope; // cyclic entity

smart_pointer< rope<int> > p = new (gc) rope<int>(10); //
entity_header::count == 1
smart_pointer< rope<int> > q = p; // entity_header::count == 2
p.~smart_pointer< rope<int> >(); // entity_header::count == 1
q.~smart_pointer< rope<int> >(); // entity_header::count == 0,

The purpose of the entity_header is to know the number of times the entity
is refered by a pointer on the stack.

Do this algorithm already has a name? If so, why aren't you using it since
there is no need to scan the graph looking up for dangling entities. It may
take a little bit more memory (1 more pointer per node + 1 entity_header per
heap graph) but I think the cost / benefits here are quite acceptable since
the speed will always be O(1).



Boost list run by bdawes at, gregod at, cpdaniel at, john at