Re: [boost] reset_and_collect root determination and sp_collectsimilarity

From: Larry Evans (cppljevans_at_[hidden])
Date: 2005-06-16 07:16:57

On 06/16/2005 06:38 AM, Peter Dimov wrote:
> Larry Evans wrote:
[snip]
>>to find the roots, at least AFAICT.  Is this intentional, ...
> 
> 
> Yes, this is intentional, as reset_and_collect does not require any help 
> from the implementation of shared_ptr, so it can be used with 
> tr1::shared_ptr as well. It has been developed in response to Eric Niebler's 
> scenario where the roots that form cycles are known to the programmer.

Ah!  My mind's fog is lifting slightly ;)

[snip]
> 
> It's possible to combine the two approaches and perhaps provide a default 
> enable_tracking that does a memory scan as in sp_collector. I think that in 

I would be nice if somehow the method for finding a referent's contained
smart_ptr's could be a determined by a policy.

> most typical cyclic shared_ptr situations the problematic roots are known in 
> advance, though, so a reset_and_collect-type solution may be enough.

Hadn't thought of that.

> Note that reset_and_collect is perfectly capable of figuring out on its own 
> that unknown roots to a node exist, it only needs a starting point (and can 
> be modified to work with several starting points). 

Hmm... is this anything like the 'local mark scan' in [mart90] cited on
Jones page?  Give a node, call it the subroot node, it traverses nodes
reachable from that while decrementing the refcounts.  If the subroot
node still has a positve refcount, it can't be in a cycle; so, it
undoes the decrementing.  I'm guessing that the difference is that:

   1) reset_and_collect doesn't decrement, it only increments the value
      associated with the node's key in a map_type.

   2) instead of user selection of the staring point, the selection is
      made each time a decrement is made, and the starting point is
      the smart_ptr making the decrement.

The modification to several starting points sounds like it may be a 
variation of the method in [lins90a], where a decrement doesn't
immediately scan the subnodes, but waits until a que of decremented
smart_ptr's is filled, and then scan's nodes reachable from each
element in the que.  Is that, at least approximately, what's happening
in reset_and_collect?