Re: [boost] reset_and_collect root determination andsp_collectsimilarity

From: Peter Dimov (pdimov_at_[hidden])
Date: 2005-06-16 07:59:27

Larry Evans wrote:
> 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.

Yes, this is pretty much what reset_and_collect does.

> 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.

Exactly. In this variation, 'reset_and_collect' would just record a weak_ptr 
obtained from the shared_ptr being reset in a queue; then a separate 
function would mark starting from the weak_ptr queue and collect the 
unreachable nodes. It's also possible to allow the user to specify the weak 
pointers explicitly, if they are already being kept somewhere.