Boost logo

Boost :

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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at