From: Philippe A. Bouchard (philippe_at_[hidden])
Date: 2003-06-04 09:22:18
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.
- you can easily detect weither an object was allocated on the stack or on
- 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.
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>
template <typename U>
smart_pointer(U * p) : m_p(p)
// 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
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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk