[boost] shared_cyclic_ptr question

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
new();

Given:
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.
                else
                {
                    // 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. ****
            }

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

        ...

    private:
        T * m_p;
    };

Then:
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).

Ex.:
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,
destruction

Thus:
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).

Regards,

Philippe