== Some patterns for polymorphism in C

As I've [[written about before CProgrammerOOView]], 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 CProgrammerOOView]] 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 _struct_s 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 _struct_s nested inside each other
  like [[Matryoshka dolls http://en.wikipedia.org/wiki/Matryoshka_doll]],
  each adding a few more fields that each layer of polymorphism
  needs.

* the object _struct_ goes at some constant offset inside your larger
  _struct_s. 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 _struct_s); 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
_struct_s, 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 CPolymorphicPatternsII]].