71 Building the table — polymorphism, inheritance, overloading, versions, lifetime

71.1 Polymorphism — what it gives, what it costs, what to watch#

Calling a function through a table is dynamic dispatch: which function is called is decided at run time by the object’s table.

What it gives is plain.

• The caller need not know the object’s kind. Drawing code does not ask whether a shape is a circle or a rectangle.
• A new kind can be added without changing the callers’ code — a new table and a few functions are enough. Plug-in structures, file systems and device drivers stand on this property.

What it costs is just as plain.

• Indirect calls. The compiler does not know which function will be called, so it cannot expand it in place (inline it). When inlining is blocked, the optimisations that follow — constant propagation (computing in advance values known at compile time), vectorisation (computing several values with one instruction), removing needless work — are blocked with it. That costs more than the call itself.
• The cost of reading. Someone reading s->ops->area(s) cannot tell what it does. They have to go and find where the table was filled.
• Objects with no table. Call an object whose table pointer was never filled and the program jumps anywhere.

Where the compiler can tell which table it is, it sometimes turns an indirect call into a direct one (devirtualisation). In C there is room for that when the table is static const and the object is visible at that point — how narrow that condition is, chapter 73 checks in the machine code. But do not count on it when designing.

There are three things to watch.

1. If the set of kinds is closed — no more kinds will be added — no table is needed. If shapes are circles, rectangles and triangles and nothing else, a tag and a switch are simpler (“Where things are going now” in chapter 75). Which is faster depends on whether each branch’s function is inlined and on how the kinds are mixed (chapter 73). A table earns its keep when the set of kinds is open — when people outside add new kinds.
2. A derived kind must not break the base’s promises. Say a square “is a kind of rectangle” and inherits the rectangle’s table; if the square cannot honour the rectangle’s “change the width only”, code that accepts rectangles goes wrong when it meets a square. Barbara Liskov put this idea forward in her OOPSLA keynote of 1987; it later came to be called the Liskov substitution principle. In C it is kept only by documentation and tests.
3. A table’s slots, once published, are a contract. Change the order or the arguments of the slots, and all the outside code that filled the old table goes wrong (“Structs that survive new versions”, below).

71.2 Inheritance through tables — a derived table that embeds the base table#

In chapter 70, the imitation of inheritance was “the base struct as the first member”. That is inheritance of state. Inheritance of behaviour is the table’s job — and the same method works for tables. A derived kind’s table holds the base kind’s table as its first member.

/* Inheritance by tables: the derived table holds the base table as its first member.
   - square overrides one slot (area) and inherits describe from shape.
   - circle overrides describe, calls the base version first (an "up-call"),
     and adds a slot of its own (radius) that only circle code can reach. */
#include <stdio.h>

struct shape;
struct shape_ops {
    double (*area)(const struct shape *);
    void   (*describe)(const struct shape *);
};
struct shape { const struct shape_ops *ops; const char *name; };

static void shape_describe(const struct shape *s)          /* the base behaviour */
{
    printf("%-7s area %6.2f", s->name, s->ops->area(s));
}

/* square: a plain derived kind --- one slot replaced, the rest copied from the base */
struct square { struct shape base; double side; };
static double square_area(const struct shape *s)
{
    const struct square *q = (const struct square *)s;      /* base is the first member */
    return q->side * q->side;
}
static const struct shape_ops square_ops = {
    .area = square_area, .describe = shape_describe,
};

/* circle: a derived table that embeds the base table and adds a slot */
struct circle;
struct circle_ops {
    struct shape_ops base;                                  /* must stay first */
    double (*radius)(const struct circle *);
};
struct circle { struct shape base; double r; };

static double circle_area(const struct shape *s)
{
    const struct circle *c = (const struct circle *)s;
    return 3.0 * c->r * c->r;
}
static double circle_radius(const struct circle *c) { return c->r; }
static void circle_describe(const struct shape *s)
{
    shape_describe(s);                                      /* up-call: base first */
    const struct circle_ops *ops = (const struct circle_ops *)s->ops;
    printf("  radius %.1f", ops->radius((const struct circle *)s));
}
static const struct circle_ops circle_ops = {
    .base = { .area = circle_area, .describe = circle_describe },
    .radius = circle_radius,
};

