Leopold Toetsch wrote: > > gen n | gen j > [ A ] -> [ B ] -|-----> [ C ] > ^ | > +----------------------+ > > A circular data structure doesn't really change the picture, except, > when again scanning up to generation j, and we find object C being > alive, we'd have to restart scanning at object A, by following the > backreference. > If non of A, B, or C is referenced from elsewhere, we would still > delete the whole reference loop.
Hi, I don't know how this could work. First, we need more than one pass (if each alive object in the IGP needs to follow the backreference, this can lead to between |alive_IGP_set| and 2^|alive_IGP_set| passes...). And I don't see either how we could check if the loop is referenced from elsewhere, as the mark is a single bit. A solution I'm thinking of is using two bits for the marking : b0 is "referenced by an element of the real root set or by an object with b0 set" and b1 is "referenced by an element of the IGP or by an object with b1 set". Then if we come across such a loop with C being part of IGP, we check the marking bits of A : if b0 is set, then A is definitely alive, so do nothing. If b0 is not set, A could be dead. But the problem is that A could also be referenced by a fourth object, D, which would also be in the IGP set. The only way I can see to check if it really is dead is the following : take temporarily C out of the IGP set, then redo *all* of the marking pass. If b1 is not set, then only C was referencing it, and we can safely delete it. We then have to mark A as "definitely dead", set C back on IGP and do once again the marking pass... I hope there's a (much) more simple way :/ And this is not at all one pass mark&sweep... Regards, Alexandre
