From: Gregory Colvin (gregory.colvin_at_[hidden])
Date: 2003-06-04 20:18:03
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://listarchives.boost.org/mailman/listinfo.cgi/boost