Garbage collector based on reference counting This library contains some classes that allow you to write code without explicitly managing cyclic references. You have to manage explicitly the reference counts when you have objects that form cyclic graphs. The garbage collector neither maintains explicitly all the pointers in your program nor it collects all the memory allocated by you in the program. Instead it collects and maintains only some special kind of objects, that are garbage collectable. The algorithm was inspired from a similar one found in the Brian M. Kennedy's OATH C++ library. It works in three passes. Suppose that all the objects that are garbage collectable are known. Also each object has an additional flag, used for determining if the object was already visited. During the first pass, all objects that are garbage collectable clears the associated flag and receive the message `- gcDecrementRefCountOfContainedObjects'. In this method the object decrements the ref count of every garbage collectable object it contains. After this pass all the objects that have the ref count 0 are part of cyclic graphs. Such objects have their ref count due only to another objects from graph. In the second pass we have to restore the original ref counts and to isolate the nodes from cyclic graphs. In this pass all the objects that have the ref count greater than 0 receive the message `- gcIncrementRefCountOfContainedObjects'. In this method the object check the flag if it's set. This flag tells if the object was visited previously. If the flag is set, the method returns, else the flag is set. Then the ref count of every garbage collectable object contained is incremented and the message `-gcIncrementRefCountOfContainedObjects' is sent to those objects. After this pass all the objects that are reachable from `outside' have their ref count greater than 0. All the objects that still have their ref count equal with 0 are part of cyclic graphs and there is no reference from `outside' to an object from these graphs. In the third pass all the objects that have their ref count equal with 0 receive the `-dealloc' message. In this method the objects should send the `-release' message to all contained objects that are not garbage collectable. This because the order of deallocation is not known and you can send `-release' to an already deallocated object. So if a class contains both normal objects and garbage collectable objects, it should maintain their collectable status when the objects are retained. The `GarbageCollector' class The class `GarbageCollector' implements the garbage collector. It has the following interface: @interface GarbageCollector : NSObject + (void)addObject:(id)anObject; + (void)objectWillBeDeallocated:(id)anObject; + (void)collectGarbages; @end A new garbage collectable object has to be made know to the `GarbageCollector' collector by sending it the `+addObject:' message with self as argument. When the object is deallocated it should inform the `GarbageCollector' class about this by sending it the `+objectWillBeDeallocated:' message with self as argument. The `+collectGarbages' should be send to the `GarbageCollector' class to collect the garbages. You can send it whenever you want. If you are using a run loop in your program you can set a timer to be called periodically. Or you can call the garbage collector when the program is idle. In the current implementation the garbage collector is not thread-safe, so please don't use it in multi-threaded programs, unless you use garbage collectable objects only in one thread. The `GarbageCollecting' protocol To allow instances of a class to be garbage collectable, the class should implement the following protocol: @protocol GarbageCollecting - gcSetNextObject:(id)anObject; - gcSetPreviousObject:(id)anObject; - (id)gcNextObject; - (id)gcPreviousObject; - (void)gcIncrementRefCount; - (void)gcDecrementRefCount; - (void)gcDecrementRefCountOfContainedObjects; - (BOOL)gcIncrementRefCountOfContainedObjects; - (BOOL)isGarbageCollectable; @end The `GarbageCollector' class uses a double linked list to maintain the objects. The `gcSetNextObject:', `gcSetPreviousObject:', `gcNextObject' and `gcPreviousObject' are used by the collector to add or remove objects in its list. This could change in the future. The `gcIncrementRefCount' and `gcDecrementRefCount' methods should increment, respectively decrement the ref count of receiver. The `gcDecrementRefCountOfContainedObjects' method should decrement the ref count of all garbage collectable objects contained, by sending them the `-gcDecrementRefCount'. The `gcIncrementRefCountOfContainedObjects' method should check the flag. If this is true, the method should return NO; it this is false the method should set it. Then it should increment the ref count of garbage collectable objects contained by sending them the `-gcIncrementRefCount' message. After this it should send the `- gcIncrementRefCountOfContainedObjects' message to the same objects. Then it should return YES. The object should respond YES at the `-isGarbageCollectable' message if it is garbage collectable. The NSObject class responds NO to this message. You should note the asymmetry between the `gcDecrementRefCountOfContainedObjects' and `gcIncrementRefCountOfContainedObjects' methods. This makes the algorithm to work. So be careful if you're using copy/paste operations to write them in your editor :-)! Support classes There is a class `GCObject' from which you could inherit your own classes. This class implements the `GarbageCollecting' protocol. Using this class, you could write a class whose instances hold other objects. This class is safe to cyclic references. Here is its implementation: @interface MyGCObject : GCObject { id object; BOOL isGarbageCollectable; } - (void)setObject:(id)anObject; - (id)object; @end @implementation MyGCObject - (void)setObject:(id)anObject { [anObject retain]; [object release]; object = anObject; isGarbageCollectable = [object isGarbageCollectable]; } - (id)object { return object; } - (void)decrementRefCountOfContainedObjects { [object gcDecrementRefCount]; } - (BOOL)incrementRefCountOfContainedObjects { if(![super incrementRefCountOfContainedObjects]) return NO; [object gcIncrementRefCount]; [object incrementRefCountOfContainedObjects]; return YES; } - (void)dealloc { if(!isGarbageCollectable) [object release]; [super dealloc]; } @end There are also concrete subclasses of NSArray and NSDictionary named GCArray and GCDictionary respectively, together with their mutable classes GCMutableArray and GCMutableDictionary. Their instances could hold both normal and garbage collectable objects.