As a result of making regular use of object-oriented programming in
C, I’ve discovered a useful reference counting technique for the
occasional dynamically allocated structs that need it. The situation
arises when the same struct instance is shared between an arbitrary
number of other data structures and I need to keep track of it all.
It’s incredibly simple and lives entirely in a header file, so
without further ado (ref.h):
It has only two fields: the reference count and a “method” that knows
how to free the object once the reference count hits 0. Structs using
this reference counter will know how to free themselves, so callers
will never call a specific *_destroy()/*_free() function. Instead
they call ref_dec() to decrement the reference counter and let it
happen on its own.
I decided to go with a signed count because it allows for better error
checking. It may be worth putting an assert() in ref_inc() and
ref_dec() to ensure the count is always non-negative. I chose an
int because it’s fast, and anything smaller will be padded out to
at least that size anyway. On x86-64, struct ref is 16 bytes.
This is basically all there is to a C++ shared_ptr,
leveraging C++’s destructors and performing all increment/decrement
work automatically.
Thread Safety
Those increments and decrements aren’t thread safe, so this won’t work
as-is when data structures are shared between threads. If you’re sure
that you’re using GCC on a capable platform, you can make use of its
atomic builtins, making the reference counter completely thread
safe.
There’s a very deliberate decision to make all of the function
arguments const, for both reference counting functions and the
free() method. This may seem wrong because these functions are
specifically intended to modify the reference count. There are
dangerous-looking casts in each case to remove the const.
The reason for this is that’s it’s likely for someone holding a
const pointer to one of these objects to want to keep their own
reference. Their promise not to modify the object doesn’t really
apply to the reference count, which is merely embedded metadata. They
would need to cast the const away before being permitted to call
ref_inc() and ref_dec(). Rather than litter the program with
dangerous casts, the casts are all kept in one place — in the
reference counting functions — where they’re strictly limited to
mutating the reference counting fields.
On a related note, the stdlib.hfree() function doesn’t take a
const pointer, so the free() method taking a const pointer is a
slight departure from the norm. Taking a non-const pointer was a
mistake in the C standard library. The free() function
mutates the pointer itself — including all other pointers to that
object — making it invalid. Semantically, it doesn’t mutate the
memory behind the pointer, so it’s not actually violating the
const. To compare, the Linux kernel kfree() takes a
const void *.
Just as users may need to increment and decrement the counters on
const objects, they’ll also need to be able to free() them, so
it’s also a const.
Usage Example
So how does one use this generic reference counter? Embed a struct
ref in your own structure and use our old friend: the
container_of() macro. For anyone who’s forgotten, this macro not
part of standard C, but you can define it with offsetof().
Here’s a dumb linked list example where each node is individually
reference counted. Adding an extra 16 bytes to each of your linked
list nodes isn’t normally going to help with much, but if the tail of
the linked list is being shared between different data structures
(such as other lists), reference counting makes things a lot simpler.
Notice that it recursively decrements its child’s reference count
afterwards (intentionally tail recursive). A whole list will clean
itself up when the head is freed and no part of the list is shared.
The allocation function sets up the free() function pointer and
initializes the count to 1.
(Side note: I used snprintf() because strncpy() is
broken and strlcpy() is non-standard, so it’s the most
straightforward way to do this in standard C.);
And to start making some use of the reference counter, here’s push and
pop.
Notice node_pop() increments the reference count of the new head
node before returning. That’s because the node now has an additional
reference: from *nodesand from the node that was just popped.
It’s up to the caller to free the returned node, which would decrement
the count of the new head node, but not free it. Alternatively
node_pop() could set next on the returned node to NULL rather than
increment the counter, which would also prevent the returned node from
freeing the new head when it gets freed. But it’s probably more useful
for the returned node to keep functioning as a list. That’s what the
reference counting is for, after all.
Finally, a simple program to exercise it all. It reads ID/value pairs
from standard input.