Re: [boost] shared_cyclic_ptr question

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://lists.boost.org/mailman/listinfo.cgi/boost