int main(void)
{
    struct square sq = { { &square_ops, "square" }, 2 };
    struct circle ci = { { &circle_ops.base, "circle" }, 1.5 };
    const struct shape *all[] = { &sq.base, &ci.base };

    for (size_t i = 0; i < sizeof all / sizeof all[0]; i++) {
        all[i]->ops->describe(all[i]);   /* the caller sees only shape */
        putchar('\n');
    }
    printf("circle's table starts with the shape table: %s\n",
           (const void *)&circle_ops == (const void *)&circle_ops.base ? "yes" : "no");
    return 0;
}

square  area   4.00
circle  area   6.75  radius 1.5
circle's table starts with the shape table: yes

Three places where inheritance shows in the example: the inherited slot, the up-call, the derived-only slot.

1. A slot not overridden holds the base’s function. square_ops’s describe is shape_describe. C has no syntax for “inherit”, so inheriting means writing the base’s function into that slot. With one or two tables you write it by hand; with many, chapter 70′s bundle of defaults does it.
2. The up-call. circle_describe calls the base’s shape_describe first and then adds its own part. It is what C++‘s Base::describe() does. It calls the base function by name, so it is a direct call — it does not go through the table.
3. A slot only the derived kind knows. circle_ops holds shape_ops as its first member and adds radius. The object points at &circle_ops.base, so callers see only shape_ops. The circle’s own code turns that pointer back into a const struct circle_ops * to reach its own slot.

Why the last conversion is right is in the standard. A pointer to a structure, suitably converted, points to its initial member, and the other way round (C23 §6.7.3.2p17). The example’s last line shows the two addresses are the same.

This shape — a derived table embedding the base table — has one limit. The shape of the table is fixed at compile time. Which parent, which slots to override — they are written in the source. When kinds arrive at run time, as with plugins, or the parent’s table is known only at run time, the derived table has to be built at run time. That story is told in chapter 72.

71.3 Overloading — one name, several bodies#

First, two words that are often mixed up: overloading and overriding.

When building objects in C, “which functions go in the table and which do not” is a question of overriding. “Should the same name have a different body for each type?” is a question of overloading. Decide the two separately.

71.3.1 Functions for the table, and functions not for it#

Put in the table only the behaviour that differs between kinds. Leave the rest as ordinary functions.

• A shape’s area differs between circles and rectangles → the table.
• A shape’s move(dx, dy) is “add to the position” for every shape → an ordinary function, shape_move.
• shape_name, returning the object’s name, only reads a field of the base struct → an ordinary function.

Ordinary functions are called directly, inlined, and found in one step in a debugger. Put every function in the table “in case it needs changing one day”, and every call pays the costs above. C++ making functions non-virtual by default, with virtual written separately, is the same judgement.

71.3.2 Two ways to overload in C#

C cannot have two functions with the same name. There are two ways round it.

First, split the names. The standard library took this way itself — sqrtf, sqrt, sqrtl; abs, labs, llabs. The type shows in the name, so the reader knows what is called, and searching and linking are never confused.

Second, choose with _Generic (chapter 67). _Generic, added in C11, is a compile-time device that picks a branch by the type of an expression. sqrt(x) from <tgmath.h> goes to sqrtf or sqrtl by the type of x — the header has been there since C99, before _Generic, but today’s implementations usually build it with _Generic.

71.3.3 The pros and cons of _Generic, and what to watch#

_Generic is convenient, but the type it sees is sometimes not the type the programmer had in mind.

/* Overloading in C: _Generic picks a branch by the type of an expression,
   at compile time. The type it sees is not always the type you had in mind. */
#include <stdint.h>
#include <stdio.h>

#define type_name(x) _Generic((x),                          \
    char: "char", signed char: "signed char", unsigned char: "unsigned char", \
    short: "short", unsigned short: "unsigned short",        \
    int: "int", unsigned: "unsigned", long: "long", unsigned long: "unsigned long", \
    long long: "long long", unsigned long long: "unsigned long long", \
    float: "float", double: "double", long double: "long double", \
    char *: "char *", const char *: "const char *", int *: "int *", \
    default: "(something else)")

