This is GarbageCollector.txt in view mode; [Download] [Up]
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 <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.
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.
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.