22 ms·
I don't understand. When sweep frees an object, it invalidates the "next" object of the previous object in the linked list, breaking the traversal next time a g
by robertk 13y ago
I don't understand. When sweep frees an object, it invalidates the "next" object of the previous object in the linked list, breaking the traversal next time a gc() is called. Doesn't the linked list have to be patched? (e.g., keep track of "prev_object" and set its next to unreached->next before freeing unreached)
- bla2 13y agoI think `*object = unreached->next;` does that, since it's using a pointer to a pointer.
- munificent 13y agoThat's correct. It patches the "next" pointer of the previous object to point past the freed object. It's a pointer to a pointer to handle the case where you're freeing the first object in the list. In that case, it's "firstObject" that needs to be modified, not some Object's "next" pointer. Using a pointer to a pointer (while admittedly harder to read at first) lets you handle both of those cases with the same code.
- unwind 13y agoThis technique is talked about in this Stack Overflow answer: http://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list http://stackoverflow.com/questions/12914917/using-pointers-t..., which also references this Slashdot interview (http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions http://meta.slashdot.org/story/12/10/11/0030249/linus-torval...) with Linus Torvalds where he gives this as his "favorite hack".
- munificent 13y agoYup, I got the idea for this from Linus. Before then, I've always done the uglier "if this is the first node then ..." special case branch instead.