The C programming language does not have a garbage collection, or any other kind of built-in resource management. For this reason, we who use C often find ourselves contemplating the best ways for managing object lifetimes. The following is an account of two methods that I use. Namely: reference counting and weak references via the observer model. Note that I have not tested the following examples and they are incomplete in some ways, e.g. they lack error checking.

The Reference Count

The most common pattern for managing object lifetimes is probably the reference count. It looks like this:

struct a {
	int ref;
};

struct a* a_create(void)
{
	struct a* self = calloc(1, sizeof(*self));
	self->ref = 1;
	return self;
}

void a_ref(struct a* self)
{
	self->ref++;
}

void a_unref(struct a* self)
{
	if (--self->ref == 0)
		free(self);
}

struct b {
	struct a* a;
};

struct b* b_create(struct a* a)
{
	struct b* self = calloc(1, sizeof(*self));
	self->a = a;
	a_ref(a);
	return self;
}

void b_destroy(struct b* self)
{
	a_unref(self->a);
	free(self);
}

In the example above, we have two object classes: a and b, of which b depends on a. Multiple objects of class b may hold references to the same object of class a, and only when all b have been destroyed can a be freed, that is, when its reference count reaches zero. In C++11, there is a template class for this named std::shared_ptr.

This is pretty neat, isn’t it? Why don’t we use it everywhere? Well, some do use reference counting quite judiciously. However, there are some problems with reference counting.

Problem: Reference Cycles

Let’s look at an example with three object that have a dependency loop: X <- Y <- Z <- X and they’re constructed like in the previous example.

// We'll start by constructing them
struct x* x = x_create(); // x->ref = 1
struct y* y = y_create(x); // y->ref = 1, x->ref = 2
struct z* z = z_create(y); // z->ref = 1, y->ref = 2

// This is just some fictional function that binds z to x so that now x has
// has a reference to z
x_bind_z(x, z); // x->ref = 2

// Let's see what happens if we destroy all these objects:
z_unref(z); // z->ref = 1
y_unref(y); // y->ref = 1
x_unref(x); // x->ref = 1

// Now all these objects are leaked. If we hadn't referenced x from things
// would look like this instead:
z_unref(z); // z->ref = 0, y->ref = 1
y_unref(y); // y->ref = 0, x->ref = 1
x_unref(x); // x->ref = 0

Reference cycles can be broken up using weak references which I will explain later in this post.

Problem: Finding Mistakes

In C++ and some other languages, reference counts can be maintained automatically using constructors and destructors, so you don’t really make the mistake of forgetting to reference or un-reference an object. However, in C, it is quite easy to make that mistake, and if you have a large code base, it can become rather difficult to track down reference counting errors. I’ve found that writing out the reference count to console in some places can be useful. If all else fails, you can do a stack dump from the ref and unref functions.

Problem: Welcome to the Party!

Being a reference counted object is a little bit like hosting a party. You have to stay up until everyone has left. Even if you’ve gotten bored a long time ago and you’re just waiting for everyone to go home. What I’m trying to say is that if you have a big dependency tree, you risk holding up resources. Also, the problem gets even worse when you add multiple layers of reference counts. I’m not saying that reference counting is bad. Just that it’s a pretty big hammer and it’s better not to swing it around unless it’s what’s required to solve the problem.

Observer Pattern

I have a confession: I never read Design Patterns and I’m not a computer scientist. My degree is in electrical engineering. With that out of the way, let’s discuss one of those famous patterns.

A system where one object can observe state changes in another without the observed object knowing anything about the observer implements the observer pattern. The object under observation is called the subject and the observer is called the observer.

What does this have to do with object lifetime management? Well, a subject can tell its observers when it’s destroyed. This is one way of implementing weak references. The std::weak_ptr in C++ is an example of a weak reference.

Examples of the observer pattern are Qt’s signal/slot system and Wayland’s wl_signal/wl_listener. In Qt, QObject::destroyed events are most often handled automatically, e.g. using the QPointer class. In the Wayland API, destroy signals are often implemented, but the user must make the reference to the subject inert manually using the listener’s callback. Note that I am not equating these different systems in any way. They are just examples of different software that use the observer pattern.

An implementation of weak references in C using the observer pattern might look like this:

#include <sys/queue.h>

struct weakref_subject;

struct weakref_observer {
	LIST_ENTRY(weakref_observer) link;
	struct weakref_subject* subject;
};

// This defines a struct named "weakref_subject" that's used as the head of a
// linked list of observers.
LIST_HEAD(weakref_subject, weakref_observer);

void weakref_observer_init(struct weakref_observer* observer,
		struct weakref_subject* subject)
{
	observer->subject = subject;
	LIST_INSERT_HEAD(subject, observer, link);
}

void weakref_observer_deinit(struct weakref_observer* self)
{
	// We no longer want to receive notifications from the subject, so we
	// remove this observer from its list, that is if the subject is still
	// alive.
	if (self->subject)
		LIST_REMOVE(self, link);
}

void weakref_subject_init(struct weakref_subject* self)
{
	LIST_INIT(self);
}

void weakref_subject_deinit(struct weakref_subject* self)
{
	// Remove all observers from the list:
	while (!LIST_EMPTY(self)) {
		struct weakref_observer* observer = LIST_FIRST(self);
		LIST_REMOVE(observer, link);

		// This is how we tell the observer that the subject is no
		// no longer reachable.
		observer->subject = NULL;
	}
}

struct c {
	int number;
	struct weakref_subject ref;
};

struct c* c_create(int number)
{
	struct c* self = calloc(1, sizeof(*self));
	c->number = number;
	weakref_subject_init(&self);
	return self;
}

void c_destroy(struct c* self)
{
	weakref_subject_destroy(&self->ref);
	free(self);
}

struct d {
	struct weakref_observer c;
};

struct d* d_create(struct c* c)
{
	struct d* self = calloc(1, sizeof(*self));
	weakref_observer_init(&self->c, &c->ref);
	return self;
}

void d_destroy(struct d* self)
{
	weakref_observer_destroy(&self->ref);
	free(self);
}

int main()
{
	struct c* c = c_create(42);

	struct d* d_1 = d_create(c);
	struct d* d_2 = d_create(c);
	// d_1 and d_2 each have a weak reference to c now

	// Let's say we want to reach c through d_1, this is what we do:
	// First, check is it's alive:
	if (d_1->c->subject) {
		// Second, get a pointer to c using the container_of macro:
		struct c* my_c = container_of(d_1->c->subject, struct c, subject);

		// Third, do something with c:
		printf("C's number is: %d\n", my_c->number);
	}

	// We can destroy d_2 here and c won't notify it when c dies because
	// d removes itself from the observer list
	d_destroy(d_2);
	d_2 = NULL;

	// If we destroy c now, d_1 will no longer have a reference to c because
	// c will have set the observer's reference to NULL.
	c_destroy(c);
	c = NULL;

	assert(d_1->c->subject == NULL);
	d_destroy(d_1);
	d_1 = NULL;
}

What is described above is just one way of implementing weak references. They can also be implemented using a global object registry from which the objects are removed when they die.

That’s all I have to say on this subject for now.