/* a "print" overloaded by type --- each branch must still compile for every call */
static void print_int(long long v)    { printf("%lld", v); }
static void print_uint(unsigned long long v) { printf("%llu", v); }
static void print_dbl(double v)       { printf("%g", v); }
static void print_str(const char *s)  { printf("\"%s\"", s); }
#define print(x) _Generic((x),                                          \
    int: print_int, long: print_int, long long: print_int,               \
    unsigned: print_uint, unsigned long: print_uint, unsigned long long: print_uint, \
    float: print_dbl, double: print_dbl,                                 \
    char *: print_str, const char *: print_str)(x)

int main(void)
{
    char c = 'a';
    uint8_t byte = 200;
    const int ci = 5;
    int arr[3] = { 0 };

    /* a character constant is an int in C */
    printf("%-16s -> %s\n", "'a'",        type_name('a'));
    printf("%-16s -> %s\n", "c (a char)", type_name(c));
    printf("%-16s -> %s\n", "c + 1",      type_name(c + 1));   /* promoted */
    printf("%-16s -> %s\n", "byte",       type_name(byte));    /* uint8_t is a typedef */
    printf("%-16s -> %s\n", "ci (const)", type_name(ci));      /* qualifier dropped */
    printf("%-16s -> %s\n", "arr",        type_name(arr));     /* the array decays */
    /* char *, not const char * */
    printf("%-16s -> %s\n", "\"text\"",   type_name("text"));
    printf("%-16s -> %s\n", "1.0f * 2",   type_name(1.0f * 2));

    printf("\nprint: ");
    print(42); printf(", "); print(3u); printf(", ");
    print(2.5); printf(", "); print("hi");
    printf("\n");
    /* print(c) would not compile: there is no char branch. A missing branch is an
       error, which is the good news; the bad news is that `c + 1` silently goes
       to the int one. */
    return 0;
}

'a'              -> int
c (a char)       -> char
c + 1            -> int
byte             -> unsigned char
ci (const)       -> int
arr              -> int *
"text"           -> char *
1.0f * 2         -> float

print: 42, 3, 2.5, "hi"

• A character constant 'a' is an int in C (unlike C++).
• c + 1 becomes int by integer promotion (chapter 30).
• uint8_t is only a typedef, so on this machine it goes to the unsigned char branch — on another implementation it could be another branch.
• const int goes to the int branch. The controlling expression undergoes lvalue conversion and loses its qualifiers.
• An array decays to a pointer to its first element. A string literal is char *, not const char *.

And print(c) does not compile — there is no char branch. That a missing branch is an error is the good news; that c + 1 goes silently to the int branch is the bad news. The error messages point at the long expression after the macro has expanded, which is hard to read, and every branch of a _Generic has to pass syntax and type checking even when it is not chosen.

So the judgement is this: overload only when the meaning really is the same. “Square root” means the same whatever the type, so <tgmath.h> suits it. Hide something like “print”, whose format differs by type, behind one name and the reader cannot tell which format will come out. When in doubt, split the names.

71.4 Structs that survive new versions — writing the size into the struct#

Libraries get new versions, and members are added to structs. If the API is one where the caller builds the struct and passes it in, that is a problem: a program compiled against the old header passes a struct of the old size, and the new library reads the new size — someone else’s memory.

The Windows API deals with this by writing the struct’s size into the struct itself: a first member such as cbSize in WNDCLASSEX, cbSize in NONCLIENTMETRICS or lStructSize in OPENFILENAME. The caller fills that place with sizeof, and from that value the library knows “which version of the struct it was given”.

/* A struct that carries its own size, in the style of the Windows API (cbSize).
   Version 2 of the library added a member at the end. A program compiled against
   version 1 still works: the library reads only as many bytes as the caller says. */
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

/* what the version-1 header said */
struct win_opts_v1 { uint32_t size; int32_t width, height; };
/* what the version-2 header says: one member more, at the end, nothing else moved */
struct win_opts    { uint32_t size; int32_t width, height; int32_t dpi; };

