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 <bmk@csc.ti.com> 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.
GarbageCollector
classGarbageCollector
implements the garbage collector. It has the following interface:
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.
GarbageCollecting
protocol
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 :-)!
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:
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.