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.