Wandering Thoughts archives

Some patterns for polymorphism in C

As I've written about before, C programmers tend to (re)invent certain parts of OO programming on their own as the natural easiest way to write code. In that entry I mentioned that one thing C programs tend to have is a polymorphic object system. As it happens, I've seen several different ways of doing this in C (and I'm sure there are others, C programmers are inventive).

In theory the simplest way of doing polymorphism in C is just to start all of your structs with a common set of members; then you can just dereference a pointer to any struct to get at these without caring just what particular sort of struct you have. In practice, almost everyone does this by having a core struct type with all of those members because this gives your code a convenient base name for this set of common members.

(You can do without this base name but then you have to pick some actual struct type for the type of your pointer and the whole point of the polymorphism is that you don't care just what concrete type the pointer you have is.)

Once you have a struct with all your common members in it (call it an object struct), a question comes up: where does it go in your actual struct? I've seen three answers.

• the object struct goes at the start of your larger struct, and you simply cast the pointer between the two types as needed. This leads naturally to a style where you have several levels of more or less common object structs nested inside each other like Matryoshka dolls, each adding a few more fields that each layer of polymorphism needs.

• the object struct goes at some constant offset inside your larger structs. Going back and forth between a pointer to the object struct (when you need polymorphism) and a pointer to your actual struct requires some casting magic (generally wrapped up in CPP macros) and is somewhat more annoying than before.

  (I think this style is the least common.)

• the object struct has a pointer to your overall struct and goes anywhere you like in your larger struct (and may not be at a constant position in various different structs); you simply initialize the pointer appropriately when you're setting up an instance of the overall struct. This costs you an extra pointer field but frees you from various issues.

The first approach is by far the most common one that I've seen. It's the one I've generally used in my code when I needed this kind of thing; the other two approaches tend to be for more esoteric situations where for some reason you can't put (this) object struct at the start of your overall struct.

There is an interesting variation on the first approaches that kind of sidesteps having an actual object struct at the start of your real structs, but explaining it (and talking about why you'd want to do it) requires quoting enough code from CPython that I'm going to make it a separate entry.