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.