On Wednesday, Jun 4, 2003, at 08:22 America/Denver, Philippe A. Bouchard wrote:
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();
Neither of which can be done portably.
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
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
