Reference counting in ANSI-C

Author
Jean-David Gadina
Copyright
© 2018 Jean-David Gadina - www.xs-labs.com - All Rights Reserved
License
This article is published under the terms of the FreeBSD Documentation License

About

Memory management can be a hard task when coding a C program.
Some higher level programming languages provide other ways to manage memory.
Main variants are garbage collection, and reference counting.
This article will teach you how to implement a reference counting memory management system in C.

Personally, as a C and Objective-C developer, I love the reference counting way.
It implies the notion of ownership on objects.

Objective-C example

For instance, in Objective-C, when you creates an object using the alloc, or copy methods, you own the object. It means you'll have to release your object, so the memory can be reclaimed.

Objects can also be retained. In such a case they must be released too.

Objects get by convenience methods are not owned by the caller, so there's no need to release them, as it will be done by someone else.

For instance, in Objective-C:

NSArray * object1 = [ NSArray array ];
NSArray * object2 = [ [ NSArray alloc ] init ];
NSArray * object3 = [ [ [ NSArray array ] retain ] retain ];

Here, the object2 variable will need to be released, as we allocated it explicitly.
The object3 variable will need to be released twice, since we retained it twice.

[ object2 release ];
[ [ object3 release ] release ];

C implementation

As a C coder, I've implemented this with ANSi-C.
Here are some explanations.

First of all, we are going to define a structure for our memory records.
The structure will look like this:

typedef struct
{
    unsigned int retainCount
    void       * data;
}
MemoryObject;

Here, we are storing the retain count of the memory object. A retain will increment it, and a release decrement it. When it reaches 0, the object will be freed.

We'll also need a custom allocation function:

void * Alloc( size_t size )
{
    MemoryObject * o;
    
    o = ( MemoryObject * )calloc( sizeof( MemoryObject ) + size, 1 );

Here, allocate space for our memory object structure, plus the user requested size.
We are not going to return the memory object, so we need some calculation here.

First of all, let's declare a char pointer, that will point to our allocated memory object structure:

char * ptr = ( char * )o;

Then, we can get the location of the user defined data by adding the size of the memory object structure:

ptr += sizeof( MemoryObject );

Then, we can set our data pointer, et set the retain count to 1.

o->data        = ptr;
o->retainCount = 1;

Now we'll return to pointer to the user data, so it doesn't have to know about our memory object structure.

return ptr;

Here's the full function:

void * Alloc( size_t size )
{
    MemoryObject * o;
    char         * ptr;
    
    o              = ( MemoryObject * )calloc( sizeof( MemoryObject ) + size, 1 );
    ptr            = ( char * )o;
    ptr           += sizeof( MemoryObject );
    o->retainCount = 1;
    o->data        = ptr;
    
    return ( void * )ptr;
}

This way, we return the user defined allocated size, and we are hiding our structure before that data.

To retrieve our data, we simply need to subtract the size of the MemoryObject structure.

For example, here's the Retain function:

void Retain( void * ptr )
{
    MemoryObject * o;
    char         * cptr;
    
    cptr  = ( char * )ptr;
    cptr -= sizeof( MemoryObject );
    o     = ( MemoryObject * )cptr;
    
    o->retainCount++:
}

We are here retrieving our MemoryObject structure, by subtracting the size of it to the user pointer. Once done, we can increase the retain count by one.

Same thing is done for the Release function:

void Release( void * ptr )
{
    MemoryObject * o;
    char         * cptr;
    
    cptr  = ( char * )ptr;
    cptr -= sizeof( MemoryObject );
    o     = ( MemoryObject * )cptr;
    
    o->retainCount--:
    
    if( o->retainCount == 0 )
    {
        free( o );
    }
}

When the retain count reaches zero, we can free the object.

That's all. We now have a reference counting memory management in C.
All you have to do is call Alloc to create an object, Retain if you need to, and Release when you don't need the object anymore.
It may have been retained by another function, but then you don't have to care if it will be freed or not, as you don't own the object anymore.