static_assert(offsetof(struct win_opts, height) == offsetof(struct win_opts_v1, height),
              "old members must stay where they were");

/* the library (version 2) */
static bool win_open(const void *opts)
{
    uint32_t size;
    memcpy(&size, opts, sizeof size);        /* the first member is always the size */
    struct win_opts o = { .dpi = 96 };       /* defaults for whatever the caller lacks */
    if (size == sizeof(struct win_opts_v1) || size == sizeof(struct win_opts))
        memcpy(&o, opts, size);              /* read no more than the caller has */
    else {
        printf("  size %u: not a version this library knows --- refused\n",
               (unsigned)size);
        return false;
    }
    printf("  size %2u: %d x %d at %d dpi\n", (unsigned)size, o.width, o.height, o.dpi);
    return true;
}

int main(void)
{
    puts("an old program (built with the version-1 header):");
    struct win_opts_v1 old = { .size = sizeof old, .width = 640, .height = 480 };
    win_open(&old);

    puts("a new program:");
    struct win_opts now = { .size = sizeof now, .width = 1920, .height = 1080,
                            .dpi = 144 };
    win_open(&now);

    puts("a program that forgot to fill in the size:");
    struct win_opts careless = { .width = 800, .height = 600 };   /* size stays 0 */
    win_open(&careless);
    return 0;
}

an old program (built with the version-1 header):
  size 12: 640 x 480 at 96 dpi
a new program:
  size 16: 1920 x 1080 at 144 dpi
a program that forgot to fill in the size:
  size 0: not a version this library knows --- refused

The program compiled against the old version passes 12 bytes; the library reads only 12 and fills in the rest (dpi) with the default. The new program passes 16. The program that forgot the size passes 0 and is refused.

The price is a few bytes — and the accident of the caller forgetting to fill in the size. It is worth paying because those few bytes mean the library can move to a new version without the old programs being recompiled. That is one of the reasons programs decades old still run on today’s Windows.

71.4.1 The rules to keep#

A size field is not magic. It works only when these rules are kept.

1. Add members at the end only. Insert one in the middle and the old members’ offsets move. The example’s static_assert guards that.
2. Do not change the meaning of old members. Even at the same place and with the same type, a changed unit makes old programs wrong.
3. The receiver reads only what it knows, and fills the unknown tail with defaults.
4. Keep a fixed list of sizes. Do not accept just any value; accept only the sizes of versions you know.
5. And this approach relies on the calling program and the library laying the struct out according to the same ABI (application binary interface, chapter 61). Old and new versions of the struct put the same members at the same offsets only when both follow the same ABI.

71.4.2 Compared with the other ways#

The third row should be the default for C libraries. If outside code does not know the struct’s size, it need not be recompiled when the size changes. A size field is the second best, for when an opaque type cannot be used — when the caller wants to avoid allocation, or the struct is a simple bundle of options.

71.5 Lifetime — there is no RAII#

C++‘s RAII (resource acquisition is initialisation) calls an object’s destructor by itself when the object goes out of scope. Standard C has no such device. What you make, you destroy — exactly once, on every way out.

Chapter 58 showed techniques for governing lifetimes. In an object system those techniques take the shape of conventions.

The last row is the cheapest and the least used. Instead of governing each object’s lifetime separately, gather things with the same lifetime in one container and govern only the container. Objects made while handling one request die together when the request ends — one arena does it. Entities made during one round of a game die together when the round ends. A hundred objects, one call to destroy them.

71.5.1 Help from outside the standard#

GCC and Clang have an extension, __attribute__((cleanup(f))), that calls a function when a variable goes out of scope. GLib macros such as g_autoptr(GObject) are built on it — which is why they work only with GCC and Clang, not MSVC. On the standard side, work is under way on defer, which records what to do when a block ends, as a technical specification (ISO/IEC TS 25755, chapter 58) — it is not in C23. Either way, they only help you not forget; who owns what is still decided by people.

71.6 Summary#

Every function-pointer table in this chapter was written in the source. The next chapter builds tables at run time, and chapter 73 measures, on this machine, what one call through a table really costs.