Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!usc!snorkelwacker.mit.edu!thunder.mcrcim.mcgill.edu!bonnie.concordia.ca!ccu.umanitoba.ca!herald.usask.ca!alberta!cpsc.ucalgary.ca!news From: gintera@fsd.cpsc.ucalgary.ca (Andrew Ginter) Newsgroups: comp.lang.c++ Subject: Re: Implementing LISP in C++ (type discrimination) Summary: refcounts reclaim circular lists Message-ID: <1991Apr22.165825.13552@cpsc.ucalgary.ca> Date: 22 Apr 91 16:58:25 GMT References: <1991Mar8.024331.14235@searchtech.com> <27D7F621.2F5@tct.uucp> <17238@cadillac.CAD.MCC.COM> <1991Mar12.221015.22144@aero.org> <14342@hacgate.UUCP> <1991Apr17.233653.25149@dsd.es.com> Sender: gintera@cpsc.ucalgary.ca (Andrew Ginter) Organization: U. of Calgary Computer Science Lines: 37 Nntp-Posting-Host: fsd In article davis@barbes.ilog.fr (Harley Davis) writes: >One of the most important problems with reference counting is that it >doesn't collect all the garbage. In particular, circular data >structures never get collected. This was true of reference counting schemes until 1986. An article published in Software-Practice and Experience that year describes how reference counting systems can reclaim circular lists fairly simply. The exact name and author of the article escape me right now - they're in my other office. Drop me a note if you're desperate and I can dig them up for you. The circular list collection technique goes something like this: * Scan the collected heap. For each object in the heap, chase all pointers in the object and decrement the refcount on the target object. At the end of the scan, all of the contribution of internal pointers to refcount fields has been eliminated. * Scan the heap again. Mark any object with a non-zero refcount field. These are the objects which are referenced by "root pointers" (pointers which reside outside of the heap and which refer to collected objects). * Scan the heap again. Recursively mark any object with a non-zero refcount, incrementing reference counts as you traverse pointers in objects. * Scan the heap again. Any objects in the heap which still has a zero reference count can be reclaimed - these are the objects which were part of unreachable circular lists. I'm writing this from memory, so this may not be exactly right, but it gives the general idea. I suspect that some of the heap scans can be collapsed too, but again, I don't remember the details. Andrew Ginter, 403-220-6320, gintera@cpsc.ucalgary.ca