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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
